# Accelerated Gradient Descent via Long Steps

**Authors:** Benjamin Grimmer, Kevin Shu, Alex L. Wang  
**arXiv:** [2309.09961](https://arxiv.org/abs/2309.09961)  
**Date:** 2023-09-18  
**Summary page:** https://www.summarizepaper.com/en/paper/2309.09961v1/

## Key points

- Authors explore accelerated convergence rates in smooth convex optimization problems
- Previous work by Grimmer showed that longer steps can improve gradient descent's convergence guarantees
- Authors provide proof of achieving an accelerated rate faster than O(1/T)
- Convergence rate demonstrated as O(1/T^{1.02449}) using nonconstant nonperiodic stepsizes
- Theory for strongly convex optimization allows for big-O convergence rate accelerations from long steps
- Open question remains whether the conjectured rates of O(1/T^{1.178}) or O(1/T^2) can be achieved
- Paper contributes to understanding of accelerated convergence rates and benefits of longer steps in gradient descent algorithms

## Summary

In their paper titled "Accelerated Gradient Descent via Long Steps," authors Benjamin Grimmer, Kevin Shu, and Alex L. Wang explore the potential for accelerated convergence rates in smooth convex optimization problems. They build upon previous work by Grimmer [1], who demonstrated that utilizing longer steps periodically can improve gradient descent's state-of-the-art O(1/T) convergence guarantees by constant factors. Grimmer also conjectured the possibility of achieving an accelerated rate faster than O(1/T). In this study, the authors provide a proof of such a big-O gain and establish gradient descent's first accelerated convergence rate in this setting. Specifically, they demonstrate a convergence rate of O(1/T^{1.02449}) for smooth convex minimization by employing a nonconstant nonperiodic sequence of increasingly large stepsizes. The authors note that their theory for strongly convex optimization allows for big-O convergence rate accelerations from long steps, which are somewhat weaker but similar to those concurrently developed by Altschuler and Parrilo [3]. However, it remains an open question whether one can achieve the O(1/T^{1.178}) rate conjectured by Das Gupta et al. [2] or even reach the optimal gradient method rate of O(1/T^2). Overall, this paper contributes to the understanding of accelerated convergence rates in smooth convex optimization problems and provides new insights into the potential benefits of utilizing longer steps in gradient descent algorithms. References[1] Grimmer[2] Das Gupta et al.