betaFeedback

WorksMathematics

When Are Nesterov Trajectories Eventually Locally Minimizing?

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)=1p∥x∥p f(x)=\frac{1}{p}\|x\|^p (where ∥⋅∥\| \cdot\| denotes the Euclidean norm), we give a complete characterization: Among all exponents p≥2p\ge 2, the Nesterov trajectory with non-zero initial position is eventually locally minimizing if and only if p=4p=4. We further interpret this exceptional exponent through the stability theory of semilinear elliptic equations.

Introduction

A central problem in optimization is to minimize a convex function f:Rn→Rf : \mathbb{R}^n \to\mathbb{R},

min⁡x∈Rnf(x).\min_{x\in\mathbb{R}^n} f(x).

Nesterov’s accelerated gradient method [Nesterov, 1983] is a foundational algorithm for this problem. Its fast convergence guarantees have made it influential in large-scale optimization and machine learning [Wright and Recht, 2022]. Despite its simplicity, understanding the acceleration phenomenon has led to several perspectives, including continuous-time dynamics and variational characterization [5] (Wibisono et al. 2016; Su et al. 2016; Muehlebach and Jordan 2019; Muehlebach and Jordan 2021).

Su et al. [2016] derived the following second-order ordinary differential equation as a continuous-time analog of Nesterov’s method,

X¨(t)+3tX˙(t)+∇f(X(t))=0,t>0.\ddot{X}(t) + \frac{3}{t}\dot{X}(t) + \nabla f(X(t)) = 0,\qquad t > 0.

