# Recht-R'e Noncommutative Arithmetic-Geometric Mean Conjecture is False

arXiv: https://arxiv.org/abs/2006.01510 · HTML: https://mlsanity.com/paper/2006.01510/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2020.

## Built on by (most cited first, 16 of 16)

- [Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond](https://mlsanity.com/paper/2110.10342/) (2021)
- [Permutation-Based SGD: Is Random Optimal?](https://mlsanity.com/paper/2102.09718/) (2021)
- [Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems](https://mlsanity.com/paper/2106.06880/) (2021)
- [Convergence of Random Reshuffling Under The Kurdyka-Lojasiewicz Inequality](https://mlsanity.com/paper/2110.04926/) (2021)
- [From Continual Learning to SGD and Back: Better Rates for Continual Linear Models](https://mlsanity.com/paper/2504.04579/) (2025)
- [Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime](https://mlsanity.com/paper/2507.11274/) (2025)
- [Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization](https://mlsanity.com/paper/2206.02953/) (2022)
- [Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?](https://mlsanity.com/paper/2103.07079/) (2021)
- [Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds](https://mlsanity.com/paper/2306.12498/) (2023)
- [Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization](https://mlsanity.com/paper/2505.08306/) (2025)
- [Computing the Variance of Shuffling Stochastic Gradient Algorithms via Power Spectral Density Analysis](https://mlsanity.com/paper/2206.00632/) (2022)
- [Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-L ojasiewicz Condition](https://mlsanity.com/paper/2304.00459/) (2023)
- [Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD](https://mlsanity.com/paper/2604.10373/) (2026)
- [A Resolution of the SS--RS--GD Inequalities](https://mlsanity.com/paper/2607.22620/) (2026)
- [Linear Convergence of Reshuffling Kaczmarz Methods With Sparse Constraints](https://mlsanity.com/paper/2304.10123/) (2023)
- [When the noncommutative AM-GM inequality holds](https://mlsanity.com/paper/2610.04874/) (2026)

## Abstract (arXiv)

Stochastic optimization algorithms have become indispensable in modern machine learning. An unresolved foundational question in this area is the difference between with-replacement sampling and without-replacement sampling -- does the latter have superior convergence rate compared to the former? A groundbreaking result of Recht and R'e reduces the problem to a noncommutative analogue of the arithmetic-geometric mean inequality where n positive numbers are replaced by n positive definite matrices. If this inequality holds for all n, then without-replacement sampling indeed outperforms with-replacement sampling. The conjectured Recht-R'e inequality has so far only been established for n = 2 and a special case of n = 3. We will show that the Recht-R'e conjecture is false for general n. Our approach relies on the noncommutative Positivstellensatz, which allows us to reduce the conjectured inequality to a semidefinite program and the validity of the conjecture to certain bounds for the optimum values, which we show are false as soon as n = 5.