# Existence and Estimation of Critical Batch Size for Training Generative
Adversarial Networks with Two Time-Scale Update Rule

Naoki Sato  Hideaki Iiduka

###### Abstract

Previous results have shown that a two time-scale update rule (TTUR) using
different learning rates, such as different constant rates or different
decaying rates, is useful for training generative adversarial networks (GANs)
in theory and in practice. Moreover, not only the learning rate but also the
batch size is important for training GANs with TTURs and they both affect the
number of steps needed for training. This paper studies the relationship
between batch size and the number of steps needed for training GANs with TTURs
based on constant learning rates. We theoretically show that, for a TTUR with
constant learning rates, the number of steps needed to find stationary points
of the loss functions of both the discriminator and generator decreases as the
batch size increases and that there exists a critical batch size minimizing
the stochastic first-order oracle (SFO) complexity. Then, we use the Fréchet
inception distance (FID) as the performance measure for training and provide
numerical results indicating that the number of steps needed to achieve a low
FID score decreases as the batch size increases and that the SFO complexity
increases once the batch size exceeds the measured critical batch size.
Moreover, we show that measured critical batch sizes are close to the sizes
estimated from our theoretical results.

adaptive method, batch size, critical batch size, GANs, non-convex
optimization

##  1 Introduction

###  1.1 Background

Generative adversarial networks (GANs) have attracted attention (see, e.g.,
(Thekumparampil et al., 2019; Jordon et al., 2019; Xu et al., 2020; Zhu et
al., 2021)) with the development of real-world applications (Arjovsky et al.,
2017; Gulrajani et al., 2017; Brock et al., 2019; Zhang & Khoreva, 2019). The
generator network in a GAN constructs synthetic data from random variables,
and the discriminator network separates the synthetic data from the real-world
data.

Many optimizers have been presented for training GANs (see, e.g., (Goodfellow
et al., 2014; Nagarajan & Kolter, 2017; Heusel et al., 2017; Chavdarova et
al., 2019; Xu et al., 2020; Sauer et al., 2021)). In this paper, we focus on a
two time scale update rule (TTUR) (Heusel et al., 2017) for finding a pair of
stationary points of the loss functions of the discriminator and generator.
TTUR uses sequences generated by each of the generator and the discriminator.

For example, let us consider a TTUR based on stochastic gradient descent (SGD)
(Fehrman et al., 2020; Scaman & Malherbe, 2020; Chen et al., 2020); let
$\bm{\theta}_{n}$ be the point generated by the generator at iteration $n$ and
$\bm{w}_{n}$ be the point generated by the discriminator at iteration $n$. The
loss function of the generator $L_{G}(\cdot,\bm{w}_{n})$ is minimized by using
SGD with a learning rate $\alpha_{n}^{G}$ and a mini-batch stochastic gradient
at $\bm{\theta}_{n}$ with a batch of size $b$. The loss function of the
discriminator $L_{D}(\bm{\theta}_{n},\cdot)$ is minimized with a learning rate
$\alpha_{n}^{D}$ and a mini-batch stochastic gradient at $\bm{w}_{n}$ with the
same batch size $b$. If $\alpha_{n}^{G}$ and $\alpha_{n}^{D}$ are decaying
learning rates, then TTUR based on SGD converges almost surely to a pair of
stationary points of $L_{G}$ and $L_{D}$ (Heusel et al., 2017, Theorem 1).

TTURs based on adaptive methods can be defined by replacing SGD with adaptive
methods for training deep neural networks. For example, TTUR based on adaptive
moment estimation (Adam) (Kingma & Ba, 2015) with decaying learning rates
$\alpha_{n}^{G}$ and $\alpha_{n}^{D}$ converges almost surely to a pair of
stationary points of the loss functions of the generator and the discriminator
(Heusel et al., 2017, Theorem 2). It was shown numerically that TTUR based on
AdaBelief (short for adapting step sizes by the belief in observed gradients)
(Zhuang et al., 2020) with constant learning rates $\alpha^{G}$ and
$\alpha^{D}$ has good scores in terms of the Fréchet inception distance (FID)
(Heusel et al., 2017), which is a performance measure of optimizers for
training GANs. This implies that TTUR based on AdaBelief is a powerful way to
train GANs.

###  1.2 Motivation

The above subsection described that TTUR with decaying or constant learning
rates can be used in both theory and practice to train GANs. In particular,
the numerical results in (Heusel et al., 2017; Zhuang et al., 2020) show that
TTUR performs well with constant learning rates. Hence, we will set constant
learning rates $\alpha^{G}$ and $\alpha^{D}$ for the generator and the
discriminator.

Meanwhile, the batch size also affects the performance of TTUR. Previous
numerical evaluations (Heusel et al., 2017, Figure 5) have indicated that
increasing the batch size used in TTUR tends to decrease the FID. This implies
that large batch sizes are desirable for training GANs. The motivation behind
this work is thus to identify the theoretical relationship between the
performance of TTUR with constant learning rates and the batch size. In so
doing, we may bridge the gap between theory and practice in regard to the
performance of TTUR based on the batch size.

We will use the number of steps $N$ needed to train the GAN as the performance
metric and examine the relationship between the batch size $b$ and number of
steps $N$. Motivated by the previously reported results (Heusel et al., 2017),
we tried to find a pair of stationary points of the loss functions of the
discriminator and generator that satisfy the variational inequalities (1) of
the gradients of both loss functions.

Previous results (Shallue et al., 2019; Zhang et al., 2019; Iiduka, 2022b;
Goyal et al., 2017; Hoffer et al., 2017; You et al., 2017) on training deep
neural networks in practical tasks have shown that, for each deep learning
optimizer, the number of training steps is halved by each doubling of the
batch size and that diminishing returns exist beyond a critical batch size. On
the other hand, we are interested in verifying whether a critical batch size
for GANs exists in theory and in practice.

###  1.3 Contribution

####  1.3.1 Theoretical result on TTUR with small constant learning rates and
large batch sizes

The theoretical contribution of this paper is to show that, for TTURs with
constant learning rates, the number of steps $N$ needed to find a pair of
stationary points of the loss functions of the discriminator and the generator
decreases as the batch size $b$ increases (see also (3) for the explicit forms
of $N$). To show this, we need to clarify that TTUR with constant learning
rates can approximate a pair $(\bm{\theta}^{\star},\bm{w}^{\star})$ of
stationary points of the loss function $L_{D}(\bm{\theta}^{\star},\cdot)$ of
the discriminator and the loss function $L_{G}(\cdot,\bm{w}^{\star})$ of the
generator.

We define the inner product of $\bm{x},\bm{y}\in\mathbb{R}^{d}$ by
$\langle\bm{x},\bm{y}\rangle:=\bm{x}^{\top}\bm{y}$ and the norm of
$\bm{x}\in\mathbb{R}^{d}$ by $\|\bm{x}\|:=\sqrt{\langle\bm{x},\bm{x}\rangle}$.
Let $\nabla_{\bm{\theta}}L_{G}(\cdot,\bm{w})$ be the gradient of
$L_{G}(\cdot,\bm{w})$ ($\bm{w}\in\mathbb{R}^{W}$) and
$\nabla_{\bm{w}}L_{D}(\bm{\theta},\cdot)$ be the gradient of
$L_{D}(\bm{\theta},\cdot)$ ($\bm{\theta}\in\mathbb{R}^{\Theta}$). A pair
$(\bm{\theta}^{\star},\bm{w}^{\star})$ of stationary points of
$L_{D}(\bm{\theta}^{\star},\cdot)$ and $L_{G}(\cdot,\bm{w}^{\star})$ is such
that

$\displaystyle\|\nabla_{\bm{\theta}}L_{G}(\bm{\theta}^{\star},\bm{w}^{\star})\|=0\text{
and }\|\nabla_{\bm{w}}L_{D}(\bm{\theta}^{\star},\bm{w}^{\star})\|=0,$

which are equivalent to the following variational inequalities (see Appendix
A.11): for all $\bm{\theta}\in\mathbb{R}^{\Theta}$ and all
$\bm{w}\in\mathbb{R}^{W}$,

$\displaystyle\begin{split}&\langle\bm{\theta}^{\star}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}^{\star},\bm{w}^{\star})\rangle\leq
0\text{ and }\\\
&\langle\bm{w}^{\star}-\bm{w},\nabla_{\bm{w}}L_{D}(\bm{\theta}^{\star},\bm{w}^{\star})\rangle\leq
0.\end{split}$ (1)

Let us examine TTURs based on adaptive methods (see Algorithm 1 and Table 4 in
Appendix A.1) such as Adam (Kingma & Ba, 2015), AdaBelief (Zhuang et al.,
2020), and RMSProp (Tieleman & Hinton, 2012). Let
$((\bm{\theta}_{n},\bm{w}_{n}))_{n\in\mathbb{N}}\subset\mathbb{R}^{\Theta}\times\mathbb{R}^{W}$
be the sequence generated by TTUR with constant learning rates $\alpha^{G}$
and $\alpha^{D}$. We will show that, under certain assumptions, for all
$\bm{\theta}\in\mathbb{R}^{\Theta}$ and all $\bm{w}\in\mathbb{R}^{W}$,

$\displaystyle\begin{split}\quad&\frac{1}{N}\sum_{n=1}^{N}\mathbb{E}\left[\langle\bm{\theta}_{n}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\\\
&\quad\leq\underbrace{\frac{\Theta\mathrm{Dist}(\bm{\theta})H^{G}}{2\alpha^{G}\tilde{\beta_{1}^{G}}}}_{A_{G}}\frac{1}{N}+\underbrace{\frac{\sigma_{G}^{2}\alpha^{G}}{2\tilde{\beta_{1}^{G}}\tilde{\gamma}^{G^{2}}h_{0,*}^{G}}}_{B_{G}}\frac{1}{b}\\\
&\quad\quad+\underbrace{\frac{M_{G}^{2}\alpha^{G}}{2\tilde{\beta_{1}^{G}}\tilde{\gamma}^{G^{2}}h_{0,*}^{G}}+\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}\sqrt{\Theta\mathrm{Dist}(\bm{\theta})(\sigma_{G}^{2}+M_{G}^{2})}}_{C_{G}},\\\
&\frac{1}{N}\sum_{n=1}^{N}\mathbb{E}\left[\langle\bm{w}_{n}-\bm{w},\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\\\
&\quad\leq\underbrace{\frac{W\mathrm{Dist}(\bm{w})H^{D}}{2\alpha^{D}\tilde{\beta_{1}^{D}}}}_{A_{D}}\frac{1}{N}+\underbrace{\frac{\sigma_{D}^{2}\alpha^{D}}{2\tilde{\beta_{1}^{D}}\tilde{\gamma}^{D^{2}}h_{0,*}^{D}}}_{B_{D}}\frac{1}{b}\\\
&\quad\quad+\underbrace{\frac{M_{D}^{2}\alpha^{D}}{2\tilde{\beta_{1}^{D}}\tilde{\gamma}^{D^{2}}h_{0,*}^{D}}+\frac{\beta_{1}^{D}}{\tilde{\beta_{1}^{D}}}\sqrt{W\mathrm{Dist}(\bm{w})(\sigma_{D}^{2}+M_{D}^{2})}}_{C_{D}},\end{split}$
(2)

where $\sigma_{G}^{2},\sigma_{D}^{2}\geq 0$,
$M_{G},M_{D},\mathrm{Dist}(\bm{\theta}),\mathrm{Dist}(\bm{w})>0$,
$\beta_{1}^{G},\beta_{1}^{D},\gamma^{G},\gamma^{D}\in[0,1)$,
$\tilde{\beta_{1}^{G}}:=1-\beta_{1}^{G}$, $\tilde{\gamma}^{G}:=1-\gamma^{G}$,
$\tilde{\beta_{1}^{D}}:=1-\beta_{1}^{D}$, $\tilde{\gamma}^{D}:=1-\gamma^{D}$,
$h_{0,*}^{G},h_{0,*}^{D}>0$, $H^{G}:=\max_{i\in[\Theta]}H_{i}^{G}$, and
$H^{D}:=\max_{j\in[W]}H_{j}^{D}$ (see Theorem 3.1 and Section 3.1 for the
definitions of the parameters). This result implies that using small constant
learning rates $\alpha^{G}$ and $\alpha^{D}$ makes $B_{G}$, $C_{G}$, $B_{D}$,
and $C_{D}$ small and that using a large batch size $b$ makes $B_{G}/b$ and
$B_{D}/b$ small. Meanwhile, using small constant learning rates $\alpha^{G}$
and $\alpha^{D}$ makes $A_{G}$ and $A_{D}$ large. Hence, we need to use a
large number of steps $N$ to make $A_{G}$ and $A_{D}$ small when small
constant learning rates are used. Therefore, small constant learning rates, a
large batch size, and a large number of steps are useful for training GANs.

####  1.3.2 Relationship between batch size and the number of steps needed for
an $\epsilon$–approximation of TTUR

Let us suppose that the generator and the discriminator run in at most $N_{G}$
and $N_{D}$ steps for a certain batch size $b$,

$\displaystyle\begin{split}&N_{G}(b):=\frac{A_{G}b}{(\epsilon_{G}^{2}-C_{G})b-B_{G}}\text{
and }\\\
&N_{D}(b):=\frac{A_{D}b}{(\epsilon_{D}^{2}-C_{D})b-B_{D}},\end{split}$ (3)

where $\epsilon_{G},\epsilon_{D}>0$. Then, we can show that TTUR is an
$\epsilon$–approximation in the sense that

$\displaystyle\frac{1}{N_{G}}\sum_{n=1}^{N_{G}}\mathbb{E}\left[\langle\bm{\theta}_{n}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\leq\epsilon_{G}^{2}\text{
and }$
$\displaystyle\frac{1}{N_{D}}\sum_{n=1}^{N_{D}}\mathbb{E}\left[\langle\bm{w}_{n}-\bm{w},\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\leq\epsilon_{D}^{2}.$

Moreover, $N_{G}$ and $N_{D}$ are monotone decreasing and convex functions of
the batch size (Theorem 3.2). This result implies that large batch sizes are
desirable in the sense of minimizing the number of steps for training GANs. A
particularly interesting concern is how large the batch size $b$ should be.

####  1.3.3 Existence of a critical batch size minimizing SFO complexity

Here, we consider stochastic first-order oracle (SFO) complexities (Iiduka,
2022b) defined by $N_{G}(b)b$ and $N_{D}(b)b$. We show that $N_{G}(b)b$ and
$N_{D}(b)b$ are convex functions of $b$ and that there exist global minimizers
$b_{G}^{\star}$ and $b_{D}^{\star}$ of $N_{G}(b)b$ and $N_{D}(b)b$ (Theorem
3.3). Accordingly, $b_{G}^{\star}$ and $b_{D}^{\star}$ are given by

$\displaystyle b_{G}^{\star}:=\frac{2B_{G}}{\epsilon_{G}^{2}-C_{G}}\text{ and
}b_{D}^{\star}:=\frac{2B_{D}}{\epsilon_{D}^{2}-C_{D}}\text{.}$ (4)

It would be desirable to use critical batch sizes $b_{G}^{\star}$ and
$b_{D}^{\star}$ as it minimizes the SFO complexity, which is the computation
cost of the stochastic gradient. Furthermore, we show that lower bounds for
$b_{G}^{\star}$ and $b_{D}^{\star}$ can be estimated from some
hyperparameters, the total number of datasets, and the number of dimensions of
the model (Proposition 3.4).

####  1.3.4 Numerical results supporting our theoretical results: Estimation
of critical batch size minimizing SFO complexity

We use FID as a performance measure for training a deep convolutional GAN
(DCGAN) (Radford et al., 2016) on the LSUN-Bedroom dataset (Yu et al., 2015),
a Wasserstein GAN with Gradient Penalty (WGAN-GP) (Gulrajani et al., 2017) on
the CelebA dataset (Liu et al., 2015), and a BigGAN (Brock et al., 2019) on
the ImageNet dataset (Deng et al., 2009). We numerically show that increasing
the batch size decreases the number of steps needed to achieve a low FID score
and that there exist critical batch sizes minimizing the SFO complexities. The
numerical results match our theoretical results in Sections 1.3.2 and 1.3.3.
We are also interested in estimating appropriate batch sizes before
implementing TTURs. Hence, we estimate batch sizes using $b_{G}^{\star}$ and
$b_{D}^{\star}$ in (4) and compare them with ones measured in numerical
experiments. We find that the estimated sizes are close to the measured ones
(see Section 4.4).

##  2 Mathematical Preliminaries

###  2.1 Assumptions

The notation used in this paper is summarized in Table 1.

Table 1: Notation List (The parameters and functions of the discriminator are defined by replacing $G$, $\mathcal{S}_{n}$, $\bm{\theta}$, and $\bm{w}$ in the generator with $D$, $\mathcal{R}_{n}$, $\bm{w}$, and $\bm{\theta}$) Notation | Description
---|---
$\mathbb{N}$ | The set of all nonnegative integers
$[N]$ |  $[N]:=\\{1,2,\ldots,N\\}$ ($N\in\mathbb{N}\backslash\\{0\\}$)
$|A|$ |  The number of elements of a set $A$
$\mathbb{R}^{d}$ |  A $d$-dimensional Euclidean space with inner product $\langle\cdot,\cdot\rangle$, which induces the norm $\|\cdot\|$
$\mathbb{R}_{+}^{d}$ | $\mathbb{R}_{+}^{d}:=\\{\bm{x}\in\mathbb{R}^{d}\colon x_{i}\geq 0\text{ }(i\in[d])\\}$
$\mathbb{R}_{++}^{d}$ | $\mathbb{R}_{++}^{d}:=\\{\bm{x}\in\mathbb{R}^{d}\colon x_{i}>0\text{ }(i\in[d])\\}$
$\mathbb{S}_{++}^{d}$ |  The set of $d\times d$ symmetric positive-definite matrices
$\mathbb{D}^{d}$ |  The set of $d\times d$ diagonal matrices, i.e., $\mathbb{D}^{d}=\\{M\in\mathbb{R}^{d\times d}\colon M=\mathsf{diag}(x_{i}),\text{ }x_{i}\in\mathbb{R}\text{ }(i\in[d])\\}$
$\mathbb{E}_{\xi}[X]$ |  The expectation with respect to $\xi$ of a random variable $X$
$\mathcal{S}$ |  A set of synthetic samples $\bm{z}^{(i)}$
$\mathcal{R}$ |  A set of real-world samples $\bm{x}^{(i)}$
$\mathcal{S}_{n}$ |  Mini-batch of $b$ synthetic samples $\bm{z}^{(i)}$ at time $n$
$\mathcal{R}_{n}$ |  Mini-batch of $b$ real world samples $\bm{x}^{(i)}$ at time $n$
$L_{G}^{(i)}(\cdot,\bm{w})$ |  A loss function of the generator for $\bm{w}\in\mathbb{R}^{W}$ and $\bm{z}^{(i)}$
$L_{G}(\cdot,\bm{w})$ |  The total loss function of the generator for $\bm{w}\in\mathbb{R}^{W}$, i.e., $L_{G}(\cdot,\bm{w}):=|\mathcal{S}|^{-1}\sum_{i\in\mathcal{S}}L_{G}^{(i)}(\cdot,\bm{w})$
$\xi^{G}$ |  A random variable supported on $\Xi^{G}$ that does not depend on $\bm{w}\in\mathbb{R}^{W}$ and $\bm{\theta}\in\mathbb{R}^{\Theta}$
$\xi_{n}^{G}$ |  $\xi_{0}^{G},\xi_{1}^{G},\ldots$ are independent samples and $\xi_{n}^{G}$ is independent of $(\bm{\theta}_{k})_{k=0}^{n}\subset\mathbb{R}^{\Theta}$ and $\bm{w}\in\mathbb{R}^{W}$
$\xi_{n,i}^{G}$ |  A random variable generated from the $i$-th sampling at time $n$
$\xi_{[n]}^{G}$ |  The history of process $\xi_{0}^{G},\xi_{1}^{G},\ldots$ to time step $n$, i.e., $\xi_{[n]}^{G}:=(\xi_{0}^{G},\xi_{1}^{G},\ldots,\xi_{n}^{G})$
$\mathsf{G}_{\xi^{G}}(\bm{\theta})$ |  The stochastic gradient of $L_{G}(\cdot,\bm{w})$ at $\bm{\theta}\in\mathbb{R}^{\Theta}$
$\nabla L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})$ |  The mini-batch stochastic gradient of $L_{G}(\bm{\theta}_{n},\bm{w}_{n})$ for $\mathcal{S}_{n}$, i.e., $\nabla L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n}):=b^{-1}\sum_{i\in[b]}\mathsf{G}_{\xi_{n,i}^{G}}(\bm{\theta}_{n})$

We assume the following standard conditions:

######  Assumption 2.1.

(S1) $L_{G}^{(i)}(\cdot,\bm{w})\colon\mathbb{R}^{\Theta}\to\mathbb{R}$ and
$L_{D}^{(i)}(\bm{\theta},\cdot)\colon\mathbb{R}^{W}\to\mathbb{R}$ are
continuously differentiable.

(S2) Let
$((\bm{\theta}_{n},\bm{w}_{n}))_{n\in\mathbb{N}}\subset\mathbb{R}^{\Theta}\times\mathbb{R}^{W}$
be the sequence generated by an optimizer.

(i) For each iteration $n$,

$\displaystyle\mathbb{E}_{\xi_{n}^{G}}\left[\mathsf{G}_{\xi_{n}^{G}}(\bm{\theta}_{n})\right]=\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\text{
and }$
$\displaystyle\mathbb{E}_{\xi_{n}^{D}}\left[\mathsf{G}_{\xi_{n}^{D}}(\bm{w}_{n})\right]=\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n}).$

(ii) There exist nonnegative constants $\sigma_{G}^{2}$ and $\sigma_{D}^{2}$
such that

$\displaystyle\mathbb{E}_{\xi_{n}^{G}}\left[\|\mathsf{G}_{\xi_{n}^{G}}(\bm{\theta}_{n})-\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\|^{2}\right]\leq\sigma_{G}^{2}\text{
and }$
$\displaystyle\mathbb{E}_{\xi_{n}^{D}}\left[\|\mathsf{G}_{\xi_{n}^{D}}(\bm{w}_{n})-\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\|^{2}\right]\leq\sigma_{D}^{2}.$

(S3) For each iteration $n$, the optimizer samples mini-batches
$\mathcal{S}_{n}\subset\mathcal{S}$ and $\mathcal{R}_{n}\subset\mathcal{R}$
and estimates the full gradients $\nabla L_{G}$ and $\nabla L_{D}$ as

$\displaystyle\nabla L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})$
$\displaystyle:=\frac{1}{b}\sum_{i\in[b]}\mathsf{G}_{\xi_{n,i}^{G}}(\bm{\theta}_{n})$
$\displaystyle=\frac{1}{b}\sum_{\\{i\colon\bm{z}^{(i)}\in\mathcal{S}_{n}\\}}\nabla_{\bm{\theta}}L_{G}^{(i)}(\bm{\theta}_{n},\bm{w}_{n})\text{
and }$ $\displaystyle\nabla L_{D,\mathcal{R}_{n}}(\bm{w}_{n})$
$\displaystyle:=\frac{1}{b}\sum_{i\in[b]}\mathsf{G}_{\xi_{n,i}^{D}}(\bm{w}_{n})$
$\displaystyle=\frac{1}{b}\sum_{\\{i\colon\bm{x}^{(i)}\in\mathcal{R}_{n}\\}}\nabla_{\bm{w}}L_{D}^{(i)}(\bm{\theta}_{n},\bm{w}_{n}).$

###  2.2 Adaptive method

We will consider the following TTUR-type optimizer, described by Algorithm 1,
for solving Problem (1).

Algorithm 1 Adaptive Method for Solving Problem (1)

0:
$(\alpha_{n}^{G})_{n\in\mathbb{N}},(\alpha_{n}^{D})_{n\in\mathbb{N}}\subset\mathbb{R}_{++}$,
$\beta_{1}^{G},\beta_{1}^{D}\in[0,1)$, $\gamma^{G},\gamma^{D}\in[0,1)$

1: $n\leftarrow 0$,
$(\bm{\theta}_{0},\bm{w}_{0})\in\mathbb{R}^{\Theta}\times\mathbb{R}^{W}$,
$\bm{m}_{-1}^{G}=\bm{0}\in\mathbb{R}^{\Theta}$,
$\bm{m}_{-1}^{D}=\bm{0}\in\mathbb{R}^{W}$

2: loop

3: loop

4: $\bm{m}_{n}^{G}:=\beta_{1}^{G}\bm{m}_{n-1}^{G}+(1-\beta_{1}^{G})\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})$

5: $\hat{\bm{m}}_{n}^{G}:=(1-\gamma^{{G}^{n+1}})^{-1}\bm{m}_{n}^{G}$

6: $\mathsf{H}_{n}^{G}\in\mathbb{S}_{++}^{\Theta}\cap\mathbb{D}^{\Theta}$

7: Find $\bm{d}_{n}^{G}\in\mathbb{R}^{\Theta}$ that solves
$\mathsf{H}_{n}^{G}\bm{d}=-\hat{\bm{m}}_{n}^{G}$

8: $\bm{\theta}_{n+1}:=\bm{\theta}_{n}+\alpha_{n}^{G}\bm{d}^{G}_{n}$

9: end loop

10: loop

11: $\bm{m}_{n}^{D}:=\beta_{1}^{D}\bm{m}_{n-1}^{D}+(1-\beta_{1}^{D})\nabla
L_{D,\mathcal{R}_{n}}(\bm{w}_{n})$

12: $\hat{\bm{m}}_{n}^{D}:=(1-\gamma^{{D}^{n+1}})^{-1}\bm{m}_{n}^{D}$

13: $\mathsf{H}_{n}^{D}\in\mathbb{S}_{++}^{W}\cap\mathbb{D}^{W}$

14: Find $\bm{d}_{n}^{D}\in\mathbb{R}^{W}$ that solves
$\mathsf{H}_{n}^{D}\bm{d}=-\hat{\bm{m}}_{n}^{D}$

15: $\bm{w}_{n+1}:=\bm{w}_{n}+\alpha_{n}^{D}\bm{d}^{D}_{n}$

16: end loop

17: $n\leftarrow n+1$

18: end loop

In order to analyze Algorithm 1, we will assume the following conditions:

######  Assumption 2.2.

  1. (A1)

$\mathsf{H}_{n}^{G}=\mathsf{diag}(h_{n,i}^{G})$ depends on $\xi_{[n]}^{G}$ and
$\mathsf{H}_{n}^{D}=\mathsf{diag}(h_{n,i}^{D})$ depends on $\xi_{[n]}^{D}$.
Moreover, $h_{n+1,i}^{G}\geq h_{n,i}^{G}$ and $h_{n+1,j}^{D}\geq h_{n,j}^{D}$
hold for all $n\in\mathbb{N}$, all $i\in[\Theta]$, and all $j\in[W]$.

  2. (A2)

For all $i\in[\Theta]$, there exists a positive number $H_{i}^{G}$ such that
$\sup_{n\in\mathbb{N}}\mathbb{E}[h_{n,i}^{G}]\leq H_{i}^{G}$. For all
$j\in[W]$, there exists a positive number $H_{j}^{D}$ such that
$\sup_{n\in\mathbb{N}}\mathbb{E}[h_{n,j}^{D}]\leq H_{j}^{D}$.

Examples of
$\mathsf{H}_{n}^{G}\in\mathbb{S}_{++}^{\Theta}\cap\mathbb{D}^{\Theta}$ and
$\mathsf{H}_{n}^{D}\in\mathbb{S}_{++}^{W}\cap\mathbb{D}^{W}$ satisfying
Assumption 2.2 are listed in Table 4 (see Appendix A.1). By referring to the
results in (Chen et al., 2019; Iiduka, 2022a; Zhuang et al., 2020), we can
check that $\mathsf{H}_{n}^{G}$ and $\mathsf{H}_{n}^{D}$ in Table 4 satisfy
(A1) and (A2).

##  3 Main Results

###  3.1 Convergence analysis of Algorithm 1 using constant learning rates

We will assume the following conditions:

######  Assumption 3.1.

  1. (C1)

$\alpha_{n}^{G}:=\alpha^{G}$ and $\alpha_{n}^{D}:=\alpha^{D}$ for all
$n\in\mathbb{N}$.

  2. (C2)

There exist positive numbers $M_{G}$ and $M_{D}$ such that
$\mathbb{E}[\|\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\|^{2}]\leq
M_{G}^{2}$ and
$\mathbb{E}[\|\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\|^{2}]\leq
M_{D}^{2}$.

  3. (C3)

For all $\bm{\theta}=(\theta_{i})\in\mathbb{R}^{\Theta}$ and all
$\bm{w}=(w_{i})\in\mathbb{R}^{W}$, there exist positive numbers
$\mathrm{Dist}(\bm{\theta})$ and $\mathrm{Dist}(\bm{w})$ such that
$\max_{i\in[\Theta]}\sup\\{(\theta_{n,i}-\theta_{i})^{2}\colon
n\in\mathbb{N}\\}\leq\mathrm{Dist}(\bm{\theta})$ and
$\max_{i\in[W]}\sup\\{(w_{n,i}-w_{i})^{2}\colon
n\in\mathbb{N}\\}\leq\mathrm{Dist}(\bm{w})$.

A previous study (Heusel et al., 2017) used a decaying learning rate
$\mathcal{O}(n^{-\tau})$, where $\tau\in(0,1]$, for TTUR based on Adam to
train GANs. This paper investigates the performance of TTUR based on adaptive
methods using constant learning rates defined by (C1). Condition (C2) provides
upper bounds on the performance measures
$(1/N)\sum_{n=1}^{N}\mathbb{E}\left[\langle\bm{\theta}_{n}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
and
$(1/N)\sum_{n=1}^{N}\mathbb{E}\left[\langle\bm{w}_{n}-\bm{w},\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
(see (2) and Theorem 3.1 for details). (C2) has also been used to analyze
adaptive methods for training deep neural networks (see, e.g., (Chen et al.,
2019; Zhuang et al., 2020)). Condition (C3) has been used to provide upper
bounds on the performance measures and for analyzing both convex and nonconvex
optimization in deep neural networks (see, e.g., (Kingma & Ba, 2015; Reddi et
al., 2018; Zhuang et al., 2020)). See Appendix A.12 for remarks regarding
(C3).

The following is a convergence analysis of Algorithm 1 (The proof of Theorem
3.1 is in Appendices A.6 and A.7).

######  Theorem 3.1.

Suppose that Assumptions 2.1, 2.2, and 3.1 hold and consider the sequence
$((\bm{\theta}_{n},\bm{w}_{n}))_{n\in\mathbb{N}}$ generated by Algorithm 1.
Then, the following hold:

(i) For all $\bm{\theta}\in\mathbb{R}^{\Theta}$ and all
$\bm{w}\in\mathbb{R}^{W}$,

$\displaystyle\liminf_{n\to+\infty}\mathbb{E}\left[\langle\bm{\theta}_{n}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
$\displaystyle\leq\frac{\alpha^{G}(\sigma_{G}^{2}b^{-1}+M_{G}^{2})}{2\tilde{\beta_{1}^{G}}\tilde{\gamma}^{G^{2}}h_{0,*}^{G}}+\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}\frac{\beta^{G}}{\tilde{\beta_{1}^{G}}},$
$\displaystyle\liminf_{n\to+\infty}\mathbb{E}\left[\langle\bm{w}_{n}-\bm{w},\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
$\displaystyle\leq\frac{\alpha^{D}(\sigma_{D}^{2}b^{-1}+M_{D}^{2})}{2\tilde{\beta_{1}^{D}}\tilde{\gamma}^{D^{2}}h_{0,*}^{D}}+\sqrt{W\mathrm{Dist}(\bm{w})\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)}\frac{\beta_{1}^{D}}{\tilde{\beta_{1}^{D}}},$

where $\tilde{\beta_{1}^{G}}:=1-\beta_{1}^{G}$,
$\tilde{\beta_{1}^{D}}:=1-\beta_{1}^{D}$, $\tilde{\gamma}^{G}:=1-\gamma^{G}$,
$\tilde{\gamma}^{D}:=1-\gamma^{D}$,
$h_{0,*}^{G}:=\min_{i\in[\Theta]}h_{0,i}^{G}$, and
$h_{0,*}^{D}:=\min_{j\in[W]}h_{0,j}^{D}$. Furthermore, there exist
accumulation points $(\bm{\theta}^{*},\bm{w}^{*})$ and
$(\bm{\theta}_{*},\bm{w}_{*})$ of
$((\bm{\theta}_{n},\bm{w}_{n}))_{n\in\mathbb{N}}$ such that

$\displaystyle\mathbb{E}\left[\|\nabla_{\bm{\theta}}L_{G}(\bm{\theta}^{*},\bm{w}^{*})\|^{2}\right]$
$\displaystyle\leq\frac{\alpha^{G}(\sigma_{G}^{2}b^{-1}+M_{G}^{2})}{2\tilde{\beta_{1}^{G}}\tilde{\gamma}^{G^{2}}h_{0,*}^{G}}+\sqrt{\Theta\mathrm{Dist}(\tilde{\bm{\theta}})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}},$
$\displaystyle\mathbb{E}\left[\|\nabla_{\bm{w}}L_{D}(\bm{\theta}_{*},\bm{w}_{*})\|^{2}\right]$
$\displaystyle\leq\frac{\alpha^{D}(\sigma_{D}^{2}b^{-1}+M_{D}^{2})}{2\tilde{\beta_{1}^{D}}\tilde{\gamma}^{D^{2}}h_{0,*}^{D}}+\sqrt{W\mathrm{Dist}(\tilde{\bm{w}})\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)}\frac{\beta_{1}^{D}}{\tilde{\beta_{1}^{D}}},$

where
$\tilde{\bm{\theta}}:=\bm{\theta}^{*}-\nabla_{\bm{\theta}}L_{G}(\bm{\theta}^{*},\bm{w}^{*})$
and
$\tilde{\bm{w}}:=\bm{w}_{*}-\nabla_{\bm{w}}L_{D}(\bm{\theta}_{*},\bm{w}_{*})$.

(ii) For all $\bm{\theta}\in\mathbb{R}^{\Theta}$, all
$\bm{w}\in\mathbb{R}^{W}$, and all $N\geq 1$,

$\displaystyle\frac{1}{N}\sum_{n\in[N]}\mathbb{E}\left[\langle\bm{\theta}_{n}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
$\displaystyle\quad\leq\frac{\Theta\mathrm{Dist}(\bm{\theta})H^{G}}{2\alpha^{G}\tilde{\beta_{1}^{G}}N}+\frac{\alpha^{G}}{2\tilde{\beta_{1}^{G}}\tilde{\gamma}^{G^{2}}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)$
$\displaystyle\quad\quad+\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)},$
$\displaystyle\frac{1}{N}\sum_{n\in[N]}\mathbb{E}\left[\langle\bm{w}_{n}-\bm{w},\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
$\displaystyle\quad\leq\frac{W\mathrm{Dist}(\bm{w})H^{D}}{2\alpha^{D}\tilde{\beta_{1}^{D}}N}+\frac{\alpha^{D}}{2\tilde{\beta_{1}^{D}}\tilde{\gamma}^{D^{2}}h_{0,*}^{D}}\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)$
$\displaystyle\quad\quad+\frac{\beta_{1}^{D}}{\tilde{\beta_{1}^{D}}}\sqrt{W\mathrm{Dist}(\bm{w})\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)},$

