Pith. sign in

REVIEW 2 major objections 3 minor 33 references

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent

T0 review · 2 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that random-permutation coordinate descent (RPCD) converges strictly faster than uniformly random coordinate descent (RCD) on every positive-definite quadratic whose Hessian lies in the class $A_\sigma$, a…

desk verdict A genuinely new per-instance gap between RCD and RPCD on a natural quadratic class, but the small-n proof leans on a computer-assisted Sturm check that is not valid as written. read the letter →

arxiv 2505.23152 v1 pith:NQ46CIRB submitted 2025-05-29 math.OC

Donghwa Kim , Jaewook Lee , Chulhee Yun This is my paper
classification math.OC MSC 90C2565K0568W20
keywords coordinatedescentrandompermutationswithout-replacementsamplingconvergenceratequadraticoptimizationpermutation-invariantHessianreshufflingcontraction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Stochastic coordinate descent samples one coordinate uniformly at each step (RCD), while random-permutation coordinate descent (RPCD) sweeps all $n$ coordinates in a fresh random order. Empirically the shuffled version is usually faster, but for the simplest possible test case, positive-definite quadratics, no proof of a strict gap had been found. This paper proves the gap for a class $A_\sigma$ of unit-diagonal Hessians built from one permutation-invariant block $\sigma I_k+(1-\sigma)1_k1_k^\top$ plus an identity block, and their sign flips. For every instance in this class, the per-epoch contraction rate of RPCD is at most $\max\{(1-1/n)^n,(1-\sigma/n)^{2n}\}$, while RCD's per-epoch rate is at least $\left(1-1/n+(1-\sigma)^2/n\right)^n$, and the RPCD upper bound lies strictly below the RCD lower bound for $\sigma\in(0,1)$. The RCD lower bound holds for all positive-definite quadratics; extending the RPCD upper bound to all of them is stated as a conjecture supported by numerical maximization.

What carries the argument

The carrier of the argument is the second-moment operator $M_A(X)=\mathbb{E}[T_A^\top X T_A]$, where $T_A$ is the random iteration matrix ($T^{\mathrm{RCD}}_{A,i}=I-E_iA$ or $T^{\mathrm{RPCD}}_{A,p}=I-P\Gamma_P^{-1}P^\top A$); its spectral radius on an invariant subspace controls the asymptotic rate of $\mathbb{E}[\|x_k\|^2]$ through power iteration. For $A=\sigma I+(1-\sigma)11^\top$, both operators leave the two-dimensional subspace $\operatorname{span}\{I,11^\top\}$ invariant, so the analysis reduces to a $2\times2$ matrix. For RPCD the entries of that matrix are non-negative, which lets the authors use the infinity norm; bounding the two row sums turns the theorem into a finite comparison of polynomials in $\sigma$. Those polynomial comparisons are completed with Sturm sequences, partly by hand for large $n$ and partly by the exact computer-assisted checks in Appendix C.

What would settle it

Run the paper's own exact computer-algebra verification at rational arithmetic: it asserts that certain polynomials $T_i(m,\sigma)/[m(m-1)]$ stay below the comparison bounds on $(0,0.6]$, $[0.6,0.8]$, and $[0.8,1)$, with zero roots in each interval and positive endpoint values. A single counterexample, for instance $\sigma=0.01$, $n=6$, $m=3$ with $T_1(m,\sigma)/[m(m-1)]>(1-\sigma/n)^{2n}$, would falsify the small-dimension part of Theorem 3.3; alternatively, a direct numerical simulation of RPCD on any $A\in A_\sigma$ whose measured per-epoch contraction exceeds the claimed maximum would disprove the bound.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is an instancewise separation of randomized coordinate descent variants, not a worst-case comparison. For any $A\in A_\sigma$ with $\sigma\in(0,1)$, Theorem 3.3 bounds the asymptotic per-epoch contraction of RPCD, $\lim_{K\to\infty}(\mathbb{E}[\|x_K\|^2]/\|x_0\|^2)^{1/K}$, from above by $\max\{(1-1/n)^n,(1-\sigma/n)^{2n}\}$, and Theorem 3.4 bounds the corresponding per-epoch RCD contraction from below by $\left(1-1/n+(1-\sigma)^2/n\right)^n$. The first number is strictly smaller than the second for every $\sigma\in(0,1)$, which is what makes the separation provable for every individual problem instance rather than only on average. The bound is strong because the theorem excludes only a Lebesgue measure zero set of initial points, so the ordering is a property of the algorithm-problem pair. A companion lower bound (Theorem 3.1) applies to every positive-definite quadratic, and the authors conjecture that the same RPCD upper bound in fact holds for all such quadratics.

