# Byzantine-Robust Decentralized Stochastic Optimization
over Static and Time-Varying Networks

Jie Peng Weiyu Li Qing Ling* *Corresponding Author
E-mail address<EMAIL_ADDRESS>
School of Data and Computer Science and Guangdong Province Key Laboratory of
Computational Science,
Sun Yat-Sen University, Guangzhou, Guangdong, 510006, China

###### Abstract

In this paper, we consider the Byzantine-robust stochastic optimization
problem defined over decentralized static and time-varying networks, where the
agents collaboratively minimize the summation of expectations of stochastic
local cost functions, but some of the agents are unreliable due to data
corruptions, equipment failures or cyber-attacks. The unreliable agents, which
are called as Byzantine agents thereafter, can send faulty values to their
neighbors and bias the optimization process. Our key idea to handle the
Byzantine attacks is to formulate a total variation (TV) norm-penalized
approximation of the Byzantine-free problem, where the penalty term forces the
local models of regular agents to be close, but also allows the existence of
outliers from the Byzantine agents. A stochastic subgradient method is applied
to solve the penalized problem. We prove that the proposed method reaches a
neighborhood of the Byzantine-free optimal solution, and the size of
neighborhood is determined by the number of Byzantine agents and the network
topology. Numerical experiments corroborate the theoretical analysis, as well
as demonstrate the robustness of the proposed method to Byzantine attacks and
its superior performance comparing to existing methods.

###### keywords:

Decentralized stochastic optimization, Byzantine attacks, robustness, static
networks, time-varying networks

††volume: 00

Signal Processing procs SIGPRO

##  1 Introduction

In recent years, decentralized stochastic optimization has become a popular
research topic in the signal processing and machine learning communities. With
the rapidly increasing number of distributed devices and volume of generated
data, traditional signal processing and machine learning approaches, which
rely on a central controller to collect the data samples or coordinate the
optimization process, suffer from privacy and scalability issues [2]. In
decentralized stochastic optimization, every device (called as agent
thereafter) learns its own model using its local data samples, and
periodically exchanges its model with neighboring agents so as to achieve
consensus. This scheme is favorable in privacy preservation since the data
samples are kept local, and does not rely on any central controller that could
be a system bottleneck. Existing decentralized stochastic optimization methods
include decentralized parallel stochastic gradient descent (DPSGD) [3],
stochastic subgradient projection [4], dual averaging [5], mirror descent [6],
etc. Asynchronous algorithms are developed in [7, 8] to reduce the idle time,
and variance reduction techniques are proposed in [9, 10, 11, 12, 13] to
improve the convergence rate. Decentralized stochastic optimization methods
are shown to be superior to their centralized counterparts on training large-
scale neural networks when the communication links are subject to high latency
and limited bandwidth [14].

However, the lack of centralized coordination in decentralized stochastic
optimization also raises concerns on robustness. Some of the agents might be
malfunctioning or even malicious. Due to data corruptions, equipment failures
or cyber-attacks, they can send faulty values to their neighbors and bias the
optimization process. We consider a general Byzantine attack model [15], in
which the Byzantine agents are omniscient and can arbitrarily modify the
values sent to other agents. Such an attack model imposes no restrictions on
the adversaries and is worst-case. The purpose of this paper is to develop a
Byzantine-robust decentralized stochastic optimization method.

Most of the existing decentralized stochastic optimization methods are
vulnerable to Byzantine attacks. Take DPSGD as an example. At every iteration,
every agent mixes the models received from its neighbors, followed by a
stochastic gradient step on the cost function constructed from one local data
sample (or a batch of them), to update its local model [3]. When the Byzantine
agents send well-designed faulty values instead of the true models, they are
able to lead the regular agents to end up with incorrect results.

Byzantine-robust decentralized deterministic optimization methods have been
developed in [16, 17], where at every iteration every regular agent uses all
of its local data samples, instead of one or a batch. The work of [16]
proposes ByRDiE, in which every regular agent utilizes coordinate-wise trimmed
mean to screen outliers in the received models, and then applies coordinate
gradient descent to update its local model. The one-coordinate-at-a-time
update of ByRDiE is inefficient for high-dimensional problems [17]. To address
this issue, the work of [17] proposes BRIDGE, which allows every regular agent
to update all the coordinates of its local model at every iteration. Although
these two algorithms are originally developed for decentralized deterministic
optimization, they can also be adapted to the decentralized stochastic setting
according to our numerical experiments. However, to the best of our knowledge,
most of the existing works do not explicitly consider the Byzantine-robust
decentralized stochastic optimization problem; see for reference the recent
survey paper [18].

There are some works that consider the Byzantine-robust centralized stochastic
optimization problem, where a central controller aggregates the information
from the agents and coordinates the optimization process. The main idea of
these works is to modify the stochastic gradient method with robust
aggregation rules. To be specific, at every iteration, the central controller
sends the current model to all the agents, the regular agents send back their
local stochastic gradients, while the Byzantine agents may send back faulty
values. When the local data samples are independently and identically
distributed (i.i.d.), the local stochastic gradients are also i.i.d. and the
central controller can obtain a reliable approximation to the average of the
local stochastic gradients through aggregating all the received values with
trimmed mean, geometric median, or other robust aggregation rules [19, 20].
However, this idea is not directly applicable to decentralized stochastic
optimization. Since there is no central controller to maintain a common model,
the regular agents have to evaluate their local stochastic gradients at
different points. Therefore, even though the local data samples are i.i.d. the
local stochastic gradients are not necessarily so, and thus the robust
aggregation rules have no theoretical guarantee in this case.

In addition to Byzantine-robust decentralized stochastic optimization over
static networks, we are also interested in the case that the underlying
network topologies are time-varying, which finds applications in mobile
computation systems and robotic swarms. Various decentralized stochastic
optimization algorithms over time-varying networks have been developed, such
as those in [21, 22]. Some of the recent works further consider that the time-
varying networks are directed such that the designed mixing matrices are
column stochastic [23, 24, 25] or row stochastic [26]. However, none of these
algorithms take into account the existence of Byzantine agents. On the other
hand, there exist other works considering adversarial attacks over time-
varying graphs. For example, the works of [27, 28] focus on robust distributed
parameter estimation, while their attack model is different from ours. To be
specific, the works of [27, 28] consider adversarial attacks on the measured
data, while our Byzantine attack model considers attacks during the
optimization process.

This paper develops a Byzantine-robust decentralized stochastic optimization
method over static and time-varying networks, where the networks are fully
decentralized and contain unknown numbers of Byzantine agents, the local data
samples at the regular agents are not necessarily i.i.d. and only one data
sample (or a batch of them) is available for every regular agent at every
iteration. The key idea is to formulate a total variation (TV) norm-penalized
approximation of the Byzantine-free problem, where the penalty term forces the
local models of regular agents to be close, but also allows the existence of
outliers from the Byzantine agents. A stochastic subgradient method is applied
to solve the penalized problem (Section 2). Although the TV norm-penalized
approximation has been investigated in Byzantine-robust decentralized
deterministic [29], decentralized dynamic [30] and centralized stochastic [31]
optimization problems, its application in Byzantine-robust decentralized
stochastic optimization is novel. We prove that the proposed method reaches a
neighborhood of the Byzantine-free optimal solution under mild assumptions,
and the size of neighborhood is determined by the number of Byzantine agents
and the network topology (Section 3). Numerical experiments corroborate the
theoretical analysis and demonstrate the robustness of the proposed method to
Byzantine attacks (Section 4).

##  2 Problem Statement and Algorithm Development

In this section, we describe the formulation of Byzantine-robust decentralized
stochastic optimization problem, and develop the algorithm for both static and
time-varying networks.

###  2.1 Static Network Case

Consider a static and undirected network
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ with a set of $n$ agents
$\mathcal{V}=\\{1,\cdots,n\\}$ and a set of undirected edges $\mathcal{E}$. If
$e=(i,j)\in\mathcal{E}$, then agents $i$ and $j$ are neighbors and can
communicate with each other at a low cost. Since the network is undirected,
for notational convenience, we let every $e=(i,j)$ satisfy $i<j$. However, not
all the agents are regular. An unknown number of Byzantine agents are supposed
to be omniscient and can send faulty values to their neighbors during the
optimization process. Denote $\mathcal{R}$ and $\mathcal{B}$ as the sets of
regular agents and Byzantine agents, respectively. We have
$\mathcal{V}=\mathcal{R}\cup\mathcal{B}$. For agent $i$, denote the set of its
regular neighbors as $\mathcal{R}_{i}$ and the set of its Byzantine neighbors
as $\mathcal{B}_{i}$. Thus,
$\mathcal{N}_{i}:=\mathcal{R}_{i}\cup\mathcal{B}_{i}$ is the set of all
neighbors of agent $i$. Denote $\mathcal{E}_{R}\subseteq\mathcal{E}$ as the
set of reliable edges not attached to any Byzantine agent. The decentralized
stochastic optimization problem defined over the network is

$\displaystyle\tilde{x}^{*}=\arg\min\limits_{\tilde{x}\in{\mathbb{R}}^{p}}\sum_{i\in\mathcal{R}}\bigg{(}\mathbb{E}[F(\tilde{x},\xi_{i})]+f_{0}(\tilde{x})\bigg{)},$
(1)

where $\tilde{x}\in{\mathbb{R}}^{p}$ is an optimization variable (also called
as model), $F(\tilde{x},\xi_{i})$ is a smooth cost function determined by a
random variable $\xi_{i}$ following a distribution $\mathcal{D}_{i}$ and
represents an empirical loss related to a randomly chosen data sample in
regular agent $i$, and $f_{0}(\tilde{x})$ is a smooth regularization term.
Instead of the i.i.d. assumption as in [16, 17], here the random variables
$\\{\xi_{i},i\in\mathcal{R}\\}$ are only assumed to be mutually independent.
We will also assume $\mathbb{E}[F(\tilde{x},\xi_{i})]+f_{0}(\tilde{x})$ to be
strongly convex in Assumption 3 in Section 3. Our goal is to find the optimal
solution $\tilde{x}^{*}$ through collaboration of the regular agents. The main
challenges are three-fold: (i) the network lacks a central coordinator and is
fully decentralized, (ii) only one randomly chosen data sample (or a batch of
them) can be used by every regular agent at every iteration, and, (iii) more
importantly, the Byzantine agents can send faulty values to their neighbors so
as to bias the optimization process, but their identities are unknown.

To develop a reasonable algorithm, it is necessary to assume that the network
of regular agents is connected [30]. Otherwise, if a regular agent is
surrounded by Byzantine neighbors, it is unable to communicate and collaborate
with any regular agents. Therefore, the best model it can learn is solely
based on its local data samples, and may be far away from the true model in
the non-i.i.d. setting.

######  Assumption 1.

(Network Connectivity over Static Graph) The network consisting of all regular
agents $i\in\mathcal{R}$, denoted as $(\mathcal{R},\mathcal{E}_{R})$, is
connected.

We begin from assuming that the Byzantine agents are absent. Rewrite (1) to a
consensus-constrained form, which is common in decentralized optimization.
Denote $x_{i}\in{\mathbb{R}}^{p}$ as the local copy of the model $\tilde{x}$
at regular agent $i$ and stack all local copies in a longer vector
$x:=[x_{i}]\in{\mathbb{R}}^{|\mathcal{R}|p}$. When the regular agents are
connected as stated by Assumption 1, (1) is equivalent to

$\displaystyle\min\limits_{x:=[x_{i}]}$
$\displaystyle~{}\sum_{i\in\mathcal{R}}\bigg{(}\mathbb{E}[F(x_{i},\xi_{i})]+f_{0}(x_{i})\bigg{)},$
(2) $\displaystyle s.t.$ $\displaystyle~{}x_{i}=x_{j},~{}\forall
i\in\mathcal{R},~{}\forall j\in\mathcal{R}_{i},$

in the sense that $[\tilde{x}^{*}]\in{\mathbb{R}}^{|\mathcal{R}|p}$ that
stacks $|\mathcal{R}|$ vectors of $\tilde{x}^{*}$, the optimal solution to
(1), is the optimal solution to (2).

Then, motivated by [29, 30, 31], we propose to solve a TV norm-penalized
approximation of (2), as

$\displaystyle
x^{*}=\arg\min\limits_{x:=[x_{i}]}~{}\sum_{i\in\mathcal{R}}\bigg{(}\mathbb{E}[F(x_{i},\xi_{i})]+\frac{\lambda}{2}\sum_{j\in\mathcal{R}_{i}}\|x_{i}-x_{j}\|_{1}+f_{0}(x_{i})\bigg{)},$
(3)

where $\lambda\geq 0$ is a penalty parameter. For every pair of regular
neighbors $(i,j)$, $x_{i}$ and $x_{j}$ are forced to be close through
introducing the TV norm penalty
$\frac{\lambda}{2}\sum_{i\in\mathcal{R}}\sum_{j\in\mathcal{R}_{i}}\|x_{i}-x_{j}\|_{1}$,
in which every pair of regular neighbors $(i,j)$ appears once. The larger
$\lambda$ is, the closer $x_{i}$ and $x_{j}$ are forced to be. On the other
hand, the TV norm penalty also allows some pairs of $x_{i}$ and $x_{j}$ to be
different, which is important when the Byzantine agents are present as we will
discuss later.

Since calculating the full subgradient of the cost function in (3) is time-
consuming or even impossible, we solve (3) with the stochastic subgradient
method. At time $k$, every regular agent $i$ updates its local model
$x_{i}^{k+1}$ as