where $H^{G}:=\max_{i\in[\Theta]}H_{i}^{G}$ and
$H^{D}:=\max_{j\in[W]}H_{j}^{D}$.

Theorem 3.1(i) and (ii) indicate that the larger the batch size $b$ is, the
smaller the upper bounds of the performance measures become. From Theorem
3.1(i), it would be desirable to use small learning rates $\alpha^{G}$ and
$\alpha^{D}$. Meanwhile, Theorem 3.1(ii) indicates that there is no evidence
that using sufficiently small $\alpha^{G}$ and $\alpha^{D}$ is good for
training GANs since the upper bounds in Theorem 3.1 depend on $\alpha^{G}$,
$\alpha^{D}$, $1/\alpha^{G}$, and $1/\alpha^{D}$. Indeed, the results reported
in (Heusel et al., 2017) used small $\alpha^{G},\alpha^{D}=10^{-4},10^{-5}$.

###  3.2 Relationship between batch size and number of steps for Algorithm 1

The relationship between $b$ and the number of steps $N$ satisfying an
$\epsilon$–approximation of TTUR is as follows (The proof of Theorem 3.2 is in
Appendix A.8):

######  Theorem 3.2.

Suppose that Assumptions 2.1, 2.2, and 3.1 hold and consider Algorithm 1.
Then, $N_{G}$ and $N_{D}$ defined by

$\displaystyle\begin{split}&N_{G}(b):=\frac{A_{G}b}{(\epsilon_{G}^{2}-C_{G})b-B_{G}}\leq
N_{G}\text{ for }b>\frac{B_{G}}{\epsilon_{G}^{2}-C_{G}},\\\
&N_{D}(b):=\frac{A_{D}b}{(\epsilon_{D}^{2}-C_{D})b-B_{D}}\leq N_{D}\text{ for
}b>\frac{B_{D}}{\epsilon_{D}^{2}-C_{D}}\end{split}$ (5)

satisfy

