May, 2017

用于非凸优化的随机递归梯度算法

PDF
TL;DR本文研究分析了随机递归梯度算法 (StochAstic Recursive grAdient algoritHm, SARAH) 的 mini-batch 版本，用于解决非凸损失函数的经验损失最小化问题。我们提出了一种子线性收敛率 (对于一般非凸函数) 和一种线性收敛率 (对于梯度主导函数)，这两种方法相比其他现代非凸损失随机梯度算法具有一些优势。
发现论文，激发创造
  • SARAH：一种使用随机递归梯度的机器学习问题新方法

    本文提出了一种名为 SARAH 的随机递归梯度算法及其改进版 SARAH +，以优化有限累加和问题，并证明了该算法在强凸情况下具有线性收敛速率。

    Mar, 2017

  • 非凸有限和问题中随机递归梯度的概率性保证

    本研究开发了一种基于 Azuma-Hoeffding 类型边界的新的无维度维数的 martingale 差异序列的累加范数，利用这一结果，我们为所提出的 Prob-SARAH 算法中的梯度范数估计器提供了高概率边界，该算法是 StochAstic Recursive grAdient algoritHm（SARAH）的改进版本，它是一种具有最优计算复杂性的方差减小算法，用于有限和问题的期望。Prob-SARAH 的概率复杂性与最佳期望结果相匹配，并且经验实验表明 Prob-SARAH 在真实数据集上相对于其他流行算法具有更优异的概率性能。

    Jan, 2024

  • ProxSARAH：随机复合非凸优化的高效算法框架

    提出了一种新的随机一阶算法框架来解决随机复合非凸优化问题，该算法覆盖了有限和期望设置，其中算法仅需要非凸目标项的平均光滑性假设和附加的有界方差假设，并证明了算法可以实现最佳复杂度界限。

    Feb, 2019

  • 随机非凸优化的混合随机梯度下降算法

    本文提出了使用混合随机估算器设计的混合随机梯度算法来解决非凸期望问题，该算法可以获得更好的复杂度，同时考虑不同的扩展，如使用自适应步长和不同的迭代方式。在使用两个非凸模型进行了多个数据集上的比较。

    May, 2019

  • ZeroSARAH: 高效的非凸有限和优化算法，使用零全梯度计算

    ZeroSARAH 是一种新的方差减少方法，用于分布式学习中处理大量非凸函数的平均值，可以在不需要计算全梯度的情况下实现，并在标准和分布式设置下取得新的最优结果。

    Mar, 2021

  • 使用 SARAH 算法进行有限和平滑优化

    该论文提出了改进的 SARAH 算法并证明其最劣情况复杂性与通常常数因子内与阈值相关，用于求解随机一阶优化算法的无限和光滑非凸目标函数，同时提出 SARAH++ 算法，并在各种数据集上进行数值实验以验证其实用性。

    Jan, 2019

  • 一种最优混合方差减小算法用于随机复合非凸优化

    提出了一种新的混合方差缩减近端梯度法，它使用随机梯度评估来代替早期方法中的 $SARAH$，从而实现每次迭代少使用一个随机梯度，在达到了随机梯度评估的最优随机预测复杂度界限的同时很简单。

    Aug, 2020

  • 非光滑非凸正则化优化的简单随机梯度方法

    本研究旨在探讨优化非光滑非凸正则化器下的平滑非凸损失函数的随机梯度方法。我们提出了两种简单的随机梯度算法，对于有限总和和一般随机优化问题，相较于现有技术水平，其具有更优的收敛复杂度。同时，我们在经验风险最小化中比较了两种算法的实际表现。

    Jan, 2019

  • 任意抽样的非凸方差减少优化

    调查了非凸损失函数下的经验风险最小化的方差缩减算法，尤其是 SVRG、SAGA 和 SARAH 的非凸版本，提出了基于重要性采样的小批量分析，并成功提高了训练速度。

    Sep, 2018

  • 随机递归动量策略梯度方法

    本文提出一种名为 STORM-PG 的新算法，它采用 SARAH 类型的随机递归方差降低的策略梯度，具有对于 STORM-PG 具有严格的 O（1/ε^3）样本复杂度界限，并避免了其他方差减小的策略梯度方法中存在的大批处理和小批处理之间的交替，从而允许较简单的参数调整，并在数值实验中表现出了与其他策略梯度算法相比的优越性。

    Mar, 2020