Differentially Private Federated Learning with Time-Adaptive Privacy Spending
Authors: Shahrzad Kiani
Nupur Kulkarni
Adam Dziedzic
Stark Draper
Franziska Boenisch
Venue: ICLR 2025 Poster (2025)
Keywords: Differential Privacy
Federated Learning
Time Adaptive Privacy Spending
Individualized Privacy Constraints
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We propose a time-adaptive differentially private federated learning algorithm that enables clients to spend their privacy budgets non-uniformly over time.

Abstract: Federated learning (FL) with differential privacy (DP) provides a framework for collaborative machine learning, enabling clients to train a shared model while adhering to strict privacy constraints. The framework allows each client to have an individual privacy guarantee, e.g., by adding different amounts of noise to each client's model updates. One underlying assumption is that all clients spend their privacy budgets uniformly over time (learning rounds). However, it has been shown in the literature that learning in early rounds typically focuses on more coarse-grained features that can be learned at lower signal-to-noise ratios while later rounds learn fine-grained features that benefit from higher signal-to-noise ratios. Building on this intuition, we propose a time-adaptive DP-FL framework that expends the privacy budget non-uniformly across both time and clients. Our framework enables each client to save privacy budget in early rounds so as to be able to spend more in later rounds when additional accuracy is beneficial in learning more fine-grained features. We theoretically prove utility improvements in the case that clients with stricter privacy budgets spend budgets unevenly across rounds, compared to clients with more relaxed budgets, who have sufficient budgets to distribute their spend more evenly. Our practical experiments on standard benchmark datasets support our theoretical results and show that, in practice, our algorithms improve the privacy-utility trade-offs compared to baseline schemes.

