技术摘要：超越最优速率的随机优化：轨迹自适应停止规则

1. 问题定义

本文探讨了随机梯度下降（SGD）在强凸优化理论分析中存在的一个根本性脱节。标准的理论保证是**事前（ex ante）**的：它们在算法运行前指定一个确定的时界 $T$，并提供关于该特定时刻优化误差的高概率界限。然而，在实践中，停止决策是根据观察到的演化轨迹（例如，监测验证损失或梯度范数）自适应地做出的。

这种不匹配产生了一个认证问题（certification problem）：

1. 有效性失效： 为固定时间 $T$ 证明的高概率界限，通常并不适用于根据观测轨迹选定的数据依赖型停止时间 $\tau$。停止时间与随机波动相关联，而基于有利波动进行的选择会使原始的概率保证失效。
2. 保守性： 为了保持有效性，可以通过反转最坏情况下的界限来预先计算一个时界 $T_\epsilon$，以找到何时误差保证低于目标 $\epsilon$。然而，由于这些界限是基于最坏情况假设推导出来的，$T_\epsilon$ 通常过于保守，对于特定的实际运行过程而言，所需的迭代次数远多于实际需要。

本文旨在通过构建随时有效（anytime-valid）、轨迹自适应的置信序列来弥补这一差距。这些序列是关于优化误差（平方距离到优化器或次优性）的可观测上界，能够同时在所有时间步长内保持有效，从而允许算法在达到预设精度得到认证时立即停止，且不牺牲统计有效性。

2. 方法论

作者将 SGD 轨迹建模为一个序列实验，其中迭代过程和随机梯度提供了关于未知优化误差的证据。核心方法论涉及构建置信序列（可观测的、依赖于轨迹的上界），这些序列对所有 $t \ge t_0$ 同时保持有效。

2.1. 核心概率工具

其构建依赖于两种针对 SGD 递归动力学进行适配的概率技术：

• 一致时间 Hoeffding 论证： 这是一种使用指数超鞅（exponential supermartingales）和“缝合”（stitching，即在内在时间的二进标度上分配误差概率）的标准方法，用以推导出在时间上一致成立的界限。
• 一致时间经验 Bernstein 不等式： 一种针对具有随时间变化的条件均值且可预测范围可能无界增长的自适应过程的新颖扩展。这至关重要，因为 SGD 中方向梯度噪声项的范围随与优化器距离的变化而缩放。作者开发了一种“缝合”论证，能够同时适应累积二次变分（已实现方差）和运行中的可预测范围。

2.2. 性能度量

本文为两种特定的性能度量构建了置信序列：

1. 到优化器的平方距离 ($Z_t = \|x_t - x^*\|^2$)： 衡量最后一次迭代（last-iterate）精度的度量。
2. 加权平均次优性 ($\bar{F}_t$)： 衡量线性加权平均迭代的次优性，已知该度量可以达到最优收敛速率。

2.3. 用于可观测性的递归构建

一个关键的技术挑战是，理论界限依赖于未知量（例如真实的距离 $Z_t$ 或优化器 $x^*$）。为了使这些界限完全可观测，作者采用了递归支配策略：

• 他们从初始距离的一个可观测上界 $R_0$ 开始。
• 他们使用置信序列本身来限制后续步骤中的未知距离（例如，用之前计算的上包络 $\hat{U}_s$ 代替 $Z_s$）。
• 这种“自我定位（self-localizing）”的构建确保了用于浓度不等式的内在时间（方差代理）随着算法的收敛而缩小，从而保持了最优的 $1/t$ 衰减速率。

2.4. 小批量（Minibatch）扩展

该方法被扩展到了小批量 SGD。对于经验 Bernstein 界限，作者利用了每个小批量内的已实现二阶矩结构。他们不再依赖统一的最坏情况方差代理，而是使用每个小批量梯度已实现的二阶矩矩阵的最大特征值，从而使界限能够适应观测数据的几何特性。

3. 核心贡献