Load-bearing premise

The load-bearing premise is that the finite set of polynomial inequalities verified by the exact computer-assisted Sturm-sequence script in Appendix C is transcribed and checked correctly, since that machine component is what closes the strict gap on small and moderate dimensions.

Editorial extensions

If this is right

  • For every $\sigma\in(0,1)$, every $A\in A_\sigma$, and almost every initialization, the asymptotic per-epoch contraction of RPCD is strictly smaller than that of RCD, so shuffled sweeping is provably faster on each such instance.
  • The RCD lower bound in Theorem 3.1 applies to all positive-definite quadratics, so if Conjecture 4.1 holds, RPCD would be provably faster than RCD on the entire class of smooth strongly convex quadratics.
  • The comparison already holds after finitely many epochs: Appendix G gives a $\sigma$-dependent epoch threshold after which the expected squared-norm bounds for RPCD fall below those for RCD.
  • Translated quadratics and expected function values are covered up to explicit constant factors, so the instancewise ordering extends beyond origin-centered problems and beyond the squared-norm measure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same subspace-reduction idea should apply to block-structured Hessians with repeated blocks: the paper sketches a four-dimensional basis that converts the problem into a $4\times4$ spectral analysis in two parameters, a finite but heavier computation rather than a new conceptual step.
  • If Conjecture 4.1 is true, the practical takeaway is that on any strongly convex quadratic, sweeping coordinates without replacement is never asymptotically worse than i.i.d. uniform sampling, so random-shuffling styles already used in stochastic gradient methods can be adopted in coordinate descent without a rate penalty.
  • A sharper numerical search at dimensions $n\ge7$ (the paper only reports $n=3,\dots,6$) would be a low-cost test of Conjecture 4.1 before attempting a full proof, since the search maximizes the same spectral upper bound that the conjecture controls.
  • Because the sign-flipped matrices in $A_\sigma$ are covered, the benefit is not tied to positive correlation among Hessian entries but appears to come from the ordering geometry induced by permutations, suggesting similar gaps may hold for non-quadratic convex functions with locally quadratic Hessians.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper analyzes two randomized coordinate descent variants, RCD (i.i.d. uniform sampling) and RPCD (random permutations), on strongly convex quadratic objectives. Its central contribution is a comparison on the structured class A_sigma of permutation-invariant/sign-flipped quadratic forms: Theorem 3.1 gives a lower bound for RCD on all quadratics, Theorem 3.3 gives an upper bound for RPCD on A_sigma, and Theorem 3.4 gives a stronger RCD lower bound on A_sigma, so that, together, the per-epoch contraction of RPCD is provably below that of RCD for every instance in A_sigma. The proof reduces the RPCD second-moment operator to a 2x2 matrix using Lemma B.2, derives explicit coefficient formulas for the relevant polynomials, and handles small dimensions with a computer-assisted Sturm sequence verification in Appendix C. The paper also contains a conjecture extending the RPCD bound to all positive-definite quadratics, numerical experiments, and a non-asymptotic comparison in Appendix G.

Significance. If Theorem 3.3 is fully supported, this is a substantial advance: it supplies the first per-instance, per-epoch separation between RPCD and RCD for a nontrivial class of quadratics, with explicit constants and no fitting between the RCD lower bound and RPCD upper bound. The paper is careful to credit prior work, clearly labels the general-quadratic claim as a conjecture, and provides explicit derivations, reproducible experiment code, and a script for the computer-assisted checks. The main analytical reduction from the operator to a 2x2 matrix is transparent and appears sound. However, the validity of the central theorem currently depends on Appendix C, and the Sturm-sequence certification as written is not a valid proof for the finite cases it is asked to cover. Because those finite cases are exactly the cases not handled by the analytic parts of the proof, the central claim is not yet fully established.

