#  Robust Training in High Dimensions via
Block Coordinate Geometric Median Descent

Anish Acharya This work is supported in part by NSF grants CCF-1564000,
IIS-1546452 and HDR-1934932. University of Texas at Austin  Abolfazl Hashemi
University of Texas at Austin
Prateek Jain  Google AI  Sujay Sanghavi  University of Texas at Austin  Amazon
Search  Inderjit Dhillon  University of Texas at Austin  Amazon Search  Ufuk
Topcu  University of Texas at Austin

###### Abstract

Geometric median (Gm) is a classical method in statistics for achieving a
robust estimation of the uncorrupted data; under gross corruption, it achieves
the optimal breakdown point of 0.5. However, its computational complexity
makes it infeasible for robustifying stochastic gradient descent (SGD) for
high-dimensional optimization problems. In this paper, we show that by
applying Gm to only a judiciously chosen block of coordinates at a time and
using a memory mechanism, one can retain the breakdown point of 0.5 for smooth
non-convex problems, with non-asymptotic convergence rates comparable to the
SGD with Gm.111The implementation of the proposed method is available at Code
Link

##  1 Introduction

Consider smooth non-convex optimization problems with finite sum structure:

$\min_{\mathbf{x}\in\mathbb{R}^{d}}\left[\bar{f}(\mathbf{x}):=\frac{1}{n}\sum_{i=1}^{n}f_{i}(\mathbf{x})\right].$
(1)

Mini-batch SGD is the de-facto method for optimizing such functions [RM51,
Bot10, TBA86] which proceeds as follows: at each iteration $t$, it selects a
random batch ${\mathcal{D}}_{t}$ of $b$ samples, obtains gradients
${\mathbf{g}}_{t}^{(i)}=\nabla f_{i}({\mathbf{x}}_{t}),\;\forall
i\in{\mathcal{D}}_{t}$, and updates the parameters using iterations of the
form:

${\mathbf{x}}_{t+1}:={\mathbf{x}}_{t}-\gamma\tilde{{\mathbf{g}}}^{(t)},\quad\tilde{{\mathbf{g}}}^{(t)}=\frac{1}{|{\mathcal{D}}_{t}|}\sum_{i\in{\mathcal{D}}_{t}}{\mathbf{g}}_{i}^{(t)}.$
(2)

In spite of its strong convergence properties in the standard settings [MB11,
DGBSX12, LZCS14, GDG+17, KMN+16, YHCL12], it is well known that even a small
fraction of corrupt samples can lead SGD to an arbitrarily poor solution
[BBC11, BTN00]. This has motivated a long line of work to study robust
optimization in presence of corruption [BGS+17, AAZL18, WLCG20, XKG19]. While
the problem has been studied under a variety of contamination models, in this
paper, we study the robustness properties of the first-order method (2) under
the strong and practical gross contamination model (See Definition 1) [Li18,
DK19, DKK+19b, DKK+19a] which also generalizes the popular Huber’s
contamination model and the byzantine contamination framework [Hub92, LSP82].

In particular, the goal of this work is to design an efficient first-order
optimization method to solve (1), which remains robust even when
$0\leq\psi<1/2$ fraction of the gradient estimates ${\mathbf{g}}_{t}^{(i)}$
are arbitrarily corrupted in each batch ${\mathcal{D}}_{t}$, without any prior
knowledge about the malicious samples. Note that, by letting the corrupt
estimates to be arbitrarily skewed, this corruption model is able to capture a
number of important and practical scenarios including corruption in feature
(e.g., existence of outliers) , corrupt gradients (e.g., hardware failure,
unreliable communication channels during distributed training) and backdoor
attacks [CLL+17, LZS+18, GLDGG19, BNL12, MGR18, TLM18] (See Section 7).

#### Robust SGD via Geometric Median Descent (GmD).

Under the gross corruption model (Definition 1), the vulnerability of mini-
batch SGD can be attributed to the linear gradient aggregation step (2)
[BGS+17, AAZL18, YCKB18, XKG19]. In fact, it can be shown that no linear
gradient aggregation strategy can tolerate even a single grossly corrupted
update, i.e., they have a breakdown point (Definition 2) of 0. To see this,
consider the single malicious gradient
${\mathbf{g}}_{t}^{(j)}=-\sum_{i\in{{\mathcal{D}}_{t}\setminus
j}}{\mathbf{g}}_{t}^{(i)}$. One can see that this single corrupted gradient
results in the average to become $\mathbf{0}$, which in turn means mini-batch
SGD gets stuck at the initialization. An approach for robust optimization may
be to find an estimate $\tilde{g}$ such that with high probability
$\|\tilde{g}-\frac{1}{{\mathbb{G}}}\sum_{{\mathbf{g}}_{i}\in{\mathbb{G}}}{\mathbf{g}}_{i}\|$
is small even in presence of gross-corruption [DK19]. In this context,
geometric median (Gm) (Definition 3) is a well studied rotation and
translation invariant robust estimator with optimal breakdown point of 1/2
even under gross corruption [LR+91, M+15, CLM+16]. Due to this strong
robustness property, SGD with Gm-based gradient aggregation (GmD) has been
widely studied in robust optimization literature [AAZL18, CSX17, PKH19,
WLCG20]. Following the notation of (2) the update step of GmD can be written
as:

${\mathbf{x}}_{t+1}:={\mathbf{x}}_{t}-\gamma\tilde{{\mathbf{g}}}^{(t)},\quad\tilde{{\mathbf{g}}}^{(t)}=\textsc{Gm}(\\{{\mathbf{g}}_{i}^{(t)}\\})\;\forall
i\in[b]$ (3)

Despite the strong robustness guarantees of Gm, the computational cost of
calculating $\epsilon$ approximate Gm is prohibitive, especially in high
dimensional settings. For example, the best known result [CLM+16] uses a
subroutine that needs $O(d/\epsilon^{2})$ computations to find an
$\epsilon$-approximate Gm. Despite recent efforts in [VZ00, Wei37, CT89,
CMMP13, CLM+16, PKH19] to design computationally tractable Gm($\cdot$), given
that in practical large-scale optimization settings such as training deep
learning models the number of parameters ($d$) is large (e.g., $d\approx 60M$
for AlexNet, $d\approx 175B$ for GPT-3). GmD remains prohibitively expensive
[CWCP18, PKH19] and with limited applicability.

#### Overview of Our Algorithm (BgmD).

In this work, we leverage coordinate selection strategies to reduce the cost
of GmD and establish Block co-ordinate Gm Descent (BGmD) (Algorithm 1). BGmD
is a robust optimization approach that can significantly reduce the
computational overhead of Gm based gradient aggregation resulting in nearly
two orders of magnitude speedup over GmD on standard deep learning training
tasks, while maintaining almost the same level of accuracy and optimal
breakdown point 1/2 even in presence of gross corruption.

At a high level, BGmD selects a block of $0<k\leq d$ important coordinates of
the gradients; importance of a coordinate is measured according to the largest
directional derivative measured by the squared $\ell_{2}$ norm across all the
samples (Algorithm 2). The remaining $(d-k)$ dimensions are discarded and
gradient aggregation happens only along these selected $k$ directions. This
Implies the Gm subroutine is performed only over gradient vectors in
${\mathbb{R}}^{k}$ (a significantly lower dimensional subspace). Thus, when
$k\ll d$, this approach provides a practical solution to deploy Gm-based
aggregation in high dimensional settings222The notation $k\ll d$ implies that
$k$ is at least an order of magnitude smaller than $d$.

The motivation behind reducing the dimension of the gradient vectors is that
in many scenarios most of the information in the gradients is captured by a
subset of the coordinates [SCCS19]. Hence, by the judicious block coordinate
selection subroutine outlined in Algorithm 2 one can identify an informative
low-dimensional representation of the gradients.

While Algorithm 2 identifies a representative block of the coordinates,
aggressively reducing the dimension (i.e., $k\ll d$) might lead to a
significant approximation error, which in turn might lead to slower
convergence [Nes12, NSL+15] (i.e., more iterations), dwarfing the benefit from
reduction in per iteration cost. To alleviate this issue, by leveraging the
idea of Error Compensation [SFD+14, SK19, KRSJ19] in Algorithm 1 we introduce
a memory augmentation mechanism. Specifically, at each iteration the residual
error from dimensionality reduction is computed and accumulated in a memory
vector i.e., $\hat{{\mathbf{m}}}_{t}$ and in the subsequent iteration,
$\hat{{\mathbf{m}}}_{t}$ is added back to the new gradient estimates. Our
ablation studies show that such memory augmentation indeed ensures that the
required number of iterations remain relatively small despite choosing $k\ll
d$ (See Figure 6).

Initialize: estimate: ${\mathbf{x}}_{0}\in{\mathbb{R}}^{d}$, step-size:
$\gamma$, memory: $\hat{{\mathbf{m}}}_{0}=\textbf{0}$, Block Coordinate
Selection operator: ${\mathcal{C}}_{k}(\cdot)$, Geometric Median operator:
Gm($\cdot$)

for  _epochs ;_

_t = 0, …, until convergence_ do

Select samples ${\mathcal{D}}_{t}=\\{i_{1},\dots,i_{b}\\}$

Obtain : ${\mathbf{g}}_{t}^{(i)}:=\nabla f_{i}({\mathbf{x}}_{t}),\;\forall
i\in{\mathcal{D}}_{t}$

Let ${\mathbf{G}}_{t}\in{\mathbb{R}}^{b\times d}$ s.t. each row
${\mathbf{G}}_{t}[i,:]={\mathbf{g}}_{t}^{(i)}$

${\mathbf{G}}_{t}[i,:]=\gamma{\mathbf{G}}_{t}[i,:]+\hat{{\mathbf{m}}}_{t}\;\forall
i\in[b]$ (Memory Augmentation)

$\bm{\Delta}_{t}:=\mathcal{C}_{k}({\mathbf{G}}_{t})$ (Select top $k$ columns
via Algo 2)

${\mathbf{M}}_{t}={\mathbf{G}}_{t}-\bm{\Delta}_{t}$ (Compute Residuals)

$\hat{{\mathbf{m}}}_{t+1}=\frac{1}{b}\sum_{0\leq i\leq
b}{\mathbf{M}}_{t}[i,:]$ (Update memory)

$\tilde{{\mathbf{g}}}_{t}:=\textsc{Gm}(\bm{\Delta}_{t})$ (Robust Aggregation
in ${\mathbb{R}}^{k}$)

${\mathbf{x}}_{t+1}:={\mathbf{x}}_{t}-\tilde{{\mathbf{g}}}_{t}$ (Global model
update)

end for

Algorithm 1 Block Gm Descent (BGmD)

Input: ;

${\mathbf{G}}_{t}\in{\mathbb{R}}^{n\times d},\;k$

for  _coordinates ;_

_j = 0, …, d-1_ do

$s_{j}\leftarrow\|{\mathbf{G}}_{t}[:,j]\|^{2}$ ;

(norm along each dimension)

end for

Sample set ${\mathbb{I}}_{k}$ of $k$ dimensions with probabilities
proportional to $s_{j}$

${\mathcal{C}}_{k}({\mathbf{G}})_{i,j\in{\mathbb{I}}_{k}}={\mathbf{G}}_{i,j},\;{\mathcal{C}}_{k}({\mathbf{G}})_{i,j\notin{\mathbb{I}}_{k}}=0$

Return: ${\mathcal{C}}_{k}({\mathbf{G}})$

Algorithm 2 Block Coordinate Selection Strategy

#### Contributions.

The main contributions of this work are as follows:

  * •

We propose BGmD (Algorithm 1), a method for robust optimization in high
dimensions. BGmD is significantly more efficient than the standard Gm-SGD
method but is still able to maintain the optimal breakdown point 1/2 – first
such efficient method with provable convergence guarantees.

  * •

We provide strong guarantees on the rate of convergence of BGmD in standard
non-convex scenarios including smooth non-convex functions, and non-convex
functions satisfying the Polyak-Łojasiewicz Condition. These rates are
comparable to those established for Gm-SGD under more restricting conditions
such as strong convexity [CSX17, PKH19, WLCG20].

  * •

Through extensive experiments under several common corruption settings ; we
demonstrate that BGmD can be up to $3\times$ more efficient to train than Gm-
SGD on Fashion MNIST and CIFAR-10 benchmarks while still ensuring similar test
accuracy and maintaining same level of robustness.

Table 1: Comparison of time complexity and robustness properties of different robust optimization methods. The bold quantities show a method achieves the theoretical limits. $*$ CmD throughout the paper will refer to Co-ordinate wise median descent i.e. simply replacing the aggregation step of SGD by Cm. Algorithm | Iteration Complexity | Breakdown Point
---|---|---
SGD | ${\mathcal{O}}(bd)$ | 0
CMD∗ [YZFL19, YCKB18] | ${\mathcal{O}}(bd)$ | 1/2 - $\Omega(\sqrt{d/b})$
GMD [CLM+16, WLCG20] | ${\mathcal{O}}(d\epsilon^{-2}+bd)$ | 1/2
[DD20] | ${\mathcal{O}}(db^{2}\min(d,b))$ | 1/4
BGmD (This Work) | ${\mathcal{O}}(k\epsilon^{-2}+bd)$ | 1/2

##  2 Related Work

#### Computationally Tractable Robust SGD.

Robust optimization in the presence of gross corruption has received renewed
impetus in the machine learning community, following practical considerations
such as preserving the privacy of the user data and coping with the existence
of adversarial disturbances [BGS+17, CSX17, MMR+17]. There are two main
research directions in this area.
The first direction aims at designing robustness criteria to identify and
subsequently filter out corrupt samples before employing the linear gradient
aggregation technique in (2). For example, [GMK+19, GLV20] remove the samples
with gradient norms exceeding a predetermined threshold, [YCKB18] remove a
fraction of samples from both tails of the gradient norm distribution,
[CWCP18, YB19] use redundancy [VN56] and majority vote operations, [DKK+19b]
rely on spectral filtering, [SCV17, BGS+17, DD20, BKSV20] use
$(\epsilon,\sigma)$-resilience based iterative filtering approach, while
[XKG19] instead add a resilience-based penalty to the optimization task to
implicitly remove the corrupt samples.
Our approach falls under the second research direction, where the aim is to
replace mini-batch averaging with a robust gradient aggregation operator. In
addition to Gm operator [FXM14, AAZL18, CSX17] which was discussed earlier,
other notable examples of robust aggregation techniques include krum [BGS+17],
coordinate wise median [YCKB18], and trimmed mean [YCKB18]. Despite these
alternatives, Gm is the most resilient method in practice achieving the
optimal breakdown point of 1/2. We compare a number of robust optimization
methods in this direction with BGmD in terms of computational complexity and
breakdown in Table 1.

#### Connection to Coordinate Descent

Coordinate Descent (CD) refers to a class of methods wherein at each
iteration, a block of coordinates is chosen and subsequently updated using a
descent step. While this strategy has a long history [SBT00, Fu98, Ber97,
Joa98, Opt98], it has received renewed interest in the context of modern large
scale machine learning with very high dimensional parameter space [Nes12,
RT14, TY09a, TY09b, SRJ17, BT13]. There has been significant research efforts
focusing on efficient coordinate selection strategy. For instance, [Nes12,
NT14, SSZ13, RT14, AZQRY16] choose the coordinates randomly while [ST13,
GOPV17] do so cyclically in a fixed order, referred as the Gauss Seidel rule,
and [NSL+15, NLS17, HD11, DRT11, YLL+16, KKSJ19] propose choosing the
coordinates greedily according to norm-based selection criteria, a strategy
known as the Gauss Southwell rule.

######  Remark 1.

