Anytime Acceleration of Gradient Descent

Abstract

This work investigates stepsize-based acceleration of gradient descent with anytime convergence guarantees. For smooth (non-strongly) convex optimization, we propose a stepsize schedule that allows gradient descent to achieve convergence guarantees of O(T^-2log_2ρ/1+log_2ρ) ≈ O(T^-1.119) for any stopping time T, where ρ=√(2)+1 is the silver ratio and the stepsize schedule is predetermined without prior knowledge of the stopping time. This result provides an affirmative answer to a COLT open problem regarding whether stepsize-based acceleration can yield anytime convergence rates of o(T^-1). We further extend our theory to yield anytime convergence guarantees of exp(-Ω(T/κ^0.893)) for smooth and strongly convex optimization, with κ being the condition number.