🤖 machine learning

Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions

This paper proposes Byz-Clip21-SGD2M, a novel federated learning algorithm that unifies Byzantine robustness and differential privacy with high-probability convergence guarantees under standard assumptions, eliminating the need for unrealistic conditions like bounded gradients or auxiliary datasets.

Original authors: Rustem Islamov, Grigory Malinovsky, Alexander Gaponov, Aurelien Lucchi, Peter Richtárik, Eduard Gorbunov

Published 2026-03-25

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Rustem Islamov, Grigory Malinovsky, Alexander Gaponov, Aurelien Lucchi, Peter Richtárik, Eduard Gorbunov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the conductor of a massive orchestra. You want to compose a beautiful symphony (a smart AI model), but you can't bring all the musicians (data) into one room. Instead, each musician stays in their own home, plays a part of the song, and sends you a recording of their notes. This is Federated Learning. It's great for privacy because the raw data (the musicians' sheet music) never leaves their homes.

However, this setup has two big problems:

The Spies (Privacy Leaks): Even if you don't see the sheet music, a clever spy (the server) might listen to the recordings and figure out what the music was. They might even steal the melody entirely.
The Saboteurs (Byzantine Attacks): Imagine some musicians are actually spies for the enemy. They don't just play wrong notes; they scream, play static, or send recordings that are completely backwards to ruin the whole symphony.

For a long time, researchers tried to fix these problems separately. They had methods to hide the notes (Differential Privacy) and methods to ignore the screamers (Byzantine Robustness). But combining them was like trying to wear a heavy winter coat and a life jacket at the same time—it was clunky, required unrealistic rules (like "all musicians must play very softly"), and often didn't work well.

The New Solution: "The Double-Momentum, Double-Clipping Maestro"

The authors of this paper introduce a new conductor named Byz-Clip21-SGD2M. Think of this algorithm as a super-smart, tough, and privacy-conscious conductor who uses two main tricks to keep the orchestra playing perfectly, even with spies and saboteurs.

1. The "Double-Momentum" (The Echo Chamber)

Imagine you are trying to hear a whisper in a noisy room. If you just listen to one second of audio, it might be garbled. But if you remember what you heard a moment ago and blend it with what you hear now, the signal becomes clearer.

This algorithm uses two layers of this "memory":

Client Memory: Each musician keeps a running average of their own recent notes to smooth out their own mistakes.
Server Memory: The conductor keeps a running average of the notes coming from everyone.

This "double echo" helps cancel out the random noise (privacy noise) and the chaotic screaming (Byzantine attacks) so the true melody can emerge.

2. The "Clipping" (The Volume Limiter)

In the old days, if a saboteur screamed at 100 decibels, it would drown out the whole orchestra. To stop this, the new conductor puts a Volume Limiter on every recording.

If a musician tries to send a note that is too loud (too extreme), the conductor simply turns the volume down to a safe, pre-set level.
This ensures that no single person, whether a saboteur or just someone having a bad day, can dominate the symphony.
Crucially, this also helps with privacy. By capping the volume, the conductor knows exactly how much "static" (noise) to add to hide the original notes, making the privacy guarantee much stronger.

Why This Paper is a Big Deal

Previous attempts to solve this problem were like trying to build a fortress with rules that only work if the enemy is weak or if the weather is perfect. They assumed things like "gradients must be bounded" (a fancy way of saying "the musicians can never play too loudly"). But in the real world, data is messy, and gradients can get huge.

This paper breaks those rules.

No Unfair Assumptions: The new method works even if the data is wild and the gradients are huge. It doesn't need a "helper dataset" (a cheat sheet) to work.
High-Probability Success: Instead of saying "it works on average," the authors prove it works almost always. It's like saying, "This bridge will hold up 99.9% of the time, even during a hurricane," rather than "It usually holds up."
Real-World Proof: They tested this on real models (like recognizing handwritten digits) and showed that even when 20% of the clients are malicious saboteurs, their method still learns the best model, often beating the competition.

The Bottom Line

Think of Byz-Clip21-SGD2M as the ultimate team manager for a remote workforce.

It protects the workers' secrets (Privacy).
It fires the trolls who try to ruin the project (Byzantine Robustness).
It uses a smart "memory" system to smooth out mistakes (Double Momentum).
It puts a "cap" on how crazy anyone can get (Clipping).

And the best part? It does all this without needing the team to follow impossible rules. It's a robust, practical, and mathematically proven way to build trustworthy AI in a messy, dangerous world.

1. Problem Statement

The paper addresses the critical challenge of securing Federated Learning (FL) against two simultaneous threats:

Byzantine Attacks: Malicious clients (Byzantine nodes) that send arbitrary, adversarial updates to disrupt the training process.
Privacy Leakage: The risk that gradients or model updates reveal sensitive information about local data, necessitating Differential Privacy (DP).

The Core Conflict: Existing methods struggle to combine these two defenses.

Theoretical Limitations: Most prior work relies on unrealistic assumptions, such as bounded gradient norms (which fail even for simple quadratic objectives) or requires access to auxiliary server-side datasets.
Algorithmic Conflicts: DP requires adding noise to updates, which reduces consistency and makes it harder to detect Byzantine attacks. Conversely, robust aggregation (to filter Byzantine attacks) can amplify the negative effects of DP noise, hindering convergence.
Gap: There was a lack of algorithms that provide high-probability convergence guarantees under standard assumptions (L-smoothness and sub-Gaussian noise) while handling both Byzantine adversaries and DP simultaneously.

2. Methodology: Byz-Clip21-SGD2M

The authors propose a new algorithm, Byz-Clip21-SGD2M, which integrates four key mechanisms to overcome the aforementioned limitations:

Double Momentum:
- Client-side Momentum ( $v_t$ ): Smooths mini-batch gradient noise. The authors note that without this, methods like EF21-SGD fail to converge under mini-batch noise.
- Server-side Momentum ( $m_t$ ): Counteracts the accumulation of DP noise in the buffers, preventing the noise from destroying convergence.
Error Feedback (EF21-style):
- Compensates for the bias introduced by heterogeneous client data and the compression/clipping operations. This allows the algorithm to handle data heterogeneity without requiring the restrictive "bounded gradient" assumption found in prior work.
Carefully Designed Clipping:
- Updates are clipped to a threshold $\tau$ before adding DP noise. This ensures the sensitivity of the mechanism is bounded, which is essential for DP guarantees.
- Crucially, the clipping acts as a contractive compressor, which the authors leverage in their high-probability analysis to keep update norms bounded.
Robust Aggregation:
- The server uses a robust aggregation rule ( $R_{Agg}$ ) satisfying the $(\delta_{byz}, c)$ -robustness definition (e.g., Coordinate-wise Median or Geometric Median). This limits the damage caused by Byzantine clients.

Algorithm Flow:

Clients compute local gradients and update a momentum buffer.
Gradients are clipped, and DP noise is added.
Error feedback is applied to correct for bias.
The server aggregates the noisy, clipped updates using a robust rule.
The global model is updated using a server-side momentum buffer.

3. Key Contributions

New Algorithm: Introduction of Byz-Clip21-SGD2M, the first algorithm to jointly handle Byzantine robustness and Differential Privacy with a unified design involving double momentum and error feedback.
Relaxed Assumptions: Theoretical analysis is conducted under standard assumptions:
- $L$ -smoothness of local functions.
- $\sigma$ -sub-Gaussian gradient noise.
- No bounded gradient assumption: This is a significant departure from prior literature (e.g., Safe-DSHB, DP-BREM) which often assumed gradients were bounded by a constant $M$ .
- Weaker Heterogeneity Assumption: The bounded gradient dissimilarity is only required at initialization ( $x_0$ ), not uniformly over the entire space.
High-Probability Convergence: The paper provides high-probability convergence guarantees (rather than just in-expectation), which is crucial for practical reliability.
Tight Utility Bounds: The derived convergence rates match state-of-the-art lower bounds in the absence of adversaries and improve utility guarantees in the presence of both DP and Byzantine attacks.
Empirical Validation: Extensive experiments on MNIST using CNN and MLP models demonstrate the algorithm's effectiveness.

4. Theoretical Results

The main convergence theorem (Theorem 5.1) establishes that the average squared gradient norm converges to a neighborhood of size:
$\tilde{O}\left( \Delta_0 \left( R + R^{2/3} \right) \right)$
Where $R$ represents the error terms:
$R = \underbrace{\frac{\sqrt{d}\sigma_\omega}{\sqrt{GT\tau}}}_{\text{Privacy Error}} + \underbrace{\frac{\sqrt{c\delta_{byz}d}\sigma_\omega}{\sqrt{T\tau}}}_{\text{Privacy-Byzantine Interaction}} + \underbrace{\sqrt{c\delta_{byz}}}_{\text{Byzantine Error}}$

Key Implications:

Privacy-Utility Trade-off: The first term reflects the cost of DP noise.
Byzantine Robustness: The last term reflects the cost of Byzantine clients.
Interaction: The middle term shows the additional penalty incurred when enforcing both privacy and robustness simultaneously.
Special Cases:
- No Adversaries: Recovers the standard $\tilde{O}(1/\sqrt{GT})$ rate for non-convex optimization.
- DP Only: Matches known lower bounds for local DP.
- Byzantine Only: Matches the in-expectation lower bounds of prior Byzantine-robust works.

5. Experimental Results

The authors evaluated Byz-Clip21-SGD2M against baselines Byz-Clip-SGD and Safe-DSHB on the MNIST dataset with CNN and MLP models.

Attack Scenarios:
- IPM Attack: Byzantine clients multiply the average of honest updates by $-10$.
- Label Flipping: Byzantine clients flip labels ( $y \to 9-y$ ).
Variables: Number of Byzantine clients (up to 40% of total) and Privacy Budget ( $\epsilon \in \{3, 8, 13, 18, 23\}$ ).
Findings:
- Superior Performance: Byz-Clip21-SGD2M consistently matched or surpassed baselines in test accuracy across all configurations.
- Robustness: The algorithm maintained high accuracy even with a high fraction of Byzantine clients and strict privacy budgets.
- Sub-sampling: An extended variant (Byz-Clip21-SGD2M+) utilizing sub-sampling for privacy amplification was also tested, showing competitive performance, particularly at higher privacy budgets.

6. Significance and Impact

Theoretical Advancement: This work breaks the reliance on "bounded gradient" assumptions that have plagued the field of differentially private and Byzantine-robust FL. It proves that strong guarantees are possible under standard, realistic conditions.
Practical Applicability: By removing the need for auxiliary datasets and relaxing assumptions, the algorithm is more deployable in real-world scenarios where data distributions are heterogeneous and gradients can be unbounded.
Regulatory Compliance: The unified framework addresses the dual requirements of modern AI regulations (e.g., GDPR, EU AI Act) regarding both data privacy and system robustness/security.
Foundation for Trustworthy AI: The paper provides a principled foundation for building FL systems that are simultaneously private, robust, and efficient, paving the way for more trustworthy AI deployment in sensitive domains.