arXiv CSopen access

Statistical Limits and Efficient Algorithms for Differentially Private Federated Learning

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

machine learning, deep learning, neural networks

Statistical Limits and Efficient Algorithms for Differentially Private Federated Learning Xiangni Peng Subhadeep Paul Department of Statistics The Ohio State University

arXiv:2605.18656v1 [stat.ML] 18 May 2026

Arnab Auddy

Abstract Federated Learning is a leading framework for training ML and AI models collaboratively across numerous user devices or databases. We study the trade-offs among estimation accuracy, privacy constraints, and communication cost for differentially private (DP) federated M estimation. The two standard methods in the literature are FedAvg, which may suffer from high federation bias, and FedSGD, which can incur high communication cost. Aimed at improving accuracy at a reduced communication cost, we propose FedHybrid, which uses FedSGD starting with an improved initialization by the FedAvg estimator. We propose FedNewton, which averages local Newton iterations to reduce bias in FedAvg, achieving an estimation accuracy comparable to FedSGD with much fewer communication rounds when the number of clients grows sufficiently slowly. We establish finite sample upper bounds on the mean-squared error rates of the DP versions of these estimators as functions of the number of clients, local sample sizes, privacy budget, and number of iterations. We further derive a minimax lower bound on the MSE of any iterative private federated procedure that provides a benchmark to assess the optimality gap of these methods. We numerically evaluate our methods for training a logistic regression and a neural network on the computer vision datasets MNIST and CIFAR-10.

Keywords: Federated Learning, M-estimators, Deep Learning, Differential Privacy, µ-GDP Privacy, MSE Bounds, Minimax Lower Bound.

Introduction

Federated Learning (FL) is a machine learning technique in which multiple client devices collaboratively train a model without sharing raw data with a central server [McMahan et al., 2017a, Kairouz and McMahan, 2021]. The data typically resides on numerous client devices (e.g., mobile or wearable devices) or in client databases (e.g., hospital or financial institution databases) and cannot be sent to a central server due to user privacy or data ownership concerns. Recently, some AI systems promise to deliver AI tools to users that are trained on user data without requiring the data to leave the user’s device [Apple, 2024]. The key tools for accomplishing this ambitious goal are privacy-preserving FL [Paulik et al., 2021]. Moreover, FL has also gained prominence recently as a possible solution to train AI and ML systems while complying with regulations that prevent data sharing, e.g., the European Union’s General Data Protection Reg-

ulations (GDPR) [Brauneck et al., 2023]. In addition to protecting privacy, FL can also reduce costs associated with moving and storing data in centralized cloud servers [Noble et al., 2022]. Two foundational methods in FL are Federated Stochastic Gradient Descent (FedSGD) and Federated Averaging (FedAvg) [McMahan et al., 2017a]. In FedAvg, the central server aggregates (for example, by taking a weighted average) local model updates from clients, often communicating only occasionally after multiple rounds of local client computations. In FedSGD, in each round, each client computes the gradient from its local data and sends it to the server, which then updates the global model pooling these local gradients, requiring communication in every round. Many federated optimization methods such as FedProx [Li et al., 2020], SCAFFOLD [Karimireddy et al., 2020], FedPAQ [Reisizadeh et al., 2020], and adaptive federated optimization methods, such as FedAdagrad, FedAdam, and FedYogi [Reddi et al., 2020] can be viewed as methods built on FedAvg and FedSGD. A major concern in all of the above methods is guaranteeing user privacy. Although FL does not directly share raw data, it does not automatically guarantee privacy, as information may still be leaked through gradients, model updates, or other summaries sent by the clients [Geiping et al., 2020, Wei et al., 2020, Geyer et al., 2017]. Differential privacy (DP) provides a framework for sharing functions of data (i.e., statistics) while preserving the privacy of individual users [Dwork, 2008, Dong et al., 2022, Cai et al., 2021]. Several works study differentially private federated learning from the optimization viewpoint [McMahan et al., 2017b, Kato et al., 2024, Kairouz et al., 2021]. Ensuring privacy necessitates the introduction of randomization, and these works study the effect of this randomization on optimization behavior. A second major concern in federated learning is communication cost. It is quite common for iterative procedures to be used in FL, where the server and the clients exchange model information repeatedly. This cost can become very large for exchanging large parameter and gradient vectors, such as those in deep neural networks. Several papers therefore study communicationefficient federated learning. In homogeneous settings, communication can be reduced by local updates, periodic averaging, quantization, double compression, and less frequent communication with the central server [McMahan et al., 2017a, Konečnỳ et al., 2016, Stich, 2018, Reisizadeh et al., 2020, Spiridonoff et al., 2021, Gao et al., 2021]. We note that the two concerns of privacy and communication are closely related, and Noble et al. [2022], Zhang et al. [2022] show that privacy, clipping, and communication cost need to be understood jointly. Despite enormous interest in FL in recent years and the proliferation of methods as described above, key challenges remain unresolved, especially in terms of statistical theory. The first challenge is to theoretically understand the performance and estimation error rates of FL methods, especially when there are a large number of clients, each with a small amount of data. In particular, how to effectively reduce the bias of Federated averaging to boost the accuracy of parameter estimation in this scenario. The second one is to design methods that effectively preserve the privacy of the users and understand how privacy impacts estimation accuracy. Overcoming these challenges is the goal of the current work. Our contribution in this paper is twofold. Firstly, we connect private federated learning with statistical estimation theory by deriving finite-sample mean squared error bounds for the parameter estimation error of private federated algorithms. We study how privacy noise and communication rounds affect statistical accuracy. This leads to guarantees that are meaningful 2

for practical use. We consider several methods for private Federated Learning of M-estimators using noise-added gradient descent [Bassily et al., 2014, Avella-Medina et al., 2023, McMahan et al., 2017a] and provide MSE upper bounds for them. All of these methods are based on variants of noisy gradient descent or noisy Newton iterations, where a Gaussian noise is added in each iteration of the gradient descent algorithm. The methods vary in terms of the extent of communication between the server and clients. We further prove a lower bound over the MSE of any Private Federated Learning method, to understand the optimality gaps of the methods. Our second contribution is to propose two new methods FedHybrid and FedNewton. Recall that in FedSGD, (we consider only the non-stochastic version of it for theoretical results), the gradient descent steps are all performed by the server aggregating gradients from the clients. Clearly, this method has a high communication cost of O(mdK), where m is the number of clients, d is the dimension of the parameters, and K is the number of gradient iterations, and is identical to the number of rounds of communication for this method. Our first novel estimator, FedHybrid, is a hybrid between FedSGD and FedAvg. This method differs from FedSGD in terms of its initialization. While the server starts from an arbitrary initial value in FedSGD, in our FedHybrid, we run FedAvg with 1 round of communication (R = 1) consisting of K1 local training iterations at each client to obtain an initial value. The warm start from FedAvg allows this algorithm to run K2 gradient communication rounds, where K2 ≪ K. This method has a lower communication cost of O(mdK2 ) than FedSGD and theoretically achieves higher accuracy than communication cost-efficient FedAvg. Therefore, this method represents a middle ground in terms of communication cost and accuracy tradeoff. Our second proposal is the FedNewton method, which consists of FedAvg followed by 1 Newton iteration locally at the clients and aggregation of the updated parameters at the clients. This method is designed to mitigate the bias from FedAvg in a communication-efficient way. We theoretically prove that this method achieves comparable MSE to FedSGD with much less communication cost, provided the number of clients grows sufficiently slowly as the total sample size increases. The FedNewton estimator is related to the FedFisher in Jhunjhunwala et al. [2024], however, unlike FedFisher, we do not need to communicate the Hessian matrix or an approximation of it to the central server and therefore is more communication efficient. Our estimators are derived, and their properties studied, under federated µ-GDP guarantees, which use the Gaussian differential privacy framework of Dong et al. [2022] on data distributed across m clients. This allows us to protect data privacy not only against a third party, but also towards the server, which is the so-called “honest but curious” server scheme of FL [Noble et al., 2022]. Under such a setting, with strong convexity and other assumptions standard in the M -estimation literature, we derive the following rates for the mean squared error of federated M -estimators: md2 L(d, N, µ) d 2 + 2 2 inf sup E∥θ̂ − θ∥ ≍ N N µ log(1/µ) θ̂ θ,Pθ ∈P where N is the total sample size, L(d, N, µ) is a factor of order at most O(log(d) log(N d) log(1/µ)). For ease of presentation, in the above, we assume that N samples are distributed evenly across m clients. More general cases of uneven sample size distributions can be found in later sections. The above bound builds on an MSE lower bound over the class of all possible µfederated GDP estimators. On the other hand, the near-optimal upper bound is attained by the 3

FedSGD, FedHybrid, and FedNewton. With the above guarantees of statistical accuracy, we now turn to the communication rounds required across the different methods. Note that the number of client-server communication rounds coincides with the number of gradient iterations (K) for FedSGD, and with the warmstarted gradient iterations (K2 ) for FedHybrid. The next table makes this comparison explicit in terms of m and N . method Communication Rounds MSE

FedSGD

FedHybrid

FedAvg

FedNewton

Ω(log N )

Ω(log m)

near optimal

sub optimal

near optimal

In contrast to FedSGD, FedHybrid, and 2FedNewton, we show that the FedAvg suffers from fedd m d2 mKd2 eration bias and has an MSE of O N + N 2 + µ2 N 2 , which is worse compared to FedSGD and for d, µ = O(1), away from the lower bound if m ≫ N 1/2 , i.e., when we have a large number of clients each holding relatively small amount of data. Both the new proposed methods FedHybrid and FedNewton achieve error rates comparable to FedSGD, and within log n factor of the optimal rate. While FedSGD and FedHybrid are communication-heavy, they do not impose any restriction on the number of clients. In contrast, the near optimality of FedNewton estimator is contingent on the number of clients satisfying m ≪ N 2/3 , which is a condition weaker than that imposed by FedAvg. We evaluate the finite sample performance of our methods using two simulation studies, corresponding to Poisson and Logistic regression models, respectively. In both settings, the results show that the MSE decreases as either the number of clients or the local client sample sizes increases. Further, we see that as the number of iterations increases, while the MSE decreases at first, it goes up with a higher number of iterations due to the privacy-accuracy tradeoff. Finally, when the number of clients increases without increasing the total sample size, the performance of FedAvg deteriorates significantly, while the new FedNewton provides excellent protection against this decline. We apply our methods to the benchmark MNIST and CIFAR10 image datasets using binary and multi-class logistic regression models, as well as for training Convolution Neural Networks (CNN). For FedNewton applying Newton iteration on the entire set of parameters of a CNN model maybe unstable. We therefore propose to apply the Newton iteration only to the last fully connected layer of the CNN, leaving the convolution layers unchanged during the Newton iteration. For CNN training, we also devise an iterated version of the FedNewton method. We compare the methods in terms of test accuracy using CNN for the MNIST and CIFAR10 datasets. Our work is closely related to a growing body of theoretical results in federated learning. Firstly, there are earlier works that focus on optimization convergence rather than statistical estimation accuracy. These works mainly analyze convergence rates, optimization error, and the trade-off between communication and optimization accuracy [Haddadpour and Mahdavi, 2019, Li et al., 2019, Stich, 2018, Reddi et al., 2020, Qu et al., 2020, Gao et al., 2021, Wei et al., 2020]. For example, Karimireddy et al. [2020] analyzes FedAvg under heterogeneous data and proposes

SCAFFOLD to correct client drift, providing a convergence rate. Moreover, this framework is extended to the private setting in Noble et al. [2022], who analyze the privacy-utility trade-off through convergence bounds. In both works, the main theoretical results are expressed in terms of optimization error rather than parameter estimation error. As shown in Avella-Medina et al. [2023], bounds on objective sub-optimality do not directly control parameter estimation error, which is not sufficient for statistical inference. There is also a distributed inference literature focusing on estimation accuracy for Mestimators. For example, Zhang et al. [2013] showed that distributed averaging of M-estimators can achieve comparable estimation accuracy to centralized estimation under regularity conditions. Huang and Huo [2019] further discusses that adding one Newton update at the central server (one-step-estimation) allows the aggregated distributed estimator to achieve the same asymptotic behavior as the centralized estimator. Communication-efficient distributed statistical inference methods using surrogate likelihood were studied in [Duan et al., 2022, Jordan et al., 2019]. Further, Gu and Chen [2023, 2024] considered heterogeneous and decentralized distributed statistical inference. However, these works do not study the properties of gradient descent iterations that are typically employed in modern federated learning, nor do they consider the impact of privacy noise. In contrast, our work considers privacy, analyzes the relationship between privacy, accuracy, communication cost, and the number of gradient iterations for FL methods, and provides a lower bound to benchmark accuracy against. Finally, our contribution is related to the recent works on distributed statistical learning under differential privacy requirements. See, for example, the results on nonparametric distributed learning in Cai et al. [2024], Auddy et al. [2024], Xue et al. [2024]. Our work contributes to this literature by characterizing the cost of distributed privacy requirements in parametric large-dimensional M -estimation problems, while also proposing methods that reduce the communication requirements.

Background and notations

In this section, we present the basic settings and notations under which we develop our privacypreserving federated M-estimators. Suppose there are m clients where client i possesses local (i) dataset {Xj }, j = 1, . . . , n with i.i.d. samples from distribution F . We denote ni as the local P sample size for client i, so that the total sample size is N = m i=1 ni . It will also be convenient to denote the average sample size as n = N/m. Let {ρ(x; θ) : θ ∈ Θ ⊂ Rd } be a family of loss functions. Then our objective is to estimate θ0 = arg min E[ρ(X, θ)], θ∈Θ

where θ0 is assumed to be unique,

without having the data sent to a central server and protectingthe privacy of users. The following notations are used throughout the following sections. The local empirical loss P i P (i) ρ(xj , θ), and the global loss is L(θ) = N1 m for each client i is Li (θ) = n1i nj=1 i=1 ni Li (θ). Accordingly we denote θ̂i as the minimizer of the local empirical loss, θ̂i = arg minθ∈Θ Li (θ). This estimator is widely known as the M -estimator or the empirical risk minimization estimator. P ni Let us denote the first-order derivatives of the global loss as L̇(θ) = ∇L(θ) = m i=1 N ∇Li (θ). The corresponding first-order derivatives of the local loss are denoted as L̇i (θ) = ∇Li (θ). The

derivatives of the expected loss function are denoted as, L̇0 (θ) = ∇L0 (θ). The expectation of the global loss is denoted as L0 (θ) = E[ρ(X, θ)]. As stated before, our objective is to estimate the unique global minimizer of this expected loss function.

2.1

Assumptions

Before introducing our estimators and stating our theoretical results, we introduce the necessary assumptions. Similar assumptions can be found in previous work on M-estimation, see, e.g., Avella-Medina et al. [2023]. Assumption 1. The parameter space Θ ⊂ Rd is a compact and convex set. Assumption 2. The expectation of the loss function ρ(x; θ) is τ1 -strongly convex in θ, i.e., E(∇2 ρ(x, θ)) ⪰ τ1 Id

for all θ.

