parameters, joint-gradient, and Cartesian components of the momentum-buffer at
the current iterate as in Equation 4.10.

######  Lemma B.1.2.

$\displaystyle\bm{\omega}^{j\\!+\\!1}=\bm{\omega}^{j}+\Re\left(\alpha\bm{\mu}^{j\\!+\\!1}\right)\iff\bm{\omega}^{j\\!+\\!1}=\bm{\omega}^{j}-\Re\left(\alpha\right)\hat{\bm{g}}^{j}+\Re\left(\alpha\beta\right)\Re\left(\bm{\mu}^{j}\right)-\Im\left(\alpha\beta\right)\Im\left(\bm{\mu}^{j}\right)$

###### Proof.

$\displaystyle\Re\left(\alpha\bm{\mu}^{j\\!+\\!1}\right)$ $\displaystyle=$
$\displaystyle\left(\Re\left(\alpha\right)\Re\left(\bm{\mu}^{j\\!+\\!1}\right)-\Im\left(\alpha\right)\Im\left(\bm{\mu}^{j\\!+\\!1}\right)\right)$
$\displaystyle=$
$\displaystyle\left(\Re\left(\alpha\right)\left(\Re\left(\beta\right)\Re\left(\bm{\mu}^{j}\right)-\Im\left(\beta\right)\Im\left(\bm{\mu}^{j}\right)-\hat{\bm{g}}^{j}\right)-\Im\left(\alpha\right)\left(\Im\left(\beta\right)\Re\left(\bm{\mu}^{j}\right)+\Re\left(\beta\right)\Im\left(\bm{\mu}^{j}\right)\right)\right)$
$\displaystyle=$
$\displaystyle-\Re\left(\alpha\right)\hat{\bm{g}}^{j}+\left(\Re\left(\alpha\right)\left(\Re\left(\beta\right)\Re\left(\bm{\mu}^{j}\right)-\Im\left(\beta\right)\Im\left(\bm{\mu}^{j}\right)\right)-\Im\left(\alpha\right)\left(\Im\left(\beta\right)\Re\left(\bm{\mu}^{j}\right)+\Re\left(\beta\right)\Im\left(\bm{\mu}^{j}\right)\right)\right)$
$\displaystyle=$
$\displaystyle-\Re\left(\alpha\right)\hat{\bm{g}}^{j}+\left(\Re\left(\alpha\right)\Re\left(\beta\right)-\Im\left(\alpha\right)\Im\left(\beta\right)\right)\Re\left(\bm{\mu}^{j}\right)-\left(\Re\left(\alpha\right)\Im\left(\beta\right)+\Im\left(\alpha\right)\Re\left(\beta\right)\right)\Im\left(\bm{\mu}^{j}\right)$
$\displaystyle=$
$\displaystyle-\Re\left(\alpha\right)\hat{\bm{g}}^{j}+\Re\left(\alpha\beta\right)\Re\left(\bm{\mu}^{j}\right)-\Im\left(\alpha\beta\right)\Im\left(\bm{\mu}^{j}\right)$

Thus,

$\displaystyle\bm{\omega}^{j\\!+\\!1}=\bm{\omega}^{j}+\Re\left(\alpha\bm{\mu}^{j\\!+\\!1}\right)\iff\bm{\omega}^{j\\!+\\!1}=\bm{\omega}^{j}-\Re\left(\alpha\right)\hat{\bm{g}}^{j}+\Re\left(\alpha\beta\right)\Re\left(\bm{\mu}^{j}\right)-\Im\left(\alpha\beta\right)\Im\left(\bm{\mu}^{j}\right)$

∎

####  B.1.1 Theorem 3 Proof Sketch

See 3

###### Proof.

We reproduce the proof quadratic games, which is simple case of the well-known
method from Polyak (1964) for analyzing the convergence of iterative methods.
Bertsekas (2008) generalizes this result from quadratic games to when we are
sufficiently close to any stationary point.

For quadratic games, we have that
$\hat{\bm{g}}^{j}=\left(\nabla_{\bm{\omega}}\hat{\bm{g}}\right)^{\top}\bm{\omega}^{j}$.
By Lemma B.1.1 and B.1.2 we have:

$\begin{pmatrix}\Re\left(\bm{\mu}^{j\\!+\\!1}\right)\\\
\Im\left(\bm{\mu}^{j\\!+\\!1}\right)\\\
\bm{\omega}^{j\\!+\\!1}\end{pmatrix}=\bm{J}\begin{pmatrix}\Re\left(\bm{\mu}^{j}\right)\\\
\Im\left(\bm{\mu}^{j}\right)\\\ \bm{\omega}^{j}\end{pmatrix}$ (B.11)

By telescoping the recurrence for the $j^{\textnormal{th}}$ augmented
parameters:

$\begin{pmatrix}\Re\left(\bm{\mu}^{j}\right)\\\
\Im\left(\bm{\mu}^{j}\right)\\\
\bm{\omega}^{j}\end{pmatrix}=\bm{J}^{j}\begin{pmatrix}\Re\left(\bm{\mu}^{0}\right)\\\
\Im\left(\bm{\mu}^{0}\right)\\\ \bm{\omega}^{0}\end{pmatrix}$ (B.12)

We can compare $\bm{\mu}^{j}$ with the value it converges to $\bm{\mu}^{*}$
which exists if $\bm{J}$ is contractive. We do the same with $\bm{\omega}$.
Because $\bm{\mu}^{*}=\bm{J}\bm{\mu}^{*}=\bm{J}^{j}\bm{\mu}^{*}$:

$\begin{pmatrix}\Re\left(\bm{\mu}^{j}\right)-\Re\left(\bm{\mu}^{*}\right)\\\
\Im\left(\bm{\mu}^{j}\right)-\Im\left(\bm{\mu}^{*}\right)\\\
\bm{\omega}^{j}-\bm{\omega}^{*}\end{pmatrix}=\bm{J}^{j}\begin{pmatrix}\Re\left(\bm{\mu}^{0}\right)-\Re\left(\bm{\mu}^{*}\right)\\\
\Im\left(\bm{\mu}^{0}\right)-\Im\left(\bm{\mu}^{*}\right)\\\
\bm{\omega}^{0}-\bm{\omega}^{*}\end{pmatrix}$ (B.13)

By taking norms:

$\displaystyle\left\|\begin{pmatrix}\Re\left(\bm{\mu}^{j}\right)-\Re\left(\bm{\mu}^{*}\right)\\\
\Im\left(\bm{\mu}^{j}\right)-\Im\left(\bm{\mu}^{*}\right)\\\
\bm{\omega}^{j}-\bm{\omega}^{*}\end{pmatrix}\right\|_{2}$
$\displaystyle=\left\|\bm{J}^{j}\begin{pmatrix}\Re\left(\bm{\mu}^{0}\right)-\Re\left(\bm{\mu}^{*}\right)\\\
\Im\left(\bm{\mu}^{0}\right)-\Im\left(\bm{\mu}^{*}\right)\\\
\bm{\omega}^{0}-\bm{\omega}^{*}\end{pmatrix}\right\|_{2}$ (B.14)
$\displaystyle\implies\left\|\begin{pmatrix}\Re\left(\bm{\mu}^{j}\right)-\Re\left(\bm{\mu}^{*}\right)\\\
\Im\left(\bm{\mu}^{j}\right)-\Im\left(\bm{\mu}^{*}\right)\\\
\bm{\omega}^{j}-\bm{\omega}^{*}\end{pmatrix}\right\|_{2}$
$\displaystyle\leq\left\|\bm{J}^{j}\right\|_{2}\left\|\begin{pmatrix}\Re\left(\bm{\mu}^{0}\right)-\Re\left(\bm{\mu}^{*}\right)\\\
\Im\left(\bm{\mu}^{0}\right)-\Im\left(\bm{\mu}^{*}\right)\\\
\bm{\omega}^{0}-\bm{\omega}^{*}\end{pmatrix}\right\|_{2}$ (B.15)

With Lemma 11 from Foucart (2012), we have there exists a matrix norm
$\forall\epsilon>0$ such that:

$\|\bm{J}^{j}\|\leq\left(\rho\left(\bm{J}\right)+\epsilon\right)^{j}$ (B.16)

We have a finite-dimensional space norm equivalence. So, for all norms
$\|\cdot\|$, $\exists C\\!\geq\\!B\\!>\\!0$ such that:

$B\|\bm{J}^{j}\|\leq\|\bm{J}^{j}\|_{2}\leq C\|\bm{J}^{j}\|$ (B.17)

Combining Equations B.16) and B.17 we have:

$\left\|\begin{pmatrix}\Re\left(\bm{\mu}^{j}\right)-\Re\left(\bm{\mu}^{*}\right)\\\
\Im\left(\bm{\mu}^{j}\right)-\Im\left(\bm{\mu}^{*}\right)\\\
\bm{\omega}^{j}-\bm{\omega}^{*}\end{pmatrix}\right\|_{2}\leq
C\left(\rho\left(\bm{J}\right)+\epsilon\right)^{j}\left\|\begin{pmatrix}\Re\left(\bm{\mu}^{0}\right)-\Re\left(\bm{\mu}^{*}\right)\\\
\Im\left(\bm{\mu}^{0}\right)-\Im\left(\bm{\mu}^{*}\right)\\\
\bm{\omega}^{0}-\bm{\omega}^{*}\end{pmatrix}\right\|_{2}$ (B.18)

So, we have:

$\left\|\begin{pmatrix}\Re\left(\bm{\mu}^{j}\right)-\Re\left(\bm{\mu}^{*}\right)\\\
\Im\left(\bm{\mu}^{j}\right)-\Im\left(\bm{\mu}^{*}\right)\\\
\bm{\omega}^{j}-\bm{\omega}^{*}\end{pmatrix}\right\|_{2}=\mathcal{O}\left(\left(\rho\left(\bm{J}\right)+\epsilon\right)^{j}\right)$
(B.19)

Thus, we converge linearly with a rate of
$\mathcal{O}\left(\rho\left(\bm{J}\right)+\epsilon\right)$. ∎

####  B.1.2 Characterizing the Augmented Dynamics Eigenvalues

Here, we present polynomials whose roots are the eigenvalues of the Jacobian
of our augmented dynamics $\operatorname*{Sp}\left(\bm{J}\right)$, given the
eigenvalues of the Jacobian of the joint-gradient vector field
$\operatorname*{Sp}\left(\nabla_{\bm{\omega}}\hat{\bm{g}}\right)$. We use a
similar decomposition as Gidel et al. (2019).

We expand $\nabla_{\bm{\omega}}\hat{\bm{g}}=\bm{P}\bm{T}\bm{P}^{-1}$ where
$\bm{T}$ is upper-triangular and $\lambda_{i}$ is an eigenvalue of
$\nabla_{\bm{\omega}}\hat{\bm{g}}$.

$\bm{T}=\begin{bmatrix}\lambda_{1}&*&\dots&*\\\ $0$&\dots&\dots&\dots\\\
\dots&\dots&\dots&*\\\ $0$&\dots&$0$&\lambda_{d}\\\ \end{bmatrix}$ (B.20)

We then break up into components for each eigenvalue, giving us submatrices
$\mathbf{R}_{k}\in\mathbb{C}^{$3$\times$3$}$:

$\bm{J}_{k}\vcentcolon=\begin{bmatrix}\Re\left(\beta\right)&-\Im\left(\beta\right)&-\lambda_{k}\\\
\Im\left(\beta\right)&\Re\left(\beta\right)&0\\\
\Re\left(\alpha\beta\right)&-\Im\left(\alpha\beta\right)&1-\Re\left(\alpha\right)\lambda_{k}\\\
\end{bmatrix}$ (B.21)

We can get the characteristic polynomial of $\bm{J}_{k}$ with the following
Mathematica command, where we use substitute the symbols $r+iu=\lambda_{k}$,
$a=\Re\left(\beta\right)$, $b=\Im\left(\beta\right)$,
$c=\Re\left(\alpha\right)$, and $d=\Im\left(\alpha\right)$.

CharacteristicPolynomial[{{a, -b, -(r + u I)}, {b, a, 0}, {a c - b d, -(b c +
a d), 1 - c (r + u I)}}, x]

The command gives us the polynomial associated with the eigenvalue
$\lambda_{k}=r+iu$:

$p_{k}(x)=-a^{2}x+a^{2}+acrx+iacux+2ax^{2}-2ax-b^{2}x+b^{2}+bdrx+ibdux-
crx^{2}-icux^{2}-x^{3}+x^{2}$ (B.22)

Consider the case where $\lambda_{k}$ is imaginary – i.e., $r=0$ – which is
true in all purely adversarial and bilinear zero-sum games. Then (B.22)
simplifies to:

$p_{k}(x)=-a^{2}x+a^{2}+iacux+2ax^{2}-2ax-b^{2}x+b^{2}+ibdux-
icux^{2}-x^{3}+x^{2}$ (B.23)

Our complex $\lambda_{k}$ come in conjugate pairs where $\lambda_{k}=u_{k}i$
and $\bar{\lambda}_{k}=-u_{k}i$. Equation B.23 has the same roots for
$\lambda_{k}$ and $\bar{\lambda}_{k}$, which can be verified by writing the
roots with the cubic formula. This corresponds to spiraling around the
solution in either a clockwise or counterclockwise direction. Thus, we
restrict ourselves to analyzing $\lambda_{k}$ where $u_{k}$ is positive
without loss of generality.

If we make the step size $\alpha$ real – i.e., $d=0$ – then Equation B.23
simplifies to:

$p_{k}(x)=x\left(-a^{2}+iacu-2a-b^{2}\right)+a^{2}+x^{2}\left(2a-icu+1\right)+b^{2}-x^{3}$
(B.24)

Using a heuristic from single-objective optimization, we look at making step
size proportional to the inverse of the magnitude of eigenvalue $k$ – i.e.,
$\alpha_{k}=\frac{\alpha^{\prime}}{|\lambda_{k}|}=\frac{\alpha^{\prime}}{u_{k}}$.
With this, (B.24) simplifies to:

$p_{k}(x)=x\left(-a^{2}+ia\alpha^{\prime}-2a-b^{2}\right)+a^{2}+x^{2}\left(2a-i\alpha^{\prime}+1\right)+b^{2}-x^{3}$
(B.25)

Notably, in Equation B.25 there is no dependence on the components of
imaginary eigenvalue $\lambda_{k}=r+iu=$0$+iu$, by selecting a $\alpha$ that
is proportional to the eigenvalues inverse magnitude. We can further simplify
with $a^{2}+b^{2}=|\beta|^{2}$:

$p_{k}(x)=x\left(\Re\left(\beta\right)\left(i\alpha^{\prime}-2\right)-|\beta|^{2}\right)+x^{2}\left(2\Re\left(\beta\right)-i\alpha^{\prime}+1\right)+|\beta|^{2}-x^{3}$
(B.26)

We could expand this in polar form for $\beta$ by noting
$\Re(\beta)=|\beta|\cos(\arg(\beta))$:

$p_{k}(x)=x\left(|\beta|\cos\left(\arg\left(\beta\right)\right)\left(i\alpha^{\prime}-2\right)-|\beta|^{2}\right)+x^{2}\left(2|\beta|\cos\left(\arg\left(\beta\right)\right)-i\alpha^{\prime}+1\right)+|\beta|^{2}-x^{3}$
(B.27)

We can simplify further by considering an imaginary $\beta$ – i.e.,
$\Re\left(\beta\right)=0$ or $\cos\left(\arg\left(\beta\right)\right)=0$:

$p_{k}(x)=|\beta|^{2}-x|\beta|^{2}-x^{2}\left(i\alpha^{\prime}-1\right)-x^{3}$
(B.28)

The roots of these polynomials can be trivially evaluated numerically or
symbolically with the by plugging in $\beta,\alpha,$ and $\lambda_{k}$ then
using the cubic formula. This section can be easily modified for the
eigenvalues of the augmented dynamics for variants of complex momentum by
defining the appropriate $\bm{J}$ and modifying the Mathematica command to get
the characteristic polynomial for each component, which can be evaluated if it
is a sufficiently low degree using known formulas.

####  B.1.3 Convergence Bounds

See 1

###### Proof.

Note that Theorem 3 bounds the convergence rate of Algorithm 7 by
$\operatorname*{Sp}(\bm{J})$. Also, Equation B.24 gives a formula for 3
eigenvalues in $\operatorname*{Sp}\left(\bm{J}\right)$ given $\alpha,\beta,$
and an eigenvalue
$\lambda\in\operatorname*{Sp}\left(\nabla_{\bm{\omega}}\hat{\bm{g}}\right)$.
The formula outputs a cubic polynomial whose roots are eigenvalues of
$\operatorname*{Sp}(\bm{J})$, which can be trivially evaluated with the cubic
formula.

