# Robust Distributed Gradient Descent to Corruption over Noisy Channels

Shuche Wang1, and Vincent Y. F. Tan231
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>This paper was presented in
part at the 2024 IEEE International Symposium on Information Theory (ISIT)
[1].  1 Institute of Operations Research and Analytics, National University of
Singapore, Singapore
2 Department of Mathematics, National University of Singapore, Singapore
3 Department of Electrical and Computer Engineering, National University of
Singapore, Singapore

# A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed
Gradient Descent

Shuche Wang1, and Vincent Y. F. Tan231
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>This paper was presented in
part at the 2024 IEEE International Symposium on Information Theory (ISIT)
[1].  1 Institute of Operations Research and Analytics, National University of
Singapore, Singapore
2 Department of Mathematics, National University of Singapore, Singapore
3 Department of Electrical and Computer Engineering, National University of
Singapore, Singapore

###### Abstract

Distributed gradient descent algorithms have come to the fore in modern
machine learning, especially in parallelizing the handling of large datasets
that are distributed across several workers. However, scant attention has been
paid to analyzing the behavior of distributed gradient descent algorithms in
the presence of adversarial corruptions instead of random noise. In this
paper, we formulate a novel problem in which adversarial corruptions are
present in a distributed learning system. We show how to use ideas from (lazy)
mirror descent to design a corruption-tolerant distributed optimization
algorithm. Extensive convergence analysis for (strongly) convex loss functions
is provided for different choices of the stepsize. We carefully optimize the
stepsize schedule to accelerate the convergence of the algorithm, while at the
same time amortizing the effect of the corruption over time. Experiments based
on linear regression, support vector classification, and softmax
classification on the MNIST dataset corroborate our theoretical findings.

###### Index Terms:

Distributed gradient descent, Mirror descent, Adversarial corruptions, Noisy
channels, Convergence rates

##  I Introduction

Driven by the growing scale of datasets in various learning tasks, distributed
gradient descent has become increasingly important in modern machine learning
[2, 3, 4]. In this paradigm, there is a central parameter server coordinating
information among all workers and each worker in the system processes partial
gradients using its subset of data [5, 6]. These partial gradients are then
collectively used to update the global model parameters. Such a distributed
framework not only expedites the learning process but also manages datasets
that are too large to be handled in the memory of a single worker or server.

However, there are significant challenges in the use of distributed gradient
descent such as the communication overhead [7], the necessity for resilience
against system failures [8, 9], and the presence of adversarial attacks [10,
11, 12, 13]. In a distributed framework, workers may become unreliable (called
Byzantine workers in the sequel), which can disrupt the learning process. For
instance, as demonstrated in [14], the presence of even a single Byzantine
worker can undermine the convergence of a distributed gradient descent
algorithm.

In this paper, we consider a new problem concerning the distributed gradient
descent algorithm but we take into account a novel and critical aspect that
has, to the best of our knowledge, not been considered before. We consider the
presence of adversarial corruptions at each worker in addition to the usual
random (Gaussian) noises in the uplink and downlink channels. The corruptions
and noises affect the accuracy of partial gradients and parameters. Each
worker experiences adversarial corruption, with the total corruption budget
being bounded over the entire time horizon. Our convergence analysis of a
modified version of a (lazy) mirror descent-type algorithm addresses the
worst-case scenario of these corruptions subject to a long-term constraint on
the total corruption budget. We show both theoretically and empirically that
our algorithm RDGD and its variants such as RDGD-Restart can be suitably tuned
to be corruption tolerant.

###  I-A Main Contributions

Our main contributions are as follows:

  1. 1.

We formulate the problem of distributed gradient descent with adversarial
corruptions on the partial gradient vectors held by each of the $m$ workers.
We impose a bound $C(T)$ on the total amount of corruptions over the $m$
workers and over the time horizon $T$. The uplink and downlink channels are
also subject to the usual Gaussian noises.

  2. 2.

We design a mirror descent-inspired distributed gradient descent algorithm
RDGD that is robust to corruptions. For smooth and convex functions, we show
that the expected suboptimality gap of RDGD scales as
$O\big{(}\frac{C(T)}{m\sqrt{T}}\big{)}$.

  3. 3.

We extend RDGD to the case of loss functions that are strongly convex in
addition to being smooth. We bound the suboptimality gap of the enhanced
algorithm RDGD-SC. The convergence behavior of RDGD-SC depends on different
choices of the stepsize. For a certain choice of stepsize, we observe that the
expected suboptimality gap decays as $O\big{(}\rho^{t}+\frac{C(t)}{m}\big{)}$
where $\rho\in(0,1)$ is a contraction factor and $t$ is number of iterations,
while for another choice, the gap decays as
$O\big{(}\frac{1}{t^{2}}+\frac{C(t)}{m\sqrt{t}}\big{)}$. Thus for the former,
there is an exponentially decaying term and a term that does not cause the
corruption to vanish; for the latter, there is a (slower) polynomially
decaying term and a term that amortizes the corruption.

  4. 4.

The above observation motivates us to design a hybrid algorithm RDGD-Restart
that exploits the benefits of each choice of the stepsize. RDGD-Restart
switches the stepsize schedule at an analytically determined transition time.
In RDGD-Restart, we first exploit the exponential decrease of the
suboptimality gap, and eventually amortize the corruption by changing the
stepsize.

  5. 5.

The proposed algorithms are assessed numerically through several canonical
machine learning models such as linear regression, support vector
classification, and softmax classification (on the MNIST dataset). All
experimental results corroborate our theoretical findings.

###  I-B Related Works

There are many studies that analyze the effect of random corruptions in
(stochastic) gradient descent [15, 16, 17] and its accelerated versions [15,
18, 19]. Our study adopts a distinctly different approach in which we focus on
the effect of malicious adversarial corruptions, instead of random ones, on
distributed gradient descent-type algorithms. In this scenario, some workers
send maliciously corrupted gradient information to adversely affect the
system’s performance. In [20], the authors investigate the robustness of
gradient descent in the face of the worst case of corruption, where
adversaries can manipulate the corruption up to a certain bounded extent
throughout the gradient descent process. In contrast to our distributed
gradient descent formulation, [20] considers a centralized gradient descent
scheme. Furthermore, the approach of [20] does not modify the traditional
gradient descent algorithm to further mitigate the adversarial corruption’s
effect.

Another line of research that relevant to our work pertains to _Byzantine
distributed gradient descent_. Byzantine faults refer to the scenario where
some nodes in the distributed network act arbitrarily or maliciously,
potentially leading to incorrect or suboptimal outcomes. One line of solutions
is based on the robust aggregation rules, including trimmed mean [12],
coordinate-wise median [12], geometric median [11], and Krum [14]. However,
these robust aggregation rules work under the assumption that the number of
Byzantine workers is less than half the total number of workers. Our research
approach bifurcates from this line of research since we allow the adversary to
arbitrarily allocate a bounded amount of corruptions among all workers.

In addition, these robust aggregation methods can, in general, only recover
the parameters obtained from vanilla gradient descent with high probability
but not with probability one. To address this challenge, an algorithm called
DRACO is presented in [10]. DRACO is a framework that applies repetition codes
to the computational results of the workers. This requires roughly doubling
the replication of each gradient computation, i.e., $2s+1$ replications of
each partial gradient for $s$ malicious workers. Recently, [21] reduced the
number of replications from $2s+1$ to $s+1$ by introducing an additional step
to first detect the Byzantine workers. However, if the channels used for
transmitting the parameters are noisy, this idea of replicating each partial
gradient does not work perfectly well since the parameter server may fail to
reliably select the majority among all the corrupted partial gradients.

The works on adversarial optimization are also closely related to some lines
of work in the multi-armed bandit literature, particularly in the adversarial
(and not stochastic) setting [22, 23, 24, 25]. In these settings, adversarial
corruption is added to the random rewards, resulting in the agent receiving
corrupted versions of the rewards. These approaches typically assume the
adversary is capable of arbitrarily allocating corruption in a malicious
manner within a total corruption budget. They then use various randomized
policies to mitigate the effect of the corruption. However, our study focuses
on distributed gradient descent, which is a first-order optimization method
that is rather different scenarios with bandit feedback.

###  I-C Outline

The rest of this paper is organized as follows. The framework of distributed
gradient descent in the presence of adversarial corruptions over noisy
channels is presented precisely in Section II. The proposed RDGD algorithm and
the analysis of its expected suboptimality gap for smooth loss functions are
developed in Section III. In Section IV, we additionally assume the loss
function is strongly convex, design an extended algorithm RDGD-SC, and prove a
bound on its expected suboptimality gap. The algorithm RDGD-Restart to
mitigate corruption accumulation through a judicious choice of stepsizes is
presented in Section V. Numerical experiments are presented in Section VI.
Finally, Section VII concludes the paper by suggesting several avenues for
further research.

##  II Problem Setting

In this section, we present the framework of distributed gradient descent in
the presence of corruptions and noise in channels in both the downlink and the
uplink. In addition, we present some basic notations and preliminaries that
will facilitate the subsequent analysis.

###  II-A Distributed Gradient Descent

We assume that the samples in a dataset
$\mathcal{Z}=\\{(x_{i},y_{i})\\}_{i=1}^{N}$ are drawn from an unknown
distribution $\mathcal{D}$. Here $x_{i}\in\mathbb{R}^{p}$ is the $i$-th
feature vector and $y_{i}\in\mathbb{R}$ is the corresponding scalar response
(which could be discrete or continuous). Let $\Theta\subset\mathbb{R}^{p}$ be
the set of model parameters. We seek to minimize the average of loss functions
$L:\mathbb{R}^{p}\times\mathbb{R}\times\Theta\rightarrow\mathbb{R}$ each
evaluated over a sample in $\mathcal{Z}$, i.e., we consider the problem

$\min_{\theta\in\Theta}\Big{\\{}L(\theta)\coloneq\frac{1}{N}\sum_{i=1}^{N}L(x_{i},y_{i};\theta)\Big{\\}}.$

In a centralized gradient descent scheme, the model parameter
$\theta_{t}\in\Theta$ is updated at iteration $t$ as follows,

$\theta_{t+1}=\theta_{t}-\eta_{t}g_{t},$

where $g_{t}:=\frac{1}{N}\sum_{i=1}^{N}\nabla L(x_{i},y_{i};\theta_{t})$ is
the full gradient ($\nabla L(x_{i},y_{i};\theta)$ is the gradient vector of
$L(x_{i},y_{i};\theta)$ w.r.t. $\theta$) and $\eta_{t}$ is an appropriately
chosen stepsize at iteration $t$.

When $N$ is large, it is inefficient to compute the full gradient $g_{t}$.
Rather, one typically parallelizes the computation of $g_{t}$ by distributing
the data points among $m\ll N$ workers. We assume the $N$ data samples in
$\mathcal{Z}$ are uniformly partitioned among the $m$ workers.111Without loss
of generality, we assume $N$ is a multiple of $m$. In particular, the $i$-th
worker maintains a subset $\mathcal{Z}_{i}$ of the dataset $\mathcal{Z}$,
where $\mathcal{Z}_{i}\cap\mathcal{Z}_{j}=\emptyset$, $|\mathcal{Z}_{i}|=N/m$.
Then, worker $i$ computes its partial gradient vector

$g_{i,t}:=\frac{1}{|\mathcal{Z}_{i}|}\sum_{(x,y)\in\mathcal{Z}_{i}}\nabla
L(x,y;\theta_{t}).$

This partial gradient vector is then sent to the server.

###  II-B Noisy channel transmission

At the $t$-th iteration of distributed gradient descent, the parameter server
broadcasts the current model parameter $\theta_{t}\in\Theta$ to all $m$
workers through noisy downlink channels. Worker $i$ receives a noisy version
of $\theta_{t}$ as:

$\theta_{i,t}=\theta_{t}+v_{t}^{(i)},$ (1)

where
$v_{t}^{(i)}=[v_{t,1}^{(i)},\dotsc,v_{t,p}^{(i)}]^{\top}\in\mathbb{R}^{p}$ is
the $p$-dimensional noise vector at worker $i$ and time $t$. Furthermore,
$v_{t}^{(i)}$ is a zero-mean random vector consisting of independent and
identically distributed (i.i.d.) elements with variance
$\mathbb{E}[(v_{t,k}^{(i)})^{2}]=\sigma_{t}^{2}$. Thus,

$\mathbb{E}[\|v_{t}^{(i)}\|_{2}^{2}]=p\sigma_{t}^{2},\quad\forall i\in[m].$

Now, the noisy partial gradient vector at worker $i$ for based on its local
dataset $\mathcal{Z}_{i}$ can be written as

$g^{\prime}_{i,t}:=\frac{1}{|\mathcal{Z}_{i}|}\sum_{(x,y)\in\mathcal{Z}_{i}}\nabla
L(x,y;\theta_{i,t}),$ (2)

