← 研踪 PaperTrailarXiv:2603.01430 · v2
On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisation
首次提交 2026-03-02 12:22
版本更新 2026-11-16 07:08
雷达观测 2026-11-17 17:12
摘要
We establish a connection between the stability of discrete-time algorithms (DTAs) and continuous-time dynamical systems, in particular their -resolution ordinary differential equations (ODEs). We show that exponential stability of a common equilibrium transfers to the DTA whenever the one-step error is small relative to the distance to the equilibrium and the one-step Lyapunov decay. This condition is sharp in order, and one-step consistency alone is insufficient. The result is local and allows step-size-dependent ODEs and Lyapunov functions, covering -resolution ODEs whose decay rate vanishes as the step size tends to zero. Asymptotic stability is not inherited in general, but a comparison criterion and a checkable compatibility condition ensure it carries over for equilibria and compact sets. For resolution ODEs, joint regularity of the update map guarantees the required error bound. We apply the framework to two-timescale gradient descent ascent (TT-GDA), generalised extragradient, two-timescale proximal point, and (regularised) damped Newton, showing that for small step sizes and suitable parameters, every saddle point with invertible Hessian is locally exponentially stable for all but TT-GDA. For degenerate saddle points, the framework yields asymptotic stability and convergence rates.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-16 07:08 · 最新观测版本
On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisation
We establish a connection between the stability of discrete-time algorithms (DTAs) and continuous-time dynamical systems, in particular their -resolution ordinary differential equations (ODEs). We show that exponential stability of a common equilibrium transfers to the DTA whenever the one-step error is small relative to the distance to the equilibrium and the one-step Lyapunov decay. This condition is sharp in order, and one-step consistency alone is insufficient. The result is local and allows step-size-dependent ODEs and Lyapunov functions, covering -resolution ODEs whose decay rate vanishes as the step size tends to zero. Asymptotic stability is not inherited in general, but a comparison criterion and a checkable compatibility condition ensure it carries over for equilibria and compact sets. For resolution ODEs, joint regularity of the update map guarantees the required error bound. We apply the framework to two-timescale gradient descent ascent (TT-GDA), generalised extragradient, two-timescale proximal point, and (regularised) damped Newton, showing that for small step sizes and suitable parameters, every saddle point with invertible Hessian is locally exponentially stable for all but TT-GDA. For degenerate saddle points, the framework yields asymptotic stability and convergence rates.
查看此版本解读 →查看此版本原文 ↗