🤖 machine learning

A Rate Separation for Agnostic Direct Sums

Cet article démontre que le taux d'apprentissage PAC agnostique d'une somme directe de classes de concepts n'est pas uniquement déterminé par les taux d'apprentissage des instances uniques de ses composantes, comme le montre la construction de deux classes ayant des courbes d'apprentissage identiques en $n^{-1/2}$ qui produisent des taux différents lorsqu'elles sont combinées.

Auteurs originaux : Mihir More, Aritra Das, Debayan Gupta

Publié 2026-08-10

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Mihir More, Aritra Das, Debayan Gupta

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un monde où les machines apprennent en jouant à un jeu de devinettes. Dans le domaine de l'informatique connu sous le nom d'« apprentissage automatique » (machine learning), nous demandons souvent : de combien d'exemples une machine a-t-elle besoin pour devenir vraiment douée dans une tâche ? C'est l'étude des « courbes d'apprentissage ». Considérez cela comme l'entraînement d'un chiot. Si vous voulez qu'un chiot apprenne à s'asseoir, vous aurez peut-être besoin de dix friandises. Si vous voulez qu'il apprenne à se rouler par terre, vous en aurez peut-être besoin de vingt. La « courbe d'apprentissage » est simplement un graphique montrant comment les erreurs du chiot diminuent à mesure qu'il mange plus de friandises.

Imaginez maintenant que vous avez un super-chiot qui n'apprend pas seulement un tour, mais tout un ensemble de tours à la fois. Peut-être doit-il apprendre à s'asseoir, à se rouler par terre et à aboyer, tout cela lors de la même séance. En mathématiques, cela s'appelle une « somme directe ». Vous prenez un problème d'apprentissage simple et vous le multipliez par lui-même de nombreuses fois pour créer un défi plus vaste et plus complexe. Pendant longtemps, les scientifiques se sont demandé si la difficulté de ce grand ensemble était simplement un problème mathématique simple : si vous connaissez la difficulté d'un seul tour, et que vous savez combien de tours sont regroupés, pouvez-vous simplement faire le calcul pour savoir quelle sera la difficulté de l'ensemble ? Il semblait logique que si un tour est facile, dix tours devraient être dix fois plus difficiles, ou peut-être un peu plus difficiles. Mais comme nous allons le voir, l'univers de l'apprentissage est plein de surprises, et parfois, le tout est très différent de la somme de ses parties.

Cet article, intitulé « A Rate Separation for Agnostic Direct Sums », plonge précisément dans cette question. Les auteurs, Mihir More, Aritra Das et Debayan Gupta, se sont mis à tester une idée populaire : que la vitesse à laquelle une machine apprend une tâche unique (le « taux d'apprentissage d'une instance unique ») détermine complètement la vitesse à laquelle elle apprendra un ensemble de ces tâches (le « taux de somme directe »). Ils voulaient voir si connaître la vitesse d'apprentissage d'un problème était suffisant pour prédire la vitesse d'apprentissage d'une version massive et combinée de ce même problème.

