Source-linked AI summary
On Optimal Probabilities in Stochastic Coordinate Descent Methods
Peter Richtárik, Martin Takáč
TL;DR
Coordinate descent can update coordinates serially or in parallel, but uniform selection may not be the best choice. This paper analyzes NSync, which updates randomly sampled subsets with nonuniform probabilities under strong convexity. Its analysis and experiments indicate that optimal single-coordinate updates can require fewer iterations than fully parallel updates in some settings.
Problem
Method
Results
Takeaways & Limitations
The paper's bound can be optimized through the choice of coordinate probabilities, and optimal single-coordinate updates may outperform fully parallel updates when ω is large enough.
Source: §4 · p. 4The convergence analysis assumes nonuniform ESO and strong convexity, with strong convexity specified in a weighted norm.
Source: §2 · p. 2
Abstract
from arXiv · showhide
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 non-uniformly. 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.
1 Introduction
NSync is a parallel coordinate descent method for strongly convex, smooth objectives that updates random subsets of coordinates and allows nonuniform sampling. The paper presents it as the first nonuniform parallel coordinate descent method to the authors’ knowledge.
1 Introduction
- NSync is proposed for objectives that are strongly convex and smooth.Source: §1 · p. 1
- NSync updates a randomly selected subset of coordinates in parallel, with each coordinate moving along its negative partial derivative using a chosen stepsize.The updates are synchronized, and the subset is drawn independently at each iteration according to its assigned probability.Source: §1 · p. 1
- To the authors’ knowledge, NSync is the first nonuniform parallel coordinate descent method.Earlier work cited in the passage considered nonuniform serial methods updating one or two coordinates at a time.Source: §1 · p. 2
2 Analysis
The analysis establishes a high-probability convergence guarantee for NSync under nonuniform ESO and strong convexity assumptions. Its rate depends on the analysis parameters, while the theorem leaves practical choices of stepsizes and subset probabilities to the following section.
2 Analysis
- The analysis assumes nonuniform ESO and strong convexity, with strong convexity measured in a weighted norm.The ESO assumption generalizes the concept used in prior work to nonuniform samplings.Source: §2 · p. 2
- Under Assumptions 1 and 2, Theorem 3 bounds the iterations sufficient for NSync to approximately solve the optimization problem with high probability.The theorem's bound is stated in terms of the objective accuracy ε and failure probability ρ.Source: §2 · p. 2
- The expected objective gap contracts geometrically by factor (1−µ), and Markov's inequality bounds the probability that the gap exceeds ε after K iterations by ρ.The proof passage defines µ as γ/Λ.Source: §2 · p. 2
- The theorem is generic about when its assumptions hold and how to choose stepsizes and subset probabilities; the next section addresses those choices.Source: §2 · p. 3
3 Nonuniform samplings and ESO
The section gives conditions for nonuniform samplings to satisfy the ESO assumption and describes a tractable two-stage sampling scheme. It also illustrates the smoothness setup using a least-squares objective.
3 Nonuniform samplings and ESO
- For coordinate-smooth objectives, the coordinate gradient changes are bounded using positive coordinate-specific Lipschitz constants L_i.Source: §3 · p. 3
- For a sum of component functions depending on subsets of coordinates, separability degree ω is the largest size of those subsets.Source: §3 · p. 3
- For f(x)=1/2∥Ax−b∥², the coordinate constants are L_i=∥A_:i∥², and ω is the maximum number of nonzeros in a row of A.Source: §3 · p. 3
- The proposed sampling first chooses a set S_j with probability q_j, then draws uniformly a τ-sized subset from that set.This two-stage procedure avoids computing the probability of every possible coordinate subset.Source: §3 · p. 3
- Under Assumptions 4 and 5, Theorem 7 states that the described sampling satisfies Assumption 1 with p given by (12), for any w meeting the stated condition.Source: §3 · p. 3
4 Optimal probabilities
The section shows how sampling choices can minimize the convergence-bound quantity Λ, including in the serial setting. It also compares optimal serial sampling with uniform serial and fully parallel methods, and finds that diagonal rescaling cannot improve the condition numbers Li/vi.
4 Optimal probabilities
- Choosing sets S_j and probabilities q_j to minimize Λ optimizes the method’s convergence rate, and the minimizing q can be computed by a linear program.The program has c+1 variables, 2n linear inequality constraints, and one linear equality constraint.Source: §4 · p. 4
- The optimal serial method uses probabilities that minimize Λ over p, with stepsizes w_i = L_i + v_i.Source: §4 · p. 4
- Uniform serial sampling can have Λ_US much larger than the optimal serial method’s Λ_OS.Source: §4 · p. 4
- Diagonal rescaling cannot improve the condition numbers L_i/v_i.The change of variables alters coordinate Lipschitz constants and weights, but not these condition numbers.Source: §4 · p. 4
- For sufficiently large ω, Λ_FP can be at least Λ_OS, so the optimal serial method can be faster than updating every coordinate each iteration.Source: §4 · p. 4
5 Experiments
Preliminary small-scale experiments illustrate the theory: optimal serial sampling can be faster than uniform sampling, though it is sensitive to errors in the constants. A nonuniform serial method can also be faster than the fully parallel variant in the tested settings.
5 Experiments
- The experiments were preliminary, small-scale runs on problems of form (11), with 100 runs and 95% confidence intervals for the left-plot comparison.Source: §5 · p. 4
- The optimal serial method can be faster than uniform sampling, but is sensitive to over- or under-estimating L_i and v_i.Source: §5 · p. 4
- In the tested settings, the nonuniform serial method can be faster than the fully parallel variant.The comparison used m = 8, n = 10, and three values of ω.Source: §5 · p. 4