$\displaystyle x^{k+1}_{i}=x^{k}_{i}-\alpha^{k}\Bigg{(}\nabla
F(x^{k}_{i},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x^{k}_{i}-x^{k}_{j})+\nabla
f_{0}(x_{i}^{k})\Bigg{)},$ (4)

where $\xi_{i}^{k}\sim\mathcal{D}_{i}$ corresponds to the random data sample
chosen independently by agent $i$ at time $k$, $sign(\cdot)$ is the element-
wise sign function, and $\alpha^{k}>0$ is a step size. Given
$\beta\in{\mathbb{R}}$, $sign(\beta)$ equals to $1$ when $\beta>0$, $-1$ when
$\beta<0$, and an arbitrary value within $[-1,1]$ when $\beta=0$. Observe that
(4) is fully decentralized. To update $x^{k+1}_{i}$, a regular agent $i$ needs
to evaluate its own local stochastic gradient $\nabla
F(x^{k}_{i},\xi_{i}^{k})$ and gradient $\nabla f_{0}(x_{i}^{k})$, as well as
combine the models $\\{x^{k}_{j},j\in\mathcal{R}_{i}\\}$ received from its
regular neighbors $\\{j,j\in\mathcal{R}_{i}\\}$.

Now we consider how (4) performs when the Byzantine agents are present. A
Byzantine agent $j$ will not send its true model to its neighbors at time $k$.
Instead, it sends an arbitrary vector $z_{j}^{k}\in{\mathbb{R}}^{p}$. In this
case, for a regular agent $i$, (4) becomes

$\displaystyle x^{k+1}_{i}=x^{k}_{i}-\alpha^{k}\Bigg{(}$ $\displaystyle\nabla
F(x^{k}_{i},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x^{k}_{i}-x^{k}_{j})+\lambda\sum_{j\in\mathcal{B}_{i}}sign(x^{k}_{i}-z^{k}_{j})+\nabla
f_{0}(x_{i}^{k})\Bigg{)}.$ (5)

The resulting Byzantine-robust decentralized stochastic optimization method is
outlined in Algorithm 1. In (5), observe that the elements of
$sign(x^{k}_{i}-z^{k}_{j})$ are in the range of $[-1,1]$, such that the
influence of the faulty vector $z^{k}_{j}$ is limited, although $z^{k}_{j}$
can be arbitrary. We will theoretically justify the robustness of the proposed
algorithm to Byzantine attacks in the subsequent section.

Note that the TV norm penalty introduced here is based on the $\ell_{1}$ norm.
Other norms such as $\ell_{2}$ and $\ell_{\infty}$ are also applicable, as
recommended in [31] for Byzantine-robust centralized stochastic optimization.
We leave their development and analysis to our future work.

Algorithm 1 Byzantine-robust decentralized stochastic optimization over static
graph

Input: $x_{i}^{0}\in{\mathbb{R}}^{p}$ for $i\in\mathcal{R}$, $\lambda>0$, and
$\\{\alpha^{k},k=0,1,\cdots\\}$.

1:for $k=0,1,\cdots$, every regular agent $i\in\mathcal{R}$ do

2: Broadcast its current model $x_{i}^{k}$ to all the neighbors.

3: Receive $x^{k}_{j}$ from regular neighbors $j\in\mathcal{R}_{i}$ and
$z^{k}_{j}$ from Byzantine neighbors $j\in\mathcal{B}_{i}$.

4: Update local iterate $x^{k+1}_{i}$ according to (5).

5:end for

###  2.2 Time-Varying Network Case

We further consider the more challenging scenario that the network has time-
varying communication edges. As in the static case, we denote $\mathcal{R}$
and $\mathcal{B}$ as the sets of regular agents and Byzantine agents,
respectively, such that $\mathcal{V}=\mathcal{R}\cup\mathcal{B}$. Given the
fixed agents, there are a finite number of possible undirected graphs with
different edges. We encode these candidate graphs by the edge sets
$\mathcal{E}(\zeta)$ with
$\zeta=[\zeta_{e}]_{e=(i,j)\in\mathcal{V}\times\mathcal{V}}$, in which each
entry $\zeta_{e}\in\\{0,1\\}$ of $\zeta$ means $e\in\mathcal{E}$ if
$\zeta_{e}=1$, and $e\notin\mathcal{E}$ otherwise. At time $k$, the current
graph can be represented as
$\mathcal{G}^{k}=\big{(}\mathcal{V},\mathcal{E}(\zeta^{k})\big{)}$, where
$\zeta^{k}$ is a random vector, not necessarily independent with each other
across time, but independent with $\xi_{i}^{k^{\prime}}$ for all agent $i$ and
time $k^{\prime}$. Then we obtain a countable infinite random sequence
$(\zeta^{1},\zeta^{2},\ldots,\zeta^{k},\ldots)$ which completely characterizes
the time-varying network during the optimization process. To simplify the
notations, we use $\mathcal{E}^{k}=\mathcal{E}(\zeta^{k})$ as an abbreviation,
and the stochasticity of $\zeta^{k}$ will be implicitly included in the
following discussions. For agent $i$ at time $k$, denote $\mathcal{R}_{i}^{k}$
as the set of its instantaneous regular neighbors, $\mathcal{B}_{i}^{k}$ the
set of its instantaneous Byzantine neighbors, and
$\mathcal{N}_{i}^{k}:=\mathcal{R}_{i}^{k}\cup\mathcal{B}_{i}^{k}$ the set of
all instantaneous neighbors. Denote
$\mathcal{E}_{R}^{k}\subseteq\mathcal{E}^{k}$ as the set of reliable edges not
attached to any Byzantine agent.

Though our goal is still to solve the decentralized stochastic optimization
problem defined in (1), the time-varying network topology is an essential
issue compared to the static case. To guarantee sufficiently frequent
information exchange among all regular agents, we consider the average network
consisting of all regular agents and the edges that ergodically appear many
times. To be specific, define $\bar{a}_{e}$ as the limiting frequency of a
reliable edge $e=(i,j)$ appearing, where $i,j\in\mathcal{R}$ and $i<j$, given
by

$\bar{a}_{e}=\liminf_{K\rightarrow\infty}\frac{1}{K+1}\sum_{k=0}^{K}\zeta_{e}^{k}.$

Denote $\bar{\mathcal{E}}_{R}=\\{e:\bar{a}_{e}>0\\}$, and then call
$(\mathcal{R},\bar{\mathcal{E}}_{R})$ as the average network. The following
assumption guarantees that the average network is connected.

######  Assumption 2.

(Network Connectivity over Time-Varying Graph) The empirical distribution of
$\\{\zeta^{k}\\}_{k=0}^{K}$ converges to the distribution of some random
variable $\bar{\zeta}=[\bar{\zeta}_{e}]$ as $K\rightarrow\infty$, where the
expectation of $\bar{\zeta}_{e}$ is exactly $\bar{a}_{e}$ at each regular edge
$e$. The average network $(\mathcal{R},\bar{\mathcal{E}}_{R})$ is connected.

Assumption 2 is much weaker than Assumption 1 in which there exists a path
between any two regular agents at all times. In contrast, Assumption 2 allows
the path to be temporarily disconnected, while ensuring the regular agents to
exchange information in a sufficiently frequent manner.

Remark 1. Our time-varying network model is able to describe several common
scenarios.

(i) Randomly activated edges. At every time $k$, every reliable edge $e$ is
connected with probability $p_{e}\in(0,1]$. In this scenario,
$\bar{a}_{e}=p_{e}$.

(ii) Periodical network. From time $0$ to $T-1$, every reliable edge $e$
appears $t_{e}$ times. These $T$ network topologies reappear at the following
times, with a period of $T$. In this scenario, $\bar{a}_{e}=\frac{t_{e}}{T}$.

(iii) Quasi-periodical network. For any time span with length $T$, every
reliable edge $e$ appears at least $t_{e}$ time. In this scenario,
$\bar{a}_{e}\geq\frac{t_{e}}{T}$.

Similar to the equivalent transformation from (1) to (2), if the regular
agents are connected in the average network as stated by Assumption 2, (1) is
equivalent to

$\displaystyle\min\limits_{x:=[x_{i}]}$
$\displaystyle~{}\sum_{i\in\mathcal{R}}\bigg{(}\mathbb{E}_{\xi_{i}}[F(x_{i},\xi_{i})]+f_{0}(x_{i})\bigg{)},$
(6) $\displaystyle s.t.$
$\displaystyle~{}x_{i}=x_{j},~{}\forall(i,j)\in\bar{\mathcal{E}}_{R}.$

The TV norm-penalized approximation of (6) is given by

$\displaystyle x^{*}$
$\displaystyle=\arg\min\limits_{x:=[x_{i}]}~{}\sum_{i\in\mathcal{R}}\bigg{(}\mathbb{E}_{\xi_{i}}[F(x_{i},\xi_{i})]+f_{0}(x_{i})\bigg{)}+\lambda\sum_{e=(i,j)\in\bar{\mathcal{E}}_{R}}\bigg{(}\bar{a}_{e}\|x_{i}-x_{j}\|_{1}\bigg{)}$
$\displaystyle=\arg\min_{x:=[x_{i}]}~{}\sum_{i\in\mathcal{R}}\Bigg{(}\mathbb{E}_{\xi_{i}}[F(x_{i},\xi_{i})]+\frac{\lambda}{2}\
\mathbb{E}_{\bar{\zeta}}[\sum_{j\in\mathcal{R}_{i}(\bar{\zeta})}\|x_{i}-x_{j}\|_{1}]+f_{0}(x_{i})\Bigg{)},$
(7)

where $\mathcal{R}_{i}(\bar{\zeta})$ is the set of regular neighbors of agent
$i$ in terms of the average network
$\big{(}\mathcal{R},\mathcal{E}(\bar{\zeta})\big{)}$.

Therefore, akin to the static case, we solve (7) by the stochastic subgradient
method as follows. At time $k+1$, every regular agent $i$ updates its local
model as

