Byzantine-Robust Decentralized Stochastic Optimization with Stochastic Gradient Noise-Independent Learning Error

Existing decentralized deterministic optimization methods, such as the classical decentralized gradient descent (DGD) [6], generally use weighted mean to aggregate neighboring models and are hence vulnerable to Byzantine attacks. The remedy is to replace weighted mean aggregation by robust aggregation. The works of [18, 19, 20] study Byzantine-robust decentralized deterministic optimization with scalar models, using trimmed mean to replace weighted mean. When the models are vectors, ByRDiE [21] performs coordinate gradient descent, and applies trimmed mean [18] to filter out potential malicious elements on every dimension. A centerpoint-based method is proposed in [22] to guarantee that the aggregated model always lies in the convex hull of the regular neighbors’ models. However, for high-dimensional problems, these two methods are not suitable. Coordinate gradient descent used in ByRDiE is slow, while the centerpoint-based method requires the number of neighbors for every agent to be larger than the problem dimension. BRIDGE [23] extends the work of ByRDiE [21], allowing all coordinates to be updated at one time with the help of gradient descent. The work of [24] provides a general algorithmic framework that includes BRIDGE as a special case, and establishes the linear convergence speed and approximate consensus. In [25, 26], every agent aggregates the signs of the differences between its own model and the neighbors’ such that the influence of Byzantine attacks is limited. The work of [27] considers both gradient aggregation and model aggregation. It combines two techniques, comparative gradient elimination to select relatively reliable neighboring gradients, and coordinate-wise trimmed mean to aggregate neighboring models. But [27] requires the network to be fully connected.

Although there are an increasing number of methods, such as decentralized parallel stochastic gradient descent (DPSGD) [4, 6], for decentralized stochastic optimization, few of them consider Byzantine-robustness. Motivated by [25] and [26], [28] introduces a total variation (TV)-norm penalized formulation to force the local models to be close, but allow possible outliers. Applying the stochastic subgradient method to solve this TV-norm penalized formulation yields a Byzantine-robust algorithm, and its sublinear convergence is established. The work of [29] proposes a robust decentralized centered-clipping rule to aggregate the received local models. The work of [30] provides a principled guideline for designing proper robust aggregation rules in Byzantine-robust decentralized stochastic optimization. It also proposes iterative outlier scissor as one of such robust aggregation rules. However, the robust aggregation rules introduced in [29] and [30] are computationally costly. In addition, the convergence rates established in [29] and [30] are both sublinear.

On the other hand, Byzantine-robust distributed stochastic optimization has been a popular topic. Therein, a central server maintains a single global model and aggregates messages from the distributed agents. Most of the methods modify distributed stochastic gradient descent (SGD) by robustly aggregating the stochastic gradients sent from the agents [31, 32]. Such robust aggregation rules include coordinate-wise median, geometric median, trimmed mean, etc. Byzantine-robust stochastic second-order methods have also been developed in [33]. To enhance Byzantine-robustness, [34] assumes that the central server has extra clean data, and uses the clean data to distinguish malicious messages from the true stochastic gradients. However, it is difficult to generalize the above-mentioned works to the decentralized scenario, since there is no central server to collect and aggregate messages in a decentralized network.

In stochastic optimization, the noise induced by calculating stochastic gradients plays a critical role and affects convergence. For reducing the negative effect of stochastic gradient noise, variance reduction methods have been employed in decentralized stochastic optimization [35, 36, 37]. In Byzantine-robust distributed stochastic optimization, stochastic gradient noise also significantly influences Byzantine-robustness. With large stochastic gradient noise, the regular stochastic gradients are statistically very different, which is conducive for the Byzantine agents to hide themselves and perform attacks [38]. In light of this observation, [38] proposes to use the stochastic average gradient algorithm (SAGA) to eliminate the impact of inner variation, namely, the stochastic gradient noise caused by the heterogeneity of every regular agent’s local samples. The works of [39, 40] show that momentum acceleration can effectively reduce the impact of stochastic gradient noise and enhance Byzantine-robustness. Aiming at non-convex problems, [41] combines the stochastic variance-reduced gradient (SVRG) method and robust aggregation, and empirically demonstrates the performance. However, none of the existing works considers variance reduction in Byzantine-robust decentralized stochastic optimization. Due to the absence of the central server, there is no common model in the decentralized system, and the regular agents have to calculate their stochastic gradients at different local models. Thus, the statistical difference between the regular agents’ local models is enlarged, and variance reduction methods are more difficult to analyze.

