SDEs for Minimax Optimization

Enea Monzio Compagnoni Antonio Orvieto Hans Kersting

Department of Mathematics and Computer Science University of Basel ELLIS
Institute Tübingen MPI for Intelligent Systems Tübingen AI Center Yahoo!
Research

Frank Norbert Proske Aurelien Lucchi

Department of Mathematics University of Oslo Department of Mathematics and
Computer Science University of Basel

###### Abstract

Minimax optimization problems have attracted a lot of attention over the past
few years, with applications ranging from economics to machine learning. While
advanced optimization methods exist for such problems, characterizing their
dynamics in stochastic scenarios remains notably challenging. In this paper,
we pioneer the use of stochastic differential equations (SDEs) to analyze and
compare Minimax optimizers. Our SDE models for Stochastic Gradient Descent-
Ascent, Stochastic Extragradient, and Stochastic Hamiltonian Gradient Descent
are provable approximations of their algorithmic counterparts, clearly
showcasing the interplay between hyperparameters, implicit regularization, and
implicit curvature-induced noise. This perspective also allows for a unified
and simplified analysis strategy based on the principles of Itô calculus.
Finally, our approach facilitates the derivation of convergence conditions and
closed-form solutions for the dynamics in simplified settings, unveiling
further insights into the behavior of different optimizers.

##  1 INTRODUCTION

Minimax optimization plays a fundamental role in decision theory, game theory,
and machine learning (Goodfellow et al.,, 2016). The problem it addresses is
finding the solution of the following optimization problem:

$\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}\left[f(x,y):=\frac{1}{N}\sum_{i=1}^{N}f_{i}(x,y)\right],$
(1)

where $f,f_{i}:\mathcal{X}\times\mathcal{Y}\to{\mathbb{R}}$ for $i=1,\dots,N$.
In machine learning, $f$ is an empirical risk function where $f_{i}$ is the
contribution of the $i$-th data point of the training data. In this notation,
$(x,y)\in\mathcal{X}\times\mathcal{Y}$ is a vector of trainable parameters and
$N$ is the size of the dataset. The goal is to find optimal saddle points
$(\mathrm{x}^{*},\mathrm{y}^{*})$ such that

$f\left(\mathrm{x}^{*},\mathrm{y}\right)\leq
f\left(\mathrm{x}^{*},\mathrm{y}^{*}\right)\leq
f\left(\mathrm{x},\mathrm{y}^{*}\right)\quad\forall\mathrm{x}\in\mathcal{X},\quad\forall\mathrm{y}\in\mathcal{Y}.$

The most intuitive algorithm to solve Eq. (1) is Gradient Descent Ascent
(GDA). However, its updates are computationally expensive for large datasets.
Therefore, a common choice is to use mini-batches to approximate the
gradients, which gives rise to Stochastic Gradient Descent Ascent (SGDA).
Unfortunately, it is known that both GDA and SGDA do not converge on
relatively simple landscapes such as $f(x,y)=xy$ for $(x,y)\in{\mathbb{R}}$.
This led to the design of alternative optimizers such as Extragradient (EG)
(Korpelevich,, 1976) and Hamiltonian GD (Balduzzi et al.,, 2018). While these
methods exhibit more favorable convergence guarantees compared to SGDA, they
are relatively complex to study and some of their properties are still not
well understood, especially in a stochastic setting.

In this paper, we leverage continuous-time models in the form of stochastic
differential equations (SDEs) to study these minimax optimizers. SDEs have
recently become popular in the minimization community: They provide a unified
and simplified analysis strategy rooted in Itô calculus which facilitates the
derivation of novel insights about the discrete algorithms, see e.g. (Su et
al.,, 2014; Li et al.,, 2017). It is worth mentioning that the interest in
applying SDEs to minimax problems has been a topic of prior research
discussions (Chavdarova et al.,, 2022). Following the framework of Li et al.,
(2017) for minimization, our work provides the first _formal_ derivation —
rooted in the theory of weak approximation (Mil’shtein,, 1986) — of the SDEs
of SGDA,

$\displaystyle z_{k+1}=z_{k}-\eta F_{\gamma_{k}}(z_{k}),$ (2)

SEG,

$\displaystyle z_{k+1}=z_{k}-\eta F_{\gamma^{1}_{k}}(z_{k}-\rho
F_{\gamma^{2}_{k}}(z_{k})),$ (3)

and SHGD

$z_{k+1}=z_{k}-\eta\nabla\mathcal{H}_{\gamma_{k}^{1},\gamma_{k}^{2}}(z_{k}),$
(4)

where $F$ is the drift field and $\mathcal{H}$ the Hamiltonian:

$\displaystyle
F_{\gamma}(z)=F_{\gamma}(x,y):=(\nabla_{x}f_{\gamma}(x,y),-\nabla_{y}f_{\gamma}(x,y)),$
(5)
$\displaystyle\mathcal{H}_{\gamma^{1},\gamma^{2}}(z):=\frac{F_{\gamma^{1}}^{\top}(z)F_{\gamma^{2}}(z)}{2}.$
(6)

Above, $\eta\in{\mathbb{R}}^{>0}$ is the stepsize and $\rho\in{\mathbb{R}}$ is
the extra stepsize of SEG111We also support the cases where the stepsizes and
extra steps depend on time, e.g. $\eta_{k}$ and $\rho_{k}$, as well as depend
on the coordinates, e.g. $\eta=\left(\eta_{1},\cdots,\eta_{d}\right)$.. The
mini-batches $\\{\gamma^{j}_{k}\\}$ are modelled as i.i.d. random variables
uniformly distributed on $\\{1,\cdots,N\\}$, and of size $B\geq 1$.

Formally, these continuous-time models are weak approximations, i.e.
approximations in distribution, of their respective discrete-time algorithms.
We will exploit these models to derive novel insights into the convergence
behavior, the effect of the noise and the curvature of the landscape, or the
role of hyper-parameters such as the extra stepsize $\rho$ appearing in SEG.

##### Contributions.

  * •

We provide the first formal derivation of the SDE models of popular minimax
optimizers. Then, we use them to make the following additional contributions:

    1. 1.

Moderate Exploration regime. If $\rho=\mathcal{O}(\eta)$, we show that SEG
essentially behaves like SGDA;

    2. 2.

Aggressive Exploration regime (Hsieh et al.,, 2020). For
$\rho=\mathcal{O}(\sqrt{\eta})$, the dynamics of SEG can be interpreted as
that of SGDA on an implicitly regularized vector field with additional
implicit curvature-induced noise;

    3. 3.

SHGD uses explicit curvature-based information. Thus, it has an explicit
curvature-induced noise;

    4. 4.

We characterize the evolution of the Hamiltonian under the dynamics of SEG and
SHGD;

    5. 5.

We use the latter to derive convergence conditions for SEG and SHGD on a wide
class of functions.

  * •

For Bilinear Games with different noise structures:

    1. 1.

We explicitly solve the differential equation of the Hamiltonian, thus
elucidating the interplay of all hyperparameters in determining the speed of
convergence (or divergence) of these methods;

    2. 2.

We provide necessary and sufficient conditions for stepsize schedulers to
recover convergence.

  * •

We explicitly solve the SDEs for some Quadratic Games, meaning that we derive
the first closed-form formula for the dynamics of SEG and SHGD on these
landscapes. This allows for a 1-to-1 comparison of the two optimizers,
particularly of their first and second moments. One key takeaway of this
comparison is that selecting $\rho$ is a matter of trade-off between the speed
of convergence and asymptotic optimality: Our formulas show how a suitable
choice of $\rho$ allows SEG to match (or outperform) SHGD w.r.t. convergence
speed but negatively impacts its optimality (the iterates converge to a larger
neighborhood of the optimum). Interestingly, the curvature determines whether
SEG or SHGD is faster at converging as well as more suboptimal. Importantly,
we provide the first experimental and theoretical evidence that negative
$\rho$ might be advisable for certain landscapes.

  * •

Finally, we present extensive experiments on various relevant minimax
problems: these are meant to verify that each formula derived from our SDEs
correctly describes the behavior of the respective discrete-time algorithms.
Figure 1 offers a preliminary glimpse at the accuracy of the SDEs
approximations.

(a)  (b)

(c)  (d)

Figure 1: Empirical validation of Theorem 3.4 and 3.6: The trajectories of the
simulated SDEs match those of the respective algorithms averaged over $5$ runs
- That of SGDA gets trapped in limit cycles as well (Top Left); That of SHGD
converges to the optimum of a highly nonlinear landscape (Bottom Left); The
SDE of SGDA would not be a good model for SEG (Top Right); The SDEs and the
optimizers move along the trajectory at the same speed (Bottom Right). For a
description of the landscapes and of the simulation settings for the SDEs, see
Appendix G.

##  2 RELATED WORKS

We start by discussing existing continuous-time analysis for minimax
optimization and related applications. For related works regarding SGDA, SEG,
SHGD, and bilinear games, we refer the reader to Appendix A.

##### ODE Approximations and Applications.

Several works use continuous-time models to describe the dynamics of minimax
optimizers. First, Ryu et al., (2019) informally derived ODEs to study
Stochastic Gradient Methods with Optimism and Anchoring. Then, Lu, (2022)
formally showed that different saddle-point optimizers yield the same ODE and
derived High-Resolution (Ordinary) Differential Equations (HRDEs) to provide
convergence conditions on a wide class of problems. Similarly, Chavdarova et
al., (2023) derived HRDEs as well and established the convergence of certain
methods in continuous time on bilinear games. Finally, Hsieh et al., (2021)
modeled a wide class of zeroth- and first-order minimax algorithms with ODEs
and proved that they may be subject to inescapable convergence failures,
meaning that they could get attracted by spurious attractors. Unfortunately,
their approach based on Robbins–Monro templates cannot handle ergodic
averages, second-order methods, adaptive methods, and constant stepsizes.

##### SDE Approximations and Applications.

(Li et al.,, 2017) first proposed a formal theoretical framework to derive
SDEs to appropriately capture the intrinsic stochasticity of stochastic
optimizers. These SDEs can be understood as weak approximations of stochastic
gradient algorithms (See Definition 3.2). SDEs open to a variety of concrete
applications that include _stochastic optimal control_ to select the stepsize
(Li et al.,, 2017, 2019) or the batch size (Zhao et al.,, 2022) and _scaling
rules_ (Malladi et al.,, 2022) to adjust the optimization hyperparameters
w.r.t. the batch size. Additionally, SDEs give access to the fine-grained
structure of the interaction between stochasticity and curvature. For example,
the study of _escape times_ of SGD from minima of different sharpness (Xie et
al.,, 2021), the factors influencing the minima found by SGD Jastrzebski et
al., (2018), the convergence bounds for mini-batch SGD and SVRG derived in
Orvieto and Lucchi, (2019), and the fundamental interplay between noise and
curvature of the landscape for SAM (Compagnoni et al.,, 2023). For more
references, see (Kushner and Yin,, 2003; Ljung et al.,, 2012; Chen et al.,,
2015; Mandt et al.,, 2015; Chaudhari and Soatto,, 2018; Zhu et al.,, 2019; He
et al.,, 2018; An et al.,, 2020). A gentle introduction to SDEs is provided in
Appendix B.2

##  3 RESULTS & INSIGHTS: THE SDEs

This section provides the general formulations of the SDEs of SGDA (Theorem
3.3), SEG (Theorem 3.4), and SHGD (Theorem 3.6). Due to the technical nature
of the analysis, we refer the reader to the appendix for the complete formal
statements and proofs.

######  Assumption 3.1.

We assume that

  1. 1.

$\nabla f,\nabla f_{i}$ satisfy a Lipschitz condition: $\exists L>0$ s.t.
$|\nabla f(u)-\nabla f(v)|+\sum_{i=1}^{N}\left|\nabla f_{i}(u)-\nabla
f_{i}(v)\right|\leq L|u-v|$;

  2. 2.

$f,f_{i}$ and their partial derivatives up to order 7 have polynomial growth;

  3. 3.

$\nabla f,\nabla f_{i}$ satisfy a linear growth condition: $\exists M>0$ s.t.
$|\nabla f(z)|+\sum_{i=1}^{N}\left|\nabla f_{i}(z)\right|\leq M(1+|z|).$

######  Definition 3.2 (Weak Approximation).

A continuous-time stochastic process $\\{Z_{t}\\}_{t\in[0,T]}$ is an order
$\alpha$ weak approximation (or $\alpha$-order SDE) of a discrete stochastic
process $\\{z_{k}\\}_{k=0}^{\left\lfloor T/\eta\right\rfloor}$ if for every
polynomial growth function $g$, there exists a positive constant $C$,
independent of the stepsize $\eta$, such that $\max_{k=0,\ldots,\left\lfloor
T/\eta\right\rfloor}\left|{\mathbb{E}}g\left(z_{k}\right)-{\mathbb{E}}g\left(Z_{k\eta}\right)\right|\leq
C\eta^{\alpha}.$

This definition comes from the field of numerical analysis of SDEs, see
Mil’shtein, (1986). When $g(z)=\lVert z\rVert^{j}$, the bound restricts the
disparity between the $j$-th moments of the discrete and the continuous
process.

###  3.1 SGDA SDE

######  Theorem 3.3 (SGDA SDE - Informal Statement of Theorem C.5).

Under sufficient regularity conditions, the solution of the following SDE is
an order $1$ weak approximation of the discrete update of SGDA (2):

$\displaystyle
dZ_{t}=-F\left(Z_{t}\right)dt+\sqrt{\eta\Sigma\left(Z_{t}\right)}dW_{t},$ (7)

where $\Sigma(z)$ is the noise covariance

$\displaystyle\Sigma(z)={\mathbb{E}}[\xi_{\gamma}(z)\xi_{\gamma}(z)^{\top}],$
(8)

and $\xi_{\gamma}(z):=F\left(z\right)-F_{\gamma}\left(z\right)$ the noise in
the sample $F_{\gamma}$.

###  3.2 SEG SDE

A notable characteristic of SEG is the inclusion of the variable $\rho$ that
controls the magnitude of the extra step. This variable plays an important
role in the derivation of the SDE of SEG and one has to differentiate between
two different regimes:

1. When $\rho\sim\eta$, the SDE of SEG is the same as SGDA, which is consistent with the literature on ODEs (Chavdarova et al.,, 2023; Lu,, 2022). The formal proof is given in Theorem C.12. 2. However, if the extra stepsize $\rho$ is sizeably larger than $\eta$ (Hsieh et al.,, 2020) (i.e. $\rho=\mathcal{O}(\sqrt{\eta}))$, SEG enters a more exploratory regime, for which the SDE becomes distinct from the first regime.

Before presenting our main result, we introduce some notation. Let
${\boldsymbol{\gamma}}:=(\gamma^{1},\gamma^{2})$,
$\bar{F}_{{\boldsymbol{\gamma}}}(z):=\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)$, and
$\bar{F}(z):={\mathbb{E}}[\bar{F}_{{\boldsymbol{\gamma}}}(z)]$ be its
expectation. We denote the noise in $\bar{F}$ as
$\bar{\xi}_{{\boldsymbol{\gamma}}}(z):=\bar{F}_{{\boldsymbol{\gamma}}}(z)-\bar{F}(z)$
and consider the mixed (non-symmetric) covariance matrix
$\bar{\Sigma}(z)={\mathbb{E}}[\xi_{\gamma^{1}}(z)\bar{\xi}_{{\boldsymbol{\gamma}}}(z)^{\top}]$.

######  Theorem 3.4 (Informal Statement of Theorem C.8).

Let

$\displaystyle F^{\scalebox{0.6}{\text{SEG}}}(z):=F(z)-\rho\bar{F}(z),$ (9)
$\displaystyle\Sigma^{\scalebox{0.6}{\text{SEG}}}(z):=\Sigma(z)+\rho\left[\bar{\Sigma}(z)+\bar{\Sigma}(z)^{\top}\right].$
(10)

Under sufficient regularity conditions and $\rho=\mathcal{O}(\sqrt{\eta})$,
the solution of the following SDE is the order 1 weak approximation of the
discrete update of SEG

$\displaystyle
dZ_{t}=-F^{\scalebox{0.6}{\text{SEG}}}\left(Z_{t}\right)dt+\sqrt{\eta\Sigma^{\scalebox{0.6}{\text{SEG}}}\left(Z_{t}\right)}dW_{t}.$
(11)

###### Proof.

To prove that the SDE is a weak approximation of SEG as per Definition 3.2, we
prove that the first and second moments of its discretization match those of
SEG up to an error of order $\eta$ and $\eta^{2}$, respectively. ∎

For didactic reasons, we now present Corollary 3.5, a consequence of Theorem
3.4 that provides a more interpretable SDE for SEG which we will use to
establish a comparison with SGDA (Eq.(7)) and SHGD (Eq.(16)).

(a)  (b)

(c)  (d)

Figure 2: Graphical representation of the implicit regularization of the
vector field of SEG for $f(x,y)=xy$: $-F$ spins the dynamics in a circle (Top
Left); $+\nabla FF$ pulls it towards $0$ (Top Right); If $\rho$ is small,
$-F+\rho\nabla FF$ combines the two fields and spirals towards the origin
(Bottom Left); If $\rho$ is large, $-F+\rho\nabla FF$ is a chaotic field that
makes the dynamics diverge (Bottom Right).

######  Corollary 3.5 (Informal Statement of Corollary C.10).

Under the assumptions of Theorem 3.4, that $\gamma^{1}=\gamma^{2}=\gamma$, and
that the stochastic gradients are
$\nabla_{x}f_{\gamma}(z)=\nabla_{x}f(z)+U^{x}$ and
$\nabla_{y}f_{\gamma}(z)=\nabla_{y}f(z)+U^{y}$ such that $U^{x}$ and $U^{y}$
are independent noises that do not depend on $z$, the following SDE provides a
1 weak approximation of the discrete update of SEG

$\displaystyle dZ_{t}=$ $\displaystyle-\left(F(Z_{t})-\rho\nabla
F(Z_{t})F(Z_{t})\right)dt$ (12)
$\displaystyle+\left(\mathbf{I}_{2d}-\rho\nabla
F\left(Z_{t}\right)\right)\sqrt{\eta\Sigma}dW_{t}.$

If instead (under the same assumptions) $\gamma^{1}$ and $\gamma^{2}$ are
uncorrelated, the SDE has a drift regularization term but no variance
regularization:

$\displaystyle dZ_{t}=-\left(F(Z_{t})-\rho\nabla
F(Z_{t})F(Z_{t})\right)dt+\sqrt{\eta\Sigma}dW_{t}.$

###### Proof.

The noise assumption implies $\nabla F_{\gamma^{1}}(z)=\nabla F(z)$. Therefore
$\bar{F}(z):=\nabla F(z)F(z)$. Next, note that
$\bar{\xi}_{{\boldsymbol{\gamma}}}(z):=\nabla F(z)\xi_{\gamma^{2}}(z)$ and
therefore
$\bar{\Sigma}(z)={\mathbb{E}}[\xi_{\gamma^{1}}(z)\xi_{\gamma^{2}}^{\top}(z)\nabla
F(z)^{\top}]=\Sigma\nabla F(z)^{\top}$ if $\gamma^{1}=\gamma^{2}$ and is zero
otherwise. Next, note that
$\Sigma^{\scalebox{0.6}{\text{SEG}}}(z):=\Sigma+\rho\Sigma\nabla
F(z)^{\top}+\rho\nabla F(z)\Sigma=(\mathbf{I}_{2d}+\rho\nabla
F(z))\Sigma(\mathbf{I}_{2d}+\rho\nabla F(z)^{\top})+\mathcal{O}(\rho^{2})$.
Since terms of order $\rho^{2}$ have a vanishing influence, this proves the
result. ∎

###  3.3 SHGD SDE

######  Theorem 3.6 (SHGD SDE - Informal Statement of Theorem C.14).

Let $\mathcal{H}_{\boldsymbol{\gamma}}:=\mathcal{H}_{\gamma^{1},\gamma^{2}}$
and let us define

$\displaystyle
F^{\scalebox{0.6}{\text{SHGD}}}(z):=\nabla{\mathbb{E}}\left[\mathcal{H}_{{\boldsymbol{\gamma}}}\left(z\right)\right],$
(13)
$\displaystyle\Sigma^{\scalebox{0.6}{\text{SHGD}}}(z):={\mathbb{E}}\left[\hat{\xi}_{\boldsymbol{\gamma}}(z)\hat{\xi}_{\boldsymbol{\gamma}}(z)^{\top}\right],$
(14)

where
$\hat{\xi}_{\boldsymbol{\gamma}}(z)=F^{\scalebox{0.6}{\text{SHGD}}}(z)-\nabla\mathcal{H}_{{\boldsymbol{\gamma}}}\left(z\right)$.
Under sufficient regularity conditions, the solution of the following SDE is
the order 1 weak approximation of the discrete update of SHGD (4):

$\displaystyle
dZ_{t}=-F^{\scalebox{0.6}{\text{SHGD}}}\left(Z_{t}\right)dt+\sqrt{\eta\Sigma^{\scalebox{0.6}{\text{SHGD}}}\left(Z_{t}\right)}dW_{t}.$
(15)

Once again, we provide a more interpretable SDE under additional assumptions:

######  Corollary 3.7 (Informal Statement of Corollary C.16).

Under the assumptions of Theorem 3.6, that $\gamma^{1}=\gamma^{2}=\gamma$, and
that the stochastic gradients are
$\nabla_{x}f_{\gamma}(z)=\nabla_{x}f(z)+U^{x}$ and
$\nabla_{y}f_{\gamma}(z)=\nabla_{y}f(z)+U^{y}$ such that $U^{x}$ and $U^{y}$
are independent noises that do not depend on $z$, the SDE is

