# Adaptive Federated Learning with Auto-Tuned Clients

Junhyung Lyle Kim1 Mohammad Taha Toghani2 César A. Uribe2 Anastasios
Kyrillidis1
1Department of Computer Science 2Department of Electrical and Computer
Engineering
Rice University
{jlylekim, mttoghani, cauribe<EMAIL_ADDRESS>

###### Abstract

Federated learning (FL) is a distributed machine learning framework where the
global model of a central server is trained via multiple collaborative steps
by participating clients without sharing their data. While being a flexible
framework, where the distribution of local data, participation rate, and
computing power of each client can greatly vary, such flexibility gives rise
to many new challenges, especially in the hyperparameter tuning on both the
server and the client side. We propose $\Delta$-SGD, a simple step size rule
for SGD that enables each client to use its own step size by adapting to the
local smoothness of the function each client is optimizing. We provide
theoretical and empirical results where the benefit of the client adaptivity
is shown in various FL scenarios. In particular, our proposed method achieves
TOP-1 accuracy in 73% and TOP-2 accuracy in 100% of the experiments considered
without additional tuning.

##  1 Introduction

Federated learning (FL) is a distributed machine learning framework that
allows multiple clients to learn a global model collaboratively. Each client
trains the model on its local data and sends only the updated model parameters
to a central server for aggregation. Mathematically, FL aims to solve the
following optimization problem:

$\min_{x\in\mathbb{R}^{d}}f(x):=\frac{1}{m}\sum_{i=1}^{m}f_{i}(x),$ (1)

where $f_{i}(x):=\mathbb{E}_{z\sim\mathcal{D}_{i}}[F_{i}(x,z)]$ is the loss
function of the $i$-th client, and $m$ is the number of clients.

A key property of FL is its flexibility in _how different clients participate
in the overall training_ : the number of clients $m$, their participation
rates, and computing power available to each client can all vary and change at
any point during the overall training procedure. On top of that, each client’s
local data is not shared with other clients or the server, resulting in
certain inherent data privacy [35, 1].

While advantageous, such flexibility and data privacy also introduce a
plethora of new challenges, notably: $i)$ how the server aggregates the local
information coming from each client, and $ii)$ how to make sure each client
meaningfully “learns” using their local data and computing device. The first
challenge was partially addressed in [47], where adaptive optimization
methods, such as Adagrad [13] or Adam [24], were utilized in the aggregation
step. However, the second challenge remains largely unaddressed as we
elaborate below, other than the exception of [57, 59] reviewed in Section 2.

Local data of each client is not shared, which intrinsically implies
heterogeneity in terms of the size and the distribution $\mathcal{D}_{i}$ of
local datasets. That is, $\mathcal{D}_{i}$ differs for each client $i$, as
well as the number of samples $z\sim\mathcal{D}_{i}$. Consequently, $f_{i}(x)$
can vastly differ from client to client, making Problem (1) hard to solve
(i.e., find an approximate minimizer). Moreover, the sheer amount of local
updates is far larger than the number of aggregation steps, given that less
communication is desired (i.e., less server-side aggregation) due to the high
communication cost—typically 3-4$\times$ orders of magnitude more expensive
than local computation—in distributed optimization settings [27].

Figure 1: (A): CIFAR-10 classification task trained on ResNet-18. (B): MNIST
classification task trained on shallow CNN. (C): CIFAR-100 classification task
trained on ResNet-50. All experiments use FedAvg [35] as the server optimizer.

Extensive fine-tuning of the client optimizers is often required to achieve
good performance. For instance, experimental results of the famous FedAvg
algorithm were obtained after performing a grid-search of typically 11-13 step
sizes of the clients’ SGD [35, Section 3], as SGD (and its variants) are
highly sensitive to the step size [36, 52, 4, 23]. Similarly, in [47], 6
different client step sizes were grid-searched for different tasks, and not
surprisingly, each task requires a different client step size to obtain the
best result, regardless of the server-side adaptivity [47, Table 8].
Importantly, even these “fine-tunings” are done under the setting that all
clients use the same step size, which is sub-optimal, given that $f_{i}$ can
be vastly different per client; we analyze this further in Section 2.

Initial examination as motivation. The implication of not properly tuning the
client optimizer is highlighted in Figure 1. We plot the progress of test
accuracies for different client optimizers, where, for all the other test
cases, we intentionally use the same step size rules that were fine-tuned for
the task in Figure 1(A). There, we train a ResNet-18 for CIFAR-10 dataset
classification within an FL setting, where the best step sizes were used for
all algorithms after grid-search; we defer the experimental details to Section
4. Hence, all methods perform reasonably well, although $\Delta$-SGD, our
proposed method, achieves noticeably better test accuracy when compared to
non-adaptive SGD variants –e.g., a 5% difference in final classification
accuracy from SGDM– and comparable final accuracy only with adaptive SGD
variants, like Adam and Adagrad.

In Figure 1(B), we train a shallow CNN for MNIST data classification using the
same step size rules. MNIST classification is now considered an “easy” task,
and therefore SGD with the same constant and decaying step sizes from Figure
1(A) works well. However, with momentum, SGDM exhibits highly oscillating
behavior, which results in slow progress and poor final accuracy, especially
without decaying the step size. Adaptive optimizers, like Adam and Adagrad,
show similar behavior, falling short in achieving good final accuracy,
compared to their performance in the case of Figure 1(A).

Similarly, in Figure 1(C), we plot the test accuracy progress for CIFAR-100
classification trained on ResNet-50, again using the same step size rules as
before. Contrary to Figure 1(B), SGD with momentum (SGDM) works better than
SGD, both with the constant and the decaying step sizes. Adam becomes a “good
optimizer” again, but its “sibling”, Adagrad, performs worse than SGDM. On the
contrary, our proposed method, $\Delta$-SGD, which we introduce in Section 3,
achieves superior performance in all cases without any additional tuning.

The above empirical observations beg answers to important and non-trivial
questions in training FL tasks using variants of SGD methods as the client
optimizer: Should the momentum be used? Should the step size be decayed? If
so, when? Unfortunately, Figure 1 indicates that the answers to these
questions highly vary depending on the setting; once the dataset itself or how
the dataset is distributed among different clients changes, or once the model
architecture changes, the client optimizers have to be properly re-tuned to
ensure good performance. Perhaps surprisingly, the same holds for adaptive
methods like Adagrad [13] and Adam [24].

Our hypothesis and contributions. Our paper takes a stab in this direction: we
propose DELTA-SGD (DistributEd LocaliTy Adaptive SGD), a simple adaptive SGD
scheme, that does not require any knowledge of the problem constants, such as
the $L$-smoothness parameter. We will refer to our algorithm as $\Delta$-SGD
in the rest of the text. Our adaptive step size is extended from [34], where
the focus was centralized convex optimization; we defer the readers to Section
3 for details. Our contributions can be summarized as follows:

  * •

We extend the (centralized) adaptive step size from [34] to the FL setting.
The implication of this adaptive step size in FL is twofold: $i)$ each client
can use its own step size, and $ii)$ each client’s step size adapts to the
local smoothness of $f_{i}$—hence LocaliTy Adaptive— and can even increase
during local iterations. Moreover, thanks to the simplicity of the proposed
step size, our method is agnostic to the server optimizer as well as the loss
function, and thus can be easily combined with server adaptive methods such as
FedAdam [47], or methods that use different (regularized) loss functions such
as FedProx [31] or MOON [30].

  * •

We provide convergence analysis of $\Delta$-SGD in a general nonconvex setting
(Theorem 1). We also provide the convergence analysis in the convex setting,
extending the analysis from [34] to a distributed one, as well as a simple
centralized nonconvex convergence analysis, which was an open question posed
in [34]. Due to space constraints, we only state the result of general
nonconvex case in Theorem 1, and defer other theorems and proofs to Appendix
A.

  * •

We evaluate our approach on several benchmark datasets and demonstrate that
$\Delta$-SGD achieves superior performance compared to other state-of-the-art
FL methods. Our experiments show that our method can effectively adapt the
client step size to the underlying data distribution and achieve faster
convergence of the global model, without any additional tuning. Our approach
can help overcome the client step size tuning challenge in FL and enable more
efficient and effective collaborative learning in distributed systems.

##  2 Preliminaries and Related Work

A bit of background on optimization theory. Arguably the most fundamental
optimization algorithm for minimizing a function
$f(x):\mathbb{R}^{d}\rightarrow\mathbb{R}$ is the gradient descent (GD) [8],
which iterates with the step size $\eta_{t}$ as: $x_{t+1}=x_{t}-\eta_{t}\nabla
f(x_{t})$. Under the assumption that $f$ is globally $L$-smooth, that is:

$\|\nabla f(x)-\nabla f(y)\|\leqslant L\cdot\|x-y\|\quad\forall x,y,$ (2)

the step size $\eta_{t}=\frac{1}{L}$ is the “optimal” step size for GD, which
converges at the rate, which is not improvable [37, 12], for convex $f$:

$f(x_{t+1})-f(x^{\star})\leqslant\frac{L\|x_{0}-x^{\star}\|^{2}}{2(2t+1)},$
(3)

while $\eta_{t}\in(0,\frac{2}{L})$ defines the “admissible” step size range
required to ensure that GD converges for this function class [43]. Similarly,
if $f$ is also (globally) $\mu$-strongly convex, that is:

$f(x)\geqslant f(y)+\langle\nabla
f(y),x-y\rangle+\tfrac{\mu}{2}\|x-y\|^{2}~{}~{}\forall x,y,$

then the optimal step size is $\eta_{t}=\frac{2}{\mu+L}$ [37], and the rate
improves to a linear one:

$\|x_{t+1}-x^{\star}\|^{2}\leqslant\Big{(}\frac{L-\mu}{L+\mu}\Big{)}^{t}\|x_{0}-x^{\star}\|^{2}.$

Limitations of popular step sizes. In practice, however, the constants $L$ and
$\mu$ are rarely known [7]. As such, there has been a plethora of efforts in
the optimization community to come up with a general step size rule or method
that does not require a priori knowledge of problem constants [38, 40, 29], so
that an optimization algorithm can work as “plug-and-play.”

This is a well-known research question, with some major lines of work on this
direction being: $i)$ line-search [2, 41], $ii)$ adaptive learning rate (e.g.,
Adagrad [13] and Adam [24]), and $iii)$ Polyak step size [44, 17], to name a
few. Unfortunately, the search for the “perfect” step size is still active
[33, 11, 10, 5, 28], as the aforementioned approaches have limitations. For
instance, to use line search, solving a sub-routine is often required,
inevitably incurring additional evaluations of the function and/or the
gradient. To use methods like Adagrad and Adam, the knowledge of the initial
distance from the solution set $D$, which is nontrivial to find, is required
to ensure good performance [10]; see also Section 4. Lastly, Polyak step size
requires a sharp knowledge of $f(x^{\star})$ [17], which is not always known a
priori, and is unclear what value to use for an arbitrary loss function and
model.

Implications in FL scenarios. On top of that, even with the knowledge of $L$,
GD can be slow. Indeed, the global $L$-smoothness condition, as described
above, needs to be satisfied for all $x$ and $y$, implying even finite $L$ can
be arbitrarily large. This results in a small step size, leading to slow
convergence, as seen in (3).

Naturally, the challenge is aggravated in the distributed case. To solve (1),
under the assumption that each $f_{i}$ is $L_{i}$-smooth, the step size of the
form ${1}/{L_{\text{max}}}$ where ${L_{\text{max}}}:=\max_{i}L_{i}$ is often
used [62, 48, 46], to ensure convergence [53]. Yet, one can easily imagine a
situation where $L_{i}\gg L_{j}$ for $i\neq j,$ in which case the convergence
of $f_{j}(x)$ can be arbitrarily slow by using step size
${1}/{L_{\text{max}}}$.

There are plenty of practical examples where such a scenario could happen. For
instance, imagine smartphone photo albums of the members of a fishing club
versus a bird-watching club. The albums of these two groups could have vastly
different data distributions, one skewed with pictures including fishes and
rivers, while the other skewed with birds and forests [56]. On top of that,
smartphones from different manufacturers nowadays have distinctly different
camera filters applied—recently a big selling point for companies like Apple,
introducing technologies like “portrait mode,” and Samsung, introducing
100$\times$ zoom capability, both based on image processing techniques—making
even similar pictures to have distinct pixel values, when taken with different
smartphones.

Therefore, to ensure that each client learns useful information in the FL
setting as in (1), ideally: $i)$ each agent should be able to use its own step
size, instead of crude ones like $1/L_{\text{max}}$ for all; $ii)$ the
individual step size should be “locally adaptive” to the function $f_{i},$
(i.e., even $1/L_{i}$ can be too crude, analogously to the centralized GD);
and $iii)$ the step size should not depend on problem constants like $L_{i}$
an $\mu_{i}$, which are often unknown. In Section 3, we introduce DistributEd
LocaliTy Adaptive SGD ($\Delta$-SGD), which satisfies all of the
aforementioned desiderata.

Related work on FL. FedAvg [35] is the simplest and probably the most famous
FL algorithm, which takes a (weighted) average of the client parameters in the
aggregation step after clients perform some local iterations. While FedAvg has
achieved great results empirically, it has been observed recently that it can
suffer from model drift [45] induced by the heterogeneity [19]. At the core,
simple averaging is too crude of an operation. As such, FedAvg uses a weighted
average heuristic, where the weights are based on the number of data $n_{i}$
for each client $i$ [35].

