Technische Samenvatting: Schaalgevoelige Schattering: Leerbaarheid en Evalueerbaarheid bij Optimale Schaal

Probleemstelling

Dit artikel behandelt fundamentele vragen in de statistische leertheorie met betrekking tot klassen van reëelwaardige functies. Specifiek onderzoekt het de precieze relatie tussen drie kernconcepten: agnostische leerbaarheid, uniforme convergentie en de fat-shattering-dimensie (een schaalgevoelige generalisatie van de VC-dimensie).

Hoewel het "Fundamentele Theorema van PAC-leren" de equivalentie van deze notaties voor binaire classificatie vaststelt, vertoonde de reëelwaardige setting historisch gezien een kloof. Eerdere werken (bijv. Bartlett en Long, 1998) toonden aan dat een eindige $\gamma$-fat-shattering-dimensie uniforme convergentie en leerbaarheid impliceert, maar slechts op een schaal van $2\gamma$ (of $c\gamma$ voor $c>2$). Dit liet de vraag open of een multiplicatieve factor 2 in de schaal onvermijdelijk is, een conjectuur die wordt toegeschreven aan Phil Long in het leerboek van Anthony en Bartlett (1999).

Verder behandelt het artikel het gedrag van metrische entropie (logaritme van overdekkingsgetallen) in relatie tot de fat-shattering-dimensie. Eerdere resultaten (Alon et al., 1997; Rudelson en Vershynin, 2006) boden grenzen voor metrische entropie, maar lieten open of de afhankelijkheid van de steekproefgrootte $n$ op optimale schalen kon worden verbeterd van $O(\log^2 n)$ naar $O(\log n)$, en of de schaalfactoren in deze grenzen konden worden verscherpt.

