# An O(sr)-Resolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems

arXiv: https://arxiv.org/abs/2001.08826 · HTML: https://mlsanity.com/paper/2001.08826/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2020.

## Built on by (most cited first, 1 of 1)

- [Continuous-time Analysis for Variational Inequalities: An Overview and Desiderata](https://mlsanity.com/paper/2207.07105/) (2022)

## Abstract (arXiv)

There has been a long history of using ordinary differential equations (ODEs) to understand the dynamics of discrete-time algorithms (DTAs). Surprisingly, there are still two fundamental and unanswered questions: (i) it is unclear how to obtain a suitable ODE from a given DTA, and (ii) it is unclear the connection between the convergence of a DTA and its corresponding ODEs. In this paper, we propose a new machinery -- an O(sr)-resolution ODE framework -- for analyzing the behavior of a generic DTA, which (partially) answers the above two questions. The framework contains three steps: 1. To obtain a suitable ODE from a given DTA, we define a hierarchy of O(sr)-resolution ODEs of a DTA parameterized by the degree r, where s is the step-size of the DTA. We present a principal approach to construct the unique O(sr)-resolution ODEs from a DTA; 2. To analyze the resulting ODE, we propose the O(sr)-linear-convergence condition of a DTA with respect to an energy function, under which the O(sr)-resolution ODE converges linearly to an optimal solution; 3. To bridge the convergence properties of a DTA and its corresponding ODEs, we define the properness of an energy function and show that the linear convergence of the O(sr)-resolution ODE with respect to a proper energy function can automatically guarantee the linear convergence of the DTA. To better illustrate this machinery, we utilize it to study three classic algorithms -- gradient descent ascent (GDA), proximal point method (PPM) and extra-gradient method (EGM) -- for solving the unconstrained minimax problem minx∈RRn maxy∈ RRm L(x,y).