ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning

I Introduction

One of the fundamental goals in machine learning is to learn a model that minimizes the statistical risk. This is typically accomplished through stochastic optimization techniques, with the underlying principle referred to as empirical risk minimization (ERM) . The ERM principle involves the use of a training dataset and tools from optimization theory. Traditionally, training data have been assumed available at a centralized location. Many recent applications of machine learning, however, involve the use of a dataset that is either distributed across different locations (e.g., the Internet of Things) or that cannot be processed at a single machine due to its size (e.g., social network data). The ERM framework in this setting of distributed training data is often referred to as decentralized or distributed learning .

While there exist excellent works that solve the problem of distributed learning, all these works make a simplified assumption that all nodes in the network function as expected. Unfortunately, this assumption does not always hold true in practice; examples include cyber attacks, malfunctioning equipments and undetected failures . When a node arbitrarily deviates from its intended behavior, it is termed to have undergone Byzantine failure . While Byzantine failures are hard to detect in general, they can easily jeopardize the operation of the whole network .

In particular, with just a simple strategy, one can show that a single Byzantine node in the network can lead to failures of most state-of-the-art distributed learning algorithms . The main contribution of this paper is to introduce and analyze an algorithm that completes the distributed learning task in the presence of Byzantine failures in the network.

To achieve the goal of distributed learning, one usually sets up a distributed optimization problem by defining and minimizing a (regularized) loss function on the training data of each node. The resulting problem can then be solved by distributed optimization algorithms. Several types of distributed algorithms have been introduced in the past . The most common of these are gradient-based methods , which usually have low local computational complexity. Another type includes augmented Lagrangian-based methods , which iteratively update the primal and dual variables. These methods often require the ability to locally solve an optimization subproblem at each node. A third type includes second-order distributed methods , which tend to have high computational and/or communications costs. While any of these distributed optimization algorithms can be used for distributed learning, they all make the assumption that there are no failures in the network.

Byzantine-resilient algorithms for a variety of problems have been studied extensively over the years . Byzantine-resilient algorithms for scalar- and vector-averaging distributed consensus were studied in . The algorithms proposed in extend some of these works from scalar consensus to scalar-valued distributed optimization, but they cannot be used in a straightforward manner for vector-valued distributed optimization problems. In the context of distributed learning, introduces a method to implement distributed support vector machines (SVMs) under Byzantine failures, but it neither provides theoretical guarantees nor generalizes to other learning problems. A number of recent works have also investigated Byzantine-resilient distributed learning in networks that are equipped with a central processor (often referred to as a paramater server) . Theoretical guarantees developed in such works make extensive use of the fact that the parameter server is connected to all network nodes; as such, these guarantees cannot be generalized to Byzantine-resilient learning in fully distributed networks.

I-B Our Contributions

We have already noted several limitations of works like within the context of Byzantine-resilient learning in fully distributed settings. Additionally, one of the limitations of existing Byzantine-resilient algorithms such as is that, when required to work with vector-valued data, they make a strong assumption on the network topology. Specifically, the smallest size of neighborhood of each node in the vector setting depends linearly on the dimensionality of the problem. This is impractical for most learning problems since the dimensionality of the training samples is usually much larger than the size of the neighborhood of each node. Within the specific context of Byzantine-resilient distributed machine learning, the main limitation of fully distributed algorithms proposed in is that they only yield the minimizer of a convex combination of local empirical risk functions for scalar-valued problems. Since this (scalar) minimizer is usually different from the minimizer of the exact average of local loss functions, these works cannot guarantee by themselves alone that the outputs of any vector-valued algorithms that leverage similar ideas will converge to either the minimum empirical risk or the minimum statistical risk.

In contrast to prior works, our work has two main contributions. First, we propose a Byzantine-resilient algorithm that scales well with the dimensionality of distributed learning problems. The proposed algorithm is an inexact distributed variant of coordinate descent that first breaks vector-valued distributed learning problems into a (possibly infinite) sequence of scalar-valued distributed subproblems and then solves these subproblems in a Byzantine-resilient manner by leveraging ideas from works such as . The inexactness here stems from the fact that—even when using an exact line search procedure—the subproblems cannot be solved exactly in the presence of Byzantine failures (cf. Sec. III). This inexactness in the solution of each subproblem, whether or not an exact line search procedure is used, is one of the reasons the analytical techniques of prior works such as do not lead to theoretical guarantees for the proposed coordinate descent algorithm. In contrast, under the assumption of independent and identically distributed training samples across the network, we provide theoretical guarantees that the output of the proposed algorithm will lead to the minimum statistical risk with high probability. Our theoretical analysis, which forms the second main contribution of this work, also highlights the fact that the output of our algorithm can statistically converge to the minimizer of the statistical risk faster than using only local information by a factor that will be shown in the sequel.

I-C Notation and Organization

The rest of this paper is organized as follows. Section II gives the problem formulation. Section III discusses the proposed algorithm along with theoretical guarantees for consensus as well as statistical and algorithmic convergence. Numerical results corresponding to distributed convex and nonconvex learning on two different datasets are provided in Section IV, while Section V concludes the paper.

II Problem Formulation

Given a connected network in which nodes have access to local training data, our goal is to learn a machine learning model from the distributed data, even in the presence of Byzantine failures. We begin with a model of our basic problem, which will be followed with a model for Byzantine failures and the final problem statement.

Note that while the main problem is being formulated here under the supervised setting, our proposed framework and the final results are equally applicable under both unsupervised and semi-supervised settings.

Note that Assumption 1 implies the risk function itself is also Lipschitz continuous :

Centralized machine learning focuses on learning the “best” mapping from $x$ to $y$ in terms of the following stochastic optimization problem (referred to as statistical risk minimization):

While the set $W$ has no algorithmic significance, it is later shown that the iterates of the proposed algorithm stay within it. Because of this reason, $W$ makes an appearance in our theoretical guarantees concerning statistical convergence.

In particular, the minimizer of the empirical risk $\widehat{f}(w,S)$ can be shown to converge to $w^{\ast}$ with high probability . In the case of i.i.d. training samples, and for a fixed probability of failure and ignoring some $\log$ terms, the rate of this statistical convergence is known to be $\mathcal{O}\left(1/\sqrt{|S|}\right)\equiv\mathcal{O}\left(1/\sqrt{MN}\right)$ under mild assumptions on the problem .