Note that, our approach (Algorithm 2) is closely related to the Greedy Gauss
Southwell coordinate selection approach. In fact, it is immediate that for
batch size $b=1$ Gauss Southwell Co-ordinate Descent becomes a special case of
BGmD.

#### Connection to Error Feedback

Compensating for the loss incurred due to approximation through a memory
mechanism is a common concept in the feedback control and signal processing
literature (See [DFT13] and references therein). [SFD+14, Str15] adapt this to
gradient compression (1Bit-SGD) to reduce the number of communicated bits in
distributed optimization. Recently, [SCJ18, SK19, KRSJ19] have analyzed this
error feedback framework for a number of gradient compressors in the context
of communication-constrained distributed training.

######  Remark 2.

Note that our memory mechanism is inspired by this error feedback mechanism.
In fact, all the works on error feedback to compensate for gradient
compression [SCJ18, SK19, KRSJ19] are special case of our proposed memory
mechanism when batch size $b=1$ i.e.
${\mathbf{M}}_{t}=\hat{{\mathbf{m}}}_{t}$.

##  3 Preliminaries

We first briefly recall some related concepts and state our main assumptions.
Throughout, $\|.\|$ denotes the $\ell_{2}$ norm unless otherwise specified.

######  Definition 1 (Gross Corruption Model).

Given $0\leq\psi<\frac{1}{2}$ and a distribution family ${\mathcal{D}}$ on
${\mathbb{R}}^{d}$ the adversary operates as follows: $n$ samples are drawn
from $D\in{\mathcal{D}}$. The adversary is allowed to inspect all the samples
and replace up to $\psi n$ samples with arbitrary points.

Intuitively, this implies that $(1-\psi)$ fraction of the training samples are
generated from the true distribution (inliers) and rest are allowed to be
arbitrarily corrupted (outliers) i.e.
$\alpha:=|{\mathbb{B}}|/|{\mathbb{G}}|=\frac{\psi}{1-\psi}<1$, where
${\mathbb{B}}$ and ${\mathbb{G}}$ are the sets of corrupt and good samples. In
the rest of the paper, we will refer to a set of samples generated through
this process as $\alpha$-corrupted.

######  Definition 2 (Breakdown Point).

Finite-sample breakdown point [DH83] is a way to measure the resilience of an
estimator. It is defined as the smallest fraction of contamination that must
be introduced to cause an estimator to break i.e. produce arbitrarily wrong
estimates.

In the context Definition 1 we can say an estimator has the optimal breakdown
point 1/2 if it is robust in presence of $\alpha$-corruption
$\forall\;\psi<1/2$ or alternatively $\forall\;\alpha<1$.

######  Definition 3 (Geometric Median).

Given a finite collection of observations
${\mathbf{x}}_{1},{\mathbf{x}}_{2},\dots\mathbf{x}_{n}$ defined over a
separable Hilbert space $\mathbb{X}$ with norm $\|\cdot\|$ the geometric
median or the Fermet-Weber point [Hal48, WF+29, M+15, Kem87] is defined as:

${\mathbf{x}}_{*}=\textsc{Gm}(\\{{\mathbf{x}}_{i}\\})=\operatorname*{arg\,min}_{{\mathbf{y}}\in\mathbb{X}}\bigg{[}g({\mathbf{x}}):=\sum_{i=1}^{n}\|{\mathbf{y}}-{\mathbf{x}}_{i}\|\bigg{]}$
(4)

We call a point ${\mathbf{x}}\in\mathbb{R}^{d}$ an $\epsilon$-accurate
geometric median if $g({\mathbf{x}})\leq(1+\epsilon)g({\mathbf{x}}_{*})$.

######  Assumption 1 (Stochastic Oracle).

Each non-corrupt sample $i\in{\mathbb{G}}$ is endowed with an unbiased
stochastic first-order oracle with bounded variance. That is,

$\mathbb{E}_{z\sim{\mathcal{D}}_{i}}[{\mathbf{g}}_{i}({\mathbf{x}},z)]=\nabla
f_{i}({\mathbf{x}}),\qquad\mathbb{E}_{z\sim{\mathcal{D}}_{i}}\|\nabla
F_{i}({\mathbf{x}},z)\|^{2}\leq\sigma^{2}$ (5)

######  Assumption 2 ( Smoothness).

Each non-corrupt function $f_{i}$ is $L$-smooth, $\forall i\in{\mathbb{G}}$,

$f_{i}({\mathbf{x}})\leq
f_{i}({\mathbf{y}})+\langle{\mathbf{x}}-{\mathbf{y}},\nabla
f_{i}({\mathbf{y}})\rangle+\frac{L}{2}\|{\mathbf{x}}-{\mathbf{y}}\|^{2}.\quad\forall{\mathbf{x}},{\mathbf{y}}\in{\mathbb{R}}^{d}.$
(6)

######  Assumption 3 ( Polyak-Łojasiewicz Condition).

The average of non-corrupt functions
$f:=\frac{1}{{\mathbb{G}}}\sum_{i\in{\mathbb{G}}}f_{i}(\mathbf{x})$ satisfies
the Polyak-Łojasiewicz condition (PLC) with parameter $\mu$, i.e.

$\displaystyle\|\nabla f({\mathbf{x}})\|^{2}\geq
2\mu(f({\mathbf{x}})-f({\mathbf{x}}^{\ast})),\;\mu>0\quad\textup{where}$
$\displaystyle{\mathbf{x}}^{\ast}=\operatorname*{arg\,min}_{\mathbf{x}}f({\mathbf{x}}),\quad\forall{\mathbf{x}}\in{\mathbb{R}}^{d}.$
(7)

We further assume that the solution set
${\mathcal{X}}^{\ast}\in{\mathbb{R}}^{d}$ is non-empty and convex. Also note
that $\mu<L$.

Simply put, the Polyak-Łojasiewicz condition implies that when multiple global
optima exist, each stationary point of the objective function is a global
optimum [Pol63, KNS16]. This setting enables the study of modern large-scale
ML tasks that are generally non-convex. Also note that $\mu$-strongly convex
functions satisfy PLC with parameter $\mu$ implying PLC is a weaker assumption
than strong convexity.

##  4 Block Coordinate Geometric Median Descent (BGmD)

As discussed earlier, BGmD (Algorithm 1) involves two key steps: (i) Selecting
a block of coordinates and run computationally expensive Gm aggregation over a
low dimensional subspace and (ii) Compensating for the residual error due to
block coordinate selection. In the rest of this section we will discuss these
two ideas in more detail.

#### Block Selection Strategy.

The key intuition why we might be able to select a small number of $k$
coordinates for robust mean estimation is that in practical over-parameterized
models, the main mass of the gradient is concentrated in a few coordinates
[CCS+19]. So, what would be the best strategy to select the most informative
block of coordinates? Ideally, one would like to select the best $k$
dimensions that would result in the largest decrease in training loss.
However, this task is NP-hard in general [DK11, NW81, CGK+00]. Instead, we
adopt a simple and fast block coordinate selection rule: Consider
${\mathbf{G}}\in{\mathbb{R}}^{b\times d}$ where each row corresponds to the
transpose of the stochastic gradient estimate, i.e.
${\mathbf{G}}_{i,:}={\mathbf{g}}_{i}^{T}\in{\mathbb{R}}^{1\times
d},\quad\forall i\in[b]$ where $b$ is number of samples (or batches/clients in
case of distributed setting) participating in that iteration (2). Then,
selecting $k$ dimensions is equivalent to selecting $k$ columns of
${\mathbf{G}}$, which we select according to the norm of the columns. That is,
we assign a score to each dimension proportional to the $\ell_{2}$ norm (total
mass along that coordinate) i.e. $s_{j}=\|{\mathbf{G}}_{:,j}\|^{2},$ for all
$j\in[d]$. We then sample only $k$ coordinates with with probabilities
proportional to $s_{j}$ and discard the rest to find a set $\omega_{k}$ of
size $k$ (see Algorithm 2). We show below that this method produces a
contraction approximation to ${\mathbf{G}}$.

######  Lemma 1.

Algorithm 2 yields a contraction approximation, i.e.,
$\mathbb{E}_{{\mathcal{C}}_{k}}\left[\|{\mathcal{C}}_{k}({\mathbf{G}})-{\mathbf{G}}\|_{F}^{2}|{\mathbf{x}}\right]\leq(1-\xi)\|{\mathbf{G}}\|_{F}^{2},\;\frac{k}{d}\leq\xi\leq
1,$ where
${\mathcal{C}}_{k}({\mathbf{G}})_{i,j\in\omega_{k}}={\mathbf{G}}_{i,j},$ and
${\mathcal{C}}_{k}({\mathbf{G}})_{i,j\notin\omega_{k}}=0$.

It is also worth noting that without additional distributional assumption on
${\mathbf{G}}$ the lower bound on $\xi$cannot be improved. 333To see this,
consider the case where each ${\mathbf{g}}_{t}^{(i)}$ is uniformly distributed
along each coordinates. Then, the algorithm would satisfy Lemma 1 with
$\xi=\frac{k}{d}$. In this scenario, the achievable bound is identical to the
bound achieved via choosing the $k$ dimensions uniformly at random. However,
in practice the gradient vectors are extremely unlikely to be uniform [AHJ+18]
and thus active norm sampling is expected to to satisfy Lemma 1 with
$\xi\approx 1$.

#### The Memory Mechanism.

While descending along only a small subset of $k$ coordinates at each
iteration significantly improves the per iteration computational cost, a
smaller value of $k$ would also imply larger gradient information loss i.e., a
smaller $\xi$ (Lemma 1). Intuitively, a restriction to a $k$-dimensional
subspace results in a $\frac{d}{k}$ factor increase in the gradient variance
[SCJ18].To mitigate this, we adopt a memory mechanism [SFD+14, Str15, SCJ18,
KRSJ19, SK19, DFT13] Our approach is as follows: Throughout the training
process, we keep track of the residual errors in
${\mathbf{G}}_{t}-{\mathcal{C}}_{k}({\mathbf{G}}_{t})$ via
$\hat{{\mathbf{m}}}_{t}\in{\mathbb{R}}^{d}$ that we call memory. At each
iteration $t$, it simply accumulates the residual error incurred due to
ignoring $d-k$ dimensions, averaged over all the samples participating in that
round. In the next iteration, $\hat{{\mathbf{m}}}_{t}$ is added back to all
the the new gradient estimates as feedback. Following our Jacobian notation,
the memory update is given as:

$\displaystyle\textup{{Memory
Augmentation}}\quad{\mathbf{G}}_{t}[i,:]=\gamma{\mathbf{G}}_{t}[i,:]+\hat{{\mathbf{m}}}_{t}\;\forall
i\in[b]$ (8) $\displaystyle\textup{{Memory
Update}}\quad{\mathbf{M}}_{t}={\mathbf{G}}_{t}-{\mathcal{C}}_{k}({\mathbf{G}}_{t})\;;\hat{{\mathbf{m}}}_{t+1}=\frac{1}{b}\sum_{0\leq
i\leq b}{\mathbf{M}}_{t}[i,:]$

Intuitively, as the residual at each iteration is not discarded but rather
kept in memory and added back in a future iteration, this ensures similar
convergence rates as training in ${\mathbb{R}}^{d}$ (see Theorem 1).

##  5 Computational Complexity Analysis

To theoretically understand the overall computational benefit of our proposed
scheme BGmD over Gm-SGD, we first analyze the per epoch time complexity of
both the algorithms. Combining this with the convergence rates derived in
Theorems 1 and 2 provides a clear picture of the overall computational
efficiency of BGmD.

Consider problem (1) with parameters ${\mathbf{x}}\in{\mathbb{R}}^{d}$ and SGD
style iterations of the form (2) and batch size $|{\mathcal{D}}_{t}|=b$. Note
that the difference between the iterations of SGD, Gm-SGD, and BGmD is
primarily in the aggregation step, i.e., how they aggregate the updates
communicated by samples (or batches) participating in training during that
iteration.

At iteration $t$, let $T_{a}^{(t)}$ denote the time to aggregate the
gradients. Also let, $T_{b}^{(t)}$ denote the time taken to compute the batch
gradients (i.e., time to perform back propagation). Thus, the overall
complexity of one training iteration is roughly
${\mathcal{O}}(T_{a}^{(t)}+T_{b}^{(t)})$. Now, note that $T_{b}^{(t)}$ is
approximately the same for all the algorithms mentioned above and for methods
like Gm-SGD $T_{b}^{(t)}\ll T_{a}^{(t)}$. So we focus on $T_{a}^{(t)}$ to
study the relative computational cost of SGD, Gm-SGD, and BGmD. To compute
$\tilde{{\mathbf{g}}}^{(t)}$ vanilla SGD needs to compute average of $b$
gradients in ${\mathbb{R}}^{d}$ implying ${\mathcal{O}}(bd)$ cost. On the
other had, Gm-SGD and its variants [AAZL18, CSX17, BCNW12] require computing
$\epsilon$-approximate Gm of $b$ points in ${\mathbb{R}}^{d}$ incurring per
iteration cost of at least ${\mathcal{O}}(\frac{d}{\epsilon^{2}})$ [CLM+16,
PKH19, AAZL18, CSX17]. In contrast, $T_{a}^{(t)}$ for BGmD is
${\mathcal{O}}(\frac{k}{\epsilon^{2}}+bd)$, where the first term in
computational complexity is due to computation of Gm of
${\mathbb{R}}^{k}$-dimensional points. The second term is due to the
coordinate sampling procedure.

That is, by choosing a sufficiently small block of coordinates i.e. $k\ll d$,
BGmD can result in significant savings per iteration. Based on this
observation, one can derive the following Lemma.

######  Lemma 2.

(Choice of k). Let $k\leq{\mathcal{O}}(\frac{1}{F}-b\epsilon^{2})\cdot d$.
Then, given an $\epsilon$\- approximate Gm oracle, Algorithm 1 achieves a
factor $F$ speedup over Gm-SGD for aggregating $b$ samples.

In most practical settings, the second term of $b\epsilon^{2}$ in Lemma 2 is
often negligible compared to the first term which implies significantly
smaller per-iteration complexity for BGmD compared to that of Gm-SGD.
Interestingly, in Theorem 1 we show that the rate of convergence and break-
down point for both the methods is similar, which implies that overall BGmD is
much more efficient in optimizing (1) than Gm-SGD.

##  6 Convergence Guarantees of BGmD

We now analyze the convergence properties of BGmD as described in Algorithm 1.
We state the results in Theorem 1 and Theorem 2 for general non-convex
functions and functions satisfying PLC, respectively.

######  Theorem 1 (Smooth Non-convex).

Consider the general case where the functions $f_{i}$ correspond to non-
corrupt samples $i\in{\mathbb{G}}$ are non-convex and smooth (Assumption 2).
Define, $R_{0}:=f({\mathbf{x}}_{0})-f({\mathbf{x}}^{\ast})$ where
${\mathbf{x}}^{\ast}$ is the true optima and ${\mathbf{x}}_{0}$ is the initial
parameters. Run Algorithm 1 with compression factor $\frac{k}{d}\leq\xi\leq 1$
(Lemma 1), learning rate $\gamma=1/2L$ and $\epsilon-$approximate Gm($\cdot$)
oracle in presence of $\alpha-$corruption (Definition 1) for $T$ iterations.
Sample an iteration $\tau$ from $1,\dots,T$ uniformly at random. Then, it
holds that:

$\displaystyle\mathbb{E}\|\nabla
f({\mathbf{x}}_{\tau})\|^{2}={\mathcal{O}}\Bigg{(}\frac{LR_{0}}{T}+\frac{\sigma^{2}\xi^{-2}}{(1-\alpha)^{2}}+\frac{L^{2}\epsilon^{2}}{|{\mathbb{G}}|^{2}(1-\alpha)^{2}}\Bigg{)}.$

