On Approximate Computation of Critical Points

Résumé technique : Sur le calcul approximatif des points critiques

Énoncé du problème
L'article traite de la complexité computationnelle de la recherche de points critiques (points stationnaires où le gradient s'annule) pour les fonctions non convexes, en se concentrant spécifiquement sur la tractabilité du calcul approximatif. Bien qu'il soit bien établi que trouver des points critiques exacts pour les polynômes cubiques est NP-difficile, une croyance prédominante dans la communauté de l'optimisation suggère que trouver des points critiques approximatifs — des points où la norme du gradient est faible ($\|\nabla f(x)\| \le \epsilon$) ou des points proches d'un véritable point critique ($\|x - x^*\| \le \epsilon$) — devrait être computationnellement tractable. Les auteurs contestent cette intuition, en étudiant si même des approximations grossières de points critiques peuvent être calculées en temps polynomial pour des classes simples de fonctions non convexes, telles que les polynômes de bas degré.

Méthodologie
Les auteurs utilisent le modèle de calcul de Turing standard, où l'entrée consiste en les coefficients d'une classe de fonctions paramétriques (principalement des polynômes de degré fixe). La méthodologie centrale implique des réductions en temps polynomial du problème de la Clique (un problème connu pour être NP-complet) vers le problème de la recherche de points critiques approximatifs.

Outils techniques clés :

1. Construction polynomiale : Les auteurs construisent des polynômes cubiques et quartiques spécifiques (ainsi que des produits de polynômes avec des exponentielles) dont les points critiques correspondent aux cliques dans un graphe donné. Une construction centrale est un polynôme quartique $g_{G,C,k}(x)$ conçu de telle sorte que ses racines correspondent exactement aux vecteurs indicateurs de $k$-cliques dans un graphe $G$.
2. Dureté de l'approximation : Pour prouver la dureté de l'approximation, les auteurs doivent démontrer que si un algorithme renvoie un point qui est "proche" d'être un point critique (en termes de norme de gradient ou de distance euclidienne), il résout efficacement le problème de décision sous-jacent qui est NP-difficile.
3. Bornes analytiques : Les preuves reposent largement sur l'établissement des bornes du comportement des polynômes construits. Cela inclut :
   • L'établissement que les polynômes sont coercitifs et admettent des minima.
   • L'utilisation des conditions nécessaires du premier et second ordre (FONC/SONC) pour borner l'emplacement des minimiseurs.
   • L'application d'arguments de continuité de Lipschitz pour relier la valeur du polynôme en un point proche d'un point critique à la valeur au véritable point critique.
   • L'utilisation de bornes sur les racines de polynômes univariés (borne de Fujiwara) pour contraindre l'amplitude des variables.

Contributions clés et résultats

L'article établit que le calcul de points critiques approximatifs est intraitable (à moins que P $\neq$ NP) selon plusieurs définitions distinctes d'« approximation » et sous diverses hypothèses structurelles :

1. Points critiques $\epsilon$-approximatifs (Norme de gradient) :

   • Théorème 3 : Les auteurs prouvent que, sauf si P=NP, aucun algorithme en temps polynomial ne peut calculer un point critique $2^n$-approximatif (où $\|\nabla p(x)\| \le 2^n$) pour un polynôme cubique en $n$ variables. Cela reste vrai même si l'algorithme est autorisé à retourner un point arbitraire lorsqu'aucun point critique n'existe.
   • Corollaire 8 : Ce résultat s'étend aux algorithmes en temps pseudo-polynomial pour trouver des points critiques $n^d$-approximatifs.
   • Implication pour les points critiques uniques : La dureté persiste même si le polynôme est promis d'avoir un point critique unique. Trouver un point critique $2^n$-approximatif dans ce cadre réfuterait la conjecture de la Clique Plantée et impliquerait NP=RP.

2. Hypothèses structurelles (Minorité de borne inférieure et unicité) :

   • Proposition 9 : Décider si l'exponentielle d'un polynôme cubique (qui est toujours minorée) possède un point critique est NP-difficile.
   • Proposition 10 : Même pour des fonctions minorées garantissant l'existence d'un point critique et l'absence de points critiques parasites (c'est-à-dire que chaque point critique est un minimum global), la recherche d'un point critique est difficile. Cela implique que l'absence de minima locaux parasites ne garantit pas la tractabilité.
   • Théorème 11 : Pour les polynômes quartiques minorés, trouver un point critique $2^n$-approximatif dans une boule de rayon $2^n$ est NP-difficile, même si l'algorithme est autorisé à se comporter de manière arbitraire lorsqu'aucun point critique n'existe dans l'hypercube unité.

3. Points critiques $\epsilon$-proches (Distance à la solution) :

   • Définition : Un point critique $\epsilon$-proche est un point situé à une distance $\epsilon$ d'un véritable point critique.
   • Théorème 13 : À moins que P $\neq$ NP, aucun algorithme en temps polynomial ne peut calculer un point critique $\frac{1}{12000 n^{3.5}}$-proche pour un polynôme cubique.
   • Théorème 15 : Ce résultat de dureté s'étend aux fonctions minorées (produits de polynômes quartiques et d'exponentielles), montrant que trouver un point critique $\frac{1}{1000 n^7}$-proche est également intraitable.

Signification et revendications
La principale signification de cet article réside dans le fait qu'il renverse la croyance commune selon laquelle le calcul de points critiques approximatifs est une tâche tractable en optimisation non convexe. Les auteurs soutiennent que la difficulté de l'optimisation non convexe ne provient pas uniquement de la présence de minima locaux parasites ou de points cols, mais qu'elle est intrinsèque à la tâche de localiser n'importe quel point stationnaire, même approximativement.

• Contraste avec les modèles d'oracle : Les auteurs distinguent leurs résultats des travaux antérieurs basés sur des modèles d'oracle (par exemple, Carmon et al., Hollender et Zampetakis), qui fournissent des bornes inférieures sur la complexité de requête. Cet article opère dans le modèle de Turing, excluant tout algorithme en temps polynomial, y compris ceux basés sur des relaxations convexes ou d'autres approches non fondées sur des oracles.
• Implications pour les algorithmes : Les résultats suggèrent que les algorithmes standards comme la descente de gradient ou la méthode de Newton (et ses extensions d'ordre supérieur) ne peuvent pas garantir la recherche de même des approximations grossières de points critiques en temps polynomial pour des polynômes cubiques généraux. Plus précisément, l'article note que l'extension la plus naturelle de la méthode de Newton (résoudre les points critiques des développements de Taylor de degré 3) manque de complexité par itération traitable, à moins que P $\neq$ NP.
• Directions futures : Les auteurs concluent modestement que leurs résultats motivent la recherche de classes spécifiques de fonctions paramétriques et d'hypothèses structurelles (vérifiables en temps polynomial) sous lesquelles le calcul de points critiques approximatifs devient tractable. Ils notent que si la convexité permet la tractabilité, vérifier la convexité pour des polynômes de degré 4 ou supérieur est en soi difficile, laissant un fossé dans la compréhension des propriétés structurelles qui permettent une approximation efficace.