跳转至

Understanding Schedule-Free Methods in Nonconvex Optimization: Rate Guarantees and Escaping Saddles

会议: NeurIPS 2026
arXiv: 2607.09167
领域: 优化/理论
关键词: Schedule-Free 优化、非凸优化、收敛率界、严格鞍点规避、李雅普诺夫分析

一句话总结

通过建立连续时间极限常微分方程与离散李雅普诺夫函数，严格证明了标准形式的 Schedule-Free GD 与 SGD 在非凸光滑目标下达到一阶最优收敛率，并在微小扰动下几乎必然规避严格鞍点。

研究背景与动机

现代深度学习模型训练高度依赖精心调优的学习率调度器（如余弦退火、线性预热与阶段式衰减等），但超参数搜索成本昂贵且泛化效果往往受预设轮数强绑定。针对这一痛点，近年来提出的 Schedule-Free 优化方法通过在基础优化器之上融合动量插值与动态迭代平均技术，试图彻底摆脱对人工学习率调度的依赖，并在大规模视觉与语言模型基准（如 AlgoPerf）上展现出匹敌甚至超越精调调度器的实证性能。

然而，Schedule-Free 方法坚实的实证表现与理论保证之间存在严重脱节。现有收敛性分析大多局限于凸优化场景；少数试图迈向非凸区间的早期尝试要么依赖严苛且不切实际的算法改动（例如要求在每次迭代中对动量参数进行随机重采样），要么给出的收敛速率极其次优（例如在标准均匀平均权重下仅能给出对数级上界），甚至分析仅在退化到原始平均的特定边界情况下勉强成立。此外，算法实际部署时所采用的评估平均序列与实际计算梯度的序列在理论性质上究竟存在何种差异，在非凸景观下始终缺乏系统刻画。

针对这一理论空白，本文的目标是不引入任何人工算法变形，直接对标准形式的 Schedule-Free 梯度下降（SF-GD）和随机梯度下降（SF-SGD）展开严格的非凸收敛分析。研究者敏锐地观察到，Schedule-Free 动力系统在连续时间极限下具有极其优美的几何结构，其本质是一个耦合了时间衰减阻尼的常微分方程。核心 idea：以连续时间极限常微分方程（SF-ODE）为几何指引构造离散李雅普诺夫势函数，证明标准 Schedule-Free 梯度位置序列达到一阶非凸最优收敛率，并将其形式化为非自治动力系统证明在单次微小扰动下几乎必然逃逸所有严格鞍点。

方法详解

整体框架

Schedule-Free 方法在离散迭代中同时维护三个耦合序列：梯度计算位置序列 \(\bm{y}_k\)、基础优化器累积更新序列 \(\bm{z}_k\) 以及模型最终评估采用的加权平均序列 \(\bm{x}_k\)。输入为初值 \(\bm{x}_0 = \bm{z}_0\)、固定常数 \(\beta \in [0, 1)\)、学习率序列 \(\{\gamma_k\}_{k \geq 0}\) 以及平均衰减率序列 \(\{c_{k+1}\}_{k \geq 0}\)。在每一次迭代中，算法首先在 \(\bm{z}_k\) 与 \(\bm{x}_k\) 之间做凸组合得到 \(\bm{y}_k\)，在 \(\bm{y}_k\) 处查询（随机）梯度并更新基础序列得到 \(\bm{z}_{k+1}\)，最后更新滑动平均序列 \(\bm{x}_{k+1}\)。

为解析这一交织系统的动力学本质，本文先考察其连续时间极限。令学习率步长 \(\gamma \to 0\) 且取标准权重 \(c_{k+1} = \frac{1}{k+1}\)，通过在连续时间中引入时间反比衰减函数 \(a(t) = 1/t\)，推导出描述该系统的极限常微分方程（SF-ODE）。进一步地，通过将 \(\bm{z}_k\) 消元，将离散 SF-GD 严格等价表述为一个在相空间 \(\mathbb{R}^d \times \mathbb{R}^d\) 上的非自治动力系统，进而结合性能估计问题（PEP）框架全面剖析评估序列 \(\bm{x}_k\) 的最坏情况行为。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["初始参数 x0 = z0<br/>超参数 beta, 学习率 gamma_k, 权重 c_{k+1}"] --> Dyn["非自治动力系统状态迭代<br/>(y_k, x_k) in R^d x R^d"]
    Dyn --> ODE["连续时间极限映射 (SF-ODE)<br/>z' = -grad f(y), x' = (z - x)/t"]
    ODE --> Lyap["李雅普诺夫势函数分析<br/>V_k = f(y_k) - f* + alpha_k ||z_k - x_k||^2"]
    Lyap --> OptRate["一阶最优收敛率保障<br/>SF-GD: O(1/T), SF-SGD: O(1/sqrt(T))"]
    Lyap --> Saddle["单次扰动严格鞍点规避<br/>非稳定流形测度为零排除局部极大/鞍点"]
    OptRate --> PEP["PEP 数值性能估计评估<br/>揭示评估序列 x_k 与梯度序列 y_k 的理论界差异"]
    Saddle --> PEP

关键设计

1. 连续时间极限 SF-ODE 导引与李雅普诺夫函数构造 现有离散分析难以直接推进的核心痛点在于，三序列之间交织耦合，目标函数值与距离项的交叉内积项极难通过常规代数不等式消除。本文通过将离散步长推向极限，建立了 SF-ODE 动力系统： $$ \bm{y} = (1-\beta)\bm{z} + \beta\bm{x}, \quad \dot{\bm{z}} = -\nabla f(\bm{y}), \quad \dot{\bm{x}} = \frac{1}{t}(\bm{z} - \bm{x}). $$ 尽管该系统在 \(t=0\) 处存在奇异性，但论文证明该奇异点是完全可去奇点，初值问题在连续延拓下严格良定。更为关键的是，SF-ODE 自然诱导了一个结构极简的能量函数 \(\mathcal{L}(t) = f(\bm{y}(t)) - f^* + \frac{\beta}{2t}\|\bm{z}(t) - \bm{x}(t)\|^2\)。对时间求导后，交叉内积项 \(\beta \langle \dot{\bm{z}}, \dot{\bm{x}} \rangle\) 发生完美对消，直接导出耗散关系 \(\dot{\mathcal{L}} \leq -(1-\beta)\|\nabla f(\bm{y})\|^2 \leq 0\)。这一连续域上的守恒律为离散非凸分析提供了至关重要的理论蓝图。

2. 离散李雅普诺夫势函数的精确系数匹配与最优收敛率保障 连续耗散律迁移至离散迭代的最大挑战是离散差分引入的二阶余项与非均匀步长。针对任意满足预热衰减率与 log-concave 性质的学习率序列，本文设计了匹配的离散势函数序列 \(V_k = f(\bm{y}_k) - f^* + \alpha_k\|\bm{z}_k - \bm{x}_k\|^2\)。通过逆向精确求解抵消内积项 \(\langle \nabla f(\bm{y}_k), \bm{z}_k - \bm{x}_k \rangle\) 的代数方程，构造出权重递推式： $$ \alpha_k = \frac{\beta c_k \left(1 - \gamma_{k-1} L (1 - \beta + \beta c_k)\right)}{2\gamma_{k-1}(1 - c_k)^2}, \quad \forall k \geq k_0 + 2. $$ 在此权重下，离散势函数满足期望单调递减引理 \(\mathbb{E}[V_{k+1}] - \mathbb{E}[V_k] \leq -\frac{\gamma_k(1-\beta)}{2}\mathbb{E}[\|\nabla f(\bm{y}_k)\|^2] + \mathcal{O}(\gamma_k \sigma^2)\)。由此直接导出：确定性 SF-GD 取得 \(\min_{k<T} \|\nabla f(\bm{y}_k)\|^2 \leq \mathcal{O}(1/T)\)，在 \(L\)-光滑非凸函数类中匹配一阶方法信息论下界 \(\Omega(\epsilon^{-2})\)；随机 SF-SGD 在选取 \(\gamma \asymp 1/\sqrt{T}\) 时取得 \(\min_{k<T} \mathbb{E}[\|\nabla f(\bm{y}_k)\|^2] \leq \mathcal{O}(1/\sqrt{T})\)，严格匹配随机一阶最优界 \(\Omega(\epsilon^{-4})\)。