The authors in [47] took this idea one step further: it showed that FedAvg can
be seen as a special case where both the clients and the server use the SGD
optimizer, with a server learning rate of 1. To handle the heterogeneity and
the model drift, they proposed to use adaptive optimization scheme at the
server, resulting in, e.g., FedAdam or FedYogi, which respectively use Adam
[24] and Yogi [63] as the server optimizer, and can improve upon FedAvg in
various scenarios. Note that this fundamentally differs from our approach,
where we propose a client adaptive optimizer that can be easily combined with
sophisticated server-side aggregation methods like FedAdam.

Perhaps the closest works in spirit to our work are AdaAlter [59] and locality
adaptivity in FL [57]. Both works utilize an adaptive client optimizer,
similar to Adagrad [13], with either delayed or restarted updates on the
adaptive variables (e.g., pre-conditioners and momentum buffers). However, as
noted in [47], AdaAlter incurs twice the memory compared to FedAvg, as
AdaAlter requires communicating both the model parameters as well as the
“client accumulators,” which is of the same dimension as model parameters.
[57] overcomes this issue by simply restarting the client optimizer states,
but requires complicated local and global correction step to achieve good
performance. On the contrary, $\Delta$-SGD changes virtually nothing compared
to FedAvg other than the simple step size computation, and yet still achieves
impressive performance; see Section 4.

Other approaches have handled the heterogeneity by changing the loss function.
FedProx [31] adds an $\ell_{2}$-norm proximal term to the individual loss
functions such that the local parameters do not diverge too much from the
previously communicated global model. Similarly, MOON [30] uses the cross-
entropy loss between the current and previous models. As mentioned in the
introduction, our proposed method can be seamlessly combined with these
approaches.

Another line of works attempts to handle heterogeneity by utilizing control-
variates [45, 32, 21], a similar idea to variance reduction from single-
objective optimization [20, 16]. While theoretically appealing, these methods
either require full gradient computation periodically or are not usable when
not all the clients participate, as the clients must maintain a state
throughout all rounds.

##  3 DELTA($\Delta$)-SGD: Distributed locality adaptive SGD

In [34], a novel step size rule for (centralized) GD was introduced, which
adapts to the minimization function’s local geometry. The proposed step size
is clever and strikingly simple:

$\eta_{t}=\min\Big{\\{}\tfrac{\|x_{t}-x_{t-1}\|}{2\|\nabla f(x_{t})-\nabla
f(x_{t-1})\|},\sqrt{1+\theta_{t-1}}\eta_{t-1}\Big{\\}},\quad\theta_{t-1}=\eta_{t-1}/\eta_{t-2}.$
(4)

The step size in (4) adapts to the _local smoothness_ of the iterates, that
is:

$\|\nabla f(x_{t})-\nabla f(x_{t-1})\|\leqslant
L_{t}\cdot\|x_{t}-x_{t-1}\|,\quad\forall t=1,2,\dots$ (5)

and hence can increase during iterations, while the second condition in (4)
ensures that $\eta_{t}$ does not increase arbitrarily. By definition, $L_{t}$
in (5) is never bigger than the global $L$ in (2), resulting in faster
convergence in practice [34, Section 4]. Note that (4) is vastly different
from some standard adaptive methods like Adagrad [13], which can only decrease
the learning rate, as they accumulate non-negative quantities in the
denominator of the step size. As a result, the scalar multiplied to their
“adaptive” learning rates play a crucial role and requires proper tuning,
similarly to vanilla SGD, as evident in Figure 1; see also Table 1 in Section
4.

We now introduce DELTA($\Delta$)-SGD: DistributEd LocaliTy Adaptive SGD, where
we extend (4) to the FL setting, with the inclusion of stochasticity and local
iterations, as summarized in Algorithm 1. For brevity, we use
$\tilde{\nabla}f_{i}(x)=\frac{1}{|\mathcal{B}|}\sum\limits_{z\in\mathcal{B}}F_{i}(x,z)$
to denote the stochastic gradients with batch size $|\mathcal{B}|=b.$

Algorithm 1 DELTA($\Delta$)-SGD: DistributEd LocaliTy Adaptive SGD

1:input: $x_{0}\in\mathbb{R}^{d}$, $\eta_{0},\theta_{0},\gamma>0$, and
$p\in(0,1)$.

2:for each round $t=0,1,\ldots,T{-}1$ do

3: sample a subset $\mathcal{S}_{t}$ of clients with size
$|\mathcal{S}_{t}|=p\cdot m$

4: for each machine in parallel for $i\in\mathcal{S}_{t}$ do

5: Set $x_{t,0}^{i}=x_{t}$

6: Set $\eta_{t,0}^{i}=\eta_{0}$ and $\theta_{t,0}^{i}=\theta_{0}$

7: for local step $k\in[K]$ do

8:
$x_{t,k}^{i}=x_{t,k-1}^{i}-\eta_{t,k-1}^{i}\tilde{\nabla}f_{i}(x_{t,k-1}^{i})$
$\triangleright$ update local parameter with $\Delta$-SGD

9:
$\eta_{t,k}^{i}=\min\Big{\\{}\frac{\gamma\|x_{t,k}^{i}-x_{t,{k-1}}^{i}\|}{2\|\tilde{\nabla}f_{i}(x_{t,k}^{i})-\tilde{\nabla}f_{i}(x_{t,{k-1}}^{i})\|},\sqrt{1+\theta_{t,k-1}^{i}}\eta_{t,k-1}^{i}\Big{\\}}$

10: $\theta_{t,k}^{i}=\eta_{t,k}^{i}/\eta_{t,k-1}^{i}$ $\triangleright$ (line
10 & 11) update locality adaptive step size

11: end for

12: end for

13:
$x_{t+1}=\frac{1}{|\mathcal{S}_{t}|}\sum\limits_{i\in\mathcal{S}_{t}}x_{t,K}^{i}$
$\triangleright$ server-side aggregation

14:end for

15:return $x_{T}$

We make a few remarks about Algorithm 1. First, the input $\eta_{0}>0$ can be
quite arbitrary, as it can be corrected, per client level, in the 1st local
iteration (line 9); similarly for $\theta_{0}>0$ (line 10). Second, as the
step size $\eta_{t,k}^{i}$ requires two successive stochastic gradients, there
could be two options: using $i)$ the same batch or $ii)$ a new batch; the
second option will incur additional memory requirement, so we use the
first.111This distinction was already analyzed in the centralized setting, and
it was reported that using the same batch performed better in practice [34].
Third, we include the “amplifier” $\gamma$ to the first condition of step size
(line 9), but this is only needed for Theorem 1.222In practice, we did not
change from the default value $\gamma=2$ in the original implementation in
https://github.com/ymalitsky/adaptive_GD/blob/master/pytorch/optimizer.py.
fourth, after local steps are done, $\eta_{0}$ is re-used (line 6); we could
potentially use a more sophisticated approach and use a similar adaptive step
size to line 9, but we leave this for future work. Last, we present simple
averaging as the server-side aggregation for simplicity (line 13), but more
sophisticated methods like FedAdam [47] can be used instead.

###  3.1 Convergence Analysis

Technical challenges. Before we present the convergence analysis, let us
elaborate on the non-trivial technical challenges of analyzing Algorithm 1.
The main difference of analyzing Algorithm 1 compared to other
distributed/decentralized optimization theory is that the step size
$\eta_{t,k}^{i}$ not only depends on the round $t$ and local steps $k$ (which
is a challenge shared by other analyses), but also on $i$, the client. To deal
with the client-dependent step size, we require a slightly non-standard
assumption on the dissimilarity between $f$ and $f_{i}$, as shown below.

######  Assumption 1.

There exist nonnegative constants $\sigma,\rho,$ and $G$ such that for all
$i\in[M]$ and $x\in\mathbb{R}^{d}$,

$\displaystyle\mathbb{E}\|\nabla F_{i}(x,z)-\nabla f_{i}(x)\|$
$\displaystyle\leqslant\sigma^{2},$ (bounded variance) (1a)
$\displaystyle\|\nabla f_{i}(x)\|$ $\displaystyle\leqslant G,$ (bounded
gradient) (1b) $\displaystyle\|\nabla f_{i}(x)-\nabla f(x)\|^{2}$
$\displaystyle\leqslant\rho\|\nabla f(x)\|^{2}.$ (strong growth of
dissimilarity) (1c)

Assumption 1a has been standard in stochastic optimization literature [36, 14,
50, 22]; recently, this assumption has been relaxed to weaker ones such as
weak growth assumption [6] or expected smoothness [15], but this is out of
scope of this work. Assumption 1b is fairly standard in nonconvex optimization
[63, 58], and often used in FL setting [59, 60, 47]. Assumption 1c is
reminiscent of the strong growth assumption in stochastic optimization
literature [49], which is still used in recent works [9, 54, 55]. To the best
of our knowledge, this is the first theoretical analysis of the FL setting
where clients can use their step size. We now present the main convergence
theorem of Algorithm 1.

######  Theorem 1.

Let Assumption 1 hold, with $\rho=\mathcal{O}(1)$. Further, suppose that
$\gamma=\mathcal{O}(\frac{1}{K\sqrt{T}})$, and $\eta_{0}=\mathcal{O}(\gamma)$.
Then, the following property holds for Algorithm 1, for $T$ sufficiently
large:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\,\mathbb{E}\left\|\nabla
f\left(x_{t}\right)\right\|^{2}$
$\displaystyle\leqslant\mathcal{O}\left(\frac{\Psi_{1}}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\tilde{L}^{2}\Psi_{2}}{T}\right)+\mathcal{O}\left(\frac{\tilde{L}^{3}\Psi_{2}}{\sqrt{T^{3}}}\right),$

where
$\Psi_{1}=\max\left\\{\frac{\sigma^{2}}{b},f(x_{0})-f(x^{\star})\right\\}$ and
$\Psi_{2}=\left(\frac{\sigma^{2}}{b}+G^{2}\right)$ are global constants, with
$b=|\mathcal{B}|$ being the batch size; $\tilde{L}$ is a constant at most the
average of local smoothness, i.e., $\max_{t}\frac{1}{m}\sum_{i=1}^{m}L_{i,t},$
where $L_{i,t}$ the local smoothness of $f_{i}$ at round $t$.

The convergence result in Theorem 1 implies a sublinear convergence to an
$\varepsilon$-first order stationary point with at least
$T=\mathcal{O}(\varepsilon^{-2})$ communication rounds. We emphasize again
that the conditions on $\gamma$ and $\eta_{0}$ are only required for our
theory.333In all experiments in Section 4, we use the default setting
$\gamma=2$, and $\eta_{0}=0.2$, without additional tuning. Importantly, we did
not assume $f_{i}$ is $L$-smooth (or even $L_{i}$-smooth), a standard
assumption in nonconvex optimization and FL literature [58, 25, 31, 47];
instead, we can obtain a smaller quantity, $\tilde{L}$, through our analysis
in a similar vein to (5); for space limitation, we defer the details and the
proof to Appendix A.

##  4 Experimental Setup and Results

Datasets and models. To test the performance of different client optimizers in
various settings, we evaluate on four datasets commonly used in FL scenarios:
MNIST, FMNIST, CIFAR-10, and CIFAR-100 [26]. For MNIST and FMNIST, we train a
shallow CNN with two convolutional and two fully-connected layers, followed by
dropout and ReLU activations. For CIFAR-10, we train a ResNet-18 [18]. For
CIFAR-100, we train both a ResNet-18 and a ResNet-50 to study the effect of
changing the model architecture.

For each dataset, we create a federated version by randomly partitioning the
training data among $100$ clients, with each client getting $500$
examples.444All the datasets we consider have $50,000$ training samples,
leading to $500$ samples distributed per client. To control the level of “non-
iidness”, we apply latent Dirichlet allocation (LDA) over the labels following
[19], where each client has an associated multinomial distribution over the
labels from which its examples are drawn. That is, the local training examples
of each client has been drawn from a categorical distribution over $N$
classes, parameterized by $\mathbf{q}$, such that
$\mathbf{q}\sim\text{Dir}(\alpha\mathbf{p}),$ where $\mathbf{p}$ is a prior
distribution over $N$ classes, with $\alpha>0$ being the concentration
parameter. We vary $\alpha\in\\{0.01,0.1,1\\}$, where bigger $\alpha$
indicates settings closer to i.i.d. scenarios. The class distribution of
different $\alpha$’s is visualized in Figure 5 in Appendix B.

FL setup and optimizers. For all cases, we fix the number of clients to be
$100,$ and randomly sample $10\%$ among the $100$ clients. Similarly to [47,
31], we perform $E$ local epochs of training over each client’s dataset, and
we utilize mini-batch gradients of size $b=64$, leading to
$K\approx\lfloor\tfrac{E\cdot 500}{64}\rfloor$ local gradient steps; we use
$E=1$ for all settings. For client optimizers, we compare stochastic gradient
descent (SGD), SGD with momentum (SGDM), adaptive methods including Adam [24],
Adagrad [13], SGD with stochastic Polyak step size (SPS) [33], and our
proposed method: $\Delta$-SGD in Algorithm 1. As our focus is on client
adaptivity, we only present the results using simple FedAvg [35] as the server
optimizer.

Hyperparameters. For all methods, we perform a simple grid search on a single
task: CIFAR-10 classification trained with ResNet-18, with Dirichlet
concentration parameter $\alpha=0.1$; for the rest of the settings, we use the
same hyperparameters. For SGD, we perform a grid search with
$\eta\in\\{0.01,0.05,0.1,0.5\\}$. For SGDM, we use the same grid for $\eta$
and use momentum parameter $\beta=0.9$. For Adam, we tried
$\eta\in\\{0.001,0.01\\},$ and for Adagrad, we tried $\eta\in\\{$0.01, 0.1}
(i.e., the default learning rates in Pytorch and their one-tenths). For SPS,
we use the default setting of the official implementation.555I.e., we use
$f_{i}^{\star}=0$, an $c=0.5,$ for the SPS step size:
$\frac{f_{i}(x)-f_{i}^{\star}}{c\|\nabla f_{i}(x)\|^{2}}$. The official
implementation can be found in https://github.com/IssamLaradji/sps For
$\Delta$-SGD, we append $\delta$ in front of the second condition:
$\sqrt{1+\delta\theta_{t,k-1}^{i}}\eta_{t,k-1}^{i}$ following [34], and use
$\delta=0.1$ for all experiments (however, as shown in Figure 4 in Appendix B,
$\delta$ has little impact on final accuracy in most cases). To account for
the SGD(M) fine-tuning done in practice, we also tested dividing the step size
(LR decay) by 10 after $50\%$, and then again by 10 after $75\%$ of the total
training rounds and report the inclusive results in Table 1. Finally, for the
number of rounds $T$, we use $500$ for MNIST, $1000$ for FMNIST, and $2000$
for CIFAR-10 and CIFAR-100.

Implementation. We use Pytorch [42] to implement all experiments and run on
eight P100 GPUs. Our implementation will be available online after the
anonymous review process for reproducibility.

Figure 2: The effect of stronger heterogeneity on different client optimizers,
induced by the Dirichlet concentration parameter $\alpha$.

###  4.1 Results

Results of the experiments detailed in the previous subsection are presented
in Table 1. Below, we make comprehensive remarks, depending on: $i)$ the level
of heterogeneity induced by different $\alpha$’s of the Dirichlet
concentration parameter, $ii)$ the effect of changing the model architecture,
and $iii)$ the effect of changing the dataset, and how these affect the
performance of different client optimizers.

Non-iidness | Optimizer | Dataset / Model
---|---|---
$\text{Dir}(\alpha\cdot\mathbf{p})$ |  | MNIST | FMNIST | CIFAR-10 | CIFAR-100 | CIFAR-100
CNN | CNN | ResNet-18 | ResNet-18 | ResNet-50
$\alpha=1$ | SGD | 98.3↓(0.2) | 86.5↓(0.8) | 87.7↓(2.1) | 57.7↓(4.2) | 53.0↓(12.8)
SGD ($\downarrow$) | 97.8↓(0.7) | 86.3↓(1.0) | 87.8↓(2.0) | 61.9↓(0.0) | 60.9↓(4.9)
SGDM | 98.5↓(0.0) | 85.2↓(2.1) | 88.7↓(1.1) | 58.8↓(3.1) | 60.5↓(5.3)
SGDM ($\downarrow$) | 98.4↓(0.1) | 87.2↓(0.1) | 89.3↓(0.5) | 61.4↓(0.5) | 63.3↓(2.5)
Adam | 94.7↓(3.8) | 71.8↓(15.5) | 89.4↓(0.4) | 55.6↓(6.3) | 61.4↓(4.4)
Adagrad | 64.3↓(34.2) | 45.5↓(41.8) | 86.6↓(3.2) | 53.5↓(8.4) | 51.9↓(13.9)
SPS | 10.1↓(88.4) | 85.9↓(1.4) | 82.7↓(7.1) | 1.0↓(60.9) | 50.0↓(15.8)
$\Delta$-SGD | 98.4↓(0.1) | 87.3↓(0.0) | 89.8↓(0.0) | 61.5↓(0.4) | 65.8↓(0.0)
$\alpha=0.1$ | SGD | 98.1↓(0.0) | 83.6↓(2.8) | 72.1↓(12.9) | 54.4↓(6.7) | 44.2↓(19.9)
SGD ($\downarrow$) | 98.0↓(0.1) | 84.7↓(1.7) | 78.4↓(6.6) | 59.3↓(1.8) | 48.7↓(15.4)
SGDM | 97.6↓(0.5) | 83.6↓(2.8) | 79.6↓(5.4) | 58.8↓(2.3) | 52.3↓(11.8)
SGDM ($\downarrow$) | 98.0↓(0.1) | 86.1↓(0.3) | 77.9↓(7.1) | 60.4↓(0.7) | 52.8↓(11.3)
Adam | 96.4↓(1.7) | 80.4↓(6.0) | 85.0↓(0.0) | 55.4↓(5.7) | 58.2↓(5.9)
Adagrad | 89.9↓(8.2) | 46.3↓(40.1) | 84.1↓(0.9) | 49.6↓(11.5) | 48.0↓(16.1)
SPS | 96.0↓(2.1) | 85.0↓(1.4) | 70.3↓(14.7) | 42.2↓(18.9) | 42.2↓(21.9)
$\Delta$-SGD | 98.1↓(0.0) | 86.4↓(0.0) | 84.5↓(0.5) | 61.1↓(0.0) | 64.1↓(0.0)
$\alpha=0.01$ | SGD | 96.8↓(0.7) | 79.0↓(1.2) | 22.6↓(11.3) | 30.5↓(1.3) | 24.3↓(7.1)
SGD ($\downarrow$) | 97.2↓(0.3) | 79.3↓(0.9) | 33.9↓(0.0) | 30.3↓(1.5) | 24.6↓(6.8)
SGDM | 77.9↓(19.6) | 75.7↓(4.5) | 28.4↓(5.5) | 24.8↓(7.0) | 22.0↓(9.4)
SGDM ($\downarrow$) | 94.0↓(3.5) | 79.5↓(0.7) | 29.0↓(4.9) | 20.9↓(10.9) | 14.7↓(16.7)
Adam | 80.8↓(16.7) | 60.6↓(19.6) | 22.1↓(11.8) | 18.2↓(13.6) | 22.6↓(8.8)
Adagrad | 72.4↓(25.1) | 45.9↓(34.3) | 12.5↓(21.4) | 25.8↓(6.0) | 22.2↓(9.2)
SPS | 69.7↓(27.8) | 44.0↓(36.2) | 21.5↓(12.4) | 22.0↓(9.8) | 17.4↓(14.0)
$\Delta$-SGD | 97.5↓(0.0) | 80.2↓(0.0) | 31.6↓(2.3) | 31.8↓(0.0) | 31.4↓(0.0)
Table 1: Experimental results based on the settings detailed in Section 4.
Performance difference within 0.5% of the best result for each task are shown
in bold. Subscripts↓(x.x) is the performance difference from the best result
and is highlighted in pink when the difference is bigger than 2%. The symbol
($\downarrow$) appended to SGD and SGDM indicates step-wise learning rate
decay, where the step sizes are divided by $10$ after 50%, and another by $10$
after 75% of the total rounds.

Changing the level of non-iidness. We first investigate how the performance of
different client optimizers degrade in increasing degrees of heterogeneity by
varying the concentration parameter $\alpha\in\\{1,0.1,0.01\\}$ multiplied to
the prior of Dirichlet distribution, following [19].

Three illustrative cases are visualized in Figure 2. We remind that the
hyperparameters are tuned for the case of CIFAR-10 trained with ResNet-18,
with $\alpha=0.1$ (Figure 2(A)). For this task, with $\alpha=1$ (i.e., closer
to iid), all methods perform better than $\alpha=0.1,$ as expected. With
$\alpha=0.01,$ which is highly non-iid (c.f., Figure 5 in Appendix B), we see
a significant drop in performance for all methods. SGD with LR decay and
$\Delta$-SGD perform the best, while adaptive methods like Adam
($85\%\rightarrow 22.1\%$) and Adagrad ($84.1\%\rightarrow 12.5\%$) degrade
noticeably more than other methods.

For FMNIST trained with CNN (Figure 2(B)), which can be considered as an
easier problem compared to CIFAR-10 classification, the performance
degradation with varying $\alpha$’s is much milder. Interestingly, adaptive
methods like Adam, Adagrad, and SPS perform much worse than other methods,
indicating their inflexibility when applied to diverse datasets and model
architectures, which often is worse than simple SGD-based methods; we further
investigate this phenomenon in more detail in the next remark.

A similar trend can be seen in MNIST classification, where SGD-based methods
work relatively well, except for SGDM with $\alpha=0.01$: without the LR
decay, SGDM only achieves around 78% accuracy, while SGD without LR decay
still achieves over $96\%$ accuracy (c.f., Figure 1(A)). Even with the LR
decay, SGDM achieves noticeably worse performance. While this may seem like an
“easy fix” in hindsight, it indicates that in a highly non-iid setting, one
should be extremely careful in tuning SGD-based methods, even for easy
datasets like MNIST. Interestingly, SPS performs particularly poorly, merely
achieving 10% for MNIST with $\alpha=1,$ while achieving 96% for “harder” case
of $\alpha=0.1,$ and again dropping to 69.7% with $\alpha=0.01$; a possible
explanation is, with simple CNN, the model is not over-parameterized enough to
have $f_{i}^{\star}=0,$ the default estimate we use on which the performance
of SPS crucially rely [17]. Adagrad similarly performs quite poorly.

Lastly, in Figure 2(C), results for CIFAR-100 classification trained with
ResNet-50 are illustrated. $\Delta$-SGD exhibits superior performance in all
cases of $\alpha$. Unlike MNIST and FMNIST, Adam enjoys the second
($\alpha=0.1$) or the third ($\alpha=1$) best performance in this task,
complicating how one should “tune” Adam for the task at hand. Other methods,
including SGD with and without momentum/LR decay, Adagrad, and SPS, perform
much worse than $\Delta$-SGD.

Changing the model architecture. For this remark, let us focus on CIFAR-100
trained on ResNet-18 versus on ResNet-50, with $\alpha=0.1$, illustrated in
Figure 3(A). SGD and SGDM (both with and without LR decay), Adagrad, and SPS
perform worse using ResNet-50 than ResNet-18. This is a counter-intuitive
behavior, as one would expect to get better accuracy by using a more powerful
model. $\Delta$-SGD is an exception: without any additional tuning,
$\Delta$-SGD can improve its performance. Adam also improves similarly, but
the achieved accuracy is significantly worse than that of $\Delta$-SGD. While
it is true that the performance of $\Delta$-SGD also slightly degrades for
$\alpha=0.01,$ it still performs better than the other methods.

Changing the dataset. We now focus on cases where the dataset changes, but the
model architecture remains the same. We mainly consider two cases, illustrated
in Figure 3(B) and (C): When CNN is trained for classifying MNIST versus
FMNIST, and when ResNet-18 is trained for CIFAR-10 versus CIFAR-100.
Aggravating the complexity of fine-tuning SGD(M) for MNIST, one can observe a
similar trend in CIFAR-10 trained with ResNet-18. In that case, $\Delta$-SGD
does not achieve the best test accuracy (although it is the second best with a
pretty big margin with the rest), while SGD with LR decay does. However,
without LR decay, the accuracy achieved by SGD drops _more than_ 11%.

Interestingly, for the same setting, when we change the dataset from CIFAR-10
to CIFAR-100, SGD without LR decay (which is not one of the best methods for
the CIFAR-10 case) achieves the second-best performance (after $\Delta$-SGD).
On the other hand, SGDM with LR decay, which achieves the 3rd best performance
for CIFAR-10 achieves very poor performance (more than 10% less than the best)
for CIFAR-100. Finally, SGD with decay, which performs the best in the
CIFAR-10 case, turns out to be the 3rd best algorithm when we change the
dataset to CIFAR-100. Again, adaptive methods like Adam, Adagrad, and SPS
perform quite poorly in this case.

Figure 3: The effect of changing the dataset and the model architecture on
different client optimizers. (A): CIFAR-100 trained with ResNet-18 versus
Resnet-50 ($\alpha=0.1$), (B): MNIST versus FMNIST trained with CNN
($\alpha=0.01$), (C): CIFAR-10 versus CIFAR-100 trained with ResNet-18
($\alpha=0.01$).

##  5 Conclusion

In this work, we propose $\Delta$-SGD, a distributed SGD scheme equipped with
an adaptive step size that enables each client to use its step size and adapts
to the local smoothness of the function each client is optimizing. We prove
the convergence of $\Delta$-SGD in the general nonconvex setting and present
extensive empirical results, where the superiority of $\Delta$-SGD is shown in
various scenarios without any tuning. For future works, extending $\Delta$-SGD
to a coordinate-wise step size in spirit of [13, 24], as well as enabling
asynchronous updates [3, 51, 39] could be interesting directions.

Broader Impacts and Limitations. We believe our proposed method, $\Delta$-SGD,
can potentially impact reducing the amount of tuning required in training FL
models. By now, it is widely believed that FL systems do not “dodge the
bullet” of high carbon emission in AI/ML: as noted in a recent study [61],
“compute on client devices, and the communication between the clients and the
server are responsible for the majority of FL’s overall carbon emissions
(97%).” The lack of principled hyperparameter tuning only exacerbates this
problem. Based on the results presented in Section 4, $\Delta$-SGD achieves
superior performance while robust to different settings.

In terms of limitations, our assumption on Theorem 1, especially Assumption
1c, as well as the conditions on $\gamma$ and $\eta_{0}$ are quite strong, and
does not truly capture the strength of $\Delta$-SGD. Moreover, due to non-
optimal implementation, $\Delta$-SGD takes about $1.3\times$ more wall-clock
time compared to SGD, which can be improved with more efficient
implementation.

