8 papers · 1 filter
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…
Min-Max Optimization Is Strictly Easier Than Variational Inequalities
Henry Shugart, Jason M. Altschuler
Classically, a mainstream approach for solving a convex-concave min-max problem is to instead solve the variational inequality problem arising from its first-order optimality condi…
Optimized methods for composite optimization: a reduction perspective
Jinho Bok, Jason M. Altschuler
Recent advances in convex optimization have leveraged computer-assisted proofs to develop optimized first-order methods that improve over classical algorithms. However, each optimi…