Optimistic Rates for Multiclass PAC Learning

Résumé Technique : Taux Optimistes pour l'Apprentissage PAC Multiclasse

Énoncé du Problème
L'article traite de la difficulté statistique de la classification multiclasse dans le cadre de l'apprentissage PAC. Les limites existantes en pire cas pour l'apprentissage multiclasse dépendent de deux paramètres de capacité : la dimension de Natarajan ($d_N$) et la dimension de Daniely–Shalev-Shwartz ($d_{DS}$). Bien que les taux optimaux soient connus aux deux extrêmes — l'apprentissage réalisable ($L^\star = 0$) et l'apprentissage agnostique complet ($L^\star$ constant) — le comportement intermédiaire reste non résolu. Plus précisément, les limites actuelles en pire cas agnostique évoluent selon $\sqrt{d_N/n} + d_{DS}/n$, ne reflétant pas le fait que si le meilleur classificateur est presque correct (faible risque de l'oracle $L^\star$), le problème d'apprentissage devrait être plus facile. L'objectif est d'établir un « taux optimiste » où le terme de fluctuation évolue avec $L^\star$, interpolant entre le taux rapide réalisable et le taux lent agnostique.

Méthodologie
Les auteurs proposent un apprenant, RMC (Relative Menu Compression — Compression de Menu Relative), qui réalise cette interpolation sans connaissance préalable de $L^\star$ ou du niveau de confiance $\delta$. L'architecture de la preuve repose sur une stratégie de division d'échantillons en trois blocs, adaptant la réduction « cover–menu–compression » de [CEH+26] mais en introduisant une interface statistique novatrice.

1. Bloc 1 (Cover - Couverture) : Un compresseur déterministe réduit la classe d'hypothèses infinie à une famille finie $\hat{\mathcal{F}}$ de taille approximativement $d_{DS} \log^2 n$. Cette étape garantit que pour tout comparateur $h$, il existe un « témoin canonique » dans $\hat{\mathcal{F}}$ qui est en accord avec $h$ sur la région où $h$ est correct.
2. Bloc 2 (Menu) : Un algorithme de poids multiplicatifs apprend un « menu » $\mu$ (un ensemble de labels candidats pour chaque entrée) qui couvre les labels du témoin canonique sur la région correcte de l'oracle. Cette étape contrôle la probabilité qu'un label correct soit absent du menu, un mode de défaillance régi par $d_{DS}$.
3. Bloc 3 (Compression) : Une fois le menu fixé, le problème se réduit à la classification binaire au sein du menu. L'apprenant applique une règle de compression qui domine empiriquement un comparateur fixe.

L'innovation technique centrale est un Théorème de Compression Relative face au Comparateur (Théorème 3.3). Contrairement aux limites de compression standard qui comparent le risque de population de l'apprenant à son risque empirique (produisant une fluctuation de $\sqrt{k/n}$), ce théorème compare directement le risque de population de l'apprenant au risque de population $L(h)$ d'un comparateur fixe $h$. Il établit que si une règle de compression de taille $k$ n'a pas une perte empirique plus grande que $h$, alors :
$$L(h) \leq L(h) + O\left(\sqrt{L(h) \frac{k \log n}{n}} + \frac{k \log n}{n}\right)$$
Crucialement, le coefficient de $L(h)$ est exactement 1, et la fluctuation évolue avec $\sqrt{L(h)}$. Ceci est réalisé en utilisant des descriptions ordonnées avec des indices répétés et des inégalités de Bernstein à un côté, sans nécessiter d'hypothèses de stabilité.

Contributions Clés

1. Taux Optimiste Multiclasse Optimal : L'article prouve que pour une classe avec dimension de Natarajan $d_N$ et dimension DS $d_{DS}$, l'excès de risque optimal est :
   $$\tilde{\Theta}\left( \sqrt{\frac{L^\star d_N}{n}} + \frac{d_{DS}}{n} \right)$$
   Ce résultat est uniforme dans la taille de l'alphabet. Le terme $d_N$ se localise sur le risque de l'oracle $L^\star$, tandis que le terme $d_{DS}$ reste un résidu d'ordre réalisable.