Published as a conference paper at ICLR 2025
DIFFERENTIALLY PRIVATE FEDERATED LEARNING WITH ADAPTIVE PRIVACY SPENDING
Shahrzad ; Nupur Kulkarni², Adam Dziedzic², Stark Draper', & Franziska Boenisch²
Department of Electrical and Computer Engineering, University of Toronto
2 CISPA Helmholtz Center for Information Security
ABSTRACT
Federated learning (FL. with differential privacy (DP) provides framework for collaborative machine learning, enabling clients to train a shared model while ad- hering strict privacy constraints. The framework allows each client to have an individual privacy guarantee, e.g., by adding different amounts of noise to each client's model updates. One underlying assumption is that all clients spend their privacy budgets uniformly over time (learning rounds). However, it has been shown in the literature that learning in early rounds typically focuses more coarse-grained features that can be learned at lower signal-to-noise ratios while later rounds learn fine-grained features that benefit from higher signal-to-noise ra- tios. Building on this intuition, we propose a time-adaptive DP-FL framework that expends the privacy budget non-uniformly across both time and clients. Our framework enables each client to save privacy budget in early rounds so as to be able spend more in later rounds when additional accuracy is beneficial in learn- ing more fine-grained features. We theoretically prove utility improvements in the case that clients with stricter privacy budgets spend budgets unevenly across rounds, compared to clients with more relaxed budgets, who have sufficient bud- gets to distribute their spend more evenly. Our practical experiments on standard benchmark datasets support our theoretical results and show that, in practice, our algorithms improve the privacy-utility trade-offs compared to baseline schemes.
INTRODUCTION
With machine learning (ML) relying increasingly users' sensitive data, the development of utility- driven frameworks that also adhere to users' individual constraints, including privacy preferences, has become a priority. When federated learning (FL) (McMahan et al. 2017) was first introduced, it was perceived as a privacy-preserving distributed learning framework that allows users (also called clients) to keep their data local and solely exchanging model updates with the server who can ag- gregate the updates and apply them to the global model for training.
However, has been shown that data can be leaked through the model gradients (Zhu et al. 2019 Geiping et al.) 2020; Boenissh et al. (023). Hence, FL was extended to incorporate formal pri- vacy guarantees (McMahan al. 2017 Geyer et al. 2017; Wei et al., 2020 Hu et al., 2023 Ra- maswamy et al. 2020) via the mathematical framework of differential privacy (DP) (Dwork] (2066).
In DP-FL frameworks, one common approach is to protect the entire dataset of each client ('client- level DP") by clipping local model updates and adding noise before releasing them in each training round (Truex al., (209 2020). This ensures that an adversary who has access to the aggregated perturbed updates of subset of clients cannot confidently infer whether or not any particular client has participated in the given training round. However, although the DP-FL framework ensures pri- vacy, it degrades model utility by introducing errors into the model updates. Thus, careful calibration of the perturbations necessary to balance privacy and utility.
There are several extensions of the DP-FL framework in the literature that aim to improve privacy- utility tradeoffs by reducing the effect of perturbation while adhering to the privacy budgets of
correspondence to shahrrad.kianidekkkno @ malil.ttoroooooocc Part of the work was done while Shahrzad Kiani visited CISPA.

---

Published as a conference paper at ICLR 2025
clients. Typically, these prior works (Pichapati et al. 2019 Yang al. 2021: Shen et al. 2023 Yang et al. 2023] McMahan et al.) 2017) consider the ineeeent heterogeneity in FL both in data and privacy- to make perturbation more efficient. Yet, they either assume that clients' privacy bud- gets should be exhausted uniformly over time (Boenisch et al., 2024). or rely on strong assumptions regarding access to public data (Li et al.] (022) or negligible privacy loss when adjusting privacy parameters in a time-adaptive manner based on data (Pichapati et al. 2019). As we will see, judi- ciously expending the budget non-uniformly over time and in a privacy-preserved manner can yield an improved privacy-utility tradeoff. Hence, a gap exists in the literature.
In this work, we reduce this gap by proposing a novel DP-FL framework with a data data-indepee inta-inndeeeneent fime-adaptive privacy spending method. In our framework, clients can spend their privacy budget non-uniformly across time (training rounds). This means that clients intentionally allocate less of their privacy budgets in the early rounds to save them for later rounds. We term these rounds as "saving". Clients then transit to "spending" rounds, wherein they uniformly allocate their remaining budget across spending rounds. The decisions about when each client transits from saving to spend- ing and how much they save in each round are made solely based on clients' privacy budgets, and not their local data. Therefore, of privacy loss. We account for each client's 's privacy spending in each round, formulating privacy bounds as a function of clients' decisions and budgets.
schedule spending before the start of training, making it free
Two observations that motivate the potential of our framework to improve the privacy-utility tradeoff follows. First, by preserving the privacy budget in early rounds and incrementally spending later, we are able to adjust the signal-to-noise (SNR) ratio to be uneven across training rounds, with noise shifting from later rounds to earlier ones. This enables coarse-grained features, which are typically learned in the early rounds and are more tolerant to noise, still to be learned effec- tively. Furthermore, the fine- grained features, typically learned in later rounds (Dziedzic et al., 2019 Raghu et al.) [017] Shwartz-ZZi & Tishby| (217)) can be learned in a beneficial higher-SNE setting. Secondly, in practical scenarios, we note that clients are likely to have different privacy budgets. We show theoretically that clients with stricter privacy budgets benefit from expending their privacy budgets more unevenly than those with relaxed (larger) budgets. Intuitively, this allows ces-prrivccy-sensiivv clients, who have often sufficient budgets, to contribute to the learning both of coarse- grainned features in early rounds and of fine- mne-griieed features in later rounds. On the other hand, perre-prvvcy-come constrained clients can preserve their budgets and helpfully contribute more to the learning of fine- -he-gra features.
In summary, we make the following contributions:
As part of our framework design (detailed in Sec. 3) ing method, namely "spend-as-you-go"" where clients spend their privacy budgets incre- mentally over time, instead of spending the privacy budget uniformly across time, as in traditional DP-FL approaches.
we introduce a novel privacy spend-
Our theoretical analysis (detailed in Sec. 4 provides privacy accounting for the incremental spending pattern in our method. Additionally, we show theoretically, that if clients that use stricter privacy parameters, such as lower clipping norms, save larger portion of their privacy budget during saving rounds, and can spend more in spending rounds, then, in expectation, we can reduce the clipping bias (Das et al. 2023).
Based these theoretical insights, in Sec.5]we experimentally benchmark framework against the baselines and show that the global test accuracy achieved by our method sur- passes that of the baselines for the FMNIST (Xiao al. (2017). MNIST (Deng) 2012). Adult Income (Becker & Kohavi 1996). and CIFAR 10 datasets (Krizhevsky et al.
2009)
2 BACKGROUND AND RELATED WORK
Federated Learning. We consider a typical FL. system with N clients and a central server. Each client E [N] has its own data distribution P., on X' Y, where X' C RR denotes the feature space and ) C I denotes the label space. Let C., R" x X' x y + R denote client n's loss function which maps a model parameter 0 R" and a data sample (x, y) E X y cost. Each client n is assumed to have access to dataset D, which consists of |D,l data points sampled
from P,.. Defining (0) ;= [..| E(xyleD. Cn (0; (x, v)) and E(0) == 1/ Em (B), the
2

---

Published as a conference paper at ICLR 2025
optimization problem in FL is ming [().. The Federated Averaging (FedAvg) (McMahan et al. 2017) algorithm solves this problem by having clients run local stochastic gradient descent (SGD) and send updates to the server, which averages them to update the global model. This cycle repeats until convergence or for a specified number of communication rounds. As the baseline for our proposed approach (detailed in Se consider FedAvg, presented Alg. in App/A.1 This algorithm, unconstrained by privacy limitations, represents the ideal utility case.
Differential Privacy. In ML, the mathematical framework of (c, 5)-DP (Dwork et al. 2014). en- sures that two models trained on neighboring datasets, i.c., datasets that differ in one data point, differ only slightly in their outputs. This can be formalized as Def. in App. A.662 In (c, DD-P, a smaller privacy budget c E R. enforces stronger privacy guarantee. The å E [0, 1] quantifies the probability of violating the privacy guarantee and thereby has usually a small value. We discuss (a, e) ))-Rényi-DP (Mironov 2017) as an alternative to relax DP guarantees and get smoother compo- sition in App. [A..2 In this paper, we adopt RDP, while as it is shown by (Mironov 2017). it can be converted to DP when needed (cf. Lem. 3 in App. A..62).
DP-FL. We use the notion of client-level DP-FL which protects the entire client's dataset (McMa- han et al. 2017 Geyer et al., [2017 Hu et al. 2023). To implement client-level DP in FL, we rely on the De-Fed (McMahan et al. [017]] Hu et al. 2023) algorithm that first clips clients' updates according sensitivity e and then adds Gaussian noise according to N (0, (0, c²o2T). DD-FFedAgg also implements privacy amplification by sub-sampling (Beimel et al.) 2014). where clients are sam- pled independently at random with probability q. As shown by Mironov et al. (2019), the Sampled Gaussian Mechanism (SGM) tightens the RDP by a quadratic scaling factor q² (cf. Lem. 4 in
App. A.6.2. We also use the notion of distributed DP (DDP) (Trexx et al. 2019) which com- bines the advantages of centralized (Ramaswamy et al., 2020) and local DP (Truex et al., 2020). In DDP, clients clip their updates and locally add small amount of noise, distributed according to N (0,co2//NT) (Truex et al. 2019). By adding local noise, clients" privacy is partially protected against the server, and sufficient noise, .N (0,c2 2Q)T)), is guaranteed when the server aggregates all N noisy updates. We consider the De-FedAvg algorithm that is implemented with client-level and
DDP (presented as Alg. in App A.I as baseline for our approach, detailed in Sec 3
Personalized DP. DP-FedAvg and most of its variants apply worst-case privacy guarantees to ensure privacy for the most constrained clients. This leads to over-perturbation and reduced utility for clients with more relaxed privacy constraints. Some recent literature addresses this by exploring personalized, or individualized, DP (Yang et al. 2021 Shen et al. 2023 Malekmohammadi et al. |Boenisch al. (2024) introduce individualized DP (IDP)
2024 Boenisch et al.. 2024). For example,.Bocmisch and apply it to the DP-SGD algorithm, collaboration-free variant of DP-FedAvg. The integration of IDP into a client-level DP-FI. framework is natural. IDP enables individualized privacy budgets across clients and fine-tunes client-specifie privacy parameters, through the use of different clip norms and/or sampling rates. We name this integrated algorithm IDP-FedAvg and formally present it Alg. 5 in A.I We note that IDP-FedAvg and our proposed approach, detailed in See complement each other. In this paper, we consider DDP-FedAvg as another baseline for our approach.
Adaptive DP. Another approach to improve the utility performance of DP learning is parameter grouping (Yang al. 2023 McMahan et al., (017)) which clusters the ML parameters with similar clipping norms and applies a non-uniform clipping across clusters. Similar to the IDP approach, our approach and parameter grouping are complementary. However, integrating our approach into parameter grouping optimally, given the increased parameter choices across clusters, requires a study on cluster-based parameter selection which is beyond the scope of this paper. Another approach used for utility improvement is adaptive clipping (Pichapati et al., 2019;; Andrew et al., [202T] Li et al.) 2022) which aims to optimize the clipping norms during training and thereby reduce the noise effect. Some of these papers either rely on strong assumption of accessing public data (Li et al.) 2022). or the strong assumption of minimal privacy loss occurs during parameter optimization (Pichapati et al. 2019). Our proposed approach is an alternative that selects privacy parameters non-uniformly over time. Compared to the above adaptive clipping methods, our approach eliminates the need for public data, and as parameter selection is done prior to training, ensures zero privacy loss. Another adaptive clipping method that is not limited to prior assumptions and is more relevant to ours is the one proposed by Andrew et al. 2021), and presented as Alg. 6 and detailed in App While
3

---

Published as a conference paper at ICLR 2025
targeting the same goal of improving the privacy-utility tradeoff ours, the method (Andrew al. 2021] maintains fixed privacy spending over time. Note that adaptive clipping is orthogonal to approach and could be combined with ours for potential performance gain. However, such integration requires careful privacy analysis, which is beyond the scope of this paper and left for future work. In App. [A.8, we benchmark our approach against the method (Andrew et al. 2021). showing that our approach achieves a better privacy-utility tradeoff.
PROPOSED FRAMEWORK
We introduce novel time-adaptive DP-FL framework to solve the FL optimization problem with high utility and under privacy constraints that are not meant be spent uniformly over time. We first discuss our threat space and privacy-related hyperparameters (summarized in Table
Threat Space. We assume that each client aims to prevent data leakage any other client who may be honest but curious (HbC). Specifically, HbC clients follow the FL protocol honesty but may attempt to infer sensitive information of the victim client from the shared model updates. We assume the server is trusted but rather than offering zero protection, we make clients perturb their model updates before sharing with the server to preserve privacy, though at a lower level. This is because, after the server aggregates the perturbed model updates, the total perturbation increases, providing stronger privacy protection against other clients than the server. For enhanced protection against the server, server only learns an aggregated function (typically the sum) of the clients' local updates, without learning individual updates. However, the design or implementation of secure aggregation schemes is beyond the scope of this paper, and we mainly focus on preserving privacy against HBC clients.
can use secure aggregation (Bonawitz et al., 2016) which ensures that the
Privacy Hyperparameters. In spend-as-you-ge method, which we will detail as part of our framework design in Sec.3.1] each client saves a specific fraction their budget in certain rounds, then incrementally spends the saved portion over time. We realize savings by using client-specific sampling rates, denoted as 9n E [0, 1] for client n, during "saving" rounds and by using a uni- form, higher, sampling rate, denoted q E [0, 1], during "spending" rounds. If qn 9. client is less likely to be sampled during the saving rounds. According to privacy amplification by sub- sampling (Beimel al.) 2014), and detailed in Sec. [4. fraction of the clients' privacy budget will thereby be saved for later rounds. Another hyperparameter for transitioning from the saving to the non-saving (spend) mode. For each n E [LV. we use T, to denote the first round in which client n is in the spending mode. Intuitively, if Tú is aligned with the client n transitioning from the coarse marse-grained training of early rounds the fine- mne-graieed feature training of later rounds, the client's saved budget during early rounds enables the client to spend more in later rounds when additional accuracy is beneficial in learning more fine-grained features. By setting 4- over time, resembling the traditional non-time non-time-adape -im--idaptiiee spending approaches. We show the hyper- parameters 4n and T.. which are specific to our framework, in the first two rows of Table [ Other hyperparameters, which are common in much of the DP-FL literature, are summarized in rows 3 to 10 of T The privacy-related parameters, consistent across clients and fixed over time, include the global clip norm c, the sampling rate g. the DP parameter 8, and the ReP-related order a. The configuration of these hyperparameters to avoid additional privacy loss is covered partly in simula- tions (Sec. 5land App. A.) and partly in theory (Sec.) 4p. Later, in Sec, 6 we discuss potential future directions for broader hyperparameter tuning.
each client's 's designated round
Tn = 1 for every E [N]. each client's privacy spending becomes uniform
3.1 THE SPEND-AS- AS-OU-GO METHOD
We consider an FL. setting where every client n E [N] is given privacy budget cn derived from their individual privacy preferences. We assume all clients exhaust their privacy budget after T global rounds. We propose the spend-as-you-go method, which is executed before training begins, and obtains the following privacy parameters used during execution: the local noise multipliers of the sampling rates of the privacy budget remaining e, (with an initial value of e, en), and the local clip norms o, Each qf is chosen as either q or qn- depending on whether client n is in spending or saving mode. From now on, denote of the sampling rate, and to distinguish
4

---

Published as a conference paper at ICLR 2025
between q and qn. we respectively refer to them as the spending-based sampling rate and the saving- based sampling rate. To denote whether clients are in saving or spending mode at each round, we use M a binary variable that is set to O if round t is saving round for client n, and otherwise. Iee. M = O if < Tn and M, = 1 if 1 2 Tn. Algorithm | presents the pseudocode for the spend-as-you-go method. Regardless of the saving or sampling mode, in each round, we first find the value of required to obtain the remaining privacy budget e, using the Get se fuuccion (Line 4 of Alg. D. This function takes inputs e,, ò, q, and the number of remaining rounds - During the spending rounds of client (i.e.. when M,,
1), the client is sampled according to % 9. During the saving rounds (when M, = 0), the client sets 9n 9n- As shown in lines 6-8, we calculate the privacy spent and e, at the end of each round / E [T) and for every client n E [V]. Using Compute pdp function, we calculate the privacy spent given L o and a. We then use get-gri vacy-spent to convert the RDP privacy spent into the DP privacy spent, given the RDP privacy spent, a, and We finally follow the same procedure as in Boenisch et al. (2024) to compute local clip norms e, such that their average across n E [NV] equals the hyperparameter
To achieve this, we calculate c = co' (Line 12), where of = N (EnE[N) 1/o4)
(Line 10).
Table 1: Hyperparameters Summary
Algorithm 2 Iterative Training in Our Time- adaptive DP-FL Framework
To
Saving-to -oeendding transition round Saving-based sompling rate of Client i
9=
T
Number of rounds
Inputs: No. clients N. global rounds No. local iterations local privacy budgets ca, sampling rate average clip norm e. modes {0, 1}, sampling rites for saving q.. loss functions Lo..
L
Number of local iterations
Batch size
datasets D,,, learning rate X, batch size B, Prob, of violating 5
Leurning
a
Rčnyi order in RDP
1: (9 of, Agh, of of bucte
Probability of Violating in DP
Average clipping nomn
Set PeaPPraaaaPaam 6. Enuss M MannE)) T,8 (E(T)
Global (spending-based) sampling rite
2:
Initialize global model 8a)
3:
each global round é [2']
Algorithm The spend-as-yous Method in
4:
C + Sample clients with probability {oh))
Our adae-vdaetive DP-FL Framework
5:
for each client n [N] in parallel do
6:
Ao,, = =fl.:::uuuuudeeeefec
6t-1 . of)).
Inputs: No. elients N. No. global rounds T. local privacy badgets cu. sampling rate q, average clip norm e, modes Mr, E {0, 1}. sampling rales suving mode g... Prob. violating
7:
end for
8: Ao = Encer 30% + +nnCINhie Nf (u, 2igl1
Def Set Set.rivayySaram
9. fun Sn. M. hne[ T,8
9: Update gt Aat '"
(E[3)
10: end for
1: Initialize e, = <. and s.p... O for n [N]
2: for each global round t E [T] do
Def PeCcleen ClientCppatee n, gr-=,, cch.
3: for each client n [N]
4: of GGetNo (rh (ch 1. 5, q.
t)
1: Initialize model 0 0²-1
5: If M" then q:, gn. Else. oi =
2: local iteration E [4] do
6:
cap. =Compute__rd (oh of.a)
3: (15.) 1E.1/B +- Split D., to size B batches
7:
i.p.. 1-1 + sab..
4:
For each hatch 1, do
> Wes, vca (o6i--1 (x.)))
8: < =,,,, ga--gtte get.pptttaccyypprrre (a, 1))
5: 8t.
6: end for
9:
end for
Compute a² + $ EnEINi sta )
7: end for
10:
8: Compute A0", 03.1. 6F.0
of Clip So A0", min (1, |aarall
11: for each client n [N] do
9:
12:
local clip norm c², so!
10: Add noise 50; + 3o,, + N (o, (ot (25)110511
13:
end for
14:
N E. %i Return (a". o0, tah oh wh InsIN
11: Return 50*
15:
end For
3.2
THE ITERATIVE TRAINING MODULE
After setting parameters through the spend-as-you--o method, our DP-FI. framework operates the iterative training module, with the pscudocode presented in Algorithm 2 We note that although the primary contribution of our DP-FL framework lies in the aoaud-as-ou--gee method, the iterative
'To introduce our yoond- method, we use some functions implemented by Opacus li-
brary Youseeppour al. 2027.
5

---

Published as a conference paper at ICLR 2025
training module also differs from the baseline due to the of time-adaptive privacy parameters and has to be carefully designed. This module spans T communication rounds. Within each round, clients conduct L iterations of local training. For iteration / E [L] within round t E [T]. let 6% denote the local model of client n. In round E (7), C³ denotes the set of workers contributing to local training. This set is randomly chosen using Poisson sampling (Line 4). Each client [N] in round & E [Z'] has an independent probability 9f E [0. 1] of being selected for C?. In expectation Ene(N] an are sampled round t.
N clients, where q²
0 (Line of ClientUpdate) It then performs L iterations of local training, using a gradient- based technique, such as mini-batch SGD. In each iteration I E [4]. the client first splits D, into size batches (Line of clientUpdate).
Client update: In round i, each client n E [N] initializes nt
For each batch B, the Σ (x.))EB, VLn (0%'1; (x,v)) v)) where À is the learn- wth client updates 8%, = 0 B
ing rate and B (x,,), VL,, (0r--11 (x,y)) estimates the gradient VE, (Line of ClientUpdate), Once local training finishes, the client computes the resulting model update A0,, 0 0%.0 (Line of ClientUpdated
The first phase of integrating the DP mecha- nism in the iterative training module is to assign the client the task of clipping Adt as shown in of
(Line of ClientUpdate), and detailed as Â0% A0,, min (1, T where ch the clip norm. The client then perturbs further its clipped model update by injecting random noise (Line 10 of ClientUpdate), The noise is selected independently for each client n E round Algebraically, given noise z ~ (N,, ()) 50% Âot z/0-
Server aggregation: As shown in lines 6 and 8, the server aggregates Âø for all n E C² and com- putes the sum ÁØ" = Ennco Áør,- For those clients not being selected, i.e., n E [N]]c the server compensates by injecting additional noise Âσ" + -0 +EneNNii=> (Ot)2(()))/N)) Assuming co c,, for all n E [N], because of this compensation, the total noise power W (0, (a that is injected to the global model update not function of the sampling. The round ends with åe" the server computing gr + g-N (Line 9).
THEORETICAL ANALYSIS
For the DP-FL framework (described in Sec.3), now develop the theory that underlies our privacy accounting (Sec. 4.1) and optimize the sampling rates to improve utility (Sec. (42)..
4.1 PRIVACY ACCOUNTING
In this section, caleulate the RDP bounds for each client n E [N] at round t E [T]. The results will support the general idea of save-to-spend in our framework. Since we use RDP to perform privacy accounting, we convert each client's privacy budgets fc,) {cn]ne(N] into the RDP equivalent, denoted (fndp.n) ne[N]- ( fixed order a. For client n, use Edp. and < Iep denote, respec- tively, the RDP privacy spent in round and the "go-forward" RDP privacy budget remaining for round onwards.
The privacy accounting for the spond-as-you-go method first involves calculating each <ap.. (ef. line 6 of Alg. [] Next, the total RDP privacy spent during the first / rounds is calculated as Σi=1 Tdp.. (Line of Alg. I. with budget remaining ddp-een, Cdlp.n -E== Spp... Recalling from Sec. 3.1 client n selects the noise multiplier of, assuming that et Edp-left.n will be spent uniformly across the remaining T + rounds subject using sampling rate q. As shown by Myroroo al.) 2019), under this uniform assumption of should satisfy
2ag". of
Tu. the sam- When
T-t+1
Supuen (0m))
pling rate 4n reduces the RDP expenditure to <'pp. (7--+ [ When /. Tg. the full allocated
budget is used in round t. The RDP privacy spend chpp. can be computed recursively as Crdp.n Σt=1 Epp.
)
gh 1 1121
Gdp.
T- 1

---

Published as a conference paper at ICLR 2025
Lemma | solves the recursive formula (I) for the RDP spent. Theorem shows the RDP spent is
non-decreasing over time. The proofs of Lem. and Thm. I A.3
are respectively provided in App. A.2
Lemma 1. Given any E [ E [T], and Tn E [T], we have
Capun T-1+1
4u
IT==1
1 T --++1+3
ist < Tn
Edp,a
2
(2)
T T-1+1
I
1- T-
9n
OW
Theorem 1. For (n, t,Tr)) [N] [T]. Gdp... E ift S Tw, and e nlo
Eddp.n ift = 2-1 >> Tw.
Remark 1. The non-decreasing result of Thm. iidicates that during saving rounds (Mü 0) clients spend at least as much of their privacy budget in each round as in the previous round. In other words, saving decreases over time. During spending rounds (M, clients expend privacy budget constant rate. If budget savings are accumulated than T_ have access to larger budget to spend.
Tn and clients will rdp.
odp... >
4.2 OPTIMAL PERMUTATION OF SAVING-BASED SAMPLING RATES
We optimize the selection of sampling rates. We start from a pre-defined set of N sampling rates. We then choose a permutation that assigns each of the N rates to distinct client. The permutation is selected to minimize the per-round difference between the utility achieved when DP perturbation is not applied (which generally will maximize utility), and the utility achieved when DP-FL framework is used. In the first case, the server aggregates the unperturbed local updates Aet, (i.e., no clipping or noise addition) for all clients n E [N] (i.e., no sub-sampled), and updates the global model as l fr-1 A0" where
A
1 N
Σ
AØ
(3)
In our DP-FL framework, local updates undergo the DP mechanism detailed in Sec. Factoring into the (modified) global update A the clipping norms dy the additive noise multipliers o and the sampling rates di we get
N Σ (b,, (Clip (A#), <.) + +2,) + +1 (1-b,,,))) b(,)%,)
1
(4)
Nq¹ n=1
where g¹ N Σn Ghe 2 z. N (0. (ahe") )
are identically and independently distributed Bern (g%) are also IID. The optimization problem is to choose the {gh hE[N] so that Âœ' closely approximates an unbiased estimate of Att. We define the difference between the respective model updates as
(IID), and b¹,
Error A0" -
Error' has four sources of randomness:
(i) Local dataset randomness: distributions P,,. This randomness is reflected in the local updates A0.
the randomness of local datasets D,,, which are sampled from
(ii) Client sampling randomness: the sampling of clients, represented by the use of random variables b These determine whether client contributes to the round i's local training.
iiii)
Noise addition randomness: the addition of the Gaussian noises 2 and 2
(iv)
Privacy budget assignment randomness: the matching of clients with different datasets Dn and data distributions P,, different privacy budgets e,- Here, [cn]ne[N] are consid- ered random permutation of predefined set of privacy budgets (En)ne(N)-

---

Published as a conference paper at ICLR 2025
To optimize the sampling rates, first develop two upper bounds on the bias term | (Error')
Both bounds build on the clipping bias lemma (Das et al., 2023), cf., Lem. 2 in App. A.6.1 Our theorems extend the results of that lemma to the situation where clients have indiviuuaizzed privacy budgets and use time-varying clip norms c, and sampling rates gh-
Our first theorem, Thm. bounds the expected bias with respect to (W...t)) three sources of random- The proof of Thm.
ness: (i), (ii), and (iii). We denote this expectation as [(()))6))) (Error") [|-
given in App. [.44
Theorem 2. Taking the expectation w.r.t. (i), (üi, and (iii), and for any > 1, we have
((0000000)) (Error") I1
Σ
N
1
In
B (A0))
+
1
G E B (140/1))
(6)
(c)))-)
To minimize this bias term in reasoned fashion we select the d to minimize the upper bound. The upper bound in (6) contains terms that couple g¹. with the pure local updates Aet The latter are not accessible to the server who is responsible for sampling clients. If clients were to select their own 2 based on their local updates, this could lead to privacy leakage and would require additional privacy protection. The coupling between z and A6, can be removed from the first term of the upper bound in (6) under certain conditions. For example, if all clients are sampled at the same rate (9' = g¹) the upper bound reduces to the second term, which still couples qt, with Ad; and the clip norms ct.
if E() (A0%) )) is equal across all n E [N] the first term becomes zero. In such cases,
In contrast to Thm. 2 in Thm. 3 we take the expectation w.r.t. the additional source of randomness, (iv). This results in a bound that depends solely on clipping norms, which makes optimizing the sampling rates, 2h. easier to accomplish. As we now bound the expected bias w.r.t all four sources of randomness (i), (ii), (iii,, and (iv) we denote the expectation as | (())))))) (Error') ||- The proof of Thm.3ji given in App. A.S
Theorem 3. Taking the expectation w.r.t. (i), (ūi), (iii), and (iv), and for any
> 1, we have:
1 Σ E (1A0)11)) N2
Σ gh
9e (())-)
(00, (Error")
The main step in the proofs of Thm. 3 builds on the common assumption in FL that the sampling from Pa and of is independent. This assumption is made without significant loss of generality as privacy budgets are often assigned based on clients' personal preferences and policy requirements. In contrast, the data distribution is influenced by external factors such geographical locations. Such decoupling of privacy budgets and data distributions simplifies the proof of Thm. 3 It avoids the need to model potential correlations between the client's data and privacy preferences. These often unknown or irrelevant in practice.
As per Thm. 3 to minimize (10)))) (Error'] w.r.t. the sampling rates % we solve the following optmiizatinn problem:
Σ dh d' (c)))-1
1
min (n.)
s.t. d nn (m) [N]
where the } are a set of (bijective) permutation maps II, [N] + [N]. Each permutation maps each element of the index set [N] a distinct element of [N]. We apply the permutation to the indices of the fixed set of sampling rates ( 9N to get (gi..... ). The set {qI...., 4N is a hyperparameter in our problem, which constrained by the condition 4n S q for every n E [N]. The optimized choice of the set of sampling rates {91,...,9N' } is reserved for future work. Per g). the optimal choice for {qf...,, .,, 4 is to assign clients with smaller clip norms cf (which will contribute highly perturbed model updates) to have lower sampling rates q and vice versa. The intuition is that by matching the d' to the c,,, we prevent clients who contribute a highly perturbed model update from deteriorating other clients' performance during saving rounds. This reduces clipping bias and allows these clients to preserve more of their privacy budget compared, with the subsequent benefit of enabling them to contribute more in future rounds.
8

---

Published as a conference paper at ICLR 2025
5 EXPERIMENTS
Datasets. To empirically evaluate the performance of our framework against baselines, con- sider widely used datasets. For the Fashion MNIST (FMNIST) and MNIST, we use convolutional neural network (CNN) architecture from (McMahan al. 2017). For the Adult Income dataset, we use multi-layer perception from (Zhang et al. 2020). For the CIFAR 10 dataset, we use a CNN architecture from He et al. (2016). We partition datasets across 100 clients in non-IID manner using the Dirichlet distribution with a default parameter 0.1 (Zhang et al. 2023).
Privacy Settings. To reduce the number of choices for clients' privacy budgets, and motivated by society wherein individuals often share similar privacy preferences (Alaggan et al. 2015 Bocnisch divide clients into three groups. The groups are respectively assigned budgets of Cgrupp.l, (group.2: or 'group.3. We randomly allocate 34% of clients to belong to Group 43% to Group 2, and 23% to Group 3. In other words, Client in Group m. shares En Egroup.m- To account for privacy consumption, we use the Opacus library (Yousefpour et al.) 2021 We consider DP parameter = 10 and choose an extended version of the default RDP parameter a from the RDPAccountant function in Opacus. We apply per-layer clipping (McMahan et al. 2017) to restrict the influence of individual layers by constraining their norms.
et al. 2024), in our experiments
As discussed in Sec. 2 we consider several baselines. The first is the non-private Fe- dAvg (McMahan et al.) 2017) which represents our upper bound on utility without any privacy constraints. The second is De-FedAvg (McMahan al. (017) where use uniform privacy budget, chosen according to the smallest epsilon value of any of the clients. This ensures that no client's privacy budget is exceeded. The third is IDP-FedAvg which is the IDP- inteerrgrat (Boenisch et al. (024) of DP-FedAvg. The fourth is adaptive clipping (Andrew et al.) 2021). To have fair comparison with the baselines, evaluate variant assumes every client's budget is constrained by the smallest value in the group budget tuple (Egroup.1 Egroup.2, 2: 3) The second variant incorporates different privacy groups. Further details on the choice of hyperparameters in our experiments are given in Table in Appendix[A. A.7
Baselines.
variants of our tramework. The first
Global Test Anturacy
Global Accuracy
60
80-
40-
20
20
(a) Test Accuracy FMNIST
(b) Test Accuracy MNIST
Figure 1: Our framework improves accuracy in later rounds compared to the baseline. We plot the global test accuracy vs. rounds for (a) the FMNIST dataset, and (b) the MNIST dataset. In (a), (Egroup, 1, Egroup.2; Egroup.3) (10, 20, 30), and in (b) it equals (10, 15, 20).
Table 2: Global test accuracy for FedAvg without DP constraints, DP-FedAvg with 6,, 10, IDP- FedAvg with non-uniform privacy budgets, our framework with e, = 10, and our framework with non-uniform budgets. For the FMNIST and Adult Income datasets, the non-uniform privacy budgets en are (c 1, fgroup.2, fgnup.3) = (10, 20, 30), and for MNIST, they are (10, 15,20)
DATASET
FedAvg (non-DP)
DP-FedAvg 10
IDP-FedAvg Non-uniform
Ours
Ours
6n 10
Non-uniform
FMNIST
72.95
64.8
65.45
67.90
70.57
MNIST
90.23
76.79
76.94
80.2
83.83
Adult Income
78.93
60.12
70.93
72.14
77.53

---

Published as a conference paper at ICLR 2025
IDP-FudAvg, 5,m30
Privacy Buddget Spent
25-
Ours,
IDF-FudAvg,.s-
20-
Ours, c.220
Fodlwg 10
2.5
Ours, co-10
10-
10
20
Rounds
Figure 2: While both adhere to privacy budgets, our framework follows spend-as-you--e whereas IDP-FedAAg uses uniform privacy spending. The blue solid curves correspond to clients' privacy spending in our framework, while the red dashed curves show IDP-FedAvg. The curves of clients with budgets of 30, 20, and 10 marked with rectangles, circles, and squares, respectively.
Experimental Results. As shown in Table and Fig. 1 our framework yields improvements in the resulting global model's accuracy by spending privacy budget non-uniformly across training rounds. Comparing Columns 4 and 6 of Table - our framework with non-uniform privacy budgets improves global test accuracy over IDP-FedAve by 7.8%, 8.9%, and 9.3% on FMNIST, MNIST, and Adult Income. In the case of using uniform budget of C, 10 across all clients n. our framework achieves respective improvements of 4.7% %,, 4.4%, and 19.9% compared to DP-FedAvg, as shown Columns and 5. We also observe that, our time-adaptive DP-FL scheme comes closest to ideal-case performance of FedAvg (column 2) without privacy constraints. Figure global test accuracy vs. global rounds for our framework with non-uniform privacy budgets and IDP-FedAvg, on the FMNIST and MNIST datasets. This figure shows that while our framework conserves privacy in early rounds, it allocates more budget in later rounds, eventually catching up to and surpassing IDP- IDP-FedAvg by about 8% FMNIST and 6% MNIST in the final round.
In Fig. 2 we present the privacy budget spent by clients from different budget groups (10, 20, 30) across rounds. This figure shows that, while IDP-FedAvg enforces uniform privacy consumption over time, in our framework, clients follow spend-as-you-go saving budgets in the first half of training, and spending more in later rounds. Our experimental results demonstrate that time- adaptive approach boosts the utility of the trained model while adhering to privacy constraints.
In Appendix A.8. we present extended experimental results, including benchmarks on the CIFARIO dataset (Table I1). comparisons with adaptive clipping (Table 7 and evaluations across privacy- related hyperparameters (Tables and 10 and Figure 5) well other parameters (Tables
and 8 and Figure
DISCUSSIONS AND FUTURE WORK
We now diseuss some limitations of work that represent interesting directions for future work. Our spend-as-you-g method reduces reliance on determining when clients should transition from saving to spending by allowing them gradually spend their saved budgets over time, rather than waiting until a specific round to start spending. While our experiments indicate that transitioning from saving spending midway through training generally yields good results, tuning the hyper- parameters involved in estimating the transitioning round may improve utility. However, such hy- perparameter tuning can lead to additional privacy loss (Papernot & Steinke (02T) that would need to be accounted for. For future work, we believe that our time-adaptive DP-FI. framework should be closely integrated with a form of privacy-pred preeey-pres hyperparameter tuning to identify the best rounds in which to transition from savings to spending.
Furthermore, as we demonstrated theoretically and validated experimentally, adapting saving-related hyperparameters to clients' specific privacy budgets can enhance utility. To eliminate the risk of privacy leakage from this adaptation, we provide theoretical optimizations that rely solely on clients' privacy-related constraints, independent of their data. Future research can explore data-and- privacyy joint measures to quantify clients' contributions with controlled privacy leakage and adapt client- specific savings decisions accordingly.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We would like acknowledge our sponsors. This work was supported in part by Discovery Research Grant from the Natural Sciences and Engineering Research Council of Canada (NSERC), by an NSERC Alexander Graham Bell Canada Graduate scholarship-Doctone (CGS D3), by DiDi graduate award, and by the Mitacs Globalink research award.
REFERENCES
Mohammad Alaggan, Sébastien Gambs, and Anne-Marie Kermarrec. Heterogeneous differential 06998, privacy. ArXiv preprint: 150406998, 2015.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34:17455- 17466, 2021.
Barry Becker and Ronny Kohavi. Adult dataset. UCI Machine Learning Repository, 1996. DOI: http:///bbiorg/1002443//////
Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. Bounds on the sample complexity for private learning and private data release. Machine Learning, 94:401-437, 2014.
Franziska Boenisch, Adam Dziedzic, Roei Schuster, Ali Shahin Shamsabadi, Ilia Shumailov, and Nicolas Papernot. When the curious abandon honesty: Federated learning not private. In IEEE European Symposium on Security and Privacy (FuroS& P), pp. 175-199. IEEF, 2023.
Franziska Boenisch, Christopher Mühl, Adam Dziedzic, Roy Rinberg, and Nicolas Papernot. Have it your way: Individualized privacy assignment for dp-sgd. Advances in Neural Information Processing Systems, 36, 2024.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for federated learning on user-held data. ArXiv 16 2016.
Rudrajit Das, Satyen Kale, Zheng Xu, Tong Zhang. and Sujay Sanghavi. Beyond uniform lips- chitz condition differentially private optimization. In International Conference on Machine Learning, pp. 7066-7101. PMLR, 2023.
Li Deng. The mnist database handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6): 141-142, 2012.
Cynthia Dwork. Differential privacy. In International Colloquium on Automata, Languages, and Programming, pp. 1-12. Springer, 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations differential privacy. Foundations and Trends@ in Theoretical Computer Science, 933-4):211-077, 2014.
Adam Dziedzic, John Paparrizos, Sanjay Krishnan, Aaron Elmore, and Michael Franklin. Band- limited training and inference for convolutional neural networks. In International Conference on Machine Learning, pp. 1745-1754. PMLR, 2019.
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients- how easy is it to break privacy in federated learning? Advances Neural Information Processing Systems, 33:16937-16647, 2020.
Robin Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. ArXiv 1712.07577 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp- 770-778, 2016.
11

---

Published as a conference paper at ICLR 2025
Rui Hu, Yuanxiong Guo, and Yanmin Gong. Federated learning with sparsified model perturba- tion: Improving accuracy under client-level differential privacy. IEEE Transactions on Mobile Computing, 2023.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Tian Li, Manzil Zaheer, Sashank Reddi, and Virginia Smith. Private adaptive optimization with side information. In International Conference on Machine Learning, pp. 13086-13100 PMLR, 2022.
Iya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts, 08 2016.
doi: 10.48550/arXiv. wew..6600..8.....
Saber Malekmohammadi, Yaoliang Yu, and Yang Cao. Noise-aware algorithm for heterogeneous differentially private federated learning. ArXiv preprint:2406.03519 2024.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--fficceenn learning deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282, 2017.
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. ArXiv 1710006663, 2017.
Ilya Mironov. Rényi differential privacy. In Computer Security Foundations Symp. (CSF), pp. 263- 275. IEEE, 2017.
Iyy Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. ArXiv preprint:/900 1908. 10530, 2019.
Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with rényi differential privacy. ArXiv preprint:2110.0362) 2021.
Venkatadheerai Pichapati, Ananda Theertha Suresh, Felix X Yu, Sashank J Reddi, and Sanjiv Kumar. Adaclip: Adaptive clipping for private sgd. ArXiv preprint: / /900 07643, 2019.
Maithra Raghu, Justin Gilmer, Jason Yosinski, and Jascha Sohl-Dickstei. Sveca: Singular vector canonical correlation analysis for deep learning dynamics and interpretability. Advances Neural Information Processing Systems, 30, 2017.
Swaroop Ramaswamy, Om Thakkar, Rajiv Mathews, Galen Andrew, H Brendan McMahan, and Françoise Beaufays. Training production language models without memorizing user data. ArXiv preprint:2009. 10031, 2020.
Xiaoying Shen, Hang Jiang, Yange Chen, Baocang Wang, and Le Gao. Pldp-fl: Federated learning with personalized local differential privacy. Entmpp, 25(3):485, 2023.
Ravid Shwartz-Ziv and Naftali Tishby. Opening the black box of deep neural networks via informa- tion. ArXiv prpprin:1103.0081100 2017.
Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig. Rui Zhang, and
Yi 7hou. A hybrid approach to srivacy-preserving federated learning. In Proceedings of the ACM Workshop on Artificial Intelligence and Security, pp. 1-11, 2019.
Stacey Truex, Ling Liu, Ka-Ho Chow, Mehmet Emre Gursoy, and Wengi Wei. Ldp-fed: Federated learning with local differential privacy. In Proceedings of the ACM International Workshop on Edge Systems, Analytics and Networking, pp. 61-66, 2020.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang. Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security, 15:3454-3469, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: a novel image dataset for benchmark- 2017.
ing machine learning algorithms. ArXiv preprint:
12

---

Published as a conference paper at ICLR 2025
Ge Yang, Shaowei Wang, and Haijie Wang. Federated learning with personalized local differential privacy. IEEE International Conference on Computer and Communication Systems (ICCCS), pp. 484 IEEE, 2021.
Xiyuan Yang, Wenke Huang, and Mang Ye. Dynamic personalized federated learning with adaptive differential privacy. Advances in Neural Information Processing 3 36:72181-72192, 2023.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library in PyTorch. ArXiv preprint:2109, 12298, 2021.
Daniel Yue Zhang, Ziyi Kou, and Dong Wang. Fairfl: fair federated learning approach to reducing demographic bias in privacy-sensitive classification models. In 2020 JEEE International Confer- ence on Big Data (Big Data), pp. 1051-1060, 2020. doi: 10. 100.0////iData50022222.2....... 2020.9378043...
Jianqing Zhang, Yang Hua, Hao Wang. Tao Song, Zhengui Xue, Ruhui Ma, and Haibing Guan. Fedala: Adaptive local aggregation for personalized federated learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 11237-112444 2023.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. Advances in Neural Infor- mation Processing Systems, 32, 2019.
13

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 SUMMARY OF NOTATIONS AND BENCHMARKING SCHEMES
We summarize the important notations (including the hyperparameters shown in Table 1 in Table We formally depict the baselines: FedAvg (McMahan et al.] (017) as Alg. 3 DP-FedAvg
Alg. 4
IDP-FedAvg as Alg. 5 and adaptive clipping (Andrew et al. 2021) as Alg. 6 Next, we provide
further details explain the adaptive clipping baseline in comparison with our proposed approach.
Table 3: A Summary of Notation and Hyperparameters'.
N
No. of Clients
Dn
Dataset of Client n
C
Client set R. /
B,
Batch
T
No. of rounds
B
Batch size
L
No. local iterations
En
DP privacy budget of Client n
0
Global model at R. t
RDP privacy spent of Client n in R. t
Edp..n
Ag
Global model update at R. f
Ief
RDP budget RE. of Client n for R. onwards
0
Model of Client n at R. E, I.
Edp..
RDP privacy spend of Client y up to R. t ++1
A6
Model update of Client n at R. t
DP budget RE. of Client n. for R. t onwards
m
Aot
Perturbed update of Client at R.
0²
Global noise multiplier in R. f
Error,
A A
0
Noise multiplier of Client n in R. f
Learning rate
c
Average clipping norm
a
Rényi order in RDP
Clipping norm of Client n in R.
Probability of violating DP
9
Spending- bassd sampling rate Saving-basie -ering-basedd sampling rate of Client n
Ta
Saving-to-spending transition R.
9n
M,
Saving-or-spending mode Loss function of Client n
d'
Sampling rate of Client n in R. / Average sampling rate R. t
L.
q²
Table's abbreviations:
"No." for "Number", "RE." for "Remaining", "I." for "Iteration", and "R." for
"Round".
Algorithm 4 Differential Private Federated Aver- aging (DPFeedAg) (McMahan et al. 2017)
Algorithm 3 Federated Averaging d'vgg) (McMahan et al.) 2017)
(Fe-
Inputs: No. elients N. No. global rounds T, No. local iterations L. noise multiplier clip
sampling rale g, loss functiios Ca. local datasets D.,, leaminng rate X, batch size B3
Imputs: No. clients N. No. glohal rouds T,, No. local iterations T.,
loss functions C.., local datasets P.,, leaming rate batch size
1: Initialize global model 8
2:
for each global round É [2') do
1: Initialize global model gd
3: + Sample clients with probability q.
2:
for each global round é [2]
4:
for each client n E C in parallel do
3: C¹ +- Sample clients with probubility g-
5: Aet, = CcieentUpdaeeeeeeeee n. (c).
4: for each client n Ct in purallel do
5: A0", = enntppaate n, -1))
6:
7: Aggregate Ao' Enecs Aog.
end for
6:
end for
8: noise Ao' 4- A0 + +N(00, 21)
7:
Aggregate 40" = En, Áo;
9: Update of r--1 + Set
8: Update 6¹ = 1 det ON"
7N"
10: end
9:
end for
Def C1 sentupdat (t. (t, n. .c)c)
Def clieett Updst= n, 8²)
I: Initialize local model 0f 0²
1: Initialize local model 85.0 =
2: iterationn E [1]
2: for local iteration I E [I] do
3: (15, ( 6- Split D., to size B hatches
3: /Pal + Split 2,, size batches
4: for each batch 15, do
4: for each butch
5: gt.l o:i-1 Eorple ven ven(ot (ot (xx.))
5: 0- 0 Vix, Ven (ot 1 (0.0))
B
6: end for
6: end for
7: end for
7: end
8: Compute AP', 8/: 8:,0
8: Return Ae L 61.0
9: Clip Áot, = A0t min [
10: Return Ae!
14

---

Published as a conference paper at ICLR 2025
The Adapting Clipping Baseline. In this paper, we consider the adaptive clipping method (Andrew)
et al., 2021) as baseline for our time-adaptive DP-FL approach. the extended simulations (cf. App. A.8), we benchmark that method against our approach. The method is formally presented as Alg. 6 As shown in Line 13, the server dynamically adjusts the clipping norm based on a specified quantile r of the distribution of clients' updates. The goal of this method is to minimize the dif- ference between the clipping norm and the quantile in the distribution, aiming to achieve the same objective as ours: improving the privacy-utility tradeoff. In contrast to our time-adaptive approach, which is independent of the client's 's data and can be done prior to training, the method (Andrew) al. 202T) introduces privacy risks during the quantile approximation. To mitigate these risks, and as is shown in Line 2 of the SetCl vetClipping ipping function in Alg. 6 the method (Andrew et al.] (021) incorporates a supplementary DP mechanism that allocates part of the privacy budget to preserve privacy during quantile estimation. However, this results in lower remaining privacy budget, re- quiring a larger noise multiplier o, as computed in Line of SetSigma gima in A in comparison to our approach.
Algorithm 6 DV-FedAvg-M with Adaptive Clip- ping (Andrew et al. 2021))
Inpots: No. elients N. No. global rounds T. No. local iterations L. noise multiplier clip norm sampling rate loss Functionn [En (il'he') local datasets (2, heeNN- client-side side learning rale A. clip-related learning Au "y quantile
Algorithm 5 Individualized DP-FedAvg (IDP-
FedAvg), a natural integration of IDP (Boenisch et al. (024) to FL
server-side side leaminng batch size B, probability of violating 6,
Inputs: No. clients N, No. global rounds T, No. local iterations L. local privacy budgets en. average clip norm c, sampling rate q. loss Junctions C.., loval datasets 2n,, learning rale X, butch size B. probu- bility of violating
1: a =Set.Sigma(4 T,, o.)
2: Initialize global model 00
3:
for each global round E [2'
4: C¹ + Sumple g.V clients unifornly.
I: (ennJEEiN #BeLPrivacyParamssc (en]aE:N) T,
5: for each client n E C² in parallel do
2: Initialize global model da
6:
(B), A0;,)= Cliientcccne
3: for each global round è E [2] do
7: end for
8: Aggregate Ao" = =Encrt Āør
4: C* + Sample clients with probubility q-
5: For each client n C in parallel do
9: Add noise ÂØ 20t +N110, (c')²0²1)
6: Ad,, = =ClientEpdaaee(. n, gt- oo,)
10:
Average Ao + n Ao"
7:
end for
11:
Compute Âot + 300-11 + (1 20)
8: Aggregate Âo" =Incet Áe;
12:
Update
- 1 2,,00
9:
Add noise 30 6- A0 + NN o"?))
13:
cftlssacli g (1 Incneeeeeen. n 9.7% do.
10: Update 8¹ 0² 78"
Agt
14:
end
11:
end
Def c1 (tiinnuppatta (",,,
Def MiieeeentDdddteeel (t, 0", cx)
I: Initialize local model 8 = 8²
1: Initialize local model 0f. 0²*
2: iteration E [1]
2: for local iteration / E [8] do
3: [8,) |Pal/B <- Split D., to size B hutches
3: [B.)_Bl/8B + Split D,, to size B batches
4: for each hatch 15 do
4: for each batch B, do
5: ghd 01i A Ven (2m(0t/- ((x.v))
A Exxuiss vea (oh (a.s))
B
5: 0t'' 0
6: end for
6:
7: end for
7: end for
8: Compute Ao g4.
02.0
8: Compute A0', = 04.2 02.0
9: Compute 21100A
9: Clip Ao;, = A0 min Taui
10: Clip ăe", = A0, min 1, |
10: Return 5o;,
11: Return 6, Â8"
Def Sat Se vacyyaaraa (c, (cn)neIN), T.
Def Set c, T, on)
1: for each elient n E [N] do
I: ā =CotNoisn(e, g. T.))
2: Set local noise multiplier a= =eettoire(e..
2: o (+ (2mp)
1/2
3: end for
4: Compute o +- (1 EnEIN] on
3: Return
5: for each client n E [N] do
Def setclippig ((b), 6,,11 Jngee, m..g. g,75 do)
6: Set local clip norm Cn. ce
7: end for
1: Aggregate b' = Σ Eneet by,
8: Return d, (o-))entt Jee(N)
2: Add noise B¹ <- b¹ + (U, o2()
3: Average D1
+ B$
4: Update of l1 al exp (>x0( - 7))
5: Return e+1
15

---

Published as a conference paper at ICLR 2025
A.2 PROOF OF LEMMA
We use induction to solve the recursive formula
According to d1. when In. Edp..
(g and when 2 < Tn, client spends Cup.. T(g)=
Cobo.n - Sap..n
9t
By substituting Grdp.
dd ad we obtain 2 kdp. T-I
Im
We now assume 'ddp,"
satisfies in (2) for
c-1 every 2 < t < lft < Tn by substituting rdp..n in
we obtain
2
Endp,n
-- T-
T
Edpp.n
4n
2
1-1 náp.
(T - + 2)
4n
4.
.dp..
f-1
In
(9)
q
T t+1
q
T 1--+22
(92)
<dp.n
1-1
(10)
T - t 1
2
- 1-42 -
9z
Eddp.n
4n
(11)
T 1+2
T 1 1+22 2
9
T-1+1
i=1
21-1
Endp,n
qn
1
gn
1
(12)
1++
f=1
If Tn. by substituting Sdp.a in
II. we obtain
2
1 Endpin
T-
(T
T, + +2
2
Th "ddp,n
F=1 Edp..
ddp.
ddp.
(13)
T Tú +1
T Tx
T - Tn + -(xx) )²
Idp.n
Tu-1
Tn
On
9
(14)
T
2)
T
Ta
2
Edpp,n
9n
4
1
(15)
T
Tn +
T
Tn + 2 2
Tn
+
i=1
T,-1
Eddp.n
1
9n
1
(16)
T
Tx
T
Tx
+
1=1
If t > Tn, by substituting
xdp.
f-1 in II. we obtain
Edp. 1
1-1 (T - 2)
1-1
Erdp.n
Edp..
=dp..
Edp..
(17)
T 1.
T - 1. +
T--1
On 2
1-1
6rdp.n
1
(18)
4dg.n
T Tn +
T T, + +1 +
16

---

Published as a conference paper at ICLR 2025
A.3 PROOF OF THEOREM 1
We use the explicit solutions of the recursive formula I.. presented in Lem. 1 When
to prove this theorem.
Tn.
2 1-1
fnd,,
1-1 'ndp.1
Cddp.n
4n
qn
(19)
T t t+1
T ++ +i
i=1
2 2-2
2
Crdp.
qn
9n
(20)
T - t 2
q
T +
9
iml
On
Qn
Edd..
(21)
T + 2
q
1=1
1
1
In
1
1
(22)
T t+1
1
T
+
q
++2
))
2
9m
Edp.n
In
II
1-
9n
9
T
2
9
1)
+ 2)
(23)
The right-hand side of (23) is larger than equal zero because On S q. Therefore, in this case 2-1 "ddp. 2 'dp... When T
On 2
T.
To
Eddp.n
II
1-
(24)
"dp..
T Tn +
T Tn + +1+1
9
TT, -
2
Endp,
qn
9r
(25)
T
Tn 2
Tn + 2 2
9
i=1
To
9n
Cdp.no
(26)
T Ta + 2 +i
==1
9n
1
1
(27)
T T-t+1
T T +2
q
T
T, +2 2
2
To
(nm)
In 12) ()
9m
Cupp.n
II i=1
1 T
(28)
+2
(T T, 1)
The right-hand side of (28) is again larger than equal zero because. Therefore, in this case t-1
also have Te 2 T. "ip.. Lem. aalso shows 6'pp.n -dp.n when 1. Ta-
app..
17

---

Published as a conference paper at ICLR 2025
A.4 PROOF OF THEOREM 2
If the expectation is taken (i) the randomness of local datasets, (ii) the sampling of clients, and (iii) the randomness of injected Gaussian noise, then the bias is simplified as follows:
E (1)
(Error')
N
(()).(0))(()))
A00
(b;, (Clip (A0% () + 2 + (1 by)
N
N
(())
AØt
b% by q¹
(Clip (A0 <tt))
(29)
N
un q²
Σ
(())
1
(Clip
[ ch))
(30)
N
dh
oh
Σ
(A)
A0'
(Clip ( (00)444)))
(31)
n
g²
q²
d
B(g)
(AO))
(1)) (s0',
(Clip (2O ne <())
(32)
N
d (e)
E(()
(A0%)
(A
(Clip (A0t (()))
(33)
N
N
n=1
N
dh E (110%11")
Σ
E00 (A%%)
(34)
N
q²
N
(ch)--
The equality (29 is due to ((a) (z,) = E(a)) (z.) = 0. The equality (30 is due to E(s)) (b:)) = g..
The incquality 33 is due to triangle inequality. The incquality 34 due to the clipping bias lemma (Das et al. 2023). given any p > 1.
A.5 PROOF OF THBOREM 3
If the expectation is taken w.r.t. (i) the randomness of local datasets and (ii) the sampling of clients, (iii) the randomness of injected Gaussian noise, and (iv) privacy budget assignment randomness, then the bias is simplified follows:
18

---

Published as a conference paper at ICLR 2025
(600 (Error")
(50
1
Σ ((0,6000
(b% (Clip (D0 (n) + z (1 - )
N
q²
1
(100000)
A0h
by (Clip (A (2,
(35)
N
q'
by2
(0.00000
AA
(Clip (A (n,)
(36)
N
dh of
Σ
E (10)
A0c 12
(Clip (D0" (n))
(37)
N
1
Σ
N
A0e
q'
gn
dh
(Clip (s0 chh)
(38)
N
qr
g²
q²
q²
1
g¹
dh
Σ
((0)
20%
((o) (ghg' A0% (Clip (A0t <th
(39)
N
q¹
q'
on
Be()) (A0%) )
Σ ((0)
+
N
9º
N
dh Bees (A0), - (Clipp ( (A0 <2)))
B((w))
Ees
(40)
N
(gt
((#
BeS (A0%) )
+
Σ E (iv)
N
n=
c
(Clip (A <c)))
((v)
Beo
(A0%
(41)
q²
((v)
(())
Bao (Ax))
+
1
Σ
N
(iv)
E(a)
(1 11
(42)
N
N
(c)))-1
The equality (35 is due to ( (z,) = E(aa)
Z
= 0. The equality (36 is due to E (b.) = 9.
The inequality 40) is due to triangle inequality. lemma (Das et al. 2023) given any p > 1.
The inequality 42 due to the clipping bias
We next further simplify the first and second terms on the right-hand side of (42
19

---

Published as a conference paper at ICLR 2025
The first term equals zero:
E (5o) (4/
Ih g:) B (A0%)
() (I|00 l") (ii)))
(1-
Th
(43)
qr
g
())) (1 1")
Pr (en = Es) B(io)
1
cn = Es
=
(44)
oe
1E|N]
-E (140%11)
Σ iE[M]
1
(45)
N
L
Σ
(46)
N
qp)
RE[N]
1
N'N
qº )) = O.
(o (| I")
N
(47)
N
Equality
43 is due to the independency of randomness between (i) and (iv). Equality
45
is
because of our assumption that the sampling from Pn and of 6n is independent. Equality
447
is
because Σ 9/2 =
The second term on the right-hand side of (42) can be further simplified into:
dh (6) (1102119)
B(x0)
(ct)
gh 1
E()) (|) B(()
(ii))
(48)
8t (c,)a-1)
-Eo (1100111))
Σ
Pen = Ei) B(ae)
1/2
En éi
E1)
(49)
9d (ch))
p
+E|M
=E(o (11
Σ
(50)
N
(2))-T
iE|M
dn dd (c))a-
EE (1
(51)
N
RE[N]
Equality 48 is due to the independency of randommess between (i) and (iv). Equality of our assumption that the sampling from P. and of en is independent. Combining 422 (47 and
49) is because
ST Thm. 3 is proved.
A.6
EXTENDED BACKGROUND
A.6.1
SOME USEFUL. LEMMAS FROM PRIOR WORKS
Lemma [Clipping bias Das et al. 2023) Suppose db(E) (where & denotes the source of ran- domness) is unbiased estimator of i.e., Ee (ő(E)) 6. Let b(E) denote the clipping bias of Clip (ő(E), e), i.e. b(c) = 11ø - Eg (Clip (Ø(E), c))ll. Then for any > 1,
b(c) < Es (1({(E)1
(52)
---1
20

---

Published as a conference paper at ICLR 2025
A.6.2 DIFFERENTIAL PRIVACY
Definition ((e, 5)- Dwork al. (2014). The randomized algorithm A X - R with domain
and range R satisfies (c. for any two neighboring inputs D, E x that differ by at most one record, and any measurable subset of outputs S _ R,
Pr Pr(((D) E S ( S
(53)
In (53) the privacy budget E R. controls the extent which the output distributions induced by two neighboring inputs may differ. The ô E [0, 1] quantifies the probability of violating the privacy guarantee. Allowing a larger d [0. 1] improves utility at the cost of more relaxed (weaker) privacy guarantee. One way to relax the DP guarantee is to use c)-ééíi DP (RDP) (Mironov h.17 The a > is the order of Rényi divergence between distributions == Pr (r(())) and
P = Pr (A(D))), defined as
1 Ra (PI) = T-a a
a Pr
P
log Expor
(54)
While the Rényi divergence can be defined for < including negative orders, the RDP defini- tion Mironov (0117) is based on a 2 1 and is outlined as follows.
Definition 2 (Rényi DP (RDP) Mironov (2017)). The randomized algorithm A + R with domain X and range R is (ot, RDPPDP iff for any neighboring inputs D, D' X, we have
R, (Pr (P( Pr (r((D))) Sc.
(55)
When accounting for total privacy consumption composition property than DP. RDP allows the privacy budget to accumulate linearly with the num- ber of training rounds (Mironov 2017). This simplifies the tracking and management of privacy budgets over time. We next recall a lemma from (Mironov) 2017). Lemma shows how RDP can be converted to DP when needed.
an iterative algorithm, RDP offers smoother
Lemma 3. If A is (dd algorithm, it also satisfies (c, for any 5 where
a- log + loga
= Edpp + log
(56)
a a
To implement privacy guarantees, we use the sampled Gaussian mechanism (SGM) Mironov et al. 2019), formally defined as follows.
Definition 3 (SGM Mironov al. (211))) Consider the algorithm A which maps subset D C x to R. and has Eg fe-sensitiiitty c. The sampled Gaussian mechanism parameterized by the sampling rate q E [0, 1]. c, and noise multiplier >> 0 is defined as
Go,n(D) == A(fx) x E D is sampled with Probability 4}) + (0 Io
(57)
where each element of 'D (Poisson) sampled independently at random with probability q, and NO IooII is spherical w-dimensional Gaussian noise with per-coordinate variance o²
Lemma 4 (Mironov et al. (2019)) The SGM Gooog with = 1 guarantees (R,e)-RDP, where
2ag
E
A.7 EXTENDED EXPERIMENTAL SETUP
We conduct our experiments in Python 3.11 using Pytorch leveraging the x 1.4 24 GB GPU. Below, provide additional details the experimental setups used in Sec. 5 to analyze how adme-adaptive DP-FL framework enhances the privacy-utility tradcoff and in Appendix A.8 which extends experiments for further analysis.
Details on Datasets. For our experiments, we use FMNIST, MNIST, Adult Income, and CIFARI0 datasets. Both FMNIST and MNIST datasets have training set of 60,000 and test set of 10,000 28 x 28 images, associated with 10 labels. The Adult Income dataset consists of 48,842 samples with 14 features and is split into training set of 32,561 samples and test set of 16,281 samples.
21

---

Published as a conference paper at ICLR 2025
The CIFARIO dataset consists of 60,000 32 x 32 color images in 10 classes, with 6000 images per class. There are 50,000 training images and 10,000 test images.
Simulation Parameters. Throughout our simulations, we use SGD optimizer and momentum equal to 0.9. We also use a CosineAnnealing Annealing learning rate scheduler from (Loshchilov & Hutter] (016) for faster convergence. In Sec fix the spending-basee sample rate (during spend mode) to = 0.9 and the average clipping norm to c = 250. We consider the transition from saving round to spending round occurs in the middle of training. Le.. given the total number of rounds T 25, we set Tgoup.1 group.2,, T gropp3
13. The obtained results are averaged over three runs. In Table 4 we summarize other hyperparameters, including learning rate (A), number of clients (N), batch size (B), number of local epochs (L), and the saving- based sampling rates of clients from privacy groups 1, 2, and 3 (Agrap.1 1. (group.2 2, Igroup,3).
We set T 25, T grroup,1 Table 4: Parameters for different datasets, used in Table 2 and Figure 2
T group.2, groopp.3 = 13, 0.9, and 250.
Dataset
ppppp Sgrop, Spropp3)
A
N
B
L
(Agasp, Opropp 2 Rgospp,3 33)
FMNIST
(10, 20, 30)
0.001
100
125
30
(0.5, 0.7,
MNIST
(10, 15, 20)
0.001
100
125
30
(0.5, 0.6,
Adult Income
(10, 20, 30)
0.01
80
32
5
(0.6, 0.7, 0.8)
1.50
Average Training Loss
Time Adaptive DR-FI
1.25
IDP-FedAug
1.00
0.75
0.50
0.25
5
10
15
20
25
Rounds
Figure 3: Average Training loss of clients in our time-adaptive DP-FL scheme plotted ver- sus the IDP-FedAvg baseline with FMNIST dataset in training rounds T 25. We set (fgroup, (group. 2: (group.3) (10, 20, 30) our scheme and IDD-FedAvg.
A.8 EXTENDED EXPERIMENTAL RESULTS
Impact of Training Rounds on Model Convergence. We extend experiments to more training rounds- T E {25, 50, 100). For example, in Figure 4 set T 50, and plot the global test accuracy vs. communication rounds. is evident from Figure 4 that for our time-adaptive DP- FL framework, as the number of training rounds increases, the upward trend in the accuracy starts slowing down. However, increasing the number of communication rounds does not always improve accuracy. This is because, with more rounds, the privacy budget is distributed across more rounds, resulting in a lower budget per round. Consequently, the increased effect of perturbation can degrade the privacy-utility tradeoff. This is demonstrated in our FMNIST and MNIST experiments, as shown in Table 5 in which we report the final-round test accuracy across different schemes. As shown in the third column of Table when training rounds increase from 25 to 50 and from 50 to 100, Fe- dAvg (the non-DP baseline scheme) consistently demonstrates an upward trend in both MNIST and FMNIST experiments. However, our scheme (fitth column of Table and IDP-FedAvg (fourth col- umn), which operate under limited group privacy budgets (Egroup,1 Egroup.2 2 Egroup.3 3) (10, 20, 30), do not exhibit the same consistent improvement. They exhibit an upward trend from 25 to 50 rounds but not consistently from 50 to 100 rounds. Notably, the best performance amongst the DP ex- periments of Table 55) is achieved by our scheme, reaching 75.63% after T = 100 rounds for the FMNIST dataset, and 90.78% at T 50 rounds for the MNIST dataset.
Impact of Different Privacy Budgets on Model Utility. We present additional experimental results to evaluate the impact of stricter privacy budgets ( (1 (group, Egroup.3) = (2, 5, 10) and (5, 5,5)
22

---

Published as a conference paper at ICLR 2025
Global Test Accuracy
80-
Time Adaptive DR-FL
60
40
10
40
Rounds
Figure 4: Global test accuracy for increasing number of communication rounds. In this figure, we use the FMNIST dataset, . 100 clients, L 30 local iterations, (Egroup,1 Egroup,2: Egroup.3) (20, 20, 20). 250, and 0.8.
Table Benchmarking our time-adaptive DP-FL scheme against the baselines in terms of global test accuracy and across varying datasets and number of training rounds (T). We set (Egroup,1 Egroup. Egroup.3) (10, 20, 30) our scheme and IDP-FedAvg.
Dataset
FedAvg (non-DP)
IDP-FedAvg
Ours
25
72.95
62.57
66.55
FMNIST
50
76.00
71.80
75.51
100
80.14
71.29
75.63
90.23
64.53
74.69
MNIST
50
93.42
89.57
90.78
100
95.91
87.00
90.15
Global Test Accuracy
Adaptive
IDP-FodAvg
60
40
0
10
20
30
40 50
Rounds
Figure 5: Test accuracy for our time-adaptive DP-FL framework vs. IDP-FedAvg, using strieter privacy budgets (Egroup.1: fgroup.2: 2: fgroup.3) = (2, 5, 10). In this figure, we use N = 100 clients, T = 50 global rounds, L 30 local iterations, 250. and q = 0.8.
on model utility (test accuracy). The results are presented in Figure 5 and Tables 6 and 7 As expected, observe that lower privacy budgets hamper utility. In particular, in Table we bench- mark our scheme against the IDP-FedAvg baseline using two sets of non-uniform privacy budgets, (10, 20,30) 30) and (2, 5, 10), evaluated across two datasets. Our findings suggest that the time-adaptive DP-FI. framework yields considerably higher utility than IDP-FedAvp also under stringent privacy constraints. Similarly, Table focuses on uniform privacy budgets and further confirms that even with reduction in privacy budgets from (10, 10, 10) to (5, 5, 5), our scheme consistently outper- forms the corresponding baselines.
Additional Baseline. We benchmark our scheme against the adaptive clipping method Andrew al. (002)) with pseudocode provided in Algorithm 6 We present results in the third and fifth columns of Table 7 This baseline is designed for uniform privacy budgets and is parameterized by the server- side learning rate X, and momentum parameter 3. which are not privacy-specific. To ensure a fair comparison with our scheme and other baselines in our paper, set these parameters X, 1.0
23

---

Published as a conference paper at ICLR 2025
Table Benchmarking our time-adaptive DP-FL scheme against the baselines in terms of the final- round test accuracy and across varying privacy budgets (c (grrupp.1 Cgnopp (group.3). We set T = 25 and for c {10, 20, 30} and T 25 and for c {2, 5, 10), (grrop,1 Igroup, Ogroup.3) 33) = (0.3, 0.7).
Datasct
Privacy Budgets
IDP-FedAvg Non-uniform
Ours
Non-uniform
FMNIST
(10, 20, 30)
62.57
66.55
FMNIST
(2, 5, 10)
60.99
65.75
MNIST
(10, 20, 30)
64.53
77.38
MNIST
(2, 10)
63.35
66.50
Table 7: Benchmarking our time-adaptive DP-FI. scheme against the baselines in terms of the final- round test accuracy and across varying uniform privacy budgets (grup,1 T = 25 and L = 30.
6 Egruu,
Egroup33 We set
Dataset
Privacy Budgets
Adaptive Clipping (9. A.) = (0, 1.0)
DP-FedAvg
Adaptive Clipping optimal (8,, A.)
Ours
FMNIST (10, 10, 10)
60.23
64.8
67.64
67.90
FMNIST
(5,5,5)
52.39
51.06
52.39
60.79
MNIST
(10, 10, 10)
65.59
76.79
78.04
80.2
MNIST
(5,5,5)
55.48
61.45
55.48
69.07
and Bg 0.0. column 3, we use these default values, while column 5, we select the optimal values from set of possible choices. As shown in the table, scheme consistently outperforms adaptive clipping, even when the baseline's parameters are optimally tuned.
Effect of Number of Clients Model Utility. We experiment with different numbers of clients- N E {30, 60, 75]-for for the MNIST dataset to validate the applicability of our time-adaptive DP- FL framework across various scenarios. Additionally, our framework outperforms the baselines, in terms of the utility of the trained model. Our results in Table g indicate that for all the different numbers of clients that we consider, framework remarkably surpasses the utility of the baseline.
also perform experiments to analyze if
Table 8: Comparison of model utility on a varying number of clients and comparison of model utility for time-adaptive DP-FL with baselines for varying number of clients
Number clients
SETUP
IDP-FedAvg Non-uniform
Ours Non-uniform
Privacy Budgets
30
(10,20,30) 20)
72.35
73.34
(10, 20, 30)
78.69
83.83
75
(10, 20, 30)
70.93
77.53
The Choice of Hyperparameters. We evaluate our DP-FL framework with different choices of snperparameters-ddffiee saving-based sampling rates (Agroup. 1 Igroup.2 2: Igroup.3) and different transition rounds (I (Egroupp11 T T Tg). The final-round test accuracies for different choices of (1group.1 Ogrop. (grmpp3)) and across both MNIST and FMNIST datasets, are presented in Table [9] In this table, in Column 3 we set these rates (0.5,0.6,0.7), in Column as (0.3, 0.5, 0.7). and in Column 5 as (0.6, 0.6, 0.6). As shown the table, our scheme, which uses lower sampling rates during saving-e.28 for all i E [3]. 4group, is smaller than 0.9 in this table- outeorrrrroorm the IDD-FedAvg baseline (Column 6) that uses a uniform sampling rate over time. This table also shows that our method is relatively robust against the clients' choice of saving-basee based sampling rates, consistently achieving performance between that of -eddAgg and the ideal case of FedAvg without DP (Column 2).
24

---

Published as a conference paper at ICLR 2025
Table 9: Evaluating the impact of saving-based sampling rates of different privacy groups, (ggroup,1 1 Ogroup, (g)oup.3), on our time-adaptive DP-FL scheme in comparison with the baseline. We set (Cgroup,1: (group. Cgroup.3) = (10, 20, 30), T 25, L 30 and N 100, T group. gropp2
T group.3 = 13. q- 0.9, 250, À = 0.001, and B 125.
DATASET
FedAvg noa-DP
Ours
Ours (0.3, 0.3,0.3,077
Ours
IDI-FedAvg
(0.5, 0.7.
(0.6, 0.G, 0.6)
MNIST
90.23
72.72
77.39
71.6
64.53
FMNIST
72.95
70.57
66.55
67.75
62.57
The final-round test accuracies for different choices of saving-to-spending transition rounds (I (rgooup.1. grogup. gg), for both MNIST and FMNIST datasets, are presented in Table 10 We set the total number of rounds as = 25. In this table, in Column we set the transition rounds as (7,7,7), in Column 4 as (7, 13, 19), in Column 5 (19, 13, 7), and in Column 6 as (19, 19, 19). As shown in the table, our scheme, which transitions from saving to spend mode sometime between the first and final round-i.e., for all [3), 1 < T group, (Column 7) which can be viewed as special case of ours with transition rounds set to 1,1. This table shows the robustness of our method to the client's choice of transition rounds, showing less than 2% variation in accuracy across different choices while consistently achieving performance between that of IDD-FedAvg and the ideal-case of FedAvg without DP (Column 2).
25 33--ouperformms the IDP-FedAvg baseline
Table 10: Evaluating the impact of saving-to toenddinng transition rounds of different privacy groups, (Tgrup, groppp.,, T gmap.3), baseline. We set (fgrup,1, , Egrpp. 2, (grup.3)
our time-adaptive DP-FL scheme in comparison with the
(10, 20, 30), T 25, = 30, N = 100, (Agroup,1 1 4group.2: Mgroup.3) = (0.3, 0.5, 0.7), = 0.9, 250, À 0.001, and B = 125.
DATASET
FedAvg
IDP-FedAyg
nom: DP
(7,7,7) 7)
(7, 13, 19)
(19, 13,
(19, 19, 19)
MNIST
90.23
74.38
74.69
72.24
73.88
64.53
FMNIST
72.95
66.72
65.29
65.34
67.5
62.57
Experiments on The CIFAR10 Dataset. We run experiments on the CIFARIO dataset. The final- round test accuracies of our time-adaptive DP-FL framework in comparison with the FedAvg (non- DP) and IDP-FedAvg baselines are presented Table [1] The results suggest that our proposed approach surpasses IDP-FedAvg. by lowering the gap the ideal case of FedAvg by about 9%. We note that the test accuracies reported for all schemes in this table are relatively lower than those we reported earlier in this paper for the MNIST, FMNIST, and Adult Income datasets. We hypothe- size that this happens due to the increased complexity of the CIFAR10 dataset, particularly when distributed in a non-iid manner in an FL setting with N 100 clients.
Table 11: Benchmarking our time-adaptive DP-FL framework against the baselines using the CI- 10 dataset. We set (4 (4gmup. 1, fgmup.2 'group.3 = (100, 50, 25), T = 50, T, 30, N 100, (Agroup.L 1. 9grop,2 9group.3 ) = (0.5, 0.5, 0.5). 9 = 0.9, c = 250, = 0.001, and B = 125.
DATASET FedAvg
IDP-FedAvg
Ours
CIFAR1O
44.42
34.97
35.41
25


Reviews:
[{"review_id": "vzvjslqnrb", "reviewer": "Reviewer_s8p8", "summary": "The paper presents a novel approach for DP FL wherein instead of making the clients spend the privacy budget uniformly over all communication rounds, as in traditional DP FL approaches, the clients allocate their privacy budgets non-uniformly over time. Specifically, the method suggests that clients save their privacy budgets in early communication rounds since coarse-grained features are learnt in early rounds and spend more in later rounds where more fine grained features are learned.", "questions": "1. What is the $\\delta$ for experiments in Table 1 and Figure 2? Can you elaborate on why such an high $\\epsilon$ in 10, 20, 30 is acceptable? How many number of communication rounds are considered?\n\nMinor:\n1. Clearly defining notations, and relationships between different notations would make paper easier to understand, like DP to RDP mapping.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The approach is novel and intuitive.\n2. The privacy analysis of the algorithm is provided.", "weaknesses": "1. Insufficient experimental evaluation - Only two datasets and baselines are considered.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "ttKvJMUzpe", "reviewer": "Reviewer_19qN", "summary": "The paper studies federated learning with distributed differential privacy, where each client adds noise to its model update/gradient before sending to the server, and a trusted server aggregates the noisy updates for an overall $(\\epsilon,\\delta)$ aggregated model. The authors point out that the early rounds are less sensitive to noise while later rounds are heavily affected by the introduction of noise. Hence, the paper proposes that privacy budget can be saved in early rounds so that the later rounds can spend more privacy budget as they need it more. To achieve this, the paper proposes to use a lower sub-sampling rate in earlier rounds and normal sampling rate in the later rounds/spending rounds. The paper proves that given a set of sampling rates, one can optimize the assignment of these sampling rates to clients (based on their personalized privacy budget) to minimize an upper bound of the expected clipping bias. Empirical evaluation shows that spend-as-you-go achieves higher performance under the same privacy budgets.", "questions": "I raise a few questions in the earlier section of weaknesses when I list my concerns. I would appreciate it if the authors could address the questions listed above.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Improving the performance of DP-FL is an important and interesting problem\n* The adaptive spending scheme is intuitive and well motivated\n* Theoretical analysis provides insights on the algorithm and bounds the expected clipping bias\n* The paper is well written and easy to read", "weaknesses": "* In section 3, the algorithm for the spend-as-you-go budgeting scheme and the FL training loop are described in great details. However, the motivation of each design choice is not clearly explained. I suggest the authors to edit the section to include explain the rationale behind each design choice that defers from the conventional FL algorithm.\n* The configuration of the hyperparamters of the proposed method are not explained. For example, how are the set of lower sampling rates determined? Why do we choose the values presented in the Appendix? Also, how is the switching round $T_n$ chosen?\n* The paper could benefit from additional experiments.\n  * I would like to see the empirical evaluation on the effects of the set of sampling rates and the switching time.\n  * I suggest the authors to also include the non-private baseline in the figures for reference.\n  * If I understand correctly, the proposed adaptive spending scheme also works for non-personalized FL (all clients share the same budget) as well as non-FL (i.e., DP-SGD). Will the spending scheme also bring performance improvements? It would be interesting to see how the proposed scheme would perform in these settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "6wQtBLeqgP", "reviewer": "Reviewer_iRT5", "summary": "This paper addresses the problem of heterogeneous client-level DPFL with non-uniform privacy expending across time (and clients). The reasoning behind the idea is that, as claimed, saving privacy budgets in early rounds lets clients with stricter privacy requirements (with smaller clipping threshold or larger noise scales) spend privacy unevenly across rounds compared to clients with more relaxed privacy requirements. This enables them to spend more privacy in later rounds when more fine-grained features are learned.", "questions": "I ask the following questions based on their order in the draft.\n\n* In line 169, the authors claim that it is unfair to compare with the adaptive clipping methods. However, these methods are proposed for reducing the noise level as the training continues, and are directly related to the goal of this paper, even more than IDPSGD-based method (I-DPFedAvg). As such, comparison to these baselines is crucial. Also, they have proposed some methods for reducing the extra privacy leakage for tuning clipping thresholds adaptively. So there is no barrier for comparing the proposed method with them. \n\n* The privacy analysis done in alg.1 is performed **before** training starts. It gets $c$, $q$, $\\{q_n\\}$, $\\{M_n^t\\}$ and $T$ all as hyperparameters, and as output, returns $\\{q^t\\}$, $\\{q_n^t\\}$, and $\\{c_n^t\\}$. First, having this many hyperparameters before training is unrealistic and makes the applicability of the proposed method limited indeed. Second, I think the privacy analysis in alg1 is incorrect. The reason is that a client can compute the amount of privacy that it has spent **only after each round that it really participates** in the FL. The value of sampling rate $q_n^t$ implicitly determines the number of times the client $n$ participates during the total $T$ rounds. It is impossible to account for the amount of privacy a client spends before even starting training. What if simply out of randomness, the client $n$ turns out to participate in all rounds $T$ (as if its sampling rate $q_n^t$ was 1 for all $t$). How do you explain about this scenario? How can you claim that you can always run alg.1 before even starting the training, and return the set of $q_n^t$ based on its result?\n\n\n* The threat model considered is based on having \"honest-but-curious\" clients and \"honest\" server. How does the analysis in your paper and the proposed method work if you consider an \"honest-but-curious\" server? For instance the very recent work [1] below also aims at improving utility in the system by a noise-aware aggregation (it should be added to your related works). Does your algorithm work in this threat model too?\n\n\"Noise-Aware Algorithm for Heterogeneous Differentially Private Federated Learning\", ICML 2024 (https://arxiv.org/pdf/2406.03519v3)\n\n* How do you determine the set $\\{q_n^t\\}$ and $\\{M_n^t\\}$ in your experiments? Especially, where is the latter coming from?\n\nSome minor comments:\n* line 119 and 122: $(\\epsilon, \\delta)$-DP is the common notation\n* line 137: provide a brief introduction to SGM\n* the order of lines 14 and 15 in alg1 should be exchanged.\n* line 6 in alg2 needs \"5\"inputs (one input is missing)", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The problem of time-adaptive privacy spending is interesting. \n* The existing related works are mentioned and discussed clearly.", "weaknesses": "There are multiple weaknesses in the  work as mentioned below.\n\n* The current writing of the draft is hard to understand, and requires one to read it multiple times to get a clear understanding of the work.\n* There are some big assumptions that make one to hesitate about the applicability of the work. \n* Some of the theoretical analysis seem to be incorrect (see the questions below).\n* The existing close algorithms (e.g., adaptive clipping threshold) are not evaluated.  \n* The existing datasets in the experimental results are pretty simple (MNIST and FMNIST). Running experiments with more complex datasets, e.g., CIFAR10/100, will improve the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "lQzSMKs8Li", "reviewer": "Reviewer_UXeM", "summary": "This paper proposes a differentially private federated learning algorithm with flexible noise injected over the training time. They do so by manipulating the client sampling rate: smaller rate for the first course of the training (saving phase) and larger rate for the later part of the training (spending phase). The author intensively analyzes the privacy accounting for both phases and shows how to select the optimal client sampling rate.", "questions": "1. When do clients decide to switch from privacy saving to spending phase? \n2. Is the data sensitivity taken into account when computing the differential privacy noise scale?\n3. Would model heterogeneity be a challenge with the proposed algorithm?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea of cutting down the privacy budget spent in the early training phase is fascinating and quite new.\n2. Extensive theoretical analysis of the proposed method is given.\n3. Experimental results show a moderate amount of privacy budget saved throughout the training, supporting the proposed mechanism.", "weaknesses": "Limited empirical comparison with other adaptive differential privacy methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)