######  Theorem 2 (Non-convex under PLC).

State the notation of Theorem 1. Assume
$f=\frac{1}{{\mathbb{G}}}\sum_{i\in{\mathbb{G}}}f_{i}(\mathbf{x})$ satisfies
the Polyak-Łojasiewicz Condition (Assumption 3) with parameter $\mu$. After
$T$ iterations Algorithm 1 with compression factor $\frac{k}{d}\leq\xi\leq 1$
(Lemma 1), learning rate $\gamma=1/4L$ and $\epsilon-$approximate Gm($\cdot$)
oracle in presence of $\alpha-$corruption (Definition 1) satisfies:

$\displaystyle\mathbb{E}\|\hat{{\mathbf{x}}}_{T}-{\mathbf{x}}^{\ast}\|^{2}$
$\displaystyle={\mathcal{O}}\Bigg{(}\frac{LR_{0}}{\mu^{2}}\left[1-\frac{\mu}{8L}\right]^{T}+\frac{\sigma^{2}\xi^{-2}}{\mu^{2}(1-\alpha)^{2}}+\frac{L^{2}\epsilon^{2}}{\mu^{2}|{\mathbb{G}}|^{2}(1-\alpha)^{2}}\Bigg{)},$
(9)

for a global optimal solution ${\mathbf{x}}^{\ast}\in{\mathcal{X}}^{\ast}$.
Here,
$\hat{{\mathbf{x}}}_{T}:=\frac{1}{W_{T}}\sum_{t=0}^{T-1}w_{t}{\mathbf{x}}_{t}$
with weights $w_{t}:=(1-\frac{\mu}{8L})^{-(t+1)}$,
$W_{T}:=\sum_{t=0}^{T-1}w_{t}$.

Theorem 1 and Theorem 2 state that Algorithm 1 with a constant stepsize
convergences to a neighborhood of a first order stationary point. The radius
of this neighborhood depends on two terms. The first term depends on the
variance of the stochastic gradients as well as the effectiveness of the
coordinate selection strategy through $\xi$. The second term however depends
on how accurate the Gm computation is performed in each iteration. As we
demonstrate in our experiments typically the proposed coordinate selection
strategy entails a $\xi\approx 1$. Therefore, we expect the radius of error to
be negligible. Furthermore, both terms in the radius depend on the fraction of
corrupted samples and as long as less than 50% of the samples are corrupted,
BGmD attains convergence to a neighborhood of a stationary point. We also note
that this rate matches the rate of Gm-SGD when the data is not i.i.d. (see
e.g. [CSX17, AAZL18, WLCG20, DD20] and the references therein) while Algorithm
1 significantly reduces the cost of Gm-based aggregation. We further note that
the convergence properties established in Theorem 2 are analogous to those of
Gm-SGD. However, compared to the existing analyses that require strong
convexity([AAZL18, WLCG20, DD20]), Theorem 2 only assumes PLC which as we
discussed is a much milder condition. Furthermore, in absence of corruption
(i.e., $\alpha=0$), if the data is i.i.d., our theoretical analysis reveals
that by setting $\gamma=\mathcal{O}(1/\sqrt{T})$ Algorithm 1 convergences at
the rate of ${\mathcal{O}}(1/\sqrt{T})$ to the statistical accuracy.444setting
$\gamma=\mathcal{O}(1/T)$, BGmD convergences at the rate of
${\mathcal{O}}(\frac{\log T}{T})$ under PLC and no corruption. This last
result can be established by using the concentration of the median-of-the-
means estimator [CSX17].

###  6.1 Proof Outline

Following [Sti18, KRSJ19, BDKD19], we start by defining a sequences of
averaged quantities. Divergent from these works however, due to the
adversarial setting being considered, we define these quantities over only the
uncorrupted samples:

$\displaystyle{\mathbf{g}}_{t}$
$\displaystyle=\frac{1}{|{\mathbb{G}}|}\sum_{i\in{\mathbb{G}}}{\mathbf{g}}_{t}^{i},\quad\bar{{\mathbf{g}}}_{t}=\mathbb{E}_{t}[{\mathbf{g}}_{t}]=\frac{1}{|{\mathbb{G}}|}\sum_{i\in{\mathbb{G}}}\nabla
f_{i}({\mathbf{x}}_{t}),$ (10) $\displaystyle{\mathbf{m}}_{t}$
$\displaystyle=\frac{1}{|{\mathbb{G}}|}\sum_{i\in{\mathbb{G}}}{\mathbf{M}}_{t}[i,:],\quad\Delta_{t}=\frac{1}{|{\mathbb{G}}|}\sum_{i\in{\mathbb{G}}}\Delta_{t}^{i},\quad{\mathbf{p}}_{t}=\frac{1}{|{\mathbb{G}}|}\sum_{i\in{\mathbb{G}}}{\mathbf{p}}_{t}^{i}=\gamma_{t}{\mathbf{g}}_{t}+{\mathbf{m}}_{t}.$

Notice that the BGmD cannot compute the above average sequences over the
uncorrupted samples, but it aims to approximate the aggregated stochastic
gradients of the reliable clients, i.e. ${\mathbf{g}}_{t}$, via the
Gm($\cdot$) oracle. Noting the definition of $\Delta_{t}$ in (10), the update
can be thought of as being a perturbed sequence with the perturbation quantity
${\mathbf{z}}_{t}:=\tilde{{\mathbf{g}}}_{t}-\textsc{Gm}(\\{\Delta_{t}^{i}\\}_{i\in{\mathcal{G}}}).$
Next, using the closeness of the Gm($\cdot$) oracle to the true average we
will establish the following lemmas to bound the perturbation.

######  Lemma 3 (Bounding the Memory).

Consider the setting of Algorithm 1 in iteration $t$ with compression factor
$\xi$ (Lemma 1), learning rate $\gamma$ and in presence of $\alpha-$corruption
(Definition 1). If further $f_{i}$ have bounded variance $\sigma^{2}$
(Assumption 1) we have

$\mathbb{E}\|\hat{{\mathbf{m}}}_{t}\|^{2}\leq
4(1-\xi^{2})\gamma^{2}\sigma^{2}\xi^{-2},\quad\forall i\in[n].$ (11)

######  Lemma 4 (Bounding the Perturbation).

Consider the setting of Algorithm 1 in iteration $t$ with compression factor
$\xi$ (Lemma 1), learning rate $\gamma$ and $\epsilon-$approximate Gm($\cdot$)
oracle in presence of $\alpha-$corruption (Definition 1). Under the assumption
that function $f_{i}$ are smooth (Assumption 2),

$\mathbb{E}\|{\mathbf{z}}_{t}\|^{2}\leq\frac{96\gamma^{2}\sigma^{2}}{(1-\alpha)^{2}}\left[1+\frac{4(1-\xi^{2})}{\xi^{2}}\right]+\frac{2\epsilon^{2}}{|{\mathbb{G}}|^{2}(1-\alpha)^{2}}.$
(12)

With the bound in Lemma 4, we define the following perturbed virtual sequences
for $i\in{\mathbb{G}}$

$\tilde{{\mathbf{x}}}_{t+1}^{i}=\tilde{{\mathbf{x}}}_{t}-\gamma{\mathbf{g}}_{t}^{i}-{\mathbf{z}}_{t},\quad\tilde{{\mathbf{x}}}_{0}^{i}={\mathbf{x}}_{0},\quad\tilde{{\mathbf{x}}}_{t+1}=\frac{1}{|{\mathbb{G}}|}\sum_{i\in{\mathbb{G}}}\tilde{{\mathbf{x}}}_{t+1}^{i}=\tilde{{\mathbf{x}}}_{t}-\gamma{\mathbf{g}}_{t}-{\mathbf{z}}_{t}$
(13)

Again, $\tilde{{\mathbf{x}}}_{t}$ can be though of as a perturbed version of
the SGD iterates over only the good samples $i\in{\mathbb{G}}$. Notice that
BGmD does not compute the virtual sequence and this sequence is defined merely
for the theoretical analysis. Therefore, it is essential to establish its
relation to ${{\mathbf{x}}}_{t}$, i.e. the iterates of BGmD. We do so in Lemma
5.

######  Lemma 5 (Memory as a Delayed Sequence).

Consider the setting of Algorithm 1 in iteration $t$. It holds that
${\mathbf{x}}_{t}-\tilde{{\mathbf{x}}}_{t}={\mathbf{m}}_{t}.$

The main challenge in showing this result is the presence of perturbations
${\mathbf{z}}_{t}$ in the resilient aggregation that we adopt in Algorithm 1.
Upon establishing this lemma, using smoothness we establish a bound on
suboptimality of the model learned at each iteration of BGmD as a function of
the perturbed virtual sequence $\tilde{{\mathbf{x}}}_{t}$.

######  Lemma 6 (Recursive Bounding of the Suboptimality).

For any $0<\rho<0.5$ it holds that

$\displaystyle\mathbb{E}_{t}[f(\tilde{{\mathbf{x}}}_{t+1})]$
$\displaystyle\leq
f(\tilde{{\mathbf{x}}}_{t})-\left(\frac{1}{2}-\rho\right)\frac{\gamma}{2}\|\nabla
f({\mathbf{x}}_{t})\|^{2}+\frac{3\gamma
L^{2}}{2}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}$ (14)
$\displaystyle\qquad\qquad+L\gamma^{2}\mathbb{E}_{t}\|{\mathbf{g}}_{t}\|^{2}+\left(L+\frac{1}{2\rho\gamma}+\frac{1}{2\gamma}\right)\mathbb{E}_{t}\|{\mathbf{z}}_{t}\|^{2}.$

The proofs are furnished by noting that the amount of perturbation can be
bounded by using smoothness and the PLC assumptions.

##  7 Empirical Evidence

In this section, we describe our experimental setup and present our empirical
findings and establish strong insights about the performance of BgmD. Table 2,
3 and 4 provide a summary of the results.

###  7.1 Experimental Setup

We use the following two important optimization setups for our experiments:

#### Homogeneous Samples

We trained a moderately large LeNet [LBBH98] style CNN with 1.16M parameters
on the challenging Fashion-MNIST [XRV17] dataset in the vanilla mini batch
setting with 32 parallel mini-batches each with batch size 64. The training
data was i.i.d among all the batches at each epoch. We use initial learning
rate of 0.01 which was decayed by $1\%$ at each epoch. Each experiment under
this setting was run for 50 epochs (full passes over training data). We also
train the same model on simple MNIST [LBBH98] dataset using mini-batch SGD
with 10 parallel batches each of size 64. We use a learning rate 0.001 updated
using cosine annealing scheduler along with a momentum 0.9.

#### Heterogeneous Samples

Our theoretical results (Theorem 1, 2) are established without any assumption
on how the data is distributed across batches. We verify this by training an
18-layer wide ResNet [HZRS16] with 11.2M parameters on CIFAR 10 [KSH12] in a
federated learning setting [MMR+17]. In this setting, at each iteration 10
parallel clients compute gradients over batch sizes of 128 and communicate
with the central server. The training data was distributed among the clients
in a non i.i.d manner only once at the beginning of training. Each experiment
was run for 200 epochs with an initial learning rate 0.1 , warm restarted via
cosine annealing.
To Simulate heterogeneous (non i.i.d) data distribution among clients we use
the following scheme: The entire training data was first sorted based on
labels and then contiguously divided into 80 equal data-shards
${\mathcal{D}}_{i}$ i.e. for Fashion-MNIST each data shard was assigned 750
samples. Each client was then randomly assigned 8 shards of data at the
beginning of training implying with high probability no client had access to
all classes of data ensuring heterogeneity [LSZ+18, LHY+19, DAH+20, KKM+20].

Common to all the experiments, we used the categorical cross entropy loss plus
an $\ell_{2}$ regularizer with weight decay value of $1\mathrm{e}{-4}$. All
the experiments are performed on a single 12 GB Titan Xp GPU. For
reproducibility, all the experiments are run with deterministic CuDNN back-
end. Further, each experiment is repeated 5 times with different random seeds
and confidence interval is noted in the Tables 2 4 and 3.

