Koordinate vs. Gefälle

Ich habe mich gefragt, was die verschiedenen Anwendungsfälle für die beiden Algorithmen Koordinatensinkflug und Gradientensinkflug sind .

Ich weiß, dass der Koordinatenabstieg Probleme mit nicht glatten Funktionen hat, aber er wird in gängigen Algorithmen wie SVM und LASSO verwendet.

Gradientenabstieg wird jedoch meiner Meinung nach häufiger eingesetzt, insbesondere bei der Wiederbelebung von ANNs und für viele andere maschinelle Lernaufgaben.

Meine Frage ist: Welche Art von Problemen passt zum einen, aber nicht zum anderen, und was macht in dieser Hinsicht die Anpassung der Koordinatenabnahme für SVMs und LASSO, aber die Anpassung der Gradientenabnahme für ANNs aus?

Wie soll man bei der Auswahl eines Optimierungsalgorithmus zwischen beiden wählen?

Ich denke, es ist normalerweise eine Frage, wie einfach / leicht es ist, den Gradienten des glatten Teils der Funktion und / oder des proximalen Operators der Strafe zu berechnen.

Manchmal ist es viel einfacher, eine genaue Lösung des Problems für eine einzelne Variable (oder einen Block oder mehrere Variablen) zu finden, als sie für alle Variablen gleichzeitig auszuarbeiten. Ansonsten ist es einfach zu teuer, den Gradienten im Vergleich zu den einzelnen Ableitungen zu berechnen. Die Konvergenz der Koordinatenabsenkung ist die gleiche wie für ista, , wobei k die Anzahl der Iterationen ist, sie kann jedoch manchmal im Vergleich zu ISTA und FISTA besser sein, siehe z . B. http: //statweb.stanford. edu / ~ tibs / compare.txt .$1/k^2$$k$

Solche Dinge beeinflussen zum Beispiel die Wahl des Koordinatenabstiegs gegenüber ISTA / FISTA.

Beim Koordinatenabstieg wird jeweils ein Parameter aktualisiert , während beim Gradientenabstieg versucht wird, alle Parameter gleichzeitig zu aktualisieren.

Es ist schwer genau anzugeben , wann ein Algorithmus besser abschneidet als der andere. Ich war zum Beispiel sehr schockiert, als ich erfuhr, dass der Koordinatenabstieg für LASSO auf dem neuesten Stand der Technik war. Und ich war nicht der einzige; siehe Folie 17 .

Trotzdem gibt es einige Funktionen, die ein Problem anpassbarer machen können, um den Abstieg zu koordinieren:

(1) Schnelle bedingte Updates. Wenn das Problem aus irgendeinem Grund die Möglichkeit bietet, Parameter sehr schnell individuell zu optimieren, kann der Koordinatenabstieg dies nutzen. Beispielsweise kann es möglich sein, bestimmte Parameter nur unter Verwendung einer Teilmenge der Daten zu aktualisieren, wodurch die Rechenaufwendungen für diese Aktualisierungen erheblich reduziert werden. Ein anderer Fall ist, wenn für einen einzelnen Parameter eine geschlossene Lösung vorliegt, die von den Werten aller anderen Parameter abhängig ist.

(2) Relativ unabhängige Modi für Parameter. Wenn der optimale Wert eines Parameters völlig unabhängig von den anderen Parameterwerten ist, führt eine Runde des Koordinatenabstiegs zur Lösung (unter der Annahme, dass jede Koordinatenaktualisierung den aktuellen Modus findet). Wenn andererseits der Modus für einen bestimmten Parameter sehr stark von anderen Parameterwerten abhängt, ist es sehr wahrscheinlich, dass der Koordinatenabstieg mit sehr kleinen Aktualisierungen bei jeder Runde einsetzt.

Leider gilt für die meisten Probleme (2) nicht, so dass es selten vorkommt, dass der Koordinatenabstieg im Vergleich zu alternativen Algorithmen gut funktioniert. Ich glaube, der Grund für die gute Leistung von LASSO ist, dass es viele Tricks gibt, mit denen man Bedingung (1) umsetzen kann.

$\alpha$

Mir ist klar, dass dies eine alte Frage ist und einige sehr gute Antworten hat. Ich möchte einige praktische persönliche Erfahrungen teilen.

$k$

• Alle Wahrscheinlichkeiten müssen positiv sein.
• Alle Elemente der Wahrscheinlichkeitsmenge müssen eins ergeben

Das verlangt tatsächlich viel. Beim Gradientenabstieg wird üblicherweise mit Einschränkungen über eine Straffunktion umgegangen. Hier wird es nicht funktionieren. Sobald ein Wert gegen eine dieser Einschränkungen verstößt, führt Ihr Code in der Regel zu einer Art numerischem Fehler. Man muss sich also mit den Einschränkungen auseinandersetzen, indem man dem Optimierungsalgorithmus niemals erlaubt, diese zu durchlaufen.

Es gibt zahlreiche Transformationen, die Sie auf Ihr Problem anwenden können, um die Einschränkungen zu erfüllen und einen Gradientenabstieg zu ermöglichen. Wenn Sie jedoch nach dem einfachsten und faulsten Weg suchen, dies zu implementieren, ist der koordinierte Abstieg der richtige Weg:

$p_i$

• $p_i^{k+1} = p_i^{k} - \eta \frac{\partial J}{\partial p_i}$
• $p_i = \min(\max(p_i,0),1)$
• $\mathbf{P}^{j+1} = \mathbf{P}^j \cdot \frac{1}{\sum_{i=1}^n p_i}$

Für jemanden wie mich, der in Python arbeitet, bedeutet dies normalerweise, dass ich eine zusätzliche for-Schleife verwenden muss, die sich negativ auf die Leistung auswirkt. Beim Gefälle kann ich den leistungsoptimierten Numpy verwenden. Man kann damit eine sehr gute Geschwindigkeit erreichen, dies ist jedoch mit Koordinatenabstieg nicht erreichbar, so dass ich normalerweise eine Transformationstechnik verwende.

Die Schlussfolgerung ist also, dass der Koordinatenabstieg die einfachste Option ist, um mit sehr strengen Einschränkungen wie dem Ratenparameter in der Poisson-Verteilung umzugehen. Wenn es negativ wird, codieren Sie Beschwerden usw.

Ich hoffe das hat ein bisschen Einsicht hinzugefügt.