Generalization of Zeroth-Order Method for Quotients of Quadratic Functions

1. Énoncé du problème

L'article traite de l'optimisation de la norme d'opérateur généralisée et du quotient de Rayleigh généralisé extrémal sous des contraintes d'ordre zéro (sans dérivées). Plus précisément, l'objectif est de résoudre :
$$\left\| \frac{A}{B} \right\| := \max_{v \in \mathbb{R}^d \setminus \{0\}} \frac{\|Av\|}{\|Bv\|}$$
où $A \in \mathbb{R}^{m \times d}$ et $B \in \mathbb{R}^{\ell \times d}$ sont des matrices accessibles uniquement via des évaluations directes (accès boîte noire).

Contraintes et défis clés :

• Sans adjoint / Sans matrice : Les adjointes $A^T$ et $B^T$ sont indisponibles ou incohérentes avec les opérateurs directs (fréquent dans les codes hérités, les solveurs d'EDP et la tomographie).
• Bien-posé : $B$ doit être de plein rang colonne ($\text{rank}(B)=d$) afin que $B^TB \succ 0$.
• Limites des méthodes existantes : Les méthodes récentes de l'état de l'art en ordre zéro (par exemple, Bresch et al. [7–9]) reposent sur un échantillonnage dans l'espace tangent d'une sphère généralisée ($S^{d-1}_{B^TB}$). Cela nécessite la connaissance de la métrique $B^TB$ ou de sa racine carrée pour projeter les directions de recherche, ce qui est irréalisable dans des contextes stricts de boîte noire.

2. Méthodologie

L'article propose une approche fondamentalement différente basée sur un échantillonnage non contraint sur toute la sphère unité plutôt que sur des espaces tangents restreints.

A. Stratégie d'échantillonnage non contraint

Au lieu d'échantillonner les directions de recherche $x_k$ depuis l'espace tangent de la sphère généralisée (ce qui nécessite $B^TB$), la méthode échantillonne $x_k$ uniformément depuis la sphère unité standard $S^{d-1}$ :
$$x_k = \frac{x}{\|x\|}, \quad x \sim \mathcal{N}(0, I_d)$$
Cela élimine le besoin de projections dépendantes de la métrique ou d'informations sur les adjointes.

B. Taille de pas optimale via solution en forme close

Pour un itéré courant $v_k$ et une direction de recherche $x_k$, l'algorithme cherche une taille de pas optimale $\tau_k$ pour maximiser l'objectif le long du chemin de rétraction. La fonction objectif le long du chemin devient un quotient de fonctions quadratiques :
$$s_k(\tau) = \frac{\|A(v_k + \tau x_k)\|^2}{\|B(v_k + \tau x_k)\|^2} = \frac{a_k + 2b_k\tau + c_k\tau^2}{d_k + 2e_k\tau + f_k\tau^2}$$
Les coefficients ($a_k, \dots, f_k$) sont calculés en utilisant uniquement des évaluations directes de $A$ et $B$.

• Avancée théorique : L'article démontre que trouver le $\tau_k$ optimal équivaut à résoudre un problème de valeurs propres généralisé en 2D impliquant des matrices de Gram $2 \times 2$, $M_k$ et $N_k$.
• Résultat : Une solution en forme close pour $\tau_k$ est dérivée (Théorème 3.1), garantissant que la taille de pas est optimale pour la direction aléatoire spécifique, sans heuristiques de recherche linéaire.

C. Cadre d'optimisation Riemannienne d'ordre zéro

La méthode construit des estimateurs pour les quantités d'optimisation Riemannienne en utilisant uniquement des évaluations de fonction :

1. Estimateur de gradient : Un estimateur sans biais du gradient Riemannien est construit en utilisant la direction aléatoire $x_k$ et la logique de taille de pas optimale.
2. Estimateur de Hessienne (Quasi-Newton) : L'article dérive un estimateur sans biais pour la Hessienne Riemannienne (Corollaire 3.3) en utilisant les moments d'ordre quatre de la distribution uniforme sur la sphère. Cela permet de construire une méthode Quasi-Newton d'ordre zéro (Algorithme 3).
3. Réduction de variance : En moyennant $m$ échantillons indépendants (Algorithme 2), la variance de l'estimateur de gradient est réduite, accélérant la convergence.

3. Contributions clés

1. Échantillonnage non contraint sur $S^{d-1}$ :
   L'article introduit un schéma d'échantillonnage opérant sur la sphère unité complète plutôt que sur l'espace tangent d'une sphère généralisée. Cela élimine l'exigence de $B^TB$ ou de son adjoint, rendant la méthode applicable à des scénarios stricts de boîte noire où les méthodes précédentes échouaient.

2. Taille de pas optimale en forme close :
   Contrairement aux méthodes d'ordre zéro standards qui utilisent des tailles de pas fixes ou heuristiques, ce travail dérive une solution exacte et en forme close pour la taille de pas optimale $\tau_k$ pour l'objectif spécifique de quotient quadratique. Cela transforme le sous-problème en un problème de valeurs propres généralisé en 2D résoluble.

3. Estimation de Hessienne sans biais :
   Les auteurs fournissent une dérivation fondée sur des principes d'un estimateur sans biais pour la Hessienne Riemannienne dans un cadre sans dérivées. Cela permet la construction d'un algorithme d'ordre zéro du second ordre (Quasi-Newton) qui capture les informations de courbure sans dérivées explicites.

4. Garanties de convergence théorique :

   • Convergence presque sûre : La suite des itérés converge presque sûrement vers le sous-espace propre généralisé dominant (Théorème 3.7).
   • Analyse des points critiques : L'article démontre que la suite des proxies de gradient ($\alpha_k$) converge vers zéro presque sûrement, garantissant que l'algorithme ne reste pas coincé à des points critiques non optimaux (sous des hypothèses spectrales légères).
   • Bien-définition : Il est prouvé que le dénominateur dans le calcul de la taille de pas reste non nul presque sûrement, assurant que l'algorithme est bien défini.

4. Résultats numériques

Des expériences ont été menées sur des matrices gaussiennes aléatoires synthétiques avec des dimensions allant jusqu'à $d=1000$.

• Performance par rapport à l'état de l'art :
  • En basses dimensions, la méthode proposée est comparable aux méthodes récentes d'échantillonnage dans l'espace tangent [9].
  • En hautes dimensions ($d \gg 10$), l'échantillonnage non contraint sur la sphère surpasse nettement les méthodes d'espace tangent. Cela est attribué à l'espace de recherche plus vaste et à l'évitement d'opérations de projection coûteuses (multiplications matrice-matrice) requises par les méthodes d'espace tangent.
• Vitesses de convergence :
  • La méthode présente une convergence linéaire pour l'erreur de quotient relative (RQE).
  • Le résidu quadratique minimal (MSQR) pour l'équation aux valeurs propres généralisée montre un taux de convergence de $O(1/k)$, supérieur aux taux sous-linéaires souvent observés dans les méthodes sans dérivées.
• Avantage du second ordre :
  La variante Quasi-Newton (Algorithme 3) démontre un comportement de convergence plus strict et une réduction d'erreur plus rapide près des points critiques par rapport à la variante du premier ordre (Algorithme 2), comblant efficacement l'écart de performance près des optimums.

5. Importance

Ce travail représente une avancée significative en optimisation sans dérivées pour les problèmes spectraux.

• Impact pratique : Il permet le calcul de normes d'opérateurs et de quotients de Rayleigh dans des scénarios où les opérateurs adjoints sont indisponibles, incohérents ou trop coûteux à calculer (par exemple, codes de simulation hérités, solveurs d'EDP complexes).
• Impact théorique : Il comble le fossé entre la recherche aléatoire d'ordre zéro et l'optimisation Riemannienne en fournissant des estimateurs sans biais pour les gradients et les Hessiennes sur des variétés sans projections explicites sur la variété.
• Efficacité algorithmique : La taille de pas en forme close et la capacité d'opérer sans projections d'espace tangent rendent l'algorithme efficace sur le plan computationnel et évolutif vers des problèmes de haute dimension.

En résumé, Bresch généralise les méthodes d'ordre zéro pour traiter les quotients de fonctions quadratiques en remplaçant l'échantillonnage contraint dans l'espace tangent par un échantillonnage non contraint sur la sphère, en dérivant des tailles de pas exactes et en établissant un cadre rigoureux du second ordre qui surpasse les techniques existantes de l'état de l'art dans des contextes de haute dimension et de boîte noire.