where $\theta_{i,t}$ is the noisy parameter vector in (1).

###  II-C Corrupted gradients

At iteration $t$, instead of transmitting the true local gradients, due to
Byzantine faults, each worker also suffers an arbitrary corruption to its
partial gradient vector as follows:

$\bar{g}_{i,t}=g^{\prime}_{i,t}+\varepsilon_{i,t}.$ (3)

Here the corruption $\varepsilon_{i,t}$ is a vector in $\mathbb{R}^{p}$.
Define the $\ell_{2}$ norm of the total corruption at iteration $t$ as:

$c_{t}=\bigg{\|}\sum_{i=1}^{m}\varepsilon_{i,t}\bigg{\|}_{2}.$ (4)

This quantifies the aggregate corruption in gradients, introduced by the
adversary at iteration $t$. We denote the corruption vector as
$c=[c_{1},c_{2},\dotsc,c_{T}]^{\top}\in\mathbb{R}^{T}$ and assume that there
is an overall $\ell_{2}$ bound on it across the entire time horizon. The form
of the bound we employ is

$\|c\|_{2}=\Big{(}\sum_{t=1}^{T}c_{t}^{2}\Big{)}^{1/2}\leqslant C(T).$ (5)

We emphasize that terms $\\{\varepsilon_{i,t}\\}$ and hence, $\\{c_{t}\\}$,
and $c$ are deterministic quantities induced by Byzantine faults. These are in
contrast to the stochastic noises in the (downlink and uplink) channels. Our
subsequent analysis is thus applicable to the worst-case instantiation of
these corruptions subject to the constraint in (5).

The $i$-th worker sends $\bar{g}_{i,t}$ defined in (3) to the parameter
server. However, due to the presence of noise in the uplink communication
channels, the parameter server receives the following perturbed version of
$\bar{g}_{i,t}$ from worker $i$:

$\tilde{g}_{i,t}=\bar{g}_{i,t}+w_{t}^{(i)},$ (6)

where
$w_{i,t}^{(i)}=[w_{t,1}^{(i)},\dotsc,w_{t,p}^{(i)}]^{\top}\in\mathbb{R}^{p}$
is a $p$-dimensional noise vector at worker $i$ and time $t$. Furthermore,
$w_{t}^{(i)}$ is a zero-mean random vector consisting of i.i.d. elements with
variance $\mathbb{E}[(w_{t,k}^{(i)})^{2}]=\sigma_{t}^{2}$. As a result,

$\mathbb{E}[\|w_{t}^{(i)}\|_{2}^{2}]=p\sigma_{t}^{2},\quad\forall\,i\in[m].$

An illustration of our distributed gradient descent setting with corruptions
over noisy channels is presented in Fig. 1.

……Worker 1Worker $i$ Worker $m$
Server$\theta_{t}+\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{v_{t}^{(1)}}$$g^{\prime}_{1,t}\\!+\\!{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\varepsilon_{1,t}}}\\!+\\!\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{w_{t}^{(1)}}$……$\theta_{t}\\!+\\!\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{v_{t}^{(m)}}$$g^{\prime}_{m,t}\\!+\\!{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\varepsilon_{m,t}}}\\!+\\!\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{w_{t}^{(m)}}$

Figure 1: Illustration of the distributed gradient descent setting with
corruption over noisy channels. The variables indicated in blue are random
Gaussian noises, defined in (1) and (6). The variables indicated in red are
deterministic adversarial corruptions specified in (3) and subject to the
bound in (5).

###  II-D Preliminaries

Consider a continuously differentiable function $f:\Theta\to\mathbb{R}$, where
$\Theta\subseteq\mathbb{R}^{p}$ is a closed and convex set. The convexity of
$f$ is characterized by the following inequality:

$f(\theta^{\prime})\geqslant f(\theta)+\langle\nabla
f(\theta),\theta^{\prime}-\theta\rangle,\quad\forall\,\theta^{\prime},\theta\in\Theta.$

######  Definition 1 (Smoothness)

A differentiable function $f:\Theta\to\mathbb{R}$ is $M$-smooth on $\Theta$ if
for all $\theta,\hat{\theta}\in\Theta$,

$f(\hat{\theta})\leqslant f(\theta)+\langle\nabla
f(\theta),\hat{\theta}-\theta\rangle+\frac{M}{2}\|\hat{\theta}-\theta\|_{2}^{2}.$

######  Definition 2 (Strong Convexity)

A differentiable function $f:\Theta\to\mathbb{R}$ is $\mu$-strongly convex on
$\Theta$ if for all $\theta,\hat{\theta}\in\Theta$,

$f(\hat{\theta})\geqslant f(\theta)+\langle\nabla
f(\theta),\hat{\theta}-\theta\rangle+\frac{\mu}{2}\|\hat{\theta}-\theta\|_{2}^{2}.$

######  Definition 3 (Convex Conjugate)

The convex conjugate of a function
$\psi:\Theta\subset\mathbb{R}^{p}\to\mathbb{R}$, denoted as
$\psi^{*}:\mathbb{R}^{p}\rightarrow\mathbb{R}\cup\\{\pm\infty\\}$

$\psi^{*}(z)=\max_{\theta\in\Theta}\\{\langle
z,\theta\rangle-\psi(\theta)\\}.$

In the following, we assume that whenever we have to compute the convex
conjugate $\psi^{*}$ of a function $\psi:\Theta\to\mathbb{R}$, this can be
done efficiently and potentially in closed form.

The following is a corollary of Danskin’s Theorem [26].

###### Proposition 1

Let $\psi:\Theta\to\mathbb{R}$ be a differentiable and strongly convex
function. Then, the gradient of its convex conjugate $\psi^{*}$ at any point
$z$ is given by:

$\nabla\psi^{*}(z)=\operatorname*{arg\,max}_{\theta\in\Theta}\\{\langle
z,\theta\rangle-\psi(\theta)\\}.$

######  Definition 4 (Bregman Divergence)

Let $\psi:\Theta\to\mathbb{R}$ be a continuously differentiable and strictly
convex function. The Bregman divergence
$D_{\psi}:\Theta^{2}\rightarrow\mathbb{R}$ is defined as:

$D_{\psi}(\theta,\theta^{\prime})\coloneq\psi(\theta)-\psi(\theta^{\prime})-\langle\nabla\psi(\theta^{\prime}),\theta-\theta^{\prime}\rangle.$

The Bregman divergence $D_{\psi}(\theta,\theta^{\prime})$ quantities the gap
between $\psi(\theta)$ and its first-order approximation at $\theta^{\prime}$.

##  III Robust distributed gradient descent to corruption over noisy channel

In this section, we present Robust Distributed Gradient Descent (RDGD), an
algorithm that is robust to corruptions over noisy channels. For the
minimization of smooth loss functions, the algorithm is described in Algorithm
1. We also provide a bound on the expected suboptimality gap of RDGD.

###  III-A The RDGD Algorithm

Algorithm 1 Distributed Gradient Descent Algorithm Robust to Corruptions over
Noisy Channels (RDGD)

1:Initialization: Parameter vector $\theta_{0}\in\Theta$, dual vector
$z_{0}=\nabla\psi(\theta_{0})$ for some $\mu$-strongly convex function $\psi$,
algorithm parameters $\eta_{t}$, and $T$. $\theta_{1}=\theta_{0}$ and
$\hat{\theta}_{0}=\theta_{0}$.

2:for $t=1,2,\ldots,T$ do

3: Parameter server: Send $\theta_{t}$ to all $m$ workers over the downlink
noisy channel.

4: for all $i\in[m]$ do in parallel

5: Worker $i$:

6: Receive $\theta_{i,t}=\theta_{t}+v_{t}^{(i)}$ and calculate the corrupted
local gradient $g^{\prime}_{i,t}$ in (2).

7: Send $\bar{g}_{i,t}=g^{\prime}_{i,t}+\varepsilon_{i,t}$ to the parameter
server via the noisy uplink channel.

8: end for

9: Parameter server:

10: Receive $\tilde{g}_{i,t}=\bar{g}_{i,t}+w_{t}^{(i)}$ for all $i\in[m]$.

11: Compute mean gradient
$\tilde{g}_{t}\leftarrow\frac{1}{m}\sum_{i=1}^{m}\tilde{g}_{i,t}$

12: Update model parameters:

13: $z_{t}=z_{t-1}-\eta_{t}\tilde{g}_{t}$, i.e.,
$z_{t}=-\sum_{k=1}^{t}\eta_{k}\tilde{g}_{k}+z_{0}$.

14:
$\hat{\theta}_{t}=\frac{H_{t-1}}{H_{t}}\hat{\theta}_{t-1}+\frac{\eta_{t}}{H_{t}}\theta_{t}$,
where $H_{t}=\sum_{k=1}^{t}\eta_{k}$.

15:
$\theta_{t+1}=\operatorname*{arg\,min}_{u\in\Theta}\\{\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k},u-\theta_{k}\rangle+D_{\psi}(u,\theta_{0})\\}$.

16:end for

17:Output: The parameter vector $\hat{\theta}_{T}$.

$\Theta$Dual SpacePrimal
Space$\nabla$$\psi$$\theta_{0}$$z_{0}$$z_{t}=-\sum_{k=1}^{t}\eta_{k}\tilde{g}_{k}+z_{0}$$\nabla\psi^{*}$$\theta_{t+1}$

Figure 2: Illustration of primal and dual updates in RDGD.

At a high level, we utilize a modified lazy mirror descent approach with
primal and dual updates. To initialize, we map the initial point $\theta_{0}$
to $z_{0}=\nabla\psi(\theta_{0})$ in the dual space via the mirror map
$\nabla\psi$ for some suitably chosen $\mu$-strongly convex function $\psi$.
At the $t$-th iteration of RDGD, the parameter server receives the corrupted
partial gradients $\tilde{g}_{i,t}$ for all $i\in[m]$. Then, the parameter
server calculates the mean of these $\tilde{g}_{i,t}$ and denotes it as
$\tilde{g}_{t}=\frac{1}{m}\sum_{i=1}^{m}\tilde{g}_{i,t}$ (Line 11). Next (Line
13), the server updates $z_{0}$ in the dual space to
$z_{t}=z_{0}-\sum_{k=1}^{t}\eta_{k}\tilde{g}_{k}.$ It then maps $z_{t}$ back
to the point $\theta_{t+1}$ in the primal space (Line 15). The illustration of
the primal and dual updates in RDGD is presented in Fig. 2. We let

$\nabla\psi^{*}(z_{t})=\operatorname*{arg\,min}_{u\in\Theta}\Big{\\{}\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k},u-\theta_{k}\rangle+\
D_{\psi}(u,\theta_{0})\Big{\\}}.$ (7)

This process can be considered as a modified version of lazy mirror descent
[27]. The intuition behind RDGD is that in (7), we are minimizing an
approximation of the loss function, regularized by the Bregman divergence
$D_{\psi}(u,\theta_{0})$. Introducing this regularizer prevents the updated
point $\theta_{t+1}$ from straying too far from the current point $\theta_{t}$
when there are corruptions. Also, we denote
$\hat{\theta}_{t}=\frac{H_{t-1}}{H_{t}}\hat{\theta}_{t-1}+\frac{\eta_{t}}{H_{t}}\theta_{t},$
(where $H_{t}=\sum_{k=1}^{t}\eta_{k}$) as the output at iteration $t$ (Line
14). We note that $\hat{\theta}_{t}$ is the sum of the weighted gradients
based on the history of gradients. As the analysis shows, this ensures that
the final output of RDGD $\hat{\theta}_{T}$ is robust against noisy updates.

###  III-B Convergence Analysis

We apply the approximate duality gap technique proposed in [28] to analyze the
convergence of RDGD. We will show how to construct an upper bound $G_{t}$ of
the suboptimality gap $L(\hat{\theta}_{t})-L({\theta^{*}})$, where
$\hat{\theta}_{t}$ is the output of a first-order method at the $t$-th
iteration. Denote $G_{t}=U_{t}-L_{t}$, where $U_{t}\geqslant
L(\hat{\theta}_{t})$ is an upper bound on $L(\hat{\theta}_{t})$ and
$L_{t}\leqslant L({\theta^{*}})$ is a lower bound on $L({\theta^{*}})$. Define
$H_{t}\coloneq\sum_{k=1}^{t}\eta_{k}$. For the lower bound $L_{t}$, by the
convexity of $L$, we have

$L(\theta^{*})\geqslant\frac{\sum_{k=1}^{t}\eta_{k}L(\theta_{k})+\sum_{k=1}^{t}\eta_{k}\langle\nabla
L(\theta_{k}),\theta^{*}-\theta_{k}\rangle}{H_{t}}.$ (8)

