WorksComputer Science
Projected Penalty-Gradient Tracking for Communication-Efficient Byzantine-Resilient Federated Learning
Abstract
We investigate communication-efficient federated learning over heterogeneous datasets in the presence of Byzantine adversaries capable of uploading arbitrary information. Penalty-based methods bound the influence of each worker through the bounded gradient of a penalty function; however, the bound is lost once the uploads are compressed, since a Byzantine worker can accumulate an unbounded state at the server. To retain the Byzantine resilience under compressed uploads, we propose a projected penalty-gradient tracking framework, where each honest worker uploads a compressed residual of its penalty gradient and the server projects each reconstructed state onto the known penalty-gradient ball. The framework accommodates any contractive compressor and yields two algorithms: fault-resilient proximal gradient with consistent sparsification (FRPG-CS), whose shared mask is protected by freshly drawn reserve rows, and lazily aggregated FRPG (LAG-FRPG), whose uploads are event-triggered. For smooth and strongly convex losses, we establish a finite-time bound on the expected objective gap, where the Byzantine error floor is independent of the compressor and the compression error decays faster than the optimization error. We also bound the expected number of lazy uploads and derive certificates that separate the finite-penalty model bias from the optimization error. Experiments on MNIST and Fashion-MNIST show that the proposed algorithms attain the highest accuracy among twelve methods under the Min-Max attack, whereas a compressed-momentum benchmark and a local-update benchmark remain preferable in attack-free accuracy and total traffic, respectively.
Introduction
Federated learning (FL) enables a group of workers to learn from decentralized data under the orchestration of a central server, where each worker performs local computation and exchanges only model-related information with the server [1]. When FL is deployed over a large number of heterogeneous devices, it faces two major challenges, namely, Byzantine attacks [2, 3] and the communication bottleneck [4, 5]. Byzantine adversaries may upload arbitrary information to disrupt the learning process, while the frequent upload of high-dimensional vectors over bandwidth-limited uplinks can make the training prohibitively slow.
Current Byzantine-resilient FL algorithms either aggregate the uploaded gradients by robust rules [2, 3, 6, 7, 8] or penalize the disagreement between the local model of each worker and the server model [9, 10]. The penalty-based methods, e.g., robust stochastic aggregation (RSA) [9] and fault-resilient proximal gradient (FRPG) [10], are naturally suited to heterogeneous datasets, since the influence of each worker on the server model is bounded by the gradient of the penalty function.
Combining the penalty-based methods with communication compression is nontrivial. The bound on the penalty gradient holds for the vector that an honest worker computes rather than for the vector that a Byzantine worker uploads. Moreover, communication-efficient algorithms accumulate compressed increments into a persistent state at the server [4, 11, 12]; projecting each received increment is thus insufficient, since the accumulated state of a Byzantine worker can still grow. Therefore, we track the penalty gradients with projected states: each honest worker uploads a compressed residual between its exact penalty gradient and a local copy of its server-side state, while the server projects each accumulated state onto the known penalty-gradient ball. In this way, the state that enters the server update remains bounded regardless of the uploaded payloads.
We focus on smooth and strongly convex losses, which cover -regularized generalized linear models and least-squares estimators, e.g., the logistic regression in a production federated keyboard [13], linear heads on frozen pretrained models [14], parameter estimation from heterogeneous and partly compromised measurements [15], and the state estimation of power grids under false data injection [16]. Strong convexity also makes the learning target unique, such that an error floor in the objective gap bounds how far the Byzantine workers can move the model.
Related Works
Byzantine resilience
Since the seminal work [2], the trimmed mean has been replaced by robust aggregation rules, e.g., Krum [2], coordinate-wise median and trimmed mean [3], Bulyan [6], and geometric median [7]. Their original guarantees rely on concentration, common-distribution, or honest-majority conditions, and cannot be transferred unchanged to heterogeneous datasets. To handle the data heterogeneity, worker momentum with centered clipping [17], bucketing [18], and nearest-neighbor mixing [19] have been developed, while the tight bounds in [20, 21] show that the achievable learning error depends on the heterogeneity model. Other works rely on trusted data or reference gradients at the server [22]–[24]. Meanwhile, the inner-product manipulation (IPM) [25], a-little-is-enough (ALIE) [26], and Min-Max [27] attacks show that the knowledge and the feasible payloads of the adversaries need to be specified. Different from the above methods that minimize the consensus loss of the honest workers, the penalty-based methods allow the local models to differ from the server model (see also [28], [29]). RSA [9] employs the bounded subgradients of a norm penalty and separates the consensus error from the penalty bias, while FRPG and its local variant LFRPG [10] accelerate the penalty-based route via proximal-gradient recursions. Nevertheless, RSA and FRPG upload a dense vector per worker and slot, and the guarantee of FRPG requires the messages of the Byzantine workers to obey the norm bound of the penalty gradient.
b) Communication compression: Sparsification with memory [4] and error feedback [11] correct the bias of contractive compressors, where the residual bound in [11 Lemma 3] scales as with the contraction factor and vanishes at full communication. EF21 [12] tracks a changing vector by compressed differences and provides the tracking recurrence that we build on. In the presence of Byzantine adversaries, compression has been combined with robust aggregation via error feedback [30], gradient-difference compression in BROADCAST [31], Byz-DASHA-PAGE and Byz-EF21 [32], compressed momentum filtering [33], Byz-DM21 [34], coordinated sparse supports in RoSDHB [35], and globally consistent Top- compression in FedAdam-BACK [36]; a common support is also selected by ARC-Top- [37] for All-Reduce compatibility. For the penalty-based methods, C-RSA [38] combines compression with RSA in the non-convex and non-i.i.d. regime. Nevertheless, the tracking of penalty gradients with bounded server-side states has yet to be characterized for the accelerated penalty-based methods.
c) Lazy and event-triggered communication: LAG [5] reuses the outdated gradients of the workers whose gradients change slowly, LASG [39] adapts the triggering rules to stochastic gradients, and LAQ [40] combines lazy uploads with quantization. Event triggering is combined with compression in SPARQ-SGD [41] and analyzed asymptotically for FL in [42], and the communication frequency is also reduced by local updates in ProxSkip [43], LoCoDL [44], and LFRPG [10]. Nevertheless, to the best of our knowledge, lazy uploads have not been analyzed in the presence of Byzantine adversaries.
Our Contributions
Motivated by the above limitations, we develop a communication-efficient penalty-based FL framework whose Byzantine resilience does not degrade with the communication format. Our contributions are as follows.
We propose a projected penalty-gradient tracking framework, where each honest worker uploads a compressed residual of its penalty gradient and the server projects each reconstructed state onto the penalty-gradient ball. The framework accommodates any contractive compressor and bounds the state of each Byzantine worker regardless of the uploaded payloads. In particular, FRPG-CS lets all workers share a mask that combines robustly ranked rows with freshly drawn reserve rows, such that the contraction is guaranteed even when the ranking is manipulated, and LAG-FRPG lets each honest worker upload only when its residual exceeds a decaying threshold.
For smooth and strongly convex losses, we establish a finite-time bound on the expected objective gap without assuming bounded stochastic gradients or an honest majority. The Byzantine error floor is independent of the compressor, while the compression adds an term over slots, whose dependence on the contraction factor cannot be improved in order. For LAG-FRPG, the lazy uploads add an term, and the expected fraction of uploading slots decays as .
We derive computable certificates that separate the finite-penalty model bias from the optimization error for any penalty weight, and evaluate the proposed algorithms against ten benchmarks on the MNIST and Fashion-MNIST datasets.
Organization. The remaining work is organized as follows. The problem description and several preliminaries are introduced in § 2. The algorithmic development and the theoretical results are provided in Sections III and IV, respectively. Numerical results are presented in § 5, which is followed by the concluding remarks in Section VI.
Problem Description and Preliminaries
Penalty-Based Federated Learning
We consider an FL system where a central server orchestrates workers, among which workers are honest and workers are Byzantine. Without loss of generality, we index the honest workers by ; the indexing is only used in the analysis, and the server requires neither the identities of the honest workers nor the value of . Each honest worker holds a local dataset with the local loss , and the server holds a regularizer . With equally weighted workers, the consensus-based FL minimizes
where is the -dimensional model parameter vector. To handle the heterogeneous datasets and bound the influence of each worker, the penalty-based methods [9], [10] assign a local model to each honest worker and a model to the server, and minimize
where , is the penalty weight, and is the penalty function of worker . We denote the minimizer of (2) by , and rely on the following assumptions.
Assumption 1 (Smoothness): For , the function has an -Lipschitz continuous gradient.
Assumption 2 (Strong convexity): For , the function is -strongly convex with .
Assumption 3 (Bounded penalty gradient): For , the penalty function is convex and differentiable with and an -Lipschitz continuous gradient, where .
Assumptions 1 and 2 hold for -regularized generalized linear models and least-squares estimators, where a worker with a rank-deficient local design requires a positive ridge regularization since Assumption 2 is imposed per worker. Assumption 3 is satisfied by the radial Huber penalty
with , , and , which we use for all workers in the sequel. Assumption 3 implies that each honest worker moves the server model through the penalty gradient , whose norm never exceeds .
Threat Model
The Byzantine workers can collude, know the algorithm, observe the messages and the current vectors of the honest workers, and upload arbitrary finite real-valued vectors, where a missing upload is replaced by zero. The server is trusted, i.e., it follows the protocol, accepts only the coordinates permitted by the announced communication format, and rejects malformed messages. The identities of the workers are fixed, and the links between the honest workers and the server are synchronous and reliable, such that each honest worker and the server keep identical copies of the state of that worker; packet loss without state reconciliation is beyond the scope of this work. Moreover, the randomness drawn by the server is independent of the history, i.e., the Byzantine workers can react to an announced mask but cannot predict it when committing their earlier reports.
Finite-Penalty Target and Consensus Certificates
For a finite penalty weight , the server optimum of (2) generally differs from the consensus optimum in (1). In fact, minimizes the profiled loss , to which each worker contributes a gradient with norm at most (cf. Appendix A); hence, the bounded influence of each worker comes with a model bias. Let denote the Euclidean projection onto the ball with radius , , and . The model bias is quantified in the following lemma, whose proof is deferred to Appendix A.
Lemma 1 (Unconditional consensus certificates): Suppose Assumptions 1–3 are satisfied. For any , let with being the gradient of with respect to . Then, we have
and
Moreover, let and . For the Huber penalty (3) with any , the server optimum satisfies
The inequalities (4) and (5) certify the distance and the objective gap between any server model and the consensus optimum; evaluated at an approximate minimizer of , the certificate (4) holds for after adding to its right-hand side (RHS). Since the certificates use the full-data quantities of the honest workers, they serve as offline diagnostics rather than information available to the server.
Remark 1 (Penalty weight and model bias): When , the penalized optimum lies in the quadratic region of the Huber penalty, and the sharper bound holds (cf. Appendix A). However, such a condition fails in general and can lead to configurations with the Dirichlet concentration 0.3 in § 5-E, whereas (6) holds for any and . If , we have and the model bias vanishes with ; otherwise, reducing alone cannot remove the model bias in general. Meanwhile, a larger raises the Byzantine error floor (cf. Theorem 1), which reveals a tradeoff between the model bias and the Byzantine resilience.
Projected Penalty-Gradient Tracking
In this section, we develop the projected penalty-gradient tracking framework based on the FRPG recursions [10], and specify the communication formats of the FRPG-CS and LAG-FRPG algorithms.
Projected Tracking Framework
Per slot , the server and the honest workers perform the FRPG recursions with the stepsizes
and
More specifically, the server updates
where aggregates the states that the server maintains for all workers. After receiving , each honest worker samples a mini-batch from and updates
where is the stochastic gradient, is the proximal operator, and
Algorithm 1 Projected Penalty-Gradient Tracking
Require: stepsizes and ; penalty weight ; communication format; number of slots .
Server and honest workers initialize , , and
for do
Server computes and via (9a) and (9b), and broadcasts to all workers
Each honest worker samples and computes , , , and via (10) and (11)
if FRPG-CS then
Each worker uploads its row energies; server clips them via (14), selects by trimmed means, draws the reserve , and broadcasts
Each honest worker uploads via (15)
else if LAG-FRPG then
Each honest worker uploads via (17)
else
Each honest worker uploads and the required support information
end if
Server updates the states of all workers via (12), and each honest worker applies the same update to its copy
Server computes via (9c)
end for
return
are the penalty gradient of worker and its residual with respect to the state that the server maintains for worker . Note that (10c) uses the exact penalty gradient , which is locally available regardless of the uploaded information.
Different from FRPG, where each worker uploads per slot, each honest worker in the proposed framework uploads a compressed version of the residual and keeps an identical copy of its state. After receiving , the server updates the state of each worker as
with , while the local models are not projected. The projection in (12) plays two roles. For an honest worker, it cannot increase the tracking error , since belongs to the ball with radius under Assumption 3. For a Byzantine worker, the state obeys the same norm bound regardless of the uploaded payloads. The detailed procedures are summarized in Algorithm 1, where the models and are initialized at deterministic finite vectors.
Contractive Compressors
Let with being the compressor of worker per slot , and let denote the history that fixes the residuals of the honest workers and precedes the fresh randomness of the compressors. The proposed framework requires each honest worker to use a contractive compressor, i.e.,
where is the contraction factor. The compressor may vary with the history, and no independence among the workers is required.
To specify the compressors, we zero-pad and partition each -dimensional vector into rows of length . For an integer , keeping the rows with the largest energy of each residual (individual top- rows) and keeping uniformly sampled rows that are shared by all workers both satisfy (13) with . The former requires each worker to upload the indices of its rows, the latter requires the server to broadcast a mask, and the full model upload corresponds to . Note that each honest worker mirrors the entire projected state in (12), since the projection may rescale the coordinates outside the transmitted support.
Consistent Sparsification (FRPG-CS)
The FRPG-CS algorithm lets all workers share a data-dependent mask, which combines robustly ranked rows with freshly drawn reserve rows since the ranking can be manipulated by the Byzantine workers. Based on the row partition, each honest worker first uploads the row energies with being the -th row of , . Since the residual of an honest worker satisfies , the server clips each report as
where denotes the entry-wise positive part. For each row, the server computes a trimmed mean of the clipped reports with entries removed from each tail, where . The rows with the highest scores form the set with index-based tie breaking. After the reports are fixed, the server selects rows uniformly without replacement from the complement of to form the reserve set . The mask and the upload of each honest worker are
where keeps the rows in and sets the remaining rows to zero. Hence, each honest worker uploads scalars per slot, and the mask is broadcast on the downlink.
Let denote the history that includes the current residuals of the honest workers and all energy reports, but excludes the fresh reserve and the subsequent payloads. Since and are fixed given , we have
i.e., FRPG-CS satisfies (13) with . The contraction is supplied by the reserve rather than by the trimmed mean; hence, (16) remains valid even when the Byzantine workers manipulate all ranking decisions, and the analysis requires neither nor an honest majority, although the numerical tests set . Note that the reserve is necessary, since the shared top rows alone provide no uniform contraction: when the reports of the other workers rank the first row at the top while the residual of an honest worker is supported on the second row, selecting only the first row leaves the tracking error of that worker untouched.
Lazy Uploads (LAG-FRPG)
The LAG-FRPG algorithm keeps the same recursions and state updates, but lets each honest worker upload the full residual only when the residual is large, i.e.,
with the threshold
An upload of honest worker resets its state to , while an inactive worker sends no vector and the server interprets the absence as a zero increment. Therefore, the tracking error of each honest worker satisfies the deterministic bound
Note that the server still broadcasts the model and each honest worker still evaluates a stochastic gradient per slot; hence, the lazy uploads reduce the uplink traffic rather than the downlink traffic or the oracle calls.
Convergence Analysis
Preliminary Results
Let denote the -field generated by the history before the stochastic gradients of the honest workers are sampled in slot , such that the points are -measurable. The noise of the stochastic gradient of honest worker is
Assumption 4 (Stochastic gradient noise): The noise satisfies and for .
Assumption 4 bounds the variance of the noise rather than the stochastic gradients, and holds for the ridge-regularized softmax regression in Section V with bounded input features, since the ridge term cancels in (20). Analogous to (20), we define the deviation of the aggregated state from the sum of the penalty gradients of the honest workers as
where collects the states of the Byzantine workers and is the tracking error of the honest workers. Based on the projection in (12), we have for each sample path
Different from the noise in (20), the deviation can be biased and can depend on the current samples of the honest workers. We measure the learning error by the expected objective gap with . In the sequel, Assumptions 1–4 are satisfied, the stepsizes follow (7) and (8), all constants are independent of the horizon , and all proofs are deferred to the appendices.
Lemma 2 (One-step recursion): For any , let
Then, we have
Lemma 2 extends the one-step analysis of FRPG [10] to an arbitrary deviation : since the noise is only cancelled against the -measurable , neither the unbiasedness of nor its independence of the current samples is required, and the result remains valid under adaptive attacks.
Lemma 3 (Stability): There exist finite constants given in (41) such that
for and $k\ge 0.
Lemma 4 (Penalty-gradient drift): With , there exist finite constants given in (43) such that
Lemma 3 follows from (23) with the coarse bound implied by (22); hence, the stability holds for any communication format and is not assumed by the analysis of the tracking error. Lemma 4 shows that the penalty gradients are slowly varying signals, since the models move by per slot and the Lipschitz continuity of transfers the movement to .
Lemma 5 (Bounded-state tracking): Suppose (13) is satisfied. Let and
For , the tracking error of honest worker satisfies
In particular, , and for .
The proof of Lemma 5 specializes the tracking recurrence of EF21 [12 Suppl., Lemma 2] to the drift in Lemma 4, and combines it with the cap implied by the bounded states in (12), which handles the first slots. The inverse-quadratic dependence of on the contraction factor agrees with that of error feedback [11], and cannot be improved uniformly over the bounded signals with the drift (25) and the contractive compressors (cf. Lemma 6 in Appendix D).
Main Results
Based on Lemmas 2–5, we are ready to establish the convergence of the proposed framework with the constants
Theorem 1. Suppose Assumptions 1–4 are satisfied and the stepsizes follow (7) and (8). For any fixed and , the proposed framework achieves
where
When the compressor of each honest worker satisfies (13), we have
where .
Theorem 1 applies to FRPG-CS with as well as to the individual and uniform sparsification with . The RHS of (30) consists of the optimization error, the Byzantine error floor, and the compression error. The optimization error decays as , where depends on the initialization and collects the impacts of the bounded states and the stochastic gradient noise; when , converges to zero at the rate of .
The Byzantine error floor is obtained by taking the limit of the horizon for a fixed and then the infimum over , i.e.,
Note that the finite-time bound (30) holds for each fixed and is not uniform as . The floor in (32) is independent of the compressor, i.e., the compression does not degrade the Byzantine resilience of the penalty-based method. Moreover, the floor grows with and without requiring an honest majority; hence, a smaller penalty weight improves the Byzantine resilience at the expense of a larger model bias (cf. Remark 1).
The compression error decays as , which is faster than the optimization error, and depends on the compressors only through the constants that scale as and vanish at full communication. Therefore, a smaller contraction factor reduces the uplink traffic per slot at the expense of a larger constant of a higher-order term.
Since Theorem 1 bounds the expected objective gap of (2), the strong convexity implies . Together with Lemma 1, the distance to the consensus optimum is separated into the algorithmic error and the model bias as
where the second term on the RHS is not removed by the convergence of the algorithm.
Theorem 2. Under the conditions of Theorem 1, the LAG-FRPG algorithm with the threshold (18) achieves (30) with
Consequently, the Byzantine error floor (32) also holds for LAG-FRPG.
Theorem 2 follows from the deterministic bound (19), which gives . The lazy uploads add an term that is dominated by the optimization error, while the Byzantine error floor remains unchanged. The number of uploads is characterized in the following corollary.
Corollary 1 (Number of lazy uploads). Let denote the number of uploads of honest worker during slots , where indicates an upload in slot . Under the conditions of Theorem 1, for any positive and nondecreasing thresholds with , we have
In particular, the threshold (18) yields
where and .
Corollary 1 shows that the expected fraction of uploading slots of LAG-FRPG decays as . The proof relies on the normalized tracking error , which is summed along each sample path before taking the expectation; compared with the bound that only uses the final threshold and the total path length of the penalty gradients, such an argument removes a logarithmic factor. Note that the threshold controls the tradeoff between the tracking accuracy and the upload frequency, e.g., the alternative threshold reduces the additional objective error to , while the expected fraction of uploading slots only vanishes as (cf. Appendix F).
Numerical Results
Experimental Setup
Datasets and Models
We evaluate the proposed algorithms on the MNIST [45] and Fashion-MNIST [46] datasets with the ten-class linear softmax regression, which has parameters with a constant input feature representing the bias. All parameters of the honest workers are regularized by a ridge term with weight , and the server regularizer is a ridge term with weight ; hence, Assumptions 1 and 2 are satisfied.
2) Federated Settings: We set honest workers and add Byzantine workers unless otherwise specified, without changing the data of the honest workers. A fixed stratified split of the training set yields 50,000 training and 10,000 validation examples, and the 10,000 test examples are only used for testing. The training examples are partitioned among the honest workers by a label-Dirichlet distribution with concentration , where a partition is redrawn when a worker receives fewer than 100 examples. For each seed, all methods share the same partition and mini-batch indices with 32 examples sampled with replacement per worker and slot. All methods start from the zero model and run for 2,000 oracle slots in double precision, where each local step of LFRPG is counted as one slot, i.e., each run consumes 640,000 sample-gradient evaluations.
We report three sets of runs. The main comparison uses 20 seeds (100–119) in the attack-free and Min-Max scenarios. An exploratory study uses five seeds (0–4) over eight scenarios, including the IPM, ALIE, and Gaussian-noise attacks, , and , together with the ablations in § 5-D; since the main comparison was designed after inspecting the exploratory study, the two seed sets are reported separately. A controlled study fixes , eight transmitted rows, and with all 60,000 training examples for the diagnostics in § 5-D and V-E.
3) Benchmarks: We compare FRPG-CS and LAG-FRPG with ten benchmarks, all of which are implemented by ourselves: FRPG and LFRPG with frame length [10], projected FRPG (i.e., the proposed framework with full uploads), -norm RSA [9], trimmed mean and coordinate-wise median [3], Krum [2], geometric median [7], Byz-EF21-SGDM [33], and FedAdam-BACK [36]. The implementation details of the benchmarks are provided in Appendix § 13.
4) Hyperparameter Tuning Protocol: For a fair comparison, each method receives six candidate configurations, which are scored by the mean validation cross-entropy after 1,000 slots over the attack-free, IPM, and ALIE scenarios with the calibration seed 9001. The selected configurations are frozen before the evaluation; hence, the Min-Max and Gaussian-noise attacks, the alternative concentrations, and the case of are not used for tuning. The tuning selects with , , and for FRPG-CS, for LAG-FRPG, for projected FRPG, and for FRPG and LFRPG. Since the selected configurations optimize different finite-penalty objectives and several selected values lie on the boundary of the candidate grids, we complement the main comparison with a matched-objective comparison in § 5-C and the ablations in § 5-D.
5) Malicious Attacks: The Byzantine workers collude and observe the vectors that the considered protocol aggregates from the honest workers, i.e., the penalty gradients, the (reconstructed) momentum, or the loss gradients, with the mean . They submit in the IPM attack [25], with being the coordinate-wise standard deviation of the honest vectors in the ALIE-type attack [26], and a Gaussian vector whose norm is ten times the root-mean-square norm of the honest vectors in the Gaussian-noise attack. In the Min-Max attack [27], they submit with the largest that satisfies
where a fixed unit direction replaces when . For the protocols with states, the targets are converted into increments in the admissible sparse format, and the Byzantine workers in FRPG-CS additionally forge the energy reports on the rows with low honest energy before the reserve is revealed. Since the feasible payloads differ across the protocols, the attacks share the same information access but not necessarily the same strength for all methods. Note that the IPM and Gaussian-noise payloads exceed the norm bound required by FRPG and LFRPG; hence, the degradation of FRPG and LFRPG under such attacks does not contradict the guarantees in [10].
6) Performance Metrics: We report the test accuracy at 2,000 slots and at the budget endpoints, i.e., the last models before the uplink traffic averaged over the honest workers exceeds 1, 4, or 8 MiB, where the traffic counts 64-bit scalars and 32-bit indices including the energy reports, the masks, and the model downloads per recipient. The methods are compared by paired -tests across the seeds with the Holm correction, and the reported intervals are marginal 95% confidence intervals conditional on the fixed test images.
Performance Comparison
Table I summarizes the test accuracy in the main comparison. Under the Min-Max attack, FRPG-CS and LAG-FRPG achieve the highest and the second-highest accuracy on both datasets at 2,000 slots as well as under the 8-MiB uplink budget. Compared with the best benchmark at 2,000 slots, i.e., projected FRPG on MNIST and geometric median on Fashion-MNIST, FRPG-CS improves the accuracy by 2.49 (95% confidence interval [2.04, 2.93]) and 3.70 ([2.63, 4.77]) percentage points, respectively, and LAG-FRPG by 1.93 ([1.51, 2.34]) and 2.34 ([1.19, 3.49]) percentage points, respectively, where the Holm-adjusted two-sided -values are below 0.001 except for the last one (0.006). More generally, among the 160 paired contrasts between the two proposed algorithms and the ten benchmarks over two datasets, two scenarios, and two endpoints, each proposed algorithm outperforms each benchmark in all 40 Min-Max contrasts after the correction; note that such contrasts are not independent replications. In the attack-free scenario, Byz-EF21-SGDM achieves the highest accuracy on both datasets, i.e., 89.65% and 80.75%, and outperforms both proposed algorithms.
| Method | M: Clean | M: Min-Max | M: 8 MiB | F: Clean | F: Min-Max | F: 8 MiB |
| FRPG-CS (ours) | ||||||
| LAG-FRPG (ours) | ||||||
| FRPG | ||||||
| Projected FRPG | ||||||
| LFRPG | ||||||
| -RSA | ||||||
| Trimmed mean | ||||||
| Coord. median | ||||||
| Krum | ||||||
| Geometric median | ||||||
| Byz-EF21-SGDM | ||||||
| FedAdam-BACK |
Table I. Test accuracy (%, mean standard deviation over 20 seeds) with and . Clean and Min-Max: 2,000 slots; 8 MiB: Min-Max scenario under the budget of 8 MiB on the mean uplink traffic of the honest workers. M: MNIST; F: Fashion-MNIST. Bold: highest mean per column.
Fig. 1 shows the test cross-entropy versus the number of oracle slots, which is a common predictive metric rather than the training objective of each method or the objective gap in Theorem 1. All methods start from the zero model with the test cross-entropy of . Under the Min-Max attack, LAG-FRPG has a lower mean loss than FRPG-CS at slot 500 on both datasets but a higher mean loss at slot 2,000, while Byz-EF21-SGDM attains the lowest final mean loss in the attack-free scenario.
Figure 1. Test cross-entropy (log scale) versus oracle slots for all twelve methods in the attack-free and Min-Max () scenarios. Lines and shaded regions show the means and the pointwise 95% confidence intervals over 20 seeds.
Comparison of Communication Formats
To remove the confound of different finite-penalty objectives, we fix , , the stepsizes, the partitions, and the mini-batch streams, and compare four communication formats of the proposed framework: the full upload, the shared mask of FRPG-CS with and , the individual top-16 rows, and 16 uniformly sampled common rows. The 320 runs cover both datasets, the attack-free and Min-Max scenarios, and the seeds 100–119 without retuning; since they reuse the partitions and the test sets of the main comparison, they do not serve as an independent confirmation.
Table II summarizes the test accuracy, where the 24 contrasts between the shared mask and the other three formats form the family for the Holm correction. Under the Min-
| Method | M: Clean | M: Min-Max | M: 8 MiB | F: Clean | F: Min-Max | F: 8 MiB |
| Projected full | 88.72 ± 0.63 | 85.98 ± 1.56 | 85.50 ± 1.66 | 78.55 ± 1.09 | 73.99 ± 1.80 | 72.02 ± 1.90 |
| Shared reserve | 88.60 ± 0.57 | 88.46 ± 0.66 | 88.43 ± 0.82 | 78.48 ± 1.11 | 78.38 ± 1.09 | 78.07 ± 1.06 |
| Individual top | 88.68 ± 0.61 | 87.28 ± 1.29 | 88.11 ± 0.84 | 78.62 ± 0.92 | 78.28 ± 1.04 | 78.18 ± 1.07 |
| Uniform common | 88.32 ± 0.68 | 88.29 ± 0.70 | 88.07 ± 0.76 | 78.14 ± 1.19 | 78.11 ± 1.22 | 77.74 ± 1.25 |
Table II. Test accuracy (%, mean ± standard deviation over 20 seeds) of four communication formats with the matched objective (, , and 16 rows for the sparse formats). The columns are defined as in Table I. Bold: highest mean per column.
Max attack, the shared mask outperforms the full upload on both datasets at both endpoints. Compared with the individual top rows on MNIST, the shared mask improves the accuracy by 1.18 percentage points at 2,000 slots (95% confidence interval [0.85, 1.51], adjusted ) and by 0.32 percentage points under the 8-MiB budget (), while the corresponding contrasts on Fashion-MNIST remain unresolved. Compared with the uniformly sampled common rows, the two contrasts at 2,000 slots under the Min-Max attack remain unresolved, while the contrast under the 8-MiB budget on MNIST favors the shared mask by 0.36 percentage points (). In the attack-free scenario, the contrasts with the full upload and the individual top rows are all unresolved, with slightly lower means for the shared mask.
Hence, the shared mask has conditional rather than uniform advantages over the simpler formats, all of which are covered by Theorem 1.
At 2,000 slots, the mean uplink traffic per honest worker is 119.78 MiB for the full upload, 14.60 MiB for the shared mask, 12.33 MiB for the individual top rows, and 12.21 MiB for the uniformly sampled common rows, including the energy reports of the shared mask and the indices of the individual top rows. In terms of the common objective (2), the individual top rows attain a lower mean value than the shared mask on Fashion-MNIST under the Min-Max attack (6.204 versus 6.333) despite the slightly lower mean accuracy (cf. Table V in Appendix § 13).
| Method | M: Clean | M: Min-Max | F: Clean | F: Min-Max |
| Projected full | 6.188 0.132 | 6.770 0.132 | 6.069 0.289 | 6.587 0.281 |
| Shared reserve | 6.465 0.166 | 6.396 0.167 | 6.393 0.310 | 6.333 0.312 |
| Individual top | 6.236 0.140 | 6.557 0.133 | 6.271 0.308 | 6.204 0.306 |
| Uniform common | 7.279 0.296 | 7.148 0.308 | 7.085 0.366 | 7.106 0.341 |
Table V. Final value of the common objective (2) at 2,000 slots in the matched-objective comparison (mean standard deviation over 20 seeds). Bold: lowest mean per column.
Communication Overhead and Ablation Studies
Communication Overhead
With the selected configuration, FRPG-CS uploads 157 + 16 × 50 = 957 scalars per honest worker and slot, i.e., 12.19% of the dense vector with 7,850 entries, such that its uplink traffic over 2,000 slots is 14.60 MiB compared with 119.78 MiB for the full upload. Since the server broadcasts the model per slot, the total traffic of FRPG-CS including the downlink is 134.51 MiB per honest worker. In contrast, LFRPG requires 11.98 MiB in total at the expense of a lower accuracy under the Min-Max attack, and Byz-EF21-SGDM and FedAdam-BACK also have a smaller total traffic than the proposed algorithms. Moreover, under the strict 1-MiB uplink budget on Fashion-MNIST, LAG-FRPG trails LFRPG and several compressed benchmarks; hence, the advantage of the proposed algorithms depends on the available communication resources.
Mechanism Ablation
Table III shows the ablations of the exploratory study, where each ablation inherits the selected hyperparameters and the communication format of its parent. Without the error feedback, i.e., when the honest workers upload the masked penalty gradients and the server overwrites the states, the accuracy of FRPG-CS drops to 60.02% and 36.88% under the IPM attack and to 35.95% and 12.54%
| Method | M: IPM | M: Min-Max | F: IPM | F: Min-Max |
| FRPG-CS | 86.95 ± 1.70 | 86.82 ± 1.74 | 79.25 ± 1.05 | 79.35 ± 1.03 |
| CS: no EF | 60.02 ± 5.16 | 35.95 ± 3.19 | 36.88 ± 5.09 | 12.54 ± 2.51 |
| CS: no reserve | 85.62 ± 2.57 | 83.14 ± 3.88 | 78.95 ± 0.99 | 78.96 ± 0.93 |
| CS: no projection | 2.97 ± 3.07 | 86.85 ± 1.72 | 6.74 ± 3.32 | 79.30 ± 1.02 |
| LAG-FRPG | 85.84 ± 1.84 | 86.10 ± 1.68 | 78.00 ± 0.99 | 78.29 ± 0.82 |
| LAG: no projection | 3.48 ± 4.35 | 86.09 ± 1.67 | 4.31 ± 4.88 | 78.30 ± 0.81 |
Table III. Ablation study: test accuracy (%, mean ± standard deviation over five seeds) at 2,000 slots with and . EF: error feedback. Bold: highest mean per column.
under the Min-Max attack. Without the projection in (12), both proposed algorithms fail under the IPM attack with its large payloads, while the projection has little effect under the Min-Max attack. Without the reserve rows, i.e., when all 16 rows are selected by the ranking, the mean accuracy of FRPG-CS decreases in all four cases, e.g., by 3.68 percentage points on MNIST under the Min-Max attack. Hence, the ablations support the roles of the residual feedback and the projection in the tested scenarios, although they do not imply that each component improves the accuracy under every attack.
Objective Gap and Upload Frequency
In the controlled study, where the minimizer of (2) is computed with a certified objective error below , FRPG-CS under two sign-flipping Byzantine workers attains a higher accuracy of the server model but a larger final objective gap than the full upload on both datasets; hence, a higher accuracy does not imply a smaller objective gap. Moreover, the individual top rows with eight rows attain an accuracy comparable to that of the shared mask with a smaller uplink traffic (cf. Appendix § 13); therefore, we do not claim that the shared mask outperforms the individual sparsification in general. Finally, ten runs of LAG-FRPG over 20,000 slots upload in 8.08% and 11.36% of the slots in the final window on the two datasets, compared with the cumulative fractions of 21.82% and 26.97%, respectively, which agrees with the decreasing upload activity in Corollary 1.
Finite-Penalty Model Bias
We evaluate the certificates in Lemma 1 on the 20 reference problems of the controlled study, i.e., two datasets, , and five seeds, with and . The consensus optimum and the penalized optimum are computed from the full data of the honest workers, where the numerical errors are bounded by the strong-convexity residuals with the largest half-width of the distance intervals being . Table IV reports the interval that encloses the exact distance of all five seeds, which is deterministic rather than a confidence interval, together with the largest upper bound from the gradient certificate (4).
| Data, | Distance enclosure | Max. bound |
| M, 0.3 | [0.339, 0.621] | 12.574 |
| M, 10 | [0.023, 0.035] | 0.377 |
| F, 0.3 | [0.531, 0.945] | 37.980 |
| F, 10 | [0.027, 0.050] | 1.198 |
Table IV. Model bias with and : enclosure of the exact values over five seeds and the largest upper bound from (4). Bold: smallest values per dataset.
With , the model bias is appreciable, i.e., between 0.339 and 0.621 on MNIST and between 0.531 and 0.945 on Fashion-MNIST, while it is one order of magnitude smaller with . The threshold ranges from 1.047 to 1.683 on MNIST and from 2.088 to 4.536 on Fashion-MNIST with , which exceeds ; hence, in (6), and the positive bias is confirmed by the enclosures. Raising the penalty weight would raise the Byzantine error floor in (36), which agrees with the tradeoff in Remark 1. The source code, the configurations, and the raw results of all 3,012 runs are provided in the supplementary archive (cf. Appendix § 13).
Concluding Remarks
We have proposed a projected penalty-gradient tracking framework for communication-efficient and Byzantine-resilient FL over heterogeneous datasets, and developed the FRPG-CS algorithm with a reserve-protected shared mask and the LAG-FRPG algorithm with event-triggered uploads. For smooth and strongly convex losses, we have established a finite-time bound on the expected objective gap, where the Byzantine error floor is independent of the compressor, the compression error decays as with a tight dependence on the contraction factor, and the expected fraction of lazy uploads decays as ; we have also derived unconditional certificates that separate the finite-penalty model bias from the optimization error. Numerical results on MNIST and Fashion-MNIST have shown that FRPG-CS and LAG-FRPG outperform ten benchmarks under the Min-Max attack, although Byz-EF21-SGDM attains a higher attack-free accuracy and LFRPG requires a smaller total traffic. Since our analysis requires strongly convex losses, a trusted server, and reliable links, and our evaluation is limited to linear models on two image datasets, future work will extend the framework to non-convex losses and downlink compression, and validate it on larger models and stronger protocol-specific attacks.
Proof of Lemma 1
Since the penalty gradients enter the gradients of with respect to and with opposite signs, we have
Therefore,
whose norm is bounded by under Assumption 1. The strong monotonicity of gives (4), and minimizing both sides of over gives (5). For an approximate minimizer of , the strong convexity of yields , and the triangle inequality gives the certificate stated after Lemma 1. Moreover, the strong convexity of in yields , and Minkowski’s inequality in proves (37).
To prove (6), let denote the function obtained by replacing each Huber penalty in with the Euclidean norm. Let denote the minimizer of , and let . We use the block norm . At , we choose the subgradients of the norm penalties, such that a subgradient of at has the blocks and the dual norm , where the first block follows from . The strong monotonicity of and the weighted Cauchy–Schwarz inequality imply . Since the Huber penalty satisfies , the optimality of for gives , and the strong convexity of yields . The triangle inequality and prove (6). When only a numerical consensus solution is available, is replaced by the dual norm of the subgradients with the blocks and , and is added to the RHS of (6), which is fully computable.
Profiled Loss
Eliminating the local models from (2) gives the profiled loss
The inner minimizer exists and is unique by the strong convexity and the coercivity in , the partial minimization preserves the convexity, and the envelope formula gives with the norm of at most . Hence, is -strongly convex with the unique minimizer , i.e., the finite-penalty target is a profiled loss with bounded gradient contributions of the workers.
Conditional Bound in Remark 1
If , the stationarity implies and hence . Summing the stationarity conditions gives , and the strong monotonicity of yields the bound in Remark 1. The condition can fail: for , , and , the penalized optimum is for any , whereas .
Proof of Lemma 2
In Appendices B–F, the initialization is deterministic and finite, all messages are finite real vectors, and the constants are only used in the analysis and need not be known to the algorithm. In this appendix, we abbreviate and by and , and let and for . Based on (10) and the optimality condition of the proximal operator in (13), we have for . For any comparison point , the smoothness and the strong convexity in Assumptions 1 and 2 give
where the second inequality is obtained by starting from , applying the smoothness upper bound to , and using ; the first inequality is obtained similarly by adding and subtracting and using . Moreover, the convexity of the penalty function gives
Let , for , and
Summing the above inequalities over the server and the honest workers, the penalty gradients of the honest workers cancel, and we obtain
where is the deviation in (25).
The updates (11) and (14) imply that minimizes the quadratic function . After discarding , the optimality of gives
We apply (42) at together with the above inequality at , apply (42) at with its negative strong-convexity terms discarded, and take the convex combination of the two results with the weights and . Since , the term involving becomes
and the remaining linear term is . For , the remaining linear term is bounded by . For , the first summand is replaced by based on . The squared increments cancel the corresponding negative quadratic terms. For the deviation of the server, we use
Finally, completing the squares in gives
Collecting the above steps, the RHS of (27) holds for each sample path with replaced by and with the additional term . The second moments of all iterates are finite by induction, since the smooth gradients have at most linear growth, the proximal operator is nonexpansive, the noise has bounded second moments, and the projected states are bounded. Hence, the additional term has zero expectation by conditioning on under Assumption 4. Since neither the unbiasedness of nor its independence of the current samples is used, taking the expectation completes the proof.
Proofs of Lemmas 3 and 4
Proof of Lemma 3
Let and , and let denote the sum of the last four terms on the RHS of (27) divided by . Since and , dividing (27) by and summing over give
Indeed, the interior coefficients of are for the server and for the honest workers, all of which are nonpositive, and the initial terms are bounded by in (32) since . Substituting the stepsizes (7) and (8), we have , , and , which yield
Based on (26), we have and . With
we therefore obtain
Using and , we have , and the strong convexity gives . Let and for , such that . Hence, Lemma 3 holds with
The same bounds hold at , since and . Note that the above argument bounds the second moments of the iterates without assuming bounded stochastic gradients or bounded sample paths.
Proof of Lemma 4
With and for , the updates imply
Lemma 3 gives and . At the penalized optimum, we have and . Consequently, with
where the bound for the honest workers uses without assuming the independence of and . Using , we obtain
The Lipschitz continuity of and the inequality yield (29) with
Proof of Lemma 5 and Tightness of Its Contraction Dependence
Proof of Lemma 5
We fix an honest worker , write and , and omit the index . Since both and belong to the ball with radius , the nonexpansiveness of the projection and the contraction (17) imply the uniform cap for . For , we follow the tracking recurrence of EF21 [12 Suppl., Lemma 2]: since the projection is nonexpansive with respect to , applying Young’s inequality with the parameter to and using Lemma 4, we obtain
For , the uniform cap proves (27). For , the inductive hypothesis and give
and the second term of the recurrence is absorbed since . For , the contraction makes the state of the honest worker exact per slot, which proves the result separately. Since , the simplified bound on follows.
Tightness of the Contraction Dependence
The following lemma shows that the order in Lemma 5 cannot be improved uniformly over the bounded signals that satisfy the drift bound (29) and the compressors that satisfy (17); note that it does not provide a lower bound on the trajectories generated by a specific algorithm.
Lemma 6 (Tightness of the contraction dependence). Consider the one-dimensional signal with , which satisfies (29) with , and the compressor that uploads the full residual with probability independently per slot. The tracking error satisfies
To prove Lemma 6, note that and . The compressor uploads with probability and zero otherwise, which satisfies (17) with the contraction factor ; the projection is inactive, since each state is either zero or a previous value of the signal. With , the most recent upload has the age with probability , and no upload has occurred with probability . Hence, we have
For each fixed , we have , whose magnitude is at most for ; the contribution of the ages is bounded by a constant times and tends to zero. The dominated convergence with the summable geometric weights therefore gives
Since the cosine tends to one along the integer subsequence nearest to , , the limit superior is for , and the tracking error is zero for .
Proofs of Theorems 1 and 2
Proof of Theorem 1
For any , the decomposition and the bounds in (22) imply
Therefore, the RHS of (40) is at most
Substituting the above bound into (39), discarding the non-negative distance terms, using , and multiplying both sides by , we obtain (30) with
Based on Lemma 5 and Minkowski’s inequality in , we have , which proves (31) together with . Fixing before taking and then taking the infimum over give (32).
Proof of Theorem 2
Based on (19), we have for each sample path. The proof of Theorem 1 holds unchanged up to the definition of , and the threshold (18) gives
To bound the sum over , we compare it with . For , the derivative of is at least ; moreover, , and the finitely many integers satisfy the same bound directly. Consequently, we have , which yields (34).
Proof of Corollary 1
Let denote the normalized tracking error of honest worker . An upload resets the tracking error to zero, and a skipped upload ensures . Based on the trigger rule (17) and the triangle inequality, we have
for , and regardless of the initial residual. Summing over and dropping give (35) for each sample path with in place of , and taking expectation with Jensen’s inequality and Lemma 4 proves (35). Note that neither independence nor conditioning on stopping times is needed.
For the threshold (18), we have for , since decreases for . Moreover, we have , , and . Substituting these bounds into (35) proves (36).
For the alternative threshold discussed after Corollary 1, i.e.,
we have
Indeed, decreases for and obeys the same bound on , such that proves (47); moreover, together with and the definition of proves (48). Hence, the expected fraction of uploading slots vanishes as , and the additional objective error is .
Implementation Details
Implementation Conventions: The proximal operator of the Huber penalty is when , and otherwise. A valid smoothness constant of the softmax regression is with being the feature vector of sample , since the covariance of the class probabilities has a spectral norm of
at most . The benchmarks that aggregate loss gradients use the ridge weight , which matches the consensus problem (1) normalized by . The honest workers use the exact penalty gradient in (10c), including the slots with compressed or skipped uploads. LFRPG uses a frame of local steps, the iterate of the corresponding slot in the previous frame, the current local auxiliary iterate, and the average penalty gradient of the frame; the communication occurs once per frame, and each local step is charged as an oracle slot. FRPG and LFRPG are implemented without the projection at the server. RSA uses the Euclidean norm penalty with the zero subgradient at coincidence and a stepsize that decays as . The robust aggregation rules use a local exponential moving average with the momentum of zero or selected by validation. Krum scores the nearest vectors of the other workers, and the trimmed mean removes entries per coordinate tail. The geometric median uses the smoothed Weiszfeld iterations with the distance floor , the relative tolerance , and at most 30 iterations. Byz-EF21-SGDM [33] initializes a full stochastic gradient estimate, which is charged on the uplink, uses the top-400 momentum residuals and the trimmed mean of the persistent states, and omits only the unused gradient evaluation after its last reported model. FedAdam-BACK uses a Gaussian projection of rank one and eight rows, zero-fills the selected coordinates into fixed-dimensional moments, and selects the workers from the projections with the nearest neighbors; it applies the bias correction to the second moment only, and the offset of its denominator is .
Protocol and Reproduction
The reserve rows are drawn by a pseudorandom generator, which does not provide a cryptographic guarantee of unpredictability. The split seed is 20261103, the calibration seed is 9001, the seeds of the exploratory study are 0–4, and the seeds of the main comparison are 100–119. The candidates of each benchmark vary the penalty parameters, the learning rate, the momentum, the compression budget, or the local frame as appropriate; hence, the tuning provides the same number of candidates rather than equally expressive search spaces. A budget endpoint is the last model before the next communication would exceed the cap on the uploaded bytes averaged over the honest workers, under the common ceiling of 2,000 slots; a lazy worker can individually exceed the average. The traffic counts the numerical content and the indices, where the controlled study uses 8-bit row indices; headers, retransmissions, and latency are not modeled. The supplementary archive contains the code with pinned dependencies and dataset checksums, the candidate grids, the final models and the trajectories of all runs, and the scripts that recompute the reported metrics and the paired statistics.
Matched-Objective Comparison
All four formats in Section V-C use the identical , , stepsizes, stratifications, and mini-batch streams. The three sparse formats transmit 16 rows of length 50, where the shared mask uses 13 ranked rows and three reserve rows with , the individual top rows upload their own indices, and the uniformly sampled common rows require no energy reports. Each format enforces a different feasible support under the same Min-Max rule, and the shared mask additionally admits forged energy reports. The 80 runs with the shared mask reproduce the corresponding runs of the main comparison exactly. Table V reports the final value of the common objective (2), and Figure 2 shows the test cross-entropy of the four formats under the Min-Max attack.
Figure 2. Test cross-entropy (log scale) versus oracle slots for the four communication formats with the matched objective under the Min-Max attack. Lines and shaded regions show the means and the pointwise 95% confidence intervals over 20 seeds.
Controlled Study
The minimizer of (2) is approximated by an L-BFGS solution , which satisfies the certificate
with the RHS below in all cases. With eight rows under two sign-flipping Byzantine workers, the individual top rows upload 5.10% of the dense vector plus 64 index bits per slot, compared with 7.10% for the shared mask, and attain the accuracy of 88.35 0.64% versus 87.98 0.90% on MNIST and 78.60 1.51% versus 78.63 1.71% on Fashion-MNIST over five seeds. The 20,000-slot runs of LAG-FRPG show a decreasing upload activity, although they are too short to estimate the asymptotic exponent in Corollary 1.
Consensus Diagnostics: Let and denote the numerical solutions of the penalized problem (2) and the consensus problem (1), respectively, with and . The exact model bias lies between and , which gives the enclosures in Table IV. Over the 20 reference problems, the largest gradient norm of the consensus solutions is , and the largest certificate (5) of the consensus objective is .
References
- [1]B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. Agüera y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Proc. AISTATS, ser. PMLR, vol. 54, 2017, pp. 1273–1282.arxiv.org/abs/1602.05629
- [2]P. Blanchard, E. M. El Mhamdi, R. Guerraoui, and J. Stainer, “Machine learning with adversaries: Byzantine tolerant gradient descent,” in Adv. Neural Inf. Process. Syst., vol. 30, 2017.
- [3]D. Yin, Y. Chen, R. Khamrandhan, and P. Bartlett, “Byzantine-robust distributed learning: Towards optimal statistical rates,” in Proc. ICML, ser. PMLR, vol. 80, 2018, pp. 5650–5659.arxiv.org/abs/1803.01498
- [4]S. U. Stich, J.-B. Cordonnier, and M. Jaggi, “Sparsified SGD with memory,” in Adv. Neural Inf. Process. Syst., vol. 31, 2018.
- [5]T. Chen, G. B. Giannakis, T. Sun, and W. Yin, “LAG: Lazily aggregated gradient for communication-efficient distributed learning,” in Adv. Neural Inf. Process. Syst., vol. 31, 2018.arxiv.org/abs/1805.09965
- [6]E. M. El Mhamdi, R. Guerraoui, and S. Rouault, “The hidden vulnerability of distributed learning in Byzantium,” in Proc. ICML, ser. PMLR, vol. 80, 2018, pp. 3521–3530.
- [7]K. Pillutla, S. M. Kakade, and Z. Harchaoui, “Robust aggregation for federated learning,” IEEE Trans. Signal Process., vol. 70, pp. 1142–1154, 2022.DOI
- [8]Z. Wu, Q. Ling, T. Chen, and G. B. Giannakis, “Federated variance-reduced stochastic gradient descent with robustness to Byzantine attacks,” IEEE Trans. Signal Process., vol. 68, pp. 4583–4596, 2020.DOI
- [9]L. Li, W. Xu, T. Chen, G. B. Giannakis, and Q. Ling, “RSA: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets,” in Proc. AAAI Conf. Artificial Intelligence, vol. 33, no. 1, 2019, pp. 1544–1551.arxiv.org/abs/1811.03761
- [10]Y. Dong, G. B. Giannakis, T. Chen, J. Cheng, M. J. Hossain, and V. C. M. Leung, “Communication-efficient Byzantine-resilient federated learning over heterogeneous datasets,” arXiv:2006.09992v3, 2020.arxiv.org/abs/2006.09992
- [11]S. P. Karimireddy, Q. Rebjock, S. U. Stich, and M. Jaggi, “Error feedback fixes SignSGD and other gradient compression schemes,” in Proc. ICML, ser. PMLR, vol. 97, 2019, pp. 3252–3261.arxiv.org/abs/1901.09847
- [12]P. Richtárik, I. Sokolov, and I. Fatkhullin, “EF21: A new, simpler, theoretically better, and practically faster error feedback,” in Adv. Neural Inf. Process. Syst., vol. 34, 2021.arxiv.org/abs/2106.05203
- [13]T. Yang et al., “Applied federated learning: Improving Google keyboard query suggestions,” arXiv:1812.02903, 2018.arxiv.org/abs/1812.02903
- [14]G. Legate, N. Bernier, L. Page-Caccia, E. Ovallon, and E. Belilovsky, “Guiding the last layer in federated learning with pre-trained models,” in Adv. Neural Inf. Process. Syst., vol. 36, 2023.arxiv.org/abs/2306.03937
- [15]Y. Chen, S. Kar, and J. M. F. Moura, “Resilient distributed parameter estimation with heterogeneous data,” IEEE Trans. Signal Process., vol. 67, no. 19, pp. 4918–4933, Oct. 2019.DOI
- [16]Y. Liu, P. Ning, and M. K. Reiter, “False data injection attacks against state estimation in electric power grids,” ACM Trans. Inf. Syst. Secur., vol. 14, no. 1, May 2011, Art. no. 13.
- [17]S. P. Karimireddy, L. He, and M. Jaggi, “Learning from history for Byzantine robust optimization,” in Proc. ICML, vol. 139, 2021, pp. 5311–5319.arxiv.org/abs/2012.10333
- [18]——, “Byzantine-robust learning on heterogeneous datasets via bucketing,” in Proc. ICLR, 2022.
- [19]Y. Allouah, S. Farhadkhani, R. Guerraoui, N. Gupta, R. Pinot, and J. Stephan, “Fixing by mixing: A recipe for optimal Byzantine ML under heterogeneity,” in Proc. AISTATS, vol. 206, 2023, pp. 1232–1300.arxiv.org/abs/2302.01772
- [20]Y. Allouah, R. Guerraoui, N. Gupta, R. Pinot, and G. Rizk, “Robust distributed learning: Tight error bounds and breakdown point under data heterogeneity,” in Adv. Neural Inf. Process. Syst., vol. 36, 2023, pp. 45 744–45 776.
- [21]Q. Shi, J. Peng, K. Yuan, X. Wang, and Q. Ling, “Optimal complexity in Byzantine-robust distributed stochastic optimization with data heterogeneity,” J. Mach. Learn. Res., vol. 26, no. 268, pp. 1–58, 2025.arxiv.org/abs/2503.16337
- [22]X. Cao, M. Fang, J. Liu, and N. Z. Gong, “FLTrust: Byzantine-robust federated learning via trust bootstrapping,” in Proc. NDSS, 2021.arxiv.org/abs/2012.13995
- [24]A. Shestakov, V. Aletov, and A. Beznosikov, “On Johnson-Lindenstrauss transforms for Byzantine-robust optimization,” arXiv:2610.27989v1, 2026.arxiv.org/abs/2610.27989
- [25]C. Xie, O. Koyejo, and I. Gupta, “Fall of empires: Breaking Byzantine-tolerant SGD by inner product manipulation,” in Proc. 35th Conf. Uncertainty in Artificial Intelligence, ser. PMLR, vol. 115, 2020, pp. 261–270.arxiv.org/abs/1903.03936
- [26]M. Baruch, G. Baruch, and Y. Goldberg, “A little is enough: Circumventing defenses for distributed learning,” in Adv. Neural Inf. Process. Syst., vol. 32, 2019.arxiv.org/abs/1902.06156
- [27]V. Shejwalkar and A. Houmansadr, “Manipulating the Byzantine: Optimizing model poisoning attacks and defenses for federated learning,” in Proc. NDSS, 2021.DOI
- [28]A. Koppel, B. M. Sadler, and A. Ribeiro, “Proximity without consensus in online multiagent optimization,” IEEE Trans. Signal Process., vol. 65, no. 12, pp. 3062–3077, 2017.DOI
- [29]C. T. Dinh, N. Tran, and J. Nguyen, “Personalized federated learning with Moreau envelopes,” in Adv. Neural Inf. Process. Syst., vol. 33, 2020, pp. 21 394–21 405.arxiv.org/abs/2006.08848
- [30]A. Ghosh, R. K. Maity, S. Kadhe, A. Mazumdar, and K. Ramchandran, “Communication-efficient and Byzantine-robust distributed learning with error feedback,” IEEE J. Sel. Areas Inf. Theory, vol. 2, no. 3, pp. 942–953, 2021.arxiv.org/abs/1911.09721
- [31]H. Zhu and Q. Ling, “Byzantine-robust distributed learning with compression,” IEEE Trans. Signal Inf. Process. Netw., vol. 9, pp. 280–294, 2023.DOI
- [32]A. Rammal, K. Gruntkowska, N. Fedin, E. Gorbunov, and P. Richtárik, “Communication compression for Byzantine robust learning: New efficient algorithms and improved rates,” in Proc. AISTATS, ser. PMLR, vol. 238, 2024, pp. 1207–1215.arxiv.org/abs/2310.09804
- [33]C. Liu, Y. Li, Y. Yi, and K. H. Johansson, “Byzantine-robust and communication-efficient distributed learning via compressed momentum filtering,” IEEE Trans. Neural Netw. Learn. Syst., vol. 37, no. 8, pp. 3985–3997, 2026.DOI
- [34]Y. Li, C. Liu, and Y. Yi, “Accelerating Byzantine-robust distributed learning with compressed communication via double momentum and variance reduction,” arXiv:2603.15144v2, 2026.arxiv.org/abs/2603.15144
- [35]D. Gupta, A. Honsell, C. Xu, N. Gupta, and G. Neglia, “Reconciling communication compression and Byzantine-robustness in distributed learning,” in Proc. AISTATS, vol. 300, 2026, pp. 2008–2016.arxiv.org/abs/2508.17129
- [36]L. Xu, J. Chen, H. Ko, W. Wang, and Y. Dong, “FedAdam-BACK: A compression-based Byzantine-resilient federated learning,” 2026, unpublished manuscript.
- [37]C. Chen, C. Ma, Z. Li, Y. He, Y. Dong, and K. Yuan, “An All-Reduce compatible Top-K compressor for communication-efficient distributed learning,” arXiv:2510.26709v3, 2025.arxiv.org/abs/2510.26709
- [38]X. He, H. Zhu, and Q. Ling, “C-RSA: Byzantine-robust and communication-efficient distributed learning in the non-convex and non-IID regime,” Signal Process., vol. 213, Dec. 2023, art. 109222.DOI
- [39]T. Chen, Y. Sun, and W. Yin, “Communication-adaptive stochastic gradient methods for distributed learning,” IEEE Trans. Signal Process., vol. 69, pp. 4637–4651, 2021.DOI
- [40]J. Sun, T. Chen, G. B. Giannakis, Q. Yang, and Z. Yang, “Lazily aggregated quantized gradient innovation for communication-efficient federated learning,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 44, no. 4, pp. 2031–2044, Apr. 2022.
- [41]N. Singh, D. Data, J. George, and S. Diggavi, “SPARQ-SGD: Event-triggered and compressed communication in decentralized optimization,” IEEE Trans. Autom. Control, vol. 68, no. 2, pp. 721–736, 2023.
- [42]X. He, X. Yi, Y. Zhao, K. H. Johansson, and V. Gupta, “Asymptotic analysis of federated learning under event-triggered communication,” IEEE Trans. Signal Process., vol. 71, pp. 2654–2667, 2023.DOI
- [43]K. Mishchenko, G. Malinovsky, S. Stich, and P. Richtárik, “ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally!” in Proc. ICML, ser. PMLR, vol. 162, 2022, pp. 15 750–15 769.arxiv.org/abs/2202.09357
- [44]L. Condat, A. Maranjan, and P. Richtárik, “LoCoDL: Communication-efficient distributed learning with local training and compression,” in Proc. ICLR, 2025.arxiv.org/abs/2403.04348
- [45]Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proc. IEEE, vol. 86, no. 11, pp. 2278–2324, 1998.
- [46]H. Xiao, K. Xiao, X. Rasul, and R. Vollgraf, “Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms,” arXiv:1708.07747, 2017.arxiv.org/abs/1708.07747

