CS Paper Radar

When Are Nesterov Trajectories Eventually Locally Minimizing?

Peyman Morteza, Stephen Wright

cs.LG math.OCstat.ML ·submitted 2026-10-23 22:27 UTC · v1
unusual

Abstract

We revisit the variational characterization of Nesterov's celebrated method and study when Nesterov trajectories are eventually locally minimizing in a variational sense, a notion that we define precisely. We show that this question is equivalent to the nonnegativity of an associated Schrödinger operator acting on variations of the trajectory. For power objectives of the form \[ f(x)=\frac{1}{p}\|x\|^p \] (where $\| \cdot\|$ denotes the Euclidean norm), we give a complete characterization: Among all exponents $p\ge 2$, the Nesterov trajectory with non-zero initial position is eventually locally minimizing if and only if $p=4$. We further interpret this exceptional exponent through the stability theory of semilinear elliptic equations.

Closest papers

Nearest neighbours by meaning across the whole index.

Variational Structure at the Edge of Stability

cs.LG ·2026-08-21 ·Eric Regis
unusual similarity 0.50
Abstract

When discrete-time optimizers operate at the edge of stability, they exhibit near-two-periodic behavior. These oscillatory dynamics are reminiscent of conservative systems, such as the dynamics generated by symplectic integrators. However, a precise formulation of the connection between discrete-time optimizers at the edge of stability and discrete mechanics remains underexplored. Recently, Litman introduced the "edge coupling": a functional on consecutive gradient descent iterates whose critical points encode the fixed points and two-point orbits of the gradient descent dynamics. Here we extend the edge coupling to heavy-ball and Nesterov momentum. We show that its critical points characterize the fixed points and two-point orbits, with its Hessian characterizing their stability. We also show that the edge coupling can be identified with the symmetric Verlet action, formalizing the connection between the edge of stability and discrete mechanics.

0.27

Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity

cs.LG math.OCstat.ML ·2026-11-03 ·Cedar Site Bai
theory similarity 0.48
Abstract

In this paper, we provide tight lower bounds for minimizing high-order Hölder-smooth and uniformly convex functions when their orders match. Specifically, we consider functions whose $p^{th}$-order derivatives are Hölder continuous with degree $ν$ and parameter $H$, and that are uniformly convex with degree $q$ and parameter $σ$. When these orders match, namely, $q = p + ν$, we show that any deterministic algorithm with access to derivatives up to order $p$ requires $Ω\left(\left(\frac{H}σ\right)^{\frac{2}{3(p+ν)-2}}\log\frac{Δ_0}ε\right)$ oracle calls to reduce an initial optimality gap of $Δ_0$ to $ε$. This matches the corresponding upper bound and establishes a higher-order uniformly convex counterpart to Nesterov's classical first-order lower bound for strongly convex functions. Rather than directly generalizing Nesterov's classical quadratic-chain construction, we develop a multiscale phase-wise construction that preserves previous oracle responses while maintaining global Hölder smoothness and uniform convexity. Our result resolves the matched case left open by existing lower bounds for the two asymmetric regimes.

0.26

Incremental Stability of Gradient Flows under Generalized Polyak-Łojasiewicz Inequalities and Its Implications for General Systems

eess.SY math.OC ·2026-10-29 ·Andreas Oliveira, Arthur C. B. de Oliveira, Mario Sznaier, Eduardo Sontag
similarity 0.48
Abstract

Gradient flows of twice continuously differentiable strongly convex and convex objectives are, respectively, incrementally exponentially stable and non-expansive in the Euclidean metric. In this work, we investigate to what extent these properties extend to nonconvex objectives satisfying generalized Polyak-Łojasiewicz inequalities. For objectives with a unique minimizer, we establish conditions under which the gradient flow is contracting in a state-dependent Riemannian metric and incrementally exponentially stable. For objectives with nonunique minimizers, we generalize the non-expansivity of convex objectives to incremental stability for more general nonconvex objectives. We focus on incremental stability due to its implication to convergence to equilibrium points; when paired with a Lyapunov function it implies pointwise convergence to a minimizer and continuity of the endpoint map. Along the way, we derive new structural results for incrementally stable nonlinear systems and extend the analysis to Heavy-Ball and Dynamical Inertial Newton flows.

0.28

Least-time Gradient Flow

cs.LG math.OC ·2026-10-01 ·Alessandro Betti, Marco Gori, Stefano Melacci, Jinwei Zhao
theoryunusual similarity 0.48
Abstract