Assumption 3 (sub-Gaussian Gradient and Hessian). There exist constants C1 , C2 > 0 such that P v⊤ (∇ρ(X, θ) − E[∇ρ(X, θ)]) ≥ t ≤ exp(−t2 /C12 ). P v⊤ (∇2 ρ(X, θ) − E[∇2 ρ(X, θ)])v ≥ t ≤ exp(−t2 /C22 ). for any fixed θ ∈ Θ and v with ∥v∥= 1. Assumption 4 (Smoothness). There exists positive constants W and τ2 such that for all θ, θ′ ∈ Θ and x ∈ X : ∥∇2 ρ(x, θ) − ∇2 ρ(x, θ′ )∥≤ W ∥θ − θ′ ∥,

2.2

∥∇2 ρ(x, θ)∥≤ τ2 .

Differential Privacy

We will use the following notion of µ- Gaussian Differential Privacy from Dong et al. [2022]. Definition 2.1 (Central Gaussian Differential Privacy). For any n ∈ N, let Dn∗ denote the space ∗ that differ in exactly one datum. A of all datasets of size n. Consider two datasets D, D′ ∈ DN mechanism M is said to be µ-Gaussian differentially private (µ-GDP) if T (α, M ((D), M (D′ )|D, D′ ) ≥ Φ(Φ−1 (1 − α) − µ)

for all α ∈ (0, 1]

where Φ(·) is the standard Gaussian cdf, and for two random variates X ∼ P and Y ∼ Q T (α, X, Y ) = inf{1 − EQ (ϕ) : EP (ϕ) ≤ α} and the infimum is over all possible measurable rejection rules 0 ≤ ϕ ≤ 1. Definition 2.2 (Federated Gaussian Differential Privacy). For any n ∈ N, let Dn∗ denote the space of all datasets of size n. Consider datasets {Ds , Ds′ ∈ Dn∗ s : 1 ≤ s ≤ m} where for each s, Ds and Ds′ differ in exactly one datum.

A mechanism M is said to be µ-federated Gaussian differentially private (µ-fed-GDP) if T (α, M (Ds ), M (Ds′ )|{Dj , Dj′ : j ̸= s}) ≥ Φ(Φ−1 (1 − α) − µ)

for all α ∈ (0, 1] and 1 ≤ s ≤ m

where Φ and T are as defined in Definition 2.1. Our choice of GDP and fed-GDP as our preferred frameworks for differential privacy are motivated by their exact privacy accounting for the Gaussian mechanism, which adds Gaussian noise calibrated to the global sensitivity of the estimators. For completeness, we state the related ideas in the appendix.

Proposed Methods and Theoretical Results

In this section, we analyze four methods for estimating M-estimators under the Gaussian mechanism of privacy. As discussed in the introduction, these methods are: 1. a K-iteration server-side private gradient descent M-estimator similar to FedSGD; 2. a R round federated averaging M-estimator with client-level privacy FedAvg; 3. a new K1 -local and K2 -server private federated M-estimator, FedHybrid; 4. a one local Newton iteration improvement for FedAvg that we call FedNewton. All of these algorithms are variants of noisy gradient descent (or Newton iteration) where Gaussian privacy noise is added to gradient (or Newton) iterations. All of these algorithms aim to approximate the same population M-estimator, but differ in how local updates, communication, and privacy noise are incorporated across clients and the central server. These design differences allow us to study the trade-offs between statistical efficiency and privacy protection in federated settings. In what follows, to make the methods comparable to each other, we constrain that all methods must maintain that client updates are µ-fed GDP, as defined in Definition 2.2. We operate under the “honest but curious” server scheme of FL [Noble et al., 2022], where the clients need to ensure privacy of their users not only from a malicious third party observing the server’s model outputs, but also from the server itself. Therefore, the functions of data (parameter estimates, gradients, etc.) that the clients send to the server need to be privatized under the µ-fed GDP framework. Following previous work in Noble et al. [2022], Wei et al. [2020], we distinguish between two types of privacy notions. First, we provide a privacy guarantee for the clients towards an external third party who can only view the aggregated model updates released by the server, and not the client updates. The second notion of privacy is to the honest but curious server who can observe all the privatized local client updates. These two notions are formalized by Definition 2.1 and Definition 2.2, respectively.

3.1

Server Gradient Descent FedSGD

In the first algorithm, which we refer to as FedSGD (displayed in Algorithm 1), the bulk of the computation is carried out on the server. In particular, the server runs K gradient descent 7

Algorithm 1: K-Iteration FedSGD Input: Data {X (i) }m i=1 with local client sample sizes {ni }; step size η; iters K; privacy parameter µ >P 0; initialization θ(0) ; loss function ρ(·, θ); weight vector {w ∈ [0, 1]m : i wi = 1}; clipping bound B. Output: θ(K) P Set g(x, θ) = ∇ρ(x, θ), N = m i=1 ni . √ 2B K Noise: σi = . µni for k = 0, . . . , K − 1 do for each client i = 1, . . . , m do ni 1 X (k) (i) (k) (k) gi = g(xj , θ(k) ), g̃i = gi + σi Zik , Zik ∼ N (0, Id ). ni j=1 (k) Send g̃i to server. m X (k) g̃ (k) = wi g̃i , θ(k+1) = θ(k) − η g̃ (k) . i=1 Broadcast θ(k+1) .

Return θ(K) .

iterations starting from an arbitrary initializer θ(0) . At each iteration, every client provides a privatized gradient by computing its local gradient and perturbing it with Gaussian noise calibrated to the privacy parameter. These privatized gradients are then sent to the server, where they are aggregated using a weighted average to form a global gradient estimate. The server updates the global parameter using this aggregated gradient and learning rate η and broadcasts the updated parameter back to all clients. The current iteration ends with this broadcast step, and the next iteration begins. This algorithm is closely related to centralized gradient descent, with the key difference being that privacy noise is added at the client level before aggregation. This design mimics our “honest but curious” server assumption, where the clients (e.g., mobile devices, hospitals, financial institutions) need to ensure the privacy of their users by privatizing gradients that they communicate to the server. √ The next Lemma shows that if the scaling for the Gaussian noise is set to 2BµniK , then Algorithm 1 is µ-fed-GDP as defined in Definition 2.2. Lemma 3.1. (Privacy guarantee for FedSGD) With the scaling of the Gaussian noise at the ith √ 2B K client set as µni , the FedSGD algorithm is µ-fed-GDP in the sense of Definition 2.2 and the √ full Algorithm 1 is µ/ m−GDP towards a third party in the sense of Definition 2.1. The next theorem is our main result for Algorithm 1, which provides a finite sample bound on the MSE of the parameter estimate. (K)

Theorem 3.2 (Error Bound of FedSGD). Suppose Assumptions 1-4 above hold. Let θ(AG1) be 9 the output of Algorithm 1 with K iterations initialized at θ(0) and learning rate 2τ12 ≤ η ≤ 10τ . 2

√ Then with B = CB d ∨ log N for a constant CB > 0, we have the bound E

2 (K) θ(AG1) − θ0

τ1 ≤ 3 1− 3τ2

E∥θ(0) − θ0 ∥2

  2 m m 2 C 2 Kd(d ∨ log N ) X 2 X η 4 w i  B η 2 E + (1) wi L̇i (θ0 ) + (1 − γ1 )2 µ2 n2i i=1

i=1

q N where γ1 = 1 + C d∨log − ητ 1 . In particular, if nmin ≥ Cd for some constant C > 0 and nmin √ K = 2 log(dN )/log(3τ2 /(3τ2 − τ1 )) iterations and any θ(0) satisfying ∥θ(0) ∥= O( d), the mean (K) squared error of estimating θ0 by θ̂(AG1) = θ(AG1) satisfies E

θ̂(AG1) − θ0

m X trace(Σ)

17 ≤ 2 τ1

i=1

2C 2 d(d ∨ log N ) log(dN ) + 2B 2 µ ni log(3τ2 /(3τ2 − τ1 ))

(1)

where Σ := Var(∇ρ(x1 , θ0 )), and optimal weights ŵi ∝ m X ŵi = 1.

−1 !−1

C 2 d(d∨log N )K trace(Σ) + B µ2 n2 ni i

(2) −1

with

i=1

In the above theorem, we obtain an upper bound on the MSE of Algorithm 1 after K iterations without any restriction on the sample sizes. For ease of understanding, we present two simplifications of the above rate, aiming to explain the dichotomy between utility and federated privacy in our problem. Remark 3.1 (Rate Simplification). The upper bound in Theorem 3.2 can be simplified to E

θ̂(AG1) − θ0

≤ Pm

2 2 i=1 (ni ∧ (ni µ /(d ∨ log N ) log(N )))

(3)

for a constant C > 0, under standard assumptions wherein trace(Σ) ≤ Cd. The denominator implies that the effective sample size contribution from each client is the minimum of the actual sample size ni and its privacy-affected version n2i µ2 /d log N . If µ is sufficiently small, in partic−1/2 ular µ ≲ ni , this sample size reduction is significant and leads to a slower MSE decay. This upper bound also coincides with the minimax lower bound in Theorem 3.10. Remark 3.2 (Comparable sample sizes). When nmax /nmin ≤ C for some constant C > 0, the above MSE bound reduces to: 2 md(d ∨ log N ) log(dN ) 2 C trace(Σ) CB ≤ 2 E θ̂(AG1) − θ0 + (4) N µ2 N 2 τ1 for a constant C > 0, where N =

m X

ni and we use the weights {wi = ni /N : 1 ≤ i ≤ m} when

i=1 (k)

computing the weighted average of gradients {g̃i

: 1 ≤ i ≤ m} for k = 1, . . . , K.

Remark 3.3 (Weight selection). The optimal choice of weights in Theorem 3.2 depends on the knowledge of trace(Σ), which is not known in practice. However, our assumptions 3 imply 9

bounded singular values of Σ, so that trace(Σ) can be replaced in the weights by Cd for a constant C > 0, leading to an MSE that will be worse by a factor of at most a numerical constant. The result in Equation (1) of Theorem 3.2 represents a tradeoff between accuracy improvement due to higher number of iterations K (first term) and accuracy loss due to enhanced variance of added Gaussian noise needed to protect against privacy leak for higher number of iterations. Note that in our framework, K needs to be pre-selected, since the amount of noise introduced by the clients is a function of K. This is needed to guarantee the entire algorithm is private. Therefore, from Lemma 3.1, a smaller K leads to the introduction of smaller privacy noise. The Equation 2 in Theorem 3.2 provides a finite sample bound on the MSE of Algorithm 1 for any large enough K chosen such that the first term vanishes (such as O(log(dN ))) and any bounded initial value θ(0) (for example, θ(0) = 0). Moving to the individual terms of the MSE bound, we note from Equation (4) that the first part of the right-hand side is the familiar MSE for M-estimators, while the second part is the additional error due to privacy. Since the entire gradient descent computation is being performed at the server (with aggregation of privatized client gradients), there is no loss of accuracy due to federation in the first term. Therefore, this method is well-suited when we have numerous clients. We further see in the Remark 3.2, that noting N = mn, where n is the average sample 1 1 size at the clients, the second term is O( mn 2 ), while the first term is O( mn ). Therefore, as the average sample size in the clients increases, the additional error due to privacy becomes smaller compared to the error rate in the non-private case. Remark 3.4. For d ≥ C log N , and keeping K > C1 log(dN ) explicitly in the upper bound, mKd2 the privacy-related error term in Theorem 3.2 and Remark 3.2 scales as O µ2 N 2 . This can be compared with the scaling for the non-federated settings in Avella-Medina et al. [2023]. The federated framework we consider causes an additional factor of m in our bound, because of our stronger privacy requirement in our framework, to ensure clients satisfy µ-fed-GDP in the sense of Definition 2.2. In the next algorithm, we explore the idea of a better initialization, which can possibly lead to similar accuracy with fewer iterations.

3.2

Algorithm 2 (FedHybrid: K1 local/K2 server gradient descent)

The second algorithm which we call FedHybrid, adopts a two-stage design that combines private local estimation with server-side refinement using FedSGD. In the first stage, clients independently perform K1i steps (for i = 1, . . . , m) of private gradient descent on its local data, starting from a (0) (K ) common initialization (e.g., θi = 0), to obtain a privatized local estimator θi 1i , which is then sent to the server. In the second stage, the server aggregates the local estimators by weighted P (K1i ) , and subsequently applies averaging to form an initial global estimator θ̄ = N1 m i=1 ni θi K2 steps of server-side private gradient descent following FedSGD. The method is displayed in Algorithm 2. The MSE bound for this estimator can then be derived by combining the MSE from Equation (1) with suitable bounds on the initialization θ̄. We state the result on the initialization θ̄ first. This MSE bound is the bound on FedAvg [McMahan et al., 2017a] with just one round of 10

Algorithm 2: K1 -Local / K2 -Server FedHybrid Input: Data {X (i) }m i=1 with local client sample sizes {ni }; step sizes η1 , η2 ; iteration K1i = K1 , K2 ; privacy parameter µ > 0; loss function ρ(·, θ); clipping bound B. Output: θ(K2 ) (0)

Set g(x, θ) = ∇ρ(x, θ). Initialize θi

= 0 for all i.

Stage I (clients): For each client i = 1, . . . , m, for t = 0, . . . , K1i − 1: √ ni 2Bη1 2K1i η1 X (i) (t) (t+1) (t) . g(xj , θi ) + ai Zit , Zit ∼ N (0, Id ), ai = θi = θi − ni µni

j=1 (K1i ) Client i sends θi to server. m X

Stage II (server): θ̄ =

i=1

ni (K1i ) θ . N i

Run K2 steps of Algorithm 1 initializing at θ̄ with noise multipliers

√ 2B 2K2 . µni

Return θ(K2 ) .

communication, i.e., R = 1, and is of independent interest to understand tradeoffs between accuracy, and costs of federation and privacy. Theorem 3.3. (FedAvg with R = 1) Suppose Assumptions 1-4 above hold. Let θ̄ be as defined above. Then there exists a numerical constant C > 0 such that h i 2K 16 trace(Σ) 2mCB 2 max d(d ∨ log N ) E θ̄ − θ0 + ≤ 2 N µ2 N 2 τ1 !2 m 2 K d(d ∨ log N ) X CB C 1i + 2 mtrace(Σ) + N µ2 n i i=1

√ where B = CB d ∨ log N , K1i ≥ C log(dN )/log(3τ2 /(3τ2 − τ1 )) for constants C, CB > 0 and Kmax = max{K1i : 1 ≤ i ≤ m}. Remark 3.5 (Cost of federation and privacy). Opting for the case of fixed dimensions for cleaner presentation, the above Theorem can be compared with the error rate of a centralized non-private M estimator, which is O( N1 ), to assess the costs of federation and privacy. The dominant term for m2 the cost of federation is the third term, which scales as O( N 2 ). Therefore, the cost of federation is smaller than the accuracy of a centralized estimator as long as m = O(N 1/2 ), which has been observed in several works in the literature Zhang et al. [2013], Huang and Huo [2019]. The 2 m4 ). For dominant term for the cost of privacy is the rightmost term, which amounts to O( K µ4 N 4 µ = O(1), this term becomes negligible compared to the centralized non-private estimation error provided m = O(N 3/4 ). With the above initialization we can now use (1) to derive the following MSE on θ̂(AG2) , the output of FedHybrid in Algorithm 2. Lemma 3.4. (Privacy guarantee for FedHybrid) With the scaling of the Gaussian noise at the √ √ 2Bη1 2K1i 2B 2K2 ith client in stage 1 set at ai = and in stage 2 set at µni , each client is µ-fed-GDP µni

in the sense of Definition 2.2, and the full Algorithm is √µm -GDP towards a third-party in the sense of Definition 2.1. Theorem 3.5. (Error bound for FedHybrid) Suppose assumptions 1-4 above hold. Let θ̂AG2 √ 2 > 0, K be the output of Algorithm 2 with norm bound B = CB d ∨ log N for a constant CB 1i iterations in Stage 1 and K2 iterations in Stage 2. For K1i ≥ 4 log(ni )/log(3τ2 /(3τ2 − τ1 )) and K2 = 2 log(m)/log(3τ2 /(3τ2 − τ1 )) the mean squared error of estimating θ0 by θ̂AG2 satisfies E

θ̂(AG2) − θ0

17 ≤ 2 τ1

m X trace(Σ) i=1

2C 2 d(d ∨ log N ) log(m) + 2 B2 µ ni log(3τ2 /(3τ2 − τ1 ))

−1 !−1

(1)

where Σ := Var(∇ρ(x1 , θ0 )). To compare with the analogous result for Algorithm 1, we state the simplified upper bound in the case where sample sizes are comparable. Remark 3.6 (Comparable sample sizes). When nmax /nmin ≤ C for some constant C > 0, the above MSE bound reduces to: 2 md(d ∨ log N ) log(m) 2 C trace(Σ) CB + (5) E θ̂(AG2) − θ0 ≤ 2 N µ2 N 2 τ1 for a constant C > 0, where N =

m X

ni and we use the weights {wi = ni /N : 1 ≤ i ≤ m} when

i=1 (k)

computing the weighted average of gradients {g̃i

: 1 ≤ i ≤ m} for k = 1, . . . , K.

Comparing Equations (4) and (5) shows that in the comparable sample size regime, the MSEs of θ̂(AG1) and θ̂(AG2) coincide in the “non-private” term of trace(Σ)/N but differ in the “private” term. This difference stems from the dependence on K and K2 . A quick inspection of the required number of iterations (and consequently rounds of server-client communications) reveals that K = Ω(log(N )) for Algorithm 1 while K2 = Ω(log(m)) for Algorithm 2. It is reasonable to assume that the number of servers, m, grows at a much slower rate than the total sample size N . This implies that the MSE of FedHybrid θ̂(AG2) is lower than that of FedSGD θ̂(AG1) while also improving the server-client communication cost from O(d log N ) to O(d log m). This result theoretically shows the benefit of our novel FedHybrid method over the alternative method FedSGD.

3.3

Algorithm 3: R round FedAvg

Our third estimator involves federated averaging of client updates. The complete algorithm is described in Algorithm 3. The FedAvg [McMahan et al., 2017a, Wei et al., 2020] alternates between local private updates and server-side aggregation over multiple communication rounds. At each round, the server broadcasts the current global model to all clients. Each client then performs local gradient descent iterations, adding Gaussian noise at each iteration to ensure client-level privacy. After completing the local updates, the clients send their locally trained models to the server. Then the server aggregates the received local models using weighted average to form an updated global model, which is then broadcast in the next round. 12

Algorithm 3: FedAvg Input: Data {X (i) }m i=1 with local client sample sizes {ni }; communication rounds R; local iteration K; privacy parameter µ > 0; loss function ρ(·, θ); clipping bound B. Output: θ(R) Set g(x, θ) = ∇ρ(x, θ). Initialize θ(0) = 0. √ 2Bη RK Noise scale: σi = . µni for r = 1, . . . , R do round Server broadcasts θ(r−1) . for each client i = 1, . . . , m do (0) θi = θ(r−1) . for t = 0, . . . , K − 1 do local ni η X (i) (t) (t+1) (t) g(xj , θi ) + σi Zit , Zit ∼ N (0, Id ). θi = θi − ni j=1

(K) Send θi to server. m m X X ni (K) θ(r) = θi , N = ni . N i=1 i=1 Return θ(R) .

Unlike FedSGD, which aggregates privatized gradients at every iteration, FedAvg aggregates the parameter estimates at communication rounds. This aggregation strategy can be beneficial in terms of reducing communication cost without losing much accuracy when local sample sizes are sufficiently large, as the local models can be relatively accurate. However, as we show below, the benefits disappear if local sample sizes are small and we have numerous clients. Lemma 3.6. (FedAvg DP guarantee) With the scaling of noise mentioned in Algorithm 3, the clients are µ-fed-GDP in the sense of Definition 2.2. With the Assumptions 2 and 4 on τ1 strong convexity and τ2 smoothness, and setting learning rate η such that Cη := (1 − 2ητ1 + η 2 τ22 ) < 1, the algorithm is √µm -GDP towards a third-party in the sense of Definition 2.1. Theorem 3.7. (Error bound for FedAvg) Suppose Assumptions 1–4 hold. For the estimator θ(R) obtained after R rounds of Algorithm 3, 2 16 trace(Σ) 2mCRKd(d ∨ log N ) ≤ 2 + E θ̂(AG3) − θ0 N µ2 N 2 τ1 C + 2 N

m trace(Σ) +

m X RKd(d ∨ log N ) i=1

µ2 n i

!2 .

√ where B = CB d ∨ log N , K ≥ C log(dN )/log(3τ2 /(3τ2 − τ1 )) for constants C, CB > 0. This result is a R communication round version of the result in Theorem 3.3 and is proved through recursion starting from that result. These results also reveal a similar tradeoff between accuracy and costs of federation and privacy protection. We note that the result is intended for a finite number of rounds of communication, and does not show the advantage of higher R. 13

Remark 3.7. (Bias of FedAvg) We have the following expression for the bias of FedAvg for 1 round of communication (equal sample size case), E(θ̄ − θ0 ) ≤ O

mtrace(Σ) d(d ∨ log N )m2 + N µ2 N 2

md(d∨log N )RK . Hence approximately the squared bias is while the variance is O trace(Σ) + 2 2 N µ N 2 O(m ) higher than that of variance. To achieve an MSE bound comparable to Theorem 3.2 the FedAvg estimator would thus require m ≤ (N/C(d ∨ log N ))1/2 , when µ is large. This bias is the primary reason for the underperformance of FedAvg. In the next section we present FedNewton, as a communication-efficient approach to reducing this bias of FedAvg.

3.4

The FedNewton Algorithm

Next, we propose a new method that adds one Newton step following the FedAvg estimator. The purpose of this Newton step is to reduce the bias in the FedAvg estimator as shown in Remark 3.7. At the conclusion of the R rounds of communication of the FedAvg estimator, the current solution is broadcasted to the clients for an additional round. In this round the clients make one (or several) updates, but instead of gradient descent, they run a Newton step which requires the Hessian matrix. The clients then send the updated model parameters back to the server, which then aggregates the parameters for the final estimator. Lemma 3.8. (FedNewton DP guarantee) With the scaling of noise mentioned in Algorithm 4, the clients are µ-fed-GDP in the sense of Definition 2.2. Theorem 3.9. (Error bound for FedNewton) For the estimator θ̂(AG4) obtained from Algorithm 4, we have E

θ̂(AG4) − θ0

≤

Ctrace(Σ) Cmd(d ∨ log N ) + , µ2 N 2 τ12 N

(6)

√ where B (N ew) = CB d ∨ log N for some constant CB > 0, if the weights wi are taken to be wi = ni /N , where Kmax = max K1i , provided there exists a constant C > 0 such that 2 2 m ≤ min{(N/Cd)2/3 , (µ3 N n2min /C(d ∨ log N )3 Kmax )2/3 , (µ2 N n2min /C(d ∨ log N )2 Kmax )1/2 }. 2 }1/3 Moreover, if either i) nmax ≤ Cnmin , or ii) m ≤ {(1∧{N µ2 /d})µ2 n2min N/C(d∨log N )3 Kmax for a constant C > 0, then

θ̂(AG4) − θ0

C ≤ 2 τ1

m X trace(Σ) i=1

(1) where Σ := Var(∇ρ(x1 , θ0 )), and weights ŵi ∝

2C 2 d(d ∨ log N ) + 2 2 B µ ni log(3τ2 /(3τ2 − τ1 )) 2 d2 K CB trace(Σ) + ni µ2 n2i

−1

with

−1 !−1

m X

(7)

ŵi = 1.

i=1

The above theorem shows that when the number of clients m is sufficiently small, FedNewton achieves the same upper bound on MSE, as done by FedSGD and FedHybrid. To better under-

Algorithm 4: FedNewton: One-Step Newton following FedAvg Input: Client data {X (i) }m i=1 with local sample sizes ni , Local step size η; local iterations per round K, Privacy parameter µ > 0,loss function ρ(·, θ); clipping bound B. Output: Global model θ(2) Sample Splitting: Split X (i) into disjoint sets of samples X (i)1 , X (i)2 each of size ni /2. Initialization: Set θ(0) = 0.

√

Noise scale: Set noise scale for each client: σi = 4Bηµni2K . Federated Training: DPFedAvg: Run FedAvgAlgorithm 3 with R = 1 and noise scaling σi on data X (i)1 . // Client-side local One-Step Newton for each client i = 1, . . . , m in parallel do Update Newton-step:

(N ew) θi = θ(1) −

L̈i (θ

(1)

(i)1

−1 2B (N ew) ) L̇i (θ(1) , X (i)2 )+ Zi , µni

(N ew)

Client i sends local model θi

where B

(new)

√ 4 2B = τ1

to server

// Server-side aggregation Aggregate client models with sample-size weighting: θ

(2)

m X

(N ew)

wi θ i

i=1

Return: Final global model θ(2) .

stand the benefit of FedNewton we focus on the case of comparable sample sizes, i.e., when nmax ≤ Cnmin for some C > 0. Remark 3.8. (Comparable sample sizes) When the sample sizes are comparable the restriction on the number of clients reduces to 4/7 1/2 m ≤ min{(N/C(d ∨ log N ))2/3 , (N µ/(d ∨ log N ))6/7 /CKmax , (µ/(d ∨ log N ))1/2 N 3/4 /CKmax }.

We note from the above theorem that FedNewton does not suffer from the same limitation as FedAvg did in terms of the growth rate of the number of clients and the result in Equation 6 of Theorem 3.9 holds as long as m is bounded by the above quantity. In particular when µ is sufficiently large, the restriction becomes m ≤ (N/C(d ∨ log N ))2/3 , which is weaker than the requirement of m ≤ (N/C(d ∨ log N ))1/2 in Theorem 3.7. Remark 3.9. (Dependence on K) A striking feature of the FedNewton estimator is that it corrects for the bias in the initial estimator obtained by 1 round FedAvg, and in doing so, removes the privacy cost in terms of the number of iterations K. This is possible of course if m is sufficiently small, and we note that the upper bound on m becomes tighter if we were to allow larger values of Kmax . This conclusion is consistent with the notion of unnecessarily large Kmax 15

being detrimental to the accuracy of our estimator.

3.5

Lower bound

Next, we provide a minimax lower bound on the error rate of any µ-Fed-GDP private federated procedure with K rounds of client-server iterations. Theorem 3.10. (minimax lower bound) For 0 < µ < 1, the class of federated private estimators with K rounds of client-server iterations satisfies inf

sup E θ̂ − θ

θ̂∈T ({n1 ,...,nm },m,K,µ) θ,Pθ ∈P

d 2 2 −1 C n ∧ C (n 2 i µ log(µ )/d)) i=1 1 i

