Definition - Stochastisches Gradientenabstiegsverfahren

• Generalisierungen:
  • Gradientenabstiegsverfahren
  • Mini-Batch Gradient Descent
• Eigenschaften:
  • Konvergenz des stochastischen Gradientenabstiegsverfahren für stark-konvexe Funktionen
  • Konvergenz des stochastischen Gradientenabstiegsverfahren für konvexe Funktionen
  • Gradient Descent vs Stochastic Gradient Descent vs Mini-Batch Gradient Descent
• Involvierte Definitionen:
  • Partielle Differenzierbarkeit
  • Diskrete Gleichverteilung
  • siehe auch Gradientenabstiegsverfahren
• Veranstaltung: MatheDS
• Referenz: @riedel2023 (S. 78 f.)

⠀

Definition: Stochastisches Gradientenabstiegsverfahren

Sei eine partiell differenzierbare Funktion mit Teilfunktionen , sodass .

Als stochastisches Gradientenabstiegsverfahren definieren wir die Iteration in Richtung des jeweils steilsten Abstiegs einer zufällig gewählten Teilfunktion von , also:

wobei

• der Startpunkt fest gewählt ist,
• der Index einer in jedem Schritt zufällig (diskret gleichverteilt) zu wählenden Teilfunktion sei,
• der Parameter die Schrittweite des Verfahrens beschreibt.

Anmerkung

Variierende Schrittweite?

Klar, natürlich kann man statt auch eine Folge wählen :)

Wie ist das mit den Teilfunktionen gemeint?

Nun, viele Funktionen lassen sich in eine Summe von Teilfunktionen aufteilen. Beispielsweise lässt sich die Kostenfunktion eines Datensatzes aufteilen in die Summe der Kostenfunktionen der einzelnen Einträge aus dem Datensatz.

In diesen Fällen ist die Berechnung des normalen Gradientenabstiegsverfahrens sehr aufwändig. Stochastic Gradient Descent führt dort in der Praxis oft schneller zum Ziel.