Gradientenabstieg

Gradientenabstieg ist eine Methode zur unbeschränkten mathematischen Optimierung . Es handelt sich um einen iterativen Algorithmus erster Ordnung zur Minimierung einer differenzierbaren multivariaten Funktion .

Die Idee besteht darin, wiederholt Schritte entgegen der Richtung des Gradienten (oder des angenäherten Gradienten) der Funktion am aktuellen Punkt auszuführen, da dies die Richtung des steilsten Abstiegs ist. Umgekehrt führt ein Schritt in Richtung des Gradienten zu einer Trajektorie, die die Funktion maximiert; dieses Verfahren wird dann als Gradientenaufstieg bezeichnet . Gradientenabstieg sollte nicht mit lokalen Suchalgorithmen verwechselt werden, obwohl beide iterative Optimierungsverfahren sind .

Gradientenabstieg ist besonders nützlich im maschinellen Lernen und in der künstlichen Intelligenz, um die Kosten- oder Verlustfunktion zu minimieren. ^{[ 1 ]}

Das Gradientenabstiegsverfahren wird im Allgemeinen Augustin-Louis Cauchy zugeschrieben , der es 1847 erstmals vorschlug. ^{[ 2 ]} Jacques Hadamard entwickelte 1907 unabhängig davon eine ähnliche Methode. ^{[ 3 ] [ 4 ]} Die Konvergenzeigenschaften des Verfahrens für nichtlineare Optimierungsprobleme wurden erstmals 1944 von Haskell Curry untersucht. ^{[ 5 ]} In den folgenden Jahrzehnten wurde das Verfahren zunehmend erforscht und angewendet. ^{[ 6 ] [ 7 ]}

Eine einfache Erweiterung des Gradientenabstiegs, der stochastische Gradientenabstieg , dient heute als grundlegendster Algorithmus für das Training der meisten tiefen neuronalen Netze .

Gradientenabstieg basiert auf der Beobachtung, dass eine Funktion mehrerer Variablen, die in einer Umgebung eines Punktes definiert und differenzierbar ist , am schnellsten abnimmt , wenn man von dort aus in Richtung des negativen Gradienten von f an dieser Stelle geht . Daraus folgt, dass, wenn ${\displaystyle f(\mathbf {x} )}$${\displaystyle \mathbf {a} }$${\displaystyle f(\mathbf {x} )}$${\displaystyle \mathbf {a} }$${\displaystyle f}$${\displaystyle \mathbf {a} ,dh,-\nabla f(\mathbf {a} )}$

${\displaystyle \mathbf {a} _{n+1}=\mathbf {a} _{n}-\eta \nabla f(\mathbf {a} _{n})}$

Bei ausreichend kleiner Schrittweite oder Lernrate gilt dann . Anders ausgedrückt: Der Term wird von subtrahiert, da wir uns entgegen dem Gradienten, also in Richtung des lokalen Minimums, bewegen wollen. Ausgehend von dieser Beobachtung beginnt man mit einer Schätzung für ein lokales Minimum von und betrachtet die Folge , für die gilt: ${\displaystyle \eta \in \mathbb {R} _{+}}$${\displaystyle f(\mathbf {a_{n}} )\geq f(\mathbf {a_{n+1}} )}$${\displaystyle \eta \nabla f(\mathbf {a} )}$${\displaystyle \mathbf {a} }$${\displaystyle \mathbf {x} _{0}}$${\displaystyle f}$${\displaystyle \mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots }$

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\eta _{n}\nabla f(\mathbf {x} _{n}),\ n\geq 0.}$

Wir haben eine monotone Folge

${\displaystyle f(\mathbf {x} _{0})\geq f(\mathbf {x} _{1})\geq f(\mathbf {x} _{2})\geq \cdots ,}$

Die Folge konvergiert also zum gewünschten lokalen Minimum. Beachten Sie, dass der Wert der Schrittweite in jeder Iteration geändert werden darf. ${\displaystyle (\mathbf {x} _{n})}$${\displaystyle \eta }$

Unter bestimmten Annahmen an die Funktion (z. B. Konvexität und Lipschitz-Stetigkeit ) und für bestimmte Wahlen von kann die Konvergenz zu einem lokalen Minimum garantiert werden . Dazu gehört die Folge ${\displaystyle f}$${\displaystyle f}$${\displaystyle \nabla f}$${\displaystyle \eta }$