Table 2: Homogeneous Training: 1.12M parameter CNN trained on Fashion MNIST in regular i.i.d. setting. For all corruption types, test accuracy of BGmD is similar to that of GmD and surprisingly, in some cases even higher. As expected, SGD often diverges under corruption (empty entries in the table). CmD performs sub-optimally as corruption is increased. | Corruption (%) | SGD | CmD | BGmD | GmD
---|---|---|---|---|---
Clean | - | $\mathbf{89.39}{\color[rgb]{.5,.5,.5}\pm 0.28}$ | $83.82{\color[rgb]{.5,.5,.5}\pm 0.26}$ | $89.25{\color[rgb]{.5,.5,.5}\pm 0.19}$ | $88.98{\color[rgb]{.5,.5,.5}\pm 0.3}$
Gradient Attack
Bit Flip | 20 | - | $84.20{\color[rgb]{.5,.5,.5}\pm 0.02}$ | $\mathbf{88.42}{\color[rgb]{.5,.5,.5}\pm 0.16}$ | $88.07{\color[rgb]{.5,.5,.5}\pm 0.05}$
40 | - | $82.33{\color[rgb]{.5,.5,.5}\pm 1.60}$ | $\mathbf{85.67}{\color[rgb]{.5,.5,.5}\pm 0.09}$ | $85.57{\color[rgb]{.5,.5,.5}\pm 0.09}$
Additive | 20 | - | $72.55{\color[rgb]{.5,.5,.5}\pm 0.16}$ | $\mathbf{87.87}{\color[rgb]{.5,.5,.5}\pm 0.33}$ | $87.24{\color[rgb]{.5,.5,.5}\pm 0.16}$
40 | - | $41.04{\color[rgb]{.5,.5,.5}\pm 1.13}$ | $\mathbf{88.29}{\color[rgb]{.5,.5,.5}\pm 0.01}$ | $83.89{\color[rgb]{.5,.5,.5}\pm 0.08}$
Feature Attack
Additive Noise | 20 | - | $82.38{\color[rgb]{.5,.5,.5}\pm 0.13}$ | $\mathbf{86.76}{\color[rgb]{.5,.5,.5}\pm 0.03}$ | $86.63{\color[rgb]{.5,.5,.5}\pm 0.04}$
40 | - | $78.54{\color[rgb]{.5,.5,.5}\pm 0.65}$ | $\mathbf{82.27}{\color[rgb]{.5,.5,.5}\pm 0.06}$ | $81.23{\color[rgb]{.5,.5,.5}\pm 0.03}$
Impulse Noise | 20 | $79.18{\color[rgb]{.5,.5,.5}\pm 6.47}$ | $82.59{\color[rgb]{.5,.5,.5}\pm 0.60}$ | $\textbf{86.91}{\color[rgb]{.5,.5,.5}\pm 0.36}$ | $86.23{\color[rgb]{.5,.5,.5}\pm 0.03}$
40 | - | $78.03{\color[rgb]{.5,.5,.5}\pm 0.73}$ | $\mathbf{78.03}{\color[rgb]{.5,.5,.5}\pm 0.73}$ | $81.41{\color[rgb]{.5,.5,.5}\pm 0.12}$
Label Attack
Backdoor | 20 | $86.99{\color[rgb]{.5,.5,.5}\pm 0.02}$ | $76.38{\color[rgb]{.5,.5,.5}\pm 0.13}$ | $\mathbf{88.97}{\color[rgb]{.5,.5,.5}\pm 0.10}$ | $88.26{\color[rgb]{.5,.5,.5}\pm 0.04}$
40 | $73.01{\color[rgb]{.5,.5,.5}\pm 0.68}$ | $60.85{\color[rgb]{.5,.5,.5}\pm 1.24}$ | $\mathbf{84.69}{\color[rgb]{.5,.5,.5}\pm 0.31}$ | $81.32{\color[rgb]{.5,.5,.5}\pm 0.16}$
Table 3: Homogeneous Training:1.12M parameter CNN trained on MNIST in regular i.i.d. setting. For all corruption types, test accuracy of BGmD is similar to that of GmD and surprisingly, in some cases even higher. As expected, SGD fails to make progress under corruption . CmD performs sub-optimally as corruption is increased. | Corruption (%) | SGD | CmD | BGmD | GmD
---|---|---|---|---|---
Clean | - | $\mathbf{99.27}{\color[rgb]{.5,.5,.5}\pm 0.01}$ | $98.83{\color[rgb]{.5,.5,.5}\pm 0.02}$ | $99.09{\color[rgb]{.5,.5,.5}\pm 0.05}$ | $99.24{\color[rgb]{.5,.5,.5}\pm 0.02}$
Gradient Attack
Bit Flip | 20 | $9.51{\color[rgb]{.5,.5,.5}\pm 1.77}$ | $98.79{\color[rgb]{.5,.5,.5}\pm 0.01}$ | $\mathbf{99.06}{\color[rgb]{.5,.5,.5}\pm 0.02}$ | $98.98{\color[rgb]{.5,.5,.5}\pm 0.01}$
40 | $9.60{\color[rgb]{.5,.5,.5}\pm 2.04}$ | $93.69{\color[rgb]{.5,.5,.5}\pm 0.09}$ | $97.89{\color[rgb]{.5,.5,.5}\pm 0.05}$ | $\mathbf{98.11}{\color[rgb]{.5,.5,.5}\pm 0.12}$
Additive | 20 | $9.68{\color[rgb]{.5,.5,.5}\pm 0.11}$ | $94.26{\color[rgb]{.5,.5,.5}\pm 0.03}$ | $98.61{\color[rgb]{.5,.5,.5}\pm 0.01}$ | $\mathbf{98.69}{\color[rgb]{.5,.5,.5}\pm 0.01}$
40 | $9.74{\color[rgb]{.5,.5,.5}\pm 0.12}$ | $91.86{\color[rgb]{.5,.5,.5}\pm 0.03}$ | $\mathbf{97.78}{\color[rgb]{.5,.5,.5}\pm 0.27}$ | $92.78{\color[rgb]{.5,.5,.5}\pm 0.04}$
Table 4: Heterogeneous Training: ResNet-18 trained on CIFAR-10 in a federated setting under two gradient attack models. We observe similar trends as Tables 2 and 3 \- GmD and BGmD both remain robust at both 20% and 40% corruption maintaining high accuracy. At high corruptions BGmD achieves similar or even better performance than GmD while taking 3x less time. Interestingly, even in non-corrupt setting, BGmD outperforms SGD, perhaps due to the distributional shift introduced by non-i.i.d setting. Note that in i.i.d setting, our model achieves 94.8% accuracy with SGD | Corruption (%) | SGD | CmD | BGmD | GmD
---|---|---|---|---|---
Clean | - | $82.29{\color[rgb]{.5,.5,.5}\pm 1.32}$ | $85.50{\color[rgb]{.5,.5,.5}\pm 1.43}$ | $84.82{\color[rgb]{.5,.5,.5}\pm 0.76}$ | $\mathbf{85.65}{\color[rgb]{.5,.5,.5}\pm 0.48}$
Gradient Attack
Bit Flip | 20 | - | $80.87{\color[rgb]{.5,.5,.5}\pm 0.21}$ | ${84.56}{\color[rgb]{.5,.5,.5}\pm 0.06}$ | $\mathbf{88.07}{\color[rgb]{.5,.5,.5}\pm 0.05}$
40 | - | $77.41{\color[rgb]{.5,.5,.5}\pm 1.04}$ | $\mathbf{82.66}{\color[rgb]{.5,.5,.5}\pm 0.31}$ | $80.81{\color[rgb]{.5,.5,.5}\pm 0.01}$
Additive | 20 | $20.7{\color[rgb]{.5,.5,.5}\pm 1.56}$ | $54.75{\color[rgb]{.5,.5,.5}\pm 0.38}$ | $\mathbf{83.84}{\color[rgb]{.5,.5,.5}\pm 0.12}$ | $82.40{\color[rgb]{.5,.5,.5}\pm 0.90}$
40 | - | $23.35{\color[rgb]{.5,.5,.5}\pm 6.13}$ | $\mathbf{82.79}{\color[rgb]{.5,.5,.5}\pm 0.68}$ | $79.46{\color[rgb]{.5,.5,.5}\pm 0.24}$

(a) No corruption

(b) 10% Corruption

(c) 20% Corruption

(d) 40% Corruption

Figure 1: Robustness to Feature Corruption: We compare test set performance of
different schemes as a function of wall clock time for training Fashion MNIST
in i.i.d setting. These experiments are performed in presence of increasing
the fraction samples corrupted with impulse noise. At 40% corruption SGD
diverged and thus does not appear in the plot. Observe that BGmD is able to
maintain high accuracy in even presence of strong corruption and is at least
GmD while attaining at least 3x speedup over GmD.

(a) No corruption

(b) 10% Corruption

(c) 20% Corruption

(d) 40% Corruption

Figure 2: Robustness to Gradient Corruption: We train a CNN on Fashion MNIST
in the i.i.d setting in presence of scaled bit flip corruption of stochastic
gradients. Similar to Figure 1, BGmD achieves up to $\sim 3\times x$ speedup
over GmD while being robust. For high corruption $\%$, CmD converges to sub-
optimal solution.

(a) No corruption

(b) 10% Corruption

(c) 20% Corruption

(d) 40% Corruption

Figure 3: Robustness to Label Corruption: We train a CNN on Fashion-MNIST in
the i.i.d setting in presence of backdoor attack. BGmD achieves up to large
speedup over GmD while being robust even at very high corruptions where SGD
converges very slowly due to backdoor attack and converges to a sub-optimal
point at high 40% corruption.CmD converges to sub-optimal solution.

###  7.2 Corruption Simulation

We consider all three possible sources of error: corruption in features,
corruption in labels, and corruption in communicated gradients. All the
experiments are repeated for 0% (i.e. clean), 20% and 40% corruption levels,
i.e, $\psi=0,0.2,0.4$, respectively (see Definition 1).

#### Feature Corruption:

We consider corruption in the raw training data itself which can arise from
different issues related to data collection. Particularly, adopting the
corruptions introduced in [HD18], we use two noise models to directly apply to
the corrupt samples:
(i) Additive: Gaussian noise ${\mathbf{z}}_{i}\sim\mathcal{N}(0,100)$ directly
added to the image, and
(ii) Impulse: Salt and Pepper noise added by setting 90% of the pixels to 0 or
1.

(a) Original Image

(b) Gaussian Noise

(c) Salt & Pepper Noise

(d) Gaussian Blur

Figure 4: Feature Corruption: shows the effect of the perturbations added to
image.

(a) Clean Data

(b) 10% corruption

(c) 30% corruption

(d) 45% corruption

Figure 5: Gradient Corruption:This Toy example in 2 dimensions visually
demonstrates the superior robustness properties of Gm for robust mean
estimation (e.g. estimating the aggregated gradient) for increasing fraction
of (None to 45%) gradients corrupted with additive Gaussian noise.

#### Gradient Corruption:

In distributed training over multiple machines the communicated gradients can
be noisy, e.g., due to hardware issues or simply because some nodes are
adversarial and aim to maliciously disrupt the training. Using standard noise
models for gradient corruption [Fu98, XKG19, BWAA18] we directly corrupt the
gradients in the following manner:
(i) Additive: adversary adds random Gaussian noise
${\mathbf{z}}_{i}\sim\mathcal{N}(0,100)$ to the true gradient, and
(ii)Scaled Bit Flip: corrupted gradients ${\mathbf{g}}_{t}^{c}$ are the scaled
bit flipped version of the true gradient [BWAA18] estimate; in particular, we
use the following scale: ${\mathbf{g}}_{t}^{c}=-100{\mathbf{g}}_{t}$.

#### (c) Label Corruption:

We simulate the important real world backdoor attack [SS19, TTGL20] where the
goal of the adversary is to bias the classifier towards some adversary chosen
class. To simulate this behavior: at each iteration we flip the labels of
randomly chosen $\psi$ fraction of the samples to a target label (e.g. in
Fashion-MNIST we use 8:bag as the backdoor label).

#### Dynamic Corruption Strategy.

In order to represent a wide array of real world adversarial scenarios we use
the following dynamic corruption strategy: At each iteration, we randomly
sample $\psi$ fraction of the samples malicious. Note that this implies none
of the samples are trustworthy and thus makes the robust estimation problem
truly unsupervised. Note that, this is a strictly stronger and realistic
simulation of corruption compared to existing literature where a fixed set of
samples are treated as malicious throughout the training.

###  7.3 Discussion

#### Discussion on the Test Performance

In Table 2 we observe that without corruption both BgmD and GmD are able to
achieve similar accuracy as the baseline (i.e., SGD). Conversely, CmD has a
significant sub-optimality gap even in the clean setting. We observe the same
trend under different corruption models over various levels of corruption.
When corruption is high, SGD starts to diverge after a few iterations. While
CmD doesn’t diverge, at higher level of corruptions its performance
significantly degrades. On the other hand, both GmD and BGmD remain robust and
maintain their test accuracy as expected from thier strong theoretical
guarantees. Surprisingly, BGmD not only maintains similar robustness as GmD,
in several experiments it even outperforms the performance of GmD. We
hypothesize that this might be because of implicit regularization properties
of BGmD in over-parameterized settings and leave it as a future problem.

#### Discussion on the Relative Speedup.

The main goal of this work is to speed up Gm based robust optimization
methods. To this end, we verify the efficiency of different methods via
plotting the performance on test set as a function of the wall clock time.
Figure 1, 2 and 3 suggest that under a variety of corruption settings BgmD is
able to achieve significant speedup over GmD often by more than 3x while
maintaining similar (sometime even better) test performance as GmD.

#### Choice of $k$ and the Role of Memory

In order to study the importance the memory mechanism we train a 4-layer CNN
on MNIST [LBBH98] dataset while retaining $0<\beta\leq 1$ fraction of
coordinates, i.e., $k=\beta d$. Figure 6 shows that the training runs that
used memory (denoted by M) were able to achieve a similar accuracy while using
significantly fewer coordinates.

Figure 6: BGMD with different values of $k$ and with / without memory on MNIST
using CNN demonstrating the importance of memory augmentation

#### Discussion on Over parameterization

Intuitively, as a consequence of over-parameterization, large scale deep
learning models are likely to have sparse gradient estimates [SCCS19]. In the
context of robust optimization this would imply that performing robust
gradient estimation in a low-dimensional subspace has little to no impact in
the downstream optimization task especially in case of over-parameterized
models. Thus, by judiciously selecting a block of co-ordinates and performing
robust gradient estimation only in this low-dimensional subspace is a
practical approach to leverage highly robust estimators such as Gm even in
high dimensional setting which was previously intractable. This means BGmD
would be an attractive choice especially in overparameterized setting. In
order to validate this, we perform a small experiment: we take a tiny 412
parameter CNN and a large 1.16M parameter CNN and train both on simple MNIST
dataset. In addition to looking at the train and test performance we also
compute relative residual error
$1-\xi=\|{\mathbf{G}}_{t}-{\mathcal{C}}_{k}({\mathbf{G}}_{t})\|_{F}^{2}/\|{\mathbf{G}}_{t}\|_{F}^{2}$
Lemma 1 at each gradient step (iteration). We plot the relative residual,
train and test performance for different values of $k=\beta d$ where
$0<\beta\leq 1$ in Figure 7, 8. 555Just to clarify, both these experiments are
performed in clean setting

(a) Relative Residual

(b) Test Accuracy

(c) Train Loss

Figure 7: Large Model: We train an over-parameterized ($d$ = 1.16 M) parameter
CNN on MNIST [LBBH98] dataset. (a) shows relative residual error as a function
of iterations (gradient steps) (b) and (c) show the corresponding test and
training performance. The residual error starts to approaches zero as training
progresses even for very small values of $k$ explaining negligible impact on
training and test performance.

(a) Relative Residual

(b) Test Accuracy

(c) Train Loss

Figure 8: Tiny Model: Here we instead train a super tiny $d=412$ parameter CNN
on MNIST. (a),(b),(c) plots relative residual, train and test performance
respectively. We can see that even in this setting $(1-\xi)>k/d=\beta$ as we
remarked in Lemma 1. However, as training progresses the gradients become
closer to uniform explaining the optimality gap of BGmD with small values of
$k$.

It is clear from these experiments that in over-parameterized settings $\xi\to
0$ as training progresses potentially due to the inherent sparsity of
overparameterized models. This implies our block selection procedure is often
near lossless and thus BGmD even with aggressively small $k$ can achieve near
optimal performance. And since it is a few orders of magnitude faster than GmD
\- it is an attractive robust optimization algorithm in high dimensions.
However, in the tiny CNN setting, as training progresses the gradients tend to
become more uniform implying higher loss due to block co-ordinate selection.
This implies, in these settings, BGmD needs to use a larger $k$ in order to
retain the optimal performance. However, note that in these small scale
settings, GmD is not expensive and thus for robust optimization , a larger
value of $k$ or at the extreme $k=d$ i.e. running GmD can be practical.

#### Summary of Results

The above empirical observations highlight the following insights:
(a) For challenging corruption levels/models, Gm based methods are indeed
superior while standard SGD or CmD can be significantly inaccurate,
(b) In all of our reported experiments, BGmD was run with $k$ set to 10% of
the number of parameters. Despite using such a small ratio BGmD retains the
strong performance of GmD.
(c) By judiciously choosing $k$, BGmD is more efficient than GmD, and
(d) memory augmentation is vital for BGmD to attain a high accuracy while
employing relatively small values of $k$.

##  8 Conclusion

We proposed BGmD, a method for robust, large-scale, and high dimensional
optimization that achieves the optimal statistical breakdown point while
delivering significant savings in the computational costs per iteration
compared to existing Gm-based strategies. BGmD employs greedy coordinate
selection and memory augmentation which allows to aggressively select very few
coordinates while attaining strong convergence properties comparable to Gm-SGD
under standard non-convex settings. Extensive deep learning experiments
demonstrated the efficacy of BGmD.

##  9 Limitation

Currently, BGmD samples the coordinates for computing geometric median using
just the norm of each coordinate in the gradient matrix. In large deep
networks, the gradients should have more structure that cannot be captured
just by the norm of coordinates. We leave further investigation into
leveraging gradient structure for more effective coordinate selection for
future work.

##  10 Broader Impact

While the current work is more theoretical and algorithmic in nature, we
believe that robust learning – the main problem addressed in the work – is a
key requirement for deep learning systems to ensure that a few malicious data
points do not completely de-rail the system and produce offensive/garbage
output.

Missing Proofs of BgmD

##  Appendix A Proof of Lemma 1 (Sparse Approximation)

######  Lemma 1.

Algorithm 2 yields a contraction approximation, i.e.,
$\mathbb{E}_{{\mathcal{C}}_{k}}\left[\|{\mathcal{C}}_{k}({\mathbf{G}})-{\mathbf{G}}\|_{F}^{2}|{\mathbf{x}}\right]\leq(1-\xi)\|{\mathbf{G}}\|_{F}^{2},\;\frac{k}{d}\leq\xi\leq
1,$ where
${\mathcal{C}}_{k}({\mathbf{G}})_{i,j\in\omega_{k}}={\mathbf{G}}_{i,j},$ and
${\mathcal{C}}_{k}({\mathbf{G}})_{i,j\notin\omega_{k}}=0$.

