Aug, 2023

随机近端点算法的方差降低技术

HTML
PDF
TL;DR在有限和求和最小化的背景下，方差缩减技术被广泛应用于改进现有随机梯度方法的性能，本研究首次提出了针对随机近端点算法的方差缩减技术研究，介绍了针对平滑凸函数的SVRG、SAGA和其变种的随机近端版本，并且提供了迭代和目标函数值的多个收敛结果，特别对于满足Polyak-Lojasiewicz条件的情况下，我们获得了迭代和函数值的线性收敛速度，数值实验结果表明相对于梯度方法来说，近端方差缩减方法在选择步长方面具有更好的稳定性。
发现论文，激发创造
  • 加速随机梯度下降求解有限和最小化

    本论文提出了一种优化方法，该方法融合了加速梯度下降、随机方差减少梯度的优点，适用于非强凸和强凸问题，并在效率和收敛速率上都有优异表现。

    Jun, 2015

  • 非凸优化的随机方差缩减

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

    Mar, 2016

  • 基于方差减少的随机优化算法在具有有限和结构的无限数据集上的应用

    本文提出了针对复合目标强凸的情况下，带有方差约束的随机梯度下降法，其收敛速度优于传统的随机梯度下降法，同时常数因子也更小，只与输入数据的方差有关。

    Oct, 2016

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

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

    Feb, 2018

  • 使用半定规划加速随机方差减少的耗散理论：SVRG和Katyusha的统一分析

    运用耗散理论对两种方差降低算法(SVRG和Katyusha)进行新的解释，从能量守恒的角度提供物理图像化的直观理解，将这种新视角的工具用于捕捉SVRG等方法的特性，以进行收敛性分析。

    Jun, 2018

  • 一个简单的随机方差减少算法，具有快速收敛速率

    本篇论文介绍了一种简单的随机方差减小(MiG)算法及其在强凸和非强凸问题中最佳的收敛速率，并在稀疏和异步情况下介绍了其有效的变体并在这些情况下理论化分析其收敛速率。最后，我们进行了大量的实验，如逻辑回归等，以证明在串行和异步设置中的实际改进。

    Jun, 2018

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

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

    Jun, 2020

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

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

    Feb, 2024

  • 具有强收敛保证的确定性约束随机非凸优化的方差减少的一阶方法

    本文解决了确定性约束随机优化问题中如何确保约束几乎被确定性满足的核心问题。我们提出了一种单循环方差减少的随机一阶方法，通过计算确定性部分的确切梯度，确保在复杂度保证下能找到近似的随机静态点。研究表明，该方法在样本复杂度和一阶操作复杂度上达到了显著提升，具有重要的实际应用潜力。

    Sep, 2024

  • 具有强收敛保证的确定性约束随机非凸优化的一阶方差减少方法

    本研究解决了确定性约束的随机优化问题，现有方法往往只寻求满足一定准确度的随机平衡点，但在实际应用中，确保约束的确定性满足更为重要。我们提出了一种单循环方差减少的随机一阶方法，实验证明，该方法在满足约束的可能性上具有显著改进，且实现了样本复杂度和操作复杂度的优化。

    Sep, 2024