Fast Optimal Locally Private Mean Estimation via Random Projections
Authors: Hilal Asi
Vitaly Feldman
Jelani Nelson
Huy Nguyen
Kunal Talwar
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential Privacy
mean estimation
private federated learning
communication complexity

Abstract: We study the problem of locally private mean estimation of high-dimensional vectors in the Euclidean ball. Existing algorithms for this problem either incur sub-optimal error or have high communication and/or run-time complexity. We propose a new algorithmic framework, namely ProjUnit, for private mean estimation that yields algorithms that are computationally efficient, have low communication complexity, and incur optimal error up to a $1+o(1)$-factor. Our framework is deceptively simple: each randomizer projects its input to a random low-dimensional subspace and then runs an optimal algorithm such a PrivUnitG in the lower dimensional space. We analyze the error of the algorithm in terms of properties of the random projection ensemble, and study two instantiations. We conduct several experiments for private mean estimation and private federated learning which demonstrate that our algorithms obtain nearly the same utility as optimal algorithms while having significantly lower communication and computational cost.

Fast Optimal Locally Private Mean Estimation via Random Projections
Hilal Asi Apple Inc.
Vitaly Feldman
Jelani Nelson UC Berkeley
Apple Inc. vitaly. sasalyyedu@gmai.coo com
hilal. asi949gmai1.ccmmm
minilee@bbekeele.yco edu
Huy L. Nguyen
Kunal Talwar
Northeastem University
Apple Inc.
hu ww..ngyynnenorthhasteee...cc
kunal@kunaltalwarr org
Abstract
We study the problem of locally private mean estimation of high-dimensional vectors in the Euclidean ball. Existing algorithms for this problem either incur sub- optimal error have high communication and/or run-time complexity. We propose a new algorithmic framework, ProjUnit, for private mean estimation that yields algorithms that are computationally efficient, have low communication complexity, and incur optimal error up to a + o(1)-factor. Our framework is deceptively simple: each randomizer projects its input to random low-dimensional subspace, normalizes the result, and then runs optimal algorithm such as PrivUnitG in the swwer-dimensionll space. addition, we show that, by appropriately correlating the random projection matrices across devices, we can achieve fast server run- run-time. We mathematically analyze error of the algorithm terms of properties of the random projections, and study two instantiations. Lastly, our experiments for private mean estimation and private federated learning demonstrate that our algorithms empirically obtain nearly the same utility optimal ones while having significantly lower communication and computational cost.
Introduction
Distributed estimation of the mean, or equivalently the sum, of vectors v1...., By Rd fundamental problem in distributed optimization and federated learning. For example, in the latter, each devices may compute some update parameters of machine learning model based on its local data, at which point central server wishes to apply all updates to the model, i.c. add Σ U; to the vector of parameters. The typical desire keep local data private necessitates methods for computing this sum while preserving privacy of the local data on each individual device, so that the central server essentially only learns the noisy sum and (almost) nothing about each individual summand v; 20 IT]
The gold standard for measuring privacy preservation via the language of differential privacy In this work, we study this problem in the setting of local differential privacy (LDP), We consider (one- round) protocols for which there exists some randomized algorithm R I M (called the local randomizer), such that each device i sends R(v;) to the server. We say the protocol is E e-differentially private if for any v, u' E Rdd and any event S S M. Pr(R(u) E S) s e Pr(R(v') E 5). If = then the distribution of (Tv) is independent of v, and hence the output of R(-) reveals nothing about the local data (perfect privacy); meanwhile if oe then the distributions of R(v) and R(v') can be arbitrarily far, so that in fact one may simply R(x)
and reveal local data in the clear (total lack of privacy). Thus, E 2 0 is typically called the privacy loss of protocol.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

There has been much previous work on private protocols for estimating the mean p== Σi= 2 in the LDP setting, Henceforth we assume each v, lives on the unit Euclidean sphere |--1 C IR Let be the estimate computed by the central server based on the randomized messages R(vi),.... R(w,) it receives. Duchi and Rogers [88 showed that the asymptotically optimal expected mean squared error IE 1| 2l12 achievable by any one-round protocol must be least S2( mimtee..))) ) which is in
fact achieved by several protocols [9 9 24 These protocols however achieved empirically
different errors, with some having noticeably better constant factors than others.
Recent work of Asi al. (7] sought understand the optimal enror achievable by any protocol. Let R be any local randomizer satisfying e-DP, and A be an aggregation algorithm for the central server such that it computes its mean estimate as ja == A(R(u)) ), ,...., ,R(v)) Furthermore, suppose that the protocol is unbiased, so that Ej = 1 for any inputs V1,-.... "m Lastly, let ApaMUnit RrivUnit denote the PrivUnits protocol of (parameterized to satisfy R Let Err,,a R) denote
[A(((()),..... ((v,)))),,,,,()))) - m1/2
sup
Uaa E
Asi et al. proved the remarkable theorem that for any n, d:
(A, R) 2 (Apiuu(A RetivUoit.).
Thus, PrivUnit is not only asymptotically optimal, but in fact actually optimal in a very strong sense (at least, amongst unbiased protocols).
While this work thus characterizes the optimal error achievable for s-LDP mean estimation, there are other desiderata that are important in practice. The most important amongst them are the device run- time (the time to compute R(v)), the server runtime (the time to compute A on (R(v)).... R ((r)))), ), and the communication cost (flog [M]] bits for each device to send its R(v) to the server). The known error-optimal algorithms (PrivUni [9] and PrivUnitG (77) either require communicating d floats or have a slower device runtime of (e As mean estimation often used subroutine in nigh-dimensional learning settings, this communication cost can be prohibitive and this has led to a large body of work on reducing communication cost these optimal algorithms are also slow, scaling as nd, whereas one could hope for nearly linear time Ö(n + d) (see Table 1p.
24 Server runtimes of
Chen et al. [14 recently studied this tradeoff and proposed algorithm called SQKR, which has an optimal communication cost of bits and device runtime only Od d). However, this algorithm incurs error that is suboptimal by a constant factor, which can be detrimental in practice. Indeed our experiments in ineecioon 4 demonstrate the significance of such constants the utility of these algorithms does not match that of optimal algorithms even empirically, resulting for example in 10% degradation in accuracy for private federated learning over MNIST with 10.
Feldman and Talwar [24] give a general approach to reducing communication via rejection sampling. When applied to PrivUnitG, it yields a natural algorithm that we call Compressed Priv UnitG. While it yields optimal error and near-optimal communication, it requires device run time that is O(e d). These algorithms are often used for large d (e.g. in the range 10y 10²) corresponding large model sizes. The values of æ are often in the range 4- 12 or more, which may be justifiable due to privacy being improved by aggregation or shuffling [10 15 22 25). For this range of values, the O d) device runtime is prohibitively large and natural approaches to reduce this in Feldman and Talwar [24] lead to increased error. To summarize, in the nigh-dimensional setting, communication--ffiiee local randomizers are forced to choose between high device runtime or suboptimal error (see (Table 1).
Another related line of work is non-private communication efficient distributed mean estimation where numerous papers have recently studied the problem due to its importance in federated learning [37 26.
38 39). Similarly to our paper, multiple works in this line of work have used random rotations to design efficient algorithms [3 39 However, the purpose of these works is to
29
23 32
'One often considers the problem for the vectors being of norm at most 1, rather than exactly 1. It is easy to show that vectors in the unit ball in It' can be mapped to S, C [ed+), simply as (v, 1 - lle)12). Thus up to changing d to d the version that is easier to work with.
the two problems are the same. Since are interested in the case of large d, we choose
'There are multiple ways to set parameters of PrivUnit to achieve e-DP we assume the setting described by Asi et al. [7]. which optimizes the parameters to minimize the expected mean squared error.

---

develop better quantization schemes for real-valued vectors to reduce communication to (1 (1+o(1)) d bits. This is different from our goal, which is to send & < d parameters while still obtaining the statistically optimal bounds up to 1 + o(1) factor. Moreover, in order to preserve privacy, our algorithms require new techniques to handle the norms of the projected vectors, and post-process them using different normalization schemes, in order to guarantee that the projection error after post-processing is negligible.
1.1 Contributions
Our main contribution is new framework, ProjUnit, for private mean estimation which results in near- optimal, efficient, and low-communication algorithms. Our algorithm obtains the same optimal utility as Univ and PrivUnitG but with a significantly lower polylogarithmic communication complexity, and device runtime that is (d d) and server runtime On + d). We also implement our algorithms and show that both the computational cost and communication cost are small empirically as well. Figure plotts the error as a function of e for several algorithms and demonstrates the superiority of our algorithms compared to existing low-communication algorithms (see more details in Section 4). Moreover, we show that the optimal error bound indeed translates to fast convergence in our private federated learning simulation.
At a high level, each local randomizer in our algorithm first projects the vector to a randomly chosen dineeiiimesionnal subspace, and then runs optimal local randomizer in this lower- dimensional space. At first glance, this is reminiscent Johnson-Linddestrauss (JL) transform the use of various embeddings in prior work (such (14). However, unlike the JL transform and embeddings in prior work, in our application, each point uses its own projection matrix. The JL transform designed to preserve distances between points, not the points themselves. In our application, a random projection is used to obtain a low-dimensional unbiased estimator for point; however the variance of this estimator is quite large (of the order of d k)). Our main observation is that while large, this variance is small compared to the variance added due to privacy when & chosen appropriately. This fact allows us to use the projections as a pre-processing step. With some care needed to control the norm of the projected vector which is no longer fixed, we then run a local randomizer in the lower dimensional space. We analyze the expected squared error of the whole process and show that as long as the random projection ensemble satisfies certain specific properties, the expected squared error of our algorithm is within (1 + o1)) factors of the optimal; the o(1) term here falls with the projection dimension k. The required properties are easily shown to satisfied by random orthogonal projections. We further show that more structured projection ensembles, that allow for faster projection algorithms. also satisfy the required properties, and this yields even faster device runtime.
the use of random projections in the
Although these structured projections result in fast device runtime, they still incur an expensive computational cost for the server which needs apply the inverse transformation for each client, resulting in runtime Ond log d). Specifically, each device sends a privated version é; of W and the server must then compute E, W 6; To address this, we use correlated transformations in order reduce server runtime while maintaining optimal accuracy up to 1 + o(1) factors. In our correlated PnojUnit protocol, the server pre-defines a random transformation W, which all devices then use to define Wi S,W where S, is a sampling matrix. The advantage is then that Σ, W;T 6, replaced with Σ, W T 0; = W WT (E, Szūz), which can be computed more quickly as it requires only a single matrix-vector multiplication. The main challenge with correlated transformations is that the correlated client transformations result in increased variance. However, we show that the independence in choosing the sampling matrices S; is sufficient to obtain optimal error.
Finally, we note without correlating projections each client using its own projection would imply that each projection needs to be communicated to the server. Doing this naively would require communicating kd real values completely defeating the benefits of our protocol. However the projection matrix does not depend on the input and therefore can be communicated cheaply using a seed to an appropriate pseudorandom generator.
2 A random projection framework for low-communication private algorithms
In this section we propose a new algorithm, namely ProjUnit, which has low communication com- plexity and obtains near-optimal error (namely, up a o+) factor of optimum). The starting point
3