$\displaystyle\begin{split}&\frac{1}{N_{G}}\sum_{n=1}^{N_{G}}\mathbb{E}\left[\langle\bm{\theta}_{n}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\leq\epsilon_{G}^{2},\\\
&\frac{1}{N_{D}}\sum_{n=1}^{N_{D}}\mathbb{E}\left[\langle\bm{w}_{n}-\bm{w},\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\leq\epsilon_{D}^{2},\end{split}$
(6)

where $A_{G}$, $B_{G}$, $C_{G}$, $A_{D}$, $B_{D}$, and $C_{D}$ are defined as
in (2). Moreover, the functions $N_{G}(b)$ and $N_{D}(b)$ defined by (5) are
monotone decreasing and convex for $b>B_{G}/(\epsilon_{G}^{2}-C_{G})$ and
$b>B_{D}/(\epsilon_{D}^{2}-C_{D})$.

Theorem 3.2 indicates that $N_{G}$ and $N_{D}$ defined by (5) decrease as the
batch size increases. Accordingly, it is useful to choose a sufficiently large
$b$ in the sense of minimizing of the number of steps $N$ needed for an
$\epsilon$–approximation of TTUR.

###  3.3 Existence of a critical batch size

A particular concern is how large $b$ should be. Here, we consider SFO
complexities defined for the number of steps needed for (6) and for the batch
size by

$\displaystyle\begin{split}&N_{G}(b)b=\frac{A_{G}b^{2}}{(\epsilon_{G}^{2}-C_{G})b-B_{G}}\text{
and}\\\
&N_{D}(b)b=\frac{A_{D}b^{2}}{(\epsilon_{D}^{2}-C_{D})b-B_{D}}.\end{split}$ (7)

The following theorem guarantees the existence of critical batch sizes that
are global minimizers of $N_{G}(b)b$ and $N_{D}(b)b$ defined by (7) (The proof
of Theorem 3.3 is in Appendix A.9).

######  Theorem 3.3.

Suppose that Assumptions 2.1, 2.2, and 3.1 hold and consider Algorithm 1.
Then, there exist

$\displaystyle b_{G}^{\star}:=\frac{2B_{G}}{\epsilon_{G}^{2}-C_{G}}\text{ and
}b_{D}^{\star}:=\frac{2B_{D}}{\epsilon_{D}^{2}-C_{D}}$ (8)

such that $b_{G}^{\star}$ minimizes the convex function $N_{G}(b)b$
($b>B_{G}/(\epsilon_{G}^{2}-C_{G})$) and $b_{D}^{\star}$ minimizes the convex
function $N_{D}(b)b$ ($b>B_{D}/(\epsilon_{D}^{2}-C_{D})$).

Theorem 3.3 leads to the following proposition that gives lower bounds for the
critical batch sizes.

######  Proposition 3.4.

Suppose that the assumptions in Theorem 3.3 hold and consider Algorithm 1.
Then, $b_{G}^{\star}$ and $b_{D}^{\star}$ defined by (8) satisfy the following
that
(i) for Adam,

$\displaystyle b_{G}^{\star}$
$\displaystyle\geq\frac{\sigma_{G}^{2}\alpha^{G}}{\epsilon_{G}^{3}(1-\beta_{1}^{G})^{3}\sqrt{\frac{\Theta}{1-\beta_{2}^{G}}\frac{1}{|S|^{2}}}}\text{
and }$ $\displaystyle b_{D}^{\star}$
$\displaystyle\geq\frac{\sigma_{D}^{2}\alpha^{D}}{\epsilon_{D}^{3}(1-\beta_{1}^{D})^{3}\sqrt{\frac{W}{1-\beta_{2}^{D}}\frac{1}{|S|^{2}}}},$

(ii) for AdaBelief,

$\displaystyle b_{G}^{\star}$
$\displaystyle\geq\frac{\sigma_{G}^{2}\alpha^{G}}{\epsilon_{G}^{3}(1-\beta_{1}^{G})^{3}\sqrt{\frac{4\Theta}{1-\beta_{2}^{G}}\frac{1}{|S|^{2}}}}\text{
and }$ $\displaystyle b_{D}^{\star}$
$\displaystyle\geq\frac{\sigma_{D}^{2}\alpha^{D}}{\epsilon_{D}^{3}(1-\beta_{1}^{D})^{3}\sqrt{\frac{4W}{1-\beta_{2}^{D}}\frac{1}{|S|^{2}}}},$

(iii) for RMSProp,

$\displaystyle
b_{G}^{\star}\geq\frac{\sigma_{G}^{2}\alpha^{G}}{\epsilon_{G}^{3}\sqrt{\frac{\Theta}{|S|^{2}}}}\text{
and
}b_{D}^{\star}\geq\frac{\sigma_{D}^{2}\alpha^{D}}{\epsilon_{D}^{3}\sqrt{\frac{W}{|S|^{2}}}},$

where $\sigma_{G}^{2},\sigma_{D}^{2}\geq 0$,
$\alpha^{G},\alpha^{D},\epsilon_{G},\epsilon_{D}>0$,
$\beta_{1}^{G},\beta_{1}^{D}\in[0,1)$, and
$\beta_{2}^{G},\beta_{2}^{D}\in[0,1)$.

Theorem 3.3 indicates that critical batch sizes exist in the sense of
minimizing the SFO complexities $N_{G}(b)b$ and $N_{D}(b)b$. We are interested
in verifying whether or not a critical batch size exists for training GANs as
is the case of training deep neural networks (Shallue et al., 2019; Zhang et
al., 2019; Iiduka, 2022b). The next section numerically examines the
relationship between the batch size $b$ and the number of steps $N$ and also
that between $b$ and the SFO complexity $Nb$ to see if there is a critical
batch size $b^{\star}$ at which $N(b)b$ is minimized. Proposition 3.4
indicates that a lower bound for the critical batch size can be estimated from
some hyperparameters. Hence, we would like to check whether the estimated
sizes are close to the measured ones (see Section 4.4).

##  4 Numerical Results

We measured the number of steps required to achieve a low FID (Heusel et al.,
2017) score for different batch sizes in several GAN trainings. The
experimental environment consisted of NVIDIA DGX A100$\times$8GPU and Dual AMD
Rome7742 2.25-GHz, 128 Cores$\times$2CPU. The software environment was Python
3.8.2, Pytorch 1.6.0, and CUDA 11.6. The distribution of $\xi_{n}^{G}$ was a
uniform one. The clean-fid package (Parmar et al., 2022) was used to calculate
the FID. The code is available at https://github.com/iiduka-researches/GANs.
The TTURs based on Adam, AdaBelief, and RMSProp used $\mathsf{H}_{n}^{G}$ and
$\mathsf{H}_{n}^{D}$ defined in Table 4. See Table 5 for the optimizer
hyperparameters used in the experiment. The learning rate used in each
experiment was determined on the basis of a grid search of 36 combinations of
the generator learning rate $\alpha^{G}$ and discriminator learning rate
$\alpha^{D}$ (see Figure 7 in Appendix A.3). Appendix A.4 indicates that, when
a fixed batch size is used, the FID scores of the TTURs used in the
experiments decrease sufficiently as the number of steps increases.

###  4.1 Training DCGAN on the LSUN-Bedroom dataset

First, we evaluated the performance of TTURs based on RMSProp, AdaBelief, and
Adam in training DCGAN (Radford et al., 2016) on the LSUN-Bedroom dataset.
Figure 1 plots the number of steps $N$ needed to achieve an FID score lower
than 70 versus the batch size $b$. The figure indicates that the number of
steps for TTUR based on any optimizer is monotone decreasing and convex with
respect to $b$. Figure 2 plots the SFO complexity $Nb$ versus $b$. The figure
indicates that $Nb$ for TTUR based on any optimizer is convex with respect to
$b$.

###  4.2 Training WGAN-GP on the CelebA dataset

Next, we evaluated the performance of TTURs based on RMSProp, AdaBelief, and
Adam in training WGAN-GP on the CelebA dataset. The original WGAN-GP code
updates the discriminator five times for each generator update, whereas the
discriminator is updated only once when using TTUR. Figure 3 plots the number
of steps $N$ needed to achieve an FID score lower than 50 versus the batch
size $b$. The figure indicates that the number of steps for TTUR based on any
optimizer is a monotone decreasing and convex function of $b$. Figure 4 plots
$Nb$ versus $b$. The figure indicates that $Nb$ for TTUR based on any
optimizer is a convex function of $b$.

Table 2: Parameters used to train GANs | Section 4.1 | Section 4.2 | Section 4.3
---|---|---|---
$\Theta$ | $\sepnum{.}{,}{,}{3576704}$ | $\sepnum{.}{,}{,}{3576704}$ | $\sepnum{.}{,}{,}{70433795}$
W | $\sepnum{.}{,}{,}{2765568}$ | $\sepnum{.}{,}{,}{2765568}$ | $\sepnum{.}{,}{,}{87982369}$
$|S|$ | $\sepnum{.}{,}{,}{3033042}$ | $\sepnum{.}{,}{,}{162770}$ | $\sepnum{.}{,}{,}{1281167}$
Figure 1: Number of steps for TTURs based on Adam, AdaBelief, and RMSProp
versus batch size needed to train DCGAN on the LSUN-Bedroom dataset. The
average of multiple runs is plotted.
---
Figure 2: SFO complexities for TTURs based on Adam, AdaBelief, and RMSProp
versus batch size needed to train DCGAN on the LSUN-Bedroom dataset. The
double circle symbol denotes the measured critical batch size that minimizes
SFO complexity. The square symbol denotes the estimated critical batch size.
---
Figure 3: Number of steps for TTURs based on Adam, AdaBelief, and RMSProp
versus batch size needed to train WGAN-GP on the CelebA dataset. The average
of multiple runs is plotted.
---
Figure 4: SFO complexities for TTURs based on Adam, AdaBelief, and RMSProp
versus batch size needed to train WGAN-GP on the CelebA dataset. The double
circle symbol denotes the measured critical batch size that minimizes SFO
complexity. The square symbol denotes the estimated critical batch size.
---
Figure 5: Number of steps for TTURs based on Adam and AdaBelief versus batch
size needed to train BigGAN on the ImageNet dataset. The average of multiple
runs is plotted.
---
Figure 6: SFO complexities for TTURs based on Adam and AdaBelief versus batch
size needed to train BigGAN on the ImageNet dataset. The double circle symbol
denotes the measured critical batch size that minimizes SFO complexity. The
square symbol denotes the estimated critical batch size.
---
Table 3: Measured and estimated critical batch sizes | Section 4.1 | Section 4.2 | Section 4.3
---|---|---|---
| measured | estimated | measured | estimated | measured | estimated
Adam | $2^{5}$ | $2^{5}$ | $2^{1}$ | $2^{1}$ | $2^{8}$ | $2^{8}$
AdaBelief | $2^{5}$ | $2^{5}$ | $2^{2}$ | $2^{2}$ | $2^{9}$ | $2^{9}$
RMSProp | $2^{3}$ | $2^{7}$ | $2^{6}$ | $2^{4}$ | - | -

###  4.3 Training BigGAN on the ImageNet dataset

We evaluated the performance of TTURs based on AdaBelief and Adam in training
BigGAN (Brock et al., 2019) on the ImageNet dataset. Figure 5 plots the number
of steps $N$ needed to achieve an FID score lower than 25 versus the batch
size $b$. The figure indicates that the number of steps for TTUR based on
AdaBelief and Adam is monotone decreasing and convex with respect to $b$.
Figure 6 plots the SFO complexity $Nb$ versus $b$. The figure indicates that
$Nb$ for TTUR based on AdaBelief and Adam is convex with respect to $b$.

We can conclude that the results in Sections 4.1, 4.2, and 4.3 support the
theoretical results (Theorems 3.2 and 3.3).

###  4.4 Estimation of lower bound of critical batch size

Proposition 3.4 indicates that a lower bound on the critical batch size can be
estimated with some parameters. The parameters used in the experiments are
shown in Table 2; see Section A.2 for the settings of $\alpha^{G}$,
$\beta_{1}^{G}$, and so on. Figure 2 indicates that the measured critical
batch sizes minimizing the SFO complexities of Adam, AdaBelief, and RMSProp
are $2^{5}=32$, $2^{5}=32$, and $2^{3}=8$, respectively. For batch sizes below
$2^{7}=128$, there is no significant difference in SFO complexity, but it is
clear that the measured critical batch size is less than $2^{7}$. In the
previous studies (Shallue et al., 2019; Zhang et al., 2019), the critical
batch sizes for training deep neural networks are large, such as $2^{12}$,
while the critical batch sizes for training GANs are small. According to
Figure 2, in the DCGAN on the LSUN-Bedroom dataset setting, the measured
critical batch size for Adam is $2^{5}$; using this and Proposition 3.4(i) to
back-calculate $\sigma_{G}^{2}$/$\epsilon_{G}^{3}$ gives
$\sigma_{G}^{2}$/$\epsilon_{G}^{3}$ $=788.7$. We can use this ratio and
Proposition 3.4(ii), (iii) to estimate a lower bound of $47.9$ for AdaBelief
and $126.5$ for RMSProps (see Table 3).

Figure 4 indicates that the measured critical batch sizes for Adam, AdaBelief,
and RMSProp are $2$, $2^{2}=4$, and $2^{6}=64$, respectively. As in Figure 2,
there is no significant difference in SFO complexity for batch sizes less than
$2^{6}$, but it is clear that the critical batch size is less than $2^{6}$. As
expected, it is smaller than the critical batch sizes of deep neural networks.
In the same way as above, the estimated lower bounds on the WGAN-GP on the
CelebA dataset are $1.7$ for Adam, $4.25$ for AdaBelief, and $20.3$ for
RMSProp (see Table 3).

According to Figure 6, in the BigGAN on the ImageNet dataset setting, the
measured critical batch size for Adam is $2^{8}$; using this and Proposition
3.4(i) to back calculate $\sigma_{G}^{2}$/$\epsilon_{G}^{3}$ gives
$\sigma_{G}^{2}$/$\epsilon_{G}^{3}$ $=530303.8$. We can use this ratio and
Proposition 3.4(ii) to estimate a lower bound of $511.99$ for AdaBelief (see
Table 3).

Proposition 3.4(i) and (ii) indicate that the estimated critical batch sizes
of Adam and AdaBelief strongly depend on the values of $\beta_{1}$ and
$\beta_{2}$. Accordingly, the estimated critical batch sizes of Adam and
AdaBelief were found to be the same as the measured ones. Meanwhile,
Proposition 3.4(iii) indicates that the critical batch size of RMSProp is
completely independent of the values of $\beta_{1}$ and $\beta_{2}$. In
particular, $\beta_{1}$ in RMSProp is always 0 and $\beta_{2}$ in RMSProp is
not used to estimate the critical batch size (see the proof of Proposition 3.4
in Appendix A.10 for details). The independence of $\beta_{1}$ and $\beta_{2}$
may have caused the failure in estimating the critical batch size of RMSProp.

##  5 Conclusion

We considered a stationary point problem in a GAN and performed a theoretical
analysis of TTUR with constant learning rates to find a solution. We evaluated
the upper bound of the expectation of the gradient of the loss function of the
discriminator and the generator and showed that it is small when small
constant learning rates and a large batch size are used. Next, we examined the
relationship between the number of steps needed for solving the problem and
batch size and showed that the number of steps decreases as the batch size
increases. Moreover, we evaluated the SFO complexity of TTUR to check how
large the batch size should be and showed that there is a critical batch size
minimizing the SFO complexity, which is a convex function of the batch size.
We also showed that it is possible to estimate the critical batch size
specific to the model-dataset-optimizer combination. Finally, we provided
numerical examples to support our theoretical analyzes. In particular, the
numerical results showed that TTUR with small constant learning rates can be
used to train DCGAN, WGAN-GP, and BigGAN, the number of steps needed to train
them is monotone decreasing with the batch size, a critical batch size that
minimizes the SFO complexity exists, and the estimated critical batch size is
close to the experimentally measured value for DCGAN, WGAN-GP, and BigGAN.

## Acknowledgements

We are sincerely grateful to Program Chairs, Area Chairs, and the three
anonymous reviewers for helping us improve the original manuscript. We would
like to thank Hiroki Naganuma (Mila, UdeM) for his help on the PyTorch
implementation. This research is partly supported by the computational
resources of the DGX A100 named TAIHO at Meiji University. This work was
supported by the Japan Society for the Promotion of Science (JSPS) KAKENHI
Grant Number 21K11773 awarded to Hideaki Iiduka.

## References

  * Arjovsky et al. (2017) Arjovsky, M., Chintala, S., and Bottou, L.  Wasserstein GAN.  In _Proceedings of the 34th International Conference on Machine Learning_ , volume 70, pp. 214–223, 2017.
  * Brock et al. (2019) Brock, A., Donahue, J., and Simonyan, K.  Large scale GAN training for high fidelity natural image synthesis.  In _Proceedings of The International Conference on Learning Representations_ , 2019.
  * Chavdarova et al. (2019) Chavdarova, T., Gidel, G., Fleuret, F., and Lacoste-Julien, S.  Reducing noise in GAN training with variance reduced extragradient.  In _Advances in Neural Information Processing Systems_ , volume 32, pp. 393–403, 2019.
  * Chen et al. (2020) Chen, H., Zheng, L., AL Kontar, R., and Raskutti, G.  Stochastic gradient descent in correlated settings: A study on Gaussian processes.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 2722–2733, 2020.
  * Chen et al. (2019) Chen, X., Liu, S., Sun, R., and Hong, M.  On the convergence of a class of Adam-type algorithms for non-convex optimization.  In _Proceedings of The International Conference on Learning Representations_ , 2019.
  * Deng et al. (2009) Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L.  ImageNet: A large-scale hierarchical image database.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 248–255, 2009.
  * Fehrman et al. (2020) Fehrman, B., Gess, B., and Jentzen, A.  Convergence rates for the stochastic gradient descent method for non-convex objective functions.  _Journal of Machine Learning Research_ , 21:1–48, 2020\.
  * Goodfellow et al. (2014) Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y.  Generative adversarial nets.  In _Advances in Neural Information Processing Systems_ , volume 27, pp. 2672–2680, 2014.
  * Goyal et al. (2017) Goyal, P., Dollár, P., Girshick, R. B., Noordhuis, P., Wesolowski, L., Kyrola, A., Tulloch, A., Jia, Y., and He, K.  Accurate, large minibatch SGD: Training ImageNet in 1 hour.  https://arxiv.org/abs/1706.02677, 2017.
  * Gulrajani et al. (2017) Gulrajani, I., Ahmed, F., Arjovsky, M., Dumoulin, V., and Courville, A. C.  Improved training of Wasserstein GANs.  In _Advances in Neural Information Processing Systems_ , volume 30, pp. 5769–5779, 2017.
  * Heusel et al. (2017) Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., and Hochreiter, S.  GANs trained by a two time-scale update rule converge to a local Nash equilibrium.  In _Advances in Neural Information Processing Systems_ , volume 30, pp. 6629–6640, 2017.
  * Hoffer et al. (2017) Hoffer, E., Hubara, I., and Soudry, D.  Train longer, generalize better: Closing the generalization gap in large batch training of neural networks.  In _Advances in Neural Information Processing Systems_ , volume 11, pp. 1729–1739, 2017.
  * Horn & Johnson (1985) Horn, R. A. and Johnson, C. R.  _Matrix Analysis_.  Cambridge University Press, Cambridge, 1985.
  * Iiduka (2022a) Iiduka, H.  Appropriate learning rates of adaptive learning rate optimization algorithms for training deep neural networks.  _IEEE Transactions on Cybernetics_ , 52(12):13250-13261, 2022a.
  * Iiduka (2022b) Iiduka, H.  Critical bach size minimizes stochastic first-order oracle complexity of deep learning optimizer using hyperparameters close to one.  https://arxiv.org/abs/2208.09814, 2022b.
  * Jordon et al. (2019) Jordon, J., Yoon, J., and van der Schaar, M.  KnockoffGAN: Generating knockoffs for feature selection using generative adversarial networks.  In _Proceedings of The International Conference on Learning Representations_ , 2019.
  * Kingma & Ba (2015) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  In _Proceedings of The International Conference on Learning Representations_ , 2015.
  * Liu et al. (2015) Liu, Z., Luo, P., Wang, X., and Tang, X.  Deep learning face attributes in the wild.  In _Proceedings of International Conference on Computer Vision_ , 2015\.
  * Nagarajan & Kolter (2017) Nagarajan, V. and Kolter, J. Z.  Gradient descent GAN optimization is locally stable.  In _Advances in Neural Information Processing Systems_ , volume 30, pp. 5591–5600, 2017.
  * Parmar et al. (2022) Parmar, G., Zhang, R., and Zhu, J.-Y.  On aliased resizing and surprising subtleties in GAN evaluation.  In _2022 IEEE/CVF Computer Vision and Pattern Recognition_ , pp. 11400–11410, 2022.
  * Radford et al. (2016) Radford, A., Metz, L., and Chintala, S.  Unsupervised representation learning with deep convolutional generative adversarial networks.  In _Proceedings of the International Conference on Learning Representations_ , 2016.
  * Reddi et al. (2018) Reddi, S. J., Kale, S., and Kumar, S.  On the convergence of Adam and beyond.  In _Proceedings of The International Conference on Learning Representations_ , 2018.
  * Sauer et al. (2021) Sauer, A., Chitta, K., Müller, J., and Geiger, A.  Projected GANs converge faster.  In _Advances in Neural Information Processing Systems_ , volume 34, pp. 17480–17492, 2021.
  * Scaman & Malherbe (2020) Scaman, K. and Malherbe, C.  Robustness analysis of non-convex stochastic gradient descent using biased expectations.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 16377–16387, 2020.
  * Shallue et al. (2019) Shallue, C. J., Lee, J., Antognini, J., Sohl-Dickstein, J., Frostig, R., and Dahl, G. E.  Measuring the effects of data parallelism on neural network training.  _Journal of Machine Learning Research_ , 20:1–49, 2019\.
  * Thekumparampil et al. (2019) Thekumparampil, K. K., Oh, S., and Khetan, A.  Robust conditional GANs under missing or uncertain labels.  In _The ICML 2019 Workshop on Uncertainty and Robustness in Deep Learning_ , volume 1–7, 2019.
  * Tieleman & Hinton (2012) Tieleman, T. and Hinton, G.  RMSProp: Divide the gradient by a running average of its recent magnitude.  _COURSERA: Neural networks for machine learning_ , 4(2):26–31, 2012.
  * Xu et al. (2020) Xu, T., Wenliang, L. K., Munn, M., and Acciaio, B.  COT-GAN: Generating sequential data via causal optimal transport.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 8798–8809, 2020.
  * You et al. (2017) You, Y., Gitman, I., and Ginsburg, B.  Large batch training of convolutional networks.  https://arxiv.org/abs/1708.03888, 2017.
  * Yu et al. (2015) Yu, F., Seff, A., Zhang, Y., Song, S., Funkhouser, T., and Xiao, J.  LSUN: Construction of a large-scale image dataset using deep learning with humans in the loop.  https://arxiv.org/abs/1506.03365, 2015.
  * Zhang & Khoreva (2019) Zhang, D. and Khoreva, A.  Progressive augmentation of GANs.  In _Advances in Neural Information Processing Systems_ , volume 32, pp. 6246–6256, 2019.
  * Zhang et al. (2019) Zhang, G., Li, L., Nado, Z., Martens, J., Sachdeva, S., Dahl, G. E., Shallue, C. J., and Grosse, R.  Which algorithmic choices matter at which batch sizes? Insights from a noisy quadratic model.  In _Advances in Neural Information Processing Systems_ , volume 32, pp. 8196–8207, 2019.
  * Zhu et al. (2021) Zhu, J., Feng, R., Shen, Y., Zhao, D., Zha, Z.-J., Zhou, J., and Chen, Q.  Low-rank subspaces in GANs.  In _Advances in Neural Information Processing Systems_ , volume 34, pp. 16648–16658, 2021.
  * Zhuang et al. (2020) Zhuang, J., Tang, T., Ding, Y., Tatikonda, S., Dvornek, N., Papademetris, X., and Duncan, J. S.  AdaBelief optimizer: Adapting stepsizes by the belief in observed gradients.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 18795–18806, 2020.

##  Appendix A Appendix

Unless stated otherwise, all relations between random variables are supported
to hold almost surely. Let $S\in\mathbb{S}_{++}^{d}$. The $S$-inner product of
$\mathbb{R}^{d}$ is defined for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$ by
$\langle\bm{x},\bm{y}\rangle_{S}:=\langle\bm{x},S\bm{y}\rangle$ and the
$S$-norm is defined by $\|\bm{x}\|_{S}:=\sqrt{\langle\bm{x},S\bm{x}\rangle}$.
The Hadamard product of $\mathbb{R}^{d}$ is defined for all
$\bm{x}=(x_{i})_{i=1}^{d}\in\mathbb{R}^{d}$ by
$\bm{x}\odot\bm{x}:=(x_{i}^{2})_{i=1}^{d}\in\mathbb{R}^{d}$.

###  A.1 Examples of diagonal matrix in Algorithm 1

Table 4: Examples of $\mathsf{H}_{n}^{G}\in\mathbb{S}_{++}^{\Theta}\cap\mathbb{D}^{\Theta}$ and $\mathsf{H}_{n}^{D}\in\mathbb{S}_{++}^{W}\cap\mathbb{D}^{W}$ (steps 6 and 13) in Algorithm 1 ($\beta_{2}^{G},\beta_{2}^{D}\in[0,1)$) | $\mathsf{H}_{n}^{G}$ | $\mathsf{H}_{n}^{D}$
---|---|---
RMSProp | $\bm{p}_{n}^{G}=\nabla L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})\odot\nabla L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})$ | $\bm{p}_{n}^{D}=\nabla L_{D,\mathcal{R}_{n}}(\bm{w}_{n})\odot\nabla L_{D,\mathcal{R}_{n}}(\bm{w}_{n})$
(Tieleman & Hinton, 2012) | $\bm{v}_{n}^{G}=\beta_{2}^{G}\bm{v}_{n-1}^{G}+(1-\beta_{2}^{G})\bm{p}_{n}^{G}$ | $\bm{v}_{n}^{D}=\beta_{2}^{D}\bm{v}_{n-1}^{D}+(1-\beta_{2}^{D})\bm{p}_{n}^{D}$
($\gamma^{G}=\gamma^{D}=\beta_{1}^{G}=\beta_{1}^{D}$) | $\mathsf{H}_{n}^{G}=\mathsf{diag}(\sqrt{v_{n,i}^{G}})$ | $\mathsf{H}_{n}^{D}=\mathsf{diag}(\sqrt{v_{n,i}^{D}})$
Adam | $\bm{p}_{n}^{G}=\nabla L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})\odot\nabla L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})$ | $\bm{p}_{n}^{D}=\nabla L_{D,\mathcal{R}_{n}}(\bm{w}_{n})\odot\nabla L_{D,\mathcal{R}_{n}}(\bm{w}_{n})$
(Heusel et al., 2017) | $\bm{v}_{n}^{G}=\beta_{2}^{G}\bm{v}_{n-1}^{G}+(1-\beta_{2}^{G})\bm{p}_{n}^{G}$ | $\bm{v}_{n}^{D}=\beta_{2}^{D}\bm{v}_{n-1}^{D}+(1-\beta_{2}^{D})\bm{p}_{n}^{D}$
(Kingma & Ba, 2015) | $\bar{\bm{v}}_{n}^{G}=\frac{\bm{v}_{n}^{G}}{1-\beta_{2}^{G^{n}}}$ | $\bar{\bm{v}}_{n}^{D}=\frac{\bm{v}_{n}^{D}}{1-\beta_{2}^{D^{n}}}$
($v_{n,i}^{G}\leq v_{n+1,i}^{G}$) | $\mathsf{H}_{n}^{G}=\mathsf{diag}(\sqrt{\bar{v}_{n,i}^{G}})$ | $\mathsf{H}_{n}^{D}=\mathsf{diag}(\sqrt{\bar{v}_{n,i}^{D}})$
($v_{n,i}^{D}\leq v_{n+1,i}^{D}$) |  |
($\gamma^{G}=\gamma^{D}=\beta_{1}^{G}=\beta_{1}^{D}$) |  |
AMSGrad (Reddi et al., 2018) | $\bm{p}_{n}^{G}=\nabla L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})\odot\nabla L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})$ | $\bm{p}_{n}^{D}=\nabla L_{D,\mathcal{R}_{n}}(\bm{w}_{n})\odot\nabla L_{D,\mathcal{R}_{n}}(\bm{w}_{n})$
(Chen et al., 2019) | $\bm{v}_{n}^{G}=\beta_{2}^{G}\bm{v}_{n-1}^{G}+(1-\beta_{2}^{G})\bm{p}_{n}^{G}$ | $\bm{v}_{n}^{D}=\beta_{2}^{D}\bm{v}_{n-1}^{D}+(1-\beta_{2}^{D})\bm{p}_{n}^{D}$
($\gamma^{G}=\gamma^{D}=0$) | $\hat{\bm{v}}_{n}^{G}=(\max\\{\hat{v}_{n-1,i}^{G},v_{n,i}^{G}\\})_{i=1}^{\Theta}$ | $\hat{\bm{v}}_{n}^{D}=(\max\\{\hat{v}_{n-1,i}^{D},v_{n,i}^{D}\\})_{i=1}^{W}$
| $\mathsf{H}_{n}^{G}=\mathsf{diag}(\sqrt{\hat{v}_{n,i}^{G}})$ | $\mathsf{H}_{n}^{D}=\mathsf{diag}(\sqrt{\hat{v}_{n,i}^{D}})$
AdaBelief | $\tilde{\bm{p}}_{n}^{G}=\nabla L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})-\bm{m}_{n}^{G}$ | $\tilde{\bm{p}}_{n}^{D}=\nabla L_{D,\mathcal{R}_{n}}(\bm{w}_{n})-\bm{m}_{n}^{D}$
(Zhuang et al., 2020) | $\tilde{\bm{s}}_{n}^{G}=\tilde{\bm{p}}_{n}^{G}\odot\tilde{\bm{p}}_{n}^{G}$ | $\tilde{\bm{s}}_{n}^{D}=\tilde{\bm{p}}_{n}^{D}\odot\tilde{\bm{p}}_{n}^{D}$
($s_{n,i}^{G}\leq s_{n+1,i}^{G}$) | $\bm{s}_{n}^{G}=\beta_{2}^{G}\bm{v}_{n-1}^{G}+(1-\beta_{2}^{G})\tilde{\bm{s}}_{n}^{G}$ | $\bm{s}_{n}^{D}=\beta_{2}^{D}\bm{v}_{n-1}^{D}+(1-\beta_{2}^{D})\tilde{\bm{s}}_{n}^{D}$
($s_{n,i}^{D}\leq s_{n+1,i}^{D}$) | $\hat{\bm{s}}_{n}^{G}=\frac{\bm{s}_{n}^{G}}{1-\beta_{2}^{G^{n}}}$ | $\hat{\bm{s}}_{n}^{D}=\frac{\bm{s}_{n}^{D}}{1-\beta_{2}^{D^{n}}}$
($\gamma^{G}=\gamma^{D}=\beta_{1}^{G}=\beta_{1}^{D}$) | $\mathsf{H}_{n}^{G}=\mathsf{diag}(\sqrt{\hat{s}_{n,i}^{G}})$ | $\mathsf{H}_{n}^{D}=\mathsf{diag}(\sqrt{\hat{s}_{n,i}^{D}})$

###  A.2 Hyperparameters of optimizers

Table 5: Hyperparameters of the optimizer used in the experiments in Sections 4.1, 4.2, and 4.3. | optimizer | $\alpha^{D}$ | $\alpha^{G}$ | $\beta_{1}^{G}=\beta_{1}^{D}$ | $\beta_{2}^{G}=\beta_{2}^{D}$ |  $\beta_{1}$ and $\beta_{2}$’s reference
---|---|---|---|---|---|---
| Adam | $0.0003$ | $0.0001$ | $0.5$ | $0.999$ | (Radford et al., 2016)
Section 4.1 | AdaBelief | $0.00003$ | $0.0003$ | $0.5$ | $0.999$ | (Zhuang et al., 2020)
| RMSProp | $0.00003$ | $0.0001$ | $0$ | $0.99$ |
| Adam | $0.0003$ | $0.0001$ | $0.5$ | $0.999$ | (Gulrajani et al., 2017)
Section 4.2 | AdaBelief | $0.00003$ | $0.0005$ | $0.5$ | $0.999$ | (Zhuang et al., 2020)
| RMSProp | $0.0001$ | $0.0003$ | $0$ | $0.99$ |
Section 4.3 | Adam | $0.0004$ | $0.0001$ | $0$ | $0.999$ | (Brock et al., 2019)
| AdaBelief | $0.0005$ | $0.00005$ | $0.5$ | $0.999$ |

###  A.3 Grid search

The combinations of learning rates used in the experiments in Sections 4.1 and
4.2 are determined using a grid search. Figure 7 shows the results of the grid
search.

