Proposition - Konvergenz des stochastischen Gradientenabstiegsverfahren für stark-konvexe Funktionen

• Involvierte Definitionen:
  • Stochastisches Gradientenabstiegsverfahren
  • mu-stark konvexe Funktion
  • L-glatt
  • Totale Differenzierbarkeit
  • Globales Minimum einer Funktion
  • siehe auch Konvergenz des stochastischen Gradientenabstiegsverfahren für konvexe Funktionen
• Veranstaltung: MatheDS
• Referenz: @riedel2023 (Satz 3.3.22)

⠀

Proposition: Konvergenz des stochastischen Gradientenabstiegsverfahren für stark-konvexe Funktionen

Sei -stark konvex, total differenzierbar und -glatt.
Sei das eindeutige globale Minimum von .
Sei eine konstante Schrittweite.
Sei , so dass

Sei die durch das stochastische Gradientenabstiegsverfahren definierte Folge mit beliebigem Startpunkt .

Dann gilt:

Anmerkung

Folgerungen

Für die Schrittweiten von gilt:

• je größer die Schrittweite, desto geringer die Konstante
• je größer die Schrittweite, desto größer der Term .

wobei letztere wiederum von der Größe des Gradienten abhängig ist.

Daher wird in Anwendungen häufig mit einer relativ großen Schrittweite gestartet, welche dann im Verlauf des Verfahrens immer dann halbiert wird, wenn die Iteration zu keinem nennenswerten Fortschritt mehr führt.