どうやらあなたは、ユークリッド単位球内に留まるという制約のもとで、凸関数上の勾配流の経路がどれだけ長くなり得るか、という問題についてお聞きのようですね。
^ この問題は、私がここ2年間、AI の進歩をテストするために使ってきたものです。問題文は驚くほどシンプルですが、解くのは非常に困難です。GPT-5.6 は 168 分の思考時間を経て、この問題に関する公開されている SOTA を大幅に上回る結果を出しました。これは、これまで他のどのモデルも成し遂げられなかったことです。しかし、話が先走りました。まずはこの問題について少し考え、関連文献をレビューし、その後で o3 から GPT-5.6 への進歩について議論しましょう。
1. SOTA（最先端）
単純に考えると、「勾配降下法には次元に依存しない収束率がある―だからこそ多パラメータ問題に使うのが魅力的なのだ！―だから、おそらくそのような流れの長さも次元に依存しないのではないか？」と言うかもしれません。しかし、単純な考えは大間違いであることがあります。そもそも、そのような曲線は長さが有限である（次元依存性はさておき）と言えるのでしょうか？ それを証明するだけでも容易ではなく、実際、ネステロフの加速勾配降下法ではそれは偽です（ @ErnestRyu による この論文 、すべて GPT-5.5 で行われた研究を参照）。
では、この問題について正確に何が分かっているのでしょうか？ 1991 年に Manselli と Pucci による素晴らしい論文があり、そのような曲線は確かに長さが有限であり、さらにその長さは最大でも n^O(n) であることを示しています。そうです、お読みの通り、次元に関して指数関数的よりもさらに悪い、それが 35 年前の最良の上限です！！ ちなみに、この論文は、そのような曲線が「自己収縮性（self-contracted）」と呼ばれる性質を持つことも指摘しています。つまり、曲線上の任意の点を時刻 t に取ると、dist(x(s), x(t)) は s < t に対して非増加であるということです（下図参照）。
では、下界、つまり実際に長い自己収縮曲線を構成する場合はどうでしょうか？ 凸最適化の文献でよく見られるのは、悪条件の二次形式、例えば x_1^2 + 大きな定数 x_2^2 + さらに大きな定数 x_3^2 + ... のようなものです。要点は、勾配降下法はまず最大の定数を持つ方向に沿ってほぼ真っ直ぐ進み、次に二番目に大きな定数を持つ方向に進み、以下同様に進むということです（下図参照）。したがって、経路の全長はおおよそ n になり、経路は半径 sqrt(n) の球に含まれる超立方体に含まれるため、スケーリングし直すと sqrt(n) の長さの自己収縮曲線が得られます。
以上です。これが公表されている SOTA です：上限が n^O(n)、下限が sqrt(n)。これほど単純で自然な問題に対して、なんと大きなギャップでしょう！！！
自己収縮曲線の定義
sqrt(n) の長さの自己収縮曲線
2. 人間による未発表の研究
私は 8 年前に、素晴らしい共同研究者である Omer Angel、Tomas Merchan Rodriguez、Fedja Nazarov とこの問題について考えました。私たちはかなりの進歩を遂げ、答えが実際に次元に関して指数関数的であることを証明しました！ 具体的には、sqrt(2)^n の下界と 4^n の上界を得ました。これらの推定値を含む論文はきちんと書かれており、私の Dropbox フォルダに 10 年近く置かれています。その理由の一つは、これらの境界がさらに改善できると分かっていたからです。そして実際、Tomas と Fedja はさらに進歩し、まず下界を 2^n に押し上げ、上界も 2.29...^n に改善しました。ちなみに、私自身のこの問題に対する理解は、sqrt(2)^n を少し上回る下界と 4^n の上界にとどまっていました（実際、AI がこの問題で進歩を見せるまで、2^n と 2.29^n のことは忘れていました... 詳細は後述）。
3. AI の進歩
o3 は、この問題を「理解」した最初の AI モデルでした。そうです、その一文を正しくお読みいただいています。もしかすると忘れているかもしれませんが、2 年前には、AI がこのような一見単純な問題を「理解」できるかどうかさえ明らかではなく、ましてや解決できるかどうかはなおさらでした。特に o3 は、この問題が実際には自己収縮曲線に関するものであることを理解し、この問題の SOTA が何であるかを知っていました。当時、私は非常に感銘を受けました。
しかしその後、状況は複雑になり、GPT-5 シリーズのモデルの登場に伴い、私はこの問題を「戒めの話」として使うようになりました。つい最近の今年 2 月でも、私は講演で LLM の数学的進歩について話す際に、この問題を「LLM に尋ねるべきではない問題」の例として挙げていました。その理由は、GPT-5 や GPT-5.2/5.4 でさえ複雑な回答をしようと試みるものの、どこかで必ず間違えており、そのチェックに多くの時間を費やすことになるからです。そのため、LLM との数学的なやり取りで時間を無駄にしないためには、適切なレベルの質問を知っておくべきだという良い例でした。
この状況が変わったのは GPT-5.5 からです。そして、多くのやり取りと専門家によるプロンプトを経て、Mark Sellke は 2^n の下界構成を再発見することができました（私はこれに非常に驚きました。その理由の一つは、Tomer と Fedja がすでにそれを知っていたことを忘れていたからです 😅）。一方、上界については全く進展がありませんでした。
そして今、GPT-5.6 が登場し、AI の進歩が完全に明らかになりました：
- GPT-5.6-pro は 2^n の下界をワンショットで解きました。そのワンショットはこちらでご覧いただけます（80 分の思考時間）：https://chatgpt.com/s/t_6a50cb2a29488191b643ecb2426df87d
- GPT-5.6-pro は 4^n の上界もワンショットで解き、実際にはその CoT の中で非常に迅速にそれを導き出し、思考の終わりまでに 2.31...^n の上界を生成しました。Fedja の 2.29...^n には完全には及びません（実際、2.31...^n の戦略は新しいアイデアなしではこれ以上改善できません。実際、Fedja 自身も 2018 年の MathOverflow の投稿 で次のように述べています：「[2.31.. については] 議論はやや複雑になり、この方法では最適な推定値に到達できないことは明らかである」）。しかし、それでも非常に印象的であり、私がこの問題に真剣に取り組んでいた当時に個人的に理解していた範囲を超えています。このワンショットは、88 分の思考時間で行われたもので、こちらでご覧いただけます：https://chatgpt.com/share/6a50764e-3eec-83ea-97e6-3d1f30c07b64
3. 未来への挑戦
この話では、現在もまだ人間が勝者です。人間が 2.29 に対して、機械が 2.31 です。当然、予想としては、自己収縮曲線は 2^n より長くなることはない（そうなれば、2^n の下界を考えると最適な答えとなる）というものです。これは証明するのが非常に難しく、GPT-5.6 の能力を超えているように思われます。この問題を AI の進歩を追跡するために、あとどれくらい使えるでしょうか？ おそらく 6 ヶ月も経たないうちに超えられるのではないかと疑っています...
追記：上記の投稿を ChatGPT ワークスペースにコピーペーストし、それに合わせた図を作成するよう依頼しました。ここにある画像のコレクションは、そのクエリからワンショットで得られたものです。
