精读笔记

Problem Setting

《An Improved Analysis of the Last Iterate of the SubGradient Method in the Plane》（arXiv preprint / 2026）。这篇论文实际解决的是：对二维 convex Lipschitz optimization，常步长 projected subgradient method 返回最后一个 iterate 时，是否仍会像高维 worst-case theory 那样损失一个 log n。困难点在于 last iterate 没有平均化带来的 telescoping 保护，单个末端点可能被早期或中期的坏方向影响；而高维 tight examples 正是通过不断引入新正交方向让误差累积成 log n。以前的标准分析只能给 averaged/best iterate 的 O(1/sqrt(n))，或者给 last iterate 的 O(log n / sqrt(n))；一维能去掉 log 主要靠 order structure，二维没有这个结构。关键矛盾是：subgradient trajectory 可以局部振荡、projection 也可能改变方向，但二维空间又不允许无限制造彼此正交的新坏方向。

Motivation

已有路线不够的原因很明确：dimension-free last-iterate theory 把高维下界当作主导现象，但其 tightness 依赖维度随 n 增长；这不能回答 fixed dimension。另一方面，一维证明依赖实线顺序，无法迁移到平面。作者的核心观察是，高维 log loss 的来源可能不是 subgradient method 的 last iterate 本身，而是高维几何允许轨迹持续进入新方向；如果在平面中能证明轨迹一旦从某个好 sublevel 出发，就只能在一个窄管道内移动，那么 log loss 就没有空间出现。关键缺口不是新的 stepsize policy，而是常步长下 last iterate 的低维几何不变量。

Core Idea

核心思想是用“参考线段”替代“参考最优点”。标准 subgradient analysis 用到最优点的平方距离势函数，但这对 last iterate 太粗，因为低 sublevel 可能沿某个方向很长，离一个固定最优点远并不意味着函数值高。论文改用由最优点 0 和某个已知低误差点 y1 组成的线段 I=[0,y1]；凸性保证整条线段都在低 sublevel 内，因此只要控制 iterate 到这条线段的距离，就能控制函数值。

本质区别在于，它不再试图证明轨迹靠近某个 minimizer，而是证明轨迹靠近一条“已经被函数值认证过”的低值几何结构。这是更贴合 last iterate 的 inductive bias：last iterate 不一定回到最优点附近，但在二维中它不能稳定地离开低值线段太远。这个建模方式把问题从时间累积误差转成平面中的横向偏离控制。

Method

方法可以压缩成三个机制。首先，标准 telescoping 只用来找一个中间好点 xs，使 f(xs)-f* 达到 averaged-rate 量级；这一步解决的是 last iterate 缺少初始低误差锚点的问题，本身不是创新。

其次，从 xs 开始重标定尾段轨迹，把最近 minimizer 平移到 0，定义 F(y)=f(y+x*)-f*。选取 A=max{eta L^2, F(y1)}，构造 I=[0,y1]。这一步的作用是把“已经好”的函数值转成一个可用的凸几何对象：I 全部落在 {F<=A} 内。

第三，证明所有尾段点到 I 的距离不超过 eta L。关键递推是 rt+1 <= max{rt, eta L}。它解决的是 last iterate 可能逃离低 sublevel 的问题；核心变化是把 subgradient step 的下降性质投影到垂直于 I 的方向上，而不是只看到原点的径向距离。

Key Insight / Why It Works

最关键的 insight 是：二维中，一条线段的正交方向只有一个维度；一旦点在 segment 的内部投影区间内，离线段的距离就是一个带符号横向坐标的绝对值。由于当前点函数值高于线段上的投影点，subgradient 在横向方向上的分量必须指向降低横向偏离的方向；再结合 ||h||<=L，单步最多 overshoot eta L。因此横向距离不能增长到 eta L 以上。

这不是 scaling，也不是更好的步长设计；它是一个低维 latent geometry argument。论文真正贡献在 Lemma 7：把 last-iterate 控制归结为平面中 subgradient 对低 sublevel segment 的横向收缩。Claim 8 的 averaged-bound anchor 是必要但常规的辅助。projection non-expansiveness、Lipschitz-to-function conversion 也都是标准工具。

