Full Text: PDF
DOI: 10.23952/cot.2024.40
Received December 6, 2023; Accepted January 16, 2024; Published online October 15, 2024
Abstract. We propose a new framework to design and analyze accelerated methods that solve general monotone equation (ME) problems in the form of where
is a continuous and monotone operator. Traditional approaches include generalized steepest descent methods [37] and inexact Newton-type methods [86]. If
is uniformly monotone and twice differentiable, the former methods are shown to achieve local linear convergence while the latter methods attain a guarantee of local superlinear convergence. The latter methods are also globally convergent thanks to line search and hyperplane projection. However, a global convergence rate is unknown for these methods. Since the ME problems are equivalent to the unconstrained variational inequality (VI) problems, VI methods can be applied to yield a global convergence rate that is expressed in terms of the residue function
. Indeed, the optimal rate among first-order methods is
if
is Lipschitz continuous and was achieved by an anchored extragradient method [94]. However, these existing results are restricted to first-order methods and ME problems with a Lipschitz continuous operator. It has not been clear how to obtain global acceleration using high-order Lipschitz continuity of
. We take a continuous-time perspective in which accelerated methods are viewed as the discretization of dynamical systems. Our contribution is to propose accelerated rescaled gradient systems and prove that they are equivalent to closed-loop control systems [46]. Based on this connection, we establish the desired properties of solution trajectories of our new systems. Moreover, we provide a unified algorithmic framework obtained from discretization of continuous-time systems, which together with two different approximation subroutines yields both the existing high-order methods [47] and new first-order methods. This highlights the advantage of our new systems over the closed-loop control systems since the resulting methods do not require line search at each iteration. We prove that the
-order method achieves a global rate of
in terms of
if
is
-order Lipschitz continuous and the first-order method can achieve the same rate if
is
-order strongly Lipschitz continuous. If
is further strongly monotone, the restarted versions of these methods achieve local convergence with order
when
. Our discrete-time analysis is largely motivated by the continuous-time analysis and demonstrates the fundamental role that rescaled gradients play in global acceleration for solving ME problems.
How to Cite this Article:
T. Lin, M. I. Jordan, A continuous-time perspective on global acceleration for monotone equation problems, Commun. Optim. Theory 2024 (2024) 40.