Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuning

Résumé Technique : Optimisation sans paramètres d'ordre zéro pour les méthodes basées sur l'LMO

Énoncé du Problème
L'ajustement fin (fine-tuning) des grands modèles de langage (LLM) est une application centrale de l'optimisation moderne, mais il fait face à un goulot d'étranglement critique : la surcharge de mémoire de la rétropropagation. Le stockage des activations intermédiaires, des gradients et des états de l'optimiseur pour des modèles comme OPT-1.3B nécessite une mémoire substantielle (par exemple, ~25 Go), ce qui limite la scalabilité. L'optimisation d'ordre zéro (ZO) offre une alternative économique en mémoire en remplaçant les calculs de gradient par des estimations de différences finies dérivées de requêtes de valeurs de fonction. Cependant, les méthodes ZO existantes souffrent de deux limitations principales :

1. Sensibilité aux Hyperparamètres : La performance dépend fortement du pas de l'apprentissage (stepsize) et du paramètre de lissage ($\tau$). Les réglages optimaux nécessitent généralement la connaissance de constantes dépendantes du problème (par exemple, les constantes de Lipschitz, la distance à l'optimum) qui sont indisponibles en pratique, nécessant ainsi des recherches par grille coûteuses et spécifiques à chaque tâche.
2. Inadéquation Géométrique : Les mises à jour euclidiennes standard peuvent ne pas capturer la structure hétérogène des blocs de paramètres (par exemple, les poids de forme matricielle dans les LLM). Les méthodes utilisant des Oracles de Minimisation Linéaire (LMO) peuvent s'adapter à des géométries non euclidiennes (telles que les normes spectrales pour les matrices), mais la combinaison de ces méthodes avec une adaptation sans paramètres (PF) dans un contexte ZO reste inexplorée.

Méthodologie
Les auteurs proposent AdaNAGED (ADAptive Norm-Agnostic Gradient-frEe Descent), un nouvel algorithme qui unifie trois paradigmes : l'optimisation d'ordre zéro économique en mémoire, l'adaptation sans paramètres et les mises à jour sensibles à la géométrie via les LMO.

• Estimation Sans Paramètres (Parameter-Free) :

  • Lissage ($L$) : Au lieu d'exiger une constante de Lipschitz préalable, la méthode estime la lissure locale de manière itérative le long de la trajectoire d'optimisation. Elle calcule le ratio de la différence entre les approximations de gradient ZO et la distance entre les itérations consécutives : $L_t = \|g_t(x_{t+1}, e_t)_* / \|x_{t+1} - x_t\|$. Crucialement, la même direction de perturbation $e_t$ (stockée sous forme de graine aléatoire) est utilisée aux deux points pour maintenir l'efficacité de la mémoire.
  • Écart Initial ($\Delta$) : La méthode utilise une borne inférieure connue de la fonction objectif ($f_{min}$) pour estimer l'écart initial $\Delta \leq f(x_0) - f_{min}$, évitant ainsi de devoir connaître la distance à l'optimum.
  • Pas d'Apprentissage Adaptatif : Le pas d'apprentissage $\gamma_t$ est mis à jour en utilisant une accumulation de type AdaGrad-Norm des estimations de lissage local ($S_t = S_{t-1} + L_t$), produisant $\gamma_t \propto 1/\sqrt{S_t}$.
  • Paramètre de Lissage ($\tau$) : Pour assurer la stabilité, $\tau_t$ est mis à l'échelle linéairement avec le pas d'apprentissage ($\tau_t = \rho C_2 \gamma_t$), dérivé des exigences théoriques de la preuve de convergence.

