技術要約：オンラインアルゴリズムは孤立したパーセプトロン解を見つけることはできない

1. 問題設定

本論文は、ランダムな制約充足問題（CSP）であるバイナリ・パーセプトロン問題を調査している。この問題の目的は、行列 $G$ の各成分が独立同一な標準ガウス分布に従うとき、$G\sigma \ge \kappa\sqrt{n}$ を成分ごとに満たす符号ベクトル $\sigma \in \{\pm 1\}^n$ を見つけることである。本問題は、固定された制約密度 $\alpha > 0$ に対して $m = \lfloor \alpha n \rfloor$ となる比例レジームにおいて研究される。

このモデルの決定的な特徴は、**強い凍結（strong freezing）である。すなわち、任意の $\alpha > 0$ に対して、ほとんどすべての解は孤立（isolated）**している。具体的には、高確率で、すべての解は他のどの解ともハミング距離 $\Omega(n)$ 離れている。この幾何学的特性は、効率的なアルゴリズムが解を見つけるのが困難であることを示唆している。なぜなら、局所探索を導くような「近くの」解が存在しないからである。

しかし、一つのパラドックスが存在する。効率的なアルゴリズム、特にオンラインアルゴリズム（行列 $G$ の列を一つずつ処理し、符号を不可逆的に割り当てるもの）は、特定の制約密度（例：$\kappa=0$ のときの $\alpha < 0.327$）において解を見つけることが知られている。中心となる問いは、これらの成功するオンラインアルゴリズムは、典型的な孤立した解を見つけているのか、それとも稀に存在する、よく結合された解のクラスターを見つけているのか？ という点である。

2. 手法および証明戦略

著者らは、オンラインアルゴリズムが孤立した解を定数確率で（すなわち、成功確率が $n \to \infty$ で消失することなく）見つけることはできないことを証明する。証明は、主に以下の3つの技術的段階で進められる。

A. 決定論的アルゴリズムへの帰着

著者らは、任意のランダム化されたオンラインアルゴリズムは、平均化の議論を通じて解析可能であると最初に指摘する。したがって、現在の列 $g_t$、列の履歴、および以前に割り当てられた符号の関数として、ステップ $t$ における符号 $\sigma_t$ が決まる決定論的オンラインアルゴリズムを考えるだけで十分である。

B. 「学習停止」補題（サフィックス・パラレル・ベースライン）

核心となる洞察は、もしオンラインアルゴリズムが$h$-孤立解（ここで $h = \omega(\log^4 n)$）を出力する場合、そのアルゴリズムはプロセスの終盤で実質的に「学習を停止」しなければならないということである。

• 論理: もしアルゴリズムが孤立した解を出力する場合、最後の $r$ 個の符号（ここで $r < h$）は、解のプレフィックス（接頭辞）によって一意に決定されていなければならない。もしアルゴリズムが依然として「学習中」（すなわち、残りの列の特定の順序に基づいて決定ルールを変更している状態）であれば、非一意な補完を出力してしまうリスクがあり、それは孤立性を損なうことになる。
• 構成: 著者らは、サフィックス・パラレル・ベースラインアルゴリズム（$\text{Alg}^{(r)}$ と表記）を定義する。このアルゴリズムは、最初の $n-r$ 個の列については元のアルゴリズム $\text{Alg}$ と同一の挙動を示す。しかし、最後の $r$ 個の列については、それらがステップ $n-r+1$ で同時に到着したかのように扱う。具体的には、すべてのサフィックス列 $Y_i$ に対して、同じ決定関数 $\phi = \text{SubAlg}_{n-r+1}$ を適用し、サフィックス内での到着順序は無視する。
• 結果: ガウス分布に従う列の交換可能性と平均化の議論を用いることで、どのような成功するアルゴリズムに対しても、その出力がこのサフィックス・パラレル・ベースラインと高確率で一致するような $r$ が存在することを示す。

C. ベースラインの反集中性

証明の第二部は、いかなるサフィックス・パラレル・ベースラインも一意な補完を生み出すことができないことを示す。

