Acceleration by stepsize hedging: Silver Stepsize Schedule for smooth convex optimization

We provide a concise, self-contained proof that the Silver Stepsize Schedule proposed in our companion paper directly applies to smooth (non-strongly) convex optimization. Specifically, we show that with these stepsizes, gradient descent computes an \(\varepsilon \) $\epsilon$ -minimizer in \(O(\varepsilon ^{-\log _{\rho } 2}) = O(\varepsilon ^{-0.7864})\) $O({\epsilon }^{-{log}_{\rho }2})=O({\epsilon }^{-0.7864})$ iterations, where \(\rho = 1+\sqrt{2}\) $\rho =1+\sqrt{2}$ is the silver ratio. This is intermediate between the textbook unaccelerated rate \(O(\varepsilon ^{-1})\) $O({\epsilon }^{-1})$ and the accelerated rate \(O(\varepsilon ^{-1/2})\) $O({\epsilon }^{-1/2})$ due to Nesterov in 1983. The Silver Stepsize Schedule is a simple explicit fractal: the i-th stepsize is \(1 + \rho ^{\nu (i)-1}\) $1+{\rho }^{\nu (i)-1}$ where \(\nu (i)\) $\nu (i)$ is the 2-adic valuation of i. The design and analysis are conceptually identical to the strongly convex setting in our companion paper, but simplify remarkably in this specific setting.