Towards Trustworthy Federated Learning with Untrusted Participants
Authors: Youssef Allouah
Rachid Guerraoui
John Stephan
Venue: ICML 2025 poster (2025)
Keywords: distributed machine learning
differential privacy
robustness
federated learning
trustworthy machine learning
Primary area: social_aspects->privacy

Abstract: Resilience against malicious participants and data privacy are essential for trustworthy federated learning, yet achieving both with good utility typically requires the strong assumption of a trusted central server. This paper shows that a significantly weaker assumption suffices: each pair of participants shares a randomness seed unknown to others.  
In a setting where malicious participants may collude with an untrusted server, we propose CafCor, an algorithm that integrates robust gradient aggregation with correlated noise injection, using shared randomness between participants.
We prove that CafCor achieves strong privacy-utility trade-offs, significantly outperforming local differential privacy (DP) methods, which do not make any trust assumption, while approaching central DP utility, where the server is fully trusted.  
Empirical results on standard benchmarks validate CafCor's practicality, showing that privacy and robustness can coexist in distributed systems without sacrificing utility or trusting the server.

Towards Trustworthy Federated Learning with Untrusted Participants
Youssef Allouah Rachid Guerraoui
John Stephan
Abstract
especially valuable when privacy constraints prohibit data sharing, such in healthcare applications where institutions hold sensitive patient records (Kaissis et al., 2020).
Resilience against malicious participants and data privacy are essential for trustworthy federated learning, yet achieving both with good utility typ- ically requires the strong assumption central server. This paper shows that a signifi- cantly weaker assumption suffices: each pair of participants shares randomness seed unknown others. In a setting where malicious participants may collude with an unirusted server, we propose CAFCOR, an algorithm that integrates robust gra- dient aggregation with correlated noise injection, using shared randomness between participants. We prove that CAFCOR achieves strong privacy- utility trade-offs, significantly outperforming lo- cal differential privacy (DP) methods, which do not make any trust assumption, while approaching central DP utility, where the server is fully trusted. Empirical results on standard benchmarks vali- date CAFCOR's 's practicality, showing that privacy and robustness can coexist in distributed systems without sacrificing utility or trusting the server.
While DSGD inherently reduces data exposure by keeping local datasets private, significant privacy risks remain. the trained model is publicly accessible, it becomes vul- nerable to membership inference (Shokri al., 2016) and model inversion (Fredrikson al., 2015; Hitaj al., 2017; Melis et al., 2019) attacks. Moreover, curious server can analyze gradients and intermediate model states during train- ing to extract sensitive information about individual data points (Phong et al., 2017; Wang et al., 2019; Zhu et al., 2019). Besides, in practical distributed environments, common for some workers to behave unpredictably due to system failures, corrupted data, adversarial interference. These workers, also known Byzantine (Lamport et al., 1982), can arbitrarily manipulate their updates, compromis- ing the integrity of the learning process (Baruch et al., 2019; Xie et al., 2020). In DSGD, even a few malicious workers can significantly degrade model performance by poisoning gradients or models (Feng et al., 2015). This vulnerability underscores the need for robust aggregation techniques to mitigate the influence of malicious workers.
trusted
1. Introduction
Threat models. Differential privacy (DP) (Choudhury et al., 2019; Hu et al., 2020; Noble et al., 2022) and robust- ness (Yin et al., 2018; Karimireddy et al., 2021; Allouah et al., 2023b) have been extensively studied in isolation in distributed machine learning. However, their intersection, which is crucial for building trustworthy learning systems, remains underexplored. Recent work shows that combining local DP (LDP), which assumes trust, with robustness in- curs a fundamental utility cost (Allouah et al., 2023c). This reinforces earlier findings that ensuring privacy under IDP, even without malicious workers, is prohibitive in terms of utility (Duchi et al., 2013). contrast, the central DP (CDP) model, where the server fully trusted, enables significantly better utility than LDP, particularly the number of work- ers increases (Liu et al., 2021; Hopkins et al., 2022). These findings highlight the trade-offs between trust, privacy, and robustness in distributed learning, underscoring the need for alternative approaches that mitigate these limitations.
The increasing complexity of machine learning (ML) mod- els and the vast amounts data required for training have driven the widespread adoption of distributed ML (Dean al., 2012; Kairouz et al., 2021). By distributing the com- putational workload across multiple machines, this approach enables scalable and efficient model training. In the standard server-based architecture, multiple workers collaboratively optimize a shared model under the coordination of a central server. This process is typically implemented using dis- tributed stochastic gradient descent (DSGD) (Bertsekas & Tsitsiklis, 2015), where workers compute gradients on local mini-batches and transmit them the server, which then aggregates the updates to refine the global model. DSGD is
'EPFL, Switzerland. Alphabetical order. Correspondence to: Youssef Allouah arousseefallooua@@pppppp @wwpaahhcppp..c........ John Stephan <john.stephan@@ee @cp?
Proceedings of the 4rnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Towards Trustworthy Federated Learning with Untrusted Participants
1.1. Contributions
louah et al., 2023c). In the CDP model where the server is fully trusted, the privacy-utility trade-off is far superior to the LDP setting (Duchi et al., 2013; 2018). Prior work on centralized robust mean estimation with DP (Liu et al., 2021; Hopkins et al., 2022; Alabi et al., 2023) achieves near- optimal error bounds, disentangling the three-way trade-off by matching the optimal sample complexity in both private and robust settings. Empirical studies confirm this advan- tage in standard federated learning tasks (Xie et al., 2023).
In this work, we analyze an intermediate threat model that extends the privacy guarantees of LDP while achieving util- ity comparable to CDP, which assumes trusted server. This model, referred to as secret-based -ased local differential privacy (SecLDP), was only studied in non-adversarial settings fo- cused on privacy (Allouah et al., 2024) or without utility guarantees in the presence of malicious workers (Sabater et al., 2022). We present the first analysis of SecLDP in adversarial distributed learning, considering an untrusted server and malicious workers, who aim to disrupt the leam- ing as well as to compromise the privacy of honest workers by colluding with the server. Our results establish SecLDP as a viable privacy model for trustworthy distributed learn- ing, bridging the gap between the stringent trust assumptions of LDP and the stronger utility guarantees of CDP.
Intermediate threat models between local and central DP, such as those leveraging cryptographic primitives or anonymization via shuffling (Jayaraman et al., 2018; Er- lingsson et al., 2019; Cheu et al., 2019), can approach the privacy-utility trade-off of central DP but often incur high computational costs, rely on trusted entities, or lack robust- ness. Correlated noise schemes have also been explored for privacy without trusted server; early methods like se- cret sharing (Shamir, 1979) ensure input security but do not privatize the output, leaving it vulnerable to inference at- tacks (Melis et al., 2019). More refined approaches (Imtiaz et al., 2021) combine correlated and uncorrelated Gaussian noise to protect averages, while decentralized extensions remain limited to averaging tasks (Sabater et al., 2022) and lack robustness (Allouah et al., 2024). We also note that (Sabater et al., 2022) consider malicious workers but do not provide utility guarantees in their presence, and only use cryptographic checks, c.g., to verify boundedness of all messages. On the other hand, they consider sparse topolo- gies which induces lower communication costs, unlike our quadratic communication complexity for seed exchange, which we recall is negligible since it happens once before training and only includes integers, compared to the large- scale models exchanged iteratively during training. Re- cently, Gu et al. (2023) considered malicious workers and an untrusted server but relied on computationally intensive tools like knrolenooee proofs and secure aggregation, whereas our method avoids these complexities. Moreover, they do not quantify the utility cost of their solution.
Algorithm. We introduce CAFCOR, a preseeriig and robust distributed learning algorithm under the SecLDP model. CAFCOR employs a correlated noise injection mech- anism inspired by secret sharing (Shamir, 1979), leveraging workers' access to shared randomness. This is efficiently achieved through a one-time pairwise agreement on secret randomness seeds using standard public-key infrastructure, as commonly done in secure distributed systems (Bonawitz et al., 2017). However, the added noise can obscure honest contributions, reducing the effectiveness of existing aggre- gations in filtering out malicious workers. To address this, we design novel robust aggregation method that efficiently mitigates the impact of dimensionality on the mean estima- tion error, relying only on an upper bound on the number of corrupt workers.
Bridging the gap. We provide theoretical guarantees the privacy-utility trade-off of CAFCOR under SecLDP, as- suming an untrusted server and colluding malicious work- ers. Our analysis shows that CAFCOR achieves near-CDI CDP performance under limited corruption, significantly outper- forming LDP-basee methods. When shared randomness is unavailable, CAFCOR seamlessly reverts to the standard LDP model while maintaining tfte-of-theear performance. Extensive experiments on benchmark datasets (MNIST and Rushion-MNIST validate our findings, confirming CAF- COR's s superior performance in adversarial settings.
Cryptographic primitives such as homomorphic encryption and secure multi-party computation have been widely used to enhance privacy in distributed learning (Bonawitz et al., 2017: Zhang et al., 2020), offering efficient implementations. Some works have explored integrating these techniques with robustness (Corrigan-Gibby & Boneh, 2017: Choffrut et al., 2024), but they face limitations. While cryptographic schemes efficiently support basic operations like averaging, they often incur significant computations when coupled with robust aggregation due to the non-linearity of key operations such as median and nearest neighbors. This limits their practicality in robust distributed learning.
1.2. Related Work
Most works combining DP and robustness focus on local privacy models, often only achieving per-step privacy guar- antees and suboptimal learning performance (Guerraoui et al., 2021: Zhu & Ling, 2022: Xiang& & Su, 2022; Ma et al., 2022). Others reveal a three-way trade-off between pri- vacy, robustness, and utility for discrete distribution estima- tion in non-interactive settings (Cheu et al., 2021; Acharya et al., 2021) and more general interactive learning tasks (Al-
2

---

Towards Trustworthy Federated Learning with Untrusted Participants
2. Problem Statement
the formalism of Allouah al. (2024), where two datasets are adjacent if they differ by one worker's local dataset.
We consider the classical server-based architecture com- prising workers and central server. The workers hold local datasets Di...., Dn. each composed of m data points from input space X, i.e., D; E Xm"
Definition 2.2 (SecL.DP). Let 2 0, 8 E [0,1], Consider randomized distributed algorithm As Xmxxx + y. which outputs the transcript of all communications given the full set of secrets S. Algorithm As satisfies (c, 6, Strnoon) SecLDP if it satisfies (c, (e,6)-DP given that the subset of secrets Sknonn C SS is revealed to the curious server. That is, for all adjacent datasets D, D' Xmxn
[n]. For given parameter vector 0 E IRd a data point x X' has real-valued loss function z();z). The empirical loss function for each i E [n] is defined for all 0 E R² as (,) == 1 EeeD, E(0:z). The goal of the server is to minimize the global empirical loss function defined for all 0 Rd as [(0)= 1 -ー (0). We assume that each loss C; is differentiable, and that C is lower bounded.
IP (As(D) Strowal e P[AAsDD) SShowel + 8.
We simply say that As satisfies (c, -..8LLD when Strown is clear from the context.
2.1. Robustness
The above definition captures multiple levels of trust, always considering the server to be honest-but-curious. First, the least stringent setting when no worker colludes with the server, meaning that no secrets (Senown Ø). Second, the most adversarial scenario arises when all workers collude with the server (Sknown S), which corresponds to the standard LDP threat model. Fi- nally, we consider an intermediate scenario where only ma- licious workers may collude with the server to compromise the privacy of honest workers by disclosing the secrets they share with them (Sknow {Sig E [n] H. [m]))) However, even under this model, the server remains unaware of the malicious identities. A malicious worker may collude by revealing its secrets but has no incentive to disclose its adversarial nature, as it also aims to disrupt the learning.
We consider setting where most f out of n workers may be malicious. Such workers may send arbitrary messages to the server, and need not follow the prescribed protocol. The identity of malicious workers is priori unknown to the server. Let H C {1, ni. with |7| = n - f. We define for all 0 E R (0) = [H4] Eien (.))). If H represents the indices of honest workers, LH is referred to as the global honest loss. An algorithm is robust if it enables the server to approximately minimize the global honest loss, as follows.
disclosed to the server
Definition 2.1 (S: Robustttts,,.. A distributed algo- rithm A is (f, r)-buuttt if it outputs Ô such that E [cx(0) - L.] S e, where L. == infoeRs (0((),, and the expectation is over the randomness of the algorithm.
In other words, Algorithm A is (J, e)-rubust if it outputs in every execution a g-approximate minimizer of the global honest loss function Lu, despite ff malicious workers.
2.3. Assumptions
Our results are derived under standard assumptions. Data heterogeneity is modeled via Assumption 2.1 (Allouah et al., 2023c), which subsumes standard assumptions federated learning (Karimireddy et al., 2020) by bounding gradient variance in all directions. To establish the convergence guar- antees of CAFCOR, we adopt the standard Assumption 2.2 on the variance of stochastic gradients. Assumption 2.3 ensures bounded gradients at any data point, a common requirement in differentially private optimization to avoid complications due to clipping (Agarwal et al., 2018).
2.2. Differential Privacy
Each honest worker i E H. aims to protect the privacy of their dataset D; against the honest-but-curious (or un- trusted) server. That is, the server follows the prescribed protocol, but may attempt to violate the workers' data pri- vacy. Also, we assume that every pair of workers i,j [n] shares sequence of secrets Sij. which represent observa- tions of random variables only known to the workers i, In practice, these are generated locally via shared randomness seeds exchanged after one round of encrypted communi- cations (Bonawitz et al., 2017), and conceptually one can consider the secrets to be the shared randomness seeds only. We denote by S {S.y : j e [n]] the set of all secrets.
Assumption 2.1 (Bounded heterogeneity). There exists G such that V0 E IRd,
Σ (u VL,(0) (LH(0)) S G.ov.
17
S
Assumption 2.2 (Bounded variance). There exists 0 such for each honest worker w,, E H, and all 0 Rd.
We recall that local DP (LDP) (Kasiviswanathan et al., 2011) protects against an untrusted server without assuming the existence of secrets, at the price of a poor privacy-utility trade-off (Duchi et al., 2013). Instead, to achieve a better trade-off, we consider the following relaxation of LDP into recret-based local differential privacy (SecL.DP), adapting
Σ -V(0)))-V.(00)) s0²
ZED.
Assumption 2.3 (Bounded gradients). There exists C > 0 such that VO E Rd, E H, and x E D,, [[V[(0;))) S SC.
3

---

Towards Trustworthy Federated Learning with Untrusted Participants
Algorithm 1 CAFCOR
Algorithm 2 CAF: Covariance bound- Agnostic Filter
Input: Initial model 0o: DP noise levels Gind: Teori batch
Input: vectors I1,..... In
E Rdd bound on number of
size b: clipping threshold C; learning rates {7a]; momentum coefficients { number of iterations T.
corrupt imputs 0 - f < 2.
1: Initialize C1..... Cn = 11
1 n2
Ei= 22, = co.
1: for ( = O... do
2: while Σi= G > - 2 do
2: Server broadcasts 0, to all workers.
3: Compute Pc -i= G.s// Ei= C..
3: for every honest worker i E H in parallel do
4: Compute empirical covariance E. = Ei=1 C3(23
4: Sample mini batch 5 of size b at random from
Be)(2; ( Ao) /i> C.
D; without replacement.
5: Compute maximum eigenvalue 02 of Ex and an as- sociated eigenvector fo.
5: Average the mini- batch gradients and clip: (a)
Clip(} & ExEs(a Ve(O;;ar); C¹) (see (1)).
if & S a. then
6: Inject DP noises to the gradient: g = 9i +
Update best guess: fha t- Pes 0+ t- ō 8: end if
(() + EZje(my 2t (15) where T!!) ~ ~N(0, and
9: Compute T; = (0e; - Mo) Vi E [m].
and 114 of66) = -1,00) ~ ~2 Ta)-
10: Update weight e₁ +- -cc(1 maxze(n) T5 ). Vi E [n]]
7: Send m. = Bt-1m (6)
(6) 1-1 + Be-1) if 2 1,
11: end while
else mg =
(i)
12:
return μ4,
8:
end for
Server aggregates: R₂ CAF(m, (1)
m, )
9:
where the CAF aggregation is given by Algorithm 2.
the correlated noise terms are pairwise-canceling, workers with smaller indices add the generated noise, while their paired counterparts subtract it.
10: Server updates the model: 0.+1 = O2 7 Re.
11: end for
12:
return uniformly sampled from
Next, each honest worker E HH updates their local momen- tum for t 2 1:
ml (9) B.-mm(") + (1 -3,-1 with m (4) 0 and 3 E 1] is the momentum coefficient, and then sends it to the server. If worker i is malicious, i.e., not honest, then they may send an arbitrary value for their momentum m. tums using the CAF aggregation, detailed in Algorithm 2, to obtain R² CAF(m) (1) m, (n)). It then updates the y Rt, where Y 2 0 is the learning rate.
3. Algorithm: CAFCOR
We now introduce CAFCOR, summarized in Algorithm 1. CAFCOR extends distributed stochastic gradient descent (DSGD) by incorporating a correlated noise scheme and momentum- based updates at the worker level, and a novel robust aggregation scheme, called CAF, at the server level.
(6) The server aggregates the momen-
model: p.+1 02 - After T iterations, the server outputs 0 sampled uniformly from Po.....,r-11.
The server sets an initial model 0o and broadcasts O, to workers at each iteration 2 0. Each honest worker i H then randomly samples mini-batch st of size b S from their local dataset D, without replacement. Worker i E H then computes per-example gradients Ve(O;; x) for ((1)
Covariance-bound Agnostic Filter (CAF).' The CAF aggregation, outlined in Algorithm 2, aggregates d- dimensional vectors F1,..., Fn E IRd given only an up- per bound 0 S f < 3 on the number of corrupt in- puts. CAF operates without requiring any additional as- sumptions on the distribution of honest inputs. The algo- rithm iteratively decreases the weights e; E [o, 1] of in- put vectors, each initially assigned a unit weight, until the total sum of weights falls below n - 2 Weight reduc- tions are determined based on each vector's contribution to variance along the worst-case direction. Specifically, let c.. Σi= G.2// Σ C2 denote the current weighted mean and let Ex = Ex- ci (t) - / Σ G denote the corresponding empirical covariance matrix. The largest eigenvalue of Σ., is denoted o?. with associated eigenvector U. E Rd. Each vector's weight is reduced in
E S( averages them, and then applies gradient clipping to bound the sensitivity, ensuring the gradient norm does not exceed C: gt = Clip(t Eees(" Ve(O;; x); where
Clip(g; = g min (1,C/ (99l))
(1)
Each honest worker E H perturbs He (4) with noise to obtain of 9t
(t) Eyemiy o(()) t(() where 7(6)
(O of Ta) is an independent Gaussian noise term and (o)5)) JomnI are painwise-cancelngg correlated Gaussian noise terms, i.e., 1. (())) -0,50)
((0) (O Ta) These noise terms are generated through a one-time pairwise agree- ment protocol executed before CAFCOR. This is efficiently achieved using a kub infrastructure, where workers establish shared randomness seeds in a single encrypted communication round (Bonawitz et al., 2017). To ensure
Naaeed for being agnostic to any bound the honest input covariance, as discussed in Section 4.2.

---

Towards Trustworthy Federated Learning with Untrusted Participants
proportion its influence on variance along the worst di- rection, quantified by T, (ic, 32- - CAF tracks the weighted average corresponding to the covariance matrix with the smallest top eigenvalue encountered across all iter- ations. Once the sum of weights falls below n - 2f. CAF outputs this tracked weighted average as its final result.
tice. This exact computation was not feasible in previous related works, as they either considered different communi- cation topologies (Sabater et al., 2022; Allouah et al., 2024). The major difference with the aforemennioned analyses is granularity: we consider 0$qS. workers who may poison training but are not curious, while prior works considered one extreme or the other, i.e., q E {0, f}. This granularity induces improved empirical performance (Figure 1).
4. Theoretical Analysis
We now present the theoretical guarantees of CAFCOR in terms of privacy and utility, as well as their trade-off.
4.2. Utility Analysis
We first study the robustness of the CAF aggregation (Al- gorithm 2) in Proposition 4.1, and then analyze the conver- gence of CAFCOR (Algorithm 1) in Theorem 4.2. The proof
4.1. Privacy Analysis
Theorem 4.1 establishes the privacy guarantee of CAFCOR after T iterations, with the proof deferred to Appendix A. As discussed in Section 4.2, the noise magnitudes of and oeor are key factors in the privacy-utility trade-off. Our objective is to minimize these terms while ensuring privacy.
is deferred to Appendix B.
Proposition 4.1. Let 0 S
and K. =
2
(1+ be any subset of size n f. Let āe = [ST Eies 24. and Amax denote the maximum eigenvalue operator. The output
6f
Let Iı, In E Rd, and S S
[n]
Theorem 4.1. Let 5 E (0, 1). E (oloo(//))) S < 2. Algorithm 1 satisfies (e, d)-SeLLDP against an honest- but-curious server colluding with q malicious workers, if
R
a CAF((11....... F.,) satisfies:
| Ts|l S K Amax
Ez) -os)
(n- 4)0 cor +o ind
(og2/0)
S
52
1 + (ox cor ta
Proposition 4. 1 establishes an important property satisfied by CAF. The above corresponds to the high-dimensional ro- bustness criterion studied by Allouah al. (2023c), shown to be stronger than existing ones in the distributed learning literature, e.g., that of Karimireddy et al. (2022). Further- more, we recall from Allouah et al. (2023c) that standard robust aggregations, such as the trimmed mean and me- dian (Yin et al., 2018), can only achieve a weaker variant of Proposition 4.1, where the right-hand side of the inequality involves the trace instead of the maximum eigenvalue opera- tor. Since the trace of d x d matrix can be up d times its largest eigenvalue, standard robust aggregations only satisfy Proposition 4.1 with an additional multiplicative factor of d in K. (4. 1), leading to a looser robustness bound.
Theorem 4.1 guarantees SecLDP for any number of collud- ing malicious workers q S f < 2. if the noise scales as olu deor O (m=))) ), ignoring dependencies on other parameters. Notably, if at least one malicious worker j does not collude with the server (i.e., j retains its shared secrets and 9 < f), the independent noise term can be entirely removed (nd = 0), while maintaining o2 = 0 n ) to satisfy SecLDP. The key insight is that each honest worker shares correlated noise with all other workers, including non-colluding malicious worker j. As result, the server cannot cancel the correlated noise associated with worker j's hidden secrets. This effectively serves as an independent noise source for honest workers, eliminating the need for an explicit and in the correlated noise scheme. Finally, if the shared randomness assumption among workers is unavail- able, CAFCOR naturally falls back to the LDP setting by setting o ooor = 0 in Algorithm 1. Conceptually, this corre- sponds to a scenario where all secrets are revealed, allowing the server to eliminate correlated noise and leaving only in- dependent noise for privacy. Consequently, ofd must scale as @ + which n times larger than under SecL.P.
Moreover, the so-called SMEA aggregation of Allouah et al. (2023c) also satisfies Proposition 4.1 up to constants. How- ever, SMEA is computationally impractical as its time com- plexity grows exponentially with f. In contrast, CAF is effi- cient, running in polynomial time Of (ndd + dd)). Indeed, at each itcration, at least one input (i E argmax,{{(1) Ty) is assigned a weight of zero. Thus, CAF terminates within at most 2 iterations, each requiring the computation of the top eigenvector and the formation of the empirical covariance matrix. To further improve efficiency, we implement a CAF variant with reduced complexity D(fndlog d) by approxi- mating the top eigenvector using the power method. This approach avoids explicit covariance matrix formation and instead relies on matrix-vector products. We adopt this more efficient variant in our experiments in Section 5, as it can be easily shown to satisfy Proposition 4.1 up to constants.
The proof of Theorem 4.1, deferred to Appendix A, re- lies upon computing the Rényi divergence induced by the correlated noise scheme, before converting back to DP fol- lowing standard conversion results (Mironov, 2017). In- deed, we derive the exact expression of the aforementioned Rényi divergence in Lemma A.4, which we use directly in our Rényi- privacy accountant for SPcL.DP prac-
5

---

Towards Trustworthy Federated Learning with Untrusted Participants
CAF builds on recent algorithmic advances in robust statis- ties (Diakonikolas al., 2017). A major difference is that CAF does not require a bound on the covariance of honest inputs. In contrast, prior robust mean estimators have relied on such bounds as a crucial design requirement (Diakoniko- las et al., 2017: Steinhardt et al., 2018). CAF operates instead under a more practical assumption, requiring only a bound on the number of corrupt inputs f. a standard as- sumption in robust ML (Yin et al., 2018; Karimireddy et al., 2021; Farhadkhani et al., 2022). By eliminating covariance constraints, CAF is more suited to our setting, where infor- mation about honest inputs such as gradients or momentums may not be available or could compromise privacy.
4.3. Privacy-Utility Trade-off
Corollary 4.1 below, which quantifies the privacy-utility trade-off of CAFCOR, follows directly from combining the results of Theorems 4.1 and 4.2.
Corollary 4.1. Let å E (0, E (0, log((/8)) and n. P (2 + f)..fffff for some absolute constant rj > O. Consider Algorithm I in the strongly convex setting of Theorem 4.2. Tog (1/8), then Algorithm I is 8)- e((x-))
If o o ind
SecLDP against an nonest-but-curious server colluding with all malicious workers, and (J, 2)-obust where e
O (E+t))2d)oo((1/)) + 5C (o2(1/1//)) + n L.aaa)) asymptoti-
n2z²
cally in T and ignoring absolute constants.
Next, Theorem 4.2 establishes the convergence rate of CAF- COR, with the proof deferred to Appendix C.
To analyze the privacy-utility trade-off, we examine the first term of o from Corollary 4.1. This term dominates the second whenever d 2 n, a condition that is typically met in practice, given that modern deep learning models have dimensions in the order of millions (He et al., 2016), while the number of clients in federated learning, particularly in cross-silo settings, is often much smaller (Kairouz et al., 2021). The final term in the error stems solely from data het- erogeneity and becomes negligible when data is not highly heterogeneous. Overall, CAFCOR achieves a privacy-utilit, trade-off of Ō n²r²
Theorem 4.2. Suppose that Assumptions 2.1, 2.2, and 2.3 hold, and that Lit is L-smooth. Recall is from (4.1). Let
0²= o + dl, d(Jocor + omd)
n f
d o + 108 (nocor + omd) (1+ + n ) + 4x
where of 2(1 - ) We also denote C. infoeRs (0), Lo = (00) - L.. Consider Algorithm with T 2 1, the learning rates 7/2 specified below, and mo- mentum coefficients &e= = 1 - 24 The following holds:
- m
(f+1d)) Notably, our analysis assumes the worst case where all malicious workers collude with the server to breach privacy (q = f in Theorem 4.1). If they do not (i.e., 9 = 0), the trade-off still holds, but constants improve with the choice of and 0, discussed after Theorem 4.1 and empirically validated in Section 5.
1. Cu is p-strongly convex: 1
M(t+240 4 then L
E[Cu(Or)- - 2 KGow
L²
+
12T + 12T22
For comparison, recall that the minimax optimal privacy- utility trade-off in LDP is O(,4)) ) (Duchi et al., 2018), which is n times larger than the corresponding rate in CDP given by O ( (Bassily et al., 2014), both under user- level dataset adjacency. Therefore, our rate of Ō (f+1)d derived under SecLDP naturally bridges these two extremes. Notably, as the number of malicious workers f decreases, our rate converges to CDP. Specifically, our rate matches CDP when f f= ((1) and remains strictly better than LDP as long as f is sublinear in n. Furthermore, under the LDP privacy model (a = 0), such when shared random- ness among workers is unavailable, CAFCOR recovers the tftte-of-the-ar privacy-utility trade-off of θ nnz))
/
2. LH is non-convex: If = min
T 1 163 VLT) J.
v3Ca
then
LLC LCo
[0) kO cov
VT
T
where S denotes inequality up to absolute constants and the expectation is over the randomness of the algorithm.
Our result recovers the itate-of-fon ofte-offthh-ar convergence analysis in robust optimization in the local privacy model (Allouah et al., 2023c) when setting ooor = 0. The key difference with the latter analysis is the role of the correlated noise magnitude oeor, which appears in the dominating term in- side T, in both strongly convex and non-convex settings. Moreover, our convergence rates exhibit the standard depen- dence on the number of iterations in smooth stochastic op- timization: ( for the strongly convex case and O VT for the convex case. The presence of non-vanishing term in 7 is fundamental in robust optimization in heteroge- neous data settings (Karimireddy et al., 2022). Finally, our upper bound in the strongly convex case also applies to non- convex loss functions that satisfy the Dolyak-Lojasiwwiee inequality (Karimi et al., 2016).
CAF plays a crucial role in ensuring that Algorithm 1 achieves the derived trade-off. In contrast, employing stan- dard robust aggregations, such as the trimmed mean or median (Yin et al., 2018), significantly degrades theoretical performance. Specifically, after replacing CAF with the trimmed mean, the resulting convergence rate is Ö n for f > 0 (see Appendix C.5). This rate is n times worse than that achieved with CAF and only matches LDP when f = Ō(1). For larger f. performance further degrades, with rate strictly worse than LDP.
fd
6

---

Towards Trustworthy Federated Learning with Untrusted Participants
1.00
1.00
Test accuracy
0560 SeCLDP
Test accuracy
0.75
0.75
0.50
0.50
0.25
0.25
0.00
0.00
10
20
25
10
15
25
30
Iteration
Iteration
(a) MNIST, f =
(b) MNIST, f= 10
0.8
0.8
Test accuracy
Test accuracy
0.6
0.6
0.4
0.4
0.2
0.2
0.0
10
20
25
10
15
25
30
Iteration
Iteration
(c) Beshion-MNISTH f 5
(d) Fashion-MNIST. f
Figure 1: Comparison of CAFCOR and DSGD under four privacy threat models on Beshion--MMNIST. There are 100 workers, including f = 5 and 10 malicious workers executing ALIE (Baruch et al., 2019), A homogeneous data distribution considered among honest workers. User-level DP used and privacy budgets for MNIST are & = 26.4 and 27.8 for = 10 and f = 5, respectively. For Fashion-MNIST, the privacy budget is 39.6. Throughout, we set 10-4
5. Experimental Evaluation
at the end of training, we use Opacus (Yousefpour al., 2021). Our experiments conducted with five random seeds (1-5) to ensure reproducibility. All reported results include standard deviation across these seeds. To facilitate reproducibility, we intend to publicly release our code.
We empirically evaluate the performance of CAFCOR a distributed environment under varying threat models. We also compare CAFCOR to existing robust and private algo- rithms, demonstrating its empirical advantages.
Datasets and models. We consider two widely used image classification datasets: MNIST (LeCun & Cortes, 2010) and Fashion-MNIST (Xiao et al., 2017). While these tasks are relatively simple in standard, non-adversarial settings, they become challenging with the introduction of malicious workers (Karimireddy al., 2021; Farhadkhani al., 2022) and the differential privacy constraint (Noble al., 2022).
5.1. Comparison of Threat Models
In Figure 1, we compare CAFCOR to the DSGD baseline across four privacy regimes: LDP, CDP, SecLDP (assuming no collusion), and a novel threat model we call ByzLDP discussed in Section where all malicious workers collude with the server. We execute CAFCOR a distributed system with 100 workers among which f E {5, 10} mali- cious. On MNIST, we batch size b 50, learning rate 7 0.075, momentum parameter 3 0.85, and clipping parameter C = 2.25. For Fashion Fashion-MNISTT, MNIST, we use = 100,
MNIST images normalized using mean of 0.1307 and standard deviation of 0.3081, while Dushion-MNISY images are horizontally flipped. To simulate data heterogeneity, we sample data for honest workers using a Dirichlet distribution of parameter a (Hsu et al., 2019). We consider homogeneous distribution scenario, and an extreme het- erogeneity scenario where data is sorted by label and evenly assigned to honest workers. On both datasets, same convolutional neural network with a model size of 431,080 parameters, using the negative log-likelihood loss.
= 0.3, 3 = 0.9, and C = 1. For both datasets, we train for = 30 iterations and apply fg-regularization 10-4 We adopt user-level DP across all threat models. On MNIST, the privacy budgets reach = 26.4 and 27.8 8 for f = 10 and f = 5, respectively. On Fashion-MNIST the privacy budget is 39.6 for both values of f. In Figure 1, we consider malicious workers executing the ALIE attack. Results for the remaining attacks are deferred to Appendix D.I, where similar trends are observed.
10.
train the
Attacks. We consider four state-of-the-art attacks: Fall of Empires (FOE) (Xie et al., 2020), A Little is Enough (ALIE) (Baruch al., 2019), Label Flipping (LF) and Sign Flipping (SF) (Allen-Zhu et al., 2020).
As illustrated in Figure 1, the performance of DSGD un- der LDP is significantly lower than under CDP. Under SecLDP, CAFCOR achieves performance closely match-
Reproducibility. To estimate the privacy budgets achieved

---

Towards Trustworthy Federated Learning with Untrusted Participants
100
100
nscn if
Test Test Accuracy
CARCOR
Test Test Accuracy
75
75
50
50
25
25
100
200
300
100
200
300
400
Iteration
Iteration
(a) MNIST, Sign Flipping attack
(b) MNIST, Label Flipping attack
100
100
Test Accuracy
Test Accuracy
75
75
50
50
25
25
100
200
300
400
0
100
200
300
400
Iteration
Iteration
(c) Fashion-MNIST. Sign Flipping attack
(d) Fashion-MNIST Label Flipping attack
Figure 2: Performance of CAFCOR versus standard robust algorithms. There are f = 5 malicious workers among n = 15 on MNIST and a 1, and = 3 malicious workers among n 13 on Fashion-MNIST and a = 0.1. The CDP privacy model is considered under example-level DP, and the privacy budget (e, 6) (13.7, 10-1) throughout.
ing CDP and substantially outperforming LDP on both datasets. For = 5, CAFCOR-SecLDD exhibits identi- cal final accuracies to the adversary- free DSGD baseline under CDP: 83% on MNIST and 72% on Fashion-MNIST. When f 10, CAFCOR-SecLDP has slight decrease in accuracy compared to DSGD-CDP but remains significantly superior to DSGD-LDP. Under the stronger ByzLDP threat model, CAFCOR maintains performance comparable to Se- cLDP for f 5. On Fashion-MNIST, the difference is negligible, demonstrating effective mitigation of malicious worker collusion.
workers and f E {1,3, 5} malicious workers, with hetero- geneous distributions with a E {0.1, and an extreme distribution. Training is conducted with b = 100, = 5, and 400 iterations for both datasets. Figure presents results for LF and SF attacks with 5, a 1 on MNIST, and 3, 0.1 Pashion-MNIST Example-level DP is applied under the CDP privacy model, yielding privacy budget of (s. 6) (13.7, 10-4) across all configurations.
Figure demonstrates the clear superiority CAFCOR (and CAF) over competing aggregations across all configurations, even under the least stringent privacy model (CDP). While MK matches CAFCOR on Fashion-MNIIT under the LF attack, its performance significantly deteriorates under the SF attack and on MNIST. Meamed performs relatively well under LF on MNIST but struggles under LF and SF attacks on Fashion-MNIST and under the SF attack on MNIST, with CAPCOR outperforming it consistently. Other aggre- gations, such as CWTM, CWMED, and GM, exhibit poor performance across both datasets and attacks, particularly under LF, where their utility drops significantly and the best competing aggregation among them achieves accuracy just above 50%. In contrast, CAF achieves results nearly indistinguishable from adversary-free DSGD under the L.F attack on both datasets (90% accuracy) and delivers the best performance under SF, reaching an accuracy close to 80%. This pattern holds consistently across the remaining attacks, detailed in Appendix D.2.
MNIST, however, accuracy decreases by 8% due to the more stringent privacy constraints. For f= 10, the gap between CAFCOR-Secl.DP and CAFCOR- ByzLDP is more pronounced, particularly MNIST (see Figure lb). Yet, MAFCoR-ByzLDD still significantly outper- forms DSGD-LDP, where training struggles to exceed 30% accuracy. These findings underscore the practical utility of SecLDP and ByzLDP, and the robustness of CAFCOR under stringent privacy constraints. For completeness, we also evaluate CAFCOR under the CDP and LDP privacy models in Appendix D.I, demonstrating that the performance of CAFCOR matches the DSGD baseline under both models.
5.2. Comparison with Prior Robust Aggregations
To highlight the performance of our aggregation, replace CAF in Algorithm with standard alternatives in robust dis- tributed learning: coordinate- wise trimmed mean (CWTM) and median (CWMED) (Yin et al., 2018), 8), geometric median (GM) (Chen et al., 2017), Multi-Krum (MK) (Blanchard al., 2017), and mean around median (Meamed) (Xie et al., 2018). We consider system with
10 honest
8

---

Towards Trustworthy Federated Learning with Untrusted Participants
6. Conclusion
Allouah, Y., Guerraoui, R., Gupta, N., Pinot, R., and Rizk, G. Robust distributed learning: Tight error bounds and breakdown point under data heterogeneity. In Thirty- seventh Conference on Neural Information Processing Systems, 2023b.
Achieving good utility while simultaneously ensuring both robustness against malicious parties and strong privacy in distributed learning typically requires trusting the central server, an often unrealistic assumption. We address this chal- lenge with CAFCOR, a novel algorithm leveraging shared randomness among workers to enable correlated noise in- jection prior to robust gradient aggregation. Even under col- lusion between malicious workers and an untrusted server, CAFCOR achieves a strong privaey-utility trade-off, signif- icantly outperforming local DP (where there are no trust assumptions) while approaching the performance of central DP (where the server is trusted). Our results show that pri- vacy and robustness can coexist without sacrificing utility, yet open questions remain. Notably, what is the optimal utility under SecLDP, and does CAFCOR achieve it?
Allouah. Y., Guerraoui, R., Gupta, N., Pinot, R., and trilemma
Stephan, J. On the privacy-robustnes--iiin in distributed learning. In International Conference on Machine Learning, pp. 569-626. PMLR, 2023c.
Allouah, Y., Koloskova, A., EI Firdoussi, A., Jaggi, M., and Guerraoui, R. The privacy power of correlated noise in decentralized learning. In Proceedings of the 41st International Conference on Machine Learning, ICML, 2024.
Baruch, G., Baruch, M., and Goldberg, Y. A little is enough: Circumventing defenses for distributed learning. In Wallach, H., Larochelle, H., Beygelz- imer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Process- ing Systems, volume 32. Curran Associates, Inc., 2019. URL
Acknowledgements
YA acknowledges support by SNSF grant 200021 200477.
Impact Statement
cc /e//appt_iilleeppper/////////// neurips. ccle5914D06cd1886bbccdd6e3333333 pdf.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Bassily, R., Smith, A., and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foun- dations of computer science, pp. 4644773 IEEE, 2014.
References
Acharya, J., Sun, Z., and Zhang, H. Robust testing and estimation under manipulation attacks. In International Conference on Machine Learning, pp. 43-53. PMLR, 2021.
Bertsekas, D. and Tsitsiklis. J. Parallel and distributed com- putation: numerical methods. Athena Scientific, 2015.
Blanchard, P., El Mhamdi, E. M., Guerraoui, R., and Stainer, J. Machine learning with adversaries: Byzantine tolerant gradient descent. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30, pp. 119-129. Curran Associates, Inc., 2017.
Agarwal, N., Suresh, A. T., Yu, X. X., Kumar, S., and McMahan, B. cpsgd: Communicatiion-effiieee and differentiaall--riinee distributed sgd. Advances in Neural Information Processing Systems, 31, 2018.
Alabi, D., Kothari, P. K., Tankala, P., Venkat, P., and Zhang, F. Privately estimating gaussian: Efficient, robust, and optimal. In Proceedings of the 55th Annual ACM Sympo- sium on Theory of Computing, pp. 483-496, 2023.
Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A.. and Seth, K. Practical secure aggregation for privacy- preserving machine learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communica- tions Security, pp. 1175-1191, 2017.
Allen-Zhr Zhu, Z., Ebrahimianghazani, F., Li. and Alistarh, D. Byzantine ressileet non-convex stochastic gradient descent. International Conference on Learning Repre- sentations, 2020.
Chen, Y., Su, L.., and Xu, J. Distributed statistical machine learning in adversarial settings: Byzantine gradient de- scent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1-25, 2017.
Allouah, Y., Farhadkhani, S., Guerraoui, R., Gupta, N., Pinot, R., and Stephan, J. Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 1232-1300. PMLR, 2023a.
Cheu, A., Smith, A., Ullman, J., Zeber, D., and Zhilyaev, M. Distributed differential privacy via shuffling. In Ad- vances in
2019: 38th Annual

---

Towards Trustworthy Federated Learning with Untrusted Participants
International Conference on the Theory and Applica- tions of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part I 38, pp. 375-403. Springer, 2019.
In Proceedings of the Thirtieth Annual ACM-SIAM Sym- posium on Discrete Algorithms, pp. 2019.
SIAM,
Farhadkhani, S., Guerraoui, R., Gupta, N., Pinot, R., and Stephan, Byzantine machine learning made easy by resilient averaging of momentums. In Chaudhuri, K., Jegelka, S., Song, L.,, Szepesvari, C.,, Niu, G., and Sabato, S. (eds.). Proceedings of the 39th International Confer- ence on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 6246-6283. PMLR, 17-23 Jul 2022. URL httptttp::/ppooeeediddeee .mlr. press vv 62 7ress//.dd/fcchhcchhh..2222 http//aaaaaaaaaii22aaaa.aa html.
Cheu, A.. Smith, A., and Ullman, J. Manipulation attacks in local differential privacy. In 202/ IEEE Symposium on Security and Privacy (SP), pp. 883-900. IEEE, 2021.
Choffrut, A., Guerraoui, R., Pinot, R., Sirdey, R., Stephan, J., and Zuber, M. Towards practical homomorphic aggregation in byzantine- resilient distributed learning. In Proceedings of the 25th International Middleware Conference, Middleware '24, pp. 431-444, New York, NY, USA, 2024. Association for Computing Machin- ery. ISBN 9798400706233, doi: 10.1 10.1145/3652892. 3700783. URL https:/ http://doo.org/01111/.1 3652892. (652892.3700788.
Feng, J., Xu, H., and Mannor, S. Distributed robust learning, 2015.
Fredrikson, M., Jha, S., and Ristenpart, T. Model in- version attacks that exploit confidence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Commu- nications Security, CCS '15, pp. 1322-1333, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450338325. doi: 10.1145/ 3310103.2816677 URL https://doff org/10. 1145
Choudhury, O., "koulalas-Divanis A., Salonidis, T., Sylla, I., Park, Y., Hsu, G., and Das, A. Differential privacy- enabled federated learning for sensitive health data, arXiv preprint ar 19/0. 02.578. 2019.
Corrigan- Gibbs, H. and Boneh, D. Prio: private, robust, and scalable computation of aggregate statistics. In Proceedings of the 14th USENIX Conference on Net- worked Systems Design and Implementation, NSDI 17, pp. 250-25922222 282, USA, 2017. USENIX Association. ISBN 9781931971379.
Gil, M., Alajaji, F., and Linder, T. Rényi divergence mea- sures for commonly used univariate continuous distribu- tions. Information Sciences, 249: 121-131, 2013.
Gu, X., Li, M., and Xiong, L. Dp-brem: differentially- private and byzantine-robur federated learning with client momentum. arXiv preprint arXiv:2306. /2608, 2023.
Dean, J., Corrado, G., Monga, R., Chen, K., Devin, M., Mao, M., Ranzato, M. a., Senior, A., Tucker, P., Yang, K., Le, Q., and Ng, A. Large scale distributed deep networks. In Pereira, F., Burges, C. J. C., Bottou, L., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems, volume 25, Curran Associates, Inc., 2012.
Guerraoui, R., Gupta, N., Pinot, R., Rouault, S., and Stephan, J. Differential privacy and Byzantine re- silience in sgd: Do they add up? In Proceed- ings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC'21, pp. 391-401, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450385480. 0465084.3467919 URL https://doi. http///0...../....////// 1145 1445/3455884.344 3467919.
Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Moitra, A., and Stewart, A. Being robust (in high dimensions) can be practical. In International Conference on Machine Learning, pp. 999-1008. PMIR, 2017.
doi: 10.1145/
Duchi, J. C., Jordan, M. I., and Wainwright, M. J. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations Computer Science, pp. 229-438. IEEE, 2013.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual leam- ing for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Duchi, J. C., Jordan, M. I., and Wainwright, M. J. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):182- 201, 2018
Hitaj. B., Ateniese, G., and Perez-Cruz, F. Deep models under the gan: Information leakage from collaborative deep learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS '17, pp. 603-618, New York, NY, USA, 2017. Asso- ciation for Computing Machinery. ISBN 9781 9781450349468.
Erlingsson, Ó. Feldman, V., Mironov, I., Raghunathan, A.,
Talwar, K., and Thakurta, A. Amplification by shuffling: From local to central differential privacy via anonymity.
10

---

Towards Trustworthy Federated Learning with Untrusted Participants
doi: 10. 10.114553113395631344022 URL httpps:///o. 0tte/100111//3133333 3134012.
International Conference on Learning Representations, 2022. URL https: /twp///vieeeeeeee/o//e/eeee.eeee net/ new../rrmtf forum? id=jxKKDEi5vJt.
Hopkins, S. B., Kamath, G., and Majid, M. Efficient mean estimation with pure differential privacy via sum-of- squares exponential mechanism. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Com- puting, pp. 10006-141,,00 2022.
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhod- nikova, S., and Smith, A. What can we learn privately? SIAM Journal on Computing, 40(3):793-88) 2011.
Lamport, L., Shostak, R., and Pease, M. The Byzan- tine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-011, jul 1982. ISSN 0164-0925. doi: 10. 10.1145/3571722:357776 URL https::/doi..nt 10.1145/357172.5577
Hsu, T.-M. H., Qi, H., and Brown, M. Measuring the effects of Eon--nded hon-identical data distribution for federated visual clas- sification, 2019. URL /ettps://arxiv.... org/ abs/ 1909. 06335.
Hu, R., Guo, Y., Li, H., Pei, Q., and Gong, Y. Personalized federated learning with differential privacy. IEEE Internet of Things Journal, 7110)9530-9539 2020.
LeCun, Y. and Cortes, C. MNIST handwritten digit database. 2010.
Liu, X., Kong, W., Kakade, S., and Oh, S. Robust and dif- ferentially private mean estimation. Advances Neural Information Processing Systems, 34:3887-3901, 2021.
Intiaz, H., Mohammadi, J., Silva, R.,, Baker, B., Plis, S. M., Sarwate, A. D., and Calhoun, V. D. correlated noise- assisted decentralized differentially private estimation protocol, and its application fmri source separation. doi: 10.1
Ma, X., Sun, X., Wu, Y., Liu, Z., Chen, X., and Dong, C. Differentially private Byzantine-robust federated learning. IEEE Transactions on Parallel and Distributed Systems, 2022.
volume 69, pp. 6355-6370, 2021. 2021.3126546.
Jayaraman, B., Wang, L., Evans, D., and Gu, Q. Distributed learning without distress: Friacy--reeservng empirical risk minimization. Advances in Neural Information Pro- cessing Systems, 31, 2018.
Melis, L.,, Song, C., Cristofaro, E. D., and Shmatikov, V. Ex- ploiting unintended feature leakage in collaborative learn- ing. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, pp. 691-706 IEEE, 2019. doi: 10.1109/SP22019.00000 URL https: /doi.dii.o////// org /00 1109/ 2019 00029.
Kairouz, P. McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., al. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
Mironov, I. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263- 275. IEEE, 2017.
Kaissis, G. A., Makowski, M. R., Rückert, D., and Braren, R. F. Secure, privacy-preserving and federated machine learning in medical imaging. Nature Machine Intelli- gence, 266):305-31, 2020.
Nesterov, Y. et al. Lectures on convex optimization, volume 137. Springer, 2018
Noble, M., Bellet, A., and Dieuleveut, A. Differentially pri- vate federated learning on heterogeneous data. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 10110-10145. PMLR, 2022.
Karimi, H., Nutini, J., and Schmidt, M. Linear conver- gence of gradient and mookimal-gradices methods under the bayyak-tojasiewizz condition. In Joint European con- ference machine learning and knowledge discovery in databases, pp. 795 1158811.22 Springer, 2016.
Pauwels, E. Lecture notes: Statistics, optimization and
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. Scaffold: Stochastic controlled averag- ing for federated learning. In International Conference on Machine Learning, pp. 5133. PMLR, 2020.
algorithms in high dimension, 2020.
Phong, L. T., Aono, Y., Hayashi, T., Wang, L., and Moriai, S. Privacy- Privacyprreservin deep learning: Revisited and en- hanced. In Batten, L., Kim, D. S., Zhang, X., and Li, G. (eds.), Applications and Techniques in Information Secu- rity, pp. 100-110, Singapore, 2017. Springer Singapore. ISBN 978-981-10-5421-1.
Karimireddy, S. P., He, L.,, and Jaggi, M. Learning from history for Byzantine robust optimization. International Conference On Machine Learning, Vol 139, 139, 2021.
Karimireddy, S. P., He, L., and Jaggi, M. Byzantine-robus learning on heterogeneous datasets via bucketing. In
Rice, J. A. Mathematical statistics and data analysis. Cen- gage Learning, 2006.

---

Towards Trustworthy Federated Learning with Untrusted Participants
Rigollet, P. and Hütter, J.-C. High dimensional statistics. Lecture notes for course 18S997, 813(814):46, 2015.
Yin, D., Chen, Y., Kannan, R., and Bartlett, P. Byzantine- robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 9650-56599 PMLR, 2018.
Sabater, C., Bellet, A., and Ramon, J. An accurate, scalable and verifiable protocol for federated differentially private averaging, Machine Learning, 1 111(11):224-422) 4293, 2022.
Yousefpour, A., Shilov, I., Sablayrolles, A., Testuggine, D., Prasad, K., Malek, M., Nguyen, J., Ghosh, S., Bharadwaj,
Shamir, A. How to share secret. Communications of the ACM, 22(11))612-613, 1979.
A., Zhao, J., Cormode, G., and Mironov, I. Opacus: User- friendly differential privacy library in pytorch, 2021. URL https: //tp///axxit aaaaaaaiiiiiiiio org/ abs / 221//119.... 12298.
Shokri, R., Stronati, M., and Shmatikov, V. Membership inference attacks against machine learning models. CoRR, abs/1610.058200, 2016.
Zhang, C., Li, S., Xia, J., Wang, W. Yan, F., and Liu, Y. BatchCrypt: Efficient homomorphic en- cryption for Cross-Silo federated learning. In 2020 USENIX Annual Technical Conference (USENIX
Steinhardt, J., Charikar, M., and Valiant, G. Resilience: A criterion for learning in the presence of arbitrary outliers. In 9th Innovations in Theoretical Computer Science Con- ference (ITCS 2018). Schloss Bogstuhl-Leibbiz-Zonn fuer Informatik, 2018
ATC 20), pp. 493-506. USENIX Association,
July 2020,
ISBN 978-1-939133-1444,
URL
https:/ www.:w/sseix...o www.:ussi.....cceeoooo www.emii.org//cofeeeeeeee
atc20 atc20/presenne http:///reeentattin///arrrggeeee
lang.
Vershynin, R. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint urXiv:1011.333 2010.
Zhu, B., Jiao, J., and Steinhardt, J. Robust estimation via generalized quasi-gradients Information and Inference: Journal of the IMA, 1 11(2):581-633 2022.
Zhu, H. and Ling, Q. Bridging differential privacy and Byzantine-rouustees via model aggregation. In Raedt, L. D. (ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 2427-2433, International Joint Conferences Artificial Intelligence Organization, 7 2022. doi: 10.24963/ijcai. 2022/337. URL. https: //ooo..... org / 949 i 1jcai.200 /377. Main Track.
Wang, Z., Mengkai, S., Zhang. Z., Song, Y., Wang, Q., and Qi, H. Beyond inferring class representatives: User-level privacy leakage from federated learning. pp. 2512-2520, 04 2019. doi: 10.1
Xiang, M. and Su, L. 8-stochastic sign sgd: A Byzantine resilient and differentially private gradient compressor for federated learning. arXiv preprint arXiv:22 10.00665, 2022.
Zhu, L., Liu, Z., and Han, Deep Icakage from gradients. In Wallach, H., Larochelle, H.,, Beygelzimer, A., d Alché- Buc, F., Fox, E., and Garnet,, R. (eds.), Advances in Neural Information Processing Systems 32, pp. 14774 14784. Curran Associates, Inc., 2019.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist; novel image dataset for benchmarking machine learning algorithms, arXiv preprint 17810:100, 2017
Xie, C., Koyejo, O., and Gupta, I. Generalized Byzantine- tolerant sgd. 2018
Xie, C., Koyejo, O., and Gupta, I. Fall of empires: Break- ing byzantine-tolerant sgd by inner product manipula- tion. In Adams, R. P. and Gogate, V. (eds.), Proceed- ings of The 35th Uncertainty Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pp. 261-270. PMLR, 22-25 Jul 2020. URLhttps: http://pteeeenn...c/eep mlr press/ v115/xie20a. httt/ieee2a.am......111
Xie, C., Long, Y., Chen, P.-Y., Li, Q., Koyejo, S., and Li, B. Unraveling the connections between privacy and certified robustness in federated learning against poisoning attacks. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pp. 1511-1525, 2023.
12

---

Towards Trustworthy Federated Learning with Untrusted Participants
Organization of the Appendix
Appendix presents the privacy analysis of CAFCOR. Appendix B contains the robustness analysis of Proposition 4.1. Appendix C provides the convergence analysis of CAFCOR. Appendix contains additional experimental results.
A. Privacy Analysis: Proof of Theorem 4.1
Definition A.1 (a-Rényi divergence). Let a >> 0, F 1. The a-Rényi divergence between two probability distributions P and Q is defined as
P(X)
(P Q = a
log Ex~Q
Q(X)
Lemma A.I (GGil et al., 2013)). Let a > 0, a F M, P2 E IR", and Y E Raxx, Assume that E is positive definite. The a-Rényi divergence between the multivariate Gaussian distributions N 2 and ( 2) is
T (N(N(11 2) || [ 2)) 2 (MI - 12) - (m) - p2).
We now define secret-based local Rényi differential privacy (SecRDP), a strong variant of SecLDP based on Rényi DP, paraphrasing Allouah et al. (2024).
Definition A.2 (SecRDP). Let E 2 0. E [0, 1. Consider a randomized decentralized algorithm As Xmxx + y, which outputs the transcript of all communications, given the full set of secrets S. Algorithm As said to satisfy (ar, E, (..ott)) -SeRRD if As satisfies E)-D), given that the subset of secrets Sknown C 8 is revealed the adversary. That is, for every adjacent datasets D, D' Xmxn we have
(A((((D) Sknown As(DD) Skmonon E.
where the left-hand side is the Rényi divergence (Definition A.2) between the probability distributions of A(D) and A(D"), conditional on the secrets Sau revealed to the adversary. We simply say that As satisfies (o,,))-ecRDPP if it satisfies (or,,, Skmown DSecRDP and Smoom is clear from the context.
Both SecLDP and SecRDP preserve the properties of DP and RDP, respectively, since these relaxations only condition the probability space of the considered distributions.
Lemma A.2 (RDP Adpative Composition, (Mironov, 2017)). If Mr that takes the dataset as input is --).P. and M2 that takes the dataset and the output of Mj as input is (a, -R)DP, then their composition is (a, + RDDP
Lemma A.3 (RDP to DP conversion, (Mironov, 2017)). If . is (o,E)-RDP, then M is (E log (1/8) 8)-DP for all 5 E (0, 1).
We first prove a lemma analyzing a single iteration of Algorithm 1 within the SecRDP formalism. Lemma A.4. Let and q f. Each iteration of Algorithm satisfies (a, oe)-Se (Definition A.2) against the honest-but-curious server, colluding with q malicious workers, where
20
2
1 (f 1)0 for + ind
cor
(2)
(n 2)02
of ind
Proof. Let a > 1, 1 1, and I C [n] H. be an arbitrary group of [Z] malicious workers. Recall that we denote by Sz = {s j [n], E ]} the set of secrets revealed by the malicious workers in I to the server. We will prove that Algorithm satisfies (a, e, Sz) 3y))-eDDDPP which protects against the honest-but-curion server, in addition to colluding malicious workers. For ease exposition, we consider the one-dimensional case Extending the proof to the general case is straightforward.
Formally, at each iteration of Algorithm 1, users possess private inputs (gradients) in the form of vector [-C, given that gradients are clipped at threshold C.. Each user i E [n) shares the following privatized quantity:
2 = F; +
Ui + U2
(3)
1=1
13

---

Towards Trustworthy Federated Learning with Untrusted Participants
where Vij uy , (0, for all j [n], and 82 (N o
Our goal is to show that the mechanism producing Nx := [ se satisfies SecRDP when a single entry of X = [ is
arbitrarily changed; i.e., one user's input differs. To do so, we first rewrite (3) to discard the noise terms known to the colluding curious users who can simply substract them to get for every i H:
Vig + U. =
+
1 + 2 1 +
Uij + U.
(4)
==1
JEH
JEH
(
JEHUT
where U, Σn 11 JEHUI
Viy + 02 NOO, (f 2or + mnd). We now rewrite the above in matrix form as:
x Xx + KNH + N,
(5)
f)x (n- f-1 where K E (nn- f1x (n- f-1 is the vector of pairwise noises, and N = [T.KEH.. Now, consider two input vectors XA. E |--,
2
is the oriented incidence matrix of the complete graph over H. Nu = |ny))sissss-
R
2
which differ maximally in an arbitrary coordinate E [n - f] without loss of generality:
XA - Xg = 2Cea E R"-!
(6)
where e; is the vector of R=-/ where the only nonzero element is in the i-th coordinate.
We will then show that the a-Rényi divergence between XA and XB, which are respectively produced by input vectors Xa and XB, is bounded. To do so, by looking at Equation (5), we can see that XA, XB follow a multivariate Gaussian distribution means XA, A respectively and variance
Σ == - XX) - XA) T = E{XB (B)(XB - XB) = Loo L + ((f D) + ona)) In-g E (R(=f))((m f)
where L - KK E (((--)(a--)) is the Laplacian matrix of the complete graph over H. Note that Es positive definite when - -) + lud > 0, because L is positive semi- Also, recalling the expression L (n f) 11 of the Laplacian of the complete graph over H. we have
Σ = 0f L + ((f g) + omaa) In-f oaar (nn - f)hn-s 11 + ((f -9)o2or + oiaa) In-S
((n q) 2 + ind)) In-s 2 11
(8)
Moreover, recall the Ahherman-Morissee formula, i.e., for any matrix A and vectors u, such that v A--"u + -1, we have "uo"
(A + wo T)-- -- 1+o 1 Using this formula, we have
Σ = [[(n- g)020r + ond)) In-s o² 11
02
(n 9) + Ind In- +
11
[nn - 20oe + 2
(n-No No
(n-q)o t
1
0%
In In-f (n g) + o (f 2)02.r
11
(9)
(n 2) + Ind
ind
Finally, following Lemma A.1, the aéRényi divergence between the distributions of XA and X is
Dx(XA || Xx)
a 2 (Xx -xn) -x EX -X))
1
2
(n - 200 + and
(n - g)o + oud (s o) o
2aC
2er
1
(10)
(n 9)022r + ond
(f - 90020r + o
14

---

Towards Trustworthy Federated Learning with Untrusted Participants
We now prove the SecLDP property of the full Algorithm by using the composition properties of RDP and converting DP (Mironov, 2017).
Theorem 4.1. Let ( (0, log((/))), q S f 2. Algorithm satisfies (s, (e. against an honest-but- curious server colluding with q malicious workers, if
(n 1) cor + ind
16C log(1/6) (lgg/)))(
1 1
Geu (f-4)0 to
E²
Proof. Recall from Lemma A.4 that each iteration of Algorithm satisfies (a, StE SSecRD against collusion at level q for every & >> 1 where
20
o
Eaep
1 (f
cor
(11)
n 20
+ o ind
o
o
ind
Thus, following the composition property of RDP from Lemma A.3, the full Algorithm I satisfies (a, "'aEEsep)-SSRRRR for any a > 1. From Lemma A.3, we deduce that Algorithm satisfies (e'(a), 8) DP for any E (0, 1) and any a > 1, where
e'(a) Ta + log(1/8)
20
o
log(1/8)
aT (n Do2er + o
1
(ʃ 9 oo + a
a
Optimizing the above bound over yields the solution
a. = 1 + v /lo(11/6) (nn tom
0120 Lt Tt
which in turn leads to the following bound
02
E+ = ST (n docr + oidd
20
1 (f g)0 cor + +o
+ 20
2o (1/8)
(/ (/-9)03 cur to mnd
(n --)00000 + of
Now, recall that assume
1
cor
<
(n 90...r o
(f 2) + nn
16C log(18)
Therefore, using the assumption S log (1/8), Algorithm 1 satisfies (E., 6) SScLLDP where
2²
+
V2 <
8log (1/5)
This concludes the proof.
15

---

Towards Trustworthy Federated Learning with Untrusted Participants
B. Robustness Analysis: Proof of Proposition 4.1
6f Proposition 4.1. Let 0 - f 2 and ====- n-1 (1+ (1+m21) ) Let 21...., In E R and S S [n] be any subset of size
n- Let Is 1 [S] Lies Vi, and Amax denote the maximum eigenvalue operator. The oulput & CA, satisfies:
| - Es|2- S k.
Amax
Σ EE
(as - [ - T
S
Proof. Let 1,0 S f < n/2, 21 II RR, and S [n]. 18| f. Denote Is
Eies 2i and
o = Amax (x; (2) -sS
First, we remark that Algorithm 2 terminates after most 2 iterations. Indeed, each iteration, least one weight G, E [n], becomes zero-this is true for any [n] such that i E argmaxye(x) (ter I. /ee) - 2 for the remaining iterations. Therefore, since the weights c, i [m], are all in [0, 1], is guaranteed that >i G S n 2f after 2 iterations.
Second, show that there exists an iteration such that the maximum eigenvalue o is at most 2n(n-f) (n- f3
o.. For the sake of contradiction, assume that for every iteration we have o² > 2n(a= (x-27)= is well-known from the analysis of the original Filter algorithm (Diakonikolas et al., 2017; Steinhardt et al., 2018) (see (Zhu al., 2022, Appendix E.3) for details) that the following invariant thus holds:
Σ0-
Σ (1-
(12)
iES
xE(n](S
That is, the mass removed from the points in S is never greater than that removed from the points outside Importantly manipulating the bound above yields:
Σ 4 4 +
Σ 4: 2 n 2f.
(13)
1EIM/SS
This is exactly the opposite of the termination condition, i.e., the algorithm does not terminate. This a contradiction, since we have shown first that the algorithm terminates. Therefore, we have shown that there exists an iteration such that the maximum eigenvalue 0² is at most (n-2
2m(n-fl
Finally, recall that the output μ. is the weighted mean of the original inputs with respect to weights corresponding to of the smallest maximum eigenvalue across the algorithm. Thus, thanks to the last shown result, we have of < (n-27)² 0 Therefore, using (Zhu et al., 2022, Lemma 2.2), we have
2nin
f ||w. Esll S V n (o. +00)
f n-
2n(n - f) 1+
S
V
0s.
(14)
f
n 2f
We conclude by taking squares and using Jensen's 's inequality.
CAF draws inspiration from recent algorithmic advances in robust statistics (Diakonikolas et al., 2017). However, key distinction is that CAF does not rely on knowing a bound on the covariance of honest inputs, which has been a crucial requirement the design efficient robust mean estimators (Diakonikolas et al., 2017; Steinhardt et al., 2018). In the aforementioned literature, knowing such bound allows for an alternative termination condition in Algorithm 2, where the algorithm halts once the weighted covariance is sufficiently small relative to the known bound, and the final output computed as the mean weighted by the last iteration's computed weights (Diakonikolas et al., 2017).
16

---

Towards Trustworthy Federated Learning with Untrusted Participants
C. Utility Analysis: Proof of Theorem 4.2 and Corollary 4.1
C.1. Preliminaries
We recall that we assume the loss function to be differentiable everywhere, throughout the paper.
Definition C.1 (L-smoothness), A function L: R - IR is L-smooth if. for all 0, I' E IR", we have
L
C(0') - (()) (' 0) -
10' 011 2
The above is equivalent to, for all 0,0 0. E IRd, having ||VC(()) VL(()]| S L 10 - 011 (see, e.g., (Nesterov et al., 2018)).
Definition C.2 (u-strong convexity). A function L: Rd IR is p-stonnly convex if. for all 0, E Rd, have
[(0) ((0) - (VL(0), 8)
11 6 0|
2
Moreover, we recall that strong convexity implies the Polyak-Lojasiewiez (PL) inequality (Karimi et al., 2016) 2p (C(0) - C.) I |VC())) Note that a function satisfies L-smoothness and p-strong convexity incquality simul- taneously only if p S I..
C.2. Proof Outline
Our analysis of CAFCOR (Algorithm 1), is inspired from standard analyses in non non-private robust distributed learning (Karimireddy et al., 2021; Farhadkhani al., 2022; Allouah et al., 2023c). We include all proofs for completeness.
Notation. Recall that for each step i, for each honest worker ws.
m (4)
B
B1-mm--
(4)
+
(x-1)gt
(15)
ft
9t
+
(65)
+
(i),
T( ~ (id) -1(
(1f) (10) ~NO0, 200
(16)
jf1
where we initialize mo
(6) -0. Recall that we denote
R₁ = CAF mi m!..,
(17)
0.+1 = 0: - RR.
(18)
Throughout, we denote by Pe the history from steps to E , = (o.... 0,: m m m i E [n]] }
By convention, P1 respectively. Thus,
}0,} We denote by Es [-] and IE| [-] the conditional expectation E| [P]] and the total expectation,
E, E.. [-]].
Or, the honest workers' local momentums may drift away from each other. The drift has three distinct sources: (i) noise injected by the correlated noise scheme, (ūi) gradient dissimilarity induced by data heterogeneity. and (iii) stochasticity of the mini-batch gradients. The aforementioned drift of local momentums can be exploited by the adversaries to maliciously bias the aggregation output. Formally, we will control the growth of the drift A, between momentums, which we define as
Momentum drift. Along the trajectory 0o....,0,
A: = Amna
Σ (ml IEH
m² mm)(m - mme
(19)
[74|
where Amax denotes the maximum eigenvalue, and m, [R] Σien mi denotes the average honest momentum. We show in Lemma C.I below that the growth of the drift A, the momentums can be controlled by tuning the momentum coefficient H. The full proof can be found in Appendix C.6.2.
17

---

Towards Trustworthy Federated Learning with Untrusted Participants
Lemma C.I. Suppose that assumptions 2.2 and 2.3 hold. Consider Algorithm 1. For every E {0,..., T 1}, we have
03 108 (no + +nal (1+ + n ) + (1- (1-B))Ci
d
E E| 3 + + -.)²
where m [7]] EiEn my ( og == 2(1 t ) b and Go SuPaER" SuP SI [H] Eien (v, VL.( (LH(
The dimension factor due to correlated and uncorrelated noises is divided by n- f. which would not have been possible without leveraging the Gaussian nature of the noise. To do this, we use a concentration argument on the empirical covariance matrix of Gaussian random variables, stated in Lemma C.6. Moreover, the correlated noise magnitude o has multiplicative factor n, which essentially reflects the fact that correlated noise term is added per worker, for each worker. Finally, the remaining term 2o of the upper bound is only due to data heterogeneity, and also appears in Allouah et al. (2023c). Similar to the aforementioned work, an important distinction from Karimireddy et al. (2022) is that G is a tighter bound on heterogeneity, compared to G the bound on the average squared distance from Assumption 2.1. This is because the drift A, is not an average squared distance, but rather a bound on average squared distances of every projection on the unit ball. Controlling this quantity requires a covering argument (stated in Lemma C.4).
Momentum deviation. Next, we study the momentum deviation; i.e., the distance between the average honest momentum m. and the true gradient (0,, in an arbitrary step t. Specifically, we define momentum deviation to be
6e = m, V (0,)
(20)
Also, we introduce the error between the aggregate Rd and mi for the case. Specifically, when defining the error
[H] EiEn mf" the average momentum of honest workers
C == R m4.
(21)
we get the following bound on the momentum deviation in Lemma C.2. proof of which can be found in Appendix C.6.3.
Lemma C.2. Suppose that assumptions 2.2 and 2.3 hold and that Lix is T-smooth. Consider Algorithm 1. For all
t (O....,T- 13, we have
E 11 [1]
S (18 71 + 42 [10.1[]] + 44 mL) [VL2)
+ (1 - B,)² n
DP
+ 27x + 7L) B E [|ea|]]
where op (1 () of dfo + do ind
Above, the error due to the correlated noise scheme involves the noise magnitude oor but only multiplied by the number of malicious workers f. This essentially reflects the fact that all correlated noise terms cancel out upon averaging, except those shared with malicious workers, since the latter do not follow the protocol in the worst case.
Descent bound. Finally, we bound the progress made at each learning step in minimizing the loss L# using Algorithm 1, as in previous work in robust distributed optimization. From (18) and (17), we obtain that, for each step t, 6,41 = =,, - -% Rs = 0, - 7077 - (R, - m.), Furthermore, by (21), R² me. = 6t- Thus, for all t,
0,11 = 0 - m- - -/EEe-
(22)
This means that Algorithm can actually be treated as distributed SGD with a momentum term that is subject to perturbation proportional to G, at each step This perspective leads us to Lemma C.3, proof of which can be found in Appendix C.6.4.
Lemma C.3. Assume that Lu is L-smooth. Consider Algorithm 1. For any E [T], we have
E (Cx(011)) Cx(0,) <- Pt. (1- 4xcL) E
( [VCC((0)1]] + t 2 (1+ 2x E [16:11 + + (1 + 7cL) E [[tal]]]
Putting all of the previous lemmas together, we prove Theorem 4.2 Section C.3.
18

---

Towards Trustworthy Federated Learning with Untrusted Participants
C.3. Proof of Theorem 4.2
We recall the theorem statement below for convenience. We denote
inf (+). Lu Cu(6)) L, 240, 02 480, 03 5760, and a1 270. OERd
Theorem 4.2. Suppose that Assumptions
2.1, 2.2, and 2.3 hold, and that Cu L-smooth. Recall rs from (4.1). Let
of + d(So + md
0²
n
4x o + 108 (no + omd)) (1 n d )
where of = - 5 We also denote L. = inr (0), Lo Cx((0) L.. Consider Algorithm I with T 2 1.
the learning rates specified below, and momentum coefficients Bt = 24L The following holds: CH is p-strongly convex: 1f v(14240 5)
then
KG Cov
L L²
E (0T) -c.) + 112 12
2. CH is non-convex: If min
1
v32n
j.
then
21L
16
TTTLo
LLo T
E Le RG can
VT
where $ denotes inequality up to absolute constants and the expectation is the randomness of the algorithm.
We prove Theorem 4.2 in the strongly convex case in Section C.3.1, and in the non-convex case in Section C.3.2. These proofs follow along the lines of Allouah et al. (2023c), and we include them here for completeness.
C.3.1. STRONGLY CONVEX CASE
...,T - 1}. We set Proof. Let Assumption 2.2 hold and assume that LH is L-smooth and ju-ttrongly convex. Let L E (O...., the learning rate and momentum schedules to be
10
Vt
8i = - -4L
(23)
MLl + a1
where a1 == 240. Note that we have
10
1
71 S 70
(24)
p240 L
24L
To obtain the convergence result we define the Lyapunov function to be
2
(1) B [[cn(0)) - C. +
21 || +
22 Ao L
V1 = + a1
(25)
where 01 240, 21 Consider also the auxiliary sequence W, defined as
I6 and 22 2. Throughout the proof, we denote i = t + a 4.2 Therefore, we have
10
W, E (x.) L. 21 I
|10el
22 K.
A1
(26)
I.
Therefore, have
V4+1 Vi = (f+ 1) PW, = (f 1) (82 22 1)W, + +2f (1W,
= -(f+ 1)2 Wt) + (2f 1)W,
(27)
We now bound the quantity W++1 - We below.
19

---

Towards Trustworthy Federated Learning with Untrusted Participants
Invoking Lemma C.1. Upon substituting from Lemma C.I, we obtain
R 1+1
22
K.
22 L
A
K
52 [ + 2k L
22 2(1 (1- of + 108 (no + tnd)) (1 + n2 m
L
22 +
7, (1 B,) coo k
22 E [
(28)
I.
Invoking Lemma C.2. Upon substituting from Lemma C.2, we obtain
+ 2 (1 -3,2² T
21
|1 212
21
|
S 21 of EE
[1661P]] + 42176(1 + LL) E [VVxx
Dr
L
L
n2
21 + 76) E [Iail]]
21 EE [16a11]]
(29)
where we introduced the following quantity for simplicity
Ct = (1+ + TeL (1 + 47r4) = 1+ 5% + 432
(30)
Invoking Lemma C.3. Substituting from Lemma C.3, we obtain
E [Cu(0.+1) Cx((,)] - Tt (1 - 42L) E [VCn(())1]] + n (1 + 2xL) E [1[61|]] + (1 + xb) E [Ical]]]
2
(31)
Substituting from (28), (29) and (31) in (26), we obtain
W4+1 W2 E2 [CH (1(+1) Cx (0,) E
I || 1|
21 l1ó:1l"
I
+E
k-
22 A r+1 R.
L
22 _1
L
s Lt (1 4xxL) E [VCH ]]
+ 7 (1 + 2)x EE [[16|1[] + (1 +1++7 77eb) E [[|erl]]] 2]
2
+ 21 faa E [11611]] + 4222 (1 + L E || (0,)11
21 (1 - 3.)² Tp
+ L
L
n - f
+ 21 + 3. T. [||aa|]]
21 FF |16.11
+ k. 22 3 E A
B,)² oi + 108 (no + and) (1 + d
n - )
22 (1 -3,) cov
+ 2N I
I,
I
22 E [A]
- K
(32)
L
Upon rearranging the R.H.S. in (32) we obtain that
W411 - W₁ S
7t ((1
4x+ - 821 + xz))3))) E || | [[,)())
+ -
7 (1- 11--3p 1-))² Dr
2
n S
-1
1 (1+27eL)
1
8.
T.
1)
3[10,11" + 7 (1 + t 22 (1 + 12) E [Iee_l]]
7
21
22
E|) + 2xx
22 2 - 8.)²
oî + 108 (no + did)) (1
n m-,)) + k 22 (1 BB:)) G2oo
d
22
K
L
(33)
By Proposition 4.1, we can bound E ||eall 2 as follows. Starting from the definition of et, we have
||ee||== = Ra, m²ll2 CAF(m (1)
"............................... ...., .......(")) (()) me || < N Amax
1
(ml (6)
( mma)) -. A. mm)
7H
iEN
Then taking total expectations above gives the bound
E [[teal]]] S E [A.)
20

---

Towards Trustworthy Federated Learning with Untrusted Participants
Using the bound above in Equation (33), and then rearranging terms, yields
+ +. -11 o n f
W4+1- W "t ((1
41 - 81 + 3) E
V (+,)1)
2
-170
1
(1 + 2))L)
7 fl +
1
1
E [16b1]]]]] + mo (1 + + 201 (1 + (c)) E [Ar]
21
7cL)
22 (1 (,) E [A.] + 2n
22 (1 - B,)²
d og + 108 (no + Ima) (1+
n n- f ) + k.
22 (1 Br Be)
L
L
L
FB
't (11
L2 - 821 + 7/ L) 1) E [ 11 + 2/ (1 (1-3))²
2
n f
- (-2 (1+ 2),Li)
1
1) E [[0b11]]]
of + TLL)
217
21
7
1
1
R2271
(1 Bt)
(1 + + 221 (1 + )(b))
E [[a[]
7
22
+ 2K
22
(1 8,)²
oo + 108 2no mnd) (1+ + n --)) - 2 (1 3,) coo.
d
L
For simplicity, we define
1 (1 4.) - (8 + 1.
A
(34)
2
1
7cL B. + 1
1
B
(1+ 27(4)
(35)
21
7eLi
and
1 (1 - Be) -
1
C = 7LL
(1 + v + 221 (1 + +111)3
(36)
22
Denote also
a² ob d(Jo cor + +ind)
+ An og + 108 (no + +nda) (1+ + d
n )
n f
Recall that, as 21 16
and 22 = 2, and op = =0 + +d(fo2 + ouud). we have
0² 2 21 n f
DP
d 2x 22 og + 108 (nodor + oma) (1 n m-/))
Thus, substituting the above variables, we obtain
W411 W, < A E [|VCu(0)1]]] - By E [1661]]] K 2yChr E(A.]
1 (1-3,)20 3.)20² n- 22 (1 G2 + -
(37)
We now analyze below the terms A, B and C on the RHS of (37).
Term A. Recall from (24) that 7
1_ Upon using this in (34), and the facts that 21
1
and
33 < 1, obtain that
24I-
16
A h 1 - 4) (1 + L) 2
1
1
8
1
1
2
4
x
(1
>
(38)
2
24
16
24
10
Term B. Substituting from (30) in (35) we obtain that
1 (1 + 2)
_
1
1
B
32
(1 + + 122 +
21
7
I
1
1
(1- - BB)
(1+
++22 + 52 + 42 (8
I
21
21

---

Towards Trustworthy Federated Learning with Untrusted Participants
Using the facts that Bt S 1 and Yt
and then substituting =1
we obtain
247"
B (1 - -) - 16 (1
2
5
4
1
+
2
(1
23 2
(1
3c)
23 = 1.
(39)
24
16
24
x
16
%el
7/ I
where the last equality follows from the fact that -e 2.
Term C. Substituting ž1 I6. 22 2 in (36), and then using the facts that Br S 1 and
S
2II we obtain
1
(
1
C (1-3)
2 11+ (2x (6) +b))() 2 nat. (1 - Bc)
++
+
32 +
-
nT
2
24
24
1
7o B1) 18 6,
(40)
where the last equality follows from the fact that Combining terms A, B, and C. Finally, substituting from (38), (39), and (40) in (37) (and recalling that 22 2) we obtain
3e 1B I.
that
W41 - W.
Yt E [0))11 10
-21 [16611]] 6M227 TE [Ax)
1 3.)20² +
-.) 2
-1 G.)
(41)
1,
Since Lu is u-strongly convex, we have (Karimi al., 2016) for any 0 E IRd that
[0)l 2 2p(((0) L.).
(42)
Plugging (42) in (41) above, and then recalling that L 2 μs, yields
W411 W/ S
E ((,)))
f.] 21 [16.11]] 6K22 E [A,]
5
1
2 (1
(1 02)²0² k
Be) G2
L
L
pm
E [x((0) L. +
21
|1ô.11 + K
22 A
3,) + [ -1-3,))o (1-
1
2
5
|
1
147 E [n((0)) - L. +
#1
|| + n
22 A
+ (1- 31) + (1 - B. L
1
2
5
L
L
L
1 W. + 7 (1 101-3,)886 3,) + K. 2 (1- B, cov.
5
Upon plugging the above bound back in Equation (27), rearranging terms and substituting 1 1- = =24L;, we obtain
V4+1 14 1/
1)2
1 5
we W. + 7 - -.)-3²8222 +
2 - 11.333
+ +(2 1)W,
(i+ 1)²
2(i + 1)²
= =- (0 + 1)a 2?
-(2 + 1)] W. +
L (24Tr k
(24Thx
5
L
Recall however that 7/- = 10 as f = + #.. Recall that we denote a1 = 24 x 10 = 240. Substituting Y above yields
Ve+1 - V s (f+ 1)2 | 1h w, + 1 11 B,) K 2 -1-1))62
+ (2f + 1)W,
=- 2 (i 11 (2f (2++1) W, + of (1+ 1)2 0² + 2a,
(1+
G2 2000 ut
2222
Observe that 2 (f+1)² : > 22( > 2i + 1, implying that the first term above is negative:
(t 112 x² + 2aix (f+1) 1)2
V4 V, 5 a2 S0LL 11222
ul G2
22

---

Towards Trustworthy Federated Learning with Untrusted Participants
Observe now that, i + d1 4 d1 240 (because L 2 (c), we have (i+ 1)2 < (1 ) s 21². Plugging this bound in the inequality above gives
2a 4
Vi+1 V1
+
401k
Go
Therefore, we have for every & (O..... T 1 that
V++1 - 1== = Σ
(Vk+1 - V4) = [t+ (++1)
2a
g² +
i Σ h Amma
40
Go.w..
G
1²
k=0
Since Ek_ok k Ek ai = k aill + 1) = [(++1) + (t + 1) we obtain
V++1 10-- 1o= = Σ(V++ Vi)) s (t+1)
20
7² +
(((++))
ai (t + (1+1)
4a
G2
112
2
16 1
= (1+ 2a d² + (t ( ( +00 1.)
40
Goom.
n2
However, recalling the definition (25) of Vi, we obtain
+++1+ag a1 / L 3 2 (IH(((())))))))))))))))))1)))))) - c.l s V4+1 S Vo V (t
2a L
②² + (t (++1) ( +
L
401k
G2
2
By rearranging terms, and using the fact that
& d 2 1, then get
(1 (1+1) 20
+ a1
Vo
t ++1
4a1x G
E [[H((0(+1) 5.
+
ai
222
(1+1+ a
4222
122
+++ al 4/22
1
Vo
20
4aik P2om
+
+
(43)
(++1+
122
++1+
12
It remains bound Vo. By definition, we have
T.) ()) Vo a1 11
(Cu(0o) - L. 110011
22 L
Ao
By definition of Th
[म EieN m. and the initializations mn [ (m)) mo)
0 for all E H. we have Do =
Amax 1
m O. Therefore, we have
21 |l 2 (c((b)) - C.+ +
Vo = a1
L
Moreover, by definition of 5, in (20), we obtain that
|| Immo (cx(0,)11 -|VC<(()))]
Recall that CH is L-smooth. Thus, [0))11 & (0)) L*) (see (Nesterov et al., 2018), Theorem 2.1.5). Therefore, substituting 21 = 16+ we have
1.
1)² Vo < 01 ) (x)( - f.+ (xx(0)) (0)) - ca)) /1)
2L
L 2
4)² (CH(0,) L.)-
=5
a1 μ
(H(()) - L.) $ a1 11)
16L
8
23

