Agnostisches Lernen in nahezu optimaler Zeit dank neuer Analyse

Ein neues Ergebnis auf arXiv (2603.06027v1) zeigt, dass das Lernen von Konzeptklassen unter Gaußschen Randverteilungen im agnostischen Modell wesentlich schneller möglich ist, als bisher angenommen. Der Schlüssel liegt in der Beziehung zwischen der Komplexität des Lernens und der L1‑Approximation durch Polynome niedriger Ordnung.

Für jede Konzeptklasse, deren Gaußscher Flächeninhalt höchstens Γ beträgt, konnte Klivans und Kollegen 2008 bereits einen Polynomgrad d = O(Γ²/ε⁴) nachweisen, der eine ε‑Annäherung ermöglicht. Die neue Analyse reduziert diesen Grad auf d = ~O(Γ²/ε²), was die Lernzeit drastisch verkürzt und die bisher besten Schranken für zahlreiche Konzeptklassen verbessert.

In Kombination mit den unteren Schranken von Diakonikolas et al. (2021) liefert die Arbeit nahezu optimale Grenzen für das agnostische Lernen von Polynom‑Schwellenfunktionen im statistischen Abfrage‑Modell. Der Beweis stützt sich auf eine direkte Analogie zu einer Konstruktion von Feldman et al. (2020), die zuvor die L1‑Approximation auf dem Booleschen Hyperwürfel untersuchte.