On Approximate Computation of Critical Points

Technisches Resümee: Über die approximative Berechnung kritischer Punkte

Problemstellung
Das Paper befasst sich mit der Komplexität der Berechnung kritischer Punkte (stationäre Punkte, an denen der Gradient verschwindet) für nichtkonvexe Funktionen, wobei der Fokus auf der Berechenbarkeit der approximativen Berechnung liegt. Während es etabliert ist, dass das Finden exakter kritischer Punkte für kubische Polynome NP-schwer ist, herrscht in der Optimierungsgemeinschaft die weitverbreitete Annahme vor, dass das Finden approximativer kritischer Punkte – also Punkte, an denen die Gradientennorm klein ist ($\|\nabla f(x)\| \le \epsilon$) oder Punkte, die einem wahren kritischen Punkt nahe kommen ($\|x - x^*\| \le \epsilon$) – berechenbar sein sollte. Die Autoren stellen diese Intuition infrage und untersuchen, ob selbst grobe Approximationen kritischer Punkte für einfache Klassen nichtkonvexer Funktionen, wie etwa Polynome niedrigen Grades, in Polynomialzeit berechnet werden können.

Methodik
Die Autoren verwenden das Standard-Turing-Modell der Berechnung, bei dem die Eingabe aus den Koeffizienten einer parametrischen Funktionsklasse besteht (primär Polynome eines festen Grades). Die Kernmethodik umfasst Polynomialzeit-Reduktionen vom Clique-Problem (ein bekanntes NP-vollständiges Problem) auf das Problem des Findens approximativer kritischer Punkte.

Zentrale technische Werkzeuge sind:

1. Polynomkonstruktion: Die Autoren konstruieren spezifische kubische und quartische Polynome (sowie Produkte von Polynomen mit Exponentialfunktionen), deren kritische Punkte exakt mit Cliques in einem gegebenen Graphen korrespondieren. Eine zentrale Konstruktion ist ein quartisches Polynom $g_{G,C,k}(x)$, das so entworodent ist, dass seine Nullstellen exakt den Indikatorvektoren von $k$-Cliques in einem Graphen $G$ entsprechen.
2. Härte der Approximation: Um die Härte für die approximative Berechnung zu beweisen, müssen die Autoren zeigen, dass ein Algorithmus, der einen Punkt zurückgibt, der „nah“ an einem kritischen Punkt ist (hinsichtlich der Gradientennorm oder der euklidischen Distanz), effektiv das zugrunde liegende NP-schwere Entscheidungsproblem löst.
3. Analytische Schranken: Die Beweise stützen sich stark auf die Begrenzung des Verhaltens der konstruierten Polynome. Dies beinhaltet:
   • Den Nachweis, dass die Polynome koerzitiv sind und Minima aufweisen.
   • Die Verwendung der notwendigen Bedingungen erster und zweiter Ordnung (FONC/SONC), um die Lage der Minimierer zu begrenzen.
   • Die Anwendung von Lipschitz-Stetigkeitsargumenten, um den Wert des Polynoms an einem Punkt nahe eines kritischen Punktes mit dem Wert am wahren kritischen Punkt in Beziehung zu setzen.
   • Die Nutzung von Schranken für die Wurzeln univariater Polynome (Fujiwara-Schranke), um die Größe der Variablen einzugrenzen.

Wesentliche Beiträge und Ergebnisse

Das Paper stellt fest, dass die Berechnung approximativer kritischer Punkte unter mehreren verschiedenen Definitionen von „Approximation“ und unter verschiedenen strukturellen Annahmen unberechenbar ist (sofern P $\neq$ NP):

1. $\epsilon$-approximative kritische Punkte (Gradientennorm):

   • Theorem 3: Die Autoren beweisen, dass, sofern P $\neq$ NP, kein Polynomialzeit-Algorithmus einen $2^n$-approximativen kritischen Punkt (wobei $\|\nabla p(x)\| \le 2^n$) für ein kubisches Polynom in $n$ Variablen berechnen kann. Dies gilt selbst dann, wenn der Algorithmus erlaubt ist, einen beliebigen Punkt zurückzugeben, falls kein kritischer Punkt existiert.
   • Korollar 8: Dieses Ergebnis lässt sich auf pseudo-polynomiale Zeit-Algorithmen für das Finden von $n^d$-approximativen kritischen Punkten ausweiten.
   • Implikation für eindeutige kritische Punkte: Die Härte bleibt bestehen, selbst wenn dem Polynom zugesichert wird, einen eindeutigen kritischen Punkt zu besitzen. Das Finden eines $2^n$-approximativen kritischen Punktes in diesem Szenario würde die Planted-Clique-Vermutung widerlegen und implizieren, dass NP = RP gilt.

