AlphaEvolveが行列乗算指数の上界を2.371177まで改善

導入

行列乗算は線形代数の基本操作ですが、その計算量を漸近的にどこまで削減できるかは、理論計算機科学で長く研究されてきた問題です。行列乗算指数 ω は、サイズがおよそ n の正方行列同士を掛けるために必要な計算量を、概ね n^ω と表したときの指数です。値が小さいほど、漸近的には効率のよいアルゴリズムを意味します。ただし、これは特定のGPUやライブラリの実測性能を直接表す数値ではありません。

DeepMindの研究者らを含むチームは、この指数の既知の上界をさらに改善したと報告しました。新しい上界は ω < 2.371177 で、従来の2.371339を下回ります。焦点は、一般的な行列乗算ソフトウェアの高速化ではなく、レーザー法の現代的な改良に組み込まれた最適化問題です。

主なポイント

• 組合せ損失解析を対象にする。 近年の最良クラスの上界は、レーザー法を発展させた組合せ損失解析に基づいています。この手法では、代数的な構成だけでなく、結果の強さを左右する難しい最適化問題を解く必要があります。
• 問題を再定式化した。 研究チームは中心的な最適化問題を書き換え、従来より広い設定で解けるようにしました。これにより、探索できる候補の範囲が広がります。
• 機械学習の最適化技術を利用した。 近年の機械学習から着想を得た新しい最適化アルゴリズムを設計しました。ここでAIモデルを行列乗算用に学習したという意味ではなく、数学的なアルゴリズム探索に現代的な最適化手法を適用したという意味です。
• AlphaEvolveで結果を精密化した。 新しい最適化アルゴリズムの結果を、さらにAlphaEvolveで改良しました。問題の再構成、探索、そして自動的な精密化を連続させる構成です。

意義と限界

2.371339から2.371177への差は小さく見えます。しかし行列乗算指数の研究では、すでに高度に最適化された理論上の境界をさらに動かすこと自体が難題です。新しい上界には、複雑な構成を見つける探索と、それが必要な条件を満たすことを示す厳密な議論が関わります。そのため、この成果の主な価値は、日常の行列処理が直ちに同じ倍率で高速化することではなく、自動化された最適化が基礎アルゴリズム研究に貢献できる点にあります。

また、この上界は現在のライブラリがn^2.371177で動作することを意味しません。あくまで、行列乗算の漸近的な理論限界に関する主張です。古典的な代数手法と機械学習由来の最適化、さらに自動探索を組み合わせる流れが、今後ほかの問題にも広がるかは、今回の素材だけでは判断できません。それでも、本研究はAI支援による理論アルゴリズム発見の具体例となっています。

出典：Hugging Face Daily Papers