Control theoretic approach to study accelerated first-order optimization algorithms
- Author(s): sun, boya
- Advisor(s): Solmaz, Kia
- et al.
Motivated by the fact that the gradient-based optimization algorithms can be studied from the perspective of limiting ordinary differential equations, we study the stability and convergence of the accelerated triple momentum (TM) algorithm by obtaining its ordinary differential representation and using Lyapunov stability analysis in the control theory. For unconstrained optimization problems with strongly convex cost, the TM algorithm has a proven faster convergence rate than the Nesterov’s accelerated gradient (NAG) method but with the same computational complexity. We show that similar to the NAG method to capture accurately the characteristics of the TM method, we use high-resolution modeling to obtain the ODE representation of the TM algorithm. We use Lyapunov analysis to investigate the stability and convergence behavior of the proposed high-resolution ODE representation of the TM algorithm. We show that this ODE model has the robustness to deviation from the parameters of the TM algorithm. We compare the rate of the ODE representation of the TM method with that of the NAG method to confirm its faster convergence. Also, inspired by the singular perturbation theory’s multi-time scale notions and ideas in control theory, we propose a systematic approach to construct a distributed implementation of the TM algorithm over network systems using its continuous-time representation. We study the correctness of this distributed implementation via the Lyapunov framework. A numerical example of a binary classification problem demonstrates the performance of these algorithms.