🤖 machine learning

Online Realizable Regression and Applications for ReLU Networks

Diese Arbeit stellt fest, dass realisierbare Online-Regression unter approximativen Pseudo-Metrik-Verlusten horizonfreie kumulative Verlustschranken zulässt, die durch ein generisches Entropiepotenzialintegral von Überdeckungszahlen charakterisiert sind, ein Ergebnis, das endlichen Regret für ReLU-Netzwerke mit beschränktem Norm zeigt, wo analoge Klassifizierungsprobleme unmöglich sind.

Ursprüngliche Autoren: Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel

Veröffentlicht 2026-06-16

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie spielen ein hochriskantes Ratespiel gegen einen hinterlistigen Gegner. In jeder Runde zeigt Ihnen der Gegner ein Bild (einen Input) und Sie müssen eine Zahl (ein Label) erraten. Nachdem Sie geraten haben, enthüllt der Gegner die wahre Zahl und Sie werden basierend darauf „bestraft“, wie weit Sie daneben lagen.

Die große Frage, die dieses Paper stellt, lautet: Wenn der Gegner nach den Regeln spielt (das heißt, wenn tatsächlich eine perfekte Formel im Spiel verborgen ist, die jede einzelne Zahl perfekt hätte vorhersagen können), können Sie diese Formel schließlich lernen und aufhören, Fehler zu machen? Und wenn ja, wie viele Fehler werden Sie insgesamt machen?

Die Autoren fanden heraus, dass die Antwort stark davon abhängt, wie Sie Ihre Fehler messen.

Die zwei Welten: Klassifikation vs. Regression

Betrachten Sie die Klassifikation als ein Spiel, bei dem Sie „Rot“ oder „Blau“ erraten müssen. Wenn Sie falsch liegen, verlieren Sie einen ganzen Punkt. Das Paper weist darauf hin, dass Sie in dieser Welt, selbst wenn eine perfekte Regel existiert, gezwungen sein könnten, eine unendliche Anzahl von Fehlern zu machen. Es ist, als würde man versuchen, einen geheimen Code zu erraten, bei dem jede falsche Vermutung das Spiel zurücksetzt und der Gegner die Regeln gerade so weit ändert, dass man ewig weiter rätseln muss.

Die Regression ist anders. Hier erraten Sie eine Zahl wie „5,2“ oder „5,8“. Wenn die Wahrheit „5,5“ ist, verlieren Sie nur ein winziges Stück eines Punktes. Das Paper stellt die zentrale Entdeckung, dass in dieser Welt die Realisierbarkeit (die Tatsache, dass eine perfekte Regel existiert) wie ein Sicherheitsnetz wirkt. Selbst ohne davon auszugehen, dass der Gegner zufällig oder nett ist, kann die Tatsache, dass eine perfekte Regel existiert, dazu führen, dass Ihre Gesamtzahl an Fehlern endlich bleibt. Sie werden am Anfang vielleicht einige Fehler machen, aber schließlich werden Sie es richtig machen, und Ihr „Score“ wird aufhören zu wachsen.

Der Kompass des „Entropie-Potenzials“

Um dies zu beweisen, haben die Autoren ein neues mathematisches Werkzeug erfunden, das sie „Entropie-Potenzial“ nennen.

Stellen Sie sich die Menge aller möglichen Regeln, die Ihr Gegner verwenden könnte, als eine riesige, neblige Landschaft vor.

Covering Numbers (Überdeckungszahlen): Um diesen Nebel zu durchqueren, benötigen Sie eine Karte. Eine „Covering Number“ ist wie die Frage: „Wie viele kleine Taschenlampen brauche ich, um in diese Landschaft zu leuchten, um jeden Winkel zu sehen?“ Wenn die Landschaft einfach ist, benötigen Sie wenige Taschenlampen. Wenn sie wild komplex ist, brauchen Sie Millionen.
Das Potenzial: Die Autoren haben eine Formel entwickelt, die die „Schwierigkeit“ dieser Karte auf jeder Zoomstufe zusammenzählt. Dies nennen sie das Entropie-Potenzial.