$\displaystyle dZ_{t}$
$\displaystyle=-\nabla\mathcal{H}\left(Z_{t}\right)dt+\sqrt{\eta}\nabla^{2}f\left(Z_{t}\right)\sqrt{\Sigma}dW_{t}.$
(16)

If instead $\gamma^{1}$ and $\gamma^{2}$ are uncorrelated, the SDE is the same
but with less variance:

$dZ_{t}=-\nabla\mathcal{H}\left(Z_{t}\right)dt+\sqrt{\frac{\eta}{2}}\nabla^{2}f\left(Z_{t}\right)\sqrt{\Sigma}dW_{t}.$
(17)

##### Empirical Validation

Figure 1 shows the empirical validation of Theorem 3.4 and Theorem 3.6: The
top left shows that the SDE of SGDA matches the algorithm and is also
attracted to a limit cycle. The bottom left shows that the SDE of SHGD matches
the empirical optimization of a highly nonlinear landscape. The top right
shows that the SDE of SEG matches its discrete-time counterpart for different
values of $\rho$. Also, the SDE of SGDA is not a good model to describe the
dynamics of SEG. The bottom right shows the evolution of the norm of the
iterates in time: We understand that the SDE $Z_{k\eta}$ and optimizer $z_{k}$
move at the exact same speed along the trajectory — This justifies their use
as investigation tools. Figure 9 shows that if $\rho=\mathcal{O}(\eta)$ or
smaller, the SDE of SGDA models the dynamics of SEG accurately. However, if
$\rho=\mathcal{O}(\sqrt{\eta})$ or larger, the SDE of SGDA no longer does so
while the SDE of SEG does. All experiments are averaged over 5 runs and
additional details are in Appendix G.

###  3.4 Comparisons

There are three notable observations we immediately derive from the SDEs
presented above:

1. Let us use $\tilde{\nabla}:=\left(\nabla_{x},-\nabla_{y}\right)$. Then, one can see that the drift term $F$ is simply equal to $F=\tilde{\nabla}f$ for SGDA, while SEG implicitly introduces an additional regularizer such that $F^{\scalebox{0.6}{\text{SEG}}}=\tilde{\nabla}\left[f+\frac{\rho}{2}\left[\lVert\nabla_{y}f\rVert_{2}^{2}-\lVert\nabla_{x}f\rVert_{2}^{2}\right]\right].$ Therefore, the dynamics of SEG is equivalent to that of SGDA on an implicitly regularized vector field. Figure 2 illustrates this phenomenon. 2. The presence of $\rho\nabla F$ in the diffusion term of SEG shows that the extra step implicitly adds (on top of that of SGDA) a noise component that depends on the curvature of the landscape. 3. SHGD is a second-order method that explicitly optimizes the Hamiltonian which by definition uses curvature-based information. The SDE in Eq.(16) shows how this results in $\nabla^{2}f$ directly affecting its noise structure.

##  4 CONVERGENCE CONDITIONS

In this section, we derive the ODE that characterizes the evolution of the
expected Hamiltonian $H_{t}$ along the dynamics of SEG and SHGD. We use it to
derive convergence conditions on a wide class of functions. Then, we focus on
Bilinear Games where we can explicitly solve the ODE which allows us to single
out the role of each ingredient of the dynamics. Finally, we provide
sufficient conditions to craft stepsize schedulers that induce convergence.

###  4.1 SHGD

We begin by introducing an auxiliary result that elucidates the evolution of
the Hamiltonian. Here we denote by $Z_{t}$ the stochastic process that defines
the evolution of SHGD. We also define
$H_{t}:={\mathbb{E}}_{\boldsymbol{\gamma}}[\mathcal{H}_{{\boldsymbol{\gamma}}}(Z_{t})]$
and
$\Sigma^{\scalebox{0.6}{\text{SHGD}}}_{t}:=\Sigma^{\scalebox{0.6}{\text{SHGD}}}(Z_{t})$.
Then,

${\mathbb{E}}\left[\dot{H}_{t}\right]=-{\mathbb{E}}\left[\|\nabla
H_{t}\|^{2}\right]+\frac{\eta}{2}\text{Tr}\left({\mathbb{E}}\left[\Sigma^{\scalebox{0.6}{\text{SHGD}}}_{t}\nabla^{2}H_{t}\right]\right).$

We observe that:

1. $-{\mathbb{E}}\left[\|\nabla H_{t}\|^{2}\right]$ comes from the drift of the SDE and is pulling the dynamics towards regions with zero energy; 2. $\frac{\eta}{2}\text{Tr}\left({\mathbb{E}}\left[\Sigma^{\scalebox{0.6}{\text{SHGD}}}_{t}\nabla^{2}H_{t}\right]\right)$ is induced by the diffusion term and has an adversarial effect; 3. Convergence can only be achieved if the pulling force is stronger than the repulsive one, even at vanishing energies.

We formalize this in Theorem 4.1 and Corollary 4.2.

######  Theorem 4.1 (SHGD General Convergence).

Consider the solution $Z_{t}$ of the SHGD SDE with $\gamma^{1}\neq\gamma^{2}$.
Let
$v_{t}:={\mathbb{E}}\left[{\mathbb{E}}_{{\boldsymbol{\gamma}}}\left[\lVert\nabla\mathcal{H}_{t}\left(Z_{t}\right)-\nabla\mathcal{H}_{{\boldsymbol{\gamma}}}\left(Z_{t}\right)\rVert_{2}^{2}\right]\right]$
measure the error in $\nabla\mathcal{H}$, in expectation over the whole
randomness up to time $t$. Suppose that:

  1. 1.

The smallest eigenvalue (in absolute value) $\mu$ of $\nabla^{2}f(z)$ is non-
zero;

  2. 2.

$\lVert\nabla^{2}H(z)\rVert_{\text{op}}<\mathcal{L}_{\mathcal{T}}$, for all
$z\in{\mathbb{R}}^{2d}$.

Then,

${\mathbb{E}}\left[H_{t}\right]\leq
e^{-2\mu^{2}t}\left[H_{0}+\frac{\eta\mathcal{L}_{\mathcal{T}}}{2}\int_{0}^{t}v_{s}e^{2\mu^{2}s}ds\right].$
(18)

###### Proof.

We derive the SDE of $H_{t}$ via Itô’s Lemma and take its expectation to
obtain the ODE of ${\mathbb{E}}\left[H_{t}\right]$. Then, we use the
assumptions to derive a bound on it. ∎

######  Corollary 4.2.

Under the assumptions of Theorem 4.1, if for $\mathcal{L}_{\mathcal{V}}>0$

$v_{t}\leq\mathcal{L}_{\mathcal{V}}{\mathbb{E}}\left[H_{t}\right],$ (19)

the solution is more explicit:

${\mathbb{E}}\left[H_{t}\right]\leq
H_{0}e^{\left(-2\mu^{2}+\eta\mathcal{L}_{\mathcal{V}}\mathcal{L}_{\mathcal{T}}\right)t}.$
(20)

If instead

$v_{t}\leq\mathcal{L}_{\mathcal{V}},$ (21)

we have

${\mathbb{E}}\left[H_{t}\right]\leq
H_{0}e^{-2\mu^{2}t}+\left(1-e^{-2\mu^{2}t}\right)\frac{\eta\mathcal{L}_{\mathcal{V}}\mathcal{L}_{\mathcal{T}}}{2\mu^{2}}.$
(22)

Discussion about Assumptions Note that:

1. (Loizou et al.,, 2020) which first proposed SHGD assumed independent mini-batches; 2. Lipschitzianity on $\nabla\mathcal{H}_{\gamma^{1},\gamma^{2}}$ and Error Bound on $F$ imply Eq. (19); 3. Bounded variance on $\nabla\mathcal{H}_{\gamma^{1},\gamma^{2}}$ implies Eq. (21).

##### Concrete Examples

We analyze Bilinear Games for which we can provide explicit formulas for the
results presented above. We focus on:
$f(x,y)=x^{\top}{\mathbb{E}}_{\xi}\left[\mathbf{\Lambda}_{\xi}\right]y$ and
$f(x,y)=x^{\top}\mathbf{\Lambda}y$ where $\mathbf{\Lambda}$ and
$\mathbf{\Lambda}_{\xi}$ are square, diagonal, and positive semidefinite
matrices.

######  Proposition 4.3.

For $f(x,y)=x^{\top}{\mathbb{E}}_{\xi}\left[\mathbf{\Lambda}_{\xi}\right]y$,
Eq. (19) holds and we have

$\frac{{\mathbb{E}}\left[\lVert
Z_{t}\rVert^{2}\right]}{2}=\sum_{i=1}^{d}\frac{\lVert
Z^{i}_{0}\rVert^{2}}{2}e^{-\left(2\lambda^{2}_{i}-\eta\sigma_{i}^{2}\left(2\lambda_{i}^{2}+\sigma_{i}^{2}\right)\right)t}.$
(23)

In particular, $\frac{{\mathbb{E}}\left[\lVert
Z_{t}\rVert^{2}\right]}{2}\overset{t\rightarrow\infty}{=}0$ if
$\eta<\frac{2\lambda^{2}_{i}}{\sigma_{i}^{2}\left(2\lambda_{1}^{2}+\sigma_{i}^{2}\right)},\quad\forall
i$.

In this case, the noise structure is such that $v_{t}$ scales like
${\mathbb{E}}\left[H_{t}\right]$. Thus, ${\mathbb{E}}\left[H_{t}\right]$
exponentially decays to $0$.

######  Proposition 4.4.

For $f(x,y)=x^{\top}\mathbf{\Lambda}y$ and covariance noise
$\Sigma:=\operatorname{diag}(\sigma_{1},\cdots,\sigma_{d})$, Eq. 21 holds and

$\frac{{\mathbb{E}}\left[\lVert
Z_{t}\rVert^{2}\right]}{2}=\sum_{i=1}^{d}\frac{\lVert
Z^{i}_{0}\rVert^{2}}{2}e^{-2\lambda^{2}_{i}t}+\frac{\eta\sigma_{i}^{2}}{2}\left(1-e^{-2\lambda^{2}_{i}t}\right),$
(24)

which implies that $\frac{{\mathbb{E}}\left[\lVert
Z_{t}\rVert^{2}\right]}{2}\overset{t\rightarrow\infty}{=}\frac{\eta}{2}\sum_{i=1}^{d}\sigma_{i}^{2}>0$.

In this case, $v_{t}$ is bounded, meaning that
${\mathbb{E}}\left[H_{t}\right]$ reaches an asymptotic suboptimality
exponentially fast.

Now we provide sufficient and necessary conditions to craft stepsize
schedulers that recover convergence.

######  Proposition 4.5.

Under the assumptions of Prop. 4.4, for any stepsize scheduler $\eta_{t}$,
$\frac{{\mathbb{E}}\left[\lVert Z_{t}\rVert^{2}\right]}{2}$ is equal to

$\sum_{i=1}^{d}e^{-2\lambda^{2}_{i}\int_{0}^{t}\eta_{s}ds}\left(\frac{\lVert
Z^{i}_{0}\rVert^{2}}{2}+\eta\sigma_{i}^{2}\lambda_{i}^{2}\int_{0}^{t}e^{2\lambda^{2}_{i}\int_{0}^{s}\eta_{r}dr}\eta^{2}_{s}ds\right).$

Therefore,

$\frac{{\mathbb{E}}\left[\lVert
Z_{t}\rVert^{2}\right]}{2}\overset{t\rightarrow\infty}{\rightarrow}0\iff\int_{0}^{\infty}\eta_{s}ds=\infty\text{
and }\lim_{t\rightarrow\infty}\eta_{t}=0.$ (25)

Among other possible choices of $\eta_{t}$,

$\eta_{t}=\frac{1}{(t+1)^{\gamma}}\implies\frac{{\mathbb{E}}\left[\lVert
Z_{t}\rVert^{2}\right]}{2}\rightarrow 0,\text{ for }\gamma\in\\{0.5,1\\}.$

(a)  (b)

Figure 3: Empirical validation of Prop. 4.4 and Prop. 4.5 (Left); Prop. 4.9
and Prop. 4.10 (Right): The dynamics of ${\mathbb{E}}\left[\lVert
Z_{t}\rVert^{2}\right]$ averaged across $5$ runs perfectly matches that
prescribed by our results for all schedulers. Both for SEG and SHGD,
$\eta=0.01$, while $\rho=1$.

###  4.2 SEG

Let $Z_{t}$ be the solution of the SEG SDE,
$\Sigma^{\scalebox{0.6}{\text{SEG}}}_{t}=\Sigma^{\scalebox{0.6}{\text{SEG}}}(Z_{t})$,
$H_{t}={\mathbb{E}}_{\boldsymbol{\gamma}}[\mathcal{H}_{{\boldsymbol{\gamma}}}(Z_{t})]$,
and
$F^{\scalebox{0.6}{\text{SEG}}}_{t}=F^{\scalebox{0.6}{\text{SEG}}}(Z_{t})$.
Then,

${\mathbb{E}}\left[\dot{H}_{t}\right]=-{\mathbb{E}}\left[\nabla
H_{t}^{\top}F^{\scalebox{0.6}{\text{SEG}}}_{t}\right]+\frac{\eta}{2}\text{Tr}\left({\mathbb{E}}\left[\Sigma^{\scalebox{0.6}{\text{SEG}}}_{t}\nabla^{2}H_{t}\right]\right).$

Once again, we have to study how the pulling and repulsive forces balance each
other in order to dissect the convergence behavior of SEG.

######  Theorem 4.6 (SEG General Convergence).

Consider the solution $Z_{t}$ of the SEG SDE with $\gamma^{1}\neq\gamma^{2}$.
Let $v_{t}:={\mathbb{E}}\left[{\mathbb{E}}_{{\boldsymbol{\gamma}}}\left[\lVert
F^{\scalebox{0.6}{\text{SEG}}}\left(Z_{t}\right)-F^{\scalebox{0.6}{\text{SEG}}}_{{\boldsymbol{\gamma}}}\left(Z_{t}\right)\rVert_{2}^{2}\right]\right]$
measure the error in $F^{\scalebox{0.6}{\text{SEG}}}$, in expectation over the
whole randomness up to time $t$. Suppose that:

  1. 1.

The smallest eigenvalue (in absolute value) $\mu_{\rho}$ of $\mathbf{M}$ is
non-zero, where
$\mathbf{M}=\operatorname{diag}(\mathbf{M}_{1,1},\mathbf{M}_{2,2})$, with
$\mathbf{M}_{1,1}:=\nabla^{2}f_{xx}+\rho\left(\nabla^{2}f_{xy}\nabla^{2}f_{xy}^{T}-\nabla^{2}f_{xx}^{2}\right)$,
and
$\mathbf{M}_{2,2}:=-\nabla^{2}f_{yy}+\rho\left(\nabla^{2}f_{xy}\nabla^{2}f_{xy}^{T}-\nabla^{2}f_{yy}^{2}\right)$;

  2. 2.

$\lVert\nabla^{2}H(z)\rVert_{\text{op}}<\mathcal{L}_{\mathcal{T}}$, for all
$z\in{\mathbb{R}}^{2d}$.

Then,

${\mathbb{E}}\left[H_{t}\right]\leq
e^{-2\mu_{\rho}^{2}t}\left[H_{0}+\frac{\eta\mathcal{L}_{\mathcal{T}}}{2}\int_{0}^{t}v_{s}e^{2\mu_{\rho}^{2}s}ds\right].$
(26)

######  Corollary 4.7.

The very same result as Corollary 4.2 holds where we substitute $\mu$ with
$\mu_{\rho}$.

Discussion about Assumptions Note that:

1. Independent mini-batches are used in Indep.-Sample SEG (Du et al.,, 2022; Gorbunov et al.,, 2022), and are not a necessary condition; 2. $\kappa_{1}$-Lipschitzianity on $F_{\gamma^{1}}$, $\kappa_{2}$-Lipschitzianity on $\nabla F_{\gamma^{1}}F_{\gamma^{2}}$, and $\beta$-Error Bound on $F$, imply $v_{t}\leq\beta^{2}(\kappa_{1}^{2}+\rho^{2}\kappa_{2}^{2}){\mathbb{E}}\left[H_{t}\right]$; 3. $\sigma_{1}$-Bounded variance on $F_{\gamma^{1}}$ and $\sigma_{2}$-Bounded variance on $\nabla F_{\gamma^{1}}F_{\gamma^{2}}$, imply $v_{t}\leq\sigma_{1}^{2}+\rho^{2}\sigma_{2}^{2}$.

Interestingly, we notice that increasing $\rho$ might be detrimental as it
could possibly lead to divergence.

##### Concrete Examples

######  Proposition 4.8.

For $f(x,y)=x^{\top}{\mathbb{E}}_{\xi}\left[\mathbf{\Lambda}_{\xi}\right]y$,
we have

$\frac{{\mathbb{E}}\left[\lVert
Z_{t}\rVert^{2}\right]}{2}=\sum_{i=1}^{d}\frac{\lVert
Z^{i}_{0}\rVert^{2}}{2}e^{-\left(2\rho\lambda^{2}_{i}-\eta\sigma_{i}^{2}\left(1+\rho^{2}\left(2\lambda_{i}^{2}+\sigma_{i}^{2}\right)\right)\right)t}.$
(27)

In particular, $\frac{{\mathbb{E}}\left[\lVert
Z_{t}\rVert^{2}\right]}{2}\overset{t\rightarrow\infty}{=}0$ if $,\forall
i\in\\{i,\cdots,d\\}$

$2\rho\lambda^{2}_{i}-\eta\sigma_{i}^{2}\left(1+\rho^{2}\left(2\lambda_{i}^{2}+\sigma_{i}^{2}\right)\right)>0.$
(28)

######  Proposition 4.9.

For $f(x,y)=x^{\top}\mathbf{\Lambda}y$ and covariance noise
$\Sigma:=\operatorname{diag}(\sigma_{1},\cdots,\sigma_{d})$,
$\frac{{\mathbb{E}}\left[\lVert Z_{t}\rVert^{2}\right]}{2}$ is equal to

$\sum_{i=1}^{d}\frac{\lVert
Z^{i}_{0}\rVert^{2}}{2}e^{-2\rho\lambda^{2}_{i}t}+\frac{\eta\sigma_{i}^{2}}{2}\frac{1+\rho^{2}\lambda_{i}^{2}}{\rho\lambda_{i}^{2}}\left(1-e^{-2\rho\lambda^{2}_{i}t}\right),$
(29)

which implies that

$\frac{{\mathbb{E}}\left[\lVert
Z_{t}\rVert^{2}\right]}{2}\overset{t\rightarrow\infty}{=}\frac{\eta}{2}\sum_{i=1}^{d}\sigma_{i}^{2}\frac{1+\rho^{2}\lambda_{i}^{2}}{\rho\lambda_{i}^{2}}>0.$
(30)

We derive necessary and sufficient conditions for stepsize schedulers to
remediate the convergence deficiency.

######  Proposition 4.10.

Under the assumptions of Prop. 4.9, for any stepsize scheduler $\eta_{t}$ and
$\rho_{t}$, $\frac{{\mathbb{E}}\left[\lVert Z_{t}\rVert^{2}\right]}{2}$ is
equal to

$\displaystyle\sum_{i=1}^{d}e^{-2\lambda^{2}_{i}\rho\int_{0}^{t}\eta_{s}\rho_{s}ds}\left(\frac{\lVert
Z^{i}_{0}\rVert^{2}}{2}\right.$ (31)
$\displaystyle\left.+\eta\sigma_{i}^{2}\int_{0}^{t}e^{2\lambda^{2}_{i}\rho\int_{0}^{s}\eta_{r}\rho_{r}dr}\eta^{2}_{s}(1+\lambda_{i}^{2}\rho^{2}\rho_{s}^{2})ds\right).$

Therefore, $\frac{{\mathbb{E}}\left[\lVert
Z_{t}\rVert^{2}\right]}{2}\overset{t\rightarrow\infty}{\rightarrow}0$ if and
only if

$\int_{0}^{\infty}\eta_{s}\rho_{s}ds=\infty\text{ and
}\lim_{t\rightarrow\infty}\eta_{t}\rho_{t}=\lim_{t\rightarrow\infty}\frac{\eta_{t}}{\rho_{t}}=0.$
(32)

In particular, when $\rho_{t}=1$,

$\eta_{t}=\frac{1}{(t+1)^{\gamma}}\implies\frac{{\mathbb{E}}\left[\lVert
Z_{t}\rVert^{2}\right]}{2}\rightarrow 0,\text{ for }\gamma\in\\{0.5,1\\}.$

The left of Figure 3 shows the empirical validation of Prop. 4.4 and Prop. 4.5
while its right side shows that of Prop. 4.9 and Prop. 4.10. Figure 7 shows
the same for Prop. 4.3 and Prop. 4.8. More details are available in Appendix
G.

Conclusion: 1. If the uncertainty $v_{t}$ is well behaved as in Prop. 4.3 and
Prop. 4.8, the Hamiltonian decays exponentially to $0$; 2. When $v_{t}$ is
constant as in Prop. 4.4 and Prop. 4.9, both algorithms exponentially reach a
level of suboptimality that depends on the curvature of the landscape (and on
$\rho$ for SEG); 3. Prop. 4.5 and Prop. 4.10 provide a recipe to craft
schedulers that recover convergence. We provide examples of such necessary and
sufficient conditions; 4. Eq. (27) and Eq. (29) clearly show that large $\rho$
speeds up the convergence. However, this might violate Eq. (28) and increase
the suboptimality in Eq. (30).