To express the gradient $\nabla L(\theta_{k})$ in relation to the corrupted
gradients $\\{\tilde{g}_{i,k}:i\in[m]\\}$, we write $\nabla L(\theta_{k})$ as
$\nabla L(\theta_{k})=\tilde{g}_{k}+\nabla L(\theta_{k})-\tilde{g}_{k}$. Also,
by adding and subtracting $\frac{1}{H_{t}}D_{\psi}(\theta^{*},\theta_{0})$ in
(8), we have

$\displaystyle
H_{t}L(\theta^{*})\geqslant\sum_{k=1}^{t}\eta_{k}L(\theta_{k})+\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k},\theta^{*}-\theta_{k}\rangle$
$\displaystyle-\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k}-\nabla
L(\theta_{k}),\theta^{*}-\theta_{k}\rangle+D_{\psi}(\theta^{*},\theta_{0})-D_{\psi}(\theta^{*},\theta_{0}).$

Next, we can obtain our lower bound by replacing $\theta^{*}$ by a
minimization over $\Theta$:

$\displaystyle
H_{t}L(\theta^{*})\geqslant\sum_{k=1}^{t}\eta_{k}L(\theta_{k})-\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k}-\nabla
L(\theta_{k}),\theta^{*}-\theta_{k}\rangle$ $\displaystyle-
D_{\psi}(\theta^{*},\theta_{0})+\min_{u\in\Theta}\Big{\\{}\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k},u-\theta_{k}\rangle+D_{\psi}(u,\theta_{0})\Big{\\}}.$

We then define $H_{t}L_{t}$ as the lower bound above, i.e.,

$\displaystyle L_{t}$
$\displaystyle\coloneq\frac{1}{H_{t}}\Big{\\{}\sum_{k=1}^{t}\eta_{k}L(\theta_{k})-\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k}-\nabla
L(\theta_{k}),\theta^{*}-\theta_{k}\rangle$ $\displaystyle\hskip 85.35826pt-
D_{\psi}(\theta^{*},\theta_{0})+\min_{u\in\Theta}h_{t}(u)\Big{\\}},$

where

$h_{t}(u)\coloneq\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k},u-\theta_{k}\rangle+D_{\psi}(u,\theta_{0}).$
(9)

The promised upper bound is chosen as $U_{t}=L(\hat{\theta}_{t})$, where
$\hat{\theta}_{t}$ is a weighted average of the points
$(\theta_{k})_{k=1}^{t}$ generated from RDGD up to $t$-th iteration (specified
in Line 14). Given the forms of $U_{t}$ and $L_{t}$, it is evident that
$L(\hat{\theta}_{t})-L(\theta^{*})\leqslant G_{t}$. Therefore, demonstrating
the convergence of the algorithm primarily is tantamount to establishing a
bound for $G_{t}$. We need to track the change of
$E_{t}=H_{t}G_{t}-H_{t-1}G_{t-1}$. To facilitate subsequent analyses, we
express $G_{t}$ as:

$G_{t}=\frac{H_{1}}{H_{t}}G_{1}+\frac{\sum_{k=2}^{t}E_{k}}{H_{t}}.$

According to RDGD,
$\theta_{t+1}=\operatorname*{arg\,min}_{u\in\Theta}h_{t}(u)$. For our
analysis, we first bound $h_{t}(\theta_{t+1})-h_{t-1}(\theta_{t})$ to track
the change of the lower bound $L_{t}$ in the following lemma. The proof is
provided in Appendix A.

###### Lemma 1

For all $t\geqslant 1$, the following holds:

$h_{t}(\theta_{t+1})-h_{t-1}(\theta_{t})\geqslant\eta_{t}\langle\tilde{g}_{t},\theta_{t+1}-\theta_{t}\rangle+D_{\psi}(\theta_{t+1},\theta_{t}).$

Now, we can derive an upper bound on $H_{t}G_{t}-H_{t-1}G_{t-1}$ based on
Lemma 1. The proof is provided in Appendix B.

###### Lemma 2

For all $t\geqslant 1$, the following holds:

$H_{t}G_{t}-H_{t-1}G_{t-1}\leqslant\eta_{t}\langle\tilde{g}_{t}-L(\theta_{t}),\theta^{*}-\theta_{t+1}\rangle\\\
-\eta_{t}\langle L(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle-
D_{\psi}(\theta_{t+1},\theta_{t}).$

Finally, we state the convergence rate of RDGD.

###### Theorem 1

Let $0<M<\infty$ be such that for all
$(x,y)\in\mathbb{R}^{p}\times\mathbb{R}$, $\ L(x,y;\cdot)$ is $M$-smooth. Let
$\theta_{0}\in\Theta$ be an arbitrary initial point. Let
$\\{(\theta_{t},z_{t},\hat{\theta}_{t})\\}_{t=1}^{T}$ evolve according to RDGD
(Algorithm 1) for some $\mu$-strongly convex function $\psi$, where
$R_{\Theta}=\max_{\theta\in\Theta}\|\theta-\theta^{*}\|_{2}$. For a fixed
number of iterations $T$ and stepsize $\eta_{k}=\frac{1}{\sqrt{T}}$, we have
for all $k\geqslant 1$:

$\displaystyle\mathbb{E}[L(\hat{\theta}_{T})-L(\theta^{*})]$
$\displaystyle\leqslant\frac{D_{\psi}(\theta^{*},\theta_{0})}{\sqrt{T}}+\frac{M^{2}}{2\mu}\cdot\frac{1}{\sqrt{T}}$
$\displaystyle+\frac{R_{\Theta}C(T)}{m}\cdot\frac{1}{\sqrt{T}}+(M+1)\sqrt{p}\sigma
R_{\Theta}.$

The first two terms $\frac{D_{\psi}(\theta^{*},\theta_{0})}{\sqrt{T}}$ and
$\frac{M^{2}}{2\mu}\cdot\frac{1}{\sqrt{T}}$ are similar to what one would
expect for mirror descent [29]. Since we assume that $\Theta$ is bounded,
$R_{\Theta}$ is finite. The effect of the adversarial corruption is manifested
in the term $\frac{R_{\Theta}C(T)}{m}\cdot\frac{1}{\sqrt{T}}$, where recall
that $C(T)$ (defined in (5)) represents the total corruption among all $m$
workers over $T$ iterations. Even though we do not have a lower bound on the
gap $\mathbb{E}[L(\hat{\theta}_{T})-L(\theta^{*})]$, the scaling
$O\big{(}\frac{C(T)}{m\sqrt{T}}\big{)}$ is intuitively order-optimal as, based
on (5), if each worker suffers a constant amount of corruption at each time,
then $C(T)=\Theta(m\sqrt{T})$. Besides, if the variances of the noises in both
downlink and uplink channels are bounded across all iterations (i.e.,
$\sigma_{t}^{2}\leqslant\bar{\sigma}^{2}$ for all $t$ and some
$\bar{\sigma}^{2}<\infty$), the effect of noisy channels on the bound is the
constant $(M+1)\sqrt{p}\sigma R_{\Theta}$. We provide the proof of Theorem 1
in Appendix C.

If the number of iterations $T$ is not known a priori, then $\eta_{k}$ cannot
depend on $T$. In this case, we can set $\eta_{k}=\frac{1}{\sqrt{k}}$ for all
$k\geqslant 1$. A simple corollary of Theorem 1 says that under the same
assumptions, for all $t\geqslant 1$,

$\displaystyle\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]$
$\displaystyle\leqslant\frac{D_{\psi}(\theta^{*},\theta_{0})}{\sqrt{t}}+\frac{M^{2}}{2\mu}\cdot\frac{\log
t}{\sqrt{t}}$ $\displaystyle+\frac{R_{\Theta}C(t)}{m}\cdot\sqrt{\frac{\log
t}{t}}+(M+1)\sqrt{p}\sigma R_{\Theta}.$

The only difference vis-à-vis the convergence rate specified in Theorem 1 is
the corruption term $O\big{(}\sqrt{\frac{\log t}{t}}\big{)}$, which is
slightly worse, by a factor of $\sqrt{\log t}$, than its counterpart in
Theorem 1. This is due to our incognizance of the number of iterations $T$.

##  IV The Strongly Convex Case

In this section, we make a further assumption that the loss function $L$ is
strongly convex (in addition to being smooth), and consequently, we are able
to improve on the convergence rate in Theorem 1. Our extended algorithm is
known as RDGD-SC (Algorithm 2), where the suffix SC stands for Strongly
Convex. In essence, assuming that the loss function $L$ is $\alpha$-strongly
convex, the only step that differs from Algorithm 1 is Line 15 therein, which
now reads:

$\displaystyle\theta_{t+1}$
$\displaystyle=\operatorname*{arg\,min}_{u\in\Theta}\Big{\\{}\sum_{k=1}^{t}\eta_{k}\left(\langle\tilde{g}_{t},u-\theta_{k}\rangle+\frac{\alpha}{2}\|u-\theta_{k}\|^{2}\right)$
$\displaystyle\hskip 56.9055pt+D_{\psi}(u,\theta_{0})\Big{\\}}.$ (10)

The purpose of the quadratic term $\frac{\alpha}{2}\|u-\theta_{k}\|^{2}$ in
(10) is to exploit the strong convexity of the loss function $L$ to ensure
that the expected suboptimality gap decays faster; typically exponentially
fast in $t$.

Algorithm 2 Distributed Gradient Descent Algorithm Robust to Corruptions over
Noisy Channels for Strongly-Convex Functions (RDGD-SC)

1:Initialization: Parameter vector $\theta_{0}\in\Theta$, algorithm parameters
$\eta_{t}$, dual vector $z_{0}=\nabla\psi(\theta_{0})$ with
$\psi(x)=\frac{\eta_{1}\alpha}{2}\|x\|_{2}^{2}$, $\theta_{1}=\theta_{0}$ and
$\hat{\theta}_{0}=\theta_{0}$.

2:for $t=1,2,\ldots$ do

3: Parameter server: Send $\theta_{t}$ to all the workers over the downlink
noisy channel.

4: for all $i\in[m]$ do in parallel

5: Worker $i$:

6: Receive $\theta_{i,t}=\theta_{t}+v_{t}^{(i)}$ and calculate the corrupted
local gradient $g^{\prime}_{i,t}$ in (2).

7: Send $\bar{g}_{i,t}=g^{\prime}_{i,t}+\varepsilon_{i,t}$ to parameter server
via the noisy uplink channel.

8: end for

9: Parameter server:

10: Receive $\tilde{g}_{i,t}=\bar{g}_{i,t}+w_{t}^{(i)}$, for all $i\in[m]$.

11: Compute mean gradient
$\tilde{g}_{t}\leftarrow\frac{1}{m}\sum_{i=1}^{m}\tilde{g}_{i,t}$.

12: Update model parameter:

13: $z_{t}=z_{t-1}-\eta_{t}\tilde{g}_{t}$, i.e.,
$z_{t}=-\sum_{k=1}^{t}\eta_{k}\tilde{g}_{k}+z_{0}$.

14:
$\hat{\theta}_{t}=\frac{H_{t-1}}{H_{t}}\hat{\theta}_{t-1}+\frac{\eta_{t}}{H_{t}}\theta_{t}$,
where $H_{t}=\sum_{k=1}^{t}\eta_{k}$.

15:
$\theta_{t+1}=\operatorname*{arg\,min}_{u\in\Theta}\\{\sum_{k=1}^{t}\eta_{k}(\langle\tilde{g}_{t},u-\theta_{k}\rangle+\frac{\alpha}{2}\|u-\theta_{k}\|^{2})+D_{\psi}(u,\theta_{0})\\}$.

16:end for

17:Output: The sequence of parameter vectors
$\\{\hat{\theta}_{t}\\}_{t=1}^{\infty}$.

To analyze the convergence behavior of RDGD-SC, we also apply the approximate
duality gap technique used in Section III. For the sake of brevity, we only
emphasize the parts that are different from Section III in this section. For
the lower bound $L_{t}$, exploiting strongly convexity instead of regular
convexity, we redefine it as

$\displaystyle
L_{t}\coloneq\frac{1}{H_{t}}\Big{\\{}\sum_{k=1}^{t}\eta_{k}L(\theta_{k})$
$\displaystyle-\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k}-\nabla
L(\theta_{k}),\theta^{*}-\theta_{k}\rangle$ $\displaystyle-
D_{\psi}(\theta^{*},\theta_{0})+\min_{u\in\Theta}h_{t}(u)\Big{\\}}$

where $h_{t}$ is also redefined as

$h_{t}(u)\coloneq\sum_{k=1}^{t}\eta_{k}\Big{(}\langle\tilde{g}_{k},u-\theta_{k}\rangle+\frac{\alpha}{2}\|u-\theta_{k}\|_{2}^{2}\Big{)}+D_{\psi}(u,\theta_{0}).$
(11)

