Optimal Byzantine-resilient Federated Learning with User-level Differential Privacy

Optimal Byzantine-resilient Federated Learning with User-level Differential Privacy

arXiv:2611.10898v1 [cs.LG] 7 Nov 2026

1

Ming Xiang1 Stratis Ioannidis1 Edmund Yeh1 Carlee Joe-Wong2 Lili Su1 Northeastern University, Boston, MA, USA; 2 Carnegie Mellon University, Pittsburgh, PA, USA. {xiang.mi,e.ioannidis,e.yeh,l.su}@northeastern.edu, cjoewong@andrew.cmu.edu

Abstract Real-world deployment of federated learning (FL) requires resilience against adversarial clients and data privacy. Byzantine fault captures the worst-case behavior of adversarial clients, while differential privacy (DP) provides statistical guarantees against privacy loss. In particular, user-level DP guards a client’s entire contribution and provides more realistic protection against information leakage. Despite intensive efforts, the minimax-optimal convergence bound of Byzantine-resilient FL with user-level DP remains open. We establish an information-theoretic lower bound for any Byzantine-resilient empirical risk minimization problem under userlevel DP and heterogeneous clients. We propose ByzULDP, a central DP algorithm featuring a two-level momentum across the client and server. Client-side momentum mitigates stochastic gradient variance during robust aggregation. Unlike the fault-free case, naively combining non-linear Byzantine-resilient aggregation with central DP noise can be insufficient to guarantee convergence to a bounded neighborhood of a stationary point. Our key contribution is a server-side momentum that leverages a property specific to user-level DP, where privacy sensitivity depends on how client updates are constructed, to empower convergence. ByzULDP achieves the order-optimal convergence bound for strongly-convex objectives, with vanishing √ error terms decaying at the optimal O(1/T ) and O(1/ T ) rates for stronglyconvex and non-convex objectives, respectively. We corroborate our analysis with numerical experiments on real-world datasets across diverse privacy budgets.

1

Introduction

Federated learning (FL) enables large-scale AI/ML training without transmitting raw local data through collaboration between a parameter server (PS) and clients. Its success has been evidenced by widespread commercial deployments in diverse fields such as autonomous vehicles [18, 56, 74], the Internet of things [30, 55, 75], and natural language processing [47, 49, 53]. While FL keeps raw data locally, shared model parameters can still leak sensitive information about clients’ training data [12, 38]. Differential privacy (DP) provides statistical guarantees against such leakage [26], with the client as the natural unit of protection. In regulated domains such as healthcare and finance, the aggregating server operates as a trusted intermediary under legal accountability. The privacy threat comes from external auditors or curious clients, who attempt to infer sensitive information about participating clients. Meanwhile, FL operates over a complex and heterogeneous client population [40], where faulty or abnormal clients arise due to software or hardware bugs [58], poisoned data [59], or adversarial manipulations [72]. Such unstructured failures are well captured by the Byzantine failure model [50]. Byzantine-resilience [17, 19, 70] and user-level DP [37, 45, 66] have each received extensive attention in isolation. However, real-world deployments, such as healthcare, mobile personalization, and financial collaborations, require addressing both of them simultaneously. Their integration is fundamentally challenging: Byzantine-resilience aims to preserve 40th Conference on Neural Information Processing Systems (NeurIPS 2026).

the utility by discriminating adversarial updates, whereas user-level DP aims to obscure clients’ contributions, potentially drowning useful signals. We therefore ask: Question: Under a trusted server, what is the minimax-optimal convergence bound of user-level DP empirical risk minimization (ERM) under Byzantine adversaries and heterogeneous clients? Combining DP and Byzantine-resilience remains largely underexplored. One line of work provides per-step privacy guarantees [34, 51, 67, 76], yielding a loose cumulative privacy cost that grows with the number of rounds T . Only a handful of works study the synthesis of DP and Byzantine-resilience with multi-round guarantees. Allouah et al. [7] and Gu et al. [33] both consider item-level DP with Byzantine resilience, with the analysis of the latter requiring i.i.d. clients. Yet, FL is by definition heterogeneous, and item-level DP often provides insufficient protection against user-level leakage [45]. For example, in a specialized hospital, client records often exhibit correlated structures. Per-item perturbations cannot fully mask cross-record correlations, leaving the cumulative client signature recoverable. Closer to our setting, Allouah et al. [8] achieve user-level DP without a trusted server via locally correlated noise injection at each client, seeking to attain the utility of central DP algorithms, where the server is trusted. In the absence of Byzantine adversaries, central DP is known to achieve a favorable privacy-utility trade-off [25]. However, the minimax-optimal convergence bound for Byzantine-resilient ERM with user-level DP remains open. Contributions. In this work, we establish order-matching lower and upper bounds for Byzantineresilient ERM with user-level DP. The lower bound is privacy-regime agnostic, while the upper bound is attained by a central DP algorithm, showing that central DP suffices to achieve the optimum. Our contributions are fourfold: • In Section 4, we establish an information-theoretic lower bound for any Byzantine-resilient ERM problem under user-level DP constraints and heterogeneous clients. • In Section 5, we propose the ByzULDP, which features two-level momentum across the client and the server. Client-side momentum mitigates stochastic gradient variance during robust aggregation, which ensures Byzantine resilience. Server-side momentum reshapes each client’s contribution so that the privacy sensitivity achieves a reduction specific to user-level DP, enabling convergence. • In Section 6, we provide two convergence results for ByzULDP. For strongly convex objectives, the non-vanishing errors match our lower bound, and the vanishing error terms decay at the optimal O(1/T √) rate for stochastic first-order methods. For non-convex objectives, we obtain the optimal O(1/ T ) rate on the vanishing error terms. • In Section 7, we corroborate our analysis with numerical experiments on real-world datasets across a range of privacy budgets.

2

Related Work

User-level Private Learning. Without Byzantine resilience, user-level private learning has received growing attention. For example, Badih et al. [11] study user-level DP for PAC learning and characterize the number of clients required to learn a concept class. The seminal work [45] by Levy et al. studies user-level DP for mean estimation, ERM, and stochastic convex optimization (SCO) under homogeneous client distributions or mildly heterogeneous data. Bassily et al. [16] and Liu et al. [48] both achieve the optimal rates for user-level DP-SCO, with the latter adopting more relaxed assumptions on how the number of clients scales with the problem dimension. Another line of work explores intermediate threat models bridging local and central DP by using cryptographic techniques or anonymization via shuffling [22, 39]. Yet, Byzantine clients fundamentally alter the problem. Most prior work relies on a simple mean aggregation, which is highly vulnerable to adversarial updates. Naively combining robust aggregators with DP noise is insufficient to guarantee convergence to a bounded neighborhood of a stationary point, as these nonlinear aggregators often exhibit high privacy sensitivity; see Remark 2 for details. Byzantine-resilient Learning. Tolerating Byzantine attacks in distributed learning has received intensive attention [4, 17, 19, 27, 28, 31, 41, 42, 61, 63, 70, 73]. A robust aggregator is the most common way to mitigate the negative impacts of adversarial updates from Byzantine clients. Numerous robust aggregators have been developed over the recent years, including Geometric Median [19], Krum [17], Coordinate-wise Trimmed Mean [73], Coordinate-wise Median [73], Bulyan [35], and centered clipping [42]. Yet, their original analysis is under a simplified i.i.d. setting. Karimireddy et 2

al. [41] and Allouah et al. [4] have shown that any distributed algorithm can only reach a neighborhood of a stationary point in the presence of coupled non-i.i.d. data and Byzantine faults. Karimireddy et al. [41] propose a simple bucketing mechanism to reduce the likelihood that any subset of clients is consistently compromised. Allouah et al. [4] propose nearest-neighbor mixing, which remixes the clients’ updates with their closest neighbors to obtain a better representation of the global gradient. Robust learning and estimation with DP. Recent advances focus on the user-level private-mean estimation problem with [1, 21, 43] or without Byzantine adversaries [2, 32, 54], where the clients send the perturbed local data to the server only once. However, FL prohibits direct data transmission and requires multi-round interactions. Another line of work leverages cryptographic techniques, e.g., homomorphic encryption and secure multi-party computation to reconcile robustness and privacy [23, 24], but these approaches incur prohibitive computation overhead when combined with robust aggregations. Recently, Allouah et al. [7] establish a privacy-utility-robustness trilemma for item-level DP in the presence of Byzantine adversaries. Gu et al. [33] also study item-level DP and propose algorithms in both local and central DP modes, yet their analysis is only applicable to i.i.d. clients. Allouah et al. [8] consider user-level DP with an untrusted server and propose an algorithm that uses correlated local noise to achieve utility comparable to central DP algorithms. We establish an improved convergence bound in the central DP setting; see Remark 1 for details.

3

Problem Formulation

Federated Learning System. We consider the classic master-slave architecture with a collection of n clients and a PS. The clients hold local data sets D1 , . . . , Dn . The local loss function at client i is defined as Fi (θ) ≜ E(x,y)∼Di [ℓ(θ, (x, y))], where, with a little abuse of notation, E(x,y)∼Di can be understood as taking expectation over the empirical data distribution. The global objective is the average of clients’ local loss functions: n 1X F (θ) ≜ Fi (θ). n i=1 Threat model. We consider an FL environment with two simultaneous threats: Byzantine faults and client privacy leakage. The PS aims to robustly learn a model despite malicious updates from clients under Byzantine faults. At the same time, it also faces privacy adversaries, including external auditors who analyze the deployed model and participating clients who observe per-round updates. Byzantine fault. We follow the classic notion of Byzantine fault in distributed systems, where up to f clients can be compromised to send malicious messages. These clients, collectively denoted by B, can collude and adaptively send malicious messages based on previously observed information exchange, but cannot impersonate peers or observe or interfere with the communications of honest clients [50]. Let G ≜ [n] \ B denote the set of honest clients. Due to the existence of Byzantine clients, it is impossible to minimize the fault-free objective F [62]. Therefore, we follow the mainstream in the literature of Byzantine-resilient distributed learning [4, 7, 8, 41], and henceforth consider (1). 1 X FG (θ) ≜ Fi (θ) (1) |G| i∈G

User-level differential privacy. We consider central DP [16, 45], where the PS is assumed to be trustworthy. To protect honest clients from having their participation inferred by privacy adversaries, we adopt Byzantine user-level DP in Definition 1, with adjacency defined exclusively over the set of honest clients to account for Byzantine behavior. Definition 1 ((ϵ, δ)-Byzantine user-level DP). Let X be the space of possible client datasets, [n] be the set of client indices, which includes a set of honest clients G and a set of Byzantine clients B such that G ∩ B = ∅. • Byzantine strategy. A Byzantine strategy B is an arbitrary, possibly randomized and colluding rule whose round-t actions depend on the honest datasets DG only through what the server publishes in rounds s < t. • Output. For an algorithm A, let AB (DG ) denote its output, i.e., everything the server publishes over the course of its execution, when the honest clients hold the dataset collection DG = {Di }i∈G ∈ X |G| , and the Byzantine clients follow strategy B. 3

• Neighboring. Two honest dataset collections DG and DG′ are said to be neighboring, denoted by DG ∼ DG′ , if they differ in the dataset of exactly one honest client. We say that A satisfies (ϵ, δ)-Byzantine user-level DP if, for every Byzantine strategy B, every pair of neighboring collections DG ∼ DG′ , it holds for every measurable set Q,  P {AB (DG ) ∈ Q} ≤ eϵ P AB (DG′ ) ∈ Q + δ.

4

Lower Bound

In this section, we introduce an information-theoretic lower bound in Theorem 1 for any Byzantineresilient ERM that ensures (ϵ, δ) user-level DP under heterogeneous clients. The full proofs are deferred to Appendix E.5. Assumption 1. There exist B ≥ 0 and G ≥ 0 such that ∀θ ∈ Rd 1 X 2 2 ∥∇Fi (θ) − ∇FG (θ)∥2 ≤ B 2 ∥∇FG (θ)∥2 + G2 . |G|

(2)

i∈G

Assumption 1 captures the heterogeneity across honest clients [6, 41, 42], which is what makes both Byzantine robustness and user-level DP fundamentally hard. When G = 0, all honest clients share common stationary points and become almost statistically indistinguishable. Specifically, clients’ full-batch gradients become identical when B = G = 0, making the DP guarantees trivial. Even when B > 0 and G = 0, the same degeneracy may arise, e.g., if each Fi is strongly-convex or admits a unique stationary point. In any of these regimes, Byzantine clients cannot deviate without being identified as outliers and are readily excluded. Henceforth, we focus on the regime where G > 0. Theorem 1. For any given L, B ≥ 0 and G > 0, there exists a collection of n functions {Fi }i∈[n] , each defined over a dataset of m samples, that are all i) L-smooth, ii) µ-strongly convex with µ = Θ(L), and iii) satisfy Assumption 1. Let m, n, d ≥ 1 and 1 ≤ f < n/2. Suppose that 1−γ ϵ, δ ∈ (0, 1) and 1/2(n−f ) ≤ δ ≤ 1/(n − f )1+γ , where γ ∈ (0, 1). If any distributed algorithm A is (ϵ, δ)-Byzantine user-level DP, then its output θb satisfies f
dG2 log(1/δ)
f G2 + 1 + , n µ2 n µ2 ϵ2 (n − f )2
2
b 2 = Ω f G2 + 1 + f dG log(1/δ) , E∥∇FG (θ)∥ 2 2 2 n n ϵ (n − f ) E∥θb − θ ∗ ∥22 = Ω

where θb is the output of A, P the expectation is taken over the randomness in A and the data generation, 1 and θ ∗ = arg minθ |G| i∈G Fi (θ). The number of samples per client m does not appear in the bound because we focus on the ERM problem with arbitrary data. In the worst case, each client i ∈ [n] may hold m identical copies of a single point, with the point differing across clients. User-level DP reduces to item-level DP over n data points, and no improvement in m is possible. Note that the construction of Theorem 1 is based on m data samples. The absence of m is inherent to the worst-case ERM setting, rather than an artifact of our proof. When no Byzantine clients are present (f = 0), the bound reduces to Ω(dG2 log(1/δ)/(ϵ2 n2 )), matching the centralized item-level ERM lower bound in [15] up to the dependence on G, which is normalized to G = O(1) in their construction. The constraints on ϵ and δ are necessary only for the lower bound [60], which can be relaxed at the cost of a looser bound via techniques from [15]. The proof of Theorem 1 includes three subcases, each captured by a separate lemma. The theorem follows by taking a maximum. Lemma 1 recovers the DP-only cost in the absence of Byzantine clients. Lemma 1 (Non-Byzantine). Suppose that the conditions in Theorem 1 hold with f = 0, the output θb of a (ϵ, δ) user-level DP learning algorithm A has an error at least E∥θb − θ ∗ ∥22 = Ω

2
dG2 log(1/δ)
b 2 = Ω dG log(1/δ) . , E∥∇F ( θ)∥ 2 µ2 ϵ2 n2 ϵ2 n 2

4

(3)

Algorithm 1: ByzULDP e−1 = 0, R, σ 2 , ηt , βt , αt , and T ; Input: θ 0 , m0i = 0, ∀i ∈ G, R dp,t T 2 Output: θ . 3 for t = 0, . . . , T − 1 do /* On the PS /* On all clients */ 11 for i = 1, · · · , n do 4 for i = 1, · · · , n do et−1 + (1 − βt )c 5 Download θ t from the PS ; 12 Mit ← βt R mti ; t t t 6 gbi ← clip(∇ℓi (θ ; ξi ),C), where 13 end 14 Rt ← R(M1t , . . . , Mnt ) clip(v, C) = v · min 1, C/∥v∥2 ; t−1 t t et ← Rt + X t , where 7 mi ← αt mi + (1 − αt )b gi ; 15 R dp  t t 2 mi , if i ∈ G; Xdp ∼ N (0, σdp,t I) t ci = ; 8 m t+1 t t e ∗, otherwise. 16 θ ← θ − ηt R ; cti to the PS. 9 Send m 10 end 17 end 1

*/

To show Lemma 1, we reduce the distributed learning problem to a centralized DP mean estimation of one-way marginals. The key technique is to adapt [45, Proposition 2] to our setting: user-level DP mean estimation is equivalent to the item-level mean estimation problem, where each item is the mean of a client’s local dataset, thereby reducing a multi-point estimation problem to a single-point one. This reduction clarifies the earlier intuition: the m data points held by each client contain no more private information than their mean, which explains why m does not appear in the bound. Lemma 2 characterizes the sole cost of Byzantine resilience in the absence of DP constraints. Its proof follows from the standard roadmap in the Byzantine-resilient learning literature [4, 7, 42]. Lemma 2 (Non-private). Suppose that the conditions in Theorem 1 hold with 1 ≤ f < n/2, the output θb of a (ϵ, δ) user-level DP learning algorithm A has an error at least E∥θb − θ ∗ ∥22 = Ω

f G2
b 2 = Ω f G2 . , E∥∇FG (θ)∥ 2 2 n−f µ n−f

(4)

Lemma 3 (Coupled). Suppose that the conditions in Theorem 1 hold with 1 ≤ f < n/2, the output θb of a (ϵ, δ) user-level DP learning algorithm A has an error at least E∥θb − θ ∗ ∥22 = Ω

2
f dG2 log(1/δ)
b 2 = Ω f dG log(1/δ) . , E∥∇FG (θ)∥ 2 2 2 2 2 2 n µ ϵ (n − f ) n ϵ (n − f )

(5)

Compared with (3), (5) inflates the DP error by a factor of Byzantine fraction f /n. The key step is to construct two adversarial configurations that are indistinguishable to any user-level DP algorithm, yet have well-separated optima. We partition the n clients into three groups whose local dataset means point in opposing directions: +G0 1, −G0 1, and 0, where G0 = Θ(G). We construct hard instances by combining these groups in different ways. By comparing each instance to a common reference, we show that no distributed algorithm can distinguish them, which reduces the distributed learning problem to a centralized, item-level DP mean-estimation task on n − f items.

5

Algorithm: ByzULDP

In this section, we propose Byzantine-resilient User-level Differentially Private Learning (ByzULDP), formally presented in Algorithm 1. ByzULDP departs from FedAvg by tackling the dual challenges of Byzantine attacks and user-level DP together. At a high level, ByzULDP achieves Byzantine resilience through a nonlinear robust aggregator combined with a client-side momentum scheme that mitigates stochastic gradient noise. ByzULDP introduces a server-side momentum to regulate the global update. While the fault-free recipe for user-level central DP relies on injecting central noise directly into a linear simple mean [16, 45], this approach is insufficient for convergence with nonlinear robust aggregators; see Remark 2 for details. 5