This ODE provides a dynamical system framework for studying accelerated trajectories. Building on that, a variational framework, developed by Wibisono et al. [2016] and discussed in Jordan [ [5], characterizes these trajectories as stationary points of the following action functional associated with a time-dependent Lagrangian,

L:Cxa,xb→R,\mathcal{L}: C_{x_a,x_b} \to\mathbb{R},
L(γ)=∫abt3(12∥γ˙(t)∥2−f(γ(t))) dt(1)\mathcal{L}(\gamma) = \int_a^b t^3\left(\frac{1}{2}\|\dot{\gamma}(t)\|^2 - f(\gamma(t))\right)\,dt \tag*{(1)}

where Cxa,xbC_{x_a,x_b} is the space of sufficiently regular curves, γ:[a,b]→Rn\gamma:[a,b]\to\mathbb{R}^n, connecting xax_a to xbx_b. We refer to L\mathcal{L} as the Nesterov functional.

In this paper, we revisit the variational perspective and study when the accelerated trajectories are actually minimizers of the Nesterov functional. We begin by computing its second variation (see Lemma 3.2). Our first key observation is that the change of variables,

s:=log⁡t,u(s):=esh(es)=th(t)(2)s := \log t,\qquad u(s) := e^s h(e^s) = th(t) \tag*{(2)}

transforms the second variation into an unweighted quadratic form associated with the Schrödinger operator,

Hγ:=−d2ds2+I−e2s∇2f(γ(es)),\mathcal{H}_{\gamma}:=-\frac{d^2}{ds^2}+I-e^{2s}\nabla^2f(\gamma(e^s)),

acting on vector-valued functions on [log⁡a,log⁡b][\log a,\log b] with Dirichlet boundary conditions. In particular, we show that nonnegativity of the second variation is equivalent to nonnegativity of the associated Schrödinger operator (see Propositions 4.1, 4.2, and 4.4). This representation implies that the Hessian scaled by the square of time,

e2s∇2f(γ(es))=t2∇2f(γ(t)),t=es,e^{2s}\nabla^2f(\gamma(e^s))=t^2\nabla^2f(\gamma(t)),\qquad t=e^s,

is the key quantity governing the behavior of the second variation. This observation also shows that the notion of minimality is dependent on the time along the flow. In particular, the starting time and interval length play a role in determining when the action is minimal or not. Motivated by this we define the notion of eventually locally minimizing (See also Definition 4.3).

Definition. Let X:[0,∞)→RnX:[0,\infty)\to\mathbb{R}^n be a Nesterov trajectory. Fix T0>0T_0>0. We say that XX is T0T_0-eventually locally minimizing if for every finite aa and bb satisfying T0<a<b<∞T_0<a<b<\infty, the restriction, X∣[a,b]X|_{[a,b]}, is a local minimizer of the Nesterov functional in H1H^1-topology, among curves satisfying, γ(a)=X(a)\gamma(a)=X(a), γ(b)=X(b)\gamma(b)=X(b). We say that XX is eventually locally minimizing if this holds for some T0>0T_0>0.

Intuitively speaking, this notion captures the idea that, after a sufficiently large time, the trajectory locally minimizes the action on every subsequent finite interval. Motivated by this notion, we ask the following question:

For which classes of objective functions is the Nesterov trajectory eventually locally minimizing?

Zhang et al. [2021] study the minimality of accelerated trajectories for quadratic objectives on finite intervals. Beyond introducing eventual local minimality as a natural notion for studying long-time variational behavior, we show that vanishing curvature alone is insufficient to guarantee this property. Our main result (see Theorem 5.1) gives a complete characterization for power objective functions f(x)=1p∥x∥pf(x)=\frac{1}{p}\|x\|^p with p≥2p\geq2. Perhaps surprisingly, we find that the only exponent for which the regular Nesterov trajectory with non-zero initial position is eventually locally minimizing is p=4p=4. The proof is inspired by the stability theory of radial solutions of semilinear elliptic equations. The connection arises because the Nesterov ODE is the radial reduction in four dimensions of the system,

ΔU+∇f(U)=0,U:R4→Rn.\Delta U+\nabla f(U)=0,\qquad U:\mathbb{R}^4\to\mathbb{R}^n.

We provide a self-contained proof of Theorem 5.1 inspired by techniques from elliptic stability theory.

The organization of the rest of this paper is as follows. In Section 2, we recall the flow formulations of gradient descent and Nesterov’s accelerated method. In Section 3, we review the variational characterization of the Nesterov flow and compute the first and second variations of the associated Lagrangian action. In Section 4, we show that the local minimality of a Nesterov trajectory is governed by an associated Schrödinger operator, and define what we mean by an eventually locally minimizing trajectory. In Section 5, we obtain a precise characterization for power objectives. In Section 6, we give a complete PDE interpretation for our main result and in Appendix A we present omitted proofs.

Optimization Methods as Flows

In this section, we recall some basic facts about optimization methods. Specifically, we review the formulations of gradient descent and Nesterov’s accelerated method as solutions of certain ODEs. We refer to [Su et al., 2016] and references therein for detailed discussion. We present them here for completeness and to help set the stage for our results.

Gradient Flow

We first recall the basic convergence result for gradient flow, which can be viewed as the continuous-time analog of gradient descent. For completeness we include a proof of this result in Appendix A; see also [Su et al., 2016].

Theorem 2.1. Let f:Rn→Rf : \mathbb{R}^{n} \to\mathbb{R} be a convex, C1C^{1} function, with a finite minimum. Let X:[0,∞)→RnX : [0,\infty) \to\mathbb{R}^{n} be the solution of,

X˙(t)+∇f(X(t))=0,X(0)=x0.\dot{X}(t) + \nabla f(X(t)) = 0, \qquad X(0) = x_{0}.

Then, for every x⋆∈argmin⁡fx^{\star} \in\operatorname{argmin} f,

f(X(t))−f(x⋆)≤∥x0−x⋆∥22t,t>0.f(X(t)) - f(x^{\star}) \le\frac{\lVert x_{0} - x^{\star}\rVert^{2}}{2t}, \qquad t > 0.

In particular,

f(X(t))−f(x⋆)=O(1t).f(X(t)) - f(x^{\star}) = O\left(\frac{1}{t}\right).

Nesterov Flow

We now turn to the continuous-time model of Nesterov’s accelerated method introduced by Su et al. [2016]. Let f:Rn→Rf : \mathbb{R}^{n} \to\mathbb{R} be a C1C^{1}, convex function, with finite minimum. The associated Nesterov ODE is,

X¨(t)+3tX˙(t)+∇f(X(t))=0,t>0.(3)\ddot{X}(t) + \frac{3}{t}\dot{X}(t) + \nabla f(X(t)) = 0, \qquad t > 0. \tag*{(3)}

Because of the singular coefficient 3/t3/t, the natural solution concept is the regular solution satisfying,

X(0)=x0,X˙(0)=0.X(0) = x_{0}, \qquad\dot{X}(0) = 0.

Given the singularity at t=0t = 0, one needs to be careful when discussing the above initial value problem. The following lemmas show local and global existence of solutions to the Nesterov ODE. These results are standard and we defer the proofs to Appendix A.

Lemma 2.2 (Regular solution at $t = 0). Let f:Rn→Rf : \mathbb{R}^{n} \to\mathbb{R} be C1C^{1} with locally Lipschitz gradient. For every x0∈Rnx_{0} \in\mathbb{R}^{n}, there exists T>0T > 0 and a unique regular solution, X:[0,T]→RnX : [0,T] \to\mathbb{R}^{n} of,

X¨(t)+3tX˙(t)+∇f(X(t))=0,t>0,\ddot{X}(t) + \frac{3}{t}\dot{X}(t) + \nabla f(X(t)) = 0, \qquad t > 0,
X(0)=x0,X˙(0)=0.X(0) = x_{0}, \qquad\dot{X}(0) = 0.

Equivalently, XX is the unique continuous solution of the integral equation,

X(t)=x0−∫0tτ−3(∫0τs3∇f(X(s)) ds)dτ.X(t) = x_{0} - \int_{0}^{t} \tau^{-3}\left(\int_{0}^{\tau} s^{3}\nabla f(X(s))\,\mathrm{d}s\right)\mathrm{d}\tau.

Moreover,

X(t)=x0−t28∇f(x0)+o(t2)as t→0.X(t) = x_{0} - \frac{t^{2}}{8}\nabla f(x_{0}) + o(t^{2}) \qquad\text{as } t \to0.

The next lemma establishes global existence.

Lemma 2.3 (Global existence of regular Nesterov trajectories). Let f∈C2(Rn)f \in C^{2}(\mathbb{R}^{n}). Suppose that ff is bounded below. Then, for every x0∈Rnx_{0} \in\mathbb{R}^{n}, there exists a unique regular solution X:[0,∞)→RnX : [0,\infty) \to\mathbb{R}^{n} of Nesterov ODE with X(0)=x0X(0) = x_{0}, X˙(0)=0\dot{X}(0) = 0.

We now recall the basic convergence estimate for this flow. See for example [Su et al., 2016] for a proof.

Theorem 2.4. Let f:Rn→Rf:\mathbb{R}^{n}\to\mathbb{R} be a C1C^{1}, convex function, with finite minimum. Let X:[0,∞)→RnX:[0,\infty)\to\mathbb{R}^{n} be the regular solution of,

X¨(t)+3tX˙(t)+∇f(X(t))=0,X(0)=x0,X˙(0)=0.\ddot{X}(t)+\frac{3}{t}\dot{X}(t)+\nabla f(X(t))=0,\qquad X(0)=x_{0},\qquad\dot{X}(0)=0.

Then, for every x⋆∈argmin⁡fx^{\star}\in\operatorname{argmin} f,

f(X(t))−f(x⋆)≤2∥x0−x⋆∥2t2,t>0.(4)f(X(t))-f(x^{\star})\leq\frac{2\lVert x_{0}-x^{\star}\rVert^{2}}{t^{2}},\qquad t>0. \tag*{(4)}

In particular,

f(X(t))−f(x⋆)=O(1t2).f(X(t))-f(x^{\star})=O\left(\frac{1}{t^{2}}\right).

Variational Characterization of Nesterov

References

  1. [1]T. Aubin. Problèmes isopérimétriques et espaces de Sobolev. Journal of differential geometry, 11(4):573–598, 1976.DOI
  2. [2]A. Farina. On the classification of solutions of the Lane–Emden equation on unbounded domains of ℝ^N. Journal de mathématiques pures et appliquées, 87(5):537–561, 2007.DOI
  3. [3]M. Fazly and H. Shahgholian. Monotonicity formulas for coupled elliptic gradient systems with applications. Advances in Nonlinear Analysis, 9(1):479–495, 2020.arxiv.org/abs/1509.08153
  4. [4]B. Gidas and J. Spruck. Global and local behavior of positive solutions of nonlinear elliptic equations. Communications on Pure and Applied Mathematics, 34(4):525–598, 1981.DOI
  5. [5]M. I. Jordan. Dynamical, symplectic and stochastic perspectives on gradient-based optimization. In Proceedings of the international congress of mathematicians: Rio de Janeiro 2018, pages 523–549. World Scientific, 2018.DOI
  6. [6]D. D. Joseph and T. S. Lundgren. Quasilinear Dirichlet problems driven by positive sources. Archive for Rational Mechanics and Analysis, 49:241–269, 1973.DOI
  7. [7]N. Kawano, W.-M. Ni, and S. Yotsutani. A generalized Pohozaev identity and its applications. Journal of the Mathematical Society of Japan, 42(3):541–564, 1990.DOI

Paper details

vlnc:W_najr7xz2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-6 Astra (bare)

View statement
Looking for related papers…
Contents