---
Figure 7: Analysis of the relationship between combination of learning rates
and FID score: discriminator learning rate $\alpha^{D}$ on the vertical axis
and generator learning rate $\alpha^{G}$ on the horizontal axis. The heatmap
colors denote the FID scores; the darker the blue, the lower the FID, meaning
that the training of the generator succeeded.

###  A.4 FID decreases sufficiently

We measured the number of steps required to achieve a good FID with different
batch sizes. To demonstrate the soundness of the model used in the
experiments, Figure 8 shows the decrease in FID. We find that, with DCGAN on
the LSUN-Bedroom dataset, the FID score decreases to $41.8$, and with WGAN-GP
on the CelebA dataset, it decreases to $24.8$.

---
Figure 8: Mean FID (solid line) bounded by the maximum and the minimum over 5
runs (shaded area) for DCGAN on the LSUN-Bedroom dataset and WGAN-GP on the
CelebA dataset for three optimizers. For all runs, the batch size is 64 and
the learning rate combinations are determined with the same grid search (see
Figure 7) used in Sections 4.1 and 4.2.

###  A.5 Lemmas

######  Lemma A.1.

Suppose that (S1), (S2)(i), and (S3) hold and consider Algorithm 1. Then, for
all $\bm{\theta}\in\mathbb{R}^{\Theta}$ and all $n\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\|\bm{\theta}_{n+1}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\|\bm{\theta}_{n}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}\right]+\alpha_{n}^{G^{2}}\mathbb{E}\left[\|\bm{d}_{n}^{G}\|_{\mathsf{H}_{n}^{G}}^{2}\right]$
$\displaystyle\quad+2\alpha_{n}^{G}\left\\{\frac{\beta_{1}^{G}}{\tilde{\gamma}_{n}^{G}}\mathbb{E}\left[\langle\bm{\theta}-\bm{\theta}_{n},\bm{m}_{n-1}^{G}\rangle\right]+\frac{\tilde{\beta_{1}^{G}}}{\tilde{\gamma}_{n}^{G}}\mathbb{E}\left[\langle\bm{\theta}-\bm{\theta}_{n},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\right\\},$

where $\tilde{\beta_{1}^{G}}:=1-\beta_{1}^{G}$ and
$\tilde{\gamma}_{n}^{G}:=1-\gamma^{G^{n+1}}$.

###### Proof.

Let $\bm{\theta}\in\mathbb{R}^{\Theta}$ and $n\in\mathbb{N}$. The definition
of $\bm{\theta}_{n+1}$ implies that

$\displaystyle\|\bm{\theta}_{n+1}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}=\|\bm{\theta}_{n}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}+2\alpha_{n}^{G}\langle\bm{\theta}_{n}-\bm{\theta},\bm{d}_{n}^{G}\rangle_{\mathsf{H}_{n}^{G}}+\alpha_{n}^{G^{2}}\|\bm{d}_{n}^{G}\|_{\mathsf{H}_{n}^{G}}^{2}.$

Moreover, the definitions of $\bm{d}_{n}^{G}$, $\bm{m}_{n}^{G}$, and
$\hat{\bm{m}}_{n}^{G}$ ensure that

$\displaystyle\left\langle\bm{\theta}_{n}-\bm{\theta},\bm{d}_{n}^{G}\right\rangle_{\mathsf{H}_{n}^{G}}$
$\displaystyle=\frac{1}{{\tilde{\gamma}}_{n}^{G}}\langle\bm{\theta}-\bm{\theta}_{n},\bm{m}_{n}^{G}\rangle$
$\displaystyle=\frac{\beta_{1}^{G}}{{\tilde{\gamma}}_{n}^{G}}\langle\bm{\theta}-\bm{\theta}_{n},\bm{m}_{n-1}^{G}\rangle+\frac{\tilde{\beta_{1}^{G}}}{{\tilde{\gamma}}_{n}^{G}}\langle\bm{\theta}-\bm{\theta}_{n},\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})\rangle.$

Hence,

$\displaystyle\begin{split}\left\|\bm{\theta}_{n+1}-\bm{\theta}\right\|_{\mathsf{H}_{n}^{G}}^{2}&=\left\|\bm{\theta}_{n}-\bm{\theta}\right\|_{\mathsf{H}_{n}^{G}}^{2}+\alpha_{n}^{G^{2}}\|\bm{d}_{n}^{G}\|_{\mathsf{H}_{n}^{G}}^{2}\\\
&\quad+2\alpha_{n}^{G}\left\\{\frac{\beta_{1}^{G}}{{\tilde{\gamma}}_{n}^{G}}\langle\bm{\theta}-\bm{\theta}_{n},\bm{m}_{n-1}^{G}\rangle+\frac{\tilde{\beta_{1}^{G}}}{{\tilde{\gamma}}_{n}^{G}}\langle\bm{\theta}-\bm{\theta}_{n},\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})\rangle\right\\}.\end{split}$ (9)

Conditions (S2)(i) and (S3) guarantee that

$\displaystyle\mathbb{E}\left[\mathbb{E}\left[\langle\bm{\theta}-\bm{\theta}_{n},\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})\rangle\Big{|}\bm{\theta}_{n}\right]\right]$
$\displaystyle=\mathbb{E}\left[\left\langle\bm{\theta}-\bm{\theta}_{n},\mathbb{E}\left[\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})\Big{|}\bm{\theta}_{n}\right]\right\rangle\right]$
$\displaystyle=\mathbb{E}\left[\langle\bm{\theta}-\bm{\theta}_{n},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right].$

The lemma follows by taking the expectation with respect to $\xi_{n}^{G}$ on
both sides of (9). ∎

A discussion similar to the one proving Lemma A.1 leads to the following
lemma.

######  Lemma A.2.

Suppose that (S1), (S2)(i), and (S3) hold and consider Algorithm 1. Then, for
all $\bm{w}\in\mathbb{R}^{W}$ and all $n\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\|\bm{w}_{n+1}-\bm{w}\|_{\mathsf{H}_{n}^{D}}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\|\bm{w}_{n}-\bm{w}\|_{\mathsf{H}_{n}^{D}}^{2}\right]+\alpha_{n}^{D^{2}}\mathbb{E}\left[\|\bm{d}_{n}^{D}\|_{\mathsf{H}_{n}^{D}}^{2}\right]$
$\displaystyle\quad+2\alpha_{n}^{D}\left\\{\frac{\beta_{1}^{D}}{\tilde{\gamma}_{n}^{D}}\mathbb{E}\left[\langle\bm{w}-\bm{w}_{n},\bm{m}_{n-1}^{D}\rangle\right]+\frac{\tilde{\beta_{1}^{D}}}{\tilde{\gamma}_{n}^{D}}\mathbb{E}\left[\langle\bm{w}-\bm{w}_{n},\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\right\\},$

where $\tilde{\beta_{1}^{D}}:=1-\beta_{1}^{D}$ and
$\tilde{\gamma}_{n}^{D}:=1-\gamma^{D^{n+1}}$.

######  Lemma A.3.

Algorithm 1 satisfies that, under (S2)(i), (ii) and (C2), for all
$n\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\|\bm{m}_{n}^{G}\|^{2}\right]\leq\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}.$

Under (A1) and (C2), for all $k\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\|\bm{d}_{n}^{G}\|_{\mathsf{H}_{n}^{G}}^{2}\right]\leq\frac{1}{(1-{\gamma^{G}})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right),$

where $h_{0,*}^{G}:=\min_{i\in[\Theta]}h_{0,i}^{G}$.

###### Proof.

Let $n\in\mathbb{N}$. From (S2)(i), we have

$\displaystyle\mathbb{E}\left[\|\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})\|^{2}\big{|}\bm{\theta}_{n}\right]$
$\displaystyle=\mathbb{E}\left[\|\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})-\nabla
L_{G}(\bm{\theta}_{n},\bm{w}_{n})+\nabla
L_{G}(\bm{\theta}_{n},\bm{w}_{n})\|^{2}\big{|}\bm{\theta}_{n}\right]$
$\displaystyle=\mathbb{E}\left[\|\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})-\nabla
L_{G}(\bm{\theta}_{n},\bm{w}_{n})\|^{2}\big{|}\bm{\theta}_{n}\right]+\mathbb{E}\left[\|\nabla
L_{G}(\bm{\theta}_{n},\bm{w}_{n})\|^{2}\big{|}\bm{\theta}_{n}\right]$
$\displaystyle\quad+2\mathbb{E}\left[\langle\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})-\nabla
L_{G}(\bm{\theta}_{n},\bm{w}_{n}),\nabla
L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\Big{|}\bm{\theta}_{n}\right]$
$\displaystyle=\mathbb{E}\left[\|\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})-\nabla
L_{G}(\bm{\theta}_{n},\bm{w}_{n})\|^{2}\big{|}\bm{\theta}_{n}\right]+\|\nabla
L_{G}(\bm{\theta}_{n},\bm{w}_{n})\|^{2},$

which, together with (S2)(ii) and (C2), implies that

$\displaystyle\mathbb{E}\left[\|\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})\|^{2}\right]\leq\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}.$
(10)

The convexity of $\|\cdot\|^{2}$, together with the definition of
$\bm{m}_{n}^{G}$ and (10), guarantees that, for all $n\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\|\bm{m}_{n}^{G}\|^{2}\right]$
$\displaystyle\leq\beta_{1}^{G}\mathbb{E}\left[\|\bm{m}_{n-1}^{G}\|^{2}\right]+(1-\beta_{1}^{G})\mathbb{E}\left[\|\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})\|^{2}\right]$
$\displaystyle\leq\beta_{1}^{G}\mathbb{E}\left[\|\bm{m}_{n-1}^{G}\|^{2}\right]+(1-\beta_{1}^{G})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right).$

Induction thus ensures that, for all $n\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\|\bm{m}_{n}^{G}\|^{2}\right]\leq\max\left\\{\|\bm{m}_{-1}^{G}\|^{2},\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right\\}=\frac{\sigma_{G}^{2}}{b}+M_{G}^{2},$
(11)

where $\bm{m}_{-1}^{G}=\bm{0}$ is used. For $n\in\mathbb{N}$,
$\mathsf{H}_{n}^{G}\in\mathbb{S}_{++}^{\Theta}$ guarantees the existence of a
unique matrix $\overline{\mathsf{H}}_{n}^{G}\in\mathbb{S}_{++}^{\Theta}$ such
that $\mathsf{H}_{n}^{G}=\overline{\mathsf{H}}_{n}^{G^{2}}$ (Horn & Johnson,
1985, Theorem 7.2.6). We have that, for all $\bm{x}\in\mathbb{R}^{\Theta}$,
$\|\bm{x}\|_{\mathsf{H}_{n}^{G}}^{2}=\|\overline{\mathsf{H}}_{n}^{G}\bm{x}\|^{2}$.
Accordingly, the definitions of $\bm{d}_{n}^{G}$ and $\hat{\bm{m}}_{n}^{G}$
imply that, for all $n\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\|\bm{d}_{n}^{G}\|_{\mathsf{H}_{n}^{G}}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left\|\overline{\mathsf{H}}_{n}^{G^{-1}}\mathsf{H}_{n}^{G}\bm{d}_{n}^{G}\right\|^{2}\right]\leq\frac{1}{{\tilde{\gamma}}_{n}^{G^{2}}}\mathbb{E}\left[\left\|\overline{\mathsf{H}}_{n}^{G^{-1}}\right\|^{2}\|\bm{m}_{n}^{G}\|^{2}\right]$
$\displaystyle\leq\frac{1}{(1-\gamma^{G})^{2}}\mathbb{E}\left[\left\|\overline{\mathsf{H}}_{n}^{G^{-1}}\right\|^{2}\|\bm{m}_{n}^{G}\|^{2}\right],$

where

$\displaystyle\left\|\overline{\mathsf{H}}_{n}^{G^{-1}}\right\|=\left\|\mathsf{diag}\left(h_{n,i}^{G^{-\frac{1}{2}}}\right)\right\|={\max_{i\in[\Theta]}h_{n,i}^{G^{-\frac{1}{2}}}}$

and ${\tilde{\gamma}}_{n}^{G}:=1-{\gamma}^{G^{n+1}}\geq 1-{\gamma}^{G}$.
Moreover, (A1) ensures that, for all $n\in\mathbb{N}$,

$\displaystyle h_{n,i}^{G}\geq h_{0,i}^{G}\geq
h_{0,*}^{G}:=\min_{i\in[\Theta]}h_{0,i}^{G}.$

Hence, (11) implies that, for all $k\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\|\bm{d}_{n}^{G}\|_{\mathsf{H}_{n}^{G}}^{2}\right]\leq\frac{1}{(1-{\gamma}^{G})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right),$

completing the proof. ∎

A discussion similar to the one proving Lemma A.3 leads to the following
lemma.

######  Lemma A.4.

Algorithm 1 satisfies that, under (S2)(i), (ii) and (C2), for all
$n\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\|\bm{m}_{n}^{D}\|^{2}\right]\leq\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}.$

Under (A1) and (C2), for all $k\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\|\bm{d}_{n}^{D}\|_{\mathsf{H}_{n}^{D}}^{2}\right]\leq\frac{1}{(1-{\gamma^{D}})^{2}h_{0,*}^{D}}\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right),$

where $h_{0,*}^{D}:=\min_{i\in[W]}h_{0,i}^{D}$.

Lemmas A.1 and A.3 lead to the following:

######  Lemma A.5.

Suppose that (S1)–(S3), (A1), and (C2)–(C3) hold and define
$X_{n}^{G}(\bm{\theta}):=\mathbb{E}[\|\bm{\theta}_{n}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}]$
for all $n\in\mathbb{N}$ and all $\bm{\theta}\in\mathbb{R}^{\Theta}$. Then,
for all $\bm{\theta}\in\mathbb{R}^{\Theta}$ and all $n\in\mathbb{N}$,

$\displaystyle X_{n+1}^{G}(\bm{\theta})$ $\displaystyle\leq
X_{n}^{G}(\bm{\theta})+\mathrm{Dist}(\bm{\theta})\mathbb{E}\left[\sum_{i\in[\Theta]}(h_{n+1,i}^{G}-h_{n,i}^{G})\right]+\frac{\alpha_{n}^{G^{2}}}{(1-{\gamma^{G}})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)$
$\displaystyle\quad+2\alpha_{n}^{G}\left\\{\frac{\beta_{1}^{G}}{\tilde{\gamma}_{n}^{G}}\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}+\frac{\tilde{\beta_{1}^{G}}}{\tilde{\gamma}_{n}^{G}}\mathbb{E}\left[\langle\bm{\theta}-\bm{\theta}_{n},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\right\\}.$

###### Proof.

Lemma A.3 and Jensen’s inequality guarantee that

$\displaystyle\mathbb{E}\left[\|\bm{m}_{n}^{G}\|\right]\leq\sqrt{\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}}.$

Condition (C3) implies that, for all $\bm{\theta}\in\mathbb{R}^{\Theta}$,

$\displaystyle\|\bm{\theta}_{n}-\bm{\theta}\|^{2}=\sum_{i\in[\Theta]}(\theta_{n,i}-\theta_{i})^{2}\leq\Theta\mathrm{Dist}(\bm{\theta}).$

The Cauchy-Schwarz inequality thus ensures that

$\displaystyle\mathbb{E}\left[\langle\bm{\theta}-\bm{\theta}_{n},\bm{m}_{n-1}^{G}\rangle\right]\leq\mathbb{E}\left[\|\bm{\theta}-\bm{\theta}_{n}\|\|\bm{m}_{n-1}^{G}\|\right]\leq\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}.$
(12)

We define
$X_{n}^{G}(\bm{\theta}):=\mathbb{E}[\|\bm{\theta}_{n}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}]$
for all $n\in\mathbb{N}$ and all $\bm{\theta}\in\mathbb{R}^{\Theta}$. Then, we
have

$\displaystyle
X_{n+1}^{G}(\bm{\theta})-\mathbb{E}\left[\|\bm{\theta}_{n+1}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}\right]=\mathbb{E}\left[\sum_{i\in[\Theta]}(h_{n+1,i}^{G}-h_{n,i}^{G})(\theta_{n+1,i}-\theta_{i})^{2}\right],$

which, together with (C3), implies that

$\displaystyle
X_{n+1}^{G}(\bm{\theta})-\mathbb{E}\left[\|\bm{\theta}_{n+1}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}\right]\leq\mathrm{Dist}(\bm{\theta})\mathbb{E}\left[\sum_{i\in[\Theta]}(h_{n+1,i}^{G}-h_{n,i}^{G})\right].$

Hence, Lemmas A.1 and A.3 lead to the assertion in Lemma A.5. ∎

A discussion similar to the one proving Lemma A.5, together with Lemmas A.2
and A.4, leads to the following lemma.

######  Lemma A.6.

Suppose that (S1)–(S3), (A1), and (C2)–(C3) hold and define
$X_{n}^{D}(\bm{w}):=\mathbb{E}[\|\bm{w}_{n}-\bm{w}\|_{\mathsf{H}_{n}^{D}}^{2}]$
for all $n\in\mathbb{N}$ and all $\bm{w}\in\mathbb{R}^{W}$. Then, for all
$\bm{w}\in\mathbb{R}^{W}$ and all $n\in\mathbb{N}$,

$\displaystyle X_{n+1}^{D}(\bm{w})$ $\displaystyle\leq
X_{n}^{D}(\bm{w})+\mathrm{Dist}(\bm{w})\mathbb{E}\left[\sum_{i\in[W]}(h_{n+1,i}^{D}-h_{n,i}^{D})\right]+\frac{\alpha_{n}^{D^{2}}}{(1-{\gamma^{D}})^{2}h_{0,*}^{D}}\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)$
$\displaystyle\quad+2\alpha_{n}^{D}\left\\{\frac{\beta_{1}^{D}}{\tilde{\gamma}_{n}^{D}}\sqrt{W\mathrm{Dist}(\bm{w})\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)}+\frac{\tilde{\beta_{1}^{D}}}{\tilde{\gamma}_{n}^{D}}\mathbb{E}\left[\langle\bm{w}-\bm{w}_{n},\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\right\\}.$