In many distributed learning problems, training data cannot be made available at a single location. This then requires learning $w^{\ast}$ in a distributed fashion, which can be done by employing distributed optimization techniques. The main idea of distributed optimization-based learning is to minimize the average of local empirical risks, i.e.,

To achieve this goal, we need nodes to cooperate with each other by communicating over network edges. Specifically, define the neighborhood of node $i$ as $\mathcal{N}_{i}:=\{j\in J:(j,i)\in\mathcal{E}\}$. We say that node $j$ is a neighbor of node $i$ if $j\in\mathcal{N}_{i}$. Distributed learning algorithms proceed iteratively. In each iteration $(r+1)$ of the algorithm, node $j$ is expected to accomplish two tasks:

Update a local variable $w_{j}^{r}$ according to some (deterministic or stochastic) rule $g_{j}(\cdot)$, and

Broadcast the updated local variable to other nodes, where node $i$ can receive the broadcasted information from node $j$ only if $j\in\mathcal{N}_{i}$.

While distributed learning via message passing is well understood , existing protocols require all nodes to operate as intended. In contrast, the main assumption in this paper is that some of the nodes in the network can undergo Byzantine failures, formally defined as follows.

A node $j\in J$ is said to be Byzantine if during any iteration, it either updates its local variable using an update function $g_{j}^{\prime}(\cdot)\neq g_{j}(\cdot)$ or it broadcasts some value other than the intended update to its neighbors.

In this paper, we assume there are $b$ Byzantine nodes in the network. Knowing the exact value of $b$, however, is not necessary. One can, for example, set $b$ to be an upper bound on the number of Byzantine nodes. Let $J^{\prime}\subset J$ denote the set of nonfaulty nodes. Without loss of generality, we assume the nonfaulty nodes are labeled from 1 to $|J^{\prime}|$. We now provide some definitions and an assumption that are common in the literature; see, e.g., .

A subgraph $\mathcal{G}_{r}$ of $\mathcal{G}$ is called a reduced graph if it is generated by ($i$) removing all Byzantine nodes along with their incoming and outgoing edges, and ($ii$) removing additionally up to $b$ incoming edges from each nonfaulty node.

A “source component” of a graph is a collection of nodes such that each node in the source component has a directed path to every other node in the graph.

All reduced graphs $\mathcal{G}_{r}$ generated from $\mathcal{G}(J,\mathcal{E})$ contain a source component of cardinality at least $(b+1)$.

The purpose of Assumption 3 is to ensure there is enough redundancy in the graph to tolerate Byzantine failures. Note that the total number of different reduced graphs one can generate from $\mathcal{G}$ is finite as long as $M$ is finite. So, in theory, Assumption 3 can be certified for any graph. But efficient certification of this assumption remains an open problem. In the case of Erdős–Rényi graphs used in our experiments, however, we have observed that Assumption 3 is typically satisfied whenever the ratio of the average incoming degree of the graph and the number of Byzantine nodes is high enough.

Assumption 3 has been stated to guarantee resilience against the worst-case attack scenario in which all Byzantine nodes concentrate in the neighborhood of any one of the network nodes. While such worst-case analysis is customary in the literature on Byzantine fault tolerance , it does impose stringent constraints on the network topology. Such topology constraints, however, seem to be unavoidable for the types of “local screening” algorithms being considered in the fully distributed setting of this paper.

II-B Problem Statement

Our goal is to develop a Byzantine fault-tolerant algorithm for distributed learning under Assumptions 1–3. Specifically, under the assumption of at most $b$ Byzantine nodes in the network, we need to accomplish the following:

Achieve consensus among nonfaulty nodes in the network, i.e., $w_{j}^{r}=w_{i}^{r}$ $\forall i,j\in J^{\prime}$ as the number of algorithmic iterations $r\rightarrow\infty$; and

Guarantee $w_{j}^{r}\rightarrow w^{\ast}$ $\forall j\in J^{\prime}$ as the number of training samples at nonfaulty nodes $N\rightarrow\infty$.

In particular, the latter objective requires understanding both the statistical convergence and the algorithmic convergence of the distributed empirical risk minimization problem in the presence of Byzantine failures.

III Byzantine-resilient Distributed Coordinate Descent for Decentralized Learning

In distributed learning, one would ideally like to solve the empirical risk minimization (ERM) problem

at each node $j\in J^{\prime}$ and show that $w_{opt}\rightarrow w^{\ast}$ as $N\rightarrow\infty$. However, we know from prior work that this is infeasible when $b\geq 1$. Nonetheless, we establish in the following that distributed strategies based on coordinate descent algorithms can still be used to solve a variant of (4) at nonfaulty nodes and guarantee that the solutions converge to the minimizer $w^{\ast}$ of the statistical risk for the case of i.i.d. training data. We refer to our general approach as Byzantine-Resilient Distributed coordinate dEscent (ByRDiE), which is based on key insights gleaned from two separate lines of prior work. First, it is known that certain types of scalar-valued distributed optimization problems can be inexactly solved in the presence of Byzantine failures . Second, coordinate descent algorithms break down vector-valued optimization problems into a sequence of scalar-valued problems . The algorithmic aspects of ByRDiE leverage these insights, while the theoretical aspects leverage tools from Byzantine-resilient distributed consensus , optimization theory , stochastic convex optimization , and statistical learning theory .

ByRDiE involves splitting the ERM problem (4) into $P$ one-dimensional subproblems using coordinate descent and then solving each scalar-valued subproblem using the Byzantine-resilient approach described in . The exact implementation is detailed in Algorithm 1. The algorithm can be broken into an outer loop (Step 3) and an inner loop (Step 5). The outer loop is the coordinate descent loop, which breaks the vector-valued optimization problem in each iteration $r$ into $P$ scalar-valued subproblems. The inner loop solves a scalar-valued optimization problem in each iteration $t$ and ensures resilience to Byzantine failures. We assume the total number of iterations $\bar{r}$ for coordinate descent are specified during initialization. We use $[w_{j}^{r}(t)]_{k}$ to denote the $k$-th element of $w_{j}$ at the $r$-th iteration of the coordinate descent loop and the $t$-th iteration of the $k$-th subproblem (coordinate). Without loss of generality, we initialize $[w_{j}^{1}(1)]_{k}=0,\forall k=1,\dots,P$.