## References

  * Agarwal et al. [2018] Agarwal, N., A. T. Suresh, F. X. X. Yu, S. Kumar, and B. McMahan (2018).  cpSGD: Communication-efficient and differentially-private distributed SGD.  Advances in Neural Information Processing Systems 31.
  * Armijo [1966] Armijo, L. (1966).  Minimization of functions having lipschitz continuous first partial derivatives.  Pacific Journal of mathematics 16(1), 1–3.
  * Assran et al. [2020] Assran, M., A. Aytekin, H. R. Feyzmahdavian, M. Johansson, and M. G. Rabbat (2020).  Advances in asynchronous parallel and distributed optimization.  Proceedings of the IEEE 108(11), 2013–2031.
  * Assran and Rabbat [2020] Assran, M. and M. Rabbat (2020).  On the convergence of nesterov’s accelerated gradient method in stochastic settings.  arXiv preprint arXiv:2002.12414.
  * Bernstein et al. [2023] Bernstein, J., C. Mingard, K. Huang, N. Azizan, and Y. Yue (2023).  Automatic gradient descent: Deep learning without hyperparameters.  arXiv preprint arXiv:2304.05187.
  * Bottou et al. [2018] Bottou, L., F. E. Curtis, and J. Nocedal (2018).  Optimization methods for large-scale machine learning.  SIAM review 60(2), 223–311.
  * Boyd et al. [2004] Boyd, S., S. P. Boyd, and L. Vandenberghe (2004).  Convex optimization.  Cambridge university press.
  * Cauchy et al. [1847] Cauchy, A. et al. (1847).  Méthode générale pour la résolution des systemes d’équations simultanées.  Comp. Rend. Sci. Paris 25(1847), 536–538.
  * Cevher and Vũ [2019] Cevher, V. and B. C. Vũ (2019).  On the linear convergence of the stochastic gradient method with constant step-size.  Optimization Letters 13(5), 1177–1187.
  * Defazio and Mishchenko [2023] Defazio, A. and K. Mishchenko (2023).  Learning-rate-free learning by d-adaptation.  arXiv preprint arXiv:2301.07733.
  * Defazio et al. [2022] Defazio, A., B. Zhou, and L. Xiao (2022).  Grad-gradagrad? a non-monotone adaptive stochastic gradient method.  arXiv preprint arXiv:2206.06900.
  * Drori and Teboulle [2014] Drori, Y. and M. Teboulle (2014).  Performance of first-order methods for smooth convex minimization: a novel approach.  Mathematical Programming 145(1-2), 451–482.
  * Duchi et al. [2011] Duchi, J., E. Hazan, and Y. Singer (2011).  Adaptive subgradient methods for online learning and stochastic optimization.  Journal of machine learning research 12(7).
  * Ghadimi and Lan [2013] Ghadimi, S. and G. Lan (2013).  Stochastic first-and zeroth-order methods for nonconvex stochastic programming.  SIAM Journal on Optimization 23(4), 2341–2368.
  * Gower et al. [2021] Gower, R. M., P. Richtárik, and F. Bach (2021).  Stochastic quasi-gradient methods: Variance reduction via jacobian sketching.  Mathematical Programming 188, 135–192.
  * Gower et al. [2020] Gower, R. M., M. Schmidt, F. Bach, and P. Richtárik (2020).  Variance-reduced methods for machine learning.  Proceedings of the IEEE 108(11), 1968–1983.
  * Hazan and Kakade [2019] Hazan, E. and S. Kakade (2019).  Revisiting the polyak step size.  arXiv preprint arXiv:1905.00313.
  * He et al. [2016] He, K., X. Zhang, S. Ren, and J. Sun (2016).  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778.
  * Hsu et al. [2019] Hsu, T.-M. H., H. Qi, and M. Brown (2019).  Measuring the effects of non-identical data distribution for federated visual classification.  arXiv preprint arXiv:1909.06335.
  * Johnson and Zhang [2013] Johnson, R. and T. Zhang (2013).  Accelerating stochastic gradient descent using predictive variance reduction.  Advances in neural information processing systems 26.
  * Karimireddy et al. [2020] Karimireddy, S. P., M. Jaggi, S. Kale, M. Mohri, S. J. Reddi, S. U. Stich, and A. T. Suresh (2020).  Mime: Mimicking centralized stochastic algorithms in federated learning.  arXiv preprint arXiv:2008.03606.
  * Khaled et al. [2020] Khaled, A., K. Mishchenko, and P. Richtárik (2020).  Tighter theory for local sgd on identical and heterogeneous data.  In International Conference on Artificial Intelligence and Statistics, pp. 4519–4529. PMLR.
  * Kim et al. [2022] Kim, J. L., P. Toulis, and A. Kyrillidis (2022).  Convergence and stability of the stochastic proximal point algorithm with momentum.  In Learning for Dynamics and Control Conference, pp. 1034–1047. PMLR.
  * Kingma and Ba [2014] Kingma, D. P. and J. Ba (2014).  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980.
  * Koloskova et al. [2020] Koloskova, A., N. Loizou, S. Boreiri, M. Jaggi, and S. Stich (2020).  A unified theory of decentralized sgd with changing topology and local updates.  In International Conference on Machine Learning, pp. 5381–5393. PMLR.
  * Krizhevsky et al. [2009] Krizhevsky, A., G. Hinton, et al. (2009).  Learning multiple layers of features from tiny images.
  * Lan et al. [2020] Lan, G., S. Lee, and Y. Zhou (2020).  Communication-efficient algorithms for decentralized and stochastic optimization.  Mathematical Programming 180(1-2), 237–284.
  * Latafat et al. [2023] Latafat, P., A. Themelis, L. Stella, and P. Patrinos (2023).  Adaptive proximal algorithms for convex optimization under local lipschitz continuity of the gradient.  arXiv preprint arXiv:2301.04431.
  * Levy et al. [2018] Levy, K. Y., A. Yurtsever, and V. Cevher (2018).  Online adaptive methods, universality and acceleration.  Advances in neural information processing systems 31.
  * Li et al. [2021] Li, Q., B. He, and D. Song (2021).  Model-contrastive federated learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10713–10722.
  * Li et al. [2020] Li, T., A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith (2020).  Federated optimization in heterogeneous networks.  Proceedings of Machine learning and systems 2, 429–450.
  * Liang et al. [2019] Liang, X., S. Shen, J. Liu, Z. Pan, E. Chen, and Y. Cheng (2019).  Variance reduced local sgd with lower communication complexity.  arXiv preprint arXiv:1912.12844.
  * Loizou et al. [2021] Loizou, N., S. Vaswani, I. H. Laradji, and S. Lacoste-Julien (2021).  Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence.  In International Conference on Artificial Intelligence and Statistics, pp. 1306–1314. PMLR.
  * Malitsky and Mishchenko [2020] Malitsky, Y. and K. Mishchenko (2020).  Adaptive gradient descent without descent.  In Proceedings of the 37th International Conference on Machine Learning, Volume 119 of Proceedings of Machine Learning Research, pp. 6702–6712. PMLR.
  * McMahan et al. [2017] McMahan, B., E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas (2017).  Communication-efficient learning of deep networks from decentralized data.  In Artificial intelligence and statistics, pp. 1273–1282. PMLR.
  * Moulines and Bach [2011] Moulines, E. and F. Bach (2011).  Non-asymptotic analysis of stochastic approximation algorithms for machine learning.  Advances in neural information processing systems 24.
  * Nesterov [2003] Nesterov, Y. (2003).  Introductory lectures on convex optimization: A basic course, Volume 87.  Springer Science & Business Media.
  * Nesterov [2015] Nesterov, Y. (2015).  Universal gradient methods for convex optimization problems.  Mathematical Programming 152(1-2), 381–404.
  * Nguyen et al. [2022] Nguyen, J., K. Malik, H. Zhan, A. Yousefpour, M. Rabbat, M. Malek, and D. Huba (2022).  Federated learning with buffered asynchronous aggregation.  In International Conference on Artificial Intelligence and Statistics, pp. 3581–3607. PMLR.
  * Orabona and Pál [2016] Orabona, F. and D. Pál (2016).  Coin betting and parameter-free online learning.  Advances in Neural Information Processing Systems 29.
  * Paquette and Scheinberg [2020] Paquette, C. and K. Scheinberg (2020).  A stochastic line search method with expected complexity analysis.  SIAM Journal on Optimization 30(1), 349–376.
  * Paszke et al. [2019] Paszke, A., S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala (2019).  Pytorch: An imperative style, high-performance deep learning library.  In Advances in Neural Information Processing Systems 32, pp. 8024–8035. Curran Associates, Inc.
  * Polyak [1963] Polyak, B. T. (1963).  Gradient methods for the minimisation of functionals.  USSR Computational Mathematics and Mathematical Physics 3(4), 864–878.
  * Polyak [1969] Polyak, B. T. (1969).  Minimization of nonsmooth functionals.  Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki 9(3), 509–521.
  * Praneeth Karimireddy et al. [2019] Praneeth Karimireddy, S., S. Kale, M. Mohri, S. J. Reddi, S. U. Stich, and A. Theertha Suresh (2019).  Scaffold: Stochastic controlled averaging for federated learning.  arXiv e-prints, arXiv–1910.
  * Qu and Li [2019] Qu, G. and N. Li (2019).  Accelerated distributed nesterov gradient descent.  IEEE Transactions on Automatic Control 65(6), 2566–2581.
  * Reddi et al. [2021] Reddi, S. J., Z. Charles, M. Zaheer, Z. Garrett, K. Rush, J. Konečný, S. Kumar, and H. B. McMahan (2021).  Adaptive federated optimization.  In International Conference on Learning Representations.
  * Scaman et al. [2017] Scaman, K., F. Bach, S. Bubeck, Y. T. Lee, and L. Massoulié (2017).  Optimal algorithms for smooth and strongly convex distributed optimization in networks.  In international conference on machine learning, pp. 3027–3036. PMLR.
  * Schmidt and Roux [2013] Schmidt, M. and N. L. Roux (2013).  Fast convergence of stochastic gradient descent under a strong growth condition.  arXiv preprint arXiv:1308.6370.
  * Stich [2018] Stich, S. U. (2018).  Local sgd converges fast and communicates little.  arXiv preprint arXiv:1805.09767.
  * Toghani et al. [2022] Toghani, M. T., S. Lee, and C. A. Uribe (2022).  PersA-FL: Personalized Asynchronous Federated Learning.  arXiv preprint arXiv:2210.01176.
  * Toulis and Airoldi [2017] Toulis, P. and E. M. Airoldi (2017).  Asymptotic and finite-sample properties of estimators based on stochastic gradients.
  * Uribe et al. [2020] Uribe, C. A., S. Lee, A. Gasnikov, and A. Nedić (2020).  A dual approach for optimal algorithms in distributed optimization over networks.  In 2020 Information Theory and Applications Workshop (ITA), pp. 1–37. IEEE.
  * Vaswani et al. [2019] Vaswani, S., F. Bach, and M. Schmidt (2019).  Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron.  In The 22nd international conference on artificial intelligence and statistics, pp. 1195–1204. PMLR.
  * Vaswani et al. [2019] Vaswani, S., A. Mishkin, I. Laradji, M. Schmidt, G. Gidel, and S. Lacoste-Julien (2019).  Painless stochastic gradient: Interpolation, line-search, and convergence rates.  Advances in neural information processing systems 32.
  * Wah et al. [2011] Wah, C., S. Branson, P. Welinder, P. Perona, and S. Belongie (2011).  The caltech-ucsd birds-200-2011 dataset.
  * Wang et al. [2021] Wang, J., Z. Xu, Z. Garrett, Z. Charles, L. Liu, and G. Joshi (2021).  Local adaptivity in federated learning: Convergence and consistency.  arXiv preprint arXiv:2106.02305.
  * Ward et al. [2020] Ward, R., X. Wu, and L. Bottou (2020).  Adagrad stepsizes: Sharp convergence over nonconvex landscapes.  The Journal of Machine Learning Research 21(1), 9047–9076.
  * Xie et al. [2019] Xie, C., O. Koyejo, I. Gupta, and H. Lin (2019).  Local adaalter: Communication-efficient stochastic gradient descent with adaptive learning rates.  arXiv preprint arXiv:1911.09030.
  * Xie et al. [2019] Xie, C., S. Koyejo, and I. Gupta (2019).  Asynchronous federated optimization.  arXiv preprint arXiv:1903.03934.
  * Yousefpour et al. [2023] Yousefpour, A., S. Guo, A. Shenoy, S. Ghosh, P. Stock, K. Maeng, S.-W. Krüger, M. Rabbat, C.-J. Wu, and I. Mironov (2023).  Green federated learning.  arXiv preprint arXiv:2303.14604.
  * Yuan et al. [2016] Yuan, K., Q. Ling, and W. Yin (2016).  On the convergence of decentralized gradient descent.  SIAM Journal on Optimization 26(3), 1835–1854.
  * Zaheer et al. [2018] Zaheer, M., S. Reddi, D. Sachan, S. Kale, and S. Kumar (2018).  Adaptive methods for nonconvex optimization.  Advances in neural information processing systems 31.

## Supplementary Materials for
“Adaptive Federated Learning with Auto-Tuned Clients”

In this appendix, we provide all missing proofs that were not present in the
main text, as well as additional plots and experiments. The appendix is
organized as follows.

  * •

In Appendix A, we provide all the missing proofs. In particular:

    * –

In Section A.1, we provide the proof of Algorithm 1, under Assumption 1.

    * –

In Section A.2, we provide the proof of Algorithm, 1, with some additional
assumptions, including that $f_{i}$ is convex for all $i\in[m]$.

    * –

In Section A.3, we provide a simple proof in the centralized nonconvex
setting, which was an open question posed in [34].

  * •

In Appendix B, we provide additional experiments, as well as miscellaneous
plots that were missing in the main text due to the space constraints.
Specifically:

    * –

In Section B.1, we provide some perspectives on the ease of tuning of
$\Delta$-SGD in Algorithm 1.

    * –

In Section B.2, we provide illustration of the different level of
heterogeneity induced by the Dirichlet concentration parameter $\alpha$.

    * –

