\subsection{The \acl{RM} template}

Much of our analysis will revolve around iterative algorithms that can be cast as generalized \acl{RM} algorithms \citep{RM51} of the general form
\begin{equation}
\label{eq:RM}
\tag{RM}
\next
	= \curr
		+ \curr[\step] \bracks{ \vecfield(\curr) + \curr[\error]}
\end{equation}
where:
\begin{enumerate}
[]
\item
$\curr = (\curr[X],\curr[Y]) \in \points$ denotes the state of the algorithm at each stage $\run = \running$
\item
$\curr[\error]$ is an abstract error term described in detail below.
\item
$\curr[\step]$ is the method's step-size hyperparameter, and is typically of the form $\curr[\step] \propto 1/\run^{\pexp}$ for some $\pexp\geq0$. Throughout the paper, we will always assume $\sum_{\run} \curr[\step] = \infty$ and $\lim_{\run} \curr[\step] = 0$.
\end{enumerate}

In the above, the error term $\curr[\error]$ is generated \emph{after} $\curr$;
thus, by default, $\curr[\error]$ is not adapted to the history $\curr[\filter] \defeq \history(\init,\dotsc,\curr)$ of $\curr$.
For concision,


we will also write
\begin{equation}
\label{eq:signal}
\curr[\signal]
	= \vecfield(\curr)
		+ \curr[\error]


\end{equation}

so $\curr[\signal]$ can be seen as a noisy estimator of $\vecfield(\curr)$.
In more detail, to differentiate between ``random'' (zero-mean) and ``systematic'' (non-zero-mean) errors in $\curr[\signal]$ it will be convenient to further decompose the error process $\curr[\error]$ as
\begin{equation}
\label{eq:error}
\curr[\error]
	= \curr[\noise]
		+ \curr[\bias]
\end{equation}
where
$\curr[\bias] = \exof{\curr[\error] \given \curr[\filter]}$ represents the systematic component
and
$\curr[\noise] = \curr[\error] - \curr[\bias]$ captures the random, zero-mean part.
In view of all this, we will consider the following descriptors for $\curr[\error]$:

\begin{subequations}
\label{eq:signal-stats}
\begin{alignat}{3}
\label{eq:bias}
a)\quad
	&\textit{Bias:}
	&\quad
	\curr[\bbound]
		&= \exof{\norm{\curr[\bias]} \given \curr[\filter]}


	\\
b)\quad
\label{eq:variance}
	&\textit{Variance:}
	&\quad\curr[\sdev]^{2}
		&= \exof{\norm{\curr[\noise]}^{2} \vert \curr[\filter]}

	\hspace{20em}


\end{alignat}


\end{subequations}
Note that both $\curr[\bbound]$ and $\curr[\sdev]$ are random (conditioned on $\curr[\filter]$);
this will play an important part in the sequel.


\subsection{Specific algorithms} \label{subsec:specific}

In the rest of this section, we discuss how a wide range of algorithms used in the literature can be seen as special instances of our general \ac{RM} template.
\smallskip


\begin{algo}[\Acl{SGDA}]
\label{alg:SGDA}
The basic \ac{SGDA} algorithm \textendash\ also known as the \acli{AH} method \citep{AHU58} \textendash\ queries an \ac{SFO} and proceeds as:
\begin{equation}
\label{eq:SGDA}
\tag{SGDA}
\next
	= \curr
		+ \curr[\step] \orcl(\curr;\curr[\seed]),
\end{equation}
where $\curr[\seed] \in \seeds$ ($\run=\running$) is an \ac{iid} sequence of oracle seeds.
As such, \eqref{eq:SGDA} admits a straightforward \ac{RM} representation by taking $\curr[\error] = \curr[\noise] = \err(\curr;\curr[\seed])$ and $\curr[\bias] = 0$.
\endenv
\end{algo}
\smallskip


\begin{algo}[\Acl{PPM}]
\label{alg:PPM}
The (deterministic) \acdef{PPM} \cite{rockafellar1976monotone} is an implicit update rule of the form:
\begin{equation}
\label{eq:PPM}
\tag{PPM}
\next
	= \curr
		+ \curr[\step] \vecfield(\next).
\end{equation}
The \ac{RM} representation of \eqref{eq:PPM} is obtained by taking $\curr[\error] = \curr[\bias] =  \vecfield(\next) -  \vecfield(\curr)$ and $\curr[\noise] = 0$.
\endenv
\end{algo}
\smallskip


\begin{algo}[\Acl{SEG}]
\label{alg:SEG}
Since \eqref{eq:PPM} is only implicitly defined, one can rarely run it in practice. Nonetheless, it is possible to approximate \eqref{eq:PPM} by locally querying two (stochastic) gradients at each iteration \cite{Nem04}.


This can be achieved by the \acdef{SEG}:

\begin{equation}
\label{eq:SEG}
\tag{SEG}
\begin{alignedat}{2}
\lead
	&= \curr
		+ \curr[\step] \orcl(\curr;\curr[\seed]),


	\\
\next
	&= \curr
		+ \curr[\step] \orcl(\lead;\lead[\seed]).


\end{alignedat}
\end{equation}
To recast \eqref{eq:SEG} in the \acl{RM} framework, simply take
$\curr[\error] = \orcl(\lead;\lead[\seed]) - \vecfield(\curr)$,
\ie
$\curr[\noise] = \err(\lead;\lead[\seed])$
and
$\curr[\bias] = \vecfield(\lead) - \vecfield(\curr)$.
\endenv
\end{algo}
\smallskip


\begin{algo}[\Acl{OG} / \Acl{PEG}]
\label{alg:PEG}
Compared to \eqref{eq:SGDA}, the scheme \eqref{eq:SEG} involves two oracle queries per iteration, which is considerably more costly.
An alternative iterative method with a single oracle query per iteration was proposed by \citet{Pop80}:
\begin{equation}
\label{eq:PEG}
\tag{OG/PEG}
\begin{alignedat}{2}
\lead
	&= \curr
		+ \curr[\step] \orcl(\prelead;\prev[\seed]),
	\\
\next
	&= \curr
		+ \curr[\step] \orcl(\lead;\curr[\seed]).
\end{alignedat}
\end{equation}
\acl{PEG}\acused{PEG} has been rediscovered several times and is more widely known as the \acf{OG} method in the machine learning literature \cite{RS13-COLT,CYLM+12,DISZ18,HIMM19}.
In unconstrained problems, \eqref{eq:PEG} turns out to be equivalent to a number of other existing methods, including
``extrapolation from the past'' \cite{GBVV+19} and
reflected gradient \cite{malitsky2020forward}.

Its \acl{RM} representation is obtained by setting
$\curr[\error] = \orcl(\lead;\curr[\seed]) - \vecfield(\curr)$,
\ie
$\curr[\noise] = \err(\lead;\curr[\seed])$
and
$\curr[\bias] = \vecfield(\lead) - \vecfield(\curr)$.
\endenv
\end{algo}


\begin{algo}[\acl{KW}]
\label{alg:SPSA}
When first-order feedback is unavailable, a popular alternative is to obtain gradient information of $\minmax$ via zeroth-order observations \cite{liu2019min}.
This idea can be traced back to the seminal work of \citet{KW52} and the subsequent development of the \ac{SPSA} method by \citet{Spa92}.
In our setting, this leads to the recursion:
\begin{equation}
\label{eq:SPSA}
\tag{SPSA}
\begin{aligned}
\curr[\signal]
	&= \pm (\vdim/\curr[\mix])
		\, \minmax(\curr + \curr[\mix]\curr[\seed])
		\, \curr[\seed]
	\notag\\
\next
	&= \curr
		+ \curr[\step] \curr[\signal]
\end{aligned}
\end{equation}
where
$\curr[\mix] \searrow 0$ is a vanishing ``sampling radius'' parameter,
$\curr[\seed]$ is drawn uniformly at random from the composite basis $\seeds = \bvecs_{\minvars} \cup \bvecs_{\maxvars}$ of $\points = \minvars \times \maxvars$,
and
the ``$\pm$'' sign is equal to $-1$ if $\curr[\seed]\in\bvecs_{\minvars}$ and $+1$ if $\curr[\seed]\in\bvecs_{\maxvars}$.
Viewed this way, the interpretation of \eqref{eq:SPSA} as a \acl{RM} method is immediate;
furthermore, a straightforward calculation (that we defer to \cref{app:RM-APT}) shows that the sequence of gradient estimators $\curr[\signal]$ in \eqref{eq:SPSA} has $\curr[\bbound] = \bigoh(\curr[\mix])$ and $\curr[\sdev]^{2} = \bigoh(1/\curr[\mix]^{2})$.
\endenv
\end{algo}
\smallskip

Further examples that can be cast in the \ac{RM} framework include
the negative momentum method \cite{gidel2019negative},
generalized \ac{OG} schemes \cite{mokhtari2019unified},
the Chambolle-Pock algorithm \cite{chambolle2011first},
the ``prediction method'' of \citet{yadav2017stabilizing},
and
centripetal acceleration \cite{peng2020training};
the analysis is similar and we omit the details.
Certain scalable second-order methods can also be viewed as \ac{RM} schemes, but the driving vector field $\vecfield$ is no longer the gradient field of $\minmax$;
we discuss this in the supplement.


\subsection{Alternating updates and moving averages}


There are two extremely common heuristics for practitioners in applying min-max algorithms to real applications: alternating and averaging.
An \emph{alternating} algorithm for \eqref{eq:minmax} updates the $\minvar$ and $\maxvar$ variables sequentially (instead of simultaneously as in \cref{subsec:specific}). An \emph{averaged} algorithm takes the next state as a convex combination of $\curr$ and $\next$ in \eqref{eq:RM}, \cf \cite{karras2018progressive}.