≥ Pm

where T ({n1 , . . . , nm }, m, K, µ) denotes the set of all estimators obtained from ni samples at the i-th client for 1 ≤ i ≤ m, where each client uses a fresh batch of samples for each of K clientserver rounds of communication, while satisfying µ-fed-GDP in the sense of Definition 2.2. The minimax lower bound brings out information-theoretic intuition on the cost of privacy P during federated learning. Instead of having N = i ni in the lower bound, as we would have in centralized non-private estimation, the sample size contribution of each client is modulated by the effect of privacy. The contribution or effective sample size for each client is the minimum of the actual sample size and a quantity that depends on privacy parameters. The construction of the lower bound is via Van Trees inequality and characterizing the shrinkage in information due to federated privacy requirements. Similar techniques have been used earlier in nonparametric federated learning problems: see Cai et al. [2024], Auddy et al. [2024], Xue et al. [2024]. The next two remarks compare the lower bound with the upper bounds obtained via our algorithms. Remark 3.10. (Near-optimality of our methods) As can be seen from the upper bounds in Theorems 3.2, 3.5, and 3.9, FedSGD, FedHybrid, when d ≥ C log N , the upper bounds obtained by our algorithms match the lower bound in Theorem 3.10 upto a factor of log(µ) and K, R, which in our theoretical analyses are also of log(N ) order. Thus our MSE bounds are near optimal, with the only multiplicative discrepancy being of a factor logarithmic in sample size. We note that such gaps in optimality are ubiquitous in the (ε, δ) differential privacy literature: see, e.g., Cai et al. [2021, 2024]. As pointed out in Remark 3.9, the final MSE of the FedNewton estimator does not depend on K and R. FedNewton thus matches the lower bound, with a sub-optimality of only the log(µ) factor. We remind the reader once again of the important caveat that this is possible only when the number of clients m is sufficiently small. Remark 3.11. (Sample splitting) Beyond what is pointed out in the above remark, we note that for a more convenient proof, the lower bound explicitly uses sample splitting at every communication round, while the upper bounds have no such requirement. Using a similar sample splitting in the algorithms would lead to an MSE which is worse by a factor of R in each case, where R refers to the number of client-server communications. The three methods, FedSGD, FedHybrid, and FedNewton now primarily differ in terms of communication cost, which we discuss in the next section. 16

3.6

Communication cost of the methods

The communication costs associated with the three algorithms are summarized in Table 1. Algorithm

Effective Rounds

Total Communication

Error Bound d md2 log N d O + µ2 N 2 N d md2 log m O + N µ2 N 2 2 2 d m d md2 RK O + + N N2 µ2N 2 2 d md O + 2 2 N µ N

FedSGD

K = Ω(log N d)

O(mKd)

FedHybrid

K2 = Ω(log m)

O(mK2 d)

R = O(1)

O(mRd)

O(md)

FedAvg FedNewton

Table 1: Comparison of total communication cost and mean squared error bounds for the four proposed differentially private federated algorithms. We note that FedSGD has high communication cost of O(mKd) due to the need of collecting gradients from the clients at each step. The hybrid method (FedHybrid), on the other hand, runs the first K1 iterations locally at the clients, which does not require any communication. In stage 2, the algorithm runs K2 ≪ K iterations, resulting in a communication cost of O(mK2 d). We remind the readers that in our setup of empirical risk minimization with scalar valued response, both the parameter and the gradient are of dimension d. This comparison of communication cost continues to hold even if we consider non-convex risk minimization such as training deep neural networks.

3.7

FedNewton adaptation for training neural networks