$\displaystyle x_{i}^{k+1}=x_{i}^{k}-\alpha^{k}\bigg{(}\nabla
F(x_{i}^{k},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\bigg{)}.$ (8)

Now we turn to the case with Byzantine attacks. A Byzantine agent $j$ will
send an arbitrary vector $z_{j}^{k}\in{\mathbb{R}}^{p}$ instead of the true
model $x_{j}^{k}$ to its neighbors at time $k$. Therefore, in the presence of
Byzantine agents, (8) becomes

$\displaystyle x_{i}^{k+1}=x_{i}^{k}-\alpha^{k}\bigg{(}\nabla
F(x_{i}^{k},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\lambda\sum_{j\in\mathcal{B}_{i}^{k}}sign(x_{i}^{k}-z_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\bigg{)}.$ (9)

The resulting Byzantine-robust decentralized stochastic optimization method
over the time-varying network is outlined in Algorithm 2. With particular
note, our proposed method has a consistent form for both static and time-
varying networks. No specific design of any mixing matrix is needed to adapt
to the time-variance.

Algorithm 2 Byzantine-robust decentralized stochastic optimization over time-
varying graph

Input: $x_{i}^{0}\in{\mathbb{R}}^{p}$ for $i\in\mathcal{R}$, $\lambda>0$ and
$\\{\alpha^{k},k=0,1,\cdots\\}$.

1:for $k=0,1,\cdots$, every regular agent $i\in\mathcal{R}$ do

2: Broadcast its current model $x_{i}^{k}$ to all the neighbors.

3: Receive $x_{j}^{k}$ from regular neighbors $j\in\mathcal{R}_{i}^{k}$ and
$z^{k}_{j}$ from Byzantine neighbors $j\in\mathcal{B}_{i}^{k}$.

4: Update local iterate $x^{k+1}_{i}$ according to (9).

5:end for

##  3 Performance Analysis

In this section, we theoretically analyze the proposed Byzantine-robust
decentralized stochastic optimization method in terms of convergence and
robustness. We make the following assumptions, which are common in analyzing
decentralized stochastic optimization methods.

######  Assumption 3.

(Strong Convexity) For any model $\tilde{x}\in{\mathbb{R}}^{p}$ and every
regular agent $i\in\mathcal{R}$,
$\mathbb{E}[F(\tilde{x},\xi_{i})]+f_{0}(\tilde{x})$ is strongly convex with
constants $u_{i}$, where $\mathbb{E}[F(\tilde{x},\xi_{i})]$ is the local cost
function and $f_{0}(\tilde{x})$ is the regularization term.

######  Assumption 4.

(Lipschitz Continuous Gradients) For any model $\tilde{x}\in{\mathbb{R}}^{p}$
and every regular agent $i\in\mathcal{R}$,
$\mathbb{E}[F(\tilde{x},\xi_{i})]+f_{0}(\tilde{x})$ is differentiable and has
Lipschitz continuous gradients with constants $L_{i}$, where
$\mathbb{E}[F(\tilde{x},\xi_{i})]$ is the local cost function and
$f_{0}(\tilde{x})$ is the regularization term.

######  Assumption 5.

(Bounded Variance) Every regular worker $i\in\mathcal{R}$ samples data with
random variables $\xi_{i}^{k}\sim\mathcal{D}_{i}$ at every time $k$
independently. For any model $\tilde{x}\in{\mathbb{R}}^{p}$, the variance of
$\nabla F(\tilde{x},\xi_{i}^{k})$ is upper bounded by $\delta_{i}^{2}$, i.e.,
${\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[\|\nabla
F(\tilde{x},\xi_{i}^{k})-{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[\nabla
F(\tilde{x},\xi_{i}^{k})]\|^{2}]\leq\delta_{i}^{2},\forall i\in\mathcal{R}$.

The analysis in this paper shares similarities with that in [31]. However,
[31] considers Byzantine-robust centralized stochastic optimization, while
this paper considers the decentralized case. Due to the underlying
decentralized static and time-varying networks, our proofs are significantly
different from those in [31]. Our theoretical results also explicitly show the
influence of the topologies on the performance. Due to the page limit, we
delegate the detailed proofs to [32].

###  3.1 Performance Analysis over Static Network

The first theorem shows that the TV norm-penalized problem (3) is equivalent
to the consensus-constrained one (2) (and hence (1) too), when the penalty
parameter $\lambda$ is sufficiently large. This theorem is analogous to
Theorem 1 in [31], but our proof is based on a system of linear equations
involving the decentralized network structure and different from the proof of
Theorem 1 in [31]. We define
$A\in\mathbb{R}^{|\mathcal{R}|\times|\mathcal{E}_{R}|}$ as the node-edge
incidence matrix of $(\mathcal{R},\mathcal{E}_{R})$. To be specific, for an
edge $e=(i,j)\in\mathcal{E}_{R}$ with $i<j$, the $(i,e)$-th entry of $A$ is
$1$ while the $(j,e)$-th entry of $A$ is $-1$.

######  Theorem 1.

Suppose that Assumptions 1 and 3 hold true. If
$\lambda\geq\lambda_{0}:=\frac{\sqrt{|\mathcal{R}|}}{\tilde{\sigma}_{\min}(A)}max_{i\in\mathcal{R}}\|\nabla\mathbb{E}[F(\tilde{x}^{*},\xi_{i})]+\nabla
f_{0}(\tilde{x}^{*})\|_{\infty}$ where $\tilde{\sigma}_{\min}(A)$ is the
minimum nonzero singular value of $A$, then for the optimal solution $x^{*}$
of (3) and the optimal solution $\tilde{x}^{*}$ of (1), we have
$x^{*}=[\tilde{x}^{*}]$.

No matter how large $\lambda$ is, with a proper step size the proposed
stochastic gradient method can converge to the optimal solution of (3) when
the Byzantine agents are absent. However, the Byzantine agents bring
disturbance to the optimization process, and their influence is illustrated in
the following theorem.

######  Theorem 2.

Suppose that Assumptions 1, 3, 4, 5 hold true. Set the step size of the
proposed method given by (5) as
$\alpha^{k}=\min\\{\underline{\alpha},\frac{\overline{\alpha}}{k+1}\\}$, where
$\underline{\alpha}=\min\limits_{i\in\mathcal{R}}\\{\frac{1}{4(u_{i}+L_{i})}\\}$,
and $\overline{\alpha}>\frac{1}{\eta}$ with
$\eta=\min\limits_{i\in\mathcal{R}}\\{\frac{2u_{i}L_{i}}{u_{i}+L_{i}}\\}-\epsilon>0$
for some $\epsilon>0$. Then, there exists a smallest integer $k_{0}$
satisfying $\underline{\alpha}\geq\frac{\overline{\alpha}}{k_{0}+1}$, such
that

$\displaystyle\mathbb{E}\|x^{k+1}-x^{*}\|^{2}\leq(1-\eta\underline{\alpha})^{k}\|x^{0}-x^{*}\|^{2}+\frac{1}{\eta}(\underline{\alpha}\Delta_{0}+\Delta_{2}),\quad\forall{k}<k_{0},$
(10)

and

$\displaystyle\mathbb{E}\|x^{k+1}-x^{*}\|^{2}\leq\frac{\Delta_{1}}{k+1}+\overline{\alpha}\Delta_{2},\quad\forall{k}\geq
k_{0}.$ (11)

Here we take expectations over all the random variables and define constants

$\displaystyle\Delta_{0}=\sum\limits_{i\in\mathcal{R}}\Big{(}32\lambda^{2}|\mathcal{R}_{i}|^{2}p+4\lambda^{2}|\mathcal{B}_{i}|^{2}p+2\delta_{i}^{2}\Big{)},~{}\Delta_{1}=\max\Bigg{\\{}\frac{\overline{\alpha}^{2}\Delta_{0}}{\eta\overline{\alpha}-1},(k_{0}+1)\mathbb{E}\|x^{k_{0}}-x^{*}\|^{2}+\frac{\overline{\alpha}^{2}\Delta_{0}}{k_{0}+1}\Bigg{\\}},~{}\Delta_{2}=\sum\limits_{i\in\mathcal{R}}\frac{\lambda^{2}|\mathcal{B}_{i}|^{2}p}{\epsilon}.$

Theorem 2 asserts that the proposed Byzantine-robust decentralized stochastic
optimization method can reach a neighborhood of the optimal solution $x^{*}$
of (3). The convergence rate is sublinear and matches the rates of Byzantine-
free decentralized stochastic optimization methods [3, 4, 5, 6]. The size of
neighborhood is proportional to $p$ (the dimension of model), $\lambda^{2}$
(squared penalty parameter), and $\sum_{i\in\mathcal{R}}|\mathcal{B}_{i}|^{2}$
that is determined by the number of Byzantine agents and the network topology.
Combining Theorems 1 and 2, we derive the main Theorem as follows.

######  Theorem 3.

Under the same conditions of Theorem 2, if choosing $\lambda\geq\lambda_{0}$,
then for a sufficiently large $k\geq k_{0}$, we have

$\displaystyle\mathbb{E}\|x^{k+1}-[\tilde{x}^{*}]\|^{2}\leq\frac{\Delta_{1}}{k+1}+\overline{\alpha}\Delta_{2}.$
(12)

If choosing $0<\lambda<\lambda_{0}$ and supposing that the difference between
the optimizers of (3) and (1) is bounded by
$\|x^{*}-[\tilde{x}^{*}]\|^{2}\leq\Delta_{3}$, then for a sufficiently large
$k\geq k_{0}$, we have

$\displaystyle\mathbb{E}\|x^{k+1}-[\tilde{x}^{*}]\|^{2}\leq\frac{2\Delta_{1}}{k+1}+2\overline{\alpha}\Delta_{2}+2\Delta_{3}.$
(13)

When $\lambda$ is large enough, according to Theorem 1, (3) is equivalent to
(1). Therefore, the gap between $x^{k}$ and $x^{*}$ directly translates to the
gap between $x^{k}$ and $[\tilde{x}^{*}]$ as in (12). However, if $\lambda$ is
too large, the gap will also be large because $\Delta_{2}$ is proportional to
$\lambda^{2}$. When $\lambda$ is too small, (3) cannot guarantee to have a
consensual solution. In this case, the gap between $[\tilde{x}^{*}]$ and
$x^{*}$ is unclear, but we assume that it is bounded by $\Delta_{3}$.
Therefore, we are also able to characterize the gap between $x^{k}$ and
$[\tilde{x}^{*}]$ as in (13).

###  3.2 Performance Analysis over Time-Varying Network

Analogous to Theorem 1, when the network is time-varying, we can also show
that as long as $\lambda$ is large enough, the penalized problem (7) has the
same optimal solution as the Byzantine-free problem (1). Also, we define an
incidence matrix to determine how large $\lambda$ should be to guarantee
consensus, yet in the time-varying case it depends on the connectivity of the
average network. In specific, the weighted incidence matrix
$\bar{A}\in\mathbb{R}^{|\mathcal{R}|\times|\bar{\mathcal{E}}_{R}|}$ of the
average network is constructed according to the $\bar{a}_{e}$’s. For an edge
$e=(i,j)\in\bar{\mathcal{E}}_{R}$ with $i<j$, the $(i,e)$-th entry of
$\bar{A}$ is $\bar{a}_{e}$ while the $(j,e)$-th entry of $\bar{A}$ is
$-\bar{a}_{e}$.

######  Theorem 4.

Suppose that Assumption 2 and 3 hold true. If
$\lambda\geq\lambda_{0}:=\frac{\sqrt{|\mathcal{R}|}}{\tilde{\sigma}_{\min}(\bar{A})}max_{i\in\mathcal{R}}\|\nabla\mathbb{E}[F(\tilde{x}^{*},\xi_{i})]+\nabla
f_{0}(\tilde{x}^{*})\|_{\infty}$ where $\tilde{\sigma}_{\min}(\bar{A})$ is the
minimum nonzero singular value of the weighted node-edge incidence matrix
$\bar{A}$ of $(\mathcal{R},\bar{\mathcal{E}}_{R})$, then for the optimal
solution $x^{*}$ of (7) and the optimal solution $\tilde{x}^{*}$ of (1),
almost surely  we have $x^{*}=[\tilde{x}^{*}]$.

Different to the static case where the critical parameter $\lambda_{0}$
depends on the node-edge incidence matrix $A$ of
$(\mathcal{R},\mathcal{\mathcal{E}_{R}})$, here $\lambda_{0}$ depends on the
weighted node-edge incidence matrix $\bar{A}$ of
$(\mathcal{R},\mathcal{\bar{\mathcal{E}}_{R}})$. When the time-varying network
degenerates to the static one, we have $\bar{A}=A$ such that Theorem 4
coincides with Theorem 1.

In the time-varying network model, define $\mathcal{R}_{i}$ as the set of all
possible neighbors of agent $i$. To be specific,
$\mathcal{R}_{i}=\\{j:j\in\mathcal{R}_{i}(\zeta^{k})\text{ for some
}\zeta^{k}\text{ or }j\in\mathcal{R}_{i}(\bar{\zeta})\text{ for some
}\bar{\zeta}\\}$. With $\mathcal{R}_{i}$, we are ready to establish the
following theorem which implies the convergence property of the proposed
stochastic subgradient method under Byzantine attacks.

######  Theorem 5.

Suppose that Assumptions 2, 3, 4, 5 hold true. Set the step size of the
proposed method given by (9) as
$\alpha^{k}=\min\\{\underline{\alpha},\frac{\overline{\alpha}}{k+1}\\}$, where
$\underline{\alpha}=\min_{i\in\mathcal{R}}\\{\frac{1}{4(u_{i}+L_{i})}\\}$, and
$\overline{\alpha}>\frac{1}{\eta}$ with
$\eta=\min\limits_{i\in\mathcal{R}}\\{\frac{2u_{i}L_{i}}{u_{i}+L_{i}}\\}-\epsilon>0$
for some $\epsilon>0$. Then, there exists a smallest integer $k_{0}$
satisfying $\underline{\alpha}\geq\frac{\overline{\alpha}}{k_{0}+1}$, such
that almost surely for any Byzantine attack, we have

$\displaystyle\mathbb{E}\|x^{k+1}-x^{*}\|^{2}\leq(1-\eta\underline{\alpha})^{k}\|x^{0}-x^{*}\|^{2}+\frac{1}{\eta}(\underline{\alpha}\Delta_{4}+\Delta_{6}),\quad\forall{k}<k_{0},$
(14)

and

$\displaystyle\mathbb{E}\|x^{k+1}-x^{*}\|^{2}\leq\frac{\Delta_{5}}{k+1}+\overline{\alpha}\Delta_{6},\quad\forall{k}\geq
k_{0}.$ (15)

Here the expectation $\mathbb{E}$ is taken over all the random samples
$\xi^{k}_{i}\sim\mathcal{D}_{i}$ and the constants are defined as

$\displaystyle\Delta_{4}=\sum\limits_{i\in\mathcal{R}}\Big{(}{\color[rgb]{0,0,0}32}\lambda^{2}|\mathcal{R}_{i}|^{2}p+4\lambda^{2}|\mathcal{B}_{i}|^{2}p+2\delta_{i}^{2}\Big{)},\quad\Delta_{5}=\max\Bigg{\\{}\frac{\overline{\alpha}^{2}\Delta_{4}}{\eta\overline{\alpha}-1},(k_{0}+1)\mathbb{E}\|x^{k_{0}}-x^{*}\|^{2}+\frac{\overline{\alpha}^{2}\Delta_{4}}{k_{0}+1}\Bigg{\\}},$

and

$\displaystyle\Delta_{6}=\sum\limits_{i\in\mathcal{R}}\bigg{(}\frac{2\lambda^{2}|\mathcal{B}_{i}|^{2}p}{\epsilon}+\frac{8\lambda^{2}|\mathcal{R}_{i}|^{2}p}{\epsilon}\bigg{)}.$

With Theorem 5, we conclude that the proposed Byzantine-robust decentralized
stochastic optimization method can also reach a neighborhood of the optimal
solution $x^{*}$ of (7) when the underlying network is time-varying. Combining
Theorems 4 and 5, we get the main theorem as follows.

######  Theorem 6.

Under the same conditions of Theorem 5, if choosing $\lambda\geq\lambda_{0}$,
then for a sufficiently large $k\geq k_{0}$, almost surely we have

$\displaystyle\mathbb{E}\|x^{k+1}-[\tilde{x}^{*}]\|^{2}\leq\frac{\Delta_{5}}{k+1}+\overline{\alpha}\Delta_{6}.$
(16)

If choosing $0<\lambda<\lambda_{0}$ and supposing that the difference between
the optimizers of (7) and (1) is bounded by
$\|x^{*}-[\tilde{x}^{*}]\|^{2}\leq\Delta_{7}$, then for a sufficiently large
$k\geq k_{0}$, almost surely we have

$\displaystyle\mathbb{E}\|x^{k+1}-[\tilde{x}^{*}]\|^{2}\leq\frac{2\Delta_{5}}{k+1}+2\overline{\alpha}\Delta_{6}+2\Delta_{7}.$
(17)

##  4 Numerical Experiments

In this section, we conduct several numerical experiments to demonstrate the
robustness of our proposed method to Byzantine attacks over static and time-
varying networks.

###  4.1 Numerical Experiments over Static Network

Consider a static Erdos-Renyi network consisting of $n=30$ agents, where every
edge $e$ is activated with probability $p_{e}=0.7$. Randomly choose $b$ agents
to be Byzantine, but guarantee that the network of regular agents is
connected.

We consider the softmax regression problem, which is defined as

$\displaystyle
F(\tilde{x})=-\frac{1}{N}\sum_{l=1}^{N}\sum_{m=0}^{M-1}\Big{(}I(w^{(l)}=m)\ln\Big{(}\frac{exp((\tilde{x})_{m}^{T}v^{(l)})}{\sum_{j=0}^{M-1}exp((\tilde{x})_{j}^{T}v^{(l)})}\Big{)}\Big{)}.$

Here $N$ and $M$ are the numbers of data samples and data classes,
respectively. Further, $(v^{(l)},w^{(l)})$ is the $l$-th data sample with
$v^{(l)}\in{\mathbb{R}}^{p/M}$ and $w^{(l)}\in{\mathbb{R}}$, and
$I(w^{(l)}=m)$ is the indicator function with $I(w^{(l)}=m)=1$ if $w^{(l)}=m$
and $I(w^{(l)}=m)=0$ otherwise. The model parameter is
$\tilde{x}\in{\mathbb{R}}^{p}$ and $(\tilde{x})_{j}\in{\mathbb{R}}^{p/M}$ is
the $j$-th block of $\tilde{x}$. The dataset is MNIST, which contains $M=10$
handwritten digits from 0 to 9, with 60,000 training images and 10,000 testing
images whose dimensions are $p/M=784$. In the i.i.d. case, we randomly and
evenly distribute the training images to all the agents. In the non-i.i.d.
case, we let every three agents evenly split the training images of one digit.
We use the softmax regression with regularization term
$f_{0}(\tilde{x})=\frac{0.01}{2}\|\tilde{x}\|_{2}^{2}$ to learn the model. At
the testing stage, we randomly choose one regular agent and use its local
model to calculate the classification accuracy. Also, we calculate the
variance of regular agents’ local models to quantify the level of consensus.

The benchmark methods are DPSGD [3], as well as the stochastic versions of
ByRDiE [16] and BRIDGE [17] (denoted by ByRDiE-S and BRIDGE-S, respectively).
In DPSGD, the mixing matrix is constructed following the equal neighbor
weights rule [33]. In ByRDiE-S, the coordinates of the model are updated
sequentially. We set the number of inner-loop iterations to update every
coordinate to be 1, as suggested by [16]. For fair comparison, in ByRDiE-S one
iteration refers to that all the coordinates have been updated once. Step
sizes of the benchmark methods are hand-tuned to the best. In all the compared
methods, the batch-size is set as 32.

Figure 1: Classification accuracy and variance of regular agents’ local models
without Byzantine attacks.

Figure 2: Classification accuracy and variance of regular agents’ local models
under zero-sum attacks.

Figure 3: Classification accuracy and variance of regular agents’ local models
under same-value attacks.

Figure 4: Classification accuracy and variance of regular agents’ local models
under sign-flipping attacks.

Without Byzantine Attacks. When the number of Byzantine agents is $b=0$, all
the methods perform well in terms of both classification accuracy and level of
consensus, as depicted in Figure 1. In our proposed method, we set the penalty
parameter as $\lambda=0.005$ and the step size as
$\alpha^{k}=\frac{0.3}{\sqrt{k+1}}$. Because of the sensitivity of the
$O(\frac{1}{k})$ step size to its initial value, we use the
$O(\frac{1}{\sqrt{k}})$ step size in the numerical experiments.

Zero-sum Attacks. Let the number of Byzantine agents be $b=3$. Every Byzantine
agent $j\in\mathcal{B}$ sends
$z_{j}^{k}=-\frac{\sum_{l\in\mathcal{R}_{i}}x_{l}^{k}}{|\mathcal{B}_{i}|}$ to
its regular neighbor $i\in\mathcal{R}$, such that the received messages of $i$
are summed to zero. In our proposed method, the penalty parameter is
$\lambda=0.001$ and the step size is $\alpha^{k}=\frac{0.9}{\sqrt{k+1}}$. With
results depicted in Figure 2, we observe that DPSGD fails because of its
vulnerability to Byzantine attacks. Our proposed method, BRIDGE-S and ByRDiE-S
are robust to the zero-sum attacks.

Same-value Attacks. Let the number of Byzantine agents be $b=3$. Every
Byzantine agent $j\in\mathcal{B}$ sends $z_{j}^{k}=c\mathbf{1}$ to its
neighbors. Here $\mathbf{1}\in{\mathbb{R}}^{p}$ is an all-one vector and $c$
is a constant which we set as 100. In our proposed method, the penalty
parameter is $\lambda=0.01$ and the step size is
$\alpha^{k}=\frac{0.28}{\sqrt{k+1}}$. As shown in Figure 3, DPSGD fails and
our proposed method is the best among all the three Byzantine-robust methods
in terms of classification accuracy. Its variance is higher than that of
ByRDiE-S, but small enough such that all the regular agents have high
classification accuracies.

Sign-flipping Attacks. Let the number of Byzantine agents be $b=3$. Every
Byzantine agent $j\in\mathcal{B}$ first calculates its true model, and then
multiplies it with a negative constant $\gamma$ and sends to its neighbors.
Here we set $\gamma=-4$. In our proposed method, the penalty parameter is
$\lambda=0.0022$ and the step size is $\alpha^{k}=\frac{0.5}{\sqrt{k+1}}$. As
shown in Figure 4, the results are consistent with those under the same-value
attacks, but the performance gain of our proposed method in terms of
classification accuracy is more obvious. Note that we choose a relatively
small $\lambda$ such that the level of consensus is slightly worse than those
of ByRDiE-S and BRIDGE-S.

Figure 5: Classification accuracy and variance of regular agents’ local models
with different fractions of Byzantine agents under zero-sum attacks.

Figure 6: Classification accuracy and variance of regular agents’ local models
with different $\lambda$ under same-value attacks.

Figure 7: Classification accuracy and variance of regular agents’ local models
based on different norms under sign-flipping attacks.

Impact of Fraction of Byzantine Agents. We study the robustness of our
proposed method with different fractions of Byzantine agents under the zero-
sum attacks. In our proposed method, we set the penalty parameter
$\lambda=0.001$ and the step size $\alpha^{k}=\frac{0.9}{\sqrt{k+1}}$. Since
ByRDiE-S and BRIDGE-S require $n\geq 2b+1$, we let no more than half of the
agents be Byzantine. When the fraction of Byzantine agents increases, as
depicted in Figure 5, the performance of all the methods degrades slightly.

Impact of Penalty Parameter $\lambda$. To investigate the impact of penalty
parameter $\lambda$, we choose several different values for $\lambda$ in the
setting of same-value attacks with $b=3$ Byzantine agents. The step sizes are
hand-tuned to the best. As shown in Figure 6, larger $\lambda$ ensures better
consensus, which corroborates the theoretical results in Section 3. When
$\lambda=0$, the level of consensus is the worst, since the agents do not
communicate and learn with their own local data samples independently.
However, larger $\lambda$ leads to larger gap relative to the Byzantine-free
optimal solution, and hence lower classification accuracy. This observation
also matches the theoretical results in Section 3.

Penalty with Different Norms. To validate the effectiveness of TV norm penalty
with different norms, we compare our proposed method with $\ell_{1}$,
$\ell_{2}$ and $\ell_{\infty}$ norms under sign-flipping attacks. We set
$\lambda=0.0022$ and $\alpha^{k}=\frac{0.5}{\sqrt{k+1}}$ in the $\ell_{1}$
case, $\lambda=0.2$ and $\alpha^{k}=\frac{0.4}{\sqrt{k+1}}$ in the $\ell_{2}$
case, while $\lambda=0.9$ and $\alpha^{k}=\frac{0.4}{\sqrt{k+1}}$ in the
$\ell_{\infty}$ case. As shown in Figure 7, the accuracies of our proposed
method with different norms are similar with different norms, but the result
with $\ell_{\infty}$ norm has the biggest variance since it needs a large
$\lambda$ to guarantee consensus. We deliberately choose a moderate $\lambda$
to ensure accuracy but sacrifice consensus in the $\ell_{\infty}$ case.

Figure 8: Classification accuracy and variance of regular agents’ local models
with non-i.i.d. data.

Figure 9: Classification accuracy and variance of regular agents’ local models
with different fractions of Byzantine agents and non-i.i.d. data.

Non-i.i.d. Data. Let the number of Byzantine agents be $b=6$. All the
Byzantine agents copy the values of one randomly chosen regular agent, and
send to their neighbors. Recall that every three agents evenly split the
training images of one digit and here we deliberately let the Byzantine agents
share the training images of digits 8 and 9. Therefore, information from
digits 8 and 9 is totally lost and the best classification accuracy we can
reach is no more than 0.8. Note that under these particularly designed
attacks, DPSGD is able to reach a satisfactory classification accuracy. In our
proposed method, the penalty parameter is $\lambda=0.02$ and the step size is
$\alpha^{k}=\frac{0.4}{\sqrt{k+1}}$. As shown in Figure 8, our proposed method
almost coincides with DPSGD with respect to classification accuracy. ByRDiE-S
and BRIDGE-S do not perform well under such attacks, because nine agents
(including six Byzantine agents and three regular agents) essentially use the
training images of one digit, such that the models trained from this
particular digit dominate. Therefore, the majority voting rules of ByRDiE-S
and BRIDGE-S emphasize more on this particular digit, while ignore other
digits relatively.

Impact of Fraction of Byzantine Agents with Non-i.i.d. Data. We further study
the robustness of our proposed method with different fractions of Byzantine
agents with Non-i.i.d. data. The data distributions and Byzantine attacks are
the same as those in the above paragraph. In our proposed method, the penalty
parameter is $\lambda=0.02$ and the step size is
$\alpha^{k}=\frac{0.4}{\sqrt{k+1}}$. Not surprisingly, as shown in Figure 9
the performance of all the methods degrades when the fraction of Byzantine
agents increases. However, different to the i.i.d. case in Figure 5, our
proposed method shows much better robustness than ByRDiE-S and BRIDGE-S in the
non-i.i.d. case.

###  4.2 Numerical Experiments over Time-Varying Network

Consider a static Erdos-Renyi networks consisting of $n=30$ agents, in which
$b=3$ agents are Byzantine but the network of regular agents is connected. We
generate two time-varying networks upon it. At every time $k$, every edge $e$
is randomly activated with probabilities $p_{e}=0.01$ and $p_{e}=0.005$,
respectively. We consider the same-value attacks, where every Byzantine agent
$j\in\mathcal{B}$ sends $z_{j}^{k}=c\mathbf{1}$ to its neighbors, with
$\mathbf{1}\in{\mathbb{R}}^{p}$ being an all-one vector and $c=100$. The
algorithm parameters are: (i) $\lambda=0.01$ and
$\alpha^{k}=\frac{0.28}{\sqrt{k+1}}$ for the static network, (ii)
$\lambda=0.2$ and $\alpha^{k}=\frac{0.5}{\sqrt{k+1}}$ for the time-varying
network with $p_{e}=0.01$, and, (iii) $\lambda=0.4$ and
$\alpha^{k}=\frac{0.5}{\sqrt{k+1}}$ for the time-varying network with
$p_{e}=0.005$. Note that smaller $p_{e}$ means worse connectivity, which leads
to smaller $\tilde{\sigma}_{\min}(\bar{A})$ as we have empirically observed
from the experiments. Therefore, according to Theorem 4, the critical value of
$\lambda$ that guarantees consensus, given by
$\lambda_{0}:=\frac{\sqrt{|\mathcal{R}|}}{\tilde{\sigma}_{\min}(\bar{A})}max_{i\in\mathcal{R}}\|\nabla\mathbb{E}[F(\tilde{x}^{*},\xi_{i})]+\nabla
f_{0}(\tilde{x}^{*})\|_{\infty}$, should be larger for smaller $p_{e}$.

As shown in Figure 10, our proposed method shows remarkable robustness to the
Byzantine attacks even when the network is time-varying. The classification
accuracies are almost the same over the static and the time-varying networks.
The level of consensus degrades when $p_{e}$ decreases. This makes sense
because in a less connected network, information diffusion is slower such that
reaching consensus becomes more difficult.

Figure 10: Classification accuracy and variance of regular agents’ local
models under same-value attacks over static and time-varying networks.

##  5 Conclusion

In this paper, we deal with the Byzantine-robust decentralized stochastic
optimization problem over static and time-varying networks. We introduce the
TV norm penalty to handle Byzantine attacks and propose a stochastic
subgradient method to solve the penalized problem. Theoretical analysis and
numerical experiments demonstrate the robustness of our proposed method to
Byzantine attacks, no matter the network topology is static or time-varying.
In our future work, we will investigate the application of variance reduction
techniques, which have been shown effective in Byzantine-robust centralized
stochastic optimization [35], to the decentralized case. We will also consider
TV norm penalties based on $\ell_{2}$ and $\ell_{\infty}$ norms [31].

Acknowledgement. Qing Ling is supported in part by NSF China Grant 61973324,
and Fundamental Research Funds for the Central Universities. A preliminary
version of this paper has appeared in IEEE International Conference on
Acoustics, Speech, and Signal Processing, Barcelona, Spain, May 4-8, 2020
[36].

##  Appendix A Proof of Theorem 1

Proof. The optimal solution $x^{*}:=[x_{i}^{*}]$ of (3) satisfies the
optimality condition

$\displaystyle\nabla\mathbb{E}[F(x_{i}^{*},\xi_{i})]+\lambda\sum_{j\in\mathcal{R}_{i},i<j}s_{ij}-\lambda\sum_{j\in\mathcal{R}_{i},i>j}{\color[rgb]{0,0,1}s_{ji}}+\nabla
f_{0}(x^{*}_{i})=0,\quad\forall i\in\mathcal{R},$ (18)

where $s_{ij}=sign(x^{*}_{i}-x^{*}_{j})\in[-1,1]^{p}$ for $i<j$. Note that
$x^{*}$ is unique due to the strong convexity given by Assumption 3. We will
prove that $[\tilde{x}^{*}]$ satisfies (18), such that

$\displaystyle\nabla\mathbb{E}[F(\tilde{x}^{*},\xi_{i})]+\lambda\sum_{j\in\mathcal{R}_{i},i<j}s_{ij}-\lambda\sum_{j\in\mathcal{R}_{i},i>j}s_{ji}+\nabla
f_{0}(\tilde{x}^{*})=0,\quad\forall i\in\mathcal{R}.$ (19)

For simplicity, define
$v_{i}:=\nabla\mathbb{E}[F(\tilde{x}^{*},\xi_{i})]+\nabla
f_{0}(\tilde{x}^{*})$. Since (19) can be decomposed element-wise, from now on
we assume the variable dimension $p=1$ such that both $s_{ij}$ and $v_{i}$ are
scalars. Then, (19) can be rewritten as a system of linear equations

$\displaystyle\lambda As+v=0,$ (20)

where $s=[s_{ij}]$ collects all the scalars $s_{ij}$ in order and $v=[v_{i}]$
collects all the scalars $v_{i}$ in order. Now the problem is equivalent to
finding a vector $s$ whose elements are within $[-1,1]$, namely,
$\|s\|_{\infty}\leq 1$, to satisfy (20).

We first show that (20) has at least one solution. To see so, observe that the
rank of $A$ is $|\mathcal{R}|-1$ and the null space of the columns is spanned
by the all-one vector $1_{|\mathcal{R}|}\in\mathbb{R}^{|\mathcal{R}|}$,
because $(\mathcal{R},\mathcal{E}_{R})$ is bidirectionally connected according
to Assumption 1. Meanwhile, according to the optimality condition of (1),
$\sum_{i\in\mathcal{R}}v_{i}=\sum_{i\in\mathcal{R}}\left(\nabla\mathbb{E}[F(\tilde{x}^{*},\xi_{i})]+\nabla
f_{0}(\tilde{x}^{*})\right)=0$. Therefore, the columns of $\lambda A$ and
those of $[\lambda A,v]$ share the same null space and have the same rank.
Consequently, we can find at least one solution to (20).

We next find one solution to (20) that satisfies $\|s\|_{\infty}\leq 1$.
According to the above derivation, we also know that we can find at least one
solution to $s^{\prime}$ to $As^{\prime}+v=0$. Among all the solutions to
$As^{\prime}+v=0$, we consider the least-squares solution given by
$s^{\prime}=-A^{\dagger}v$, where ${\dagger}$ denotes the pseudo inverse. This
solution is bounded by

$\|s^{\prime}\|_{2}=\|A^{\dagger}v\|_{2}\leq\sigma_{\max}(A^{\dagger})\|v\|_{2}\leq\frac{1}{\tilde{\sigma}_{\min}(A)}\|v\|_{2},$

where $\sigma_{\max}(\cdot)$ and $\tilde{\sigma}_{\min}(\cdot)$ denotes the
largest and the smallest nonzero singular values, respectively. Since
$\|s^{\prime}\|_{\infty}\leq\|s^{\prime}\|_{2}$ and
$\|v\|_{2}\leq\sqrt{|\mathcal{R}|}\|v\|_{\infty}$, we further have

$\|s^{\prime}\|_{\infty}\leq\frac{\sqrt{|\mathcal{R}|}}{\tilde{\sigma}_{\min}(A)}\|v\|_{\infty}=\frac{\sqrt{|\mathcal{R}|}}{\tilde{\sigma}_{\min}(A)}max_{i\in\mathcal{R}}|v_{i}|.$

Then, we construct $s=\frac{1}{\lambda}s^{\prime}$, which is a solution to
(20) because $As^{\prime}+v=0$. In addition, we have

$\|s\|_{\infty}=\frac{1}{\lambda}\|s^{\prime}\|_{\infty}\leq\frac{\sqrt{|\mathcal{R}|}}{\lambda\tilde{\sigma}_{\min}(A)}max_{i\in\mathcal{R}}|v_{i}|,$

which is less than $1$ as long as
$\lambda\geq\frac{\sqrt{|\mathcal{R}|}}{\tilde{\sigma}_{\min}(A)}max_{i\in\mathcal{R}}|v_{i}|$.

Now we consider the variable dimension $p\geq 1$. For all the dimensions we
construct vectors $s$ in this way such that $\|s\|_{\infty}\leq 1$ as long as
$\lambda\geq\lambda_{0}:=\frac{\sqrt{|\mathcal{R}|}}{\tilde{\sigma}_{\min}(A)}max_{i\in\mathcal{R}}\|\nabla\mathbb{E}[F(\tilde{x}^{*},\xi_{i})]+\nabla
f_{0}(\tilde{x}^{*})\|_{\infty}$. This completes the proof.

##  Appendix B Proof of Theorem 2

Proof. Step 1. We first take conditional expectations given the variables up
to time $k$, namely $\\{x_{i}^{l}:l\leq k,i\in\mathcal{R}\\}$, and then take
the expectation over $\\{x_{i}^{l}:l\leq k,i\in\mathcal{R}\\}$. We simply
denote $\mathbb{E}[\cdot|x_{i}^{l}:l\leq k,i\in\mathcal{R}]$ as
$\mathbb{E}_{k}[\cdot]$. From the update (5) at every regular agent $i$, we
have:

$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|x_{i}^{k+1}-x_{i}^{*}\|^{2}$
(21) $\displaystyle=$
$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|x_{i}^{k}-x_{i}^{*}-\alpha^{k}\big{(}\nabla
F(x_{i}^{k},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\lambda\sum_{j\in\mathcal{B}_{i}}sign(x_{i}^{k}-z_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\big{)}\|^{2}$ $\displaystyle=$
$\displaystyle\|x_{i}^{k}-x_{i}^{*}\|^{2}+(\alpha^{k})^{2}{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|\nabla
F(x_{i}^{k},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\lambda\sum_{j\in\mathcal{B}_{i}}sign(x_{i}^{k}-z_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}$
$\displaystyle-2\alpha^{k}\langle{\color[rgb]{0,0,0}\mathbb{E}_{k}}[\nabla
F(x_{i}^{k},\xi_{i}^{k})]\
+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k}),x_{i}^{k}-x_{i}^{*}\rangle-2\alpha^{k}\langle\lambda\sum_{j\in\mathcal{B}_{i}}sign(x_{i}^{k}-z_{j}^{k}),x_{i}^{k}-x_{i}^{*}\rangle.$

Below, we handle the terms at the right-hand side of (21) one by one.

For the second term at the right-hand side of (21), we have

$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|\nabla
F(x_{i}^{k},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\lambda\sum_{j\in\mathcal{B}_{i}}sign(x_{i}^{k}-z_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}$ (22) $\displaystyle=$
$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|\nabla{\color[rgb]{0,0,0}\mathbb{E}_{k}}[F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\lambda\sum_{j\in\mathcal{B}_{i}}sign(x_{i}^{k}-z_{j}^{k})+\nabla
f_{0}(x_{i}^{k})+\nabla
F(x_{i}^{k},\xi_{i}^{k})-\nabla{\color[rgb]{0,0,0}\mathbb{E}_{k}}[F(x_{i}^{k},\xi_{i}^{k})]\|^{2}$
$\displaystyle\leq$ $\displaystyle
2\|\nabla{\color[rgb]{0,0,0}\mathbb{E}_{k}}[F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\lambda\sum_{j\in\mathcal{B}_{i}}sign(x_{i}^{k}-z_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}+2{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|F(x_{i}^{k},\xi_{i}^{k})-\nabla{\color[rgb]{0,0,0}\mathbb{E}_{k}}[F(x_{i}^{k},\xi_{i}^{k})]\|^{2}$
$\displaystyle\leq$ $\displaystyle
4\|\nabla{\color[rgb]{0,0,0}\mathbb{E}_{k}}[F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}+4\lambda^{2}\|\sum_{j\in\mathcal{B}_{i}}sign(x_{i}^{k}-z_{j}^{k})\|^{2}+2{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|F(x_{i}^{k},\xi_{i}^{k})-\nabla{\color[rgb]{0,0,0}\mathbb{E}_{k}}[F(x_{i}^{k},\xi_{i}^{k})]\|^{2}$
$\displaystyle\leq$ $\displaystyle
4\|\nabla{\color[rgb]{0,0,0}\mathbb{E}_{k}}[F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}+4\lambda^{2}|\mathcal{B}_{i}|^{2}p+2\delta_{i}^{2},$

where the last inequality holds true because each element of the
$p$-dimensional vector $sign(x_{i}^{k}-z_{j}^{k})$ is within $[-1,1]$, and the
variance is bounded by
${\color[rgb]{0,0,0}\mathbb{E}_{k}}\|F(x_{i}^{k},\xi_{i}^{k})-\nabla{\color[rgb]{0,0,0}\mathbb{E}_{k}}[F(x_{i}^{k},\xi_{i}^{k})]\|^{2}\leq\delta_{i}^{2}$
stated in Assumption 5 and the independence of random $\xi_{i}^{k}$’s. Recall
the optimality condition of (3) shown in (18). For simplicity, we define
$s_{ji}=-s_{ij}$ for $j>i$, then

$\nabla\mathbb{E}[F(x_{i}^{*},\xi_{i})]+\lambda\sum_{j\in\mathcal{R}_{i}}s_{ij}+\nabla
f_{0}(x_{i}^{*})=0,$ (23)

which holds true for some $s_{ij}=sign(x_{i}^{*}-x_{j}^{*})\in[-1,1]^{p}$.
Plugging this equation into the first term at the right-hand side of (22) and
replacing $\xi_{i}$ by $\xi_{i}^{k}$, we have

$\displaystyle
4\|\nabla\mathbb{E}_{k}[F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}$ (24) $\displaystyle=$ $\displaystyle
4\|\nabla\mathbb{E}_{k}[F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k})-\nabla\mathbb{E}_{k}[F(x_{i}^{*},\xi_{i}^{k})]-\lambda\sum_{j\in\mathcal{R}_{i}}{\color[rgb]{0,0,0}s_{ij}}-\nabla
f_{0}(x_{i}^{*})\|^{2}$ $\displaystyle\leq$ $\displaystyle
8\|\nabla\mathbb{E}_{k}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{k})-\nabla\mathbb{E}_{k}[F(x_{i}^{*},\xi_{i}^{k})]-\nabla
f_{0}(x_{i}^{*})\|^{2}+8\lambda^{2}\|\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})-\sum_{j\in\mathcal{R}_{i}}s_{ij}\|^{2}$
$\displaystyle\leq$ $\displaystyle
8\|\nabla\mathbb{E}_{k}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{k})-\nabla\mathbb{E}_{k}[F(x_{i}^{*},\xi_{i}^{k})]-\nabla
f_{0}(x_{i}^{*})\|^{2}+32\lambda^{2}|\mathcal{R}_{i}|^{2}p,$

where the first inequality is due to $(a+b)^{2}\leq 2a^{2}+2b^{2}$. Combining
(22) and (24), we have

$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|\nabla
F(x_{i}^{k},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\lambda\sum_{j\in\mathcal{B}_{i}}sign(x_{i}^{k}-z_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}$ (25) $\displaystyle\leq$
$\displaystyle{\color[rgb]{0,0,0}8\|\nabla{\color[rgb]{0,0,0}\mathbb{E}_{k}}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{k})-\nabla{\color[rgb]{0,0,0}\mathbb{E}_{k}}[F(x_{i}^{*},\xi_{i}^{k})]-\nabla
f_{0}(x_{i}^{*})\|^{2}+32}\lambda^{2}|\mathcal{R}_{i}|^{2}p+4\lambda^{2}|\mathcal{B}_{i}|^{2}p+2\delta_{i}^{2}.$

For the third term at the right-hand side of (21), noticing that $x_{i}^{k}$
is independent with $\xi_{i}^{k}$ such that

$\displaystyle\langle{\color[rgb]{0,0,0}\mathbb{E}_{k}}[\nabla
F(x_{i}^{k},\xi_{i}^{k})],x_{i}^{k}-x_{i}^{*}\rangle=\langle\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})],x_{i}^{k}-x_{i}^{*}\rangle,$
(26)

we have

$\displaystyle-2\langle{\color[rgb]{0,0,0}\mathbb{E}_{k}}[\nabla
F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k}),x_{i}^{k}-x_{i}^{*}\rangle$ (27) $\displaystyle=$
$\displaystyle-2\langle\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k}),x_{i}^{k}-x_{i}^{*}\rangle.$

Plugging the optimality condition (23) into (27) , we have

$\displaystyle-2\langle\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k}),x_{i}^{k}-x_{i}^{*}\rangle$ (28) $\displaystyle=$
$\displaystyle-2\langle\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{k})-\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{*},\xi_{i}^{k})]-\nabla
f_{0}(x_{i}^{*}),x_{i}^{k}-x_{i}^{*}\rangle-2\langle\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})-\lambda\sum_{j\in\mathcal{R}_{i}}{\color[rgb]{0,0,0}s_{ij}},x_{i}^{k}-x_{i}^{*}\rangle$

