Sep, 2011

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

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

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

    Dec, 2012

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

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

    Jun, 2013

  • 随机梯度下降的稳定性和最优性

    提出一种基于平均隐式（averaged implicit）随机梯度下降的迭代过程，旨在解决参数估计过程中的数值不稳定性和统计效率问题。实践证明这种方法比其他现有方法表现更为出色。

    May, 2015

  • SGD和Hogwild!：在无需有界梯度假设的情况下收敛

    该研究论文讨论了随机梯度下降算法的收敛性分析，提出了一种在异步并行环境下使用降低学习率机制的算法，并证明了其收敛性。

    Feb, 2018

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

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

    Nov, 2018

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

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

    Jul, 2019

  • 非凸世界中SGD的更好理论

    本篇论文使用类似于期望光滑性假设的新方法来研究随机梯度下降法在非凸优化中的收敛率，并在考虑多种采样策略和小批量大小的情况下，探讨有限和优化问题的影响。

    Feb, 2020

  • 平均加速随机梯度下降算法：有限样本速率和渐近正态性

    本研究分析了随机梯度下降与动量法在强凸设置下的有限样本收敛速度，并证明了 Polyak-averaging 版本的 SGDM 估算器的渐近正态性以及其与平均 SGD 的渐近等价性。

    May, 2023

  • 状态依赖噪声的加速随机逼近

    本文讨论了一类随机光滑凸优化问题，其噪声的方差与算法产生的近似解的次优性有关，提出了两个非欧几里德加速随机逼近算法，即随机加速梯度下降（SAGD）和随机梯度外推（SGE），并证明了在适当的条件下，这两个算法可以同时达到最优的迭代和样本复杂度。同时本文还提出了应用SGE进行恢复稀疏解的方法。

    Jul, 2023

  • 加权平均随机梯度下降：渐近正态性与最优性

    本文探讨了随机梯度下降算法的加速收敛方法，提出了一种自适应加权平均方案，并提供了非渐近收敛的统计保证和在线推断方法。最终的结论表明，该自适应加权平均方案不仅在统计率上是最优的，而且在非渐近收敛方面也具有有利的效果。

    Jul, 2023