Convexity of Optimization Curves: Local Sharp Thresholds, Robustness Impossibility, and New Counterexamples
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909781723185152 |
|---|---|
| author | Hieu, Le Duc |
| author_facet | Hieu, Le Duc |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_08954 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Convexity of Optimization Curves: Local Sharp Thresholds, Robustness Impossibility, and New Counterexamples Hieu, Le Duc Optimization and Control Machine Learning 90C25, 90C30, 65K05, 37N40, 26B25 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. |
| title | Convexity of Optimization Curves: Local Sharp Thresholds, Robustness Impossibility, and New Counterexamples |
| topic | Optimization and Control Machine Learning 90C25, 90C30, 65K05, 37N40, 26B25 |
| url | https://arxiv.org/abs/2509.08954 |