Coordinate descent with arbitrary sampling I: algorithms and complexity†

By Zheng Qu, Peter Richtárik. 2014

135 citations recorded by the source corpus.

We study the problem of minimizing the sum of a smooth convex function and a convex block-separable regularizer and propose a new randomized coordinate descent method, which we call ALPHA. Our method at every iteration updates a random subset of coordinates, following an arbitrary distribution. No coordinate descent methods capable to handle an arbitrary sampling have been studied in the literature before for this problem. ALPHA is a very flexible algorithm: in special cases, it reduces to deterministic and randomized methods such as gradient descent, coordinate descent, parallel coordinate descent and distributed coordinate descent—both in nonaccelerated and accelerated variants. The variants with arbitrary (or importance) sampling are new. We provide a complexity analysis of ALPHA, from which we deduce as a direct corollary complexity bounds for its many variants, all matching or improving best known bounds.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, Statistics and Probability

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 Computer Vision and Pattern Recognition

In Statistics and Probability

Citations in the corpus

Federated Learning: Strategies for Improving Communication Efficiency (2016, methodology): “This strategy can be seen as the combination of the master training method and a randomized block coordinate minimization approach [15, 14].”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, background): “Mini-batch versions of both SGD and coordinate descent (CD) (Richt ´ arik & Tak ´ a ˇ c, 2013b;a; Shalev-Shwartz & Zhang, 2013b; Yang, 2013; Qu & Richt´arik, 2014; Qu et al., 2014) suffer from their convergence rate degrading towards the rate of batch gradient descent, as the size of the mini-batch ”
Distributed optimization with arbitrary local solvers (2015, background): “…with the massive growth of available datasets, major roadblocks still persist in the distributed setting, where data no longer ﬁts in the memory of a single computer, and computation must be split across multiple machines in a network [3, 7, 12, 18, 22, 28, 32, 34, 37, 46, 50, 58, 60, 62, 76].”
SGD: General Analysis and Improved Rates (2019, methodology): “These subsets will be selected using a random set valued map S , in the literature referred to by the name sampling (Richt´arik & Tak´aˇc, 2016; Qu & Richt´arik, 2016).”
Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, background): “ smooth convex optimization [47], composite convex optimization [62], and parallel/subspace descent variants [63]. These results were later further extended to handle arbitrary sampling distributions [58, 59,61,6] . Accelerated variants of RCD were studied in [34,16,1]. For other non-randomized coor”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “For more information about modern dual and primal methods we refer the reader to the literature on randomized coordinate descent methods [5], [8]–[18] and stochastic gradient methods [4], [17], [19]–[24], respectively.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “However, mini-batch versions of both SGD and coordinate descent (CD) [151, 149, 164, 111, 188, 176, 150, 140, 141, 143, 38, 40] suffer from their convergence rate degrading towards the rate of batch gradient descent as the size of the mini-batch is increased.”
Nonconvex Variance Reduced Optimization with Arbitrary Sampling (2018, methodology): “For dual methods based on coordinate descent, importance sampling is relatively well understood (Nesterov, 2012; Richtárik and Takáč, 2014; Qu and Richtárik, 2016; Qu et al., 2015; Allen-Zhu et al., 2016).”
L-SVRG and L-Katyusha with Arbitrary Sampling (2019, methodology): “Methods already endowed with arbitrary sampling variants and analysis include, among others, the primal-dual method Quartz [13], accelerated randomized coordinate descent [11, 12, 5], stochastic primal-dual hybrid gradient method [2], SGD [4], and SAGA [10].”
Randomized Iterative Methods for Linear Systems (2015, background): “For a brief up to date account of the development in this area, we refer the reader to [12, 28] and the references therein.”
Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory (2017, background): “The notion of importance sampling developed in the last 5 years in the randomized optimization and machine learning literature [45, 64, 42, 40] can be seen a type of stochastic preconditioning, somewhat reverse to what we have outlined above.”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, background): “a Gauss-Seidel for linear systems) and its block variant, Randomized Block Coordinate Descent we suggest [104, 139, 166, 167, 160, 161, 163, 22, 102, 51, 2, 192].”
99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it (2019, background): “[28] Zheng Qu and Peter Richtárik.”
Faster Coordinate Descent via Adaptive Importance Sampling (2017, background): “…random [Hsieh et al., 2008, Shalev-Shwartz and Tewari, 2011, Lacoste-Julien et al., 2013, Shalev-Shwartz and Zhang, 2012], recently [Nesterov, 2012, Qu and Richtárik, 2016, Zhao and Zhang, 2014, Allen-Zhu et al., 2016] showed that an appropriately defined fixed non-uniform sampling…”