非光滑优化的随机梯度下降：收敛结果与最优平均方案

ICMLDec, 2012

非光滑优化的随机梯度下降：收敛结果与最优平均方案

Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes

Ohad Shamir, Tong Zhang

TL;DR本文探讨了在没有光滑假设的情况下，以及通过运行平均方案将 SGD 迭代转换为具有最佳优化精度的解决方案的性能，并证明了对于凸非光滑目标函数，最后一个 SGD 迭代的次优性的程度随 T 的轮次按 O（log（T）/sqrt（T））缩放，对于非光滑强凸情况，次优性的程度随 T 按 O（log（T）/ T）缩放。此外，本文提出了一种新的简单平均方案，并提供了一些实验说明。

Abstract

stochastic gradient descent (SGD) is one of the simplest and most popular stochastic optimization methods. While it has already been theoretically studied for decades, the classical analysis usually required non-trivial smoothness assumptions, which do not apply to many modern applicat

stochastic gradient descent non-smooth objective functions running average scheme suboptimality bounds averaging scheme

发现论文，激发创造

强凸随机优化的最优梯度下降算法

本文研究了随机梯度下降在随机情形下的最优性。结果表明，对于光滑问题，算法可以达到最优的 O (1/T) 收敛速率，但对于非光滑问题，平均收敛速率可能真的是 Ω(log (T)/T)，而这不仅仅是分析的产物。反过来，我们展示了一种简单的平均步骤修改方法，足以恢复到 O (1/T) 收敛速率，而无需对算法做出任何其他改变。此外，我们还给出了支持我们发现的实验结果，并指出了开放性问题。

Sep, 2011

加权平均随机梯度下降：渐近正态性与最优性

本文探讨了随机梯度下降算法的加速收敛方法，提出了一种自适应加权平均方案，并提供了非渐近收敛的统计保证和在线推断方法。最终的结论表明，该自适应加权平均方案不仅在统计率上是最优的，而且在非渐近收敛方面也具有有利的效果。

Jul, 2023

非凸世界中 SGD 的更好理论

本篇论文使用类似于期望光滑性假设的新方法来研究随机梯度下降法在非凸优化中的收敛率，并在考虑多种采样策略和小批量大小的情况下，探讨有限和优化问题的影响。

Feb, 2020

随机非光滑优化的交错时间平均算法及 O (1/T) 收敛性

本文研究了基于随机子梯度优化的非光滑函数的优化问题，提出一种具有 O（1/T）收敛率的算法，并且证明在去除局部 polyhedral 假设时具有一般的收敛性，最后，在确定性问题的特殊情况下，在局部 polyhedral 假设上的收敛性得到了改善。

Jul, 2016

非凸学习的随机梯度下降算法 (无需假设梯度有上限)

本文研究证明了随机梯度下降在非凸学习中，无需统一梯度有界性假设也能达到最优收敛率的情况，并在一定程度上对于一般非凸目标函数和梯度主导的目标函数实现了几乎必然收敛。特别地，在方差为零的情况下可以得到线性收敛。

Feb, 2019

非光滑随机梯度下降的严格分析

使用随机梯度下降来最小化 Lipschitz 函数和强凸函数但不一定可微的问题，证明了在 T 步随机梯度下降后，最终迭代的误差高概率为 O (log (T)/T)；同时构造了一个函数，证明了在确定性梯度下降中，最终迭代的误差为 Ω(log (T)/T)；然后证明了在采用后缀平均法的情形下，它的高概率误差界是优化函数相关类别中的最优界（O (1/T)）；最后证明了对于 Lipschitz 和凸函数 class，使用随机梯度下降解决此问题后，最终迭代的误差高概率为 O (log (T)/sqrt (T))

Dec, 2018

（随机）梯度方法的统一最优分析

证明在 L - 平滑度条件下，随机梯度下降的迭代收敛速度的数量级为 O (LR2exp [-(mu/4L) T]+sigma2/muT), 其中 sigma2 是随机噪声方差，且收敛速度与最佳已知的 GD 和 SGD 迭代复杂度匹配.

Jul, 2019

ROOT-SGD：单算法的尖锐非渐近性和渐近效率

本论文从统计的角度考虑了一阶随机优化问题，提出了一种基于过去随机梯度的递归平均方法 - 递归 One-Over-T SGD (ROOT-SGD)，在在线方差约减随机逼近方法中达到了最先进的收敛速率，并且在稍强的分布式假设下，归一化最后的迭代会收敛于一个接近最优协方差的零均值高斯分布。

Aug, 2020

一种用于非光滑非凸约束优化的随机次梯度平均法收敛性分析

本文证明了具有广义可微性质、约束非光滑非凸目标函数的单时标随机次梯度法和子梯度平均方法的收敛性，同时，我们也证明了这类函数路径上的链式规则。

Dec, 2019

非凸问题通用逐步学习方法，收敛于平均解

本文提出了一个通用的分级优化框架，用于求解一类广泛的非平滑非凸问题，采用随机凸优化算法，如准随机梯度下降和 AdaGrad 以及分级降低步长方式，并返回平均解决方案。作者的理论结果表明分级 AdaGrad 的自适应性，从而揭示其对于稀疏随机梯度问题比分级 SGD 更快收敛的见解，并在经验研究中提高了现有 SGD 和 AdaGrad 实现的泛化性能。

Aug, 2018