arXiv CSopen access

Unveiling the Non-Monotonic Effect of Privacy on Generalization under Byzantine Robustness

Unveiling the Non-Monotonic Effect of Privacy on Generalization under Byzantine Robustness

arXiv:2607.01492v1 [cs.LG] 1 Jul 2026

Thomas Boudou Inria, Université de Montpellier, INSERM Montpellier, France [email protected] Nirupam Gupta University of Copenhagen Copenhagen, Denmark [email protected]

Batiste Le Bars Inria, Université de Lille Lille, France [email protected]

Aurélien Bellet Inria, Université de Montpellier, INSERM Montpellier, France [email protected]

Abstract Recent work has established a fundamental trilemma between Byzantine robustness, local differential privacy (LDP), and optimization error in distributed learning. We show that this trilemma does not universally extend to generalization error, but instead depends critically on the privacy regime. Specifically, in the high-noise regime (strong privacy), we prove that increasing privacy reduces the generalization error, i.e., there is no tension between robustness and privacy. In the low-noise regime (weaker privacy), however, the tension between robustness and privacy reappears and increasing privacy indeed degrades generalization. Our theory explains this surprising non-monotonic behavior of the generalization error via matching lower and upper bounds on the algorithmic stability of Byzantine-robust distributed learning under LDP constraints. We corroborate and further analyze these theoretical findings with empirical evaluations.

1

Introduction

Learning high-quality models often requires access to large amounts of data and substantial computational resources, making distributed learning systems such as Federated Learning (FL) [19] a promising approach to leverage data and computation across many participants. FL is typically implemented via distributed gradient descent algorithms coordinating local updates across participants. However, sharing model updates is known to leak information about the underlying training data, which can reduce participants’ willingness to contribute and raises challenges for complying with data protection regulations. Local Differential Privacy (LDP, or local DP) is a natural privacy framework for distributed learning under the honest-but-curious threat model, where the server follows the protocol but may attempt to infer sensitive information from participant updates [12, 19]. This assumption is practically motivated, as the server is often a third party that cannot be fully trusted. LDP typically enforces privacy by having each participant locally add noise to its updates before sending them. In addition to privacy concerns, real-world distributed systems face a range of unpredictable malfunctions, from benign hardware failures to adversarial misbehavior (e.g., poisoning attacks), broadly categorized under the umbrella of Byzantine failures [17]. This motivates a second line of defense known as Byzantine robustness, which aims to ensure reliable learning through robust aggregation rules that mitigate the influence of corrupted or malicious updates. While both LDP and Byzantine robustness are well-studied in isolation, their interplay remains a largely underexplored frontier despite being highly relevant in practical deployments.

Related work. A first line of work has investigated the impact of LDP alone, establishing a tight privacy-utility trade-off, where LDP constraints inflate the optimization of the empirical risk by a variance penalty [35, 15, 27]. LDP has also been studied in federated stochastic convex optimization [12, 29], where the focus is on excess population risk guarantees, leading to similar qualitative insights on the privacy–utility trade-off. Focusing on Byzantine robustness alone, recent work has extensively studied (f, κ)-robust aggregation as a principled approach to achieve optimal optimization guarantees in the presence of Byzantine failures [1]. These results show that, while robust aggregation can tolerate a fraction of Byzantine participants, it introduces an unavoidable bias that prevents the optimization error from vanishing when data are heterogeneous across participants. This limitation extends to the statistical learning setting [7], where the generalization error (the discrepancy between training and population risks) is further amplified by the constraints imposed by robust aggregation. However, their analysis does not consider formal privacy constraints. Recently, a fundamental trilemma has been demonstrated for distributed algorithms that aim to be both Byzantine robust and satisfy LDP [2]. More precisely, this work shows that the interaction between Byzantine robustness mechanisms and LDP constraints induces an additional optimization error term that does not appear when considering either requirement in isolation. This unavoidable term reveals an intrinsic tension between privacy and robustness. While this trilemma precisely characterizes the optimization dynamics in terms of empirical risk, the true measure of a model’s performance is its population risk, i.e., its behavior on unseen data. This risk is typically decomposed into the sum of optimization and generalization errors (see Section 2) [18]. This naturally raises the question: does this trilemma extend to generalization? While it is intuitive that injecting privacy noise prior to aggregation can hinder the server’s ability to distinguish between honest and Byzantine updates, thereby increasing optimization error, its effect on generalization is less clear. Indeed, such noise is often associated with an implicit regularization effect that can help control and even improve generalization [36, 26]. This creates a fundamental tension: does LDP noise merely exacerbate the impact of Byzantine robustness, or can it also mitigate them? The interplay between these two opposing effects remains poorly understood and is the focus of our work. Contributions. We investigate this question and show that the privacy-robustness-optimization trilemma does not directly extend to generalization. By tightly analyzing the algorithmic stability of the algorithm introduced in [2] (i.e., Safe-D(S)DG, detailed in Algorithm 1), which achieves optimal optimization error in the considered setting, we uncover a fundamental non-monotonic relationship between privacy guarantees and generalization error under Byzantine robustness. Crucially, this behavior is not driven solely by the raw noise magnitude, but is characterized by the ability of Byzantine participants to reliably detect the presence of individual data points, i.e., the performance of a Membership Inference Attack (MIA). Indeed, we show that membership information of honest participants’ data is crucial to Byzantine participants’ power to attack the learning process. Specifically, we identify a threshold corresponding to a qualitative change in the privacy regime, where an optimal MIA achieves a non-trivial probability of success. This transition delineates two distinct regimes, each exhibiting fundamentally different generalization behavior. (i) Weak privacy regime (low noise): In this regime, the injected noise interacts adversely with Byzantine-robust aggregation, leading to a degradation of generalization performance. Quantitatively, the generalization error increases with the noise level and with the fraction of Byzantine participants, causing an initial deterioration. (ii) Strong privacy regime (high noise): Beyond the MIA threshold, the attack becomes ineffective and the system enters a regime consistent with classical differential privacy behavior. In this regime, increasing the noise level improves stability, and the generalization error decreases, eventually vanishing as privacy strengthens. We validate our theoretical findings, including our tight stability bounds, through empirical evaluations. These confirm that the identified worst-case behavior is relevant in realistic scenarios. Overall, our results refine the characterization of the privacy-robustness-utility trade-off in distributed learning.

2

Preliminaries

Problem setting. We consider a distributed setup with n participants coordinated by a central server. We assume this system is subject to Byzantine failures, and requires to guarantee LDP. 2

We consider the Byzantine failures threat model [22, 17], in which at most f (< n2 ) participants can act arbitrarily. Their identities are unknown to the server and they may deviate from the prescribed algorithm, collude, and send adversarial updates while having access to all information exchanged between honest participants and the server. We note H ⊆ [n] := {1, . . . , n} the set of honest participants, with |H| = n−f . Each honest participant i ∈ H holds a local dataset Di = {z (i,1) , . . . , z (i,m) } composed of m i.i.d. data points (or samples) from an input space Z drawn from a distribution pi . We denote by S = ∪i∈H Di the overall dataset. Given a parameter vector θ ∈ Θ ⊂ Rd representing the model, a data point z ∈ Z incurs a loss defined by a real-valued function ℓ(θ; z). The goal is to minimize the population risk over the honest participants P 1 RH (θ) = |H| i∈H Ez∼pi [ℓ(θ, z)]. Since only a finite number of samples are available from each distribution, we approximate this objective by minimizing the corresponding empirical risk over the (unknown) set of honest participants P P 1 1 b bH (θ) = 1 P R i∈H Ri (θ) = n−f i∈H m z∈Di ℓ(θ, z). |H| The expected excess population risk of a distributed learning algorithm’s output A : Z (n−f )m → Θ, S 7→ A(S) can be decomposed into generalization and optimization errors (e.g. [18]) as follows       bH (A(S)) + E R bH (A(S)) − inf R bH (θ) . (1) E RH (A(S)) − inf RH (θ) ≤ E RH (A(S)) − R θ∈Θ

θ∈Θ

Prior work on robust distributed learning has focused primarily on the optimization error, i.e., the second term on the right-hand side. In contrast, our goal is to study the generalization error, corresponding to the first term. Robust distributed optimization. Robust distributed optimization algorithms aim to achieve low empirical risk. They are typically adaptations of standard first-order iterative optimization algorithms like gradient descent (GD) or stochastic gradient descent (SGD). These algorithms are made resilient by replacing the server-side averaging operator by a robust aggregation rule F : (Rd )n → Rd [17]. Formally, given a learning rate γ, a parameter θt at iteration t ∈ {0, . . . , T − 1} is updated as follows (1)

(n)

θt+1 = GF γ (θt ) := θt − γF (gt , . . . , gt ), (i)

where gt denotes the update sent by participant i at step t. For an honest participant i ∈ H, we have (i) bi (θt ) under GD, or gt(i) = ∇ℓ(θt ; zt(i) ) under SGD, with zt(i) uniformly sampled from the gt = ∇R (i) local dataset Di . For a misbehaving participant i ∈ / H, gt is an arbitrary vector in Rd . Recent advances in robust distributed optimization have identified key properties sufficient for a robust aggregation rule to ensure the strong notion of (f, ρ)-resilience with respect to the empirical risk [1, 2]. The following definition encompasses a wide range of aggregation rules and has been shown to yield tight resilience guarantees across a variety of practical distributed learning settings. Definition 2.1. Let ∥·∥sp denote the spectral norm for p.s.d. matrices (i.e., the largest eigenvalue). Let d n ≥ 1, 0 ≤ f < n/2 and κ ≥ 0. An aggregation P rule F is (f, κ)-robust P if for any g1 , . . . , gn ∈⊺ R , 1 1 any set S ⊂ [n] of size n − f , with g S = |S| i∈S gi and ΣS = |S| i∈S (gi − g S )(gi − g S ) , ∥F (g1 , . . . , gn ) − g S ∥22 ≤ κ∥ΣS ∥sp . f and κ are referred to as the robustness parameter and robustness coefficient of F , respectively. An aggregation rule F that is (f, O(f /n))-robust achieves optimal (f, ρ)-resilience. Specifically, iterative methods using such F attain an optimization error that matches the information-theoretic lower bound for first-order optimization under f Byzantine participants [2]. An example is the smallest maximum eigenvalue averaging (SMEA) [2]. Definition 2.2. Let f, n ∈ N, f < n/2 and g1 , . . . , gn ∈ Rd , the SMEA outputs   1 X 1 X ⊺ gS∗ = ∗ gi with S ∗ ∈ argmin λmax (gi − g S ) (gi − g S ) . |S | |S| S⊆{1,...,n},|S|=n−f ∗ i∈St

i∈S

3

Note that the use of the spectral norm in Definition 2.1 is motivated by our setting. Under LDP constraints, which are usually achieved by adding isotropic noise to gradients, the empirical covariance matrix of honest participants’ gradients trace typically scales with the dimension, which is not the case when using the spectral norm, hence the usefulness of this matrix norm in high dimension. This highlights the focus on SMEA, which was specifically designed for our setting [2]. The recent Covariance Bound Agnostic-Filter (CAF) [3] is a computationally efficient variant of SMEA. Differential privacy. A primary objective for honest participants is to protect the privacy of their datasets. To provide a rigorous, quantifiable guarantee, we leverage differential privacy (DP) [13]. DP ensures that an algorithm’s output is indistinguishable whether or not any single individual’s data is included in the input dataset. We adopt the standard definition of (ε, δ)-DP. Definition 2.3. Let ε > 0, 0 ≤ δ ≤ 1. A randomized algorithm A is (ε, δ)-DP if for all neighboring honest datasets S and S ′ (differing in a single entry) and for all measurable subset of output O, P(A(S) ∈ O) ≤ eε P(A(S ′ ) ∈ O) + δ In the distributed setting, let Zi (S) denote the (random) transcript of communications between the server and honest participant i generated by A(S). A is (ε, δ)-LDP if ∀i ∈ H, Zi is (ε, δ)-DP. To summarize, our threat model considers two types of adversaries. First, we model the central server as honest-but-curious: it follows the prescribed protocol (i.e., it is honest) but may simultaneously attempt to infer sensitive, private information about individual participants’ datasets from model updates it observes (i.e., it is curious). Second, our system operates under the assumption of Byzantine failures. Note that this second adversary is strictly more powerful: it observes as much information as the server (since it can eavesdrop on its communications with honest participants), but also controls f Byzantine participants that can deviate from the protocol arbitrarily. The Safe-D(S)GD algorithm. Owing to its strong empirical performance and baseline optimality guarantees, Safe-D(S)GD [2] constitutes a natural choice of algorithm for our study. We consider the variant without momentum (Algorithm 1). In the deterministic (GD) setting, momentum is not required to achieve optimal error rates, making Safe-DGD theoretically optimal. While momentum is necessary in the stochastic regime to control the noise floor induced by Byzantine failures in the optimization error guarantee [20], omitting it here simplifies our analysis of algorithmic stability, which is already technically involved, and helps isolate the effects of privacy and Byzantine robustness. This simplification is further justified by prior work showing that momentum can negatively impact stability in distributed optimization [4, 28]. Algorithm 1 Safe-D(S)GD 1: Initialization: θ0 , aggregation F , noise σDP , number of steps T , learning rate γ 2: for t = 0 to T − 1 do 3: Server broadcasts θt to all participants 4: for all honest participant i ∈ H do 5:

(i)

1 Compute gt = m (i)

Pm

