First-Order Constrained Optimization: Non-smooth Dynamical System Viewpoint
Sholom Schechtman, Daniil Tiapkin, Éric Moulines, Michael I. Jordan, Michael Muehlebach · IFAC-PapersOnLine · 2022
In a recent paper, Muehlebach and Jordan (2021a) proposed a novel algorithm for constrained optimization that uses original ideals from nonsmooth dynamical systems. In this work, we extend Muehlebach and Jordan (2021a) in several important directions: (i) we provide existence and convergence results for continuous-time trajectories under general conditions, and (ii) we provide a convergence guarantee for a perturbed version of the discrete-time version of the algorithm (covering stochastic gradient updates), for nonconvex and nonsmooth objective functions. Our analysis framework rationalizes the continuous-time and discrete-time cases, which not only provides an important intuition but could also enable convergence proofs for accelerated or Newton-like versions of our algorithm.