On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisation

• URL: http://arxiv.org/abs/2603.01430v1
• Date: Mon, 02 Mar 2026 04:22:26 GMT
• Title: On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisation
• Authors: Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Iman Shames,
• Abstract summary: We show that 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.<n>We apply this framework to analyse the limit point properties of several prominent algorithms.
• Score: 1.308951527147782
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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.

Related papers

• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• The Procrustean Bed of Time Series: The Optimization Bias of Point-wise Loss [53.542743390809356]
  This paper aims to provide a first-principles analysis of the Expectation of Optimization Bias (EOB)<n>Our analysis reveals a fundamental paradigm paradox: the more deterministic and structured the time series, the more severe the bias by point-wise loss function.<n>We present a concrete solution that simultaneously achieves both principles via DFT or DWT.
  arXiv  Detail & Related papers  (2025-12-21T06:08:22Z)
• Convergence of Stochastic Gradient Langevin Dynamics in the Lazy Training Regime [4.297070083645049]
  Continuoustime models provide insights into the training dynamics of optimization algorithms in deep learning.<n>We establish a non-asymptotic convergence analysis of gradient Langevin dynamics (SGLD)<n>We show that, under regularity conditions on the Hessian of the loss function, SGLD with multiplicative and state-dependent noise yields a non-degenerate kernel throughout the training process with high probability.
  arXiv  Detail & Related papers  (2025-10-24T08:28:53Z)
• Uniform-in-time convergence bounds for Persistent Contrastive Divergence Algorithms [0.29494468099506904]
  We propose a continuous-time formulation of persistent contrastive divergence (PCD) for maximum likelihood estimation (MLE) of unnormalised densities.<n>We are able to derive explicit bounds for the error between the PCD and the MLE solution for the model parameter.
  arXiv  Detail & Related papers  (2025-10-02T12:12:33Z)
• Enabling Local Neural Operators to perform Equation-Free System-Level Analysis [1.2468700211588881]
  Neural Operators (NOs) provide a powerful framework for computations involving physical laws.<n>We propose and implement a framework that integrates (local) NOs with advanced iterative numerical methods in the Krylov subspace.<n>We illustrate our framework via three nonlinear PDE benchmarks.
  arXiv  Detail & Related papers  (2025-05-05T01:17:18Z)
• Stochastic Optimization with Optimal Importance Sampling [49.484190237840714]
  We propose an iterative-based algorithm that jointly updates the decision and the IS distribution without requiring time-scale separation between the two.<n>Our method achieves the lowest possible variable variance and guarantees global convergence under convexity of the objective and mild assumptions on the IS distribution family.
  arXiv  Detail & Related papers  (2025-04-04T16:10:18Z)
• Integral regularization PINNs for evolution equations [4.5305564316166675]
  We propose a novel approach that enhances temporal accuracy by incorporating an integral-based residual term into the loss function.<n>This method divides the entire time interval into smaller sub-intervals and enforces constraints over these sub-intervals, thereby improving the resolution and correlation of temporal dynamics.<n> Numerical experiments on benchmark problems demonstrate that IR-PINNs outperform original PINNs and other state-of-the-art methods in capturing long-time behaviors.
  arXiv  Detail & Related papers  (2025-03-31T05:02:59Z)
• Convergence of mean-field Langevin dynamics: Time and space discretization, stochastic gradient, and variance reduction [49.66486092259376]
  The mean-field Langevin dynamics (MFLD) is a nonlinear generalization of the Langevin dynamics that incorporates a distribution-dependent drift. Recent works have shown that MFLD globally minimizes an entropy-regularized convex functional in the space of measures. We provide a framework to prove a uniform-in-time propagation of chaos for MFLD that takes into account the errors due to finite-particle approximation, time-discretization, and gradient approximation.
  arXiv  Detail & Related papers  (2023-06-12T16:28:11Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem [27.09339991866556]
  We show that ODE searches for optimal control for an unknown computation system by directly searching over the corresponding space of controllers. We take a step towards demystifying the performance and efficiency of such methods by focusing on the gradient-flow dynamics set of stabilizing feedback gains and a similar result holds for the forward disctization of the ODE.
  arXiv  Detail & Related papers  (2019-12-26T16:56:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.