揭示离散优化算法与连续微分方程的稳定性关联,指导算法设计。
On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisation
- 通过高阶精度微分方程建立离散算法与连续系统的稳定性联系。
- 证明在步长足够小时,连续系统稳定则离散系统也稳定。
- 适用于多类极小极大优化算法,放宽了传统假设限制。
本文建立了离散时间算法(DTA)与其通过 $ O(s^r) $-分辨率常微分方程(ODE)导出的连续时间动力系统之间稳定性性质的严格关联。我们证明,若离散与连续系统满足温和误差假设,则当连续时间动力学在共同平衡点处呈指数稳定时,只要步长足够小,该平衡点对离散时间动力学亦为指数稳定。该结果进一步推广至共同紧致不变集。我们还证明,若某平衡点对 $ O(s^r) $-分辨率 ODE 是指数稳定的,则其对相应 DTA 亦是。我们将该框架应用于分析多种主流优化算法——包括两尺度梯度下降-上升(TT-GDA)、广义外梯度(GEG)、两尺度近端点法(TT-PPM)、阻尼牛顿法(DN)、正则化阻尼牛顿法(RDN)及雅可比方法(JM)——通过研究其 $ O(1) $ 和 $ O(s) $-分辨率 ODE。结果表明,在合理超参数设置下,目标函数的鞍点集是 GEG、TT-PPM、DN 与 RDN 的指数稳定平衡点子集。我们通过直接分析分辨率 ODE,放松了常见的海森矩阵不变性假设,拓展了结论适用范围。数值实验验证了理论结果。
原文摘要 · Abstract (English)
This work establishes a rigorous connection between stability properties of discrete-time algorithms (DTAs) and corresponding continuous-time dynamical systems derived through $ O(s^r) $-resolution ordinary differential equations (ODEs). We show that for discrete- and continuous-time dynamical systems satisfying a mild error assumption, exponential stability of a common equilibrium with respect to the continuous time dynamics implies exponential stability of the corresponding equilibrium for the discrete-time dynamics, provided that the step size is chosen sufficiently small. We extend this result to common compact invariant sets. We prove that if an equilibrium is exponentially stable for the $ O(s^r) $-resolution ODE, then it is also exponentially stable for the associated DTA. We apply this framework to analyse the limit point properties of several prominent optimisation algorithms, including Two-Timescale Gradient Descent--Ascent (TT-GDA), Generalised Extragradient (GEG), Two-Timescale Proximal Point (TT-PPM), Damped Newton (DN), Regularised Damped Newton (RDN), and the Jacobian method (JM), by studying their $ O(1) $- and $ O(s) $-resolution ODEs. We show that under a proper choice of hyperparameters, the set of saddle points of the objective function is a subset of the set of exponentially stable equilibria of GEG, TT-PPM, DN, and RDN. We relax the common Hessian invariance assumption through direct analysis of the resolution ODEs, broadening the applicability of our results. Numerical examples illustrate the theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。