精读笔记

Problem Setting

论文标题：Accelerated Golden Ratio Primal--Dual Algorithm for Structured Convex Optimisation without Linesearch（arXiv preprint / 2026-07-10）。

这篇论文实际解决的是一个很具体的算法分析问题：在结构化凸优化 min_x f(x)+g(Kx)+h(x) 中，当 h 的梯度只局部 Lipschitz 时，如何构造不依赖全局 Lipschitz 常数、不使用 linesearch、也不需要人为步长上界的 primal-dual 方法。

困难点在于局部光滑本身不提供全局稳定步长。若步长按局部差分估计放大，理论上必须证明迭代轨迹有界，否则局部 Lipschitz 常数无法统一控制；但轨迹有界性又通常依赖下降不等式，而下降不等式本身需要步长受控。这是核心闭环。

已有 aEGRPDA 通过 tau_max 打断这个循环：先人为限制步长，再证明收敛。但这让算法多了一个很尴尬的尺度参数。tau_max 取小会压制局部自适应，取大则理论常数失真。本文的关键矛盾就是：能不能让 adaptive rule 自己给出步长上界，而不是外部硬截断。

Motivation

已有路线的问题不是没有 primal-dual 算法，而是不同路线各自卡在一个现实成本上。固定步长方法需要全局 Lipschitz 常数和 ||K|| 的保守组合；linesearch 方法能处理局部光滑，但代价是内循环、重复算子调用和实现复杂度；已有 adaptive GRPDA 避免 linesearch，却引入 tau_max。

作者的核心观察很朴素但有效：aEGRPDA 的步长更新本身是一个两分支 min 结构，一个分支允许按 rho 增长，另一个分支按局部曲率和 ||K|| 限制增长。这个结构天然不可能无限放大，因为 min{rho tau, c/tau} 受 sqrt(rho c) 控制。也就是说，tau_max 不是算法机制需要，而是旧证明没有充分利用递推结构。

关键缺口因此变成：去掉 tau_max 后，是否还能建立完整的下降、下界、收敛、ergodic residual bound，并进一步在强凸情形下拿到 O(1/N^2)。本文基本是在补这个理论缺口。

Core Idea

核心思想是把“局部光滑估计”从一个需要 linesearch 验证的条件，改造成步长递推中的内生约束。算法每步用 L_n=||grad h(x_n)-grad h(x_{n-1})||/||x_n-x_{n-1}|| 表示沿轨迹的局部曲率，同时用 ||K|| 控制线性耦合项，再通过 golden-ratio 变量 z_n 组织可 telescoping 的能量函数。

本质区别不在于 proximal 更新本身，而在于信息流的重新组织：局部曲率信息只通过步长更新进入算法，不通过回溯检验；稳定性由 min 递推和 Fejer 能量共同保证；加速则通过让 beta_n 增长，把每步 residual 的权重 beta_n tau_n 拉成线性增长，从而让累计权重 Q_N 达到 O(N^2)。

这是一种算法尺度自校准机制。它没有改变问题建模，也没有引入新的 oracle；它改变的是步长控制从“外部验证/外部上界”变成“递推结构自约束”。这一点比单纯去掉 tau_max 更重要。

Method

1. 参数自由 PF-GRPDA：解决 tau_max 依赖。步长更新保留增长分支 rho tau_{n-1} 和局部曲率约束分支。关键变化是用 min{a,b}<=sqrt(ab) 证明 tau_n 自动有上界，再用轨迹有界性和局部光滑得到 tau_n 下界。这样 Fejer 型下降可以闭合，得到 O(1/N) ergodic objective residual 和 feasibility violation。

2. residual 而非 classical primal-dual gap：论文使用 Lagrangian residual J(x,w,y)=Phi(x,w)-Phi(x*,w*)+<y,Kx-w>。这是必要的，因为 dual domain 无界时普通 gap 可能不稳定甚至误导。这个选择使 objective residual 和 feasibility violation 能通过对 ||y||<=b 取 supremum 同时控制。

3. 强凸 f 的加速版本：当 f 强凸时，proximal 最优性给出额外的 ||x_{n+1}-x*||^2 和 ||x_{n+1}-x_n||^2 项。算法让 beta_n 按 curvature 驱动增长，同时仍保持局部光滑约束。理论核心是证明 beta_n 至少二次增长、beta_n tau_n 至少线性增长，因此加权 ergodic 平均达到 O(1/N^2)。

4. 强凸 h 的加速版本：h 的强凸项出现在 x_n 而非 x_{n+1}，不能直接照搬强凸 f 的证明。作者利用 golden-ratio 关系把 z_{n+2}-x* 展开为 x_n-x*、x_{n+1}-x_n、x_n-z_{n+1} 的组合，再用 gamma 的上界把 beta 增长产生的额外项吸收进强凸下降项。这是技术上更细的一部分。

5. 线性收敛情形：当 f 和 g* 都强凸时，能量函数中 primal 和 dual 两边都有曲率，结合 psi>rho 得到真正 contraction。这部分更多是已有 primal-dual 强凸分析在该步长系统下的适配。

Key Insight / Why It Works

最核心贡献是证明步长自适应规则本身隐含了全局上界。这个 insight 很小，但抓住了旧算法中 tau_max 的本质冗余。没有这一步，后面的无 linesearch、无 cap、局部光滑收敛都站不稳。

方法有效的原因不是“golden ratio 神奇”，而是三件事配合得刚好：第一，golden-ratio 更新给出可 telescoping 的 z_n 能量；第二，局部差分 L_n 只需要沿轨迹有效，不要求全局 Lipschitz；第三，步长 min 结构同时允许恢复性增长和自动抑制过大步长。真正的稳定性来自这三个机制的代数耦合。