Another relevant line of research in the signal processing society is Byzantine-robust decentralized detection. An adaptive threshold is used in [42] to screen malicious messages and alleviate the negative effect of Byzantine agents. The alternating direction method of multipliers (ADMM) is applied in [43], where the trimmed mean aggregation rule is adopted to defend against Byzantine attacks. The work of [44] considers identifying Byzantine models under data falsification attacks. For a comprehensive survey, readers are referred to [17].

Although the methods proposed in [28, 29, 30] are proven effective in handling Byzantine attacks for decentralized stochastic optimization, the established convergence speeds are sublinear. In particular, for the decentralized Byzantine-robust stochastic aggregation (DRSA) algorithm proposed in [28], with a constant step size, it exhibits a linear convergence speed but the learning error is suboptimal and can be significant (see Section II). With a diminishing step size, DRSA achieves an optimal learning error in order (see Section IV), but only has a sublinear convergence speed. We reveal that the underlying reason of such an unsatisfactory trade-off is the existence of stochastic gradient noise. In this context, our main contributions are as follows.

Following the line of [25, 26, 28], we penalize the consensus constraints in (3) by a TV-norm term, which yields

with $\lambda>0$ being the penalty parameter. The TV-norm penalty term forces the local models to be close, but allows possible outliers. Note that [25] and [26] consider decentralized deterministic optimization, while [28] investigates decentralized stochastic optimization in the expectation minimization form, not in the finite-sum minimization form here. Nevertheless, the DRSA algorithm in [28] can still be applied to solve (4). When the Byzantine agents are absent, applying the stochastic subgradient method to solve (4) yields the update

for any regular agent $w\in\mathcal{R}$ at time $k$. Therein, $\alpha^{k}>0$ is the step size, and $i_{w}^{k}$ is the local sample index (one sample or a mini-batch of samples) selected by regular agent $w$ at time $k$. To run (5), every regular agent $w\in\mathcal{R}$ needs to collect its neighboring models. However, when the Byzantine agents appear, (5) is not applicable since every regular agent $w\in\mathcal{R}$ does not know the identities of its Byzantine neighbors, while the Byzantine neighbors may send arbitrarily malicious messages for the sake of disturbing the optimization process. Denote $z_{v}^{k}\in\mathbb{R}^{p}$ as an arbitrary model that Byzantine agent $v\in\mathcal{B}$ sends to all neighbors. In fact, it can send different arbitrary models to different neighbors, but for notational convenience we use the same $z_{v}^{k}$, which does not affect algorithm development and theoretical analysis. In this case, for regular agent $w\in\mathcal{R}$, the update rule of DRSA is changed from (5) to

DRSA is a stochastic subgradient-based method and uses a decreasing step size by default. According to Theorem 2 in [28], the theoretical convergence rate of DRSA is sublinear, which is slow. With a proper constant step size, DRSA has a linear convergence rate, but the corresponding learning error is relative to the variance of stochastic gradients, which could be large when the local samples of each regular agent are statistically very different.

Here we illustrate the impact of stochastic gradient noise on DRSA with a simple decentralized stochastic least-squares problem. As shown in Fig. 1, when the batch size is small, the stochastic gradient noise is large and the iterate $x^{k}$ converges to a neighborhood far away from the optimal solution $x^{*}$. As the batch size increases, the convergence error correspondingly decreases. However, a larger batch size means that more stochastic gradients must be calculated at every time, which is expensive. Inspired by this observation, we propose to utilize computationally cheap variance reduction techniques to reduce the stochastic gradient noise, and in consequence, lower the learning error.

We make the following assumptions that are common in the analysis of decentralized stochastic optimization [4, 28] and variance reduction [45, 46].

Assumption 5 bounds the variance of the local stochastic gradients. It is worth noting that BRAVO-SAGA and BRAVO-LSVRG only need Assumptions 3 and 4, but do not need Assumption 5 that is necessary for the theoretical analysis of DRSA [28]. The reason is that the adopted variance reduction methods are able to eliminate the effect of stochastic gradient noise. We do not assume homogeneity of regular agents; their local costs can be totally different.

As the network topology plays a critical role in the analysis, we define $A\in{\mathbb{R}}^{R\times|\mathcal{E}_{R}|}$ as the oriented agent-edge incidence matrix of $(\mathcal{R},\mathcal{E}_{R})$. To be specific, for an edge $e=(w,v)\in\mathcal{E}_{R}$ with $w<v$, the $(w,e)$-th entry of $A$ is 1 and the $(v,e)$-th entry of $A$ is $-1$. We review the following lemma.

