Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellation
Authors: Roie Reshef
Kfir Yehuda Levy
Venue: ICML 2025 poster (2025)
Keywords: Machine Learning
Privacy
Federated Learning
Primary area: social_aspects->privacy
TL;DR: An algorithm for private federated learning in the partial-participation setting with optimal excess loss and computational complexity.

Abstract: This paper addresses the challenge of achieving Differential Privacy (DP) in Federated Learning (FL) under the partial-participation setting, where each machine participates in only some of training rounds.
While earlier work achieved optimal performance and efficiency in full-participation scenarios, these methods could not extend effectively to cases with partial-participation.
Our approach addresses this gap by introducing a novel noise-cancellation mechanism that ensures privacy without compromising convergence rates or computational efficiency.
We analyze our method within the Stochastic Convex Optimization (SCO) framework and demonstrate that it achieves optimal performance for both homogeneous and heterogeneous data distributions.
This work broadens the applicability of DP in FL, providing a practical and efficient solution for privacy-preserving learning in distributed systems with partial participation.

Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellation
Roie Reshef
Kfir Yehuda Levy
Abstract
In this work, we focus on guaranteeing DP in centralized FL systems, which are prevalent both in academic research and in many real-world applications. In such systems all machines communicate through a coordinating server which orchestrates the training process (Kairouz et al., 2021b). A key challenge here is that multi-round communication can compromise privacy, and research integrating DP in FL (Huang et al., 2020; Wei al., 2020; Girgis et al., 2021; Noble et al., 2022; Lowy & Razaviyayn, 2023; Lowy et al.. 2023; Gao et al., 2024) focuses on balancing data masking with model performance to protect privacy while maintaining performance.
This paper tackles the challenge of achieving Dif- ferential Privacy (DP) in Federated Learning (FL) under partial-particr partiipppatiiiiaaiion,, where only a subset of the machines participate in each time-step. While previous work achieved optimal performance in full tull-participation settings, these methods strug- gled to extend to partial-paticcipation scenarios. Our approach fills this gap by introducing novel noise-cancellation mechanism that preserves pri- vacy without sacrificing convergence rates or com- putational efficiency. We analyze our method within the Stochastic Convex Optimization (SCO) framework and show that it delivers optimal per- formance for both homogeneous and heteroge- neous data distributions. This work expands the applicability of DP in FL, offering an efficient and learning
While many FL protocols assume full- tull-participation from all machines, real-world deployments often face inconsis- tent device availability, limited connectivity, or scheduling conflicts. This leads to partial-participattoo, where only subset of machines engage in each training round. En- suring DP in these settings is more challenging but crucial for expanding FL. to large-scale, resource-constrainee and dynamic environments.
practical solution for privacy-preserve in distributed systems with partial participation.
Moreover, in the context of privacy, FL systems can be cate- gorized into trusted and untrusted Server cases. In Trusted Server scenarios, devices rely on the server's s assurance of correct DP implementation. However, in more practical cases with an Untrusted Server, devices must protect their data from potential misuse by the server.
1. Introduction
Federated Learning (FL) is an innovative framework within Machine Learning (ML) that facilitates collaborative learn- ing across wide range of decentralized devices or systems (McMahan al., 2017; Kairouz et al., 2021b). Privacy is central concern in FL. highlighting the critical importance of safeguarding personal data during the training process.
Ensuring DP in centralized FL has mainly been studied in the context of Empirical Risk Minimization (ERM) (Huang et al., 2020; Wei et al., 2020; Girgis et al., 2021; Noble et al., 2022), focusing minimizing training loss. How- ever, translating ERM guarantees to population loss leads to suboptimal bounds, as shown in (Bassily et al., 2019).
Differential Privacy (DP) is a strong framework for assess- ing and mitigating privacy risks (Dwork et al., 2006a;b; Kasiviswanathan et al., 2011). It formally ensures that data analysis results remain largely unchanged regardless of individual's 's data inclusion, thus preserving data privacy (Dwork& & Roth, 2014).
Recent works have explored population loss (generaliza- tion) guarantees under DP (Lowy & Razaviyayn, 2023; Gao et al., 2024; Reshef & Levy, 2024), providing optimal guarantees for both trusted and untrusted server cases. No- tably, (Lowy & Razaviyayn, 2023) addresses both full and partial-participation but relies on mega-batches, leading to super-linear complexity of O (n:/22). where n the total dataset size, and (Gao al., 2024) build upon the algorithm of (Lowy & Razaviyayn, 2023) in iterations to improve the
'Equal contribution 'Faculty of Electrical and Computer Engineering, Technion, Haifa, Israel. Correspondence to: Roie Reshef < wwworrcampuu..coommm wwwpps.tcccmiooo.c..... www.nion..c.iii....... Kfrr Yehuda Levy Setiryley@@tcchnion.ce
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Balancing Portial-Participatiin and Efficiency via Noise Cancellation
complexity O (n In contrast, (Reshef & Levy, 2024) achieves linear complexity of O (n), similar standard non-private training, but is limited to full-participation.
Structured noise for DP has been explored in prior work. The work of (Koloskova et al., 2023) suggests adding cor- related noise in ERM settings using standard gradients, but without utility guarantees or support for partial partial-paticipatioo. Moreover, the work of (Hafeez et al., 2021), while also us- ing noise cancellation, addresses smart metering rather than ML and offers no formal guarantees.
Despite these advances, a gap remains: Can we develop a DP-FL method for partial participation that achieves optimal population loss while matching the computational cost of standard training? In particular, we seek a procedure with overall complexity linear in n, the total number of data samples used throughout the training. In this work, we address this gap by proposing a novel approach that ensures near-optimal population-los guarantees under DP, while preserving the computational efficiency of standard partial-patiiciaation methods.
The work of (Bassily et al., 2014) established lower bound for DP-SCO, and (Bassily et al., 2019) presented an algo- rithm that achieves this bound, though with super-linear computational complexity x 323/2. This was later improved by (Feldman et al., 2020), which achieved optimal guaran- tees with a sample complexity linear in n, but only provides privacy for the final iterate, making unsuitable to be ex- tended FL settings.
Concretely, in our approach, each participating machine em- ploys exactly one new sample for every round participates, and use it to performs two stochastic gradient computations, thus keeping the total gradient computations linear in n. Thus, if we have a total of M machines but only a subset of m machines (m I M)) participate in each round, for a total of T rounds then overall we employ n = mT samples.
In the FL setting, notable work is (Cheu et al., 2022), which provides the optimal bounds for the trusted server case, though it relies on an expensive vector-shuftling rou- tine, resulting in a computational complexity greater than n3/2. Another important work is (Lowy & Razaviyayn, 2023), which combines the large-batch technique of (Bass- ily al., 2019) with other mechanisms to achieve optimal results for both untrusted server (called ISRL-DP in their work) and trusted server (called SDP in their work) cases, operating in the partial-paticciattinn setting with compu- tational complexity of n²/2, and (Gao et al., 2024) further improving it to 9/88 However, the works of (Lowy & Raza- viyayn, 2023; Gao et al., 2024) achieve the optimal bound only in the tull-participation setting, while suffering an extra M m their excess loss bound in
For the trusted-server scenario, we present a simple method that achieves an optimal convergence rate of O ( x where di is the problem's dimensionality, and e is the privacy level. This rate matches the lower bound substantiated in (Bassily et al., 2014). In the more challenging untrusted- server setting, we develop a novel mechanism that yields <Md where M an optimal convergence rate of O ( en is the total number of machines. This matches the lower bound substantiated in (Lowy & Razaviyayn, 2023).
V
multiplicative factor of V setting.
Our work builds on the full-participation approach of (Reshef & Levy, 2024). To address the challenging un- trusted server and partial-participationn case, we introduce a novel noise-cancellation mechanism that effectively ob- scures the information sent to the server, rather than the independent noise injection employed by (Reshef & Levy, 2024). Additionally, we tailor each machine's 's noise injec- tion based on the number of rounds it participates in, thus balancing privacy and performance.
the
Our approach draws on the private extension of (Levy, 2023) introduced in (Reshef Levy, 2024), which achieves both optimal convergence and computational efficiency un- der trusted and untrusted server cases, but only in full- participation setting. We extend these results to the more practical partial-participaal setting. retaining the same tight population-loss guarantees and linear computational complexity.
Related Work. Several studies have made significant con-
2. Preliminaries
tributions to DP in the context of SCO, particularly in ERM (Chaudhuri et al., 2011; Kifer et al., 2012; Thakurta & Smith, 2013; Song et al., 2013; Duchi et al., 2013; Ullman, 2015;
Here we provide the necessary background for analyzing private federated learning.
Notations: We will employ the following notations:
Talwar et al., 2015: Wu et al., 2017: Wang et al., 2018:
[n] = (1....,n). au == Et= 07, and Ik (x) = arg min ||x - w|l.
Iyengar al., 2019; Kairouz et al., 2021a; Avella-Medina et al., 2021; Ganesh et al., 2023). However, these works mainly focus on training loss, and attempting to extend their results to population loss guarantees through standard uni- form convergence (Shalev-Shwartz et al., 2009) results in sub-optimal bounds, as discussed in (Bassily et al., 2019; Feldman et al., 2020).
2.1. Federated Learning
We focus on Stochastic Convex Optimization (SCO) scenar- ios where we have M different machines, and each machine
2

---

Balancing Partial-Participatte and Efficiency via Noise Cancellation
i E [M] has convex objective function, Jt K. + R,
We also make assumptions about Lipschitz: 3G > 0 such:
[1(52), about Vi E [M], E 2,
which takes the following form:
[(x) = Ez-D, [x]
[f; z) fi 2) - G ull, Mr,UEK
Where K. C Rd is a compact convex set, and Dj is unknown data distribution, from which machine i may draw i..d. samples. Our goal is minimizing the average objective:
This also implies that
= G,Vr EK.
Smoothness: 3L > such:
[V - f( -alie)=>>-(((aaii S 1| yll, Va K
f(x) = M Σ f()z)
(2)
Since these assumptions hold for fi( z) for every i E [M]. E 2, they also hold for f((x) and f(x). These
In federated learning the machines aim to collaboratively minimize the above objective, where each machine i may
assumptions imply the following (proof in Appendix B.1):
Bounded Variance: Do E [0, such:
acess a dataset of S; = {......, An. C Z, (Z, is the set where the samples of machine i reside), of ny i.i.d. samples from D,. Upon utilizing these data samples the learning algorithm eventually outputs a solution Tout E K. Our performance metric the expected excess loss (Zow))
E V - so², Y
(4)
Bounded Smoothness Variance: 3or E [0. L] such:
E [[ - Vf(())) (Vi((y;)) ((()i)
R(Zou) == E [
min =EK.
(3)
S oo 1| u1l? V
(5)
The expectation is w.r.t the randomness of the samples, well as w.r.t. the (possible) randomization of the algorithm.
Bounded Heterogeneity: S E [O. such:
We focus on centralized systems where machines can syn- chronize and communicate through a central entity called the Parameter Server (PS), which orchestrates the learning scenarios where at each communication round & only random subset of the machines Me S [M communicate with the PS.
M
1 M
(6)
process. We further focus on Cartial-Participane
Bounded Smoothness Heterogeneity: 36, [0, L] such:
[(V - -)(==)- (V -(())
We focus on the common parallelization scheme inspired by Minibatch-SGD (Dekel et al., 2012). In this scheme, the PS maintains a sequence of query points {re) which are updated using gradient information that is gathered from the participating machines. Concretely, time step t the PS sends the query point F2. to a of randomly chosen ma- chines Me S [M.]. Each machine i E .M, draws new sam- ple žt.i ~ Dr (taken from Sz), independently of past sam- ples, and calculates a gradient estimate It. = V [((; se,s;; where the derivative is with respect to x. The PS aggregates the gradient estimates into g. [M EieM, It. which is then used to compute the next query point T1+1
M
1=1
S 16
VI
These properties allow us bound the variance of the aver- age of the gradients (proof in Appendix B.2):
Lemma 2.1. Let M C [M], and 2; ~ D,, Define g(x) M Eiem ff(zz; for for all a E K. If 24 are independent, and M is chosen uniformly from all subsets of size m.
E [ - [((3)) < 1 0²
M
Vo EC
M
B1(((()) - vf(z)) (gly) - v5()))
The independence of the samples guarantees that 9t, is an unbiased estimator of V f (zz), meaning that E [9r, [r]] = fx+)))) It is useful to conceptualize the calculation of It.4 Vi(eri 2.,)) as sort of (noisy) Gradient Ora- cle: upon receiving a query point Z₁ E K, this Oracle outputs a vector It.s E Rd, serving as an unbiased esti- mate of fx(z)). Moreover, assuming M2 is picked uni- formly over the M machines, directly implies that g. = M. ΣiEM, It is an unbiased estimate of V fzz)).
s m of + M
M <2 | Va,yeK
Under these assumptions, g(x) is an unbiased estimate of fxx).. When m = M, heterogeneity disappears, and as m gets smaller relative to M, heterogeneity becomes more significant. Additionally, since M-m M-T < 1, we can use the bounds o² + g² and o + <7. Thus, heterogeneity in partial participation adds an extra term to the variance. In this work, we assume the number of participating machines per round is fixed, and denote by m.
Assumptions: We will make the following assumptions:
Diameter: 3D > 0 such: ||æ- - yll S D, Vx, y E K.
3

---

Balancing Participaottiiiitiionn and Efficiency via Noise Cancellation
2.2. Differential Privacy
Lastly, for the case of Gaussian noise, there is more fitting DP definition based on RDP:
The core concept of Differential Privacy (DP) is to compare the algorithm's 's output with and without private informa- tion and quantify the difference between these outputs. The closer they are, the more private the algorithm is. This is measured by the difference between the probability distribu- tions of the outputs.
Definition 2.7 (Zero- - Differential Privacy). (Bun & Steinke, 2016) A randomized algorithm A (5, p)- zero-concentrated differentially private, or (6. p)-xCDP, if for all neighboring datasets S, S' that differ in a single ele- ment, and for all a > 1, we have:
The Rényi Divergence is a popular difference measure between probability distributions:
m (A(S) (A((")) S + po:
We define p-zCDP as (0,
Definition 2.2 (Rényi Divergence (Rényi, 1961)). Let P, be probability distributions over the same set, and let a >> 1. The Rényi divergence of order between P and Q is:
Note that if an algorithm is (a, pa)- for all a > 1, it is also (5, p)-CDD and visa-versa. Also note that according to Lemma 2.3, a Gaussian mechanism is
||| using Lemma 2.6, if an algorithm is - 20 -zCDP, and PV
1 Da (PIIQ) = a - log Ex<P
[
(((x))
((()) a-1 1)
7-CDPP it is also
( + PV 2 log (t) -DP, for all å E (0, 1). By choosing to work with -2ZDP, we get that p = |لها| which the signal-to to-ise ratio, and we also get that O (B) E E (2),
We follow with the convention that 0 = 0. If (==) but P(x:) A for some æ, then the Rényi divergence is defined to be co. Divergence of orders 1, oo are defined by continuity.
with o + pV + (t).
2
Notation: X ~ P,Y ~ Q, we will use the terms Da (PIIQ) Da (XIIY) interchangeably.
In federated learning, we consider the case where DP guaran- tees must be ensured individually for each machine E [M]. The challenge in this context arises because each machine communicates multiple times with the PS, potentially re- vealing its private dataset. The machines don't 't' trust one another, and thus cannot allow them to uncover private data. In this work, we mainly focus on the Untrusted Server case, where the PS cannot reveal private data, and DP guar- antees must be ensured for the information machines share with the PS. In the Trusted Server case, machines trust the PS and may share private data, but it is still necessary to prevent machines from uncovering each other's 's private data from the PS.
Adding Gaussian noise is popular in privacy, so we find the following lemma useful (proof in Appendix B.3):
Lemma 2.3, Let P = N(u, Io²) and Q- = Ni A, lo²), two Gaussian distributions. Then, D. (PI()) = a||A|
20
The classic differential privacy definition:
Definition 2.4 (Differential Privacy (Dwork et al., 2006a;b)).
randomized algorithm A (e, -)-differentiaally private, or (c, d),,P if for all neighboring datasets S, that differs in a single element, and for all events O:
P (A(S) = 0) S E (P(P = 0}+ +
2.3. Lower Bounds
The term neighboring datasets refers to S,S' being ordered sets of data samples that only differ on a single sample.
Here we elaborate on the existing excess loss lower bounds for the DP trusted and untrusted server scenarios, and show that they coincide with the upper bounds that we establish. Notably, existing lower bounds holds irrespective of the training method, and therefore apply simultaneously for both full and starting points of such lower bounds is to assume that the learning process may access a total of n data points.
A privacy measure that relies on the Rényi divergence:
Definition 2.5 (Rényi Differential Privacy (Mironov, 2017)). For 1 < a S oo and 2 0, a randomized algorithm A is (a,c) Rénéi differentially private, or (a, R)-RDP, if for all neighboring datasets S, S": D. (A(S))LA(S)) S
settings. Concretely, the
RDP implies DP, as shown here (proof in Appendix B.4): Lemma 2.6 (Mironnov, 2017)). If A satisfies (a, RDDP then for all 8 E (0. 1), it also satisfies (ct log 1) 8)-
In the Trusted Server setting we can think of the server as learner that may access n data points, and aims to output a solution that maintains a DP level of e. The work of (Bassily et al., 2014) establishes lower bound of S ( va the excess loss in this case, which matches the term in our upper bound which is related to privacy.
on
DP. In particular, if A satisfies (a, aq" RRDP for ev- ery a > 1. then for all 8 E (0,1), it also satisfies
en
c +p 220g /2100(()),6) -DP. DP.
In the Untrusted Server setting we have M machines,
4

---

Balancing
and Efficiency via Noise Cancellation
which aim to collaboratively compute a solution given stochastic optimization problem. Yet each machine and aims to maintains& a DP level of for the data that it shares during the learning process. It is also assume that the over- all data used by all machines is of size n. The work of (Lowy & Razaviyayn, 2023) establishes a lower bound of 22 matches the term in our upper bound which is related to privacy. The extra VM factor exists because we have M devices that hold privacy, instead of just one (the PS).
to yield corrected momentum estimate d, in the spirit of (Cutkosky & Orabona, 2019), with technique called Stochastic Corrected Momentum (STORM), This is done as follows: d1 := V (1): and Vt >> 1:
de - V (zi x) + (1 -1- (d) V((T)-13))) (9)
+ vMd on the excess loss in this case, which
Where Be E [0, 1] are called corrected momentum weights. It can be shown by induction that E2 [de] E [V f but generally E dd [ma] * ( in contrast to standard SGD estimators. However, as demonstrated in (Levy, 2023) by choosing corrected momentum weights of 33 x 1. the above estimates achieve an error reduction at time-step t of:
VR en
Note that the first term in our lower bounds Ω V2
matches the known lower and upper bounds of excess loss in non-DP setting. Finally, note that in our setting, only a subset of m < M machines participate once in each round, for a total of T rounds, so we have n = ml..
Bl -V((=)) 0o (
1 ml
(oa (oe+ +))
E
=
Where 82 S (0² + of D2) and F2 s 05 D2). This implies that the enror decreases with t, in contrast to standard SGD where the variance E ||=SGD
3. The μ²² Technique
2 == E El - Vf((x)) remains uniformly bounded by (o² + (2) as shown in Lemma 2.1.
As mentioned earlier, our technique for the partial- participation case builds on the previous approach of (Reshef & Levy, 2024) for the full-participation case. Here we discuss the algorithmic techniques behind the latter, which will later serve us in our design of an optimal and efficient approach for
Upon choosing 3e = _=_1 and denoting d: == a,d, the gradient estimate update of n² 2SD in Equation (9) can be written as follows (proof in Appendix C.I):
8, 0z (((5)))) - Oie-1 V (((-1i)))
The approach of (Reshef & Levy, 2024) strongly relies recent (non-DP) algorithmic approach called -SGD (Levy, 2023). Next we elaborate on it.
g: 0t-1 + 8t.
(10)
3.2. Differentially Private 2²² Federated Learning
3.1. The J.GD Algorithm
The 2SGD approach is naturally extends to the FL setting as follows: At every time-step, the PS sends the current
The SSG (Levy, 2023) is a variant of standard SGD with two modifications. Its update rule is of the following form: W1 = 01 E K., and Vt 2 1:
query point x, to all machines. Then, each machine i E [M] updates local estimate of the (weighted) gradient qr.i = de, based on its local (and private) data and on 22. This is done similarly to Equation (10), with 21, being the sample used by machine i time-step t:
We+1 =IIx (w:- - mardd)
014
at+1
F++1 a1:111
W1+1
(8)
01:+1
St,i = V Vf 25,) ar-1 (((
Here O2 > are importance weights for each time-step. We use 04 x f, giving more weight to more recent updates.
4r, - + $1
(1I)
Note that this update rule maintains two sequences: {weJe, {2, ht, where fe is sequence of weighted averages of the iterates {we).. de is an estimate for the gradient at the average point, i.e. of V (zz), which differs from stan- dard SGD which employs estimates for the gradients at the iterates, i.e. of fww). This approach is related technique called Anytime-GB GD (Cutkosky, 2019), which is strongly connected to the notions of momentum and accel- eration (Cutkosky, 2019; Kavis et al., 2019).
In the trusted server case, (Reshef Levy, 2024) sug- gests to aggregate these estimates by the PS into qi := Σi= Ut.5- To maintain privacy, the server adds fresh noise Y, into qi and use qt qe + Y, (a common technique in DP training (Abadi et al., 2016)). In the untrusted server case, (Reshef & Levy, 2024) suggests adding fresh zero- mean noise Y2, to the gradient estimates Qt,i, in order to ensure privacy, and then send qr, == qt. + Y,, to the PS. It aggregate these private estimates into q = 37 ΣM Tr.i-
In the standard SGD version of Anytime-GDl one would use the estimate V ff(z 21). However, the SGD ap- proach suggests to employ a variance reduction mechanism
In both case, the PS then updates w, and x, similarly to Equation (8), while using qe instead of a,de. Upon choos- ing appropriate noise magnitude and learning rates, this
5

---

Balancing Cartial-Participatii and Efficiency via Noise Cancellation
approach ensures optimal convergence guarantees for DP training in full- palticaatiiiitoonn settings, while preserving the linear computational complexity of standard methods.
uses these estimates to update qa (Equation (10)).
This approach works well in the Trusted server case, where the PS can receive the non-private st, from the participat- ing machines, and use them to update qt. Similarly to the ap- proach of (Reshef & Levy, 2024) the PSS then injects noise into qe to maintain its privacy, and then updates according to Equation (8). We describe this approach in Appendix F. and substantiate a convergence rate of O + x
There is a natural trade-off in selecting the noise magnitude: larger noise improves privacy but slows convergence. As shown in (Reshef & Levy, 2024), the S²DDGD algorithm is substantially less sensitive to individual data samples compared to standard SGD, so we can maintain privacy with relatively small noise magniuuess, thus achieving optimal convergence.
Nevertheless, extending this approach to the Untrusted server case not trivial. Concretely, one can think of the natural extension where each machine that participates at round computes a private estimate of St and then pri- vatize it by adding fresh noise št, St, + Yi, which is then sent to the PS. The latter utilizes the private &1, to update q which is then used to update in the spirit of Equation (8). Unfortunately, ensuring the privacy of &,, that way, leads to a cumulative noise in the global estimate qt which leads to highly suboptimal performance. Next, we will see how to mend this approach by injecting correlated noise to st,i, which leads to noise cancellation qt, thus enabling to achieve optimal performance.
4. Our Approach
Here we discuss the challenges of extending FF- to Partial-Participatiin scenarios (Section 4.1), and suggest a natural modification that remedies these challenges in the Trusted server case, thus leading to optimal and computa- tionally efficient methods for this case. Unfortunately, this modification leads to suboptimal performance in the more challenging Untrusted server case.
Towards addressing this gap, in Section 4.2 we provide new perspective on DP- in the full-participation case, which induces novel noise-cancellation technique, allowing us to extend their method to Partial-Partciipation settings. Finally, in Section 4.3 we discuss the properties of the resulting gradient estimates, which are later used in to analyze our approach. In Section we present our complete algorithm (Algorithm 1) and its guarantees.
4.2. Noise Cancellation
We focus addressing the untrusted server partial- participation case. Towards doing so, provide an alterna- tive perspective on the approach of (Reshef & Levy, 2024) for the full-participation. In the full-participation case, Equa- tion (11) implies qr. = = 87,6. Since qt,; = qt,s + Ye,.. we can write the update rule for qe in the PS like this:
4.1. Challenge in Partial-Participation
The performance of DP- strongly relies on the as- sumption that every machine can access the entire sequence of query points {xe which is crucial for computing qu. (see Equation (11)). Unfortunately, this assumption longer holds in purtial-participation setting.
qc = -T-1 + St + Y, YL- == Q1-1 + 5t.
Where := 1/ E St.5. Y. = t EM Yr.., and Se := St +Y, - YY-1. The above update rule for or can be equivalently achieved as follows: at every round t each machine computes ă., = St, + Yr, Y which is equivalent to injecting s; with a fresh noise term while can- celing the previous one. Then each machine sends s,, to the PS, which aggregates them into ă, = M ΣM 50,6, and updates the estimate q. = q + 5t. The sequence of noise terms that we inject into St,i, {Yr, Y,-1,h is now correlated.
Alternative 1: A natural resolution is to update q. based on the sequence of queries that machine may access:
Qr. = --- + ar f 21.)) - aL- f(
(12)
Where / --1 T is the previous time-step that machine i partic- ipated in. Unfortunately, this approach yields suboptimal guarantees even in standard non-DP particpppatiiiiaaionnn set- tings. The delayed updates lead to an excessive error for qt.i. resulting a degraded convergence rate of O (v without DP requirements. We elaborate it in Appendix G.
This perspective now induces the following approach for the prrtiialpaticiipatiin setting: at each time-step t, only some of the machines, MM S [M], are participating. We employ this update rule (Algorithm l):
v even
Alternative 2: Another natural solution is to simply let the PS calculate q:. This suggest the following approach for the particplattiiiiaiionnn setting: A machine participating at round t computes $t, (Equation (11)), and sends it the the PS, who averages them into 8t m ΣiEM, St,5 and
St,i =o Vf(( 24,)) 04-1 a4-1 V
St.i St,i Yy, 1
8, =
1
Σ
St, & q = q. + &z
(13)
M

---

Balancing Cartial-Participatie and Efficiency via Noise Cancellation
And the PS then uses qe update we and de as in Equa- tion (8). The noise Y2,, being:
Now, will define the error of of our weighted corrected momentum estimate &, = Qt or (x+)) Note that the update rule for E, is (proof in Appendix D.3):
{ Ut.i M
Y1,=
(14)
E = Et (3t - 3p)
(15)
(Y-15 i i Me
And the above implies & Σ (s+ - 87). The above enable to bound the error Er (proof in Appendix D.4):
Where the noise Ve,i Pt. is the new independent noise generated time-step in machine i, and Y,, is the last noise generated up to time-step t in machine i. As we can see, for the machines that participate at time-step 1, we gen- erate a new noise, and the machines that do not participate at time-step retain their previous noise. Using this noise, we can see how q. looks like (proof in Appendix D.I):
Lemma 4.3 ((Rehhef & Levy, 2024)), Algorithm I with weights az = ensures:
M m 22
E l|x 11 == E 11ge - O4 V(()))
0
m
M
Lemma 4.1. Our definitions of qt. qt, Yt, above imply:
5. DP- with Partial-Patticiiption
M
Our complete algorithm depicted in Algorithm 1, is based on the noise cancellation idea we describe in Equations (13) and (14), combined with the D'2DGD approach described in Equation (8). At each time-step t, we select a subset of m machines M,. Each machine E .M, computes the gradient estimate correction St,i, and then adds fresh noise term yt, and removes the previous noise Y; := Yı-1,i (omitting the sime-step index for practical implementation) to get a private correction st, It is transmitted to the PS, which averages these corrections, updates its weighted noisy gradient estimate Õt. and in turn uses d to compute the next iterate Wt+1 and query point Tz+1-
a. = +
Yz
1=1
Due to our noise cancellation, the effective injected noise on the PS time t is Y, -. Ei= Yr,,. Note that Y, is a sum total of M different independent noises (one from each machine), but normalized by the number of machines participating at each round m. Also note that since for some machines Y,, = -,i, the noises of different time-steps are not independent. These two points will make it harder for to evaluate the effect of this noise the excess loss.
To balance privacy with performance, we found it neces- sary to set each machine's 's noise injection proportionally to the number of time-steps it participated in up until now, because a machine that participates more rounds may leak more private data, which requires more noise to maintain its privacy. Thus, we set oh,3 x NN.s, where N is the number of time-steps machine participated up to time step L.
4.3. Gradient Error& & Sensitivity Analysis
Here we analyze the properties of the st,; estimates depicted above, as well discuss the properties of gt- These proper- ties are crucial for analyzing the privacy and performance of our approach. Our analysis follows similar lines to (Levy, 2023; Reshef& & Levy, 2024).
We define: Jt.i == V
It.s == fa 2..1.). Ir.: = (z,,) 9: := (zxz)) By these notation we can write $t, = aggt.: 19-15:-1.5- We will also use the notation F [ denote the expectation conditioned over all randomization up to time-step t 1. Using this notation we get that: E [st,a] = a a 19-19:-1.5 We define 31,1 == a.gt. - 09-19:11.1 and 5, = agg: 1311-- Next we bound $2,5 (proof in Lemma 4.2):
5.1. Privacy Guarantees
We shows how the privacy of Algorithm 1 depends on the injected noises { (proof in Appendix E.
Theorem 5.1. Let K. Rdd be a convex set of diameter D, and (f(: (();))))ez be a family of convex G-Lipschitz and T.- smooth functions, and S = GG+ 2LD. Then invoking Algo- rithm I with noise distributions Yt Pt, =N (0, (o,I) and any learning rate 1) >> 0, ensures that for any machine E [M], that acts at time-steps T, the resulting sequences (3r, is E -CDD where: P; = 25 E of.
Lemma 4.2 (Resheff & Levy, 2024)). Let K. C Rdd be
convex set of diameter D, and (si(: ()(=;)) 2, be a family of convex G-Lipschitz and L-smooth functions Assume Oe = t and define S == G+2LD, Ō = -0200
- D:
Proof Sketch. First, assume that S; and S are neighboring datasets, meaning that there exists only a single time-step I" E T. where they differ, i.c. that 2,. 24
||st,1|| S S,, and E. |s2
1 S-- m
02
M -
M
Where the in expectation bound furteer assumes that the samples in Z, arrive from i. D..
We then use the post processocessing property (Lemma A.4) to say that the privacy of ( is equal to the pri-

---

Balancing Partial-Participall and Efficiency via Noise Cancellation
Algorithm DP- with Partial-Partccipation
minl 28T (2og SLT
pDm
and o
Inputs: #iterations T. #TotalMachines M, #Machines per step m, initial point To. learning rate > O, importance weights {az > 0}. noise distributions {Pr. NO,, ] datasets {S: = {z1,i..... 2T,, Initialize: set W1 21 = 20. go = 0, and Y, 0, vi
( N1.5. with No.5 being the number of time steps n that machine participated up to time step t, and for any datasets {S: E of he(A)) then Algorithm I satisfies eg. zCDP w.r.t gradient estimate correction sequences that each machine produces, i.e. {8r,)iie(M).eE
for / ,,...., T do
Choose M2 M with [M, m for every Machine i E MM, do
Furthermore, S, consists of i.idd samples from distribu- tion for all E [MI) and M, are also chosen uniformly in an i.i.d manner, then Algorithm I guarantees:
Actions of Machine i:
Retrieve 2,, from S;, compute It,i = Vf(
and 1, [1 zr,i)
RT :=][((TTT]]
min f(z) TEK.
Update St,i 04.9t.i 14-199--1
Draw Vt. . (0,,))
Update S1, St,s + M1.s -
G + 4LD
28 21 log T)
4D
+
+
Update Y; yt.i (saving the last noise)
T
VmT
pmT
end for
Actions of Server:
Proof Sketch. The privacy guarantees follow directly from Theorem 5.1, and our choice of oř.
Aggregate &t = 1 ΣiEM, $1,5
Update q = qt-1 + 8t
Update W++1 11x(Wr n/q:)
p²
Update Fe+11 (1
as+1
It 01:11
de+1 W1+1
25
Σ
o
=S
Σ
45² (1 + log T)
No.
arill
SE
TE
end for Output: 2T
ITc
p²
p²
2 (1 + log T)
N
2 log T)
k
LET;
p²
p²
vacy of ErSSAEEET 3r TET:"
Using the composition rule (Lemma A.3), we bound the privacy of them with the sum of the privacy of each individual member. Now, recalling that the noises cancel each other and thus:
2 (1 + (1+logg) (1+ log (Ti) S
Regrading convergence, in the spirit of D²DDGD analysis (Levy, 2023; Reshef & Levy. 2024), we bound the excess loss using the anytime theorem (Theorem A. rewrite the expression to get to the form of Lemma A.5 and use it to bound, and separate the terms of E, and Y. We already bounded in Lemma 4.3, though we bound M-m but the bound on the parts of Y, is harder, since the se- quence (Yt) is not independent each other, as it was in (Reshef & Levy, 2024), since in each round different machine participate. We get:
Σ
Σ TEILTET
ST, + Ut.ir
WET
TSIRTET
W-I < 1.
We may use Lemma 2.3 and obtain that ErstSten: 37, is Ai,
-CDP. Using the bound ||s+,]|| S. which holds for any T E Ti due to Lemma 4.2, we show that A.,; 2S. Thus, we are 25 of
20
-CDP. Using the above together, we get
that heeT is 252 ΣIen of ZCDP.
Σ E (Y x² w++1)
1
E llw,
w 1
41
5.2. Convergence Guarantees
M
1
E |1
Guarantees of Algorithm 1 (proof in Appendix E.2):
m²p(2
Theorem 5.2. Let C Red be a convex set of diameter D and (f((=))) be a family of G-Lischhizz and L-smooth functions over K,, with o,g E [0, G), E [0, L}, and let [Mihe be subsets of [M] of size m, define
Where p = m2 the probability that machine participate M
at time-step for all machines and time-steps. We then use our chosen value for 0², to bound Vs.i. We then input all the bounds, bound the gradient using the excess loss with Lemma A.6, to get bound of the excess loss using the previous excess losses. Using Lemma A.7 we get the final bound on the excess loss. By inputting our chosen 17, that minimize this expression, we get our bound.
G* : Vz(xx), where x= = arg minzex f(x)), and S ==
D, moreover let G + 2LD, == + 20, := E
TE N.
Then upon invoking Algorithm with at = t,
8

---

Balancing Partiiipaattiiiitiioon and Efficiency via Noise Cancellation
Table 1. Privacy Level Comparison
Table 2. Participating Machines Comparison
Our Work
Noisy SGD
Other Work
Our Work
Noisy SGD
Other Work
p
Accuracy
Time
Accuracy Time
Accuracy
Time
Tra
Accuracy
Time
Accuracy Time
Accuracy
Time
4
53.8%
13 sec
45.1%
9 sec
47.6%
64 sec
20
60.8%
13 sec
54.9%
9 sec
59.7%
114 sec
8
63.7%
13 sec
58.9%
9 sec
63.3%
282 sec
50
63.7%
13 sec
58.9%
9 sec
63.3%
282 see
12
sec 66.5%
63.7%
9 sec
66.7%
730 see
80
63.8%
13 sec
57.0%
sec
65.8%
452 sec
Since Algorithm 1 uses total of .mT samples in the learning process, our rate translates to O Vn + M/M which matches the lower bound for the untrusted server case. Moreover, our approach performs two gradient com- putations per sample, and its computational complexity is therefore linear in n, which matches standard methods.
We can see that by increasing m., we increase the accuracy, except in Noisy SGD, where the higher value is worse than the middle one. That is because in Our Work and the Other Work, the less partial the participation is, the less we lose, but it doesn't 't matter for Noisy SGD. In Noisy SGD, m can be seen as the batch size, which is inverse to the number of time-steps, which was probably too small in this case. The change in accuracy is smaller than the one in Table 1, which implies that the privacy more important, can be seen in our bound in Theorem 5.2. The running time is unchanged in Our Work and Noisy SGD, since the total number of samples used is the same, but is increasing in the Other Work with m, since they make more iterations when m is larger. Comparing between the algorithms, the Other Work gets the best accuracy in the largest m. but does so with much longer running time. Our Work still has slightly longer running time than Noisy SGD with better accuracy.
(
5.3. Experiments
We ran Algorithm on MNIST using logistic regression. The parameters are G = V2. 785 39.6, L = 785/2- = 392.5, D- = 0.1, which brings us S = 118.1. Our model has d = 10 - 785 = 7850 parameters. We compared our al- gorithm (called "Our Work") to SGD with noise, inspired by (Abadi et al., 2016) (called "Noisy SGD"), and to the other work (Lowy& & Razaviyayn, 2023) (called "Other Work"). We kept the same parameter in all 3 algorithms to the best of our abilities, and in all tests the total data samples used across all machines is = 60, 000. Note that in Our Work and Noisy SGD, we only do a single-pass over the data, and each data sample is only used once, while in the Other Work the same samples are reused, as is done in their al- gorithm. This fact and the noise added as part of privacy are part of the reason why the accuracy is bellow 70% in all experiments. We compare both the test accuracy and running time.
In conclusion, like it was shown from the theoretical bounds, Our Work is as good as the Other Work in terms of accuracy, but with much faster running time, while getting only a slightly longer running time than Noisy SGD but with a better accuracy.
6. Conclusion
We enhanced DP-μ to operate in the partial- participation setting with an untrusted server by introducing an innovative noise cancellation technique that preserves privacy while minimizing overall noise. We demonstrated that this approach achieves optimal excess loss with linear computational complexity.
For our first experiment, we fix m = 50, M- = 100, and compare various values of p. We show our results in Table 1.
We can see that by increasing p. the accuracy of all algo- rithms increase. That makes sense, since the higher the privacy level, the less noise we need. The running time doesn't change in Our Work or Noisy SGD, because we make the same number of computations, just with different noise, but in the Other Work, they use more iterations with a higher privacy level, to get better results when allowed, so the running time drastically increases. Comparing between the algorithms, the Other Work needs large privacy level to truly shine, overtaking Our Work in the highest privacy level, but getting results closer to Noisy SGD in the lowest, albeit with much longer running time, with our algorithm being just slightly longer than Noisy SGD, with better accuracy.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning, and especially the aspect of Privacy. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
A Acknovledemment
This research was partially supported by Israel PBC- VATAT, by the Technion Artificial Intelligent Hub (Tech.AD) and by the Israel Science Foundation (grant No. 3109/24).
In a second experiment, we fix p = 8, M = 100, and com- pare various values of m. We show our results in Table 2.

---

Balancing
and Efficiency via Noise Cancellation
References
Duchi, J. C., Jordan, M. I,, and Wainwright, M. Local privacy and statistical minimax rates. In 54th Annual IEEE Symposium Foundations of Computer Science, FOCS. IEEE Computer Society, 2013.
Abadi, M., Chu, A., Goodfellow, I. J., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Weippl, E. R., Katzenbeisser, S., Kruegel, C., Myers, A. C., and Halevi, S. (eds.). Pro- ceedings of ACM SIGSAC Conference on Computer and Communications Security. ACM, 2016.
Dwork, C. and Roth, A. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 2014.
Avella-Medina, M., Bradshaw, C., and Loh, P. Differen- tially private inference via noisy optimization. CoRR, abs/2103. 1003, 2021.
Dwork, C.,, Kenthapadi, K., McSherry, F,, Mironov, I., and Naor, M. Our data, outselves: Privacy via distributed noise generation. In Vaudenay, S. (ed.), Advances in Cryptology EUROCRYPT, 25th Annual International Conference on the Theory and Applications of Crypto- graphic Techniques, Lecture Notes in Computer Science. Springer, 2006a.
Bassily, R., Smith, A. D., and Thakurta, A. Differentially private empirical risk minimization: Efficient algorithms and tight error bounds. In 55th IEEE Annual Sympo- sium on Foundations of Computer Science, FOCS. IEEE Computer Society, 2014.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. D. Calibrating noise to sensitivity private data analysis. In Halevi, and Rabin, T. (eds.), Theory of Cryptography, Third Theory of Cryptography Conference, TCC. Lecture Notes in Computer Science. Springer, 2006b.
Bassily, R., Feldman, V., Talwar, K., and Thakurta, A. G. Pri- vate stochastic convex optimization with optimal rates. In Wallach, H. M., Larochelle, H., Beygelzimer, A., Alché- Buc. F., Fox, E. B., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurlPS, 2019.
Feldman, V., Koren, T., and Talwar, K. Private stochastic convex optimization: optimal rates in linear time. In Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., and Chuzhoy, J. (eds.), Proccedings of the 52nd An- nual ACM SIGACT Symposium on Theory of Computing, STOC. ACM, 2020.
Bun, M. and Steinke, T. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Hirt, M. and Smith, A. D. (eds.), Theory of Cryptography 14th International Conference, TCC, Proceedings, Part I, Lecture Notes in Computer Science, 2016.
Ganesh, A., Haghifam, M., Steinke, T., and Thakurta, A. Faster differentially private convex optimization via second-order methods. CoRR, abs/2305. 0...00.....000 13209, 2023.
Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. Dif- ferentially private empirical risk minimization. J. Mach. Learn. Res., 2011.
Gao, C., Lowy, A., Zhou, X., and Wright, S. J. Private heterogeneous federated learning without a trusted server revisited: Epror-optimal and communication efficiien al- gorithms for convex losses. In Forty-first International Conference on Machine Learning, ICML, 2024.
Cheu, A., Joseph, M., Mao, J., and Peng, B. Shuffle private stochastic convex optimization. In The Tenth Interna- tional Conference on Learning Representations, ICLR, 2022.
Girgis, A. M., Data, D., Diggavi, S. N., Kairouz, P., and Suresh, A. T. Shuffled model of federated learning: Pri- vacy, accuracy and communication trade-offs. IEEE J.
Cutkosky, A. Anytime online-to-batch, optimism and accel- eration. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Ma- chine Learning, ICMI., Proceedings of Machine Learning Research. PMLR, 2019.
Sel. Areas Inf. Theory, 2021.
Hafeez, K., Rehmani, M. H., and O'Shea, D. DPNCT: A differential private noise cancellation scheme for load monitoring and billing for smart meters. In IEEE Interna- tional Conference on Communications Workshops, ICC Workshops. IEEE, 2021.
Cutkosky, A. and Orabona, F. Momentum-based vari- ance reduction in non-convex SGD. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d' Alché-Buc, F., Fox, E. B., and Garnett, R. (eds.). Advances in Neural Infor- mation Processing Systems 32: Annual Conference on Neural Information Processing Systems, NewrIPS, 2019.
Huang, Z.,, Hu, R., Guo, Y., Chan-Tin, E., and Gong, Y. DP-ADMM: admm-based distributed learning with dif- ferential privacy. IEEE Trans. Inf. Forensies Secur, 2020.
Iyengar, R., Near, J. P., Song, D., Thakkar, O., Thakurta, A., and Wang, L. Towards practical differentially private convex optimization. In IEEE Symposium on Security and Privacy, SP. IEFE, 2019.
Dekel, O., Gilad- Bachhachc R., Shamir, O., and Xiao, L. Optimal distributed online prediction using mini-batches. Mach. Learn Res., 2012.
10

---

Balancing Partial-Pardi Participaottiiiitiionn and Efficiency via Noise Cancellation
Kairouz, P., McMahan, B., Song, S., Thakkar, O., Thakurta, A., and Xu, Z. Practical and private (deep) learning without sampling shuffling. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, ICMI., Proceedings of Machine Learning Research. PMLR, 2021a.
Lowy, A., Ghafelebashi, A., and Razaviyayn, M. Private non-convex federated learning without a trusted server. In Ruiz, F. J. R., Dy, J. G., and van de Meent, J. (eds.), International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research. PMLR, 2023.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K. A., Charles, Z., Cor- mode, G., Cummings, R., D' Olivvee,,,, R. G. L., Eichner, H., Rouayheb, S. E., Evans, D., Gardner, J., Garrett, Z., Gascón, A., Ghazi, B., Gibbons, B., Gruteser, M., Har- chaoui, Z., He, C., He, L., Huo, Z., Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M., Konečný, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T., Liu, Y., Mittal, P., Mohri, M., Nock, R., Özgür, A., Pagh, R., Qi, H., Ramage, D., Raskar, R., Raykova, M., Song, D., Song. W., Stich, S. U., Sun, Z., Suresh, A. T., Tramer, F. Vepakomma, P., Wang, J., Xiong, L., Xu, Z., Yang. Q.. Yu, F. X., Yu, H., and Zhao, S. Advances and open prob- lems in federated learning. Found. Trends Mach. Learn., 2021b.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication--eficieenn learning of deep networks from decentralized data. Singh, A. and Zhu, X. J. (eds.), Proceedings of the 20th Interna- tional Conference on Artificial Intelligence and Statistics, AISTATS, Proceedings of Machine Learning Research. PMLR, 2017.
Mironov, I. Rényi differential privacy. In 30th IEEE Com- puter Security Foundations Symposium, CSF. IEEE Com- puter Society, 2017.
Noble, M., Bellet, A., and Dieuleveut, A. Differentially private federated learning on heterogencous data. In Camps-Valls, G., Ruiz, F. J. R., and Valera, I. (eds.), International Conference on Artificial Intelligence and Statistics, AISTATS, Proceedings of Machine Learning Research. PMLR, 2022.
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhod- nikova, S., and Smith, A. D. What can we learn privately?
SIAM J. Comput., 2011.
Rényi, A. On measures of entropy and information. In Proceedings of the fourth Berkeley symposium on math- ematical statistics and probability. The Regents of the University of California, 1961.
Kavis, A., Levy, K. Y., Bach, F. R., and Cevher, V. Unix- grad: A universal, adaptive algorithm with optimal guar- antees for constrained optimization. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d' Alchh-BBuc, F., Fox, E. B., and Garnett, R. (eds.), Advances in Neurul Infor- mation Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurlPS, 2019.
Reshef, R. and Levy, K. Y. Private and federated stochastic convex optimization: Efficient strategies for centralized systems. In Forty-first International Conference on Ma- chine Learning, ICML, 2024.
Kifer, D., Smith, A. D.. and Thakurta, A. Private convex optimization for empirical risk minimization with appli- cations to nigh-dimensional regression. In Mannor, S., Srebro, N., and Williamson, R. C. (eds.), COLT 2012 The 25th Annual Conference on Learning Theory, JMLR Proceedings. JMLR.org, 2012.
Shalev-Shwartz, S., Shamir, O., Srebro, N., and Sridharan, K. Stochastic convex optimization. In COLT - The 22nd Conference on Learning Theory, 2009.
Song, S., Chaudhuri, K., and Sarwate, A. D. Stochastic gra- dient descent with differentially private updates. In IEFE Global Conference on Signal and Information Processing, GlobalSIP. IEEE, 2013.
Koloskova, A., McKenna, R., Charles, Z., Rush, J. K., and McMahan, H. B. Gradient descent with linearly corre- lated noise: Theory and applications to differential pri- vacy. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurlPS, 2023.
Talwar, K., Thakurta, A., and Zhang, L. Nearly optimal private LASSO. In Cortes, C., Lawrence, N. D., Lee, D. D.,, Sugiyama, M., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 28: Annual Conference Neural Information Processing Systems, 2015.
Levy, K. Y. ssgd Stable stochastic optimization via double momentum mechanism. CoRR, abs/2304.04172, 2023.
Thakurta, A. and Smith, A. D. Differentially private fea- ture selection via stability arguments, and the robustness of the lasso. In Shalev-Shwartz, S. and Steinwart, I. (eds.), COLT- - The 26th Annual Conference on Learning Theory, JMLR Workshop and Conference Proceedings. M..R.org. 2013.
Lowy, A. and Razaviyayn, M. Private federated learning without a trusted server: Optimal algorithms for convex losses. In The Eleventh International Conference on Learning Representations, ICLR, 2023.
11

---

Balancing Partial-Parii Particiaaartiiiaaaiinn and Efficiency via Noise Cancellation
Ullman, J. R. Private multiplicative weights beyond linear queries. In Milo, T. and Calvanese, D. (eds.). Proceedings of the 34th ACM Symposium Principles of Database Systems, PODS. ACM, 2015.
van Erven, T. and Harremoës, Rényi divergence and kullback-leibler divergence. IEEE Trans. Inf. Theory, 2014.
Wang, D., Ye, M., and Xu, Differentially private empiri- cal risk minimization revisited: Faster and more general. 2018.
CoRR,
Wei, K., J., Jin, S., Quek, Q S., and Poor, V. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Trans. Inf. Forensics Secur., 2020.
J., Ding, M., Ma, C., Yang, H. H., Farokhi, F.,
Wu, X., Li, F, Kumar, A., Chaudhuri, K., Jha, S., and Naughton, J. F. Bolt-on differential privacy for scalable stochastic gradient descent-based analytics. In Salihoglu, S., Zhou, W. Chirkova, R., Yang. J., and Suciu, D. (eds.), Proceedings of the 2017 ACM International Conference Management of Data, SIGMOD Conference. ACM, 2017.
12

---

Balancing Partial-Participatie and Efficiency via Noise Cancellation
A. Additional Theorems and Lemmas
Here we provide additional theorems and lemmas that are used for our proofs. These were also used in (Reshef' Levy, 2024).
Theorem A.1 (CCutkosky, 2019)). Let f - lK be convex function. Also let for > 0} and {wr E K.). Let fare be the weighted average of {wr]+=> meaning: 2t = and 2 at, Wy. Then the following holds for all t 2 1, K:
1
-
ar (VS(I+), w0 - x))
Note that the above theorem holds generally for any sequences of iterates {weet with weighted averages (x+) )., and as a private case it holds for the sequences generated by Anytime-SGD. Concretely, the theorem implies that the excess loss of the weighted average Fa can be related the weighted regret Er=1 ar (Vf(r)), wy x).
Proof of Theorem A. Proof by induction.
Induction basis: t =
an (1(f(z)) S a1 (Vf(z1). - -2) 01 [ (Vf(z1), -x)
The inequality is from convexity of f, and the equality because 11 = W1.
Induction assumption: for some 2
@ra(f(x)) - f(x)) $ Σ ar (Vf(I)), w, - x)
Induction step: proof for 1:
aa (f()+)))))))))))))) - f(x)) ((t [(x)) - ((+ s(x))
ar - 1
- f(z))
Or W 2) + (V((m))) xz)) + 0441(24411 x:)
T=1 ar (Vf(x,), w. - z) + au+1 (Vf(z(41) We41 Σ ar (Vf(z,) w. x)
In the first equality rearranged the terms, and added and subtracted the same thing, then used the induction assumption, then used convexity of f on both pairs and added them together, and finally we used the update rule of x++1 01:4114411 01:21 + a4+1 W4+1, and added the last member of the sum to get our desired result.
Lemma A.2. Let } be a Martingale difference sequence w.r.l a Filtration (Fete. i.e. E [2 = 0, then:
Zr
E 1
Proof of Lemma A.2. Proof by induction. Induction basis: t = 1
E
Z,
=
Σ
B
13

---

Balancing
and Efficiency via Noise Cancellation
Induction assumption: for some 2 1:
E
Z
Σ E
11
Induction step: proof for 7 ++1 1:
E
Z
E
Σ Z
+ 2E
Σ 1==
Zr
Zo+1
Z
B
Σ B E
E 1r 11
T=1
The first equality is square rules, then we used the induction assumption and the fact that E 1Z,+1|11,.... Ze] = 0, and finally we added the last term into the sum.
Lemma A.3 (Mironov, 2017; Bun & Steinke, 2016)). If .......AA As are randomized algorithms satisfying P1-ZCDP, Px-zCDP, respectively, then their composition (AI(S).... ...) Ax()) is (0r +p..,.+t))=2CD Moreover, the i'th algorithm Ai, can be chosen on the busis of the oulputs of the previous algorithms , Ai-1-
Proof of Lemma A.3. Proof by induction.
Induction basis: k =
D. (S)) S api
Because Ai is PCDDC Induction assumption: for some l 2 1:
Da ((A(5)))II(4(0))) S Sa Σa
Induction step: proof for
)7))
IP )
Da (14(6))
log EAIAA(S))
P P((A(S))TT))
P PPAAN ("AAIHHHAIAAAHAPAPAAAAAAAA
log
E BAIA((S)
0
IP 14
1
log
BANA((S)
(A
1) (((((())))))))
TP (((A(S)))))
1
+ a a-1
log
BAIAA((S)
=Da (AR+1 (()))) MAAEL) Da (LA(()))
k+1
Sapk+1 + Σ = Σ P
The writing A, A.SS) means that the output of A; is distributed in the case that the dataset is S. The first equation is the definition of the Rényi divergence, next we use conditional probability rules, then we use the fact that the output of Ae+1 conditioned on the outputs of the previous algorithms is independent of the outputs of these previous algorithms, and let the product out of the log as a summery. We then notice that each the two members are divergences themselves, and finally, we invoke both the the fact that A4+1 is Pk+1-22DD and the induction assumption, and add them together to the same sum.
14

---

Balancing Partial-Participatie and Efficiency via Noise Cancellation
Lemma A.4 (Post Processing Lemma (van Erven & Harremoës, 2014)). Let X, Y be random variables and A be randomized or deterministic algorithm. Then for all 1:
Da (A(X)) & D. (X
Note that we get equality if is an invertible function.
Lemma A.S. Let > O, and K. C TRd be convex domain of bounded diameter D, also let {7: E 1==1 be a sequence of arbitrary vectors. Then for any starting point wi E RRd, and an update rule w II (w; ngt) vI the following holds Vx E K.:
D2
Σ (r. W++1
2)
w++1ll
2m
2n
Proof of Lemma A.5. The update rule u4+11 II (we n/q1) can be re-written convex optimization problem IC:
We++1 = 1x (we 170c) = arg min
|I00e 7/: - x1 =112]]
arg min aEK
(ūt, x wi) + 2n ||:0
w. 11
zEK
The first equality is our update definition, the second is by the definition of the projection operator, and then rewrite it in way that does not affect the minimum point.
Now, since w is the minimal point of the above convex problem, then from optimality conditions we obtain:
it + (we+1 - we), x w++11 2 0,
Vo KC
Re-arranging the above, we get that:
1 (we W++1, We+1 xx)
1
1
1
(ih, w++1 x²) < Where the equality is an algebraic manipulation. After summing over t get:
ww x=|2
|
- xe|2
||u, w4 w 11
1)
21
2n
21
(ār, w++1 - x) S 2m r=1
1|+ - z012 - -+12-11u7+1 x012 - -|| -0,+2|1 1x+2112)
[w x1| |10e+11 x01
D2
w|w, w1+1
w.
wy+1ll
2m
2m
2n
2n
7=1
Where the second line due to splitting the into sums, and using the fact that the first one is telescopic sum, and lastly, the diameter of K. This establishes the lemma.
Lemma A.6. f f K. R is convex and L-smooth, and x² arg min min(f(z)) (f(()) then Vo Rd:
DEK
( 2L(((x) f(xx))
Proof of Lemma A.6. Let us define a new function:
M(x) f(x) f(x²) (VV(((((())))))))))0 xx))
Since f is convex and L-smooth, we know that:
L 2
0 0 h(x))()))))))
| x11
The gradient of this function is:
Vh(x) Vf(x)
15

