Freya PAGE: 大规模非凸有限和优化中的首个最优时间复杂性与异步计算的异构

May, 2024

Freya PAGE: 大规模非凸有限和优化中的首个最优时间复杂性与异步计算的异构

Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations

PDF

Alexander Tyurin, Kaja Gruntkowska, Peter Richtárik

TL;DR该研究论文介绍了一种名为 Freya PAGE 的新的并行方法，用于处理异构和异步计算情况下的非凸有限和问题，该方法具有较强的鲁棒性，通过忽略慢速计算和对付异常值，相比之前的方法包括异步 SGD、Rennala SGD、SPIDER 和 PAGE，具有显著改善的时间复杂度保证。它还提供了一种新颖的随机梯度收集策略，并建立了异步设置下平滑非凸有限和问题的时间复杂性下界，证明了 Freya PAGE 在大规模情况下的最优性。

Abstract

In practical distributed systems, workers are typically not homogeneous, and due to differences in hardware configurations and network conditions, can have highly varying processing times. We consider smooth nonconvex finite-sum (empirical risk minimization) problems in this setup and

distributed systems heterogeneous computations asynchronous computations time complexity guarantees stochastic gradient collection strategies

发现论文，激发创造

PAGE: 简单且最优的概率梯度估计器用于非凸优化

通过引入新的 “概率梯度估计器”（PAGE），该研究证明了在非凸优化问题中，当函数满足 Polyak-Lòjasiewicz 条件时，PAGE 可以自动切换到更快的线性收敛速率，并且在深度学习实验中 PAGE 不仅训练速度更快，而且测试准确率也更高，从而证实了 PAGE 在理论和实践上的优势。

Aug, 2020

并行重启 SPIDER -- 与最优计算复杂度的通信高效分布式非凸优化

本文提出了一种基于 SPIDER 梯度估计器的分布式算法，可用于处理随机的平滑、非凸优化问题，该算法结合了最优化方差减少技术与并行 SGD 算法，优化了可以用于联邦学习的非相同分布的数据的模型，提出的算法具有最优迭代复杂度复杂度，并实现了与现有方法相同的线性加速。

Dec, 2019

FedPAGE：一种快速局部随机梯度法，用于通信效率高的联邦学习

本文提出了一种新的联邦学习算法 FedPAGE，通过利用最新的优化 PAGE 方法来代替 FedAvg 中的 SGD，从而进一步减少通信复杂度。在联邦凸优化和非凸优化两种情境下，FedPAGE 都比之前的本地方法使用更少的通信轮次，为联邦凸优化和非凸优化实现了通信复杂度方面的新的最优结果。

Aug, 2021

非凸优化的异步并行随机梯度

本研究探讨了两种异步并行随机梯度下降的实现方式，并证明了它们的收敛率均为 O (1 / 根号 K)，且在工作者数受到限制的情况下可实现线性加速。

Jun, 2015

突破不光滑障碍：复合优化可扩展并行方法

本研究提出了一种基于 ProxASAGA 算法的并行异步稀疏方法，用于解决多核架构下大规模优化问题中的非光滑目标，并在实验中取得了多项实际加速。

Jul, 2017

关于平滑非凸有限和优化的下界

本文研究了平滑的非凸有限和优化的下界，并证明了在不同设置下找到 ε- 次优点和 ε- 近似稳定点的复杂度的严格下界，以及一些现有算法的最佳增量一阶预测器（IFO）复杂度。

Jan, 2019

随机增量方法的改进异步并行优化分析

探究计算机体系结构和日益增长的数据集规模增大了异步并行优化算法在机器学习领域中的必要性，以及解决其理论分析的难题，提出一种新的 “扰动迭代” 框架，通过对三种不同的异步并行优化算法的实验分析，得出以往的假设存在问题，提高了算法的理论性能，以及研究了理论分析中的重要参数 “重叠常数” 与之前猜想不同，其复杂性更高。

Jan, 2018

异步联邦优化

提出了一种新的异步联邦优化算法，用于在海量边缘设备上进行培训，具有近线性收敛全局最优点的证明，可用于强凸和一类非凸问题，实验证明在各种应用中算法收敛快且容忍陈旧。

Mar, 2019

非凸优化的异步随机拟牛顿 MCMC 算法

本研究开发了一种适用于分布式和共享内存的异步并行随机 L-BFGS 算法，它利用了随机梯度马尔科夫链蒙特卡罗技术的优势，在非凸优化问题中提供了可行性和收敛性的证明，并在多个实验中验证了该算法的优越性能。

Jun, 2018

分散的非凸优化求和

本文研究分散设置中的非凸函数求和最小化优化问题，提出了 PMGT-SVRG 算法的新的理论分析，证明了其方法的线性收敛性。然而，PMGT-SVRG 算法的收敛速度与条件数呈线性依赖关系，这对于病态问题而言是不理想的。为了解决这个问题，我们提出了一种结合加速、梯度跟踪和多共识混合技术的加速随机分散一阶算法，该方法的收敛速度与条件数呈平方根依赖关系。数值实验验证了我们提出算法在合成和真实数据集上理论保证的有效性。

Feb, 2024