Proximal Stochastic Recursive Momentum Methods for Nonconvex Composite Decentralized Optimization
Proximal Stochastic Recursive Momentum Methods for Nonconvex Composite Decentralized Optimization
复制标题
DOI：
10.1609/aaai.v37i7.26087
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Gabriel Mancino-Ball;Shengnan Miao;Yangyang Xu;Jiewei Chen
中科院分区：
文献类型：
--
作者：
Gabriel Mancino-Ball;Shengnan Miao;Yangyang Xu;Jiewei Chen
考虑N个分散计算代理的网络协作解决非凸随机组合问题。在这项工作中，我们提出了一个单循环算法，称为DEEPSTORM，实现了最佳的样本复杂度为这个设置。与需要大批量来偶尔计算（随机）梯度的双环算法不同，DEEPSTORM使用小批量，在流数据和在线学习等场合中具有优势。这是第一个实现分散非凸随机组合问题的最佳样本复杂度的方法，需要O（1）批量大小。我们进行收敛性分析的DEEPSTORM与常数和递减步长。此外，在适当的初始化和一个足够小的期望的解决方案的错误，我们表明，DEEPSTORM与一个恒定的步长实现了一个独立于网络的样本的复杂性，与一个额外的线性加速相对于N集中的方法。所有代码都可以在https://github.com/gmancino/DEEPSTORM上找到。
Consider a network of N decentralized computing agents collaboratively solving a nonconvex stochastic composite problem. In this work, we propose a single-loop algorithm, called DEEPSTORM, that achieves optimal sample complexity for this setting. Unlike double-loop algorithms that require a large batch size to compute the (stochastic) gradient once in a while, DEEPSTORM uses a small batch size, creating advantages in occasions such as streaming data and online learning. This is the first method achieving optimal sample complexity for decentralized nonconvex stochastic composite problems, requiring O(1) batch size. We conduct convergence analysis for DEEPSTORM with both constant and diminishing step sizes. Additionally, under proper initialization and a small enough desired solution error, we show that DEEPSTORM with a constant step size achieves a network-independent sample complexity, with an additional linear speed-up with respect to N over centralized methods. All codes are made available at https://github.com/gmancino/DEEPSTORM.