In Section B.3, we provide some perspectives on how $\Delta$-SGD performs
using different number of local iterations.

    * –

In Section B.4, we provide additional experimental results where each client
has different number of samples as local dataset.

##  Appendix A Missing Proofs

We first introduce the following two inequalities which will be used in the
following proofs.

$\displaystyle\langle x_{i},x_{j}\rangle$
$\displaystyle\leqslant\frac{1}{2}\|x_{i}\|^{2}+\frac{1}{2}\|x_{j}\|^{2},\quad\text{and}$
(7) $\displaystyle\Big{\|}\sum_{i=1}^{m}x_{i}\Big{\|}^{2}$
$\displaystyle\leqslant m\sum_{i=1}^{m}\Big{\|}x_{i}\big{\|}^{2},$ (8)

for any set of $m$ vectors $\\{x_{i}\\}_{i{=}1}^{m}$ such that
$x_{i}\in\mathbb{R}^{d}$.

We also provide the following lemma, which establishes $\tilde{L}$-smoothness
based on local smoothness, without assuming the global $L$-smoothness.

######  Lemma 2.

For locally smooth function $f_{i}$, the following holds for the points that
Algorithm 1 visits:

$\displaystyle f_{i}(x_{t})\leqslant f_{i}(x_{t-1})+\langle\nabla
f_{i}(x_{t-1}),x_{t}-x_{t-1}\rangle+\frac{1}{4\eta_{t}^{i}}\|x_{t}-x_{t-1}\|^{2}.$
(9)

###### Proof.

By the definition of $\eta_{t}^{i},$ we have

$\displaystyle\|\nabla f_{i}(x_{t})-\nabla
f_{i}(x_{t-1})\|\leqslant\frac{1}{2\eta_{t}^{i}}\|x_{t}-x_{t-1}\|$

Thus, we have

$\displaystyle\langle\nabla f_{i}(x_{t})-\nabla
f_{i}(x_{t-1}),x_{t}-x_{t-1}\rangle$ $\displaystyle\leqslant\|\nabla
f_{i}(x_{t})-\nabla f_{i}(x_{t-1})\|\cdot\|x_{t}-x_{t-1}\|$
$\displaystyle\leqslant\frac{1}{2\eta_{t}^{i}}\|x_{t}-x_{t-1}\|^{2}.$

Let $g(k)=f_{i}(x_{t-1}+k(x_{t}-x_{t-1})).$ Then, we have

$\displaystyle g^{\prime}(k)$ $\displaystyle=\langle\nabla
f_{i}(x_{t-1}+k(x_{t}-x_{t-1})),x_{t}-x_{t-1}\rangle$ $\displaystyle
g^{\prime}(k)-g^{\prime}(0)$ $\displaystyle=\langle\nabla
f_{i}(x_{t-1}+k(x_{t}-x_{t-1})-\nabla
f_{i}(x_{t}),\frac{k}{k}(x_{t}-x{t-1})\rangle$
$\displaystyle\leqslant\frac{k}{2\eta_{t}^{i}}\|x_{t}-x_{t-1}\|^{2}.$

Using the Mean Value Theorem, we have

$\displaystyle f_{i}(x_{t})=g(1)$
$\displaystyle=g(0)+\int_{0}^{1}g^{\prime}(k)dk$ $\displaystyle\leqslant
g(0)+\int_{0}^{1}[g^{\prime}(0)+\frac{k}{2\eta_{t}^{i}}\|x_{t}-x_{t-1}]dk$
$\displaystyle\leqslant
g(0)+g^{\prime}(0)+\frac{1}{4\eta_{t}^{i}}\|x_{t}-x_{t-1}\|^{2}$
$\displaystyle\leqslant f_{i}(x_{t-1})+\langle\nabla
f_{i}(x_{t-1}),x_{t}-x_{t-1}\rangle+\frac{1}{4\eta_{t}^{i}}\|x_{t}-x_{t-1}\|^{2}.$

∎

We also establish the averaged version of local $\tilde{L}$-smoothness. First,
we re-write the statement of Lemma 2 as follows:

$\displaystyle\|\nabla f_{i}(x)-\nabla
f_{i}(y)\|^{2}\leqslant\tilde{L}_{i}\|x-y\|^{2},$ (10)

where $\tilde{L}_{i}$ is $\max_{t}\Big{(}\frac{1}{2\eta_{t}^{i}}\Big{)}$ for
all $x,y\in\text{conv}\\{x_{0},x_{1},\dots\\}$, and $\text{conv}\\{\cdots\\}$
denotes the convex hull of the arguments [7]. Now, given (10),

######  Lemma 3.

The average of $\tilde{L}$-local smooth functions $f_{i}$ are at least
$\tilde{L}$-local smooth, where
$\tilde{L}=\frac{1}{m}\sum_{i=1}^{m}\tilde{L}_{i}$.

###### Proof.

Starting from (10), we have:

$\displaystyle\Big{\|}\frac{1}{m}\sum_{i=1}^{m}\nabla
f_{i}(x)-\frac{1}{m}\sum_{i=1}^{m}\nabla f_{i}(y)\Big{\|}$
$\displaystyle=\Big{\|}\frac{1}{m}\sum_{i=1}^{m}\big{(}\nabla f_{i}(x)-\nabla
f_{i}(y)\big{)}\Big{\|}$
$\displaystyle\leqslant\frac{1}{m}\sum_{i=1}^{m}\big{\|}\nabla f_{i}(x)-\nabla
f_{i}(y)\big{\|}$
$\displaystyle\leqslant\frac{1}{m}\sum_{i=1}^{m}\tilde{L}_{i}\|x-y\|$
$\displaystyle=\tilde{L}\|x-y\|.$ (11)

∎

###  A.1 Proof of Algorithm 1 under Assumption 1

###### Proof.

Based on Algorithm 1, we use the following notations throughout the proof:

$\displaystyle x_{t,0}^{i}$ $\displaystyle=x_{t},$ $\displaystyle x_{t,k}^{i}$
$\displaystyle=x_{t,k-1}^{i}-\eta_{t,k}^{i}\tilde{\nabla}f_{i}(x_{t,k-1}^{i}),\quad\forall
k\in[K],$ $\displaystyle x_{t+1}$
$\displaystyle=\frac{1}{|\mathcal{S}_{t}|}\sum_{i\in\mathcal{S}_{t}}x_{t,k}^{i},$

where we denoted with $x_{t+1}$ as the server parameter at round $t+1$, which
is the average of the local parameters $x_{t,k}^{i}$ for all client
$\forall~{}i\in[m]$ after running $k$ local iterations for
$\forall~{}k\in[K]$.

We start from the smoothness of $f(\cdot)$, which we emphasize again that is
obtained via Lemma 3, i.e., as a byproduct of our analysis, and we do not
assume that $f_{i}$’s are globally $L$-smooth. Also note that Lemma 3 holds
for $\text{conv}\\{x_{0},x_{1},\dots\\}$, i.e., the average of the local
parameters visited by Algorithm 1.

Proceeding, we have

$\displaystyle f(x_{t+1})\leqslant f(x_{t})-\Big{\langle}\nabla
f(x_{t}),\frac{1}{|\mathcal{S}_{t}|}\sum_{i\in\mathcal{S}_{t}}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\tilde{\nabla}f_{i}(x_{t,k}^{i})\Big{\rangle}+\frac{\tilde{L}}{2}\Big{\|}\frac{1}{|\mathcal{S}_{t}|}\sum_{i\in\mathcal{S}_{t}}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\tilde{\nabla}f_{i}(x_{t,k}^{i})\Big{\|}^{2}.$

Taking expectation from the expression above, we get

$\displaystyle\mathbb{E}f(x_{t+1})$ $\displaystyle\leqslant
f(x_{t})-\mathbb{E}\Big{\langle}\nabla
f(x_{t}),\frac{1}{|\mathcal{S}_{t}|}\sum_{i\in\mathcal{S}_{t}}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\tilde{\nabla}f_{i}(x_{t,k}^{i})\Big{\rangle}+\frac{\tilde{L}}{2}\mathbb{E}\Big{\|}\frac{1}{|\mathcal{S}_{t}|}\sum_{i\in\mathcal{S}_{t}}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\tilde{\nabla}f_{i}(x_{t,k}^{i})\Big{\|}^{2}$
(12) $\displaystyle\leqslant f(x_{t})-\mathbb{E}\Big{\langle}\nabla
f(x_{t}),\frac{1}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\nabla
f_{i}(x_{t,k}^{i})\Big{\rangle}+\frac{\tilde{L}}{2m}\sum_{i=1}^{m}\,\mathbb{E}\Big{\|}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\tilde{\nabla}f_{i}(x_{t,k}^{i})\Big{\|}^{2}$
(13) $\displaystyle=f(x_{t})-D_{t}\,\|\nabla
f(x_{t})\|^{2}-D_{t}\,\mathbb{E}\Big{\langle}\nabla
f(x_{t}),\frac{1}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}\frac{\eta_{t,k}^{i}}{D_{t}}\Big{(}\nabla
f_{i}(x_{t,k}^{i})-\nabla f(x_{t})\Big{)}\Big{\rangle}$ $\displaystyle\hskip
113.81102pt+\frac{\tilde{L}}{2m}\sum_{i=1}^{m}\,\mathbb{E}\Big{\|}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\tilde{\nabla}f_{i}(x_{t,k}^{i})\Big{\|}^{2},$
(14)

where in the equality, we added and subtracted
$\frac{1}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\nabla f(x_{t})$ in
the inner product term, and also replaced
$D_{t}=\frac{1}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}\eta_{t,k}^{i}$. Then, using
(7) and (12)-(14), we have

$\displaystyle\mathbb{E}f(x_{t+1})$ $\displaystyle\leqslant
f(x_{t})-D_{t}\,\|\nabla f(x_{t})\|^{2}+\frac{D_{t}}{2}\,\|\nabla
f(x_{t})\|^{2}$ (15)
$\displaystyle\quad+\frac{D_{t}}{2}\,\mathbb{E}\Big{\|}\frac{1}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}\frac{\eta_{t,k}^{i}}{D_{t}}\Big{(}\nabla
f_{i}(x_{t,k}^{i})-\nabla
f(x_{t})\Big{)}\Big{\|}^{2}+\frac{\tilde{L}}{2m}\sum_{i=1}^{m}\,\mathbb{E}\Big{\|}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\tilde{\nabla}f_{i}(x_{t,k}^{i})\Big{\|}^{2}$
$\displaystyle=f(x_{t})-\frac{D_{t}}{2}\,\|\nabla
f(x_{t})\|^{2}+\frac{1}{2D_{t}}\,\mathbb{E}\Big{\|}\frac{1}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\Big{(}\nabla
f_{i}(x_{t,k}^{i})-\nabla f(x_{t})\Big{)}\Big{\|}^{2}$
$\displaystyle\quad+\frac{\tilde{L}}{2m}\sum_{i=1}^{m}\,\mathbb{E}\Big{\|}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\tilde{\nabla}f_{i}(x_{t,k}^{i})\Big{\|}^{2}$
(16) $\displaystyle=f(x_{t})-\frac{D_{t}}{2}\,\|\nabla f(x_{t})\|^{2}$
$\displaystyle\quad+\frac{1}{2D_{t}}\,\mathbb{E}\Big{\|}\frac{1}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\Big{(}\nabla
f_{i}(x_{t})-\nabla f_{i}(x_{t,k}^{i})+\nabla f_{i}(x_{t})-\nabla
f(x_{t})\Big{)}\Big{\|}^{2}$
$\displaystyle\quad+\frac{\tilde{L}}{2m}\sum_{i=1}^{m}\,\mathbb{E}\Big{\|}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\Big{(}\tilde{\nabla}f_{i}(x_{t,k}^{i})-\nabla
f_{i}(x_{t,k}^{i})+\nabla f_{i}(x_{t,k}^{i})-\nabla f_{i}(x_{t})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\nabla f_{i}(x_{t})-\nabla
f(x_{t})+\nabla f(x_{t})\Big{)}\Big{\|}^{2}$ (17)

We now expand the terms in (17), and will bound each seprately, as follows.

$\displaystyle\mathbb{E}f(x_{t+1})$ $\displaystyle\leqslant
f(x_{t})-\frac{D_{t}}{2}\,\|\nabla f(x_{t})\|^{2}$
$\displaystyle\quad+\underbrace{\frac{1}{D_{t}}\,\mathbb{E}\Big{\|}\frac{1}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\Big{(}\nabla
f_{i}(x_{t})-\nabla f_{i}(x_{t,k}^{i})\Big{)}\Big{\|}^{2}}_{\mathrm{A}_{1}}$
$\displaystyle\quad+\underbrace{\frac{1}{D_{t}}\,\mathbb{E}\Big{\|}\frac{1}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\Big{(}\nabla
f_{i}(x_{t})-\nabla f(x_{t})\Big{)}\Big{\|}^{2}}_{\mathrm{A}_{2}}$
$\displaystyle\quad+\underbrace{\frac{2\tilde{L}}{m}\sum_{i=1}^{m}\,\mathbb{E}\Bigg{\|}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\Big{(}\tilde{\nabla}f_{i}(x_{t,k}^{i})-\nabla
f_{i}(x_{t,k}^{i})\Big{)}\Bigg{\|}^{2}}_{\mathrm{A}_{3}}$
$\displaystyle\quad+\underbrace{\frac{2\tilde{L}}{m}\sum_{i=1}^{m}\,\mathbb{E}\Bigg{\|}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\Big{(}\nabla
f_{i}(x_{t,k}^{i})-\nabla f_{i}(x_{t})\Big{)}\Bigg{\|}^{2}}_{\mathrm{A}_{4}}$
$\displaystyle\quad+\underbrace{\frac{2\tilde{L}}{m}\sum_{i=1}^{m}\,\mathbb{E}\Bigg{\|}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\Big{(}\nabla
f_{i}(x_{t})-\nabla f(x_{t})\Big{)}\Bigg{\|}^{2}}_{\mathrm{A}_{5}}$
$\displaystyle\quad+\underbrace{\frac{2\tilde{L}}{m}\sum_{i=1}^{m}\,\mathbb{E}\Bigg{\|}\sum_{k=0}^{K-1}\eta_{t,k}^{i}\nabla
f(x_{t})\Bigg{\|}^{2}}_{\mathrm{A}_{6}}.$ (18)

