Source-linked AI summary
Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
Zeyuan Allen-Zhu, Zheng Qu, Peter Richtárik, Yang Yuan
TL;DR
The paper addresses accelerated coordinate descent and the design of effective non-uniform sampling for coordinates with differing smoothness. It introduces NU ACDM with square-root smoothness sampling and reports running-time improvements of up to √n, including applications to randomized Kaczmarz and related problems.
Problem
The paper studies unconstrained minimization and the unclear design of non-uniform sampling distributions for coordinate descent when coordinate smoothness parameters differ.
Method
NU ACDM uses a non-uniform sampling method that selects coordinate i with probability proportional to √L_i, with a proof approach different from classical estimation sequences.
Results
The method runs up to √n faster in the non-uniform case and yields faster running times for applications including randomized Kaczmarz.
Takeaways & Limitations
The sampling method improves accelerated coordinate descent for problems with non-uniform coordinate smoothness and can exploit problem structure in applications such as linear-system solving.
Takeaways & Limitations
In the non-strongly convex case, convergence results with respect to different β are generally incomparable.
Abstract
from arXiv · showhide
Accelerated coordinate descent is widely used in optimization due to its cheap per-iteration cost and scalability to large-scale problems. Up to a primal-dual transformation, it is also the same as accelerated stochastic gradient descent that is one of the central methods used in machine learning. In this paper, we improve the best known running time of accelerated coordinate descent by a factor up to $\sqrt{n}$. Our improvement is based on a clean, novel non-uniform sampling that selects each coordinate with a probability proportional to the square root of its smoothness parameter. Our proof technique also deviates from the classical estimation sequence technique used in prior work. Our speed-up applies to important problems such as empirical risk minimization and solving linear systems, both in theory and in practice.
1 Introduction
The paper develops NU ACDM, an accelerated coordinate-descent method using square-root smoothness sampling, improving prior accelerated methods by up to √n. Its analysis applies across norm settings and targets applications including empirical risk minimization and linear systems.
- Motivation: Accelerated coordinate descent is important for large-scale optimization because coordinate updates reduce per-iteration cost, while its accelerated regime remains harder to design.The paper also relates accelerated coordinate descent to accelerated stochastic gradient descent through a primal-dual transformation.
- Method: NU ACDM samples coordinate i with probability proportional to √Li rather than the Li-based probabilities used by ACDM.The method addresses the uncertainty over how to choose non-uniform probabilities when coordinate smoothness parameters differ.
- Results: NU ACDM improves accelerated coordinate-descent running time by up to √n when the coordinate smoothness parameters are non-uniform.The stated improvement compares NU ACDM with ACDM in the relevant convergence bounds.
- Analysis: The new analysis avoids the estimation-sequence technique used in prior accelerated coordinate-descent analyses.The paper instead develops a different proof approach for the new sampling rule.
- Scope: For the general Lβ-norm setting, the method is faster than ACDM by up to √n, while convergence guarantees under different β values are generally incomparable in the non-strongly convex case.The paper notes that Euclidean-norm guarantees are especially relevant for strongly convex machine-learning objectives with ℓ2 regularization.
2 Applications
The paper applies accelerated coordinate descent to empirical risk minimization and linear systems, using data-dependent smoothness to motivate NU ACDM and its non-uniform sampling.
- Empirical Risk Minimization: In empirical risk minimization, coordinate smoothness parameters are data dependent and roughly proportional to feature-vector norm squares.This enables NU ACDM to improve the running time obtained by APCG or AccSDCA.
- Empirical Risk Minimization: NU ACDM samples feature vectors with probabilities roughly proportional to their Euclidean norms, unlike squared-norm sampling for non-accelerated SDCA.Using squared norms in the accelerated setting yields a running time similar to ACDM and worse than NU ACDM.
- Solving Linear Systems: Randomized Kaczmarz samples rows with probability proportional to squared row norms, and each iteration costs O(n).It produces an ε-approximate solution after the theorem’s stated number of iterations.
- Solving Linear Systems: ACDM views solving Ax = b as an m-variate quadratic minimization problem with coordinate smoothness Li = ∥ai∥2 and strong convexity σ = ∥A−1∥−2.This reduction allows accelerated coordinate descent to be applied to Kaczmarz.
- Solving Linear Systems: NU ACDM samples row i with probability proportional to ∥ai∥ and is always faster than ACDM, by up to a factor √m depending on problem structure.The comparison follows from ∥A∥F ≤ ∥A∥2,1 ≤ √m∥A∥F.
- Solving Linear Systems: The paper notes that NU ACDM also provides further speedups in cases where ACDM runs faster than conjugate gradient.This comparison concerns positive semidefinite square linear systems.
3 Other Related Work
Related work covers alternative non-uniform sampling, accelerated coordinate-descent extensions, parallelization, and methods for empirical risk minimization that do not use coordinate gradients.
- Alternative Sampling: Prior work studied Gauss-Southwell selection, non-uniform stochastic-gradient sampling, and arbitrary sampling on dual variables.These approaches provide perspectives related to, but distinct from, the paper’s sampling results.
- Scope and Extensions: The paper focuses on improving intrinsic coordinate-descent convergence rates rather than covering other important features.This stated scope boundary motivates omitting extensions such as proximal objectives and parallelization.
- Scope and Extensions: The paper’s results can support composite objectives with separable proximal functions, but the paper omits this extension because it complicates notation and proofs.The composite form is min_x{f(x) + Σ_i ψ_i(x_i)}.
- Scope and Extensions: Parallel coordinate updates are another important feature studied in prior work, including extensions to accelerated coordinate descent.The paper does not develop this feature here.
- Empirical Risk Minimization: For empirical risk minimization, AccSDCA and Katyusha achieve relevant fast running times but do not solve the problem through coordinate gradients.Accelerated coordinate descent methods such as APCG are therefore not the only route to fast ERM algorithms.
4 Notations
This section defines the optimization notation, smoothness assumptions, convexity assumptions, and coordinate-wise smoothness used throughout the paper.
- The goal is to find x satisfying f(x) − f(x∗) ≤ ε for a specified accuracy ε > 0.
- L-smoothness bounds full-gradient variation by L times the Euclidean distance between points.
- σ-strong convexity lower-bounds f(y) using the first-order expansion at x plus a quadratic curvature term.
- Coordinate-wise smoothness uses parameters (L1, ..., Ln) to bound each coordinate-gradient change along its corresponding coordinate direction.
- The same results extend from coordinate gradients to more general block-wise gradients under a block partition of the variables.
5 NUACDM in the Strongly Convex Case
For strongly convex, coordinate-wise smooth objectives, NU ACDM samples coordinates non-uniformly and combines accelerated interpolation, coordinate-gradient updates, and mirror-descent analysis to obtain its convergence guarantee.
- NU ACDM applies to coordinate-wise smooth f that is σβ-strongly convex with respect to the weighted norm Lβ for β ∈ [0, 1].
- The method forms xk+1 from zk and yk, samples coordinate i with probability proportional to L_i^α, and performs two updates using the selected coordinate gradient.
- The algorithm supports block-wise smoothness through a permutation-based partition of variables and block-gradient Lipschitz parameters.
- Theorem 5.1 gives an expected convergence guarantee for the output yT under coordinate-wise smoothness and weighted-norm strong convexity.
- Proof outline: The proof combines coordinate-wise objective decrease, a mirror-descent formulation, probabilistic averaging, convexity, and strong convexity before telescoping across iterations.
- Parameter choices: The parameter choices enforce the relation 1 + ησβ = 1/(1−τ), while coordinate smoothness and strong convexity ensure the selected parameters are valid.
6 NUACDM in the Non-Strongly Convex Case
For non-strongly convex coordinate-wise smooth objectives, NU ACDMns introduces a β-parameterized accelerated scheme with sampling proportional to a power of coordinate smoothness and proves a corresponding expected-error bound.
- NU ACDMns handles non-strongly convex, coordinate-wise smooth objectives with parameters (L1, ..., Ln).
- The method forms xk+1 from zk and yk, samples coordinate i with probability proportional to L_i^α, and uses two updates based on ∇if(xk+1).
- Its parameter satisfies α = (1−β)/2, linking the sampling distribution to the chosen β ∈ [0, 1].
- Theorem 6.1 states an expected convergence guarantee for yT after T iterations, with the displayed rate depending on β and the weighted initial distance.
- Proof outline: The proof combines coordinate-wise decrease, mirror-descent analysis, convexity, Cauchy–Schwarz, and the sampling choice before telescoping the resulting inequality.
- Proof outline: The analysis fixes τk and ηk so the recursive inequalities telescope across iterations and yield the final bound.
7 Experiments on Empirical Risk Minimization
Experiments on ERM problems test NU ACDM across ridge, Lasso, and non-strongly convex penalty regression, finding the clearest practical gains when coordinate smoothness is highly non-uniform.
- Experimental setup: The experiments use news20, w8a, and covtype datasets whose examples have non-uniform Euclidean norms.
- Strongly convex objectives: Ridge-regression comparisons measure dual-objective distance to minimum against dataset passes, while Table 2 reports theoretical NU ACDM speed-up factors over ACDM.
- Strongly convex objectives: The experiments confirm the predicted advantage of NU ACDM over ACDM, with the largest improvements on news20 and under greater non-uniformity.
- Strongly convex objectives: APCG performs poorly on news20 because its β = 1 setting relies on Lβ-norm strong convexity that differs substantially from Euclidean-norm strong convexity under highly non-uniform Li.
- Lasso: For Lasso, a small ℓ2 regularizer makes the dual smooth while introducing an O(λ2) objective error, enabling comparisons with accelerated coordinate methods.
- Non-strongly convex objectives: For non-strongly convex ℓ1-ℓ2 penalty regression, NU ACDMns has a clear advantage when Li are highly non-uniform, whereas ACDM is slightly faster on covtype.
- Dependence on β: Across β values, smaller β values are generally more preferred in practice, while APCG and NU ACDMns with β = 1 perform similarly.
8 Experiments on Solving Linear Systems
The experiments generate random linear systems with heterogeneous row norms and compare NU ACDM against ACDM and randomized Kaczmarz. NU ACDM’s advantage over ACDM grows as the fraction of high-norm rows decreases, matching the expected smoothness-based speedup.
- Experimental setup: The experiment compares randomized Kaczmarz, ACDM, and NU ACDM on randomly generated linear systems.Systems use m = 300 and n = 100, with rows scaled to norms 10 or 1.
- Expected behavior: NU ACDM is expected to gain more over ACDM when few rows have large norms, because row norms determine coordinate smoothness.The study computes theoretical speedup factors for these settings.
- Results: Both accelerated methods outperform non-accelerated randomized Kaczmarz, while NU ACDM and ACDM are comparable when r = 100%.NU ACDM’s relative advantage becomes more significant as r decreases.
Appendix
Figure 7 compares ridge-regression performance using primal objective distance to minimum against the number of dataset passes.
- Figure 7: Figure 7 reports performance for ridge regression in the primal formulation.The figure compares methods using the primal objective distance to minimum.
- Figure 7: The y axis measures primal objective distance to minimum.This axis indicates optimization progress toward the minimum.
- Figure 7: The x axis measures the number of passes through the dataset.Performance is evaluated as optimization proceeds across dataset passes.