The template for our analysis is similar to that in the smooth case. The
following definitions are identical, starting with
$\theta_{t+1}=\mathrm{argmin}_{u\in\Theta}h_{t}(u)$ and $G_{t}=U_{t}-L_{t}$.
Additionally, we need to track the change of
$E_{t}=H_{t}G_{t}-H_{t-1}G_{t-1}$, which leads to
$G_{t}=\frac{H_{1}}{H_{t}}G_{1}+\frac{\sum_{k=2}^{t}E_{k}}{H_{t}}$. The
following lemma bounds $H_{1}G_{1}$ and its proof is provided in Appendix D.

###### Lemma 3

Let $\psi(x)=\frac{\eta_{1}\alpha}{2}\|x\|_{2}^{2}$, the following holds:

$H_{1}G_{1}\leqslant\frac{\eta_{1}\alpha}{2}\|\theta^{*}-\theta_{1}\|_{2}^{2}+\eta_{1}\langle\tilde{g}_{1}-\nabla
L(\theta_{1}),\theta^{*}-\theta_{2}\rangle+\frac{\eta_{1}M^{2}}{4\alpha}.$

The following lemma bounds $h_{t}(\theta_{t+1})-h_{t-1}(\theta_{t})$ and
serves to track the change of the lower bound $L_{t}$. Its proof is provided
in Appendix E.

###### Lemma 4

Let $\psi(x)=\frac{\eta_{1}\alpha}{2}\|x\|_{2}^{2}$. For all $t\geqslant 1$,

$h_{t}(\theta_{t+1})-h_{t-1}(\theta_{t})\geqslant\eta_{t}\langle\tilde{g}_{t},\theta_{t+1}-\theta_{t}\rangle\\\
+\frac{(H_{t}+\eta_{t})\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}.$

Finally, the following lemma whose proof is provided in Appendix F provides a
bound of $H_{t}G_{t}-H_{t-1}G_{t-1}$.

###### Lemma 5

Let $\psi(x)=\frac{\eta_{1}\alpha}{2}\|x\|_{2}^{2}$ and
$0\leqslant\frac{\eta_{t}}{H_{t}}\leqslant\frac{\alpha}{M}$. Then, for all
$t\geqslant 1$,

$H_{t}G_{t}-H_{t-1}G_{t-1}\leqslant\eta_{t}\langle\tilde{g}_{t}-\nabla
L(\theta_{t}),\theta^{*}-\theta_{t+1}\rangle+\frac{\eta_{t}M^{2}}{2\alpha}.$

Equipped with these preliminary results, the convergence rate of RDGD-SC can
be quantified as follows.

###### Theorem 2

Let $0<\alpha\leqslant M<\infty$ be such that for all
$(x,y)\in\mathbb{R}^{p}\times\mathbb{R}$, $\ L(x,y;\cdot)$ is $M$-smooth and
$\alpha$-strongly convex. let $\theta_{0}\in\Theta$ be an arbitrary initial
point. Let $\\{(\theta_{t},z_{t},\hat{\theta}_{t})\\}_{t=1}^{T}$ evolve
according to RDGD-SC (Algorithm 2) for
$\psi(x)=\frac{\eta_{1}\alpha}{2}\|x\|_{2}^{2}$. Set
$R_{\Theta}=\max_{\theta\in\Theta}\|\theta-\theta^{*}\|_{2}$. Let $\eta_{1}=1$
and $\eta_{k}$ satisfy $\eta_{k}\leqslant\frac{\alpha}{M}H_{k}$ for all
$k\geqslant 2$. Then for all $t\geqslant 2$:

$\displaystyle\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]$
$\displaystyle\leqslant\Big{(}\prod_{k=2}^{t}\big{(}1-\frac{\eta_{k}}{H_{k}}\big{)}\Big{)}\frac{\alpha}{2}\|\theta^{*}-\theta_{0}\|_{2}^{2}+\frac{M^{2}}{2\alpha}$
$\displaystyle+\frac{R_{\Theta}C(t)}{m}\cdot\frac{\sqrt{\sum_{k=1}^{t}\eta_{k}^{2}}}{H_{t}}+(M+1)\sqrt{p}\sigma
R_{\Theta}.$ (12)

###### Proof:

We write $G_{t}=\frac{H_{1}}{H_{t}}G_{1}+\frac{\sum_{k=2}^{t}E_{k}}{H_{t}}$ as

$\displaystyle G_{t}$
$\displaystyle=\frac{H_{1}}{H_{2}}\frac{H_{2}}{H_{3}}\dotsm\frac{H_{t-1}}{H_{t}}G_{1}+\frac{\sum_{k=2}^{t}E_{k}}{H_{t}}$
$\displaystyle=\Big{(}1-\frac{\eta_{2}}{H_{2}}\Big{)}\Big{(}1-\frac{\eta_{3}}{H_{3}}\Big{)}\ldots\Big{(}1-\frac{\eta_{t}}{H_{t}}\Big{)}G_{1}+\frac{\sum_{k=2}^{t}E_{k}}{H_{t}}.$

The remaining parts of the proof are essentially the same as those for Theorem
1. ∎

Observe that we have the flexibility of setting different stepsize sequences
$\\{\eta_{k}\\}_{k=1}^{\infty}$ to achieve different convergence rates in
(12). Motivated by this observation, we derive the following corollary of
Theorem 2. The proof is presented in Appendix G.

###### Corollary 1

(of Theorem 2). For $k\geqslant 2$, setting

  * •

$\eta_{k}=\frac{\alpha}{M}H_{k}$, we have

$\displaystyle\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]$
$\displaystyle\leqslant\Big{(}1-\frac{\alpha}{M}\Big{)}^{t-1}\frac{\alpha}{2}\|\theta^{*}-\theta_{0}\|_{2}^{2}+\frac{M^{2}}{2\alpha}$
$\displaystyle+\frac{R_{\Theta}C(t)}{m}+(M\\!+\\!1)\sqrt{p}\sigma R_{\Theta}.$
(13)

  * •

$\eta_{k}=\frac{2}{k+1}H_{k}$, we have

$\displaystyle\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]$
$\displaystyle\leqslant
O\Big{(}\frac{\|\theta^{*}-\theta_{0}\|_{2}^{2}}{t^{2}}+\frac{1}{\sqrt{t}}\cdot\frac{R_{\Theta}C(t)}{m}\Big{)}$
$\displaystyle\quad+\frac{M^{2}}{2\alpha}+(M+1)\sqrt{p}\sigma R_{\Theta}.$
(14)

If we set $\eta_{k}=\frac{\alpha}{M}H_{k}$ (the first case in Corollary 1), we
notice that the leading term
$\left(1-\frac{\alpha}{M}\right)^{t-1}\frac{\alpha}{2}\|\theta^{*}-\theta_{0}\|_{2}^{2}$
resembles the convergence behavior typically observed in the analysis of
smooth and strongly convex functions, in scenarios without corruption and
noise [30]. This term decays exponentially fast as $t$ grows. However, there
is an additional term of the form $\frac{R_{\Theta}C(t)}{m}$ that represents
the effect of the corruption and does not vanish with $t$. Alternatively, if
we set $\eta_{k}=\frac{2}{k+1}H_{k}$ (the second case of Corollary 1), the
leading term vanishes at a slower rate of $t^{-2}$ but the corruption term
vanishes at a rate $\frac{C(t)}{m\sqrt{t}}$. This naturally begs the question
of whether we can design a “best of both worlds” algorithm to exploit the
benefits of both settings of the stepsize $\eta_{k}$ to accelerate the overall
convergence.

##  V Corruption Reduction by Exploiting the Best of Both Worlds

Based on the results from Section IV, we observe that for certain natural
choices of the stepsize such as $\eta_{k}=\frac{\alpha}{M}H_{k}$ with
$H_{k}=\sum_{\ell=1}^{k}\eta_{\ell}$, the adversarial corruption results in
the upper bound on the suboptimality gap in (13) stagnating at a positive,
non-vanishing constant. This is clearly undesirable. In this section, we
explore how to mitigate this corruption accumulation by proposing an algorithm
that switches the stepsize schedule at an appropriate transition time. The
main idea is to first exploit the exponential decrease of the expected
suboptimality gap by setting $\eta_{k}=\frac{\alpha}{M}H_{k}$ until the
corruption accumulation begins to dominate the convergence behavior. At this
point, we switch to a different stepsize schedule (i.e.,
$\eta_{k}=\frac{2}{k+1}H_{k}$), allowing the corruption to be gradually
amortized and thus enabling the hybrid algorithm to further reduce the
suboptimality gap as $t$ grows.

In this section, for clarity, we specify the total corruption budget as
$C(t)=mt^{r}$ for some fixed $r\in(0,1/2)$. We observe from (13) that the
suboptimality gap initially decreases and then increases due to the
accumulation of the corruption $C(t)$ when we set
$\eta_{k}=\frac{\alpha}{M}H_{k}$. Hence, we determine the optimal transition
time $t_{0}$ corresponding to the point where the minimum upper bound of
suboptimality gap is achieved. The proof of the following lemma is provided in
Appendix H.

###### Lemma 6

If $\eta_{k}=\frac{\alpha}{M}H_{k}$, the minimum of the upper bound of
$\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]$ in (13) with respect to
$t\in\mathbb{N}$ is attained at

$t_{0}=\Big{\lceil}-\frac{(1-r)M}{\alpha}W_{-1}\big{(}B(r)\big{)}\Big{\rceil},$
(15)

where
$B(r):=-\frac{\alpha}{(1-r)M}\big{(}\frac{2Mr}{\alpha^{2}R_{\Theta}\exp(\alpha/M)}\big{)}^{\frac{1}{1-r}}$,
and $W_{-1}$ denotes the Lambert W function, i.e., the inverse of
$f(w)=we^{w}$.

Note from Lemma 6 that the transition time $t_{0}$ can be analytical
determined based on known parameters of the problem such as $M$, $\alpha$, and
$R_{\Theta}$. Inspired by Lemma 6, we propose the Algorithm 3 that is based on
RDGD but with a novel restart mechanism (RDGD-Restart). RDGD-Restart exploits
the exponential decrease in the suboptimality gap until the effect of the
accumulation of the corruption starts to dominate the overall bound in (13).
To mitigate this, we then switch to a stepsize sequence that decays more
slowly to prevent excessive corruption accumulation. This then leads to the
bound in (14) dominating the overall convergence behavior subsequently.

Algorithm 3 Distributed Gradient Descent Algorithm Robust to Corruptions over
Noisy Channels with Restart (RDGD-Restart)

1:Initialization: Parameter vector $\theta_{0}\in\Theta$, $\eta_{1}=1$, dual
vector $z_{0}=\nabla\psi(\theta_{0})$ with
$\psi(x)=\frac{\alpha}{2}\|x\|_{2}^{2}$, $\theta_{1}=\theta_{0}$ and
$\hat{\theta}_{0}=\theta_{0}$ (defined in (15)).

2:Stage 1: Run RDGD-SC (Algorithm 2) with $\eta_{k}=\frac{\alpha}{M}H_{k}$
from $k\geqslant 2$. Terminate when $k=t_{0}$.

3:Stage 2: Restart RDGD-SC taking $\theta_{t_{0}}$ as the initial point and
change the stepsize to $\eta_{k}=\frac{2}{k+1}H_{k}$ for all $k\geqslant
t_{0}+1$.

4:Output: The parameter vector $\hat{\theta}_{t}$.

We now bound the suboptimality gap
$\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]$ of RDGD-Restart. The proof is
presented in Appendix I.

###### Theorem 3

Under the same setting as Theorem 2 and when corruption budget is paramterized
as $C(t)=mt^{r}$ for $r\in(0,1/2)$, for all $t>t_{0}$ (defined in (15)), the
convergence rate of RDGD-Restart in Algorithm 3 is:

$\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]\leqslant\frac{\alpha}{2}\Big{(}1-\frac{\alpha}{M}\Big{)}^{t_{0}-1}\frac{t_{0}(t_{0}+1)}{t(t+1)}\|\theta^{*}-\theta_{0}\|_{2}^{2}\\\
+R_{\Theta}t^{r}\cdot A(t,t_{0})+\frac{M^{2}}{2\alpha}+(M+1)\sqrt{p}\sigma
R_{\Theta},$

where
$A(t,t_{0})\coloneq\sqrt{\left(\frac{t_{0}(t_{0}+1)}{t(t+1)}\right)^{2}\\!+\\!\left(\frac{2}{t(t+1)}\right)^{2}\sum_{k=t_{0}+1}^{t}k^{2}}$.

As $t\to\infty$, $A(t,t_{0})$ decays as $O(1/\sqrt{t})$. We observe from the
first term of the bound that in the initial rounds (when $t\leqslant t_{0}$),
the suboptimality gap decays rapidly due to the exponentially decaying term
with contraction factor $1-\frac{\alpha}{M}$. When $t>t_{0}$, we observe from
the second term that the effect of the corruption is amortized because $r<1/2$
and $A(t,t_{0})=O(1/\sqrt{t})$.

