A Resolution of the SS--RS--GD Inequalities

Binghui Peng

A 2021 conjecture about the order of shuffled SGD methods is split: the single-shuffle versus reshuffling inequality fails, while the reshuffling versus gradient-descent inequality holds.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-02 10:58 UTC pith:WV23IWON

load-bearing objection A genuine resolution of the SS–RS–GD open problem: a clean near-identity counterexample for SS–RS and a correct dimension-free RS–GD theorem, both backed by explicit verifiable proofs.

arxiv 2607.22620 v1 pith:WV23IWON submitted 2026-06-16 math.OC cs.LGstat.ML

A Resolution of the SS--RS--GD Inequalities

Binghui Peng This is my paper

classification math.OC cs.LGstat.ML MSC 90C2515A45

keywords single-shuffle SGDrandom-reshuffle SGDfinite-sum optimizationmatrix AM-GM inequalityoperator normconditioned matricesshufflingnoncommutative matrix inequality

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Three common ways to minimize a finite sum of quadratics—single-shuffle SGD (one random order reused), random-reshuffle SGD (a fresh random order each epoch), and gradient descent (all terms at once)—have expected iterative operators W_SS, W_RS, W_GD. A 2021 conjecture said these should always be ordered by operator norm, W_SS <= W_RS <= W_GD, for well-conditioned matrices. This paper proves the conjecture is false on the first comparison but true on the second: it constructs matrices within any constant of the identity for which ||W_SS|| > ||W_RS||, and proves ||W_RS|| <= ||W_GD|| whenever each matrix lies between (1 - 1/(4n^2+1))I and I. The positive half reduces to a single-epoch bound on the average of all permutation-ordered products, established by expanding around the identity matrix.

Core claim

The paper's central claim is a split resolution of the SS-RS-GD order conjecture. On the negative side, for n=3, K=2, and d=4, it exhibits A_i = B_i ⊗ B_i built from rank-one projectors B_i with eigenvalues {q, 1}; as q approaches 1 from below, these satisfy (1-η)I ⪯ A_i ⪯ I for any proposed η, yet the explicit eigenvalue formulas give ||W_SS|| >= λ_SS(q) > λ_RS(q) = ||W_RS||. On the positive side, for all n, K, d and all symmetric A_i with (1 - 1/(4n^2+1))I ⪯ A_i ⪯ I, the paper proves 0 ⪯ R ⪯ ρ^n I, where R is the uniform average of ordered products A_{σ(1)}⋯A_{σ(n)} and ρ = ||(1/n)Σ A_i||. Powering this gives ||W_RS|| = ||R^K|| <= ρ^{nK} = ||W_GD||, so the second half of the conjecture hol

What carries the argument

The three expected-iteration operators carry the argument: W_SS averages the K-th power of each permutation product, W_RS takes the K-th power of the average product, and W_GD is the full-batch average raised to nK. The affirmative proof rests on a near-identity shuffled AM-GM lemma: if C_i = I + X_i are positive semidefinite, their average C̄ satisfies C̄ ⪯ I, and δ = max ||X_i|| <= 1/(4n^2), then the averaged ordered product R̄ satisfies 0 ⪯ R̄ ⪯ I. The lemma is proven by expanding the product around I, using the average condition to identify a positive first-order term, and bounding all higher-order words by a geometric series in δ.

Load-bearing premise

The positive half rests on the tail estimate in the near-identity lemma: after expanding R̄ = I + E_1 + ⋯ + E_n, the proof bounds the order-k≥3 contribution by a geometric series and asserts this tail stays below 1/4 for all n with δ <= 1/(4n^2); the displayed manipulation is abbreviated and the closest case is n=2, where the slack is small. The argument also needs R̄ to have no negative eigenvalues before the norm-power exchange ||R||^K can be used, so if the tail bound fail

What would settle it

