Technical Summary: A Resolution of the SS–RS–GD Inequalities

Problem Statement

The paper addresses a conjecture proposed by Yun, Sra, and Jadbabaie (COLT 2021) regarding the convergence rates of three optimization schemes applied to finite-sum quadratic objectives:

1. Gradient Descent (GD): Uses the full batch at every step.
2. Random Shuffle (RS) SGD: Draws a fresh random permutation of components every epoch.
3. Single Shuffle (SS) SGD: Draws a single permutation at the outset and reuses it for all $K$ epochs.

For well-conditioned symmetric matrices $A_1, \dots, A_n$, the authors define operators $W_{SS}$, $W_{RS}$, and $W_{GD}$ that encode the expected iterate after $K$ epochs for each scheme. The conjecture posits that for sufficiently well-conditioned matrices (specifically, $(1-\eta)I \preceq A_i \preceq I$), the spectral norms of these operators satisfy the ordering:
$$\|W_{SS}\| \leq \|W_{RS}\| \leq \|W_{GD}\|$$
This ordering would imply that Single-Shuffle is the most efficient, followed by Random-Shuffle, with Gradient Descent being the least efficient (or having the slowest convergence rate in terms of the spectral radius of the error operator).

Methodology

The paper employs a combination of explicit counterexample construction and spectral analysis to resolve the conjecture.

1. Refutation of the SS–RS Inequality

To disprove the first inequality ($\|W_{SS}\| \leq \|W_{RS}\|$), the authors construct a specific counterexample:

• Dimension and Parameters: They fix $n=3$ components, $K=2$ epochs, and dimension $d=4$.
• Matrix Construction: They define rank-one projectors $P_i$ in $\mathbb{R}^2$ based on three unit vectors. They then construct matrices $B_i = qI_2 + (1-q)P_i$ and define the final matrices as tensor products $A_i = B_i \otimes B_i \in \mathbb{R}^{4\times 4}$.
• Conditioning: By choosing a parameter $q$ sufficiently close to 1, the condition number of $A_i$ can be made arbitrarily close to 1, satisfying the "well-conditioned" hypothesis of the conjecture for any proposed constant $\eta$.
• Spectral Analysis: The authors derive exact polynomial expressions for the eigenvalues of $W_{SS}$ and $W_{RS}$ as functions of $q$. They demonstrate that for $q$ in a specific range near 1, the largest eigenvalue of $W_{SS}$ strictly exceeds that of $W_{RS}$.

2. Proof of the RS–GD Inequality

To prove the second inequality ($\|W_{RS}\| \leq \|W_{GD}\|$), the authors utilize a reduction to a single-epoch bound and a near-identity matrix analysis:

• Reduction: Since $W_{RS} = R^K$ and $W_{GD} = G^{nK}$ (where $R$ is the average of permutation products and $G$ is the average of matrices), and given the symmetry and positive semi-definiteness of these operators for even powers, the problem reduces to proving $\|R\| \leq \|G\|^n$.
• Normalization: The matrices are normalized such that $C_i = \rho^{-1}A_i = I + X_i$, where $\rho = \|G\|$. The condition $(1-\eta)I \preceq A_i \preceq I$ translates to bounds on the perturbation matrices $X_i$.
• Expansion and Bounding: The operator $\tilde{R}$ (the normalized version of $R$) is expanded as a sum of terms involving products of $X_i$. The authors bound the spectral norm of the higher-order terms using the Cauchy-Schwarz inequality and the smallness of $\|X_i\|$.
• Conditioning Constant: They establish that if the condition number is bounded by $\eta = \frac{1}{4n^2+1}$, the spectral norm of the shuffled product operator remains bounded by the identity, thereby proving $\|R\| \leq \rho^n$.

Key Contributions and Results

1. Refutation of the SS–RS Inequality (Theorem 2)

The paper conclusively proves that the conjecture $\|W_{SS}\| \leq \|W_{RS}\|$ is false.

• Result: There exist symmetric positive definite matrices $A_1, A_2, A_3$ with condition numbers arbitrarily close to 1 such that $\|W_{SS}\| > \|W_{RS}\|$.
• Implication: The intuition that Single-Shuffle SGD is strictly superior to Random-Shuffle SGD in the well-conditioned regime does not hold universally, even for small dimensions ($n=3, d=4$).

2. Validation of the RS–GD Inequality (Theorem 3)

The paper proves that the conjecture $\|W_{RS}\| \leq \|W_{GD}\|$ holds under a specific conditioning constraint.

• Result: For any $n \geq 2$, $K \geq 1$, and $d \geq 1$, if the symmetric matrices satisfy $(1 - \frac{1}{4n^2+1})I \preceq A_i \preceq I$, then $\|W_{RS}\| \leq \|W_{GD}\|$.
• Significance: This confirms that Random-Shuffle SGD converges faster (or at least as fast) as Gradient Descent, provided the problem is sufficiently well-conditioned. The constant $\eta = \frac{1}{4n^2+1}$ is dimension-free regarding $d$ and independent of the number of epochs $K$.

Significance and Claims

The paper claims to resolve the COLT open question regarding the ordering of these optimization schemes.

• Resolution of Conjecture: The authors demonstrate that the proposed ordering is partially incorrect. While the RS–GD relationship holds for well-conditioned problems, the SS–RS relationship fails even in the most favorable (near-identity) conditions.
• Role of AI: The authors explicitly state that the core proof idea for the RS–GD inequality was generated by an AI model (GPT-5.5 Pro), while the counterexample construction and the final manuscript assembly were handled by the author and another AI tool (Claude Code). The author verified the proofs and polished the text.
• Limitations: The paper notes that the constant $\eta$ for the RS–GD inequality is likely not optimal, as the proof relies on a slack in the geometric series bound. However, it establishes the existence of a valid conditioning radius. Conversely, for the SS–RS inequality, no positive conditioning constant can save the conjecture, as the counterexample works for arbitrarily small $\eta$.

The work clarifies the theoretical landscape of finite-sum optimization, showing that while Random-Shuffle SGD maintains an advantage over Gradient Descent under mild conditions, it does not necessarily dominate Single-Shuffle SGD in terms of spectral radius for the expected iterate.