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

By Fabian Pedregosa, Rémi Leblond, Simon Lacoste-Julien. 2017

33 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

Citations in the corpus

Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, methodology): “Pedregosa et al. (2017) extend the Asaga algorithm presented in Section 3.2 to the proximal setting.”
Communication trade-offs for synchronized distributed SGD with large step size (2019, neutral): “…Keuper and Pfreundt (2015); De and Goldstein (2015); Feyzmahdavian et al. (2015); Lian et al. (2015); Mania et al. (2015); Zhao and Li (2015); Duchi et al. (2015); Chen et al. (2016a); Lian et al. (2017a); Pedregosa et al. (2017); Lian et al. (2017b); Leblond et al. (2018); Alistarh et al. (2018).”
Distributed Learning with Sparse Communications by Identification (2018, methodology): “We also mention that the idea of randomly selecting some entries has been already applied in distributed algorithms: random selection is used to sparsify local gradients in the synchronous algorithm of [68], to sparsify the variance-reducing term in the stochastic algorithm of [47], or to sparsify u”
Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization (2018, background): “Note that some asynchronous parallel and distributed variants [46, 47, 48, 49] of stochastic variance reduction methods have also been proposed for such stochastic settings.”
A Delay-tolerant Proximal-Gradient Algorithm for Distributed Learning (2018, background): “(Recht et al., 2011), Distributed SDCA (Takáč et al., 2015), Distributed SVRG (Lee et al., 2015; Zhao & Li, 2016), ASAGA (Leblond et al., 2017), ProxASAGA (Pedregosa et al., 2017)).”
Asynchronous Distributed Learning with Sparse Communications and Identification (2018, methodology): “Random selection is used to sparsify local gradients in the synchronous algorithm of [33], to sparsify the variance-reducing term in the stochastic algorithm of [13] and [24], or to sparsify updates in ﬁxed-point iterations [25].”