Research map / Optimization / Nonconvex and smooth optimization
Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that for unit-diagonal positive-definite quadratics with permutation-invariant Hessians, the epoch-wise contraction upper bound of random-permutation CD is strictly below the contraction lower bound of random CD, and conjectures this extends to all positive-definite quadratics.
Problem
Whether random-permutation coordinate descent (RPCD) provably converges faster than uniform random coordinate descent (RCD), since prior work only compared upper bounds or lacked rigorous gaps, even for positive-definite quadratics.
Approach
For quadratics with permutation-invariant Hessians sigma*I + (1-sigma)*11^T, RPCD's operator closes on a 2x2 subspace, yielding a spectral-radius upper bound; combined with a new RCD lower bound valid for almost all initializations, this shows a strict per-instance gap, and a numerical search suggests this class is the worst case for RPCD among all positive-definite quadratics.
Key results
- For A in the permutation-invariant class, RPCD epoch contraction upper bound max{(1-1/n)^n, (1-sigma/n)^{2n}} is strictly below the RCD lower bound (1-1/n+(1-sigma)^2/n)^n for every sigma in (0,1), establishing a per-instance gap.
- The RCD lower bound (1-1/n+(1-sigma)^2/n)^n is stronger than the prior bound max{(1-1/n)^n,(1-sigma/n)^{2n}} and holds for almost all initializations.
- Numerical algorithmic search over n=3..6 found permutation-invariant instances as worst cases for the RPCD spectral-radius upper bound, supporting the conjecture for general positive-definite quadratics.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use random-permutation coordinate updates instead of uniform sampling with replacement | Coordinate descent on quadratics with Hessian in A_sigma · Quadratics with Hessian in A_sigma | expected squared iterate norm contraction rate: \max \bigset{\bigopen{1 - \frac{1}{n}}^n, \bigopen{1 - \frac{\sigma}{n}}^{2n}} vs. \bigopen{1 - \frac{1}{n} + \frac{(1 - | Helped |
| Use random-permutation coordinate updates instead of uniform sampling with replacement | Coordinate descent on quadratics with permutation-invariant Hessians · Permutation-invariant quadratic functions | convergence speed | Helped |
| Use random-permutation coordinate updates instead of uniform sampling with replacement | Coordinate descent on general positive-definite quadratic functions · General positive-definite quadratics | convergence speed | Helped |
| Use random-permutation coordinate updates instead of uniform sampling with replacement | Coordinate descent on a quadratic plus scaled log-sum-exp term · Quadratic plus scaled LSE | convergence speed | Helped |
Surprising findings
- The stated RPCD upper bound is not a clean derivation of prior work's rate: the authors note the new bound is weaker in the leading term but tighter overall in explicit form.
- A bump appears in the RPCD spectral radius near sigma=1 for large n, breaking monotonicity.
Limitations
- Upper bound for RPCD is proven only for the permutation-invariant class; general quadratics remain a conjecture.
- Analysis restricted to quadratic objectives and unit-diagonal Hessians, with no non-quadratic or block results.
- Partially invariant matrix case reduces to an asymmetric 4x4 spectral problem left without full analysis.
Experimental setup
Datasets: synthetic quadratics l2-regularized sparse logistic regression (synthetic)
Metrics: contraction rate of expected iterate norm spectral radius
Baselines: RCD CCD RPCD bounds of prior work
Builds on: random reshuffling cyclic coordinate descent convergence analysis
Closest papers by meaning
- Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems (ICML 2025 · similarity 0.88)
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.86)
- A Unified Analysis of Stochastic Gradient Descent with Arbitrary Data Permutations and Beyond (NeurIPS 2025 · similarity 0.86)
- Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learning (AAAI 2025 · similarity 0.86)
- Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization (ICML 2025 · similarity 0.85)
- Differentiable extensions with rounding guarantees for combinatorial optimization over permutations (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.