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

Abstract 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 $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -minimizer in $$O(\varepsilon ^{-\log _{\rho } 2}) = O(\varepsilon ^{-0.7864})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>ε</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:msub> <mml:mo>log</mml:mo> <mml:mi>ρ</mml:mi> </mml:msub> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>ε</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>0.7864</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> iterations, where $$\rho = 1+\sqrt{2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ρ</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:msqrt> <mml:mn>2</mml:mn> </mml:msqrt> </mml:mrow> </mml:math> is the silver ratio. This is intermediate between the textbook unaccelerated rate $$O(\varepsilon ^{-1})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>ε</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and the accelerated rate $$O(\varepsilon ^{-1/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>ε</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> due to Nesterov in 1983. The Silver Stepsize Schedule is a simple explicit fractal: the i -th stepsize is $$1 + \rho ^{\nu (i)-1}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:msup> <mml:mi>ρ</mml:mi> <mml:mrow> <mml:mi>ν</mml:mi> <mml:mo>(</mml:mo> <mml:mi>i</mml:mi> <mml:mo>)</mml:mo> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> where $$\nu (i)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ν</mml:mi> <mml:mo>(</mml:mo> <mml:mi>i</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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.