论文标题
关于单调方程问题的全球加速度的连续时间观点
A Continuous-Time Perspective on Global Acceleration for Monotone Equation Problems
论文作者
论文摘要
我们提出了一个新框架，以设计和分析加速方法，以解决一般单调方程（ME）问题$ f（x）= 0 $。传统方法包括广义陡峭的下降方法和牛顿型方法不可推动的方法。如果$ f $是统一的单调，并且两次可微分，则这些方法实现了局部收敛速率，而后者的方法是通过线路搜索和超平面投影的全球收敛性。但是，这些方法的全球速率是未知的。可以应用变分的不等式方法来产生以$ \ | f（x）\ | $表示的全局速率，但这些结果仅限于一阶方法和Lipschitz连续操作员。尚不清楚如何使用高阶Lipschitz连续性获得全球加速度。本文采用连续的时间观点，将加速方法视为动态系统的离散化。我们的贡献是提出加速的重新梯度系统，并证明它们等于闭环控制系统。基于此连接，我们建立了解决方案轨迹的属性。此外，我们提供了从系统离散化获得的统一算法框架，该框架与两个近似子例程一起产生了现有的高阶方法和新的一阶方法。我们证明，$ p^{th} $ - 订单方法在$ o（k^{ - p/2}）$中达到$ \ | f（x）\ | $ f $是$ p^{th} $ - 订购lipschitz的连续和第一个订单的速度相同的lips lips $ p^$ p^^$ p^p^p^p^p^^$ p^ploss of $ o（k^{ - p/2}）$。如果$ f $强烈单调，则重新启动的版本在$ p \ geq 2 $时使用订单$ p $实现本地融合。我们的离散时间分析在很大程度上是由连续的时间分析引起的，并证明了恢复梯度在解决我问题的全球加速中起着的基本作用。
We propose a new framework to design and analyze accelerated methods that solve general monotone equation (ME) problems $F(x)=0$. Traditional approaches include generalized steepest descent methods and inexact Newton-type methods. If $F$ is uniformly monotone and twice differentiable, these methods achieve local convergence rates while the latter methods are globally convergent thanks to line search and hyperplane projection. However, a global rate is unknown for these methods. The variational inequality methods can be applied to yield a global rate that is expressed in terms of $\|F(x)\|$ but these results are restricted to first-order methods and a Lipschitz continuous operator. It has not been clear how to obtain global acceleration using high-order Lipschitz continuity. This paper takes a continuous-time perspective where 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. Based on this connection, we establish the properties of solution trajectories. Moreover, we provide a unified algorithmic framework obtained from discretization of our system, which together with two approximation subroutines yields both existing high-order methods and new first-order methods. We prove that the $p^{th}$-order method achieves a global rate of $O(k^{-p/2})$ in terms of $\|F(x)\|$ if $F$ is $p^{th}$-order Lipschitz continuous and the first-order method achieves the same rate if $F$ is $p^{th}$-order strongly Lipschitz continuous. If $F$ is strongly monotone, the restarted versions achieve local convergence with order $p$ when $p \geq 2$. 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.
