Jan, 2019

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

PDF
TL;DR该论文提出了改进的 SARAH 算法并证明其最劣情况复杂性与通常常数因子内与阈值相关，用于求解随机一阶优化算法的无限和光滑非凸目标函数，同时提出 SARAH++ 算法，并在各种数据集上进行数值实验以验证其实用性。
stochastic first-order optimization algorithmfinite-sum smooth nonconvex objective functionconvergence analysissarah algorithmconvex optimization
发现论文，激发创造
  • ProxSARAH：随机复合非凸优化的高效算法框架

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

    Feb, 2019

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

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

    Mar, 2021

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

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

    May, 2017

  • 关于 SARAH 及超出其的收敛性

    本文提出了一种称为 L2S 的算法，扩展了一种方差缩减方法 SARAH，并证明了在凸问题中 L2S 的复杂性为 O (n+sqrt (n)/epsilon)。我们的实验结果表明，L2S 可能比 SARAH 具有更好的泛化性能。

    Jun, 2019

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

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

    Jan, 2024

  • 关于平滑非凸有限和优化的下界

    本文研究了平滑的非凸有限和优化的下界，并证明了在不同设置下找到 ε- 次优点和 ε- 近似稳定点的复杂度的严格下界，以及一些现有算法的最佳增量一阶预测器（IFO）复杂度。

    Jan, 2019

  • SCSG 方法求解非凸有限和优化问题

    开发了基于 Stochastically Controlled Stochastic Gradient Method 的算法，可用于非凸的有限和优化问题，并取得了优于随机梯度下降的表现。在满足 Polyak-Lojasiewicz Condition 约束的函数中，同样实现了加速优化，实验表明在训练多层神经网络方面，该方法优于随机梯度下降。

    Jun, 2017

  • SARAH：一种使用随机递归梯度的机器学习问题新方法

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

    Mar, 2017

  • 随机平均梯度下降法最小化有限和

    本文提出了基于随机平均梯度方法的优化算法，它克服了黑匣子随机梯度方法的缺点，具有更快的收敛速度和更少的梯度评估数量。实验表明，该算法在许多情况下都优于现有的随机梯度方法和确定性梯度方法，并且可以通过非均匀采样策略进一步提高表现。

    Sep, 2013

  • 优化有限和的下界

    本文提出了优化 n 个 L-smooth、强凸函数总和的下界，并将其与先前的方法进行比较。在随机数据情况下，我们将这些复杂度结果与用于直接优化总和的最优一阶方法进行对比。研究发现需要谨慎进行准确比较，并确定新方法在机器学习场景中的帮助计算能力。

    Oct, 2014