3.6k citations · 12.4k across the 101 of their papers we have counts for
67 papers · 1 filter
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…
Convex Ternary Quartics Are SOS-Convex
Amir Ali Ahmadi, Grigoriy Blekherman, Pablo A. Parrilo
We prove that convex ternary quartic forms are sum-of-squares-convex (sos-convex). This result is in a meaningful sense the ``convex analogue'' a celebrated theorem of Hilbert from…
Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization
Jason M. Altschuler, Pablo A. Parrilo
We provide a concise, self-contained proof that the Silver Stepsize Schedule proposed in Part I directly applies to smooth (non-strongly) convex optimization. Specifically, we show…
Improved Nonnegativity Testing in the Bernstein Basis via Geometric Means
Mitchell Tong Harris, Pablo A. Parrilo
We develop a new kind of nonnegativity certificate for univariate polynomials on an interval. In many applications, nonnegative Bernstein coefficients are often used as a simple wa…
Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule
Jason M. Altschuler, Pablo A. Parrilo
Can we accelerate convergence of gradient descent without changing the algorithm -- just by carefully choosing stepsizes? Surprisingly, we show that the answer is yes. Our proposed…