Distributed Stochastic Inertial-Accelerated Methods with Delayed Derivatives for Nonconvex Problems
Distributed Stochastic Inertial-Accelerated Methods with Delayed Derivatives for Nonconvex Problems
复制标题
DOI：
10.1137/21m1435719
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Yangyang Xu;Yibo Xu;Yonggui Yan;Jiewei Chen
中科院分区：
文献类型：
--
作者：
Yangyang Xu;Yibo Xu;Yonggui Yan;Jiewei Chen
随机梯度法是求解随机优化问题的主要方法。在光滑非凸问题上，一些加速技术已经被应用来提高SGMS的收敛速度。然而，将某种加速技术应用于求解非光滑非凸问题的随机次梯度法(SsGM)却鲜有人涉足。此外，很少有人对具有延迟衍生品的(加速的)上证综指进行分析。信息延迟自然会发生在分布式系统中，在分布式系统中，计算人员之间不会相互协调。本文提出了一种求解非光滑非凸随机优化问题的惯性近似式SsGM。在分布式环境下，即使存在延迟的导数信息，所提出的方法也能保证收敛。建立了三类非凸问题的收敛速度结果：具有凸正则的弱凸非光滑问题、具有非光滑凸正则的复合非凸问题和光滑非凸问题。对于每个问题类，对于$K$迭代，收敛速度是在梯度范数平方的期望值中的$O(1/K^{\FRAC{1}{2}})$。在分布式环境下，该方法的收敛速度会因信息延迟而变慢。然而，对于后两类问题，减速效应将随着迭代次数的增加而减弱。我们在三个应用上测试了所提出的方法。数值结果清楚地表明了采用惯性加速的优越性。此外，我们观察到异步更新比同步更新具有更高的并行化速度，尽管前者使用延迟导数。我们的源代码在https://github.com/RPI-OPT/Inertial-SsGM上发布
Stochastic gradient methods (SGMs) are predominant approaches for solving stochastic optimization. On smooth nonconvex problems, a few acceleration techniques have been applied to improve the convergence rate of SGMs. However, little exploration has been made on applying a certain acceleration technique to a stochastic subgradient method (SsGM) for nonsmooth nonconvex problems. In addition, few efforts have been made to analyze an (accelerated) SsGM with delayed derivatives. The information delay naturally happens in a distributed system, where computing workers do not coordinate with each other. In this paper, we propose an inertial proximal SsGM for solving nonsmooth nonconvex stochastic optimization problems. The proposed method can have guaranteed convergence even with delayed derivative information in a distributed environment. Convergence rate results are established to three classes of nonconvex problems: weakly-convex nonsmooth problems with a convex regularizer, composite nonconvex problems with a nonsmooth convex regularizer, and smooth nonconvex problems. For each problem class, the convergence rate is $O(1/K^{\frac{1}{2}})$ in the expected value of the gradient norm square, for $K$ iterations. In a distributed environment, the convergence rate of the proposed method will be slowed down by the information delay. Nevertheless, the slow-down effect will decay with the number of iterations for the latter two problem classes. We test the proposed method on three applications. The numerical results clearly demonstrate the advantages of using the inertial-based acceleration. Furthermore, we observe higher parallelization speed-up in asynchronous updates over the synchronous counterpart, though the former uses delayed derivatives. Our source code is released at https://github.com/RPI-OPT/Inertial-SsGM