###### Proof.

Suppose, $\Omega_{k}=\\{\omega\subseteq\\{1,2,...,d\\}:|\omega|=k\\}$ is the
set of all possible subsets of cardinality $k$ i.e.
$|\Omega_{k}|=\binom{d}{k}$. Also let the embeddings produced by random co-
ordinate sampling and active norm sampling (Algorithm 2) are denoted by
${\mathcal{C}}^{r}_{k}(\cdot)$ and ${\mathcal{C}}^{n}_{k}(\cdot)$ respectively
and let the $i-$th row ${\mathbf{G}}_{t}[i,:]={\mathbf{g}}_{t}^{i}$. Then, we
can bound the reconstruction error in expectation
$\forall{\mathbf{G}}_{t}\in{\mathbb{R}}^{b\times d}$ as:

$\displaystyle\mathbb{E}_{{\mathcal{C}}^{n}_{k}}\left[\|{\mathcal{C}}^{n}_{k}({\mathbf{G}}_{t})-{\mathbf{G}}_{t}\|_{F}^{2}|{\mathbf{G}}\right]$
$\displaystyle\leq\mathbb{E}_{{\mathcal{C}}^{n}_{k}}\left[\|{\mathcal{C}}^{r}_{k}({\mathbf{G}}_{t})-{\mathbf{G}}_{t}\|^{2}|{\mathbf{G}}_{t}\right]$
$\displaystyle=\sum_{i=1}^{n}\mathbb{E}_{{\mathcal{C}}^{n}_{k}}\left[\|{\mathcal{C}}^{r}_{k}({\mathbf{g}}_{t}^{i})-{\mathbf{g}}_{t}^{i}\|^{2}|{\mathbf{g}}_{t}^{i}\right]$
$\displaystyle=\sum_{i=1}^{n}\frac{1}{|\Omega_{k}|}\sum_{\omega\in\Omega_{k}}\sum_{i=1}^{d}{\mathbf{x}}_{i}^{2}\mathbb{I}\\{i\notin\omega\\}$
$\displaystyle=\sum_{i=1}^{n}(1-\frac{k}{d})\|{\mathbf{g}}_{t}^{i}\|^{2}$
$\displaystyle=(1-\frac{k}{d})\|{\mathbf{G}}_{t}\|^{2}_{F}$

This concludes the proof. ∎

##  Appendix B Computational Complexity of BGmD iterates

######  Proposition 1.

(Computational Complexity). Given an $\epsilon$\- approximate Gm oracle , each
gradient aggregation of BGmD with block size $k$ incurs a computational cost
of: ${\mathcal{O}}(\frac{k}{\epsilon^{2}}+bd)$.

###### Proof.

Let us first recall, one gradient aggregation operation: given $b$ stochastic
gradients ${\mathbf{g}}_{i}\;\forall i\in[b]$, the goal of the aggregation
step is to compute $\tilde{{\mathbf{g}}}$ for subsequent iterations of the
form ${\mathbf{x}}_{t+1}={\mathbf{x}}_{t}-\eta\tilde{g}$. Further,
${\mathbf{G}}_{t}\in{\mathbb{R}}^{b\times d}$ denote the gradient jacobian
where $i$ th row ${\mathbf{G}}_{t}[i,:]$ corresponds to ${\mathbf{g}}_{i}$.
Also assume that we have at our disposal an oracle $\textsc{Gm}(\cdot)$ that
can compute an $\epsilon$-approximate Gm
${\mathbf{g}}_{i}\in{\mathbb{R}}^{d}\;\forall i\in[b]$ using
${\mathcal{O}}(\frac{d}{\epsilon^{2}})$ compute [CLM+16]. Recall that BGmD
(Algorithm 1) is composed of the following main steps:
• Memory Augmentation: At each gradient aggregation step, BgmD needs to add
back the stored memory $\hat{{\mathbf{m}}}_{t}$ compensating for accumulated
residual error incurred in previous iterations to ${\mathbf{G}}_{t}$ such that
${\mathbf{G}}_{t}[i,:]=\gamma{\mathbf{G}}_{t}[i,:]+\hat{{\mathbf{m}}}_{t}$.
Note that, this is a row wise linear (addition) operation implying
${\mathcal{O}}(bd)$ associated cost.
• Active Norm Sampling: At each gradient aggregation step: BgmD selects $k$ of
the $d$ coordinates i.e. $k$ columns of ${\mathbf{G}}_{t}$ using Algorithm 2.
This requires computing the $\ell_{2}$ norm distribution along the $d$
columns, followed by sampling $k$ of them proportional to the norm
distribution. The computational complexity of computing Active Norm Sampling
is ${\mathcal{O}}(bd)$ [WS17].
• Compute ${\mathbf{M}}_{t+1}$: Further, memory needs to be updated to
${\mathbf{M}}_{t+1}$ for future iterates implying another row wise linear
operation incurring ${\mathcal{O}}(bd)$ compute.
• Low Rank Gm: Note that BGmD needs to run $\textsc{Gm}(\cdot)$ over
${\mathbb{R}}^{k}$ implying a cost of ${\mathcal{O}}(\frac{k}{\epsilon^{2}})$.
Putting it together, the total cost of computing gradient aggregation per
iteration using Algorithm 1 is then
${\mathcal{O}}(\frac{k}{\epsilon^{2}}+bd)$. This concludes the proof. ∎

##  Appendix C Proof of Lemma 2

######  Lemma 2.

(Choice of k) Let $k\leq{\mathcal{O}}(\frac{1}{F}-b\epsilon^{2})\cdot d$.
Then, given an $\epsilon$\- approximate Gm oracle, Algorithm 1 achieves a
factor $F$ speedup over Gm-SGD for aggregating $b$ samples.

###### Proof.

First, note that: for one step of gradient aggregation Gm-SGD makes one call
to Gm($\cdot$) oracle implying a ${\mathcal{O}}(\frac{d}{\epsilon^{2}})$
computational cost per gradient aggregation.
Now, let us assume, $k=\beta d$ where $0<\beta\leq 1$ denotes the fraction of
total gradient dimensions retained by BGmD. Then using Proposition 1 we can
find a bound on $\beta$ such that gradient aggregation step of BGmD has a
linear speedup over that of Gm-SGD by a linear factor $F$.

$\displaystyle{\mathcal{O}}(\frac{d}{\epsilon^{2}})\geq
F\cdot{\mathcal{O}}(\frac{k}{\epsilon^{2}}+bd)$ (15)
$\displaystyle\Rightarrow$
$\displaystyle{\mathcal{O}}(\frac{1}{\epsilon^{2}})\geq{\mathcal{O}}(\frac{F\beta}{\epsilon^{2}})+{\mathcal{O}}(Fb)$
$\displaystyle\Rightarrow$
$\displaystyle{\mathcal{O}}(F\beta)\leq{\mathcal{O}}(1)-{\mathcal{O}}(Fb\epsilon^{2})$
$\displaystyle\Rightarrow$
$\displaystyle{\mathcal{O}}(\beta)\leq{\mathcal{O}}(\frac{1}{F})-{\mathcal{O}}(b\epsilon^{2})$

This concludes the proof. ∎

##  Appendix D Detailed Statements of the convergence Theorems

We here state the full version of the main convergence theorems

######  Theorem 1 (Smooth Non-convex).

Consider the general case where the functions $f_{i}$ correspond to non-
corrupt samples $i\in{\mathbb{G}}$ i.e.
$f=\frac{1}{{\mathbb{G}}}\sum_{i\in{\mathbb{G}}}f_{i}(\mathbf{x})$ are non-
convex and smooth (Assumption 2). Define,
$R_{0}:=f({\mathbf{x}}_{0})-f({\mathbf{x}}^{\ast})$ where
${\mathbf{x}}^{\ast}$ is the true optima and ${\mathbf{x}}_{0}$ is the initial
parameters. Run Algorithm 1 with compression factor $\xi$ (Lemma 1), learning
rate $\gamma=1/2L$ and $\epsilon-$approximate Gm($\cdot$) oracle in presence
of $\alpha-$corruption (Definition 1) for $T$ iterations. Then it holds that:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f({\mathbf{x}}_{t})\|^{2}$ $\displaystyle\leq\frac{8R_{0}}{\gamma
T}+8L\gamma\sigma^{2}+\frac{48L^{2}\gamma^{2}\sigma^{2}(1-\xi^{2})}{\xi^{2}}$
(16)
$\displaystyle+\frac{2304\sigma^{2}}{(1-\alpha)^{2}}\left[1+\frac{4(1-\xi^{2})}{\xi^{2}}\right]+\frac{48\epsilon^{2}}{\gamma^{2}|{\mathbb{G}}|^{2}(1-\alpha)^{2}}$
$\displaystyle={\mathcal{O}}\Bigg{(}\frac{LR_{0}}{T}+\frac{\sigma^{2}\xi^{-2}}{(1-\alpha)^{2}}+\frac{L^{2}\epsilon^{2}}{|{\mathbb{G}}|^{2}(1-\alpha)^{2}}\Bigg{)}$

######  Theorem 2 (Non-convex under PLC).

Assume in addition to non-convex and smooth (Assumption 2) the functions
$f_{i}$ correspond to non-corrupt samples also satisfy the Polyak-Łojasiewicz
Condition (Assumption 3) with parameter $\mu$. After $T$ iterations Algorithm
1 with compression factor $\xi$ (Lemma 1), learning rate $\gamma=1/4L$ and
$\epsilon-$approximate Gm($\cdot$) oracle in presence of $\alpha-$corruption
(Definition 1) satisfies:

$\displaystyle\mathbb{E}\|\hat{{\mathbf{x}}}_{T}-{\mathbf{x}}^{\ast}\|^{2}$
$\displaystyle\leq\frac{16(f({\mathbf{x}}_{0})-f^{\ast})}{\mu^{2}\gamma}\left[1-\frac{\mu\gamma}{2}\right]^{T}+\frac{16L\gamma\sigma^{2}}{\mu^{2}}+\left[\frac{80\gamma^{2}\sigma^{2}L^{2}(1-\xi^{2})}{\mu^{2}\xi^{2}}\right]$
(17)
$\displaystyle+\frac{3072\sigma^{2}}{\mu^{2}(1-\alpha)^{2}}\left[1+\frac{4(1-\xi^{2})}{\xi^{2}}\right]+\frac{64\epsilon^{2}}{\mu^{2}\gamma^{2}|{\mathbb{G}}|^{2}(1-\alpha)^{2}}$
$\displaystyle={\mathcal{O}}\Bigg{(}\frac{LR_{0}}{\mu^{2}}\left[1-\frac{\mu}{8L}\right]^{T}+\frac{\sigma^{2}\xi^{-2}}{\mu^{2}(1-\alpha)^{2}}+\frac{L^{2}\epsilon^{2}}{\mu^{2}|{\mathbb{G}}|^{2}(1-\alpha)^{2}}\Bigg{)}$

for a global optimal solution ${\mathbf{x}}^{\ast}\in{\mathcal{X}}^{\ast}$.
Here,
$\hat{{\mathbf{x}}}_{T}:=\frac{1}{W_{T}}\sum_{t=0}^{T-1}w_{t}{\mathbf{x}}_{t}$
with weights $w_{t}:=(1-\frac{\mu}{8L})^{-(t+1)}$,
$W_{T}:=\sum_{t=0}^{T-1}w_{t}$.

##  Appendix E Useful Facts

######  Fact 1.

$\mathbb{E}\|\sum_{i\in{\mathcal{A}}}{\mathbf{a}}_{i}\|^{2}\leq|{\mathcal{A}}|\sum_{i\in{\mathcal{A}}}\mathbb{E}\|{\mathbf{a}}_{i}\|^{2}$
This can be seen as a consequence of the Jensen’s inequality.

######  Fact 2 (Young’s Inequality).

For any $\beta>0$,

$\mathbb{E}[\langle{\mathbf{a}},{\mathbf{b}}\rangle]\leq\frac{\beta}{2}\mathbb{E}\|{\mathbf{a}}\|^{2}+\frac{1}{2\beta}\mathbb{E}\|{\mathbf{b}}\|^{2}$
(18)

This can be seen as a special case of the weighted AM-GM inequality.

######  Fact 3 (Lemma 2 in [Sti19]).

Let $\\{a_{t}\\}$ and $\\{b_{t}\\}$ be to non-negative sequences such that

$a_{t+1}\leq(1-r\gamma)a_{t}-s\gamma b_{t}+c,$ (19)

where $r,\gamma,s,c>0$ and $r\gamma<1$. Let $w_{t}=(1-r\gamma)^{-(t+1)}$ and
$W_{T}=\sum_{t=0}^{T-1}w_{t}$. Then the following holds:

$\frac{s}{W_{T}}\sum_{t=0}^{T-1}b_{t}w_{t}+ra_{T}\leq\frac{a_{0}}{\gamma}(1-r\gamma)^{T}+\frac{c}{\gamma}.$
(20)

######  Fact 4.

Let $f$ be a function that satisfies PLC (Assumption 3) with parameter $\mu$.
Then, $f$ satisfies the quadratic growth condition [KNS16, Zha20]:

$f({\mathbf{x}})-f^{\ast}\geq\frac{\mu}{2}\|{\mathbf{x}}-{\mathbf{x}}_{p}\|^{2}$
(21)

where ${\mathbf{x}}_{p}$ is the projection of ${\mathbf{x}}$ onto the solution
set ${\mathcal{X}}^{\ast}$ .

##  Appendix F Proof of Lemma 3

###### Proof.

The result is due to Lemma 5 in [BDKD19] which is inspired by Lemma 3 in
[KRSJ19]. The proof relies on using the fact that the proposed norm sampling
operator ${\mathcal{C}}_{k}$, as shown in Lemma 1 is contractive. Hence, we
can use this property to derive a recursive bound on the norm of the memory.
Using this result as well as the bounded stochastic gradient assumption
results in a geometric sum that can be bounded by the RHS of (11). ∎

##  Appendix G Proof of Lemma 4

###### Proof.

Since $\tilde{{\mathbf{g}}}_{t}$ is the $\epsilon$-accurate Gm of
$\\{\Delta_{t}^{i}\\}_{i}$, ${\mathbf{z}}_{t}$ can be thought of as the
$\epsilon$-accurate Gm of $\\{\Delta_{t}^{i}-\Delta_{t}\\}_{i}$. Thus, by the
classical robustness property of Gm (Theorem. 2.2 in [LR+91]; see also [M+15,
CLM+16, CSX17, LXC+19, WLCG20] for similar adaptations) we have

$\mathbb{E}\|{\mathbf{z}}_{t}\|^{2}\leq\frac{8|{\mathbb{G}}|}{(|{\mathbb{G}}|-|{\mathbb{B}}|)^{2}}\sum_{i\in{\mathbb{G}}}\mathbb{E}\|\Delta_{t}^{i}-\Delta_{t}\|^{2}+\frac{2\epsilon^{2}}{(|{\mathbb{G}}|-|{\mathbb{B}}|)^{2}}.$
(22)

Next, we bound $\mathbb{E}\|\Delta_{t}^{i}-\Delta_{t}\|^{2}$ using the
properties of memory mechanism stated in Lemma 3 with $H=1$ as:

$\displaystyle\mathbb{E}\|\Delta_{t}^{i}-\Delta_{t}\|^{2}$
$\displaystyle=2\mathbb{E}\|\Delta_{t}^{i}\|^{2}+2\mathbb{E}\|\Delta_{t}\|^{2}$
(23) $\displaystyle\leq
2\mathbb{E}\|\Delta_{t}^{i}\|^{2}+\frac{2}{|{\mathbb{G}}|}\sum_{i\in{\mathbb{G}}}\mathbb{E}\|\Delta_{t}^{i}\|^{2}$
$\displaystyle\leq 4\max_{i\in{\mathbb{G}}}\mathbb{E}\|\Delta_{t}^{i}\|^{2},$