---

Towards Trustworthy Federated Learning with Untrusted Participants
Plugging the above bound back in Equation (43), rearranging terms, and then recalling that 01 4 2 yields
401 f.]
Lo
(0,L2(CH(0)) L.) +²(++ 1 a1 422
E [CC((0+11)
xG
coo
++ k)
1
40
Lo
2a (a)L2(Cx(00)) -L.)
RG
k
coo
12 (t)
1 + +1²
Specializing the inequality above for T 1 and denoting Lu ((0)) L. proves the theorem:
4a
2a Lo²
20
E (OT)
f.l S
RG cov
+
+
1²T
1272
C.3.2. NON-CONVEX CASE
Proof. Let Assumption 2.2 hold and assume that Lx is L-smooth. Let E (O...., 13. momentum to constant as follows:
We set the learning rate and
1
VaLLo
== min
Be 3 == 1- 1-24L,
(44)
24L
27 /
where a1 == 240. Note that we have
1
7t = S
(45)
24L
To obtain the convergence result we define the Lyapunov function to be
V/2 = E [x((0.) - C. |bel
22 + L
A
(46)
where 21 and 22 = 2. Note that V, corresponds to the sequence W. defined in Equation (26), and analyzed in Appendix C.3.1 under the assumption that 7 I 245- Since the latter holds by Equation (45), we directly apply the bound obtained in Equation (41):
V4+1 - 1/
" E (0.)l - 21 E [15.11]] GN227% E [AA
10
1 (1 8,) + 2 G1
+
In turn, substituting ?t- 7,, = 33 and bounding the second and third terms on the RHS by zero, this implies that
V4+1 V4 < - E (0)11 1 - 3)20
(1-3)G22
By rearranging terms and then averaging over t (O....,T-- 1}, obtain
10 T-1 7T
Σ [[VIx>001111
<
(V. - V(+1) + 7L (1 3)20² + I.
10
-1-)
20
(1 B)G cou.
We now substitute B = 1 24 Denoting d3
10 x 24 = 5760, 02 = 20 x 24 = 480, we obtain
10 T-1 7
(V. V(+1) (10 x 24
(>L) + (20 x 24)
E
[VC)(0))1
<
Σ
G c00
7h
7T.
1=1
10
(Vo Vvr) + Lo az cor.
(47)
7T
24

---

Towards Trustworthy Federated Learning with Untrusted Participants
We now bound Vo- Vr. First recall that Vr
of non-negative terms (see (46)). Therefore, have
Vo VT S Vo = (+((0) L. +
21
| +
Ao-
L
L
By definition of mh
[7] EiEn mi and the initializations my = for all E H, we have Do = (6) mo) ma)
1
(4)
Amax [ि] Eme
0. Therefore, have
Vo (x(0)) L. + 21 11011
L
Moreover, by definition of 6, in (20), we obtain that
||6e1|
ma (0, ( [[
Recall that LH is T-smooth. Thus, [[ & (1( L*) (see (Nesterov et al., 2018), Theorem 2.1.5).
Therefore, substituting 21 = 16. we have
2L
9 (LH(00)) - (cx(0)))) -Lx).
Vo- VT < Vo (0)) - -.
16T.
By plugging this bound back in (47), and denoting 04 = 24 10 (3) 270 and Lu == Cxe C.,, we obtain
10 x (2)
E (0,)11
5 7T
(CH(0g) -L.) L37 + agn
T
a1Co
L0 +aznGeov
(48)
247T
Recall that by definition
1
VagLa Co
7 min
24T.' 20 V
and thus max 24L,
J VazLT S 24L + Vaslo
2
σ VayLT. Therefore, we have
Vasto
a4Co
asLo
2
agLLo
VayagLLoo
24L
JV LzLT
24-T
24T
vagLo
T
12VT
Upon using the above, and that y S
20 in (48), we obtain that
Vaska
T-1 Σ
aaLLo
VazuaLLoo
Vagua LLno + a2kG2 S azkG2 + VazashLoo as
E [VLx(0)))]]
T
T
12vT
2vT
VT
T
E=
Finally, recall from Algorithm 1 that i is chosen randomly from the set of parameter vectors (fo...,,0, 0r-1). Thus,
CC 0 (0)
E
+ - E [[)01()))] Substituting this above proves the theorem.
C.4. Proof of Corollary 4.1
We now state the proof of Corollary 4.1 below.
Corollary 4.1. Let 8 E (0, 1),e e (0, log(1/))) and (2 + n) for some absolute constant 1j > 0. Con- wog then Algorithm I sider Algorithm in the strongly convex setting of Theorem 4.2. If o2 aid = (n( is (E,5) 8)-eeLDD against
server colluding with all malicious workers, and (f. robbust where O (J+1)C* IC² |C" log(1/6) (.Ge..) ). asymptotically in T and ignoring absolute constants.
n²
25

---

Towards Trustworthy Federated Learning with Untrusted Participants
Proof. The privacy claim follows directly from Theorem 4.1, given the choice of oe = dnd 32C log (1/6) 69(n-))
We now prove the utility claim. First, we recall that n - f 2 n/2 since f < n/22, and x. is bounded by 4 when n 2 (2 + f) > O, by Proposition 4.1. Plugging the expressions of and and d in the strongly convex bound of Theorem 4.2 and rearranging terms yields
n up to a constant
KG
L
LZ 12222
E (Cx( c.] 00
11
HºT
K.
L
oe + d(foeor + dudd)
}
LZ N2T2
o
now
+
+ oh + (no + tma) (1
f
4²T
n n-
fGene
(odlog(1/0)
f+1 +
C² log((1/))
f oh
f f+1
Lo
= =0
nu
82n
n
82
T
p2T
We conclude by ignoring asymptotically vanishing terms in T.
C.5. Privacy-Utility Trade-off for Standard Aggregation Methods
We now analyze the privacy-utility trade-off of CAFCOR when using standard aggregation methods instead of CAF and present the corresponding proof below. Specifically, under the same setting as Corollary 4.1, but replacing CAF in Algorithm I with the moordinate-wise trimmed mean (proven order-optimal under the weaker robustness criterion of Allouah al. (2023a))), we obtain (f, -roobustnnsss with
e e-o [ (1 (odlog(1/0) C9dlog(1/8) $ dG cov
+
+
g2
n²=²
asymptotically in T' and ignoring absolute constants.
Proof. When using moordinate-wist trimmed mean, have weaker robustness guarantee than Proposition 4.1. Essentially, can prove the latter but with the right-hand side of the inequality involving the trace instead of the maximum eigenvalue (of the empirical covariance of honest inputs), shown by Allouah et al. (2023a). Therefore, the only change in the convergence analysis occurs in Lemma C.I, which would instead involve the trace operator instead of the maximum eigenvalue operator. Formally, denoting
A = Tr
1 H
(m,
(m) me)
( m
m
(49)
icH
EE
we would have
b++1
3r E
A
+ - 3.) (0 - + 3d (no + mmd))) + (1 - B.)
reusing the same notation as Lemma C. Therefore, leaving all other lemmas unchanged for the proof of Theorem 4.2, we would obtain the statement as the latter except that the expression of a from Theorem 4.2 would become
of d(Socor +oud)) + 4m (o) + 3d (no + oiud)) n We now follow the same steps as in the proof of Corollary 4.1. First, we recall that n 2 (2 + r)) for some constant value so that k is bounded by f/n up to constants. Plugging the expressions of ond and o in the strongly convex bound of Theorem 4.2 and rearranging terms yields
kdG2 cov
L
bZLo
E (Q)( L.] = O
P RdG2
12T
+
12T2
o
caN
T
of + +dffoa + roal
n-f + k (ot + d (no + +ozul))
L.2
1
12T
12772
fdCCor cov
C²dlog(1/0)
s+1 C2dlog(1/0) e2n
of
f+1
L²LLo
ni
n
E2
n
n
11272
[dlCoo
C2dlog(1/8) C²dlog(1/8)) 22
of
f [+1
L.2
0
nj
e2n²
n
T
7
p2T2
26

---

Towards Trustworthy Federated Learning with Untrusted Participants
We conclude by ignoring asymptotically vanishing terms in T and rearranging terms.
C.6. Proof of Supporting Lemmas
Before proving Lemmas C.I to C.3 Appendices C.6.2 to C.6.4, respectively, we first present some additional results in Appendix C. below. Most of the proofs follow along the lines of Allouah et al. (2023c), and we include them here for completeness.
C. TECHNICAL LEMMAS
Lemma C.4. Let M E Raxd be a random real symmetric matrix and IR - R an increasing increisingfuunction It holds that
sup g((e, Mul)) S $9 sup
E
[20 Mo)]]
|S
|
Proof. Let M E Raxd be a random real symmetric matrix and g: R + R a increasing function.
The proof follows the construction of (Section 5.2, (Vershynin, 2010)). Recall from standard covering net results (Vershynin, 2010) that we can construct Niya a finite 1/4-net the unit ball, i.e., for any vector in the unit ball, there exists u, E Naya such that [|u, ell I 1/4. Moreover, we have the bound [Wi/a| & (1+2/(1/4)) = gd. Denote by [[ == sup Io || Me the operator norm of M. By recalling that M is symmetric, we obtain for any e in the unit ball
Ke, Mu) (Wus Muv)l (00 Up. M(v u,))i - ||e uell [ u.)ll S (Ilell + (| [IM uw)l
S 2 uz)) s 2 M| ||0- u., < || /4 = ||
Therefore, we have (v, MD) - (uy, Mu.) < |M| || /2, and (v, MM)- - || || / S (wv, Mu.) S suppeNa, (u, Mu). Recall that since M is symmetric, its operator norm coincides with its maximum eigenvalue: ||M]]| = suppoalss (0, Mv). We therefore deduce that
sup (u, Mu) 2 sup |el|l
Mb).
"ENipa
Upon composing with g, which is increasing, we get
sup ((, Mo)) sup (u, Mu) S
2 sup (v, Mo) vENi,a
sup g(2 (v, Mu)). vENi,s
sells
Upon taking expectations and applying union bound, we finally conclude
sup g(2 (v. Mul) s Wiyal sup vENiys
E sup g((u. Mo))
E
[lg(2(v, Mb))] < 9d sup E[g(2 (e, Mu))] [| s1
wENiys
Lemma C.5. Suppose assumptions 2.2 and 2.3 hold. For any E {O...., - 1} and E H. we have
E 10 -
- <2 22(1-11
b o²
d or.
m
T 17. Proof. Suppose assumptions 2.2 and 2.3 hold. Let E H and E {0,... T
First recall from (16) that, since gfth = gt
+ c
(0) iid. N/(0, Ta), we have
St.
|11
E
Dt
= E (9 = d d.o.p.
27

---

Towards Trustworthy Federated Learning with Untrusted Participants
Next, we have
b - v..(0.)) =
- |
(6)
(1)
(0.) 2
|
9t
+ 9t
-1 0 gt
(1)
(4)
2
(
vL,(0,) || + +2(01 -60h ot
V..(0.)).
+
gt
Now taking expectation on the randomness of (independent of all other random variables), and since E [((0]
0. we
get
9r
(1) -R
(0,(
12]
(1)
9t
(0) 27
-VL(0)))
||
2 +2
E E.
9t
(3)
9t
(8)
91
(
(..
=B
[ =0
(0)
0:00 10]
-
E
(a
9t
+
Upon taking total expectation, we obtain
E
1 - vC.(0:11
= (1)
91
(1)
+E 1i - vc.(0,))
= E
(6 - vC(
- +d. d. .d..r.
(50)
First observe that when m = 1. as b E [m], we must have = m. Thus, the gradient is deterministic, i.c. g! = (L,) Thus, the first term in the equation above is zero, and the claimed bound holds.
Else, when m 2 2, recall that from Assumption 2.2, we have EL)L(D) 2006), the variance reduction due to subsampling without replacement gives
- S 0². From (Rice,
v.. $ (1 11- m7
o² b
-c,00
E
Plugging this bound back in Equation (50) yields
of - v<((0)))])
b
E
5 1 m 1
+ d ob.
b
By observing, as m 2 2, that
6-1 m-1
m-b
mmb
(1+ + m-
)[
b s 2(1
b) ). we obtain the final result:
m
m
m
E (
VL:(0>>11) 52 22(11= =2
b o²
+ d o...
m
Lemma C.6. Let ODP 2 0 and d, n 2 1. Consider (()) ,...,...h distribution ((0, Ia)). We have
g(()) to he i.i.d. random variables drawn from the Gaussian
d S 360 (1 (1+ + d) U. {(0))
E
sup |
72
n
Proof. Let 2 and d, 2 1. Consider (()) AO aa))
(() to be i.i.d. random variables drawn from the Gaussian distribution
If ODP = 0, then g()) = almost surely for every i E [m], and the remainder of the proof holds with oDp = 0. Else, we assume ppr in the remaining.
28

---

Towards Trustworthy Federated Learning with Untrusted Participants
Thus, the law of the random variable /<De is (0, Ia) for every E [n]. Thus, for every vector in the unit ball, the random variable (v, < /"/or) is sub-Gaussian with variance equal to (see Chapter I, (Rigollet & Hütter, 2015)). Therefore, for every E [ni] and every vector in the unit ball, applying Theorem 2.1.1 in (Pauwels, 2020)), we have
] 2.
(u, 5 /onn)
E
exp
8
As result, by the independence of g(0)s, we obtain
v, <(10)=]]
1 (v, /oo0))))))) $
sup 1
E
exp
II exp [oll $1
sup
80
1=1
Now, observe that write Ei= (v, g
as the quadratic form (v, MD), where M == Σリ 5(0) g(1) is random
real symmetric matrix. Thus, applying Lemma C.4 with the increasing function g(-) = exp 160 x )) we have
E
sup exp sills1
Σ
Us {(1)) 2
E
sup I(u, Mo}) -lllls1
S gd sup
[0 (v, Mu))]
Br
1
U. ((1)
9d
- 9d
sup
exp
S
We this inequality to bound the term of interest. We apply Jensen's inequality thanks exp being convex, and also interchange exp and sup thanks to the former being increasing:
Ur g(())
)
exp
E
sup ||||
S E
exp
sup |
16
16
i=1
= E
sup
exp
1. 5(1)
1 gd 22
|e
160 DP
Upon taking and multiplying by B6/ /n on both sides, we obtain that
(, 5a))
)
< 16 or (dhn 1ln9+nh2) s 36 (d (d+n) = =360
TD
(1+ m
sup [ n i=1
n
The above concludes the lemma.
C.6.2. PROOF OF LEMMA C.1
Lemma C.1. Suppose that assumptions 2.2 and 2.3 hold. Consider Algorithm For every t t0...., T 1}, we have
d n - + (1-83)G2
E [| SBEA, + -3)2 o8 108 (no +uaa) (1+
[H] EiEn my of 2(1 b ) and G2.v. == supøers sup [R] ΣiEn (v, VL, (L)(
(3)
where m.
Proof. Let t E (0, (O...., . T 1). Suppose that Assumption 2.2 holds. Recall that the alternate definition of maximum eigenvalue implies, following the definition of A, in Equation (19), that
A Amax
Σ (m) mm)(m)) (9) (mmmmm"mm)]]])) NEH
me)" )
sup [
U. m mm
176
We will use the latter expression above for A, throughout this lemma.
29

---

Towards Trustworthy Federated Learning with Untrusted Participants
For every i H. by definition of m (9) given in Equation (15), we have
mi+1 Sem, (8) + (1 - 31)
(0)
We also denote m, == [ EiEN m and 94+1 = [7 EiEn g Therefore, we have M441 3.m, + (1 B,)gg-1. As a result, we can write for every E H
M++1 = Bi(mi (8) - -m&) + (1 - -1)00 - -
1+1
= B. (8) - -m,) + (1 - (V ([H((0++1))
+ (1 (-) (6) VL,(0.+1) - Te+1 + VLx (0++1))))))
By projecting the above expression arbitrary vector e and then taking squares, obtain
(0, m1+1 me+1) )² = Be ( pr m m. (1 31) (w. VL,(0++1) VLH(0(+1))
(8)
+ (1 - B₂) U 9++1
(2)
(0,(0(+1) 94t1 VCH(((+1)) ]²
= 3/ (1, U, m
(8)
m:
+ (1 - (1=)))² (v, VL,(0+1) - VCH(00+1))
+ (1 - B.)
6, 96+1 (0,(0++1 - -it4 - VCH(O++1)) 2
(6)
+ +1, B.) (1, m
(1) - m. (v. VL,(0++1) (LH(0(+1))
+ 23:(1 - B.) U, mi
1 - VLi(0++1) - D.+1 + VLLx(0++1)) 6.) (v, (L,(0(+1) - (Cx((0=+)) (e, (10) VL,(0++1) - - + (Lr((0+11).
(1) - mR (u, (1,
+ 23: - 3:)
Upon averaging over i H. taking the supremum over the unit ball, and then total expectations, we get
27 // = =
2
)
E
sup [
0, m+1 me+1)
sup
Tha U. ml
171
||
17
iEH
iEH
sup + (1 3
(v, VL:(0++1) (LH(O++1))
H
||v] 11
iEM
+ (1 E
(6) (.,(0.+11 Jet1 + VLH(0+n1))
sup
v, 96+1
[7|
||o|
iEA
+ 21 - B,) E
sup
U. m
(4)
mr (v, VL.(0(+1) ([x((((+1))
||
H
NEH
+ +1 - B
sup
U, my
(2)
The
(v, (0) (L.(0(+1)- - -Je41 + Vlzx((et1))
H7
||
iEH
(v, (L.(0+1)) V (u, (0) VL,(0.+1) Dot1 + (EalOrtn)
+ 21 - B
sup
H
||
NEH
(51)
We now show that the last two terms on the RHS of Equation (51) are non-positive. We show it for the first one, as the second one can be shown to be non-positive in the same way.
First, note that we can write the inner expression as a quadratic form. Precisely, we have for any vector v and any i e H. that
2
U. ml (4)
m. (v,
9
(()
(.,(0(41) Iitz + VLC((0+1)) (v, Mv).
K
30

---

Towards Trustworthy Federated Learning with Untrusted Participants
where we have introduced the d x d matrix M == N + NT, such that = EiEn (m) mn m² ) VL.(0++1)
9e+1 + VLu(((+1)) By observing that M is symmetric, we can apply Lemma C.4 with being the identity mapping:
B sup 2
Σ
(0) (u, mi my/ v Dit1 VL,(0++1) 9441 + VL VLx(0++1))
=B E
sup (u, [1el S1
Mo)
|| iEN
gd sup E (c, Me)]. (52)
|elll
However, the last term is zero by the total law of expectation. Indeed, recall that stochastic gradients are unbiased (Assumption 2.2) and that 0++1 and m! (6) deterministic when given history Pi+1- This gives
E (o, Mu)] = E
m
(1)
Me)
VL,(0++1) - - + vCn(0 U. 9--1
iEH
E
Ex+1
v, mi
(8) mi
(u, 064 VL,(0(+1) - - + VVx((e+1))
iEH
E+t1 Met1 - VCn((etai] /
E
U,
m
(1)
ml)
v, Et+1
ge+1
vL.(0++1)
EH
-0
Moreover, going back to Equation (52), we obtain
sup 1
0, m
m. v, 9it1 (0+(0++)) -r- - + VLx(O++1))
S gd.
sup li
E E2 Md)] = O.
iEW
As mentioned previously, we can prove in the same way that
sup 2 Σ (v, (4,(0)41) (Lz(((++1)) (u.
V2,(6.+1) - Jet1 + VEr((ee1)) 50. 0 (u.0111
E
| iEH
Plugging the two previous bounds back in Equation (51), we have thus proved that
me+1) )9/ )
2
E
sup
m
S
sup
m
m&
[71
||
|7
iEH
iCH
(1 B.)2 F
(u, VL.(0++1) (L++t(+)))
sup [|v| SI
17||
iEH
+ (1 E
sup [|v| $1
(v, 9e11 vL,(6.+1) 3et1 + VCx((1+1))
H
iEH
+ 23x - Bc) E
sup
U, m - -mi) (v, VL,(0++1) -
(53)
||
|H|
iCH
We now bound the two last terms on the RHS of Equation (53).
First, by using the fact that 2ab S a² + b2, we have for any vector o that
2
U.
m
(3)
Ti
(c,
(L,(0(+1) v Cx <
v. m, mi, )² + (v, VC,(0+1) -aaaa)))-CA..) ((+()(+1))
(1)
H
H
iEW
c, m
(3)
+ H
(0,
(L,(0
(0((++11)
(54)
77
31

---

Towards Trustworthy Federated Learning with Untrusted Participants
Taking the supremum over the unit ball and then total expectations both sides yields
E
sup
U,
m4
(8)
ml) (c, VL,(0--1) - (Lu(((+1))
||
[H.]
EEH
I E
sup
1
U, mi
(4)
mc) )²
+E
sup
(u, (L,(041) -VC()e)))) (55)
17
|
[H]
icH
Second, recall that Ti41 = 92+1
<
where we denote S4+1
Σi= (3f) o+1 + off where Jhf ~ NN on and
e++ 2 -N( oenr Ia). Denote Eet1 = [7] EiEn Set1-
(9)) (88)
Therefore, by applying Jensen's inequality, we have
E
sup
1
U, 96+1
(4)
VL,(0142)) - (Lx(0t+))) 2
[
||o|
1
(6)
VL,(0++1) 92+1 VLz(0(+11) + 5(1) - -Bets) )
EE
sup
[76
[|vl] $1
EN
S 2
sup
U/ 91+1 - (L.(0++1) - De+1 + VLH + (1, cl0) - EEt1)
(8)
||
H
NEH
Recall the following bias- decomposition: for any ......
... In Σ - x². Applying this fact above yields
IR denoting T 1 " E. Di. we have a Ei (x:
7)2 =
Σ
=²
E
sup ||||/|
1
U. 9:41
(0)
(L((((+1)) - + (Lx((++1))
17
SEH
vC((A+1)) + +u,, sit1) |1]
< 2
sup
Σ
S [74
iE7
1
e(i) 12) S1+1
< 2
+2E
sup [|vi|
(56)
[
H
icHt
iE7
where the last inequality is due to the Cauchy-Schwards inequality. Recall that, by Assumption 2.2 and Lemma C.5 applied with zero privacy noise, we have for every i E H that o averaging over i H. have
2
V..(0++))
$ 2
b 2 = =o6- Therefore, upon
m
E
g
sof.
(57)
i
32

---

Towards Trustworthy Federated Learning with Untrusted Participants
We now bound the remaining (last) term on the RHS of (56).
2
2)
(9)
(8)
(81) v U(+1 + U =ltt)
E
sup |
S141)
E sup |
241 + 1111
E
sup
H
H
|
HH
NEH
iE
j=1
SEH
= E sup || HH|
U, Ui+1/
(i5)
2
+ (0, v(1)
11+1/ )
+ 2 Σ
1111
(15)
(u,
0+1
+ 2 Σ { w (c. v
1=1
1=1
j
k k
S E sup
[7|
Σ iEN
Σ
m
U,
(15) 2 11+1/
/
+ (v, m11 )2
|
+ 2E sup
Σ
Σ
U.
u
(t))
(1) U,
+
Σ
c,
(44)
(u, ((t)))
E
We observe that the second term above is non non-positive we have shown for (52) using Lemma C.4 and the fact that for fixed E H. all the noise terms in <(i) are statistically independent and are zero in expectation. Therefore, we have from above that
E
sup |
17
Σ
(0) S6+1
(2)
<
E
|
sup
HH
Σ
(1) 2 v: 1141
/
+ 1, Btt1)
2
IEH
j=1 +
We observe here, since ui+1 = -0(+1 for all i,j E H. that Eich 23=1
(if)
(6))
(tf)) (i,11
(6)) 2 = Eiihh EsEric (u,
u + (65))2
Eien Exelmine (, 4411 = 2 Eien Ejenses (v, //+1/ + +iiE Ejetniie (1,) 2
(1)) 2
(t)) 2
Therefore, we have
(1) 22 e, S1+1) )
E
sup
< E sup
Σ
2
U. ut41
(1)
U. Uit1]
(1))
+
+( (b,
(1)
||0|| <1
H
110
[71|
iEW
JEH
jEINJiH H
JCL
x 2E sup
|
HH|
1
Σ
IEH
Σ
U.
Ut+1
(8)) 2
+ E
|
sup
H.
Σ
EEN J
v, 1/ti
(159) 2
2
+ E sup
U.
12t1)
|
H
iEH
Now, for each of the three suprema in the right-hand side above, all random variables involved are independent Gaussians
33

---

Towards Trustworthy Federated Learning with Untrusted Participants
with respective variances, so that applying Lemma C.6 separately for each of the three suprema yields:
E
sup S1
(+) c
2 S1+1
>
S 21 sup
v,
(6)) u241
+ E
sup |
Σ
(v, (())
7
I
176
H
iEH
sE JEH J3
iEH jE(n]
1
2
+ E sup
[71
|
iEN
2
[H| (1+)
1)
2d
S 36
o (1
H.
2
[7]] (1H1 1)
|7|| (n
|71
2d
+ 36
oor (1 +
+ 360 2
(1+
+
[
2
[ (n - |71
[H
=36(n- f
3d
d
1)0 (1 (1+
360 ind (1 +
n1
71
< 108 (no + mnd (1 +
(58)
Plugging the bounds obtained in (57) and (58) back in (56), get
E
sup 1
c, (6)
V2,(0.+1) - Je+1 + VLH(OeH1)) 22 oh + 108 (no + thia)
(1+ d
n -+==1/))
H
iEH
(59)
We use the above bounds in (55) and (59) to bound the RHS of (53), which yields
E
sup |0
1
U,
m
(
m4+1)
B
sup ||
U. m (6)
-m+)
2
H
H
iCH
KEH
0 + 108 (no + ohal (1+ d
) n2
+ (1 - -1-
sup
(u, (L((0++1) VLH
+ 2 - B))²
|vils1
[7.|
iEH
+ 9,(1 - (3)) B.) EE
sup ||v|i1
v. m
(4)
+ sup
Σ iCH
(u, VL,(0.+1) - VCx(0<1))
[76
|
|7|
iEH
By rearranging terms, and noticing that 18 + Bc(1 3c)
3r and (1 B,)2 + B₂ B.) = 8e, obtain
1
12)
1
E
|0l|11
sup
H
U.
m
Mc+1)
< B E
|
sup
H
m m
NEH
iEH
+ B,,3 (03 108 (no + omal (1+ d
))
+ (1 B.) E
sup
Σ (v. (L.(0++1) (LH S
n
||
Denote G2 supperd sup
1 [A| Eien (v, VL.(0)- (0))) Then, the above bound implies
U1 m Th++1) )
U m - mie 2 )
E
sup |||||S|
(2)
S S
sup
H
[||||
H7
NEW
iEZ
+ + - 2) (oā
108 (no + +iud) (1+ n (++mn)) 21))
+ +(1 - +11 -B))
The above inequality concludes the proof.
34

---

Towards Trustworthy Federated Learning with Untrusted Participants
C.6.3. PROOF OF LEMMA C.2 Lemma C.2. Suppose that assumptions 2.2 and 2.3 hold and that Lx is L-smooth. Consider Algorithm 1. For all
e {O..... T 1}, we have
E [16++ 11²]
s (1 (1 + 47,4) E [16.12] + 44 nL) B [VLx((0)1
DP
+ (1 B,)
n n 21 + 1) E [|a|1"]
where Tp == (1- )m)
o² bo ofo + do
Proof. Let &. T 1}. Suppose that assumptions 2.2 and 2.3 hold and that La is T-smooth.
Recall from (20) that
8 := Ma+1 VLH (0++1).
1 Denote T. = [H] EiEn a.a Substituting from (15) and recalling that mi4 THT Eien m we obtain
8141 3r Tu + (1 Be) De+1 VLH (0++1).
Upon adding and subtracting 3, (O,) and Be CH on the R.H.S. above we obtain that
8(+1 = B4 mi 33 (L, + (1 -1- 8 B.) 91+1 VLH (0++1) + +
- C.((01)
-e (TT.. (0,)) + (1 3.) Ō (1 -1- (0+42) + 3. -VCx))))VVVV VL+((0+1))
As m (l,) = d, (by (20)), from above we obtain that
8,+1 = B,b, + (1 3..) (0et1 VLn (0..1) + 3o (VLu(0,) (cx(0++1))
Therefore,
||6++1| 2 = 110e11 + (1- - B,) [0t11 - VLH (²
+ + (O,) - (L + 2.3 -Ba) 6c, 9r41 VLH (0++1)
+ 233 (5., (0,, - VLH(00+11) + + - -3,) (ācH1 - vLH (0 (LH(0)) ((((0)+)))
By taking conditional expectation E++1 [-] on both sides, and recalling that de, 0441 and 0, are deterministic values when the history P4t1 is given, we obtain that
E+11 [10 =3? || + (1 - E 5e+1 - VCH (0.-1) 1| 11] + +38 [[C(((0)) - VLH(0++2)]1
23,(1 - -B)) (Be, Es+1 9e+1
- VLn (0++1) + 233 (6,, vCx(0,) (CH((++1))
+ 21 - 3c) (Be+1
Do+1
- V L (0++1), (LH - VLH(O==1))
Recall that Te+1 = - EjEn D:41 Thus, we ignore clipping by Assumption 2.3, we have Est1 _ [1+1
(L)(e.)) Using this above we obtain that
=3? 12 + (1 3.) | VLH (0 (0-))]]] + (L,(O)) (LH(0++2)1
E [10e+1
+,,8% (8., (O,) vCH(O++1))
35

---

Towards Trustworthy Federated Learning with Untrusted Participants
Also, we bound the expected distance between the average of full honest gradients and the average of mini-batch gradients with additive correlated noise. We first write
G1+1
|74|
1
94+1
(
Σ
1+1
(6)
141
(0)
[H|
Σ
9i+1
+
|7||
(3)
|7||
1
i+1
(
iEH
j=1
EH
i
iEH
1
(6)
Σ
(1) 1+1
=
H
91+1
H
+
H
S
41
KCH
JE
KEH
We remark that the second term is zero by construction of the correlated noise terms, while all remaining random variables in the third and fourth terms are independently sampled from centered Gaussians with covariance dear la and la- We directly deduce the following:
B 91+1 VLH (0c+1)
=E
HH
1
Σ
1 ---1
VLH (0c+1)+
+ [H1|
1 iEN jEin]|H
Σ
H
U+1
i
SEH
iE
2
E
HHL
91 - VLH (0.+1)
+
H7]
Σ
0+1
S
7
1+1
iEH
iEN jEin]
BE
df - Mo
do Ind
E
HH|
9t-1
(3)
V (01+1)
(n f)²
n
iEH
2
b
a²
df
o
cur
do
<
n
m
n1
n
where the last step is due to Lemma C.5 thanks to assumptions 2.2 and 2.3. Now, denote ThP = 2 (1- (h) a + ofo + do .nd Thus, we have
Es+1 [10 S 11011 +1 3,)² or (n- f) + 8/ [LH(00)) - VCH((0+1)] +28? (6., (LH(0,) - VCH
By the Cauchy-Schwartz inequality, <ōc, (0,) (0 < ||+.|| (O,) (0+ Since Lu
is L-smooth, we have ([,,)( - VLH 10++1)) || I L 11 - 0.|1- Recall from (18) that 0.11 B₂ -2RRt.
TTu())) - (Lx S n Rell Using this above we obtain that
Dp
Ex+1 |10e-1
< B |1 3 9,)²
+ 12 + 2 [1-01 [Rell-
(n
As 2ab S a² + +b, from above we obtain that
Ee+1 [16c+111]]
s 38 || + (1 - -1-)))² (n-f) f) + + ||ee| + L8L (18.11+ + [|Ba(1²)
DP
=1 L) || + (1 - 32)
(n- + T111 [1(1 + 3) || 12
(60)
By definition of e, in (21), we have R2 - c, + m,, Thus, owing to the triangle inequality and the fact that 2ab < <a² + 1²2
we have || < 2 || + 2 | 1 Similarly, by defimition of o in (20), we have ||m, < 2 1|&d1l + 2 || [Lx(0)))
Thus, || < 2 3|e,_11 + 4 || + 4 ((, Using this in (60) we obtain that
s (1 + L)3 [1&611 + (1 (1-10 (1-8))2 Fhr +
||6+111 [|]
E,1
(n - f)
+ (1 LL)3 (Ileal +2 (|eal2+211// 110.011 2 21V(2((0)11²)
36

---

Towards Trustworthy Federated Learning with Untrusted Participants
By rearranging the terms on the R.H.S., we get
+ +(1 (11-10 B,)² Tp
E++1 |1 [2]
18f 72) (1 + 4%) || +
(n (n-f) f)
+ L1 + 71 L)33 ||,11
The proof concludes upon taking total expectation on both sides.
C.6.4. PROOF OF LEMMA C.3
Lemma C.3. Assume that Lyt is L-smooth. Consider Algorithm 1. For any E [T}, we have
E [Cx(00+1)) - Cx(00) S It (1 (1- 4x (1C 7/ (1 (1+ 27x E |1..10 + (1+ mL) [|eall"]
2
Proof. Lett {O..... - - 13. Assuming Lx is L-smooth, have (see Lemma 1.2.3 (Nesterov et al., 2018))
(x(0(+1) (0,) S (0.+1 - 0,, VLx( + 2 110++1- - 0.l1
Substituting from (22), i.e., 8,41 =0,- - m, TeeE, obtain that
- - (Tie (L,) (e,, (Ln( + ne - 2 me + eil?
-M (TT - [ VO,, VLH(O,) - 7a (e., vLH(O,) + | mh + 2zl2
By Definition (20), Tī. - (0,) = 6,. Thus, from above we obtain
1 2222 (x((0+1) (z((0, - Y V (0.)l1 na (6e, VLH(0.)) - To (q,, (L,( +
L m + call. (61)
Now, we consider the last three terms on the R.H.S. separately. Using Cauchy-Sehward inequality, and the fact that 2ab s La cb² for any e > O, we obtain that (by substituting c= 2)
2 Ko,, VLH(0,)) s 2 (()6 < 2 ||,,11 + [L,
(62)
Similarly,
2 (ec, VLH(0,)) < 2 eel (Lx - 2 Neel + [L)(1)
(63)
Finally, using triangle inequality and the fact that 2ab - a² + b² we have
m, <=|1² < 2 ||ml 2 2 2||ee||2 ||m. (LH(0(+1)+ (LH(0,))1 2||ee|1
< ||ō_| 2| + 4 V (0,) + 2 1l [since m. - LL. = [c]
(64)
Substituting from (62), (63) and (64) in (61) we obtain that
1
+ 1 /0 (21|cal12 1 [VCx(0)11) 22118112 +
2 + 1 [VCx(00112
Cx(0++1) - Lx(0,) < n IVV
2 %
2 2 L L ( || +4 ((,)) +
+ 21lcal1))
+
Upon rearranging the terms in the R.H.S., we obtain that
(x(0)41)-4a)) - < Ht (1 - 4n: (VH + (1 2xx4) [|61|1 + (1 + 7eL) ||=a||
2
This concludes the proof.
37

---

Towards Trustworthy Federated Learning with Untrusted Participants
D. Additional Experimental Results
this section, we provide additional results that were not included in the main paper due to space constraints. Appendix D. contains the complete of results for the evaluation CAFCOR across the four privacy threat models, under all four attack types, and for both values of 5, 10, on the MNIST and Fashion-MNIST datasets. Additionally, Appendix D.2 presents the full results comparing CAF with other robust aggregation methods under all four attack types, across various values of data heterogeneity settings, and both MNIST and Fashion-MNIST.
D.1. CAFCOR Under Three Privacy Threat Models
1.00
1.00
Test accuracy
DSGD CDP
CAPCOR COP
Test accuracy
DSG3 CDP
CAROR CDP
0.75
D5GD ScCLOP
0.75
0560 SeCLDP
CAFSON SWILEM
CAFCDR- SWLLPP
05GD ByZLOP
DSCO SyrlDP
0.50
0.50
ByZLOP
0.25
0.25
0.00
0.00
5
15
20
30
10
20
25
30
Iteration
Iteration
(a)
(b) SF
1.00
1.00
Test accuracy
Test accuracy
CARCO CDe
DSGI-CD
0.75
05GD CDP
0.75
1503-Se:LDP SecLDD
CAPCOR COP
CAROR DP
0.50
CAPCOR Sec
D5GD SeILD*
0.50
0560 SydLDP
GMCDR- By
050D ByaLD*
DECO LDP
0.25
CANCOR BycLDe
0.25
CAFCOR-INP
IDe
CARCOR
0.00
0.00
5
15
20
25
30
10
20
25
30
Iteration
Iteration
POE
(d) ALIE
Figure 3: Comparison of CAFCOR and DSGD under four privacy threat models MNIST. There are 100 workers, including f = 5 malicious workers executing four attacks. A homogeneous data distribution is considered among honest workers. User-level DP is used and the aggregate privacy budget is (e, 6) = (27.8, 10-4).
38

---

Towards Trustworthy Federated Learning with Untrusted Participants
1.00
1.00
DSGD COP
Test accuracy
D560 CDP
Test accuracy
CANCO- COP
CARDOS CDP
0.75
DSOD Ser
0.75
DSG1 SeciDP
CARCOR SeCLLP
CAFCOR SCOLDP
DSCD ByZLOP
0E60 SycLDP
0.50
CAPCOR Sy.LEM
0.50
05GD
DSCO LDP
0.25
0.25
LOP
0.00
5
10
15
20
25
30
10
20
25
30
Iteration
Iteration
LF
(b) SF
1.00
1.00
DSGD
Test accuracy
CAPCOR
accuracy
0.75
DSGD SeLLDP
0.75
CARCOR SeCLDP
CARCOR -
DSGD BYLLOP
D5G3 RyCLEW
0.50
CAPCOR Ry-1EP
0.50
CAROR-BRyE Ryr OP
D5CD LDP
0EGO LDP
0.25
CARCON
0.25
CAFDR-LUD
0.00
0.00
5
10
15
20
25
30
10
15 Iteration
20
25
30
Iteration
(c) FOE
(d) ALIE
Figure 4: Comparison of CAFCOR and DSGD under four privacy threat models on MNIST. There are = 100 workers,
including f = 10 malicious workers executing four attacks. A homogeneous data distribution is considered among honest workers. User-level DP used and the aggregate privacy budget is (c, 6) = (26.4, 10 10-
0.8
0.8
Test accuracy
Test accuracy
0.6
0.6
0SGD
DSGO CDP
CAPCOR CDP
CAFCOR CDP
0.4
DSGD SectDP
0.4
DSCD SecLDP
CARCOR SecLDP
CAFCOR StcLDP
0500 ByaLD*
DS60 BydLDY
0.2
CARCOR Byyt
0.2
CAPCOR Carcna-nyyiia -yp.
05GD
0562 LLP
CARCOR
CAFCOR
0.0
0.0
5
10
15
20
25
30
10
15
20
25
30
Iteration
Iteration
L.F
(b) SF
0.8
0.8
Test accuracy
Test accuracy
0.6
0.6
CaP
DS5D SecLDP
0.4
DSGO SecLDP
CAPCOR SecLDP
CAFCOR SpCLOP
DSGD Bys
DSce Bysl
CArCOR bycuee
0.2
CArCOE CArCOR-ByA.I
DSGD- LDe
D660 -GP
CAPCON LDP
CArCOR LDP
0.0
0.0
5
10
15
20
25
30
10
15
20
25
30
Iteration
Iteration
(c) FOE
(d) ALIE
Figure 5: Comparison of CAFCOR and DSGD under four privacy threat models on Fashion -NIIST. There are 100 workers, including f = 5 malicious workers executing four attacks. A homogeneous data distribution is considered among honest workers. User-level DP is used and the aggregate privacy budget (e, 5) (39.6, 10 10-4).
39

---

Towards Trustworthy Federated Learning with Untrusted Participants
0.8
0.8
Test accuracy
Test accuracy
0.6
0.6
0SGD CDP
DSG0 CDP
CAYCOR-CO CaP
CAFCOR EDP
0.4
0550 SeiLD*
0.4
DSte3 SecLDP
CAPCOR Sec
CAFCOR Sec
050D ByaLD>
D660 ByZLDP
0.2
CArCOR ByctDe
0.2
CArCOR Bypu 0650 LDP
LDP CArCO
0.0
0.0
15 Iteration
25
30
10
20
25
30
Iteration
LF
(b) SF
0.8
0.8
Test accuracy
Test accuracy
0.6
0.6
Sed
0.4
Sec
CAPCOR SecLDP
CARCOR, SCCLDP
0550 ByrLD*
Dstea Bydlor
CAPCOR ByzLDP
0.2
CAFCOR ByOLDP
050D LDP
D660 LDP
CAPCOR 1.P
CARCOR
0.0
0.0
5
10
15
20
25
30
10
15
20
25
30
Iteration
Iteration
(c) FOB
(d) ALIE
Figure 6: Comparison of CAFCOR and DSGD under four privacy threat models on Fashion- There are 100 workers, including f = 10 malicious workers executing four attacks. A homogeneous data distribution is considered among honest workers. Userl DP is used and the aggregate privacy budget (c, 6) (39.6, 10 10-4).
40

---

Towards Trustworthy Federated Learning with Untrusted Participants
D.2. CAF vs. Robust Aggregators
100
100
Test Accuracy
DSGD If 00 CAFCOR CWTM
Test Accuracy
75
50
GM CANED
CVIMED
25
25
NK Meamed
SMEA
100
200
300
400
0
100
200
300
400
Iteration
Iteration
(a) LF
(b) SF
100
100
Test Accuracy
Test Accuracy
OSCD
DEGO
50
50
25
25
SHEA
SMEA
0
0
100
200
300
400
0
100
200
300
400
Iteration
Iteration
(c) FOE
(d) ALIE
Figure 7: Performance of CAFCOR versus standard robust algorithms on MNIST. There is f = 1 malicious worker among workers, and we consider extreme heterogeneity among honest workers. The CDP privacy model is considered under example-level DP, and the privacy budget is (s, (13.7, 10-4) throughout.
100
100
DSGI CAPCON
Test Accuracy
OSGD
Test Accuracy
75
75
CWTM
CWTM
50
GM CWNFR
50
MBC Meamed SMEA
25
25
0
100
200
300
400
100
200
300
400
Iteration
Iteration
(a) LF
(b) SF
100
100
Test Accuracy
Test Accuracy
75
75
DSGD If 30
DSG2 If 01
CArCOR
CAFCOR
50
CWTM
50
CVTN
GM CANFO
EWMID
25
25
0
100
200 Iteration
400
100
300
400
Iteration
(c) FOE
(d) ALIE
Figure 8: Performance of CAFCOR versus standard robust algorithms on MNIST. There are f malicious workers among 13 and
0.1. The CDP privacy model is considered under example-level DP, and the privacy budget is (c, 6) (13.7, 10-1) throughout.

---

Towards Trustworthy Federated Learning with Untrusted Participants
100
100
DSGB
Test Accuracy
Test Accuracy
CArCOR
75
75
CWTM
CWTN
50
GM
50
CVMEDD
MX
25
Meamed SMEA
25
0
100
200
300
400
0
100
200
300
400
Iteration
Iteration
(a) LF
(b) SF
100
100
Test Accuracy
Test Accuracy
75
75
DSGD If 0)
CARCOR
50
50
CVTN
NK
CWMED
25
Meamed
25
SHEA
100
200 Iteration
300
400
100
200 Iteration
300
400
(c) FOE
(d) ALIE
Figure 9: Performance of CAFCOR versus standard robust algorithms on MNIST. There are f malicious workers among 15 and = 1. The CDP privacy model is considered under example-level DP, and the privacy budget is (e, (13.7, 10-4) throughout.
Comparison with SMEA (Allouah et al., 2023c) We also included in our experiments a comparison with the SMEA robust aggregation method on the MNIST dataset (see Figures 7, 8, and 9). These results show that SMEA matches CAF's accuracy, significantly outperforming other standard robust methods, and even approaching the averaging baseline. This observation aligns with our theoretical findings (see Proposition 4.1 and subsequent discussion).
However, emphasize that SMEA incurs substantial computational cost, which further supports the empirical advantage of CAF, despite the two methods offering similarly strong robustness in practice. To highlight SMEA's prohibitive computational complexity, we report runtime ratios relative to simple averaging (lower is better), with 30 workers and = malicious workers, on models of varying dimension d.
Dimension (d)
SMEA
CAF
Meamed
GM
0.25 10"
30,251
28
112
62
0.5 x 107
61,142
51
197
78
x 107
117,255
100
378
126
Table 1: Computation time (relative to simple averaging) across different dimensions for various aggregation methods.
As seen in Table 1, CAF dramatically outperforms SMEA in terms of runtime, and also maintains clear advantage over other robust aggregation baselines such as Meamed and GM. Combined with CAF's superior performance on test accuracy, these results underscore CAFCOR's practical relevance for trustworthy federated learning.
42

---

Towards Trustworthy Federated Learning with Untrusted Participants
100
100
Test Accuracy
Test Accuracy
75
DSGD CARCOR CWTM
75
01
50
GM CWNEE
50
CARCOR
MB
25
Plaamed
25
Neamed
0
100
200
300
400
0
100
200
300
400
Iteration
Iteration
(a) LF
(b) SF
100
100
Test Accuracy
Test Accuracy
75
75
DSGD If 00 CARCOR
DSG2 If 01
50
50
CAFCOR
CWTM
CWIN
25
25
0
100
200
300
400
100
200 Iteration
300
400
Iteration
(c) FOE
(d) ALIE
Figure 10: Performance of CAFCOR versus standard robust algorithms on Fashion-MNIST. There are 1 malicious worker among 11, and consider extreme heterogeneity among honest workers. The CDP privacy model is considered under example-level DP, and the privacy budget is (e, 8) (13.7, 10-#) throughout.
100
100
BSGB (f- 00
Test Accuracy
Test Accuracy
CARCOR
75
75
CWTM
50
GM
50
CWMLD
NK Meamed
25
25
0
100
200
300
400
0
100
200 Iteration
300
400
Iteration
(a)
(b)
100
100
Test Accuracy
Test Accuracy
75
75
DSGD If 00 CAPCOR
D5G0 If U1
50
50
CAFCOR
CWTM
CVTN
GH
25
OANED
25
CWMED
100
200 Iteration
400
100
300
400
Iteration
FOE
(d) ALIE
Figure 11: Performance of CAFCOR versus standard robust algorithms Fashion-MNIST. There are f 3 malicious workers among 13 and 0.1. The CDP privacy model is considered under example-level DP, and the privacy budget is (c, (13.7, 10 o) throughout.
43

---

Towards Trustworthy Federated Learning with Untrusted Participants
100
100
Test Accuracy
Test Accuracy
CAROOR
75
75
CWTM
GM
CAMED
50
50
Meamed
25
Meamed
25
100
200 Iteration
300
400
100
200
300
400
Iteration
LF
(b) SF
100
100
Test Accuracy
Test Accuracy
75
D340 [f
75
CARCOR
CVTN
CM
25
CVMED
Neamed
100
200
300
400
0
100
200 Iteration
300
400
Iteration
(c) FOB
(d) ALIE
Figure 12: Performance of CAFCOR versus standard robust algorithms on Fashion-MNIST. There are f = 5 malicious workers among 15 and a 1. The CDP privacy model is considered under example-level DP, and the privacy budget is (e, 6) = (13.7, 10 10-4) throughout.
44


Reviews:
[{"review_id": "RqNlUsyli2", "reviewer": "Reviewer_g8Bp", "summary": "The paper introduces an algorithm (CAFCOR) to achieve privacy and robustness in distributed learning without relying on a trusted central server. In particular, it employs correlated noise injection inspired by secret sharing and combines it with a robust aggregation technique to mitigate Byzantine workers' impact. The algorithm achieves near-central DP (CDP) utility by leveraging secret-based local differential privacy. Extensive experiments on MNIST and Fashion-MNIST datasets demonstrate CAFCOR's superior performance under various Byzantine attack scenarios compared to existing methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful feedback. Below, we address the key points raised:\n\n### **Experimental Scope**\n\n> Limited evaluation datasets.\n\nThe reviewer’s suggestion to evaluate additional datasets is highly valid. We stress, however, that our current evaluation on MNIST and Fashion-MNIST is already extensive, rigorously testing our algorithm CafCor across multiple threat models, robust aggregation methods, and varying data heterogeneity levels (Section 5). Crucially, our setting is quite *challenging* even on these standard datasets, since we enforce **both** differential privacy without trusting the server and Byzantine resilience under state-of-the-art attacks. Indeed, as Figure 2 clearly illustrates, prior state-of-the-art methods suffer substantial accuracy losses under these combined constraints. Also, the SOTA method by Allouah et al. (2023b, ICML) could only scale to small logistic regression tasks with weaker theoretical guarantees, highlighting the novelty and practical significance of our results.\n\nWe recall that our core contribution is a rigorous theoretical framework that significantly advances the resolution of the privacy–robustness–utility trilemma (Allouah et al. 2023b, ICML), with minimal trust assumptions. Theoretically, we approach the minimax-optimal privacy-utility trade-off achievable in the ideal scenario (trusted server, no Byzantine adversaries—Corollary 4.1). Empirically, CafCor closely matches this optimal baseline even under Byzantine threats (Figure 1). Extending to larger datasets such as ImageNet is an important and exciting future step, which we will explicitly mention.\n\n### **Comparison with State-of-the-Art Methods**\n\n> Lack of comparison with recent privacy-preserving FL methods like DP-FL or DP-SGD.\n\nWe believe there is a misunderstanding regarding our comparisons. In fact, we already benchmark CafCor against strong, theoretically optimal baselines in the paper: DP-SGD (pointed out by the reviewer) adapted for federated learning under local (LDP) and central (CDP) differential privacy. Figures 1 and 2, where \"DSGD\" denotes FL-adapted DP-SGD, demonstrate that CafCor outperforms LDP and closely approaches CDP (i.e., trusted server) utility. Moreover, in Section 5.2, we compare to numerous standard Byzantine-robust defenses. We will clarify this in the paper.\n\n### **Computational Complexity**\n\n> The complexity of CAF aggregation may hinder real-time deployment in large-scale systems.\n\nWe thank the reviewer for highlighting this important aspect. CafCor’s aggregation complexity, while higher than simple averaging, is significantly lower than previous state-of-the-art methods like SMEA, whose runtime complexity is exponential in the number of Byzantine workers $f$. Specifically, SMEA performs an exhaustive subset search across subsets of size $n-f$, making it computationally infeasible. In contrast, our covariance-based CAF aggregation with power-method approximation achieves an efficient runtime of $\\mathcal{O}(f n d \\log d)$, enabling scalability to high-dimensional models, far beyond the closest prior work (Allouah et al. 2023b), which only scaled to small logistic regression tasks. \nFinally, compression is feasible but beyond our current focus on privacy and robustness.\n\nWe refer the reviewer to new experiments, included in our response to Reviewer 6PZT due to space constraints, that explicitly demonstrate this complexity advantage over SMEA, and will include these new experiments in the revision.", "claims_and_evidence": "- The CAF aggregation method is shown to be resilient to a significant number of Byzantine workers.\n- The experimental results support the theoretical claims, demonstrating improved accuracy compared to Local Differential Privacy (LDP) baselines. \n- However, the experiments are limited to only MNISST and Fashion-MNIST.\n- The explanation of how it practically handles high-dimensional data could be clarified.", "methods_and_evaluation_criteria": "- The use of shared randomness and correlated noise injection can improve the privacy-utility trade-off.\n- It is necessary to compare against more existing state-of-the-art methods beyond LDP and CDP.", "theoretical_claims": "The theoretical claims are thoroughly developed. However, to improve clarity, more intuitive explanations of the theoretical results should be included.", "experimental_designs_or_analyses": "The experimental design is limited.", "relation_to_broader_scientific_literature": "The paper discusses related work in differential privacy, Byzantine robustness, and secret sharing.", "essential_references_not_discussed": "The related works discussed are sufficient.", "other_strengths_and_weaknesses": "### Strengths:\n- Effective handling of Byzantine workers through robust aggregation.\n- Empirical results support the theoretical findings.\n\n### Weaknesses:\n- Limited evaluation datasets.\n- The complexity of CAF aggregation may hinder real-time deployment in large-scale systems.\n- Lack of comparison with recent privacy-preserving FL methods like DP-FL or DP-SGD.", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. How does CAFCOR perform on datasets with real-world heterogeneity and natural label noise?\n2. What is the computational overhead of the CAF aggregation technique, particularly for large-scale models?\n3. Can CAFCOR be integrated with gradient compression or sparsification techniques to improve communication efficiency?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PTRKiQluwu", "reviewer": "Reviewer_aCu9", "summary": "This paper proposes a novel methodology to achieve resilience in the face of malicious parties colluding with an untrusted server in the distributed learning framework as well as privacy guarantees, based on a weak assumption that each pair of communicating workers secretly share a seed of randomness, used to inject correlated noise when aggregating gradients. As experiments show, the proposed method achieves stronger guarantees than methods based on local differential privacy and even approach those of centralized differential privacy, which do rely on an assumption of a fully trusted server. Empirical results validate.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We clarify our intent and recall our contributions below following the reviewer's comments, and we welcome further discussion to refine our presentation.\n\n\n### **Use of \"Byzantine” Terminology**\n\nThis is a standard term in distributed computing literature (Lamport et al., 1982), referring strictly to arbitrary malicious behavior, with no cultural implications. Nevertheless, we remain open to adopting alternative phrasing.\n\nWe recall that our core contribution is a rigorous theoretical framework that significantly advances the resolution of the privacy–robustness–utility trilemma (Allouah et al. 2023b, ICML), with minimal trust assumptions. Theoretically, we approach the minimax-optimal privacy-utility trade-off achievable in the ideal scenario (trusted server and no attacks, see Corollary 4.1). Empirically, CafCor closely matches this optimal baseline even under state-of-the-art attacks (Figure 1).", "claims_and_evidence": "The claims are supported theoretically and experimentally.", "methods_and_evaluation_criteria": "Methods and data are well-chosen.", "theoretical_claims": "Theorems 4.1 and 4.2 seem sound.", "experimental_designs_or_analyses": "The proposed method builds upon DSGD, and also compares against its plain version as a baseline.", "relation_to_broader_scientific_literature": "First analysis of secret-based local differential privacy in adversarial distributed learning, considering an untrusted server and workers who aim to disrupt the learning as well as to compromise the privacy of honest workers by colluding with the server. Most of the works is based on previous works by Mironov and Allouah et al.", "essential_references_not_discussed": "The claim that [Lamport 1982] labeled misbehaving workers in a certain way is false. That paper narrates a parable and applies a certain label to all workers (i.e., generals), not only misbehaving ones.", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "Is there a reason for the main body of the paper to continuously invoke a cultural bias that labels people of a certain cultural heritage as dishonest or malicious?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_flag": "Flag this paper for an ethics review.", "ethics_expertise_needed": ["Discrimination / Bias / Fairness Concerns", "Other expertise"], "ethical_review_concerns": "The paper continuously alludes to a prejudice that labels people of a certain cultural heritage as dishonest and untrustworthy."}}, {"review_id": "0Gf8uaXwib", "reviewer": "Reviewer_6PZT", "summary": "The paper proposes a technique to perform distributed mean estimation with differential privacy guarantees and robustness to byzantine participants. To achieve privacy, if first adopts the anti-correlated noise method of [1,2]. To achieve robustness, it uses the empirical covariance matrix of the contributions to filter byzantine inputs, a technique which is specially tailored to work under correlated DP noise. The resulting protocol inherits the accuracy improvement that approaches central DP of [1,2] while improving the resilience to malicious participants of related byzantine aggregation techniques that are less prepared to work under DP noise. \n\nReferences (will be also used below): \n\n[1] Sabater, César, Aurélien Bellet, and Jan Ramon. \"An accurate, scalable and verifiable protocol for federated differentially private averaging.\" Machine Learning 111.11 (2022): 4249-4293.\n\n[2] Allouah, Youssef, et al. \"The privacy power of correlated noise in decentralized learning.\" arXiv preprint arXiv:2405.01031 (2024).\n\n[3] Allouah, Youssef, et al. \"On the privacy-robustness-utility trilemma in distributed learning.\" International Conference on Machine Learning. PMLR, 2023.\n\n## update\n\nThe authors have successfully addressed all my concerns and therefore I raise my score. As long as the discussed aspects are clarified, I think the paper deserves to be accepted.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and thoughtful feedback. Below, we address the points raised:\n\n###  **Empirical Comparison with SMEA**\n\n> it is not clear why [...] SMEA [3] is not included in the comparison. Theoretically, it seems that SMEA has the same robustness as CafCor.\n\nWe thank the reviewer for this valuable suggestion. As noted, SMEA (Allouah et al., 2023b) was initially excluded from our main experiments due to its exponential complexity. Specifically, SMEA exhaustively searches all subsets of size $n - f$ for the minimal covariance top eigenvalue, incurring prohibitive computational costs. In contrast, our CAF aggregation method achieves a runtime of $\\mathcal{O}(f n d \\log d)$ using an iterative spectral reweighting scheme.\n\n**1\\. Computational Complexity Comparison**\n\nTo explicitly demonstrate SMEA's prohibitive computational complexity, we report runtime ratios relative to simple averaging (smaller is better), with $n=30$ workers and $f=3$ Byzantine workers, on models of varying dimension $d$.\n\n| Dimension ($d$) | SMEA         | CAF   | MeaMed | Geometric Median (GM) |\n|---------------------|--------------|-------|--------|------------------|\n| $2.5 \\times 10^6$ | 30,251       | **28**| 112    | 62               |\n| $5 \\times 10^6$   | 61,142       | **51**| 197    | 78               |\n| $10^7$            | 117,255      | **100**| 378   | 126              |\n\nCAF clearly achieves a dramatically lower complexity than SMEA and can even be more efficient than standard aggregations such as MeaMed and Geometric Median.\n\n**2\\. Utility Comparison**\n\nWe also execute SMEA in the setting of Figure 2 (MNIST), where we consider a small system comprised only of $n=15$ and $f=5$ Byzantine workers.\n\n| Method                 | Accuracy (\\%)        |\n|------------------------|----------------------|\n| Averaging (no attack)  | $93.05$     |\n| SMEA                   | $89.96$     |\n| **CAF**                | ${\\bf 89.60}$     |\n| MeaMed                 | $44.81$     |\n| Median (CWMED)                 | $29.66$      |\n| Trimmed mean (CWTM)          | $12.74$     |\n| Geometric Median (GM)                 | $9.73$     |\n\n\nCAF matches SMEA's accuracy, significantly outperforming other standard robust methods, and approaching the averaging baseline (thanks also to our correlated noise scheme). This result aligns with our theory (Proposition 4.1), as the reviewer helpfully pointed out.\n\nWe will clearly highlight these new results in the revised manuscript.\n\n###  **Theoretical Analysis**\n\n> The theoretical analysis [...] is reasonable [...]  First, I am not sure why a new privacy analysis is necessary [...]. Second, I do not see a clear take-away from the convergence analysis [...]\n\nThis comment is insightful. Our privacy analysis (Theorem 4.1) is distinct from [1,2], addressing a new threat model where Byzantine adversaries partially collude with the untrusted server. A notable insight (Section 4.1) is that honest workers require no independent noise injection when a non-colluding Byzantine worker exists. Further, Proposition 4.1 alone cannot derive our final privacy-utility result (Corollary 4.1); Theorem 4.2 is essential to quantify correlated noise effects across iterations, controlled by CAF aggregation and local momentum in CafCor. These dependencies were not analyzed in [1,2]. We will explicitly clarify these points.\n\n###  **Positioning relative to Reference [1]**\n\n> [1] studies cryptographic techniques [...] to deal with malicious participants [...]. The paper should broadly position to such techniques.\n\nReference [1], included in our paper, uses cryptographic checks (e.g., correct computation, bounded inputs) to verify malicious participants' messages but provides no explicit utility guarantees under arbitrary Byzantine attacks passing these checks. In contrast, CafCor addresses a more challenging scenario: adversaries crafting inputs that pass such verification yet harm model performance. Thus, cryptographic verification alone is insufficient for our Byzantine robustness objective. CafCor explicitly guarantees privacy and utility even under these stronger adversarial conditions (Corollary 4.1). We agree the privacy analysis in [1] may be tighter than [2], though both focus on decentralized topologies unlike our federated setting. We will highlight this explicitly.\n\n###  **Communication Cost**\n\n> The communication cost is not discussed [...]\n\nPairwise shared randomness (exchanging at most $n(n-1)$ integers) occurs offline once, incurring negligible quadratic communication compared to repeated training communications (model weights of size $d$ over many iterations). We will clarify this explicitly.\n\n### **Additional Clarifications**\n\n> I am not really sure why Opacus is used to estimate the privacy budget [...]\n\nWe use Opacus solely for tighter practical composition of per-round privacy budgets (using per-round theoretical guarantees of Theorem 4.1 with $T=1$). We will explicitly clarify this usage.", "claims_and_evidence": "The main claim of the paper is that the proposed byzantine aggregation technique outperforms previous techniques for FL updates that are hidden under correlated DP noise. This is theoretically and empirically backed for standard aggregation techniques. \n\nHowever, it is not clear why the SMEA aggregation method [3] is not included in the comparison. Theoretically, it seems that SMEA has the same robustness as CafCor. However, it is not present in the comparison of the empirical evaluation. \n\nTherefore, the claim is not completely backed for related previous aggregation techniques.", "methods_and_evaluation_criteria": "The paper provides a theoretical analysis and an experimental evaluation. \n\nThe experimental analysis is performed for using MNIST and fashion-MNIST datasets under homogeneous and heterogeneous distributions, which is reasonable. Attacks also seem reasonable. \n\nThe theoretical analysis of utility/robustness (i.e. Proposition 4.1) is reasonable as it provides clear comparisons with previous techniques. The rest of the theoretical results have a less clear message. First, I am not sure why a new privacy analysis is necessary, as current trade-offs are inherited from [1,2] and the novel part of the contribution (i.e. the CAF filter) is a post processing of such protocols. Second, I do not see a clear take-away from the convergence analysis that relates to the claims of the paper, whose results and techniques seem standard.", "theoretical_claims": "I have checked the proofs theoretical claims of Theorem 4.1 and Proposition 4.1 and I did not see problems. Proofs of Theorems 4.2 and Corollary 4.1 seem in shape, but I have not checked all the derivations of the appendix related to them.", "experimental_designs_or_analyses": "The experimental design is reasonable in general. However there are a few issues: \n- The number of runs of the protocol to get the confidence intervals on the reported accuracy is rather small (5 seeds).\n- I am not really sure why Opacus is used to estimate the privacy budget if the paper provides a clear privacy analysis which gives explicit $\\epsilon$ and $\\delta$ after execution", "relation_to_broader_scientific_literature": "- The contributions are well positioned with respect to what are called within the paper as standard byzantine aggregation techniques: coordinate-wise trimmed mean and median (Yin et al., 2018), geometric median (Chen et al., 2017), Multi-Krum (Blanchard et al., 2017), and mean around median (Xie et al., 2018). However, as said before, the contribution is not well positioned with respect to the resilience of SMEA [3]. In addition, it is not sufficiently clear how different is the proposed technique with respect to SMEA. \n\n- The paper states that previous literature has not studied the resilience of correlated DP noise to malicious participants. This does not seem to be true, as [1] studies cryptographic techniques (in particular, zero knowledge proofs) to deal with malicious participants under privacy constraints. The paper should broadly position to such techniques.\n\n- The paper claims that [1] does not use Renyi divergences for their privacy guarantees. I am not sure why that is a disadvantage. Renyi divergences are a tool for privacy accounting but it is not mandatory to use it as long as guarantees are provided. What makes the protocol private are the obtained with $(\\epsilon, \\delta)$ parameters and their trade-off with respect to $\\sigma_{cor}^2$ and $\\sigma_{ind}^2$. Moreover, [1] provides equal or better trade-offs between privacy and the variance of the correlated noise $\\sigma_{cor}^2$ than [2] for the extreme cases of communication topologies, which suggests that the privacy analysis is tighter.", "essential_references_not_discussed": "To the best of my knowledge, I don't see any key reference that has been ignored.", "other_strengths_and_weaknesses": "- The communication cost is not discussed: implementing the pairwise shared randomness requires that all parties communicate with each other to minimize $\\sigma_{cor}^2$. This incurs in a high communication cost ($O(n^2)$ messages). Considering that the authors claim efficiency as a feature of the protocol, this should be brought to the table.", "other_comments_or_suggestions": "I have no further comments.", "questions_for_authors": "Please address the raised points with respect to the comparison with SMEA [3] and [1,2] raised in my review.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fy8suHxRIl", "reviewer": "Reviewer_3HsQ", "summary": "Achieving robustness against Byzantine workers and preserving data privacy are two important objectives in distributed learning. Existing work primarily studies each problem separately, and achieving both simultaneously is a challenging task. In this paper, the authors propose CAFCOR, an algorithm designed to achieve both robustness and data privacy without relying on a fully trusted central server. The CAFCOR algorithm combines robust gradient aggregation with correlated noise injection, using shared randomness between workers. In this setting, each worker perturbs its gradient update using a combination of independent noise and correlated noise. The server then applies CAF (covariance-bound agnostic filter), which adjusts weights based on variance contributions to suppress the influence of Byzantine workers. The authors demonstrate that CAFCOR achieves privacy guarantees comparable to central differential privacy while maintaining robustness against Byzantine attacks.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful feedback. Below, we address the key points raised:\n\n### **Experimental Scope**\n\n> evaluating on MNIST and Fashion-MNIST is insufficient [...]\n\nThe reviewer’s suggestion to evaluate additional datasets is highly valid. We stress, however, that our current evaluation on MNIST and Fashion-MNIST is already extensive, rigorously testing our algorithm CafCor across multiple threat models, robust aggregation methods, and varying data heterogeneity levels (Section 5). Crucially, our setting is quite *challenging* even on these standard datasets, since we enforce **both** differential privacy without trusting the server and Byzantine resilience under state-of-the-art attacks. Indeed, as Figure 2 clearly illustrates, prior state-of-the-art methods suffer substantial accuracy losses under these combined constraints. Also, the SOTA method by Allouah et al. (2023b, ICML) could only scale to small logistic regression tasks with weaker theoretical guarantees, highlighting the novelty and practical significance of our results.\n\nWe recall that our core contribution is a rigorous theoretical framework that significantly advances the resolution of the privacy–robustness–utility trilemma (Allouah et al. 2023b, ICML), with minimal trust assumptions. Theoretically, we approach the minimax-optimal privacy-utility trade-off achievable in the ideal scenario (trusted server, no Byzantine adversaries—Corollary 4.1). Empirically, CafCor closely matches this optimal baseline even under Byzantine threats (Figure 1). Extending to larger datasets such as ImageNet is an important and exciting future step, which we will explicitly mention.\n\n### **Computational Complexity**\n\n> The complexity of the proposed CAF aggregation appears to be high, making it impractical for high-dimensional models, e.g., deep learning\n\nWe thank the reviewer for highlighting this important aspect. CafCor’s aggregation complexity, while higher than simple averaging, is significantly lower than previous state-of-the-art methods like SMEA, whose runtime complexity is exponential in the number of Byzantine workers $f$. Specifically, SMEA performs an exhaustive subset search across subsets of size $n-f$, making it computationally infeasible. In contrast, our covariance-based CAF aggregation with power-method approximation achieves an efficient runtime of $\\mathcal{O}(f n d \\log d)$, enabling scalability to high-dimensional models, far beyond the closest prior work (Allouah et al. 2023b), which only scaled to small logistic regression tasks.\n\nWe refer the reviewer to new experiments, included in our response to Reviewer 6PZT due to space constraints, that explicitly demonstrate this complexity advantage over SMEA, and will include these new experiments in the revision.\n\n### **Clarifications on Definitions and Methods**\n\n> Gradient clipping appears to be performed at the client-side, it is not clear why this is necessary.\n\n> Please explicitly define the nature of Byzantine workers\n\n> Please clarify how data heterogeneity is modeled in the experiments\n\nWe thank the reviewer for this helpful request for clarity.\nByzantine workers are defined as workers capable of arbitrary deviation from the protocol and collusion, with full knowledge of the algorithm. Data heterogeneity is modeled through a Dirichlet distribution (following Hsu et al. 2019, see Section 5), simulating realistic conditions.\nBesides, bounded heterogeneity is a common assumption in distributed learning for convergence analyses (Karimireddy et al. 2022, Farhadkhani et al. 2022, Allouah et al. 2023b), although heterogeneity is not the focus of our current work.\nFinally, gradient clipping at the client side is standard practice, essential for differential privacy guarantees, and carries low computational overhead.", "claims_and_evidence": "I think the claims are generally well-supported. However, please see the Experimental Designs or Analyses section.\n\n## update after rebuttal\n\nI thank the authors for their responses.\nWhile some of my concerns have been addressed, my main concern regarding the limited scope of the experiments remains unresolved. I think this paper has the potential to make a significant contribution, but it would require a major revision to reach that stage. I have decided to lower my initial rating.", "methods_and_evaluation_criteria": "- The authors introduce a refined version of secret-based local differential privacy (SecLDP), which extends traditional LDP by assuming that workers share randomness. This relaxation of the trust assumption in CDP seems to improve utility over LDP models while still maintaining privacy.\n- The authors provide a theoretical analysis of the privacy-utility trade-off and robustness against Byzantine workers achieved by CAFCOR.\n- The proposed CAF algorithm appears to be sensible and with theoretical guarantees. The requirement of shared randomness, achieved through a one-time encrypted communication round, seems reasonable.\n\n- The complexity of the proposed CAF aggregation appears to be high, making it impractical for high-dimensional models, e.g., deep learning. While the authors mention a power method-based approximation, its practical applicability in large-scale problems needs to be verified.\n- The assumption of bounded heterogeneity seems to limit the applicability. In real-world distributed learning scenarios, data can be highly heterogeneous.", "theoretical_claims": "I checked briefly the main theoretical results but not their proofs.", "experimental_designs_or_analyses": "- The experiments are weak. Even considering the theoretical contributions of the paper, evaluating on MNIST and Fashion-MNIST is insufficient. To demonstrate the practical utility of the algorithm, the authors should perform experiments on more challenging real-world datasets (e.g., ImageNet, CIFAR-100).", "relation_to_broader_scientific_literature": "Please see the Summary section.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "- Gradient clipping appears to be performed at the client-side, it is not clear why this is necessary. Given that gradient clipping could potentially be handled at the server-side, requiring additional client-side operations beyond momentum generation may reduce the practical applicability of CAFCOR.\n- Please explicitly define the nature of Byzantine workers. Do they have access to the entire learning process, or are there any limitations on their capabilities?\n- Please clarify how data heterogeneity is modeled in the experiments. Specifically, how are the datasets distributed among clients, and what level of heterogeneity is introduced?", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper tackles the challenging trilemma of privacy, robustness, and utility in federated learning without assuming a trusted central server. Inspired by recent advances in the privacy literature (Sabater et al., 2022; Allouah et al., 2024), the authors slightly relaxes the local DP threat model to be able to leverage pairwise shared randomness for correlated noise injection. The paper also proposes CAF, a novel robust aggregation rule that is significantly more computationally efficient than the state-of-the-art SMEA. Theoretical results demonstrate that the proposed approach achieves near–central‑DP utility while bounding the influence of adversarial participants.

The author response and subsequent discussion clarified key concerns, through additional experiments and improved positioning relative to prior work. With these clarifications, the majority of reviewers now view the paper favorably. I recommend acceptance.

That said, I ask the authors to follow through on the revisions they committed to during the discussion phase, particularly:
However, I ask the authors to commit to making the revisions they promised during the discussion, in particular:
- Adding the new experimental comparisons;
- Updating the discussion of Sabater et al. (2022) to appropriately acknowledge their contributions to privacy analysis and the ability to handle malicious workers;
- Replacing "Byzantine" with "adversarial" throughout the manuscript to address cultural sensitivity concerns.
Decision: Accept (poster)