##  5 QUADRATIC GAMES: EXACT DYNAMICS EXPRESSION

In this section, we derive the exact solution to the SDEs of SEG and SHGD for
the Quadratic Games
$f(x,y)=\frac{x^{\top}\mathbf{A}x}{2}+x^{\top}\mathbf{\Lambda}y-\frac{y^{\top}\mathbf{A}y}{2}$
where $\mathbf{\Lambda}$ and $\mathbf{A}$ are square, diagonal and positive
semidefinite matrices. We notice that if $\mathbf{A}=\mathbf{0}$, these are
classic Bilinear Games.

###  5.1 Exact Dynamics - SEG

######  Theorem 5.1 (Exact Dynamics of SEG).

Under the assumptions of Corollary 3.5, we take the covariance of the noise on
the gradients to be $\sigma^{2}\mathbf{I}_{d}$ and have that

$Z_{t}=\mathbf{\mathbf{\tilde{E}}}(t)\mathbf{\mathbf{\tilde{R}}}(t)\left(z+\sqrt{\eta}\sigma\int_{0}^{t}\mathbf{\mathbf{\tilde{E}}}(-s)\mathbf{\mathbf{\tilde{R}}}(-s)\mathbf{M}dW_{s}\right),$
(33)

$\mathbf{\mathbf{\tilde{E}}}(t)=\left[\begin{array}[]{ll}\mathbf{E}(t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(t)\end{array}\right],\mathbf{\mathbf{\tilde{R}}}(t)=\left[\begin{array}[]{ll}\mathbf{C}(t)&-\mathbf{S}(t)\\\
\mathbf{S}(t)&\mathbf{C}(t)\end{array}\right]$, and
$\mathbf{M}=\left[\begin{array}[]{ll}\mathbf{I}_{d}-\rho\mathbf{A}&-\rho\mathbf{\Lambda}\\\
\rho\mathbf{\Lambda}&\mathbf{I}_{d}-\rho\mathbf{A}\end{array}\right]$, where

$\mathbf{E}(t):=\operatorname{diag}{\left(e^{\rho\left(a_{1}^{2}-\lambda_{1}^{2}\right)t-a_{1}t},\cdots,e^{\rho\left(a_{d}^{2}-\lambda_{d}^{2}\right)t-a_{d}t}\right)},$
(34)
$\mathbf{C}(t):=\operatorname{diag}{\left(\cos{(\hat{\lambda}_{1}t)},\cdots,\cos{(\hat{\lambda}_{d}t)}\right)},$
(35)
$\mathbf{S}(t):=\operatorname{diag}{\left(\sin{(\hat{\lambda}_{1}t)},\cdots,\sin{(\hat{\lambda}_{d}t)}\right)},$
(36)

and $\hat{\lambda}_{i}:=\lambda_{i}(1-2\rho a_{i})$. If
$\rho\left(a_{i}^{2}-\lambda_{i}^{2}\right)-a_{i}<0$:

  1. 1.

${\mathbb{E}}\left[Z_{t}\right]=\mathbf{\mathbf{\tilde{E}}}(t)\mathbf{\mathbf{\tilde{R}}}(t)z\overset{t\rightarrow\infty}{=}0$;

  2. 2.

The covariance matrix of $Z_{t}$ is equal to

$\frac{\eta\sigma^{2}}{2}\left[\begin{array}[]{ll}\mathbf{I}_{d}-\mathbf{E}(2t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{I}_{d}-\mathbf{E}(2t)\end{array}\right]\bar{\Sigma}\overset{t\rightarrow\infty}{=}\frac{\eta\sigma^{2}}{2}\bar{\Sigma}$
(37)

where $\bar{\Sigma}:=\operatorname{diag}(\mathbf{B},\mathbf{B})$ and
$\mathbf{B}$ is defined as

$\operatorname{diag}{\left(\frac{(1-\rho
a_{1})^{2}+\rho^{2}\lambda_{1}^{2}}{a_{1}+\rho(\lambda_{1}^{2}-a_{1}^{2})},\cdots,\frac{(1-\rho
a_{d})^{2}+\rho^{2}\lambda_{d}^{2}}{a_{d}+\rho(\lambda_{d}^{2}-a_{d}^{2})}\right)}.$
(38)

###### Proof.

Since the SDE is linear, the closed-form formula of the solution $Z_{t}$ is
known. We use the martingale property of Brownian motion to calculate
${\mathbb{E}}\left[Z_{t}\right]$ while that of the second moment uses the Itô
Isometry. ∎

We verify Eq. (38) in Figure 8 in Appendix.

On the sign of $\rho$ and its magnitude:

If one can chose $\rho_{i}$ for each coordinate: 1. Eq. (34) implies that SEG
converges only if $\rho_{i}\left(a_{i}^{2}-\lambda_{i}^{2}\right)-a_{i}<0$,
and that $\rho_{i}\left(a_{i}^{2}-\lambda_{i}^{2}\right)<0$ is necessary to be
faster than SGDA, meaning that negative $\rho_{i}$ might be convenient if
$a_{i}>\lambda_{i}$; 2. If $\rho_{i}$ has the correct sign, a larger absolute
value implies faster convergence; 3. Eq. (38) implies that the asymptotic
variance along the $i$-th coordinate $\mathbf{B}_{i,i}(\rho_{i})$ explodes if
$|\rho_{i}|$ is too large or if
$\rho_{i}\rightarrow\frac{-a_{i}}{\lambda_{i}^{2}-a_{i}^{2}}$ ; 4.
$B_{i,i}(\rho_{i})$ is a convex function of $\rho_{i}$ whose minimum is
realized at $\rho^{\text{V}}_{i}=\frac{1}{a_{i}+\lambda_{i}}$; However, if
$\rho^{\text{V}}_{i}$ is small, it slows down the convergence. If one has to
choose a single value of $\rho$: 1. One has to select it as it will
(de)accelerate different coordinates based on its sign; 2. The trace of
$\mathbf{B}$ is a convex function of $\rho$, meaning that there is an optimal
$\rho^{*}$ that minimizes it.

(a)  (b)

Figure 4: Comparison between SEG and SHGD on Quadratic Games: (Left),
$\rho^{V}$ and $\rho^{H}$ meet the designated goals, sometimes negative $\rho$
is desirable as positive ones slow down the convergence. Large $|\rho|$
induces faster convergence which in turn results in larger suboptimality.
(Right), negative $\rho$ escapes the bad saddle faster than SGDA, positive
ones induce convergence, and $\rho^{H}$ matches the decay of SHGD. In both
experiments, $\eta=0.01$.

###  5.2 Exact Dynamics - SHGD

######  Theorem 5.2 (Exact Dynamics of SHGD).

Under the assumptions of Corollary 3.7, we take the covariance of the noise on
the gradients to be equal to $\sigma^{2}\mathbf{I}_{d}$ and have

$Z_{t}=\mathbf{\mathbf{\tilde{E}}}(t)\left(z+\sqrt{\eta}\sigma\int_{0}^{t}\mathbf{\mathbf{\tilde{E}}}(-s)\mathbf{M}dW_{s}\right),$
(39)

$\mathbf{\mathbf{\tilde{E}}}(t)=\left[\begin{array}[]{ll}\mathbf{E}(t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(t)\end{array}\right]$,
$\mathbf{M}=\left[\begin{array}[]{ll}\mathbf{A}&\mathbf{\Lambda}\\\
\mathbf{\Lambda}&-\mathbf{A}\end{array}\right]$, where

$\mathbf{E}(t):=\operatorname{diag}{\left(e^{-\left(\lambda_{1}^{2}+a_{1}^{2}\right)t},\cdots,e^{-\left(\lambda_{d}^{2}+a_{d}^{2}\right)t}\right)}.$
(40)

In particular, we have that

  1. 1.

${\mathbb{E}}\left[Z_{t}\right]=\mathbf{\mathbf{\tilde{E}}}(t)z\overset{t\rightarrow\infty}{=}0$;

  2. 2.

The covariance matrix of $Z_{t}$ is equal to

$\eta\frac{\sigma^{2}}{2}\left[\begin{array}[]{ll}\mathbf{I}_{d}-\mathbf{E}(2t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{I}_{d}-\mathbf{E}(2t)\end{array}\right]\bar{\Sigma}\overset{t\rightarrow\infty}{=}\frac{\eta\sigma^{2}}{2}\bar{\Sigma},$
(41)

where $\bar{\Sigma}:=\operatorname{diag}(\mathbf{I}_{d},\mathbf{I}_{d})$.

SEG vs SHGD: Insights

1. The curvature influences the convergence speed of SHGD, but differently than for SEG, it does not affect the asymptotic covariance matrix; 2. If $(\lambda_{i}^{2}-a_{i}^{2})\rho^{H}_{i}>a_{i}^{2}+\lambda_{i}^{2}-a_{i}$, SEG exponentially decays faster than SHGD. However, this means that SEG has a larger asymptotic variance; 3. If $\rho^{V}_{i}=\frac{1}{\lambda_{i}+a_{i}}$, SEG attains its lowest asymptotic variance $\frac{\eta\sigma^{2}\lambda_{i}}{2(a_{i}+\lambda_{i})^{2}}$, which is smaller than $\frac{\eta\sigma^{2}}{2}$ reached by SHGD only if $a_{i}^{2}+\lambda_{i}^{2}-\lambda_{i}>0$; 4. If $\lambda_{i}^{2}+a_{i}^{2}\sim 0$, SHGD is essentially stuck and SEG is intrinsically faster; 5. If $a_{i}<0$, $Z=0$ is a bad saddle. While SEG can escape it, SHGD is pulled towards it.

##### Conclusion

Our results allowed us to carry out a 1-to-1 comparison of the two methods,
shedding light on the role of $\rho$ in influencing the behavior of SEG w.r.t.
SHGD. The interaction between the curvature and the noise implies that
selecting $\rho_{i}$ is a trade-off between the speed of convergence and the
asymptotic variance. There is no clear winner between SEG and SHGD, as they
are preferable for different landscapes. Figure 4 shows experiments that
support the latter claim.

##  6 CONCLUSIONS

We have presented and analyzed the first formal SDE models for SGDA, SEG, and
SHGD. We have shown the implicit regularization in SEG in contrast with the
explicit use of curvature-based information in SHGD, which leads to different
noise structures and asymptotic suboptimality.

Furthermore, we have used these SDEs to fully characterize the evolution of
the Hamiltonian under the dynamics of these algorithms in useful scenarios. We
derived convergence bounds and established conditions under which stepsize
schedulers guarantee convergence.

Finally, our comparative analysis of SEG and SHGD for Quadratic Games sheds
light on the role of $\rho$, revealing a trade-off between convergence speed
and suboptimality. We also presented the first theoretical and experimental
evidence that, depending on the curvature of the loss, the optimal $\rho$
might be negative.

##### Outlook.

Our framework offers a unified and structured analytical approach rooted in
Itô calculus to study minimax optimizers. Our approach not only facilitates
the derivation of novel insights but also enables straightforward comparisons
between discrete algorithms. We believe our findings provide a foundation for
future research, which may include the analysis of momentum, adaptive methods,
derivation of scaling laws, and the design of new optimizers.

##### Limitations.

Modeling discrete-time algorithms using SDEs hinges on Assumption 3.1. As
documented (Li et al.,, 2021), large values of the stepsize $\eta$ or the
absence of specific conditions on $\nabla f$ and the noise covariance matrix
can result in an approximation failure. While these shortcomings can be
mitigated by increasing the order of the weak approximation, our perspective
aligns with the idea that SDEs should primarily serve as simplification tools
— to solidify our intuition — and might not gain substantial benefits from
additional complexity.

##  7 ACKNOWLEDGEMENTS

We thank the reviewers for their feedback which greatly helped us improve this
manuscript.

Additionally, we thank Dr. Junchi Yang and Prof. Dr. Niao He for the
insightful discussions.

Enea Monzio Compagnoni and Aurelien Lucchi acknowledge the financial support
of the Swiss National Foundation, SNF grant No 207392. Antonio Orvieto
acknowledges the financial support of the Hector Foundation. Frank Norbert
Proske acknowledges the financial support of the Norwegian Research Council
(project No 274410) and MSCA4Ukraine (project No 101101923).

## References

  * An et al., (2020) An, J., Lu, J., and Ying, L. (2020).  Stochastic modified equations for the asynchronous stochastic gradient descent.  Information and Inference: A Journal of the IMA, 9(4):851–873.
  * Balduzzi et al., (2018) Balduzzi, D., Racaniere, S., Martens, J., Foerster, J., Tuyls, K., and Graepel, T. (2018).  The mechanics of n-player differentiable games.  In International Conference on Machine Learning, pages 354–363. PMLR.
  * Chaudhari and Soatto, (2018) Chaudhari, P. and Soatto, S. (2018).  Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks.  In 2018 Information Theory and Applications Workshop (ITA), pages 1–10. IEEE.
  * Chavdarova et al., (2019) Chavdarova, T., Gidel, G., Fleuret, F., and Lacoste-Julien, S. (2019).  Reducing noise in gan training with variance reduced extragradient.  Advances in Neural Information Processing Systems, 32.
  * Chavdarova et al., (2022) Chavdarova, T., Hsieh, Y.-P., and Jordan, M. I. (2022).  Continuous-time analysis for variational inequalities: An overview and desiderata.  arXiv preprint arXiv:2207.07105.
  * Chavdarova et al., (2023) Chavdarova, T., Jordan, M. I., and Zampetakis, M. (2023).  Last-iterate convergence of saddle point optimizers via high-resolution differential equations.  In Minimax Theory and its Applications 08 (2023), No. 2, pages 333–380. Heldermann Verlag.
  * Chen et al., (2015) Chen, C., Ding, N., and Carin, L. (2015).  On the convergence of stochastic gradient mcmc algorithms with high-order integrators.  Advances in neural information processing systems, 28.
  * Chen and Rockafellar, (1997) Chen, G. H. and Rockafellar, R. T. (1997).  Convergence rates in forward–backward splitting.  SIAM Journal on Optimization, 7(2):421–444.
  * Compagnoni et al., (2023) Compagnoni, E. M., Biggio, L., Orvieto, A., Proske, F. N., Kersting, H., and Lucchi, A. (2023).  An sde for modeling sam: Theory and insights.  In International Conference on Machine Learning, pages 25209–25253. PMLR.
  * Du et al., (2022) Du, S. S., Gidel, G., Jordan, M. I., and Li, C. J. (2022).  Optimal extragradient-based bilinearly-coupled saddle-point optimization.  arXiv preprint arXiv:2206.08573.
  * Gidel et al., (2019) Gidel, G., Berard, H., Vignoud, G., Vincent, P., and Lacoste-Julien, S. (2019).  A variational inequality perspective on generative adversarial networks.  ICLR.
  * Goodfellow et al., (2016) Goodfellow, I., Bengio, Y., Courville, A., and Bengio, Y. (2016).  Deep learning, volume 1.  MIT Press.
  * Gorbunov et al., (2022) Gorbunov, E., Berard, H., Gidel, G., and Loizou, N. (2022).  Stochastic extragradient: General analysis and improved rates.  In International Conference on Artificial Intelligence and Statistics, pages 7865–7901. PMLR.
  * He et al., (2018) He, L., Meng, Q., Chen, W., Ma, Z.-M., and Liu, T.-Y. (2018).  Differential equations for modeling asynchronous algorithms.  In Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI’18, page 2220–2226. AAAI Press.
  * Hsieh et al., (2019) Hsieh, Y.-G., Iutzeler, F., Malick, J., and Mertikopoulos, P. (2019).  On the convergence of single-call stochastic extra-gradient methods.  Advances in Neural Information Processing Systems, 32.
  * Hsieh et al., (2020) Hsieh, Y.-G., Iutzeler, F., Malick, J., and Mertikopoulos, P. (2020).  Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling.  Advances in Neural Information Processing Systems, 33:16223–16234.
  * Hsieh et al., (2021) Hsieh, Y.-P., Mertikopoulos, P., and Cevher, V. (2021).  The limits of min-max optimization algorithms: Convergence to spurious non-critical sets.  In International Conference on Machine Learning, pages 4337–4348. PMLR.
  * Jastrzebski et al., (2018) Jastrzebski, S., Kenton, Z., Arpit, D., Ballas, N., Fischer, A., Bengio, Y., and Storkey, A. (2018).  Three factors influencing minima in sgd.  ICANN 2018.
  * Juditsky et al., (2011) Juditsky, A., Nemirovski, A., and Tauvel, C. (2011).  Solving variational inequalities with stochastic mirror-prox algorithm.  Stochastic Systems, 1(1):17–58.
  * Korpelevich, (1976) Korpelevich, G. M. (1976).  The extragradient method for finding saddle points and other problems.  Matecon, 12:747–756.
  * Kushner and Yin, (2003) Kushner, H. and Yin, G. G. (2003).  Stochastic approximation and recursive algorithms and applications, volume 35.  Springer Science & Business Media.
  * Li et al., (2022) Li, C. J., Yu, Y., Loizou, N., Gidel, G., Ma, Y., Le Roux, N., and Jordan, M. (2022).  On the convergence of stochastic extragradient for bilinear games using restarted iteration averaging.  In International Conference on Artificial Intelligence and Statistics, pages 9793–9826. PMLR.
  * Li et al., (2017) Li, Q., Tai, C., and Weinan, E. (2017).  Stochastic modified equations and adaptive stochastic gradient algorithms.  In International Conference on Machine Learning, pages 2101–2110. PMLR.
  * Li et al., (2019) Li, Q., Tai, C., and Weinan, E. (2019).  Stochastic modified equations and dynamics of stochastic gradient algorithms i: Mathematical foundations.  The Journal of Machine Learning Research, 20(1):1474–1520.
  * Li et al., (2021) Li, Z., Malladi, S., and Arora, S. (2021).  On the validity of modeling SGD with stochastic differential equations (SDEs).  In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W., editors, Advances in Neural Information Processing Systems.
  * Ljung et al., (2012) Ljung, L., Pflug, G., and Walk, H. (2012).  Stochastic approximation and optimization of random systems, volume 17.  Birkhäuser.
  * Loizou et al., (2021) Loizou, N., Berard, H., Gidel, G., Mitliagkas, I., and Lacoste-Julien, S. (2021).  Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity.  Advances in Neural Information Processing Systems, 34:19095–19108.
  * Loizou et al., (2020) Loizou, N., Berard, H., Jolicoeur-Martineau, A., Vincent, P., Lacoste-Julien, S., and Mitliagkas, I. (2020).  Stochastic hamiltonian gradient methods for smooth games.  In International Conference on Machine Learning, pages 6370–6381. PMLR.
  * Lu, (2022) Lu, H. (2022).  An o (sr)-resolution ode framework for understanding discrete-time algorithms and applications to the linear convergence of minimax problems.  Mathematical Programming, 194(1-2):1061–1112.
  * Malladi et al., (2022) Malladi, S., Lyu, K., Panigrahi, A., and Arora, S. (2022).  On the SDEs and scaling rules for adaptive gradient algorithms.  In Advances in Neural Information Processing Systems.
  * Mandt et al., (2015) Mandt, S., Hoffman, M. D., Blei, D. M., et al. (2015).  Continuous-time limit of stochastic gradient descent revisited.  NIPS-2015.
  * Mao, (2007) Mao, X. (2007).  Stochastic differential equations and applications.  Elsevier.
  * Mil’shtein, (1986) Mil’shtein, G. (1986).  Weak approximation of solutions of systems of stochastic differential equations.  Theory of Probability & Its Applications, 30(4):750–766.
  * Mishchenko et al., (2020) Mishchenko, K., Kovalev, D., Shulgin, E., Richtárik, P., and Malitsky, Y. (2020).  Revisiting stochastic extragradient.  In International Conference on Artificial Intelligence and Statistics, pages 4573–4582. PMLR.
  * Nemirovski et al., (2009) Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. (2009).  Robust stochastic approximation approach to stochastic programming.  SIAM Journal on optimization, 19(4):1574–1609.
  * Noor, (2003) Noor, M. A. (2003).  New extragradient-type methods for general variational inequalities.  Journal of Mathematical Analysis and Applications, 277(2):379–394.
  * Øksendal, (1990) Øksendal, B. (1990).  When is a stochastic integral a time change of a diffusion?  Journal of theoretical probability, 3(2):207–226.
  * Orvieto and Lucchi, (2019) Orvieto, A. and Lucchi, A. (2019).  Continuous-time models for stochastic optimization algorithms.  Advances in Neural Information Processing Systems, 32.
  * Ryu et al., (2019) Ryu, E. K., Yuan, K., and Yin, W. (2019).  Ode analysis of stochastic gradient methods with optimism and anchoring for minimax problems.  arXiv preprint arXiv:1905.10899.
  * Su et al., (2014) Su, W., Boyd, S., and Candes, E. (2014).  A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights.  In Advances in Neural Information Processing Systems.
  * Xie et al., (2021) Xie, Z., Sato, I., and Sugiyama, M. (2021).  A diffusion theory for deep learning dynamics: Stochastic gradient descent exponentially favors flat minima.  In International Conference on Learning Representations.
  * Xu et al., (2022) Xu, M. et al. (2022).  Experimental Evaluation of Iterative Methods for Games.  PhD thesis, Johns Hopkins University.
  * Zhao et al., (2022) Zhao, J., Lucchi, A., Proske, F. N., Orvieto, A., and Kersting, H. (2022).  Batch size selection by stochastic optimal control.  In Has it Trained Yet? NeurIPS 2022 Workshop.
  * Zhu et al., (2019) Zhu, Z., Wu, J., Yu, B., Wu, L., and Ma, J. (2019).  The anisotropic noise in stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects.  ICML 2019.

APPENDIX

##  Appendix A ADDITIONAL RELATED WORKS

SGDA is one of the most popular algorithms for solving min-max optimization
problems that arise in machine learning. Since it does not converge even on
simple landscapes (Chen and Rockafellar,, 1997; Noor,, 2003; Gidel et al.,,
2019; Loizou et al.,, 2021), researchers have derived several advanced
extensions such as the Extragradient method (Korpelevich,, 1976) and variants
with arbitrary sampling and variance (Gorbunov et al.,, 2022), as well as
alternative optimizers such as (Stochastic) Hamiltonian Gradient Descent
(Balduzzi et al.,, 2018; Loizou et al.,, 2020).

Stochastic ExtraGradient (SEG) is a prominent extension of SGDA that has been
studied extensively in recent years. Indeed, many versions have been proposed
and studied: (Nemirovski et al.,, 2009; Juditsky et al.,, 2011) studied
Independent-Samples SEG, while Mishchenko et al., (2020) and Li et al., (2022)
showed that the average iterate of Same-Sample SEG converges to a neighbor of
the optimum. While (Chavdarova et al.,, 2019) showed that same-stepsize SEG
diverges in the unconstrained monotone case, Mishchenko et al., (2020); Hsieh
et al., (2020) focused on two-scale SEG, showcasing how this design choice is
crucial by deriving schedulers that guarantee convergence. Hsieh et al.,
(2019) studies the convergence of variations of SEG engineered to mitigate the
cost of the extra gradient. Finally, Gorbunov et al., (2022) provides a rich
analysis that encompasses several variants of SEG with different choices of
stepsizes and sampling techniques, and ends up designing new promising
methods. The latter endeavor is key for future research: As highlighted by
(Hsieh et al.,, 2019), existing min-max algorithms may be subject to
inescapable convergence failures in important cases.

Among other works, we refer the reader interested in previous analyses of
bilinear and quadratic games to (Hsieh et al.,, 2021; Li et al.,, 2022; Xu et
al.,, 2022; Chavdarova et al.,, 2023): These give a detailed presentation of
the behavior of GDA, EG and HGD, and their stochastic versions on such tasks.

We highlight that some convergence conditions and some of the convergence
bounds derived in the literature for SEG (see among others (Hsieh et al.,,
2020; Mishchenko et al.,, 2020; Hsieh et al.,, 2019; Gorbunov et al.,, 2022;
Lu,, 2022; Li et al.,, 2022)) and SHGD (see (Loizou et al.,, 2020, 2021)) are
somehow related to those we present in this paper.

##  Appendix B STOCHASTIC CALCULUS

In this section, we summarize some important results in the analysis of
Stochastic Differential Equations Mao, (2007); Øksendal, (1990). The notation
and the results in this section will be used extensively in all proofs in this
paper. We assume the reader to have some familiarity with Brownian motion and
with the definition of stochastic integral (Ch. 1.4 and 1.5 in Mao, (2007)).

###  B.1 Itô’s Lemma

We start with some notation: Let
$\left(\Omega,\mathcal{F},\\{\mathcal{F}_{t}\\}_{t\geq 0},\mathbb{P}\right)$
be a filtered probability space. We say that an event $E\in\mathcal{F}$ holds
almost surely (a.s.) in this space if $\mathbb{P}(E)=1$. We call
$\mathcal{L}^{p}([a,b],{\mathbb{R}}^{d})$, with $p>0$, the family of
${\mathbb{R}}^{d}$-valued $\mathcal{F}_{t}$-adapted processes
$\\{f_{t}\\}_{a\leq t\leq b}$ such that

$\int_{a}^{b}\|f_{t}\|^{p}dt\leq\infty.$

Moreover, we denote by $\mathcal{M}^{p}([a,b],{\mathbb{R}}^{d})$, with $p>0$,
the family of ${\mathbb{R}}^{d}$-valued processes $\\{f_{t}\\}_{a\leq t\leq
b}$ in $\mathcal{L}([a,b],{\mathbb{R}}^{d})$ such that
${\mathbb{E}}\left[\int_{a}^{b}\|f_{t}\|^{p}dt\right]\leq\infty$. We will
write $h\in\mathcal{L}^{p}\left({\mathbb{R}}_{+},{\mathbb{R}}^{d}\right)$,
with $p>0$, if $h\in\mathcal{L}^{p}\left([0,T],{\mathbb{R}}^{d}\right)$ for
every $T>0$. Similar definitions hold for matrix-valued functions using the
Frobenius norm $\|A\|:=\sqrt{\sum_{ij}|A_{ij}|^{2}}$.

Let $W=\\{W_{t}\\}_{t\geq 0}$ be a one-dimensional Brownian motion defined on
our probability space and let $X=\\{X_{t}\\}_{t\geq 0}$ be an
$\mathcal{F}_{t}$-adapted process taking values on ${\mathbb{R}}^{d}$.

######  Definition B.1.

Let the drift be
$b\in\mathcal{L}^{1}\left({\mathbb{R}}_{+},{\mathbb{R}}^{d}\right)$ and the
diffusion term be
$\sigma\in\mathcal{L}^{2}\left({\mathbb{R}}_{+},{\mathbb{R}}^{d\times
m}\right)$. $X_{t}$ is an Itô process if it takes the form

$X_{t}=x_{0}+\int_{0}^{t}b_{s}ds+\int_{0}^{t}\sigma_{s}dW_{s}.$

We shall say that $X_{t}$ has the stochastic differential

$dX_{t}=b_{t}dt+\sigma_{t}dW_{t}.$ (42)

######  Theorem B.2 (Itô’s Lemma).

Let $X_{t}$ be an Itô process with stochastic differential
$dX_{t}=b_{t}dt+\sigma_{t}dW_{t}$. Let $f\left(x,t\right)$ be twice
continuously differentiable in $x$ and continuously differentiable in $t$,
taking values in ${\mathbb{R}}$. Then $f(X_{t},t)$ is again an Itô process
with stochastic differential

$df(X_{t},t)=\partial_{t}f(X_{t},t))dt+\langle\nabla f(X_{t},t),b_{t}\rangle
dt+\frac{1}{2}\text{Tr}\left(\sigma_{t}\sigma_{t}^{\top}\nabla^{2}f(X_{t},t)\right)dt+\langle\nabla
f(X_{t},t),\sigma_{t}\rangle dW_{t}.$ (43)

###  B.2 Stochastic Differential Equations

Stochastic Differential Equations (SDEs) are equations of the form

$dX_{t}=b(X_{t},t)dt+\sigma(X_{t},t)dW_{t}.$

First of all, we need to define what it means for a stochastic process
$X=\\{X_{t}\\}_{t\geq 0}$ with values in ${\mathbb{R}}^{d}$ to solve an SDE.

######  Definition B.3.

Let $X_{t}$ be as above with deterministic initial condition $X_{0}=x_{0}$.
Assume $b:{\mathbb{R}}^{d}\times[0,T]\to{\mathbb{R}}^{d}$ and
$\sigma:{\mathbb{R}}^{d}\times[0,T]\to{\mathbb{R}}^{d\times m}$ are Borel
measurable; $X_{t}$ is called a solution to the corresponding SDE if

  1. 1.

$X_{t}$ is continuous and $\mathcal{F}_{t}$-adapted;

  2. 2.

$b\in\mathcal{L}^{1}\left([0,T],{\mathbb{R}}^{d}\right)$;

  3. 3.

$\sigma\in\mathcal{L}^{2}\left([0,T],{\mathbb{R}}^{d\times m}\right)$;

  4. 4.

For every $t\in[0,T]$

$X_{t}=x_{0}+\int_{0}^{t}b(X_{s},s)ds+\int_{0}^{t}\sigma(X_{s},s)dW(s)\ \ \
a.s.$

Moreover, the solution $X_{t}$ is said to be unique if any other solution
$X^{\star}_{t}$ is such that

$\mathbb{P}\left\\{X_{t}=X^{\star}_{t},\text{ for all }0\leq t\leq
T\right\\}=1.$

Notice that since the solution to an SDE is an Itô process, we can use Itô’s
Lemma. The following theorem gives a sufficient condition on $b$ and $\sigma$
for the existence of a solution to the corresponding SDE.

######  Theorem B.4.

Assume that there exist two positive constants $\bar{K}$ and $K$ such that

  1. 1.

(Global Lipschitz condition) for all $x,y\in{\mathbb{R}}^{d}$ and $t\in[0,T]$

$\max\\{\|b(x,t)-b(y,t)\|^{2},\
\|\sigma(x,t)-\sigma(y,t)\|^{2}\\}\leq\bar{K}\|x-y\|^{2};$

  2. 2.

(Linear growth condition) for all $x\in{\mathbb{R}}^{d}$ and $t\in[0,T]$

$\max\\{\|b(x,t)\|^{2},\ \|\sigma(x,t)\|^{2}\\}\leq K(1+\|x\|^{2}).$

Then, there exists a unique solution $X_{t}$ to the corresponding SDE, and
$X_{t}\in\mathcal{M}^{2}([0,T],{\mathbb{R}}^{d}).$

##### Numerical approximation.

Often, SDEs are solved numerically. The simplest algorithm to provide a sample
path $(\hat{x}_{k})_{k\geq 0}$ for $X_{t}$, so that $X_{k\Delta
t}\approxeq\hat{x}_{k}$ for some small $\Delta t$ and for all $k\Delta t\leq
M$ is called Euler-Maruyama (Algorithm 1). For more details on this
integration method and its approximation properties, the reader can check Mao,
(2007).

Algorithm 1 Euler-Maruyama Integration Method for SDEs

0: The drift $b$, the volatility $\sigma$, and the initial condition $x_{0}$.

Fix a stepsize $\Delta t$;

Initialize $\hat{x}_{0}=x_{0}$;

$k=0$;

while $k\leq\left\lfloor\frac{T}{\Delta t}\right\rfloor$ do

Sample some $d$-dimensional Gaussian noise $Z_{k}\sim\mathcal{N}(0,I_{d})$;

Compute $\hat{x}_{k+1}=\hat{x}_{k}+\Delta t\ b(\hat{x}_{k},k\Delta
t)+\sqrt{\Delta t}\ \sigma(\hat{x}_{k},k\Delta t)Z_{k};$

$k=k+1$;

end while

The approximated sample path $(\hat{x}_{k})_{0\leq
k\leq\left\lfloor\frac{T}{\Delta t}\right\rfloor}$.

##  Appendix C THEORETICAL FRAMEWORK - WEAK APPROXIMATION

In this section, we introduce the theoretical framework used in the paper,
together with its assumptions and notations.

First of all, many proofs will use Taylor expansions in powers of $\eta$. For
ease of notation, we introduce the shorthand that whenever we write
$\mathcal{O}\left(\eta^{\alpha}\right)$, we mean that there exists a function
$K(z)\in G$ such that the error terms are bounded by $K(z)\eta^{\alpha}$. For
example, we write

$b(z+\eta)=b_{0}(z)+\eta b_{1}(z)+\mathcal{O}\left(\eta^{2}\right)$

to mean: there exists $K\in G$ such that

$\left|b(z+\eta)-b_{0}(z)-\eta b_{1}(z)\right|\leq K(z)\eta^{2}.$

Additionally, we introduce the following shorthand:

  * •

A multi-index is $\alpha=\left(\alpha_{1},\alpha_{2},\ldots,\alpha_{n}\right)$
such that $\alpha_{j}\in\\{0,1,2,\ldots\\}$;

  * •

$|\alpha|:=\alpha_{1}+\alpha_{2}+\cdots+\alpha_{n}$;

  * •

$\alpha!:=\alpha_{1}!\alpha_{2}!\cdots\alpha_{n}!$;

  * •

For $z=\left(z_{1},z_{2},\ldots,z_{n}\right)\in\mathbb{R}^{n}$, we define
$z^{\alpha}:=z_{1}^{\alpha_{1}}z_{2}^{\alpha_{2}}\cdots z_{n}^{\alpha_{n}}$;

  * •

For a multi-index $\beta$,
$\partial_{\beta}^{|\beta|}f(z):=\frac{\partial^{|\beta|}}{\partial^{\beta_{1}}_{z_{1}}\partial^{\beta_{2}}_{z_{2}}\cdots\partial^{\beta_{n}}_{z_{n}}}f(z)$;

  * •

We also denote the partial derivative with respect to $z_{i}$ by
$\partial_{e_{i}}$.

######  Definition C.1 (G Set).

Let $G$ denote the set of continuous functions
$\mathbb{R}^{2d}\rightarrow\mathbb{R}$ of at most polynomial growth, i.e.
$g\in G$ if there exists positive integers $\nu_{1},\nu_{2}>0$ such that
$|g(z)|\leq\nu_{1}\left(1+|z|^{2\nu_{2}}\right)$, for all
$z\in\mathbb{R}^{2d}$.

The next results are inspired by Theorem 1 of Li et al., (2017) and are
derived under some regularity assumption on the function $f$.

######  Assumption C.2.

Assume that the following conditions on $f,f_{i}$, and their gradients are
satisfied: • $\nabla f,\nabla f_{i}$ satisfy a Lipschitz condition: There
exists $L>0$ such that $|\nabla f(u)-\nabla f(v)|+\sum_{i=1}^{N}\left|\nabla
f_{i}(u)-\nabla f_{i}(v)\right|\leq L|u-v|;$ • $f,f_{i}$ and its partial
derivatives up to order 7 belong to $G$; • $\nabla f,\nabla f_{i}$ satisfy a
growth condition: There exists $M>0$ such that $|\nabla
f(z)|+\sum_{i=1}^{N}\left|\nabla f_{i}(z)\right|\leq M(1+|z|).$

######  Lemma C.3 (Lemma 1 Li et al., (2017)).

Let $0<\eta<1$. Consider a stochastic process $Z_{t},t\geq 0$ satisfying the
SDE $dZ_{t}=b\left(Z_{t}\right)dt+\sqrt{\eta}\sigma\left(Z_{t}\right)dW_{t}$
with $Z_{0}=z\in\mathbb{R}^{2d}$ and $b,\sigma$ together with their
derivatives belong to $G$. Define the one-step difference $\Delta=Z_{\eta}-z$,
and indicate the $i$-th component of $\Delta$ with $\Delta_{i}$. Then we have
1.
${\mathbb{E}}\Delta_{i}=b_{i}\eta+\frac{1}{2}\left[\sum_{j=1}^{d}b_{j}\partial_{e_{j}}b_{i}\right]\eta^{2}+\mathcal{O}\left(\eta^{3}\right)\quad\forall
i=1,\ldots,2d$; 2.
${\mathbb{E}}\Delta_{i}\Delta_{j}=\left[b_{i}b_{j}+\sigma\sigma_{(ij)}^{T}\right]\eta^{2}+\mathcal{O}\left(\eta^{3}\right)\quad\forall
i,j=1,\ldots,2d$; 3.
${\mathbb{E}}\prod_{j=1}^{s}\Delta_{\left(i_{j}\right)}=\mathcal{O}\left(\eta^{3}\right)$
for all $s\geq 3,i_{j}=1,\ldots,2d$. All functions above are evaluated at $z$.

######  Theorem C.4 (Theorem 2 and Lemma 5, Mil’shtein, (1986)).

Let Assumption C.2 hold and let us define $\bar{\Delta}=z_{1}-z$ to be the
increment in the discrete-time algorithm, and indicate the $i$-th component of
$\bar{\Delta}$ with $\bar{\Delta}_{i}$. If in addition there exists
$K_{1},K_{2},K_{3},K_{4}\in G$ so that 1.
$\left|{\mathbb{E}}\Delta_{i}-{\mathbb{E}}\bar{\Delta}_{i}\right|\leq
K_{1}(z)\eta^{2},\quad\forall i=1,\ldots,2d$; 2.
$\left|{\mathbb{E}}\Delta_{i}\Delta_{j}-{\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}\right|\leq
K_{2}(z)\eta^{2},\quad\forall i,j=1,\ldots,2d$; 3.
$\left|{\mathbb{E}}\prod_{j=1}^{s}\Delta_{i_{j}}-{\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}\right|\leq
K_{3}(z)\eta^{2},\quad\forall s\geq 3,\quad\forall i_{j}\in\\{1,\ldots,2d\\}$;
4. ${\mathbb{E}}\prod_{j=1}^{3}\left|\bar{\Delta}_{i_{j}}\right|\leq
K_{4}(z)\eta^{2},\quad\forall i_{j}\in\\{1,\ldots,2d\\}$. Then, there exists a
constant $C$ so that for all $k=0,1,\ldots,N$ we have
$\left|{\mathbb{E}}g\left(Z_{k\eta}\right)-{\mathbb{E}}g\left(z_{k}\right)\right|\leq
C\eta.$

###  C.1 Formal Derivation - SGDA

In this subsection, we provide the first formal derivation of an SDE model for
SGDA. Let us consider the stochastic process $Z_{t}\in\mathbb{R}^{2d}$ defined
as the solution of

$dZ_{t}=-\eta_{t}\circ
F\left(Z_{t}\right)dt+\sqrt{\eta}(\eta_{t}1^{\top})\circ\sqrt{\Sigma\left(Z_{t}\right)}dW_{t},$
(44)

where

$\displaystyle\Sigma(z):={\mathbb{E}}\left[\left(F\left(z\right)-F_{\gamma}\left(z\right)\right)\left(F\left(z\right)-F_{\gamma}\left(z\right)\right)^{\top}\right],$
(45)

and the $\circ$ symbol represents the Hadamard product. The following theorem
guarantees that such a process is a $1$-order SDE of the discrete-time
algorithm of SGDA

$z_{k+1}=z_{k}-\eta\eta_{k}\circ F_{\gamma_{k}}\left(z_{k}\right)$ (46)

with $z_{0}:=z=(x,y)\in\mathbb{R}^{d}\times\mathbb{R}^{d}$, which is an
extension of 2.

######  Theorem C.5 (Stochastic modified equations).

Let $0<\eta<1,T>0$ and set $N=\lfloor T/\eta\rfloor$. Let
$z_{k}\in\mathbb{R}^{2d},0\leq k\leq N$ denote a sequence of SGDA iterations
defined by Eq. (46). Consider the stochastic process $Z_{t}$ defined in Eq.
(44) and fix some test function $g\in G$ and suppose that $g$ and its partial
derivatives up to order 6 belong to $G$. Then, under Assumption C.2, there
exists a constant $C>0$ independent of $\eta$ such that for all
$k=0,1,\ldots,N$, we have
$\left|{\mathbb{E}}g\left(Z_{k\eta}\right)-{\mathbb{E}}g\left(z_{k}\right)\right|\leq
C\eta.$ That is, the SDE (44) is an order $1$ weak approximation of the SGDA
iterations (46).

######  Lemma C.6.

Under the assumptions of Theorem C.5, let $0<\eta<1$ and consider $z_{k},k\geq
0$ satisfying the SGDA iterations $z_{k+1}=z_{k}-\eta\eta_{k}\circ
F_{\gamma_{k}}\left(z_{k}\right)$ with
$z_{0}:=z=(x,y)\in\mathbb{R}^{d}\times\mathbb{R}^{d}$. From the definition the
one-step difference $\bar{\Delta}=z_{1}-z$, then we have 1.
${\mathbb{E}}\bar{\Delta}_{i}=-\eta^{i}_{0}F_{i}\eta\quad\forall
i=1,\ldots,2d$; 2.
${\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}=\eta^{i}_{0}\eta^{j}_{0}F_{i}F_{j}\eta^{2}+\eta^{i}_{0}\eta^{j}_{0}\Sigma_{(ij)}\eta^{2}\quad\forall
i,j=1,\ldots,2d$; 3.
${\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}=\mathcal{O}\left(\eta^{3}\right)\quad\forall
s\geq 3,\quad i_{j}\in\\{1,\ldots,2d\\}$. All the functions above are
evaluated at $z$.

###### Proof of Lemma C.6.

First of all, we have that by definition

${\mathbb{E}}\left[z_{1}-z\right]=-\eta\eta_{0}\circ F(z),$ (47)

which implies

${\mathbb{E}}\bar{\Delta}_{i}=-\eta^{i}_{0}F_{i}\left(z\right)\eta\quad\forall
i=1,\ldots,2d.$ (48)

Second, we have that by definition

$\displaystyle{\mathbb{E}}\left[\left(z_{1}-z\right)\left(z_{1}-z\right)^{\top}\right]$
$\displaystyle=\eta^{2}\eta_{0}\circ
F(z)F(z)^{\top}\circ\eta_{0}^{\top}+\eta^{2}{\mathbb{E}}\left[\eta_{0}\circ\left(F(z)-F_{\gamma}(z)\right)\left(F(z)-F_{\gamma}(z)\right)^{\top}\circ\eta_{0}^{\top}\right]$
$\displaystyle=\eta^{2}\eta_{0}\circ
F(z)F(z)^{\top}\circ\eta_{0}^{\top}+\eta^{2}(\eta_{0}1^{\top})\circ\Sigma(z)\circ(\eta_{0}1^{\top})^{\top},$
(49)

which implies that

${\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}=\eta^{i}_{0}\eta^{j}_{0}F_{i}\left(z\right)F_{j}\left(z\right)\eta^{2}+\eta^{i}_{0}\eta^{j}_{0}\Sigma_{(ij)}\left(z\right)\eta^{2}\quad\forall
i,j=1,\ldots,2d.$ (50)

Finally, by definition

${\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}=\mathcal{O}\left(\eta^{3}\right)\quad\forall
s\geq 3,\quad i_{j}\in\\{1,\ldots,2d\\},$ (51)

which concludes our proof. ∎

###### Proof of Theorem C.5.

To prove this result, all we need to do is check the conditions in Theorem
C.4. As we apply Lemma C.3, we make the following choices:

  * •

$b(z)=-\eta_{t}\circ F(z)$;

  * •

$\sigma(z)=(\eta_{t}1^{\top})\circ\sqrt{\Sigma(z)}$.

First of all, we notice that $\forall i=1,\ldots,2d$, it holds that

  * •

${\mathbb{E}}\bar{\Delta}_{i}\overset{\text{1. Lemma
\ref{lemma:SGDA_SDE}}}{=}-\eta^{i}_{0}F_{i}\left(z\right)\eta$;

  * •

${\mathbb{E}}\Delta_{i}\overset{\text{1. Lemma
\ref{lemma:li1}}}{=}-\eta^{i}_{0}F_{i}\left(z\right)\eta+\mathcal{O}\left(\eta^{2}\right)$.

Therefore, we have that for some $K_{1}(z)\in G$,

$\left|{\mathbb{E}}\Delta_{i}-{\mathbb{E}}\bar{\Delta}_{i}\right|\leq
K_{1}(z)\eta^{2},\quad\forall i=1,\ldots,2d.$ (52)

Additionally, we notice that $\forall i,j=1,\ldots,d$, it holds that

  * •

${\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}\overset{\text{2. Lemma
\ref{lemma:SGDA_SDE}}}{=}\eta^{i}_{0}\eta^{j}_{0}F_{i}\left(z\right)F_{j}\left(z\right)\eta^{2}+\eta^{i}_{0}\eta^{j}_{0}\Sigma_{(ij)}\left(z\right)\eta^{2}$;

  * •

${\mathbb{E}}\Delta_{i}\Delta_{j}\overset{\text{2. Lemma
\ref{lemma:li1}}}{=}\eta^{i}_{0}\eta^{j}_{0}F_{i}\left(z\right)F_{j}\left(z\right)\eta^{2}+\eta^{i}_{0}\eta^{j}_{0}\Sigma_{(ij)}\left(z\right)\eta^{2}+\mathcal{O}\left(\eta^{3}\right)$.

Therefore, we have that for some $K_{2}(z)\in G$,

$\left|{\mathbb{E}}\Delta_{i}\Delta_{j}-{\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}\right|\leq
K_{2}(z)\eta^{2},\quad\forall i,j=1,\ldots,2d.$ (53)

Additionally, we notice that $\forall s\geq 3,\forall
i_{j}\in\\{1,\ldots,2d\\}$, it holds that

  * •

${\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}\overset{\text{3. Lemma
\ref{lemma:SGDA_SDE}}}{=}\mathcal{O}\left(\eta^{3}\right)$;

  * •

${\mathbb{E}}\prod_{j=1}^{s}\Delta_{i_{j}}\overset{\text{3. Lemma
\ref{lemma:li1}}}{=}\mathcal{O}\left(\eta^{3}\right)$.

Therefore, we have that for some $K_{3}(z)\in G$,

$\left|{\mathbb{E}}\prod_{j=1}^{s}\Delta_{i_{j}}-{\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}\right|\leq
K_{3}(z)\eta^{2}.$ (54)

Additionally, for some $K_{4}(z)\in G$, $\forall i_{j}\in\\{1,\ldots,d\\}$,

${\mathbb{E}}\prod_{j=1}^{3}\left|\bar{\Delta}_{\left(i_{j}\right)}\right|\overset{\text{3.
Lemma \ref{lemma:SGDA_SDE}}}{\leq}K_{4}(z)\eta^{2}.$ (55)

To conclude, Eq. (52), Eq. (53), Eq. (54), and Eq. (55) allow us to conclude
the proof. ∎

######  Corollary C.7.

Let us take the same assumptions of Theorem C.5. Additionally, let us assume
that stochastic gradients can be written as
$\nabla_{x}f_{\gamma}(z)=\nabla_{x}f(z)+U^{x}$ and
$\nabla_{y}f_{\gamma}(z)=\nabla_{y}f(z)+U^{y}$ such that $U^{x}$ and $U^{y}$
are independent noises that do not depend on $z$, whose expectation is $0$,
and whose covariance matrix is $\Sigma$. For $\eta_{t}=\mathbf{1}$, the SDE
(44) becomes $\displaystyle
dX_{t}=-\nabla_{x}f\left(Z_{t}\right)dt+\sqrt{\eta\Sigma}dW^{x}_{t},$ (56)
$\displaystyle
dY_{t}=+\nabla_{y}f\left(Z_{t}\right)dt+\sqrt{\eta\Sigma}dW^{y}_{t}.$

###### Proof of Corollary C.7.

It follows directly by the independence of the noise, the definition of the
scheduler, and the definition of the covariance matrix. ∎

###  C.2 Formal Derivation - SEG

In this subsection, we provide the first formal derivation of an SDE model for
SEG. Before presenting the proof, we introduce some notation. Let
${\boldsymbol{\gamma}}:=(\gamma^{1},\gamma^{2})$,
$\bar{F}_{{\boldsymbol{\gamma}}}(z):=\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)$, and
$\bar{F}(z):={\mathbb{E}}[\bar{F}_{{\boldsymbol{\gamma}}}(z)]$ be its
expectation. We denote the noise in $\bar{F}$ as
$\bar{\xi}_{{\boldsymbol{\gamma}}}(z):=\bar{F}_{{\boldsymbol{\gamma}}}(z)-\bar{F}(z)$.

Let us consider the stochastic process $Z_{t}\in\mathbb{R}^{2d}$ defined as
the solution of

$dZ_{t}=-F^{\scalebox{0.6}{\text{SEG}}}\left(Z_{t}\right)dt+\sqrt{\eta\Sigma^{\scalebox{0.6}{\text{SEG}}}\left(Z_{t}\right)}dW_{t},$
(57)

with

$\displaystyle F^{\scalebox{0.6}{\text{SEG}}}(z):=F(z)-\rho\bar{F}(z),$ (58)
$\displaystyle\Sigma^{\scalebox{0.6}{\text{SEG}}}(z):=\Sigma(z)+\rho\left[\bar{\Sigma}(z)+\bar{\Sigma}(z)^{\top}\right],$
(59)

where $\bar{\Sigma}(z)$ is defined as

$\displaystyle{\mathbb{E}}\left[\xi_{\gamma^{1}}(z)\bar{\xi}_{{\boldsymbol{\gamma}}}(z)^{\top}\right]={\mathbb{E}}\left[\left(F\left(z\right)-F_{\gamma^{1}}\left(z\right)\right)\left({\mathbb{E}}\left[\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)\right]-\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)\right)^{\top}\right].$ (60)