where we used Fact 1 twice. Next, we establish a bound on the norm of the
communicated messages as follows. Add add and subtract ${\mathbf{p}}_{t}^{i}$
and use the update rule of the memory to obtain

$\displaystyle\mathbb{E}\|\Delta_{t}^{i}\|^{2}$
$\displaystyle=\mathbb{E}\|\Delta_{t}^{i}+{\mathbf{p}}_{t}^{i}-{\mathbf{p}}_{t}^{i}\|^{2}$
(24)
$\displaystyle=\mathbb{E}\|{\mathbf{p}}_{t}^{i}-\hat{{\mathbf{m}}}_{t+1}\|^{2}$
$\displaystyle=\mathbb{E}\|\gamma{\mathbf{g}}_{t}^{i}+\hat{{\mathbf{m}}}_{t}-\hat{{\mathbf{m}}}_{t+1}\|^{2}$
$\displaystyle\leq
3\mathbb{E}\|\gamma{\mathbf{g}}_{t}^{i}\|^{2}+3\mathbb{E}\|\hat{{\mathbf{m}}}_{t}\|^{2}+3\mathbb{E}\|\hat{{\mathbf{m}}}_{t+1}\|^{2},$
$\displaystyle\leq
3\gamma^{2}\sigma^{2}+3\mathbb{E}\|\hat{{\mathbf{m}}}_{t}\|^{2}+3\mathbb{E}\|\hat{{\mathbf{m}}}_{t+1}\|^{2},$

by definition of ${\mathbf{p}}_{t}^{i}$ and Fact 1. Notice that using Lemma 3
with $H=1$ we can uniformly bound the last two terms on the RHS of (24):

$\displaystyle
3\mathbb{E}\|\hat{{\mathbf{m}}}_{t}\|^{2}+3\mathbb{E}\|\hat{{\mathbf{m}}}_{t+1}\|^{2}\leq\frac{24(1-\xi^{2})\gamma^{2}\sigma^{2}}{\xi^{2}}.$
(25)

Therefore, we conclude

$\displaystyle\mathbb{E}\|\Delta_{t}^{i}\|^{2}$ $\displaystyle\leq
3\gamma^{2}\sigma^{2}+\frac{24(1-\xi^{2})\gamma^{2}\sigma^{2}}{\xi^{2}}.$ (26)

Therefore, by (23) and (26)

$\displaystyle\mathbb{E}\|\Delta_{t}^{i}-\Delta_{t}\|^{2}$ $\displaystyle\leq
12\gamma^{2}\sigma^{2}\left[1+\frac{4(1-\xi^{2})}{\xi^{2}}\right],$ (27)

and the proof is complete by combining this last result with (22). ∎

##  Appendix H Proof of Lemma 5

###### Proof.

We derive a recursive relation for the difference
${\mathbf{x}}_{t+1}-\tilde{{\mathbf{x}}}_{t+1}$. It follows that

$\displaystyle{\mathbf{x}}_{t+1}$
$\displaystyle={\mathbf{x}}_{t}-\tilde{{\mathbf{g}}}_{t}$ (28)
$\displaystyle={\mathbf{x}}_{t}-\Delta_{t}-{\mathbf{z}}_{t}.$

On the other hand,

$\displaystyle\tilde{{\mathbf{x}}}_{t+1}$
$\displaystyle=\tilde{{\mathbf{x}}}_{t}-\gamma{\mathbf{g}}_{t}-\gamma{\mathbf{z}}_{t}$
(29)
$\displaystyle=\tilde{{\mathbf{x}}}_{t}-\gamma{\mathbf{g}}_{t}-{\mathbf{z}}_{t}$
$\displaystyle=\tilde{{\mathbf{x}}}_{t}-\gamma{\mathbf{g}}_{t}-{\mathbf{z}}_{t},$

Collectively, (28) and (29) imply

$\displaystyle{\mathbf{x}}_{t+1}-\tilde{{\mathbf{x}}}_{t+1}$
$\displaystyle=({\mathbf{x}}_{t}-\tilde{{\mathbf{x}}}_{t})+(\gamma{\mathbf{g}}_{t}-\Delta_{t}).$
(30)

Since ${\mathbf{y}}_{0}=\tilde{{\mathbf{y}}}_{0}$ using induction yields

$\displaystyle{\mathbf{x}}_{t+1}-\tilde{{\mathbf{x}}}_{t+1}$
$\displaystyle=\sum_{j=0}^{t}(\gamma{\mathbf{g}}_{t}-\Delta_{j})$ (31)
$\displaystyle=\sum_{j=0}^{t}({\mathbf{m}}_{j+1}-{\mathbf{m}}_{j})$
$\displaystyle={\mathbf{m}}_{t+1}-{\mathbf{m}}_{0}={\mathbf{m}}_{t+1},$

where we used the fact that ${\mathbf{m}}_{0}=\mathbf{0}$. ∎

##  Appendix I Proof of Lemma 6

###### Proof.

Recall that
${\mathbf{g}}_{t}=\frac{1}{|{\mathbb{G}}|}\sum_{i\in{\mathbb{G}}}\nabla
f_{i}({\mathbf{x}}_{t},z_{t}^{i})$, i.e., the average of stochastic gradients
ove uncorrupted samples at time $t$, and
$\mathbb{E}[{\mathbf{g}}_{t}]=\bar{{\mathbf{g}}_{t}}$. By the definition of
$L$-smoothness (see Assumption 2), we have

$\displaystyle f(\tilde{{\mathbf{x}}}_{t+1})$ $\displaystyle\leq
f(\tilde{{\mathbf{x}}}_{t})+\langle\nabla
f(\tilde{{\mathbf{x}}}_{t}),\tilde{{\mathbf{x}}}_{t+1}-\tilde{{\mathbf{x}}}_{t}\rangle+\frac{L}{2}\|\tilde{{\mathbf{x}}}_{t+1}-\tilde{{\mathbf{x}}}_{t}\|^{2}$
(32) $\displaystyle=f(\tilde{{\mathbf{x}}}_{t})+\langle\nabla
f(\tilde{{\mathbf{x}}}_{t}),-\gamma{\mathbf{g}}_{t}-{\mathbf{z}}_{t}\rangle+\frac{L}{2}\|\gamma{\mathbf{g}}_{t}+{\mathbf{z}}_{t}\|^{2}$
$\displaystyle\leq f(\tilde{{\mathbf{x}}}_{t})-\gamma\langle\nabla
f(\tilde{{\mathbf{x}}}_{t}),{\mathbf{g}}_{t}\rangle-\langle\nabla
f(\tilde{{\mathbf{x}}}_{t}),{\mathbf{z}}_{t}\rangle+L\gamma^{2}\|{\mathbf{g}}_{t}\|^{2}+L\|{\mathbf{z}}_{t}\|^{2}.$

Let $\mathbb{E}_{t}$ denote expectation with respect to sources of randomness
in computation of stochastic gradients at time $t$. Then,

$\displaystyle\mathbb{E}_{t}[f(\tilde{{\mathbf{x}}}_{t+1})]$
$\displaystyle\leq f(\tilde{{\mathbf{x}}}_{t})-\gamma\langle\nabla
f(\tilde{{\mathbf{x}}}_{t}),\bar{{\mathbf{g}}}_{t}\rangle-\mathbb{E}_{t}[\langle\nabla
f(\tilde{{\mathbf{x}}}_{t}),{\mathbf{z}}_{t}\rangle]+L\gamma^{2}\mathbb{E}_{t}\|{\mathbf{g}}_{t}\|^{2}+L\mathbb{E}_{t}\|{\mathbf{z}}_{t}\|^{2}.$
(33)

The first inner-product in (33) can be bounded according to

$\displaystyle 2\langle\nabla
f(\tilde{{\mathbf{x}}}_{t}),\bar{{\mathbf{g}}}_{t}\rangle$
$\displaystyle=\|\nabla
f(\tilde{{\mathbf{x}}}_{t})\|^{2}+\|\bar{{\mathbf{g}}}_{t}\|^{2}-\|\nabla
f(\tilde{{\mathbf{x}}}_{t})-\bar{{\mathbf{g}}}_{t}\|^{2}$ (34)
$\displaystyle\geq\|\nabla f(\tilde{{\mathbf{x}}}_{t})\|^{2}-\|\nabla
f(\tilde{{\mathbf{x}}}_{t})-\bar{{\mathbf{g}}}_{t}\|^{2}$
$\displaystyle=\|\nabla
f(\tilde{{\mathbf{x}}}_{t})\|^{2}-\|\frac{1}{|{\mathbb{G}}|}\sum_{i\in{\mathbb{G}}}\nabla
f_{i}(\tilde{{\mathbf{x}}}_{t})-\frac{1}{|{\mathbb{G}}|}\sum_{i\in{\mathbb{G}}}\nabla
f_{i}({\mathbf{x}}_{t})\|^{2}$ $\displaystyle\geq\|\nabla
f(\tilde{{\mathbf{x}}}_{t})\|^{2}-\frac{1}{|{\mathbb{G}}|}\sum_{i\in{\mathbb{G}}}\|\nabla
f_{i}(\tilde{{\mathbf{x}}}_{t})-\nabla f_{i}({\mathbf{x}}_{t})\|^{2}$
$\displaystyle\geq\|\nabla
f(\tilde{{\mathbf{x}}}_{t})\|^{2}-L^{2}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}$
$\displaystyle=\|\nabla
f(\tilde{{\mathbf{x}}}_{t})\|^{2}+L^{2}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}-2L^{2}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}$
$\displaystyle\geq\|\nabla f(\tilde{{\mathbf{x}}}_{t})\|^{2}+\|\nabla
f(\tilde{{\mathbf{x}}}_{t})-\nabla
f({\mathbf{x}}_{t})\|^{2}-2L^{2}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}$
$\displaystyle=\|\nabla f(\tilde{{\mathbf{x}}}_{t})\|^{2}+\|\nabla
f(\tilde{{\mathbf{x}}}_{t})-\nabla
f({\mathbf{x}}_{t})\|^{2}-2L^{2}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}$
$\displaystyle\geq\frac{1}{2}\|\nabla
f({\mathbf{x}}_{t})\|^{2}-2L^{2}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2},$

where we employed Fact 1 and $L$-smoothness of each function several times.
Therefore,

$\displaystyle-\gamma\langle\nabla
f(\tilde{{\mathbf{x}}}_{t}),\bar{{\mathbf{g}}}_{t}\rangle\leq-\frac{\gamma}{4}\|\nabla
f({\mathbf{x}}_{t})\|^{2}+\gamma
L^{2}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}.$ (35)

We now bound the second inner-product. To this end,

$\displaystyle-\mathbb{E}_{t}[\langle\nabla
f(\tilde{{\mathbf{x}}}_{t}),{\mathbf{z}}_{t}\rangle]$
$\displaystyle=-\mathbb{E}_{t}[\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}\rangle]+\mathbb{E}_{t}[\langle\nabla
f({\mathbf{x}}_{t})-\nabla
f(\tilde{{\mathbf{x}}}_{t}),{\mathbf{z}}_{t}\rangle]$ (36)
$\displaystyle\leq\rho\gamma\|\nabla
f({\mathbf{x}}_{t})\|^{2}+\frac{1}{2\rho\gamma}\mathbb{E}_{t}\|{\mathbf{z}}_{t}\|^{2}+\mathbb{E}_{t}[\langle\nabla
f({\mathbf{x}}_{t})-\nabla
f(\tilde{{\mathbf{x}}}_{t}),{\mathbf{z}}_{t}\rangle]$
$\displaystyle\leq\frac{\rho\gamma}{2}\|\nabla
f({\mathbf{x}}_{t})\|^{2}+\frac{1}{2\rho\gamma}\mathbb{E}_{t}\|{\mathbf{z}}_{t}\|^{2}+\frac{1}{2\gamma}\mathbb{E}_{t}\|{\mathbf{z}}_{t}\|^{2}+\frac{\gamma}{2}\|\nabla
f({\mathbf{x}}_{t})-\nabla f(\tilde{{\mathbf{x}}}_{t})\|^{2}$
$\displaystyle\leq\frac{\rho\gamma}{2}\|\nabla
f({\mathbf{x}}_{t})\|^{2}+\left(\frac{1}{2\rho\gamma}+\frac{1}{2\gamma}\right)\mathbb{E}_{t}\|{\mathbf{z}}_{t}\|^{2}+\frac{\gamma
L^{2}}{2}\|{\mathbf{x}}_{t}-\tilde{{\mathbf{x}}}_{t}\|^{2},$

where we used Fact 2 twice and to obtain the last inequality we employed the
smoothness assumption. Here, $0<\rho<0.5$ is a parameter whose value will be
determined later.

Application of (35) and (36) in (33) yields

$\displaystyle\mathbb{E}_{t}[f(\tilde{{\mathbf{x}}}_{t+1})]$
$\displaystyle\leq
f(\tilde{{\mathbf{x}}}_{t})-\left(\frac{1}{2}-\rho\right)\frac{\gamma}{2}\|\nabla
f({\mathbf{x}}_{t})\|^{2}+\frac{3\gamma
L^{2}}{2}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}$ (37)
$\displaystyle\qquad\qquad+L\gamma^{2}\mathbb{E}_{t}\|{\mathbf{g}}_{t}\|^{2}+\left(L+\frac{1}{2\rho\gamma}+\frac{1}{2\gamma}\right)\mathbb{E}_{t}\|{\mathbf{z}}_{t}\|^{2}.$

∎

##  Appendix J Proof of Theorem 1

###### Proof.

Rearranging (37) and taking expectation with respect to the entire sources of
randomness, i.e. the proposed coordinated sparse approximation and the
randomness in computation of stochastic gradient in iterations $0,\dots,t-1$,
using the bounded SFO assumption yields

$\displaystyle\left(\frac{1}{2}-\rho\right)\frac{\gamma}{2}\mathbb{E}\|\nabla
f({\mathbf{x}}_{t})\|^{2}\leq$
$\displaystyle\mathbb{E}[f(\tilde{{\mathbf{x}}}_{t})]-\mathbb{E}[f(\tilde{{\mathbf{x}}}_{t+1})]+\frac{3\gamma
L^{2}}{2}\mathbb{E}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}$ (38)
$\displaystyle+L\gamma^{2}\sigma^{2}+\left(L+\frac{1}{2\rho\gamma}+\frac{1}{2\gamma}\right)\mathbb{E}\|{\mathbf{z}}_{t}\|^{2}.$

Evidently, we need to bound two quantities in (38). Lemma 4 establishes a
bound on $\mathbb{E}\|{\mathbf{z}}_{t}\|^{2}$ while by Lemma 5

$\displaystyle\mathbb{E}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}=\mathbb{E}\|{\mathbf{m}}_{t}\|^{2}$
$\displaystyle\leq\frac{1}{|{\mathbb{G}}|}\sum_{i\in{\mathbb{G}}}\mathbb{E}\|\hat{{\mathbf{m}}}_{t}\|^{2}\leq\frac{4(1-\xi^{2})\gamma^{2}\sigma^{2}}{\xi^{2}}$
(39)

using Lemma 3 with $H=1$ we get :

