Provably Faster Gradient Descent via Long Steps
This work addresses convergence speed in optimization for machine learning practitioners, but it appears incremental as it builds on existing gradient descent analyses with a new theoretical approach.
The paper tackles the problem of slow convergence in gradient descent for smooth convex optimization by proposing a nonconstant stepsize policy with long steps, which may temporarily increase the objective but leads to provably faster long-term convergence, with a conjecture for an O(1/T log T) rate supported by numerical validation.
This work establishes new convergence guarantees for gradient descent in smooth convex optimization via a computer-assisted analysis technique. Our theory allows nonconstant stepsize policies with frequent long steps potentially violating descent by analyzing the overall effect of many iterations at once rather than the typical one-iteration inductions used in most first-order method analyses. We show that long steps, which may increase the objective value in the short term, lead to provably faster convergence in the long term. A conjecture towards proving a faster $O(1/T\log T)$ rate for gradient descent is also motivated along with simple numerical validation.