# Convexity of Optimization Curves: Local Sharp Thresholds, Robustness Impossibility, and New Counterexamples

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 12 references that are in the map.
- First posted on arXiv 10 Sep 2025.

## Builds on (most cited first, 4 of 4)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k2](https://mlsanity.com/paper/1510.08740/) (2015)
- [Are Convex Optimization Curves Convex?](https://mlsanity.com/paper/2503.10138/) (2025)

## Abstract (arXiv)

We study when the optimization curve of first-order methods -- the sequence f(xn)*n≥0 produced by constant-stepsize iterations -- is convex, equivalently when the forward differences f(xn)-f(x*n+1) are nonincreasing. For gradient descent (GD) on convex L-smooth functions, the curve is convex for all stepsizes η ≤ 1.75/L, and this threshold is tight. Moreover, gradient norms are nonincreasing for all η ≤ 2/L, and in continuous time (gradient flow) the curve is always convex. These results complement and refine the classical smooth convex optimization toolbox, connecting discrete and continuous dynamics as well as worst-case analyses.