📊 statistics

Sharp Gaussian approximations for Decentralized Federated Learning

This work establishes two generalized Gaussian approximation results for local SGD in decentralized federated learning—a Berry-Esseen theorem for the final iterations and uniform-in-time approximations for the entire trajectory—enabling valid statistical inference and robust detection of adversarial attacks via bootstrap procedures.

Original authors: Soham Bonnerjee, Sayar Karmakar, Wei Biao Wu

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Soham Bonnerjee, Sayar Karmakar, Wei Biao Wu

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 a group of friends trying together to solve a huge puzzle, but they are in different rooms and cannot directly show their pieces to each other. This is Federated Learning. Instead of sending their private puzzle pieces (data) to a central room, they keep them locally. They work for a while on their own pieces, then meet briefly to compare notes and adjust their strategy. This is Decentralized Federated Learning (DFL), where they talk to neighbors instead of a central boss.

The paper you provided is like a strict "rulebook" written by mathematicians to understand exactly how well this group performs—not only at the end of the game, but at every single step along the way.

Here is a breakdown of what they discovered, using simple analogies:

1. The Problem: "We know they will finish, but do we know how they will finish?"

For a long time, scientists knew that if these friends kept working, they would eventually solve the puzzle (convergence). However, they had no precise way to measure the uncertainty of their progress.

The Gap: If you ask, "How close are we to the right answer?" or "Is this strange move by a friend a mistake or a sign of sabotage?", the old mathematics could not provide a reliable "yes" or "no" answer with a confidence value.
The Goal: The authors wanted to create a "statistical GPS" that tells you exactly how far the group is from the perfect solution at a given time and whether a sudden change in direction is normal or a sign of an attack.

2. The First Discovery: The "Berry-Esseen" Speedometer

The authors developed a new method to measure the error of the group's final answer.

The Analogy: Imagine you are timing a race. The old mathematics could state the runners' average speed. This new mathematics acts like a high-precision speedometer that shows you exactly how much the runners might accelerate or slow down due to random stumbling blocks on the road.
The Trade-off (The "Tug-of-War"): They discovered a fascinating tension between how many friends are in the group (clients) and how often they talk (synchronization).
- If the group is too huge and they talk too rarely, the "noise" of everyone working alone overwhelms the signal, and the mathematics breaks down.
- They proved there is a "sweet spot" for how often they must synchronize, depending on the group size. If you have too many people, you must synchronize more frequently; otherwise, the mathematics says: "We cannot trust the result."

3. The Second Discovery: The "Time-Uniform" Movie Camera

Most previous methods looked only at the final photo of the solved puzzle. But what if someone tries to sabotage the game halfway through?

The Analogy: Instead of looking only at the finished puzzle, the authors built a movie camera that records the entire journey.
The Innovation: They created a mathematical "shadow" of the group's entire journey. This shadow is a smooth, predictable path (a Gaussian process) that mimics the real, chaotic path the friends take.
Why it matters: Since they have this "shadow film," they can compare the real group's movements with the shadow. If the real group suddenly deviates from the shadow's path, the mathematics can shout: "Something is wrong!" This enables the detection of adversarial attacks (like a friend trying to poison the puzzle) in real time, not just afterward.

4. Two Versions of the "Shadow"

The paper offers two ways to create this shadow film, each with different privacy costs:

Aggr-GA (The Group Hug): This version requires everyone to share their specific "noise" details to create the perfect shadow. It is the most accurate but requires more sharing (less privacy).
Client-GA (The Local Whisper): This version allows each friend to create their own small part of the shadow locally and share only the final result. It is somewhat less precise but keeps everyone's private data much safer.

5. The Proof: Simulations

The authors did not just write equations; they ran thousands of computer simulations.

They showed that their new "speedometer" and "movie camera" are much sharper and more accurate than the old, standard methods (which were like trying to guess the weather by looking at a single cloud).
They demonstrated that their method can successfully detect when a "bad actor" joins the group and starts changing the rules, uncovering the attack much faster than before.

Summary

In short, this paper provides the mathematical tool to:

Measure uncertainty in decentralized learning with high precision.
Detect sabotage (adversarial attacks) by observing the entire process, not just the final result.
Balance the trade-off between a large group and the need for frequent communication.

It transforms a "black-box" learning process into a transparent, monitorable system where you can trust the numbers and detect fraud early.

Technical Summary: Sharp Gaussian Approximations for Decentralized Federated Learning

Problem Statement

Federated Learning (FL) has become a standard paradigm for collaborative model training while preserving privacy, with Decentralized Federated Learning (DFL) emerging as a robust alternative that eliminates dependence on a central server. While the convergence properties and speed of Local SGD (the primary optimization method in DFL) are well-established, there is a significant gap in understanding the asymptotic statistical properties of the algorithm's fluctuations around the true parameter vector.

Current literature lacks rigorous statistical guarantees for two critical practical needs:

Inference on final iterates: Establishing valid confidence sets and hypothesis tests for final model parameters requires more than just Central Limit Theorem (CLT) results; it demands precise error bounds (of the Berry-Esseen type) to support bootstrap procedures, especially when estimating local covariance structures is computationally prohibitive.
Trajectory monitoring: In high-risk applications (e.g., autonomous systems, financial platforms), detecting adversarial attacks (such as model poisoning) requires statistical control over the entire trajectory of SGD iterates, not just the final output. Classical inference methods struggle with the complex dependency structures inherent to DFL, and existing uniform-in-time approximations (such as Komlos-Major-Tusnady) often rely on assumptions (e.g., rapid decay, well-conditioned covariance) not met by general Local SGD with decaying step sizes.