major comments (2)
  1. [Appendix C / Proposition B.6] The computer-assisted verification in Appendix C is not a valid application of Proposition B.6 as written. The functions t1 and t2 are built from alpha, beta, gamma, and delta in (17), which contain denominators (1-s), (1-s^2), and (1+s), and the code never applies cancel, simplify, or together before forming the Sturm sequence. If these expressions remain rational functions, then the objects passed to sturm_sequence are not polynomials, and Proposition B.6, which defines the Sturm sequence for a polynomial, does not apply. The statement that "the coefficients are all rational numbers" does not address this point. In addition, in Case 1 the code calls count_real_roots(d, 0, 1, s) even though d(0)=0 for every n in the loop, whereas Proposition B.6 explicitly requires f(a) != 0 and f(b) != 0. Only the endpoint s=1 is checked for positivity. As written, the script does not certify the assertions listed at the beginning of Appendix C.
  2. [Theorem 3.3 / Appendix B.2] The finite Sturm checks in Appendix C are load-bearing for Theorem 3.3, not a peripheral convenience. The analytic part of the proof only covers n >= 7 on (0,0.6], n >= 11 on [0.6,0.8], and n >= 15 on [0.8,1), and it explicitly relies on the computer-verified inequalities for 2 <= m <= 6, 2 <= m <= 10, and 2 <= m <= 14 (or 9 for T2). If the Appendix C verification is invalid, then Theorem 3.3 is unproved for small and moderate dimensions, and with it the claimed RPCD-versus-RCD gap for those instances. The theorem may well be true, and the defect is in the certification rather than necessarily in the inequalities themselves, but the proof as submitted is incomplete. Please replace the script with one that cancels rational factors, verifies that each element of the Sturm sequence is a polynomial, factors out endpoint zeros or uses small epsilon intervals, and checks the endpoints that the chosen intervals actually require.
minor comments (3)
  1. [Section 3.3] The strict inequality between the Theorem 3.3 upper bound and the Theorem 3.4 lower bound is asserted without proof. It is worth adding the short argument: (1 - sigma/n)^(2n) <= (1 - sigma/n)^2 = 1 - 2 sigma/n + sigma^2/n^2 <= 1 - 2 sigma/n + sigma^2/n, and (1 - 1/n)^n < 1 - 1/n < 1 - 1/n + (1 - sigma)^2/n for sigma in (0,1).
  2. [Lemma B.9] There is a typo in the proof: the substitution y = 1 + x gives the equivalent inequality log y >= 1 - 1/y, not log x >= 1 + 1/x as written; the function g(x) = log x + 1/x - 1 used in the proof corresponds to the correct inequality.
  3. [Appendix C] The text says the computations are exact because all coefficients are rational, but the code uses floating-point-free symbolic arithmetic only if the inputs are actually polynomials after simplification. Please add explicit assertions or a short preprocessing step confirming that t1 and t2 are polynomials in sigma before the Sturm sequence is built.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the RCD lower bounds and RPCD upper bounds are derived independently from the iteration operators and compared only at the end.

full rationale

The paper's central comparison is between a lower bound on the per-epoch contraction of RCD and an upper bound on the per-epoch contraction of RPCD, both for the same class A_sigma. The RCD bound in Theorem 3.1 is obtained from the spectral analysis of M_RCD_A(I) = I - 2A/n + A^2/n and the matrix inequality X ⪯ n diag(X); the stronger RCD bound in Theorem 3.4 is obtained by restricting M_RCD_A to span{I, 11^T} and computing the 2x2 matrix M_A = 1/n [[n-1+(1-sigma)^2, (1-sigma)^2(n-2)], [sigma^2, sigma^2(n-2)]]. The RPCD bound in Theorem 3.3 is obtained independently by restricting M_RPCD_A to the same subspace, expressing its 2x2 representation through Lemma B.2, bounding rho(M_Ak) by ||M_Ak||_inf, and then comparing the resulting polynomials with the target max{(1-1/n)^n, (1-sigma/n)^{2n}} via coefficient estimates and Sturm-sequence checks. No parameter is fitted to make the two bounds close: sigma is the given minimum eigenvalue of the Hessian, and the RCD lower bound is never used as an input to the RPCD proof or vice versa; the inequalities are checked against the same closed-form expression that already appears in Theorem 3.1, which is the point being proved rather than an assumption. The cited external lemmas (Lee & Wright 2019 Lemma 3.1, Wright & Lee 2017 diagonal scaling, Jacobson's Sturm theorem, Horn & Johnson's Gelfand and Perron-Frobenius results) are stated with their own assumptions and are not the authors' own prior results; they do not presuppose the RPCD-vs-RCD gap. The only fragile part is the computer-assisted verification in Appendix C, where the SymPy Sturm routines may not be a formally sound certificate as written; this is a soundness concern about the proof of Theorem 3.3 for small n, not a circularity, since the polynomials being checked are derived from the update matrices and the target bound, not fitted to it. Overall, the derivation chain is self-contained and non-circular.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted: sigma is the minimum eigenvalue of the scaled Hessian and is part of the problem instance. The class A_sigma and sign-flip vectors parameterize problem instances, not fitted constants. No new particles, forces, or speculative mathematical entities are introduced.