A key innovation in ByzULDP is the use of server-side momentum to recalibrate each client’s message, thereby controlling its global impact and reducing privacy sensitivity without sacrificing robustness. This recalibration is enabled exclusively by user-level DP; the gradient is the only viable data representation for item-level DP, lacking such architectural flexibility. Client-side. Each honest client i ∈ G downloads θ t from the PS, computes a clipped stochastic gradient gbit = clip(∇ℓi (θ t ; ξit ), C), where clip(v, C) = v · min{1, C/∥v∥2 } (line 6), and updates its local momentum mti = αt mt−1 + (1 − αt )b git (line 7). Clipping bounds each client’s influence on i the global model, which is important for our privacy analysis. Byzantine clients may report arbitrary values ∗ in place of mti . One-step gradient descent is commonly adopted in Byzantine-resilient FL [4, 5, 6, 7, 41, 42]; extending to multi-step local updates is left to future work. et−1 + (1 − βt )c Server-side. The PS computes Mit = βt R mti for each client i ∈ [n] (lines 11t−1 e 13), where R is the previous-round privatized aggregate and βt ∈ (0, 1). Similar server-side momentum has been adopted in [20, 71] yet to mitigate the client-drift issue in non-Byzantine and nonctj ), private settings. Such a momentum mechanism enables contraction Mit −Mjt = (1−βt )(c mti − m which shrinks the distance between honest clients by a factor 1−βt and reduces the privacy sensitivity et−1 is already privatized, the DP of the global aggregation, formally shown in Proposition 1. Since R post-processing property ensures that all subsequent computations remain private. In line 14, the PS aggregates the server-side momentum via a nonlinear robust aggregator R(·), defined in Definition 2. Definition 2 ((f, κ)-robust [4]). Let f < n/2 and κ ≥ 0. An aggregation rule R is said to be (f, κ)-robust if for any vectors x1 , . . . , xn ∈ Rd , and any set S ⊆ [n] of size n − f , it holds that κ X 2 2 ∥R(x1 , . . . , xn ) − xS ∥2 ≤ ∥xi − xS ∥2 , |S| i∈S

P 1

where xS = |S|

i∈S xi .

We refer to κ as a robust coefficient. Robust aggregators aim to filter out the adversarial updates and have been widely adopted in Byzantine-resilient algorithm design [4, 17, 19, 41, 42, 61, 70, 73]. Our analysis can be easily extended to any such R. However, to obtain the optimal upper bound, we adopt coordinate-wise trimmed mean (CWTM) [73], defined in Definition 3, as the robust aggregator. Definition 3 (CWTM). Let x ∈ Rd , we define [x]r the r-th coordinate of x. Given the input vectors x1 , . . . , xn ∈ Rd , we let πr denote a permutation on [n] that sorts the r-th coordinate of the input vector in non-decreasing order, i.e., [xπr (1) ]r ≤ [xπr (2) ]r ≤ . . . ≤ [xπr (n) ]r . Then, the coordinatewise trimmed mean CWTM(x1 , . . . , xn ) ∈ Rd is defined coordinate-wise by n−f X   1 [CWTM(x1 , . . . , xn )]r ≜ xπr (i) r . n − 2f i=f +1

et = Rt + X t with X t ∼ N (0, σdp,t I) and updates Finally, the PS forms the privatized aggregate R dp dp et . The value of σdp,t will be specified in Section 6.2. θ t+1 = θ t − ηt R

6

Convergence Analysis of ByzULDP (Upper Bound)

In this section, we analyze the convergence of ByzULDP. Missing proofs, intermediate results, and additional privacy analysis are deferred to the Appendix. 6.1

Additional Assumptions

Let F t define the natural filtration generated by the randomness up to round t. Assumption 2. Each local objective function ∇Fi (x) is L-Lipschitz, i.e., ∥∇Fi (θ1 ) − ∇Fi (θ2 )∥2 ≤ L ∥θ1 − θ2 ∥2 , ∀θ1 , θ2 ∈ Rd , and ∀ i ∈ [n]. 6

Assumption 3. Stochastic gradients ∇ℓi (θ t ; ξit ) are unbiased with bounded variance, i.e., i h   2 E ∇ℓi (θ t ; ξit ) | F t = ∇Fi (θ t ) and E ∇ℓi (θ t ; ξit ) − ∇Fi (θ t ) 2 | F t ≤ σ 2 , ∀ i ∈ [n]. Assumption 4. Stochastic gradients ∇ℓi (θ, ξ) are uniformly bounded in l2 norm ∥∇ℓi (θ, ξ)∥2 ≤ C, ∀θ ∈ Rd and ξ. Assumptions 2 and 3 are common in FL analysis [42, 46, 64]. Assumption 4 is widely adopted by DP algorithm analysis [7, 15, 16, 29, 45, 65]. We conjecture that Assumption 4 is imposed primarily for technical convenience and leave its relaxation to future work. 6.2

Privacy Results of ByzULDP

We start from the privacy analysis of ByzULDP. Since clients influence the global model through the robust aggregator, the key step is characterizing its user-level sensitivity. Definition 4 adapts the standard ℓ2 sensitivity [26] to the Byzantine setting. As Byzantine clients may behave arbitrarily, we measure sensitivity with respect to replacing a single honest client’s update. Definition 4 (Byzantine-robust user-level sensitivity). Let [n] = G ∪ B be a union of honest clients G and Byzantine clients B such that |B| ≤ f . The Byzantine-robust user-level sensitivity of a robust aggregator R : Rn×d → Rd , operating on n inputs of which at most f < n/2 are Byzantine, is ∆(R) ≜

max

sup

sup

B⊂[n],|B|≤f XB XG ≃XG ′

∥R(XG ∪ XB ) − R(XG ′ ∪ XB )∥2 ,

where XG , XB are input collections from the respective sets, and XG ≃ XG ′ denotes honest client collections differing by exactly one input. Our analysis extends to any robust aggregator in Definition 2, but CWTM enables us to attain the optimal convergence rate in Section 6.3. Lemma 4 (Per-dimension CWTM). Let n ≥ (2 + ν)f , where ν > 0. Fix a coordinate r, for any a1 ≤ a2 ≤ · · · ≤ an−1 in Rd , let TMr (h) define the coordinate-r output of CWTM when inserting value h. For any h, h′ ∈ R, it holds that r |h − h′ | 4(2 + ν)2 f ′ |TMr (h) − TMr (h )| ≤ 1+ . n ν2 n The proof of Lemma 4 characterizes how inserting an honest client update affects the CWTM output by distinguishing whether the update lies inside or outside the trimmed set. Since it holds coordinate-wise, and honest updates are bounded by C in ℓ2 norm, aggregating across coordinates yields a sensitivity without explicit dependence on the dimension d. This intuition is formalized in Proposition 1. et−1 + Proposition 1 (CWTM sensitivity). Let n ∈ N. If the input to the robust aggregator is xi = βt R (1 − βt )mti , and n ≥ (2 + ν)f , where ∥mti ∥2 ≤ C for i ∈ G and ν > 0, the Byzantine-robust user-level sensitivity of CWTM in round t is r 4(2 + ν)2 f 2(1 − βt )C 1+ . ∆t (CWTM) = n ν2 n Theorem 2 (User-level DP noise). Let δ ∈ (0, 1) and ϵ > 0 such that ϵ ≤ 8 log(1/δ). Algo2 rithm 1 is a (ϵ, δ) user-level DP algorithm with CWTM as the robust aggregator when σdp,t =   2 2 2 32(1−βt ) C T log(1/δ) 4(2+ν) f 1 + ν2 n . n2 ϵ 2 Theorem 2 combines the per-round dimension-independent sensitivity in Proposition 1 with the 2 cross-round Rényi DP composition [52], yielding the σdp,t ∝ T scaling without explicit dependence 2 on d. The noise variance additionally inherits a (1 − βt ) factor from server-momentum aggregation, since ∥Mit − Mjt ∥2 = (1 − βt )2 ∥mti − mtj ∥2 for i, j ∈ G. Such a dependence effectively reduces privacy sensitivity when (1 − βt ) is small and is crucial for convergence; see Remark 2 for details. 7

6.3

Convergence Results of ByzULDP

In this subsection, we provide convergence results for ByzULDP. The non-convex case uses constant αt P ≡ α and ηt ≡ η, while the strongly-convex case keeps time-varying schedules. Let mt ≜ 1 t ∗ i∈G mi and FG = minθ FG (θ). In Lemma 5, we show that client-side momentum mitigates |G| the stochastic gradient noise. Take non-convex objectives as an example. Lemma 5 (Non-convex local momentum drift). Under Assumptions 1, 2, and 3. When FG is non-convex, it holds for any αt = α ∈ (0, 1) that 1 X 2 E mti − mt 2 ≤ |G| i∈G

  t X
3 1 − α2 σ 2 + 3G2 + 3B 2 (1 − α) αt−r E∥∇FG (θ r )∥22 . 3+ |G| r=0

(6)

(6) shows that the stochastic variance term scales as (1 − α2 ). Setting 1 − α = Θ(ηL) makes this factor small, effectively dampening its effect. The proof of Lemma 5 follows the standard Polyak momentum analysis by unrolling across all rounds [4, 7, 42]. An analogous strongly-convex result uses single-round unrolling; see Appendix G.2 for details. We establish our convergence bounds in Theorems 3 and 4 by constructing separate Lyapunov functions for strongly-convex and non-convex objectives to account for their different learning rate and momentum schedules. Theorem 3 (Strongly-convex, Informal). Suppose that Assumptions 1, 2, 3, and 4 hold. When 10 ηt = µ(t+a such that a ≥ 49000, 1 − αt = Θ(ηt L), 1 − βt = Θ(ηt L), B 2 ≤ 1/(600κ), and L ) µ

n ≥ (2 + ν)f , where ν > 0, it holds for Algorithm 1 with CWTM as the robust aggregator that       2 L log(1/δ)C 2 d κG2 f 1 σ T ∗ 2 E θ −θ 2 ≲ 2 + 1+ + L(1 + κ) 1 + µ µ µ2 ϵ2 n2 n |G| µ3 T      L2 (E FG (θ 0 ) − FG∗ ) Lσ 2 Lκ 1 2 2 + + + σ + G . 1 + µ3 T 2 µ3 T 2 |G| µ3 T 2 |G|

(7)

Theorem 4 (Non-convex, Informal). Suppose that Assumptions 1, 2, 3, and 4 hold. Let 1 − α = Θ(ηL), 1 − β = Θ(ηL), such that η < 1/(5100L) and B 2 ≤ 1/(23625κ). When n ≥ (2 + ν)f , where ν > 0 is an absolute constant, it holds for Algorithm 1 with CWTM as the robust aggregator that   T −1 2 dσdp E FG (θ 0 ) − FG∗ 1 X ηLσ 2 1 2 t 2 E ∇FG (θ ) 2 ≲ + + ηLκ(1 + )σ + κG2 + T t=0 ηT |G| |G| ηL   f  1 σdp =Θ(1−β) E F (θ 0 ) − F ∗ 1  (1 − β)2 T dC 2 log( 1δ )(1 + n ) ≲ + ηLσ 2 + κ(1 + ) + κG2 + ηT |G| |G| ηL n 2 ϵ2 (8)   f (1−β)=Θ(ηL) E F (θ 0 ) − F ∗ ηLT dC 2 log(1/δ)(1 + n ) 1 1 G G ≲ + ηLσ 2 ( + κ(1 + )) + κG2 + . ηT |G| |G| n2 ϵ2 (9) Corollary 1 (Informal). Suppose that Assumptions 1, 2, 3, and 4 and the conditions in Theorem 4 hold. The choice of learning rate is formally defined in Appendix G.3.3. When n ≥ (2 + ν)f , where ν > 0 is an absolute constant, it holds for Algorithm 1 with CWTM as the robust aggregator that s   T −1 1 X log(1/δ)C 2 d f 2 t 2 ∗ 0 E ∇FG (θ ) 2 ≲ κG + L(E [FG (θ )] − FG ) 1+ T t=0 ϵ2 n 2 n s      L(E FG (θ 0 ) − FG∗ ) σ 1 1 +√ L(E [FG (θ 0 )] − FG∗ ) +κ 1+ + . |G| |G| T T Remark 1 (Optimal bound for strongly-convex objectives). We remark on Theorem 3, which establishes the convergence guarantees for a µ strongly-convex objective FG . • Order-optimal bound. Theorem 3 establishes the full convergence bound for ByzULDP under a µ-strongly convex objective. The colored terms in (7) are the non-vanishing errors. 8

– DP terms. The hard instances in Lemma  1 and in Lemma 3satisfy G = Θ(C) when f = Θ(n), 2

log(1/δ) yielding a matching lower bound Ω (1+fµ/n)dC up to constants and a factor L/µ; 2 ϵ2 (n−f )2 see Appendix G.5 for details. – Byzantine-only term. CWTM aggregator achieves a robustness coefficient of κ = Θ(f /n) [4], yielding a matching bound O(κG2 /µ2 ) = O(f /n · G2 /µ2 ); see Corollary 4 for details. Together, our upper bound is order-optimal with respect to the lower bound in Section 4. In the absence of the non-vanishing error terms, our O(1/T ) rate for strongly-convex objectives also matches the optimal rate for stochastic first-order methods [57]. • Privacy-utility tradeoff. For the non-vanishing errors, we have both DP error and Byzantine residual terms, where the former dominates when d ≳ n. Fortunately, the large scale of FL systems can effectively mitigate the impact of DP noise on the final model utility [40]. On the other hand, the Byzantine residual error becomes negligible when the number of Byzantine clients f is small or when the clients’ data is not highly heterogeneous. • Comparisons with [8]. Recall that [8] guarantees user-level DP without a trusted server in the presence of Byzantine faults. We establish an improved convergence bound in the central DP setting. Ignoring the Byzantine-only error and µ, we have the following comparisons:

dC 2 log(1/δ) f dC 2 log(1/δ) + ); n 2 ϵ2 n 3 ϵ2 dC 2 log(1/δ) f dC 2 log(1/δ) f C 2 log(1/δ) + + ). [8] : O( n 2 ϵ2 n 2 ϵ2 nϵ2

Ours : O(

The two bounds coincide in the Byzantine-free case f = 0. Yet, our bound strictly improves whenever f ≥ 1. The dominant Byzantine-DP term improves from f d/n2 to f d/n3 when d ≳ n, and from f /n to f /n2 when d ≲ n. Moreover, their robust aggregator costs O(f (nd2 + d3 )) to compute, while CWTM runs efficiently in O(nd log(n)). Remark 2 (Results for non-convex objectives). We remark on Theorem 4 and Corollary 1, which establish the convergence guarantees for a non-convex objective FG . • Necessity of server-side momentum. Theorem 2 establishes that σdp = Θ(1 − β). Substituting into Theorem 4 and setting (1 − β) = Θ(ηL) reduces the DP error to a O(ηLT ) scaling. Without server momentum (β = 0), this term scales as O(T /(ηL)) and diverges, e.g., as O(T 3/2 ) when √ η = Θ(1/ T ). Thus, server momentum is a structural requirement for a√non-trivial DP guarantee. • Non-convex bound. Without the non-vanishing error terms, our O(1/ T ) convergence rate for non-convex objectives matches the optimal bound for stochastic first-order methods [9]. Similar to Remark 1, CWTM achieves an order-optimal Byzantine residual error of O(κG2 ) = O(f /n · G2 ). However, a gap remains regarding the DP residual error. Ignoring the Byzantine residual, (9) 1 scales as O( ηT + ηL(1 + T )). Applying the AM-GM inequality yields an optimal learning rate of 1 η = Θ( √ ), subject to the constraint η < 1/(5100L). However, this optimal η inevitably LT (1+T )

couples the DP noise term with the initialization error under a square root in Corollary 1, preventing a strict match with our lower bound in Section 4. The appearance of the DP noise term inside a square root is widely observed in the DP non-convex learning literature; see, e.g., [7, 8, 10, 14, 45].

7

Numerical Experiments

Overview. In this section, we evaluate the performance of ByzULDP with CWTM against other stateof-the-art (SOTA) robust aggregators. The hyperparameter setups and additional experiment details are deferred to Appendix H. We consider an FL system of 1000 clients with 250 clients corrupted by a variety of Byzantine adversaries. The image classification tasks use CNNs and are based on the MNIST [44] and the Fashion-MNIST [68] datasets. While these tasks are relatively simple in non-adversarial settings, they become significantly more challenging in the presence of Byzantine clients [36, 42] and DP [7, 8]. All of them include 10 classes of images of different categories. We partition the dataset to clients such that each client holds two classes of images. Attacks and Benchmark algorithms. We evaluate four SOTA attacks, including a little is enough [13], bit-flip attack [3], mimic attack [41], and inner-product manipulation attack [69]. The detailed attack setups are deferred to Appendix H. Our ByzULDP is a user-level DP framework, compatible 9

30 20 10 Privacy Budget ( ) More Private

1

Trimmed Mean (Ours)

Bit Flip

CAFCOR (LDP)

30 20 10 Privacy Budget ( ) More Private

1.00 0.75 0.50 0.25

1

CClip

Coordinate Median

Geometric Median

Mimic

Test Accuracy

1.00 0.75 0.50 0.25

Test Accuracy

A Little is Enough

Test Accuracy

Test Accuracy

Attack-free baseline (CDP)

1.00 0.75 0.50 0.25

30 20 10 Privacy Budget ( ) More Private

1.00 0.75 0.50 0.25

1

Inner Product Manipulation

30 20 10 Privacy Budget ( ) More Private

1

30 20 10 Privacy Budget ( ) More Private

1

Bit Flip

30 20 10 Privacy Budget ( ) More Private

1

0.8 0.6 0.4 0.2

Mimic Test Accuracy

0.8 0.6 0.4 0.2

Test Accuracy

0.8 0.6 0.4 0.2

Test Accuracy

Test Accuracy

(a) Test accuracy results on the MNIST dataset. A Little is Enough

30 20 10 Privacy Budget ( ) More Private

1

0.8 0.6 0.4 0.2

Inner Product Manipulation

30 20 10 Privacy Budget ( ) More Private

1

(b) Test accuracy results on the Fashion-MNIST dataset.

Figure 1: Test accuracy results and comparisons on real-world datasets. The results are averaged over the last 50 rounds across 4 different random seeds. All the experiments run for a total of 800 rounds. The radius of the shaded circle denotes the standard deviation at a given privacy budget ϵ.

with any robust aggregator satisfying Definition 2, and it attains the optimal rate when instantiated with CWTM. Other than CWTM, the SOTA robust aggregators include geometric median [19], coordinatewise median [73], and CClip [42]. We additionally compare against two baselines: a simple mean as an aggregator in the attack-free setting (f = 0), and CAFCOR [8]. CAFCOR is a local DP algorithm that guarantees user-level DP without a trusted server. Discussions. Fig. 1 displays the final performance under different privacy budgets. Observations are mostly consistent between the two datasets. Compared with the attack-free baseline, a performance gap emerges due to the presence of Byzantine clients. When user-level DP protection is not imposed, CWTM is among the top-performing robust aggregators. The other strong performers are CClip and CAFCOR, where the former relies on a clipping threshold that requires careful tuning, and the latter incurs high computational overhead (see Remark 1 for details). As a byproduct, we find that server-side momentum also improves the empirical performance of robust aggregators. Intuitively, et−1 pulls all clients’ updates toward a common direction, thereby strengthening the shared anchor βt R their concentration and improving the robust aggregator’s effectiveness against Byzantine clients. We defer the details to Table 6 in Appendix H. Under user-level DP protections, CWTM consistently outperforms the other baselines in the presence of Byzantine attacks. We attribute this to its dimension-free sensitivity, which yields the optimal convergence rate. Stronger privacy requires higher DP noise, degrading performance. Each nonlinear robust aggregator induces a different Byzantine-robust user-level sensitivity (Definition 4) due to the differences in structure; see Table 4 for details. Since such sensitivity determines the variance of the DP noise injected at the server, it dictates the signal-to-noise ratio and directly shapes the privacyutility tradeoff. Among the robust aggregators within our ByzULDP framework, only CClip and CWTM achieve meaningful test accuracy, and they are also the only two whose sensitivity denominators grow with the number of clients. However, the sensitivity of CClip is proportional to a heuristically chosen clipping threshold τ , typically set as τ = 10/(1 − α) [41, 42], which can be significantly larger than the corresponding C in CWTM. CAFCOR adopts an interesting correlated-noise mechanism to inject DP noise at clients and lies outside our ByzULDP framework. Nevertheless, it still falls behind, which we attribute to its suboptimal convergence rate; see Remark 1 for details. We also show that server-side momentum is essential to guarantee performance. The results are deferred to Fig. 3 in Appendix H.

8

Conclusion

In this paper, we study Byzantine-resilient federated learning with user-level DP. We have established an information-theoretic lower bound for any Byzantine-resilient empirical risk minimization problem under user-level DP and heterogeneous clients. We have proposed ByzULDP, a central DP algorithm featuring two-level momentum across client and server. We have shown that ByzULDP achieves the order-optimal convergence bound for strongly-convex objectives. Numerical experiments have corroborated our analysis. 10

Acknowledgments and Disclosure of Funding We gratefully acknowledge the support from the National Science Foundation under grants 2106891, 2107062, and the National Science Foundation CAREER award under grant 2340482. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the National Science Foundation, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.

References [1] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Robust testing and estimation under manipulation attacks. In International Conference on Machine Learning, pages 43–53. PMLR, 2021. [2] Sushant Agarwal, Gautam Kamath, Mahbod Majid, Argyris Mouzakis, Rose Silver, and Jonathan Ullman. Private mean estimation with person-level differential privacy. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2819–2880. SIAM, 2025. [3] Zeyuan Allen-Zhu, Faeze Ebrahimianghazani, Jerry Li, and Dan Alistarh. Byzantine-resilient non-convex stochastic gradient descent. In International Conference on Learning Representations, 2021. [4] Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In International Conference on Artificial Intelligence and Statistics, pages 1232–1300. PMLR, 2023. [5] Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Ahmed Jellouli, Geovani Rizk, and John Stephan. Adaptive gradient clipping for robust federated learning. In The Thirteenth International Conference on Learning Representations, 2025. [6] Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and Geovani Rizk. Robust distributed learning: Tight error bounds and breakdown point under data heterogeneity. Advances in Neural Information Processing Systems, 36:45744–45776, 2023. [7] Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. On the privacy-robustness-utility trilemma in distributed learning. In International Conference on Machine Learning, pages 569–626. PMLR, 2023. [8] Youssef Allouah, Rachid Guerraoui, and John Stephan. Towards trustworthy federated learning with untrusted participants. In Forty-second International Conference on Machine Learning, 2025. [9] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1):165–214, 2023. [10] Raman Arora, Raef Bassily, Tomás González, Cristóbal A Guzmán, Michael Menart, and Enayat Ullah. Faster rates of convergence to stationary points in differentially private optimization. In International Conference on Machine Learning, pages 1060–1092. PMLR, 2023. [11] Ghazi Badih, Kumar Ravi, and Manurangsi Pasin. User-level private learning via correlated sampling. Advances in Neural Information Processing Systems, 1, 2021. [12] Li Bai, Haibo Hu, Qingqing Ye, Haoyang Li, Leixia Wang, and Jianliang Xu. Membership inference attacks and defenses in federated learning: A survey. ACM Computing Surveys, 57(4):1–35, 2024. [13] Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. Advances in Neural Information Processing Systems, 32, 2019. 11

[14] Raef Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private stochastic optimization: New results in convex and non-convex settings. Advances in Neural Information Processing Systems, 34:9317–9329, 2021. [15] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464–473. IEEE, 2014. [16] Raef Bassily and Ziteng Sun. User-level private stochastic convex optimization with optimal rates. In International Conference on Machine Learning, pages 1838–1851. PMLR, 2023. [17] Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Advances in neural information processing systems, 30, 2017. [18] Jin-Hua Chen, Min-Rong Chen, Guo-Qiang Zeng, and Jia-Si Weng. Bdfl: a byzantine-faulttolerance decentralized federated learning method for autonomous vehicle. IEEE Transactions on Vehicular Technology, 70(9):8639–8652, 2021. [19] Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1–25, 2017. [20] Ziheng Cheng, Xinmeng Huang, Pengfei Wu, and Kun Yuan. Momentum benefits non-iid federated learning simply and provably. In The Twelfth International Conference on Learning Representations, 2024. [21] Albert Cheu, Adam Smith, and Jonathan Ullman. Manipulation attacks in local differential privacy. In 2021 IEEE Symposium on Security and Privacy (SP), pages 883–900. IEEE, 2021. [22] Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In Annual international conference on the theory and applications of cryptographic techniques, pages 375–403. Springer, 2019. [23] Antoine Choffrut, Rachid Guerraoui, Rafael Pinot, Renaud Sirdey, John Stephan, and Martin Zuber. Towards practical homomorphic aggregation in byzantine-resilient distributed learning. In Proceedings of the 25th International Middleware Conference, pages 431–444, 2024. [24] Henry Corrigan-Gibbs and Dan Boneh. Prio: Private, robust, and scalable computation of aggregate statistics. In 14th USENIX symposium on networked systems design and implementation (NSDI 17), pages 259–282, 2017. [25] John Duchi, Martin J Wainwright, and Michael I Jordan. Local privacy and minimax bounds: Sharp rates for probability estimation. Advances in Neural Information Processing Systems, 26, 2013. [26] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and trends® in theoretical computer science, 9(3-4):211–487, 2014. [27] Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. Byzantine machine learning made easy by resilient averaging of momentums. In International Conference on Machine Learning, pages 6246–6283. PMLR, 2022. [28] Jiashi Feng, Huan Xu, and Shie Mannor. arXiv:1409.5937, 2014.

Distributed robust learning.

arXiv preprint

[29] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level differentially private learning via correlated sampling. Advances in Neural Information Processing Systems, 34:20172–20184, 2021. [30] Bimal Ghimire and Danda B Rawat. Recent advances on federated learning for cybersecurity and cybersecurity for federated learning for internet of things. IEEE Internet of Things Journal, 9(11):8229–8249, 2022. 12

[31] Avishek Ghosh, Raj Kumar Maity, Swanand Kadhe, Arya Mazumdar, and Kannan Ramachandran. Communication efficient and byzantine tolerant distributed learning. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2545–2550. IEEE, 2020. [32] Antonious M Girgis, Deepesh Data, and Suhas Diggavi. Distributed user-level private mean estimation. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 2196–2201. IEEE, 2022. [33] Xiaolan Gu, Ming Li, and Li Xiong. {DP-BREM}:{Differentially-Private} and {ByzantineRobust} federated learning with client momentum. In 34th USENIX Security Symposium (USENIX Security 25), pages 3065–3082, 2025. [34] Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, Sébastien Rouault, and John Stephan. Differential privacy and byzantine resilience in sgd: Do they add up? In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pages 391–401, 2021. [35] Rachid Guerraoui, Sébastien Rouault, et al. The hidden vulnerability of distributed learning in byzantium. In International conference on machine learning, pages 3521–3530. PMLR, 2018. [36] Rachid Guerraoui, Sébastien Rouault, et al. Distributed momentum for byzantine-resilient stochastic gradient descent. In International Conference on Learning Representations, 2021. [37] Rui Hu, Yuanxiong Guo, Hongning Li, Qingqi Pei, and Yanmin Gong. Personalized federated learning with differential privacy. IEEE Internet of Things Journal, 7(10):9530–9539, 2020. [38] Yangsibo Huang, Samyak Gupta, Zhao Song, Kai Li, and Sanjeev Arora. Evaluating gradient inversion attacks and defenses in federated learning. Advances in neural information processing systems, 34:7232–7241, 2021. [39] Bargav Jayaraman, Lingxiao Wang, David Evans, and Quanquan Gu. Distributed learning without distress: Privacy-preserving empirical risk minimization. Advances in neural information processing systems, 31, 2018. [40] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends® in Machine Learning, 14(1–2):1–210, 2021. [41] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on heterogeneous datasets via bucketing. In International Conference on Learning Representations, 2021. [42] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In International conference on machine learning, pages 5311–5319. PMLR, 2021. [43] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793–826, 2011. [44] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist, 2, 2010. [45] Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. Advances in Neural Information Processing Systems, 34:12466–12479, 2021. [46] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated Optimization in Heterogeneous Networks, April 2020. arXiv:1812.06127 [cs, stat]. [47] Bill Yuchen Lin, Chaoyang He, Zihang Ze, Hulin Wang, Yufen Hua, Christophe Dupuy, Rahul Gupta, Mahdi Soltanolkotabi, Xiang Ren, and Salman Avestimehr. Fednlp: Benchmarking federated learning methods for natural language processing tasks. In Findings of the Association for Computational Linguistics: NAACL 2022, pages 157–175, 2022. 13

[48] Daogao Liu and Hilal Asi. User-level differentially private stochastic convex optimization: Efficient algorithms with optimal rates. In International Conference on Artificial Intelligence and Statistics, pages 4240–4248. PMLR, 2024. [49] Yi Liu, Xiaohan Bi, Lei Li, Sishuo Chen, Wenkai Yang, and Xu Sun. Communication efficient federated learning for multilingual neural machine translation with adapter. In Findings of the association for computational linguistics: ACL 2023, pages 5315–5328, 2023. [50] Nancy A Lynch. Distributed algorithms. Elsevier, 1996. [51] Xu Ma, Xiaoqian Sun, Yuduo Wu, Zheli Liu, Xiaofeng Chen, and Changyu Dong. Differentially private byzantine-robust federated learning. IEEE Transactions on Parallel and Distributed Systems, 33(12):3690–3701, 2022. [52] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263–275. IEEE, 2017. [53] Viktor Moskvoretskii, Nazarii Tupitsa, Chris Biemann, Samuel Horváth, Eduard Gorbunov, and Irina Nikishina. Low-resource machine translation through the lens of personalized federated learning. In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 8806–8825, 2024. [54] Shyam Narayanan, Vahab Mirrokni, and Hossein Esfandiari. Tight and robust private mean estimation with few users. In International Conference on Machine Learning, pages 16383– 16412. PMLR, 2022. [55] Thien Duc Nguyen, Samuel Marchal, Markus Miettinen, Hossein Fereidooni, N Asokan, and Ahmad-Reza Sadeghi. Dïot: A federated self-learning anomaly detection system for iot. In 2019 IEEE 39th International conference on distributed computing systems (ICDCS), pages 756–767. IEEE, 2019. [56] Muzi Peng, Jiangwei Wang, Dongjin Song, Fei Miao, and Lili Su. Privacy-preserving and uncertainty-aware federated trajectory prediction for connected autonomous vehicles. In The 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2023). IEEE/RSJ, 2023. [57] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML’12, page 1571–1578, Madison, WI, USA, 2012. Omnipress. [58] Ethan Rathbun, Christopher Amato, and Alina Oprea. Sleepernets: Universal backdoor poisoning attacks against reinforcement learning agents. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 111994–112024. Curran Associates, Inc., 2024. [59] Junshuai Song, Zhao Li, Zehong Hu, Yucheng Wu, Zhenpeng Li, Jian Li, and Jun Gao. Poisonrec: an adaptive data poisoning framework for attacking black-box recommender systems. In 2020 IEEE 36th international conference on data engineering (ICDE), pages 157–168. IEEE, 2020. [60] Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. Journal of Privacy and Confidentiality, 7(2), 2016. [61] Lili Su and Nitin H Vaidya. Fault-tolerant multi-agent optimization: optimal iterative distributed algorithms. In Proceedings of the 2016 ACM symposium on principles of distributed computing, pages 425–434, 2016. [62] Lili Su and Nitin H Vaidya. Byzantine-resilient multiagent optimization. IEEE Transactions on Automatic Control, 66(5):2227–2233, 2020. [63] Shreyas Sundaram and Bahman Gharesifard. Consensus-based distributed optimization with malicious nodes. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 244–249. IEEE, 2015. 14

[64] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization, July 2020. arXiv:2007.07481. [65] Puyu Wang, Yunwen Lei, Yiming Ying, and Hai Zhang. Differentially private sgd with nonsmooth losses. Applied and Computational Harmonic Analysis, 56:306–336, 2022. [66] Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE transactions on information forensics and security, 15:3454–3469, 2020. [67] Ming Xiang and Lili Su. Distributed non-convex optimization with one-bit compressors on heterogeneous data: Efficient and resilient algorithms. arXiv preprint arXiv:2210.00665, 2022. [68] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017. [69] Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantinetolerant sgd by inner product manipulation. In Uncertainty in artificial intelligence, pages 261–270. PMLR, 2020. [70] Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion-based fault-tolerance. In International conference on machine learning, pages 6893–6901. PMLR, 2019. [71] Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedcm: Federated learning with client-level momentum. arXiv preprint arXiv:2106.10874, 2021. [72] Han Yang, Dongbing Gu, and Jianhua He. A robust and efficient federated learning algorithm against adaptive model poisoning attacks. IEEE Internet of Things Journal, 11(9):16289–16302, 2024. [73] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International conference on machine learning, pages 5650–5659. Pmlr, 2018. [74] Tengchan Zeng, Omid Semiari, Mingzhe Chen, Walid Saad, and Mehdi Bennis. Federated learning on the road autonomous controller design for connected and autonomous vehicles. IEEE Transactions on Wireless Communications, 21(12):10407–10423, 2022. [75] Tuo Zhang, Lei Gao, Chaoyang He, Mi Zhang, Bhaskar Krishnamachari, and A Salman Avestimehr. Federated learning for the internet of things: Applications, challenges, and opportunities. IEEE Internet of Things Magazine, 5(1):24–29, 2022. [76] Heng Zhu and Qing Ling. Bridging differential privacy and byzantine-robustness via model aggregation. In Lud De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 2427–2433. International Joint Conferences on Artificial Intelligence Organization, 7 2022. Main Track.