We now fix some $r$ and $k$, and focus on the implementation of the inner loop (Step 5). Every node has some $[w_{j}^{r}(1)]_{k}$ at the start of the inner loop ($t=1$). During each iteration $t$ of this loop, all (nonfaulty) nodes engage in the following: broadcast, screening, and update. In the broadcast step (Step 7), all nodes $i\in J$ broadcast $[w_{i}^{r}(t)]_{k}$’s and each node $j\in J$ receives $[w_{i}^{r}(t)]_{k},\forall i\in\mathcal{N}_{j}$. During this step, a node can receive values from both nonfaulty and Byzantine neighbors. The main idea of the screening step (Step 8) is to reject values at node $j$ that are either “too large” or “too small” so that the values being used for update by node $j$ in each iteration will be upper and lower bounded by a set of values generated by nonfaulty nodes. To this end, we partition $\mathcal{N}_{j}$ into 3 subsets $\mathcal{N}_{j}^{\ast}(r,k,t)$, $\mathcal{N}_{j}^{s}(r,k,t)$ and $\mathcal{N}_{j}^{l}(r,k,t)$, which are defined as following:

The step is called screening because node $j$ only uses $[w_{i}^{r}(t)]_{k}$’s from $\mathcal{N}^{\ast}_{j}(r,k,t)$ to update its local variable. Note that there might still be $[w_{i}^{r}(t)]_{k}$’s received from Byzantine nodes in $\mathcal{N}^{\ast}_{j}(r,k,t)$. We will see later, however, that this does not effect the workings of the overall algorithm.

The final step of the inner loop in ByRDiE is the update step (Step 9). Using $[\nabla\widehat{f}(w_{j}^{r}(t),S_{j})]_{k}$ to denote the $k$-th element of $\nabla\widehat{f}(w_{j}^{r}(t),S_{j})$, we can write this update step as follows:

where $\{\rho(\tau)\}_{\tau=1}^{\infty}$ are square-summable (but not summable), diminishing stepsizes: $0<\rho(\tau+1)\leq\rho(\tau)$, $\sum_{\tau}\rho(\tau)=\infty$, and $\sum_{\tau}\rho^{2}(\tau)<\infty$. Notice that $[w^{r}_{j}(T+1)]_{k}$ is updated after the $k$-th subproblem of coordinate descent in iteration $r$ finishes and it stays fixed until the start of the $k$-th subproblem in the $(r+1)$-th iteration of coordinate descent. An iteration $r$ of the coordinate descent loop is considered complete once all $P$ subproblems within the loop are solved. The local variable at each node $j$ at the end of this iteration is then denoted by $w^{r,T}_{j}$ (Step 13). We also express the output of the whole algorithm as $\{w^{\bar{r},T}_{j}\}_{j\in J^{\prime}}$. Finally, note that while Algorithm 1 cycles through the $P$ coordinates of the optimization variables in each iteration $r$ in the natural order, one can use any permutation of $\{1,\dots,P\}$ in place of this order.

We conclude this discussion by noting that the parameter $T$ in ByRDiE, which can take any value between $1$ and $\infty$, trades off consensus among the nonfaulty nodes and the convergence rate; see Sec. III-E for further discussion on this tradeoff and Sec. IV for numerical experiments that highlight this tradeoff. Our theoretical analysis of ByRDiE focuses on the two extreme cases of $T\to\infty$ and $T=1$. In both cases, we establish in the following that the output of ByRDiE at nonfaulty nodes converges in probability to the minimum of the statistical risk. Convergence guarantees for a finite-valued $T>1$ can be obtained from straightforward modifications of the analytical techniques used in the following.

III-B Theoretical Guarantees: Consensus

We now turn our attention to theoretical guarantees for ByRDiE. We first show that it leads to consensus among nonfaulty nodes in the network, i.e., all nonfaulty nodes agree on the same variable, in the limit of large $\bar{r}$ and/or $T$. Then we show in the next sections that the output of ByRDiE converges to the statistical optimum in the limit of large $\bar{r}$ for the two extreme choices of $T$: $T\to\infty$ and $T=1$.

where $Y(m)$ is a matrix that is fully specified in the following.

Let $\mathcal{N}_{j}^{\prime}$ and $\mathcal{N}_{j}^{b}$ denote the nonfaulty nodes and the Byzantine nodes, respectively, in the neighborhood of $j\in J^{\prime}$, i.e., $\mathcal{N}_{j}^{\prime}=J^{\prime}\cap\mathcal{N}_{j}$ and $\mathcal{N}_{j}^{b}=\mathcal{N}_{j}\setminus\mathcal{N}_{j}^{\prime}$. Notice that one of two cases can happen during each iteration at node $j\in J^{\prime}$:

For case (10(a)), since $|\mathcal{N}_{j}^{b}|\leq b$ and $|\mathcal{N}_{j}^{s}(m)|=|\mathcal{N}_{j}^{l}(m)|=b$, we must have $\mathcal{N}_{j}^{s}(m)\cap\mathcal{N}_{j}^{\prime}\neq\emptyset$ and $\mathcal{N}_{j}^{l}(m)\cap\mathcal{N}_{j}^{\prime}\neq\emptyset$. Then for each $i\in\mathcal{N}_{j}^{\ast}(m)\cap\mathcal{N}_{j}^{b}$, $\exists s_{j}^{i}\in\mathcal{N}_{j}^{s}(m)\cap\mathcal{N}_{j}^{\prime}$ and $l_{j}^{i}\in\mathcal{N}_{j}^{l}(m)\cap\mathcal{N}_{j}^{\prime}$ satisfying $\omega_{s_{j}^{i}}(m)\leq\omega_{i}(m)\leq\omega_{l_{j}^{i}}(m)$. Therefore, we have for each $i\in\mathcal{N}_{j}^{\ast}(m)\cap\mathcal{N}_{j}^{b}$ that $\exists\theta_{i}^{j}(m)\in$ such that the following holds:

