Convexity of Optimization Curves: Local Sharp Thresholds, Robustness Impossibility, and New Counterexamples
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Local and Global Uniform Convexity Conditions
We review various characterizations of uniform convexity and smoothness on norm balls in finite-dimensional spaces and connect results stemming from the geometry of Banach spaces with \textit{scaling inequalities} used i…
Learning TheoryNew Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
We study fundamental limits of first-order stochastic optimization in a range of nonconvex settings, including L-smooth functions satisfying Quasar-Convexity (QC), Quadratic Growth (QG), and Restricted Secant Inequalitie…
Stochastic OptimizationAn Elastica Geodesic Approach With Convexity Shape Prior
The minimal geodesic models based on the Eikonal equations are capable of finding suitable solutions in various image segmentation scenarios. Existing geodesic-based segmentation approaches usually exploit the image …
Image SegmentationSegmentationSemantic SegmentationOnline stochastic gradient descent on non-convex losses from high-dimensional inference
Stochastic gradient descent (SGD) is a popular algorithm for optimization problems arising in high-dimensional inference tasks. Here one produces an estimator of an unknown parameter from independent samples of data by i…
General Classificationparameter estimationRetrievalVocal Bursts Intensity PredictionCharacterization of the basin of convexity for multi-snapshot spike deconvolution via variable projection
We study the problem of multi-snapshot spike deconvolution, where the goal is to recover the locations of sparse impulses from their noisy convolution with a known point spread function (PSF) across multiple snapshots. W…