15

Appendices Here, we provide an overview of the Appendix. In particular, the proofs of the main results are presented and backed by supporting intermediate results. A Limitations

17

B Broader Impacts

17

C Nomenclatures

17

D Useful Inequalities

18

E Lower Bound E.1 Proof of Lemma 1 (Non-Byzantine) . . . . . . . . . . . . . . . . . . . . . . . . . E.2 Proof of Lemma 2 (Non-private) . . . . . . . . . . . . . . . . . . . . . . . . . . . E.3 Proof of Lemma 3 (Coupled) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.4 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.5 Supporting Lemmas of Appendix E . . . . . . . . . . . . . . . . . . . . . . . . .

20 20 21 23 27 27

F Privacy Analysis F.1 Proof of Lemma 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.2 Proof of Proposition 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.3 Supporting Rényi DP Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.4 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.5 Byzantine-robust User-level Sensitivity Analysis of Additional Robust Aggregators

29 29 30 31 32 32

G Convergence Analysis G.1 Shared Intermediate Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.1.1 Proof of Descent Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . G.1.2 Proof of Global Momentum Estimation Error . . . . . . . . . . . . . . . . G.1.3 Proof of Client-side Momentum Estimation Error . . . . . . . . . . . . . . G.2 Strongly-convex objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.2.1 Proof of Local Momentum Drift . . . . . . . . . . . . . . . . . . . . . . . G.2.2 Proof of Theorem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.3 Non-convex objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.3.1 Proof of Lemma 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.3.2 Proof of Theorem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.3.3 Proof of Corollary 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.4 Supporting Results for the Optimality of CWTM . . . . . . . . . . . . . . . . . . . . G.5 Conditions of matching optimality . . . . . . . . . . . . . . . . . . . . . . . . . . G.6 Optimality of CWTM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35 35 35 36 40 41 41 43 51 51 52 57 59 59 60

H Experiment Details H.1 Experimental setups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H.2 Byzantine Attack Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H.3 Additional results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63 63 63 64

16

A

Limitations

The limitations of our work are twofold: 1. We assume a trustworthy parameter server. While this is the standard setting in regulated domains and achieves the minimax-optimal convergence rate, it only applies to central DP. Recent work by Allouah et al. [8] makes important progress in user-level DP without a trusted server in the presence of Byzantine adversaries. It is interesting to explore the minimax-optimal convergence rate when the server cannot be trusted. 2. We assume that stochastic gradients are uniformly bounded for technical convenience. Although this assumption is widely adopted in the DP literature [7, 15, 16, 29, 45, 65], real-world data distributions may exhibit heavy tails. Relaxing this assumption but applying gradient clipping can introduce bias that complicates the convergence analysis. It is interesting to explore the trade-off between the clipping threshold, privacy, and utility.

B

Broader Impacts

Federated learning has reshaped distributed ML/AI in recent years and has driven commercial applications such as autonomous vehicles, the Internet of Things, and natural language processing. Our paper focuses on the fault-tolerance aspect of real-world federated learning systems in the presence of both malicious clients and privacy leakage. Our work has substantially advanced the theory and algorithms for federated learning by bringing together insights from statistics, optimization, distributed computing and engineering practices. In addition, our research is important for federated learning systems to expand their outreach to more adversarial deployment environments. We are unaware of any potential negative social impacts of our work.

C

Nomenclatures

In this section, we provide the notations and nomenclatures used throughout our proofs for a comprehensive presentation. It is worth noting that all notation has been properly introduced before its first use.

∥v∥2

Table 1: Notation table The l2 norm of a given vector v.

Ft

The sigma algebra generated by randomness up to round t.

Rd

A d-dimensional vector space, where d denotes the dimension.

[n]

A set {k | k ∈ N, k ∈ [1, n]}.

G

A set of honest clients.

B

A set of clients suffering from Byzantine attacks B ≜ [n] \ G.

1

An all one vector 1 ∈ Rd .

≲

f (n) ≲ g(n), if there exists a constant cO > 0 and an integer n0 ∈ N, f (n) ≤ cO g(n) for all n ≥ n0 .

≳

f (n) ≳ g(n), if there exists a constant cΩ > 0 and an integer n0 ∈ N, f (n) ≥ cΩ g(n) for all n ≥ n0 .

O

f (n) = O(g(n)), if there exists a constant cO > 0 and an integer n0 ∈ N, f (n) ≤ cO g(n) for all n ≥ n0 .

Θ

f (n) = Θ(g(n)), if there exists a constant cΘ > 0 and an integer n0 ∈ N, f (n) = cΘ g(n) for all n ≥ n0 .

Ω

f (n) = Ω(g(n)), if there exists a constant cΩ > 0 and an integer n0 ∈ N, f (n) ≥ cΩ g(n) for all n ≥ n0 .

17

θ

Table 2: Algorithmic nomenclature table The global model at the beginning of round t in Algorithm 1.

t

Fi (θ)

The local objective function at client i.

FG (θ)

The global objective function defined in (1): FG (θ) ≜

∇ℓi (θ)

The local stochastic gradient function at client i taken with respect to θ.

gbit

The clipped local stochastic gradient function at client itaken with respect to θ. gbit ← clip(∇ℓi (θ t ; ξit ), C), where clip(v, C) = v · min 1, C/ ∥v∥2 .

mti

The client-side momentum at client i in round t.

mt

An average over the client-side momentum for clients in G in round t.

cti m

The local update from client i to the PS in round t. It duplicates mti for honest clients in G but can be arbitrary for Byzantine clients.

Mit

The server-side momentum in round t for client i.

M

t

P

i∈G Fi (θ)/ |G|.

t

An average over the server-side momentum for clients in G in round t, i.e., M ≜ P t i∈G Mi / |G|.

∇Fi (θ) The local full-batch gradient function at client i taken with respect to θ. ∇FG (θ) The global full-batch gradient function taken with respect to θ. Rt

The robust aggregation at the PS in round t by a robust aggregator R.

t Xdp

The DP noise at the PS in round t.

et R

The noisy robust aggregation at the PS in round t is a sum of a robust aggregation R t and a DP noise Xdp .

Di

Client i’s local empirical data distribution.

ξi

An independent stochastic sample drawn from client i’s local distribution Di .

L

Table 3: Variable table Lipschitz constant in Assumption 2.

σ2

The upper bound of the stochastic gradient variance.

2 σdp,t

The variance of DP noise in round t.

(B, G)

D

Parameters that capture the averaged local-global gradient dissimilarity.

C

A uniform upper bound on the stochastic gradient norm.

n

The number of clients in the FL system.

m

The number of local data points at each client in the FL system.

Useful Inequalities

For completeness and for ease of exposition, we present some common inequalities that will be frequently used in our proofs. The followings hold for any ai ∈ Rd and any i ∈ [n]. 1. Jensen’s inequality. n

1X ai n i=1

2

n

≤ 2

1X 2 ∥ai ∥2 and n i=1 18

n X i=1

2

≤n

ai 2

n X i=1

2

∥ai ∥2 .

(10)

2. Young’s inequality (a.k.a. Peter-Paul inequality). 2

2

⟨a1 , a2 ⟩ ≤

ϵ ∥a2 ∥2 ∥a1 ∥2 + , for any ϵ > 0. 2ϵ 2

(11)

Equivalently, we have 2

2

2

∥a1 + a2 ∥2 = ∥a1 ∥2 + ∥a2 ∥2 + 2 ⟨a1 , a2 ⟩   1 2 2 ∥a1 ∥2 + (1 + ϵ) ∥a2 ∥2 , for any ϵ > 0. ≤ 1+ ϵ

(12)

3. Cauchy-Schwartz inequality. ⟨a1 , a2 ⟩ ≤ ∥a1 ∥2 ∥a2 ∥2 .

(13)

4. Smoothness corollary. Given Assumption 2, it holds that   Z 1 F (a1 ) − F (a2 ) = a1 − a2 , ∇F (a2 + τ (a1 − a2 ))dτ 0

Z 1 = ⟨∇F (a2 ), a1 − a2 ⟩ +

⟨a1 − a2 , ∇F (a2 + τ (a1 − a2 )) − ∇F (a2 )⟩ dτ 0

Z 1

(a)

≤ ⟨∇F (a2 ), a1 − a2 ⟩ + L 0

≤ ⟨∇F (a2 ), a1 − a2 ⟩ +

τ ∥a1 − a2 ∥2 ∥(a1 − a2 )∥2 dτ

L 2 ∥a1 − a2 ∥2 , 2

where (a) follows from Cauchy-Schwartz inequality and Assumption 2.

19

(14)

E

Lower Bound

E.1

Proof of Lemma 1 (Non-Byzantine) 1−γ

Lemma E.1. Suppose that ϵ, δ ∈ (0, 1) and 1/2n ≤ δ ≤ 1/n1+γ , where γ ∈ (0, 1). For any given L, B ≥ 0 and G > 0, there exists a collection of n functions {Fi }i∈[n] , each defined over a dataset of m samples, that are all i) L-smooth, ii) µ-strongly convex with µ = Θ(L), and iii) satisfy Assumption 1 with respect to F . If A is (ϵ, δ)-DP, then the output θb of a (ϵ, δ) user-level DP learning algorithm A has an error at least i  2  h i  dG2 log(1/δ)  h b 22 = Ω dG log(1/δ) . , E ∥∇F ( θ)∥ E ∥θb − θ ∗ ∥22 = Ω µ2 ϵ2 n2 ϵ2 n2

(15)

Proof of Lemma 1 In this proof, we show the lower bound when we do not have any Byzantine adversaries, i.e., f = 0. It is worth noting that our bound remains valid when we have f > 0. We focus on the case of G > 0 only. We first construct n local datasets, each consisting of m elements: Each client i holds a local dataset Di of m ordered elements  1  xi G0 xm G √ , . . . , i√ 0 , Di = L d L d where xji ∈ {±1}d for j = 1, · · · , m and i ∈ [n], and G0 = G 2 , such that n X

x1i = · · · =

n X

xji = · · · =

xm i .

i=1

i=1

i=1

n X

We define local functions based on these datasets as follows: for any given µ ≤ L, m µ 1 G0 X j √ Fi (θ) = θ− x 2 m L d j=1 i

2

. 2

The resulting global objective is n

F (θ) =

1X Fi (θ). n i=1

b 2 and ∥θ − θ ∗ ∥2 can be characterized as follows: The optimality gaps ∥∇F (θ)∥ 2 2 2

b ∇F (θ)

2

=µ 2

n m G0 1 X X j θ− √ xi L d mn i=1 j=1

2 2 , and ∥θ − θ ∗ ∥2 = 2

n m G0 1 X X j θ− √ xi L d mn i=1 j=1

2

. 2

Next, we verify that the constructed functions collectively satisfy the (B, G)-conditions. It can be readily seen that ∇Fi (θ) = µθ −

m n m µG0 1 X j µG0 1 X X j √ xi . xi , and ∇F (θ) = µθ − √ L d m j=1 L d mn i=1 j=1

It follows that n n m n m 1X µ2 G2 X 1 X j 1 XX j 2 ∥∇Fi (θ) − ∇F (θ)∥2 = 2 0 xi − x n i=1 L d i=1 m j=1 nm i=1 j=1 i

2

≤ 4G20 = G2 . 2

Thus, our construction satisfies the (B, G)-condition for arbitrary given B ≥ 0 and G > 0. Different from the item-level differential privacy guarantees in Definition 2.3 in [7], Definition 1 requires the indistinguishability of clients’ local datasets. At a high level, Definition 1 does not require each client to be differentially private with respect to its own datasets. 20

Recall that

Pn

Pn Pn j 1 m i=1 xi = · · · = i=1 xi = · · · = i=1 xi , which results in n m m n n 1X j 1 X1X j 1 XX j xi = x , ∀ j ∈ [m]. xi = mn i=1 j=1 m j=1 n i=1 n i=1 i

Thus, when µ = Θ(L), we have 

2

b ∇F (θ)

E

n



2

=µ 2

2

m

1 X X xji G0 √ θb − nm i=1 j=1 L d

2

 1 Pn

1 i=1 xi

n

= µ2

1 G0  .. 1m ⊗ θb − √  m L d 1 Pn.

m i=1 xi

n

 2  

   2  2 1 md log(1/δ) d log(1/δ) 2 G (b) 0 = Ω µ2 · = Ω G , m L2 ϵ2 n 2 ϵ2 n 2

(a)

where equality (a) follows by invoking Corollary 2, and equality (b) follows from µ = Θ(L) and G2 = 4G20 . Similarly, h E

E.2

2 ∥θ − θ ∗ ∥2

i

n

m

2

1 X X xji G0 √ = θb − nm i=1 j=1 L d   d log(1/δ) G2 =Ω . ϵ2 n 2 µ2

 =Ω

d log(1/δ) G20 ϵ2 n2 L2



2

Proof of Lemma 2 (Non-private)

Lemma E.2. For any given L, B ≥ 0 and G > 0, there exists a collection of n functions {Fi }i∈[n] , each defined over a dataset of m samples, that are all i) L-smooth, ii) µ-strongly convex with µ = Θ(L), and iii) satisfy Assumption 1 with respect to FG . For this collection, the output θb of any distributed algorithm A satisfies h i  E ∥θb − θ ∗ ∥22 = Ω

i  f  f G2  h b 22 = Ω G2 . , E ∥∇FG (θ)∥ 2 n−f µ n−f

(16)

Proof of Lemma 2 [42, 4] We construct local function families such that, regardless of the algorithm employed, the resulting observations are indistinguishable under different Byzantine client configurations. The construction is similar to Theorem III in [41] and Proposition 3.2 in [7], but with adaptations to different optimality gaps. Let τ = f /(n − f ). Consider the following three groups of local datasets:                 G ·1   G ·1   G · 1 G · 1 0 0 0 0 D+ = + √ , . . . , + √ , D− = − √ , . . . , − √ , and D0 = 0 · 1, . . . , 0 · 1 , {z }  L τd   L τd  | L τd L τd   | | {z } {z } n elements n elements

n elements

d

where 1 ∈ R and G0 > 0 is a constant that can be chosen according to the given G. For each of the n clients, its local dataset Di is constructed as:  D+ , if i ∈ [1, f ]; Di = D− , if i ∈ [f + 1, 2f ];  D0 , if i ∈ [2f + 1, n]. That is, each dataset is of m rows chosen from its corresponding d-dimensional data universe. Let µ ≤ L and µ = Θ(L). Define each client’s local objective as µ X 2 Fi (θ) = ∥θ − x∥2 . 2n x∈Di

21

It can be readily computed that each Fi is L smooth, µ-strongly convex, and  2 µ  , if i ∈ [1, f ],  2 θ − LG√0 ·1  τd 2  2 µ Fi (θ) = G√ 0 ·1 , if i ∈ [f + 1, 2f ],  2 θ + L τd  2   µ 2 2 ∥θ∥2 , otherwise. We consider the following two Byzantine client configurations induced by the adversary. • Configuration #1: G1 = {1, . . . , n}, i.e., B 1 = ∅ • Configuration #2: G2 = {1, . . . , f } ∪ {2f + 1, . . . , n}, i.e., B 2 = [f + 1, 2f ]. Clearly, |B 1 | = 0 ≤ f , and |B 2 | = |[f + 1, 2f ]| = f . For ease of exposition, let FG1 and FG2 denote the global objective functions of the two configurations, respectively, i.e., 1 X 1 X FG1 (θ) = Fi (θ), and FG2 (θ) = Fi (θ). |G1 | |G2 | i∈G1

Let θ

∗1

i∈G2

= arg minθ FG1 (θ), and θ ∗2 = arg minθ FG2 (θ).

Now, we verify the (B, G) condition of the constructed functions. • Configuration #1. It is easy to see that     f 2f n 1X G0 · 1 G0 · 1 1 X 1 X µ θ− √ µ θ+ √ µθ = µθ. + + ∇FG1 (θ) = n i=1 n n L τd L τd i=f +1 i=2f +1 It follows that n 1X n i=1

2

∇Fi (θ) − ∇FG1 (θ) 2 2

2

=

n − 2f f µG0 1 f µG0 1 2 µθ − √ − µθ + ∥µθ − µθ∥2 + µθ + √ − µθ n n n L τd L τd 2 2

≤

2f G20 2f G20 ≤ = 2G20 . n τ n−f τ

• Configuration #2. Similarly, we have   f µG0 1 f µG0 1 n − 2f 2 √ . ∇FG (θ) = µθ − √ µθ = µθ − + n−f n−f n − f L τd L τd It follows that 1 X 2 ∇Fi (θ) − ∇FG2 (θ) 2 n−f i∈G2   2   2 f µ f G0 1 G 1 n − 2f µ f G0 1 √ − √0 √ = + n − f L n − f τd n − f L n − f τd 2 τd 2 2 2 G f (n − 2f )(n − f ) f G0 ≤ 0 = = G20 . τ (n − f )3 n−f τ Therefore, for any given G > 0, we can choose G0 = √12 G. For any algorithm A(F1 , · · · , Fm ), it cannot distinguish Configuration #1 from Configuration #2, since the Byzantine clients in Configuration #2 can disguise themselves by mimicking the behaviors of the non-Byzantine clients f + 1, · · · , 2f in Configuration #1. Hence, A should generate the same output θb under these two configurations. We know that b ∇FG1 (θ)

2 2

2

= µθb

2

, and

b ∇FG2 (θ)

22

s

2 2

= µθb −

2

f µG0 1 √ n−f L d

. 2

In addition, θb − θ ∗1

2

2 2

= θb

2

s

2

, and θb − θ ∗2

= θb −

2

2

f G0 1 √ n−f L d

. 2

So, we have       E 2 2 max E θb − θ ∗1 , E θb − θ ∗2 ≥ 2

θb − θ ∗1

2



 +E

2

2



2

θb

E

2

=

+ θb −

2 q

θb − θ ∗2

f G√ 01 n−f L d

2

2



2



2

2

f G20 n − f 4L2 f G2 = . n − f 8L2

≥

In addition,       E 2 2 b b max E ∇FG1 (θ) , E ∇FG2 (θ) ≥ 2

b ∇FG1 (θ)

2 2



 +E

b ∇FG2 (θ)

2 



2

 E

θb − θ 1∗

≥ µ2

2 2

+E

2



2

θb − θ 2∗

2



2

2

f µ2 G2 . n − f L2 8

≥ We can get the desired results by invoking L = Θ(µ). E.3

Proof of Lemma 3 (Coupled) 1−γ

Lemma E.3. Let m, n, d ≥ 1 and 1 ≤ f < m/2. Suppose that ϵ, δ ∈ (0, 1) and 1/2(n−f ) ≤δ≤ 1/(n − f )1+γ , where γ ∈ (0, 1). For any given L, B ≥ 0 and G > 0, there exists a collection of n functions {Fi }i∈[n] , each defined over a dataset of m samples, that are all i) L-smooth, ii) µ-strongly convex with µ = Θ(L), and iii) satisfy Assumption 1 with respect to FG . The output θb of a (ϵ, δ) user-level DP learning algorithm A has an error at least h i  f dG2 log(1/δ)  h i   2 b 22 = Ω f dG log(1/δ) . E ∥θb − θ ∗ ∥22 = Ω , E ∥∇FG (θ)∥ 2 2 2 2 2 n µ ϵ (n − f ) n ϵ (n − f )

(17)

Proof of Lemma 3 We construct local function families such that, regardless of the algorithm adopted, the resulting observations are indistinguishable under different Byzantine client configurations. Consider the following three groups of local datasets:                G 1      G 1 G 1 G 1 0 0 0 0 D+ = + √ , . . . , + √ , D− = − √ , . . . , − √ , and D0 = 0 · 1, . . . , 0 · 1 , {z }  L τd   L τd  | L τd L τd   | | {z } {z } m elements m elements

m elements

where 1 ∈ Rd , τ = f /(n − f ), and G0 > 0 is a constant that can be chosen according to a given G. For each of the n clients, its local dataset Di is constructed as:  D+ , if i ∈ [1, f ]; Di = D− , if i ∈ [f + 1, 2f ];  D0 , if i ∈ [2f + 1, n]. 23

That is, each dataset is of m rows chosen from its corresponding d-dimensional data universe. Let µ ≤ L and µ = Θ(L). Define each client’s local objective as µ X 2 Fi (θ) = ∥θ − x∥2 . 2n x∈Di

It can be readily computed that each Fi is L-smooth, µ-strongly convex, and  2 µ G  √0 1 θ − , if i ∈ [1, f ];  2 L τd 2  2 Fi (θ) = µ θ + G√0 1 , if i ∈ [f + 1, 2f ];  2 L τd 2   µ 2 2 ∥θ∥2 , otherwise. We consider the following three Byzantine client configurations induced by the adversary. • Configuration #1: G1 = {1, . . . , f } ∪ {2f + 1, n}, i.e., B 1 = {f + 1, . . . , 2f }; • Configuration #2: G2 = {f + 1, . . . , 2f } ∪ {2f + 1, n}, i.e., B 2 = {1, . . . , f }; • Configuration #3: G3 = [n], i.e., B 3 = ∅. Clearly, |B 1 | = |[f + 1, 2f ]| = f , |B 2 | = |[1, f ]| = f , and |B 3 | = 0 ≤ f . For any algorithm A(F1 , · · · , Fn ), it cannot distinguish Configuration #1 from Configuration #3, since the Byzantine clients in Configuration #1 can disguise themselves by mimicking the behaviors of the non-Byzantine clients f +1, · · · , 2f in Configuration #3. Similarly, any algorithm A(F1 , · · · , Fn ) cannot distinguish Configuration #2 from Configuration #3, since the Byzantine clients in Configuration #2 can disguise themselves by mimicking the behaviors of the non-Byzantine clients 1, · · · , f in Configuration #3. Therefore, A should generate the same output θb under Configuration #1 and Configuration #2. For ease of exposition, let FG1 and FG2 denote the global objective functions of the configurations #1 and #2, respectively, i.e., 1 X 1 X Fi (θ) and FG2 (θ) = Fi (θ). FG1 (θ) = |G1 | |G2 | i∈G1

Let θ

∗1

i∈G2

= arg minθ FG1 (θ), and θ ∗2 = arg minθ FG2 (θ).

Now, we verify the (B, G) condition of the constructed functions. Recall that n − f > f ⇔ f < n n 2 ⇔ n − f > 2. • Configuration #1. It is easy to see that s   f n X X n − 2f f G 1 f µG0 1 0 √ . µ θ− √ µθ = µθ − ∇FG1 (θ) = + n − f i=1 n−f n−f L d L τd i=2f +1 It follows that s s 2 2 1 X (n − 2f )µ2 f µ2 f G0 1 f G0 1 G0 1 2 1 √ √ −√ ∇Fi (θ) − ∇FG (θ) 2 = + . n−f (n − f )L2 n−f d (n − f )L2 n−f d τ d i∈G | {z }2 | {z }2 (1.a)

(1.b)

Bounding (1.a). It holds that s s 2 2 d (n − 2f )µ2 f G0 1 (n − 2f )µ2 X f G0 µ2 G2 f (n − 2f )f √ √ = = 2 0 ≤ G20 . 2 2 (n − f )L n−f d (n − f )L i=1 n−f d L τ n − f (n − f )2 2

2

Bounding (1.b). s s 2 2 d X f G0 1 G0 1 f G0 f µ2 f µ2 G0 µ2 G2 f (n − 2f )2 √ −√ √ −√ ≤ G20 . = ≤ 2 0 2 2 2 (n − f )L n−f d (n − f )L n − f L τ m − f (n − f ) τd d τd i=1 2

2

Combining them together, it holds that 1 X 2 ∇Fi (θ) − ∇FG1 (θ) 2 ≤ 2G20 . n−f i∈G

24

• Configuration #2:   2f X f G0 1 n − 2f 2 √ ∇FG (θ) = µ θ− + n−f n−f L τd i=f +1

n X

s µθ = µθ +

i=2f +1

f µG0 1 √ . n−f L d

It follows that s s 2 2 2 2 (n − 2f )µ 1 X f G 1 f µ f G0 1 G0 1 2 0 2 √ √ +√ − − ∇Fi (θ) − ∇FG (θ) 2 = + . n−f (n − f )L2 n−f d (n − f )L2 n−f d τd 2 i∈G 2 | {z } | {z } (2.a)

(2.b)

Bounding (2.a). s s 2 2 d (n − 2f )µ2 X µ2 G2 f (n − 2f )f (n − 2f )µ2 f G0 1 f √ − = = 2 0 G0 ≤ G20 . 2 2 (n − f )L n−f d (n − f )L i=1 (n − f )d L τ n − f (n − f )2 2

2

Bounding (2.b). s 2 f G0 1 G0 1 µ2 G2 f (n − 2f )2 f µ2 √ +√ ≤ 2 0 − ≤ G20 . 2 (n − f )L n−f d L τ n − f (n − f )2 τd 2

Combining them together, it holds that 1 X 2 ∇Fi (θ) − ∇FG2 (θ) 2 ≤ 2G20 . n−f i∈G √ Therefore, for any given G > 0, we can choose G0 = G/ 2. Let D′ be an auxiliary dataset.           G 1 −G 1 0 d 0 d ′ . D = 1m ⊗ √ , . . ., 1m ⊗ √ , . . ., 1m ⊗ 01d | {z }   L τ nd L τ nd     | {z } | {z } (n−2f ) elements  f elements

