论文标题
分布式随机共识优化，具有非凸的动量非平滑问题
Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
论文作者
论文摘要
尽管已经提出了许多分布式优化算法来解决网络上的平滑或凸问题，但很少有人可以处理非凸面和非平滑问题。基于近端原始偶对偶的方法，本文提出了一种具有Nesterov动量的新（随机）分布式算法，以加速非凸和非平滑问题的优化。从理论上讲，我们表明所提出的算法可以在恒定步长下实现$ε$ - 定单的解决方案，并使用$ \ MATHCAL {O}（1/ε^2）$计算复杂性和$ \ Mathcal {O}（O}（O}（1/ε））$通信复杂性。与现有的基于梯度跟踪的方法相比，所提出的算法具有相同的计算复杂性顺序，但通信复杂性的较低顺序。据我们所知，提出的结果是第一个随机算法，具有$ \ mathcal {o}（1/ε）$对于非convex和非平滑问题的通信复杂性。提出了分布式非凸回归问题和深层神经网络分类问题的数值实验，以说明所提出算法的有效性。
While many distributed optimization algorithms have been proposed for solving smooth or convex problems over the networks, few of them can handle non-convex and non-smooth problems. Based on a proximal primal-dual approach, this paper presents a new (stochastic) distributed algorithm with Nesterov momentum for accelerated optimization of non-convex and non-smooth problems. Theoretically, we show that the proposed algorithm can achieve an $ε$-stationary solution under a constant step size with $\mathcal{O}(1/ε^2)$ computation complexity and $\mathcal{O}(1/ε)$ communication complexity. When compared to the existing gradient tracking based methods, the proposed algorithm has the same order of computation complexity but lower order of communication complexity. To the best of our knowledge, the presented result is the first stochastic algorithm with the $\mathcal{O}(1/ε)$ communication complexity for non-convex and non-smooth problems. Numerical experiments for a distributed non-convex regression problem and a deep neural network based classification problem are presented to illustrate the effectiveness of the proposed algorithms.
