Convexity of Optimization Curves: Local Sharp Thresholds, Robustness Impossibility, and New Counterexamples
This work provides refined theoretical insights into optimization dynamics, addressing a specific problem in mathematical optimization for researchers and practitioners.
The paper investigates the convexity of optimization curves for first-order methods, establishing that for gradient descent on convex L-smooth functions, the curve is convex for stepsizes up to 1.75/L, with this threshold being tight, and gradient norms are nonincreasing up to 2/L.
We study when the \emph{optimization curve} of first-order methods -- the sequence \${f(x\_n)}*{n\ge0}\$ produced by constant-stepsize iterations -- is convex, equivalently when the forward differences \$f(x\_n)-f(x*{n+1})\$ are nonincreasing. For gradient descent (GD) on convex \$L\$-smooth functions, the curve is convex for all stepsizes \$η\le 1.75/L\$, and this threshold is tight. Moreover, gradient norms are nonincreasing for all \$η\le 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.