1. 轨迹自适应置信序列： 本文为强凸随机优化中的平方距离和加权平均次优性构建了完全可观测的置信序列。这些序列在时间上同时有效，实现了经过认证的自适应停止。
2. 具有自适应性的最优速率： 所构建的界限在最坏情况下达到了最优的 $O(1/t)$ 衰减速率（除了由于一致时间有效性而固有的迭代对数因子）。至关重要的是，它们能适应已实现的随机梯度，通常比最坏情况的预测更紧凑。
3. 精炼的经验 Bernstein 界限： 作者开发了一种新的、针对具有增长可预测范围的过程的一致时间经验 Bernstein 不等式。这使得置信序列可以用已实现的梯度平方量级替换固定的最坏情况方差代理，从而产生更尖锐的界限，且依赖于特定的轨迹。
4. 小批量自适应： 该框架扩展到了小批量 SGD，其中经验 Bernstein 界限能够适应每个小批量的已实现二阶矩结构，从而随着小批量规模的增加提高置信序列的收敛性。
5. 递归自我定位： 本文引入了一种递归构建方法，利用置信序列来限制所需方差代理的未知距离，确保界限保持可观测并保留最优衰减速率。

4. 结果

4.1. 理论保证

• 基于 Hoeffding 的界限： 在条件亚高斯噪声下，界限按 $O(\frac{\log(1/\alpha) + \log \log t}{t})$ 衰减。
• 经验 Bernstein 界限： 在梯度有界的情况下，界限适应已实现的梯度量级。领先项与已实现的二阶矩成比例，且额外的范围项以更快的速率（$O(t^{-3/2})$）衰减。
• 停止规则： 本文定义了停止时间 $\tau_\epsilon = \inf \{t : \hat{U}_t(\alpha) \le \epsilon\}$。命题 1.6 证明了这些停止规则是有效的：以至少 $1-\alpha$ 的概率，如果算法停止，返回的迭代值满足精度要求。

4.2. 数值实验

实验在包含真实世界（Covertype）和合成数据集的支持向量机（SVM）问题上进行。

• 认证速度： 轨迹自适应停止规则比源自最坏情况界限的自然确定性时界提前数个数量级完成了目标精度的认证。
  • 在一项实验中，经验 Bernstein 界限比最坏情况基准提前 312 倍认证了目标精度。
  • 基于 Hoofding 的自适应界限比最坏情况基准提前 6.1 倍完成了认证。
• 小批量效应： 随着小批量大小 $b$ 的增加，自适应界限与最坏情况界限之间的差距扩大。随着 $b$ 的增加，经验 Bernstein 界限回收了最坏情况界限与真实值之间越来越多的份额。
• 鲁棒性： 经验 Bernstein 界限被证明对问题常数（如梯度界限 $G$ 或初始距离 $R_0$）的保守高估具有鲁棒性。这种误设的影响主要是瞬态的，会随着轨迹依赖项的累积而消失。
• 单次遍历有效性： 这些改进在真正的单次遍历机制（不带放回地处理有限数据集）中依然存在，证实了其收益并非来自对经验分布的重采样伪影。

5. 意义与主张

本文声称通过提供一个理论框架，解决了随机优化中的“认证问题”，在该框架下，不断演化的轨迹本身决定了何时取得了足够的进展，且具备统计有效性。

• 超越固定时界： 这项工作超越了传统的“事前（ex ante）”分析，提供了一种既严谨又具自适应性的在线停止机制。
• 实际效率： 其主要意义在于实践：提出的停止规则可以比源自最坏情况界限的确定性时界减少数个数量级的迭代次数，且不牺牲统计保证。
• 对已实现数据的自适应： 不同于仅依赖迭代次数和全局参数的一致时间保证，这些置信序列能够适应已实现的随机波动以及特定问题实例的几何特性。
• 研究范围有限： 作者指出，虽然这些界限比最坏情况基准显著更紧凑，但置信序列与真实值之间仍存在残余差距。他们提出了一个开放性问题，即是否可以通过对 SGD 动力学的更尖锐分析来缩小这一差距。本文重点讨论的是强凸目标，并未声称解决了非凸或一般凸设置下的停止问题（尽管文中引用了相关领域的前期工作）。

总之，本文提供了一种严谨、完全可观测且具有自适应性的方法，用于认证 SGD 运行的精度，使从业者能够在统计保证的前提下，一旦目标精度得到认证便立即停止算法，而不是依赖于过度保守的预计算时界。