On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisation
Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Iman Shames
原文摘要
We establish a connection between the stability of discrete-time algorithms (DTAs) and continuous-time dynamical systems, in particular their $O(s^r)$-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 $O(s)$-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.
math.OC · cs.LG · eess.SY · math.NA