Dec, 2023

一种新的非平滑非凸有限和优化问题随机重排方法

HTML
PDF
TL;DR本文提出并研究了一种新颖的随机优化算法，称为基于正态映射的近端随机重排（norm-PRR）方法，用于非光滑非凸有限和问题。我们建立了norm-PRR的迭代复杂度O(n^{-1/3}T^{-2/3})，其中n是组成函数的数量，T表示迭代总数。此外，在Kurdyka-Łojasiewicz不等式下，我们建立了norm-PRR的强极限点收敛性，并得到了迭代的最终收敛速度为O(k^{-p})的形式；其中，p∈[0, 1]取决于KL指数θ∈[0,1)和步长动态。最后，我们还提供了关于机器学习问题的初步数值结果，证明了该方法的效率。
发现论文，激发创造
  • 非光滑非凸优化的快速随机方法

    本文研究随机算法优化非凸、非光滑的有限和问题。针对此问题，本文提出快速的随机算法，可获得常数迷你批量的收敛性。本文还使用这些算法的变种，证明了比批量近端梯度下降更快的收敛性，并在非凸、非光滑函数的一个子类中证明全局线性收敛率。

    May, 2016

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

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

    Feb, 2018

  • 随机重排的恒定步长随机学习

    本文研究了常数步长情况下强凸损失函数的随机梯度算法，在收敛时随机重排比均匀抽样性能更优，通过分析表明了迭代值到达最小值的邻域范围更小，证明了随机重排算法的性能更好，同时解释了随机重排算法实现中观察到的周期性行为。

    Mar, 2018

  • 一种随机复合非凸优化的混合随机优化框架

    提出一种新方法解决一类复合随机非凸优化问题，通过组合两种随机估计量形成混合估计量，将之应用于多种变体的随机梯度法中以达到最优的复杂度界限。

    Jul, 2019

  • 随机重排：简单分析，显著提高

    该研究探讨了利用随机重排来压缩有限和函数的算法——Random Reshuffling。该算法在凸优化和非凸优化中很有实用性，并且通常比随机梯度下降更快。研究者通过理论和实验表明，新的方差类型为RR的卓越性能提供了额外的理论依据。此外，他们还展示了Shuffle-Once算法的快速收敛性，并进一步提出了多种适用于非强凸和非凸目标的算法。他们的理论优于现有文献，同时也揭示了在某些情况下，随机变量的不同类型可能产生更大的影响。

    Jun, 2020

  • 近端和联邦随机重洗

    本篇论文提出两种新的优化算法：ProxRR 和 FedRR，应用于分布式问题的改进。这些算法在收敛性和计算复杂度方面具有明显优势，并在重要的最优化任务中发挥出色。

    Feb, 2021

  • 超参数化情况下随机重排的快速收敛及Polyak-Łojasiewicz条件

    研究了过度参数化的机器学习模型，提出了抽样无替换的 SGD 变体-random reshuffling-，并证明了在一些假设条件下，它可以比 SGD 更快地收敛。此外，对于 Polyak-L ojasiewicz (PL) 函数类问题，当样本数小于条件数与参数之积或小于参数的强增长条件时，证明了 random reshuffling 优于 SGD。

    Apr, 2023

  • 非凸优化的基于符号随机重排算法的收敛性

    signSGD与随机重排（SignRR）在非凸优化中具有相同的收敛速率，我们还提出了利用减小方差的梯度和动量更新的SignRVR和SignRVM算法，且将这些算法扩展到数据在不同机器上分布的情况。

    Oct, 2023

  • 随机重排的高概率保证

    我们考虑了应对平滑非凸优化问题的具有随机重排特性的随机梯度方法，通过研究其样本复杂度和下降特性，我们提出了一个简单可行的停止准则，并设计了一个扰动随机重排方法，可以有效地避开严格的鞍点并返回一个具有二阶停滞点的迭代解。

    Nov, 2023

  • 具有随机重排的随机外推算法：对变分不等式的改进收敛性

    Stochastic Extragradient的随机重排列变体SEG-RR收敛分析：证明SEG-RR对于VIPs的三类问题具有更快的收敛速度，并在单调情况下无需大批次样本即可保证任意精度的收敛。

    Mar, 2024