值得注意的是，这个机制非常几何化，不是一般 Hilbert space 论证。它解释了为什么高维 log lower bound 不能直接说明二维：高维坏例子需要不断切换横向方向，而二维只有一个横向自由度，subgradient inequality 会迫使该自由度被压回 eta L 管道内。

Relation To Prior Work

最接近的是三条线：经典 Shor/Polyak averaged 或 best iterate 分析、Shamir-Zhang/Harvey 等 last-iterate log-loss 分析、以及 Zamani-Glineur 对常步长 last iterate 的高维 exact worst-case rate。论文不是提出新算法，也不是优化 stepsize schedule；它属于 subgradient method last-iterate finite-time analysis 的固定维度分支。

和 prior 的本质差异在于势函数选择。经典分析看相对 minimizer 的平方距离；高维 tight analysis 关注跨正交方向累积；一维结果靠 order structure。本文用低 sublevel 中的线段作为 reference object，把平面几何引入 last-iterate analysis。看似只是 proof trick，但它确实新增了信息：last iterate 的坏行为不只由函数值和步长决定，还由低 sublevel 的几何维度决定。

已有思想的重组部分是 telescoping 找好点、projection non-expansiveness、Lipschitz bound；实质创新是用 reference segment 和一维正交补控制尾段逃逸。

Dataset / Evaluation

没有 dataset / empirical evaluation；这不是缺陷，因为论文 claim 是纯理论 worst-case upper bound。评价标准就是 theorem 是否覆盖目标设定：二维、convex Lipschitz、closed convex feasible set、constant stepsize、arbitrary subgradient selection、finite horizon。覆盖面相当干净，且比依赖 tie-breaking 或 smoothness 的结果更强。

但 evaluation 的局限也明确：它只验证 planar upper bound，不提供 matching lower bound，不说明常数是否最优，也不说明 d=3 或一般固定 d 的真实行为。文中没有实验，也不需要实验；如果把它理解为实践中 last iterate 会更好，那是过度外推。

Limitation

最大限制是二维性几乎不可移除。论文自己也指出唯一用到 d=2 的地方是 Lemma 7，但这恰好是整个 proof 的发动机。正交补一维使得横向偏离可由单个标量控制；在 d>2 中，subgradient 可能只压缩当前偏离方向，却无法阻止轨迹在横向子空间换方向漂移。当前 argument 没有给出处理这种旋转自由度的工具。

第二，结论是 order-optimal 而非 sharp。常数没有优化，eta* 依赖 dist(x1,X*)/L 的比例，实际使用中通常不知道该量；不过这不影响 asymptotic order claim。

第三，论文没有证明二维下 O(1/sqrt(n)) 是 tight 的 last-iterate lower bound，虽然从一般 Lipschitz convex optimization 的信息论下界可预期该量级无法整体改进，但针对该 exact setting 的 tight characterization 仍未完成。

第四，方法可能只是把问题从“控制点”转移到“寻找合适 reference convex object”。在二维线段足够；高维若要推广，reference object 可能需要随轨迹自适应增长维度，届时是否还能避免 log n 文中未充分说明。

Takeaway

• 最值得记住的不是 bound 本身，而是 proof bias：last iterate 不一定要靠近最优点，只要靠近一个低 sublevel 内的几何证书即可。
• 高维 log loss 的本质可能是方向复杂度，而不是常步长 last iterate 的必然缺陷；固定维度分析应显式利用低维几何，而不是套 dimension-free worst-case template。
• 后续真正值得做的是找到 d>2 中替代 reference segment 的对象和势函数，控制横向多维漂移；如果能做到，Koren-Segal 的固定维度问题可能沿“sublevel geometry + tube control”路线推进。
• 这篇论文推动的是分析技术，而不是算法设计；它说明对于经典方法，改变观察轨迹的几何对象也能消除看似 tight 的 logarithmic artifact。

一句话总结

这篇论文在 subgradient method last-iterate 理论中给出一个二维几何型 proof，证明高维常步长 log loss 在平面中不是本质现象，核心贡献是用低 sublevel 参考线段控制尾段轨迹的横向逃逸。