2. Borne Inférieure Correspondante : Les auteurs construisent une classe d'hypothèses unique et une distribution unique pour tout $L^\star$ fixé qui forcent simultanément les deux termes de la borne supérieure. Cela confirme que la séparation des rôles — $d_{DS}$ contrôlant la couverture des labels et $d_N$ contrôlant les fluctuations au sein du menu — est intrinsèque au problème, et non un artefact de l'analyse.
3. Extension à l'Apprentissage de Liste : L'architecture est étendue à l'apprentissage de liste (produire $r$ labels). Les auteurs dérivent des taux optimistes contre le meilleur $r$-uplet d'hypothèses, localisant la fluctuation au risque de liste de l'oracle. Cela résout une attente de [Pab26] concernant la nécessité d'un terme de fluctuation de Natarajan $r$-aire et améliore la borne inférieure connue de l'apprentissage réalisable de liste en supprimant un facteur $r$.
4. Vérification Formelle : Les principaux théorèmes et leurs preuves sont vérifiés par machine dans Lean 4, assurant la correction des constantes et des dépendances logiques.

Résultats

• Borne Supérieure (Théorème 3.1) : L'apprenant RMC atteint le taux $\tilde{O}(\sqrt{L^\star d_N/n} + d_{DS}/n)$ avec une probabilité $1-\delta$. L'apprenant est sans paramètre (indépendant de $L^\star$ et $\delta$).
• Borne Inférieure (Théorème 4.1) : Pour toute $1 \leq d_N \leq d_{DS}$, il existe une classe et une distribution où tout apprenant subit un excès de risque attendu d'au moins $\Omega(\sqrt{L^\star d_N/n} + d_{DS}/n)$. La construction utilise un produit d'un cube de Natarajan bruité et d'un pseudo-cube (dérivé de [BCD+22]) pour séparer les deux dimensions.
• Apprentissage de Liste (Théorèmes 5.1 & 5.2) : Le taux optimiste s'étend aux apprenants de liste contre le meilleur $r$-uplet, avec une borne inférieure confirmant la nécessité du terme de fluctuation. De plus, une nouvelle borne inférieure pour l'apprentissage de liste réalisable supprime le facteur $r$ présent dans les résultats précédents [HMZ24].

Signification et Revendications
L'article prétend combler l'écart entre les taux connus pour le réalisable et l'agnostique en multiclasse, fournissant le premier taux optimiste sans distribution et sans paramètre pour l'apprentissage multiclasse.

• Unification Théorique : Il démontre que le principe de comparaison « coefficient-un », précédemment établi pour la classification binaire via la géométrie du cube booléen [MQZ26], peut être élevé aux contextes multiclasses en découplant la géométrie des labels (gérée par le menu/couverture) de la fluctuation stochastique (gérée par la compression relative).
• Séparation Intrinsèque : La borne inférieure certifie que les deux paramètres de capacité ($d_N$ et $d_{DS}$) jouent des rôles distincts et non interchangeables : $d_{DS}$ dicte si les labels corrects sont visibles (couverture), tandis que $d_N$ dicte la difficulté de choisir parmi les labels visibles (fluctuation).
• Limites : Les auteurs notent que les facteurs logarithmiques dans la borne supérieure ne sont pas optimisés, et que l'apprenant est informationnel (pas nécessairement efficace sur le plan computationnel). Les résultats supposent un alphabet de labels fini, bien que la borne soit uniforme en sa cardinalité.

Le travail est présenté comme une résolution de la question d'interpolation dans l'apprentissage PAC multiclasse, établissant que la difficulté statistique dépend effectivement du niveau de réalisabilité, et fournissant le taux précis auquel cette difficulté se dégrade.