Methodology

The authors propose a refined theoretical framework to establish sharp Gaussian approximations for Local SGD iterates in a decentralized setting. The methodology includes:

Model Setup: A DFL setting with $K$ clients, each optimizing a local loss function $f_k$ with potentially heterogeneous data distributions $P_k$ . Clients perform local updates and synchronize every $\tau$ steps over a fixed connectivity graph defined by a symmetric matrix $C$ .
Berry-Esseen Analysis: The authors derive non-asymptotic bounds for the Kolmogorov distance between the distribution of Local SGD iterates (both Polyak-Ruppert averaged and final iterates) and a Gaussian distribution. This involves careful linearization of SGD updates and the application of Lindeberg-type coupling arguments adapted to the decentralized, synchronized structure.
Uniform-in-Time Coupling: To address trajectory monitoring, the paper goes beyond the standard CLT to establish uniform-in-time Gaussian approximations. This involves constructing a Gaussian process that mimics the Local SGD path with a quantifiable error bound that holds uniformly over all time steps $t \in [1, n]$ .
Two Approximation Schemes:
- Aggr-GA (Aggregated Gaussian Approximation): A global approximation assuming full propagation of covariance structures, offering sharper rates but potentially higher privacy costs.
- Client-GA (Client-Level Gaussian Approximation): A localized approximation mimicking the local SGD procedure using only local covariance information, trading a slight increase in approximation error for improved privacy and computational efficiency.

Main Contributions

1. Berry-Esseen Theorems for Local SGD

The paper establishes the first explicit Berry-Esseen bounds for Local SGD updates.

Theorem 2.1: For the Polyak-Ruppert averaged iterates $\bar{Y}_n$ , the paper proves:
$d_{Berry-Esseen} \lesssim \frac{1}{\sqrt{nK}} + n^{1/2-\beta}\sqrt{K} + n^{-\beta/2}\frac{1}{\sqrt{K}}$
where $\eta_t \asymp t^{-\beta}$ . This result explicitly clarifies the condition $K = o(n^{2\beta-1})$ required for the CLT to hold, a condition previously noted in related works without justification.
Theorem 2.2: A corresponding bound is provided for the final iterates $Y_n$ , scaled as $n^{\beta/2}(Y_n - \theta^*_K)$ .
Implication: These bounds enable valid multiplier bootstrap procedures for constructing asymptotically valid confidence sets without requiring explicit estimation of complex local covariance matrices.

2. Trade-off between Computation and Communication

The analysis reveals a phase transition in the convergence of the Berry-Esseen bound based on the relationship between the number of clients $K$ and iterations $n$ .

Theorem 2.3 & Remark 2.2: If $K = o(\sqrt{n})$ , an optimal step size $\beta = 3/4$ exists. However, if $K \gtrsim \sqrt{n}$ , the Berry-Esseen bound does not converge to zero for any $\beta \in (1/2, 1)$ , even though the CLT may still hold. This highlights a fundamental hardness in Local SGD when the number of clients scales, differing from standard convergence rates.

3. Uniform-in-Time Gaussian Approximations

The paper introduces the first uniform-in-time Gaussian approximations for stochastic approximation algorithms in a decentralized setting.

Theorem 3.1 (Aggr-GA): Establishes a coupling between the aggregated Local SGD process and a Gaussian process $Y^G_t$ with an error rate of $O_P(n^{1-\beta} + n^{1/p}K^{-1/2}\log n)$ .
Theorem 3.2 (Client-GA): Provides a client-level coupling mimicking local updates, with an error rate of $O_P(n^{1-\beta} + (n/K)^{1/4 + 1/2p}(\log n)^{3/2})$ .
Significance: These results enable statistical hypothesis testing over the entire trajectory and allow for the detection of adversarial attacks (e.g., model poisoning) using CUSUM-like statistics and Gaussian bootstrap methods, previously considered intractable.

4. Empirical Validation

Extensive simulations validate the theoretical findings:

Berry-Esseen Rates: Simulations confirm the decay of the approximation error with $n$ and the trade-off behavior with $K$ , matching theoretical rates.
Trajectory Approximation: Q-Q plots show that the proposed Aggr-GA and Client-GA approximations significantly outperform standard Brownian motion (functional CLT) approximations, even with finite samples.
Attack Detection: The proposed bootstrap-based algorithms successfully detect label-flipping attacks and model poisoning in simulated environments and on the MNIST dataset, achieving high detection performance with controlled false-positive rates.

Significance and Claims

The paper claims to be the first work to derive:

Berry-Esseen bounds specifically for Local SGD updates in a decentralized setting, providing the necessary theoretical foundation for bootstrap-based inference.
Sharp uniform-in-time Gaussian approximations for the entire trajectory of Local SGD, enabling valid statistical inference for anomaly detection in high-risk decentralized systems.

The authors emphasize that these results go beyond standard Central Limit Theory to offer sharper, step-by-step control over the iterates. This enables the development of powerful statistical inference methods (confidence sets, hypothesis tests) that are robust to the complex dependencies and privacy constraints of DFL. The work bridges the gap between theoretical convergence guarantees and practical statistical inference, offering a path to sharper results in related fields such as multi-agent systems and transfer learning.