Monotone Inclusions, Acceleration, and Closed-Loop Control

Tianyi Lin () and Michael I. Jordan ()
Additional contact information
Tianyi Lin: Department of Electrical Engineering and Computer Science, University of California, Berkeley, California 94720
Michael I. Jordan: Department of Electrical Engineering and Computer Science, University of California, Berkeley, California 94720; Department of Statistics, University of California, Berkeley, California 94720

Mathematics of Operations Research, 2023, vol. 48, issue 4, 2353-2382

Abstract: 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 ⇉ 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 ) − 1 x ( 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 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 p th -order tensor algorithms for monotone inclusion problems, complementing the recent analysis for saddle point and VI problems.

Keywords: Primary: 37N40; 90C25; 90C60; 49M37; 68Q25; monotone inclusion; acceleration; closed-loop control system; feedback control; high-order tensor algorithm; iteration complexity (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1343 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:4:p:2353-2382

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().