Achieving Acceleration in Distributed Optimization via Direct Discretization of the Heavy-Ball ODE
arXiv:1811.02521
Abstract
We develop a distributed algorithm for convex Empirical Risk Minimization, the problem of minimizing large but finite sum of convex functions over networks. The proposed algorithm is derived from directly discretizing the second-order heavy-ball differential equation and results in an accelerated convergence rate, i.e, faster than distributed gradient descent-based methods for strongly convex objectives that may not be smooth. Notably, we achieve acceleration without resorting to the well-known Nesterov's momentum approach. We provide numerical experiments and contrast the proposed method with recently proposed optimal distributed optimization algorithms.
References in corpus (7)
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- A Variational Perspective on Accelerated Methods in Optimization
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
- Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
- Direct Runge-Kutta Discretization Achieves Acceleration
- Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method