BFGS vs L-BFGS - wie unterschiedlich sind sie wirklich?

7

Ich versuche, ein Optimierungsverfahren in Python mit BFGS und L-BFGS in Python zu implementieren, und erhalte in beiden Fällen überraschend unterschiedliche Ergebnisse. L-BFGS konvergiert superschnell zum richtigen Minimum, während BFGS sehr langsam konvergiert, und das auch zu einem unsinnigen Minimum.

FRAGE: Aus meinen Messwerten geht hervor, dass BFGS und L-BFGS im Grunde genommen der Algorithmus sind (Quasi-Newton-Methoden), außer dass letzterer weniger Speicher benötigt und daher schneller ist. Ist das wahr? Ansonsten, wenn sie unterschiedlicher sind, wie dann?

Letztendlich möchte ich herausfinden, ob der Leistungsunterschied auf einige Unterschiede in den tatsächlichen Algorithmen oder auf deren Implementierung in den Python-SciPy-Modulen zurückzuführen ist.

BEARBEITEN: Ich füge einige Daten hinzu, um meine Behauptungen zu unterstützen, dass sich das Verhalten von den beiden Algorithmen unterscheidet.

 RUNNING THE L-BFGS-B CODE

       * * *

Machine precision = 2.220D-16
N =          147     M =           10
This problem is unconstrained.

At X0         0 variables are exactly at the bounds
At iterate    0    f=  2.56421D+04    |proj g|=  1.19078D+03
At iterate    1    f=  2.12904D+04    |proj g|=  1.04402D+03
At iterate    2    f=  1.49651D+03    |proj g|=  2.13394D+02
At iterate    3    f=  6.08288D+02    |proj g|=  9.85720D+01
At iterate    4    f=  2.91810D+02    |proj g|=  6.23062D+01
...
At iterate  142    f=  3.27609D+00    |proj g|=  8.80170D-04
Time taken for minimisation: 36.3749790192


*** BFGS code ***

At iterate    1,  f= 21249.561722 
At iterate    2,  f= 15710.435098 
At iterate    3,  f= 15443.836262 
At iterate    4,  f= 15386.035398 
At iterate    5,  f= 15311.242917 
At iterate    6,  f= 15211.986938 
At iterate    7,  f= 15022.632266
...
At iterate  524,  f= 67.898495
...
Warning: Desired error not necessarily achieved due to precision loss.
Iterations: 1239
Time taken: 340.728140116
optimization ap21
quelle
L-BFGS ist buchstäblich eine Annäherung an BFGS, die weniger Speicher benötigt. Sie können also erwarten, dass es langsamer konvergiert. Da es sich jedoch in gewissem Sinne um Annäherungen handelt, ist es möglich, dass L-BFGS für Ihre spezielle Eingabe „Glück“ hat. Eine weitere Option ist, dass Ihr Computer beim Ausführen von BFGS einen schwerwiegenden Speicherengpass aufweist, nicht jedoch bei L-BFGS. Wenn also keiner der Algorithmen ein seltsames Verhalten unabhängig voneinander aufweist, fehlen Ihnen einfach Daten, um zu behaupten, dass eine bestimmte Implementierung schlechter als die andere ist.
Diskrete Eidechse
@Discretelizard, ich habe einige Daten geteilt, die zeigen, wie sich BFGS und LBFGS für meine Funktion ab einem Anfangszustand entwickeln. Beachten Sie, wie der Funktionswert für LBFGS innerhalb weniger Iterationen um eine Größenordnung abnimmt, für BFGS jedoch nur geringfügig abfällt. Meine Frage ist im Grunde, warum es eine so große Diskrepanz im Suchverhalten geben könnte / sollte.
21.
Nun, beide nähern sich dem „besten Weg“, um ein Optimum zu finden, sodass sich ihre Leistung in einer großen Anzahl von Datensätzen unterscheiden kann. Um eine genaue Antwort zu erhalten, können Sie überprüfen, ob / warum die Methode von L-BFGS für diese bestimmte Funktion einen viel besseren Gradientenabstiegsschritt ergibt. Ich denke, eine Visualisierung des Lösungsraums, die den "Pfad" beider Methoden zeigt, wäre nützlich, um eine Vorstellung davon zu bekommen, was los ist.
Diskrete Eidechse
1
Erwägen Sie die Verwendung eines Lösungsraums mit niedrigeren Dimensionen. Wenn Sie wirklich am Verhalten dieser Algorithmen in Ihrer spezifischen Funktion interessiert sind, müssen Sie die Details der Funktion (z. B. ist die Funktion konvex, polynomisch, linear, diskontinuierlich usw.) und des Lösungsraums (Ist es) wirklich verwendenR.n, eine konvexe Menge, ein Polyeder usw.), da ich bezweifle, dass eine allgemeine Bedingung für die relative Qualität dieser Methoden für beliebige Funktionen besteht.
Diskrete Eidechse
2
Nein, das ist das Gegenteil von dem, was ich sage. BFGS und LBFGS können theoretisch zu völlig unterschiedlichen Lösungen (wenn es mehrere lokale Minima gibt) mit unterschiedlichen Konvergenzgeschwindigkeiten konvergieren, je nachdem, wie Sie die Funktion und den Lösungsraum auswählen. Wenn Sie also behaupten möchten, dass die Implementierung Einschränkungen aufweist, sollten Sie eine große Anzahl verschiedener Funktionen und Lösungsbereiche testen.
Diskrete Eidechse

