近端和联邦随机重洗
该研究探讨了利用随机重排来压缩有限和函数的算法 ——Random Reshuffling。该算法在凸优化和非凸优化中很有实用性,并且通常比随机梯度下降更快。研究者通过理论和实验表明,新的方差类型为 RR 的卓越性能提供了额外的理论依据。此外,他们还展示了 Shuffle-Once 算法的快速收敛性,并进一步提出了多种适用于非强凸和非凸目标的算法。他们的理论优于现有文献,同时也揭示了在某些情况下,随机变量的不同类型可能产生更大的影响。
Jun, 2020
本文研究了随机重洗方法的收敛速率,表明在特定条件下随机重洗方法通过迭代平均和逐渐缩小的步长可以以概率一的方式在优化目标值的次优性上以 $\Theta (1/k^{2s})$ 的速率收敛,从而改善了 SGD 的 $\Omega (1/k)$ 收敛速率。
Oct, 2015
本文提出了两种分布式随机重排方法,分别是随机重排梯度追踪 (GT-RR) 和带随机重排的精确扩散 (ED-RR),用于解决连接网络上的分布式优化问题,并在理论上和实践中都优化了以前的分布式随机重排算法的性能。
Jun, 2023
本文提出并研究了一种新颖的随机优化算法,称为基于正态映射的近端随机重排(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) 和步长动态。最后,我们还提供了关于机器学习问题的初步数值结果,证明了该方法的效率。
Dec, 2023
我们考虑了应对平滑非凸优化问题的具有随机重排特性的随机梯度方法,通过研究其样本复杂度和下降特性,我们提出了一个简单可行的停止准则,并设计了一个扰动随机重排方法,可以有效地避开严格的鞍点并返回一个具有二阶停滞点的迭代解。
Nov, 2023
研究了过度参数化的机器学习模型,提出了抽样无替换的 SGD 变体 - random reshuffling-,并证明了在一些假设条件下,它可以比 SGD 更快地收敛。此外,对于 Polyak-L ojasiewicz (PL) 函数类问题,当样本数小于条件数与参数之积或小于参数的强增长条件时,证明了 random reshuffling 优于 SGD。
Apr, 2023
研究分布式学习中的本地 SGD 和基于随机梯度的优化方法,通过随机梯度下降的方案,降低了随机抽样带来的估计偏差和方差,提高了模型的训练效率,实验表明,该方案的效果比替代方案更好。
Oct, 2021
本文围绕随机梯度下降 (SGD) 优化方法,在经验风险最小化的线性预测器上,利用原始 - 对偶视角对 SGD 进行了分析,并证明了一种细粒度复杂度界的方法,以数据矩阵为基础,证明了它比现有的复杂度界更加紧密地预测了 SGD 的性能。
Jun, 2023
本文研究了无替换 SGD 算法在有限和优化问题上的应用及其两种不同的指标洗牌方式(RandomShuffle 和 SingleShuffle)。作者们建立了这些算法的最小二次理论下的优化收敛率。此外,作者们进一步应用了各自分量的凸性来缩小 RandomShuffle 的宽松收敛结果,并减少了所有先前艺术品中共有的缺点。
Jun, 2020