${\displaystyle \eta _{n}={\frac {\left|\left(\mathbf {x} _{n}-\mathbf {x} _{n-1}\right)^{\top }\left[\nabla f(\mathbf {x} _{n})-\nabla f(\mathbf {x} _{n-1})\right]\right|}{\left\|\nabla f(\mathbf {x} _{n})-\nabla f(\mathbf {x} _{n-1})\right\|^{2}}}}$

Wie beim Barzilai-Borwein-Verfahren [ ^{8 ] [ 9 ]} oder einer Folge, ^die die Wolfe-Bedingungen erfüllt (die mittels Liniensuche gefunden werden kann). Ist die Funktion konvex , so sind alle lokalen Minima auch globale Minima, sodass in diesem Fall der Gradientenabstieg zur globalen Lösung konvergiert. ${\displaystyle \eta _{n}}$${\displaystyle f}$

Dieser Prozess wird in der nebenstehenden Abbildung veranschaulicht. Hierbei wird angenommen, dass die Funktion in der Ebene definiert ist und ihr Graph eine schalenförmige Gestalt hat. Die blauen Kurven stellen die Höhenlinien dar , also die Bereiche, in denen der Funktionswert konstant ist. Ein roter Pfeil, der von einem Punkt ausgeht, zeigt die Richtung des negativen Gradienten an diesem Punkt an. Der (negative) Gradient an einem Punkt steht senkrecht zur Höhenlinie, die durch diesen Punkt verläuft. Wir sehen, dass der Gradientenabstieg uns zum tiefsten Punkt der Schale führt, also zu dem Punkt, an dem der Funktionswert minimal ist. ${\displaystyle f}$${\displaystyle f}$${\displaystyle f}$

Die grundlegende Intuition hinter dem Gradientenabstieg lässt sich anhand eines hypothetischen Szenarios veranschaulichen. Personen befinden sich in den Bergen und versuchen, abzusteigen (d. h. das globale Minimum zu finden). Dichter Nebel schränkt die Sicht stark ein. Da der Weg den Berg hinunter nicht sichtbar ist, müssen sie lokale Informationen nutzen, um das Minimum zu finden. Sie können die Methode des Gradientenabstiegs anwenden, bei der sie die Steilheit des Hügels an ihrem aktuellen Standort bestimmen und sich dann in Richtung des steilsten Gefälles (bergab) begeben. Wollten sie hingegen den Gipfel (das Maximum) erreichen, würden sie sich in Richtung des steilsten Anstiegs (bergauf) begeben. Mit dieser Methode finden sie schließlich den Weg den Berg hinunter oder geraten möglicherweise in eine Senke (ein lokales Minimum oder einen Sattelpunkt ), wie beispielsweise einen Bergsee. Angenommen, die Steilheit des Hügels ist nicht durch einfache Beobachtung erkennbar, sondern erfordert ein ausgeklügeltes Messinstrument, das den Personen in diesem Moment zufällig zur Verfügung steht. Die Messung der Steilheit des Hügels mit diesem Instrument benötigt einige Zeit. Daher sollten sie den Einsatz des Instruments minimieren, wenn sie vor Sonnenuntergang vom Berg herunterkommen wollen. Die Schwierigkeit besteht dann darin, die Frequenz für die Messung der Hangneigung so zu wählen, dass sie nicht vom Weg abkommen.

In dieser Analogie repräsentieren die Personen den Algorithmus, und der Weg den Berg hinunter steht für die Abfolge der Parametereinstellungen, die der Algorithmus durchläuft. Die Steilheit des Hügels entspricht der Steigung der Funktion an diesem Punkt. Das Instrument zur Messung der Steilheit ist die Differenzierung . Die Richtung, in die sie sich bewegen, entspricht der Steigung der Funktion an diesem Punkt. Die Zeitspanne zwischen den Messungen ist die Schrittweite.

Da eine zu kleine Schrittweite die Konvergenz verlangsamt und eine zu große zu Überschwingen und Divergenz führt, ist die Wahl einer geeigneten Schrittweite ein wichtiges praktisches Problem. Philip Wolfe befürwortete in der Praxis auch die „kluge Wahl der Abstiegsrichtung“ ^{[ 10 ]} . Auch wenn die Verwendung einer von der steilsten Abstiegsrichtung abweichenden Richtung kontraintuitiv erscheinen mag, liegt die Idee darin, dass die geringere Steigung durch die Beibehaltung einer deutlich längeren Distanz kompensiert werden kann. ${\displaystyle \eta }$${\displaystyle \eta }$${\displaystyle \eta }$

Um dies mathematisch zu begründen, betrachten wir eine Richtung und eine Schrittweite sowie die allgemeinere Aktualisierung: ${\displaystyle \mathbf {p} _{n}}$${\displaystyle \eta _{n}}$