加速部分的核心也不是 Nesterov 式动量，而是权重增长。强凸性提供额外可吸收项，beta_n 增长让累计权重 Q_N 从 O(N) 变成 O(N^2)。从这个角度看，加速主要是 energy weighting / scaling，而不是引入更强的预测结构。它更像 primal-dual metric scaling 的理论化版本。

哪些可能只是辅助：alpha_n、psi 区间、gamma 上界等大量常数设计主要服务证明闭合，未必对应实际最优行为。尤其 Algorithm 4 的 gamma 选择看起来保守，实践中是否能稳定释放强凸加速取决于 scaling。文中未充分说明这些参数对真实运行的敏感性。

哪些值得迁移：把局部 smoothness estimate 嵌入步长递推，而不是用 linesearch 验证；用 residual ball over y 同时转化 feasibility 与 objective；用强凸性驱动 metric/dual-ratio 增长来制造 O(N^2) 权重。这些机制可以迁移到其他 splitting、ADMM-like 或 distributed composite optimization。

Relation To Prior Work

最接近的是 Soe et al. 2026 的 aEGRPDA。本文不是从零设计新算法，而是对其步长规则做更精细分析，去掉 tau_max，并扩展强凸加速。这是实质改进，但性质更像理论修正和机制补全，而不是全新算法谱系。

与 Chambolle-Pock / Condat-Vu / classical primal-dual splitting 相比，本文仍在 proximal primal-dual splitting 谱系内；差异是局部光滑下的 adaptive non-monotone step-size，而不是固定全局 Lipschitz 条件。

与 Malitsky-Pock linesearch、aPDAc-L 相比，本文的本质区别是不用 backtracking 来验证 local model，而是用递推结构内生限制步长。它牺牲了一部分即时的局部充分下降检验，换来无内循环和更简单的 oracle 调用。

与 aGRAAL 相比，作者强调直接把问题写成 MVIP 后用通用 GRAAL 会丢掉 composite structure，误差界也弱。这个判断合理：本文的 w/y 分裂和 g 的 prox 结构确实更贴合原问题。

看似新的部分中，golden-ratio 外推、Fejer telescoping、强凸加权平均都不是新思想；真正新增的信息是：这些已有工具在局部光滑、无 linesearch、无 tau cap 的设定下可以闭合，并且强凸时还能通过 beta_n 增长得到 O(1/N^2)。

Dataset / Evaluation

实验主要是 Poisson inverse imaging，包含 motion blur 和 defocus blur，两类设置：普通 KL-TV、带二次项的强凸版本，以及把二次项放入 h 来测试强凸 h 的加速版本。任务选择是合理的，因为 KL 项确实是局部光滑而非全局光滑，TV + 非负约束也符合 proximal splitting 场景。

但 evaluation 覆盖范围偏窄。它验证的是成像类局部光滑问题上的行为，不足以支持“广泛 robust”或“跨应用优越”的结论。没有 logistic/fused lasso/elastic net 等文中提到的其他结构化问题，也没有大规模 wall-clock 分解来量化避免 linesearch 的真实收益。

实验支持的核心 claim 是有限的：PF-GRPDA 去掉 cap 后运行稳定；强凸加速版本在 residual 上优于非加速版本；aPDAc-L 仍然很有竞争力，但需要 linesearch。它没有充分证明加速收益来自理论机制本身，还是来自 beta scaling、参数选择、或任务特定 conditioning。

adaptive-beta heuristic 在实验中看起来有用，但理论不覆盖。这里增益来源不清，可能主要来自 primal-dual residual balancing / scaling，而不是论文主算法的核心 golden-ratio 机制。

Limitation

第一，理论依赖轨迹有界后再调用局部 Lipschitz 常数。虽然证明通过 Fejer 结构闭合了这一点，但常数仍然是后验的，实际不可计算。所谓“不需要全局 Lipschitz”并不等于理论常数可用。

第二，||K|| 仍然需要已知或可估计。对于许多成像算子这不是问题，但对复杂 implicit operator、learned operator 或 distributed setting，||K|| 的估计本身可能成为瓶颈。

第三，加速版本依赖强凸常数和参数上界。尤其 Algorithm 4 的 gamma 需要满足保守阈值，实际中小 gamma 可能几乎不产生加速，大 gamma 又可能破坏证明。文中未充分说明如何稳健选择这些参数。

第四，实验没有隔离 scaling 贡献。PF-AGRPDA、PF-GRPDA-ad beta、aPDAc-L 的差异有相当一部分可能来自 primal-dual ratio beta 的调节，而不是核心理论结构。增益归因不够干净。

第五，O(1/N^2) 是 ergodic residual rate，不是 last-iterate objective gap，也不是实际重建质量的直接提升。PSNR 很快饱和说明后期优化 residual 改善未必转化为应用指标。

第六，论文没有解决自适应估计强凸性的问题。若强凸参数未知、局部强凸、或模型中 curvature 很不均匀，当前加速机制可能退化或需要手调。

Takeaway

• 1. 这篇最值得记住的是：aEGRPDA 的 tau_max 是冗余的，步长 min 递推本身已经提供上界。
• 这是一个小而实的理论修正。
• 2. 对局部光滑问题，linesearch 不是唯一办法。
• 只要步长递推能同时表达增长和曲率约束，并能进入 telescoping 能量，就可以避免回溯。

一句话总结

这篇论文在 golden-ratio primal-dual splitting 谱系中把“局部光滑自适应步长”从带外部 cap 的经验机制推进为无 linesearch、无 tau_max、可加速的理论框架，真正贡献是步长递推自约束和强凸驱动 scaling 的分析闭合。