###  A.6 Proof of Theorem 3.1(i)

The following is a convergence analysis of Algorithm 1.

######  Theorem A.1.

Suppose that Assumptions 2.1, 2.2, and 3.1 hold and consider the sequence
$((\bm{\theta}_{n},\bm{w}_{n}))_{n\in\mathbb{N}}$ generated by Algorithm 1.
Then, the following hold: For all $\bm{\theta}\in\mathbb{R}^{\Theta}$ and all
$\bm{w}\in\mathbb{R}^{W}$,

$\displaystyle\liminf_{n\to+\infty}\mathbb{E}\left[\langle\bm{\theta}_{n}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\leq\frac{\alpha^{G}(\sigma_{G}^{2}b^{-1}+M_{G}^{2})}{2\tilde{\beta_{1}^{G}}\tilde{\gamma}^{G^{2}}h_{0,*}^{G}}+\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}},$
$\displaystyle\liminf_{n\to+\infty}\mathbb{E}\left[\langle\bm{w}_{n}-\bm{w},\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\leq\frac{\alpha^{D}(\sigma_{D}^{2}b^{-1}+M_{D}^{2})}{2\tilde{\beta_{1}^{D}}\tilde{\gamma}^{D^{2}}h_{0,*}^{D}}+\sqrt{W\mathrm{Dist}(\bm{w})\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)}\frac{\beta_{1}^{D}}{\tilde{\beta_{1}^{D}}},$

where $\tilde{\beta_{1}^{G}}:=1-\beta_{1}^{G}$,
$\tilde{\beta_{1}^{D}}:=1-\beta_{1}^{D}$, $\tilde{\gamma}^{G}:=1-\gamma^{G}$,
$\tilde{\gamma}^{D}:=1-\gamma^{D}$,
$h_{0,*}^{G}:=\min_{i\in[\Theta]}h_{0,i}^{G}$, and
$h_{0,*}^{D}:=\min_{j\in[W]}h_{0,j}^{D}$. Furthermore, there exist
accumulation points $(\bm{\theta}^{*},\bm{w}^{*})$ and
$(\bm{\theta}_{*},\bm{w}_{*})$ of
$((\bm{\theta}_{n},\bm{w}_{n}))_{n\in\mathbb{N}}$ such that

$\displaystyle\mathbb{E}\left[\|\nabla_{\bm{\theta}}L_{G}(\bm{\theta}^{*},\bm{w}^{*})\|^{2}\right]\leq\frac{\alpha^{G}(\sigma_{G}^{2}b^{-1}+M_{G}^{2})}{2\tilde{\beta_{1}^{G}}\tilde{\gamma}^{G^{2}}h_{0,*}^{G}}+\sqrt{\Theta\mathrm{Dist}(\tilde{\bm{\theta}})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}},$
$\displaystyle\mathbb{E}\left[\|\nabla_{\bm{w}}L_{D}(\bm{\theta}_{*},\bm{w}_{*})\|^{2}\right]\leq\frac{\alpha^{D}(\sigma_{D}^{2}b^{-1}+M_{D}^{2})}{2\tilde{\beta_{1}^{D}}\tilde{\gamma}^{D^{2}}h_{0,*}^{D}}+\sqrt{W\mathrm{Dist}(\tilde{\bm{w}})\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)}\frac{\beta_{1}^{D}}{\tilde{\beta_{1}^{D}}},$

where
$\tilde{\bm{\theta}}:=\bm{\theta}^{*}-\nabla_{\bm{\theta}}L_{G}(\bm{\theta}^{*},\bm{w}^{*})$
and
$\tilde{\bm{w}}:=\bm{w}_{*}-\nabla_{\bm{w}}L_{D}(\bm{\theta}_{*},\bm{w}_{*})$.

###### Proof.

Let us assume (C1), i.e., $\alpha_{n}^{G}:=\alpha^{G}$ for all
$n\in\mathbb{N}$. Then, Lemma A.5 ensures that, for all
$\bm{\theta}\in\mathbb{R}^{\Theta}$ and all $n\in\mathbb{N}$,

$\displaystyle X_{n+1}^{G}(\bm{\theta})$ $\displaystyle\leq
X_{n}^{G}(\bm{\theta})+\mathrm{Dist}(\bm{\theta})\mathbb{E}\left[\sum_{i\in[\Theta]}(h_{n+1,i}^{G}-h_{n,i}^{G})\right]+\frac{\alpha^{G^{2}}}{(1-{\gamma^{G}})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)$
$\displaystyle\quad+2\alpha^{G}\left\\{\frac{\beta_{1}^{G}}{\tilde{\gamma}_{n}^{G}}\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}+\frac{\tilde{\beta_{1}^{G}}}{\tilde{\gamma}_{n}^{G}}\mathbb{E}\left[\langle\bm{\theta}-\bm{\theta}_{n},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\right\\}.$

Since we have that $\tilde{\gamma}_{n}^{G}=1-\gamma^{G^{n+1}}\leq 1$,
$\gamma^{G^{n+1}}(X_{n+1}^{G}(\bm{\theta})-X_{n}^{G}(\bm{\theta}))\leq\gamma^{G^{n+1}}X_{n+1}^{G}(\bm{\theta})$,
and $h_{n+1,i}^{G}\geq h_{n,i}^{G}$ (by (A1)) for all $n\in\mathbb{N}$, we
also have that

$\displaystyle\begin{split}X_{n+1}^{G}(\bm{\theta})&\leq
X_{n}^{G}(\bm{\theta})+\gamma^{G^{n+1}}X_{n+1}^{G}(\bm{\theta})+\mathrm{Dist}(\bm{\theta})\mathbb{E}\left[\sum_{i\in[\Theta]}(h_{n+1,i}^{G}-h_{n,i}^{G})\right]\\\
&\quad+\frac{\alpha^{G^{2}}}{(1-{\gamma^{G}})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)\\\
&\quad+2\alpha^{G}\left\\{\beta_{1}^{G}\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}+\tilde{\beta_{1}^{G}}\mathbb{E}\left[\langle\bm{\theta}-\bm{\theta}_{n},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\right\\}.\end{split}$
(13)

Let us show that, for all $\bm{\theta}\in\mathbb{R}^{\Theta}$ and all
$\epsilon>0$,

$\displaystyle\begin{split}&\liminf_{n\to+\infty}\mathbb{E}\left[\langle\bm{\theta}_{n}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\\\
&\leq\frac{\alpha^{G}}{2\tilde{\beta_{1}^{G}}(1-{\gamma^{G}})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)+\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}+\epsilon.\end{split}$
(14)

If (14) does not hold, then there exist
$\hat{\bm{\theta}}\in\mathbb{R}^{\Theta}$ and $\epsilon_{0}>0$ such that

$\displaystyle\liminf_{n\to+\infty}\mathbb{E}\left[\langle\bm{\theta}_{n}-\hat{\bm{\theta}},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
$\displaystyle>\frac{\alpha^{G}}{2\tilde{\beta_{1}^{G}}(1-{\gamma^{G}})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)+\sqrt{\Theta\mathrm{Dist}(\hat{\bm{\theta}})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}+\epsilon_{0}.$

Then, there exists $n_{0}\in\mathbb{N}$ such that, for all $n\geq n_{0}$,

$\displaystyle\mathbb{E}\left[\langle\bm{\theta}_{n}-\hat{\bm{\theta}},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
$\displaystyle>\frac{\alpha^{G}}{2\tilde{\beta_{1}^{G}}(1-{\gamma^{G}})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)+\sqrt{\Theta\mathrm{Dist}(\hat{\bm{\theta}})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}+\frac{\epsilon_{0}}{2}.$

Meanwhile, the conditions $\gamma^{G}\in[0,1)$, (C3), and (A1)–(A2) guarantee
that there exists $n_{1}\in\mathbb{N}$ such that, for all $n\geq n_{1}$,

$\displaystyle\gamma^{G^{n+1}}X_{n+1}^{G}(\hat{\bm{\theta}})+\mathrm{Dist}(\hat{\bm{\theta}})\mathbb{E}\left[\sum_{i\in[\Theta]}(h_{n+1,i}^{G}-h_{n,i}^{G})\right]\leq\frac{\alpha^{G}\tilde{\beta_{1}^{G}}\epsilon_{0}}{2}.$

Accordingly, from (13), for all $n\geq n_{2}:=\max\\{n_{0},n_{1}\\}$,

$\displaystyle X_{n+1}^{G}(\hat{\bm{\theta}})$
$\displaystyle<X_{n}^{G}(\hat{\bm{\theta}})+\frac{\alpha^{G}\tilde{\beta_{1}^{G}}\epsilon_{0}}{2}+\frac{\alpha^{G^{2}}}{(1-{\gamma^{G}})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)$
$\displaystyle\quad+2\alpha^{G}\beta_{1}^{G}\sqrt{\Theta\mathrm{Dist}(\hat{\bm{\theta}})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}-2\alpha^{G}\tilde{\beta_{1}^{G}}\Bigg{\\{}\frac{\alpha^{G}}{2\tilde{\beta_{1}^{G}}(1-{\gamma^{G}})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)$
$\displaystyle\quad+\sqrt{\Theta\mathrm{Dist}(\hat{\bm{\theta}})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}+\frac{\epsilon_{0}}{2}\Bigg{\\}}$
$\displaystyle=X_{n}^{G}(\hat{\bm{\theta}})-\frac{\alpha^{G}\tilde{\beta_{1}^{G}}\epsilon_{0}}{2}$
$\displaystyle<X_{n_{2}}^{G}(\hat{\bm{\theta}})-\frac{\alpha^{G}\tilde{\beta_{1}^{G}}\epsilon_{0}}{2}(n+1-n_{2}).$

Note that the right-hand side of the above inequality approaches minus
infinity as $n$ approaches positive infinity, producing a contradiction.
Therefore, (14) holds, which implies that, for all
$\bm{\theta}\in\mathbb{R}^{\Theta}$,

$\displaystyle\begin{split}&\liminf_{n\to+\infty}\mathbb{E}\left[\langle\bm{\theta}_{n}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\\\
&\quad\leq\frac{\alpha^{G}}{2\tilde{\beta_{1}^{G}}(1-{\gamma^{G}})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)+\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}.\end{split}$
(15)

A discussion similar to the one showing (15), together with Lemma A.6, leads
to the finding that, for all $\bm{w}\in\mathbb{R}^{W}$,

$\displaystyle\begin{split}&\liminf_{n\to+\infty}\mathbb{E}\left[\langle\bm{w}_{n}-\bm{w},\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]\\\
&\quad\leq\frac{\alpha^{D}}{2\tilde{\beta_{1}^{D}}(1-{\gamma^{D}})^{2}h_{0,*}^{D}}\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)+\sqrt{W\mathrm{Dist}(\bm{w})\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)}\frac{\beta_{1}^{D}}{\tilde{\beta_{1}^{D}}}.\end{split}$
(16)

Let $\bm{\theta}\in\mathbb{R}^{\Theta}$. From (15), there exists a subsequence
$((\bm{\theta}_{n_{i}},\bm{w}_{n_{i}}))_{i\in\mathbb{N}}$ of
$((\bm{\theta}_{n},\bm{w}_{n}))_{n\in\mathbb{N}}$ such that

$\displaystyle\lim_{i\to+\infty}\mathbb{E}\left[\langle\bm{\theta}_{n_{i}}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n_{i}},\bm{w}_{n_{i}})\rangle\right]$
$\displaystyle\quad\leq\frac{\alpha^{G}}{2\tilde{\beta_{1}^{G}}(1-{\gamma^{G}})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)+\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}.$

Conditions (S1) and (C3) guarantee that there exists
$((\bm{\theta}_{n_{i_{j}}},\bm{w}_{n_{i_{j}}}))_{j\in\mathbb{N}}$ of
$((\bm{\theta}_{n_{i}},\bm{w}_{n_{i}}))_{i\in\mathbb{N}}$ such that
$((\bm{\theta}_{n_{i_{j}}},\bm{w}_{n_{i_{j}}}))_{j\in\mathbb{N}}$ converges
almost surely to
$(\bm{\theta}^{*},\bm{w}^{*})\in\mathbb{R}^{\Theta}\times\mathbb{R}^{W}$.
Therefore, for all $\bm{\theta}\in\mathbb{R}^{\Theta}$,

$\displaystyle\mathbb{E}\left[\langle\bm{\theta}^{*}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}^{*},\bm{w}^{*})\rangle\right]$
$\displaystyle\quad\leq\frac{\alpha^{G}}{2\tilde{\beta_{1}^{G}}(1-{\gamma^{G}})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)+\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}.$

Hence, letting
$\bm{\theta}=\tilde{\bm{\theta}}:=\bm{\theta}^{*}-\nabla_{\bm{\theta}}L_{G}(\bm{\theta}^{*},\bm{w}^{*})$
implies that

$\displaystyle\begin{split}&\mathbb{E}\left[\|\nabla_{\bm{\theta}}L_{G}(\bm{\theta}^{*},\bm{w}^{*})\|^{2}\right]\\\
&\quad\leq\frac{\alpha^{G}}{2\tilde{\beta_{1}^{G}}(1-{\gamma^{G}})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)+\sqrt{\Theta\mathrm{Dist}(\tilde{\bm{\theta}})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}.\end{split}$
(17)

A discussion similar to the one showing (17), together with (16), implies that
there exists
$(\bm{\theta}_{*},\bm{w}_{*})\in\mathbb{R}^{\Theta}\times\mathbb{R}^{W}$ such
that

$\displaystyle\mathbb{E}\left[\|\nabla_{\bm{w}}L_{D}(\bm{\theta}_{*},\bm{w}_{*})\|^{2}\right]$
$\displaystyle\quad\leq\frac{\alpha^{D}}{2\tilde{\beta_{1}^{D}}(1-{\gamma^{D}})^{2}h_{0,*}^{D}}\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)+\sqrt{W\mathrm{Dist}(\tilde{\bm{w}})\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)}\frac{\beta_{1}^{D}}{\tilde{\beta_{1}^{D}}},$

where
$\tilde{\bm{w}}=\bm{w}_{*}-\nabla_{\bm{w}}L_{D}(\bm{\theta}_{*},\bm{w}_{*})$.
This completes the proof. ∎

###  A.7 Proof of Theorem 3.1(ii)

Lemmas A.1 and A.3 lead to the following lemma:

######  Lemma A.7.

Suppose that (S1)–(S3), (A1)–(A2), and (C2)–(C3) hold and consider Algorithm
1, where $(\alpha_{n}^{G})_{n\in\mathbb{N}}$ is monotone decreasing. Then, for
all $\bm{\theta}\in\mathbb{R}^{\Theta}$ and all $N\geq 1$,

$\displaystyle\frac{1}{N}\sum_{n\in[N]}\mathbb{E}\left[\langle\bm{\theta}_{n}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
$\displaystyle\quad\leq\frac{\Theta\mathrm{Dist}(\bm{\theta})H^{G}}{2\alpha_{N}^{G}\tilde{\beta_{1}^{G}}N}+\frac{1}{N}\sum_{n\in[N]}\frac{\alpha_{n}^{G}}{2\tilde{\beta_{1}^{G}}(1-{\gamma}^{G})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)+\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)},$

where $H^{G}:=\max_{i\in[\Theta]}H_{i}^{G}$.

###### Proof.

Lemma A.1 implies that, for all $\bm{\theta}\in\mathbb{R}^{\Theta}$ and all
$n\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\langle\bm{\theta}_{n}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
$\displaystyle=\frac{\tilde{\gamma}_{n}^{G}}{2\alpha_{n}^{G}\tilde{\beta_{1}^{G}}}\left\\{\mathbb{E}\left[\|\bm{\theta}_{n}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}\right]-\mathbb{E}\left[\|\bm{\theta}_{n+1}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}\right]\right\\}+\frac{\alpha_{n}^{G}\tilde{\gamma}_{n}^{G}}{2\tilde{\beta_{1}^{G}}}\mathbb{E}\left[\|\bm{d}_{n}^{G}\|_{\mathsf{H}_{n}^{G}}^{2}\right]+\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}\mathbb{E}\left[\langle\bm{\theta}-\bm{\theta}_{n},\bm{m}_{n-1}^{G}\rangle\right],$

which implies that, for all $\bm{\theta}\in\mathbb{R}^{\Theta}$ and all $N\geq
1$,

$\displaystyle\frac{1}{N}\sum_{n\in[N]}\mathbb{E}\left[\langle\bm{\theta}_{n}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
$\displaystyle=\frac{1}{N}\underbrace{\sum_{n\in[N]}\frac{\tilde{\gamma}_{n}^{G}}{2\alpha_{n}^{G}\tilde{\beta_{1}^{G}}}\left\\{\mathbb{E}\left[\|\bm{\theta}_{n}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}\right]-\mathbb{E}\left[\|\bm{\theta}_{n+1}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}\right]\right\\}}_{\Theta_{N}}+\frac{1}{N}\underbrace{\sum_{n\in[N]}\frac{\alpha_{n}^{G}\tilde{\gamma}_{n}^{G}}{2\tilde{\beta_{1}^{G}}}\mathbb{E}\left[\|\bm{d}_{n}^{G}\|_{\mathsf{H}_{n}^{G}}^{2}\right]}_{A_{N}}$
$\displaystyle\quad+\frac{1}{N}\underbrace{\sum_{n\in[N]}\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}\mathbb{E}\left[\langle\bm{\theta}-\bm{\theta}_{n},\bm{m}_{n-1}^{G}\rangle\right]}_{B_{N}}.$