We can now rewrite the update at node $j\in J^{\prime}$ as follows:

It can be seen from (III-B) that the screening rule in ByRDiE effectively enables nonfaulty nodes to replace data received from Byzantine nodes with convex combinations of data received from nonfaulty nodes in their neighborhoods. This enables us to express the updates at nonfaulty nodes in the form (9), with the entries of $Y(m)$ given by

Notice further that, since $\mathcal{N}_{j}^{\ast}(m)\cap\mathcal{N}_{j}^{b}=\emptyset$ (cf. (III-B)), case (10(b)) corresponds to a special case of case (10(a)) in which we keep only the first, second, and last rows of (13). It is worth noting here that our forthcoming proof does not require knowledge of $Y(m)$; in particular, since the choices of $s_{j}^{i}$ and $l_{j}^{i}$ are generally not unique, $Y(m)$ itself is also generally not unique. The main thing that matters here is that $Y(m)$ will always be a row stochastic matrix; we refer the reader to for further properties of $Y(m)$.

In order to complete our claim that nonfaulty nodes achieve consensus under ByRDiE, even in the presence of Byzantine failures in the network, fix an arbitrary $m_{0}\geq 0$ and consider $m>m_{0}$. It then follows from (9) that

$\Phi(m,m):=Y(m)$, and $\Phi(m,m+1):=I$. Notice that $\Phi(m,m_{0})$ is also row stochastic since it is a product of row-stochastic matrices. We can then express (III-B) as

Next, we need two key properties of $\Phi(m,m_{0})$ from .

Suppose Assumption 3 holds. Then for any $m_{0}\geq 0$, there exists a stochastic vector $\pi(m_{0})$ such that

In words, Lemma 1 states that the product of the row-stochastic matrices $Y(m)$ converges to a steady-state matrix whose rows are identical and stochastic. We can also characterize the rate of this convergence; to this end, let $\psi$ denote the total number of reduced graphs that can be generated from $\mathcal{G}$, and define $\nu:=\psi|J^{\prime}|$, $\mathcal{N}_{max}:=\max\limits_{j\in J^{\prime}}|\mathcal{N}_{j}|$, and

Suppose Assumption 3 holds. We then have that $\forall m_{0}\geq 0$ ,

Lemma 2 describes the rate at which the rows of $\Phi(m,m_{0})$ converge to $\pi(m_{0})$. We now leverage this result and show that the nonfaulty nodes achieve consensus under ByRDiE in the limit of large $m$, which translates into $\bar{r}\rightarrow\infty$ and/or $T\rightarrow\infty$. To this end, under the assumption of $m_{0}=1$, we have from (15) the following expression:

Next, suppose the nonfaulty nodes stop computing local gradients at time step $m$ and use $G(m+m^{\prime})=0$ for $m^{\prime}\geq 0$. Then, defining $V(m):=\lim\limits_{m^{\prime}\rightarrow\infty}\Omega(m+m^{\prime}+1)$, we obtain:

Let Assumptions 1 and 3 hold and fix $\bar{m}=\bar{r}T+1$. Then,

as $\bar{r}\to\infty$ and/or $T\to\infty$.

Let Assumptions 1 and 3 hold. Then, fixing $T=1$, the iterates of ByRDiE satisfy:

where $\bar{V}(r)$ denotes the consensus vector in iteration $r$.

Theorem 2, which is a straightforward consequence of the proof of Theorem 1 (cf. (A)), guarantees a sublinear rate for consensus; indeed, choosing the stepsize evolution to be $\rho(r)=\mathcal{O}\left(1/r\right)$ gives us $\|w_{j}^{r}-\bar{V}(r)\|=\mathcal{O}\left(\sqrt{P}/r\right)$.

III-C Theoretical Guarantees: Convergence for T→∞→𝑇T\to\infty

We now move to the second (and perhaps the most important) claim of this paper. This involves showing that the output of ByRDiE converges in probability to the minimizer (and minimum) of the statistical risk (cf. (2)) for two extreme cases: Case I: $T\to\infty$ and Case II: $T=1$. We start our discussion with the case of $T\rightarrow\infty$, in which case an auxiliary lemma simply follows from [13, Theorem 2] (also, see ).

Let Assumptions 1 and 3 hold, and let the $k$-th subproblem of the coordinate descent loop in iteration $r$ of ByRDiE be initialized with some $\{w_{j}\}_{j\in J^{\prime}}$. Then, as $T\to\infty$,

for some $\alpha_{j}(r,k)\geq 0$ such that $\sum_{j\in J^{\prime}}\alpha_{j}(r,k)=1$.

Lemma 3 shows that each subproblem of the coordinate descent loop in ByRDiE under Case I converges to the minimizer of some convex combination of local empirical risk functions of the nonfaulty nodes with respect to each coordinate. In addition, Lemma 3 guarantees that consensus is achieved among the nonfaulty nodes at the end of each coordinate descent loop under Case I. Note that while this fact is already known from Theorems 1 and 2, Lemma 3 helps characterize the consensus point. In summary, when nonfaulty nodes begin a coordinate descent subproblem with identical local estimates and $T\to\infty$, they are guaranteed to begin the next subproblem with identical local estimates.

for some $\alpha_{j}(r,k)\geq 0$ such that $\sum_{j\in J^{\prime}}\alpha_{j}(r,k)=1$. Note that $h_{k}^{r}(\cdot)$ is strictly convex and Lipschitz continuous. Now for fixed $r$ and $k$, define

In words, if one were to solve the statistical risk minimization problem (2) using (centralized) coordinate descent then $w^{\star}$ will be the $k$-th component of the output of coordinate descent after update of each coordinate $k$ in every iteration $r$. In contrast, $\widehat{w}$ is the $k$-th component of the outputs of ByRDiE after update of each coordinate $k$ in every iteration $r$ (cf. Lemma 3). While there exist works that relate the empirical risk minimizers to the statistical risk minimizers (see, e.g., ), such works are not directly applicable here because of the fact that $H_{k}^{r}(w^{\prime})$ in this paper changes from one pair $(r,k)$ of indices to the next. Nonetheless, we can provide the following uniform statistical convergence result for ByRDiE under Case I that relates the empirical minimizers $\{\widehat{w}\}$ to the statistical minimizers $\{w^{\star}\}$.

