Gradientenabstieg bei nicht konvexen Funktionen

Welche Situationen kennen wir, in denen gezeigt werden kann, dass der Gradientenabstieg für nicht konvexe Funktionen konvergiert (entweder zu einem kritischen Punkt oder zu einem lokalen / globalen Minimum)?

Für SGD zu nicht konvexen Funktionen wurde hier eine Art von Beweis überprüft: http://www.cs.cornell.edu/courses/cs6787/2017fa/Lecture7.pdf

Siehe Anhang B1 unter https://web.stanford.edu/~boyd/cvxbook/ .

Die Funktion und die Einschränkung können in einem quadratisch beschränkten quadratischen Programm nicht konvex sein, und Sie können immer noch eine starke Dualität feststellen (dies ist garantiert, wenn eine technische Bedingung gilt, die als Slaters Einschränkungsqualifizierer bekannt ist).

Starke Dualität in schwachen Begriffen bedeutet, dass wir das Optimierungsproblem lösen können. Aus dem ursprünglichen Problem, das als primäres Problem bezeichnet wird, können Sie ein alternatives Problem formulieren, das als duales Problem bezeichnet wird. Die Lösung des doppelten Problems bietet eine Lösung, die in gewissem Sinne die "beste Untergrenze" für Ihre ursprünglichen Probleme darstellt

Bei vielen nicht konvexen Optimierungsproblemen besteht eine Lücke zwischen der ursprünglichen und der doppelten Lösung, dh die Untergrenze kann weit unter dem tatsächlichen optimalen Wert liegen (sogar negative Unendlichkeit). In einigen besonderen Fällen ist die Bindung eng. Diese Sonderfälle sind solche, in denen wir eine starke Dualität haben.

Der Algorithmus ist eine TECHNIK, mit der der optimale Punkt erreicht wird. Die optimale Lösung und unsere Fähigkeit, sie zu finden, hängen von der GEOMETRIE des Problems ab (zu der die Dualität zu gelangen versucht). Die Analyse besagt, dass bei ordnungsgemäßer Einrichtung die Optimierung auf ein Minimum konvergiert.

Im Allgemeinen konvergiert der Gradientenabstieg zu einem stationären Punkt. Dieser Punkt kann ein lokales Minimum / globales Minimum / Sattelminimum sein. In nur wenigen nicht konvexen Fällen können wir garantieren, wohin es konvergiert

In dieser Antwort werde ich zwei interessante und relevante Artikel untersuchen, die in den Kommentaren angesprochen wurden. Vorher werde ich versuchen, das Problem zu formalisieren und einige der Annahmen und Definitionen zu beleuchten. Ich beginne mit einem Artikel von Lee et al.

Wir versuchen, eine nicht konvexe Funktion zu minimieren , die unten begrenzt ist. Wir verlangen, dass es zweimal differenzierbar ist. Wir verwenden einen Gradientenabstiegsalgorithmus der Form:$f: \mathbb{R}^d \to \mathbb{R}$

.$\pmb{x}_{t+1} = \pmb{x}_t - \alpha\nabla f(\pmb{x}_t)$

Zusätzlich haben wir folgende Anforderung:

$\| \nabla f(\pmb{x}_1)-\nabla f(\pmb{x}_2) \| \leq \ell \| \pmb{x}_1 - \pmb{x}_2 \|, \quad \text{for all } \pmb{x}_1, \pmb{x}_2$

Das heißt, wir verlangen, dass unsere Funktion in ihrer ersten Ableitung Lipschitz ist. Auf Englisch bedeutet dies, dass sich unser Gradient nirgendwo in der Domäne zu schnell ändern kann. Diese Annahme stellt sicher, dass wir eine Schrittgröße so wählen können, dass wir niemals divergierende Schritte erhalten.$\ell$