######  Theorem C.8 (Stochastic modified equations).

Let $0<\eta<1,T>0$ and set $N=\lfloor T/\eta\rfloor$. Let
$z_{k}\in\mathbb{R}^{2d},0\leq k\leq N$ denote a sequence of SEG iterations
defined by Eq. (3). Additionally, let us take
$\rho=\mathcal{O}\left(\sqrt{\eta}\right).$ (61) Consider the stochastic
process $Z_{t}$ defined in Eq. (57) and fix some test function $g\in G$ and
suppose that $g$ and its partial derivatives up to order 6 belong to $G$.
Then, under Assumption C.2, there exists a constant $C>0$ independent of
$\eta$ such that for all $k=0,1,\ldots,N$, we have
$\left|{\mathbb{E}}g\left(Z_{k\eta}\right)-{\mathbb{E}}g\left(z_{k}\right)\right|\leq
C\eta.$ That is, the SDE (57) is an order $1$ weak approximation of the SEG
iterations (3).

######  Lemma C.9.

Under the assumptions of Theorem C.8, let $0<\eta<1$ and consider $z_{k},k\geq
0$ satisfying the SEG iterations (3) $\left[\begin{array}[]{l}x_{k+1}\\\
y_{k+1}\end{array}\right]=\left[\begin{array}[]{l}x_{k}\\\
y_{k}\end{array}\right]-\eta\left[\begin{array}[]{l}+\nabla_{x}f_{\gamma^{1}_{k}}\left(x_{k}-\rho\nabla_{x}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right),y_{k}+\rho\nabla_{y}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)\right)\\\
-\nabla_{y}f_{\gamma^{1}_{k}}\left(x_{k}-\rho\nabla_{x}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right),y_{k}+\rho\nabla_{y}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)\right)\end{array}\right]$
(62) with $z_{0}:=z=(x,y)\in\mathbb{R}^{d}\times\mathbb{R}^{d}$. From the
definition the one-step difference $\bar{\Delta}=z_{1}-z$, then we have 1.
${\mathbb{E}}\bar{\Delta}_{i}=-F^{\scalebox{0.6}{\text{SEG}}}_{i}\eta+\mathcal{O}\left(\eta^{2}\right)\quad\forall
i=1,\ldots,2d$; 2.
${\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}=F^{\scalebox{0.6}{\text{SEG}}}_{i}F^{\scalebox{0.6}{\text{SEG}}}_{j}\eta^{2}+\Sigma^{\scalebox{0.6}{\text{SEG}}}_{(ij)}\eta^{2}+\mathcal{O}\left(\eta^{3}\right)\quad\forall
i,j=1,\ldots,2d$; 3.
${\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}=\mathcal{O}\left(\eta^{3}\right)\quad\forall
s\geq 3,\quad i_{j}\in\\{1,\ldots,2d\\}$. All the functions above are
evaluated at $z$.

