随机梯度下降法在递减步长下期望收敛速率的紧凑维度无关下限

Oct, 2018

随机梯度下降法在递减步长下期望收敛速率的紧凑维度无关下限

Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD

Phuong Ha Nguyen, Lam M. Nguyen, Marten van Dijk

TL;DR研究随机梯度下降法（SGD）在强凸目标函数上的收敛性，证明了 ICML 2018 和 2019 提出的降低步长的速率序列在每次迭代后的收敛速度与我们的下限相差不到 32 倍，为最优状态；该下限相较于现有工作大约高出了因子 775×d，其中 d 是维度。

Abstract

We study the convergence of stochastic gradient descent (SGD) for strongly convex objective functions. We prove for all $t$ a lower bound

stochastic gradient descent convergence strongly convex objective functions sequences of step sizes lower bound

发现论文，激发创造

随机梯度算法的新收敛性特点

本文对随机梯度下降法（SGD）的收敛性进行了分析，提出了一种新的假设随机梯度较真实梯度的范数更小的分析方法，并在多个情境下证明了 SGD 的收敛性，拓展了当前一类可达到收敛性的学习率。

Nov, 2018

通过马尔可夫链实现常数步长 SGD 的收敛和集中特性

本文研究在强凸光滑目标下使用常数步长随机梯度下降的优化问题，通过马洛夫链的视角对其性质进行研究，证明了当梯度噪音分布满足一定条件时，该迭代过程以总变差距离或 Wasserstein-2 距离收敛于一个不变分布，同时证明了该极限分布具有次高斯或次指数分布的浓度性质；最后针对一些具体应用，推导出了高可信度界限。

Jun, 2023

增强型随机梯度下降算法的改进步长：收敛性和实验

该论文提出了一种新颖的方法，通过引入基于 1/√t 的修改衰减步长来提高随机梯度下降 (SGD) 算法的性能。所提出的步长整合了对数项，在最后的迭代中选择较小的值。通过分析，我们在非凸光滑函数无 Polyak-Lojasiewicz 条件的情况下，建立了收敛速度为 O (ln T/√T)。为了评估我们的方法的有效性，我们在 FashionMNIST 和 CIFAR10 数据集上进行了图像分类任务的数值实验，结果显示与传统的 1/√t 步长相比，准确率明显提高，分别观察到 0.5% 和 1.4% 的增益。源代码可以在 https://github.com/Shamaeem/LNSQRTStepSize 找到。

Sep, 2023

SGD: 一般分析和改进速率

提出 SGD 收敛的通用简单定理，该定理可描述与特定概率法相关的各种 SGD 变体的收敛性。该定理是第一次执行这种分析，大多数 SGD 的变体以前从未明确考虑过。论文依赖于最近引入的期望平滑性的概念，并不依赖于随机梯度方差的统一界限。

Jan, 2019

随机梯度下降在非凸问题中的几乎必然收敛

本文针对随机梯度下降算法在非凸问题中的收敛性进行轨迹分析，首先证明了在广泛的步长策略范围内，SGD 生成的迭代序列保持有界并以概率 1 收敛，随后证明了 SGD 避开了严格的鞍点 / 流形的概率是 1，最后证明了算法在采用 Theta (1/n^p) 步长时收敛速度为 O (1/n^p)，这为调整算法步长提供了重要的指导建议，并且在 CIFAR 的 ResNet 架构中，展示了此启发式方法加速收敛的效果。

Jun, 2020

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

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

Jul, 2019

解密 SGD 非凸收敛的神话与传说

通过分析，本文展示了当总迭代次数足够大时，随机梯度下降法（SGD）的最终迭代中存在一个 ε- 稳定点，这是一个比现有结果更强的结论，并且可以在 SGD 的最终迭代中度量 ε- 稳定点的密度，同时对于目标函数和随机梯度的边界条件，我们恢复了经典的 O (1/√T) 渐进速率，此分析结果解决了与 SGD 的非凸收敛性相关的某些迷思和传说，并提出了一些有启发性的研究方向。

Oct, 2023

使 SGD 的最后迭代在信息理论上达到最优

本文旨在设计新的步长序列，以获得对最后一点的 SGD 和 GD 的理论最佳子优越性保证，并通过模拟验证了新的步长序列相对于标准步长序列的改进，主要涉及随机梯度下降、优化、步长序列、子优越性和收敛率。

Apr, 2019

基于收敛诊断的随机梯度下降的步长

本论文提出一种简单的统计程序，可以有效地检测恒定步长随机梯度下降法的转换和稳定阶段，从而快速获得收敛结果。这种统计程序在人工数据集和实际数据集上表现出最先进的性能，即便目标函数为二次时，传统的 Pflug 检验方法也不能提供足够的诊断。

Jul, 2020

非凸区域中恒定步长随机梯度下降的分析：渐近正态性和偏差

本研究探讨了非凸非光滑目标函数中常数步长随机梯度下降算法的渐近正态结果，结果表明只要非凸和非光滑目标函数满足耗散性特性，SGD 算法的迭代平均值就会渐近正态分布，该结果可用于构建对于使用 SGD 算法的非凸问题的置信区间。同时，本文通过对其与马尔可夫链的关系进行了详细地分析，还对目标函数的临界点与其期望值之间的偏差进行了表征。

Jun, 2020