Since we assume that the functions
${\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i},{\color[rgb]{0,0,0}\xi_{i}^{k}})]+f_{0}(x_{i})$
are strongly convex and have Lipschitz continuous gradients (cf. Assumption 3
and 4), by [34] we have

$\displaystyle-2\langle\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{k})-\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{*},\xi_{i}^{k})]-\nabla
f_{0}(x_{i}^{*}),x_{i}^{k}-x_{i}^{*}\rangle$ (29) $\displaystyle\leq$
$\displaystyle-\frac{2u_{i}L_{i}}{u_{i}+L_{i}}\|x_{i}^{k}-x_{i}^{*}\|^{2}-\frac{2}{u_{i}+L_{i}}\|\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{K})-\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{*},\xi_{i}^{k})]^{2}-\nabla
f_{0}(x_{i}^{*})\|^{2}.$

Substituting (28), (29) into (27), we have

$\displaystyle-2\langle\mathbb{E}_{k}[\nabla
F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k}),x_{i}^{k}-x_{i}^{*}\rangle$ (30) $\displaystyle\leq$
$\displaystyle-2\langle\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})-\lambda\sum_{j\in\mathcal{R}_{i}}{\color[rgb]{0,0,0}s_{ij}},x_{i}^{k}-x_{i}^{*}\rangle-(\frac{2u_{i}L_{i}}{u_{i}+L_{i}})\
\|x_{i}^{k}-x_{i}^{*}\|^{2}$ $\displaystyle-\frac{2}{u_{i}+L_{i}}\
\|\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{k})-\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{*},\xi_{i}^{k})]-\nabla
f_{0}(x_{i}^{*})\|^{2}.$

