随机梯度下降的收敛率可以“搬运”:先在扩散方程上做一次Lyapunov计算,再逐窗传回离散迭代
核心概要
随机梯度算法的有限时间收敛界可以从关联随机微分方程的Lyapunov估计直接搬运过来,强凸SGD与随机Heavy Ball都由此复现已知速率。
深度剖析
随机梯度算法的收敛率分析可以改写成对一条连续扩散方程的Lyapunov计算,再把结果搬回离散迭代。 此前这类速率要么靠针对每个算法的离散时间证明,要么依赖只在有限时间窗内准确的扩散近似。 强凸随机梯度下降由这一搬运复现了Moulines与Bach(2011)直接离散分析给出的经典速率,随机Heavy Ball则复现了几何暂态加一个邻域。
做法是把连续比较器在每个固定扩散时间窗的边界重新启动,只比较Lyapunov观测量的弱误差。 强过程级扩散近似要求整条轨迹在越来越长的时间上保持接近,误差会随时间累积。 每个窗口的局部弱误差以阶进入估计,并被后续窗口的收缩因子衰减,因此不需要单一扩散近似在增长的时间尺度上保持准确。
启示与展望
这套搬运方法面向随机逼近与随机梯度类算法的收敛率分析,读者是熟悉随机逼近或连续时间分析的研究者。它给出的是有限时间界:SDE提供收缩与强迫项,离散算法额外贡献一个由固定窗弱比较产生的强迫项。作者指出同一证明模板在验证矩与正则条件后可套用到单调Robbins–Monro、收缩不动点递归、稳定线性随机逼近等递归,并明确把更一般的Lyapunov耗散不等式、高阶随机修正方程、路径空间与命中时间量、Markov噪声、自适应时钟和双时间尺度递归列为需要扩展定理而非仅新增应用的方向。
作者说明全局Lipschitz条件是方便而非最小的充分条件,多项式增长的系数在非爆炸与足够强的固定窗多项式矩界下也可处理。定理的全迭代结论还需要全局矩稳定性条件,作者用关联SDE的Foster–Lyapunov不等式给出充分条件,并在需要更高阶矩时使用幂提升技巧。常数步长只给出到邻域的收敛,而非收敛到零;作者也说明该常数步结论仅限一阶设定,不对带持续乘性缺陷的比较作断言。
