🤖 machine learning

Improving the matrix multiplication exponent with modern optimization and AlphaEvolve

本論文は、基礎となる最適化問題を再定式化し、現代的な機械学習技術とAlphaEvolveを用いて解法プロセスを強化することにより、行列乗算指数 $\omega$ の上界を2.371177未満へと改善するものである。

原著者： Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii, Abbas Mehrabian, Francisco J. R. Ruiz, Abigail See, Renfei Zhou, Josh Alman, Virginia Vassilevska Williams, Matej Balog

公開日 2026-08-18

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii, Abbas Mehrabian, Francisco J. R. Ruiz, Abigail See, Renfei Zhou, Josh Alman, Virginia Vassilevska Williams, Matej Balog

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

コンピュータサイエンスの広大な領域において、2つの巨大な数値の格子（グリッド）を掛け合わせる、行列乗算として知られる操作ほど基礎的なものはほとんどありません。この数学的タスクは、人工知能モデルの学習からビデオゲームにおけるリアルな画像のレンダリングに至るまで、あらゆる事象の根底を支えています。数十年にわたり、科学者たちはこの操作が標準的な単純な手法よりも速く実行できることを知ってきましたが、それが一体どこまで速くなり得るのかという正確な限界は、この分野における最も手強い謎の一つであり続けてきました。この限界は、格子のサイズが増大するにつれて計算に要する時間がどのように増大するかを規定する、単一の数、すなわち数学的な指数によって記述されます。この数値が小さければ小さいほど、コンピュータはより効率的になります。理論的な最小値は少なくとも2であることは分かっていますが、これまで証明されている最良の上限値は長年2.37をわずかに上回る付近を推移しており、研究者たちはますます洗練された数学的ツールを用いて、その障壁を少しずつ削り取ってきました。

Google DeepMindの研究チームは、複数の大学の共同研究者と共に、この境界をさらにわずかに押し広げました。現代的な最適化技術と新しい形態の人工知能を組み合わせることで、彼らは新たな記録を樹立し、指数を2.371177未満に下げられることを証明しました。これは数値としては小さな変化ですが、この特定の問題の文脈においては、重要な前進を意味します。2025年に達成された前回の最良の結果は2.371339でした。今回の発見は、究極の謎である正確な限界を解明したわけでも、コンピュータによる行列乗算の実践的な方法を即座に変えるものでもありませんが、理論的な制約を強め、天井が以前考えられていたよりも低いことを示しました。

この新記録への道のりは、行列乗算のより高速なアルゴリズムを間接的に設計するために40年前に開発された「レーザー法（laser method）」と呼ばれる数学的枠組みから始まりました。この手法の最新の洗練版である「結合損失解析（combination loss analysis）」は、巨大で複雑な最適化問題を解くことに依存しています。この問題は、大きな数学的構造をより小さな断片へと分解する最善の方法を見つけることを含みます。研究者たちは、この問題の難易度が、分解の深さを表すパラメータに依存することを発見しました。これまでの試みは深さ3で止まっており、それが調整可能な変数の数を制限していました。新しいチームは、この深さを4に増やすことで、より広い可能性の空間を探索できることに気づきましたが、それを行うには、過去に使用された従来のアルゴリズムでは処理するにはあまりにも巨大な、数百万の変数を持つ問題を解く必要がありました。

この規模に対処するため、研究者たちは機械学習から借用した技術を導入しました。標準的な数学的ソルバーを使用する代わりに、彼らは問題を、ニューラルネットワークの訓練によく用いられる手法である勾配降下法で扱えるように再定式化しました。このアプローチにより、彼らは強力なコンピュータハードウェアを使用してデータを並列処理し、深い分解に伴う複雑性の爆発を処理することが可能になりました。彼らは数学的な変数を、学習モデルにおける調整可能な重みのように扱い、それらを反復的に洗練させることで、より優れた解を見つけ出しました。この戦略の転換だけで、境界値を測定可能な量だけ改善することに成功し、現代の計算ツールが、かつての手法が見逃していた潜在能力を解き放てることを実証しました。

しかし、チームはそこで立ち止まりませんでした。彼らは、自らのコードを書き、改良するように設計された人工知能である「AlphaEvolve」を採用しました。単に最適化アルゴリズムを実行するだけでなく、AIにアルゴリズム自体を修正させたのです。システムは新しいバージョンのコードを生成し、それがどのような境界値を生み出すかを確認し、その後、その境界値を最小化するようにコードをさらに進化させました。この自己改善のプロセスにより、研究者たちは、人間のチームが見落としたかもしれない最適化戦略の微細な洗練を見つけ出すことができました。この自動化された進化の結果、さらなる改善が得られ、境界値は新たな記録である2.371177へと押し下げられました。

この結果がコンピュータの丸め誤差や浮動小数点数の不正確さによる産物ではないことを確実にするため、チームは厳格な検証ステップを実施しました。彼らはアルゴリズムによって見出された解を取り出し、すべての数値を正確な分数に変換して、完全な精度で最終的な計算を行いました。また、方程式内のすべての対数を、制約が満たされることを保証する安全な有理数の境界に置き換えました。この入念な認証プロセスにより、新しい境界値が数学的に妥当であり、複雑な計算にしばしば伴う数値的なノイズから自由であることが確認されました。