Les chercheurs ont découvert que la réponse est un « non » catégorique. Ils ont prouvé que deux problèmes d'apprentissage complètement différents peuvent sembler identiques lorsque vous les testez un par un, mais qu'une fois regroupés, ils se comportent de manières totalement opposées. Pour le démontrer, ils ont créé deux « classes de concepts » fictives (qui sont simplement des ensembles de règles que la machine tente d'apprendre). Appelons-les la « Classe Constante » et la « Classe Identité ».

La première classe, la « Classe Constante », est comme une horloge cassée qui indique toujours la même heure, peu importe. La machine doit simplement deviner quelle est la constante. La seconde classe, la « Classe Identité », est comme un miroir ; quel que soit l'apport que vous lui donnez, elle se contente de le recopier. Lorsque la machine essaie d'apprendre l'une de ces règles, les deux sont également faciles. Elles suivent toutes deux une courbe d'apprentissage où les erreurs diminuent à un rythme de $n^{-1/2}$ (ce qui signifie que si vous doublez vos données d'entraînement, vous devenez un peu meilleur, mais pas deux fois meilleur). C'est un rythme standard, prévisible.

Cependant, le rebondissement survient lorsque les auteurs regroupent ces règles. Ils ont créé une « somme directe » en prenant 100 copies de la Classe Constante et 100 copies de la Classe Identité et en demandant à la machine de les apprendre toutes à la fois. C'est ici que la magie opère. Le groupe de Constantes est resté facile, conservant ce même rythme d'apprentissage régulier. Mais le groupe d'Identités est devenu un cauchemar. À mesure que le nombre de copies ( $r$ ) augmentait, la courbe d'apprentissage du groupe d'Identités ralentissait de manière spectaculaire, devenant beaucoup plus difficile à apprendre que le groupe de Constantes.

L'article prouve mathématiquement que pour le groupe d'Identité, le taux d'apprentissage dépend fortement du nombre de copies d'une manière dont le groupe de Constantes ne dépend pas. Plus précisément, lorsque le nombre de copies ( $r$ ) est élevé, le taux d'erreur pour le groupe d'Identité reste obstinément élevé, refusant de diminuer aussi vite que celui du groupe de Constantes. En fait, si vous avez suffisamment de copies, la machine pourrait rester bloquée à un taux d'erreur élevé, peu importe la quantité de données que vous lui donnez, alors que le groupe de Constantes continue de s'améliorer.

Les auteurs ont utilisé des outils mathématiques rigoureux, notamment un lemme célèbre appelé « lemme d'Assouad » et une technique appelée « inégalité de deux points de Le Cam », pour construire une preuve inattaquable. Ils ne se sont pas contentés d'une simulation sur ordinateur ; ils ont montré que cette séparation est une loi fondamentale de la théorie de l'apprentissage. Ils ont démontré que l'on ne peut pas simplement regarder la vitesse à laquelle une machine apprend une chose et supposer que l'on sait à quelle vitesse elle apprendra cent de ces choses. La structure des règles compte tout autant que le nombre de règles.

En fin de compte, cet article retire le tapis sous les pieds d'une hypothèse simple. Il nous dit que dans le monde de l'apprentissage automatique, le contexte est roi. Deux problèmes peuvent sembler identiques de manière isolée, mais se comporter comme de l'huile et de l'eau lorsqu'ils sont mélangés. La vitesse d'apprentissage d'une tâche unique n'est pas une boule de cristal pour la vitesse d'apprentissage d'un système complexe. Les auteurs ont montré que la relation entre l'apprentissage d'une instance unique et l'apprentissage par somme directe est bien plus mystérieuse et complexe que ce que l'on avait réalisé auparavant, prouvant que dans le grand jeu de l'apprentissage, le tout n'est définitivement pas la simple somme de ses parties.

Résumé Technique : Une séparation de taux pour les sommes directes agnostiques

Énoncé du Problème
L'article traite d'une question fondamentale concernant l'apprentissage PAC agnostique relatif au comportement des sommes directes de classes de concepts. Plus précisément, il examine si la courbe d'apprentissage agnostique d'une somme directe $r$ -uple, notée $C^r$ , est déterminée uniquement par la courbe d'apprentissage d'une instance unique $\varepsilon_{\text{agn}}(n \mid C)$ et le nombre de facteurs $r$ . Cette question a été posée par Hanneke, Moran et Waknine [HMW24]. L'interrogation centrale est de savoir si l'ordre du taux d'apprentissage pour une instance unique, combiné au nombre de copies, suffit à prédire le taux d'apprentissage de la classe produit dans le cadre non restreint et sans distribution (distribution-free).

Méthodologie et Configuration
Les auteurs utilisent le cadre standard de l'apprentissage PAC agnostique où l'objectif est de minimiser l'excès de risque par rapport au meilleur membre d'une classe de concepts $C$ .

Définition de la Somme Directe : Pour les classes $C_1 \subseteq Y^{X_1}$ et $C_2 \subseteq Y^{X_2}$ , la somme directe $C_1 \otimes C_2$ consiste en des fonctions $(c_1 \otimes c_2)(x_1, x_2) = (c_1(x_1), c_2(x_2))$ . La somme directe $r$ -uple est $C^r = \bigotimes_{i=1}^r C$ .
Fonction de Perte : La perte est définie comme la perte zéro-un sur le vecteur de sortie complet, et non par la perte de Hamming coordonnée.
Courbe d'Apprentissage : La courbe d'apprentissage agnostique est définie par $\varepsilon_{\text{agn}}(n \mid C) = \inf_A \sup_D (L_{D,n}(A) - L_D(C))$ , où l'infimum est pris sur les règles d'apprentissage et le supremum sur toutes les distributions.

Pour résoudre le problème, les auteurs construisent deux classes de concepts spécifiques, $F$ et $G$ , sur le domaine et l'espace d'étiquetage $X = Y = \{0, 1\}$ :

Classe $F$ : Contient les deux fonctions binaires constantes ( $f_0(x)=0, f_1(x)=1$ ).
Classe $G$ : Contient la fonction nulle et la fonction identité ( $g_0(x)=0, g_1(x)=x$ ).

Les auteurs démontrent que bien que les deux classes présentent le même taux d'apprentissage pour une instance unique, leurs sommes directes $r$ -uples présentent des taux d'apprentissage fondamentalement différents.

Contributions Clés et Résultats

Équivalence de l'Instance Unique :
L'article établit que les deux classes $F$ et $G$ ont une courbe d'apprentissage agnostique d'ordre $n^{-1/2}$ .

Pour $F$ , le résultat découle de l'analyse standard des fonctions constantes et de la minimisation du risque empirique.
Pour $G$ , le résultat est dérivé en prenant $r=1$ dans le théorème principal (Théorème 1), ce qui donne $\varepsilon_{\text{agn}}(n \mid G) \asymp n^{-1/2}$ .

Séparation de Taux dans les Sommes Directes (Le Théorème Principal) :
La contribution centrale est le Théorème 1, qui démontre une « séparation de taux » entre les sommes directes $F^r$ et $G^r$ :

Pour $F^r$ (Classe Constante) : Le taux d'apprentissage reste $\Theta(n^{-1/2})$ quel que soit $r$ . La preuve montre que l'excès de risque est régi par l'erreur d'estimation du vecteur constant le plus probable, qui évolue en $1/\sqrt{n}$ .
Pour $G^r$ (Classe Zéro/Identité) : Le taux d'apprentissage évolue en $\Theta(\min\{1, \sqrt{r/n}\})$ $Θ (min {1, r / n})$ .
- Lorsque $r \le n$ , le taux est $\Theta(\sqrt{r/n})$ .
- Lorsque $r > n$ , l'excès de risque minimax est borné par une constante positive (c'est-à-dire que l'apprentissage est impossible dans la limite).

Par conséquent, bien que $\varepsilon_{\text{agn}}(n \mid F) \asymp \varepsilon_{\text{agn}}(n \mid G)$ , les ordres asymptotiques de $\varepsilon_{\text{agn}}(n \mid F^r)$ et $\varepsilon_{\text{agn}}(n \mid G^r)$ divergent à mesure que $r$ croît.

Techniques de Preuve :

Bornes Supérieures : Dérivées des bornes standard de minimisation du risque empirique pour les classes finies. Pour $G^r$ , la borne utilise le fait que $|G^r| = 2^r$ , menant à un terme proportionnel à $\sqrt{\frac{r \log 2}{n}}$ .
Bornes Inférieures : Établies à l'aide d'outils d'information-théoriques.
- Pour $F^r$ , une méthode de Le Cam à deux points est utilisée pour montrer la difficulté de distinguer deux étiquettes constantes dominantes.
- Pour $G^r$ , les auteurs emploient le Lemme d'Assouad combiné à l'inégalité de Pinsker. Ils construisent une famille de distributions paramétrées par $\theta \in \{-1, +1\}^r$ . Dans cette construction, une coordonnée d'entrée $J$ est choisie uniformément parmi $\{1, \dots, r\}$ , fixant $X = e_J$ . Conditionnellement à $J=j$ , l'étiquette $Y$ est $e_j$ avec une probabilité de $1/2 + \theta_j \alpha$ et $0^r$ avec une probabilité de $1/2 - \theta_j \alpha$ . La preuve relie la distance de Hamming de l'estimation de $\theta$ à l'excès de risque, montrant que l'estimation du vecteur de paramètres $r$ -dimensionnel nécessite un échantillon proportionnel à $r$ .

Signification et Revendications
L'article fournit une réponse négative à la question de niveau de taux posée par [HMW24]. Il affirme que le taux d'apprentissage d'une instance unique et le nombre de facteurs $r$ ne sont pas suffisants pour déterminer l'ordre asymptotique de la courbe d'apprentissage pour la somme directe $C^r$ .

Les auteurs notent que bien que des travaux ultérieurs (par exemple, [Sur24], [HMS26]) aient étudié les sommes directes sous différents cadres de complexité ou hypothèses structurelles de distribution, et que des travaux récents sur l'apprentissage multiclasse fournissent des bornes combinatoires, aucun de ces résultats n'exprime la courbe de la somme directe comme une fonction de la courbe de l'instance unique seule. Ce papier résout explicitement cette lacune en présentant un contre-exemple où les propriétés structurelles de la classe (constante vs identité) mènent à des comportements divergents dans l'espace produit, malgré des performances identiques pour une instance unique.

La conclusion souligne que pour des classes de concepts arbitraires, la connaissance de $\varepsilon_{\text{agn}}(n \mid C)$ et de $r$ ne permet pas de prédire $\varepsilon_{\text{agn}}(n \mid C^r)$ . Spécifiquement, pour $G^r$ , le risque peut rester éloigné de zéro lorsque $r \ge n$ , alors que pour $F^r$ , il continue de décroître en $n^{-1/2}$ .

Articles similaires