Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization

Abstract

Due to their simplicity and excellent performance, parallel asynchronous variants of stochastic gradient descent have become popular methods to solve a wide range of large-scale optimization problems on multi-core architectures. Yet, despite their practical success, support for nonsmooth objectives is still lacking, making them unsuitable for many problems of interest in machine learning, such as the Lasso, group Lasso or empirical risk minimization with convex constraints. In this work, we propose and analyze ProxASAGA, a fully asynchronous sparse method inspired by SAGA, a variance reduced incremental gradient algorithm. The proposed method is easy to implement and significantly outperforms the state of the art on several nonsmooth, large-scale problems. We prove that our method achieves a theoretical linear speedup with respect to the sequential version under assumptions on the sparsity of gradients and block-separability of the proximal term. Empirical benchmarks on a multi-core architecture illustrate practical speedups of up to 12x on a 20-core machine.

Appears in Advances in Neural Information Processing Systems 30 (NIPS 2017), 28 pages

References in corpus (6)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• Proximal Stochastic Dual Coordinate Ascent
• The Sound of APALM Clapping: Faster Nonsmooth Nonconvex Optimization with Stochastic Asynchronous PALM
• Asynchronous Stochastic Block Coordinate Descent with Variance Reduction

Cited by in corpus (2)

• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• Communication trade-offs for synchronized distributed SGD with large step size