Anderson acceleration of the proximal point method: the exact adaptive minimax, a spectral phase transition, and optimal safeguarding

技術要約：近接点法におけるアンダーソン加速

問題設定
本論文は、極大単調包含 $0 \in M(x)$ に適用される近接点法（PPM）に対する残差多項式加速の限界を調査している。標準的なPPM反復 $y_{k+1} = (I + M)^{-1}y_k$ は、初期解集合への距離を $d_0$ とすると、$\Theta(d_0/\sqrt{k})$ というタイトな不動点残差レートを達成する。アンダーソン加速（AA）やその他の適応型スキーム（KimのAPPMなど）は、特定の条件下で経験的に成功しているが、これらが $\Theta(1/\sqrt{k})$ のレートを「いつ」「どの程度」改善できるかという理論的理解は不完全であった。具体的には、本論文は以下の3つの根本的な問いに取り組んでいる：

1. 残差多項式による手法（任意のメモリ、適応性、またはセーフガードを備えたもの）が達成可能な正確なミニマックス複雑度は何か？
2. どのようなレゾルベントのスペクトル構造において、このような改善が可能となるのか？
3. 非線形設定において、「セーフガード（残差の非増加を保証すること）」を行うための正確なコストは何か？

手法
著者らは、過去のレゾルベント出力のアフィン結合によって次ステップの $y_{k+1}$ を決定する、履歴に依存する任意の係数を持つ残差多項式手法のクラス $\mathcal{A}_\infty$ を分析している。

• 多項式への還元： 線形極大単調作用素に対して、著者らは $\mathcal{A}_\infty$ に属するあらゆる手法が、初期点に対して多項式 $Q_k(L)$ を適用することに対応することを確立している。ここで $L = (I+M)^{-1}$ であり、$Q_k(1)=1$ かつ $\deg(Q_k) \le k$ である。これにより、適応的な下界問題は多項式近似問題へと還元される。
• 極値インスタンスの構成： 著者らは、特定のスペクトル測度を持つ、具体的な歪対称作用素（$\mathbb{R}^{2n}$ における回転）を、ワーストケースのインスタンスとして構築している。これらのインスタンスは、次数 $K$ の任意の多項式に対して残差を最大化するために、単位根と注意深く選択された質量分布（重み）を利用している。
• 双対性とクリストフェル関数： 下界の証明は、ミニマックス残差問題と単位円上のチェビシェフ近似問題との間の双対性に依拠している。著者らは、正確なインスタンスのミニマックス値を計算するために、クリストフェル関数とラグランジュ恒等式を利用している。
• セーフガードの分析： 非線形設定において収束を保証するためのオラクルコールの必要性を分析し、履歴のみから収束を証明することは不可能であり、候補となる残差を評価する必要があることを証明している。

主な貢献と結果

1. 正確な適応的ミニマックス複雑度
本論文は、$K$ 回のレゾルベント評価後の全適応クラス $\mathcal{A}_\infty$（および非適応サブクラス）におけるミニマックス残差が以下であることを確立している：
$$\sup_{M} \inf_{\text{methods}} \|r(y_K)\| = \frac{d_0}{K+1}$$

• 上界： 平均反射推定器（averaged-reflection estimator） $\hat{y}_K = \frac{1}{K+1}\sum_{j=0}^K (2J-I)^j y_0$ によって達成される。この推定器は、すべての極大単調作用素に対して、望遠鏡的な恒等式を通じて $\|r(\hat{y}_K)\| \le d_0/(K+1)$ を達成する。
• 下界： 著者らは、明示的な「極値インスタンス」（固有値が $u^{K+1} = -1$ の単位根にあり、質量が $\csc^2$ に比例する歪対称作用素）を構築した。このインスタンスにおいて、$\mathcal{A}_\infty$ に属するあらゆる手法（適応型か否かを問わず）は $\|r(y_K)\| \ge d_0/(K+1)$ を満たす。
• 含意： 線形ワーストケース・インスタンスにおいて、適応性とメモリは、非適応的な平均反射に対して何の優位性も提供しない。最適な多項式は一意にフェイェール核（Fejér kernel）である。これは、従来のバーンスタイン型の境界が残していた「因子2」のギャップを埋め、回転スペクトルのインスタンスで見られた対数的な緩みを取り除いたものである。