where $c_{1}:=8C$, $c_{2}:=24C|J^{\prime}|$, and $c_{3}:=24L^{\prime}\Gamma P$.

The proof of this theorem is provided in Appendix B. In words, ignoring minor technicalities that are resolved in Theorem 4 in the following, Theorem 3 states that the coordinate-wise outputs $\{\widehat{w}\}$ of ByRDiE for all $(r,k)$ under Case I achieve, with high probability, almost the same statistical risk as that obtained using the corresponding coordinate-wise statistical risk minimizers $\{w^{\star}\}$. We now leverage this result to prove that the iterates of ByRDiE at individual nodes achieve statistical risk that converges to the minimum statistical risk achieved by the statistical risk minimizer (vector) $w^{*}$ (cf. (2)).

Let Assumptions 1–3 hold. Then, $\forall j\in J^{\prime},\forall\epsilon>0,$ and $T\to\infty,$ we have

where $c_{1}^{\prime}:=c_{1}c_{4}$, $c_{2}^{\prime}:=c_{2}c_{4}$, and $c_{3}^{\prime}:=c_{3}c_{4}$ for $c_{4}:=2PL\Gamma$, and $(\bar{a},c_{1},c_{2},c_{3})$ are as defined in Theorem 3.

The proof of this theorem is given in Appendix C. We now make a couple of remarks concerning Theorem 4. First, note that the uniqueness of the minimum of strictly convex functions coupled with the statement of Theorem 4 guarantee that $\forall j\in J^{\prime},w^{\bar{r},T}_{j}\to w^{\ast}$ with high probability.

