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

Dec, 2018

Tight Analyses for Non-Smooth Stochastic Gradient Descent

Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, Sikander Randhawa

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

Abstract

Consider the problem of minimizing functions that are Lipschitz and strongly convex, but not necessarily differentiable. We prove that after $T$ steps of stochastic gradient descent, the error of the final iterate is $O(\log(T)/T)$ with high probability. We also construct a function fr

stochastic gradient descent lipschitz functions strongly convex functions suffix averaging method optimization

发现论文，激发创造

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

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

Sep, 2011

随机梯度方法的最后迭代收敛性再探讨

研究证明了随机梯度下降法的最终迭代在各种条件下都能以最优的收敛速度收敛，包括期望和高概率收敛，在紧致域、非平滑问题和组合优化中都能适用。

Dec, 2023

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

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

Dec, 2012

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

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

Jul, 2019

非强凸平稳随机逼近，收敛速率 O (1/n)

本篇论文研究了关于随机逼近问题的现有算法，提出了两种新型随机梯度算法，并在回归和逻辑分类两种经典的监督学习问题上进行了测试，得到了较好的优化效果。

Jun, 2013

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

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

Apr, 2019

强生长条件下随机梯度下降的快速收敛

本文考虑优化一个平滑凸函数，该函数是一组可微函数的平均数，在每个梯度的范数受到平均梯度范数的线性约束的假设下，证明了基本的随机梯度方法具有 O (1/k) 的收敛速度，并且在强凸条件下具有线性收敛速度。

Aug, 2013

凸 SGD: 泛化无需提前停止

我们研究了在紧致集合上的光滑凸函数中使用随机梯度下降的泛化误差，并展示了当迭代次数 T 和数据集大小 n 以任意速率趋近于零时，我们第一次得到了一个消失的泛化误差界，该界与步长 αt=1/√t 成比例，泛化能力不需要强凸性。

Jan, 2024

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

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

Jul, 2016

随机凸优化中梯度下降的样本复杂度

我们分析了非光滑随机凸优化中全批量梯度下降（GD）的样本复杂性，表明 GD 的泛化误差与最优超参数选择的样本复杂性匹配，可以表示为 Θ(d/m + 1/√m)，其中 d 为维度，m 为样本大小，这与最坏情况下的经验风险最小化器相符，这意味着与其他算法相比，GD 没有优势。我们的界限来自一个新的泛化界限，它取决于维度、学习速率和迭代次数。对于一般的超参数，当维度严格大于样本数量时，需要 Ω(1/ε^4) 次迭代才能避免过拟合，这解决了 schliserman2024dimension 和 amir2021sgd 提出的一个开放问题，并改进了先前的下界，前者证明了样本大小至少必须为维度的平方根。

Apr, 2024