Denken Sie daran, dass ein Punkt ein strenger Sattel ist, wenn und und . Wenn alle Eigenwerte des Hessischen das gleiche Vorzeichen haben, ist der Punkt ein Minimum (wenn sie positiv sind) oder ein Maximum (wenn sie negativ sind). Wenn es 0 Eigenwerte gibt, wird dies als entartet bezeichnet und es handelt sich nicht um einen strengen Sattel. ∇ f ( $\pmb{x}$λ min ( ∇ 2 f ( $\nabla f(\pmb{x}) = 0$ λ max ( ∇ 2 f ( $\lambda_{\min}\left(\nabla^2 f(\pmb{x})\right) < 0$$\lambda_{\max}\left(\nabla^2 f(\pmb{x})\right) > 0$

Das Papier zeigt, dass mit den obigen Annahmen zusammen mit der Annahme, dass alle Sattelpunkte der Funktion streng gesattelt sind, ein Gradientenabstieg garantiert auf ein Minimum konvergiert.

Der Beweis ist ziemlich technisch, aber die Intuition ist folgende: Definiere eine Menge , wobei ein Sattelpunkt ist. Ich mag diese Notation überhaupt nicht. Was sie versuchen , zu erhalten , ist , dass die Menge der Startwerte für die der Gradient Karte ist sendet zu . Einfacher ausgedrückt ist es die Menge der zufälligen Initialisierungen, die letztendlich zu einem Sattel konvergieren.$W^s(\pmb{x}^s) = \{\pmb{x} : \lim_k g^k(\pmb{x}) = \pmb{x}^s \}$ Wg: R d → R d $\pmb{x}^s$$W$$g : \mathbb{R}^d \to \mathbb{R}^d$$\pmb{x}_k$$\pmb{x}^s$

Ihre Argumentation stützt sich auf den Satz der stabilen Mannigfaltigkeit. Mit den obigen Annahmen und einer Reihe von esoterischen Berechnungen schließen sie, dass die Menge das Maß Null sein muss, das heißt, es besteht keine Wahrscheinlichkeit, dass ein Punkt, der zu einem Sattelpunkt konvergiert, zufällig initialisiert wird. Da wir wissen, dass der Gradientenabstieg auf Funktionen des in den Annahmen beschriebenen Typs mit entsprechend kleinen Schrittgrößen irgendwann einen kritischen Punkt erreichen wird und wir jetzt (fast sicher) wissen, dass er niemals auf einem Sattel landen wird, wissen wir, dass er konvergiert ein Minimierer.$W^s$

Das zweite, neuere Papier von Reddi et al. Ich werde weniger detailliert diskutieren. Es gibt verschiedene Unterschiede. Erstens arbeiten sie nicht mehr in einem deterministischen Rahmen, sondern entscheiden sich für den praktisch relevanteren stochastischen Approximationsrahmen für eine endliche Summe (denken Sie an Stochastic Gradient Descent). Die Hauptunterschiede bestehen darin, dass die Schrittgröße zusätzliche Sorgfalt erfordert und der Gradient zu einer Zufallsvariablen wird. Außerdem lockern sie die Annahme, dass alle Sättel streng sind, und suchen nach einem stationären Punkt zweiter Ordnung. Das heißt, ein Punkt, bei dem $\|\nabla(f) \| \leq \epsilon, \quad \text{and}, \quad \lambda_{\min}\left(\nabla^2 f(\pmb{x})\right)\geq -\sqrt{\rho\epsilon}$

Wobei die Lipschitz-Konstante für den Hessischen ist. (Das heißt, zusätzlich zu der Anforderung, dass unser Gradient nicht zu schnell variiert, haben wir jetzt eine ähnliche Anforderung an unser Hessisches. Im Wesentlichen suchen die Autoren nach einem Punkt, der sowohl in der ersten als auch in der zweiten Ableitung wie ein Minimum aussieht.$rho$

Die Methode, mit der sie dies erreichen, besteht darin, die meiste Zeit eine Variante (wählen Sie Ihren Favoriten) des stochastischen Gradientenabfalls zu verwenden . Aber wo immer sie auf einen Punkt stoßen, an dem , verwenden sie eine geeignet gewählte Methode zweiter Ordnung, um dem Sattel zu entkommen. Sie zeigen, dass sie durch Einbeziehen dieser Informationen zweiter Ordnung nach Bedarf zu einem stationären Punkt zweiter Ordnung konvergieren.$\lambda_{\min}\left(\nabla^2 f(\pmb{x})\right)\leq 0$

Technisch gesehen handelt es sich um eine Gradientenmethode zweiter Ordnung, die unter das Dach von Algorithmen fallen kann, an denen Sie interessiert waren.

Dies ist ein sehr aktives Forschungsgebiet und ich habe viele wichtige Beiträge ausgelassen (ex Ge et al. ). Ich bin auch neu in diesem Thema, daher hat mir diese Frage die Möglichkeit gegeben, nachzuschauen. Bei Interesse setze ich die Diskussion gerne fort.

*** Geeignet gewählt bedeutet einer, von dem gezeigt wird, dass er zu einem stationären Punkt zweiter Ordnung konvergiert. Sie verwenden die kubisch regulierte Newton-Methode von Nesterov und Polyak.

Ich werde versuchen, den Teil der Frage zu beantworten, wann die Konvergenz des Gradientenabfalls zu einem kritischen Punkt erfolgt.

Die Arbeit "Konvergenz von Abstiegsmethoden für semi-algebraische und zahme Probleme: proximale Algorithmen, Vorwärts-Rückwärts-Aufteilung und regulierte Gauß-Seidel-Methoden"

von Attouch, Bolte und Svaiter,

zeigt, dass, wenn die Zielfunktion die Kurdyka-Lojasiewicz (KL) -Ungleichung erfüllt, GD und andere Abstiegsmethoden tatsächlich zu einem Minimierer konvergieren. Beachten Sie, dass der KL-Zustand äußerst allgemein, aber schwer zu erfassen ist. Funktionen, die KL erfüllen, sind beispielsweise durch semi-algebraische Funktionen gegeben (wiederum sehr allgemein, aber kein einfacher Begriff).

Um ein paar Intuitionen über diese Begriffe zu vermitteln, werde ich versuchen, weniger vage, aber auch nicht zu technisch zu sein. Eine Funktion erfüllt die KL-Bedingung an einem kritischen Punkt wenn eine Funktion (beachten Sie, dass ich einige Bedingungen ), so dass für alle so dass für einige . Die Intuition ist, dass es eine Funktion die unsere interessierende Funktion parametrisiert.$f$$\bar{x}$$\phi$

Die Semialgebrizität ist dagegen etwas schwieriger. Das Feld, das es untersucht, wird auch als zahme Geometrie bezeichnet . Ich denke, der Name zahm fängt die Essenz sehr gut ein. Zu dieser Klasse gehörende Funktionen können nicht willkürlich "wild" sein.