${\displaystyle \mathbf {a} _{n+1}=\mathbf {a} _{n}-\eta _{n}\,\mathbf {p} _{n}}$Die

Die Suche nach geeigneten Einstellungen für und erfordert etwas Überlegung. Zunächst einmal möchten wir, dass die Aktualisierungsrichtung bergab zeigt. Mathematisch ausgedrückt: Sei der Winkel zwischen und , dann bedeutet dies, dass . Um dies genauer zu erklären, benötigen wir weitere Informationen über die Zielfunktion, die wir optimieren. Unter der relativ schwachen Annahme, dass stetig differenzierbar ist, können wir beweisen, dass: ^{[ 11 ]}${\displaystyle \mathbf {p} _{n}}$${\displaystyle \eta _{n}}$${\displaystyle \theta _{n}}$${\displaystyle -\nabla f(\mathbf {a_{n}} )}$${\displaystyle \mathbf {p} _{n}}$${\displaystyle \cos \theta _{n}>0.}$${\displaystyle f}$

${\displaystyle f(\mathbf {a} _{n+1})\leq f(\mathbf {a} _{n})-\eta _{n}\|\nabla f(\mathbf {a} _{n})\|_{2}\|\mathbf {p} _{n}\|_{2}\left(\cos \theta _{n}-\max _{t\in [0,1]}{\frac {\|\nabla f(\mathbf {a} _{n}-t\eta _{n}\mathbf {p} _{n})-\nabla f(\mathbf {a} _{n})\|_{2}}{\|\nabla f(\mathbf {a} _{n})\|_{2}}}\right)}$

1

Diese Ungleichung impliziert, dass das Ausmaß der sicheren Verringerung der Funktion von einem Kompromiss zwischen den beiden Termen in eckigen Klammern abhängt. Der erste Term in eckigen Klammern misst den Winkel zwischen der Abstiegsrichtung und dem negativen Gradienten. Der zweite Term misst, wie schnell sich der Gradient entlang der Abstiegsrichtung ändert. ${\displaystyle f}$

Prinzipiell ließe sich die Ungleichung ( 1 ) optimieren , um eine optimale Schrittweite und Richtung zu wählen. Das Problem besteht darin, dass die Auswertung des zweiten Terms in den eckigen Klammern die Auswertung von erfordert , und zusätzliche Gradientenberechnungen sind im Allgemeinen aufwändig und unerwünscht. Folgende Lösungsansätze gibt es: ${\displaystyle \mathbf {p} _{n}}$${\displaystyle \eta _{n}}$${\displaystyle \nabla f(\mathbf {a} _{n}-t\eta _{n}\mathbf {p} _{n})}$

• Verzichten Sie auf die Vorteile einer optimalen Abstiegsrichtung durch Setzen von und verwenden Sie stattdessen eine Liniensuche , um eine geeignete Schrittweite zu finden , beispielsweise eine, die die Wolfe-Bedingungen erfüllt . Eine ökonomischere Methode zur Wahl der Lernrate ist die Backtracking-Liniensuche , ein Verfahren mit guten theoretischen Garantien und experimentellen Ergebnissen. Beachten Sie, dass nicht zwingend als Gradient gewählt werden muss; jede Richtung mit einem positiven Skalarprodukt zum Gradienten führt (bei ausreichend kleinem Wert von ) zu einer Reduzierung des Funktionswertes .${\displaystyle \mathbf {p} _{n}=\nabla f(\mathbf {a_{n}} )}$${\displaystyle \gamma _{n}}$${\displaystyle \mathbf {p} _{n}}$${\displaystyle \eta _{n}}$
• Unter der Annahme, dass die Funktion zweimal differenzierbar ist, wird ihre Hesse-Matrix verwendet , um zu schätzen. Anschließend werden und durch Optimierung der Ungleichung ( 1 ) gewählt.${\displaystyle f}$${\displaystyle \nabla ^{2}f}$${\displaystyle \|\nabla f(\mathbf {a} _{n}-t\eta _{n}\mathbf {p} _{n})-\nabla f(\mathbf {a} _{n})\|_{2}\ approx \|t\eta _{n}\nabla ^{2}f(\mathbf {a} _{n})\mathbf {p} _{n}\|.}$${\displaystyle \mathbf {p} _{n}}$${\displaystyle \eta _{n}}$
• Unter der Annahme, dass Lipschitz-stetig ist , verwenden wir seine Lipschitz-Konstante, um zu beschränken. Dann wählen wir und durch Optimierung der Ungleichung ( 1 ).${\displaystyle \nabla f}$${\displaystyle L}$${\displaystyle \|\nabla f(\mathbf {a} _{n}-t\eta _{n}\mathbf {p} _{n})-\nabla f(\mathbf {a} _{n})\|_{2}\leq Lt\eta _{n}\|\mathbf {p} _{n}\|.}$${\displaystyle \mathbf {p} _{n}}$${\displaystyle \eta _{n}}$
• Erstellen Sie ein benutzerdefiniertes Modell von für . Wählen Sie dann und durch Optimierung der Ungleichung ( 1 ).${\displaystyle \max _{t\in [0,1]}{\frac {\|\nabla f(\mathbf {a} _{n}-t\eta _{n}\mathbf {p} _{n})-\nabla f(\mathbf {a} _{n})\|_{2}}{\|\nabla f(\mathbf {a} _{n})\|_{2}}}}$${\displaystyle f}$${\displaystyle \mathbf {p} _{n}}$${\displaystyle \eta _{n}}$
• Unter stärkeren Annahmen an die Funktion, wie beispielsweise Konvexität , sind möglicherweise fortgeschrittenere Techniken möglich.${\displaystyle f}$

Durch Befolgen einer der oben genannten Vorgehensweisen lässt sich üblicherweise die Konvergenz zu einem lokalen Minimum gewährleisten. Ist die Funktion konvex , so sind alle lokalen Minima auch globale Minima, sodass der Gradientenabstieg in diesem Fall zur globalen Lösung konvergiert. ${\displaystyle f}$

Gradientenabstieg kann zur Lösung eines Systems linearer Gleichungen verwendet werden.

${\displaystyle \mathbf {A} \mathbf {x} -\mathbf {b} =0}$

Das Problem wird als quadratisches Minimierungsproblem neu formuliert. Ist die Systemmatrix reell, symmetrisch und positiv definit , so ist die Zielfunktion die quadratische Funktion, deren Minimierung gilt. ${\displaystyle \mathbf {A} }$

${\displaystyle f(\mathbf {x} )=\mathbf {x} ^{\top }\mathbf {A} \mathbf {x} -2\mathbf {x} ^{\top }\mathbf {b} ,}$

so dass

${\displaystyle \nabla f(\mathbf {x} )=2(\mathbf {A} \mathbf {x} -\mathbf {b} ).}$

Für eine allgemeine reelle Matrix definieren lineare Kleinste-Quadrate${\displaystyle \mathbf {A} }$

${\displaystyle f(\mathbf {x} )=\left\|\mathbf {A} \mathbf {x} -\mathbf {b} \right\|^{2}.}$

Bei der traditionellen linearen Ausgleichsrechnung für reelle Zahlen wird die euklidische Norm verwendet, in welchem ​​Fall ${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {b} }$

${\displaystyle \nabla f(\mathbf {x} )=2\mathbf {A} ^{\top }(\mathbf {A} \mathbf {x} -\mathbf {b} ).}$

Die Liniensuche zur Minimierung, bei der in jeder Iteration die lokal optimale Schrittweite gefunden wird , kann für quadratische Funktionen analytisch durchgeführt werden, und es sind explizite Formeln für das lokale Optimum bekannt. ^{[ 6 ] [ 13 ]}${\displaystyle \eta }$${\displaystyle \eta }$

Zum Beispiel kann für eine reelle symmetrische und positiv definite Matrix ein einfacher Algorithmus wie folgt aussehen, ^{[ 6 ].}${\displaystyle \mathbf {A} }$

${\displaystyle {\begin{aligned}&{\text{repeat in the loop:}}\\&\qquad \mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&\qquad \eta :={\mathbf {r} ^{\top }\mathbf {r} }/{\mathbf {r} ^{\top }\mathbf {Ar} }\\&\qquad \mathbf {x} :=\mathbf {x} +\eta \mathbf {r} \\&\qquad {\hbox{if }}\mathbf {r} ^{\top }\mathbf {r} {\text{ is sufficiently small, then exit loop}}\\&{\text{end repeat loop}}\\&{\text{return }}\mathbf {x} {\text{ as the result}}\end{aligned}}}$

Um eine zweimalige Multiplikation pro Iteration zu vermeiden, stellen wir fest, dass dies impliziert , was zum traditionellen Algorithmus führt, ^{[ 14 ].}${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {x} :=\mathbf {x} +\eta \mathbf {r} }$${\displaystyle \mathbf {r} :=\mathbf {r} -\eta \mathbf {Ar} }$

