随机重排的恒定步长随机学习

Mar, 2018

Stochastic Learning under Random Reshuffling with Constant Step-sizes

Bicheng Ying, Kun Yuan, Stefan Vlaski, Ali H. Sayed

TL;DR本文研究了常数步长情况下强凸损失函数的随机梯度算法，在收敛时随机重排比均匀抽样性能更优，通过分析表明了迭代值到达最小值的邻域范围更小，证明了随机重排算法的性能更好，同时解释了随机重排算法实现中观察到的周期性行为。

Abstract

In empirical risk optimization, it has been observed that stochastic gradient implementations that rely on random reshuffling of the data

empirical risk optimization stochastic gradient random reshuffling uniform sampling convergence

发现论文，激发创造

随机梯度下降法的效果如何？

本研究探讨了随机梯度下降在平滑和强凸有限和优化问题上的性能，重点研究了包含在个体函数的随机排列中的启发式方法，给出了这些启发式方法的期望优化误差的下界，说明了它们的优势和劣势。

Jul, 2019

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

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

Oct, 2015

随机重排：简单分析，显著提高

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

Jun, 2020

Primal-Dual 视角下的洗牌 SGD 经验风险最小化及改进界限

本文围绕随机梯度下降 (SGD) 优化方法，在经验风险最小化的线性预测器上，利用原始 - 对偶视角对 SGD 进行了分析，并证明了一种细粒度复杂度界的方法，以数据矩阵为基础，证明了它比现有的复杂度界更加紧密地预测了 SGD 的性能。

Jun, 2023

随机重排的高概率保证

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

Nov, 2023

非替换式 SGD 的排序

本文探讨了基于随机排序和增量梯度下降算法收敛率的不同速度，找到一种可以提高算法非替代形式的收敛率的排序方式，通过实验数据验证了基于这种排序方式的一些优化想法在多个数据集上的效果以及在更复杂的神经网络上的应用前景。

Jun, 2023

常值步长最小均方：偏差 - 方差权衡与最优抽样分布

本文考虑了最小二乘回归问题，提出了平均恒定步长随机梯度下降（也称最小均方误差）的性能的详细渐近分析。在强凸情况下，我们提供了一个高度渐近展开式。我们的分析提供了对随机逼近算法的新见解。

Nov, 2014

SGD: 一般分析和改进速率

提出 SGD 收敛的通用简单定理，该定理可描述与特定概率法相关的各种 SGD 变体的收敛性。该定理是第一次执行这种分析，大多数 SGD 的变体以前从未明确考虑过。论文依赖于最近引入的期望平滑性的概念，并不依赖于随机梯度方差的统一界限。

Jan, 2019

常步长随机梯度下降与马尔可夫链的桥梁

本文应用马尔科夫链理论，通过随机梯度下降（SGD）算法来计算目标函数，并提供了一种新的 Richardson-Romberg 外推方法来优化 SGD 算法，通过渐进展开分析，总结出其与初始条件、噪声和步长的相关性。

Jul, 2017

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

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

Jun, 2018