Search papers, labs, and topics across Lattice.
This paper investigates the acceleration of gradient descent (GD) in smooth convex optimization by establishing improved lower bounds for predetermined stepsizes. The authors derive a non-anytime lower bound of \(Ω(n^{-1.6342})\) and an anytime lower bound of \(Ω(n^{-1.2408})\), surpassing previous results and demonstrating a clear distinction in convergence rates between anytime and non-anytime settings. These findings not only refine the theoretical understanding of GD's limitations but also highlight the potential for significant improvements in optimization strategies.
Achieving a new anytime lower bound of \(Ω(n^{-1.2408})\) reveals critical insights into the acceleration limits of gradient descent.
We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical $Ω(n^{-2})$ first-order oracle lower bound of Nemirovsky and Yudin, we prove an $Ω(n^{-1.6342})$ non-anytime lower bound and an $Ω(n^{-1.2408})$ anytime lower bound. These improve the recent $Ω(n^{-1.932})$ non-anytime lower bound of Ma and Chen and the $Ω(n^{-4/3})$ anytime lower bound of Tsai et al., respectively. Together with the non-anytime $O(n^{-\log_2(1+\sqrt{2})})$ rate achieved by silver schedules, our anytime lower bound establishes a strict separation between the achievable convergence exponents in the two settings.
