betaFeedback

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 ℓ2\ell_2-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.

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 (1−γ)/γ2(1-\gamma)/\gamma^2 with the contraction factor γ\gamma 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-KK compression in FedAdam-BACK [36]; a common support is also selected by ARC-Top-KK [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 O(ln⁡K/K2)\mathcal{O}(\ln K/K^2) term over KK slots, whose dependence (1−γ)/γ2(1-\gamma)/\gamma^2 on the contraction factor cannot be improved in order. For LAG-FRPG, the lazy uploads add an O(1/(Kln⁡K))\mathcal{O}(1/(K\ln K)) term, and the expected fraction of uploading slots decays as O(ln⁡K/K)\mathcal{O}(\sqrt{\ln K/K}).

  • 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 Q=N+BQ=N+B workers, among which NN workers are honest and BB workers are Byzantine. Without loss of generality, we index the honest workers by n=1,…,Nn=1,\ldots,N; the indexing is only used in the analysis, and the server requires neither the identities of the honest workers nor the value of BB. Each honest worker nn holds a local dataset Dn\mathcal{D}_n with the local loss fn(x):=Eξ∼Dn[f(x;ξ)]f_n(x):=\mathbb{E}_{\xi\sim\mathcal{D}_n}[f(x;\xi)], and the server holds a regularizer f0f_0. With equally weighted workers, the consensus-based FL minimizes

x⋆=arg⁡min⁡x∈Rd H(x):=f0(x)+∑n=1Nfn(x)(1)x^\star=\underset{x\in\mathbb{R}^d}{\arg\min}\ H(x):=f_0(x)+\sum_{n=1}^{N}f_n(x) \tag*{(1)}

where xx is the dd-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 wn∈Rdw_n\in\mathbb{R}^d to each honest worker nn and a model w0∈Rdw_0\in\mathbb{R}^d to the server, and minimize

F(w):=f0(w0)+∑n=1N{fn(wn)+λpn(w0−wn)}(2)F(w):=f_0(w_0)+\sum_{n=1}^{N}\{f_n(w_n)+\lambda p_n(w_0-w_n)\} \tag*{(2)}

where w:=vec⁡(w0,…,wN)w:=\operatorname{vec}(w_0,\ldots,w_N), λ>0\lambda>0 is the penalty weight, and pnp_n is the penalty function of worker nn. We denote the minimizer of (2) by u⋆:=vec⁡(u0⋆,…,uN⋆)u^\star:=\operatorname{vec}(u_0^\star,\ldots,u_N^\star), and rely on the following assumptions.

Assumption 1 (Smoothness): For n=0,…,Nn=0,\ldots,N, the function fnf_n has an LnL_n-Lipschitz continuous gradient.

Assumption 2 (Strong convexity): For n=0,…,Nn=0,\ldots,N, the function fnf_n is δn\delta_n-strongly convex with δn>0\delta_n>0.

Assumption 3 (Bounded penalty gradient): For n=1,…,Nn=1,\ldots,N, the penalty function pnp_n is convex and differentiable with ∥∇pn(y)∥2≤G\lVert\nabla p_n(y)\rVert^2 \le G and an LpL_p-Lipschitz continuous gradient, where G>0G > 0.

Assumptions 1 and 2 hold for ℓ2\ell_2-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

p(y)={∥y∥2/(2μ),∥y∥≤μ∥y∥−μ/2,∥y∥>μ(3)p(y) = \begin{cases} \lVert y\rVert^2/(2\mu), & \lVert y\rVert\le\mu\\ \lVert y\rVert-\mu/2, & \lVert y\rVert> \mu \end{cases} \tag*{(3)}

with μ>0\mu> 0, G=1G = 1, and Lp=1/μL_p = 1/\mu, which we use for all workers in the sequel. Assumption 3 implies that each honest worker moves the server model through the penalty gradient λ∇pn(w0−wn)\lambda\nabla p_n(w_0-w_n), whose norm never exceeds λG\lambda\sqrt{G}.

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 λ\lambda, the server optimum u0∗u_0^* of (2) generally differs from the consensus optimum x∗x^* in (1). In fact, u0∗u_0^* minimizes the profiled loss f0(x)+∑n=1Ninf⁡y{fn(y)+λp(x−y)}f_0(x) + \sum_{n=1}^{N}\inf_y\{f_n(y) + \lambda p(x-y)\}, to which each worker contributes a gradient with norm at most λ\lambda (cf. Appendix A); hence, the bounded influence of each worker comes with a model bias. Let Πr\Pi_r denote the Euclidean projection onto the ball with radius rr, δΣ:=∑n=0Nδn\delta_\Sigma:= \sum_{n=0}^{N}\delta_n, and δmin⁡:=min⁡nδn\delta_{\min} := \min_n\delta_n. 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 w=vec⁡(w0,…,wN)w = \operatorname{vec}(w_0,\ldots,w_N), let b(w):=∥∑n=0N∇nF(w)∥+∑n=1NLn∥w0−wn∥b(w) := \lVert\sum_{n=0}^{N}\nabla_nF(w)\rVert+ \sum_{n=1}^{N}L_n\lVert w_0-w_n\rVert with ∇nF\nabla_nF being the gradient of FF with respect to wnw_n. Then, we have

∥w0−x∗∥≤∥∇H(w0)∥δΣ≤b(w)δΣ(4)\lVert w_0-x^*\rVert\le\frac{\lVert\nabla H(w_0)\rVert}{\delta_\Sigma} \le\frac{b(w)}{\delta_\Sigma} \tag*{(4)}

and

H(w0)−H(x∗)≤∥∇H(w0)∥22δΣ.(5)H(w_0)-H(x^*) \le\frac{\lVert\nabla H(w_0)\rVert^2}{2\delta_\Sigma}. \tag*{(5)}

Moreover, let en:=∇fn(x∗)−Πλ(∇fn(x∗))e_n := \nabla f_n(x^*)-\Pi_\lambda(\nabla f_n(x^*)) and Aλ2:=∥∑n=1Nen∥2/δ0+∑n=1N∥en∥2/δnA_\lambda^2 := \lVert\sum_{n=1}^{N}e_n\rVert^2/\delta_0+\sum_{n=1}^{N}\lVert e_n\rVert^2/\delta_n. For the Huber penalty (3) with any λ,μ>0\lambda,\mu>0, the server optimum satisfies

∥u0∗−x∗∥≤Aλ+Nλμδ0.(6)\lVert u_0^*-x^*\rVert\le\frac{A_\lambda+\sqrt{N\lambda\mu}}{\sqrt{\delta_0}}. \tag*{(6)}

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 uˉ\bar{u} of FF, the certificate (4) holds for u0∗u_0^* after adding ∥∇F(uˉ)∥/δmin⁡\lVert\nabla F(\bar{u})\rVert/\delta_{\min} 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 λ>max⁡n∥∇fn(un∗)∥\lambda> \max_n\lVert\nabla f_n(u_n^*)\rVert, the penalized optimum lies in the quadratic region of the Huber penalty, and the sharper bound ∥u0∗−x∗∥≤μ∑n=1NLn/δΣ\lVert u_0^*-x^*\rVert\le\mu\sum_{n=1}^{N}L_n/\delta_\Sigma 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 λ\lambda and μ\mu. If λ≥max⁡n∥∇fn(x∗)∥\lambda\ge\max_n\lVert\nabla f_n(x^*)\rVert, we have Aλ=0A_\lambda=0 and the model bias vanishes with μ\mu; otherwise, reducing μ\mu alone cannot remove the model bias in general. Meanwhile, a larger λ\lambda 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 k≥1k \ge1, the server and the honest workers perform the FRPG recursions with the stepsizes

βk=2/(k+2)(7)\beta_k = 2/(k+2) \tag*{(7)}

and

αn,k={δ0(k+2)2/14+3L0/2,n=0,3δn(k+2)2/14+Ln,n≥1.(8)\alpha_{n,k} = \begin{cases} \delta_0(k+2)^2/14+3L_0/2, & n=0, \\ 3\delta_n(k+2)^2/14+L_n, & n\ge1. \end{cases} \tag*{(8)}

More specifically, the server updates

u0,k=(1−βk)w0,k−1+βkv0,k−1(9)u_{0,k}=(1-\beta_k)w_{0,k-1}+\beta_kv_{0,k-1} \tag*{(9)}
w0,k=u0,k−∇f0(u0,k)/α0,k(10)w_{0,k}=u_{0,k}-\nabla f_0(u_{0,k})/\alpha_{0,k} \tag*{(10)}
v0,k=v0,k−1−δ0(v0,k−1−u0,k)+∇f0(u0,k)+Skδ0+α0,kβk(11)v_{0,k}=v_{0,k-1}-\frac{\delta_0(v_{0,k-1}-u_{0,k})+\nabla f_0(u_{0,k})+S_k}{\delta_0+\alpha_{0,k}\beta_k} \tag*{(11)}

where Sk:=∑n=1Qg^n,kS_k := \sum_{n=1}^{Q}\hat{g}_{n,k} aggregates the states {g^n,k}n=1Q\{\hat{g}_{n,k}\}_{n=1}^{Q} that the server maintains for all workers. After receiving w0,kw_{0,k}, each honest worker nn samples a mini-batch ξn,k\xi_{n,k} from Dn\mathcal{D}_n and updates

un,k=(1−βk)wn,k−1+βkvn,k−1(12)u_{n,k}=(1-\beta_k)w_{n,k-1}+\beta_kv_{n,k-1} \tag*{(12)}
wn,k=w0,k−prox⁡λpn/αn,k(w0,k−un,k+∇~n,k/αn,k)(13)w_{n,k}=w_{0,k}-\operatorname{prox}_{\lambda p_n/\alpha_{n,k}}(w_{0,k}-u_{n,k}+\widetilde{\nabla}_{n,k}/\alpha_{n,k}) \tag*{(13)}
vn,k=vn,k−1−δn(vn,k−1−un,k)+∇~n,k−gn,kδn+αn,kβk(14)v_{n,k}=v_{n,k-1}-\frac{\delta_n(v_{n,k-1}-u_{n,k})+\widetilde{\nabla}_{n,k}-g_{n,k}}{\delta_n+\alpha_{n,k}\beta_k} \tag*{(14)}

where ∇~n,k:=∇f(un,k;ξn,k)\widetilde{\nabla}_{n,k}:=\nabla f(u_{n,k};\xi_{n,k}) is the stochastic gradient, prox⁡tp(x):=arg⁡min⁡y{tp(y)+∥x−y∥2/2}\operatorname{prox}_{t p}(x):=\arg\min_y\{t p(y)+\lVert x-y\rVert^2/2\} is the proximal operator, and

gn,k:=λ∇pn(w0,k−wn,k),zn,k:=gn,k−g^n,k−1.(15)g_{n,k}:=\lambda\nabla p_n(w_{0,k}-w_{n,k}),\qquad z_{n,k}:=g_{n,k}-\widehat{g}_{n,k-1}. \tag*{(15)}

Algorithm 1 Projected Penalty-Gradient Tracking

Require: stepsizes {αn,k}\{\alpha_{n,k}\} and {βk}\{\beta_k\}; penalty weight λ\lambda; communication format; number of slots KK.

  1. Server and honest workers initialize wn,0w_{n,0}, vn,0v_{n,0}, and g^n,0=0\hat{g}_{n,0}=0

  2. for k=1,…,Kk=1,\ldots,K do

  3. Server computes u0,ku_{0,k} and w0,kw_{0,k} via (9a) and (9b), and broadcasts w0,kw_{0,k} to all workers

  4. Each honest worker nn samples ξn,k\xi_{n,k} and computes un,ku_{n,k}, wn,kw_{n,k}, vn,kv_{n,k}, and zn,kz_{n,k} via (10) and (11)

  5. if FRPG-CS then

  6. Each worker uploads its row energies; server clips them via (14), selects Tk\mathcal{T}_k by trimmed means, draws the reserve Rk\mathcal{R}_k, and broadcasts Mk\mathcal{M}_k

  7. Each honest worker uploads cn,kc_{n,k} via (15)

  8. else if LAG-FRPG then

  9. Each honest worker uploads cn,kc_{n,k} via (17)

  10. else

  11. Each honest worker uploads cn,k=Cn,k(zn,k)c_{n,k}=C_{n,k}(z_{n,k}) and the required support information

  12. end if

  13. Server updates the states of all workers via (12), and each honest worker applies the same update to its copy

  14. Server computes v0,kv_{0,k} via (9c)

  15. end for

  16. return w0,Kw_{0,K}

are the penalty gradient of worker nn and its residual with respect to the state g^n,k−1\hat{g}_{n,k-1} that the server maintains for worker nn. Note that (10c) uses the exact penalty gradient gn,kg_{n,k}, which is locally available regardless of the uploaded information.

Different from FRPG, where each worker uploads gn,kg_{n,k} per slot, each honest worker in the proposed framework uploads a compressed version cn,kc_{n,k} of the residual zn,kz_{n,k} and keeps an identical copy of its state. After receiving cn,kc_{n,k}, the server updates the state of each worker n=1,…,Qn=1,\ldots,Q as

g^n,k=ΠλG(g^n,k−1+cn,k)(16)\hat{g}_{n,k}=\Pi_{\lambda\sqrt{G}}(\hat{g}_{n,k-1}+c_{n,k}) \tag*{(16)}

with g^n,0=0\hat{g}_{n,0}=0, while the local models are not projected. The projection in (12) plays two roles. For an honest worker, it cannot increase the tracking error ∥g^n,k−gn,k∥\|\hat{g}_{n,k}-g_{n,k}\|, since gn,kg_{n,k} belongs to the ball with radius λG\lambda\sqrt{G} 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 wn,0w_{n,0} and vn,0v_{n,0} are initialized at deterministic finite vectors.

Contractive Compressors

Let cn,k=Cn,k(zn,k)c_{n,k}=C_{n,k}(z_{n,k}) with Cn,kC_{n,k} being the compressor of worker nn per slot kk, and let Hk\mathcal{H}_k 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 nn to use a contractive compressor, i.e.,

E[∥Cn,k(zn,k)−zn,k∥2∣Hk]≤(1−γn)∥zn,k∥2(17)\mathbb{E}[\|C_{n,k}(z_{n,k})-z_{n,k}\|^2\mid\mathcal{H}_k]\le(1-\gamma_n)\|z_{n,k}\|^2 \tag*{(17)}

where γn∈(0,1]\gamma_n\in(0,1] 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 dd-dimensional vector into m:=⌈d/ℓ⌉m:=\lceil d/\ell\rceil rows of length ℓ\ell. For an integer 1≤r≤m1\le r\le m, keeping the rr rows with the largest energy of each residual (individual top-rr rows) and keeping rr uniformly sampled rows that are shared by all workers both satisfy (13) with γn=r/m\gamma_n=r/m. 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 γn=1\gamma_n=1. 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 ψn,k[j]:=∥zn,k[j]∥2\psi_{n,k}[j]:=\|z_{n,k}[j]\|^2 with zn,k[j]z_{n,k}[j] being the jj-th row of zn,kz_{n,k}, j=1,…,mj=1,\ldots,m. Since the residual of an honest worker satisfies ∥zn,k∥2≤4λ2G\|z_{n,k}\|^2\le4\lambda^2G, the server clips each report as

ψ~n,k=4λ2G[ψn,k]+max⁡{4λ2G,∑j[ψn,k[j]]+}(18)\widetilde{\psi}_{n,k}= \frac{4\lambda^2G[\psi_{n,k}]_+}{\max\{4\lambda^2G,\sum_j[\psi_{n,k}[j]]_+\}} \tag*{(18)}

where [⋅]+[\cdot]_+ denotes the entry-wise positive part. For each row, the server computes a trimmed mean of the clipped reports with b^\hat{b} entries removed from each tail, where 0≤b^<Q/20\le\hat{b}<Q/2. The ss rows with the highest scores form the set Tk\mathcal{T}_k with index-based tie breaking. After the reports are fixed, the server selects R≥1R\ge1 rows uniformly without replacement from the complement of Tk\mathcal{T}_k to form the reserve set Rk\mathcal{R}_k. The mask and the upload of each honest worker are

Mk=Tk∪Rk,s+R≤m,cn,k=PMkzn,k(19)\mathcal{M}_k=\mathcal{T}_k\cup\mathcal{R}_k,\qquad s+R\le m,\qquad c_{n,k}=P_{\mathcal{M}_k}z_{n,k} \tag*{(19)}

where PMkP_{\mathcal{M}_k} keeps the rows in Mk\mathcal{M}_k and sets the remaining rows to zero. Hence, each honest worker uploads m+(s+R)ℓm+(s+R)\ell scalars per slot, and the mask is broadcast on the downlink.

Let Fk′\mathcal{F}'_k 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 Tk\mathcal{T}_k and zn,kz_{n,k} are fixed given Fk′\mathcal{F}'_k, we have

E[∥zn,k−cn,k∥2∣Fk′]≤(1−γ)∥zn,k∥2,γ=Rm−s(20)\mathbb{E}[\|z_{n,k}-c_{n,k}\|^2\mid\mathcal{F}'_k]\le(1-\gamma)\|z_{n,k}\|^2,\qquad\gamma=\frac{R}{m-s} \tag*{(20)}

i.e., FRPG-CS satisfies (13) with γn=R/(m−s)\gamma_n=R/(m-s). 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 b^≥B\hat{b}\ge B nor an honest majority, although the numerical tests set b^=B\hat{b}=B. 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.,

cn,k={z^n,k,∥z^n,k∥2>τk,0,otherwise(21)c_{n,k} = \begin{cases} \widehat{z}_{n,k}, & \lVert\widehat{z}_{n,k}\rVert^2 > \tau_k,\\ 0, & \text{otherwise} \end{cases} \tag*{(21)}

with the threshold

τk=τ0λ2G(k+2)ln⁡(k+2),τ0>0.(22)\tau_k = \frac{\tau_0\lambda^2G}{(k+2)\ln(k+2)}, \qquad\tau_0 > 0. \tag*{(22)}

An upload of honest worker nn resets its state to gn,kg_{n,k}, 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

∥g^n,k−gn,k∥2≤τk,n=1,…,N.(23)\lVert\widehat{g}_{n,k}-g_{n,k}\rVert^2 \le\tau_k, \qquad n=1,\ldots,N. \tag*{(23)}

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 Fk\mathcal{F}_k denote the σ\sigma-field generated by the history before the stochastic gradients of the honest workers are sampled in slot kk, such that the points {un,k}\{u_{n,k}\} are Fk\mathcal{F}_k-measurable. The noise of the stochastic gradient of honest worker nn is

Δn,k:=∇f(un,k;ξn,k)−∇fn(un,k),n=1,…,N.(24)\Delta_{n,k} := \nabla f(u_{n,k};\xi_{n,k})-\nabla f_n(u_{n,k}), \qquad n=1,\ldots,N. \tag*{(24)}

Assumption 4 (Stochastic gradient noise): The noise satisfies E[Δn,k∣Fk]=0\mathbb{E}[\Delta_{n,k}\mid\mathcal{F}_k]=0 and E[∥Δn,k∥2∣Fk]≤σn2<∞\mathbb{E}[\lVert\Delta_{n,k}\rVert^2\mid\mathcal{F}_k]\le\sigma_n^2<\infty for n=1,…,Nn=1,\ldots,N.

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

Δ0,k:=Sk−∑n=1Ngn,k=Bk+Ek(25)\Delta_{0,k} := S_k-\sum_{n=1}^{N}g_{n,k}=B_k+E_k \tag*{(25)}

where Bk:=∑n=N+1Qg^n,kB_k:=\sum_{n=N+1}^{Q}\widehat{g}_{n,k} collects the states of the Byzantine workers and Ek:=∑n=1N(g^n,k−gn,k)E_k:=\sum_{n=1}^{N}(\widehat{g}_{n,k}-g_{n,k}) is the tracking error of the honest workers. Based on the projection in (12), we have for each sample path

∥Sk∥≤QλG,∥Bk∥≤BλG,∥Ek∥≤2NλG.(26)\lVert S_k\rVert\le Q\lambda\sqrt{G}, \qquad\lVert B_k\rVert\le B\lambda\sqrt{G}, \qquad\lVert E_k\rVert\le2N\lambda\sqrt{G}. \tag*{(26)}

Different from the noise in (20), the deviation Δ0,k\Delta_{0,k} can be biased and can depend on the current samples of the honest workers. We measure the learning error by the expected objective gap Dk:=E[F(wk)]−F(u∗)D_k:=\mathbb{E}[F(w_k)]-F(u^*) with wk:=vec⁡(w0,k,…,wN,k)w_k:=\operatorname{vec}(w_{0,k},\ldots,w_{N,k}). In the sequel, Assumptions 1–4 are satisfied, the stepsizes follow (7) and (8), all constants are independent of the horizon KK, and all proofs are deferred to the appendices.

Lemma 2 (One-step recursion): For any ϵ>0\epsilon>0, let

η1,0,k:=12(ϵβk+α0,kβk2)∥u0∗−v0,k−1∥2−12(δ0βk+α0,kβk2)∥u0∗−v0,k∥2\eta_{1,0,k}:=\frac{1}{2}(\epsilon\beta_k+\alpha_{0,k}\beta_k^2)\lVert u_0^*-v_{0,k-1}\rVert^2-\frac{1}{2}(\delta_0\beta_k+\alpha_{0,k}\beta_k^2)\lVert u_0^*-v_{0,k}\rVert^2
η1,n,k:=12αn,kβk2∥un∗−vn,k−1∥2−12(δnβk+αn,kβk2)∥un∗−vn,k∥2,n≥1.\eta_{1,n,k}:=\frac{1}{2}\alpha_{n,k}\beta_k^2\lVert u_n^*-v_{n,k-1}\rVert^2-\frac{1}{2}(\delta_n\beta_k+\alpha_{n,k}\beta_k^2)\lVert u_n^*-v_{n,k}\rVert^2,\qquad n\ge1.

Then, we have

Dk≤(1−βk)Dk−1+∑n=0NEη1,n,k+3E[(∥Sk∥+∥Δ0,k∥)2]2(2α0,k−3L0)+∑n=1Nσn22(αn,k−Ln)+2E∥Sk∥2α0,k+βkE∥Δ0,k∥22ϵ.(27)D_k\le(1-\beta_k)D_{k-1}+\sum_{n=0}^{N}\mathbb{E}\eta_{1,n,k} +\frac{3\mathbb{E}[(\lVert S_k\rVert+\lVert\Delta_{0,k}\rVert)^2]}{2(2\alpha_{0,k}-3L_0)} +\sum_{n=1}^{N}\frac{\sigma_n^2}{2(\alpha_{n,k}-L_n)} +\frac{2\mathbb{E}\lVert S_k\rVert^2}{\alpha_{0,k}} +\frac{\beta_k\mathbb{E}\lVert\Delta_{0,k}\rVert^2}{2\epsilon}. \tag*{(27)}

Lemma 2 extends the one-step analysis of FRPG [10] to an arbitrary deviation Δ0,k\Delta_{0,k}: since the noise is only cancelled against the Fk\mathcal{F}_k-measurable un∗−vn,k−1u^*_{n}-v_{n,k-1}, neither the unbiasedness of Δ0,k\Delta_{0,k} nor its independence of the current samples is required, and the result remains valid under adaptive attacks.

Lemma 3 (Stability): There exist finite constants {Vn}n=0N\{V_n\}_{n=0}^{N} given in (41) such that

E∥wn,k−un∗∥2≤Vn,E∥vn,k−un∗∥2≤Vn(28)\mathbb{E}\lVert w_{n,k}-u_n^*\rVert^2\le V_n,\qquad\mathbb{E}\lVert v_{n,k}-u_n^*\rVert^2\le V_n \tag*{(28)}

for n=0,…,Nn=0,\ldots,N and $k\ge 0.

Lemma 4 (Penalty-gradient drift): With gn,0:=λ∇pn(w0,0−wn,0)g_{n,0}:=\lambda\nabla p_n(w_{0,0}-w_{n,0}), there exist finite constants {χn}n=1N\{\chi_n\}_{n=1}^{N} given in (43) such that

E∥gn,k−gn,k−1∥2≤χn(k+2)2.(29)\mathbb{E}\lVert g_{n,k}-g_{n,k-1}\rVert^2\le\frac{\chi_n}{(k+2)^2}. \tag*{(29)}

Lemma 3 follows from (23) with the coarse bound ∥Δ0,k∥≤(Q+N)λG\lVert\Delta_{0,k}\rVert\le(Q+N)\lambda\sqrt{G} 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 O(1/k)\mathcal{O}(1/k) per slot and the Lipschitz continuity of ∇pn\nabla p_n transfers the movement to gn,kg_{n,k}.

Lemma 5 (Bounded-state tracking): Suppose (13) is satisfied. Let Jn:=⌈8/γn⌉J_n:=\lceil8/\gamma_n\rceil and

Kn:=4(1−γn)max⁡{λ2G(Jn+2)2,(2−γn)χnγn2}.(30)\mathcal{K}_n:=4(1-\gamma_n)\max\left\{\lambda^2G(J_n+2)^2,\frac{(2-\gamma_n)\chi_n}{\gamma_n^2}\right\}. \tag*{(30)}

For k≥1k\ge1, the tracking error of honest worker nn satisfies

ζn,k:=E∥g^n,k−gn,k∥2≤Kn(k+2)2.(31)\zeta_{n,k}:=\mathbb{E}\lVert\widehat{g}_{n,k}-g_{n,k}\rVert^2\le\frac{\mathcal{K}_n}{(k+2)^2}. \tag*{(31)}

In particular, Kn≤(1−γn)γn−2max⁡{484λ2G,8χn}\mathcal{K}_n\le(1-\gamma_n)\gamma_n^{-2}\max\{484\lambda^2G,8\chi_n\}, and Kn=0\mathcal{K}_n=0 for γn=1\gamma_n=1.

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 ζn,k≤4(1−γn)λ2G\zeta_{n,k}\le4(1-\gamma_n)\lambda^2G implied by the bounded states in (12), which handles the first JnJ_n slots. The inverse-quadratic dependence of Kn\mathcal{K}_n 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

Λ0=D0+(3δ08+α0,12)∥u0∗−v0,0∥2+∑n=1Nαn,12∥un∗−vn,0∥2(32)\Lambda_0 = D_0 + \left(\frac{3\delta_0}{8}+\frac{\alpha_{0,1}}{2}\right)\lVert u_0^* - v_{0,0}\rVert^2 + \sum_{n=1}^{N}\frac{\alpha_{n,1}}{2}\lVert u_n^* - v_{n,0}\rVert^2 \tag*{(32)}
η(θ)=[7Q2+218(1+θ)(Q+B)2]λ2Gδ0+∑n=1N7σn212δn.(33)\eta(\theta) = \left[7Q^2+\frac{21}{8}(1+\theta)(Q+B)^2\right]\frac{\lambda^2G}{\delta_0}+\sum_{n=1}^{N}\frac{7\sigma_n^2}{12\delta_n}. \tag*{(33)}

Theorem 1. Suppose Assumptions 1–4 are satisfied and the stepsizes follow (7) and (8). For any fixed θ>0\theta>0 and K≥1K\ge1, the proposed framework achieves

DK≤4Λ0+4Kη(θ)(K+2)2+(1+θ)K2+5K(K+2)2λ2B2Gδ0+CK(34)D_K \le\frac{4\Lambda_0+4K\eta(\theta)}{(K+2)^2}+(1+\theta)\frac{K^2+5K}{(K+2)^2}\frac{\lambda^2B^2G}{\delta_0}+C_K \tag*{(34)}

where

CK:=1+1/θ2δ0(K+2)2∑k=1K(4k+29)E∥Ek∥2.C_K := \frac{1+1/\theta}{2\delta_0(K+2)^2}\sum_{k=1}^{K}(4k+29)\mathbb{E}\lVert E_k\rVert^2.

When the compressor of each honest worker satisfies (13), we have

CK≤(1+1/θ)(∑n=1NKn)22δ0(K+2)2[4ln⁡K+22+21c2](35)C_K \le\frac{(1+1/\theta)(\sum_{n=1}^{N}\sqrt{\mathcal{K}_n})^2}{2\delta_0(K+2)^2}\left[4\ln\frac{K+2}{2}+21c_2\right] \tag*{(35)}

where c2:=π2/6−5/4c_2:=\pi^2/6-5/4.

Theorem 1 applies to FRPG-CS with γn=R/(m−s)\gamma_n=R/(m-s) as well as to the individual and uniform sparsification with γn=r/m\gamma_n=r/m. The RHS of (30) consists of the optimization error, the Byzantine error floor, and the compression error. The optimization error decays as O(1/K)O(1/K), where Λ0\Lambda_0 depends on the initialization and η(θ)\eta(\theta) collects the impacts of the bounded states and the stochastic gradient noise; when B=0B=0, DKD_K converges to zero at the rate of O(1/K)O(1/K).

The Byzantine error floor is obtained by taking the limit of the horizon for a fixed θ\theta and then the infimum over θ\theta, i.e.,

lim sup⁡K→∞DK≤λ2B2Gδ0.(36)\limsup_{K\to\infty}D_K\le\frac{\lambda^2B^2G}{\delta_0}. \tag*{(36)}

Note that the finite-time bound (30) holds for each fixed θ\theta and is not uniform as θ↓0\theta\downarrow0. 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 λ2\lambda^2 and B2B^2 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 CKC_K decays as O(ln⁡K/K2)O(\ln K/K^2), which is faster than the optimization error, and depends on the compressors only through the constants {Kn}\{\mathcal{K}_n\} that scale as (1−γn)/γn2(1-\gamma_n)/\gamma_n^2 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 E∥wK−u∗∥2≤2DK/δmin⁡\mathbb{E}\lVert w_K-u^*\rVert^2\le2D_K/\delta_{\min}. Together with Lemma 1, the distance to the consensus optimum is separated into the algorithmic error and the model bias as

E∥w0,K−x⋆∥2≤2DK/δ0+∥u0∗−x⋆∥(37)\sqrt{\mathbb{E}\lVert w_{0,K}-x^\star\rVert^2}\le\sqrt{2D_K/\delta_0}+\lVert u_0^*-x^\star\rVert \tag*{(37)}

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

CK≤11(1+1/θ)N2τ0λ2Gδ0(K+2)ln⁡(K+2).(38)C_K\le\frac{11(1+1/\theta)N^2\tau_0\lambda^2G}{\delta_0(K+2)\ln(K+2)}. \tag*{(38)}

Consequently, the Byzantine error floor (32) also holds for LAG-FRPG.

Theorem 2 follows from the deterministic bound (19), which gives ∥Ek∥≤Nτk\lVert E_k\rVert\le N\sqrt{\tau_k}. The lazy uploads add an O(1/(Kln⁡K))O(1/(K\ln K)) 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 Un,K:=∑k=1KIn,kU_{n,K}:=\sum_{k=1}^{K}I_{n,k} denote the number of uploads of honest worker nn during slots 1,…,K1,\ldots,K, where In,k∈{0,1}I_{n,k}\in\{0,1\} indicates an upload in slot kk. Under the conditions of Theorem 1, for any positive and nondecreasing thresholds {τk}\{\tau_k\} with ωk:=τk\omega_k:=\sqrt{\tau_k}, we have

EUn,K≤1+Kn∑k=2K1(k+2)ωk+∑k=2K(ωk−1ωk−1).(39)\mathbb{E}U_{n,K}\le1+\sqrt{\mathcal{K}_n}\sum_{k=2}^{K}\frac{1}{(k+2)\omega_k}+\sum_{k=2}^{K}\left(\frac{\omega_{k-1}}{\omega_k}-1\right). \tag*{(39)}

In particular, the threshold (18) yields

EUn,K≤1+2Kn/τˉln⁡M(M−3)+ln⁡((K+1)/2)(40)\mathbb{E}U_{n,K}\le1+2\sqrt{\mathcal{K}_n/\bar{\tau}}\sqrt{\ln M}(\sqrt{M}-\sqrt{3})+\ln((K+1)/2) \tag*{(40)}

where τˉ:=τ0λ2G\bar{\tau}:=\tau_0\lambda^2G and M:=K+2M:=K+2.

Corollary 1 shows that the expected fraction of uploading slots of LAG-FRPG decays as O(ln⁡K/K)O(\sqrt{\ln K/K}). The proof relies on the normalized tracking error ∥gn,k−g^n,k∥/ωk∈[0,1]\lVert g_{n,k}-\hat{g}_{n,k}\rVert/\omega_k\in[0,1], which is summed along each sample path before taking the expectation; compared with the bound O((ln⁡K)3/2/K)O((\ln K)^{3/2}/\sqrt{K}) 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 τk=τˉln⁡2(k+2)/(k+2)2\tau_k=\bar{\tau}\ln^2(k+2)/(k+2)^2 reduces the additional objective error to O(ln⁡3K/K2)O(\ln^3K/K^2), while the expected fraction of uploading slots only vanishes as O(1/ln⁡K)O(1/\ln K) (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 785×10=7,850785\times10=7{,}850 parameters with a constant input feature representing the bias. All parameters of the honest workers are regularized by a ridge term with weight ρ=0.01\rho=0.01, and the server regularizer is a ridge term with weight ρ0=0.1\rho_0=0.1; hence, Assumptions 1 and 2 are satisfied.

2) Federated Settings: We set N=10N = 10 honest workers and add B=2B = 2 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 a=0.3a = 0.3, 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, a∈{0.1,10}a \in\{0.1, 10\}, and B=4B = 4, 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 (λ,μ)=(0.5,0.1)(\lambda, \mu) = (0.5, 0.1), eight transmitted rows, and τ0=1\tau_0 = 1 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 T=20T = 20 [10], projected FRPG (i.e., the proposed framework with full uploads), ℓ2\ell_2-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 B=4B = 4 are not used for tuning. The tuning selects (λ,μ,s+R)=(0.5,0.1,16)(\lambda, \mu, s + R) = (0.5, 0.1, 16) with ℓ=50\ell= 50, s=13s = 13, and R=3R = 3 for FRPG-CS, (λ,μ,τ0)=(0.5,0.1,100)(\lambda, \mu, \tau_0) = (0.5, 0.1, 100) for LAG-FRPG, (λ,μ)=(0.5,0.05)(\lambda, \mu) = (0.5, 0.05) for projected FRPG, and λ=0.1\lambda= 0.1 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 {yn}n=1N\{y_n\}_{n=1}^{N} that the considered protocol aggregates from the honest workers, i.e., the penalty gradients, the (reconstructed) momentum, or the loss gradients, with the mean yˉ\bar{y}. They submit −10yˉ-10\bar{y} in the IPM attack [25], yˉ−1.5σy\bar{y} - 1.5\sigma_y with σy\sigma_y 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 yB:=yˉ−ζyˉ/∥yˉ∥y^{\mathrm{B}} := \bar{y} - \zeta\bar{y}/\lVert\bar{y}\rVert with the largest ζ≥0\zeta\ge0 that satisfies

max⁡n∥yB−yn∥2≤max⁡i,j∥yi−yj∥2(41)\max_{n}\lVert y^{\mathrm{B}} - y_n\rVert^2 \leq\max_{i,j}\lVert y_i - y_j\rVert^2 \tag*{(41)}

where a fixed unit direction replaces yˉ/∥yˉ∥\bar{y}/\lVert\bar{y}\rVert when yˉ=0\bar{y} = 0. 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 tt-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 pp-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.

MethodM: CleanM: Min-MaxM: 8 MiBF: CleanF: Min-MaxF: 8 MiB
FRPG-CS (ours)88.60±0.5788.60 \pm0.5788.46±0.6688.46 \pm0.6688.43±0.8288.43 \pm0.8278.48±1.1178.48 \pm1.1178.38±1.0978.38 \pm1.0978.07±1.0678.07 \pm1.06
LAG-FRPG (ours)88.72±0.6188.72 \pm0.6187.90±0.7687.90 \pm0.7688.26±0.6888.26 \pm0.6878.57±1.0978.57 \pm1.0977.02±1.3177.02 \pm1.3177.75±1.1277.75 \pm1.12
FRPG86.49±1.9886.49 \pm1.9885.47±2.4185.47 \pm2.4182.11±3.4882.11 \pm3.4875.54±1.9975.54 \pm1.9973.87±2.4073.87 \pm2.4066.55±3.3966.55 \pm3.39
Projected FRPG88.68±0.6588.68 \pm0.6585.97±1.5585.97 \pm1.5585.51±1.6685.51 \pm1.6678.49±1.1278.49 \pm1.1273.99±1.8073.99 \pm1.8072.01±1.9072.01 \pm1.90
LFRPG86.30±2.0186.30 \pm2.0185.28±2.4585.28 \pm2.4585.28±2.4585.28 \pm2.4575.19±2.0675.19 \pm2.0673.60±2.4273.60 \pm2.4273.60±2.4273.60 \pm2.42
ℓ2\ell_2-RSA88.49±0.7088.49 \pm0.7085.81±1.6685.81 \pm1.6679.80±3.1579.80 \pm3.1578.18±1.1878.18 \pm1.1873.68±1.8773.68 \pm1.8767.17±2.9267.17 \pm2.92
Trimmed mean89.40±0.1789.40 \pm0.1781.10±4.4481.10 \pm4.4472.90±5.7372.90 \pm5.7376.84±2.3576.84 \pm2.3570.30±3.6970.30 \pm3.6961.79±5.1161.79 \pm5.11
Coord. median81.33±3.3481.33 \pm3.3465.73±7.6765.73 \pm7.6757.60±7.5657.60 \pm7.5672.36±3.8172.36 \pm3.8163.59±6.9163.59 \pm6.9151.85±6.1351.85 \pm6.13
Krum80.37±4.5180.37 \pm4.5165.93±7.8265.93 \pm7.8257.14±5.1657.14 \pm5.1668.18±5.6968.18 \pm5.6959.93±6.9559.93 \pm6.9558.53±7.4158.53 \pm7.41
Geometric median88.92±0.4788.92 \pm0.4784.89±2.4684.89 \pm2.4680.77±2.8280.77 \pm2.8279.51±1.0779.51 \pm1.0774.68±2.3974.68 \pm2.3962.10±4.7862.10 \pm4.78
Byz-EF21-SGDM89.65±0.1989.65 \pm0.1981.41±4.0081.41 \pm4.0081.68±3.9481.68 \pm3.9480.75±0.4880.75 \pm0.4867.76±4.1167.76 \pm4.1167.70±4.4367.70 \pm4.43
FedAdam-BACK84.77±1.4984.77 \pm1.4973.43±4.1773.43 \pm4.1773.38±3.1973.38 \pm3.1974.37±1.5274.37 \pm1.5267.63±3.5767.63 \pm3.5768.03±3.2468.03 \pm3.24

Table I. Test accuracy (%, mean ±\pm standard deviation over 20 seeds) with a=0.3a = 0.3 and B=2B = 2. 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 ln⁡10\ln10. 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 (B=2B = 2) 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 λ=0.5\lambda= 0.5, μ=0.1\mu= 0.1, 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 s=13s = 13 and R=3R = 3, 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-

MethodM: CleanM: Min-MaxM: 8 MiBF: CleanF: Min-MaxF: 8 MiB
Projected full88.72 ± 0.6385.98 ± 1.5685.50 ± 1.6678.55 ± 1.0973.99 ± 1.8072.02 ± 1.90
Shared reserve88.60 ± 0.5788.46 ± 0.6688.43 ± 0.8278.48 ± 1.1178.38 ± 1.0978.07 ± 1.06
Individual top88.68 ± 0.6187.28 ± 1.2988.11 ± 0.8478.62 ± 0.9278.28 ± 1.0478.18 ± 1.07
Uniform common88.32 ± 0.6888.29 ± 0.7088.07 ± 0.7678.14 ± 1.1978.11 ± 1.2277.74 ± 1.25

Table II. Test accuracy (%, mean ± standard deviation over 20 seeds) of four communication formats with the matched objective (λ=0.5\lambda= 0.5, μ=0.1\mu= 0.1, 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 p=7.43×10−6p = 7.43 \times10^{-6}) and by 0.32 percentage points under the 8-MiB budget (p=0.0043p = 0.0043), 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 (p=0.0027p = 0.0027). 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).

MethodM: CleanM: Min-MaxF: CleanF: Min-Max
Projected full6.188 ±\pm 0.1326.770 ±\pm 0.1326.069 ±\pm 0.2896.587 ±\pm 0.281
Shared reserve6.465 ±\pm 0.1666.396 ±\pm 0.1676.393 ±\pm 0.3106.333 ±\pm 0.312
Individual top6.236 ±\pm 0.1406.557 ±\pm 0.1336.271 ±\pm 0.3086.204 ±\pm 0.306
Uniform common7.279 ±\pm 0.2967.148 ±\pm 0.3087.085 ±\pm 0.3667.106 ±\pm 0.341

Table V. Final value of the common objective (2) at 2,000 slots in the matched-objective comparison (mean ±\pm 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%

MethodM: IPMM: Min-MaxF: IPMF: Min-Max
FRPG-CS86.95 ± 1.7086.82 ± 1.7479.25 ± 1.0579.35 ± 1.03
CS: no EF60.02 ± 5.1635.95 ± 3.1936.88 ± 5.0912.54 ± 2.51
CS: no reserve85.62 ± 2.5783.14 ± 3.8878.95 ± 0.9978.96 ± 0.93
CS: no projection2.97 ± 3.0786.85 ± 1.726.74 ± 3.3279.30 ± 1.02
LAG-FRPG85.84 ± 1.8486.10 ± 1.6878.00 ± 0.9978.29 ± 0.82
LAG: no projection3.48 ± 4.3586.09 ± 1.674.31 ± 4.8878.30 ± 0.81

Table III. Ablation study: test accuracy (%, mean ± standard deviation over five seeds) at 2,000 slots with B=2B = 2 and a=0.3a = 0.3. 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 3.43×10−93.43 \times10^{-9}, 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, a∈{0.3,10}a \in\{0.3, 10\}, and five seeds, with λ=0.5\lambda= 0.5 and μ=0.1\mu= 0.1. 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 8.31×10−48.31 \times10^{-4}. Table IV reports the interval that encloses the exact distance ∥u0∗−x∗∥\lVert u_0^* - x^* \rVert of all five seeds, which is deterministic rather than a confidence interval, together with the largest upper bound from the gradient certificate (4).

Data, aaDistance enclosureMax. 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 ∥u0∗−x∗∥\lVert u_0^* - x^* \rVert with λ=0.5\lambda= 0.5 and μ=0.1\mu= 0.1: enclosure of the exact values over five seeds and the largest upper bound from (4). Bold: smallest values per dataset.

With a=0.3a = 0.3, 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 a=10a = 10. The threshold max⁡n∥∇fn(x∗)∥\max_n \|\nabla f_n(x^*)\| ranges from 1.047 to 1.683 on MNIST and from 2.088 to 4.536 on Fashion-MNIST with a=0.3a = 0.3, which exceeds λ=0.5\lambda= 0.5; hence, Aλ>0A_\lambda> 0 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 λ2B2G/δ0\lambda^2 B^2 G/\delta_0 is independent of the compressor, the compression error decays as O(ln⁡K/K2)O(\ln K/K^2) with a tight dependence on the contraction factor, and the expected fraction of lazy uploads decays as O(ln⁡K/K)O(\sqrt{\ln K/K}); 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 FF with respect to w0w_0 and wnw_n with opposite signs, we have

∑n=0N∇nF(w)=∇f0(w0)+∑n=1N∇fn(wn).\sum_{n=0}^{N} \nabla_n F(w) = \nabla f_0(w_0) + \sum_{n=1}^{N} \nabla f_n(w_n).

Therefore,

∇H(w0)=∑n=0N∇nF(w)+∑n=1N[∇fn(w0)−∇fn(wn)]\nabla H(w_0) = \sum_{n=0}^{N} \nabla_n F(w) + \sum_{n=1}^{N} [\nabla f_n(w_0) - \nabla f_n(w_n)]

whose norm is bounded by b(w)b(w) under Assumption 1. The strong monotonicity of ∇H\nabla H gives (4), and minimizing both sides of H(x)≥H(w0)+⟨∇H(w0),x−w0⟩+δΣ2∥x−w0∥2H(x) \ge H(w_0)+\langle\nabla H(w_0), x-w_0\rangle+\frac{\delta_\Sigma}{2}\|x-w_0\|^2 over xx gives (5). For an approximate minimizer uˉ\bar{u} of FF, the strong convexity of FF yields ∥uˉ−u∗∥≤∥∇F(uˉ)∥/δmin⁡\|\bar{u}-u^*\| \le\|\nabla F(\bar{u})\|/\delta_{\min}, and the triangle inequality gives the certificate stated after Lemma 1. Moreover, the strong convexity of FF in w0w_0 yields E∥w0,K−u0∗∥2≤2DK/δ0\mathbb{E}\|w_{0,K}-u_0^*\|^2 \le2D_K/\delta_0, and Minkowski’s inequality in L2L^2 proves (37).

To prove (6), let F~\widetilde{F} denote the function obtained by replacing each Huber penalty in FF with the Euclidean norm. Let u~\tilde{u} denote the minimizer of F~\widetilde{F}, and let xˉ∗:=vec⁡(x∗,…,x∗)\bar{x}^* := \operatorname{vec}(x^*,\ldots,x^*). We use the block norm ∥w∥δ2:=∑n=0Nδn∥wn∥2\|w\|_\delta^2 := \sum_{n=0}^{N}\delta_n\|w_n\|^2. At xˉ∗\bar{x}^*, we choose the subgradients Πλ(∇fn(x∗))\Pi_\lambda(\nabla f_n(x^*)) of the norm penalties, such that a subgradient of F~\widetilde{F} at xˉ∗\bar{x}^* has the blocks −∑n=1Nen,e1,…,eN-\sum_{n=1}^{N} e_n, e_1,\ldots,e_N and the dual norm AλA_\lambda, where the first block follows from ∇H(x∗)=0\nabla H(x^*)=0. The strong monotonicity of F~\widetilde{F} and the weighted Cauchy–Schwarz inequality imply ∥u~−xˉ∗∥δ≤Aλ\|\tilde{u}-\bar{x}^*\|_\delta\le A_\lambda. Since the Huber penalty satisfies 0≤F~(w)−F(w)≤Nλμ/20 \le\widetilde{F}(w)-F(w) \le N\lambda\mu/2, the optimality of u∗u^* for FF gives F~(u∗)−F~(u~)≤Nλμ/2\widetilde{F}(u^*)-\widetilde{F}(\tilde{u}) \le N\lambda\mu/2, and the strong convexity of F~\widetilde{F} yields ∥u∗−u~∥δ≤Nλμ\|u^*-\tilde{u}\|_\delta\le\sqrt{N\lambda\mu}. The triangle inequality and δ0∥u0∗−x∗∥≤∥u∗−xˉ∗∥δ\sqrt{\delta_0}\|u_0^*-x^*\| \le\|u^*-\bar{x}^*\|_\delta prove (6). When only a numerical consensus solution xˉ\bar{x} is available, AλA_\lambda is replaced by the dual norm of the subgradients with the blocks ∇f0(xˉ)+∑n=1NΠλ(∇fn(xˉ))\nabla f_0(\bar{x})+\sum_{n=1}^{N}\Pi_\lambda(\nabla f_n(\bar{x})) and ∇fn(xˉ)−Πλ(∇fn(xˉ))\nabla f_n(\bar{x})-\Pi_\lambda(\nabla f_n(\bar{x})), and ∥∇H(xˉ)∥/δΣ\|\nabla H(\bar{x})\|/\delta_\Sigma is added to the RHS of (6), which is fully computable.

Profiled Loss

Eliminating the local models from (2) gives the profiled loss

Φ(x):=f0(x)+∑n=1Nϕn(x)\Phi(x) := f_0(x) + \sum_{n=1}^{N} \phi_n(x)
ϕn(x):=inf⁡y{fn(y)+λp(x−y)}.\phi_n(x) := \inf_y \{f_n(y) + \lambda p(x-y)\}.

The inner minimizer yn(x)y_n(x) exists and is unique by the strong convexity and the coercivity in yy, the partial minimization preserves the convexity, and the envelope formula gives ∇ϕn(x)=λ∇p(x−yn(x))\nabla\phi_n(x)=\lambda\nabla p(x-y_n(x)) with the norm of at most λ\lambda. Hence, Φ\Phi is δ0\delta_0-strongly convex with the unique minimizer u0∗u_0^*, i.e., the finite-penalty target is a profiled loss with bounded gradient contributions of the workers.

Conditional Bound in Remark 1

If λ>max⁡n∥∇fn(un∗)∥\lambda> \max_n\|\nabla f_n(u_n^*)\|, the stationarity implies u0∗−un∗=μ∇fn(un∗)/λu_0^*-u_n^*=\mu\nabla f_n(u_n^*)/\lambda and hence ∥u0∗−un∗∥<μ\|u_0^*-u_n^*\| < \mu. Summing the stationarity conditions gives ∥∇H(u0∗)∥≤μ∑n=1NLn\|\nabla H(u_0^*)\| \le\mu\sum_{n=1}^{N}L_n, and the strong monotonicity of ∇H\nabla H yields the bound in Remark 1. The condition can fail: for f0(x)=x2/2f_0(x)=x^2/2, f1(x)=(x−4)2/2f_1(x)=(x-4)^2/2, and λ=1\lambda=1, the penalized optimum is (1,3)(1,3) for any 0<μ<20<\mu<2, whereas x∗=2x^*=2.

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 αn,k\alpha_{n,k} and βk\beta_k by αn\alpha_n and β\beta, and let h0:=∇f0(u0,k)h_0 := \nabla f_0(u_{0,k}) and hn:=∇f(un,k;ξn,k)−gn,kh_n := \nabla f(u_{n,k};\xi_{n,k})-g_{n,k} for n≥1n\ge1. Based on (10) and the optimality condition of the proximal operator in (13), we have αn(un,k−wn,k)=hn\alpha_n(u_{n,k}-w_{n,k})=h_n for n=0,…,Nn=0,\ldots,N. For any comparison point x=vec⁡(x0,…,xN)x = \operatorname{vec}(x_0,\ldots,x_N), the smoothness and the strong convexity in Assumptions 1 and 2 give

f0(w0,k)−f0(x0)≤⟨Sk,x0−w0,k⟩+∥Sk∥∥h0∥α0−2α0−L02α02∥h0∥2−δ02∥x0−u0,k∥2−⟨h0+Sk,x0−u0,k⟩\begin{aligned} f_0(w_{0,k}) - f_0(x_0) &\le\langle S_k, x_0-w_{0,k}\rangle+ \frac{\lVert S_k\rVert\lVert h_0\rVert}{\alpha_0} -\frac{2\alpha_0-L_0}{2\alpha_0^2}\lVert h_0\rVert^2 -\frac{\delta_0}{2}\lVert x_0-u_{0,k}\rVert^2 \\ &\quad-\langle h_0+S_k,x_0-u_{0,k}\rangle \end{aligned}
fn(wn,k)−fn(xn)≤⟨Δn,k−gn,k,xn−wn,k⟩−2αn−Ln2αn2∥hn∥2−δn2∥xn−un,k∥2−⟨hn,xn−un,k⟩.\begin{aligned} f_n(w_{n,k})-f_n(x_n) &\le\langle\Delta_{n,k}-g_{n,k},x_n-w_{n,k}\rangle -\frac{2\alpha_n-L_n}{2\alpha_n^2}\lVert h_n\rVert^2 \\ &\quad-\frac{\delta_n}{2}\lVert x_n-u_{n,k}\rVert^2 -\langle h_n,x_n-u_{n,k}\rangle. \end{aligned}

where the second inequality is obtained by starting from fn(xn)≥fn(un,k)+⟨∇fn(un,k),xn−un,k⟩+δn∥xn−un,k∥2/2f_n(x_n)\ge f_n(u_{n,k})+\langle\nabla f_n(u_{n,k}),x_n-u_{n,k}\rangle+\delta_n\lVert x_n-u_{n,k}\rVert^2/2, applying the smoothness upper bound to fn(wn,k)f_n(w_{n,k}), and using ∇fn(un,k)=hn+gn,k−Δn,k\nabla f_n(u_{n,k})=h_n+g_{n,k}-\Delta_{n,k}; the first inequality is obtained similarly by adding and subtracting SkS_k and using ⟨Sk,h0⟩≥−∥Sk∥∥h0∥\langle S_k,h_0\rangle\ge-\lVert S_k\rVert\lVert h_0\rVert. Moreover, the convexity of the penalty function gives

λ[pn(w0,k−wn,k)−pn(x0−xn)]≤⟨gn,k,w0,k−x0+xn−wn,k⟩.\lambda[p_n(w_{0,k}-w_{n,k})-p_n(x_0-x_n)] \le\langle g_{n,k},w_{0,k}-x_0+x_n-w_{n,k}\rangle.

Let h~0:=h0+Sk\widetilde h_0:=h_0+S_k, h~n:=hn\widetilde h_n:=h_n for n≥1n\ge1, and

Ωk:=∥Sk∥∥h0∥α0−∑n=0N2αn−Ln2αn2∥hn∥2.\Omega_k:=\frac{\lVert S_k\rVert\lVert h_0\rVert}{\alpha_0} -\sum_{n=0}^{N}\frac{2\alpha_n-L_n}{2\alpha_n^2}\lVert h_n\rVert^2.

Summing the above inequalities over the server and the honest workers, the penalty gradients of the honest workers cancel, and we obtain

F(wk)−F(x)≤∑n=0N⟨Δn,k,xn−wn,k⟩+Ωk−∑n=0Nδn2∥xn−un,k∥2+⟨h~n,xn−un,k⟩.(42)\begin{aligned} F(w_k)-F(x) &\le\sum_{n=0}^{N}\langle\Delta_{n,k},x_n-w_{n,k}\rangle+\Omega_k\\ &\quad-\sum_{n=0}^{N}\frac{\delta_n}{2}\lVert x_n-u_{n,k}\rVert^2 +\langle\widetilde h_n,x_n-u_{n,k}\rangle. \tag*{(42)} \end{aligned}

where Δ0,k\Delta_{0,k} is the deviation in (25).

The updates (11) and (14) imply that vn,kv_{n,k} minimizes the quadratic function ⟨h~n,x−un,k⟩+δn∥x−un,k∥2/2+αnβ∥x−vn,k−1∥2/2\langle\widetilde h_n,x-u_{n,k}\rangle+\delta_n\lVert x-u_{n,k}\rVert^2/2+\alpha_n\beta\lVert x-v_{n,k-1}\rVert^2/2. After discarding δn∥vn,k−un,k∥2/2≥0\delta_n\lVert v_{n,k}-u_{n,k}\rVert^2/2\ge0, the optimality of vn,kv_{n,k} gives

⟨h~n,x−un,k⟩+δn2∥x−un,k∥2≥⟨h~n,vn,k−un,k⟩+αnβ+δn2∥x−vn,k∥2+αnβ2∥vn,k−vn,k−1∥2−αnβ2∥x−vn,k−1∥2.\begin{aligned} \langle\widetilde h_n,x-u_{n,k}\rangle+\frac{\delta_n}{2}\lVert x-u_{n,k}\rVert^2 &\ge\langle\widetilde h_n,v_{n,k}-u_{n,k}\rangle +\frac{\alpha_n\beta+\delta_n}{2}\lVert x-v_{n,k}\rVert^2\\ &\quad+\frac{\alpha_n\beta}{2}\lVert v_{n,k}-v_{n,k-1}\rVert^2 -\frac{\alpha_n\beta}{2}\lVert x-v_{n,k-1}\rVert^2 . \end{aligned}

We apply (42) at xn=un∗x_n=u_n^* together with the above inequality at x=un∗x=u_n^*, apply (42) at xn=wn,k−1x_n=w_{n,k-1} with its negative strong-convexity terms discarded, and take the convex combination of the two results with the weights β\beta and 1−β1-\beta. Since un,k=(1−β)wn,k−1+βvn,k−1u_{n,k}=(1-\beta)w_{n,k-1}+\beta v_{n,k-1}, the term involving Δn,k\Delta_{n,k} becomes

β⟨Δn,k,un∗−vn,k−1⟩+αn−1⟨Δn,k,hn⟩\beta\langle\Delta_{n,k},u_n^*-v_{n,k-1}\rangle+\alpha_n^{-1}\langle\Delta_{n,k},h_n\rangle

and the remaining linear term is β⟨h~n,vn,k−1−vn,k⟩\beta\langle\widetilde h_n,v_{n,k-1}-v_{n,k}\rangle. For n≥1n\ge1, the remaining linear term is bounded by ∥hn∥2/(2αn)+αnβ2∥vn,k−vn,k−1∥2/2\lVert h_n\rVert^2/(2\alpha_n)+\alpha_n\beta^2\lVert v_{n,k}-v_{n,k-1}\rVert^2/2. For n=0n=0, the first summand is replaced by 2∥h0∥2/(3α0)+2∥Sk∥2/α02\lVert h_0\rVert^2/(3\alpha_0)+2\lVert S_k\rVert^2/\alpha_0 based on ∥h0+Sk∥2≤4∥h0∥2/3+4∥Sk∥2\lVert h_0+S_k\rVert^2\le4\lVert h_0\rVert^2/3+4\lVert S_k\rVert^2. The squared increments ∥vn,k−vn,k−1∥2\lVert v_{n,k}-v_{n,k-1}\rVert^2 cancel the corresponding negative quadratic terms. For the deviation of the server, we use

β⟨Δ0,k,u0∗−v0,k−1⟩≤β2ϵ∥Δ0,k∥2+ϵβ2∥u0∗−v0,k−1∥2.\beta\langle\Delta_{0,k},u_0^*-v_{0,k-1}\rangle \le\frac{\beta}{2\epsilon}\lVert\Delta_{0,k}\rVert^2+\frac{\epsilon\beta}{2}\lVert u_0^*-v_{0,k-1}\rVert^2 .

Finally, completing the squares in ∥hn∥\lVert h_n\rVert gives

∥Sk∥+∥Δ0,k∥α0∥h0∥−2α0−3L06α02∥h0∥2≤3(∥Sk∥+∥Δ0,k∥)22(2α0−3L0)\frac{\lVert S_k\rVert+\lVert\Delta_{0,k}\rVert}{\alpha_0}\lVert h_0\rVert -\frac{2\alpha_0-3L_0}{6\alpha_0^2}\lVert h_0\rVert^2 \le\frac{3(\lVert S_k\rVert+\lVert\Delta_{0,k}\rVert)^2}{2(2\alpha_0-3L_0)}
∥Δn,k∥αn∥hn∥−αn−Ln2αn2∥hn∥2≤∥Δn,k∥22(αn−Ln),n≥1.\frac{\lVert\Delta_{n,k}\rVert}{\alpha_n}\lVert h_n\rVert -\frac{\alpha_n-L_n}{2\alpha_n^2}\lVert h_n\rVert^2 \le\frac{\lVert\Delta_{n,k}\rVert^2}{2(\alpha_n-L_n)},\qquad n\ge1.

Collecting the above steps, the RHS of (27) holds for each sample path with σn2\sigma_n^2 replaced by ∥Δn,k∥2\lVert\Delta_{n,k}\rVert^2 and with the additional term ∑n=1Nβ⟨Δn,k,un∗−vn,k−1⟩\sum_{n=1}^{N}\beta\langle\Delta_{n,k},u_n^*-v_{n,k-1}\rangle. 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 Fk\mathcal{F}_k under Assumption 4. Since neither the unbiasedness of Δ0,k\Delta_{0,k} 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 ϵ=δ0/2\epsilon=\delta_0/2 and νn,k:=(δn/βk+αn,k)/2\nu_{n,k}:=(\delta_n/\beta_k+\alpha_{n,k})/2, and let Ξk\Xi_k denote the sum of the last four terms on the RHS of (27) divided by βk2\beta_k^2. Since δn≥0\delta_n\ge0 and ∑k=1K(1−βk)/βk2≤1/βk−12\sum_{k=1}^{K}(1-\beta_k)/\beta_k^2\le1/\beta_{k-1}^2, dividing (27) by βk2\beta_k^2 and summing over k=1,…,Kk=1,\ldots,K give

DKβK2+∑n=0Nνn,KE∥un∗−vn,K∥2≤Λ0+∑k=1KΞk.(43)\frac{D_K}{\beta_K^2}+\sum_{n=0}^{N}\nu_{n,K}\mathbb{E}\lVert u_n^*-v_{n,K}\rVert^2 \le\Lambda_0+\sum_{k=1}^{K}\Xi_k . \tag*{(43)}

Indeed, the interior coefficients of E∥un∗−vn,k∥2\mathbb{E}\lVert u_n^*-v_{n,k}\rVert^2 are [α0,k+1−α0,k+ϵ/βk+1−δ0/βk]/2=3δ0(1−k)/56[\alpha_{0,k+1}-\alpha_{0,k}+\epsilon/\beta_{k+1}-\delta_0/\beta_k]/2=3\delta_0(1-k)/56 for the server and [αn,k+1−αn,k−δn/βk]/2=δn(1−k)/28[\alpha_{n,k+1}-\alpha_{n,k}-\delta_n/\beta_k]/2=\delta_n(1-k)/28 for the honest workers, all of which are nonpositive, and the initial terms are bounded by Λ0\Lambda_0 in (32) since β0=1\beta_0=1. Substituting the stepsizes (7) and (8), we have 2(α0,k−3L0)βk2=8δ0/72(\alpha_{0,k}-3L_0)\beta_k^2=8\delta_0/7, 2(αn,k−Ln)βk2=12δn/72(\alpha_{n,k}-L_n)\beta_k^2=12\delta_n/7, and 2/(α0,kβk2)≤7/δ02/(\alpha_{0,k}\beta_k^2)\le7/\delta_0, which yield

Ξk≤218δ0E(∥Sk∥+∥Δ0,k∥)2+7δ0E∥Sk∥2+∑n=1N7σn212δn+k+22δ0E∥Δ0,k∥2.(44)\Xi_k\le\frac{21}{8\delta_0}\mathbb{E}(\lVert S_k\rVert+\lVert\Delta_{0,k}\rVert)^2+\frac{7}{\delta_0}\mathbb{E}\lVert S_k\rVert^2+\sum_{n=1}^{N}\frac{7\sigma_n^2}{12\delta_n}+\frac{k+2}{2\delta_0}\mathbb{E}\lVert\Delta_{0,k}\rVert^2. \tag*{(44)}

Based on (26), we have ∥Sk∥≤QλG\lVert S_k\rVert\le Q\lambda\sqrt{G} and ∥Δ0,k∥≤(Q+N)λG\lVert\Delta_{0,k}\rVert\le(Q+N)\lambda\sqrt{G}. With

ηˉ:=[7Q2+218(2Q+N)2]λ2Gδ0+∑n=1N7σn212δn\bar{\eta}:=\left[7Q^2+\frac{21}{8}(2Q+N)^2\right]\frac{\lambda^2G}{\delta_0}+\sum_{n=1}^{N}\frac{7\sigma_n^2}{12\delta_n}

we therefore obtain

Dkβk2+∑n=0Nνn,kE∥un∗−vn,k∥2≤Λ0+kηˉ+(k2+5k)(Q+N)2λ2G4δ0.\frac{D_k}{\beta_k^2}+\sum_{n=0}^{N}\nu_{n,k}\mathbb{E}\lVert u_n^*-v_{n,k}\rVert^2\le\Lambda_0+k\bar{\eta}+\frac{(k^2+5k)(Q+N)^2\lambda^2G}{4\delta_0}.

Using 4k/(k+2)2≤1/24k/(k+2)^2\le1/2 and (k2+5k)/(k+2)2≤25/24(k^2+5k)/(k+2)^2\le25/24, we have Dk≤Dˉ:=Λ0+ηˉ/2+25(Q+N)2λ2G/(24δ0)D_k\le\bar{D}:=\Lambda_0+\bar{\eta}/2+25(Q+N)^2\lambda^2G/(24\delta_0), and the strong convexity gives E∥wn,k−un∗∥2≤2Dˉ/δn\mathbb{E}\lVert w_{n,k}-u_n^*\rVert^2\le2\bar{D}/\delta_n. Let κ0:=δ0/14\kappa_0:=\delta_0/14 and κn:=3δn/14\kappa_n:=3\delta_n/14 for n≥1n\ge1, such that νn,k≥κn(k+2)2/2\nu_{n,k}\ge\kappa_n(k+2)^2/2. Hence, Lemma 3 holds with

Vn=max⁡{2Dˉδn,2κn[Λ09+ηˉ8+25(Q+N)2λ2G96δ0]}.(45)V_n=\max\left\{\frac{2\bar{D}}{\delta_n},\frac{2}{\kappa_n}\left[\frac{\Lambda_0}{9}+\frac{\bar{\eta}}{8}+\frac{25(Q+N)^2\lambda^2G}{96\delta_0}\right]\right\}. \tag*{(45)}

The same bounds hold at k=0k=0, since D0≤Λ0D_0\le\Lambda_0 and Λ0≥αn,1∥un∗−vn,0∥2/2≥9κn∥un∗−vn,0∥2/2\Lambda_0\ge\alpha_{n,1}\lVert u_n^*-v_{n,0}\rVert^2/2\ge9\kappa_n\lVert u_n^*-v_{n,0}\rVert^2/2. 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 h0,k:=∇f0(u0,k)h_{0,k}:=\nabla f_0(u_{0,k}) and hn,k:=∇f(un,k;ξn,k)−gn,kh_{n,k}:=\nabla f(u_{n,k};\xi_{n,k})-g_{n,k} for n≥1n\ge1, the updates imply

wn,k−wn,k−1=βk(vn,k−1−wn,k−1)−hn,k/αn,k.w_{n,k}-w_{n,k-1}=\beta_k(v_{n,k-1}-w_{n,k-1})-h_{n,k}/\alpha_{n,k}.

Lemma 3 gives E∥vn,k−1−wn,k−1∥2≤4Vn\mathbb{E}\lVert v_{n,k-1}-w_{n,k-1}\rVert^2\le4V_n and E∥un,k−un∗∥2≤Vn\mathbb{E}\lVert u_{n,k}-u_n^*\rVert^2\le V_n. At the penalized optimum, we have ∥∇f0(u0∗)∥≤NλG\lVert\nabla f_0(u_0^*)\rVert\le N\lambda\sqrt{G} and ∥∇fn(un∗)∥≤λG\lVert\nabla f_n(u_n^*)\rVert\le\lambda\sqrt{G}. Consequently, E∥hn,k∥2≤Γn\mathbb{E}\lVert h_{n,k}\rVert^2\le\Gamma_n with

Γ0:=2N2λ2G+2L02V0\Gamma_0:=2N^2\lambda^2G+2L_0^2V_0
Γn:=9λ2G+6Ln2Vn+3σn2,n≥1.(46)\Gamma_n:=9\lambda^2G+6L_n^2V_n+3\sigma_n^2,\qquad n\ge1. \tag*{(46)}

where the bound for the honest workers uses ∥∇fn(u)+Δ−g∥2≤3(∥∇fn(u)∥2+∥Δ∥2+∥g∥2)\lVert\nabla f_n(u)+\Delta-g\rVert^2\le3(\lVert\nabla f_n(u)\rVert^2+\lVert\Delta\rVert^2+\lVert g\rVert^2) without assuming the independence of gg and Δ\Delta. Using (k+2)2≥9(k+2)^2\ge9, we obtain

E∥w0,k−w0,k−1∥2≤32V0+392Γ0/(9δ02)(k+2)2\mathbb{E}\lVert w_{0,k}-w_{0,k-1}\rVert^2\le\frac{32V_0+392\Gamma_0/(9\delta_0^2)}{(k+2)^2}
E∥wn,k−wn,k−1∥2≤32Vn+392Γn/(81δn2)(k+2)2.\mathbb{E}\lVert w_{n,k}-w_{n,k-1}\rVert^2\le\frac{32V_n+392\Gamma_n/(81\delta_n^2)}{(k+2)^2}.

The Lipschitz continuity of ∇pn\nabla p_n and the inequality ∥a+b∥2≤2∥a∥2+2∥b∥2\lVert a+b\rVert^2\le2\lVert a\rVert^2+2\lVert b\rVert^2 yield (29) with

χn:=2λ2Lp2[32(V0+Vn)+392Γ09δ02+392Γn81δn2].(47)\chi_n:=2\lambda^2L_p^2\left[32(V_0+V_n)+\frac{392\Gamma_0}{9\delta_0^2}+\frac{392\Gamma_n}{81\delta_n^2}\right]. \tag*{(47)}

Proof of Lemma 5 and Tightness of Its Contraction Dependence

Proof of Lemma 5

We fix an honest worker nn, write γ:=γn\gamma:=\gamma_n and q:=1−γq:=1-\gamma, and omit the index nn. Since both gkg_k and g^k−1\hat{g}_{k-1} belong to the ball with radius λG\lambda\sqrt{G}, the nonexpansiveness of the projection and the contraction (17) imply the uniform cap ζk≤4qλ2G\zeta_k\le4q\lambda^2G for k≥1k\ge1. For 0<γ<10<\gamma<1, we follow the tracking recurrence of EF21 [12 Suppl., Lemma 2]: since the projection is nonexpansive with respect to gkg_k, applying Young’s inequality with the parameter γ/(2q)\gamma/(2q) to zk=(gk−gk−1)−(g^k−1−gk−1)z_k=(g_k-g_{k-1})-(\hat{g}_{k-1}-g_{k-1}) and using Lemma 4, we obtain

ζk≤(1−γ/2)ζk−1+q(2−γ)χγ(k+2)2.\zeta_k\le(1-\gamma/2)\zeta_{k-1}+\frac{q(2-\gamma)\chi}{\gamma(k+2)^2}.

For k≤Jk\le J, the uniform cap proves (27). For k≥J+1k\ge J+1, the inductive hypothesis and k+1≥8/γk+1\ge8/\gamma give

(1−γ/2)(k+2k+1)2≤(1−γ/2)(1+γ/8)2=1−γ/4−7γ2/64−γ3/128≤1−γ/4(1-\gamma/2)\left(\frac{k+2}{k+1}\right)^2\le(1-\gamma/2)(1+\gamma/8)^2 =1-\gamma/4-7\gamma^2/64-\gamma^3/128 \le1-\gamma/4

and the second term of the recurrence is absorbed since K≥4q(2−γ)χ/γ2K\ge4q(2-\gamma)\chi/\gamma^2. For γ=1\gamma=1, the contraction makes the state of the honest worker exact per slot, which proves the result separately. Since J+2≤11/γJ+2\le11/\gamma, the simplified bound on KnK_n follows.

Tightness of the Contraction Dependence

The following lemma shows that the order (1−γ)/γ2(1-\gamma)/\gamma^2 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 gk=gˉsin⁡ln⁡(k+2)g_k=\bar{g}\sin\ln(k+2) with 0<gˉ≤λG0<\bar{g}\le\lambda\sqrt{G}, which satisfies (29) with χ=gˉ2/4\chi=\bar{g}^2/4, and the compressor that uploads the full residual with probability γ\gamma independently per slot. The tracking error ζk:=E∣g^k−gk∣2\zeta_k:=\mathbb{E}|\hat{g}_k-g_k|^2 satisfies

lim sup⁡k→∞(k+2)2ζk=gˉ2(1−γ)(2−γ)/γ2.(48)\limsup_{k\to\infty}(k+2)^2\zeta_k=\bar{g}^2(1-\gamma)(2-\gamma)/\gamma^2. \tag*{(48)}

To prove Lemma 6, note that ∣gk∣≤gˉ|g_k|\le\bar{g} and ∣gk−gk−1∣2≤(gˉ2/4)/(k+2)2|g_k-g_{k-1}|^2\le(\bar{g}^2/4)/(k+2)^2. The compressor uploads zkz_k with probability γ\gamma and zero otherwise, which satisfies (17) with the contraction factor γ\gamma; the projection is inactive, since each state is either zero or a previous value of the signal. With q:=1−γq:=1-\gamma, the most recent upload has the age i∈{0,…,k−1}i\in\{0,\ldots,k-1\} with probability γqi\gamma q^i, and no upload has occurred with probability qkq^k. Hence, we have

ζk=γ∑i=0k−1qi(gk−i−gk)2+qkgk2.\zeta_k=\gamma\sum_{i=0}^{k-1}q^i(g_{k-i}-g_k)^2+q^k g_k^2.

For each fixed ii, we have (k+2)(gk−i−gk)=gˉ[−gˉcos⁡ln⁡(k+2)+o(1)](k+2)(g_{k-i}-g_k)=\bar{g}\left[-\bar{g}\cos\ln(k+2)+o(1)\right], whose magnitude is at most 2gˉ2\bar{g} for i≤k/2i \le k/2; the contribution of the ages i>k/2i > k/2 is bounded by a constant times k2qk/2k^2q^{k/2} and tends to zero. The dominated convergence with the summable geometric weights therefore gives

(k+2)2ζk=gˉ2q(1+q)γ2cos⁡2ln⁡(k+2)+o(1).(k+2)^2\zeta_k=\frac{\bar{g}^2q(1+q)}{\gamma^2}\cos^2\ln(k+2)+o(1).

Since the cosine tends to one along the integer subsequence nearest to exp⁡(2πj)−2\exp(2\pi j)-2, j=1,2,…j=1,2,\ldots, the limit superior is gˉ2(1−γ)(2−γ)/γ2\bar{g}^2(1-\gamma)(2-\gamma)/\gamma^2 for 0<γ<10<\gamma<1, and the tracking error is zero for γ=1\gamma=1.

Proofs of Theorems 1 and 2

Proof of Theorem 1

For any θ>0\theta>0, the decomposition Δ0,k=Bk+Ek\Delta_{0,k}=B_k+E_k and the bounds in (22) imply

∥Δ0,k∥2≤(1+θ)B2λ2G+(1+1θ)∥Ek∥2\left\|\Delta_{0,k}\right\|^2\le(1+\theta)B^2\lambda^2G+\left(1+\frac{1}{\theta}\right)\left\|E_k\right\|^2
[∥Sk∥+∥Δ0,k∥]2≤(1+θ)(Q+B)2λ2G+(1+1θ)∥Ek∥2.\left[\left\|S_k\right\|+\left\|\Delta_{0,k}\right\|\right]^2\le(1+\theta)(Q+B)^2\lambda^2G+\left(1+\frac{1}{\theta}\right)\left\|E_k\right\|^2.

Therefore, the RHS of (40) is at most

η(θ)+(1+θ)(k+2)B2λ2G2δ0+1+1/θ8δ0(4k+29)E∥Ek∥2.(49)\eta(\theta)+\frac{(1+\theta)(k+2)B^2\lambda^2G}{2\delta_0}+\frac{1+1/\theta}{8\delta_0}(4k+29)\mathbb{E}\left\|E_k\right\|^2. \tag*{(49)}

Substituting the above bound into (39), discarding the non-negative distance terms, using ∑k=1K(k+2)=(K2+5K)/2\sum_{k=1}^{K}(k+2)=(K^2+5K)/2, and multiplying both sides by βK2=4/(K+2)2\beta_K^2=4/(K+2)^2, we obtain (30) with

CK=1+1/θ2δ0(K+2)2∑k=1K(4k+29)E∥Ek∥2.C_K=\frac{1+1/\theta}{2\delta_0(K+2)^2}\sum_{k=1}^{K}(4k+29)\mathbb{E}\left\|E_k\right\|^2.

Based on Lemma 5 and Minkowski’s inequality in L2L^2, we have E∥Ek∥2≤(∑n=1Nκn)2/(k+2)2\mathbb{E}\left\|E_k\right\|^2\le\left(\sum_{n=1}^{N}\sqrt{\kappa_n}\right)^2/(k+2)^2, which proves (31) together with ∑k=1K(4k+29)/(k+2)2≤4ln⁡((K+2)/2)+21c2\sum_{k=1}^{K}(4k+29)/(k+2)^2\le4\ln((K+2)/2)+21c_2. Fixing θ>0\theta>0 before taking K→∞K\to\infty and then taking the infimum over θ\theta give (32).

Proof of Theorem 2

Based on (19), we have ∥Ek∥2≤N2τk\left\|E_k\right\|^2\le N^2\tau_k for each sample path. The proof of Theorem 1 holds unchanged up to the definition of CKC_K, and the threshold (18) gives

(4k+29)E∥Ek∥2≤11N2τ0λ2Gln⁡(k+2).(4k+29)\mathbb{E}\left\|E_k\right\|^2\le\frac{11N^2\tau_0\lambda^2G}{\ln(k+2)}.

To bound the sum over kk, we compare it with ∫2K+2dt/ln⁡t\int_{2}^{K+2}dt/\ln t. For t≥e2t\ge e^2, the derivative of 2t/ln⁡t2t/\ln t is at least 1/ln⁡t1/\ln t; moreover, ∫2e2dt/ln⁡t≤(e−2)/ln⁡2+e2−e<e2\int_{2}^{e^2}dt/\ln t\le(e-2)/\ln2+e^2-e<e^2, and the finitely many integers K+2<e2K+2<e^2 satisfy the same bound directly. Consequently, we have ∑k=1K1/ln⁡(k+2)≤2(K+2)/ln⁡(K+2)\sum_{k=1}^{K}1/\ln(k+2)\le2(K+2)/\ln(K+2), which yields (34).

Proof of Corollary 1

Let ϑk:=∥gn,k−g^n,k∥/ωk\vartheta_k:=\left\|g_{n,k}-\widehat{g}_{n,k}\right\|/\omega_k denote the normalized tracking error of honest worker nn. An upload resets the tracking error to zero, and a skipped upload ensures ϑk≤1\vartheta_k\le1. Based on the trigger rule (17) and the triangle inequality, we have

ln⁡n,k+ϑk≤ωk−1ωkϑk−1+∥gn,k−gn,k−1∥ωk≤ϑk−1+ωk−1ωk−1+∥gn,k−gn,k−1∥ωk.\begin{aligned} \ln_{n,k}+\vartheta_k\le\frac{\omega_{k-1}}{\omega_k}\vartheta_{k-1}+\frac{\left\|g_{n,k}-g_{n,k-1}\right\|}{\omega_k} \\ &\le\vartheta_{k-1}+\frac{\omega_{k-1}}{\omega_k}-1+\frac{\left\|g_{n,k}-g_{n,k-1}\right\|}{\omega_k}. \end{aligned}

for k≥2k\ge2, and ln⁡1,1+ϑ1≤1\ln_{1,1}+\vartheta_1\le1 regardless of the initial residual. Summing over kk and dropping ϑK≥0\vartheta_K\ge0 give (35) for each sample path with ∥gn,k−gn,k−1∥\left\|g_{n,k}-g_{n,k-1}\right\| in place of χn/(k+2)\sqrt{\chi_n}/(k+2), 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 ωk−1/ωk≤(k+2)/(k+1)\omega_{k-1}/\omega_k\le(k+2)/(k+1) for k≥2k\ge2, since ln⁡x/x\ln x/x decreases for x≥3x\ge3. Moreover, we have ∑k=2K(k+2)−1/2≤2(M−3)\sum_{k=2}^{K}(k+2)^{-1/2}\le2(\sqrt{M}-\sqrt{3}), ln⁡(k+2)≤ln⁡M\ln(k+2)\le\ln M, and ∑k=2K1/(k+1)≤ln⁡((K+1)/2)\sum_{k=2}^{K}1/(k+1)\le\ln((K+1)/2). Substituting these bounds into (35) proves (36).

For the alternative threshold discussed after Corollary 1, i.e.,

τk=τˉln⁡2(k+2)/(k+2)2(50)\tau_k=\bar{\tau}\ln^2(k+2)/(k+2)^2 \tag*{(50)}

we have

E[Un,K]≤1+2χn/τˉln⁡M+ln⁡K+12(51)\mathbb{E}[U_{n,K}]\le1+\frac{2\sqrt{\chi_n/\bar{\tau}}}{\ln M}+\ln\frac{K+1}{2} \tag*{(51)}
CK≤11(1+1/θ)N2τˉ2δ0M2ln⁡2Mln⁡(M/2).(52)C_K\le\frac{11(1+1/\theta)N^2\bar{\tau}}{2\delta_0M^2}\ln^2 M\ln(M/2). \tag*{(52)}

Indeed, ωk=τˉln⁡(k+2)/(k+2)\omega_k=\sqrt{\bar{\tau}}\ln(k+2)/(k+2) decreases for k≥1k\ge1 and obeys the same bound on ωk−1/ωk\omega_{k-1}/\omega_k, such that ∑k=2K1/ln⁡(k+2)≤2M/ln⁡M\sum_{k=2}^{K}1/\ln(k+2)\le2M/\ln M proves (47); moreover, (4k+29)τk≤11τˉln⁡2M/(k+2)(4k+29)\tau_k\le11\bar{\tau}\ln^2M/(k+2) together with ∑k=1K1/(k+2)≤ln⁡(M/2)\sum_{k=1}^{K}1/(k+2)\le\ln(M/2) and the definition of CKC_K proves (48). Hence, the expected fraction of uploading slots vanishes as O(1/ln⁡K)O(1/\ln K), and the additional objective error is O(ln⁡3K/K2)O(\ln^3 K/K^2).

Implementation Details

  1. Implementation Conventions: The proximal operator of the Huber penalty is prox⁡tp(v)=μv/(μ+t)\operatorname{prox}_{t_p}(v)=\mu v/(\mu+t) when ∥v∥≤μ+t\|v\|\le\mu+t, and (1−t/∥v∥)v(1-t/\|v\|)v otherwise. A valid smoothness constant of the softmax regression is Ln=ρ+12Dn∑i∈Dn∥φi∥2L_n=\rho+\frac{1}{2D_n}\sum_{i\in D_n}\|\varphi_i\|^2 with φi\varphi_i being the feature vector of sample ii, since the covariance of the class probabilities has a spectral norm of

at most 1/21/2. The benchmarks that aggregate loss gradients use the ridge weight ρ+ρ0/N=0.02\rho+ \rho_0/N = 0.02, which matches the consensus problem (1) normalized by NN. The honest workers use the exact penalty gradient in (10c), including the slots with compressed or skipped uploads. LFRPG uses a frame of TT 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 1/(1+k/1000)1/(1 + k/1000). The robust aggregation rules use a local exponential moving average with the momentum of zero or 0.90.9 selected by validation. Krum scores the Q−B−2Q-B-2 nearest vectors of the other workers, and the trimmed mean removes BB entries per coordinate tail. The geometric median uses the smoothed Weiszfeld iterations with the distance floor 10−610^{-6}, the relative tolerance 10−710^{-7}, 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 N−1N-1 nearest neighbors; it applies the bias correction to the second moment only, and the offset of its denominator is 10−8=10−4\sqrt{10^{-8}} = 10^{-4}.

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 λ=0.5\lambda= 0.5, μ=0.1\mu= 0.1, 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 b^=B\hat{b} = B, 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 wrefw_{\mathrm{ref}}, which satisfies the certificate

0≤F(wref)−F(w∗)≤∥∇F(wref)∥22δmin⁡(53)0 \le F(w_{\mathrm{ref}}) - F(w^*) \le\frac{\lVert\nabla F(w_{\mathrm{ref}}) \rVert^2}{2\delta_{\min}} \tag*{(53)}

with the RHS below 3.43×10−93.43 \times10^{-9} 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 ±\pm 0.64% versus 87.98 ±\pm 0.90% on MNIST and 78.60 ±\pm 1.51% versus 78.63 ±\pm 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.

  1. Consensus Diagnostics: Let uˉ\bar{u} and xˉ\bar{x} denote the numerical solutions of the penalized problem (2) and the consensus problem (1), respectively, with εF:=∥∇F(uˉ)∥/δmin⁡\varepsilon_F := \|\nabla F(\bar{u})\|/\delta_{\min} and εH:=∥∇H(xˉ)∥/δΣ\varepsilon_H := \|\nabla H(\bar{x})\|/\delta_{\Sigma}. The exact model bias ∥u0⋆−x⋆∥\|u_0^\star-x^\star\| lies between [∥uˉ0−xˉ∥−εF−εH]+[\|\bar{u}_0-\bar{x}\|-\varepsilon_F-\varepsilon_H]_+ and ∥uˉ0−xˉ∥+εF+εH\|\bar{u}_0-\bar{x}\|+\varepsilon_F+\varepsilon_H, which gives the enclosures in Table IV. Over the 20 reference problems, the largest gradient norm of the consensus solutions is 7.903×10−77.903\times10^{-7}, and the largest certificate (5) of the consensus objective is 1.562×10−121.562\times10^{-12}.

References

  1. [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. [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. [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. [4]S. U. Stich, J.-B. Cordonnier, and M. Jaggi, “Sparsified SGD with memory,” in Adv. Neural Inf. Process. Syst., vol. 31, 2018.
  5. [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. [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. [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. [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. [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. [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. [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. [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. [13]T. Yang et al., “Applied federated learning: Improving Google keyboard query suggestions,” arXiv:1812.02903, 2018.arxiv.org/abs/1812.02903
  14. [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. [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. [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. [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. [18]——, “Byzantine-robust learning on heterogeneous datasets via bucketing,” in Proc. ICLR, 2022.
  19. [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. [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. [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. [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
  23. [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
  24. [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
  25. [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
  26. [27]V. Shejwalkar and A. Houmansadr, “Manipulating the Byzantine: Optimizing model poisoning attacks and defenses for federated learning,” in Proc. NDSS, 2021.DOI
  27. [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
  28. [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
  29. [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
  30. [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
  31. [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
  32. [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
  33. [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
  34. [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
  35. [36]L. Xu, J. Chen, H. Ko, W. Wang, and Y. Dong, “FedAdam-BACK: A compression-based Byzantine-resilient federated learning,” 2026, unpublished manuscript.
  36. [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
  37. [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
  38. [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
  39. [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.
  40. [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.
  41. [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
  42. [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
  43. [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
  44. [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.
  45. [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

Paper details

vlnc:W_b78qvpk4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents