A Control-Theoretic Perspective on Optimal High-Order Optimization

Abstract

We provide a control-theoretic perspective on optimal tensor algorithms for minimizing a convex function in a finite-dimensional Euclidean space. Given a function $\Phi :{\mathbb{R}}^d\to \mathbb{R}$ that is convex and twice continuously differentiable, we study a closed-loop control system that is governed by the operators $\nabla \Phi$ and ${\nabla }^2\Phi$ together with a feedback control law $\lambda (\cdot )$ satisfying the algebraic equation $(\lambda (t){)}^p\Vert \nabla \Phi (x(t)){\Vert }^{p-1}=\theta$ for some $\theta \in (0,1)$. Our first contribution is to prove the existence and uniqueness of a local solution to this system via the Banach fixed-point theorem. We present a simple yet nontrivial Lyapunov function that allows us to establish the existence and uniqueness of a global solution under certain regularity conditions and analyze the convergence properties of trajectories. The rate of convergence is $O(1/t^{(3p+1)/2})$ in terms of objective function gap and $O(1/t^{3p})$ in terms of squared gradient norm. Our second contribution is to provide two algorithmic frameworks obtained from discretization of our continuous-time system, one of which generalizes the large-step A-HPE framework and the other of which leads to a new optimal $p$-th order tensor algorithm. While our discrete-time analysis can be seen as a simplification and generalization of~\citet{Monteiro-2013-Accelerated}, it is largely motivated by the aforementioned continuous-time analysis, demonstrating the fundamental role that the feedback control plays in optimal acceleration and the clear advantage that the continuous-time perspective brings to algorithmic design. A highlight of our analysis is that we show that all of the $p$-th order optimal tensor algorithms that we discuss minimize the squared gradient norm at a rate of $O(k^{-3p})$, which complements the recent analysis.

Accepted by Mathematical Programming Series A; 45 pages

References in corpus (17)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$
• A Lyapunov Analysis of Momentum Methods in Optimization
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• Direct Runge-Kutta Discretization Achieves Acceleration
• On damped second-order gradient systems
• Acceleration via Symplectic Discretization of High-Resolution Differential Equations
• A Dynamical Systems Perspective on Nesterov Acceleration
• Hamiltonian Descent Methods
• On Symplectic Optimization
• Near-optimal method for highly smooth convex optimization
• Accelerating Rescaled Gradient Descent: Fast Optimization of Smooth Functions
• Near-Optimal Hyperfast Second-Order Method for convex optimization and its Sliding
• Higher-Order Accelerated Methods for Faster Non-Smooth Optimization
• Nesterov's acceleration and Polyak's heavy ball method in continuous time: convergence rate analysis under geometric conditions and perturbations

Cited by in corpus (2)

• On complexity and convergence of high-order coordinate descent algorithms for smooth nonconvex box-constrained minimization
• A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate