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

• URL: http://arxiv.org/abs/2607.22620v1
• Date: Tue, 16 Jun 2026 16:17:42 GMT
• Title: A Resolution of the SS--RS--GD Inequalities
• Abstract summary: proof was found via GPT-5.5 Pro extended prompted by the author.<n>The conjecture is resolved, $bullet$ SS-RS inequality fails.<n>For every symmetric $A_i$ with $bigl (1-frac14n2+1bigr)Ipreceq A_ipreceq I$, one has $|W_rs|le|W_gd|$.
• Score: 9.373325778575127
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee [12.89814955033651]
  Randomized sketch-and-solve algorithms accelerate overconstrained $ell$ regression by replacing the input with a smaller problem.<n>Our sketch yields the $ell_infty$ guarantee with $m=O(-2dlog d)$ rows, uses one Hadamard pass with a padded internal dimension $N=widetildeO(n+-2d3)$, and is efficient to apply.
  arXiv  Detail & Related papers  (2026-08-27T02:43:30Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$ can affect prediction by scale $r_j$ and enters only $n_T,j=T-j+1$ prediction rounds.<n>For every summable envelope, a localized mixture proves $cR_T(r)leq C_T(r)$.<n>For exponential and envelopes, under the stated finite-sample condition, a Toeplitz-design converse proves $cR_T(r)geq c_T(r)$.
  arXiv  Detail & Related papers  (2026-08-27T01:31:46Z)
• A Counterexample to the Tang Zhang Schatten Norm Conjecture and Sharp Positive Results [1.8051706864605614]
  Tang and Zhang conjectured an explicit formula for every finite $p>1$.<n>We prove the conjectured sharp bound for every family of rank-at-most-one summands when $2leq pinfty$.
  arXiv  Detail & Related papers  (2026-08-16T06:10:33Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• On the convergence of graph Laplacians with a symmetric divergence [0.0]
  A key estimate for the geodesic distance $d_g$ is that there exists $K > 0$ such that $0 leq d_g(p, q)2 - |p-q|2 leq K d_g(p, q)4$ for all $p, q in mathcalM$.<n>We demonstrate that this is sufficient for the pointwise convergence of graph Laplacians constructed with $D$ and discuss examples where $D$ is given by the Sinkhorn divergence on a family of probability measures para
  arXiv  Detail & Related papers  (2026-07-07T06:41:21Z)
• Is Dimensionality a Barrier for Retrieval Models? [21.1705493494434]
  We show that the best possible margin without a restriction on the dimension, $mathsfmmathsfrd(+infty, A)-2log n)$ can be nearly achieved in dimension $d = O(mathsfmmathsfrd(+infty, A)-2log n)$.<n>Our main theorem establishes that the best possible margin without a restriction on the dimension, $mathsfmmathsfrd(+infty, A)-2log n)$ can be
  arXiv  Detail & Related papers  (2026-05-22T12:22:20Z)
• Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$ [0.0]
  We establish deterministic hardness of approximation results for the Shortest Vector Problem in $ell_p$ norm ($mathsfSVP_p$) and for Unique-SVP ($mathsfuSVP_p$)<n>For every $p > 2$, we prove constant-ratio hardness: no-time algorithm approximates $mathsfSVP_p$ or $mathsfuSVP_p$ within a ratio of $sqrt2 - o(1)$.
  arXiv  Detail & Related papers  (2025-10-19T20:17:26Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• Non-representable quantum measures [55.2480439325792]
  Grade-$d$ measures on a $sigma$-algebra $mathcalAsubseteq 2X$ over a set $X$ are generalizations of measures satisfying one of a hierarchy of weak additivity-type conditions.<n>Every signed polymeasure $lambda$ on $(X,mathcalA)d$ produces a grade-$d$ measure as its diagonal $widetildelambda(A):=lambda(A,cdots,A)$.
  arXiv  Detail & Related papers  (2025-08-20T00:47:24Z)
• PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
  We introduce $mathsfPREM$ (Private Relative Error Multiplicative weight update), a new framework for generating synthetic data that a relative error guarantee for statistical queries under $(varepsilon, delta)$ differential privacy (DP)<n>We complement our algorithm with nearly matching lower bounds.
  arXiv  Detail & Related papers  (2025-02-20T18:32:02Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model. For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits. For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
  arXiv  Detail & Related papers  (2023-07-11T08:51:53Z)
• Matrix concentration inequalities and efficiency of random universal sets of quantum gates [0.0]
  For a random set $mathcalS subset U(d)$ of quantum gates we provide bounds on the probability that $mathcalS$ forms a $delta$-approximate $t$-design. We show that for $mathcalS$ drawn from an exact $t$-design the probability that it forms a $delta$-approximate $t$-design satisfies the inequality $mathbbPleft(delta geq x right)leq 2D_t
  arXiv  Detail & Related papers  (2022-02-10T23:44:09Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• On the continuous Zauner conjecture [0.0]
  In this paper we prove that for any $t in [-frac1d2-1, frac1d+1] setminus0$ the equality $textebr(Phi_t)=d2$ is equivalent to the existence of a pair of informationally complete unit norm tight frames.
  arXiv  Detail & Related papers  (2021-12-11T00:14:35Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  We study the problem of reconstructing a perfect matching $M*$ hidden in a randomly weighted $ntimes n$ bipartite graph. We show that if $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$.
  arXiv  Detail & Related papers  (2021-03-17T00:59:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.