Now, we provide an upper bound for each term in (18). Starting with
$\mathrm{A}_{1},$ using (7), (8), and (11), we have

$\displaystyle\mathrm{A}_{1}$
$\displaystyle\leqslant\frac{K}{D_{t}m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\,\mathbb{E}\Big{\|}\nabla
f_{i}(x_{t})-\nabla f_{i}(x_{t,k}^{i})\Big{\|}^{2}$ (19)
$\displaystyle\leqslant\frac{K\tilde{L}^{2}}{D_{t}m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\,\mathbb{E}\Big{\|}x_{t}-x_{t,k}^{i}\Big{\|}^{2}$
$\displaystyle=\frac{K\tilde{L}^{2}}{D_{t}m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\,\mathbb{E}\Big{\|}\sum_{\ell=0}^{k-1}\eta_{t,l}^{i}\tilde{\nabla}f_{i}(x_{t,\ell}^{i})\Big{\|}^{2}$
$\displaystyle=\frac{K\tilde{L}^{2}}{D_{t}m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\,\mathbb{E}\Big{\|}\sum_{\ell=0}^{k-1}\eta_{t,l}^{i}\Big{(}\tilde{\nabla}f_{i}(x_{t,\ell}^{i})-\nabla
f_{i}(x_{t,\ell}^{i})+\nabla f_{i}(x_{t,\ell}^{i})\Big{)}\Big{\|}^{2}$
$\displaystyle\leqslant\frac{2K\tilde{L}^{2}}{D_{t}m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\Big{[}\mathbb{E}\Big{\|}\sum_{\ell=0}^{k-1}\eta_{t,l}^{i}\Big{(}\tilde{\nabla}f_{i}(x_{t,\ell}^{i})-\nabla
f_{i}(x_{t,\ell}^{i})\Big{)}\Big{\|}^{2}+\,\mathbb{E}\Big{\|}\sum_{\ell=0}^{k-1}\eta_{t,l}^{i}\nabla
f_{i}(x_{t,\ell}^{i})\Big{\|}^{2}\Big{]}$
$\displaystyle\leqslant\frac{2K\tilde{L}^{2}}{D_{t}m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}k(\eta_{t,k}^{i})^{2}\sum_{\ell=0}^{k-1}(\eta_{t,k}^{i})^{2}\Big{[}\mathbb{E}\Big{\|}\tilde{\nabla}f_{i}(x_{t,\ell}^{i})-\nabla
f_{i}(x_{t,\ell}^{i})\Big{\|}^{2}+\mathbb{E}\Big{\|}\nabla
f_{i}(x_{t,\ell}^{i})\Big{\|}^{2}\Big{]}$
$\displaystyle\leqslant\frac{2K\tilde{L}^{2}}{D_{t}m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}k(\eta_{t,k}^{i})^{2}\sum_{\ell=0}^{k-1}(\eta_{t,k}^{i})^{2}\Big{(}\frac{\sigma^{2}}{b}+G^{2}\Big{)}$
$\displaystyle\leqslant\frac{2K^{2}\tilde{L}^{2}\Big{(}\frac{\sigma^{2}}{b}+G^{2}\Big{)}}{D_{t}m}\sum_{i=1}^{m}\Big{(}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\Big{)}^{2}.$
(20)

For $\mathrm{A}_{2},$ using (7) and (8), we have:

$\displaystyle\mathrm{A}_{2}$
$\displaystyle\leqslant\frac{K}{D_{t}m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\,\mathbb{E}\Big{\|}\nabla
f_{i}(x_{t})-\nabla f(x_{t})\Big{\|}^{2}$
$\displaystyle\leqslant\frac{K\rho}{D_{t}m}\Big{\|}\nabla
f(x_{t})\Big{\|}^{2}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}.$ (21)

For $\mathrm{A}_{3}$, using (7), (8), and (11), we have:

$\displaystyle\mathrm{A}_{3}$
$\displaystyle\leqslant\frac{2K\tilde{L}}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\,\mathbb{E}\Big{\|}\tilde{\nabla}f_{i}(x_{t,k}^{i})-\nabla
f_{i}(x_{t,k}^{i})\Big{\|}^{2}$
$\displaystyle\leqslant\frac{2K\tilde{L}\sigma^{2}}{mb}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}.$
(22)

For $\mathrm{A}_{4},$ using (7), (8), and (11), we have:

$\displaystyle\mathrm{A}_{4}$
$\displaystyle\leqslant\frac{2K\tilde{L}}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\,\mathbb{E}\Big{\|}\nabla
f_{i}(x_{t})-\nabla f_{i}(x_{t,k}^{i})\Big{\|}^{2}$ (23)
$\displaystyle\leqslant\frac{2K\tilde{L}^{3}}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\,\mathbb{E}\Big{\|}x_{t}-x_{t,k}^{i}\Big{\|}^{2}$
$\displaystyle=\frac{2K\tilde{L}^{3}}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\,\mathbb{E}\Big{\|}\sum_{\ell=0}^{k-1}\eta_{t,l}^{i}\tilde{\nabla}f_{i}(x_{t,\ell}^{i})\Big{\|}^{2}$
$\displaystyle=\frac{2K\tilde{L}^{3}}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\,\mathbb{E}\Big{\|}\sum_{\ell=0}^{k-1}\eta_{t,l}^{i}\Big{(}\tilde{\nabla}f_{i}(x_{t,\ell}^{i})-\nabla
f_{i}(x_{t,\ell}^{i})+\nabla f_{i}(x_{t,\ell}^{i})\Big{)}\Big{\|}^{2}$
$\displaystyle\leqslant\frac{4K\tilde{L}^{3}}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\Big{[}\mathbb{E}\Big{\|}\sum_{\ell=0}^{k-1}\eta_{t,l}^{i}\Big{(}\tilde{\nabla}f_{i}(x_{t,\ell}^{i})-\nabla
f_{i}(x_{t,\ell}^{i})\Big{)}\Big{\|}^{2}+\,\mathbb{E}\Big{\|}\sum_{\ell=0}^{k-1}\eta_{t,l}^{i}\nabla
f_{i}(x_{t,\ell}^{i})\Big{\|}^{2}\Big{]}$
$\displaystyle\leqslant\frac{4K\tilde{L}^{3}}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}k(\eta_{t,k}^{i})^{2}\sum_{\ell=0}^{k-1}(\eta_{t,k}^{i})^{2}\Big{[}\mathbb{E}\Big{\|}\tilde{\nabla}f_{i}(x_{t,\ell}^{i})-\nabla
f_{i}(x_{t,\ell}^{i})\Big{\|}^{2}+\mathbb{E}\Big{\|}\nabla
f_{i}(x_{t,\ell}^{i})\Big{\|}^{2}\Big{]}$
$\displaystyle\leqslant\frac{4K\tilde{L}^{3}}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}k(\eta_{t,k}^{i})^{2}\sum_{\ell=0}^{k-1}(\eta_{t,k}^{i})^{2}\Big{(}\frac{\sigma^{2}}{b}+G^{2}\Big{)}$
$\displaystyle\leqslant\frac{4K^{2}\tilde{L}^{3}\Big{(}\frac{\sigma^{2}}{b}+G^{2}\Big{)}}{m}\sum_{i=1}^{m}\Big{(}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\Big{)}^{2}.$
(24)

For $\mathrm{A}_{5},$ using (7), (8), and (11), we have:

$\displaystyle\mathrm{A}_{5}$
$\displaystyle\leqslant\frac{2K\tilde{L}}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\,\mathbb{E}\Big{\|}\nabla
f_{i}(x_{t})-\nabla f(x_{t})\Big{\|}^{2}$
$\displaystyle\leqslant\frac{2K\tilde{L}\rho}{m}\Big{\|}\nabla
f(x_{t})\Big{\|}^{2}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}.$ (25)

For $\mathrm{A}_{6},$ using (7), (8), and (11), we have:

$\displaystyle\mathrm{A}_{6}$
$\displaystyle\leqslant\frac{2K\tilde{L}}{m}\Big{\|}\nabla
f(x_{t})\Big{\|}^{2}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}.$ (26)

#### Putting all bounds together.

Now, by putting (19)–(26) back into (18) and rearranging the terms, we obtain
the following inequality:

$\displaystyle\Big{(}\frac{D_{t}}{2}-\frac{K\rho}{D_{t}m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}-\frac{2K\tilde{L}(1+\rho)}{m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\Big{)}\|\nabla
f(x_{t})\|^{2}$ $\displaystyle\qquad\qquad\leqslant
f(x_{t})-f(x_{t+1})+\frac{2K^{2}\tilde{L}^{2}\Big{(}\frac{\sigma^{2}}{b}+G^{2}\Big{)}}{D_{t}m}\sum_{i=1}^{m}\Big{(}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\Big{)}^{2}$
$\displaystyle\qquad\qquad\qquad+\frac{2K\tilde{L}\sigma^{2}}{mb}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}+\frac{4K^{2}\tilde{L}^{3}\Big{(}\frac{\sigma^{2}}{b}+G^{2}\Big{)}}{m}\sum_{i=1}^{m}\Big{(}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\Big{)}^{2}.$
(27)

Now, it remains to notice that, by definition,
$\eta_{t,k}^{i}=\mathcal{O}(\gamma)$, for all $i\in[m]$, $k\in\\{0,1,\dots
K{-}1\\}$, and $t\geqslant 0$. Therefore, $D_{t}=\mathcal{O}(\gamma K)$. Thus,
by dividing the above inequality by $\frac{D_{t}}{2}$, we have:

$\displaystyle\Big{(}1-\underbrace{\frac{2K\rho}{D_{t}^{2}m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}}_{\mathcal{O}(1)}~{}-~{}\underbrace{\frac{4K\tilde{L}(1+\rho)}{D_{t}m}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}}_{\mathcal{O}(\gamma
K)}\Big{)}\|\nabla f(x_{t})\|^{2}$
$\displaystyle\qquad\qquad\leqslant\underbrace{\frac{2(f(x_{t})-f(x_{t+1}))}{D_{t}}}_{\mathcal{O}\Big{(}\frac{1}{\gamma
K}\Big{)}}~{}+~{}\underbrace{\frac{4K\tilde{L}\sigma^{2}}{D_{t}mb}\sum_{i=1}^{m}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}}_{\mathcal{O}(\gamma
K)}$
$\displaystyle\qquad\qquad\qquad+\underbrace{\frac{4K^{2}\tilde{L}^{2}\Big{(}\frac{\sigma^{2}}{b}+G^{2}\Big{)}}{D_{t}^{2}m}\sum_{i=1}^{m}\Big{(}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\Big{)}^{2}}_{\mathcal{O}(\gamma^{2}K^{2})}$
$\displaystyle\qquad\qquad\qquad+\underbrace{\frac{8K^{2}\tilde{L}^{3}\Big{(}\frac{\sigma^{2}}{b}+G^{2}\Big{)}}{D_{t}m}\sum_{i=1}^{m}\Big{(}\sum_{k=0}^{K-1}(\eta_{t,k}^{i})^{2}\Big{)}^{2}}_{\mathcal{O}(\gamma^{3}K^{3})},$
(28)

for $\rho=\mathcal{O}(1)$. For the simplicity of exposition, assuming
$\rho\leqslant\frac{1}{4}$ and $T\geqslant(5/\rho)^{2}=400$, we obtain the
below by averaging (28) for $t=0,1,\dots,T{-}1$:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T{-}1}\|\nabla f(x_{t})\|^{2}$
$\displaystyle\leqslant\mathcal{O}\Big{(}\frac{f(x_{0})-f^{\star}}{\gamma
KT}\Big{)}+\mathcal{O}\Big{(}\frac{\gamma
K\sigma^{2}}{b}\Big{)}+\mathcal{O}\Big{(}\tilde{L}^{2}\Big{(}\frac{\sigma^{2}}{b}+G^{2}\Big{)}\gamma^{2}K^{2}\Big{)}$
$\displaystyle\quad+\mathcal{O}\Big{(}\tilde{L}^{3}\Big{(}\frac{\sigma^{2}}{b}+G^{2}\Big{)}\gamma^{3}K^{3}\Big{)}.$
(29)

Finally, by choosing $\gamma=\mathcal{O}\Big{(}\frac{1}{K\sqrt{T}}\Big{)}$,
and defining
$\Psi_{1}=\max\left\\{\frac{\sigma^{2}}{b},f(x_{0})-f(x^{\star})\right\\}$ and
$\Psi_{2}=\left(\frac{\sigma^{2}}{b}+G^{2}\right)$ with $b=|\mathcal{B}|$
being the batch size, we arrive at the statement in Theorem 1, i.e.,

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\,\mathbb{E}\Big{\|}\nabla
f\Big{(}x_{t}\Big{)}\Big{\|}^{2}$
$\displaystyle\leqslant\mathcal{O}\Big{(}\frac{\Psi_{1}}{\sqrt{T}}\Big{)}+\mathcal{O}\Big{(}\frac{\tilde{L}^{2}\Psi_{2}}{T}\Big{)}+\mathcal{O}\Big{(}\frac{\tilde{L}^{3}\Psi_{2}}{\sqrt{T^{3}}}\Big{)}.$

