精读笔记

Problem Setting

这篇论文实际处理的是 stochastic smooth convex-concave minimax / monotone VI 中的 last-iterate convergence，且重点放在 constrained feasible sets 上。问题不是如何得到 averaged iterate 的 O(T^{-1/2}) ergodic guarantee，而是最终输出的 u_T 是否在标准 bounded-variance oracle 下有非渐近保证。

真正困难点在于 stochastic noise 对 saddle dynamics 的影响是结构性的。EG/OGDA 在 deterministic monotone setting 中有良好的 last-iterate 行为，但加入不衰减噪声后，bilinear game 这种最简单情形也会出现最终迭代不收敛。也就是说，算法的旋转稳定性在随机扰动下不够强，单靠 monotonicity 和 Lipschitzness 不足以形成 last-iterate contraction。

以前方法卡在两个地方：一类通过 mini-batch / variance reduction 改 oracle，本质是减少噪声；另一类通过 anchoring 或 adaptive perturbation 改 dynamics，但 constrained setting 下 rate 弱，且常需要 compact domain、Hessian Lipschitz 或更强结构。关键矛盾是：要稳定 last iterate 需要强收缩；但原问题只是 convex-concave，强行加入收缩又会引入偏差。

Motivation

作者的切入点很清楚：既然 vanilla S-EG/S-OGDA 失败的根因是噪声下缺少足够稳定的吸引机制，那么与其在 oracle 层面降噪，不如直接在 operator 层面制造强单调性。这样可以保留 single-loop、standard SFO、projection-based EG/OGDA 的简单结构。

已有路线缺的是一个同时满足三点的机制：不要求额外采样结构、不依赖紧可行域、还能给 constrained last iterate 做非渐近分析。anchoring 方法看起来相近，但它通常是直接改更新式，把 iterates 拉向 reference point；本文的 perturbation 是改问题本身，把 EG/OGDA 解释为在 perturbed VI 上运行。这一点对证明很重要，因为强单调性可以直接进入 VI recursion。

核心缺口不是“有没有一个稳定 trick”，而是能否把稳定 trick 的 bias 定量转回原问题 stationarity。本文的主要工作量实际上就在这个转译链条：perturbed distance convergence -> original restricted gap / gradient norm。

Core Idea

核心思想是对原始目标加小的二次项：F_τ(x,y)=F(x,y)+τ/2||x||^2-τ/2||y||^2。对应 operator 变成 W(u)=V(u)+τu。这个改动把 monotone VI 变成 τ-strongly monotone VI，于是 stochastic EG/OGDA 的 one-step recursion 中出现真正的 contraction 项。噪声项仍然存在，但可以通过递减 stepsize 累积控制。

这不是一个新的优化器，而是改变了优化对象：不直接解原问题，而是解一个随 τ 逼近原问题的 strongly monotone surrogate。τ 大时收缩强但 bias 大；τ 小时 bias 小但抗噪弱。整篇论文的 rate 都来自这个 tradeoff 的参数平衡。已知 horizon 时可以选 τ≈T^{-1/4} 得到 O(T^{-1/4}) gap；anytime 时 τ_t 递减，需要额外控制 u_{τ_t}^* 的漂移，rate 因此变慢。

和 prior 的本质区别在于它不依赖 variance reduction，也不依赖额外 oracle 调用；它把 last-iterate convergence 的问题改写成 strongly monotone stochastic approximation 加 perturbation bias 的问题。这是一个很干净的 reduction。

Method

1. Quadratic perturbation：解决原始 monotone operator 没有收缩的问题。加入 τu 后，operator 强单调，EG/OGDA 的递推能产生距离到 u_τ^* 的 contraction。核心变化是从“控制旋转动态”变成“控制带收缩的随机递推”。

2. Perturbed S-EG / PS-OGDA：算法层面几乎不增加复杂度，只是在 stochastic gradient estimate 上加 τ_t u_t。它在解决的问题是如何保留 vanilla S-EG/S-OGDA 的 single-loop 结构，同时获得 last-iterate 稳定性。这里的贡献不是工程实现，而是证明这种最小改动足够。