Die große Regel: Wenn dieser „Potenzial“-Wert endlich ist (das heißt, die Landschaft ist nicht zu unendlich komplex), dann sind Sie garantiert, dass Sie irgendwann aufhören werden, Fehler zu machen, und Ihr Gesamtverlust wird begrenzt sein. Wenn das Potenzial unendlich ist, könnte das Spiel ewig weitergehen.

Anwendung 1: Lipschitz-Funktionen (Die „glatten“ Regeln)

Die Autoren haben dies an einem speziellen Typ von Regel getestet, den Lipschitz-Funktionen genannt werden. Stellen Sie sich diese als Regeln vor, bei denen sich der Output nicht zu abrupt ändern kann; wenn Sie sich im Input ein kleines Stück bewegen, kann sich auch der Output nur ein kleines Stück bewegen. Es ist wie ein sanfter, rollender Hügel statt einer gezackten Klippe.

Sie untersuchten, wie die „Strafe“ funktioniert:

Der sanfte Penalty ( $q > d$ ): Wenn die Strafe für das Falschliegen langsam wächst (wie das Quadrieren des Fehlers), und die Welt nicht zu hochdimensional ist, ist das „Entropie-Potenzial“ endlich. Ergebnis: Sie werden die Regel lernen, und Ihre Gesamtzahl an Fehlern wird begrenzt sein.
Der scharfe Penalty ( $q \le d$ ): Wenn die Strafe zu hart ist oder die Welt zu komplex ist, explodiert das „Potenzial“ ins Unendliche. Ergebnis: Der Gegner kann Sie ewig raten lassen, und Ihre Gesamtzahl an Fehlern wird unbeschränkt wachsen.

Es ist wie der Versuch, auf einem Hügel zu wandern: Wenn der Hügel sanft genug ist, erreichen Sie den Gipfel. Wenn er zu steil oder das Gelände zu zerklüftet ist, könnten Sie in einer Endlosschleife stecken bleiben.

Anwendung 2: ReLU-Netzwerke (Die „neuronalen Netzwerk“-Regeln)

Als Nächstes betrachteten sie ReLU-Netzwerke, die Bausteine moderner KI. Dies sind Funktionen, die wie eine Serie von „An/Aus“-Schaltern aussehen (wie ein Lichtschalter, der nur angeht, wenn der Input positiv ist).

Hier fanden sie eine faszinierende Spaltung zwischen den beiden Welten:

Die Klassifikations-Falle: Wenn Sie versuchen, diese Netzwerke zu nutzen, um „Ja/Nein“ (0/1 Loss) zu erraten, ist das Spiel unmöglich zu gewinnen. Selbst mit einem einfachen Netzwerk kann der Gegner Sie dazu bringen, unendlich viele Fehler zu machen. Die „Littlestone-Dimension“ (ein Maß dafür, wie schwer das Spiel ist) ist unendlich.
Die Regressions-Flucht: Aber wenn Sie dieselben Netzwerke verwenden, um eine Zahl zu erraten (Squared Loss), wird das Spiel gewinnbar!
- Ein Schalter: Wenn das Netzwerk nur einen einzigen „Schalter“ hat, können Sie es mit einer konstanten Anzahl von Fehlern lernen, egal wie groß der Input ist. Es ist, als würde man lernen, einen einzelnen Schalter umzulegen; man bekommt es schnell richtig.
- Viele Schalter: Wenn das Netzwerk $k$ Schalter hat, wächst die Gesamtzahl Ihrer Fehler etwa mit $k^2$ . Es wird schwieriger, je mehr Schalter Sie hinzufügen, aber es bleibt endlich. Sie werden nicht in einer Endlosschleife stecken bleiben.

Der Haken der „Effizienz“

Das Paper fragt auch: „Können wir einen schnellen Computer-Algorithmus finden, um dies zu tun?“

