Stochastisches Gradientenverfahren und Mini-Batches

Den Gradienten aus wenigen Stichproben schätzen

Die meisten Anpassungsprobleme minimieren einen Mittelwert über Daten, $f(\mathbf w)=\frac1n\sum_{i=1}^{n}\ell_i(\mathbf w)$, etwa quadratische Fehler über $n$ Beobachtungen. Der exakte Gradient braucht in jedem Schritt alle $n$ Terme, was bei Millionen von Ticks zu langsam ist. Das stochastische Gradientenverfahren zieht einen zufälligen Mini-Batch $B$ aus $b$ Beobachtungen und nutzt stattdessen deren mittleren Gradienten $g_B$. Diese Schätzung ist erwartungstreu: Im Mittel gleicht sie dem wahren Gradienten.

Der Preis der Abkürzung ist Rauschen. Die Varianz des Batch-Gradienten fällt wie $1/b$, die Halbierung ihrer Standardabweichung braucht also einen viermal größeren Batch, ein stark abnehmender Ertrag. Eine Epoche ist ein voller Durchlauf durch die Daten und enthält $n/b$ Updates. Mit konstanter Schrittweite kommen die Iterierten nie zur Ruhe: Sie zittern weiter in einer kleinen Kugel um das Minimum, denn selbst im Minimum ist der Batch-Gradient nicht null. Abhilfe schafft eine schrumpfende Schrittweite. Die klassischen Robbins-Monro-Bedingungen verlangen $\sum_t\eta_t=\infty$, damit die Bewegung so weit reichen kann wie nötig, und $\sum_t\eta_t^{2}<\infty$, damit das Rauschen abklingt. Der Plan $\eta_t=\eta_0/t$ erfüllt beides.

• Erwartungstreu: Der Gradient eines zufälligen Batches gleicht im Mittel dem vollen Gradienten.
• Verrauscht: Varianz $\sigma^2/b$; ein vierfacher Batch halbiert die Standardabweichung.
• Schrumpfende Schritte: $\sum\eta_t=\infty$ und $\sum\eta_t^2<\infty$, z. B. $\eta_t=\eta_0/t$, sichern Konvergenz.

Lab: Was bewertet wird

• Der volle Gradient15 Pkt.
• Das Rauschen einer Stichprobe15 Pkt.
• Das Rauschen eines Batches15 Pkt.
• Updates pro Epoche15 Pkt.
• Ein konvergenter Schrittplan15 Pkt.
• Die Mini-Batch-Schleife10 Pkt.
• Warum eine konstante Schrittweite nicht zur Ruhe kommt15 Pkt.