• Mises à Jour Basées sur l'LMO :
  L'algorithme définit les mises à jour via un Oracle de Minimisation Linéaire sur une boule de norme : $v_t = \text{lmo}(g_t)$. Cela permet à la méthode de s'adapter à différentes géométries :

  • Géométrie Vectorielle : L'utilisation de la norme $\ell_\infty$ produit une mise à jour de type Sign-SGD.
  • Géométrie Matricielle : L'utilisation de la norme spectrale produit une mise à jour de type Muon. Comme la décomposition polaire exacte (SVD) est coûteuse en termes de calcul, les auteurs introduisent AdaMuGED, qui approxime l'opérateur polaire à l'aide de quelques étapes de l'itération de Newton–Schulz (N-SS), évitant ainsi l'inversion de matrice.

Principales Contributions

1. Nouvelle Construction ZO Sans Paramètres : Le papier introduit une méthode pour estimer la lissure locale et fixer les pas d'apprentissage dans le cadre ZO sans connaissance préalable des constantes du problème. Cela préserve l'efficacité de la mémoire de la ZO en ne stockant que les graines génératrices pour les directions de perturbation.
2. Unification des Paradigmes : L'algorithme proposé AdaNAGED combine la ZO économique en mémoire, la réduction de la dépendance aux hyperparamètres et les mises à jour géométriquement conscientes via les LMO.
3. Garanties de Convergence : Les auteurs établissent des taux de convergence pour des objectifs lipschitiens, lisses et convexes. Le taux résultant est asymptotiquement optimal ($O(1/\epsilon^2)$), avec des facteurs supplémentaires tenant compte de l'estimation sans paramètres et de la stochasticité.
4. Variantes Pratiques : L'introduction d'AdaMuGED étend le cadre aux paramètres de type matrice en utilisant les itérations de Newton–Schulz, le rendant applicable au fine-tuning de LLM où les paramètres sont structurés comme des matrices.

Résultats Expérimentaux
Les méthodes ont été évaluées sur le fine-tuning du modèle OPT-1.3B sur la tâche de classification de sentiment SST-2, un benchmark pour l'adaptation de LLM sous contrainte de mémoire.

• Baselines : Les auteurs ont comparé les méthodes contre des optimiseurs ZO ajustés (tuned) : ZO-AdaMM, ZO-SignSGD et ZO-Muon.
• Performance :
  • AdaNAGED (de type SignSGD) a atteint une précision de 0,903, soit à 0,7 point de pourcentage de la version ajustée de ZO-SignSGD (0,910).
  • AdaMuGED (de type Muon) a atteint une précision de 0,908, réduisant l'écart avec la version ajustée de ZO-SignSGD à 0,2 point de pourcentage et surpassant AdaNAGED de 0,5 point de pourcentage.
  • Le ZO-Muon ajusté est resté la baseline la plus forte avec 0,921, confirmant le bénéfice de la géométrie sensible aux matrices.
• Conclusion : Les méthodes sans paramètres ont démontré des performances compétitives par rapport aux baselines ajustées manuellement, validant que les règles adaptatives peuvent récupérer une grande partie de la performance des méthodes ZO ajustées sans recherche intensive d'hyperparamètres.

Signification
Le papier affirme présenter la première méthode opérant à l'intersection de l'optimisation d'Ordre Zéro, Sans Paramètres et de l'Oracle de Minimisation Linéaire. Sa signification réside dans la démonstration que :

1. Efficacité Mémoire : L'optimisation ZO peut être rendue pratique pour les LLM en évitant la rétropropagation.
2. Automatisation : La dépendance aux hyperparamètres coûteux et spécifiques aux tâches peut être éliminée grâce à l'estimation adaptative et sans paramètres de la lissure et des pas d'apprentissage.
3. Flexibilité Géométrique : Le cadre supporte des mises à jour non euclidiennes (via les LMO) qui s'alignent sur les propriétés structurelles des paramètres du modèle (par exemple, les matrices), améliorant le conditionnement et la stabilité.

Les auteurs maintiennent une position modeste, notant que bien que leur approche sans paramètres soit compétitive, les baselines ajustées (particulièrement ZO-Muon) conservent un léger avantage, suggérant que l'ajustement manuel reste optimal mais que la méthode proposée offre une alternative robuste et automatisée.