f elements

Next, we show that the errors induced by D and D′ are the same in a special case. Suppose that an b √m, that auxiliary global model parameter θb′ ∈ Rmd It holds, when θb′ = 1m ⊗ θ/ • Configuration #1. b′

θ −θ

′1∗

s

f G0 1 2 √ n − f md 2 2 s 2 b θ f G0 1 √ = 1m ⊗ √ − 1m ⊗ n − f md m 2 s 2 m 2 1 X b f G0 1 √ θ− = = θb − θ 1∗ . m j=1 n−f d 2 2 2

b′

= θ − 1m ⊗

• Configuration #2. b′

θ −θ

′2∗

s

f G0 1 2 √ n − f md 2 2 s 2 b θ f G0 1 √ = 1m ⊗ √ + 1m ⊗ m − f md m 2 s 2 m 2 1 X b f G0 1 √ = θ+ = θb − θ 2∗ . m j=1 n−f d 2 2 2

b′

= θ + 1m ⊗

25

′ We construct another auxiliary dataset D± of n − f data points.       s s     ±   ± x G 1 0 f f x G 1 0 n−f ′ 1 √ √ , . . . , 1n ⊗ D± = 1m ⊗ ,  n − f L nd n − f L nd       {z } |  (n−f ) elements

b where 1 ∈ R and x± i ∈ {−1, +1} for all i ∈ [1, n − f ]. Let θ(i) denote the i-th coordinate P n−f ± ± ± ± b x ≜ of θ, i=1 xi /(n − f ), and x(i) denote the i-th coordinate of x . Since we know that ± x± (i) ∈ [−1, 1], it holds that x(i) = −1 · λ(i) + 1 · (1 − λ(i) ) for some λ(i) ≥ 0. Further, it holds that λi = λ because x± (i) is by definition identical for all i ∈ {1, . . . , d}. It follows that s s s ! ! ± x G 0 f f f G G (i) 0 0 ′ ′ ′ √ √ √ = λ θb(i) + + (1 − λ) θb(i) − θb(i) − d

n − f L md n − f L md n − f L md s s s 2 2 2 ± x G 0 f f f G G0 (i) 0 ′ ′ ′ b b b √ √ √ ⇒ θ(i) − ≤ λ θ(i) + + (1 − λ) θ(i) − . n − f L md n − f L md n − f L md 2 2 2

Since this holds for each coordinate i ∈ {1, . . . , d}, it holds that s s s 2 2 2 md md md X X X x± G0 f f G f G (i) 0 0 ′ ′ ′ √ √ √ θb(i) − ≤λ θb(i) + + (1 − λ) θb(i) − n − f L md n − f L md n − f L md i=1 i=1 i=1 2 2 2 s s s 2 2 2 ± f x G0 1 f G0 f G0 ′ ′ ′ b b b √ √ √ ⇔ θ − 1m ⊗ ≤ λ θ + 1m ⊗ + (1 − λ) θ − 1m ⊗ . n − f L md n − f L md n − f L md 2 2 2 Taking expectation with respect to the randomness in the algorithm, we have   s 2 2 ± f x G0 1  √ E  θb′ − 1m ⊗ n − f L md 2     s s 2 2 f f G 1 G 1 0 0  + (1 − λ)E  θb′ − 1m ⊗  √ √ ≤ λE  θb′ + 1m ⊗ n − f L md n − f L md 2 2      s s 2 2   f f G0 1 G0 1  , E  θb′ − 1m ⊗  . (18) √ √ ≤ max E  θb′ + 1m ⊗   n − f L md n − f L md 2 2 Recall that we have shown the indistinguishability of Configurations #1 and #2. Since the algorithm should generate the same output for all possible collections of Byzantine clients, we have for any θb′ that      2 2 ′ ′1∗ ′ ′2∗ b b max E θ − θ ,E θ − θ 2 2      s s 2 2   G G f f  , E  θb′ + 1m ⊗  √0 √0 = max E  θb′ − 1m ⊗   n − f L md n − f L md 2 2   s 2 ± (18) f x G 1 0 ′ . √ ≥ E  θb − 1m ⊗ (19) n − f L md 2 q f G0 In our data universe below, ∆ = m(n−f ) L with dimension md, and the one-way marginal ′ (average) is computed over n − f data points in the auxiliary dataset D± . It holds that   s 2     f x± G0 1  (a) f nd log(1/δ) G20 (b) f d log(1/δ) G2 √ E  θb′ − 1m ⊗ = Ω = Ω , n − f L md n − f mϵ2 (n − f )2 L2 n − f ϵ2 (n − f )2 L2 2

26

where equality (a) holds because of Corollary 2, and equality (b) holds because G2 = 2G20 . It follows that           2 2 2 2 1∗ 2∗ ′ ′1∗ ′ ′2∗ b b b b max E θ − θ ,E θ − θ = max E θ − θ ,E θ − θ 2 2 2 2   f d log(1/δ) G2 =Ω . n − f ϵ2 (n − f )2 L2 In addition,           2 2 2 2 b b , E θb − θ 2∗ = µ2 max E θb − θ 1∗ , E ∇FG2 (θ) max E ∇FG1 (θ) 2 2 2 2   2 f d log(1/δ)G ≥Ω . n − f ϵ2 (n − f )2 We can get the desired results by invoking L = Θ(µ). E.4

Proof of Theorem 1

Theorem 1 can be obtained by summing up Lemmas 1, 2, and 3. E.5

Supporting Lemmas of Appendix E n √ od √ Lemma E.4 ([60]). Let n, d ≥ 1, X = ±1/ d , and Y = [±1/ d]d . Let D ∈ X n denote a P dataset of size n, and D̄ ≜ n1 x∈D x denote the average of the samples in D. Let A : X n → Y be −o(n) an arbitrary mapping used to estimate ≤ δ ≤ 1/n1+Ω(1) . If  D̄.√Suppose that ϵ = O(1) and 2 A is (ϵ, δ)-DP and E A(D) − D̄ 1 ≤ dϱ, then ! p d log(1/δ) n=Ω . ϱϵ n √ od √ Lemma E.5. Let n, d ≥ 1, X = ±1/ d , and Y = [±1/ d]d . Let D ∈ X n denote a dataset P of size n, and D ≜ n1 x∈D x denote the average of the samples in D. Let A : X n → Y be an arbitrary mapping used to estimate D. Suppose that ϵ = O(1) and 2−o(n) ≤ δ ≤ 1/n1+Ω(1) . If A is (ϵ, δ)-DP, then   h i d log(1/δ) 2 E A(D) − D 2 = Ω , (20) ϵ2 n 2 where the expectation is taken over the randomness of A. Proof of Lemma E.5. We prove this lemma by contradiction. Suppose that (20) is not true. Then   h i d log(1/δ) 2 E A(D) − D 2 = o . ϵ2 n 2 On the other hand, we know that E





A(D) − D 1 ≤

√ dE





A(D) − D 2 ≤

√

r h i 2 d E A(D) − D 2 = o

! p d log(1/δ) . ϵn

√ √ d log(1/δ) d log(1/δ) It further implies that there exists 0 < ϱ = o( ) (i.e., n = o( )) such that ϵn ϵϱ   √ E A(D) − D 1 ≤ dϱ. p Invoking Lemma E.4, we obtain n = Ω( d log(1/δ)/ϱϵ), contradicting with n p o( d log(1/δ)/ϱϵ). Therefore, (20) must be true.

27

=

Corollary 2. Fix ∆ > 0, and let n, d ≥ 1. Define X =

n √ od √ ±∆/ d and Y = [±∆/ d]d . Let

A : kX n → kY be an arbitrary scale-invariant mapping for any k > 0, i.e., A(k · D) = k · A(D) for any dataset D ∈ X n and k > 0. For any ϵ = O(1), and 2−o(n) ≤ δ ≤ 1/n1+Ω(1) , if A is (ϵ, δ)-DP, then h i ∆2 d log(1/δ) 2 ), E A(D) − D 2 = Ω( ϵ2 n 2 where D is defined in Lemma E.5. Corollary 2 follows immediately from Lemma E.5 and the fact that A is scale invariant.

28

F

Privacy Analysis

Claim 1. When n ≥ (2 + ν)f , where ν > 0, it holds that  −2 f 2f ≍1+ . 1− n n Proof of Claim 1. It is easy to see that 1 1 1 1 = 2 = 2 2f 2 2 (n − 2f ) n (1 − n ) n

 −2 2f 1− . n

 −2 By Bernoulli inequality, it holds that 1 − 2f ≥ 1 + 4f n n . We know that (1 − x)2 + 1 − (1 − x)2 x(2 − x) 2x 1 = =1+ ≤1+ . (1 − x)2 (1 − x)2 (1 − x)2 (1 − x)2 Therefore, 1+

4f ≤ n

2f n

−2

1−

2f n

−2

1−



It follows that 

F.1

≤1+

4(2 + ν)2 f . ν2 n

≍1+

f . n

Proof of Lemma 4

We consider TM as a continuous function of h. For ease of notation, let L(h) ≜ |{j : aj < h}| be the rank of h among the unchanged values. After insertion, its position becomes L(h) + 1. The value remains untrimmed iff f + 1 ≤ L(h) + 1 ≤ n − f Case #1: L(h) < f .

⇔ f ≤ L(h) ≤ n − f − 1.

h is trimmed from below. TM(h) =

n−f X−1 1 aj = TMbottom . n − 2f j=f

Case #2: f ≤ L(h) ≤ n − f .

h is kept.

  n−f X−1 1  TM(h) = h+ aj  = TMmiddle (h). n − 2f j=f +1

Case #3: L(h) > n − f

h is trimmed from above. n−f X 1 TM(h) = aj = TMtop . n − 2f j=f +1

It is easy to see that     n−f n−f X−1 X−1 1  1 af + TMmiddle (h) = h+ aj  ≥ aj  = TMbottom , n − 2f n − 2f j=f +1

j=f +1

29

and  TMmiddle (h) =

1  h+ n − 2f

n−f X−1





aj  ≤

1  an−f + n − 2f

j=f +1

n−f X−1

 aj  = TMtop ,

j=f +1

where both inequalities hold because f ≤ L(h) ≤ n − f . Therefore, we have  if h < af ;  TMbottom , P  n−f −1 1 TM(h) = n−2f h + j=f +1 aj , if af ≤ h ≤ an−f ;   TMtop , if h > an−f . With a bit of abuse of notations, it follows that ( 1 , dTM(h) = n−2f dh 0,

if af ≤ h ≤ an−f ; otherwise.

Fig. 2 confirms this pictorially. Without loss of generality, we assume h < h′ . Therefore, TM(v) TMtop

1 slope = n−2f

TMbottom af

an−f

v

Figure 2: Demonstration of CWTM with respect to a coordinate-wise insertion value. ′

Z h′

|TM(h) − TM(h )| = h

1 dTM(h) dh ≤ dh n − 2f

Z h′ h

|h − h′ | |h − h′ | ≤ dh = n − 2f n

r 1+

4(2 + ν)2 f , ν2 n

where the last inequality follows from Claim 1. F.2

Proof of Proposition 1

Let i denote the replaced client in G1 , j denote the replaced client in its adjacent healthy client set G2 . Further, define Diff(CWTM) as the difference between the CWTM outputs of G1 and G2 . Step 1: One-dimensional analysis.

From Lemma 4, we know that

[∥Diff(CWTM)∥2 ]r ≤

|[xi ]r − [xj ]r | (1 − βt ) |[mi ]r − [mj ]r | = . n − 2f n − 2f

Step 2: High-dimensional analysis. By the definition of Byzantine user-level sensitivity, it holds that (1 − βt ) ∥Diff(CWTM)∥22 ≤

2 2 Pd r=1 |[mi ]r − [mj ]r | 2 (n − 2f )

|[mi ]r |2 + |[mj ]r |2 (n − 2f )2
2(1 − βt )2 ∥mi ∥22 + ∥mj ∥22 = (n − 2f )2

≤

≤

2(1 − βt )2

Pd

r=1

4(1 − βt )2 C 2 . (n − 2f )2

30

Step 4: Combining together. 4(1 − βt )2 C 2 4(1 − βt )2 C 2 2 ≤ ∥Diff(CWTM)∥2 ≤ 2 2 (n − 2f )



n

4(2 + ν)2 f 1+ ν2 n

 .

Therefore, we have the Byzantine user-level sensitivity of CWTM as 2

(∆(CWTM)) F.3

4(1 − βt )2 C 2 2 = max ∥Diff(CWTM)∥2 = 2 n

  4(2 + ν)2 f 1+ . ν2 n

Supporting Rényi DP Analysis

Our privacy analysis is based on Rényi differential privacy (RDP) for its tight composition guarantees. Its guarantee can be translated back to DP. First, we introduce the notions of RDP. Definition 5 ((α, ϵ)-RDP, Definition 4 in [52]). A randomized mechanism M : D → R is said to have ϵ-Rényi differential privacy of order α, or (α, ϵ)-RDP for short, if for any adjacent D, D′ ∈ X, it holds that Dα (M(D)∥M(D′ )) ≤ ϵ, 1 where Dα (M(D)∥M(D′ )) ≜ α−1 log Ex∼M(D′ ) (M(D)(x)/M(D′ )(x))α defines the Rényi divergence of order α > 1 for two probability distributions M(D) and M(D′ ).

Next, we introduce the connections between Rényi differential privacy and differential privacy [26]. Lemma F.6 (RDP to DP, Proposition 3 in [52]). If M is an (α, ϵ)-RDP mechanism, it also satisfies (ϵ + log(1/δ)/(α − 1), δ)-differential privacy for any δ ∈ (0, 1). It is well known that the Gaussian mechanism can also work under Rényi differential privacy. Lemma F.7 (Gaussian mechanism, Corollary 3 in [52]). Define Gaussian mechanism Gσdp f = 2 f + N (0, σdp I), where f is a function with l2 sensitivity ∆. The gaussian mechanism Gσdp f satisfies 2 2 (α, α∆ /2σdp )-RDP. Lemma F.8 characterizes the adaptive composition in RDP. Lemma F.8 (Adaptive composition, Proposition 1 in [52]). Let M1 : D → R1 be (α, ϵ1 )-RDP and g : R1 × D → R2 be (α, ϵ2 )-RDP, then the mechanism defined as (X, Y ), where X ∼ M1 (D) and Y ∼ M2 (X, D), satisfies (α, ϵ1 + ϵ2 )-RDP. Lemma F.9. Let δ ∈ (0, 1), Algorithm 1 is a (ϵ∗ , δ) differentially private distributed learning algorithm with   log(1/δ) ∗ ϵ = inf T ϵ(α) + , α>1 α−1 α∆2

2

dp,r

dp

α∆ where ϵ(α) = 2σ2 r = 2σ is the per-round RDP budget. 2

Proof of Lemma F.9. We characterize the privacy guarantees of Algorithm 1 based on RDP. This includes two steps: i) derive guarantees in a single global round for all clients, and ii) compose the single-round guarantees to account for the final privacy loss. Step 1: single-round guarantee. Definition 1 defines the notion of differential privacy at a system level. It shows that the output model parameter should be nearly indistinguishable when two adjacent client sets differ by only one client. We track the privacy loss through the robust gradient descent step (line 7) in Algorithm 1. In Proposition 1, we have derived the Byzantine user-level sensitivity. Step 2: T rounds composition. By Lemma F.8, we know that Algorithm 1 is (α, T ϵ(α))-RDP 2 after T rounds of execution, where ϵ(α) = α∆2 /2σdp is the per-round RDP budget. 31

Table 4: Byzantine-robust user-level sensitivity when the honest inputs to the corresponding robust aggregator are bounded by C or τ in the case of CClip. Robust Aggregator

Trimmed Mean

Coordinate Median

Geometric Median

Krum

CClip

Average (fault-free)

Sensitivity

2C n−2f

√ 2C d

2C

2C

2τ n

2C n

Now, we convert RDP guarantees back to differential privacy guarantees. By Lemma F.6, it holds that Algorithm 1 is (ϵdp , δ)-differentially private, where δ ∈ (0, 1) and ϵdp =

T −1 X

log(1/δ) log(1/δ) α∆2r αT ∆2 + + = , 2 2 2σdp,r α−1 2σdp α−1 r=0 ∆2

2

dp,r

dp

(21)

where the last equality follows from σ2 r = σ∆2 for r ∈ [T ]. F.4

Proof of Theorem 2

By Lemma F.9, since (21) holds for any α > 1, we can optimize it to obtain a tighter budget. r T ∆2Byz,r ∂ϵdp 2 log(1/δ) log(1/δ) σdp,r = > 1, − =0⇔α=1+ 2 ∂α 2σdp,r (α − 1)2 ∆Byz,r T which implies that ϵ∗dp =

T ∆2Byz,r 2 2σdp,r

σdp,r 1+ ∆Byz,r

r

2 log(1/δ) T

!

p T ∆2Byz,r ∆Byz,r 2T log(1/δ) = . + 2 2σdp,r σdp,r 2 log(1/δ)

log(1/δ) q

+

σdp,r ∆Byz,r

T

p When σdp,r ≥ 2∆Byz,r 2T log(1/δ)/ϵ and ϵ ≤ 8 log(1/δ), it holds that p T ∆2Byz,r ∆Byz,r 2T log(1/δ) ϵ ϵ ϵ ϵ2 ∗ + ≤ + = ϵ. ϵdp = + ≤ 2 2σdp,r σdp,r 16 log(1/δ) 2 2 2 F.5

Byzantine-robust User-level Sensitivity Analysis of Additional Robust Aggregators

In this section, we characterize the sensitivity of robust aggregators when a single honest client is replaced. When updates from honest clients are bounded, updates from Byzantine clients must also be bounded in the worst case. Otherwise, it is easy for the aggregator to filter out their presence. In the remainder of this section, we consider {xi }i∈[n] as the inputs to the robust aggregator. Note that et−1 + (1 − βt )c we have xti = Mit = βt R mti in Algorithm 1. Krum. Let Nj denote the set of indices of the n − f nearest neighbors of xj in {x1 , . . . , xn }, with ties arbitrarily broken. Krum outputs the vector xk∗ such that X 2 k ∗ ∈ arg min ∥xj − xi ∥2 , j∈[n]

i∈Nj

with ties arbitrarily broken if the set of minimizers above includes more than one element. Example 1. Suppose that we have a collection of five clients’ updates {x1 , . . . , x5 } such that ∥xi ∥2 = C for i ∈ [5]. Further, we assume f = 1 Byzantine client is x5 . There exist client placements where the Byzantine user-level sensitivity of Krum is 2C. Proof of Example 1. We consider two adjacent configurations, where clients are divided into two clusters C1 and C2 . Let the clients in each cluster reside at the same point, i.e., ∥xi − xj ∥2 = 0 for i, j ∈ C1 and for i, j ∈ C2 , respectively. Moreover, let ∥xi − xj ∥2 = 2C for all i ∈ C1 and all j ∈ C2 . 32

Configuration 1.

Let C1 = {x1 , x2 , x3 }, and C2 = {x4 , x5 }. It can be readily checked that Krum(x1 , . . . , x5 ) = xC1 ,

which denotes any points in C1 . Configuration 2. Without loss of generality, we replace client x1 in C1 with an auxiliary client x′ ∈ C2 . Therefore, it holds that C1 = {x2 , x3 } and {x4 , x5 , x′ }. It can be readily checked that Krum(x′ , . . . , x5 ) = xC2 , which denotes any points in C2 . Therefore, the Byzantine user-level sensitivity of Krum in this instance is 2C. Proposition 2. Let m ∈ N and f < n/2. The Byzantine-robust user-level sensitivity of Krum is 2C if ∥xi ∥2 ≤ C for i ∈ [n]. Proof of Proposition 2. We prove this by contradiction based on Example 1. Suppose that we have the Byzantine user-level sensitivity of Krum is smaller than 2C. Contradiction with Example 1. Therefore, it must be true that ∆(Krum) = 2C. It is a rather trivial bound. By the triangle inequality, we have ∆(Krum) = ∥xk1 − xk2 ∥2 ≤ ∥xk1 ∥2 + ∥xk2 ∥2 ≤ 2C, where k1 and k2 denote the indices of the minimizers of two adjacent honest client sets, respectively. Median. For input vectors x1 , . . . , xn , their coordinate-wise median, denoted by CWMed(x1 , . . . , xn ), is defined to be a vector whose k-th coordinate, for all k ∈ [d], is defined to be [CWMed(x1 , . . . , xn )]k ≜ Median([x1 ]k . . . . , [xn ]k ). Example 2. Suppose that we have a collection of five clients’ updates {x1 , . . . , x5 } such that ∥xi ∥2 = C for i ∈ [5]. Further, we assume f = 1 Byzantine client is x5 . There exist client placements where the Byzantine user-level sensitivity of CWMedian is 2C. Proof of Example 2. We consider two adjacent configurations, where clients are divided into two clusters C1 and C2 . Let the clients in each cluster reside at the same point, i.e., ∥xi − xj ∥2 = 0 for i, j ∈ C1 and for i, j ∈ C2 , respectively. Moreover, let ∥xi − xj ∥2 = 2C for all i ∈ C1 and all j ∈ C2 . More specifically, let  if i ∈ C1 ; (C, 0, . . . , 0),    | {z } d dimensions xi =  (−C, 0, . . . , 0), if i ∈ C2 .  | {z } d dimensions

Configuration 1.

Let C1 = {x1 , x2 , x3 }, and C2 = {x4 , x5 }. It can be readily checked that CWMed(x1 , . . . , x5 ) = (C, 0, . . . , 0).

Configuration 2. Without loss of generality, we replace client x1 in C1 with an auxiliary client x′ ∈ C2 . Therefore, it holds that C1 = {x2 , x3 } and {x4 , x5 , x′ }. It can be readily checked that CWMed(x′ , . . . , x5 ) = (−C, 0, . . . , 0). Therefore, the Byzantine user-level sensitivity of CWMed in this instance is 2C. Proposition 3. Let m ∈ N and f < n/2. The Byzantine-robust user-level sensitivity of CWMed is at least 2C if ∥xi ∥2 ≤ C for i ∈ [n]. Proof of Proposition 3. We prove this by contradiction based on Example 2. Suppose that we have the Byzantine user-level sensitivity of CWMed is smaller than 2C. Contradiction with Example 2. Therefore, it must be true that ∆(CWMed) is at least 2C. 33

Geometric median. The geometric median of x1 , . . . , xn ∈ Rd , denoted by GM(x1 , . . . , xn ), is defined to be a vector that minimizes the sum of the l2 distances to these vectors: GM(x1 , . . . , xn ) ∈ arg min

y∈Rd

n X

∥y − xi ∥2 .

i=1

Example 3. Suppose that we have a collection of five clients’ updates {x1 , . . . , x5 } such that ∥xi ∥2 = C for i ∈ [5]. Further, we assume f = 1 Byzantine client is x5 . There exist client placements where the Byzantine user-level sensitivity of GM is 2C. Proof of Example 3. We reuse the instances from Example 2 and consider two adjacent configurations, where clients are divided into two clusters C1 and C2 . Let the clients in each cluster reside at the same point, i.e., ∥xi − xj ∥2 = 0 for i, j ∈ C1 and for i, j ∈ C2 , respectively. Moreover, let ∥xi − xj ∥2 = 2C for all i ∈ C1 and all j ∈ C2 . More specifically, let  (C, 0, . . . , 0), if i ∈ C1 ;    | {z } d dimensions xi =  (−C, 0, . . . , 0), if i ∈ C2 .  | {z } d dimensions

Configuration 1.

Let C1 = {x1 , x2 , x3 }, and C2 = {x4 , x5 }. It can be readily checked that GM(x1 , . . . , x5 ) = (C, 0, . . . , 0).

Configuration 2. Without loss of generality, we replace client x1 in C1 with an auxiliary client x′ ∈ C2 . Therefore, it holds that C1 = {x2 , x3 } and {x4 , x5 , x′ }. It can be readily checked that GM(x′ , . . . , x5 ) = (−C, 0, . . . , 0). Therefore, the Byzantine user-level sensitivity of CWMed in this instance is 2C. Proposition 4. Let n ∈ N and f < n/2. The Byzantine-robust user-level sensitivity of GM is 2C if ∥xi ∥2 ≤ C for i ∈ [n]. Proof of Proposition 4. We prove this by contradiction based on Example 3. Suppose that we have the Byzantine user-level sensitivity of GM is smaller than 2C. Contradiction with Example 3. Therefore, it must be true that ∆(GM) is at least 2C. Next, we show that 2C is achievable. Since GM is a convex operation over a set of inputs within a convex set (∥x∥2 ≤ C). It holds that ∥GM(x1 , . . . , xn )∥2 ≤ C. Without loss of generality, we assume x1 ∈ G is replaceped with x′ . It follows that ∆(GM) = ∥GM(x1 , . . . , xn ) − GM(x′ , . . . , xn )∥2 ≤ ∥GM(x1 , . . . , xn )∥2 +∥GM(x′ , . . . , xn )∥2 ≤ 2C.

34

G

Convergence Analysis

G.1

Shared Intermediate Results t

1 For ease of notation, let M ≜ |G|

G.1.1

t 1 t i∈G Mi , m ≜ |G|

P

t 1 t i∈G mi , and g ≜ |G|

P

t i∈G gi .

P

Proof of Descent Lemma

Lemma G.10. Under Assumption 2, it holds that     3 η 2 Ld 2 2 t t+1 t E FG (θ ) − FG (θ ) F ≤ −ηt − 2ηt L ∇FG (θ t ) 2 + t σdp,t 4 2     2κηt (1 + ηt L) X t 2 t 2 t t t t F + F . + 2ηt (1 + ηt L)E ∇FG (θ ) − M E Mi − M |G| 2 2 i∈G

