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

2024/12/08 by Jason M. Altschuler, Pablo A. Parrilo, Altschuler, Jason M. +1 · 1 voice · 2 citations
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DS #math.OC

paper · pdf · doi:10.48550/arxiv.2412.05790

arxiv published 2024/12/08 · arxiv updated 2026/05/29

Abstract

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.

Cited by

• Generalization of Silver Stepsize Schedule to Stochastic Optimization
• On the Effectiveness of the z-Transform Method in Quadratic Optimization

Discussions

• Cool new result: random arcsine stepsize schedule accelerates gradient descent (no momentum!) on separable problems. The separable class is clearly very limited, and it remains unclear if acceleration [bsky, 4 points, 0 comments]

Related

• Accelerating Proximal Gradient Descent via Silver Stepsizes
• Composing Optimized Stepsize Schedules for Gradient Descent
• Anytime Acceleration of Gradient Descent
• Generalization of Silver Stepsize Schedule to Stochastic Optimization
• Provably Faster Gradient Descent via Long Steps