###### Proof of Lemma C.9.

First of all, we have that by definition and using a Taylor expansion,

$\displaystyle x_{k+1}$
$\displaystyle=x_{k}-\eta\nabla_{x}f_{\gamma^{1}_{k}}\left(x_{k}-\rho\nabla_{x}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right),y_{k}+\rho\nabla_{y}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)\right)$
(63)
$\displaystyle=x_{k}-\eta\nabla_{x}f_{\gamma^{1}_{k}}\left(x_{k},y_{k}\right)+\eta\rho\nabla^{2}_{xx}f_{\gamma^{1}_{k}}\left(x_{k},y_{k}\right)\nabla_{x}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)-\eta\rho\nabla^{2}_{xy}f_{\gamma^{1}_{k}}\left(x_{k},y_{k}\right)\nabla_{y}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)+\mathcal{O}\left(\eta\rho^{2}\right),$

and

$\displaystyle y_{k+1}$
$\displaystyle=y_{k}+\eta\nabla_{y}f_{\gamma^{1}_{k}}\left(x_{k}-\rho\nabla_{x}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right),y_{k}+\rho\nabla_{y}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)\right)$
(64)
$\displaystyle=y_{k}+\eta\nabla_{y}f_{\gamma^{1}_{k}}\left(x_{k},y_{k}\right)-\eta\rho\nabla^{2}_{xy}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)\nabla_{x}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)+\eta\rho\nabla^{2}_{yy}f_{\gamma_{k}}\left(x_{k},y_{k}\right)\nabla_{y}f_{\gamma_{k}}\left(x_{k},y_{k}\right)+\mathcal{O}\left(\eta\rho^{2}\right).$

Therefore

$\displaystyle z_{1}$ $\displaystyle=z-\eta F_{\gamma^{1}}(z)+\eta\rho\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)+\mathcal{O}\left(\eta^{2}\right),$ (65)

which implies that

$\displaystyle{\mathbb{E}}\left[z_{1}-z\right]$ $\displaystyle=-\eta
F(z)+\eta\rho{\mathbb{E}}\left[\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)\right]+\mathcal{O}\left(\eta^{2}\right)$
$\displaystyle=z-\eta
F^{\scalebox{0.6}{\text{SEG}}}\left(z\right)+\mathcal{O}\left(\eta^{2}\right),$
(66)

where
$F^{\scalebox{0.6}{\text{SEG}}}\left(z\right):=F(z)-\rho{\mathbb{E}}\left[\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)\right]$, which in turn implies that

${\mathbb{E}}\bar{\Delta}_{i}=-F^{\scalebox{0.6}{\text{SEG}}}_{i}\left(z\right)\eta+\mathcal{O}\left(\eta^{2}\right)\quad\forall
i=1,\ldots,2d.$ (67)

Second, we have that

$\displaystyle{\mathbb{E}}\left[\left(z_{1}-z\right)\left(z_{1}-z\right)^{\top}\right]$
$\displaystyle=\eta^{2}\left[\left(F^{\scalebox{0.6}{\text{SEG}}}(z)\right)\left(F^{\scalebox{0.6}{\text{SEG}}}(z)\right)^{\top}\right]$
$\displaystyle+\eta^{2}{\mathbb{E}}\left[\left(F(z)-F_{\gamma^{1}}(z)\right)\left(F(z)-F_{\gamma^{1}}(z)\right)^{\top}\right]$
$\displaystyle+\eta^{2}\rho\left({\mathbb{E}}\left[\left(F\left(z\right)-F_{\gamma^{1}}\left(z\right)\right)\left({\mathbb{E}}\left[\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)\right]-\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)\right)^{\top}\right]\right)$
$\displaystyle+\eta^{2}\rho\left({\mathbb{E}}\left[\left(F\left(z\right)-F_{\gamma^{1}}\left(z\right)\right)\left({\mathbb{E}}\left[\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)\right]-\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)\right)^{\top}\right]\right)^{\top}+\mathcal{O}\left(\eta^{3}\right)$
$\displaystyle=\eta^{2}\left[\left(F^{\scalebox{0.6}{\text{SEG}}}(z)\right)\left(F^{\scalebox{0.6}{\text{SEG}}}(z)\right)^{\top}\right]+\eta^{2}\Sigma^{\scalebox{0.6}{\text{SEG}}}(z)+\mathcal{O}\left(\eta^{3}\right),$
(68)

which implies that

${\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}=F^{\scalebox{0.6}{\text{SEG}}}_{i}\left(z\right)F^{\scalebox{0.6}{\text{SEG}}}_{j}\left(z\right)\eta^{2}+\Sigma^{\scalebox{0.6}{\text{SEG}}}_{(ij)}\left(z\right)\eta^{2}+\mathcal{O}\left(\eta^{3}\right)\quad\forall
i,j=1,\ldots,2d.$ (69)

Finally, by definition

${\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}=\mathcal{O}\left(\eta^{3}\right)\quad\forall
s\geq 3,\quad i_{j}\in\\{1,\ldots,2d\\},$ (70)

which concludes our proof. ∎

###### Proof of Theorem C.8.

To prove this result, all we need to do is check the conditions in Theorem
C.4. As we apply Lemma C.3, we make the following choices:

  * •

$b(z)=-F^{\scalebox{0.6}{\text{SEG}}}(z)$;

  * •

$\sigma(z)=\Sigma^{\scalebox{0.6}{\text{SEG}}}(z)^{\frac{1}{2}}$.

First of all, we notice that $\forall i=1,\ldots,2d$, it holds that

  * •

${\mathbb{E}}\bar{\Delta}_{i}\overset{\text{1. Lemma
\ref{lemma:SEG_SDE}}}{=}-F^{\scalebox{0.6}{\text{SEG}}}_{i}\left(z\right)\eta+\mathcal{O}\left(\eta^{2}\right)$;

  * •

${\mathbb{E}}\Delta_{i}\overset{\text{1. Lemma
\ref{lemma:li1}}}{=}-F^{\scalebox{0.6}{\text{SEG}}}_{i}\left(z\right)\eta+\mathcal{O}\left(\eta^{2}\right)$.

Therefore, we have that for some $K_{1}(z)\in G$,

$\left|{\mathbb{E}}\Delta_{i}-{\mathbb{E}}\bar{\Delta}_{i}\right|\leq
K_{1}(z)\eta^{2},\quad\forall i=1,\ldots,2d.$ (71)

Additionally, we notice that $\forall i,j=1,\ldots,d$, it holds that

  * •

${\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}\overset{\text{2. Lemma
\ref{lemma:SEG_SDE}}}{=}F^{\scalebox{0.6}{\text{SEG}}}_{i}\left(z\right)F^{\scalebox{0.6}{\text{SEG}}}_{j}\left(z\right)\eta^{2}+\Sigma^{\scalebox{0.6}{\text{SEG}}}_{(ij)}\left(z\right)\eta^{2}+\mathcal{O}\left(\eta^{3}\right)$;

  * •

${\mathbb{E}}\Delta_{i}\Delta_{j}\overset{\text{2. Lemma
\ref{lemma:li1}}}{=}F^{\scalebox{0.6}{\text{SEG}}}_{i}\left(z\right)F^{\scalebox{0.6}{\text{SEG}}}_{j}\left(z\right)\eta^{2}+\Sigma^{\scalebox{0.6}{\text{SEG}}}_{(ij)}\left(z\right)\eta^{2}+\mathcal{O}\left(\eta^{3}\right)$.

Therefore, we have that for some $K_{2}(z)\in G$,

$\left|{\mathbb{E}}\Delta_{i}\Delta_{j}-{\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}\right|\leq
K_{2}(z)\eta^{2},\quad\forall i,j=1,\ldots,2d.$ (72)

Additionally, we notice that $\forall s\geq 3,\forall
i_{j}\in\\{1,\ldots,2d\\}$, it holds that

  * •

${\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}\overset{\text{3. Lemma
\ref{lemma:SEG_SDE}}}{=}\mathcal{O}\left(\eta^{3}\right)$;

  * •

${\mathbb{E}}\prod_{j=1}^{s}\Delta_{i_{j}}\overset{\text{3. Lemma
\ref{lemma:li1}}}{=}\mathcal{O}\left(\eta^{3}\right)$.

Therefore, we have that for some $K_{3}(z)\in G$,

$\left|{\mathbb{E}}\prod_{j=1}^{s}\Delta_{i_{j}}-{\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}\right|\leq
K_{3}(z)\eta^{2}.$ (73)

Additionally, for some $K_{4}(z)\in G$, $\forall i_{j}\in\\{1,\ldots,d\\}$,

${\mathbb{E}}\prod_{j=1}^{3}\left|\bar{\Delta}_{\left(i_{j}\right)}\right|\overset{\text{3.
Lemma \ref{lemma:SEG_SDE}}}{\leq}K_{4}(z)\eta^{2}.$ (74)

Finally, Eq. (71), Eq. (72), Eq. (73), and Eq. (74) allow us to conclude the
proof.

∎

######  Corollary C.10.

Let us take the same assumptions of Theorem C.8. Additionally, let us assume
that $\gamma^{1}=\gamma^{2}=\gamma$, the stochastic gradients can be written
as $\nabla_{x}f_{\gamma}(z)=\nabla_{x}f(z)+U^{x}$ and
$\nabla_{y}f_{\gamma}(z)=\nabla_{y}f(z)+U^{y}$ such that $U^{x}$ and $U^{y}$
are independent noises that do not depend on $z$, whose expectation is $0$,
and whose covariance matrix is $\Sigma$. Therefore, the SDE (57) is
$\displaystyle dZ_{t}$ $\displaystyle=-F(Z_{t})+\rho\nabla
F(Z_{t})F(Z_{t})dt+\sqrt{\eta}\left(\mathbf{I}_{2d}-\rho\nabla
F\left(Z_{t}\right)\right)\sqrt{\Sigma}dW_{t}.$ (75)

###### Proof of Corollary C.10.

First of all, we notice that

$\displaystyle F(z)-\rho{\mathbb{E}}\left[\nabla
F_{\gamma}(z)F_{\gamma}(z)\right]$
$\displaystyle=F(z)-\rho{\mathbb{E}}\left[\nabla F(z)F_{\gamma}(z)\right]$
$\displaystyle=F(z)-\rho\nabla F(z)F(z).$ (76)

Second, based on our assumption of the noise structure, we can rewrite Eq.
(60) of the matrix $\Sigma^{\scalebox{0.6}{\text{SEG}}}$ as

$\displaystyle\Sigma^{\scalebox{0.6}{\text{SEG}}}$
$\displaystyle=\eta^{2}{\mathbb{E}}\left[\left(F(z)-F_{\gamma}(z)\right)\left(F(z)-F_{\gamma}(z)\right)^{\top}\right]$
$\displaystyle+\eta^{2}\rho\left({\mathbb{E}}\left[\left(F\left(z\right)-F_{\gamma}\left(z\right)\right)\left({\mathbb{E}}\left[\nabla
F_{\gamma}(z)F_{\gamma}(z)\right]-\nabla
F_{\gamma}(z)F_{\gamma}(z)\right)^{\top}\right]\right)$
$\displaystyle+\eta^{2}\rho\left({\mathbb{E}}\left[\left(F\left(z\right)-F_{\gamma}\left(z\right)\right)\left({\mathbb{E}}\left[\nabla
F_{\gamma}(z)F_{\gamma}(z)\right]-\nabla
F_{\gamma}(z)F_{\gamma}(z)\right)^{\top}\right]\right)^{\top}+\mathcal{O}\left(\eta^{3}\right)$
$\displaystyle=\eta^{2}{\mathbb{E}}\left[\left(F(z)-F_{\gamma}(z)\right)\left(F(z)-F_{\gamma}(z)\right)^{\top}\right]$
$\displaystyle+\eta^{2}\rho\left({\mathbb{E}}\left[\left(F\left(z\right)-F_{\gamma}\left(z\right)\right)\left({\mathbb{E}}\left[\nabla
F(z)F_{\gamma}(z)\right]-\nabla F(z)F_{\gamma}(z)\right)^{\top}\right]\right)$
$\displaystyle+\eta^{2}\rho\left({\mathbb{E}}\left[\left(F\left(z\right)-F_{\gamma}\left(z\right)\right)\left({\mathbb{E}}\left[\nabla
F(z)F_{\gamma}(z)\right]-\nabla
F(z)F_{\gamma}(z)\right)^{\top}\right]\right)^{\top}+\mathcal{O}\left(\eta^{3}\right)$
$\displaystyle=\eta^{2}\left(\Sigma+\rho\Sigma\nabla
F\left(z\right)^{\top}+\rho\nabla
F\left(z\right)\Sigma\right)+\mathcal{O}\left(\eta^{3}\right).$ (77)