Proof of Lemma G.10. By Assumption 2, it holds that L t+1 2 FG (θ t+1 ) − FG (θ t ) ≤ ∇FG (θ t ), θ t+1 − θ t + θ − θt 2 . | {z } |2 {z } (A)

(B)

Bounding (A). ∇FG (θ t ), θ t+1 − θ t E E D D t t 2 t = ηt ∇FG (θ t ), M − Rt − ηt ∇FG (θ t ), M − ∇FG (θ t ) − ηt ∇FG (θ t ) 2 − ηt ∇FG (θ t ), Xdp,t (a) η

≤

t

2

∇FG (θ t ) 2 + 2ηt Rt − M

t 2

+

2 ηt t 2 2 ∇FG (θ t ) 2 + 2ηt M − ∇FG (θ t ) − ηt ∇FG (θ t ) 2 8 2

8 2 t − ηt ∇FG (θ t ), Xdp,t 2 3ηt t 2 t 2 t ∇FG (θ t ) 2 + 2ηt Rt − M + 2ηt M − ∇FG (θ t ) − ηt ∇FG (θ t ), Xdp,t , =− 4 2 2

where inequality (a) follows from Young’s inequality. Taking expectation conditional on F t , it holds that E



∇FG (θ t ), θ t+1 − θ t | F t



    2  t  3ηt t 2 t 2 ∇FG (θ t ) 2 + 2ηt E Rt − M | F t + 2ηt E M − ∇FG (θ t ) | F t − ηt ∇FG (θ t ), E Xdp,t | Ft 4 2 2     2 2 3ηt t t 2 =− ∇FG (θ t ) 2 + 2ηt E Rt − M | F t + 2ηt E M − ∇FG (θ t ) | F t . 4 2 2

≤−

Bounding (B). 2 L t+1 η2 L t t 2 t θ − θt 2 = t Rt − M + M + Xdp,t 2 2  2 D E 2 ηt2 L t t t t 2 t t t = Rt − M + M + Xdp,t + 2 R − M + M , X . dp,t 2 2 2

35

Taking expectation conditional on F t , it holds that  i η2 L   i h 2 L h t+1 t t 2 2 t t E Rt − M + M − ∇FG (θ t ) + ∇FG (θ t ) | F t + E Xdp,t | F E θ − θt 2 | F t = t 2 2 2 2 hD E i t t t + 2E Rt − M + M , Xdp,t | Ft   i h 2  2 (b) ηt L t t 2 t t E Rt − M + M − ∇FG (θ t ) + ∇FG (θ t ) | F t + E Xdp,t | F = 2 2 2 i E  D h   t t t + 2 E Rt − M + M | F t , E Xdp,t | Ft   2 ηt2 L t t 2 t t t = R − M + M − ∇FG (θ ) + ∇FG (θ ) + dσdp,t−1 2 2   (c) 2 d 2 t 2 t 2 t t t 2 ≤ ηt L 2 R − M + 2 M − ∇FG (θ ) + 2 ∇FG (θ ) 2 + σdp,t−1 2 2 2 ! X (d) 2 2 d 2 2κ t t t t 2 2 t Mi − M + 2 M − ∇FG (θ ) + 2 ∇FG (θ ) 2 + σdp,t−1 , ≤ ηt L |G| 2 2 2 i∈G

t where equality (b) holds because Xdp and Rt are independent, inequality (c) follows from Jensen’s inequality, and inequality (d) follows from the definition of robust aggregator.

Putting them together.    3 2κηt (1 + ηt L) X t 2 t t 2 t − 2ηt L ∇FG (θ ) 2 + E Mi − M |F 4 |G| 2 i∈G   η 2 Ld 2 t 2 t t σdp,t−1 . + 2ηt (1 + ηt L)E ∇FG (θ ) − M |F + t 2 2

  E FG (θ t+1 ) − FG (θ t ) | F t ≤ −ηt

G.1.2



Proof of Global Momentum Estimation Error

Lemma G.11. Let F t−1 be the sigma algebra by the randomness up to round t − 1. Suppose that Assumptions 2, and 4 hold, we have for some absolute constant k2 > 0     2 2 σ2 t t−1 − ∇FG (θ t−1 ) | F t−1 E M − ∇FG (θ t ) | F t−1 ≤ (1 − βt )2 (1 − αt )2 + CM ,1 E M |G| 2 2 h i 2 t−1 t−1 2 t−1 + CM ,2 E m − ∇FG (θ ) 2 | F + CM ,3 ∇FG (θ t−1 ) 2 i κ X h 2 2 E mt−1 − mt−1 2 | F t−1 + CM ,5 dσdp,t−1 . + CM ,4 i |G| i∈G

where 

 (1 − βt )αt + (1 − βt−1 )αt CM ,1 (αt , βt , ηt−1 L) ≜ βt βt + + ηt−1 L(βt + (1 − βt )αt ) 2k2 + 3ηt−1 L (βt + (1 − βt )αt ) ((βt + (1 − βt )αt ) (1 + ηt−1 L) + βt (1 − βt )) , CM ,2 (αt , βt , ηt−1 L) ≜ (1 − βt )αt [((1 − βt )αt + 2k2 βt ) (1 + ηt−1 L) + (1 − βt )βt ] , CM ,3 (αt , βt , ηt−1 L) ≜ 3ηt−1 L (βt + (1 − βt )αt ) ((βt + (1 − βt )αt ) (1 + ηt−1 L) + βt (1 − βt )) ,   ηt−1 L(1 − βt ) CM ,4 (αt , βt , ηt−1 L) ≜ βt (1 − βt−1 ) 2k2 βt + (1 − βt )αt + (βt + (1 − βt )αt ) 1 − βt−1 + 3(1 − βt−1 )2 ηt−1 L (βt + (1 − βt )αt ) ((βt + (1 − βt )αt ) (1 + ηt−1 L) + βt (1 − βt ))
CM ,5 (αt , βt , ηt−1 L) ≜ βt2 + ηt−1 L (βt + (1 − βt )αt ) ((βt + (1 − βt )αt ) (1 + ηt−1 L) + βt (1 − βt )) . 36

Proof of Lemma G.11. We know that

t et−1 + (1 − βt )mt − ∇FG (θ t ) M − ∇FG (θ t ) = βt R   t−1  
t−1 t−1 = βt Xdp + βt M − ∇FG (θ t−1 ) + (1 − βt ) mt − ∇FG (θ t ) − βt ∇FG (θ t ) − ∇FG (θ t−1 ) + βt Rt−1 − M   t−1  
t−1 t−1 + βt M − ∇FG (θ t−1 ) + (1 − βt ) αt mt−1 + (1 − αt )g t − ∇FG (θ t ) = βt Xdp + βt Rt−1 − M
− β ∇FG (θ t ) − ∇FG (θ t−1 )   t−1  
t−1 t−1 = βt Xdp + βt M − ∇FG (θ t−1 ) + (1 − βt )αt mt−1 − ∇FG (θ t−1 ) + βt Rt−1 − M

+ (1 − βt )(1 − αt ) g t − ∇FG (θ t ) − (βt + (1 − βt )αt ) ∇FG (θ t ) − ∇FG (θ t−1 ) .

It follows that t

M − ∇FG (θ t )

2 2

2

  2  t−1  2
2 t−1 + βt Rt−1 − M + βt M − ∇FG (θ t−1 ) + (1 − βt )αt mt−1 − ∇FG (θ t−1 ) 2 2 2 2
2
2 + (1 − βt )(1 − αt ) g t − ∇FG (θ t ) 2 + (βt + (1 − βt )αt ) ∇FG (θ t−1 ) − ∇FG (θ t ) 2 D t−1 E + 2βt (1 − βt )αt M − ∇FG (θ t−1 ), mt−1 − ∇FG (θ t−1 )

=

t−1 βt Xdp

+ 2 (βt + (1 − βt )αt ) (1 − βt )αt mt−1 − ∇FG (θ t−1 ), ∇FG (θ t−1 ) − ∇FG (θ t ) E D t−1 + 2βt (1 − βt )αt Rt−1 − M , mt−1 − ∇FG (θ t−1 ) D E t−1 + 2βt (βt + (1 − βt )αt ) Rt−1 − M , ∇FG (θ t−1 ) − ∇FG (θ t ) D E t−1 t−1 + 2βt2 Rt−1 − M , M − ∇FG (θ t−1 ) D t−1 E + 2βt (βt + (1 − βt )αt ) M − ∇FG (θ t−1 ), ∇FG (θ t−1 ) − ∇FG (θ t )
+ 2(1 − βt )(1 − αt ) g t − ∇FG (θ t ), βt Rt−1 − βt ∇FG (θ t−1 ) + (1 − βt )αt mt−1 − ∇FG (θ t−1 )
− 2(1 − βt )(1 − αt ) (βt + (1 − βt )αt ) g t − ∇FG (θ t ), ∇FG (θ t ) − ∇FG (θ t−1 ) D E t t−1 + 2 βt Xdp , βt Rt−1 + (1 − βt )M − ∇FG (θ t )  2  t−1  2  (a) 2
2 t−1 t−1 ≤ βt Xdp + βt Rt−1 − M + βt M − ∇FG (θ t−1 ) + (1 − βt )αt mt−1 − ∇FG (θ t−1 ) 2 2 2 2
2
2 t t t−1 + (1 − βt )(1 − αt ) g − ∇FG (θ ) 2 + (βt + (1 − βt )αt ) ∇FG (θ ) − ∇FG (θ t ) 2 + 2βt (1 − βt )αt M

t−1

− ∇FG (θ t−1 )

2

mt−1 − ∇FG (θ t−1 ) 2

+ 2 (βt + (1 − βt )αt ) (1 − βt )αt mt−1 − ∇FG (θ t−1 ) 2 ∇FG (θ t−1 ) − ∇FG (θ t ) 2 + 2βt (1 − βt )αt Rt−1 − M

t−1 2

+ 2βt (βt + (1 − βt )αt ) Rt−1 − M + 2βt2 Rt−1 − M

t−1

M

t−1

2

+ 2βt (βt + (1 − βt )αt ) M

t−1

mt−1 − ∇FG (θ t−1 ) 2 t−1 2

∇FG (θ t−1 ) − ∇FG (θ t ) 2

− ∇FG (θ t−1 )

− ∇FG (θ

t−1

2

) 2

∇FG (θ t−1 ) − ∇FG (θ t ) 2

+ 2(1 − βt )(1 − αt ) g t − ∇FG (θ t ), βt Rt−1 − βt ∇FG (θ t−1 ) + (1 − βt )αt mt−1 − ∇FG (θ t−1 )
− 2(1 − βt )(1 − αt ) (βt + (1 − βt )αt ) g t − ∇FG (θ t ), ∇FG (θ t ) − ∇FG (θ t−1 ) D E t−1 + 2 βt Xdp , βt Rt−1 + (1 − βt )mt − ∇FG (θ t ) , 37

where inequality (a) follows from the Cauchy-Schwarz inequality. By the definition of a robust aggregator, it holds that

R

t−1

−M

r

t−1

Rt−1 − M

=

t−1 2

2

s ≤

2

κ X t−1 2 Mit−1 − M |G| 2 i∈G

s (25) κ X 2 ≤ (1 − βt−1 ) mt−1 − mt−1 2 . i |G|

(22)

i∈G

Let (A) define the terms that include ∥Rt−1 − M

t−1

∥2 .

 2  t−1 t−1 + 2βt (1 − βt )αt Rt−1 − M (A) ≜ βt Rt−1 − M 2

2

mt−1 − ∇FG (θ t−1 ) 2

t−1

t−1

t−1

+ 2βt (βt + (1 − βt )αt ) Rt−1 − M ∇FG (θ t−1 ) − ∇FG (θ t ) 2 + 2βt2 Rt−1 − M M − ∇FG (θ t−1 ) 2 2 2 s (b) κ X 2 ≤ 2βt (1 − βt )(1 − βt−1 )αt mt−1 − mt−1 2 mt−1 − ∇FG (θ t−1 ) 2 i |G| i∈G s κ X 2 t−1 + 2ηt−1 Lβt (1 − βt )(βt + (1 − βt )αt ) mt−1 − mt−1 2 Rt−1 + Xdp i |G| 2 i∈G s κ X κ X t−1 2 2 + 2βt2 (1 − βt−1 ) mt−1 − mt−1 2 M mt−1 − mt−1 2 − ∇FG (θ t−1 ) + βt2 (1 − βt−1 )2 i i |G| |G| 2 i∈G

(c)

≤ βt2 (1 − βt−1 )2

i∈G

κ X κ X 2 2 mt−1 mt−1 − mt−1 2 + βt (1 − βt )(1 − βt−1 )αt − mt−1 2 i i |G| |G| i∈G

i∈G

t−1

+ βt (1 − βt )(1 − βt−1 )αt m

t−1

2 2

− ∇FG (θ ) 2 κ X 2 t−1 + ηt−1 Lβt (1 − βt )(βt + (1 − βt )αt ) mt−1 − mt−1 2 + ηt−1 Lβt (1 − βt )(βt + (1 − βt )αt ) Rt−1 + Xdp i |G| 2 i∈G

2 βt2 t−1 (1 − βt−1 ) M − ∇FG (θ t−1 ) |G| 2k2 2 i∈G   ηt−1 L(1 − βt ) κ X 2 = βt (1 − βt−1 ) 2k2 βt + (1 − βt )αt + (βt + (1 − βt )αt ) mt−1 − mt−1 2 i 1 − βt−1 |G|

+ 2k2 βt2 (1 − βt−1 )

κ X

2

mt−1 − mt−1 2 + i

i∈G

2

+ βt (1 − βt )(1 − βt−1 )αt mt−1 − ∇FG (θ t−1 ) 2 + t−1 + ηt−1 Lβt (1 − βt )(βt + (1 − βt )αt ) Rt−1 + Xdp

38

βt2 2k2 2

, 2

(1 − βt−1 ) M

t−1

− ∇FG (θ t−1 )

2 2

where inequality (b) follows from (22), and inequality (c) follows from Young’s inequality. Let (B) define the terms that include ∥mt−1 − ∇FG (θ t−1 )∥2 .

(B) ≜ 2βt (1 − βt )αt M

t−1

− ∇FG (θ t−1 )

2

mt−1 − ∇FG (θ t−1 ) 2

+ 2 (βt + (1 − βt )αt ) (1 − βt )αt mt−1 − ∇FG (θ t−1 ) 2 ∇FG (θ t−1 ) − ∇FG (θ t ) 2 + 2βt (βt + (1 − βt )αt ) M (d)

≤ 2βt (1 − βt )αt M

t−1

t−1

− ∇FG (θ t−1 )

− ∇FG (θ t−1 )

2

2

∇FG (θ t−1 ) − ∇FG (θ t ) 2

mt−1 − ∇FG (θ t−1 ) 2

t−1 + 2ηt−1 L (βt + (1 − βt )αt ) (1 − βt )αt mt−1 − ∇FG (θ t−1 ) 2 Rt−1 + Xdp

+ 2ηt−1 Lβt (βt + (1 − βt )αt ) M

t−1

− ∇FG (θ t−1 )

2

t−1 Rt−1 + Xdp

2

2

(e)

2 αt t−1 2 ≤ βt (1 − βt ) M − ∇FG (θ t−1 ) + 2k2 βt (1 − βt )αt mt−1 − ∇FG (θ t−1 ) 2 2k2 2 2

t−1 + ηt−1 L (βt + (1 − βt )αt ) (1 − βt )αt mt−1 − ∇FG (θ t−1 ) 2 + ηt−1 L (βt + (1 − βt )αt ) (1 − βt )αt Rt−1 + Xdp 2

t−1

2 2

2

t−1 + ηt−1 Lβt (βt + (1 − βt )αt ) M − ∇FG (θ t−1 ) + ηt−1 Lβt (βt + (1 − βt )αt ) Rt−1 + Xdp 2 2   2 αt t−1 = βt (1 − βt ) + ηt−1 L(βt + (1 − βt )αt ) M − ∇FG (θ t−1 ) 2k2 2 2

+ (1 − βt )αt (2k2 βt + ηt−1 L(βt + (1 − βt )αt )) mt−1 − ∇FG (θ t−1 ) 2 + ηt−1 L (βt + (1 − βt )αt )

2

t−1 Rt−1 + Xdp

2

, 2

where inequality (d) follows from Assumption 2, and inequality (e) follows from Young’s inequality and k2 is an absolute constant. Putting them together, it follows, by taking expectation conditional on F t , that

 E

t

t

M − ∇FG (θ )

2

|F

t



 ≤ βt

2

 2 (1 − βt )αt + (1 − βt−1 )αt t−1 − ∇FG (θ t−1 ) βt + + ηt−1 L(βt + (1 − βt )αt ) M 2k2 2 2

+ (1 − βt )αt [((1 − βt )αt + 2k2 βt ) (1 + ηt−1 L) + (1 − βt )βt ] mt−1 − ∇FG (θ t−1 ) 2   2 σ2 t−1 + (1 − βt )2 (1 − αt )2 | F t−1 + βt2 E Xdp,t |G| 2   2 t−1 + ηt−1 L (βt + (1 − βt )αt ) ((βt + (1 − βt )αt ) (1 + ηt−1 L) + βt (1 − βt )) E Rt−1 + Xdp,t | Ft 2   X ηt−1 L(1 − βt ) κ 2 + βt (1 − βt−1 ) 2k2 βt + (1 − βt )αt + (βt + (1 − βt )αt ) mt−1 − mt−1 2 i 1 − βt−1 |G| i∈G D E   t t−1 t t t−1 + 2 βt Xdp,t , βt R + (1 − βt )E m | F − ∇FG (θ ) .

Taking expectation conditional on F t−1 , it holds that

 E

t−1 Rt−1 + Xdp

2 2

| F t−1



(f )

h

  D  iE i 2  h t−1 2 t−1 Rt−1 2 | F t−1 + E Xdp,t | F t−1 + 2 E Rt−1 | F t−1 , E Xdp,t | F t−1

(g)

h

2 Rt−1 2 | F t−1

= E

= E

2

39

i

2 + dσdp,t−1 ,

(23)

where equality (f ) follows from independent DP noise, and equality (g) follows from zero-mean DP noise. It remains to bound ∥Rt−1 ∥2 2

Rt−1 2 = Rt−1 − M (g)

≤ 3 Rt−1 − M

t−1 2

t−1

+M

+3 M

2 (h) 3κ X

≤

|G|

i∈G

(i) 3(1 − β

≤

Mit−1 − M 2 X t−1 ) κ

|G|

t−1 2

t−1

t−1

− ∇FG (θ t−1 ) + ∇FG (θ t−1 )

− ∇FG (θ t−1 )

+3 M

t−1

2

2 2

2

2 2

+ 3 ∇FG (θ t−1 ) 2

− ∇FG (θ t−1 )

mt−1 − mt−1 2 + 3 M i

2

t−1

2 2

− ∇FG (θ t−1 )

i∈G

2

+ 3 ∇FG (θ t−1 ) 2 2 2

2

+ 3 ∇FG (θ t−1 ) 2 , (24)

where inequality (g) follows from Jensen’s inequality, inequality (h) follows from Definition 2, and inequality (i) follows from (22). Therefore, it further holds, by putting the above back, that   2 σ2 t E M − ∇FG (θ t ) | F t−1 ≤ (1 − βt )2 (1 − αt )2 |G| 2     2 (1 − βt )αt + (1 − βt−1 )αt t−1 + β t βt + + ηt−1 L(βt + (1 − βt )αt ) E M − ∇FG (θ t−1 ) | F t−1 2k2 2   2 t−1 + 3ηt−1 L (βt + (1 − βt )αt ) ((βt + (1 − βt )αt ) (1 + ηt−1 L) + βt (1 − βt )) E M − ∇FG (θ t−1 ) | F t−1 2 h i 2 + (1 − βt )αt [((1 − βt )αt + 2k2 βt ) (1 + ηt−1 L) + (1 − βt )βt ] E mt−1 − ∇FG (θ t−1 ) 2 | F t−1 2

+ 3ηt−1 L (βt + (1 − βt )αt ) ((βt + (1 − βt )αt ) (1 + ηt−1 L) + βt (1 − βt )) ∇FG (θ t−1 ) 2   i ηt−1 L(1 − βt ) κ X h 2 − mt−1 2 | F t−1 E mt−1 + βt (1 − βt−1 ) 2k2 βt + (1 − βt )αt + (βt + (1 − βt )αt ) i 1 − βt−1 |G| i∈G i κ X h 2 − mt−1 2 | F t−1 E mt−1 + 3(1 − βt−1 )2 ηt−1 L (βt + (1 − βt )αt ) ((βt + (1 − βt )αt ) (1 + ηt−1 L) + βt (1 − βt )) i |G| i∈G
2 + βt2 + ηt−1 L (βt + (1 − βt )αt ) ((βt + (1 − βt )αt ) (1 + ηt−1 L) + βt (1 − βt )) dσdp,t−1 .

G.1.3

Proof of Client-side Momentum Estimation Error

Lemma G.12. Under Assumptions 2, and 3, it holds that h i h i σ2 2 2 E mt − ∇FG (θ t ) 2 | F t−1 ≤ αt2 (1 + ηt−1 L)E mt−1 − ∇FG (θ t−1 ) 2 | F t−1 + (1 − αt )2 |G| i h 2 t−1 2 2 t−1 t−1 2 + 3αt ηt−1 L(1 + ηt−1 L) ∇FG (θ ) 2 + 3αt ηt−1 L(1 + ηt−1 L)E m − ∇FG (θ ) 2 | F t−1 i (1 − βt−1 )2 κ X h 2 2 + 3αt2 ηt−1 L(1 + ηt−1 L) E mt−1 − mt−1 2 | F t−1 + αt2 ηt−1 L(1 + ηt−1 L)dσdp,t−1 . i |G| i∈G

Proof of Lemma G.12. mt − ∇FG (θ t ) = αt mt−1 + (1 − αt )g t − ∇FG (θ t )


= αt mt−1 − ∇FG (θ t−1 ) + (1 − αt ) g t − ∇FG (θ t ) − αt ∇FG (θ t ) − ∇FG (θ t−1 ) . It follows that 2

2 mt−1 − ∇FG (θ t−1 ) − ∇FG (θ t ) − ∇FG (θ t−1 ) 2

+ 2(1 − αt )αt g t − ∇FG (θ t ), mt−1 − ∇FG (θ t−1 ) − ∇FG (θ t ) − ∇FG (θ t−1 ) . 2

mt − ∇FG (θ t ) 2 = (1 − αt )2 g t − ∇FG (θ t ) 2 + αt2

40

Taking expectation conditional on F t , it holds that i h i h 2 2 E mt − ∇FG (θ t ) 2 | F t = (1 − αt )2 E g t − ∇FG (θ t ) 2 | F t

2 + αt2 mt−1 − ∇FG (θ t−1 ) − ∇FG (θ t ) − ∇FG (θ t−1 ) 2 

 + 2(1 − αt )αt E g t − ∇FG (θ t ) | F t , mt−1 − ∇FG (θ t−1 ) − ∇FG (θ t ) − ∇FG (θ t−1 )

2 σ2 = αt2 mt−1 − ∇FG (θ t−1 ) − ∇FG (θ t ) − ∇FG (θ t−1 ) 2 + (1 − αt )2 |G| (a)

2

≤ αt2 (1 + ηt−1 L) mt−1 − ∇FG (θ t−1 ) 2 + αt2 (1 +

(b)

1 ηt−1 L

2

) ∇FG (θ t ) − ∇FG (θ t−1 ) 2 + (1 − αt )2

2

t−1 ≤ αt2 (1 + ηt−1 L) mt−1 − ∇FG (θ t−1 ) 2 + αt2 ηt−1 L(1 + ηt−1 L) Rt−1 + Xdp

2 2

+ (1 − αt )2

σ2 |G|

σ2 , |G|

where inequality (a) follows from Young’s inequality, and inequality (b) follows from Assumption 2. Plugging (23) and (24), it holds, by taking expectation conditional on F t−1 , that i (c) i h h 2 2 2 E mt − ∇FG (θ t ) 2 | F t−1 ≤ αt2 (1 + ηt−1 L)E mt−1 − ∇FG (θ t−1 ) 2 | F t−1 + αt2 ηt−1 L(1 + ηt−1 L)dσdp,t−1 h i 2 2 + 3αt2 ηt−1 L(1 + ηt−1 L) ∇FG (θ t−1 ) 2 + 3αt2 ηt−1 L(1 + ηt−1 L)E mt−1 − ∇FG (θ t−1 ) 2 | F t−1 i (1 − βt−1 )2 κ X h σ2 t−1 2 t−1 + 3αt2 ηt−1 L(1 + ηt−1 L) E mt−1 − m | F + (1 − αt )2 , i 2 |G| |G| i∈G

t−1 where inequality (c) follows from zero-mean and independent DP noise Xdp .

G.2 G.2.1

Strongly-convex objectives Proof of Local Momentum Drift

Lemma G.13. Under Assumptions 2, 3 and 1. When FG is strongly convex, for any αt , βt ∈ (0, 1), it holds that   i 1 X h 1 t t 2 t−1 2 2 2 2 2 E mi − m 2 F σ2 ≤ 2(1 − αt )B ηt−1 L dσdp,t−1 + 2(1 − αt ) 1 + |G| |G| i∈G i
1 X h 2 2 − mt−1 2 F t−1 + (1 − αt )G2 + αt + 6κ(1 − αt )(1 − βt−1 )2 B 2 ηt−1 L2 E mt−1 i |G| i∈G   2
t−1 2 2 2 − ∇F (θ t−1 ) F t−1 . + 2(1 − αt )B 2 1 + 3ηt−1 L2 ∇F (θ t−1 ) 2 + 6(1 − αt )B 2 ηt−1 L2 E M 2

