The constant η_(2,K)=1 is impossible: an exact counterexample to the single-shuffle inequality at n=2, K=2, d=4
Abstract
Yun, Sra and Jadbabaie compare the expected iterate of stochastic gradient descent on a quadratic finite sum under single shuffling, random reshuffling and plain gradient descent, and conjecture that for every number of components n, every epoch count K and every dimension d there is a step-size constant η_(n,K) ∈ (0,1] for which (1-η_(n,K))Ipreceq Aᵢpreceq I forces |Wₛₛ| ≤ |Wᵣₛ| ≤ |W_(gd)|. About the first component of their conjecture at n=2 they write: emph"Nevertheless, for n=2, we believe that the conjecture itself is likely true for any d and K, with step-size constants η_(2,K)=1." We refute that belief, with two explicit witnesses. For the symmetric positive definite integer matrices A=diag(1,10²,10⁴,10⁶) and an explicit B with entries at most 10⁷, at K=2 and d=4, we have |Wₛₛ|>ρ² ≥ |Wᵣₛ| with ρ=106130000; the true ratio is |Wₛₛ|/|Wᵣₛ|=1.035608302215…. Rescaled into the conjecture's own normalisation the pair satisfies (1)/(84375000)Ipreceq A',B'preceq I and still violates the inequality. A second, far better conditioned pair — A=diag(1,7²,62²,624²) and an explicit B with entries of at most ten digits — does the same at (1)/(389765)Ipreceq A',B'preceq I, a factor 216.5 sharper, with true ratio 1.048908816189…; and we prove that no renormalisation of that pair can reach past tfrac1389376, so its bookkeeping is within 0.1 witness rather than of the accounting. Hence no admissible constant reaches 1-2.5656… × 10⁻⁶, while η=1/4 is admissible, by the authors' own Theorem 3 together with the n=2 case of the Recht–Ré inequality. The conjecture itself survives at n=2; what dies is the value of the constant, and a stated belief becomes a quantitative question whose answer, the supremum η^(*)_(2,2) of the admissible constants, is bracketed by 1/4 ≤ η^(*)_(2,2) ≤ 1-2.5656… × 10⁻⁶ — about five and a half orders of magnitude in 1-η, and no better. Each certificate is four denominator-cleared LDLᵗop identities and two Rayleigh quotients, all in exact integer arithmetic, so the refutations are checked by kernel reduction alone, with no compiled evaluation and no floating point anywhere in the proofs. We also record, with credit, the two halves of the n=2 picture that do hold — the reshuffling-versus-gradient-descent inequality for all positive semidefinite A,B at η=1, and the single-shuffle inequality at d=2 for every K — and we explain why the counterexample is invisible to the searches that look for it: the violating eigenvalue is the negative one, and the largest eigenvalue can never violate the inequality. Every statement below is machine-checked in Lean 4.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 2 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
339c64cb43154c2463e8c7e8b4612e075bf1acf97078382e12edb220eda78485
Claim ledger
Stated results
SSRS1candidate2026-09-03
the SS-RS inequality of Yun-Sra-Jadbabaie's Conjecture 1 FAILS at n = 2, eta = 1: for the symmetric positive definite integer matrices A = diag(1, 100, 10⁴, 10⁶) and B = [[10⁷, 1.1*10⁶, 10⁴, 0], [1.1*10⁶, 2*10⁵, -6000, 100], [10⁴, -6000, 2100, 110], [0, 100, 110, 10]] at K = 2, d = 4, one has ||Wₛs|| > rho² = 11263576900000000 >= ||Wᵣs||, with a four-part exact integer certificate; this refutes the belief 'for n = 2, we believe that the conjecture itself is likely true for any d and K, with step-size constants eta_(2,K) = 1' stated verbatim in arXiv:2103.07079v1 section 4.1
SSRS2known2026-09-03
the RS-GD half of Conjecture 1 holds at n = 2 with eta = 1 and no conditioning hypothesis: for all real symmetric PSD A, B and all c >= 0 with A + B <= (2c)*I, one has -c²*I <= (AB+BA)/2 <= c²*I, hence ||Wᵣs|| <= ||W_gd|| for every K and every d; the constant c² is attained at A = B = c*I, and eta = 1 is sharp – for every eta > 1 a 1x1 witness has W_gd = 0 while Wᵣs!= 0
SSRS3known2026-09-03
the d = 2 SS-RS inequality for every K and every real spectrum: if N is a real 2x2 matrix whose two eigenvalues are real ((tr N)² >= 4 det N) and -c*I <= sym N <= c*I, then -c^K*I <= sym(N^K) <= c^K*I; equivalently w_R(N^K) <= w_R(N)^K for the real numerical radius w_R(X) = ||sym X||. At N = AB with A, B PSD this is Yun-Sra-Jadbabaie's Theorem 4 (thm:ss-3), here with the PSD hypothesis weakened to 'N has real spectrum'. The real-spectrum hypothesis is not removable: a rotation has w_R(N²) = 1 > 0 = w_R(N)²
SSRS4measurement2026-09-03
the optimal step-size constant eta_(2,2) of Conjecture 1 satisfies 1/4 <= eta_(2,2) < 1 - 1/84375000 = 1 - 1.1851852e-8, the upper half KERNEL-BOUND: the SSRS1 witness rescaled by 10⁻6 and 10125000⁻1 satisfies Conjecture 1's own hypothesis (1-eta) I <= A, B <= I with 1-eta = 1/84375000 and still violates ||Wₛs|| <= ||Wᵣs||. A sharper witness, found by a homotopy in the conditioning cap and certified in exact rational arithmetic, gives eta_(2,2) < 1 - 3.9591821e-7; that one is not yet formalised
SSRS5measurement2026-09-03
the infimum over N = AB with A, B PSD of the margin lambdaₘin(sym(N²))/||sym N||² – which is >= -1 exactly when the K = 2 SS-RS inequality holds – is -1/3 at d = 2, numerically -0.999999998 at d = 3, and at most -1.0356 at d = 4 (exact witness); so d = 3 is the open dimension and, if the d = 3 numeric is right, d = 4 is the minimal dimension of any eta = 1 counterexample
This ledger entry is reported in prose and is not bound to a Lean theorem.SSRS6candidate2026-09-03
Conjecture 1 of Yun-Sra-Jadbabaie (arXiv:2103.07079v1) FAILS at n = 2, K = 2, d = 4 for every step-size constant eta > 1 - 1/389765: for the symmetric positive definite integer matrices A = diag(1, 49, 3844, 389376) and B = [[5074956432, 841928256, 7921368, 0], [841928256, 280642752, -13956696, 74958], [7921368, -13956696, 3066336, 126945], [0, 74958, 126945, 26908]], the rescaled pair A' = A/389376, B' = B/5220000000 satisfies the conjecture's own hypothesis (1/389765) I <= A', B' <= I and still has ||Wₛs|| > rho² >= ||Wᵣs|| at K = 2, with rho = 42869796155, rho² = 1837819422371252784025, the violating vector v = (-8, 4, -4, 8) and certified ratio 1.0482812150 (true ratio 1.0489088162). Hence eta_(2,2) < 1 - 1/389765 = 1 - 2.5656485e-6, a factor 216.5 sharper than conjectureₒne_fails (1 - 1.1851852e-8) and 6.5 sharper than the exact-arithmetic witness of journal/2026-09-03-ssrs-n2-founding.md section 7.1 (1 - 3.9591821e-7). The bracket on the optimal step-size constant is now 1/4 <= eta_(2,2) < 1 - 2.5656485e-6
SSRS7measurement2026-09-03
the conditioning of the SSRS6 witness, kernel-bound on BOTH sides. Upper: 1*I <= A <= 389376*I and (5220000000/389765)*I <= B <= 5220000000*I, by four cleared-LDL^T integer certificates, so cond(A) = 389376 exactly and cond(B) <= 389765; conditioningᵣayleigh records the Rayleigh-quotient reading that makes 'condition number' the right word. Lower: every Loewner sandwich m*I <= A <= M*I has M >= 389376*m (cond_A_ge) and every m*I <= B <= M*I has M >= 380791*m (cond_B_ge), so ANY normalisation (1-eta) I <= A/s_A, B/s_B <= I of this pair has 1 - eta <= 1/389376 (normalisation_floor). The cap 1/389765 used in SSRS6 is 0.0999% above that floor: the remaining about five and a half orders of magnitude (log10(0.75 / 2.5656485e-6) = 5.47; "seven" was v1's figure – v2 referee 2026-09-03) down to eta_(2,2) >= 1/4 are a gap in the WITNESS, not in its bookkeeping. Exact rational bisection on LDL^T: lambdaₘin(B) = 13704.3865656996, lambdaₘax(B) = 5218514684.2663055854, cond(B) = 380791.556
SSRS8routine2026-09-03
controls for the SSRS6 witness: (i) 10²1 is NOT a Loewner bound for Wᵣs, witnessed by u = (1,1,1,1), so with ||Wᵣs|| <= rho² = 1.8378e21 the bound rho² is bracketed in (10²1, rho²] and not vacuously large; (ii) at the wrong vector w = (1,0,0,0) the Rayleigh quotient of Wₛs is 6.073e19 and does NOT escape [-rho², rho²], so the refutation depends on the violating vector and is not an artefact of the shape of the statement; (iii) the claim cannot be weakened upward: (1/380800) I <= B/5220000000 is FALSE, refuted by the same integer vector that realises lambdaₘin(B); (iv) non-vacuity: A - 1*I and 389765*B - 5220000000*I are both PSD, so A and B are positive DEFINITE and the hypothesis of conjectureₒne_failsₛharp is satisfiable strictly inside the cone, not on its boundary
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Yun, Sra and Jadbabaie (arXiv:2103.07079v1, COLT 2021 open problem, *Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?*) study the expected iterate of stochastic gradient descent on a quadratic finite sum under three sampling schemes: single shuffle (SS, one permutation drawn once and reused), random reshuffling (RS, a fresh permutation each epoch), and plain gradient descent (GD). For real symmetric A₁, …, Aₙ (the Aᵢ = I − ηMᵢ of a quadratic problem) and K epochs they define, with P_σ = A_(σ(1)) A_(σ(2)) ⋯ A_(σ(n)),
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7