Technische Samenvatting: Online Realiseerbare Regressie en Toepassingen voor ReLU-netwerken

Probleemstelling

Dit artikel onderzoekt realiseerbare online regressie in de adversariële setting, waarbij geen stochastische aannames of margecondities worden opgelegd. De kern van het probleem is te bepalen wanneer realiseerbaarheid (het bestaan van een doelhypothese $h^* \in \mathcal{H}$ die de labels perfect genereert) impliceert dat er een horizon-vrije (eindige) cumulatieve verliesgrens bestaat, en om de complexiteitsparameters te identificeren die deze grens bepalen.

De auteurs contrasteren dit met online classificatie, waar zelfs eenvoudige klassen zoals Perceptrons oneindige foutengrenzen kunnen hebben zonder marge-aannames. In regressie kan realiseerbaarheid echter een eindig totaal verlies afdwingen onder metriek-achtige verliezen, zelfs wanneer het analoge classificatieprobleem onleerbaar is. De studie richt zich op verliesfuncties $\ell$ die voldoen aan een benaderende driehoeksongelijkheid (benaderende pseudo-metrieken), een conditie die noodzakelijk is om degeneratieve scenario's te voorkomen waarbij een leerder tussenliggende labels met verwaarloosbaar verlies kan voorspellen, ondanks grote gaten in de hypotheseruimte.

Methodologie

Het artikel introduceert een generieke potentieelmethode om de geschaalde Littlestone-dimensie ($D_{\text{onl}}$) te begrenzen, een abstracte dimensie geïntroduceerd door Attias et al. [2] die de minimax realiseerbare cumulatieve verlieskarakteriseert.

Het Entropie-potentieel Raamwerk

In plaats van direct $D_{\text{onl}}$ te berekenen, wat moeilijk kan zijn, begrenzen de auteurs het met een Dudley-type entrope-integraal gebaseerd op de dekkingsgetallen van de hypotheseklasse $\mathcal{H}$ onder de geïnduceerde sup-pseudo-metriek $d_\ell(f, g) = \sup_{x} \ell(f(x), g(x))$.

1. Definitie van Entropie-potentieel: Voor een hypotheseklasse $\mathcal{H}$ met een eindige diameter is het entropie-potentieel gedefinieerd als:
   $$\Phi(\mathcal{H}) = \int_{0}^{\text{diam}(\mathcal{H})} \log_2 N(\mathcal{H}, \varepsilon) \, d\varepsilon$$
   waarbij $N(\mathcal{H}, \varepsilon)$ het $\varepsilon$-dekkingsgetal van $\mathcal{H}$ is met betrekking tot $d_\ell$.

2. Hoofdstelling: De auteurs bewijzen dat voor elke $c$-benaderende pseudo-metriek verlies, de geschaalde Littlestone-dimensie wordt begrensd door het entropie-potentieel:
   $$D_{\text{onl}}(\mathcal{H}) \leq 4c \cdot \Phi(\mathcal{H})$$
   Het bewijs maakt gebruik van een branch bound-argument op realiseerbare geschaalde Littlestone-bomen. Door de versie-ruimtes bij elke knoop te analyseren, tonen ze aan dat de benaderende driehoeksongelijkheid ervoor zorgt dat elke $\varepsilon$-dek de kinderen van een knoop met een gat $\gamma$ splitst wanneer $\varepsilon < \gamma/(2c)$. Het integreren van deze "dek-splitsing" over verschillende schalen levert een potentieel-daling op die proportioneel is aan het gat, waardoor het totale gat langs elke tak wordt begrensd door $\Phi(\mathcal{H})$.

3. Implicatie: Als $\mathcal{H}$ polynomiale dekkingsgetallen heeft (d.w.z. $N(\mathcal{H}, \varepsilon) \leq (A/\varepsilon)^p$), dan is $\Phi(\mathcal{H}) < \infty$, wat een horizon-vrije realiseerbare cumulatieve verliesgrens impliceert.

Belangrijkste Bijdragen en Resultaten

1. Lipschitz Regressie onder $\ell_q$ Verlies