Proof of Lemma G.13. We know that mti = αt mt−1 + (1 − αt )git . i It follows that



1 X 1 X 2 mti − mt 2 = αt mt−1 − mt−1 + (1 − αt ) git − ∇Fi (θ t ) − g t − ∇FG (θ t ) i |G| |G| i∈G i∈G
2 t + (1 − αt ) ∇Fi (θ ) − ∇FG (θ t ) 2

2 1 X = αt mt−1 − mt−1 + (1 − αt ) ∇Fi (θ t ) − ∇FG (θ t ) 2 i |G| i∈G


2 1 X + (1 − αt ) git − ∇Fi (θ t ) − g t − ∇FG (θ t ) 2 |G| i∈G



1 − αt X + αt mt−1 − mt−1 + (1 − αt ) ∇Fi (θ t ) − ∇FG (θ t ) , git − ∇Fi (θ t ) − g t − ∇FG (θ t ) . i |G| i∈G

41

Taking expectation conditional on F t , it holds that i



1 X 1 X h 2 E mti − mt 2 | F t = E[ αt mt−1 − mt−1 + (1 − αt ) git − ∇Fi (θ t ) − g t − ∇FG (θ t ) i |G| |G| i∈G i∈G
2 t t + (1 − αt ) ∇Fi (θ ) − ∇FG (θ ) 2 | F t ] i

2 1 X h = E αt mt−1 − mt−1 + (1 − αt ) ∇Fi (θ t ) − ∇FG (θ t ) 2 | F t i |G| i∈G i

2
1 X h + E (1 − αt ) git − ∇Fi (θ t ) − g t − ∇FG (θ t ) 2 | F t |G| i∈G



 1 − αt X  + E αt mt−1 − mt−1 + (1 − αt ) ∇Fi (θ t ) − ∇FG (θ t ) , git − ∇Fi (θ t ) − g t − ∇FG (θ t ) | F t i |G| i∈G i h

2 (a) 1 X = E αt mt−1 − mt−1 + (1 − αt ) ∇Fi (θ t ) − ∇FG (θ t ) 2 | F t i |G| i∈G i

2
1 X h + E (1 − αt ) git − ∇Fi (θ t ) − g t − ∇FG (θ t ) 2 | F t |G| i∈G



 1 − αt X + αt mt−1 − mt−1 + (1 − αt ) ∇Fi (θ t ) − ∇FG (θ t ) , E git − ∇Fi (θ t ) − g t − ∇FG (θ t ) | F t i |G| i∈G   (b) α X
2 1 − αt X 1 t t t 2 2 t−1 ≤ mt−1 − ∇F (θ ) − ∇F (θ ) + 2(1 − α ) 1 + m + σ2 i G t i 2 2 |G| |G| |G| i∈G i∈G   (c) α X
2 1 t t−1 t−1 2 t 2 2 2 mi − m ≤ σ2 , + (1 − αt )B ∇FG (θ ) 2 + (1 − αt )G + 2(1 − αt ) 1 + 2 |G| |G| i∈G

where equality (a) follows from independence, inequality (b) follows from Jensen’s inequality and Assumption 3, and inequality (c) follows from Assumption 1. It follows that 2

2

(1 − αt )B 2 ∇FG (θ t ) 2 = (1 − αt )B 2 ∇FG (θ t ) − ∇FG (θ t−1 ) + ∇FG (θ t−1 ) 2 2

2

≤ 2(1 − αt )B 2 ∇FG (θ t ) − ∇FG (θ t−1 ) 2 + 2(1 − αt )B 2 ∇FG (θ t−1 ) 2 t−1 2 ≤ 2(1 − αt )B 2 ηt−1 L2 Rt−1 + Xdp

2 2

2

+ 2(1 − αt )B 2 ∇FG (θ t−1 ) 2 .

We know that     i D  iE h 2 2  h t−1 t−1 t−1 t−1 t−1 2 t−1 t−1 t−1 t−1 t−1 t−1 | F + E X | F + 2 E R | F , E X | F E R + Xdp |F =E R dp dp 2 2 2 h i 2 2 = E Rt−1 2 | F t−1 + dσdp , and 2

Rt−1 2 = Rt−1 − M

t−1

+M

(22) 3(1 − βt−1 )2 κ X

≤

|G|

t−1

− ∇FG (θ t−1 ) + ∇FG (θ t−1 )

2 mt−1 − mt−1 2 + 3 i

i∈G

M

t−1

2 2

− ∇FG (θ t−1 )

2 2

2

+ 3 ∇FG (θ t−1 ) 2 .

Therefore,   2 t−1 t−1 t−1 E R + Xdp |F 2

2

  i 2 3(1 − βt−1 ) κ X h t−1 2 t−1 t−1 2 t−1 t−1 t−1 E mi − m |F + 3E M − ∇FG (θ ) | F + 3 ∇FG (θ t−1 ) 2 ≤ 2 |G| 2 i∈G

2 + dσdp,t−1 .

42

Putting it back in, it holds that i h 2 2 (1 − αt )B 2 E ∇FG (θ t ) 2 | F t−1 ≤ 2(1 − αt )B 2 ∇FG (θ t−1 ) 2   6κ(1 − αt )B 2 ηt2 L2 X t−1 2 t−1 t−1 2 E Mi − M |F + 2(1 − αt )B 2 ηt2 L2 dσdp,t−1 + |G| 2 i∈G   2 t−1 2 2 2 2 t−1 t−1 + 6(1 − αt )B ηt L E M − ∇FG (θ ) | F + 6(1 − αt )B 2 ηt2 L2 ∇FG (θ t−1 ) 2 2

i 6κ(1 − αt )(1 − βt−1 )2 B 2 ηt2 L2 X h 2 t−1 2 t−1 m | F ≤ 2(1 − αt )B 2 ∇FG (θ t−1 ) 2 + E mt−1 − i 2 |G| i∈G   2 t−1 2 + 6(1 − αt )B 2 ηt2 L2 E M − ∇FG (θ t−1 ) | F t−1 + 6(1 − αt )B 2 ηt2 L2 ∇FG (θ t−1 ) 2 2

2 + 2(1 − αt )B 2 ηt2 L2 dσdp,t−1 .

Combining everything together, it holds that   i 1 X h 1 t 2 t−1 2 2 2 2 2 2 t σ2 ≤ 2(1 − αt )B ηt−1 L dσdp,t−1 + (1 − αt )G + 2(1 − αt ) 1 + E mi − m 2 | F |G| |G| i∈G i
1 X h 2 2 E mt−1 + αt + 6κ(1 − αt )(1 − βt−1 )2 B 2 ηt−1 L2 − mt−1 2 | F t−1 i |G| i∈G   2
t−1 2 2 2 + 2(1 − αt )B 2 1 + 3ηt−1 L2 ∇FG (θ t−1 ) 2 + 6(1 − αt )B 2 ηt−1 L2 E M − ∇FG (θ t−1 ) | F t−1 . 2

G.2.2

Proof of Theorem 3

Theorem G.5 (Strongly-convex, formal). Suppose that Assumptions 2, 3, 1, and 4 hold. When 10 1 αt = 1 − 4900ηt L, βt = 1 − 55ηt L, ηt = µ(t+a such that a ≥ 49000, and B 2 ≤ 600κ , it holds L ) µ

that h E

θ

T

2 − θ∗ 2

i

     L2 (E FG (θ 0 ) − FG∗ ) Lσ 2 Lκ 1 2 2 ≲ + + 1 + σ + G µ3 T 2 µ3 T 2 |G| µ3 T 2 |G|     2   L log(1/δ)C 2 d σ 1 f κG2 + + L(1 + κ) 1 + 1 + + 2 . 3 2 2 2 |G| µ T µ µ ϵ m m µ

Proof. Define the Lyapunov function as " # X 2 1 1 2κ 1 t 2 2 W t ≜ E FG (θ t ) − FG∗ + ∇FG (θ t ) − M + ∇FG (θ t ) − mt 2 + mti − mt 2 ; 20L 15L L |G| 2 i∈G  2 L Vt ≜ t+a Wt µ #  2 " L 1 1 2κ 1 X t 2 t ∗ t t t 2 t t 2 = t+a E FG (θ ) − FG + + ∇FG (θ ) − m 2 + mi − m 2 . ∇FG (θ ) − M µ 20L 15L L |G| 2 i∈G

For ease of notation, let b t = t + aL µ . It follows that V t+1 − V t = (b t + 1)2 W t+1 − b t2 W t
= (b t + 1)2 (W t+1 − W t ) + (b t + 1)2 − b t2 W t
= (b t + 1)2 (W t+1 − W t ) + 2b t + 1 W t. 43

Next, we have  h i 2κη (1 + η L)(1 − β )2 X h i 3 2 2 t t t − 2ηt L E ∇FG (θ t ) 2 + E mti − mt 2 4 |G| i∈G   2 2 η Ld 2 t + t + 2ηt (1 + ηt L)E ∇FG (θ t ) − M σdp,t , 2 2

  E FG (θ t+1 ) − FG (θ t ) ≤ −ηt



It follows that   2 2 z1 z1 σ2 t+1 t t t+1 t − ∇FG (θ ) − M − ∇FG (θ ) | F ≤ (1 − βt+1 )2 (1 − αt+1 )2 E M L L |G| 2 2       2 z1 (1 − βt+1 )αt+1 + (1 − βt )αt+1 t t t + βt+1 βt+1 + + ηt L(βt+1 + (1 − βt+1 )αt+1 ) − 1 E M − ∇FG (θ ) | F L 2k2 2   2 t t t + 3z1 ηt (βt+1 + (1 − βt+1 )αt+1 ) ((βt+1 + (1 − βt+1 )αt+1 ) (1 + ηt L) + βt+1 (1 − βt+1 )) E M − ∇FG (θ ) | F 2 h i z1 2 + (1 − βt+1 )αt+1 [((1 − βt+1 )αt+1 + 2k2 βt+1 ) (1 + ηt L) + (1 − βt+1 )βt+1 ] E mt − ∇FG (θ t ) 2 | F t L 2 + 3z1 ηt (βt+1 + (1 − βt+1 )αt+1 ) ((βt+1 + (1 − βt+1 )αt+1 ) (1 + ηt L) + βt+1 (1 − βt+1 )) ∇FG (θ t ) 2   i κ X h z1 ηt L(1 − βt+1 ) 2 (βt+1 + (1 − βt+1 )αt+1 ) E mti − mt 2 | F t + (1 − βt )βt+1 2k2 βt+1 + (1 − βt+1 )αt+1 + L 1 − βt |G| i∈G i κ X h 2 2 E mti − mt 2 | F t + 3z1 (1 − βt ) ηt (βt+1 + (1 − βt+1 )αt+1 ) ((βt+1 + (1 − βt+1 )αt+1 ) (1 + ηt L) + βt+1 (1 − βt+1 )) |G| i∈G
2 z1 2 + β + ηt L (βt+1 + (1 − βt+1 )αt+1 ) ((βt+1 + (1 − βt+1 )αt+1 ) (1 + ηt L) + βt+1 (1 − βt+1 )) dσdp,t , L t+1 where the inequality follows from Lemma G.11. Also, i z i
h z2 h 2 2 2 2 2 E mt+1 − ∇FG (θ t+1 ) 2 − mt − ∇FG (θ t ) 2 | F t ≤ αt+1 (1 + ηt L) − 1 E mt − ∇FG (θ t ) 2 | F t L L  2

2 2 + 3z2 αt+1 ηt (1 + ηt L) ∇FG (θ t ) 2 + 3z2 αt+1 ηt (1 + ηt L)E 2 + 3z2 αt+1 ηt (1 + ηt L)

t

M − ∇FG (θ t )

2

| Ft

2

i (1 − βt )2 κ X h 2 E mti − mt 2 | F t |G| i∈G

z2 σ2 2 2 + (1 − αt+1 )2 + z2 αt+1 ηt (1 + ηt L)dσdp,t , L |G| where the inequality follows from Lemma G.12. Furthermore, i κz3 h 1 X 1 X t+1 2 t t 2 t E mt+1 − m − m − m | F i i 2 2 L |G| |G| i∈G i∈G
1 X κz3 2 αt+1 + 6κ(1 − αt+1 )(1 − βt )2 B 2 ηt2 L2 − 1 mti − mt 2 ≤ L |G| i∈G   κz 1 κz3 3 (1 − αt+1 )G2 + 2(1 − αt+1 )2 1+ σ2 + L L |G| 2 κz3 t 2 + 2(1 − αt+1 )B 2 (1 + 3ηt2 L2 ) ∇FG (θ t ) 2 + 6(1 − αt+1 )B 2 ηt2 Lκz3 M − ∇FG (θ t ) L 2 2 2 2 + 2(1 − αt+1 )B ηt Lκz3 dσdp,t , 44

where the inequality follows from Lemma 5. Putting them together and taking expectation over the remaining randomness, it holds that



 h i 3 2 W − W ≤ −ηt − 2ηt L − 3z1 (βt+1 + (1 − βt+1 )αt+1 ) ((βt+1 + (1 − βt+1 )αt+1 ) (1 + ηt L) + βt+1 (1 − βt+1 )) E ∇FG (θ t ) 2 4   h i 2 2 2 2 2 κz3 − ηt −3z2 αt+1 (1 + ηt L) − 2(1 − αt+1 )B (1 + 3ηt L ) E ∇FG (θ t ) 2 ηt L   2
t 2 2 2 t + 2ηt (1 + ηt L) + 3z2 αt+1 ηt (1 + ηt L) + 6(1 − αt+1 )B ηt Lκz3 E M − ∇FG (θ ) 2       2 (1 − βt+1 )αt+1 + (1 − βt )αt+1 z1 t t βt+1 βt+1 + + ηt L(βt+1 + (1 − βt+1 )αt+1 ) − 1 E M − ∇FG (θ ) + L 2k2 2   2 t + 3z1 ηt (βt+1 + (1 − βt+1 )αt+1 ) ((βt+1 + (1 − βt+1 )αt+1 ) (1 + ηt L) + βt+1 (1 − βt+1 )) E M − ∇FG (θ t ) 2 h i z1 t t 2 + (1 − βt+1 )αt+1 [((1 − βt+1 )αt+1 + 2k2 βt+1 ) (1 + ηt L) + (1 − βt+1 )βt+1 ] E m − ∇FG (θ ) 2 L i 2κη (1 + η L)(1 − β )2 X h i
h z2 2 2 2 t t t + αt+1 (1 + ηt L) − 1 E mt − ∇FG (θ t ) 2 + E mti − mt 2 L |G| i∈G   i z1 ηt L(1 − βt+1 ) κ X h 2 + (1 − βt )βt+1 2k2 βt+1 + (1 − βt+1 )αt+1 + E mti − mt 2 (βt+1 + (1 − βt+1 )αt+1 ) L 1 − βt |G| i∈G i κ X h 2 + 3z1 (1 − βt )2 ηt (βt+1 + (1 − βt+1 )αt+1 ) ((βt+1 + (1 − βt+1 )αt+1 ) (1 + ηt L) + βt+1 (1 − βt+1 )) E mti − mt 2 |G| i∈G i 2 X h (1 − β ) κ 2 t 2 + 3z2 αt+1 ηt (1 + ηt L) E mti − mt 2 | F t |G| i∈G i
1 X h κz3 2 + αt+1 + 6κ(1 − αt+1 )(1 − βt )2 B 2 ηt2 L2 − 1 E mti − mt 2 L |G| i∈G  
κz3 (1 − αt+1 )2 1 z1 (1 − βt+1 )2 + z2 + 2κz3 1 + σ2 + (1 − αt+1 )G2 + L |G| L  2 
ηt L z1 2 2 + + β + ηt L (βt+1 + (1 − βt+1 )αt+1 ) ((βt+1 + (1 − βt+1 )αt+1 ) (1 + ηt L) + βt+1 (1 − βt+1 )) dσdp,t 2 L t+1
2 2 + z2 αt+1 ηt (1 + ηt L) + 2(1 − αt+1 )B 2 ηt2 Lκz3 dσdp,t . t+1

t

Let αt = 1 − k1 ηt L and βt = 1 − k2 ηt L, where k2 ≤ k1 . More specifically, k1 = 4900, and k2 = 55. It follows that αt ≤ βt . We know that

10

t + aL µ(t+1+a L ηt+1 1 a µ µ) = = =1− ∈[ , 1], 10 L L ηt 1 + a t + 1 + a t + 1 + a µ µ µ(t+a L µ)

1 where the last inequality follows from t ≥ 0 and L ≥ µ. Recall that ηt ≤ 49000L , and B 2 ≤ 40k11 κ . Next, we bound the coefficients by applying the learning rate condition for ηt .

45

h i 2 Bounding C1 for E ∥∇FG (θ t )∥2 .

C1 ≜

3 − 2ηt L − 3z1 (βt+1 + (1 − βt+1 )αt+1 ) ((βt+1 + (1 − βt+1 )αt+1 ) (1 + ηt L) + βt+1 (1 − βt+1 )) 4 κz3 2 − 3z2 αt+1 (1 + ηt L) − 2(1 − αt+1 )B 2 (1 + 3ηt2 L2 ) ηt L

3 − 2ηt L − 3z1 (1 + k2 ηt L) ((1 + k2 ηt L) (1 + ηt L) + k2 ηt L) − 3z2 (1 + ηt L) − 2k1 B 2 (1 + 3ηt2 L2 )κz3 4            3 1 3 8 8 1 8 1 1 4 1 2 ≥ −2× − × 1+ × 1+ × 1+ + − × 1+ − 1+3×( ) 4 150 20 150 150 150 150 5 150 40 150 3 1 1 ≥ − − 0.19921 − 0.252 − 0.105 ≥ . 4 75 10 ≥



t

t

M − ∇FG (θ )

Bounding C2 for E

2

 .

2

