精读笔记

Problem Setting

[New Bounds for the Last Iterate of the Stochastic subGradient Method]（arXiv preprint / 2026-06-24）

这篇论文实际解决的是：固定 horizon 下，标准固定步长 η=Θ(1/√n) 的 projected stochastic subgradient method，最后迭代是否能像平均迭代一样达到 O(1/√n)。更精确地说，作者把问题压到一维凸 Lipschitz 目标上，问已有 O(log n/√n) 最后迭代界里的 log 到底是分析松弛、维度效应，还是 oracle 条件不足导致的真实障碍。

真正困难点在于最后迭代没有平均化的“保险”。平均迭代只需要总误差可求和/可 telescoping；最后迭代则要求从某个好时刻以后，过程不能被噪声重新推离最优子水平集太多。对于非光滑目标，尤其存在平坦最优区间时，次梯度在平坦区内不给恢复力，噪声只要在合适时刻产生罕见大跳跃，就能把最后点推出去。

以前方法卡在两类边界上：通用最后迭代分析得到 O(log n/√n)，但不知 log 是否必要；一维特例结果说明某些良性 oracle 下可以去 log，但不能解释一般二阶矩 oracle。本文揭示的关键矛盾是：固定维度降低了几何复杂性，但不能消除 oracle 在时间或状态上编码“坏事件标签”的能力。

Motivation

已有路线不够的原因是它们混合了两个问题：最后迭代的算法动力学问题，以及随机 oracle 的结构问题。Koren–Segal 的开放问题表面上问固定维度能否去 log，但本文的核心观察是，固定维度本身不是决定因素；噪声是否 i.i.d.、是否不能利用状态/时间选择 rare large jump，才是决定因素。

作者真正抓住的缺口是：条件无偏 + 条件二阶矩有界这个 oracle 假设太粗，它允许非常 adversarial 的条件分布。即使每一步方差受控，oracle 仍可把不同幅度的大跳跃分散到不同时间或不同状态上，每个跳跃概率按 1/j² 缩小，二阶矩不爆，但期望终端误差按调和级数累积出 log。

因此论文不是单纯改进 upper bound，而是在分离“低维几何”和“噪声结构”两种来源：一维 + i.i.d. additive noise 足够去 log；一维 + 仅方差控制不够。

Core Idea

核心思想可以概括为：最后迭代的好坏不是从头到尾直接控制，而是先找到一个平均意义上的好迭代 k*，再证明在足够结构化的噪声下，从 k* 到 n 的退化是 O(η)。这把 last-iterate 问题拆成两部分：平均迭代负责给一个好起点，一维 Markov excursion 控制负责保证之后不会坏太多。

理论上这成立的原因是，在一维凸函数中，任一子水平集外只有左右两个方向；离开子水平集后，次梯度方向具有单调的“向内拉回”结构。作者把这种结构编码成一个单调映射 T，并构造支配真实轨道离开子水平集距离的 one-sided Markov chain。i.i.d. additive noise 使得条件化在 k* 后的未来仍是同分布独立噪声，因此可用 stationary / Foster–Lyapunov 漂移统一控制所有后续时刻。

和 prior 的本质区别在于：prior 多数是全局递推或加权平均式证明，log 来自时间累积；本文正向部分改为“好时刻 + 后续退化上界”，反向部分则证明如果未来噪声可以通过时间或状态带标签，那么这种时间累积不是证明 artifact，而是真实可实现。

Method

第一，标准能量不等式只用于找 k*。这一步解决的是“至少有一个迭代点好”的问题，和平均迭代分析本质相同；它不试图证明最后点好，因此避免了直接 last-iterate 递推里的 log 累积。

第二，条件化在 F_{k*}。这一步解决的是随机阈值 f(X_{k*}) 难处理的问题：条件化后把 q=f(X_{k*}) 当作固定水平，问题变成控制未来轨道超过子水平集 {f≤q} 的正部。为什么需要 i.i.d. 噪声也在这里最清楚：条件化之后未来噪声必须仍然是同一 law 的独立样本，否则支配链无法统一成立。

第三，构造左右 one-sided dominating chains。它解决的是真实 SsGM 轨道在非光滑凸函数外侧如何被次梯度拉回的问题。T_{I,m,η} 把“先由次梯度向内推进、再受噪声扰动”的最坏一维距离更新抽象出来，核心变化是把优化动力学转成单调 Markov 链的 excursion 控制。

第四，Foster–Lyapunov 漂移给 O(η) 退化界。Lyapunov 函数 B(z)=z²/(2η)+2Lz 平衡了噪声二阶矩项和单调 drift；其作用不是精细常数，而是证明无论后续走多少步，超过当前子水平集的期望 excess 都保持 O(η)。

第五，下界用 rare-large-noise harmonic construction。它解决的是“log 是否真实必要”的问题：在状态依赖或时间非齐次的 oracle 中，为每个 label j 安排概率约 1/j²、幅度约 j 的跳跃；每个 label 对终端误差贡献约 η/j，叠加得到 η log(1/η)。

Key Insight / Why It Works

最核心贡献是把 last-iterate 的 log 问题归因到 oracle 分布结构，而不是简单归因到维度或非光滑性。正向结果说明：在一维，只要未来噪声没有状态/时间标签，即 i.i.d. additive，最后迭代从好时刻之后不会显著退化；反向结果说明：只要允许状态或时间携带标签，即使一维、凸 Lipschitz、有界二阶矩，log 也能被构造出来。