Numerically evaluate the tail in the near-identity lemma at the boundary: take n=2, δ=1/16, and maximize over unit vectors v the quantity Σ_{k≥3} v^T E_k v over all symmetric X_i with ||X_i|| <= 1/16 and C̄ ⪯ I; if the maximum reaches 1/4, the lemma's proof collapses. Independently, for the negative half, run the paper's symbolic script at q=0.99 and check whether λ_SS(q) > λ_RS(q) while A_i remain within (1-η)I of I for arbitrarily small η.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

Random reshuffling is never worse than full-batch gradient descent over any number of epochs K, as long as the component matrices are within 1/(4n^2+1) of the identity; the guarantee is independent of K and d.
Single-shuffle can strictly beat random reshuffling in operator norm even when the matrices are arbitrarily close to the identity, so the failure of the first inequality is not merely a conditioning artifact.
The safe conditioning radius shrinks like Θ(1/n^2) with the number of components, quantifying how close to identity the matrices must be for the reshuffle-versus-GD order to be guaranteed.
The counterexample lives at n=3, K=2, d=4, with all claimed polynomial identities verified symbolically, so the negative result is exact and not asymptotic at these parameters.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The failure of SS-RS near the identity suggests that the comparison between single-shuffle and reshuffling is genuinely order-dependent: no amount of conditioning forces the conjectured direction. A natural extension would be to test whether the tensor construction yields failures for larger n and K.
The near-identity lemma plausibly has a sharp constant far above 1/(4n^2); the proof itself notes the tail is below 1/24, much smaller than the 1/4 it bounds against, so computing the largest δ for which R̄ ⪯ I holds would be a concrete follow-up.
Because the RS-GD result is K-free, it indicates that the reshuffling-versus-full-batch comparison is settled epoch by epoch: later epochs inherit the same inequality by powering the single-epoch operator bound.
The same expansion technique—controlling a first-order term by the average condition and bounding higher-order words by word-count arguments—could apply to other symmetrized noncommutative product inequalities, such as weighted or non-uniform permutation averages.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

A genuine resolution of the SS–RS–GD open problem: a clean near-identity counterexample for SS–RS and a correct dimension-free RS–GD theorem, both backed by explicit verifiable proofs.

read the letter

Read it. The paper actually resolves the Yun–Sra–Jadbabaie conjecture, one half by a counterexample, the other by a positive theorem. The counterexample is strong: three 4x4 matrices built from a tensor square of rank-one projectors, with condition number arbitrarily close to one, for which ||W_SS|| > ||W_RS||. The algebra is exact, and the sympy script in Appendix A verifies the characteristic polynomials and gap identities. That is reproducible evidence, not hand-waving.

The positive side is the near-identity shuffled AM-GM lemma (Lemma 7). The reduction to one epoch is sound, and the expansion into E_k terms is correct. The most delicate step is the tail bound in (14); the paper says the series is dominated by a geometric tail and is < 1/4, but doesn't show the details. I checked it with the crude bounds: for delta <= 1/(4n^2), the k-th term is <= n^{3-k}/(k! 4^{k-2}), the k=3 term is 1/24, and the rest sum to well under 1/4 — actually under 1/23 for all n >= 2. So the step is safe; it just needs a couple of lines to make a referee happy.

A couple of minor things: the abstract says 'RS-GD holds inequality holds' — typo. In Section 4.1 the proof says raising (9) to the K-th power is legitimate because R >= 0; that's unnecessary since ||R^K|| = ||R||^K for any symmetric R, and R >= 0 is only established later. No mathematical harm, just a slightly odd justification. The AI provenance is disclosed transparently, and the script makes the claim checkable.

Overall, the paper does what it claims. It settles a named open problem, the counterexample is strong, and the positive result is a genuinely useful conditioning theorem. The proof is elementary but not trivial, and the lemmas are reusable. I'd send this to a serious referee — someone who can verify the algebra and fill in the tail-bound details. It deserves to be in the literature.

Referee Report

0 major / 3 minor

Summary. The paper addresses the Yun–Sra–Jadbabaie COLT 2021 open problem concerning the SS–RS–GD operator norm inequalities for well-conditioned symmetric matrices. It claims two results: (i) the SS–RS inequality fails already at n=3, K=2, d=4, with explicit 4×4 positive definite matrices whose condition number is arbitrarily close to 1 yet ∥W_SS∥>∥W_RS∥; and (ii) the RS–GD inequality holds for all n,K,d whenever the symmetric matrices satisfy (1−1/(4n^2+1))I ⪯ A_i ⪯ I, with η^{RS-GD}_{n,K}=1/(4n^2+1). The counterexample is verified by an exact sympy script in Appendix A, and the positive result is proved through a near-identity shuffled AM–GM lemma (Lemma 7) with an elementary expansion and tail bound. The paper thus resolves the conjecture in a split manner: one half is false and the other half is true.

Significance. If correct, this settles the open problem definitively. The refutation of SS–RS is particularly strong: it shows that no positive well-conditioning radius can rescue the first inequality at (n,K)=(3,2), even when the matrices are arbitrarily close to the identity. The proof of RS–GD is self-contained, uses only elementary tools, and provides a dimension-free, epoch-independent constant Θ(1/n^2). A notable strength is the machine-checked symbolic verification in Appendix A, which turns the eigenvalue and gap identities of Section 3 into exact proofs. I also checked the tail estimate in Lemma 7 flagged by the stress-test note; the estimate is correct, with ample slack, so that concern does not land. The AI-provenance disclosure is unusual but does not affect the mathematical content.

minor comments (3)

[§4.2, Eq. (14)] The tail bound for S := Σ_{k=3}^n (n−1)_{k−1} δ^{k−2}/k! is stated too tersely. The line 'the series is dominated by a geometric tail, giving < 1/4' is correct but should be expanded, since this bound is load-bearing for the constant 1/(4n^2+1). One explicit route: (n−1)_{k−1} ≤ n^{k−1} and δ ≤ 1/(4n^2) give term ≤ n^{3−k}/(k!4^{k−2}); for n≥2 this is at most 2^{3−k}/(k!4^{k−2}), and the sum over k≥3 is ≤ 1/24 + 1/768 + ⋯ < 1/4 (indeed < 0.05). The current phrase 'supremum over n is 1/24+o(1)' is informal and should be replaced by this explicit chain.
[§4.1] The parenthetical '(legitimate because R⪰0, established below)' is misleading. The equality ∥W_RS∥=∥R∥^K holds for every symmetric R, since eigenvalues are raised to the K-th power, and (9) is an inequality between nonnegative quantities; R⪰0 is not needed at that step. Rephrase to avoid the appearance of a circular argument.
[Abstract and §1] There is a typo in the abstract: 'RS-GD holds inequality holds' should read 'RS-GD inequality holds.' Also, 'found via GPT-5.5 Pro extended prompted by the author' is grammatically awkward; consider 'with prompting by the author.' These are presentation issues only.

Circularity Check

0 steps flagged

No significant circularity: all derivations are self-contained.

full rationale

The paper contains no load-bearing circular step. The SS-RS refutation (Theorem 2) is a direct explicit construction: matrices A_i are defined from q and fixed projectors, and the comparison ||W_SS|| > ||W_RS|| is reduced to exact polynomial identities for the eigenvalues (Lemmas 5–6), verified by the symbolic script in Appendix A. No fitted parameter is later relabeled as a prediction, and no external result is needed to force the inequality. The RS-GD proof (Theorem 3) is independent: it normalizes by rho=||G||, expands the shuffled product, and proves the near-identity AM-GM bound in Lemma 7 entirely from the stated conditioning hypothesis, using direct expansions, Cauchy-Schwarz, and elementary tail estimates. The constant eta=1/(4n^2+1) is chosen to make delta <= 1/(4n^2) hold, not extracted from the target inequality. The cited works are used only for context and known counterexamples in the general (unconditioned) case; there are no self-citations and no uniqueness or ansatz imported from other papers by the same author. The proof is therefore self-contained against external benchmarks, and no circularity is present.