Given the importance of federated learning for training deep neural networks (DNN), we briefly discuss practical adaptation of the proposed FedNewton to DNNs. Note the FedNewton algorithm requires computation of the Hessian matrix locally (at the clients), and in particular, does not require communication of the Hessian. Following recent works in federated learning for DNN and language model training [Jhunjhunwala et al., 2024], we approximate the Hessian with the sample average of the inner product of the derivative (score function) with its transpose. However, unlike Jhunjhunwala et al. [2024], we do not further approximate this matrix by its diagonal, since we do not need to communicate the Hessian to the central server, and the Newton iteration is performed locally at the client. Our method thus achieves a better communicationaccuracy tradeoff. Further, in our data examples on MNIST and CIFAR10 data with convolution neural networks, we found that the full (approximated) Hessian matrix performs better than when only the diagonal is kept as an approximation. For numerical stability, we add a small ridge parameter and a damping parameter to control the step size. The entire method is described in Algorithm 5. In real data examples, we further repeat the entire algorithm (with both stages) for a few iterations instead of finishing all stage 1 runs first and then doing stage 2 iterations. Note that since the loss function of deep neural networks is nonconvex and our Assumptions 1-4 do not hold, the theoretical bounds derived earlier for the four methods do not hold for the case of neural networks. 17

Algorithm 5: FedNewton-NN: Neural network adaptation Input: Client datasets {X (i) }m i=1 with sizes ni ; step size η; rounds R; local steps K; privacy µ; loss ρ(·, θ); clipping bound B; ridge parameter λ; damping parameter α. Output: Global model θ(R+1) √

Initialization: θ(0) = 0,

σi = 2Bηµn2RK . i

Stage 1 (DP-FedAvg): Run DP-FedAvg for R rounds with noise σi to obtain θ(R) . Stage 2 (Approximate Newton refinement): for each client i in parallel do Compute   X X 1 1 gi = ∇ρ(x, θ(R) ), hi =  ∇ρ(x, θ(R) ) ∇ρ(x, θ(R) )⊤  ni n i (i) (i) x∈X

x∈X

Clip ḡi = gi · min{1, B/∥gi ∥2 } Update 2B (New) θi = θ(R) − α(hi + λ)−1 ḡi +

(New)

µni

Aggregation: θ

(R+1)

Zi ,

(New)

√ 2 2B = τ1

m X ni (New) = θ . N i i=1

Return: θ(R+1) .

Simulation Studies

We conduct multiple simulation studies to evaluate the finite-sample performance of the considered methods and validate our theoretical results in finite samples under Poisson and logistic regression models. The generalized linear model (GLM) family takes the form g(E[Y | X]) = Xβ, where g(·) denotes the canonical link function, X is the design matrix of covariates and intercept, and β is the vector of model coefficients. Both the logistic regression and Poisson regression are special cases of GLM. We estimate the parameter β through the maximum likelihood estimator, which is a type of M estimator with the negative log likelihood of the model serving the role of the loss function. Since we know the true parameter vector β in simulation, our goal is to evaluate the performance of the methods in terms of empirical MSE for estimating this parameter vector. In all settings, a total sample of size N is first generated and then partitioned across m clients. We vary the number of clients and the local sample sizes in various scenarios, and apply the four methods, FedSGD, FedHybrid, FedAvg, and FedNewton, to estimate the model parameters. Each simulation study is repeated 100 times. For each repetition, when implementing FedSGD, the number of iterations is set to K = 50 with step size η = 0.5. For FedHybrid, Stage One consists of K1 = 30 local iterations for each client with step size η1 = 0.5, while Stage Two uses K2 = 20 iterations with step size η2 = 0.5. For FedAvg, the number of local iterations is 18

(a) FedSGD, same ni

(b) FedHybrid, same ni

Figure 1: Empirical MSE results of DP version of FedSGD and FedHybrid under equal sample sizes across clients in Logistic Regression. K3 = 50, and the total number of communication rounds is set to R = 2, leading to an effective 100 iterations. For FedNewton, the first stage uses FedAvg with K4 = 50 local iterations and R = 1, followed by just one private Newton step. In all cases, the scale of Gaussian noise to be added to the gradient iterations is calibrated accordingly. We will generally compare the performance of FedHybrid against FedSGD, and FedNewton against FedAvgand avoid comparison across those pairs due to differences in communication cost. The reported results are obtained by averaging the empirical squared estimation error over the 100 repetitions.

4.1

General Federated Simulation Setup

A pooled dataset of size N is simulated from a GLM with the canonical link function. Each data point in this pooled dataset includes a response variable y and its associated covariate vector x. Let β true ∈ Rp denote the true parameter vector, where the first component corresponds to an intercept term. We first generate a covariate matrix C ∈ RN ×(p−1) , whose entries are independently sampled from a normal distribution with mean zero and variance σc2 . An intercept column of ones is then added to this covariate matrix to obtain X. After the pooled data are generated, they are split into m clients according to the local sample sizes {ni }m i=1 . Therefore, (i) n ×p (i) n client i receives a design matrix X ∈ R i and a response vector y ∈ R i . To control the global sensitivity, gradient clipping is applied at the initial value β (0) = 0 for each client. For each observation j = 1, ..., ni in client i = 1, . . . , m, we first compute (i) (i) its gradient norm as, ∇ρ(xj , yj ; β (0) ) . The local clipping threshold Bi is then defined as 2 the 90th percentile of the local sample gradient norms. Then the global sensitivity bound is defined as B = max1≤i≤m Bi . Any gradient vector g ∈ Rp is then clipped using this global bound. This step allows that all gradients are uniformly bounded by B, which is necessary to control the sensitivity before applying the Gaussian mechanism. We note that this data driven global clipping bound uses client data and therefore will leak information, however, following standard practice in the literature [Noble et al., 2022], we ignore this minor privacy leakage in

our theoretical privacy guarantees. As an alternative, one can use a part of the privacy budget, say, µ/10 to set B, and the rest for the estimation procedure. This would leave our theoretical guarantees and algorithmic properties unchanged.

(a) FedAvg, same ni

(b) FedNewton, same ni

Figure 2: Empirical MSE results of FedAvg and FedNewton under equal client sample sizes in Logistic Regression. In the simulation experiments, different numbers of clients and local sample sizes are considered. In the first set of simulations for both logistic and Poisson GLM, we vary number of clients m ∈ {20, 30, 40, 50, 60}. For the local sample sizes, two cases are examined. The first case assumes that all clients have the same local sample size of n with n ∈ {30, 50, 70, 90, 110}. The second case allows variation across clients in the local sample sizes. In this case, the sample sizes for clients ni are independently sampled from a discrete uniform distribution. Specifically, the following ranges are considered: [10, 90], [20, 80], [30, 70], [60, 160], [80, 140], [100, 120]. In the second set of simulations to better compare the four methods, we consider a setting of m increasing from 60 to 140, under three different local sample size regimes: equal local sample sizes with ni = 400, local sample sizes generated from a discrete uniform distribution on [100, 700], and local sample sizes generated from a log-normal distribution with parameters (5.5, 1). These settings are used to compare the estimation performance of FedSGD, FedHybrid, FedAvg, and FedNewton under different client-size distributions with mean local sample size around 400 for both logistic and Poisson GLMs. The third and fourth set of simulations evaluate the tradeoffs we observed theoretically in the previous sections in finite samples. For this we first vary the number of iterations to evaluate the behavior of the methods in the third set while we vary the number of clients without changing the total sample size across all clients in the fourth simulation.

4.2

Logistic Regression performance of federated methods

We remind the readers that for logistic regression setting, the probability of yij = 1 is defined by exp(x⊤ ij β true ) . The binary responses are then generated indepenthe logit link function as πij = 1+exp(x⊤ ij β true ) dently according to yij | xij ∼ Bernoulli(πij ), j = 1, . . . , ni , i = 1, . . . , m. The performance of the federated M -estimator algorithms is evaluated by assessing how the MSE varies with 20

(a) Random sample size

(b) Equal sample size

Figure 3: MSE comparison of FedSGD, FedHybrid, FedAvg, and FedNewton for logistic regression with local sample sizes having mean around 400 under different distributions: (a) Uniformly distributed sample sizes, (b) Equal sample sizes, and (c) Lognormally distributed sample sizes. the number of clients m while keeping the local sample size ni fixed so that the total sample size increases. We display the results over two figures, clubbing similar methods together. In Figure 1, we display the MSE of FedSGD and FedHybrid methods with increasing values of m for different values of the common client sample size ni . In Figure 2, we plot the same results for the other two methods FedAvg and FedHybrid. In Appendix, we show similar figures for both cases with variable client sample sizes ni . The simulation results show that larger sample sizes lead to lower MSE, suggesting that estimation accuracy improves when either more clients are included or each client has access to more local data. Even after allowing for variation in local sample sizes, the overall MSE trend remains stable across all four algorithms, showing a decreasing trend as m increases. These results suggest a baseline improvement in all federated methods with increasing sample size, either in terms of the number of clients or the number of samples per client, which is expected from the theoretical results.

4.3

Comparison between FedSGD, FedHybrid, FedAvg, and FedNewton

After verifying each method works well, we now compare the MSE of the estimators produced by FedSGD, FedHybrid, FedAvg, and FedNewton under different distributions of local client sample sizes. The results are presented in Figure 3 for logistic regression. In all three cases, the average local sample size is approximately 400. For this setting, we consider three distributions of local sample sizes ni : equal sample sizes, discrete uniformly distributed sample sizes, and log-normal distributed sample sizes. Specifically, we consider the following distributions for the local sample size ni : (i) equal local sample sizes with ni = 400; (ii) a discrete uniform distribution [100, 700]; and (iii) a log-normal distribution with mean 5.5 and standard deviation 1 on the log scale. Among the two communication heavy methods, FedHybrid outperforms FedSGD in terms of empirical MSE. We remind the readers that in FedHybrid, clients first compute private local estimators, which are averaged at the server before further FedSGD updates, which saves in communication cost, yet achieves a superior performance in our simulation. Among the two communication-efficient methods, FedNewton outperforms FedAvg. Further, among the methods considered, FedNewton achieves the best performance, while FedAvg has the worst performance. Recall that compared with FedAvg, FedNewton further refines the estimator by performing an additional Newton step after a FedAvg initialization. This second-order update 21

(a) FedSGD

(b) FedHybrid

(d) FedNewton

Figure 4: The empirical MSE of the methods with increasing number of iterations illustrating the tradeoff between optimization quality and privacy. improves estimation accuracy and leads to lower MSE than FedAvg in this setting.

4.4

Accuracy and Privacy Trade-off with Number of Iterations

We next validate the theoretical results showing that increasing the number of iterations leads to a phenomenon of conflict between increased accuracy due to better optimization and decreased accuracy due to higher privacy noise. In Figure 4 we show this trade-off between optimization performance and privacy noise for the logistic regression setting. When the number of iteration K is small, the MSE decreases as K increases. This is expected because additional steps help improve the estimator. However, after a certain point, further increasing K can increase the MSE. This is because a larger number of iterations also leads to more accumulated privacy noise. A smaller value of µ gives stronger privacy and requires more Gaussian noise. As shown in the figure, the curve for µ = 2, while remaining similar to the non-private and µ = 6 curves for smaller K, sharply goes above those curves for larger K, especially for K > 100. This shows that although a larger K can improve optimization, too many iterations may add too much privacy noise and harm the final estimator. Overall, the results illustrate the trade-off among accuracy, privacy, and K. 22

(a) Equal ni

(b) Uniformly distributed ni

Figure 5: MSE comparison of FedSGD, FedHybrid, FedAvg, and FedNewton under fixed total sample size N = 20000 with varying number of clients m: (a) equal local sample sizes, (b) uniformly distributed local sample sizes, and (c) lognormally distributed local sample sizes.

4.5

Effect of the Number of Clients under Fixed Total Sample Size

To illustrate the effect of federation across clients, we conduct a simulation study with a fixed total sample size N , while allowing the number of clients m to increase. The total sample size is fixed at N = 20000. For each value of m, we consider three local sample-size allocation schemes: equal sample sizes, uniformly distributed sample sizes, and lognormally distributed sample sizes. In this experiment, increasing m redistributes the same total amount of data across more clients, instead of increasing the total sample size as was the case in section 4.3. This is a very relevant scenario for modern Federated Learning applications, where we typically have many small client devices, each with a small amount of data. The results are consistent with the theoretical comparison. FedAvg shows the sharpest increase in MSE as m grows, which agrees with the O(m2 d2 /N 2 ) term in its error bound. When N is fixed, this term increases quadratically with m, indicating that FedAvg is more sensitive to splitting the same data across more clients. In contrast, FedSGD, FedHybrid, and FedNewton remain relatively stable as m increases. This is consistent with their m-dependent terms in the error bound, which are O(md2 log(N d)/(µ2 N 2 )) for FedSGD, O(md2 log m/(µ2 N 2 )) for FedHybrid, and O(md2 /(µ2 N 2 )) for FedNewton. Overall, this experiment shows that redistributing the same total sample size across more clients affects the four private methods differently. The performance of FedAvg deteriorates quickly, whereas our new communication-efficient solution FedNewton significantly mitigates this decline.

4.6

Poisson GLM

In the Poisson GLM the link function is log. Accordingly, the response variables are generated independently according to yij | xij ∼ Poisson(λij ), j = 1, . . . , ni , i = 1, . . . , m, with the conditional mean of the Poisson distribution given by λij = exp(x⊤ ij β true ). To evaluate the performance of the proposed federated M-estimator algorithms, we compute the empirical MSE as the number of clients m changes both for homogeneous sample sizes and different sample sizes. For the four proposed algorithms, FedSGD, FedHybrid, FedAvg, and FedNewton, the empirical MSE of the corresponding final estimates are plotted against increasing values of m under different values of ni in Figure 13 and Figure 14 in the Appendix B. The results indicate that larger local sample sizes lead to lower MSE across all values of m, suggesting that 23

(a) Uniformly distributed ni

(b) Equal ni

Figure 6: Poisson GLM: Empirical MSE comparison of FedSGD, FedHybrid, FedAvg, and FedNewton for local sample sizes with mean around 400 under different local sample size distributions: equal sample sizes, uniformly distributed sample sizes, and lognormally distributed sample sizes. the estimation accuracy improves when there are more clients or when each client has more local data. Moreover, variation in local sample sizes does not substantially affect the overall MSE trend. Regardless of the variation in local sample sizes, the MSE decreases as the number of clients increases for all four algorithms. The four methods are compared against each other in Figure 6. We once again see that among communication inefficient methods, FedHybrid outperforms FedSGD. Among communicationefficientient methods, FedNewton clearly performs better than FedAvg. The comparison of the methods with increasing number of iterations K is presented in the Appendix Figure 15, while the comparison in the case of increasing number of clients yet fixed total sample size is presented in Appendix Figure 16. The conclusions from these figures are similar to what we had in the logistic regression case.

Real Data Applications

5.1

Binary and Multiclass Logistic regression on MNIST

The first real data application we consider is binary and multiclass logistic regression on the popular MNIST image classification dataset [LeCun et al., 1998]. The MNIST consists of grayscale handwritten digit images from ten classes, corresponding to the digits 0 through 9. Each image is available as a 28 × 28 matrix with entries being the pixel intensities taking integer values between 0 and 255. The MNIST dataset consists of two components: a training set containing 60000 images and a test set containing 10000 images, each with corresponding class labels. For this application, we vectorize the matrices and store them as feature vectors of length 784. The associated labels indicating the handwritten digit (0–9) in each image is our response variable. Moreover, all image vectors are normalized by dividing pixel intensities by 255, so that their values lie in [0,1]. In this study, we combine the original training and testing sets to form a single dataset of size N = 70000. This combined dataset is then randomly partitioned across m = 80 clients, while ensuring a minimum local sample size of 800 images for each client. This is done so that the number of samples in each client is higher than the total number of parameters, which is 24

