Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization

Résumé Technique : Barrières de Degré de Somme de Carrés pour la Méthode du Hinge Reweighted dans l'Apprentissage de Demi-espaces Robuste

Énoncé du Problème
L'article traite du problème de l'apprentissage robuste d'un demi-espace (un classifieur linéaire) en présence de bruit malveillant. Dans le modèle de bruit malveillant de Kearns–Li, un adversaire observe l'échantillon d'entraînement propre et remplace un $\eta$-fraction de paires instance-étiquette par des points arbitraires de son choix. L'objectif est de produire une hypothèse $\hat{w}$ telle que l'erreur sur les points sains (inliers) soit au plus $\epsilon$.

Le focus spécifique porte sur la méthode du hinge reweighted (hinge repondéré), une lignée de travaux influente initiée par Talwar (2020) et affinée par Shen (2025) et Zeng et Shen (2025). Ces méthodes minimisent une perte hinge repondérée où des poids sont assignés par un programme de suppression d'outliers (typiquement une contrainte de variance ou de Somme de Carrés de degré 2) pour supprimer les points corrompus. Bien que ces méthodes atteignent une tolérance au bruit constante pour les marginales log-concaves, elles souffrent de deux limitations reconnues :

1. Tolérance au Bruit Infime : Le taux de bruit tolérable $\eta$ est extrêmement petit (par exemple, $2^{-32}$ dans Shen (2025)) et ne peut être rendu proche de l'optimal de rupture de $1/2$.
2. Dépendance Non Naturelle à la Marge : La marge $\gamma$ requise passe à l'échelle selon $\Omega(\log(1/\epsilon)/\sqrt{d})$, couplant l'exactitude cible $\epsilon$ à la géométrie des données d'une manière qui semble structurellement forcée plutôt que naturelle.

Méthodologie et Cadre Central
L'article recadre les limitations de l'approche du hinge reweighted à travers le prisme du degré SoS (Somme de Carrés) et de la fonction de Christoffel.

1. La Fonction de Christoffel comme une Barrière : Les auteurs établissent un « principe de résolution » (Proposition 3.3). Ils soutiennent qu'un certificat SoS de degré-$2t$, qui repose uniquement sur les $2t$ premiers moments de la marginale propre, ne peut détecter et supprimer une corruption de masse $\eta$ à un centre $c$ que si la fonction de Christoffel de la marginale propre, $\lambda_{t+1}(c)$, satisfait $\lambda_{t+1}(c) < \eta$.

   • Dans l'analyse de données moderne, une valeur de Christoffel élevée marque généralement un point « typique » à conserver.
   • Dans ce contexte adversarial, une valeur de Christoffel élevée représente la masse de corruption maximale qu'un adversaire peut cacher à cet emplacement à partir d'un certificat de degré-$2t$.
   • Ainsi, la fonction de Christoffel agit comme un « plafond de certificat » : si la masse de corruption est inférieure à ce plafond, le certificat ne peut pas distinguer la corruption des données propres.

