Résumé Technique : Reconsidérer l'Approximation de la Hessienne par Ordre Zéro : Une Perspective d'Optimisation de Politique à Étape Unique

1. Énoncé du Problème

L'optimisation d'ordre zéro (ZO) traite des scénarios où la fonction objectif $F(\theta) = \mathbb{E}_\xi[f(\theta; \xi)]$ est une boîte noire accessible uniquement via des évaluations de fonctions bruitées. Bien que l'estimation du gradient par ordre ZO soit bien établie, l'approximation de la Hessienne par ordre ZO précise reste un défi majeur, particulièrement dans les régimes de haute dimension et de bruit élevé.

Une information de courbure précise est critique pour :

• L'optimisation bi-niveau sans dérivée.
• La quantification de l'incertitude.
• L'ajustement fin (fine-tuning) sensible à la courbure des grands modèles de langage (LLM).

Les méthodes existantes font face à deux limitations principales :

1. Variance Élevée : Les estimateurs aléatoires classiques (par exemple, les estimateurs de type Stein) souffrent souvent d'une variance élevée dans les contextes de grande dimension, ce qui entraîne une optimisation instable.
2. Portée Limitée : Les recherches antérieures se sont concentrées principalement sur l'estimation de la matrice Hessienne $\nabla^2 F(\theta)$ elle-même. Peu d'attention a été portée à l'inverse de la Hessienne régularisée $(\nabla^2 F(\theta) + \lambda I_d)^{-1}$ et au produit Hessienne-gradient inverse $(\nabla^2 F(\theta) + \lambda I_d)^{-1}\nabla F(\theta)$, qui sont essentiels pour les mises à jour de second ordre en ZO.
3. Efficacité des Requêtes : Les méthodes naïves de différence finie nécessitent $O(d^2)$ requêtes, tandis que les méthodes aléatoires existantes échouent souvent à équilibrer la réduction de la variance avec la réutilisation des requêtes de manière efficace.

2. Méthodologie

2.1. Cadre Théorique : Perspective d'Optimisation de Politique (PO)

Les auteurs proposent un cadre unifié qui réinterprète l'approximation de la Hessienne ZO à travers le prisme de l'Optimisation de Politique (PO) à étape unique.

• Objectif lissé : L'objectif ZO est reformulé comme un objectif lissé $F_\mu(\theta) = \mathbb{E}_{x \sim \pi_\theta(x)}[\mathbb{E}_\xi[f(x; \xi)]]$, où $\pi_\theta$ est une politique d'échantillonnage paramétrée (par exemple, une Gaussienne $N(\theta, \mu^2 I_d)$).
• Identité de la Hessienne : En différenciant le gradient de la politique, les auteurs dérivent une identité de Hessienne générale pour l'objectif lissé :
  $$\nabla^2 F_\mu(\theta) = \mathbb{E}_{x \sim \pi_\theta(x)} \left[ H_{\pi_\theta} \cdot \mathbb{E}_\xi[f(x; \xi)] \right]$$
  où $H_{\pi_\theta}$ est la Hessienne de la densité de log de la politique.
• Unification des Estimateurs : Cette perspective révèle que les estimateurs classiques de type Stein (un point, deux points, trois points) et les estimateurs de différence centrale sont des cas particuliers de ce cadre, distingués uniquement par leur choix de base (par exemple, base nulle, base ancre $f(\theta)$, ou échantillonnage antithétique).

2.2. ZoVH : Estimateur de Hessienne à Variance Réduite

S'appuyant sur le cadre PO, les auteurs introduisent ZoVH (Zeroth-Order Variance-reduced Hessian), qui emploie deux techniques clés :

1. Base Moyennée Optimale :

   • Contrairement aux estimateurs de gradient où les bases sont souvent heuristiques, les auteurs prouvent que pour l'estimateur de Hessienne dérivé de l'identité de rang un, la base moyennée $\hat{b} = \frac{1}{K}\sum f(x_k)$ est le choix unique qui préserve l'absence de biais.
   • Théoriquement, il est prouvé que cette base minimise la variance de l'estimateur parmi toutes les bases constantes.

2. Stratégie de Réutilisation des Requêtes :

   • Pour réduire davantage la variance sans augmenter les coûts de requête, ZoVH utilise un tampon d'historique des requêtes de fonctions passées.
   • Cela est interprété comme un apprentissage hors-politique (off-policy) dans le cadre PO, où les données historiques (générées à partir d'itérations précédentes) sont repondérées via l'échantillonnage d'importance pour estimer la Hessienne actuelle.
   • Cela augmente efficacement la taille de l'échantillon de $K$ à $NK$(où$N$ est la longueur de l'historique) sans appels de fonction supplémentaires.

2.3. Approximations Inverses Efficaces

Pour permettre des mises à jour pratiques de second ordre, l'article étend ZoVH pour approximer l'inverse de la Hessienne et le produit inverse Hessienne-gradient :