We denote the $k^{\textnormal{th}}$ eigenspace of
$\operatorname*{Sp}\left(\nabla_{\bm{\omega}}\hat{\bm{g}}\right)$ with
eigenvalue $\lambda_{k}=ic_{k}$ and $|c_{1}|\leq\dots\leq|c_{n}|$, because
bilinear zero-sum games have purely imaginary eigenvalues due to
$\nabla_{\bm{\omega}}\hat{\bm{g}}$ being antisymmetric. Eigenvalues come in a
conjugate pairs, where $\bar{\lambda_{k}}=i\left(-c_{k}\right)$

If we select momentum coefficient
$\beta=|\beta|\exp\left(i\arg\left(\beta\right)\right)$ and step size
$\alpha_{k}=\frac{\alpha_{k}^{\prime}}{|c_{k}|}$, and use that
$\lambda\in\operatorname*{Sp}\left(\nabla_{\bm{\omega}}\hat{\bm{g}}\right)$
are imaginary, then – as shown in Appendix Section B.1.2 – (B.24) simplifies
to:

$p_{k}\left(x\right)=x\left(|\beta|\cos\left(\arg\left(\beta\right)\right)\left(i\alpha_{k}^{\prime}-2\right)-|\beta|^{2}\right)+x^{2}\left(2|\beta|\cos\left(\arg\left(\beta\right)\right)-i\alpha_{k}^{\prime}+1\right)+|\beta|^{2}-x^{3}$
(B.29)

So, with these parameter selections, the convergence rate of Algorithm 7 in
the $k^{\textnormal{th}}$ eigenspace is bounded by the largest root of
Equation B.29.

Note that if we find a separate $\alpha^{\prime}_{k}$ that converges in each
eigenspace $k$, then selected the smallest $\alpha^{\prime}_{k}$ converges in
every eigenspace because the convergence rate in eigenspace $k$ is a convex
function of $\alpha$ that equals $1$ when $\alpha=0$ and is minimized when
$\alpha>0$.

First, consider $\arg\left(\beta\right)=\pi-\epsilon$, where
$\epsilon=\frac{\pi}{16}$. We select $\alpha_{k}^{\prime}=$0.75$$
(equivalently, $\alpha_{k}=\frac{$0.75$}{|c_{k}|}$) and $|\beta|=$0.986$$ via
grid search. Using the cubic formula on the associated $p(x)$ from Equation
B.29, the maximum magnitude root has size $\approx$0.9998$<1$, so this
selection converges in the $k^{\textnormal{th}}$ eigenspace. So, selecting:

$\displaystyle\hat{\alpha}$ $\displaystyle\leq\min_{k}\alpha_{k}$ (B.30)
$\displaystyle=\min_{k}\frac{$0.75$}{c_{k}}$ (B.31)
$\displaystyle=\frac{$0.75$}{\max_{k}c_{k}}$ (B.32)
$\displaystyle=\frac{$0.75$}{\|\nabla_{\bm{\omega}}\hat{\bm{g}}\|_{2}}$ (B.33)

with $\beta=$0.986$\exp\left(i\left(\pi-\epsilon\right)\right)$ will converge
in each eigenspace.

Now, consider $\arg\left(\beta\right)=\epsilon=\frac{\pi}{16}$ with
$\alpha_{k}^{\prime}=$0.025$$ and $|\beta|=$0.9$$. Using the cubic formula on
the associated $p(x)$ from Equation B.29 the maximum magnitude root has size
$\approx$0.973$<1$, so this selection converges in the $k^{\textnormal{th}}$
eigenspace. So, selecting:

$\displaystyle\hat{\alpha}$ $\displaystyle\leq\min_{k}\alpha_{k}$ (B.34)
$\displaystyle=\min_{k}\frac{$0.025$}{c_{k}}$ (B.35)
$\displaystyle=\frac{$0.025$}{\max_{k}c_{k}}$ (B.36)
$\displaystyle=\frac{$0.025$}{\|\nabla_{\bm{\omega}}\hat{\bm{g}}\|_{2}}$
(B.37)

with $\beta=$0.9$\exp\left(i\epsilon\right)$ will converge in each eigenspace.

Thus, for any of the $\arg(\beta)$ choices, we can select
$\hat{\alpha},|\beta|$ that converges in every eigenspace and thus converges.

∎

In the preceding proof, our prescribed $\hat{\alpha}$ depends on the largest
norm eigenvalue of
$\operatorname*{Sp}\left(\nabla_{\bm{\omega}}\hat{\bm{g}}\right)$, due to our
selections of
$\hat{\alpha}\,\,\propto\,\,\frac{1}{\|\nabla_{\bm{\omega}}\hat{\bm{g}}\|_{2}}$.
In practice, we may not have access to the largest norm eigenvalue of
$\operatorname*{Sp}\left(\nabla_{\bm{\omega}}\hat{\bm{g}}\right)$.
Nevertheless, this shows that a parameter selection converges, even if it may
be difficult to find. Often, in convex optimization we describe the choices of
$\alpha,\beta$ in terms of the largest and smallest norm eigenvalues of
$\operatorname*{Sp}(\nabla_{\bm{\omega}}\hat{\bm{g}})$ (i.e., the Hessian of
the loss) (Boyd et al., 2004).

gradient$\bm{\mu}$update$\alpha$$\beta$ (a) Classical
(Polyak, 1964)

gradient$\bm{\mu}_{(1)}$…$\bm{\mu}_{(n)}$update$\alpha_{(1)}$$\beta_{(1)}$$\alpha_{(n)}$$\beta_{(n)}$
(b) Aggregated
(Lucas et al., 2018)

gradient$\bm{\mu}_{(1)}$$\bm{\mu}_{(2)}$update$\beta_{(1,2)}$$\alpha_{(1)}$$\beta_{(1,1)}$$\beta_{(2,1)}$$\alpha_{(2)}$$\beta_{(2,2)}$
(c) Recurrently linked
(new)

gradient$\Re(\bm{\mu}$)$\Im(\bm{\mu}$)update${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\Im(\beta)}$$\alpha$$\Re(\beta)$$-{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\Im(\beta)}$$\Re(\beta)$
(d) Complex
(ours)

Figure B.1:  We show computational diagrams for momentum variants
simultaneously updating all players parameters, which update the momentum
buffers $\bm{\mu}$ at iteration $j\\!+\\!1$ with coefficient $\beta$ via
$\bm{\mu}^{j\\!+\\!1}\\!=\\!\left(\beta\bm{\mu}^{j}-\textnormal{gradient}\right)$.
Our parameter update is a linear combination of momentum buffers weighted by
step sizes $\alpha$. (a) Classical momentum (Polyak, 1964; Sutskever et al.,
2013), with a single buffer and coefficient $\beta\in[0,1)$. (b) Aggregated
momentum (Lucas et al., 2018) adds multiple buffers with different
coefficients. (c) Recurrently linked momentum adds cross-buffer coefficients
and updates the buffers with
$\bm{\mu}_{(k)}^{j+1}\\!=\\!\left(\sum_{l}\beta_{(l,k)}\bm{\mu}_{(l)}^{j}-\textnormal{gradient}\right)$.
We allow $\beta_{(l,k)}$ to be negative as negative momentum (Gidel et al.,
2019) for solutions with simultaneous updates in adversarial games. (d)
Complex momentum is a special case of recurrently linked momentum with two
buffers and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\beta_{(1,1)}}\\!=\\!{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\beta_{(2,2)}}\\!=\\!{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Re(\beta)}$,
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\beta_{(1,2)}}\\!=\\!-{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\beta_{(2,1)}}\\!=\\!{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\Im(\beta)}$.
Analyzing other recurrently linked momentum setups is an open problem.

###  B.2 Algorithms

Here, we include additional algorithms that may be useful to some readers.
Algorithm 9 show aggregated momentum (Lucas et al., 2018). Algorithm 10 shows
the recurrently linked momentum that generalizes and unifies aggregated
momentum with negative momentum (Gidel et al., 2019). Algorithm 11 shows our
algorithm with alternating updates, which we use for training GANs. Algorithm
12 shows our method with all real-valued objects if one wants to implement
complex momentum in a library that does not support complex arithmetic.

Algorithm 9 Aggregated momentum

1:Select number of buffers $K\in\mathbb{N}$

2:Select $\beta_{(k)}\in[0,1)$ for $k=1\dots K$

3:Select $\alpha_{(k)}\in\mathbb{R}^{+}$ for $k=1\dots K$

4:Initialize $\bm{\mu}_{(k)}^{0}$ for $k=1\dots K$

5:for $j=$1$\dots N$ do

6: for $k=$1$\dots K$ do

7: $\bm{\mu}_{(k)}^{j+$1$}=\beta_{(k)}\bm{\mu}_{(k)}^{j}-\hat{\bm{g}}^{j}$

8: end for

9:
$\bm{\omega}^{j+$1$}=\bm{\omega}^{j}+\sum_{k=1}^{K}\alpha_{(k)}\bm{\mu}^{j+1}_{(k)}$

10:end for

11:return $\bm{\omega}_{N}$

Algorithm 10 Recurrently linked momentum

1:Select number of buffers $K\in\mathbb{N}$

2:Select $\beta_{(l,k)}\in\mathbb{R}$ for $l=1\dots K$ and $k=1\dots K$

3:Select $\alpha_{(k)}\in\mathbb{R}^{+}$ for $k=1\dots K$

4:Initialize $\bm{\mu}_{(k)}^{0}$ for $k=1\dots K$

5:for $j=$1$\dots N$ do

6: for $k=$1$\dots K$ do

7:
$\bm{\mu}_{(k)}^{j+1}=\sum_{l}\beta_{(l,k)}\bm{\mu}_{(l)}^{j}-\hat{\bm{g}}^{j}$

8: end for

9:
$\bm{\omega}^{j+$1$}=\bm{\omega}^{j}+\sum_{k=1}^{K}\alpha_{(k)}\bm{\mu}^{j+1}_{(k)}$

10:end for

11:return $\bm{\omega}_{N}$

Algorithm 11 (AltCM) Momentum

1:Select $\beta\in\mathbb{C},\alpha\in\mathbb{R}^{+}$

2:Initialize $\bm{\mu}_{A}^{0},\bm{\mu}_{B}^{0}$

3:for $j=$1$\dots N$ do

4: $\bm{\mu}_{A}^{j+$1$}=\beta\bm{\mu}_{A}^{j}-\bm{g}_{A}^{j}$

5:
$\bm{\theta}_{A}^{j+$1$}=\bm{\theta}_{A}^{j}+\Re\left(\alpha\bm{\mu}^{j+$1$}_{A}\right)$

6:
$\bm{\mu}_{B}^{j+$1$}=\beta\bm{\mu}_{B}^{j}-\bm{g}_{B}\left(\bm{\theta}_{A}^{j+1},\bm{\theta}_{B}^{j}\right)$

7:
$\bm{\theta}_{B}^{j+$1$}=\bm{\theta}_{B}^{j}+\Re\left(\alpha\bm{\mu}^{j+1}_{B}\right)$

8:end for

9:return $\bm{\omega}_{N}$

Algorithm 12 (SimCM) Complex Momentum - $\mathbb{R}$ valued

1:Select $\Re(\beta),\Im(\beta),\Re(\alpha),\Im(\alpha)\in\mathbb{R}$

2:Select $\Re(\beta),\Im(\beta),\Re(\alpha),\Im(\alpha)\in\mathbb{R}$

3:Initialize $\Re(\bm{\mu}^{0}),\Im(\bm{\mu}^{0})$

4:for $j=1\dots N$ do

5:
$\Re\left(\bm{\mu}^{j+1}\right)=\Re\left(\beta\right)\Re\left(\bm{\mu}^{j}\right)-\Im\left(\beta\right)\Im\left(\bm{\mu}^{j}\right)-\hat{\bm{g}}^{j}$

6:
$\Im\left(\bm{\mu}^{j+1}\right)=\Re\left(\beta\right)\Im\left(\bm{\mu}^{j}\right)+\Im\left(\beta\right)\Re\left(\bm{\mu}^{j}\right)$

7:
$\bm{\omega}^{j+1}=\bm{\omega}^{j}-\Re\left(\alpha\right)\hat{\bm{g}}^{j}+\Re\left(\alpha\beta\right)\Re\left(\bm{\mu}^{j}\right)-\Im\left(\alpha\beta\right)\Im\left(\bm{\mu}^{j}\right)$

8:end for

9:return $\bm{\omega}_{N}$

####  B.2.1 Complex Momentum in PyTorch

Our method can be easily implemented in PyTorch 1.6+ by using complex tensors.
The only necessary change to the SGD with momentum optimizer is extracting the
real-component from momentum buffer as with JAX – see here.

In older versions of Pytorch, we can use a tensor to represent the momentum
buffer $\bm{\mu}$, step size $\alpha$, and momentum coefficient $\beta$.
Specifically, we represent the real and imaginary components of the complex
number independently. Then, we redefine the operations __add__ and __mult__ to
satisfy the rules of complex arithmetic – i.e., Equations B.7 and B.8.

###  B.3 Experiments

####  B.3.1 Computing Infrastructure and Runtime

We do our computing in CPU for the purely adversarial experiments in Sections
4.4.1 and 4.4.2. Training each $2$D GAN in Section 4.4.3 takes $2$ hours and
we can train $10$ simultaneously on an NVIDIA T$4$ GPU. Training each CIFAR
GAN in Section 4.4.4 takes $10$ hours, and we can only train $1$ model per
NVIDIA T4 GPU.

####  B.3.2 Optimization in Purely Adversarial Games

We include the alternating update version of Figure 4.3 in Appendix Figure
B.3, which allows us to contrast simultaneous and alternating updates. With
alternating updates on a Dirac-GAN for $\alpha=$0.1$$ the best momentum
coefficient $\beta$ was complex, but we could converge with real, negative
momentum. Simultaneous updates may be a competitive choice with alternating
updates, if alternating updates cost two gradient evaluations per step, which
is common in deep learning setups.

####  B.3.3 Adversarialnesses Effect on Convergence

We include the extragradient (EG) update with extrapolation parameter
$\alpha^{\prime}$ and step size $\alpha$:

$\displaystyle\bm{\omega}^{j+\frac{1}{2}}=\bm{\omega}^{j}-\alpha^{\prime}\hat{\bm{g}}^{j}$
(EG)
$\displaystyle\bm{\omega}^{j+1}=\bm{\omega}^{j}-\alpha\hat{\bm{g}}^{j+\frac{1}{2}}$

and the optimistic gradient (OG) update with extrapolation parameter
$\alpha^{\prime}$ and step size $\alpha$:

$\displaystyle\bm{\omega}^{j+1}=\bm{\omega}^{j}-2\alpha\hat{\bm{g}}^{j}+\alpha^{\prime}\hat{\bm{g}}^{j-1}$
(OG)

EG and OG are often used with $\alpha=\alpha^{\prime}$. However, we found that
this constraint crippled these methods in cooperative games (that is,
minimization). As such, we tune the extrapolation parameter $\alpha^{\prime}$
separately from the step size $\alpha$, so EG and OG were competitive
baselines.

We include Figure B.4, which shows a GANs spectrum throughout training and
elaborates on Figure 4.7. This shows many real and imaginary eigenvalues, so
GAN training is neither purely cooperative nor adversarial. In addition, the
structure of the set of eigenvalues for the discriminator differs from the
generator, which may motivate separate optimizer choices. The structure
between the players persists through training, but the eigenvalues grow in
magnitude and spread out their phases. This indicates how adversarial the game
is can change during training.

