Das Gradientenabstiegsverfahren

Den Hang hinabgehen

Das Gradientenverfahren wiederholt eine einzige Bewegung: einen Schritt gegen den Gradienten, $\mathbf w_{k+1}=\mathbf w_k-\eta\,\nabla f(\mathbf w_k)$. Die Zahl $\eta>0$ ist die Schrittweite, oft Lernrate genannt. Ein kleines $\eta$ ist sicher, aber langsam. Ein großes $\eta$ schießt über das Tal hinaus, und die Iterierten können sich jedes Mal weiter entfernen.

Auf der einfachsten Schale multipliziert die Aktualisierung $w$ jedes Mal mit $1-\eta a$; die Iterierten gehen genau dann gegen null, wenn $|1-\eta a|<1$, also $\eta<2/a$. Die Wahl $\eta=1/a$ trifft das Minimum in einem Schritt, und jedes $\eta$ zwischen $1/a$ und $2/a$ konvergiert noch, wechselt aber unterwegs das Vorzeichen. Jenseits von $2/a$ ist der Betrag des Faktors größer als eins, und die Iterierten explodieren.

In mehreren Variablen hängt die Krümmung von der Richtung ab. Der größte Eigenwert $L$ der Hesse-Matrix begrenzt die nutzbare Schrittweite ($\eta<2/L$), der kleinste $\mu$ bestimmt, wie langsam die flachste Richtung durchquert wird. Ihr Verhältnis $\kappa=L/\mu$ ist die Konditionszahl. Mit der besten festen Schrittweite $\eta=2/(L+\mu)$ schrumpft der Fehler pro Schritt etwa um den Faktor $(\kappa-1)/(\kappa+1)$; ein großes $\kappa$ heißt also einen Faktor nahe eins und ein langsames Zickzack in einem langen schmalen Tal. Für die Kovarianzmatrix von zwölf großen US-Aktien seit 2010 ist $\kappa$ etwa $33$: Der Faktor ist $0.941$, und den Fehler auf ein Hundertstel zu senken braucht etwa 76 Schritte.

• Sichere Schrittweite: $\eta<2/L$, wobei $L$ der größte Eigenwert der Hesse-Matrix ist; sonst divergieren die Iterierten.
• Geschwindigkeit: bestimmt durch die Konditionszahl $\kappa=L/\mu$; je größer, desto langsamer der Abstieg.
• Abbruch: stoppen, wenn $\lVert\nabla f\rVert$ unter einer Toleranz liegt, mit einer Obergrenze für die Iterationen.

Lab: Was bewertet wird

• Der erste Schritt15 Pkt.
• Der zweite Schritt10 Pkt.
• Die größte stabile Schrittweite15 Pkt.
• Eine zu große Schrittweite15 Pkt.
• Eine Konditionszahl15 Pkt.
• Der beste Kontraktionsfaktor15 Pkt.
• Warum schlechte Kondition langsam ist15 Pkt.