$\displaystyle\left(\frac{1}{2}-\rho\right)\frac{\gamma}{2}\mathbb{E}\|\nabla
f({\mathbf{x}}_{t})\|^{2}\leq$
$\displaystyle\mathbb{E}[f(\tilde{{\mathbf{x}}}_{t})]-\mathbb{E}[f(\tilde{{\mathbf{x}}}_{t+1})]+L\gamma^{2}\sigma^{2}$
(40) $\displaystyle+\frac{6\gamma
L^{2}(1-\xi^{2})\gamma^{2}\sigma^{2}}{\xi^{2}}$
$\displaystyle+\left(L+\frac{1}{2\rho\gamma}+\frac{1}{2\gamma}\right)\frac{96\gamma^{2}\sigma^{2}}{(1-\alpha)^{2}}\left[1+\frac{4(1-\xi^{2})}{\xi^{2}}\right]$
$\displaystyle+\left(L+\frac{1}{2\rho\gamma}+\frac{1}{2\gamma}\right)\frac{2\epsilon^{2}}{|{\mathbb{G}}|^{2}(1-\alpha)^{2}}.$

Finally, letting $\rho=1/4$ and $\gamma=\frac{1}{2L}$ we obtain the stated
result by averaging (40) over time and noting
$f^{\ast}\leq\mathbb{E}[f(\tilde{{\mathbf{x}}}_{T})]$ and
$f(\tilde{{\mathbf{x}}}_{0})=f({\mathbf{x}}_{0})$. ∎

##  Appendix K Proof of Theorem 2

Recall (38) in the proof of Theorem 1. Let
$a_{t}:=\mathbb{E}[f(\tilde{{\mathbf{x}}}_{t})]-f^{\ast}\geq 0$. Using
Assumption 3 to bound the gradient terms in (38) yields

$\displaystyle a_{t+1}\leq$ $\displaystyle
a_{t}-\left(\frac{1}{2}-\rho\right)\gamma\mu\mathbb{E}[f({\mathbf{x}}_{t})-f^{\ast}]+\frac{3\gamma
L^{2}}{2}\mathbb{E}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}$ (41)
$\displaystyle+L\gamma^{2}\sigma^{2}+\left(L+\frac{1}{2\rho\gamma}+\frac{1}{2\gamma}\right)\mathbb{E}\|{\mathbf{z}}_{t}\|^{2}.$

The above result is not sufficient to complete the proof since $a_{t}$ is with
respect to the virtual sequence. This difficulty, which is addressed for the
first time in this paper, has been the main challenge in the proof of
convergence of error compensated schemes with biased gradient compression
under PLC. To deal with this burden, we revisit (33) to establish an
alternative bound. Specifically, we to bound the first inner-product in (33)
we instead establish

$\displaystyle-\gamma\langle\nabla
f(\tilde{{\mathbf{x}}}_{t}),\bar{{\mathbf{g}}}_{t}\rangle$
$\displaystyle=-\gamma\langle\nabla f(\tilde{{\mathbf{x}}}_{t}),\nabla
f(\tilde{{\mathbf{x}}}_{t})\rangle+\gamma\langle\nabla
f(\tilde{{\mathbf{x}}}_{t}),\nabla
f(\tilde{{\mathbf{x}}}_{t})-\bar{{\mathbf{g}}}_{t}\rangle$ (42)
$\displaystyle\leq-\gamma\|\nabla
f(\tilde{{\mathbf{x}}}_{t})\|^{2}+\frac{\gamma\rho_{1}}{2}\|\nabla
f(\tilde{{\mathbf{x}}}_{t})\|^{2}+\frac{\gamma}{2\rho}\|\nabla
f(\tilde{{\mathbf{x}}}_{t})-\bar{{\mathbf{g}}}_{t}\|^{2}$
$\displaystyle=-\gamma(1-\frac{\rho_{1}}{2})\|\nabla
f(\tilde{{\mathbf{x}}}_{t})\|^{2}+\frac{\gamma}{2\rho_{1}}\|\nabla
f(\tilde{{\mathbf{x}}}_{t})-\bar{{\mathbf{g}}}_{t}\|^{2}$

where we used Fact 2 with parameter $\rho_{1}>0$ which will be determined
later. Recall that by smoothness

$\displaystyle\|\nabla
f(\tilde{{\mathbf{x}}}_{t})-\bar{{\mathbf{g}}}_{t}\|^{2}\leq
L^{2}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}.$ (43)

We now derive a bound for the second inner-product in (33). To do so, an
application of Fact 2 yields

$\displaystyle-\mathbb{E}_{t}[\langle\nabla
f(\tilde{{\mathbf{x}}}_{t}),{\mathbf{z}}_{t}\rangle]\leq\frac{\rho_{2}\gamma}{2}\|\nabla
f(\tilde{{\mathbf{x}}}_{t})\|^{2}+\frac{1}{2\gamma\rho_{2}}\mathbb{E}_{t}\|{\mathbf{z}}_{t}\|^{2}.$
(44)

Therefore, in light of these new bounds we obtain

$\displaystyle\mathbb{E}_{t}[f(\tilde{{\mathbf{x}}}_{t+1})]$
$\displaystyle\leq
f(\tilde{{\mathbf{x}}}_{t})-\gamma\left(1-\frac{\rho_{1}+\rho_{2}}{2}\right)\|\nabla
f(\tilde{{\mathbf{x}}}_{t})\|^{2}+L\gamma^{2}\mathbb{E}_{t}\|{\mathbf{g}}_{t}\|^{2}$
(45)
$\displaystyle+\left(L+\frac{1}{2\gamma\rho_{2}}\right)\mathbb{E}_{t}\|{\mathbf{z}}_{t}\|^{2}+\frac{\gamma
L^{2}}{2\rho_{1}}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}.$

Subtracting $f^{\ast}$ and taking expectation with respect to the entire
sources of randomness yields

$\displaystyle\mathbb{E}[f(\tilde{{\mathbf{x}}}_{t+1})]-f^{\ast}$
$\displaystyle\leq\mathbb{E}[f(\tilde{{\mathbf{x}}}_{t})]-f^{\ast}-\gamma\left(1-\frac{\rho_{1}+\rho_{2}}{2}\right)\mathbb{E}\|\nabla
f(\tilde{{\mathbf{x}}}_{t})\|^{2}+L\gamma^{2}\sigma^{2}$ (46)
$\displaystyle+\left(L+\frac{1}{2\gamma\rho_{2}}\right)\mathbb{E}\|{\mathbf{z}}_{t}\|^{2}+\frac{\gamma
L^{2}}{2\rho_{1}}\mathbb{E}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}.$

The gradient term $\mathbb{E}\|\nabla f(\tilde{{\mathbf{x}}}_{t})\|^{2}$ in
(46) can be related to $a_{t}$ using the PL condition. Therefore

$\displaystyle a_{t+1}\leq$
$\displaystyle\left[1-2\mu\gamma\left(1-\frac{\rho_{1}+\rho_{2}}{2}\right)\right]a_{t}+L\gamma^{2}\sigma^{2}$
(47)
$\displaystyle+\left(L+\frac{1}{2\gamma\rho_{2}}\right)\mathbb{E}\|{\mathbf{z}}_{t}\|^{2}+\frac{\gamma
L^{2}}{2\rho_{1}}\mathbb{E}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}.$

Multiply (41) and (47) by $1/2$ and add the two to obtain

$\displaystyle a_{t+1}\leq$
$\displaystyle\left[1-\mu\gamma\left(1-\frac{\rho_{1}+\rho_{2}}{2}\right)\right]a_{t}+L\gamma^{2}\sigma^{2}-\left(\frac{1}{2}-\rho\right)\frac{\gamma\mu}{2}\mathbb{E}[f({\mathbf{x}}_{t})-f^{\ast}]$
(48)
$\displaystyle\qquad+\left(L+\frac{1}{4\gamma\rho}+\frac{1}{4\gamma\rho_{2}}+\frac{1}{4\gamma}\right)\mathbb{E}\|{\mathbf{z}}_{t}\|^{2}$
$\displaystyle\qquad+\left(3+\frac{1}{\rho_{1}}\right)\frac{\gamma
L^{2}}{4}\mathbb{E}\|\tilde{{\mathbf{x}}}_{t}-{\mathbf{x}}_{t}\|^{2}.$

Define

$b_{t}:=\mathbb{E}[f({\mathbf{x}}_{t})-f^{\ast}].$ (49)

Let $\rho=1/4$, $\rho_{1}=1/2$, $\rho_{2}=1/2$, and $\gamma=1/4L$. Using Lemma
4 and (39), (48) simplifies to

$\displaystyle a_{t+1}$
$\displaystyle\leq\left[1-\frac{\mu\gamma}{2}\right]a_{t}-\frac{\gamma\mu}{8}b_{t}+L\gamma^{2}\sigma^{2}+\frac{5L^{2}}{4}\gamma^{3}\sigma^{2}\left[\frac{4(1-\xi^{2})}{\xi^{2}}\right]$
(50)
$\displaystyle\qquad+\frac{192\gamma\sigma^{2}}{(1-\alpha)^{2}}\left[1+\frac{4(1-\xi^{2})}{\xi^{2}}\right]+\frac{4\epsilon^{2}}{\gamma|{\mathbb{G}}|^{2}(1-\alpha)^{2}}.$

Thus we can apply Fact 3 to obtain

$\displaystyle\frac{1}{W_{T}}\sum_{t=0}^{T-1}b_{t}w_{t}$
$\displaystyle\leq\frac{8(f({\mathbf{x}}_{0})-f^{\ast})}{\mu\gamma}\left[1-\frac{\mu\gamma}{2}\right]^{T}+\frac{8L\gamma\sigma^{2}}{\mu}+\frac{10L^{2}}{\mu}\gamma^{2}\sigma^{2}\left[\frac{4(1-\xi^{2})}{\xi^{2}}\right]$
(51)
$\displaystyle+\frac{1536\sigma^{2}}{\mu(1-\alpha)^{2}}\left[1+\frac{4(1-\xi^{2})}{\xi^{2}}\right]+\frac{32\epsilon^{2}}{\mu\gamma^{2}|{\mathbb{G}}|^{2}(1-\alpha)^{2}},$

where we used $E[f(\tilde{{\mathbf{x}}}_{0}^{i})]=f({\mathbf{x}}_{0})$.
Finally, to obtain the stated result we invoke Fact 4 and the assumption that
the solution set (i.e., the set of all stationary points) is convex.
Specifically, by the quadratic growth condition and convexity of the Euclidean
norm

$\displaystyle\sum_{t=0}^{T-1}\frac{w_{t}}{W_{T}}\mathbb{E}[f({\mathbf{x}}_{t})-f^{\ast}]$
$\displaystyle\geq\sum_{t=0}^{T-1}\frac{w_{t}}{W_{T}}\mathbb{E}\|{\mathbf{x}}_{t}-{\mathcal{P}}_{{\mathcal{X}}^{\ast}}({\mathbf{x}}_{t})\|^{2}$
(52)
$\displaystyle\geq\frac{\mu}{2}\sum_{t=0}^{T-1}\frac{w_{t}}{W_{T}}\mathbb{E}\|{\mathbf{x}}_{t}-{\mathcal{P}}_{{\mathcal{X}}^{\ast}}({\mathbf{x}}_{t})\|^{2}$
$\displaystyle\geq\frac{\mu}{2}\mathbb{E}\|\sum_{t=0}^{T-1}\frac{w_{t}}{W_{T}}{\mathbf{x}}_{t}-\sum_{t=0}^{T-1}\frac{w_{t}}{W_{T}}{\mathcal{P}}_{{\mathcal{X}}^{\ast}}({\mathbf{x}}_{t})\|^{2}$
$\displaystyle:=\frac{\mu}{2}\mathbb{E}\|\hat{{\mathbf{x}}}_{T}-{\mathbf{x}}^{\ast}\|^{2},$

where ${\mathcal{P}}_{{\mathcal{X}}^{\ast}}({\mathbf{x}}_{t})$ is the
projection of ${\mathbf{x}}_{t}$ onto the solution set ${\mathcal{X}}^{\ast}$
and
${\mathbf{x}}^{\ast}:=\sum_{t=0}^{T-1}\frac{w_{t}}{W_{T}}{\mathcal{P}}_{{\mathcal{X}}^{\ast}}({\mathbf{x}}_{t})\in{\mathcal{X}}^{\ast}$
by the assumption that the solution set is convex.

