11 papers
Negative Stepsizes Make Gradient-Descent-Ascent Converge
Henry Shugart, Jason M. Altschuler
Efficient computation of min-max problems is a central question in optimization, learning, games, and control. Arguably the most natural algorithm is gradient-descent-ascent (GDA).…
Stepsize Hedging: an Alternative Mechanism for Accelerating Gradient Descent
Jason M. Altschuler, Pablo A. Parrilo
Can gradient descent be accelerated by just choosing better stepsizes? Surprisingly, the answer is yes. This short expository article provides an accessible introduction to this ph…
Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule
Jason M. Altschuler, Pablo A. Parrilo
We show that for separable convex optimization, random stepsizes fully accelerate Gradient Descent. Specifically, using inverse stepsizes i.i.d. from the Arcsine distribution impro…
Negative Momentum for Convex-Concave Optimization
Henry Shugart, Shuyi Wang, Jason M. Altschuler
This paper revisits momentum in the context of min-max optimization. Momentum is a celebrated mechanism for accelerating gradient dynamics in settings like convex minimization, but…
Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling
Jason M. Altschuler, Sinho Chewi, Matthew S. Zhang
Acceleration is a celebrated cornerstone of convex optimization, enabling gradient-based algorithms to converge sublinearly in the condition number. A major open question is whethe…
Algorithmic warm starts for Hamiltonian Monte Carlo
Matthew S. Zhang, Jason M. Altschuler, Sinho Chewi
Generating samples from a continuous probability density is a central algorithmic problem across statistics, engineering, and the sciences. For high-dimensional settings, Hamiltoni…