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

Jun, 2023

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

Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds

Xufeng Cai, Cheuk Yin Lin, Jelena Diakonikolas

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

Abstract

stochastic gradient descent (SGD) is perhaps the most prevalent optimization method in modern machine learning. Contrary to the empirical practice of sampling from the datasets without replacement and with (possible) reshuffling at each epoch, the theoretical counterpart of SGD usually

stochastic gradient descent empirical risk minimization linear predictors primal-dual perspective cyclic coordinate updates

发现论文，激发创造

随机原始 - 对偶法用于经验风险最小化，每次迭代复杂度为 O（1）

本文提出了新的随机原始对偶算法，用于解决具有线性预测器的正则化经验风险最小化问题。通过泰勒展开、凸组合和割平技巧得到具有较优复杂度和收敛性质的算法，进一步提出了方差减少版算法和数值实验表明该算法在高维问题上优于现有算法，收敛速度更快。

Nov, 2018

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

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

Jul, 2019

有序 SGD: 一种新的经验风险最小化随机优化框架

论文提出了一种新的随机优化方法，它有针对性地偏向于高损失值的观测结果，并证明该算法对于凸损失具有亚线性收敛率，对于弱凸损失（非凸）具有关键点，同时在 SVM、逻辑回归和深度学习等模型中获得了更好的测试误差。

Jul, 2019

解密双倍随机梯度下降法

对于以不可解期望的求和形式作为优化目标的问题，除了有界方差等强假设条件外，很少了解双重随机梯度下降（doubly SGD）的收敛性质。本研究在一般条件下，建立了具有独立小批量和随机重排的双重随机梯度下降的收敛性，并允许对依赖的分量梯度估计进行详细分析，推荐在每次迭代的计算预算中如何进行合理分配，同时证明随机重排（RR）可以改善子采样噪声的复杂度依赖关系。

Jun, 2024

带洗牌的 SGD: 无需分量凸性和大的 epoch 要求的最优速率

本文研究了无替换 SGD 算法在有限和优化问题上的应用及其两种不同的指标洗牌方式（RandomShuffle 和 SingleShuffle）。作者们建立了这些算法的最小二次理论下的优化收敛率。此外，作者们进一步应用了各自分量的凸性来缩小 RandomShuffle 的宽松收敛结果，并减少了所有先前艺术品中共有的缺点。

Jun, 2020

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

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

Mar, 2018

小批量 SGD 与局部 SGD 洗牌：紧密收敛界与进一步研究

研究分布式学习中的本地 SGD 和基于随机梯度的优化方法，通过随机梯度下降的方案，降低了随机抽样带来的估计偏差和方差，提高了模型的训练效率，实验表明，该方案的效果比替代方案更好。

Oct, 2021

非替换式 SGD 的排序

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

Jun, 2023

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

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

Jun, 2018

轻触重约束的 SGD

本研究提出了 Projected Stochastic Gradient Descent（SGD）算法的一种有效扩展，可应用于许多受限函数的学习中，同时较少地应用每个迭代的约束，从而在适应区域内保持良好的优化。我们的理论分析显示，针对拥有大量约束的问题，其在单次迭代工作时间与所需迭代次数之间取得了很好的平衡。

Dec, 2015