Second, Theorem 4 helps crystallize the advantages of distributed learning over local learning, in which nodes individually solve the empirical risk minimization problem using only their local data samples. Prior work on stochastic convex optimization (see, e.g., [47, Theorem 5 and (11)]) tells us that, with high probability and ignoring the $\log$ terms, the gap between the statistical risk achieved by the empirical risk minimizer and the statistical risk minimizer scales as $\mathcal{O}\left(1/\sqrt{\text{\# of samples}}\right)$ in the centralized setting. This learning rate translates into $\mathcal{O}(1/\sqrt{N})$ for local learning and $\mathcal{O}(1/\sqrt{MN})$ for the idealized centralized learning. In contrast, Theorem 4 can be interpreted as resulting in the following distributed learning rate (with high probability):We are once again ignoring the $\log$ terms in our discussion; it can be checked, however, that the $\log$ terms resulting from Theorem 4 match the ones in prior works such as on centralized learning.

where $N_{\text{eff}}:=N/\bar{a}^{2}$ denotes the effective number of training samples available during distributed learning.

In order to understand the significance of (30), notice that

In particular, $\bar{a}^{2}=1/M$ if and only if there are no Byzantine failures in the network, resulting in the coordinate descent-based distributed learning of $\mathcal{O}\left(1/\sqrt{NM}\right)$, which matches the centralized learning rate. (This, to the best of our knowledge, is the first result on the explicit learning rate of coordinate descent-based distributed learning.) In the presence of Byzantine nodes, however, the maximum number of trustworthy samples in the network is $|J^{\prime}|N$, and (30) and (31) tell us that the learning rate of ByRDiE in this scenario will be somewhere between the idealized learning rate of $\mathcal{O}\left(1/\sqrt{|J^{\prime}|N}\right)$ and the local learning rate of $\mathcal{O}\left(1/\sqrt{N}\right)$.

where the parameter $\delta(\epsilon,N,\bar{a})$ is given by

while $c_{5}:=c_{4}L^{\prime}\sqrt{P}\gamma^{*}$, and the constants $c_{1}^{\prime},c_{2}^{\prime},c_{3}^{\prime}$, and $c_{4}$ are as defined in Theorem 4.

III-D Theoretical Guarantees: Convergence for T=1𝑇1T=1

Case I for ByRDiE, in which $T\to\infty$, is akin to doing exact line search during minimization of each coordinate, which is one of the classic ways of implementing coordinate descent. Another well-adopted way of performing coordinate descent is to take only one step in the direction of descent in a dimension and then switch to another dimension . Within the context of ByRDiE, this is equivalent to setting $T=1$ (Case II); our goal here is to provide convergence guarantees for ByRDiE in this case. Our analysis in this section uses the compact notation $w_{j}^{r}:=w_{j}^{r,1}\equiv w_{j}^{r+1}(1)$. In the interest of space, and since the probabilistic analysis of this section is similar to that of the previous section, our probability results are stated asymptotically here, rather than in terms of precise bounds.

where $e_{k}$ denotes the standard basis vector (i.e., it is zero in every dimension except $k$ and $[e_{k}]_{k}=1$) and the relationship between $r,k$, and $q$ is as defined earlier. The sequence $Q(q)$ effectively helps capture update of the optimization variable after each coordinate-wise update of ByRDiE. In particular, we have the following result concerning the sequence $Q(q)$.

Let Assumptions 1, 2, and 3 hold for ByRDiE and choose $T=1$. We then have that $Q(q)\xrightarrow{q,N}w^{\ast}$ in probability.

The proof of this lemma is provided in Appendix E. We are now ready to state the convergence result for ByRDiE under Case II (i.e, $T=1$).

Let Assumptions 1, 2, and 3 hold for ByRDiE and choose $T=1$. Then, $\forall j\in J^{\prime}$, $w_{j}^{\bar{r}}\xrightarrow{\bar{r},N}w^{\ast}$ in probability.

We have from Theorem 1 that $\forall j\in J^{\prime},[w_{j}^{\bar{r}}]_{k}\xrightarrow{\bar{r}}v^{k}(\bar{r})$ for all $k\in\{1,2,\dots,P\}$. The definition of $Q(q)$ along with Lemma 4 also implies that $v^{k}(\bar{r})\xrightarrow{\bar{r},N}[w^{\ast}]_{k}$ in probability. This completes the proof of the theorem. ∎

III-E How to Choose the Parameter T𝑇T in ByRDiE?

The parameter $T$ in ByRDiE trades off consensus among the nonfaulty nodes and the convergence rate as a function of the number of communication iterations $t_{c}(r,k,t)$, defined as

In particular, given a fixed $T$, each iteration $r$ of ByRDiE involves $TP$ (scalar-valued) communication exchanges among the neighboring nodes. In the previous section, we have provided theoretical guarantees for the two extreme cases of $T\to\infty$ and $T=1$. In the limit of large $\bar{r}$, our results establish that both extremes result in consensus and convergence to the statistical risk minimizer. In practice, however, different choices of $T$ result in different behaviors as a function of $t_{c}(\equiv t_{c}(r,k,t))$, as discussed in the following and as illustrated in our numerical experiments in the next section.

When $T$ is large, the two time-scale nature of ByRDiE ensures the disagreement between nonfaulty nodes does not become too large in the initial stages of the algorithm; in particular, the larger the number of iterations $T$ in the inner loop, the smaller the disagreement among the nonfaulty nodes at the beginning of the algorithm. Nonetheless, this comes at the expense of slower convergence to the desired minimizer as a function of the number of communication iterations $t_{c}$.

On the other hand, while choosing $T=1$ also guarantees consensus among nonfaulty nodes, it only does so asymptotically (cf. Theorem 1). Stated differently, ByRDiE cannot guarantee in this case that the disagreement between nonfaulty nodes will be small in the initial stages of the algorithm (cf. Theorem 2). This tradeoff between small consensus error and slower convergence (as a function of communication iterations $t_{c}$) should be considered by a practitioner when deciding the value of $T$. We conclude by noting that the different nature of the two extreme cases requires markedly different proof techniques, which should be of independent interest to researchers.

Our discussion so far has focused on the use of a static parameter $T$ within ByRDiE. Nonetheless, it is plausible that one could achieve somewhat better tradeoffs between consensus and convergence through the use of an adaptive parameter $T_{r}$ in lieu of $T$ that starts with a large value and gradually decreases as $r$ increases. Careful analysis and investigation of such an adaptive two-time scale variant of ByRDiE, however, is beyond the scope of this paper.

IV Numerical Results

In this section, we validate our theoretical results and make various observations about the performance of ByRDiE using two sets of numerical experiments. The first set of experiments involves learning of a binary classification model from the infinite MNIST datasethttps://leon.bottou.org/projects/infimnist that is distributed across a network of nodes. This set of experiments fully satisfies all the assumptions in the theoretical analysis of ByRDiE. The second set of experiments involves training of a small-scale neural network for classification of the Iris dataset distributed across a network. The learning problem in this case corresponds to a nonconvex one, which means this set of experiments does not satisfy the main assumptions of our theorems. Nonetheless, we show in the following that ByRDiE continues to perform well in such distributed nonconvex learning problems.

We consider a distributed linear binary classification problem involving MNIST handwritten digits dataset. The (infinite) MNIST dataset comprises images of handwritten digits from ‘0’ to ‘9’. Since our goal is demonstration of the usefulness of ByRDiE in the presence of Byzantine failures, we focus only on distributed training of a linear support vector machine (SVM) for classification between digits ‘5’ and ‘8’, which tend to be the two most inseparable digits. In addition to highlighting the robustness of ByRDiE against Byzantine failures in this problem setting, we evaluate its performance for different choices of the parameters $T$, $N$, and $b$.

In terms of the experimental setup, we generate Erdős–Rényi networks ($p=0.5$) of $M$ nodes, $b$ of which are randomly chosen to be Byzantine nodes. All nonfaulty nodes are allocated $N$ samples—equally divided between the two classes—from the dataset, while a Byzantine node broadcasts random data uniformly distributed between and $1$ to its neighbors in each iteration. When running ByRDiE algorithm, each node updates one dimension $T$ times before proceeding to the next dimension. All tests are performed on the same test set with 1000 samples of digits ‘5’ and ‘8’ each.

We first report results that confirm the idea that ByRDiE can take advantage of cooperation among different nodes to achieve better performance even when there are Byzantine failures in the network. This involves varying the local sample size $N$ and comparing the classification accuracy on the test data. We generate a network of $M=50$ nodes, randomly pick $b=10$ nodes within the network to be Byzantine nodes ($20\%$ failures), vary $N$ from $10$ to $30$, and average the final set of results over 10 independent (over network, Byzantine nodes, and data allocation) Monte Carlo trials of ByRDiE. The performance of ByRDiE is compared with two approaches: ($i$) coordinate descent-based training using only local data (local CD); and ($ii$) distributed gradient descent-based training involving network data (DGD). To achieve the best convergence rate for ByRDiE, $T$ is chosen to be 1 in these experiments. The final set of results are shown in Fig 1, in which the average classification accuracy is plotted against the number of algorithmic iterations, corresponding to the number of (scalar-valued) communication iterations for ByRDiE, the number of per-dimension updates for local CD, and the number of (vector-valued) communication iterations for DGD. It can be seen that the performance of local CD is not good enough due to the small local sample size. On the other hand, when trying to improve performance by cooperating among different nodes, DGD fails for lack of robustness against Byzantine failures. In contrast, the higher accuracy of ByRDiE shows that ByRDiE can take advantage of the larger distributed dataset while being Byzantine resilient.

Next, we investigate the impact of different values of $T$ in ByRDiE on the tradeoff between consensus and convergence rate. This involves generating a network of $M=50$ nodes that includes randomly placed $b=5$ Byzantine nodes within the network ($10\%$ failures), randomly allocating $N=60$ training samples to each nonfaulty node, and averaging the final set of results over $10$ independent trials. The corresponding results are reported in Fig. 2 for four different values of $T$ as a function of the number of communication iterations $t_{c}$ in terms of ($i$) average classification accuracy (Fig. 2(a)) and ($ii$) average pairwise distances between local classifiers (Fig. 2(b)). It can be seen from these figures that $T=1$ leads to the fastest convergence in the initial stages of the algorithm, but this fast convergence comes at the expense of the largest differences among local classifiers, especially in the beginning of the algorithm. In contrast, while $T=4$ results in the slowest convergence, it ensures closeness of the local classifiers at all stages of the algorithm.

Finally, we investigate the impact of different values of $b$ (the actual number of Byzantine nodes) on the performance of ByRDiE. In order to amplify this impact, we focus on a smaller network of $M=20$ nodes with a small number of $N=10$ samples per node and $T=3$. Assuming resilience against the worst-case Byzantine scenario (cf. Remark 3), ByRDiE requires the neighborhood of each node to have at least $(2b+1)$ nodes. Under this constraint, we find that $b\geq 5$ in this setting, which translates into $25\%$ or more of the nodes as being Byzantine, often renders ByRDiE unusable.As noted in Remark 3, one could overcome this limit by opting instead for resilience against the average-case scenario and replacing $b$ with $b_{\text{ave}}$. We therefore report our results in terms of both consensus and convergence behavior by varying $b$ from $1$ to $4$. The final results, averaged over $10$ independent trials, are shown in Fig. 3. It can be seen from these figures that both the classification accuracy (Fig. 3(a)) and the consensus performance (Fig. 3(b)) of ByRDiE suffer as $b$ increases from $1$ to $4$. Such behavior, however, is in line with our theoretical developments. First, as $b$ increases, the post-screening graph becomes sparser, which slows down information diffusion and consensus. Second, as $b$ increases, fewer samples are incorporated into distributed learning, which limits the final classification accuracy of distributed SVM.

IV-B Distributed Neural Network Using Iris Dataset

While the theoretical guarantees for ByRDiE have been developed for convex learning problems, we now demonstrate the usefulness of ByRDiE in distributed nonconvex learning problems. Our setup in this regard involves distributed training of a small-scale neural network using the three-class Iris dataset. This dataset consists of 50 samples each from three species of irises, with each sample being a four-dimensional feature vector. While one of the species in this data is known to be linearly separable from the other two, the remaining two species cannot be linearly separated. We employ a fully connected three-layer neural network for classification of this dataset, with a four-neuron input layer, a three-neuron hidden layer utilizing the rectified linear unit (ReLU) activation function and a three-neuron output layer using the softmax function for classification. The distributed setup corresponds to a random network of $M=10$ nodes with one Byzantine node ($b=1$), in which each nonfaulty node is allocated $N=15$ samples that are equally divided between the three classes.

Since distributed training of this neural network requires solving a distributed nonconvex problem, our theoretical guarantees for ByRDiE do not hold in this setting. Still, we use ByRDiE with $T=1$ to train the neural network for a total of 200 independent trials with independent random initializations. Simultaneously, we use DGD for distributed training and also train the neural network in a centralized setting using CD for comparison purposes. The final results are reported in Table I, which lists the average number of outer iterations needed by each training algorithm to achieve $95\%$ classification accuracy. It can be seen from these results that while DGD completely breaks down in the presence of a single Byzantine node, ByRDiE continues to be resilient to Byzantine failures in distributed nonconvex learning problems and comes close to matching the performance of centralized CD in this case.

V Conclusion

In this paper, we have introduced a coordinate descent-based distributed algorithm, termed ByRDiE, that can carry out distributed learning tasks in the presence of Byzantine failures in the network. The proposed algorithm pursues the minimizer of the statistical risk in a fully distributed environment and theoretical results guarantee that ByRDiE achieves this objective under mild assumptions on the risk function and the network topology. In addition, numerical results presented in the paper validate resilience of ByRDiE against Byzantine failures in the network for distributed convex and nonconvex learning tasks. Future works in this direction include strengthening the results in terms of almost sure convergence, deriving explicit rates of convergence, and extensions of theoretical analysis to constant step size and nonconvex risk functions.

Appendix A Proof of Theorem 1

Fix any dimension $k\in\{1,\dots,P\}$ and recall from (III-B) that

Since $m:=(r-1)T+t$ and $[\Omega(m)]_{j}:=[w_{j}^{r}(t)]_{k}$, we get

where we have used the fact that $\Phi(m,m+1)=I$. Thus,

where the last summation follows from the observation that $\sum_{i=1}^{|J^{\prime}|}[\pi(m+1)]_{i}=1$. Further, Assumption 1 implies there exists a coordinate-wise bound $L_{\nabla}\leq L^{\prime}$ such that $\forall i,m,|[G(m)]_{i}|\leq L_{\nabla}$. Using this and Lemma 2, we obtain

Note that the last inequality in the above expression exploits the fact that $[w_{i}^{1}(1)]_{k}\equiv 0$. In the case of an arbitrary initialization of ByRDiE, however, we could have bounded the first term in the second inequality in (A) as $|J^{\prime}|\Gamma\mu^{\frac{m+1}{\nu}}$, which still goes to zero as $m\rightarrow\infty$.

We now expand the term $\sum_{\tau=1}^{m-1}\bar{\rho}(\tau)\mu^{\frac{m-\tau}{\nu}}$ in (A) asWe focus here only on the case of an even $m$ for the sake of brevity; the expansion for an odd $m$ follows in a similar fashion.

It can be seen from the above expression that $\lim_{m\rightarrow\infty}\sum_{\tau=1}^{m-1}\bar{\rho}(\tau)\mu^{\frac{m-\tau}{\nu}}\leq 0$. Since $\sum_{\tau=1}^{m-1}\bar{\rho}(\tau)\mu^{\frac{m-\tau}{\nu}}\geq 0$, it follows that $\lim_{m\rightarrow\infty}\sum_{\tau=1}^{m-1}\bar{\rho}(\tau)\mu^{\frac{m-\tau}{\nu}}=0$. This fact in concert with (A) and the diminishing nature of $\bar{\rho}(m)$ give

Next, take $r=\bar{r}$, $t=T$, and note that $w_{j}^{r}(t+1)=w_{j}^{\bar{r},T}$ and $\bar{m}=\bar{r}T+1=[(r-1)T+T]+1=m+1$ in this case. Further, $\bar{m}\to\infty$ when $\bar{r}\to\infty$ and/or $T\to\infty$. It therefore follows from (41) that $[w_{j}^{\bar{r},T}]_{k}\to v^{k}(\bar{m})$ as $\bar{r}\to\infty$ and/or $T\to\infty$. Finally, since $k$ in our analysis was arbitrary, the same holds for all $k=1,2,\dots,P$.∎

Appendix B Proof of Theorem 3

Next, notice from (II), (22), and (23) that

Further, since the $|J^{\prime}|$-dimensional vector $\alpha^{r}_{k}$ is an arbitrary element of the standard simplex, defined as

the probability bound in (44) also holds for any $v\in\Delta$, i.e.,

We now define the set $\mathcal{S}_{\alpha}:=\{\alpha^{r}_{k}\}_{r,k=1}^{\bar{r},P}$. Our next goal is to leverage (46) and derive a probability bound similar to (44) that uniformly holds for all $v\in\mathcal{S}_{\alpha}$. To this end, let

Therefore, picking any $\epsilon^{\prime\prime}>0$, and defining $\epsilon^{\prime}:=\epsilon^{\prime\prime}/2$ and $\xi:=\epsilon^{\prime\prime}/(2C\sqrt{|J^{\prime}|})$, we have from (B) and (51) that

We now fix $\epsilon^{\prime\prime\prime}>0$, and define $\epsilon^{\prime\prime}:=\epsilon^{\prime\prime\prime}/2$ and $\zeta:=\epsilon^{\prime\prime\prime}/4L^{\prime}$. We then obtain the following from (B)–(57):

for any $\epsilon>0$. Conditioned on this event, we have

Therefore, given any $\epsilon>0$, we have from (B)–(B) that

Appendix C Proof of Theorem 4

We now fix an arbitrary $\epsilon^{\prime}\in(0,1)$ and note that

where ($a$) follows from the definition of ${w^{\star}}^{r}_{k}$ and ($b$) follows from Assumption 1. Plugging $w^{\prime}=\widehat{w}_{k}^{r-1}-\frac{1}{L}[\nabla h_{k}^{r}(\widehat{w}_{k}^{r-1})]_{k}$ in (C), we obtain

Using (67), (C), and the Cauchy–Schwarz inequality yields

Setting $\epsilon^{\prime}=\epsilon/c_{4}$ in (C) and removing conditioning on (62) using Theorem 3 give us the desired bound.

Appendix D Proof of Theorem 5

with probability $\geq 1-\delta(\epsilon,N,\bar{a})$ as long as $\bar{f}(\widehat{w}^{r})-\bar{f}^{*}>\epsilon$ (see, e.g., (65) and the discussion around it). Conditioning on the probability event described by (70), the definition of $h_{k}^{r}(\cdot)$ and (70) then give us the following recursion in $r$:

Plugging the inequality $\bar{f}^{0}-\bar{f}^{*}\leq L^{\prime}\|w^{*}\|\leq L^{\prime}\sqrt{P}\gamma^{*}$ in (72) completes the proof.∎

Appendix E Proof of Lemma 4

because of convexity of $\bar{f}(\cdot)$, the Cauchy–Schwarz inequality, and our assumptions. Since this is the desired result, we need now focus on the claim of strict monotonicity of $\bar{f}(Q(q))$ for this lemma. To prove this claim, note from Assumption 1 that

where (a) follows from the fact that $Q(q+1)-Q(q)$ is only nonzero in dimension $k$.

where E(q):=\eta(q)\sum_{i=1}^{|J^{\prime}|}[\pi(r+1)]_{i}\big{(}[\nabla\widehat{f}(Q(q),S_{i})]_{k}-[\nabla\widehat{f}(w_{i}^{r},S_{i})]_{k}\big{)}e_{k}. Plugging this into (E) results in

The right-hand side of (E) strictly lower bounded by implies strict monotonicity of $\bar{f}(Q(q))$. Simple algebraic manipulations show that this is equivalent to the condition

converges to $1$ uniformly for all $(r,k)$ (equivalently, all $q$) for any $\epsilon^{\prime}>0$. We therefore have with probability $1$ (as $N\rightarrow\infty$)

Next, we consider two cases: ($i$) $[\nabla\bar{f}(Q(q))]_{k}>0$, and ($ii$) $[\nabla\bar{f}(Q(q))]_{k}<0$. When $[\nabla\bar{f}(Q(q))]_{k}>0$, we have in probability $\sum_{i\in J^{\prime}}[\pi(r+1)]_{i}[\nabla\widehat{f}(Q(q),S_{i})]_{k}\geq[\nabla\bar{f}(Q(q))]_{k}-\epsilon^{\prime}$. This fact along with (E), the realization that $\frac{L\eta(q)^{2}}{2}-\eta(q)<0$ for large enough $q$ since $\eta(q)\rightarrow 0$, and some tedious but straightforward algebraic manipulations show that the following condition is sufficient for (E) to hold in probability:

Using similar arguments, one can also show that the case $[\nabla\bar{f}(Q(q))]_{k}<0$ also results in (E) as a sufficient condition for (E) to hold in probability. We now note that $|[\nabla\bar{f}(\cdot)]_{k}|$ and $|[\nabla\widehat{f}(\cdot,\cdot)]_{k}|$ in (E) can be upper bounded by some constants $L_{\bar{\nabla}}$ and $L_{\nabla}$ by virtue of Assumption 1 and the definition of $W$. This results in the following sufficient condition for (E):

The right-hand side of (E) can be made arbitrarily small (and, in particular, equal to $\epsilon_{\nabla}$) through appropriate choice of $\epsilon^{\prime}$ and large enough $q$; indeed, we have from our assumptions, Theorem 1, and the definitions of $\eta(q)$ and $E(q)$ that both $[E(q)]_{k}$ and $[E(q)]_{k}/\eta(q)$ converge to as $q\rightarrow\infty$.

Taking summation on both sides of (83) from $q=q_{0}$ to $\infty$, and noting that $\sum_{q=q_{0}}^{\infty}\eta(q)=\infty$ and $\sum_{q=q_{0}}^{\infty}\eta(q)^{2}<\infty$, gives us $\bar{f}(Q(q_{0}))-\lim_{q\to\infty}\bar{f}(Q(q))=\infty$. This contradicts the fact that $\bar{f}(\cdot)$ is lower bounded, thereby validating our claim.

References