3. 非自治动力系统表述与单次微小扰动规避严格鞍点 确定性一阶优化算法能否摆脱局部极恶鞍点、收敛到局部极小点是非凸理论的核心指标。由于 SF-GD 初始状态满足 \(c_1=1\) 导致 \(\bm{y}_1 = \bm{x}_1\)，状态轨迹分布塌缩在对角流形 \(\Delta = \{(\bm{x}, \bm{x})\}\) 上，其在相空间 \(\mathbb{R}^d \times \mathbb{R}^d\) 内测度为零，使得经典的稳定流形定理无法直接套用。本文将 SF-GD 等价重构为二维块坐标状态转移映射 \((\bm{y}_{k+1}, \bm{x}_{k+1}) = h_k(\bm{y}_k, \bm{x}_k)\)，并在第 1 步更新后对 \(\bm{z}_1\) 施加单次零均值且具有勒贝格绝对连续分布的任意微小扰动 \(\bm{\xi}\)。该设计打破了初始流形退化性，结合非自自治伪双曲动力系统的局部微分同胚性质，严格证明了轨迹落入严格鞍点稳定流形的初值测度为零，即算法以概率 1 几乎必然规避所有严格鞍点。

4. 评估序列与梯度序列的性能解耦与 PEP 刻画 在实际使用中，社区通常将平均序列 \(\bm{x}_k\) 作为模型输出权重，而理论收敛保证针对的是梯度查询序列 \(\bm{y}_k\)。本文借助性能估计问题（PEP）框架建立半定规划数值上界求解器，系统评估了 \(\min_{k<T} \|\nabla f(\bm{x}_k)\|^2\) 的最坏情况行为。分析表明，在纯非凸最坏情况下，平均序列 \(\bm{x}_k\) 确实可能退化（在 \(\beta=0\) 的 Polyak-Ruppert 平均下甚至不收敛）。然而，当动量参数取在接近 1 的实用区间（如 \(\beta \in [0.75, 0.95]\)）时，PEP 证明界显著优于两端极端值（\(\beta=0\) 与 \(\beta=1\)），完美印证了实践中 Schedule-Free 选取 \(\beta \ge 0.9\) 的抗噪与平滑机制。

损失函数 / 训练策略

论文研究的一般性光滑非凸优化目标满足： 1. \(L\)-光滑性：\(\|\nabla f(\bm{x}) - \nabla f(\bm{y})\| \leq L \|\bm{x} - \bm{y}\|\)； 2. 下有界性：\(f(\bm{x}) \geq f^* > -\infty\)； 3. 随机梯度无偏与方差有界：\(\mathbb{E}[\nabla f(\bm{x}, \zeta)] = \nabla f(\bm{x})\)，\(\mathbb{E}[\|\nabla f(\bm{x}, \zeta) - \nabla f(\bm{x})\|^2] \leq \sigma^2\)。

在离散参数配置中，学习率序列允许包含预热阶段 \(\gamma_k = \gamma \min\{1, \frac{k+1}{T_{\mathsf{w}}}\}\)，滑动平均系数满足 \(c_{k+1} = \min\left\{\frac{\gamma_k^2}{\sum_{i=0}^k \gamma_i^2}(1-\beta)C, 1\right\}\)，其中解耦参数 \(C>0\) 使得基础参数与平均参数在前 \(k_0\) 步保持同步探索，随后逐渐平滑分离。

实验关键数据

主实验

论文通过理论收敛率推导与 PEP（Performance Estimation Problem）严格数值极值求解，对各优化算法在 \(L\)-光滑非凸目标下的最坏情况复杂度与梯度范数衰减率进行了系统评测对比。

方法 目标序列 确定性梯度下界复杂度 随机预言机查询复杂度 严格鞍点逃逸保障
标准 GD [5] \(\bm{x}_k\) \(\mathcal{O}(1/T) \quad [\Omega(\epsilon^{-2})]\) - 几乎必然逃逸 [18]
标准 SGD [3] \(\bm{x}_k\) - \(\mathcal{O}(1/\sqrt{T}) \quad [\Omega(\epsilon^{-4})]\) 需额外噪声/扰动
Primal Averaging (\(\beta=1\)) [8] \((\bm{x}_k, \bm{z}_k)\) 联合 \(\mathcal{O}(1/T)\) \(\mathcal{O}(1/\sqrt{T})\) 未证明
早期 SF-SGD 分析 [4] \(\bm{x}_k\) \(\mathcal{O}(1/\log T)\) (次优) \(\mathcal{O}(1/\log T)\) (次优) 无
SF-GD (本文) \(\bm{y}_k\) \(\mathcal{O}(1/T)\) (达下界最优) - 几乎必然逃逸 (单次扰动)
SF-SGD (本文) \(\bm{y}_k\) - \(\mathcal{O}(1/\sqrt{T})\) (达下界最优) 继承随机平滑性质

消融实验

基于 PEPit 工具包在 \(L=1\)、步长 \(\gamma = 1/L\)、\(T=100\) 的非凸平滑目标类上，针对不同动量超参数 \(\beta\) 下评估序列 \(\bm{x}_k\) 与梯度序列 \(\bm{y}_k\) 的最坏情况平方梯度范数上界进行了数值验证：

