2021/11/15 by Lin, Tianyi, Jordan, Michael. I.
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2111.08093
We propose and analyze a new dynamical system with a closed-loop control law in a Hilbert space H, aiming to shed light on the acceleration phenomenon for monotone inclusion problems, which unifies a broad class of optimization, saddle point and variational inequality (VI) problems under a single framework. Given A: H \rightrightarrows H that is maximal monotone, we propose a closed-loop control system that is governed by the operator I - (I + λ(t)A)-1, where a feedback law λ(⋅) is tuned by the resolution of the algebraic equation λ(t)‖(I + λ(t)A)-1x(t) - x(t)‖p-1 = θ for some θ> 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 pth-order tensor algorithms for monotone inclusion problems, complementing the recent analysis for saddle point and VI problems.