---

Balancing Particiapattiiiaaiionn and Efficiency via Noise Cancellation
We that h(=*) = 0, Vh(=*) 0, and that x² is the global minimum. The function h is also convex and L-smooth, since the gradient is the same as up constant translation. We will add the domain of h to include all R. while still being convex and L-smooth. Since h is convex then:
byy) 2 h(x²) + (V x²) = O, Vy E Rd
is true even for points outside of the original domain, meaning that x" remains the global minimum even after this. For smooth function, Vz, y R
h(y) s h(x)) (Vh(x).v 2) + L 1ly =1|
By picking y = x- Vh(x), we get:
1(x) - (x)))(()) 1 [Vh(2)]1
2L
Rearranging, we get:
|[b(2)]] 2L(((()) -h()) 2L h(x)
By using IC we get:
Since x² the minimum point of tthe::
(V)6)),-~')10) Vr EK
Thus we get that:
[Vf(x) vf(x")| & 2L(((x) f(x'))
Lemma A.7. Af S + ET A, B, [T), then A, S 2B, E [T].
Proof of Lemma A.7. Let's sum the inequalities:
T 1 A
E
2T Σ
A
+
Σ
TB
2
The inequality is from the assumption, and the equality is because we sum constant values. we rearrange this we get:
Σ Ar S 2TB
And then:
A <
Σ Ar +
B 2B
27
-=1
16

---

Balancing Partiil-aatiicipaatinn and Efficiency via Noise Cancellation
B. Proofs of Section 2
B.1. Proof Equations (4) to (7)
Both claims use the same principle:
E || - E8 [x]]] s |
And so:
[. V/ <VV[ S G² E (1) - - V((())) [V]] V/il:
s 1,2 1| -y1l
With the heterogeneity, V (z) is the empirical mean of fz)), so the same rule applies:
M
1
vs(2) < | C² [V)())
M
-V V(())) -EVA)) V S 1 |1 yyl?
(V/())
M
Thus 5 S G and or, & < L.
B.2. Proof of Lemma 2.1
The first part will be combination of the bounded variance and the bounded heterogeneity. At first, will assume that M is fixed:
E [g((x) vf
2)
m iEM
V(((x) Vf(x)
E
Vf((;;2)) -
m
m
iEM
iEM
Vf(()) V/(x)
( v\((a)1
m
m
iEM
iEM
Vf(()) V/(x)
m
m
iEM
iEM
Vf(z)- Vf(x)
m
m
FEM
At first the definition of g(x), then we use the fact that E 2 V (z()). Then we use the fact that the variance of a sum equal to the sum of the variances, and then use the bounded variance.
| + EXI and E [x; 2,)
Next we need to bound the first term:
M Ii vf(x))
m
iEM
M
M
lfe ( My Vf(x), Vz) vf(x))
-
m
2
Where we rewrote the sum using the indicator function, and then open the square into two sums. Now we will add an expectation on the randomness of M. Note that the only random variables here are the indicators. The properties of the
17

---

Balancing
and Efficiency via Noise Cancellation
indicators, given that M is chosen uniformly:
m
=
B BiifEe M E
= -
M
m(m-1]
i i
M -1)
(M +
m(m- - 1)
m
M (M -) 1[i= j}
m(m -
m(m - 1)
m(M m)
I [{
M
M(M 1)
M(M 1)
Where at the end, we wrote using an indicator, for the case they are equal. Returning to the bound, we get:
1
E
V((()) - (x(2)
m
EM
m(m - 1)
m(M m)
M(M - 1) (i (i= (VS((1)
-
((M - 1)
M M
M
m -
(Vfi()) - Vf)()) Vf(z))
M - m
[Vf((z) -((=))
mM
mM 1)
1=1
M m 1
M
- M M m 5 M - m
m(M - 1) M
Where first inputted the expectation of the indicators, then separated the into two, then we that the first sum multiplication of two independent sums, that are both equal to O, since f((x)= = + EM f((x), and finally we use the definition of ç. In total we got that:
E [1g - vf(x)) < 02
1 1(22 m
M m
M -
For the second part, we will use similar steps, but with the bounded smoothness variance:
E V/()
=
- (Vi()))))) VS(DI)) -V/(I)
m
Σ
-V/0))))))))))
m
iEM
E
Σ M
(Vf((=2)))))) vf(())) - (v):) - f(()))
Where we first used the definitions of g(v), and the variance rule, the same steps before. Also before, will bound the second term using the smoothness variance bound:
1 -V/()))) (V/())))
E
v(((T)))
m
iEM
E
- vf(()) [(((f((()))
( -
m
EM
of r y11
|
y/
m
iEM
The first term is the difficult one, so we will use indicators, as before. For simplicity of the writing, we will define A, (Vfi(z) {(()) (Vfily) - v(())
M
M M ΣΣ
1 ΣΦ
Σ
CIEE
The MYIEEEM
m²
m
iE
18

---

Balancing
and Efficiency via Noise Cancellation
And just before, will use expectation over Mt
1
M
M
m(m - 1)
m(M -
mm] m)
B
A
M(M- 1) +
M(M - 1) {i ] 51 (Ai, A₃}
iE
M M
M | |
m 1
M- - m
(A
m.M (M
mM(M 1)
M m
M m L
|
|| v
m(M - 1) M
M 1 m
Where we used the same steps, including the fact that
M i=1
A
0 and the definition of Ey. In total we got that:
- 1 oz - M- - m
E - - v(()i|
M - <2
||x- y1
B.3. Proof of Lemma 2.3
Let us calculate Da (PIIQ) by definition.
0-1 ()
1 log Ex~P
P(X)
(Exwp (ela (1X
f1 (1x- -12--11-1 -1 1111----1)) =113))
Da (PIIQ)
log
Q(x)
a a-
1
log
(Exxp]
E (IIA 12 P- -ii])
- log
@
||
(a (a-1)
20
20
20
The first equality is the definition of the Rényi divergence, the second we input the values P and Q, then we open the norm, and then we calculate the expectation using the moment generating function of Gaussian random vector [e(a,X)] = joo"lll and finally the log and the exponent cancel each other, and we fix things up.
B.4. Proof of Lemma 2.6
We will start with the first part. To do it, we will show another property of the Rényi divergence. Holder's inequality states that for any P, q 2 1 such that 1/p+ + 1/q = 1, we get [|fall < IIfll,, IIsll,- We will pick p = a, q = : q = Q² and the norm to be on an arbitrary event A, and then:
f P(x)dxx S UA ((P6)))
(Lole)da) ((2.(P100(A))) S (e QAA))
P(A) =
The equality is the definition of the probability of the event, the inequality is from Holder's, 's next cxpand the integral over everything to get the Rényi divergence, and finally we bound the Rényi divergence by We pick the event A to be A = O, and then:
P ((A(S) 0} s (CP(A(S) -
If (e'P (A(S)) -1) S then ((A()) = 0} s If If (A()) 0)) then (e'P (A(S') = 0})
8 - = (od( and then:
Ioe(!)
P ((A(S)) = 0, S c+ -- PPA(S') =0}
If we combine both cases, we showed that:
lon (AA(S)) =), -ott S P(A(S)) - +8+8
lox(H)
P (AA(S) о} S max
19

---

Balancing Particiapaatiiiiaiiinn and Efficiency via Noise Cancellation
Now for the second part. Since A is (a, ag² RDDP for every a > 1, then it is also 2 a-1
log(#)
-DP, for every
2
1,0 (0,1). We will pick the value that minimize this expression 1 ++
1 p VV 22log ($), and get that for every
8 E (0, 1), Ais
2 + 22 6
C. Proofs of Section 3
C.1. Proof of Equation (10)
We will start with Equation (9), 8 = ai-1 and qt = axd4.
aa,e = ar (Vf(z);)) (1 (c) Vf(x = (Vf(mz 2x) + 0v-1 (d--1 -d--1
v((x=-1;21)
at
=a,d + 1 V v((==11;=) qr-1 + orde 0t-1 Vf(zx-iiz) 9--1 1 8t
Where at first we use the definition of qt, then Equation (9), then input our choice of Be, open the brackets and finally reuse the definition of qt-1 and the definition of st.
D. Proofs of Section 4
D.1. Proof of Lemma 4.1
We will use a definitions of ge. qr, $t, St, S1,5, St,i5 Ye,3-
87,1
Σ
(8T3 + Yr. f V--1a))
m
m
iEM,
iEM,
S
(Yri - Y Y--1i)
iEM-
S.M,
M
M
Sy
(Y,,s Y,-1,) = at + Yu.
1=1
i=1 TSISTET
At first we used 0. = Et= 87, then 8, EiEM, 87,5, then 8T,; = 87,5 + Yo.i Y 1,i then we split the sums using the linearity of the summation. For the first sum used 8., EiEM. 8T,i and then gt E' 8r. For the second sum, switched the order of summation and introduced new notation T, {tli E M, to help reverse M, Finally, while it is not very clear, the sum over 7 is telescopic sum, due to the definition of Yr, as the last noise generated by machine i at time-step t, and the fact that we sum over T, and thus Er (Y, Y7-1,) = Ye.-
D.2. Proof of Lemma 4.2
Before we begin, we shall bound the difference between consecutive query points:
2, It-1 Fz 1.
CrWW
(w), xx)
01:11
01:-11
Where the first equality is due to a1aT7 = O' 11 + or Using the above enables to bound the following scaled difference:
a1-1 ( |w,, a1
a- 1/ xt-1ll
xzIl S 2D
Where we use that fact that 0; 1, which implies at-10; 201 as well as the bounded diameter assumption.
20

---

Balancing Participattiiiii and Efficiency via Noise Cancellation
First part:
||, = -llaght - 19-- & (ar - a1-1) ga,il + a 19. - 11-1
=(a: 04-1) | ( 2 )I + a1-1 ([V) 2,,) (
S(a= aa-1) + It æ1- G =
The first equality is from the definition of st,s, then we use the triangle incquality, then explicitly employ the definitions of gt.z. 9t.i. next we use Lipschitz and smoothness, and finally, we employ the bound on 2t It-1 and a = t. and the definition of S.
Second part: We will also define 9: Ei It and 1 Σiem Ir. so that 8 = ac9t at 19-119-11 The proof will follow similarly to the proof of Lemma 2.1. At first, we will fix M,
E ||
3,112=
=
E
Σ
($L, - 84)
(5e
8p)
+
($ 8e,1)
m iEML
iEM,
iEMe
This are the same steps the proof of Lemma 2.1. The second term is:
E
(tt
81,2)
E B|s,,,1 1 3,,11=
1
Σ
E Bllaaiger Dc,)) - a ( 1.)11
2
m
BEMM
iEMi
SEM..
(a: 1V El -1.ll + ai- B
Bllee, I
Dt.i)) - (0t-1.5 3i-1,))??)
m
iEM.
(0 20 D)
((a: - al-1)0 + a0-10L 11 - x1-111)
m
m
m
iEMi
Where used the fact the each St, St,i is independent with zero mean, used the definitions of st, St,i, then we use the 2
inequality: X + 211 < (VEIITT + \
which holds since:
x B | =
2E (X,Y) +
s < 2 | || 2 (VE]IXI² + VENIYP 2
And finally, we used Equations (4) and (5). the bounds from the first part, and the definition of + 20 The first term also follows similar steps the proof of Lemma 2.1:
M
M M.IM MM (.. - St, - 51)
1 m REMM
Σ
(oL.
5t)
=
M
Ife
m²
=
Taking the expectation over the randomization of M, that is in the indicators, and following the same steps of the proof of
21

---

Balancing Partial-Participaali and Efficiency via Noise Cancellation
Lemma 2.1, get:
1
M m
M
E
(3 32)
m(M 1) M ==1
iEMi
M
M
(00 - 9t) - ar gg - 1111)11
m(M - 1) M
2
M m
M
M
(a--0t-1)
(al 00-1)/ 1
[0r, - gell + ta-11
Σ t=1
[ - 9t) - -0r--11 1, Dr- -t- 1)11
m(M 1)
M
M
1=1
M
m(M - 1) ((or - - + at a1 L 1| - -1--1l)²
m (5 + D) M m E
M -
M 1
Where at first we used the steps of the proof of Lemma 2.1, then used the definitions of St,i, 8,, then used IE ||X + 2
V E|IXII + | with empirical mean instead of expectation, and finally used Equations (6) and (7), the bounds
from the first part, and the definitions of g 5 + D. In total, we got:
1
M m 22 M 1
E |1 8ell2
0² +
m
D.3. Proof of Equation (15)
We will start with the definition of E, and the update rule of q::
c = Qt C+get = q- + 8 - aggi = EL-1 + 04-19 + 8t -aggt = Et-1 + St St
Where at first we use the definition of E,, then Equation (10), then the definition of E;-1, and finally the definition of 5.-
D.4. Proof of Lemma 4.3
Notice that E is Martingale sequence with a difference sequence of St. It means that:
E ||e.1l2
Σ
E |s, 1,
8
M- m
22 t
M m 22
M 1
M
Where at first we used Lemma A.2, and then used Lemma 4.2.
E. Proofs of Section 5
E.1. Proof of Theorem 5.1
Let us look at a single machine Let S,, S be neighboring datasets of [T|] samples which differ on a single data point; i.c. as- sume there exists -" E T, such that S; := {2t 2tg and 2,, z!-..
Zy iss ....
(3) } and S := { is 2t ..,, ....., 7,
Notation: We will employ (S,), (S:) to denote the resulting values of these quantities when we invoke our algorithm with the dataset S,, we will similarly denote (S)), (S)).
Setup: At first let's bound the sensitivity of s,-,i meaning the difference between (S,) and 8,- , (S)) conditioned on the values of {æ, Vr The value of Φ441 is calculated using št,s and the other signals from the other machines, and the server sends 2441 to them afterwards. Thus, we may assume that prior to the computation of 8t,s, we are given (
22

---

Balancing Cartial-Participatii and Efficiency via Noise Cancellation
Note that given the query history 21,.... - and the dataset St. 8,- (S,) known (respectively 8 (S!) is known given the dataset S and the query history). Also note that St,i is calculated using only #t,#1-1: 2t,i, and thus for all * T" we get (S)) (S,), thus we only need the sensitivity of sr-, (but for all possible values of r"
Sensitivity: Since ||,,,, I S (Lemma 4.2), then (|s)=.((S)) S,- (S()) S [|s),,,(S)) + ||,,,, (SS)) S 2S.
Bounding the Divergence: Here we will bound the Rényi Divergence of the sequence (E,,) Note that 81,5 =
Si, + yt - 1, and that Vt E Ti we get that E.glKrEn 87,1 = ExSIRTET $t,i + ye,s. It means that:
(
Da ((8, =Da
Σ TSINTETT
(T,(()))
Σ
(,,(S))
BET:
IET.
Σ Da
Σ
(
E
3r,(S))
1E
SSMTTT
TSUKTET
ETSLRCEET sr,(S:) ETSHKOTTT ST, (S)
203
IET;
(s))((()) ST (S))l S 2a.5
Σ LE
207
1ET&122
Where at first we use the post-processing property (Lemma A.4), then to composition rule (Lemma A.3), then we use the result of the Gaussian mechanism (Lemma 2.3), then use the fact that (S,) = (S)) for all t * T", and finally we bound each difference by 2S and sum more terms. We got that our algorithm 2S² Eier. of -ZDPP, meaning is
2 -C-ZCDP P: = 25 EIET, o7
E.2. Proof of Theorem 5.2
Start by bounding the excess loss R,:
R1 =a [B] f(x*)) -
Σ
E lar (Vf(z;) wy - x²)|=
Σ
(g. E, Wy w - x*)
r=1
7=1
(1r, Wi - x²) + Σ
E (er + Yr, - -
r=1
(ār, Wr+1 - x²) )-- +
E (ār, Wi - w1) +
Σ
E (sr + +Y,,""
- -wr)
T=1
7=1
D2
W Wo+1 112 +
E (ūr, W. w++1) + Σ E (E- + Yr, -w-)
27 2n
1=1
D2
Σ
Or E V (xx) - vs(x)), w. wr+1)
|| Wr+ill 1|
29
2n1
E (a, V ff(z") wi wr+1) +
E (5r, x² wr+1)
E (Yr,,² w
(A)
(B)
(C)
The first inequality is the anytime theorem (Theorem A.1), then we use q. 9. + E, + Y,, split it into two sums, split the first sum using Wt+1, bound the first sum using Lemma A.5, and finally we add and subtract Vx(x*) and reuse the definition of d and add it to the other sums. We will now bound the bottom terms:
23

---

Balancing Partial-Participaa and Efficiency via Noise Cancellation
Bounding (A): This term be written follows:
(A) R (a, Vf(x)), -++1) ar a-- (R-1))B(S((T)))) (+) a, (V m+++)
aa a (VI(x*), w1+1) (a+ a. VV E [| w |I]
<D Vf(x')) ||
Σ ar a,-1) a. [V 04 DG
The first equality is rearrangement of the sum while defining Cp = 0, then we put the last term into the sum, and use Cauchy- Schwartz. Finally, we use the diameter bound and telescope the sum. Note that we use the definition G := || fz² Ill and that GH E (0, G.. Bounding (B): This term is bounded as follows:
(B)
E (Er, x¹ - wr+1)
E |||=||| 1|x - wr+1ll
T=1
T=1
82 E2 T
D DVO2 + E2
<D
E B
1|
S D
S
vm
The first inequality is function vz. then we use Lemma 4.3, and finally increase 7 to f.
and the second using the bounded diameter and Jensen's inequality w.r.t concave
Bounding (C): This term is bounded follows:
E BY,,, (Y,,, w++1)= 1 m
(C)
E (Yr,,,²' x" wy+1)
M
M
t
P
p(1 - (11-p)=-a -BE (y/s x= wr+1)
(1 (1-p)" p)- EE
(ys,s w. -w+11)
m
m
M
P
p)T Σ E (Wa,is Wy - wr++1)
m
"E (Uz,dr Wy Wr+1) p)"
(1-p)
1 m
E Weltr Wy -rr+1) p)
p) -
Vo.t
wr Wr+1
E B|w 1wm--w41l1
+
F
p)"
ys,i
m
At first we write Y, as shown in Lemma 4.1, then we know that Y7, is actually ys.i. where s is a geometric random variable that starts at downwards with probability p X Va,i is independent of everything up to the time step 8, so we replace x with w., divide w - W,+1 into a sum of differences, then rearrange the order of summation, and the sum in 7 is geometric sum bounded by 1. We put the sum of outside and use Cauchy-Schwartz Schwartz with 4n and r to split it into two sums. We will p-
m
24

---

Balancing
and Efficiency via Noise Cancellation
now bound the second sum:
M
E
p)
Vysi
Vssi
p)2
||
m
M
M
7
U/ Σ (1 p)
2((-5))
7
E 13,
m
m m²p(2 p) 1=1 8=1
rms
M
d log T)
n (1 + log T)
M
E
[N..ll
ΣΣ =1
(1 + p(s-11)) 1))
m²p -p) i= ==1
2
p²m p)
4. 1n p2m2p(22 p)
+ log T) ( 1122-
t(t 1 1) 2ddnd (1 + log T) p²mp² p)
25 25t (1 + log T) (pl + 1)
(pl + (2 (-))))
S
2
ppmpp
Each Us.i is independent of each other and with zero mean, so the variance of the sum is the sum variances, with the factors squared. We rearrange the summation order and the sum r is geometric sum that is bounded by p(2-p) and then we use the variance ys,i, which is proportional to the number of time steps of machine i played up to the time step 8, which we call Na... NN.: - 1 binomial random variables with s 1 trials with probability p. so we input the expectation of it, then we solve both remaining sums. We input M m and finally we cancel the two 2 - p and bound it from below by I.
In total, get:
a. E.E (VS(x,) Vf(x"), wy wr+1) 1 1|,, W++1ll 4nj
R1aR R. S Σ
r=1
D2 +
25² (1 log T) DGD + DV 62 + 526.5
DV
+
(pt +
21
Vm
ppmpa
DVO2 E2pl:
D²
25 ntd (1 + log T)
S1
o (EIV)(() V5xx")|
+
+ DG
+
(pl + 1)
2n
Vm
ppmpp
r=1
252n (1 + log T) + DG + D DV + 221
D2 S4mL 01 R2 + 2n
(++ p)
pmmp
Where at first we inputted what we got, used Sauchy-Schwarte and finally bounded a² S E| )l(=")|| < 2LR, (Lemma A.6). If we enforce 7) S ST. we can use Lemma A.7 to get:
20 and
D22 + BurDD" +
2D 2D 02 + E2T15
4 (1 log T)
T+ 1
RnT S
mm
pmmp
Then after dividing by anr and using ,
M < T, we get:
2D2
4DG
AD 02 +
1652,, 1652n (1 + +log T))
RT < T)T2
+
T
VmT
p²m²
Picking 77 = min
pDm
8T. g.
1
we get:
28T (MM(1+logg) T)
4D(G +LLD)
4D 0² + E
8DS
/DS-2Md 2Md
RT
T
VmT
pmT
F. Trusted Server
The algorithm for the trusted server case is almost the same as the one in (Reshef & Levy, 2024). The only difference is that we use m machines instead of M at each time-step, and that we let the server hold qt. instead of each machine holding its own Zt.i. Algorithm 2 depicts our approach.
25

---

Balancing Partial-Participatiion and Efficiency via Noise Cancellation
Algorithm 2 DP- for Trusted Server
Inputs: #iterations T, #machines in total M, #machines per step m, initial point Zo. learning rate > 0, im- = ( 2T,+}
portance weights {a+ > 0}, noise distributions PP: = (0, [ož)}, per-machine E [M] a dataset of samples
Initialize: set W1 = 2 = z0. and 4o
for 1...., do
Choose Mr M with |M,l = m
for every Machine i E Mr do
Actions of Machine i:
Retrieve 2,, from S,, compute Jt, V V 2,,), and I--1, = (i(
Update $t,i = 0. 11-19t-1,5
end for
Actions of Server:
Aggregate 8t m LieM. 81,1
Update Qi 91-1 81
Draw Y2 ~ N' (0, To?)
Update To = qi + Yr
Update w = [ww - m7())
Update T++1
attl
It +
act1 W141
01:+11
ama
end for Output: TT
F.. Privacy Guarantees
Here establish the privacy guarantees of Algorithm 1. Concretely, the following theorem shows how does the privacy of our algorithm depends on the variances of injected noise {ve,she.
Theorem F.1. Let K Rd be convex set of diameter D, and {Ji(G=))2eZ, be family of convex G-Lipschitz and L-smooth functions, and SD G 2LD. Then invoking Algorithm 2 with number of participating machines [M&l m.
noise distributions Y, ~ pt.; = N (0, Io?), and any learning rate >> 0, the resulting sequences {xtht & .CDP. where:
28
The proof is the same as the one in (Reshef & Levy, 2024).
Proof Sketch. First, assume that S, and S are neighboring datasets, meaning that there exists only single time-step T" E T, where they differ, i.e. that " # 2/,-..-
Then, we use the post-processing property of privacy (Lemma A.4) to say that the privacy of {æt), is bounded by the privacy of h. Using the composition rule (Lemma A.3), we bound the privacy of them with the sum of the privacy of each individual member. We may use Lemma 2.3 and obtain that q
A -CPP.. Using the bound ||sT,i S S, from Lemma 4.2, 2n
we show that A < 29 Thus, we are m²o?
25a -ZCPP Using the above together, we get that {2r), is 25² m² Σ
1 oz -CDD.
0
F.2. Convergence Guarantees
Here we establish the convergence guarantees of Algorithm 2.
Theorem F22 Let KC C Rd be convex set of diameter D and {.fa ()(:;)))) (i) be a family of G-Lipschitz and L-smooth functions over K,, with a E [0, G), 01, E [0, L). and lei M, be a subsel of [M] of size m, define G* = Vf(=*), where
x" = arg mingek f(x), and S = 2LD, = σ + 20,, D, = D. moreover let T E N. > 0.
Then, upon invoking Algorithm 2 with a; t, = min {
pm 1) }. and of
SS2T with No,5 being the number of p=
25T 4LT time steps that machine i participaated up to time step t, and any starting point xı K and datasets (8, E 2 Jie[M), then Algorithm 2 satisfies of -CDP w.n. the query point, i.e. {xt)--
26

---

Balancing Partial-Participar and Efficiency via Noise Cancellation
Furthermore, S consists of i..dd samples from distribution for all E [M], and M, are also chosen uniformly and Li.d then Algorithm 2 guarantees:
G* +LD
0² + 6
2
aek RT == ==][(((T) min f(x) S 4D
VmT
pmn
The proof is the same the one in (Reshef & Levy, 2024). Notably, the above bounds are optimal.
Proof Sketch. The privacy guarantees follow directly from Theorem 5.1, and our choice of of:
1
2
p²m
p²
Ø² 2
25
m² Σ
Σ
0f
4S2T 2T
Regrading convergence, in the spirit of SGD analysis (Levy, 2023; Reshef & Levy, 2024), we bound the excess loss using the anytime theorem (Theorem A.1), rewrite the expression to get to the form of Lemma A.5 and use bound, and separate the terms of E, and Y,. We already bounded E, in Lemma 4.3, though
bound M-m I and now the bound on Yt is easy, since the sequence {Yr). is i.i.d., so we can use the technique of the proof in (Reshef' & Levy, 2024). We then input all the bounds, bound the gradient using the excess loss with Lemma A.6, to get bound of the excess loss using the previous excess losses. Using Lemma A.7 we get the final bound on the excess loss. By inputting our chosen 17, that minimize this expression, we get our bound.
G. Analysis of Alternative Method
Here provide simplified analysis which demonstrates the suboptimality of the approach we present in Equation (12). We show that the delayed updated lead to an excessive error of the gradient estimates which translates to a degraded bound, even in the non private case.
We start by bounding the error of gradient estimate, Et. similarly to Lemma 4.3. At first, we will define Et, == gr, ar V f((e), and notice that:
1
Σ Eti + at
1 Σ
Vf(xz) -f((z))Vf(z)
Et
m NeM,
m iEMo
If we ignore heterogeneity for simplicity, we get:
E |ea11
Σ
E
m REM,
Now let us look at Et,i- Similarly to Equation (15), can write the update step of εt, as:
E,i Et-r.i a, (z Vf((z,))
a. a (V - (x,,,))))
We that f is martingale given the time-steps machine i participates T, Similarly Lemma 4.2:
E (V. 21) Vf((z.)) - at- (V - vf((x++))]
$ ((a, 00- + or- 12,, xz-r11)² 82,2
Since know that:
Q1-7 |z - F4-71 S at-r
a1-r+1d D
(t (t-7) -2 D D
aud
(++
Note that is geometric random variable with probability p Nevertheless, to simplify the analysis let us look at the "average case", where
M. m
1/T 2 2 2 82 LT
Mt 7 m
E 1 5 E ||
k=1
27

---

Balancing Partial-Participaal and Efficiency via Noise Cancellation
Thus, in total, we get:
ML
ML m2
E
|eall
B
E 2
0²
0²
m
m
iEMi
iEM:
It is M. times larger than what we get in Lemma 4.3. Plugging these bounds back into the bound for Rr, in a similar manner to what we do in the proof of Theorem 5.2 (see Appendix E.2) leads to the following additive term in the error bound,
2
T
4D 72
M 7T8
0² E2
4D
02
2
M
Σ
B |er 2 =
S
01:T
m
v
mm
m
This substantiates the degradation.
28


Reviews:
[{"review_id": "4qHsyIlQrY", "reviewer": "Reviewer_kvrv", "summary": "The paper addresses the challenge of ensuring Differential Privacy (DP) in Federated Learning (FL) under partial participation, where only a subset of devices engage in each training round. Existing approaches struggle to extend DP guarantees from full-participation settings to practical FL scenarios with inconsistent availability. The authors propose a novel noise-cancellation mechanism that preserves privacy without degrading convergence rates or computational efficiency. Their method, analyzed in the SCO framework, achieves optimal performance for both homogeneous and heterogeneous data distributions. The results provide a scalable and practical solution for privacy-preserving FL, particularly in large-scale environments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review and for your comments.\n\nWe address all of your comments and kindly ask you to update your score accordingly.\n\nRegarding your comments:\n\n---\n\n**Q: Comparison to [Gao et al. 2024]**  \n**A:** The work of [Gao et al. 2024] indeed provides guarantees for DP-FL learning.\n\n**Regarding guarantees:**\n\n- In the **Full-Participation** setting, [Gao et al. 2024] enjoy *optimal DP generalization* (i.e., population loss guarantees), while requiring a computational complexity which is super-linear in the size of the dataset, i.e., $O(|S|^{9/8})$, where we define $|S|$ to be the overall number of samples used (see Eq. (7) therein).  \n  Note that in the notation of [Gao et al. 2024], $|S| = nN$, where they use $N$ to denote the total number of machines, and $n$ to be the size of the data on each machine.\n\n- Comparably, **in this setting we achieve optimal DP generalization while requiring only linear computational complexity in** $|S|$.  \n  Note that in the notation of our paper, $|S| = n$, since we denote $n$ as the total number of datapoints used by all machines throughout the training process.\n\n- In the **Partial-Participation** setting, [Gao et al. 2024] obtain *sub-optimal* DP generalization guarantees.  \n  Concretely, the total data used in their work is still $|S| = nN$, where $N$ is the total number of machines and $n$ is the number of data points on each machine. This applies even when they are using $M \\leq N$ machines in every round (see Alg. 1 and Alg. 2 in their paper).\n\n  The bound they establish in Theorem C.1 (Eq. (17)) shows a convergence rate of:  \n  $$O\\left(\\frac{1}{\\sqrt{Mn}} + \\frac{\\sqrt{d}}{\\epsilon \\sqrt{M}n}\\right).$$  \n  Translating this into the size of the dataset $|S| = nN$ implies a bound of:  \n  $$O\\left(\\frac{\\sqrt{N/M}}{\\sqrt{|S|}} + \\frac{\\sqrt{d}N/\\sqrt{M}}{\\epsilon |S|}\\right),$$  \n  which is suboptimal.  \n  Moreover, their approach requires a computation which is superlinear in $|S|$.\n\n  Conversely, in the partial participation case **we obtain optimal guarantees** of:  \n  $$O\\left(\\frac{1}{\\sqrt{|S|}} + \\frac{\\sqrt{d}\\sqrt{M}}{|S|}\\right),$$  \n  and our computational complexity scales **linearly** with $|S|$.  \n  Note that in our notation $M$ is the total number of machines.\n\n  We shall add this comparison to the paper.\n\n\n---\n\n**Q: Stating overall lower bounds, w.r.t. Population loss**  \n**A:** Thank you for this suggestion, we will do so.\n\n---\n\n**Q: Relation of our noise-cancellation mechanism to [Koloskova et al. 2023]**  \n**A:** [Koloskova et al. 2023] discusses the idea of adding general correlated noise patterns during DP training. But they:\n- only discuss ERM problems  \n- suggest adding correlated noise to FTRL or SGD which use standard gradient estimates  \n- do not provide explicit guarantees, and do not discuss partial-participation\n\nConversely in our work we:\n- discuss and provide population-loss guarantees  \n- suggest adding noise-cancellation (and therefore correlated noise) to $\\mu^2$-SGD estimates, which is crucial to our guarantees  \n- provide explicit bounds for partial-participation\n\nWe shall add this discussion to our work.\n\n---\n**Q: Experiments.**  \n**A:** We performed experiments that illustrate the benefit of our approach and corroborate our theoretical findings. See below.\n\n**Experimental Results (MNIST, Logistic Regression)**  \nWe compare our method (“Our Work”) to Noisy SGD [DL DP] and [Lowy & Razaviyayn, 2023]. All use n=60,000 samples. In Our Work and Noisy SGD, each sample is used only once (single pass). The low accuracy (<70%) is due to privacy noise and single-pass training.\n\n**Privacy-Level Comparison** (fixed m=50, M=100):\n\n| ρ   | Our Work | Time | Noisy SGD | Time | [Lowy & Razaviyayn, 2023] | Time |\n|-----|----------|------|-----------|------|---------------------------|------|\n| 4   | 53.8%    | 13s  | 45.1%     | 9s   | 47.6%                     | 64s  |\n| 8   | 63.7%    | 13s  | 58.9%     | 9s   | 63.3%                     | 282s |\n| 12  | 66.5%    | 13s  | 63.7%     | 9s   | 66.7%                     | 730s |\n\n**Participation-Level Comparison** (fixed ρ=8, M=100):\n\n| m  | Our Work | Time | Noisy SGD | Time | [Lowy & Razaviyayn, 2023] | Time |\n|----|----------|------|-----------|------|---------------------------|------|\n| 20 | 60.8%    | 13s  | 54.9%     | 9s   | 59.7%                     | 114s |\n| 50 | 63.7%    | 13s  | 58.9%     | 9s   | 63.3%                     | 282s |\n| 80 | 63.8%    | 13s  | 57.0%     | 9s   | 65.8%                     | 452s |\n\n**Key Takeaways:**\n- For strong DP requirement (low $\\rho$) and partial-participation (low $m$) we consistently achieve better performance with runtimes  comparable to noisy-SGD. The runtime of [Lowy & Razaviyayn] is substantially higher! And in this regime they obtain substantially worse performance.\n\n-For weak DP requirement (high $\\rho$) and when  approaching full-participation (high $m$), the accuracy of [Lowy & Razaviyay] improves but the runtime is very high.", "claims_and_evidence": "I think the main theoretical claims are well-supported by the proofs.", "methods_and_evaluation_criteria": "Due to the theoretical nature of this paper, there are no experiments. The authors did compare their bounds with previous works.", "theoretical_claims": "I have mainly checked the privacy and convergences of Theorem 5.1 and Theorem 5.2, which appear to be correct to me.", "experimental_designs_or_analyses": "NA.", "relation_to_broader_scientific_literature": "FL with formal DP guarantees is important, and improving the computational complexity is also meaningful.", "essential_references_not_discussed": "I think the authors may consider discussing the improvement over the following paper [1], which seems to improve the computation complexity (as well as communication complexity) compared to (Lowy & Razaviyayn,2023)\n\n[1] Gao, C., Lowy, A., Zhou, X., & Wright, S. J. (2024). Private heterogeneous federated learning without a trusted server revisited: Error-optimal and communication-efficient algorithms for convex losses. arXiv preprint arXiv:2407.09690.", "other_strengths_and_weaknesses": "Strengths: \n+ A nice extension of the previous framework to handle the partial participation scenario, which somehow demonstrates the power of $\\mu^2$-SGD approach.\n+ The paper is also well-written and easy to follow\n\nWeaknesses:\n- Maybe, some experiments could be added, though I understand that this is mainly a theory paper.", "other_comments_or_suggestions": "It seems that the notation $|\\mathcal{S}|$ is not defined in the related work section, though it can be infered from the context.", "questions_for_authors": "I have two main comments. \n\n1. It seems that in the lower bound sections, the authors mainly use the results for empirical loss, while later upper bounds are for population loss. I understand one can do a quick reduction from the lower bound for the empirical one to the population one. It would be better to explicitly say it to avoid any confusion. \n\n2. Another comment is about the relationship between the noise cancelation in this paper and the one in the standard binary-tree mechanism (see [1]). This is mainly from my curiosity. Are they related or simply not related at all?\n\n[1] Koloskova, Anastasiia, et al. \"Gradient descent with linearly correlated noise: Theory and applications to differential privacy.\" Advances in Neural Information Processing Systems 36 (2023): 35761-35773.", "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": "puJD8vPPVd", "reviewer": "Reviewer_S51V", "summary": "This paper proposes a differentially private algorithm for federated learning when the untrusted server and with partial participation. The approach is an extension of the previous work of the paper \"Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systems\", Roie Reshef, Kfir Y. Levy ICML 2024 which requires full participation.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. \n\nWe address all of your concerns and kindly ask you to increase your score accordingly.\n\nRegarding your comment:\n\n---\n\n**Q: Novelty over full-participation paper [Reshef and Levy, 2024]**  \n**A:** We understand that our approach seems simple in hindsight. However,  \nlet us highlight that coming up with this idea and analyzing it was *not trivial at all*. \n\nConcretely,\n\n- In **Section 4.1** of our paper, we depict **two natural extensions** of [Reshef and Levy, 2024] that **completely fail to achieve optimal guarantees**!\n\n- Moreover, as you can see in our analysis appearing in **Appendices D and E**, the partial participation and correlated noise:\n\n     - substantially complicate the analysis  \n     - are substantially more challenging compared to the analysis of [Reshef and Levy, 2024]\n\n-  In pages 12–16 of the appendix we do have some overlap with [Reshef and Levy, 2024], but these appendices are provided **for completeness**.  \nActually, [Reshef and Levy, 2024] themselves also provide this for completeness, and this part is **not a novelty of their work**.  \nWe shall highlight this in the final version of the paper.\n\n- Moreover, our approach is:\n\n    - the **first to achieve optimal generalization guarantees** in the partial-participation setting  \n    - the **first to achieve linear computational complexity** in this setting\n\n- Finally, we believe that:\n\n    - a **simple algorithm is an advantage rather than a disadvantage**  \n    - while our approach is simple in hindsight, it was **very challenging to come up with this non-trivial algorithmic idea and analyze it**", "claims_and_evidence": "The claims are supported by the proofs", "methods_and_evaluation_criteria": "The approach is only theoretical, and proofs are included, so the methodology is correct", "theoretical_claims": "I was not able to check the soundness of the proofs.", "experimental_designs_or_analyses": "This is theoretical paper.", "relation_to_broader_scientific_literature": "It seems coherent.", "essential_references_not_discussed": "none", "other_strengths_and_weaknesses": "The main weakness of this paper is its significant similarity with the previous paper of ICML 2024. The extension to partial participation does not seem very challenging and it is not clear that this should deserve a full ICML paper. The overlap is a bit concerning. For instance, pages 12 to beginning of 16 are nearly identical in both papers, without clear mention of it. It would ease the reader understanding to clear present what is new and what is unherited from previous work.", "other_comments_or_suggestions": "none", "questions_for_authors": "Please comment on the novelty with respect to the ICML 2024.", "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": "ymqEq8ZwXA", "reviewer": "Reviewer_T3sK", "summary": "The paper addresses the challenge of applying DP in FL when only a subset of clients are active per iteration. \n\nIt mainly improves on a previous paper called 'Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systems', in which all settings are same but the clients are all active.  \n\nThe authors argue that the previous proposed full participation approach does not extent well to partial participation case.  The main challenge is that the partial participation case will accumulate noise in the global estimate.  \n\nTo overcome this, the authors propose a novel noise-cancellation mechanism. Specifically, they introduce a method where the added noise at each round is adjusted by subtracting the noise from the previous round (i.e., the noise is defined as Y^(t+1)-Y^(t) ) This approach prevents cumulative noise growth, which can otherwise degrade model accuracy and convergence.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. \n\nWe address all of your concerns and kindly ask you to increase your score accordingly.\n\n---\n\n**Q: Novelty over the full-participation paper [Reshef and Levy, 2024]**  \n**A:** We understand that our approach seems simple in hindsight. However,  \nlet us highlight that coming up with this idea and analyzing it was *not trivial at all*. \n\nConcretely:\n\n- In **Section 4.1** of our paper, we depict **two natural extensions** of [Reshef and Levy, 2024] that completely fail to achieve optimal guarantees.\n- As shown in our analysis in **Appendices D and E**, the incorporation of **partial participation** and **correlated noise**:\n     - substantially complicates the analysis\n     - introduces challenges far beyond those in [Reshef and Levy, 2024]\n\n- Moreover, our approach is:\n     - the **first to achieve optimal generalization guarantees** in the partial-participation setting  \n     - the **first to achieve linear computational complexity** in this setting\n\n- Finally, we believe that:\n\n     - a **simple algorithm is an advantage** rather than a disadvantage  \n     - while our approach is simple in hindsight, it was **very challenging to develop and analyze this non-trivial algorithmic idea**\n\n---\n\n**Q: Novelty over previous work with noise-cancellation, [DPNCT: A Differential Private Noise Cancellation Scheme for Load Monitoring and Billing for Smart Meters]**  \n**A:** Please note again that our work is the **first approach to achieve optimal guarantees for DP-FL with partial participation**.\n\nThe work you referenced indeed discusses noise cancellation in the context of privacy, and we will gladly cite it in the final version of the paper. However, that paper:\n\n  - does **not consider machine learning training!**\n  - does **not provide any guarantees!** — not even privacy guarantees!\n\nConversely, our work:\n\n  - discusses **machine learning**, specifically **DP training** in the **federated partial-participation** setting  \n  - provides **optimal guarantees** for:\n        - population risk\n        - computational complexity\n        - differential privacy\n  - proposes the use of **noise-cancellation in conjunction with the $\\mu^2$-SGD approach**, which is crucial to achieving our guarantees  \n  (using noise-cancellation with standard SGD estimates would **fail** to provide optimal guarantees)\n\n---\n\n**Q: Adding experiments**  \n**A:** We have now added experiments that demonstrate the applicability of our approach and corroborate our theoretical guarantees (Logistic regression over MNIST). Please see our response to Reviewer **kvrv**.", "claims_and_evidence": "The claim is supported by rigorous theoretical proofs", "methods_and_evaluation_criteria": "While it make sense to address the challenge of cumulative noise by introducing noise cancellation mechanism, it is not a novel technique proposed firstly in federated convex optimization, but has been applied in other applications such as 'DPNCT: A Differential Private Noise Cancellation Scheme for Load Monitoring and Billing for Smart Meters'", "theoretical_claims": "It appears correct with explicit assumptions like bounded heterogeneity and Smoothness etc", "experimental_designs_or_analyses": "No, there is no experimental validation", "relation_to_broader_scientific_literature": "In terms of the broader scientific literature, the main idea of noise cancellation in differential privacy (DP) is not entirely new. Similar concepts have been applied in other domains, such as in \"DPNCT: A Differential Private Noise Cancellation Scheme for Load Monitoring and Billing for Smart Meters.\"\n\nBeyond the prior work \"Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systems,\" the primary contribution of this paper lies in extending the analysis from full client participation to partial client participation. However, this incremental advancement offers limited novelty, particularly given that the core technique, noise cancellation, has already been explored in other applications.", "essential_references_not_discussed": "Noise cancellation in DP related literature are not discussed. E.g.,  'DPNCT: A Differential Private Noise Cancellation Scheme for Load Monitoring and Billing for Smart Meters'", "other_strengths_and_weaknesses": "No experimental validation is provided in the paper. As a result, it is difficult to assess how the proposed approach enhances privacy in practical settings or how it performs compared to existing methods. Without empirical evidence, the practical effectiveness and advantages of the method remain unclear.\n\nAdditionally, the paper offers limited novelty. The core idea of noise cancellation in differential privacy has been previously explored in other contexts, and the transition from full to partial client participation represents only an incremental extension of existing work.", "other_comments_or_suggestions": "I recommend conducting a more comprehensive review of the broader literature, particularly focusing on related work in FL and decentralized computation that addresses DP and noise design techniques. This would help contextualize the proposed approach within existing research and clarify its unique contributions.\n\nIn addition, it is important to provide experimental validation to demonstrate the effectiveness of the proposed method. Comparative evaluations against established approaches in FL or decentralized learning would offer valuable insights into its practical benefits", "questions_for_authors": "No", "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": "ApTzhCJbVX", "reviewer": "Reviewer_Aidn", "summary": "The paper proposes DP federated learning algorithms that allows partial participation based on the DP $\\mu^2$ SGD algorithms from (Reshef & Levy, 2024). The objective is to minimize the average of the population risks across all clients. The authors consider both cases of trusted and untrusted servers and achieve optimal convergence rate and linear computation efficiency. The case of trusted server is just a straightforward extension to (Reshef & Levy, 2024) where the queries are updated on the server side. Meanwhile, in the case of trusted server, the authors propose a technique of noise cancellation such that the injected noise at the server will be i.i.d and enjoy some concentration properties.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review and for your comments.\n\nWe address all of your concerns and kindly ask you to update your score accordingly.\n\n---\n**Q: Adding experiments**  \n**A:** We have now added experiments that demonstrate the applicability of our approach and corroborate our theoretical guarantees (Logistic regression over MNIST). Please see our response to Reviewer **kvrv**. \n\n---\n\n**Q: Novelty over the full-participation paper [Reshef and Levy, 2024]**  \n**A:** The **trusted server setting** is indeed quite simple — as explicitly mentioned in our paper.  \nBut this is **not the case** for the **untrusted-server setting**, which is our **main contribution**.\n\nWe understand that our approach seems simple in hindsight. However:\n\n- In **Section 4.1** of our paper, we depict **two natural extensions** of [Reshef and Levy, 2024] that completely **fail to achieve optimal guarantees**.\n- As shown in our analysis in **Appendices D and E**, the combination of **partial participation** and **correlated noise**:\n     - substantially complicates the analysis\n     - introduces challenges well beyond those in [Reshef and Levy, 2024]\n\n-Moreover, our approach is:\n    (i) the **first to achieve optimal generalization guarantees** in the partial-participation setting  \n    (ii) the **first to achieve linear computational complexity** in this setting\n\n-Finally, we believe that:\n    (i) a **simple algorithm is an advantage**, not a disadvantage  \n    (ii) while our approach is simple in hindsight, it was **very challenging to develop and analyze this non-trivial idea**\n\n---\n\n**Q: Other related works**  \n**A:** Let us re-emphasize the relation to previous works:\n\n- For the case **where machines trust each other**:\n     - The work of [Feldman et al. 2020] achieves **optimal guarantees** with **linear computational complexity**, but **only for the last iterate**.\n  - Their technique **does not extend** to the case where machines do not trust each other, since they **only maintain privacy of the last iterate**, while all intermediate iterates are **non-private**.\n     - Conversely, our approach works when machines **do not trust each other** (regardless of whether they trust the server), and still obtains optimal guarantees and complexity.\n\n- For the case **where machines do not trust each other**, beyond the work of [Lowy & Razaviyayn, 2023] that requires  $O(|S|^{3/2})$ complexity, there is a recent work of [Gao et al. 2024] brought to our attention by Reviewer *kvrv*. However: \n\n   - In the **full-participation** case, [Gao et al. 2024] achieves **optimal generalization** with a complexity of $O(|S|^{9/8})$, which improves over [Lowy & Razaviyayn, 2023], but is **still suboptimal** compared to our work.\n\n   - In the **partial-participation** case, [Gao et al. 2024] achieves **suboptimal guarantees** (see below), and still requires **superlinear computation** in $|S|$.\n\n   -Conversely, **we obtain optimal performance for the partial-participation case**, and enjoy **linear computational complexity** in $|S|$.\n\n**Elaborate Comparison to [Gao et al. 2024]**\n\nThe work of [Gao et al. 2024] indeed provides guarantees for DP-FL learning.\n\n**Regarding guarantees:**\n\n- In the **full-participation** setting:\n    - [Gao et al. 2024] achieves **optimal DP generalization** (i.e., population loss guarantees)\n   - However, their approach requires **super-linear computational complexity**, i.e., $O(|S|^{9/8})$, where $|S|$ is the total number of  samples used (see Eq. (7) in their paper)\n   - Note that in their notation:  \n    $|S| = nN$, where:\n       - $N$ = total number of machines  \n       - $n$ = number of samples per machine\n\n- **Comparably, in this setting** we:\n     - achieve **optimal DP generalization**\n     - require **only linear computational complexity** in $|S|$\n     - In our notation, $|S| = n$ denotes the **total number of datapoints used by all machines** during training\n\n- In the **partial-participation** setting:\n     - [Gao et al. 2024] still uses $|S| = nN$ (even when only $M \\leq N$ machines are used per round; see Alg. 1 and Alg. 2)\n     - Theorem C.1 (Eq. (17)) in their paper shows a convergence rate of:  \n    $$\n    O\\left(\\frac{1}{\\sqrt{Mn}} + \\frac{\\sqrt{d}}{\\epsilon \\sqrt{M}n}\\right)\n    $$\n    -Translating to total data $|S| = nN$, this becomes:\n    $$\n    O\\left(\\frac{N/M}{\\sqrt{|S|}} + \\frac{\\sqrt{d}N/\\sqrt{M}}{\\epsilon |S|}\\right)\n    $$\n    which is **suboptimal**\n  - Moreover, their approach still requires **superlinear computation** in $|S|$\n\n- **Conversely, in our partial-participation setting**, we:\n  - obtain **optimal guarantees** of:\n    $$\n    O\\left(\\frac{1}{\\sqrt{|S|}} + \\frac{\\sqrt{d}\\sqrt{M}}{|S|}\\right)\n    $$\n  - achieve **linear computational complexity** in $|S|$\n  - Note: in our notation, $M$ = total number of machines\n\nWe shall add this comparison to the paper.", "claims_and_evidence": "All the claims make sense to me and are supported by convincing proofs.", "methods_and_evaluation_criteria": "There are no empirical demonstrations in the paper. It will be greatly appreciated if the authors can include some experiments and comparisons to other DP FL methods.", "theoretical_claims": "I took a quick look at the proofs but didn't go through them thoroughly. The proofs look reasonable and seem correct to me.", "experimental_designs_or_analyses": "See my reviews in the section \"Methods And Evaluation Criteria\".", "relation_to_broader_scientific_literature": "The contributions of this paper, especially compared with prior works, are not clear to me. The contribution of the trusted server case is trivial given the extension from (Reshef & Levy, 2024)  is straightforward. \n\nFor the case of non-trusted server, the authors mention in the paper that (Lowy & Razaviyayn, 2023) achieves the same rate but with $|S|^{3/2}$ computations. However, given the problem of LDP SCO is a well studied area, I am wondering if there are any other related works (even in centralized setting) that achieves optimal rate and linear computational complexity. If so, how is this work compared with them?", "essential_references_not_discussed": "Please see my comments in section \"Relation To Broader Scientific Literature\"", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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:

Meta-review: The paper proposes a differentially private federated learning method for partial participation scenarios, extending prior work by Reshef and Levy (ICML 2024) on full participation. The novel noise-cancellation mechanism prevents cumulative noise growth, achieving optimal DP guarantees, linear computational complexity, and strong convergence rates. The initial submission was a little weak on experiments and lacked a more thorough discussion about related noise cancellation literature, but these have been addressed during the rebuttal. Still, multiple reviewers perceive the paper as incremental, and I agree that a more careful literature review should be included. The relationship with the ICML 2024 paper by Reshef and Levy must also be explicitly highlighted in the final version to avoid confusion.
Decision: Accept (poster)