Wie lang kann der Pfad eines Gradientenflusses auf einer konvexen Funktion sein, unter der Einschränkung, dass er innerhalb der euklidischen Einheitskugel in Dimension n bleibt?
^ das ist die Frage, die ich seit 2 Jahren verwende, um den Fortschritt der KI zu testen. Sie ist unheimlich einfach zu formulieren, aber teuflisch schwer zu lösen. In 168 Minuten Denkzeit konnte GPT-5.6 die veröffentlichte SOTA zu dieser Frage deutlich übertreffen, auf eine Weise, wie es keinem anderen Modell bisher gelungen ist. Aber ich greife vor, lassen Sie uns zuerst ein wenig über die Frage nachdenken, die Literatur durchgehen und dann diskutieren, wie der Fortschritt von o3 zu gpt-5.6 war.
1. SOTA
Naiverweise könnte man sagen: „Nun, Gradientenabstieg hat eine Konvergenzrate, die dimensionsfrei ist – weshalb es spannend ist, ihn für Probleme mit vielen Parametern zu verwenden! – also sollte die Länge eines solchen Flusses wahrscheinlich auch dimensionsfrei sein?“. Nun, manchmal können naive Ansätze völlig falsch liegen. Zunächst einmal: Sind solche Kurven überhaupt rektifizierbar (d.h. von endlicher Länge, ganz zu schweigen von der Dimensionsabhängigkeit)??? Selbst das ist nicht einfach zu beweisen, und tatsächlich ist es FALSCH für Nesterovs beschleunigten Gradientenabstieg (siehe diese Arbeit von @ErnestRyu, alles mit gpt-5.5 gemacht).
Okay, also was genau ist über diese Frage bekannt? Nun, es gibt eine wunderschöne Arbeit von Manselli und Pucci aus dem Jahr 1991, die zeigt, dass solche Kurven tatsächlich rektifizierbar sind, und ihre Länge ist höchstens n^O(n). Ja, Sie haben richtig gelesen, sogar schlimmer als exponentiell in der Dimension, das ist die beste Schranke von vor 35 Jahren!! Übrigens weist diese Arbeit auch darauf hin, dass solche Kurven das sind, was man „selbstkontrahierend“ nennt, d.h. sie kommen ihrem Verlauf immer näher (nehmen Sie einen beliebigen Punkt auf der Kurve zum Zeitpunkt t, dann ist dist(x(s), x(t)) für s<t nicht steigend; siehe Abbildung unten).
Was ist nun mit unteren Schranken, d.h. der Konstruktion einer tatsächlich langen selbstkontrahierenden Kurve? Ein Standardbeispiel aus der Literatur zur konvexen Optimierung wäre eine schlecht konditionierte quadratische Funktion, so etwas wie x_1^2 + große_Konstante\x_2^2 + noch_größere_Konstante\x_3^2 + ... Der Punkt ist, dass der Gradientenabstieg zuerst fast geradeaus in Richtung der größten Konstante geht, dann in die Richtung der zweitgrößten Konstante und so weiter (siehe Abbildung unten). Die Gesamtlänge des Pfades wird also ungefähr n sein, und der Pfad ist im Hyperwürfel enthalten, der wiederum in einer Kugel mit Radius sqrt(n) enthalten ist. Durch Reskalierung erhalten wir also eine selbstkontrahierende Kurve der Länge sqrt(n).
Das war’s. Das ist die veröffentlichte SOTA: obere Schranke von n^O(n) und untere Schranke von sqrt(n). Eine ziemliche Lücke für eine so einfache und natürliche Frage!!!
Definition einer selbstkontrahierenden Kurve
Eine selbstkontrahierende Kurve der Länge sqrt(n)
2. Unveröffentlichte Arbeit von Menschen
Ich habe vor 8 Jahren mit den großartigen Mitarbeitern Omer Angel, Tomas Merchan Rodriguez und Fedja Nazarov über diese Frage nachgedacht. Wir konnten ziemliche Fortschritte erzielen und feststellen, dass die Antwort tatsächlich exponentiell in der Dimension ist!! Genauer gesagt hatten wir eine untere Schranke von sqrt(2)^n und eine obere Schranke von 4^n. Die Arbeit mit diesen Schätzungen ist ordentlich geschrieben und liegt seit fast einem Jahrzehnt in meinem Dropbox-Ordner, unter anderem, weil wir wussten, dass diese Schranken weiter verbessert werden können. Und tatsächlich machten Tomas und Fedja weitere Fortschritte, indem sie zuerst die untere Schranke auf 2^n erhöhten und auch die obere Schranke auf 2.29...^n verbesserten. Beachten Sie, dass mein eigenes Verständnis des Problems auf der etwas besseren als sqrt(2)^n unteren Schranke und der 4^n oberen Schranke blieb (tatsächlich hatte ich die 2^n und die 2.29^n vergessen, bis die KI begann, Fortschritte zu machen … mehr dazu unten).
3. KI-Fortschritt
o3 war das erste KI-Modell, das die Frage überhaupt verstand. Ja, Sie haben diesen Satz richtig gelesen. Vielleicht haben Sie vergessen, dass vor zwei Jahren nicht einmal klar war, dass eine KI so trügerisch einfache Fragen VERSTEHEN kann, geschweige denn lösen. Insbesondere konnte o3 erkennen, dass es sich bei der Frage tatsächlich um selbstkontrahierende Kurven handelte, und kannte die SOTA zu dieser Frage. Ich war damals sehr, sehr beeindruckt.
Aber dann wurde es knifflig, und mit dem Erscheinen der GPT-5-Modellreihe verwendete ich diese Frage als warnendes Beispiel: Noch im Februar dieses Jahres habe ich diese Frage in Vorträgen über die Fortschritte von LLMs in der Mathematik als Beispiel für eine Frage verwendet, die man LLMs NICHT stellen sollte. Der Grund ist, dass GPT-5 oder sogar GPT-5.2/5.4 versuchen würden, komplizierte Antworten zu geben, die aber ausnahmslos irgendwo falsch waren, und man würde viel Zeit damit verschwenden, sie zu überprüfen. Es war also ein gutes Beispiel dafür, dass man, um keine Zeit mit LLMs in der Mathematik zu verschwenden, das richtige Niveau der Frage kennen sollte.
Dies änderte sich mit GPT-5.5, und plötzlich konnte Mark Sellke mit viel Hin und Her und fachkundiger Eingabeaufforderung die 2^n untere Schrankenkonstruktion wiederentdecken (worüber ich SCHOCKIERT war, unter anderem, weil ich vergessen hatte, dass Tomer und Fedja sie bereits kannten 😅). Andererseits hatte er bei der oberen Schranke überhaupt kein Glück.
Und nun kommt GPT-5.6, und der Fortschritt der KI wird vollständig sichtbar:
- GPT-5.6-pro liefert die 2^n untere Schranke mit einem EINZIGEN DURCHLAUF. Sie können den Einzeldurchlauf hier sehen (80 Minuten Denkzeit): https://chatgpt.com/s/t_6a50cb2a29488191b643ecb2426df87d
- GPT-5.6-pro liefert die 4^n obere Schranke mit einem EINZIGEN DURCHLAUF, und zwar sehr schnell in seiner Gedankenkette, und am Ende seines Denkens produziert es eine obere Schranke von 2.31...^n. Es erreicht nicht ganz Fedjas 2.29...^n (und tatsächlich kann die 2.31...^n-Strategie ohne neue Ideen nicht weiter verbessert werden – Fedja selbst bemerkte dies in einem MathOverflow-Beitrag im Jahr 2018: „[für 2.31..] wird das Argument etwas unübersichtlich und es ist klar, dass dieser Weg nicht zur optimalen Schätzung führt“). Trotzdem ziemlich beeindruckend und über das hinaus, was ich persönlich über das Problem verstanden hatte, als ich ernsthaft daran arbeitete. Sie können den Einzeldurchlauf hier sehen, erledigt in 88 Minuten Denkzeit: https://chatgpt.com/share/6a50764e-3eec-83ea-97e6-3d1f30c07b64
3. Eine Herausforderung für die Zukunft
Diese Geschichte hat derzeit immer noch den Menschen als Sieger. 2.29 für Menschen gegenüber 2.31 für Maschinen. Natürlich ist die Vermutung, dass selbstkontrahierende Kurven nicht länger als 2^n sein können (was dann die optimale Antwort angesichts der 2^n unteren Schranke wäre). Dies scheint sehr schwer zu beweisen zu sein und über die Fähigkeiten von GPT-5.6 hinauszugehen. Wie lange werde ich diese Frage noch verwenden können, um den Fortschritt der KI zu verfolgen? Ich vermute, es könnten weniger als 6 Monate sein …
PS: Ich habe den obigen Beitrag in ChatGPT Work kopiert und gebeten, Illustrationen dazu zu erstellen. Die Sammlung von Bildern hier wurde mit einem einzigen Durchlauf aus dieser Abfrage erhalten.