assumptions (5)
  • domain assumption Unit diagonal assumption is without loss of generality via diagonal scaling.
    Assumption 2.2 and the following paragraph invoke Wright and Lee (2017) Appendix A; every coordinate descent iterate on the scaled quadratic corresponds to the original iterate, so all theorems reduce to D = I.
  • standard math Nesterov's lemma X is positive semidefinite implies X is dominated by n times its diagonal.
    Lemma B.1 is used in the proof of Theorem 3.1 to lower bound the RCD operator by (I - A/n)^T X (I - A/n).
  • standard math Lee and Wright's expectation formula for P Q P^T over random permutations.
    Lemma B.2 reduces the RPCD operator on permutation-invariant matrices to a 2 by 2 matrix M_A in span{I, 11^T}.
  • standard math Sturm's theorem over real closed fields with exact rational arithmetic.
    Proposition B.6 and Appendix C verify the finite-range polynomial inequalities needed for Theorem 3.3; the supplied SymPy code is the only artifact for these checks.
  • domain assumption Exact coordinate minimization for quadratic objectives is equivalent to the explicit gradient form used in the proofs.
    The remark after Algorithm 1 states that the arg-min update equals x_{t+1} = x_t - (1/a_{i_t i_t}) E_{i_t} A x_t, which all theorem proofs rely on.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent." pith.science (2026). https://pith.science/paper/NQ46CIRB

@misc{pith2026250523152,
  author       = {Pith},
  title        = {Pith review of: Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NQ46CIRB}},
  note         = {Machine review of arXiv:2505.23152}
}
read the original abstract

We analyze the convergence rates of two popular variants of coordinate descent (CD): random CD (RCD), in which the coordinates are sampled uniformly at random, and random-permutation CD (RPCD), in which random permutations are used to select the update indices. Despite abundant empirical evidence that RPCD outperforms RCD in various tasks, the theoretical gap between the two algorithms' performance has remained elusive. Even for the benign case of positive-definite quadratic functions with permutation-invariant Hessians, previous efforts have failed to demonstrate a provable performance gap between RCD and RPCD. To this end, we present novel results showing that, for a class of quadratics with permutation-invariant structures, the contraction rate upper bound for RPCD is always strictly smaller than the contraction rate lower bound for RCD for every individual problem instance. Furthermore, we conjecture that this function class contains the worst-case examples of RPCD among all positive-definite quadratics. Combined with our RCD lower bound, this conjecture extends our results to the general class of positive-definite quadratic functions.

Figures

Figures reproduced from arXiv: 2505.23152 by the authors.