Antworten:

2

Nein, sie sind nicht gleich. In gewissem Sinne ist L-BFGS eine Annäherung an BFGS, die viel weniger Speicher benötigt. BFGS und L-BFGS werden in vielen Standardressourcen ausführlich erläutert.

Sehr grob kann man sich den Unterschied so vorstellen. BFGS berechnet und speichert das vollständige HessischeH.bei jedem Schritt; dafür braucht manΘ(n2) Raum, wo nZählt die Anzahl der Variablen (Dimensionen), über die Sie optimieren. L-BFGS berechnet und speichert eine Annäherung an das Hessische, die so gewählt wurde, dass die Annäherung in gespeichert werden kannΘ(n)Platz. Tatsächlich verwendet L-BFGS die NäherungH.≈M.⊤M. für einige k×n Matrix M. (Ich glaube).

Jeder Schritt von L-BFGS ist ein Versuch, zu approximieren / zu erraten, was der entsprechende Schritt von BFGS tun würde. Ein einzelner Schritt von L-BFGS benötigt jedoch viel weniger Platz und Zeit als ein einzelner Schritt von BFGS. Folglich können Sie innerhalb einer bestimmten Zeit viel mehr Schritte von L-BFGS ausführen als von BFGS. Daher stellen Sie möglicherweise fest, dass L-BFGS schneller konvergiert, da es innerhalb einer bestimmten Zeit so viel mehr Iterationen ausführen kann als BFGS.

Ich weiß nicht, was ein unsinniges Minimum bedeutet oder warum BFGS zu etwas Schlimmerem als L-BFGS konvergieren würde, wenn beide unbegrenzt laufen könnten.

DW
quelle
Bitte schauen Sie sich die folgenden Links an. Das unsinnige Minimum von BFGS - plot.ly/~apal90/162 - und das gute Minimum (ein Zylinder) von LBFGS - plot.ly/~apal90/160 .
21.
Was Sie sagen ist, dass BFGS und LBFGS theoretisch zu derselben Lösung konvergieren sollten, vorerst keine Barriere, oder? Dann schauen wir uns wirklich die Einschränkungen der Implementierung von Algorithmen in SciPy an, oder?
21.
L-BFGS funktioniert in dieser Instanz auch bei gleicher Anzahl von Iterationen besser. Daher erklärt L-BFGS mit schnelleren Iterationen den Unterschied hier nicht.
Diskrete Eidechse
1
@Discretelizard, du hast ganz recht. Die detaillierten Informationen zu den beiden Läufen waren nicht verfügbar, als ich meine Antwort schrieb, also habe ich geraten - und es sieht so aus, als ob meine Vermutung nicht korrekt war. Ich weiß nicht, warum ap21 das in der Frage aufgeführte Verhalten sieht. Hoffentlich kann jemand anderes eine bessere Antwort geben.
DW