On Using Secure Aggregation in Differentially Private Federated Learning with Multiple Local Steps
Authors: Mikko A. Heikkilä
Venue: Accepted by TMLR ()

Abstract: Federated learning is a distributed learning setting where the main aim is to train machine learning models without having to share raw data but only what is required for learning. To guarantee training data privacy and high-utility models, differential privacy and secure aggregation techniques are often combined with federated learning. However, with fine-grained protection granularities, e.g., with the common sample-level protection, the currently existing techniques generally require the parties to communicate for each local optimization step, if they want to fully benefit from the secure aggregation in terms of the resulting formal privacy guarantees. In this paper, we show how a simple new analysis allows the parties to perform multiple local optimization steps while still benefiting from using secure aggregation. We show that our analysis enables higher utility models with guaranteed privacy protection under limited number of communication rounds.

Published in Transactions on Machine Learning Research (03/2025)
On Using Secure Aggregation in Differentially Private Feder- ated Learning with Multiple Local Steps
Mikko A. Heikkilä
mikko a hhelkalaaelsssssiiiii
Deportment of Computer Science
University of Helsinki"
Reviewed on OpenReview: https: openreview. net/ forun? id= wayWlXPuIg
Abstract
Federated learning is distributed learning setting where the main aim is train machine learning models without having to share data but only what is required for learning. To guarantee training data privacy and high-utility models, differential privacy and secure aggregation techniques are often combined with federated learning. However, with fine- grained protection granularities, e.g., with the common sample-level protection, the currently cxisting techniques gencrally roquire the parties to communicate for each local optimization step, if they want to fully benefit from the secure aggregation in lerms of the resulting formal privacy guarantees. In this paper, we show how a simple new analysis allows the parties to perform multiple local optimization steps while still benefiting from using secure aggregation. We show that our analysis enables higher utility models with guaranteed privacy protection under limited number of communication rounds.
1 Introduction
Federated learning (FL; McMahan et al. 2017 Kairouz et al. 2019 is a common distributed learning setting, where a central server and several clients holding their own local data sets collaborate to train a single global model. The main feature FL that the clients do not directly communicate data, but only what required for lcarning, c.g., gradients or updated model parameters dsscudo-rradeents
While FL satisfies the data minimization principle, i.e., only what is actually needed is communicated while the actual raw data never leaves the client, it does not protect against privacy attacks such membership
inference (Shokri et al.) 2017) or reconstruction (Fredrikson et al. 2014
Yoom et al. 2018). Instead, training
data privacy is commonly ensured by combining differential privacy
(DP; Dwork et. al. 2006b), a formal
privacy definition, and secure multiparty computation (MPC; Yao 1982
with FL (see, e.g., Kairouz et al.
2019
DP essentially robustness guarantee for stochastic algorithms, which guarantees that small perturbations to the inputs have small effects the algorithms' output probabilities. What constitutes small perturbation depends on the chosen protection granularity: the same basic DP definition anything from single sample to entire data set level. In turn, MPC protocols can be used to limit the amount of information an adversary has about computations. In FL, secure aggregation (SecAgg) protocols, a specialised form of secure computation that requires significantly less resources than general MPC, are commonly used for communicating model updates from the clients to the server. This approach enables provably better distributed DP (DDP) guarantees, that rely jointly on a group of clients, than is possible achieve by any single client in isolation.
be used for ensuring privacy
Under the general FL setup, two main alternat ives are commonly considered: cross-device FL and cross-silo FL (Kairouz et al. 2019 In cross-device FL, each client is assumed to have a small local data set, while the
Work done partly at Telefónica Research, Rarcelona.

---

Published in Transactions on Machine Learning Research (03/2025)
total number of clients is large, e.g., thousands millions. In the cross-silo case, the total number of clients is small, for example, dozen, but each client is assumed to have a larger local data set. In this paper, our running example is standard cross-silo differentially private FL (DPFL) where the clients communicate all updates to the server using SocAgg In this setting, the most useful DP protection granularity is typically something strictly more fine-grained than client-level: when clients are, e.g., different. hospitals or banks, there are typically several individuals in a single clients' local data set and the protection gramularity needs to match the use case.
While client-level gramularit in DPFL is, at least in principle, straightforward to combine with SecAgg, more fine-grained granularities such as sample-leeel DP can present problems: using existing techniques one has to choose between i) having DDP guarantees with less noise due to SecAgg but with all clients using only a single local optimization step per FL round, and ii) having more noisy local DP (LDP) guarantees that do not formally benefit from SecAgg while allowing the clients to do more local optimization stops per FL round. Both of these options have significant drawbacks: the amount of server-client communications is typically one of the first. bottlenecks that limit model training in FL, while LDP guarantees regularly require noise levels that heavily affect the resulting model utility. In this paper show that this trade-off is not unavoidable but can be largely remedied by simple new analysis of the problem.
Our Contribution
We present novel and simple theoretical privacy analysis showing when we can increase the number of local optimization steps in FL using fine-grained DP granularity, while still benefiting from DDP guarantees using a trusted aggregator.
We demonstrate empirically that the proposed approach can lead to large utility benefits (in terms of prediction accuracy and loss) without requiring any changes to the underlying algorithms under both iid and heterogeneous client data splits. In our experiments with limited number of global communication rounds, using convolutional neural network with Fashion MNIST data set as well as linear models on C-FAR-10 (using pre-trained model as feature extractor) and ACS Income data sets, we improve prediction accuracy roughly by 16% points, 4% points, and 4% points, respectively (corresponding to 23%, 5% and 5% improvements).
Our results point to mismatch between the current theoretical understanding of vanilla DPFL (standard DPFL with FedAvg) and practical results.
2 Related Work
There is a significant amount of existing work focusing on the general problem of combining DP with FL, although the focus has mostly been on the cross-device FL setting with user- or client-level DP. To the best of our knowledge, while the combination of DPFL with SecAgg is certainly not novel (see, e.g., Truex let al. 2019 Kairouz et al. 2019 Heikkilä el al. 2020 Stevens el al. 2022 Yang el al. 2023), there is very limited amount of work specifically on the privacy analysis when the clients do multiple local optimization steps with fino-grained DP and communicate the results via SecAgg. As far we know, the only directly relevant analysis is by Noble et al. 20222 who consider the Gaussian mechanism for sample-level DP in the cross-device setting without secure aggregation. Our main theorem (Theorem 4.6) can be seen as extending their result on the Gaussian mechanism to other DP mechanisms that are more suitable for combining with actual secure aggregation protocols.
Considering other existing work in more detail, we can distinguish some main lines of closely-related research. Besides the DDP approach we focus on, i.e., the combination of LDP noise with secure aggregation, the use
Instead of considering any specific SecAgg implementation, in this work we mostly assume an idealised trusted aggregator. We discuss practical implementations in Appendix A.4
"Note that (Trucx et al. 2019 Algorithm 4) also state a similar specialised version for the Gaussian mechanism, i.c., they use several local optimization stops with samplo-level DP and SocAgg in FL, while scaling the Gaussian noise for DDP cousidering all the clients. However, as also noted by Malekzadeh et 2021 , the approach of Truex et al. 2019 would require separate proof of privacy beyond what is actually provided the paper.
2

---

Published in Transactions on Machine Learning Research (03/2025)
of LDP mechanism by each client independently provides robust privacy with few assumptions, but generally results in worse utility (see, e.g., Kasiviswanathan et al. 2008 Truex et al. 2020). Another recently considered approach assumes a trusted server that is tasked with the DP noise addition, and does privacy accounting via the matrix mechanism (Zhang ct al.) 2024). This can be shown to improve the privacy-utility tradc-off compared lo standard DP-SGD under some assumptions, but is not directly compatible with the secure aggregation approach for DDP we focus on in this work.
Looking at somewhat more closely-related papers in terms of the general setting, there is plenty of work proposing novel learning methods for FL, assuming sample-lvel DP and LDP noise with SecAgg for improved DDP guarantees. While the existing work only uses a single local optimization step (sce, e.g., Heikkil et al. 2020: Malekzadeh et al. 2021; Stevens et al. 2022 Yang et al. 2023), our analysis can be leveraged in this setting to enable running multiple local steps generally for many such methods without requiring any other changes to the algorithms.
Another clear line of work has focused on introducing novel discrete DP mechanisms that can be used with additively homomorphic encryption techniques, which typically operate on the group of integers with modulo additions. Agarwal et al. (2018) proposed a binomial mechanism that provides DP using discrete binomial noise. Improving on the binomial mechanism, Canonne et al. (2020) proposed discrete Gaussian mechanism, while Agarwal et. al. (2021) introduced a Skellam mechanism and Chen et. al. (2022b) a Poisson-binomial mechanism, both of which improve on the discrete Gaussian, e.g., by being infinitely divisible distributions: the sum of Skellam SkellammPPisson-- biiiiooo--biooiiall distributed random variables is another Skellam/Poissor Poossson-binooiill binomial random variable. Our work is not focused on introducing new DP mechanisms, but our analysis allows for using many different DP noise mechanism. In particular, our analysis allows for using LDP noise with SecAgg including when using infinitely divisible DP mechanisms, such as the Skellam mechanism, with pseudo-gras grandd-gradeetss and fine- ahn-ggraindd DP protection level.
While our main focus is on privacy accounting with SecAgg under limited communication budget, there has also been considerable effort by the community to reduce the amount of required communication further by applying quantization ion to the gradients (Agarwal et al. 2018 Kairouz et al.] 2021 Agarwal et al. 2021 Chen le al. 2022b Jin et al. 2020 Chaudhuri et al. 2022 Guo et al. (022)) or by compressing the updates sent by the clients Triastcyn et al. 2021 Chen et al. 2022a).. In principle, any such technique for compressing the model updates compatible with SecAgg can also be directly combined with our privacy analysis. In contrast, benefiting from gradient quantization is not entirely straightforward as in our case the model updates are pseudo-gradients and not gradients. We leave a detailed consideration and comparison of the possible methods for reducing the required communictiin budget beyond what is possible by pushing more optimization steps to the clients for future work.
In summary, while many of the contributions cited above, e.g. novel DP mechanisms, are not limited to cross-device FL, all the experiments and use cases mentioned in the cited papers that are compatible with SecAgg and use multiple local steps only consider DDP with user- or client-level DP in cross-device FI. In contrast, we focus on more fine-grained DP granularities, namely on sample-level DP. As we discuss in Section g combining sample-level DP with multiple local steps and LDP noise with SecAgg for improved utility requires a novel privacy analysis. The main aim of this paper is to provide such an analysis.
While the currently existing theoretical convergence bounds for vanilla DPFL with FedAvg do not show any benefit. from increasing the number of local steps in DPFL (see Malekmohammadii et al. 2024 Theorem 3.2), we empirically demonstrate the utility of our analysis in Section after stating the results in Section 4 Our results clearly highlight the need for improving the thcoretical analysis of standard DPFL over what is shown by Malekmohanmadi et al. (2024) to understand when increasing the number of local steps is useful (compare this disagreement of empirical results and theory to the discussion by Mishhhenko et al. 2022 on the provable usefulness of local steps in vanilla non-DP FL).
3 Background
Federated learning (FL, McMahan et al. 2017 Kairouz et al. 2019) collaborative learning setting, where the participants include central server and clients holding some data. On each FL round, the server chooses
3