$\Im\left(\operatorname*{Sp}\left(\bm{J}\right)\right)$$\arg(\beta)=$0$$$\arg(\beta)=\frac{\pi}{$4$}$The
real component of the spectrum of the augmented learning dynamics
$\Re(\operatorname*{Sp}(\bm{J}))$$\arg(\beta)=\frac{\pi}{$2$}$$\arg(\beta)=\
\frac{$3$\pi}{$4$}$$\arg(\beta)=\pi$$|\beta|$ Figure B.2:  The spectrum of the
augmented learning dynamics $\bm{J}$ is shown, whose spectral norm is the
convergence rate in Theorem 3. Each image is a different momentum phase
$\arg(\beta)$ for a range of $\alpha,|\beta|\\!\in\\![$0$,\\!$1$]$. The
opacity of an eigenvalue is the step size $\alpha$, and the color corresponds
to the magnitude of the momentum $|\beta|$. A red unit circle shows where all
eigenvalues must lie to converge for a fixed $\alpha,\beta$. If the max
eigenvalue norm $<\\!$1$$, we draw a green circle whose radius is our
convergence rate and a green star at the associated eigenvalue. In particular,
at every non-real $\beta$ we can select $\alpha,\\!|\beta|$ for convergence.
The eigenvalues are symmetric on the $x$-axis, and the eigenvalues near
$\Re(\lambda)\\!=\\!$1$$ dictate convergence rate. The eigenvalues near the
center are due to state augmentation, are of small magnitude, and do not
impact the convergence rate. Simultaneous gradient descent corresponds to the
magenta values where $|\beta|\\!=\\!$0$$.  Momentum phase $\arg(\beta)$SimCM
for # grad. eval. = # stepsMomentum Magnitude $|\beta|$AltCM for # grad.
eval.# grad. eval. to convergeAltCM for # steps# steps to converge Figure B.3:
We show many steps and gradient evaluations both simultaneous and alternating
complex momentum take on a Dirac-GAN take for a set solution distance. We fix
the step size $\alpha=$0.1$$ as in Figure 4.4, while varying the phase and
magnitude of our momentum
$\beta=|\beta|\exp\left(i\arg\left(\beta\right)\right)$. There is a red star
at the optima, dashed red lines at real $\beta$, and a dashed magenta line for
simultaneous or alternating gradient descent. We only display color for
convergent setups. _Left:_ Simultaneous complex momentum (SimCM). This is the
same as in Figure 4.3, which we repeat to contrast with alternating updates.
No real-valued $\beta$ converges for this – or any – $\alpha$ with
simultaneous updates (Gidel et al., 2019). Simultaneous updates can
parallelize gradient computation for all players at each step, thus costing
only one gradient evaluation per step for many deep learning setups. The best
convergence rate per step and gradient evaluation is
$\approx{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}$0.955$}$.
_Middle:_ Alternating complex momentum (AltCM), where we show how many
gradient evaluations – as opposed to steps – to reach a set solution distance.
Alternating updates are bottlenecked by waiting for the first player’s update
to compute the second player’s update, effectively costing two gradient
evaluations per step for many deep learning setups. As shown by Gidel et al.
(2019), negative momentum can converge here, but the best momentum is still
complex. Also, alternating updates can make the momentum phase $\arg(\beta)$
choice less sensitive to our convergence. The best convergence rate per
gradient evaluation is
$\approx{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}$0.965$}$.
_Right:_ AltCM, where we show how many steps it takes to reach a set solution
distance. The best convergence rate per step is
$\approx{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}$0.931$}$.
Takeaway: If we can parallelize the computation of the gradients of both
players, we can benefit from SimCM. However, if we cannot, then AltCM can
converge more quickly for a wider set of optimizer parameters. In any case,
the best solution uses a complex momentum $\beta$ for this $\alpha$.  Joint-
gradient $\hat{\bm{g}}$ index $l$$\log(|a_{lk}|+\epsilon)$ for $a_{lk}$ in
$\nabla_{\\!\bm{\omega}}\hat{\bm{g}}^{j}$Joint-parameter $\bm{\omega}$ index
$k$Jacobian of joint-gradient $\nabla_{\\!\bm{\omega}}\hat{\bm{g}}^{j}$ for
GANAbs of EVec componentIndex into $\mathbf{v}$ – first $337$ are for D’s
paramsEVec $\mathbf{v}$ components for eigenvalues
$\lambda\in\operatorname*{Sp}\left(\nabla_{\\!\bm{\omega}}\hat{\bm{g}}\right)$-$\pi$
-$\frac{\pi}{2}$ $0$ -$\frac{\pi}{2}$ -$\pi$Phase of eigenvalue
$\arg(\lambda)$disc. unsure gen.Does EVec point at a player?Log-magnitude of
eigenvalue $\log\left(|\lambda|\right)$Start of trainingEnd of trainingLog-
polar graph of the spectrum of Jacobian of the joint-gradient
$\operatorname*{Sp}\left(\nabla_{\\!\bm{\omega}}\hat{\bm{g}}^{j}\right)$
throughout training Figure B.4:  These plots investigate the spectrum of the
Jacobian of the joint-gradient for the GAN in Figure 4.7 through training. The
spectrum is key for bounding convergence rates in optimization.
_Top left:_ The Jacobian $\nabla_{\bm{\omega}}\hat{\bm{g}}$ for a GAN on a
$2$D mixture of Gaussians with a two-layer, fully-connected $16$ hidden unit
discriminator (D) and generator (G) at the end of training. In the
concatenated parameters $\bm{\omega}\in\mathbb{R}^{723}$, the first $337$ are
for D, while the last $386$ are for G. We display the $\log$ of the absolute
value of each component plus $\epsilon=10^{-10}$. The upper left and lower
right quadrants are the Hessian of D’s and G’s losses, respectively.
_Top Right:_ We visualize two randomly sampled eigenvectors from
$\nabla_{\bm{\omega}}\hat{\bm{g}}$. The first part of the parameters is for
the discriminator, while the second is for the generator. Given an eigenvalue
with eigenvector $\mathbf{v}$, we approximate the attribution of eigenvectors
to players by calculating how much of it lies in the parameter space of D with
$\frac{\|\mathbf{v}_{1\mathrel{\mathop{\ordinarycolon}}|\textnormal{D}|}\|_{1}}{\|\mathbf{v}\|_{1}}=\frac{\|\mathbf{v}_{1\mathrel{\mathop{\ordinarycolon}}337}\|_{1}}{\|\mathbf{v}\|_{1}}$.
If this ratio is close to $1$ (or $0$) and say _the eigenvector mostly points
at D (or G)_. The blue eigenvector mostly points to G, while the orange
eigenvector is unclear. Finding useful ways to attribute eigenvalues to
players is an open problem.
_Bottom:_ The spectrum of the Jacobian of the joint-gradient
$\operatorname*{Sp}\left(\nabla_{\bm{\omega}}\hat{\bm{g}}^{j}\right)$ is shown
in log-polar coordinates because it is difficult to see structure when
graphing in Cartesian (i.e., $\Re$ and $\Im$) coordinates, due to eigenvalues
spanning orders of magnitude, while being positive and negative. The end of
training is when we stop making progress on the log-likelihood. We have
imaginary eigenvalues at $\arg(\lambda)=\pm\nicefrac{{\pi}}{{$2$}}$, positive
eigenvalues at $\arg(\lambda)=$0$$, and negative eigenvalues at
$\arg(\lambda)=\pm\pi$.
_Takeaway:_ A banded structure for the coloring of the eigenvalues persists
through training. We may want different optimizer parameters for the
discriminator and generator due to asymmetry in their associated eigenvalues.
Furthermore, the magnitude of the eigenvalues increases during training, and
the $\arg$s spread out, indicating that the game can change the eigenstructure
near the solutions.

####  B.3.4 Training GANs on 2D Distributions

For $2$D distributions, the data is generated by sampling from a mixture of
$8$ Gaussian distributions distributed uniformly around the unit circle.

For the GAN, we use a fully connected network with $4$ ReLU (Hahnloser et al.,
2000) layers with $256$ hidden units. We chose this architecture to be the
same as Gidel et al. (2019). Our noise source for the generator is a $4$D
Gaussian. We trained the models for $100\,000$ iterations. The performance of
the optimizer settings is evaluated by computing the negative log-likelihood
of a batch of $100\,000$ generated $2$D samples.

Momentum phase $\arg(\beta)$Step size $\alpha=$0.001$$Momentum Magnitude
$|\beta|$Step Size $\alpha=$0.003$$NLL, lower = better Figure B.5:  Heatmaps
of the negative log-likelihood (NLL) for tuning $\arg(\beta),|\beta|$ with
various fixed $\alpha$ on a $2$D mixture of Gaussians GAN. We highlight the
best performing cell in red, which had
$\arg(\beta)\approx\nicefrac{{\pi}}{{$8$}}$. Runs equivalent to alternating
SGD are shown in a magenta box. We compare to negative momentum with
alternating updates as in Gidel et al. (2019) in the top row with
$\arg(\beta)=\pi$. _Left_ : Tuning the momentum with $\alpha=$0.001$$. _Right_
: Tuning the momentum with $\alpha=$0.003$$.  Figure B.6:  The mixture of
Gaussian samples from the GAN with the best hyperparameters from Figure B.5.
Figure B.7:  Class-conditional CIFAR-10 samples from the GAN with the best
hyperparameters from Figure B.8.  Momentum phase
$\arg\left(\beta_{1}\right)$Momentum magnitude $|\beta_{1}|$Inception score
$\uparrow$ Figure B.8:  The inception score for a grid search on
$\arg\left(\beta_{1}\right)$ and $|\beta_{1}|$ for training BigGAN on CIFAR-10
with the Adam variant in Algorithm 8. The $\beta_{1}$ is complex for the
discriminator, while the generator’s optimizer is fixed to the defaults
supplied by the author. Red points are runs that failed to train to the
minimum inception score in the color bar. The vertical magenta line denotes
runs equivalent to alternating SGD. Negative momentum did not train for any
magnitude of momentum $|\beta_{1}|>.5$, so we did not display it for more
resolution near the values of interest.  Inception score $\uparrow$Iteration
Figure B.9:  We compare the best optimization parameters from grid search
Figure B.8 for our complex Adam variant (i.e., Algorithm 8) shown in green,
with the author provided values shown in red for the CIFAR-10 BigGAN over $10$
seeds. A star is displayed at the best inception score for all runs, a cross
is at the worst inception score for all runs, and a circle is at the best
inception score for each run. Dashed lines are shown at the max/min inception
score over all runs at each iteration, low-alpha lines for each runs inception
score, and solid lines for the average inception score over all seeds at each
iteration. The results are summarized in Table 4.1.

##  Appendix C Lyapunov Exponents for Diversity in Differentiable Games

Table C.1: Notation for Lyapunov Exponents for Diversity in Differentiable Games RR | Ridge Rider
---|---
IPD | Iterated Prisoners’ Dilemma
GAN | Generative Adversarial Network
LOLA | Learning with Opponent Learning Awareness
EVec, EVal | Shorthand for Eigenvector or Eigenvalue
SGD | Stochastic Gradient Descent
SimSGD | Simultaneous SGD
$\vcentcolon=$ | Defined to be equal to
$x,y,z,\dots\in\mathbb{C}$ | Scalars
$\bm{x},\bm{y},\bm{z},\dots\in\mathbb{C}^{n}$ | Vectors
$\bm{X},\bm{Y},\bm{Z},\dots\in\mathbb{C}^{n\times n}$ | Matrices
$\bm{X}^{\top}$ | The transpose of matrix $\bm{X}$
$\bm{I}$ | The identity matrix
$\Re(z),\Im(z)$ | The real or imaginary component of $z\in\mathbb{C}$
$i$ | The imaginary unit. $z\in\mathbb{C}\implies z=\Re(z)+i\Im(z)$
$\bar{z}$ | The complex conjugate of $z\in\mathbb{C}$
$|z|\vcentcolon=\sqrt{z\bar{z}}$ | The magnitude or modulus of $z\in\mathbb{C}$
$\arg(z)$ | The argument or phase of $z\in\mathbb{C}\implies z=|z|\exp(i\arg(z))$
$A,B$ | A symbol for the outer/inner players
$d_{A},d_{B}\in\mathbb{N}$ | The number of weights for the outer/inner players
$\bm{\theta}$ | A symbol for the parameters or weights of a player
$\bm{\theta}_{A}\in\mathbb{R}^{d_{A}},\bm{\theta}_{B}\in\mathbb{R}^{d_{B}}$ | The outer/inner parameters or weights
$\mathcal{L}\mathrel{\mathop{\ordinarycolon}}\mathbb{R}^{n}\to\mathbb{R}$ | A symbol for a loss
$\mathcal{L}_{A}(\bm{\theta}_{A},\bm{\theta}_{B}),\mathcal{L}_{B}(\bm{\theta}_{A},\bm{\theta}_{B})$ | The outer/inner losses – $\mathbb{R}^{d_{A}+d_{B}}\mapsto\mathbb{R}$
$\bm{g}_{A}(\bm{\theta}_{A},\bm{\theta}_{B}),\bm{g}_{B}(\bm{\theta}_{A},\bm{\theta}_{B})$ | Gradient of outer/inner losses w.r.t. their weights in $\mathbb{R}^{d_{A}/d_{B}}$
$\bm{\theta}_{B}^{*}\\!(\bm{\theta}_{A}\\!)\\!\vcentcolon=\\!\mathop{\mathrm{argmin}}\limits\limits_{\bm{\theta}_{B}}\\!\\!\mathcal{L}_{B}\\!(\\!\bm{\theta}_{A}\\!,\\!\bm{\theta}_{B}\\!)$ | The best-response of the inner player to the outer player
$\mathcal{L}_{A}^{*}(\bm{\theta}_{A})\\!\vcentcolon=\\!\mathcal{L}_{A}\\!(\\!\bm{\theta}_{A}\\!,\\!\bm{\theta}_{B}^{*}(\bm{\theta}_{A})\\!)$ | The outer loss with a best-responding inner player
$\bm{\theta}_{A}^{*}\\!\vcentcolon=\\!\mathop{\mathrm{argmin}}\limits\limits_{\bm{\theta}_{A}}\mathcal{L}_{A}^{*}(\bm{\theta}_{A}\\!)$ | Outer optimal weights with a best-responding inner player
$d\vcentcolon=d_{A}+d_{B}$ | The combined number of weights for both players
$\bm{\omega}\vcentcolon=[\bm{\theta}_{A},\bm{\theta}_{B}]\in\mathbb{R}^{d}$ | A concatenation of the outer/inner weights
$\hat{\bm{g}}(\bm{\omega})\\!\vcentcolon=\\![\bm{g}_{A}(\bm{\omega}),\bm{g}_{B}(\bm{\omega})]\in\mathbb{R}^{d}$ | A concatenation of the outer/inner gradients
$\bm{\omega}^{$0$}=[\bm{\theta}_{A}^{$0$},\bm{\theta}_{B}^{$0$}]\in\mathbb{R}^{d}$ | The initial parameter values
$j$ | An iteration number
$\hat{\bm{g}}^{j}\vcentcolon=\hat{\bm{g}}(\bm{\omega}^{j})\in\mathbb{R}^{d}$ | The joint-gradient vector field at weights $\bm{\omega}^{j}$
$\nabla_{\bm{\omega}}\hat{\bm{g}}^{j}\vcentcolon=\nabla_{\bm{\omega}}\hat{\bm{g}}|_{\bm{\omega}^{j}}\in\mathbb{R}^{d\times d}$ | The Jacobian of the joint-gradient $\hat{\bm{g}}$ at weights $\bm{\omega}^{j}$
$\hat{\mathcal{H}}$ | The game Hessian
$\alpha\in\mathbb{C}$ | The step size or learning rate
$\lambda\in\mathbb{C},e$ | Notation for an arbitrary Eval
$\operatorname*{Sp}(\bm{M})\in\mathbb{C}^{n}$ | The spectrum – or set of eigenvalues – of $\bm{M}\in\mathbb{R}^{n\times n}$
$\rho(\bm{M})\\!\vcentcolon=\\!\max_{z\in\operatorname*{Sp}(\bm{M})}|z|$ | The spectral radius in $\mathbb{R}^{+}$ of $\bm{M}\in\mathbb{R}^{n\times n}$
$\bm{F}(\bm{\omega})$ | Fixed-point operator for our optimization
$\bm{J}$ | The Jacobian of the fixed-point operator
$\bm{d}$ | A displacement for a Lyapunov exponent
$\gamma_{j}(\bm{\omega}_{0},\bm{d})\vcentcolon=\log(\bm{d}^{\top}(\bm{J}^{j}(\bm{\omega}_{0}))^{\top}\bm{J}^{j}(\bm{\omega}_{0})\bm{d})$ | A Lyapunov term for a Lyapunov exponent
$\hat{\lambda}_{k}(\bm{\omega}_{0},\bm{d})=\frac{1}{k}\smash{\sum_{j=0}^{k}}\gamma_{j}(\bm{\omega}_{0},\bm{d})$ | A $k$-step Lyapunov exponent
$\hat{\lambda}_{k}^{max}(\bm{\omega}_{0})=\max_{\bm{d},\|\bm{d}\|=1}\hat{\lambda}_{k}(\bm{\omega}_{0},\bm{d})$ | The max $k$-step Lyapunov exponent
$\mathcal{L}(\bm{\omega}_{0})$ | A starting point loss using Lyapunov exponents
$\mathcal{L}_{n}^{\textnormal{sum}}(\bm{\omega}_{0})$ | A loss using the sum of top $n$ exponents
$\mathcal{L}_{n}^{\textnormal{min}}(\bm{\omega}_{0})$ | A loss using the min of top $n$ exponents

