Mar, 2024

约束条件下的随机优化：非渐近函解析

PDF
TL;DR通过分析局部最小值下界与扰动问题解的关系，我们证明了方差减小的近端梯度算法在样本数量趋向无穷大时达到了局部最小值下界，除了普适常数和对数因子的样本大小外。
stochastic convex optimizationvariance reduced proximal gradient algorithmnon-asymptotic guaranteeinstance-dependentlocal minimax lower bound
发现论文，激发创造
  • 非凸优化的随机方差缩减

    本研究分析了随机变量缩减梯度（SVRG）方法在非凸有限和问题中的应用，证明了其比随机梯度下降（SGD）和梯度下降（GD）更快收敛于固定点，并分析了一类 SVRG 在解决非凸问题上的线性收敛，同时研究了 mini-batch 变体的 SVRG 在并行设置中加速的外延。

    Mar, 2016

  • 一种简单的近端随机梯度下降法用于非光滑非凸优化

    本文提出一种基于变量规约的 Proximal 随机梯度下降算法 (ProxSVRG+), 该算法在非凸性和非光滑性优化问题上具有更好的性能，并在收敛性分析方面比之前的算法更加全面和普适性更强。

    Feb, 2018

  • 无强凸性的方差缩减随机梯度线性收敛

    本研究介绍了 Prox-SVRG 及其投影变体 VRPSG 算法，用于解决一类在机器学习中广泛使用的非强凸优化问题。通过 SSC 不等式的使用，本文证明了两种算法可以在无强凸性的情况下实现线性收敛率。

    Jun, 2014

  • 非光滑非凸正则问题的随机方法的非渐进分析

    本文研究了非光滑非凸正则化问题的非渐近收敛性分析，并提出了基于随机近端梯度（SPG）的各种变体方法，以解决光滑非凸损失和非光滑非凸正则化器构成的非凸优化问题，其复杂度与解决凸规则化非凸问题的方法相同，并且在实践中比其他同类随机方法更有效。

    Feb, 2019

  • 非凸随机复合优化问题的小批量随机逼近方法

    该论文提出了一种随机梯度下降算法（RSPG）来解决一类包含非可微凸函数和非光滑性质的随机优化问题，并且证明了该算法的收敛速度。

    Aug, 2013

  • 随机近端梯度算法的收敛性

    本文基于凸优化中函数是光滑和非光滑组合的形式，证明了一种适用于大类凸优化问题的随机近端梯度算法收敛性质，其避免了平均化和理论研究中常见但实际中不一定满足的有界性假设，证明了一系列强、弱收敛性结果，并得到了期望意义下的 $O (1/n)$ 的有界性结果。

    Mar, 2014

  • 随机嵌套方差缩减非凸优化

    我们提出了一种基于嵌套方差降低的新随机梯度下降算法，可用于解决有限个数个、非凸函数的优化问题，并且在平滑非凸函数上具有比现有算法更好的梯度复杂度。

    Jun, 2018

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

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

    Feb, 2024

  • VR-SGD: 一种简单的随机方差缩减机器学习方法

    本文提出了一种名为 VR-SGD 的变体随机梯度下降法，其使用平均值和上一个时期的最后迭代作为两个向量，能够直接解决非光滑和 / 或非强凸问题，并能够使用更大的学习率。此方法在解决各种机器学习问题，如凸和非凸的经验风险最小化以及特征值计算等方面，具有更快的收敛速度。

    Feb, 2018

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

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

    Mar, 2014