Tot slot past het artikel deze theoretische inzichten toe op de evalueerbaarheid en schatbaarheid van generatieve modellen met behulp van Integral Probability Metrics (IPM's). Een recente dichotomie voor binaire testfuncties (Aiyer et al., 2026) suggereerde dat dergelijke metrieken ofwel schatbaar zijn of zwak evalueerbaar met een optimale schaal van $c=3$. Het uitbreiden hiervan naar reëelwaardige functies werd belemmerd door de bovengenoemde schaal-kloof in resultaten voor uniforme convergentie.

Methodologie

De primaire technische innovatie van de auteurs is een directe grens voor empirische $\ell_\infty$-overdekkingsgetallen, waarbij de standaard omweg via verpakkingsgetallen wordt omzeild.

1. Directe Overdekking via Partiële Conceptklassen:
   In plaats van overdekkingsgetallen te relateren aan verpakkingsgetallen (wat inherent een schaalverlies met zich meebrengt), maken de auteurs gebruik van de theorie van partiële conceptklassen (Lon01; AHHM22). Zij mappingen reëelwaardige functies naar partiële binaire functies op basis van drempels ten opzichte van de schaal $\gamma$. Door de VC-dimensie van deze geïnduceerde partiële klassen te begrenzen, construeren zij expliciete overdekkingen van sub-exponentiële grootte. Dit stelt hen in staat om grenzen voor overdekkingsgetallen direct af te leiden op de optimale schaal $\gamma/2$ in plaats van $2\gamma$.

2. Iteratieve Verfijning:
   Om grenzen op schalen willekeurig dicht bij $\gamma/2$ te bereiken, maken de auteurs gebruik van een iteratieve constructie. Beginnen met een ruwe overdekking, verfijnen zij de dozen recursief, waarbij zij de straal geometrisch verminderen terwijl zij de groei van de grootte van de overdekking beheersen. Dit levert een grens op voor de metrische entropie $H(F, \gamma/2 + \epsilon, n)$ die sublineair is in $n$.

3. Steekproefcompressie en Duale Klassen:
   Voor het regime waarin de schaal groot is ($\gamma > 2\gamma^*$), maken de auteurs gebruik van steekproefcompressieschema's. Zij benutten het feit dat de duale klasse van een functieklass met een eindige fat-shattering-dimensie ook voldoet aan uniforme convergentie (een resultaat afgeleid uit hun hoofdstelling) om verdelingen te verdunnen en compressieschema's met constante grootte te construeren. Dit leidt tot entropiegrenzen van $O(\log n)$.

4. Reductie naar Totale Variatie:
   In de toepassing op evalueerbaarheid construeren de auteurs een reductie van algemene IPM's met een oneindige fat-shattering-dimensie naar de setting van de Totale Variatie (TV) afstand. Zij construeren zorgvuldig mengsels van verdelingen over geschaterde sets om aan te tonen dat de IPM asymptotisch gedraagt als de TV-afstand, waarbij de optimale schaalkonstanten behouden blijven.

Belangrijkste Bijdragen en Resultaten

1. Oplossing van de Schaal-kloof (Stelling 1)

Het artikel vestigt een exact analoog van het Fundamentele Theorema van PAC-leren voor reëelwaardige klassen. Voor een begrenste functieklass $F$ en schaal $\gamma > 0$ zijn de volgende gelijkwaardig:

1. $F$ is $\gamma/2$-leerbaar.
2. $F$ voldoet aan $\gamma$-uniforme convergentie.
3. Voor elke $\gamma' > \gamma$ is de $\gamma'$-fat-shattering-dimensie van $F$ eindig.

Betekenis: Dit resultaat weerlegt de conjectuur dat een factor-2-kloof onvermijdelijk is. Het bewijst dat leerbaarheid en uniforme convergentie gelden op de optimale schaal $\gamma/2$ (voor leerbaarheid) en $\gamma$ (voor convergentie), mits de fat-shattering-dimensie eindig is op elke schaal strikt groter dan $\gamma$.

2. Scherpe Metrische Entropiegrenzen (Stelling 2)

Het artikel biedt een volledige karakterisering van de groei van metrische entropie $H(F, \gamma, n)$ gebaseerd op de kritische schaal $\gamma^* = \inf\{\gamma : \text{fat}_\gamma(F) < \infty\}$:

• Lineair Regime ($\gamma < \gamma^*/2$): $H(F, \gamma, n) = \Theta(n)$.
• Intermediair Regime ($\gamma^*/2 < \gamma \le 2\gamma^*$): $H(F, \gamma, n) = O(\log^2 n)$. Het artikel toont aan dat deze grens strak is (tot op termen van lagere orde) voor $\gamma \in (\gamma^*/2, \gamma^*)$, waarmee een vraag van Alon et al. (1997) over de noodzaak van de factor $\log^2 n$ wordt opgelost.
• Grote Schaal Regime ($\gamma > 2\gamma^*$): $H(F, \gamma, n) = O(\log n)$. Dit bevestigt dat de exponent kan worden teruggebracht tot 1 op voldoende grote schalen, waarmee een vraag van Rudelson en Vershynin (2006) wordt opgelost.

3. Dichotomie voor Evalueerbaarheid van Generatieve Modellen (Stelling 3 & Proposition 1)

Door de scherpe schaalgevoelige resultaten toe te passen, vestigt het artikel een dichotomie voor begrenste Integral Probability Metrics (IPM's):

• Als de fat-shattering-dimensie eindig is voor alle $\gamma > 0$, is de IPM schatbaar (en dus sterk evalueerbaar met $c=1$).
• Als de fat-shattering-dimensie oneindig is voor een zekere $\gamma \in (0, 1/2)$, is de IPM zwak evalueerbaar met optimale schaal $c=3$, maar niet voor enige $c < 3$.

Betekenis: Dit breidt de binaire dichotomie van Aiyer et al. (2026) uit naar reëelwaardige functies. Het bewijs is cruciaal afhankelijk van het vermogen van de auteurs om uniforme convergentie op schaal $\gamma$ vast te stellen zonder het factor-2-verlies; zonder dit zou het argument voor de optimale schaal $c=3$ falen.

4. Sluitingseigenschappen

Het artikel toont aan dat de eigenschappen van $\gamma$-leerbaarheid en $\gamma$-uniforme convergentie invariant zijn onder:

• Dualiteit: De duale klasse van een uniform convergente klasse is ook uniform convergent.
• Aggregatie: Het aggregeren van klassen via 1-Lipschitz-functies behoudt uniforme convergentie op dezelfde schaal.

Betekenis en Claims

De auteurs claimen dat hun werk verschillende langdurig openstaande vragen in de leertheorie oplost:

1. Weerlegging van de Factor-2 Conjectuur: Door te bewijzen dat leerbaarheid en uniforme convergentie gelden op de optimale schalen, beantwoordt het artikel definitief de vraag gesteld door Anthony en Bartlett (1999), en toont het aan dat de factor-2-kloof niet inherent is.
2. Scherpe Entropiegrenzen: Het artikel legt de precieze afhankelijkheid van metrische entropie van de steekproefgrootte $n$ en de schaal $\gamma$ vast, en verduidelijkt exact wanneer $O(\log n)$-grenzen haalbaar zijn versus wanneer $O(\log^2 n)$ noodzakelijk is.
3. Kwalitatieve Karakterisering van Evalueerbaarheid: Het artikel betoogt dat de kwantitatieve verbetering van een factor 2 naar 1 in de schaal van uniforme convergentie een kwalitatieve karakterisering van de evaluatie van generatieve modellen ontsluit, en een scherpe dichotomie vestigt tussen schatbaarheid en zwakke evalueerbaarheid met $c=3$.

De auteurs merken op dat hoewel zij het asymptotische gedrag en het bestaan van de dichotomie oplossen, het precieze gedrag van entropie in het intermediaire bereik $\gamma^* < \gamma \le 2\gamma^*$ en scherpe steekproefcomplexiteitsgrenzen voor leren op de optimale schaal open problemen blijven. Bovendien wordt de relatie tussen fat-shattering-dimensie en overdekkingsgetallen onder andere $\ell_p$-metrieken overgelaten aan toekomstig onderzoek.