• 設定: ベースラインが、サフィックス列 $Y_1, \dots, Y_r$ に対して符号 $z_i = \phi(Y_i)$ を割り当てる固定関数 $\phi$ を使用するとする。出力が解であるための条件は、和 $\frac{1}{\sqrt{r}}\sum z_i Y_i$ が特定の領域（プレフィックスによる制約によってシフトした上部直交錐）内に存在することである。
• 一意性の制約: 解が孤立しているためには、文字列 $z$ がこの線形制約を満たす $\{\pm 1\}^r$ 内の唯一の文字列でなければならない。
• 幾何学的議論: この一意性は、ランダムベクトル $S_\phi = \frac{1}{\sqrt{r}}\sum \phi(Y_i)Y_i$ が $\mathbb{R}^m$ における非常に狭い「シェル（殻）」（二つの上部直交錐の差）の中に位置する必要があることを意味する。
• 確率的境界: 著者らは、ベリー・エッセン（Berry-Esseen）の定理を適用して、$S_\phi$ の分布をガウス変数 $Z$ で近似する。そして、ガウスベクトルの反集中境界を提供するナザロフ（Nazarov）の不等式を援用する。この不等式は、ガウスベクトルがこのような狭いシェルに入る確率は極めて小さい（$o(1)$）ことを示している。
• 結論: ベースラインが確率 $o(1)$ で一意な解を生成すること、そして成功するオンラインアルゴリズムは本質的にそのようなベースラインと一致しなければならないことから、オンラインアルゴリズム自体の成功確率も $o(1)$ となる。

3. 主な貢献と結果

主定理

定理 1.1（簡略化）: すべての制約密度 $\alpha > 0$ およびマージン $\kappa$ において、あらゆるオンラインアルゴリズムがバイナリ・パーセプトロンの孤立した解を見つける確率は $o(1)$ である。

• この結果は、標準的なバイナリ・パーセプトロンに対して成立し、対称バイナリ・パーセプトロンや、制約集合が分離している他の一般的なパーセプトロンモデルにも拡張される。
• 孤立性の閾値は $h = \omega(\log^4 n)$ まで緩和されており、これは文献で通常議論される線形な孤立（$\Omega(n)$）よりも大幅に弱い条件であり、この結果の堅牢性を示している。

先行研究との比較

• Gong, Huang, Li, and Sellke [GHLS26]: 以前の研究では、安定な（stable） アルゴリズム（入力の再サンプリングによって出力がわずかにしか変化しないアルゴリズム）が、孤立した解を見つける確率は最大でも $\approx 0.84$ であることを示した。
  • [GHLS26] の限界: この境界は定数であり、ゼロにはならない。したがって、成功確率が 0.8 であるアルゴリズムを排除できていない。さらに、既知の最良のオンラインアルゴリズム（例：Jo and Lee [JL26a]）が彼らの意味で安定しているかどうかは不明である。
• 本研究: オンラインアルゴリズムに対して消失する境界（vanishing bound）（$o(1)$）を提供した。これにより、オンラインアルゴリズムが孤立した解を見つけることで定数確率で成功する可能性を決定的に排除した。

4. 意義と主張

本論文は、バイナリ・パーセプトロン問題における「統計的・計算的ギャップ」の重要な側面を解決している。

• パラドックスの解決: 「効率的なオンラインアルゴリズムが、解空間が孤立した点によって支配されているにもかかわらず、解を見つけることができる」という一見矛盾した状況は、[BIL+15, BDVLZ20] で提案された仮説を裏付けることで解決される。著者らは、オンラインアルゴリズムが典型的な孤立した解を見つけることはできないことを証明した。したがって、もし彼らが成功するのであれば、それは解空間に存在する指数関数的に稀で、よく結合された解のクラスターを見つけているに違いない。
• アルゴリズムの困難性: 本研究は、**オーバーラップ・ギャップ特性（OGP）**の枠組みとは異なる、オンラインアルゴリズムに対する新しい困難性の結果を確立している。OGPは安定なアルゴリズムに対する困難性を証明するための標準的なツールであるが、著者らの証明は、解のオーバーラップの幾何学ではなく、オンライン設定の構造的制約（不可逆な決定）と反集中特性に依存している。
• 適用範囲: この結果は、不一致最小化やパーセプトロン学習で使用される幅広いクラスのアルゴリズムに適用され、最先端のオンラインアルゴリズムである Jo and Lee [JL26a] にも当てはまる。これは、これらのアルゴリズムが「凍結された」孤立した解のランドスケープをナビゲートする能力を本質的に持っていないことを裏付けている。

要約すると、本論文は、バイナリ・パーセプトロン問題におけるオンラインアルゴリズムの成功が、支配的な孤立した解を見つける能力によるものではなく、稀な非孤立的な解のクラスターの存在とアクセシビリティに依存していることを厳密に証明している。