Apr, 2015

近端设置下的小批量半随机梯度下降

PDF
TL;DR提出了一种利用小批量方案改进半随机梯度下降（S2GD）方法的 mS2GD，该方法主要用于最小化一个由很多光滑凸函数的平均值和一个简单的非光滑凸正则化器组成的强凸函数，分析表明，该方法在具有小批量效应和简单并行实现方案的情况下，可以加速算法的收敛过程。
semi-stochastic gradient descentmini-batchingstrongly convex functionsmooth convex functionsnonsmooth convex regularizer
发现论文，激发创造
  • 半随机梯度下降方法

    本文提出了一种名为 S2GD 的新方法，为解决优化大量平滑凸损失函数的平均最小化问题，文章指出其期望工作量可以通过几个步骤推导得出。

    Dec, 2013

  • 半随机坐标下降

    提出了一种基于半随机坐标下降（S2CD）的新型随机梯度方法，用于最小化表示为大量平滑凸函数平均值的强凸函数，我们所提出的方法具有非常好的稳定性和计算复杂度。

    Dec, 2014

  • 加速随机梯度下降求解有限和最小化

    本论文提出了一种优化方法，该方法融合了加速梯度下降、随机方差减少梯度的优点，适用于非强凸和强凸问题，并在效率和收敛速率上都有优异表现。

    Jun, 2015

  • 最小二乘回归的随机梯度下降并行化：小批量、平均和模型错误

    该研究探讨了在随机梯度下降中广泛使用的平均方案的好处。特别是，通过对最小二乘回归的随机逼近问题进行非渐进超额风险分析，提供了这些方案的性能保证，并提出了高度可并行化的随机梯度下降方法。同时，该研究认为，为了保证最小极大风险，针对混浊噪声的步长必须是噪声属性的一个函数。

    Oct, 2016

  • 稳定随机梯度下降：一种流形传播方法用于大规模优化

    提出一种名为分层半随机梯度下降（S3GD）的算法，此算法通过有效的流形传播计算半随机梯度，实现了对大量复合凸函数的优化，能够很好地平衡了几何算法收敛速度和时间空间复杂度。

    Jun, 2015

  • 带逐步方差缩减的近端随机梯度下降法

    提出了一种多级方案来逐渐减少随机梯度方差的新的近端随机梯度方法，用于解决平滑组件函数的平均和简单近端映射的一般凸函数总和的极小化问题。

    Mar, 2014

  • 通过加速梯度方法实现更好的小批量算法

    通过加速梯度方法，改进小批量算法加速随机凸优化问题，提供新颖分析证明标准梯度法有时不足以获取大幅加速，提出一种新的加速梯度算法，解决了这个缺点，并在实践中表现良好。

    Jun, 2011

  • 拜占庭随机梯度下降

    本文研究了在对抗性环境下分布式随机优化问题，其中包括部分机器为拜占庭故障，提出了解决方案并证明了算法的采样和时间复杂度均达到信息上界。

    Mar, 2018

  • 随机凸优化中梯度下降的样本复杂度

    我们分析了非光滑随机凸优化中全批量梯度下降（GD）的样本复杂性，表明 GD 的泛化误差与最优超参数选择的样本复杂性匹配，可以表示为 Θ(d/m + 1/√m)，其中 d 为维度，m 为样本大小，这与最坏情况下的经验风险最小化器相符，这意味着与其他算法相比，GD 没有优势。我们的界限来自一个新的泛化界限，它取决于维度、学习速率和迭代次数。对于一般的超参数，当维度严格大于样本数量时，需要 Ω(1/ε^4) 次迭代才能避免过拟合，这解决了 schliserman2024dimension 和 amir2021sgd 提出的一个开放问题，并改进了先前的下界，前者证明了样本大小至少必须为维度的平方根。

    Apr, 2024

  • 使用随机梯度下降平滑非凸函数：隐式逐渐优化与最优噪声调度的分析

    本文定义了用于 graduated optimization 的一类新的非凸函数，讨论了其充分条件，并对 graduated optimization 算法的收敛性进行了分析。研究发现，带有 mini-batch 随机梯度的随机梯度下降 (SGD) 方法可以使函数平滑的程度由学习率和 batch size 决定。此发现从 graduated optimization 的角度提供了理论洞察，解释了为何大批量大小会陷入尖锐的局部最小值，以及为何逐渐减小的学习率和逐渐增大的批量大小优于固定的学习率和批量大小，并给出了最佳的学习率调度方法。此外，分析了一种新的 graduated optimization 框架，该框架使用逐渐减小的学习率和逐渐增大的批量大小，并报告了支持我们理论发现的图像分类的实验结果。

    Nov, 2023