---

Published in Transactions on Machine Learning Research (03/2025)
group of clients for an update and sends them the current model parameters. The chosen clients update their local model parameters by taking some amount of optimization steps using only their own local data, and then send an update back to the server. The server then aggregates the client-specific contributions to update the global model. We use the standard federated averaging update rule: assuming w.l.o.g that clients == I,....., N have been selected at FL round i, and that client i sends an update 4 (pseudo-gradient) the updated global model Or is given by
N
8, = 8
(1)
N
3.1 Differential Privacy
We want to guarantee privacy of the trained model w.r.t. the training data, for which we use differential privacy (DP). Writing the space possible data sets as X := UnENd"" we have the following:
Definition 3.1. (Dwork et al. 2006b a Let >> 0 and d [0, A randomised algorithm A: x - O is (EP8)-DP if for every 2, x' E X"
1 2, and every measurable set C,
P(A(z) E E) S (FP(((()) E E)
where ~ is a neighbourhood relation. A is tightly (e, 6)-DP, if there does not exist 8' < 8 such that A is (E. When = O, we write e-DP and call it pure DP. The more general case (e, 5)-D called approzimate DP (ADP).
Definition 3.1 can be equivalently stated as a bound on the so-called hockey-stick divergence:
Definition 3.2. Let a > 0. The hockey-stick divergence between distributions P, Q is given by
Ha(PIl) = Enn (1081)) - a (1+) 1 EnQ
[200 q(())
1
(2)
1+
where [a]+ == max 0), AP is the Radon-Nikodyı derivative, and p, q are the densities of P, Q, respectively. áq In the rest of this paper, we assume that all the relevant densities exists.
It has been shown that a randomised algorithm A is (e,8)-DP iff sup H (((=))AA(())) s 6 Barthe et al. 2013 Barthe & Olmedo 2013).
Our main results do not depend on the exact neighbourhood definition, but in all the experiments we use the add/ aad/remove relation or unbounded DP, that is, x, x' E X are neighbours, if x can be transformed into x' by adding or removing a single protected unit from X. For the protection gramularity, although this is not strict limitation, we focus on the common sample-level DP, i.e., a single protected unit corresponds to single sample of data, As noted earlier, our analysis could be advantageous for anything more fine- fine-graine grained than client-level DP, c.g., clement-level DP (Asi et al. 2019) or even for individual-level when there are more than one individual in the clients' local data.
We also make use of dominating pairs:
Definition 3.3. (Zhu et al.) 2022 A pair of distributions (P,Q) is dominating pair for a stochastic
algorithm A, if for all a 20
sup E. Sartt "
H. (A(z))A((E)) H. (PI(Q).
(3)
where Ha is the hockey-stick divergence (Definition 3.2
3.2 Problem with Local Steps in DPFL with SecAgg
While DP offers strict privacy protection, comes at the cost of reduced model utility. This is especially true in the local DP (T.P)) setting, where each client protects its data independently of any other party
4

---

Published in Transactions on Machine Learning Research (03/2025)
Kasiviswanathan al. 2008 One well-known technique to improve model utility in DPFL has been to utilise secure aggregation ASecAgg) to turn LDP guarantees into distributed DP (DDP) guarantees that depend on multiple clients (see, e.g., Kairouz et al. 2019) In effect, this means that when the clients are able to collaborate, they can jointly scale the locally used noise levels to reach a target DDP guarantee resulting in improved utility compared to the LDP guarantees. Even if the clients do not explicitly collaborate on calibrating the noise levels, the DDP guarantees resulting from using SecAgg will nevertheless be stronger compared to the LDP guarantees reached by each client individually.
However, naively combining fin-grainee DP protection with SecAgg for DDP runs into problems, we demonstrate in the rest of this section. For convenience, we give the pscudo-code for running standard DPFL with sample- and user-level DP protection in Appendix A.2
Starting with the umproblematic case of client-level DP, writing TA for an ideal trusted aggregator and using the well-known Gaussian mechanism (Dwork et al. 2006a) for simplicity, one can get DDP guarantoes for any number of local optimization steps with the following update:
N TA
0. 0
1 N
Σ
dipe dipc +(())
(4)
where the sum inside TA is done by a trusted aggregator, clipe ensures that each client-specific update has fz-norm bounded by the constant C, and { is Gaussian noise s.t. Σ e gives the DDP protection level we are siming for. As the clipping and noise are applied directly to the updated weights after the local optimization has finished, the privacy protection is not affected by the number of local optimization steps client i is using to arrive at A before applying DP.
There is also a simple approach that works with more fine-grained gramularities, when the clients use a single local optimization step with common learning rate y and, for example, standard DP stochastic gradient descent (DP-SGD, Song et al. 2013) again utilising Gaussian noise: we can take A = -7(9 + ( where (1) is sum of clipped per-unit gradients (e.g. per-sample for sample-level DP) from client i, to have the update
9s
- N TA
e + 44))) Σ (
0, 0- 0,
55)
Looking at the sum in Equation 5 since each per-unit gradient has a common bounded norm and Gaussian noise is infinitely divisible, i.e., the summed-up noise another Gaussian, we can calculate the resulting privacy with standard techniques (see, e.g., Mironov et al. 2019 Koskela et al. 2020 Zhu al. (022). Now, if one tries to use the same reasoning with sample-level DP using S> 1 local optimization steps, the problem is that the sensitivity of the per-sample clipped gradicnts when summed over the local steps increases with S:
assuming [1g..112 S C, ,, S implies that || 1 21, S SC (Iriangle-neequalitt)) 4
In other words, trying to scale the noise over multiple local optimization steps naively ends up scaling the query sensitivity lincarly with the total number of steps, while the obvious problem in using only a single step per FL round is that the number of communication rounds is typically one of the main bottlenecks in FL (Kairouz et al. 2019
3.3 Trust Model
In this paper, we assume an hontst-but-curious (hbc) server and that all the clients are fully honest. The latter assumption can be easily generalised to allow for lbce clients with some weakening to the relevant. privacy bounds: with N (non-colluding) hbc clients, since any client could potentially remove its own noise from the aggregated results, the noise from the other N clients needs to guarantee the target DP level. In
Here, distinguish between local DP (LDP, each client guarantees DP for it's contribution locally and in isolation), distributed DP (DDP, group of clients jointly contribute to the resulting DP guarantces against outside advensaries without trusted central party) and centralised DP (CDP, trusted party guarantces DP for everyonc).
NNoe that, already mentioned in Section for the special case of Gaussian noise with trusted server, the analysis of Noble et al. (022) shows that can indeed avoid the problem and get valid DDP guarantees that improve on the LDP case.
5

---

Published in Transactions on Machine Learning Research (03/2025)
effect, to allow for all hbc clients, we would need to scale up the noise level somewhat (sce, e.g., Heikkilää et al. 2017 for discussion on the noise scaling and for formal proofs).
In principle, the same technique can also protect against privacy threats in the case of including some fully malicious clients in the protocol (i.e, simply scale the noise so that the hbc clients are enough to guarantee the required DP level). However, in this case the required level of extra noise will increase quickly with the number of malicious clients leading to heavier utility loss. With malicious clients, there would also be no guarantee that the learning algorithm terminates properly.
4 Privacy Accounting for Multiple Local Steps Using a Trusted Aggregator
Consider standard FL setting with M clients and client holding some local data aq. On FL round 6, N, clients are selected for updating by the server, w.l.ogg assumed to be clients i i N,. Each selected client
receives the current model parameters ((t-1) from the server, then runs S; local optimization steps using
DP-SGD with constant learning rate Yt, and finally sends an update to the server via a trusted aggregator T TA:
4,00 = 0000 1000-g(-11 g)(-1) =- Σ r + (
(6)
where we write Di,s for the per-unit clipped gradients of client i at local step 8, and E for the DP noise. After receiving all the messages via the trusted aggregator, the server updates the global model using FedAvg:
(1)
N TA No 2 A ())
gi0) B(t-1) +
(7)
In the rest of this section state our main results: we show that under some assumptions for privacy in FL by looking at the local optimization steps while benefiting from the noise added by all the clients on each step, even if there is no communication between the clients during the local optimization but only a single trusted aggregation at the end of the round to update the global model paramoters.
account
W.l.o.g. from now on we drop the FL round index and simply write, e-g. N instead of N, for the number of updating clients. Since the global updates do not access any sensitive data, once we can do privacy accounting for single FL round, which is the main topic in the rest of this section, generalising to T FL rounds can be done in a forair manner (see Appendix A.5
In the following, we assume that all clients have access to an ideal trusted aggregator, and that all sums are calculated by calling the trusted aggregator. We comment on more realistic implementations Appendix [A.4 after stating our main results.
We make the following assumptions throughout this section:
Assumption 4.1. Let x, E X I,...,N.. N. We write U 1 and assume that xy Oayy for every i 1, j, ie., there are overlapping samples in different clients' local data sets. We are interested in fixed-length optimization runs of S local steps (common to all clients), which leads to (fixed-length) adaptive sequential composition for privacy accounting (see e.g. Rogers et al. 2016 Zhu et al. 2022). We assume all clients use the same learning rate & and norm clipping with constant C when applicable. We also assume I....,N N are DP w.r.t. the first argument for any given
that all local DP mechanisms A!"",, 8 1,..,, S, auxiliary values (which we generally do not write out explicitly).
Note that we consider how to loosen many of these assumptions in Appendix A.3
Not all possible DP mechanisms might allow for improved DDP guarantees via simple aggregation. For convenience, in Definition 4.2 we define a family of suitable mechanisms, which we call sum-dominating:

---

Published in Transactions on Machine Learning Research (03/2025)
Definition 4.2 (Sum-dominating mechanism). Let A, - We call A sum-dominaling mechanism w.r.t. Ar, i = N,
-0, I,..., N be randomised algorithms.
sup Ha aotere
Σ A.
Σ Ar(1))
S sup H. (A(=))lA(z)) z
(8)
where Ho is the hockey-stick divergence, and is the DP neighbourhood relation. If additionally suparar Ha (A(z))lA(z") max,sup,-> sup Ha (A))))))AA then we call A a properly uun-dominating mechanism.
Looking Definition 4.2 in practice the interesting mechanisms for will be the properly sum-dominating mechanisms, these have improved privacy bounds compared to any single mechanism A; in isolation. However, from the following results only Theorem 4.7 is specilic to proper sum-dominating mechanisms. Considering concrete mechanisms that are properly sum-dominating, simple examples are given by the existing DP mochanisms that use infinitely divisible noise (see Definition A.1]. such as Skellam (Valovich & Agarwal et al. 2021), boisson-binomial CChen et al. 2022b), as well as the ubiquitous continuous 2006a
AIdà 2017
Gaussian Dwork
Erample 4.3 (Gaussian mechanism). Assume A, is a Gaussian mechanism with noise covariance C² Iaa and f has bounded sensitivity C. Since the normal distribution is infinitely divisible (Definition A.I). the combined mechanism A = Σim A; is another Gaussian with sensitivity C and noise covariance C² N Finally, due to well-known existing results (see e.g. Meiser & Mohammadi 2018 Koskela et al. 2020 Zhu ct al. 2022). a (tightly) dominating pair of distributions (P. Q) in the sense of Definition 3.3 for the sum- dominating mechanism A is given by a pair of 1d Gaussians with means μp = 0, H2 = 1, and variances i-1 a²- As the DP guarantees for the Gaussian improve when incrcasing the variance (Balle & Wang 2018), A is a properly sum-dominating mechanism w.r.t. to = 1...,, (Definition 4.2)
La-
of. = 0 -
Next, we consider composing sum-dominating mechanisms over S local steps. This allows us account for the total privacy when doing more than local optimization step:
Lemma 4.4. Assume A(s) is sum-dominating mechanism w.r.t. (a) == 1,..., N for every s= 1.....,
Then the composition of the sum-dominating mechanisms (A((), 1s)) dominates the composition
A
Σ
A (8)
Proof. For any E (1,...,)), we immediately have
sup Ha
Σ A
Σ
(1
< sup Ha (1)4 zozr!
(10)
by definition of A (Definition 4.2
The claim therefore follows immodiately from Zhu et al. 2022 Theorem 10).
Considering Lemma 1.4 in our case essentially says that to account for running S local optimization steps, it is enough to find sum-dominating mechanism for each step separately.
With the next result given in Lemina 4.5 we can connect the previous results with the form of output we get
from actually running local optimization in FL:
Discrete Gaussian (Canoune al. 2020 is not infinitely divisible, but close-enough that properly sun-dominating mechanism can still be found in many practical settings, see Kairouz al. 2021 In such cases, the incquality in Equation
could always be strict, whereas for the infinitely divisible noise mechanisms mentioned the text can be written as equality. We note that in this case, however, writing Equation with inequality necessary avoid nonsensical limitations, such as having DP mechanism that satisfies Definition 4.2 with given while not satisfying it any 8 > 8.
7

---

Published in Transactions on Machine Learning Research (03/2025)
Lemma 4.5. Assume that releasing the vector
Σ
A (5) (xi) (xi))
(11)
salisfies (e,6)-DP, Then releasing
N 8
(z:)
(12)
also satisfies (e, (P..
Due to the post-processing immunity of DP (see, e.g.. Dwork & Roth 2014), the assumption implies that releasing
Proof.
N
(x4)
(13)
s=1
satisfies (eDP) and by exchanging the order of summation the claim follows. Note that all the mechanisms are assumed to be DP w.r.t. their first argument for any given auxiliary value, which allows us to do the exchange without affecting privacy (in the context of FL, we effectively switch from communicating between each local step to running all local steps and then communicatin)).
Taken together, Definition 4.2 along with Lemmas
allow to compose DP mechanisms for DDP guarantees using LDP noise from multiple clients. In our main result given Theorem 4.6, we show that with (properly) sum-dominating mechanisms each client can run DP-SGD with several local steps and LDP noise while receiving (improved) DDP guarantees when communicating the update via a trusted aggregator.
Theorem 4.6. Assume clients use local noise mechanisms A ; N as in Definition 4.2 for each
local gradient optimization step L,..., and that the final aggregated update N A, is released via ideal trusted aggregator. Then denoting the dominatnng mechanism for step by A(o), the query release satisfies () for any å E [0, 1], when s(ő) is given by accounting for releasing the vector
where UN 104
Proof. For privacy accounting, assuming all sums are done by trusted aggregator TA, releasing the aggregated update TA(EE A;) corresponds to releasing the result
where each mechanism includes mapping that maps the local samples to the clipped per-unit gradients well as the DP noise, and 2i,s are auxiliary values (e.g,, state after the previous step) Since all mechanisms are assumed to be DP w.r.t. the first argument for any auxiliary value, the auxiliary values do not affect the DP guarantees, and hence we do not write them explicitly in the following.
From Lemma 4.5 it follows that valid DP guarantees can established by accounting for the release of the vector EN (a.). EM A (x:)) Furthermore, Definition 4.2 implics that for any step s 1, 1,
the sum-dominating mechanism (+) dominates ΣN A("), and therefore by Lemma 4.4 the claim follows. E
For example, with standard DP-SGD, sample-level DP and continuous Gaussian noise, ΣV Di= A:= ΣN Ee (g..
(..)), where Si.s (sums of) elipped per-sample gradients and &s,s are per-step Gaussian
8

---

Published in Transactions on Machine Learning Research (03/2025)
Considering properly sum-dominating mechanisms based on infinitely divisible noise, we also have the following theorem scaling the noise with multiple clients:
Theorem 4.7. In addition to the assumptions of Theorem 4.6, assume that each client uses a common noise level LDD for some mechanism based on infinitely divisible additine noise for each local step s.t. the DP noise SLDP for any given local mechanism A!"), -..,., I,...,,,5 ,, has covariance Li for some Ea. Then for quoranteeing given (c(5),)--DD) the required OLDP scales as O
Proof. Let O² be such that when accounting for the total of local steps, the composition of the sum- dominating mechanisms (A( ((9) is (e(6), From Definition A.1 it immediately follows that the required total noise can be broken into parts while staying in the same noise family to give
N
o²
a² = Σ LLDP + LLrP= $ OLDP
N
We note that similar scaling results as given in Theorem 4.7 for specific cases like the Gaussian mechanism are already well-known in the existing literature (see, e.g., Noble et al. 2022 Heikkilä et al. 2017).
is worth noting that since the accounting relies Lemma 4.5 which assumes releasing each local step while the actually released query answer is sum over the local steps, the resulting privacy bound need not be tight but an upper bound on the privacy budget. However, this matches the usual DP-SGD privacy accounting analysis (see e.g. Mironov et al. 2019 Koskela et al. 20200), which typically needs to account for each local optimization step duc to tochnical reasons even if only the final model is relcased. In the general case, it has also been shown that hiding the intermediate steps does not bring any privacy benefits compared to the per-slep accounting (Annamalai 2024].
Finally, considering tightness of the privacy accounting done based on Theorem 4.6
5 Experiments
Setup and Motivation: Our chosen settings try to mimic typical cross-silo FL setup: there are limited number of clients, each having a smallish local databasc. The clients have enough local compute to run optimization on the chosen model, while the number of server-client communications required for updating the global model are the main bottle-neck. Note that this bottleneck will emerge even with larger actual organisations training models with broadband connections, when the model size is large-enough, e.g., when training foundation models (Bommasani et al.) 2021). This is especially true when using SecAgg protocols, since the cost of running real SecAgg algorithm presents significant compute and communication overheads even with the efficient protocols discussed in Appendix A.4 In this setting, it makes sense to try and push more optimization steps to the clients while reducing the number of global updates (FL rounds). We also assume that the clients send their local updates via some trusted aggregator (which we only assume and do not implement in practice in the experiments. However, we do use only discrete DP mechanisms compatible with standard SecAgg algorithms in all the experiments). For more details on all the experiments, see Appendix A.6. The code for reproducing the results will be released on GitHub
CNN on Fashion-MNIST: We first train a small convolutional neural network (CNN) on Fashion MNIST 2017 that is distributed iid among 10 clients. We use the CNN architecture introduced by Papernot et al. 2021]; Tramer & Boneh (2021). Figure I shows the mean with standard error of the mean (SEM) over 5 repcats for test accuracy and loss with DP-SGD using Skellam noise (Agarwal et al. 2021 with 32 bits gradient quantization,.iee without quantization. We train the model for 20 FL rounds and varying number of local steps. Comparing the results for 1 local step as opposed to local epoch (~ 11 steps, but with different sampling fraction compared to baseline), it is evident that being able to take more local optimization steps (as allowed by Theorem 4.6 brings considerable utility benefits under fixed privacy and communication budgels.
dala (Xiao et al.
https://githhen http:////gthhhbccco///eieee///// Seckkggthh-ehgggae Saapee

---

Published in Transactions on Machine Learning Research (03/2025)
Test accuracy, 10 clients, CNN on Fashion MNIST Skellam mechanism, unbounded = 1, le -
Test loss, 10 clients, CNN on Fashion MNIST Skellam mechanism, unbounded 1, 1e 5
0.8
Local steps
2.0
step
0.7
epoch
Accuracy
0.6
1.5
Loss
0.5
0.4
Local steps
0.3
step
epach
0.2
1
5
10
15
20
10
15
20
FL round
FL round
(a) Test accuracy
(b) Test loss
Figure 1: CNN Fashion-MNIST, 10 clients, mean and SEM over 5 seeds. Rumning more local steps is clearly beneficial.
Linear Classifier Transformed CIFAR-10: Overall, assuming fixed privacy budget, might expect the benefits from being able to run more local steps to be more accentuated with more complex models and very limited communication budget, while for simple-enough models and more FL. rounds even few local steps could lead to good results. To test to what extent this is true for simple yet still useful models, we consider CIFAR-10 data Krizzevskyy 2009). Similar to Tramèr Bonch (2021), we take a ResNeXt-299 model (Xie et al. 2017 pre-trained with CIFAR-100 data (Krizhevsky 2009), remove the final classifier, and use a feature extractor transform the input data. We distribute the transformed CIFAR-10 data jid to 10 clients, and train linear classification layers from scratch for 10, 20, 40, 80 and 160 FL rounds using DP-SGD with Skellam noise, 32 bit gradient quantization, and more local steps (1 epoch 19 steps, but with different expected batch size compared to the baseline). The mean and SEM over 5 seeds of the best. results for each model over the training run are shown in Figure 2 The benefits of being able to run more than a single local steps are again clear; even with the relatively simple linear model, using local step needs roughly an order of magnitude more FL rounds over a fairly broad range of available communication budgets reach a similar performance compared to using local epoch.
Test accuracy, 10 clients, Linear on CIFAR-10 Skellam mechanism, unbounded = 1, 11-5=1e5
Test loss, 10 clients, Linear on CIFAR-10 Skellam mechanism, unbounded E = =, 5 le -
0.80
0.85
Local steps
step
0.80
epoch
0.78
Accuracy
0.75
0.76
0.70
0.65
0.72
Local steps
0.60
step
epoch
0.55
10a
102
10a
10a
FL round
FL round
Test accuracy
(b) Test loss
Figure 2: Mean and SEM over 5 seeds of the best performance over training runs for Lincar models on CIFAR-10 using pre-trained ResNeXi29 as feature extractor for varying nunber of FL rounds, 10 clients. Running more local steps clearly beneficial.
10

---

Published in Transactions on Machine Learning Research (03/2025)
Logistic Model on Income: To further test the robustness of the possible benefits from being able to more than single local optimization step, train simple Logistic Neural Network (LNN) model (i.e., l-layer fully connected linear classification network similar to the one used in the previous experiment, but without any pre-trained feature extractor) on ACS Income data (Ding et al., 2021p. Unlike the synthetic iid data splits used in the previous experiments, Income data has an inherent client split. corresponding states from where the data has been collected. Since the inherent split is heterogencous (different states have very different number of samples as well as different data distributions), we would expect the benefits of doing more local optimization steps between global communication rounds to dwindle, since the local models from different clients could diverge when only trained locally. However, setting taking more local steps can be very beneficial (here 1 epoch = 20 steps with same local sampling Traction compared to baseline). This clearly demonstrates the utility of our analysis.
shown in Figure 3 even in this
Test accuracy, 51 clients, Logistic Net on ACS Income Skellam mechanism, unbounded 1, le -
Test loss, 51 clients, Logistic Net on ACS Income Skellam mechanism, unbounded e 1,
0.775
Local steps
step
0.750
0.65
1 epoch
Accuracy
0.725
0.60
Loss
0.700
0.55
0.675
steps
0.50
0.650
epoch
0.625
2
6 FL round
10
2
6
10
FL round
(a) Test accuracy
(b) Test loss
Figure 3: LNN on ACS Income, 51 clients, mean and SEM over 5 seeds. Rumning more local steps is clearly beneficial.
Improved Privacy from Model Averaging: Finally, our results might sometimes be of use also outside standard FL. For example, consider a setting where we have N copies model trained on disjoint data sets (for example, think of independent parties learning a classifier on top a common pre-trained model or fine-tuning common pre-trained model; either scenario would usually lead to shared model structure and possibly also hyperparameters without explicit coordination), and the parties would like to combine the models post-hoc without rumning any joint training from scratch. Since this can be seen FL with single FL round, if the original model training on each party satisfies Assumption 4.1 (or the relaxed assumptions
in Appendix A.3). then simple averaging of the weights will result in a joint model with improved privacy guarantecs against adversarics without access to the original models.
To demonstrate this effect, we account for privacy assuming the same linear model used in Figure 2 (but without actually training any models), Skellam mechanism with 32 bit gradients, Poisson subsampling with sampling probability 0.1, and varying number of parties and local steps. The accounting is done as it would be done in a realistic sett intt we first. find noise level OLDP that results in the target privacy level (unbounded (e = 5, = le 5)-LDP) for each soparate model with the chosen number of local steps. We then assume that the local training satisfies Assumption 4.1 and calculate the privacy for averaging varying number of local models. Combining even 2 models results in clearly improved privacy for the averaged model (see Table in Appendix A.7
6 Discussion
In this paper we have shown how to combine multiple local stops in DPFL using fino-grained protection gramularities with SecAgg, and empirically demonstrated that this can bring considerable utility benefits under various communicationnoonstrreeo settings. Our experimental results stand in stark contrasts with
11

---

Published in Transactions on Machine Learning Research (03/2025)
the message from the currently existing theoretical bounds for vanilla DPFL with FedAvg Malekmohammadi et al. 2024 Theorem 3.2), which do not show any benefit. from increasing the number of local steps. This disagreement of experimental and theoretical results underlines the need for improved theoretical analysis to understand the conditions under which increasing the number of local steps can lead to improved utility, similar to the recent. breakthroughs in analysing non-DP FL (Mishchenko et al. 2022
Acknowledgments
This research was partially supported by: 1) The Ministry of Economic Affairs and Digital Transformation of Spain and the European Iioon-NextGeneratiionn programme for the 'Recovery, Transformation and Resilience Plan' and the 'Recovery and Resilience Mechanism' under agreements 151-063000-2021-117 2021-147 (6G-RIEMANN) and TSI-063000-2021-63 (MAP-6G), 2) 2020 program under grant agrecments 101140096435 (CONFIDENTIAL6G) and No.101139067 (ELASTIC), and 3) the European Lighthouse on Safe and Secure AI (ELSA) from the European Union's Horizon Europe program under grant agreement No 101070617. The views and opinions expressed are those of the authors only and do not necessarily reflect those of the European Union or other funding agencies. Neither the European Union nor the granting authority can be held responsible for them.
931-063000-2021-114
The European Union Horizon
References
Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Πya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi (eds.), Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austrio, October 24-28 2016, pp. 308 318. ACM, 2016. doi: 10.1145 00.1145/2976745 07777749.207 49.2978318. URL btttps://doi httpe::/ddioooo/////// org/ror.//// 11w11//9///779.... 2Tt.//9997779997.7111888 2978318
Naman Agarwal, Ananda Theortha Suresh, Felix X. Yu, Sanjiv Kumar, and Brendan McMahan. cpSGD: Commuiicttion-cffccenn and differentially-privaal distributed SGD. In Samy Bengio, Hanna M. Wallach, Hugo Tarochelle, Kristen Grauman, Nicolò Desa-Biaachh, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 7575-7586, 2018. URL http::://prooceecingg htt.://dwaaaabaetaaaaaarr......a
Naman Agarwal, Peter Kairouz, and Ziyu Liu. The Skellam mechanism for diffcrentially private federated learning. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advonces in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NewrIPS 2021, December 6- http:///w.....rpppps..o./////p/p
14. 2021, virtual, pp. 5052 5064, 2021. URL 2Bbbaccooffra.ddd4445922aaeeee Abstract. html
Meenatchi Sundaram Muthu Selva Annamalai. It's our loss: No privacy amplification for hidden state DP-SGD with non-convex loss. In Maura Pintor, Xinyun Chen, and Matthew Jagielski (eds.). Proceedings of the 2024 Workshop on Artificial Intelligence and Security, AlSec 2024, Salt Lake City, UT, USA, October 14-18, 2024, pp. 24-30. ACM, 2024. doi: 10. 10.1145//6899822334477. URL httts:///do..rg/111 1145/ 0199932.3694760
Hilal Asi, John C. Duchi, and Omid Javidbakht. Element level different privacy: The right granularity of privacy. CoRR, abs/ abs/1192.00444,, 2019. URL
04042
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässon, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 403 403-412 412. PMLR, 2018. http://proceedings. mlr. httpa//is.......peeees////////aa varess/800/baleiti html
URL
12

---

Published in Transactions on Machine Learning Research (03/2025)
Gilles Barthe and Federico Olmedo. Beyond differential privacy: Composition theorems and relational
logic for E-iveereecess between probabilistic programs. pp. 49 60. Springer Berlin Heidelberg, 2013. doi: 10.0007/978-33-622-99222 8. URL http://dx http::///x..di..r//1o....o. htt.:///o..////..00//////-----30 0010//1000007777-------22-22---1
Gilles Barthe, Boris Köpf, Federico Olmedo, and Santiago Zanella-Béguclin. Probabilistic relational reasoning for differential privacy. ACM Transactions on Programming Languages and Systems, 35(3):1 49, 2013. ISSN 0164-0925, 1558-4593. doi: 2..1445/449006.
James Henry Bell, Kallista A. Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. Secure single-server aggregation with logarthigai overhead. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna (ods.), CCS '20: 2020 ACM SIGSAC Conference on Computer and Communications Securily, Virtual Event, USA, November 9-13, 2020, pp. 1253 1269. ACM, 2020. doi: 10.1145/3372297. 3417885. URL lhttps://dot org/10. 10.....11513333220 3441788
Daniel J. Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Titouan Parcollet, and Nicholas D. Lane. Flower: A friendly federated learning rescarch framework. CoRR, abs/2000.143390 2020. URL httpss//arxis org/abs/2000 14390
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL available from wandb.com.
com/ Software
Rishi Bonunasani, Drew A. Hudson, Ehsan Adeli, Russ B. Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri S. Chatterji, Annie S. Chen, Kathleen Creel, Jared Quincy Davis, Dorottya Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea. Finn, Trevor Gale, Lauren F. Gillespie, Karan Goel, Noah D. Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho, Jenny Hong, Kyle Hsu, Jing Huang, Thomas Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, Omar Khattab, Pang Wei Koh, Mark S. Krass, Ranjay Krishna, Rohith Kuditipudi, and et al. On the opportunítics and risks of foundation models. CoRR, abs/2108.00 /2108.07258, 2021. URL https: pettpa//arriin http://axvvv.rr.g/ aba/ 2108.07258
Kallista A. Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, machine
Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for learning. In Bhavani Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu (eds.), , Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 November 03, 2017, pp. 1175-1191, ACM, 2017. doi: 10.1145 10.1145/3133965 011333313356333333333 URL https:://ai...o org/ 10. 1e111111/333563113100 3133982
Clément L. Canonne, Gautam Kamath, and Thomas Steinke. The discrete Gaussian for differential privacy. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Ticn Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL |nttps:// www.ellllbabttttttttaaaaa
Kamalika Chaudhuri, Chuan Guo, and Mike Rabbat. Privacy- compression for federated data analysis. In James Cussens and Kun Zhang (eds.), Uncertainly in Artificial Intelligence, Proceedings of the Thirly- Eighth Conference on Uncertainty in Artificial Intelligence, UAI 2022, 1-5 August 2022, Eindhoven, The Netherlands, volume 180 of Proceedings of Machine Learning Research, pp. 306-306.77 PMLR, 2022. URL https://proceedingg. mlr. wwwps//ee0//aaiie whw.uuuurhauuuuuiii/ 12a.. html
Wei-Ning Chen, Christopher A. Choquette-Choo, Peter Kairouz, and Ananda Theertha Suresh. The fundamental price of secure aggregation in differentially private federated learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 3056-3089. PMLR, 2022a. URL https: scctps://proceedingg .mrpingsssrrrrr.....r. mlr press/ v162/ chen22c. html
13

---

Published in Transactions on Machine Learning Research (03/2025)
Wei-Ning Chen, Ayfer Ozgur, and Peter Kairouz. The Poisson binomial mechanism for unbiased federated learning with secure aggregation. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 3490-3500 PMLR, 17-23 Jul 2022b. URL
https://proceedings mor.mmmm.mm. wwwpe/wwpsseeeeeeeeeeee wwtpe//2chhee..... .html
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring Adult: New datasets for fair machine learning. In Mare Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (cds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NewrIPS 2021, December 6- neurips. cc/paper/20000 2021/hash/
14, 2021, virtual, pp. 6478 6490, 2021. URL.
126441116311/fbbbba3333366333333 wws.ratttos-sttttttto..o.o.a html
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Comput. Sci., 9(3-4)2111-407, 2014.
Trends Theor.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Craplographic Techniques, pp. 486-56 503. Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin (eds.), Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer Science, pp. 265-284. Springer, 2006b. doi: 10.1007/1168133 14
14. URL
William Feller. An Introduction to Probability and Its Applications, Vol.2. John Wiley & Sons, Inc., 1966.
Matthew Fredrikson, Eric Lantz, Somesh Jha, Simon Lin, David Page, and Thomas Ristenpart. Privacy in pharmacogenetics: An End-to-End case study of personalized warfarin dosing. Proc USENIX Secur Symp, 2014:17 32, 2014.
Chuan Guo, Kamalika Chaudhuri, Pierre Stock, and Michael G. Rabbat. Privacy-aware compression for federated learning through numerical mechanism design. In Andreas Kranse, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlet (eds.), International Conference on Machine Learning, 1CML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Reseorch, pp. 11888- 11904. PMLR, 2023. URL https::/ppoceeeiiii html
mlr wwwppp/sss22.... gu0023a
Mikko A. Heikkilä, Eemil Lagerspetz, Samuel Kaski, Kana Shimizu, Sasu Tarkoma, and Antti Honkela. Differentially private bayesian learning on distributed data. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 3226 3235. 2017. URL httpss l/proceedings
www.eaaaaddd-ttttttttttcc html
Mikko A. Heikkilä, Antti Koskela, Kana Shimizu, Samuel Kaski, and Antti Honkela. Differentially private cross-silo federated lcarning. CoRR, abs/2007.055.. .05533, 2020. URL httpp:://aaddv.or/abb//////
Richeng Jin, Yufan Huang, Xiaofan He, Huaiyu Dai, and Tianfu Wu. Stochastic-sign SGD for federated learning with thcorctical guarantecs. ArXiv preprint, abs/ 100/2002.00940, 2020. URL https://arxiv.orr
0/0/20002.19944
Peler Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G L D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adríà Gascón, Badih Ghazi, Phillip Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar,
14

---

Published in Transactions on Machine Learning Research (03/2025)
Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateck Mittal, Mchryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang. Felix X Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. ArXiv preprint, abs//112.0445
2019. URL
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete Gaussian mechanism for federated learning with secure aggregation. In Marina Meila and Tong Zhang (eds.), Proceedings of the 98th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 5201-5212 PMLR, 2021. URL http://prroeeddnggs
mlr.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? ArXiv preprint, abs/0803.0024, 2008. URL httpps://axiv..ort http:///wwvv...r/a//////00/00 0924
Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using FFT. In Silvia Chiappa and Roberto Calandra (cds.), The 23rd International Conference on Artificial Intelligence and Stalistics, ATSTATS 2020, 26-28 August 2020, Online (Palermo, Sicily, Ialy), volume 108
of Proceedings of Machine Learning Research, pp. 2560 2569. PMLR, 2020. URL http://proceeddings html
mlr. ttress/v100/koskel//e
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009. URL httph::ttppww....: toronto edu/-kriz/cifar html
Saber Malekmohammadi, Yaoliang Yu, and Yang Cao. Noiso-aware algorithm for heterogencous differentially private federated learning. In Forty-first International Conference on Machine Learning. ICML 2024, Vienna, Austria, July 21-27, 2024. OpenRoview.net, 2024. URL https://openrevieet hetppperrriee.nnn//ouuuu wwt.feruumm/eeeeee FuQ2DRPAuy
Mohammad Malekzadeh, Burak Hasircioglu, Nitish Mital, Kunal Katarya, Mehmet Emre Ozfatura, and Deniz Gündüz. Dopamine: Differentially private federated learning medical data. CoRR, Abs/2101.11169) 2021. URL https://arxiv
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication- efficient learning of deep networks from decentralized data. In Aarti Singh and Xiaojin (Jerry) Zhu (eds.), Proceedings of the 20th International Conference Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 of Proceedings of Machine Learning Research, pp- 1273 1282. PMLR, 2017. URL http://proceedinng mlr. wwl...pres//vee httpa/////////aaaaaaaaaaaaa
H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canoda, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.nett net, 2018. URL https://opennreview Bett/forum?iddBJhhFFL d1d=BJ0hF1200b
Sebastian Meiser and Esfandiar Mohammadi. Tight on budget? Tight bounds for r-fold approximate differential privacy. pp. 247-264, New York, New York, USA, 2018 ACM Press. doi:
URL
http://dl.ca acm. org/citation wttp:ccodddddom....... http://d.....oo..e..oaooooooottt 32437655
lyya Mironov. Rényi differential privacy. In 30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Borbara, CA, USA, August 21-25, 2017, pp. 263-275. IEEE Computer Society, 2017. doi: 10.1109/CS$ LSLO0///SF//0 2017.111. URL 2017.1...1
CoRR, abs/1908. 10530, 2019. URL /1/.///00...0//1..11//////// 2017.11
llya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled Gaussian mechanism. wttp:///wwwr//aab//.....o 10530
Konstantin Mishchenko, Grigory Malinovsky, Scbastian Stich, and Peter Richtarik. ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally! In Kanalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International
15

---

Published in Transactions on Machine Learning Research (03/2025)
Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 15750-15769. PMLR, 17-23 Jul 2022. URL. https::/prroeedddgng mlr. http://wwww.....eeeeeeeeeeeeeeee /ttpss///112mmmshhcceeno22222 html
Maxence Noble, Aurélien Bellet, and Aymeric Dieuleveut. Differentially private federated learning on heterogeneous data. In Gustau Camps-Valls Francisco J. R. Ruiz, and Isabel Valera (eds.), International Conference on Artificial Intellgence and Stalistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Reseorch, pp. html
PMLR, 2022. URL https:
//proceedings.. mlr. wwtpss/vvi///ool.e/e.eeeep
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson. Tempered sigmoid activations for deep learning with diffcrential privacy. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirly Third Conference on Innovalive Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pp. 9312-9321. AAAT Press, 2021. URL htlLittts:://o/// baai.org. index htt//M///arrtice//veee///////
Ryan M. Rogers, Salil Vadhan, Aaron Roth, and Jonathan R. Ullman. Privacy odometers and filters: Pay-as- you-go composition. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (eds.), Advances in Newral Information Processing Systems 29: Annual Conference on Neural Infor- mation Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 1921-1929, 2016. (ttpsst wbt.r//ceebbstat....m html
César Sabater, Aurélien Bellet, and Jan Ramon. An accurate, scalable and verifiable protocol for federated doi: 10.1007/110994-02-000771.
differentially private averaging. Mach. Learn., 111(11):4249 4244249999994,, 2022.
URL
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, pp. 3 18. IEEE Computer Society, 2017. doi: 10.11.9//PP22117..1. URL
https://dbi. orgg 10. 11.00.109//1 1109/SP 2017.
Jinhyun So, Basak Güler, and Amir Salman Avestimehr. Turbo-aggregate: Breaking the quadratic aggregation barrier in secure federated learning. IEEE J. Sel. Areas Inf. Theory, 2(1):479-445) 489, 2021. doi: 10.1109/
SEATT:2001.3054611 URL ktttps://dot /00 1...191/JJAII. 2021 3054610
Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. Stochastic gradient descent with differentially private updates. In IEFE Global Conference Signal and Information Processing, GlobalSTP 2013, Austin, TX, USA, December 3-5, 2013, pp. 245 248. IEEE, 2013, doi: B0.1109/GLOBALLIIP2113...77 https://doi org/ 10. 1199//11lllbbs11 2013. 6736861
URL
Thomas Steinke. Composition of differential privacy & privacy amplification by subsampling. CoRR, abs/2210.00597, 2022. URL https:://ai. 10. 48550444885.0.222.0 2210.00590
Timothy Stevens, Christian Skalka, Christelle Vincent, John Ring, Samuel Clark, and Joseph P. Near. Efficient differentially private secure aggregation for federated learning via hardness of learning with errors. In Kevin R. B. Butler and Kurt Thomas (eds.), 31st USENIX Security Symposium, USENIX Securily 2022, Boston, MA, USA, August 10-12, 2022, pp. 1379 1395. USENIX Association, 2022. URL https: / wwwpw/wwwwwccccccc usenix....... http://oonrereeeeeaaaaaaaaaattaa stteretteiiiisteeennnsss stevens
Florian Tramèr and Dan Boneh. Differentially private learning needs better features (or much more data). In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenRevicw.nee 2021. URL https:://operreview wwtp::/nnneefoooooneeeeeeoee http://www....eeeeooomo/aaaaaaaa
Alcksci Triastcyn, Matthias Reisser, and Christos Louizos. DP-REC: private & commuication-cffiion federated learning. CoRR, hts/2111.05454/ 2021. URL
http///awwv...rr/a////111..... 251100
Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and Yi Zhou. A hybrid approach to privacy-preserving federated learning. Tn Proceedings of the 12th ACM Workshop
16

---

Published in Transactions on Machine Learning Research (03/2025)
on Artificial Intelligence and Security, AISec'19, 19, pp. 1-11, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450068339. doi:
URL https:://oi.orrg:/
1145/3388501.35777 33573770
Stacey Truex, Ling Liu, Ka Ho Chow, Mehmet Emre Gursoy, and Wenqi Wei. Ldp-fed: federated learning with local differential privacy. In Aaron Yi Ding and Richard Mortier (eds.), Proceedings of the 3rd International Workshop on Edge Systems, Analytics and Networking, EdgeSys SuroSSs 2020, Heraklion, Greece, April 27, 2020, pp. 61-66. ACM, 2020. doi: 10.1145 10.1145/3378679..3 333333377773393333 URL https: https://do30 1145/3378679 3394533
Filipp Valovich and Francesco Aldà. Computational differential privacy from lattice-based cryplography. In Jerzy Kaczorowski, Josef Pieprzyk, and Jacek Pomykala (eds.), Number- Theoretic Methods in Cryptology First International Conference, NuTMiC 2017, Warsaw, Poland, September 11-13, 2017, Revised Selected Papers, volume 10737 of Lecture Notes in Computer Science pp. 121-141. Springer, 2017. doi: 10.1007/
978-3-319- 31-22--0---66--11 8. URL
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: a novel image datasot for benchmarking machine learning algorithms. CoRR, abs/ 1708.07747, 2017. URL
Saining Xie, Ross B. Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural nelworks. In 2017 IEEE Conference on Computer Vision and Pallern Recognaition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pp. 5987 5995. IEEE Computer Society, 2017. doi: 10. 1ww.:/119///.... 2017 664
D0.109/CCVPR.2111
URL htttts://doi....
Yuchen Yang, Bo Hui, Haolin Yuan, Neil Gong, and Yinzhi Cao. PrivateFT.: Accurate, differentially private federated learning via personalized data transformation. In 32nd USENIX Security Symposium (USENIX Security 23), pp. 1595-1612, Anaheim, CA, 2023. USENIX Association. ISBN 978-1-939133-8744 URL
https: www.///wwww.u.ii.ce/////.
usenix. http://www..............aaaaaata
Andrew C Yao. Protocols for secure computations. In SFCS '82, pp. 160 164. JEEE Computer Society, 1982.
doi: 10.1109/SF S000//FFSS1992.888 URL http://dx.ddo dol.
http:////x.doi..r//110000 org/10 10. L119//SFCC 1982. 88
Samuel Yoom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine lcarning: Analyzing the connection to overfitting. In 31st IEEE Computer Securily Foundations Symposium, CSF 2018, Ouford, United Kingdom, July 9- 12, 2018, pp. 268 282. IEEE Computer Society, 2018. doi: 10. (CSF.2018.0002. URL https:///oi.ooo /rg////t..ooor///// 10. 1 1109/CSF 2018.00027
Ashkan Yousefpour, Tgor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, Graham Cormode, and llya Mironov. Opacus: User-friendly differential privacy library in PyTorch. CoRR, abs/2109.12209 2021. URL
12298
Jiaojiao Zhang, Linglingzhi Zhu, Dominik Fay, and Mikael Johansson. Locally differentially private online federated learning with correlated noise. CoRR, abs/ 221/21111.8752 2024. URL atttps://doi http::///dd..0gg0.44555000 48550/
arXiv
Yuqing Zhu, Jinshuo Dong, and Yu-Xine Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In Gustau Camps- Valps-Valls, Francisco R. Ruiz, and Isabel Valera (eds.), International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151
of Proceedings of Machine Learning Research, pp. mlr. wt..press////............ hatasssvv11//aaa 2ew.cc...22..... .mml
PMLR, 2022. URL https://proceediugs
A Appendix
A.1 Definitions Omitted from the Main Paper
In the following, we write to mean equality of distributions. With this notation, we define infinite divisibility in standard way (see, e.g., Feller 1966):
17

---

Published in Transactions on Machine Learning Research (03/2025)
Definition A.1 (Infinite divisibility). A distribution F is infinitely divisible if for every there exists lamily of distributions Fn s.t.
Sn
Xim
:=1
where the random variables S, F and Xi, Fn are independent for all .....,n.
A.2 Standard Algorithms Omitted from the Main Paper
For convenience, we give the pseudo-code for running DPFL with FedAvg when using DP-SGD for either sample- (Algorithm 2 or user-level (Algorithm 3) protection. We emphasize that we do not claim any novel contribution in these algorithms, but they included simply to clarify the discussion in the main paper.
Algorithm (DP)FL, with FedAvg: Server-side (McMahan et al. 2017)
Require: Number of clients N, number of FL rounds T, initial global model parameters ((0)
for E [T] do
Choose N₂ clients for updating (w.l.o.g. numbered I,..., N.) and send the current model ((t-1)
Receive pseudo-gradients A (1-1), ,,....A.. N₂ from the updating clients
Update the global model:
g() + g(t-1) + N, ΣN A (f-1)
5:
end for
Output: 0
Algorithm DPFT: Client-side with sample-level DP-SGD using Gaussian noise (Song al. 2013 Abadi
al.
2016
Require: Number of local optimization steps S, local dataset H;, loss function f, learning rate y, clipping constant C, noise scale a, Poisson subsampling probability q Client receives current model 0 from the server:
to k- 0
3: for S [S] do
4: Update local model with DP-SGD:
5:
91.a +
Sample minibatch by from x; using Poisson sampling with probability g
for E [[b=l] do
Calculate jth per-sample gradient in minibatch, clip and accumulate: Di. f- Vf(baajjie 0.-1) 10: Ii.s + 9i.s + min (1, (1.1a..lle)) Hi..
11: end for
12:
Add noise to clipped gradients and take a step:
13: ((s) ()x-1) 7 (gi. C(E), where & N(O, d2 and d is model dimensionality
14: end for
15: A - 0S 0p
Output:
sent to the server)
18

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm DPFL: Client-side with user-level DP using Gaussian noise (McMahan al. 2018
Require: Number of local optimization steps S local dalaset Vi, learning rale 7, clipping constant C, noise
scale o, Poisson subsampling probability 4
Client receives current model 0 from the server:
2: dn t
3: Update local model S times with standard SGD:
4: ((5) + from running SGD locally for steps with learning rate y on z;
A -0 0n
Clip sseudo-gradient and add noise:
A min [ A C5, where & ~ (0, and d is model dimensionality
Output: (Pseudo-gradieni sent the server)
Essentially, for this example when aiming for DDP, at FL round analysis enables choosing the number of local steps S in Algorithm freely while still calibrating the DP noise by looking at the total noise level Σ of added by each client separately on each local step (line 13 in Algorithm 2). Note that for the special case of using Gaussian noise, a similar result has been presented by Noble et al. (2022).
A.3 Loosening Assumptions
In the main paper, as stated in Assumption 4.1 for each FL round we have assumed constant learning rate Y, norm clipping bound C, noise level 6, and number local optimization steps S, all of them shared by all the clients. Next, we consider loosening these assumptions. As before, w.l.o.g. we consider only a single FT. round, and will therefore omit the index
Focusing first the learning rate, can immediately generalize our results allow for different learning rate Ne for each local step ,, with this notation, following the reasoning of Theorem 4.6 the aggregated update from the clients is given by
N
N
S As
Σ
A
=
10 (i,;)
(14)
1=1 mmm1
which can again be seen as post-processing the vector E 1 (x.), En A (z:)) can again
use Lemma 4.5 for accounting without encountering problems.
When considering spicnf-specific learning rates things can be more complicated. The main issue now is find proper sum-dominating mechanisms that satisfy:
sup Ha #20e!
Σ Y
(xx)
Σ i=1
A (a!) S sup Ha (z) ,8 s==...... I....,.. (15)
As concrete example, assume A()) is the continuous Gaussian mechanism with shared norm clipping constants and noise levels Ci, = C,, Ti, as Vi. Dropping the step index & for readability, let % = t for some 4 > 0, N. Writing 9i for sum over the per-unit clipped gradients of client i, and & ~ NO, C² Ia) single optimization step now contributes the following term for the global update:
Σ 1=1
78 (g. + &)
(16)
N
Si + E 1
+ E +
(17)
1=2
m
91
+
9i
(18)
1
1=2
19

---

Published in Transactions on Machine Learning Research (03/2025)
where & ~~ for the sun-dominating mechanism, it has sensitivity C* -max (C, E.- ..... Iy which in turn gives noise .....
Ei { 1111. Ia), which is sum-dominating Gaussian mechanism. When accounting
variance ( Ei=2 | for DP.
Similarly, we could relax the assumptions further to allow the clients to use different clipping and noise levels Cz, As before, a single optimization step can again be written in the form of Equation 18] when
$ s-rr(0 O9o7
(o.
N Σ
ci 12
ls
(19)
For global privacy accounting with a sum-dominattnng Gaussian mechanism, suitable sensitivity is now given by C* max(C1, f2..... ...., Cv J, and the resulting variance for accounting Ty
(G
Assuming clients have differing number of local steps, can try to fuse some local steps for the privacy analysis until all clients have the same number of steps S, after which we can then use the earlier results [
As simple example, assume we have 2 clients rumning DP-SGD: client 1 runs S local steps using norm clipping constant C' and Gaussian mechanism with noise variance o², while client runs 25 local steps with clipping C/2 and Gaussian noise variance o². The difference now is that while the clipping done on each step, from the privacy accounting perspective we can disregard some noise and think that client 2 adds noise only on every other step. Looking at the update from client 2, we would then have
28
22 -2
Σ
U2 + I[s = [1,==1,, E N] E2,x)
(20)
S
Σ (gb + *2,,);
(21)
where I2,s are the clipped per-sample gradients, 22.5 == 92,2a + 92.2., ε,., are the noise values, E, == E2, and I is the indicator function. Due to the clipping, the sensitivity of each fused step can be easily upper ll2 S C. Since Equation 21 now has the same number of local steps as client taking, we can readily use the previous results to enable privacy accounting for the aggregated update. Combining the fusing of local steps with the previous notes on differing clipping norm values, learning rates and noise variances allows us to use main results in several settings beyond what is stated in Assumption 4.1
bounded via inequali:: 1192, ll2 = 2 22' 2l S 1192
As a final note, when the clients use data subsampling for the local optimization, differing local subsampling probabilities can lead to having varying DP guarantees between the clients on the global level due to the different subsampling amplification effects, but can otherwise be incorporated with the same analysis we have already presented.
A.4 From Ideal Trusted Aggregators to Practical SecAgg Protocols
For implementing the trusted aggregator assumed in Theorem 4.6 in practice it should be noted that as the sum over 8 is done locally by each client during local optimization, it is always trusted as long as the individual clients are, while the sum over would need to be implemented, c.g., using a suitable SecAgg protocol. Several such algorithms are known, including the ones proposed by Bell et al. (220)
Bonawitz
et al. 2017;; Sabater et al. (2022) So et al. (2021)
Using SecAgg protocol will typically also place some extra requirements on the DP mechanisms A since the SecAgg algorithms usually run on elements of finite rings. This precludes continuous noise mechanisms, A viable alternative to use some suitable discrete noise mechanism, such Skellam (Agarwal et al. 2021
8 AAlternativeyy, we could also consider breaking some local steps several parts. We leave the detailed consideration of this approach for future work.
20

---

Published in Transactions on Machine Learning Research (03/2025)
Poisson-binomial (Chen et al. 2022b However, differing from the cases considered in the cited papers, since in our case the clients send model updates instead of single gradients, the finite ring size used in the SecAgg protocol needs to accommodate the model update size: it does no good to use Skellam mechanism with gradient quantization to a small number of bits, if the model weights and the resulting model update A for client, i stiill uses 32 bit floats.
A.5 Privacy Accounting Details
For privacy accounting we utilize Rényi DP (RDP):
Definition A.2. (Mironov 2017] Let a > 1 and E > 0. A randomised algorithm A: X -0000 (a, RDDD if for every I, x' E X" 2
Da(d())lA(('))) s.
where Dr is the Rényi divergence of order o:
1 log E
p(t) a (t))
(Pll)) a
We do privacy accounting for all the experiments based on RDP. Generally, we account. for the privacy of each individual local optimization step using the noise contributions from all the clients selected for a given FL round. When the clients use Poisson subsampling the same probability for including any individual sample in the minibatch), amplification results. In practice, we use the RDP accountant implemented in Opacus (Yousefpour et al. 2021j, as well as bounds for Skellam mechanism by Agarwal et al. (2021) and tight RDP amplification by Poisson subsampling (Steinke] 2022). We calculate the privacy cost of the entire training run in RDP, and then convert into ADP using (Mironov 2017 Proposition 3). Note that, as is common in DP research, we do not include the privacy cost hyperparameter tuning in the reported privacy budgets (scc, c.g., Tramèr & Boneh 2021 for some reasoning on this practice).
sample minibatches (we assunee each client uses
standard RDP privacy
A.6 Experimental Details
All the experimental settings we use satisfy Assumption We use DP-SGD with Skellam mechanism optimise the local model parameters, and standard federated averaging as the aggregation rule for updating the global model in all experiments. For cach centralised data set (combining original train and test sets), we split the data randomly into equal shares, which results in having almost the same data distribution on each client. For hyperparameter optimization with each dataset, we first split each clients' data internally into train and test parts with fractions (.-.2). For tuning all hyperparamotors, we use only the training fraction, and divide it further (.7-33 into hyperparameter train-validation. We use Bayesian optimization- approach implemented in Weights and Biases (Biewald 2020 for hyperparameter tuning, and simulate FT. using Flower (Beutel et al. 2020
In general, when tuning hyperparameters we do 50 hyperparameter tuning runs. For each tuning run, we train the model on hyperparameter training fraction, test on the validation fraction, and try to optimise for the final model weighted validation loss. After finishing the hyperparameter tuning, we re-train the model from scratch 5 times with different random seeds with the best found hyperparameters using the entire original training data and testing on the test fraction. We report the mean and the standard error of the mean (SEM) in all the figures. In Figure 2 we plot the minimum test boss/maximum test accuracy taken over the entire training run.
For the experiments with Fashion-MNIST (Xiao et al. 2017 and CIFAR-10 Krizhevsky 2009 data sets, we run hyperparameter tuning separately for each combination of number of local steps {1 step, 1 epoch), and expected minibatch sizes on the grid [64, 128, 256, 512) using Poisson subsampling.
For Fashion-MNIST the best expected batch sizes found are 512 for local epoch, and 128 for 1 local step.
With CIFAR-10, due to heavy computational cost of hyperparameter tuning, we use single expected batch size for each configuration of local steps (1 step, epoch) and FL rounds {10, 20, 40, 160). Concretely, we
21

---

Published in Transactions on Machine Learning Research (03/2025)
pick the best expected batch size value from the above grid when using Bayesian optimization to tune all hyperparameters with 20 FT, rounds. This results in choosing expected batch size 128 for local step and 256 for local epoch. We then use these values and optimize all other hyperparameters separately for all other FL round settings.
With ACS Income data DDing et al. 2021 we tune all hyperparameters for each combination of local steps {1 step, 1 epoch) with Poisson subsampling using local sampling probability on the grid {0.4, 0.2, 0.1, 0.05) for 10 FL rounds. We report results the best found local sampling probabilities (0.05 for both).
For ResNeXt-29 8x64, used pre-trained weights available from https://github. http::///gghhuu..ccmbbbaaaaaa sytorch-classificc
Our implementation of the Skellam mechanism is based on the implemen-
lation from 2023
comppessioooooossiooooooooo.oooo Chaudhuri et al. 2022 Guo el. al.
For American Community Survey (ACS) Income data set Ding al. (2021) we use the data for all the states and Puerto Rico for 2018. The goal is to predict whether individual has income greater than $50000. Instead of simulating data splits, we use the inherent splits, ie., we take each original region (state or Puerto Rico) to be client.
For training all models, we use a small cluster with NVIDIA Titan Xp, and NVIDIA Titan V GPUs. The total compute time of the training runs (including debugging) over all GPUs amounts roughly to 30-60 GPU days.
A.7 Additional Results
Table shows the results from averaging several independently trained LDP models as described in Section 5
Table 1: Improved privacy for averaged models, Skellam mechanism, 32 bits (no quantization), Poisson sampling with sampling fraction 0.1, each local model is unbounded (e = 5., 6 = le - 5)-LDP. Averaging more models improves on the DP guarantees against adversaries who do not have access to the original models.
Local steps
Parties
Ototal
avg model
step
1
0.69
5.0
step
2
0.98
2.78
step
5
1.54
1.22
step
10
2.18
0.64
epoch
1
0.90
5.0
epoch
2
1.28
2.61
epoch
5
2.02
1.19
epoch
10
2.85
0.72
epochs
1
1.18
5.0
epochs
2
1.67
2.85
epochs
5
2.64
1.55
epochs
10
3.73
1.03
22


Reviews:
[{"review_id": "0uwDMf0xdc", "reviewer": "Reviewer_B4Wt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem of sample-level differential privacy with multiple local steps is interesting to the community. However, I find the key approach is unclear.\n\n1. The key approach \"Joint Noise Scaling\" is not clearly defined. The authors define a family of sum-dominating mechanisms in Definition 4.2 that permit joint noise scaling but I am unable to locate the precise definition of the joint noise scaling concept. Can the authors use an Algorithm block to outline the joint noise scaling steps? Do we need multiple clients to agree on a set of diverse noise scales? How does it differ from the baseline Gaussian mechanism?\n\n2. Albeit claimed, the approach with pseudo-gradient clipping may not be compatible with the secure aggregation protocol. The secure aggregation protocol [1] lets pairs of clients to agree on a common secrete. Then, one client adds the secret to its pseudo-gradient while the other subtract the secrete from its pseudo-gradient. As such, the average remains the same with and without the secrete. The clipping operation in Equations 4 and 5 may deviate the average from its ground-truth. Perhaps I missed some key contributions from the proposed approach but I would need the authors to clearly describe their algorithm steps.\n\nThis work may have a decent amount of value but currently the presentation issues block me from further assess its contributions. \n\nDisclaimer: I am not an expert in differential privacy theory and I did not extensively evaluate the soundness of the assumptions and proofs.\n\n**Reference**\n\n[1] Practical Secure Aggregation for Privacy-Preserving Machine Learning, CCS 2017.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of sample-level differential privacy with multiple local steps. The authors aim to show that a joint noise scaling approach can improve the model utility under privacy constraint and provide empirical evidence with a single-step setting and a single-epoch (~20 steps) setting.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The sample-level differential privacy setting needs to appear early in the introduction setting. This is the analysis setup of this paper but its current location is on page 2, after a long literature review.\n2. This paper could use Algorithms blocks for the joint noise scaling approach and (optional, in appendix) the secure aggregation protocol.\n3. Some proofs can go to the Appendix and leave space in the main paper for introducing, discussing, and comparing the theoretical results.\n5. Comparing the theoretical result with prior ones can further highlight the contribution. For example, are there improvements over the Gaussian mechanism in Example 4.4?\n6. I usually do not want to overwhelm the authors for additional experiments. If time permits, its would be interesting to see whether the performance improvements are smooth if we interpolate the local step from 1 to 20.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UAGo6kzZSt", "reviewer": "Reviewer_DqzM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The paper proposes the concept of the *sum-dominating mechanism* and uses it to characterize the privacy amplification.\n\nWeakness:\n1. Inaccurate claim: the authors claim that \" there is no existing work on the privacy analysis when the clients do multiple local optimization steps with fine-grained DP and communicate the results via SecAgg\". This is incorrect. In the work \"Differentially Private Federated Learning on Heterogeneous Data\" [Link](https://arxiv.org/pdf/2111.09278), they provide a clear privacy guarantee for the case with and without trusted server (see Thm 4.1). Other related works considering SecAgg setting with local updates are also not discussed, e.g., \"Differentially Private Online Federated Learning with Correlated Noise\", \"LDP-Fed: Federated Learning with Local Differential Privacy\".\n\n2. Unclear results: the paper fails to provide an explicit bound on the privacy amplification, i.e., the $\\epsilon, \\delta$ of $TA(\\cdot)$ and its dependency on $N$, $\\epsilon_i, \\delta_i$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper discusses the privacy amplification in Federated learning via secure aggregation. The paper provides a theoretical discussion of the privacy protection for Local DP-SGD when the clients perform per-step gradient privatization and use secure aggregation.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the weaknesses.\n\nAlso, please clarify the novelty of the paper.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7DK6f4Qlw7", "reviewer": "Reviewer_yKBn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The underlying setting is interesting and I appreciate the exposition at the start of Sections 1 and the start of Section 3. But the submission is missing content that would make the problem-of-interest and contributions clearer. Specifically, the introduction does not define what notion of \"utility\" that is being considered. As a result, the reader does not have the baseline quantities (or asymptotic rates) for comparison. Additionally, Section 3 favors a loose description of learning algorithms instead of precise pseudocode and notation. This means it is not obvious why or when the sensitivity C in equation (4) is smaller than the sensitivity of the naive S-step variant of (5), which is implied in the text. Some more notation is given in Section 4 but it should have been in Section 3 and it is still missing precise language that describes the privacy units and how the proposed algorithm processes them.\n\nSection 4 presents theorem & lemma statements but does not give the most important piece: guidance on how a practitioner should calibrate hyperparameters. More precisely, the Introduction claims that \"the proposed approach can lead to large utility benefits without requiring any changes to the underlying algorithms\" but how many local steps S are possible under the new analysis? The lack of pseudocode also makes it unclear what is meant by \"scaling the noise level jointly over the clients.\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission explores optimizations of the analysis of differentially private cross-silo federated learning, assuming access to a secure aggregation primitive. One baseline approach to learning in this setting is to enforce clipping and noising on a per-client level. However, this ignores the fact that each client holds data from many individuals. Another approach would be to clip and noise every individual's contribution to every local optimization step, but this (seemingly) scales poorly with the number of steps. The authors present a number of technical lemmas to argue that it is possible to have more local steps than previously considered. They assess the quality of their analysis via experiments on Fashion MNIST, CIFAR10, and ACS Income Data.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical:\n- In the introduction, identify the quantities that the analysis improves upon and how much they are improved (informal language is fine here)\n\n- In the main body (Sections 3-4), add pseudocode and notation to clarify where/how the new work is so successful\n\n- In Section 4, give a \"big-picture\" theorem that quantifies the improvement (formal ver. of Introduction statements)\n\n- The phrase \"joint DP\" already has a meaning that appears to be distinct from the way you use it [see e.g. https://bpb-us-w2.wpmucdn.com/sites.gatech.edu/dist/c/679/files/2017/10/lecture13.pdf]. If it is a distinct notion, please use a distnct term. Otherwise please cite the prior work. In either case, please define what it is in Section 3.\n\nNon-critical\n- although it is fine to focus on noisy SGD, please discuss (or simply scope-out) alternatives that the clients can employ: what about momentum? what about DP follow-the-regularized-leader?\n\n- The final bullet point in *Our Contribution* says \"our results point to a clear mismatch between the current theoretical understanding of DPFL and practical results.\" Was your algorithm implemented before (hence \"practical results\") and you just provided a new analysis? If so, please explicitly cite that.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper received conflicting recommendations:
- Reviewer yKBn leaned accept after the clarification and revised version of the manuscript
- Reviewer DqzM leaned reject in part due to limited novelty, which should not be a criterion as per TMLR's guidelines.
- Reviewer B4Wt leaned reject as he/she found the contributions unclear, while also acknowledging not being an expert in differential privacy.

After carefully going through the paper, reviews and discussion, I align with the view of Reviewer yKBn while agreeing in general with the sentiment that the clarity of the paper can still be improved.
Decision: Accept (poster)