Monotone Inclusions, Acceleration and Closed-Loop Control

Abstract

We propose and analyze a new dynamical system with a closed-loop control law in a Hilbert space $\mathcal{H}$, aiming to shed light on the acceleration phenomenon for \textit{monotone inclusion} problems, which unifies a broad class of optimization, saddle point and variational inequality (VI) problems under a single framework. Given $A:\mathcal{H}\rightrightarrows \mathcal{H}$ that is maximal monotone, we propose a closed-loop control system that is governed by the operator $I-(I+\lambda (t)A{)}^{-1}$, where a feedback law $\lambda (\cdot )$ is tuned by the resolution of the algebraic equation $\lambda (t)\Vert (I+\lambda (t)A{)}^{-1}x(t)-x(t){\Vert }^{p-1}=\theta$ for some $\theta >0$. Our first contribution is to prove the existence and uniqueness of a global solution via the Cauchy-Lipschitz theorem. We present a simple Lyapunov function for establishing the weak convergence of trajectories via the Opial lemma and strong convergence results under additional conditions. We then prove a global ergodic convergence rate of $O(t^{-(p+1)/2})$ in terms of a gap function and a global pointwise convergence rate of $O(t^{-p/2})$ in terms of a residue function. Local linear convergence is established in terms of a distance function under an error bound condition. Further, we provide an algorithmic framework based on the implicit discretization of our system in a Euclidean setting, generalizing the large-step HPE framework. Although the discrete-time analysis is a simplification and generalization of existing analyses for a bounded domain, it is largely motivated by the above continuous-time analysis, illustrating the fundamental role that the closed-loop control plays in acceleration in monotone inclusion. A highlight of our analysis is a new result concerning $p^{th}$-order tensor algorithms for monotone inclusion problems, complementing the recent analysis for saddle point and VI problems.

arXiv commentAccepted by Mathematics of Operations Research; 42 Pages

References in corpus (8)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• A Dynamical Systems Perspective on Nesterov Acceleration
• Near-optimal method for highly smooth convex optimization
• Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation