Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation
Privacy and communication constraints are two major bottlenecks in federated learning (FL) and analytics (FA). We study the optimal accuracy of mean and frequency estimation (canonical models for FL and FA respectively) under joint communication and $(\varepsilon, δ)$-differential privacy (DP) constraints. We show that in order to achieve the optimal error under $(\varepsilon, δ)$-DP, it is sufficient for each client to send $Θ\left( n \min\left(\varepsilon, \varepsilon^2\right)\right)$ bits for FL and $Θ\left(\log\left( n\min\left(\varepsilon, \varepsilon^2\right) \right)\right)$ bits for FA to the server, where $n$ is the number of participating clients. Without compression, each client needs $O(d)$ bits and $\log d$ bits for the mean and frequency estimation problems respectively (where $d$ corresponds to the number of trainable parameters in FL or the domain size in FA), which means that we can get significant savings in the regime $ n \min\left(\varepsilon, \varepsilon^2\right) = o(d)$, which is often the relevant regime in practice. Our algorithms leverage compression for privacy amplification: when each client communicates only partial information about its sample, we show that privacy can be amplified by randomly selecting the part contributed by each client.
Paper
Similar papers
Peer review
Summary
This paper studies the distributed mean estimation problem with communication constraints and central DP. Communication constraints are met by subsampling a Kashin representation of the target vector, and \eps-DP is achieved by adding Gaussian noise. Privacy in the absence of a trusted server can be achieved using a LDP mechanism along with a secure shuffler. After discussions with the authors, I have increased my score.
Strengths
The work claims to be the first to study the communication-privacy-accuracy tradeoff for DME problem with central DP. It provides a simple scheme that achieves order-optimal error bounds.
Weaknesses
While this is the first work to study the problem, the solution was well-known. Unlike the LDP constraints, there is no tension between the communication cost and privacy in this case. Therefore, in my opinion, the novelty of this work is limited. The results are a straightforward amalgamation of well-known techniques that are independently known to be optimal.
Questions
The results are intuitively correct and are technically sound.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
3 good
Contribution
3 good
Limitations
Yes
Summary
This paper studied the optimal rates of the tradeoff among privacy (central DP), utility ($\ell_2$ estimation error), and communication cost (in bits) for the distributed mean and frequency estimation settings. The authors used Kashin's representation and Coordinate Subsampled Gaussian Mechanism to achieve the optimal rates. They also propose a many-round procedure with a shuffling mechanism to achieve the optimal rate if there is a secure shuffler instead of a secure central server. Simulation results are provided to supper the theoretical results of the distributed mean estimation setting.
Strengths
1. This paper provides the optimal rates for the distributed mean estimation given specific privacy and communication constraints, which is a fundamental problem in distributed learning (with a central server). 2. The authors proposed the Coordinate Subsampled Gaussian Mechanism and used it to realize the optimal rates. 3. The theoretical results are supported by the simulation results.
Weaknesses
1. In Theorem 5.3, the rate is $O(C^2 d \ldots)$ while in the appendix Lemma G.1 and Proposition G.2, the rates are $O(c^2 d)$. As Theorem 5.3 is also using Kashin's representation, I think it should be $c=O(\frac{C}{\sqrt{d}})$ as in Line 211. Therefore, there could be something incorrect in the result of Theorem 5.3. However, removing $d$ from the current result also seems to be strange to me. 2. The authors derived the theoretical results for the histogram estimation while not showing corresponding simulation results. They claimed these results in the abstract and introduction as contributions while only showing them in the appendix, which may not be very appropriate. 3. This paper uses the name 'federated learning' many times while the problem being solved is more restricted to the distributed learning (with a central server). Minor weaknesses: 1. Citation issues: [33] is cited as 'in submission' while it is already published in AISTATS 2023. [59] and [60] are duplicates. 2. Line 91. $10^6-10^9$ -> $10^6$ to $10^9$. 3. In Theorem 4.1, $\sigma$ should use $\Omega$ notation since we need it large enough to guarantee privacy. Similar misuses are in other results. This can be seen in the transition from $\sigma_1^2$ to $\sigma^2$ in Line 630 where the former used $\Omega$ while the latter used $O$. 4. Line 358. $\lceil \log d\rceil + 1)T$ should be $(\lceil \log d\rceil + 1)T$ 5. Line 361. The period is missing in the end of this line. 6. The citation of Theorem B.3 is missing. 7. Line 628. $e_2^\epsilon$ should be $e^{\epsilon_2}$. 8. Line 642. The second term in this equality is random which must be incorrect. Nevertheless, the final result is unaffected. --- I have read the rebuttal which addressed my questions and the weakness concerns.
Questions
1. Line 212. What does the dot product in $x_i = K \cdot \tilde x_i$ mean? Is it a matrix multiplied by a vector? 2. Are the notations of $(\alpha)$ and $(\beta)$ in Equation (4) in Line 217 misplaced? I think $(\alpha)$ is only the first part of Equation (4) and $(\beta)$ is the remaining two parts. Nevertheless, this seems not to affect the analysis in Section 4.1. 3. Line 354. For the statement of $d=5000$, is it from the previous claim based on the theoretical results '$b$ is independent of $d$'? Or is the result of $d=5000$ missing in this manuscript? 4. Line 622 in Section B. Should the sensitivity of $S_j(x^n)$ be $2c$? Should $Z_{i,j}$ be i.i.d. from $\mathrm{Bern}(\gamma)$ instead of $\mathrm{Bern}(1/\gamma)$? 5. Line 630. Should $\log(d/\delta)$ be $\log(d\gamma/\delta)$? Is $\gamma$ missing here (and elsewhere) intentionally?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
N.A.
Summary
The paper proposes a new randomization scheme for differentially private mean estimation. It is based on each user choosing randomly the coordinates to be sent in their messages. Similar scheme has been proposed in reference paper [55] (Hu et al., 2020), however Hu et al. do not sparsify the individual data-element-wise vectors, only mini-batch gradients. In the proposed scheme, data-element-wise vectors are sparsified randomly and the server averages these sparse vectors and adds normally distributed noise. A classical differential privacy analysis (meaning it uses some classical (eps,delta)-amplification results) is carried out resulting in optimal communication - privacy - accuracy tradeoffs (solving also an open problem in the untrusted server - setting) when these quantities are measured asymptotically. Algorithms both in trusted server setting and untrusted server (via multimessage shuffling) are given. The privacy analysis is essentially for the $\ell_\infty$-mean estimation, and the $\ell_2$-mean estimation bounds are obtained using the so called Kashin's representation which turns $\ell_2$-constraints into $\ell_\infty$-constraints in an optimal way.
Strengths
- solves an open problem and given optimal tradeoffs between privacy, accuracy and communication both in trusted and untrusted setting - Generally well written - extensive list of references and a comprehensive 'related works' section. I think the paper serves even as a good starting point for diving into this topic.
Weaknesses
- I think some parts are too densely written. The Kashin's representation is not introduced properly I think, those lines 208 to 214 give simply to little information. Like what is that tight frame $K$? I think there is some (still quite short) introduction in reference [34]. I think it would help a lot to have some more material on Kashin's representation, e.g. in the appendix. You use it repeatedly to get the $\ell_2$ mean estimation bounds anyways. - Related to the above comment, and for further improving writing: in lines 645-646 in the appendix you write "applying the same trick of Kashin's representation"... what are you referring to with 'the same' ? Here also would help expanding / elaborating a bit. - I think the paper is not entirely explicit about the difficulty of accurate privacy accounting in case of $\ell_2$-mean estimation (see the question comment below in the Questions - section) - It is not entirely clear how well the method fits to reducing communication in FL training of ML models if one would need to randomly sparsify individual gradients (see comment in the Questions - section)
Questions
- You mention that the privacy analysis could possibly be improved, and the log factors shaved off. Somehow I get the impression that you could elaborate on this more... Looking at the trusted server setting, I get the impression that the $\ell_\infty$-mean estimation algorithm one could perhaps analyse tightly (with RDP or directly with approximative DP). In a sense I think you do that in the experimental example. However, again with the $\ell_\infty$-constraints, how would you go about involving the Kashin's representations in the analysis? I get the impression that, e.g., in reference [34], the privacy bounds are simply big-O bounds as there are some universal constant involved when transforming between the constraints. Do you think it would be possible to analyse $\ell_2$-mean estimation algorithm using this coordinate subsampling tightly? - How would this fit to federated learning? I mean wouldn't the sparsity be lost quickly in case each device/user has model updates constructed using several data-elements? Wouldn't sparsification similar to the that of [55] be then required to reduce the communication? Minor comments: - Shouldn't "$\ell_2$ error" in Table 1 be actually "$\ell_2^2$ error ? - In bibliography, please use the Arxiv reference for the reference [33] instead of "in submission" - The reference paper [55] (which is quite central here) has been published in IJCAI, you only mention the Arxiv reference.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
3 good
Contribution
4 excellent
Limitations
Yes, I think the limitations with the analysis are adequately discussed in Section 7.
Summary
This paper studies the federated learning problem within the central differential privacy model, where a trusted central server gathers information from local clients. The primary focus is on minimizing communication costs while ensuring privacy and maintaining accuracy guarantees. To address this challenge, the paper introduces a novel privacy amplification framework. The framework operates by having each local client transmit only a random subsample of its full parameters to the central server, effectively reducing the communication overhead. Simultaneously, the randomness introduced in the subsampling process amplifies the privacy guarantee. Notably, in the specific case of distributed mean estimation, this framework significantly reduces the communication cost from an order of $O(d)$ to $\tilde O(n\min\\{\epsilon, \epsilon^2\\})$, showing a significant improvement over state-of-art result.
Strengths
This paper provides a novel privacy amplification method in central DP setting that optimizes the communication-privacy-accuracy three-way trade-off. Furthermore, the proposed distributed mean estimation also has significant implications. For example, upon setting $x_i$ to be local gradients, this algorithm immediately implies a private distributed SGD algorithm with reduced communication cost.
Weaknesses
The privacy amplification method is restricted to the central DP model and does not apply to LDP model.
Questions
N/A
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
4 excellent
Limitations
N/A
Reply
Thanks for your rebuttal. I still would like to ask about the last point. You replied: > Note that in the context of standard FL, it is not guaranteed that each local gradient or model update exhibits sparsity. As a result, additional sparsification procedures must be explicitly introduced to effectively mitigate communication costs. In the work of [55], this sparsification process involves the random selection of coordinates from a set of coordinates. Our scheme, the Coordinate Subsampled Gaussian Mechanism, on the other hand, can also be viewed as sparsification (as mentioned earlier). However, our primary contribution lies in demonstrating how this sparsification can be used to "amplify" central DP. In comparison to [Hu et al.], our scheme injects isotropic Gaussian noise after local sparsification and aggregation, which enables us to apply the amplification lemma via subsampling. My point was that wouldn't you need to sparsity every individual data-sample wise gradient if you want to have the privacy amplification from the random sparsification? If a user has several gradients, and sparsities, e.g., the sum, then you would not get the desired amplification for the central guarantee, and on the other hand, if you sparsity individual gradients and sum, you quickly loose the sparsity?
Reply to Reviewer's follow-up questions
Thank you for your prompt response and for providing additional clarification regarding your question. In the context of FL when each user has multiple data samples, the vector $x_i$ in our distributed mean estimation (DME) problem formulation can be taken as the mean local gradient computed at user $i$ (i.e., the average of sample-level gradients computed over $m$ samples at client $i$ for some arbitrary $m$). In other words, our Coordinate Subsampled Gaussian Mechanism and consequently the sampling-and-amplification lemma (Theorem 2) will be applied to the *average* gradient computed at each user and will achieve the order-optimal MSE. Note that the privacy amplification comes from the fact that we randomly sparsify the final vector $x_i$ each user aims to communicate to the server (i.e. a random subset of the coordinates of $x_i$ are communicated to the server). The fact that $x_i$ represents the *average* local gradient at each user does not change the privacy amplification. We believe the reviewer's question also relates to the the distinction between *user-level* DP (where two neighboring datasets differ in one *user*, which may hold $m$ samples/gradients) and *item-level* DP (where two neighboring datasets differ in one *sample*). Note that when applied to the average user-level gradient as described above our scheme leads to user-level DP, which is stronger than item-level DP. We provide a more mathematical argument below. Mathematically, under the multi-sample setting, each of the $n$ clients holds $m$ samples and each sample is associated with a (sample-level) gradient $g_{i, j}$, where $i \in [n]$ is the client index and $j \in [m]$ is the sample index. In each round of training, the server aims to estimate $\bar{g} = \frac{1}{nm}\sum_{i=1}^n\sum_{j=1}^m g_{i, j}$. Since we focus on *user-level* DP, the $L_2$ sensitivity of $\bar{g}$ is defined as $$ \max\_{(g\_{i,1},...,g\_{i,m}), (g'\_{i,1},...,g'\_{i,m})} \left\Vert \frac{1}{nm}\sum_{j=1}^m g_{i, j} - \frac{1}{nm}\sum_{j=1}^m g'_{i, j} \right\Vert_2 = \frac{2C}{n}, $$ where we assume each local gradient is clipped to $C$ ahead of time (note that the $\ell_2$ clipping is not needed if the loss function is $C$-Lipschitz). If there is no communication constraint, one can apply the standard Gaussian mechanism and achieve a MSE $\mathbb{E}\left[ \left\Vert\bar{g} - \bar{g}_{\text{gauss}} \right\Vert^2_2 \right] = O\left(\frac{C^2d}{n^2\varepsilon^2}\right)$. On the other hand, to further reduce communication cost, one can also apply our coordinate-sampling algorithm CGSM (Algorithm 2 in our paper) or the shuffled-SQKR scheme (Algorithm 4) to user-level gradients $g\_i := \frac{1}{m}\sum\_{j=1}^m g\_{i, j}$, yielding an $\tilde{O}\left(\frac{C^2d}{n^2\varepsilon^2}\right)$ MSE as well as $\tilde{O}(n\varepsilon^2)$ bits of communication. This means that only user-level subsampling is necessary, and as mentioned by the reviewer, item-level sampling does not help as it does not necessarily sparsify the user-level gradient. We note that [55] considers item-level DP (see the derivation of Theorem 1 therein) as opposed to user-level DP as described above. Although their framework could be adapted to user-level DP, such a modification will still fail to leverage the randomness introduced during the sampling step, thus lead to suboptimal communication costs. As a side note, while our current discussion assumes full client participation in every training round with all local samples, our analysis extends to scenarios where clients are initially sampled by the server or where each client computes their local updates on a local mini-batch. By applying standard privacy amplification by subsampling [Balle et al. 2018], one can obtain an optimal privacy-accuracy trade-off. Finally, we thank the reviewer for bringing this up and we plan to briefly mention the application to FL with multiple-samples per user in the revision as discussed above. We look forward to further discussions and input. [Balle et al. 2018] Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences
Thank you, the fact that all results are stated for user-level privacy definitely clarifies things! It's all clear now in that respect. > Regarding the $\ell_2$ mean estimation in practice, we opted not to use Kashin's representation and instead perform random rotation with $\ell_\infty$ clipping. Although the $\ell_\infty$ clipping step introduces a small amount of bias, we believe it offers a better privacy-MSE trade-off in practice. One may be able to directly analyze the privacy of $\ell_2$ mean estimation with coordinate-sampling (without the Kashin's representation step), but currently it remains unclear. This is my point. Similarly to the Poisson binomial mechanism, it seems to me that it is unclear how to accurately do the privacy accounting for $\ell_2$ mean estimation. Just like in the Poisson binomial mechanism paper, here the experimental example where RDP is used is such that the $\ell_2$-sensitivity is constant. I would imagine that the Skellam mechanism or the discrete Gaussian mechanism would be competitive (when not considering communication constraints). Although the Kashin representation might be discussed in the literature, the paper should be a coherent presentation, so please add the required definitions and hopefully some material about the Kashin representation. Also adding something about the random rotation + $\ell_\infty$ clipping would be good too.
Reply to the official comment
We thank the reviewer for further suggestions. We will compare with Skellam/discrete Gaussian mechanisms as baselines in the experiment, and will also include materials about Kashin's representation and a discussion regarding the empirical random rotation with an $\ell_\infty$ clipping scheme.
devil's advocate, not an adversary
Thanks for the clean perspective. "Similarly for central DP, one may a priori expect that compression will increase the sensitivity of the mean and therefore require the addition of larger noise at the central server, and hence lower accuracy, for the same privatization level." However, without any local privacy constraints, using Chen et al. (essentially the same random compression as in this work), the optimal accuracy is dictated only by the communication constraint. Now at the central server, adding Gaussian noise to the mean of the compressed data is known to be optimal. Therefore, I was questioning the novelty in terms of the techniques and how they deviate from the straightforward application of Chen et al. and folklore Gaussian mechanism.
Response the follow-up comment
We thank the reviewer for offering additional details regarding the question. We would like to clarify that the straightforward application of the compression in [Chen et al] with the Gaussian mechanism is *strictly sub-optimal*, since the compressed (and properly decompressed) mean has a much higher sensitivity. Consequently, the direct implementation of the standard Gaussian mechanism inherently gives rise to a larger amount of MSE. The main contribution of this paper is to show that in order to achieve optimal privacy-utility trade-off when the local data is compressed, one has to take into account the randomness in the local compression and carefully leverage it to reduce the amount of DP noise.
Thanks for the clarification. I will increase my score. I was under the impression that Kashin embedding with randomized rounding followed by coordinate subsampling is exactly what is done by Chen et al. also. Here is an alternate approach (which I initially understood as your result): Without any LDP constraints, Chen et al. should give you optimal communication vs accuracy tradeoff for mean estimation. And you can further achieve central DP by adding Gaussian noise to the achieved optimal mean estimate. Where does this approach fail or differ from yours?
Response the follow-up question
Thanks for the follow-up questions. The procedure outlined is indeed aligned with our CGSM algorithm, but the key question in this procedure is *”how much Gaussian noise do we need to add to ensure $\varepsilon$-DP?* If one were to calibrate the noise scale (i.e., variance) based on the sensitivity of the compressed mean, an additional factor of $\Omega(d/b)$ emerges in comparison to the sensitivity derived from raw, uncompressed samples. This consequently introduces an extra $\Omega(d/b)$ term into the MSE, where $b$ is the compressed dimension (or communication budget), and $d$ is the original dimension. Our work shows that one can get rid of this $\Omega(d/b)$ factor while still achieving the same level of DP (even though the sensitivity is higher!) by leveraging the randomness introduced during the compression/sampling step . Note that the standard Gaussian mechanism with the noise calibrated to the sensitivity (of the compressed sample) would fail to achieve the optimal privacy-accuracy trade-off. The key idea that our paper brings is that the randomness in the local compression can be leveraged for privacy amplification in central DP (and hence the title of the paper). Lastly, as a side note, our compression scheme coincides with SQKR from [Chen et. al] only when the communication budget $b$ is large enough $b = \Omega(\sqrt{d})$. For scenarios where communication budgets are more limited ($b = O(\sqrt{d})$), a more sophisticated sampling strategy, a more sophisticated sampling strategy is needed (i.e., the coordinate pre-selection scheme presented in Algorithm 2).
Thank you for the clarification.
Thank you for the response!
The authors have addressed most of my questions. In the two papers [Mcmahan et al. 2016, Kairouz et al. 2019] provided, the definition of federated learning includes several key properties: Non-IID, Unbalanced, Massively distributed, and Limited communication; They also said, 'An unbalanced and non-IID (identically and independently distributed) data partitioning across a massive number of unreliable devices with limited communication bandwidth was introduced as the defining set of challenges.' Therefore, I still think this paper only provides insights on Distributed Mean Estimation or in general distributed learning, but not more general federated learning (missing the discussion of unbalanced and non-IID settings). I have raised my score from 5 to 6.
Thank you for increasing the score!
We thank the reviewer for valuable suggestions and for increasing the score. We agree with the reviewer on the multifaceted nature of FL and that our work centers specifically on its privacy and communication aspects. We also agree with the reviewer's suggestion that exploring more practical scenarios, such as unbalanced data or personalization, is crucial to enhancing the general understanding of FL's real-world implications. We however would like to briefly clarify that our work does not assume local data to be generated i.i.d. Our goal is to estimate empirical means (a canonical formulation ofFedAvg or FedSGD), which does not involve any distributional assumption on local data/gradients. Once again, we express our gratitude to the reviewer for their valuable feedback and constructive suggestions.
Thank you for the response!
I do not have further questions.
clarification about the result
To authors and reviewers: From a quick look at the results it seems that the results immediately follow from simple and well-known facts. First: optimal $\ell_2$ error for $\ell_2$ mean estimation with $(\epsilon,\delta)$-differential privacy in the central and shuffle models is $\frac{\sqrt{d}}/{\epsilon n}$ (ignoring the log factor). This lower bound on the final error implies that one does not really need all the information about the input vectors and can instead replace inputs with outputs of an unbiased estimator. This has been previously used explicitly and implicitly in many private compression protocols. Specifically, if every input vector is replaced with an output of an unbiased estimator with mean squared error $\alpha^2$ this will add $\alpha/\sqrt{n}$ to the error of the sum. This means that any unbiased estimator with mean squared error of at most $frac{d}{\epsilon^2 n}$ would not change the final error asymptotically. Now there are several known ways to compress the $d$-dimensional input to $\epsilon^2 n$ bits that have mean squared error of $frac{d}{\epsilon^2 n}$. One can use the one from Chen et al (Thm 2.1) as part of the SQKR algorithm or random projection with subsamling from this work: https://proceedings.mlr.press/v162/vargaftik22a/vargaftik22a.pdf This paper uses a variation on these techniques. The same insight applies to histogram estimation, except the results in this work are already implied via shuffling/aggregation of LDP protocols for the entire range of \epsilon. Would be great to hear from the authors if they believe that this point captures the essence of their contribution and from reviewers on whether that affects their view of this work. Beyond theory I'm also not convinced by practical significance of the results. As far as I understand, the setting where $d \gg \epsilon^2 n$ seems atypical. I don't recall seeing it in empirical papers and I imagine that for most problems the resulting error is too large to get practically meaningful estimates.
Response to AC's comment
We sincerely appreciate the AC for handling and reading our paper and raising the questions. We clarify their concerns below. We believe the approach outlined by the AC can be summarized as follows: clients first compress individual local vectors $x_i$ into $n\varepsilon^2$ bits, thereby creating a locally unbiased estimator with a Mean Squared Error (MSE) of $\alpha^2 = d/n\varepsilon^2$, and subsequently, the server aggregates these locally compressed vectors. Since the compression error has the same order as the MSE under an $(\varepsilon, \delta)$-DP constraint, the final MSE will not be affected order-wise. The critical question here is whether the estimate produced by this scheme is still $(\varepsilon, \delta)$-DP. The local compression has increased the sensitivity of the mean by a factor of $d/b$, where $b$ is the communication budget (intuitively, there is less averaging now because each node is communicating less information), and hence the DP noise must increase accordingly to achieve the same $\varepsilon$. If we increase the DP noise accordingly, this leads to an additional $d/b$ in the final MSE for the scheme described by the AC. It is unclear how one can privatize the locally compressed vector without increasing the sensitivity, and hence the MSE compared to the uncompressed case. Indeed, we show that this is *impossible* without carefully leveraging the randomness used in local compression. Our main result shows that by carefully accounting for the randomness in the local compression, one can significantly reduce the amount of noise needed, *despite the larger sensitivity of the mean to the local vectors*. Note that this result cannot be obtained from the simple and well-known facts described by the AC, and we showed that obtaining the optimal privacy-communication-accuracy trade-off requires a non-trivial analysis, which is the main contribution of our work. We would also like to point the AC to Reviewer mo9D's follow-up question (who seems to have initially held the same concern as the AC) ( https://openreview.net/forum?id=izNfcaHJk0¬eId=9ar2F1pJtk ) and our response therein ( https://openreview.net/forum?id=izNfcaHJk0¬eId=Y2raU5pGJK ). We hope these discussions clarify our main contributions. Finally, $d \gg \varepsilon^2 n$ is indeed a practical (and possibly the most relevant) regime in cross-device FL settings. We would like to clarify that since the mean estimation task is invoked in each round of model updating, $n$ here refers to the number of participating clients *per round* (which is typically a small subset of available clients). Similarly, $\varepsilon$ here is the *per-round* privacy budget, which is of the order of $\varepsilon_{final}/\sqrt{T}$ (due to the composition theorem) where $T$ is the total number of training rounds. In practice, the model size $d$ can be on the order of $10^6$ to $10^9$, and the number of per-round clients $n$ ranges from $10^2$ to $10^5$. In addition, if we target a moderate final $\varepsilon$, say $\varepsilon_{final} = 20$, with total training round $T \geq1000$, then the per-round privacy budget $\varepsilon \leq 1$. As a result, $d \ll n\varepsilon^2$ is indeed very relevant and covers most of the cross-device FL regimes.
Thank you for your response. I see that indeed this simpler approach would not work (the sensitivity grows by $\sqrt{d/b}$ not $d/b$ as far as I can tell though). I now appreciate the importance a more subtle algorithm and more interesting analysis that is needed in this case. Thank you for the clarification and sorry about the misunderstanding.
Thank you!
We are pleased to have addressed the AC’s concerns and questions, and we will make sure to reiterate our main contributions in the upcoming version of the paper. The AC is correct that the l2 sensitivity increases by $\sqrt{\frac{d}{b}}$ instead of $\frac{d}{b}$. We thank AC again for their time and efforts in handling and assessing our paper.
Decision
Accept (poster)