Nesterov trajectories minimize locally only for fourth power functions
When Are Nesterov Trajectories Eventually Locally Minimizing?
Machine Learning
Summary
This paper explores when certain paths used in optimization methods, called Nesterov trajectories, actually represent locally best solutions to a problem. The authors discovered that for functions based on distances raised to a power, these trajectories only behave like local minima when the power is exactly four. They connect this unique case to ideas from an area of mathematics that studies stability of certain equations.
What this means in practice
- •For optimization engineers: Identify settings where accelerated optimization trajectories guarantee local optimality, improving algorithm design for problems with specific power-based objectives.
- •For applied mathematicians: Use the equivalence to Schrödinger operator positivity to analyze stability properties of nonlinear dynamical systems modeled by similar trajectories.
A theory result. No direct application yet.
Authors
Peyman Morteza, Stephen Wright
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.