Asynchronous Accelerated Proximal Stochastic Gradient for Strongly Convex Distributed Finite Sums

Abstract

In this work, we study the problem of minimizing the sum of strongly convex functions split over a network of $n$ nodes. We propose the decentralized and asynchronous algorithm ADFS to tackle the case when local functions are themselves finite sums with $m$ components. ADFS converges linearly when local functions are smooth, and matches the rates of the best known finite sum algorithms when executed on a single machine. On several machines, ADFS enjoys a $O(\sqrt{n})$ or $O(n)$ speed-up depending on the leading complexity term as long as the diameter of the network is not too big with respect to $m$. This also leads to a $\sqrt{m}$ speed-up over state-of-the-art distributed batch methods, which is the expected speed-up for finite sum algorithms. In terms of communication times and network parameters, ADFS scales as well as optimal distributed batch algorithms. As a side contribution, we give a generalized version of the accelerated proximal coordinate gradient algorithm using arbitrary sampling that we apply to a well-chosen dual problem to derive ADFS. Yet, ADFS uses primal proximal updates that only require solving one-dimensional problems for many standard machine learning applications. Finally, ADFS can be formulated for non-smooth objectives with equally good scaling properties. We illustrate the improvement of ADFS over state-of-the-art approaches with simulations.

References in corpus (12)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Revisiting Distributed Synchronous SGD
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• D${}^2$: Decentralized Training over Decentralized Data
• A Universal Catalyst for First-Order Optimization
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Asynchronous Decentralized Parallel Stochastic Gradient Descent
• Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions
• Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives
• ASAGA: Asynchronous Parallel SAGA
• DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization
• Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication

Cited by in corpus (11)

• Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
• An introduction to decentralized stochastic optimization with gradient tracking
• Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
• Asynchronous Decentralized Successive Convex Approximation
• Gradient tracking and variance reduction for decentralized optimization and machine learning
• Optimization over time-varying networks with unbounded delays
• Optimal Complexity in Decentralized Training
• A general framework for decentralized optimization with first-order methods
• Byzantine-Robust Decentralized Stochastic Optimization over Static and Time-Varying Networks
• Distributed Stochastic Optimization With Unbounded Subgradients Over Randomly Time-Varying Networks
• Practical sufficient conditions for convergence of distributed optimisation algorithms over communication networks with interference