Oct, 2023

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

PDF
TL;DR基于梯度剪裁的随机一阶优化方法在噪声假设温和的情况下引起了很大关注。我们提出了新的用于复合和分布式优化的随机方法，并证明了这些方法的紧密高概率收敛结果（包括几乎最优的结果）。同时，我们还针对复合和分布式变分不等式开发了新的方法，并分析了这些方法的高概率收敛性。
stochastic first-order optimization methodsgradient clippinghigh-probability guaranteescomposite and distributed optimizationstochastic gradient differences
发现论文，激发创造
  • 通过加速梯度削减实现重尾噪声的随机优化

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

    May, 2020

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

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

    Oct, 2023

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

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

    Jul, 2023

  • 非凸随机优化中重尾的高概率界限

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

    Jun, 2021

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

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

    Sep, 2023

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

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

    Nov, 2023

  • 通过近端点方法在随机优化中降低方差和样本复杂度

    该研究提出了一种随机近端点方法来解决随机凸复合优化问题，通过仅假设随机梯度的方差有界等较弱条件，建立了对于该方法收敛的高概率保证的低样本复杂度。此外，本研究的一个显著特点是开发了一个用于解决近端子问题的子程序，该子程序还作为一种新的方差减小技术。

    Feb, 2024

  • 在重尾噪声存在时，梯度剪裁改进了 AdaGrad

    本文通过证明，在处理偏重尾噪声时，AdaGrad 和 Adam 具有很差的高概率收敛性，提出了一种名为 Clip-RAdaGradD（Clipped Reweighted AdaGrad with Delay）的新版本 AdaGrad，并证明了它在处理偏重尾噪声时具有多对数相关性的高概率收敛边界。经验评估揭示出剪裁版本的 AdaGrad/Adam 在处理偏重尾噪声时具有卓越优势。

    Jun, 2024

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

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

    May, 2023

  • 针对复合凸光滑优化的随机梯度方法统一分析

    本文为最小化平滑和凸损失加上凸正则化的随机梯度算法提供了一致的收敛性分析定理，并探讨了特定算法的最优小批量大小。

    Jun, 2020