d = 784. After allocating this minimum number of samples to all clients, the remaining images are distributed among the clients according to randomly generated proportions. Within each client, the local MNIST data are split into K = 5 folds for cross-validation. Fold assignment is performed independently within each client by first applying a random permutation to the observations and then allocating them approximately evenly across the five folds. In each round, one fold serves as the testing set and the remaining four folds are used for training. Then in every round, the out of sample AUC values are computed for the data in the test fold for each method and each client. To reduce variability induced by the partition into clients, we repeat the client splitting procedure S = 3 times. Therefore, within each split, each method yields one AUC per client and per fold. We then average these client-level AUCs across the 5 folds to obtain a fold-averaged AUC for each client. Therefore, for each fixed (µ, method) combination, we obtain m × S = 80 × 3 = 240 fold-averaged client-level AUC values, which are summarized using boxplots. To investigate how predictive performance varies with the privacy budget, we consider two levels of privacy, with larger values of the privacy parameter corresponding to weaker privacy requirement. Specifically, we take µ ∈ {6, 2}. We compare nine estimators using the AUC values: FedSGD, FedAvg, FedHybrid, FedNewton, DP-SCAFFOLD, NP-SCAFFOLD, NP-FedAvg, NP-LocalFit, and NP-Pooled. The methods with a “NP” are non-private methods and are used as baselines.

Figure 7: Binary class logistic regression MNIST results under different privacy budgets.

Binary Classification We consider a binary classification task for MNIST. Specifically, images whose original labels correspond to odd digits (1, 3, 5, 7, 9) are relabeled as 1, while images corresponding to even digits (0, 2, 4, 6, 8) are relabeled as 0. The resulting binary response variable indicates whether an image represents an odd digit. A logistic regression model is then fitted to estimate the probability that an image corresponds to an odd digit. Figure 7 reports the boxplots of the client-level AUC values under µ = 6 (left) and µ = 2 (right) respectively. The private federated estimators studied in this paper achieve strong predictive performance in both settings. The results are also stable when the privacy constraint becomes stronger, from µ = 6 to µ = 2. This suggests that the additional privacy noise does not lead to a substantial loss in prediction accuracy in this application. Among all the private methods, FedNewton has the highest median AUC. In fact it has 25

Figure 8: Multiclass MNIST results under different privacy budgets. higher median AUC compared to the non-private methods as well. In particular it outperforms both DP version of FedAvg and SCAFFOLD. The FedHybrid and FedAvg also perform well, while FedSGD is slightly lower but still comparable. They methods are also competitive Compared with the non-private federated baselines, the proposed private methods remain competitive. Their performance is close to the performance of NP-FedAvg and NP-SCAFFOLD. In contrast, NPLocalFit has the lowest AUC among the methods considered, which suggests that local fitting alone is less effective than federated aggregation in this setting. These results indicate that the proposed private federated estimators achieve a good balance between data privacy and prediction accuracy under reasonable privacy budgets. Multi-Class Classification Now we consider the more natural target of multi-class classification using a multiclass logistic regression model. More specifically, we fit a logistic (often also called “softmax") regression model to estimate the class probabilities for the ten digit classes. Figure 8 shows the client-level classification accuracy under µ = 6 and µ = 2. The accuracy of classification is a more commonly used metric for multi-class classification problems. As shown in Figure 8, all methods achieve relatively high accuracy in this setting. The results are also stable when the privacy constraint becomes stronger, from µ = 6 to µ = 2. The private federated methods perform closely to the non-private federated methods. Among the private methods, FedNewton continues to have the highest median accuracy, followed by DP-SCAFFOLD, while FedSGD, FedHybrid, and FedAvg have slightly lower but still comparable performance. Among the non-private methods, NP-SCAFFOLD and NP-FedAvg perform well, whereas NP-LocalFit has the lowest accuracy. These results suggest that the proposed private federated estimators can preserve predictive performance well in the multiclass MNIST problem. Among the private methods, FedNewton appears to benefit from the additional Newton refinement step. The similar performance under µ = 6 and µ = 2 further suggests that the private methods are not very sensitive to the moderate increase in privacy protection in this data application.

5.2

Federated training of neural networks on MNIST and CIFAR10

Final test accuracy

We apply the private federated learning methods to multi-class image classification on MNIST and CIFAR-10 using convolutional neural networks (CNNs). For MNIST, the CNN has two convolutional layers followed by two fully connected layers. For CIFAR-10, the CNN has three convolutional layers followed by three fully connected layers. The global accuracy reported in all figures is the accuracy on the standard held-out test set. We consider two federated learning scenarios. In the first scenario, shown in Figure 9, we fix the number of clients at m = 100 and increase the number of samples available to each client. In the second scenario, shown in Figure 10, we use the full training splits and increase the number of clients while keeping the total training sample size fixed. Thus, as m increases, the average number of samples per client decreases. 0.52 DP-FedSGD DP-FedHybrid DP-FedAvg DP-FedNewton-Iter

0.42

0.33

1.00 DP-FedSGD DP-FedHybrid DP-FedAvg DP-FedNewton-Iter

0.80

0.60

0.24

0.40

0.14

0.20

0.05

0.00 50

100

200

300

400

500

Samples per client

100

200

300

400

600

Samples per client

Final test accuracy

Figure 9: CNN results with increasing samples per client: median test accuracy on (left) CIFAR10 and (right) MNIST. The number of clients is fixed at m = 100. The medians are computed over five independent runs.

0.53 DP-FedSGD DP-FedHybrid DP-FedAvg DP-FedNewton-Iter

0.44

0.34

0.95 DP-FedSGD DP-FedHybrid DP-FedAvg DP-FedNewton-Iter

0.93

0.90

0.24

0.88

0.14

0.85

0.05

0.83 100

200

300

500

800

1000

100

Number of clients

200

300

500

800

1000

Number of clients

Figure 10: CNN results with increasing number of clients fixing the total sample size: median final test accuracy on (left) CIFAR-10 and (right) MNIST. The medians are computed over four independent runs.

5.2.1

Data and Client Partitioning

We compare the performance of federated training of CNNs on two popular image classification benchmarks: MNIST and CIFAR-10. The MNIST dataset has been discussed before. The standard dataset contains 60,000 training images and 10,000 test images. Because the images are low-dimensional, centered, and visually simple, MNIST is a relatively easy benchmark for convolutional neural networks. CIFAR-10 Krizhevsky et al. [2010] is a more challenging natural image classification benchmark with ten object classes: airplane, automobile, bird, cat, deer, dog, frog, horse, ship, and truck. Each image has spatial dimension 32 × 32 with three RGB color channels making those 32 × 32 × 3 tensors. The standard split contains 50,000 training images and 10,000 test images. Compared with MNIST, CIFAR-10 has substantially greater visual variation due to color, texture, background clutter, and changes in orientation, making it a harder problem to classify accurately. For the increasing samples in the clients scenario, the training data are split IID across m = 100 clients and each client’s local data are capped at n ∈ {50, 75, 100, 200, 300, 400, 600} samples per client. Since CIFAR-10 has 50,000 training examples, the maximum sample per client for this dataset is 500. For the increasing client scenario, we instead use the full training split and vary m ∈ {100, 200, 300, 500, 800, 1000}. This keeps the total sample size fixed while changing the average local sample size per client. In both cases, each client’s data is further divided locally into training, validation, and local test portions using 10% validation and 10% local test splits. Local gradient descent updates are full-batch updates, so one local epoch corresponds to one gradient step over the client’s local training split. For both scenarios, we repeat the runs a few times and plot the median test accuracies in each case in the figures. 5.2.2

Models and optimization setup

We use convolutional neural networks with log-softmax outputs and negative log-likelihood loss for optimization. The CNN model for MNIST has two convolutional blocks with 32 and 64 channels, followed by a 128-unit fully connected layer and a 10-class classifier layer. The CIFAR10 network uses three convolutional blocks with 32, 64, and 128 channels, followed by a 256-unit fully connected layer and a 10-class classifier. In both scenarios, a fraction q = 0.1 of clients is sampled per global round. The MNIST runs use 10 base global rounds and 10 local epochs per round, with learning rate 0.01, server learning rate 1.0, and clipping bound B = 1.0. The CIFAR-10 runs use 10 base global rounds and 30 local epochs per round, with learning rate 0.005, server learning rate 0.75, and clipping bound B = 0.75. The privacy parameter is µ = 2.0 in all runs. The figures compare four DP federated learning methods. These are FedAvg, a computematched FedSGD, compute-matched FedHybrid, and FedNewton-Iter. The FedAvgperforms private full-batch local SGD on selected clients. The FedSGD and FedHybrid uses additional communication rounds to match the local computation budget of FedAvg. The FedNewton-Iter alternates FedAvg blocks with private head-only Newton refinements. It uses two cycles, each with five FedAvg rounds followed by one Newton refinement. All methods are privatized with the Gaussian noise added as described in the methods and theory.

5.2.3

Results

Figure 9 shows that increasing the number of local examples generally improves final accuracy, as expected, because both the cost of federation and the effect of client-level privacy noise decrease with larger local sample sizes. On MNIST, FedAvg and FedNewton-Iter are strongest in the small-sample regime, while compute-matched FedSGDbecomes competitive once clients have a few hundred examples. On CIFAR-10, FedAvg and FedNewton-Iter perform best at small to moderate sample sizes, but compute-matched FedSGD improves sharply with more local data and becomes the strongest method at the largest sample sizes. Figure 10 shows the effect of increasing the number of clients while keeping the total training set fixed. We note that the performance of all methods deteriorates as the same data is split among more clients due to the cost of federation. We also note that FedNewton is either competitive or is better than FedAvg at a higher number of clients.

Conclusion

In this article, we obtained finite sample upper bounds on the estimation error of differentially private federated learning methods for M-estimation. These results allowed us to theoretically study the tradeoffs among accuracy gain and privacy loss as the number of iterations increases, as well as the cost of federation and privacy in federated learning. We developed a minimax lower bound on the error rate of any private federated estimator, which allowed us to further study the optimality gap of various federated learning methods. Based on these theoretical considerations, we further proposed two methods as improvements on the existing FedSGD and FedAvg respectively. Our new FedHybrid achieves the same level of accuracy as FedSGD with fewer communication rounds and hence reduces the communication cost. Our new FedNewton retains the communication efficiency of FedAvg while improving upon the accuracy of FedAvg especially when the number of clients is high.

Acknowledgement

This research was partially supported by a grant from the NSF (DMS grant 2529302) and a grant from the OSU College of Arts and Sciences. We also gratefully acknowledge the computing credits provided by the Ohio Supercomputer Center.

References Apple. https://www.apple.com/apple-intelligence/, 2024. Arnab Auddy, T Tony Cai, and Abhinav Chakraborty. Minimax and adaptive transfer learning for nonparametric classification under distributed differential privacy constraints. arXiv preprint arXiv:2406.20088, 2024. Marco Avella-Medina, Casey Bradshaw, and Po-Ling Loh. Differentially private inference via noisy optimization. The Annals of Statistics, 51(5):2067–2092, 2023.

Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464–473. IEEE, 2014. Alissa Brauneck, Louisa Schmalhorst, Mohammad Mahdi Kazemi Majdabadi, Mohammad Bakhtiari, Uwe Völker, Christina Caroline Saak, Jan Baumbach, Linda Baumbach, and Gabriele Buchholtz. Federated machine learning in data-protection-compliant research. Nature Machine Intelligence, 5(1):2–4, 2023. T Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825–2850, 2021. T Tony Cai, Abhinav Chakraborty, and Lasse Vuursteen. Optimal federated learning for nonparametric regression with heterogeneous distributed differential privacy constraints. arXiv preprint arXiv:2406.06755, 2024. Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3–37, 2022. Rui Duan, Yang Ning, and Yong Chen. Heterogeneity-aware and communication-efficient distributed statistical inference. Biometrika, 109(1):67–83, 2022. Cynthia Dwork. Differential privacy: A survey of results. In International conference on theory and applications of models of computation, pages 1–19. Springer, 2008. Hongchang Gao, An Xu, and Heng Huang. On the convergence of communication-efficient local sgd for federated learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7510–7518, 2021. Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradientshow easy is it to break privacy in federated learning? Advances in neural information processing systems, 33:16937–16947, 2020. Robin C Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arXiv preprint arXiv:1712.07557, 2017. Richard D. Gill and Boris Y. Levit. Applications of the van Trees inequality: a Bayesian Cramér-Rao bound. Bernoulli, 1(1-2):59 – 79, 1995. Jia Gu and Song Xi Chen. Distributed statistical inference under heterogeneity. Journal of Machine Learning Research, 24(387):1–57, 2023. Jia Gu and Song Xi Chen. Statistical inference for decentralized federated learning. The Annals of Statistics, 52(6):2931–2955, 2024. Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint arXiv:1910.14425, 2019.

Cheng Huang and Xiaoming Huo. A distributed one-step estimator. Mathematical Programming, 174:41–76, 2019. Divyansh Jhunjhunwala, Shiqiang Wang, and Gauri Joshi. Fedfisher: Leveraging fisher information for one-shot federated learning. In International Conference on Artificial Intelligence and Statistics, pages 1612–1620. PMLR, 2024. Michael I Jordan, Jason D Lee, and Yun Yang. Communication-efficient distributed statistical inference. Journal of the American Statistical Association, 2019. Peter Kairouz and H Brendan McMahan. Advances and open problems in federated learning. Foundations and trends® in machine learning, 14(1–2):1–210, 2021. Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning, pages 5213–5225. PMLR, 2021. Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference on machine learning, pages 5132–5143. PMLR, 2020. Fumiyuki Kato, Li Xiong, Shun Takagi, Yang Cao, and Masatoshi Yoshikawa. Uldp-fl: federated learning with across-silo user-level differential privacy. In Proceedings of the VLDB Endowment. International Conference on Very Large Data Bases, volume 17, page 2826, 2024. Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492, 2016. Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced research). URL http://www. cs. toronto. edu/kriz/cifar. html, 5(4):1, 2010. Yann LeCun, Corinna Cortes, and Christopher J.C. Burges. The MNIST database of handwritten digits. http://yann.lecun.com/exdb/mnist/, 1998. Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2:429–450, 2020. Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint arXiv:1907.02189, 2019. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017a. H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv:1710.06963, 2017b.

Maxence Noble, Aurélien Bellet, and Aymeric Dieuleveut. Differentially private federated learning on heterogeneous data. In International conference on artificial intelligence and statistics, pages 10110–10145. PMLR, 2022. Matthias Paulik, Matt Seigel, Henry Mason, Dominic Telaar, Joris Kluivers, Rogier van Dalen, Chi Wai Lau, Luke Carlson, Filip Granqvist, Chris Vandevelde, et al. Federated evaluation and tuning for on-device personalization: System design & applications. arXiv preprint arXiv:2102.08503, 2021. Zhaonan Qu, Kaixiang Lin, Zhaojian Li, Jiayu Zhou, and Zhengyuan Zhou. Federated learning’s blessing: Fedavg has linear speedup. 2020. Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečnỳ, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020. Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-efficient federated learning method with periodic averaging and quantization. In International conference on artificial intelligence and statistics, pages 2021–2031. PMLR, 2020. Artin Spiridonoff, Alex Olshevsky, and Yannis Paschalidis. Communication-efficient sgd: From local sgd to one-shot averaging. Advances in Neural Information Processing Systems, 34: 24313–24326, 2021. Sebastian U Stich. Local sgd converges fast and communicates little. arXiv:1805.09767, 2018.