2. Strukturelle Annahmen (Untere Beschränktheit und Eindeutigkeit):

   • Proposition 9: Zu entscheiden, ob das Exponential eines kubischen Polynoms (welches stets nach unten beschränkt ist) einen kritischen Punkt besitzt, ist NP-schwer.
   • Proposition 10: Selbst für nach unten beschränkte Funktionen, die garantiert einen kritischen Punkt und keine spuriösen kritischen Punkte besitzen (d. h. jeder kritische Punkt ist ein globales Minimum), ist das Finden eines kritischen Punktes schwer. Dies impliziert, dass das Fehlen spurerer lokaler Minima keine Berechenbarkeit garantiert.
   • Theorem 11: Für nach unten beschränkte quartische Polynome ist das Finden eines $2^n$-approximativen kritischen Punktes innerhalb eines Radius von $2^n$ NP-schwer, selbst wenn der Algorithmus berechtigt ist, sich beliebig zu verhalten, falls kein kritischer Punkt im Einheitshyperwürfel existiert.

3. $\epsilon$-nahe kritische Punkte (Distanz zur Lösung):

   • Definition: Ein $\epsilon$-naher kritischer Punkt ist ein Punkt innerhalb der Distanz $\epsilon$ zu einem wahren kritischen Punkt.
   • Theorem 13: Sofern P $\neq$ NP, kann kein Polynomialzeit-Algorithmus einen $\frac{1}{12000 n^{3.5}}$-nahen kritischen Punkt für ein kubisches Polynom berechnen.
   • Theorem 15: Dieses Härteergebnis erstreckt sich auf nach unten beschränkte Funktionen (Produkte aus quartischen Polynomen und Exponentials), was zeigt, dass das Finden eines $\frac{1}{1000 n^7}$-nahen kritischen Punktes ebenfalls unberechenbar ist.

Bedeutung und Behauptungen
Die primäre Bedeutung des Papers liegt darin, den allgemeinen Glauben zu revidieren, dass die approximative Berechnung kritischer Punkte eine handhabbare Aufgabe in der nichtkonvexen Optimierung sei. Die Autoren argumenten, dass die Schwierigkeit der nichtkonvexen Optimierung nicht allein aus der Präsenz spurerer lokaler Minima oder Sattelpunkte resultiert, sondern intrinsisch mit der Aufgabe verbunden ist, irgendeinen stationären Punkt – selbst nur approximativ – zu lokalisieren.

• Kontrast zu Oracle-Modellen: Die Autoren unterscheiden ihre Ergebnisse von vorangegangenen Arbeiten in Oracle-basierten Modellen (z. B. Carmon et al., Hollender und Zampetakis), die untere Schranken für die Abfragekomplexität liefern. Dieses Paper operiert im Turing-Modell und schließt damit jeden Polynomialzeit-Algorithmus aus, einschließlich solcher, die auf konvexen Relaxationen oder anderen Nicht-Oracle-Ansätzen basieren.
• Implikationen für Algorithmen: Die Ergebnisse legen nahe, dass Standardalgorithmen wie das Gradientenverfahren oder die Newton-Methode (und deren höherwertige Erweiterungen) nicht garantiert werden können, selbst grobe Approximationen kritischer Punkte in Polynomialzeit zu finden. Insbesondere merkt das Paper an, dass die natürlichste höherwertige Erweiterung der Newton-Methode (das Lösen von kritischen Punkten von Grad-3-Taylor-Approximationen) keine handhabbare pro Iteration aufweisende Komplexität besitzt, sofern P $\neq$ NP.
• Zukünftige Richtungen: Die Autoren schließen bescheiden, dass ihre Ergebnisse die Suche nach spezifischen Klassen parametrischer Funktionen und strukturellen Annahmen motivieren, die in Polynomialzeit überprüfbar sind und unter denen die Berechnung approximativer kritischer Punkte berechenbar wird. Sie stellen fest, dass während Konvexität Berechenbarkeit ermöglicht, die Überprüfung der Konvexität für Polynome ab dem Grad 4 selbst schwer ist, was eine Lücke im Verständnis darüber hinterlässt, welche strukturellen Eigenschaften eine effiziente Approximation ermöglichen.