By observing that $(\mathbf{I}_{2d}-\rho\nabla
F\left(z\right))\sqrt{\Sigma}\sqrt{\Sigma}(\mathbf{I}_{2d}-\rho\nabla
F\left(z\right)^{\top})=\Sigma+\rho\Sigma\nabla
F\left(z\right)^{\top}+\rho\nabla
F\left(z\right)\Sigma+\mathcal{O}\left(\eta\right)$, we conclude the proof. ∎

######  Corollary C.11.

Let us take the same assumptions of Theorem C.8. Additionally, let us assume
that $\gamma^{1}$ and $\gamma^{2}$, are independent and the stochastic
gradients can be written as
$\nabla_{x}f_{\gamma^{i}}(z)=\nabla_{x}f(z)+U_{x}^{i}$ and
$\nabla_{y}f_{\gamma^{i}}(z)=\nabla_{y}f(z)+U_{y}^{i}$ such that $U_{x}^{i}$
and $U_{y}^{i}$ are independent noises that do not depend on $z$, whose
expectation is $0$, and whose covariance matrix is $\Sigma$. Therefore, the
SDE (57) is $\displaystyle dZ_{t}$ $\displaystyle=-F(Z_{t})+\rho\nabla
F(Z_{t})F(Z_{t})dt+\sqrt{\eta\Sigma}dW_{t}.$ (78)

###### Proof of Corollary C.11.

First of all, we notice that

$\displaystyle F(z)-\rho{\mathbb{E}}\left[\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)\right]=F(z)-\rho\nabla F(z)F(z).$ (79)

Second, based on our assumption of the noise structure, we can rewrite Eq.
(60) of the matrix $\Sigma^{\scalebox{0.6}{\text{SEG}}}$ as

$\displaystyle\Sigma^{\scalebox{0.6}{\text{SEG}}}$
$\displaystyle=\eta^{2}{\mathbb{E}}\left[\left(F(z)-F_{\gamma^{1}}(z)\right)\left(F(z)-F_{\gamma^{1}}(z)\right)^{\top}\right]$
$\displaystyle+\eta^{2}\rho\left({\mathbb{E}}\left[\left(F\left(z\right)-F_{\gamma^{1}}\left(z\right)\right)\left(\nabla
F(z)F(z)-\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)\right)^{\top}\right]\right)$
$\displaystyle+\eta^{2}\rho\left({\mathbb{E}}\left[\left(F\left(z\right)-F_{\gamma^{1}}\left(z\right)\right)\left(\nabla
F(z)F(z)-\nabla
F_{\gamma^{1}}(z)F_{\gamma^{2}}(z)\right)^{\top}\right]\right)^{\top}+\mathcal{O}\left(\eta^{3}\right)$
$\displaystyle=\eta^{2}{\mathbb{E}}\left[\left(F(z)-F_{\gamma^{1}}(z)\right)\left(F(z)-F_{\gamma^{1}}(z)\right)^{\top}\right]$
$\displaystyle+\eta^{2}\rho\left({\mathbb{E}}\left[\left(F\left(z\right)-F_{\gamma^{1}}\left(z\right)\right)\left(\nabla
F(z)F(z)-\nabla F(z)F_{\gamma^{2}}(z)\right)^{\top}\right]\right)$
$\displaystyle+\eta^{2}\rho\left({\mathbb{E}}\left[\left(F\left(z\right)-F_{\gamma^{1}}\left(z\right)\right)\left(\nabla
F(z)F(z)-\nabla
F(z)F_{\gamma^{2}}(z)\right)^{\top}\right]\right)^{\top}+\mathcal{O}\left(\eta^{3}\right)$
$\displaystyle=\eta^{2}\Sigma+\mathcal{O}\left(\eta^{3}\right),$ (80)

which concludes the proof.

∎

####  C.2.1 Continuous-time SEG is equivalent to SGDA if
$\rho=\mathcal{O}(\eta)$

In this subsection, we provide a formal proof that if
$\rho=\mathcal{O}(\eta)$, the first-order weak approximation of SEG is the
same as that of SGDA. This is consistent with the ODE literature on ODEs for
these models (Chavdarova et al.,, 2023; Lu,, 2022).

We will consider the stochastic process $Z_{t}\in\mathbb{R}^{2d}$ defined as
the solution of

$dZ_{t}=-F\left(Z_{t}\right)dt+\sqrt{\eta\Sigma}dW_{t}.$ (81)

######  Theorem C.12 (Stochastic modified equations).

Let $0<\eta<1,T>0$ and set $N=\lfloor T/\eta\rfloor$. Let
$z_{k}\in\mathbb{R}^{2d},0\leq k\leq N$ denote a sequence of SEG iterations
defined by Eq. (3). Additionally, let us take
$\rho=\mathcal{O}\left(\eta\right).$ (82) Consider the stochastic process
$Z_{t}$ defined in Eq. (81) and fix some test function $g\in G$ and suppose
that $g$ and its partial derivatives up to order 6 belong to $G$. Then, under
Assumption C.2, there exists a constant $C>0$ independent of $\eta$ such that
for all $k=0,1,\ldots,N$, we have
$\left|{\mathbb{E}}g\left(Z_{k\eta}\right)-{\mathbb{E}}g\left(z_{k}\right)\right|\leq
C\eta.$ That is, the SDE (81) is an order $1$ weak approximation of the SEG
iterations (3).

######  Lemma C.13.

Under the assumptions of Theorem C.12, let $0<\eta<1$ and consider
$z_{k},k\geq 0$ satisfying the SEG iterations (3)
$\left[\begin{array}[]{l}x_{k+1}\\\
y_{k+1}\end{array}\right]=\left[\begin{array}[]{l}x_{k}\\\
y_{k}\end{array}\right]-\eta\left[\begin{array}[]{l}+\nabla_{x}f_{\gamma^{1}_{k}}\left(x_{k}-\rho\nabla_{x}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right),y_{k}+\rho\nabla_{y}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)\right)\\\
-\nabla_{y}f_{\gamma^{1}_{k}}\left(x_{k}-\rho\nabla_{x}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right),y_{k}+\rho\nabla_{y}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)\right)\end{array}\right]$
(83) with $z_{0}:=z=(x,y)\in\mathbb{R}^{d}\times\mathbb{R}^{d}$. From the
definition the one-step difference $\bar{\Delta}=z_{1}-z$, then we have 1.
${\mathbb{E}}\bar{\Delta}_{i}=-F_{i}\left(z\right)\eta+\mathcal{O}\left(\eta^{2}\right)\quad\forall
i=1,\ldots,2d$; 2.
${\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}=F_{i}\left(z\right)F_{j}\left(z\right)\eta^{2}+\Sigma_{(ij)}\left(z\right)\eta^{2}+\mathcal{O}\left(\eta^{3}\right)\quad\forall
i,j=1,\ldots,2d$; 3.
${\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}=\mathcal{O}\left(\eta^{3}\right)\quad\forall
s\geq 3,\quad i_{j}\in\\{1,\ldots,2d\\}.$ All the functions above are
evaluated at $z$.

###### Proof of Lemma C.13.

First of all, we have that by definition and using a Taylor expansion,

$\displaystyle x_{k+1}$
$\displaystyle=x_{k}-\eta\nabla_{x}f_{\gamma^{1}_{k}}\left(x_{k}-\rho\nabla_{x}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right),y_{k}+\rho\nabla_{y}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)\right)$
(84)
$\displaystyle=x_{k}-\eta\nabla_{x}f_{\gamma^{1}_{k}}\left(x_{k},y_{k}\right)+\eta\rho\nabla^{2}_{xx}f_{\gamma^{1}_{k}}\left(x_{k},y_{k}\right)\nabla_{x}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)-\eta\rho\nabla^{2}_{xy}f_{\gamma^{1}_{k}}\left(x_{k},y_{k}\right)\nabla_{y}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)+\mathcal{O}\left(\eta\rho^{2}\right),$

and

$\displaystyle y_{k+1}$
$\displaystyle=y_{k}+\eta\nabla_{y}f_{\gamma^{1}_{k}}\left(x_{k}-\rho\nabla_{x}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right),y_{k}+\rho\nabla_{y}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)\right)$
(85)
$\displaystyle=y_{k}+\eta\nabla_{y}f_{\gamma^{1}_{k}}\left(x_{k},y_{k}\right)-\eta\rho\nabla^{2}_{xy}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)\nabla_{x}f_{\gamma^{2}_{k}}\left(x_{k},y_{k}\right)+\eta\rho\nabla^{2}_{yy}f_{\gamma_{k}}\left(x_{k},y_{k}\right)\nabla_{y}f_{\gamma_{k}}\left(x_{k},y_{k}\right)+\mathcal{O}\left(\eta\rho^{2}\right).$

Therefore

$\displaystyle z_{1}$ $\displaystyle=z-\eta
F_{\gamma^{1}}(z)+\mathcal{O}\left(\eta^{2}\right),$ (86)

which implies that

$\displaystyle{\mathbb{E}}\left[z_{k+1}-z_{k}\right]$ $\displaystyle=-\eta
F(z_{k})+\mathcal{O}\left(\eta^{2}\right),$ (87)

which in turn implies that

${\mathbb{E}}\bar{\Delta}_{i}=-F_{i}\left(z\right)\eta+\mathcal{O}\left(\eta^{2}\right)\quad\forall
i=1,\ldots,2d.$ (88)

Second, we have that

$\displaystyle{\mathbb{E}}\left[\left(z_{1}-z\right)\left(z_{1}-z\right)^{\top}\right]$
$\displaystyle=\eta^{2}\left[\left(F(z)\right)\left(F(z)\right)^{\top}\right]+\eta^{2}\Sigma(z)+\mathcal{O}\left(\eta^{3}\right),$
(89)

which implies that

${\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}=F_{i}\left(z\right)F_{j}\left(z\right)\eta^{2}+\Sigma_{(ij)}\left(z\right)\eta^{2}+\mathcal{O}\left(\eta^{3}\right)\quad\forall
i,j=1,\ldots,2d.$ (90)

Finally, by definition,

${\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}=\mathcal{O}\left(\eta^{3}\right)\quad\forall
s\geq 3,\quad i_{j}\in\\{1,\ldots,2d\\},$ (91)

which concludes our proof. ∎

###### Proof of Theorem C.12.

To prove this result, all we need to do is check the conditions in Theorem
C.4. As we apply Lemma C.3, we make the following choices:

  * •

$b(z)=-F(z)$;

  * •

$\sigma(z)=\Sigma(z)^{\frac{1}{2}}$.

First of all, we notice that $\forall i=1,\ldots,2d$, it holds that

  * •

${\mathbb{E}}\bar{\Delta}_{i}\overset{\text{1. Lemma
\ref{lemma:SEG_SDE_small_rho}}}{=}-F_{i}\left(z\right)\eta+\mathcal{O}\left(\eta^{2}\right)$;

  * •

${\mathbb{E}}\Delta_{i}\overset{\text{1. Lemma
\ref{lemma:li1}}}{=}-F_{i}\left(z\right)\eta+\mathcal{O}\left(\eta^{2}\right)$.

Therefore, we have that for some $K_{1}(z)\in G$,

$\left|{\mathbb{E}}\Delta_{i}-{\mathbb{E}}\bar{\Delta}_{i}\right|\leq
K_{1}(z)\eta^{2},\quad\forall i=1,\ldots,2d.$ (92)

Additionally, we notice that $\forall i,j=1,\ldots,d$, it holds that

  * •

${\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}\overset{\text{2. Lemma
\ref{lemma:SEG_SDE_small_rho}}}{=}F_{i}\left(z\right)F_{j}\left(z\right)\eta^{2}+\Sigma_{(ij)}\left(z\right)\eta^{2}+\mathcal{O}\left(\eta^{3}\right)$;

  * •

${\mathbb{E}}\Delta_{i}\Delta_{j}\overset{\text{2. Lemma
\ref{lemma:li1}}}{=}F_{i}\left(z\right)F_{j}\left(z\right)\eta^{2}+\Sigma_{(ij)}\left(z\right)\eta^{2}+\mathcal{O}\left(\eta^{3}\right)$.

Therefore, we have that for some $K_{2}(z)\in G$,

$\left|{\mathbb{E}}\Delta_{i}\Delta_{j}-{\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}\right|\leq
K_{2}(z)\eta^{2},\quad\forall i,j=1,\ldots,2d.$ (93)

Additionally, we notice that $\forall s\geq 3,\forall
i_{j}\in\\{1,\ldots,2d\\}$, it holds that

  * •

${\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}\overset{\text{3. Lemma
\ref{lemma:SEG_SDE_small_rho}}}{=}\mathcal{O}\left(\eta^{3}\right)$;

  * •

${\mathbb{E}}\prod_{j=1}^{s}\Delta_{i_{j}}\overset{\text{3. Lemma
\ref{lemma:li1}}}{=}\mathcal{O}\left(\eta^{3}\right)$.

Therefore, we have that for some $K_{3}(z)\in G$

$\left|{\mathbb{E}}\prod_{j=1}^{s}\Delta_{i_{j}}-{\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}\right|\leq
K_{3}(z)\eta^{2}.$ (94)

Additionally, for some $K_{4}(z)\in G$, $\forall i_{j}\in\\{1,\ldots,d\\}$

${\mathbb{E}}\prod_{j=1}^{3}\left|\bar{\Delta}_{\left(i_{j}\right)}\right|\overset{\text{3.
Lemma \ref{lemma:SEG_SDE_small_rho}}}{\leq}K_{4}(z)\eta^{2}.$ (95)

Finally, Eq. (92), Eq. (93), Eq. (94), and Eq. (95) allow us to conclude the
proof.

∎

###  C.3 Formal Derivation - SHGD

In this subsection, we present the first formal derivation of an SDE model for
SHGD. We will consider the stochastic process $Z_{t}\in\mathbb{R}^{d}$ defined
as the solution of

$dZ_{t}=-F^{\scalebox{0.6}{\text{SHGD}}}\left(Z_{t}\right)dt+\sqrt{\eta\Sigma^{\scalebox{0.6}{\text{SHGD}}}\left(Z_{t}\right)}dW_{t}.$
(96)

with

$\displaystyle
F^{\scalebox{0.6}{\text{SHGD}}}(z):=\nabla{\mathbb{E}}\left[\mathcal{H}_{{\boldsymbol{\gamma}}}\left(z\right)\right],$
(97)
$\displaystyle\Sigma^{\scalebox{0.6}{\text{SHGD}}}(z):={\mathbb{E}}\left[\hat{\xi}_{\boldsymbol{\gamma}}(z)\hat{\xi}_{\boldsymbol{\gamma}}(z)^{\top}\right],$
(98)
$\displaystyle\hat{\xi}_{\boldsymbol{\gamma}}(z)=F^{\scalebox{0.6}{\text{SHGD}}}(z)-\nabla\mathcal{H}_{{\boldsymbol{\gamma}}}\left(z\right).$
(99)

We remind the following equalities that will come in handy in the subsequent
proofs:

$\displaystyle\Sigma^{\scalebox{0.6}{\text{SHGD}}}(z)={\mathbb{E}}\left[\left(\nabla{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]-\nabla\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right)\left(\nabla{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]-\nabla\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right)^{\top}\right],$
(100)
${\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]={\mathbb{E}}\left[\frac{F_{\gamma^{1}}^{\top}\left(z\right)F_{\gamma^{2}}\left(z\right)}{2}\right],\quad\text{and}\quad{\mathbb{E}}\left[\nabla\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]={\mathbb{E}}\left[\frac{F_{\gamma^{1}}^{\top}\left(z\right)\nabla
F_{\gamma^{2}}\left(z\right)+F_{\gamma^{2}}^{\top}\left(z\right)\nabla
F_{\gamma^{1}}\left(z\right)}{2}\right].$ (101)

######  Theorem C.14 (Stochastic modified equations).

Let $0<\eta<1,T>0$ and set $N=\lfloor T/\eta\rfloor$. Let
$z_{k}\in\mathbb{R}^{2d},0\leq k\leq N$ denote a sequence of SHGD iterations
defined by Eq. (4). Consider the stochastic process $Z_{t}$ defined in Eq.
(96) and fix some test function $g\in G$ and suppose that $g$ and its partial
derivatives up to order 6 belong to $G$. Then, under Assumption C.2, there
exists a constant $C>0$ independent of $\eta$ such that for all
$k=0,1,\ldots,N$, we have
$\left|{\mathbb{E}}g\left(Z_{k\eta}\right)-{\mathbb{E}}g\left(z_{k}\right)\right|\leq
C\eta.$ That is, the SDE (96) is an order $1$ weak approximation of the SHGD
iterations (4).

######  Lemma C.15.

Under the assumptions of Theorem C.14, let $0<\eta<1$ and consider
$z_{k},k\geq 0$ satisfying the SHGD iterations (4)
$z_{k+1}=z_{k}-\eta\nabla\mathcal{H}_{\gamma^{1}_{k}\gamma^{2}_{k}}\left(z_{k}\right)$
with $z_{0}:=z=(x,y)\in\mathbb{R}^{d}\times\mathbb{R}^{d}$. From the
definition the one-step difference $\bar{\Delta}=z_{1}-z$, then we have 1.
${\mathbb{E}}\bar{\Delta}_{i}=-\partial_{e_{i}}{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\right]\eta\quad\forall
i=1,\ldots,2d$; 2.
${\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}=\partial_{e_{i}}{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\right]\partial_{e_{j}}{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\right]\eta^{2}+\Sigma^{\scalebox{0.6}{\text{SHGD}}}_{(ij)}\eta^{2}\quad\forall
i,j=1,\ldots,2d$; 3.
${\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}=\mathcal{O}\left(\eta^{3}\right)\quad\forall
s\geq 3,\quad i_{j}\in\\{1,\ldots,2d\\}.$ All the functions above are
evaluated at $z$.

###### Proof of Lemma C.15.

First of all, we have that by definition

${\mathbb{E}}\left[z_{1}-z\right]=-\eta\nabla{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right],$
(102)

which implies

${\mathbb{E}}\bar{\Delta}_{i}=-\partial_{e_{i}}{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]\eta\quad\forall
i=1,\ldots,2d.$ (103)

Second, we have that by definition

$\displaystyle{\mathbb{E}}\left[\left(z_{1}-z\right)\left(z_{1}-z\right)^{\top}\right]$
$\displaystyle=\eta^{2}\left[\nabla{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]\nabla{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]^{\top}\right]$
$\displaystyle+\eta^{2}{\mathbb{E}}\left[\left(\nabla{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]-\nabla\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right)\left(\nabla{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]-\nabla\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right)^{\top}\right]$
$\displaystyle=\eta^{2}\left[\nabla{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]\nabla{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]^{\top}\right]+\eta^{2}\Sigma^{\scalebox{0.6}{\text{SHGD}}}(z),$
(104)

which implies that

${\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}=\partial_{e_{i}}{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]\partial_{e_{j}}{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]\eta^{2}+\Sigma^{\scalebox{0.6}{\text{SHGD}}}_{(ij)}\left(z\right)\eta^{2}\quad\forall
i,j=1,\ldots,2d.$ (105)

Finally, by definition

${\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}=\mathcal{O}\left(\eta^{3}\right)\quad\forall
s\geq 3,\quad i_{j}\in\\{1,\ldots,2d\\},$ (106)

which concludes our proof. ∎

###### Proof of Theorem C.14.

To prove this result, all we need to do is check the conditions in Theorem
C.4. As we apply Lemma C.3, we make the following choices:

  * •

$b(z)=-\nabla{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]$;

  * •

$\sigma(z)=\Sigma^{\scalebox{0.6}{\text{SHGD}}}(z)^{\frac{1}{2}}$.

First of all, we notice that $\forall i=1,\ldots,2d$, it holds that

  * •

${\mathbb{E}}\bar{\Delta}_{i}\overset{\text{1. Lemma
\ref{lemma:SHGD_SDE}}}{=}-\partial_{e_{i}}{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]\eta$;

  * •

${\mathbb{E}}\Delta_{i}\overset{\text{1. Lemma
\ref{lemma:li1}}}{=}-\partial_{e_{i}}{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]\eta+\mathcal{O}\left(\eta^{2}\right)$.

Therefore, we have that for some $K_{1}(z)\in G$,

$\left|{\mathbb{E}}\Delta_{i}-{\mathbb{E}}\bar{\Delta}_{i}\right|\leq
K_{1}(z)\eta^{2},\quad\forall i=1,\ldots,2d.$ (107)

Additionally, we notice that $\forall i,j=1,\ldots,d$, it holds that

  * •

${\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}\overset{\text{2. Lemma
\ref{lemma:SHGD_SDE}}}{=}\partial_{e_{i}}{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]\partial_{e_{j}}{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]\eta^{2}+\Sigma^{\scalebox{0.6}{\text{SHGD}}}_{(ij)}\left(z\right)\eta^{2}$;

  * •

