On Approximate Computation of Critical Points

Sintesi Tecnica: Sull'approssimazione del calcolo dei punti critici

Enunciato del Problema
Il documento affronta la complessità computazionale della ricerca di punti critici (punti stazionari dove il gradiente si annulla) per funzioni non convesse, concentrandosi specificamente sulla trattabilità del calcolo approssimato. Sebbene sia ben stabilito che trovare punti critici esatti per polinomi cubici sia NP-difficile, una convinzione prevalente nella comunità dell'ottimizzazione suggerisce che trovare punti critici approssimati — ovvero punti dove la norma del gradiente è piccola ($\|\nabla f(x)\| \le \epsilon$) o punti vicini a un vero punto critico ($\|x - x^*\| \le \epsilon$) — debba essere computazionalmente trattabile. Gli autori mettono in discussione questa intuizione, indagando se anche approssimazioni grossolane di punti critici possano essere computate in tempo polinomiale per classi semplici di funzioni non convesse, come i polinomi di basso grado.

Metodologia
Gli autori utilizzano il modello standard di computazione di Turing, in cui l'input consiste nei coefficienti di una classe di funzioni parametriche (principalmente polinomi di grado fisso). La metodologia centrale prevede riduzioni in tempo polinomiale dal problema del Clique (un noto problema NP-completo) al problema della ricerca di punti critici approssimati.

Strumenti tecnici chiave:

1. Costruzione Polinomiale: Gli autori costruiscono specifici polinomi cubici e quartici (e prodotti di polinomi con esponenziali) i cui punti critici corrispondono a clique in un dato grafo. Una costruzione centrale è un polinomio quartico $g_{G,C,k}(x)$ progettato in modo tale che le sue radici corrispondano esattamente ai vettori indicatori di $k$-clique in un grafo $G$.
2. Difficoltà dell'Approssimazione: Per dimostrare la difficoltà dell'approssimazione, gli autori devono dimostrare che se un algoritmo restituisce un punto che è "vicino" ad essere un punto critico (in termini di norma del gradiente o distanza euclidea), esso risolve efficacemente il problema decisionale NP-difficile sottostante.
3. Limiti Analitici: Le prove si basano pesantemente sul determinare il comportamento dei polinomi costruiti. Ciò include:
   • Stabilire che i polinomi siano coercitivi e ammettano minimi.
   • Utilizzare le Condizioni Necessarie del Primo e Secondo Ordine (FONC/SONC) per limitare la posizione dei minimizzatori.
   • Applicare argomenti di continuità di Lipschitz per relazionare il valore del polinomio in un punto vicino a un punto critico al valore nel vero punto critico.
   • Utilizzare i limiti sulle radici di polinomi univariati (il limite di Fujiwara) per vincolare l'ampiezza delle variabili.

Contributi Chiave e Risultati

Il documento stabilisce che il calcolo di punti critici approssimati è intrattabile (a meno che P $\neq$ NP) sotto diverse definizioni distinte di "approssimazione" e sotto varie assunzioni strutturali:

1. Punti Critici $\epsilon$-Approssimati (Norma del Gradiente):

   • Teorema 3: Gli autori dimostrano che, a meno che P $\neq$ NP, nessun algoritmo in tempo polinomiale può calcolare un punto critico $2^n$-approssimato (dove $\|\nabla p(x)\| \le 2^n$) per un polinomio cubico in $n$ variabili. Ciò è valido anche se l'algoritmo è autorizzato a restituire un punto arbitrario quando non esiste un punto critico.
   • Corollario 8: Questo risultato si estende agli algoritmi in tempo pseudo-polinomiale per la ricerca di punti critici $n^d$-approssimati.
   • Implicazione per i Punti Critici Unici: La difficoltà persiste anche se al polinomio viene garantito di avere un punto critico unico. Trovare un punto critico $2^n$-approssimato in questo contesto confuterebbe la congettura del Planted Clique e implicherebbe NP=RP.

2. Assunzioni Strutturali (Limitatezza Inferiore e Unicità):

   • Proposizione 9: Decidere se l'esponenziale di un polinomio cubico (che è sempre limitato inferiormente) possieda un punto critico è NP-difficile.
   • Proposizione 10: Anche per funzioni limitate inferiormente e garantite di avere un punto critico e senza punti critici spurii (ovvero, ogni punto critico è un minimo globale), la ricerca di un punto critico è difficile. Ciò implica che l'assenza di minimi locali spurii non garantisce la trattabilità.
   • Teorema 11: Per polinomi quartici limitati inferiormente, trovare un punto critico $2^n$-approssimato all'interno di una sfera di raggio $2^n$ è NP-difficile, anche se l'algoritmo è permesso di comportarsi arbitrariamente quando non esiste un punto critico nella ipercubo unitario.

3. Punti Critici $\epsilon$-Vicini (Distanza dalla Soluzione):

   • Definizione: Un punto critico $\epsilon$-vicino è un punto entro distanza $\epsilon$ da un vero punto critico.
   • Teorema 13: A meno che P $\neq$ NP, nessun algoritmo in tempo polinomiale può calcolare un punto critico $\frac{1}{12000 n^{3.5}}$-vicino per un polinomio cubico.
   • Teorema 15: Questo risultato di difficoltà si estende alle funzioni limitate inferiormente (prodotti di polinomi quartici ed esponenziali), mostrando che trovare un punto critico $\frac{1}{1000 n^7}$-vicino è ugualmente intrattabile.

Significato e Rivendicazioni
Il significato primario del documento risiede nel ribaltare la comune convinzione che il calcolo di punti critici approssimati sia un compito trattabile nell'ottimizzazione non convessa. Gli autori sostengono che la difficoltà dell'ottimizzazione non convessa non derivi esclusivamente dalla presenza di minimi locali o punti di sella spurii, ma sia intrinseca al compito di localizzare qualsiasi punto stazionario, anche solo approssimativamente.

• Contrasto con i Modelli Oracle: Gli autori distinguono i loro risultati dai lavori precedenti in modelli basati su oracle (ad esempio, Carmon et al., Hollender e Zampetakis), che forniscono limiti inferiori sulla complessità di query. Questo articolo opera nel modello di Turing, escludendo qualsiasi algoritmo in tempo polinomiale, inclusi quelli basati su rilassamenti convessi o altri approcci non basati su oracle.
• Implicazioni per gli Algoritmi: I risultati suggeriscono che gli algoritmi standard come il Gradiente Discendente o il metodo di Newton (e le loro estensioni di ordine superiore) non possono garantire di trovare anche solo approssimazioni grossolane di punti critici in tempo polinomiale per polinomi cubici generici. Nello specifico, il documento nota che l'estensione più naturale del metodo di Newton (risolvere per i punti critici di espansioni di Taylor di grado 3) manca di una complessità per iterazione trattabile a meno che P $\neq$ NP.
• Direzioni Future: Gli autori concludono con modestia che i loro risultati motivano la ricerca di classi specifiche di funzioni parametriche e assunzioni strutturali (verificabili in tempo polinomiale) sotto le quali il calcolo di punti critici approssimati diventi trattabile. Notano che, mentre la convessità permette la trattabilità, verificare la convessità per polinomi di grado 4 o superiore è esso stesso difficile, lasciando un vuoto nella comprensione di quali proprietà strutturali permettano un'approssimazione efficiente.