Let
$\delta_{n}^{G}:=\tilde{\gamma}_{n}^{G}/(2\alpha_{n}^{G}\tilde{\beta_{1}^{G}})$
for all $n\in\mathbb{N}$. Then, we have that

$\displaystyle\Theta_{N}$
$\displaystyle:=\delta_{1}^{G}\mathbb{E}\left[\|\bm{\theta}_{1}-\bm{\theta}\|_{\mathsf{H}_{1}^{G}}^{2}\right]+\underbrace{\sum_{n=2}^{N}\left\\{\delta_{n}^{G}\mathbb{E}\left[\|\bm{\theta}_{n}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}\right]-\delta_{n-1}^{G}\mathbb{E}\left[\|\bm{\theta}_{n}-\bm{\theta}\|_{\mathsf{H}_{n-1}^{G}}^{2}\right]\right\\}}_{\tilde{\Theta}_{N}}$
$\displaystyle\quad-\delta_{N}^{G}\mathbb{E}\left[\|\bm{\theta}_{N+1}-\bm{\theta}\|_{\mathsf{H}_{N}^{G}}^{2}\right].$

Since $\overline{\mathsf{H}}_{n}^{G}\in\mathbb{S}_{++}^{\Theta}$ exists such
that $\mathsf{H}_{n}^{G}=\overline{\mathsf{H}}_{n}^{G^{2}}$, we have
$\|\bm{x}\|_{\mathsf{H}_{n}^{G}}^{2}=\|\overline{\mathsf{H}}_{n}^{G}\bm{x}\|^{2}$
for all $\bm{x}\in\mathbb{R}^{\Theta}$. Accordingly, we have

$\displaystyle\tilde{\Theta}_{N}=\mathbb{E}\left[\sum_{n=2}^{N}\left\\{\delta_{n}^{G}\left\|\overline{\mathsf{H}}_{n}^{G}(\bm{\theta}_{n}-\bm{\theta})\right\|^{2}-\delta_{n-1}^{G}\left\|\overline{\mathsf{H}}_{n-1}^{G}(\bm{\theta}_{n}-\bm{\theta})\right\|^{2}\right\\}\right].$

Hence, for all $N\geq 2$,

$\displaystyle\tilde{\Theta}_{N}=\mathbb{E}\left[\sum_{n=2}^{N}\sum_{i=1}^{\Theta}\left(\delta_{n}^{G}h_{n,i}^{G}-\delta_{n-1}^{G}h_{n-1,i}^{G}\right)(\theta_{n,i}-\theta_{i})^{2}\right].$
(18)

Since $(\alpha_{n}^{G})_{n\in\mathbb{N}}$ is monotone decreasing, we have that
$\delta_{n+1}^{G}\geq\delta_{n}^{G}$ ($n\in\mathbb{N}$). Hence, from (A1), we
have that, for all $n\geq 1$ and all $i\in[\Theta]$,

$\displaystyle\delta_{n}^{G}h_{n,i}^{G}-\delta_{n-1}^{G}h_{n-1,i}^{G}\geq 0.$

Moreover, from (C3),
$\max_{i\in[\Theta]}\sup_{n\in\mathbb{N}}(\theta_{n,i}-\theta_{i})^{2}\leq\mathrm{Dist}(\bm{\theta})$.
Accordingly, for all $N\geq 2$,

$\displaystyle\tilde{\Theta}_{N}$
$\displaystyle\leq\mathrm{Dist}(\bm{\theta})\mathbb{E}\left[\sum_{n=2}^{N}\sum_{i=1}^{\Theta}\left(\delta_{n}^{G}h_{n,i}^{G}-\delta_{n-1}^{G}h_{n-1,i}^{G}\right)\right]$
$\displaystyle=\mathrm{Dist}(\bm{\theta})\mathbb{E}\left[\sum_{i=1}^{\Theta}\left(\delta_{N}^{G}h_{N,i}^{G}-\delta_{1}^{G}h_{1,i}^{G}\right)\right].$

Therefore,
$\delta_{1}^{G}\mathbb{E}[\|\bm{\theta}_{1}-\bm{\theta}\|_{\mathsf{H}_{1}^{G}}^{2}]\leq\mathrm{Dist}(\bm{\theta})\delta_{1}^{G}\mathbb{E}[\sum_{i=1}^{\Theta}h_{1,i}^{G}]$,
and (A2) imply that, for all $N\geq 1$,

$\displaystyle\Theta_{N}$
$\displaystyle\leq\delta_{1}^{G}\mathrm{Dist}(\bm{\theta})\mathbb{E}\left[\sum_{i=1}^{\Theta}h_{1,i}^{G}\right]+\mathrm{Dist}(\bm{\theta})\mathbb{E}\left[\sum_{i=1}^{\Theta}\left(\delta_{N}^{G}h_{N,i}^{G}-\delta_{1}^{G}h_{1,i}^{G}\right)\right]$
$\displaystyle=\delta_{N}^{G}\mathrm{Dist}(\bm{\theta})\mathbb{E}\left[\sum_{i=1}^{\Theta}h_{N,i}^{G}\right]$
$\displaystyle\leq\delta_{N}^{G}\mathrm{Dist}(\bm{\theta})\sum_{i=1}^{\Theta}H_{i}^{G}$
$\displaystyle\leq\delta_{N}^{G}\Theta\mathrm{Dist}(\bm{\theta})H^{G},$

where $H^{G}=\max_{i\in[\Theta]}H_{i}^{G}$. From
$\delta_{n}^{G}:=\tilde{\gamma}_{n}^{G}/(2\alpha_{n}^{G}\tilde{\beta_{1}^{G}})$
and $\tilde{\gamma}_{n}^{G}=1-{\gamma}^{G^{n+1}}\leq 1$, we have

$\displaystyle\Theta_{N}\leq\frac{\Theta\mathrm{Dist}(\bm{\theta})H^{G}}{2\alpha_{N}^{G}\tilde{\beta_{1}^{G}}}.$
(19)

Lemma A.3 implies that, for all $N\geq 1$,

$\displaystyle
A_{N}:=\sum_{n\in[N]}\frac{\alpha_{n}^{G}\tilde{\gamma}_{n}^{G}}{2\tilde{\beta_{1}^{G}}}\mathbb{E}\left[\|\bm{d}_{n}^{G}\|_{\mathsf{H}_{n}^{G}}^{2}\right]\leq\sum_{n\in[N]}\frac{\alpha_{n}^{G}}{2\tilde{\beta_{1}^{G}}(1-{\gamma}^{G})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right).$
(20)

From (12), we have

$\displaystyle\begin{split}B_{N}&:=\sum_{n\in[N]}\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}\mathbb{E}\left[\langle\bm{\theta}-\bm{\theta}_{n},\bm{m}_{n-1}^{G}\rangle\right]\leq\frac{\beta_{1}^{G}N}{\tilde{\beta_{1}^{G}}}\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)}.\end{split}$
(21)

Therefore, (19), (20), and (21) lead to the assertion in Lemma A.7. This
completes the proof. ∎

A discussion similar to the one proving Lemma A.7, together with Lemmas A.2
and A.4, leads to the following lemma:

######  Lemma A.8.

Suppose that (S1)–(S3), (A1)–(A2), and (C2)–(C3) hold and consider Algorithm
1, where $(\alpha_{n}^{D})_{n\in\mathbb{N}}$ is monotone decreasing. Then, for
all $\bm{w}\in\mathbb{R}^{W}$ and all $N\geq 1$,

$\displaystyle\frac{1}{N}\sum_{n\in[N]}\mathbb{E}\left[\langle\bm{w}_{n}-\bm{w},\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
$\displaystyle\quad\leq\frac{W\mathrm{Dist}(\bm{w})H^{D}}{2\alpha_{N}^{D}\tilde{\beta_{1}^{D}}N}+\frac{1}{N}\sum_{n\in[N]}\frac{\alpha_{n}^{D}}{2\tilde{\beta_{1}^{D}}(1-{\gamma}^{D})^{2}h_{0,*}^{D}}\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)+\frac{\beta_{1}^{D}}{\tilde{\beta_{1}^{D}}}\sqrt{W\mathrm{Dist}(\bm{w})\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)},$

where $H^{D}:=\max_{j\in[W]}H_{j}^{D}$.

###### Proof of Theorem 3.1(ii).

Let $\alpha_{n}^{G}:=\alpha^{G}$ and $\alpha_{n}^{D}:=\alpha^{D}$ for all
$n\in\mathbb{N}$. Lemmas A.7 and A.8 thus guarantee that, for all
$\bm{\theta}\in\mathbb{R}^{\Theta}$ and all $N\geq 1$,

$\displaystyle\frac{1}{N}\sum_{n\in[N]}\mathbb{E}\left[\langle\bm{\theta}_{n}-\bm{\theta},\nabla_{\bm{\theta}}L_{G}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
$\displaystyle\quad\leq\frac{\Theta\mathrm{Dist}(\bm{\theta})H^{G}}{2\alpha^{G}\tilde{\beta_{1}^{G}}N}+\frac{\alpha^{G}}{2\tilde{\beta_{1}^{G}}(1-{\gamma}^{G})^{2}h_{0,*}^{G}}\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)+\frac{\beta_{1}^{G}}{\tilde{\beta_{1}^{G}}}\sqrt{\Theta\mathrm{Dist}(\bm{\theta})\left(\frac{\sigma_{G}^{2}}{b}+M_{G}^{2}\right)},$
$\displaystyle\frac{1}{N}\sum_{n\in[N]}\mathbb{E}\left[\langle\bm{w}_{n}-\bm{w},\nabla_{\bm{w}}L_{D}(\bm{\theta}_{n},\bm{w}_{n})\rangle\right]$
$\displaystyle\quad\leq\frac{W\mathrm{Dist}(\bm{w})H^{D}}{2\alpha^{D}\tilde{\beta_{1}^{D}}N}+\frac{\alpha^{D}}{2\tilde{\beta_{1}^{D}}(1-{\gamma}^{D})^{2}h_{0,*}^{D}}\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)+\frac{\beta_{1}^{D}}{\tilde{\beta_{1}^{D}}}\sqrt{W\mathrm{Dist}(\bm{w})\left(\frac{\sigma_{D}^{2}}{b}+M_{D}^{2}\right)},$

which completes the proof. ∎

###  A.8 Proof of Theorem 3.2

###### Proof of Theorem 3.2.

Condition (5) implies that TTUR achieves an $\epsilon$–approximation. We have
that, for $b>B_{G}/(\epsilon_{G}^{2}-C_{G})$,

$\displaystyle\frac{\mathrm{d}N_{G}(b)}{\mathrm{d}b}=\frac{-A_{G}B_{G}}{\\{(\epsilon_{G}^{2}-C_{G})b-B_{G}\\}^{2}}\leq
0,$
$\displaystyle\frac{\mathrm{d}^{2}N_{G}(b)}{\mathrm{d}b^{2}}=\frac{2A_{G}B_{G}(\epsilon_{G}^{2}-C_{G})}{\\{(\epsilon_{G}^{2}-C_{G})b-B_{G}\\}^{3}}\geq
0.$

Hence, $N_{G}$ is monotone decreasing and convex for
$b>B_{G}/(\epsilon_{G}^{2}-C_{G})$. We also have that $N_{D}$ is monotone
decreasing and convex for $b>B_{D}/(\epsilon_{D}^{2}-C_{D})$. This completes
the proof. ∎

###  A.9 Proof of Theorem 3.3

###### Proof of Theorem 3.3.

We have that, for $b>B_{G}/(\epsilon_{G}^{2}-C_{G})$,

$\displaystyle N_{G}(b)b=\frac{A_{G}b^{2}}{(\epsilon_{G}^{2}-C_{G})b-B_{G}}.$

Hence,

$\displaystyle\frac{\mathrm{d}N_{G}(b)b}{\mathrm{d}b}=\frac{A_{G}b\\{(\epsilon_{G}^{2}-C_{G})b-2B_{G}\\}}{\\{(\epsilon_{G}^{2}-C_{G})b-B_{G}\\}^{2}},$
$\displaystyle\frac{\mathrm{d}^{2}N_{G}(b)b}{\mathrm{d}b^{2}}=\frac{2A_{G}B_{G}^{2}}{\\{(\epsilon_{G}^{2}-C_{G})b-B_{G}\\}^{3}}\geq
0,$

which implies that $N_{G}(b)b$ is convex for
$b>B_{G}/(\epsilon_{G}^{2}-C_{G})$ and

$\displaystyle\frac{\mathrm{d}N_{G}(b)b}{\mathrm{d}b}\begin{cases}<0&\text{ if
}b<b_{G}^{\star},\\\ =0&\text{ if
}b=b_{G}^{\star}=\frac{2B_{G}}{\epsilon_{G}^{2}-C_{G}},\\\ >0&\text{ if
}b>b_{G}^{\star}.\end{cases}$

The point $b_{G}^{\star}$ attains the minimum value
$N_{G}(b_{G}^{\star})b_{G}^{\star}$ of $N_{G}(b)b$. The discussion for $N_{D}$
is similar to the one for $N_{G}$. This completes the proof. ∎

###  A.10 Proof of Proposition 3.4

Theorem 3.3 and the definitions of $B_{G}$, $C_{G}$, $\tilde{\beta_{1}^{G}}$
and $\tilde{\gamma}^{G}$ ensure that

$\displaystyle
b_{G}^{\star}=\frac{2B_{G}}{\epsilon_{G}^{2}-C_{G}}>\frac{2B_{G}}{\epsilon_{G}^{2}}=\frac{2}{\epsilon_{G}^{2}}\cdot\frac{\sigma_{G}^{2}\alpha^{G}}{2\tilde{\beta_{1}^{G}}\tilde{\gamma}^{G^{2}}h_{0,*}^{G}}=\frac{\sigma_{G}^{2}\alpha^{G}}{\epsilon_{G}^{2}(1-\beta_{1}^{G})(1-\gamma^{G})^{2}h_{0,*}^{G}}.$

Moreover, (10) and the definition of $L_{G}(\bm{\theta}_{n},\bm{w}_{n})$
ensure that

$\displaystyle\left\|\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})\right\|^{2}\leq\frac{\sigma_{G}^{2}}{b}+\left\|\nabla
L_{G}(\bm{\theta}_{n},\bm{w}_{n})\right\|^{2}\approx\left\|\nabla
L_{G}(\bm{\theta}_{n},\bm{w}_{n})\right\|^{2}=\frac{1}{|S|^{2}}\left\|\sum_{i=1}^{|S|}\nabla
L_{G}^{(i)}(\bm{\theta}_{n},\bm{w}_{n})\right\|^{2},$

where $\sigma_{G}^{2}/b\approx 0$ holds when $b$ is sufficiently large. We
define $\sum_{i=1}^{|S|}\nabla
L_{G}^{(i)}(\bm{\theta}_{n},\bm{w}_{n}):=\bm{G}_{n}$ for all $n\in\mathbb{N}$.
Then, we have

$\displaystyle\frac{1}{|S|^{2}}\left\|\sum_{i=1}^{|S|}\nabla
L_{G}^{(i)}(\bm{\theta}_{n},\bm{w}_{n})\right\|^{2}=\frac{1}{|S|^{2}}\sum_{i=1}^{\Theta}G_{n,i}^{2}\leq\frac{\Theta}{|S|^{2}}\max_{i\in[\Theta]}G_{n,i}^{2}.$

###### Proof of Proposition 3.4(i).

The definition of $\bm{v}_{n}^{G}$ implies that

$\displaystyle
v_{n,i}^{G}=\beta_{2}^{G}v_{n-1,i}^{G}+(1-\beta_{2}^{G})g_{n,i}^{2}\leq\max_{n,i}g_{n,i}^{2}=:g_{n^{*},i^{*}}^{2}\leq\sum_{i=1}^{\Theta}g_{n^{*},i}^{2}=\left\|\nabla
L_{G,\mathcal{S}_{n^{*}}}(\bm{\theta}_{n^{*}})\right\|^{2},$

where the first inequality can be shown by induction. Therefore, for all
$n\in\mathbb{N}$ and all $i\in[\Theta]$,

$\displaystyle
v_{n,i}^{G}\leq\frac{\Theta}{|S|^{2}}\max_{i\in[\Theta]}G_{n^{*},i}^{2}.$

From the definition of $\bar{v}_{n,i}^{G}$ and $\beta_{2}\in[0,1)$, we have

$\displaystyle
h_{0,*}^{G}:=\min_{i\in[\Theta]}h_{0,i}^{G}\leq\sqrt{\bar{v}_{n,i}^{G}}=\sqrt{\frac{v_{n,i}^{G}}{1-{\beta_{2}^{G}}^{n}}}\leq\sqrt{\frac{v_{n,i}^{G}}{1-\beta_{2}^{G}}}.$

Hence,

$\displaystyle
b_{G}^{\star}\geq\frac{\sigma_{G}^{2}\alpha^{G}}{\epsilon_{G}^{2}(1-\beta_{1}^{G})(1-\gamma^{G})^{2}\sqrt{\frac{\Theta}{1-\beta_{2}^{G}}\frac{1}{|S|^{2}}\max_{i\in[\Theta]}G_{n^{*},i}^{2}}}.$

Accordingly, using $\gamma^{G}=\beta_{1}^{G}$ and
$\max_{i\in[\Theta]}G_{n^{*},i}^{2}\approx\epsilon_{G}^{2}$ implies that

$\displaystyle
b_{G}^{\star}\geq\frac{\sigma_{G}^{2}\alpha^{G}}{\epsilon_{G}^{3}(1-\beta_{1}^{G})^{3}\sqrt{\frac{\Theta}{1-\beta_{2}^{G}}\frac{1}{|S|^{2}}}}.$

The discussion for $b_{D}^{\star}$ is similar to the one for $b_{G}^{\star}$.
This completes the proof. ∎

