Fallstricke der Nichtkonvexität und Neustarts

Wenn es mehr als ein Tal gibt

Die meisten interessanten Modelle sind nicht konvex. Ihre Zielfunktionen haben mehrere lokale Minima, Sattelpunkte und flache Plateaus, und das Gradientenverfahren rollt einfach in das Tal, in dem es startet. Nehmen Sie $f(x)=x^4-3x^2+x$. Ihre Ableitung $4x^3-6x+1$ verschwindet bei $x=-1.301$, $x=0.170$ und $x=1.131$. Das erste und das letzte sind Minima mit $f=-3.514$ und $f=-1.070$, das mittlere ist ein Hügel dazwischen. Der Abstieg mit kleiner Schrittweite von $x_0=2$ endet bei $1.131$, nur einem lokalen Minimum, von $x_0=-2$ bei $-1.301$, dem globalen. Zwei Starts so nah wie $x_0=0.1$ und $x_0=0.2$, beiderseits des Hügels bei $0.170$, enden in verschiedenen Tälern.

Sattelpunkte sind die andere Falle. Dort ist der Gradient null, aber die Hesse-Matrix hat Eigenwerte beider Vorzeichen, die Funktion fällt also in manchen Richtungen und steigt in anderen. In hohen Dimensionen sind die meisten stationären Punkte Sättel, und einfacher Gradientenabstieg kriecht in ihrer Nähe. Momentum, das Rauschen von Mini-Batches und Information zweiter Ordnung helfen beim Entkommen. Plateaus, auf denen der Gradient über ein weites Gebiet winzig ist, sehen nach Konvergenz aus, sind aber keine.

Das Standardmittel ist der Neustart. Führen Sie den Optimierer von $K$ verschiedenen Startpunkten aus und behalten Sie das Ergebnis mit dem niedrigsten Zielwert. Landet jeder Start unabhängig mit Wahrscheinlichkeit $p$ im globalen Tal, dann tut das mindestens einer von $K$ Starts mit Wahrscheinlichkeit $1-(1-p)^K$. Für $p=0.2$ und $K=10$ sind das $0.893$, und $99\%$ erfordern $K\ge\ln0.01/\ln0.8=20.6$, also 21 Starts. Auch bessere Startpunkte helfen: eine Lösung aus einer konvexen Relaxation, die Kalibrierung von gestern oder eine Gittersuche über die wenigen wichtigsten Parameter.

• Lokale Minima: Der Abstieg endet im Startal, der Start entscheidet also über die Antwort.
• Sättel und Plateaus: Nullgradient oder winziger Gradient ohne Minimum; Momentum und Rauschen helfen.
• Neustarts: $K$ Starts gelingen mit Wahrscheinlichkeit $1-(1-p)^K$; behalten Sie den besten Zielwert.

Lab: Was bewertet wird

• Der Wert des globalen Minimums15 Pkt.
• Start bei x = 215 Pkt.
• Zwei nahe Starts15 Pkt.
• Erfolg zufälliger Neustarts15 Pkt.
• Wie viele Neustarts15 Pkt.
• In der Nähe eines Sattelpunkts10 Pkt.
• Neustartergebnisse vergleichen15 Pkt.