精读笔记
Problem Setting
论文题目：Preconditioned primal-dual algorithms for saddle point problems: non-ergodic convergence rates（arXiv preprint / 2026-07-10）。
这篇论文实际解决的是一般 convex-concave saddle point problem 中 primal-dual 方法的“原始迭代点”收敛速率问题，而不是平均迭代点的 ergodic gap。问题形式允许 Phi=f+F、Gamma=g+G，其中 f,g 可 nonsmooth proximable，F,G smooth convex，并包含线性约束凸优化作为特例。
困难点在于：经典 PDHG / Chambolle-Pock 依赖步长条件可以稳定，但一般凸情形下最自然得到的是 ergodic O(1/k)；非遍历 rate 往往需要强凸性、加速结构、或 augmented Lagrangian 类机制。这里作者想在没有强凸性、没有显式 Nesterov 惯性、且允许每步 inexact subproblem 的情况下，直接控制 Delta_k = L(x_k,y*) - L(x*,y_k)。关键矛盾是：要得到非遍历下降，需要当前迭代点的能量收缩；但 primal-dual coupling 的 skew 结构通常只给 telescoping 或 averaged control，直接 gap 很难压住。
Motivation
已有路线不够的地方很明确：PDHG 类方法工程上好用，但理论上一般给 average iterate；Condat-Vu 可给非遍历收敛但 rate 仍常是 ergodic；强凸或惯性加速路线能给非遍历 rate，但引入额外结构假设或算法复杂性；augmented Lagrangian 路线可得到更强结果，但改变了子问题形态和计算负担。
作者的核心观察来自连续时间动力系统：如果预条件器含有 antisymmetric coupling，即 beta A^* ydot 与 -beta A xdot，那么 primal-dual 运动中的交叉项可以在 Lyapunov 分析里抵消。这个观察的意义是，非遍历下降不是靠平均化“抹平振荡”，而是通过改变离散动力学本身的几何结构来抑制振荡。
关键缺口是把 Apidopoulos-Molinari-Peypouquet-Villa 的连续动力学结果变成可执行算法，并处理两个现实问题：smooth+nonsmooth 分裂，以及每步 implicit diagonal+skew resolvent 不一定精确可解。
Core Idea
核心思想是把 primal-dual algorithm 看成一个带反对称预条件器的离散动力系统，而不是把它看成标准 forward-backward splitting 的小改动。标准 PDHG 的 coupling 主要出现在 operator 本身；这里 coupling 进一步进入“速度项”或差分项，即用 beta_k A^*(y_{k+1}-y_k) 和 -beta_k A(x_{k+1}-x_k) 重新组织 primal 与 dual 的信息流。
这种设计引入的 inductive bias 是：primal 和 dual 的变化方向必须通过 A 成对协调，算法不允许两侧独立漂移后再靠 averaging 修正。理论上，这种 antisymmetric coupling 保留了 skew operator 不产能的性质，同时 diagonal alpha/delta 项提供耗散。结果是能构造 E_k = Delta_k + tau_k||x_k-x*||^2/2 + sigma_k||y_k-y*||^2/2，并让 E_k 近似满足乘法收缩递推。
和 prior 的本质区别不在于用了 variable metric，也不在于用了 inexact prox，而在于：预条件器不是纯正定几何缩放，而是刻意加入反对称速度耦合，使 gap 本身参与 Lyapunov 下降。这是本文最值得记住的建模变化。
Method
第一，算法从连续 inclusion 离散化而来：alpha_k(x_{k+1}-x_k) + beta_k A^*(y_{k+1}-y_k) + partial f(x_{k+1}) + grad F(x_k) + A^*y_{k+1} 包含 primal 方程；dual 方程对称地含有 -beta_k A(x_{k+1}-x_k)。它解决的是 primal-dual 振荡和非遍历 gap 难控的问题。核心变化是把 coupling 从位置层面扩展到增量层面。
第二，smooth+nonsmooth 分裂采用显式-隐式处理：F,G 用前向梯度，f,g 用隐式 subdifferential / resolvent。它解决的是一般 composite saddle point 的适用性问题。这里没有新奇的 splitting 技巧，主要价值是证明该分裂不会破坏 antisymmetric Lyapunov cancellation。
第三，参数 alpha_k,beta_k,delta_k 被设计成满足 Assumption 3。它解决的是能量递推中正负项的配平问题：Lipschitz smoothness 带来的二次误差必须被 diagonal damping 吸收，而 beta_k 的增长决定最终 B_k 和速率。beta_k 常数给形式上的线性收敛，beta_k 线性增长给 O(1/k)，但这些速率都与误差可求和条件绑定。
第四，inexactness 通过 epsilon_{k+1}, epsilon'_{k+1} 进入，并被压缩成 R_k。它解决的是每步 resolvent 很难精确求的问题。核心变化是理论不再假装子问题可精确解，而是要求误差与 beta_k、B_k 的收敛尺度匹配。实际代价是内层 tolerance 可能越来越严格。
Key Insight / Why It Works
真正有效的部分是 Lemma 9 的能量差分结构。antisymmetric 预条件器让 A 相关的交叉项在两条方程相加时抵消，剩下的是 diagonal damping、smoothness penalty、参数变化项和误差项。只要 alpha/delta 足够吸收 L_F/L_G，且 tau_k、sigma_k 按 beta_k 的规则下降，E_k 就满足类似 (1+1/beta_k)E_{k+1} - E_k <= error terms 的递推。没有误差时，这就是非遍历收缩的来源。
本文最核心贡献不是某个具体算法实例，而是把“反对称速度耦合 + gap-augmented Lyapunov + variable beta scaling”组合成离散分析模板。它本质上是 better inductive bias / geometry design，不是 scaling，不是 data coverage，不是 retrieval，也不是 test-time compute。算法在每步使用更多结构化隐式计算，但理论收益来自几何抵消，而非简单增加计算量。
辅助部分包括半光滑 Newton、CG 子程序、wavelet 特例推导等。这些说明算法可落地，但不是理论核心。实验里看到的稳定性可能部分来自这种更强的隐式子问题求解和参数调优；增益来源不清，不能全部归因于 antisymmetric preconditioner。
需要注意一个细节：Example 6 中 beta 常数给 linear decay 的表述在一般凸、无强凸问题上看起来非常强，实际依赖参数递推和能量定义中的变权结构；其可解释性需要谨慎。它不是通常意义下对距离到解或 objective gap 的无条件线性收敛结论，且误差条件非常严格。
Relation To Prior Work
最接近的技术谱系有三条：PDHG / Chambolle-Pock / Condat-Vu 的 primal-dual splitting；Luo 2022 的 affine constrained primal-dual flow；以及 Apidopoulos et al. 2026 的 preconditioned primal-dual continuous dynamics。本文主要是第三条路线的算法化和扩展。
相对 PDHG，真正差异不是“换了步长”或“用了预条件”，而是预条件器含有 skew off-diagonal velocity coupling。PDHG 的 extrapolation/momentum 通过预测点改善稳定性；本文通过 antisymmetric differential coupling 改变能量守恒-耗散结构。
相对 Nesterov/inertial primal-dual 方法，本文不依赖显式加速项，也不把非遍历 rate 建立在动量估计上。它更像 continuous-time geometry induced discretization，而不是 acceleration recipe。
相对 augmented Lagrangian 非遍历路线，本文避免显式 penalty/dual regularization 主导的 ALM 分析，但代价是每步出现 diagonal+skew strongly monotone 子问题，实际计算复杂度未必更低。
相对 Luo 2022，本文扩展到一般 saddle point 与 smooth+nonsmooth 结构，并显式纳入 inexact implementation。Luo 的思路在约束问题中已有类似 flow/preconditioned 影子；本文的新信息是更系统的 antisymmetric parameterization 和误差鲁棒的非遍历 Lyapunov rate。
Dataset / Evaluation
实验覆盖三个场景：线性约束 least squares、线性约束 l1+l2 composite problem、wavelet image denoising。任务选择基本对应理论覆盖面：线性约束、nonsmooth composite、imaging saddle formulation。它们能验证算法在典型 convex optimization toy/medium-scale setting 下不会只是纸面构造。
但 evaluation 的支撑力度有限。首先，实验规模不大，更多是数值稳定性展示，不是大规模优化系统验证。其次，对比对象主要是 Chambolle-Pock 和 Luo-type 方法，没有系统比较现代 ALM、adaptive PDHG、preconditioned PDHG、operator-splitting variants。第三，参数选择有明显调优成分，例如 heatmap 搜索 alpha_0/delta_0；这会让 observed gain 难以归因。
图像去噪实验展示视觉效果和 optimality measures，但没有清楚回答核心理论 claim：antisymmetric preconditioner 是否在相同计算预算下稳定优于 prior。文中未充分说明每次外层迭代的 inner solve cost 与 baseline 的公平折算。因此实验支持“方法可运行且稳定”，但不足以强支持“总体效率优于标准方法”。
Limitation
第一，方法成立依赖参数条件。Assumption 3 需要 alpha_k、delta_k 吸收 smooth Lipschitz 常数，并要求 beta/alpha、beta/delta 的特定增长关系。实际问题中 L_F、L_G 未必易估，且过保守估计会改变算法行为。
第二，算法把一部分困难转移到子问题求解。一般情形每步要解 strongly monotone diagonal+skew inclusion，不一定有闭式 prox。半光滑 Newton / CG 可以处理特例，但这不是免费的 first-order method。若把 inner iterations 计入总复杂度，增益来源不清。
第三，误差条件可能偏强。为了保持 rate，需要 beta_k B_k R_k 可求和；在 beta_k 线性增长时，内层误差通常要按多项式更快下降。这会导致后期内层求解越来越精确，实际 scalability 可能受限。
第四，理论结果主要是 gap 和 weak subsequential limit，未给出强收敛或更细的 last-iterate distance rate。若解集非唯一，E_k 中的距离项依赖固定 saddle point，实际轨迹选择与稳定性仍有未解释部分。
第五，实验增益归因不清。可能主要来自 scaling / parameter tuning / implicit subproblem solve，而不是反对称结构本身。缺少 ablation：去掉 beta A^*dy 但保持同等 inner solve、改变 beta schedule、固定内层精度、同预算比较。
Takeaway
- 1. 非遍历 primal-dual rate 的一个有效方向不是继续堆 acceleration，而是设计能让 gap 进入 Lyapunov 收缩的预条件几何；antisymmetric velocity coupling 是一个可迁移的机制。
- 2. 对 saddle point 方法，off-diagonal preconditioning 不应只被理解为数值调参。
- 只要保持 skew cancellation，它可以改变可证明的收敛对象，从 averaged gap 转向 last-iterate gap。
- 3. 真正值得后续做的是 adaptive / line-search 版本，以及按总计算量计费的复杂度分析。
一句话总结
这篇论文把连续时间 antisymmetric preconditioned primal-dual dynamics 离散成可处理 smooth+nonsmooth 与 inexact subproblem 的算法框架，核心贡献是在不靠平均迭代的情况下用反对称速度耦合建立 last-iterate primal-dual gap 的 Lyapunov 收缩。