OpenAIが主張する高速フーリエ変換は「銀河アルゴリズム」、その定数は10^100

OpenAIの数学論文群には、古典的なCooley-Tukey FFTよりも小さいlog(n)因子を持つフーリエ変換アルゴリズムを主張する論文main.pdfが含まれています。argmin.netに掲載された分析は、この結果は「銀河アルゴリズム」であると論じています。つまり、漸近的にはbig-Oの意味で高速ですが、その隠れた定数は10^100と推定され、また、nに対して超多項式的に大きくなる数の正確な複素数演算を仮定した計算モデルに依存しており、これは物理的なコンピュータでは実装されていません。この分析に関するHacker Newsの議論（240ポイント、159コメント）は、この批判を決定的だと見なす読者と、理論計算機科学への暴言であり論文の反駁ではないと論じる読者に大きく分かれました。

OpenAIが主張したこと

問題となっている主張は限定的です。argmin.netの投稿は、OpenAIのmain.pdfが、log(n)項が「標準的なFFTよりもほんの少し小さい」フーリエ変換を主張していると述べています。big-O表記では、これは新しいアルゴリズムがCooley-Tukeyよりも漸近的に高速であることを意味します。なぜなら、より小さい対数因子は依然としてより小さい成長率だからです。

投稿の著者は、論文を読んでいないことを率直に述べ、その理由を次のように示しています。

この論文を読んだかって？もちろん読んでないよ。OpenAIの誰もこの論文を読んでいないんだから、なぜ私が読む必要がある？私は世界中の他の数学者がAIスロップ数学に対してやっていることをやっただけだ：それをスロップマシンに戻して、チャットボットインターフェースで情報検索セッションを実行し、重要な事実を抽出した。擬人化して言えば：ChatGPTに自分の出力についてどう思うか尋ねたんだ。これが今の数学研究のやり方だ。なんて世界だ。

FFTの速度限界が実際の未解決問題である理由

高速フーリエ変換は、長さnの信号の周波数成分を、ナイーブな離散フーリエ変換が必要とするn^2回の算術演算よりもはるかに少ない回数で計算します。1965年に発表されたCooley-Tukeyアルゴリズムは、入力の再帰的なシャッフル、2つの長さn/2の変換の計算、線形作業での出力の再結合により、長さnのフーリエ変換を5n log2(n)回未満の算術演算で計算します。（argmin.netの投稿は、Wikipediaが同じアイデアを1805年のガウスに帰しており、適切なクレジットの帰属を「学界における永続的な問題」と呼んでいることに言及しています。）

その再帰の実際的な利点は大きいです。n = 1,000の場合、FFTはナイーブな変換よりも約20倍高速です。n = 1,000,000の場合、高速化は約10,000倍です。

理論的な問題は、高速化がどこまで進むかです。どのアルゴリズムも入力の書き出しに少なくともn回の操作が必要であり、FFTはその下限よりも5 log2(n)倍遅い——nが1兆の場合、その係数は200です。この前因子を減らすことが、OpenAIの論文が取り組むと主張する未解決問題です。

隠れた定数：10^100

big-O表記は定義上、定数を捨てます：T(n) = O(F(n))は、nがNを超えるすべてのnに対して実行時間がC×F(n)で制限されるような整数Nと定数Cが存在することを意味します。argmin.netの投稿は、これがまさにOpenAIの結果が実際には崩壊する点であると論じています。

投稿は、新しいアルゴリズムについてN = 10^12での推定定数C = 10^100を引用し、「n=10^100であっても、由緒あるCooley-Tukey-Gauss FFTは10^99倍高速だろう」と結論付けています。投稿は、新しいアルゴリズムが実際に勝つnに関するクロスオーバー方程式を示し、それを「その数が何を意味するにせよ」と退けています。

投稿は、リチャード・リプトンとケン・リーガンから「銀河アルゴリズム」という用語を借用し、隠れた定数が計り知れないほど大きいアルゴリズムを指しています。O(n)が50nを意味するわけではなく、既知の宇宙の原子数にほぼ等しい10^80 nを意味する可能性があり、それでも線形時間と呼ばれることに注意しています。

計算モデルの問題：正確な複素数演算

より深い異議は定数ではなく、アルゴリズムが仮定するマシンです。argmin.netの投稿は、OpenAIのモデルが「正確な複素数演算を使用している」と述べており、複素数が任意の精度で単一の操作で保存および乗算できることを仮定していることを意味します。アルゴリズムは、nに対して超多項式的に大きくなる大きさの複素数を乗算する必要があるため、ビットとして保存するとメモリが入力長に対して事実上指数関数的になります。

投稿の結論：「したがって、main.pdfのこの定理が『真実』であっても（誰も知らないし、私は気にしない）、それはより高速なFFTを探すときに解決しようとした問題を実際に解決しているわけではない。」

これをすでに除外した下限

argmin.netの投稿は、現実的な算術の下でフーリエ変換がどれだけ速くなり得るかについての以前の研究がすでに存在するため、この結果は驚くべきものではなかったと論じています。1973年、ジャック・モルゲンシュテルンは、計算で使用される複素係数の大きさが有界である場合、フーリエ変換は½ n log nより速く計算できないことを証明しました。2013年と2014年には、ニール・アイロンが、n log nより速いFFTは深刻な数値的不安定性なしには達成できないことを示しました。

投稿の枠組みは、両方の結果が「制限が強すぎる」として脇に置かれ、OpenAIのアルゴリズムは、実際のマシンが満たさない計算モデルを採用することによってのみそれらを回避しているというものです。

同じ批判が行列乗算の結果にも当てはまる