###  C.1 Related Work

The material from Chapter 5 is primarily from Lorraine et al. (2022b), with a
prior workshop submission of Lorraine et al. (2021b) and an arXiv submission
of Lorraine et al. (2021c).

Diversity in machine learning: Finding diverse solutions is often desirable in
machine learning, for example, improving performance for model ensembles
(Hansen and Salamon, 1990), with canonical approaches directly optimizing for
negative correlation amongst model predictions (Liu and Yao, 1999). In recent
times, these ideas have begun to re-emerge, improving ensemble performance
(Sinha et al., 2021; Ross et al., 2020; Mariet and Sra, 2016), robustness
(Pang et al., 2019; Cully et al., 2015) and boosting exploration in
reinforcement learning (Lehman and Stanley, 2008; Eysenbach et al., 2019;
Parker-Holder et al., 2020b; Pugh et al., 2016).

Many of these approaches seek diverse solutions by following gradients of an
altered, typically multi-objective loss function. In contrast, the recent
_Ridge Rider_ (RR) (Parker-Holder et al., 2020a) algorithm searches for
diverse solutions by following eigenvectors of the Hessian with respect to the
original loss function, producing orthogonal (loss reducing) search
directions.

Finding solutions in games: There are first-order methods for finding
solutions in games (Zhang et al., 2021b) including alternating updates (Zhang
et al., 2022), extragradient (Korpelevich, 1976; Azizian et al., 2020c),
optimistic gradient (Rakhlin and Sridharan, 2013; Daskalakis et al., 2018),
negative momentum (Gidel et al., 2019; Zhang and Wang, 2021), complex momentum
(Lorraine et al., 2022c), and iterate averaging (Gidel et al., 2018). There
are also higher-order methods such as consensus optimization (Mescheder et
al., 2017), symplectic gradient adjustment (SGA) (Letcher et al., 2019), local
symplectic surgery (LSS) (Mazumdar et al., 2019), competitive gradient descent
(CGD) (Schäfer and Anandkumar, 2019), follow-the-ridge (Wang et al., 2019b).
Recently, Vicol et al. (2022a) looked at the effects of overparameterization
while doing online learning in games.

Diversity in multi-agent RL: In recent times, a series of works have explored
the benefit of diversity in competitive (Balduzzi et al., 2019; Garnelo et
al., 2021; Vinyals et al., 2019) and cooperative (Yang et al., 2020; Lupu et
al., 2021) multi-agent RL. However, once again, these approaches all consider
augmented loss functions. Instead, we take inspiration from RR and extend it
to the multi-agent setting.

Tree searches in MDP: Tree searches are a classic technique for planning and
control in discrete Markov Decision Processes (MDP). The branch locations and
the possible branch choices are provided in these settings. All that remains
is to choose which to explore. There is much interest in performing these
searches ranging from depth/breadth-first search, A* (Hart et al., 1968), to
more sophisticated methods such as Monte Carlo Tree Search (Abramson, 2014)
potentially with learned value functions (Silver et al., 2016). Searching in
continuous action spaces was explored in Moerland et al. (2018); Kim et al.
(2020); Mao et al. (2020). All of these methods search in the agents’ action
space, and we employ them to find agent parameters.

Rapidly-exploring random tree builds a space-filling tree to cover a
continuous optimization space (LaValle et al., 1998; LaValle and Kuffner Jr,
2001). Unlike RR-based methods, the branching points are not determined by the
underlying properties of the loss landscape (e.g., only at saddles or
bifurcation). This technique is commonly used in robotic motion planning
(Rodriguez et al., 2006).

Branching in evolutionary optimization: Designing optimization algorithms in a
multimodal loss landscape is a focus of the evolutionary optimization
community (Singh and Deb, 2006; Wong, 2015), which implicitly build a tree of
candidate solutions. Evolutionary algorithms designed to encourage diversity
have been explored in the context of multi-player games (Balduzzi et al.,
2019; Vinyals et al., 2019; Arulkumaran et al., 2019) by encouraging agent
populations to learn different strategies that perform well against other
agents, resulting in a growing collection of strategies.

Bifurcations: This work builds on the previous workshop submission of Lorraine
et al. (2022b). The works of Zeeman (1980); Yang et al. (2018); Chotibut et
al. (2020); Piliouras (2020); Leonardos and Piliouras (2020); Bielawski et al.
(2021) leverage the bifurcations for learning in games. Yang et al. (2018)
introduces hysteresis and optimal control mechanisms to control equilibrium
selection and improve social welfare. We do not focus on maximizing social
welfare but on finding multiple solutions. Chotibut et al. (2020) studies the
properties of bifurcations in routing games, showing various analyses for
social cost. Piliouras (2020) combines catastrophe theory with mechanism
design to destabilize inefficient solutions. Leonardos and Piliouras (2020)
studies how changing an exploration parameter in multi-agent learning can
affect equilibrium selection. Our work focuses on connecting bifurcations with
finding diverse solutions in optimization with Ridge Rider and finding those
bifurcations - potentially with gradient-based methods.

Lyapunov exponents: The works of Cheung and Piliouras (2019); Cheung and Tao
(2020); Sato et al. (2002) use Lyapunov exponents when learning in games.
Cheung and Piliouras (2019) shows that some learning algorithms are Lyapunov
chaotic in the payoff space. Our work focuses on using Lyapunov exponent
variants to identify bifurcations (which are used to find diverse solutions in
optimization) and potentially using optimization methods on the exponent.

Separatrices: The works of Panageas and Piliouras (2016); Zhang and Hofbauer
(2015); Nagarajan et al. (2020) look at computing separatrices in games used
for various purposes. Nagarajan et al. (2020) finds the shape of separatrices
using invariant functions with online learning dynamics.

###  C.2 Proposed Algorithms

####  C.2.1 Branching Optimization Tree Searches

Algorithm 13 Branching Optimization Tree Search – important changes from RR to
GRR in red

1:Input: $\mathrm{FindStartingPoint}$, $\mathrm{ChooseBranch}$,
$\mathrm{SplitBranch}$, $\mathrm{EndRide}$, $\mathrm{Optimize}$,
$\mathrm{VerifySolution}$, $\mathrm{ContinueBranching}$

2:Select optimization parameters $\alpha$

3:Find starting parameters
$\bm{\omega}^{\textnormal{start}}={\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathrm{FindStartingPoint}(\alpha)}$

4:Initialize a branch
$\psi^{\textnormal{init}}=\mathrm{InitBranch}(\bm{\omega}^{\textnormal{start}},\alpha)$

5:Initialize the set of branches
$\mathcal{B}={\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathrm{SplitBranch}}(\psi^{\textnormal{init}})$

6:Initialize the set of solutions $\mathcal{S}=\emptyset$

7:while $\textnormal{Branches }\mathcal{B}\textnormal{ non-empty}$ do

8: $\psi,\mathcal{B}=\mathrm{ChooseBranch}(\mathcal{B})$

9:
$\bm{\omega}^{*}={\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathrm{Optimize}}(\psi.\bm{\omega},\psi.\alpha)$
# Optimize our parameters

10: if $\mathrm{VerifySolution}(\bm{\omega}^{*})$ then

11: $\mathcal{S}=\mathcal{S}\cup\\{\bm{\omega}^{*}\\}$

12: end if

13: Make new branch to split $\psi^{\prime}=\mathrm{copy}(\psi)$

14: Store the optimized parameters
$\psi^{\prime}\textnormal{.parameters}=\bm{\omega}^{*}$

15: if $\mathrm{ContinueBranching}(\psi^{\prime})$ then

16:
$\mathcal{B}=\mathcal{B}\cup{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathrm{SplitBranch}}(\psi^{\prime})$

17: end if

18:end while

19:return $\mathcal{S}$

###  C.3 Experiments

####  C.3.1 Test Problems

Iterated Prisoners’ Dilemma (IPD): This game is an infinite sequence of the
Prisoner’s Dilemma, where the future payoff is discounted by $\gamma\in[0,1)$.
In other words, the rewards sequences $r_{j}$ for each player were summed
through $\sum_{j=0}^{\infty}\gamma^{j}r_{j}$. Each agent is conditioned on the
actions in the prior state ($s$). Thus, there are 5 parameters for each agent
$i$: $P^{i}(C|s)$ is the probability of cooperating in the start state
$s_{0}=\emptyset$ or in the state $s_{t}=\left(a^{1}_{t-1},a^{2}_{t-1}\right)$
for $t>0$. There are two Nash equilibria we care about: Defect-Defect (DD),
where agents are selfish (resulting in poor reward), and tit-for-tat (TT),
where agents initially cooperate, then copy the opponents’ action (resulting
in higher reward).

Small IPD: This is a 2-parameter simplification of IPD, which allows DD and TT
Nash equilibria. We fix the strategy if our opponent defects, to defect with
high probability. We also constrain the probability of cooperating to depend
only on whether the opponent cooperates, and in the initial state, we assume
our opponent cooperated. This game allows us to visualize some optimization
difficulties for the full-scale IPD. However, the game Hessian has strictly
real eigenvalues, unlike the full-scale IPD. See Figure 5.2 top for a
visualization of the strategy space.

Matching Pennies: This is a simplified 2-parameter version of rock-paper-
scissors, where each player selects to cooperate or defect. This game has a
Nash equilibrium, in which players select their actions uniformly. Notably,
this problem’s game Hessian has purely imaginary eigenvalues, so following the
gradient does not converge to solutions, and we need a method for learning in
games like LOLA. Also, this game only has one solution. Thus, it is a poor fit
for evaluating RR, which finds diverse solutions. See Figure 5.2, bottom for a
visualization of the strategy space.

Mixing Small IPD and Matching Pennies: This game interpolates between the
Small IPD and Matching Pennies games, with the loss for player $j$:

$\mathcal{L}_{\textnormal{mix},P_{j},\tau}=\tau\mathcal{L}_{\textnormal{smallIPD},P_{j}}+(1-\tau)\mathcal{L}_{\textnormal{matchingPennies},P_{j}}$
(C.1)

This problem has two solutions: one where both players cooperate and one where
both players select actions uniformly. The uniform action solution has
imaginary eigenvalues, so it is only stable under a method for learning in
games, while the both cooperate solution has real eigenvalues. There is a Hopf
bifurcation that separates these solutions. See Figure 5.2 for standard
methods on this problem and Appendix Figure C.1 to contrast this problem with
Small IPD or Matching Pennies.

Player 1 StrategyPlayer 2 StrategySmall IPDPlayer 2 StrategyMixed
ProblemJoint-player grad. log-norm $\log(\|\hat{\bm{g}}\|)$Player 2
StrategyMatching Pennies Figure C.1:  This shows the phase portrait for two
standard optimization algorithms on various problems. Following the gradient
is shown in red, while LOLA – a method for learning in games – is shown in
blue. _Left_ : The small IPD has solutions in the top right and bottom left.
_Middle_ : Matching Pennies, which has a single solution in the middle.
Following the gradient does not find this solution because it has imaginary
eigenvalues, so we must use a method like LOLA. _Right_ : A mixture of small
IPD and Matching Pennies. Following the gradient only finds the solution in
the top right because the center solution has imaginary eigenvalues; LOLA can
find either solution. Takeaway: The mixture game has a range of phenomena,
including an imaginary eigenvalue solution, a real eigenvalue solution, and a
Hopf bifurcation. We may want to use a method for learning in games to
converge robustly to different solutions.  Player 1 StrategyPlayer 2
StrategyDifferent direction estimation strategies in $10$-step Lyapunov
exponent calculationRandom DirectionPower Iteration, first stepPower
Iteration, every stepjax.numpy.linalg.eigh every stepMax $10$-step Lyapunov
Exponent Figure C.2:  We compare different methods for choosing a direction in
the max $10$-step Lyapunov exponent calculation on the Mixed Objective.
_Takeaway:_ Re-estimating the top eigenvectors at each iteration performs best
but is most expensive. _Left_ : We uniformly sample a random normalized
direction for our displacement $\bm{d}$ at each exponent calculation, which
does not clearly show the bifurcation. _Middle_ : We perform $10$ steps of
power iteration to tune $\bm{d}$. First, we tune the displacement only at the
first iteration, which shows the bifurcation. Next, we tune the displacement
at every iteration in the exponent calculation, which shows the bifurcation
more clearly. _Right_ : We use jax.numpy.linalg.eigh to tune $\bm{d}$, which
also clearly shows the bifurcation.  Player 1 StrategyMax $1$-step Lyapunov
ExponentMax $5$-step Lyapunov ExponentMax $10$-step Lyapunov ExponentPlayer 1
StrategyPlayer 2 StrategyMax $100$-step Lyapunov ExponentPlayer 2 Strategy
Figure C.3:  We show the $k$-step Lyapunov exponent calculation for various
$k$ on the small IPD. The $k$-step optimization trajectories used for
calculating the exponent are shown in red, allowing us to see the horizon over
which the associated exponent measures separation. _Takeaway:_ We can
effectively find bifurcations with a $k$-step exponent for various $k$. Using
only $1$-step does not show the bifurcation, while using more does. As $k$
gets larger, the scale of the gradients changes, causing difficult
optimization in the limit – note the changing color bar scale.  Player 1
StrategyMax $10$-step Lyapunov ExponentLOLAPlayer 1 StrategyPlayer 2
StrategySimSGD Figure C.4:  We contrast the max $20$-step Lyapunov exponent
calculations between LOLA and SimSGD. The $20$-step optimization trajectories
used for calculating the exponent are shown in red, allowing us to see the
trajectories in which the associated exponent measures separation. Takeaway:
We can find optimizer-dependent bifurcations with our method. _Top:_ $10$
steps from the optimization with LOLA at each point where we calculate an
exponent for the heatmap. _Bottom:_ The same visualization as the top, except
with a SimSGD optimizer.  Player 1 StrategyMax $10$-step Lyapunov ExponentStep
size $\alpha=10$Player 1 StrategyPlayer 2 StrategyStep size $\alpha=20$ Figure
C.5:  We investigate the impact of optimization algorithm parameters on the
$10$-step max Lyapunov exponent calculation with LOLA. The $10$-step
optimization trajectories used for calculating the exponent are shown in red,
allowing us to see the trajectories in which the associated exponent measures
separation. Takeaway: If the step size is too large, the optimizer does not
converge to solutions, resulting in limit cycles. _Top:_ $10$ steps from the
optimization with a step size of $\alpha=10$ at each point where we calculate
an exponent for the heatmap. _Bottom:_ The same visualization as the top,
except with a step size of $\alpha=20$. Optimization trajectories only
converge at the solution in the top right. In the center, the trajectories
accumulate in a limit cycle, rotating around the solution.  $y$Max $10$-step
Lyapunov Exponent$x$ Figure C.6:  We investigate finding bifurcations with a
$10$-step max Lyapunov exponent on a single-objective optimization problem
from RR. The optimization trajectories used for the calculation of the
exponent are shown in red, allowing us to verify where the bifurcations are.
Takeaway: Our method effectively highlights bifurcations in RRs example.
$x_{0}$$r$ Figure C.7:  We display the Lyapunov exponent on the logistic map:
$x(t+1)=x(t)+r+x(t)^{2}$. Takeaway: Intuition for Lyapunov exponents on a
canonical 1-dimensional example for bifurcations.  Player 1 StrategyMax =
1-direction Lyapunov ExponentPlayer 1 StrategyPlayer 2 StrategySum of top 2
Lyapunov Exponents Figure C.8:  We compare different $10$-step Lyapunov
exponent objectives trying to guarantee divergence in multiple directions on
the small IPD. The optimization trajectories used for the exponent calculation
are shown in red, allowing us to see the trajectories for the associated
objective. Takeaway: We can find bifurcations while guaranteeing trajectory
separation in every direction. Local maxima – not saddles – allow trajectory
separation in all directions here. _Top:_ The max $10$-step Lyapunov exponent.
_Bottom:_ The sum of the top two $10$-step Lyapunov exponents.  Figure C.9:
Ground truth samples for our Mixture of Gaussian experiments.  Player 1
StrategySubspace seed 0Player 2 StrategyRandom subspace IPDSubspace seed
1Subspace seed 2Subspace seed 3DiscriminatorSubspace seed 0GeneratorRandom
subspace GANSubspace seed 1Subspace seed 2Subspace seed 3Max $10$-step
Lyapunov Exponent Figure C.10:  This reproduces Figure 5.7 with more random
subspaces. The optimization trajectories used for the exponent calculation are
shown in red, allowing us to see the trajectories the associated exponent
measures separation over. _Takeaway:_ The exponent is peaked near where
trajectories separate for each subspace, showing that these strategies can
find various bifurcations. We display the Lyapunov exponent calculation – as
in Figure 5.6 – on more complicated toy problems to see how robustly we can
find different bifurcations. Section 5.5 describes how we construct these
examples by taking higher-dimensional problems and optimizing them in a random
subspace. _Top:_ Different IPD subspaces: we effectively highlight
bifurcations – i.e., regions where trajectory behavior qualitatively changes.
_Bottom:_ Different GAN subspaces: we can find bifurcations, but the
highlighted structure is less crisp in this more complicated and stochastic
toy example.  loss
$\mathcal{L}_{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}^{\textnormal{min}}(\bm{\omega}_{0})$=
-Max exp lossargument of EVal $\arg(\lambda)$EVals of Jac. of fixed-point
operator $\operatorname*{Sp}(\bm{J})$loss
$\mathcal{L}_{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}5}}^{\textnormal{min}}(\bm{\omega}_{0})$=
-Min top 5 expsargument of EVal $\arg(\lambda)$loss
$\mathcal{L}_{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}10}}^{\textnormal{min}}(\bm{\omega}_{0})$
= -Min top 10 expsoptimization iterationargument of EVal $\arg(\lambda)$log-
norm of EVal $\log(|\lambda|)$ Figure C.11:  We compare the optimization for
different losses using the local Lyapunov exponent with varying numbers of
exponents. _Takeaway:_ We can effectively optimize multiple exponents, which
give trajectory separation in multiple directions. Our objective is the
minimum of the top $n$ local Lyapunov exponents, with a different $n$’s
optimization trajectory shown in each row. To review this visualization also
in Figure 5.5: The spectrum is shown with a scatterplot in blue and a
progressively larger alpha at each iteration. The final spectrum is shown in
red. For the Jacobian of the fixed-point operator $\bm{J}$, a vertical red
line is shown where the eigenvalue norm equals $1$, signifying the cutoff
between (locally) convergent and divergent eigenspaces. _Top_ : Optimizing the
max local Lyapunov exponent from Figure 5.5, where the largest eigenvalue is
effectively maximized. _Middle_ : Optimizing the top $5$ local exponents,
where we find $5$ moderately divergent directions instead of $1$ extremely
divergent direction as in the top. _Bottom_ : Optimizing the top $10$ local
exponents results in trajectory separation in all directions. We study
different objectives of the top $n$ exponents in Appendix Figure C.12, and
study non-local $k$-step exponents in Appendix Figure C.13.  loss
$\mathcal{L}_{10}^{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\textnormal{min}}}(\bm{\omega}_{0})$=
-Min top 10 expsargument of EVal $\arg(\lambda)$EVals of Jac. of fixed-point
operator $\operatorname*{Sp}(\bm{J})$loss
$\mathcal{L}_{10}^{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\textnormal{sum}}}(\bm{\omega}_{0})$=
-Sum top 10 expsoptimization iterationargument of EVal $\arg(\lambda)$log-norm
of EVal $\log(|\lambda|)$ Figure C.12:  We compare the optimization for
different losses using the top $10$ local Lyapunov exponents. _Takeaway:_
Using the minimum of the top exponents is a strong method to guarantee
separation in many directions. This visualizes the same aspects as Figure 5.5:
The spectrum is shown with a scatterplot in blue and a progressively larger
alpha at each iteration. The final spectrum is shown in red. For the Jacobian
of the fixed-point operator $\bm{J}$, a vertical red line is shown where the
eigenvalue norm equals $1$, signifying the cutoff between (locally) convergent
and divergent eigenspaces. _Top:_ To guarantee trajectory separation in all
directions, we optimize the minimum of the top exponents. At the end of the
training, all eigenvalues of $\bm{J}$ are greater than $1$, signifying local
trajectory separation in all directions. _Bottom:_ We optimize the sum of the
top $10$ exponents, which does not guarantee trajectory separation in every
direction. Our optimizer is happy with solutions diverging rapidly in the top
directions while converging (slowly) in the bottom directions.  10-step loss
$\mathcal{L}^{\textnormal{min}}_{1}(\bm{\omega}_{0})=-\hat{\lambda}_{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}10}}^{\textnormal{max}}(\bm{\omega}_{0})$optimization
iteration Figure C.13:  We investigate optimizing a loss of the max $k$-step
Lyapunov exponent for $k>1$. _Takeaway:_ We effectively minimize multi-step
exponents in higher-dimensional problems if required, extending the
visualization in Figure 5.5.