De auteurs passen hun raamwerk toe op de klasse $\mathcal{H}_L$ van $L$-Lipschitz functies op $[-1, 1]^d$ onder het verlies $\ell_q(y, y') = |y - y'|^q$. Ze stellen een scherpe faseovergang vast op basis van de relatie tussen $q$ en de dimensie $d$:

• Leerbaar Regime ($q > d$): Het entropie-potentieel is eindig. Het minimax realiseerbare cumulatieve verlies is $\Theta_{d,q}(L^d)$. De auteurs bieden een efficiënt deterministisch proper algoritme aan gebaseerd op Lipschitz-enveloppen (onder- en bovengrenzen) dat deze grens bereikt.
• Onleerbaar Regime ($q \leq d$): Het entropie-potentieel divergeert.
  • Als $q < d$, groeit het minimax cumulatieve verlies polynomiaal met de horizon $T$.
  • Als $q = d$, groeit het verlies logaritmisch met $T$.
  • In beide gevallen is $D_{\text{onl}}(\mathcal{H}) = \infty$.
• Uiteindelijke Leerbaarheid: Voor elke continue verliesfunctie $\ell$ met $\ell(y,y)=0$, laten de auteurs zien dat voor $L$-Lipschitz functies het instantane verlies $\ell(\hat{y}_t, y_t)$ convergeert naar 0 als $t \to \infty$, ongeacht of het totale cumulatieve verlies eindig is.

2. Begrensde $k$-ReLU Netwerken

Het artikel bestudeert de klasse $\mathcal{H}_{k,d}$ van begrensde $k$-ReLU netwerken (sommen van $k$ ReLU's met begrensde gewichten) over $[-1, 1]^d$ met kwadratisch verlies.

• Regressie versus Classificatie Separatie:
  • Classificatie: Onder 0/1 verlies is realiseerbare online classificatie onmogelijk voor $\mathcal{H}_{2,1}$ (twee verborgen neuronen, 1D input), aangezien de Littlestone-dimensie oneindig is, zelfs met begrensde gewichten.
  • Regressie: Onder kwadratisch verlies staat realiseerbare online regressie een eindig totaal verlies toe.
• Bovengrenzen:
  • Er bestaat een (informatie-theoretisch) online algoritme met cumulatief verlies $O(k^2 \log^4 d) = \tilde{O}(k^2)$.
  • Voor een enkele ReLU ($k=1$) is er een efficiënt algoritme met $O(1)$ cumulatief verlies, onafhankelijk van de dimensie $d$.
• Ondergrenzen:
  • Een ondergrens van $\Omega(k^2 \log(d/k^2))$ wordt bewezen, wat aantoont dat de afhankelijkheid van $k$ en $\log d$ noodzakelijk is.
• Computationele Hardheid:
  • Onder de aanname van de Gap-ETH hypothese, sluiten de auteurs het bestaan uit van een efficiënt proper online leerder voor $k \geq 2$ die een cumulatief verlies $e^{o(d)}$ bereikt in tijd die polynomiaal is in $d$. Dit suggereert dat hoewel eindig verlies informatie-theoretisch mogelijk is, het efficiënt berekenen ervan voor proper learners waarschijnlijk moeilijk is.

3. Generalisatie naar Diepe Netwerken

De resultaten worden uitgebreid naar diepte-$L$, breedte-$k$ netwerken. Het minimax realiseerbare cumulatieve kwadratische verlies wordt getoond als $\tilde{O}(k^L)$, met een bijbehorende ondergrens van $\Omega(k^L \log(d/k^L))$ wanneer $d/k^L \to \infty$.

Betekenis en Claims

Het artikel claimt dat realiseerbaarheid het landschap van online leren fundamenteel verandert vergeleken met de agnostische setting. Specifiek:

1. Metrische Entropie als Complexiteitsmaat: De auteurs stellen vast dat voor realiseerbare regressie onder benaderende pseudo-metrieken, de metrische entropie (via het entropie-potentieel $\Phi$) een voldoende en vaak nauwe benadering is voor de online dimensie $D_{\text{onl}}$. Dit biedt een concreet, berekenbaar instrument voor het analyseren van leerbaarheid waar abstracte dimensies onhandelbaar zijn.
2. Faseovergangen in Nonparametrische Regressie: Het werk identificeert precieze condities ($q > d$) waaronder nonparametrische Lipschitz-regressie horizon-vrij is, wat scherp contrasteert met de onleerbaarheid van classificatie of regressie met $q \leq d$.
3. Leerbaarheid van Neurale Netwerken: Het artikel benadrukt een scherpe scheiding tussen classificatie en regressie voor ReLU-netwerken. Hoewel begrensde ReLU-netwerken onleerbaar zijn in de classificatie-setting (oneindige Littlestone-dimensie), staan ze een eindig cumulatief verlies toe in de regressie-setting. Deze leerbaarheid gaat echter gepaard met kanttekeningen: voor $k \geq 2$ is het efficiënt bereiken van dit verlies via proper learners waarschijnlijk computationeel onhandelbaar.
4. Beperkingen: De auteurs merken op dat de entropie-potentieel grens niet altijd nauw is; er bestaan klassen waar $\Phi(\mathcal{H}) = \infty$ maar $D_{\text{onl}}(\mathcal{H}) < \infty$. Zo dient $\Phi$ als een expliciete bovenliggende surrogaat in plaats van een volledige karakterisering in alle gevallen.

Het werk steunt op recente ontwikkelingen in de online dimensie-theorie [2] en past technieken uit de stochastische processen (Dudley-integralen) aan voor de adversariële online setting, waarbij zij sequential chaining vermijden ten gunste van standaard dekkingsmethoden vanwege de realiseerbaarheidsaanname.