${\displaystyle {\begin{aligned}&\mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&{\text{repeat in the loop:}}\\&\qquad \eta :={\mathbf {r} ^{\top }\mathbf {r} }/{\mathbf {r} ^{\top }\mathbf {Ar} }\\&\qquad \mathbf {x} :=\mathbf {x} +\eta \mathbf {r} \\&\qquad {\hbox{if }}\mathbf {r} ^{\top }\mathbf {r} {\text{ is sufficiently small, then exit loop}}\\&\qquad \mathbf {r} :=\mathbf {r} -\eta \mathbf {Ar} \\&{\text{end repeat loop}}\\&{\text{return }}\mathbf {x} {\text{ as the result}}\end{aligned}}}$

Die Methode wird selten zur Lösung linearer Gleichungssysteme verwendet; die konjugierte Gradientenmethode ist eine der gängigsten Alternativen. Die Anzahl der Gradientenabstiegsiterationen ist üblicherweise proportional zur spektralen Konditionszahl der Systemmatrix (dem Verhältnis der größten zu den kleinsten Eigenwerten ) , während die Konvergenz der konjugierten Gradientenmethode typischerweise durch die Quadratwurzel der Konditionszahl bestimmt wird, d. h. sie ist deutlich schneller. Beide Methoden können von einer Vorkonditionierung profitieren, wobei der Gradientenabstieg möglicherweise weniger Annahmen über den Vorkonditionierer benötigt. ^{[ 14 ]}${\displaystyle \kappa (\mathbf {A} )}$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {A} ^{\top }\mathbf {A} }$

Bei der Anwendung des Gradientenabstiegsverfahrens zur Lösung von , wobei symmetrisch positiv definit ist, sind die Residuenvektoren über die Iterationen hinweg orthogonal: ${\displaystyle \mathbf {Ax} =\mathbf {b} }$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {r} _{k}=\mathbf {b} -\mathbf {A} \mathbf {x} _{k}}$

${\displaystyle \langle \mathbf {r} _{k+1},\mathbf {r} _{k}\rangle =0.}$

Da jeder Schritt in Richtung des steilsten Anstiegs erfolgt, wechseln sich die Richtungen der steilsten Abstiegsschritte entlang der Extremachsen der länglichen Niveaumengen ab. Bei großen Werten von führt dies zu einem charakteristischen Zickzack-Pfad. Die schlechte Konditionierung von ist die Hauptursache für die langsame Konvergenz, und die Orthogonalität aufeinanderfolgender Residuen verstärkt diesen Wechsel. ${\displaystyle \kappa (\mathbf {A} )}$${\displaystyle \mathbf {A} }$

Wie die Abbildung rechts zeigt, konvergiert das Verfahren des steilsten Abstiegs aufgrund der hohen Konditionszahl von nur langsam , und die Orthogonalität der Residuen zwingt jede neue Richtung dazu, den Überschuss des vorherigen Schritts zu korrigieren. Das Ergebnis ist ein zickzackförmiger Pfad zur Lösung. Diese Ineffizienz ist ein Grund dafür, dass konjugierte Gradientenverfahren oder Vorkonditionierungsverfahren bevorzugt werden. ^{[ 15 ]}${\displaystyle \mathbf {A} }$

Gradientenabstieg kann auch zur Lösung von Systemen nichtlinearer Gleichungen verwendet werden. Das folgende Beispiel zeigt _{, wie man mit} dem Gradientenabstieg drei unbekannte Variablen, x₁ , x₂ und x₃ _, bestimmt . Dieses Beispiel zeigt eine Iteration des Gradientenabstiegs.

Betrachten Sie das nichtlineare Gleichungssystem

${\displaystyle {\begin{cases}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}=0\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1=0\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}=0\end{cases}}}$

Wir führen nun die zugehörige Funktion ein.

${\displaystyle G(\mathbf {x} )={\begin{bmatrix}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}\\\end{bmatrix}},}$

Wo

${\displaystyle \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\end{bmatrix}}.}$

Man könnte nun die Zielfunktion definieren

${\displaystyle {\begin{aligned}f(\mathbf {x} )&={\frac {1}{2}}G^{\top }(\mathbf {x} )G(\mathbf {x} )\\&={\frac {1}{2}}\left[\left(3x_{1}-\cos(x_{2}x_{3})-{\frac {3}{2}}\right)^{2}+\left(4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\right)^{2}+\right.\\&{}\qquad \left.\left(\exp(-x_{1}x_{2})+20x_{3}+{\frac {10\pi -3}{3}}\right)^{2}\right],\end{aligned}}}$