## References

  * Maclaurin et al. (2015a) Dougal Maclaurin, David Duvenaud, and Ryan Adams.  Gradient-based hyperparameter optimization through reversible learning.  In _International Conference on Machine Learning_ , pages 2113–2122, 2015a.
  * Andrychowicz et al. (2016) Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas.  Learning to learn by gradient descent by gradient descent.  In _Advances in Neural Information Processing Systems_ , pages 3981–3989, 2016.
  * Fu et al. (2016) Jie Fu, Hongyin Luo, Jiashi Feng, Kian Hsiang Low, and Tat-Seng Chua.  DrMAD: Distilling reverse-mode automatic differentiation for optimizing hyperparameters of deep neural networks.  In _International Joint Conference on Artificial Intelligence_ , pages 1469–1475, 2016.
  * Shaban et al. (2019) Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots.  Truncated back-propagation for bilevel optimization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1723–1732, 2019.
  * Goodfellow et al. (2014) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In _Advances in neural information processing systems_ , pages 2672–2680, 2014.
  * Pfau and Vinyals (2016) David Pfau and Oriol Vinyals.  Connecting generative adversarial networks and actor-critic methods.  _arXiv preprint arXiv:1610.01945_ , 2016.
  * Baker et al. (2019) Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch.  Emergent tool use from multi-agent autocurricula.  In _International Conference on Learning Representations_ , 2019.
  * Balduzzi et al. (2019) David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojciech Czarnecki, Julien Perolat, Max Jaderberg, and Thore Graepel.  Open-ended learning in symmetric zero-sum games.  In _International Conference on Machine Learning_ , pages 434–443. PMLR, 2019.
  * Sukhbaatar et al. (2018) Sainbayar Sukhbaatar, Zeming Lin, Ilya Kostrikov, Gabriel Synnaeve, Arthur Szlam, and Rob Fergus.  Intrinsic motivation and automatic curricula via asymmetric self-play.  In _International Conference on Learning Representations_ , 2018.
  * Bose et al. (2020) Avishek Joey Bose, Gauthier Gidel, Hugo Berrard, Andre Cianflone, Pascal Vincent, Simon Lacoste-Julien, and William L Hamilton.  Adversarial example games.  _arXiv preprint arXiv:2007.00720_ , 2020.
  * Yuan et al. (2019) Xiaoyong Yuan, Pan He, Qile Zhu, and Xiaolin Li.  Adversarial examples: Attacks and defenses for deep learning.  _IEEE Transactions on Neural Networks and Learning Systems_ , 30(9):2805–2824, 2019.
  * Rajeswaran et al. (2020) Aravind Rajeswaran, Igor Mordatch, and Vikash Kumar.  A game theoretic framework for model based reinforcement learning.  _arXiv preprint arXiv:2004.07804_ , 2020.
  * Abachi et al. (2020) Romina Abachi, Mohammad Ghavamzadeh, and Amir-massoud Farahmand.  Policy-aware model learning for policy gradient methods.  _arXiv preprint arXiv:2003.00030_ , 2020.
  * Nikishin et al. (2021) Evgenii Nikishin, Romina Abachi, Rishabh Agarwal, and Pierre-Luc Bacon.  Control-oriented model-based reinforcement learning with implicit differentiation.  _arXiv preprint arXiv:2106.03273_ , 2021.
  * Acuna et al. (2021) David Acuna, Guojun Zhang, Marc T Law, and Sanja Fidler.  f-domain-adversarial learning: Theory and algorithms for unsupervised domain adaptation with neural networks, 2021.  URL https://openreview.net/forum?id=WqXAKcwfZtI.
  * Elsken et al. (2019) Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter.  Neural architecture search: A survey.  _The Journal of Machine Learning Research_ , 20(1):1997–2017, 2019.
  * Finn et al. (2017) Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _International Conference on Machine Learning_ , pages 1126–1135, 2017.
  * Ren et al. (2018a) Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua B Tenenbaum, Hugo Larochelle, and Richard S Zemel.  Meta-learning for semi-supervised few-shot classification.  _arXiv preprint arXiv:1803.00676_ , 2018a.
  * Ren et al. (2020) Mengye Ren, Eleni Triantafillou, Kuan-Chieh Wang, James Lucas, Jake Snell, Xaq Pitkow, Andreas S Tolias, and Richard Zemel.  Flexible few-shot learning with contextual similarity.  _arXiv preprint arXiv:2012.05895_ , 2020.
  * Raghu et al. (2020) Aniruddh Raghu, Maithra Raghu, Simon Kornblith, David Duvenaud, and Geoffrey Hinton.  Teaching with commentaries.  _arXiv preprint arXiv:2011.03037_ , 2020.
  * Von Stackelberg (1952) Heinrich Von Stackelberg.  _The theory of the market economy_.  William Hodge, 1952.
  * Vicol et al. (2022a) Paul Vicol, Jonathan P Lorraine, Fabian Pedregosa, David Duvenaud, and Roger B Grosse.  On implicit bias in overparameterized bilevel optimization.  In _International Conference on Machine Learning_ , pages 22234–22259. PMLR, 2022a.
  * Berard et al. (2019) Hugo Berard, Gauthier Gidel, Amjad Almahairi, Pascal Vincent, and Simon Lacoste-Julien.  A closer look at the optimization landscapes of generative adversarial networks.  In _International Conference on Learning Representations_ , 2019.
  * Močkus (1975) Jonas Močkus.  On Bayesian methods for seeking the extremum.  In _Optimization Techniques IFIP Technical Conference_ , pages 400–404, 1975.
  * Snoek et al. (2012) Jasper Snoek, Hugo Larochelle, and Ryan Adams.  Practical Bayesian optimization of machine learning algorithms.  In _Advances in Neural Information Processing Systems_ , pages 2951–2959, 2012.
  * Mehta et al. (2024a) Nikhil Mehta, Jonathan Lorraine, Steve Masson, Ramanathan Arunachalam, Zaid Pervaiz Bhat, James Lucas, and Arun George Zachariah.  Improving hyperparameter optimization with checkpointed model weights.  _arXiv preprint arXiv:2406.18630_ , 2024a.
  * Mehta et al. (2024b) Nikhil Mehta, Jonathan Lorraine, Steve Masson, Zaid Arunachalam, Ramanathan Pervaiz Bhat, James Lucas, and Arun George Zachariah.  Improving hyperparameter optimization with checkpointed model weights.  In _In Submission to Advances in Neural Information Processing Systems (NeurIPS)_ , 2024b.
  * Bae et al. (2024) Juhan Bae, Wu Lin, Jonathan Lorraine, and Roger Grosse.  Training data attribution via approximate unrolled differentiation.  _arXiv preprint arXiv:2405.12186_ , 2024.
  * Xie et al. (2024) Kevin Xie, Jonathan Lorraine, Tianshi Cao, Jun Gao, James Lucas, Antonio Torralba, Antonio Torralba, Sanja Fidler, and Xiaohui Zeng.  Latte3d: Large-scale amortized text-to-enhanced3d synthesis.  _arXiv preprint arXiv:2403.15385_ , 2024.
  * Lim et al. (2024) Derek Lim, Haggai Maron, Marc T. Law, Jonathan Lorraine, and James Lucas.  Graph metanetworks for processing diverse neural architectures.  In _The International Conference on Learning Representations (ICLR)_ , 2024.
  * Lim et al. (2023) Derek Lim, Haggai Maron, Marc T Law, Jonathan Lorraine, and James Lucas.  Graph metanetworks for processing diverse neural architectures.  _arXiv preprint arXiv:2312.04501_ , 2023.
  * Zhang et al. (2023a) Michael Zhang, Nishkrit Desai, Juhan Bae, Jonathan Lorraine, and Jimmy Ba.  Using large language models for hyperparameter optimization.  In _Advances in Neural Information Processing Systems (NeurIPS) 2023 Foundation Models for Decision Making Workshop_ , 2023a.
  * Zhang et al. (2023b) Michael R Zhang, Nishkrit Desai, Juhan Bae, Jonathan Lorraine, and Jimmy Ba.  Using large language models for hyperparameter optimization.  _arXiv preprint arXiv:2312.04528_ , 2023b.
  * Lorraine et al. (2023a) Jonathan Lorraine, Kevin Xie, Xiaohui Zeng, Chen-Hsuan Lin, Towaki Takikawa, Nicholas Sharp, Tsung-Yi Lin, Ming-Yu Liu, Sanja Fidler, and James Lucas.  Att3d: Amortized text-to-3d object synthesis.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 17946–17956, 2023a.
  * Lorraine et al. (2023b) Jonathan Lorraine, Kevin Xie, Xiaohui Zeng, Chen-Hsuan Lin, Towaki Takikawa, Nicholas Sharp, Tsung-Yi Lin, Ming-Yu Liu, Sanja Fidler, and James Lucas.  Att3d: Amortized text-to-3d object synthesis.  _arXiv preprint arXiv:2306.07349_ , 2023b.
  * Lorraine et al. (2022a) Jonathan Lorraine, Nihesh Anderson, Chansoo Lee, Quentin De Laroussilhe, and Mehadi Hassen.  Task selection for automl system evaluation.  _arXiv preprint arXiv:2208.12754_ , 2022a.
  * Vicol et al. (2022b) Paul Vicol, Jonathan Lorraine, Fabian Pedregosa, David Duvenaud, and Roger Grosse.  On implicit bias in overparameterized bilevel optimization, 2022b.
  * Vicol et al. (2021) Paul Vicol, Jonathan Lorraine, David Duvenaud, and Roger Grosse.  Implicit regularization in overparameterized bilevel optimization.  In _ICML 2021 Beyond First Order Methods Workshop_ , 2021.
  * Richter-Powell et al. (2021) Jack Richter-Powell, Jonathan Lorraine, and Brandon Amos.  Input convex gradient networks.  _arXiv preprint arXiv:2111.12187_ , 2021.
  * Raghu et al. (2021a) Aniruddh Raghu, Jonathan Lorraine, Simon Kornblith, Matthew McDermott, and David K Duvenaud.  Meta-learning to improve pre-training.  _Advances in Neural Information Processing Systems_ , 34, 2021a.
  * Raghu et al. (2021b) Aniruddh Raghu, Jonathan Lorraine, Simon Kornblith, Matthew McDermott, and David Duvenaud.  Meta-learning to improve pre-training.  _arXiv preprint arXiv:2111.01754_ , 2021b.
  * Lorraine and Hossain (2019) Jonathan Lorraine and Safwan Hossain.  Jacnet: Learning functions with structured jacobians.  In _ICML INNF Workshop_ , 2019.
  * MacKay et al. (2019a) Matthew MacKay, Paul Vicol, Jon Lorraine, David Duvenaud, and Roger Grosse.  Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions.  In _International Conference on Learning Representations_ , 2019a.
  * MacKay et al. (2019b) Matthew MacKay, Paul Vicol, Jon Lorraine, David Duvenaud, and Roger Grosse.  Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions.  _arXiv preprint arXiv:1903.03088_ , 2019b.
  * Adam and Lorraine (2019) George Adam and Jonathan Lorraine.  Understanding neural architecture search techniques.  _arXiv preprint arXiv:1904.00438_ , 2019.
  * Lorraine and Duvenaud (2017) Jonathan Lorraine and David Duvenaud.  Hyperparameter optimization with hypernets.  In _31st Conference on Neural Information Processing Systems (NIPS 2017), Workshop on Meta-learning_ , Long Beach, USA, 2017.
  * Bae and Grosse (2020) Juhan Bae and Roger B Grosse.  Delta-stn: Efficient bilevel optimization for neural networks using structured response jacobians.  _Advances in Neural Information Processing Systems_ , 33:21725–21737, 2020.
  * Li et al. (2016) Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar.  Hyperband: A novel bandit-based approach to hyperparameter optimization.  _arXiv preprint arXiv:1603.06560_ , 2016.
  * Swersky et al. (2014) Kevin Swersky, Jasper Snoek, and Ryan Prescott Adams.  Freeze-thaw bayesian optimization.  _arXiv preprint arXiv:1406.3896_ , 2014.
  * Ha et al. (2016) David Ha, Andrew Dai, and Quoc V. Le.  Hypernetworks.  _arXiv preprint arXiv:1609.09106_ , 2016.
  * Brock et al. (2017) Andrew Brock, Theodore Lim, JM Ritchie, and Nick Weston.  Smash: One-shot model architecture search through hypernetworks.  _arXiv preprint arXiv:1708.05344_ , 2017.
  * Rasmussen and Williams (2006) Carl Edward Rasmussen and Christopher KI Williams.  _Gaussian processes for machine learning_ , volume 1.  MIT press Cambridge, 2006.
  * Amos (2022) Brandon Amos.  Tutorial on amortized optimization for learning to optimize over continuous domains.  _arXiv e-prints_ , pages arXiv–2202, 2022.
  * Requeima et al. (2019) James Requeima, Jonathan Gordon, John Bronskill, Sebastian Nowozin, and Richard E Turner.  Fast and flexible multi-task classification using conditional neural adaptive processes.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Ratzlaff and Fuxin (2019) Neale Ratzlaff and Li Fuxin.  Hypergan: A generative model for diverse, performant neural networks.  In _International Conference on Machine Learning_ , pages 5361–5369. PMLR, 2019.
  * Pilault et al. (2020) Jonathan Pilault, Amine Elhattami, and Christopher Pal.  Conditionally adaptive multi-task learning: Improving transfer learning in nlp using fewer parameters & less data.  _arXiv preprint arXiv:2009.09139_ , 2020.
  * Tay et al. (2020) Yi Tay, Zhe Zhao, Dara Bahri, Donald Metzler, and Da-Cheng Juan.  Hypergrid transformers: Towards a single model for multiple tasks.  In _International Conference on Learning Representations_ , 2020.
  * Rusu et al. (2018) Andrei A Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osindero, and Raia Hadsell.  Meta-learning with latent embedding optimization.  _arXiv preprint arXiv:1807.05960_ , 2018.
  * Bergstra and Bengio (2012) James Bergstra and Yoshua Bengio.  Random search for hyper-parameter optimization.  _Journal of Machine Learning Research_ , 13(Feb):281–305, 2012.
  * Snoek et al. (2019) Jasper Snoek, Michael Gelbart, et al.  Spearmint: A software package for bayesian optimization.  https://github.com/HIPS/Spearmint, 2019.
  * Alexandropoulos et al. (2019) Stamatios-Aggelos N Alexandropoulos, Christos K Aridas, Sotiris B Kotsiantis, and Michael N Vrahatis.  Multi-objective evolutionary optimization algorithms for machine learning: A recent survey.  _Approximation and Optimization: Algorithms, Complexity and Applications_ , pages 35–55, 2019.
  * Jaderberg et al. (2017) Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, Iain Dunning, Karen Simonyan, et al.  Population based training of neural networks.  _arXiv preprint arXiv:1711.09846_ , 2017.
  * Domke (2012) Justin Domke.  Generic methods for optimization-based modeling.  In _Artificial Intelligence and Statistics_ , pages 318–326, 2012.
  * Franceschi et al. (2017) Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil.  Forward and reverse gradient-based hyperparameter optimization.  In _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 1165–1173. PMLR, 2017.
  * LeCun et al. (1998) Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Nair and Hinton (2010) Vinod Nair and Geoffrey E. Hinton.  Rectified linear units improve restricted boltzmann machines.  In _Proceedings of the 27th international conference on machine learning (ICML-10)_ , pages 807–814, 2010.
  * Maclaurin et al. (2015b) Dougal Maclaurin, David Duvenaud, and Ryan P. Adams.  Autograd: Effortless gradients in numpy.  ICML 2015 AutoML Workshop, 2015b.
  * Kingma and Ba (2014) Diederik Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Lorraine and Duvenaud (2018) Jonathan Lorraine and David Duvenaud.  Stochastic hyperparameter optimization through hypernetworks.  _arXiv preprint arXiv:1802.09419_ , 2018.
  * Schmidhuber (1987) Jürgen Schmidhuber.  _Evolutionary principles in self-referential learning, or on learning how to learn: The meta-meta-… hook_.  PhD thesis, Technische Universität München, 1987.
  * Bengio (2000) Yoshua Bengio.  Gradient-based optimization of hyperparameters.  _Neural Computation_ , 12(8):1889–1900, 2000.
  * Franceschi et al. (2018) Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil.  Bilevel programming for hyperparameter optimization and meta-learning.  In _International Conference on Machine Learning_ , pages 1563–1572, 2018.
  * Rajeswaran et al. (2019) Aravind Rajeswaran, Chelsea Finn, Sham Kakade, and Sergey Levine.  Meta-learning with implicit gradients.  _arXiv preprint arXiv:1909.04630_ , 2019.
  * Liu et al. (2018) Hanxiao Liu, Karen Simonyan, and Yiming Yang.  Darts: Differentiable architecture search.  _arXiv preprint arXiv:1806.09055_ , 2018.
  * Grefenstette et al. (2019) Edward Grefenstette, Brandon Amos, Denis Yarats, Phu Mon Htut, Artem Molchanov, Franziska Meier, Douwe Kiela, Kyunghyun Cho, and Soumith Chintala.  Generalized inner loop meta-learning.  _arXiv preprint arXiv:1910.01727_ , 2019.
  * Mehra and Hamm (2019) Akshay Mehra and Jihun Hamm.  Penalty method for inversion-free deep bilevel optimization.  _arXiv preprint arXiv:1911.03432_ , 2019.
  * Kukačka et al. (2017) Jan Kukačka, Vladimir Golkov, and Daniel Cremers.  Regularization for deep learning: A taxonomy.  _arXiv preprint arXiv:1710.10686_ , 2017.
  * Wang et al. (2018) Tongzhou Wang, Jun-Yan Zhu, Antonio Torralba, and Alexei A Efros.  Dataset distillation.  _arXiv preprint arXiv:1811.10959_ , 2018.
  * Ren et al. (2018b) Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun.  Learning to reweight examples for robust deep learning.  In _International Conference on Machine Learning_ , pages 4331–4340, 2018b.
  * Kim and Choi (2018) Tae-Hoon Kim and Jonghyun Choi.  ScreenerNet: Learning self-paced curriculum for deep neural networks.  _arXiv preprint arXiv:1801.00904_ , 2018.
  * Zhang et al. (2019a) Jiong Zhang, Hsiang-fu Yu, and Inderjit Dhillon.  AutoAssist: A framework to accelerate training of deep neural networks.  _arXiv preprint arXiv:1905.03381_ , 2019a.
  * Cubuk et al. (2018) Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le.  Autoaugment: Learning augmentation policies from data.  _arXiv preprint arXiv:1805.09501_ , 2018.
  * Xie et al. (2019) Qizhe Xie, Zihang Dai, Eduard Hovy, Minh-Thang Luong, and Quoc V Le.  Unsupervised data augmentation.  _arXiv preprint arXiv:1904.12848_ , 2019.
  * Kandasamy et al. (2019) Kirthevasan Kandasamy, Karun Raju Vysyaraju, Willie Neiswanger, Biswajit Paria, Christopher R Collins, Jeff Schneider, Barnabas Poczos, and Eric P Xing.  Tuning hyperparameters without grad students: Scalable and robust Bayesian optimisation with Dragonfly.  _arXiv preprint arXiv:1903.06694_ , 2019.
  * Liao et al. (2018) Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urtasun, and Richard Zemel.  Reviving and improving recurrent back-propagation.  In _International Conference on Machine Learning_ , pages 3088–3097, 2018.
  * Pearlmutter (1994) Barak A Pearlmutter.  Fast exact multiplication by the hessian.  _Neural computation_ , 6(1):147–160, 1994.
  * Christianson (1998) Bruce Christianson.  Reverse aumulation and imploicit functions.  _Optimization Methods and Software_ , 9(4):307–322, 1998.
  * Larsen et al. (1996) Jan Larsen, Lars Kai Hansen, Claus Svarer, and M Ohlsson.  Design and regularization of neural networks: The optimal use of a validation set.  In _Neural Networks for Signal Processing VI. Proceedings of the 1996 IEEE Signal Processing Society Workshop_ , pages 62–71, 1996.
  * Ochs et al. (2015) Peter Ochs, René Ranftl, Thomas Brox, and Thomas Pock.  Bilevel optimization with nonsmooth lower level problems.  In _International Conference on Scale Space and Variational Methods in Computer Vision_ , pages 654–665, 2015.
  * Wang et al. (2019a) Yuanhao Wang, Guodong Zhang, and Jimmy Ba.  On solving minimax optimization locally: A follow-the-ridge approach.  _arXiv preprint arXiv:1910.07512_ , 2019a.
  * Lee et al. (2019) Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto.  Meta-learning with differentiable convex optimization.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 10657–10665, 2019.
  * Beirami et al. (2017) Ahmad Beirami, Meisam Razaviyayn, Shahin Shahrampour, and Vahid Tarokh.  On optimal generalizability in parametric learning.  In _Advances in Neural Information Processing Systems_ , pages 3455–3465, 2017.
  * Koh and Liang (2017) Pang Wei Koh and Percy Liang.  Understanding black-box predictions via influence functions.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 1885–1894. JMLR. org, 2017.
  * Luketina et al. (2016) Jelena Luketina, Mathias Berglund, Klaus Greff, and Tapani Raiko.  Scalable gradient-based tuning of continuous regularization hyperparameters.  In _International Conference on Machine Learning_ , pages 2952–2960, 2016.
  * Pedregosa (2016) Fabian Pedregosa.  Hyperparameter optimization with approximate gradient.  In _International Conference on Machine Learning_ , pages 737–746, 2016.
  * Bai et al. (2019) Shaojie Bai, J Zico Kolter, and Vladlen Koltun.  Deep equilibrium models.  _arXiv preprint arXiv:1909.01377_ , 2019.
  * Agarwal et al. (2017) Naman Agarwal, Brian Bullins, and Elad Hazan.  Second-order stochastic optimization for machine learning in linear time.  _The Journal of Machine Learning Research_ , 18(1):4148–4187, 2017.
  * Martens and Grosse (2015) James Martens and Roger Grosse.  Optimizing neural networks with Kronecker-factored approximate curvature.  In _International Conference on Machine Learning_ , pages 2408–2417, 2015.
  * Balaji et al. (2018) Yogesh Balaji, Swami Sankaranarayanan, and Rama Chellappa.  Metareg: Towards domain generalization using meta-regularization.  In _Advances in Neural Information Processing Systems_ , pages 998–1008, 2018.
  * Shavitt and Segal (2018) Ira Shavitt and Eran Segal.  Regularization learning networks: Deep learning for tabular datasets.  In _Advances in Neural Information Processing Systems_ , pages 1379–1389, 2018.
  * Nichol et al. (2018) Alex Nichol, Joshua Achiam, and John Schulman.  On first-order meta-learning algorithms.  _arXiv preprint arXiv:1803.02999_ , 2018.
  * Mescheder et al. (2017) Lars Mescheder, Sebastian Nowozin, and Andreas Geiger.  The numerics of gans.  In _Advances in Neural Information Processing Systems_ , pages 1825–1835, 2017.
  * Wu et al. (2018) Yuhuai Wu, Mengye Ren, Renjie Liao, and Roger Grosse.  Understanding short-horizon bias in stochastic meta-optimization.  _arXiv preprint arXiv:1803.02021_ , 2018.
  * Balduzzi et al. (2018) David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel.  The mechanics of n-player differentiable games.  In _International Conference on Machine Learning_ , pages 363–372, 2018.
  * Banach (1922) Stefan Banach.  Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales.  _Fundamenta Mathematicae_ , 3:133–181, 1922.
  * Maddison et al. (2017) C Maddison, A Mnih, and Y Teh.  The concrete distribution: A continuous relaxation of discrete random variables.  In _International Conference on Learning Representations_ , 2017.
  * Jang et al. (2016) Eric Jang, Shixiang Gu, and Ben Poole.  Categorical reparameterization with Gumbel-softmax.  _arXiv preprint arXiv:1611.01144_ , 2016.
  * Jamieson and Talwalkar (2016) Kevin Jamieson and Ameet Talwalkar.  Non-stochastic best arm identification and hyperparameter optimization.  In _Artificial Intelligence and Statistics_ , pages 240–248, 2016.
  * Kumar et al. (2018) Manoj Kumar, George E Dahl, Vijay Vasudevan, and Mohammad Norouzi.  Parallel architecture and hyperparameter search via successive halving and classification.  _arXiv preprint arXiv:1805.10255_ , 2018.
  * Harrison Jr and Rubinfeld (1978) David Harrison Jr and Daniel L Rubinfeld.  Hedonic housing prices and the demand for clean air.  _Journal of Environmental Economics and Management_ , 5(1):81–102, 1978.
  * Zhang et al. (2018) Guodong Zhang, Shengyang Sun, David Duvenaud, and Roger Grosse.  Noisy natural gradient as variational inference.  In _International Conference on Machine Learning_ , pages 5847–5856, 2018.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  ImageNet classification with deep convolutional neural networks.  In _Advances in Neural Information Processing Systems_ , pages 1097–1105, 2012.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Conference on Computer Vision and Pattern Recognition_ , pages 770–778, 2016.
  * Krizhevsky (2009) Alex Krizhevsky.  Learning multiple layers of features from tiny images, 2009.
  * Ronneberger et al. (2015) Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-Net: Convolutional networks for biomedical image segmentation.  In _International Conference on Medical image Computing and Computer-Assisted Intervention_ , pages 234–241, 2015.
  * Mounsaveng et al. (2019) Saypraseuth Mounsaveng, David Vazquez, Ismail Ben Ayed, and Marco Pedersoli.  Adversarial learning of general transformations for data augmentation.  _International Conference on Learning Representations_ , 2019.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  _Neural Computation_ , 9(8):1735–1780, 1997.
  * Marcus et al. (1993) Mitchell P Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini.  Building a large annotated corpus of English: The Penn Treebank.  _Computational Linguistics_ , 19(2):313–330, 1993.
  * Gal and Ghahramani (2016) Yarin Gal and Zoubin Ghahramani.  A theoretically grounded application of dropout in recurrent neural networks.  In _Advances in Neural Information Processing Systems_ , pages 1027–1035, 2016.
  * Kingma et al. (2015) Durk P Kingma, Tim Salimans, and Max Welling.  Variational dropout and the local reparameterization trick.  In _Advances in Neural Information Processing Systems_ , pages 2575–2583, 2015.
  * Wan et al. (2013) Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus.  Regularization of neural networks using Dropconnect.  In _International Conference on Machine Learning_ , pages 1058–1066, 2013.
  * Gal et al. (2017) Yarin Gal, Jiri Hron, and Alex Kendall.  Concrete dropout.  In _Advances in Neural Information Processing Systems_ , pages 3581–3590, 2017.
  * Goodfellow et al. (2016) Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  _Deep Learning_.  MIT Press, 2016.  http://www.deeplearningbook.org.
  * Foerster et al. (2018) Jakob Foerster, Richard Y Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch.  Learning with opponent-learning awareness.  In _International Conference on Autonomous Agents and MultiAgent Systems_ , pages 122–130, 2018.
  * Letcher et al. (2018) Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, and Shimon Whiteson.  Stable opponent shaping in differentiable games.  _arXiv preprint arXiv:1811.08469_ , 2018.
  * Lorraine et al. (2020a) Jonathan Lorraine, Paul Vicol, and David Duvenaud.  Optimizing millions of hyperparameters by implicit differentiation.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1540–1552. PMLR, 2020a.
  * Lorraine et al. (2019) Jonathan Lorraine, Paul Vicol, and David Duvenaud.  Optimizing millions of hyperparameters by implicit differentiation.  _arXiv preprint arXiv:1911.02590_ , 2019.
  * Morgenstern and Von Neumann (1953) Oskar Morgenstern and John Von Neumann.  _Theory of Games and Economic Behavior_.  Princeton University Press, 1953.
  * Von Stackelberg (2010) Heinrich Von Stackelberg.  _Market Structure and Equilibrium_.  Springer Science & Business Media, 2010.
  * Arrow et al. (1958) Kenneth Joseph Arrow, Hirofumi Azawa, Leonid Hurwicz, and Hirofumi Uzawa.  _Studies in Linear and Non-Linear Programming_ , volume 2.  Stanford University Press, 1958.
  * Freund and Schapire (1999) Yoav Freund and Robert E Schapire.  Adaptive game playing using multiplicative weights.  _Games and Economic Behavior_ , 29(1-2):79–103, 1999.
  * Gidel et al. (2019) Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Simon Lacoste-Julien, and Ioannis Mitliagkas.  Negative momentum for improved game dynamics.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 1802–1811. PMLR, 2019.
  * Lucas et al. (2018) James Lucas, Shengyang Sun, Richard Zemel, and Roger Grosse.  Aggregated momentum: Stability through passive damping.  In _International Conference on Learning Representations_ , 2018.
  * Polyak (1964) Boris T Polyak.  Some methods of speeding up the convergence of iteration methods.  _USSR Computational Mathematics and Mathematical Physics_ , 4(5):1–17, 1964.
  * Brock et al. (2018) Andrew Brock, Jeff Donahue, and Karen Simonyan.  Large scale gan training for high fidelity natural image synthesis.  In _International Conference on Learning Representations_ , 2018.
  * Osawa et al. (2019) Kazuki Osawa, Yohei Tsuji, Yuichiro Ueno, Akira Naruse, Rio Yokota, and Satoshi Matsuoka.  Large-scale distributed second-order optimization using Kronecker-factored approximate curvature for deep convolutional neural networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 12359–12367, 2019.
  * Schäfer and Anandkumar (2019) Florian Schäfer and Anima Anandkumar.  Competitive gradient descent.  In _Advances in Neural Information Processing Systems_ , pages 7623–7633, 2019.
  * Wang et al. (2019b) Yuanhao Wang, Guodong Zhang, and Jimmy Ba.  On solving minimax optimization locally: A follow-the-ridge approach.  In _International Conference on Learning Representations_ , 2019b.
  * Hemmat et al. (2020) Reyhane Askari Hemmat, Amartya Mitra, Guillaume Lajoie, and Ioannis Mitliagkas.  LEAD: Least-action dynamics for min-max optimization.  _arXiv preprint arXiv:2010.13846_ , 2020.
  * Schäfer et al. (2020) Florian Schäfer, Anima Anandkumar, and Houman Owhadi.  Competitive mirror descent.  _arXiv preprint arXiv:2006.10179_ , 2020.
  * Czarnecki et al. (2020) Wojciech Marian Czarnecki, Gauthier Gidel, Brendan Tracey, Karl Tuyls, Shayegan Omidshafiei, David Balduzzi, and Max Jaderberg.  Real world games look like spinning tops.  _arXiv preprint arXiv:2004.09468_ , 2020.
  * Zhang et al. (2020a) Guojun Zhang, Kaiwen Wu, Pascal Poupart, and Yaoliang Yu.  Newton-type methods for minimax optimization.  _arXiv preprint arXiv:2006.14592_ , 2020a.
  * Korpelevich (1976) GM Korpelevich.  The extragradient method for finding saddle points and other problems.  _Matecon_ , 12:747–756, 1976.
  * Harris et al. (2020a) Charles R Harris, K Jarrod Millman, Stéfan J van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J Smith, et al.  Array programming with numpy.  _Nature_ , 585(7825):357–362, 2020a.
  * Bertsekas (2008) D Bertsekas.  _Nonlinear Programming_.  Athena Scientific, 2008.
  * O’donoghue and Candes (2015) Brendan O’donoghue and Emmanuel Candes.  Adaptive restart for accelerated gradient schemes.  _Foundations of computational mathematics_ , 15(3):715–732, 2015.
  * Mescheder et al. (2018) Lars Mescheder, Andreas Geiger, and Sebastian Nowozin.  Which training methods for gans do actually converge?  In _International Conference on Machine learning (ICML)_ , pages 3481–3490. PMLR, 2018.
  * Goh (2017) Gabriel Goh.  Why momentum really works.  _Distill_ , 2(4):e6, 2017.
  * Azizian et al. (2020a) Waïss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel.  A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2863–2873. PMLR, 2020a.
  * Bradbury et al. (2018) James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, et al.  Jax: composable transformations of python+ numpy programs, 2018.
  * Paszke et al. (2017) Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer.  Automatic differentiation in PyTorch, 2017.
  * Chiang et al. (2012) Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu.  Online optimization with gradual variations.  In _Conference on Learning Theory_ , pages 6–1. JMLR Workshop and Conference Proceedings, 2012.
  * Rakhlin and Sridharan (2013) Alexander Rakhlin and Karthik Sridharan.  Optimization, learning, and games with predictable sequences.  In _Proceedings of the 26th International Conference on Neural Information Processing Systems_ , pages 3066–3074, 2013.
  * Daskalakis et al. (2018) Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng.  Training GANs with Optimism.  In _International Conference on Learning Representations (ICLR 2018)_ , 2018.
  * Wu et al. (2019) Yan Wu, Jeff Donahue, David Balduzzi, Karen Simonyan, and Timothy Lillicrap.  Logan: Latent optimisation for generative adversarial networks.  _arXiv preprint arXiv:1912.00953_ , 2019.
  * Nesterov (1983) Yurii E Nesterov.  A method for solving the convex programming problem with convergence rate o (1/k^ 2).  In _Dokl. Akad. Nauk SSSR_ , volume 269, pages 543–547, 1983.
  * Nesterov (2013) Yurii Nesterov.  _Introductory lectures on convex optimization: A basic course_ , volume 87.  Springer Science & Business Media, 2013.
  * Maddison et al. (2018) Chris J Maddison, Daniel Paulin, Yee Whye Teh, Brendan O’Donoghue, and Arnaud Doucet.  Hamiltonian descent methods.  _arXiv preprint arXiv:1809.05042_ , 2018.
  * Sutskever et al. (2013) Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton.  On the importance of initialization and momentum in deep learning.  In _International Conference on Machine Learning_ , pages 1139–1147, 2013.
  * Zhang and Mitliagkas (2017) Jian Zhang and Ioannis Mitliagkas.  Yellowfin and the art of momentum tuning.  _arXiv preprint arXiv:1706.03471_ , 2017.
  * Choi et al. (2019) Dami Choi, Christopher J Shallue, Zachary Nado, Jaehoon Lee, Chris J Maddison, and George E Dahl.  On empirical comparisons of optimizers for deep learning.  _arXiv preprint arXiv:1910.05446_ , 2019.
  * Zhang et al. (2019b) Michael R Zhang, James Lucas, Geoffrey Hinton, and Jimmy Ba.  Lookahead optimizer: k steps forward, 1 step back.  _arXiv preprint arXiv:1907.08610_ , 2019b.
  * Chen et al. (2020) Ricky TQ Chen, Dami Choi, Lukas Balles, David Duvenaud, and Philipp Hennig.  Self-tuning stochastic optimization with curvature-aware gradient filtering.  _arXiv preprint arXiv:2011.04803_ , 2020.
  * Letcher et al. (2019) Alistair Letcher, David Balduzzi, Sébastien Racaniere, James Martens, Jakob N Foerster, Karl Tuyls, and Thore Graepel.  Differentiable game mechanics.  _Journal of Machine Learning Research_ , 20(84):1–40, 2019.
  * Nagarajan et al. (2020) Sai Ganesh Nagarajan, David Balduzzi, and Georgios Piliouras.  From chaos to order: Symmetry and conservation laws in game dynamics.  In _International Conference on Machine Learning_ , pages 7186–7196. PMLR, 2020.
  * Omidshafiei et al. (2020) Shayegan Omidshafiei, Karl Tuyls, Wojciech M Czarnecki, Francisco C Santos, Mark Rowland, Jerome Connor, Daniel Hennes, Paul Muller, Julien Pérolat, Bart De Vylder, et al.  Navigating the landscape of multiplayer games.  _Nature Communications_ , 11(1):1–17, 2020.
  * Gidel et al. (2020) Gauthier Gidel, David Balduzzi, Wojciech Marian Czarnecki, Marta Garnelo, and Yoram Bachrach.  Minimax theorem for latent games or: How I learned to stop worrying about mixed-Nash and love neural nets.  _arXiv preprint arXiv:2002.05820_ , 2020.
  * Perolat et al. (2020) Julien Perolat, Remi Munos, Jean-Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, et al.  From poincar$\backslash$’e recurrence to convergence in imperfect information games: Finding equilibrium via regularization.  _arXiv preprint arXiv:2002.08456_ , 2020.
  * Zhang et al. (2021a) Guodong Zhang, Yuanhao Wang, Laurent Lessard, and Roger Grosse.  Don’t fix what ain’t broke: Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization.  _arXiv preprint arXiv:2102.09468_ , 2021a.
  * Zhang et al. (2020b) Guodong Zhang, Xuchao Bao, Laurent Lessard, and Roger Grosse.  A unified analysis of first-order methods for smooth games via integral quadratic constraints.  _arXiv preprint arXiv:2009.11359_ , 2020b.
  * Ibrahim et al. (2020) Adam Ibrahim, Waıss Azizian, Gauthier Gidel, and Ioannis Mitliagkas.  Linear lower bounds and conditioning of differentiable games.  In _International Conference on Machine Learning_ , pages 4583–4593. PMLR, 2020.
  * Bailey et al. (2020) James P Bailey, Gauthier Gidel, and Georgios Piliouras.  Finite regret and cycles with fixed step-size via alternating gradient descent-ascent.  In _Conference on Learning Theory_ , pages 391–407. PMLR, 2020.
  * Jin et al. (2020) Chi Jin, Praneeth Netrapalli, and Michael Jordan.  What is local optimality in nonconvex-nonconcave minimax optimization?  In _International Conference on Machine Learning_ , pages 4880–4889. PMLR, 2020.
  * Nouiehed et al. (2019) Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn.  Solving a class of non-convex min-max games using iterative first order methods.  _Advances in Neural Information Processing Systems_ , 32:14934–14942, 2019.
  * Zhang et al. (2020c) Guojun Zhang, Pascal Poupart, and Yaoliang Yu.  Optimality and stability in non-convex smooth games.  _arXiv e-prints_ , pages arXiv–2002, 2020c.
  * Zhang (2023) Guodong Zhang.  _Deep Learning Dynamics: From Minimization to Games_.  PhD thesis, University of Toronto (Canada), 2023.
  * Zhang and Wang (2020) Guodong Zhang and Yuanhao Wang.  On the suboptimality of negative momentum for minimax optimization.  _arXiv preprint arXiv:2008.07459_ , 2020.
  * Azizian et al. (2020b) Waïss Azizian, Damien Scieur, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel.  Accelerating smooth games by manipulating spectral shapes.  _arXiv preprint arXiv:2001.00602_ , 2020b.
  * Domingo-Enrich et al. (2020) Carles Domingo-Enrich, Fabian Pedregosa, and Damien Scieur.  Average-case acceleration for bilinear games and normal matrices.  _arXiv preprint arXiv:2010.02076_ , 2020.
  * Zhang and Yu (2019) Guojun Zhang and Yaoliang Yu.  Convergence of gradient methods on bilinear zero-sum games.  In _International Conference on Learning Representations_ , 2019.
  * Loizou et al. (2020) Nicolas Loizou, Hugo Berard, Alexia Jolicoeur-Martineau, Pascal Vincent, Simon Lacoste-Julien, and Ioannis Mitliagkas.  Stochastic Hamiltonian gradient methods for smooth games.  In _International Conference on Machine Learning_ , pages 6370–6381. PMLR, 2020.
  * Liu et al. (2020) Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang.  Towards better understanding of adaptive gradient algorithms in generative adversarial nets.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=SJxIm0VtwH.
  * Peng et al. (2020) Wei Peng, Yu-Hong Dai, Hui Zhang, and Lizhi Cheng.  Training GANs with centripetal acceleration.  _Optimization Methods and Software_ , 35(5):955–973, 2020.
  * Albuquerque et al. (2019) Isabela Albuquerque, João Monteiro, Thang Doan, Breandan Considine, Tiago Falk, and Ioannis Mitliagkas.  Multi-objective training of generative adversarial networks with multiple discriminators.  In _International Conference on Machine Learning_ , pages 202–211. PMLR, 2019.
  * Hsieh et al. (2019) Ya-Ping Hsieh, Chen Liu, and Volkan Cevher.  Finding mixed Nash equilibria of generative adversarial networks.  In _International Conference on Machine Learning_ , pages 2810–2819. PMLR, 2019.
  * Metz et al. (2016) Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein.  Unrolled generative adversarial networks.  _arXiv preprint arXiv:1611.02163_ , 2016.
  * Qin et al. (2020) Chongli Qin, Yan Wu, Jost Tobias Springenberg, Andrew Brock, Jeff Donahue, Timothy P Lillicrap, and Pushmeet Kohli.  Training generative adversarial networks by solving ordinary differential equations.  _arXiv preprint arXiv:2010.15040_ , 2020.
  * Schäfer et al. (2019) Florian Schäfer, Hongkai Zheng, and Anima Anandkumar.  Implicit competitive regularization in GANs.  _arXiv preprint arXiv:1910.05852_ , 2019.
  * Jolicoeur-Martineau and Mitliagkas (2019) Alexia Jolicoeur-Martineau and Ioannis Mitliagkas.  Connections between support vector machines, Wasserstein distance and gradient-penalty GANs.  _arXiv preprint arXiv:1910.06922_ , 2019.
  * Gidel et al. (2018) Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien.  A variational inequality perspective on generative adversarial networks.  In _International Conference on Learning Representations_ , 2018.
  * Chavdarova et al. (2019) Tatjana Chavdarova, Gauthier Gidel, Francois Fleuret, and Simon Lacoste-Julien.  Reducing noise in GAN training with variance reduced extragradient.  In _Proceedings of the International Conference on Neural Information Processing Systems_ , 2019.
  * Lorraine et al. (2021a) Jonathan Lorraine, David Acuna, Paul Vicol, and David Duvenaud.  Complex momentum for learning in games.  _arXiv preprint arXiv:2102.08431_ , 2021a.
  * Geirhos et al. (2018) Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Matthias Bethge, Felix A Wichmann, and Wieland Brendel.  Imagenet-trained cnns are biased towards texture; increasing shape bias improves accuracy and robustness.  In _ICLR_ , 2018.
  * Geirhos et al. (2020) Robert Geirhos, Jörn-Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann.  Shortcut learning in deep neural networks.  _Nature Machine Intelligence_ , 2(11):665–673, 2020.
  * Cully et al. (2015) Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean-Baptiste Mouret.  Robots that can adapt like animals.  _Nature_ , 521(7553):503–507, 2015.
  * Song et al. (2020) Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-based generative modeling through stochastic differential equations.  In _ICLR_ , 2020.
  * Bengio et al. (2009) Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston.  Curriculum learning.  In _International Conference on Machine Learning_ , pages 41–48. ACM, 2009.
  * Lorraine et al. (2020b) Jonathan Lorraine, Paul Vicol, and David Duvenaud.  Optimizing millions of hyperparameters by implicit differentiation.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , pages 1540–1552, 2020b.
  * Bacon et al. (2019) Pierre-Luc Bacon, Florian Schäfer, Clement Gehring, Animashree Anandkumar, and Emma Brunskill.  A Lagrangian method for inverse problems in reinforcement learning.  _lis.csail.mit.edu/pubs_ , 2019.
  * Zoph and Le (2016) Barret Zoph and Quoc V Le.  Neural architecture search with reinforcement learning.  _arXiv preprint arXiv:1611.01578_ , 2016.
  * Real et al. (2019) Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le.  Regularized evolution for image classifier architecture search.  In _AAAI Conference on Artificial Intelligence_ , volume 33, pages 4780–4789, 2019.
  * Grathwohl et al. (2018) Will Grathwohl, Elliot Creager, Seyed Kamyar Seyed Ghasemipour, and Richard Zemel.  Gradient-based optimization of neural network architecture, 2018.
  * Arjovsky et al. (2017) Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In _International Conference on Machine Learning (ICML)_ , pages 214–223, 2017.
  * Hu et al. (2020) Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster.  “Other-Play” for zero-shot coordination.  In _International Conference on Machine Learning (ICML)_ , pages 4399–4410, 2020.
  * Parker-Holder et al. (2020a) Jack Parker-Holder, Luke Metz, Cinjon Resnick, Hengyuan Hu, Adam Lerer, Alistair Letcher, Alexander Peysakhovich, Aldo Pacchiano, and Jakob Foerster.  Ridge Rider: Finding diverse solutions by following eigenvectors of the Hessian.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 753–765, 2020a.
  * Katok and Hasselblatt (1997) Anatole Katok and Boris Hasselblatt.  _Introduction to the Modern Theory of Dynamical Systems_.  Cambridge University Press, 1997.
  * Abadi et al. (2015) Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015.  URL https://www.tensorflow.org/.
  * Hale and Koçak (2012) Jack K Hale and Hüseyin Koçak.  _Dynamics and Bifurcations_ , volume 3.  Springer Science & Business Media, 2012.
  * Tabor (1989) Michael Tabor.  _Chaos and Integrability in Nonlinear Dynamics: An Introduction_.  Wiley-Interscience, 1989.
  * Wolff (1992) Rodney CL Wolff.  Local Lyapunov exponents: Looking closely at chaos.  _Journal of the Royal Statistical Society_ , 1992.
  * Loreto et al. (1996) Vittorio Loreto, Giovanni Paladin, Michele Pasquini, and Angelo Vulpiani.  Characterization of chaos in random maps.  _Physica A: Statistical Mechanics and its Applications_ , 232(1-2):189–200, 1996.
  * Kachman et al. (2017) Tal Kachman, Shmuel Fishman, and Avy Soffer.  Numerical implementation of the multiscale and averaging methods for quasi periodic systems.  _Computer Physics Communications_ , 221:235–245, 2017.
  * Pesin (1977) Yakov Borisovich Pesin.  Characteristic Lyapunov exponents and smooth ergodic theory.  _Uspekhi Matematicheskikh Nauk_ , 1977.
  * Yao et al. (2020) Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W Mahoney.  PyHessian: Neural networks through the lens of the Hessian.  In _IEEE International Conference on Big Data (Big Data)_ , pages 581–590, 2020.
  * Poundstone (1993) William Poundstone.  _Prisoner’s Dilemma/John Von Neumann, Game Theory and the Puzzle of the Bomb_.  Anchor Press, 1993.
  * Strogatz (2018) Steven H Strogatz.  _Nonlinear Dynamics and Chaos with Student Solutions Manual: With Applications to Physics, Biology, Chemistry, and Engineering_.  CRC Press, 2018.
  * Van Rossum and Drake Jr (1995) Guido Van Rossum and Fred L Drake Jr.  _Python reference manual_.  Centrum voor Wiskunde en Informatica Amsterdam, 1995.
  * Oliphant (2007) Travis E Oliphant.  Python for scientific computing.  _Computing in Science & Engineering_, 9(3):10–20, 2007.
  * Oliphant (2006) Travis E Oliphant.  _A guide to NumPy_ , volume 1.  Trelgol Publishing USA, 2006.
  * Van Der Walt et al. (2011) Stefan Van Der Walt, S Chris Colbert, and Gael Varoquaux.  The NumPy array: A structure for efficient numerical computation.  _Computing in Science & Engineering_, 13(2):22–30, 2011.
  * Harris et al. (2020b) Charles R Harris, K Jarrod Millman, Stéfan J van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J Smith, et al.  Array programming with NumPy.  _Nature_ , 585(7825):357–362, 2020b.
  * Hunter (2007) John D Hunter.  Matplotlib: A 2D graphics environment.  _Computing in Science & Engineering_, 9(3):90–95, 2007.
  * Jones et al. (2001) Eric Jones, Travis Oliphant, Pearu Peterson, et al.  SciPy: Open source scientific tools for Python, 2001.
  * Lorraine (2024) Jonathan Lorraine.  _Scalable Nested Optimization for Deep Learning_.  PhD thesis, University of Toronto (Canada), 2024.
  * Mockus (1998) Jonas Mockus.  The application of bayesian methods for seeking the extremum.  _Towards global optimization_ , 2:117, 1998.
  * Shahriari et al. (2015) Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas.  Taking the human out of the loop: A review of bayesian optimization.  _Proceedings of the IEEE_ , 104(1):148–175, 2015.
  * Ginsbourger et al. (2010) David Ginsbourger, Rodolphe Le Riche, and Laurent Carraro.  Kriging is well-suited to parallelize optimization.  In _Computational intelligence in expensive optimization problems_ , pages 131–162. Springer, 2010.
  * Lam et al. (2016) Remi Lam, Karen Willcox, and David H Wolpert.  Bayesian optimization with a finite budget: An approximate dynamic programming approach.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Swersky et al. (2013) Kevin Swersky, Jasper Snoek, and Ryan P Adams.  Multi-task bayesian optimization.  _Advances in neural information processing systems_ , 26, 2013.
  * Golovin et al. (2017) Daniel Golovin, Benjamin Solnik, Subhodeep Moitra, Greg Kochanski, John Karro, and David Sculley.  Google vizier: A service for black-box optimization.  In _Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining_ , pages 1487–1495, 2017.
  * Klein et al. (2017) Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter.  Fast bayesian optimization of machine learning hyperparameters on large datasets.  In _Artificial intelligence and statistics_ , pages 528–536. PMLR, 2017.
  * Li et al. (2017) Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar.  Hyperband: A novel bandit-based approach to hyperparameter optimization.  _The journal of machine learning research_ , 18(1):6765–6816, 2017.
  * Daulton et al. (2022) Samuel Daulton, David Eriksson, Maximilian Balandat, and Eytan Bakshy.  Multi-objective bayesian optimization over high-dimensional search spaces.  In _Uncertainty in Artificial Intelligence_ , pages 507–517. PMLR, 2022.
  * Hinton et al. (2012) Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky.  Neural networks for machine learning. Lecture 6a. Overview of mini-batch gradient descent, 2012.
  * Merity et al. (2018) Stephen Merity, Nitish Shirish Keskar, and Richard Socher.  Regularizing and optimizing LSTM language models.  _International Conference on Learning Representations_ , 2018.
  * Salimans et al. (2016) Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen.  Improved techniques for training GANs.  In _Advances in Neural Information Processing Systems_ , pages 2234–2242, 2016.
  * Foucart (2012) Simon Foucart.  Matrix norm and spectral radius.  https://www.math.drexel.edu/~foucart/TeachingFiles/F12/M504Lect6.pdf, 2012.  Accessed: 2020-05-21.
  * Boyd et al. (2004) Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe.  _Convex Optimization_.  Cambridge university press, 2004.
  * Hahnloser et al. (2000) Richard HR Hahnloser, Rahul Sarpeshkar, Misha A Mahowald, Rodney J Douglas, and H Sebastian Seung.  Digital selection and analogue amplification coexist in a cortex-inspired silicon circuit.  _Nature_ , 405(6789):947–951, 2000.
  * Lorraine et al. (2022b) Jonathan Lorraine, Paul Vicol, Jack Parker-Holder, Tal Kachman, Luke Metz, and Jakob Foerster.  Lyapunov exponents for diversity in differentiable games.  In _Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems_ , pages 842–852, 2022b.
  * Lorraine et al. (2021b) Jonathan Lorraine, Jack Parker-Holder, Paul Vicol, Aldo Pacchiano, Luke Metz, Tal Kachman, and Jakob Foerster.  Using bifurcations for diversity in differentiable games.  In _ICML 2021 Beyond First Order Methods Workshop_ , 2021b.
  * Lorraine et al. (2021c) Jonathan Lorraine, Paul Vicol, Jack Parker-Holder, Tal Kachman, Luke Metz, and Jakob Foerster.  Lyapunov exponents for diversity in differentiable games.  _arXiv preprint arXiv:2112.14570_ , 2021c.
  * Hansen and Salamon (1990) Lars Kai Hansen and Peter Salamon.  Neural network ensembles.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 1990.
  * Liu and Yao (1999) Yong Liu and Xin Yao.  Ensemble learning via negative correlation.  _Neural Networks_ , 12(10):1399 – 1404, 1999.
  * Sinha et al. (2021) Samarth Sinha, Homanga Bharadhwaj, Anirudh Goyal, Hugo Larochelle, Animesh Garg, and Florian Shkurti.  Diversity inducing information bottleneck in model ensembles.  _AAAI_ , 2021.
  * Ross et al. (2020) Andrew Slavin Ross, Weiwei Pan, Leo A. Celi, and Finale Doshi-Velez.  Ensembles of locally independent prediction models.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI_ , 2020.
  * Mariet and Sra (2016) Zelda Mariet and Suvrit Sra.  Diversity networks: Neural network compression using determinantal point processes.  In _International Conference on Learning Representations (ICLR)_ , May 2016.
  * Pang et al. (2019) Tianyu Pang, Kun Xu, Chao Du, Ning Chen, and Jun Zhu.  Improving adversarial robustness via promoting ensemble diversity.  In _International Conference on Machine Learning (ICML)_ , 2019.
  * Lehman and Stanley (2008) Joel Lehman and Kenneth O. Stanley.  Exploiting open-endedness to solve problems through the search for novelty.  In _Proceedings of the Eleventh International Conference on Artificial Life (Alife XI)_. MIT Press, 2008.
  * Eysenbach et al. (2019) Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine.  Diversity is all you need: Learning skills without a reward function.  In _International Conference on Learning Representations (ICLR)_ , 2019.
  * Parker-Holder et al. (2020b) Jack Parker-Holder, Aldo Pacchiano, Krzysztof M Choromanski, and Stephen J Roberts.  Effective diversity in population based reinforcement learning.  _Advances in Neural Information Processing Systems_ , 33:18050–18062, 2020b.
  * Pugh et al. (2016) Justin K. Pugh, Lisa B. Soros, and Kenneth O. Stanley.  Quality diversity: A new frontier for evolutionary computation.  _Frontiers in Robotics and AI_ , 3:40, 2016.
  * Zhang et al. (2021b) Guodong Zhang, Xuchan Bao, Laurent Lessard, and Roger Grosse.  A unified analysis of first-order methods for smooth games via integral quadratic constraints.  _Journal of Machine Learning Research_ , 22(103):1–39, 2021b.
  * Zhang et al. (2022) Guodong Zhang, Yuanhao Wang, Laurent Lessard, and Roger B Grosse.  Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 7659–7679. PMLR, 2022.
  * Azizian et al. (2020c) Waïss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel.  A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2020c.
  * Zhang and Wang (2021) Guodong Zhang and Yuanhao Wang.  On the suboptimality of negative momentum for minimax optimization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2098–2106. PMLR, 2021.
  * Lorraine et al. (2022c) Jonathan P Lorraine, David Acuna, Paul Vicol, and David Duvenaud.  Complex momentum for optimization in games.  In _International Conference on Artificial Intelligence and Statistics_ , pages 7742–7765. PMLR, 2022c.
  * Mazumdar et al. (2019) Eric V Mazumdar, Michael I Jordan, and S Shankar Sastry.  On finding local Nash equilibria (and only local Nash equilibria) in zero-sum games.  _arXiv preprint arXiv:1901.00838_ , 2019.
  * Garnelo et al. (2021) Marta Garnelo, Wojciech Marian Czarnecki, Siqi Liu, Dhruva Tirumala, Junhyuk Oh, Gauthier Gidel, Hado van Hasselt, and David Balduzzi.  Pick your battles: Interaction graphs as population-level objectives for strategic diversity.  In _Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems (AAMA)_ , pages 1501–1503, 2021.
  * Vinyals et al. (2019) Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al.  Grandmaster level in StarCraft II using multi-agent reinforcement learning.  _Nature_ , 575, 2019.
  * Yang et al. (2020) Yaodong Yang, Ying Wen, Jun Wang, Liheng Chen, Kun Shao, David Mguni, and Weinan Zhang.  Multi-agent determinantal q-learning.  In _International Conference on Machine Learning (ICML)_ , 2020.
  * Lupu et al. (2021) Andrei Lupu, Hengyuan Hu, and Jakob Foerster.  Trajectory diversity for zero-shot coordination.  In _Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems_ , 2021.
  * Hart et al. (1968) Peter Hart, Nils Nilsson, and Bertram Raphael.  A formal basis for the heuristic determination of minimum cost paths.  _IEEE Transactions on Systems Science and Cybernetics_ , 4(2):100–107, 1968.
  * Abramson (2014) Bruce Abramson.  _The Expected-Outcome Model of Two-Player Games_.  Morgan Kaufmann, 2014.
  * Silver et al. (2016) David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of Go with deep neural networks and tree search.  _Nature_ , 2016.
  * Moerland et al. (2018) Thomas M Moerland, Joost Broekens, Aske Plaat, and Catholijn M Jonker.  A0c: Alpha zero in continuous action space.  _arXiv preprint arXiv:1805.09613_ , 2018.
  * Kim et al. (2020) Beomjoon Kim, Kyungjae Lee, Sungbin Lim, Leslie Kaelbling, and Tomás Lozano-Pérez.  Monte Carlo tree search in continuous spaces using Voronoi optimistic optimization with regret bounds.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2020.
  * Mao et al. (2020) Weichao Mao, Kaiqing Zhang, Qiaomin Xie, and Tamer Basar.  Poly-hoot: Monte-carlo planning in continuous space mdps with non-asymptotic analysis.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * LaValle et al. (1998) Steven M LaValle et al.  Rapidly-exploring random trees: A new tool for path planning.  _Technical Report, Iowa State University, USA_ , 1998.
  * LaValle and Kuffner Jr (2001) Steven M LaValle and James J Kuffner Jr.  Randomized kinodynamic planning.  _The International Journal of Robotics Research_ , 2001.
  * Rodriguez et al. (2006) Samuel Rodriguez, Xinyu Tang, Jyh-Ming Lien, and Nancy M Amato.  An obstacle-based rapidly-exploring random tree.  In _IEEE International Conference on Robotics and Automation (ICRA)_ , 2006.
  * Singh and Deb (2006) Gulshan Singh and Kalyanmoy Deb.  Comparison of multi-modal optimization algorithms based on evolutionary algorithms.  In _Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation_ , pages 1305–1312, 2006.
  * Wong (2015) Ka-Chun Wong.  Evolutionary multimodal optimization: A short survey, 2015.
  * Arulkumaran et al. (2019) Kai Arulkumaran, Antoine Cully, and Julian Togelius.  Alphastar: An evolutionary computation perspective.  In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2019.
  * Zeeman (1980) E Christopher Zeeman.  Population dynamics from game theory.  In _Global Theory of Dynamical Systems_ , pages 471–497. Springer, 1980.
  * Yang et al. (2018) Ger Yang, David Basanta, and Georgios Piliouras.  Bifurcation mechanism design—from optimal flat taxes to better cancer treatments.  _Games_ , 9(2):21, 2018.
  * Chotibut et al. (2020) Thiparat Chotibut, Fryderyk Falniowski, Michał Misiurewicz, and Georgios Piliouras.  The route to chaos in routing games: When is price of anarchy too optimistic?  _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Piliouras (2020) Georgios Piliouras.  Catastrophe by design in population games: Destabilizing wasteful locked-in technologies.  In _Web and Internet Economics: 16th International Conference (WINE)_ , page 473, 2020.
  * Leonardos and Piliouras (2020) Stefanos Leonardos and Georgios Piliouras.  Exploration-exploitation in multi-agent learning: Catastrophe theory meets game theory.  _arXiv preprint arXiv:2012.03083_ , 2020.
  * Bielawski et al. (2021) Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski, Grzegorz Kosiorowski, Michał Misiurewicz, and Georgios Piliouras.  Follow-the-regularized-leader routes to chaos in routing games.  _arXiv preprint arXiv:2102.07974_ , 2021.
  * Cheung and Piliouras (2019) Yun Kuen Cheung and Georgios Piliouras.  Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games.  In _Conference on Learning Theory_ , 2019.
  * Cheung and Tao (2020) Yun Kuen Cheung and Yixin Tao.  Chaos of learning beyond zero-sum and coordination via game decompositions.  In _International Conference on Learning Representations (ICLR)_ , 2020.
  * Sato et al. (2002) Yuzuru Sato, Eizo Akiyama, and J Doyne Farmer.  Chaos in learning a simple two-person game.  _Proceedings of the National Academy of Sciences_ , 99(7):4748–4751, 2002.
  * Panageas and Piliouras (2016) Ioannis Panageas and Georgios Piliouras.  Average case performance of replicator dynamics in potential games via computing regions of attraction.  In _Proceedings of the 2016 ACM Conference on Economics and Computation_ , pages 703–720, 2016.
  * Zhang and Hofbauer (2015) Boyu Zhang and Josef Hofbauer.  Equilibrium selection via replicator dynamics in 2x2 coordination games.  _International Journal of Game Theory_ , 44(2):433–448, 2015.