• Inverse de la Hessienne : Utilise l'identité de Woodbury pour calculer efficacement l'inverse de l'estimateur de Hessienne de rang $K$ régularisé ($O(K^2 d)$ ou $O(Kd)$ avec une approximation diagonale) sans inverser une matrice dense $d \times d$.
• Produit Corrigé de Biais : Lorsque les mêmes directions aléatoires sont utilisées pour l'estimation du gradient et de la Hessienne (pour économiser des requêtes), un biais de corrélation est introduit. Les auteurs proposent une stratégie de "leave-one-out" (exclusion d'un élément) pour corriger ce biais, permettant de calculer efficacement $(\nabla^2 F + \lambda I)^{-1}\nabla F$ avec un surcoût minimal.

3. Contributions Clés

1. Perspective PO Unifiée : A établi une équivalence théorique entre les estimateurs de Hessienne ZO généraux et la Hessienne d'un objectif de PO lissé, unifiant les estimateurs aléatoires classiques comme des instances spécifiques de sélection de base.
2. Algorithme ZoVH : A développé une suite complète d'estimateurs à variance réduite pour la Hessienne complète, son inverse régularisé, et le produit inverse Hessienne-gradient corrigé de biais.
3. Garanties Théoriques :
   • Prouvé l'absence de biais de l'estimateur de Hessienne avec la base moyennée.
   • Démontré l'optimalité de la variance de la base moyennée.
   • Fourni des bornes d'erreur pour toute la suite ZoVH (décomposition biais-variance).
   • Établi des garanties de convergence pour l'algorithme ZO sensible à la courbure résultant vers un point stationnaire $\epsilon$.
4. Efficacité Pratique : A introduit un mécanisme de réutilisation de requêtes qui améliore l'efficacité de l'échantillonnage sans gonfler le budget de requête, et a dérivé des approximations inverses stables adaptées aux problèmes de haute dimension comme le fine-tuning de LLM.

4. Résultats Expérimentaux

Les auteurs ont validé ZoVH à travers des benchmarks synthétiques, l'entraînement de réseaux de neurones et des attaques adverses en boîte noire.

• Précision de l'Estimation de la Hessienne :

  • Sur des fonctions synthétiques (Quadratique, Rosenbrock, Styblinski-Tang) et des couches CNN, ZoVH (avec réutilisation de requête, $N=4$) a systématiquement obtenu l'erreur de norme de Frobenius la plus faible par rapport aux estimateurs classiques de Stein et de différence centrale.
  • ZoVH ($N=1$) montre une amélioration de précision de 8x par rapport à l'estimateur de différence centrale sur les fonctions Quadratique et Rosenbrock.
  • Sur les couches CNN, ZoVH ($N=4$) a obtenu une réduction d'erreur de 9x par rapport à l'estimateur de différence centrale.

• Convergence de l'Optimisation :

  • Dans les tâches d'optimisation synthétiques, ZoVH ($N=4$) surpasse de manière significative Vanilla ZOO, HiZOO et ZoAR tant en vitesse de convergence qu'en précision finale, atteignant une accélération moyenne de 22x par rapport à Vanilla ZOO.
  • Dans les attaques adverses en boîte noire, ZoVH ($N=4$) nécessite 4x moins d'itérations pour réussir une attaque par rapport à Vanilla ZOO.

• Fine-Tuning de LLM :

  • Appliqué au fine-tuning des modèles OPT-1.3B et OPT-13B sur les tâches GLUE/SuperGLUE.
  • ZoVH a démontré une convergence plus rapide et une précision de test plus élevée par rapport à MeZO et HiZOO.
  • Le surcoût de temps d'exécution et de mémoire était minimal, ZoVH étant seulement légèrement plus lent que MeZO et utilisant une mémoire supplémentaire négligeable (stockage de seules valeurs scalaires et de graines/seeds).

5. Signification et Revendications

L'article affirme que ZoVH fournit une base robuste pour l'optimisation sans dérivée sensible à la courbure. En comblant le fossé entre l'approximation ZO et l'optimisation de politique, ce travail offre :

• Clartart Théorique : Une dérivation rigoureuse qui explique pourquoi certains estimateurs fonctionnent et comment les optimiser via la sélection de base.
• Utilité Pratique : Une méthode qui atteint une précision d'estimation et une performance de convergence supérieures dans des applications réelles (y compris les LLM) sans les coûts de requête prohibitifs des schémas de différence finie complets.
• Scalabilité : La capacité de gérer des problèmes de haute dimension (ex: des millions de paramètres dans les LLM) grâce à des approximations inverses efficaces et la réutilisation de requêtes, rendant l'optimisation de second ordre réalisable dans des contextes de boîte noire là où elle était auparavant impraticable.

Les auteurs soulignent que bien que la méthode introduise un biais de lissage (inhérent aux méthodes ZO), les gains de réduction de la variance et d'efficacité des requêtes l'emportent largement sur ce compromis, menant à une convergence plus rapide et plus stable dans des environnements bruités et de haute dimension.