Oct, 2023

高概率收敛界限在重尾噪声下的非线性随机梯度下降

PDF
TL;DR通过研究一类广泛的非线性随机梯度下降方法在高概率下的收敛界限，我们证明了对于具有 Lipschitz 连续梯度的强凸损失函数，即使在噪声具有重尾分布的情况下，也能实现失败概率的对数依赖性，这对于任何具有有界（逐分量或联合）输出的非线性性质（如剪切、归一化和量化）都是成立的，与以往对于具有重尾噪声的研究相比，我们的研究结果在噪声的矩阶限制上得以松弛。
stochastic gradient descentclipped sgdnonlinear sgd methodsconvergence boundslipschitz continuous gradients
发现论文，激发创造
  • 非凸随机优化中重尾的高概率界限

    本研究讨论了使用第一阶梯度算法进行的非凸随机优化问题，其中梯度估计可能具有重尾特征，结果表明梯度剪裁，动量和归一化梯度下降的组合可以在高概率下收敛于关键点，特别适用于光滑损失的已知最佳速率，适用于任意光滑度规范，并针对克服该领域二阶光滑损失引发的问题进行讨论。

    Jun, 2021

  • 具有重尾噪声的复合和分布式随机最小化和变分不等式的高概率收敛

    基于梯度剪裁的随机一阶优化方法在噪声假设温和的情况下引起了很大关注。我们提出了新的用于复合和分布式优化的随机方法，并证明了这些方法的紧密高概率收敛结果（包括几乎最优的结果）。同时，我们还针对复合和分布式变分不等式开发了新的方法，并分析了这些方法的高概率收敛性。

    Oct, 2023

  • 通过加速梯度削减实现重尾噪声的随机优化

    本文提出了一种新的加速随机一阶方法 clipped-SSTM，该方法通过剪辑随机梯度结合特殊变体的随机梯度下降法，用于解决具有重尾分布噪声的光滑凸随机优化问题，并推导出了该方法的第一个高概率复杂度界限，证明了其优于同类方法。

    May, 2020

  • 基于梯度分位数截断的鲁棒随机优化

    引入了一种剪裁策略，使用梯度范数的分位数作为剪裁阈值，为平滑目标（凸或非凸）提供鲁棒且高效的优化算法，容忍重尾样本和数据中的异常值，数学分析说明了其收敛性质以及对初始估计误差的高概率界限，并通过实验证实了其高效性和鲁棒性。

    Sep, 2023

  • 带剪辑的非凸随机优化的高概率分析

    使用梯度裁剪技术在随机优化算法中研究梯度的截尾行为和其理论保证。

    Jul, 2023

  • 随机梯度剪裁的稳定性和收敛性：超越 Lipschitz 连续性和平滑性

    本文提出了一种修剪随机梯度（子）梯度法（SGD）的收敛性研究，特别是对于具有快速增长次梯度的非光滑凸函数。研究表明，修剪对 SGD 的稳定性有益，并且修剪 SGD 算法在许多情况下具有有限的收敛速率。同时，我们还研究了带有动量的修剪方法的收敛性，并展示了新的 Lyapunov 分析证明了该方法在这类问题中具有最佳的收敛速率。数值结果验证了理论结果。

    Feb, 2021

  • 突破随机优化问题中的重尾噪声障碍

    我们针对具有结构密度的重尾噪声的随机优化问题展开研究，证明在随机梯度具有有限阶矩（α ∈ (1, 2]）时，可以获得比 Ο(K^(-2 (α - 1)/α)) 更快的收敛速率，而且噪声范数可以有无界期望。为实现这些结果，我们使用平滑的中值均值稳定随机梯度，并证明了所得估计具有可忽略的偏差和可控的方差，从而可以将其谨慎地纳入剪辑随机梯度下降（clipped-SGD）和剪辑随机次梯度均值（clipped-SSTM），并推导出所考虑情况下的新的高概率复杂度界限。

    Nov, 2023

  • 重温梯度剪裁：随机偏差和紧密收敛保证

    本文研究了梯度裁剪在随机梯度下降中的应用，给出了裁剪阈值对收敛结果的影响和其上下界，进一步阐述了裁剪机制的缺陷及解决方案。

    May, 2023

  • 随机梯度下降噪声的隐私泄露可能会收敛，即使对于非凸损失函数

    本文研究了 DP-SGD 算法在限制梯度影响的条件下，对于具有省略凸性和平滑性假设的损失函数，随着迭代次数的增加，其隐私泄露的收敛速度是指数级的。同时，文章还分析了非正则 DP-SGD 的隐私损失。

    May, 2023

  • 非光滑非凸优化中随机次梯度方法的收敛性保证

    本研究论文探讨了随机梯度下降（SGD）方法及其变种在训练非光滑激活函数构建的神经网络中的收敛性质，提出了一种新的框架，分别为更新动量项和变量分配不同的时间尺度。在一些温和条件下，我们证明了我们提出的框架在单一时间尺度和双时间尺度情况下的全局收敛性。我们展示了我们提出的框架包含了许多著名的 SGD 类型方法，包括 heavy-ball SGD、SignSGD、Lion、normalized SGD 和 clipped SGD。此外，当目标函数采用有限和形式时，我们证明了基于我们提出的框架的这些 SGD 类型方法的收敛性质。特别地，在温和的假设条件下，我们证明了这些 SGD 类型方法以随机选择的步长和初始点找到了目标函数的 Clarke 稳定点。初步的数值实验表明了我们分析的 SGD 类型方法的高效性。

    Jul, 2023