pdflatexsn-jnl

2021

[2]Li Shen

1]IEOR, Columbia Unviersity, NY, USA

2]JD Explore Academy, JD.com Inc, Beijing, China

3]Booth School of Business, University of Chicago, IL, USA

# Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimization

Luofeng Liao<EMAIL_ADDRESS><EMAIL_ADDRESS>Jia Duan
<EMAIL_ADDRESS>Mladen Kolar<EMAIL_ADDRESS>Dacheng Tao
<EMAIL_ADDRESS>[  [  [

###### Abstract

Large scale convex-concave minimax problems arise in numerous applications,
including game theory, robust training, and training of generative adversarial
networks. Despite their wide applicability, solving such problems efficiently
and effectively is challenging in the presence of large amounts of data using
existing stochastic minimax methods. We study a class of stochastic minimax
methods and develop a communication-efficient distributed stochastic
extragradient algorithm, LocalAdaSEG, with an adaptive learning rate suitable
for solving convex-concave minimax problems in the Parameter-Server model.
LocalAdaSEG has three main features: (i) a periodic communication strategy
that reduces the communication cost between workers and the server; (ii) an
adaptive learning rate that is computed locally and allows for tuning-free
implementation; and (iii) theoretically, a nearly linear speed-up with respect
to the dominant variance term, arising from the estimation of the stochastic
gradient, is proven in both the smooth and nonsmooth convex-concave settings.
LocalAdaSEG is used to solve a stochastic bilinear game, and train a
generative adversarial network. We compare LocalAdaSEG against several
existing optimizers for minimax problems and demonstrate its efficacy through
several experiments in both homogeneous and heterogeneous settings.

###### keywords:

Stochastic Minimax Problem, Adaptive Optimization, Distributed Computation

##  1 Introduction

Stochastic minimax optimization problems arise in applications ranging from
game theory neumann1928theorie , robust optimization
delage2010distributionally , and AUC Maximization guo2020communication , to
adversarial learning wang2019towards  and training of generative adversarial
networks (GANs) goodfellow2014generative . In this work, we consider

$\displaystyle\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}\;\bigg{\\{}F(x,y)=\int_{\Xi}f(x,y,\xi)P(\mathop{}\\!\mathrm{d}\xi)\bigg{\\}},$
(1)

where ${\mathcal{X}}\subseteq\mathbb{X}$, ${\mathcal{Y}}\subseteq\mathbb{Y}$
are nonempty compact convex sets, $\mathbb{X}$, $\mathbb{Y}$ are finite
dimensional vector spaces, $\xi$ is a random vector with an unknown
probability distribution $P$ supported on a set $\Xi$, and
$f:{\mathcal{X}}\times{\mathcal{Y}}\times\Xi\to{{\mathbb{R}}}$ is a real
valued function, which may be nonsmooth. Throughout the paper, we assume that
the expectation ${\mathbb{E}}_{\xi\sim P}[f(x,y,\xi)]$ is well defined and
finite. For all $\xi\in\Xi$, we assume that the function $F(x,y)$ is convex in
$x\in{\mathcal{X}}$ and concave in $y\in{\mathcal{Y}}$. In addition, we assume
that $F(x,y)$ is a Lipschitz continuous function.

There are three main challenges in developing an efficient solver for the
large-scale minimax problem (1). First, the solver should generate converging
iterates. In contrast to convex optimization, convergence results for minimax
problems are harder to obtain. Second, the solver should be able to take
advantage of parallel computing in a communication-efficient way. Only then
can it be applied to problems with large-scale datasets, which are often
distributed across multiple workers. Third, it is desirable for the solver to
choose learning rates in an adaptive manner. It is well known that, in minimax
problems, solver performance is susceptible to learning rates. We discuss
these challenges in detail below.

First, it has been shown that direct application of the (stochastic) gradient
descent ascent ((S)GDA) to solve (1) may result in divergence of the iterates
mertikopoulos2018optimistic ; daskalakis2018training ; gidel2019negative ;
mertikopoulos2018cycles . Possible ways to overcome the divergence issue are
to apply the primal-dual hybrid gradient (PDHG) or (stochastic) extragradient
method and their variants mertikopoulos2018optimistic ; daskalakis2018training
; gidel2018a ; azizian2020tight ; liu2020towards ; zhao2021accelerated ;
NEURIPS2020_52aaa62e .

Second, it is often desirable to have a communication-efficient distributed
solver to solve the stochastic minimax problem (1). The first reason being
that the minimax problem (1) is often instantiated as a finite-sum problem
with large-scale datasets (with the distribution $P$ being the empirical
distribution over millions of data points), and thus storing and manipulating
datasets on multiple workers is a must. For example, when problem (1) is
specified as BigGAN brock2018large  over ImageNet deng2009imagenet , the
number of training samples is as many as 14 million. Traditional distributed
SGDA on the problem (1) may suffer from a considerable communication burden;
reducing communication complexity of the algorithm is a major concern in our
paper. The second reason is that, in some scenarios, data are distributed on
mobile devices (such as cell phones or smart watches), and due to privacy
concerns, local data must stay on the device. Furthermore, frequent
communication among devices is not feasible due to failures of mobile devices
(network connectivity, battery level, etc.). This further motivates the design
of communication-efficient distributed solvers to eliminate central data
storage and improve communication efficiency. For these reasons,
communication-efficient distributed solvers for minimax problems have been
investigated recently beznosikov2021distributed ; deng2020local ;
hou2021efficient ; mingruiliu2020decentralized .

Third, the performance of stochastic minimax solvers for (1) is highly
dependent on the learning rate tuning mechanism heusel2017gans ;
antonakopoulos2021adaptive . And yet, designing a solver for (1) with an
adaptive learning rate is much more challenging compared to the convex case;
the value of $F$ at an iterate $(x,y)$ does _not_ serve as a performance
criterion. For example, for classical minimization problems, the learning rate
can be tuned based on the loss evaluated at the current iterate, which
directly quantifies how close the iterate is to the minimum. However, such an
approach does not extend to minimax problems and, therefore, a more
sophisticated approach is required for tuning the learning rate. Development
of adaptive learning rate tuning mechanisms for large scale stochastic minimax
problems has been explored only recently bach2019universal ;
babanezhad2020geometry ; ene2020adaptive ; antonakopoulos2021adaptive ;
liu2020towards . Hence, we ask

_Can we develop an efficient algorithm for the stochastic minimax problem ( 1)
that enjoys convergence guarantees, communication-efficiency and adaptivity
simultaneously?_

Figure 1: A Venn Diagram for related works. Left circle: Communication-
efficient methods for stochastic minimax problems. Right circle: Adaptive
methods for stochastic minimax problems.

We provide an affirmative answer to this question and develop
${\operatorname*{{LocalAdaSEG}}}$ (Local Adaptive Stochastic Extragradient)
algorithm. Our contributions are three-fold:

Novel communication-efficient distributed minimax algorithm. Fig. 1
illustrates the difference between ${\operatorname*{{LocalAdaSEG}}}$ algorithm
and the existing works. ${\operatorname*{{LocalAdaSEG}}}$ falls under the
umbrella of the Parameter-Server model smola2010architecture  and adopts a
periodic communication mechanism to reduce the communication cost between the
server and the workers, similar to Local SGD/FedAvg Yu2019onthelinear ;
stich2018local ; Li2020On  in federated learning mcmahan2021advances . In
addition, in each worker, a local stochastic extragradient algorithm with an
adaptive learning rate is performed independently with multiple iterations.
Every once in a while, current iterates and adaptive learning rates from all
workers are sent to the server. The server computes a weighted average of the
iterates, where the weights are constructed from the received local adaptive
learning rates. We emphasize that adaptive learning in each worker is distinct
from others and is automatically updated according to local data as is done in
chen2021quantized ; beznosikov2021distributed , and different from the
existing adaptive distributed algorithms xie2019local ; reddi2021adaptive ;
chen2021cada .

Theoretically optimal convergence rate. Let $M$ denote the number of workers,
$\sigma$ denote the variance of stochastic gradients, and $T$ denote the
number of local iterations on each worker. For stochastic convex-concave
minimax problems, we establish the rate in terms of the duality gap metric
nemirovski2004prox ; lin2020near  as $\tilde{O}({\sigma}{/}{\sqrt{MT}})$ in
the _nonsmooth and noise-dominant_ case and the rate
$\tilde{O}({\sigma}{/}{{\sqrt{MT}}}+\text{ higher-order terms})$ in _smooth
case with slow cumulative gradient growth_. The terms depending on the
variance $\sigma$ achieve the statistical lower bound and are not improvable
without further assumptions. Therefore, the ${\operatorname*{{LocalAdaSEG}}}$
algorithm enjoys the linear speed-up property in the stochastic gradient
variance term due to the periodic communication mechanism.

Experimental verification. We conduct several experiments on the stochastic
bilinear game and the Wasserstein GAN arjovsky2017wasserstein  to verify the
efficiency and effectiveness of the ${\operatorname*{{LocalAdaSEG}}}$
algorithm. We also extend the ${\operatorname*{{LocalAdaSEG}}}$ algorithm to
solve the challenging federated GANs in a heterogeneous setting. The
experimental results agree with the theoretical guarantees and demonstrate the
superiority of ${\operatorname*{{LocalAdaSEG}}}$ against several existing
minimax optimizers, such as SEGDA nemirovski2004prox , UMP bach2019universal ,
ASMP ene2020adaptive , LocalSEGDA beznosikov2021distributed , LocalSGDA
deng2020local , and Local Adam beznosikov2021distributed .

##  2 Related Work

Although there has been a lot of work on minimax optimization, due to space
constraints, we summarize only the most closely related work. Our work is
related to the literature on stochastic minimax algorithms, adaptive minimax
algorithms, and distributed minimax algorithms. We defer a detailed discussion
of related work to Appendix A in the appendix.

Our work and the proposed ${\operatorname*{{LocalAdaSEG}}}$ contribute to the
literature described above. To our knowledge, the proposed
${\operatorname*{{LocalAdaSEG}}}$ algorithm is the first distributed
communication-efficient algorithm for the stochastic minimax problem and
simultaneously supports the adaptive learning rate and minibatch size.
Moreover, ${\operatorname*{{LocalAdaSEG}}}$ communicates only periodically to
improve communication efficiency and uses a local adaptive learning rate,
computed on local data in each worker, to improve the efficiency of
computation. In addition, ${\operatorname*{{LocalAdaSEG}}}$ can also be
applied in a non-smooth setting with the convergence guarantee.
${\operatorname*{{LocalAdaSEG}}}$ can be seen as a distributed extension of
bach2019universal  with period communication as local SGD stich2018local . We
note that only very recently a local adaptive stochastic minimax algorithm,
called Local Adam, has been used heuristically to train GANs without a
convergence guarantee beznosikov2021distributed . We summarize the
relationship with the existing literature in Table 1.

Stochastic minimax algorithms | Nonsmooth ? | Comm. eff. ? | Adaptive ?
---|---|---|---
Mirror SA nemirovski2009robust , SMP Juditsky2011solving , SAMP chen2017accelerated , Optimal Stochastic PDHG-type zhao2021accelerated  | ✓ | ✗ | ✗
SCAFFOLD-Catalyst-S hou2021efficient , Local SGDA deng2020local , Extra Step Local SGD beznosikov2021distributed  | ✗ | ✓ | ✗
Universal Mirror-prox bach2019universal , Adaptive Single-gradient Mirror-prox ene2020adaptive , Geometry-Aware Universal Mirror-prox babanezhad2020geometry , AdaProx antonakopoulos2021adaptive  | ✓ | ✗ | ✓
Optimistic AdaGrad liu2020towards  | ✗* | ✗ | ✓
Our ${\operatorname*{{LocalAdaSEG}}}$ | ✓ | ✓ | ✓
Table 1: Comparison to related works on adaptive or communication-efficient
approaches to stochastic minimax problems. Here ”Nonsmooth ?” asks whether the
algorithm enjoys theoretical guarantees in the nonsmooth convex-concave
setting; ”Comm. eff. ?” asks whether the proposed algorithm is communication-
efficient; ”Adaptive ?” asks whether the proposed algorithm requires knowledge
of problem parameters. ”*”: The work of liu2020towards  discusses non-convex
non-concave minimax problems.

##  3 Methodology

###  3.1 Notations and Assumptions

A point $(x^{*},y^{*})\in{\mathcal{X}}\times{\mathcal{Y}}$ is called a saddle-
point for the minimax problem in (1) if for all
$(x,y)\in{\mathcal{X}}\times{\mathcal{Y}}$,

$\displaystyle F(x^{*},y)\leq F(x^{*},y^{*})\leq F(x,y^{*}).$ (2)

Under the assumptions stated in Section 1, the corresponding primal,
$\min_{x}\\{\max_{y}F(x,y)\\}$, and dual problem,
$\max_{y}\\{\min_{x}F(x,y)\\}$, have optimal solutions and equal optimal
values, denoted $F^{*}$. The pairs of optimal solutions $(x^{*},y^{*})$ form
the set of saddle-points of $F$ on ${\mathcal{X}}\times{\mathcal{Y}}$. We
denote $\mathbb{Z}=\mathbb{X}\times\mathbb{Y}$,
$\mathcal{Z}={\mathcal{X}}\times{\mathcal{Y}}$, $z=(x,y)\in\mathcal{Z}$, and
$z^{*}=(x^{*},y^{*})\in\mathcal{Z}$. We use $\|\cdot\|_{\mathcal{X}}$,
$\|\cdot\|_{\mathcal{Y}}$, and $\|\cdot\|_{\mathcal{Z}}$ to denote the
Euclidean norms on $\mathbb{X}$, $\mathbb{Y}$, $\mathbb{Z}$, respectively, and
let $\|\cdot\|_{{\mathcal{X}},*}$, $\|\cdot\|_{{\mathcal{Y}},*}$ and
$\|\cdot\|_{\mathcal{Z},*}$ denote the corresponding dual norms. With this
notation,
$\|z\|_{\mathcal{Z}}=\sqrt{\|x\|_{\mathcal{X}}^{2}+\|y\|_{\mathcal{Y}}^{2}}$
and
$\|z\|_{{\mathcal{Z}},*}=\sqrt{\|x\|_{{\mathcal{X}},*}^{2}+\|y\|_{{\mathcal{Y}},*}^{2}}$.
Throughout the paper, we focus on the Euclidean setting, but note that the
results can readily generalize to non-Euclidean cases.

We are interested in finding a saddle-point of $F$ over
${\mathcal{X}}\times{\mathcal{Y}}$. For a candidate solution
$\tilde{z}=(\tilde{x},\tilde{y})\in\mathcal{Z}$, we measure its quality by the
duality gap, defined as

$\displaystyle{\operatorname*{{DualGap}}}(\tilde{z})\vcentcolon=\max_{y\in{\mathcal{Y}}}F(\tilde{x},y)-\min_{x\in{\mathcal{X}}}F(x,\tilde{y}).$
(3)

The duality gap is commonly used as a performance criterion for general
convex-concave minimax problems (see, e.g., nemirovski2004prox ; lin2020near
). Note that for all $z\in{\mathcal{Z}}$ it holds
${\operatorname*{{DualGap}}}(z)\geq 0$ and ${\operatorname*{{DualGap}}}(z)=0$
if and only if $z$ is a saddle-point.

For the stochastic minimax problem (1), we assume that neither the function
$F(x,y)$ nor its sub/supgradients in $x$ and $y$ are available. Instead, we
assume access to an unbiased stochastic oracle
$G(x,y,\xi)=[G_{x}(x,y,\xi),-G_{y}(x,y,\xi)]$, such that the vector
${\mathbb{E}}_{\xi}[G(x,y,\xi)]$ is well-defined and
${\mathbb{E}}_{\xi}[G(x,y,\xi)]\in[\partial_{x}F(x,y),-\partial_{y}F(x,y)]$.
For notational convenience, we let

$\displaystyle\tilde{G}(z)\vcentcolon=G(x,y,\xi),\quad
G(z)\vcentcolon={\mathbb{E}}_{\xi}[G(x,y,\xi)].$ (4)

Below, we impose assumptions on the minimax problem (1) and the stochastic
gradient oracle (4).

######  Assumption 1 (Bounded Domain).

There exists $D$ such that $\sup_{z\in{\mathcal{Z}}}\frac{1}{2}\|z\|^{2}\leq
D^{2}$.

######  Assumption 2 (Bounded Stochastic Gradients).

There exists $G$ such that $\sup_{z\in{\mathcal{Z}}}\|\tilde{G}(z)\|_{*}\leq
G$, P-almost surely.

Domain boundedness 1 is commonly assumed in the convex-concave minimax
literature; see references in Section 1. However, we note that the assumption
might be removed in certain settings. For example, Chen2014 ;
monteiro2011complexity  use a perturbation-based variant of the duality gap as
the convergence criterion, and antonakopoulos2021adaptive  handles unbounded
domains via the notion of local norms, while zhao2021accelerated  handles
unbounded domains with access to a convex optimization oracle. The almost sure
boundedness Assumption 2 on the gradient oracle seems restrictive but is
common in the literature on adaptive stochastic gradient methods (see, e.g.,
duchi2011adaptive ; chen2018on ; bach2019universal ; liu2020towards ). In
Remark 2 we discuss how to extend our analysis to unbounded oracles.

######  Assumption 3 (Bounded Variance).

There exists $\sigma$ such that
${\mathbb{E}}_{\xi}\big{[}\|G(z)-\tilde{G}(z)\|_{*}^{2}\,|\,z\big{]}\leq\sigma^{2}$
for $P$-almost every $z$.

We separately analyze the case when the saddle function $F$ is differentiable
with Lipschitz gradients.

######  Assumption 4 (Smoothness).

Assume that for all $z,z^{\prime}\in{\mathcal{Z}}$, we have
$\|G(z)-G(z^{\prime})\|_{*}\leq L\|z-z^{\prime}\|$.

###  3.2 ${\operatorname*{{LocalAdaSEG}}}$ Algorithm

We introduce the ${\operatorname*{{LocalAdaSEG}}}$ algorithm used to solve (1)
and describe its main features. Algorithm 1 details the procedure.

Algorithm 1 ${\operatorname*{{LocalAdaSEG}}}(G_{0},D\mathchar
24635\relax\;K,M,R\mathchar 24635\relax\;\alpha)$

1:Input: $G_{0}$, a guess on the upper bound of gradients, $D$, the diameter
of the set ${\mathcal{Z}}$, $K$, communication interval, $M$, the number of
workers, $R$, number of rounds, $\alpha$, base learning rate.

2:Initialize: $\eta^{m}_{1}=D\alpha/G_{0}$,
$\tilde{z}_{0}=\tilde{z}^{m}_{0}=\tilde{z}^{m,*}_{0}=0$ for all $m$, and
$S\vcentcolon=\\{0,K,2K,\dots,RK\\}$.

3:for $t=1,\dots,T=RK$, parallel for workers $m=1,\dots,M$ do

4: update learning rate ${\eta^{m}_{t}}=$
$\displaystyle{D\alpha}\big{/}{\sqrt{G_{0}^{2}+\sum_{\tau=1}^{t-1}\frac{\textstyle{\|z^{m}_{\tau}-\tilde{z}^{m,*}_{\tau-1}\|^{2}+\|z^{m}_{\tau}-\tilde{z}^{m}_{\tau}\|^{2}}}{{{5}({\eta^{m}_{\tau}})^{2}}}}}$

5: if $t-1\in S$ then

6: worker $m$: send $({\eta^{m}_{t}},{\tilde{z}^{m}_{t-1}})$ to server

7: server: compute ${\tilde{z}^{\circ}_{t-1}}$, the weighted average of
$\\{{\tilde{z}^{m}_{t-1}}\\}_{m\in[M]}$, and broadcast it to workers
$w^{m}_{t}=\frac{({\eta^{m}_{t}})^{-1}}{\textstyle\sum_{m^{\prime}=1}^{M}(\eta^{m^{\prime}}_{t})^{-1}},\;{\tilde{z}^{\circ}_{t-1}}={\sum_{m=1}^{M}}w^{m}_{t}\cdot{\tilde{z}^{m}_{t-1}}$

8: worker $m$: set ${\tilde{z}^{m,*}_{t-1}}={\tilde{z}^{\circ}_{t-1}}$

9: else

10: set ${\tilde{z}^{m,*}_{t-1}}={\tilde{z}^{m}_{t-1}}$

11: end if

12: update  $\displaystyle{z^{m}_{t}}$
$\displaystyle=\Pi_{{\mathcal{Z}}}[{\tilde{z}^{m,*}_{t-1}}-{\eta^{m}_{t}}{M^{m}_{t}}]$
$\displaystyle\text{ with }{M^{m}_{t}}=\tilde{G}({\tilde{z}^{m,*}_{t-1}})$
$\displaystyle{\tilde{z}^{m}_{t}}$
$\displaystyle=\Pi_{{\mathcal{Z}}}[{\tilde{z}^{m,*}_{t-1}}-{\eta^{m}_{t}}{g^{m}_{t}}]$
$\displaystyle\text{ with }{g^{m}_{t}}=\tilde{G}({z^{m}_{t}})$

13:end for

14:Output: $\frac{1}{TM}{\sum_{m=1}^{M}}{\sum_{t=1}^{T}}z^{m}_{t}$

The Parameter-Server model. ${\operatorname*{{LocalAdaSEG}}}$ uses $M$
parallel workers which, in each of $R$ rounds, independently execute $K$ steps
of extragradient updates (Line 12). The adaptive learning rate is computed
solely based on iterates occurred in the local worker (Line 4). Let
$S\vcentcolon=\\{0,K,2K,\dots,RK=T\\}$ denote the time points of
communication. At a time of communication ($t\in S+1$, Lines 5–8), the workers
communicate and compute the weighted iterate, ${\tilde{z}^{\circ}_{t-1}}$,
defined in Line 7. Then the next round begins with a common iterate
${\tilde{z}^{\circ}_{t-1}}$. Finally, ${\operatorname*{{LocalAdaSEG}}}$
outputs the average of the sequence $\\{{z^{m}_{t}}\\}_{m\in[M],t\in[T]}$.
Overall, each worker computes $T=KR$ extragradient steps locally, for a total
of $2MT$ stochastic gradient calls (since each extragradient step, Line 12,
requires two calls of gradient oracle) with $R$ rounds of communication (every
$K$ steps of computation).

Extragradient step. At the time when no communication happens ($t-1\notin S$),
Line 12 reduces to

$\displaystyle{z^{m}_{t}}$
$\displaystyle=\Pi_{{\mathcal{Z}}}[{\tilde{z}^{m}_{t-1}}-{\eta^{m}_{t}}{M^{m}_{t}}]$
$\displaystyle\text{ with }{M^{m}_{t}}=\tilde{G}({\tilde{z}^{m}_{t-1}}),$
$\displaystyle{\tilde{z}^{m}_{t}}$
$\displaystyle=\Pi_{{\mathcal{Z}}}[{\tilde{z}^{m}_{t-1}}-{\eta^{m}_{t}}{g^{m}_{t}}]$
$\displaystyle\text{ with }{g^{m}_{t}}=\tilde{G}({z^{m}_{t}}),$

where
$\Pi_{\mathcal{Z}}(z)=\operatorname*{argmin}_{z^{\prime}\in{\mathcal{Z}}}\|z-z^{\prime}\|_{2}$
is the projection operator onto the compact set ${\mathcal{Z}}$. The above
update is just the extragradient (EG) algorithm korpel1976  that is commonly
used to solve minimax problems; see references in Section 1.

Periodic averaging weights. The proposed weighted averaging scheme in Line 7
is different from existing works on local SGD and Local Adam
beznosikov2021distributed . At the time of averaging ($t\\!-\\!1\\!\in\\!S$),
${\operatorname*{{LocalAdaSEG}}}$ pulls the averaged iterate towards the local
iterate with a smaller learning rate. For the homogeneous case studied in this
paper, we expect $w^{m}\sim 1/M$.

Intuition of local adaptive learning rate scheme. The adaptive learning rate
scheme (Line 4) follows that of Bach and Levy bach2019universal  closely. To
develop intuition, consider the deterministic setting where $\sigma=0$ and
define
$({\delta_{t}^{m}})^{2}\vcentcolon=\|{g^{m}_{t}}\|_{*}^{2}+\|{M^{m}_{t}}\|_{*}^{2}$.
If we ignore the projection operation, the learning rate ${\eta^{m}_{t}}$
would look like ${\eta^{m}_{t}}\sim
1/(1+\sum_{\tau=1}^{t-1}({\delta_{\tau}^{m}})^{2})^{1/2}$. In the nonsmooth
case, the subgradients might not vanish as we approach the solution (in the
case of convex optimization, consider the function
$f(x)=\mbox{{}\rm\sf\leavevmode\hbox{}\hbox{}x\/}$near$0$),andweonlyhave$\liminf_{t\to\infty}
{\delta_t^m}>
0$.Thisimplies${\eta^m_t}$willvanishattherate$1/\sqrt{t}$,whichistheoptimallearningrateschemefornonsmoothconvex-
concaveproblems\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{bach2019universal,
antonakopoulos2021adaptive}{\@@citephrase{(}}{\@@citephrase{)}}}.Forthesmoothcase,onemightexpectthesequence$\\{{\delta_t^m}\\}_t$tobesquare-
summableand${\eta^m_t}\to\eta_{\infty}^m >
0$,inwhichcasethelearningratedoesnotvanish.Additionally,theadaptivelearningrateforeachworkerislocallyupdatedtoexploittheproblemstructureavailableinworker^{\prime}slocaldataset.Thismakesourlocaladaptivelearningrateschemedistinctcomparedtoexistingdistributedadaptivealgorithmsforminimizationproblems\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{xie2019local,reddi2021adaptive,chen2021cada}{\@@citephrase{(}}{\@@citephrase{)}}}.Veryrecently,\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{beznosikov2021distributed}{\@@citephrase{(}}{\@@citephrase{)}}}usedlocalAdamfortrainingconditionalGANsefficiently,buttheyprovidetheoreticalguaranteesonlyforthelocalextragradientwithoutadaptivity.\par\textbf{Adaptivity
to $(G,L,\sigma)$.}\
Ouralgorithmdoesnotrequireknowledgeofproblemparameterssuchasthesizeofthegradients$G$,thesmoothness$L$,orthevarianceofgradientestimates$\sigma$.Instead,weonlyneedaninitialguessof$G$,denoted$G_0$,andthediameterofthefeasibleset,$D$.Following\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{bach2019universal}{\@@citephrase{(}}{\@@citephrase{)}}},wedefine\begin{aligned}
\gamma\vcentcolon=\max\\{G/G_{0},G_{0}/G\\}\geq
1.\end{aligned}Thisquantitymeasureshowgoodourguessisandappearsintheconvergenceguaranteesforthealgorithm.Ouralgorithmstillrequiresknowledgeoftheproblemclass,asweneedtouseadifferentbaselearningrate,$\alpha$,forsmoothandnonsmoothproblems\mathchar
24635\relax\;seeTheorems~{}\ref{thm:nonsmooth}and\ref{thm:smooth},respectively.\par\par\@@numbered@section{subsection}{toc}{Convergence
Results} \par We state two theorems characterizing the convergence rate of
${\operatorname*{{LocalAdaSEG}}}$ for the smooth and nonsmooth problems. We
use the notation $\tilde{O}$ to hide absolute constants and logarithmic
factors of $T=KR$ and problem parameters. The proofs are given in
\lx@cref{creftype~refnum}{sec:proof:thmnonsmooth} and
\lx@cref{creftype~refnum}{sec:proof:thmsmooth} of the appendix. Recall the
definition of $\gamma$ in~{}\eqref{eq:defgamma}.
\par\par\begin{theorem}[Nonsmooth Case] Assume that Assumptions
\ref{as:bddomain}, \ref{as:bdsg}, and \ref{as:bdvar} hold. Let
$\bar{z}={\operatorname*{{LocalAdaSEG}}}(G_{0},D\mathchar
24635\relax\;K,M,R\mathchar 24635\relax\;1)$. Then
$${\mathbb{E}}[\operatorname*{DualGap}(\bar{z})]=\tilde{O}\bigg{(}\frac{\gamma
GD}{\sqrt{T}}+\frac{\sigma D}{\sqrt{MT}}\bigg{)}\,.$$ \end{theorem}
\par\begin{theorem}[Smooth Case] Assume that Assumptions \ref{as:bddomain},
\ref{as:bdsg}, \ref{as:bdvar}, and \ref{as:smooth} hold. Let
$\bar{z}={\operatorname*{{LocalAdaSEG}}}(G_{0},D\mathchar
24635\relax\;K,M,R\mathchar 24635\relax\;1/\sqrt{M})$. Define the cumulative
norms of stochastic gradients occurred on worker $m$ as
\@@amsalign{\mathcal{V}_{m}(T)}\vcentcolon={\mathbb{E}}\left[\sqrt{{\sum_{t=1}^{T}}\|{g^{m}_{t}}\|_{*}^{2}+\|{M^{m}_{t}}\|_{*}^{2}}\right].
Then
\@@amsalign{\mathbb{E}}[\operatorname*{DualGap}(\bar{z})]=\tilde{O}\\!\bigg{(}\\!\frac{\sigma
D}{{\sqrt{MT}}}\\!+\\!\frac{D\sqrt{M}{\mathcal{V}_{1}(T)}}{T}\\!+\\!\frac{\gamma^{2}LD^{2}M^{-1/2}}{T}\\!+\\!\frac{\gamma
GD\sqrt{M}}{T}\bigg{)}. \end{theorem} \par\begin{remark}[The term $\cVoneT$.]
Note that by symmetry ${\mathcal{V}_{m}(T)}=\mathcal{V}_{1}(T)$ for all $m$.
Although a trivial bound on ${\mathcal{V}_{1}(T)}$ is
${\mathcal{V}_{1}(T)}\leq G\sqrt{2T}$, typically we have
${\mathcal{V}_{1}(T)}\ll\sqrt{T}$ in practice \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{duchi2011adaptive, Reddi2018on, chen2018universal,
chen2018on, liu2020towards}{\@@citephrase{(}}{\@@citephrase{)}}}, especially
in the sparse data scenarios. For example, consider the bilinear saddle-point
problem
$\min_{x\in{\mathcal{X}}}\max_{y\in{\mathcal{Y}}}\big{\\{}x^{\top}(\sum_{i=1}^{n}p_{i}M_{i})y\big{\\}}$,
where a larger weight $p_{i}>0$ means the matrix $M_{i}$ appears more
frequently in the dataset. When most of matrices with large weights are row-
sparse and column-sparse, the quantity ${\mathcal{V}_{1}(T)}$ is much smaller
than $G\sqrt{2T}$. Theorem~{}\ref{thm:smooth_noV}, in the appendix, shows that
with a different choice of the base learning rate $\alpha$ one can obtain a
near linear speed-up result, which removes the dependence on
${\mathcal{V}_{1}(T)}$: for large $T$,
$${\mathbb{E}}[\operatorname*{DualGap}(\bar{z})]=\tilde{O}\left(\frac{\sigma
D}{{\sqrt{MT^{1-2\epsilon}}}}+\frac{\gamma^{2}LD^{2}}{T^{1-2\epsilon}}+\frac{LD^{2}M}{T}+\frac{\gamma
GDM^{3/2}}{T^{1+\epsilon}}\right),$$ for any $\epsilon\in(0,\tfrac{1}{2})$.
Following the discussion in \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{chen2018universal,liu2020towards}{\@@citephrase{(}}{\@@citephrase{)}}},
when the cumulative growth of the stochastic gradient is slow, i.e.,
${\mathcal{V}_{1}(T)}=O(T^{b})$ for some $0<b<\tfrac{1}{2}$, then the second
term in~{}\eqref{eq:bound2} is $O(DM^{3/2}/T^{1-b})$ and linear speed-up is
achieved, since as $T\to\infty$, the dominating term become $O(\sigma
D/\sqrt{MT})$. \end{remark} \par\begin{remark}[Extension to unbounded
stochastic gradient oracle] Our analysis can be extended to unbounded
homogeneous and light-tailed oracles using the following argument. Let
\@@amsalign\|G\|_{\infty}\vcentcolon=\sup_{z\in{\mathcal{Z}}}\|G(z)\|_{*}<\infty,
which upper bounds the expectation of the SG oracle. Assume
$\|\tilde{G}(z)-G(z)\|_{*}/\|G\|_{\infty}$ is independent of $z$ and follows
the distribution of the absolute value of a standard normal. Define the set
${\mathcal{Z}}^{\prime}\vcentcolon=\\{{z^{m}_{t}},{\tilde{z}^{m,*}_{t-1}}\\}_{t,m}$
of all iterates. For any $0<\delta<1$, define the event
\@@amsalign{\mathcal{E}}\vcentcolon=\Big{\\{}\max_{z^{\prime}\in{\mathcal{Z}}^{\prime}}\|\tilde{G}(z^{\prime})-G(z^{\prime})\|_{*}\leq
G_{T,\delta}\vcentcolon=\|G\|_{\infty}\cdot\big{(}\sqrt{2\log(4MT)}+\sqrt{2\log(2/\delta)}\big{)}\Big{\\}}.
Then ${\mathbb{P}}({\mathcal{E}})\geq 1-\delta$; see Appendix
\ref{app:unbdsg}. We can repeat the proof of Theorem~{}\ref{thm:nonsmooth} and
Theorem~{}\ref{thm:smooth} on the event ${\mathcal{E}}$ and interpret our
results with $G$ replaced by $G_{T,\delta}$, which effectively substitutes $G$
with $\|G\|_{\infty}$ at the cost of an extra $\log(T)$ factor. \end{remark}
\par\begin{remark}[Baseline 1: Minibatch EG] \par We comment on the
performance of an obvious baseline that implements minibatch stochastic EG
using $M$ workers. Suppose the algorithm takes $R$ extragradient steps, with
each step using a minibatch of size $KM$, resulting in a procedure that
communicates exactly $R$ times. The performance of such a minibatch EG for
general nonsmooth and smooth minimax problems \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{bach2019universal,ene2020adaptive}{\@@citephrase{(}}{\@@citephrase{)}}}
is, respectively, \@@amsalign{O}\bigg{(}\frac{\sigma
D}{\sqrt{KMR}}+\frac{\|G\|_{\infty}D}{\sqrt{R}}\bigg{)}\text{ and
}{O}\bigg{(}\frac{\sigma D}{\sqrt{KMR}}+\frac{LD^{2}}{R}\bigg{)}\,. Under the
same computation and communication structure, our algorithm enjoys adaptivity,
achieves the same linear speed-up in the variance term $\frac{\sigma
D}{\sqrt{KMR}}$, and improves dependence on the gradient upper bound
$\|G\|_{\infty}$ and the smoothness parameter $L$, which is a desirable
property for problems where these parameters are large. \end{remark}
\par\begin{remark}[Baseline 2: EG on a single worker] Another natural baseline
is to run EG on a single worker for $T$ iterations with batch-size equal to
one. The convergence rates for this procedure in nonsmooth and smooth cases
are $O(\sigma D/\sqrt{T}+\|G\|_{\infty}D/\sqrt{T})$ and $O(\sigma
D/\sqrt{T}+LD^{2}/T)$, respectively. In the smooth case, EG on a single worker
is inferior to minibatch EG, since the dominant term for the former is
$1/\sqrt{T}$, but it is $1/\sqrt{MT}$ for the latter. On the other hand, in
the nonsmooth case, minibatch EG reduces the variance term, but the term
involving the deterministic part degrades. Therefore, in the nonsmooth case,
we can only claim that the minibatch EG is better than the single-worker mode
in the noise-dominant regime $\sigma=\Omega(\|G\|_{\infty}\sqrt{M})$.
\end{remark} \par\par\begin{remark}[On the choice of $K$] Consider the
baseline minibatch EG (see \lx@cref{creftype~refnum}{rm:minibatch_EG}) which
runs as follows: the algorithm takes $R$ extragradient steps, with each step
using a minibatch of size $KM$, resulting in a procedure that communicates
exactly $R$ times. Note this procedure has exactly the same computation and
communication structure as ${\operatorname*{{LocalAdaSEG}}}$, facilitating a
fair comparison. In the non-smooth case, our theory shows that
${\operatorname*{{LocalAdaSEG}}}$ dominates minibatch EG regardless of the
choice $K$. Therefore, let us focus the discussion on the \emph{smooth loss
with slow gradient growth case}. Suppose that the gradient growth term
$\mathcal{V}_{m}(T):=\mathbb{E}\big{[}(\sum_{t=1}^{T}\left\|g_{t}^{m}\right\|_{*}^{2}+\left\|M_{t}^{m}\right\|_{*}^{2})^{1/2}\big{]}$
admits a rate $\mathcal{V}_{m}(T)=O(T^{b})$ for some $0<b<1/2$. Theorem 2 then
shows that ${\operatorname*{{LocalAdaSEG}}}$ enjoys a convergence rate
(ignoring problem parameters $L,D$ and $G$)
\@@amsalign\frac{1}{\sqrt{MKR}}+\frac{\sqrt{M}}{(KR)^{1-b}}+\frac{\sqrt{M}}{KR}\;,
where $M$ is the number of machines, $R$ the communication rounds, and $K$ is
the length between two communications. The minibatch EG attains the
convergence rate \@@amsalign\frac{1}{\sqrt{MKR}}+\frac{1}{R}\;. Both
algorithms achieve linear speedup, i.e., the dominant term is
$O(\sigma/\sqrt{MKR})$. In order for ${\operatorname*{{LocalAdaSEG}}}$ to be
comparable with minibatch EG in the higher order term, we set
$\sqrt{M}/(KR)^{1-b}=\Theta(1/R)$ and $\sqrt{M}/(KR)=O(1/R)$ and obtain
$K=\Theta(\sqrt{M}T^{b})$. With this choice of $K$,
${\operatorname*{{LocalAdaSEG}}}$ achieves a communication efficiency no worse
than minibatch EG with the crucial advantage of being tuning-free. Compared
with case of optimizing strongly-convex functions, local SGD needs
$K=O(\sqrt{T})$ to achieve linear speedup \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{stich2018local}{\@@citephrase{(}}{\@@citephrase{)}}}. The
discussion here is purely theoretical, since the exponent of gradient growth
$b$ is hard to estimate in practice. \end{remark}
\par\par\par\@@unnumbered@section{paragraph}{toc}{Proof Sketch of Theorem
\ref{thm:smooth}} We present a proof sketch for the smooth case. Recall the
update formula
\@@amsalign{z^{m}_{t}}&=\Pi_{{\mathcal{Z}}}[{\tilde{z}^{m,*}_{t-1}}-{\eta^{m}_{t}}{M^{m}_{t}}]&&\text{
with }{M^{m}_{t}}=\tilde{G}({\tilde{z}^{m,*}_{t-1}}),\\\
{\tilde{z}^{m}_{t}}&=\Pi_{{\mathcal{Z}}}[{\tilde{z}^{m,*}_{t-1}}-{\eta^{m}_{t}}{g^{m}_{t}}]&&\text{
with }{g^{m}_{t}}=\tilde{G}({z^{m}_{t}}).
\lx@cref{creftype~refnum}{fig:computation} provides a computation diagram and
illustrates the relationship between the above variables. \begin{figure}[ht]
\centering\includegraphics[scale={.6}]{computation.pdf}
\@@toccaption{{\lx@tag[ ]{{2}}{The computation diagram for
${\operatorname*{{LocalAdaSEG}}}$. Left panel: computation on machine $m$ when
no communication ($t\notin S$). Right panel: computation on machine $m$ when
on communication round ($t\in S$)}}}\@@caption{{\lx@tag[: ]{{Figure 2}}{The
computation diagram for ${\operatorname*{{LocalAdaSEG}}}$. Left panel:
computation on machine $m$ when no communication ($t\notin S$). Right panel:
computation on machine $m$ when on communication round ($t\in S$)}}}
\@add@centering\end{figure} \par We define the noise in the gradient operator
$G$ by
\@@amsalign{\xi^{m}_{t}}\vcentcolon=G({z^{m}_{t}})-{g^{m}_{t}}=G({z^{m}_{t}})-\tilde{G}({z^{m}_{t}}).
Moreover, we define a gradient-like quantity
$$\left(Z_{t}^{m}\right)^{2}:=\frac{\left\|z_{t}^{m}-\tilde{z}_{t-1}^{m,
*}\right\|^{2}+\left\|z_{t}^{m}-\tilde{z}_{t}^{m}\right\|^{2}}{5\left(\eta_{t}^{m}\right)^{2}}.
$$ If we ignore the projection operator in the update, the term $(Z_{t}^{m})$
will be of a similar scale as the gradients $\tilde{G}({z^{m}_{t}})$ and
$\tilde{G}({\tilde{z}^{m}_{t}})$. \par\par We begin with the following
decomposition: for all $z\in{\mathcal{Z}}$,
\@@amsalign&{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\big{\langle}{z^{m}_{t}}-z,G({z^{m}_{t}})\big{\rangle}\\\
&={\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\big{\langle}{z^{m}_{t}}-z,{\xi^{m}_{t}}\rangle+{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\langle{z^{m}_{t}}-z,{g^{m}_{t}}\rangle\\\
&\leq\underbracket{{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\big{\langle}{z^{m}_{t}}-z,{\xi^{m}_{t}}\big{\rangle}}_{{I}(z)}\\\
&\quad+\underbracket{{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\frac{1}{{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\tilde{z}^{m,*}_{t-1}}\|^{2}-\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}}_{{II}(z)}\\\
&\quad\underbracket{-{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\frac{1}{{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}+\tfrac{1}{2}\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}}_{{III}}\\\
&\quad+\underbracket{{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\|{g^{m}_{t}}-{M^{m}_{t}}\|_{*}\cdot\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|}_{{IV}},
where we have used a descent lemma for EG updates common in the literature
(Lemma 4 in our paper). The reason we care about the above quantity is that by
the convexity-concavity of the problem, the duality gap metric can be upper-
bounded by this term. \par Next, we analyze each term separately. The term
$I(z)$ characterizes the noise of the problem and eventually contributes to
the noise term $\frac{\sigma}{\sqrt{KMR}}$. For the term $II$ we use a
telescoping argument and show that it can be upper bounded by
$\sum_{m,t}{\eta^{m}_{t}}{(Z^{m}_{t})^{2}}$. The telescoping argument can be
applied due to the averaging weights $w^{m}_{t}$ in the algorithm. The term
$III$ is negative. We keep the tail part of $III$ which cancels the tail part
of the term $IV$. For the term $IV$ we use the smoothness property of the
problem and show that it can be bounded by
$\sum_{m,t}{(\eta^{m}_{t})^{2}}{(Z^{m}_{t})^{2}}$. Finally, two sums of the
form $\sum_{m,t}{\eta^{m}_{t}}{(Z^{m}_{t})^{2}}$ and
$\sum_{m,t}{(\eta^{m}_{t})^{2}}{(Z^{m}_{t})^{2}}$ remain to be handled. For
this we use the well-known basic inequality
$\sum_{i=1}^{n}{a_{i}}/({a_{0}+\sum_{j=1}^{i-1}a_{j}})=O(\log(1+\sum_{i}a_{i}))$
and
$\sum_{i=1}^{n}{a_{i}}/{\sqrt{a_{0}+\sum_{j=1}^{i-1}a_{j}}}=\Theta(\sqrt{\sum_{i}a_{i}})$
for positive numbers $a_{i}$'s. \par\par Nonadaptive local algorithms rely on
choosing a vanishing stepsize that is usually inversely proportional to a
prespecified number of total iterations $T$. The freedom to choose the
stepsize based on a prespecified $T$ is crucial in the proofs of these
algorithms and allows canceling of the asynchronicity of updates caused by
local updates and the bias in those updates caused by data heterogeneity. This
is the case for both convex optimization and convex-concave optimization.
However, in the adaptive algorithm regimes, such a proof technique is clearly
not viable. \par Our algorithm requires a carefully designed iterates
averaging scheme, with weight inversely proportional to stepsize. Such
averaging-scheme is designed to account for the asynchronicity of local
iterates and is automatically determined by the optimization process. This is
what enables the extension of an Adam-type stepsize to parallel settings,
which is highly nontrivial.
\par\par\par\@@numbered@section{section}{toc}{Experiments} \par We apply
${\operatorname*{{LocalAdaSEG}}}$ to the stochastic bilinear minimax problem
introduced in \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{gidel2018a,beznosikov2021distributed}{\@@citephrase{(}}{\@@citephrase{)}}}
and train the Wasserstein generative adversarial neural network (Wasserstein
GAN) \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{arjovsky2017wasserstein}{\@@citephrase{(}}{\@@citephrase{)}}}.
For the homogeneous setting, to demonstrate the efficiency of our proposed
algorithm, we compare ${\operatorname*{{LocalAdaSEG}}}$ with minibatch
stochastic extragradient gradient descent (MB-SEGDA)
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{nemirovski2004prox}{\@@citephrase{(}}{\@@citephrase{)}}},
minibatch universal mirror-prox (MB-UMP) \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{bach2019universal}{\@@citephrase{(}}{\@@citephrase{)}}},
minibatch adaptive single-gradient mirror-Prox (MB-ASMP)
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{ene2020adaptive}{\@@citephrase{(}}{\@@citephrase{)}}},
extra step local SGD (LocalSEGDA) \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{beznosikov2021distributed}{\@@citephrase{(}}{\@@citephrase{)}}},
and local stochastic gradient descent ascent (LocalSGDA)
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{deng2020local}{\@@citephrase{(}}{\@@citephrase{)}}}. We
further extend the proposed ${\operatorname*{{LocalAdaSEG}}}$ algorithm to
solve federated WGANs with a heterogeneous dataset to verify its efficiency.
\leavevmode\color[rgb]{0,0,1}\ignorespaces To validate the practicality of
${\operatorname*{{LocalAdaSEG}}}$, we also train the BigGAN
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{brock2018large}{\@@citephrase{(}}{\@@citephrase{)}}} over
CIFAR10 dataset under the heterogeneous setting. In this setting, we also
compare ${\operatorname*{{LocalAdaSEG}}}$ with Local Adam
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{beznosikov2021distributed}{\@@citephrase{(}}{\@@citephrase{)}}}.
We emphasize here that whether Local Adam converges is still an open question,
even for the stochastic convex-concave setting.
\par\begin{figure*}\centering\begin{@subfigure}
\includegraphics[width=195.12767pt]{
diff_local_iter_with_total_iter_sigma0-1}\end{@subfigure} \begin{@subfigure}
\includegraphics[width=195.12767pt]{
diff_local_iter_with_round_sigma0-1}\end{@subfigure} \begin{@subfigure}
\includegraphics[width=195.12767pt]{
diff_local_iter_with_total_iter_sigma0-5}\end{@subfigure} \begin{@subfigure}
\includegraphics[width=195.12767pt]{
diff_local_iter_with_round_sigma0-5}\end{@subfigure}
\par\@@toccaption{{\lx@tag[ ]{{3}}{\small Subfigures (a)-(b) and (c)-(d) plot
the residual of ${\operatorname*{{LocalAdaSEG}}}$ against the total number of
iterations $T$ and communications $R$, with varying numbers of local
iterations $K$. We also investigate the effect of noise level ($\sigma=0.1$ in
(a)(b) and $\sigma=0.5$ in (c)(d)). }}}\@@caption{{\lx@tag[: ]{{Figure
3}}{\small Subfigures (a)-(b) and (c)-(d) plot the residual of
${\operatorname*{{LocalAdaSEG}}}$ against the total number of iterations $T$
and communications $R$, with varying numbers of local iterations $K$. We also
investigate the effect of noise level ($\sigma=0.1$ in (a)(b) and $\sigma=0.5$
in (c)(d)). }}} \@add@centering\end{figure*}
\par\begin{figure*}\centering\begin{@subfigure}
\includegraphics[width=195.12767pt]{
diff_opt_with_total_iter_sigma0-1}\end{@subfigure} \begin{@subfigure}
\includegraphics[width=195.12767pt]{
diff_opt_with_round_sigma0-1}\end{@subfigure} \par\begin{@subfigure}
\includegraphics[width=195.12767pt]{
diff_opt_with_total_iter_sigma0-5}\end{@subfigure} \begin{@subfigure}
\includegraphics[width=195.12767pt]{
diff_opt_with_round_sigma0-5}\end{@subfigure} \par\@@toccaption{{\lx@tag[
]{{4}}{\small Subfigures (a)-(b) and (c)-(d) compare
${\operatorname*{{LocalAdaSEG}}}$ with existing optimizers. We plot the
residuals against the total number of iterations $T$ and communications $R$
with different noise levels ($\sigma=0.1$ in (a)(b) and $\sigma=0.5$ in
(c)(d)).}}}\@@caption{{\lx@tag[: ]{{Figure 4}}{\small Subfigures (a)-(b) and
(c)-(d) compare ${\operatorname*{{LocalAdaSEG}}}$ with existing optimizers. We
plot the residuals against the total number of iterations $T$ and
communications $R$ with different noise levels ($\sigma=0.1$ in (a)(b) and
$\sigma=0.5$ in (c)(d)).}}} \vspace{0cm} \@add@centering\end{figure*}
\par\par\@@numbered@section{subsection}{toc}{Stochastic bilinear minimax
problem} We consider the stochastic bilinear minimax problem with box
constraints \@@amsalign\min_{x\in C^{n}}\max_{y\in C^{n}}F(x,y) where
\@@amsalign F(x,y)\vcentcolon={\mathbb{E}}_{\xi\sim
P}\big{[}x^{\top}Ay+(b+\xi)^{\top}x+(c+\xi)^{\top}y\big{]}, Here
$C^{n}=[-1,1]^{n}$ is a box in ${{\mathbb{R}}}^{n}$, the tuple $(A,b,c)$ is
deterministic, and the perturbation variable $\xi$ follows the normal
distribution with variance $\sigma$. We define the KKT residual ${\rm
Res}(x,y)$ as: \@@amsalign{\rm
Res}(x,y)^{2}\vcentcolon=&\|x-\Pi_{C^{n}}\big{(}x-(Ay+b)\big{)}\|^{2}\\\
&+\|y-\Pi_{C^{n}}\big{(}y+(Ax+c)\big{)}\|^{2}. It is not hard to verify that
given $(x^{*},y^{*})\in\mathbb{R}^{n}\times\mathbb{R}^{n}$, ${\rm
Res}(x^{*},y^{*})=0$ if and only if $(x^{*},y^{*})$ belongs to the set of
saddle-points of the bilinear minimax problem \eqref{spp-bilinear}. During
experiments, we use ${\rm Res}(x,y)$ to measure the quality of the approximate
solution obtained by different optimizers. \par{\bf Dataset Generation.}\ We
uniformly generate $b$ and $c$ in $[-1,1]^{n}$ with $n=10$. The symmetric
matrix $A$ is constructed as
$A={\bar{A}}/{\max\big{(}\mbox{{}\rm\sf\leavevmode\hbox{}\hbox{}b\/}_{\max},
\mbox{{}\rm\sf\leavevmode\hbox{}\hbox{}c}_{\max}\big{)}}$,where$\bar{A}\in[-1,
1]^{n \times
n}$isarandomsymmetricmatrix.Weemphasizethat$A$ismerelysymmetric,butnotsemi-
definite.Tosimulatethedistributedenvironment,wedistribute$(A, b,
c)$to$M$workers,where$M =
4$.Eachworkersolvestheabovebilinearproblemlocallywithanoptimizationalgorithm.Weinstantiate${\operatorname*{{LocalAdaSEG}}}$withdifferentnumbersoflocaliterations$K
\in\\{1, 5, 10, 50, 100, 250, 500\\}$,anddifferentnoiselevels$\sigma\in\\{0.1,
0.5\\}$,shownin\lx@cref{creftype~refnum}{fig:diff_local_iter}.Alarger$\sigma$indicatesmorenoiseinthestochasticgradients,makingproblem~{}\eqref{spp-
bilinear}harder.Furthermore,wecompare${\operatorname*{{LocalAdaSEG}}}$bysettingthelocaliteration$K
=
50$againstseveralexistingoptimizers,illustratedin\lx@cref{creftype~refnum}{fig:diff_local_iter_agaisnt_SOTA}.\par{\bf
ExperimentalResults.}\
In\lx@cref{creftype~refnum}{fig:diff_local_iter},${\operatorname*{{LocalAdaSEG}}}$providesstableconvergenceresultsunderdifferentconfigurationsoflocaliterations$K$andnoiselevels$\sigma$.Figure(b)(d)illustratesthatasuitablylarge$K$couldacceleratetheconvergencespeedof${\operatorname*{{LocalAdaSEG}}}$.Figure(a)(c)illustratesthatalargevariancewouldresultinunstableoptimizationtrajectories.Thefindingsoftheexperimentagreewithourtheoreticalpredictions:(i)alarger$T=KR$improvesconvergence\mathchar
24635\relax\;(ii)thevariancetermdominatestheconvergencerateof${\operatorname*{{LocalAdaSEG}}}$\mathchar
24635\relax\;alargevariancetermwillslowdown${\operatorname*{{LocalAdaSEG}}}$.In\lx@cref{creftype~refnum}{fig:diff_local_iter_agaisnt_SOTA},(a)(c)illustratethatadaptivevariantsofstochasticminimaxoptimizers,i.e.,${\operatorname*{{LocalAdaSEG}}}$,MB-
UMP,andMB-
ASMP,achievebetterperformancecomparedtostandardonessuchasLocalSGDA,LocalSEGDA,andMB-
SEGDA,whoselearningratesarehardtotuneforminimaxproblems.Furthermore,whencomparedintermsofcommunicationroundsin(b)(d),${\operatorname*{{LocalAdaSEG}}}$convergesfasterthanotherdistributedstochasticminimaxoptimizers,demonstratingthesuperiorityof${\operatorname*{{LocalAdaSEG}}}$.\par\par
Tovalidatetheperformanceofourproposedmethod,weconductthecomparisonoftheasynchronouscaseandthesynchronouscaseof${\operatorname*{{LocalAdaSEG}}}$forthestochasticbilinearminimaxproblem.Wealsocompareasynchronousandsynchronouscaseswiththesingle-
threadversion(SEGDAwithMKRiterations)fromtheaspectsofresidualandwallclocktime.Finally,weevaluatethequantityof$V_t$withtheupdate$t$.TheexperimentaldetailsaredescribedinAppendix\ref{app:add_exp}.Ascanbeseenin\lx@cref{creftype~refnum}{fig:additional_exp}(inAppendix\ref{app:add_exp}),comparedwithsynchronouscases,asynchronicityonlyaffectstheconvergenceratethatisslowerthanthesynchronousversionwithrespecttothecommunicationrounds.ComparedtoSEGDAofMKRiterations,ourproposed${\operatorname*{{LocalAdaSEG}}}$canachievemorestableandbetterperformance.Regardingthequantityof$Vt$,itisreallymuchsmallerthanthedominantvarianceterm.\par\par\par\par\@@numbered@section{subsection}{toc}{Wasserstein
GAN} \par We train Wasserstein GAN (WGAN) to validate the efficiency of
${\operatorname*{{LocalAdaSEG}}}$ on a real-world application task. This is a
challenging minimax problem as the objectives of both generator and
discriminator are non-convex and non-concave. The description of the problem
and implementation details are placed in \lx@cref{creftype~refnum}{wgan-
discription}. \par\par\par\par\par{\bf Experimental results.} Fig.
\ref{fig:wgan_iid_agaisnt_SOTA} and \ref{fig:wgan_noniid_agaisnt_SOTA} (in
\lx@cref{creftype~refnum}{wgan-discription}) compare MB-UMP, MB-ASMP,
LocalAdam and ${\operatorname*{{LocalAdaSEG}}}$ in a homogeneous and
heterogeneous setting, respectively. In
\lx@cref{creftype~refnum}{fig:wgan_iid_agaisnt_SOTA}(a) and
\lx@cref{creftype~refnum}{fig:wgan_noniid_agaisnt_SOTA}(a), MB-UMP, MB-ASMP,
LocalAdam and ${\operatorname*{{LocalAdaSEG}}}$ quickly converge to a solution
with a low FID value. However, when compared in terms of communication rounds
in \lx@cref{creftype~refnum}{fig:wgan_iid_agaisnt_SOTA}(b) and
\lx@cref{creftype~refnum}{fig:wgan_noniid_agaisnt_SOTA}(b),
${\operatorname*{{LocalAdaSEG}}}$ and Local Adam converge faster than other
optimizers and reach a satisfactory solution in just a few rounds. In
\lx@cref{creftype~refnum}{fig:wgan_iid_agaisnt_SOTA}(c) and
\lx@cref{creftype~refnum}{fig:wgan_noniid_agaisnt_SOTA}(c), all the listed
optimizers achieve a high IS. In particular, the IS of
${\operatorname*{{LocalAdaSEG}}}$ and Local Adam increases much faster with
less communication than MB-UMP, MB-ASMP as shown in
\lx@cref{creftype~refnum}{fig:wgan_iid_agaisnt_SOTA}(d) and
\lx@cref{creftype~refnum}{fig:wgan_noniid_agaisnt_SOTA}(d). \par In
\lx@cref{creftype~refnum}{fig:wgan_under_diff_dist} and
\lx@cref{creftype~refnum}{fig:compare_wgan_under_diff_dist}, we show and
compare the FID and IS of ${\operatorname*{{LocalAdaSEG}}}$ with other
optimizers under different data distributions. As can be seen from
\lx@cref{creftype~refnum}{fig:wgan_under_diff_dist},
${\operatorname*{{LocalAdaSEG}}}$ converges faster when the Dirichlet
distribution parameter $\alpha$ decreases. In
\lx@cref{creftype~refnum}{fig:compare_wgan_under_diff_dist}, when data
distribution changes, our ${\operatorname*{{LocalAdaSEG}}}$ can still converge
faster than other existing optimizers.
\par\par\par\@@numbered@section{subsection}{toc}{BigGAN} To validate the
practicability of our proposed ${\operatorname*{{LocalAdaSEG}}}$ method, we
apply LocaAdaSEG to train the large-scale BigGAN \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{brock2018large}{\@@citephrase{(}}{\@@citephrase{)}}} model
over the CIFAR10 dataset. The description of BigGAN and parameter setup are
placed in $\lx@cref{creftype~refnum}{biggan_cifar10}$. \par{\bf Experimental
results.} \lx@cref{creftype~refnum}{fig:bigGAN_FID_IS} illustrates the
comparison of the FID and IS against communication rounds by using
${\operatorname*{{LocalAdaSEG}}}$ and existing optimizers. As can be seen from
\lx@cref{creftype~refnum}{fig:bigGAN_FID_IS}(a),
${\operatorname*{{LocalAdaSEG}}}$ and Local Adam can reach a satisfactory FID
value in a few rounds. Similarly, from
\lx@cref{creftype~refnum}{fig:bigGAN_FID_IS}(b), we can see that the IS value
of ${\operatorname*{{LocalAdaSEG}}}$ and Local Adam is much higher than that
of MB-UMP and MB-ASMP. In a word, the FID and IS values of
${\operatorname*{{LocalAdaSEG}}}$ and Local Adam converge much faster than
that of other optimizers.
\par\par\par\@@unnumbered@section{paragraph}{toc}{Additional Discussions} To
end this section, we briefly discuss the limitation of current work. \par
Theoretical limitations. Our theory is applicable to the homogeneous setting,
meaning each worker has access to data from one distribution. However, in
practice, data heterogeneity is a main factor practitioners must take into
account for distributed learning. We briefly discuss technical challenges
here. For the heterogeneous case, the theory for \emph{non-adaptive}
algorithms relies on choosing a very small stepsize, usually inverse
proportional to a prespecified number of total iterations $T$. The freedom to
choose the stepsize based on a prespecified $T$ is crucial in those proofs and
enables canceling the bias caused by local updates, a.k.a.\ client drifts. The
same situation also occurs in the convex optimization case. However, our goal
is to have an adaptive algorithm that does not depend on the problem
parameters or a prespecified $T$. For this reason, we leave such an important
open question for future work. \par Experimental limitations. In the scale of
the dataset, we experimented with should be increased to showcase the
computation benefit of the proposed algorithm. At the current stage we have
experimented with MNIST data and further, add CIFAR 10 experiments after
reviewers' suggestions. Application to other ultra-large datasets such as
ImageNet requires significant engineering efforts and will be left for future
investigation. We should emphasize that our paper mainly contributes to the
theoretical understanding of adaptive algorithms in distributed settings.
\par\par\par\@@numbered@section{section}{toc}{Conclusion} We proposed an
adaptive communication-efficient distributed stochastic extragradient
algorithm in the Parameter-Server model for stochastic convex-concave minimax
problem, ${\operatorname*{{LocalAdaSEG}}}$. We theoretically showed
${\operatorname*{{LocalAdaSEG}}}$ that achieves the optimal convergence rate
with a linear speed-up property for both nonsmooth and smooth objectives.
Experiments verify our theoretical results and demonstrate the efficiency of
${\operatorname*{{LocalAdaSEG}}}$. \par For future work, since that the
current analysis merely holds for the homogeneous setting, a promising
direction is to extend the theoretical result of
${\operatorname*{{LocalAdaSEG}}}$ to the heterogeneous setting that better
models various real-world applications, such as federated GANs
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{beznosikov2021distributed}{\@@citephrase{(}}{\@@citephrase{)}}}
and robust federated learning \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{NEURIPS2020_ac450d10}{\@@citephrase{(}}{\@@citephrase{)}}}.
In addition, extending theoretical results from the stochastic convex-concave
setting to the stochastic nonconvex-(non)concave setting is an interesting and
challenging research direction.
\par\par\par\@@unnumbered@section{section}{}{Declarations} \par\begin{itemize}
\par\itemize@item@Funding (This work is supported by the Major Science and
Technology Innovation 2030 “Brain Science and Brain-like Research” key project
(No. 2021ZD0201405).) \par\itemize@item@Conflict of interest/Competing
interests (The authors declare that they have no conflict of interest.)
\par\itemize@item@Ethics approval (Not Applicable.) \par\itemize@item@Consent
to participate (Not Applicable.) \par\itemize@item@Consent for publication
(Not Applicable.) \par\itemize@item@Availability of data and materials (The
data used in this work is all public.) \par\itemize@item@Code availability
(The codes of the proposed method will be released after publishing.)
\par\itemize@item@Authors' contributions (All authors contributed to the study
conception and design. The first draft of the manuscript was written by
Luofeng Liao, and all authors commented on previous versions of the
manuscript. All authors read and approved the final manuscript.)
\par\end{itemize} \par\noindent If any of the sections are not relevant to
your manuscript, please include the heading and write `Not applicable' for
that section. \par\vskip 12.0pt plus 4.0pt minus
4.0pt\begin{flushleft}Editorial Policies for: \par\vskip 12.0pt plus 4.0pt
minus 4.0pt\noindent Springer journals and proceedings:
\url{https://www.springer.com/gp/editorial-policies} \par\vskip 12.0pt plus
4.0pt minus 4.0pt\noindent Nature Portfolio journals:
\url{https://www.nature.com/nature-research/editorial-policies} \par\vskip
12.0pt plus 4.0pt minus 4.0pt\noindent{Scientific Reports}:
\url{https://www.nature.com/srep/journal-policies/editorial-policies}
\par\vskip 12.0pt plus 4.0pt minus 4.0pt\noindent BMC journals:
\url{https://www.biomedcentral.com/getpublished/editorial-policies}
\end{flushleft}
\par\thebibliography\@@lbibitem{antonakopoulos2021adaptive}\NAT@@wrout{1}{}{}{}{(1)}{antonakopoulos2021adaptive}\lx@bibnewblock
K.~{}Antonakopoulos, V.~{}Belmega, and P.~{}Mertikopoulos. \lx@bibnewblock
Adaptive extra-gradient methods for min-max optimization and games.
\lx@bibnewblock In {\em International Conference on Learning Representations},
2021.
\par\@@lbibitem{arjovsky2017towards}\NAT@@wrout{2}{}{}{}{(2)}{arjovsky2017towards}\lx@bibnewblock
M.~{}Arjovsky and L.~{}Bottou. \lx@bibnewblock Towards principled methods for
training generative adversarial networks. \lx@bibnewblock{\em arXiv preprint
arXiv:1701.04862}, 2017.
\par\@@lbibitem{arjovsky2017wasserstein}\NAT@@wrout{3}{}{}{}{(3)}{arjovsky2017wasserstein}\lx@bibnewblock
M.~{}Arjovsky, S.~{}Chintala, and L.~{}Bottou. \lx@bibnewblock Wasserstein
generative adversarial networks. \lx@bibnewblock In D.~{}Precup and Y.~{}W.
Teh, editors, {\em Proceedings of the 34th International Conference on Machine
Learning, {ICML} 2017, Sydney, NSW, Australia, 6-11 August 2017}, volume~{}70
of {\em Proceedings of Machine Learning Research}, pages 214--223. {PMLR},
2017.
\par\@@lbibitem{azizian2020tight}\NAT@@wrout{4}{}{}{}{(4)}{azizian2020tight}\lx@bibnewblock
W.~{}Azizian, I.~{}Mitliagkas, S.~{}Lacoste-Julien, and G.~{}Gidel.
\lx@bibnewblock A tight and unified analysis of gradient-based methods for a
whole spectrum of differentiable games. \lx@bibnewblock In {\em International
Conference on Artificial Intelligence and Statistics}, pages 2863--2873. PMLR,
2020.
\par\@@lbibitem{babanezhad2020geometry}\NAT@@wrout{5}{}{}{}{(5)}{babanezhad2020geometry}\lx@bibnewblock
R.~{}Babanezhad and S.~{}Lacoste-Julien. \lx@bibnewblock Geometry-aware
universal mirror-prox. \lx@bibnewblock{\em arXiv preprint arXiv:2011.11203},
2020.
\par\@@lbibitem{bach2019universal}\NAT@@wrout{6}{}{}{}{(6)}{bach2019universal}\lx@bibnewblock
F.~{}Bach and K.~{}Y. Levy. \lx@bibnewblock A universal algorithm for
variational inequalities adaptive to smoothness and noise. \lx@bibnewblock In
{\em Conference on Learning Theory}, pages 164--194. PMLR, 2019.
\par\@@lbibitem{beznosikov2021distributed}\NAT@@wrout{7}{}{}{}{(7)}{beznosikov2021distributed}\lx@bibnewblock
A.~{}Beznosikov, V.~{}Samokhin, and A.~{}Gasnikov. \lx@bibnewblock Distributed
saddle-point problems: Lower bounds, optimal algorithms and federated gans.
\lx@bibnewblock{\em arXiv preprint arXiv:2010.13112}, 2021.
\par\@@lbibitem{brock2018large}\NAT@@wrout{8}{}{}{}{(8)}{brock2018large}\lx@bibnewblock
A.~{}Brock, J.~{}Donahue, and K.~{}Simonyan. \lx@bibnewblock Large scale gan
training for high fidelity natural image synthesis. \lx@bibnewblock In {\em
International Conference on Learning Representations}, 2019.
\par\@@lbibitem{Chambolle2010}\NAT@@wrout{9}{}{}{}{(9)}{Chambolle2010}\lx@bibnewblock
A.~{}Chambolle and T.~{}Pock. \lx@bibnewblock A first-order primal-dual
algorithm for convex problems with~{}applications to imaging.
\lx@bibnewblock{\em Journal of Mathematical Imaging and Vision}, 40(1):120--
145, Dec. 2010.
\par\@@lbibitem{Chatterjee2014}\NAT@@wrout{10}{}{}{}{(10)}{Chatterjee2014}\lx@bibnewblock
S.~{}Chatterjee. \lx@bibnewblock{\em Superconcentration and Related Topics}.
\lx@bibnewblock Springer International Publishing, 2014.
\par\@@lbibitem{chen2021quantized}\NAT@@wrout{11}{}{}{}{(11)}{chen2021quantized}\lx@bibnewblock
C.~{}Chen, L.~{}Shen, H.~{}Huang, and W.~{}Liu. \lx@bibnewblock Quantized adam
with error feedback. \lx@bibnewblock{\em ACM Transactions on Intelligent
Systems and Technology (TIST)}, 12(5):1--26, 2021.
\par\@@lbibitem{chen2021towards}\NAT@@wrout{12}{}{}{}{(12)}{chen2021towards}\lx@bibnewblock
C.~{}Chen, L.~{}Shen, F.~{}Zou, and W.~{}Liu. \lx@bibnewblock Towards
practical adam: Non-convexity, convergence theory, and mini-batch
acceleration. \lx@bibnewblock{\em arXiv preprint arXiv:2101.05471}, 2021.
\par\@@lbibitem{chen2021cada}\NAT@@wrout{13}{}{}{}{(13)}{chen2021cada}\lx@bibnewblock
T.~{}Chen, Z.~{}Guo, Y.~{}Sun, and W.~{}Yin. \lx@bibnewblock Cada:
Communication-adaptive distributed adam. \lx@bibnewblock In {\em International
Conference on Artificial Intelligence and Statistics}, pages 613--621. PMLR,
2021.
\par\@@lbibitem{chen2018on}\NAT@@wrout{14}{}{}{}{(14)}{chen2018on}\lx@bibnewblock
X.~{}Chen, S.~{}Liu, R.~{}Sun, and M.~{}Hong. \lx@bibnewblock On the
convergence of a class of adam-type algorithms for non-convex optimization.
\lx@bibnewblock In {\em International Conference on Learning Representations},
2019.
\par\@@lbibitem{chen2020distributed}\NAT@@wrout{15}{}{}{}{(15)}{chen2020distributed}\lx@bibnewblock
X.~{}Chen, S.~{}Yang, L.~{}Shen, and X.~{}Pang. \lx@bibnewblock A distributed
training algorithm of generative adversarial networks with quantized
gradients. \lx@bibnewblock{\em arXiv preprint arXiv:2010.13359}, 2020.
\par\@@lbibitem{Chen2014}\NAT@@wrout{16}{}{}{}{(16)}{Chen2014}\lx@bibnewblock
Y.~{}Chen, G.~{}Lan, and Y.~{}Ouyang. \lx@bibnewblock Optimal primal-dual
methods for a class of saddle point problems. \lx@bibnewblock{\em{SIAM}
Journal on Optimization}, 24(4):1779--1814, Jan. 2014.
\par\@@lbibitem{chen2017accelerated}\NAT@@wrout{17}{}{}{}{(17)}{chen2017accelerated}\lx@bibnewblock
Y.~{}Chen, G.~{}Lan, and Y.~{}Ouyang. \lx@bibnewblock Accelerated schemes for
a class of variational inequalities. \lx@bibnewblock{\em Mathematical
Programming}, 165(1):113--149, June 2017.
\par\@@lbibitem{chen2018universal}\NAT@@wrout{18}{}{}{}{(18)}{chen2018universal}\lx@bibnewblock
Z.~{}Chen, Z.~{}Yuan, J.~{}Yi, B.~{}Zhou, E.~{}Chen, and T.~{}Yang.
\lx@bibnewblock Universal stagewise learning for non-convex problems with
convergence on averaged solutions. \lx@bibnewblock In {\em International
Conference on Learning Representations}, 2019.
\par\@@lbibitem{daskalakis2018training}\NAT@@wrout{19}{}{}{}{(19)}{daskalakis2018training}\lx@bibnewblock
C.~{}Daskalakis, A.~{}Ilyas, V.~{}Syrgkanis, and H.~{}Zeng. \lx@bibnewblock
Training {GAN}s with optimism. \lx@bibnewblock In {\em International
Conference on Learning Representations}, 2018.
\par\@@lbibitem{delage2010distributionally}\NAT@@wrout{20}{}{}{}{(20)}{delage2010distributionally}\lx@bibnewblock
E.~{}Delage and Y.~{}Ye. \lx@bibnewblock Distributionally robust optimization
under moment uncertainty with application to data-driven problems.
\lx@bibnewblock{\em Operations research}, 58(3):595--612, 2010.
\par\@@lbibitem{deng2009imagenet}\NAT@@wrout{21}{}{}{}{(21)}{deng2009imagenet}\lx@bibnewblock
J.~{}Deng, W.~{}Dong, R.~{}Socher, L.-J. Li, K.~{}Li, and L.~{}Fei-Fei.
\lx@bibnewblock Imagenet: A large-scale hierarchical image database.
\lx@bibnewblock In {\em 2009 IEEE conference on computer vision and pattern
recognition}, pages 248--255. Ieee, 2009.
\par\@@lbibitem{NEURIPS2020_ac450d10}\NAT@@wrout{22}{}{}{}{(22)}{NEURIPS2020_ac450d10}\lx@bibnewblock
Y.~{}Deng, M.~{}M. Kamani, and M.~{}Mahdavi. \lx@bibnewblock Distributionally
robust federated averaging. \lx@bibnewblock In {\em Advances in Neural
Information Processing Systems}, volume~{}33, pages 15111--15122. Curran
Associates, Inc., 2020.
\par\@@lbibitem{deng2020local}\NAT@@wrout{23}{}{}{}{(23)}{deng2020local}\lx@bibnewblock
Y.~{}Deng and M.~{}Mahdavi. \lx@bibnewblock Local stochastic gradient descent
ascent: Convergence analysis and communication efficiency. \lx@bibnewblock In
{\em Proceedings of The 24th International Conference on Artificial
Intelligence and Statistics}, volume 130 of {\em Proceedings of Machine
Learning Research}, pages 1387--1395. PMLR, 13--15 Apr 2021.
\par\@@lbibitem{duchi2011adaptive}\NAT@@wrout{24}{}{}{}{(24)}{duchi2011adaptive}\lx@bibnewblock
J.~{}Duchi, E.~{}Hazan, and Y.~{}Singer. \lx@bibnewblock Adaptive subgradient
methods for online learning and stochastic optimization. \lx@bibnewblock{\em
Journal of machine learning research}, 12(7), 2011.
\par\@@lbibitem{ene2020adaptive}\NAT@@wrout{25}{}{}{}{(25)}{ene2020adaptive}\lx@bibnewblock
A.~{}Ene and H.~{}L. Nguyen. \lx@bibnewblock Adaptive and universal single-
gradient algorithms for variational inequalities. \lx@bibnewblock{\em arXiv
preprint arXiv:2010.07799}, 2020.
\par\@@lbibitem{gidel2018a}\NAT@@wrout{26}{}{}{}{(26)}{gidel2018a}\lx@bibnewblock
G.~{}Gidel, H.~{}Berard, G.~{}Vignoud, P.~{}Vincent, and S.~{}Lacoste-Julien.
\lx@bibnewblock A variational inequality perspective on generative adversarial
networks. \lx@bibnewblock In {\em International Conference on Learning
Representations}, 2019.
\par\@@lbibitem{gidel2019negative}\NAT@@wrout{27}{}{}{}{(27)}{gidel2019negative}\lx@bibnewblock
G.~{}Gidel, R.~{}A. Hemmat, M.~{}Pezeshki, R.~{}Le~{}Priol, G.~{}Huang,
S.~{}Lacoste-Julien, and I.~{}Mitliagkas. \lx@bibnewblock Negative momentum
for improved game dynamics. \lx@bibnewblock In {\em The 22nd International
Conference on Artificial Intelligence and Statistics}, pages 1802--1811. PMLR,
2019.
\par\@@lbibitem{goodfellow2014generative}\NAT@@wrout{28}{}{}{}{(28)}{goodfellow2014generative}\lx@bibnewblock
I.~{}J. Goodfellow, J.~{}Pouget-Abadie, M.~{}Mirza, B.~{}Xu, D.~{}Warde-
Farley, S.~{}Ozair, A.~{}C. Courville, and Y.~{}Bengio. \lx@bibnewblock
Generative adversarial nets. \lx@bibnewblock In {\em NIPS}, 2014.
\par\@@lbibitem{guo2020communication}\NAT@@wrout{29}{}{}{}{(29)}{guo2020communication}\lx@bibnewblock
Z.~{}Guo, M.~{}Liu, Z.~{}Yuan, L.~{}Shen, W.~{}Liu, and T.~{}Yang.
\lx@bibnewblock Communication-efficient distributed stochastic auc
maximization with deep neural networks. \lx@bibnewblock In {\em International
Conference on Machine Learning}, pages 3864--3874. PMLR, 2020.
\par\@@lbibitem{heusel2017gans}\NAT@@wrout{30}{}{}{}{(30)}{heusel2017gans}\lx@bibnewblock
M.~{}Heusel, H.~{}Ramsauer, T.~{}Unterthiner, B.~{}Nessler, and
S.~{}Hochreiter. \lx@bibnewblock Gans trained by a two time-scale update rule
converge to a local nash equilibrium. \lx@bibnewblock In {\em NIPS}, 2017.
\par\@@lbibitem{hou2021efficient}\NAT@@wrout{31}{}{}{}{(31)}{hou2021efficient}\lx@bibnewblock
C.~{}Hou, K.~{}K. Thekumparampil, G.~{}Fanti, and S.~{}Oh. \lx@bibnewblock
Efficient algorithms for federated saddle point optimization, 2021.
\par\@@lbibitem{judisky2011firstorder}\NAT@@wrout{32}{}{}{}{(32)}{judisky2011firstorder}\lx@bibnewblock
A.~{}Juditsky, A.~{}Nemirovski, et~{}al. \lx@bibnewblock First order methods
for nonsmooth convex large-scale optimization, ii: utilizing problems
structure. \lx@bibnewblock{\em Optimization for Machine Learning}, 30(9):149--
183, 2011.
\par\@@lbibitem{Juditsky2011solving}\NAT@@wrout{33}{}{}{}{(33)}{Juditsky2011solving}\lx@bibnewblock
A.~{}Juditsky, A.~{}Nemirovski, and C.~{}Tauvel. \lx@bibnewblock Solving
variational inequalities with stochastic mirror-prox algorithm.
\lx@bibnewblock{\em Stochastic Systems}, 1(1):17--58, June 2011.
\par\@@lbibitem{kingma2017adam}\NAT@@wrout{34}{}{}{}{(34)}{kingma2017adam}\lx@bibnewblock
D.~{}P. Kingma and J.~{}Ba. \lx@bibnewblock Adam: A method for stochastic
optimization. \lx@bibnewblock In {\em International Conference on Learning
Representations}, 2017.
\par\@@lbibitem{korpel1976}\NAT@@wrout{35}{}{}{}{(35)}{korpel1976}\lx@bibnewblock
G.~{}M. Korpelevich. \lx@bibnewblock The extragradient method for finding
saddle points and other problems. \lx@bibnewblock{\em Matecon}, 1976.
\par\@@lbibitem{Li2020On}\NAT@@wrout{36}{}{}{}{(36)}{Li2020On}\lx@bibnewblock
X.~{}Li, K.~{}Huang, W.~{}Yang, S.~{}Wang, and Z.~{}Zhang. \lx@bibnewblock On
the convergence of fedavg on non-iid data. \lx@bibnewblock In {\em
International Conference on Learning Representations}, 2020.
\par\@@lbibitem{lin2020near}\NAT@@wrout{37}{}{}{}{(37)}{lin2020near}\lx@bibnewblock
T.~{}Lin, C.~{}Jin, and M.~{}I. Jordan. \lx@bibnewblock Near-optimal
algorithms for minimax optimization. \lx@bibnewblock In {\em Conference on
Learning Theory}, pages 2738--2779. PMLR, 2020.
\par\@@lbibitem{lin2019don}\NAT@@wrout{38}{}{}{}{(38)}{lin2019don}\lx@bibnewblock
T.~{}Lin, S.~{}U. Stich, K.~{}K. Patel, and M.~{}Jaggi. \lx@bibnewblock Don't
use large mini-batches, use local sgd. \lx@bibnewblock In {\em International
Conference on Learning Representations}, 2020.
\par\@@lbibitem{liu2020towards}\NAT@@wrout{39}{}{}{}{(39)}{liu2020towards}\lx@bibnewblock
M.~{}Liu, Y.~{}Mroueh, J.~{}Ross, W.~{}Zhang, X.~{}Cui, P.~{}Das, and
T.~{}Yang. \lx@bibnewblock Towards better understanding of adaptive gradient
algorithms in generative adversarial nets. \lx@bibnewblock In {\em
International Conference on Learning Representations}, 2020.
\par\@@lbibitem{mingruiliu2020decentralized}\NAT@@wrout{40}{}{}{}{(40)}{mingruiliu2020decentralized}\lx@bibnewblock
M.~{}Liu, W.~{}Zhang, Y.~{}Mroueh, X.~{}Cui, J.~{}Ross, T.~{}Yang, and
P.~{}Das. \lx@bibnewblock A decentralized parallel algorithm for training
generative adversarial nets. \lx@bibnewblock volume~{}33, 2020.
\par\@@lbibitem{mcmahan2021advances}\NAT@@wrout{41}{}{}{}{(41)}{mcmahan2021advances}\lx@bibnewblock
H.~{}B. McMahan et~{}al. \lx@bibnewblock Advances and open problems in
federated learning. \lx@bibnewblock{\em Foundations and
Trends{\textregistered} in Machine Learning}, 14(1), 2021.
\par\@@lbibitem{mertikopoulos2018optimistic}\NAT@@wrout{42}{}{}{}{(42)}{mertikopoulos2018optimistic}\lx@bibnewblock
P.~{}Mertikopoulos, B.~{}Lecouat, H.~{}Zenati, C.-S. Foo, V.~{}Chandrasekhar,
and G.~{}Piliouras. \lx@bibnewblock Optimistic mirror descent in saddle-point
problems: Going the extra(-gradient) mile. \lx@bibnewblock In {\em
International Conference on Learning Representations}, 2019.
\par\@@lbibitem{mertikopoulos2018cycles}\NAT@@wrout{43}{}{}{}{(43)}{mertikopoulos2018cycles}\lx@bibnewblock
P.~{}Mertikopoulos, C.~{}Papadimitriou, and G.~{}Piliouras. \lx@bibnewblock
Cycles in adversarial regularized learning. \lx@bibnewblock In {\em
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete
Algorithms}, pages 2703--2717. SIAM, 2018.
\par\@@lbibitem{monteiro2011complexity}\NAT@@wrout{44}{}{}{}{(44)}{monteiro2011complexity}\lx@bibnewblock
R.~{}D.~{}C. Monteiro and B.~{}F. Svaiter. \lx@bibnewblock Complexity of
variants of tseng's modified f-b splitting and korpelevich's methods for
hemivariational inequalities with applications to saddle-point and convex
optimization problems. \lx@bibnewblock{\em SIAM J. Optimization}, 21:1688--
1720, 2011.
\par\@@lbibitem{nemirovski2004prox}\NAT@@wrout{45}{}{}{}{(45)}{nemirovski2004prox}\lx@bibnewblock
A.~{}Nemirovski. \lx@bibnewblock Prox-method with rate of convergence o (1/t)
for variational inequalities with lipschitz continuous monotone operators and
smooth convex-concave saddle point problems. \lx@bibnewblock{\em SIAM Journal
on Optimization}, 15(1):229--251, 2004.
\par\@@lbibitem{nemirovski2009robust}\NAT@@wrout{46}{}{}{}{(46)}{nemirovski2009robust}\lx@bibnewblock
A.~{}Nemirovski, A.~{}Juditsky, G.~{}Lan, and A.~{}Shapiro. \lx@bibnewblock
Robust stochastic approximation approach to stochastic programming.
\lx@bibnewblock{\em SIAM Journal on Optimization}, 19(4):1574--1609, 2009.
\par\@@lbibitem{neumann1928theorie}\NAT@@wrout{47}{}{}{}{(47)}{neumann1928theorie}\lx@bibnewblock
J.~{}v. Neumann. \lx@bibnewblock Zur theorie der gesellschaftsspiele.
\lx@bibnewblock{\em Mathematische annalen}, 100(1):295--320, 1928.
\par\@@lbibitem{reddi2021adaptive}\NAT@@wrout{48}{}{}{}{(48)}{reddi2021adaptive}\lx@bibnewblock
S.~{}J. Reddi, Z.~{}Charles, M.~{}Zaheer, Z.~{}Garrett, K.~{}Rush,
J.~{}Kone{\v{c}}n{\'{y}}, S.~{}Kumar, and H.~{}B. McMahan. \lx@bibnewblock
Adaptive federated optimization. \lx@bibnewblock In {\em International
Conference on Learning Representations}, 2021.
\par\@@lbibitem{Reddi2018on}\NAT@@wrout{49}{}{}{}{(49)}{Reddi2018on}\lx@bibnewblock
S.~{}J. Reddi, S.~{}Kale, and S.~{}Kumar. \lx@bibnewblock On the convergence
of adam and beyond. \lx@bibnewblock In {\em International Conference on
Learning Representations}, 2018.
\par\@@lbibitem{rogozin2021decentralized}\NAT@@wrout{50}{}{}{}{(50)}{rogozin2021decentralized}\lx@bibnewblock
A.~{}Rogozin, A.~{}Beznosikov, D.~{}Dvinskikh, D.~{}Kovalev,
P.~{}Dvurechensky, and A.~{}Gasnikov. \lx@bibnewblock Decentralized
distributed optimization for saddle point problems, 2021\.
\par\@@lbibitem{smola2010architecture}\NAT@@wrout{51}{}{}{}{(51)}{smola2010architecture}\lx@bibnewblock
A.~{}Smola and S.~{}Narayanamurthy. \lx@bibnewblock An architecture for
parallel topic models. \lx@bibnewblock{\em Proceedings of the VLDB Endowment},
3(1-2):703--710, 2010.
\par\@@lbibitem{stich2018local}\NAT@@wrout{52}{}{}{}{(52)}{stich2018local}\lx@bibnewblock
S.~{}U. Stich. \lx@bibnewblock Local {SGD} converges fast and communicates
little. \lx@bibnewblock In {\em International Conference on Learning
Representations}, 2019.
\par\@@lbibitem{wang2019towards}\NAT@@wrout{53}{}{}{}{(53)}{wang2019towards}\lx@bibnewblock
J.~{}Wang, T.~{}Zhang, S.~{}Liu, P.-Y. Chen, J.~{}Xu, M.~{}Fardad, and
B.~{}Li. \lx@bibnewblock Towards a unified min-max framework for adversarial
exploration and robustness. \lx@bibnewblock{\em arXiv preprint
arXiv:1906.03563}, 2019.
\par\@@lbibitem{xie2019local}\NAT@@wrout{54}{}{}{}{(54)}{xie2019local}\lx@bibnewblock
C.~{}Xie, O.~{}Koyejo, I.~{}Gupta, and H.~{}Lin. \lx@bibnewblock Local
adaalter: Communication-efficient stochastic gradient descent with adaptive
learning rates. \lx@bibnewblock{\em arXiv preprint arXiv:1911.09030}, 2019.
\par\@@lbibitem{yan2020adaptive}\NAT@@wrout{55}{}{}{}{(55)}{yan2020adaptive}\lx@bibnewblock
Y.~{}Yan and Y.~{}Xu. \lx@bibnewblock Adaptive primal-dual stochastic gradient
method for expectation-constrained convex stochastic programs.
\lx@bibnewblock{\em arXiv preprint arXiv:2012.14943}, 2020.
\par\@@lbibitem{Yu2019onthelinear}\NAT@@wrout{56}{}{}{}{(56)}{Yu2019onthelinear}\lx@bibnewblock
H.~{}Yu, R.~{}Jin, and S.~{}Yang. \lx@bibnewblock On the linear speed-up
analysis of communication efficient momentum {SGD} for distributed non-convex
optimization. \lx@bibnewblock In {\em Proceedings of the 36th International
Conference on Machine Learning}, volume~{}97 of {\em Proceedings of Machine
Learning Research}, pages 7184--7193. PMLR, 09--15 Jun 2019.
\par\@@lbibitem{NEURIPS2020_52aaa62e}\NAT@@wrout{57}{}{}{}{(57)}{NEURIPS2020_52aaa62e}\lx@bibnewblock
J.~{}Zhang, P.~{}Xiao, R.~{}Sun, and Z.~{}Luo. \lx@bibnewblock A single-loop
smoothed gradient descent-ascent algorithm for nonconvex-concave min-max
problems. \lx@bibnewblock In {\em Advances in Neural Information Processing
Systems}, volume~{}33, pages 7377--7389. Curran Associates, Inc., 2020.
\par\@@lbibitem{zhao2021accelerated}\NAT@@wrout{58}{}{}{}{(58)}{zhao2021accelerated}\lx@bibnewblock
R.~{}Zhao. \lx@bibnewblock Accelerated stochastic algorithms for convex-
concave saddle-point problems. \lx@bibnewblock{\em arXiv preprint
arXiv:1903.01687}, 2021.
\par\@@lbibitem{zou2019sufficient}\NAT@@wrout{59}{}{}{}{(59)}{zou2019sufficient}\lx@bibnewblock
F.~{}Zou, L.~{}Shen, Z.~{}Jie, W.~{}Zhang, and W.~{}Liu. \lx@bibnewblock A
sufficient condition for convergences of adam and rmsprop. \lx@bibnewblock In
{\em Proceedings of the IEEE/CVF Conference on computer vision and pattern
recognition}, pages 11127--11135, 2019. \par\endthebibliography
\par\LTX@newpage \par\par\@@numbered@section{appendix}{toc}{Related Works}
\par{Stochastic minimax algorithms.}\ Stochastic convex-concave minimax
problems~{}\eqref{spp} have been extensively studied in the optimization
literature and are usually solved via variants of PDHG or extragradient
methods, for example,
\cite[cite]{[\@@bibref{Number}{Chambolle2010,zhao2021accelerated,
nemirovski2004prox, nemirovski2009robust,
Juditsky2011solving,judisky2011firstorder,
Chen2014,beznosikov2021distributed}{}{}]}.
\cite[cite]{[\@@bibref{Number}{chen2017accelerated}{}{}]} and
\cite[cite]{[\@@bibref{Number}{Juditsky2011solving}{}{}]} adopted mirror-prox-
type methods to tackle the stochastic convex-concave minimax problem with
${O}({1}/{\sqrt{T}})$ convergence rate.
\cite[cite]{[\@@bibref{Number}{zhao2021accelerated}{}{}]} proposed an
accelerated stochastic PDHG-type algorithm with Bergman divergence to solve
the stochastic convex-concave minimax problem with a similar
${O}({1}/{\sqrt{T}})$ convergence rate dominated by the stochastic variance
term. However, while all these algorithms
\cite[cite]{[\@@bibref{Number}{chen2017accelerated,Juditsky2011solving,zhao2021accelerated}{}{}]}
have achieved the optimal rate according to the low and upper bound for the
stochastic convex-concave minimax problem
\cite[cite]{[\@@bibref{Number}{beznosikov2021distributed}{}{}]}, their
performance is highly influenced by the choice of the learning rate, which is
either using sufficiently small constants or diminishing learning rates. \\\
\par{Adaptive minimax algorithms.}\ Adaptive learning rate in stochastic
optimization is first developed for minimization problems
\cite[cite]{[\@@bibref{Number}{duchi2011adaptive}{}{}]}. Its variants
\cite[cite]{[\@@bibref{Number}{kingma2017adam,Reddi2018on,
zou2019sufficient,chen2021towards,chen2021quantized}{}{}]} are widely used to
train deep learning models. The key feature of the adaptive learning rate is
that it can automatically adjust the learning rate during the training process
and achieve faster convergence. Recently, the adaptive learning rate has also
been developed for minimax algorithms to accelerate the training process,
since the learning rate in stochastic minimax algorithm is hard to tune based
on the minimax loss, as compared to minimization problems. Several recent
papers have tried to analyze the convergence rate of adaptive extragradient in
the convex-concave minimax settings. The universal mirror-prox method
\cite[cite]{[\@@bibref{Number}{bach2019universal}{}{}]} proposed a new
adaptive learning rate technique that adapts to problem parameters, such as
the unknown Lipschitz parameter, and achieves optimal convergence rates in
stochastic setting.
\cite[cite]{[\@@bibref{Number}{babanezhad2020geometry}{}{}]} extended the
universal mirror-prox \cite[cite]{[\@@bibref{Number}{bach2019universal}{}{}]}
by replacing the norm dependence in the learning rate with a general Bregman
divergence dependence. \cite[cite]{[\@@bibref{Number}{ene2020adaptive}{}{}]}
proposed an adaptive stochastic single-call extragradient algorithm for
variational inequality problems.
\cite[cite]{[\@@bibref{Number}{antonakopoulos2021adaptive}{}{}]} proposed a
similar adaptive mirror-prox algorithm, but their method handles an unbounded
domain by introducing the notion of local norms in the deterministic setting.
In addition to the adaptive extragradient methods mentioned above for the
general stochastic minimax problem,
\cite[cite]{[\@@bibref{Number}{yan2020adaptive}{}{}]} proposed an adaptive
primal-dual method for expectation-constrained convex stochastic programs,
which can be formulated as a minimax optimization with the coupled term being
a linear function with dual variable. Training of a GAN model
\cite[cite]{[\@@bibref{Number}{goodfellow2014generative}{}{}]} corresponds to
solving a specific non-convex non-concave minimax problem. Several works have
heuristically adopted a stochastic adaptive extragradient for training GANs
\cite[cite]{[\@@bibref{Number}{gidel2018a,mertikopoulos2018optimistic,beznosikov2021distributed}{}{}]}.
Recently, \cite[cite]{[\@@bibref{Number}{liu2020towards}{}{}]} studied the
convergence behavior of an adaptive optimistic stochastic gradient algorithm
for a class of non-convex non-concave minimax problems under the MVI condition
to train GANs. \\\ \par{Distributed minimax algorithms.}\ As datasets and deep
learning architectures become larger and larger distributed minimax algorithms
are needed for GANs and adversarial training.
\cite[cite]{[\@@bibref{Number}{beznosikov2021distributed}{}{}]} established
upper and lower bounds for iteration complexity for strongly-convex-strongly-
concave and convex-concave minimax problems in both a centralized and
decentralized setting. However, the convergence rate for their Extra Step
Local SGD is established only in a strongly-convex-strongly-concave setting
with a linear speed-up property with respect to the number of works; while for
their proposed local Adam no convergence results are provided.
\cite[cite]{[\@@bibref{Number}{deng2020local}{}{}]} provided convergence
guarantees for a primal-dual local stochastic gradient algorithm in the
strongly-convex-strongly-concave-setting and several non-convex settings with
PL-inequality-type conditions.
\cite[cite]{[\@@bibref{Number}{chen2020distributed}{}{}]} and
\cite[cite]{[\@@bibref{Number}{mingruiliu2020decentralized}{}{}]} studied the
convergence of a distributed optimistic stochastic gradient algorithm for non-
convex non-concave minimax problems under the pseudomonotonicity condition and
MVI condition, respectively. However, their convergence rates hold only for a
sufficiently large minibatch size or a sufficiently large number of workers.
In addition, there also exist several decentralized or federated algorithms
for stochastic strongly-convex-strongly-concave minimax problems
\cite[cite]{[\@@bibref{Number}{hou2021efficient,
rogozin2021decentralized}{}{}]}. In this work, we mainly focus on the
centralized setting for the stochastic convex-concave minimax problems.
\par\par\par\@@numbered@section{appendix}{toc}{Appendix to Main Text}
\par\par\@@numbered@section{subsection}{toc}{Extension to Unbounded Stochastic
Gradient Oracle} Let $\\{Z_{i}\\}_{i=1}^{n}$ be a sequence of
i.i.d.~{}standard normals. We have the following well-known results (see
Appendix A of \cite[cite]{[\@@bibref{Number}{Chatterjee2014}{}{}]}):
\@@amsalign&{\mathbb{P}}\big{(}\max_{i}Z_{i}>{\mathbb{E}}[\max_{i}Z_{i}]+t\big{)}\leq\exp(-t^{2}/2)\text{
for all }t>0,\\\ &{\mathbb{E}}[\max_{i}|Z_{i}|]\leq\sqrt{2\log(2n)}. With
this, we have ${\mathbb{P}}(\max_{i}|Z_{i}|\geq\sqrt{2\log(2n)}+t)\leq
2\exp(-t^{2}/2)$. We apply this result to the sequence
$\big{\\{}\|G({z^{m}_{t}})-\tilde{G}({z^{m}_{t}})\|_{*}/\|G\|_{\infty},\|G({\tilde{z}^{m,*}_{t-1}})-\tilde{G}({\tilde{z}^{m,*}_{t-1}})\|_{*}/\|G\|_{\infty}\big{\\}}_{m,t}$,
which is a sequence of $2MT$ i.i.d.~{}standard normals by the homogeneity of
the oracle. \par\par\@@numbered@section{appendix}{toc}{Proof of Theorems}
\par\par\begin{lemma} For all $m\in[M]$, consider the sequence
$\\{{\eta^{m}_{t}},{\tilde{z}^{m,*}_{t-1}},{z^{m}_{t}},{\tilde{z}^{m}_{t}}\\}_{t=1}^{T}$
defined in \lx@cref{creftype~refnum}{algo}. It holds
\@@amsalign\|{\tilde{z}^{m,*}_{t-1}}-{z^{m}_{t}}\|/{\eta^{m}_{t}}\leq
G,\quad\|{\tilde{z}^{m}_{t}}-{z^{m}_{t}}\|/{\eta^{m}_{t}}\leq G. \end{lemma}
\rm{\par\addvspace{\medskipamount}\noindent{\bf Proof: }}\ignorespaces[Proof
of \lx@cref{creftype~refnum}{lm:bdimprovement}] Let
$I:{\mathcal{Z}}\to{\mathcal{Z}}^{*}$ be the identity map which maps an
element $z\in{\mathcal{Z}}$ to the corresponding element in the dual space
${\mathcal{Z}}^{*}$ (we are considering Euclidean case). The first-order
optimality condition of the update rule
${z^{m}_{t}}=\Pi_{\mathcal{Z}}[{\tilde{z}^{m,*}_{t-1}}-{\eta^{m}_{t}}{M^{m}_{t}}]$
is
\@@amsalign\langle{\eta^{m}_{t}}{M^{m}_{t}}+I({z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}),z-{z^{m}_{t}}\rangle\geq
0,\forall z\in{\mathcal{Z}}. Set $z={\tilde{z}^{m,*}_{t-1}}$, apply the
Cauchy-Schwartz inequality and we obtain
\@@amsalign{\eta^{m}_{t}}\|{M^{m}_{t}}\|_{*}\cdot\|{\tilde{z}^{m,*}_{t-1}}-{z^{m}_{t}}\|&\geq\langle{\eta^{m}_{t}}{M^{m}_{t}},{\tilde{z}^{m,*}_{t-1}}-{z^{m}_{t}}\rangle\\\
&\geq\langle
I({\tilde{z}^{m,*}_{t-1}}-{z^{m}_{t}}),{\tilde{z}^{m,*}_{t-1}}-{z^{m}_{t}}\rangle=\|{\tilde{z}^{m,*}_{t-1}}-{z^{m}_{t}}\|^{2}.
The second inequality holds due to similar reasoning. We conclude the proof of
Lemma~{}\ref{lm:bdimprovement}. \end@proof \par\begin{lemma}[One-step
analysis] For all $m\in[M]$, consider the sequence
$\\{{\eta^{m}_{t}},{\tilde{z}^{m,*}_{t-1}},{M^{m}_{t}}=\tilde{G}({\tilde{z}^{m,*}_{t-1}}),{z^{m}_{t}},{g^{m}_{t}}=\tilde{G}({\tilde{z}^{m}_{t}}),{\tilde{z}^{m}_{t}}\\}_{t=1}^{T}$
defined in Algorithm~{}\ref{algo}. It holds for all $z\in{\mathcal{Z}}$,
\@@amsalign\langle{z^{m}_{t}}-z,{g^{m}_{t}}\rangle\leq\frac{1}{{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\tilde{z}^{m,*}_{t-1}}\|^{2}-\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}-\frac{1}{{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}+\tfrac{1}{2}\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}\\\
+\|{g^{m}_{t}}-{M^{m}_{t}}\|_{*}\cdot\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|.
\end{lemma} \par\rm{\par\addvspace{\medskipamount}\noindent{\bf Proof:
}}\ignorespaces[Proof of Lemma~{}\ref{lm:onestep}] For any
$c,g\in{\mathcal{Z}}$, consider the update of the form
$a^{*}=\Pi_{{\mathcal{Z}}}[c-g]=\operatorname*{argmin}_{z\in{\mathcal{Z}}}\,\langle
g,z\rangle+\tfrac{1}{2}\|z-c\|^{2}$. It holds for all $b\in{\mathcal{Z}}$,
\@@amsalign\langle
g,a^{*}-b\rangle\leq\tfrac{1}{2}\|b-c\|^{2}-\tfrac{1}{2}\|b-a^{*}\|^{2}-\tfrac{1}{2}\|a^{*}-c\|^{2}.
By the update rule of ${z^{m}_{t}}$ and ${\tilde{z}^{m}_{t}}$, we have (taking
$a^{*}\leftrightarrow{z^{m}_{t}}$, $b\leftrightarrow{\tilde{z}^{m}_{t}}$,
$g\leftrightarrow{\eta^{m}_{t}}{M^{m}_{t}}$,
$c\leftrightarrow{\tilde{z}^{m,*}_{t-1}}$)
\@@amsalign\langle{\eta^{m}_{t}}{M^{m}_{t}},{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\rangle\leq\tfrac{1}{2}\|{\tilde{z}^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}-\tfrac{1}{2}\|{\tilde{z}^{m}_{t}}-{z^{m}_{t}}\|^{2}-\tfrac{1}{2}\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2},
and for all $z\in{\mathcal{Z}}$ (taking
$a^{*}\leftrightarrow{\tilde{z}^{m}_{t}}$, $b\leftrightarrow z$,
$g\leftrightarrow{\eta^{m}_{t}}{g^{m}_{t}}$,
$c\leftrightarrow{\tilde{z}^{m,*}_{t-1}}$)
\@@amsalign\langle{\eta^{m}_{t}}{g^{m}_{t}},{\tilde{z}^{m}_{t}}-z\rangle\leq\tfrac{1}{2}\|z-{\tilde{z}^{m,*}_{t-1}}\|^{2}-\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t}}\|^{2}-\tfrac{1}{2}\|{\tilde{z}^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}.
Finally we apply the Cauchy-Schwarz inequality and plug in
Eqs.~{}\eqref{eq:eq1} and \eqref{eq:eq2}.
\@@amsalign\langle{g^{m}_{t}},{z^{m}_{t}}-z\rangle&=\langle{g^{m}_{t}},{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\rangle+\langle{g^{m}_{t}},{\tilde{z}^{m}_{t}}-z\rangle\\\
&=\langle{g^{m}_{t}}-{M^{m}_{t}},{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\rangle+\langle{g^{m}_{t}},{\tilde{z}^{m}_{t}}-z\rangle+\langle{M^{m}_{t}},{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\rangle\\\
&\leq\|{g^{m}_{t}}-{M^{m}_{t}}\|_{*}\cdot\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|+\langle{g^{m}_{t}},{\tilde{z}^{m}_{t}}-z\rangle+\langle{M^{m}_{t}},{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\rangle\\\
&\leq\|{g^{m}_{t}}-{M^{m}_{t}}\|_{*}\cdot\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|\
\\\
&\quad\quad+{\frac{1}{\eta^{m}_{t}}}\Big{(}{\tfrac{1}{2}\|{\tilde{z}^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}}-\tfrac{1}{2}\|{\tilde{z}^{m}_{t}}-{z^{m}_{t}}\|^{2}-\tfrac{1}{2}\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}\Big{)}\\\
&\quad\quad+{\frac{1}{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\tilde{z}^{m,*}_{t-1}}\|^{2}-\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t}}\|^{2}-{\tfrac{1}{2}\|{\tilde{z}^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}}\Big{)}\\\
&=\frac{1}{{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\tilde{z}^{m,*}_{t-1}}\|^{2}-\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}-\frac{1}{{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}+\tfrac{1}{2}\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}\\\
&\quad\quad+\|{g^{m}_{t}}-{M^{m}_{t}}\|_{*}\cdot\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|.
This finishes the proof of Lemma~{}\ref{lm:onestep}. \end@proof
\par\par\@@numbered@section{subsection}{toc}{Proof of
Theorem~\ref{thm:nonsmooth}} \rm{\par\addvspace{\medskipamount}\noindent{\bf
Proof: }}\ignorespaces[Proof of Theorem~{}\ref{thm:nonsmooth}, Non-smooth
Case] The proof strategy follows closely that of Bach and Levy
\cite[cite]{[\@@bibref{Number}{bach2019universal}{}{}]}. {Step 1.} We apply
the Lemma~{}\ref{lm:onestep} and sum over all $m\in[M]$ and $t\in[T]$. Define
\@@amsalign{\xi^{m}_{t}}\vcentcolon=G({z^{m}_{t}})-{g^{m}_{t}}=G({z^{m}_{t}})-\tilde{G}({z^{m}_{t}}).
For all $z\in{\mathcal{Z}}$,
\@@amsalign{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\big{\langle}{z^{m}_{t}}-z,G({z^{m}_{t}})\big{\rangle}&={\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\big{\langle}{z^{m}_{t}}-z,{\xi^{m}_{t}}\rangle+{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\langle{z^{m}_{t}}-z,{g^{m}_{t}}\rangle\\\
&\leq\underbracket{{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\big{\langle}{z^{m}_{t}}-z,{\xi^{m}_{t}}\big{\rangle}}_{{I}(z)}\\\
&\quad+\underbracket{{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\frac{1}{{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\tilde{z}^{m,*}_{t-1}}\|^{2}-\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}}_{{II}(z)}\\\
&\quad\underbracket{-{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\frac{1}{{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}+\tfrac{1}{2}\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}}_{{III}}\\\
&\quad+\underbracket{{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\|{g^{m}_{t}}-{M^{m}_{t}}\|_{*}\cdot\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|}_{{IV}}.
Now we use Lemma~{}\ref{lm:gaptoregret} and obtain \@@amsalign
TM\cdot{\mathbb{E}}[{\operatorname*{{DualGap}}}(\bar{z})]&\leq{\mathbb{E}}[\sup_{z\in{\mathcal{Z}}}\\{{I}(z)+{II}(z)+{III}+{IV}\\}]\\\
&\leq{\mathbb{E}}[\sup_{z\in{\mathcal{Z}}}I(z)]+{\mathbb{E}}[\sup_{z\in{\mathcal{Z}}}II(z)]+{\mathbb{E}}[III]+{\mathbb{E}}[IV]
Next we upper bound each term in turns. Steps 2--5 rely heavily on the
learning rate scheme. Define
\@@amsalign(Z^{m}_{t})^{2}\vcentcolon=\frac{\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}+\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}}{{5}({\eta^{m}_{t}})^{2}}
for all $t\in[T]$ and $m\in[M]$. By Lemma~{}\ref{lm:bdimprovement} we know
$Z^{m}_{t}\leq G$ almost surely. This is due to
\@@amsalign\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}+\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}\leq\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}+2\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}+2\|{\tilde{z}^{m,*}_{t-1}}-{\tilde{z}^{m}_{t}}\|^{2}\leq
5G^{2}{(\eta^{m}_{t})^{2}}. \par\par Moreover, for the nonsmooth case
($\alpha=1$), ${\eta^{m}_{t}}$ can be expressed by
\@@amsalign{\eta^{m}_{t}}=\frac{D}{\sqrt{G_{0}^{2}+\sum_{\tau=1}^{t-1}(Z^{m}_{\tau})^{2}}}.
\par{Step 2.} Show ${\mathbb{E}}[\sup_{z\in{\mathcal{Z}}}I(z)]=O(\sigma
D\sqrt{MT})$. For all $z\in{\mathcal{Z}}$, \@@amsalign
I(z)={\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\langle{z^{m}_{t}}-\tilde{z}^{m}_{0},{\xi^{m}_{t}}\rangle+{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\langle\tilde{z}^{m}_{0}-z,{\xi^{m}_{t}}\rangle.
The first term is a martingale difference sequence (MDS) and is zero in
expectation. For the second term, we use the Cauchy–Schwarz inequality. For
all $z\in{\mathcal{Z}}$,
\@@amsalign{\mathbb{E}}\bigg{[}\sup_{z}{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\langle\tilde{z}^{m}_{0}-z,{\xi^{m}_{t}}\rangle\bigg{]}&={\mathbb{E}}\bigg{[}\sup_{z}\Big{\langle}\tilde{z}_{0}-z,{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}{\xi^{m}_{t}}\Big{\rangle}\bigg{]}\\\
&\leq{\mathbb{E}}\bigg{[}\sup_{z}\|\tilde{z}_{0}-z\|\cdot\bigg{\|}{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}{\xi^{m}_{t}}\bigg{\|}_{*}\bigg{]}\\\
&\leq
D\cdot\sqrt{{\mathbb{E}}\bigg{[}\bigg{\|}{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}{\xi^{m}_{t}}\bigg{\|}_{*}^{2}\bigg{]}}\leq\sigma
D\sqrt{MT}. In the last equality, we use the fact that $\\{{\xi^{m}_{t}}\\}$
is an MDS. This establishes ${\mathbb{E}}[\sup_{z}I(z)]\leq\sigma D\sqrt{MT}$.
\par{Step 3.} Show ${\mathbb{E}}[\sup_{z\in{\mathcal{Z}}}II(z)]=O(DG\cdot
M\sqrt{T})$. For all $z\in{\mathcal{Z}}$, \tiny\@@amsalign
II(z)&={\sum_{t=1}^{T}}{\sum_{m=1}^{M}}{\frac{1}{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\tilde{z}^{m,*}_{t-1}}\|^{2}-\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}\\\
&={\sum_{m=1}^{M}}{\sum_{t\notin
S+1}}{\frac{1}{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\tilde{z}^{m,*}_{t-1}}\|^{2}-\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}+{\sum_{m=1}^{M}}{\sum_{t\in
S+1}}{\frac{1}{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\tilde{z}^{m,*}_{t-1}}\|^{2}-\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}\\\
&={\sum_{m=1}^{M}}{\sum_{t\notin
S+1}}{\frac{1}{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\color[rgb]{1,0,0}{\tilde{z}^{m}_{t-1}}}\|^{2}-\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}+{\sum_{m=1}^{M}}{\sum_{t\in
S+1}}{\frac{1}{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\color[rgb]{1,0,0}{\tilde{z}^{\circ}_{t-1}}}\|^{2}-\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}\\\
&=\underbracket{{\sum_{m=1}^{M}}{\sum_{t=1}^{T}}{\frac{1}{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t-1}}\|^{2}-\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}}_{A}+\underbracket{{\sum_{m=1}^{M}}{\sum_{t\in
S+1}}{\frac{1}{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\tilde{z}^{\circ}_{t-1}}\|^{2}-\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t-1}}\|^{2}\Big{)}}_{B}
\normalsize where we used the definition of ${\tilde{z}^{m,*}_{t-1}}$ for two
cases $t\in S+1$ and $t\notin S+1$ (Line~{}\ref{line:sync} and
\ref{line:nosync} in algorithm). \par We upper bound $A$ and show $B\leq 0$.
\par Recall for $t\in S+1$, we have
${\tilde{z}^{m,*}_{t-1}}={\tilde{z}^{\circ}_{t-1}}={\sum_{m=1}^{M}}w_{m}\cdot{\tilde{z}^{m}_{t-1}}$,
and for $t\notin S+1$, we have
${\tilde{z}^{m,*}_{t-1}}={\tilde{z}^{m}_{t-1}}$. For the first term $A$ we use
$\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t}}\|^{2}\leq D^{2}$ and then telescope.
\@@amsalign
A&={\sum_{m=1}^{M}}\bigg{[}\frac{1}{\eta^{m}_{1}}\Big{(}\tfrac{1}{2}\|\tilde{z}^{m}_{0}-z\|^{2}\Big{)}-\frac{1}{\eta^{m}_{T}}\Big{(}\tfrac{1}{2}\|\tilde{z}^{m}_{T}-z\|^{2}\Big{)}+\sum_{t=2}^{T}\Big{(}\frac{1}{{\eta^{m}_{t}}}-\frac{1}{\eta^{m}_{t-1}}\Big{)}\Big{(}\tfrac{1}{2}\|{\tilde{z}^{m}_{t-1}}-z\|^{2}\Big{)}\bigg{]}\\\
&\leq{\sum_{m=1}^{M}}\bigg{[}\frac{D^{2}}{\eta^{m}_{1}}+\sum_{t=2}^{T}\Big{(}\frac{1}{{\eta^{m}_{t}}}-\frac{1}{\eta^{m}_{t-1}}\Big{)}D^{2}\bigg{]}\\\
&\leq{\sum_{m=1}^{M}}\bigg{[}\frac{D^{2}}{\eta^{m}_{1}}+\frac{D^{2}}{\eta^{m}_{T}}\bigg{]}
For each $m$, we have $D^{2}/\eta^{m}_{1}=DG_{0}$. For $D^{2}/\eta^{m}_{T}$ we
use the learning rate scheme. Recall the definition of ${Z^{m}_{t}}$. Then
\@@amsalign\frac{D^{2}}{\eta^{m}_{T}}=D\sqrt{G_{0}^{2}+\sum_{t=1}^{T-1}(Z^{m}_{t})^{2}}\leq
D\sqrt{G_{0}+G^{2}T}\leq DG_{0}+DG\sqrt{T}. This implies $A\leq
M(2DG_{0}+DG\sqrt{T})=O(DG\cdot M\sqrt{T})$. \par For the term $B$, we use the
definition of ${\tilde{z}^{\circ}_{t-1}}$ and the weights $\\{w_{m}\\}$ to
show $B\leq 0$. For each $t$, since ${\tilde{z}^{\circ}_{t-1}}$ the same for
all workers,
\@@amsalign{\sum_{m=1}^{M}}{\frac{1}{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\tilde{z}^{\circ}_{t-1}}\|^{2}\Big{)}&=\Big{(}{\sum_{m=1}^{M}}{\frac{1}{\eta^{m}_{t}}}\Big{)}\Big{(}\tfrac{1}{2}\|z-{\tilde{z}^{\circ}_{t-1}}\|^{2}\Big{)}\\\
&=\Big{(}{\sum_{m=1}^{M}}{\frac{1}{\eta^{m}_{t}}}\Big{)}\Big{(}\tfrac{1}{2}\big{\|}{\textstyle\sum_{m=1}^{M}{w_{m}}^{1/2}\cdot{w_{m}}^{1/2}(z-{\tilde{z}^{m}_{t-1}})}\big{\|}^{2}\Big{)}\\\
&\leq\Big{(}{\sum_{m=1}^{M}}{\frac{1}{\eta^{m}_{t}}}\Big{)}\Big{(}{\sum_{m=1}^{M}}w_{m}\Big{)}\Big{(}{\sum_{m=1}^{M}}w_{m}\cdot\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t-1}}\|^{2}\Big{)}\\\
&={\sum_{m=1}^{M}}{\frac{1}{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|z-{\tilde{z}^{m}_{t-1}}\|^{2}\Big{)}.
In the last equality we use ${\sum_{m=1}^{M}}w_{m}=1$ and
$({\sum_{m=1}^{M}}1/{\eta^{m}_{t}})w_{m^{\prime}}=1/\eta^{m^{\prime}}_{t}$ for
all $m^{\prime}\in[M]$. This implies $B\leq 0$. This establishes
${\mathbb{E}}[\sup_{z}II(z)]\leq{\mathbb{E}}[\sup_{z}A]=O(DG\cdot M\sqrt{T})$.
\par\par{Step 4.} Show ${\mathbb{E}}[III]\leq 0$. This is obviously true.
\par{Step 5.} Show ${\mathbb{E}}[IV]=\tilde{O}(\gamma DG\cdot M\sqrt{T})$.
Define $\gamma=G/G_{0}$. By \ref{as:bdsg} we have
$\|{g^{m}_{t}}-{M^{m}_{t}}\|_{*}\leq 2G$. It holds almost surely that
\@@amsalign IV&\leq
2G{\sum_{m=1}^{M}}{\sum_{t=1}^{T}}\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|\\\ &\leq
2G\sqrt{T}\cdot{\sum_{m=1}^{M}}\sqrt{{\sum_{t=1}^{T}}\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}}\\\
&\leq
2G\sqrt{T}\cdot{\sum_{m=1}^{M}}\sqrt{{\sum_{t=1}^{T}}({\eta^{m}_{t}}{Z^{m}_{t}})^{2}}\\\
&=2G\sqrt{T}\cdot
D\cdot{\sum_{m=1}^{M}}\sqrt{{\sum_{t=1}^{T}}\frac{({Z^{m}_{t}})^{2}}{G_{0}^{2}+{\sum_{\tau=1}^{t-1}}(Z^{m}_{\tau})^{2}}}\\\
&\leq
2GD\sqrt{T}\cdot{\sum_{m=1}^{M}}\sqrt{2+4\gamma^{2}+2\log\Big{(}\frac{G_{0}^{2}+{\sum_{t=1}^{T-1}}{(Z^{m}_{t})^{2}}}{G_{0}^{2}}\Big{)}}\\\
&\leq
2GD\sqrt{T}\cdot{\sum_{m=1}^{M}}\sqrt{2+4\gamma^{2}+2\log\Big{(}\frac{G_{0}^{2}+G^{2}T}{G_{0}^{2}}\Big{)}}\\\
&\leq
2GD\sqrt{T}\cdot{\sum_{m=1}^{M}}\sqrt{2+4\gamma^{2}+2\log(1+\gamma^{2}T)}\\\
&=\tilde{O}(\gamma GD\cdot M\sqrt{T}) Finally, we plug in the upper bounds for
$I$--$IV$ and continue Eq~{}\eqref{eq:boundnonsmooth}. \@@amsalign
TM\cdot{\mathbb{E}}[{\operatorname*{{DualGap}}}(\bar{z})]=\tilde{O}(\gamma
DG\cdot M\sqrt{T}+\sigma D\sqrt{MT}). This finishes the proof of
Theorem~{}\ref{thm:nonsmooth} \end@proof
\par\par\par\@@numbered@section{subsection}{toc}{Proof of
Theorem~\ref{thm:smooth}} \rm{\par\addvspace{\medskipamount}\noindent{\bf
Proof: }}\ignorespaces[Proof of Theorem~{}\ref{thm:smooth}, Smooth Case] The
proof strategy follows closely that of Bach and Levy
\cite[cite]{[\@@bibref{Number}{bach2019universal}{}{}]}. Using the notation
for Step~{}1 in the proof for the nonsmooth case, we have the bound
\@@amsalign
TM{\mathbb{E}}[{\operatorname*{{DualGap}}}(\bar{z})]\leq{\mathbb{E}}[\sup_{z}\\{I(z)+II(z)+III+IV\\}],
where $I$--$IV$ are defined in Eqs.~{}\eqref{eq:defI}--\eqref{eq:defIV}. We
deal with these terms in a different manner. \par For the term $I(z)$ in
Eq.~{}\eqref{eq:defI}, following Step~{}2 we have
${\mathbb{E}}[\sup_{z}I(z)]=O(\gamma\sigma D\sqrt{MT})$. \par Next, we define
a stopping time. For each $m\in[M]$, let
\@@amsalign\tau^{*}_{m}\vcentcolon=\max\bigg{\\{}t\in[T]:{\frac{1}{\eta^{m}_{t}}}\leq
1/(2L)\bigg{\\}}. Recall our learning rate scheme for the smooth case
\@@amsalign\eta^{m}_{1}=\frac{D\alpha}{G_{0}},\quad{\eta^{m}_{t}}=\frac{D\alpha}{\sqrt{G_{0}^{2}+\sum_{\tau=1}^{t-1}(Z^{m}_{\tau})^{2}}}.
\par For the term $II(z)$ in Eq.~{}\eqref{eq:defII}, we follow Step~{}3 and
obtain for all $z\in{\mathcal{Z}}$, \@@amsalign
II(z)\leq{\sum_{m=1}^{M}}\bigg{(}\frac{D^{2}}{\eta^{m}_{1}}+\frac{D^{2}}{\eta^{m}_{T}}\bigg{)}.
By the definition of $\eta^{m}_{1}$, we have
${\sum_{m=1}^{M}}D^{2}/\eta^{m}_{1}\leq DMG_{0}/\alpha$. For the second term,
for fixed $m\in[M]$,
\@@amsalign{\sum_{m=1}^{M}}D^{2}/{\eta^{m}_{T}}&={\sum_{m=1}^{M}}\frac{D}{\alpha}\sqrt{G_{0}^{2}+{\sum_{t=1}^{T-1}}{(Z^{m}_{t})^{2}}}\\\
&\leq{\sum_{m=1}^{M}}\frac{D}{\alpha}\Bigg{(}G_{0}+{\sum_{t=1}^{T}}\frac{{(Z^{m}_{t})^{2}}}{\sqrt{G_{0}^{2}+{\sum_{\tau=1}^{t-1}}{(Z^{m}_{\tau})^{2}}}}\Bigg{)}\\\
&=\frac{MDG_{0}}{\alpha}+\underbracket{{\sum_{m=1}^{M}}{\sum_{t=1}^{T}}\frac{1}{\alpha^{2}}{\eta^{m}_{t}}{(Z^{m}_{t})^{2}}}_{\vcentcolon={\mathcal{A}}}
So we have ${\mathbb{E}}[\sup_{z}II(z)]\leq 2\gamma
MDG/\alpha+{\mathbb{E}}[{\mathcal{A}}]$. \par For the term $III$ in
Eq.~{}\eqref{eq:defIII}, we also split it into two parts by $\tau^{*}_{m}$.
\@@amsalign
III&\vcentcolon=-{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\frac{1}{{\eta^{m}_{t}}}\Big{(}\tfrac{1}{2}\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}+\tfrac{1}{2}\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}\\\
&=-{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\frac{5}{2}{\eta^{m}_{t}}{(Z^{m}_{t})^{2}}\\\
&=-\underbracket{{\sum_{m=1}^{M}}{\sum_{t=1}^{\tau^{*}_{m}}}\frac{5}{2}{\eta^{m}_{t}}{(Z^{m}_{t})^{2}}}_{\geq
0}-\underbracket{{\sum_{m=1}^{M}}{\sum_{t=\tau^{*}_{m}+1}^{T}}\frac{5}{2}{\eta^{m}_{t}}{(Z^{m}_{t})^{2}}}_{\vcentcolon={\mathcal{B}}_{\operatorname*{{tail}}}}
For the term $IV$ in defined in Eq.~{}\eqref{eq:defIV}, we first introduce a
margtingale difference sequence. For all $t\in[T],m\in[M]$, let
\@@amsalign\zeta^{m}_{t}\vcentcolon=\big{(}{g^{m}_{t}}-G({z^{m}_{t}})\big{)}+\big{(}{M^{m}_{t}}-G({\tilde{z}^{m,*}_{t-1}})\big{)}.
By the triangular inequality, we have \@@amsalign
IV&\vcentcolon={\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\|{g^{m}_{t}}-{M^{m}_{t}}\|_{*}\cdot\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|\\\
&\leq\underbracket{{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\|\zeta^{m}_{t}\|_{*}\cdot\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|}_{\vcentcolon=V}+{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\|G({z^{m}_{t}})-G({\tilde{z}^{m,*}_{t-1}})\|_{*}\cdot\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|\\\
&\leq
V+{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\Big{(}\frac{L}{2}\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}+\frac{L}{2}\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}\Big{)}\\\
&=V+{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\frac{5L}{2}{(\eta^{m}_{t})^{2}}{(Z^{m}_{t})^{2}}\\\
&=V+\underbracket{{\sum_{m=1}^{M}}{\sum_{t=1}^{\tau^{*}_{m}}}\frac{5L}{2}{(\eta^{m}_{t})^{2}}{(Z^{m}_{t})^{2}}}_{\vcentcolon={\mathcal{C}}_{\operatorname*{{head}}}}+\underbracket{{\sum_{m=1}^{M}}{\sum_{t=\tau^{*}_{m}+1}^{T}}\frac{5L}{2}{(\eta^{m}_{t})^{2}}{(Z^{m}_{t})^{2}}}_{\vcentcolon={\mathcal{C}}_{\operatorname*{{tail}}}}
Eq.~{}\eqref{eq:smoothnesskickin} holds due to smoothness, i.e., for all
$z,z^{\prime}\in{\mathcal{Z}}$, $\|G(z)-G(z^{\prime})\|_{*}\leq
L\|z-z^{\prime}\|$. Using smoothness, we can verify
Eq.~{}\eqref{eq:smoothnesskickin} as follows.
\@@amsalign&\|G({z^{m}_{t}})-G({\tilde{z}^{m,*}_{t-1}})\|_{*}\cdot\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|\\\
&\leq\frac{1}{2L}\|G({z^{m}_{t}})-G({\tilde{z}^{m,*}_{t-1}})\|_{*}^{2}+\frac{L}{2}\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}\\\
&\leq\frac{L}{2}\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}+\frac{L}{2}\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}.
To summarize, we have shown \@@amsalign
TM\cdot{\mathbb{E}}[{\operatorname*{{DualGap}}}(\bar{z})]&\leq{\mathbb{E}}[\sup_{z}\\{I(z)+II(z)+III+IV\\}]\\\
&\leq O\Big{(}\gamma\sigma D\sqrt{MT}\Big{)}+{2\gamma MDG}/{\alpha}\\\
&\quad+{\mathbb{E}}[{\mathcal{A}}+{\mathcal{C}}_{\operatorname*{{head}}}+(-{\mathcal{B}}_{\operatorname*{{tail}}}+{\mathcal{C}}_{\operatorname*{{tail}}})+V].
\par{Step a.} Show ${\mathbb{E}}[{\mathcal{A}}]\leq 8\gamma
GDM/\alpha+3DM{\mathcal{V}_{1}(T)}/\alpha$. Recall its definition in
Eq.~{}\eqref{eq:defcA:nonsmooth}.
\@@amsalign{\mathcal{A}}&\vcentcolon={\sum_{m=1}^{M}}{\sum_{t=1}^{T}}\frac{1}{\alpha^{2}}{\eta^{m}_{t}}{(Z^{m}_{t})^{2}}\\\
&=\frac{D}{\alpha}{\sum_{m=1}^{M}}{\sum_{t=1}^{T}}\frac{{(Z^{m}_{t})^{2}}}{\sqrt{G_{0}^{2}+{\sum_{\tau=1}^{t-1}}{(Z^{m}_{\tau})^{2}}}}\\\
&\leq\frac{D}{\alpha}{\sum_{m=1}^{M}}\Bigg{(}5\gamma
G+3\sqrt{G_{0}^{2}+{\sum_{t=1}^{T-1}}{(Z^{m}_{t})^{2}}}\Bigg{)}\\\
&\leq\frac{D}{\alpha}{\sum_{m=1}^{M}}\Bigg{(}8\gamma
G+3\sqrt{{\sum_{t=1}^{T-1}}{(Z^{m}_{t})^{2}}}\Bigg{)} Note by
Lemma~{}\ref{lm:bdimprovement} we know
${(Z^{m}_{t})^{2}}\leq(\|{g^{m}_{t}}\|_{*}^{2}+\|{M^{m}_{t}}\|_{*}^{2})/5\leq\|{g^{m}_{t}}\|_{*}^{2}+\|{M^{m}_{t}}\|_{*}^{2}$.
Recall the definition of ${\mathcal{V}_{m}(T)}$ in Eq.~{}\eqref{eq:defcVmT}.
By the symmetry of the algorithm over all workers, we know
${\mathcal{V}_{1}(T)}={\mathcal{V}_{m}(T)}$ for all $m\in[M]$. Then
\@@amsalign{\mathbb{E}}[{\mathcal{A}}]&\leq 8\gamma
DMG/\alpha+\frac{3D}{\alpha}{\sum_{m=1}^{M}}{\mathbb{E}}\Bigg{[}\sqrt{{\sum_{t=1}^{T-1}}{(Z^{m}_{t})^{2}}}\Bigg{]}\\\
&\leq 8\gamma
DMG/\alpha+\frac{3D}{\alpha}{\sum_{m=1}^{M}}{\mathbb{E}}\Bigg{[}\sqrt{{\sum_{t=1}^{T-1}}\|{g^{m}_{t}}\|_{*}^{2}+\|{M^{m}_{t}}\|_{*}^{2}}\Bigg{]}\\\
&=8\gamma
DMG/\alpha+\frac{3D}{\alpha}{\sum_{m=1}^{M}}{\mathcal{V}_{m}(T)}=8\gamma
DMG/\alpha+3DM{\mathcal{V}_{1}(T)}/\alpha. By our choice of $\alpha$ we have
${\mathbb{E}}[{\mathcal{A}}]=O(\gamma
DM^{3/2}G+DM^{3/2}{\mathcal{V}_{1}(T)})$. \par{Step b.} Show
${\mathbb{E}}[{\mathcal{C}}_{\operatorname*{{head}}}]=O(1)$. Recall its
definition in Eq.~{}\eqref{eq:defcC}.
\@@amsalign{\mathcal{C}}_{\operatorname*{{head}}}&\vcentcolon={\sum_{m=1}^{M}}{\sum_{t=1}^{\tau^{*}_{m}}}\frac{5L}{2}{(\eta^{m}_{t})^{2}}{(Z^{m}_{t})^{2}}\\\
&=\frac{5\alpha^{2}D^{2}L}{2}{\sum_{m=1}^{M}}{\sum_{t=1}^{\tau^{*}_{m}}}\frac{{(Z^{m}_{t})^{2}}}{G_{0}^{2}+{\sum_{\tau=1}^{t-1}}{(Z^{m}_{\tau})^{2}}}\\\
&\leq\frac{5\alpha^{2}D^{2}L}{2}{\sum_{m=1}^{M}}\bigg{(}6\gamma^{2}+2\log\Big{(}\frac{G_{0}^{2}+{\sum_{t=1}^{\tau^{*}_{m}-1}}{(Z^{m}_{\tau})^{2}}}{G_{0}^{2}}\Big{)}\bigg{)}\\\
&=\frac{5\alpha^{2}D^{2}L}{2}{\sum_{m=1}^{M}}\bigg{(}6\gamma^{2}+2\log\Big{(}\frac{\alpha^{2}D^{2}}{G_{0}^{2}(\eta^{m}_{\tau^{*}_{m}})^{2}}\Big{)}\bigg{)}\\\
&\leq\frac{5\alpha^{2}D^{2}LM}{2}\bigg{(}6\gamma^{2}+4\log\Big{(}\frac{\alpha
D}{2G_{0}L}\Big{)}\bigg{)} The last inequality is due to the definition of
$\tau_{m}^{*}$. By our choice of $\alpha$ we have
${\mathbb{E}}[{\mathcal{C}}_{\operatorname*{{head}}}]={\tilde{O}}(\gamma^{2}LD^{2})$.
\par{Step c.} Show
${\mathcal{C}}_{\operatorname*{{tail}}}-{\mathcal{B}}_{\operatorname*{{tail}}}\leq
0$. Recall ${\mathcal{B}}_{\operatorname*{{tail}}}$ is defined in
Eq.~{}\eqref{eq:defBtail}. By definition,
\@@amsalign{\mathcal{C}}_{\operatorname*{{tail}}}-{\mathcal{B}}_{\operatorname*{{tail}}}={\sum_{m=1}^{M}}{\sum_{t=\tau^{*}_{m}+1}^{T}}\Big{(}\frac{5L}{2}{\eta^{m}_{t}}-\frac{5}{2}\Big{)}{\eta^{m}_{t}}{(Z^{m}_{t})^{2}}.
We show $\frac{5L}{2}{\eta^{m}_{t}}-\frac{5}{2}\leq 0$ for all
$t\in[T],m\in[M]$. Note that for all $t\geq\tau^{*}_{m}+1$ we have
${\eta^{m}_{t}}\leq 1/(2L)$. And so
$\frac{5L}{2}{\eta^{m}_{t}}-\frac{5}{2}\leq(5/4)-(5/2)=-5/4$. Summarizing, we
have shown
${\mathcal{C}}_{\operatorname*{{tail}}}-{\mathcal{B}}_{\operatorname*{{tail}}}\leq
0$. \par{Step d.} Show ${\mathbb{E}}[V]={\tilde{O}}(\gamma\sigma D\sqrt{MT})$.
Recall its definition in Eq.\eqref{eq:defV}. Also note
${\mathbb{E}}[\|\zeta^{m}_{t}\|_{*}^{2}]\leq 4\sigma^{2}$.
\@@amsalign{\mathbb{E}}[V]&\vcentcolon={\mathbb{E}}\Bigg{[}{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\|\zeta^{m}_{t}\|_{*}\cdot\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|\Bigg{]}\\\
&\leq{\mathbb{E}}\Bigg{[}\sqrt{{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\|\zeta^{m}_{t}\|_{*}^{2}}\Bigg{]}\cdot{\mathbb{E}}\Bigg{[}\sqrt{{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}}\Bigg{]}\\\
&\leq\sqrt{{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}{\mathbb{E}}\big{[}\|\zeta^{m}_{t}\|_{*}^{2}\big{]}}\cdot{\mathbb{E}}\Bigg{[}\sqrt{{\sum_{t=1}^{T}}{\sum_{m=1}^{M}}\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}}\Bigg{]}\\\
&\leq
2\sigma\sqrt{MT}\cdot{\mathbb{E}}\Bigg{[}\sqrt{{\sum_{m=1}^{M}}{\sum_{t=1}^{T}}\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}}\Bigg{]}\\\
&\leq
2\sigma\sqrt{MT}\cdot{\mathbb{E}}\Bigg{[}\sqrt{{\sum_{m=1}^{M}}{\sum_{t=1}^{T}}\|{z^{m}_{t}}-{\tilde{z}^{m,*}_{t-1}}\|^{2}+\|{z^{m}_{t}}-{\tilde{z}^{m}_{t}}\|^{2}}\Bigg{]}\\\
&=2\sigma\sqrt{MT}\cdot{\mathbb{E}}\Bigg{[}\sqrt{{\sum_{m=1}^{M}}{\sum_{t=1}^{T}}5\cdot{(\eta^{m}_{t})^{2}}{(Z^{m}_{t})^{2}}}\Bigg{]}\\\
&=2\sqrt{5}\cdot\sigma\sqrt{MT}\cdot
D\alpha\cdot{\mathbb{E}}\Bigg{[}\sqrt{{\sum_{m=1}^{M}}{\sum_{t=1}^{T}}\frac{{(Z^{m}_{t})^{2}}}{G_{0}^{2}+{\sum_{\tau=1}^{t-1}}{(Z^{m}_{\tau})^{2}}}}\Bigg{]}\\\
&\leq 6\cdot\sigma\sqrt{MT}\cdot
D\alpha\cdot{\mathbb{E}}\Bigg{[}\sqrt{{\sum_{m=1}^{M}}\bigg{(}6\gamma^{2}+2\log\Big{(}\frac{G_{0}^{2}+{\sum_{t=1}^{T-1}}{(Z^{m}_{t})^{2}}}{G_{0}^{2}}\Big{)}\bigg{)}}\Bigg{]}\\\
&\leq 6\sigma\sqrt{MT}\cdot
D\alpha\cdot\sqrt{M(6\gamma^{2}+2\log(1+\gamma^{2}T))}. By our choice of
$\alpha$, we have ${\mathbb{E}}[V]={\tilde{O}}(\gamma\sigma D\sqrt{MT})$. \par
Continuing Eq.~{}\eqref{eq:smoothdecomp_1}, we have
\@@amsalign&TM\cdot{\mathbb{E}}[{\operatorname*{{DualGap}}}(\bar{z})]\\\ &\leq
O\Big{(}\gamma\sigma D\sqrt{MT}\Big{)}+{2\gamma
MDG}/{\alpha}+{\mathbb{E}}[{\mathcal{A}}+{\mathcal{C}}_{\operatorname*{{head}}}+(-{\mathcal{B}}_{\operatorname*{{tail}}}+{\mathcal{C}}_{\operatorname*{{tail}}})+V]\\\
&={\tilde{O}}\Big{(}\gamma\sigma D\sqrt{MT}+\underbracket{\gamma
DM^{3/2}G+DM^{3/2}{\mathcal{V}_{m}(T)}}_{{\mathcal{A}}}+\underbracket{\gamma^{2}LD^{2}}_{{\mathcal{C}}_{\operatorname*{{head}}}}+\underbracket{\gamma\sigma
D\sqrt{MT}}_{V}\Big{)}. \par This finishes the proof of
Theorem~{}\ref{thm:smooth}. \par\end@proof \par\begin{remark}[Getting rid of
$\cVoneT$] We could also use the free parameters $\alpha$ (base learning rate)
and obtain the following near linear speed-up result.
\par\begin{theorem}[Smooth Case, free of $\cVoneT$] \par Assume
\ref{as:bddomain}, \ref{as:bdsg}, \ref{as:bdvar} and \ref{as:smooth}. Let
$\sigma,D,G,L$ be defined therein. For any $\epsilon\in(0,\frac{1}{2})$, let
$\bar{z}={\operatorname*{{LocalAdaSEG}}}(G_{0},D\mathchar
24635\relax\;K,M,R\mathchar 24635\relax\;T^{\epsilon}/\sqrt{M})$. If $T\geq
M^{1/(2\epsilon)}$, then
$${\mathbb{E}}[\operatorname*{DualGap}(\bar{z})]=\tilde{O}\bigg{(}\frac{\sigma
D}{{\sqrt{MT^{1-2\epsilon}}}}+\frac{\gamma^{2}LD^{2}}{T^{1-2\epsilon}}+\frac{LD^{2}M}{T}+\frac{\gamma
GDM^{3/2}}{T^{1+\epsilon}}\bigg{)}\,,$$ where $\tilde{O}$ hides absolute
constants, logarithmic factors of problem parameters and logarithmic factors
of $T$. \end{theorem} \par\rm{\par\addvspace{\medskipamount}\noindent{\bf
Proof: }}\ignorespaces[Proof of Theorem~{}\ref{thm:smooth_noV}] We decompose
the term $II$ in Eq.\eqref{eq:defII} in a different way. Recall in Step~{}3 we
have shown for all $z\in{\mathcal{Z}}$,
$II(z)\leq{\sum_{m=1}^{M}}\frac{D^{2}}{\eta^{m}_{1}}+\frac{D^{2}}{\eta^{m}_{T}}.$
For the second term, for fixed $m\in[M]$,
\@@amsalign{\sum_{m=1}^{M}}D^{2}/{\eta^{m}_{T}}&={\sum_{m=1}^{M}}\frac{D}{\alpha}\sqrt{G_{0}^{2}+{\sum_{t=1}^{T-1}}{(Z^{m}_{t})^{2}}}\\\
&\leq{\sum_{m=1}^{M}}\frac{D}{\alpha}\Bigg{(}G_{0}+{\sum_{t=1}^{T}}\frac{{(Z^{m}_{t})^{2}}}{\sqrt{G_{0}^{2}+{\sum_{\tau=1}^{t-1}}{(Z^{m}_{\tau})^{2}}}}\Bigg{)}\\\
&=\frac{MDG_{0}}{\alpha}+{\sum_{m=1}^{M}}{\sum_{t=1}^{T}}\frac{1}{\alpha^{2}}{(\eta^{m}_{t})^{2}}{(Z^{m}_{t})^{2}}\\\
&\leq\frac{\gamma
MDG}{\alpha}+\underbracket{{\sum_{m=1}^{M}}{\sum_{t=1}^{\tau^{*}_{m}}}\frac{1}{\alpha^{2}}{(\eta^{m}_{t})^{2}}{(Z^{m}_{t})^{2}}}_{\vcentcolon={\mathcal{A}}_{\operatorname*{{head}}}}+\underbracket{{\sum_{m=1}^{M}}{\sum_{t=\tau^{*}_{m}+1}^{T}}\frac{1}{\alpha^{2}}{(\eta^{m}_{t})^{2}}{(Z^{m}_{t})^{2}}}_{\vcentcolon={\mathcal{A}}_{\operatorname*{{tail}}}}
So we have ${\mathbb{E}}[\sup_{z}II(z)]\leq 2\gamma
MDG/\alpha+{\mathbb{E}}[{\mathcal{A}}_{\operatorname*{{head}}}+{\mathcal{A}}_{\operatorname*{{tail}}}]$.
Then, following the proof in the smooth case, we have \par\@@amsalign
TM\cdot{\mathbb{E}}[{\operatorname*{{DualGap}}}(\bar{z})]&\leq{\mathbb{E}}[\sup_{z}\\{I(z)+II(z)+III+IV\\}]\\\
&\leq O\Big{(}\gamma\sigma D\sqrt{MT}\Big{)}+{2\gamma MDG}/{\alpha}\\\
&\quad+{\mathbb{E}}[{\mathcal{A}}_{\operatorname*{{head}}}+{\mathcal{C}}_{\operatorname*{{head}}}+({\mathcal{A}}_{\operatorname*{{tail}}}-{\mathcal{B}}_{\operatorname*{{tail}}}+{\mathcal{C}}_{\operatorname*{{tail}}})+V].
\par\par\par Recall our choice of $\alpha=T^{\epsilon}/\sqrt{M}$. \par\par
Show ${\mathbb{E}}[{\mathcal{A}}_{\operatorname*{{head}}}]={\tilde{O}}(1)$.
Recall its definition in Eq.~{}\eqref{eq:defcA}.
\@@amsalign{\mathcal{A}}_{\operatorname*{{head}}}&\vcentcolon={\sum_{m=1}^{M}}{\sum_{t=1}^{\tau^{*}_{m}}}\frac{1}{\alpha^{2}}{(\eta^{m}_{t})^{2}}{(Z^{m}_{t})^{2}}\\\
&=\frac{D}{\alpha}{\sum_{m=1}^{M}}{\sum_{t=1}^{\tau^{*}_{m}}}\frac{{(Z^{m}_{t})^{2}}}{\sqrt{G_{0}^{2}+{\sum_{\tau=1}^{t-1}}{(Z^{m}_{\tau})^{2}}}}\\\
&\leq\frac{D}{\alpha}{\sum_{m=1}^{M}}\Bigg{(}5\gamma
G+3\sqrt{G_{0}^{2}+{\sum_{t=1}^{\tau^{*}_{m}-1}}{(Z^{m}_{t})^{2}}}\Bigg{)}\\\
&=\frac{D}{\alpha}{\sum_{m=1}^{M}}\Big{(}5\gamma
G+\frac{3D\alpha}{\eta^{m}_{\tau^{*}_{m}}}\Big{)}\\\
&\leq\frac{D}{\alpha}{\sum_{m=1}^{M}}\Big{(}5\gamma G+6\alpha
LD\Big{)}=\frac{5\gamma GDM}{\alpha}+6LD^{2}M. By our choice of $\alpha$ we
have ${\mathbb{E}}[{\mathcal{A}}_{\operatorname*{{head}}}]\leq 5\gamma
GDM^{3/2}T^{-\epsilon}+6LD^{2}M$. \par\par For
${\mathcal{C}}_{{\operatorname*{{head}}}}$ defined in Eq.~{}\eqref{eq:defcC},
following Eq~{}\eqref{eq:endofcChead}, we have
${\mathbb{E}}[{\mathcal{C}}_{\operatorname*{{head}}}]={\tilde{O}}(\gamma^{2}LD^{2}T^{2\epsilon})$.
\par\par Show
${\mathcal{A}}_{\operatorname*{{tail}}}+{\mathcal{C}}_{\operatorname*{{tail}}}-{\mathcal{B}}_{\operatorname*{{tail}}}\leq
0$. Recall ${\mathcal{B}}_{\operatorname*{{tail}}}$ is defined in
Eq.~{}\eqref{eq:defBtail}. By definition,
\@@amsalign{\mathcal{A}}_{\operatorname*{{tail}}}+{\mathcal{C}}_{\operatorname*{{tail}}}-{\mathcal{B}}_{\operatorname*{{tail}}}={\sum_{m=1}^{M}}{\sum_{t=\tau^{*}_{m}+1}^{T}}\Big{(}\frac{1}{\alpha^{2}}+\frac{5L}{2}{\eta^{m}_{t}}-\frac{5}{2}\Big{)}{\eta^{m}_{t}}{(Z^{m}_{t})^{2}}.
We show $\frac{1}{\alpha^{2}}+\frac{5L}{2}{\eta^{m}_{t}}-\frac{5}{2}\leq 0$
for all $t\in[T],m\in[M]$. Note that \@@amsalign T\geq
M^{1/(2\epsilon)}\implies\alpha^{2}=(T^{\epsilon}/\sqrt{M})^{2}\geq 1, and
that for all $t\geq\tau^{*}_{m}+1$ we have ${\eta^{m}_{t}}\leq 1/(2L)$. And so
$\frac{1}{\alpha^{2}}+\frac{5L}{2}{\eta^{m}_{t}}-\frac{5}{2}\leq
1+(5/4)-(5/2)=-1/4$. Summarizing, we have shown
${\mathcal{A}}_{\operatorname*{{tail}}}+{\mathcal{C}}_{\operatorname*{{tail}}}-{\mathcal{B}}_{\operatorname*{{tail}}}\leq
0$. \par For $V$ defined in Eq.~{}\eqref{eq:defV}, following
Eq.~{}\eqref{eq:boundVend}, ${\mathbb{E}}[V]={\tilde{O}}(\gamma\sigma
D\sqrt{MT^{1+2\epsilon}})$. \par Putting together we have
\@@amsalign&TM\cdot{\mathbb{E}}[{\operatorname*{{DualGap}}}(\bar{z})]\\\ &\leq
O\Big{(}\gamma\sigma D\sqrt{MT}\Big{)}+{2\gamma
MDG}/{\alpha}+{\mathbb{E}}[{\mathcal{A}}_{\operatorname*{{head}}}+{\mathcal{C}}_{\operatorname*{{head}}}+({\mathcal{A}}_{\operatorname*{{tail}}}-{\mathcal{B}}_{\operatorname*{{tail}}}+{\mathcal{C}}_{\operatorname*{{tail}}})+V]\\\
&={\tilde{O}}\Big{(}\gamma\sigma D\sqrt{MT}+\underbracket{\gamma
GDM^{3/2}T^{-\epsilon}+LD^{2}M}_{{\mathcal{A}}_{\operatorname*{{head}}}}+\underbracket{\gamma^{2}LD^{2}T^{2\epsilon}}_{{\mathcal{C}}_{\operatorname*{{head}}}}+\underbracket{\gamma\sigma
D\sqrt{MT^{1+2\epsilon}}}_{V}\Big{)}. \par This finishes the proof of
Theorem~{}\ref{thm:smooth_noV} \end@proof \end{remark}
\par\par\@@numbered@section{appendix}{toc}{Helper Lemmas} \par\begin{lemma}
For any non-negative real numbers $a_{1},\dots,a_{n}\in[0,a]$, and $a_{0}>0$,
it holds
\@@amsalign\sum_{i=1}^{n}\frac{a_{i}}{a_{0}+\sum_{j=1}^{i-1}a_{j}}\leq
2+\frac{4a}{a_{0}}+2\log\Big{(}1+\sum_{i=1}^{n-1}a_{i}/a_{0}\Big{)}.
\rm{\par\addvspace{\medskipamount}\noindent{\bf Proof: }}\ignorespaces[Proof
of Lemma~{}\ref{lm:boundwithlog}] See Lemma A.2 of
\cite[cite]{[\@@bibref{Number}{bach2019universal}{}{}]}. \par\end@proof
\end{lemma} \par\begin{lemma} For any non-negative numbers
$a_{1},\dots,a_{n}\in[0,a]$, and $a_{0}>0$, it holds
\@@amsalign\sqrt{a_{0}+\sum_{i=1}^{n-1}a_{i}}-\sqrt{a_{0}}\leq\sum_{i=1}^{n}\frac{a_{i}}{\sqrt{a_{0}+\sum_{j=1}^{i-1}}a_{j}}\leq\frac{2a}{a_{0}}+3\sqrt{a}+3\sqrt{a_{0}+\sum_{i=1}^{n-1}a_{i}}.
\rm{\par\addvspace{\medskipamount}\noindent{\bf Proof: }}\ignorespaces[Proof
of Lemma~{}\ref{lm:boundwithlog}] See Lemma A.1 of
\cite[cite]{[\@@bibref{Number}{bach2019universal}{}{}]}. \par\end@proof
\end{lemma} \par\par\begin{lemma}9 For any sequence
$\\{z_{t}\\}_{t=1}^{T}\subset{\mathcal{Z}}^{o}$, let $\bar{z}$ denote its
mean. It holds \@@amsalign
T\cdot{\operatorname*{{DualGap}}}(\bar{z})\leq\sup_{z\in{\mathcal{Z}}}{\sum_{t=1}^{T}}\big{\langle}z_{t}-z,G(z_{t})\big{\rangle}.
\end{lemma} \rm{\par\addvspace{\medskipamount}\noindent{\bf Proof:
}}\ignorespaces[Proof of Lemma~{}\ref{lm:gaptoregret}] This lemma depends on
the convexity-concavity of the saddle function $F$. \par Denote
$\bar{z}\vcentcolon=[\bar{x},\bar{y}]$, $z_{t}\vcentcolon=[x_{t},y_{t}]$. Note
$\bar{x}=(1/T){\sum_{t=1}^{T}}x_{t}$ and $\bar{y}=(1/T){\sum_{t=1}^{T}}y_{t}$.
By definition of the duality gap and the convexity-concavity of $F$,
\@@amsalign{\operatorname*{{DualGap}}}(\bar{z})&\vcentcolon=\sup_{x\in{\mathcal{X}},y\in{\mathcal{Y}}}F(\bar{x},y)-F(x,\bar{y})\\\
&\leq\sup_{x\in{\mathcal{X}},y\in{\mathcal{Y}}}\frac{1}{T}{\sum_{t=1}^{T}}F(x_{t},y)-\frac{1}{T}{\sum_{t=1}^{T}}F(x,y_{t}).
Let $G(z_{t})=G(x_{t},y_{t})\vcentcolon=[d_{x,t},-d_{y,t}]$. Since
$d_{x,t}\in\partial_{x}F(x_{t},y_{t})$, for all $x\in{\mathcal{X}}$ and
$y\in{\mathcal{Y}}$ , \@@amsalign F(x_{t},y)+\langle
d_{x,t},x-x_{t}\rangle\leq F(x,y). Similarly, for all $x\in{\mathcal{X}}$ and
$y\in{\mathcal{Y}}$, it holds \@@amsalign F(x,y_{t})+\langle
d_{y,t},y-y_{t}\rangle\geq F(x,y). We have \@@amsalign
T\cdot{\operatorname*{{DualGap}}}(\bar{z})&\leq\sup_{x\in{\mathcal{X}},y\in{\mathcal{Y}}}{\sum_{t=1}^{T}}\langle
d_{x,t},x_{t}-x\rangle-\langle d_{y,t},y_{t}-y\rangle\\\
&=\sup_{z\in{\mathcal{Z}}}{\sum_{t=1}^{T}}\langle G(z_{t}),z_{t}-z\rangle.
This completes the proof of Lemma~{}\ref{lm:gaptoregret}. \end@proof
\par\par\@@numbered@section{appendix}{toc}{Additional Experiments} We
implement our algorithm and conduct all the experiments on a computer with
Intel Core i5 CPU @ 3.20GHz cores, 8GB RAM, and GPU @ GeForce RTX 3090. The
deep learning framework we use is PyTorch 1.8.1. The OS environment was
created by Conda over Ubuntu 20.04. We use Python 3.7. Python library
requirement is specified in the configuration file provided in the
supplemental materials. Due to the hardware limitation, we simulate the
distributed environment by creating object instances to simulate multiple
clients and a central server on one GPU card.
\par\par\par\par\@@numbered@section{subsection}{toc}{Stochastic bilinear
minimax problem} \par\begin{figure*}[tp] \centering \begin{@subfigure}
\includegraphics[width=195.12767pt]{ syn_asyn}\end{@subfigure}
\begin{@subfigure} \includegraphics[width=195.12767pt]{ MKR}\end{@subfigure}
\par\begin{@subfigure} \includegraphics[width=195.12767pt]{
convergence_time}\end{@subfigure} \begin{@subfigure}
\includegraphics[width=195.12767pt]{ vt_sqrt}\end{@subfigure}
\par\@@toccaption{{\lx@tag[ ]{{5}}{\small(a) Residual comparison between
synchronous and asynchronous cases with the communication rounds; (b) Residual
comparison between ${\operatorname*{{LocalAdaSEG}}}$ (Asynchronous and
Synchronous version) and SEGDA-MKR with samples; (c) Residual comparison
between ${\operatorname*{{LocalAdaSEG}}}$ (Asynchronous and Synchronous
version) and SEGDA-MKR with wallclock time; (d) Comparison of $V_{t}$,
$\sqrt{t}$, $t^{2/5}$ with the update $t$. }}}\@@caption{{\lx@tag[: ]{{Figure
5}}{\small(a) Residual comparison between synchronous and asynchronous cases
with the communication rounds; (b) Residual comparison between
${\operatorname*{{LocalAdaSEG}}}$ (Asynchronous and Synchronous version) and
SEGDA-MKR with samples; (c) Residual comparison between
${\operatorname*{{LocalAdaSEG}}}$ (Asynchronous and Synchronous version) and
SEGDA-MKR with wallclock time; (d) Comparison of $V_{t}$, $\sqrt{t}$,
$t^{2/5}$ with the update $t$. }}} \vspace{0cm} \@add@centering\end{figure*}
\par Experimentally, to validate the performance of our proposed method, we
conduct an asynchronous variant of our proposed
${\operatorname*{{LocalAdaSEG}}}$ for the stochastic bilinear minimax problem.
Specifically, we vary the number of local iterations $K$ in $M$ workers, where
$M=4$ and the noise level $\sigma=0.1$. In the case of 'Asynch-50', the local
iteration $K$ is in the range of $\\{50,45,40,35\\}$ for each worker, and
$K=50$ is adopted for all workers in 'Synch-50'. Similarly, in the case of
'Asynch-100', the local iteration $K$ varies in the range of
$\\{100,90,80,70\\}$. In the comparison, $K$ is fixed to 100 for each worker
in the case of 'Synch-100'. As can be seen from
\lx@cref{creftype~refnum}{fig:additional_exp} (a), both asynchronous and
synchronous cases converge to an optimal point after several communication
rounds. Compared with synchronous cases, asynchronicity only affects the
convergence rate that is slower than the synchronous version with respect to
the communication rounds. \par Secondly, we compared our
${\operatorname*{{LocalAdaSEG}}}$ (both Asynchronous and Synchronous versions)
with SEGDA of MKR iterations to solve bilinear minimax problems(refer to
Section 6.1). Specifically, we choose $M=4$ workers, the noise level
$\sigma=0.1$ and local iteration $K=50$ in the Synchronous case, and $K$ in
the range of $\\{50,45,40,35,30\\}$ in the Asynchronous case. To provide
fairness, we run vanilla SEGDA with $M\times K\times R$ iterations on one
worker with batchsize = 1, where $M$ denotes the number of workers, $K$
denotes the number of local iterations and $R$ represents the number of
rounds. The experimental results are illustrated in
\lx@cref{creftype~refnum}{fig:additional_exp} (b). As can be seen, the
performance of SEGDA is unstable and worse than that of
${\operatorname*{{LocalAdaSEG}}}$ (Asyn. and Syn.). The reason is possible
since the batchsize of stochastic gradient $bs=1$ in each iteration results in
a large variance of stochastic gradient estimation. Because there are several
workers involved in the optimization in ${\operatorname*{{LocalAdaSEG}}}$, it
has much more samples in each iteration than that of SEGDA-MKR. It indicates
that the stochastic variance is smaller than that of SEGDA-MKR, resulting in
the stable performance of ${\operatorname*{{LocalAdaSEG}}}$. \par Thirdly, we
also conduct experiments to validate the performance from the aspect of
wallclock time on a bilinear minimax problem, where the number of workers
$M=4$, and the noise level $\sigma=0.1$. We record the wallclock time of
reaching the target residual value for synchronous
${\operatorname*{{LocalAdaSEG}}}$ ($K=50$), the asynchronous version ($K$ in
the range of $\\{50,45,40,35,30\\}$), and the single thread version. The
results are illustrated in \lx@cref{creftype~refnum}{fig:additional_exp} (c).
As can be seen, compared with the single thread version, our proposed method
speed-ups the convergence. With respect to the wall clock time, Asynchronous
${\operatorname*{{LocalAdaSEG}}}$(${\operatorname*{{LocalAdaSEG}}}$-Asyn) is
slightly better than synchronous ${\operatorname*{{LocalAdaSEG}}}$(synchronous
${\operatorname*{{LocalAdaSEG}}}$-Syn). Since the tested bilinear minimax
problem with noise level $\sigma=0.1$ is very simple (time cost is around 20
seconds), the differences in time cost between synchronous and asynchronous
cases are not significant. \par Fourthly, we conduct the experiments with the
bilinear case to evaluate the quantity of $Vt$ with the update t. Here, we
adopt the same experimental settings as that of experiments in Section 6.1.
The noise level $\sigma=0.1$ and the number of workers $M=4$. As can be seen
from \lx@cref{creftype~refnum}{fig:additional_exp} (d), $Vt$ is really much
smaller than the dominant variance term. \par\par\par\begin{figure*}[tp]
\centering\par\begin{@subfigure} \includegraphics[width=195.12767pt]{
diff_opt_with_total_iter_fid_iid}\end{@subfigure} \begin{@subfigure}
\includegraphics[width=195.12767pt]{
diff_opt_with_round_fid_iid}\end{@subfigure} \par\begin{@subfigure}
\includegraphics[width=195.12767pt]{
diff_opt_with_total_iter_is_iid}\end{@subfigure} \begin{@subfigure}
\includegraphics[width=195.12767pt]{
diff_opt_with_round_is_iid}\end{@subfigure} \par\@@toccaption{{\lx@tag[
]{{6}}{\small Subfigures (a)-(b) and (c)-(d) show the results of WGAN trained
with ${\operatorname*{{LocalAdaSEG}}}$ and existing optimizers. We plot FID
and IS against the number of iterations and communications,
respectively.}}}\@@caption{{\lx@tag[: ]{{Figure 6}}{\small Subfigures (a)-(b)
and (c)-(d) show the results of WGAN trained with
${\operatorname*{{LocalAdaSEG}}}$ and existing optimizers. We plot FID and IS
against the number of iterations and communications, respectively.}}}
\@add@centering\end{figure*} \par\par\par\begin{figure*}[tp]
\centering\begin{@subfigure} \includegraphics[width=195.12767pt]{
diff_opt_with_total_iter_fid}\end{@subfigure} \begin{@subfigure}
\includegraphics[width=195.12767pt]{ diff_opt_with_round_fid}\end{@subfigure}
\par\begin{@subfigure} \includegraphics[width=195.12767pt]{
diff_opt_with_total_iter_is}\end{@subfigure} \begin{@subfigure}
\includegraphics[width=195.12767pt]{ diff_opt_with_round_is}\end{@subfigure}
\@@toccaption{{\lx@tag[ ]{{7}}{\small Subfigures (a)-(b) and (c)-(d) show the
results of Federated WGAN trained with ${\operatorname*{{LocalAdaSEG}}}$ and
existing optimizers. We plot FID and IS against the number of iterations and
communications, respectively.}}}\@@caption{{\lx@tag[: ]{{Figure 7}}{\small
Subfigures (a)-(b) and (c)-(d) show the results of Federated WGAN trained with
${\operatorname*{{LocalAdaSEG}}}$ and existing optimizers. We plot FID and IS
against the number of iterations and communications, respectively.}}}
\@add@centering\end{figure*}
\par\par\par\@@numbered@section{subsection}{toc}{Wasserstein GAN} \par
Inspired by game theory, generative adversarial networks (GANs) have shown
great performance in many generative tasks to replicate the real-world rich
content, such as images, texts, and music. GANs are composed of two models, a
generator and a discriminator, which are competing with each other to improve
the performance of a specific task. In this experiment, we aim to train a
digit image generator using the MNIST dataset. \par It is challenging to train
a GAN model due to the slow convergence speed, instability of training or even
failure to converge. \cite[cite]{[\@@bibref{Number}{arjovsky2017towards,
arjovsky2017wasserstein}{}{}]} proposed to use the Wasserstein distance as the
GAN loss function to provide stable and fast training. To enforce the
Lipschitz constraint on the discriminator, we adopt WGAN with gradient penalty
as our experimental model. The objective can be described as
\@@amsalign\mathop{\min}_{G}\mathop{\max}_{D}\bigg{\\{}\mathop{\mathbb{E}}_{x\sim\mathbb{P}_{r}}[D(x)]-\mathop{\mathbb{E}}_{z\sim\mathbb{P}_{z}}\big{[}D\big{(}G(z)\big{)}\big{]}-\lambda\big{[}\big{(}\|\nabla_{\hat{x}}D(\hat{x})\|_{2}-1\big{)}^{2}\big{]}\bigg{\\}}\,,
where $D$ and $G$ denote the generator and discriminator, $\mathbb{P}_{r}$ is
the data distribution, and $\mathbb{P}_{z}$ represents the noise distribution
(uniform or Gaussian distribution). The point
$\hat{x}\sim\mathbb{P}_{\hat{x}}$ is sampled uniformly along straight lines
between pairs of points sampled from the real data distribution
$\mathbb{P}_{r}$ and the generator distribution $\mathbb{P}_{\tilde{x}}$,
expressed as $\hat{x}:=\epsilon x+(1-\epsilon)\tilde{x}$, where $\epsilon\sim
U[0,1]$. \par{\bf DCGAN.} We implement WGAN with the DCGAN architecture, which
improves the original GAN with convolutional layers. Specifically, the
generator consists of $3$ blocks, which contain deconvolutional layers, batch
normalization and activations. The details of the whole generator can be
represented as sequential layers \emph{\\{Linear, BN, ReLU, DeConv, BN, ReLU,
DeConv, BN, ReLU, DeConv, Tanh\\}}, where \emph{Linear}, \emph{BN},
\emph{DeConv} denote the linear, batch normalization and deconvolutional
layer, respectively. \emph{ReLU} and \emph{Tanh} represent the activation
functions. Similarly, the discriminator also contains $3$ blocks, which can be
described as sequential layers \emph{\\{Conv, LReLU, Conv, LReLU, Conv, LReLU,
Linear\\}}, where \emph{Conv} and \emph{LReLU} denote the convolutional layer
and Leaky-ReLU activation function, respectively. \par{\bf Inception score
(IS).} Inception score (IS) is proposed to evaluate the performance of a GAN
with an inception model. IS measures GAN from two aspects simultaneously.
Firstly, GAN should output a high diversity of images. Secondly, the generated
images should contain clear objects. Specifically, we feed the generated
images $x$ into a well-trained inception model to obtain the output $y$. Then,
IS can be calculated by the following equation:
\@@amsalign\mathrm{IS}\vcentcolon=\exp\bigg{(}\mathop{\mathbb{E}}_{x\sim\mathbb{P}_{g}}\big{[}D_{\mathrm{KL}}\big{(}p(y\,|\,x)\|p(y)\big{)}\big{]}\bigg{)},
where $\mathbb{P}_{g}$ is the generator model distribution. Essentially, IS
computes the mutual information $I(y\mathchar
24635\relax\;x)=H(y)-H(y\,|\,x)$, where $H(\cdot)$ denotes the entropy. The
larger $H(y)$, the more diversity in the generated images. The lower
$H(y\,|\,x)$ implies the input $x$ belongs to one class with a higher
probability. In summary, IS is bounded by $1\leq\mathrm{IS}\leq 1000$. The
higher IS implies a better performance of a GAN. \par\par{\bf Fr\'{e}chet
Inception Distance (FID).} Although IS can measure the diversity and quality
of the generated images, it still has some limitations, such as losing sight
of the true data distribution, failure to measure the model generalization.
FID is an improved metric for GAN, which cooperates with the training samples
and generated samples to measure the performance together. Specifically, we
feed the generated samples and training samples into an inception model to
extract the feature vectors, respectively. Usually, we extract the logits
value before the last sigmoid activation as the feature vector with dimension
$2048$. Essentially, FID is the Wasserstein metric between two
multidimensional Gaussian distributions: $\mathcal{N}(\mu_{g},\Sigma_{g})$ the
distribution of feature vectors from generated samples and
$\mathcal{N}(\mu_{r},\Sigma_{r})$ the distribution of feature vectors from the
training samples. It can be calculated as
\@@amsalign\mathrm{FID}\vcentcolon=\|u_{r}-u_{g}\|^{2}+\mathrm{tr}\big{(}\Sigma_{r}+\Sigma_{g}-2(\Sigma_{r}\Sigma_{g})^{1/2}\big{)}
where $\mathrm{tr}(\cdot)$ denotes the trace of a matrix. The lower the FID,
the better the performance of a GAN. \par\par\begin{figure*}[tp]
\centering\par\begin{@subfigure}
\includegraphics[width=195.12767pt]{FID_Diff_Dist}\end{@subfigure}
\begin{@subfigure}
\includegraphics[width=195.12767pt]{IS_Diff_Dist}\end{@subfigure}
\par\@@toccaption{{\lx@tag[ ]{{8}}{\small Subfigures (a)-(b) show the FID and
IS against communication rounds of WGAN trained over MNIST dataset under
different Dirichlet distribution.}}}\@@caption{{\lx@tag[: ]{{Figure 8}}{\small