---

Run-time (client)
Run-time (server)
Utility
Communication
Repeated PrivIIS
1
24
O(OPT)
ed d
n [e] nd
E. -pooy(log d)
PnivUnit
g
OPT
SQKR
O(OPT)
dlgg d
ne log d d logg
log d
CompPrivUnit
A
(1)) OPT
e
nd.lg
8 poly(log d)
UnstProjUnit
(Section 2)
(1+ ((1)) OPT
d log d
nd log d
slog" d
FastProjUnit-cor
(Section 3)
(1+ -
dlog d
n nog' d ne no d
log d
Table Comparison of Eroe-BuntineCoommnniaton trade-offs for different algorithms for private mean estimation. The last two rows use our algorithms from [Section 2 and [Section 3 with communication budget & Rs e log PrivUnitG is omitted as it has the same guarantees as PrivUnit except utility where it has (1 + o(1) OPT. We omit constant factors from the run-time and communication complexitics.
TestProjint
Figure 1: Squared error of different algorithms as function of for 32768 averaged over 50 runs with 90% confidence inter- vals. The lines for the top three algorithms almost identical.
Projkit
Squared Enor
RePriVHS
SOKR
10t
12
14
of our algorithms a randomized projection map in &xd which we use to project the input vectors to lover-dimensional space. The algorithm then normalizes the vector necessary pre-processing step. Finally, the local randomizer applies PrivUnitG (7] (see Algorithm 8) in Appendix) over the normalized projected vector and sends the response the server. The server then applies the inverse transformation and aggregates the responses in order to estimate the mean. We present the full details of the client and server algorithms in Algorithm and Algorithm 2]
To analyze this algorithm, we first present our general framework for an arbitrary distribution over projections. In the next sections we utilize different instances of the framework using different random projections such as random rotations and more structured transforms.
Algorithm ProjUnit (client)
Require:
Input vector E Rd Distribution over projections W.
1: Randomly sample transform W E k from W
2: Project the input vector Up = We
3: Normalize
2p
[pll. 4: Let á = PrivUnitG(u)) (as in Algorithm 8
5: Send å and (encoding of) W to server
The following theorem states the privacy and utility guarantees of ProjUnit for a general distribution over transformation W that satisfies certain properties. For ease of notation, let Reu denote the PnojUnit local randomizer of the client (Algorithm 1), and Apu denote the server aggregation of

---

Algorithm 2 ProjUnit (server)
1: Receive , új from clients with (encodings of) transforms Wi,..., Wa
2: Return the estimate - - WiY i;
ProjUnit (Algorithm 2). To simplify notation, we let
Err (PrivUnit)) = Err,, Erri,a(Arivvnnnc,, ReaiVnniG. = Cd.e
denote the error of the PrivUnitG e-DP protocol where ApriLLn Uniis denote the PrivUnitG protocol with optimized parameters (see Algorithm 8) and Cd.e (1) is constant 77.. We defer the proof to Appendix B.1.
Theorem 1. Let k S d and assume that the transformations W; R Rexd are independently chosen from a distribution W that satisfies:
[ [1]] < d/k: Bw-
1. Bounded operator norm: TE
2. Bounded bias:
Wan
w S vaw for all unit vectors E Rd.
W.rllla
Then for all unit vectors Uly..., randomizers ReU are s-DP and
Un E Rd setting ğ Apu (Reu(vi),... Reu(Un)), the local
27
(1+ k:Sw
+0 E + ((+logh) )) aw.
E
P
0/
I Err (Erm,.(PrivUnnic))
d
k
2.1 ProjUnit using Random Rotations
Building the randomized projection framework of the previous section, in this section we instantiate with a random rotation matrix. In particular, we sample W E Rexd with the structure
d WH = SU.
(1)
where E Rdxd a random rotation matrix such that UT- and Rexd is a sampling matrix where each row has a single in uniformly random location (without repetitions). The following theorem states our guarantees for this distribution.
Theorem 2.
Let l S d and Then for all unit vectors U1,..., E Rdd, setting jı Apu (Reu(v1)..... RRu((V)) the local randomizers Reu are e-DP and
Rxd be a random rotation matrix sampled as described in ①
Errn Erri,((PriUUnnnC)) (1+0
E log )) +0 (et0((()))) k
E
A
U
71
The proof follows directly from Theorem I and the following proposition which proves certain properties of random rotations. We defer the proof to topppendix B.2
Proposition 1. Let W k be a random rotation matrix sampled as described ! Then
|| V
Bounded operator norm:
2. Bounded bias: for every unit vector E Rdd
E
www.. w W
/ O(1/k)
We also have similar analysis for Gaussian transforms with additional O O(/k/d) factor in the first term. We include the analysis in Appendix D
5

---

2.2 Fast ProjUnit using the SRHT
While the random rotation based randomizer enjoys near-optimal enror and low communication complexity, its runtime complexity is somewhat unsatisfactory as it requires calculating We for W e Rxxd taking time (kd)). In this section, we propose ProjUnit algorithm using the Subsampled Randomized Hadamard transform (SRHT), which is closely related to the fast JI. transform R We show that this algorithm has the same optimality and now-communicationn guarantees as the random rotations version, and additionally has an efficient implementation with O(dlog d' client runtime.
The SRHT ensemble contains matrices WH E R faxdd with the following structure:
WH V SHD:
(2)
where S Rexd is sampling matrix where each has single in uniformly random location sampled without replacement, H E Rdxd is the Hadamard matrix, and D E Rdxd is diagonal matrix where Da independent samples from the Rademacher distribution, that is, Dj ~ Unif{- +1, The main advantage of the SRHT is that there exist efficient algorithms for matrix-vector multiplication with H.
The following theorem presents our main guarantees for the SRHT-based ProjUnit algorithm.
Theorem 3. Let k I d and W be sampled from the SRHT ensemble as described in 2 Then all unit vectors V1...... Un E R2, setting P = Apu (Rpu(t1).... ".pG)),...,RR((...... (Pu(Un)), the local randomizers Reu are s-DP and
Errr,,(PrivUunitt (1+
(
(E+ log )) + log" d
E
i
T1
k
Remark 1. The communication complexity of SRHT-based ProjUnit can be reduced to O log d log² d). To see this, note that û is k-dimensional vector. Moreover, the matrix W W=v/ Vd/k SHD can be sent in Ok log d) as follows: S has lo rows, each with a single entry that contains hence we can send the indices for each row using log d bits for each row. Moreover, H is the Hadamard transform and need not be sent. Finally, D is a diagonal matrix with entries Dạ Unif +1}. By standard techniques (36 5]. we only need the entries of D to be (llo(()) ([ii(d))-wise independent for Proposition 2 to hold. Thus Olog" d) bits suffice to communicate sampled D.
The proof of the theorem builds directly on the following two properties of the SHRT.
Proposition 2. Let W be sampled from the SRHT ensemble as described in Then we have
1. Bounded operator norm:
E W II] = [[[[[ S Va/k.
2. Bounded bias: for every unit vector E Rd:
E
WwW W
WT
// O(log(d)/VR))
Theorem 3 now follows directly from the bounds of Theorem deter the proof to Appendix B.3
using ow = O(log(dd/kk) We
Remark 2. While our randomizers in this section pay an additive term that does not decrease with n (e.g. log' (d)/k: for SRHT), this term is negligible in most settings of interest. Indeed, using Theorem 3 and the fact that Err, PrivUUnni)) = d/.ed/ne, we get that the final error of our SRHT algorithm is roughly d aodn=((1+ o(1) (loog (d)/k). This implies that in the high digeesiinn setting the bias term is negligible.
However, to cover the whole spectrum of parameters, we develop nearly unbiased versions of these algorithms Appendix A) particular, we show in Theorem 6 that our unbiased version has error
(1+0
(
[ log
log(nd/k)
Errna Erina(PrivUnntC))
k
3 Efficient Server Runtime via Correlated Sampling
One downside of the algorithms in the previous section that server runtime can costly: indeed, each client uses independent transformation, the server has to apply the inverse transformation

---

(matrix multiplication) for each client, resulting in runtime O(nd d). In this section, we propose new protocol that significantly reduces server runtime to O(n log' d + d log d nk) while retaining similar error guarantees. The protocol uses correlated transformations between users which allows the server to apply an inverse transformation only small number of times. However, clients cannot use the same transformation as this will result large bias.
The protocol works as follows: the server samples U E Rdddd from the Randomized Hadamard transform: U HD where H Rdxd is the Hadamard transform, and D R is diagonal matrix where each diagonal entry is independently sampled from the Rademacher distribution. Then, client E [n]], samples random sampling matrix St IR R and uses U define the transform W; R
W; = V
We describe the full details of the client and server algorithms for correlated ProjUnit in Alloriihmm 3 and Algorithm 4] and denote them RcPU and Acpu. respectively. We have the following guarantee. We defer the proof to Appendix C
Algorithm 3 Correlated Pnoj (client)
Require: Input vector E Fd
1: Randomly sample diagonal D from the Rademacher distribution based on predefined seed
2: Sample S E R where each is chosen uniformly at random without replacement from standard basis vectors (ei,...,cd) Ca]
3: Project the input vector Up = SHDu where E IRd is the Hadamard matrix
4: Normalize
Sp
5: Let û = Priv Un)tG(u) (as in Algorithm 8)
6: Send and (an encoding of) S server
Algorithm 4 Correlated ProjUnit (server)
1: Receive ū,,.... ú1 from clients with (encodings of) transforms St, Sn
2: Sample diagonal matrices D from Rademacher distribution based on predefined seed d is the Hadamard matrix
3: Let U = HD D where H E Rdxd
4: Return the estimate j LUT S.S S,T, 0z
Theorem 4. Let k < Then for all unit vectors V1,..., Un E IRd, setting p Acpu (Rcpu()1),..... RcPu(v,)), the local randomizers RePU are e-DP and
1
(1+0 (++log
k 1)0h))
log d
E
12
Moreover, server runtime is On log(d) d) log? (nd) + dlog + nk).
Experiments
We conclude the paper with several experiments that demonstrate the performance of our proposed algorithms, comparing them to existing algorithms in the literature. We conduct our experiments in two different settings: the first is synthetic data, where we aim to test our algorithms and understand their performance for our basic task of private mean estimation, comparing them to other algorithms. In our second setting, we seek to evaluate the performance of our algorithms for private federated learning which requires private mean estimation as subroutine for DP-SGD.
4.1 Private mean estimation
In our synthetic-data experiment, we study the basic private mean estimation problem, aspiring to investigate the following aspects:
7

---

2.1 301
Mivuntd FostProjnntt
Performance of ProjUnit, FastProjUnn and their correlated versions with 90% confidence intervals as a function of for 32768, NumRep 30, n 50, and e =
Figure 2:
1x
Squared Emror
Projuntt
1,9
1.8 1107
1.7 10-
1
15
201
Utility ProjUnit algorithms as function of the communication budget
2. Utility of our low-communication algorithms compared the optimal utility and other existing cowccommunication algorithms
3. Run-time complexity of our algorithms compared to existing algorithms
Our experimente measure the error of different algorithms for estimating the mean of dataset. To this end, sample unit vectors , Un Rd by normalizing samples from the normal distribution N(N, 1/d) (where I2d is a random unit vector), and apply certain privacy protocol NumRep times estimate the mean Σ vt/n, producing mean squared errors c1...., e1....,,NumRepp CNumRep- NuuRee
Our final error estimate then the mean NumRep Σ i= eq. We test the performance of several algorithms: ProjUnit SSbssection 2.1). Unit Subsectton 2.2), FastProj
(Section 3) PnivUnitG 77), CompPrivUnitG 2124). PrivHS [19]. RePrivHS 19 24], SQKR (14).
Figure 2 we plot the error for our ProjUnit algorithms as a function the communication budget k. We consider high-dimensional regime where d = 2 with small number of users 50 and a bounded communication budget
2000). Our plot shows that our ProjUnit algorithms obtain the same near-optimal error Priv UnitG for l: as small 1000. Moreover, the plots show that the correlated versions of our ProjUnit algorithms obtain nearly the same error.
To translate this into concrete numbers, the transform W can be communicated using a small seed (~ 128 bits) in practice, or using log + log" d ~ 20400 bits or less than 3kB for d = 10 Sending the k-dimensional vector of 32-bit floats would need additional 4kB. Thus the total communication cost is between 4 and 8kB. This can be further reduced by using a compressed version of UnitG in the projected space, which requires the client send a 128-bit seed. In this setting, the communication cost is a total of 256 bits. Thus in the sequel, we primarily focus on the & = 1000 version of our algorithms.
10a
10a
ProtantG
Projünk
Pejunnit
10a-
Fasthhofink
Time (seconds)
Prints
Time (seconds)
Pritt
10
CompPriethinn
CompPritettG
10P
10:1
30
16
d
(a)
(b)
Figure 3: Run-time (in seconds) as a function the dimension for (a) = 10 and (b) E 16. The plots for some algorithms not complete they did not finish within the cut-off time.
Thee code is also available online bttps://githiin httpp::/ggicuu..cmm//pppee///// -projuntt

---

MNIST (epsilon 10)
Figure 4: Test accuracy on the MNIST dataset with 90% confidence intervals as a function of epoch for e = 10.0.
Test accuracy
0.50
Gaussian PrivUnits
0.75
FastProjunit d 1000) FastProjunit 1000:
0.70
5)
Epoch
Next, we compare the performance of our Iow-communication algorithms against existing low- communication algorithms: PrivHS and SQKR. In Figure I] we plot the error as function of the privacy parameter for each algorithm using the best choice of k (bound on communication) for each algorithm. In particular, we choose = E for SQKR, num repetitions R = E/2 for repeated PrivHS, & 1000 for ProjUnit and FastProjUnit. Moreover, in this experiment and NumRep = 50 to estimate the variance each method. The figure shows that PrivHS and SQKR, while having now-communication complexity, suffer significantly worse utility than (near- optimal) PrivUnitG: On the other side, both our UrojUnit algorithms obtain nearly the same error as PrivUnitG with bounded communication budget of k 1000.
set 1
In our third experiment in Figure 3, we plot the runtime of each algorithm as a function of the privacy parameter. Here, we use 1, NumRep 10 and measure the run-time of each method for different values of the dimension d and privacy parameter E, allowing each method to run for hour before interrupting. As expected from our theoretical analysis, the runtime of ProjUnit using random rotations is noticeably slower than the (high communication cost) PrivUnitG. However, our SRHT-based FastProjUnit is substantially faster and has comparable run-time to PrivUnitG. Moreover, for large e and d, the run-time of compressed PrivUnitG becomes too costly compared to algorithms due to the end time complexity.
4.2 Private federated learning
Having demonstrated the effectiveness our methods for private mean estimation, this section we illustrate the improvements offered by our algorithms for private federated learning. Similarly the experimental setup in [13], we consider the MNIST (31 datasct and train a convolutional network (see Table 2) using DP-SGD [ with 10 epochs and different sub-routines for privately estimating the mean of gradients at each batch. order to bound the sensitivity, we clip the gradients to have fo-m 1, and run DP-SGD with batch size of 600, step-size equal to 0.1, and momentum of 0.5.
Figure 4 shows our results for this experiment, where we plot the test accuracy as a function of the epoch for each method. The plots demonstrate that our ProjUnit algorithms obtain similar performance to PrivUnitG, and better performance than the Gaussian mechanism or PrivHS. For the Gaussian mechanism, we set d = 10-5 and add noise to satisfy (e, 8)DP using the analysis in [8) We did not run SQKR in this experiment as it is not sufficiently computationally efficient for this experiment and has substantially worse performance in the experiments of the previous section. We also did not run the MVU mechanism [3] as their experiments show that it is worse than the Gaussian mechanism which has worse performance than methods.
Finally, our private algorithms obtain accuracy roughly 91%, whereas the same model trained without privacy obtains around 98%. This degradation in accuracy is mostly due to the choice of the optimization algorithm (DP-SGD with clipping); indeed, even without adding any noise, DP-SGD with clipping achieves around 91% accuracy, suggesting that other private optimization algorithms with different clipping strategies (e.g. [4 6)) may tighten this gap further. As this is not the main focus of our work, we leave this investigation to future work.

---

Acknowledgments
HLN is supported by NSF CAREER grant 1750716 and NSF grant 2311649.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Nya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 23rd Annual ACM Conference on Computer and Communications Security (CCS), pages 308-318, 2016.
[2] Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan. epsgd: Communication--ffiee and differentiallly-riivanl distributed sgd. In Proceedings of the 3 Annual Conference on Advances in Neural Information Processing Systems (NeurIPS), 2018.
[3] Nir Ailon and Bernard Chazelle. The fast Johnson-Lindensttrann transform and approximate nearest neighbors. SIAM Journal Computing, 39(1):302-322, 2009.
[4] Dan Alistarh, Demjan Grubic, Jenry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-eefioii sgd via gradient quantization and encoding. In Guyon, U. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Ad- vances in Neural Information Processing Systems, volume 30, pages 1709-1720. Curran Associates, Inc., 2017. URL
www..pps.ccpaape///// ptcppppp//011//iieee pdf
[5] N. Alon and J. H. Spencer. The Probabilistic Method. Wiley-Interscience, second edition, 2000.
[6] Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 383-392, 2021.
[7] Hilal Asi, Vitaly Feldman, and Kunal Talwar. Optimal algorithms for mean estimation under local differential privacy. In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
[8] Borja Balle and Yu-Xia Yu-Xiang Wang. Improving the gaussian mechanism for differential pri- vacy: Analytical calibration and optimal denoising. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 394-403. PMLR, 2018.
[9] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Protec- tion against reconstruction and its applications private federated learning. arXiv.1812.00984 [stat.MLJ,, 2018.
[10] Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, llya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo: Strong privacy for analyties in the crowd. In Proceedingy of the 26th Symposium on Operating Systems Principles, SOSP '17, page 441-459, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781 9503555350 doi: 10. 10.11455/1322777731327666 URL https //doi. 1100001111/3333 .7.112277773333789 3132769
[11] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for machine learning. In Proceedings of the Annual ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 1175-1191, 2017.
[12] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12: 12:1-1991100 1109, 2011.
[13] Kamalika Chaudhuri, Chuan Guo, and Mike Rabbat. Privacy-aware compression for federated data analysis. In Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, volume 180, pages 296-306. PML.R, 2022. URL httpp::/pprcceeeeeee mlr press/v180 http/chaahhhca// html
10

---

[14] Wei-Ning Chen, Peter Kairouz, and Ayfer Özgür. Breaking the communication- privacy accuraacy trilemma. In Proceedings of the 33rd Annual Conference on Advances in Neural Information Processing Systems (NeurIPS), 2020.
[15] Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryp- tology - EUROCRYPT 2019, pages 375-403, Cham, 2019. Springer International Publishing. ISBN 978-3-030-11653-2.
[16) Michael B. Cohen, Jelani Nelson, and David P. Woodruff. Optimal approximate matrix product terms of stable rank. Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), pages 11:1-11:14, 2016. Full version at https
//arxiv. org/ www.or//////a/o/eeo/////e.eeeee/ absaaaa/1/00 110./1507..00 02268v3
[17] K.R. Davidson and Stanislaw Szarek. Local operator theory, random matrices and banach spaces. Handbook the Geomelry of Banach spaces, Vol. 1, pages 317-366, 01 2003.
[18] John Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Proceedings of the 32nd Annual Conference on Learning Theory (COLT), pages 1161-1191, 2019.
[19] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 1136521)182-2155, 2018.
[20] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology (EUROCRYPT 2006), 2006.
[21] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Theory of Cryptography Conference, pages 265-284, 2006.
[22] Ulfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth ACM-SIAM Symposium on Discrete Algorithmms (SODA), 2019.
[23] Fartash Faghri, Iman Tabrizian, Ilia Markov, Dan Alistarh, Daniel M. Roy, and Ali Ramezani- Kebrya, Adaptive gradient quantization for data paraalea sgd. In Advances in Neural Information Processing Systems, volume 33, 2020.
[24] Vitaly Feldman and Kunal Talwar. Lossless compression of efficient private local randomizers. In Proceedings of the 38th International Conference Machine Learning, volume 139, pages 3208-3219. PMLR, 2021.
[25] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 954-964, 2022. doi: 10.1 [cs.LG].
FOCS52979.2022 200000 arXiv:2012.
12803 12200
[26] Venkata Gandikota, Daniel Kane, Raj Kumar Maity, and Arya Mazumdar. vqsgd: Vector quantized stochastic gradient descent. arXiv preprint arXiv:1911.07977, 2019.
[27] Antonious M. Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffled model of federated learning: Privacy, communication and accuracy trade-offs, 2020.
(28) Parikshit Gopalan, Daniek Kane, and Raghu Meka. Pseudorandomness via the discrete fourier transform. pages 903-922, 10 2015, doi: 10. 20009//00...01...6...
[29] Jakub Konečný and Peter Richtárik. Randomized distributed mean estimation: Accuracy vs. communication. Frontiers in Applied Mathematics and Statistics, 4:62, 2018.

---

[30] Pravesh K. Kothari and Raghu Meka. Almost optimal pseudorandom generators for spherical caps: Extended abstract. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, page 247-256, New York, NY. USA, 2015. Association for Computing Machinery. ISBN 9781450335362.
doi: N0.11455274653997744444
URL
https://doi.org
1141/ 2746539 2746611
[31] Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database, 1998. URL http://yann.. lecun. com/ com/exdb/ exdb/mnist mmist ATT Labs [Online].
[32] P. Mayekar and H. Tyagi. Limits on gradient compression for stochastic optimization. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2658-2663, 2020. doi:
10.1 (000////TT444442220001791147
[33] Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12:
449 461, 1992.
[34] Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X. Yu, Sashank Reddi, and Sanjiv Kumar. AdaCliP: Adaptive clipping for private SGD. arXiv:1908 0e2019988807433 [cs.LG), 2020.
[35] Tamás Sarlós. Improved approximation algorithms for large matrices via random projections. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
pages 143-152, 152, 2006.
[36] Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223-250, 1995. doi: 10.11377000954481192237X,
[37] Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, and H. Brendan McMahan. Distributed mean estimation with limited communication. In Proceedings of the 34th International Confer- ence on Machine Learning (ICML), 2017.
[38] Shay Vargaftik, Ran Ben-Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben-Itzhak, and Michael Mitzenmacher. Drive: One-bir bit distributed mean estimation. Proceedings of the 34nd Annual Conference on Advances in Neural Information Processing Systems (NeurIPS), 2021.
[39] Shay Vargaftik, Ran Ben-Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben Itzhak, and Michael Mitzenmacher. Eden: Communicationn-fficcenn and robust distributed mean estimation for federated learning. In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
12


Reviews:
[{"review_id": "7wvzDLmRsU", "reviewer": "Reviewer_Dc2U", "summary": "The paper considers the problem of performing mean estimation for worst-case data under local differential privacy. The precise setting considered involves $n$ users, each of whom has one data vector $v_i$ (which, without loss of generality, can be assumed to exist within the unit ball). The users must privatize their data and send them to a central server which tries to estimate $\\frac{1}{n} \\sum_i v_i$ as accurately as possible using the privatized data. The older work of Asi et. al. showed that the PrivUnit algorithm of Bhowmick et. al. attains the optimal error rate among all unbiased estimators. However, implementing that approach leads to concerns regarding the number of bits that need to be exchanged, as well as the runtime, both from the perspective of the clients and the server. The present work tries to address these concerns by using an approach relying on random projections. In particular, the users embed their data into a low-dimensional sub-space of the original space and privatize the resulting vectors. This results in a significantly smaller number of bits being exchanged, thus addressing the issue of potential constraints in communication. In greater detail, the authors give two different algorithms, both of which fit into the above framework. The first algorithm involves each user randomly sampling their own projection matrix, which they must communicate to the server. On the other hand, the second algorithm involves the server choosing a matrix which they communicate to the clients, and then each client has to transform the matrix using their own sampling matrix. For both approaches, the overhead in the error is small ($1 + o(1)$ specifically), while the latter approach manages to significantly reduce not just the communication between servers, but also the runtime for both the clients and the server. The theoretical results are complemented by experiments which support them.", "questions": "No questions.", "limitations": "No obvious negative societal impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very well written and gives a complete picture, covering both theoretical aspects and empirical evaluation. Additionally, the coverage of the prior work in the introduction is quite thorough, so the results are clearly positioned within the overall literature. Considering the computational aspects (in addition to the statistical ones) of performing mean estimation under local differential privacy is a very well motivated question, which the paper does a good job of addressing by giving algorithms that have significant improvements compared to prior work. For that reason, I believe that it is of interest to the NeurIPS community.", "weaknesses": "No obvious weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback.\n"}, {"review_id": "L5ezAKYRJH", "reviewer": "Reviewer_r6Zt", "summary": "The paper studies the problem of locally private mean estimation, and design algorithms with optimal (upto $1+o(1)$ factor) error with better communication complexity and runtime. The key idea behind improved communication complexity and runtime is (a certain) random projection based pre-processing step.", "questions": "Please respond to the weaknesses. Another simple questions is: why not use same $W$ in every client? Then the server won't have apply the inverse transformation (matrix multiplication) for each client. Is there some fundamental reason this isn't done?", "limitations": "The paper focuses on obtaining optimal (upto upto $1+o(1)$ factor) error for worst-case instances (minimax risk). Consequently, methods which achieve optimal error but with (large) constant factor are deemed inferior. However, in practice, the instances are usually not worst-case but are rather structured (eg: sparse) and therein non-optimal methods may fare better (unlesss there is something fundamental about the achieving worse error regardless of the instance). Therefore, more instance-specific guarantees may be needed to reflect improvement in practice. This is not to say that worst-case error (which is studied in this paper) isn't interesting and important.    \n", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The problem of private mean estimation is an important problem in itself and moreover, a lot of interest is also derived from its application to federated learning. Hence, there has been a lot of work recently on devising \"better\" algorithms for it in various settings. The paper identifies gaps in our understanding of the problem, mainly on obtaining optimal error with better communication complexity and runtime, and make solid contributions towards them.\n\n2. The paper is written well. Instead of presenting the final result first, it gradually builds towards conveying the challenges and key ideas.\n\n3. The experiments are encouraging, testing various aspects and comparison with many known methods. Further, the experiments section is well-organized and outlined.", "weaknesses": "1. The underlying key technique -- random-projection to smaller dimensions -- is simple and has been used in the prior works for this problem (albeit without the privUnit). Further, even improvements gained via Subsampled Randomized Hadamard Transform follow standard ideas used in prior works. I encourage the authors to highlight if there are significant differences between this paper and the prior works.\n\n2. While I enjoyed reading Section 2 where the authors gradually build towards the main results and various instantiations, I found Section 3 to be short. It does not provide intuition on how correlated sample is beneficial. Similarly, Remark 2 references unbiased versions of the proposed procedures, deferred to Appendix A.  I encourage the authors to expand on these, if possible. \n\nMinor: Table 2 referenced is missing in the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and positive feedback. Below we answer all of their questions.\n\n1. Technical challenges: While the techniques we use are similar to techniques used in the *non-private* version of the problem, our paper is the first to use them with privacy and several challenges arise in doing so. One of the technical challenges that comes from privacy is that the private randomizers only apply to vectors of bounded norm, thus requiring us to deterministically and carefully control the norm of the projected vector. While one could use a conservative upper bound on the norm (e.g. twice the expected norm),  the norm bound linearly impacts the privacy error, and this conflicts with our goal of getting (1+o(1))*OPT error.  We discuss these differences in lines 70-78 and we will elaborate and highlight them more prominently in the revised version.\n\n2. Unclarity in Section 3: as requested by the reviewer, we will add more intuitions and clarifications to section 3. Briefly, the main point of that section is to improve the server runtime compared to non-correlated transformations: the protocols of section 2 (non-correlated transformations) have runtime ~ n*d whereas the protocols of section 3 (based on correlated transformation) have a significantly better runtime of ~ n + d.\n\n3. Same matrix for each client: unfortunately, using the same matrix for all clients is not possible in our setting as our goal is to estimate the mean, hence using the same matrix for all clients results in large bias for mean estimation. Section 3 uses correlated matrices, which allows to improve the runtime of the server, requiring only a single inverse step in this case. We will elaborate on this more in the paper.\n\n4. Worst-case vs instance-dependent: we agree with the reviewer about the importance of obtaining instance-dependent guarantees. However, the focus of our paper is on the worst-case setting, and we leave the instance-dependent setting to future work.\n"}, {"review_id": "6BYzK9K1Xo", "reviewer": "Reviewer_kcoe", "summary": "The paper introduces a fast algorithm for private mean estimation under communication constraints. The proposed scheme primarily relies on random projection, and the algorithm enhances speed through the utilization of Hadamard matrix and sampling techniques.", "questions": "- Could you please specify the exact value of k used in Figure 1?\n\n- As both SQKR and the current work utilize Kashin's representation, which can be approximated using an orthogonal matrix, it might be worth exploring the possibility of a unified framework that encompasses both algorithms.\n\n- Does the LDP constraint automatically hold due to the inclusion of PrivUnit in the projected space?\nEven in correlated sampling?", "limitations": "Although the proposed work is impressive in terms of complexity, the communication budget is order-wise suboptimal compared to previous work (e.g., SQKR).", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Theorem 1 offers a theoretical analysis of the utility achieved when random projection is employed.\n\n- It is intriguing to observe that the combination of SRHT (Hadamard matrix + Rademacher diagonal matrix) achieves results close to the optimal.\n\n- The idea of enhancing performance through correlated sampling appears to be a compelling approach.", "weaknesses": "1. I believe the current work primarily focuses on the tradeoff between utility and complexity, where the communication budget is relatively higher compared to other algorithms like SQKR. For instance, SQKR has a communication budget of epsilon (~10), while the proposed scheme has k on the order of 10^2 to 10^3 (the communication budget k\\log^2 d is even larger).\n\n2. In Figure 1, comparing the proposed scheme with a communication budget of k\\log^2 d to SQKR with a communication budget of epsilon may appear unfair (despite being the optimal choices for their respective algorithms). To properly compare with SQKR, I suggest the authors provide two separate figures: one with a communication budget of k and another with a communication budget of k\\log^2 d.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and comments. Below we answer all of their questions.\n\n1. Comparison to SQRK (communication):\nThe primary emphasis in this paper is on getting the optimal error bounds with practical communication:  our work is the first to achieve optimal utility with feasible communication that is logarithmic in the dimension. It's important to highlight that SQKR, regardless of the communication budget, fails to provide optimal utility bounds and exhibits an order of magnitude disparity in error (increasing k > epsilon doesn't reduce the error of SQKR). We note, however, that getting constant-optimal bounds with smaller communication is a natural open question.\nAdditionally, SQKR relies on the model of shared randomness, which is less practical. In the private randomness model SQKR would additionally need to send k \\log d bits to specify the indices of bits (as we show in Table 1). \n\n2. Figure 1: we use k=1000 (see details in section 4 in the paper).\n\n3. Kashin representation: we note that our work, unlike SQKR, does not use Kashin representation and instead builds on orthogonal transformations. Kashin representation has two main limitations compared to our approach: first, it is more computationally expensive to find a Kashin representation than using our transforms (e.g. SRHT), moreover, Kashin requires us to increase the dimensionality by a constant factor, hence, is unlikely to give utility bounds with optimal constants. Indeed, the difference comes from us requiring only an $\\ell_2$ bound on the projected vector, whereas SQKR needs an $\\ell_\\infty$ bound, leading to additional constant overheads.\n\n\n4. LDP constraint: the reviewer is right; privacy holds because we apply PrivUnit over a unit input vector. The transformation only changes the input vector, which doesn’t matter for the privacy analysis, hence this holds for input-independent correlated transformations as well (we will clarify this in the paper).\n"}, {"review_id": "vTO9FNRNaz", "reviewer": "Reviewer_rS8z", "summary": "This paper presents an efficient distributed mean estimation framework, which first reduces local data dimension using (different) random projections and then applies an existing private processor (Asi et al [7]) on the projected data before sending them to the server. Further speedups of the framework are also presented, using a more efficient projection matrix and correlated sampling. Utility bounds of the framework and its speedups are derived, and experimental results on both synthesis and real-world data sets are presented.", "questions": "Could authors respond to my comments [3] and [2] in the Weakness section?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "[1] Accelerating private distributed mean estimation is a useful topic. \n\n[2] The paper (especially, narrative) is beautifully written. \n\n[3] Utility bounds are derived.", "weaknesses": "[1] Novelty of the proposed framework is a bit limited, as it basically applies random projection (in a non-traditional but still considerably straightforward way) on PrivUnitG (Asi et al [7]) to speed up the latter. \n\n[2] Comparison of efficiency to the naive PrivUnitG in Table 2 is missing and should be added. Importantly, I suspect the proposed framework does not significantly improve over PrivUnitG, because it simply applies PrivUniteG on fewer features -- this is partly evidenced in the experimental results (Figure 3), where PrivUnitG appears more efficient. \n\n[3] There is a potential error in the proof of Theorem 1 that may make the result invalid. \n\nIn line 486 (supplementary), equation (i) is argued to follow because $E[\\hat{u}] = u$, but such argument does not make sense to me. Consider a simple case when n = 1, then the equation basically argues $E[||A + B||_2^2] = E[||A||_2^2] + E[||B||_2^2]$. I don't see how this can fly... Can authors elaborate? \n\n\n---------- Update ----------\n\nI've read the author responses and my concerns [2][3] are well-addressed. I have raised my score accordingly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. Below we answer all of their questions.\n\n1. Novelty: While the techniques we use are similar to techniques used in the *non-private* version of the problem, our paper is the first to use them with privacy and several challenges arise in doing so. One of the technical challenges that comes from privacy is that the private randomizers only apply to vectors of bounded norm, thus requiring us to deterministically and carefully control the norm of the projected vector. While one could use a conservative upper bound on the norm (e.g. twice the expected norm),  the norm bound linearly impacts the privacy error, and this conflicts with our goal of getting (1+o(1))*OPT error.  We discuss these differences in lines 70-78 and we will elaborate and highlight them more prominently in the revised version.\n\n\n2. Comparison to PrivUnitG: note that PrivUnitG has the same guarantees as PrivUnit in Table 2 (up to (1+o(1)) term in utility) and we will add a row for PrivUnitG to the table. Crucially, the main improvement of our algorithms over PrivUnitG is in communication complexity, where PrivUnitG requires a communication budget of d whereas our algorithms require epsilon*log(d), which is an exponential improvement. As we mention in the paper, our algorithm is the first communication-efficient algorithm for LDP mean estimation that obtains optimal utility bounds (with exact constants).\n\n3. Error in proof of theorem 1: the proof does not contain an error. The reason is that $E[W_i \\hat{u_i} - W_i u_i]=0$ since $E[\\hat{u_i}] = u_i$ and this holds conditioned on $W_i$. Translating this to the reviewer’s example, this means that we have $E[A]=0$ conditioned on any $B=b$, and therefore $E[\\| A+B\\|^2] = E[\\|A\\|^2] + E[\\|B\\|^2]$. The  cross term vanishes since $E[\\langle A,B\\rangle] = E[\\sum_i A_i B_i] = \\sum_i E[A_i B_i] = \\sum_i \\sum_b \\Pr(B=b) b \\underbrace{E[A_i \\mid B=b]}_0 = 0$. We will add further clarification to the proof in the paper. We hope this resolves the concerns that the reviewer has about the validity of our results."}]

Author rebuttal:

Meta-review: This paper addresses the problem of distributed mean estimation with privacy. The recent optimal algorithms of PrivUnit suffers from large communication cost. This paper significantly improves the number of bits required to be transmitted, using random projections. The reviewers agree that this paper makes foundational advances in a fundamental problem of private mean estimation.
Decision: Accept (poster)