For the last term at the right-hand side of (21), it holds for any
$\epsilon>0$ that

$\displaystyle-2\langle\lambda\sum_{j\in\mathcal{B}_{i}}sign(x_{i}^{k}-z_{j}^{k}),x_{i}^{k}-x_{i}^{*}\rangle$
(31) $\displaystyle\leq$
$\displaystyle\epsilon\|x_{i}^{k}-x_{i}^{*}\|^{2}+\frac{\lambda^{2}}{\epsilon}\|\sum_{j\in\mathcal{B}_{i}}sign(x_{i}^{k}-z_{j}^{k})\|^{2}$
$\displaystyle\leq$
$\displaystyle\epsilon\|x_{i}^{k}-x_{i}^{*}\|^{2}+\frac{\lambda^{2}|\mathcal{B}_{i}|^{2}p}{\epsilon}.$

Substituting (25), (30) and (31) into (21) and combining the terms, we have

$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|x_{i}^{k+1}-x_{i}^{*}\|^{2}$
(32) $\displaystyle\leq$
$\displaystyle\big{(}1-\alpha^{k}(\frac{2u_{i}L_{i}}{u_{i}+L_{i}}-\epsilon)\big{)}\|x_{i}^{k}-x_{i}^{*}\|^{2}+(\alpha^{k})^{2}(32\lambda^{2}|\mathcal{R}_{i}|^{2}p+4\lambda^{2}|\mathcal{B}_{i}|^{2}p+2\delta_{i}^{2})+\alpha^{k}\frac{\lambda^{2}|\mathcal{B}_{i}|^{2}p}{\epsilon}$
$\displaystyle-2\alpha^{k}\langle\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})-\lambda\sum_{j\in\mathcal{R}_{i}}{\color[rgb]{0,0,0}s_{ij}},x_{i}^{k}-x_{i}^{*}\rangle$
$\displaystyle-2\alpha^{k}(\frac{1}{u_{i}+L_{i}}-4\alpha^{k})\|\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{k})-\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{*},\xi_{i}^{k})]-\nabla
f_{0}(x_{i}^{*})\|^{2}.$

