Definition - Gradientenabstiegsverfahren

• Typen:
  • Mini-Batch Gradient Descent
  • Stochastisches Gradientenabstiegsverfahren
• Konstrukte:
  • Vanishing Gradient Problem
  • Exploding Gradient Problem
• Generalisierungen:
  • Folge
• Eigenschaften:
  • n)
  • Gradientenabstiegsverfahren konvergiert für L-glatte und stark-konvexe Funktionen linear
  • Gradient Descent vs Stochastic Gradient Descent vs Mini-Batch Gradient Descent
• Hinreichende Bedingungen:
  • Für die Konvergenz gegen das Globales Minimum:
    • Lokale Minima konvexer Funktionen sind auch globale Minima und
    • Konvexe Funktion hat ihr globales Minimum an der Stelle an der der Gradient null ist
• Involvierte Definitionen:
  • Partielle Differenzierbarkeit
  • Gradient
    • Gradient weist in die Richtung des stärksten Wachstums
  • ArgMin
  • Lokales Minimum
  • Globales Minimum
  • Konvexe Funktion
  • Konkave Funktion
  • siehe auch Newton-Verfahren für Minimierungsprobleme
• Veranstaltung: MatheDS
• Referenz: @riedel2023

⠀

Tipp: Ziel des Gradientenabstiegsverfahrens

Sei eine partiell differenzierbare Funktion.

Ziel des Gradientenabstiegsverfahrens ist es, eine globale Minimalstelle zu bestimmen, also

Definition: Gradientenabstiegsverfahren

Sei eine partiell differenzierbare Funktion.

Als Gradientenabstiegsverfahren definieren wir die Iteration in Richtung des jeweils steilsten Abstiegs von , also:

wobei

• der Startpunkt fest gewählt ist und
• der Parameter die Schrittweite des Verfahrens beschreibt.

Anmerkung

Einschränkungen für konkave Funktionen

Ist eine konkave Funktion, so können zwei Probleme auftreten:

• das Verfahren kann gegen ein lokales Minimum konvergieren.
• das Verfahren kann gegen einen Sattelpunkt konvergieren.

Ist jedoch konvex, werden diese Fälle durch die Propositionen

• Lokale Minima konvexer Funktionen sind auch globale Minima und
• Konvexe Funktion hat ihr globales Minimum an der Stelle an der der Gradient null ist

ausgeschlossen.

Herleitung

In der Definition haben wir das Gradientenabstiegsverfahren durch die Eigenschaft hergeleitet, dass der Gradient in die Richtung des stärksten Wachstums weist.

Wie in @riedel2023 (S. 77) wollen wir hier noch die eine Herleitung mittels des Satzes von Taylor bzw. der Taylor-Approximation erläutern.

Ist also eine offene Menge und eine zweimal differenzierbare Funktion.

Dann gilt mit der mehrdimensionalen Taylor-Approximation für beliebige

heißt: eine Bewegung von aus in Richtung lässt sich mit einem maximalen Fehler von approximieren durch

Ziel des Gradientenabstiegsverfahrens ist das Finden einer Minimalstelle . Wir suchen also dasjenige , anhand dessen wir uns bestmöglich von aus in Richtung bewegen.

Da eine Minimalstelle ist, suchen wir also ein so, dass es den Ausdruck minimiert. Das ist äquivalent dazu, die Funktion zu minimieren, mit

Mithilfe der Lagrange-Funktion erhalten wir das optimale durch:

wobei der Schrittweite entspricht. Wollen wir dieses Verfahren iterieren, um zu finden, so ginge das durch

denn wir Bewegen uns von in Richtung um zu zu gelangen. Und das entspricht genau der Definition des Gradientenverfahrens.