Since BRAVO-SAGA, BRAVO-LSVRG and DRSA solve the same TV-norm penalized problem (4), they share Lemma 1, which shows that (4) is equivalent to the original problem (2) when the penalty parameter $\lambda$ is sufficiently large. Note that the threshold $\lambda_{0}$ is determined by the heterogeneity of the regular agents’ local costs. Higher heterogeneity leads to larger $\lambda_{0}$. Below we only consider the regime of large $\lambda$ and focus on the convergence to (4).

The next theorem demonstrates that both BRAVO-SAGA and BRAVO-LSVRG can achieve linear convergence, and the learning errors are bounded.

The difference between (15) and (16) comes from the ways of SAGA and LSVRG to correct the stochastic gradients. Thus, we choose different Lyapunov functions $V^{k}$ and derive a unified convergence expression for the two methods. Theorem 1 asserts that BRAVO-SAGA and BRAVO-LSVRG can linearly converge to a neighborhood of the optimal solution $x^{*}$ of (4); the size of the neighborhood is determined by the penalty parameter $\lambda$, the summation of the squared numbers of Byzantine neighbors $\sum_{w\in\mathcal{R}}|\mathcal{B}_{w}|^{2}$, the summation of the squared numbers of regular neighbors $\sum_{w\in\mathcal{R}}|\mathcal{R}_{w}|^{2}$, and the problem dimension $p$.

Next, we show that the learning errors established in Theorem 1 are optimal in order for any subgradient-based method that solves the TV-norm penalized decentralized stochastic optimization problem in (4). The class of such methods satisfy the following assumption.

Such a span condition is standard in analyzing the performance bounds of (stochastic) first-order methods [47, 48]. Methods satisfying Assumption 6 include but are not limited to DRSA, BRAVO-SAGA and BRAVO-LSVRG.

The lower bound on the learning error, as given in (18), is influenced by the heterogeneity across the local costs of regular agents (represented by the penalty parameter $\lambda$) and the impact of Byzantine agents (represented by the term $\sum_{w\in\mathcal{R}}|\mathcal{B}_{w}|^{2}$). Note that the lower bound given in [49] for Byzantine-robust distributed stochastic optimization is also determined by the heterogeneity across the local costs of regular agents and the impact of Byzantine agents.

To further illustrate the benefits of variance reduction to Byzantine-robust decentralized stochastic optimization, we compare the theoretical results with that of DRSA.

Lemma 2 shows that with a constant step size, DRSA can also achieve a linear convergence rate, and the learning error is relative to the summed variance $\sum_{w\in\mathcal{R}}\delta_{w}^{2}$. Comparing the learning errors in Theorem 1 and Lemma 2, we can observe that in BRAVO-SAGA and BRAVO-LSVRG the effect of stochastic gradient noise has been fully eliminated. On the other hand, Lemma 2 also implies that with a diminishing step size, DRSA has a learning error that matches the lower bound in (18), but the convergence rate is sublinear. To the best of our knowledge, the proposed BRAVO-SAGA and BRAVO-LSVRG are the first Byzantine-robust decentralized stochastic optimization methods that achieve stochastic gradient noise-independent learning errors and linear convergence speeds simultaneously.

When Byzantine agents exist, we set their number as $B=20$, unless otherwise specified. We randomly choose $B$ agents to be Byzantine but guarantee the network of regular agents to be connected. We consider the following Byzantine attacks in the numerical experiments.

To further highlight the advantages of BRAVO-SAGA and BRAVO-LSVRG over DRSA, we also compare them on the MNIST and Fashion-MNIST datasets in terms of the convergence error $\|x^{k}-x^{*}\|^{2}$. Since the step sizes of DRSA are different in theory and in practice, we choose three step size rules for DRSA, $\alpha^{k}=0.01/(k+1)$, $\alpha^{k}=0.01/\sqrt{k+1}$ and $\alpha^{k}=0.01$. The attacks are sign-flipping with i.i.d. data where we set $\lambda=0.0001$ and sample-duplicating with non-i.i.d. data where we set $\lambda=0.02$. The experimental results are depicted in Fig. 9. Observe that BRAVO-LSVRG and BRAVO-SAGA, with the help of variance reduction, both achieve faster convergence speeds than DRSA with the diminishing step sizes, and achieve smaller learning errors than DRSA with a constant step size that suffers from the stochastic gradient noise. These experimental results corroborate the theoretical analysis in Section 4 and show the superior performance of BRAVO-SAGA and BRAVO-LSVRG.