Für einfache Fälle (wie einen Schalter), ja, es gibt einen schnellen, effizienten Weg.
Für komplexere Netzwerke (zwei oder mehr Schalter) deutet das Paper an, dass das Finden eines schnellen Algorithmus wahrscheinlich unmöglich ist (unter der Annahme einiger Standardannahmen der Informatik). Sie können zwar beweisen, dass eine Lösung existiert und dass die Gesamtzahl der Fehler gering ist, aber das eigentliche schnelle Finden dieser Lösung könnte so schwierig sein wie das Lösen eines Puzzles, das länger dauert als das Alter des Universums.

Zusammenfassung

Kurz gesagt zeigt dieses Paper, dass die Art und Weise, wie wir Fehler messen, alles verändert.

In der „Alles-oder-Nichts“-Welt der Klassifikation garantiert die Existenz perfekter Regeln nicht, dass Sie diese lernen können; Sie könnten dazu verdammt sein, ewig zu scheitern.
In der „feingliedrigen“ Welt der Regression (Zahlen erraten) ist die Existenz einer perfekten Regel eine mächtige Garantie. Solange die Regeln nicht zu wahnsinnig komplex sind (gemessen an ihrem „Entropie-Potenzial“), werden Sie sie schließlich lernen, und Ihre Gesamtzahl an Fehlern wird gedeckelt sein.

Die Autoren haben einen neuen „Kompass“ (das Entropie-Potenzial) bereitgestellt, um Ihnen genau zu sagen, wann Sie dieses Spiel gewinnen können und wie viele Fehler Sie wahrscheinlich machen werden, bevor Sie es tun.

Technisches Resümee: Online-realisierbare Regression und Anwendungen für ReLU-Netzwerke

Problemstellung

Diese Arbeit untersucht die realisierbare Online-Regression im adversariellen Setting, in dem keine stochastischen Annahmen oder Margin-Bedingungen auferlegt werden. Der Kern des Problems besteht darin, zu bestimmen, wann Realisierbarkeit (die Existenz einer Zielhypothese $h^* \in \mathcal{H}$ , die die Labels perfekt generiert) eine horizontenfreie (endliche) kumulative Verlustobergrenze impliziert, und um die Komplexitätsparameter zu identifizieren, die diese Schranke bestimmen.

Die Autoren kontrastieren dies mit der Online-Klassifikation, bei der selbst einfache Klassen wie Perzeptronen ohne Margin-Annahmen unendliche Fehlerbounds haben können. In der Regression hingegen kann Realisierbarkeit einen endlichen Gesamtverlust unter metrikähnlichen Verlustfunktionen erzwingen, selbst wenn das analoge Klassifikationsproblem unlernbar ist. Die Studie konzentriert sich auf Verlustfunktionen $\ell$ , die eine approximative Dreiecksungleichung (approximative Pseudo-Metriken) erfüllen – eine Bedingung, die notwendig ist, um degenerative Szenarien zu verhindern, in denen ein Lernender Zwischenlabels mit vernachlässigbarem Verlust vorhersagen kann, obwohl große Abstände im Hypothesenraum bestehen.

Methodik

Das Papier führt eine generische Potenzialmethode ein, um die skalierte Littlestone-Dimension ( $D_{\text{onl}}$ ) nach oben zu begrenzen – eine abstrakte Dimension, die von Attias et al. [2] eingeführt wurde und den minimax-realisierbaren kumulativen Verlust charakterisiert.

Das Entropie-Potenzial-Framework

Anstatt $D_{\text{onl}}$ direkt zu berechnen, was schwierig sein kann, begrenzen die Autoren es mithilfe eines Dudley-Typ-Entropieintegrals, das auf den Überdeckungszahlen der Hypothesenklasse $\mathcal{H}$ unter der induzierten Sup-Pseudo-Metrik $d_\ell(f, g) = \sup_{x} \ell(f(x), g(x))$ basiert.

