# Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Dec 2024.

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

- [Negative Stepsizes Make Gradient-Descent-Ascent Converge](https://mlsanity.com/paper/2505.01423/) (2025)
- [Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes](https://mlsanity.com/paper/2504.04105/) (2025)
- [A lower bound for stepsize-based acceleration of gradient descent](https://mlsanity.com/paper/2608.10418/) (2026)
- [On the Effectiveness of the z-Transform Method in Quadratic Optimization](https://mlsanity.com/paper/2507.03404/) (2025)
- [Silver Rate Is (Almost) Optimal for Gradient Descent](https://mlsanity.com/paper/2609.09152/) (2026)
- [Mathematics of Data Science](https://mlsanity.com/paper/2607.11938/) (2026)

## Abstract (arXiv)

We show that for separable convex optimization, random stepsizes fully accelerate Gradient Descent. Specifically, using inverse stepsizes i.i.d. from the Arcsine distribution improves the convergence rate from O(k) to O(√k), where k is the condition number. No momentum or other algorithmic modifications are required. Our starting point is a remarkable "equalization property" of the Arcsine distribution: it yields an identical convergence rate for all quadratic functions. A key technical insight is that martingale arguments extend this phenomenon to all separable convex functions. We interpret this equalization as an extreme form of hedging: by using this random distribution over stepsizes, Gradient Descent converges at exactly the same rate for all functions in the function class.