Oct, 2023

非凸优化的基于符号随机重排算法的收敛性

PDF
TL;DRsignSGD 与随机重排（SignRR）在非凸优化中具有相同的收敛速率，我们还提出了利用减小方差的梯度和动量更新的 SignRVR 和 SignRVM 算法，且将这些算法扩展到数据在不同机器上分布的情况。
signsgdnonconvex optimizationrandom reshufflingvariance-reduced gradientsmomentum updates
发现论文，激发创造
  • 随机重排：简单分析，显著提高

    该研究探讨了利用随机重排来压缩有限和函数的算法 ——Random Reshuffling。该算法在凸优化和非凸优化中很有实用性，并且通常比随机梯度下降更快。研究者通过理论和实验表明，新的方差类型为 RR 的卓越性能提供了额外的理论依据。此外，他们还展示了 Shuffle-Once 算法的快速收敛性，并进一步提出了多种适用于非强凸和非凸目标的算法。他们的理论优于现有文献，同时也揭示了在某些情况下，随机变量的不同类型可能产生更大的影响。

    Jun, 2020

  • 高效的基于符号的优化：通过方差减少加速收敛

    本文介绍了 signSGD 方法及其收敛速率的改进，并引入了基于符号的随机方差缩减（SSVR）方法，通过引入方差缩减估计器来跟踪梯度并利用其符号进行更新；此外，还研究了分布式环境中的异构多数投票，引入了两种新算法以获得更好的收敛速率，通过数值实验验证了所提方法的有效性。

    Jun, 2024

  • Shuffle SGD 总是比 SGD 更好：对任意数据顺序的 SGD 的改进分析

    该论文研究了随机梯度下降算法在非凸优化问题中的迭代次数，发现采用随机 / 单扰动的随机梯度下降算法的收敛速度要快于经典的随机梯度下降算法，实验证明其具有更好的性能。

    May, 2023

  • 有限轮数后，随机重洗优于随机梯度下降

    本论文首次提出了证明随机梯度下降算法的 RandomShuffle 版本在 “合理” 迭代次数后，比常规的有替换版本更快收敛的非相态解决方法。同时，论文还探讨了该问题在强凸性、稀疏数据和非强凸梯度主导函数等方面的推广。

    Jun, 2018

  • 超参数化情况下随机重排的快速收敛及 Polyak-Łojasiewicz 条件

    研究了过度参数化的机器学习模型，提出了抽样无替换的 SGD 变体 - random reshuffling-，并证明了在一些假设条件下，它可以比 SGD 更快地收敛。此外，对于 Polyak-L ojasiewicz (PL) 函数类问题，当样本数小于条件数与参数之积或小于参数的强增长条件时，证明了 random reshuffling 优于 SGD。

    Apr, 2023

  • 随机重排的高概率保证

    我们考虑了应对平滑非凸优化问题的具有随机重排特性的随机梯度方法，通过研究其样本复杂度和下降特性，我们提出了一个简单可行的停止准则，并设计了一个扰动随机重排方法，可以有效地避开严格的鞍点并返回一个具有二阶停滞点的迭代解。

    Nov, 2023

  • 基于随机洗牌的方差缩减随机学习

    本文研究基于方差减小的随机梯度算法，探究了随机数据抽样和随机重排的条件下的线性收敛性和新的 AVRG 算法，并给出了理论保证。

    Aug, 2017

  • signSGD：非凸问题的压缩优化

    signSGD 可通过传输最小批次随机梯度符号来缓解学习分布在多个 worker 上时的通信效率问题，在实际应用中，其动量对应项能够匹配 Adam 算法在深层 Imagenet 模型上的精度和收敛速度。高斯定理证明 sign-based 优化方法对于通信效率和收敛速度的提高具有巨大潜力。

    Feb, 2018

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

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

    Mar, 2024

  • 为什么随机重洗超越随机梯度下降

    本文研究了随机重洗方法的收敛速率，表明在特定条件下随机重洗方法通过迭代平均和逐渐缩小的步长可以以概率一的方式在优化目标值的次优性上以 $\Theta (1/k^{2s})$ 的速率收敛，从而改善了 SGD 的 $\Omega (1/k)$ 收敛速率。

    Oct, 2015