技術的概要：ケーリー表の完成による幾何学的圧縮とアルゴリズム的圧縮の分離

1. 問題提起

本論文は、統計的学習理論（SLT）において幾何学的圧縮とアルゴリズム的圧縮の間に根本的な理論的断絶が存在することを特定している。

• 幾何学的圧縮: 現代の深層学習は、連続的な容量制御メカニズム（例えば、ノルムに基づく正則化、マージンの最大化、低ランクバイアス）に依存している。これらの手法は、簡潔な概念が滑らかな多様体または低次元の線形部分空間上に存在すると仮定している。連続データに対しては成功しているが、このパラダイムは、正確なアルゴリズム的または離散的代数規則の外挿には失敗する。
• アルゴリズム的圧縮: 古典的学習理論（PAC 学習、オッカムの剃刀、MDL）は、学習を正確で最小の論理規則の回復として捉えていた。しかし、離散的アルゴリズム的複雑性の最適化は一般的に NP 困難であり、その結果、現代の SLT はこれをほぼ放棄している。
• ギャップ: 深層学習にはアルゴリズム的複雑性の最小化に向けた帰納的バイアスが欠如している。その結果、ニューラルネットワークは、正確な離散代数構造を必要とするタスク（例えば、アルゴリズム的タスクにおける長さ一般化、正確な対称性の発見）に苦しみ、規則の抽象化ではなく、脆い記憶に頼る傾向がある。

本論文は、この欠落したバイアスを扱うための標準的なテストベッドとしてケーリー表の完成を提案する。このタスクは、部分的な観測から離散的二項演算（群または擬群構造）を回復するものであり、行列完成の離散的代数版として機能する。

2. 手法と理論的枠組み

標準的タスク：ケーリー表の完成

線形ランクが低いこと（行が線形従属であること）を求める行列完成とは異なり、群のケーリー表は、行が互いの置換であるラテン方格である。この構造は本質的に線形冗長性を排除する。代数群の真の簡潔さは、結合律の公理に由来し、これが構造記述長を最小化するように大域的構造を制約する。

作用素値テンソル分解

扱いにくい組み合わせ探索なしにこれを解決するため、本論文は Huh (2025) による最近の研究に基づいた連続的かつ微分可能なアプローチを利用する：

1. テンソル表現: 大きさ $n$ の有限集合 $Q$ 上の二項演算 $\circ$ は、構造テンソル $\delta \in \{0, 1\}^{n \times n \times n}$ で表現される。ここで、$a \circ b = c$ ならば $\delta_{abc} = 1$ である。
2. 分解モデル: テンソルは、作用素値分解を通じてモデル化される：
   $$T_{abc}(\Theta) := \frac{1}{n} \text{Tr}(A_a B_b C_c)$$
   ここで、$\Theta = (A, B, C)$ であり、$A_a, B_b, C_c$ は $n \times n$ 行列スライス（線形作用素）である。
3. 平坦性事前分布: 最適化目的関数には、経験的再構成損失のヘッシアン（Hessian）のトレースを罰則とする平坦性事前分布が含まれる：
   $$H(\Theta) := \text{Tr}\left(\nabla^2 \sum_{(a,b,c) \in \Omega} (T_{abc}(\Theta) - \delta_{abc})^2\right)$$

変分特性

目的関数 $H(\Theta)$ は、離散的性質を誘発する 2 つの重要な構成要素に分解される：

• 幾何学的整合性（共線性）: 結合律の公理を強制する。
• 逆 $\ell_2$ ペナルティ: 共線多様体内における正確な逆ランクペナルティとして機能する。

決定的なことに、このメカニズムはパラメータをフルランクのユニタリ性へと駆動し、標準的な幾何学的圧縮の低ランクバイアスと正反対の方向に向かわせる。

3. 主要な結果と証明

本論文は、提案された枠組みに基づき以下の理論的発見を提示する：

• 正確な回復限界: 完全観測の極限において、幾何学的下限 $H_{\inf}(\delta) := \inf_{T(\Theta)=\delta} H(\Theta)$ は、代数的複雑性の正確かつ微分可能な尺度であることが証明される。
• 下限: 目的関数は絶対的な下限 $H_{\inf}(\delta) \ge 3|\delta|$（ここで $|\delta| = n^2$）を確立する。
• 最小化子の特性: この限界は、必要十分条件として、対象とする演算が群と同位である場合に達成される。この場合、大域的最小化子は（ユニタリゲージまで）基礎となる群の正則表現を一意に特徴づける。
• 概念実証: これは、組み合わせ探索に頼ることなく、連続的な勾配ベースの最適化が離散的代数公理（特に結合律）をネイティブに発見できるという形式的証明を提供する。

4. 提起された未解決問題

本論文は、以下の 2 つの特定の未解決問題を通じて、幾何学的圧縮とアルゴリズム的圧縮の分離を形式化するようコミュニティに挑戦している：

1. 未解決問題 1（形式的分離）: 幾何学的容量制御（例えば、ラデマハ複雑性、マージン限界）とアルゴリズム的圧縮の間に厳密な分離定理を確立すること。純粋な幾何学的一般化限界が明らかに空虚（指数関数的なサンプル複雑性を要求）であり、微分可能なアルゴリズム的複雑性尺度が厳密な多項式保証をもたらすような仮説クラス（例えば、離散的代数規則）を特徴づけることが目標である。
2. 未解決問題 2（ケーリー表完成のサンプル複雑性）: 平坦性正則化されたテンソル分解に対する正確な回復保証を形式的に確立すること。具体的には、$O(n \log n)$ の一様サンプリングされたエントリのみが与えられた場合、大域的最小化者が高い確率で群表を完全に完成させることが証明できるか？これは、フルランク構造に対して $O(n^2)$ を超える空虚な限界をもたらす標準的な行列完成理論とは対照的である。

5. 意義と限界

意義

本論文は、ケーリー表完成問題の形式化と解決が以下の点で重要であると主張する：

• 古典的な論理駆動時代と現代の幾何学駆動時代の SLT の間に、厳密な数学的架け橋を提供する。
• 慎重に設計された純粋な連続事前分布が、勾配降下法に正確な組み合わせ性質をネイティブに最適化させることを示す概念実証となる。
• 幾何学的代理が失敗し、アルゴリズム的圧縮が成功する領域に関する SLT の決定的に欠落している基盤に対処する。

限界と現状

• 部分的な結果: 本論文は、存在証明やランドスケープ解析は存在するものの（Huh, 2025）、正確な理論的境界という基礎的な問いは未解決であることを認めている。
• ニューロシンボリックの限界: 現在のニューロシンボリックアプローチは、論理を近似確率に緩和して（剛体構造の回復に失敗）いるか、論理的制約を処理するために外部のシンボリックエンジンに依存して（ネイティブなアルゴリズム的発見の達成に失敗）いるとして批判されている。
• 範囲: 本論文は、理論的枠組みの確立と未解決問題の提起に焦点を当てている。本文書内でサンプル複雑性の限界（未解決問題 2）や一般的な分離定理（未解決問題 1）が解決されたとは主張しておらず、むしろこれらを分野にとって必要な次のステップとして位置づけている。