Monotone Inclusions, Acceleration, and Closed-Loop Control

• 成果类型: Article
• 署名作者: Lin, Tianyi; Jordan, Michael I.
• 署名单位: University of California System; University of California Berkeley; University of California System; University of California Berkeley
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1343
• 发表日期: 2023
• 页码: 2353-2382
• 关键词: proximal extragradient method; convergence rate analysis; inertial dynamics; variational-inequalities; convex-optimization; saddle-point; asymptotic-behavior; WEAK-CONVERGENCE; Newton method; algorithms

摘要

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 an operator A : H paired right arrows 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(center dot) is tuned by the resolution of the algebraic equation lambda(t)||(I + lambda(t)A)(-1)x(t) - x(t)||(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 hybrid proximal extragradient framework. Even though the discrete-time analysis is a simplification and generalization of existing analyses for a bounded domain, it is largely motivated by the aforementioned 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.