die wir zu minimieren versuchen werden. Nehmen wir als erste Schätzung an, dass wir Folgendes verwenden:

${\displaystyle \mathbf {x} ^{(0)}=\mathbf {0} ={\begin{bmatrix}0\\0\\0\\\end{bmatrix}}.}$

Wir wissen, dass

${\displaystyle \mathbf {x} ^{(1)}=\mathbf {0} -\eta _{0}\nabla f(\mathbf {0} )=\mathbf {0} -\eta _{0}J_{G}(\mathbf {0} )^{\top }G(\mathbf {0} ),}$

wobei die Jacobi-Matrix gegeben ist durch ${\displaystyle J_{G}}$

${\displaystyle J_{G}(\mathbf {x} )={\begin{bmatrix}3&\sin(x_{2}x_{3})x_{3}&\sin(x_{2}x_{3})x_{2}\\8x_{1}&-1250x_{2}+2&0\\-x_{2}\exp {(-x_{1}x_{2})}&-x_{1}\exp(-x_{1}x_{2})&20\\\end{bmatrix}}.}$

Wir berechnen:

${\displaystyle J_{G}(\mathbf {0} )={\begin{bmatrix}3&0&0\\0&2&0\\0&0&20\end{bmatrix}},\qquad G(\mathbf {0} )={\begin{bmatrix}-2.5\\-1\\10.472\end{bmatrix}}.}$

Daher

${\displaystyle \mathbf {x} ^{(1)}=\mathbf {0} -\eta _{0}{\begin{bmatrix}-7.5\\-2\\209.44\end{bmatrix}},}$

Und

${\displaystyle f(\mathbf {0} )=0.5\left((-2.5)^{2}+(-1)^{2}+(10.472)^{2}\right)=58.456.}$

Nun muss ein geeignetes gefunden werden, so dass ${\displaystyle \eta _{0}}$

${\displaystyle f\left(\mathbf {x} ^{(1)}\right)\leq f\left(\mathbf {x} ^{(0)}\right)=f(\mathbf {0} ).}$

Dies kann mit verschiedenen Liniensuchalgorithmen erfolgen . Man könnte auch einfach raten, welcher Algorithmus den richtigen Wert liefert. ${\displaystyle \eta _{0}=0.001,}$

${\displaystyle \mathbf {x} ^{(1)}={\begin{bmatrix}0.0075\\0.002\\-0.20944\\\end{bmatrix}}.}$

Die Auswertung der Zielfunktion an dieser Stelle ergibt:

${\displaystyle f\left(\mathbf {x} ^{(1)}\right)=0.5\left((-2.48)^{2}+(-1.00)^{2}+(6.28)^{2}\right)=23.306.}$

Die Abnahme von auf den Wert des nächsten Schritts ${\displaystyle f(\mathbf {0} )=58.456}$

${\displaystyle f\left(\mathbf {x} ^{(1)}\right)=23.306}$

Dies stellt eine deutliche Verringerung der Zielfunktion dar. Weitere Schritte würden ihren Wert weiter reduzieren, bis eine Näherungslösung für das System gefunden wäre.

Gradientenabstiegsverfahren funktionieren in Räumen beliebiger Dimension, sogar in unendlichdimensionalen. Im letzteren Fall ist der Suchraum typischerweise ein Funktionenraum , und man berechnet die Fréchet-Ableitung des zu minimierenden Funktionals, um die Abstiegsrichtung zu bestimmen. ^{[ 7 ]}

Dass Gradientenabstieg in beliebiger Dimension (zumindest in endlicher) funktioniert, lässt sich als Folge der Cauchy-Schwarz-Ungleichung sehen : Der Betrag des Skalarprodukts zweier Vektoren beliebiger Dimension ist maximal, wenn sie kollinear sind . Im Fall des Gradientenabstiegs wäre dies der Fall, wenn der Vektor der Anpassungen der unabhängigen Variablen proportional zum Gradientenvektor der partiellen Ableitungen ist.

Der Gradientenabstieg kann viele Iterationen benötigen, um ein lokales Minimum mit der erforderlichen Genauigkeit zu berechnen , wenn die Krümmung der gegebenen Funktion in verschiedenen Richtungen stark variiert. Für solche Funktionen behebt eine Vorkonditionierung , die die Geometrie des Raums so verändert, dass die Niveaumengen der Funktion konzentrischen Kreisen ähneln, die langsame Konvergenz. Die Konstruktion und Anwendung einer Vorkonditionierung kann jedoch rechenaufwändig sein.

