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

NIPSOct, 2018

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

Uniform Convergence of Gradients for Non-Convex Learning and Optimization

Dylan J. Foster, Ayush Sekhari, Karthik Sridharan

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

Abstract

We investigate 1) the rate at which refined properties of the empirical risk---in particular, gradients---converge to their population counterparts in standard non-convex learning tasks, and 2) the consequences of this convergence for optimization. Our analysis follows the tradition of

empirical risk rademacher complexities non-convex learning batch gradient descent relu

发现论文，激发创造

广义平滑下的凸优化和非凸优化

本文介绍了一种新的非均匀光滑条件下的优化方法，并开发出一种简单但有效的分析技术来限制沿轨迹的梯度，从而获得更强的凸优化和非凸优化问题的结果。我们通过这种新方法证明了（随机）梯度下降和 Nesterov 加速梯度法在这种一般的光滑条件下的收敛率，而不需要梯度剪裁，并允许在随机场景中的有界方差的重尾噪声。

Jun, 2023

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

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

Aug, 2019

非凸优化的自适应梯度方法收敛性研究

本文提供了关于一类自适应梯度方法（包括 AMSGrad，RMSProp 和 AdaGRad）在光滑非凸函数优化方面的收敛性分析，证明了期望下自适应梯度方法能够收敛到一阶稳定点，同时还证明了 AMSGrad，RMSProp 和 AdaGrad 的收敛速率，这些结论有助于更好地理解自适应梯度方法在优化非凸目标时的机制。

Aug, 2018

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

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

Sep, 2022

用梯度实现的维度冲击：随机凸优化中的梯度方法的泛化

研究了梯度方法在基础随机凸优化条件下的泛化性能，并关注其与维数的依赖关系。针对全批量梯度下降（GD），通过构建学习问题，在维数为 $ d = O（n^2）$ 的情况下，可以证明经过调整以达到经验风险最优表现的典型 GD（使用 n 个训练样本）在具有常数概率的情况下，收敛为近似经验风险最小化器，且其相对于总体风险具有 Ω（1）的过量风险。这个界限对于标准 GD 需要达到非平凡测试误差的训练样本数量有一个下界 Ω（√d），回答了 Feldman（2016）和 Amir，Koren 和 Livni（2021b）提出的一个开放问题，表明非平凡的维数依赖性是不可避免的。此外，针对标准的一次遍历随机梯度下降（SGD），我们证明了同样的构建技术在样本复杂度上提供了类似的 Ω（√d）下界，以达到非平凡的经验误差，尽管它可以实现最优的测试性能。与之前的工作（Koren，Livni，Mansour 和 Sherman，2022）相比，这提供了维数依赖性的指数级改进，解决了其中的一个开放问题。

Jan, 2024

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

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

Jun, 2018

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

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

Jun, 2024

非参数方法下随机梯度下降在无噪声线性模型中的紧致收敛速率

本文探究噪声线性模型下单次训练中的随机梯度下降算法，证明了其收敛性和泛化误差的多项式收敛率，解释了结果在再生核希尔伯特空间框架下的意义，同时将分析应用于超出监督学习的场景。

Jun, 2020

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

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

Feb, 2024

广义平滑非凸优化中的 RMSProp 和 Adam 的收敛保证与仿射噪声方差

该论文在最宽松的坐标普适光滑性和仿射噪声方差假设下，为 RMSProp 和 Adam 在非凸优化中提供了首个收敛性分析，首先分析了 RMSProp，然后将分析推广到 Adam，表明它们的迭代复杂度与复杂性下界一致。

Apr, 2024