∎

###  A.2 Proof of Algorithm 1 for convex case

Here, we provide an extension of the proof of [34, Theorem 1] for distributed
version. Note that the proof we provide here is not exactly the same version
of $\Delta$-SGD presented in Algorithm 1; in particular, we assume no local
iterations, i.e., $k=1$ for all $i\in[m]$, and every client participate, i.e,
$p=1.$

We start with the extension of [34, Lemma 1], which constructs a Lyapunov
function for the distributed objective in (1).

######  Lemma 4.

Let $f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be convex and twice
differentiable. Then, the sequence $\\{x_{t}\\}$ generated by Algorithm 1,
assuming $k=1$ and $p=1$, satisfy the following:

$\displaystyle\|x_{t+1}-x^{\star}\|^{2}+\frac{1}{2m}\sum_{i=1}^{m}\|x_{t+1}^{i}-x_{t}^{i}\|^{2}+\frac{2}{m}\sum_{i=1}^{m}\Big{[}\eta_{t}^{i}(1+\theta_{t}^{i})\big{(}f_{i}(x_{t}^{i})-f_{i}(x^{\star})\big{)}\Big{]}$
$\displaystyle\qquad\leqslant\|x_{t}-x^{\star}\|^{2}+\frac{1}{2m}\sum_{i=1}^{m}\|x_{t}^{i}-x_{t-1}^{i}\|^{2}+\frac{2}{m}\sum_{i=1}^{m}\Big{[}\eta_{t}^{i}\theta_{t}^{i}\big{(}f_{i}(x_{t-1}^{i})-f_{i}(x^{\star})\big{)}\Big{]}.$
(30)

The above lemma, which we prove below, constructs a contracting Lyapunov
function, which can be seen from the second condition on the step size
$\eta_{t}^{i}:$

$\displaystyle\eta_{t+1}^{i}\leqslant\sqrt{1+\theta_{t}^{i}}\eta_{t}^{i}\implies\eta_{t+1}^{i}\theta_{t+1}^{i}\leqslant(1+\theta_{t}^{i})\eta_{t}^{i}.$

###### Proof.

We denote $x_{t}=\frac{1}{m}\sum_{i=1}^{m}x_{t}^{i}.$

$\displaystyle\|x_{t+1}-x^{\star}\|^{2}$
$\displaystyle=\|x_{t}-\frac{1}{m}\sum_{i=1}^{m}\eta_{t}^{i}\nabla
f_{i}(x_{t}^{i})-x^{\star}\|$ (31)
$\displaystyle=\|x_{t}-x^{\star}\|^{2}+\Big{\|}\frac{1}{m}\sum_{i=1}^{m}\eta_{t}^{i}\nabla
f_{i}(x_{t}^{i})\Big{\|}^{2}-2\Big{\langle}x_{t}-x^{\star},\frac{1}{m}\sum_{i=1}^{m}\eta_{t}^{i}\nabla
f_{i}(x_{t}^{i})\Big{\rangle}$ (32)

We will first bound the second term in (32). Using
$\|\sum_{i=1}^{m}a_{i}\|^{2}\leqslant m\cdot\sum_{i=1}^{m}\|a_{i}\|^{2},$ we
have

$\displaystyle\Big{\|}\frac{1}{m}\sum_{i=1}^{m}\eta_{t}^{i}\nabla
f_{i}(x_{t}^{i})\Big{\|}^{2}$
$\displaystyle=\Big{\|}\frac{1}{m}\sum_{i=1}^{m}(x_{t}^{i}-x_{t+1}^{i})\Big{\|}^{2}\leqslant\frac{1}{m}\sum_{i=1}^{m}\|x_{t}^{i}-x_{t+1}^{i}\|^{2}.$
(33)

To bound $\|x_{t}^{i}-x_{t+1}^{i}\|^{2},$ observe that

$\displaystyle\|x_{t}^{i}-x_{t+1}^{i}\|^{2}$
$\displaystyle=2\|x_{t}^{i}-x_{t+1}^{i}\|^{2}-\|x_{t}^{i}-x_{t+1}^{i}\|^{2}$
$\displaystyle=2\langle-\eta_{t}^{i}\nabla
f_{i}(x_{t}^{i}),x_{t}^{i}-x_{t+1}^{i}\rangle-\|x_{t}^{i}-x_{t+1}^{i}\|^{2}$
$\displaystyle=2\eta_{t}^{i}\langle\nabla f_{i}(x_{t}^{i})-\nabla
f_{i}(x_{t-1}^{i}),x_{t+1}^{i}-x_{t}^{i}\rangle-\|x_{t}^{i}-x_{t+1}^{i}\|^{2}$
$\displaystyle\quad+2\eta_{t}^{i}\langle\nabla
f_{i}(x_{t-1}^{i}),x_{t+1}^{i}-x_{t}^{i}\rangle$ (34)

For the first term in (34), using Cauchy-Schwarz and Young’s inequalities as
well as
$\eta_{t}^{i}\leqslant\frac{\|x_{t}^{i}-x_{t-1}^{i}\|}{2\|\nabla
f_{i}(x_{t}^{i})-\nabla f_{i}(x_{t-1}^{i})\|}$, we have:

$\displaystyle 2\eta_{t}^{i}\langle\nabla f_{i}(x_{t}^{i})-\nabla
f_{i}(x_{t-1}^{i}),x_{t+1}^{i}-x_{t}^{i}\rangle$ $\displaystyle\leqslant
2\eta_{t}^{i}\|\nabla f_{i}(x_{t}^{i})-\nabla
f_{i}(x_{t-1}^{i})\|\cdot\|x_{t+1}^{i}-x_{t}^{i}\|$
$\displaystyle\leqslant\|x_{t}^{i}-x_{t-1}^{i}\|\cdot\|x_{t+1}^{i}-x_{t}^{i}\|$
$\displaystyle\leqslant\frac{1}{2}\|x_{t}^{i}-x_{t-1}^{i}\|^{2}+\frac{1}{2}\|x_{t+1}^{i}-x_{t}^{i}\|^{2}.$

For the third term in (34), by convexity of $f_{i}(x),$ we have

$\displaystyle 2\eta_{t}^{i}\langle\nabla
f_{i}(x_{t-1}^{i}),x_{t+1}^{i}-x_{t}^{i}\rangle$
$\displaystyle=2\tfrac{\eta_{t}^{i}}{\eta_{t-1}^{i}}\langle
x_{t-1}^{i}-x_{t}^{i},x_{t+1}^{i}-x_{t}^{i}\rangle$
$\displaystyle=2\theta_{t}^{i}\eta_{t}^{i}\langle x_{t-1}^{i}-x_{t}^{i},\nabla
f_{i}(x_{t}^{i})\rangle$ $\displaystyle\leqslant
2\theta_{t}^{i}\eta_{t}^{i}[f_{i}(x_{t-1}^{i})-f_{i}(x_{t}^{i})].$

Together, we have

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}\|x_{t}^{i}-x_{t+1}^{i}\|^{2}\leqslant\frac{1}{m}\sum_{i=1}^{m}\Big{\\{}\tfrac{1}{2}\|x_{t}^{i}-x_{t-1}^{i}\|^{2}-\tfrac{1}{2}\|x_{t+1}^{i}-x_{t}^{i}\|^{2}+2\theta_{t}^{i}\eta_{t}^{i}[f_{i}(x_{t-1}^{i})-f_{i}(x_{t}^{i})]\Big{\\}}.$
(35)

Now to bound the last term in (32), we have

$\displaystyle-2\Big{\langle}x_{t}-x^{\star},\frac{1}{m}\sum_{i=1}^{m}\eta_{t}^{i}\nabla
f_{i}(x_{t}^{i})\Big{\rangle}$
$\displaystyle=\frac{2}{m}\eta_{t}^{i}\sum_{i=1}^{m}\Big{\langle}x^{\star}-x_{t}^{i},\nabla
f_{i}(x_{t}^{i})\Big{\rangle}$
$\displaystyle\leqslant\frac{2}{m}\sum_{i=1}^{m}\eta_{t}^{i}\big{(}f_{i}(x^{\star})-f_{i}(x_{t}^{i})\big{)},$
(36)

where in the equality we used the fact that $x_{t}^{i}=x_{t},$ for $k=1.$

Putting (35) and (36) back to (32), we have

$\displaystyle\|x_{t+1}-x^{\star}\|^{2}$
$\displaystyle=\|x_{t}-x^{\star}\|^{2}+\Big{\|}\frac{1}{m}\sum_{i=1}^{m}\eta_{t}^{i}\nabla
f_{i}(x_{t}^{i})\Big{\|}^{2}-2\Big{\langle}x_{t}-x^{\star},\frac{1}{m}\sum_{i=1}^{m}\eta_{t}^{i}\nabla
f_{i}(x_{t}^{i})\Big{\rangle}$
$\displaystyle\leqslant\|x_{t}-x^{\star}\|^{2}+\frac{1}{m}\sum_{i=1}^{m}\Big{\\{}\tfrac{1}{2}\|x_{t}^{i}-x_{t-1}^{i}\|^{2}-\tfrac{1}{2}\|x_{t+1}^{i}-x_{t}^{i}\|^{2}+2\theta_{t}^{i}\eta_{t}^{i}[f_{i}(x_{t-1}^{i})-f(x_{t}^{i})]\Big{\\}}$
$\displaystyle\quad\quad-2\Big{\langle}x_{t}-x_{t}^{i},\frac{1}{m}\sum_{i=1}^{m}\eta_{t}^{i}\nabla
f_{i}(x_{t}^{i})\Big{\rangle}+2\frac{1}{m}\sum_{i=1}^{m}\eta_{t}^{i}\big{(}f_{i}(x^{\star})-f_{i}(x_{t}^{i})\big{)}.$
(37)

Averaging (37) for $i=1,\dots,m,$ notice that the first term in (37)
disappears, as $\hat{x_{t}}=\frac{1}{m}\sum_{i=1}^{m}x_{i}.$

$\displaystyle\|x_{t+1}-x^{\star}\|^{2}+\frac{1}{m}\sum_{i=1}^{m}\Big{[}2\eta_{t}^{i}(1+\theta_{t}^{i})\big{(}f_{i}(x_{t}^{i})-f_{i}(x^{\star})\big{)}+\frac{1}{2}\|x_{t+1}^{i}-x_{t}^{i}\|^{2}\Big{]}$
$\displaystyle\hskip
56.9055pt\leqslant\|x_{t}-x^{\star}\|^{2}+\frac{1}{m}\sum_{i=1}^{m}\Big{[}2\eta_{t}^{i}\theta_{t}^{i}\big{(}f_{i}(x_{t-1}^{i})-f_{i}(x^{\star})\big{)}+\frac{1}{2}\|x_{t}^{i}-x_{t-1}^{i}\|^{2}\Big{]}.$

∎

######  Theorem 5.

Let $f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be convex and twice
differentiable. Then, the sequence $\\{x_{t}\\}$ generated by Algorithm 1,
assuming $k=1$ and $p=1$, satisfy the following:

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}\big{(}f_{i}(\tilde{x}_{t}^{i})-f_{i}(x^{\star})\big{)}\leqslant\frac{2DL^{2}}{2Lt+1},$
(38)

where

$\displaystyle\tilde{x}_{t}^{i}$
$\displaystyle=\frac{\eta_{t}^{i}(1+\theta_{t}^{i})x_{t}^{i}+\sum_{k=1}^{t-1}\alpha_{k}^{i}x_{k}^{i}}{S_{t}^{i}},$
$\displaystyle\alpha_{k}^{i}$
$\displaystyle=\eta_{k}^{i}(1+\theta_{k}^{i})-\eta_{k+1}^{i}\theta_{k+1}^{i}$
$\displaystyle S_{t}^{i}$
$\displaystyle=\eta_{t}^{i}(1+\theta_{t}^{i})+\sum_{k=1}^{t-1}\alpha_{k}^{i}=\sum_{k=1}^{t}\eta_{k}^{i}+\eta_{1}^{i}\theta_{1}^{i}.$

Further, if $x^{\star}$ is any minimum of $f_{i}(x)$ for all $i\in[m]$, (38)
implies convergence for problem (1).

###### Proof.

We start by telescoping (30). Then, we arrive at

$\displaystyle\|x_{t+1}-x^{\star}\|^{2}$
$\displaystyle+\frac{1}{2m}\sum_{i=1}^{m}\|x_{t+1}^{i}-x_{t}^{i}\|^{2}+\frac{2}{m}\sum_{i=1}^{m}\Big{[}\eta_{t}^{i}(1+\theta_{t}^{i})\big{(}f_{i}(x_{t}^{i})-f_{i}(x^{\star})\big{)}$
$\displaystyle\hskip
99.58464pt+\sum_{k=1}^{t-1}\big{(}\eta_{k}^{i}(1+\theta_{k}^{i})-\eta_{k+1}^{i}\theta_{k+1}^{i}\big{)}\big{(}f_{i}(x_{k}^{i})-f_{i}(x^{\star})\big{)}\Big{]}$
(39)
$\displaystyle\leqslant\|x_{1}-x^{\star}\|^{2}+\frac{1}{2m}\sum_{i=1}^{m}\|x_{1}^{i}-x_{0}^{i}\|^{2}+\frac{2}{m}\sum_{i=1}^{m}\eta_{1}^{i}\theta_{1}^{i}\big{(}f_{i}(x_{0}^{i})-f_{i}(x^{\star})\big{)}:=D.$
(40)

