On optimal probabilities in stochastic coordinate descent methods

By Peter Richtárik, Martin Takác. 2013

132 citations recorded by the source corpus.

We propose and analyze a new parallel coordinate descent method—NSync—in which at each iteration a random subset of coordinates is updated, in parallel, allowing for the subsets to be chosen using an arbitrary probability law. This is the first method of this type. We derive convergence rates under a strong convexity assumption, and comment on how to assign probabilities to the sets to optimize the bound. The complexity and practical performance of the method can outperform its uniform variant by an order of magnitude. Surprisingly, the strategy of updating a single randomly selected coordinate per iteration—with optimal probabilities—may require less iterations, both in theory and practice, than the strategy of updating all coordinates at every iteration.

Subfields: Artificial Intelligence, Statistics and Probability, 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 Statistics and Probability

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “…by recent results from the optimization literature [Gower et al., 2019], we give the ﬁrst stochastic reformulation of the variational inequality problem (1) which enables us to provide convergence guarantees of SGDA and SCO under the arbitrary sampling paradigm [Richtárik and Takáˇc, 2016].”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, methodology): “See e.g. (Shalev-Shwartz & Zhang, 2013c) for several concrete applications.”
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).”
Not All Samples Are Created Equal: Deep Learning with Importance Sampling (2018, background): “For convex optimization problems, many works (Bordes et al., 2005; Zhao & Zhang, 2015; Needell et al., 2014; Can´evet et al., 2016; Richt´arik & Tak´aˇc, 2013) have taken advantage of the difference in importance among the samples to improve the convergence speed of stochastic optimization methods.”
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.”
Accelerated, Parallel, and Proximal Coordinate Descent (2013, methodology): “An ESO inequality for a uniform distributed sampling was developed in [14] and that nonuniform samplings and ESO, together with a parallel coordinate descent method based on such samplings, was proposed in [15].”
Parallel coordinate descent methods for big data optimization (2012, methodology): “For instance, methods based on ESO can be compared favorably (9)Revision note: See [18].”
Quartz: Randomized Dual Coordinate Ascent with Arbitrary Sampling (2015, background): “Assumption (5) was for the ﬁrst time introduced in [16].”
L-SVRG and L-Katyusha with Arbitrary Sampling (2019, background): “For an integer τ ∈ [n], a τ -nice sampling refers to the case when |S| = τ with probability one and each subset of size τ is selected with equal probability, see (Richtárik and Takáč, 2016).”
Importance Sampling for Minibatches (2016, background): “In terms of theory, as in the case of minibatching, this strategy leads to the improvement of the leading constant in the complexity estimate, typically via replacing the maximum of certain data-dependent quantities by their average [24, 12, 40, 23, 19, 2, 3].”
Nonconvex Variance Reduced Optimization with Arbitrary Sampling (2018, methodology): “To the best of our knowledge, there are only a handful of papers on this topic [30, 6], none of which apply to the non-convex setting considered here, nor to the methods we will analyze, and the problem is open.”
SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization (2015, unknown): “(7)”
Distributed Block Coordinate Descent for Minimizing Partially Separable Functions (2014, methodology): “Distributed coordinate descent methods were developed and studied recently by Richtárik and Takáč [23] (algorithm: Hydra) and Fercoq et al. [4] (Algorithms: Hydra2).”