3. Distance-to-gap conversion：因为算法收敛到的是 perturbed saddle point，不是原问题 saddle point，必须把 E||u_t-u_τ^*||^2 转成原始 restricted primal-dual gap。这里出现 sqrt(distance) + τ 的结构，也直接决定了最终 rate。这个转换是 constrained setting 下的关键，但也是 rate 损失来源。

4. Anytime diminishing perturbation：当 T 未知时，τ_t 和 η_t 同时下降。它解决 horizon-dependent τ 需要预知 T 的问题，但引入 moving target u_{τ_t}^*，需要额外控制 perturbed solution 的 drift。general constrained case 因此只能得到 O(T^{-1/5})。

5. Unconstrained PS-EG reference tracking：这是一个单独分析，不经过 moving perturbed saddle point，而是让 stochastic trajectory 跟踪 deterministic perturbed EG trajectory。它绕开 restricted gap 与 uniform boundedness 的技术瓶颈，因此可恢复 O(T^{-1/4}) anytime gradient norm。但这个机制依赖 unconstrained gradient norm stationarity，不能直接搬到 constrained setting。

Key Insight / Why It Works

最核心的 insight 是：随机 last-iterate 不稳定不是 EG/OGDA 的 extrapolation 机制失效，而是 monotone problem 缺少能抵抗持续噪声的强收缩。二次 perturbation 给 operator 注入了一个全局线性 restoring force，使得每一步递推有类似 (1-η_t τ) 的收缩。只要 ∑η_t^2 控制噪声，且 τ∑η_t 足够大，last iterate 就能靠近 perturbed saddle point。

真正有效的部分是 strong monotonicity injection。PS-EG/PS-OGDA 本身没有新的信息流，也没有更好的梯度估计；增益不是来自 scaling、data coverage、retrieval、memory reuse 或 test-time compute，而是来自更强的 problem geometry。换句话说，这是一篇典型的 regularization-as-stabilization 论文。

rate 的来源可以直接分解：optimization error 到 u_τ^* 的 mean-square 距离大约由 contraction-noise 平衡决定；original problem 的 stationarity 再付出 perturbation bias τ；restricted gap 还要付出平方根转换损失。horizon-known O(T^{-1/4}) 基本是把 distance O(T^{-1/2}) 和 τ=T^{-1/4} 平衡出来的，不是某个复杂 algorithmic trick。

PS-OGDA 的分析比 PS-EG 更重，是因为 optimistic recursion 多了 consecutive operator variation，需要 Lyapunov 中额外放入 ||W(u_{t-1/2})-W(u_{t-3/2})||^2。这是技术负担，不是新的机制。unconstrained PS-EG 的 sharper anytime result 更有意思，因为它说明此前 O(T^{-1/5}) 的瓶颈部分来自 proof framework 和 stationarity conversion，而不完全是算法本身。

我会把本文的实质贡献判断为：用最小 perturbation 把 constrained stochastic last-iterate convergence 降到 strongly monotone stochastic approximation，并把 restricted gap 的偏差控制做完整。方法本身不复杂，贡献主要在问题重写和证明闭环。

Relation To Prior Work

最接近的是 stochastic EG/OGDA、anchored methods、regularized / perturbed methods for monotone VI，以及 variance-reduced stochastic minimax。

和 variance reduction / mini-batch 路线的本质差异是：本文不降低 oracle noise，而是提高 dynamics 对噪声的稳定性。因此它在 oracle model 上更弱、更干净，但 rate 也不能达到使用更强 oracle 的 O(T^{-1/3}) unconstrained result。

和 anchoring 方法的关系最微妙。形式上，当 anchor 在 0 附近时，perturbation 看起来像 shrinkage；但本文强调 PS-EG 是在 perturbed operator 上做 EG，第二步的 shrinkage 作用在 extrapolated point 上，而 anchoring 是直接修改 update drift。这个差异在分析上有意义：前者可以直接调用 strongly monotone VI 结构，后者更像 algorithmic regularization。

