Neuer Algorithmus löst Lernproblem von Halbflächen bei faktorisierten Verteilungen

Das Lernen von Schnittstellen zweier Halbflächen ist ein zentrales Problem der Computational Learning Theory. Trotz jahrzehntelanger Forschung ist es noch immer unklar, ob ein polynomieller Algorithmus existiert, der die Datenpunkte mit einem gegebenen Rand γ und einer Dimensionalität d verarbeiten kann. Bestehende Verfahren benötigen quasi-polynomielle Laufzeiten dO(log(1/γ)) und zeigen, dass die CSQ‑Hardness‑Barriere für reine Korrelationsabfragen unvermeidlich ist.

In der aktuellen Veröffentlichung wird ein völlig neuer Ansatz vorgestellt, der die CSQ‑Hardness umgeht. Der Algorithmus funktioniert für eine breite Klasse faktorisierbarer Verteilungen – ein Zwischenraum zwischen verteilungsabhängigen und verteilungsfreien Modellen – und erzielt eine Laufzeit von poly(d, 1/γ). Damit wird ein deutlicher Abstand zwischen CSQ‑ und allgemeineren SQ‑Methoden demonstriert.

Der Schlüssel liegt in einer innovativen Dualitätsstruktur, die die Momenten‑Tensoren der Randverteilungen beschreibt. Aufbauend auf dieser Analyse kombiniert der Algorithmus eine verfeinerte Variante von Jennrichs Verfahren mit einer PCA‑Analyse zufälliger Projektionen, um die Schnittpunkte effizient zu rekonstruieren.

Diese Ergebnisse markieren einen bedeutenden Fortschritt in der Theorie des Lernens von Halbflächen und eröffnen neue Wege für die Entwicklung schnellerer Lernalgorithmen unter realistischeren Verteilungsannahmen.