精读笔记

Problem Setting

论文实际解决的是一个很窄但技术上干净的问题：Halpern iteration

x^k = λ_k u + (1-λ_k)T x^{k-1}

在非扩张 T、Fix(T) 非空的 Hilbert 空间中，当 anchor u 与 initial guess x^0 不相等时，如何给出 \|x^k-Tx^k\| 的 tight convergence rate。

关键困难不在 asymptotic regularity，也不在强收敛；这些在经典 Halpern 文献里已有条件。困难在于已有 sharp rate 的证明强烈利用 u=x^0：anchor 同时作为起始点，使得轨道表达式、能量不等式和内积项天然闭合。一旦 u≠x^0，初始 mismatch 会沿 Tx^{k-1} 路径传播，旧证明中的 cancellation 不再直接成立。

这篇论文的关键矛盾是：Halpern anchor 本来控制极限点和正则化方向，但 initial guess 控制轨道早期误差；当两者分离时，rate bound 到底应该依赖 anchor-to-solution 距离，还是也必须支付 anchor-to-initial 距离。作者的回答是：一般 λ_k=1/(k+1) 情况下必须显式支付 \|u-x^0\|；但通过特殊 anchor / shift 或 adaptive 参数，可以恢复更接近 u=x^0 情形的形式。

Motivation

已有 Lieder 的 sharp estimate

\|x^k-Tx^k\| ≤ 2/(k+1) \|x^0-x^*\|

以及 He et al. 的 adaptive estimate 都建立在 u=x^0 上。这不是一个无关紧要的记号假设，而是 rate 证明的结构性假设：初始点和 anchor 合一后，迭代轨道等价于以同一个 reference point 生成的 Cesàro-like fixed-point trajectory。

作者的核心观察是：很多 Halpern 型算法，尤其在 fixed-point reformulation、monotone inclusion、optimization acceleration 中，anchor 可以被看作外部 reference 或 regularization center，不必自然等于 x^0。因此已有 tight rate 对一般 Halpern iteration 的解释力不足。

真正缺的是一个“mismatch-aware”的 sharp rate theory：既要说明初始错位如何进入常数，又要说明 adaptive anchoring 的几何机制是否仍然成立。本文没有试图发明更快算法，而是补上 tight complexity statement 中一个此前被默认规避的初始化自由度。

Core Idea

核心思想可以概括为：把 anchor-initial mismatch 从 Halpern 轨道的主收敛机制中分离出来。

对于标准 λ_k=1/(k+1)，作者构造一个辅助轨道 y^0=u，并令 y^k 与 x^k 使用同样 anchor 和参数。由于 T 非扩张，两个轨道的距离满足

\|x^k-y^k\| ≤ \|x^0-u\|/(k+1)。

于是一般轨道的 residual 可以用三角不等式拆成：辅助轨道 residual + 两轨道距离 + 映射后轨道距离。辅助轨道正好满足 u=y^0，因此可调用 Lieder 的 tight bound；错位项以同阶 O(1/k) 衰减。这说明 mismatch 不改变阶数，但改变常数，而且该常数不可一般性消除。

对于 adaptive φ_k，核心不是 coupling，而是让参数本身吸收几何信息。φ_k 被定义为当前 residual 与 anchor direction 的归一化内积，这相当于选择一个使下一步能量不等式闭合的局部步长。它引入的 inductive bias 是：每一步都要求 residual 朝向 anchor displacement 有足够正投影，从而把 residual norm 控制为 anchor-to-solution 距离的 2/(φ_k+1) 倍。

Method

1. 一般预设参数 λ_k=1/(k+1)： 解决的是任意 u,x^0 下旧 sharp bound 不能直接用的问题。作者引入从 u 出发的辅助 Halpern 轨道 y^k。非扩张性给出轨道差距的 multiplicative damping：每一步乘 k/(k+1)，最终是 1/(k+1)。这一步的核心变化是把初始化不一致解释为一个同阶衰减扰动，而不是重新证明整个 rate。

