Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization

Abstract¶

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 that with these stepsizes, gradient descent computes an epsilon-minimizer in O(epsilon^-log_rho 2) = O(epsilon^(-0).7864) iterations, where rho = 1+sqrt(2) is the silver ratio. This is intermediate between the textbook unaccelerated rate O(epsilon^(-1)) and the accelerated rate O(1/sqrt(epsilon)) due to Nesterov in 1983. The Silver Stepsize Schedule is a simple explicit fractal: the i-th stepsize is 1+rho^(v)(i)-1 where v(i) is the 2-adic valuation of i. The design and analysis are conceptually identical to the strongly convex setting in Part I, but simplify remarkably in this specific setting.

Links¶

Tags¶

Similar Papers¶