评估对象 / 超参数配置 \(\beta = 0.0\) (Polyak-Ruppert) \(\beta = 0.50\) \(\beta = 0.75\) \(\beta = 0.90\) (实用推荐) \(\beta = 0.95\) \(\beta = 1.0\) (Primal Averaging)
PEP 梯度序列 \(\min_{k<T} \|\nabla f(\bm{y}_k)\|^2\) \(0.0200\) (匹配 \(\frac{2}{T}\)) \(0.0400\) \(0.0800\) \(0.2000\) \(0.4000\) -
理论上界界值 \(\frac{2(f(\bm{x}_0)-f^*)}{(1-\beta)T}\) \(0.0200\) \(0.0400\) \(0.0800\) \(0.2000\) \(0.4000\) 退化
PEP 评估序列 \(\min_{k<T} \|\nabla f(\bm{x}_k)\|^2\) 震荡不收敛 (\(>1.0\)) \(0.3421\) \(0.1854\) \(0.1245\) \(0.1512\) \(0.2180\)

关键发现

  • 梯度位置序列 \(\bm{y}_k\) 的 PEP 严格数值最坏情况曲线与本文推导的解析理论上界 \(\frac{2}{(1-\beta)T}\) 高度重合，证明了构造的离散李雅普诺夫势函数系数估计极其紧凑。
  • 对于实际部署采用的模型参数 \(\bm{x}_k\)，最坏情况下的表现随 \(\beta\) 呈现明显的“U 型”凹曲线：在 \(\beta \to 0\) 端点处完全失去非凸收敛性，但在 \(\beta \in [0.75, 0.95]\) 区间内，其最坏表现显著优于两端经典方案（Polyak-Ruppert 与 Primal Averaging），从数值几何层面首次阐释了 Schedule-Free 超参数插值的核心机理。

亮点与洞察

  • 将常微分方程作为李雅普诺夫函数设计的原型透镜：传统非凸优化分析常陷入离散项展开的复杂代数泥潭，本文先推导连续时间 SF-ODE 并发现对消内积项的能量守恒形式，反向指导离散系数 \(\alpha_k\) 的精确配凑，极具方法论启发性。
  • 解耦奇异性与退化性证明鞍点逃逸：洞察到 Schedule-Free 在初值处由滑动平均权重强制导致的流形测度退化现象，创新性地引入单次微小随机扰动，在不破坏收敛速率的前提下成功复用了非自治双曲动力系统的稳定流形排除定理。

局限与展望

  • 理论最坏情况最优性仅在梯度查询序列 \(\bm{y}_k\) 上给出了闭式解析界，对实践中真正作为模型权重产出的评估序列 \(\bm{x}_k\)，非凸理论界仍依赖 PEP 数值计算，尚缺乏解析闭式的速率证明。
  • 收敛速率常数因子中包含 \(\frac{1}{1-\beta}\) 膨胀项，随着 \(\beta \to 1\) 理论界上浮，与实际深度学习训练中大 \(\beta\)（如 0.98）表现稳健的实证现象仍存在常数项维度的未闭合间隙。

相关工作与启发

  • vs. Ahn et al. (ICML 2025)：后者基于在线到非凸转换框架，必须将 \(\beta\) 在每次迭代设为随机变量采样且固定均匀权重，研究的是算法变体；本文不作任何算法修改，直接在标准固定 \(\beta\) 与动态加权权重下给出完整证明。
  • vs. Brown et al. (OPT 2025)：后者尝试直接分析离散序列但依赖前提不等式，本文在附录中严格证明该关键假设在 \(\beta < 1\) 时不成立，指出了先前工作在非凸情形下的数学漏洞，给出了真正成立的收敛证明。

评分

  • 新颖性: ⭐⭐⭐⭐⭐ 首次建立非凸无调度优化器的严格连续动力学与鞍点逃逸理论。
  • 理论充分度: ⭐⭐⭐⭐⭐ 兼具完备的连续/离散李雅普诺夫收敛证明与 PEP 紧凑半定规划数值验证。
  • 写作质量: ⭐⭐⭐⭐⭐ 逻辑链路极其缜密，连续到离散的映射动机叙述行云流水。
  • 价值: ⭐⭐⭐⭐⭐ 为无调度学习率算法在现代非凸深度学习领域的广泛采纳奠定了坚实理论基石。

相关论文