2. 特殊预设参数 λ_k=1/(k+3), u=2x^0-Tx^0： 解决的是一般 bound 中额外 \|u-x^0\| 项导致常数较差的问题。这个 anchor 选择本质上把初始 residual 预先写入 anchor，使第一步能量项精确抵消。之后通过归纳维持

\|x^k-Tx^k\|^2 + 2/(k+2)<x^k-u,x^k-Tx^k> ≤ 0。

它不是普适改进，而是一个经过校准的初始化 scheme。

3. Adaptive anchoring parameter： 解决的是固定 λ_k 不能利用局部几何的问题。φ_k 由

2<x^{k-1}-Tx^{k-1},u-x^{k-1}> / \|x^{k-1}-Tx^{k-1}\|^2 + 1

给出，使 φ_k 至少线性增长，并保证 residual-anchor 内积不等式可递推。核心变化是从 predetermined schedule 转向由当前 residual geometry 决定的 effective time scale φ_k。

Key Insight / Why It Works

最核心的 insight 是：Halpern residual rate 的 sharp 常数来自一个非常具体的 Hilbert 几何恒等式，而不是来自普通 Fejér monotonicity。论文中的 Lemma 2.3 把 residual、anchor displacement、fixed-point distance 组织成一个平方差结构；只要能证明某个 residual-anchor 内积项非正或可控，就能直接推出 2/(time+1) 形式的 sharp bound。

对于 λ_k=1/(k+1) 的一般情形，真正有效的是 coupling，而不是新的收敛分析。非扩张性保证初始 mismatch 不会被放大，而且在 Halpern 权重下恰好按 1/(k+1) 衰减。因此 bound 中出现

\|u-x^0\| + \|u-x^*\|

很自然：第一项是轨道错位成本，第二项是 anchor 到 fixed point 的主复杂度尺度。这部分贡献更像是对已有 sharp theorem 的稳定性分析。

对于 λ_k=1/(k+3), u=2x^0-Tx^0，增益来自人为制造的 cancellation。这里所谓更好 rate 并不是一般意义上的 adaptive acceleration，而是通过选择 anchor 改变了初始几何，使归纳不等式从 k=1 开始成立。这个结果有数学美感，但实际算法含义要谨慎解读：anchor 已经使用了 Tx^0，因此它不是普通外部 anchor，而是经过一次 operator probing 后构造出的校准点。

Adaptive 部分最有迁移价值。φ_k 的定义让时间尺度不再是 iteration index k，而是由 residual 与 anchor displacement 的 alignment 决定。若当前 residual 在 anchor 方向上投影大，则 φ_k 增长更快，bound 随之更强。这更像是一种 geometry-adaptive clock，而不是简单调参。它的有效性完全依赖非扩张性 + Hilbert 平方恒等式 + 内积 alignment 的可归纳传播。

需要明确：本文没有证明比 O(1/k) 更高阶的普适加速。所谓 adaptive improvement 是以 φ_k≥φ_0+k 表达的实例相关 bound；如果 φ_k 只线性增长，就仍是 O(1/k)。因此这不是 scaling，也不是 data/retrieval/memory reuse/test-time compute 之类机制，而是 sharp operator-theoretic inequality 的重新组织。

Relation To Prior Work

最接近的是 Lieder 2021 的 u=x^0, λ_k=1/(k+1) sharp residual rate，以及 He et al. 2024 的 adaptive anchoring parameter 分析。本文基本沿着这条 Halpern residual complexity 谱系推进：关注 \|x^k-Tx^k\|，追求 tight constant，而非一般 convergence theorem。

与 Lieder 的本质差异在于，Lieder 的证明对象是 anchor-initial coincident trajectory；本文把 distinct initial guess 作为显式扰动，并证明扰动衰减。严格说，Theorem 3.1 的新意不是一个全新的不等式技巧，而是证明 sharp rate 对初始化 mismatch 的稳定性，并给出 tight 常数。

与 He et al. adaptive work 的差异是 anchor 从 x^0 替换为一般 u，同时需要 φ_0>-1 来保证 adaptive 参数合法和归纳启动。形式上是推广；实质上是把 adaptive 参数的几何中心从 initial guess 改成 anchor，并重新检查核心不等式是否仍闭合。

