Continuous-Time Accelerated Methods via a Hybrid Control Lens
For optimization researchers, this work offers a new control-theoretic framework for designing fast methods, though it is incremental as it builds on existing dynamical system viewpoints.
The paper proposes two classes of accelerated optimization methods using hybrid control systems to achieve a pre-specified exponential convergence rate under the Polyak–Łojasiewicz inequality, with Zeno-free trajectories and a discretization mechanism.
Treating optimization methods as dynamical systems can be traced back centuries ago in order to comprehend the notions and behaviors of optimization methods. Lately, this mind set has become the driving force to design new optimization methods. Inspired by the recent dynamical system viewpoint of Nesterov's fast method, we propose two classes of fast methods, formulated as hybrid control systems, to obtain pre-specified exponential convergence rate. Alternative to the existing fast methods which are parametric-in-time second order differential equations, we dynamically synthesize feedback controls in a state-dependent manner. Namely, in the first class the damping term is viewed as the control input, while in the second class the amplitude with which the gradient of the objective function impacts the dynamics serves as the controller. The objective function requires to satisfy the so-called Polyak--Łojasiewicz inequality which effectively implies no local optima and a certain gradient-domination property. Moreover, we establish that both hybrid structures possess Zeno-free solution trajectories. We finally provide a mechanism to determine the discretization step size to attain an exponential convergence rate.