Inducing Uniform Asymptotic Stability in Non-Autonomous Accelerated Optimization Dynamics via Hybrid Regularization

Abstract

There have been many recent efforts to study accelerated optimization algorithms from the perspective of dynamical systems. In this paper, we focus on the robustness properties of the time-varying continuous-time version of these dynamics. These properties are critical for the implementation of accelerated algorithms in feedback-based control and optimization architectures. We show that a family of dynamics related to the continuous-time limit of Nesterov's accelerated gradient method can be rendered unstable under arbitrarily small bounded disturbances. Indeed, while solutions of these dynamics may converge to the set of optimizers, in general, this set may not be uniformly asymptotically stable. To induce uniformity, and robustness as a byproduct, we propose a framework where we regularize the dynamics by using resetting mechanisms that are modeled by well-posed hybrid dynamical systems. For these hybrid dynamics, we establish uniform asymptotic stability and robustness properties, as well as convergence rates that are similar to those of the non-hybrid dynamics. We finish by characterizing a family of discretization mechanisms that retain the main stability and robustness properties of the hybrid algorithms.

arXiv commentTo appear at the 2019 IEEE Conference on Decision and Control

References in corpus (6)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• A Lyapunov Analysis of Momentum Methods in Optimization
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Direct Runge-Kutta Discretization Achieves Acceleration
• PARNES: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals