Résumé technique : Dynamiques d'apprentissage de l'optimisation d'ordre zéro : Une perspective par noyau

Énoncé du problème

La théorie classique de l'optimisation postule que les algorithmes d'ordre zéro (ZO) souffrent d'une « malédiction de la dimensionnalité », où les taux de convergence évoluent linéairement avec la dimension du modèle $d$. Cette limitation théorique suggère que les méthodes ZO devraient être prohibitivement lentes pour les modèles de grande dimension, tels que les grands modèles de langage (LLM) comportant des milliards de paramètres. Cependant, des percées empiriques récentes contredisent cette vision pessimiste, démontrant que les méthodes ZO peuvent affiner avec succès des LLM avec des performances compétitives par rapport aux méthodes d'ordre un (FO). Le problème central abordé par cet article est de résoudre ce paradoxe : pourquoi les méthodes ZO s'adaptent-elles efficacement à des espaces de paramètres massifs malgré des bornes théoriques suggérant le contraire ?

Méthodologie

Les auteurs proposent un cadre novateur qui analyse l'optimisation ZO à travers le prisme des dynamiques d'apprentissage et du noyau empirique tangentiel neuronal (eNTK), plutôt que de se concentrer uniquement sur la convergence dans l'espace des paramètres ou sur les valeurs de perte scalaires.

1. Dérivation des dynamiques d'apprentissage ZO : L'article dérive les dynamiques d'apprentissage en une étape de la descente de gradient stochastique (SGD) d'ordre zéro. En appliquant un développement de Taylor au logarithme de la probabilité des prédictions du modèle, les auteurs montrent que la règle de mise à jour est régie par un eNTK projeté.
2. Formulation de la projection de noyau : L'insight théorique central est que le noyau effectif induit par l'optimisation ZO (dénommé ZO-eNTK) est une projection géométrique de l'eNTK FO standard sur un sous-espace de faible dimension aléatoire engendré par les vecteurs de perturbation.
3. Application du lemme de Johnson-Lindenstrauss (JL) : Les auteurs invoquent le lemme de Johnson-Lindenstrauss pour analyser la fidélité de cette projection. Ils établissent que l'erreur d'approximation entre le ZO-eNTK et le véritable FO-eNTK dépend de la préservation des produits scalaires dans les espaces de haute dimension.
4. Bornes théoriques : L'analyse dérive des bornes rigoureuses montrant que l'erreur d'approximation $\epsilon$ évolue comme $O(\sqrt{\ln V / P})$, où $V$ est la taille du vocabulaire de sortie et $P$ est le nombre de perturbations. Crucialement, cette borne est indépendante de la dimension massive des paramètres du modèle $d$.
5. Validation empirique : Le cadre est validé par des expériences sur :
   • LeNet (MNIST) : Visualisation de la convergence du ZO-eNTK vers le FO-eNTK à mesure que $P$ augmente, à l'aide de cartes thermiques et d'erreurs de norme de Frobenius.
   • Modèles OPT (SST-2) : Test de modèles allant de 125M à 1,3 milliard de paramètres pour vérifier l'indépendance à la dimension.
   • Comparaison de distributions : Comparaison des distributions de perturbation gaussienne et de Rademacher.

Contributions clés

1. Résolution théorique du paradoxe ZO

L'article fournit une justification théorique de l'évolutivité des méthodes ZO vers les LLM. En déplaçant l'analyse de l'espace des paramètres vers l'espace des fonctions (via l'eNTK), les auteurs démontrent que la fidélité des mises à jour ZO est régie par la taille du vocabulaire de sortie $V$ et le nombre de perturbations $P$, plutôt que par la dimension du modèle $d$. Cette propriété « sans dimension » explique pourquoi les méthodes ZO restent efficaces même lorsque $d$ est de l'ordre des milliards.

2. Le rôle du nombre de perturbations ($P$)

