Mar, 2024

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

PDF
TL;DRStochastic Extragradient 的随机重排列变体 SEG-RR 收敛分析：证明 SEG-RR 对于 VIPs 的三类问题具有更快的收敛速度，并在单调情况下无需大批次样本即可保证任意精度的收敛。
stochastic extragradientseg-rrconvergence analysisvipswith-replacement variants
发现论文，激发创造
  • 变分不等式中的随机方法：遍历性，偏差和改进

    本研究旨在通过将常数步长随机外推算法（SEG）和随机梯度升降（SGDA）重新组合为时齐马尔科夫链来澄清并量化这些算法内在的概率结构，并证明了对于广泛的单调和非单调 VIP 而言，平均迭代数渐近地趋向于具有唯一不变分布的正态分布，从而带来了对 VIPs 的改进和理论发现验证的实验

    Jun, 2023

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

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

    Jun, 2020

  • 基于随机洗牌的方差缩减随机学习

    本文研究基于方差减小的随机梯度算法，探究了随机数据抽样和随机重排的条件下的线性收敛性和新的 AVRG 算法，并给出了理论保证。

    Aug, 2017

  • 关于随机梯度方法的最终迭代收敛性

    用 “随机梯度下降”（SGD）而无需替换的 “洗牌梯度方法”，基于曲率刻画关于目标值的收敛速度，证明其对于目标值的最优性。

    Mar, 2024

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

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

    Oct, 2023

  • 随机重排的高概率保证

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

    Nov, 2023

  • 为什么随机重洗超越随机梯度下降

    本文研究了随机重洗方法的收敛速率，表明在特定条件下随机重洗方法通过迭代平均和逐渐缩小的步长可以以概率一的方式在优化目标值的次优性上以 $\Theta (1/k^{2s})$ 的速率收敛，从而改善了 SGD 的 $\Omega (1/k)$ 收敛速率。

    Oct, 2015

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

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

    Apr, 2023

  • 改进的分布式随机重排方法

    本文提出了两种分布式随机重排方法，分别是随机重排梯度追踪 (GT-RR) 和带随机重排的精确扩散 (ED-RR)，用于解决连接网络上的分布式优化问题，并在理论上和实践中都优化了以前的分布式随机重排算法的性能。

    Jun, 2023

  • 随机变分不等式问题的最优鲁棒平滑外推算法

    本文考虑了随机泛型不等式问题及其解决方案，利用局部随机平滑方案求解，并证明了该解决方案在平均意义下和几乎肯定意义下都能收敛到问题的解，同时也实现了 $1/k$ 的收敛速度。

    Mar, 2014