📊 statistics

Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation

This paper establishes the first federated Gaussian approximations for linear stochastic approximation with explicit communication-computation trade-offs and heterogeneity-aware error bounds, and leverages these results to develop a non-asymptotically valid online multiplier bootstrap procedure for inference on the last iterate.

Original authors: Ilya Levin, Maksim Shuklin, Eric Moulines, Paul Mangold, Sergey Samsonov

Published 2026-05-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ilya Levin, Maksim Shuklin, Eric Moulines, Paul Mangold, Sergey Samsonov

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 to solve a giant, complex puzzle together. They are in different rooms (different computers or "agents") and can't see the whole picture at once. They each have their own piece of the puzzle, but the pieces are slightly different because of how they were cut (this is called heterogeneity).

To solve the puzzle, they use a method called Federated Learning. Instead of sending all their pieces to a central table every second (which would be slow and clog the internet), they work on their own pieces for a while, make some progress, and then send their current progress to a central hub. The hub averages everyone's progress and sends a new "best guess" back to everyone. They repeat this cycle.

This paper is about two main things: how fast they actually solve the puzzle and how confident they can be that their solution is correct.

Here is a breakdown of the paper's discoveries using simple analogies:

1. The "Speed vs. Accuracy" Trade-off

In the past, researchers mostly looked at how fast this group could solve the puzzle. This paper asks a different question: "How close is their final answer to a perfect, bell-curve distribution?"

Think of the final answer as a dart thrown at a board. If you throw enough darts, they usually form a nice, round cluster (a Gaussian distribution). The authors wanted to know: How many throws (iterations) does it take for the cluster to look perfectly round?

They found that the shape of this cluster depends heavily on two choices the group makes:

Step Size: How big of a step they take when updating their guess.
Local Updates: How long they work alone before checking in with the group.

The Discovery: They proved that if the group takes smaller steps over time and works alone for longer periods as they get closer to the solution, they can still form a perfect cluster. However, if they work alone too long without adjusting their steps, the cluster gets distorted. They provided a mathematical "speed limit" (a bound) on how quickly this cluster becomes a perfect circle, accounting for how different the friends' puzzle pieces are.

2. The "Magic Mirror" (Multiplier Bootstrap)

Usually, to know if your solution is good, you need to calculate a complex "uncertainty map" (the covariance matrix). Imagine trying to draw a map of a foggy forest while standing in the middle of it; it's very hard to get right without a satellite view.

The authors developed a new tool called the Multiplier Bootstrap.

The Old Way: Try to calculate the foggy map directly using complex math.
The New Way (The Magic Mirror): Instead of calculating the map, you create a "shadow version" of the process. You take the friends' current progress and run a simulation where you randomly shake their hands (add random weights) to see how their answers wiggle.

The Big Claim: The authors proved that this "wiggling shadow" perfectly mimics the real uncertainty of the solution.

Why it's cool: You don't need to know the complex "foggy map" (the asymptotic covariance matrix) to do this. The shadow is the map.
The Guarantee: They proved mathematically that this shadow method works even when the group hasn't finished the puzzle yet (non-asymptotic). It gives you a reliable "confidence interval" (a range where the true answer likely sits) without needing to know the future.

3. The "Heterogeneity" Problem

In real life, not everyone is the same. Some friends are faster, some have better pieces, some are distracted. This is called heterogeneity.

The paper shows that this "difference between friends" creates a specific kind of noise. If everyone is identical, the solution is easy to predict. But because they are different, the "cluster" of answers gets stretched or squashed. The authors' formulas explicitly measure this stretching. They show that you can still get a reliable answer, but you have to account for how different the group members are.

Summary of the "Takeaway"

The Problem: In distributed learning, it's hard to know how confident you should be in your answer, especially when data is messy and different across users.
The Solution: The authors created a new mathematical framework that:
1. Measures the "Roundness": They calculated exactly how many steps it takes for the group's answers to settle into a predictable, bell-curve shape, even with messy, different data.
2. The "Shadow" Trick: They proved you can use a "shadow simulation" (bootstrap) to create confidence intervals without needing to solve the impossible math problem of mapping the uncertainty directly.

In a nutshell: They gave the group of friends a new rulebook that tells them exactly how to work together to not only solve the puzzle faster but also to know, with mathematical certainty, that they haven't just gotten lucky.

Technical Summary: Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation

Problem Statement

The paper addresses the challenge of statistical inference in Federated Linear Stochastic Approximation (FedLSA). While Federated Averaging (FedAvg) is the standard algorithm for collaborative model training across distributed agents, existing theoretical literature primarily focuses on optimization convergence rates. There is a significant gap in providing non-asymptotic guarantees for statistical inference, specifically for constructing confidence intervals for the model parameters.

Current approaches for inference in federated settings often rely on asymptotic convergence to a limiting Gaussian distribution or require explicit estimation of the asymptotic covariance matrix ( $\Sigma_\infty$ ), which is computationally expensive and difficult to estimate accurately in finite-sample regimes. Furthermore, existing non-asymptotic Gaussian approximation results for stochastic approximation (SA) and Stochastic Gradient Descent (SGD) do not fully capture the complexities introduced by heterogeneity (differences in local data distributions) and the specific communication-computation trade-offs inherent in federated learning, particularly when the number of local iterations varies over time.

Methodology

The authors develop a rigorous theoretical framework to analyze the last iterate of FedLSA under a regime of decreasing step sizes and an increasing number of local iterations. The methodology proceeds through three main stages:

High-Order Moment Bounds and Error Decomposition:
The authors extend the error decomposition framework to accommodate non-constant step sizes and varying local update counts. They decompose the estimation error $\theta_t - \theta^\star$ into four components:
- A transient term decaying from initialization.
- A bias term arising from statistical heterogeneity.
- A fluctuation term due to heterogeneity.
- A fluctuation term due to stochastic noise.
  Crucially, they establish high-order moment bounds (for $p \ge 2$ ) for these error components. This is a novel contribution, as previous literature largely focused on second-order moments. These bounds explicitly quantify the effects of local step sizes, the number of local updates, and data heterogeneity.
Non-Asymptotic Gaussian Approximation (GAR):
Using the derived moment bounds, the paper establishes a Berry-Esseen-type bound for the last iterate of FedLSA. The analysis employs a decomposition of the normalized error into a linear statistic $W_t$ and a remainder term $D_t$ . By applying concentration inequalities and tools from the theory of nonlinear statistics (specifically Shao and Zhang [2022]), the authors bound the convex distance between the distribution of the normalized last iterate and a Gaussian distribution.
- The analysis tracks the interplay between the step size decay rate ( $\gamma_\eta$ ) and the growth rate of local iterations ( $\gamma_H$ ).
- It explicitly accounts for the convergence rate of the empirical covariance matrix $\Sigma_t$ to the asymptotic covariance $\Sigma_\infty$ , showing that approximating $\Sigma_\infty$ directly can introduce slower convergence rates.
Online Multiplier Bootstrap:
To facilitate practical inference without estimating $\Sigma_\infty$ , the authors propose an online multiplier bootstrap procedure. This method generates bootstrap iterates by introducing random multiplicative weights to the local updates.
- The procedure is fully online and data-driven.
- Theoretical validity is proven by showing that the conditional distribution of the bootstrap statistic approximates the sampling distribution of the normalized estimation error with a rate comparable to the Gaussian approximation rate, effectively bypassing the need to estimate the asymptotic covariance matrix.

Key Contributions

The paper makes the following specific contributions:

First High-Order Moment Bounds for FedLSA: The authors provide the first moment bounds of order $p \ge 2$ for FedLSA with decreasing step sizes and increasing local iterations. These bounds capture heterogeneity bias and noisy updates, extending previous work that was limited to constant step sizes or second-order moments.
Non-Asymptotic Gaussian Approximation for the Last Iterate: The paper presents the first Gaussian approximation bound for the last iterate of FedLSA in a federated setting with increasing local iterations. The bound is expressed in terms of convex distance and scales up to $t^{-1/2}$ (up to logarithmic factors and heterogeneity terms), explicitly capturing the trade-offs between communication frequency and local computation.
Valid Multiplier Bootstrap for Federated Inference: The authors develop and prove the validity of an online multiplier bootstrap procedure for the last iterate. This method avoids the explicit estimation of the asymptotic covariance matrix $\Sigma_\infty$ , which is often a bottleneck in federated inference.
Lower Bound Analysis: The paper provides a non-asymptotic lower bound for the convex distance in a simplified 1-dimensional setting, demonstrating that the derived rates are tight and that the convergence of the covariance matrix is a limiting factor in the approximation error.

Results

The theoretical results are summarized as follows:

Convergence Rates: Under the scheme of decreasing step sizes ( $\eta_t \propto t^{-\gamma_\eta}$ ) and increasing local iterations ( $H_t \propto t^{\gamma_H}$ ), the Gaussian approximation error for the last iterate is bounded by terms scaling as $N^{-1/2}t^{-\gamma_\eta/2}$ , $N^{1/2}t^{-\gamma}$ , and $t^{-(3\gamma-\gamma_\eta)/2}$ , where $\gamma = \gamma_\eta - \gamma_H$ .
Bootstrap Validity: The multiplier bootstrap procedure achieves a convergence rate of the same order ( $O(t^{-1/2})$ ) as the Gaussian approximation. This confirms that the bootstrap distribution accurately approximates the true sampling distribution without requiring knowledge of $\Sigma_\infty$ .
Numerical Validation: Experiments on a Garnet environment with heterogeneous agents demonstrate that the proposed bootstrap-based confidence intervals (using empirical quantiles and standard deviation) achieve better coverage than plug-in Gaussian baselines, particularly in early iterations and regimes with increasing local updates. The plug-in method improves as the sample size grows but lags in finite-sample performance.

Significance and Claims

The paper claims to close a critical gap in the federated learning literature by providing the first theoretically grounded, non-asymptotic methods for quantifying uncertainty in federated linear stochastic approximation.

Heterogeneity-Aware: Unlike previous works that assumed homogeneous agents or constant local steps, this analysis explicitly models the impact of data heterogeneity and the dynamic schedule of local updates.
Practical Inference: By validating the multiplier bootstrap, the paper offers a practical tool for constructing confidence intervals in federated settings without the computational burden of estimating the asymptotic covariance matrix.
Confirmation of Hypotheses: The results confirm the hypothesis (previously conjectured without proof by Bonnerjee et al. [2025]) that multiplier bootstrap procedures can provide valid inference for federated estimators, even in complex regimes with varying local iterations.
Trade-off Insight: The analysis highlights a fundamental trade-off: while increasing the number of local iterations improves optimization efficiency and communication costs, it can adversely affect the rate of distributional convergence (Gaussian approximation), suggesting that a constant number of local updates may be preferable for statistical inference, though this is not always implementable due to communication constraints.

In summary, the paper establishes a rigorous foundation for statistical inference in federated learning, moving beyond asymptotic guarantees to provide finite-sample, non-asymptotic error bounds and a validated inference procedure.