真正有效的技术点是 Lemma 10 背后的 conditional excursion bound。它不是常规 SGD 证明里的小改动，而是把“超过随机基准 f(X_{k*}) 的正部”变成左右两条受控 Markov 链的 stationary moment bound。这里的一维 order structure 是核心 inductive bias：凸函数子水平集是区间，区间外的次梯度符号单调，投影也保持序。

Foster–Lyapunov 部分是关键证明工具，但它服务于更核心的结构事实：i.i.d. 噪声无法持续选择“正确标签”的大跳跃；状态/时间依赖噪声可以。也就是说，增益不是来自 scaling、不是更强 smoothness、不是更优步长 schedule，而是来自对噪声信息流的限制。

下界最有杀伤力的 insight 是二阶矩约束无法阻止多尺度罕见事件。幅度 j、概率 1/j² 的设计让每个尺度都合法，但期望终端损失按 1/j 累积。这类构造值得迁移到其他 stochastic approximation 问题：只看 conditional variance 往往不足以排除多尺度 adversarial rare events。

哪些部分可能只是辅助：显式常数、具体区间 [-2,1]、hinge 目标 max{x,0}、M=floor(1/(16η)) 都主要是工程化证明选择；核心不是这些数值，而是 flat optimum + rare jump + deterministic decay over remaining j steps。

Relation To Prior Work

这篇最接近 Shamir–Zhang / Harvey et al. / Jain et al. / Liu–Zhou 的 last-iterate SGD/SsGM 谱系，也直接回应 Koren–Segal 关于 constant dimension tight convergence 的开放问题。与平均迭代理论相比，它研究的不是 oracle complexity 的最优统计率，而是同一算法输出最后点时是否丢 log。

和 Koren–Segal、Liu–Lu 的一维正向结果相比，本文正向结果更一般：任意一维凸 Lipschitz 目标，而不是绝对值或特定 piecewise-linear 类；噪声只需 i.i.d. additive 且二阶矩有限，不需要 sub-Gaussian。真正新增的信息是：一维正向现象不是特定目标的随机游走巧合，而是子水平集 excursion 可控。

和高维 deterministic lower bounds 不同，本文证明 log 不依赖高维构造；即使 d=1，只要 oracle 条件允许状态/时间编码，log 就会出现。这是本质差异。

看似新的 kernel-oracle formulation 本身不是算法创新，而是为了精确区分 state-independence 与 time-homogeneity。实质创新在于把这两个 symmetry 证明为 minimax 意义上都必要：只保留其中一个仍然无法去 log。

Dataset / Evaluation

这是一篇纯理论论文，没有 dataset、benchmark 或实验评估；“evaluation”主要是 upper/lower bound 的匹配性。就理论验证而言，覆盖范围很清楚：正向定理覆盖一维任意凸 Lipschitz 目标、固定步长族 η=Θ(1/√n)、i.i.d. additive noise；反向定理覆盖同一维度、同一步长族、仅二阶矩条件下的两个结构性失败模式。

这些结果确实支撑核心 claim：log 的去除需要比 uniformly bounded variance 更强的 oracle symmetry。尤其下界不是换成高维、不是换成非标准步长，而是在一维标准设置中构造 Ω(log n/√n)，因此对开放问题的回答是实质性的。

但评估边界也很明显：下界依赖随 n/η 增大的噪声幅度，不能说明 uniformly bounded stochastic gradients 下 log 必然存在；正向结果也没有覆盖多维或非 i.i.d. 但实际常见的 sampling noise。

Limitation

最大限制是正向机制高度一维化。左右分支、单调 T、区间子水平集、投影保序，这些都是 d=1 的结构红利；多维中没有自然的 total order，也很难把离开子水平集的方向分解成两个受控 excursion。因此这不是一个可直接推广的通用 last-iterate 技术。

第二，i.i.d. additive noise 假设很强。它排除了许多实际 stochastic oracle：数据依赖噪声、状态依赖梯度估计、非平稳采样、adaptive sampling、Markovian noise。论文证明的是在这个强 symmetry 下 log 消失，而不是一般实际训练过程都会如此。

第三，下界的噪声幅度是 Θ(1/η)=Θ(√n)。这在二阶矩意义上合法，但和 uniformly bounded gradient/noise 的模型不同。作者也明确指出它没有解决 almost-sure bounded stochastic gradients。换言之，下界把问题从维度转移到了 oracle tail/rare-event 结构上。

第四，常数和 explicit bound 不是主要价值，也不应过度解读。Theorem 2 的常数依赖 L、σ、初始距离和步长常数，证明目标是去 log；实际 sharp constant 文中未充分说明。

第五，固定 horizon 固定步长是本文设定核心；anytime decreasing stepsize 或非标准步长策略的比较不是本文重点。

Takeaway

• 第一，最后迭代是否最优不能只看维度和凸性；oracle 的 distributional symmetry 是一等公民。
• 仅有条件二阶矩控制太弱，会允许多尺度 rare-event 累积。
• 第二，一维下去 log 的正确证明范式不是强化单步递推，而是“平均分析找好点 + excursion 稳定性控制后续退化”。
• 这个思路可能迁移到其他存在有序结构或可构造 Lyapunov drift 的问题。

一句话总结

这篇论文把一维 SsGM 最后迭代的 log 损失从“可能的分析 artifact”重新定位为“oracle 结构不足导致的真实现象”，并证明 i.i.d. additive noise 是去 log 的关键 symmetry，而仅有有界方差即使在一维也不够。