arXiv preprint

Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE transactions on information forensics and security, 15:3454–3469, 2020. Gengyu Xue, Zhenhua Lin, and Yi Yu. Optimal estimation in private distributed functional data analysis. arXiv preprint arXiv:2412.06582, 2024. Xinwei Zhang, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Jinfeng Yi. Understanding clipping for federated learning: Convergence and client-level differential privacy. In International Conference on Machine Learning, ICML 2022, 2022. Yuchen Zhang, John C Duchi, and Martin J Wainwright. Communication-efficient algorithms for statistical optimization. The Journal of Machine Learning Research, 14(1):3321–3363, 2013.

Proofs of Lemmas and Theorems

A.1

Additional definitions and lemmas

We will require the following definition for privacy accounting. Definition A.1 (Global Sensitivity). Let D∗ denote the space of all datasets. Consider two datasets D, D′ ∈ D∗ that differ in exactly one datum. The global sensitivity of a function f : Rn×m → Rp with respect to a norm ∥·∥ is defined as GSf = sup ∥f (D) − f (D′ )∥. D,D′

Proposition A.2 (Theorem 1 in Dong et al. [2022]). Let f : Rn×m → Rp be a function and assume its global sensitivity GSf < ∞. Let Z ∼ N (0, Ip ) be a p-dimensional standard Gaussian random vector. For any µ > 0, define h(x) = f (x) +

GSf Z, µ

x ∈ Rn×m .

Then h(x) is µ-Gaussian Differentially Private (µ-GDP). Lemma A.3. Let E be the event defined as follows: ( E :=

max max

1≤i≤m 1≤j≤ni

(i) ∇ρ(xj , θ0 )

CH CH ≤ B, sup L̈i (θ) − L̈0 (θ) ≤ √ for all i, sup L̈(θ) − L̈0 (θ) ≤ √ n N i θ∈Rd θ∈Rd

√ for H = C1 d ∨ log N where C1 is the sub-Gaussian constant in Assumption 3. Then P(E c ) ≤ √ √ c(exp(−cd) ∧ N −4 ) whenever B ≥ C( d ∨ log N ). Proof of Lemma A.3. We prove the result for the case where d > C log N so that we take √ B ≥ C d. The proof for the first part follows by sub-Gaussian tail assumptions on the gradient (i) ∇ρ(xj , θ0 ). Similarly for the Hessian L̈i (θ), we use a 1/3-net S on the unit sphere d−1 , which has a cardinality at most 4d . For each u ∈ S, we again use sub-Gaussian tail assumptions to show CH ⊤ for all i ≤ exp(−Cd) P u (L̈i (θ) − L̈(θ))u ≥ √ ni for a constant C > 0. The result follows by taking a union bound over all u ∈ S and then using a standard ε-net argument, after which we take another union bound using a second ε-net argument over {θ : ∥θ∥≤ C} for a sufficiently large constant C > 0. The proof for the case of √ small dimensions, i.e., d ≤ C log N follows similarly by allowing B = C log N .

A.2

Proof of results in the main paper

Proof of Lemma 3.1. Suppose we run Algorithm 1 (AG1) with K gradient iterations at the server. The total privacy budget for each client is assumed to be µ (i.e., the clients are µ-GDP). Then for each iteration, by the composition theorem of the Gaussian mechanism Dong et al. [2022], the privacy budget is √µK . Also, the server takes a weighted average of the clients’

)

gradients in each of the K iterations. Let us denote the scaling factor of the Gaussian noise as σ/ni for the ith client. To determine the differential privacy of the client towards the server, we note that the (k) (i) (k) 1 Pni global sensitivity of the function gi = ni j=1 ∇ρ xj , θ is 2B ni from the bounded gradient assumption. Then √ σ 2B K = . µni ni √

This gives us σ = 2Bµ K for all clients to be µ-fed-GDP towards the server. To determine the differential privacy of the server to a third party, we make the following calculation.

θ(k+1) = θ(k) − ηg̃ (k) = θ(k) − η

m X ni (k) g̃ N i i=1

m X ni (k) (k) (k) =θ −η gi + noisei N i=1   ni m X X σ (i) ni  1 (i) = θ(k) − η ∇ρ xj , θ(k) + Zk  N ni ni

=θ

(k)

i=1

j=1

ni m X X

η − N

= θ(k) −

η N

i=1 j=1 ni m X X

∇ρ

(i) xj , θ(k)

(i)

η X (i) − σ × Zk N

∇ρ xj , θ(k) −

i=1 j=1

ησ N

i=1 m X i=1

Now in the notation of Proposition A.2, we denote f (x) = θ(k) − Nη Then,

GSf =

(i)

Zk ,

Pm Pni i=1

j=1 ∇ρ

(i) xj , θ(k) .

ni m ni m X X η XX (i)′ (i) ∇ρ xj , θ(k) ∇ρ xj , θ(k) − N i=1 j=1

i=1 j=1

η 2Bη ≤ · 2B = N N Note in the above calculation, the global sensitivity is measured by considering two datasets differ by just one data point overall in the global sample (i.e., there is one client where one data point is different). P (i) (i) Also note that Zk ∼ N (0, Id ) are independent across i and k. Then m i=1 Zk ∼ N (0, mId ). Let the server be µ1 −GDP. Then, we have the following equality √ √ √ 2Bη K η m2B K = µN N µ1 √ √ This implies µ1 = µ/ √m. Therefore, the full algorithm is µ/ m−GDP to a third-party with the noise scaling of 2BµniK for client i. 34

Proof of Theorem 3.2. We first note that g̃ (k) =

m X

(k)

wi g̃i

i=1

m X

i=1

Therefore, writing L̇w (·) =

wi L̇i (·) and L̈w (·) =

θ(k+1) − θ0 = θ(k) − θ0 − η L̇w (θ(k) ) +

! √ K 2ηB (i) Zk . ∇Li (θ(k) ) + µni

m X i=1

wi L̈i (·)

√ ! 2ηB K (i) wi Zk µni

√ m 2ηB K X wi (i) Z = θ − θ0 − η L̇w (θ0 ) + L̈w ((1 − t)θ0 + tθ )dt (θ − θ0 ) + µ n k 0 i=1 i √ Z 1 m 2ηB K X wi (i) (k) (k) Z . (8) = I −η L̈w ((1 − t)θ0 + tθ )dt (θ − θ0 ) − η L̇w (θ0 ) + µ ni k 0 Z 1

(k)

i=1

By the τ1 -strong convexity of ρ, on the event E we have s H2 L̈w ((1 − t)θ0 + tθ(k) )dt ≥ τ1 − C nmin 0

Z 1 λmin

and hence again on E we have from (8) that  ∥θ

(k+1)

− θ0 ∥≤ 1 + C

√ m 2ηB K X wi (i) (k)  − ητ1 ∥θ − θ0 ∥+η L̇w (θ0 ) + Z nmin µ ni k 

i=1

Unrolling the above recursion for k = 0, 1, . . . , K − 1 we have ∥θ(K) − θ0 ∥≤ γ1K ∥θ(0) − θ0 ∥ ( ) √ m X 2ηB K w (s) i η L̇w (θ0 ) + Z + γ1K−1 + γ1K−2 + · · · + 1 µ ni k s=1

q 2 where γ1 = 1 − η τ1 − C nHmin . Squaring and moving to expectations one obtains: E(∥θ(K) − θ0 ∥2 1E ) ≤ 3γ12K E∥θ(0) − θ0 ∥2   √ 2 m 2 3(1 − γ1K )2  2 2ηB K X ws (s)  η E L̇w (θ0 ) + E + Z (1 − γ1 )2 µN ns k s=1

≤ 3γ12K E∥θ(0) − θ0 ∥2 +

3 (1 − γ1 )2

η E

L̇(θ0 )

η 2 B 2 Kd X ws2 + µ2 n2s

s=1

Since η ≥ 2τ12 , for sufficiently large N , we have γ1 ≤ 1 − τ1 /3τ2 , so that we have the rate: E

(K)

− θ0

τ1 ≤ 3 1− 3τ2

2K E∥θ

(0)

3 − θ0 ∥ + (1 − γ1 )2 2

η E L̇w (θ0 )

η 2 B 2 Kd X ws2 + µ2 n2s s=1

! .

2 log(dN ) −2 ), assuming To get the final rates, we choose K = log((1−τ −1 ) so that the first term is O(N 1 /3τ2 ) h i 2 E θ(0) − θ0 = O(d). For the second term, note that

 2 ni m X X 2 wi (i)  ∇ρ xj , θ0 E η L̇w (θ0 ) 1E ≤ η 2 E ni i=1

j=1

ni 2 wi2 X (i) 2 =η E ∇ρ xj , θ0 (since i.i.d.) 2 n i j=1 i=1 m 2 X wi (i) · trace Var ∇ρ xj , θ0 = η2 ni i=1 m X wi2 2 m X

= η trace(Σ)

i=1

Thus the overall rate becomes: E

θ(K) − θ0

m X w2

η 2 B 2 Kd X wi2 i η 2 trace(Σ) + ni µ2 n2 i=1 i=1 i ! m m X 16η 2 wi2 B 2 Kd X wi2 ≤ 2 trace(Σ) + ni µ2 τ1 n2 i=1 i=1 i m 16η 2 X 2 trace(Σ) B 2 Kd = 2 wi + 2 2 ni τ1 i=1 µ ni 4 ≤ (1 − γ1 )2

q 2 where the second last line uses the assumption that 1 − γ1 = ητ1 − Cη HN ≥ 12 ητ1 . P Note that the above MSE bound holds for any w := {(w1 , . . . , wm ) ∈ [0, 1]m : wi = 1}. We can thus minimize over all possible w to find ŵi ∝

trace(Σ) B 2 Kd + 2 2 ni µ ni

−1

and the corresponding MSE E

(K)

− θ0

16η 2 ≤ 2 τ1

m X trace(Σ) i=1

B 2 Kd + 2 2 µ ni

−1 !−1 .

To finish the proof we write E

θ(K) − θ0

2 1E c ≤ 2E θ(K) − θ(0) 1E c + 2E∥θ(0) − θ0 ∥2 P(E c )  ≤ 2 E θ(0) +

K X

1/2

(θ(k) − θ(k−1) ) 

k=1

≤ 2CK

d mB 2 dK + N N 2 µ2

C Cd + 4 4 N N

p P(E c ) + 2E∥θ0 − θ(0) ∥2 P(E c )

for some constant C > 0. Here we use the triangle inequality at each gradient descent iteration and bound the fourth moment of the gradient h i sum and noise added due to privacy. Thus the 2 (K) MSE contribution from E θ − θ0 1E c contributes a smaller order term, so that the final rate is given by the term reported in the theorem statement.

Proof of Lemma 3.4 . In stage 1, the clients perform the following iterations ni η1 X (t+1) (t) (i) (t) θi = θi − g(xj , θi ) + ai Zit , ni j=1

Zit ∼ N (0, Id ),

√ 2Bη1 2K1i . ai = µni

As discussed before GSgi = 2B ni . Let µi be the DP for client i in stage 1. Then, √ √ 2Bη1 2K1i 2Bη1 K1i = , n i µi µni implies µi = √µ2 . In stage 2, we run K2 steps of AG1 with θ̄ as initializer and noise multiplier √

2 b′ = 2Bµn2K . From the proof of Lemma 3.1, we have GS as 2B ni . Hence i

√ √ 2B K2 2B 2K2 µ = ⇒ µi = √ . n i µi µni 2 Therefore, by the composition theorem in Dong et al. [2022], the clients are µ-GDP to the server. It follows immediately from the Proof of Lemma 3.1, that for stage 2, the server’s DP to a √ third party of µ/ 2m. For stage 1, following the proof of Lemma 3.1, we obtain a DP bound of √ µ/ 2m. Therefore, the total GDP privacy for the server to a third party can be bounded by µ √ . m

Proof of Theorem 3.3. The proof follows the technique for bounding the MSE of θAG1 by replacing (L, L̇, L̈) by (Li , L̇i , L̈i ) to obtain: E

2 (k) θi − θ 0

16 ≤ 2 τ1

trace(Σ) dB 2 K1 + 2 2 ni µ ni

=: ri for all k ≥ K1i /2 and i = 1, . . . , m. (9)

The next step will be to follow the proof of Lemma 23 from Huang and Huo [2019] to bound (K ) the bias of θi 1 . Modifying (8) for the i-th client we have: (K ) θi 1 − θ 0 =

Z 1

I −η

L̈i ((1 − t)θ0 + tθ √ 2ηB K1 (s) − η L̇i (θ0 ) + Zk µni 0

(K1 −1)

)dt (θ(K1 −1) − θ0 )

so that Z 1 (K1 −1) (K1 −1) I −η L̈i ((1 − t)θ0 + tθi )dt (θi − θ0 ) 0 (K −1) = E I − η L̈i (θ0 ) (θi 1 − θ0 ) Z 1 (K1 −1) (K1 −1) + ηE [L̈i (θ0 ) − L̈i ((1 − t)θ0 + tθi )]dt (θi − θ0 ) 0 (K −1) (K −1) = I − η L̈0 (θ0 ) E(θi 1 − θ0 ) + ηE L̈0 (θ0 ) − L̈i (θ0 ) (θi 1 − θ0 ) Z 1 (K −1) (K −1) + ηE [L̈i (θ0 ) − L̈i ((1 − t)θ0 + tθi 1 )]dt (θi 1 − θ0 ) 0 (K −1) =: I − η L̈0 (θ0 ) E(θi 1 − θ0 ) + ηT1 + ηT2 .

(K ) E(θi 1 − θ0 ) = E

This implies (K1 )

(I − I + η L̈0 (θ0 ))E(θi

− θ0 ) =

(K −1) (K ) I − η L̈0 (θ0 ) E(θi 1 − θi 1 ) + ηT1 + ηT2

which by the definition of privatized gradient descent implies: (K −1) I − η L̈0 (θ0 ) E(L̇i (θi 1 )) + T1 + T2 (K −1) = I − η L̈0 (θ0 ) E(L̇i (θ0 )) + EL̈i (θ0 )(θi 1 − θ0 ) + Ξ + T1 + T2 (K −1) = I − η L̈0 (θ0 ) 0 + EL̈0 (θ0 )(θi 1 − θ0 ) + Ξ − I − η L̈0 (θ0 ) T1 + T1 + T2 (K −1) = I − η L̈0 (θ0 ) L̈0 (θ0 )E(θi 1 − θ0 ) + Ξ

(K ) L̈0 (θ0 )E(θi 1 − θ0 ) =

+ η L̈0 (θ0 )T1 + T2 (K1 −1)

where the Lipschitz condition on L̈0 (θi yields Z 1 ∥Ξ∥= ∥EL̈i 0

) and convergence of L̈i (θ) to L̈0 (θ) for ∥θ − θ0 ∥≤ c0

(K −1) tθ0 + (1 − t)(θi 1 )) − L̈i (θ0 )dt (K1 −1)