###### Proof of Proposition3.4(ii).

The definition of $\bm{s}_{n}^{G}$ implies that

$\displaystyle s_{n,i}^{G}$
$\displaystyle=\beta_{2}^{G}v_{n-1,i}^{G}+(1-\beta_{2}^{G})(g_{n,i}-m_{n,i})^{2}\leq\max_{n,i}(g_{n,i}-m_{n,i})^{2}=:(g_{n^{*},i^{*}}-m_{n^{*},i^{*}})^{2}$
$\displaystyle\leq\sum_{i=1}^{\Theta}(g_{n^{*},i}-m_{n^{*},i})^{2}=\left\|\nabla
L_{G,\mathcal{S}_{n^{*}}}(\bm{\theta}_{n^{*}})-\bm{m}_{n^{*}}^{G}\right\|^{2},$

where the first inequality can be shown by induction. Hence, we have

$\displaystyle\left\|\nabla
L_{G,\mathcal{S}_{n^{*}}}(\bm{\theta}_{n^{*}})-\bm{m}_{n^{*}}^{G}\right\|^{2}\leq
2\left\|\nabla
L_{G,\mathcal{S}_{n^{*}}}(\bm{\theta}_{n^{*}})\right\|^{2}+2\left\|\bm{m}_{n^{*}}^{G}\right\|^{2}\leq\frac{4\sigma_{G}^{2}}{b}+4\left\|\nabla
L_{G}(\bm{\theta}_{n^{*}},\bm{w}_{n^{*}})\right\|^{2}$

Therefore, for all $n\in\mathbb{N}$ and all $i\in[\Theta]$,

$\displaystyle
s_{n,i}^{G}\leq\frac{4\Theta}{|S|^{2}}\max_{i\in[\Theta]}G_{n^{*},i}^{2}.$

From the definition of $\hat{s}_{n,i}^{G}$ and $\beta_{2}\in[0,1)$, we have

$\displaystyle
h_{0,*}^{G}:=\min_{i\in[\Theta]}h_{0,i}^{G}\leq\sqrt{\hat{s}_{n,i}^{G}}=\sqrt{\frac{s_{n,i}^{G}}{1-{\beta_{2}^{G}}^{n}}}\leq\sqrt{\frac{s_{n,i}^{G}}{1-\beta_{2}^{G}}}.$

Hence,

$\displaystyle
b_{G}^{\star}\geq\frac{\sigma_{G}^{2}\alpha^{G}}{\epsilon_{G}^{2}(1-\beta_{1}^{G})(1-\gamma^{G})^{2}\sqrt{\frac{4\Theta}{1-\beta_{2}^{G}}\frac{1}{|S|^{2}}\max_{i\in[\Theta]}G_{n^{*},i}^{2}}}.$

Accordingly, using $\gamma^{G}=\beta_{1}^{G}$ and
$\max_{i\in[\Theta]}G_{n^{*},i}^{2}\approx\epsilon_{G}^{2}$ implies that

$\displaystyle
b_{G}^{\star}\geq\frac{\sigma_{G}^{2}\alpha^{G}}{\epsilon_{G}^{3}(1-\beta_{1}^{G})^{3}\sqrt{\frac{4\Theta}{1-\beta_{2}^{G}}\frac{1}{|S|^{2}}}}.$

The discussion for $b_{D}^{\star}$ is similar to the one for $b_{G}^{\star}$.
This completes the proof. ∎

###### Proof of Proposition 3.4(iii).

From the definition of $\bm{v}_{n}^{G}$ and a discussion similar to the proof
of Proposition 3.4(i), we have

$\displaystyle
v_{n,i}^{G}\leq\frac{\Theta}{|S|^{2}}\max_{i\in[\Theta]}G_{n^{*},i}^{2}.$

From the definition of $v_{n,i}^{G}$, we have

$\displaystyle
h_{0,*}^{G}:=\min_{i\in[\Theta]}h_{0,i}^{G}\leq\sqrt{v_{n,i}^{G}}.$

Hence,

$\displaystyle
b_{G}^{\star}\geq\frac{\sigma_{G}^{2}\alpha^{G}}{\epsilon_{G}^{2}(1-\beta_{1}^{G})(1-\gamma^{G})^{2}\sqrt{\frac{\Theta}{|S|^{2}}\max_{i\in[\Theta]}G_{n^{*},i}^{2}}}.$

Accordingly, using $\gamma^{G}=\beta_{1}^{G}=0$ and
$\max_{i\in[\Theta]}G_{n^{*},i}^{2}\approx\epsilon_{G}^{2}$ implies that

$\displaystyle
b_{G}^{\star}\geq\frac{\sigma_{G}^{2}\alpha^{G}}{\epsilon_{G}^{3}\sqrt{\frac{\Theta}{|S|^{2}}}}.$

The discussion for $b_{D}^{\star}$ is similar to the one for $b_{G}^{\star}$.
This completes the proof. ∎

###  A.11 Relationship between stationary point problem and variational
inequality

######  Proposition A.1.

Suppose that $f:\mathbb{R}^{d}\to\mathbb{R}$ is continuously differentiable
and $\bm{x}^{*}$ is a stationary point of $f$. Then, $\nabla
f(\bm{x}^{*})=\bm{0}$ is equivalent to the following variational inequality:
for all $\bm{x}\in\mathbb{R}^{d}$,

$\displaystyle\langle\nabla f(\bm{x}^{*}),\bm{x}-\bm{x}^{*}\rangle\geq 0.$

###### Proof of Proposition A.1.

Suppose that $\bm{x}\in\mathbb{R}^{d}$ satisfies $\nabla f(\bm{x})=\bm{0}$.
Then, for all $\bm{y}\in\mathbb{R}^{d}$,

$\displaystyle\langle\nabla f(\bm{x}),\bm{y}-\bm{x}\rangle\geq 0.$

Suppose that $\bm{x}\in\mathbb{R}^{d}$ satisfies $\langle\nabla
f(\bm{x}),\bm{y}-\bm{x}\rangle\geq 0$ for all $\bm{y}\in\mathbb{R}^{d}$. Let
$\bm{y}:=\bm{x}-\nabla f(\bm{x})$. Then we have

$\displaystyle 0\leq\langle\nabla f(\bm{x}),\bm{y}-\bm{x}\rangle=-\|\nabla
f(\bm{x})\|^{2}.$

Hence,

$\displaystyle\nabla f(\bm{x})=\bm{0}.$

∎

###  A.12 Remarks regarding (C3)

We make the following remarks regarding (C3).

(C3)(i) Let $L_{G}^{(i)}(\cdot,\bm{w})\colon\mathbb{R}^{\Theta}\to\mathbb{R}$
$(i\in\mathcal{S})$ be convex and
$\nabla_{\bm{\theta}}L_{G}^{(i)}(\cdot,\bm{w})\colon\mathbb{R}^{\Theta}\to\mathbb{R}^{\Theta}$
be Lipschitz continuous with the Lipschitz constant $l_{G}$. Let
$L_{D}^{(i)}(\bm{\theta},\cdot)\colon\mathbb{R}^{W}\to\mathbb{R}$
$(i\in\mathcal{R})$ be convex and
$\nabla_{\bm{w}}L_{D}^{(i)}(\bm{\theta},\cdot)\colon\mathbb{R}^{W}\to\mathbb{R}^{W}$
be Lipschitz continuous with the Lipschitz constant $l_{D}$. Then, the
sequences $(\bm{\theta}_{n})_{n\in\mathbb{N}}$ and
$(\bm{w}_{n})_{n\in\mathbb{N}}$ generated by SGD with $\alpha^{G}\leq 1/l_{G}$
and $\alpha_{D}\leq 1/l_{D}$ satisfy (C3).

(C3)(ii) Let $L_{G}^{(i)}(\cdot,\bm{w})\colon\mathbb{R}^{\Theta}\to\mathbb{R}$
$(i\in\mathcal{S})$ and
$L_{D}^{(i)}(\bm{\theta},\cdot)\colon\mathbb{R}^{W}\to\mathbb{R}$
$(i\in\mathcal{R})$ be nonconvex. Let $B^{G}\subset\mathbb{R}^{\Theta}$ and
$B^{D}\subset\mathbb{R}^{W}$ be closed balls defined by
$B^{G}:=\\{\bm{\theta}\in\mathbb{R}^{\Theta}\colon\|\bm{\theta}-\bm{c}^{G}\|\leq
r^{G}\\}$ and
$B^{D}:=\\{\bm{w}\in\mathbb{R}^{W}\colon\|\bm{w}-\bm{c}^{D}\|\leq r^{D}\\}$,
where $\bm{c}^{G}\in\mathbb{R}^{\Theta}$, $\bm{c}^{D}\in\mathbb{R}^{W}$, and
$r^{G},r^{D}>0$ are large radii of $B^{G}$ and $B^{D}$. We replace
$\bm{\theta}_{n+1}:=\bm{\theta}_{n}+\alpha_{n}^{G}\bm{d}^{G}_{n}$ and
$\bm{w}_{n+1}:=\bm{w}_{n}+\alpha_{n}^{D}\bm{d}^{D}_{n}$ in Algorithm 1 with

$\displaystyle\bm{\theta}_{n+1}:=P_{G}\left(\bm{\theta}_{n}+\alpha_{n}^{G}\bm{d}^{G}_{n}\right)\text{
and }\bm{w}_{n+1}:=P_{D}\left(\bm{w}_{n}+\alpha_{n}^{D}\bm{d}^{D}_{n}\right),$
(22)

where $P_{G}$ is the projection onto $B^{G}$ and $P_{D}$ is the projection
onto $B^{D}$. Then, the sequences $(\bm{\theta}_{n})_{n\in\mathbb{N}}\subset
B^{G}$ and $(\bm{w}_{n})_{n\in\mathbb{N}}\subset B^{D}$ generated by (22) are
bounded. Thus, the nonexpansivity conditions of $P_{G}$ and $P_{D}$ guarantee
that Algorithm 1 using (22) satisfies (2) without assuming (C3).

###### Proof of (C3)(i).

Let $n\in\mathbb{N}$. We define
$\phi_{n}\colon\mathbb{R}^{\Theta}\to\mathbb{R}$ for all
$\bm{\theta}\in\mathbb{R}^{\Theta}$ by

$\displaystyle\phi_{n}(\bm{\theta}):=L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n},\bm{w}_{n})+\langle\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n}),\bm{\theta}-\bm{\theta}_{n}\rangle+\frac{1}{2\alpha^{G}}\|\bm{\theta}-\bm{\theta}_{n}\|^{2}.$

The convexity of $L_{G,\mathcal{S}_{n}}(\cdot,\bm{w}_{n})$ implies that, for
all $\bm{\theta}\in\mathbb{R}^{\Theta}$,
$L_{G,\mathcal{S}_{n}}(\bm{\theta},\bm{w}_{n})\geq
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n},\bm{w}_{n})+\langle\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n}),\bm{\theta}-\bm{\theta}_{n}\rangle$.
Hence, we have that, for all $\bm{\theta}\in\mathbb{R}^{\Theta}$,

$\displaystyle\phi_{n}(\bm{\theta})\leq
L_{G,\mathcal{S}_{n}}(\bm{\theta},\bm{w}_{n})+\frac{1}{2\alpha^{G}}\|\bm{\theta}-\bm{\theta}_{n}\|^{2}.$
(23)

Moreover, from $\nabla_{\bm{\theta}}\phi_{n}(\bm{\theta})=\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})+(1/\alpha^{G})(\bm{\theta}-\bm{\theta}_{n})$,
$\phi_{n}$ is strongly convex with a constant $1/\alpha^{G}$. Accordingly,
there exists a unique minimizer $\tilde{\bm{\theta}}_{n}$ of $\phi_{n}$ such
that

$\displaystyle\bm{0}=\nabla_{\bm{\theta}}\phi_{n}(\tilde{\bm{\theta}}_{n})=\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})+\frac{1}{\alpha^{G}}(\bm{\theta}-\bm{\theta}_{n}),$

i.e.,

$\displaystyle\tilde{\bm{\theta}}_{n}=\bm{\theta}_{n}-\alpha^{G}\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n})=:\bm{\theta}_{n+1}.$

The strong convexity of $\phi_{n}$ and
$\nabla_{\bm{\theta}}\phi_{n}(\bm{\theta}_{n+1})=\bm{0}$ imply that

$\displaystyle\begin{split}\phi_{n}(\bm{\theta})&\geq\phi_{n}(\bm{\theta}_{n+1})+\langle\nabla_{\bm{\theta}}\phi_{n}(\bm{\theta}_{n+1}),\bm{\theta}-\bm{\theta}_{n+1}\rangle+\frac{1}{2\alpha^{G}}\|\bm{\theta}_{n+1}-\bm{\theta}\|^{2}\\\
&=\phi_{n}(\bm{\theta}_{n+1})+\frac{1}{2\alpha^{G}}\|\bm{\theta}_{n+1}-\bm{\theta}\|^{2}.\end{split}$
(24)

The condition $\alpha^{G}\leq 1/l_{G}$ and the Lipschitz continuity of $\nabla
L_{G,\mathcal{S}_{n}}(\cdot)$ ensure that

$\displaystyle\begin{split}\phi_{n}(\bm{\theta}_{n+1})&:=L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n},\bm{w}_{n})+\langle\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n}),\bm{\theta}_{n+1}-\bm{\theta}_{n}\rangle+\frac{1}{2\alpha^{G}}\|\bm{\theta}_{n+1}-\bm{\theta}_{n}\|^{2}\\\
&\geq L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n},\bm{w}_{n})+\langle\nabla
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n}),\bm{\theta}_{n+1}-\bm{\theta}_{n}\rangle+\frac{l_{G}}{2}\|\bm{\theta}_{n+1}-\bm{\theta}_{n}\|^{2}\\\
&\geq L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n+1},\bm{w}_{n}).\end{split}$ (25)

From (23), (24), and (25),

$\displaystyle
L_{G,\mathcal{S}_{n}}(\bm{\theta},\bm{w}_{n})+\frac{1}{2\alpha^{G}}\|\bm{\theta}_{n}-\bm{\theta}\|^{2}\geq
L_{G,\mathcal{S}_{n}}(\bm{\theta}_{n+1},\bm{w}_{n})+\frac{1}{2\alpha^{G}}\|\bm{\theta}_{n+1}-\bm{\theta}\|^{2},$

which implies that, for all $\bm{\theta}\in\mathbb{R}^{\Theta}$,

$\displaystyle
L_{G}(\bm{\theta},\bm{w}_{n})+\frac{1}{2\alpha^{G}}\|\bm{\theta}_{n}-\bm{\theta}\|^{2}\geq
L_{G}(\bm{\theta}_{n+1},\bm{w}_{n})+\frac{1}{2\alpha^{G}}\|\bm{\theta}_{n+1}-\bm{\theta}\|^{2}.$

Let $\bm{\theta}^{*}\in\mathbb{R}^{\Theta}$ be a minimizer of
$L_{G}(\bm{\theta},\bm{w}_{n})$. Then, we have

$\displaystyle\frac{1}{2\alpha^{G}}\left(\|\bm{\theta}_{n+1}-\bm{\theta}^{*}\|^{2}-\|\bm{\theta}_{n}-\bm{\theta}^{*}\|^{2}\right)\leq
L_{G}(\bm{\theta}^{*},\bm{w}_{n})-L_{G}(\bm{\theta}_{n+1},\bm{w}_{n})\leq 0.$

Since $(\|\bm{\theta}_{n}-\bm{\theta}^{*}\|^{2})_{n\in\mathbb{N}}$ is monotone
decreasing, the sequence
$(\|\bm{\theta}_{n}-\bm{\theta}^{*}\|^{2})_{n\in\mathbb{N}}$ is bounded. The
discriminator can be defined by replacing $G$, $\mathcal{S}_{n}$,
$\bm{\theta}$, and $\bm{w}$ in the generator with $D$, $\mathcal{R}_{n}$,
$\bm{w}$, and $\bm{\theta}$. ∎

Details of (C3)(ii): Let $\bm{\theta}\in B^{G}\subset\mathbb{R}^{\Theta}$ and
$n\in\mathbb{N}$. The definition of $\bm{\theta}_{n+1}$ and the nonexpansivity
of $P_{G}$ (i.e.,
$\|P_{G}(\bm{\theta}_{1})-P_{G}(\bm{\theta}_{2})\|_{\mathsf{H}}\leq\|\bm{\theta}_{1}-\bm{\theta}_{2}\|_{\mathsf{H}}$
$(\bm{\theta}_{1},\bm{\theta}_{2}\in\mathbb{R}^{\Theta},\mathsf{H}\in\mathbb{S}_{++}^{\Theta})$)
imply that

$\displaystyle\|\bm{\theta}_{n+1}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}$
$\displaystyle=\|P_{G}(\bm{\theta}_{n}+\alpha_{n}^{G}\bm{d}_{n}^{G})-P_{G}(\bm{\theta})\|_{\mathsf{H}_{n}^{G}}^{2}$
$\displaystyle\leq\|(\bm{\theta}_{n}-\bm{\theta})+\alpha_{n}^{G}\bm{d}_{n}^{G}\|_{\mathsf{H}_{n}^{G}}^{2}=\|\bm{\theta}_{n}-\bm{\theta}\|_{\mathsf{H}_{n}^{G}}^{2}+2\alpha_{n}^{G}\langle\bm{\theta}_{n}-\bm{\theta},\bm{d}_{n}^{G}\rangle_{\mathsf{H}_{n}^{G}}+\alpha_{n}^{G^{2}}\|\bm{d}_{n}^{G}\|_{\mathsf{H}_{n}^{G}}^{2}.$

Hence, a discussion similar to the one proving Theorem 3.1 ensures that
Algorithm 1 using (22) satisfies (2) without assuming (C3).