(i,j) ) j=1 ∇ℓ(θt ; z (i) (i,Jt )

(i) (i,Jt )

or gt = ∇ℓ(θt ; z ) where z from Di is sampled uniformly at random (i) (i) (i) (i) 2 Id ) 6: Add noise get = gt + ξt ; ξt ∼ N (0, σDP (i) 7: Send get to the server (1) (n) 8: Server aggregates Rt = F (e gt , . . . , get ) # f participants may send an arbitrary vector 9: Server updates model θt+1 = ΠΘ (θt − γt Rt ) 10: return θT or θ̂ sampled uniformly from {θ0 , . . . , θT }

The privacy analysis of Safe-D(S)GD follows the same, classic line of reasoning as in [2, Theorem 4.1], namely the composition of the subsampled Gaussian mechanism. We state the theorem for Safe-DGD for simplicity, though Safe-DSGD yields similar guarantees. √ 2C 2T ln(1/δ) Theorem 2.1. If σDP = , then Safe-DGD is (ε, δ)-LDP. mε Stability under misbehaving participants. Our study leverages algorithmic stability to understand the generalization error of robust distributed learning algorithms. We do so via uniform stability, 4

which measures the sensitivity of a learning algorithm to changes in its training data. This approach was introduced in [33, 10, 30], later popularized by [8, 32, 18], and has recently been successfully applied to Byzantine-robust distributed learning [7]. We revisit this framework to study generalization in private and robust distributed learning, where changes occur only in the honest participants’ data. Definition 2.4. Consider a distributed setting with up to f Byzantine participants (out of n). A distributed algorithm A is ε-uniformly stable if, for all honest datasets S, S ′ ∈ Z (n−f )m that are neighboring—i.e., differing in at most one sample—we have, supz∈Z EA [ℓ(A(S); z) − ℓ(A(S ′ ); z)] ≤ ε. This property leads to an upper bound on the generalization error, proved in Section A. As established by DP-to-stability arguments [36, Lemma 23], a (ε, δ)-DP algorithm already provides a bound on its algorithmic stability. For completeness, we provide a proof in Section A.1. Lemma 2.2. Any (ε, δ)-DP algorithm is ℓ∞ (eε − 1 + δ)-uniformly stable under an ℓ∞ -bounded loss. In other words, stronger privacy guarantees, i.e., smaller ε and δ (corresponding to higher noise variance in Safe-D(S)GD), lead to improved generalization. However, because this guarantee applies universally to any (ε, δ)-DP algorithm, this baseline stability bound is expected to be loose. To address this, we provide a refined, algorithm-specific analysis in the next section.

3

Non-monotonic privacy effect for Byzantine-robust generalization

We present our main results in the form of tight stability bounds for Safe-D(S)GD. We subsequently use these bounds to demonstrate a non-monotonic effect of LDP on the generalization error under Byzantine robustness, depicting a comprehensive understanding of the interplay between LDP and Byzantine robustness on generalization error. Upper bounds.

We start by deriving stability upper bounds. The proof is deferred to Section C.2. √ 2C 2T ln(1/δ) Theorem 3.1. Consider the setting described in Section 2. Let σDP = and γ ≤ L1 . mε Suppose ∀z ∈ Z, ℓ(·; z) C-Lipschitz and L-smooth. Then A is (ε, δ)-LDP and, up to numerical constants explicitly provided in Section C.2, (i) If ℓ(·; z) is convex ∀z ∈ Z, then the uniform stability of A is upper bounded by   √ √ DP q 1 d 2γC 2 T (n−f κ + κ σC 1 + n−f . (2) )m + (ii) If ℓ(·; z) is µ-strongly convex ∀z ∈ Z, then the uniform stability of A is upper bounded by   √ √ σDP q 2C 2 d 1 + κ + κ 1 + (3) µ (n−f )m C n−f . When there is no Byzantine participant (f = 0, hence κ = 0), both eqs. (2) and (3) reduce to the classical stability bounds established in [18]. When σDP = 0, we recover the bound from [7]. However, when both f, σDP > 0, the analysis reveals an additive degradation term arising from the interaction between privacy and robustness. In the convex setting, this degradation accumulates over the T iterations, whereas in the strongly convex case, it appears as a one-time term. The bound scales linearly with the maximal sensitivity of the gradient update (2γC), but also, perhaps surprisingly, with the privacy noise magnitude. Thus, stronger privacy (more noise) degrades stability, in contrast with standard DP-to-stability arguments [36]. We discuss this apparent paradox in the tightness analysis below. Lower bounds. Byzantine failures expose a vulnerability of robust aggregation: their adaptivity, typically beneficial, makes stability sensitive to independent noise addition. While this may seem counter-intuitive, as DP is usually associated with improved generalization, the following lower bounds show that this effect is in fact unavoidable in some regimes. In particular, these bounds hold under a weak privacy regime, where √ ε ∈ Ω(1); we defer the discussion of the two key ln(1/δ)

different privacy regimes to the next paragraph. The proof is deferred to Section C.3. Theorem 3.2. Consider the setting in Section 2 with full batch and the SMEA aggregation. Suppose f d there exist αmin , µ, ν > 0 such that n−f ∈ [αmin , 21 ) and n−f ∈ [µ, ν]. Let µmin , Nmin , cmin be 5

problem-dependent constants defined in Assumption C.3, and assume µ ≥ µmin , n√ − f − 1 ≥ Nmin , √ √ 2
2C 2T ln(1/δ) cmin ( d+ n−f −1) ε T ∈O e . Further suppose √ ∈ Ω(1) and σ = . Then ln(1/δ)

DP

mε

Θ×Z

there exists ℓ ∈ R such that ∀z ∈ Z, ℓ(·; z) is C-Lipschitz, L-smooth and convex, such that the uniform stability of A is lower bounded by q     q f f σDP 1 d Ω γC 2 T (n−f 1 + n−f . (4) )m + n−2f + n−2f C If we moreover assume n3 ≤ f < n2 , the uniform stability of A is lower bounded by q q     q f f σDP 1 d Ω γC 2 T (n−f + + 1 + . )m n−2f n−2f C n−f

(5)

The assumptions of Theorem 3.2, while technical, are fairly mild. They are either almost always satisfied in practice (e.g., the upper bound on T ) or assumed to enable bounds on expectations and concentration of random matrices (e.g., µmin and Nmin ). For details, seeqSection C.3.2. q The two
f f σDP d regimes on n from Theorem 3.1 are inherited from [7]. In contrast, the term n−2f C 1+ n−f , which is common to these two regimes, reflects a different privacy regime, as detailed in the next paragraph. It arises as the product of privacy- and robustness-driven terms and vanishes when f = 0. q
 √ f f Note that, for SMEA, κ ∈ O [2, Proposition 5.1]. Plugging this into our n−f 1 + n−2f upper bound (2) establishes tightness with respect to (2) and (5), and shows that (2) matches (4) q
σDP d under the mild condition C 1 + n−f ∈ Ω(1). This highlights an unavoidable tension between LDP and Byzantine robustness in the stability of the studied algorithm, which translates to the generalization error as proven in [7, Lemma 4.1]. A surprising, yet principled non-monotonic effect on generalization. We sketch the proof of Theorem 3.2 and explain how it extends to the strong privacy regime. We then show that stability under this regime eventually stops increasing and converges to 0 as the privacy guarantee strengthens. The Byzantine attack used in the construction of our lower bounds proceeds in two phases. In the first phase, Byzantine participants send arbitrary vectors to the server (e.g., mimicking a participant or sending 0’s) while collecting the communicated honest gradients over multiple rounds. After accumulating sufficient observations, they perform a membership inference attack (MIA): consistent with the threat model of DP, they know all but one sample (representing the differing sample in stability) and seek to determine whether it is present, triggering the second phase of the attack. In this second phase, Byzantine participants send a malicious vector that is explicitly conditioned on the outcome of the MIA, with the goal of ensuring that it is consistently picked by the SMEA aggregation rule. In our construction, the success of the two phases are independent. That is, the success probability of the MIA, denoted P, is independent of the probability that Byzantine participants successfully fool the SMEA aggregation (i.e., the server). Consequently, as detailed in the proof of Theorem 3.2, we demonstrate that our construction yields a lower bound that is the product of two terms: the MIA success P, that depends on the privacy guarantee, and the instability of the second phase, independent of the privacy guarantee and which we denote by I. This is due to sup E |ℓ(A(S), z) − ℓ(A(S ′ ), z)| ≥ sup E[|ℓ(A(S), z) − ℓ(A(S ′ ), z)| | E] P(E) = I P, z∈Z

(6)

z∈Z

where the event E := {MIA success}, with P(E) = P. Note that I still crucially depends on the privacy noise magnitude since, conditioned on a successful MIA, Byzantine participants can leverage the spectral dispersion of the honest noisy gradients to bias the update in a data-dependent direction. This, however, is capped by the filter (SMEA) at the level of the honest spectral dispersion, qspectral

d i.e., E∥ΣH ∥sp ∈ Θ σDP 1 + n−f . Within the stability analysis of Safe-DGD and our construction, the MIA success probability satisfies, P = P (zα − ∆ < Z ≤ zα ) = Φ(zα ) − Φ(zα − ∆) ≥ ϕ(zα )∆, where Z ∼ N (0, 1) has cumulative distribution function Φ and density ϕ. Here, α ∈ (0, 1) is a fixed false positive rate, with zα defined by P(Z > zα ) = α, and ∆ denotes the worst case sensitivity of 6

local gradients normalized by the standard deviation of the Gaussian noise aggregated over the first step. Importantly, ∆ is directly tied to the (ε, δ)-DP guarantee, scaling as √ ε . ln(1/δ)

Let (εweak , δweak ) denote the privacy parameters associated with the weak privacy regime, defined by √ εweak ∈ Ω(1), and Pweak , Iweak , LBweak the corresponding MIA success probability, instabilln(1/δweak )

ity, and stability lower bound induced by our proof technique (cf. (4) and (5)). The analogous quantities in the strong privacy regime are denoted with the subscript strong. By (6), our construction yields     εweak LBweak = Iweak Pweak ∈ Ω Iweak p ∈ Ω Iweak , ln(1/δweak )
where we used Pweak ∈ Ω √ εweak ∈ Ω(1). This explains why the stability—and conseln(1/δweak )

quently the generalization error [7, Lemma 4.1]—degrades with the noise magnitude in the weak privacy regime. Moreover, we can prove with a Taylor expansion that for small ∆ (i.e., strong privacy regime), we have P ∈ Θ(∆). Hence,   εstrong LBstrong = Istrong Pstrong ∈ Θ Istrong p . ln(1/δstrong ) Eventually, LBstrong vanishes as the privacy guarantee strengthens, i.e., as (ϵ, δ) → (0, 0). While deriving an upper bound that matches LBstrong represents interesting future work, this is only a minor gap to be closed. Indeed, the fact that stability ultimately converges to 0 is well established in the DP literature: our theory can thus be completed via standard DP-to-stability arguments. Specifically, for a ℓ∞ -bounded loss function,1 any (ε, δ)-DP learning algorithm is guaranteed to be ℓ∞ (eε − 1 + δ)-uniformly stable (Lemma 2.2). Note that, although implicit, δ ≤ ε in all practical scenarios. This shows that, assuming εstrong ≤ 1, LBstrong ≤ sup E |ℓ(A(S), z) − ℓ(A(S ′ ), z)| ≤ ℓ∞ (eεstrong −1+δstrong ) ≤ (e+1)ℓ∞ εstrong . (7) z∈Z

∈ Ω(1), or equivalently

ln(1/δ) √ C T := σDP ∈ O(σbase ) with σbase m , the stabilty scales as

q    q f d σDP × Θ γCT n−2f 1 + n−f , and, in the strong privacy regime, it scales as √   ℓ∞ C T ln(1/δ) 1 , σDP × O m

(8)

tight

tightness unknown

In the weak privacy regime √ ε

gen. error

Consequently, stability can be controlled as the minimum between the upper bounds of Theorem 3.1 √ T and the one in Equation (7), which is itself in Õ( mσDP ) when we get rid of constants and log factors. Hence, for small σDP (large ε, weak privacy regime), the bound of Theorem 3.1 is smaller, tight (Theorem 3.2), and it linearly grows with σDP . At some point, σDP becomes large enough (small ε, strong privacy regime) and the second upper bound becomes the smallest one, and it decreases with σDP . This transition highlights a surprising non-monotonic dependence of generalization on the level of privacy noise, as summarized by the following corollary. √ 2C 2T ln(1/δ) Corollary 3.2.1. Assume the setting of Theorem 3.2 and Theorem 2.2. Let σDP = . mε (8) (9) min{(8),(9)}

σbase σthreshold

tight σDP

(9) Figure 1: Generalization error as a function of σDP . which is asymptotically tight in σDP due to (7). In other words, there exists εthreshold ∈ (0, 1) such that, for εstrong ≤ εthreshold , we have LBstrong ∈ Θεstrong (εstrong ) when we consider parameters other than εstrong fixed. Generalization exhibits a similar behavior, following from [7, Lemma 4.1]. Overall, our results offer a comprehensive perspective on the interplay between LDP and Byzantine robustness on generalization error, as differential privacy can be characterized by the performance of MIAs [11] and stability provides a tight control on the generalization error [7, Lemma 4.1].²

We next corroborate our theoretical results empirically, showing that the predicted non-monotonic behavior is also observed in practice. 1 This can be ensured by projecting the parameter onto a compact set Θ after the server update (Line 10 in Algorithm 1).

7

(a) Realization of the Generalization Error (All Runs)

Generalization Error

0.75

(c) Generalization Error by Data Split (Monte Carlo Estimate)

(b) Expected Generalization Error (Monte Carlo Estimate)

0.25

0.3 0.20

0.50 0.25

0.2

0.15

0.1

0.10

0.0

0.00 0.25 0.50 0.75 1.00 2 3

0.1

0.05 Mean ± 1 Std Dev 2 2 2 1 20

21

22

Noise Multiplier ( )

23

24

25

0.00

23

Mean ± 1 Std Error 2 2 2 1 20

0.2 21

22

Noise Multiplier ( )

23

24

25

23

Mean Individual Training Data Splits 2 2 2 1 20 21 22

Noise Multiplier ( )

23

24

25

Figure 2: Synthetic dataset. Impact of LDP on generalization error under Byzantine failures. The Byzantine participant (f = 1) executes the Opt-IPM attack, the server uses SMEA as defense, with γ = 0.4, T = 600, and d = 50. (a) Realizations of the generalization error (as a random variable) demonstrating high variance across all independent runs (variance estimated on all runs). (b) The Monte Carlo estimate of the expected generalization error, where reported variance represents the mean estimation standard error. (c) Expected generalization error stratified by individual training dataset, isolating the variance attributable to data samples versus differential privacy noise.

4

Empirical evaluations

In this section, we empirically validate the non-monotonic behavior predicted by our theory. All simulations are implemented via the ByzFL library [16]. More details and evaluations are presented in Section D. Empirical evaluation settings. For each of the three datasets considered, we consider a common evaluation protocol. While a single training run is inexpensive, estimating expected generalization requires repetitions over datasets, seeds, and noise multipliers, which is the main bottleneck. This motivates the use of a fixed setting with n = 7 participants2 and m = 200 local samples per honest participant. The model test loss is evaluated on a held-out test set of Ntest = 10000 samples. We consider three classification tasks: (i) synthetic data following [25, 27] with logistic regression; (ii) MNIST [24] with logistic regression; and (iii) CIFAR-10 [21] with a convolutional network. All experiments use deterministic initialization and Safe-DGD with learning rate γ, T iterations, SMEA aggregation, and Gaussian noise σDP = σ × σbase , calibrated via a multiplier σ, which √ serves as a proxy for the privacy level and scales the base noise σbase := 2Cm2T . We evaluate σ ∈ {0.125, 0.25, 0.5, 1, 2, 4, 8, 16, 32}, reporting both individual realizations and Monte Carlo estimates over datasets and seeds. Byzantine participants (f = 1 unless otherwise stated) use a state-of-the-art Opt-IPM attack [37], relying on line search at each iteration to compute the most damaging perturbation bypassing SMEA. For (i)–(ii), the objective is convex and smooth. To be consistent with our theory, we enforce Lipschitzness and smoothness by L2 -normalizing features (∥x∥2 ≤ 2) [38, Proposition F.1], and bounded loss by projecting parameters onto a ball of radius 100 after updates, enabling calibrated privacy noise. For CIFAR-10, gradients are clipped at 3.0 and parameters layerwise projected onto a ball of radius 10. Below, we present the results, along with additional experiment-specific details. Results and discussion. Our empirical results in Figures 2 to 5 show consistent and interpretable trends across settings. For logistic regression on synthetic data (Figures 2 and 3) and MNIST (Figure 4), which satisfy the assumptions of our theory, the observed dynamics closely match our predictions. On CIFAR-10 (Figure 5), where we train a CNN and thus operate outside the convex setting covered by our analysis, the behavior remains qualitatively consistent and exhibits meaningful structure despite more challenging interpretation, suggesting promising directions for further investigation. Across Figures 2 and 4, the dependence on the noise multiplier aligns with our bounds: it grows linearly in the weak privacy regime. Figure 3 further highlights other dynamics: in the weak privacy 2 The computational cost of SMEA scales poorly with n, hence the small number of participants.

8

Generalization Error

0.16

Byzantine participants

0.6

f=1 f=2 f=3

0.5 0.4

Dimensionality

0.025

d = 12 d = 25 d = 50

0.14 0.12

0.020

0.10

0.015

0.3

0.08

0.010

0.2

0.06

0.005

0.1

0.04

0.000

0.0

0.02

0.005

23

22

21

20

21

22

Noise Multiplier ( )

23

25

24

23

22

21

20

21

22

Noise Multiplier ( )

23

24

25

Heterogeneity = =1 = =5 = = 10

23 22 21

20

21

22

Noise Multiplier ( )

23

24

25

Figure 3: Synthetic dataset. Absolute expected generalization error under variations of parameters. (a) Left: varying f ∈ {1, 2, 3} for fixed d = 50. (b) Middle: varying d ∈ {12, 25, 50} for fixed f = 1. (c) Right: varying heterogeneity for fixed f = 1, where α, β are defined in [25] (the larger α and β, the more heterogenous). All evaluations share identical baseline parameters T = 200 and γ = 0.2. 0.20

(a) Realization of the Generalization Error (All Runs) 0.06

Generalization Error

0.15 0.10

0.05

0.05

0.04

0.00

0.03

0.05

0.02

0.10 0.15 0.20 2 3

(c) Generalization Error by Data Split (Monte Carlo Estimate)

(b) Expected Generalization Error (Monte Carlo Estimate) 0.06 0.04 0.02

0.01 Mean ±1 Std Dev 22 21

0.00 20

21

22

Noise Multiplier ( )

23

24

25

23

Mean ±1 Std Error 22 21

0.00 20

21

22

Noise Multiplier ( )

23

24

25

23

Mean Individual Training Data Splits 22 21 20 21 22

Noise Multiplier ( )

23

24

25

Figure 4: MNIST. Analogous to Figure 2 with γ = 0.4, T = 400, f = 1. regime, higher dimension consistently leads to worse generalization, in line with the predicted ordering, although the dependence departs from the square-root behavior suggested by the bound. In the strong privacy regime, the behavior becomes less regular, suggesting the presence of multiple interacting effects. The dependence on the Byzantine fraction exhibits richer structure. The results are consistent with the change in regime in our bounds, which distinguish between nf ≤ 31 (4) (f = 1, 2) and 13 ≤ nf < 12 (5) (f = 3). For each fixed f , the behavior remains non-monotonic, as f predicted, while the regime transition depends on f . Varying n−f , the dynamic is consistent with our bounds (inherited from [7]), including a pronounced increase in attack severity at f = 3. Finally, the larger the heterogeneity, the less the model generalize. Overall, these results support the qualitative trends of our analysis while revealing additional structure not captured by the bounds. As predicted, we observe an initial increase in generalization error under small noise (weak privacy), followed by a regime switch where the error decreases as noise increases (strong privacy). We leave several directions future work, including alternative optimizers, varying number of participants, different aggregation rules, and relaxing assumptions beyond convexity.

5

Conclusion

Prior optimization-focused theory overlooks the joint impact of LDP and Byzantine robustness on generalization, leaving an incomplete picture. We close this gap and uncover a surprising non-monotonic, two-phase behavior. Through tight stability bounds, we show that privacy noise actively degrades the generalization error in weak privacy regime, yet drives it to zero as privacy strengthens. Our theory offers several predictive insights and provides a qualitative and quantitative characterization of the transition between the two regimes. We moreover corroborate these findings in empirical evaluations, validating the usefulness of our bounds as predictive of the generalization error dynamics accross multiple critical parameters. While these findings offer a theoretical counterpoint to the optimization trilemma, practical privacy budgets typically lie in the weak privacy regime. Thus, achieving privacy, robustness, and generalization simultaneously in practical distributed learning is fundamentally constrained. Moving forward, this necessitates the exploration of ways to systematically relax the threat models, whether by integrating cryptographic primitives to bound misbehaviors [14, 7], or by 9

(a) Total Realizations

(b) Expected Performance

(c) Variance by Data Split

0.150

Generalization Error

0.4 0.2 0.0

0.125

0.20

0.100

0.15

0.075

0.10

0.050

0.05

0.025

0.00

0.000

0.2

0.05

0.025 23

22

21

20

21

22

Noise Multiplier ( )

23

24

25

Split 0 Split 1 Split 2 Split 3 Split 4

0.25

23

22

21

20

21

22

Noise Multiplier ( )

23

24

25

0.10 2 3

22

21

20

21

22

Noise Multiplier ( )

23

24

25

Figure 5: CIFAR-10. Analogous to Figure 2 with γ = 0.1, T = 400, f = 1. The convolutional network architecture consists of three convolutional layers (16, 32, 64 filters), ReLU activations, max-pooling, and a 1024-dim feature map followed by fully connected layers (128, 64, 10). relaxing LDP as in [3], where a shared randomness seed among honest clients is assumed, enabling correlated noise mechanisms that yield improved optimization guarantees.

Acknowledgments and Disclosure of Funding The work of Thomas Boudou and Aurélien Bellet is supported by grant ANR 22-PECY-0002 IPOP (Interdisciplinary Project on Privacy) project of the Cybersecurity PEPR.

10

References [1] Y. Allouah, S. Farhadkhani, R. Guerraoui, N. Gupta, R. Pinot, and J. Stephan. Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In AISTATS, 2023. [2] Y. Allouah, R. Guerraoui, N. Gupta, R. Pinot, and J. Stephan. On the privacy-robustness-utility trilemma in distributed learning. In ICML, 2023. [3] Y. Allouah, R. Guerraoui, and J. Stephan. Towards trustworthy federated learning with untrusted participants. In ICML, 2025. [4] A. Attia and T. Koren. Algorithmic instabilities of accelerated gradient descent. NeurIPS, 2021. [5] F. Bach. Learning Theory from First Principles. Adaptive Computation and Machine Learning series. MIT Press, 2024. [6] S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013. [7] T. Boudou, B. Le Bars, N. Gupta, and A. Bellet. Byzantine failures harm the generalization of robust distributed learning algorithms more than data poisoning. arXiv preprint arXiv:2506.18020v2, 2025. [8] O. Bousquet and A. Elisseeff. Stability and generalization. JMLR, 2:499–526, 2002. [9] W. G. Cochran. The distribution of quadratic forms in a normal system, with applications to the analysis of covariance. Mathematical Proceedings of the Cambridge Philosophical Society, 30(2):178–191, 1934. [10] L. Devroye and T. Wagner. Distribution-free performance bounds for potential function rules. IEEE Transactions on Information Theory, IT-25:601 – 604, 10 1979. [11] J. Dong, A. Roth, and W. J. Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 84(1):3–37, 2022. [12] J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Local privacy, data processing inequalities, and statistical minimax rates. arXiv preprint arXiv:1302.3203, 2013. [13] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, pages 265–284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. [14] S. Farhadkhani, R. Guerraoui, O. Villemaud, et al. An equivalence between data poisoning and byzantine gradient attacks. In ICML, 2022. [15] A. Girgis, D. Data, S. Diggavi, P. Kairouz, and A. Theertha Suresh. Shuffled model of differential privacy in federated learning. In AISTATS, 2021. [16] M. González, R. Guerraoui, R. Pinot, G. Rizk, J. Stephan, and F. Taïani. Byzfl: Research framework for robust federated learning. arXiv preprint arXiv:2505.24802, 2025. [17] R. Guerraoui, N. Gupta, and R. Pinot. Byzantine machine learning: A primer. ACM Computing Surveys, 56(7), 2024. [18] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In ICML, 2016. [19] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, R. G. L. D’Oliveira, H. Eichner, S. E. Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He, L. He, Z. Huo, B. Hutchinson, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konecný, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Y. Liu, P. Mittal, M. Mohri, R. Nock, A. Özgür, R. Pagh, H. Qi, D. Ramage, R. Raskar, M. Raykova, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, J. Wang, L. Xiong, Z. Xu, Q. Yang, F. X. Yu, H. Yu, and S. Zhao. Advances and open problems in federated learning. Foundations and Trends® in Machine Learning, 14(1–2):1–210, 2021. [20] S. P. Karimireddy, L. He, and M. Jaggi. Learning from history for byzantine robust optimization. In ICML, 2021. [21] A. Krizhevsky. Learning multiple layers of features from tiny images. 2009. [22] L. Lamport, R. Shostak, and M. Pease. The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382–401, 1982.

11

[23] B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, 28, 10 2000. [24] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998. [25] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization in heterogeneous networks. MLSys, 2020. [26] G. Neu, G. K. Dziugaite, M. Haghifam, and D. M. Roy. Information-theoretic generalization bounds for stochastic gradient descent. In COLT, 2021. [27] M. Noble, A. Bellet, and A. Dieuleveut. Differentially private federated learning on heterogeneous data. In AISTATS, 2022. [28] A. Ramezani-Kebrya, K. Antonakopoulos, V. Cevher, A. Khisti, and B. Liang. On the generalization of stochastic gradient descent with momentum. JMLR, 25(22):1–56, 2024. [29] R. Reshef and K. Y. Levy. Private and federated stochastic convex optimization: Efficient strategies for centralized systems. In ICML, 2024. [30] W. Rogers and T. Wagner. A finite sample distribution-free performance bound for local discrimination rules. The Annals of Statistics, 6, 05 1978. [31] M. Rudelson and R. Vershynin. Hanson-wright inequality and sub-gaussian concentration. 2013. [32] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. JMLR, 11(90):2635–2670, 2010. [33] V. Vapnik and A. Chervonenkis. Theory of pattern recognition. Nauka, 1974. [34] R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. [35] D. Wang, M. Gaboardi, A. Smith, and J. Xu. Empirical risk minimization in the non-interactive local model of differential privacy. JMLR, 21(200):1–39, 2020. [36] Y.-X. Wang, J. Lei, and S. E. Fienberg. Learning with differential privacy: Stability, learnability and the sufficiency and necessity of erm principle. JMLR, 17(183):1–40, 2016. [37] C. Xie, O. Koyejo, and I. Gupta. Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation. In UAI, 2020. [38] J. Ye and R. Shokri. Differentially private learning needs hidden state (or much faster convergence). In NeurIPS, 2022.

12

A

Stability or DP implies generalization in robust distributed learning

In this section, we focus on the formal link between uniform stability and generalization under Byzantine failures. The proof follows classic arguments [8]. Proposition A.1. Consider the setting described in Section 2. let A an ε-uniformly stable (randomized) distributed algorithm. Then, bH (A(S))]| ≤ ε. |ES,A [RH (A(S)) − R Proof. Recall that S denotes the collective dataset of honest participants. Let S ′ = {z ′(i,j) , i ∈ H, j ∈ {1, . . . , m}} be another independently sampled dataset for honest participants where for all i ∈ H, Di′ = {z ′(i,1) , . . . , z ′(i,m) } is composed of m i.i.d. data points (or samples) drawn from distribution pi . Let S (i,j) be a neighboring dataset of S with only a single differing data sample z ′(i,j) at index (i, j) ∈ H × {1, . . . , m}. Then,   m X 1 X 1 (i,j) ′(i,j) bH (A(S))] = ES,S ′ ,A  ES,A [R ℓ(A(S ), z ) |H| m j=1 i∈H   m X X 1 1 ℓ(A(S), z ′(i,j) ) + δ = ES,S ′ ,A  |H| m j=1 i∈H

= ES,A [RH (A(S))] + δ with 

 m h i X 1 X 1 δ = ES,S ′  EA ℓ(A(S (i,j) ), z ′(i,j) ) − ℓ(A(S), z ′(i,j) )  |H| m j=1 i∈H   m h i X 1 X 1 ≤ ES ES ′  sup EA ℓ(A(S (i,j) ), z) − ℓ(A(S), z)  ≤ ε |H| m j=1 z∈Z i∈H

Substituting from the above equation proves the lemma. A.1

Differential privacy implies stability

We demonstrate that a strong differential privacy constraint is sufficient to establish non-oblivious stability result, even though implementing such strong differential privacy may be impractical. As a result, each of our bound should be interpreted as min{ℓ∞ , (1), (2)}, where (1) represents the bound on uniform algorithmic stability implied by the privacy constraint, and (2) corresponds to the bound on uniform algorithmic stability demonstrated through the sensitivity analysis of a particular iterative optimization algorithm. The following result is proven in [36]. Lemma 2.2. Any (ε, δ)-DP algorithm is ℓ∞ (eε − 1 + δ)-uniformly stable under an ℓ∞ -bounded loss. Proof. For any S and S ′ two neighboring datasets and any x ∈ X . Let the probability density (with respect to the Lebesgue measure) defined by A(S) and A(S ′ ) be p and p′ respectively. We define the event E = {θ ∈ Θ; p(θ) ≥ p′ (θ)}. Then we can bound the uniform algorithmic stability as follows Z Z Eθ∼A(S) [ℓ(θ, x)] − Eθ∼A(S ′ ) [ℓ(θ, x)] = ℓ(θ, x)p(θ)dθ − ℓ(θ, x)p′ (θ)dθ θ∈Θ θ∈Θ Z = ℓ(θ, x) (p(θ) − p′ (θ)) dθ θ∈Θ Z  ′ ≤ max{ ℓ(θ, x) (p(θ) − p (θ)) dθ , θ∈Θ

Z θ∈Θ

13

+

ℓ(θ, x) (p(θ) − p′ (θ)) dθ

 } −

The definition of DP is symmetric, so that we have the same bound irrespective of the fact that cumulative positive quantity is greater than cumulative negative quantity or the opposite. We show it here for the positive part. Z  ′ Eθ∼A(S) [ℓ(θ, x)] − Eθ∼A(S ′ ) [ℓ(θ, x)] ≤ ℓ(θ, x)p(θ) − p (θ)dθ θ∈Θ + Z = ℓ(θ, x) (p(θ) − p′ (θ))+ dθ ℓ≥0 θ∈Θ Z ≤ sup ℓ(θ, x) (p(θ) − p′ (θ)) dθ x∈X ,θ∈E

E

≤ ℓ∞ (P(A(S) ∈ E) − P(A(S ′ ) ∈ E)) ≤ ℓ∞ ((eε − 1)P(A(S ′ ) ∈ E) + δ) ≤ ℓ∞ (eε − 1 + δ) ε>0

Remark A.1. For the bound to be meaningful, we need eε − 1 + δ ≤ 1, that is ε ≤ ln (1 + (1 − δ)). This is generally a difficult condition to hold.

B

Regularity assumptions and expansivity results

To analyze the stability of iterative optimization algorithms, we typically rely on regularity assumptions on the loss function. We begin by stating standard regularity assumptions [18] used throughout the paper, along with classical results that follow from them. Definition B.1 (Regularity assumptions). Let ℓ : Θ → R differentiable, Θ ⊂ Rd . (i) ℓ is C−Lipschitz continuous (or C−Lipschitz) if there exists C > 0 such that, ∀u, v ∈ Θ,

|ℓ(u) − ℓ(v)| ≤ C∥u − v∥2 .

This property is equivalent to the norm of the gradient of ℓ being uniformly bounded by C. (ii) ℓ is L−Lipschitz smooth (or L−smooth) if its gradient is L-Lipschitz. This is equivalent to the following smoothness inequality: ∀u, v ∈ Θ,

ℓ(u) ≤ ℓ(v) + ⟨∇ℓ(v), u − v⟩ +

L ∥u − v∥22 . 2

(10)

(iii) ℓ is convex if and only if, ∀u, v ∈ Θ, ⟨∇ℓ(u) − ∇ℓ(v), u − v⟩ ≥ 0. Moreover it is µ−strongly convex if there exists µ > 0 such that, ∀u, v ∈ Θ,

ℓ(u) ≥ ℓ(v) + ⟨∇ℓ(v), u − v⟩ +

µ ∥u − v∥22 . 2

We note that for a strongly convex function to have bounded gradients, it must be defined on a convex compact set, which then implies boundedness of both the loss and the gradient. To ensure this, we can either penalize the problem or restrict the parameter domain and apply an Euclidean projection at every step. Throughout the paper, we will tacitly assume this when referring to strongly convex functions, which does not limit the applicability of our analysis since the projection does not increase the distance between projected points. Notably, convex and L−smooth functions satisfy an important property known as co-coercivity (see Proposition 5.4 in [5]). Lemma B.1. Let ℓ : Θ → R differentiable, Θ ⊂ Rd . If ℓ is a convex and L−smooth function, then it satisfies the co-coercivity inequality, ∀u, v ∈ Θ,

⟨∇ℓ(u) − ∇ℓ(v), u − v⟩ ≥ 14

1 ∥∇ℓ(u) − ∇ℓ(v)∥22 . L

(11)

We focus on robust variants of distributed gradient descent and stochastic gradient descent. Below we recall properties of the one-step update. Let A ∈ {GD, SGD}, ℓ : Θ → R differentiable and γ > 0, we denote: 1 X (i) GA g . γ (θ) := θ − γ |H| i∈H

Here, for each i ∈ H, g (i) denotes the exact gradient ∇ℓ(θ) in the case of GD, or an unbiased estimate thereof—effectively computed with a sample from the local dataset—in the case of SGD. We recall the expansiveness definition for an update rule from [18, Definition 2.3]. Definition B.2. An update rule G : Θ → Θ is said to be η−expansive if for all θ, ω ∈ Θ, ∥G(θ) − G(ω)∥2 ≤ η∥θ − ω∥2 . A straightforward extension of [18, Lemma 3.6] to the distributed setting yields: Lemma B.2. Let A ∈ {GD, SGD} and γ > 0. Assume ∀z ∈ Z, ℓ(·, z) : Θ → R is L-smooth, Then GA −expansive, with the following expansive coefficient, γ is ηGA γ (i) ηGA = (1 + γL). γ (ii) Assume in addition that ℓ is convex. Then, for any γ ≤ L2 , ηGA = 1. γ Lµ 2 (iii) Assume in addition that ℓ is µ-strongly convex. Then, for any γ ≤ µ+L , ηGA = (1 − γ µ+L ). γ 1 For γ ≤ L , since we have L ≥ µ, we can simplify the contractive constant to ηGA = γ (1 − γµ).

ηGA is referred to as the expansivity coefficient of A with learning rate γ. γ

C

Defered proofs from section 3

In what follows, we first provide supporting lemmas, to then prove Theorems 3.1 and 3.2. C.1

Supporting lemmas

For clarity and simplicity, we chose to emphasize our results under the broad bounded gradient assumption (i.e. Lipschitz-continuity of the loss function) in the main text. In this section, we present results derived under refined assumptions—namely, bounded heterogeneity and bounded variance—in place of the more general bounded gradient condition. These assumptions are more commonly used in the optimization literature (as opposed to the generalization literature). We formally define these assumptions below. Assumption C.1 (Bounded heterogeneity). P 1 2 2 b b i∈H ∥∇Ri (θ) − ∇RH (θ)∥2 ≤ G . |H|

There exists G < ∞ such that for all θ ∈ Θ:

Assumption C.2 (Bounded variance). There exists σ < ∞ such that for each honest participant P 1 2 2 b i ∈ H and all θ ∈ Θ: m x∈Di ∥∇ℓ(θ; x) − ∇Ri (θ)∥2 ≤ σ . As shown in the following, our analysis techniques can yield tighter bounds when assuming bounded heterogeneity and bounded variance. However, we note that these bounds do not provide additional conceptual insights within the scope of our discussion. Indeed, within the uniform stability framework, if we assume only bounded gradients and nothing more, there exist distributed learning settings where G is a constant multiple of the Lipschitz constant C. For instance, consider a scenario where half of the honest participants produce gradients with norm C, and the other half produce gradients with norm −C; in this case, G would be C. We will need an adaptation of the Lemma D.1 from [2] that use a concentration argument on the empirical covariance matrix of Gaussian random variables: Lemma C.1. Consider the setting described in Section 2. Suppose Assumptions C.1, C.2. Then, for every t ∈ {1, . . . , T − 1} we have 1 X (i) d (i) 2 EA [λmax ( (e gt − get )(e gt − get )T )] ≤ 2σ 2 + 72σDP (1 + ) + G2 |H| n−f i∈H

15

2 ≤ 3C 2 + 72σDP (1 +

d ) n−f

We note that, in the absence of momentum, the upper bound remains time-independent. Proof. The proof leverages the ability to evaluate the expectation of the controllable noise— specifically, the differential privacy noise and the noise arising from random sample selection—while conditioning on the uncontrollable noise introduced by adversarial participants. The bound being independent of the latter noise, we establish the result by taking the total expectation. Let t ∈ {0, . . . , T − 1}, we recall: (i) 1 X 1 X (i) (i) get = ∇ℓ(θt , x(i,Jt ) ) + ξt get = |H| |H| i∈H

i∈H

(i)

(i)

2 with ξt ∼ N (0, σDP Id ) and Jt ∼ U({1, . . . , m}) and an alternative formulation of the maximal eigenvalue 1 X (i) 1 X (i) (i) ∆t = λmax ( (e gt − get )(e gt − get )T ) = sup ⟨v, get − get ⟩2 |H| |H| ∥v∥2 ≤1 i∈H

i∈H

We decompose (i)

(i)

bi (θt ) + ∇R bi (θt ) − ∇R bH (θt ) + ∇R bH (θt ) − get get − get = get − ∇R so that we have (i) bi (θt ) + ∇R bH (θt ) − get ⟩2 bi (θt ) − ∇R bH (θt )⟩2 + ⟨v, get(i) − ∇R ⟨v, get − get ⟩2 = ⟨v, ∇R (i)

bi (θt ) + ∇R bH (θt ) − get ⟩⟨v, ∇R bi (θt ) − ∇R bH (θt )⟩ + 2⟨v, get − ∇R Upon averaging, taking the supremum over the unit ball, and then taking total expectations, we get: # " # " 1 X 1 X (i) 2 2 b b ⟨v, get − get ⟩ = E sup ⟨v, ∇Ri (θt ) − ∇RH (θt )⟩ E sup ∥v∥2 ≤1 |H| i∈H ∥v∥2 ≤1 |H| i∈H " # 1 X (i) 2 b b + E sup ⟨v, get − ∇Ri (θt ) + ∇RH (θt ) − get ⟩ ∥v∥2 ≤1 |H| i∈H " # 1 X (i) bi (θt ) − ∇R bH (θt )⟩ bi (θt ) + ∇R bH (θt ) − get ⟩⟨v, ∇R + 2E sup (12) ⟨v, get − ∇R ∥v∥2 ≤1 |H| i∈H

We show that the last term in eq. (12) is non-positive. In fact, with M = N + N T , X (i) bi (θt ) + ∇R bH (θt ) − get )(∇R bi (θt ) − ∇R bH (θt ))T N= (e g t − ∇R i∈H

and using Lemma D.4 from [2]: " # X (i) bi (θt ) + ∇R bH (θt ) − get ⟩⟨v, ∇R bi (θt ) − ∇R bH (θt )⟩ E sup 2 ⟨v, get − ∇R ∥v∥2 ≤1

i∈H

" =E

# sup ⟨v, M v⟩ ≤ 9d sup E [⟨v, M v⟩]

∥v∥2 ≤1

∥v∥2 ≤1

 = 9d sup E 2 ∥v∥2 ≤1

 X i∈H

(i)

bi (θt ) + ∇R bH (θt ) − get |θt ]⟩⟨v, ∇R bi (θt ) − ∇R bH (θt )⟩ ⟨v, E[e g − ∇R {z } | t =0

We now bound the second term in eq. (12):

16

"

# 1 X (i) 2 b b E sup ⟨v, get − ∇Ri (θt ) + ∇RH (θt ) − get ⟩ ∥v∥2 ≤1 |H| i∈H " # 1 X (i) (i) bi (θt ) + ∇R bH (θt ) − g t ⟩2 + ⟨v, ξt − ξ t ⟩2 2E sup ≤ ⟨v, gt − ∇R 2ab≤a2 +b2 ∥v∥2 ≤1 |H| i∈H " # 1 X (i) (i) 2 2 bi (θt )⟩ + ⟨v, ξt ⟩ ≤ 2E sup ⟨v, gt − ∇R bias-variance ∥v∥2 ≤1 |H| i∈H decomposition   " #   1 X 1 X (i) (i) bi (θt )∥2 ] ≤ 2 E sup ⟨v, ξt ⟩2 +2E  EJ (i) [∥gt − ∇R 2   t |H| ∥v∥2 ≤1 |H| i∈H {z } i∈H | | {z } ≤σ 2 2 (1+ d ) Lemma D.6 from [2] ≤ 36σDP n−f

And finally we bound the first term in eq. (12) with assumption C.1: " # 1 X 1 X 2 bi (θt ) − ∇R bH (θt )⟩ ≤ bi (θt ) − ∇R bH (θt )⟩2 sup E sup ⟨v, ∇R ⟨v, ∇R ∥v∥2 ≤1 |H| i∈H θ∈Θ,∥v∥2 ≤1 |H| i∈H 1 X bi (θt ) − ∇R bH (θt )∥22 ∥∇R ≤ sup θ∈Θ |H| i∈H

≤ G2

C.2

Proof of Theorem 3.1

Theorem 3.1. Consider the setting described in Section 2. Let σDP > 0 and γ ≤ L1 . Suppose ∀z ∈ Z, ℓ(·; z) C-Lipschitz and L-smooth. Then A is (ε, δ) − DP and, (i) If ℓ(·; z) is convex ∀z ∈ Z, then the uniform stability of A is upper bounded by s ! √ √ σDP √ d 1 2 1+ 2γC T + 3κ + 2 18 κ . (13) (n − f )m C n−f (ii) If ℓ(·; z) is µ-strongly convex ∀z ∈ Z, then the uniform stability of A is upper bounded by s ! √ √ √ σDP 1 2C 2 d + 3κ + 2 18 κ . (14) 1+ µ (n − f )m C n−f Proof. The proof follows exactly all the arguments of [7, Theorem 3.1], the only difference is the use of Theorem C.1. C.3

Proof of Theorem 3.2

In this appendix, we present the proof of Theorem 3.2 first by focusing on the case d = 1, as the extension to d > 1 is more technical yet follows an identical proof structure, making the d = 1 case sufficient to convey the fundamental insight and construction. We then provide the proof of Theorem 3.2 fot the case d > 1. C.3.1

Proof for d = 1.

Theorem 3.2. Consider the setting in
Section 2 with full batch and the SMEA aggregation rule. Suppose d = 1, T ∈ O ecmin (n−f −1) , where cmin is a problem-dependent constant, √ ε ∈ ln(1/δ)

17

√ 2C 2T ln(1/δ) Ω(1) and σDP = . Then there exist ℓ ∈ RΘ×Z such that ∀z ∈ Z, ℓ(·; z) is C-Lipschitz, mε L-smooth and convex, such that the uniform stability of A is lower bounded by s !! 1 f f σ DP 2 Ω γC T + + . (15) (n − f )m n − 2f C n − 2f If we moreover assume n3 < f < n2 , the uniform stability of A is lower bounded by s s !! f f σDP 1 2 . Ω γC T + + (n − f )m n − 2f n − 2f C

(16)

Proof. Let d = 1, n > 0, H = {1, . . . , n − f } and let S, S ′ ∈ Z (n−f )m neighboring datasets where every sample equal 0, except for one sample in S ′ from the participant 1, equal to C. Let (i) 2 ℓ : (θ, z) → ℓ(θ; z) = θz 3 . For i ∈ H := {1, . . . , n − f }, 0 ≤ t ≤ T , let ξt ∼ N (0, σDP ) be independent random gaussian noise. Byzantine participants trigger. We analyze two attacker capabilities. First, if Byzantine participants have access to the random seeds of honest participants, they can circumvent the differential privacy guarantee. Indeed, this knowledge allows them to perfectly reconstruct the added noise, subtract it, and deterministically identify, at the first iteration, whether the first participant’s true gradient was C m or 0. In the alternative scenario, where attackers only observe the final noisy gradient (lacking the seed), they cannot perform this deterministic inference. We must then rely on a statistical test to bound their success probability to distinguish the two cases. We explain a possible test in what follows. Let ptest ∈ (0, 1). We define the behavior of Byzantine participants based on a trigger condition. This trigger is determined by performing a gaussian mean hypothesis test on the first ntest := ptest T sample, collected during an initial fraction of the total T iterations. The test evaluates whether the sample mean corresponds to hypothesis H0 (mean 0, equivalently the dataset is S) or to hypothesis C 2 H1 (mean m , equivalently the dataset is S ′ ), assuming a known variance σDP . This test processes ζ̄ Pntest (1) 1 C ¯ ¯ ¯ which evaluates at m + ξ under H1 , and evaluates at ξ under H0 , where ξ = ntest t=1 ξt . Overall, the Byzantine participants undergo a membership inference attack to know whether the gradients (1) (1) ′(1) (1) C from participant 1 equals gt = ξt or gt = m + ξt , i.e whether the dataset is S or S ′ . The decision is made depending on a trigger value ctrigger , reject H0 if ζ > ctrigger , else accept H0 . We denote Z ∼ N (0, 1) a standard gaussian random variable, and zα ∈ R the value such that P(Z > 2 σDP ), hence setting ctrigger = zα √σnDPtest , zα ) = α, α ∈ (0, 1). Conditioned on H0 , ζ|H0 ∼ N (0, ntest P (reject H0 |H0 ) = P (ζ > ctrigger |H0 ) = P (Z > zα ) = α. Let denote E1 the event that the Byzantine workers successfully infer the underlying datasets from the gradient statistics (successful MIA). Under the optimal hypothesis test, we have n o n o C E1 = ξ¯ does not trigger H0 rejection ∩ shifting ξ¯ by triggers H0 rejection m o n o n C > ctrigger = ξ¯ ≤ ctrigger ∩ ξ¯ + m n o C = ctrigger − < ξ¯ ≤ ctrigger . m And, n   o n o C C P (E1 ) = P = P ctrigger − ξ¯ ≤ ctrigger ∩ ξ¯ + > ctrigger < ξ¯ ≤ ctrigger m m   √ C ntest = P zα − < Z ≤ zα mσDP 3We only require the gradient to be zero when z = 0 and C for the perturbed data.

18

  √ ε ptest = P zα − p < Z ≤ zα . 2 2 ln(1/δ) p This means that P (E1 ) ∈ Ω(1) if and only if there exist a constant k such that ε ≥ k ln(1/δ). Byzantine participants behavior. We assign the following behavior (Algorithm 2) to the Byzantine participants i ∈ {n − f + 1, n}, for t ≥ ntest + 1. Algorithm 2 Byzantine Participant Behavior # β (defined below) depends on f and n if ζ̄ > ctrigger then return β σDP else return −β σDP That is, depending on the input ζ̄, which itself depends only on the observed noisy gradients, the Byzantine participants bias the trajectory toward either positive or negative values. In what follows, we decompose our analyze depending on whether the Byzantine participants participants a successful MIA (i.e., infer whether the dataset is S or S ′ successfully) in the two coupled optimization trajectories (E1 ), or not (E1c ). (1)′

(i) Under E1 and the trajectory produced by S ′ (i.e., with gt

1 = m

Pm

j=1 z

(1,j)′

(1)

+ ξt

=

(1) C m + ξt ), the Byzantine participants favor the positive noises. This is possible because of

similar computations as in [7, Theorem 3.2]. Following this reasoning, we set the Byzantine values to be (i) ∀i ∈ {n − f + 1, . . . , n}, t ∈ {ntest + 1, . . . , T }, gt := βσDP ,

where 1 β := 2

s

(n − f − 1)(n − f ) . f (n − 2f )

In what follows, we show that, with high probability (i)

(i)

for t ∈ {ntest + 1, . . . , T }, Var({gt }i∈St ) ≤ Var({gt }i∈H ), (1)

(n)

where St = {n − f + 1, . . . , n} ∪ Selectn−2f (H), i.e. SMEA(gt , . . . , gt ) = P (i) 1 i∈St gt This is ensured by a concentration argument and the fact that n−f h i n−f −1 h i (i) (i) 2 E Var({gt }i∈H ) = σDP > E Var({gt }i∈St ) . n−f We demontrate this rigourously in the following points. (a) First, we compute the last expectation, h i 3 h i (i) (i) E Var({gt }i∈St ) ≤ E Var({gt }i∈H ) 4 In fact, we use the following indentity " # h i 2 1 X (i) (i) E Var({gt }i∈St ) = E (gt − ḡSt ) n−f i∈St " # X (i) 2   1 E gt − E ḡS2 t = n−f i∈St " # X (i) 2 1 2 = E gt − Var(ḡSt ) − E [ḡSt ] , n−f i∈St

19

and compute the three terms separetely. Let assume 1 ∈ St (we simply take C = 0 otherwise), " X

E

(i) 2 gt

#

 =

i∈St

=

C2 2 + σDP m2



2 2 + (n − 2f − 1)σDP + f β 2 σDP

C2 2 + σDP n − 2f + f β 2 . 2 m

f C Moreover, E [ḡSt ] = n−f βσDP + (n−f )m , and by independence

Var(ḡt ) =

n − 2f 2 1 2 (n − 2f ) Var(N (0, σDP )) + Var(f βσDP ) = σ 2 (n − f ) (n − f )2 DP

As a result,   h i n − 2f f2 f n − 2f (i) 2 2 2 E Var({gt }i∈St ) = σDP − β + β − n−f n−f (n − f )2 (n − f )2   C C/m (n − f − 1) − 2f βσDP . + (n − f )2 m For clarity, our analysis will focus on the case where 1 ∈ / St . The alternative scenario, C 1 ∈ St , introduces an additional cross-term proportional to (n − f − 1) m − 2f βσDP due to the modified gradient at participant 1. A detailed sign analysis of this term (which is typically negative) is not central to our main argument and does not materially alter the proof’s conclusion. We therefore proceed with the representative case where 1 ∈ St . Moreover,   h i f (n − 2f ) (i) 2 n − f − 1 n − 2f + β2 E Var({gt }i∈St ) ≤ σDP n−f n−f (n − f − 1)(n − f )   n − f − 1 n − 2f 1 2 = σDP + n−f n−f 4    3 f n − f − 1 1 2 = σDP − − n−f 4 n−f 2 h i 3 2 n−f −1 (i) ≤ σDP < E Var({gt }i∈H ) . 4 n−f (b) Second, we control with high probability that SMEA chooses St when 1 ∈ / St , the (H) (i) case 1 ∈ St follows similarly. Let denote gt := (gt )i∈H and, by the Cochran’s Theorem [9], Yt :=

2 1 X  (i) g − ḡ = t t 2

σDP

i∈H

1 2 σDP

(H) ⊺

gt

(H)

Pn−f gt

=

n−f X−1

(i) 2

Yt

∼ χ2n−f −1 ,

i=1

(i) − 1}, Yt

where ∀i ∈ {1, . . . , n − f ∼ N (0, 1), χ2n−f −1 is the chi-squared 1 distribution with n − f − 1 degree of freedom, Pn−f = In−f − n−f 1n−f 1⊺n−f is an orthogonal projection matrix onto the n − f − 1-dimensional subspace of vectors whose components sum to zero, In−f is the identity matrix of size (n − f ) × (n − f ), and 1n−f the vector of size n − f with every entry equal to 1. Hence, we have from [23, Lemma 1], for any s ≥ 0 s2

P (Yt ≤ n − f − 1 − s) ≤ e− 4(n−f −1) , (i)

that is, because

Var({gt }i∈H ) n−f −1 2 n−f σDP

Yt 1 n−f −1 2 = n−f −1 , we have for s = 8 n−f σDP

 
n−f −1 2 7n−f −1 2 c := P Var({gt(i) }i∈H ) ≤ P E2,t σDP − s = σDP n−f 8 n−f 20

−

≤e and  P

(n−f )2 s2 4(n−f −1)σ 4 DP

= e−

n−f −1 256

,



T −ntest  n−f −1   n−f −1 ∈ Ω(1) if on only if T ∈ O e 256 . E2,t  ≥ 1 − e− 256

\ t∈{ntest +1,...,T }

(c) Finally, we control the variance which the Byzantine participant vectors with  include  (i) := h (g ) t i∈H∩S t t high probability. Let denote gt := the vector containing every bt := βσDP 1f (i) values from {gt }i∈St . Then 2 1 X (i) 1 (gt − ḡSt ) = g ⊺ Pn−f gt n−f n−f t i∈St   1 1 ⊺ ⊺ h In−2f − 1n−2f 1n−2f ht = n−f t n−f | {z }

(i)

Var({gt }i∈St ) =

V1

2 h⊺ 1n−2f 1⊺f bt − (n − f )2 t {z } | V2

 # 1 1 ⊺ ⊺ + b If − 1f 1f bt n−f t n−f {z } | 

V3

2f βσDP = V1 − (n − f )2

(i)

X

ξt +

i∈H∩St

f (n − 2f ) 2 β σDP 2 . (n − f )2

(V1 ) The concentration property of V1 , whether 1 ∈ St or note is the same. We use the Hanson-Wright inequality from [31, Theorem 1.1], with 1 1n−2f 1⊺n−2f M = In−2f − n−f −c1 min{

P (V1 > E [V1 ] + s) ≤ e

s2 (n−f )2 s(n−f ) } , σ 4 ∥M ∥2 σ 2 ∥M ∥sp DP F DP

where c1 > 0 is a constant, ∥M ∥2F = n−2f −1+



f n−f

2

.

≤ n−2f and ∥M ∥sp =

f . That is, ∀s ≥ 0, 1 as the eigenvalue of M are 1 with multiplicity n−2f −1 and n−f −c1 min{

p1 (s) := P (V1 > E [V1 ] + s) ≤ e

s2 (n−f )2 s(n−f ) } , 2 σ 4 (n−2f ) σ DP DP

.

(V2 ) For V2 , t ≥ ntest and i ∈ H ∩ St , 2f βσDP (n − f )2

X

(i) ξt ∼ N



2f βσDP (n − f )2

0,

i∈H∩St

2

! 2 (n − 2f )σDP

,

i.e. ∀s ≥ 0, p2 (s) := P (V2 > E [V2 ] + s = s) = P (V2 < −s) −

≤e

s2 (n−f )4 8f 2 β 2 (n−2f )σ 4 DP

−

=e

s2 (n−f )3 8f (n−f −1)σ 4 DP

.

(n−2f ) 2 2 (V3 ) For V3 , t ≥ ntest , f(n−f )2 β σDP is perfectly concentrated as Byzantine participants send constant values. Hence, with 1 2 n−f −1 s = σDP , 8 n−f

21

h   i −1 2 1 we have E gt⊺ n−f Pn−f gt + s ≤ 78 n−f n−f σDP , and using the union bound, P

c E3,t

      1 1 ⊺ := P Pn−f gt > E gt Pn−f gt + s n−f n−f   n − f − 1 n − 2f 2 = P V1 − V 2 > σ +s n − f n − f DP   1n−f −1 2 ≤ P V1 − V 2 > s = σDP 8 n−f s s ≤ p1 ( ) + p2 ( ) 2 2 

gt⊺



c1

n−f −1

= e− 16 (n−f −1) min{ 16(n−2f ) ,1} + e− As a result, 

.



\

P

(n−f )(n−f −1) 2048f

t∈{ntest +1,...,T }

 s T −ntest s E3,t  ≥ 1 − p1 ( ) − p2 ( ) 2 2

 T −ntest c1 n−f −1 (n−f )(n−f −1) 2048f = 1 − e− 16 (n−f −1) min{ 16(n−2f ) ,1} − e−   c1 n−f −1 (n−f )(n−f −1) 2048f ∈ Ω(1) if and only if T ∈ O min{e 16 (n−f −1) min{ 16(n−2f ) ,1} , e } . Pm (1,j) (1) (1) (1) 1 (ii) Under E1 and the trajectory produced by S (i.e., with gt = m + ξt = ξt ), j=1 z we do an analogous analysis as in (i), in the opposite direction. That is, due to Algorithm 2, the Byzantine participants successfully steer the optimization trajectory in the negative direction. (iii) Otherwise, in the complementary event E1c , the influence of Byzantine participants is considered negligible, and any potential contribution to instability from this case is disregarded. Consequence for the lower bound. Recall that we controll the probability of the following event \
E = E1 ∩ E2,t ∩ E3,t , t∈{ntest +1,...,T }

Conditioned on E, the parameter divergence is bounded by E [|θT − θT′ | |E] ≥ E [|θT′ | |E] ≥

T X γ f βσDP n − f t=n +1 test

s 1 f (n − f − 1)(n − f ) = γ(T − ntest )σDP 2 n−f f (n − 2f ) s   1 f f −1 = (1 − ptest )γT σDP 1+ . 2 n−f n − 2f Moreover, note that for t, s ∈ {ntest + 1, . . . , T }, t ̸= s, E1 is independent of E2,t and E3,t , E2,t ∩ E3,t is independent of E2,s ∩ E3,s and Y P (E) = P (E1 ) P (E2,t ∩ E3,t ) t∈{ntest +1,...,T }

≥ P (E1 )

Y

c c 1 − P E2,t − P E3,t

t∈{ntest +1,...,T }

 T −ntest c1 n−f −1 (n−f )(n−f −1) n−f −1 2048f ≥ P (E1 ) 1 − e− 256 − e− 16 (n−f −1) min{ 16(n−2f ) ,1} − e− ∈ Ω(1).

22

As a result, we have s E [|θT − θT′ |] ≥ E [|θT − θT′ | |E] P (E) ∈ Ω

γT σDP

f n − 2f

! ,

and the uniform stability is lower bounded by s E [|ℓ(θT , z) − ℓ(θT′ , z)|] ≥ CE [|θT − θT′ | |E] P (E) ∈ Ω

sup

γT CσDP

z∈[−C,C]

f n − 2f

! .

Gluing lower is lower bounded  when σDP = 0, the uniform  by   bounds.q Moreover,  stability  f f n 1 n 1 2 2 Ω γC T (n−f )m + n−2f when 3 ≤ f < 2 , and by Ω γC T (n−f )m + n−2f when f < n3 [7, Theorem 3.2]. We conclude the proof with the formula max{a, b} ≥ a+b 2 ∈ Ω(a + b), i.e. when n3 ≤ f < n2 the uniform stability is lower bounded by s !!  σDP  f 1 2 1+ . Ω γC T + (n − f )m n − 2f C q √ f The case f < n3 is analogous. Note that κSMEA is of the same order as n−2f if we assume there n exist a constant ν > 0 such that f ≤ 2+ν , i.e. the lower bound matches the upper bound. C.3.2

Proof for d > 1.

Assumption C.3. We assume the the following. f 1. There exists a constant αmin > 0 such that α := n−f ∈ [αmin , 1/2). d ≤ ν. 2. There exist constants µ, ν > 0 such that µ ≤ n−f

3. µ > µmin and n − f − 1 ≥ Nmin , where µmin and Nmin are constants that depends on assumption 1. & 2., and the problem spectral and finite-sample structure. That is, µmin :=

4 c2max (1 − rmax )

,

and Nmin := max

 

√

3( ν +



√

1 − αmin + max{C1 , C2 }) √ 1 − 1 − αmin

2 ,

 

16 min(1, ν) q , √ αmin µc2  cδ µ 2 + min(1,ν)

where C1 , C2 > 0 are universal constants, and cmax , rmax ∈ (0, 1) are defined as √ √ 2 E∥X⊥ ∥2sp ν + 31 + 32 1 − αmin √ rmax := √ ≥ , E∥X∥2sp ν + 32 + 31 1 − αmin c2max := 1 − 

1 − αmin

2 ≤ √ √ min ν + 1 − 1− 1−α 3

E [(DZ)⊺ Pn−f DZ] , E∥X∥2sp

where Z ∼ N (0, In−f ), X ∈ Rd×(n−f −1) , X⊥ ∈ R(d−1)×(n−2f ) are random matrices with i.i.d. standard normal entries. D ∈ R(n−f )×(n−f ) is a diagonal masking matrix with n − 2f 1 ones and f zeros, and Pn−f = In−f − n−f 1n−f 1⊺n−f is a centering projection matrix.

Assumption C.3, while technical are fairly mild. They are either practically always true (e.g., T ) or assumed to bound expectation and concentration of random matrices (e.g., µmin and Nmin ). 23

The quantities

E∥X⊥ ∥2sp E[(DZ)⊺ Pn−f DZ] have interpretation within the context of our proof. E∥X∥2sp and E∥X∥2sp

E∥X⊥ ∥2

Indeed, E∥X∥2sp is the ratio between the expected principal variance of the honest noise orthogonal sp to the attack and the expected principal variance of all honest noise. Intuitively, it measures how much of the honest noise aligns with the attack direction (which is arbitrary in our proof), dictating E[(DZ)⊺ Pn−f DZ] how easily the attacker can hide inside the honest variance. Finally, is the ratio E∥X∥2sp between the expected variance of the honest noise along the attack axis and the expected principal variance of all the honest noise. Intuitively, this measures how much the orthogonal honest noise tilts the principal eigenvector away from the attack direction. We now turn to the proof of Theorem 3.2.

Theorem 3.2. Consider the setting in √Section 2 with full batch and the SMEA aggregation rule. √ 2
Suppose Assumption C.3, T ∈ O ecmin ( d+ n−f −1) where cmin is a problem-dependent constant, √ 2C 2T ln(1/δ) √ ε ∈ Ω(1) and σDP = . Then there exist ℓ ∈ RΘ×Z such that ∀z ∈ Z, ℓ(·; z) is mε ln(1/δ)

C-Lipschitz, L-smooth and convex, such that the uniform stability of A is lower bounded by s s !!! 1 f f σDP d 2 Ω γC T + + 1+ . (n − f )m n − 2f n − 2f C n−f If we moreover assume n3 < f < n2 , the uniform stability of A is lower bounded by s s s !!! 1 f f σDP d 2 Ω γC T + + 1+ . (n − f )m n − 2f n − 2f C n−f

(17)

(18)

Proof. Let d, n ≥ 1, H = {1, . . . , n − f } and let S, S ′ ∈ Z (n−f )m neighboring datasets where every sample equal 0, except for one sample in S ′ from the participant 1, equal to −Ce1 . Let ℓ : Rd × B(0, C) → R, (θ, z) 7→ ℓ(θ; z) = θ⊺ z. For i ∈ H := {1, . . . , n − f }, 0 ≤ t ≤ T , let (i) 2 ξt ∼ N (0, σDP Id ) be independent random gaussian noise. Byzantine participants trigger. We analyze two attacker capabilities. First, if Byzantine participants have access to the random seeds of honest participants, they can circumvent the differential privacy guarantee. Indeed, this knowledge allows them to perfectly reconstruct the added noise, subtract it, and thus deterministically identify, at the first iteration, whether the first participant’s true C gradient was − m e1 or 0. In the alternative scenario, where attackers only observe the final noisy gradient (lacking the seed), they cannot perform this deterministic inference. We must then rely on a statistical test to bound their success probability to distinguish the two cases. We explain a possible test in what follows. Let ptest ∈ (0, 1). We define the behavior of Byzantine participants based on a trigger condition. This trigger is determined by performing a gaussian mean hypothesis test on the first ntest := ptest T sample, collected during an initial fraction of the total T iterations. The test evaluates whether the sample mean, projected on e1 , corresponds to hypothesis H0 (mean 0, equivalently the dataset is S) C 2 or to hypothesis H1 (mean − m , equivalently the dataset is S ′ ), assuming a known variance σDP . C This test processes the statistic ζ̄ which evaluates at − m + ξ¯ under H1 , and evaluates at ξ¯ under H0 , Pntest (1) ⊺ where ξ¯ = 1 ξ e1 . Overall, the Byzantine participants undergo a membership inference ntest

t=1 t

(1)

(1)

′(1)

(1)

C attack to know whether the gradients from participant 1 equals gt = ξt or gt = − m e1 + ξt , ′ i.e, whether the dataset is S or S . The decision is made depending on a trigger value ctrigger ,

reject H0 if ζ < −ctrigger , else accept H0 . We denote Z ∼ N (0, 1) a standard gaussian random variable, and zα ∈ R the value such that P(Z > 2 σDP zα ) = α, α ∈ (0, 1). Conditioned on H0 , ζ|H0 ∼ N (0, ntest ), hence setting ctrigger = zα √σnDPtest , P (reject H0 |H0 ) = P (ζ > ctrigger |H0 ) = P (Z > zα ) = α. 24

Let denote E1 the event that the Byzantine workers successfully infer the underlying datasets from the gradient statistics (successful MIA). Under the optimal hypothesis test, we have n o n o C E1 = ξ¯ does not trigger H0 rejection ∩ shifting ξ¯ by − triggers H0 rejection m n o n o C = ξ¯ ≥ −ctrigger ∩ ξ¯ − < −ctrigger m n o C = − ctrigger ≤ ξ¯ < − ctrigger . m ¯ = Law(−ξ), ¯ we have Because Law(ξ)     √ C ntest C ¯ P (E1 ) = P ctrigger − < ξ ≤ ctrigger = P zα − < Z ≤ zα m mσDP   √ ε ptest = P zα − p < Z ≤ zα . 2 2 ln(1/δ) p This means that P (E1 ) ∈ Ω(1) if and only if there exist a constant c1 such that ε ≥ c1 ln(1/δ). The event E1 relates to the best false negative rate βα = inf P(reject H0 |H0 )≤α P(accept H0 | H1 ) = √ √ ε p C n P(Z − m σDPtest ≤ zα ) = Φ(zα + √ test ) (the Byzantine participants infer S when S ′ ) for 2

2 ln(1/δ)

a fixed false positive rate α = P(reject H0 | H0 ) = P(Z > zα ) = 1 − Φ(zα ) (the Byzantine √ ε ptest ′ √ ). That participants infer S when S) through P(E1 ) = 1 − α − βα = Φ(zα ) − Φ(zα + 2

2 ln(1/δ)

is, P(E1 ) = 1 − P(reject H0 | H0 ) − P(accept H0 | H1 ) quantifies the Byzantine participants maximum inference capability, representing the probability of MIA success beyond random chance (or MIA advantage). Byzantine participants behavior under the SMEA aggregation rule. We assign the following behavior (Algorithm 3) to the Byzantine participants i ∈ {n − f + 1, n}, for t ≥ ntest + 1. Algorithm 3 Byzantine Participant Behavior # β (defined below) depends on f and n if ζ̄ ≥ −ctrigger then return β σDP e1 else return −β σDP e1 That is, depending on the input ζ̄ statistic, which itself depends only on the observed noisy gradients, the Byzantine participants attempt to steer the optimization trajectory toward either positive or negative values (with respect to the hyperplane orthogonal to e1 ). In what follows, we decompose our analyze depending on whether the Byzantine participants undergo a successful MIA (i.e., infer whether the dataset is S or S ′ successfully) in the two coupled optimization trajectories (E1 ), or not (E1c ). In the complementary event E1c , the influence of Byzantine participants is considered negligible, and any potential contribution to instability from this case is disregarded. Consequently, we fix their behavior to sending an arbitrary vector, for example, 0. Under E1 , the attack Algorithm 3 output β σDP e1 for the trajectory produced by S ′ (i.e., with Pm (1,j)′ (1)′ (1) (1) 1 C gt = m + ξt = − m e1 + ξt ), and output −β σDP e1 for the trajectory produced j=1 z P (1) (1) (1) m 1 (1,j) by S (i.e., with gt = m + ξt = ξt ). That is, under E1 , the Byzantine participants j=1 z attempt to steer the optimization trajectory in different directions depending on the dataset they have successfully inferred. The analysis is analogous for both trajectories. For the remaining of this paragraph, we work under E1 and the trajectory induced by S. Let Λ := E∥ΣH ∥sp . Following Algorithm 3 after ntest steps, all Byzantine participants i ∈ B := {n − f + 1, . . . , n} send to the server a constant vectors in the direction e1 , for all i ∈ B, t ∈ {ntest + 1, . . . , T }, 25

(i) gt := βσDP e1 ,

(19)

where β := c p

n−f

√

Λ , σ f (n − 2f ) DP

(20)

where c ∈ (0, copt ) and copt are parameter-independent constants defined in step (iv) below. β is chosen so that SMEA consistently selects the Byzantine vectors, as explained below. √

• Note on Λ and the magnitude of σDPΛ . By standard derivation, ΣH is identically distributed σ2

DP XX ⊺ , where X ∈ Rd×(n−f −1) is a random matrix with i.i.d. standard normal entries to n−f

σ2

DP N (0, 1)4 . Hence, λmax (ΣH ) = n−f smax (X)2 , where smax (X) is the maximum singular value of X. Taking the expectation yields

2 σDP E[smax (X)2 ]. (21) n−f √ √ To relate Λ to the Marchenko-Pastur baseline n − f − 1 + d, we multiply and divide Equation (21) by this baseline, yielding s s ! p √ E[smax (X)2 ] Λ n−f −1 d √ . 1+ , where cΛ := √ = cΛ σDP n−f n−f −1 n−f −1+ d (22) To prove that cΛ can be considered as a constant, we rely on results from high-dimensional probability [34, Chapter 7]. By [34, Theorems 7.3.1] and standard Gaussian comparison arguments, there exists a constant C > 0 such that p p √ √ d + n − f − 1 − C ≤ E[smax (X)] ≤ d + n − f − 1.

Λ = E[λmax (ΣH )] =

Furthermore, because the map X 7→ smax (X) is 1-Lipschitz5 , the Gaussian Poincaré inequality guarantees Var(smax (X)) ≤ 1 [6, Section 3.7]. Using the identity E[smax (X)2 ] =
2 E[smax (X)] + Var(smax (X)) yields p p √ √ ( d + n − f − 1 − C)2 ≤ E[smax (X)2 ] ≤ ( d + n − f − 1)2 + 1. √ √ Taking the square root and dividing by the baseline dimension ( d + n − f − 1), we obtain s r C C 1 1 5 , max{ , 1 − } ≤ 1 − √ ≤ cΛ ≤ 1 + √ ≤ √ √ 2 2 2 4 d+ n−f −1 ( d + n − f − 1) (23) where the numerical lower bound is obtained through the following inequalities E∥X∥2 d(n−f −1) Esmax (X)2 ≥ min(d,n−fF −1) = min(d,n−f −1) = max(d, n − f − 1), and hence −1) √ ≥ 1. √ cΛ ≥ max(d,n−f 2 n−f −1+ d

P (i) (i) 1 ⊺ Let ΣS := |S| i∈S (gt − ḡS )(gt − ḡS ) denote the sample covariance matrix of a subset S. To ensure the aggregator selects the subset St = Ht ∪ B, where Ht ⊂ H is composed of n − 2f indices from H, over the honest subset H, we must guarantee with high probability that for t ∈ {ntest + 1, . . . , T },

λmax (ΣSt ) < λmax (ΣH ).

(i)

4 Indeed, denoting Ξ the matrix whose column are ξt t σDP

(24)

1 for i ∈ H and Pn−f = In−f − n−f 1n−f 1⊺n−f the σ2

DP centering matrix which is an orthogonal projection matrix, Σt = n−f Ξt Pn−f Ξ⊺t . Pn−f is diagonalizable, Pn−f =

σ2

DP U ΛU ⊺ , where U is an orthogonal matrix and Λ := diag(1, . . . , 1, 0) . Consequently, Σt = n−f (Ξt U )Λ(Ξt U )⊺ = 2 2 P σDP σDP n−f −1 (Ξt U )j (Ξt U )⊺j := n−f XX ⊺ , with Xj = (Ξt U )j . j=1 n−f 5 |s max (X) − smax (Y )| = |∥X∥sp − ∥Y ∥sp | ≤ ∥X − Y ∥sp ≤ ∥X − Y ∥F .

26

P (1) (n) (i) f 1 ¯ That is SMEA(gt , . . . , gt ) = ḡSt = n−f = n−f β σDP e1 + n−2f i∈St gt n−f ξHt . Indeed, all other subsets than St and H necessaryly have greater spectral norm6 . We demonstrate this via a concentration argument, first bounding the expected spectra of both matrices. To tightly bound λmax (ΣSt ), we leverage the fact that, due to the subset B, the dominant eigenvector of ΣSt consistently aligns with e1 , thereby reducing the dimensional dependence7 . To do so, we decompose ΣSt into a 2 × 2 block matrix structure, where one diagonal block accounts for the covariance along the direction e1 , and the other for the covariance in the (d − 1)-dimensional orthogonal complement e⊥ 1 . Geometrically, we demonstrate that the principal eigenvector of ΣSt is overwhelmingly aligned with the attack axis e1 . Any unit vector v ∈ Rd can be uniquely decomposed as v = xe1 + yw, where w ∈ e⊥ 1 is a unit vector and x2 + y 2 = 1. Hence, v ⊺ ΣSt v = x2 (e⊺1 ΣSt e1 ) + y 2 (w⊺ ΣSt w) + 2xy(e⊺1 ΣSt w) = x2 Σ11 + y 2 (w⊺ Σ22 w) + 2xyw⊺ Σ12 ,

(25)

where we define the following blocks. • Σ11 := e⊺1 ΣSt e1 ∈ R is the variance along the attack axis e1 . := • Σ22 := Pe⊥ ΣSt Pe⊥ ∈ R(d−1)×(d−1) is the orthogonal covariance block, where Pe⊥ 1 1 1 ⊺ Id − e1 e1 denote the orthogonal projection matrix zeroing out the first coordinate. Because the attack vector spans e1 , Σ22 is entirely independent of the Byzantine vectors. • Σ12 := Pe⊥ ΣSt e1 ∈ Rd−1 is the cross-covariance vector. Note that we identify 1 (0 Σ2,1 . . . Σd,1 ) with Σ⊺12 , since w ∈ e⊺1 . We identify Σ22 analogously. To bound the maximal eigenvalue, λmax (ΣSt ) = supv∈Sd−1 v ⊺ ΣSt v, we aim at upper bounding (25),    Σ11 ∥Σ12 ∥2 |x| ⊺ 2 2 v ΣSt v ≤ x Σ11 + y λmax (Σ22 ) + 2|xy|∥Σ12 ∥2 = (|x| |y|) , ∥Σ12 ∥2 λmax (Σ22 ) |y| 6 For any intermediate subset S containing exactly 0 < k < f Byzantine vectors, the expected variance along the k direction e1 introduces a between-group mixture term proportional to k(n − f − k). Because this forms a strictly concave quadratic function of k, its minimum over the closed interval [0, f ] is necessarily achieved at the boundaries (k = 0 or k = f ). By tuning β to equalize these endpoints with a slight margin favoring k = f , we guarantee that SMEA selects either the purely honest subset H or the subset St over any intermediate mixture. 7 This avoids the worst-case—loose in our setting—application of Weyl’s inequality. The reasoning is as follows. By definition, St is partitioned into two disjoint groups: the honest subset Ht of size n − 2f (with empirical mean ξ̄Ht and covariance ΣHt ) and the Byzantine subset B of size f (with empirical mean βσDP e1 and covariance 0). Using the standard decomposition formula for the empirical covariance for the partition St = Ht ∪ B, we have

|Ht | |B| |Ht ||B| ΣHt + ΣB + (ξ̄Ht − βσDP e1 )(ξ̄Ht − βσDP e1 )⊺ |St | |St | |St |2 n − 2f f (n − 2f ) = ΣHt + (ξ̄Ht − βσDP e1 )(ξ̄Ht − βσDP e1 )⊺ . n−f (n − f )2

ΣSt =

We have λmax ((ξ̄Ht − βσDP e1 )(ξ̄Ht − βσDP e1 )⊺ ) = ∥ξ̄Ht − βσDP e1 ∥22 and, by Weyl’s inequality, the maximum eigenvalue of a sum of symmetric matrices is bounded by the sum of their maximum eigenvalues, λmax (ΣSt ) ≤ UBSt :=

n − 2f f (n − 2f ) λmax (ΣHt ) + ∥ξ̄Ht − βσDP e1 ∥22 . n−f (n − f )2

UBSt does not leverage the fact that, because of the subset B, the dominant eigenvector aligns with e1 , which introduces a dimensional dependence and makes the analysis loose. Note that general alternatives to Weyl’s inequality for matrix perturbation exist, such as those based on the Davis–Kahan sin Θ theorem [34, Theorem 4.1.15] (i.e., eigen-space perturbation theory). However, our technique directly leverages the problem structure, making the overall reasoning tighter and simpler.

27

where (|x|

|y|) is a unit vector in R2 . Consequently, this decomposition yields 8   Σ11 ∥Σ12 ∥2 λmax (ΣSt ) ≤ λmax ( ) ∥Σ12 ∥2 λmax (Σ22 ) q Σ11 + λmax (Σ22 ) 1 2 (Σ11 − λmax (Σ22 )) + 4∥Σ12 ∥22 . = + 2 2

(26)

(i) Bounding Σ11 . The variance along e1 decomposes into 1 2f βσDP X (i) f (n − 2f ) 2 2 e⊺1 ΣSt e1 = ξt,1 + β σDP , h⊺t,1 Pn−f ht,1 − n−f (n − f )2 (n − f )2 i∈H∩St {z } | | {z } | {z } :=V1 :=V 3

:=V2

(i)

(i) ⊺

1 where ξt,1 = ξt e1 , Pn−f = In−f − n−f 1n−f 1⊺n−f , and ht is the vector containing the n − 2f honest noise from St , and filled with 0 for the remaining f dimension. By the definition of β, the deterministic Byzantine contribution simplifies to V3 = c2 Λ. Taking the expectation yields9 .

E[Σ11 ] = σ02 + c2 Λ := U11 , where σ02 :=

(n − 2f )(n − f − 1) 2 σDP . (n − f )2

(27)

(i)

(ii) Bounding Eλmax (Σ22 ) via Loewner partial order. Let ui := Pe⊥ gt denote the projected 1 P 1 u gradients and µ := n−f their subset mean. We have, Σ22 = M22 − µµ⊺ , i∈St i P ⊺ 1 ⊺ where M22 := n−f i∈St ui ui . Because µµ ⪰ 0, we have Σ22 ⪯ M22 , and hence λmax (Σ22 ) ≤ λmax (M22 ). Crucially, because the f Byzantine vectors evaluate to zero in e⊥ 1 , they contribute zero to the uncentered sum, σ2 1 X (i) (i) ⊺ ⊺ M22 = ξt,⊥ ξt,⊥ := DP X⊥ X⊥ , n−f n−f i∈Ht

(d−1)×(n−2f )

where X⊥ ∈ R consists of i.i.d. standard normal entries. Because f ≥ 1, X⊥ is formed by removing columns (discarding f − 1 excess honest participants) and a row d×(n−f −1) (projecting onto e⊥ defined in (21). Thus, smax (X⊥ ) ≤ 1 ) from the matrix X ∈ R smax (X) deterministically. Furthermore, because X is composed by independent normal random variables, the extra row and columns almost surely project non-trivially onto the dominant singular vectors of X⊥ . Consequently, the spectral norm strictly expands with probability 1 (i.e., P(smax (X⊥ ) < smax (X)) = 110 ). Taking the expectation yields 2 max (X⊥ ) ] rΛ := E[s E[smax (X)2 ] < 1, and hence Eλmax (Σ22 ) ≤ Eλmax (M22 ) = rΛ Λ := U22 .

(28)

(iii) Bounding E∥Σ12 ∥22 . Because the Byzantine vectors project to zero in e⊥ 1 and evaluate to βσDP in e1 , the cross-covariance simplifies to Σ12 = (1 − α)(ΣH )12 + α(1 − α)(ξ¯H ,1 − βσDP )ξ¯H ,⊥ , t

t

t

2

y x2 + y 2 ≤ min{|x| + |y|, |x| + 2|x| } to the square root term to simplify the proof. Though, we place our analysis on the edge of what the Byzantine participants can do. That is, in the inequality above, it is difficult to know if |x| and |y| will have the same order or not. As we require to be as tight as possible, we apply Sylvester’s criterion to avoid explicitly handling inequalities. 9 This expectation is derived using the trace trick for quadratic forms. Because the honest variables are zero-mean, 1 E[h⊺t,1 Pn−f ht,1 ] = Tr(Pn−f Σh ) = Tr(Σh ) − n−f Tr(1n−f 1⊺n−f Σh ), where Σh := E[ht,1 h⊺t,1 ]. The vector ht,1 ∈ 8We might use the inequality

p

2 ) and f zeros. Thus, Σ is diagonal, yielding Tr(Σ ) = Rn−f contains n − 2f independent honest coordinates ∼ N (0, σDP h h ⊺ ⊺ ⊺ 1 2 . Moreover, Tr(1 2 (n − 2f )σDP n−f 1n−f Σh ) = 1n−f Σh 1n−f = (n − 2f )σDP . Consequently, n−f E[ht,1 Pn−f ht,1 ] =
2 (n−2f )(n−f −1) 2 1 n − 2f − n−2f σDP = σDP . n−f n−f (n−f )2 10 Let X be a submatrix obtained by deleting rows or columns from X. By definition, ∥X∥ = sup sp ⊥ ∥v∥2 =1 ∥Xv∥2 . For any unit vector u in the domain of X⊥ , appending zeros to the deleted coordinates yields a unit vector ũ in the domain of X such that ∥X ũ∥2 = ∥X⊥ u∥2 . Taking the supremum over all such vectors guarantees ∥X⊥ ∥sp ≤ ∥X∥sp deterministically. Consequently, E[smax (X⊥ )2 ] ≤ E[smax (X)2 ].

28

P 1 ¯ ¯ where (ΣHt )12 = n−2f i∈Ht (ξi,⊥ − ξHt ,⊥ )(ξi,1 − ξHt ,1 ). To compute the expected squared norm E∥Σ12 ∥22 , we square the sum. By the independence of the Gaussian sample mean and sample covariance, the expected cross-term evaluates to zero (i.e., E[(ΣHt )⊺12 ξ¯Ht ,⊥ ] = E[(ΣHt )12 ]⊺ E[ξ¯Ht ,⊥ ] = 0). This yields the decomposition,   E∥Σ12 ∥2 = (1 − α)2 E∥(ΣH )12 ∥2 + α2 (1 − α)2 E (ξ¯H ,1 − βσDP )2 ∥ξ¯H ,⊥ ∥2 . 2

t

2

t

t

2

Furthermore, ξ¯Ht ,1 is independent of ξ¯Ht ,⊥ , we have  2    σDP 2 E (ξ¯Ht ,1 − βσDP )2 ∥ξ¯Ht ,⊥ ∥22 = + β 2 σDP UV2 . n − 2f Additionally11 , E∥(ΣHt )12 ∥22 =

n − 2f − 1 2 2 d−1 2 n − 2f − 1 4 (d − 1)σDP = σDP UV where UV2 := σ . 2 (n − 2f ) n − 2f n − 2f DP

Thus, (n − 2f )(n − 2f − 1) 2 2 α2 (1 − α)2 2 2 σ U + σDP UV + α(1 − α)UV2 c2 Λ DP V (n − f )2 n − 2f
2 2 1−α n − 2f − 1 + α2 σDP UV + α(1 − α)c2 UV2 Λ = n−f   n − 2f − 1 + α2 2 σDP + αc2 Λ = (1 − α)UV2 n−f   n−f −1−α 2 = (1 − α)UV2 (1 − α) σDP + αc2 Λ n−f   n − f −1 2 2 ≤ (1 − α)UV2 (1 − α) σDP + αc2 Λ := U12 (29) n−f

E∥Σ12 ∥22 =

(iv) The margin via Sylvester’s criterion (fixing copt and δ). Let define the following matrices   Σ11 ∥Σ12 ∥2 := M ∥Σ12 ∥2 λmax (Σ22 ) and, where we used (27) (28) (29),  U11 Mexp := U12

U12 U22

 =

 2 σ0 + c 2 Λ U12

 U12 . rΛ Λ

We have λmax (ΣSt ) ≤ λmax (M ) = λmax (Mexp + (M − Mexp )) ≤ λmax (Mexp ) + λmax (∆M ), where we define ∆M = M − Mexp . We require λmax (Mexp ) ≤ Λ − 2δ for a chosen margin δ > 0. This is equivalent to requiring the shifted matrix (Λ − 2δ)I − Mexp to be positive semi-definite. By Sylvester’s Criterion, a 2 × 2 symmetric matrix is positive semi-definite if and only if its diagonal terms and its determinant are non-negative Λ − U11 − 2δ ≥ 0, 2 (Λ − U11 − 2δ)(Λ − U22 − 2δ) ≥ U12 .

(30) (31)

σ2

DP Satisfying condition (30). Recall that Λ = n−f E[smax (X)2 ] for a d × (n − f − 1) standard

E∥X∥2

Gaussian matrix X, and E[smax (X)2 ] ≥ min(d,n−fF −1) = max(d, n − f − 1). Hence, 2 (1 − α)σDP d max(d, n − f − 1) = σ02 max( , 1). n−f n−f −1 Consequently, (30) is possible with the following mild assumptions.

(1 − α)Λ ≥

2

σDP ⊺ 1 11We write (Σ Ht )12 = n−2f X⊥ Pn−2f X1 , with the projection matrix Pn−2f := In−2f − n−2f 1n−2f 1n−2f , and X⊥ ∈ R(d−1)×(n−2f ) , X1 ∈ Rn−2f denote an independent standard normal matrix and vector. ⊺ 2 Evaluating E∥X⊥ Pn−2f X1 ∥22 = E[Tr(XPn−2f E[X1 X1⊺ | X⊥ ]Pn−2f X ⊺ )] = E[Tr(X⊥ Pn−2f X⊥ )] = ⊺ Tr(Pn−2f E[X⊥ X⊥ ]) = Tr(Pn−2f (d − 1)In−f ) = (n − 2f − 1)(d − 1) yield the result.

29

(A) The Byzantine participant number scale with the network scale. There exists ι such σ2 ι ι that f ≥ ιn, hence α ≥ 1−ι . Consequently, Λ0 ≤ (1 − 1−ι ) := ρmax < 1. (B) Overparametrization regime. There exists η > 0 such that d ≥ (1 + η)(n − f − 1). σ2 −1) 1 := ρmax < 1. ≤ 1+η Hence Λ0 ≤ (1−α)(n−f d σ2

−1 (C) We can use a more refined bound on Λ0 = (1 − α) E[sn−f 2 . Assume there exists max (X) ] ν > 0 such that d ≥ ν(n − f − 1). We prove that, by [34, Chapter 7], there exists √ 2 √ a constant C > 0 such that E[smax (X)2 ] ≥ d + n − f − 1 − C . Because C of Assumption C.3, α ≥ αmin and √n−f ≤ ϵ̄. Hence, −1

σ02 ≤ q Λ

1−α d √ C n−f −1 + 1 − n−f −1

1 − αmin := ρmax < 1. 2 ≤ √ 2 ( ν + 1 − ϵ̄)

Assuming ρmax < 1 exists, and define c2max := 1 − ρmax > 0. Because c ∈ (0, cmax ), and to satisfy the condition (30), we fix the margin δ as follows. min{c2max − c2 , 1 − rΛ } Λ. 4 Substituting this margin into condition (30) yields δ := cδ Λ =

Λ − U11 − 2δ = (1 − c2 )Λ − σ02 − 2δ ≥ (1 − ρmax − c2 )Λ − 2δ =

(32)

c2max − c2 Λ > 0. 2

Satisfying condition (31). We require 2 (Λ − U11 − 2δ)(Λ − U22 − 2δ) ≥ U12 .

By factoring out Λ, and substituting (27), (28) (32), yields (Λ − U11 − 2δ)(Λ − U22 − 2δ) ≥

(c2max − c2 )(1 − rΛ ) 2 Λ . 4

(33)

d 2 2 2 Conversely, we upper bound U12 from (29). Because Λ ≥ n−f σDP , hence σDP ≤ n−f d Λ. 1 2 Substituting this alongside UV ≤ 1−α Λ yields     n−f n−f −1 2 2 2 2 2 2 U12 = (1 − α)UV (1 − α) σDP + αc Λ ≤ Λ αc + (1 − α) . (34) n−f d

Combining the bounds from (33) and (34) gives the condition (c2max − c2 )(1 − rΛ ) n−f ≥ αc2 + (1 − α) . 4 d Rearranging,   1 − rΛ c2 (1 − rΛ ) n−f c2 α + ≤ max − (1 − α) . 4 4 d

(35)

Consequently, by [34, Chapter 7], combined with standard Gaussian concentration, there exist absolute constants C1 , C2 > 0 such that √ 2 √ E[smax (X⊥ )2 ] d − 1 + n − 2f + C1 √ rΛ = ≤ √ E[smax (X)2 ] d + n − f − 1 − C2 q 2 q n−2f d−1 √ C1 + + n−f −1 n−f −1   n−f −1 q =  . d √ C2 + 1 − n−f −1 n−f −1 q q q q √ d d 1 1 By Assumption C.3, = 1 + ≤ ν(1 + n−f −1 n−f n−f −1 n−f −1 ), and q q q q √ n−2f n−2f 1 + n−f1 −1 ≤ 1 − α(1 + n−f1 −1 ). We aggregate these terms n−f −1 = n−f 30

√

√

1 ,C2 ) √ and define the residual ϵn := ν+ 1−α+max(C . Again, by Assumption C.3, because  √ √ n−f −1 2 √ min +max{C1 ,C2 }) min √ we assume, n − f − 1 ≥ 3( ν+ 1−α we have ϵn ≤ ϵ̄ := 1− 1−α . 3 1− 1−αmin Consequently, because rΛ decreases with respect to α and increases with respect to the residual ϵn , substituting their bound yield

rΛ =

E[smax (X⊥ )2 ] < E[smax (X)2 ]

√

√ 2 ν + 1 − α + ϵn √ ν + 1 − ϵn √ 2 √ ν + 31 + 23 1 − αmin := rmax ∈ (0, 1). √ ≤ √ ν + 32 + 13 1 − αmin

Concurrently, satisfying Sylvester’s criterion requires   c2 (1 − rΛ ) n−f 1 − rΛ c2 α + ≤ max − (1 − α) . 4 4 d c2max (1−rmax )−4µ−1 , 2+(1−rmax )

This condition is implied when, defining c2opt := c2 ≤ c2opt ≤

c2max (1 − rΛ ) − 4(1 − α) n−f d . 4α + 1 − rΛ 4

Note that, by Assumption C.3, µ > c2

max (1−rmax )

and hence c2opt ∈ (0, 1).

(v) Probabilistic consequence. Recall that  λmax (ΣSt ) ≤ λmax (Mexp ) + λmax (∆M ), with ∆M = M − Mexp := min{c2

∆11 ∆12

 ∆12 . ∆22

−c2 ,1−r }

Λ max We prove λmax (Mexp ) ≤ Λ−2δ for δ = Λ. We now control the following 4 tail failure events for t ∈ {ntest + 1, . . . , T } with high probability

c := {λmax (ΣH ) ≤ Λ − δ} , E2,t       δ δ δ c E3,t := {λmax (∆M ) ≥ δ} ⊂ |∆11 | ≥ ∪ |∆12 | ≥ ∪ |∆22 | ≥ , 4 4 4 p where we used λmax (∆M ) ≤ ∥∆M ∥F ≤ ∆211 + 2∆212 + ∆222 ≤ |∆11 |+2|∆12 |+|∆22 |.

σ2

c DP High probability bound for E2,t . Recall that ΣH is identically distributed to n−f XX ⊺ , where X ∈ Rd×(n−f −1) is a random matrix with i.i.d. standard normal entries N (0, 1). Hence, λmax (ΣH ) behaves as the squared spectral norm of a Gaussian matrix, scaled by 2 σDP n−f . Because the spectral norm map X 7→ smax (X) is 1-Lipschitz continuous, Gaussian Lipschitz concentration [6, Theorem 5.6] guarantees sub-Gaussian tails for smax (X). By 2 σDP c definition, Λ = n−f E[smax (X)2 ], hence E2,t is equivalent to smax (X)2 ≤ E[smax (X)2 ] −

δ n−f . Moreover, by the Gaussian Poincaré inequality [6, Section 3.7], the variance of the σ2 DP

1-Lipschitz function is bounded, meaning E[smax (X)2 ] ≤ (E[smax (X)])2 + 1. Substituting this yields the implication     δ n−f − 1 2 σDP c E2,t =⇒ smax (X) ≤ E[smax (X)] − ,  2E[smax (X)]  √ √ y where we used the inequality x − y ≤ x − 2√ for 0 < y < x. Because the x margin δ scales proportionally with Λ, there exists a constant c̃2 ∈ (0, 1) such that δ n−f − 1 ≥ c̃2 δ n−f . Furthermore, applying Jensen’s inequality, we have E[smax (X)] ≤ σ2 σ2 DP

DP

31

q p n−f E[smax (X)2 ] = 2 Λ. Consequently, the required deviation s from the mean is σDP bounded by s c̃2 δ n−f 2 c̃2 n−f σDP s≥ q = δ 2 Λ. n−f 2 σDP 2 σ2 Λ DP

By Gaussian Lipschitz concentration [6, Theorem 5.6], for any s > 0 we have P(smax (X) ≤ 2 E[smax (X)] − s) ≤ e−s /2 . That is, there exists a constant c2 > 0 such that  
δ 2 (n − f ) c P E2,t ≤ P(smax (X) ≤ E[smax (X)] − s) ≤ exp −c2 . 2 Λ σDP c High probability bound for E3,t . Concurrently, we bound the entries of ∆M using concentration argument.

Bounding P(|∆11 | ≥ 4δ ). Recall that ∆11 = (V1 − E[V1 ]) − V2 . By the Hanson-Wright inequality [31, Theorem 1.1] applied to V1 , and standard Gaussian tail bounds for the term V2 , we have for universal constants c̃1 , c̃3 > 0    2   δ (n − f )2 δ(n − f ) δ ≤ 2 exp −c̃1 min , , P |V1 − E[V1 ]| ≥ 4 (n − 2f ) 2 8 64σDP 8σDP     δ δ 2 (n − f )3 P |V2 | ≥ ≤ 2 exp −c̃3 . 4 8 128f (n − f − 1)β 2 σDP Hence, by the union bound there exisits c̃4 > 0 such that       δ δ δ P |∆11 | ≥ ≤ P |V1 − E[V1 ]| ≥ + P |V2 | ≥ 4 8 8  −c̃4 min

≤ 4e

δ 2 (n−f )2 δ(n−f ) δ 2 (n−f )3 , , 64σ 4 (n−2f ) 8σ 2 128f (n−f −1)β 2 σ 4 DP DP DP



.

Bounding P(|∆22 | ≥ 4δ ). We bound the absolute deviation of ∆22 := λmax (Σ22 ) − U22 . P (i) σDP 1 Recall that Σ22 = M22 − µµ⊺ , where µ := n−f i∈Ht ξt,⊥ = n−f X⊥ 1n−2f , M22 = 2 σDP ⊺ (d−1)×(n−2f ) n−f X⊥ X⊥ , and by definition, U22 = E[λmax (M22 )]. We recall that X⊥ ∈ R n−2f is the matrix with standard normal entries and that 1n−2f ∈ R is the all-ones vector.

For the upper tail, because µµ⊺ ⪰ 0, we have Σ22 ⪯ M22 , which implies λmax (Σ22 ) ≤ λmax (M22 ). Consequently, ∆22 ≤ λmax (M22 ) − U22 . By a analogous derivation done for c bounding E3,t in high probability, there exists an absolute constant c̃5 > 0 such that       δ δ δ 2 (n − f ) P ∆22 ≥ ≤ P λmax (M22 ) − U22 ≥ ≤ exp −c̃5 . 2 Λ 4 4 σDP 1 1 For the lower tail, because n − f > n − 2f , we have (n−f )2 < (n−f )(n−2f ) and we define a surrogate matrix Σ0 with the larger penalty to obtain the positive-semidefinite ordering 2 σDP ⊺ X⊥ 1n−2f 1⊺n−2f X⊥ (n − f )(n − 2f )   2 σDP 1 ⊺ ⊺ := Σ0 . = X⊥ In−2f − 1n−2f 1n−2f X⊥ n−f n − 2f

Σ22 ⪰ M22 −

1 The matrix In−2f − n−2f 1n−2f 1⊺n−2f is a projection matrix of rank n − 2f − 1. Therefore, by the rotational invariance of the Gaussian matrix X⊥ , the surrogate matrix Σ0 is identically 2 σDP ⊺ distributed to n−f X̃⊥ X̃⊥ , where X̃⊥ ∈ R(d−1)×(n−2f −1) consists of i.i.d. standard normal entries. Because Σ22 ⪰ Σ0 , we have λmax (Σ22 ) ≥ λmax (Σ0 ). Thus, the lower deviation of Σ22 is contained within the lower tail of Σ0 . Again, we apply the Gaussian Lipschitz c concentration [6, Theorem 5.6] and analogous derivation as done for E2,t .

32

Consequently, combining the upper tail of M22 and the lower tail of Σ0 , there exists a constant c̃6 > 0 such that     δ δ 2 (n − f ) P |∆22 | ≥ ≤ 2 exp −c̃6 . 2 Λ 4 σDP Bounding P(|∆12 | ≥ 4δ ). We bound the absolute deviation |∆12 | = |∥Σ12 ∥2 − U12 |. To map this to concentration inequalities, we transition to the squared norm and prove that it is sufficient to control the deviation |∥Σ12 ∥22 − E∥Σ12 ∥22 |. From the expansion in (29), we 2 2 2 2 2 2 2 := α(1−α) have U12 = E∥Σ12 ∥22 + α(1−α) n−f σDP UV . For readibility, define G n−f σDP UV = α(1−α)2 d−1 4 n−f n−2f σDP . Squaring the bounds of the absolute deviation event {|∥Σ12 ∥2 − U12 | ≥

δ/4}, we have the following. – The upper tail ∥Σ12 ∥2 ≥ U12 + 4δ . The squared upper tail, requires ∥Σ12 ∥22 ≥ δ2 2 U12 + 2δ U12 + 16 . Define τ := δU812 , we have     δ2 δ δ 2 = P ∥Σ12 ∥22 ≥ U12 P ∥Σ12 ∥2 ≥ U12 + + U12 + 4 2 16    3δU12 δ2 = P ∥Σ12 ∥22 ≥ E∥Σ12 ∥22 + τ + G + + 8 16
2 2 ≥ P ∥Σ12 ∥2 ≥ E∥Σ12 ∥2 + τ . – The lower tail ∥Σ12 ∥2 ≤ U12 − 4δ . First, note that if U12 < 4δ the probability of the event is 0. We only need to control the regime where U12 > 4δ , which is equivalent to δ2 2τ = δU412 ≥ 16 . Under this condition, the squared lower tail event write   δ2 δ2 δ 2 2 2 = E∥Σ12 ∥2 − τ − (2τ − ) − (τ − G) ∥Σ12 ∥2 ≤ U12 − U12 + 2 16 16 Hence, if G ≤ τ , which we prove below, we have     δ δ2 δ 2 2 P ∥Σ12 ∥2 ≤ U12 − = P ∥Σ12 ∥2 ≤ U12 − U12 + 4 2 16   δ2 2 2 = P ∥Σ12 ∥2 ≤ E∥Σ12 ∥2 − τ − (2τ − ) − (τ − G) 16
2 2 ≥ P ∥Σ12 ∥2 ≤ E∥Σ12 ∥2 − τ . 2

4

(1−α) d−1 2 4 4 2 – Ensuring G ≤ τ . Recall that G2 = α(n−f )2 σDP UV , where UV = n−2f σDP , and   n−f −1 2 2 2 2 σDP + αc Λ . U12 = (1 − α)UV (1 − α) n−f 12 Hence, the requirement G ≤ τ = cδ ΛU is equivalent to 8    c 2 α2 (1 − α)3 4 2 n−f −1 2 δ 2 2 σ U ≤ Λ (1 − α) σDP + αc Λ . (n − f )2 DP V 8 n−f

Applying (22) and Assumption C.3, we have !2 r n−f −1 c2Λ µ d 2 2 Λ ≥ cΛ σDP 1 + ≥ σ2 . n−f d min(1, ν) DP Substituting this lower bound and UV2 , the condition G ≤ τ is implied by  2   α2 (1 − α)2 cδ c2Λ n−f −1 µc2 c2Λ ≤d (1 − α) +α . n−f 8 min(1, ν) n−f min(1, ν) 33

The following is stronger inequality, as d ≥ µ(n − f ),    2 µc2 c2Λ 8 min(1, ν) 2 α2 (1 − α)2 . µ (1 − α)(n − f − 1)(n − f ) + α (n − f ) ≥ min(1, ν) cδ c2Λ Because (n − f )2 ≥ (n − f )(n − f − 1) ≥ (n − f − 1)2 , we also have the condition    2 µc2 c2Λ 8 min(1, ν) µ(n − f − 1)2 1 − α + α α2 (1 − α)2 . ≥ min(1, ν) cδ c2Λ The following is stronger inequality    2 αmin µc2 c2Λ 2 min(1, ν) 2 1 . (n − f − 1) + ≥ √ 2 min(1, ν) µcδ c2Λ Hence n−f −1≥

Using the fact that 21 ≤ cΛ ≤

q

2 min(1, ν) q . αmin µc2 c2Λ 1 + 2 min(1,ν)

√ cδ c2Λ µ

5 4 , we have

n−f −1≥

16 min(1, ν) q , √ αmin µc2 cδ µ 2 + min(1,ν)

which is ensured by Assumption C.3. Consequently, we prove P(|∆12 | ≥ 4δ ) ≥ P(|∥Σ12 ∥22 − E∥Σ12 ∥22 | ≥ τ ). We next control the right hand side. Bounding P(|∥Σ12 ∥22 − E∥Σ12 ∥22 | ≥ τ ). Recall the cross-covariance decomposition Σ12 = (1 − α)(ΣH )12 + α(1 − α)(ξ¯H ,1 − βσDP )ξ¯H ,⊥ . t

t

t

Both terms are sums of scaled products of independent standard Gaussian vectors and matrices. Indeed, for the first term, we use the centering projection Pn−2f := In−2f − ⊺ 1 (d−1)×(n−2f ) and X1 ∈ Rn−2f denote an independent n−2f 1n−2f 1n−2f . Let X⊥ ∈ R standard normal matrix and vector. We can write   2 2 σDP 1 σDP ⊺ X⊥ In−2f − 1n−2f 1n−2f X1 = X⊥ Pn−2f X1 . (ΣHt )12 = n − 2f n − 2f n − 2f 2

2

σDP σDP For the second term, we have ξ¯Ht ,1 ∼ N (0, n−2f ) and ξ¯Ht ,⊥ ∼ N (0, n−2f Id−1 ). Reparameterizing with independent standard normal variable z1 ∼ N (0, 1) and ξ¯Ht ,⊥ = X⊥ 1n−2f σDP √ ∼ N (0, Id−1 ), we have n−2f X⊥ 1n−2f , where n−2f

(ξ¯Ht ,1 − βσDP ) =

2 σDP

(n − 2f )

3 2

(z1 − β

p

n − 2f )X⊥ 1n−2f .

Consequently, we have  2 2  p (1 − α)σDP α(1 − α)σDP X⊥ Pn−2f X1 + z + β n − 2f X⊥ 1n−2f , 1 3 n − 2f (n − 2f ) 2   2 2 p (1 − α)σDP α(1 − α)σDP (z − β = X⊥ Pn−2f X1 + n − 2f )1 1 n−2f . 3 n − 2f (n − 2f ) 2 | {z }

Σ12 =

:=vcond

We condition on the σ-algebra F1 := σ(X1 , z1 ). Given F1 , the vector vcond ∈ Rn−2f is deterministic. Because X⊥ consists of independent standard Gaussians, right-multiplying by vcond guarantees Σ12 | F1 ∼ N (0, ∥vcond ∥22 Id−1 ). The squared norm of such combination 34

⊺ is ∥a(Pn−2f X1 ) + b(1n−2f )∥22 = a2 ∥Pn−2f X1 ∥22 + b2 (n − 2f ) + 2abX1⊺ Pn−2f 1n−2f = a2 ∥Pn−2f X1 ∥22 + b2 (n − 2f )12 . Consequently, the conditional variance simplifies to   2 2 2 2 α(1 − α)σDP (1 − α)σDP 2 := ∥vcond ∥22 = ∥Pn−2f X1 ∥22 + (z1 − βσDP )2 . σcond n − 2f n − 2f d

2 As a result, we have the following distributional equality ∥Σ12 ∥22 | F1 = σcond W , where W ∼ χ2d−1 . Crucially, the standard χ2d−1 distribution of W originates from X⊥ and is hence independent of F1 . By the law of total probability, integrating out F1 proves that the unconditional distribution of ∥Σ12 ∥22 is equivalent to the product of the two independent d

2 2 2 random variables, ∥Σ12 ∥22 = σcond W . Thus, E∥Σ12 ∥22 = E[σcond W ] = E[σcond ]E[W ]. We bound the product deviation using the identity 2 2 ∥Σ12 ∥22 − E∥Σ12 ∥22 = σcond W − E[σcond ]E[W ] 2 2 = (σcond − E[σcond ])(W − E[W ]) 2 2 2 + (σcond − E[σcond ])E[W ] + E[σcond ](W − E[W ]).

We define the intersection of independent high-probability events 2 2 E := {|σcond − E[σcond ]| ≤ tA } ∩ {|W − E[W ]| ≤ tB }. p pτ τ τ τ Define tA = min{ 3E[W 2 ], ], 3 } and tB = min{ 3E[σcond 3 }. By the triangle inequality, conditioned on E, we have 2 |∥Σ12 ∥22 − E∥Σ12 ∥22 | ≤ tA tB + tA E[W ] + tB E[σcond ] ≤ τ.

Consequently, P(|∆12 | ≥

δ ) ≤ P(|∥Σ12 ∥22 − E∥Σ12 ∥22 | ≥ τ ) ≤ P(E). 4

Bounding P(|W − E[W ]| ≥ tB ). We evaluate the concentration of the standard χ2d−1 variable W . We apply the Hanson-Wright inequality [34, Theorem 6.2.2]13 , there exists CB > 0 such that   2  tB P(|W − E[W ]| ≤ tB ) ≤ 2 exp −CB min , tB . (36) (d − 1) p Substituting tB = min{ 3E[στ 2 ] , τ3 } yields two possible regimes for the tail. Because cond

12 /8 2 2 E[σcond ]E[W ] = E∥Σ12 ∥22 ≤ U12 and E[W ] = d − 1, we have 3E[στ 2 ] ≥ 3UδU 2 /(d−1) = 12

cond

δ(d−1) 24U12 . Consequently, the exponent in (36) is lower-bounded by

( EB := CB min

δ 2 (d − 1) δU12 δ(d − 1) , 2 , 24(d − 1) , 24U 576U12 12

r

δU12 24

) .

2 2 2 Bounding P(|σcond − E[σcond ]| ≥ tA ). We expand σcond as the sum of a centered quadratic 2 (1−α)σDP α(1−α)σ 2 form and a linear Gaussian term. Let v1 := n−2f and v2 := n−2f DP . We define V := [X√1 ; z1 ] ∈ Rn−2f +1 and√ MA := diag(v12 Pn−2f , v22 ). The non-centrality stems from 2 2 (z1 − β n − 2f ) = z1 − 2β n − 2f z1 + β 2 (n − 2f ). Thus, p 2 2 σcond − E[σcond ] = V ⊤ MA V − E[V ⊤ MA V ] −2c22 β n − 2f z1 . | {z }| {z } :=Q

:=L

⊺ 1 12 P ⊺ n−2f 1n−2f = 1n−2f − n−2f 1n−2f 1n−2f 1n−2f = 0. 13With the theorem notation, we have A = I 2 d−1 , hence ∥Id−1 ∥F = d−1 and ∥Id−1 ∥sp = 1. Moreover the sub-Gaussian

norm K is a constant for standard normals, hence we absorb it in the constants.

35

To bound P(|Q+L| ≥ tA ), we apply the union bound P(|Q| ≥ tA /2)+P(|L| ≥ tA /2). For the quadratic form Q, we apply the Hanson-Wright inequality, with ∥MA ∥2F = v14 (nq− 2f − p δU12 τ 1)+v24 and ∥MA ∥sp = v12 . Substituting tA = min{ 3(d−1) , τ3 } = min{ 24(d−1) , δU2412 }, the exponent for P(|Q| ≥ tA /2) is √   2 δU12 δU12 δ 2 U12 δU12 , , √ EQ := CA min , . 2304∥MA ∥2F (d − 1)2 96∥MA ∥2F 48v12 (d − 1) 2 24v12 2

), For L ∼ N (0, 4v24 β 2 (n − 2f )), we apply the Gaussian tail bound exp(− (tA2σ/2) 2 L

 EL := min

2

2 δ U12

δU12 , 18432v24 β 2 (n − 2f )(d − 1)2 768v24 β 2 (n − 2f )

 .

Wrapping-up. Applying the union bound, we have   δ P |∆12 | ≥ ≤ P(|W − E[W ]| ≥ tB ) + P(|Q| ≥ tA /2) + P(|L| ≥ tA /2) 4 ≤ 2e−EB + 2e−EQ + 2e−EL ≤ 6 exp (− min{EB , EQ , EL }) . Wrapping the high probability bounds. Crucially, conditioned on the intersection of the success events (E2,t ∩ E3,t ), we have λmax (ΣSt ) ≤ λmax (Mexp ) + δ ≤ (Λ − 2δ) + δ = Λ − δ < λmax (ΣH ).

(37)

This proves that the attack systematically lures SMEA with high probability, masking their attack beneath the honest spectral norm. Finally, we search for the bottleneck exponent ESMEA := min{E2 , E11 , E22 , E12 }, where δ 2 (n − f ) , 2 Λ σDP   2 δ(n − f ) δ 2 (n − f )3 δ (n − f )2 , , , E11 := c̃4 min 4 (n − 2f ) 2 4 64σDP 8σDP 128f (n − f − 1)β 2 σDP δ 2 (n − f ) E22 := c̃5 , 2 Λ σDP E12 := min{EB , EQ , EL }, E2 := c2

Recall that

c P(E2,t ) ≤ e−E2 ,

and



δ |∆11 | ≥ 4 Applying the union bound yields c E3,t ⊂





δ ∪ |∆22 | ≥ 4





δ ∪ |∆12 | ≥ 4

 .

c P(E3,t ) ≤ 4e−E11 + 2e−E22 + 6e−E12 .

Consequently, we finally have c c c c P(E2,t ∩ E2,t ) ≥ 1 − P(E2,t ) − P(E3,t ) ≥ 1 − 13e−ESMEA .

The scaling of ESMEA . Observe that, substituting δ = cδ Λ, all exponents are proportional to R :=

36

Λ(n − f ) , 2 σDP

where, using (22) and Assumption C.3 gives 2 √ p p √ d + n − f − 1 ≥ c2Λ max{(1+ µ)2 (n−f −1), (1+ max{ν −1 − 1, 0})2 d}. R = c2Λ (38) Indeed, E2 = c2 c2δ R, E22 = c̃5 c2δ R. Moreover, using (20) the definition of β,  2  n−f cδ 1 R cδ c2δ E11 = c̃4 min (1 − α) , , R. 64 (1 − α) n − f 8 128c2 n−f −1 1 R d Note that 1 − α > 12 , 1−α ≥ 1−α1min , n−f = σΛ2 ≥ c2Λ n−f ≥ c2Λ µ, hence DP   cδ c2Λ µ cδ c̃4 cδ R. min , 1, E11 ≥ 8 8(1 − αmin ) 32c2

For E12 = min{EB , EQ , EL }, to recover E12 ∈ Ω(R), we actually require to revisit how we fix tA and tB as we treat them symmetrically but the yield different concentration. t2B t2A τ Indeed, fixing d−1 = ∥MA ∥F and tA tB = 3 yields E12 ∈ Ω(R). Finally, as explained in the beginning of the paragraph, under E1 and the trajectory produced by S ′ Pm (1,j)′ (1)′ (1) (1) 1 C (i.e., with gt = m e1 + ξt ), we do an analogous analysis as above, in + ξt = − m j=1 z the opposite direction (i.e., −e1 ). That is, due to Algorithm 3, the Byzantine participants successfully steer the optimization trajectory in the negative direction. Otherwise, in the complementary event E1c , the influence of Byzantine participants is considered negligible, and any potential contribution to instability from this case is disregarded. Consequence for the lower bound. Recall that we control the probability of the event E, defined as the intersection between the successful hypothesis test E1 and the high-probability event under which SMEA continuously selects St , \
E = E1 ∩ E2,t ∩ E3,t . t∈{ntest +1,...,T }

For t, s ∈ {ntest + 1, . . . , T }, t ̸= s, E1 is independent of E2,t and E3,t , E2,t ∩ E3,t is independent of E2,s ∩ E3,s . Consequently, we have Y P (E) = P (E1 ) P (E2,t ∩ E3,t ) t∈{ntest +1,...,T }

≥ P (E1 )

Y

c c 1 − P E2,t − P E3,t

t∈{ntest +1,...,T }

≥ P (E1 ) 1 − 13e−ESMEA

T −ntest

∈ Ω(1) if on only if T ∈ O eESMEA ,

which is guaranteed by Assumption C.3. Conditioned on E, the accumulated parameter divergence occurs along the e1 coordinate, E [∥θT − θT′ ∥2 |E] ≥ E [|(θT − θT′ )⊺ e1 ||E] ≥

T X γ f βσDP n − f t=n +1 test

√ f n−f Λ p n − f f (n − 2f ) σDP s s s ! f n−f −1 d 1+ = ccΛ (1 − ptest )γT σDP n − 2f n−f n−f −1 s s ! f d ≥ ccΛ (1 − ptest )γT σDP 1+ . n − 2f n−f = c(1 − ptest )γT σDP

37

(39)

Because (39), we have P (E) ∈ Ω(1), which yields E [|ℓ(θT , z) − ℓ(θT′ , z)|] ≥ CE [∥θT − θT′ ∥ |E] P (E)

sup z∈B(0,C)

s ∈ Ω γT CσDP

f n − 2f

s 1+

d n−f

!! .

Gluing lower when σDP = 0, the uniform is lower bounded   bounds.q Moreover,   stability   by f f 1 n n 1 2 Ω γC 2 T (n−f + when ≤ f < , and by Ω γC T + when )m n−2f 3 2 (n−f )m n−2f f < n3 [7, Theorem 3.2]. We conclude the proof with the formula max{a, b} ≥ a+b 2 ∈ Ω(a + b), i.e. when n3 ≤ f < n2 the uniform stability is lower bounded by s s !!!! 1 f σ d DP Ω γC 2 T + 1+ 1+ . (n − f )m n − 2f C n−f q √ f The case f < n3 is analogous. Note that κSMEA is of the same order as n−2f if we assume there n exist a constant ν > 0 such that f ≤ 2+ν , i.e. the lower bound matches the upper bound.

D

Experimental evaluation details of section 4

We report table of the expected train and test accuracies under varying noise multipliers (σ) and Byzantine participants (f ) shown in the main text. They are reported as mean ± standard error. Table 1: Figure 3 (a) expected train and test accuracies under varying noise multipliers (σ) and Byzantine participants (f ). Reported as mean ± standard error. f =1 f =2 f =3 Noise (σ) Train Acc. Test Acc. Train Acc. Test Acc. Train Acc. Test Acc. 32 16 8 4 2 1 0.5 0.25 0.125

10.41±0.18 12.30±0.23 16.22±0.22 22.37±0.19 31.83±0.22 44.43±0.19 54.13±0.10 59.23±0.09 61.22±0.06

10.44±0.17 12.24±0.21 16.04±0.21 21.93±0.19 31.02±0.20 43.00±0.17 52.13±0.10 56.86±0.07 58.74±0.06

9.74±0.17 9.60±0.21 9.43±0.27 8.10±0.22 6.67±0.19 5.01±0.17 4.26±0.25 4.35±0.28 11.30±0.57

9.72±0.17 9.61±0.19 9.47±0.26 8.05±0.22 6.73±0.18 5.12±0.18 4.34±0.24 4.41±0.28 11.12±0.55

9.60±0.22 9.27±0.17 8.88±0.21 6.56±0.16 2.69±0.11 2.14±0.08 1.44±0.09 0.79±0.04 0.47±0.03

9.67±0.20 9.34±0.18 8.93±0.20 6.68±0.17 2.85±0.11 2.24±0.09 1.52±0.09 0.90±0.05 0.53±0.02

Table 2: Figure 3 (b) expected train and test accuracy under varying noise multipliers and heterogeneity α = β [25]. Reported as mean ± standard srror. α=1 α=5 α = 10 Noise (σ) Train Acc. Test Acc. Train Acc. Test Acc. Train Acc. Test Acc. 32 16 8 4 2 1 0.5 0.25 0.125

12.31±0.46 19.49±0.61 38.66±0.71 62.93±0.52 83.49±0.37 90.16±0.08 90.99±0.04 91.40±0.05 91.61±0.03

12.34±0.46 19.52±0.62 38.61±0.71 62.87±0.53 83.43±0.37 90.07±0.07 90.83±0.04 91.11±0.04 91.25±0.03

12.70±0.67 19.26±0.70 33.04±0.70 49.58±0.65 66.02±0.65 74.34±0.44 76.22±0.28 75.49±0.17 73.84±0.23

38

12.69±0.67 19.21±0.70 32.95±0.70 49.51±0.65 65.92±0.66 74.19±0.43 75.97±0.28 75.26±0.17 73.66±0.22

17.97±1.19 41.41±1.18 73.72±1.02 84.97±0.44 89.12±0.18 90.83±0.03 90.83±0.01 90.73±0.00 90.71±0.00

17.94±1.19 41.38±1.17 73.62±1.01 84.87±0.43 88.99±0.17 90.69±0.03 90.70±0.01 90.61±0.00 90.59±0.00

Table 3: Figure 3 (c) expected train and test accuracies (%) under varying noise multipliers (σ) and dimensionality (d). These values, reported as mean ± standard error, are from Figure 3, right panel. Noise (σ) 32 16 8 4 2 1 0.5 0.25 0.125

d = 12

d = 25

d = 50

Train Acc.

Test Acc.

Train Acc.

Test Acc.

Train Acc.

Test Acc.

10.77±0.21 12.98±0.22 16.44±0.29 23.51±0.32 34.67±0.33 48.85±0.23 57.68±0.14 60.80±0.10 62.25±0.07

10.73±0.21 12.95±0.22 16.27±0.27 23.28±0.31 34.22±0.32 48.16±0.23 56.93±0.14 60.11±0.09 61.51±0.07

12.41±0.32 18.43±0.39 29.03±0.44 43.21±0.44 59.17±0.27 71.27±0.10 75.20±0.06 76.14±0.04 76.60±0.03

12.32±0.32 18.32±0.40 28.67±0.45 42.52±0.45 58.13±0.28 70.01±0.11 73.90±0.06 74.82±0.03 75.25±0.03

10.41±0.18 12.30±0.23 16.22±0.22 22.37±0.19 31.83±0.22 44.43±0.19 54.13±0.10 59.23±0.09 61.22±0.06

10.44±0.17 12.24±0.21 16.04±0.21 21.93±0.19 31.02±0.20 43.00±0.17 52.13±0.10 56.86±0.07 58.74±0.06

Table 4: Figure 4 expected train accuracy, test accuracy, and generalization error under varying noise multipliers (σ). Reported as mean ± standard error across data splits. Noise (σ) Train Acc. (%) Test Acc. (%) 32 16 8 4 2 1 0.5 0.25 0.125

10.15±0.10 10.37±0.20 14.52±0.30 31.15±0.56 54.88±0.51 72.59±0.32 79.88±0.38 82.41±0.28 82.79±0.43

10.12±0.13 10.30±0.19 14.10±0.22 29.95±0.38 52.65±0.38 70.00±0.14 77.12±0.16 79.64±0.12 80.06±0.19

Table 5: Figure 5 expected train and test accuracy under varying noise multipliers. Reported as mean ± standard error across data splits. Noise (σ) Train Acc. (%) Test Acc. (%) 32 16 8 4 2 1 0.5 0.25 0.125

10.10±0.13 9.90±0.03 10.10±0.15 11.12±0.23 18.87±0.50 30.10±0.85 32.21±1.53 36.41±1.75 34.45±0.87

39

10.08±0.10 10.02±0.07 10.13±0.15 10.66±0.22 17.83±0.46 26.74±0.71 27.31±0.71 30.67±1.08 29.74±0.75