Der Gradientenabstieg kann durch Momentum-Parameter ^{[ 16 ]} ( Nesterov , Polyak ^{[ 17 ]} und Frank-Wolfe ^{[ 18 ]} ) und Parameter für schwere Kugeln (exponentielle gleitende Mittelwerte ^{[ 19 ]} und positives/negatives Momentum ^{[ 20 ]} ) modifiziert werden. Zu den wichtigsten Beispielen solcher Optimierer gehören Adam, DiffGrad, Yogi, AdaBelief usw.

Methoden, die auf dem Newton-Verfahren und der Invertierung der Hesse-Matrix mittels konjugierter Gradientenverfahren basieren , können bessere Alternativen darstellen. ^{[ 21 ] [ 22 ]} Im Allgemeinen konvergieren solche Methoden mit weniger Iterationen, allerdings ist der Aufwand pro Iteration höher. Ein Beispiel hierfür ist das BFGS-Verfahren , bei dem in jedem Schritt eine Matrix berechnet wird, mit der der Gradientenvektor multipliziert wird, um in eine „bessere“ Richtung zu gelangen. In Kombination mit einem komplexeren Liniensuchalgorithmus wird so der optimale Wert ermittelt. Bei extrem großen Problemen, bei denen der Arbeitsspeicher eine entscheidende Rolle spielt, sollte anstelle von BFGS oder dem Gradientenverfahren ein speicherschonendes Verfahren wie L-BFGS verwendet werden. ${\displaystyle \eta .}$

Obwohl es manchmal möglich ist, Gradientenabstieg anstelle eines lokalen Suchalgorithmus zu verwenden, gehört Gradientenabstieg nicht zur selben Familie: Obwohl es sich um eine iterative Methode zur lokalen Optimierung handelt , stützt es sich auf den Gradienten einer Zielfunktion anstatt auf eine explizite Erkundung des Lösungsraums .

Gradientenabstieg kann als Anwendung des Euler-Verfahrens zur Lösung gewöhnlicher Differentialgleichungen auf einen Gradientenfluss betrachtet werden . Diese Gleichung kann wiederum als optimaler Regler ^{[ 23 ]} für das Regelsystem mit gegebener Rückkopplungsform abgeleitet werden . ${\displaystyle x'(t)=-\nabla f(x(t))}$${\displaystyle x'(t)=u(t)}$${\displaystyle u(t)}$${\displaystyle u(t)=-\nabla f(x(t))}$

Gradientenabstiegsverfahren können in einem lokalen Minimum konvergieren und sich in der Nähe eines Sattelpunkts verlangsamen . Selbst bei unbeschränkter quadratischer Minimierung entwickelt das Gradientenabstiegsverfahren mit fortschreitenden Iterationen ein Zickzackmuster, was zu langsamer Konvergenz führt. Um diese Mängel zu beheben, wurden verschiedene Modifikationen des Gradientenabstiegsverfahrens vorgeschlagen.

Yurii Nesterov schlug ^{[ 24 ]} eine einfache Modifikation vor, die eine schnellere Konvergenz für konvexe Probleme ermöglicht und seither verallgemeinert wurde. Für unbeschränkte, glatte Probleme wird die Methode als schnelles Gradientenverfahren (FGM) oder beschleunigtes Gradientenverfahren (AGM) bezeichnet. Genauer gesagt: Ist die differenzierbare Funktion konvex und Lipschitz -stetig und wird keine starke Konvexität vorausgesetzt , so ist der Fehler im Zielfunktionswert, der in jedem Schritt durch das Gradientenabstiegsverfahren erzeugt wird, durch beschränkt . Mithilfe der Nesterov-Beschleunigungstechnik verringert sich der Fehler um ^{[ 25 ] [ 26 ]} . Es ist bekannt, dass die Abklingrate der Kostenfunktion für Optimierungsverfahren erster Ordnung optimal ist. Dennoch besteht die Möglichkeit, den Algorithmus durch Reduzierung des konstanten Faktors zu verbessern. Das optimierte Gradientenverfahren (OGM) ^{[ 27 ] halbiert diese Konstante und ist ein optimales Verfahren erster Ordnung für große Probleme [ 28 ]} .${\displaystyle f}$${\displaystyle \nabla f}$${\displaystyle f}$${\displaystyle k}$${\textstyle {\mathcal {O}}\left({k^{-1}}\right)}$${\textstyle {\mathcal {O}}\left({k^{-2}}\right)}$${\displaystyle {\mathcal {O}}\left({k^{-2}}\right)}$

