Sharp Gaussian approximations for Decentralized Federated Learning
Authors: Soham Bonnerjee
Sayar Karmakar
Wei Biao Wu
Venue: NeurIPS 2025 spotlight ()
Keywords: Federated Learning
Distributed Systems
SGD
Gaussian approximation
Primary area: theory

Abstract: Federated Learning has gained traction in privacy-sensitive collaborative environments, with local SGD emerging as a key optimization method in decentralized settings. While its convergence properties are well-studied, asymptotic statistical guarantees beyond convergence remain limited. In this paper, we present two generalized Gaussian approximation results for local SGD and explore their implications. First, we prove a Berry-Esseen theorem for the final local SGD iterates, enabling valid multiplier bootstrap procedures. Second, motivated by robustness considerations, we introduce two distinct time-uniform Gaussian approximations for the entire trajectory of local SGD. The time-uniform approximations support Gaussian bootstrap-based tests for detecting adversarial attacks. Extensive simulations are provided to support our theoretical results.

Sharp Gaussian approximations for Decentralized Federated Learning
Soham Bonnerjee edu
Sayar Karmakar sayarkarmakar@ufl. edu
Wei Biao Wu
wbvu@uchicago. edu
Abstract
Federated Learning has gained traction in privacy-sensitive collaborative environ- ments, with local SGD emerging as a key optimization method in decentralized settings. While its convergence properties cal guarantees beyond convergence remain limited. In this paper, we present two generalized Gaussian approximation results for local SGD and explore their impli- cations. First, we prove a Berry-Essee theorem for the final local SGD iterates, enabling valid multiplier bootstrap procedures. Second, motivated by robustness considerations, we introduce two distinct time-uniform Gaussian approximations for the entire trajectory of local SGI). The time-uniform approximations support Gaussian wootstrap-based tests for detecting adversarial attacks. Extensive simu- lations are provided support our theoretical results.
well-studied, asymptotic statisti-
Introduction
Federated Learning (FL), introduced by McMahan et al. [2017] decentralized model training paradigm while maintaining privacy, has seen rapid advancements driven by its applicability in domains such next-word prediction mobile devices, healthcare, and cross-silo collaborations among institutions. Subsequent works Kairouz et al. [2021]. Li et al. [2020]. Karimireddy et al. [2020], Wang et al. [2020b], Alistarh al. [2017], Lin al. [2018] have addressed key challenges around privacy and computational efficiency. Research has also extended to decentralized federated learning (DFL) Lalitha
[2019], Lian et al. [2017], He al. [2019], Kim al. [2020], Lian et al. [2017]. Wang and Joshi [2021], Singh et al. [2023], which eliminates reliance on central server by enabling peer-to-peer collaboration, thereby enhaneing robustness, fairness, and resilience to adversarial threats. We refer to Gabrielli et al. [2023], Yuan et al. [2024] for comprehensive survey of the literature. In this regard, Local SGD Stich [2019]. Khaled al. [2020], Woodworth et al. [2020b] has emerged widely adopted algorithm, allowing clients perform multiple local updates before synchronizing. significantly reducing communication overhead.
While theoretical guarantees for convergence and speed in local SGD have been developed Haddad- pour al. [2019]. Woodworth et al. [2020a], Koloskova et al. [2020], a gap remains understand- ing the statistical properties of fluctuations around the true parameter vector. This gap has practical implications: first, statistical guarantees on the final iterates are essential for inference; second, mon- itoring the entire trajectory is crucial for detecting adversarial behavior in high-stakes settings like traffic networks, autonomous systems, and financial platforms. For the first issue, emerging works on central limit theory Li et al. [2022], Gu and Chen [2024] provide initial insights, but estimat- ing local covariance structures numerically intensive. Multiplier bootstrap methods Fang et al. [2018], Fang [2019] offer computational relief, but require stronger results beyond the central limit theory. The second issue is even more challenging, as demands control over the entire trajectory of local SGD, not just the last iterate. Classical inferential methods struggle with DFLs complex dependency structure, and key open question is how to develop statistically valid, computationally efficient inference methods with minimal distributional assumptions and explicit error control.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1.1 Main Contributions
In this article, we address this gap by proposing different refined Gaussian approximations that nat- urally lead to suitable bootstrap procedures. Our results go beyond central limit theory to establish sharper, step-by-steg as well uniform control over the DFL iterates {Y,). These results not only fa- cilitate relevant bootstrap-based inference to produce asymptoticalll-valis confidence sets, but also enables us to perform statistical hypothesis tests to detect attacks, which are inaccessible otherwise. Our main contributions can be summarized as follows:
we provide an explicit characterization of the Berry-Esseen error for the Polyak- Ruppert version of the local SGD algorithm (Algorithm 1) iterates. In particular, under standard regularity conditions on the client-level optimization problems as well as for general class of connection graph of clients, we prove:
(1) In Section 2,
Theorem 1.1 (Theorem 2.1, Informal). For decentralized federtted learning set-up with K clients, the rolper-ruppert averaged iterates of the local SGD algorithm with n. iterations, and step size m x t achieves
dBerry-Easeen S n 11/2-
Our result explicitly underpins the source of the assumption K = o(122-11 used to derive central limit theory for the local SGD iterates Gu and Chen [2024]. Theorem 2.1 accompanied by a cor- responding Besre-Esscenn theorem (Theorem 2.2) for final iterates of the DFL algorithm. Both these theorems involve a finite sample scaling (equivalently, scaling by a covariance matrix depending upon n, the number of iterations) of the local SGD iterates, leading to optimal error bounds. Our result first such Berry-Esseen bounds for the local SGD updates.
(2) The finite sample scaling considered in Theorems 2.1 and 2.2 is usually not estimable. Shifting focus to an asymptotic, global scaling, our results uncover a novel trade-off involving the Berry-Esseen result. In Theorem 2.3, we show that for K = of (n)n), B 3/4 represents an optimal choice of step-size; however, for K Σ / /i, for no 3 E (1/2, 1) does the Berry- Esseen bound converge towards zero This observation is not merely an artifact of our proof, and the phase-transition are empirically validated through extensive simulations.
(3) A key motivation behind the local SGD algorithm is maintaining privacy. From this perspective, asymptotic inference on the final iterates is insufficient for detecting breach of privacy through some adversarial attack. Indeed, in Section 3, we discuss a general framework to detect broad class of model poisoning in a distributed setting. Through an example in Section 3.1, we point out a class of maximal statistics which can be used to detect such attacks. Moreover, to perform inference on such statistics, we move beyond controlling simply the end-term iterates to a more general time-uniform Gaussian coupling of the entire local SGD process. Motivated from above, in Theorem 3.1, we establish a time-uniform Gaussian approximation.
Theorem 1.2 (Theorem 3.1, Informal). If the local SGD algorithm with K clients runs iterations with step size TJt x 1-3, then there exists a Gaussian process Y. -II-WA] A)Y + +7 with Z, i..dd (0, T') for some matrix I and A being the Hessian of the problem, such that,
3/P
Σ x20
max IstsA
VK
Here we assume 2 2 finite moments of the local noisy gradients. To facilitate bootstrap, we also provide an explicit characterization P. To the best of our knowledge, these results constitute the first time-uniform Gaussian approximation results for stochastic approximation algorithms.
(4) In particular, Theorem 3.1 presents a Gaussian approximation (referred as Aggr-GA) with a slightly sharper rate, but one requiring extensive synchronization during the bootstrap procedure. Recognizing that this may not be ideal from a privacy perspective, we further present separate, client-level Gaussian approximation Client-CA in Theorem 3.2, which completely mimics the local SGD procedure. The approximation Client-GA is much more localized, leading to slight worsening of the approximation error but increased efficiency with regards to synchronization and computational cost. We argue and validate with simulations, that our Gaussian approximations are much sharper than that indicated by standard, off-the-shelf functional central-limit theorem. In fact, our Gaussian approximations represent a version of the covariance-matching approximations introduced by Bonnerjee et al. [2024], however in a multivariate, non-stationary environment.

---

(5) Finally, in Section 4, we validate our theoretical findings with extensive numerical exercises. Our simulation results in Sections 4.1 and 4.2 not only indicate the sharpness our theoretical re- sults, but also project vividly the Moreover, the numerical results Section 4.3 shows that the proposed Gaussian approximations Aggr-GA and C1 Client-GA are significantly better than an off off-the-shelf Brownian-motion based ap- proximation, even in finite sample, complementing Theorems 3.1 and 3.2 well.
trade-offs discussed in Remark 2.2.
1.2 Notations
In this paper, we denote the set (1....,n) n by [n]]. The d-dimensional Euclidean space is Rd,, with R the positive orthant. For vector E IRd |a| denotes its Euclidean norm. The set of m n real matrices is denoted by Rm and correspondingly, for M E IR=x |M denotes its Frobenius norm. For random vector X Rd, we denote || == / [ We also denote in-probability convergence, and stochastic boundedness by op and Op respectively. We write an S b, if an S C'b, for some constant > 0, and On x bn Cib,, I an I C2b,, for some constants C1, C2 > 0.
1.3 Related Literature
In view of the plethora of classical literature for central limit theorems (CLT) on SGD and its differ-
ent variants Ruppert [1988]. Polyak and Juditsky [1992], Chen et al. [2020], it is rather surprising that this area has remained relatively untouched for local SGD or DFL. Li et al. [2022] establish a functional CLT for local SGD, but only when the number of clients is held fixed. More recently, Gu and Chen [2024] established a central limit theory for DFL while allowing an increasing number of clients. Non-asymptotic guarantees for SA algorithms exist in terms of MSE guarantees Nemirovski et al. [2009], Moulines and Bach [201 1]. Lan [2012], Mou et al. [2024]. Recently, Anastasiou et al. [2019] employed Stein's method to derive Gaussian approximation for class of smooth functions of the SGD iterates. Later, Shao and Zhang [2022] obtains the first Berry-Esseen result for online SGD. Samsonov et al. [2024] extended the result to linear stochastic approximation algorithms and temporal difference learning, before being further improved by Wu et al. [2024], Sheshukova et al. [2025].
On the other hand, the best of our knowledge, time-unifone 'entire-path' Gaussian approxima- tion results have not appeared in the stochastic approximation literature. From classical time-series literature, such approximations are known as "Komlos- Mlajor-TTsnady"CCC have a long history Komlós et al. [1975], Sakhanenko [1984, 1989, 2006], Götze and Zaitsev [2008], Berkes al. [2014], Karmakar and Wu [2020] and varied uses change-poing detection Wu and Zhao [2007], wavelet analysis Bonnerjee et al. [2024], simultaneous and time-uniform inference Liu and Wu [2010], Xie et al. [2020], Karmakar et al. [2022], Waudby-Smith et al. [2024]. However, this results require fast enough decay, and well-conditioned covariance structure, which are not usually available in even stochastic approximation algorithms with decaying step-size, let alone a general local SGD algorithm. Therefore, such results not readily applicable in the current settings.
approximations. and
Berry-Esseen theory for local SGD
In this section we establish general, Berry-Esseen type Gaussian approximation result in the de- centralized federated learning setting. In order to rigorously state our results, it is imperative that we formally introduce the local stochastic gradient descent (SGD) algorithm and underline the key assumptions behind our theoretical results. This is done in Section 2. Finally, we present our first Gaussian approximation results in Section 2.2, and discuss the implications therein.
2.1 Preliminaries
Consider a typical decentralized heterogeneous federated learning setting with K clients, each hav- ing access to loss function fx Rd x R" + R, and distribution Ps on R for k E [K]. Here, Ps determines the distribution of the local noisy gradient for each client, realized by sam- pling ek Pt. We allow for heterogeneity among the clients i.e. PA 's are allowed to be different. However, noise sampling (i.e. the g*) assumed to independent from one client to the another. The corresponding risk or regret for the k-th client is denoted by F (0) = Ber., Su (0, Con-
3

---

sider a pre-specified "importance" or weight schedule, given by {wi, W2...., wx} E IR" such that Ek=1 wh 1. In online federated learning setting, the weight schedule are typically known priori, usually informed by the level of heterogeneity for each client, and specified by the moderator of the decentralized system. The goal of DFL is to obtain
i arg min
wy wgFF(() E ER..
(2.1)
2.1.1 Communication
The client-level information is defined by loss functions SK and weights wa- A key aspect of fed- erated learning (FL.) is preserving client privacy, often achieved via a synchronization step with parameter N. At each 7-th step, the moderator aggregates client data and redistributes it fol- lowing a policy. In decentralized SGD, averaging schemes Chaturapruek et al. [2015], Lian et al. [2017]. Ivkin et al. [2019] or gossip-based methods Koloskova et al. [2020], Li et al. [2019], Qin et al. [2021]. Wang and Joshi [2021] are common. In other words, a linear aggregation based on a fixed connection graph, is employed the synchronization step. Following the notation of Gu and Chen [2024], we consider a connection network of the participating clients in the FL system, defined by an undirected graph G (V, E) where V { represents the set of clients and E specifies the edge set such that (i,j) E E if and only if clients i and j are connected. Let C (ciz) E Rg be a symmetric connection matrix defined on G = (V, E), where Cjj is a nonnegative constant that specifies the contribution of the j th data block to the estimation node i. It is required that Ctj 0 and only if (i,j) E E and C1 = 1. Moreover, let c, > O.
Suppose + (0).... 10!.....0!' .f%)
dd denotes the local parameter updates of each client at the 1-th step. Suppose the corresponding local gradient updates be summarized in the matrix G. K ((w f fi, 1. e....... wk V fK 1 ())) E Bdd Here, the initial points of e Re are arbitrarily initialized for k E [K], and have no bearing on the theoretical results. For the sake of completion, we also re-state the local SGD algorithm using the notations and the set-up established in the preceding sections 2.1 and 2.1.1.
Algorithm local SGD
Input: Initializations O, (0).... ,K),)) E RddKK Connection matrix C; Synchronization param- eter T E N; Loss functions fa (* Pa,k [K], weights (wx) K number of iterations n, step-size schedules {7) )=1)
Let Fr = (T, 2T, (T....... J where T, = [
[c, EEE, θ (0, - Gi) Cc, C. Ik. otherwise.
*
n: Fort I.
(2.2)
Output: Y, = K- K
K k=
0h.
To simplify Algorithm 1, each client runs an SGD in parallel till every 7-th step, when they must synchronize their updates in order to properly solve the optimization problem (2.1). Clearly, for
т = 1, Algorithm reduces to the vanilla SGD algorithm for (2.1), which hampers privacy as well as incurs great cost at each step. since typically, the number of clients K increases with the number of iterations n. On the other hand, when r > n, there is no synchronization, and each client would solve their own local optimization problem arg min, F3 (0). defcating the benefits of sharing information. For the purpose of this paper, we assume to be fixed. Moreover, on client level, we also assume that there exists constants b,, b2 0 such that for every k [K], bi S K Kwg S bz.
2.2 Berry-Esseed theorems for client-averaged local SGD updates
Before we describe the Berry-Esseen theorems, it is important we briefly describe the conditions under which it hold. We assume the usual conditions of strong-convexity (Assumption A.1), and the stochastic Lipschitz-ness of the noisy gradients V fA& (Assumption A.2). Moreover, we also assume the continuous differentiability of ft's (Assumption A.3). Due to space constraints, the detailed description of these assumptions, alongside an extended discussion, is relegated to Appendix A. Here, we discuss additional condition unique to the decentralized federated learning setting.

---

Assumption 2.1. The connection matrix C satisfies C1 1 and C = C. Moreover, if X1 2 ... 2 AK denote the ordered eigen-values of C, then Å = and X2 p for some p E (0. 1).
This assumption also appears in Gu and Chen [2024]. Assumption 2.1 ensures that is irreducible and the corresponding stationary distribution is unique: equivalently the underlying graph G is connected, ensuring an overall information sharing between each pair of clients through repeated synchronization steps. Mathematicallyy this can also be observed by noting that limg-xo C K '11", Now, we present the first Gaussian approximation result concerning local SGD updates. Define the generalized Kolmogorov-Smimne metric between random variables Y and 7 as
dc(Y, 2) ==
sup
JP(Y E EN) - P(Z E EN
(2.3)
NEB(R)):A conves
Consider the local SGD output Y, from Algorithm 1. Our first theorem considers its corresponding Polyak-Rupper averaged version
K Σ
PA = n
LE Y2 = K
n
0
(2.4)
k=1
and provides Berry-Esseen theorem, proved in appendix Section B.1.
Theorem 2.1. Define A². : (1 A I, where A == (0i)) E [n]. Further, for & [m). define the random vectors
K U, = 11
Σ
WE Σ
EA4) (0 5t)) with En = n Σ ul 1b, gx(0 = VF+(0) (0,
with
k=1
Let there exist constant C such that for 5o Pk, k E [K], it holds ma (l 13 S
C. Suppose that the step-size schedules of the clients satisfy that nu no + ko) - for some fixed
No. kn > O, and 3 E (1/2,1). 1). Then, under Assumptions 2.1, A.l and A.2 and A.3 with p = 4, and
Yn as in (2.A), holds that
dc(Vn((, -8x),2) Vnk + + - n-
(2.5)
VK* where S hides constants involving d.3, u, L and p. and Z ~ N(,,
A slightly more general result, characterizing the effects of heterogeneity and synchronization, is presented in Corollary F.1 in the appendix. We present Theorem 2.1 here due its enhanced amenability to interpretation, which we provide in subsequent remarks.
Remark 2.1. For a fixed 3 (1/2, 1), the term n 1/2-8 PVK dominates, requiring for the central limit theory to hold for Yn. This condition, also noted in Theorem 3 of Gu and Chen [2024] without justification, is explicitly clarified by (2.5). As 8 + 1, the rate in (2.5) becomes /Kfn. The inclusion of the three terms highlights the influence of K, which is unique federated systems. The 1 1/vnk term reflects the central limit theorem's convergence rate. The 1//2-8 VK term captures the problem's 's difficulty, which increases with the number of clients running local SGD in parallel. Lastly, n - K-1/2 -1/2 represents the benefit of synchronization and information aggregation across clients. Even though this term is asymptotically dominated by 11/2-88/K, this commands considerable finite sample effects as shown in Section 4.1.
2812)-1)
Often, due to privacy reasons, clients might be unwilling to share n -'' 0f at time-point n, which makes the application of Theorem 2.1 impossible. In such cases, one can simply use a corre- sponding Berre-Esseen bound for the end-term iterates, which we provide in the following.
Theorem 2.2. Under the assumptions of Theorem 2.1, it holds that
n 8/2
do(n2/2((y - - S
+
(2.6)
VK
where Z (O, with Σ. := n Var Σx= To (0 E.)).
K
Theorem 2.2 is proved in appendix Section B.2. When K x 1, the rate (2.6) is consistent with the well-established asymptotic theory of SGD Chung [1954], Sacks [1958], Fabian [1968] for the end- term iterates. Hereafter, till the end of this section, we will continue to analyze Y, further; exactly similar analysis also holds for Y,, which we do not present separately to maintain continuity.
5

---

2.2.1 Estimating Σn
In Theorem 2.1, the local SGD updates are scaled by the matrix En, which is not usually known or estimable. This matrix originates as the covariance of the sum of independent vectors us which acts
as a linearized version of the updates Y, = K- Ek=1 0 If = K KVar : then it can be shown that KΣ, + E for Σ = A SA as n - co. In general, we show the following theorem, proved in appendix Section C.
Theorem 2.3. Under the assumptions of Theorem 2.1, it holds that
E To-K-tpp -- 2 K k 9- and consequently, it holds that, with Z' ~ N(0, --),
(2.7)
dc(vn((,, 0k), & /K(n1/2-p + n 1
(2.8)
If K = O(1) Theorem 2.3 reduces to Lemma of Sheshukova et al. [2025].
tradc-off). Theorems 2.1 and 2.3 reveal a phase transition between classical central limit theory and the Berry-Esseen rate, which isn't clear from the condition K = o(22.-1) alone. This transition arises from compuration-communici communication trade-off Tsiatsis et al. [2005], Le Ny and Pappas [2013], Dieuleveut and Patel [2019], Ballotta al. [2020], which, in our context, reflects trade-off between the step-size parameter B and the number of clients K. Specifically, if K = o(n") for some S c S 1/2, the optimal 3o E (1/2, minimizing (2.8) is = =/44 Conversely, if K 2 n for c > 1/2. no 3 E (1/2, 1) ensures that /K
Remark 2.2 campuutaioo-commuiicai
0. This implies that when K X n for some regardless of the step-size, even though central limit theory still holds for 3 E (1/2 + c/2, 1). This phase transition highlights new theoretical insight into the hardness of local SGD K increases.
1/2, the Kolmogorov error remains significant,
An one pass estimation of Σ is discussed in Gu and Chen [2024]. Additionally, in appendix Section B.3, we point towards a new direction of multiplier bootstrap, leveraging our Berry-Esseen result, that does not require covariance estimation.
3 A time-uniform Gaussian coupling for the DFL updates
Section 2 quantifies the Gaussian approximation of the final local SCD updates Y,, with an error of order vn in terms of iterations. However, maintaining privacy in federated setting requires one to draw sharp inferences not only on the final output but on the entire local SGD trajectory, particularly for detecting model poisoning or adversarial attacks. From a theoretical standpoint, when the Assumption A.3 guarantees the existence of moments >> 4 (for example, when the data may be close to Gaussian). we should be able to derive sharper bounds on approximation errors, beyond the vn result in Section 2. Since central-limg theory and Berry- Kerry-Esseen estimates rely on fourth moments, we turn to classical strong approximation theory to exploit higher moments for precise bounds on the entire trajectory.
3.1 Motivation and Applications
time-uniform Gaussian coupling for the entire local SGD updates has strong practical moti- vations, particularly for anomaly detection in "Intemnet-o--Vhhicees" (IoV) Shalev-Shwartz et al. [2017], Ghimire and Rawat [2024], Zhu et al. [2024]. Assume that at some time point E [mi]. subset of clients Ko C [K] becomes malicious. This model poisoning can be mathematically de- scribed by a change in their local risk functions Fk, k Ko. which affects the distribution of the local SGD updates Y,. This perspective extends to other attacks, such as LIE (Little is Enough) or MITM (Man in the middle) Shen al. [2016], Blanchard et al. [2017], Yin et al. [2018]. Baruch et al. [2019], where an adversary injects noise or perturbs communication at time to, disrupting the distribution and trajectory of Y, for 2 to (Ding et al. [2024]). Methods offering explicit theoretical guarantees precisely detecting attack initiation are rare: most of the literature concentrates around robustness guarantees (error bounds, convergence rates) assuming certain adversarial profile or de- tection of malicious clients [Blanchard et al., 2017, Wang et al., 2020a, Qian et al., 2024], rather than provably devising poisoning alarm. Relatedly, Mapakshi al. [2025] observed that attacks starting in later rounds can be more damaging compared to those present from the start.

---

Assume that at some time point to E [n], a subset of clients Ko. C []] becomes malicious. This model poisoning can be mathematically described by a change their local risk functions FR, k Ko, which affects the distribution of the local SGD updates Y, To identify the time-point to sequentially, we examine CUSUM-type statistic R2 == max 8 Yyl,, widely used in change-point analysis. We expect Re to be large for > to if an attack has altered the mean behavior of the local SGD updates at to. The null distribution (i.e. when no attack takes place) of RG is usually mathematically intractable, hence posing a hindrance to performing valid inference. This necessitates a bootstrap procedure.
To identify the time-point to sequentially, we examine a CUSUM-type statistic R₂ == maxigast s|Y, Yg). widely used in change-point analysis. We expect R, be large for t to an attack has altered the mean behavior of the local SGD updates at to-
Suppose there exists Gaussian process G. such that time-uniform approximation holds:
max 15t5n
|0Y, Gel (v(n.
(3.1)
Let R/C = maxisese 19.- - {9. Then it follows that,
n 1/2 max RR Re(
1/2 max max istsn 18ast
1(sV, stip- - go)
(1), 1 10 - 9.)
Isten
{
< 2n 11/2 max
1/2
|tY, t0 Gel
= (1).
(3.2)
Equation (3.2) immediately suggests using Gaussian multiplier bootstrap leveraging G. with pre- cisely quantifiable approximation error. In particular, if =1=a((X) (X) denotes the (1 - a--th quantile
of random variable X, then for a suitable positive sequence {a, }.
P(R, > QR (R.)) + an for some t [n])
PP max RR R a.)) a,
(3.3)
as long as n a, G. The two major questions that remain, are
a, 2 c. We provide more details on these bootstrap algorithms in Appendix Section
Does such a G. exist? If yes, can we get a rate T such that Tn,K < vn?
Can we explicitly characterize its covariance structure, so as to enable bootstrap sampling?
The main results in Section 3.2 provide answers both the questions above.
3.2 Optimal coupling for local SGD
The following theorem, proved in Section D.I, establishes a Gaussian approximation echoing (3.1).
Theorem 3.1. For W == g )a),, gh Pk independently for k [K], let VK K km we W.). Suppose Assumption A.3 holds for a general 2 2. Then, under Assumptions A.I, A.2 and 2.1, (on a possibly richer probability space) there exists Zi,..., Zn NO0,KV)) such that with
Var(Z>
iddd
Yy = -1- + m2.K- 1/2 YG
001 0
(3.4)
it holds that,
max ISEE
Σ (Y, -0--0x (C----)1 = + or(n KKz 1/2 1/pr-11/1ogg log
(3.5)
We call the Gaussian approximation iterates (3.5) "Aggregated Gaussian approximation (Aggr--G) Note that Aggr-GA requires a complete sharing of the covariance structure to construct VK. which may affect privacy at inference-time However, it turns out that one can further refine Theorem 3.1 to provide another Gaussian approximation results that exactly mimics the local SGD updates in their use of local structure along with periodic sharing. We call this latter approximation by Client-GA. Theorem 3.2. Under the assumptions of Theorem 3.1, on a possibly richer probability space, for each k E [K], there exist Z 2/: i.idd. N (0, Var(W such that with
0 ((I - A)
G t-1 + M,, 05 = =(O....,
(3.6)
7

---

where M₁ == w, RRA ( ,...,,...,... 2
and Ct as in (2.2), it holds that
Σ (Y, -0x- -r Op(n1-8+ (n//))) o (logn)3/2) Yr - -K- (3.7) 18t5n
max
Note that for p == 2, the rates of Theorems 3.1 and 3.2 coincide. Theorem 2.2 is proved in Section D.2. In both the results, n² reflects the fundamental eπror of a generic uniform Gaussian ap- proximation for the local SGD updates Y,, and such, does not depend on K. The second error decreases with the number of clients, as an increasing number of clients enables local SGD updates to track a larger horizon, and the corresponding client-averaged Y, becomes more concentrated in their trajectory towards k% leading to sharper approximations.
Remark 3.1 (Computational differences between Aggr-GA and Client-GA). At each iteration t, Aggr-GA has a computational complexity of (dd)), since it involves generating one random sample followed by matrix-vector multiplication. In contrast, Client-GA has complexity of O(dd)) per iteration. Importantly, the structure of Client-GA naturally allows for parallel computation between synchronization steps, significantly reducing the computational burden while preserving periodic peer-to-peer communication.
Remark 3.2 (Difference with functional CLT). Li et al. [2022] proved a functional CLT for local SGD when the number of clients K is fixed. Although such a result can theoretically be extended to the general setting considered here, nevertheless than a functional CLT approximation. As a toy example, consider the vanilla SGD setting, i.e. local SGD with 1, and suppose K = 1. Suppose F(0) (0 - /2, and V f(, = O / &. In this setting, both Aggr-GA and Client- GA collapse to the same Gaussian approximation
approximations (3.5) and (3.7) are much sharper
r₁C (I AAYY Ziz Z₁ N(0, Var(E)), YO 0.
(3.8)
Here V2F(H) 1. On the other hand, the vanilla SGD iterates can also be seen as Y; p (1- (1- -Y-) n)) + MtC.. Therefore, it can be seen that Y; μ and Y, have ex- actly the same covariance structure, i.e. Cov(Y, y Cov(Y,, Y,); on the other hand, even in such simplified setting, an approximation by Brownian motion, such as that by functional CLT, cap- tures the covariance structure of the iterates (Y, - 11221 only in an asymptotic sense. The Gaussian approximation Y, in (3.8) is a particular example of Dovariance-matchinn duced by Bonnerjee et al. [2024]. By extension, same intuition holds for Aggr-GA and Client-GA as well. However, at this point, we note that the covariance- matcuiin approximations in Bonnerjee et al. [2024] were for short-range, univariate non-stationary process. On the other hand, in the local SGD setting, the polynomially decaying step-size introduces non-stationarity that can possibly be long-range dependent. Moreover, our result allows for multivariate parameters in a direct general- ization these aforementioned, covariance-matching approximations. We empirically validate this in Section 4.
approximations, intro-
Note that 1-18 indicates the fixed error for the local SGD updates with step-sizes n/e x x and in order to completely underpin the effect of the assumption of additional moments p > 2, an optimal choice of step-size must be given so that nt becomes negligible compared to the second error term involving the moment p. This choice is indicated in the following proposition.
Proposition 1. Grant the assumptions of Theorems 3.1 and 3.2, and consider the Gaussian approx- imations Y. and Y.S defined therein. Suppose K =(n") for some (0,
(i) If c < 2/p, then B 2 1/p + c/2 ensures maxigisn E:. (Y, - 0 -Y..)) o log
(ii) For general E (0, 1), choice of BB> 1 1- (1- 2 ensures that maxigiga Ei=I
0j -V-))=== = (1 +/ (logn)3/2).
Cases (i) and (ii) reveal trade-off between Aggr-GA and Client-GA. While Aggr-GA requires information sharing at each step. yielding better approximation, it demands a stricter choice of 3 since - + c > 1- c) 1 for all p > 2, 0. In contrast, Client-GA's local operation p 2
2p
supports K o(n) clients, aligning with Zhang et al. [2013), Gu and Chen [2023]. Both methods require known Hessians and local covariances, estimable efficiently via Gu and Chen [2024].
8

---

4 Simulation results
Here, we summarize the various empirical exercises accompany our theory in Sections and In particular, in Section 4.1, we discuss the Berry-Esseen error del dc(yn(Y, -0k) 2) for Z ~ NN0, E.) with varying choices of the number of iterations N, number of clients к and synchronization pa- rameter In Section 4.2, we numerically explore the cumpuuation-oommuiicee cussed in Section 2.2. Finally, in Section 4.3, explore the approximation error of Aggr-GA and Client-GA via Q-Q plots. Detailed explanations, and additional experiments, along with the model specifications, can be found in Appendix Section All codes are available in github.
trade-off dis-
4.1 Effect of n and K on the Berry-Esseer rate
As proxy of de, we consider de suupxe(o. - S 2) where
Z ~ N (0, I) for large enough 0. Figure shows how de varies with varying n, K, T when the step-size is kept fixed 77s 0.35 In particular, de decays with N for fixed K, and increases with K for fixed n. Additional simulations and further insights can be found in Appendix section F.1
470
Figure 1: Plot of de against and K for 1, and Settings 1(left), and 2(right).
4.2 Computation-comuuiitai trade-off
Here, we fix n E {100, 200, 300, 400, 500}, and |n"] for E f0.2, and numerically investigate the peoppaatiooncommmmiiatiiino trade-off hinted at in Remark 2.2. We run the local SCD algorithm with 5, and 1/: = 0.5t- for 3 E (0.85, 0.9, 0.95}. Clearly, de decays with for r 0.2, and increases with n for r 0.6, exemplifying our assertion about the computation- communication trade-off between K and B. Appendix Section F.2 contains additional details.
18
Figure 2: Plot of di against (n for 0.2 (left), and 0.6 (right). Here 7 0.
4.3 Performance of the time-uniform Gaussian approximations
In this section, we fix N 500, 20, and let {10, 25, 50), and compare the quantiles of the maximum partial sums of local SGD Un. Aggr-GA U- CA Client-GA U'Llient-o and approximation by Brownian motion: UK-CLT Clearly, Aggr-GA seems to be performing the best, as suggested by Theorems 3.1 and 3.2. Furthermore, U/!-CL consistently has the worst approximation. Additional details can be found in appendix Section F.6.

---

Figure 3: QQ-plots of U U (blue). U'LieettGa (green) and U.-CLLT (orange) against Un for = N = 500, = 20. Here K = 10(left), K = 25(middle), K 50(right). Rest of the FRand-eff model specifications are as in Section F.I.I.
Conclusion
Sharper theoretical results beyond the central limit theorem is extremely crucial perform valid and powerful statistical inference, yet such results have not previously appeared in the literature for local SGD and in general, decentralized federated learning. In this context, the best of our knowledge, this is the first work deriving Berry-Esseen bounds as well as sharp time-uniform Gaus- sian approximations over the local SGD trajectory. These results enable the development of valid and powerful statistical inference methods, including bootstrap procedures Fang et al. [2018], Fang [2019], Zhong al. [2023], which can be adapted to decentralized settings. The technical frame- work developed herein offers a pathway to sharper results in many other related settings including multi-agent systems and transfer learning Duan and Wang [2023], Pan et al. [2023], Knight and Duan [2023], Lin and Reimherr [2024]. It is also crucial to make explicit the effect of synchronization in the derived rates, which can reflect more trade-off's and constitute a suitable future work.
Acknowledgment
The authors would like to thank the reviewers, the area chair and the senior area chair for their constructive feedbacks that helped improve the paper significantly. SK and WBW thank NSF DMS grant 2124222 and NSF DMS grant 2311249 respectively for supporting their research.
References
D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. Qsgd: Communication-effiiee sgd via gradient guantization and encoding. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.
A. Anastasiou, K. Balasubramanian, and M. A. Erdogdu. Normal approximation for stochastic gradient descent via non-asymptotic rates of martingale clt. In Conference on Learning Theory, pages 115-137. PMLR, 2019.
Bach. Self-concordant analysis for logistic regression. Electron. J. Stat., 4:384-414, 2010. ISSN 1935-7524. doi: 10.1 12..121400 4/04--FFSS21 URI. https://doi. org 12149999-1-1.
L. Ballotta, L. Schenato, and L. Carlone. Computation-communicaaii trade-offs and sensor selec- tion in real-time estimation for processing networks. IEEE Transactions on Nenwork Science and Engineering, 7(4):2952-2966 2020.
G. Baruch, M. Baruch, and Goldberg. A little is enough: Circumventing defenses for distributed learning. In H. M. Wallach, H. Larochelle, A. Beygelzimer, F, d' Alché-Buc. E. B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancou- ver, BC, Canada, pages 8632-8642, 2019. URL https: http://poooeee...nneeee nwwrinurrp.... www.eeis..cppppppeeeee cc/paper/ 2019 httes///ceeoLL1100eeeeeeooooeeee Abstract html.
I. Berkes, W. Liu, and W. B. Wu. Koml6s-Major-Tusnáde approximation under dependence. Ann. Probah., 4212))794-817, 2014. ISSN 0091-1798.
doi: 10.1214/13-AO8800 URL http::ttt//e/ //dx::
doi, org /10. 11t.111111111PSe1111
10

---

P. Blanchard, E. M. E. Mhamdi, R. Guerraoui, and J. Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Guyon, U. von Luxburg, S. Bengio. H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Pro- cessing Systems 30: Annual Conference on Neural Information Processing Systems 2017, De- cember 4-9, 2017, Long Beach, CA, USA, pages 119-129, 2017. URL https:s///proo neurips. cc/ wttpcp/pppppp///////////p http///////haah/////// wtwaaa/0000000101199999966666660
html.
Bonnerjee, Karmakar, and W. B. Wu. Gaussian approximation for nonstationary time series with optimal rate and explicit construction. Ann. Statist., (2(5):2293-2311,, 2024. ISSN (0990- 5364,2168-8988 doi: 10. 22214424-a022436. URL https //toi//d//////o org/ 121.1111//444-22253
L. Bottou, E. Curtis, and J. Nocedal. Optimization methods large-scale machine learning. SIAM Rev. 60(2):223-311 2018. ISSN 0036- 1466-144,,199-2200 doi: 10.1137/16M1000177 URL https://doi. 2tg/10.1// 1117/16M10801777
Chaturapruek, J. C. Duchi, and C. Ré. Asynchronous stochastic convex optimization: the noise is in the noise and SGD don't care. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Confer- on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 1531-1539, 2015. URL bttttss:/pproeeeeeeee hashh//ccc...aaa1137777744411122
nwwr htlppp...pppppppp 22/1// Abstractt.rrttrt.. html.
X. Chen, J. D. Lee, X. T. Tong, and Y. Zhang. Statistical inference for model parameters in stochastic gradient descent. Ann. (Bu))s,,,4(()2251-222 2020. ISSN 0090-5364,2166 11164,216888966 doi: 10.1214/ URL /
V. Chernozhukov, D. Chetverikov, and K. Kato. Detailed proof of nazarov's inequality. arXiv preprint arXiv:1711. 2017.
K. L. Chung. On a stochastic approximation method. Ann. Math. Statistics, 25:463 1954. ISSN 0003-4851. doi: 10. 00.2214/om//11777255666 URL ftttp:://doi.org//1/// 1177728716.
L. Devroye, A. Mehrabian, and T. Reddad. The total variation distance between high-dimensional gaussians with the same mean. arXiv preprint 1xXiv:811000869) 2018.
A. Dieuleveut and K. K. Patel. Communication trade-off's for local-sgd with large step size. Ad- vances in Neural Information Processing Systems, 32, 2019.
A. Dieuleveut, A. Durmus, and F. Bach. Bridging the gap between constant step size stochastic gra- dient descent and Markov chains. Ann. Statist,, 48(3): (1(33:1:3444 1418-14888888 2020. ISSN 0090-5364,2168- 8966. doi: 12211411-AAS1888
URL https: // doi org/ 10. 11.11.....1 1011/12-1111//1// A0S1850.
Z. Ding, W. Wang, X. Li, X. Wang, G. Jeon. J. Zhao, and C. Mu. Identifying alternately poisoning attacks federated learning online using trajectory anomaly detection method. Scientific Reports, 14(1):20269, 2024.
Y. Duan and K. Wang. Adaptive and robust multi-task learning. Ann. Statist., 51(5):2015-203) 2023. ISSN 0090-5364.216888800 doi: 10.1214/33-aos3119 URL https: http::::/ddoorree/ 2214/23-a0s2319.
V. Fabian. On asymptotic normality in stochastic approximatioo..o Ann. Math. Statist., 39:1327-1334 1968. ISSN 0003-4851. doi: 10.12 4/o21////////7777995333 URL https://doi. http:://doooooro////// org/10 11144/ aoms/117769825..
Y. Fang. Scalable statistical inference for averaged implicit stochastic gradient descent. Scand. Stat., 46(4):987-1002, 2019, ISSN 0303-6898, 1467-9469. 1497-999,,,467994699 doi: 10. 12378. URL
https://doi.ce wtt/ooi.oogg/1... http////....///sss..oooo 12378.
Y. Fang, J. Xu, a.d Yang. Online bootstrap confidence intervals for the stochastic gradient descent estimator. Mach. Learn. Res., 19:Paper No. 78, 21, 2018. ISSN 1532-4435,1533-799
E. Gabrielli, Pica, and G. Tolomei. survey on decentralized federated learning. arXiv preprint arXiv:2308. 04604, 2023,

---

F. Gettse and A. Y. Zaïtsev. The accuracy of approximation in the multidimensional invariance principle for sums of independent identically distributed random vectors with finite moments. Zap. Nauchn. Sem. S.PPeterburg Oudel. Mat. Inst. Steklov. (POMI), 368:110-121, 283-284, 2009. ISSN 0373-2703. doi: 10.10077111958-000-999555 URI. httthttp::/dde orgg 1007/ 110958-010-9930 9935--..
B. Ghimire and D. B. Rawat. A communication-fficcie machine learning framework for the in- ternet of vehicles. IEEE Transactions on Cognitive Communications and Networking, pages 1-1, 2024. doi: 200.0/TCCN.2244338877777
M. R. Glasgow, H. Yuan, and T. Ma. Sharp bounds for federated averaging (local SGD) and continu- ous perspective. G. Camps- Camps-Valls, F. J. R. Ruiz, and I. Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, vol- ume 151 of Proceedings of Machine Learning Research, pages 9050-9090. PMLR, 2022. URL https://proceedingg mlr. ppess/v111 /atass//11//glasgo/222 gltg///2assaoaaaa. 1tt.as.oo22a.m..... html.
Teor. Veroyamn Primen., 53(1):100-123, 2008. ISSN 0040- F. Götze and A. Y. Zaitsev. Bounds for the rate of strong approximation in the multidimen- sional invariance principle.
361X,2305-3151. doi: 10.1 101137/004053300798300
URL https: //doi. ott.loorg/.100011 1137/
$0040586X9798350X.
Gu and S. X. Chen. Distributed statistical inference under heterogeneity, J. Mach. Learn. Res., 24:Paper No. 387, 56, 2023. ISSN 1532-4433, 14,33447993337998
J. Gu and S. X. Chen. Statistical inference for decentralized federated learning, Ann. Statist., 52 (6):2931-2955, 2024. ISSN 0090-5364,2168-888 //doi. 10. 1214/24-a0s2440
doi: 10.1214/24-a024552 URL https:
F. Haddadpour, M. Kamani, and M. Mahdavi. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems (NeurIPS), pages 11082-11094, 2019.
C. He, M. Annavaram, and S. Avestimehr, Central server free federated learning over single-sided trust social networks. arXiv preprint arXiv:1910.04956. 2019.
N. Ivkin, D. Rothchild, E. Ullah, V. Braverman, I. Stoica, and R. Arora. Communication-effiiiennn distributed SGD with sketching. In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché- Buc, E. B. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 13144-13154, 2019. URL https: tttttt:://ppocceeinne neur soarips.coo cc/cc//////// htc/paper/2000 /ataa///50000656664333332323 2a00:0044440.0000111222200aaaaaa html.
Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, al. Advances and open problems in federated learning. Founda- tions and trends@ in machine learning, 14(1-2):1-210, 2021.
S. P. Karimireddy, S. Kale, M. Mohri, S. J. Reddi, S. U. Stich, and A. T. Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning (ICML), pages 5132-5143. PMLR, 2020.
S. Karmakar and W. B. Wu. Optimal Gaussian approximation for multiple time series. Statist. Sinica, 30(3):1399-1411 1417, 2020. ISSN 1017-0405, 19000400,,199999.. 9599996-7777. doi: 10.5705//..22011..003. URL https: /ttp:////oooooo/./////////:o/o/t hatg://..570///e/ 5705/ss. 202027.022200 0300.
S. Karmakar, S. Richter, and W. B. Wu. Simultaneous inference for time-varying models. Econo- metrics, 227(2):408-225 2022. ISSN 0304-407,,1882-6668 doi: 10. j0010016./ecoommm.221...000 002. URL https: org/10. httg//0.1166.. 1016/j jejjjnoono. 00.1.03.00
A. Khaled, K. Mishchenko, and P. Richtárik. Tighter theory for local sgd on identical and heteroge- neous data. In International conference on artificial intelligence and statistics, pages 4519-4529. PMLR, 2020.
H.-W. Kim, J. Kim, and M. Bennis. Blockchained on-device federated learning. IEEE Communica- tions Letters, 1279 2020.
12

---

P. Knight and R. Duan. Multi-task learning with summary statistics. In A. Oh, Globerson, Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Informa- tion Processing Systems 2023, NeurlPS 2023, New Orleans, IA, USA, December 10 wwt.ff/lappeee/////e.
T. Naumann,
16. 2023, 2023. URL http://papers: wwws.cc/pppi.eeeeeo wwtp:pcrpppppppeeeeeeeeee 9924011186577ddee112225570777772 - Awstract-Coottoee Coneeeeeooeeeeeceeee.. html..
A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. U. Stich. A unified theory of decen- tralized SGD with changing topology and local updates. In Proceedings of the 37th Interna- tional Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 5381-5393, PMLR, 2020. URL http://proceedding mlr
html.
Komlós, Major, and G. Tusnády. An approximation of partial sums of independent RV's and the sample DF. I. Z. Wahhschheinlichheessteeerrr und Verw. Gebiete, 32:111-131 1975, doi: N0.10077BF00533093, URL http:::/t/ooo.rrg////// httpap////ool.rrg//0..0/0///0/90 /00//000000//000330333
A. Lalitha, O. C. Kiline. T. Javidi, and F. Koushanfar. Peer-to-peer federated learning on graphs. arXiv preprint 1901 2019.
G. Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(1):365 2012.
J. Le Ny and G. J. Pappas. Differentially private filtering. IEEE Transactions on Automatic Control, 59(2)3441354, 2013.
Li, Z. Lou, S. Richter, and W.-B. Wu. The stochastic gradient descent from a nonlinear time series perspective, preprint, 2024.
T. Li, A. K. Sahu, A. Talwalkar, and V. Smith. Federated optimization heterogeneous networks. In Proceedings of Machine Learning and Systems, volume 2, pages 429 450, 2020.
X. Li, W. Yang, S. Wang, and Z. Zhang. Communication-cfficiii local decentralized sgd methods. arXiv preprint arXiv: 19/0.09//200 2019.
X. Li, Liang, X. Chang, and Z. Zhang. Statistical estimation and online inference via local sgd. In Proceedings of the 35th Conference on Learning Theory (COLT), volume 178, pages 1613-1661. PMLR, 2022.
X. Lian, C. Zhang, H. Zhang. C. Hsich, W. Zhang, and J. Liu. Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent. In I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vish- wanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30: An- nual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5330-5340, 2017. URL http:tttts//ppocceeiiiiiee 2017
neurips htcppps.ccpppppe capprr/ Abbr:atcrr111eeeeeeeatttttttttt Abstract html.
H. Lin and M. Reimherr. Smoothness adaptive hypothesis transfer learning. In Forty-first Interna- tional Conference Machine Learning, ICML 2024, Vienna, Austria, July 21-27. 2024. Open- Review.net, 2024. URL https: httpp:://penreeeee //ppnrevieneeeieeee net//oorum/id<<oous[115::
Y. Lin, S. Han, H. Mao, Y. Wang, and W. J. Dally. Don't use large mini-batches, use local sgd. In International Conference on Learning Representations (ICLR), 2018
W. Liu and W. B. Wu. Simultaneous nonparametric inference of time series. Ann. Statist., 38 (4):2388-2421, 2010. ISSN (090-5364,218-89999 doi: AOSS99, URL https: //doi.org/ A25700
R. Mapakshi, Akther, and M. Stamp. Temporal Analysis of Adversarial Attacks in Federated Learning. In Machine Learning, Deep Learning and AI for Cybersecurity, pages 359-392. Springer, 2025. doi: 10. 10.10777978-3--31-8815-77777 URL https: http:://axxvvve. /wwpai..oor//as//5/0..11. 11054.
13

---

H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. Arcas. Communication cfffunicationneffccientt efficient learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
Mies and Steland. Sequential gaussian approximation for nonstationary time series in high dimensions. Bernoulli, 29(4):114433140 2023.
W. Mou, A. Pananjady, M. J. Wainwright, and P. Bartlett. Optimal and instance-dependent guar- antees for Markovian linear stochastic approximation. Math. Stat. Learn., 7(1-2)411153, 2024. ISSN 2520-2316,2520-223
doi: 10.4171/msl/44, URL htthtt:s://ddo http:///oooooroo////////// wttp./.....././m/////4/4.. 4171/ms1/44
E. Moulines and F. Bach. Non-asymptotic analysis of stochastic approximation algorithms for ma- chine learning. Advances in neural information processing systems, 24, 2011.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574-1609, 19t
2009.
Q. Pan, R. Wu, T. Liu, T. Zhang, Y. Zhu, and W. Wang. Fedgkd: Unleashing the power of collabo- ration in federated graph neural networks. arXiv preprint ar Xixx:2309009517.. 2023.
I. Pinelis. Optimum bounds for the distributions of martingales in Banach spaces. Ann. Probab., 22 (4):1679-1706, 1994. ISSN 0091-1798,2168-8900 8 URL http://links jstoo org/sici? sici=0091- 1798 (199410) 22: : 0 2022-22oriiginn
B. T. Polyak and A. B. Juditsky. Accelcration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838-88) 3--385 1992.
C. Qian, M. Wang. H. Ren, and C. Zou. MYMI: Byzantine Machine Identification with False Discov- ery Rate Control. In R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning (ICML 2024), volume 235 of Proceedings of Machine Learning Research, pages 41357-41382. PMLR, 21-27 Jul 2024. URL https:: h/tppes:///ccceinngs.... mlr wwr.smrrrs.prr.ll..mmmmmmmmmmeee press/ /ttp///3////n//// httmm1122.......
T. Qin, S. R. Etesami, and C. A. Uribe. Communication decentralized local sgd over undi- rected networks. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 3361- 3366, 2021. doi: 10. D0.11099CDC4444422222...99999
D. Ruppert. Efficient estimations from a slowly convergent robbins-monro process. Technical Re- port, 1988.
J. Sacks. Asymptotic distribution of stochastic approximation procedures. Ann. Math. Statist., 29: 373-405, 1958. ISSN 0003-4851. doi: 10. 4/ommm/11777066111 URL https://doi. org/ 10. 1214/2ams/1177066665
A. Sakhanenko. Rate of convergence in the invariance principle for variables with exponential moments that are not identically distributed. In Limit theorems for sums of random variables, volume of Trudy Inst. Mat., pages 4 49. "Nauka" Sibirsk. Otdel., Novosibirsk, 1984.
A. I. Sakhanenko. On the accuracy of normal approximation in the invariance principle. Trudy Inst. Mat. (Novosibirsk), 13:40-66 66, 197, 1989. ISSN 0208-0060.
A. I. Sakhanenko. Estimates in the invariance principle in terms of truncated power moments. Sibirsk. Mat. Zh., 4766)) 2006. ISSN 0037-4474. doi: 10.1007/s1 1202-006 000-0000-11-11 URL http: //tp::///xx.// http:/xxxxxx.oooo 1ttp://0000000111100000000001000
S. Samsonov. E. Moulines, Q.-M. Shao, Z.-S. Zhang, and Naumov. Gaussian approximation and multiplier bootstrap for polyak-ruppert averaged linear stochastic approximation with applications to td learning. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Shalev-Shwartz, S. Shammah, and Shashua. On a formal model of safe and scalable self- 2017.
driving cars. arXiv preprint
14

---

Q.-.. Shao and Z.-S. Zhang. Berry- Berry-Esseen bounds for multivariate nonlinear statistics with appli- cations to M-estimators and stochastic gradient descent algorithms. Bernouli.. 28(3):1588-1576 2022. ISSN 1350-7266,,5773-9755 3150/21-bej1336.
doi: 10.3150/21-bee -hej1336. URL https://ddoo org/10.
S. Shen, S. Tople, and P. Saxena. Auror: defending against poisoning attacks in collaborative deep learning systems. In S. Schwab, W. K. Robertson, and D. Balzarotti, editors, Proceedings of the 32nd Annual Conference on Computer Security Applications, ACSAC 2016, Los Angeles, CA, USA, December 5-9, 2016, pages 508- 519. ACM, 2016. http:/// acm. cfm?id=2991125
M. Sheshukova, S. Samsonov, D. Belomestny, E. Moulines, Q.-M. Shao. Z.-S. Zhang, and A. Nau- mov. Gaussian approximation and multiplier bootstrap for stochastic gradient descent. arXiv preprint arXiv:2502.067199 2025.
A. Singh. A. Bhowmick, and N. Chakraborty. Privacy-preserte decentralized federated learning: Algorithms, challenges, and opportunities. IEEE Transactions on Artificial Intelligence, 2023.
S. U. Stich. Local SGD converges fast and communicates little. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL
V. Tsiatsis, R. Kumar, and M. B. Srivastava. Computation hierarchy for in-network processing. Mobile Networks and Applications, 10:505-518, 2005.
H. Wang, K. Sreenivasan, S. Rajput, H. Vishwakarma, S. Agarwal, J. yong Sohn, K. Lee, and D. S. Papailiopoulos. Attack of the tails: Yes, you really can backdoor federated learning. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020), 2020a.
J. Wang and G. Joshi. Cooperative SGD: unified framework for the design and analysis of local- update SGD algorithms. J. Mach. Learn. Res., 22:Paper No. 213, 50, 2021. ISSN 1532-4435,1533- 7928.
J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in Neural Information Processing Systems (NeurIPS), 33:7611-7700 2020b.
I. Waudby-Smith, D. Arbour, R. Sinha. E. H. Kennedy, and A. Ramdas. Time-uniform central limit theory and asymptotic confidence sequences. Ann. Statist., 52(6):2613-2640 2024. ISSN 0090- 3864,2168-8964 doi: 10. 2/2444/2242200 URL https: //doi. http:///to..o//////////
org/10. 10. 2214/24-aas24000
Z. Wei, W. Zhu, and W. B. Wu. Weighted averaged stochastic gradient descent: Asymptotic normal- ity and optimality. arXiv preprint arXiv:2307.069155 2023.
B. E. Woodworth, K. K. Patel, and N. Srebro. Minibatch vs local SGD for heteroge- neous distributed learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and
H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Con-
ference on Neural Information Processing Systems 2020, NeurIPS 2020. December 6- 12. 2020, virtual, 2020a. URL https: p/rrcee//procceinggss parrocedinggsnneuip... neurips.co. ctapps.cc/pappae wttpcc/ppeee/////aaaaeeee (10.///6600044111f0faa7777688888
cobstract.htmm
B. F. Woodworth, K. K. Patel, S. U. Stich, 7. Dai, B. Bullins, H. B. McMahan, O. Shamir, and N. Srebro. local SGD better than minibatch sgd? In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 10334-10343. PMLR, 2020b. URL http: htmm..
//proceedings. mlr
W. Wu, G. Li. Wei, and A. Rinaldo. Statistical inference for temporal difference learning with linear function approximation. arXiv preprint arXiv:2410.16100 2024.
W. B. Wu and Z. Zhao. Inference of trends in time series. J. R. Staf. Soc. Ser. B Stat. Methodol, 69 (3):391-410,, 2007. ISSN 1369-7412, 1467,999988 doi: 10. 10.1 1..1111jj.447-98666 2007.00594 URI. https: //ops:///doii org/10..r 1111/j 1467-98868 2007. 00594.
15

---

URL C. Xie, O. Koyejo, I. Gupta, and C. Hegde. Asynchronous federated optimization. In Advances in Neural Information Processing Systems, volume 33, pages 99359-19369, 2020.
D. Yin, Y. Chen, K. Ramchandran, and L. Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. J. G. Dy and A. Krause, editors, Proceedings of the 35th International Conference Machine Learning. ICML 2018, Stockholmsmmsssan Stockholm, Sweden, July 10- 15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 5636-5645. PMLR, 2018. URL http://proceedings. mlr. wwwps//00/ 1 18a. html.
I. Yuan, Z. Wang. I.. Sun, P. S. Yu, and C. G. Brinton. Decentralized federated learning: A survey and perspective. IEEE Internet of Things Journal, 2024.
Y. Zhang, J. C. Duchi, and M. J. Wainwright. Communication--ffiiieenn algorithms for statistical optimization. J. Mach. Learn. Res., 14:3321-3363, 2013. ISSN 3332-4435,1533-799
Y. Zhong, T. Kuffner, and S. Lahiri. Online bootstrap inference with nonconvex stochastic gradient descent estimator. arXiv preprint arXiv:2306.02200. 2023.
M. Zhu, W. Ning, Q. Qi. J. Wang, Z. Zhuang. H. Sun, J. Huang. and J. Liao. FLUK: pro- tecting federated learning against malicious clients for internet of vehicles. In J. Carretero, S. Shende, J. Gareía-Blas, Brandic, K. Olcoz, and M. Schreiber, editors, Euro-Par 2024: Par- allel Processing 30th European Conference Parallel and Distributed Processing, Madrid, Spain, August 26-30, 2024, Proceedings, Part I1, volume 14802 of Lecture Notes in Com- puter Science, pages 454-469. Springer, 2024. doi: 1_31.
https://doi. org/10 0t////1.1107/978860 1/1/9/9888-----98711
W. Zhu, X. Chen, and W. B. Wu. Online covariance matrix estimation in stochastic gradient descent. J. Amer. Statist. Assoc., 118(541):393-404 2023. ISSN 1559, doi: 10.1080/ 21621199.2021.11333988 URL https: http::////ooo.oo1.11/0100///// 1000000.010000100111001 2021 1933498.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the main claims of the paper accurately reflected in both the abstract and introduction. The paper proposes two sharp Gaussian approximation theorems for local SGD, which go beyond CLT in facilitating statistical inference. All claims theo- retically proven and empirically validated throughout the work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: All the theoretical assumptions about the local SGD settings, are explicitly mentioned and discussed length Sections and A. It also points out fundamental restrictions on the number of clients for theoretical validity of the local SGD algorithm. These discussions appear in the theoretical analysis sections and remarks following theo- rems. We also remark some limitations and possible extensions in our conclusion.
16

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e-g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All the assumptions can be found in the theorem statements, and are discussed in main paper as well as appendix Section All the proofs can be found in Section B-E.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The complete model specifications along with parameters, are provided in Section F.
Guidelines:
17

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language modell, releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the codes to reproduce the results can be found anonymously in github as well in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / ctaips.cc/ublicc//ee http///iee///eee/ Cateees//oeSSbbbeieeeee cimmisssionn wwwpeemiissiiooPoooii.io for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
18

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental details are provided in Sections 4 and F. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper does not include hypothesis testing or statistical significance anal- ysis, and error bars are not focus of the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report 1-sigma error bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification:
The experiments are lightweight and run quickly on modern laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
19

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: ptttps:/nneurpstt wttpuurips.ccpppplppaeeee heabllic/Ethisshiddeee
Answer: [Yes]
Justification: The research follows all ethical guidelines. No human data ethically sensi- tive content is involved.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper mentions certain societal motivations, such privacy protec- tion and computational efficiency while maintaining statistical validity, the introduction. Since work is theoretical in nature, do not anticipate any negative impacts, and as such the paper does not include a dedicated speculative discussion of broader societal impacts in separate section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
20

---

Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (c.g.. pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper does not release any models datasets with high risk of misuse. All released components are synthetic and pose no privacy or safety risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e-g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All baseline methods are standard, and citations to prior work are provided with proper attribution and licensing notices.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperawi thcode com/dataset. has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification:
The paper introduces novel Gaussian approximation results, which are the- oretically validated with extensive proofs. All the accompanying empirical evidence is documented and released via GitHub repository in anonymized form. Hyperparameters, dependencies, and usage instructions are all included.
Guidelines:
The answer NA means that the paper does not release new assets.
21

---

Researchers should communicate the details of the dataset/codeemmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [No]
Justification: The paper does not involve crowdsourcing or human subject research.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to NeurIPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [No]
Justification: No human subjects are involved in this research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [No]
Justification: No large language models (LLMMs) were used to produce, analyze, verify the scientific content of this paper. All methods and results are original and independently verified using rigorous mathematical analysis and custom code.
Guidelines:
22

---

The answer NA means that the core method development in this research does not involve LLMs as any important. original, ntn-standard components.
Please refer to our LLM policy (https / /ttp://eeerpppeeeeeeeeeeeee / /LMM) for what should or should not be described.
23

---

A Technical assumptions and Some comments on Section 2
A.1 Technical Assumptions
For the validity of our theoretical results, we require some mild regularity conditions on the loss functions as well as the noise level of each client. We remark, that the following assumptions have appeared extensively in the theoretical analysis of iterative convex optimization algorithms, and here, are merely adapted to the federated learning setting.
Assumption A.1 (Strong convexity). There exists μ > such that for each i E [K].
(V))(()) ()) 0²) 2 0 - 012, 0,0' E IR
Assumption of strong convexity is common in the analysis of SGD iterates, appearing in Ruppert [1988), Polyak and Juditsky [1992], Bottou et al. [2018], Chen et [2020]. and as such, Assumption A. adapts this condition the decentralized setting.
Assumption A.2. (Stochastic Lipschitzness of noisy gradients) There exists > such that for each k E [K].
Ep, [x fa g s L|0 81,, 0,0' CR..
Assumption A.2 combines the L-smoothness condition on the risk functions Fk. with a stochastic Lipschitz condition on the gradient noise vectors g (0, <+) FF) (+,,
Assumption A.3. (Control on noisy gradients) The functions (0, assumed be continuously differentiable with respect 0 for any fixed &. Moreover, assume that [ EE E[ g& (0, [P] Do for some p 2 2.
Assumption A.3 ensures that Newton-Leibnitz's integration rule holds and consequently, K Ek=n wigk (0k, <tt constitutes martingale difference sequence adapted to the filtration oEE,
1), where E, , 5 Moreover, Assumptions A.2 and A.3 jointly imply that there exists constant LQ such that for all 0 E gd
mAX KEK
V (0)
V2F(0)) - 0k)l < TQQ 10 0x
(A.1)
See Lemma 5 of Sheshukova al. [2025]. The assumptions A.2 and A.3 fairly ubiquitous in the stochastic optimization literature Zhu et al. [2023], Wei et al. [2023], Li et al. [2024]. In particular, assumption A.2 is much weaker than the corresponding Assumption A2(p) ((i) in Sheshukova et al. [2025].
A.2 Is strong-convexity Assumption A.1 necessary?
is important that Assumption A. fails to hold in certain M-estimation problems including logistic regression Bach [2010]. Gu and Chen [2024] addressed this issue by invoking a weaker local Assumption A.4 (Local strong concordance). There exists μ² O such that V2F((T 2 μt¹ Moreover, there exists constant C' O, and compact set ④ C Rd. such that for all 0, O2 4, holds that
assumption, also known as the "local concordance" condition.
10"" (w)l S S - 0zl (()), where yp u F (01 + u (02 - .E..
requires projected local SGD updates θ = Ma (0,-1- - -G C,, instead of (2.2), where M4 denotes the projection operator on the set compact Ø. The key difference in the treatment of Assumption A.4 compared to that of Assumption A. lies in the analysis of the term 10 - F)FF()) for some small enough r) > 0. In particular, a recurring theme of proofs show that
In view of Assumption A.4, for theoretical validity of our results,
| 0 - 7/ F())2 < (1 nc) 0 - 1 for some c > 0, Rdd
(A.2)
We highlight the different arguments leading up-to (A.2), leveraging Assumptions and A.4 re- spectively.
24

---

A.2.1 Proof of (A.2) via Assumptions A.1 and A.2
Note that
2n 17000000-0000000-0-0000000000000 10-0k - - -VF00 -00
5 + + 0x
(A.3)
and hence, (A.2) is inferred by choosing be small enough. In particular, since work with
decaying step size x t-P, it follows that 2nd + of I, S TJC for some c > 0 and all sufficiently large E N.
A.2.2 Proof of (A.2) via Assumptions A.4, A.2 and |a|| - R
Fix 0 E Rd, and choose d(u)= F(O + u(O kk)), [0, 1]. Note that s² w010 10- 0% 12. From Assumption A.4, one directly has
("(n) 2 < exp(( -C10 0k(u),
and therefore, recalling |x|| 2 R
(0 0k) VF =6' (1) ) d'(0)
2 0 0k
exp(- - (
1 exp(-C10 0%
= 0Kl
C|0 07
21¹ C exp( Coopp(-R)6-- R) 0x1²
(A.4)
which immediately can be applied to (A.3) to deduce (A.2).
In view of the analysis in Sections A.2.1 and A.2.2 coming to the conclusion, for the sake of simplicity, our subsequent theoretical findings are stated and proved using Assumption A.1 only. We remark that accompanying result invoking Assumption A.4 and the projected local SGD updates can easily be obtained via minor modifications of our arguments following Section A.2.2. For more detailed discussion the implications of Assumption A.4, we refer the interested readers to Assumption 3.4 and the associated remark in Gu and Chen [2024].
A.3
comment on step-size
Our choice of the step-size is motivated from the extensive literature of asymptotics of various stochastic approximation algorithm. In particular, it is well-known that SGD with a constant step- size is asymptotically biased Dieuleveut et al. [2020], Li et al. [2024], Glasgow et al. [2022], whereas central limit theory based on polynomially decaying schedule 77, x t sive literature for different algorithms. In practice, often combination of the two kinds of step-size used, where constant-step size algorithm provides a warm start, and after discarding initial few iterates pre-specified by the fixed burn-in period ko. local SGD be run with the polynomially decaying step-size to ensure appropriate convergence. This is tantamount to the step-size choice We (o(t ko) 8 ko, which also covered by our theory.
(1/2, 1) has an exten-
B Proof of Theorems 2.1 and 2.2
In this section we rigorously derive the Berry-Esseen bounds on Y, and Y,, as stated in Theorems 2.1 and 2.2 respectively. Similar to the simpler analysis for stochastic gradient descent in Samsonov et al. [2024]. we aim to leverage Theorem 2.1 of Shao and Zhang [2022]. However, the regular synchronization step, as well as the general connection matrix C, induces some significant non- triviality in the problem, requiring, in particular, careful analysis of the difference between client- wise estimates and the aggregated estimate. Before we delve deeper into the mathematical details, we summarize the road-map to prove Theorem 2.1 below.
Section 1. we decompose the local SGD updates into linear component and the remainder terms.
25

---

In Section B.1.2, we echo the Lindeberg method, and define a coupling for the remainder terms. particular, our choice of the coupling novel, and rooted into the uniqueness of the decentralized setting.
Finally, in Sections B.1.3-B.1.7, we control the different terms arising of the application of the abstract Theorem 2.1 of Shao and Zhang [2022] to the steps above. We remark that this is where our treatment diverges from the preceding works proving Berry- stochastic approximation framework. To accommodate an increasing number of clients K as well as control the error of the each local client-level iterates, we derive and apply the Auxiliary results 4-8.
in
The proof for Theorem 2.2 will follow similar structure.
B.1 Proof of Theorem 2.1
B.1.1 Linearization
Noting that Y, = K-1 matter E, or & E,, it is easy to observe
Y = Y,
wh Va LE [n], Yo - K-
05
(B.1)
k=1
Write (B.1) as follows:
Y 0k =Ya-1
0x VF((-) + 17: Σ we (VF((()))) V.L(())))) me
(0 (t)
k=1
=(1 (1-
02x + n (A(ri-1 0x) VF(Y-1))
K
K + Σ k=
+ M
wk - VELLO (VF((())))
WkSk 10
(B.2)
where gu (0(0 = V/2(0) E) denote the gradient noise. Denote A = II -- (1 A).
At 7 with A = V22(0)), and define Q. 7ls Σラ= Al. Recursively, (B.2) be simplified to
Ye 8 -Yo 0k) + Σ A (A((s-1--8) 0k) VF(Y,-1))+
w (VF - VEL(O + Σ
Wriyk (0 (0
wk
1=1
k=1
(B.3)
which immediately yields,
Yn 0x =n in-nnoQQul 0k) + n- " QaN n ~ "
n
Q (AA(Y-1 - 07) vF((,-1))
K
K
wk (V.
V (0* +
wk (9)
(x +.1
k=1
(B.4)
where we define that N₁ = Ek wA Wh. with W = (0,, (t) Let H =n 11/2 Σ レ Q. and let Er ||HH" Then, (B.4) can be re-wtitten
v 1/2 0k) - W Dj +
D2 + Dg + D4:
(B.5)
26

---

where
1
1 1/2 Q2NN
W 2n 1-1/2
Σ
Uga where u, /n
(B.6)
1 I
D1 =
1-11/2001 0k)
(B.7)
Vinioo
D2
1/11/2 1/2
(2)
(B.8)
VI. n
K
D3
1/2
Σ
Q
wx (V (1
(B.9)
VII n
#=1
k=1
n2 D4
1/2
Q
Σ
Wk 1,= 9b g0 {x,
(B.10)
B.1.2 Definition of the Lindeberg Coupling
Note that
Dzl2 SC L2VI. 1/11/21 Vn
n
Y 1--122
(B.11)
SC SC 12 1/11/2
K
Y - 8 11
(B.12)
Vnk
s=1
k=1
b2VL =0
1/2 En
F Σ
1. (I - J) == A3.
(B.13)
vnk
In the above series of inequalities, (B.11) follows from < b2 max, 1Q,/ < C, and Assumption A.2; (B.12) is trivial consequence of Cauchy-Schward Schwarz inequality. Additionally, define A = D112 for 1 = 1,2,4. Let E, = (fl...... <k), and for each E [n:) let us denote
E
1 *
E.
E = (c)' ..'.k
t=i,
where &t &t L.d. Pk, k E [K], [n]. For each [n]. define the coupled DFL iterates
O,,(1) (0.-1,)) nc Gt,))) 0o, Oo.
(B.14)
where G1 K(w, f (f) (1)()))))))))))))))) ...... wk V (0K
(-1,(1) ek (1,())) Let Y,,00
K k-10 1. Based on (B.14), we can define coupled versions of A,, 1 2,3, 4 as follows:
22,10)
1
1/2
Σ
Q. 0kk VF(Y
(B.15)
VT
L2VL
As.1i)
=0
Vnk
1-1122
F
+ a (1-
(B.16)
s=1
A4,(0
1
1/2
Σ
Q
wk (9x 10-110 Elc E.,(0))
ge cx
(B.17)
Vn
Note that Di,(;) D1 for all E [n]. With these definitions, along with the fact that E[WWT] allows us to apply Shao and Zhang [2022], Theorem 2.1 on (B.5) to obtain
II
dol dolvni, - 02),2) S <a vav, + +
E uus AAn
An.il.
(B.18)
where 7 ~ N(O, /), Y, = Σ"= Ellu 3 A, = Σt 14 and A An, = Et= A1,0)-
27

---

B.1.3 Bound on Ex=1 21 An An,()
E E w Varl which directly implies En ") in view of the fact wy x for [K]. Therefore, from (B.6) it follows [[[u,] [ O(1/n). and consequently,
Recall that max; Var W = (1). Clearly N₂ are i.i.d and ;
Σ Bl: A
S
BIJA A.,0P
(B.19)
We will deal with the three terms in the right side of (B.19) one-by-one
Bound on A2 22,10) We start with controlling E| - 2 F]. It is easy to see from (B.8) and (B.15) that
K E
A
21,
19 72
2
(A(Y, - V2,(9) -
Smi
72
<K
Y, 1=,(111 -0 K;1-10),
(B.20)
where (B.20) follows from hneais-SSccaazzzzeuualiill and Proposition 8.
B.1.4 Bound on A3 3,
Note that, since + (,)
θ for all hence must have
1 E
B A,,(1)
(0, (I
n
O - (,,(0))( -J)13-1
= (0, (1,01((1- - -J]
Σ
El[(O, - (1 (B.21)
s=+11
Note that,
[I (T |) =1 - G Ga,( J)
Σ
wk (0t
gr (0 ck' )
k=1
K
o (
0 T
2nn E11
Whgk
(B.22)
Hence, Proposition and (B.22) simultaneously imply via (B.21) that
EllA; A3
m
K
Σ
1/ = 0 + Kn Kn - -K:7-48)
(B.23)
K
smi41
B.1.5 Bound A, A.
This term the simplest to deal with. view of the facts (1) Σk_ wx (gx 50) Is <t) is martingale difference sequence adapted to the filtration F, (E, : 8 < V and (ii) for fixed i, gs (0 ( 9n (0 st) are independent conditional on
28

---

Fi-1, one readily obtains
BIIA+
E
wk (gx (0.,005 -gx s(te) (0)
E
(0% (x) wk (g (0;11
gh (0-_1, 5t (0x )111
1 K
K
K
1 0t (1 2K 2
0 - -0x13)
8=1 1=1
k=1
BI -)| + K|Y, - Yo,10// + (r
Kk
2B|1@, - J)1 + K 1
R-1
118 = 0 8 Σ
n1 - 29
1/1
(B.24)
nK
nk
n
where (B.24) follows from Theorem 2.(ii) and Lemma S16 of Gu and Chen [2024], and Proposition
4.
Combining (B.20), (B.23) and (B.24), for (B.19) obtain
8/2
i-8
n -
12-1
B[uu A An
+
+VK(n1/2-20 - -2/2-20) +
Vk
VK
n
i=1
n
+ VKnl-20 1-23
(B.25)
VK
B.1.6 Bound on B[[[|
From E2 S n 1/2 we have B[ [] O(1), where 0(-) hides constants involving d. More-
over, we also have E[| 12 S
Ei |3). For A,, observe that from (B.7),
K 1u1 z K
EiDI
exp(-Can for some constant C3 > O.
(B.26)
On the other hand, for Ωz, we can invoke Assumption A.3 and Minkowsky's inequality to deduce
K
A
EI - 02) VF(()-1))2]
π
K
K
1/
m = 0
n2=2 -8
Vknk-29
(B.27)
7
VK
where (B.27) follows from Proposition
Moving on, for Ag. is immediate that
EEA
S
1I
-I-
T = -
(B.28)
Vn
29

---

Finally, for A1, we recall the argument in (B.24) to provide
K
K
BIA
wk (gx (0=-111))))
-x +*) [9]
8=1
k=1
( J)13 1 -
nK
( + 11s))
nk
71 8
+ 12
(B.29)
K
Combining (B.26)-(B.29), we obtain
E Wi S
V
K
exp( ex -VK-- + n
+ + -8
(B.30)
VK
B.1.7
Final Berry Esseen bound
Note that, for any t E [n]. Pinelis-Rosenthar inequality (Theorem 4.1 of Pinelis [1994]) applies to yield
E|E,!/2N61 S
K
3/2
wo O(K
which immediately implies that
T
Bin 3/2 2
1/2 0
(B.31)
Vnk
Therefore, combining (B.25), (B.30) and (B.31), have that
dc( dc(VnE, 0k), Z) x
1
-
n
Vnk
VK
which completes the proof.
B.2 Proof of Theorem 2.2
Let I Var Na.) = ΣT= V A5 Clearly, [T/ x x
Define U,
r r- 1o Ng Recall (B.3), and rewrite it as
r-1/2 0k) W + D + D + D3 + D.,
(B.32)
where
W
Us
D =I 1/2 AB (Yo - 0%),
n
D2 -T 1/2
A, -0)) VF((.-1)),
n
K
1/2 D3 1/2
A
Wk (VP&(Y.-11) VFa(O.
k=1
K
D4 -I 1/2 Σ
Wh ( (0t-1. E.))
1=1
km
30

---

Let Å Drle for l = 1,2, 4, and let
A = |r 1.
Note that IDale I Σ3. The terms | and | are defined and controlled very similarly to
Theorem 2.1, and the details are omitted. The vR appears by controlling Y, En_ El[u, [3]
a-//2
which we show below. Since | S KK11, therefore
Σ
El 3/2 32
B.3 Application of Section 2: weighted multiplier bootstrap
In the context of vanilla SGD, Fang al. [2018], Fang [2019], Sheshukova et al. [2025] introduced novel multiplier bootstrap paradigm that precludes the necessity of estimating Σ, while performing inference. In this section, adapt this approach for the particular decentralized setting, and hint towards the applicability of our Berry-Esseen theorems 2.1 and 2.2. Specifically, for each client and Var[W*]
k E [K], let Fw be distribution of random variable with E[W4] W iPt For the validity of the bootstrap procedure, we assume that, for all k, of < C. for assume that W uniformly bounded, i.e. that there exists universal constants C1, C2 > such that 01 I W < c2 for all & E [K] almost surely. For b E [B] where B is the number of bootstrap samples, consider the augmented local SGD updates
of
some constant Co > 0. Moreover,
o (0 -.... (.G..))
where
G K[w, W (b)
V (0 ux W (b) iKK
f (0
1,
and for each & E [K]. (W(bb) are i..dd random variables from W [n],b E [B]. For each
1,k
b E [B), define ( = n K- Σe, gk(") Suppose F, := (5h : [n], E [K]). Following
standard arguments (see Theorem of Sheshukova et al. [2025]), adapting the proof of Theorem 2.1 as well as off-the-self Gaussian comparison results Chernozhukov al. [2017], Devroye et al. [2018], is possible to show that
P(Vn(yy -Y,) E PPVT(( 0z) A) S 1//2-
sup AEB(R():A ::A convex
modulo logarithmic factors, with high probability with respect to Fr. This result enables one to approximate the distribution of Y, - 0% via the bootstrap samples ((()) We remark that this approach works when our focus is on Y.: we do not expect this multiplier bootstrap to approximate the entire process (Y.). We leave the detailed derivations future work, since the focus of this paper is on establishing the fundamental Gaussian approximation theorems.
C Proof of Theorem 2.3
Recall that Σ, -- Q.VRQ. and Σ KA-IVXA-T, We aim to decompose E,, K-1E into manageable terms, and then control them piecemeal. To be precise, write
" Σ, -a-k-ls=2 n Σ ((Q.-A-")
A-T + (Q, - A- + (Q. (Q.
Crucial to our proof is the observation that A 1 1/. A,4 for all s, E [n]. Therefore.
n
3
Σ Q = ΣΣ naAl = Σ
Σ
A - - -A_1)) = A- Σ
(1 A6).
s=1j=s
1=1 s=1
j=1ø=
1=1
(C.1)
31

---

where the last equality is via a telescoping argument. From (C.1), we obtain -Q=1 - - AA1 Lj=1 Al. Consequently, recalling that VxlF K-1/2 it is immediate that
" n - F 1Qa.-
n
nVK L. exp(-xt- - O
Σ
A
nvK K
j=1
Moving on, the term (Q Lemma A.5 of Wu et al. [2024] (also see Lemma 11 and 12 of Sheshukova et al. [2025]). This completes the proof (2.7). Finally, (2.8) follows from (2.7) on the account of Proposition and the fact that En is positive-defintt, and hence maps convex set to convex set.
can be similarly controlled by K 1/ from
D Proofs of Section 3
In this section, we derive the time-unifone Gaussian approximation results Theorem 3.1 and 3.2. Our proofs divided into four successive approximation steps. We summarize arguments in the following. In the step I, we control the difference between the aggregated and the local client- level local SGD updates. In step II, we replace the martingale structure of the gradient noise by i..d. mean zero noise. In step III, we further linearize the local SGD updates, which we finally approximate by a stochastically linear Gaussian process such as (3.4) (3.6) in Step IV.
D.1 Proof of Theorem 3.1
D.1.1 Step I
Consider 0 (f%..... 0k) E Rdxk K and let
+ -0i-1-n,G2 G)
11
(D.1)
where G: is defined similar to G2 in (2.2), but with 0g instead of 0f. Moreover, let YP = K K-10 E RRK Suppose Rg (r...... r 0 - n G, and RS defined likewise. Recall (B.1) and (B.2). Define two more intermediate oracle processes:
- - Th
w (E Y. = Yo k=
(D.2)
Y 0
T/e VF(22) 1 + me
wkgn (0 te [n]. Yo Yo-
(D.3)
For random variable X, let || [B[]x131) |
1/2 be the random variable C2-norm. Then,
s - - mel (F F.(00=1) A + B.
(D.4)
Now, for the term A in (D.4), invoking Assumptions A. and A.2, it is easy observe that
+ o (F(F)))))))) - 2n, E A - 12 -
<(1 - 22211/1 - - 112
(D.5)
On the other hand, for B in (D.4), Assumption A.2 entails,
B Snp K Σ
-
- (D.6)
through an application of Lemma S.16 of Supplement of Gu and Chen [2024]. Combining (D.5) and (D.6) and choosing c > V L, it must hold that
| - Y, s (1 n.))lyy, Y 0
32

---

which readily yields
|
- = (Tr))
(D.7)
Very similarly, one show that I|
1 (n))) Finally it remains to show that Y, and Y, is
approximately close. We show it as follows.
|| - - 112
K
-||Vi-1 Y - -
+ v
km
(D.8)
(11-10 -i)-me]lli; -Yo11 4n 2
(110 i-10-1 12-1112 + || -fx11 110
y 11 + || 11)
k=
(D.9)
Th
<(1 -m))l - 1/ 4nz 7/t
+
(D.10)
K2
K
5(1 - mc)] V2 - Y3 1|2 + (
11 m
(D.11)
k
Here, (D.8) employs Assumption A.3 to deduce that 9k (0) (t) - (0 5t) are mean-zero martingale differences adapted to Fi oft
k E [K]); moreover, since { 9n (6) 1.5.) { also uncorrelated. Additionally, (D.9) uses a treatment analogous to (D.5) along with applying Assumption A.2 to the ga terms; and
independent for fixed t, hence 9b. (0
(D.10) involves applications of Lemmas S.16 and Theorem 2(ii) from Gu and Chen [2024]. Finally,
(D.11) immediately implies that
1| 1| =0 + vi )-
which, coupled with (D.7), yields,
1v --) S Σ Y 8p1= Or(nt-0) t=1
max 15tS
(D.12)
$=1
D.1.2 Step II
Moving on, we approximate y by another oracle descent sequence, given by
K
Y = - - Σ wrOn s.), Yy = Yo.
(D.13)
Importantly, (D.13) can be leveraged to linearize the original sequence Y in (B.1). Before we proceed in that direction, we still need to approximate Y, by Y From (D.3) and (D.13), it follows very similarly to (D.8)-D.11),, that,
1|: 1
K + mr u (0 10-)115))
=11Ý,1 r!! 17 (VF((2,)
Σ
(0xx
k=1
<(1 n:) - = -
Ct + C1²
+ <(1 - 0 n/ K 1-);
which immediately yields 1| - r On -1 finally obtain
3/2 K 1/2). Similar to (D.12), here too we T/t
max 1St5
Σ (8: - = 0p 1-388/7 K 1/2).
1-3/22
(D.14)
==1
33

---

D.1.3 Step III
Define Y/ as
K
y = - 1 + T Σ
wais (0 (t)) 80 =0x.
Then it trivially follows that
||x;" y = =1((x - f1,1) ( (VVF(() -
5 - - - Y,,,l S exp(-tt-))11 021?,
(D.15)
which implies maxigign E==1(Y; Y!) (1()), since f"" exp(-(t-0) dt O(1). Moving
on, to linearize Y write (D.13) as
0x = (T 7/: A) 0kx ((VF(L))) - 0k)) + 1/e Wk (0x- St);
(D.16)
where V2F(0k). Note that, Assumption A.1 along with Σ 10 implies that A = pl. Mimicking (D.16), define
K
-1- 7/
Whgs (Ox, <2 Y8 -0.
(D.17)
h=1
Clearly, it follows that
B[ 0 1] S(1 n 0 Y + 7/ 1
V A
0k)ll
<(1 Ta 0R Y
0x 12]
(D.18)
<(1 mI,)BIIY,, 0R Y2-1
(D.19)
where, (D.18) follows from Assumption A.3, and (D.19) is a trivial consequence of Theorem 2.(ii) of Gu and Chen [2024]. Finally, (D.19) yields that
max 1S1S
Σ (Y) OK Y!! Or(n P + n2-299
(D.20)
D.1.4 Step IV
Note that Y, is a linear process, and thus we can hope to bear down standard strong invariance prin- ciple results Komlós al. [1975], Sakhanenko [2006), Gëttse and Zaitsev [2009] on it to yield an asymptotically optimal Gaussian approximation. In particular, let Vx Var Σk= k=1 Wigh ( {*)), e* PA. k E [K]. Note that, Assumption 4.2 in Gu and Chen [2024] can also be sum- marized as |V x 1. We pursue two different type of Gaussian approximation. Let k <t), and N₁ Σk W. By Göttse and Zaïtsev [2009], there exists i..d. Z Zi....,Z, Zn iid. KVRR. such that max (D.17) as
K
W (8%
Z.)l op(n!/n. Write
Ye = (I- + +NN.
which immediately yields
Σ Yo = Σ N.N.Ba.t Bad = Σ Al
(D.21)
sm1
1m1
f=8
where A [[] [[ (I 17j A), A = T. Mimicking yp, define Yū as in (3.4), to which we can
simplify Eim Y = K 1/2 Σ Zo Ej= Al. Note that,
(Y YG )1 S max Ω
Σ K- 1-1/22) opl max Q2 1/22).
max ISSS
max
Istsa
Isrsn
(D.22)
where 24 = | + 2 BB, B,- The proof of (3.5) completed after combining (D.12), (D.14), (D.20) and (D.22) in view of Proposition 2.
34

---

D.2 Proof of Theorem 3.2 and Proposition 1
In this subsection, we pursue finer, client-level Gaussian approximation, with slight sacrifice to the optimality in terms of error rate. In particular, the steps I, II and II from the proof of Theorem 3.1 carry forward verbatim. Consequently, it enables us to invoke from Theorem 2.1 of Mies and Steland [2023] so that for each & E [K], there exists ......, 2h N(0, Var(W*))), such that
K
max ISS
Σ
(
23 Op(K ! 2 Vlogn.
(D.23)
Here W denotes generic I& (. Rdxk and simultaneously define the recursion (3.6). Letting Y K K- 1. one arrives at the recursion
)²). For 0,- ...., 0F E Rd define of (0)
0x²)
K
2 = (1- 1-1 1,2 +
Z
(D.24)
k=1
to which, from (D.23), one has
K
K
1
max 18t5n
Σoe x222
max 18t5n
S4
wh ww 2 Sby log max K-1
Σ
Σ (W 2t¹1
15t5
=02((n// K) + (logn) )3/2),
(D.25)
where the second inequality is due to Proposition 2 and max; we b2k -1 Again, we conclude (3.7) in light of (D.12), (D.14), (D.20) and (D.25). Finally, Proposition follows trivially from Theorems 3.1 and 3.2.
E Auxiliary propositions
In this section, we present some technical results required to prove our main theorems. Propositions 2 and 3 relates the local SGD updates its asymptotic covariance matrices. In particular, Proposi- tion 2 controls the implicit total variation between the linearized local SGD updates, and as such, crucial in deriving the time-uniform approximations Aggr-Ga GA and Client-GA.
Proposition 2. Let A E Rddd be positive definite matrix with smullest eigen value Amin > 0, and define A = - Ti A). A = If
2 = / |F + Σ Ba,t - Bs-1,eFF
then holds that maxigiga Ω Ollg n). Proposition 3. Let Bs,
e be in Proposition 2. Then, for all 2 L, it holds that
|B,, - AF S s- + exp (t2-3 st--)),
where C3 is some constant depending on B, Amin-
Propositions 4-8 characterizes the various properties of the local SGD updates and its difference with its corresponding Lindeberg coupling. These results hold under the conditions of Theorem 2.1, and can be considered as its building blocks.
Proposition 4. Under the assumptions of Theorem 2.1, it holds that for all i [n], it holds that
- Y. -()))))
(E.1)
Proposition 5. Under the conditions of Theorem 1. all E [m], > holds that
EI|(O, (1,0)(1 - .) = K)
35

---

Proposition 6. Under the conditions of Theorem 2.1, it holds that
OI J)(+] Om)
(B.2)
Proposition 7. Under the conditions Theorem 2.1, it holds that
E|Iy; - ffil+] 0 "1 n/²)
(E.3)
K2
Proposition 8. Grant the assumptions of Theorem 2.1. Then, for 2 i, it holds that
E Yú - = =(
(E.4)
Proposition 9 is a typical Gaussian comparison results that relates the finite-sample covariance Σ,, to the asymptotic covariance Σ in terms of the corresponding normal distributions. This result enables theorem 2.3 to reflect the conputation-commuiccai
trade-off of Remark 2.2. Proposition 9 (Gaussian comparison lemma; Theorem 1.1, Devroye et al. [2018]). Let E₁ and Eg be positive definite covariance matrices in RPxp, Let X N E4, and Y N (0, E2). Then
dTv(X,Y) S 2//2 2
1/11/2110 21
Lp
E.1 Proofs of the auxiliary results
Proof of Proposition 2. In the following, all S solely depend on 3 and Amin Observe that for 8 < I
Br,t = no + Not1 (1 (.,A))++..)) Therefore, can be written that
1/s 11s-1 Ba,t + 7-- - 1) == 11 + 12-
B.t B5-1,
(E.5)
7
The J term is relatively straightforward by noting that max,, |B,,/F- =0(1), and
n--1
%
((s ()) On the other hand, for 12, Proposition instructs that
M-- Ba, 1| S 8 881 + exp ( (t 1- + s s'-R))-
(E.6)
Combining (E.5) and (E.6), we obtain
Ba. B.-1. S - exp - ca(t!-B + s1
which immediately shows
+ exp(e exp(-calt-0) S 8 --exp(caot-3) $ log
Ω S
which completes the proof.
Proof of Proposition 3. Decompose B,, = 77 Σラ= boi=sAA3
Aj as
- - A
(1141 1141-1771 7.)A3 + +
(E.7)
j=8
where the sum Σ}= is interpreted as if t. For the term A-1A, in (E.7), we deduce |A61 < exp(-ca(1* 8 + s² ()-))). On the other hand,
H-
1-1 (j 8) exp(-i1-0) S -1
Σ 11t
- 1 n-11, S8- exp(cpss
Σ
j=s
j=s
This completes the proof.
36

---

Proof of Proposition 4. From (B.2) we write
Th Σ k=1 (9x
51)
)).
t= i,
(Y--1 1.() 71 (VF((())))) -
Y2 Y,
11 k= wk (VP - -VP()---0)) (PL(0 + (1,(0))
1/ k= wh ( (0 - 9b 02(0--110:6)))
1> i.
(E.8) Clearly, when & i, we have trivially that BI[,, [,) [2] 01 Hence, focus t > i. Consider the observation that Σk=1 wb (gl 11 9s (0.-...0)...)) is martingale
difference sequence adapted to the filtration F. = (E, $ ( V((E)) Moreover, for a fixed t, go (() gx (, 5 are independent conditional on Fi-1- Therefore, rewriting (E.8) as
Y2 Y,,0 T3 + T2 T3
(E.9)
with
T (Y1-1 Y--10)) No (VF(Y-1) (F(Y)-1,())),
K Σ
T3 T/
Wh (VF(((Y))) -F(XL- VFL + VFr and,
k=1
K
T3 =
Wh (9x (0 < 1, - gu (0, (0-1,111))))
it is easy to see that T Ts] = =E Tsl = 0. Consequently, from (E.8), one computes
E| =1
+ B||Z2/ + | |2] + 2 Tb].
(E.10)
Now all that is required is build recursion by analyzing (E.10) term- cerm-by-term Note that standard arguments invoking Assumptions A.2 and A. yields
B < (1 mc)) Y 111,,
(E.11)
On the other hand, for T3, we proceed follows:
E
Ta
1
w L (0+- 10/
9u (.0-1100:5111
2mh
Σ
w
[B110g - Y B100
Y,- 1,1,0 + Y2-1/10 (?)
k=1
mh
-
(E.12)
K
K
where On bound in (E. is derived upon applying Lemma S16 of Gu and Chen [2024]. Very similarly, one can bound 1/2 as
E T2
K
1 [X2- 02-1,19111 O
(E.13)
Finally we tackle the cross-produce term in (E. Again, Assumption A.2 and yet another applica- tion of Lemma S16 of Gu and Chen [2024] produces
ETT Tbl Sn m/
E
wi
V&&((Y-)) - -F(YY110)) (EL(O,,)) F. (1)
1=1
by VV
Sn
EE[T
BllYi=1 02-11 1 8¹ 1 12
K
Sit /
1
Sml 4c
=B([TTP3)
(E.
Sm "EITT
1 + O(7))
(E.15)
37

---

where (E. (E) involves an application of Young's s inequality zy - ex² + (4c)- "3² with c (4c) where e as (E.11). Therefore, in view of (1 + nt (1 n.c) - 1 2. 15F. into (0. to obtain
we combine (E.11)
+ mi B - 111.0) On + m ) t> i, B| - Y, 5 Th 2 K
which immediately shows (E.1) with standard manipulations (see Lemma A.I and A.2 of Zhu et al. [2023]; Polyak and Juditsky [1992]
Proof of Proposition S. Recall C from (2.2). Let Tt,s be the number of synchronization steps be- tween 1 and t, satisfying [ + Tt,s [= Further note that C -ITi=. Cj. From
(2.2) and (B.14), is easy to see that
1
( - O. J-= - [G -J.
(E.16)
where we have repeatedly used the fact that C1 1. Moreover, also holds that
| - J1l2 S (pt)
max 2).0)
1 (1-cr-11 + [te-s2r-1] 110 Rt, st,
(E.
where ý =p//T. Equation E.17 also appears as (S7) in Gu and Chen [2024]. In view of (E.17), one can expand (E.16) as follows:
E
no (G, (C.
p.r (1, 8) T G. Ge.(s)111
Kt, 8) (t, DnmB [r[ [ Go.())) (G. G.
Imidys
(E.18)
pr (t, 8) ) G. - G.
(pr((1,)) (1, (112)))) n/ 1 'E( G. G + G G1
s=i t=i,
Σ Kp,
2 (t. 8) ) G.
G. |2 + Σ s) G. 1i,,s8
(t.)(.
sm1
(E.19)
Now we are required tackle E G.,(s) (1) [.]. To that end, observe that for > i
K
BIIG, G. (
K2
w E
Vi (0 + v fa -,.
k=1
К
2b L
EllAb 3
8% 13-111111
K
K
[ - Y || + Σ
E
0h 1143 - Y Y,-1111/ + Σ B - Y Y--1, 11
1=1
1=1
())
(E.20)
38

---

where (E.20) follows from Lemma S16 of Gu and Chen [2024] and Proposition 4 respectively.
Putting (E.20) back into (E.19), we obtain
ns Kr (1,8) Σ p 0 K),
where the last assertion uses J x x= e dx S n n for a, > 0, where S is independent of n. This completes the proof.
Proof of Proposition 6. We can re-purpose significant portions of the proof of Lemma S16 of Gu and Chen [2024] to prove (E.2). Indeed, writing O = =>o.. 17 G. we have from the referenced proof that
OI - J) =1I
Σ
a=1
<2E
k p.r (t, G)
21E (E
Kpr (t, s)
Σ
ni (t,
(n,mn Gil) 21
1= 111,8
S + S2-
(E.21)
For S1 in (E.21), it is straightforward to obtain
S x
n prr (t, 8) Gi + Σ Σ
Th k (t,
1= Likk
Ty p.r (t, $) B) + Σ
p (t, (1,))m BlIG.
max
Σ (t,()
(E.22)
1=1,45
K2 (n p.r (t, + R (t, (t, = Om
(E.23)
where, in (E.22) we apply AM-GM inequality to derive
T G G 11 1 E [
very similar treatment yields the same bound S2, completing the proof of (E.2).
Proof of Proposition 7. Write
R. Y, 0x = E1 E2 + Eg, where,
Ej = RR-1 TI VF(Y,1)),
K
F2 1B
Wk (V.+((
V (Ot and
k=
E3 17
wk (0--1. <t)
(E.24)
Note that trivially, Assumptions A. and A.2 imply that
E| E, [1] (1 Rt
(E.25)
Moving on, for Eg proceed follows:
E E
E[
wk (VF. (F&
k=
K Y - 04- 12)
mi
<O²
K2
k=1
<0₂ n
< | Chn.
(E.26)
K2
39

---

for some constants C2 C2 > O, where the final assertion is drawn from Proposition 6. Finally, for Eg, we obtain.
of K2'
Bl| [|] = - B1
Σ when (0 (0)-11 - C3
(E.27)
for some constant C3 > O, where we have used the fact that gn (0/_1, <t are mean-zero and inde- pendent random vectors conditional on Fú. Now, we will leverage (E.25)-(E.77) to develop bounds on the cross pross-t terms, In particular,
E/ F2l s VE[LE [4] B[
CCan [
<C3 Bi E |111 + (4c)~1n m,, Ne nEEB[EE]11] + (4:)-
(E.28)
and similarly
Th K 1EBB|E,114 + (4=)-1 -1 Di K
B|E SC3 min + (4:)-1
(E.29)
where the final assertions follow from Young's inequality. Here, chosen to be small enough, however it remains constant: the explicit choice of will be indicated towards the end of the proof, when we collect terms to establish the recursion. Note that, quite trivially, from (F.26) and (F.27), one has
B|EE|!|ESs! S C. Di for some constant C. >
(E.30)
Rest of the cross-products are strictly dominated by some combinations of the terms analyzed now. For example, for Nor1,r, r, 21, Mauchy-Schwarz and AM-GM inequalities implies that
E[(ET ) < E.
EE [3 S / B / BIEET E,,",,
E (E F2)1 <2 / (E[(E) E,) ) + E[(ET E))
(E.31)
careful collection of terms from (E.35)-(E33)) yields
ni K
| & (1 - m1) + C,E Co O + m
(E.32)
where Co a large constant depending upon C2 C3 and C4. Now, choose e > 0 so that Coe < c/2, upon which we immediately obtain (1+ < 1 c/n. Therefore, (E.32) immediately yields (E.3).
Proof of Proposition 8. Recall (E.8). Clearly, for t the result trivial. For t i, we leverage (E.9). A proof very similar to (E.3), which uses similar decomposition (E.24), can then be followed. The crucial term |||Z; ] which is computed below. Note that
K
T T
Mh 00 (.) 9x (0/-1.10 (.)))")))) s
E
K
< 12
E
10 02-1(1917
K
k=1
<27L'
E
10 Yr- 10 + K|Y,1 111,1111 Σ 10-1,11) 1--1101
E[K - 10 10,- + 100
K
Sm.Blly
- - 1--10100+000
(E.33)
40

---

Therefore, from (E.33), it follows
E T
B|
S SVEITT|> BBI Y 1,11 + O(T)))
- ( O
E -
(E.34)
Rest of the terms are computed similar Proposition 7, and the details are omitted. The final recursion can be derived to be
B| - (o (41 s (L--ncEEllV--1 Y, (.(() (1) 1 O(n)) for some small constant >> 0,
which immediately yields (E.4).
F
Additional Simulations
F1
Effect of n and K on the Berry-Esseen rate
In this subsection, we empirically investigate the behavior of the Berry-Esseen error de(vn((,, 0j), Z) for Z (0,, Σ,) with varying choices of the number of iterations N and the number of clients K. the bound (2.5) is sharp, we expect the Berry-Esseen error to decay with increasing N, and increase with increasing number of clients. Since the distance de involves taking supremum over convex sets, which computationally infeasible, we restrict ourselves to the following measure of the approximation enror:
de = sup |P(VnE,,\/(E, - 0x)1 x) P(IZ & x)). Z N). xE(0.c]
For large enough e O, expect de to be reasonable proxy for de. For numerical exercises quantify des analyze the output Y,, of the local SGD algorithm under federated random effects model, hereafter denoted as FRand-eff. We describe the set-up below.
F111 FRand-eff formulation
Consider a positive definite matrix r E Rdxd and 3n E Rdd and let D := [Bi..... 3k) iid. I). Moreover, consider Σ := {of...., of C R For E [K] and at [n]-th iteration, suppose that the k-th client has access to data (yt,, Tt) E RR Rd generated from the linear model Vık (1 of). If the weights are chosen such that w1 =... w K-1, then clearly 0 = Ex= wrB3 + Bo as K + DC. Therefore, local SGD can be employed, and we expect Y, to consistently estimate 3o as n and K grow. This model highlights the need for information-sharing across client, since unless particular client is inconsistent for Sg.
-==
the output of local vanilla SGD for any
For the purpose of the numerical exercises in this section, choose d = 2 and Bu (2, -3) and let r== 7 with 7 2 0. In particular, 7 = corresponds to a fixed effect 3g from which each client generates their observations. For each K, generate Σ uniformly from the set (1,...,5) 5), D from the specification above, and keep them fixed throughout the corresponding experiments as n varies. The underlying connection matrix C is taken C.j 1 T jl < 1), E [K]. In other words, every client is connected to only its two immediate neighbors.
F.1.2
de versus and K
In this analyze the behavior of de versus for different choices of K, r, and y. In particular, we aim to verify the Berry- Berry-Esseen enror rate of 1/2-88 8 VK from Theorems 2.1 and 2.2. Let y 1. Consider the following two separate settings corresponding to n, K, and т.
Setting 1. Let K = 10, and vary E 2100,200, 300, 400, 500), and {10, 15, 20). For each pair of (n, 7). we plot d, against
41

---

Setting 2. fix n 300, and vary K E {20, 40, 60, 60,80,088,,0088 100), and 7 E {10, 15, 20). For each pair of T), we plot de against K.
We provide the practical details behind empirically estimating de. For each of the experimental settings described above, we generate (yht, Fzx.) E IR R2 , E [K], E [m] from the FRand-eff
specification described above, and run the local SGD algorithm with step size t 0.3/ 0.75 for t E [n]] For the large choice of = 100, d, is empirically estimated by ss = 1000 many independent Monte-Carlo repetitions of our experiments.
Figure 1 allows us to draw important practical insights from the rates of Theorems 2.1 and 2.3. Firstly, from the Settings and 3, the synchronization parameter does not seem have significant effect on the behavior of de. Moreover, Figure I(left) seems corroborate well with the conclusion of Theorem 2.1, with de decaying with n for fixed K. On the other hand, for Setting 2, Figure (rright) seems to point towards a trade-off in terms of K for fixed n. This particular behavior becomes clearer as we recall (2.5). For fixed n 300, the initial decay of de (and by extension, dc) with increasing K, is caused by the n 8/2 n --/22 term. However, as K increases, the term n / starts to dominate, leading the error de to increase with increasing K. This numerical exercise establish the sharpness of our upper-bound (2.5), complementing the discussions in Remark 2.1.
To investigate the behavior of de further, also consider the increased heterogeneity across 8k. the effect of synchronization becomes more pronounced; for the same values of n, K, r. the de values are much lesser compared to that in Figure 1. In particular, in Figure 4(right), the inflection point in K beyond which n//2--0 V K starts to dominate, has shifted to the right. This is understandable, since increased variability among S: means a greater reward for sharing information, and thus the effect of increasing the clients leads lowering the error de for longer regime, before the asymptotics of n-/2-B8 /K eventually kicks in.
5. In Figure 4, due to the
F.2 Computation-communice
trade-off
In this section, we numerically investigate the computation-commuiicai Remark 2.2. There, noted that if K x n for 1/22, then, based on our upper bounds, argued that for no 8 E (1/2, does de converge to 0. In particular, this observation trivial for E (1/2, + c/2) since the central limit theory itself fail help view of violation of K 2 28 Of particular interest is the range (1/2 c/2, 1), where, as per Theorem 3 of Gu and Chen [2024], central limit theory continues to hold, but (2.8) suggests that the upper bound to de is no longer (1))
trade-off hinted at in
To explore this phenomena through numerical examples, we invoke FRand-efffor y = 0, and let {100, 200, 300, 400, 500), and K = [n"] for r E {0.2, 0.63. In conjunction with Theorem 2.3, we consider the following error:
d = sup P zE(0,e|
-0 = - x))
where Σ = A- SSAT. Moreover, consider the local SGD algorithm with 5, and T). 0.5t 9, In light of 1/2+r/2 {0.6, 0.83, we ensure the validity of central limit theory by letting 8 E {0.85, 0.9, 0.95). Finally, for each value of r, we plot de against n for the different choices of B. For r = 0.2 and = 0.6, the evident decreasing and increasing trends of d. in Figure 2 respectively, vindicate not only the sharpness of our Berry-Esseen bounds Theorems 2-1... but also clearly highlights trade-off at the region /n < K < n.
F3 Effect of heterogeneity
In this section, we characterize the effect of data hetero- geneetty on the Berry- emrors of The- orem 2.1. To start with, we note the following generalized version of Theorem 2.1, whose proof merely follows from careful tracking of constants, and is therefore omitted.
Corollary F.1. For g(k) ~ Ps& (the data distribution of client k E [K], define μl, = ( fa ( (())
2,3,4 4. Denote Mi Σx Ma, and M22 Σ 12, Assume that for
K
42

---

some constant > O. ming Pa.k 2 Further, assume maxe Ex= wvl(V VFL( & n² for some 2 O. As long as I On, for some (0, 1), under the assumptions of Theorem 2.1, follows that:
dolvni(Y, 0k),
2(*
1
M3
8/2
n 1/2-8
SO--SVVV (VK
VM1 + M22
M2
V1 /1-1
V
3/2
vM2
K KVM2
- (VK
M4
M2
n2 1/2-25
VM2 + n
M1
(F.1)
M2
for some constant с 2 O.
The effect of heterogeneity can also be verified empirically, by noticing that plays the role of heterogeneity in the Frand-eff formulation in Section F.1.1 in the supplement. The corresponding simulation results can be seen in the following.
7 7
100
71
200
n1 = 300
0.222
0.224
0.154
0,258
0.188
0.112
0.322
0.322
0.302
0.374
0.272
0.232
5
0.542
0.292
0.302
Table I: Berry-Esseen error across different levels of heterogeneity under step-size= 0.3/-0.75 num-
ber of clients = 10, r = 2, C;5 = 1/37 - S 1}, dimension d All the results are based on 500 Monte-Carlo simulations.
F.4 Effect of Syuchronization
Note that, from the verbose Corollary F.I, one can glean the following result that condenses the effect of synchronization an interpretable manner.
Corollary F.2. As long T S On, for some 0 (0, 1), under the assumptions of Theorem 2. it follows that:
( (11 + + V1 pTrr (vn
1
do(Vi((n - -2), (VF
V
(F22
K
for some constant e 2 O.
In particular, allow the synchronization parameter grow linearly with n. Clearly, the number of local updates 7 increases, the errors increase with /T rate. This have also been verified empirically in the following table.
n
100
200
n 300
10
0.087
0.100
0.110
20
0.118
0.146
0.155
30
0.139
0.168
0.171
40
0.155
0.183
0.185
50
0.164
0.196
0.211
60
0.176
0.225
0.220
70
0.175
0.218
0.231
80
0.176
0.230
0.252
90
0.176
0.234
0.253
100
0.175
0.241
0.261
Table Comparison of Berry-Esseen error across different values of T under step-size= 0.31 0.75
number of clients K = 10. dimension d = 2, Connection matrix C; = 1/31 S 1).
43

---

F,5 Effect of connection matrix
In the following, we provide experimental results on how the Berry-Esseee errors depend on the network topology (p), where p is the second largest eigen value of the connection graph C. As the network topology becomes less connected (p 1 1), the GA error scales as (1 /1/T)-1/2, On the other hand, when p = 0, the network is densest as C = k-- 1x1k and the algorithm essentially becomes centralized one.
P
71
100
71
200
71 300
0.1
0.094
0.084
0.089
0.2
0.106
0.107
0.104
0.3
0.121
0.126
0.124
0,4
0.136
0.143
0.138
0.5
0.149
0.164
0.154
0.6
0.165
0.192
0.175
0.7
0.184
0.217
0.203
0.8
0.203
0.245
0.250
0.9
0.212
0.275
0.294
Table 3: Comparison of Berry-Esseen across different values of p under step-size= 0.31
number of clients K = 10, dimension = 2, synchronization parameter = 10. For each
C = plp + p) -1k
F.6 Performance of the time-uniform Gaussian approximations
This section devotes itself to numerical studies to validate the efficacy of the Gaussian approxima- tions Aggr-GAand Client-GA, discussed in Section 3. Consider the quantities
U, max IstEn
Σ[r, (Y, 0k),, Udger-
YGG and UClient-OA
max
YG s,2
Istsn
where Y. and Y are defined as Theorem 3.1. Moreover, also consider the Brownian motion approximation by functional central limit theorem as another competitor, and as such, consider
UfTCLT
Σ Zel, Zi,... .2,...,2. Zn iidd NOOE),, ==1
max Isten
where E is as in Section 2.2.1. In order to compare the distributions of UAggr-OA U/lleettGA and Uf-CLT that of Un. we resort to Q-Q plots. Fix
500, 7 20, and let K E {10, 25, 50}. For each triplet of of (N, K, we simulate 7sm 500 parallel independent local SGD chains with step-sizes 1)+ = 0.7t 0.75 and observations from the FRand-eff model in order to empirically simulate Un. Concurrently, we also simulate nsim independent observations from the distributions of UA AAA U (Cllsent-GA and ULLCCL by running the corresponding chains in parallel. The QQ-plots are shown Figure 3.
The sub-optimality of the functional CLT as time-uniform Gaussian approximation to (Y:} is em- pirically evident from the QQ-plots. Both our proposals Aggr-GA and Client-GA uniformly dom- inate the approximation via Brownian motion across different settings. Moreover, as K increases from left panel to the right, Aggr-GA out-performs Client-GA. This line with Proposition (i) and (ii) underpianing the sharper approximation rate for Aggr-GA. However, we must recall that Client-GA requires local covariance estimation for each client, thus protecting the privacy of the federated setting.
44

---

Figure 4: Plot de against n and K for y = 5, and Settings I(left), and 2(right).
E.7 Ablation Studies
In the following, further investigate the affect of heterogeneity and synchronization for the time- uniform Gaussian approximations. In particular, we carry out two ablation studies for the parameters and y in the FRand-eff formulation. In the first experiment, we fix N 500, K 15, d 2, Cij = 1/3/[lj - il < }} and = 1, and vary T = 5, 50, 100. For each particular setting, we report the following quantities:
14-a 91 a (U
n1 (Un)(Un) - 11---(UUs (U
QE-OLT = max
Q QAggr-GA (0(1)))
max
and,
aE(U,1)
91-a (Un)
(Un)
89 9i-m (L Cisere ai
Qcssent-ca = maxae((01)
The following table summarizes the results.
91-a(Uu (U,)
QE-CLT
QARor-GA 0.214
Qciient-GA
5
1.495
0,327
10
2.009
0.44
0.53
15
2.476
0.663
0.883
Clearly, as the number of local steps T increase, the efficacy each Gaussian approximation wors- ens; however, the two Gaussian approximations proposed, Aggr-Ga and Client-GA consistently outperforms a functional-CI.T based approach, mirroring our results from Section 4.3. Moreover, Aggr-GA consistently provides the sharpest approximation, vindicating the theory outlined in Sec- tion
Moreover, we also fix N = 500, K = 15, t = 20, and vary the heterogeneity parameter = 1, 10.
The results are follows.
7
QE-OIT
QAegr-GA GA
Qclient-GA
1
1.047
0.237
0.275
2.047
0.605
0.646
10
2.805
0.547
0.782
We again see the worsening performance of the Gaussian approximations with increasing hetero- geneity.
G Experiments on attack instance detection via time-uniform approximations
G.1 Attack instance detection
To round off our discussion in Section 3.1, one can exploit the time-uniform approximation guar- antees of Theorems 3.1 and 3.2 to propose valid, Gaussian bootstrap-based algorithms for attack instance detection. For convenience, we only state an algorithm based on Theorem 3.1; corre- sponding algorithm based on Theorem 3.2 can be likewise constructed.
45

---

Algorithm 2 Time-uniform Gaussian bootstrap
Initializations Ou = -fh..... 80 E Rd K Connection matrix C; Synchronization pa- rameter r; Loss functions fa (t, 5k ~ Pk; k E [K] weights [ number of iterations ni step-size schedules {no ) Hessian A; number of bootstrap samples B; covariance matrix VK.
Input:
Let Er (T, (T. Lr}, where L [ Initialize 1. Stopping time To
estimated attack instance 60 = + inf. While / S
Store the local SGD iterates Y, and caleulate R. = maxigagt Yy and st arg Sa 8 YY, Yz). For B 1,...: B:
Draw - NO, Vx), and do Y GG, = (I (1-M)A)), m Z, (6)
G((b)
K-1/2 1/2 Yo
K
0. Calculate R, maxi 8 (r y.(1100)
i < sample quantile ( Thresholding: If R2 > @1 a cvn:
[ (RG(())) )).
To t t. Su t st. Stop.
Else 1+ Output: 1To < n1).87.
We remark that Algorithm 2 is directly motivated from (3.3); it not only detects the attack instance, but detects it as soon as possible in a sequential manner. We provide some numerical experiments validating this algorithm in Section G.2.
G.2 Numerical experiments on attack instance detection
For a corresponding numerical validation, we consider the Frand-eff model in Section F, and consider an attack at time point to = T/2 for Ko = K/2 many clients, where their corresponding parameters 3r change to 3 3r + μ.. We take T 500, K = 10, r 20 and for each setting, the above algorithm is run for B 500 bootstrap samples. The empirical power of the described algorithm is reported below, based on 500 Monte-carlo simulations.
Probability of detection
Attack instance (mean, 95% CI)
Stopping time To (mean, 95% CI)
0 (No attack)
0.046 (False posilive)
0.5
0.172
201.233, (58.75, 290.875)
400.67, (141.25, 496.875)
0.966
265.203, (144.05, 309)
412.49, (345.05, 482)
1.5
253.772. (133.9, 310.525)
389.61, (292,477,,
2
249.672, (118.85, 18, 286.575)
356.32. (311.475, 397.525)
2.5
247.098, (113.8, 281)
343.39, (294.955, 379.525)
3
249.572, (94.275. 276)
334.57, (282.95,66)
Table 4: Simulation results of attack detection.
Clearly, the higher the severity of the attack (μ1 being large), the more probable it is to be detected, and the quicker it gets detected. Moreover, the estimated attack time also stabilizes around the correct attack instance. Finally, we note that the algorithm can be modified to perform the sequential test only at the synchronization steps, instead of testing for all t.
G.2.1 Experiments based on MNIST dataset
As further application of Algorithm 2, we work on federated learning (FL) setup with K = 5 clients collaboratively training linear classifier on MNIST data. Let each image be H; E 28x28 To get rid of high-dimensionality, PCA transform P I2 - Rd with d 3 is fitted on the full training set 2 P(x,) E R33 At time point t, each client & e [K] sequentially receives ch (vt 2t''s where S are corresponding digit labels. Following the notation of the paper, the loss function of client & is the cross-entropy loss:
(W,b; -y, log(ú!) (1 - v. log(l111111 ot), of = +b,
46

---

where is the sigmoid/logit function, and W E R and b E R so the parameter vector 0 Ve bl) R= with d 40. The weight parameters for the aggregated objective function are = --1,, h E [K], and the step-size is t 0.3/ 0.31-0.73 in conjunction with our empirical exercises. The synchronization parameter is r 5, and we use the connection matrix from the simulation: C₁ = []j il I 1). Finally, we run the local SGD iterates for 200 iterations.
For randomly selected of Ko clients, labet-flipping attack (the label of image of digits 1, 2, 4 are switched to 7, 5, 8, and vice-versa) is injected at t = 50, and Algorithm 2 is employed to detect this attack. The matrices and VK are inputs to this algorithm, and are therefore estimated by pre- ceaiiiiiing//mmmm-em transient phase. The results are summarized in the following table.
Probahility detection
Attack instance 5o (mean,
Stopping time (mean, 95% CT)
No attack
0.06
Label llippin allack
0.90
58.49, (31.7, 96.25)
95.67, (88.9.
Table 5: Simulation results for label flbppig attack detection.
We note that the empirically validity under level 0.05 is approximately maintained, and the algorithm also achieves high detection power under the label-flipping attack. We remark that the detection can be made earlier by tuning the constant e in the thresholding step appropriately by eg. cross- validation, but overall this experiment shows the applicability of such Gaussian- -bootstrap based algorithm beyond theoretical rates, in practical scenarios.
47


Reviews:
[{"review_id": "J31wgq1NUz", "reviewer": "Reviewer_PXEE", "summary": "This paper proposes two generalized Gaussian approximation methods for local SGD in Decentralized Federated Learning (DFL). First, the authors derive Berry-Esseen bounds for the final local SGD iterates, enabling valid multiplier bootstrap procedures. Second, they provide two sharp time-uniform Gaussian approximations over the local SGD trajectory. Specifically, the theoretical results proposed in this paper are related to the choice of the number of iterations $n$, and the number of clients $K$, the step size $\\beta$. These results enable the development of valid and powerful statistical inference methods, thereby enhancing the performance of federated learning in terms of privacy, robustness, and computational efficiency. Empirical results not only validate the theoretical analysis in the paper but also demonstrate the effectiveness of the proposed methods compared to off-the-shelf Brownian-motion-based approximation.", "questions": "Are there any empirical results to indicate the effectiveness of the proposed GA methods for detecting adversarial attacks?", "limitations": "This paper focuses on proposing the asymptotic statistical guarantees beyond convergence properties of local SGD under DFL. However, more experimental evidence could be provided to demonstrate the effectiveness and potential impact of the proposed sharp time-uniform Gaussian approximations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n1. The idea proposed in the paper is easy to follow, and the proposed asymptotic statistical guarantees for local SGD under DFL are potentially impactful. \n2. The elaboration of the proposed theoretical results is sufficient and intuitive.\n3. Both theoretical analysis and empirical results are provided to justify the effectiveness of the proposed Aggr-GA and Client-GA.\n\n### Weaknesses\n1. The pseudocode for the two sharp time-uniform Gaussian approximations could be provided.\n2. Some of the interpretations of empirical results are inconsistent when comparing the main body and the appendix. For example, $\\tilde{d}_c$ does not linearly increases with $K$ for fixed $n$ in Figure 1 right, and is caused by the different dominate term in Eq. (2.5) when increasing $K$. However, the analysis in Section 4.1 says that $\\tilde{d}_c$ increases with $K$ for fixed $n$.\n3. Additional comparative analysis with other approaches in the literature could strengthen the findings.\n4. Typos in line 320, \"we discuss the Berry-Esseen error Berry-Esseen error $d_C$...\".", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for carefully reading our manuscript and for the positive comments on its readability and thoroughness. Below, we address your comments individually. We warmly welcome any further suggestions to improve the paper. If our responses adequately address your concerns, we kindly ask you to consider increasing your score.\n\n### Weaknesses\n\n1. ***The pseudocode for the two sharp time-uniform Gaussian approximations could be provided.***\n\n      *Answer*:  The time-uniform Gaussian approximations follow an iterative scheme given by equations (3.3) and (3.5) in the paper. Here we present a pseudocode:\n\n     **Algorithm: Time-uniform Gaussian approximations**\n\n     Input: Client-level variances $H_k$, $k\\in[K]$.\n\n    - Let $E_{\\tau} = \\{\\tau,2\\tau,\\ldots,L\\tau\\}$, where $L = \\lfloor n / \\tau \\rfloor$. \n    - For $t=1,..,n$:\n\n    A. Store the local SGD iterates $Y_t = K^{-1} \\Theta_t \\boldsymbol{1}$, where $\\Theta_t = (\\Theta_{t-1} - \\eta_t G_t)C_t$\nwith \n$C_t = \\begin{cases}\\mathbf{C}, & \\text{if } t \\in E_{\\tau} \\\\\\\\I_K, & \\text{otherwise.}\\end{cases}$.\n\n   B. {Aggr-GA}: Draw $Z_t \\sim N(0, K\\sum_{k=1}^K H_kH_k^\\top)$, and do $Y_{t,1}^G = (I - \\eta_t A) Y_{t-1,1}^{G, (b)} + \\eta_t Z_t^{(b)} K^{-1/2}$ with $Y_{0,1}^{G, (b)} = 0$.\n\n  C. {Client-GA}: Draw $Z_t^k\\sim N(0, H_k)$ for $k=1,..,k$, and do $\\Theta_t^{G} = \\big((I -\\eta_t A) \\Theta_{t-1}^{G} + \\eta_t M_t\\big)C_t$, where $M_t:= K(w_1 Z_t^1, \\ldots, w_K Z_t^K)$, and define $Y_{t,2}^G=K^{-1}\\Theta_t^G 1_K$.\n\nWhat Theorem 3.1 (and Theorem 3.2) says is that the distribution of $Y_{t,1}^{G}$ is close to that of $\\{Y_t\\}$ in a very strong sense.\n\n2. ***Some of the interpretations of empirical results are inconsistent when comparing the main body and the appendix. For example, $\\tilde{d}_c$ does not linearly increases with $K$ for fixed $n$ in Figure 1 right, and is caused by the different dominate term in Eq. (2.5) when increasing $K$. However, the analysis in Section 4.1 says that $\\tilde{d}_c$ increases with $K$ for fixed $n$.***\n\n  *Answer*: We sincerely regret the confusion caused; due to space constraints, we could not include every detail in the main manuscript. However, in the supplementary Appendix section F.1, we write:  \n   \n   > \"On the other hand, for Setting 2, Figure 1 (right) seems to point towards a trade-off in terms of $K$ for fixed $n$. This particular behavior becomes clearer as we recall equation (2.5). For fixed $n=300$, the initial decay of ${d}_c$ with increasing $K$, is caused by the $n^{-\\beta/2}K^{-1/2}$ term. However, as $K$ increases, the term $n^{1-\\beta/2}\\sqrt{K}$ starts to dominate, leading the error $d_c$ to increase with increasing $K$.\"\n\nThis is in line with equation (2.5) of Section 2, where, in Remark 2.1, we also mention a similar trade-off. We hope this clears up the confusion, and we have added this part in the main draft.\n\n3. ***Additional comparative analysis with other approaches in the literature could strengthen the findings.***\n\n*Answer*: We are not aware of similar results in the literature. As reviewers *mVKL* and *6krr* note, our work provides the *first* Berry-Esseen bounds and time-uniform Gaussian approximation bound in the Federated Learning/`local sgd` setup. Therefore, our paper primarily focuses on novel theoretical contributions, and does not aim at proposing or competing with SOTA algorithms. Nonetheless, we acknowledge that competing approaches might exist for some applications of our results, such as attack instance detection. However, to the best of our knowledge, the literature mostly revolves around robustness guarantees (error bounds, convergence rates) assuming a certain adversarial profile or detection of malicious clients (Blanchard et al., [*Machine Learning with Adversaries: Byzantine-Tolerant Machine Learning*], NeurIPS 2017; Wang et al., [*Attack of the Tails: Yes, You Really Can Backdoor Federated Learning*], NeurIPS 2020; Qian et al., [*ByMI: Byzantine Machine Identification with False Discovery Rate Control*], ICML 2024; Mapakshi et al., [*Temporal Analysis of Adversarial Attacks in Federated Learning, Machine Learning, Deep Learning and AI for Cybersecurity*, 2025] ). This makes our approach rather unique. \n\n4. ***Typos in line 320: \"we discuss the Berry-Esseen error Berry-Esseen error $d_C$...\".***\n\n*Answer*: We have fixed it and tried removing any other typo in the paper.\n\n### Questions\n***Are there any empirical results to indicate the effectiveness of the proposed GA methods for detecting adversarial attacks?***\n\n*Answer*:  This has been addressed in detail below. \n\n### Limitations\n***This paper focuses on asymptotic statistical guarantees beyond convergence for local SGD under DFL. However, more experimental evidence could demonstrate the effectiveness and potential impact of the proposed sharp time-uniform Gaussian approximations.***\n\n*Answer*:  Thank you for this important suggestion. In our paper, we discussed in equations (3.1) and (3.2) (Section 3.1) how our Gaussian approximation results help detect model poisoning attacks. Below, we first provide pseudo-code for an algorithm leveraging our `aggr-GA` result (Theorem 3.1) to detect such attacks, followed by empirical exercises and real-data experiments. Similar algorithms can be devised using Theorem 3.2. \n\n**Algorithm: Attack detection using time-uniform Gaussian bootstrap**\n\n- **Input:** Connection matrix $C$; Synchronization parameter $\\tau$; Loss functions $f_k(\\theta, \\xi^k)$, $\\xi^k \\sim P_k, k \\in [K]$; weights $w_k$; number of iterations $n$; step-size schedules $\\eta_{t}$; Hessian $A$; number of bootstrap samples $B$; covariance matrix $V_K$. Type-1 error level $\\alpha$. \n-  Initialize $t = 1$. Stopping time $\\hat{T}_0 = 1$, estimated attack instance $\\hat{s}_0 = +\\infty$.\n- While $t \\leq n$:\n1. Store the local SGD iterates $Y_t$, and calculate\n   $$ R_t = \\max_{1 \\le s\\le t} s\\bigl|\\bar Y_s-\\bar Y_t\\bigr|\n     ,\\quad\n     s_t = \\max_{1 \\le s\\le t} s\\bigl|\\bar Y_s-\\bar Y_t\\bigr|.$$\n2. For $b = 1,\\dots,B$:\n   - Draw $Z_t^{(b)} \\sim \\mathcal N(0, V_K)$, and set\n     $$Y_{t,1}^{G,(b)}\n       = (I - \\eta_t A)\\,Y_{t-1,1}^{G,(b)} + \\eta_t\\,Z_t^{(b)}\\,K^{-1/2},\n       \\quad\n       Y_{0,1}^{G,(b)} = 0.$$\n   - Calculate\n     $$R_t^{G,(b)}=\\max_{1 \\le s\\le t}s\\bigl|\\bar Y_{s,1}^{G,(b)} - \\bar Y_{t,1}^{G,(b)}\\bigr|.$$\n3. Compute $\\hat q_{1-\\alpha}(t)$ = sample‑quantile $(R_t^{G,(b)})_{b=1}^B.$\n \n4. **Thresholding:**  \n   If\n   $$R_t > \\hat q_{1-\\alpha}(t) + c\\,\\sqrt n$$\n   then set $\\hat T_0 = t$, $\\hat s_0 = s_{\\hat T_0}$ and **stop**,  \n   otherwise $t\\leftarrow t+1$.\n\n- Output:\n$$\\hat T_0 I_{\\{\\hat T_0 < n\\}}\\; s_{\\hat T_0}.$$\nA detailed explanation on the theoretical validity of this algorithm can be found in the rebuttal to **Question 5, reviewer SopJ**. For simulations, we consider the `Frand-eff` model introduced in **Section F of the manuscript**. Recall that at iteration $t$, client $k$ observes data $(y_{tk}, x_{tk}) \\in \\mathbb{R} \\times \\mathbb{R}^d$ generated by the linear model\n$y_{tk} \\sim N(x_{tk}^\\top \\beta_k, \\sigma_k^2).$\nWe simulate an attack at $t_0 = T/2$, affecting $K_0 = K/2$ clients, shifting parameters to $\\beta_k' = \\beta_k + \\mu$. Set $T=500$, $K=10$, $\\tau=20$. The empirical power of the proposed detection algorithm is reported below for different values of $\\mu$.\n\n| $\\mu$| Probability of detection| Attack instance (mean, 95% CI)| Stopping time $\\hat{T}_0$ (mean, 95% CI)|\n|-|-|-|-|\n| 0 (No attack)| 0.046 (False positive)| - | - |\n| 1 | 0.966 | 265.203, (144.05, 309)| 412.49, (345.05, 482.)|\n| 2 | 1 | 249.672, (118.85, 286.575)| 356.32, (311.475, 397.525)|\n| 3| 1| 249.572, (94.275, 276)| 334.57, (282.95, 367)|\n\nClearly, the more severe an attack (large $\\mu$), the quicker it gets detected, and the attack instance is also estimated with higher precision. Finally, note the algorithm can be modified to perform sequential tests only at synchronization steps, rather than at every iteration $t$.\n\nFor the real-data experiment, we work on a federated learning (FL) setup with $K = 5$ clients collaboratively training a linear classifier on *MNIST* data. Let each image $x_i \\in \\mathbb{R}^{784}$. To handle high-dimensionality, a PCA transform $P: \\mathbb{R}^{784} \\rightarrow \\mathbb{R}^d$ with $d = 3$ is fitted on the full training set $z_i = P(x_i) \\in \\mathbb{R}^3$. At time point $t$, each client $k \\in [K]$ sequentially receives $(y_t^k, z_t^k)$ where $y_t^k$ are corresponding digit labels. Following the notation of the paper, the loss function of client $k$ corresponds to the *cross-entropy loss* for the logistic model $y_t^k \\sim \\operatorname{Multinomial} (1, W z_t^k + b_k)$, where $W \\in \\mathbb{R}^{10 \\times 3}$ and $b \\in \\mathbb{R}^{10}$, so the parameter vector $\\theta = \\operatorname{Vec}([W:b]) \\in \\mathbb{R}^{d}$ with $d=40$. The aggregated objective uses weights $w_k=K^{-1}$ for $k \\in [K]$, with step-size $\\eta_t= 0.3 t^{-0.75}$ consistent with our empirical analysis. The synchronization parameter is $\\tau=5$, and we reuse the connection matrix from simulation: $\\mathbf{C}_{ij}=1/3 I\\{|j-i|\\leq 1\\}$. Finally, we run the local SGD iterates for $n=100$ iterations.\n\nFor a randomly selected subset of $K_0=3$ clients, a *label-flipping attack* (labels of digits $1,2,4$ swapped with $7,5,8$, respectively, and vice versa) is introduced at $t=50$. The Gaussian bootstrap-based algorithm is applied for detection, and the results are summarized below. \n\n|| Probability of detection|Attack instance $\\hat{s}_0$  (mean, 95% CI)|Stopping time $\\hat{T}_0$ (mean, 95% CI)|\n|-|-|-|-|\n| No attack| 0.06 (false positive) |-|-|\n|Label flipping attack| 0.90|58.49, (31.7, 96.25)| 95.67, (89.1, 98.9)|\n\nThe method maintains empirical validity at level $0.05$ and has high detection power under label-flipping attacks. Earlier detection is achievable by tuning the threshold constant $c$ (e.g., via cross-validation), demonstrating the practical applicability of Gaussian-bootstrap algorithms."}, {"review_id": "2rEaJrCJe5", "reviewer": "Reviewer_SopJ", "summary": "In this paper, the authors present two generalized Gaussian approximation results for decentralized federated learning with local updates and explore their theoretical and practical implications. The theoretical development appears solid and technically nontrivial.", "questions": "My major comments are as follows:\n\n1. Motivation \n\nThe authors should elaborate on why traditional convergence analysis (i.e., focusing on optimization error) is not sufficient in modern decentralized learning settings. It is important to explain why the statistical properties investigated in this paper are important. A more thorough discussion connecting statistical properties with optimization and generalization error would greatly benefit readers unfamiliar with this line of work.\n\n2. Choice of Online Setting\n\nThe paper considers an online federated setting, rather than the more common federated learning scenario where each client holds a local dataset. It would be valuable to consider, or at least discuss, how the proposed theoretical results would extend to or differ in the standard offline setting. Additionally, analyzing how sample size, local update number, and total iteration number affect the statistical properties in such settings would be more general and practically meaningful.\n\n3. Clarification on Decentralization\n\nThe paper claims to investigate decentralized federated learning, but repeatedly refers to a ``moderator'' that aggregates client information and redistributes it according to some policy in Sections 2.1 and 2.1.1. This resembles centralized federated learning more than a truly decentralized settings. In typical decentralized Local SGD, messages are shared peer-to-peer over a communication graph.  It should be clearly justified and discussed.\n\n4. Dependence on $\\tau$, Network Topology, data heterogeneity\n\nThe authors mention that the data can be heterogeneous and describe the network topology in Section 2. However, none of the main theoretical results appear to explicitly capture the impact of $\\tau$ (the number of local updates), the network topology, or data heterogeneity. The absence of such dependencies should be discussed.\n\n5. Privacy and Robustness Claims Lack Support\n\nThe authors claim in Section 3 that analyzing the full trajectory of Local SGD can help maintain privacy and detect adversarial attacks. However, I was unable to find any formal results, theoretical justifications, or empirical validations to support these claims. More detailed discussion and supporting experiments are necessary.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "In this paper, the authors present two generalized Gaussian approximation results for decentralized federated learning with local updates and explore their theoretical and practical implications. The theoretical development appears solid and technically nontrivial. However, the paper is somewhat difficult to follow. Many important concepts and theorem statements are introduced without sufficient explanation or discussion, making it challenging for readers who are not already familiar with this specific area to fully grasp the contributions and their implications.", "was_revised": true, "final_justification": "Most of my concerns have been addressed, and I have accordingly raised my score.", "rebuttal": "We are thankful to the reviewer for a detailed perusal as well as the positive comments on the theoretical part. Below, we address your concerns individually. We warmly welcome any further suggestions you may have to improve the paper. Finally, in case you find this rebuttal adequate, we humbly request you to consider increasing your score. \n\n### Weaknesses\n\n***Readability and accessibility***\n\n*Answer*: We sincerely regret that the paper was difficult to follow. Based on this comment, we have substantially revised the paper to include more explanations, implications and remarks to improve clarity. Some of these modifications can be found in our response to the *Weakness*, point 2, by the reviewer *CKRL*.\n   \n### Questions\n\n1. ***Motivation***\n\n*Answer*: We thank the reviewer for this insightful suggestion. Indeed, traditional analyses typically focus on quantities such as $|Y_n-\\theta_K^\\star|$ or $|F(Y_n)-F(\\theta_K^\\star)|$, without addressing statistical properties explicitly. Optimization and generalization error bounds alone are insufficient for developing valid inferential tools. Distributional results like asymptotic normality explicitly quantify the randomness of DFL iterates, thereby enabling uncertainty quantification, confidence procedures, and hypothesis testing. Sensitivity analysis (using ROC curve) is an increasing concern of many federate-learning applications (Schneble and Thamilarasu, [*Attack Detection Using Federated Learning in\nMedical Cyber-Physical Systems*, ICCN, 2021]; Dayan et. al., [*Federated learning for predicting clinical outcomes in patients with COVID-19*, Nature Medicine 2019]). Our results reinforce these statistical motivations. \n\n2. ***Choice of Online Setting***\n\n*Answer*: We are not aware of any central limit theory in offline gradient descent (GD) for e.g. M-estimation, let alone in a federated setting; whereas central limit theory for SGD is classical (Polyak and Juditsky, [*Acceleration of stochastic approximation by averaging*, SIAM Optimization, 1992]). This is because, once you fix the empirical objective, the GD trajectory becomes deterministic, and converges to the empirical minimizer. Therefore, conditional on the offline data, one can only provide an $\\mathcal{L}_2$ bound; marginally (i.e. lifting the condition), the statistical property of the GD iterates mimic that of the empirical minimizer.\n\n Similar argument also holds for the DFL setting. Marginally, the decentralized GD updates $Y_n$ will converge to the maximum likelihood estimate: $\\hat \\theta_{n,K}= \\min_\\theta\\sum_{k=1}^Kw_k n_k^{-1}\\sum_{i=1}^{n_k}f(\\theta,\\xi_i^{(k)})$. Its statistical properties, e.g. CLT, are classically known. The effect of sample size, local update number, and total iteration number, can be characterized in the usual $\\mathcal L_2$ bound $\\mathbb E\\|Y_n-\\hat \\theta_{n,k}\\|^2$, and has indeed been done in the literature (Stich, [*Local SGD converges fast and communicates little*, ICLR 2019]; Khaled et. al., [*Tighter Theory for Local SGD on Identical and Heterogeneous Data*, AISTATS 2020]).\n\n3. ***Clarification on Decentralization***\n\n*Answer*: Our set-up is *decentralized*, where, during the synchronization, the messages are shared over the communication graph $\\mathbf{C}$ (Section 2.1.1, and Assumption 2.1 in the manuscript) peer-to-peer. A \"moderator\" is mentioned only to explain the known weights, and the synchronization systems. We agree that none of them require the presence of a moderator, and have removed this word from the paper.\n\n4. ***Dependence on $\\tau$, Network Topology, data heterogeneity***\n\n*Answer*: In what follows, we provide versions of our results with the explicit constants depending on the number of local updates ($\\tau$) and the network topology ($\\rho$), where $\\rho$ is the second largest eigenvalue of the connection graph $\\mathbf{C}$. \n\n**Generalization of Theorem 2.1.**  \nLet there exist $\\kappa>0$ such that it holds $\\max_\\theta \\sum_{k=1}^Kw_k\\|\\nabla F(\\theta)-\\nabla F_k(\\theta)\\|^4 \\leq\\kappa^4$. As long as $\\tau\\leq\\theta n$, for some $\\theta\\in(0,1)$, under assumptions of Theorem 2.1 in the main draft, it follows that:\n$$\\begin{aligned}\nd_{\\mathrm C}(\\sqrt{n}(\\bar Y_n-\\theta_K^\\star),Z)\\lesssim&(\\kappa\\vee\\kappa^2+1)\\Big(\\sqrt{\\tau}+\\frac{1}{\\sqrt{1-\\rho^{1/\\tau}}}\\Big)(\\frac{1}{\\sqrt{nK}}+n^{\\frac{1}{2}-\\beta} \\sqrt{K}+\\frac{n^{-\\frac{\\beta}{2}}}{\\sqrt{K}}),\n\\end{aligned}$$\nThe data heterogeneity is reflected by the $\\kappa$ parameter. \n\nAs the network topology becomes sparser ($\\rho\\uparrow1$), the GA error scales as $(1-\\rho^{1/\\tau})^{-1/2}$. Additionally, as the number of local updates $\\tau$ increases, the errors increase with a $\\sqrt{\\tau}$ rate. Finally, as the heterogeneity increases, the Berry-Esseen error rates worsens polynomially. Similar results are proved for the time-uniform Gaussian approximations.\n These theoretical intuitions can be verified empirically. In particular, note that the effect of heterogeneity can also be tracked through the effect of $\\gamma$ in the `Frand-eff` model in Section F.1.1 in the supplement. The corresponding simulation results for $\\rho,\\tau$ and $\\kappa$ are as follows.\n\n**Comparison of Berry-Esseen error under step-size $\\eta_t= 0.3t^{-0.75}$, number of clients $K=10$, dimension $d=2$.**\n\n|$\\rho$|$n=100$|$n=200$|$n=300$|\n|-|-|-|-|\n|0.2|0.106|0.107|0.104|\n|0.4|0.136|0.143|0.138|\n|0.6|0.165|0.192|0.175|\n|0.8|0.203|0.245|0.250|\n*Table: For each $\\rho$, $\\mathbf C= \\rho I_K + (1-\\rho)K^{-1}\\mathbf{1}\\mathbf{1}_K$.*\n\n|$\\tau$|$n=100$|$n=200$|$n=300$|\n|-|-|-|-|\n|20|0.118|0.146|0.155|\n|40|0.155|0.183|0.185|\n|60|0.176|0.225|0.220|\n|80|0.176|0.230|0.252|\n|100|0.175|0.241|0.261|\n\n**Table: Here $\n\\mathbf C_{ij} = \\frac{1}{3}  I_{\\,|j - i| \\leq 1}\n$**\n   \n|$\\gamma$|$n=100$|$n=200$|$n=300$|\n|-|-|-|-|\n|1|0.222|0.224|0.154|\n|2|0.258|0.188|0.112|\n|3|0.322|0.322|0.302|\n|4|0.374|0.272|0.232|\n|5|0.542|0.292|0.302|\n\n**Table: Here $\\tau=20$.**\n\n5. ***Privacy and Robustness Claims Lack Support***\n\n*Answer*: A brief mathematical justification is given in Section 3.1, equation (3.1) and (3.2) of the original draft. We elaborate it here.\n\n Assume that at time $t_0$, $\\mathcal K_0$ clients become malicious. This model poisoning can be mathematically described by a change in their local risk functions $F_k,k\\in\\mathcal K_0$, which affects the distribution of the local SGD updates $Y_t$. To identify the time-point $t_0$ sequentially, we examine the widely-used CUSUM statistic $R_{t}:=\\max_{1\\leq s\\leq t}s|\\bar Y_s-\\bar Y_t|$. We expect $R_{t}$ to be large for $t>t_0$ if an attack has altered the mean behavior of iterates. The null distribution (i.e. when no attack takes place) of $R_t$ is usually mathematically intractable, hence hindering valid inference. This necessitates a bootstrap procedure, e.g. leveraging Theorem 3.1, which we illustrate below. Let the type-one-error $\\alpha$, be given.\n    Recall the aggr-GA approximation $Y_{s,1}^G$, and define $\\mathcal G_t=\\sum_{s=1}^tY_{s,1}^G$. Then, with $R_t^G:=\\max_{1\\leq s\\leq t}|\\mathcal G_s-\\frac{s}{t}\\mathcal G_t|,$ it follows from Theorem 3.1 that,\n$n^{-1/2}\\max_{1\\leq t\\leq n}|R_t-R_t^G|\\leq2\\max_{1\\leq t\\leq n}|t\\bar Y_t-t\\theta_K^\\star-\\mathcal G_t|=o_{\\mathbb P}(1).$\nTherefore, if $Q_{1-\\alpha}(X)$ denotes the $(1-\\alpha)$-th quantile of random variable $X$, then for a suitable positive sequence $\\{a_n\\}$,\n$$\\mathbb P(R_t>Q_{1-\\alpha}(R_t^G)+a_n\\text{ for some }t\\in[n])\\leq\\alpha+\\mathbb P(\\max_{1\\leq t \\leq n}|R_t-R_t^G|>a_n)\\to\\alpha,$$\nas long as $n^{-1/2}a_n\\geq c$. Based on this, a bootstrap algorithm follows:\n\n**Algorithm: Attack detection using time-uniform Gaussian bootstrap**\n\n- **Input:** Connection matrix $C$; Synchronization parameter $\\tau$; Loss functions $f_k(\\cdot,\\xi^k),\\ \\xi^k\\sim\\mathcal P_k,\\ k\\in [K]$; weights $w_k, k=1,.., K$; number of iterations $n$; step-sizes $\\eta_t$; Hessian $A$; number of bootstrap samples $B$; covariance matrix $V_K$, level $\\alpha$.\n\n- Let $E_{\\tau}=\\{\\tau,2\\tau,\\dots,L\\tau\\}$, where $L=\\lfloor n/\\tau\\rfloor$. Initialize $t=1$. Stopping time $\\hat{T}_0=1$, attack instance $\\hat s_0=+\\infty$.\n- While $t\\leq n$:\n1. Store the local SGD iterates $Y_t$, and calculate $R_t=\\max_{1\\leq s\\leq t}s|\\bar Y_s-\\bar Y_t|,$ and, $s_t=\\max_{1\\leq s\\leq t}s|\\bar Y_s-\\bar Y_t|.$\n\n2. For $b=1,...,B$:\n       -Draw $Z_t^{(b)}\\sim N(0,V_K)$, and do $Y_{t,1}^{G,(b)}=(I-\\eta_tA)Y_{t-1,1}^{G,(b)}+\\eta_tZ_t^{(b)}K^{-1/2}$\nwith $Y_{0,1}^{G,(b)}=0$.\n       -Calculate $R_t^{G,(b)}=\\max_{1\\leq s\\leq t}|\\bar Y_{s,1}^{G,(b)}-\\bar Y_{t,1}^{G,(b)}|$\n\n3. Compute $\\hat q_{1-\\alpha}(t)\\leftarrow$ sample quantile $(\\{R_t^{G,(b)}\\})$.\n\n4. **Thresholding:** If $R_t>\\hat q_{1-\\alpha}(t)+c\\sqrt{n}$:  \n      $\\hat T_0\\leftarrow t$, $\\hat s_0 \\leftarrow s_{\\hat T_0}$. Stop.  \n   Else, $t\\leftarrow t+1$.\n- **Output:** $\\hat T_0I_\\{\\hat T_0<n\\},$  $s_{\\hat T_0}$\n\nFor a corresponding empirical validation, we consider the `Frand-eff` model in Section F of the paper, and consider an attack at time point $t_0=T/2$ for $K_0=K/2$ many clients, where their corresponding parameters $\\beta_k$ change to $\\beta_k'=\\beta_k+\\mu$. We take $T=500$, $K=10$, $\\tau=20$ and for each setting, the above algorithm is run for $B=500$ bootstrap samples. The empirical power of the described algorithm is reported below, based on $500$ Monte-Carlo simulations.\n\n|$\\mu$|Probability of detection|Attack instance $s_{\\hat T_0}$ (mean, 95% CI)|Stopping time $\\hat T_0$ (mean, 95% CI)|\n|-|-|-|-|\n|0(No attack)|0.046 (False positive)|-|-|                 \n|1|0.966|265.203, (144.05, 309)| 412.49, (345.05, 482)|\n|2|1|249.672, (118.85, 286.575)|356.32, (311.475, 397.525)|\n|3|1|249.572, (94.275, 276)|334.57, (282.95, 367)|\n\nClearly, the more severe an attack (large $\\mu$), the quicker it gets detected, and the attack instance is also estimated with higher precision. Finally, note the algorithm can be modified to perform sequential tests only at synchronization steps, rather than at every iteration $t$."}, {"review_id": "UeioIHZpAZ", "reviewer": "Reviewer_mVKL", "summary": "This paper presents sharp Gaussian approximation results for local SGD in decentralized federated learning (DFL), going beyond standard central limit theory to enable statistical inference with finite sample guarantees. The main contributions are a Berry-Esseen theorem for both the final and Polyak-Ruppert averaged iterates, and two distinct time-uniform Gaussian approximations (Aggr-GA and Client-GA) for the entire trajectory of local SGD updates. The theoretical results are validated through extensive simulations demonstrating improved approximation rates compared to traditional methods and revealing key computation-communication trade-offs.", "questions": "1. How do the approximation rates scale with non-IID data distributions across clients?\n2. What are the computational trade-offs between Aggr-GA and Client-GA in practice?\n3. How robust are the results to violations of the strong convexity assumption?\n4. Could the methods be extended to non-convex settings?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- Strong technical novelty in deriving first Berry-Esseen bounds and time-uniform Gaussian approximations for local SGD\n- Rigorous theoretical analysis with comprehensive proofs\n- Extensive empirical validation of theoretical claims through well-designed experiments\n- Clear distinction from prior work by going beyond central limit theory\n- Direct implications for statistical inference and anomaly detection in DFL\n\nWeaknesses:\n- Limited discussion of computational complexity of the proposed methods\n- Lacks ablation studies comparing different variants of the Gaussian approximations\n- Could benefit from more real-world applications beyond synthetic experiments\n- Synchronization effects could be explored more thoroughly\n- Some assumptions like strong convexity may be restrictive", "was_revised": true, "final_justification": "Thanks to the authors clarification in rebuttal and I keep the same rating for their submission.", "rebuttal": "We sincerely thank the reviewer for detailed comments and encouraging words on our technical novelty, originality and practical applications. We address all of your concerns below. We also gladly welcome any more suggestions to improve this paper. Finally, in the event you no longer have any concerns or queries, we would greatly appreciate if you can consider increasing the score of the paper.\n\n### Weaknesses\n\n1. ***Limited discussion of computational complexity of the proposed methods***\n\n*Answer*:  We address this in our response to comment 2 on your **Question** section.\n\n2. ***Lacks ablation studies comparing different variants of the Gaussian approximations***\n\n *Answer*: To address this important point, we include two more simulation studies as follows. Recall that \n$$\nU_n=\\max_{1\\leq t\\leq n}\\left|\\sum_{s=1}^t(Y_s-\\theta_K^\\star)\\right|,\\quad\nU_n^{\\texttt{Aggr-GA}}=\\max_{1\\leq t\\leq n}\\left|\\sum_{s=1}^tY_{s,1}^G\\right|,\\quad\nU_n^{\\texttt{Client-GA}}=\\max_{1\\leq t\\leq n}\\left|\\sum_{s=1}^tY_{s,2}^G\\right|\n$$\nand $U_n^{\\texttt{f-CLT}}=\\max_{1\\leq t\\leq n}\\left|\\sum_{s=1}^tZ_s\\right|$, where $Z_1,\\ldots,Z_n\\overset{i.i.d.}{\\sim}N(0,\\Sigma)$, $Y_{s,1}^G$ and $Y_{s,2}^G$ are defined as in Theorem 3.1 and 3.2, and $\\Sigma$ is as in Section 2.2.1.\n\nIn the first experiment, we fix $N=500,K=15,\\gamma=1$, and vary $\\tau=5,10,15$. For each setting, we compute the following: \n$$\nQ_{\\texttt{f-CLT}} = \\max_{\\alpha \\in (c,1-c)} \\frac{|q_{1-\\alpha}(U_n)-q_{1-\\alpha}(U_n^{\\texttt{f-CLT}})|}{q_{1-\\alpha}(U_n)},\\ Q_{\\texttt{Aggr-GA}}=\\max_{\\alpha\\in(c,1-c)} \\frac{|q_{1-\\alpha}(U_n) - q_{1-\\alpha}(U_n^{\\texttt{Aggr-GA}})|}{q_{1-\\alpha}(U_n)}, \n$$\nand $$Q_{\\texttt{Client-GA}}=\\max_{\\alpha\\in(c,1-c)}\\frac{|q_{1-\\alpha}(U_n)-q_{1-\\alpha}(U_n^{\\texttt{Client-GA}})|}{q_{1-\\alpha}(U_n)}$$ for a small $c>0$. The following table summarizes the results.\n\n|$\\tau$|$Q_{\\texttt{f-CLT}}$|$Q_{\\texttt{Aggr-GA}}$|$Q_{\\texttt{Client-GA}}$|\n|-|-|-|-|\n|5|1.495|0.214|0.327|\n|10|2.009|0.44|0.53|\n|15|2.476|0.663|0.883|                   \n\nClearly, the efficacy of each Gaussian approximation worsens with increasing $\\tau$; moreover, the two Gaussian approximations proposed, `Aggr-GA` and `Client-GA`, consistently outperform a functional-CLT-based approach, mirroring our results from Section 4.3.\n\nWe also fix $N=500,K=15,\\tau=20$, and vary the heterogeneity parameter $\\gamma=1,5,10$. The results are as follows.\n\n|$\\gamma$|$Q_{\\texttt{f-CLT}}$|$Q_{\\texttt{Aggr-GA}}$|$Q_{\\texttt{Client-GA}}$|\n|-|-|-|-|\n|1|1.047|0.237|0.275|\n|5|2.047|0.605|0.646|\n|10|2.805|0.547|0.782|\nWe again see the worsening performance of the Gaussian approximations with increasing heterogeneity. We believe these two experiments provide a clear ablation study on the empirical performances of our proposed approximations.\n\n3. ***Could benefit from more real-world applications beyond synthetic experiments***\n\n*Answer*: As an application of our time-uniform Gaussian approximation results (Theorem 3.1 and 3.2), we have added a real-world experiment in the paper. We describe this in the following. We work on a federated learning (FL) setup with $K=5$ clients collaboratively training a linear classifier on MNIST data. Let each image be $x_i\\in\\mathbb{R}^{28\\times 28}$. To get rid of high-dimensionality, a PCA transform $P:\\mathbb{R}^{28\\times 28}\\rightarrow\\mathbb{R}^d$ with $d=3$ is fitted on the full training set $z_i=P(x_i)\\in\\mathbb{R}^3$. At time $t$, each client $k\\in[K]$ sequentially receives $\\xi_t^k=(y_t^k,z_t^k)$ where $y_t^k$ are the corresponding digit labels. The loss function of client $k$ is the cross-entropy loss:\n$$\nf_k(W,b;\\xi_t^k)=-y_t^k\\log(\\hat y_t^k)-(1-y_t^k)\\log(1-\\hat y_t^k),\\quad\\hat y_t^k=\\sigma(Wz_t^k+b),\n$$\nwhere $\\sigma$ is the sigmoid/logit function, and $W\\in\\mathbb{R}^{10 \\times 3}$ and $b\\in \\mathbb{R}^{10}$, so the parameter vector $\\theta=\\operatorname{Vec}([W:b])\\in\\mathbb{R}^{d}$ with $d=40.$ The weight parameters for the aggregated objective function are $w_k=K^{-1},\\ k\\in[K]$, and the step-size is $\\eta_t=0.3t^{-0.75}$. The synchronization parameter is $\\tau=5$, and we use the connection matrix $\\mathbf{C}_{ij}=1/3I\\{|j-i|\\leq 1\\}$. Finally, we run the local SGD iterates for $n=100$ iterations.\n\n For a randomly selected set of $K_0=3$ clients, a label-flipping attack (the label of images of digits $1,2,4$ are switched to $7,5,8$, and vice-versa) is injected at $t = 50$. We have described the algorithm (named **Attack detection using time-uniform Gaussian bootstrap**) we employ to detect such attacks at our rebuttal to the **Limitation** section of the reviewer *PXEE*. The results are summarized in the following table.\n\n||Probability of detection|Attack instance $\\hat s_0$ (mean, 95% CI)|Stopping time $\\hat T_0$ (mean, 95% CI)|\n|-|-|-|-|\n|No attack|0.06 (false positive)|-|-|\n|Label flipping attack|0.90|58.49, (31.7, 96.25)|95.67, (89.1, 98.9)|\n\nNote that empirical validity at the $0.05$ level is approximately maintained, and high detection power is achieved under the label-flipping attack. Earlier detection can be obtained by suitably tuning the constant $c$ in the threshold step (e.g., via cross-validation). Overall, these experiments demonstrate the practical applicability of Gaussian-bootstrap-based algorithms.\n\n4. ***Synchronization effects could be explored more thoroughly***\n\n*Answer*: Addressing of your question, we have the following general version of the Theorem 2.1, where we allow the synchronization parameter $\\tau$ to grow linearly with $n$.\n\n**Generalization of Theorem 2.1.**  \n  As long as $\\tau \\leq \\theta n$, for some $\\theta \\in (0,1)$, under the assumptions of Theorem 2.1 in the main manuscript it follows that:\n$$\n   d_{\\mathrm{C}}(\\sqrt{n}(\\bar{Y}_n-\\theta_K^\\star),Z)\\lesssim\\left(\\sqrt{\\tau}+\\frac{1}{\\sqrt{1-\\rho^{1/\\tau}}}\\right)\\left(\\frac{1}{\\sqrt{nK}}+n^{\\frac{1}{2}-\\beta} \\sqrt{K}+\\frac{n^{-\\frac{\\beta}{2}}}{\\sqrt{K}}\\right)\n$$\nClearly, as the number of local updates $\\tau$ increases, the errors increase with a $\\sqrt{\\tau}$ rate. This has also been verified empirically in the following table.\n\n|$\\tau$|$n=100$|$n=200$|$n=300$|\n|-|-|-|-|\n|20|0.118|0.146|0.155|\n|40|0.155|0.183|0.185|\n|60|0.176|0.225|0.220|\n|80|0.176|0.230|0.252|\n|100|0.175|0.241|0.261|\n\n5. ***Some assumptions like strong convexity may be restrictive***\n\n*Answer*: Even though our theoretical results use strong convexity for convenience, in the supplementary Section A.2, we explicitly mention how the strong convexity assumption can be replaced by a much weaker, \"local concordance property\". For example, Logistic regression violates strong convexity but obeys local concordance property.\n\n### Questions\n\n1. ***How do the approximation rates scale with non-IID data distributions across clients?***\n\n*Answer*: We respectfully point out that **our results do not require IID data for each client**. In particular, we mention in **Section 2.1, Preliminaries**:  \n   \n   > \"Here, $\\mathcal{P}_k$ determines the distribution of the local noisy gradient for each client, realized by sampling $\\xi^k\\sim\\mathcal{P}_k$. We allow for heterogeneity among the clients, i.e. $\\mathcal{P}_k$'s are allowed to be different. However, noise sampling (i.e., the $\\xi^k$) is assumed to be independent from one client to another.\" \n\nThat said, if you think we misunderstood your question or further clarifications are required, we would appreciate further comments from you.\n\n2. ***What are the computational trade-offs between Aggr-GA and Client-GA in practice?***\n\n*Answer*:  We thank the reviewer for raising this important point. At each iteration $t$, Aggr-GA has a computational complexity of $O(d^2)$, since it involves generating one random sample followed by a matrix-vector multiplication. But implementing this require complete peer-to-peer sharing. In contrast, Client-GA has a complexity of $O(Kd^2)$ per iteration. However, the structure of Client-GA naturally allows for parallel computation between synchronization steps, significantly reducing the computational burden while preserving periodic, *partial*, peer-to-peer communication.\n\n3. ***How robust are the results to violations of the strong convexity assumption?***\n \n*Answer*: Answered above in response to comment 5 in the **Limitations** section.\n\n4. ***Could the methods be extended to non-convex settings?***\n \n*Answer*: If there are only finitely many local minimas, our techniques along with *local strong convexity* assumption can yield the corresponding results conditional on in-probability convergence. See for example Zhong et. al., [*Online bootstrap inference with non convex stochastic gradient descent estimator*, Preprint 2023]. Unfortunately, for non-convex regimes with uncountably many local minimas, it is unclear what the central limit theory would look like even for vanilla SGD. This indeed represents an exciting research direction, and we believe, despite the significant non-triviality, the techniques developed here should be useful there too."}, {"review_id": "HqbaWygUt5", "reviewer": "Reviewer_6krr", "summary": "This paper studies stochastic gradient descent in the framework of decentralized federated learning, and provides a non-asymptotic versions of the Central limit theorem for the convergence of the model parameter to global optimum. In Section 2, the authors generalize Berry-Essen-type bounds for the last iterate of SGD as well as for the Polyak-Ruppert average to the case of federated learning. The proof of this section are based on the framework of randomized concentration inequalities by [Shao and Zhang, 2022].\n\nIn Section 3, the authors present two ‘time uniform’ approximations of SGD iterates averaged across clients. That is, they show that strong approximations in the form of Gaussian processes with explicit covariance structures depending on the parameters of the optimization problem can be constructed. The authors derive stochastic bounds on the deviation of the original SGD process from these approximations. The authors motivate their studies of ‘time uniform’ approximations by detecting anomalies in the SGD trajectory", "questions": "1. What is the effect of data heterogeneity across different clients in Theorem 2.1? In the current version, I guess, it is completely hidden in the constants, at the same time, it will be very interesting to quantify, how this factor affects the non-asymptotic CLT.", "limitations": "Yes", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "***Strengths***\n\nThe authors obtain novel theoretical results in the federated learning setting. To the best of my knowledge, this is the first time Berry-Eseen type bounds have been proven for the federated learning setup. The considered strong approximation result for SGD training trajectories by a Gaussian process is also novel, to the best of my knowledge.\n\n***Weaknesses***\nTheorem 2.2 in its current form is unclear to me. First, a well-known asymptotic normality results on the last iterate of SGD suggest that one should consider $(\\theta_n - \\theta^\\star) / \\sqrt{\\eta_n}$ in order to have a non-trivial limiting variance. Hence, I guess, there is a normalizing factor $n^{\\beta/2}$ missing in the left-hand side. Second, the claim in lines 208-209:  \"In particular, this rate is slower than the corresponding rate for the Polyak-Ruppert averaged version\" is incorrect - when setting $\\beta = 1$, you have exactly the same rate $1/\\sqrt{n}$. The problem here is not in the rate, rather in the realizability of the corresponding step sizes (in such a case $\\eta_k = c/k$ with some lower bound on the constant $c$, which is instance-dependent). Another issue with the last iterate is that it yields a suboptimal limiting covariance matrix, unlike the Polyak-Ruppert procedure.\n\n***Minor points***\n1. Statements of \"informal\" theorems are too vague, especially the one of theorem 1.1. I would indicate arguments in $d_{Berry-Esseen}$, or at least mention in the statement that the Polyak-Ruppert averaged version of SGD is considered;\n2. There is a clash of notations related to $A$. It is used both for generic matrix in notations, generic convex set in the definition of the convex distance (see eq. (2.3)), at the same time, due to Theorem 2.1, it has a separate meaning (Hessian at the optimum). Please change. \n3. Vectors $g_k$ are intensively used in the statement of theorem 2.1 and below, but are not defined in the main text. From the context I can infer that $g_k (\\theta, \\xi) = \\nabla f_k (\\theta, \\xi)$. Please fix this discrepancy;\n4. Line 188, still statement of Theorem 2.1: \n***assume that $\\max_{k \\in [K]} \\mathbb{E}[|g_k * (\\theta_K^\\star,\\xi)|^2] = \\mathcal{O}(1)$***\nFirst, there is a typo here, you do not need $*$. Second, writing here $\\mathcal{O}(1)$ is very confusing. Please write the assumption you impose formally.\n5. Appendix A, line 989: \"Assumption A.3 is much weaker compared to assumption A2(p) in [Sheshukova, 2025]\" It is not true, Assumption A.3 is exactly assumption A2(p)- (iii) in the mentioned paper. At the same time, assumption A.2 in the current paper is indeed weaker than the a.s. Lipshitzness imposed in A2(p)-(ii) in [Sheshukova, 2025]. \n5. What is $E$ in the line 1054 in appendix? \n6. There is a $\\nabla$ symbol missing in assumption A.2, see line 979\n7. Some constructions are clearly too verbose. As a particular example: line 257, “Hence posing a hindrance to performing” --> why not just \"hindering\"? As I have already mentioned in the weaknesses section, I recommend the authors to re-read the main text carefully and update the ambiguous or verbose phrasing.", "was_revised": true, "final_justification": "The authors did a good job of obtaining, to the best of my knowledge, an original Berry–Esseen bound for the federated SGD setting. The results are sound, and my main concern was related to a number of typos in the presentation. The authors have promised to revise this part and include additional results to quantify the impact of heterogeneity. Given this modification, I continue to support accepting the paper.\n\nJustification for not giving a higher grade: The main results of the paper rely heavily on the [Shao and Zhang, 2022] approach to deriving Berry–Esseen bounds for nonlinear statistics. Thus, the paper does not create a novel tool for the analysis that enables tackling the federated setting, but rather is the first to adopt existing tools from [Shao and Zhang, 2022] to this setting.", "rebuttal": "We sincerely thank the reviewer for the detailed comments, particularly regarding our mathematical results and proofs. We are grateful for your recognition that our paper provides the *first* Berry-Esseen-type bound and strong approximation result for local SGD training trajectories. We warmly welcome any additional suggestions you may have to enhance our manuscript. If our rebuttal adequately addresses your concerns, we kindly request you to consider increasing your score. Now let us address the comments individually.\n\n### Weaknesses\n\n***Theorem 2.2 in its current form is unclear to me....***\n\n*Answer*.  \n- Your observation is indeed correct about the correct scaling factor. It was a typo on our part that we kept the scaling factor $n^{-\\beta}$ multiplied to the variance. We have added the correct version of Theorem 2.2:\n\n**Theorem 2.2**: Under the assumptions of Theorem 2, it holds that\n$$\nd_{\\mathrm C}( n^{\\beta/2}(Y_n - \\theta_K^\\star) , Z)  \\lesssim \\frac{n^{-\\beta/2}}{\\sqrt{K}}  + n^{\\frac{1}{2}-\\beta} \\sqrt{K},\n$$\nwhere $Z \\sim N(0, \\tilde \\Sigma_n)$ with\n$$\n\\tilde \\Sigma_n := n^{\\beta}\\sum_{s=1}^n \\operatorname{Var}\\left(\\mathcal A_s^n \\sum_{k=1}^K \\eta_{s,k}w_k g_k(\\theta_K^\\star, \\xi_s^k)\\right).\n$$\n \n- Regarding the subsequent remark, we mentioned the slower rate since usually we restrict the $\\beta \\in (1/2, 1)$; only in the limiting case of $\\beta=1$ do we have the $n^{-1/2}$ scaling. However, again you are absolutely right in pointing this out, and we have accordingly removed this comment. We are thankful to the reviewer for mentioning the point of suboptimal limiting covariance matrix, which we have added now.\n\n### Minor Comments\n\n1. ***Statements of \"informal\" theorems are too vague, especially the one of theorem 1.1. I would indicate arguments in $d_{Berry-Esseen}$, or at least mention in the statement that the Polyak-Ruppert averaged version of SGD is considered;***\n\n   *Answer*: We provided the informal statements to ease those readers into our paper who may not be entirely familiar into this literature, and we are sorry if we erred on the side of being too vague. In cognizance of your suggestion, we have made the following modifications.\n\n**Theorem 1.1, informal:** For a decentralized federated learning set-up with $K$ clients, the Polyak-Ruppert averaged iterates $\\bar Y_n$ of the local SGD algorithm with $n$ iterations, and step size $\\eta_t \\asymp t^{-\\beta}$, achieves\n   $$\n   \\texttt{Berry-Esseen error}\\lesssim n^{1/2 - \\beta}\\sqrt{K}.\n   $$\n\n   **Theorem 1.2, informal:** If the local SGD algorithm with $K$ clients runs $n$ iterations with step size $\\eta_t \\asymp t^{-\\beta}$, then there exists a Gaussian process $Y_t^G = (I-\\eta_tA) Y_{t-1}^G + \\eta_t Z_t$ with $Z_t$ i.i.d. $N(0,\\Gamma)$ for some matrix $\\Gamma$ and $A$ being the Hessian of the problem, such that for the local SGD iterates $Y_n$, it holds,\n   $$\n   \\max_{1\\leq t \\leq n} \\left| \\sum_{s=1}^t (Y_s - Y_s^G) \\right| \\approx o_{\\mathbb{P}}(n^{1-\\beta} + \\frac{n^{1/p}}{\\sqrt{K}} ),\n   $$\n   where $p\\geq 2$ denotes the maximum number of finite moments the data generating mechanism of each client has.\n\n2. ***There is a clash of notations related to $A$. It is used both for generic matrix in notations, generic convex set in the definition of the convex distance (see eq. (2.3)), at the same time, due to Theorem 2.1, it has a separate meaning (Hessian at the optimum). Please change.***\n\n   *Answer*: We have replaced the $A$ in the notation section by \"for $M \\in \\mathbb{R}^{m\\times n}$, $\\lVert M\\rVert_F$ denotes its Frobenius norm.\" and the $A$ in equation (2.3) by\n   $$\n   d_{\\mathrm C}(Y,Z):= \\sup_{\\aleph \\in \\mathcal B(\\mathbb R^d): A \\text{ convex}} \\left|\\mathbb P(Y \\in \\aleph)- \\mathbb P(Z \\in \\aleph) \\right|.\n   $$\n   This keeps the notation $A$ only reserved for the Hessian. We are sorry for the ambiguity caused.\n\n3. ***Vectors $g_k$ are intensively used in the statement of theorem 2.1 and below, but are not defined in the main text. From the context I can infer that $g_k(\\theta, \\xi) = \\nabla f_k(\\theta, \\xi)$. Please fix this discrepancy..***\n\n   *Answer*: Thanks for catching this. Actually the vectors $g_k$ are mean-zero versions of the noisy gradient (referred to as gradient noise), and are given by $g_k(\\theta, \\xi) = \\nabla F_k(\\theta) - \\nabla f_k(\\theta, \\xi)$. We have clarified this in the statement of the Theorem 2.1, where it were earlier used without definition.\n\n4. ***Line 188, still statement of Theorem 2.1 \"assume that \n$\n\\max_{k \\in [K]} \\mathbb E[|g_k\\star (\\theta^{\\star}_K, \\xi)|^2] = O(1)\n$\" \nFirst, there is a typo here, you do not need a $\\star$. Second, writing here $O(1)$ is very confusing. Please write the assumption you impose formally.***\n\n   *Answer*: We have modified the statement in Theorem 2.1 as follows.\n\n **Theorem 2.1.** Define $\\mathcal A_s^t := \\prod_{j=s+1}^t (I - \\eta_t A)$, $\\mathcal A_t^t = I$, where $A := \\nabla_2 F(\\theta_K^\\star)$ for $t \\in [n]$. Further, for $s \\in [n]$, define the random vectors\n$$\nu_s = \\eta_s \\sum_{k=1}^K w_k \\left( \\sum_{j=s}^n \\mathcal A_s^j \\right) g_k(\\theta_K^\\star, \\xi_s^k),\n$$\nwith\n$$\n\\Sigma_n := n^{-1} \\sum_{s=1}^n \\mathbb E[u_s u_s^\\top], \\quad g_k(\\theta, \\xi^k) = \\nabla F_k(\\theta) - \\nabla f_k(\\theta, \\xi^k).\n$$\n\nLet there exist a constant $C$ such that for $\\xi^k \\sim \\mathcal P_k$, $k \\in [K]$, it holds $\\max_{k \\in [K]} \\mathbb E[|g_k(\\theta_K^\\star, \\xi^k)|^2] \\leq C$. Suppose that the step-size schedules of the clients satisfy $\\eta_t = \\eta_0 (t + k_0)^{-\\beta}$ for some fixed $\\eta_0, k_0 > 0$, and $\\beta \\in (1/2, 1)$. Then, under Assumptions 2.1, A.1, A.2 and A.3 with $p = 4$, and $\\bar Y_n$ as in (2.4), it holds that\n\n$$\nd_{\\mathrm C} \\left( \\sqrt{n} (\\bar Y_n - \\theta_K^\\star),\\; Z \\right) \\lesssim \\frac{1}{\\sqrt{nK}} + n^{\\frac{1}{2} - \\beta} \\sqrt{K} + \\frac{n^{-\\frac{\\beta}{2}}}{\\sqrt{K}},\n$$\n\nwhere $\\lesssim$ hides constants involving $d, \\beta, \\mu, L$ and $\\rho$, and $Z \\sim N(0, \\Sigma_n)$.\n\n5. ***Appendix A, line 989: \"Assumption A.3 is much weaker compared to assumption A2(p) in [Sheshukova, 2025]\" It is not true, Assumption A.3 is exactly assumption A2(p)- (iii) in the mentioned paper. At the same time, assumption A.2 in the current paper is indeed weaker than the a.s. Lipshitzness imposed in A2(p)-(ii) in [Sheshukova, 2025].***\n\n   *Answer*: Again thank you for catching this detail. We indeed meant to write Assumption A.2, and it was a typo which has been corrected. \n\n6. ***What is $E$ in line 1054 in the appendix? It is undefined.***\n\n   *Answer*: It should be $E_{\\tau}=\\{\\tau, 2\\tau, \\ldots\\}$ which is defined in the Algorithm 1 of our manuscript. We have corrected this.\n\n7. ***There is a $\\nabla$ symbol missing in assumption A.2, see line 979***\n\n   *Answer*: Yes, this has been corrected.\n\n8. ***Some constructions are clearly too verbose. As a particular example: line 257, “Hence posing a hindrance to performing” --> why not just \"hindering\"? As I have already mentioned in the weaknesses section, I recommend the authors to re-read the main text carefully and update the ambiguous or verbose phrasing..***\n\n    *Answer*: Thank you again for your careful perusal. Based on this feedback, we have substantially revised the manuscript to make it concise while enhancing clarity and readability. Some of these modifications can be found in our rebuttal to the comment 2 of the **Weakness** section by the reviewer *CKRL*.\n\n\n### Questions\n\n- ***What is the effect of data heterogeneity across different clients in Theorem 2.1? In the current version, I guess, it is completely hidden in the constants, at the same time, it will be very interesting to quantify, how this factor affects the non-asymptotic CLT.***\n\n   *Answer*: Thank you for asking this important question. This has been one of the most common questions that we received, and accordingly we have generalized Theorem 2.1 to reflect the heterogeneity.\n\n   **Generalization of Theorem 2.1.**  \n   Let the heterogeneity parameter $\\kappa>0$ be such that $\\max_\\theta \\sum_{k=1}^K w_k \\|\\nabla F(\\theta) - \\nabla F_k(\\theta)\\|^4 \\leq \\kappa^4$. Then, under the assumptions of Theorem 2.1 in the main manuscript it follows that:\n$$\n   \\begin{aligned}\n   d_{\\mathrm C}( \\sqrt{n}(\\bar Y_n - \\theta_K^\\star) , Z) \\lesssim & (\\kappa \\vee \\kappa^2+1)(\\frac{1}{\\sqrt{nK}}  + n^{\\frac{1}{2}-\\beta} \\sqrt{K} + \\frac{n^{-\\frac{\\beta}{2}}}{\\sqrt{K}}),\n   \\end{aligned}\n$$\nClearly, as the heterogeneity increases, the Berry-Esseen error rates worsens polynomially. Similar results are proved for the time-uniform Gaussian approximations.\n\nThe effect of heterogeneity can also be verified empirically, by noticing that $\\gamma$ plays the role of heterogeneity in the Frand-eff formulation in Section F.1.1 in the supplement. The corresponding simulation results can be seen in the following table:\n\n   |$\\gamma$|$n=100$|$n=200$|$n=300$|\n   |-|-|-|-|\n   |1|0.222|0.224|0.154|\n   |2|0.258|0.188|0.112|\n   |3|0.322|0.322|0.302|\n   |4|0.374|0.272|0.232|\n   |5|0.542|0.292|0.302|\n\n*Table: Berry-Esseen error across different levels of heterogeneity under step-size $\\eta_t= 0.3t^{-0.75}$, number of clients $K=10$, $\\tau=2$, $C_{ij}=1/3 I\\{|j-i|\\leq 1\\}$, dimension $d=2$. All the results are based on 500 Monte-Carlo simulations.*"}, {"review_id": "33Ste75QtP", "reviewer": "Reviewer_CKRL", "summary": "This paper investigates the statistical properties of local SGD in decentralized federated learning (DFL) settings, focusing not only on convergence but also on refined distributional approximations. The authors propose Berry-Esseen bounds for final iterates and develop time-uniform Gaussian approximations to enable inference and adversarial attack detection. Two bootstrap frameworks, Aggr-GA and Client-GA, are introduced, and extensive simulations validate the theoretical results.", "questions": "1.\tAre the results still valid under significant client heterogeneity?\n2.\tAll analysis assumes a fixed step size, can the results extend to adaptive or momentum-based variants, e.g. Adam?", "limitations": "The paper lacks real-world experiments on standard federated learning tasks (e.g., image or text classification).", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1.\tThis paper addresses an important gap in the statistical understanding of local SGD beyond convergence. \n\n2.\tIt provides novel Berry-Esseen bounds and time-uniform Gaussian approximations. The proposed approximations support practical applications such as bootstrap inference and attack detection. Solid empirical validations that match theoretical insights.\n\n3.\tBoth centralized (Aggr-GA) and decentralized (Client-GA) solutions, can balances accuracy and privacy trade-offs. \n\n**Weaknesses:**\n\n1.\tWhile simulations are extensive, real-world experiments (e.g., NLP or vision FL benchmarks) are lacking.\n\n2.\tPresentation could be improved, the notation and organization are occasionally dense and hard to follow.", "was_revised": true, "final_justification": "My main concern lies in the real-world evaluation. While the theoretical contributions are solid and well-motivated, I believe that a more extensive evaluation on real-world benchmarks is necessary to fully demonstrate the practical impact of this work. The additional experiments in the above response are a welcome step in that direction, but their scope remains limited. Therefore, I have decided to maintain my current score.\n\nThat said, I appreciate the theoretical depth of the paper and recognize its potential for future applications. Best wishes for your continued work on this promising line of research.", "rebuttal": "We firstly thank the reviewer for the detailed and encouraging comments on our novelty. We have strived to address each of them in the following. We are happy to provide more explanation if you feel any of your comments is not adequately addressed; we also welcome any other suggestions to help improve the quality of this paper. In case you do not have any other concerns about this manuscript, we would greatly appreciate if you can increase your score. Our rebuttals are as follows.\n\n### Weaknesses\n\n1. ***While simulations are extensive, real-world experiments (e.g., NLP or vision FL benchmarks) are lacking.***\n\n   *Answer*:  \n   We appreciate the reviewer's important question. Our paper is theoretical in nature, and we do not claim to compete with any SOTA algorithm. We provide two novel, sharp, theoretically valid Gaussian approximations. As the reviewer **6krr** pointed out, our work is the first one to establish strong asymptotic guarantees in a decentralized federated learning setting. We believe that our Gaussian approximation results open door for many potential applications in these areas, but they may require developing case-by-case algorithms to be usable; in that regard, we hope that this opens door to an exciting research direction.\n\n   To illustrate our above point, we have added a real-world experiment on one of these applications from the paper, which we describe in the following paragraph. We work on a federated learning (FL) setup with $K = 5$ clients collaboratively training a linear classifier on *MNIST* data. Let each image be $x_i \\in \\mathbb{R}^{28\\times 28}$. To get rid of high-dimensionality, a PCA transform $P: \\mathbb{R}^{28\\times 28} \\rightarrow \\mathbb{R}^d$ with $d = 3$ is fitted on the full training set $z_i = P(x_i) \\in \\mathbb{R}^3$. At time point $t$, each client $k \\in [K]$ sequentially receives $\\xi_t^k=(y_t^k, z_t^k)$ where $y_t^k$ are corresponding digit labels. Following the notation of the paper, the loss function of client $k$ is the *cross-entropy loss*:\n$$\nf_k\\bigl(W, b; \\xi_t^k\\bigr)\n= -\\,y_t^k\\log\\bigl(\\hat y_t^k\\bigr)\n  -\\,(1 - y_t^k)\\log\\bigl(1 - \\hat y_t^k\\bigr),\n\\quad\n\\hat y_t^k = \\sigma\\bigl(W z_t^k + b\\bigr).\n$$\n\nwhere $\\sigma$ is the sigmoid function, $W\\in\\mathbb{R}^{10\\times3}$, $b\\in\\mathbb{R}^{10}$, and hence\n\n$$\n\\theta = \\operatorname{Vec}\\bigl([W : b]\\bigr)\\in\\mathbb{R}^d,\\quad d = 40.\n$$\n The weight parameters for the aggregated objective function are $w_k=K^{-1}, k \\in [K]$, and the step-size is $\\eta_t=0.3 t^{-0.75}$ in conjunction with our empirical exercises. The synchronization parameter is $\\tau=5$, and we use the connection matrix from the simulation: $C_{ij}=1/3 I\\{|j-i|\\leq 1\\}$. Finally, we run the local SGD iterates for $n=100$ iterations.\n\n   For a randomly selected set of $K_0=3$ clients, a *label-flipping attack* (labels of images of digits $1, 2, 4$ are switched to $7,5,8$, and vice-versa) is injected at $t = 50$, and the following Gaussian bootstrap algorithm is employed to detect this attack.\n\n**Algorithm: Attack detection using time-uniform Gaussian bootstrap**\n\n- **Input:** Connection matrix $C$; Synchronization parameter $\\tau$; Loss functions $f_k(\\theta, \\xi^k)$, $\\xi^k \\sim P_k, k \\in [K]$; weights $w_k$; number of iterations $n$; step-size schedules $\\eta_{t}$; Hessian $A$; number of bootstrap samples $B$; covariance matrix $V_K$. Type-1 error level $\\alpha$. \n-  Initialize $t = 1$. Stopping time $\\hat{T}_0 = 1$, estimated attack instance $\\hat{s}_0 = +\\infty$.\n- While $t \\leq n$:\n1. Store the local SGD iterates $Y_t$, and calculate\n   $$ R_t = \\max_{1 \\le s\\le t} s\\bigl|\\bar Y_s-\\bar Y_t\\bigr|\n     ,\\quad\n     s_t = \\max_{1 \\le s\\le t} s\\bigl|\\bar Y_s-\\bar Y_t\\bigr|.$$\n2. For $b = 1,\\dots,B$:\n   - Draw $Z_t^{(b)} \\sim \\mathcal N(0, V_K)$, and set\n     $$Y_{t,1}^{G,(b)}\n       = (I - \\eta_t A)\\,Y_{t-1,1}^{G,(b)} + \\eta_t\\,Z_t^{(b)}\\,K^{-1/2},\n       \\quad\n       Y_{0,1}^{G,(b)} = 0.$$\n   - Calculate\n     $$R_t^{G,(b)}=\\max_{1 \\le s\\le t}s\\bigl|\\bar Y_{s,1}^{G,(b)} - \\bar Y_{t,1}^{G,(b)}\\bigr|.$$\n3. Compute\n   $\\hat q_{1-\\alpha}(t)$ = sample‑quantile $(R_t^{G,(b)})_{b=1}^B.$\n \n4. **Thresholding:**  \n   If\n   $$R_t > \\hat q_{1-\\alpha}(t) + c\\,\\sqrt n$$\n   then set $\\hat T_0 = t$, $\\hat s_0 = s_{\\hat T_0}$ and **stop**,  \n   otherwise $t\\leftarrow t+1$.\n\n- Output:\n$$\\hat T_0 I_{\\{\\hat T_0 < n\\}}\\; s_{\\hat T_0}.$$\n\nThe matrices $A$ and $V_K$ are inputs to this algorithm, and are therefore estimated by a pre-training/warm-start transient phase. The results are summarized in the following table.\n\n   |                      | Probability of detection   | Attack instance $\\hat{s}_0$  (mean, 95% CI)     | Stopping time $\\hat{T}_0$ (mean, 95% CI) |\n   |----------------------|---------------------------|--------------------------------------------------|-------------------------------------------|\n   | No attack            | 0.06 (false positive detection) | -                                   | -                                         |\n   | Label flipping attack| 0.90                      | 58.49, (31.7, 96.25)                           | 95.67, (89.1, 98.9)                       |\n\n   We note that the empirical validity under level $0.05$ is approximately maintained, and the algorithm also achieves high detection power under the label-flipping attack. We remark that the detection can be made earlier by tuning the constant $c$ in the thresholding step appropriately by e.g. cross-validation, but overall this experiment shows the applicability of such Gaussian-bootstrap based algorithms in practical scenarios.\n\n2. ***Presentation could be improved, the notation and organization are occasionally dense and hard to follow.***\n\n   *Answer*: We sincerely regret that the paper was hard to follow. Our paper presents novel Gaussian approximation results, and so we want to retain their full mathematical statements with all the notations, for the readers more familiar with the literature. However, to improve readability for a broader audience, we have taken the following steps:\n   - **Informal Statements**. We present two “Informal Theorems” (Theorems 1.1 and 1.2) early in the paper, which summarizes the key contributions without notational obscurity. This gives non-technical readers immediate intuition before encountering the full statements.\n   - **Notations and Organization** We have added additional comments to re-introduce/explain many notations/contexts whenever they are used. For example, at the start of Section 2.2.1., we have modified:\n   \n   > ``In Theorem 2.1, the ```local SGD``` updates are scaled by the **covariance matrix** $\\Sigma_n$, which is not usually known or estimable.''\n\nThe statement of the Theorem 3.2 is also modified.\n\n> ``Recall the client-wise gradient noise $W_k$ from Theorem 3.1. Under the assumptions of Theorem 3.1....''\n\nOn the organizational front, we have added a new Section before Section 2, named ``Gaussian approximations in DFL: An introduction'' that serves as an extension of Section 1.1., providing mild introduction to our set-up, and explaining key assumptions, and implications of our results, in terminologies aimed at a broader audience. We hope that these changes enhance clarity and presentation adequately for a general audience. \n\n### Questions\n\n1. ***Are the results still valid under significant client heterogeneity?***\n\n   *Answer*: Yes, the results are valid even under client heterogeneity. As an example, we show the following generalized version of our Theorem 2.1 and verify it empirically. \n\n   **Generalization of Theorem 2.1.**  \n   Let the heterogeneity parameter $\\kappa$ be such that $\\max_\\theta \\sum_{k=1}^K w_k \\|\\nabla F(\\theta) - \\nabla F_k(\\theta)\\|^4 \\leq \\kappa^4$ for some $\\kappa \\geq 0$. Then, under the assumptions of Theorem 2.1 in the main manuscript it follows that:\n$$\n   d_{\\mathrm{C}}( \\sqrt{n}(\\bar{Y}_n - \\theta_K^\\star) , Z)\n   \\lesssim\n   (\\kappa \\vee \\kappa^2+1)\\left(\\frac{1}{\\sqrt{nK}}  + n^{\\frac{1}{2}-\\beta} \\sqrt{K} + \\frac{n^{-\\frac{\\beta}{2}}}{\\sqrt{K}}\\right),\n$$\nClearly, as the heterogeneity increases, the Berry-Esseen error rates worsens polynomially. Similar results are proved for the time-uniform Gaussian approximations. The effect of $\\kappa$ can also be verified empirically, by noticing that $\\gamma$ plays the role of heterogeneity in the ```Frand-eff``` formulation in Section F.1.1 in the supplement. The corresponding simulation results can be seen in the following.\n\n   | $\\gamma$ | $n=100$ | $n=200$ | $n=300$ |\n   |----------|---------|---------|---------|\n   | 1        | 0.222   | 0.224   | 0.154   |\n   | 2        | 0.258   | 0.188   | 0.112   |\n   | 3        | 0.322   | 0.322   | 0.302   |\n   | 4        | 0.374   | 0.272   | 0.232   |\n   | 5        | 0.542   | 0.292   | 0.302   |\n\n   *Table: Berry-Esseen error across different levels of heterogeneity under step-size $\\eta_t=0.3t^{-0.75}$, number of clients $K=10$, $\\tau=2$, $C_{ij}=1/3 I_{|j-i|\\leq 1\\}$, dimension $d=2$.*\n\n2. ***All analysis assumes a fixed step size, can the results extend to adaptive or momentum-based variants, e.g. Adam?***\n\n   *Answer*: We respectfully point out that even $\\mathcal L_2$ or in probability convergence properties for ADAM is not known; can in fact fail to converge, (Reddi et. al., [*On the Convergence of Adam and Beyond*, ICLR 2018]). Therefore, we think existence of valid Gaussian approximation, or even a central limit theory is much harder to prove, and is heavily conditional on some proof of in-probability convergence of ADAM iterates. However, the proof techniques here give us confidence that it can be extended, albeit non-trivially, to allow for some adaptive momentum-based variants that already have provable convergence guarantee along with almost sure bounds on gradients.\n\n### Limitations\n\n***The paper lacks real-world experiments on standard FL tasks (e.g., image or text classification).***\n\n*Answer*:  Answered above in our response to comment 1 of the **Weakness** section"}]

Author rebuttal:

Meta-review: This paper proposes two generalized Gaussian approximation methods for local SGD in decentralized federated learning. The authors derive Berry-Esseen bounds for the final local SGD iterates, enabling valid multiplier bootstrap procedures. They also provide two sharp time-uniform Gaussian approximations over the local SGD trajectory. The proposed asymptotic statistical guarantees for local SGD in decentralized federated learning are potentially impactful, the elaboration of the theoretical results is sufficient and intuitive, and the effectiveness of the proposed approximations are well justified. Although the analytical tools are originated from [Shao and Zhang, 2022], the application in decentralized federated learning is novel and the contributions are sufficient. For these reasons, I recommend Accept.

The authors are encouraged to incorporate the reviewers’ comments and polish the presentation during preparing the final version.
Decision: Accept (spotlight)