${\mathbb{E}}\Delta_{i}\Delta_{j}\overset{\text{2. Lemma
\ref{lemma:li1}}}{=}\partial_{e_{i}}{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]\partial_{e_{j}}{\mathbb{E}}\left[\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]\eta^{2}+\Sigma^{\scalebox{0.6}{\text{SHGD}}}_{(ij)}\left(z\right)\eta^{2}+\mathcal{O}\left(\eta^{3}\right)$.

Therefore, we have that for some $K_{2}(z)\in G$,

$\left|{\mathbb{E}}\Delta_{i}\Delta_{j}-{\mathbb{E}}\bar{\Delta}_{i}\bar{\Delta}_{j}\right|\leq
K_{2}(z)\eta^{2},\quad\forall i,j=1,\ldots,2d.$ (108)

Additionally, we notice that $\forall s\geq 3,\forall
i_{j}\in\\{1,\ldots,2d\\}$, it holds that

  * •

${\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}\overset{\text{3. Lemma
\ref{lemma:SHGD_SDE}}}{=}\mathcal{O}\left(\eta^{3}\right)$;

  * •

${\mathbb{E}}\prod_{j=1}^{s}\Delta_{i_{j}}\overset{\text{3. Lemma
\ref{lemma:li1}}}{=}\mathcal{O}\left(\eta^{3}\right)$.

Therefore, we have that for some $K_{3}(z)\in G$,

$\left|{\mathbb{E}}\prod_{j=1}^{s}\Delta_{i_{j}}-{\mathbb{E}}\prod_{j=1}^{s}\bar{\Delta}_{i_{j}}\right|\leq
K_{3}(z)\eta^{2}.$ (109)

Additionally, for some $K_{4}(z)\in G$, $\forall i_{j}\in\\{1,\ldots,d\\}$,

${\mathbb{E}}\prod_{j=1}^{3}\left|\bar{\Delta}_{\left(i_{j}\right)}\right|\overset{\text{3.
Lemma \ref{lemma:SHGD_SDE}}}{\leq}K_{4}(z)\eta^{2}.$ (110)

Finally, Eq. (107), Eq. (108), Eq. (109), and Eq. (110) allow us to conclude
the proof.

∎

######  Corollary C.16.

Under the assumptions of Theorem C.14. Additionally, let us assume that
$\gamma^{1}=\gamma^{2}=\gamma$, the stochastic gradients are
$\nabla_{x}f_{\gamma}(z)=\nabla_{x}f(z)+U^{x}$ and
$\nabla_{y}f_{\gamma}(z)=\nabla_{y}f(z)+U^{y}$ such that $U^{x}$ and $U^{y}$
are independent noises that do not depend on $z$, whose expectation is $0$,
and whose covariance matrix is $\Sigma$. Therefore, the SDE is:
$dZ_{t}=-\nabla\mathcal{H}\left(Z_{t}\right)dt+\sqrt{\eta}\nabla^{2}f\left(Z_{t}\right)\sqrt{\Sigma}dW_{t}.$
(111)

###### Proof of Corollary C.16.

First of all, we notice that

$\displaystyle{\mathbb{E}}\left[\mathcal{H}_{\gamma}\left(Z_{t}\right)\right]$
$\displaystyle={\mathbb{E}}\left[\frac{\lVert\nabla_{x}f_{\gamma}\left(Z_{t}\right)\rVert_{2}^{2}+\lVert\nabla_{y}f_{\gamma}\left(Z_{t}\right)\rVert_{2}^{2}}{2}\right]={\mathbb{E}}\left[\frac{\lVert\nabla_{x}f\left(Z_{t}\right)\rVert_{2}^{2}+\lVert\nabla_{y}f\left(Z_{t}\right)\rVert_{2}^{2}}{2}\right]$
$\displaystyle+\frac{{\mathbb{E}}\left[(U^{x})(U^{x})^{\top}\right]+{\mathbb{E}}\left[(U^{y})(U^{y})^{\top}\right]}{2}=\mathcal{H}\left(Z_{t}\right)+\frac{{\mathbb{E}}\left[(U^{x})(U^{x})^{\top}\right]+{\mathbb{E}}\left[(U^{y})(U^{y})^{\top}\right]}{2}.$
(112)

Since
$\frac{{\mathbb{E}}\left[(U^{x})(U^{x})^{\top}\right]+{\mathbb{E}}\left[(U^{y})(U^{y})^{\top}\right]}{2}$
is independent on $z$, we ignore it as its gradient is $0$.

Second, based on our assumption of the noise structure, we can rewrite Eq.
(100) of the matrix $\Sigma^{\scalebox{0.6}{\text{SHGD}}}\left(z\right)$ as

$\displaystyle{\mathbb{E}}\left[\left(F^{\top}\left(z\right)\nabla
F\left(z\right)-\frac{F_{\gamma^{1}}^{\top}\left(z\right)+F_{\gamma^{2}}^{\top}\left(z\right)}{2}\nabla
F\left(z\right)\right)\left(F^{\top}\left(z\right)\nabla
F\left(z\right)-\frac{F_{\gamma^{1}}^{\top}\left(z\right)+F_{\gamma^{2}}^{\top}\left(z\right)}{2}\nabla
F\left(z\right)\right)^{\top}\right].$ (113)

Since $\gamma^{1}=\gamma^{2}=\gamma$, and noticing that
$F^{\top}\left(z\right)\nabla F\left(z\right)=\nabla^{2}f\left(z\right)\nabla
f\left(z\right)$, we have

$\Sigma^{\scalebox{0.6}{\text{SHGD}}}\left(z\right)=\nabla^{2}f\left(z\right)\Sigma\nabla^{2}f\left(z\right),$
(114)

which implies that

$dZ_{t}=-\nabla\mathcal{H}\left(Z_{t}\right)dt+\sqrt{\eta}\nabla^{2}f\left(Z_{t}\right)\sqrt{\Sigma}dW_{t}.$
(115)

∎

######  Corollary C.17.

Under the assumptions of Theorem C.14. Additionally, let us assume that
$\gamma^{1}$ and $\gamma^{2}$, are independent and the stochastic gradients
can be written as $\nabla_{x}f_{\gamma^{i}}(z)=\nabla_{x}f(z)+U_{x}^{i}$ and
$\nabla_{y}f_{\gamma^{i}}(z)=\nabla_{y}f(z)+U_{y}^{i}$ such that $U_{x}^{i}$
and $U_{y}^{i}$ are independent noises that do not depend on $z$. Therefore,
the SDE is:
$dZ_{t}=-\nabla\mathcal{H}\left(Z_{t}\right)dt+\sqrt{\frac{\eta}{2}}\nabla^{2}f\left(Z_{t}\right)\sqrt{\Sigma}dW_{t}.$
(116)

###### Proof of Corollary C.17.

First of all, we notice that

${\mathbb{E}}\left[\nabla\mathcal{H}_{\gamma^{1},\gamma^{2}}\left(z\right)\right]:={\mathbb{E}}\left[\frac{F_{\gamma^{1}}^{\top}\left(z\right)\nabla
F_{\gamma^{2}}\left(z\right)+F_{\gamma^{2}}^{\top}\left(z\right)\nabla
F_{\gamma^{1}}\left(z\right)}{2}\right]=F^{\top}\left(z\right)\nabla
F\left(z\right)=\nabla\mathcal{H}\left(z\right).$ (117)

Second, based on our assumption of the noise structure, we can rewrite Eq.
(100) of the matrix $\Sigma^{\scalebox{0.6}{\text{SHGD}}}\left(z\right)$ as

$\displaystyle{\mathbb{E}}\left[\left(F^{\top}\left(z\right)\nabla
F\left(z\right)-\frac{F_{\gamma^{1}}^{\top}\left(z\right)+F_{\gamma^{2}}^{\top}\left(z\right)}{2}\nabla
F\left(z\right)\right)\left(F^{\top}\left(z\right)\nabla
F\left(z\right)-\frac{F_{\gamma^{1}}^{\top}\left(z\right)+F_{\gamma^{2}}^{\top}\left(z\right)}{2}\nabla
F\left(z\right)\right)^{\top}\right].$ (118)

Since $\gamma^{1}$ and $\gamma^{2}$ are independent, and noticing that
$F^{\top}\left(z\right)\nabla F\left(z\right)=\nabla^{2}f\left(z\right)\nabla
f\left(z\right)$, we have

$\Sigma^{\scalebox{0.6}{\text{SHGD}}}\left(z\right)=\frac{1}{2}\nabla^{2}f\left(z\right)\Sigma\nabla^{2}f\left(z\right),$
(119)

which implies that

$dZ_{t}=-\nabla\mathcal{H}\left(Z_{t}\right)dt+\sqrt{\frac{\eta}{2}}\nabla^{2}f\left(Z_{t}\right)\sqrt{\Sigma}dW_{t}.$
(120)

∎

##  Appendix D BILINEAR GAMES - INSIGHTS

In this section, we study Bilinear Games of the form
$f(x,y)=x^{\top}\mathbf{\Lambda}y$, where $\mathbf{\Lambda}$ is a square,
diagonal, and positive semidefinite matrix.

###  D.1 SEG

######  Theorem D.1 (Exact Dynamics of SEG).

Under the assumptions of Corollary C.10, for
$f(x,y)=x^{\top}\mathbf{\Lambda}y$ and noise covariance matrices equal to
$\sigma\mathbf{I}_{d}$, we have that

$Z_{t}=\mathbf{\mathbf{\tilde{E}}}(t)\mathbf{\mathbf{\tilde{R}}}(t)\left(z+\sqrt{\eta}\sigma\int_{0}^{t}\mathbf{\mathbf{\tilde{E}}}(-s)\mathbf{\mathbf{\tilde{R}}}(-s)\mathbf{M}dW_{s}\right),$
(121)