An important feature of our framework is that it captures alternating and averaged algorithms in a seamless manner.
Indeed, introducing alternating updates or a moving average in \ac{RM} schemes results in another \ac{RM} scheme:

\begin{lemma}
\label{lem:averaging}
Let $
\next
	= \curr
		+ \curr[\step] \bracks{ \vecfield(\curr) +  \curr[\error] }$ be an \ac{RM} scheme where $\curr[\error] = \curr[\noise]+ \curr[\bias]$ as in \eqref{eq:error}. Then its $\alpha$-averaged version (where $0 < \alpha < 1$), defined as
\begin{equation}
\label{eq:avg-RM}
\tag{avg-RM}
\begin{alignedat}{2}
\next[\state']
	&=
		\curr[\state]
		+ \curr[\step] \bracks{ \vecfield(\curr[\state]) + \curr[\error]}, 
	\\
\next[\state]
	&=
		\alpha \next[\state'] + (1-\alpha)\curr
\end{alignedat}
\end{equation}

is also an \ac{RM} scheme: $
\next
	= \curr
		+ \alpha\curr[\step] \bracks{ \vecfield(\curr) +  \curr[\error] }$.
\end{lemma}

\begin{remark}
\cref{lem:averaging} can be easily adapted to the scenario where one only averages either the $\curr[\minstate]$ or $\curr[\maxstate]$ variable.
\end{remark}


\begin{figure*}[th!]
\centering
\footnotesize
\includegraphics[height=.3\textwidth]{Figures/SimpleGradient.pdf}
\hfill
\includegraphics[height=.3\textwidth]{Figures/SimpleFlow.pdf}
\hfill
\includegraphics[height=.3\textwidth]{Figures/SimpleProx.pdf}
\caption{Comparison of different RM schemes for bilinear games $\minmax(\minvar,\maxvar) = \minvar\maxvar$, $\minvar,\maxvar\in\R$.
~From left to right:
(\itshape a\upshape)
\acl{GDA};
(\itshape b\upshape)
the mean dynamics \eqref{eq:MD};
(\itshape c\upshape)
\acl{EG}.}

\label{fig:bilinear}
\end{figure*}


\begin{lemma}
\label{lem:alternating}
Let $
\next
	= \curr
		+ \curr[\step] \bracks{ \vecfield(\curr) +  \curr[\error] }$ be an \ac{RM} scheme where $\curr[\error] = \curr[\noise]+ \curr[\bias]$ as in \eqref{eq:error}. Then its alternating version, defined as
\begin{equation}
\label{eq:alt-RM}
\tag{alt-RM}
\begin{alignedat}{2}
\next[\minstate]
	&=
		\curr[\minstate]
		+ \curr[\step] &&\bracks{ \vecfield_{\minvar}(\curr[\minstate],\curr[\maxstate]) + \error_{\minvar,\run}}, 
	\\
\next[\maxstate]
	&=
		\curr[\maxstate]
		+ \curr[\step] && \bracks{ \vecfield_{\maxvar}( \next[\minstate],\curr[\maxstate]) + \error_{\maxvar,\run}}, 
\end{alignedat}
\end{equation}

is also an \ac{RM} scheme: $
\next
	= \curr
		+ \curr[\step] \bracks{ \vecfield(\curr) +  \curr[\noise] + \curr[\bias'] }$ where
\begin{equation} \nonumber
\curr[\bias'] = \curr[\bias]+  \begin{bmatrix}
0 \\
\vecfield_{\maxvar}( \next[\minstate],\curr[\maxstate]) - \vecfield_{\maxvar}( \curr[\minstate],\curr[\maxstate])
\end{bmatrix}.
\end{equation}


\end{lemma}


\begin{remark}\label{rmk:k1k2}
One can easily generalize \cref{lem:alternating} to the ``$(k_1,k_2)$-\ac{RM} schemes'' where one performs $k_1$ updates for $\minvar$ and then $k_2$ updates for $\maxvar$ (here $k_1,k_2 \in \N$ are arbitrary but fixed). The resulting scheme will still be an \ac{RM} scheme.
In particular, our framework captures the popular $(k_1,k_2) = (1,5)$ variant of \eqref{eq:SGDA} used in the seminal works of \citet{GPAM+14} and \citet{arjovsky2017wasserstein}.
In view of \crefrange{lem:averaging}{lem:alternating}, \cref{rmk:k1k2}, and a simple calculation (see \eqref{eq:bias-order}), \emph{all of our results on first-order methods (\eg \crefrange{alg:SGDA}{alg:PEG}) apply also to their averaging/alternating and the more general $(k_1,k_2)$ versions.}
\end{remark}
{"config": "arxiv", "file": "2006.09065/Algorithms.tex"}