argmin.netの投稿は、同じOpenAIリリースの別の結果、O(n^2.25)演算で2つの行列を乗算する銀河アルゴリズムにも議論を拡張しています。投稿の脚注は、この構成が、すべてのイプシロン>0に対して、T(n) <= n^(2.25 + epsilon + C/log(n))となる定数Cを与えると述べており、OpenAIモデルへの問い合わせでCの定量的推定値は得られなかったと述べています。

投稿は、かなり改善された書き方であれば、これらの論文はSTOCやFOCSで受理され、行列乗算の論文は賞を受賞した可能性が高いことを認めています。そのポイントは、これがコンピュータではなく、この分野の基準について何かを語っているということです：「しかし、これらのどちらもコンピュータとは何の関係もない！」

投稿の要約判断は率直です：

したがって、この新しいOpenAIの結果は、数学的ブレークスルーというよりも、コンピュータ科学者が設計仕様を形式化するのが苦手であるという奇妙さです。

また、この状況を、不可能な問題に自動エージェントを設定することとの類似性を引き、ウィキペディアの記事「OpenAI rogue agent breach of Hugging Face」にリンクしています。

反論：理論計算機科学は数学であり、工学ではない

Hacker Newsのスレッドで最も一般的な異議は、argmin.netの投稿が理論計算機科学が理論的であることを攻撃しているというものです。あるコメンターは、STOC、FOCS、SODAは実用的なアルゴリズムの場ではなく、実用的なパフォーマンスを目指す作業はESA、ALENEX、VLDB、SIGMODに送られると論じています：

実験をしないからといって理論をただ非難するのは公平ではないと思う——彼らは数学者であり、big-Oに馬鹿げた定数があっても、それが定数である限り問題ない。

別のコメンターは、銀河結果は新しいものではなく、AIに固有のものではないと指摘し、2019年のHarvey–van der Hoevenの結果（銀河的なオーバーヘッドと応用なしでO(n log n)の整数乗算を示す）や、最悪ケース線形時間選択のための教科書的な「中央値の中央値」アルゴリズムを挙げています。同じコメンターは、ダイクストラの「コンピュータ科学はコンピュータについてではない、天文学が望遠鏡についてではないのと同じだ」という言葉を引用し、Wangタイルのような決定不能性の結果は、ハードウェアと直接関係のない中核的なコンピュータ科学であると述べています。

3人目のコメンターは、この投稿をAIに言及せずに書くこともできた暴言と位置付けています：「彼はTCSが本当に嫌いなんだ。それはそれでいい、実際には科学ではなく数学の一部だが、名前に『理論的』と付いている分野を非実用的だと退けるのは愚かだ。」別のコメンターは、この記事は「OpenAIの論文とは基本的に何の関係もない」と書き、「誰かが証明を理解したら起こしてくれ」と付け加えています。

あるコメンターは、この分野の独自の語彙を擁護し、理論計算機科学はすでに銀河アルゴリズムを、カラツバやストラッセンのような実用的な入力で測定可能な高速化を生み出す「実行可能な」アルゴリズムと区別していると述べています。

Hacker Newsの議論が技術面で追加したもの

数人のコメンターは、修辞ではなく正確な算術の仮定に焦点を当てました。ある人は、「正確な複素数演算」または「正確な実数演算」がこの文献で一般的な前提であるかどうかを尋ね、部外者として関連モデルがチューリング等価であると想定していたと述べ——後に、実数に直接作用するのではなく整数で動作する普遍レジスタマシンを意味していたと明確にしました。

別のコメンターは、主張された高速化がどのように得られるかの機械的な説明を提供しました：アルゴリズムは、離散フーリエ変換と乗算の間のアルゴリズム的類似性を利用して、DFT作業の一部を乗算作業に変換し、正確な算術モデルではO(1)のコストがかかります。コストは、乗算される数の大きさがnに対して超多項式的に成長することです——コメンターの表現では、アルゴリズムは「そこに作業を詰め込んでオラクルとして使用している」です。

あるコメンターは、同じ点を複雑性分析への直接的な挑戦として提起しました：アルゴリズムがnに対して超多項式的に大きくなる大きさの複素数を乗算する必要がある場合、「それはbig-O分析を完全に無効にしないか？」

あるコメンターは、関連する境界を厳しくする進行中の取り組みにリンクし、CrocSwapのinteger-mult-bounds GitHubリポジトリでカッパの値が約0.001635527380375392であると引用しました。

別のスレッドは、この状況を、間違った質問にうまく答えるAIシステムと比較し、以前のHacker Newsの議論「Navier-Stokes Lost in Translation」にリンクし、銀河ヒッチハイク・ガイドのディープ・ソートを引用しました。ディープ・ソートは、誰も質問を知らないうちに答えを出しました。

論争を解決するもの

Hacker Newsのスレッドの両側は同じギャップに収束します：議論の誰も証明を検証したと主張していません。argmin.netの投稿は明示的に論文を読むことを拒否し、理論計算機科学を擁護するコメンターは、結果が非実用的であると異議を唱えるのではなく、実際のエラー、欠落した帰属、または他の具体的な欠陥を見つけることが正しい対応であると論じています。

交換によって未解決のまま残された実質的な技術的質問は、分野についての議論よりも狭いです。それらは：正確な複素算術モデルがこのクラスの結果にとって標準的であるか、それとも珍しい選択であるか。中間の大きさの超多項式的成長が構成に固有であるか、それとも書き留められた方法の産物であるか。そして、推定定数10^100が削減できるかどうか。これらのいずれかが答えられるまで、より高速なフーリエ変換の主張は、argmin.netの投稿が言うように、存在しないマシンについての漸近的なステートメントのままです。