Dec, 2018

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

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

    通过对Shor子梯度分析的推广，我们将子梯度方法的经典收敛速度理论扩展到可适用于非Lipschitz函数。我们证明了在任何具有局部Lipschitz性的凸函数中，确定性投影子梯度算法的全局O（1/√T）收敛速度。我们还表明，对于具有最多二次增长的凸函数，随机投影子梯度方法的收敛速度为O（1/√T），在强凸性或较弱的二次下限条件下，该速度可进一步提高至O(1/T)。

    Dec, 2017

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

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

    Oct, 2018

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

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

    Jul, 2019

  • 使用随机梯度下降法找到稳定点的复杂度

    研究了随机梯度下降（SGD）算法在最小化光滑、可能非凸函数梯度范数方面的迭代复杂度，结果表明，Ghadimi和Lan的上限不能得到改进，除非做出额外的假设，即使对于凸二次函数，也是如此；此外还表明，对于非凸函数，SGD最小化梯度的可行性需要根据所选择的最优性标准而定。

    Oct, 2019

  • 非凸随机优化下的下限界

    采用随机一阶方法找到梯度范数不超过ε的ε-稳定点的复杂度下界，使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型，证明任何算法在最坏情况下需要至少ε^-4个查询才能找到ε-稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型，我们证明了ε^ -3个查询的下界，建立了最近提出的方差缩减技术的最优性。

    Dec, 2019

  • 高概率收敛界限在重尾噪声下的非线性随机梯度下降

    通过研究一类广泛的非线性随机梯度下降方法在高概率下的收敛界限，我们证明了对于具有Lipschitz连续梯度的强凸损失函数，即使在噪声具有重尾分布的情况下，也能实现失败概率的对数依赖性，这对于任何具有有界（逐分量或联合）输出的非线性性质（如剪切、归一化和量化）都是成立的，与以往对于具有重尾噪声的研究相比，我们的研究结果在噪声的矩阶限制上得以松弛。

    Oct, 2023

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

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

    Dec, 2023

  • 凸SGD: 泛化无需提前停止

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

    Jan, 2024

  • 关于随机梯度方法的最终迭代收敛性

    用“随机梯度下降”（SGD）而无需替换的“洗牌梯度方法”，基于曲率刻画关于目标值的收敛速度，证明其对于目标值的最优性。

    Mar, 2024

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

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

    Jun, 2024