Figure 1
Figure 1. Performance comparison of RCD and RPCD. We use the objective function f(x) = 1 2 x ⊤Ax with A = σI + (1−σ)11⊤. For this plot we use σ = 0.7 and dimension n = 25. Lipschitz constant. (The case α = 0 corresponds to uni￾form sampling). Richtarik & Tak ´ ac´ (2011) further improve the constant factors of the convergence rate and extend to composite minimization problems. After Beck & Tetru￾ashvili (2013) established glo… view at source ↗
Figure 2
Figure 2. Plots of ρ(MRPCD An [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Numerical experiments comparing RCD and RPCD. We plot the mean values and min-max range over multiple trials of RCD/RPCD. For (i)-(iii), we use n = 25, σ ∈ {0.3, 0.7}. The experiments are conducted on (i) a quadratic function with A ∈ Aσ, (ii) a random quadratic with λmin(A) = σ, (iii) a random quadratic + (scaled and transformed) LSE function, and (iv) an ℓ2-regularized sparse logistic regression objective with n =… view at source ↗
Figures from the paper (12 more)
Figure 4
Figure 4. Figure 4: Plot of ∥A− 1 2MA(A)A− 1 2 ∥ (A = σI + (1−σ)11⊤) and the RPCD upper bound from Theorem 3.3 for n = 100. We obtain results demonstrating that RPCD outperforms RCD for any problem instance in A ∈ Aσ (Theorems 3.1 and 3.3), show a stronger RCD lower bound that induces a c…
Figure 5
Figure 5. Figure 5: RCD vs RPCD, permutation-invariant quadratic functions. A = σI + (1 − σ)11⊤, n = 25, σ ∈ {0.1, . . . , 0.9}. The y-axis is in log scale. 56 [PITH_FULL_IMAGE:figures/full_fig_p056_5.png]
Figure 6
Figure 6. Figure 6: RCD vs RPCD, permutation-invariant quadratic functions. A = σI + (1 − σ)11⊤, n = 50, σ ∈ {0.1, . . . , 0.9}. The y-axis is in log scale. 57 [PITH_FULL_IMAGE:figures/full_fig_p057_6.png]
Figure 7
Figure 7. Figure 7: RCD vs RPCD, quadratic functions with unit-diagonal Hessians. A is unit-diagonal and λmin(A) = σ, n = 25, σ ∈ {0.1, . . . , 0.9}. The y-axis is in log scale. 58 [PITH_FULL_IMAGE:figures/full_fig_p058_7.png]
Figure 8
Figure 8. Figure 8: RCD vs RPCD, quadratic functions with unit-diagonal Hessians. A is unit-diagonal and λmin(A) = σ, n = 50, σ ∈ {0.1, . . . , 0.9}. The y-axis is in log scale. 59 [PITH_FULL_IMAGE:figures/full_fig_p059_8.png]
Figure 9
Figure 9. Figure 9: RCD vs RPCD, quadratic functions with unit-diagonal Hessians and log-sum-exp term. A is unit-diagonal and λmin(A) = σ, n = 25, σ ∈ {0.1, . . . , 0.9}, α = 0.5. The y-axis is in log scale. 60 [PITH_FULL_IMAGE:figures/full_fig_p060_9.png]
Figure 10
Figure 10. Figure 10: RCD vs RPCD, quadratic functions with unit-diagonal Hessians and log-sum-exp term. A is unit-diagonal and λmin(A) = σ, n = 50, σ ∈ {0.1, . . . , 0.9}, α = 0.5. The y-axis is in log scale. 61 [PITH_FULL_IMAGE:figures/full_fig_p061_10.png]
Figure 11
Figure 11. Figure 11: RCD vs RPCD, quadratic functions with unit-diagonal Hessians and log-sum-exp term. A is unit-diagonal and λmin(A) = σ, n = 25, σ ∈ {0.1, . . . , 0.9}, α = 2.0. The y-axis is in log scale. 62 [PITH_FULL_IMAGE:figures/full_fig_p062_11.png]
Figure 12
Figure 12. Figure 12: RCD vs RPCD, quadratic functions with unit-diagonal Hessians and log-sum-exp term. A is unit-diagonal and λmin(A) = σ, n = 50, σ ∈ {0.1, . . . , 0.9}, α = 2.0. The y-axis is in log scale. 63 [PITH_FULL_IMAGE:figures/full_fig_p063_12.png]
Figure 13
Figure 13. Figure 13: RCD vs RPCD, quadratic functions with unit-diagonal Hessians and log-sum-exp term. A is unit-diagonal and λmin(A) = σ, n = 25, σ ∈ {0.1, . . . , 0.9}, α = 20.0. The y-axis is in log scale. 64 [PITH_FULL_IMAGE:figures/full_fig_p064_13.png]
Figure 14
Figure 14. Figure 14: RCD vs RPCD, quadratic functions with unit-diagonal Hessians and log-sum-exp term. A is unit-diagonal and λmin(A) = σ, n = 50, σ ∈ {0.1, . . . , 0.9}, α = 20.0. The y-axis is in log scale. 65 [PITH_FULL_IMAGE:figures/full_fig_p065_14.png]
Figure 15
Figure 15. Figure 15: RCD vs RPCD, Ridge-regularized logistic regression, n = m = 100, λ ∈ {0.0001, 0.001, 0.01, 0.1, 1.0}. The y-axis is in log scale. 66 [PITH_FULL_IMAGE:figures/full_fig_p066_15.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

33 extracted references · 28 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    SGD with shuffling: Optimal rates without component convexity and large epoch requirements

    Ahn, K., Yun, C., and Sra, S. SGD with shuffling: Optimal rates without component convexity and large epoch requirements. In Advances in Neural Information Processing Systems (NeurIPS), 2020

    work page 2020

  3. [3]

    and Tetruashvili, L

    Beck, A. and Tetruashvili, L. On the convergence of block coordinate descent type methods. SIAM Journal on Optimization, 23 0 (4): 0 2037--2060, 2013. doi:10.1137/120887679. URL https://doi.org/10.1137/120887679

    doi:10.1137/120887679 2013

  4. [4]

    Positive Definite Matrices

    Bhatia, R. Positive Definite Matrices. Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, USA, 2007. URL http://press.princeton.edu/titles/8445.html

    work page 2007

  5. [5]

    Curiously fast convergence of some stochastic gradient descent algorithms

    Bottou, L. Curiously fast convergence of some stochastic gradient descent algorithms. In Proceedings of the symposium on learning and data science, Paris, 2009

    work page 2009

  6. [6]

    Tighter lower bounds for shuffling SGD : Random permutations and beyond

    Cha, J., Lee, J., and Yun, C. Tighter lower bounds for shuffling SGD : Random permutations and beyond. In International Conference on Machine Learning (ICML), 2023

    work page 2023

  7. [7]

    and Yun, C

    Cho, H. and Yun, C. SGDA with shuffling: faster convergence for nonconvex-p minimax optimization. In International Conference on Learning Representations (ICLR), 2023. URL https://openreview.net/forum?id=6xXtM8bFFJ

    work page 2023

  8. [8]

    Sampling without replacement leads to faster rates in finite-sum minimax optimization

    Das, A., Sch\" o lkopf, B., and Muehlebach, M. Sampling without replacement leads to faster rates in finite-sum minimax optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2022

    work page 2022

Show all 33 references
  1. [9]

    De Sa, C. M. Random reshuffling is not always better. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp.\ 5957--5967. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/p...

    2020

  2. [10]

    A., and Vanli, N

    G \"u rb \"u zbalaban, M., Ozdaglar, A., Parrilo, P. A., and Vanli, N. When cyclic coordinate descent outperforms randomized coordinate descent. In Advances in Neural Information Processing Systems (NeurIPS), 2017

    2017

  3. [11]

    E., Vanli, N

    G \"u rb \"u zbalaban, M., Ozdaglar, A. E., Vanli, N. D., and Wright, S. J. Randomness and permutations in coordinate descent methods. Mathematical Programming, 181: 0 349 -- 376, 2018. URL https://api.semanticscholar.org/CorpusID:119151332

    2018

  4. [12]

    Horn, R. A. and Johnson, C. R. Matrix Analysis. Cambridge University Press, 2 edition, 2012

    2012

  5. [13]

    Basic Algebra I

    Jacobson, N. Basic Algebra I. W. H. Freeman and Company, New York, 2 edition, 1985

    1985

  6. [14]

    and Tao, T

    Knutson, A. and Tao, T. Honeycombs and sums of Hermitian matrices. Notices Amer. Math. Soc., 48, 09 2000

    2000

  7. [15]

    and Lim, L.-H

    Lai, Z. and Lim, L.-H. Recht-re noncommutative arithmetic-geometric mean conjecture is false. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp.\ 5608--5617. PMLR...

    2020

  8. [16]

    and Wright, S

    Lee, C.-P. and Wright, S. J. Random permutations fix a worst case for cyclic coordinate descent. IMA Journal of Numerical Analysis, 39 0 (3): 0 1246--1275, 2019

    2019

  9. [17]

    Lee, Y. T. and Sidford, A. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013 , pp.\ 147--156, 2013. URL https://doi.org/10.1109/FOCS.2013.24

    2013 doi

  10. [18]

    and Zhou, Z

    Liu, Z. and Zhou, Z. On the last-iterate convergence of shuffling gradient methods. In International Conference on Machine Learning (ICML), 2024

    2024

  11. [19]

    Random reshuffling: Simple analysis with vast improvements

    Mishchenko, K., Khaled, A., and Richtarik, P. Random reshuffling: Simple analysis with vast improvements. In Advances in Neural Information Processing Systems (NeurIPS), 2020

    2020

  12. [20]

    Proximal and federated random reshuffling

    Mishchenko, K., Khaled, A., and Richtarik, P. Proximal and federated random reshuffling. In International Conference on Machine Learning (ICML), 2022. URL https://proceedings.mlr.press/v162/mishchenko22a.html

    2022

  13. [21]

    Efficiency of coordinate descent methods on huge-scale optimization problems

    Nesterov, Y. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22 0 (2): 0 341--362, 2012. doi:10.1137/100802001. URL https://doi.org/10.1137/100802001

    2012 doi

  14. [22]

    and Stich, S

    Nesterov, Y. and Stich, S. U. Efficiency of the accelerated coordinate descent method on structured optimization problems. SIAM Journal on Optimization, 27 0 (1): 0 110--123, 2017. doi:10.1137/16M1060182. URL https://doi.org/10.1137/16M1060182

    2017 doi

  15. [23]

    Coordinate descent converges faster with the gauss-southwell rule than random selection

    Nutini, J., Schmidt, M., Laradji, I., Friedlander, M., and Koepke, H. Coordinate descent converges faster with the gauss-southwell rule than random selection. In International Conference on Machine Learning, pp.\ 1632--1641. PMLR, 2015

    2015

  16. [24]

    and Re, C

    Recht, B. and Re, C. Toward a noncommutative arithmetic-geometric mean inequality: Conjectures, case-studies, and consequences. In Conference on Learning Theory (COLT), 2012

    2012

  17. [25]

    and Tak \'a c, M

    Richt \'a rik, P. and Tak \'a c, M. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Mathematical Programming, 144: 0 1 -- 38, 2011. URL https://api.semanticscholar.org/CorpusID:16816638

    2011

  18. [26]

    and Dye, H

    Russo, B. and Dye, H. A. A note on unitary operators in C^ -algebras . Duke Mathematical Journal, 33 0 (2): 0 413 -- 416, 1966. doi:10.1215/S0012-7094-66-03346-1. URL https://doi.org/10.1215/S0012-7094-66-03346-1

    1966 doi

  19. [27]

    and Ye, Y

    Sun, R. and Ye, Y. Worst-case complexity of cyclic coordinate descent: O(n^2) gap with randomized version. Mathematical Programming, 185: 0 487 -- 520, 2016. URL https://api.semanticscholar.org/CorpusID:232935420

    2016

  20. [28]

    On the efficiency of random permutation for ADMM and coordinate descent

    Sun, R., Luo, Z.-Q., and Ye, Y. On the efficiency of random permutation for ADMM and coordinate descent. Mathematics of Operations Research, 45 0 (1): 0 233--271, 2020. doi:10.1287/moor.2019.0990. URL https://doi.org/10.1287/moor.2019.0990

    2020

  21. [29]

    Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung)

    Weyl, H. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung). Mathematische Annalen, 71 0 (4): 0 441--479, 1912. URL https://doi.org/10.1007/BF01456804

    1912 doi

  22. [30]

    Wright, S. J. Coordinate descent algorithms. Mathematical Programming, 151: 0 3 -- 34, 2015. URL https://api.semanticscholar.org/CorpusID:15284973

    2015

  23. [31]

    Wright, S. J. and Lee, C.-P. Analyzing random permutations for cyclic coordinate descent. Math. Comput., 89: 0 2217--2248, 2017. URL https://api.semanticscholar.org/CorpusID:39214865

    2017

  24. [32]

    Open problem: Can single-shuffle sgd be better than reshuffling sgd and gd? In Belkin, M

    Yun, C., Sra, S., and Jadbabaie, A. Open problem: Can single-shuffle sgd be better than reshuffling sgd and gd? In Belkin, M. and Kpotufe, S. (eds.), Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp.\ 4653--...

    2021

  25. [33]

    Minibatch vs local sgd with shuffling: Tight convergence bounds and beyond

    Yun, C., Rajput, S., and Sra, S. Minibatch vs local sgd with shuffling: Tight convergence bounds and beyond. In 10th International Conference on Learning Representations, ICLR 2022. International Conference on Learning Representations (ICLR), 2022

    2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.