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

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).