看似新的部分中，辅助轨道 coupling 是经典非扩张映射分析里常见手法；真正新增的信息是常数级 tight characterization。特殊 anchor u=2x^0-Tx^0 则更像一个 calibration trick：它展示了如果允许 anchor 依赖 Tx^0，可以恢复更干净的 bound，但这不应被理解为一般 distinct-anchor setting 的完全解决。

Dataset / Evaluation

没有 dataset、benchmark 或实验评估；这是一篇纯理论 paper。验证方式是 theorem + sharpness example。

从 claim 支撑角度看，论文的核心 claim 是 tight convergence rate estimates，而不是 empirical acceleration。因此用二维 rotation T=-I 构造 worst-case / equality case 是合适的。这个例子有效证明了在非扩张映射类上，给定形式的 bound 不能一般性改善。

但 evaluation 的覆盖也很有限：tightness 主要针对抽象 worst-case operator，不说明在 monotone inclusion、GAN、ADMM、Chambolle-Pock 等实际应用映射中这些 bound 是否紧，也不说明 special anchor 或 adaptive φ_k 是否带来实际迭代收益。文中引用应用动机，但没有用应用实例验证这些 rate estimate 对真实算法设计的指导性。

Limitation

1. 依赖 Hilbert 空间平方结构。核心证明大量使用内积展开和平方恒等式；迁移到一般 Banach 空间不直接成立。即使 CAT(0) 空间中已有 Halpern metastability 文献，本文 sharp constant 机制也未必保留。

2. 非扩张性是假设核心。若实际算法对应的是 averaged、cocoercive、quasi-nonexpansive 或带误差/随机噪声的 operator，本文结论不能直接覆盖。实际 optimization deployment 中 T 的非扩张性常依赖精确步长、预条件器或范数选择，文中未讨论 robustness。

3. 一般 distinct-anchor bound 支付 \|u-x^0\|。这说明 mismatch 成本没有被消除，只是被量化。若 anchor 远离 initial guess，bound 可能很松；这在应用中并非小问题。

4. 特殊更优结果的通用性有限。u=2x^0-Tx^0 需要先计算 Tx^0，并让 anchor 依赖初始 residual。它改变了 anchor 的语义：anchor 不再是外部先验点，而是 operator-informed extrapolated point。文中未充分说明这在 fixed-point approximation 中是否总是合理，尤其当 anchor 本来承载目标 fixed point selection 时。

5. Adaptive φ_k 的可用条件 φ_0>-1 不只是技术细节。它要求初始 residual 与 anchor direction 的 alignment 不能太差。如果 u 的方向选得不好，算法定义或正性可能出问题。文中未充分说明如何在一般问题中选择 u 来满足该条件。

6. 强收敛部分被简略处理。Remark 3.4 说可按已有证明得到 strong convergence，但没有展开。对于一篇主打 general anchor 的论文，这里略显保守：rate bound 是 residual 的，不是直接的 iterate distance rate。

Takeaway

• 1. anchor-initial mismatch 在 Halpern residual complexity 中不是灾难性问题；在标准 λ_k=1/(k+1) 下，它以 O(1/k) 衰减并表现为额外常数 \|u-x^0\|。
• 2. sharp Halpern rate 的真正机制是 residual-anchor geometry，而不是单纯参数序列。
• 只要能维持 residual 与 anchor displacement 的内积不等式，就能通过 Hilbert 平方恒等式推出 2/time 的 tight bound。
• 3. Adaptive anchoring parameter 可以理解为一种 geometry-adaptive clock：φ_k 记录局部 alignment 质量，好的 alignment 会把 effective time 推快。

一句话总结

这篇论文是 Halpern iteration sharp residual-rate 理论的一次初始化自由度扩展：它证明 distinct anchor 与 initial guess 的错位可以被精确量化，并将已有 u=x^0 的 predetermined 与 adaptive rate 结果推广到更一般但仍高度 Hilbert-geometry-dependent 的设置。