# First-order algorithms converge faster than O(1/k) on convex problems

arXiv: https://arxiv.org/abs/1812.08485 · HTML: https://mlsanity.com/paper/1812.08485/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Dec 2018.

## Built on by (most cited first, 3 of 3)

- [Provably Faster Gradient Descent via Long Steps](https://mlsanity.com/paper/2307.06324/) (2023)
- [Open Problem: Anytime Convergence Rate of Gradient Descent](https://mlsanity.com/paper/2406.13888/) (2024)
- [Towards Universal Convergence of Backward Error in Linear System Solvers](https://mlsanity.com/paper/2604.16075/) (2026)

## Abstract (arXiv)

It is well known that both gradient descent and stochastic coordinate descent achieve a global convergence rate of O(1/k) in the objective value, when applied to a scheme for minimizing a Lipschitz-continuously differentiable, unconstrained convex function. In this work, we improve this rate to o(1/k). We extend the result to proximal gradient and proximal coordinate descent on regularized problems to show similar o(1/k) convergence rates. The result is tight in the sense that a rate of O(1/k1+ε) is not generally attainable for any ε>0, for any of these methods.