Axiom & Free-Parameter Ledger

1 free parameters · 4 axioms · 0 invented entities

The paper introduces no new entities, no new constants fitted to data, and no new axioms beyond standard linear algebra. The constant 1/(4n^2+1) is chosen for the proof to work, not fitted. The free parameter q in the counterexample is part of the construction, not a fit. Overall honest to the prior literature.

free parameters (1)

q (family parameter of the counterexample) = any q in (q*, 1); q* approx 0.212036
The counterexample is a one-parameter family; for a given target eta, q is chosen near 1 with 1 - q^2 < eta. This is a construction parameter, not fitted to data.

axioms (4)

standard math Spectral norm of a symmetric matrix equals its largest eigenvalue in absolute value.
Invoked in Sections 3.2 and 4.3; standard linear algebra, no issue.
standard math For symmetric PSD A, ||A^k|| = ||A||^k.
Used in the RS-GD reduction (Section 4.1). Requires R and G to be PSD; for R this is established by Lemma 7, and for G since the A_i are PSD, so standard.
domain assumption The sum-of-squares certificates and the exact factorizations of characteristic polynomials in Appendix A are correct.
The paper provides a sympy script that verifies them; the reasoning is consistent and the script is included, so this is machine-checked in practice.
domain assumption The tail estimate in Lemma 7 (the series sum is < 1/4) is correct as stated.
This is the only step where the paper uses a coarse inequality without displaying the full exercise. I see no obstruction, and the claimed slack appears plausible, but I flag it as the main spot to check on a first reading.

pith-pipeline@v1.3.0-alltime-deepseek · 7995 in / 7107 out tokens · 53857 ms · 2026-08-02T10:58:52.897975+00:00 · methodology

0 comments

read the original abstract

Yun, Sra, and Jadbabaie (COLT 2021, open question) conjectured the SS--RS--GD inequalities: for well-conditioned symmetric matrices $A_1,\dots,A_n$, the operators $W_{ss}$, $W_{rs}$, and $W_{gd}$ that encode the expected iterate of single-shuffle SGD, random-reshuffle SGD, and gradient descent on a quadratic finite sum should satisfy \[ \|W_{ss}\|\le \| W_{rs}\|\le \|W_{gd}\|. \] The conjecture is resolved, $\bullet$ SS-RS inequality fails. Already for $n=3$, $K=2$, and $d=4$, we exhibit explicit PSD matrices whose condition number is arbitrarily close to $1$, yet $\|W_{ss}\|>\|W_{rs}\|$. $\bullet$ RS-GD inequality holds. For every symmetric $A_i$ with $\bigl(1-\frac1{4n^2+1}\bigr)I\preceq A_i\preceq I$, one has $\|W_{rs}\|\le\|W_{gd}\|$. The proof was found via GPT-5.5 Pro extended prompted by the author.

discussion (0)

Reference graph

Works this paper leans on

11 extracted references · 1 linked inside Pith

[1]

C. Yun, S. Sra, and A. Jadbabaie. Open problem: Can single-shuffle SGD be better than reshuffling SGD and GD? InConference on Learning Theory (COLT), vol. 134, pp. 4653–4658, 2021

2021
[2]

Recht and C

B. Recht and C. R´ e. Toward a noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences. InConference on Learning Theory (COLT), pp. 11.1–11.24, 2012

2012
[3]

Lai and L.-H

Z. Lai and L.-H. Lim. Recht–R´ e noncommutative arithmetic-geometric mean conjecture is false. InInternational Conference on Machine Learning (ICML), 2020

2020
[4]