2. スペクトル相転移
本論文は、スペクトルギャップ $s = \text{dist}(1, \sigma(L))$ に基づく鋭い相転移を特定している：

• 臨界フロア ($s \asymp 1/K$)： スペクトルが不動点の近くに密集している場合（具体的には $s \le \sin(\pi/(2K+2))$）、障壁は正確に $1/(K+1)$ である。この場合、一様なレートを超える加速は不可能である。
• 脱出領域 ($sK \to \infty$)： スペクトルが 1 から一定の距離 $s$ を保ち、$sK \to \infty$ となる場合、加速が可能となる。ジャクソン核多項式を用いることで、$\|r(y_K)\| = O(d_0/(K^2 s))$ を達成でき、$1/K$ のエンベロープを打ち破ることができる。
• 対数的アーティファクト： 回転スペクトルの解析において以前の分析に現れていた対数因子 ($\log K$) は、劣臨界な質量分布 ($\csc$) によるアーティファクトであることを本論文は明らかにしている。真の極値測度は、固定点の近くに質量を集中させる臨界指数 ($\csc^2$) を持ち、対数因子を排除している。

3. セーフガードと非線形問題

• 線形的な安全性： 線形問題では、AA-PPM の残差は自動的に減少するため、セーフガードは不要である。
• 非線形性の必要性： 非線形問題については、ウィンドウ履歴のみから証明（certificate）を計算することは不可能であることを本論文は証明している。レートを保証するためには、候補となる残差を評価しなければならない。
• 最適なコスト： 著者らは、正確に2回のレゾルベント評価を必要とする認定スキームを提案している（1回は認定された連鎖のため、もう1回はプローブのため）。この「因子2」が最適であることを証明しており、履歴のみに基づいたルールではレートを証明できない。

4. 構造化された問題と成長条件
本論文は、構造化された設定における収束レートを修正および精緻化している：

• アフィン作用素： フルメモリのAAは、有限ステップ（$k \le \nu + 1$、ここで $\nu$ は異なる固有値の数）で終了する。
• 強単調性： 線形収束レートが保持される。
• ヘルダー成長： 成長指数 $q$ に関する正しい三分法を確立している：
  • $q < 2$：$1/(q-1)$ 次の超線形収束。
  • $q = 2$：線形収束。
  • $q > 2$：$d_k = O(k^{-1/(q-2)})$ および $\|r_k\| = O(k^{-(q-1)/(q-2)})$ のレートを持つ劣線形収束。

意義と主張
本論文は、極大単調包含におけるアンダーソン加速および残差多項式手法のミニマックス複雑性について、初の正確な特性付けを提供したと主張している。

• 以前の境界に残されていた「因子2」の曖昧さを解決し、その正確な値が $d_0/(K+1)$ であることを示した。
• 最も困難な線形インスタンスにおいては、適応性は何も得られないこと、すなわち最適な戦略は非適応的な平均反射であることを示した。
• 加速が理論的に可能となるスペクトル条件（相転移 $s \asymp 1/K$）を正確に記述した。
• セーフガードのコストを確定させ、非線形設定での認定には、1ステップあたり2回のオラクル評価が必要かつ十分であることを証明した。

著者らは、これらの結果が正確なスペクトル解析とクリストフェル関数の双対性から導かれたものであり、数値実験によって理論的予測がマシン精度まで一致することが確認されていることを強調している。本研究は、確率的な設定や、鋭い定数を持つ非正規作用素を解くことを目的としたものではなく、それらを未解決の問題として特定している。