Nesterov’s Accelerated Gradient (NAG) algorithm is a popular algorithm that provides a faster convergence to the optimal solution of an optimization problem. Despite its popularity, the origin of this algorithm is still a conceptual mystery that has motivated the proposed control theoretic perspective. This letter has derived the second-order ODE for Nesterov’s Accelerated Gradient algorithm for strongly convex functions (NAG-SC) through the notions of manifold stabilization achieved with the recently introduced P&I approach and persistence of an invariant manifold. Furthermore, the contraction of the Nesterov’s flows under the control actions (i.e., Controlled Contraction (CC)) is also proved. The contraction of Nesterov’s flows not only ensures a stable numerical integration but also reveals the multiple potentials of the NAG-SC method that motivate its usefulness in machine learning and deep learning applications.
22 March 2024 in Results in Control and Optimization
A common theme in all the above areas is designing a dynamical system to accomplish desired objectives, possibly in some predefined optimal way. Since control theory advances the idea of suitably modifying the behavior of a dynamical system, this paper explores the role of control theory in designing efficient algorithms (or dynamical systems) related to problems surrounding the optimization framework, including constrained optimization, optimization-based control, and parameter estimation. This amalgamation of control theory with the above-mentioned areas has been made possible by the recently introduced paradigm of Passivity and Immersion (P&I) based control. The generality and working of P&I, as compared to the existing approaches in control theory, are best introduced through the example presented below.
Gradient Descent (GD) is a ubiquitous algorithm for finding the optimal solution to an optimization problem. For reduced computational complexity, the optimal solution x* of the optimization problem must be attained in a minimum number of iterations. For this objective, the paper proposes a genesis of an accelerated gradient algorithm through the controlled dynamical system perspective. The objective of optimally reaching the optimal solution x* where the gradient of ∇ f(x*) is zero with a given initial condition x(0) is achieved through control.