with
$\mathbf{\mathbf{\tilde{E}}}(t)=\left[\begin{array}[]{ll}\mathbf{E}(t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(t)\end{array}\right],\mathbf{\mathbf{\tilde{R}}}(t)=\left[\begin{array}[]{ll}\mathbf{C}(t)&-\mathbf{S}(t)\\\
\mathbf{S}(t)&\mathbf{C}(t)\end{array}\right]$, and
$\mathbf{M}=\left[\begin{array}[]{ll}\mathbf{I}_{d}&-\rho\mathbf{\Lambda}\\\
\rho\mathbf{\Lambda}&\mathbf{I}_{d}\end{array}\right]$, where

$\mathbf{E}(t):=\operatorname{diag}{\left(e^{-\rho\lambda_{1}^{2}t},\cdots,e^{-\rho\lambda_{d}^{2}t}\right)},$
(122)
$\mathbf{C}(t):=\operatorname{diag}{\left(\cos{(\lambda_{1}t)},\cdots,\cos{(\lambda_{d}t)}\right)},$
(123)

and

$\mathbf{S}(t):=\operatorname{diag}{\left(\sin{(\lambda_{1}t)},\cdots,\sin{(\lambda_{d}t)}\right)}.$
(124)

In particular, we have that

  1. 1.

${\mathbb{E}}\left[Z_{t}\right]=\mathbf{\mathbf{\tilde{E}}}(t)\mathbf{\mathbf{\tilde{R}}}(t)z\overset{t\rightarrow\infty}{=}0$;

  2. 2.

The covariance matrix of is equal to

$\eta\sigma^{2}\left[\begin{array}[]{ll}\mathbf{I}_{d}-\mathbf{E}(2t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{I}_{d}-\mathbf{E}(2t)\end{array}\right]\bar{\Sigma}\overset{t\rightarrow\infty}{=}\eta\sigma^{2}\bar{\Sigma},$
(125)

where

$\bar{\Sigma}:=\left[\begin{array}[]{ll}\mathbf{B}&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{B}\end{array}\right],$ (126)

and
$\mathbf{B}:=\operatorname{diag}{\left(\frac{1+\rho^{2}\lambda_{1}^{2}}{2\rho\lambda_{1}^{2}},\cdots,\frac{1+\rho^{2}\lambda_{d}^{2}}{2\rho\lambda_{d}^{2}}\right)}$;

  3. 3.

If $\rho=0$, SGDA would indeed diverge.

###### Proof.

The SDEs of SEG are:

$\displaystyle
dX_{t}=-\mathbf{\Lambda}Y_{t}dt-\rho\mathbf{\Lambda}^{2}X_{t}dt+\sqrt{\eta}\mathbf{I}_{d}\sigma
dW^{x}_{t}-\sqrt{\eta}\sigma\rho\mathbf{\Lambda}dW^{y}_{t}$ (127)

and

$\displaystyle
dY_{t}=+\mathbf{\Lambda}X_{t}dt-\rho\mathbf{\Lambda}^{2}Ytdt+\sqrt{\eta}\sigma\mathbf{I}_{d}W^{y}_{t}+\sqrt{\eta}\sigma\rho\mathbf{\Lambda}dW^{x}_{t},$
(128)

which can be rewritten as

$\displaystyle dZ_{t}=\mathbf{A}Z_{t}dt+\sqrt{\eta}\sigma\mathbf{B}dW_{t},$
(129)

where

$\mathbf{A}=\left[\begin{array}[]{ll}-\rho\mathbf{\Lambda}^{2}&-\mathbf{\Lambda}\\\
\mathbf{\Lambda}&-\rho\mathbf{\Lambda}^{2}\end{array}\right]\quad\text{ and
}\quad\mathbf{B}=\left[\begin{array}[]{ll}\mathbf{I}_{d}&-\rho\mathbf{\Lambda}\\\
\rho\mathbf{\Lambda}&\mathbf{I}_{d}\end{array}\right].$ (130)

Therefore, the solution is

$Z_{t}=e^{\mathbf{A}t}\left(z+\sqrt{\eta}\sigma\int_{0}^{t}e^{-\mathbf{A}s}\mathbf{B}dW_{s}\right).$
(131)

We observe that $\mathbf{A}=\mathbf{A}_{1}+\mathbf{A}_{2}$ s.t.

$\mathbf{A}_{1}=\left[\begin{array}[]{ll}-\rho\mathbf{\Lambda}^{2}&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&-\rho\mathbf{\Lambda}^{2}\end{array}\right]\quad\text{ and
}\quad\mathbf{A}_{2}=\left[\begin{array}[]{ll}\mathbf{0}_{d}&-\mathbf{\Lambda}\\\
\mathbf{\Lambda}&\mathbf{0}_{d}\end{array}\right],$ (132)

and that since these two matrix commute,
$e^{\mathbf{A}t}=e^{\mathbf{A}_{1}t}e^{\mathbf{A}_{2}t}$. Clearly, we have
that

$\mathbf{\mathbf{\tilde{E}}}(t):=e^{\mathbf{A}_{1}t}=\operatorname{diag}{\left(e^{-\rho\lambda_{1}^{2}t},\cdots,e^{-\rho\lambda_{d}^{2}t},e^{-\rho\lambda_{1}^{2}t},\cdots,e^{-\rho\lambda_{d}^{2}t}\right)}=\left[\begin{array}[]{ll}\mathbf{E}(t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(t)\end{array}\right],$ (133)

where
$\mathbf{E}(t):=\operatorname{diag}{\left(e^{-\rho\lambda_{1}^{2}t},\cdots,e^{-\rho\lambda_{d}^{2}t}\right)}$.

Regarding $\mathbf{A}_{2}$, we observe that

$(\mathbf{A}_{2}t)^{2k}=\operatorname{diag}{\left((\lambda_{1}t)^{2k}(-1)^{k},\cdots,(\lambda_{d}t)^{2k}(-1)^{k},(\lambda_{1}t)^{2k}(-1)^{k},\cdots,(\lambda_{d}t)^{2k}(-1)^{k}\right)}$
(134)

and that

$(\mathbf{A}_{2}t)^{2k+1}=\left[\begin{array}[]{ll}\mathbf{0_{d}}&\mathbf{P}\\\
\mathbf{Q}&\mathbf{0_{d}}\end{array}\right],$ (135)

where

$\mathbf{P}:=\operatorname{diag}{\left((\lambda_{1}t)^{2k+1}(-1)^{k+1},\cdots,(\lambda_{d}t)^{2k+1}(-1)^{k+1}\right)}$
(136)

and

$\mathbf{Q}:=\operatorname{diag}{\left((\lambda_{1}t)^{2k+1}(-1)^{k},\cdots,(\lambda_{d}t)^{2k+1}(-1)^{k}\right)}.$
(137)

Therefore,

$\displaystyle\mathbf{\mathbf{\tilde{R}}}(t):=e^{\mathbf{A}_{2}t}$
$\displaystyle=\sum_{k=0}^{\infty}\frac{(\mathbf{A}_{2}t)^{2k}}{(2k)!}+\sum_{k=0}^{\infty}\frac{(\mathbf{A}_{2}t)^{2k+1}}{(2k+1)!}$
$\displaystyle=\left[\begin{array}[]{ll}\mathbf{C}(t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{C}(t)\end{array}\right]+\left[\begin{array}[]{ll}\mathbf{0}_{d}&-\mathbf{S}(t)\\\
\mathbf{S}(t)&\mathbf{0}_{d}\end{array}\right]=\left[\begin{array}[]{ll}\mathbf{C}(t)&-\mathbf{S}(t)\\\
\mathbf{S}(t)&\mathbf{C}(t)\end{array}\right],$ (144)

where

$\mathbf{C}(t):=\operatorname{diag}{\left(\cos{(\lambda_{1}t)},\cdots,\cos{(\lambda_{d}t)}\right)}$
(145)

and

$\mathbf{S}(t):=\operatorname{diag}{\left(\sin{(\lambda_{1}t)},\cdots,\sin{(\lambda_{d}t)}\right)}.$
(146)

Automatically, we get that

$e^{-\mathbf{A}_{1}s}=\left[\begin{array}[]{ll}\mathbf{E}(-s)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(-s)\end{array}\right]$ (147)

and

$\displaystyle
e^{-\mathbf{A}_{2}s}=\left[\begin{array}[]{ll}\mathbf{C}(s)&\mathbf{S}(s)\\\
-\mathbf{S}(s)&\mathbf{C}(s)\end{array}\right],$ (150)

which imply that

$\displaystyle Z_{t}$
$\displaystyle=\left[\begin{array}[]{ll}\mathbf{E}(t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(t)\end{array}\right]\left[\begin{array}[]{ll}\mathbf{C}(t)&-\mathbf{S}(t)\\\
\mathbf{S}(t)&\mathbf{C}(t)\end{array}\right]\bigg{(}z$ (155)
$\displaystyle+\sqrt{\eta}\sigma\int_{0}^{t}\left[\begin{array}[]{ll}\mathbf{E}(-s)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(-s)\end{array}\right]\left[\begin{array}[]{ll}\mathbf{C}(s)&\mathbf{S}(s)\\\
-\mathbf{S}(s)&\mathbf{C}(s)\end{array}\right]\left[\begin{array}[]{ll}\mathbf{I}_{d}&-\rho\mathbf{\Lambda}\\\
\rho\mathbf{\Lambda}&\mathbf{I}_{d}\end{array}\right]\left[\begin{array}[]{l}dW^{x}_{s}\\\
dW^{y}_{s}\end{array}\right]\bigg{)}.$ (164)

To conclude, we have that

$Z_{t}=\mathbf{\mathbf{\tilde{E}}}(t)\mathbf{\mathbf{\tilde{R}}}(t)\left(z+\sqrt{\eta}\sigma\int_{0}^{t}\mathbf{\mathbf{\tilde{E}}}(-s)\mathbf{\mathbf{\tilde{R}}}(-s)\mathbf{M}dW_{s}\right),$
(165)

where
$\mathbf{M}=\left[\begin{array}[]{ll}\mathbf{I}_{d}&-\rho\mathbf{\Lambda}\\\
\rho\mathbf{\Lambda}&\mathbf{I}_{d}\end{array}\right]$.

We observe that since the expected value of the noise terms is $0$, we have
that

${\mathbb{E}}[Z_{t}]=\left[\begin{array}[]{ll}\mathbf{E}(t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(t)\end{array}\right]\left[\begin{array}[]{ll}\mathbf{C}(t)&-\mathbf{S}(t)\\\
\mathbf{S}(t)&\mathbf{C}(t)\end{array}\right]z.$ (166)

Therefore, the expectation of $Z_{t}$ converges to $0$ exponentially fast,
while spiraling around the origin. We observe that larger values of $\rho$
encourage a faster convergence of ${\mathbb{E}}[Z_{t}]$ to $0$.

Let us now have a look at the covariance matrix of this process:

$Var(Z_{t})=\eta\sigma^{2}\left[\begin{array}[]{ll}\mathbf{E}(2t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(2t)\end{array}\right]\mathbf{\mathbf{\tilde{R}}}(t)Var(V_{t})\mathbf{\mathbf{\tilde{R}}}(t)^{\top}$,
where

$\displaystyle V_{t}$
$\displaystyle:=\int_{0}^{t}\left[\begin{array}[]{ll}\mathbf{E}(-s)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(-s)\end{array}\right]\left[\begin{array}[]{ll}\mathbf{C}(s)&\mathbf{S}(s)\\\
-\mathbf{S}(s)&\mathbf{C}(s)\end{array}\right]\left[\begin{array}[]{ll}\mathbf{I}_{d}&-\rho\mathbf{\Lambda}\\\
\rho\mathbf{\Lambda}&\mathbf{I}_{d}\end{array}\right]\left[\begin{array}[]{l}dW^{x}_{s}\\\
dW^{y}_{s}\end{array}\right]$ (175)
$\displaystyle=\int_{0}^{t}\left[\begin{array}[]{ll}\mathbf{E}(-s)(\mathbf{C}(s)+\rho\mathbf{\Lambda}\mathbf{S}(s))&\mathbf{E}(-s)(\mathbf{S}(s)-\rho\mathbf{\Lambda}\mathbf{C}(s))\\\
\mathbf{E}(-s)(\rho\mathbf{\Lambda}\mathbf{C}(s)-\mathbf{S}(s))&\mathbf{E}(-s)(\mathbf{C}(s)+\rho\mathbf{\Lambda}\mathbf{S}(s))\end{array}\right]\left[\begin{array}[]{l}dW^{x}_{s}\\\
dW^{y}_{s}\end{array}\right]$ (180)
$\displaystyle=\left[\begin{array}[]{l}\int_{0}^{t}e^{\rho\lambda_{1}^{2}s}(\cos{(\lambda_{1}s)}+\rho\lambda\sin{(\lambda_{1}s)})dW^{x_{1}}_{s}+\int_{0}^{t}e^{\rho\lambda_{1}^{2}s}(\sin{(\lambda_{1}s)}-\rho\lambda_{1}\cos{(\lambda_{1}s)})dW^{y_{1}}_{s}\\\
\vdots\\\
\int_{0}^{t}e^{\rho\lambda_{d}^{2}s}(\cos{(\lambda_{d}s)}+\rho\lambda\sin{(\lambda_{d}s)})dW^{x_{d}}_{s}+\int_{0}^{t}e^{\rho\lambda_{d}^{2}s}(\sin{(\lambda_{d}s)}-\rho\lambda_{d}\cos{(\lambda_{d}s)})dW^{y_{d}}_{s}\\\
\int_{0}^{t}e^{\rho\lambda_{1}^{2}s}(-\sin{(\lambda_{1}s)}+\rho\lambda\cos{(\lambda_{1}s)})dW^{x_{1}}_{s}+\int_{0}^{t}e^{\rho\lambda_{1}^{2}s}(\cos{(\lambda_{1}s)}+\rho\lambda_{1}\sin{(\lambda_{1}s)})dW^{y_{1}}_{s}\\\
\vdots\\\
\int_{0}^{t}e^{\rho\lambda_{d}^{2}s}(-\sin{(\lambda_{d}s)}+\rho\lambda\cos{(\lambda_{d}s)})dW^{x_{d}}_{s}+\int_{0}^{t}e^{\rho\lambda_{d}^{2}s}(\cos{(\lambda_{d}s)}+\rho\lambda_{d}\sin{(\lambda_{d}s)})dW^{y_{d}}_{s}\end{array}\right]$
(187)
$\displaystyle=:\left[\begin{array}[]{l}a^{x_{1}}_{1}(t)+a^{y_{1}}_{2}(t)\\\
\vdots\\\ a^{x_{d}}_{1}(t)+a^{y_{d}}_{2}(t)\\\
a^{x_{1}}_{3}(t)+a^{y_{1}}_{4}(t)\\\ \vdots\\\
a^{x_{d}}_{3}(t)+a^{y_{d}}_{4}(t)\end{array}\right].$ (194)

Therefore,

$Var(V_{t})=\left[\begin{array}[]{ll}\mathbf{V}^{1,2}(t)&\mathbf{C}^{1,2,3,4}(t)\\\
\mathbf{C}^{1,2,3,4}(t)&\mathbf{V}^{3,4}(t)\end{array}\right],$ (195)

such that

$\mathbf{V}^{1,2}_{i,i}(t)=Var(a^{x_{i}}_{1}(t))+Var(a^{y_{i}}_{2}(t)),\quad\forall
i\in\\{1,\cdots,d\\},$ (196)
$\mathbf{V}^{3,4}_{i,i}(t)=Var(a^{x_{i}}_{3}(t))+Var(a^{y_{i}}_{4}(t)),\quad\forall
i\in\\{1,\cdots,d\\},$ (197)

and

$\mathbf{C}^{1,2,3,4}_{i,i}(t)=Cov(a^{x_{i}}_{1}(t),a^{x_{i}}_{3}(t))+Cov(a^{y_{i}}_{1}(t),a^{y_{i}}_{3}(t)),\quad\forall
i\in\\{1,\cdots,d\\}.$ (198)

Using the well-known Itô Isometry:

${\mathbb{E}}\left[\left(\int_{0}^{t}H_{s}dW_{s}\right)^{2}\right]={\mathbb{E}}\left[\int_{0}^{t}H_{s}^{2}ds\right],$

we get that

$\displaystyle
Var(a^{x_{i}}_{1}(t))+Var(a^{y_{i}}_{2}(t))=\int_{0}^{t}e^{2\rho\lambda_{i}^{2}s}(\cos{(\lambda_{i}s)}+\rho\lambda_{i}\sin{(\lambda_{i}s)})^{2}ds+\int_{0}^{t}e^{2\rho\lambda_{i}^{2}s}(\sin{(\lambda_{i}s)}-\rho\lambda_{i}\cos{(\lambda_{i}s)})^{2}ds$
$\displaystyle=\int_{0}^{t}e^{2\rho\lambda_{i}^{2}s}\left[(\cos{(\lambda_{i}s)}+\rho\lambda_{i}\sin{(\lambda_{i}s)})^{2}+(\sin{(\lambda_{i}s)}-\rho\lambda_{i}\cos{(\lambda_{i}s)})^{2}\right]ds$
$\displaystyle=\int_{0}^{t}e^{2\rho\lambda_{i}^{2}s}\left[1+\rho^{2}\lambda_{i}^{2}\right]ds$
$\displaystyle=\frac{1+\rho^{2}\lambda_{i}^{2}}{2\rho\lambda_{i}^{2}}\left(e^{2\rho\lambda_{i}^{2}t}-1\right).$
(199)

We observe that if $\rho=0$, this quantity is equal to $t$.

Then, we do a similar calculation:

$\displaystyle
Var(a^{x_{i}}_{3}(t))+Var(a^{y_{i}}_{4}(t))=\int_{0}^{t}e^{2\rho\lambda_{i}^{2}s}(-\sin{(\lambda_{i}s)}+\rho\lambda_{i}\cos{(\lambda_{i}s)})^{2}ds+\int_{0}^{t}e^{2\rho\lambda_{i}^{2}s}(\cos{(\lambda_{i}s)}+\rho\lambda_{i}\sin{(\lambda_{i}s)})^{2}ds$
$\displaystyle=\int_{0}^{t}e^{2\rho\lambda_{i}^{2}s}\left[(-\sin{(\lambda_{i}s)}+\rho\lambda_{i}\cos{(\lambda_{i}s)})^{2}+(\cos{(\lambda_{i}s)}+\rho\lambda_{i}\sin{(\lambda_{i}s)})^{2}\right]ds$
$\displaystyle=\int_{0}^{t}e^{2\rho\lambda_{i}^{2}s}\left[1+\rho^{2}\lambda_{i}^{2}\right]ds$
$\displaystyle=\frac{1+\rho^{2}\lambda_{i}^{2}}{2\rho\lambda_{i}^{2}}\left(e^{2\rho\lambda_{i}^{2}t}-1\right).$
(200)

We observe that if $\rho=0$, also this quantity is equal to $t$.

Remembering now that

${\mathbb{E}}\left[\left(\int_{0}^{t}X_{s}dW_{s}\right)\left(\int_{0}^{t}Y_{s}dW_{s}\right)\right]={\mathbb{E}}\left[\int_{0}^{t}X_{s}Y_{s}ds\right],$

we have that

$\displaystyle
Cov(a^{x_{i}}_{1}(t),a^{x_{i}}_{3}(t))+Cov(a^{y_{i}}_{2}(t),a^{y_{i}}_{4}(t))$
$\displaystyle=\int_{0}^{t}e^{2\rho\lambda_{i}^{2}s}(\cos{(\lambda_{i}s)}+\rho\lambda_{i}\sin{(\lambda_{i}s)})(-\sin{(\lambda_{i}s)}+\rho\lambda_{i}\cos{(\lambda_{i}s)})ds$
$\displaystyle+\int_{0}^{t}e^{2\rho\lambda_{i}^{2}s}(\sin{(\lambda_{i}s)}-\rho\lambda_{i}\cos{(\lambda_{i}s)})(\cos{(\lambda_{i}s)}+\rho\lambda_{i}\sin{(\lambda_{i}s)})ds=0.$
(201)

To conclude, the covariance matrix of $Z_{t}$ is

$Var(Z_{t})=\eta\sigma^{2}\left[\begin{array}[]{ll}\mathbf{I}_{d}-\mathbf{E}(2t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{I}_{d}-\mathbf{E}(2t)\end{array}\right]\bar{\Sigma}\overset{t\rightarrow\infty}{=}\eta\sigma^{2}\bar{\Sigma},$
(202)

where

$\bar{\Sigma}:=\left[\begin{array}[]{ll}\mathbf{B}&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{B}\end{array}\right]$ (203)

and
$\mathbf{B}:=\operatorname{diag}{\left(\frac{1+\rho^{2}\lambda_{1}^{2}}{2\rho\lambda_{1}^{2}},\cdots,\frac{1+\rho^{2}\lambda_{d}^{2}}{2\rho\lambda_{d}^{2}}\right)}$.

Of course, if $\rho=0$ the covariance matrix is actually
$\eta\sigma^{2}t\mathbf{I}_{d}$, meaning that the variance of SGDA diverges. ∎

######  Lemma D.2.

Let us define the variance
$\mathbf{B}_{i,i}(\rho)=\frac{1+\rho^{2}\lambda_{i}^{2}}{2\rho\lambda_{i}^{2}}$
and consider it as a function of $\rho$. The following hold:

  1. 1.

$\lim_{\rho\rightarrow 0}\mathbf{B}_{i,i}(\rho)=\infty$;

  2. 2.

$\lim_{\rho\rightarrow\infty}\mathbf{B}_{i,i}(\rho)=\infty$;

  3. 3.

$\mathbf{B}_{i,i}(\rho)$ is convex in $\rho$;

  4. 4.

$\rho=\frac{1}{\lambda_{i}}$ realizes the minimum and
$\mathbf{B}_{i,i}\left(\frac{1}{\lambda_{i}}\right)=\frac{1}{\lambda_{i}}$;

  5. 5.

The trace of $\bar{\Sigma}$ is minimized by
$\rho=\sqrt{\frac{\sum\frac{1}{\lambda_{i}^{2}}}{d}}$.

###### Proof.

The first four points are obvious while we spell out the last one. We observe
that the trace of $\mathbf{B}$ is convex as the sum of convex functions and
its derivative w.r.t. $\rho$ is

$\frac{d}{d\rho}\left(\sum_{i=1}^{d}\frac{1+\rho^{2}\lambda_{i}^{2}}{2\rho\lambda_{i}^{2}}\right)=\sum_{i=1}^{d}\frac{1}{2}-\frac{1}{2\rho^{2}\lambda_{i}^{2}},$
(204)

which implies that the optimal $\rho$ is indeed
$\rho=\sqrt{\frac{\sum\frac{1}{\lambda_{i}^{2}}}{d}}$. ∎

##### Insights - The trade-off in selecting $\rho$

The curvature of the landscape influences the speed of convergence. Indeed,
larger values of $\lambda_{i}$, which correspond to stronger interaction,
speed up the exponential decay in the expected value of the iterates.
Additionally, $\rho$ impacts the convergence speed in expectation as larger
values boost such a decay. However, the peculiar way in which the noise and
the landscape interact implies that larger values of $\rho$ might actually
result in larger asymptotic variance. One observes that both $\rho\rightarrow
0$ and $\rho\rightarrow\infty$ result in infinite asymptotic variance. On the
bright side, $\rho_{i}=\frac{1}{\lambda_{i}}$ is the optimal choice to reduce
the variance along the $i$-th dimension. Unfortunately, this could possibly be
very small and thus slow down the convergence. Finally, if one can only select
a single $\rho$ across all parameters, then one might want to minimize the
trace of the covariance matrix using
$\rho=\sqrt{\frac{\sum\frac{1}{\lambda_{i}^{2}}}{d}}$.

###  D.2 SHGD

######  Theorem D.3 (Exact Dynamics of SHGD).

Under the assumptions of Corollary C.16, for
$f(x,y)=x^{\top}\mathbf{\Lambda}y$ and noise covariance matrices equal to
$\sigma\mathbf{I}_{d}$, we have that

$Z_{t}=\mathbf{\tilde{E}}(t)\left(z+\sqrt{\eta}\sigma\int_{0}^{t}\mathbf{\tilde{E}}(-s)\mathbf{M}dW_{s}\right),$
(205)

$\mathbf{\tilde{E}}(t)=\left[\begin{array}[]{ll}\mathbf{E}(t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(t)\end{array}\right]$,
$\mathbf{M}=\left[\begin{array}[]{ll}\mathbf{0}_{d}&\mathbf{\Lambda}\\\
\mathbf{\Lambda}&\mathbf{0}_{d}\end{array}\right]$, where

$\mathbf{E}(t):=\operatorname{diag}{\left(e^{-\lambda_{1}^{2}t},\cdots,e^{-\lambda_{d}^{2}t}\right)}.$
(206)

In particular, we have that

  1. 1.

${\mathbb{E}}\left[Z_{t}\right]=\mathbf{\tilde{E}}(t)z\overset{t\rightarrow\infty}{=}0$;

  2. 2.

The covariance matrix of $Z_{t}$ is equal to

$\eta\frac{\sigma^{2}}{2}\left[\begin{array}[]{ll}\mathbf{I}_{d}-\mathbf{E}(2t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{I}_{d}-\mathbf{E}(2t)\end{array}\right]\bar{\Sigma}\overset{t\rightarrow\infty}{=}\eta\sigma^{2}\bar{\Sigma},$
(207)

where

$\bar{\Sigma}:=\left[\begin{array}[]{ll}\mathbf{I}_{d}&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{I}_{d}\end{array}\right].$ (208)

###### Proof.

The SDEs of SHGD are:

$\displaystyle
dX_{t}=-\mathbf{\Lambda}^{2}X_{t}dt+\sqrt{\eta}\sigma\mathbf{\Lambda}dW^{y}_{t}$
(209)

and

$\displaystyle
dY_{t}=-\mathbf{\Lambda}^{2}Ytdt+\sqrt{\eta}\sigma\mathbf{\Lambda}dW^{x}_{t},$
(210)

which can be rewritten as

$\displaystyle dZ_{t}=\mathbf{A}Z_{t}dt+\sqrt{\eta}\sigma\mathbf{B}dW_{t},$
(211)

where

$\mathbf{A}=\left[\begin{array}[]{ll}-\mathbf{\Lambda}^{2}&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&-\mathbf{\Lambda}^{2}\end{array}\right]\quad\text{ and
}\quad\mathbf{B}=\left[\begin{array}[]{ll}\mathbf{0}_{d}&\mathbf{\Lambda}\\\
\mathbf{\Lambda}&\mathbf{0}_{d}\end{array}\right].$ (212)

Therefore, the solution is

$Z_{t}=e^{\mathbf{A}t}\left(z+\sqrt{\eta}\sigma\int_{0}^{t}e^{-\mathbf{A}s}\mathbf{B}dW_{s}\right).$
(213)

Clearly, we have that

$\mathbf{\mathbf{\tilde{E}}}(t):=e^{\mathbf{A}t}=\operatorname{diag}{\left(e^{-\lambda_{1}^{2}t},\cdots,e^{-\lambda_{d}^{2}t},e^{-\lambda_{1}^{2}t},\cdots,e^{-\lambda_{d}^{2}t}\right)}=\left[\begin{array}[]{ll}\mathbf{E}(t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(t)\end{array}\right],$ (214)

where
$\mathbf{E}(t):=\operatorname{diag}{\left(e^{-\lambda_{1}^{2}t},\cdots,e^{-\lambda_{d}^{2}t}\right)}$.
Automatically, we get that

$e^{-\mathbf{A}_{1}s}=\left[\begin{array}[]{ll}\mathbf{E}(-s)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(-s)\end{array}\right],$ (215)

which implies that

$Z_{t}=\left[\begin{array}[]{ll}\mathbf{E}(t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(t)\end{array}\right]\left(z+\sqrt{\eta}\sigma\int_{0}^{t}\left[\begin{array}[]{ll}\mathbf{E}(-s)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(-s)\end{array}\right]\left[\begin{array}[]{ll}\mathbf{0}_{d}&\mathbf{\Lambda}\\\
\mathbf{\Lambda}&\mathbf{0}_{d}\end{array}\right]\left[\begin{array}[]{l}dW^{x}_{s}\\\
dW^{y}_{s}\end{array}\right]\right).$ (216)

To conclude, we have that

$Z_{t}=\mathbf{\mathbf{\tilde{E}}}(t)\left(z+\sqrt{\eta}\sigma\int_{0}^{t}\mathbf{\mathbf{\tilde{E}}}(-s)\mathbf{M}dW_{s}\right),$
(217)

where $\mathbf{M}=\left[\begin{array}[]{ll}\mathbf{0}_{d}&\mathbf{\Lambda}\\\
\mathbf{\Lambda}&\mathbf{0}_{d}\end{array}\right]$. We observe that

${\mathbb{E}}[Z_{t}]=\left[\begin{array}[]{ll}\mathbf{E}(t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(t)\end{array}\right]z$ (218)

because the parts dependent on $dW$ are martingales. Therefore,
${\mathbb{E}}[Z_{t}]$ converges to $0$ exponentially fast.

Let us now have a look at the covariance matrix of this process:

$Var(Z_{t})=\eta\sigma^{2}\left[\begin{array}[]{ll}\mathbf{E}(2t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(2t)\end{array}\right]Var(V_{t})$, where

$\displaystyle V_{t}$
$\displaystyle:=\int_{0}^{t}\left[\begin{array}[]{ll}\mathbf{E}(-s)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{E}(-s)\end{array}\right]\left[\begin{array}[]{ll}\mathbf{0}_{d}&\mathbf{\Lambda}\\\
\mathbf{\Lambda}&\mathbf{0}_{d}\end{array}\right]\left[\begin{array}[]{l}dW^{x}_{s}\\\
dW^{y}_{s}\end{array}\right]$ (225)
$\displaystyle=\left[\begin{array}[]{l}\int_{0}^{t}\lambda_{1}e^{\lambda_{1}^{2}s}dW^{y_{1}}_{s}\\\
\vdots\\\ \int_{0}^{t}\lambda_{d}e^{\lambda_{d}^{2}s}dW^{y_{d}}_{s}\\\
\int_{0}^{t}\lambda_{1}e^{\lambda_{1}^{2}s}dW^{x_{1}}_{s}\\\ \vdots\\\
\int_{0}^{t}\lambda_{d}e^{\lambda_{d}^{2}s}dW^{x_{d}}_{s}\end{array}\right]=:\left[\begin{array}[]{l}a^{y_{1}}(t)\\\
\vdots\\\ a^{y_{d}}(t)\\\ a^{x_{1}}(t)\\\ \vdots\\\
a^{x_{d}}(t)\end{array}\right].$ (238)

Therefore,

$Var(V_{t})=\left[\begin{array}[]{ll}\mathbf{V}^{1,y}(t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{V}^{1,x}(t)\end{array}\right],$ (239)

such that

$\mathbf{V}^{1,y}_{i,i}(t)=Var(a^{y_{i}}(t)),\quad\forall
i\in\\{1,\cdots,d\\},$ (240)

and

$\mathbf{V}^{1,x}_{i,i}(t)=Var(a^{x_{i}}(t)),\quad\forall
i\in\\{1,\cdots,d\\}.$ (241)

Using the well-known Itô Isometry

${\mathbb{E}}\left[\left(\int_{0}^{t}H_{s}dW_{s}\right)^{2}\right]={\mathbb{E}}\left[\int_{0}^{t}H_{s}^{2}ds\right],$

we get that

$\displaystyle
Var(a^{y_{i}}(t))=\int_{0}^{t}e^{2\lambda_{i}^{2}s}\lambda_{i}^{2}ds=\frac{1}{2}\left(e^{2\lambda_{i}^{2}t}-1\right).$
(242)

Similarly, we get that

$\displaystyle
Var(a^{x_{i}}(t))=\int_{0}^{t}e^{2\lambda_{i}^{2}s}\lambda_{i}^{2}ds=\frac{1}{2}\left(e^{2\lambda_{i}^{2}t}-1\right).$
(243)

Therefore, we conclude that the covariance matrix of $Z_{t}$ is

$Var(Z_{t})=\eta\sigma^{2}\left[\begin{array}[]{ll}\mathbf{I}_{d}-\mathbf{E}(2t)&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{I}_{d}-\mathbf{E}(2t)\end{array}\right]\bar{\Sigma}\overset{t\rightarrow\infty}{=}\frac{\eta\sigma^{2}}{2}\bar{\Sigma},$
(244)

where

$\bar{\Sigma}:=\left[\begin{array}[]{ll}\mathbf{I}_{d}&\mathbf{0}_{d}\\\
\mathbf{0}_{d}&\mathbf{I}_{d}\end{array}\right].$ (245)

∎

##### Insights

Just like for SEG, the curvature influences the speed of convergence of the
algorithm. On the other, the asymptotic variance is independent of the
curvature.

##### SEG vs SHGD

We notice that if $\rho=1$, the exponential decay of SEG and SHGD is the same.
However, in such a case, the asymptotic variance of SEG along the $i$-th