自适应随机梯度下降的线性收敛

Aug, 2019

Linear Convergence of Adaptive Stochastic Gradient Descent

Yuege Xie, Xiaoxia Wu, Rachel Ward

TL;DR本文证明了自适应随机梯度方法的规范版本（AdaGrad-Norm）在强凸函数或满足 Polyak Lojasiewicz 不等式的非凸函数的子集中，达到的收敛速度是线性的。文中引入了梯度的限制均衡不等式（RUIG）的概念，用来描述函数的景观，并且 RUIG 在证明 AdaGrad-Norm 对超参数调整的鲁棒性中发挥着关键作用。我们开发了一个两阶段的框架来证明 AdaGrad-Norm 的线性收敛，而不知道目标函数的参数。数值实验验证了理论，并提出了未来的改进方向。

Abstract

We prove that the norm version of the adaptive stochastic gradient method (adagrad-norm) achieves a linear convergence rate for a subset of either strongly convex functions or non-convex functions that satisfy th

adagrad-norm linear convergence rate polyak lojasiewicz inequality restricted uniform inequality of gradients stochastic gradient norms

发现论文，激发创造

AdaGrad 步长：在非凸景观上的尖锐收敛

本文提出了一种更新梯度下降步长的方法：AdaGrad-Norm，不需要微调步长计划，对于光滑的非凸函数具有收敛性，并具备健壮性

Jun, 2018

关于 AdaGrad (Norm) 在 $R^{d}$ 上的收敛：超越凸性、非渐近速率和加速

本文针对平滑凸函数的标准和更一般的 quasar 凸函数提出了 AdaGrad 及其变体的深入理解，并提出了新的技术来明确界定未约束问题的纯净 AdaGrad 收敛速度，给出了一个新的 AdaGrad 变体，可以展示最终收敛而不是平均迭代，并在确定的情况下给出了新的加速自适应算法及其收敛保证。

Sep, 2022

自适应梯度方法在细化平滑度和噪声假设下的收敛分析

分析了 AdaGrad 在随机非凸优化中收敛速率，证明了存在优于 SGD 的收敛速度，并给出了收敛速率的上界和下界。

Jun, 2024

SGD 中的自适应能力：无界梯度和仿射方差下的自调步长

本研究旨在研究基于观察的随机梯度的步长的变化，以最小化非凸光滑目标函数的 AdaGrad-Norm 的收敛速度，并表明 AdaGrad-Norm 在假设与最佳调优的非自适应 SGD 相同的情况下展现出与之相同的收敛速度，同时不需要任何调整参数。

Feb, 2022

非凸学习和优化的梯度均匀收敛性

研究非凸性学习任务中经验风险的精细属性（梯度）和群体对应属性的收敛速度以及收敛对优化的影响；提出矢量值 Rademacher 复杂性作为导出非凸问题梯度无维度一致收敛界的工具；给出了应用这些技术进行非凸广义线性模型和非凸健壮回归的批梯度下降方法的新分析，显示了使用任何找到近似稳定点的算法可以获得最优样本复杂度。

Oct, 2018

非凸目标函数的 AdaGrad 收敛性：简单证明和宽松假设

本文提供了一种简单的收敛证明方法，证明了当仅有仿射噪声方差和有界光滑性假设时，AdaGrad 优化非凸目标，本文基于一个新的辅助函数 ξ 来消除处理 AdaGrad 更新的分子和分母之间的相关性的复杂性，与现有结果相比得到了更紧的结果，并将分析扩展到了若干个新的重要情况。

May, 2023

梯度和近端梯度法在 Polyak-Łojasiewicz 条件下的线性收敛

介绍了一种不需要强凸性条件的梯度下降算法，并针对机器学习中的各种问题提供了新的分析方法和收敛证明。

Aug, 2016

方向平滑性和梯度方法：收敛性和适应性

我们开发了一种梯度下降法的新次优性边界，该边界依赖于优化路径中的目标条件，而不是全局最坏情况下的常数。我们的证明关键在于方向平滑性，这是一种梯度变化的度量，我们用它来开发上界约束。通过求解隐式方程来最小化这些上界约束，我们展示了这些方程对于凸二次函数是容易解决的，并为两种传统步长提供了新的保证。对于一般函数，我们证明了 Polyak 步长和归一化梯度下降法尽管不使用方向平滑性的任何知识，但能够获得快速的路径相关性。逻辑回归上的实验证明，我们的收敛保证比基于 L 平滑性的传统理论更紧致。

Mar, 2024

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

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

Nov, 2018

重新审视在放宽假设下的 AdaGrad 收敛性

重新审视 AdaGrad 与动量的收敛性，研究非凸光滑优化问题中的噪声模型，分析概率收敛速度及广义平滑性

Feb, 2024