A Rate Separation for Agnostic Direct Sums

Technische Samenvatting: Een Rate-separatie voor Agnostische Directe Sommen

Probleemstelling
Het artikel behandelt een fundamentele vraag in het agnostische PAC-leren met betrekking tot het gedrag van directe sommen van conceptklassen. Specifiek wordt onderzocht of de agnostische leercurve van een $r$-voudige directe som, aangeduid als $C^r$, uitsluitend wordt bepaald door de leercurve van een enkelvoudige instantie $\varepsilon_{\text{agn}}(n \mid C)$ en het aantal factoren $r$. Deze vraag werd gesteld door Hanneke, Moran en Waknine [HMW24]. De kernvraag is of de orde van de leersnelheid voor een enkele instantie, gecombineerd met het aantal kopieën, voldoende is om de leersnelheid van de productklasse te voorspellen in de onbeperkte, distributievrije setting.

Methodologie en Opzet
De auteurs maken gebruik van het standaard agnostische PAC-leerframework waarbij het doel is om het excessieve risico te minimaliseren ten opzichte van het beste lid van een conceptklasse $C$.

• Definitie van Directe Som: Voor klassen $C_1 \subseteq Y^{X_1}$ en $C_2 \subseteq Y^{X_2}$ bestaat de directe som $C_1 \otimes C_2$ uit functies $(c_1 \otimes c_2)(x_1, x_2) = (c_1(x_1), c_2(x_2))$.
• Verliesfunctie: Het verlies is gedefinieerd als de zero-one loss op de volledige outputvector, niet als de coördinaat-gewijze Hamming-loss.
• Leercurve: De agnostische leercurve wordt gedefinieerd als $\varepsilon_{\text{agn}}(n \mid C) = \inf_A \sup_D (L_{D,n}(A) - L_D(C))$, waarbij de infimum wordt genomen over leerregels en de supremum over alle distributies.

Om het probleem op te lossen, construeren de auteurs twee specifieke conceptklassen, $F$ en $G$, over het domein en de labelruimte $X = Y = \{0, 1\}$:

1. Klasse $F$: Bevat de twee constante binaire functies ($f_0(x)=0, f_1(x)=1$).
2. Klasse $G$: Bevat de nul-functie en de identiteitsfunctie ($g_0(x)=0, g_1(x)=x$).

De auteurs bewijzen dat hoewel beide klassen dezelfde single-instance leercurve vertonen, hun $r$-voudige directe sommen fundamenteel verschillende leercurves hebben.

Belangrijkste Bijdragen en Resultaten

1. Single-Instance Equivalentie:
   Het artikel stelt vast dat zowel $F$ als $G$ een agnostische leercurve van orde $n^{-1/2}$ hebben.

   • Voor $F$ volgt dit uit de standaard analyse van constante functies en empirische risicominimalisatie.
   • Voor $G$ wordt het resultaat afgeleid door $r=1$ in de hoofdstelling (Theorem 1) te nemen, wat oplevert $\varepsilon_{\text{agn}}(n \mid G) \asymp n^{-1/2}$.

2. Rate-separatie in Directe Sommen (De Hoofdstelling):
   De centrale bijdrage is Theorem 1, die een "rate-separatie" aantoont tussen de directe sommen $F^r$ en $G^r$:

   • Voor $F^r$ (Constante Klasse): De leersnelheid blijft $\Theta(n^{-1/2})$ ongeacht $r$. Het bewijs laat zien dat het excessieve risico wordt beheerst door de schattingsfout van de meest waarschijnlijke constante vector, die schaalt als $1/\sqrt{n}$.
   • Voor $G^r$ (Zero/Identity Klasse): De leersnelheid schaalt als $\Theta(\min\{1, \sqrt{r/n}\})$.
     • Wanneer $r \le n$, is de snelheid $\Theta(\sqrt{r/n})$.
     • Wanneer $r > n$, is het minimax excessieve risico begrensd door een positieve constante (dat wil zeggen, leren is onmogelijk in de limiet).

Consequentelijk, terwijl $\varepsilon_{\text{agn}}(n \mid F) \asymp \varepsilon_{\text{agn}}(n \mid G)$, divergeren de asymptotische orden van $\varepsilon_{\text{agn}}(n \mid F^r)$ en $\varepsilon_{\text{agn}}(n \mid G^r)$ naarmate $r$ groeit.

3. Bewijstechnieken:
   • Bovengrenzen: Afgeleid met standaard empirische risicominimalisatie-bounds voor eindige klassen. Voor $G^r$ maakt de bovengrens gebruik van het feit dat $|G^r| = 2^r$, wat leidt tot een term proportioneel aan $\sqrt{\frac{r \log 2}{n}}$.
   • Ondergrenzen: Vastgesteld met informatie-theoretische instrumenten.
     • Voor $F^r$ wordt een twee-punts Le Cam-methode gebruikt om de moeilijkheid aan te tonen van het onderscheiden tussen twee dominante constante labels.
     • Voor $G^r$ gebruiken de auteurs Assouad's Lemma gecombineerd met Pinsker's ongelijkheid. Ze construeren een familie van distributies geparametriseerd door $\theta \in \{-1, +1\}^r$. In deze constructie wordt een inputcoördinaat $J$ uniform gekozen uit $\{1, \dots, r\}$, waarbij $X = e_J$. Gegeven $J=j$, is de label $Y$ gelijk aan $e_j$ met kans $1/2 + \theta_j \alpha$ en $0^r$ met kans $1/2 - \theta_j \alpha$. Het bewijs relateert de Hamming-afstand van het schatten van $\theta$ aan het excessieve risico, waarbij wordt aangetoond dat het schatten van de $r$-dimensionale parametervector een steekproefomvang vereist die proportioneel is aan $r$.

Betekenis en Claims
Het artikel biedt een negatief antwoord op de vraag over de rate-niveau vorm die door [HMW24] werd gesteld. Het beweert dat de single-instance leercurve en het aantal factoren $r$ niet voldoende zijn om de asymptotische orde van de leercurve van de directe som $C^r$ te bepalen.

De auteurs merken op dat hoewel latere werken (bijv. [Sur24], [HMS26]) directe sommen hebben bestudeerd onder verschillende complexiteitskaders of structurele distributieve aannames, en recent werk over multiclass-leren combinatorische grenzen biedt, geen van deze resultaten de directe-som-curve als een functie van de single-instance leercurve alleen uitdrukt in de onbeperkte, distributievrije setting. Dit artikel lost die kloof expliciet op door een tegenvoorbeeld te tonen waar de structurele eigenschappen van de klasse (constant versus identiteit) leiden tot uiteenlopende gedragingen in de productruimte, ondanks identieke single-instance prestaties.

De conclusie benadrukt dat voor willekeurige conceptklassen, kennis van $\varepsilon_{\text{agn}}(n \mid C)$ en $r$ niet toelaat om $\varepsilon_{\text{agn}}(n \mid C^r)$ te voorspellen. Specifiek voor $G^r$ kan het risico boven nul blijven wanneer $r \ge n$, terwijl het voor $F^r$ blijft afnemen als $n^{-1/2}$.