≤ 2 max ∥E(L̈i (tθ0 + (1 − t)(θi t∈[0,1]

(K1 −1)

(θi

− θ0 )∥ (K1 −1)

)) − L̈0 (tθ0 + (1 − t)(θi

(K −1)

(K1 −1)

+ ∥E(L̈0 (tθ0 + (1 − t)(θi 1 )) − L̈0 (θ0 ))(θi 2CH √ (K −1) ≤ √ × ri + CLip (E∥θi 1 − θ 0 ∥2 ) ni

(K1 −1)

)))(θi

− θ0 )∥+

− θ0 )∥

≤ C1 ri .

(10)

for a constant C1 > 0, where in the last step we used the assumption that H 2 ≤ C∗ trace(Σ) for some constant C∗ > 0. Note that by τ1 strong convexity of L̈0 (·), L̈0 (θ0 ) ≻ τ1 Id ,

I − η L̈0 (θ0 ) ≤ 1 − ητ1 .

Then following the recursion argument of the proof for θAG1 we have (K1 )

E(θi

3 τ2 (K /2) (1 − ητ1 )K1 /2 E(θi 1 − θ0 ) + 2 (CLip ri + ητ2 ∥T1 ∥+∥T2 ∥) τ1 ητ1 √ ri τ2 3 ≤ (11) × 2 + 2 (CLip ri + ητ2 ∥T1 ∥+∥T2 ∥) τ1 N ητ1

− θ0 ) ≤

(i)

To bound ∥T1 ∥ note that L̈0 (θ0 ) − L̈i (θ0 ) is independent of {Zk : 1 ≤ k ≤ K1 }. Then we can unroll the recursion from (8) to write: ∥T1 ∥ (K −1) = E L̈0 (θ0 ) − L̈i (θ0 ) θi 1 − θ0    1 −2 KX p (i) ≤ E  L̈0 (θ0 ) − L̈i (θ0 )  (I − η L̈(θ0 ))K1 −1−k (η L̇(θ0 ) + 4(ηB K1 /µni )Zk ) k=K1 /2

+ O(E∥L̈0 (θ0 ) − L̈i (θ0 )∥·E∥θ(K1 /2) − θ0 ∥2 )    1 −2 KX (I − η L̈i (θ0 ))K1 −1−k (η L̇i (θ0 ) ≤ E  L̈0 (θ0 ) − L̈i (θ0 )  k=K1 /2

+ O((E∥L̈0 (θ0 ) − L̈i (θ0 )∥2 ·E∥θ(K1 /2) − θ0 ∥4 )1/2 ) 1/2 2 1/2 ≤ η E L̈0 (θ0 ) − L̈i (θ0 ) E∥L̇i (θ0 )∥2 + O((E∥L̈0 (θ0 ) − L̈i (θ0 )∥2 ·E∥θ(K1 /2) − θ0 ∥4 )1/2 ) ≤

1 + ri Ctrace(Σ) · . τ2 ni

Next by Lipschitzness assumption on the Hessian L̈0 and by uniform convergence of L̈i (θ) to L̈0 (θ) for ∥θ − θ0 ∥≤ c0 we have: Z 1 ∥T2 ∥= ∥E

(K −1) [L̈i (θ0 ) − L̈i ((1 − t)θ0 + tθi 1 )]dt

0 (K1 −1) ≤ 2C1 E∥θi − θ0 ∥2 = 2C1 ri

(K −1) (θi 1 − θ0 )

∥

via an argument similar to (10). Plugging in the above bounds into (11) one obtains: 4 ≤ τ1

(K ) E(θi 1 − θ0 )

(1 + ri ) Ctrace(Σ) 3C1 ri + · . τ1 ni

Combining the bias bounds for i = 1, . . . , m we then have E(θ̄ − θ0 ) =

m X ni i=1

E(θi − θ0 )

12C1 X 5Cmtrace(Σ) ≤ ni ri + N τ1 τ12 N i=1

192C1 ≤ τ13

mtrace(Σ) B 2 d X K1i + 2 N µ N ni i=1

! +

5Cmtrace(Σ) τ12 N

(12)

where in the first inequality we use the assumption that ni are large enough so that ri ≤ 0.25 for all 1 ≤ i ≤ m. For the variance note that θ̄ is an average of M-estimators trained on independent datasets, so that: m

i=1

1 X 2 1 X 2 16 ni trace(Var(θi )) ≤ ni ri = 2 trace(Var(θ̄)) = 2 2 N N τ1

trace(Σ) mdB 2 K1 + N µ2 N 2

Thus the MSE for θ̄ becomes 2

E∥θ̄ − θ0 ∥2 = trace(Var(θ̄)) + E(θ̄ − θ0 ) 16 trace(Σ) mdB 2 Kmax ≤ 2 + C22 + N µ2 N 2 τ1

mtrace(Σ) dB 2 X K1i + 2 N µ N ni

!2 .

i=1

Proof of Lemma 3.6. We consider the FedAvg (AG3) method to be run for R rounds of communication, and each round consists of K local gradient steps. At round r, the local estimates from (K) the clients are denoted as θi,r . According to the FedAvg algorithm, the server then aggregates P (K) with weights wi = nNi to obtain θ(r) = m i=1 wi θi,r . Let D and D′ be neighboring global datasets differing in exactly one record. Let i⋆ denote the client whose dataset differs. For ease of notation, we denote, the each client empirical risk as ni 1 X (i) Fi (θ) = ρ(xj , θ). ni j=1

We couple the randomness by using the same Gaussian noises {Zit } under D and D′ . Then for all other clients, i ̸= i⋆ , the local iterates are identical (since the injected noise is also identical). Hence only client i⋆ contributes to sensitivity of the quantity server releases. ′ Let θ(t) and θ (t) denote the parameter values at iteration t, for client i⋆ under D and D′ respectively. The local update is θ(t+1) = θ(t) − η∇Fi⋆ (θ(t) ) + σi⋆ Zt . Since the noise is coupled, it cancels in the difference. Now we compute,

′

θ(t+1) − θ (t+1) = θ(t) − θ (t) − η(∇Fi⋆ (θ(t) ) − ∇Fi⋆ (θ (t) )) + η(∇Fi⋆ (θ (t) ; Di⋆ ) − ∇Fi⋆ (θ (t) ; Di′⋆ )). In the above expression, the second term is due to difference in gradients evaluated at θt and ′ θ (t) respectively, while the third term is due to the gradients differing between Di⋆ and Di′⋆ . By Assumption 2 on τ1 strong convexity and Assumption 4 on τ2 smoothness of Fi⋆ , we have the following (∇Fi⋆ (u) − ∇Fi⋆ (v))⊤ (u − v) ≥ τ1 ∥u − v∥22 ,

(13)

∥∇Fi⋆ (u) − ∇Fi⋆ (v)∥2 ≤ τ2 ∥u − v∥2 .

(14)

We now show that the gradient descent map T is contractive. For any u, v ∈ Rd , ∥T (u) − T (v)∥22 = ∥u − v − η(∇Fi⋆ (u) − ∇Fi⋆ (v))∥22 = ∥u − v∥22 +η 2 ∥∇Fi⋆ (u) − ∇Fi⋆ (v)∥22 −2η(∇Fi⋆ (u) − ∇Fi⋆ (v))⊤ (u − v). Using (13) and (14), we obtain ∥T (u) − T (v)∥22 ≤ ∥u − v∥22 +η 2 τ22 ∥u − v∥22 −2ητ1 ∥u − v∥22 = (1 − 2ητ1 + η 2 τ22 )∥u − v∥22 . Then we can write ∥T (u) − T (v)∥2 ≤ Cη ∥u − v∥2 , with suitable assumptions on the step size η such that Cη < 1. Changing one record changes the empirical gradient by at most 2B/ni⋆ , so ∥∇Fi⋆ (θ; Di⋆ ) − ∇Fi⋆ (θ; Di′⋆ )∥≤

2B . ni ⋆

′

Hence, defining δt := ∥θ(t) − θ (t) ∥, δt+1 ≤ Cη δt + η

2B . n i⋆

Since δ0 = 0, we obtain K−1

δK ≤ η

2B X (Cη )s . ni ⋆ s=0

Thus K−1

(K)

GS(θi⋆ ) ≤ η

2B X s Cη . n i⋆ s=0

Since only client i⋆ differs, the global sensitivity at the server is, (K)

GS(θ(r) ) ≤ wi⋆ GS(θi⋆ ) =

K−1

s=0

ni⋆ 2B X s 2Bη X s η Cη = Cη . N n i⋆ N

Now we turn to the noise propagation. Each noise term injected at step s propagates through the remaining gradient descent iterations. Since the gradient descent map T (θ) = θ − η∇F (θ) is Cη contractive, the contribution of a noise vector injected s steps earlier is attenuated by at most Cηs . Therefore the final iterate contains an effective Gaussian component with variance proportional to K−1 X σi2 Cη2s . s=0

After aggregation the noise standard deviation is v v uK−1 um uX uX (Cη )2s . sdround = t (wi σi )2 t s=0

i=1 √

Noting, wi σi = 2BηµNRK , we obtain √

v √ u K−1 X 2Bη RK m u t sdround = (Cη )2s . µN s=0

By the Gaussian mechanism characterization, PK−1 s µ GSround s=0 (Cη ) q P . =√ µround ≤ sdround Rm K K−1 (C )2s η s=0 We further note, PK−1

s s=0 (Cη ) q P ≤ 1, K−1 2s K s=0 (Cη )

by Cauchy-Schwarz inequality. Thus µround ≤ √ By composition for µ-GDP, µsrv ≤

√

µ . Rm

µ R µround = √ . m

Proof of Theorem 3.7. Fix the total number of communication rounds R ∈ N. Under Algorithm 3, in every round the Gaussian noise multiplier used by client i is √ 2Bη RK σi = , µni

i = 1, . . . , m,

which depends on the fixed value of R but does not depend on the round index r. We prove by induction on r ∈ {1, . . . , R} that E

θ(r) − θ0

16 ≤ 2 τ1

trace(Σ) 2mB 2 RKd + N µ2 N 2

C + 2 N

m trace(Σ) +

m X B 2 RKd i=1

µ2 n i

!2 . (15)

Since θ̂(AG3) = θ(R) , the theorem follows by taking r = R. Base case (r = 1). In round 1, all clients start from θ(0) , perform K local iterations, and the server aggregates m X ni (K,1) (1) θ = θ . N i i=1

This estimator has the same form as θ̄ in Lemma 3.3 with K1i = K and noise multipliers √ 2Bη 2RK σi = . Applying Theorem 3.3 yields (15) for r = 1. µni Inductive step. Assume that (15) holds for some r ∈ {1, . . . , R − 1}. We show that it also holds for r + 1. At the beginning of round r + 1, all clients are initialized at the common value θ(r) , perform K local iterations, and the server aggregates θ(r+1) =

m X ni i=1

(K,r+1)

θi

Consequently, conditional on the shared initialization θ(r) , θ(r+1) has the same form as the estimator θ̄ in Theorem 3.3 with noise multipliers √ 2Bη RK . σi = µni Applying Theorem 3.3 at round r + 1, we obtain E

(r+1)

− θ0

(r)

16 ≤ 2 τ1

trace(Σ) 2mB 2 RKd + N µ2 N 2

C + 2 N

m trace(Σ) +

m X B 2 RKd i=1

!2 .

µ 2 ni

By the law of total expectation, E

(r+1)

− θ0

2 (r+1) (r) =E E θ − θ0 θ ,

which implies E

(r+1)

− θ0

16 ≤ 2 τ1

trace(Σ) 2mB 2 RKd + N µ2 N 2

C + 2 N

m trace(Σ) +

m X B 2 RKd i=1

µ2 n i

!2 .

This is (15) for r + 1. By induction, (15) holds for all r ∈ {1, . . . , R}. When r = R we obtain the desired bound for θ̂(AG3) = θ(R) . √ Proof of Lemma 3.8. We design the first step of the method (FedAvg) to be µ/ 2−GDP. From √ √ 1 2RK the proof of Lemma 3.4, the noise level σi = 2Bηµn = 6Bη1µni2RK guarantees the FedAvgstep i /3 √ to be µ/ 2−GDP. Then we only need to find the desired noise level for the second (Newton) step to be √ µ/ 2−GDP. To calculate the sensitivity level of the Newton procedure, we note that from

triangle inequality, H −1 g − H ′−1 g ′ ≤ H −1 − H ′−1 · ∥g∥ + H ′−1 · g − g ′ 6B 1 2 ·B+ ≤ · ni /3 τ1 τ1 ni 12B ≤ τ1 ni Then √ 12B 2B (N ew) 6 2B τ1 ni (N ew) = µ ⇒B = √ µni τ1 2 √ Therefore the Newton step with the given noise level is µ/ 2− GDP.

Proof of Theorem 3.9. The proof follows along the lines of the bound for MSE of θ̄, through a bias variance decomposition. To that end, we find an upper bound for the bias of the private Newton step estimators first. Note that: (N ew)

θi

2B (N ew) (1) −1 (2) Zi , = θ̄ − L̈i (θ̄, Xi ) L̇i (θ̄, Xi ) + µni

so that (N ew)

θi

2B (N ew) (1) −1 (2) − θ0 = θ̄ − θ0 − L̈i (θ̄, Xi ) (L̇i (θ0 , Xi )) + Zi µni Z 1 (1) −1 (2) − L̈i (θ̄, Xi ) L̈i (tθ̄ + (1 − t)θ0 , Xi )dt (θ̄ − θ0 ) 0 Z 1 (1) −1 (2) = Id − L̈i (θ̄, Xi ) L̈i (tθ̄ + (1 − t)θ0 , Xi )dt (θ̄ − θ0 ) 0

(1)

− L̈i (θ̄, Xi ) (i)

(i)

−1

(2)

(L̇i (θ0 , Xi )) +

2B (N ew) Zi µni

(i)

=: Tn1 + Tn2 + Tn3 . We now bound the norms of each of the above terms one by one. (i) ∥Tn1 1E ∥=

≤

(1) −1 L̈i (θ̄, Xi )

Z 1 (1) (2) L̈i (θ̄, Xi ) − L̈i (tθ̄ + (1 − t)θ0 , Xi )dt (θ̄ − θ0 ) 0

× (1) (1) τ1 − ∥L̈i (θ̄, Xi ) − L̈0 (θ̄, Xi )∥ Z 1 (2) L̈0 (θ̄) − L̈0 (tθ̄ + (1 − t)θ0 , Xi )dt × 0

(k) +2 sup ∥L̈i (tθ̄ + (1 − t)θ0 , Xi ) − L̈0 (tθ̄ + (1 − t)θ0 )∥ t∈[0,1],k∈{1,2}

≤

2 C H ∥θ̄ − θ0 ∥2 + ∥θ̄ − θ0 ∥· √ τ1 τ1 ni

∥θ̄ − θ0 ∥ (16)

where we use the fact that CH (2) (2) ( sup ∥L̈i (tθ̄ + (1 − t)θ0 , Xi ) − L̈0 (tθ̄ + (1 − t)θ0 , Xi )) ≤ √ . ni t∈[0,1] (1)

(1)

with high probability over the event E, on which uniform convergence of L̈i (θ, Xi ) to L̈0 (θ, Xi ) for θ = tθ̄ + (1 − t)θ0 , for t ∈ [0, 1]. As a result on the same high probability event E we have the upper bound (N ew) (i) (i) (i) (i) − θ0 ) ≤ E(Tn1 1E ) + +E(Tn1 1E c ) + E(Tn2 ) + E(Tn3 ) E (θi (i)

(i)

= E(Tn1 1E ) + E(Tn1 1E c ) Here the first equality follows due to sample splitting which ensures (1) −1 (1) −1 (2) (i) ·0=0 E(L̇i (θ0 , Xi )) = E L̈i (θ̄, Xi ) E(Tn2 ) = E L̈i (θ̄, Xi ) (i)

and since the privacy noise are mean zero Gaussians, it is immediate to see that E(Tn3 ) = 0. Notice that due to sample splitting we have (i) E(Tn1 1E )

Id −

(1) −1 L̈i (θ̄, Xi )

Z 1

(2) L̈i (tθ̄ + (1 − t)θ0 , Xi )dt

(θ̄ − θ0 )

0 C (1) −1 (2) 2 ≤: E∥θ̄ − θ0 ∥ + E Id − L̈i (θ0 , Xi ) L̈i (θ0 , Xi ) (θ̄ − θ0 ) τ1 CH C ≤ E∥θ̄ − θ0 ∥2 + √ E∥(θ̄ − θ0 )∥+Cd exp(−cd/2) τ1 ni

where the first inequality follows due to the Lipschitz property of ∇2 ρ, and the second inequality (1) using concentration bounds of the sample Hessian L̈i (θ0 , Xi ) to its expectation L̈0 (θ0 ) on the event E. We then have ! m X ni (N ew) E θ − θ0 N i i=1 ! X m X ni H ni (i) C 2 ·√ (∥E(θ̄ − θ0 )∥) + E T 1E c ≤ E∥θ̄ − θ0 ∥ +C τ1 N ni N n1 i=1 r p C m ≤ E∥θ̄ − θ0 ∥2 +C (∥E(θ̄ − θ0 )∥) + Cd P(E c ) τ1 N r p C m 2 ≤ E∥θ̄ − θ0 ∥ +C (∥E(θ̄ − θ0 )∥) + Cd P(E c ) τ1 N r C m ≤ E∥θ̄ − θ0 ∥2 +C (∥E(θ̄ − θ0 )∥) + Cd exp(−cd) τ1 N (i)

where the last term in the second last line follows by using the definition of Tn1 to get the (i) bound E∥Tn1 ∥≤ Cd for all i. The last line follows since P(E c ) ≤ C exp(−cd) for some constant c, C > 0.

Similarly for the variance we have !! m X n i (N ew) θ trace(Var(θ̄(2) )) = trace Var N i i=1 !! !! !! m m m X X X ni (i) ni (i) ni (i) ≤ 2trace Var T + 2trace Var T + trace Var T . N n1 N n2 N n3 i=1

i=1

where we use the fact that Tn3 is composed of privacy noise and is hence independent of Tn1 and Tn2 . Note that by (16) and using the bound on P(E c ) we have trace Var

m X ni i=1

!! (i) Tn1

!2 m √ 2 X n CH 4 i ≤ 2 E∥θ̄ − θ0 ∥4 + 2 · E∥θ̄ − θ0 ∥2 · + Cd exp(−cd) N τ1 τ1 i=1 ≤

2 4 4 CmH E∥ θ̄ − θ ∥ + · E∥θ̄ − θ0 ∥2 . 0 τ12 N τ12

(1)

Next, since maxi ∥L̈i (θ̄, Xi )∥≤ Cτ1−1 on E, by a similar decomposition into E and E c we have !! m X ni (i) T trace Var N n2 i=1 !!! !!! m m X X C ni (i) ni (i) T |θ̄ + trace Tn2 |θ̄ + Cd(exp(−cd) ∧ N −4 ) ≤ trace E Var 2 Var E N n2 N τ 1 i=1 i=1 !!! m 2 X C ni (2) ≤ 2 trace Var(L̇i (θ0 , Xi )) + 0 + Cd(exp(−cd) ∧ N −4 ) 2 N τ1 i=1 ! m X C n2i trace(Σ) = 2 trace · N2 ni τ1 i=1

≤

Ctrace(Σ) + Cd(exp(−cd) ∧ N −4 ). N τ12 This implies E(∥θ̄(2) − θ0 ∥2 |) ≤

C 12m(B (N ew) )2 d 4 Ctrace(Σ) E∥ θ̄ − θ ∥ + + 0 τ 2N µ2 N 2 τ12 m C mH 2 2 2 2 + 2 (E∥θ̄ − θ0 ∥ ) + (E∥θ̄ − θ0 ∥ ) · N τ1

One can follow the proof of Theorem 3.3 to show that E∥θ̄ − θ0 ∥4 ≤ C(E∥θ̄ − θ0 ∥2 )2 so that, now

using Theorem 3.3 we have E(∥θ̄(2) − θ0 ∥2 ) ≤

Ctrace(Σ) 12m(B (N ew) )2 d + µ2 N 2 τ12 N CmH 2 + 2 3 τ1 N

µ4 n2i i=1 ! m 4 d4 X B 8 K1i 4 4 3 m (trace(Σ)) + m µ8 n4i i=1

C τ12 N 4 ≤

m2 (trace(Σ))2 + m

m X B 4 K 2 d2

Ctrace(Σ) 12m(B (N ew) )2 d + µ2 N 2 τ12 N

where we use the assumption that trace(Σ) ≤ d, H 2 ≤ Cd, and m3 d2 ≤ N 2 to ensure that the first term dominates over the third and fifth terms. Similarly, the fourth term can be bounded as m

2 2 d2 Cm3 d2 B 4 Kmax Cm2 H 2 X B 4 K1i ≤ · τ12 N 3 i=1 µ4 n2i τ12 N 3 µ4 n2min

Cm2 Kmax m(B (N ew) )2 d B 2 Kmax d · · µ2 N 2 τ12 N µ2 n2min

≤

Cm(B (N ew) )2 d µ2 N 2

where we use the assumptions m ≤ µ bounded as:

(17)

√ N n2min /(CKmax B d). The sixth term can again be

4 4 d4 Cm3 X B 8 K1i Cm4 d4 B 8 Kmax ≤ · 2 4 2 4 τ1 N 4 i=1 µ8 ni τ1 N 4 µ8 nmin

2 2 m2 (B (N ew) )4 d2 B 4 Kmax Cm2 d2 Kmax · · µ4 N 2 τ12 N 2 µ4 n4min

≤

Cm(B (N ew) )2 d µ2 N 2

√ √ 4/3 4/3 provided m ≤ µ2 nmin N 2/3 /(CdB 2 Kmax ) which follows if B = C( d ∨ log N ) and 4/3

m≤

µ4/3 nmin

· 4/3

d1/3 (d ∨ (log N ))Kmax

µ2/3 N 2/3 = Cd2/3

√

n2min µ2 2 d(d ∨ log N )3/2 Kmax

2/3

N 2 µ2 md2

1/3

· m1/3 /C

i.e., n2min µ2 m≤ √ · 2 C d(d ∨ log N )3/2 Kmax

N 2 µ2 md2

4/3

which is implied by m ≤ µ2 (N n2min )2/3 /(C(d ∨ log N )2 Kmax ). The final rate thus becomes E(∥θ̄(2) − θ0 ∥2 ) ≤

Ctrace(Σ) 12md2 + 2 2 µ N τ12 N

√ √ when B = C( d ∨ log N ). The sharper bound that coincides with Theorem 3.2 follows by first noting that m X trace(Σ)

1 τ12

i=1

2C 2 d2 log(dN ) + 2 2B µ ni log(1 − τ1 /3τ2 )

−1 !−1

Cd2 2 2 i=1 (dni ∧ (ni µ /K1i ))

≤ Pm

for a constant C > 0 and by choosing the Newton step aggregation weights to be ŵi ∝ m X 2 d2 K −1 CB d + with ŵi = 1. One can then follow analogous algebraic steps after (17) 2 2 ni µ n i

i=1

2 )1/3 . We omit the details for brevity. with m ≤ (µ2 n2min N/(d ∨ log N )3 Kmax

Proof of Theorem 3.10. From Corollary 1 in Dong et al. [2022] we have that an estimator θ̂ is µ-GDP if and only if it is (ε, δ(ε))-DP where ε ε µ µ δ(ε) = Φ − + − eε Φ − − µ 2 µ 2 Let ε = cµ where µ → 0 and c =

p 2 log µ−1 → ∞. Then

µ µ δ(cµ) = Φ −c + − ecµ Φ −c − 2 2 2 = µ(ϕ(c) − cΦ(−c)) + O(µ ) 1 = µϕ(c) 2 + O(c−4 ) + O(µ2 ) c ϕ(c) = µ 2 (1 + o(1)) c 2 µ e−c /2 = √ (1 + o(1)) 2π c2 µ µ µ2 √ = √ (1 + o(1)) = (1 + o(1)) 2π c2 2π c2 µ2 = √ (1 + o(1)). 2 2π log(1/µ) We will now use the technique for deriving lower bounds under distributed (ε, δ)-privacy as done in Cai et al. [2024], Auddy et al. [2024], Xue et al. [2024]. Let P be the set of all distributions satisfying assumptions 1 to 4. In particular, P contains Pθ , the set of joint distributions on (x, y) with x ∼ N (0, Id ) and the following generalized linear model on y|x. ⊤ x θy − ψ(x⊤ θ) ; ∥x∥∞ ≤ B pθ (y|x) := h(y) exp c satisfying max{ψ ′ (0), supu∈R ψ ′′ (u)} ≤ L. For the lower bound, we will use the multivariate Van Trees inequality (see, e.g., Theorem 1 of Gill and Levit [1995], Lemma 4.3 of Cai et al. [2024]): 2

sup E∥θ̂ − θ∥ ≥

E∥θ̂ − θ∥2 ζ(θ)dθ ≥

Cd2 , trace(Eθ [IF (T ; θ)]) + IF (ζ)

where ζ is a prior on θ supported on Rd , and Z Eθ [IF (T ; θ)] = IF (T ; θ) ζ(θ) dθ,

Z IF (ζ) =

1 ∥ξ ′ (θ)∥2 dθ. ξ(θ)

(18)

Here T is the final privatized transcript obtained after R rounds of communication between the clients and the server. The above result holds under some regularity conditions, for every estimator θ̂ = θ̂(T ) with E[∥θ̂ − θ∥2 ] < ∞ under the joint law of (T, θ). Following the proof of Proposition 10 of Xue et al. [2024], let us define M (r) :=all information shared from server to clients in r rounds (r)

(r)

(r−1) ), private transcript from client s in round r. Ts(r) :=Ts(r) ({(Xj , yj ) : 1 ≤ j ≤ n(r) s }, M

Here 1 ≤ s ≤ m and 1 ≤ r ≤ R. Note that by sample splitting, the random variables (r) (r) (r) {(Xj , yj ) : 1 ≤ j ≤ ns } are independent for 1 ≤ s ≤ m and 1 ≤ r ≤ R. Then by using conditional expectations, similar to equation 56 in Xue et al. [2024] we have

IF (T ; θ) =

m X R X

IF (Ts(r) |M (r−1) , (θ)).

(19)

s=1 r=1

By the definition of Fisher information, we have IF (Ts(r) |M (r−1) , (θ)) = EE[S(Ds(r) )|Ts(r) , M (r−1) ]E[S(Ds(r) )|Ts(r) , M (r−1) ]⊤ (r)

(r)

where S(Ds ) denotes the score function w.r.t. θ on Ds := {(Xj , yj ) : 1 ≤ j ≤ ns }. The crux of the paper is supplied by Lemma 4.2 of Cai et al. [2024] and its use in the proof of Proposition 12 of Xue et al. [2024]. It is thus enough to check their conditions. By our assumptions on bounded covariates and link function ψ, we can ensure that the score function: ∇θ log pθ (y, x) = (y − ψ ′ (x⊤ θ))x is sub-Gaussian with sub-Gaussianity parameter Cd for some constant C > 0. We can then follow the proof of Proposition 12 in Xue et al. [2024] to write: trace(IF (Ts(r) |M (r−1) , (θ))) = trace(EE[S(Ds(r) )|Ts(r) , M (r−1) ]E[S(Ds(r) )|Ts(r) , M (r−1) ]⊤ ) 2 2 −1 ≤ C(n(r) s ) µ log(µ ).

We also have the non-private upper bound trace(IF (Ts(r) |M (r−1) , (θ))) ≤ Cdn(r) s , leading to the combined upper bound: 2 2 −1 (r) trace(IF (Ts(r) |M (r−1) , (θ))) ≤ C((n(r) s ) µ log(µ )) ∧ Cdns ).