和 Abe et al. / Ito et al. 这类 constrained last-iterate 工作相比，本文的新增信息是：不要求 compact feasible domain 也能给 restricted gap 保证，并且在 compact case 下去掉或改善一些较慢 rate / log factor。这里的创新是理论覆盖面和 rate 改善，不是算法结构复杂度。

看似新的部分中，quadratic regularization 本身当然不是新思想；真正新增的是把它用于 standard bounded-variance stochastic EG/OGDA 的 constrained last-iterate 分析，并把 horizon-dependent、anytime、unconstrained sharper case 放在同一框架下。

Dataset / Evaluation

这篇是理论优化论文，几乎没有严格意义上的 dataset / benchmark evaluation。文中的实验主要是 bilinear stochastic toy problem，用来展示 vanilla S-EG/S-OGDA 在噪声下不收敛，而 perturbed variants 收敛；以及 τ 越大收敛越快但 asymptotic bias 越大的现象。

这些实验支持的是机制直觉，而不是广泛 empirical claim。它们不能验证 constrained large-scale minimax、GAN、robust learning 或真实 saddle-point workloads 中的实际优势，也不能说明常数、projection 代价、τ tuning 在真实问题中是否可接受。

因此 evidence 主要来自 theorem，而不是实验。benchmark 没有覆盖跨场景、多任务、真实世界部署，也没有检验和 variance reduction / anchoring 在相同 oracle budget 下的实际性能差异。对于一篇 math.OC 理论论文这是可以接受的，但不能把 toy result 解读成方法经验上优于 prior。

Limitation

第一，restricted primal-dual gap 是必要但也削弱 claim 的度量。非紧可行域下它只在选定 compact comparison sets 上定义；虽然作者用 uniform mean-square boundedness 构造包含 saddle point 的集合，但这不等价于全局 primal-dual gap。实际应用中这个 restricted set 的语义并不总是清楚。

第二，rate 受 τ bias 和 square-root conversion 限制。distance 收敛可以到 O(T^{-1/2})，但 gap 只到 O(T^{-1/4})，说明核心瓶颈在 stationarity translation，而不是 stochastic recursion 本身。若不能改进 distance-to-gap 转换，单纯调算法很难突破。

第三，anytime constrained rate O(T^{-1/5}) 明显暴露了 moving target 分析的代价。τ_t 下降时 u_{τ_t}^* 漂移，证明需要把 drift、noise、contraction 同时平衡。这个 rate 是否 tight 文中未充分说明，很可能部分是 proof artifact。

第四，PS-OGDA 的 sharper anytime gradient norm 没有得到。文中解释是 recursive inequality 有额外 variation terms，reference-tracking 不好迁移。这意味着 OGDA 的理论优势在该框架下没有完全体现，PS-OGDA 更像被统一框架顺带覆盖。

第五，方法没有解决更强 oracle 下的最优 rate 问题。和 variance-reduced Halpern-type 方法相比，它的优势是 oracle 简单和 constrained coverage，但不是最快。若应用场景允许 batch 或 finite-sum structure，本文方法未必是最优选择。

第六，τ 的选择仍是核心敏感点。已知 horizon 的最优 rate 依赖 τ≈T^{-1/4}；anytime schedule 虽然避免预知 T，但更慢。实际中 τ 太大 bias 明显，τ 太小抗噪不足，这个 tradeoff 没有自适应解决。

Takeaway

• 1. 对 stochastic minimax last iterate 来说，稳定性可以通过改变 operator geometry 获得，而不一定要靠 variance reduction。
• 给 monotone operator 注入强单调性是最直接、最可迁移的机制。
• 2. 这篇论文真正推动的是 constrained standard-oracle last-iterate theory，而不是提出复杂算法。
• 它说明 vanilla EG/OGDA 只要在 perturbed problem 上运行，就能得到比 anchoring/perturbation prior 更干净的 rate。

一句话总结

这篇论文把 constrained stochastic minimax 的 last-iterate 收敛问题重写为“强单调 perturbation 下的稳定随机递推 + perturbation bias 控制”，以最小算法改动给出了标准 oracle 下 PS-EG/PS-OGDA 的系统性 last-iterate 保证。