Open Problem: Anytime Convergence Rate of Gradient Descent

Guy Kornowski, Ohad Shamir
6/19/2024
math.OCcs.LG

No confident code implementation found for this paper. 3 possible matches can be shown below.

Abstract

Recent results show that vanilla gradient descent can be accelerated for smooth convex objectives, merely by changing the stepsize sequence. We show that this can lead to surprisingly large errors indefinitely, and therefore ask: Is there any stepsize schedule for gradient descent that accelerates the classic $\mathcal{O}(1/T)$ convergence rate, at \emph{any} stopping time $T$?

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 3 weaker matches are hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Anytime Acceleration of Gradient Descent

93% match2024

Provably Faster Gradient Descent via Long Steps

87% match1 repo82023

Improved Gradient Descent Lower Bounds Beyond Nesterov

86% match2026

Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth

81% match1 repo102024

The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives

81% match1 repo2026

Silver Rate Is (Almost) Optimal for Gradient Descent Acceleration

80% match2026

Cite this paper

@article{kornowski2024open,
  title  = {Open Problem: Anytime Convergence Rate of Gradient Descent},
  author = {Guy Kornowski and Ohad Shamir},
  year   = {2024},
  eprint = {2406.13888},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2406.13888v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2406.13888.svg)](https://codeofpaper.com/paper/2406.13888)

Discussion