Due to the step size rule, we have $\frac{1}{u_{i}+L_{i}}-4\alpha^{k}\geq 0$
and hence can drop the last term of at the right-hand side of (32). Also
noticing the definition of $\eta$, we rewrite (32) into

$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|x_{i}^{k+1}-x_{i}^{*}\|^{2}$
(33) $\displaystyle\leq$
$\displaystyle\big{(}1-\eta\alpha^{k}\big{)}\|x_{i}^{k}-x_{i}^{*}\|^{2}+(\alpha^{k})^{2}({\color[rgb]{0,0,0}32}\lambda^{2}|\mathcal{R}_{i}|^{2}p+4\lambda^{2}|\mathcal{B}_{i}|^{2}p+2\delta_{i}^{2})+\alpha^{k}\frac{\lambda^{2}|\mathcal{B}_{i}|^{2}p}{\epsilon}$
$\displaystyle-2\alpha^{k}\langle\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})-\lambda\sum_{j\in\mathcal{R}_{i}}{\color[rgb]{0,0,0}s_{ij}},x_{i}^{k}-x_{i}^{*}\rangle.$

Step 2. Here we define
$I_{p}(x)=\frac{\lambda}{2}\sum_{i\in\mathcal{R}}\sum_{j\in\mathcal{R}_{i}}\|x_{i}-x_{j}\|_{1}$.
Since $I_{p}(x)$ is convex, we have

$\displaystyle\langle\partial_{x}I_{p}(x^{k})-\partial_{x}I_{p}(x^{*}),x^{k}-x^{*}\rangle$
(34) $\displaystyle=$
$\displaystyle\sum_{i\in\mathcal{R}}\langle\lambda\sum_{j\in\mathcal{R}_{i}}sign(x_{i}^{k}-x_{j}^{k})-\lambda\sum_{j\in\mathcal{R}_{i}}{\color[rgb]{0,0,0}s_{ij}},x_{i}^{k}-x_{i}^{*}\rangle\geq
0.$

Summing up (33) over all regular agents $i\in\mathcal{R}$ and adding to (34),
we have

$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|x^{k+1}-x^{*}\|^{2}$ (35)
$\displaystyle\leq$
$\displaystyle\big{(}1-\eta\alpha^{k}\big{)}\|x^{k}-x^{*}\|^{2}+(\alpha^{k})^{2}\
\sum_{i\in\mathcal{R}}\
({\color[rgb]{0,0,0}32}\lambda^{2}|\mathcal{R}_{i}|^{2}p+4\lambda^{2}|\mathcal{B}_{i}|^{2}p+2\delta_{i}^{2})+\alpha^{k}\sum_{i\in\mathcal{R}}\frac{\lambda^{2}|\mathcal{B}_{i}|^{2}p}{\epsilon}.$

Taking the full expectation of (35), then we get

$\displaystyle\mathbb{E}\|x^{k+1}-x^{*}\|^{2}=\mathbb{E}[\mathbb{E}_{k}\|x^{k+1}-x^{*}\|^{2}]\leq(1-\eta\alpha^{k})\mathbb{E}\|x^{k}-x^{*}\|^{2}+(\alpha^{k})^{2}\Delta_{0}+\alpha^{k}\Delta_{2},$
(36)

where the constants $\Delta_{0}$ and $\Delta_{2}$ are defined as

$\displaystyle\Delta_{0}=\sum\limits_{i\in\mathcal{R}}\big{(}$
$\displaystyle{\color[rgb]{0,0,0}32}\lambda^{2}|\mathcal{R}_{i}|^{2}p+4\lambda^{2}|\mathcal{B}_{i}|^{2}p+2\delta_{i}^{2}\big{)},\quad\Delta_{2}=\sum\limits_{i\in\mathcal{R}}\frac{\lambda^{2}|\mathcal{B}_{i}|^{2}p}{\epsilon}.$

Step 3. According to the step size rule
$\alpha^{k}=\min\\{\underline{\alpha},\frac{\overline{\alpha}}{k+1}\\}$, there
exists a smallest integer $k_{0}$ satisfying
$\underline{\alpha}\geq\frac{\overline{\alpha}}{k_{0}+1}$ such that
$\alpha^{k}=\underline{\alpha}$ when $k<k_{0}$ and
$\alpha^{k}=\frac{\overline{\alpha}}{k+1}$ when $k\geq k_{0}$. Then for all
$k<k_{0}$, (35) becomes

$\displaystyle\mathbb{E}\|x^{k+1}-x^{*}\|^{2}\leq\big{(}1-\eta\underline{\alpha}\big{)}\mathbb{E}\|x^{k}-x^{*}\|^{2}+(\underline{\alpha})^{2}\Delta_{0}+\underline{\alpha}\Delta_{2},\quad\forall
k<k_{0}.$ (37)

By the definitions of $\eta$ and $\underline{\alpha}$,
$\eta\underline{\alpha}\in(0,1)$. Applying telescopic cancellation to (37)
through time 0 to $k<k_{0}$ yields

$\displaystyle\mathbb{E}\|x^{k+1}-x^{*}\|^{2}\leq(1-\eta\underline{\alpha})^{k}\mathbb{E}\|x^{0}-x^{*}\|^{2}+\frac{1}{\eta}(\underline{\alpha}\Delta_{0}+\Delta_{2}),\quad\forall{k}<k_{0}.$
(38)

For all $k\geq k_{0}$, (35) becomes

$\displaystyle\mathbb{E}\|x^{k+1}-x^{*}\|^{2}\leq\big{(}1-\frac{\eta\overline{\alpha}}{k+1}\big{)}\mathbb{E}\|x^{k}-x^{*}\|^{2}+\frac{(\overline{\alpha})^{2}\Delta_{0}}{(k+1)^{2}}+\frac{\overline{\alpha}\Delta_{2}}{k+1},\quad\forall
k\geq k_{0}.$ (39)

Note that $1-\frac{\eta\overline{\alpha}}{k+1}\in(0,1)$ when $k\geq k_{0}$.
Below, we use induction to prove

$\displaystyle\mathbb{E}\|x^{k+1}-x^{*}\|^{2}\leq\frac{\Delta_{1}}{k+1}+\overline{\alpha}\Delta_{2}.\quad\forall{k}\geq
k_{0},$ (40)

where

$\displaystyle\Delta_{1}=\max\\{\frac{\overline{\alpha}^{2}\Delta_{0}}{\eta\overline{\alpha}-1},(k_{0}+1)\mathbb{E}\|x^{k_{0}}-x^{*}\|^{2}+\frac{\overline{\alpha}^{2}\Delta_{0}}{k_{0}+1}\\}.$

When $k=k_{0}$, by (39), we have

$\displaystyle\mathbb{E}\|x^{k_{0}+1}-x^{*}\|^{2}$ (41) $\displaystyle\leq$
$\displaystyle\big{(}1-\frac{\eta\overline{\alpha}}{k_{0}+1}\big{)}\mathbb{E}\|x^{k_{0}}-x^{*}\|^{2}+\frac{(\overline{\alpha})^{2}\Delta_{0}}{(k_{0}+1)^{2}}+\frac{\overline{\alpha}\Delta_{2}}{k_{0}+1}$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\|x^{k_{0}}-x^{*}\|^{2}+\frac{(\overline{\alpha})^{2}\Delta_{0}}{(k_{0}+1)^{2}}+\frac{\overline{\alpha}\Delta_{2}}{k_{0}+1}$
$\displaystyle\leq$
$\displaystyle\frac{\Delta_{1}}{k_{0}+1}+\overline{\alpha}\Delta_{2}.$

Now suppose that (40) is true when $k=k^{\prime}>k_{0}$, such that

$\displaystyle\mathbb{E}\|x^{k^{\prime}+1}-x^{*}\|^{2}\leq\frac{\Delta_{1}}{k^{\prime}+1}+\overline{\alpha}\Delta_{2}.$
(42)

When $k=k^{\prime}+1$, because $k^{\prime}+1>k_{0}$ according to (39) we have

$\displaystyle\mathbb{E}\|x^{k^{\prime}+2}-x^{*}\|^{2}\leq\big{(}1-\frac{\eta\overline{\alpha}}{k^{\prime}+2}\big{)}\mathbb{E}\|x^{k^{\prime}+1}-x^{*}\|^{2}+\frac{(\overline{\alpha})^{2}\Delta_{0}}{(k^{\prime}+2)^{2}}+\frac{\overline{\alpha}\Delta_{2}}{k^{\prime}+2}.$
(43)

Substituting (42) into (43), we have:

$\displaystyle\mathbb{E}\|x^{k^{\prime}+2}-x^{*}\|^{2}$ (44)
$\displaystyle\leq$
$\displaystyle\big{(}1-\frac{\eta\overline{\alpha}}{k^{\prime}+2}\big{)}\frac{\Delta_{1}}{k^{\prime}+1}+\frac{(\overline{\alpha})^{2}\Delta_{0}}{(k^{\prime}+2)^{2}}+\overline{\alpha}\Delta_{2}+(1-\eta\overline{\alpha})\frac{\overline{\alpha}\Delta_{2}}{k^{\prime}+2}$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\big{(}1-\frac{\eta\overline{\alpha}}{k^{\prime}+2}\big{)}\frac{\Delta_{1}}{k^{\prime}+1}+\frac{(\overline{\alpha})^{2}\Delta_{0}}{(k^{\prime}+2)^{2}}+\overline{\alpha}\Delta_{2}$
$\displaystyle\overset{(b)}{\leq}$
$\displaystyle\big{(}1-\frac{\eta\overline{\alpha}}{k^{\prime}+2}\big{)}\frac{\Delta_{1}}{k^{\prime}+1}+\frac{(\eta\overline{\alpha}-1)\Delta_{1}}{(k^{\prime}+2)^{2}}+\overline{\alpha}\Delta_{2}$
$\displaystyle\leq$
$\displaystyle\big{(}1-\frac{\eta\overline{\alpha}}{k^{\prime}+2}\big{)}\frac{\Delta_{1}}{k^{\prime}+1}+\frac{(\eta\overline{\alpha}-1)\Delta_{1}}{(k^{\prime}+1)(k^{\prime}+2)}+\overline{\alpha}\Delta_{2}$
$\displaystyle\leq$
$\displaystyle\frac{\Delta_{1}}{k^{\prime}+2}+\overline{\alpha}\Delta_{2}.$

where $(a)$ uses the fact that $\overline{\alpha}>\frac{1}{\eta}$, and $(b)$
follows from
$\Delta_{1}\geq\frac{\overline{\alpha}^{2}\Delta_{0}}{\eta\overline{\alpha}-1}$.
This completes the induction and the entire proof.

##  Appendix C Proof of Theorem 3

Proof. When $\lambda\geq\lambda_{0}$, combining Theorems 1 and 2, we directly
reach (12). When $0<\lambda<\lambda_{0}$, we have

$\displaystyle\mathbb{E}[\|x^{k+1}-[\tilde{x}^{*}]\|^{2}]\leq
2\mathbb{E}[\|x^{k+1}-x^{*}\|^{2}]+2\mathbb{E}[\|x^{*}-[\tilde{x}^{*}]\|^{2}].$
(45)

Because
$\mathbb{E}\|x^{k+1}-x^{*}\|^{2}\leq\frac{\Delta_{1}}{k+1}+\overline{\alpha}\Delta_{2}\
$ and $\ \mathbb{E}[\|x^{*}-[\tilde{x}^{*}]\|^{2}]\leq\Delta_{3}$, we reach
(13) and complete the proof.

##  Appendix D Proof of Theorem 4

Proof. The optimal solution $x^{*}:=[x_{i}^{*}]$ of (7) satisfies the
optimality condition that for any $i\in\mathcal{R}$,

$\displaystyle 0$
$\displaystyle=\nabla\mathbb{E}_{\xi_{i}}[F(x_{i}^{*},\xi_{i})]+\mathbb{E}_{\bar{\zeta}}\bigg{[}\lambda\sum_{j\in\mathcal{R}_{i}(\bar{\zeta}),i<j}\bar{s}_{ij}-\lambda\sum_{j\in\mathcal{R}_{i}(\bar{\zeta}),i>j}\bar{s}_{ji}\bigg{]}+\nabla
f_{0}(x^{*}_{i}),$ (46)
$\displaystyle=\nabla\mathbb{E}_{\xi_{i}}[F(x_{i}^{*},\xi_{i})]+\lambda\sum_{e=(i,j)\in\bar{\mathcal{E}}_{R},i<j}\bar{a}_{e}\bar{s}_{ij}-\lambda\sum_{e=(i,j)\in\bar{\mathcal{E}}_{R},i>j}\bar{a}_{e}\bar{s}_{ji}+\nabla
f_{0}(x^{*}_{i}),$ (47)

for some $\bar{s}_{ij}=sign(x^{*}_{i}-x^{*}_{j})\in[-1,1]^{p}$. Note that
$x^{*}$ is unique due to the strong convexity given by Assumption 3. We will
prove that $[\tilde{x}^{*}]$ satisfies (47), such that

$\displaystyle\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}}}[F(\tilde{x}^{*},\xi_{i})]+\lambda\sum_{e=(i,j)\in\bar{\mathcal{E}}_{R},i<j}{\color[rgb]{0,0,0}\bar{a}_{e}\bar{s}_{ij}}-\lambda\sum_{e=(i,j)\in\bar{\mathcal{E}}_{R},i>j}{\color[rgb]{0,0,0}\bar{a}_{e}\bar{s}_{ji}}+\nabla
f_{0}(\tilde{x}^{*})=0,\quad\forall i\in\mathcal{R}.$ (48)

Define $v_{i}:=\nabla\mathbb{E}[F(\tilde{x}^{*},\xi_{i})]+\nabla
f_{0}(\tilde{x}^{*})$. Since (48) can be decomposed element-wise, we start
from assuming the variable dimension $p=1$ such that both $\bar{s}_{ij}$ and
$v_{i}$ are scalars, and then extend to the high-dimensional case. By the
definition of $\bar{A}$, (48) can be rewritten as a system of linear equations

$\displaystyle\lambda\bar{A}{\color[rgb]{0,0,0}\bar{s}}+v=0,$ (49)

where ${\color[rgb]{0,0,0}\bar{s}}=[{\color[rgb]{0,0,0}\bar{s}_{ij}}]$
collects all the scalars ${\color[rgb]{0,0,0}\bar{s}_{ij}}$ in order,
$v=[v_{i}]$ collects all the scalars $v_{i}$ in order. Now the problem is
equivalent to finding a vector ${\color[rgb]{0,0,0}\bar{s}}$ whose elements
are within $[-1,1]$, namely, $\|{\color[rgb]{0,0,0}\bar{s}}\|_{\infty}\leq 1$,
to satisfy (49). The rest of the proof is the same as that of Theorem 1, only
replacing $A$ by $\bar{A}$.

##  Appendix E Proof of Theorem 5

Proof. In the proof, we focus on the sequence $\\{\zeta^{k}\\}$ satisfying
$\lim_{K\rightarrow\infty}\frac{1}{K+1}\sum_{k=0}^{K}\zeta_{e}^{k}=\bar{a}_{e}$
for all $e$, which happens with probability $1$ according to Assumption 2.
Same as the proof of Theorem 2, we use the simplified notation
$\mathbb{E}_{k}$ to take the conditional expectation given $\\{x_{i}^{l}:l\leq
k,i\in\mathcal{R}\\}$, and impose no restrictions on the attacks.

Step 1. From the update (9) at every regular agent $i$, we have

$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|x_{i}^{k+1}-x_{i}^{*}\|^{2}$
(50) $\displaystyle=$
$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|x_{i}^{k}-x_{i}^{*}-\alpha^{k}\big{(}\nabla
F(x_{i}^{k},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\lambda\sum_{j\in\mathcal{B}_{i}^{k}}sign(x_{i}^{k}-z_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\big{)}\|^{2}$ $\displaystyle=$
$\displaystyle\|x_{i}^{k}-x_{i}^{*}\|^{2}+(\alpha^{k})^{2}{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|\nabla
F(x_{i}^{k},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\lambda\sum_{j\in\mathcal{B}_{i}^{k}}sign(x_{i}^{k}-z_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}$
$\displaystyle-2\alpha^{k}{\color[rgb]{0,0,0}\mathbb{E}_{k}}\langle\nabla
F(x_{i}^{k},\xi_{i}^{k})\
+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k}),x_{i}^{k}-x_{i}^{*}\rangle-2\alpha^{k}\langle\lambda\sum_{j\in\mathcal{B}_{i}^{k}}sign(x_{i}^{k}-z_{j}^{k}),x_{i}^{k}-x_{i}^{*}\rangle.$

Below, we handle the terms at the right-hand side of (50) one by one.

For the second term at the right-hand side of (50), we have

$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|\nabla
F(x_{i}^{k},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\lambda\sum_{j\in\mathcal{B}_{i}^{k}}sign(x_{i}^{k}-z_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}$ (51) $\displaystyle=$
$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\lambda\sum_{j\in\mathcal{B}_{i}^{k}}sign(x_{i}^{k}-z_{j}^{k})+\nabla
f_{0}(x_{i}^{k})+\nabla
F(x_{i}^{k},\xi_{i}^{k})-\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})]\|^{2}$
$\displaystyle\leq$ $\displaystyle
4\|\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}+4\lambda^{2}\|\sum_{j\in\mathcal{B}_{i}^{k}}sign(x_{i}^{k}-z_{j}^{k})\|^{2}+2{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}\|F(x_{i}^{k},\xi_{i}^{k})-\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})]\|^{2}$
$\displaystyle\leq$ $\displaystyle
4\|\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}+4\lambda^{2}|\mathcal{B}_{i}^{k}|^{2}p+2\delta_{i}^{2}$
$\displaystyle\leq$ $\displaystyle
4\|\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}+4\lambda^{2}|\mathcal{B}_{i}|^{2}p+2\delta_{i}^{2},$

where the second equality holds true because that each element of the
$p$-dimensional vector $sign(x_{i}^{k}-z_{j}^{k})$ is within $[-1,1]$, and
that the variance is bounded by
$\mathbb{E}\|F(x_{i}^{k},\xi_{i}^{k})-\nabla\mathbb{E}[F(x_{i}^{k},\xi_{i}^{k})]\|^{2}\leq\delta_{i}^{2}$
stated in Assumption 5.

Let $\bar{s}_{ij}=-\bar{s}_{ji}$ for $i>j$. Then the optimality condition (46)
becomes $0=\nabla\mathbb{E}_{\xi_{i}}[F(x_{i}^{*},\xi_{i})]+\lambda\
\mathbb{E}_{\bar{\zeta}}[\sum_{j\in\mathcal{R}_{i}(\bar{\zeta})}\bar{s}_{ij}]+\nabla
f_{0}(x_{i}^{*})$. Plugging it into the first term at the right-hand side of
(51) and replacing $\xi_{i}$ by $\xi_{i}^{k}$, we have

$\displaystyle
4\|\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}F(x_{i}^{k},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}$ (52) $\displaystyle=$ $\displaystyle
4\|\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{k},\xi_{i}^{k})]+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k})-\nabla{\color[rgb]{0,0,0}\mathbb{E}_{\xi_{i}^{k}}}[F(x_{i}^{*},\xi_{i}^{k})]-\lambda{\color[rgb]{0,0,0}\mathbb{E}_{\bar{\zeta}}}[\sum_{j\in\mathcal{R}_{i}({\color[rgb]{0,0,0}\bar{\zeta}})}{\color[rgb]{0,0,0}\bar{s}_{ij}}]-\nabla
f_{0}(x_{i}^{*})\|^{2}$ $\displaystyle\leq$
$\displaystyle{\color[rgb]{0,0,0}8\|\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{k})-\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{*},\xi_{i}^{k})]-\nabla
f_{0}(x_{i}^{*})\|^{2}+8\lambda^{2}\|\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})-\mathbb{E}_{\bar{\zeta}}[\sum_{j\in\mathcal{R}_{i}(\bar{\zeta})}\bar{s}_{ij}]\|^{2}}$
$\displaystyle\leq$
$\displaystyle{\color[rgb]{0,0,0}8\|\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{k})-\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{*},\xi_{i}^{k})]-\nabla
f_{0}(x_{i}^{*})\|^{2}+32\lambda^{2}|\mathcal{R}_{i}|^{2}p.}$

Here the first inequality is due to $(a+b)^{2}\leq 2a^{2}+2b^{2}$. To obtain
the last inequality, we observe that
$sign(x_{i}^{k}-x_{j}^{k}),\bar{s}_{ij}\in[-1,1]^{p}$. Combining (51) and
(52), we have

$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\|\nabla
F(x_{i}^{k},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\lambda\sum_{j\in\mathcal{B}_{i}^{k}}sign(x_{i}^{k}-z_{j}^{k})+\nabla
f_{0}(x_{i}^{k})\|^{2}$ (53) $\displaystyle\leq$
$\displaystyle{\color[rgb]{0,0,0}8\|\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{k})-\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{*},\xi_{i}^{k})]-\nabla
f_{0}(x_{i}^{*})\|^{2}+32\lambda^{2}|\mathcal{R}_{i}|^{2}p+4\lambda^{2}|\mathcal{B}_{i}|^{2}p+2\delta_{i}^{2}.}$

For the third term at the right-hand side of (50), similar to the proof from
(26) to (30), we reach

$\displaystyle-2{\color[rgb]{0,0,0}\mathbb{E}_{k}}\langle\nabla
F(x_{i}^{k},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k}),x_{i}^{k}-x_{i}^{*}\rangle$ (54) $\displaystyle\leq$
$\displaystyle-2\bigg{\langle}\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})-\lambda{\color[rgb]{0,0,0}\mathbb{E}_{\bar{\zeta}}}\big{[}\sum_{j\in\mathcal{R}_{i}({\color[rgb]{0,0,0}\bar{\zeta}})}{\color[rgb]{0,0,0}\bar{s}_{ij}}\big{]},x_{i}^{k}-x_{i}^{*}\bigg{\rangle}-\frac{2u_{i}L_{i}}{u_{i}+L_{i}}\|x_{i}^{k}-x_{i}^{*}\|^{2}$
$\displaystyle-\frac{2}{u_{i}+L_{i}}\
{\color[rgb]{0,0,0}\|\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{k})-\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{*},\xi_{i}^{k})]-\nabla
f_{0}(x_{i}^{*})\|^{2}}.$

Notice it holds for any $\epsilon>0$ that