L'analyse identifie le nombre de perturbations comme le facteur principal gouvernant la fidélité du ZO-eNTK. Les bornes théoriques et les résultats empiriques montrent que l'augmentation de $P$ réduit l'erreur d'approximation du noyau à un taux de $O(1/\sqrt{P})$. Une fois que $P$ dépasse un seuil déterminé par $V$, la trajectoire d'apprentissage ZO s'aligne étroitement sur la trajectoire FO.

3. Robustesse de la distribution

L'article examine l'impact des distributions de perturbation (Gaussienne vs Rademacher). Alors que les vues classiques de l'optimisation suggèrent souvent des différences dans la réduction de variance, l'analyse basée sur les noyaux révèle que les deux distributions produisent des constantes de concentration comparables dans le contexte du lemme JL. Les résultats empiriques confirment que le choix de la distribution a un impact négligeable sur la convergence à long terme, à condition que $P$ soit suffisant.

4. Sensibilité à la similarité des entrées

L'étude met en évidence que le taux de convergence de l'approximation ZO-eNTK est sensible à la similarité sémantique entre les paires d'entrées. Les paires présentant une forte similarité (par exemple, des chiffres ou du texte sémantiquement similaires) convergent vers la vérité terrain FO plus rapidement que les paires structurellement distinctes, bien que les deux convergent éventuellement à mesure que $P$ augmente.

Résultats

• Convergence de l'eNTK : Les expériences sur LeNet montrent qu'à mesure que $P$ augmente de 1 à 125, le ZO-eNTK récupère visuellement et numériquement la structure bloc-diagonale du FO-eNTK. L'erreur de norme de Frobenius relative diminue de manière monotone.
• Indépendance à la dimension : Dans les expériences avec des modèles OPT (125M, 350M, 1,3B), le seuil de $P$ nécessaire pour récupérer les dynamiques FO est resté virtuellement constant malgré l'augmentation de la dimension du modèle $d$ d'un ordre de grandeur. Cela confirme que les dynamiques d'apprentissage sont découplées de $d$.
• Échelle de la taille de sortie : Une expérience synthétique contrôlée faisant varier la taille de sortie $V$ (de 2 à 1000) tout en maintenant $P$ fixe a montré que l'erreur d'approximation augmente à un taux cohérent avec $\sqrt{V}$, validant la borne théorique.
• Parité des distributions : Les courbes de convergence pour les distributions gaussienne et de Rademacher étaient presque indiscernables sur toutes les métriques (Norme de Frobenius, CKA et Distance Spectrale), soutenant l'affirmation selon laquelle de simples perturbations binaires suffisent pour une approximation de noyau efficace.

Signification et revendications

L'article revendique offrir une nouvelle perspective pour comprendre les dynamiques d'apprentissage sans dérivées en complétant la vision centrée sur l'optimisation existante par un cadre basé sur les noyaux.

• Justification théorique : La signification principale réside dans la fourniture d'une explication théorique rigoureuse du succès empirique de l'affinage ZO dans les LLM, résolvant la divergence entre les bornes théoriques du pire cas (dépendantes de $d$) et les performances pratiques.
• Conseils pratiques : Les résultats suggèrent que les praticiens devraient se concentrer sur le réglage du nombre de perturbations $P$ par rapport à la taille du vocabulaire de sortie $V$, plutôt que de s'inquiéter du nombre massif de paramètres $d$.
• Limites et portée : Les auteurs notent modestement que leur analyse repose sur le régime d'« entraînement paresseux » (où les caractéristiques restent stables), ce qui est typique de l'affinage mais peut ne pas s'appliquer aux scénarios d'entraînement à partir de zéro. Ils reconnaissent également que le cadre aborde actuellement l'affinage supervisé standard et peut nécessiter une extension pour les tâches présentant de fortes dépendances séquentielles (par exemple, le raisonnement à long horizon) où la dimension de sortie effective croît avec la longueur de la séquence.

En résumé, l'article soutient que le succès de l'optimisation ZO dans des contextes de haute dimension n'est pas un hasard, mais une conséquence des propriétés géométriques du noyau tangentiel neuronal, qui permet une approximation sans dimension via des projections aléatoires.