研究者たちは、彼らのアプローチがより良い境界値をもたらした一方で、改善を得ることがますます困難になっていると指摘しています。彼らが達成した利得は、過去40年間に見られた漸進的な進歩の規模に匹敵するものです。彼らは、これらの最適化技術を洗練し続けることでさらなる緩やかな改善は可能かもしれないものの、真の限界に対する理解を大幅に飛躍させるには、全く新しい数学的アイデアが必要になるであろうと考えています。現時点において、この研究は、深い理論数学と現代の機械学習の計算能力を組み合わせる力の証となっており、長い歴史を持つ分野であっても、依然として発見の余地があることを証明しています。

技術要約：現代的な最適化とAlphaEvolveによる行列乗算指数の改善

問題提起
$n \times n$ 行列を $O(n^{\omega + o(1)})$ 回の演算で乗算できることを示す、行列乗算の計算量特性としての指数 $\omega$ の決定は、理論計算機科学における未解決の根本的な問題である。Strassenによる1969年の画期的な成果が $\omega < 2.81$ を確立して以来、現在の最良の上界は $\omega < 2.371339$ (Alman et al., 2025) である。この上界は、「レーザー法」の洗練版である**結合損失解析（combination loss analysis）**から導出されている。このアプローチの中核は、複雑な非凸最適化問題を解くことにある。困難な点は、最適化の複雑さ（再帰レベル $\ell^*$ に対して二重指数関数的に増大する）と、得られる境界のタイトさとの間のトレードオフにある。従来の最先端（SOTA）の結果は、約25,000個のパラメータを含む再帰レベル $\ell^* = 3$ で達成されていた。

手法
著者らは、より高い再帰レベル $\ell^* = 4$ をターゲットとして、結合損失解析の最適化プロセスを改善するための2段階のアプローチを提案している。

定式化と勾配ベースの最適化:
- 問題の拡張: 著者らは、 $\ell^* = 4$ を扱うために最適化問題を再定式化した。これにより、最適化可能なパラメータ数は約25kから約700万へと増加した。
- 微分可能な目的関数: この高次元の非凸問題を解くため、従来の研究で使用されていた逐次二次計画法（SQP）から脱却し、勾配ベースのアプローチを採用している。
- パラメータ化: 確率が非負であり、かつ和が1であるという制約を扱うため、分布をロジット経由でパラメータ化し、ソフトマックス関数を用いて変換することで、無制約最適化を可能にした。
- 最大エントロピーの扱い: この問題には、周辺制約の下での最大エントロピー分布（ $H_{max}$ ）の計算が含まれる。これらの分布を直接最適化するのではなく、著者らは（最適輸送論からの）Sinkhorn-Knoppアルゴリズムを利用してこれらを計算している。また、このアルゴリズムを通じてバックプロパゲーションを行うために、暗黙微分（implicit differentiation）を用いており、これにより目的関数が微分可能かつ安定であることを保証している。
- 実装: アルゴリズムは、ハードウェアの並列化を活用するために Jax で実装されている。最適化ツリーの非一様なグラフ構造を管理するため、「ファントムノード（phantom nodes）」を導入してマスキングを行い、ノードを特定の「ステージ」にクラスター化することで、問題を効率的な並列処理のための多次元テンソルとして表現できるようにしている。
AlphaEvolveの統合:
- 著者らは、最適化アルゴリズムをさらに洗練させるために AlphaEvolve (Novikov et al., 2025) を適用している。
- AlphaEvolveは、最適化プログラム自体を修正する。「進化する構成（evolving constructions）」機能を使用し、各世代のアルゴリズムは親アルゴリズムが見つけた最良の解点から開始され、結果として得られる $\omega$ の境界を最小化するようにコードを反復的に進化させる。
厳密な検証:
- 浮動小数点誤差による影響を受けないことを保証するため、著者らは別途の検証ステップを実施している。浮動小数点の解を有理数に丸め、すべての導出された量を厳密な有理演算を用いて再評価する。
- 対数については、最適化問題のすべての制約が満たされることを保証する方向に丸められた有理数の範囲に置き換えられ、最適化問題の境界に対する数学的に厳密な証明を提供している。

主な貢献と結果

新しい上界: 組み合わせたアプローチにより、新たな上界 $\omega < 2.371177$ が得られた。
改善の規模: これは、従来のSOTAである $\omega < 2.371339$ を約 $1.62 \times 10^{-4}$ 改善したものである。勾配ベースの最適化単体による改善は約 $0.97 \times 10^{-4}$ であり、残りの利得はAlphaEvolveによる洗練に起因する。
スケーラビリティ: 本研究は、標準的なSQP法ではパラメータ数の爆発により不可能であったスケールである $\ell^* = 4$ において、結合損失解析問題を解くことが可能であることを示している。

意義と主張
本論文は、この改善がCoppersmith-Winogradの境界（ $\omega < 2.376$ ）が確立されてからの過去40年間のほとんどの進展と同等の規模であると主張している。著者らは、彼らの貢献が、既存の数学的枠組みをより効果的に解くために、現代的な機械学習技術（勾配降下法、最適輸送、および進化的なコード生成）を活用したことにあると強調している。

著者らは将来の展望については控えめな姿勢を維持しており、このような最適化に焦点を当てた手法を通じてさらなる緩やかな改善は達成可能かもしれないが、 $\omega$ の大幅な減少を実現するには、現在のレーザー法の枠組みを超えた新しい数学的アイデアが必要になるであろうと述べている。本研究は、2025年秋のSimons Institute for the Theory of Computingにおける議論を契機としている。

関連論文