English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

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 howto obtain a \emph{suitable} ODE from a given DTA, and (ii) it is unclear theconnection between the convergence of a DTA and its corresponding ODEs. In thispaper, we propose a new machinery -- an $O(s^r)$-resolution ODE framework --for analyzing the behavior of a generic DTA, which (partially) answers theabove two questions. The framework contains three steps: 1. To obtain asuitable ODE from a given DTA, we define a hierarchy of $O(s^r)$-resolutionODEs of a DTA parameterized by the degree $r$, where $s$ is the step-size ofthe DTA. We present a principal approach to construct the unique$O(s^r)$-resolution ODEs from a DTA; 2. To analyze the resulting ODE, wepropose the $O(s^r)$-linear-convergence condition of a DTA with respect to anenergy function, under which the $O(s^r)$-resolution ODE converges linearly toan optimal solution; 3. To bridge the convergence properties of a DTA and itscorresponding ODEs, we define the properness of an energy function and showthat the linear convergence of the $O(s^r)$-resolution ODE with respect to aproper energy function can automatically guarantee the linear convergence ofthe DTA. To better illustrate this machinery, we utilize it to study threeclassic algorithms -- gradient descent ascent (GDA), proximal point method(PPM) and extra-gradient method (EGM) -- for solving the unconstrained minimaxproblem $\min_{x\in\RR^n} \max_{y\in \RR^m} L(x,y)$.

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