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

技术摘要：Anderson 加速近端点法 (Proximal Point Method)

问题陈述
本文研究了应用于极大单调包含问题 $0 \in M(x)$ 的残差多项式加速法的极限。标准的近端点法 (PPM) 迭代 $y_{k+1} = (I + M)^{-1}y_k$ 实现的固定点残差率是紧致的 $\Theta(d_0/\sqrt{k})$，其中 $d_0$ 是到解集的初始距离。虽然 Anderson 加速 (AA) 和其他自适应方案（例如 Kim 的 APPM）在某些问题上在经验上是成功的，但对于它们在何时以及能在多大程度上改进 $\Theta(1/\sqrt{k})$ 速率的理论理解仍不完整。具体而言，本文解决了三个基本问题：

1. 任何通过对解析算子输出进行仿射组合的方法（具有任意记忆、自适应性或保护机制）所能达到的精确极小极大复杂度是多少？
2. 对于解析算子的何种谱结构，这种改进是可能的？
3. 在非线性设置中，确保“残差非增”（即保护机制/safeguarding）的精确代价是什么？

方法论
作者分析了残差多项式方法类 $\mathcal{A}_\infty$，其中迭代值 $y_{k+1}$ 是过去解析算子输出的仿射组合，其系数取决于观察到的历史记录。

• 多项式归约： 对于线性极大单调算子，作者证明了 $\mathcal{A}_\infty$ 中的任何方法都对应于作用于初始点 $y_0$ 的多项式 $Q_k(L)$，其中 $L = (I+M)^{-1}$，$Q_k(1)=1$，且 $\deg(Q_k) \le k$。这通过将自适应下界问题转化为多项式逼近问题。
• 极值实例构建： 本文构建了显式的斜对称算子（$\mathbb{R}^{2n}$ 中的旋转），具有特定的谱测度以作为最坏情况实例。这些实例利用单位根和精心选择的质量分布（权重）来最大化任何 $K$ 次多项式的残差。
• 对偶性与 Christoffel 函数： 下界证明依赖于极小极大残差问题与单位圆上的切比雪夫逼近问题之间的对偶关系。作者利用 Christoffel 函数和 Lagrange 恒等式来计算精确的实例极小极大值。
• 保护机制分析： 本文分析了在非线性设置中为了保证收敛性而需要额外调用预言机（oracle）的必要性，证明了仅凭历史记录进行认证是不可能的，除非评估候选残差。

核心贡献与结果

1. 精确的自适应极小极大复杂度
本文确定了在经过 $K$ 次解析算子评估后，全自适应类 $\mathcal{A}_\infty$（及非自适应子类）的极小极大残差为：
$$\sup_{M} \inf_{\text{methods}} \|r(y_K)\| = \frac{d_0}{K+1}$$

• 上界： 由平均反射估计器 $\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 核。这填补了之前由 Bernstein 型界限留下的两倍因子差距，并消除了旋转谱实例中存在的对数松弛。

2. 谱相变 (Spectral Phase Transition)
本文根据谱间隙 $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$，则可以实现加速。Jackson 核多项式可实现 $\|r(y_K)\| = O(d_0/(K^2 s))$，优于 $1/K$ 的包络线。
• 对数人工痕迹： 本文澄清了先前在旋转谱分析中出现的对数因子 ($\log K$) 是亚临界质量分布 ($\csc$) 的人工痕迹，而非内在限制。真实的极值测度具有临界指数 ($\csc^2$)，它在固定点附近集中质量，从而消除了对数因子。

3. 保护机制与非线性问题

• 线性安全性： 在线性问题上，AA-PPM 的残差会自动下降；无需额外的保护机制。
• 非线性必要性： 对于非线性问题，本文证明了无法仅从窗口历史记录中计算出认证信息。为了保证速率，必须评估候选者的残差。
• 最优代价： 作者提出了一种认证方案，每次迭代恰好需要两次解析算子评估（一次用于认证链，一次用于探测）。他们证明了这个两倍因子的最优性；没有任何仅基于历史记录的规则可以实现速率认证。

4. 结构化问题与增长条件

• 仿射算子： 全记忆 AA 在有限步内终止（$k \le \nu + 1$，其中 $\nu$ 是不同特征值的数量）。
• 强单调性： 线性收敛速率得以保持。
• Hölder 增长性： 本文建立了关于增长指数 $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)})$。

意义与主张
本文声称提供了针对极大单调包含问题中 Anderson 加速及残差多项式方法的首次精确刻画。

• 它解决了之前界限中的“两倍因子”歧义，证明精确值为 $d_0/(K+1)$。
• 它表明在最难的线性实例上，自适应性毫无用处；最优策略是不可自适应的平均反射。
• 它精确划定了实现加速在理论上可能的谱条件（相变发生在 $s \asymp 1/K$）。
• 它确定了保护机制的代价，证明在非线性设置中，两次预言机评估是实现认证的充分必要条件。

作者强调，这些结果是通过精确的谱分析和 Christoffel 函数对偶性推导出来的，并得到了数值实验的支持，实验结果在机器精度范围内证实了理论预测。本工作并不声称解决了随机设置或非正规算子的问题，并将这些视为开放性问题。