$\displaystyle-2\bigg{\langle}\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})-\lambda\mathbb{E}_{\bar{\zeta}}\big{[}\sum_{j\in\mathcal{R}_{i}(\bar{\zeta})}\bar{s}_{ij}\big{]},x_{i}^{k}-x_{i}^{*}\bigg{\rangle}$
(55) $\displaystyle\leq$
$\displaystyle\frac{\epsilon}{2}\|x_{i}^{k}-x_{i}^{*}\|^{2}+\frac{2\lambda^{2}}{\epsilon}\|\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{*}-x_{j}^{*})-\mathbb{E}_{\bar{\zeta}}\big{[}\sum_{j\in\mathcal{R}_{i}(\bar{\zeta})}\bar{s}_{ij}\big{]}\|^{2}$
$\displaystyle\leq$
$\displaystyle\frac{\epsilon}{2}\|x_{i}^{k}-x_{i}^{*}\|^{2}+\frac{8\lambda^{2}|\mathcal{R}_{i}|^{2}p}{\epsilon},$

where the last inequality comes from that the candidate non-zero entries of
$sign(x_{i}^{k}-x_{j}^{k})$ and $\bar{s}_{ij}$ are bounded by $1$. Note that
due to the use of these loose upper bounds, the second term at the right-hand
side of (55) is proportional to $|\mathcal{R}_{i}|^{2}$. As a consequence, the
eventually derived size of convergence neighborhood is also monotonically
increasing when $|\mathcal{R}_{i}|^{2}$ increases. Combining (54) and (55)
yields

$\displaystyle{\color[rgb]{0,0,0}\mathbb{E}_{k}}\langle\nabla
F(x_{i}^{k},\xi_{i}^{k})+\lambda\sum_{j\in\mathcal{R}_{i}^{k}}sign(x_{i}^{k}-x_{j}^{k})+\nabla
f_{0}(x_{i}^{k}),x_{i}^{k}-x_{i}^{*}\rangle$ (56) $\displaystyle\leq$
$\displaystyle\frac{\epsilon}{2}\|x_{i}^{k}-x_{i}^{*}\|^{2}+\frac{8\lambda^{2}|\mathcal{R}_{i}|^{2}p}{\epsilon}-\frac{2u_{i}L_{i}}{u_{i}+L_{i}}\|x_{i}^{k}-x_{i}^{*}\|^{2}$
$\displaystyle-\frac{2}{u_{i}+L_{i}}{\color[rgb]{0,0,0}\|\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{k})-\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{*},\xi_{i}^{k})]-\nabla
f_{0}(x_{i}^{*})\|^{2}}.$

For the last term at the right-hand side of (50), it holds for any
$\epsilon>0$ that

$\displaystyle-2\langle\lambda\sum_{j\in\mathcal{B}_{i}^{k}}sign(x_{i}^{k}-z_{j}^{k}),x_{i}^{k}-x_{i}^{*}\rangle$
(57) $\displaystyle\leq$
$\displaystyle\frac{\epsilon}{2}\|x_{i}^{k}-x_{i}^{*}\|^{2}+\frac{2\lambda^{2}}{\epsilon}\|\sum_{j\in\mathcal{B}_{i}^{k}}sign(x_{i}^{k}-z_{j}^{k})\|^{2}$
$\displaystyle\leq$
$\displaystyle\frac{\epsilon}{2}\|x_{i}^{k}-x_{i}^{*}\|^{2}+\frac{2\lambda^{2}|\mathcal{B}_{i}|^{2}p}{\epsilon}.$

Substituting (53), (56) and (57) into (50), we have:

$\displaystyle\mathbb{E}_{k}\|x_{i}^{k+1}-x_{i}^{*}\|^{2}$ (58)
$\displaystyle\leq$
$\displaystyle\big{(}1-\alpha^{k}(\frac{2u_{i}L_{i}}{u_{i}+L_{i}}-\epsilon)\big{)}\|x_{i}^{k}-x_{i}^{*}\|^{2}+(\alpha^{k})^{2}(32\lambda^{2}|\mathcal{R}_{i}|^{2}p+4\lambda^{2}|\mathcal{B}_{i}|^{2}p+2\delta_{i}^{2})+\alpha^{k}(\frac{2\lambda^{2}|\mathcal{B}_{i}|^{2}p}{\epsilon}+\frac{8\lambda^{2}|\mathcal{R}_{i}|^{2}p}{\epsilon})$
$\displaystyle-2\alpha^{k}(\frac{1}{u_{i}+L_{i}}-4\alpha^{k})\|\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{k},\xi_{i}^{k})]+\nabla
f_{0}(x_{i}^{k})-\nabla\mathbb{E}_{\xi_{i}^{k}}[F(x_{i}^{*},\xi_{i}^{k})]-\nabla
f_{0}(x_{i}^{*})\|^{2}.$

Due to the step size rule, we have $\frac{1}{u_{i}+L_{i}}-4\alpha^{k}\geq 0$.
Therefore, we drop the last term at the right-hand side of (58). Also noticing
the definition of $\eta$, we rewrite (58) into

$\displaystyle\mathbb{E}_{k}\|x_{i}^{k+1}-x_{i}^{*}\|^{2}$ (59)
$\displaystyle\leq$
$\displaystyle\big{(}1-\eta\alpha^{k}\big{)}\|x_{i}^{k}-x_{i}^{*}\|^{2}+(\alpha^{k})^{2}(32\lambda^{2}|\mathcal{R}_{i}|^{2}p+4\lambda^{2}|\mathcal{B}_{i}|^{2}p+2\delta_{i}^{2})+\alpha^{k}(\frac{2\lambda^{2}|\mathcal{B}_{i}|^{2}p}{\epsilon}+\frac{8\lambda^{2}|\mathcal{R}_{i}|^{2}p}{\epsilon}).$

Step 2. With (59), the rest of the proof follows Step 3 of Theorem 2 by taking
expectation over $\\{x_{i}^{l}:l\leq k,i\in\mathcal{R}\\}$.

##  Appendix F Proof of Theorem 6

Proof. When $\lambda\geq\lambda_{0}$, combining Theorems 4 and 5, we directly
reach (16). When $0<\lambda<\lambda_{0}$, we have

$\displaystyle\mathbb{E}[\|x^{k+1}-[\tilde{x}^{*}]\|^{2}]\leq
2\mathbb{E}[\|x^{k+1}-x^{*}\|^{2}]+2\mathbb{E}[\|x^{*}-[\tilde{x}^{*}]\|^{2}].$
(60)

Because
$\mathbb{E}\|x^{k+1}-x^{*}\|^{2}\leq\frac{\Delta_{6}}{k+1}+\overline{\alpha}\Delta_{5}\
$ and $\ \mathbb{E}[\|x^{*}-[\tilde{x}^{*}]\|^{2}]\leq\Delta_{7}$, we reach
(17) and complete the proof.

## References

  * [1]
  * [2] Anastasia Koloskova, Sebastian U. Stich, and Martin Jaggi, “Decentralized stochastic optimization and gossip algorithms with compressed communication,” In: Proceedings of ICML, 2019.
  * [3] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu, “Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent,” In: Proceedings of NeurIPS, 2017.
  * [4] Srinivasan S. Ram, Angelia Nedic, and Venugopal V. Veeravalli,“Distributed stochastic subgradient projection algorithms for convex optimization,” Journal of Optimization Theory and Application, vol. 147, no. 3, pp. 516–545, 2010.
  * [5] John Duchi, Alekh Agarwal, and Martin Wainwright, “Dual averaging for distributed optimization: Convergence analysis and network scaling,” IEEE Transactions on Automatic Control, vol. 57, no. 3, pp. 592–606, 2012.
  * [6] Michael Rabbat, “Multi-agent mirror descent for decentralized stochastic optimization,” In: Proceedings of CAMSAP, 2015.
  * [7] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu, “Asynchronous decentralized parallel stochastic gradient descent,” In: Proceedings of ICML, 2018.
  * [8] Hadrien Hendrikx, Francis Bach, and Laurent Massoulie, “Asynchronous accelerated proximal stochastic gradient for strongly convex distributed finite sums,” arXiv preprint arXiv:1901.09865, 2019.
  * [9] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu, “D2: Decentralized training over decentralized data,” In: Proceedings of ICML, 2018.
  * [10] Kun Yuan, Bicheng Ying, Jiageng Liu, and Ali H. Sayed, “Variance-reduced stochastic learning by networked agents under random reshuffling,” IEEE Transactions on Signal Processing, vol. 67, no. 2, pp. 351–366, 2018.
  * [11] Aryan Mokhtari and Alejandro Ribeiro, “DSA: Decentralized double stochastic averaging gradient algorithm,” Journal of Machine Learning Research, vol. 17, no. 1, pp. 2165–2199, 2016.
  * [12] Shicong Cen, Huishuai Zhang, Yuejie Chi, Wei Chen, and Tie-Yan Liu, “Convergence of distributed stochastic variance reduced methods without sampling extra data,” arXiv preprint arXiv:1905.12648, 2019.
  * [13] Ran Xin, Soummya Kar, and Usman A. Khan, “Gradient tracking and variance reduction for decentralized optimization and machine learning,” arXiv preprint arXiv:2002.05373, 2020.
  * [14] Qinyi Luo, Jinkun Lin, Youwei Zhuo, and Xuehai Qian, “Hop: Heterogeneity-aware decentralized training,” In: Proceedings of ASPLOS, 2019
  * [15] Leslie Lamport, Robert E. Shostak, and Marshall C. Pease, “The Byzantine generals problem,” ACM Transactions on Programming Languages and Systems, vol. 4, no. 3, pp. 382–401, 1982.
  * [16] Zhixiong Yang and Waheed U. Bajwa, “ByRdiE: Byzantine-resilient distributed coordinate descent for decentralized learning,” IEEE Transactions on Signal and Information Processing over Networks, vol. 5, no. 4, pp. 611–627, 2019.
  * [17] Zhixiong Yang and Waheed U. Bajwa, “BRIDGE: Byzantine-resilient decentralized gradient descent,” arXiv preprint arXiv:1908.08098, 2019.
  * [18] Zhixiong Yang, Arpita Gang, and Waheed U. Bajwa, “Adversary-resilient dstributed and decentralized statistical inference and machine learning: An overview of recent advances under the Byzantine threat model,” IEEE Signal Processing Magazine, vol. 37, no. 3, pp. 146–159, 2020.
  * [19] Yudong Chen, Lili Su, and Jiaming Xu, “Distributed statistical machine learning in adversarial settings: Byzantine gradient descent,” In: Proceedings of SIGMETRICS, 2019.
  * [20] Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta, “Generalized Byzantine-tolerant SGD,” arXiv preprint arXiv:1802.10116, 2018.
  * [21] Deming Yuan and Daniel WC Ho, “Randomized gradient-free method for multiagent optimization over time-varying networks,” IEEE Transactions on Neural Networks and Learning Systems, vol. 26, no. 6, pp. 1342–1347, 2014.
  * [22] Angelia Nedic, Alex Olshevsky, and Wei Shi, “Achieving geometric convergence for distributed optimization over time-varying graphs,” SIAM Journal on Optimization, vol. 27, no. 4, pp. 2597–2633, 2017\.
  * [23] Angelia Nedic and Alex Olshevsky, “Stochastic gradient-push for strongly convex functions on time-varying directed graphs,” IEEE Transactions on Automatic Control, vol. 61, no. 12, pp. 3936–3947, 2016.
  * [24] Angelia Nedic and Alex Olshevsky, “Distributed optimization over time-varying directed graphs,” IEEE Transactions on Automatic Control, vol. 60, no. 3, pp. 601–615, 2014.
  * [25] Gesualdo Scutari and Ying Sun, “Distributed nonconvex constrained optimization over time-varying digraphs,” Mathematical Programming, vol. 176, no. 1–2, pp. 497–544, 2019\.
  * [26] Mingyi Hong and Tsung-Hui Chang, “Stochastic proximal gradient consensus over random networks,” IEEE Transactions on Signal Processing, vol. 65, no. 11, pp. 2933–2948, 2017.
  * [27] Yuan Chen, Soummya Kar, and José MF Moura, “Resilient distributed parameter estimation with heterogeneous data,” IEEE Transactions on Signal Processing, vol. 67, no. 19, pp. 4918–4933, 2019\.
  * [28] Yuan Chen, Soummya Kar, and José MF Moura, “Resilient distributed field estimation,” SIAM Journal on Control and Optimization, vol .58, no. 3, pp. 1429–1456, 2020\.
  * [29] Walid Ben-Ameur, Pascal Bianchi, and Jeremie Jakubowicz, “Robust distributed consensus using total variation,” IEEE Transactions on Automatic Control, vol. 61, no. 6, pp. 1550–1564, 2016.
  * [30] Wei Xu, Zhengqing Li, and Qing Ling, “Robust decentralized dynamic optimization at presence of malfunctioning agents,” Signal Processing, vol. 153, pp. 24–33, 2018.
  * [31] 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 AAAI, 2019.
  * [32] Jie Peng and Qing Ling, “Byzantine-robust decentralized stochastic optimization over static and time-varying networks,” arXiv preprint arXiv:2005.06276, 2020.
  * [33] Vincent D. Blondel, Julien M. Hendrickx, Alex Olshevsky, and John N. Tsitsiklis, “Convergence in multiagent coordination, consensus, and flocking,” In: Proceedings of CDC, 2006.
  * [34] Yurii Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2004.
  * [35] Zhaoxian Wu, Qing Ling, Tianyi Chen, and Georgios B. Giannakis, “Federated variance-reduced stochastic gradient descent with robustness to Byzantine attacks,” arXiv preprint arXiv:1912.12716, 2019.
  * [36] Jie Peng and Qing Ling, “Byzantine-robust decentralized stochastic optimization,” In: Proceedings of ICASSP, 2020.