Observe that (39) is of the form
$\alpha_{t}^{i}[f_{i}(x_{t}^{i})-f_{i}(x^{\star})]+\sum_{k=1}^{t-1}\alpha_{k}^{i}[f_{i}(x_{k}^{i})-f_{i}(x^{\star})]=\sum_{k=1}^{t}\alpha_{k}^{i}[f_{i}(x_{k}^{i})-f_{i}(x^{\star})]$.
The sum of the coefficients equals:

$\displaystyle\sum_{k=1}^{t}\alpha_{k}^{i}=\eta_{t}^{i}(1+\theta_{t}^{i})+\sum_{k=1}^{t-1}[\eta_{k}^{i}(1+\theta_{k}^{i})-\eta_{k+1}^{i}\theta_{k+1}^{i}]=\eta_{1}^{i}\theta_{1}^{i}+\sum_{k=1}^{t}\eta_{k}^{i}:=S_{t}^{i}.$
(41)

Therefore, by Jensen’s inequality, we have

$\displaystyle
D\geqslant\|x_{1}-x^{\star}\|^{2}+\frac{1}{2m}\sum_{i=1}^{m}\|x_{1}^{i}-x_{0}^{i}\|^{2}+2S_{t}^{i}\big{(}f_{i}(\tilde{x}_{t}^{i})-f_{i}(x^{\star})\big{)}\geqslant
2S_{t}^{i}\big{(}f_{i}(\tilde{x}_{t}^{i})-f_{i}(x^{\star})\big{)},$ (42)

which implies
$f_{i}(\tilde{x}_{t}^{i})-f_{i}(x^{\star})\leqslant\frac{D^{i}}{2S_{t}^{i}}$,
where

$\displaystyle\tilde{x}_{t}^{i}$
$\displaystyle=\frac{\eta_{t}^{i}(1+\theta_{t}^{i})x_{t}^{i}+\sum_{k=1}^{t-1}\alpha_{k}^{i}x_{k}^{i}}{S_{t}^{i}},$
$\displaystyle\alpha_{k}^{i}$
$\displaystyle=\eta_{k}^{i}(1+\theta_{k}^{i})-\eta_{k+1}^{i}\theta_{k+1}^{i}$
$\displaystyle S_{t}^{i}$
$\displaystyle=\eta_{t}^{i}(1+\theta_{t}^{i})+\sum_{k=1}^{t-1}\alpha_{k}^{i}=\sum_{k=1}^{t}\eta_{k}^{i}+\eta_{1}^{i}\theta_{1}^{i}.$
(43)

Now, notice that by definition of $\eta_{t}^{i},$ we have

$\displaystyle\eta_{t}^{i}=\frac{\|x_{t}^{i}-x_{t-1}^{i}\|}{2\|\nabla
f(x_{t}^{i})-\nabla
f(x_{t-1}^{i})\|}\geqslant\frac{1}{2\tilde{L}_{i}}\geqslant\frac{1}{2L},\quad\forall
i\in[m].$

where $\tilde{L}_{i}$ is defined in (10), which by definition is smaller than
or equal to the global smoothness $L$. Also, notice that
$\eta_{1}^{i}\theta_{1}^{i}=\frac{(\eta_{1}^{i})^{2}}{\eta_{0}^{i}}=(\eta_{1}^{i})^{2},$
assuming for simplicity that $\eta_{0}^{i}=1.$ Thus, going back to (43), we
have

$\displaystyle
S_{t}^{i}=\sum_{k=1}^{t}\eta_{k}^{i}+\eta_{1}^{i}\theta_{1}^{i}$
$\displaystyle\geqslant\sum_{k=1}^{t}\frac{1}{2\tilde{L}_{i}}+\frac{1}{4\tilde{L}_{i}^{2}}$
$\displaystyle=\frac{t}{2L_{i}}+\frac{1}{4L_{i}^{2}}\geqslant\frac{t}{2L}+\frac{1}{4L^{2}}.$

Finally, we have

$\displaystyle\frac{D}{2}$
$\displaystyle\geqslant\frac{1}{m}\sum_{i=1}^{m}S_{t}^{i}\big{(}f_{i}(\tilde{x}_{t}^{i})-f_{i}(x^{\star})\big{)}$
$\displaystyle\geqslant\frac{1}{m}\sum_{i=1}^{m}\Big{(}\frac{t}{2L}+\frac{1}{4L^{2}}\Big{)}\big{(}f_{i}(\tilde{x}_{t}^{i})-f_{i}(x^{\star})\big{)},$

which implies

$\displaystyle\frac{2DL^{2}}{2Lt+1}\geqslant\frac{1}{m}\sum_{i=1}^{m}\big{(}f_{i}(\tilde{x}_{t}^{i})-f_{i}(x^{\star})\big{)}.$

∎

###  A.3 Proof of adaptive gradient descent in nonconvex case: centralized

For the centralized version, we use the original step size from [34] as in
(4).

######  Theorem 6.

Running gradient descent with step size in (4) for nonconvex $f$, it holds
that

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla
f(x_{t})\|^{2}\leqslant\frac{8\tilde{L}}{3T}[f(x_{0})-f^{\star}],$

where $\tilde{L}$ is the local-smoothness on the set
$\mathcal{C}=\text{conv}\\{x_{0},x_{1},\dots\\}$:

$\displaystyle\|\nabla f(x)-\nabla f(y)\|\leqslant\tilde{L}\|x-y\|\quad\forall
x,y\in\mathcal{C}$

###### Proof.

Using Lemma 2, where with slight abuse of notation we interpret $f_{i}$ as $f$
and $\eta_{t}^{i}$ as $\eta_{t},$ we have

$\displaystyle f(x_{t+1})$ $\displaystyle\leqslant f(x_{t})+\langle\nabla
f(x_{t}),x_{t+1}-x_{t}\rangle+\frac{1}{4\eta_{t}}\|x_{t+1}-x_{t}\|^{2}$
$\displaystyle=f(x_{t})+\langle\nabla f(x_{t}),-\eta_{t}\nabla
f(x_{t})\rangle+\frac{1}{4\eta_{t}}\|x_{t+1}-x_{t}\|^{2}$
$\displaystyle=f(x_{t})-\eta_{t}\|\nabla
f(x_{t})\|^{2}+\frac{\eta_{t}}{4}\|\nabla f(x_{t})\|^{2}$
$\displaystyle=f(x_{t})-\frac{3\eta_{t}}{4}\|\nabla f(x_{t})\|^{2}$

Rearranging, we have

$\displaystyle\|\nabla
f(x_{t})\|^{2}\leqslant\frac{4}{3\eta_{t}}[f(x_{t})-f^{\star}+f^{\star}-f(x_{t-1})]$

Unfolding for $T$ iterations and using telescoping, we get

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla
f(x_{t})\|^{2}\leqslant\frac{4}{3T\eta_{t}}[f(x_{0})-f^{\star}]\leqslant\frac{8\tilde{L}}{3T}[f(x_{0})-f^{\star}]$

as desired. ∎

##  Appendix B Additional Experiments and Plots

###  B.1 Ease of tuning

In this subsection, we show the effect of using different parameter $\delta$
in the step size of $\Delta$-SGD. As mentioned in Section 4, for $\Delta$-SGD,
we append $\delta$ in front of the second condition, and hence the step size
becomes

$\eta_{t,k}^{i}=\min\Big{\\{}\tfrac{\gamma\|x_{t,k}^{i}-x_{t,{k-1}}^{i}\|}{2\|\tilde{\nabla}f_{i}(x_{t,k}^{i})-\tilde{\nabla}f_{i}(x_{t,{k-1}}^{i})\|},\sqrt{1+\delta\theta_{t,k-1}^{i}}\eta_{t,k-1}^{i}\Big{\\}}.$

The experimental results presented in Table 1 were obtained using a value of
$\delta=0.1$. For $\gamma$, we remind the readers that we did not change from
the default value $\gamma=2$ in the original implementation in
https://github.com/ymalitsky/adaptive_GD/blob/master/pytorch/optimizer.py.

In Figure 4, we display the final accuracy achieved when using different
values of $\delta$ from the set $\\{0.01,0.1,1\\}$. Interestingly, we observe
that $\delta$ has very little impact on the final accuracy. This suggests that
$\Delta$-SGD is remarkably robust and does not require much tuning, while
consistently achieving higher test accuracy compared to other methods in the
majority of cases as shown in Table 1.

Figure 4: Effect of using different $\delta$ in the second condition of the
step size of $\Delta$-SGD.

###  B.2 Illustration of the degree of non-iidness

As mentioned in the main text, the level of "non-iidness" is controlled using
latent Dirichlet allocation (LDA) applied to the labels. This approach is
based on [19] and involves assigning each client a multinomial distribution
over the labels. This distribution determines the labels from which the
client’s training examples are drawn. Specifically, the local training
examples for each client are sampled from a categorical distribution over $N$
classes, parameterized by a vector $\mathbf{q}$. The vector $\mathbf{q}$ is
drawn from a Dirichlet distribution with a concentration parameter $\alpha$
times a prior distribution vector $\mathbf{p}$ over $N$ classes.

To vary the level of "non-iidness," different values of $\alpha$ are
considered: $0.01,0.1$, and $1$. A larger $\alpha$ corresponds to settings
that are closer to i.i.d. scenarios, while smaller values introduce more
diversity and non-iidness among the clients, as visualized in Figure 5. As can
be seen, for $\alpha=1,$ each client (each row on $y$-axis) have fairly
diverse classes, similarly to the i.i.d. case; as we decrease $\alpha,$ the
number of classes that each client has access to decreases. With
$\alpha=0.01,$ there are man y clients who only have access to a single or a
couple classes.

Figure 5: Illustration of the degree of heterogeneity induced by using
different concentration parameter $\alpha$ for Dirichlet distribution, for
CIFAR-10 dataset (10 colors) and 100 clients (100 rows on $y$-axis).

###  B.3 Effect of different number of local iterations

In this subsection, we show the effect of different number of local epochs
performed per client, while fixing the experimental setup to be the
classification of CIFAR-100 datset, trained with a ResNet-50. We show for all
three cases of the Dirichlet concentration parameter
$\alpha\in\\{0.01,0.1,1\\}$. The result is shown in Figure 6.

As mentioned in the main text, instead of performing local iterations, we
instead perform local epochs $E,$ similarly to [47, 31]. All the results in
Table 1 use $E=1,$ and in Figure 6, we show the results for $E\in\\{1,2,3\\}$.
Note that in terms of $E$, the considered numbers might be small difference,
but in terms of actual local gradient steps, they differ significantly.

As can be seen, using higher $E$ leads to slightly faster convergence in all
cases of $\alpha.$ However, the speed up seems marginal compared to the amount
of extra computation time it requires (i.e., using $E=2$ takes roughly twice
more total wall-clock time than using $E=1$). Put differently, $\Delta$-SGD
performs well with only using a single local epoch per client ($E=1$), and
still can achieve great performance.

Figure 6:

###  B.4 Additional experiments using different number of local data per
client

In this subsection, we provide additional experimental results, where the size
of the local dataset each client has differs. In particular, instead of
distributing $500$ samples to each client as done in Section 4 of the main
text, we distribute $n_{i}\in[100,500]$ samples for each client $i$, where
$n_{i}$ is the number of samples that client $i$ has, and is randomly sampled
from the range $[100,500]$. We keep all other settings the same.

Then, in the server aggregation step (line 13 of Algorithm 1), we compute the
weighted average of the local parameters, instead of the plain average, as
suggested in [35], and used for instance in [47].

We experiment in two settings: CIFAR-10 dataset classification trained with a
ResNet-18 [18], with Dirichlet concentration parameter $\alpha=0.1,$ which was
the setting where the algorithms were fined-tuned using grid search; please
see details in Section 4. We also provide results for CIFAR-100 dataset
classification trained with a ResNet-50, with the same $\alpha.$

The result can be found in Table 2. Similarly to the case with same number of
data per client, $i.e.,n_{i}=500$ for all $i\in[m],$ we see that $\Delta$-SGD
achieves good performance without any additional tuning. In particular, for
CIFAR-10 classification trained with a ResNet-18, $\Delta$-SGD achieves the
second best performance after SGD (without LR decay), with a small margin.
Interestingly, SGDM (both with and without LR decay) perform much worse than
SGD. This contrasts with the same setting in Table 1, where SGDM performed
better than SGD, which again complicates how one should tune client optimizers
in the FL setting. For CIFAR-100 classification trained with ResNet-50,
$\Delta$-SGD outperforms all other methods with large margin.

Non-iidness | Optimizer | Dataset / Model
---|---|---
$\text{Dir}(\alpha\cdot\mathbf{p})$ |  | CIFAR-10 | CIFAR-100
ResNet-18 | ResNet-50
$\alpha=1$ | SGD | 80.7↓(0.0) | 53.5↓(4.0)
SGD ($\downarrow)$ | 78.8↓(1.9) | 53.6↓(3.9)
SGDM | 75.0↓(5.7) | 53.9↓(3.6)
SGDM ($\downarrow)$ | 66.6↓(14.1) | 53.1↓(4.4)
Adam | 79.9↓(0.8) | 51.1↓(6.4)
Adagrad | 79.3↓(1.4) | 44.5↓(13.0)
SPS | 64.4↓(16.3) | 37.2↓(20.3)
$\Delta$-SGD | 80.4↓(0.3) | 57.5↓(0.0)
Table 2: Experimental results using different number of local data per client.
Performance difference within 0.5% of the best result for each task are shown
in bold. Subscripts↓(x.x) is the performance difference from the best result
and is highlighted in pink when the difference is bigger than 2%. The symbol
($\downarrow$) appended to SGD and SGDM indicates step-wise learning rate
decay, where the step sizes are divided by $10$ after 50%, and another by $10$
after 75% of the total rounds.