Stochastische Optimierung

Die stochastische Optimierung minimiert eine Zielfunktion unter Verwendung verrauschter Schätzungen ihres Gradienten oder Wertes, wobei Parameter aus zufälligen Teilmengen von Daten oder zufälligen Störungen aktualisiert werden, anstatt die vollständige, exakte Zielfunktion zu verwenden.

Definition

Stochastische Optimierung ist eine Familie iterativer Methoden, die Parameterschätzungen unter Verwendung zufälliger, unverzerrter Schätzungen einer Zielfunktion oder ihres Gradienten aktualisieren, wodurch eine Optimierung ermöglicht wird, wenn die vollständige Zielfunktion zu aufwendig zu bewerten ist oder nur mit Rauschen beobachtet wird.

Scope

Dieses Thema behandelt die stochastische Approximation in der Robbins-Monro-Tradition, den stochastischen Gradientenabstieg und seine Mini-Batch- und Momentum-Varianten, die Schrittweiten- (Lernraten-) Zeitpläne, die die Konvergenz steuern, den Kompromiss zwischen Rauschen und Rechenkosten sowie Konvergenzgarantien. Ihre Rolle bei der Anpassung großer statistischer und maschineller Lernmodelle wird hervorgehoben.

Core questions

• Wie können verrauschte Gradientenschätzungen die Konvergenz zu einem Optimum vorantreiben?
• Welche Schrittweiten-Zeitpläne garantieren Konvergenz im Robbins-Monro-Rahmen?
• Wie tauscht Mini-Batching Rauschen gegen Rechenkosten pro Schritt ein?
• Warum ist stochastische Optimierung für sehr große Datensätze unerlässlich?

Key concepts

• Stochastische Approximation
• Mini-Batch-Gradient
• Lernraten-Zeitplan
• Unverzerrte Gradientenschätzung
• Schrittweiten-Abnahme
• Fast sichere Konvergenz

Key theories

Stochastische Approximation

Das Robbins-Monro-Schema findet die Wurzel einer unbekannten Funktion aus verrauschten Messungen, indem es kleine Schritte unternimmt, deren Größen mit einer vorgeschriebenen Rate abnehmen und unter Bedingungen an die Schrittweitenfolge fast sicher konvergieren.

Stochastische Gradientenmethoden

Das Ersetzen des vollständigen Gradienten durch eine unverzerrte Schätzung aus einer zufälligen Datenuntermenge führt zu kostengünstigen Aktualisierungen, deren gemittelte Trajektorie die Zielfunktion absteigt, wobei Lernraten-Zeitpläne die Konvergenzgeschwindigkeit mit der Varianz des Rauschens ausgleichen.

Clinical relevance

Stochastische Gradientenmethoden ermöglichen es, Modelle an Datensätze anzupassen, die zu groß sind, um auf einmal verarbeitet zu werden, und sie sind die dominierende Optimierungsstrategie für das Training neuronaler Netze und großer Regressionen, wo die Berechnung des vollständigen Gradienten bei jedem Schritt unerschwinglich wäre.

History

Robbins und Monro führten 1951 die stochastische Approximation ein, um Wurzeln aus verrauschten Beobachtungen zu finden, und Kiefer und Wolfowitz passten sie bald darauf an die Optimierung an; die Explosion des maschinellen Lernens im großen Maßstab belebte diese Ideen als stochastischen Gradientenabstieg und seine vielen modernen Varianten wieder.

Key figures

• Herbert Robbins
• Sutton Monro
• Harold Kushner
• Jack Kiefer

Seminal works

• robbins1951
• kushner2003

Frequently asked questions

Warum werden verrauschte Gradienten anstelle des exakten Gradienten verwendet?

Die Berechnung des exakten Gradienten über Millionen von Datenpunkten ist aufwendig. Ein Gradient, der aus einem kleinen zufälligen Batch geschätzt wird, ist weitaus kostengünstiger und, obwohl verrauscht, zeigt er im Durchschnitt immer noch bergab, sodass viele kostengünstige verrauschte Schritte einige exakte übertreffen können.

Warum schrumpft die Schrittweite in der Regel mit der Zeit?

Die Verringerung der Schrittweite dämpft das Gradientenrauschen, wenn sich die Iterationen dem Optimum nähern, was die Robbins-Monro-Bedingungen für die Konvergenz erfordern. Eine zu große Schrittweite lässt die Schätzung um die Lösung herumschwanken.