Definition des Entropie-Potenzials: Für eine Hypothesenklasse $\mathcal{H}$ mit endlichem Durchmesser ist das Entropie-Potenzial definiert als:
$\Phi(\mathcal{H}) = \int_{0}^{\text{diam}(\mathcal{H})} \log_2 N(\mathcal{H}, \varepsilon) \, d\varepsilon$
wobei $N(\mathcal{H}, \varepsilon)$ die $\varepsilon$ -Überdeckungszahl von $\mathcal{H}$ bezüglich $d_\ell$ ist.
Haupttheorem: Die Autoren beweisen, dass für jede $c$ -approximative Pseudo-Metrik-Verlustfunktion die skalierte Littlestone-Dimension durch das Entropie-Potenzial nach oben begrenzt ist:
$D_{\text{onl}}(\mathcal{H}) \leq 4c \cdot \Phi(\mathcal{H})$
Der Beweis nutzt ein Branch-Bound-Argument auf realisierbaren skalierten Littlestone-Bäumen. Durch die Analyse der Version Spaces an jedem Knoten zeigen sie, dass die approximative Dreiecksungleichung erzwingt, dass jede $\varepsilon$ -Überdeckung über die Kinder eines Knotens mit einer Lücke $\gamma$ aufteilt wird, wenn $\varepsilon < \gamma/(2c)$ . Die Integration dieser "Überdeckungs-Aufteilung" über verschiedene Skalen hinweg liefert einen Potenzialabfall proportional zur Lücke, wodurch der gesamte Abstand entlang eines Zweiges durch $\Phi(\mathcal{H})$ begrenzt wird.
Implikation: Wenn $\mathcal{H}$ polynomielle Überdeckungszahlen besitzt (d. h. $N(\mathcal{H}, \varepsilon) \leq (A/\varepsilon)^p$ ), dann ist $\Phi(\mathcal{H}) < \infty$ , was eine horizonfreie realisierbare kumulative Verlustobergrenze impliziert.

Zentrale Beiträge und Ergebnisse

1. Lipschitz-Regression unter $\ell_q$ -Verlust