## References

  * [AAZL18] Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li.  Byzantine stochastic gradient descent.  In Advances in Neural Information Processing Systems, pages 4613–4623, 2018.
  * [AHJ+18] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli.  The convergence of sparsified gradient methods.  In Advances in Neural Information Processing Systems, pages 5973–5983, 2018.
  * [AZQRY16] Zeyuan Allen-Zhu, Zheng Qu, Peter Richtárik, and Yang Yuan.  Even faster accelerated coordinate descent using non-uniform sampling.  In International Conference on Machine Learning, pages 1110–1119, 2016.
  * [BBC11] Dimitris Bertsimas, David B Brown, and Constantine Caramanis.  Theory and applications of robust optimization.  SIAM review, 53(3):464–501, 2011.
  * [BCNW12] Richard H Byrd, Gillian M Chin, Jorge Nocedal, and Yuchen Wu.  Sample size selection in optimization methods for machine learning.  Mathematical programming, 134(1):127–155, 2012.
  * [BDKD19] Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi.  Qsparse-local-SGD: Distributed SGD with quantization, sparsification and local computations.  In Advances in Neural Information Processing Systems, pages 14668–14679, 2019.
  * [Ber97] Dimitri P Bertsekas.  Nonlinear programming.  Journal of the Operational Research Society, 48(3):334–334, 1997\.
  * [BGS+17] Peva Blanchard, Rachid Guerraoui, Julien Stainer, et al.  Machine learning with adversaries: Byzantine tolerant gradient descent.  In Advances in Neural Information Processing Systems, pages 119–129, 2017.
  * [BKSV20] Saikiran Bulusu, Prashant Khanduri, Pranay Sharma, and Pramod K Varshney.  On distributed stochastic gradient descent for nonconvex functions in the presence of byzantines.  In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3137–3141. IEEE, 2020.
  * [BNL12] Battista Biggio, Blaine Nelson, and Pavel Laskov.  Poisoning attacks against support vector machines.  arXiv preprint arXiv:1206.6389, 2012.
  * [Bot10] Léon Bottou.  Large-scale machine learning with stochastic gradient descent.  In Proceedings of COMPSTAT’2010, pages 177–186. Springer, 2010\.
  * [BT13] Amir Beck and Luba Tetruashvili.  On the convergence of block coordinate descent type methods.  SIAM journal on Optimization, 23(4):2037–2060, 2013.
  * [BTN00] Aharon Ben-Tal and Arkadi Nemirovski.  Robust solutions of linear programming problems contaminated with uncertain data.  Mathematical programming, 88(3):411–424, 2000.
  * [BWAA18] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar.  SignSGD: Compressed optimisation for non-convex problems.  In International Conference on Machine Learning, pages 560–569, 2018.
  * [CCS+19] Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina.  Entropy-sgd: Biasing gradient descent into wide valleys.  Journal of Statistical Mechanics: Theory and Experiment, 2019(12):124018, 2019.
  * [CGK+00] Moses Charikar, Venkatesan Guruswami, Ravi Kumar, Sridhar Rajagopalan, and Amit Sahai.  Combinatorial feature selection problems.  In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 631–640. IEEE, 2000.
  * [CLL+17] Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song.  Targeted backdoor attacks on deep learning systems using data poisoning.  arXiv preprint arXiv:1712.05526, 2017.
  * [CLM+16] Michael B Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford.  Geometric median in nearly linear time.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 9–21, 2016.
  * [CMMP13] Hui Han Chin, Aleksander Madry, Gary L Miller, and Richard Peng.  Runtime guarantees for regression problems.  In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 269–282, 2013.
  * [CSX17] Yudong Chen, Lili Su, and Jiaming Xu.  Distributed statistical machine learning in adversarial settings: Byzantine gradient descent.  Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1–25, 2017.
  * [CT89] Ramaswamy Chandrasekaran and Arie Tamir.  Open questions concerning weiszfeld’s algorithm for the fermat-weber location problem.  Mathematical Programming, 44(1-3):293–295, 1989.
  * [CWCP18] Lingjiao Chen, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos.  Draco: Byzantine-resilient distributed training via redundant gradients.  In International Conference on Machine Learning, pages 903–912. PMLR, 2018.
  * [DAH+20] Rudrajit Das, Anish Acharya, Abolfazl Hashemi, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topcu.  Faster non-convex federated learning via global and local momentum.  arXiv preprint arXiv:2012.04061, 2020.
  * [DD20] Deepesh Data and Suhas Diggavi.  Byzantine-resilient SGD in high dimensions on heterogeneous data.  arXiv preprint arXiv:2005.07866, 2020.
  * [DFT13] John C Doyle, Bruce A Francis, and Allen R Tannenbaum.  Feedback control theory.  Courier Corporation, 2013.
  * [DGBSX12] Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao.  Optimal distributed online prediction using mini-batches.  The Journal of Machine Learning Research, 13:165–202, 2012.
  * [DH83] David L Donoho and Peter J Huber.  The notion of breakdown point.  A festschrift for Erich L. Lehmann, 157184, 1983.
  * [DK11] Abhimanyu Das and David Kempe.  Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection.  arXiv preprint arXiv:1102.3975, 2011.
  * [DK19] Ilias Diakonikolas and Daniel M Kane.  Recent advances in algorithmic high-dimensional robust statistics.  arXiv preprint arXiv:1911.05911, 2019.
  * [DKK+19a] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart.  Robust estimators in high-dimensions without the computational intractability.  SIAM Journal on Computing, 48(2):742–864, 2019.
  * [DKK+19b] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart.  Sever: A robust meta-algorithm for stochastic optimization.  In International Conference on Machine Learning, pages 1596–1606. PMLR, 2019.
  * [DRT11] Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari.  Nearest neighbor based greedy coordinate descent.  In Advances in Neural Information Processing Systems, pages 2160–2168, 2011.
  * [Fu98] Wenjiang J Fu.  Penalized regressions: the bridge versus the lasso.  Journal of computational and graphical statistics, 7(3):397–416, 1998.
  * [FXM14] Jiashi Feng, Huan Xu, and Shie Mannor.  Distributed robust learning.  arXiv preprint arXiv:1409.5937, 2014.
  * [GDG+17] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He.  Accurate, large minibatch sgd: Training imagenet in 1 hour.  arXiv preprint arXiv:1706.02677, 2017.
  * [GLDGG19] Tianyu Gu, Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg.  Badnets: Evaluating backdooring attacks on deep neural networks.  IEEE Access, 7:47230–47244, 2019.
  * [GLV20] Nirupam Gupta, Shuo Liu, and Nitin H Vaidya.  Byzantine fault-tolerant distributed machine learning using stochastic gradient descent (sgd) and norm-based comparative gradient elimination (cge).  arXiv preprint arXiv:2008.04699, 2020.
  * [GMK+19] Avishek Ghosh, Raj Kumar Maity, Swanand Kadhe, Arya Mazumdar, and Kannan Ramchandran.  Communication-efficient and byzantine-robust distributed learning.  arXiv preprint arXiv:1911.09721, 2019.
  * [GOPV17] Mert Gurbuzbalaban, Asuman E Ozdaglar, Pablo A Parrilo, and Nuri Denizcan Vanli.  When cyclic coordinate descent outperforms randomized coordinate descent.  2017\.
  * [Hal48] JBS Haldane.  Note on the median of a multivariate distribution.  Biometrika, 35(3-4):414–417, 1948.
  * [HD11] Cho-Jui Hsieh and Inderjit S Dhillon.  Fast coordinate descent methods with variable selection for non-negative matrix factorization.  In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1064–1072, 2011.
  * [HD18] Dan Hendrycks and Thomas Dietterich.  Benchmarking neural network robustness to common corruptions and perturbations.  In International Conference on Learning Representations, 2018.
  * [Hub92] Peter J Huber.  Robust estimation of a location parameter.  In Breakthroughs in statistics, pages 492–518. Springer, 1992.
  * [HZRS16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [Joa98] Thorsten Joachims.  Making large-scale svm learning practical.  Technical report, Technical report, 1998.
  * [Kem87] JHB Kemperman.  The median of a finite measure on a banach space.  Statistical data analysis based on the L1-norm and related methods (Neuchâtel, 1987), pages 217–230, 1987.
  * [KKM+20] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh.  Scaffold: Stochastic controlled averaging for federated learning.  In International Conference on Machine Learning, pages 5132–5143. PMLR, 2020.
  * [KKSJ19] Sai Praneeth Karimireddy, Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi.  Efficient greedy coordinate descent for composite problems.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2887–2896. PMLR, 2019.
  * [KMN+16] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang.  On large-batch training for deep learning: Generalization gap and sharp minima.  arXiv preprint arXiv:1609.04836, 2016.
  * [KNS16] Hamed Karimi, Julie Nutini, and Mark Schmidt.  Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition.  In European Conference on Machine Learning and Knowledge Discovery in Databases-Volume 9851, pages 795–811, 2016.
  * [KRSJ19] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U Stich, and Martin Jaggi.  Error feedback fixes SignSGD and other gradient compression schemes.  arXiv preprint arXiv:1901.09847, 2019.
  * [KSH12] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25:1097–1105, 2012.
  * [LBBH98] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [LHY+19] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang.  On the convergence of fedavg on non-iid data.  arXiv preprint arXiv:1907.02189, 2019.
  * [Li18] Jerry Zheng Li.  Principled approaches to robust machine learning and beyond.  PhD thesis, Massachusetts Institute of Technology, 2018.
  * [LR+91] Hendrik P Lopuhaa, Peter J Rousseeuw, et al.  Breakdown points of affine equivariant estimators of multivariate location and covariance matrices.  The Annals of Statistics, 19(1):229–248, 1991.
  * [LSP82] LESLIE Lamport, ROBERT SHOSTAK, and MARSHALL PEASE.  The byzantine generals problem.  ACM Transactions on Programming Languages and Systems, 4(3):382–401, 1982.
  * [LSZ+18] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith.  Federated optimization in heterogeneous networks.  arXiv preprint arXiv:1812.06127, 2018.
  * [LXC+19] Liping Li, Wei Xu, Tianyi Chen, Georgios B Giannakis, and Qing Ling.  Rsa: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1544–1551, 2019.
  * [LZCS14] Mu Li, Tong Zhang, Yuqiang Chen, and Alexander J Smola.  Efficient mini-batch training for stochastic optimization.  In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 661–670, 2014.
  * [LZS+18] Cong Liao, Haoti Zhong, Anna Squicciarini, Sencun Zhu, and David Miller.  Backdoor embedding in convolutional neural network models via invisible perturbation.  arXiv preprint arXiv:1808.10307, 2018.
  * [M+15] Stanislav Minsker et al.  Geometric median and robust estimation in banach spaces.  Bernoulli, 21(4):2308–2335, 2015.
  * [MB11] Eric Moulines and Francis R Bach.  Non-asymptotic analysis of stochastic approximation algorithms for machine learning.  In Advances in Neural Information Processing Systems, pages 451–459, 2011.
  * [MGR18] El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Rouault.  The hidden vulnerability of distributed learning in byzantium.  arXiv preprint arXiv:1802.07927, 2018.
  * [MMR+17] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In Artificial Intelligence and Statistics, pages 1273–1282, 2017\.
  * [Nes12] Yu Nesterov.  Efficiency of coordinate descent methods on huge-scale optimization problems.  SIAM Journal on Optimization, 22(2):341–362, 2012.
  * [NLS17] Julie Nutini, Issam Laradji, and Mark Schmidt.  Let’s make block coordinate descent go fast: Faster greedy rules, message-passing, active-set complexity, and superlinear convergence.  arXiv preprint arXiv:1712.08859, 2017.
  * [NSL+15] Julie Nutini, Mark Schmidt, Issam Laradji, Michael Friedlander, and Hoyt Koepke.  Coordinate descent converges faster with the gauss-southwell rule than random selection.  In International Conference on Machine Learning, pages 1632–1641, 2015.
  * [NT14] Deanna Needell and Joel A Tropp.  Paved with good intentions: analysis of a randomized block kaczmarz method.  Linear Algebra and its Applications, 441:199–221, 2014.
  * [NW81] George L Nemhauser and Laurence A Wolsey.  Maximizing submodular set functions: formulations and analysis of algorithms.  In North-Holland Mathematics Studies, volume 59, pages 279–301. Elsevier, 1981.
  * [Opt98] Sequential Minimal Optimization.  A fast algorithm for training support vector machines.  CiteSeerX, 10(1.43):4376, 1998.
  * [PKH19] Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui.  Robust aggregation for federated learning.  arXiv preprint arXiv:1912.13445, 2019.
  * [Pol63] Boris Teodorovich Polyak.  Gradient methods for minimizing functionals.  Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 3(4):643–653, 1963.
  * [RM51] Herbert Robbins and Sutton Monro.  A stochastic approximation method.  The annals of mathematical statistics, pages 400–407, 1951.
  * [RT14] Peter Richtárik and Martin Takáč.  Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function.  Mathematical Programming, 144(1-2):1–38, 2014.
  * [SBT00] Sylvain Sardy, Andrew G Bruce, and Paul Tseng.  Block coordinate relaxation methods for nonparametric wavelet denoising.  Journal of computational and graphical statistics, 9(2):361–379, 2000.
  * [SCCS19] Shaohuai Shi, Xiaowen Chu, Ka Chun Cheung, and Simon See.  Understanding top-k sparsification in distributed deep learning.  arXiv preprint arXiv:1911.08772, 2019.
  * [SCJ18] Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi.  Sparsified SGD with memory.  In Advances in Neural Information Processing Systems, pages 4447–4458, 2018.
  * [SCV17] Jacob Steinhardt, Moses Charikar, and Gregory Valiant.  Resilience: A criterion for learning in the presence of arbitrary outliers.  arXiv preprint arXiv:1703.04940, 2017.
  * [SFD+14] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu.  1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs.  In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
  * [SK19] Sebastian U Stich and Sai Praneeth Karimireddy.  The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication.  arXiv preprint arXiv:1909.05350, 2019.
  * [SRJ17] Sebastian U Stich, Anant Raj, and Martin Jaggi.  Approximate steepest coordinate descent.  In International Conference on Machine Learning, pages 3251–3259. PMLR, 2017.
  * [SS19] Yanyao Shen and Sujay Sanghavi.  Learning with bad training data via iterative trimmed loss minimization.  In International Conference on Machine Learning, pages 5739–5748. PMLR, 2019.
  * [SSZ13] Shai Shalev-Shwartz and Tong Zhang.  Accelerated mini-batch stochastic dual coordinate ascent.  In Advances in Neural Information Processing Systems, pages 378–385, 2013.
  * [ST13] Ankan Saha and Ambuj Tewari.  On the nonasymptotic convergence of cyclic coordinate descent methods.  SIAM Journal on Optimization, 23(1):576–601, 2013.
  * [Sti18] Sebastian U Stich.  Local sgd converges fast and communicates little.  arXiv preprint arXiv:1805.09767, 2018.
  * [Sti19] Sebastian U Stich.  Unified optimal analysis of the (stochastic) gradient method.  arXiv preprint arXiv:1907.04232, 2019.
  * [Str15] Nikko Strom.  Scalable distributed dnn training using commodity gpu cloud computing.  In Sixteenth Annual Conference of the International Speech Communication Association, 2015.
  * [TBA86] John Tsitsiklis, Dimitri Bertsekas, and Michael Athans.  Distributed asynchronous deterministic and stochastic gradient optimization algorithms.  IEEE transactions on automatic control, 31(9):803–812, 1986.
  * [TLM18] Brandon Tran, Jerry Li, and Aleksander Madry.  Spectral signatures in backdoor attacks.  In Advances in Neural Information Processing Systems, pages 8000–8010, 2018.
  * [TTGL20] Vale Tolpegin, Stacey Truex, Mehmet Emre Gursoy, and Ling Liu.  Data poisoning attacks against federated learning systems.  In European Symposium on Research in Computer Security, pages 480–501. Springer, 2020.
  * [TY09a] Paul Tseng and Sangwoon Yun.  Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization.  Journal of optimization theory and applications, 140(3):513, 2009\.
  * [TY09b] Paul Tseng and Sangwoon Yun.  A coordinate gradient descent method for nonsmooth separable minimization.  Mathematical Programming, 117(1):387–423, 2009.
  * [VN56] John Von Neumann.  Probabilistic logics and the synthesis of reliable organisms from unreliable components.  Automata studies, 34:43–98, 1956.
  * [VZ00] Yehuda Vardi and Cun-Hui Zhang.  The multivariate l1-median and associated data depth.  Proceedings of the National Academy of Sciences, 97(4):1423–1426, 2000.
  * [Wei37] Endre Weiszfeld.  Sur le point pour lequel la somme des distances de n points donnés est minimum.  Tohoku Mathematical Journal, First Series, 43:355–386, 1937.
  * [WF+29] Alfred Weber, Carl Joachim Friedrich, et al.  Alfred Weber’s theory of the location of industries.  The University of Chicago Press, 1929.
  * [WLCG20] Zhaoxian Wu, Qing Ling, Tianyi Chen, and Georgios B Giannakis.  Federated variance-reduced stochastic gradient descent with robustness to byzantine attacks.  IEEE Transactions on Signal Processing, 68:4583–4596, 2020.
  * [WS17] Yining Wang and Aarti Singh.  Provably correct algorithms for matrix column subset selection with selectively sampled data.  The Journal of Machine Learning Research, 18(1):5699–5740, 2017\.
  * [XKG19] Cong Xie, Sanmi Koyejo, and Indranil Gupta.  Zeno: Distributed stochastic gradient descent with suspicion-based fault-tolerance.  In International Conference on Machine Learning, pages 6893–6901. PMLR, 2019.
  * [XRV17] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  arXiv preprint arXiv:1708.07747, 2017.
  * [YB19] Zhixiong Yang and Waheed U Bajwa.  Bridge: Byzantine-resilient decentralized gradient descent.  arXiv preprint arXiv:1908.08098, 2019.
  * [YCKB18] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett.  Byzantine-robust distributed learning: Towards optimal statistical rates.  In International Conference on Machine Learning, pages 5650–5659. PMLR, 2018.
  * [YHCL12] Hsiang-Fu Yu, Cho-Jui Hsieh, Kai-Wei Chang, and Chih-Jen Lin.  Large linear classification when data cannot fit in memory.  ACM Transactions on Knowledge Discovery from Data (TKDD), 5(4):1–23, 2012.
  * [YLL+16] Yang You, Xiangru Lian, Ji Liu, Hsiang-Fu Yu, Inderjit S Dhillon, James Demmel, and Cho-Jui Hsieh.  Asynchronous parallel greedy coordinate descent.  In NIPS, pages 4682–4690. Barcelona, Spain, 2016.
  * [YZFL19] Haibo Yang, Xin Zhang, Minghong Fang, and Jia Liu.  Byzantine-resilient stochastic gradient descent for distributed learning: A lipschitz-inspired coordinate-wise median approach.  In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 5832–5837. IEEE, 2019.
  * [Zha20] Hui Zhang.  New analysis of linear convergence of gradient-type methods via unifying error bound conditions.  Mathematical Programming, 180(1):371–416, 2020.