2. Le Problème des Moments et la Quadrature de Gauss : L'article utilise la dualité entre le problème des moments tronqués et la quadrature de Gauss. Un certificat de degré-$2t$ ne peut certifier une borne inférieure sur la masse d'une « bande » (un slab autour d'une projection) que si la bande contient au moins un nœud de la règle de quadrature de $(t+1)$ points associée aux $2t$ premiers moments. Si la bande se situe au-delà de la plus grande racine du polynôme orthogonal correspondant, le certificat voit une masse nulle, rendant la corruption invisible.

3. Compromis Dépendants du Degré : L'analyse montre que la « ressource » régissant la méthode est le degré SoS $t$. Augmenter le degré permet au certificat de « voir » plus loin dans les queues de distribution (plus grandes racines des polynômes orthogonaux) et de résoudre des écarts de moments d'ordre supérieur.

Contributions Clés et Résultats

1. Le Compromis Marge–Degré (Théorème 4.1)
L'article prouve que la dépendance logarithmique de $1/\epsilon$ dans la marge est une nécessité structurelle du certificat, et non un artefact d'une analyse lâche.

• Pour certifier l'existence d'une « crêpe » (pancake) dense (bande) à une distance $|c|$ de l'origine, un certificat de degré-$2t$ nécessite $2t = \Omega((|c|/s)^2)$ pour les marginales sous-gaussiennes et $2t = \Omega(|c|/s)$ pour les marginales sous-exponentielles (où $s$ est l'écart-type).
• Puisqu'une erreur $\epsilon$ nécessite de certifier des bandes jusqu'au quantile $\epsilon$ (où $|c| \approx s \log(1/\epsilon)$ pour des queues sous-exponentielles), un apprenant doit soit payer un coût de degré de $t = \Omega(\log(1/\epsilon))$ (résultant en un temps d'exécution de $n^{\Omega(\log(1/\epsilon))}$), soit accepter une marge de $\gamma = \Omega(\sqrt{\log(1/\epsilon)}/\sqrt{d})$.
• Cela explique pourquoi la marge de Shen est « forcée » dans le modèle de certificat en un seul coup (one-shot).

2. La Barrière du Degré-2 pour les Outliers (Théorème 4.7)
Les auteurs construisent une instance spécifique démontrant que le reweighting de degré 2 est fondamentalement bloqué à un taux de bruit de $\eta^{1/2}$.

• Construction : Un « pic masqué par les moments » (moment-cloaked spike) consistant en deux clusters log-concaves authentiques à $\pm (\sigma/\sqrt{\eta})e_1$, auxquels l'adversaire ajoute $\eta n$ points sales tirés des mêmes clusters.
• Mécanisme : Les points sales sont conçus pour consommer exactement le budget de variance de la distribution propre. Par conséquent, le second moment (variance) reste inchangé, rendant la corruption invisible pour tout programme de degré 2 indépendant du label.
• Résultat : Tout reweighting de degré 2 laisse une contribution de gradient sale de $\Omega(\eta^{1/2})$. En revanche, un programme de degré 4 détecte l'inflation du quatrième moment et atteint un taux de $\eta^{3/4}$. Cela confirme que la petite constante de Shen (2025) est une conséquence directe de l'utilisation du degré 2.

3. L'Algorithme de Degré-$2t$ (Théorème 4.9)
L'article présente un algorithme correspondant qui trace la frontière définie par les barrières.

• Algorithme : Une méthode de hinge reweighted de degré-$2t$ où le programme de suppression d'outliers certifie une borne sur le $2t$-ième moment (hypercontractilité certifiable) plutôt que simplement la variance.
• Performance : L'algorithme tolère un taux de bruit $\eta \le \eta_0(t) = \Omega(\min(\rho/4, (\gamma\rho/((Ct)\bar{\sigma}))^{\frac{2t}{2t-1}}))$.
• Signification : À mesure que $t$ augmente, l'exposant $1 - 1/2t$ approche 1, supprimant le goulot d'étranglement de $\eta^{1/2}$ du degré 2. Cependant, le taux est limité par la densité de la crêpe $\rho/4$ et n'approche pas la limite informationnelle de $1/2$. Le gain est explicite et constant, et non asymptotique à $1/2$.

4. Le Seuil de Rupture (Proposition 4.11)
En utilisant un argument à deux points (méthode de Le Cam), l'article établit une borne inférieure informationnelle : aucun algorithme ne peut atteindre une erreur d'inlier inférieure à $\eta/2$ sous un bruit malveillant avec une marge $\gamma$ log-concave mixte. Cela confirme que la dépendance $\Theta(\eta)$ de l'algorithme proposé est un taux serré, même si la constante de rupture exacte reste ouverte.

Signification et Revendications
L'article affirme fournir la première explication rigoureuse des limitations de la lignée de travail du hinge reweighted, identifiant le degré SoS comme la ressource directrice.

• Unification : Il unifie la limitation de la marge et la limitation de la tolérance au bruit sous un cadre unique : la fonction de Christoffel de la marginale propre.
• Inversion de Perspective : Il inverse l'utilisation standard de la fonction de Christoffel. Alors qu'elle est typiquement utilisée pour détecter des points typiques (grand $\lambda$), elle sert ici de barrière, où un grand $\lambda$ indique un emplacement où un adversaire peut cacher la corruption.
• Bornes Inférieures Spécifiques à la Méthode : Les auteurs précisent explicitement que leurs bornes inférieures s'appliquent à la méthode de certificat de moment/SoS (certificats en un seul coup basés sur des moments de bas degré). Ils ne prétendent pas que ces bornes sont des bornes inférieures informationnelles inconditionnelles pour tous les algorithmes efficaces, ni qu'ils excluent des schémas de localisation itératifs qui pourraient échapper au modèle de certificat en un seul coup.
• Gains Modestes : L'article est modeste quant aux améliorations algorithmiques. L'algorithme de degré-$2t$ améliore l'exposant de la tolérance au bruit mais reste plafonné par la densité de la crêpe et n'atteint pas le point de rupture de $1/2$. La contribution principale est la caractérisation de la frontière de compromis plutôt qu'une percée dans l'obtention d'une tolérance au bruit optimale.

En résumé, l'article démontre que pour l'approche du hinge reweighted, le « coût » de la robustesse est le degré SoS, et le « prix » payé en marge ou en tolérance au bruit est dicté par le pouvoir de résolution de la fonction de Christoffel à ce degré.