How AI settled the complexity of the oldest SGD algorithm

物語：AIがいかにして90年前の数学のパズルを解いたか

1937年から棚に置かれたまま、埃をかぶっている数学の問題を想像してみてください。それは、巨大な連立方程式（複雑な問いに対して完璧な答えを見つけるための方法）を解くためのパズルです。この特定のメソッドは「カチャルツ・アルゴリズム」と呼ばれ、実はChatGPTやGeminiのような現代のAIを動かしている技術の「曽祖父」にあたります。

何十年もの間、数学者たちはこのアルゴリズムが機能することは知っていましたが、最悪のシナリオにおいて「正確にどれくらいの速さで」機能するかを証明することはできませんでした。それは、ニューヨークからロサンゼルスまでドライブできることは分かっているけれど、もし全ての信号が赤で、あらゆる渋滞に巻き込まれた場合に、正確に最大でどれくらいの時間がかかるかを計算できない車を持っているようなものです。

この論文は、2つの異なるAIモデル、GeminiとChatGPTがどのように協力して、この謎ついに解き明かし、アルゴリズムがどれほど速く収束するかを証明したかという物語です。

キャラクターとミッション

• アルゴリズム（カチャルツ法）： あなたが地図の上で隠された宝探しをしていると想像してください。正確な場所は分かりませんが、ヒントとなる手がかり（方程式）のリストを持っています。カチャルツ・アルゴリズムは、歩行者のようなものです。彼はステップごとに、ランダムに「一つの」手がかりを選び、その手がかりを満たす場所に向かって歩き、次にまた別のランダムな手がかりを選びます。時間が経つにつれ、歩行者は宝にどんどん近づいていきます。
• 謎： 歩行者は最終的に宝を見つけますが、数学者たちの間でその「速度」について議論がありました。歩行者は長い間、円を描いて彷徨い続ける（堂々巡りをする）可能性があるのでしょうか？ それとも、保証された速度制限があるのでしょうか？
• 人間の研究者： 二人の科学者（MichałとXiaoyu）は、昔ながらの人間による数学を用いてこれを解決しようとしました。彼らは惜しいところまで行きましたが、壁に突き当たりました。彼らは新しい視点が必要だと悟ったのです。
• AIチーム： 研究者たちはAIに目を向けました。彼らは単にAIに「解いて」と頼んだのではありません。代わりに、彼らは指揮者となり、2つのAIモデルが互いに会話できるようにしたのです。

「アハ体験」：アイデアのリレーレース

解決策は、一つのAIが単独で成し遂げたものではありませんでした。それは、二人の異なるランナーの間でバトンが渡されるリレーレースのように起こりました。

1. Geminiの洞察（関数解析学者）： 問題を解くよう求められたとき、Geminiは完全な証明を与えませんでした。その代わりに、奇妙で素晴らしい「つながり」を見出したのです。Geminiはこの数学の問題を見て、「これは単なる方程式の問題ではない。これは関数解析（具体的には「量子マルコフ半群」と呼ばれるもの）という分野の概念に似ている」と言いました。

   • 比喩： 壊れたエンジンを修理しようとしている整備者を想像してください。Geminiはギア（歯車）を見る代わりに、「このエンジンは、実は核原子炉と同じ物理原則で動いている」と言ったのです。それは、人間の研究者がこれまで見てこなかった、奇妙でハイレベルな結びつきでした。
   • 落とし穴： Geminiはそのつながりを正しく捉えましたが、それを証明することはできませんでした。Geminiが引用した数学論文には、必要としていた証明は実際には含まれていませんでした。それは、図書館の本を指差して「答えはここにある」と言っているものの、その本の中身は空っぽであるような状態でした。

2. ChatGPTの証明（初等的な解決者）： 人間の研究者たちは、Geminiのこの「奇妙なつながり」を受け取り、それをChatGPTに渡しました。彼らはこう尋ねました。「よし、もしこのつながりが正しいとしたら、基本的な数学を使ってこれを証明できるか？」

   • ChatGPTはその問題を見て、「これならできる」と言いました。ChatGPTはGeminiが言及した複雑で混乱を招くような専門用語は使いませんでした。代わりに、速度制限を証明するために、複素数（通常は高度な物理学や工学のために予約されている数学の一種）を用いた巧妙で初等的なトリックを用いました。
   • 比喩： もしGeminiが、遠くの山を指差して「宝はその頂の下にある」と言った人物だとしたら、ChatGPTは実際にその山に登り、穴を掘り、金を見つけた人物でした。

結果： 「最後のステップ」は速い

この論文は、ある特定のことを証明しています。カチャルツ・アルゴリズムは、私たちが期待していた通りに速い。

これらのアルゴリズムの世界には、答えを確認する方法が2つあります。

1. 平均： 歩行者が取ったすべてのステップを取り、それらを平均すると、良い答えが得られます。（これが速いことは既に分かっていました）。
2. 最後のステップ： 歩行者が最後に停止した場所だけを見ます。（これが謎でした）。

論文は、最後のステップも平均と同じくらい速いことを証明しています。歩行者は最後に「落ち着く」ために彷徨い回る必要はありません。最終的な位置は、すでに完璧な解となっているのです。

なぜこれが重要なのか（論文によれば）

• 円が閉じた： 現代のAIを訓練する最も古い既知のバージョンのアルゴリズム（SGD）が、現代のAIによって解かれました。
• 研究の新しい方法： この論文は単なる数学の話ではありません。人間とAIがいかに協力できるかを示すケーススタディです。人間は証明を書いたのではなく、AIが書きました。人間はただ、二つのAIの間の会話を促進しただけなのです。
• より大きな問題を解決する： この特定のパズルを解くことで、彼らはAIのトレーニングアルゴリズム全般がどれほど速く機能するかという、長年の広範な問いをも解決しました。

結論

この論文は、人間だけでは打ち砕くにはあまりにも頑固すぎた、90年前の数学のパズルの物語です。二つの異なるAIモデルを協力させ――一方は奇妙でハイレベルなつながりを見つけ、もう一方は実際の証明を構築する――することで、その謎はついに解明されました。結果として、この古典的なアルゴリズムの「最後のステップ」が完全に効率的であることが確認され、未来の科学研究の姿、すなわち、人間がAIを導き、AIが重労働を行うというパートナーシップの姿を私たちに示しています。