Die Autoren wenden ihr Framework auf die Klasse $\mathcal{H}_L$ der $L$ -Lipschitz-Funktionen auf $[-1, 1]^d$ unter dem Verlust $\ell_q(y, y') = |y - y'|^q$ an. Sie etablieren einen scharfen Phasenübergang basierend auf der Beziehung zwischen $q$ und der Dimension $d$ :

Lernbares Regime ( $q > d$ ): Das Entropie-Potenzial ist endlich. Der minimax-realisierbare kumulative Verlust ist $\Theta_{d,q}(L^d)$ . Die Autoren stellen einen effizienten deterministischen geeigneten (proper) Algorithmus basierend auf Lipschitz-Envelopes (untere und obere Schranken) bereit, der diese Schranke erreicht.
Unlernbares Regime ( $q \leq d$ ): Das Entropie-Potenzial divergiert.
- Wenn $q < d$ , wächst der minimax-kumulative Verlust polynomisch mit dem Horizont $T$ .
- Wenn $q = d$ , wächst der Verlust logarithmisch mit $T$ .
- In beiden Fällen ist $D_{\text{onl}}(\mathcal{H}) = \infty$ .
Eventuelle Lernbarkeit: Für jede kontinuierliche Verlustfunktion $\ell$ mit $\ell(y,y)=0$ zeigen die Autoren, dass für $L$ -Lipschitz-Funktionen der instantane Verlust $\ell(\hat{y}_t, y_t)$ für $t \to \infty$ gegen 0 konvergiert, unabhängig davon, ob der gesamte kumulative Verlust endlich ist.

2. Beschränkte $k$ -ReLU-Netzwerke

Das Papier untersucht die Klasse $\mathcal{H}_{k,d}$ der beschränkten $k$ -ReLU-Netzwerke (Summen von $k$ ReLUs mit beschränkten Gewichten) über $[-1, 1]^d$ mit quadratischem Verlust.

Trennung von Regression und Klassifikation:
- Klassifikation: Unter 0/1-Verlust ist die realisierbare Online-Klassifikation für $\mathcal{H}_{2,1}$ (zwei versteckte Neuronen, 1D-Input) unmöglich, da die Littlestone-Dimension selbst bei beschränkten Gewichten unendlich ist.
- Regression: Unter quadratischem Verlust erlaubt die realisierbare Online-Regression einen endlichen Gesamtverlust.
Obere Schranken:
- Es existiert ein (informationstheoretischer) Online-Algorithmus mit kumulativem Verlust $O(k^2 \log^4 d) = \tilde{O}(k^2)$ .
- Für ein einzelnes ReLU ( $k=1$ ) gibt es einen effizienten Algorithmus mit $O(1)$ kumulativem Verlust, unabhängig von der Dimension $d$ .
Untere Schranken:
- Eine untere Schranke von $\Omega(k^2 \log(d/k^2))$ wird bewiesen, was zeigt, dass die Abhängigkeit von $k$ und $\log d$ notwendig ist.
Komplexitätstheoretische Härte:
- Unter Annahme der Gap-ETH-Hypothese schließen die Autoren die Existenz eines effizienten geeigneten (proper) Online-Lerners für $k \geq 2$ aus, der einen akkumulierten Verlust von $e^{o(d)}$ in Zeit, die polynomiell in $d$ ist, erreicht. Dies deutet darauf hin, dass ein endlicher Verlust zwar informationstheoretisch möglich ist, das effiziente Berechnen desselben für geeignete Lerner jedoch wahrscheinlich schwer ist.

3. Generalisierung auf tiefe Netzwerke

Die Ergebnisse werden auf Tiefen- $L$ , Breite- $k$ Netzwerke ausgeweitet. Es wird gezeigt, dass der minimax-realisierbare kumulative quadratische Verlust $\tilde{O}(k^L)$ beträgt, mit einer passenden unteren Schranke von $\Omega(k^L \log(d/k^L))$ , wenn $d/k^L \to \infty$ .

Bedeutung und Behauptungen

Das Papier behauptet, dass die Realisierbarkeit die Landschaft des Online-Lernens im Vergleich zum agnostischen Setting grundlegend verändert. Speziell:

Metrische Entropie als Komplexitätsmaß: Die Autoren etablieren, dass für die realisierbare Regression unter approximativen Pseudo-Metriken die metrische Entropie (via $\Phi$ ) eine hinreichende und oft enge Näherung für die Online-Dimension $D_{\text{onl}}$ darstellt. Dies bietet ein konkretes, berechenbares Werkzeug zur Analyse der Lernbarkeit, wo abstrakte Dimensionen unhandlich sind.
Phasenübergänge in der nichtparametrischen Regression: Die Arbeit identifiziert präzise Bedingungen ( $q > d$ ), unter denen die nichtparametrische Lipschitz-Regression horizonfrei ist, was in starkem Kontrast zur Unlernbarkeit der Klassifikation oder Regression mit $q \leq d$ steht.
Lernbarkeit von neuronalen Netzen: Das Papier hebt eine deutliche Trennung zwischen Klassifikation und Regression für ReLU-Netzwerke hervor. Während beschränkte ReLU-Netzwerke im Klassifikationssetting unlernbar sind (unendliche Littlestone-Dimension), erlauben sie in der Regression einen endlichen kumulativen Verlust. Diese Lernbarkeit ist jedoch an Bedingungen geknüpft: Für $k \geq 2$ ist das effiziente Erreichen dieses Verlusts über geeignete (proper) Lerner wahrscheinlich rechnerisch unpraktikabel.
Limitierungen: Die Autoren merken an, dass die Entropie-Potenzial-Schranke nicht immer eng ist; es existieren Klassen, bei denen $\Phi(\mathcal{H}) = \infty$ , aber $D_{\text{onl}}(\mathcal{H}) < \infty$ . Somit dient $\Phi$ als explizite obere Schranke und nicht als vollständige Charakterisierung in allen Fällen.

Die Arbeit stützt sich auf jüngste Fortschritte in der Theorie der Online-Dimensionen [2] und adaptiert Techniken aus stochastischen Prozessen (Dudley-Integrale) an das adversarielle Online-Setting, wobei sie anstelle von sequenziellem Chaining Standard-Überdeckungen aufgrund der Realisierbarkeit-Annahme verwenden.