2 C2 ≜ 2ηt (1 + ηt L) + 3z2 αt+1 ηt (1 + ηt L) + 6(1 − αt+1 )B 2 ηt2 Lκz3     z1 (1 − βt+1 )αt+1 + (1 − βt+1 )αt + + ηt L(βt+1 + (1 − βt+1 )αt+1 ) − 1 βt+1 βt+1 + L 2k2 + 3z1 ηt (βt+1 + (1 − βt+1 )αt+1 ) ((βt+1 + (1 − βt+1 )αt+1 ) (1 + ηt L) + βt+1 (1 − βt+1 ))
≤ 2ηt (1 + ηt L) + 3z2 ηt (1 + ηt L) + 6k1 ηt LB 2 ηt2 Lκz3   η t z1 ηt+1 + (L + L(1 + k2 ηt L)) − k2 L + 3z1 (1 + k2 ηt L) ((1 + k2 ηt L) (1 + ηt L) + k2 ηt L) L ηt      1 1 12 1 ηt 1 a 1 ) + (1 + )+ × + 1+1+ − k2 ≤ ηt 2(1 + 150 5 150 40 150 20 10 1+a       3 1 1 1 1 + 1+ 1+ 1+ + 20 10 10 150 10   ηt ak2 ≤ 50.5 − ≤ −ηt , 20 1+a where the last inequality holds because k2 ≥ 51.5(1 + a1 ).

Bounding C3 for E

h

i 2 mt − ∇FG (θ t ) 2 .

z1 z2 2 (1 − βt+1 )αt+1 [((1 − βt+1 )αt+1 + 2k2 βt+1 ) (1 + ηt L) + (1 − βt+1 )βt+1 ] + αt+1 (1 + ηt L) − 1 L L   ηt+1 k1 ≤ ηt z1 k2 [(k2 ηt L + 2k2 ) (1 + ηt L) + k2 ηt L] + z2 1 − ηt        ηt 1 1 1 4 ak1 ≤ k22 +2 1+ + + 1− 20 150 150 10 3 1+a   ηt ak1 2 ≤ 1.6k2 + 1 − ≤ −ηt , 15 1+a

C3 ≜

where the last inequality holds because k1 ≥ 1.6k22 + 16 (1 + a1 ). 46

Bounding C4 for

h

P

i∈G E

i 2 mti − mt 2 / |G|.

  ηt L(1 − βt+1 ) z1 C4 ≜ 2ηt (1 + ηt L)(1 − βt ) + (1 − βt+1 )βt+1 2k2 βt+1 + (1 − βt+1 )αt+1 + (βt+1 + (1 − βt+1 )αt+1 ) L 1 − βt 2

+ 3z1 (1 − βt )2 ηt (βt+1 + (1 − βt+1 )αt+1 ) ((βt+1 + (1 − βt+1 )αt+1 ) (1 + ηt L) + βt+1 (1 − βt+1 ))
z3 2 + 3z2 αt+1 ηt (1 + ηt L)(1 − βt )2 + αt+1 + 6κ(1 − αt+1 )(1 − βt )2 B 2 ηt2 L2 − 1 L ≤ 2ηt (1 + ηt L)(k2 ηt L)2 + z1 k2 ηt (2k2 + k2 ηt L + ηt L(1 + k2 ηt L)) + 3z1 k22 ηt2 L2 ηt (1 + k2 ηt L) ((1 + k2 ηt L) (1 + ηt L) + k2 ηt L)
+ 3z2 ηt (1 + ηt L)k22 ηt2 L2 + z3 6κk1 ηt k22 ηt2 L2 B 2 ηt2 L2 − k1 ηt+1   1 2 k2 1 1 1 1 )( ) + 2k2 + + (1 + ) ≤ ηt 2(1 + 150 10 20 10 150 10        ! 1 1 1 1 1 1 1 2 1 1 2 1 2 ak1 3 1 2 1+ 1+ + + (1 + )( ) + 2 ( ) ( ) − + ( ) 1+ 20 10 10 10 150 10 5 10 10 40 10 150 1+a   2ak1 ≤ ηt 0.021 + 0.1k22 + 5.4 × 10−3 k2 + 2 × 10−3 + 2.2 × 10−3 + 2.3 × 10−8 − 1+a   2ak 1 ≤ ηt 0.0253 + 0.1k22 + 5.4 × 10−3 k2 − ≤ −ηt , 1+a

where the last inequality holds because k1 ≥ 0.6265 + 0.05k22 + 2.7 × 10−3 k2 we bound the remaining noise coefficients.

1 + a1 . Finally,

Coefficient C5 of σ 2 .

(1 − αt+1 )2 C5 ≜ z1 (1 − βt+1 )2 + z2 + 2κz3 ≤ k12 ηt2 L L

1 20



1 10

2

1 + + 4κ 15

! ≤ k12 ηt2 L (1 + 4κ) ,

2 Coefficient C6 of dσdp,t .

 2 
ηt L z1 2 + βt+1 + ηt L (βt+1 + (1 − βt+1 )αt+1 ) ((βt+1 + (1 − βt+1 )αt+1 ) (1 + ηt L) + βt+1 (1 − βt+1 )) 2 L
2 + z2 αt+1 ηt+1 (1 + ηt L) + 2(1 − αt+1 )B 2 ηt2 Lκz3  2       ! 1 1 1 1 1 1 1 1 1 ≤ + 1+ 1+ 1+ 1+ + L 2 49000 20 49000 10 10 49000 10  2 !
1 1 1 1 2×2 1 1 0.06 + (1 + )+ 0.051 + 1.4 × 10−6 ≤ . ≤ L 15 49000 49000 40 49000 L L

C6 ≜

47

Putting them together.

  h i i ηt h t 2 2 2 E ∇FG (θ t ) 2 − ηt E ∇FG (θ t ) − M − ηt E mt − ∇FG (θ t ) 2 10 2   i h X 1 0.06 2 κηt 2 E mti − mt 2 + k12 ηt2 L(1 + 4κ) 1 + σ 2 + 2κk1 ηt G2 + dσdp,t − |G| |G| L i∈G !   i i κz 1 X h  z1  µηt z2 h t 2 3 t ∗ t t t 2 t t 2 ≤− E FG (θ ) − FG + E ∇FG (θ ) − M + E m − ∇FG (θ ) 2 + E mi − m 2 5 µ µ µ |G| 2 i∈G   1 0.06 2 2 2 σ 2 + 2κk1 ηt G2 + dσdp,t + k1 ηt L(1 + 4κ) 1 + |G| L !   i κz 1 X h i h (a) 2   z z µηt t 2 2 2 3 1 + E mt − ∇FG (θ t ) 2 + E FG (θ t ) − FG∗ + E ∇FG (θ t ) − M E mti − mt 2 ≤ − 5 L L L |G| 2 i∈G   1 0.06 2 + k12 ηt2 L(1 + 4κ) 1 + σ 2 + 2κk1 ηt G2 + dσdp,t |G| L   µηt t 1 0.06 2 2 2 W + k1 ηt L(1 + 4κ) 1 + dσdp,t , =− σ 2 + 2κk1 ηt G2 + 5 |G| L

W t+1 − W t ≤ −

where inequality (a) holds because µ ≤ L. By plugging ηt in, we have !   1 2(b t + 1)2 (b t + 1)2 t+1 t V −V ≤− L(1 + 4κ) 1 + σ2 − (2b t + 1) W t + 100k12 b |G| µ2 (b t)2 t + 20κk1

t + 1)2 2 (b t + 1)2 2 0.06(b G + dσdp,t . L µb t

We know that 2(b t + 1)2 2(b t + 1)2 − (2b t + 1) ≥ − (2b t + 1) ≥ 1 > 0. b b t t+1 It can be readily checked that, !2  2  2 b 1 1 t+1 = 1+ ≤ 1+ ≤ 2. b b a t t We also know that 24(1 − βr )2 T log(1/δ)C 2 d2 2 dσdp,r ≤ 2 2 ϵ n

    2 2 2 4(2 + ν)2 f 4(2 + ν)2 f 2 2 24k2 log(1/δ)C d 1+ = T ηr L 1+ . ν2 n ϵ2 n 2 ν2 n

For ease of presentation, let Cdp ≜

24k22 log(1/δ)C 2 d ϵ2 n 2

  4(2 + ν)2 f 1+ . ν2 n

It follows that   1 σ2 G2 0.12T LCdp V t+1 − V t ≤ 200k12 L(1 + 4κ) 1 + + 20κk1 b t + . 2 |G| µ µ µ2 By telescoping sum, we have V t+1 − V 0 =

t X

V k+1 − V k

k=0

≤ 200(t + 1)k12 L(1 + 4κ)



1 1+ |G|



48

σ2 0.12T L(t + 1)Cdp 20 + + 2 2 µ µ µ

t  X r=0

L r+a µ

!

κk1 G2 .

We know that t  X r=0

L r+a µ

 =

t(t + 1) L + a(t + 1) . 2 µ

Therefore, V t+1 − V 0 =

t X

V k+1 − V k

k=0

      T LCdp 1 t L 1 σ2 2 + + + a κk G . ≤ 200(t + 1) k12 L(1 + 2κ) 1 + 1 |G| µ2 µ2 µ 2 µ By definition, it holds that   L V t+1 ≥ (t + 1 + a )2 E FG (θ t+1 ) − FG∗ . µ Rearrange the terms, we have   E FG (θ t+1 ) − FG∗ ≤

V0 2 (t + 1 + a L µ)

     L T LCdp 1 t 1 σ2 2 + + κk G + a k12 L(1 + 2κ) 1 + 1 |G| µ2 µ2 µ 2 µ     V0 200 1 σ2 T LCdp 100 2 ≤ + k L(1 + 2κ) 1 + + + κk1 G2 . 1 L 2 L 2 2 |G| µ µ µ (t + 1 + a µ ) t + 1 + aµ +

200(t + 1) 2 (t + 1 + a L µ)



It remains to bound V0 . !  2 L z1 κz3 1 X z2 0 2 0 0 t 0 ∗ 0 2 t 2 ∇FG (θ ) − M ∇FG (θ ) − m 2 + mi − m 2 . V0 = a FG (θ ) − FG + + µ L L L |G| 2 i∈G

By definition, we have m0 = β0 R−1 + (1 − β0 )m0 = β0 R−1 + (1 − β0 )α0 m−1 + (1 − β0 )(1 − α0 )g 0 = (1 − β0 )(1 − α0 )g 0 , where the last equality follows from the convention that R−1 = m−1 = 0. It follows that 0

M − ∇FG (θ 0 )

2 2

2 = (1 − β0 )(1 − α0 ) g 0 − ∇FG (θ 0 ) − (1 − (1 − β0 )(1 − α0 ))∇FG (θ 0 ) 2 2

2

≤ (1 − β0 )(1 − α0 ) g 0 − ∇FG (θ 0 ) 2 + (1 − (1 − β0 )(1 − α0 )) ∇FG (θ 0 ) 2 , where the last inequality holds because of Jensen’s inequality. Take expectation, we have   i h h i 2 0 2 2 E M − ∇FG (θ 0 ) ≤ (1 − β0 )(1 − α0 )E g 0 − ∇FG (θ 0 ) 2 + (1 − (1 − β0 )(1 − α0 ))E ∇FG (θ 0 ) 2 2

≤

h i σ2 2 + E ∇FG (θ 0 ) 2 |G|

Similarly, we have h i h i
2 2 E m0 − ∇FG (θ 0 ) 2 = E α0 m−1 + (1 − α0 ) g 0 − ∇FG (θ 0 ) − α0 ∇FG (θ 0 ) 2 h i
(a) 2 = E (1 − α0 ) g 0 − ∇FG (θ 0 ) − α0 ∇FG (θ 0 ) 2 h i h
2i (b) 2 = E (1 − α0 ) g 0 − ∇FG (θ 0 ) 2 + E α0 ∇FG (θ 0 ) 2 h i σ2 2 + E ∇FG (θ 0 ) 2 , ≤ |G| 49

where equality (a) follows from the convention that m−1 = 0, and equality (b) follows from the independence in stochastic gradients. Next, we have ∇FG (θ 0 ) − M

0 2 2

= ∇FG (θ 0 ) − M

0 2 2

2

= ∇FG (θ 0 ) 2 ≤ 2L(FG (θ 0 ) − FG∗ ),

and i 1 X h 2 E m0i − m0 2 |G| i∈G i
1 X h 2 E (1 − α0 ) (gi0 − ∇Fi (θ 0 )) − (g 0 − ∇FG (θ 0 ) + (1 − α0 )(∇Fi (θ 0 ) − ∇FG (θ 0 )) 2 = |G| i∈G i
2 1 X h 2 E (1 − α0 ) (gi0 − ∇Fi (θ 0 )) − (g 0 − ∇FG (θ 0 ) 2 + (1 − α0 )(∇Fi (θ 0 ) − ∇FG (θ 0 )) 2 = |G| i∈G   h i 1 2 ≤2 1+ σ 2 + B 2 E ∇FG (θ 0 ) 2 + G2 . |G| Combining everything together, it holds that 

2

  z1 z2 κz3 1 X 0 2 2 2 ∇FG (θ 0 ) − m0 2 + E FG (θ 0 ) − FG∗ + ∇FG (θ 0 ) − M mti − mt 2 + V0 = L L L |G| 2 i∈G  2   2  h i   L z1 + z2 σ 2 ≤ a E FG (θ 0 ) − FG∗ + + E ∇FG (θ 0 ) 2 µ L |G|  2     h i L κz3 1 2 + a 2 1+ σ 2 + B 2 E ∇FG (θ 0 ) 2 + G2 µ L |G|      2   
2 σ2 2κ 1 L 0 ∗ 2 2 6 E FG (θ ) − FG + + 2 1+ σ +G . ≤ a µ L |G| L |G| L a µ

!

Putting everything together, we have         6a2 L2 (E FG (θ 0 ) − FG∗ ) 2a2 Lσ 2 2a2 Lκ 1 t+1 ∗ 2 2 E FG (θ ) − FG ≤ + 2 + 2 2 1+ σ +G 2 2 2 |G| µ2 (t + 1 + a L µ (t + 1 + a L µ (t + 1 + a L µ) µ ) |G| µ)     T LCdp 100 200 1 σ2 2 κk1 G2 + + + k L(1 + 2κ) 1 + 1 2 2 |G| µ µ µ t + 1 + aL µ       2 2 6a L (E FG (θ 0 ) − FG∗ ) 2a2 Lσ 2 2a2 Lκ 1 2 2 ≤ + + 2 1 + σ + G µ2 (t + 1)2 µ2 (t + 1)2 |G| µ2 (t + 1)2 |G|    2  200 1 σ T LCdp 100 + k12 L(1 + 2κ) 1 + + + κk1 G2 . t+1 |G| µ2 µ2 µ For µ-strongly convex objectives, we also know that FG (θ t ) − FG∗ ≥

µ t 2 θ − θ∗ 2 . 2

Therefore, we have h E

θ

t

2 − θ∗ 2

i

     L2 (E FG (θ 0 ) − FG∗ ) Lσ 2 Lκ 1 2 2 + + 1 + σ + G ≲ µ3 t2 µ3 t2 |G| µ3 t2 |G|    2  1 1 σ T LCdp κG2 + L(1 + κ) 1 + + + 2 . t |G| µ3 µ3 µ 50

In particular, when t = T , it holds that    i L2 (E F (θ 0 ) − F ∗ ) h Lσ 2 1 Lκ 2 G G 2 2 + 1 + + σ E θT − θ∗ 2 ≲ + G µ3 T 2 µ3 T 2 |G| µ3 T 2 |G|   2 2 κG 1 σ LCdp + 2 + L(1 + κ) 1 + + |G| µ3 T µ3 µ      2 0 ∗ 2 L (E FG (θ ) − FG ) Lσ 1 Lκ 2 2 + 3 2 1+ ≲ + σ +G µ3 T 2 µ T |G| µ3 T 2 |G|    2    f 1 σ L log(1/δ)C 2 d κG2 1 + . + L(1 + κ) 1 + + + |G| µ3 T µ µ2 ϵ2 n2 n µ2

G.3

Non-convex objectives

In the analysis of non-convex objectives, we adopt a constant learning rate, i.e., ηt = η, βt = β, and αt = α. G.3.1

Proof of Lemma 5

It holds, for i ∈ G, that  
t et−1 + (1 − β)c et−1 + (1 − β)mt = (1 − β) m cti − mt . mti − β R Mit − M = β R It follows that (1 − β)2 X (1 − β)2 X 1 X t 2 2 2 cti − mt 2 = Mit − M = m mti − mt 2 , |G| |G| |G| 2 i∈G

i∈G

(25)

i∈G

cti = mti for i ∈ G. Furthermore, it holds for i ∈ G where the last equality holds from the fact that m that mti = αmt−1 + (1 − α) git = (1 − α) i

t X

αt−r gir .

r=0

It follows that t 2
1 X (1 − α) X X t−r r 2 mti − mt 2 = α gi − g t |G| |G| r=0 i∈G

≤

i∈G

2 X

t X

i∈G

r=0

3 (1 − α) |G| |

+

2

2

αt−r (gir − ∇Fi (θ r )) {z

(A) 2 X

t X

i∈G

r=0

3 (1 − α) |G| |

2

}2 2

αt−r (∇FG (θ r ) − g r )

2

+ }2

{z

(B)

t 2 3 (1 − α) X X t−r α (∇Fi (θ r ) − ∇FG (θ r )) , |G| i∈G r=0 | {z }2 (C)

where the inequality follows from Jensen’s inequality. Bounding (A).   2 t t 2 2 i 3 (1 − α)2 3 (1 − α) X  X t−r r 3 (1 − α) X X 2(t−r) h r 2 α (gi − ∇Fi (θ r ))  = E α E ∥gi − ∇Fi (θ r )∥2 ≤ σ2 , 2 |G| |G| 1 − α r=0 r=0 i∈G

2

i∈G

where the equality and the inequality both follow from Assumption 3. 51

Bounding (B).   2 t t 2 2 i 3 (1 − α)2 σ 2 3 (1 − α) X X 2(t−r) h 3 (1 − α) X  X t−r 2 E α (∇FG (θ r ) − g r )  = , α E ∥∇FG (θ r ) − g r ∥2 ≤ |G| |G| 1 − α2 |G| r=0 r=0 i∈G

i∈G

2

where the equality and the inequality both follow from Assumption 3. Furthermore, it holds that 1−α (1 − α)(1 + α) (1 − α)2 = ≤ (1 − α)(1 + α) = 1 − α2 . = 2 1−α 1+α (1 + α)2

Bounding (C). 2 X

3 (1 − α) |G|

i∈G

 E

t X

2

α

t−r

r

r

(∇Fi (θ ) − ∇FG (θ ))

r=0

2

≤ 3 (1 − α)

t X



2

 ≤ 3 (1 − α) |G|

t X r=0

! α

t−r

t XX

h i 2 αt−r E ∥∇Fi (θ r ) − ∇FG (θ r )∥2

i∈G r=0

t i i  h  h X 2 2 αt−r E ∥∇FG (θ r )∥2 . αt−r B 2 E ∥∇FG (θ r )∥2 + G2 ≤ 3G2 + 3B 2 (1 − α) r=0

r=0

Putting them together, it holds that   t i i h X
1 X h 1 2 t t 2 E mi − m 2 ≤ 3 1 + 1 − α2 σ 2 + 3G2 + 3B 2 (1 − α) αt−r E ∥∇FG (θ r )∥2 . |G| |G| r=0 i∈G

G.3.2

Proof of Theorem 4

Theorem G.6. Suppose that Assumptions 2, 3, and 4 hold. Let α = 1 − 5100ηL, β = 1 − 50ηL. η < 1/(5100L), and B 2 < 1/(23625κ), it holds for Algorithm 1 that

T −1 i 30(E F (θ 0 ) − F ∗ ) 25dσ 2 1 X h 2ηL σ2 σ2 G dp G t 2 E ∇FG (θ ) 2 ≤ + + k1 (k1 + k2 ) + 4k12 ηL T t=0 ηT ηL T |G| |G|   1 + 47250k1 ηLκ 1 + σ 2 + 23625κG2 . |G|

Proof. By Lemma G.10, we know that

  E FG (θ t+1 ) − FG (θ t ) | F t ≤ −η



3 − 2ηL 4



+ 2η(1 + ηL)E

h



2κη(1 + ηL) X t 2 2 ∇FG (θ ) 2 + E Mit − M | Ft |G| 2 i∈G i η 2 Ld 2 2 ∇FG (θ t ) − mt 2 | F t + σdp . 2

52

t



t

Define Lyapunov function V t ≜ E[FG (θ t )] + E[∥∇FG (θ t ) − M ∥22 ]/16L + E[∥∇FG (θ t ) − mt ∥22 ]/16L, we have

         1 t+1 2 t 2 V t+1 − V t = E FG (θ t+1 ) − E FG (θ t ) + E ∇FG (θ t+1 ) − M − E ∇FG (θ t ) − M 16L 2 2 i h i 1  h 2 2 + E ∇FG (θ t+1 ) − mt+1 2 − E ∇FG (θ t ) − mt 2 16L    h i 2κη(1 + ηL) X  3 t 2 2 t t ≤ −η E Mi − M − 2ηL E ∇FG (θ ) 2 + 4 |G| 2 i∈G   β 2 + ηL (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) 2 η 2 Ld 2 t 2 σdp + dσdp + 2η(1 + ηL)E ∇FG (θ t ) − M + 2 16L 2     h i (1 − β)2 (1 − α)2 σ 2 1 t 2 2 − + E ∇FG (θ t ) − mt 2 + E ∇FG (θ t ) − M 16L 16L |G| 2     2 (1 − β)α β t + β+ + ηL(β + (1 − β)α) E M − ∇FG (θ t ) 16L k2 2   2 3η t + (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) E M − ∇FG (θ t ) 16 2 h i (1 − β)α 2 t t + [((1 − β)α + 2k2 β) (1 + ηL) + (1 − β)β] E m − ∇FG (θ ) 2 16L h i 3η 2 + (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) E ∇FG (θ t ) 2 16 i (1 − β)β κ X h 2 (2k2 β + (1 − β)α + ηL(β + (1 − β)α)) E mti − mt 2 + 16L |G| i∈G +

i 3(1 − β)2 η κ X h 2 (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) E mti − mt 2 16 |G| i∈G

i α2 η(1 + ηL) α2 (1 + ηL) h (1 − α)2 σ 2 2 2 E mt − ∇FG (θ t ) 2 + dσdp + 16L 16 16L |G| i 3α2 η(1 + ηL) h i 3α2 η(1 + ηL) (1 − β)2 κ X h i 3α2 η(1 + ηL) h 2 2 2 + E ∇FG (θ t ) 2 + E mt − ∇FG (θ t ) 2 + E mti − mt 2 . 16 16 16 |G| i∈G +

53

Rearrange the terms, we have V t+1 − V t   h i 3 3 3α2 (1 + ηL) 2 ≤ −η − (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) − − 2ηL E ∇FG (θ t ) 2 4 16 16 i 2 2 X h (3α + 32)η(1 + ηL) (1 − β) κ 2 + E mti − mt 2 16 |G| i∈G i (1 − β)β κ X h 2 + (2k2 β + (1 − β)α + ηL(β + (1 − β)α)) E mti − mt 2 16L |G| i∈G i 2 3(1 − β) η κ X h 2 + (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) E mti − mt 2 16 |G| i∈G      1 β α t 2 + 2η(1 + ηL) − + β + (1 − β) + ηL(β + (1 − β)α) E ∇FG (θ t ) − M 16L 16L k2 2  
3η t 2 + (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) + α2 (1 + ηL) E ∇FG (θ t ) − M 16 2   h i 2 1 α (1 + ηL) (1 − β)α 2 + − + + [((1 − β)α + 2k2 β) (1 + ηL) + (1 − β)β] E mt − ∇FG (θ t ) 2 16L 16L 16L  2  2 η L β + ηL (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) α2 η(1 + ηL) 2 + + + dσdp 2 16L 16 (1 − α)2 (1 + (1 − β)2 ) σ 2 . + 16L |G| t

Next, we bound the coefficients of the terms E[∥∇FG (θ t ) − M ∥22 ] and E[∥∇FG (θ t ) − mt ∥22 ]. Recall the definition of α = 1 − k1 ηL = 1 − 5100ηL and β = 1 − k2 ηL = 1 − 50ηL, it holds that α ≤ β. t

Bounding C1 for E[∥∇FG (θ t ) − M ∥22 ].   1 β α C1 ≜ 2η(1 + ηL) − + β + (1 − β) + ηL(β + (1 − β)α) 16L 16L k2
3η + (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) + α2 (1 + ηL) 16 k2 η η 3η ≤ 2η(1 + ηL) − + (1 + (1 + k2 ηL)) + ((1 + k2 ηL) ((1 + k2 ηL) (1 + ηL) + k2 ηL) + (1 + ηL)) 16 16 16 η ≤ − (k2 − 32(1 + ηL) − (2 + k2 ηL) − 3 (1 + k2 ηL) ((1 + k2 ηL) (1 + ηL) + k2 ηL + (1 + ηL))) 16 η 5η ≤ − (50 − 33 − 2.5 − 12) = − < 0, 16 32 1 where the third to last inequality holds because η ≤ 132L and k2 = 50.

Bounding C2 for E[∥∇FG (θ t ) − mt ∥22 ]. 1 α2 (1 + ηL) (1 − β)α + + [((1 − β)α + 2k2 β) (1 + ηL) + (1 − β)β] 16L 16L 16L
1 ≤− 1 − α − α2 ηL − (1 − β)α (((1 − β)α + 2k2 β) (1 + ηL) + (1 − β)β) 16L
η ≤− k1 − 1 − k22 ((ηL + 2) (1 + ηL) + ηL) 16    η 3 1 1 1 20η ≤− 5100 − − 4 − 332 ( + 2) × ( + 1) + <− < 0, 16 132 132 132 132 16

C2 ≜ −

54

1 where the second to last inequality holds because η ≤ 132L and k1 = 5100. Therefore, we have

V t+1 − V t  h  i 3α2 (1 + ηL) 3 3 2 − (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) − − 2ηL E ∇FG (θ t ) 2 ≤ −η 4 16 16 i (3α2 + 32)η(1 + ηL) (1 − β)2 κ X h 2 E mti − mt 2 + 16 |G| i∈G i (1 − β)β κ X h 2 + (2k2 β + (1 − β)(β + α) + ηL(β + (1 − β)α)) E mti − mt 2 16L |G| i∈G i 3(1 − β)2 η κ X h 2 (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) E mti − mt 2 16 |G| i∈G   h i 2 (1 − α) (1 + (1 − β)2 ) σ 2 t 2 2 + C2 E mt − ∇FG (θ t ) 2 + + C1 E ∇FG (θ t ) − M 16L |G| 2  2  2 2 β + ηL (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) α η(1 + ηL) η L 2 + + + dσdp 2 16L 16  h  i 3α2 (1 + ηL) 3 3 2 − (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) − − 2ηL E ∇FG (θ t ) 2 ≤ −η 4 16 16 i h 2 2 2 X (3α + 32)η(1 + ηL) (1 − β) κ (1 − α) (1 + (1 − β)2 ) σ 2 2 + E mti − mt 2 + 16 |G| 16L |G| i∈G i h X (1 − β)β κ 2 + (2k2 β + (1 − β)α + ηL(β + (1 − β)α)) E mti − mt 2 16L |G| i∈G +

i 3(1 − β)2 η κ X h 2 (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) E mti − mt 2 16 |G| i∈G  2  β 2 + ηL (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) α2 η(1 + ηL) η L 2 + + + dσdp . 2 16L 16 +

Furthermore, it holds for the coefficients of E[∥∇FG (θ t )∥22 ] that 3 3 3α2 (1 + ηL) − (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) − − 2ηL 4 16 16 3 3(1 + ηL) 2 3 (1 + k2 ηL) ((1 + k2 ηL) (1 + ηL) + k2 ηL) − − 2ηL ≥ , ≥ − 4 16 16 25 where the last inequality follows from η ≤ 1/132L and k2 = 50.   Bounding C3 for E ∥mti − mt ∥22 . (3α2 + 32)η(1 + ηL)(1 − β)2 (1 − β)β + (2k2 β + (1 − β)(β + α) + ηL(β + (1 − β)α)) 16 16L 3(1 − β)2 η + (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) 16 35k22 η 3 L2 (1 + ηL) k2 η 3k 2 η 3 L2 ≤ + (2k2 + 2k2 ηL + ηL(1 + k2 ηL)) + 2 (1 + k2 ηL) ((1 + k2 ηL) (1 + ηL) + k2 ηL) 16 16 16
  50 2 1 35η 132 (1 + 132 ) 50η 2 × 50 1 50 ≤ + 2 × 50 + + × (1 + ) 16 16 132 132 132
50 2 3 132 η 50 50 1 50 + (1 + ) × ((1 + ) × (1 + )+ ) 16 132 132 132 132 ≤ η (0.316 + 314 + 0.06558) ≤ 315η.

C3 ≜

55

Moreover, we have η 2 L β 2 + ηL (β + (1 − β)α) ((β + (1 − β)α) (1 + ηL) + β(1 − β)) α2 η(1 + ηL) + + 2 16L 16 !




1 2 1 50 50 1 50 1 1 1 + 132 1 + 132 × 1 + 132 × 1 + 132 + 132 1 132 132 × (1 + 132 ) ≤ + + L 2 16 16 ≤

3 × 10−5 + 0.065 + 5 × 10−4 1 ≤ . L L

Hence, the inequality simplifies to V t+1 − V t ≤ −

i dσ 2 i 315ηκ X h k2 η2 L σ2 2η h 2 2 dp E ∇FG (θ t ) 2 + E mti − mt 2 + + 1 25 |G| L 8 |G| i∈G

i dσ 2 2η h k2 η2 L σ2 2 dp ≤ − E ∇FG (θ t ) 2 + + 1 25 L 8 |G|   t h i X
1 2 + 945κη 1 + 1 − α2 σ 2 + 945κηG2 + 945κηB 2 (1 − β)2 (1 − α) αt−r E ∥∇FG (θ r )∥2 . |G| r=0 By telescoping sum, it holds that T −1 i dσ 2 VT −V0 2η 1 X h k2 η2 L σ2 2 dp ≤− E ∇FG (θ t ) 2 + + 1 T 25 T t=0 L 8 |G|   T −1 t i
2 1 X X t−r h 1 2 2 2 2 α E ∥∇FG (θ r )∥2 1 − α σ + 945κηG + 945κηB (1 − α) + 945κη 1 + |G| T t=0 r=0 T −1 i dσ 2 2η 1 X h k2 η2 L σ2 2 dp E ∇FG (θ t ) 2 + + 1 25 T t=0 L 8 |G| !   −1 T −1 i TX
2 1 X h 1 2 2 2 t 2 r 1 − α σ + 945κηG + 945κηB (1 − α) α + 945κη 1 + E ∇FG (θ ) 2 |G| T t=0 r=0   TX   −1 h i dσ 2
2 1 k12 η 2 L σ 2 1 dp t 2 2 ≤ −η − 945κB E ∇FG (θ ) 2 + + + 945κη 1 + 1 − α2 σ 2 + 1638κηG2 . 25 T t=0 L 8 |G| |G|

≤−

For some B 2 < 1/(23625κ), it holds that   T −1 i dσ 2
VT −V0 η 1 X h k2 η2 L σ2 1 2 dp E ∇FG (θ t ) 2 + 1 − α2 σ 2 + 945κηG2 . ≤− + 1 + 945κη 1 + T 25 T t=0 L 8 |G| |G| Rearrange the terms, we have   T −1 i 25(V 0 − V T ) 25dσ 2 1 X h σ2 1 dp t 2 2 E ∇FG (θ ) 2 ≤ + + 4k1 ηL + 47250k1 ηLκ 1 + σ 2 + 23625κG2 , T t=0 ηT ηL |G| |G| where the inequality holds because (1 − α2 ) = (1 − α)(1 + α) ≤ 2(1 − α). For the term −V T , it holds that −V T ≤ −FG∗ . For the term V 0 , it holds that 0

V 0 = E[FG (θ 0 )] + E[∥∇FG (θ 0 ) − M ∥22 ]/16L + E[∥∇FG (θ 0 ) − m0 ∥22 ]/16L. 56

By definition, we have 0 e−1 + (1 − β)m0 = β R e−1 + (1 − β)αm−1 + (1 − β)(1 − α)g 0 = (1 − β)(1 − α)g 0 , M = βR

e−1 = m−1 = 0. It follows that where the last equality follows from the convention that R 2
0 2 M − ∇FG (θ 0 ) = (1 − β)(1 − α) g 0 − ∇FG (θ 0 ) − (1 − (1 − β)(1 − α))∇FG (θ 0 ) 2 2

2

2

≤ (1 − β)(1 − α) g 0 − ∇FG (θ 0 ) 2 + (1 − (1 − β)(1 − α)) ∇FG (θ 0 ) 2 , where the last inequality holds because of Jensen’s inequality. Take expectation, we have   h i h i 2 0 2 2 ≤ (1 − β)(1 − α)E g 0 − ∇FG (θ 0 ) 2 + (1 − (1 − β)(1 − α))E ∇FG (θ 0 ) 2 E M − ∇FG (θ 0 ) 2

≤ k1 k2 η 2 L2

i h σ2 2 + E ∇FG (θ 0 ) 2 |G|

Similarly, we have h i h i
2 2 E m0 − ∇FG (θ 0 ) 2 = E αm−1 + (1 − α) g 0 − ∇FG (θ 0 ) − α∇FG (θ 0 ) 2 h i
(a) 2 = E (1 − α) g 0 − ∇FG (θ 0 ) − α∇FG (θ 0 ) 2 i h h
2i (b) 2 = E (1 − α) g 0 − ∇FG (θ 0 ) 2 + E α∇FG (θ 0 ) 2 h i σ2 2 ≤ (1 − α)2 + E ∇FG (θ 0 ) 2 , |G| where equality (a) follows from the convention that m−1 = 0, and equality (b) follows from the independence in stochastic gradients. Putting them together, we have V 0 ≤ E[FG (θ 0 )] + η 2 L

k1 (k1 + k2 ) σ 2 1 + E[∥∇FG (θ 0 )∥22 ]. 16 |G| 8L

We know, for a smooth objective, that E[∥∇FG (θ 0 )∥22 ] ≤ 2L(FG (θ 0 ) − FG∗ ). It follows that V 0 ≤ E[FG (θ 0 )] + η 2 L

k1 (k1 + k2 ) σ 2 1 + E[FG (θ 0 ) − FG∗ ]. 16 |G| 4

Combining everything together, we have T −1 i 30(E F (θ 0 ) − F ∗ ) 25dσ 2 1 X h 2ηL σ2 σ2 G dp G t 2 E ∇FG (θ ) 2 ≤ + + k1 (k1 + k2 ) + 4k12 ηL T t=0 ηT ηL T |G| |G|   1 + 47250k1 ηLκ 1 + σ 2 + 23625κG2 . |G|

G.3.3

Proof of Corollary 1

Corollary 3. Suppose that Assumptions 2, 3, 1, and 4 hold. When m ≥ (2 + ν)f , where ν > 0 is an absolute constant, we have for Algorithm 1 with coordinate-wise trimmed mean as the robust aggregator that   T −1 i E F (θ 0 ) − F ∗ 1 X h f log(1/δ)C 2 d ηL σ 2 σ2 G G t 2 E ∇FG (θ ) 2 ≲ + ηLT 1 + + + ηL 2 2 T t=0 ηT n ϵ n T |G| |G|   1 + ηLκ 1 + σ 2 + κG2 . (26) |G| 57

When ( η = min

1 , 132L

v ) u 30(E [FG (θ 0 )] − FG∗ ) 1 u   √ t , 2 f 2 2 800Lk22 log(1/δ)C 2 d T T + 2Lk1 (k1 + k2 ) σ + 4k12 L σ + 94500k1 Lκσ 2 1 + 4(2+ν) 2 2 2 ϵ n

ν

|G|

n

|G|

it holds that T −1

i 1 X h σ 2 E ∇FG (θ t ) 2 ≲ √ T t=0 T s +

s L(E [FG (θ 0 )] − FG∗ ) L(E [FG (θ 0 )] − FG∗ )



    L(E FG (θ 0 ) − FG∗ ) 1 1 +κ 1+ + |G| |G| T

log(1/δ)C 2 d ϵ2 n2

  f 1+ + κG2 . n

2 We put σdp for coordinate-wise trimmed mean into the formula

8T log(1/δ)∆2Byz 32(1 − β)2 T log(1/δ)C 2 = 2 ϵ ϵ2 n 2   32k22 η 2 L2 T log(1/δ)C 2 4(2 + ν)2 f ≤ . 1 + ϵ2 n 2 ν2 n

2 σdp =

 1+

4(2 + ν)2 f ν2 n



Plugging this in, we have   T −1 i 30(E F (θ 0 ) − F ∗ ) 1 X h 800k22 log(1/δ)C 2 d 4(2 + ν)2 f σ2 2 G G E ∇FG (θ t ) 2 ≤ + ηLT 1 + + 2ηLk1 (k1 + k2 ) 2 2 2 T t=0 ηT ϵ n ν n |G| + 4k12 ηL

σ2 + 94500k1 ηLκσ 2 + 23625κG2 . |G|

When we have the optimal learning rate, i.e.,   30(E FG (θ 0 ) − FG∗ ) ηT   800k22 log(1/δ)C 2 d 4(2 + ν)2 f σ2 σ2 2 = ηLT 1 + + 2ηLk (k + k ) + 4k ηL + 94500k1 ηLκσ 2 , 1 1 2 1 ϵ2 n 2 ν2 n |G| |G| we have v u 30(E [FG (θ 0 )] − FG∗ ) 1 u   η=√ t . 2 2 2 2 2 800Lk2 log(1/δ)C d f T 1 + 4(2+ν) T + 2Lk1 (k1 + k2 ) σ + 4k12 L σ + 94500k1 Lκσ 2 2 2 2 ϵ n

ν

|G|

n

|G|

Together with the previous condition, we use   v   u  1  ∗ 0 30(E [FG (θ )] − FG ) 1 u   η = min ,√ t . 2 f 2 2 800Lk22 log(1/δ)C 2 d  T  132L  1 + 4(2+ν) T + 2Lk1 (k1 + k2 ) σ + 4k12 L σ + 94500k1 Lκσ 2  2 2 2 ϵ n

ν

n

|G|

|G|

It follows that v    u 800Lk2 log(1/δ)C 2 d  4(2+ν)2 f  σ2 2 L σ 2 + 94500k Lκσ 2  2 u   1 + T + 2Lk (k + k ) + 4k √ 2 2 2 1 1 2 1 1 |G| ϵ n ν n |G| 1 t = max 132L, T ∗   η 30(E [FG (θ 0 )] − FG )   v  u 800Lk2 log(1/δ)C 2 d  4(2+ν)2 f σ2 2 σ2 2 2 1 + √ u 2 2 2 ϵ n ν n T + 2Lk1 (k1 + k2 ) |G| + 4k1 L |G| + 94500k1 Lκσ t . ≤ 132L + T 30(E [FG (θ 0 )] − FG∗ ) 58

Therefore, we have   T −1 i 3960L(E FG (θ 0 ) − FG∗ ) 1 X h 2 E ∇FG (θ t ) 2 ≤ T t=0 T s s   30(E [FG (θ 0 )] − FG∗ ) 800Lk22 log(1/δ)C 2 d σ2 4(2 + ν)2 f σ2 +2 1 + T + 2Lk1 (k1 + k2 ) + 4k12 L + 94500k1 Lκσ 2 T ϵ2 n2 ν2 n |G| |G| + 23625κG2 .

By

√

x+y ≤

√

x+

√

y, it holds that

  T −1 i 3960L(E FG (θ 0 ) − FG∗ ) 1 X h 2 E ∇FG (θ t ) 2 ≤ T t=0 T s s   30(E [FG (θ 0 )] − FG∗ ) 800Lk22 log(1/δ)C 2 d 4(2 + ν)2 f σ2 σ2 +2 1 + T + 2Lk1 (k1 + k2 ) + 4k12 L + 94500k1 Lκσ 2 T ϵ2 m2 ν2 n |G| |G| + 23625κG2   3960L(E FG (θ 0 ) − FG∗ ) ≤ T s s   30(E [FG (θ 0 )] − FG∗ ) 800Lk22 log(1/δ)C 2 d 4(2 + ν)2 f +2 1+ T 2 2 2 T ϵ n ν n s s 30(E [FG (θ 0 )] − FG∗ ) σ2 σ2 +2 + 4k12 L + 94500k1 Lκσ 2 + 23625κG2 2Lk1 (k1 + k2 ) T |G| |G| s     3960L(E FG (θ 0 ) − FG∗ ) 2σ σ2 σ2 = √ 60(E [FG (θ 0 )] − FG∗ ) Lk1 (k1 + k2 ) + 2k12 L + 47250k1 Lκ + |G| |G| T T s   log(1/δ)C 2 d 4(2 + ν)2 f + 2 24000Lk22 (E [FG (θ 0 )] − FG∗ ) 1+ + 23625κG2 . 2 2 ϵ n ν2 n

G.4

Supporting Results for the Optimality of CWTM

In this section, we present the remaining supporting results that establish the optimality of our results. G.5

Conditions of matching optimality

Lemma 1. From its proof, we have ∇Fi (θ) = µθ − where

m µG0 X xji √ , L d j=1 m

Pm

j d j=1 xi /m ∈ {±1} for j ∈ [m] and i ∈ [n]. It follows that

C = ∥∇Fi (0)∥2 =

m µG0 X xji µG0 √ µG0 √ ∥ ∥2 = √ d = = Θ(G), L L d j=1 m L d

where the last equality holds because µ = Θ(L) and G0 = G/2. Lemmas 2 and 3. Let τ = f /(n − f ) and 1 ∈ Rd be an all-one vector. From the proofs, we have  G0 1  µ(θ − L√τ d ), if i ∈ [1, f ]; ∇Fi (θ) = µ(θ + LG√0τ1d ), if i ∈ [f + 1, 2f ];   µθ, otherwise. It follows that

 µG 1 0  − L√τ d , µG 0 ∇Fi (0) = + L√τ1d ,   0, 59

if i ∈ [1, f ]; if i ∈ [f + 1, 2f ]; otherwise.

We have

µG0 µG0 1 G C = max{∥∇Fi (0)∥2 } = ∥ √ ∥2 = √ = Θ( √ ), L τ τ i∈[n] L τd √ where the last equality holds because µ = Θ(L) and G0 = G/ 2. In the regime of f = Θ(n), it holds that C = Θ(G). G.6

Optimality of CWTM

The proofs and intermediate results below show that coordinate-wise trimmed mean (CWTM) is orderoptimal in terms of Byzantine-robustness for completeness. The proofs follow the standard roadmap from [4]. Lemma G.14. Assume that R : Rd×n → Rd is a coordinate-wise aggregation function, i.e., there exist d real-valued functions R1 , . . . , Rd such that ∀x1 , . . . , xn ∈ Rd , [R(x1 , . . . , xn )]r = Rr ([x1 ]r , . . . , [xn ]r ). If, for each r ∈ [d], Rr is (f, κ)-robust then R is (f, κ)-robust. Proof of Lemma G.14. Consider n arbitrary vectors in Rd x1 , . . . , xn , and an arbitrary set S ⊆ [n] such that |S| = n − f . Assume that, for each r ∈ [d], Rr is (f, κ)-robust. Since R is assumed to be a coordinate-wise aggregation function, we have 2

∥R(x1 , . . . , xn ) − x̄S ∥2 =

d X

|Rr ([x1 ]r , . . . , [xn ]r ) − [x̄S ]r |

2

r=1 (a)

≤

d

κ X κ XX 2 2 |[xi ]r − [x̄S ]r | = ∥xi − x̄S ∥2 , |S| r=1 |S| i∈S

i∈S

where inequality (a) follows from Definition 2. Lemma G.15. Consider n real values x1 , . . . , xn such that x1 ≤ . . . ≤ xn . Let S ⊆ [n] of size |S| = n − f , and I ≜ {f + 1, . . . , n − f }. It holds that X X 2 2 |xi − x̄S | ≤ |xi − x̄S | . i∈I\S

i∈S\I

Proof of Lemma G.15. Observer that |I| = n − 2f , |S| = n − f , |I \ S| ≤ f , and |S \ I| ≥ f . Therefore, |I \ S| ≤ |S \ I|. It suffices to show that there exists an injection ϕ : I \ S → S \ I such that |xi − x̄S | ≤ xϕ(i) − x̄S , ∀i ∈ I \ S. P P Since |I \ S| ≤ |S \ I|, we have i∈I\S |xϕ(i) − x̄S |2 ≤ i∈S\I |xϕ(i) − x̄S |2 . For east of notation, we denote S ∁ ≜ [n] \ S. It follows that |S ∁ | = f and I \ S = I ∩ S ∁ . Let I + ≜ {n − f + 1, . . . , n} and I − ≜ {1, . . . , f } define the indices of values that are greater (or equal to) and smaller (or equal to) the values in I, respectively. Further let |I ∩ S ∁ | = q. Since S ∁ = [n] \ S, it holds that |I + ∩ S| = f − |I + ∩ S ∁ | ≥ f − |S ∁ \ (I ∩ S ∁ )| = f − (f − q) = q.

(27)

Similarly, we have |I − ∩ S| ≥ q.

(28)

Recall that q = |I ∩ S ∁ | where I \ S = I ∩ S ∁ . Therefore, (27) and (28) show that there exists an injection from I \ S to (I − ∩ S) × (I + ∩ S). Let ψ denote this injection. For each i ∈ I \ S, ψ(i) is a pair, denoted by (ψ − (i), ψ + (i)), in (I − ∩ S) × (I + ∩ S). Consider an arbitrary i ∈ I \ S. By the definitions of I − and I + , we have xψ− (i) ≤ xi ≤ xψ+ (i) . It follows, for any real value y, that |xi − y| ≤ max



xψ+ (i) − y , xψ− (i) − y

.

The injection is thus defined as ϕ(i) = arg maxj∈{ψ+ (i),ψ− (i)} |xj − x̄S | for all i ∈ I \ S. 60

Proposition 5. Suppose that n ∈ N+ and f < n/2. CWTM is (f, κ)-robust with   6f f κ= 1+ . n − 2f n − 2f Proof of Proposition 5. Due to Lemma G.14, it suffices to show CWTM is (f, κ)-robust in the scalar domain. Without loss of generality, let x1 , . . . , xn ∈ R such that x1 ≤ . . . xn . We denote by I ≜ {f + 1, . . . , n − fP }, and let S be an arbitrary subset of [n] of size n − f . Recall Definition 3, it holds that 1 TM = n−2f i∈I xi . It follows that 1 X |CWTM(x1 , . . . , xn ) − x̄S | = xi − x̄S n − 2f

2

2

i∈I

(a)

=

1 X = (xi − x̄S ) n − 2f i∈I

1 X 1 X (xi − x̄S ) − (xi − x̄S ) n − 2f n − 2f i∈I

2

2

i∈S

2

X X 1 1 (xi − x̄S ) − (xi − x̄S ) , = n − 2f n − 2f i∈I\S i∈S\I P where equality (a) follows from the fact that i∈S (xi − x̄S ) = 0. It follows that   X X |I \ S| + |S \ I| 2 2 2  |CWTM(x1 , . . . , xn ) − x̄S | ≤ |xi − x̄S | + |xi − x̄S |  . (n − 2f )2 i∈I\S

i∈S\I

Note that |I \ S| = |I ∪ S| − |S| ≤ n − (n − f ) = f . Similarly, we have |S \ I| = |I ∪ S| − |I| ≤ n − (n − 2f ) = 2f , Therefore, it follows that |I \ S| + |S \ I| ≤ 3f , which yields   X X 3f 2 2 2  |xi − x̄S | + |xi − x̄S |  |CWTM(x1 , . . . , xn ) − x̄S | ≤ (n − 2f )2 i∈I\S

(b)

≤

i∈S\I

X X 6f 6f 2 2 |xi − x̄S | ≤ |xi − x̄S | , 2 2 (n − 2f ) (n − 2f ) i∈S\I

i∈S

where inequality (b) follows from Lemma G.15 Since  2 ! f (n − f ) 1 f f 1 f = = + (n − 2f )2 (n − 2f )2 n − f n − 2f n − 2f n−f  2 !   f f f f ≤ + = 1+ . n − 2f n − 2f n − 2f n − 2f

Claim 2. When n ≥ (2 + ν)f , where ν > 0, it holds that   f f (ν + 2)(ν + 1) f f ≤ 1+ ≤ . n n − 2f n − 2f ν2 n Equivalently, we have   f f f 1+ = Θ( ). n − 2f n − 2f n Proof of Claim 2. n ≥ (2 + ν)f , where ν > 0, implies that n − 2f ≥ νf , which leads to f 1 ≤ . n − 2f ν It also implies that 2n νn n − 2f ≥ n − = . ν+2 ν+2 61

Upper bound. f n − 2f

 1+

f n − 2f

 ≤

f ν+1 ν+2ν+1f (ν + 2)(ν + 1) f · ≤ = n − 2f ν ν ν n ν2 n

Lower bound. f n − 2f

 1+

f n − 2f



f 1+ n − 2f



≥

f f ≥ . n − 2f n

≤

(ν + 2)(ν + 1) f . ν2 n

Putting them together. f f ≤ n n − 2f



Corollary 4. Suppose that n ∈ N+ and n ≥ (2 + ν)f , where ν > 0, CWTM is (f, κ)-robust with   f κ=Θ . n Corollary 4 can be shown by combining Proposition 5 and Claim 2.

62

Table 5: Neural network architecture, loss function, training steps, and batch size specifications Dataset MNIST / Fashion-MNIST Neural network CNN C(1,16,8,2,3) – T – M(2,1) – C(16,32,4,2) – T – M(2,1) – Model architecture∗ L(512,32) – T – L(10) Loss function

Cross-entropy loss

Number of global rounds T

800

Batch size

20

∗

C (# in-channel, # out-channel, kernel, stride, padding): a 2D convolution layer ; T: tanh activation function; M (kernel, stride): a 2D max-pool layer; L (# outputs) or L (# inputs, # outputs): a fully-connected linear layer; D: a dropout layer (probability 0.2).

Table 6: Test accuracy comparisons of different robust aggregators with and without server-side momentum on the MNIST and Fashion-MNIST datasets. Experiments run for a total of 800 rounds. Each client holds 2 classes of images out of a total of 10 classes. β = 0 indicates that server-side momentum is turned off, and β > 0 indicates that server-side momentum is turned on. All the results are obtained based on an average over the last 50 rounds across 4 different random seeds. Datasets

Attack ALIE BitFlip

MNIST Mimic IPM ALIE Fashion MNIST

BitFlip Mimic IPM

Settings

CWTM

CClip

GM

CWMED

β=0 β>0 β=0 β>0 β=0 β>0 β=0 β>0

80.7 ± 2.6% 83.3 ± 5.4% (↑2.6%) 67.5 ± 2.3% 87.1 ± 3.7% (↑19.6%) 70.1 ± 3.2% 85.9 ± 3.6% (↑15.8) 73.6 ± 4.3% 89.2 ± 4.1% (↑15.6%)

89.8 ± 1.0% 88.4 ± 3.1% (↓ − 1.4%) 80.7 ± 2.0% 89.4 ± 4.1% (↑8.7%) 87.5 ± 1.1% 90.0 ± 4.0% (↑2.5) 88.4 ± 1.0% 90.2 ± 3.3% (↑1.8%)

67.1 ± 1.0% 86.0 ± 4.8% (↑18.9%) 77.4 ± 1.7% 89.0 ± 1.7% (↑11.6%) 40.5 ± 6.3% 79.2 ± 4.2% (↑38.7) 86.2 ± 2.0% 90.0 ± 1.2% (↑3.8%)

38.9 ± 8.0% 21.6 ± 9.4% (↓ − 17.3%) 68.9 ± 3.9% 84.8 ± 1.9% (↑15.9%) 19.3 ± 1.0% 59.6 ± 6.8% (↑40.3) 68.9 ± 3.7% 87.1 ± 1.2% (↑18.2%)

β=0 β>0 β=0 β>0 β=0 β>0 β=0 β>0

68.6 ± 2.0% 71.1 ± 3.7% (↑2.5%) 63.5 ± 4.6% 73.9 ± 4.8% (↑10.4%) 60.5 ± 4.0% 70.8 ± 6.9% (↑10.3%) 60.9 ± 5.0% 74.8 ± 4.5% (↑13.9%)

71.7 ± 1.0% 69.6 ± 2.6% (↓ − 2.1%) 65.8 ± 3.4% 73.5 ± 3.0% (↑7.7%) 70.3 ± 2.2% 75.4 ± 2.2% (↑5.1%) 66.8 ± 2.0% 75.2 ± 3.1% (↑8.4%)

62.8 ± 2.5% 64.6 ± 3.4% (↑1.8%) 64.0 ± 4.1% 72.7 ± 4.8% (↑8.7%) 37.9 ± 2.6% 66.3 ± 4.3% (↑28.4%) 65.1 ± 2.0% 68.2 ± 3.9% (↑3.1%)

48.0 ± 3.6% 44.1 ± 9.4% (↓ − 3.9%) 59.2 ± 5.2% 69.4 ± 4.0% (↑10.2%) 37.5 ± 1.0% 55.3 ± 4.9% (↑17.8%) 57.2 ± 4.6% 72.5 ± 2.6% (↑15.3%)

H

Experiment Details

H.1

Experimental setups

Hardware and Software Setups. • Hardware. The simulations are performed on a private cluster of multiple nodes, each node is equipped with 8 CPUs, 64 GB of RAM, and 1 NVIDIA A5000 GPU. • Software. We code our experiments based on PyTorch 2.8.0 and Python 3.9.1. Neural Network and Hyper-parameter Specifications. Table 5 specifies details of the structures of the convolutional neural network and training. The local learning rate η is searched based on the best performance after 100 global rounds, over two grids {0.75, 0.5, 0.1, 0.03, 0.01, 0.003, 0.001, 0.0003}. The client-side momentum coefficient α = 0.1, and the server-side momentum coefficient β = 0.85. The DP δ is set to be 10−4 throughout. Datasets and Data Heterogeneity. The MNIST dataset [44] contains 10 classes of images. In total, there are 50,000 train images and 10,000 test images. The Fashion-MNIST dataset [68] contains 10 classes of images. In total, there are 60,000 train images and 10,000 test images. Each client holds two classes of images. H.2

Byzantine Attack Details

We consider four state-of-the-art gradient attacks, including A Little is Enough (ALIE) [13], Bitflipping (BitFlip) [3], Inner product manipulation (IPM) [69], and Mimic [42]. 63

0.4 0.2 30

20 10 Privacy Budget ( ) More Private

1

Trimmed Mean ( = 0)

Test Accuracy

Test Accuracy

Test Accuracy

0.6

Bit Flip

0.8 0.6 0.4 0.2 30

20 10 Privacy Budget ( ) More Private

CClip ( > 0)

Mimic

0.8 0.6 0.4 0.2

1

CClip ( = 0)

Inner Product Manipulation

Test Accuracy

Trimmed Mean (Ours) ( > 0)

A Little is Enough

30

20 10 Privacy Budget ( ) More Private

0.75 0.50 0.25

1

30

20 10 Privacy Budget ( ) More Private

1

(a) Test accuracy results on the MNIST dataset. Bit Flip

0.2 30

20 10 Privacy Budget ( ) More Private

1

0.4 0.2 30

20 10 Privacy Budget ( ) More Private

1

Inner Product Manipulation

0.6

Test Accuracy

0.4

Mimic

0.6

Test Accuracy

0.6

Test Accuracy

Test Accuracy

A Little is Enough

0.4 0.2 30

20 10 Privacy Budget ( ) More Private

1

0.6 0.4 0.2 30

20 10 Privacy Budget ( ) More Private

1

(b) Test accuracy results on the Fashion-MNIST dataset.

Figure 3: Test accuracy results and comparisons on real-world datasets when the server-side momentum is turned on (β > 0) and when it is turned off (β = 0). The results are averaged over the last 50 rounds across 4 different random seeds. All the experiments run for a total of 800 rounds. The radius of the shaded circle denotes the standard deviation at a given privacy budget ϵ.

Let at be the attack vector in round t and γ ≥ 0 a fixed The Byzantine clients send the PS a P constant. 1 t Byzantine vector Bt = ūt + γat , where ūt = |G| M . We have the following attacks: i i∈G (1)

(d)

(r)

• ALIE. at = −σt , where σt ≜ [σt , . . . , σt ] and σt is the coordinate-wise standard deviation of the honest updates at coordinate r. All Byzantine clients send Bt = ūt − γ σt , with γ = zmax computed in closed form from (n, m) via the normal CDF [13]. • BitFlip. at = −ūt and γ = 2. All Byzantine clients send Bt = −ūt in round t. • Inner Product Manipulation. at = −ūt . All Byzantine clients send Bt = (1 − γ)ūt in round t. The optimal γ for IPM is determined by greedily searching over a defined range of values [4]; in each round we choose γ to maximize the ℓ2 distance between the robust aggregator’s output and the average of the honest clients’ updates. This strategy ensures the maximum degradation caused by the Byzantine clients in terms of ℓ2 distance. A mimic attack is defined as all Byzantine clients mimicking a specific honest client by simply sending their updates to the PS. We follow the heuristic strategy in [41] to determine the set of mocking honest clients. H.3

Additional results

In the absence of user-level DP protections, Table 6 shows the test accuracies for different robust aggregators, including CWTM, CClip, GM, and CWMED, on the MNIST and Fashion-MNIST datasets with server-side momentum enabled and disabled. Detailed definitions of the robust aggregators can be found in Appendix F.5. We can see that the server-side momentum boosts the performance in most cases. Notably, the improvements are significant. For example, GM improves over 25% under Mimic et−1 , attack on the Fashion-MNIST dataset. The improvement stems from the shared anchor βt R which pulls all clients’ updates toward a common direction, thereby strengthening their concentration and improving the robust aggregator’s effectiveness against Byzantine clients. Occasionally, we can see a drop in performance. We attribute this to the construction of CWMED, which yields a suboptimal robust coefficient [4]. CClip is also observed to have a mild accuracy drop. It is interesting to explore how to improve the performance of CWMED and CClip in a provable way in the future. Fig. 3 shows performance comparisons with server-side momentum enabled and disabled across different privacy budgets for CWTM and CClip. Without server-side momentum, both robust aggregators experience a significant performance drop, with extreme cases greater than 30%, e.g., for CClip under bit-flip and mimic attacks on the MNIST dataset. Turning off momentum amplifies DP noise and degrades the signal-to-noise ratio, drowning out the effective signals. Furthermore, our analysis in Section 6.3 shows that disabling the server-side momentum will incur an unbounded error, which is proportional to the number of rounds T , in the convergence upper bound. Consequently, the server-side momentum acts as a critical stabilizer, preventing client-level DP noise from causing catastrophic effects over extended training horizons. 64

Related documents

• Privacy-enhanced federated learning via asynchronous aggregation and local differential perturbation#1109921
• Privacy-enhanced federated learning via asynchronous aggregation and local differential perturbation#919510
• Hear No Evil: Detecting Gradient Leakage by Malicious Servers in Federated Learning#1533871
• Inverting Gradients - How easy is it to break privacy in federated learning?#1527668
• Upholding Robustness in Federated Learning: Trends, Emerging Strategies, and Research Opportunities#1076378