##  VI Numerical Experiments

In this section, we illustrate the performance of RDGD and its variants
through several numerical experiments, including least squares regression and
support vector machine (SVM) classification on synthetically generated
datasets, and softmax classification on the MNIST handwritten digits dataset
[31]. We compare our proposed algorithms with the vanilla distributed gradient
descent (DGD) algorithm, i.e., the parameter vector is simply updated as
$\theta_{t+1}=\theta_{t}-\eta_{t}\tilde{g}_{t}$ at the $t$-th iteration. Note
that DGD does not attempt to correct for the presence of corruptions; hence,
we expect that it is not robust.

###  VI-A Least Squares Regression on Synthetic Datasets

We start with least squares regression on synthetic datasets. The datasets
contain $N=10,000$ data samples. In particular, the loss function of the
least-squares regression is as
$L(x,y;\theta)=\frac{1}{2}(x^{\top}\theta-y)^{2}$ where
$\theta\in\mathbb{R}^{p}$ is the parameter vector with dimensionality $p=20$.
Then, the loss function computed over the entire dataset $\mathcal{Z}$ is
$L(\theta)=\frac{1}{2N}\sum_{i=1}^{N}(x_{i}^{\top}\theta-y_{i})^{2}$. We
consider one parameter server and $m=20$ workers.

Each element of the feature vectors $x_{i}$ is drawn from the standard
Gaussian distribution $\mathcal{N}(0,1)$. We also randomly generate each
dimension of the unknown parameter $\theta^{*}$ from $\mathcal{N}(0,1)$. The
scalar responses $y_{i}$ are obtained by taking the inner product of the
feature vectors $x_{i}$ and the unknown parameter $\theta^{*}$, followed by
adding standard Gaussian noise $\mathcal{N}(0,1)$. These data samples are then
uniformly distributed to all $20$ workers. We set the variances of the
Gaussian noise in both downlink and uplink channels to $\sigma^{2}=0.5$.

The performance metric is the suboptimality gap
$\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]$. The results reported are
averaged over 100 independent trials. We also report the standard deviations
across these 100 experiments. The bound of the total corruption until time $t$
is set to $C(t)=20t^{0.4}$. As it is difficult to find the worst case
corruption pattern, we use the following procedure as a proxy to generate the
corruption $\varepsilon_{i,t}$ at each worker $i\in[m]$ and at each time $t$.
In particular, let $\Gamma(\tau)=\sum_{k=1}^{\tau}c(k)^{2}$ denote the
corruption budget used up to time and including $n$. Then, the available
corruption budget at time $t$ is $\sqrt{C(t)^{2}-\Gamma(t-1)}$. Then, we
distribute this available corruption budget to each worker randomly. The sign
of adversarial corruption at each worker
$\operatorname{sign}(\varepsilon_{i,t})$ is set to
$-\operatorname{sign}(\tilde{g}_{i,t})$ for all $i\in[m]$. Also, the stepsize
is set to $\eta_{t}=t^{-2}$.

Figure 3: Performances of RDGD and DGD for least squares regression

Let $X\in\mathbb{R}^{N\times p}$ be the matrix where each row contains the
feature vector $x_{i}^{\top}$. Define $\lambda_{\mathrm{max}}(Q)$ and
$\lambda_{\mathrm{min}}(Q)$ as the maximum and minimum eigenvalues of the
matrix $Q$ respectively. We run RDGD (Algorithm 1) with the function
$\psi(x)=\frac{M}{2}\|x\|_{2}^{2}$, where
$M=\lambda_{\mathrm{max}}(\frac{1}{N}X^{\top}X)$. As shown in Fig. 3, our
proposed algorithm achieves a significantly smaller suboptimality gap more
quickly and consistently compared to the traditional DGD algorithm.

Next, we verify the efficacy of the restart mechanism RDGD-Restart (in
Algorithm 3) when the loss function is smooth and strongly convex. In
particular, we modify the loss function of least-squares regression by adding
an $\ell_{2}$-squared regularization term, i.e.,
$L(x,y;\theta)=\frac{1}{2}(x^{\top}\theta-y)^{2}+\frac{\lambda}{2}\|\theta\|_{2}^{2}$,
where we set $\lambda=0.01$. Now, we run RDGD-Restart for this strongly convex
loss function. We set the strongly convex parameter as
$\alpha=\lambda_{\mathrm{min}}(\frac{1}{N}X^{\top}X+\lambda\mathbf{I}_{p})$
and the smooth parameter as
$M=\lambda_{\mathrm{max}}(\frac{1}{N}X^{\top}X+\lambda\mathbf{I}_{p})$
respectively. The variance of the Gaussian noises in the uplink and downlink
is set to $\sigma^{2}=0.1$. The function
$\psi(x)=\frac{\alpha}{2}\|x\|_{2}^{2}$.

Figure 4: Comparison of the performances of RDGD-SC with different stepsizes
$\\{\eta_{k}\\}$ to RDGD-Restart

As shown in Fig. 4, if one chooses the stepsize sequence
$\eta_{k}=\frac{\alpha}{M}H_{k}$, the adversarial corruption accumulates after
a certain point, resulting in a stagnation of the suboptimality gap. However,
it is also worth noting that the gap decreases much more rapidly when
$\eta_{k}=\frac{\alpha}{M}H_{k}$ compared to when
$\eta_{k}=\frac{2}{k+1}H_{k}$ initially. In our proposed algorithm with a
restart mechanism RDGD-Restart, the gap decreases rapidly until a transition
time $t_{0}$ which can be determined analytically. After the time $t_{0}+1$,
we switch the stepsize sequence from $\eta_{k}=\frac{\alpha}{M}H_{k}$ to
$\eta_{k}=\frac{2}{k+1}H_{k}$. As can be seen, the gap subsequently decreases
with $t$. Our proposed algorithm RDGD-Restart converges faster than the
$\eta_{k}=\frac{2}{k+1}H_{k}$ case throughout the entire process, indicating a
smaller time complexity to achieve the same suboptimality gap. The
experimental results presented in Fig. 4 thus corroborate our theoretical
analysis in Section V. Hence, our proposed algorithm with a restart mechanism
RDGD-Restart successfully takes advantage of the exponential decrease in the
gap until corruption accumulation occurs, then mitigates the adverse effects
of the accumulation by switching to another stepsize sequence.

###  VI-B Classification using L2 Support Vector Machines

Next we verify the efficacy of RDGD on a binary classification task with a
loss function that is different from that used in the previous section.
Specifically, we consider L2-SVM222We consider L2-SVM instead of the usual
L1-SVM since the loss function is smooth for the former. [32, 33] and we use
the accuracy of the binary classification task as our performance metric. The
label $y_{i}$ is generated such that it takes values from the set $\\{1,-1\\}$
with equal probability. For each $y_{i}$, the corresponding feature vector
$x_{i}$ is generated from a multivariate normal distribution. If $y_{i}=1$,
$x_{i}$ is drawn from $\mathcal{N}(\bm{\mu},\gamma\mathbf{I}_{p})$, and if
$y_{i}=-1$, $x_{i}$ is drawn from
$\mathcal{N}(-\bm{\mu},\gamma\mathbf{I}_{p})$, where $\bm{\mu}$ is the vector
of all ones of length $p$ and $\gamma=4$.

We generated $N=10,000$ data samples which are then split into $8,000$ samples
for training and $2,000$ samples for testing. The primal objective function
used in L2-SVM is
$L(x,y;\theta)=\max\\{0,1-y(x^{\top}\theta)\\}^{2}+\frac{\lambda}{2}\|\theta\|_{2}^{2}$,
where $\lambda$ is set to $0.1$. We compare RDGD with vanilla DGD under
varying levels of corruption budgets $C(T)$, with a fixed noise variance
$\sigma^{2}=1$ in the (uplink and downlink) communication channels.
Specifically, the total corruption bound up to time $T$ is set as
$C(T)=20T^{r}$, where $r\in\\{0.25,0.3,0.35\\}$. The total corruption budget
is uniformly allocated to each iteration and worker, i.e.,
$c(t)=C(T)/\sqrt{T}$, for all $t\in[T]$.

Figure 5: RDGD for L2-SVM classification

As shown in Fig. 5, the proposed RDGD converges rapidly and achieves high
accuracy at any level of the corruption budget. However, the accuracy of the
classification of the vanilla DGD algorithm is lower than RDGD and is highly
sensitive to the level of the corruption budget. In particular, the
performance of DGD fails when the corruption budget exceeds a certain level
(e.g., $r=0.35$). In Fig. 6, we display the decision boundaries for the first
two dimensions of the parameter vectors $\hat{\theta}_{\rm{RDGD}}$ and
$\hat{\theta}_{\rm{DGD}}$ obtained by RDGD and DGD respectively when $r=0.35$.
Note that $\hat{\theta}_{\rm{RDGD}}$ is almost identical to $\theta^{*}$.
However, $\hat{\theta}_{\rm{DGD}}$ deviates significantly from $\theta^{*}$,
showing that DGD is far from robust.

Figure 6: Decision Boundaries for L2-SVM classification

###  VI-C Softmax Classification on the MNIST Dataset

In our final set of experiments, we consider a multi-class classification task
on the classical MNIST dataset, which contains 10 classes (i.e., the number of
values that each label $y_{i}$ can take on is 10), 60,000 training samples and
10,000 test samples. The performance metric is the classification accuracy on
the test samples. The dimensionality $p$ of the data points is $784=28\times
28$ and the number of workers $m$ is set to $20$. We use the cross-entropy
loss to optimize the softmax classifier.

Figure 7: RDGD for the MNIST dataset with different levels of corruption

In Fig. 7, we compare RDGD with vanilla DGD under varying levels of corruption
budgets $C(T)$, with a fixed noise variance $\sigma^{2}=0.5$ in the
communication channels. Specifically, the total corruption bound up to time
$T$ is set as $C(T)=100T^{r}$, where $r\in\\{0.2,0.3,0.4\\}$. The total
corruption budget is also uniformly allocated to each iteration and each
worker as in the previous subsection. As shown in Fig. 7, RDGD outperforms the
traditional DGD algorithm across all levels of the corruption budget.
Furthermore, we observe that RDGD achieves higher accuracy as the value of $r$
and hence, the amount of corruption, decreases. The vanilla DGD algorithm
reduces to random guessing (success rate $\approx 10\%$) when the corruption
budget exceeds a certain level (i.e., $r=0.4$).

##  VII Conclusion

In this paper, we considered a robustification of the standard distributed
gradient descent algorithm used extensively in the parallelization of massive
datasets in the modern era. In addition to standard channel noises on the
uplink and downlink of the communication channels, we also considered
mitigating the effects of adversarial corruptions at the workers via a mirror
descent-type algorithm RDGD and its strongly convex extension RDGD-SC.
Different convergence rates of the suboptimality gap were obtained by setting
different stepsizes in RDGD-SC. We also provided a theoretical analysis of a
unified algorithm RDGD-Restart that attains the “best-of-both-worlds” with
regard to the choice of the different stepsizes in RDGD-SC. Extensive
numerical experiments show that (i) RDGD performs much better, in terms of the
suboptimality gap and classification accuracy, than standard DGD in reducing
the effect of the corruption and (ii) the restarting mechanism in RDGD-Restart
is effective in speeding up the overall convergence rate for strongly convex
loss functions.

We may consider the following as avenues for future research. First, to model
the scenario in which some, but not all, workers are compromised, we may
redefine $c_{t}$ in (4) as $c_{t}=\sum_{i=1}^{m}\|\varepsilon_{i,t}\|_{2}$.
This encourages sparsity among the $\varepsilon_{i,t}$’s for fixed $t$.
Second, we may derive information-theoretic lower bounds on the suboptimality
gap in terms of the amount of corruption $C(T)$ to ascertain the tightness of
the upper bounds.

##  Appendix A Proof of Lemma 1

###### Proof:

By the definition of $h_{t}$ in (9), we have
$h_{t}(\theta_{t+1})-h_{t-1}(\theta_{t+1})\geqslant\eta_{t}\langle\tilde{g}_{t},\theta_{t+1}-\theta_{t}\rangle$.

Then, based on the definition of the Bregman divergence, we have
$h_{t-1}(\theta_{t+1})-h_{t-1}(\theta_{t})=\langle\nabla
h_{t-1}(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle+D_{h_{t-1}}(\theta_{t+1},\theta_{t})$
and $D_{h_{t-1}}(\theta_{t+1},\theta_{t})=D_{\psi}(\theta_{t+1},\theta_{t})$.
However, since $\theta_{t}=\mathrm{argmin}_{u\in\Theta}h_{t-1}(u)$, we have
$\langle\nabla h_{t-1}(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle\geqslant 0$.
Thus,

$\displaystyle
h_{t}(\theta_{t+1})-h_{t-1}(\theta_{t})\geqslant\eta_{t}\langle\tilde{g}_{t},\theta_{t+1}-\theta_{t}\rangle+D_{\psi}(\theta_{t+1},\theta_{t})$

as desired. ∎

##  Appendix B Proof of Lemma 2

###### Proof:

Based on Lemma 1, we have:

$\displaystyle H_{t}L_{t}-H_{t-1}L_{t-1}$
$\displaystyle\geqslant\eta_{t}L(\theta_{t})-\eta_{t}\langle\tilde{g}_{t}-L(\theta_{t}),\theta^{*}-\theta_{t}\rangle$
$\displaystyle\qquad+\eta_{t}\langle\tilde{g}_{t},\theta_{t+1}-\theta_{t}\rangle+D_{\psi}(\theta_{t+1},\theta_{t})$
$\displaystyle=\eta_{t}L(\theta_{t})-\eta_{t}\langle\tilde{g}_{t}-L(\theta_{t}),\theta^{*}-\theta_{t+1}\rangle$
$\displaystyle\;+\eta_{t}\langle
L(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle+D_{\psi}(\theta_{t+1},\theta_{t}).$

Then, it follows that:

$H_{t}G_{t}-H_{t-1}G_{t-1}\leqslant
H_{t}L(\hat{\theta}_{t})-H_{t-1}L(\hat{\theta}_{t-1})-\eta_{t}L(\theta_{t})\\\
+\eta_{t}\langle\tilde{g}_{t}-L(\theta_{t}),\theta^{*}-\theta_{t+1}\rangle-\eta_{t}\langle
L(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle\\\
-D_{\psi}(\theta_{t+1},\theta_{t}).$

From RDGD in Algorithm 1 and the convexity of the loss function $L$, we can
write
$H_{t}L(\hat{\theta}_{t})-H_{t-1}L(\hat{\theta}_{t-1})-\eta_{t}L(\theta_{t})$
as:

$\displaystyle\eta_{t}L(\hat{\theta}_{t})+H_{t-1}(L(\hat{\theta}_{t})-L(\hat{\theta}_{t-1}))-\eta_{t}L(\theta_{t})$
$\displaystyle\leqslant\eta_{t}(L(\hat{\theta}_{t})-L(\theta_{t}))+H_{t-1}\langle\nabla
L(\hat{\theta}_{t}),\hat{\theta}_{t}-\hat{\theta}_{t-1}\rangle$
$\displaystyle=\eta_{t}(L(\hat{\theta}_{t})-L(\theta_{t}))-\eta_{t}\langle\nabla
L(\hat{\theta}_{t}),\hat{\theta}_{t}-\theta_{t}\rangle$
$\displaystyle\leqslant\eta_{t}\langle\nabla
L(\hat{\theta}_{t}),\hat{\theta}_{t}-\theta_{t}\rangle-\eta_{t}\langle\nabla
L(\hat{\theta}_{t}),\hat{\theta}_{t}-\theta_{t}\rangle$ $\displaystyle=0.$
(16)

Hence, we conclude that

$H_{t}G_{t}-H_{t-1}G_{t-1}\leqslant\eta_{t}\langle\tilde{g}_{t}-L(\theta_{t}),\theta^{*}-\theta_{t+1}\rangle\\\
-\eta_{t}\langle L(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle-
D_{\psi}(\theta_{t+1},\theta_{t})$

as desired. ∎

##  Appendix C Proof of Theorem 1

###### Proof:

Based on Lemma 2, we have

$H_{t}G_{t}-H_{t-1}G_{t-1}\leqslant\eta_{t}\langle\tilde{g}_{t}-L(\theta_{t}),\theta^{*}-\theta_{t+1}\rangle\\\
-\eta_{t}\langle L(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle-
D_{\psi}(\theta_{t+1},\theta_{t}).$

By the definition of the Bregman divergence and the $\mu$-strong convexity of
the function $\psi$, we have
$D_{\psi}(\theta_{t+1},\theta_{t})\geqslant\frac{\mu}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}$.
Hence,

$-\eta_{t}\langle L(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle-
D_{\psi}(\theta_{t+1},\theta_{t})\\\
\leqslant\eta_{t}M\|\theta_{t+1}-\theta_{t}\|_{2}-\frac{\mu}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}\leqslant\frac{\eta_{t}^{2}M^{2}}{2\mu},$

where the second inequality follows from the fact that $2ab-b^{2}\leqslant
a^{2}$.

Recall that
$g_{i,k}=\frac{1}{|\mathcal{Z}_{i}|}\sum_{(x,y)\in\mathcal{Z}_{i}}\nabla
L(x,y;\theta_{k})$. Hence, we can write $\nabla
L(\theta_{k})=\frac{1}{m}\sum_{i=1}^{m}g_{i,k}$ and

$\displaystyle\langle\tilde{g}_{k}-\nabla
L(\theta_{k}),\theta^{*}-\theta_{k+1}\rangle$
$\displaystyle\\!=\\!\bigg{\langle}\frac{1}{m}\Big{(}\\!\sum_{i=1}^{m}g^{\prime}_{i,t}\\!+\\!\sum_{i=1}^{m}\varepsilon_{i,t}\\!+\\!\sum_{i=1}^{m}w_{k}^{(i)}\Big{)}$
$\displaystyle\hskip
56.9055pt-\frac{1}{m}\\!\sum_{i=1}^{m}g_{i,t},\theta^{*}\\!-\\!\theta_{k+1}\bigg{\rangle}$
$\displaystyle=\frac{1}{m}\bigg{\langle}\\!\sum_{i=1}^{m}\\!g^{\prime}_{i,t}\\!-\\!\sum_{i=1}^{m}\\!g_{i,t},\theta^{*}\\!-\\!\theta_{k+1}\\!\bigg{\rangle}\\!+\\!\frac{1}{m}\bigg{\langle}\\!\sum_{i=1}^{m}\\!\varepsilon_{i,t},\theta^{*}\\!-\\!\theta_{k+1}\\!\bigg{\rangle}$
$\displaystyle\hskip
56.9055pt-\frac{1}{m}\bigg{\langle}\sum_{i=1}^{m}w_{k}^{(i)},\theta^{*}-\theta_{k+1}\bigg{\rangle}.$

Recall that $R_{\Theta}=\max_{\theta\in\Theta}\|\theta-\theta^{*}\|_{2}$. It
follows that

$\displaystyle\langle\tilde{g}_{k}-\nabla
L(\theta_{k}),\theta^{*}-\theta_{k+1}\rangle$ $\displaystyle\leqslant
MR_{\Theta}\|v_{k}^{(i)}\|_{2}+\frac{c_{k}R_{\Theta}}{m}+R_{\Theta}\|w_{k}^{(i)}\|_{2}.$
(17)

Then, we have

$\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k}-\nabla
L(\theta_{k}),\theta^{*}-\theta_{k+1}\rangle\\\
\leqslant\frac{R_{\Theta}}{m}\sum_{k=1}^{t}\eta_{k}c_{k}+MR_{\Theta}\sum_{k=1}^{t}\eta_{k}\|v_{k}^{(i)}\|_{2}+R_{\Theta}\sum_{k=1}^{t}\eta_{k}\|w_{k}^{(i)}\|_{2}.$
(18)

Taking the expectation on both sides of (18) and assuming
$\sigma^{2}_{k}\leqslant\sigma^{2}$ for all $k\geqslant 1$, we obtain

$\displaystyle\mathbb{E}\bigg{[}\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k}-\nabla
L(\theta_{k}),\theta^{*}-\theta_{k+1}\rangle\bigg{]}$
$\displaystyle\leqslant\frac{R_{\Theta}}{m}\langle\bm{\eta}_{t},\mathbf{c}_{t}\rangle\\!+\\!(M+1)\sqrt{p}\sigma
R_{\Theta}\sum_{k=1}^{t}\eta_{k},$ (19)

where $\bm{\eta}_{t}=[\eta_{1},\ldots,\eta_{t}]^{\top}$ and
$\mathbf{c}_{t}=[c_{1},\ldots,c_{t}]^{\top}$.

Since the overall bound on the total corruption up to and including time $t$
is $C(t)$ such that $\sqrt{\sum_{k=1}^{t}c_{k}^{2}}\leqslant C(t)$, by the
Cauchy–Schwarz inequality, we have

$\displaystyle\mathbb{E}\bigg{[}\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k}-\nabla
L(\theta_{k}),\theta^{*}-\theta_{k+1}\rangle\bigg{]}$
$\displaystyle\leqslant\frac{R_{\Theta}C(t)}{m}\sqrt{\sum_{k=1}^{t}\eta_{k}^{2}}+(M+1)\sqrt{p}\sigma
R_{\Theta}H_{t}.$ (20)

Next, we bound $H_{1}G_{1}$ as follows:

$\displaystyle H_{1}G_{1}=H_{1}U_{1}-H_{1}L_{1}$
$\displaystyle\leqslant-\eta_{1}\langle
L(\theta_{1}),\theta_{2}-\theta_{1}\rangle-
D_{\psi}(\theta_{2},\theta_{0})+D_{\psi}(\theta^{*},\theta_{0})$
$\displaystyle\qquad\qquad\qquad+\eta_{1}\langle\tilde{g}_{1}-\nabla
L(\theta_{1}),\theta^{*}-\theta_{2}\rangle$
$\displaystyle\leqslant\frac{\eta_{1}^{2}M^{2}}{2\mu}+D_{\psi}(\theta^{*},\theta_{0})+\eta_{1}\langle\tilde{g}_{1}-\nabla
L(\theta_{1}),\theta^{*}-\theta_{2}\rangle.$

Then, we conclude that

$\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]\leqslant\frac{D_{\psi}(\theta^{*},\theta_{0})}{H_{t}}+\frac{M^{2}}{2\mu}\cdot\frac{\sum_{k=1}^{t}\eta_{k}^{2}}{H_{t}}\\\
+\frac{R_{\Theta}C(t)}{m}\cdot\frac{\sqrt{\sum_{k=1}^{t}\eta_{k}^{2}}}{H_{t}}+(M+1)\sqrt{p}\sigma
R_{\Theta}.$

Recall that $T$ is the fixed and known number of iterations. Let
$\eta_{k}=\frac{1}{\sqrt{T}}$ for all $k\geqslant 1$. Finally we obtain the
desired bound as follows:

$\mathbb{E}[L(\hat{\theta}_{T})-L(\theta^{*})]\leqslant\frac{D_{\psi}(\theta^{*},\theta_{0})}{\sqrt{T}}+\frac{M^{2}}{2\mu}\cdot\frac{1}{\sqrt{T}}\\\
+\frac{R_{\Theta}C(T)}{m}\cdot\frac{1}{\sqrt{T}}+(M+1)\sqrt{p}\sigma
R_{\Theta}.$

∎

##  Appendix D Proof of Lemma 3

###### Proof:

The initial lower bound $L_{1}$ multiplied by $H_{1}$ can be expressed as

$H_{1}L_{1}=\eta_{1}L(\theta_{1})+\eta_{1}\langle\tilde{g}_{1},\theta_{2}-\theta_{1}\rangle+\Big{(}\frac{\eta_{1}\alpha}{2}+\frac{\alpha_{0}}{2}\Big{)}\|\theta_{2}-\theta_{1}\|_{2}^{2}\\\
-\frac{\mu_{0}}{2}\|\theta^{*}-\theta_{1}\|_{2}^{2}-\eta_{1}\langle\tilde{g}_{1}-\nabla
L(\theta_{1}),\theta^{*}-\theta_{1}\rangle.$

The corresponding upper bound $U_{1}$ multiplied by $H_{1}$ can be written as

$\displaystyle H_{1}U_{1}=\eta_{1}L(\hat{\theta}_{1})=\eta_{1}L(\theta_{1}).$

Then, we have

$\displaystyle H_{1}U_{1}-H_{1}L_{1}=H_{1}G_{1}$
$\displaystyle\leqslant\frac{\alpha_{0}}{2}\|\theta^{*}-\theta_{1}\|_{2}^{2}+\eta_{1}\langle\tilde{g}_{1}-\nabla
L(\theta_{1}),\theta^{*}-\theta_{2}\rangle$
$\displaystyle\qquad\quad-\eta_{1}\langle\nabla
L(\theta_{1}),\theta_{2}-\theta_{1}\rangle-\Big{(}\frac{\eta_{1}\alpha}{2}+\frac{\alpha_{0}}{2}\Big{)}\Big{\|}\theta_{2}-\theta_{1}\|_{2}^{2}$
$\displaystyle\leqslant\frac{\alpha_{0}}{2}\|\theta^{*}-\theta_{1}\|_{2}^{2}+\eta_{1}\langle\tilde{g}_{1}-\nabla
L(\theta_{1}),\theta^{*}-\theta_{2}\rangle+\frac{\eta_{1}^{2}M^{2}}{2(\eta_{1}\alpha\\!+\\!\alpha_{0})}$
$\displaystyle=\frac{\eta_{1}\alpha}{2}\|\theta^{*}-\theta_{1}\|_{2}^{2}+\eta_{1}\langle\tilde{g}_{1}-\nabla
L(\theta_{1}),\theta^{*}-\theta_{2}\rangle+\frac{\eta_{1}M^{2}}{4\alpha}$

as desired. ∎

##  Appendix E Proof of Lemma 4

###### Proof:

By the definition of $h_{t}$ in (11), we have
$h_{t}(\theta_{t+1})-h_{t-1}(\theta_{t+1})\geqslant\eta_{t}\langle\tilde{g}_{t},\theta_{t+1}-\theta_{t}\rangle+\frac{\eta_{t}\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}$.
Then, based on the definition of the Bregman divergence, we have

$h_{t-1}(\theta_{t+1})-h_{t-1}(\theta_{t})=\langle\nabla
h_{t-1}(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle\\\
+D_{h_{t-1}}(\theta_{t+1},\theta_{t}).$

Since $\theta_{t}=\mathrm{argmin}_{u\in\Theta}h_{t-1}(u)$, we have
$\langle\nabla h_{t-1}(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle\geqslant 0$.
Then:

$\displaystyle h_{t-1}(\theta_{t+1})-h_{t-1}(\theta_{t})$
$\displaystyle\geqslant D_{h_{t-1}}(\theta_{t+1},\theta_{t})$
$\displaystyle=\frac{H_{t-1}\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}+\frac{\eta_{1}\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}$
$\displaystyle=\frac{H_{t}\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}$

as desired. ∎

##  Appendix F Proof of Lemma 5

###### Proof:

From Lemma 4, we have

$\displaystyle H_{t}L_{t}-H_{t-1}L_{t-1}$
$\displaystyle\geqslant\eta_{t}L(\theta_{t})+\eta_{t}\langle\tilde{g}_{t},\theta_{t+1}-\theta_{t}\rangle+\frac{(H_{t}+\eta_{t})\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}$
$\displaystyle\qquad\qquad\qquad-\eta_{t}\langle\tilde{g}_{t}-\nabla
L(\theta_{t}),\theta^{*}-\theta_{t}\rangle$
$\displaystyle=\eta_{t}L(\theta_{t})\\!+\\!\eta_{t}\langle\nabla
L(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle\\!+\\!\frac{(H_{t}\\!+\\!\eta_{t})\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}$
$\displaystyle\qquad\qquad-\eta_{t}\langle\tilde{g}_{t}-\nabla
L(\theta_{t}),\theta^{*}-\theta_{t+1}\rangle.$

Then, we have

$H_{t}G_{t}-H_{t-1}G_{t-1}\leqslant
H_{t}L(\hat{\theta}_{t})-H_{t-1}L(\hat{\theta}_{t-1})\\\
-\eta_{t}L(\theta_{t})-\eta_{t}\langle\nabla
L(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle-\\!\frac{(H_{t}\\!+\\!\eta_{t})\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}\\\
+\eta_{t}\langle\tilde{g}_{t}-\nabla
L(\theta_{t}),\theta^{*}-\theta_{t+1}\rangle.$ (21)

Combining the fact that
$\hat{\theta}_{t}=\frac{H_{t-1}}{H_{t}}\hat{\theta}_{t-1}+\frac{\eta_{t}}{H_{t}}\theta_{t}$
and (B), we have
$H_{t}L(\hat{\theta}_{t})-H_{t-1}L(\hat{\theta}_{t-1})-\eta_{t}L(\theta_{t})\leqslant
0$. Hence, we may rewrite the right-hand side of (21) as follows

$\eta_{t}(L(\theta_{t+1})-L(\theta_{t}))-\eta_{t}\langle\nabla
L(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle\\\
-\\!\frac{H_{t}\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}+\eta_{t}(L(\theta_{t})-L(\theta_{t+1}))-\\!\frac{\eta_{t}\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}\\\
+\eta_{t}\langle\tilde{g}_{t}-\nabla
L(\theta_{t}),\theta^{*}-\theta_{t+1}\rangle.$

Combining the fact that $\frac{\eta_{t}}{H_{t}}\leqslant\frac{\alpha}{M}$ and
the $M$-smoothness of $L$, we obtain

$\displaystyle\eta_{t}\left(L(\theta_{t+1})\\!-\\!L(\theta_{t})\\!-\\!\langle\nabla
L(\theta_{t}),\theta_{t+1}\\!-\\!\theta_{t}\rangle\right)\\!-\\!\frac{H_{t}\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}$
$\displaystyle\leqslant\frac{\eta_{t}M}{2}\|\theta_{t+1}\\!-\\!\theta_{t}\|_{2}^{2}-\\!\frac{H_{t}\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}=0.$
(22)

By the convexity of $L$ and the Cauchy–Schwartz inequality,

$\displaystyle\eta_{t}(L(\theta_{t})-L(\theta_{t+1}))-\\!\frac{\eta_{t}\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}$
$\displaystyle\leqslant-\eta_{t}\langle\nabla
L(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle-\\!\frac{\eta_{t}\alpha}{2}\|\theta_{t+1}-\theta_{t}\|_{2}^{2}$
$\displaystyle\leqslant\frac{\eta_{t}M^{2}}{2\alpha}.$ (23)

Combining (21), (F) and (F), we conclude that

$H_{t}G_{t}\leqslant H_{t-1}G_{t-1}+\eta_{t}\langle\tilde{g}_{t}-\nabla
L(\theta_{t}),\theta^{*}-\theta_{t+1}\rangle+\frac{\eta_{t}M^{2}}{2\alpha}$

as desired. ∎

##  Appendix G Proof of Corollary 1

###### Proof:

When $\frac{\eta_{t}}{H_{t}}=\frac{\alpha}{M}$, we write
$G_{t}=\frac{H_{1}}{H_{t}}G_{1}+\frac{\sum_{k=2}^{t}E_{k}}{H_{t}}$ as

$\displaystyle G_{t}$
$\displaystyle=\frac{H_{1}}{H_{2}}\frac{H_{2}}{H_{3}}\dotsm\frac{H_{t-1}}{H_{t}}G_{1}+\frac{\sum_{k=2}^{t}E_{k}}{H_{t}}$
$\displaystyle=\Big{(}1-\frac{\eta_{2}}{H_{2}}\Big{)}\Big{(}1-\frac{\eta_{3}}{H_{3}}\Big{)}\dotsm\Big{(}1-\frac{\eta_{t}}{H_{t}}\Big{)}G_{1}+\frac{\sum_{k=2}^{t}E_{k}}{H_{t}}$
$\displaystyle=\Big{(}1-\frac{\alpha}{M}\Big{)}^{t-1}G_{1}+\frac{\sum_{k=2}^{t}E_{k}}{H_{t}}$

From Lemmas 3 and 5, it follows that

$G_{t}=\Big{(}1-\frac{\alpha}{M}\Big{)}^{t-1}\frac{\alpha}{2}\|\theta^{*}-\theta_{0}\|_{2}^{2}+\frac{M^{2}\sum_{k=1}^{t}\eta_{k}}{2\alpha
H_{t}}\\\ +\frac{\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k}-\nabla
L(\theta_{k}),\theta^{*}-\theta_{k+1}\rangle}{H_{t}}$

By (20), we obtain the following sequence of upper bounds on the expectation
of the final term above:

$\displaystyle\mathbb{E}\bigg{[}\frac{\sum_{k=1}^{t}\eta_{k}\langle\tilde{g}_{k}-\nabla
L(\theta_{k}),\theta^{*}-\theta_{k+1}\rangle}{H_{t}}\bigg{]}$
$\displaystyle=\frac{R_{\Theta}C(t)}{m}\frac{\sqrt{\sum_{k=1}^{t}\eta_{k}^{2}}}{H_{t}}+(M+1)\sqrt{p}\sigma
R_{\Theta}$
$\displaystyle=\frac{R_{\Theta}C(t)}{m}\sqrt{\frac{{\sum_{k=1}^{t}\eta_{k}^{2}}}{H_{t}^{2}}}+(M+1)\sqrt{p}\sigma
R_{\Theta}$
$\displaystyle=\frac{R_{\Theta}C(t)\alpha}{mM}\sqrt{\frac{\sum_{k=1}^{t}H_{k}^{2}}{H_{t}^{2}}}+(M+1)\sqrt{p}\sigma
R_{\Theta}$
$\displaystyle=\frac{R_{\Theta}C(t)\alpha}{mM}\sqrt{\Big{(}\frac{H_{1}}{H_{t}}\Big{)}^{2}+\ldots+\Big{(}\frac{H_{t}}{H_{t}}\Big{)}^{2}}+(M+1)\sqrt{p}\sigma
R_{\Theta}$
$\displaystyle\leqslant\frac{R_{\Theta}C(t)\alpha}{mM}\sqrt{\frac{1-(1-\frac{\alpha}{M})^{2(t-1)}}{1-(1-\frac{\alpha}{M})^{2}}}+(M+1)\sqrt{p}\sigma
R_{\Theta}$
$\displaystyle\leqslant\frac{R_{\Theta}C(t)}{m}+(M+1)\sqrt{p}\sigma
R_{\Theta}.$

Therefore, we conclude that:

$\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]\leqslant\Big{(}1-\frac{\alpha}{M}\Big{)}^{t-1}\frac{\alpha}{2}\|\theta^{*}-\theta_{0}\|_{2}^{2}+\frac{M^{2}}{2\alpha}\\\
+\frac{R_{\Theta}C(t)}{m}+(M+1)\sqrt{p}\sigma R_{\Theta}.$

When $\eta_{k}=\frac{2}{k+1}H_{k}$, the result of Case 2 follows by
substituting this new choice of stepsize into Theorem 2. ∎

##  Appendix H Proof of Lemma 6

###### Proof:

We obtain the following inequality by substituting $C(t)=mt^{r}$ into the
general bound for the smooth and strongly convex case in (12)

$\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]\leqslant\Big{(}1-\frac{\alpha}{M}\Big{)}^{t-1}\frac{\alpha}{2}\|\theta^{*}-\theta_{0}\|_{2}^{2}+\frac{M^{2}}{2\alpha}\\\
+R_{\Theta}t^{r}+(M+1)\sqrt{p}\sigma R_{\Theta}.$

From the fact that $\|\theta^{*}-\theta_{0}\|_{2}^{2}\leqslant
R_{\Theta}^{2}$, we can simplify the above upper bound of
$\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]$ as follows

$\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]\leqslant\frac{\alpha
R_{\Theta}^{2}}{2}e^{-\frac{\alpha}{M}(t-1)}+\frac{M^{2}}{2\alpha}\\\
+R_{\Theta}t^{r}+(M+1)\sqrt{p}\sigma R_{\Theta}.$ (24)

We take the derivative of the upper bound in (24) with respect to $t$ and set
the derivative to be zero as follows:

$-\frac{\alpha^{2}R_{\Theta}^{2}}{2M}e^{-\frac{\alpha}{M}(t-1)}+\frac{r\cdot
R_{\Theta}}{t^{1-r}}=0.$ (25)

Then, we can rewrite (25) as

$\displaystyle te^{-\frac{\alpha}{(1-r)M}t}$
$\displaystyle=\left(\frac{2Mr}{\alpha^{2}R_{\Theta}\exp(\alpha/M)}\right)^{\frac{1}{1-r}}.$

Let $x=-\frac{\alpha}{(1-r)M}t$, we have

$xe^{x}=-\frac{\alpha}{(1-r)M}\left(\frac{2Mr}{\alpha^{2}R_{\Theta}\exp(\alpha/M)}\right)^{\frac{1}{1-r}}=:B(r).$

Therefore, we can obtain the solution $t_{0}$ by introducing the Lambert $W$
function $W_{-1}$ as follows:

$t_{0}=\left\lceil-\frac{(1-r)M}{\alpha}W_{-1}\left(B(r)\right)\right\rceil.$

∎

##  Appendix I Proof of Theorem 3

###### Proof:

Substituting $C(t)=mt^{r}$ into (12), we obtain

$\mathbb{E}[L(\hat{\theta}_{t})-L(\theta^{*})]\leqslant\Big{(}\prod_{k=2}^{t}(1-\frac{\eta_{k}}{H_{k}})\Big{)}\frac{\alpha}{2}\|\theta^{*}-\theta_{0}\|_{2}^{2}+\frac{M^{2}}{2\alpha}\\\
+R_{\Theta}t^{r}\cdot\frac{\sqrt{\sum_{k=1}^{t}\eta_{k}^{2}}}{H_{t}}+(M+1)\sqrt{p}\sigma
R_{\Theta}.$

We now decompose the factor $\prod_{k=2}^{t}(1-\frac{\eta_{k}}{H_{k}})$ as
follows:

$\displaystyle\prod_{k=2}^{t}(1-\frac{\eta_{k}}{H_{k}})$
$\displaystyle=\bigg{(}\prod_{k=2}^{t_{0}}(1-\frac{\alpha}{M})\bigg{)}\cdot\prod_{k=t_{0}+1}^{t}\Big{(}1-\frac{2}{k+1}\Big{)}$
$\displaystyle=\Big{(}1-\frac{\alpha}{M}\Big{)}^{t_{0}-1}\cdot\frac{t_{0}(t_{0}+1)}{t(t+1)}.$

Next, we decompose the term $\frac{1}{H_{t}}\sqrt{\sum_{k=1}^{t}\eta_{k}^{2}}$
as follows:

$\frac{\sqrt{\sum_{k=1}^{t}\eta_{k}^{2}}}{H_{t}}\\!=\\!\sqrt{\sum_{i=1}^{t_{0}}\Big{(}\frac{\eta_{i}}{H_{t}}\Big{)}^{2}+\sum_{i=t_{0}+1}^{t}\Big{(}\frac{\eta_{i}}{H_{t}}\Big{)}^{2}}.$
(26)

We now seek to bound $\sum_{i=t_{0}+1}^{t}(\frac{\eta_{i}}{H_{t}})^{2}$ in
(26). We first derive the ratio
$(\frac{\eta_{i-1}}{H_{t}})^{2}/(\frac{\eta_{i}}{H_{t}})^{2}$ for all
$i\in\\{t_{0}+2,\ldots,t\\}$. Noting that
$\frac{\eta_{i}}{H_{i}}=\frac{2}{i+1}$,

$\displaystyle\Big{(}\frac{\eta_{i-1}}{H_{t}}\Big{)}^{2}/\Big{(}\frac{\eta_{i}}{H_{t}}\Big{)}^{2}=\Big{(}\frac{\eta_{i-1}}{\eta_{i}}\Big{)}^{2}$
$\displaystyle=\Big{(}\frac{i+1}{i}\cdot\frac{H_{i-1}}{H_{i}}\Big{)}^{2}=\Big{(}\frac{i+1}{i}\cdot\frac{H_{i}-\eta_{i}}{H_{i}}\Big{)}^{2}$
$\displaystyle=\Big{(}\frac{i+1}{i}\cdot\left(1-\frac{\eta_{i}}{H_{i}}\right)\Big{)}^{2}=\Big{(}\frac{i+1}{i}\cdot\Big{(}1-\frac{2}{i+1}\Big{)}\Big{)}^{2}$
$\displaystyle=\Big{(}\frac{i-1}{i}\Big{)}^{2}.$

Hence, we have

$\displaystyle\sum_{i=t_{0}+1}^{t}\Big{(}\frac{\eta_{i}}{H_{t}}\Big{)}^{2}$
$\displaystyle=\Big{(}\frac{\eta_{t}}{H_{t}}\Big{)}^{2}\bigg{(}1\\!+\\!\Big{(}\frac{t-1}{t}\Big{)}^{2}\\!+\\!\Big{(}\frac{t-2}{t}\Big{)}^{2}\\!+\\!\dotsm\\!+\\!\Big{(}\frac{t_{0}+1}{t}\Big{)}^{2}\bigg{)}$
$\displaystyle=\Big{(}\frac{\eta_{t}}{H_{t}}\Big{)}^{2}\bigg{(}\frac{t^{2}+(t-1)^{2}+(t-2)^{2}+\dotsm+(t_{0}+1)^{2}}{t^{2}}\bigg{)}$
$\displaystyle=\Big{(}\frac{2}{t+1}\Big{)}^{2}\bigg{(}\frac{\sum_{i=t_{0}+1}^{t}i^{2}}{t^{2}}\bigg{)}.$
(27)

Next, we can bound the remaining part in (26) as follows

$\displaystyle\sum_{i=1}^{t_{0}}\Big{(}\frac{\eta_{i}}{H_{t}}\Big{)}^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{(\frac{\eta_{t_{0}}}{H_{t}})^{2}(1-(1-\alpha/M)^{2t_{0}})}{1-(1-\alpha/M)^{2}}$
$\displaystyle\leqslant\frac{(\frac{\eta_{t_{0}}}{H_{t}})^{2}}{1-(1-\alpha/M)^{2}}\stackrel{{\scriptstyle(b)}}{{\leqslant}}\frac{M^{2}}{\alpha^{2}}\Big{(}\frac{\eta_{t_{0}}}{H_{t}}\Big{)}^{2},$

where $(a)$ is due to the fact that
$(\frac{\eta_{j}}{H_{t}})^{2}/(\frac{\eta_{j+1}}{H_{t}})^{2}=(1-\alpha/M)^{2}$
for all $j\in\\{1,\ldots,t_{0}-1\\}$ and $(b)$ is due to the fact that
$1-(1-\alpha/M)^{2}\geqslant\alpha^{2}/M^{2}$ when $\alpha/M\leqslant 1$.

To compute $(\frac{\eta_{t_{0}}}{H_{t}})^{2}$, consider

$\displaystyle\frac{\eta_{t_{0}+1}}{H_{t_{0}+1}}$
$\displaystyle=\frac{2}{t_{0}+2},$
$\displaystyle\quad\frac{\eta_{t_{0}+1}}{H_{t_{0}}+\eta_{t_{0}+1}}$
$\displaystyle=\frac{2}{t_{0}+2},$
$\displaystyle\frac{H_{t_{0}}}{\eta_{t_{0}+1}}$
$\displaystyle=\frac{t_{0}}{2},$
$\displaystyle\quad\frac{\eta_{t_{0}}}{\eta_{t_{0}+1}}$
$\displaystyle=\frac{\alpha}{M}\cdot\frac{t_{0}}{2},$

where the final equality is because $\eta_{t_{0}}/H_{t_{0}}=\alpha/M$.

From
$\big{(}\frac{\eta_{t_{0}+1}}{H_{t}}\big{)}^{2}=\big{(}\frac{\eta_{t}}{H_{t}}\big{)}^{2}\big{(}\frac{t_{0}+1}{t}\big{)}^{2}$,
we have the equality
$\big{(}\frac{\eta_{t_{0}}}{H_{t}}\big{)}^{2}=\frac{\alpha^{2}}{M^{2}}\big{(}\frac{t_{0}(t_{0}+1)}{t(t+1)}\big{)}^{2}$.
Hence,

$\sum_{i=1}^{t_{0}}\Big{(}\frac{\eta_{i}}{H_{t}}\Big{)}^{2}\leqslant\Big{(}\frac{t_{0}(t_{0}+1)}{t(t+1)}\Big{)}^{2}.$
(28)

By substituting (27) and (28) back into (26), we obtain

$\displaystyle\frac{\sqrt{\sum_{k=1}^{t}\eta_{k}^{2}}}{H_{t}}\\!$
$\displaystyle\leqslant\\!\sqrt{\Big{(}\frac{t_{0}(t_{0}+1)}{t(t+1)}\Big{)}^{2}\\!+\\!\Big{(}\frac{2}{t(t+1)}\Big{)}^{2}\sum_{k=t_{0}+1}^{t}k^{2}}$

completing the proof upon using the definition of $A(t,t_{0})$. ∎

## References

  * [1] S. Wang and V. Y. F. Tan, “Robust distributed gradient descent to corruption over noisy channels,” in _2024 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2024, pp. 1–1.
  * [2] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein _et al._ , “Distributed optimization and statistical learning via the alternating direction method of multipliers,” _Foundations and Trends® in Machine learning_ , vol. 3, no. 1, pp. 1–122, 2011.
  * [3] M. I. Jordan, J. D. Lee, and Y. Yang, “Communication-efficient distributed statistical inference,” _Journal of the American Statistical Association_ , 2018.
  * [4] Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein, “Distributed graphlab: A framework for machine learning in the cloud,” _arXiv preprint arXiv:1204.6078_ , 2012.
  * [5] P. Richtárik and M. Takáč, “Distributed coordinate descent method for learning with big data,” _Journal of Machine Learning Research_ , vol. 17, no. 75, pp. 1–25, 2016.
  * [6] ——, “Parallel coordinate descent methods for big data optimization,” _Mathematical Programming_ , vol. 156, pp. 433–484, 2016.
  * [7] T. Chen, G. Giannakis, T. Sun, and W. Yin, “Lag: Lazily aggregated gradient for communication-efficient distributed learning,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [8] R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, “Gradient coding: Avoiding stragglers in distributed learning,” in _International Conference on Machine Learning_. PMLR, 2017, pp. 3368–3376.
  * [9] R. Bitar, M. Wootters, and S. El Rouayheb, “Stochastic gradient coding for straggler mitigation in distributed learning,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 1, no. 1, pp. 277–291, 2020.
  * [10] L. Chen, H. Wang, Z. Charles, and D. Papailiopoulos, “DRACO: Byzantine-resilient distributed training via redundant gradients,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 903–912.
  * [11] Y. Chen, L. Su, and J. Xu, “Distributed statistical machine learning in adversarial settings: Byzantine gradient descent,” _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , vol. 1, no. 2, pp. 1–25, 2017.
  * [12] D. Yin, Y. Chen, R. Kannan, and P. Bartlett, “Byzantine-robust distributed learning: Towards optimal statistical rates,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 5650–5659.
  * [13] X. Cao and L. Lai, “Distributed gradient descent algorithm robust to an arbitrary number of byzantine attackers,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 22, pp. 5850–5864, 2019.
  * [14] P. Blanchard, E. M. El Mhamdi, R. Guerraoui, and J. Stainer, “Machine learning with adversaries: Byzantine tolerant gradient descent,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [15] G. Lan, “An optimal method for stochastic composite optimization,” _Mathematical Programming_ , vol. 133, no. 1, pp. 365–397, 2012.
  * [16] S. Ghadimi and G. Lan, “Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization I: A generic algorithmic framework,” _SIAM Journal on Optimization_ , vol. 22, no. 4, pp. 1469–1492, 2012.
  * [17] O. Devolder, F. Glineur, and Y. Nesterov, “First-order methods of smooth convex optimization with inexact oracle,” _Mathematical Programming_ , vol. 146, pp. 37–75, 2014.
  * [18] M. Cohen, J. Diakonikolas, and L. Orecchia, “On acceleration with noise-corrupted gradients,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 1019–1028.
  * [19] Q. Zhou and S. J. Pan, “On acceleration for convex composite minimization with noise-corrupted gradients and approximate proximal mapping,” _Journal of Machine Learning Research_ , vol. 23, no. 223, pp. 1–59, 2022.
  * [20] F.-C. Chang, F. Nabiei, P.-Y. Wu, A. Cioba, S. Vakili, and A. Bernacchia, “Gradient descent: Robustness to adversarial corruption,” in _OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop)_ , 2022.
  * [21] C. Hofmeister, L. Maßny, E. Yaakobi, and R. Bitar, “Trading communication for computation in byzantine-resilient gradient coding,” in _2023 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2023, pp. 1985–1990.
  * [22] S. Ito, “On optimal robustness to adversarial corruption in online decision problems,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 7409–7420, 2021.
  * [23] J. Zimmert and Y. Seldin, “An optimal algorithm for stochastic and adversarial bandits,” in _The 22nd International Conference on Artificial Intelligence and Statistics_. PMLR, 2019, pp. 467–475.
  * [24] Z. Zhong, W. C. Cheung, and V. Tan, “Probabilistic sequential shrinking: A best arm identification algorithm for stochastic bandits with corruptions,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 12 772–12 781.
  * [25] S. Sachs, H. Hadiji, T. van Erven, and C. Guzmán, “Between stochastic and adversarial online convex optimization: Improved regret bounds via smoothness,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 691–702, 2022.
  * [26] D. Bertsekas, A. Nedic, and A. Ozdaglar, _Convex analysis and optimization_. Athena Scientific, 2003, vol. 1.
  * [27] Y. Nesterov, “Primal-dual subgradient methods for convex problems,” _Mathematical programming_ , vol. 120, no. 1, pp. 221–259, 2009.
  * [28] J. Diakonikolas and L. Orecchia, “The approximate duality gap technique: A unified theory of first-order methods,” _SIAM Journal on Optimization_ , vol. 29, no. 1, pp. 660–689, 2019.
  * [29] A. S. Nemirovskij and D. B. Yudin, “Problem complexity and method efficiency in optimization,” 1983.
  * [30] G. Garrigos and R. M. Gower, “Handbook of convergence theorems for (stochastic) gradient methods,” _arXiv preprint arXiv:2301.11235_ , 2023.
  * [31] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [32] K.-W. Chang, C.-J. Hsieh, and C.-J. Lin, “Coordinate descent method for large-scale l2-loss linear support vector machines.” _Journal of Machine Learning Research_ , vol. 9, no. 7, 2008.
  * [33] Y. Tang, “Deep learning using linear support vector machines,” _arXiv preprint arXiv:1306.0239_ , 2013.