Prescribing the speed of gradient flow on the risk itself, by the dynamics $\dot w=-u(E(w))\nabla E(w)/\abs{\nabla E(w)}^{2}$, makes the risk $e(t)=E(w(t))$ obey $\dot e=-u(e)$ exactly, whatever the landscape~$E$; the time needed to reach zero risk from $e_0$ is $\int_0^{e_0}\dd e/u(e)$. Minimizing this time alone is ill posed, and we study the regularized problem $\inf\{\int_0^{e_0}(\tfrac\lambda2\abs{u'}^{2}+1/u)\,\dd e:\ u\in H^{1}(0,e_0),\ u\ge0,\ u(0)=0\}$, $λ>0$. We prove that the minimizer exists, is unique, and is a linearly scaled cycloid, and we show that the optimal rate behaves like $u^{*}(e)\sim(9/(2λ))^{1/3}e^{2/3}$ near zero risk: the exponent $2/3$ is the one found in \cite{betti2026holder} by a power-law ansatz, and it lies in the Hölder window $(\tfrac12,1)$ where the arrival is in finite time with vanishing weight speed. The proof follows the classical route: existence by the direct method, uniqueness by strict convexity, positivity of the minimizer away from the origin, and the explicit integration of the Euler-Lagrange equation.

0.24

Optimization over covariance matrices with a parameterized metric

cs.LG math.OC ·2026-09-15 ·Yibang Li, Bamdev Mishra, Pratik Jawanpuria, Cyrus Mostajeran
theory similarity 0.47
Abstract

The choice of Riemannian metric can strongly influence the convergence of gradient-based optimization over covariance matrices. Euclidean, Bures-Wasserstein and affine-invariant metrics are common choices, but their relative effectiveness depends on the objective. We introduce a two-parameter family defined by $X^{p}LX^{q}+X^{q}LX^{p}=U$, solved for $L$ at each tangent vector $U$, that contains all three as exact members, at $(0,0)$, $(1,0)$ and $(1,1)$, and extends past them. We treat the choice of member as a particular way of preconditioning for a given problem. To this end, we analyze the conditioning of the Riemannian Hessian at the solution. We show that it obeys a lower bound that depends on $(p,q)$ only through the exponent $r=p+q$. When the Euclidean Hessian is a pure power that mixes no eigendirections, the member $p=q=r/2$ attains that bound, and a closed-form criterion identifies the other members that do. We discuss ways to tune $r$ for a given problem. Experiments on real covariance data confirm the predicted conditioning and the benefit of tuning $r$. A task covariance example shows a further gain from tuning the shape.

0.31

Non-Acceleration of the Heavy-Ball Method in 1D

cs.LG math.OC ·2026-10-18 ·Konstantinos Fotopoulos, Michael Helcig, Karl Deck, Jannis Alsbach
similarity 0.47
Abstract

Despite having an asymptotically optimal rate of convergence on convex quadratics, the acceleration of Polyak's heavy-ball method and a characterization of its dynamics within more general settings have remained long standing open problems. Recently, the work of Goujaud et al. [Math. Program. (2025)] made progress regarding acceleration in the context of smooth, strongly convex minimization: for a small enough inverse condition number, either the method does not accelerate on quadratics, or there exists a smooth strongly convex function such that heavy-ball cycles over the roots of unity. The constructed functions have two variables, thus leaving the question of acceleration over univariate functions open. In this work, we use a Fourier-based analysis to i) provide a proof for the non-acceleration of the heavy-ball method over the class of univariate smooth strongly convex functions. We also ii) provide a strict enlargement of the previous root-of-unity cycling region, with insights regarding the "fractional" sets of Goujaud et al. [arXiv:2502.19916], and iii) give a higher dimensional cycling instance which is not covered by root-of-unity cycling.

0.20

Near-Optimal Acceleration for Smooth $\ell_p$ / $\ell_q$ Nondual Convex First-Order Oracle Optimization

cs.LG math.OC ·2026-09-18 ·David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, Mathieu Molina
similarity 0.46
Abstract

We study the optimization of convex objectives with $(L,κ-1)$-Hölder-continuous gradients in $\ell_q$ over $R B_p^d$, $1<κ\le 2$. (MG26) provides selectors with a movement bound for the problem of chasing high-dimensional convex nested sets for every $p<q$ and generally reduces Lipschitz convex optimization to bounds on the movement of selectors. We couple that movement with Hölder descent yielding a polynomial-runtime first-order method whose feasible output, in the high-dimensional regime $T\le d$ and for $p<\min\{q,2\}$, has error $$ \widetilde O_{κ,p,q}\!\left( \frac{LR^κ}{T^{κ(1+1/p-(1/q-1/2)_+)-1}} \right), $$ after $T$ queries to a first-order oracle, solving the COLT 2015 open problem of (Guz15), up to logarithmic factors. At $(p,q)=(1,2)$, the rate is $\widetilde{O}(LR^κ/T^{2κ-1})$, including $\widetilde{O}(LR^2/T^{3})$ cubic decay in the smooth case.

0.41

Tilted Convexity and an Exact Offline-Online Separation

cs.LG cs.CCmath.OCstat.ML ·2026-11-02 ·Mohammad Pedramfar, Rajiv Khanna, Christopher John Quinn, Vaneet Aggarwal
similarity 0.45
Abstract

Convexity has three equivalent descriptions: support by affine functions, monotonicity of the subdifferential, and increasing secant slopes. We weaken all three by one distortion with parameter $γ\in(0,1]$, which multiplies positive changes by $γ$ and divides negative ones by $γ$. The resulting classes are the convex functions at $γ=1$ and, for $γ<1$, are distinct and nested, with the parameter dropping by at most a square along the chain. For proper lower semicontinuous functions in these classes, the effective domain is convex, local minimizers are global, and the function is locally Lipschitz on the relative interior of its domain. The classes separate offline from online optimization over compact convex sets with efficient projection, with access to function values and bounded support vectors. A smooth member of any class can be minimized to additive accuracy $\varepsilon$ with $\mathrm{poly}(1/\varepsilon)$ first-order queries and projections. Online, with nonpositive losses and $α$-regret measured against $α$ times the best fixed point, a polynomial-time algorithm achieves $γ$-regret $O(\sqrt T)$ on the largest class. For every fixed, effectively specified $γ\in(0,1)$ and every $α\in(γ,1]$, no randomized polynomial-time algorithm has sublinear expected $α$-regret unless $\mathbf{NP}=\mathbf{RP}$, already for smooth concave polynomial losses in the smallest class, each minimized by one linear optimization. Thus, unless $\mathbf{NP}=\mathbf{RP}$, $γ$ is the exact online coefficient of each class, while the offline coefficient is one.

0.15