C. De Sa. Random reshuffling is not always better. InAdvances in Neural Information Processing Systems (NeurIPS), vol. 33, 2020

2020
[5]

T. Zhang. A note on the matrix arithmetic-geometric mean inequality.Electronic Journal of Linear Algebra, 34:283–287, 2018

2018
[6]

Haochen and S

J. Haochen and S. Sra. Random shuffling beats SGD after finite epochs. InInternational Conference on Machine Learning (ICML), pp. 2624–2633, 2019

2019
[7]

Nagaraj, P

D. Nagaraj, P. Jain, and P. Netrapalli. SGD without replacement: Sharper rates for gen- eral smooth convex functions. InInternational Conference on Machine Learning (ICML), pp. 4703–4711, 2019

2019
[8]

Rajput, A

S. Rajput, A. Gupta, and D. Papailiopoulos. Closing the convergence gap of SGD without replacement. InInternational Conference on Machine Learning (ICML), 2020

2020
[9]

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

2020
[10]

Mishchenko, A

K. Mishchenko, A. Khaled, and P. Richt´ arik. Random reshuffling: Simple analysis with vast improvements.arXiv preprint arXiv:2006.05988, 2020

Pith/arXiv arXiv 2006
[11]

all identities verified

I. Safran and O. Shamir. How good is SGD with random shuffling? InConference on Learning Theory (COLT), pp. 3250–3284, 2020. 8 A Reproducible symbolic verification All claims of Section 3 are exact polynomial identities inq. The following self-containedsympy script forms the matrices of the construction (3)–(4) and verifies them; it runs to completion, pr...

2020

[1] [1]

C. Yun, S. Sra, and A. Jadbabaie. Open problem: Can single-shuffle SGD be better than reshuffling SGD and GD? InConference on Learning Theory (COLT), vol. 134, pp. 4653–4658, 2021

2021

[2] [2]

Recht and C

B. Recht and C. R´ e. Toward a noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences. InConference on Learning Theory (COLT), pp. 11.1–11.24, 2012

2012

[3] [3]

Lai and L.-H

Z. Lai and L.-H. Lim. Recht–R´ e noncommutative arithmetic-geometric mean conjecture is false. InInternational Conference on Machine Learning (ICML), 2020

2020

[4] [4]

C. De Sa. Random reshuffling is not always better. InAdvances in Neural Information Processing Systems (NeurIPS), vol. 33, 2020

2020

[5] [5]

T. Zhang. A note on the matrix arithmetic-geometric mean inequality.Electronic Journal of Linear Algebra, 34:283–287, 2018

2018

[6] [6]

Haochen and S

J. Haochen and S. Sra. Random shuffling beats SGD after finite epochs. InInternational Conference on Machine Learning (ICML), pp. 2624–2633, 2019

2019

[7] [7]

Nagaraj, P

D. Nagaraj, P. Jain, and P. Netrapalli. SGD without replacement: Sharper rates for gen- eral smooth convex functions. InInternational Conference on Machine Learning (ICML), pp. 4703–4711, 2019

2019

[8] [8]

Rajput, A

S. Rajput, A. Gupta, and D. Papailiopoulos. Closing the convergence gap of SGD without replacement. InInternational Conference on Machine Learning (ICML), 2020

2020

[9] [9]

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

2020

[10] [10]

Mishchenko, A

K. Mishchenko, A. Khaled, and P. Richt´ arik. Random reshuffling: Simple analysis with vast improvements.arXiv preprint arXiv:2006.05988, 2020

Pith/arXiv arXiv 2006

[11] [11]

all identities verified

I. Safran and O. Shamir. How good is SGD with random shuffling? InConference on Learning Theory (COLT), pp. 3250–3284, 2020. 8 A Reproducible symbolic verification All claims of Section 3 are exact polynomial identities inq. The following self-containedsympy script forms the matrices of the construction (3)–(4) and verifies them; it runs to completion, pr...

2020