which when added across s = 1, ..., m and r = 1, ..., R, together with (19) yields m X R X

IF (T ; θ) ≤

2 2 −1 (r) C((n(r) s ) µ log(µ )) ∧ Cdns ).

(20)

s=1 r=1

Following Xue et al. [2024] we choose the prior ζ to be N (0, Id ) truncated to [−1, 1]d . It can be checked that IF (ζ) ≤ Cd so that (18) and (20) together imply: Cd2

sup E∥θ̂ − θ∥2 ≥ P

(r) 2 2 (r) m PR −1 s=1 r=1 C((ns ) µ log(µ )) ∧ Cdns ) + Cd

for a constant C > 0. Note that

PR (r) 2 (r) 2 2 r=1 (ns ) ≤ ( r=1 ns ) = ns , thus implying:

d2 2 2 −1 s=1 C(ns µ log(µ )) ∧ Cdns ) + Cd d2 . ≥ Pm 2 2 −1 s=1 C(ns µ log(µ )) ∧ Cdns )

sup E∥θ̂ − θ∥2 ≥ Pm θ

Additional Simulation Results and Details

B.1

Logistic regression additional figures

(a) FedSGD, different ni

(b) FedHybrid, different ni

Figure 11: Empirical MSE results of DP version of FedSGD and FedHybrid under different local sample sizes in Logistic Regression. This section contains additional figures from the simulation study using logistic regression. These figures depict empirical MSE of the methods with an increasing number of clients for the case when the client sample sizes ni differ across the clients.

(a) FedAvg, different ni

(b) FedNewton, different ni

Figure 12: Empirical MSE results of FedAvg and FedNewton under different local sample sizes in Logistic Regression.

B.2

Poisson GLM simulation figures

(a) FedSGD, same ni

(b) FedSGD, different ni

(d) FedHybrid, different ni

Figure 13: Empirical MSE results of FedSGD and FedHybrid under Equal and different Local Sample Sizes in Poisson GLM.

(a) FedAvg, same ni

(b) FedAvg, different ni

(d) FedNewton, different ni

Figure 14: Empirical MSE results of FedAvg and FedNewton under Equal and different Local Sample Sizes in Poisson GLM.

(a) FedSGD

(b) FedHybrid

(d) FedNewton

Figure 15: The empirical MSE of the methods with increasing number of iterations illustrating the tradeoff between optimization quality and privacy under Poisson GLM.

(a) Equal ni

(b) Uniformly distributed ni

Figure 16: MSE comparison of FedSGD, FedHybrid, FedAvg, and FedNewton under fixed total sample size N = 20000 with varying number of clients m in Poisson GLM: (a) equal local sample sizes, (b) uniformly distributed local sample sizes, and (c) lognormally distributed local sample sizes.

Record · ID 200490 · SHA-256 dce161456450be84
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.