Bei eingeschränkten oder nichtglatten Problemen wird Nesterovs FGM als schnelle proximale Gradientenmethode (FPGM) bezeichnet, eine Beschleunigung der proximalen Gradientenmethode .

Um das Zickzackmuster des Gradientenabstiegs zu durchbrechen, verwendet die Momentum- oder Heavy-Ball-Methode einen Momentum-Term in Analogie zu einer schweren Kugel, die auf der Oberfläche der Werte der zu minimierenden Funktion gleitet ^{[ 6 ]} , oder zur Massenbewegung in der Newtonschen Dynamik durch ein viskoses Medium in einem konservativen Kraftfeld ^{[ 29 ]} . Der Gradientenabstieg mit Momentum speichert die Lösungsaktualisierung in jeder Iteration und bestimmt die nächste Aktualisierung als Linearkombination des Gradienten und der vorherigen Aktualisierung. Für die unbeschränkte quadratische Minimierung ist die theoretische Konvergenzrate der Heavy-Ball-Methode asymptotisch gleich derjenigen des optimalen konjugierten Gradientenverfahrens ^{[ 6 ]} .

Diese Technik wird beim stochastischen Gradientenabstieg und als Erweiterung der Backpropagation -Algorithmen zum Trainieren künstlicher neuronaler Netze eingesetzt . ^{[ 30 ] [ 31 ]} In Richtung der Aktualisierung fügt der stochastische Gradientenabstieg eine stochastische Eigenschaft hinzu. Die Gewichte können zur Berechnung der Ableitungen verwendet werden.

Gradientenabstieg kann durch Einbeziehung einer Projektion auf die Menge der Nebenbedingungen erweitert werden, um auch Nebenbedingungen zu berücksichtigen . Diese Methode ist nur dann praktikabel, wenn die Projektion effizient auf einem Computer berechnet werden kann. Unter geeigneten Annahmen konvergiert das Verfahren. Es handelt sich dabei um einen Spezialfall des Vorwärts-Rückwärts-Algorithmus für monotone Inklusionen (der konvexe Programmierung und Variationsungleichungen umfasst ). ^{[ 32 ]}

Gradientenabstieg ist ein Spezialfall des Spiegelabstiegs, bei dem die quadrierte euklidische Distanz als gegebene Bregman-Divergenz verwendet wird . ^{[ 33 ]}

Die Eigenschaften des Gradientenabstiegs hängen von den Eigenschaften der Zielfunktion und der verwendeten Variante ab (z. B. ob ein Liniensuchschritt verwendet wird). Die getroffenen Annahmen beeinflussen die Konvergenzrate und andere Eigenschaften, die für den Gradientenabstieg bewiesen werden können. ^{[ 34 ]} Beispielsweise konvergiert der Gradientenabstieg linear mit fester Schrittweite, wenn die Zielfunktion als stark konvex und Lipschitz-glatt angenommen wird. ^{[ 1 ]} Weniger strenge Annahmen führen entweder zu schwächeren Konvergenzgarantien oder erfordern eine anspruchsvollere Wahl der Schrittweite. ^{[ 34 ]}

• Yang-Mills-Fluss
• Yang-Mills-Higgs-Fluss
• Seiberg-Witten-Fluss

• Boyd, Stephen ; Vandenberghe, Lieven (2004). „Unconstrained Minimization“ (PDF) . Konvexe Optimierung . New York: Cambridge University Press. S.  457–520 . ISBN 0-521-83378-7Die
• Chong, Edwin KP; Żak, Stanislaw H. (2013). „Gradientenmethoden“ . Einführung in die Optimierung (4. Aufl.). Hoboken: Wiley. S.  131–160 . ISBN 978-1-118-27901-4Die
• Himmelblau, David M. (1972). „Unbeschränkte Minimierungsverfahren mit Ableitungen“. Angewandte nichtlineare Programmierung . New York: McGraw-Hill. S.  63–132 . ISBN 0-07-028921-2Die

• Anwendung des Gradientenabstiegs in C++, Boost und Ublas für lineare Regression
• Eine Reihe von Videos der Khan Academy behandelt den Gradientenaufstieg.
• Online-Buch zur Lehre des Gradientenabstiegs im Kontext tiefer neuronaler Netze
• Archiviert bei Ghostarchive und der Wayback Machine : „Gradient Descent, How Neural Networks Learn“ . 3Blue1Brown . 16. Oktober 2017 – via YouTube .
• Garrigos, Guillaume; Gower, Robert M. (2023). „Handbook of Convergence Theorems for (Stochastic) Gradient Methods“. arXiv : 2301.11235 [ math.OC ].