Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation
Authors: Berivan Isik
Wei-Ning Chen
Ayfer Ozgur
Tsachy Weissman
Albert No
Venue: NeurIPS 2023 poster (2023)
Keywords: distributed mean estimation
privacy
compression
communication
federated analytics.
TL;DR: We study the exact optimality conditions, together with an exact optimal mechanism for a family of schemes, for distributed mean estimation problem under communication and privacy constraints.

Abstract: We study the mean estimation problem under communication and local differential privacy constraints. While previous work has proposed order-optimal algorithms for the same problem (i.e., asymptotically optimal as we spend more bits), exact optimality (in the non-asymptotic setting) still has not been achieved. In this work, we take a step towards characterizing the exact-optimal approach in the presence of shared randomness (a random variable shared between the server and the user) and identify several conditions for exact optimality. We prove that one of the conditions is to utilize a rotationally symmetric shared random codebook. Based on this, we propose a randomization mechanism where the codebook is a randomly rotated simplex -- satisfying the properties of the exact-optimal codebook. The proposed mechanism is based on a $k$-closest encoding which we prove to be exact-optimal for the randomly rotated simplex codebook.

Exact Optimality of CommunicatoonPPivayy--iiii Tradeoffs in Distributed Mean Estimation
Berivan Isik
Wei-Ning Chen Stanford University wnchen@stanford. edu
Stanford University
berivan www.iiitiiiirreeeeoo.o.o edu
Ayfer Ozgur
Tsachy Weissman
Albert No Hongik University albertno@hongik ac. kr
Stanford University
Stanford University
aozgur@stanford.
tsachy@stanford. edu
Abstract
We study the mean estimation problem under communication and local differential privacy constraints. While previous work has proposed order-optimal algorithms for the same problem (i.e., asymptotically optimal as we spend more bits), exact optimality (in the non-asymptotic setting) still has not been achieved. In this work, we take a step towards characterizing the exact-optimal approach in the presence of shared randomness (a random variable shared between the server and the user) and identify several conditions for exact optimality. We prove that one of the conditions is utilize a rotationally symmetric shared random codebook. Based on this, we propose a randomization mechanism where the codebook is randomly rotated simplex - satisfying the properties of the exact-optimal codebook. The proposed mechanism is based on k-closest encoding which we prove to be exact-optimal for the randomly rotated simplex codebook.
Introduction
The distributed mean estimation problem has attracted attention from the machine learning community it is canonical statistical formulation for many stochastic optimization problems such dis- tributed SGD T 32 and federated learning [33] 34]. As these tasks require data collection from the users, the mean estimation problem has often been studied under privacy constraints to protect g
9 29 35 have analyzed and improved the tradeoff between the utility and e-local differential privacy (e-LDP) the predominant paradigm in privacy mechanisms, which guarantees that an adversary cannot distinguish the user data from the outcome of the privacy mechanism [10 [24] Among them, [4] g 9 developed algorithms that are asymptotically optimal, achieving an optimal mean squared error (MSE) proportional to
users' sensitive information. More specifically, several works 2 4 7
)) where n is the number users, and d is the input dimension. Later, 7 proved the
corresponding lower bounds that hold for all privacy regimes. However, only PrivUnit t [4] enjoys exact optimality among a large family of mechanisms, as proved by [2], while others provide only order optimality and their performance in practice depends heavily on the constant factors.
Another important consideration in the applications of mean estimation is the communication cost during user data collection. For instance, in federated learning, clients need to send overparameterized machine learning models at every round, which becomes significant bottleneck due to limited resources and bandwidth available to the clients (22] 25
28 This has motivated extensive research on
mean estimation 31 34 38 and distributed SGD I 3 13 26 37 under communication constraints;
and communication-effficcenn federated learning 17
18
21
33
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In addition to the lines of work that studied these constraints (either privacy or communication) separately, recently, there has also been advancement in the joint problem of mean estimation under both privacy and communication constraints. (6] introduced an order-optimal mechanism SQKR requiring only O(s) bits by using shared randomness - random variable shared between the server and the user (see Section 2 for the formal definition). Later, [30] demonstrated better MSE with another order-optimal algorithm, MMRC, by simulating PrivUnit using an importance sampling technique [5] again with shared randomness. In the absence of shared randomness, the order- optimal mechanisms proposed by [6] do not achieve the best-known accuracy under this setting and outperformed by the lossless compression approach in [12 that compresses Pri privinit using pseudorandom generator (PRG). Due to not using shared randomness, these mechanisms require more bits than others 6 30 that use shared randomness in the scenarios where it is actually available.
1.1
Contributions
To our knowledge, existing mechanism achieves exact optimality under both privacy and commu- nication constraints with shared randomnes?" In this work, we address this gap by treating the joint problem as lossy compression problem under s-LDP constraints.
Our first contribution is to demonstrate that the exact optimal scheme with shared randomness can be represented random coding with codebook- generating distribution. Specifically, under b bits of communication constraint, the server and the user generate a codebook consisting of .M- = 2 vectors (codewords) using shared randomness. The user then selects an index of a vector under distribution that satisfies e- c-LDP constraints, and the server claims the corresponding vector upon receiving the index. We term this approach as "random coding with codebook" and demonstrate that this (random codebook generation) is the optimal way to use shared randomness.
Next, we prove that the exact-optimal codebook- -gnerating distribution must be rotationally sym- metric. In other words, for any codebook- -eeebokkgenn distribution, the distribution remains the same after random rotation. Based on this insight, we propose Random Rotating Simplex Coding (RRSC), where the codebook- -gebbbrtggnn distribution is a uniformly randomly rotating simplex. This choice of codebook distribution is reasonable as it maximizes the separation between codewords, which efficiently covers the sphere. The corresponding encoding scheme is the k-closest encoding, where the top-k closest codewords to the input obtain high sampling probability, and the remaining ones are assigned low probabilities. We show that this scheme is exact-optimal for the random rotating simplex codebook.
The proposed codebook generation is valid only when M < (or S log d where b the communi- cation budget) due to the simplex structure of the codebook. Note that as shown in [6] b < log d bits of communication budget is sufficient to achieve orderwise optimal MSEs under an e-LDP constraint for any s O (log d), which is usually common scenario in practical applications such as federated learning where d can range from millions to billions. In addition, we can also extend the scheme for cases when M 2 d, by using a codebook consisting of (nearly) maximally separated M vectors on the sphere. As the number of bits used for communication increases, we demonstrate that the proposed scheme approaches PrivUnit, which is the exact-optimal scheme without communication constraints.
Finally, through empirical comparisons, we demonstrate that RRSC outperforms the existing order- optimal methods such as SQKR (6) and MMRC (30]. We also observe that the performance of RRSC is remarkably close to that of PrivUnit when the number of bits is set to b ==
1.2
Related Work
The & mean estimation problem is canonical statistical formulation for many distributed stochastic optimization methods, such as communication (memory)-efficite For instance, shown in [14] as long the final estimator of the mean is unbiased, the & estimation error (i.e., the variance) determines the convergence rate of the distributed SGD. As a result, there is a long thread of works that study the mean estimation problem under communication constraints
SGD [3] 34] or private SGD (24..
3 g 13 31 34 39). privacy constraints 16]. or a joint of both 1 6 12 30
Note that also eliminate shared randomness with a private coin setting. See Section 5 for discussion.

---

Among them, 66] shows that θ (E) bits are sufficient to achieve the order-optimal MSE
minnt,,s") and proposes SQKR, an order-optimal mean estimation scheme under both privacy and communication constraints. Notice that the MSE of SQKR orderwise optimal up constant factor. Later on, in [1]. it is shown that the pre-constant factor in SQKR is indeed suboptimal, resulting in an unignorable gap the MSE compared to PrivUnit an optimal &g mean estimation scheme under E-LDP. In the original PrivUnit, the output space is a d-dimensional sphere Sd-1 and hence requires (dd) bits of communication, which is far from the optimal ((E) communication bound. However, 12 shows that one can (almost) losslessly compress PrivUnit via a pseudo-random generator (PRG). Under the assumption of an existing exponentially strong PRG, [2] proves that one can compress the output of PrivUnit using polylog(d) bits with negligible performance loss. Similarly, [30] shows that with the help of shared randomness, PrivUnit can be (nearly) losslessly compressed to θ (s) bits via channel simulation technique, called MMRC. We remark that although the privacy-utility trade-off's in [1]] and [30] are (nearly) exactly optimal, the communication ef- ficiency is only order-optimal. That is, under exact b-bit communication constraint, the MSEs of [1] (denoted as FT21) and MMRC (30] may be suboptimal. In this work, we aim to achieve the exact-optimal MSE under both communication and privacy constraints.
Furthermore, we show that SQKR, FT21, and MMRC can be viewed as special cases in our framework i.e, (random) coding with their own codebook design. We elaborate on this in Section 5 and provide more details on prior work in Appendix !
2 Problem Setting and Preliminaries
In this section, we formally define LDP (with shared randomness) and describe our problem setting.
Local Differential Privacy (LDP) A randomized algorithm Q X - y e-LDP
@(y(x) Qlylx') S
V E &x E y,
LDP with Shared Randomness In this work, we assume that the encoder and the decoder have access a shared source of randomness U E U, where the random encoder (randomizer) Q privatizes x with additional randomness U. Then, the corresponding e-LDP constraint is
O(ylz, u)
Ya, E EX E Y,
I SE
(2)
Q(y(z', u)
for Pu-almost all u.
Notation We let gd-1 = {u E Rd :/uu||2 1} denote the unit sphere, et E Rd the standard basis vectors for = 1, ,, [k] the greatest integer less than or equal to k; and [M] = {1,..... M,..
Problem Setting We consider the lg mean estimation problem with users where each user has a private unit vector v E sd-1 for 1 < i < The server wants to recover the mean Σ after each user sends message using up to b-bits under an e-LDP constraint. We allow shared randomness between each user and the server. More concretely, the i-th user and the server both have access to a random variable U. E R² (which is independent of the private local vector v;) for some / 2 and the i-th user has a random encoder (randomizer) Sa gd-1 x R + [M], where M = 2b. We denote by ft (mg (4, uz) the transition probability induced by the random encoder fi, i.e., the probability that fi outputs my given the source es and the shared randomness u,
Pr[fi(vi, wi) = m.] Q (milu;, uz).
(3)
We require that the random encoder fa satisfies E-DPP, i.e..
2x (m: (V;, us)
QR (mg 10,, us) < e
(4)
3

---

for all Us 1/ E gd-1 m [M] and Pv, almost all us E R'.
The receives m, (u, Uj) from all users and generates unbiased estimate of the mean A(m1,..., Ma, U/....,U. Un) that satisfies
n
E [[(m my U1 ...... Uni] Σ
Up.
(5)
1=1
Then, the goal is to minimize the worst-case error
Errn(S;At Ptn)
sup EBd
A(mi,... May .I.... Un)
0
(6)
where / denotes the collection of all encoders (Ji, fn). We note that the enror is also function of the distribution of shared randomness, which was not the case for PrivUnit 2
Main Results
3.1 Canonical Protocols
Similar to Asi et al. [2]. we first define the canonical protocol when both communication and privacy constraints exist. The canonical protocols are where the server recovers each user's vector and estimates the mean by averaging them. In other words, the server has a decoder gi [M] x R gd-1 for S & M which is dedicated to the i-th user's encoder fi. where the mean estimation is simple additive aggregation, i.e.,
1 Σ
A+ (m1 May U2 Un)
g.,,, U.).
Our first result is that the exact-optimal mean estimation scheme should follow the above canonical protocol.
Po") ) that satisfies unbiasedness and E-LDP, there exists an unbiased canonical protocol with decoders = (91,...,hh, that satisfies E-LDP and achieves lower MSE, i.e.
Lemma 3.1. For any n-user mean estimation protocol (f,A,
Err, (tr,(f,Ar Ptn)
sup o E
E
9e (m,, Ui)
(8)
1=1
Err gos Pu.),
where Crrı(f: Pu) is the worst-case error for single user with a decoder
The main proof techniques are similar to (2. where we define the marginalizing decoder:
ge(m,, U.) By [nA((m,, fiv,, U:) = m,, Us]
(10)
The expectation in T0p with respect to the uniform distribution of vy's. We defer the full proof to Appendix
Since the exact-optimal n-user mean estimation scheme is simply additively aggregating user-wise exact-optimal scheme, throughout the paper, we will focus on the single-user case and drop the index i when is clear from the context, In this simpler formulation, we want the server to have an unbiased estimate i = g U), i.e.
=-Eros (o(f(,,U),U)
(11)
/IM g(m, U)Q (m/v, U?]
=Epr
(12)

---

for all E gd-1 We assume that the decoder : [M] x R' + +R is deterministic, since the randomized decoder does not improve the performance. Then, the corresponding error becomes
D(v, f.g. Pu) =Epu. [ll[ffU, (),0) -
(13)
EM (m U) - =112 f (mlu, U)]
=Epv
(14)
Finally, we want to minimize the following worst-case error over all (f. g) pairs that satisfy the unbiasedness condition in 12)
Brri(f.g,Pr sup Dlc,f.g,Pt wggd-1
(15)
3.2 Exact Optimality of the Codebook
We propose special way of leveraging shared randomness, which we term as random codebook. First, define codebook UM (U1,-- -U) E (R4)M, consisting of M number of d-dimensional random vectors generated via shared randomness (i.e., both the server and the user know these random
vectors). We then define the corresponding simple selecting decoder g [M] (IR)) R which simply picks the m-th vector of the codebook upon receiving the message m from the user:
g*t (m, U = Um.-
(16)
Our first theorem shows that there exists scheme with a random codebook and a simple selecting decoder that achieves the exact-optimal error. More precisely, instead of considering the general class of shared randomness (with general dimension !) and the decoder, it is enough to consider the random codebook UM E (R..MM the shared randomness and the simple selector g as the decoder.
Lemma 3.2. For any f. 9, Py with U E RR' that are unbiased and that satisfy E-LDP, there exists a shared randomness ÜM e (RRM) M and random encoder fo gd-1 x (RR - [M] such that
D(v, 9. Pu) D(v, fo,
.POM) ,
(17)
for all v E S0-1, where fo.g* Pas also satisfy unbiasedness and e-LDP.
The main step of the proof is to set an implicit random codebook with codewords U,, = gmm, U) for m 2,, and show that we can obtain an essentially equivalent scheme with different form of shared randomness ÚMM, which is an explicit random codebook. The detailed proof is given in Appendix B Thus, without loss generality, we can assume .M and the random codebook U is the new shared randomness, where the decoder is a simple selector. Since we fix the decoder, we drop g to simplify our notation. We say the random encoder f satisfies unbiasedness condition
2
Eru
Σ M
UnQ UMM = 8,
(18)
and the worst-case error
Err(f, PuN) sup D(v, S, PVM)
(19)
vE8--1
M Σ
sup EPgn vE84-1
IIU =
(20)
Lm
Thus, the goal is now to find the exact-optimum codebook generating distribution Pra, and the random encoder f (or the probability assignment (-1e, U)). We then argue that the exact-optimal codebook should be rotationally symmetric.
Definition 3.3. A random codebook UM e (Rd) is rotationally symmetric if (UI...., Um) (A,U),..., ar) for any d orthonormal matrix Ag
The next lemma shows that the exact-optimal Pas is rotationally symmetric.
Lemma 3.4. Let PUM be codebook generating distribution, and suppose random encoder satisfies unbiasedness and E-LDP. Then, there exists a random encoder fn and rotationally symmetric random codebook UM such that
Srr(fPPun 2 Err(fi,
(21)
which also satisfies unbiasedness and E-LDP.
5

---

This is mainly because the goal is to minimize the worst- error. and the codebook- generaatingg distribution should be symmetric in all directions. The proof is provided in Appendix C The next lemma shows that the exact-optimal scheme has constant enror for all v E ES
Lemma 3.5. For any rotationally symmetric codebook generating distribution Pyas and an unbiased randomized encoder that satisfies E-LDP, there exists random encoder f2 such that
Err(f,Puu) 2 Err(f2, PVM), where D(v, f2, Pyas) = D(v', Pum))
(22)
for all u, o' S
The formal proof is given in Appendix() D
Since the codebook is symmetric (Lemmaa 3.4 the exact- optimal encoding strategy remains the same for any input v. Thus, without loss of generality, we can assume that the input is standard unit vector u = = (1, (1,0,...,0)
3.3 Rotationally Symmetric Simplex Codebook
Now, we focus on a particular rotationally symmetric codebook. Notice that the codebook U-M has similar role to the codebook in lossy compression, in the sense that we prefer the codeword Um close to the input vector Thus, it is natural to consider the maximally separated codebook so that the M vectors U1.... UM cover the source space effectively. For M < d, the maximally separated M vectors on the unit sphere gd- is simplex. More precisely, let ........M E F form simplex:
M-1
if =j
VM
(8i)
if + j and j S M
(23)
VM(M-1
if > M
Then, we can define the rotationally symmetric simplex codebook U.
U21,U2..... Um) (d) (rAs1, ..... rAsM),
(24)
where A is uniformly drawn orthogonal matrix and r > 0 a normalizing constant. We then need to find the corresponding encoder f that minimizes the error. Recall that the error is
Ep prar
U - w EM
U)):
(25)
and it is natural to assign high probabilities to the message m with low distortion |U - -ll as long e-LDP constraint allows. More precisely, we call the following probability assignment "k-closest" encoding:
||u Um 21? is one of the [ smallest
kee + (M AMM-M k) [K- le kec + +(M
Qm(ml, (MM)
||u Um 2| is the [k] + 1-th smallest,
(26)
otherwise
ke +M k]
where we allow non-integer k. The choice of Fą is described in Section 3.4 We call this approach Randomly Rotating Simplex Coding (RRSC) and provide the pseudocode in Algorithm [ We note that the codewords Un, 's with smallest |/v Um!!! and codewords U,, 's with largest (v. Um) coincide for a codebook with fixed-norm codewords Un, 's, which is the case for the rotationally symmetric simplex codebook. Our main theorem is that the k-closest encoding exact-optimum if the codebook generating distribution is rotationally symmetric simplex.
Theorem 3.6. For a rotationally symmetric simplex codebook, there exists a such that the "k-closest" encoding is the exact-optimun unbiased scheme that satisfies c-LDP constraint.
The main step of the proof is to show that all the probabilities should be either the maximum or the minimum in order to minimize the error, and the proof is given in Appendix E
3.4 k-closest Encoding for General Rotationally Symmetric Codebook
In this section, we demonstrate that the k-closest encoding consistently yields an unbiased scheme for any rotationally symmetric codebook. To be more specific, for any given spherically symmetric

---

Algorithm Randomly Rotating Simplex Coding RRSC(K).
Inputs: v E gd-1, k rk. codebook size M
2".
Codebook Generation:
Generate the simplex s1,..., SM Rd in
Sample orthogonal matrix A Raxd uniformly using the shared random SEED.
Generate the codebook UM; (U1, U2.....UU .UM) (rx ...
Encoding:
for m [M] do
if (v, Um) is one of the k largest then
(mlu, U.
4(M-k
else
Qm(ml, U 4- kee +(M-(M)
end if end for
Sample codeword index mr* + Qu(,u,Um Output: m", encoded in b = log M bits.
codebook U.,. there exists a scalar Tk that ensures that the k-closest encoding with rgU
(raUi....,rruu is unbiased. Let (v, U*) = {m Um is one of the k-closest), and without loss of generality, let us assume v = 61. Then,
EPOM
Em= Qm(mme,, UUmm
e
1 ke + (M - k)
=EpoM
Um
Um
(27)
Ke + -k)
mETi ( (M)
eº -11
Eppa
E Um
(28)
ke + (M- (ETI(EL,MM)
where E Um] due to rotationally symmetric codebook and assume integer & for the sake of simplicity. Since the codebook is rotationally symmetric and we pick k-closest vectors toward e1 each codeword Um [e UM) is symmetric all directions other than v E1. Thus, in expectation, the decoded vector is aligned with e1, and there exists such that
X E BpyM
Σ (0(mlee, UM =11-
(29)
For a rotationally symmetric simplex codebook, where Um = Asm for a uniform random orthogonal matrix A, have (almost) analytic formula.
Lemma 3.7. Normalization constant rk for RRSC(K) is
ke M 1
Tk e
(30)
M
Ck
where C+ is an expected sum of top-k coordinates of uniform random vector gd-1
The key idea in the proof is to show that encoding e with As M equivalent to encoding uniform random vector Sd-1 with M. The formal proof is provided in Appendix
The following lemma controls the asymptotic behavior of Cs:
Lemma 3.8. Let Cg be defined as in Lemma 3.7 Then, it holds that
(v log M
C =
(31)
d
Note that C' depends on k d. and M, but for ease of presentation, we suppress the dependency on and m here and only present the full expression in the proof.
7

---

In addition, there exist absolute constants C1, C2 >
such that as long as [M/k] > C1 and l > C2.
k:2
M
C2 = Ω
log
(32)
k
As corollary, Lemma 3.8 implies the order-wise optimality of RRSC:
Err(RRSC) - 1
(
[ 1 M
d
(e5 165-13 1)2
log
M
k
By picking max (e= the above error is 0 min(("....b)
We provide the proof of
Lemma 3.8 in Appendix
G
3.5 Convergence to PrivUnit
As the communication constraint increases, the exact-optimal scheme with communication con- straint should coincide with the exact-optimal scheme without communication constraint, which is PrivUnit. Note that the rotationally symmetric simplex can be defined only when M 2 < due to its simplex structure. However, we have a natural extension where the codebook is collection of M (nearly) maximally separated vectors the sphere radius т, where we can assume that M codewords are uniformly distributed on the sphere of radius if M is large enough. Consider the case where M7 is fixed and M = is large. Since the k-closest encoding yields an unbiased scheme with error Err(f. Pyar) = r - where F3 is normalizing constant, for uniformly distributed M codewords on the sphere, the constant Fą should satisfy
Tk X ke + (M
E
Σ Lmmtop-k:
Um,1 =
(33)
k)
where Um,1 is the first coordinate uniformly drawn Um from the unit sphere Sd-1, Then, as increases, Um,1 being one of the top-k becomes equivalent to Um,1 >> 7, where y is the threshold such that Pr(Um.1 > >] = Hence, assigning higher probabilities to the top-k closest codewords becomes equivalent to assigning high probabilities the codewords with (Um: e1) > y where e1 This is essentially how PrivUnit operates.
Complexity of RRSC
Each user has d x d orthonormal matrix A and needs to find k smallest (v. Asm) for S m < M. Since (v, Asm) (ATe; v. sm), requires (dd) to compute AT and additional ((Md) to compute all inner products for < m & M. However, if M & d, we have simpler equivalent scheme using
M
M
vA sm) = M
aT v
Σ 1=1
aTu V
(34)
MM(- 1)
where aJ, is the m-th row of the matrix A. Then, it only requires storing the first M rows of the matrix and ((Md) to obtain all inner products in (34) by avoiding (dd²) to construct ATv.
On the other hand, the server computes Asm upon receiving message m. The corresponding time complexity is ((Md) (per user) since $m has M non-zero values. We note that both MMRC [30 and FT21 [12] require the same encoding complexity ((Md) RRSC, where they choose M O(exp(=)).
4 Experiments
We empirically demonstrate the cummuniiation-privayyyuue tradeoffs RRSC and compare with order-optimal schemes under privacy and communication constraints, namely SQKR [ and MMRC [30]. We also show that RRSC performs comparably with PrivUnit
4 which offers the exact-
optimal privacy-utility tradcoff's without communication constraints
2 In our simulations, use

---

the "optimized" PrivUnit mechanism, called PrivUnitG, introduced in [2], which performs better than PrivUnit in practice since it provides an easy-to-analyze approximation of PrivUnit but with analytically better-optimized hyperparameters, Similar to [6 30 we generate data independently but non-identically to capture the distribution-free setting with μ * More precisely, for the first Fi [ 1)04; and for the second half of the users, set
half of the users, set U1, .i..... Un/2
Un/2+1:.... , Un iid (10, 1)8d. We further normalize each v, ensure that they lie on S We report the average la error over 10 rounds together with the confidence intervals. To find the optimal values for and rk. we compute the optimal т7K using the formula in (33 for 1, ..... M and pick the & that gives the smallest тж (which corresponds to the bias). To estimate the expectation C₁ in (33), we run Monte Carlo simulation with 1M trials. We report the k use for each experiment in the captions. Additional experimental results are provided in Appendix
In Figure (left, middle), report &2 error for PrivUnitoe tG), the number of bits is equal to = s. In Figure (right), we report & error by fixing b 8 for RRSC and MMRC. For SQKR, only sweep
...... 8, where for each method (except
e = 6 and sweeping the bitrate from for b S E as it leads to poor performance for b > e. In each figure, RRSC performs comparably to PrivUnitG even for small and outperforms both SKQR and MMRC by large margins.
0200
200
RRSC [ours]
0175
0.755
SOKR
0150
015
MMRC
error
0.225
0.22
PrivUnitG
0100
0.100
0675
0.55
0.500
0.000
0625
0.25
0.000
# bits (b)
Figure Comparison of RRSC with SQKR (6). MMRC [30]. and PrivUnitG (2]. (left) &g error vs with 5000, 500. The number of bits is for k-closest encoding is A = for each e. (middle) Same plot zoomed into higher E, lower lz error region. (right) lg error vs number of bits b for 5000, d 500, and 6. For SQKR, we only report b < ε = 6 since it performs poorly when > E. The choice of k for k-closest encoding is 1,,1,1,1, 1, 4| for 2,, 4, 8]. respectively.
for RRSC, SQKR, and MMRC. The choice of k
The codebase for this work is
5 Discussion & Conclusion
proved that using a rotationally symmetric codebook is a necessary condition for the exact optimality of mean estimation mechanisms with privacy and communication constraints. We then proposed Random Rotating Simplex Coding (RRSC) based on k-closest encoding mechanism and proved that RRSC is exact-optimal for the random rotating simplex codebook. We now discuss some important features of RRSC and provide conjectures for future work.
Unified Framework It turns out that SQKR 6
FT21 12 and MMRC 30 can be viewed as special N
ビØ=1 Uy+ cases in our framework. Specifically, SQKR 6 uses Kashin's 's representation of
where ( E [-c/VVd c/ Vd] for some (1 + 4ddd with μ >> 0 and > 0. Then the SQKR encoder quantizes each ay into 1-bit message q: and draws samples with the help shared randomness. This can be viewed as random coding with a codebook generating distribution. More concretely, the corresponding codebook U consists of & non-zero values of tc/ Vd where the randomness is from selecting indices using shared randomness. On the other hand, since MMRC [30] is simulating the channel corresponding to privacy mechanism, it can be viewed as pre-generating random codewords UM according to the reference distribution, where the importance sampling is also way of assigning probabilities to each codeword. As elaborated in Section 3.5 it is observed that with an increase in the communication constraint b, the suggested k-clossest encoding gradually transforms into threshold- based encoding, analogous to that of MMRC. The codebook associated with FT21 [2]
codebbok-generraing

---

depends on the PRG it uses. Let PRG: {0, 1) + (0. 10.1) be a PRG that takes a b-bit seed and maps it into (d) bits, where b < d, and let {0, (0.1) + R. For example, if we represent each coordinate of x E IR as a 32-bit float, then g(-) maps the float representation of æ (a 32-bit string) to x. With a PRG, FT21 mimics PrivUnit by first generating b-bit seed m, computing (P))(m)), and then performing rejection sampling on the seed space. The above procedure can be treated as a special case in our framework, where the deterministic codebook consists of 2h points on E (0, 1)%. The probabilities assigned to each codeword according to the rejection sampling are equivalent to a threshold-basee assignment.
Rd: CFT21 == (PPRG(m)
Shared randomness When M I d ++11 1, additional randomization is required during codebook generation to achieve an unbiased scheme, as discussed in [33] Furthermore, both the encoder and decoder must possess this randomization information. In the proposed RRSC scheme, this randomization is achieved through the random rotation of the simplex code using shared randomness. However, it is possible to eircumvent the need for shared randomness by having the server generate random rotation matrices using its private coin and communicate them to the users. This approach replaces shared randomness with downlink communication, which typically more affordable than uplink communication. It should be noted that directly transmitting the rotation matrices would require (dd) bits. Nonetheless, the server can generate them using a predetermined pseudo-random generator (PRG) and transmit only the seeds of it to the users. Drawing from a similar argument as in [2], assuming the existence of exponentially strong PRGs, seeds with polylog (d) bits are sufficient.
Future Work We showed the exact-optimality of k-closest encoding for the rotating sim- plex codebook. In general, it also achieves unbiasedness and the following error formulation EPOM Σ m= Qy(m/u, U 1l implies the exact-optimality of k-closest encoding for any rotationally symmetric codebook, which leads us to the following conjecture.
Conjecture 5.1. The proposed k-closest encoding is exact-optimal for any rotationally symmetric codebook.
also remains unclear whether ls can depend on the realization the codebook U in general, which we leave to future work. We also proved that the exact-optimal codebook must be rotationally symmetrie. We conjecture that the maximally separated codebook (simplex codebook) is exact- optimal it provides the most effective coverage of the space Sd-1 This, too, is left as topic for future work.
Conjecture 5.2. The rotationally symmetric simplex codebook the exact-optimal codebook.
Limitations and Broader Impact While we take an important step towards exact optimality by proving several necessary conditions and by providing mechanism that is exact-optimal for family of codebooks, we still have the above conjectures left to be proven in future work.
6 Acknowledgement
The authors would like thank Peter Kairouz for the helpful discussions in the early stage of this work; and Hilal Asi, Vitaly Feldman, and Kunal Talwar for sharing their implementation for the PrivUnitG mechanism (2). BI was supported by a Stanford Graduate Fellowship, Google PhD Fellowship, and a Meta research grant. WNC was supported by NSF under Grant CCF-2213223. AN was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2021R FIIIII1115996
References
[1] N. Agarwal, A. T. Suresh, F. X. X. Yu, S. Kumar, and B. McMahan. cpsgd: Communication efficient and petrrentiallypprvaat distributed sgd. Advances Neural Information Processing Systems, 31, 2018
[2] H. Asi, V. Feldman, and K. Talwar. Optimal algorithms for mean estimation under local differential privacy. In International Conference on Machine Learning, pages 1046-1056. PMLR, 2022.
10

---

[3] L. P. Barnes, H. A. Inan, B. Isik, and A. Özgür. rtop-k: A statistical estimation approach to distributed sgd. IEEE Journal on Selected Areas in Information Theory, 1(3):897-007, 2020.
[4] A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers. Protection against recon- struction and its applications in private federated learning. arXiv preprint 2018.
[5] S. Chatterjee and P. Diaconis. The sample size required in importance sampling. The Annals of Applied Probability, 28(2):1099-1133 2018.
[6] W.-N. Chen, P. Kairouz, and A. Ozgur. Breaking the conmunicaaoon--pivvyy-aaammmmm trilemma. Advances in Neural Information Processing Systems, 33:3312 -3:3312-3324, 2020.
[7] J. Duchi and R. Rogers. Lower bounds for locally private estimation via communication complexity. In Conference on Learning Theory, pages 1161-1191. PMLR, 2019.
[8] J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 229-438. IEEE, 2013.
[9] Duchi, M. Jordan, and M. Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 1 113(521): 182-201, 2018.
[10] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
[11] V. Feldman, J. Nelson, H. Nguyen, and K. Talwar. Private frequency estimation via projective geometry. In International Conference Machine Learning, pages 14118-433.. PMLR, 2022.
[12] V. Feldman and K. Talwar. Lossless compression of efficient private local randomizers. In International Conference on Machine Learning, pages 3208-3210 PMLR, 2021.
[13] V. Gandikota, D. Kane, K. Maity, and A. Mazumdar. vqsgd: Vector quantized stochastic gradient descent. In International Conference on Artificial Intelligence and Statistics, pages PMLR, 2021.
[14] S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013.
[15] M. Havasi, R. Peharz, and J. M. Hernández-Lobato. Minimal random code learning: Get- ting bits back from compressed model parameters. In International Conference on Learning Representations, 2019.
[16] Z. Huang, Y. Liang, and K. Yi. Instance-optimal mean estimation under differential privacy. Advances in Neural Information Processing Systems, 34:25993-26004, 2021.
[17] B. Isik, F. Pase, D. Gunduz, S. Koyejo, T. Weissman, and M. Zorzi. Communication-effiiientn federated learning through importance sampling. arXiv preprint arXiv:2306. /2625, 2023.
[18] B. Isik, F. Pase, D. Gunduz, T. Weissman, and Z. Michele. Sparse random networks for communication-effee
federated learning. In The Eleventh International Conference on Learning Representations, 2023.
[19] B. Isik and T. Weissman. Learning under storage and privacy constraints. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 1844-1849. IEFF, 2022.
[20] B. Isik and T. Weissman. Lossy compression of noisy data for private and data-efficient learning. IEEE Journal on Selected Areas in Information Theory, 2023.
[21] B. Isik, T. Weissman, and A. No. An information-theoretie justification for model pruning. In International Conference on Artificial Intelligence and Statistics, pages 3821-3846. PMLR, 2022.

---

[22] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems federated learning. Foundations and Trends in Machine Learning, 14(1-2):1-210, 2021.
[23] B. Kashin. Section of some finite-dimensional sets and classes of smooth functions (in russian)
izv. Acad. Nauk. SSSR,
1977.
[24] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova,, and A. Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-888 826, 2011.
[25] Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492, 2016.
[26] Y. Lin, S. Han, H. Mao, Y. Wang, and Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In International Conference on Learning Representations, 2018.
[27] Y. Lyubarski and R. Vershynin. Uncertainty principles and vector quantization. IEEE Transac- tions on Information Theory, 56(7):3491-3300 2010.
[28] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication-efficienn learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[29] T. Nguyên, X. Xiao, Y. Yang, C. Hui, H. Shin, and Shin. Collecting and analyzing data from smart device users with local differential privacy. arXiv preprint arXiv:/606.0550 2016.
[30] A. Shah, W.-N. Chen, J. Balle, P. Kairouz, and L.. Theis. Optimal compression of locally differentially private mechanisms, In International Conference on Artificial Intelligence and Statistics, pages 7680-7723, PMLR, 2022.
[31] A. T. Suresh, X. Y. Felix, S. Kumar, and H. B. McMahan. Distributed mean estimation with limited communication. In International conference on machine learning, pages 3329-3337. PMLR, 2017.
[32] A. T. Suresh, 7. Sun, J. Ro, and F. Yu. Correlated quantization for distributed mean estimation and optimization. In International Conference on Machine Learning, pages 20876. PMLR, 2022.
[33] S. Vargaftik, B. Basat, Portnoy, G. Mendelson, Y. B. Itzhak, and M. Mitzenmacher. Eden: Communication-efiicien and robust distributed mean estimation for federated learning. In International Conference on Machine Learning, pages 21984 22014. PMLR, 2022.
[34] S. Vargaftik, R. Ben- can-Basat, A. Portnoy, G. Mendelson, Y. Ben-Itzhak, and M. Mitzenmacher. Drive: One-bit distributed mean estimation. Advances in Neural Information Processing Systems, 34:362-377, 2021.
[35] T. Wang, J. Zhao, X. Yang, and X. Ren. Locally differentially private data collection and analysis. arXiv preprint arXiv:1906.0/1 2019.
[36] S. L. Warner. Randomized response: survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63 0906666669-166 1965.
[37] W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Y. Chen, and H. L.. Terngrad: Ternary gradients to reduce communication distributed deep learning. Advances in neural information processing systems, 30, 2017.
[38] Y. Zhang. J. Duchi. M. I. Jordan, and M. J. Wainwright. innommation-theorette lower bounds for distributed statistical estimation with communication constraints. Advances in Neural Information Processing Systems, 26, 2013.
[39] Y. Zhang, M. Wainwright, and J. C. Duchi. Communication-efficeent algorithms for statistical optimization. Advances in neural information processing systems, 25, 2012.
12

---

A Proof of Lemma 3.1
Proof. For n-user mean estimation protocol (f, A, Pys),, following the notation and steps from 2
Proof of Lemma 3.1], we define the marginalized output
[m,,, Ug; = [m 1,ر Jys
[nA(mm,; Uد}}=ز) fi(U,, U4) = my Us, omii]
(35)
Then, we define the user-specific decoder by averaging gi(m;, U2; un) with respect to i.i.d. uniform P
ge (e U.) Egnitt Past ( (m,, U])"")]
(36)
where gn\ié indicates the vn vector except Ug. Due to the symmetry of Punit. it is clear that gi is unbiased. We also define
Rgillug. mj, U,}i)))) P
nA(tm,, U3}3=1
Σ os j=1
Uy
(37)
Consider average error where 01 ......, U/
drawn ii.. uniformly on the sphere 1d-1
myyy.my.UBB U,
| Uy}p=1) - EE /3
= =B(yy,m,
my, ال)سكررر1
(38)
= -,,
Ren-I((U), my U,}ر=و) - + Ren- my 0,}コ=
(39)
=B,
Rn ((Uj.
U,} U,
R
+ tu
(40)
E B(ry,my
Rgi(feg. U, R U, U,}$
(41)
E B Ui
[eoy, m,, U,};=)) R U,}
(42)
Em [1ss(mm U.) =ill
(43)
Then, need to show the same inequality for the worst-case error.
sup E (m.
4/
21 Pi Dn
==1
E (ys.
In([fm,UUH3)
4/
(44)
E Eu. U.
[laa Us) us113]
(45)
Σ
sup Em,,, [lliimm, U.) 2a113]
(46)
2m1
#2
13

---

where the last equality (46) is from Lemma 3.2 Lemma 3.4 and Lemma 3.5 decoder achieves lower MSE:
Thus, the user-specific
1
(f,
Err 9is Po.).
(47)
Since we keep random encoder J3 the same, the canonical protocol with also satisfies s-LDP constraint. This concludes the proof.
B Proof of Lemma 3.2
Proof. Let Um = [m, U') for all 1 S I M. Without loss of generality g(-, U) is one- one-to-one, i.e. {u: imm gm, u) for all m) has at most one element (with probability 1), and g (ū is well-defined. Then, we define randomizer fo(e, (M) that satisfies
2 (mlu, u, a M = (
(48)
It is clear that fo satisfies E- E-LDP constraint. Then,
Do,, g" .PM)) -Ejo.Pos ||lat (fole, UM), (.M) u113
(49)
-EpoNs
EM 2s (m/u, [10 m113]
(50)
-EG.Po EM Qf(mlu, (llo U) =1|
(51)
-Eg,Po [Il)(f(,U)),U) w/|3]
(52)
=D(,, f,9, Pu).
(53)
We also need to show that the composition of the new randomizer fo and selector g is unbiased.
EpnN (9t (fo(e, (M),MM)
= -Eso EM Q (mlu, Ú. Úm
(54)
=Bj,ro Em= @5(mlu, U)g(m.
(55)
=E,,po (o([(,,U),U)
(56)
=v.
(57)
Finally, (. ūM is valid transition probability, since
M
(mlu, i
Σ
Qr(mlu, (
(58)
for MM This concludes the proof.
C Proof of Lemma 3,4
Proof. Let A be a uniformly random orthogonal matrix and UM = ATUM We further let fi be randomized encoder that satisfies
On (mlv, UM) EA A0
(59)
Then, Q,; valid probability since
M
M Σ A0 1.
Qn (m/v, U. EA
(60)
Also, we have
2n UM)
EA Ar, AU
(61)
Qi (mle', (J))
EA (0 (U [1
14

---

EA [e=Q] Qm) AU MOM
(62)
E [Q5(m) AU AUMM
=ca
(63)
Finally, we need to check unbiasedness.
Ergu (mlo, U M [m]
= EAP PuM
Em= Q5(m|Ar, (TTM))m
(64)
Em= Qy(m|Au, UM ATTU
-EA. Paas
(65)
-EA [ATEPUM
EM (m UM
(66)
EA (ATAr)
(67)
=V
(68)
The key step that the original encoder f unbiased, which implies
EPAM
Σ EM
(m/mAu )m]] = AA
(69)
for all A.
Now, we are ready to prove the main inequality. Eri(f, = sup D(e, f, PUM)
(70)
EEA [D(Au, f, PPP
(71)
=EA [RPON
E 0m U. UM JImm - Aull]]
(72)
-Epum A EM Q)(m))m Av, AU )10m -ulp]]
(73)
-EPos
EM EA (m Av, A M | m1[3]
(74)
-EPos
EM Qn (mlu, I - =112
(75)
=D(v, fI, Pou).
(76)
for all v. This concludes the proof.
D Proof of Lemma
Proof. For v, v' E gd-1 let Ao be an orthonormal matrix such that o' = Agv. Let fz be a randomized encoder such that
f2 UM = fAv, AU:)
(77)
for uniform random orthonormal matrix. Then,
Q (m/c, UM EA [Q)(m|Ar, Ae, AUM)].
(78)
Similar the previous proofs, Q/2 well-defined probability distribution, and f2 is unbiased as well as s-LDP. Since Pr:m is rotationally symmetric and fz is also randomized via the uniform random orthogonal matrix, we have
D(o', f2, Pras)= = D(Age, f2, PoM) = D(v, f2, PoM). Compared to given randomizer f. we have
(79)
Err(f, Ptsr) ZEA [D(Av, f, PWM))
(80)
Σ M
UM [2] m== Qf(m|Av, U Q AU
(81)
Dm=1
M Qp(m|Av, U. )||u 11 1
(82)
-EA,PoM
Dmmi
Qr(m|Ar,
(2
(83)
-EP,M
ΣM
EA [m/ (1) AU B4l00/mmA444
(84)
=D(v, f2, PUM)
(85)
for all u E 8d-1, This concludes the proof.
15

---

E Proof of Theorem 3.6
Proof. The rotationally symmetric simplex codebook with normalization constant is (rAst..... r Let f be the unbiased encoder satisfying s-LDP. Let Qmax max ( u, rAs and Qmin = min Q, (m|o,, AA ) our objective is to demonstrate that Qmax is less than or equal to e mmi- We will employ a proof by contradiction to establish this. Suppose A1
Qj A > ef (m)
r A2) for some 11 V1, A1, m22 U2, and A2. Let Á be the row switching matrix where r rAAism, r -rA11mm 8mz and vAAism r 8m1 then we have
Qy pn r. s = (mg rAAAs$
(86)
We further let an orthogonal matrix such that A A'AA = A2, then =Q A 'o. r A =Q A' A
Qy r AA, AA
(87)
(88)
If we let of A' A',, then
rAgs = =Qy(mile), )
(89)
>et (5Qg(my) U2 A1)
(90)
which contradicts the e-LDP constraint. For an unbiased encoder, the error is
M |I 10mm1320(m//) -1
EM 1l0m - 21122, (m/e,, Unr] = Epp
E
(91)
L
1.
(92)
Thus, need to find that minimizes the error.
On the other hand, the encoder needs to satisfy unbiasedness. Without loss of generality, we assume é1, then we need
EM (
EA
e1,
(93)
where the expectation is with respect to the random orthonormal matrix A. If we focus on the first index of the vector, then
r E. Σ aT (mmee,mmmm,, = 1,
(94)
where a = (a1..... aa) is the first row of A and has uniform distribution on the sphere Sd-1, Thus, it is clear that assigning higher probability (close to Q to the larger aT sm.
Qiax strictly smaller than e min: then we can always scale up the larger probabilities and scale down the lower probabilities to keep the probability sum to one (while decreasing the error). Hence, we can assume that Qmin = go and Qmax = go for some go > 0.
Now, let & be such that
-M - | 1)40 + qa + |Ale 90 1,
(95)
where is an intermediate value such that qi [go, e go]. Then, the optimal strategy is clear: assign ef go to [k -th closest codewords 8m 's (ii) assign qi to the [[k] + 1)-th closest codeword, and (iii) assign do to the remaining codewords. This implies that the k-closest coding is optimal. O
(i)
F Proof of Lemma 3.7
Proof. Following (28) with Um Asm and V e₁, we have
1
Tk ke + (M- k) (c..(e)
. 5m
16

---

c -
Th ke + (M k)
E
A 8m
m Earg maxe (fte) (e
-1.
By focusing on the first coordinate of the above equation and observing that (e1, AsM) (a, 8m) where a the first row of the rotation matrix A, we must have
Tk ke + (M k)
E Ba-unif(sed1)
Σ
(a, sm)
=1
(96)
(( tom (0,2))))
Note that since A is random orthogonal matrix drawn from the Haar measure on SO(d), is distributed uniformly the unit sphere $6-1 Next, observe that by definition,
M
M where 1M (1. .... 0) {0, 13dd (that is, (1M) (mggr)) }). Therefore,
m
(M 1) Cm VM(M- 1)
Mentries
M
(a, 8m)
MMM am
{a, 1m),
MM - 1)
and hence plugging in 96 yields
E (a-ini(($(r1))
Σ
{a sm)
ke + (M k))
Top, T (11a,11).... (
E -
M
k Σ a(taa))
=Tk ke + (M)
Pa-uni((Sd
M (a, lns)
(M
- =Tk ke + +M
M
V
M
anii
(())
where (1) ((j))) denotes the i-th largest entry of the first M coordinates of a and (2) the last equality holds since is uniformly distributed over 8d-1
G Proof of Lemma 3.8
Proof. First of all, observe that
En-uni((3d-1)
Eavunif(Be-1)
E
(x)
M af
Ban-unf((8--1)
b Sunif((ar
((8)
im
E Ea-unif(3e-) 1)
where (a) holds due to the spherical symmetry of Next, bound (i) and (ii) separately.
17

---

Claim G.1 (Bounding (i)). For any d 2 M >> 2, it holds that
M - 2 V
d-2 < E (
Σ
at
M
(97)
d-2
Proof of Claim G.1
Observe that when is distributed uniformly over S 1,, it holds that
Z
Zz
Z
(01, 42 "i..,.....aa!)
-
E
V>
27
> i= Z3
i=
i=1
where - B denotes A and B have the same distribution, and Z1. ..., Zo must have
iid.
~
NN,,, 1). As result,
M Σ
Σ Z
omunif (34-1)
2n 2u (0.11
E 21
E 2 + EV==+11 23
1=1
By Jensen's 's inequality, it holds that
M Z Σ E Z
E Zna N(011)
M
E
21
2n Htd N10,1)
2 23
F 7,7
1/
Σ - M+1 23
1 + E
7 7i.... ZM isd ((0.1)
Eis z
(b)
1
d-M
M-2
M 2
2
where (a) holds since x that Σ; 7? follows from x distribution and that the ratio of two independent x² random variables follows an F-distribution.
1/(1 + .r) is convex mapping for O, and (b) holds due to the fact
On the other hand, it also holds that
ΣM
ZZ
E Zi ZM U. (((.1)
1=1
\
Σ 1=1
2? + vd
>/=M+1 Z3
(a)
ΣM 2?
E
2 Zn 7y N(0011
1=1 27 + Ex=M41 23
Σ1= 23
E
7 Zn 7, N(011
-==1 2 + Ex=M+1 23
1
R
2,
B,
Znr
SM z
3 M 23
18

---

@VI
Σ 2 M+= Z,2
21 po Zox ((01))
d- M-
M d -2
where (a) holds since v- is concave, (b) holds since T+= is convex, and (c) again is due to the fact that the ratio of two independent x² random variables follows an F-distribution.
Claim G.2 (Bounding (ii)). As long as
k 2 400 log 10.
log (M/k) 2
10 nt log 9
it holds that
k klog A))
4k log M
I E (a (yg.....,y))unnni33
Σ
4(3)
$
(98)
24 log 2M
M
Proof of Claim G.2
We start by re-writing a':
(d) oo.....d''i d'r) -
Z1
Zz
ZM
EEM
Zi
V
V
Zi
VE
Zi
This yields that
Z(1)
Z(2)
Z(n)
(dn) (1)))))))))) d
VMM
M
z
M VEA
i-
Z3
VIM
MM
ZT
and hence
B( (onn 1)
Σ
d(a)
1
Σ
Z(0)
7
7:
(0..1
V
Σ
Zt
1=1
Upper bound. To upper bound the above, observe that
k
1
2 2M ZM
< KE 21 2..... 2M (((11.)
(1)
E 1= Z
V 1=
z?
Let & = {(r...., BM) EM 2 < M(1 - 7) where > 0 will be optimized later. Then it
holds that
Pr (81 se- 2672
(99)
On the other hand, the Borell-TIS inequality ensures
Pr (| EE' [zmi]] {} S 2e -
(100)
19

---

where Z, ~ (0, (in our case, o = 1). Since E [1n]] I V2 M, it holds that
Pr ((1) 2 22og M + {) 2e f
(111)
Therefore, define E2 = 2(1) 2 2 log M + { and we obtain
k
1
E
201
21 1 Ze 1 (0)10
i=
7
1=1
1
kE
(1))
21 2M.... N(0,1
M Σ
i=
Z
E1 E
sup
2(1)
Pr U8))
VE 1= ??
VEM
1== 2/
M
V2 log M +E
+ (e- (e-M5²14 + 2e -x=)) e))
M(1 7)
2log M + Vlo((M)
< k
+1 (e M/400 + 2/MM)
(M/40000
0.9.M. M
(kvlog M
M
where the last inequality holds by picking 7 = 0.1 and & vlog M.
Lower bound.
The analysis of the lower bound is more sophisticated. To begin with, let
Ex == ={122 (Z ZM)
M
=
Σ
z E
M(1 7)
denote the good event such that the denominator of our target is well-controlled, where 7 >> 0 Ogain will be optimized later. By the concentration of x" random variables, it holds that
Pr (E Se - (o-lo((1+)) + e- Mn² se Se= (1- (1-vi=a)7 +e- My² S 2c M²²
(101)
Next, lower bound Ei=1 Z(a)- we partition (71, 72, 7M) into & blocks B1, B2,... Bg where
each block contains at least N [M/k] samples: B, == [(j - N -1jj- N] for E IK 1]
and B₁ [M] \ i Define ((10 be the maximum samples in the j-th block: 2(1
maxie Z, Then, it is obvious that
Σ
Z
70)
(1)
j=1
To this end, we define E to be the good event that 90% of 700's 's are large enough (i.e., concentrated to the expectation):
(1)
& = =
v log N
log 100 }/1 > 0.9k
j [k]
2
n log2
Note that by the BorelI-TIS inequality, for any [k].
Mog N
Pr
7
$ $
2
2e =t"
(1)
log2
20

---

so setting ę log 100 implies Pr (
Vog
-(]
0.98. Since blocks are independent with
v log
each other, applying Hoeffding's s bound yields
Pr {&1} 2 Pr [Binom(k: 0.98) 0.9) =((0088)² 2 0.9,
when & 2 400 log 10 2 log 10/0.08².
Next, we define a "not-too-bad" event where Σ/=1
7(1) (1)
is not catastrophically small:
k
Eg
M
for some {> >> 0 to be optimized later. Observe that Eg holds with high probability:
k M
k
Pr
(82) Pr
2z
2
M
hh) 2 1 /2/2
where (a) holds since the each of the top-k values must be greater than times the average, and (b) holds due to the Hoeffding's bound on the sum of i.idd Gaussian variables.
Lastly, trivial bound implies that
inf
(1)
aERM-
Now, we ready to bound E
-i=1 200)
We begin by decomposing
21 21,...
BM N1111
VVN 2?
it into three parts:
Σ zi-i Zo
Σ ck
Z
& E
8
Nm
Z Zi...,, 72. A ((0.1)
V Σラn M -= 2?
M 2z
Σ k Z
& E
&
ΣM 7z
Σ 1i=1 Z(e)
Pr (
Eg
U
Σ i=1
z
We bound these three terms separately. To bound the first one, observe that condition E n Eg. Nog k VM 7. As result,
Σ Z(n z
2 (1)
2 0.9k
1og
Σ i-i Z
Pr &
E, E N
i=1 z?
0.9k
log N
log / ?
(1 0.1 +e -62/2 2e
2e 2M My214)
(102)
VM(1 +))
To bound the second term, observe that under Eg,
k
Z 2
v VM
21

---

so we have
Σ 201
e E E
E2 Ei n MMM
1 Σラ i= 2?
2 Pr((EnggEEM)
(M2 (1
(-vARtL 1M -77
2 (rf
Evk
2 0.1
(103)
VM2(1- -7)
For the third term, it holds that
Σ Z(0)
Pr (r U ) E
Eg U U
L E x== z?
2 (r &
inf
Σ
((1)
0EBM-1
1=1
2 - Pr (E) U }
VM
(e /2 +
/////)
k
(104)
VM
Combining 102
1103, and [104
together, we arrive at
= Z
E
Z Za 1A N(O.1)
Σ 1= z?
0.9h
& log
VMV
(1- 0.1
(0.1
e- -8/2
+
2e 20e--MPP1)) - 0.1
(VMP(1-7)
5Vk
/M + +,)
122 1/2 +e- --M²114)
k
VM
Finally, setting 7 0
and & O(1) yields the desired lower bound
VM
Ca.M. = k log N
M
H Additional Experimental Results
In Figure 2
we provide additional empirical results by sweeping the number of users n from 2, 000 to 10, 000 the left and sweeping the dimension d from 200 to 1, 000 on the right.
I Additional Details on Prior LDP Schemes
For completeness, we provide additional details on prior LDP mean estimation schemes in this section, including PrivUnit 4. SQKR (6), FT21 [12]. and MMRC [30. We skip prior work analyzing caapression--pivacy-ttii tradeoffs that do not specifically focus on the distributed mean estimation problem [19] 20 others that study frequency estimation 6 30).
22

---

0.700
63000
(ours)
0122
SOKR
0.100
MMRC
0073
PrivunitG
6023
0025
0000
0.00
2000
6000
2000
7000
35300
19000
1U000
-012 4000
8833
350
1003
Figure 2: Comparison of RRSC with SQKR 6 MMRC [30, and PrivUnitG [2] (left) &g error vs
number of users with d 500, 6, and the number of bits is b = 6. A for each (right) & error vs dimension for n 5000, = 6, and the number of bits b = E = 6. k = 1 for for each d.
L.1 PrivUnit
2 considered the mean estimation problem under DP constraint (without communication constraint) when 2' = Sd-1 = {u E R || = 1]. Since there is no communication constraint, they assumed
canonical protocol where the random encoder f: S + Rd and the decoder is simple additive aggregator
(f((
Σ f(u)).
The authors showed that PrivUnit is an exact optimal among the family of unbiased locally private procedures.
Recall that given an input vector u E gá-1, the local randomized PrivUnit(p.g) q) has the following distribution up to normalization:
PrivUnit(p, ④) ~
22) v) 2 [2 v) < w.p. 1 -pp
w.p. P
where Z has uniform distribution on sd-1 Let S,, be the surface area of hypersphere cap {= E 8d-1 v) 7). with S-1 representing the surface area of the d dimensional hypersphere. We denoted y= Pr Z7 S 7 = (S-1 S-)/S-1 (convention from required to obtain unbiasedness.
The normalization factor
(2] also introduced PrivUnitG, which is Gaussian approximation of PrivUnit. this approach, Z is sampled from an i.i.d. (0, 1/d) distribution. This simplifies the process of determining more accurate parameters p, q, and 7. Consequently, in practical applications, PrivUnitG surpasses PrivUnit in performance owing to superior parameter optimization.
I.2 SQKR
Next, we outline the encoder and decoder of SQKR in this section. The encoding function mainly consists three steps: (1) computing Kashin's 's representation, (2) quantization, and (3) sampling and privatization.
Compute Kashin's representation A tight frame is set of vectors {u)} E Rd that satisfy
Parseval's identity, i.c. ||e112 = Ey (u,,0) o)² for all v E Rd. We say that the expansion =
ΣN ayty is a Kashin's representation of x at level if max, layl S VN ||ullz 23 shows that if N > (1 + n1) d for some μ. 0, then there exists tight frame {ug} such that for any x E Rd, one can find a Kashin's representation level K @11). This implies that we can represent the local vector with coefficients {a, {ر,} E [-c/vd c/ V for some constants c and N (d).
23

---

Quantization In the quantization step, each client quantizes each aj into 1-bit message e -c//Vd, c/ Vd with E [ = aj. This yields an unbiased estimator of {az 1 which can be described in N = (d) bits. Moreover, due to the small range of each Oj, the variance of is bounded by (11/d).
Sampling and privatization To further reduce {qp} to k = min( b) bits, client i draws independent samples from {9/}ー= with the help of shared randomness, and privatizes its &o bits message via 2 2RRRR mechanism 36]. yielding the final privatized report of bits, which it sends to the server.
Upon receiving the report from client i, the server can construct unbiased estimators âj for each {ay) and hence reconstruct 0 = Σソ= âzıly, which yields an unbiased estimator of v. In [6, it shown that the variance of è can be controlled by O (d/ min (c? b,,)..
1.3
FT21 and MMRC 30
Both FT21 and MMRC aim to simulate a given s-LDP scheme. More concretely, consider an s-LDP mechanism q(-lv) that we wish compress, which in our case, PrivUnit. tt. number of candidates
u1. ... UN are drawn from a fixed reference distribution p(u) (known to both the client and the server), which in our case, uniform distribution on the sphere gd-1, Under FT21 12], these candidates generated from (exponentially strong) PRG, with seed length & = polylog d). The client then performs rejection sampling and sends the seed of the sampled candidates to the server. See Algorithm for an illustration.
Algorithm 2 Simulating LDP mechanisms via rejection sampling [12]
Inputs: e-LDP mechanism g(-lo), ref. distribution p(-), seeded PRG G: 10, + {0, 13', failure
probability 7 >> 0. J= In(1/7).
for j E {1.-... .J do
Sample random seed (0.1)- 1)
Draw u + p(-) using the PRG G and the random seed s.
Sample 6 from Bernoulli g(ulo)
et-p(u)
if b 1 then BREAK end if end for Output:
On the other hand, under MRC [30] the LDP mechanism simulated via minimal random coding technique [15]. Specifically, the candidates are generated via shared randomness, and the client performs an importance sampling and sends the index the sampled one to the server, as illustrated in Algorithm It can be shown that when the target mechanism is E-LPP, the communication costs of both strategies are ((E) bits. It is also worth noting that both strategies will incur some bias (though the bias can be made exponentially small as increases the communication cost), and [30] provides a way to correct the bias when the target mechanism is PrivUnit (or general cap-based mechanisms).
24

---

Algorithm 3 Simulating LDP mechanisms via importance sampling (30]
Inputs: e-LDP mechanism q(-le), ref. distribution p(-), candidates M Draw samples u1.... us from p(u) using the shared source of randomness. for Ie E (1,... .M do w=)k) + (ttllw)pp(us)))
end for
TMRC(-) - w(.)/ w(k).
Draw kM TMRC.
Output: k*
25


Reviews:
[{"review_id": "jPy1KrzvhZ", "reviewer": "Reviewer_69ED", "summary": "This work considers the problem of distributed mean estimation and aims to obtain \"exact optimal\" estimators under communication, (local) differential privacy and utility constraints. Exact optimality here means that instead of focusing on the order of complexity, the focus is also on the constants as well. Prior work either focused on \"order optimality\" or were exactly optimal for privacy and utility but only order optimal [Feldman-Talwar'11], [Shah-Chen-Balle-Kairouz-Theis'22]. This work achieves exact optimality through a k-closest encoding and a randomly generated codebook shared between the server and users.\n\n", "questions": "I think part of the paragraph **unified framework** in the discussion section could be mentioned in the related work section as well.\n\nAs mentioned in the previous section a main theorem that clearly states the trade offs this work obtain for mean estimation should be included. The score currently given is assuming that such a theorem will be included.", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "They obtain exact optimality for privacy-utility-communication tradeoffs of mean estimation under l_2 norm error. This improves upon prior work that could only obtain order optimality or exact optimality but only for some parameters. \n\nTheir work unifies the framework that existed in prior work [Feldman-Talwar'11], [Shah-Chen-Balle-Kairouz-Theis'22].\n\nTheir experiments show significant improvement in communication budget required compared to the previous work, especially in the setting where the number of bits is small.\n\nThe theorem regarding optimality of rotationally symmetric shared random codebooks could be of independent interest.", "weaknesses": "There is no \"main theorem\" that sums up the results in the main results section for mean estimation, and I think it's necessary to include such a theorem.\n\nI think exact optimality compared to order optimality is a more niche setting. That being said, that's not necessarily a weakness, and it could be impactful in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reading our manuscript and for providing constructive feedback to further improve it. Specifically, we are glad that the reviewer found the theoretical and empirical improvements over the existing order-optimal schemes impressive; and highlighted the significance of the rotational symmetry condition for the optimal codebook. Upon reviewer's suggestions, we will add the following theorems in the final manuscripts, which we think will improve the clarity of the results. Therefore, we thank the reviewer for these valuable suggestions.\n### **A main theorem that sums up the main results**\nIn the theorem below, we put together the main results in Section 3 that summarize the main theoretical contributions of our work. We will provide this theorem in the final manuscript.\n\n**Theorem 1:** *There exists a canonical protocol with a rotationally symmetric random codebook \nthat achieves the exact-optimal worst-case error among all unbiased $\\ell_2$-mean estimation schemes \nunder $\\varepsilon$-local differential privacy (LDP) and $b$-bit constraint simultenously. Moreover, there exists a $k$ such that the $k$-closest encoding algorithm in Section 3.1 in the manuscript is the exact-optimum unbiased scheme for a rotationally symmetric simplex codebook under $\\varepsilon$-LDP and $b$-bit constraint. The optimal $k$ that achieves this exact optimality is found by minimizing $r_k$ in Eq. (30) since the error is $r_k^2-1$ (as shown in Eq. (90) in Appendix E) --- see Algorithm 1 in the attached pdf rebuttal for the precise description on how to find the optimal $k$.*\n\n### **A theorem that clearly states the communication-privacy-utility trade-offs**\nIn this work, we show compelling evidence that our proposed scheme, Randomly Rotating Simplex Coding (RRSC), achieves exact optimality. Upon the reviewer's suggestion, we also provide the theorem and its proof below that shows the order optimality (which is actually a weaker statement than the exact optimality result we show in the manuscript) of RRSC with a clear statement of the error.\n\n**Theorem 2:** *In the region of interest where $1 \\leq \\varepsilon \\leq b \\leq d$, RRSC($k^\\star$), i.e., RRSC with the optimal choice of k, achieves an error of $\\frac{1}{n} \\left ( (k^\\star)^2   (\\frac{e^{\\varepsilon} + 1 / q -1}{e^{\\varepsilon} -1} )^2 \\frac{M-1}{M} \\frac{1}{C_{k^\\star}^2} - 1 \\right)$, where $q=k^\\star/M<1$. This corresponds to an error that scales with $\\frac{d}{n}$ -- satisfying the order optimality.*\n\nThe rough proof is the following. As stated in Eq. (60) in Appendix E, the $\\ell_2$ error is $r_k^2-1$, where $r_k$ is precisely defined in Eq. (30). The rest of the proof follows from the fact that (1) the optimal $k^\\star$ which is found by minimizing $r_k$ (hence the error) satisfies $k^\\star = O(M)$ and (2) $C_{k^\\star}=O(k^\\star/\\sqrt{d})$. The algorithm to find the optimal $k$ is given in Algorithm 1 in the attached pdf, where we also provide a figure that justifies $k^\\star = O(M)$. We will include this theorem and its full proof in the final manuscript.\n### **The motivation to study exact optimality**\nAs the reviewer mentioned, there are already existing schemes that achieve order optimality, but it was unclear how much these schemes could be improved in the non-asymptotic regime and how far to the optimal the pre-constant of the estimation error is. It is worth noting that in many practical scenarios (such as federated learning and analytics), the constant factor of the estimation error does significantly affect the end-to-end performance. As a result, in this work, our goal is to bridge this gap by (1) specifying exact-optimality conditions, (2) proving the exact optimality of a novel scheme, and (3) demonstrating that there is indeed a non-trivial gap between this exact-optimal scheme and the previous order-optimal approaches. Therefore, we hope to convey to the community the fundamental limits of the distributed mean estimation problem under both privacy and communication constraints and provide a strong baseline for further studies. We are glad that the reviewer also finds this perspective valuable.\n### **Moving the unified framework discussion to the related work section**\nWe thank the reviewer for this suggestion. We agree that this discussion suits well to the related work section as well. In the final version of the manuscript, we will provide a high-level idea of how we unify the existing schemes in the related work section and give further details in the discussion after we cover the main results. \n\n--- \nWe again thank the reviewer for the careful reading of our manuscript and for providing valuable suggestions to improve it further. We will include the additional theorems in the final manuscript and will carry the part of the discussion on unifying the framework to the related work section as suggested by the reviewer. We hope that we addressed the reviewer's comments sufficiently. We are happy to discuss any remaining questions or concerns the reviewer may have. "}, {"review_id": "iadGkoBuhp", "reviewer": "Reviewer_FeU2", "summary": "This paper focuses on the problem of distributed mean estimation under local differential privacy (DP) and communication constraints, with shared randomness between users and the server. Previous works either achieve exact optimal mean squared error (MSE) using $O(d)$ bits or achieve order-optimal MSE with a large constant using $O(\\varepsilon)$ bits. In this paper, the authors aim to tackle the same problem under shared randomness, aiming for both exact optimal MSE and communication efficiency. The proposed solution approaches the problem as a lossy compression problem. The authors demonstrate that the optimal scheme can be represented by a codebook through random coding. Additionally, they establish that the exact-optimal codebook-generating distribution must be rotationally symmetric. Empirically, the authors demonstrate that the proposed methods outperform existing approaches.", "questions": "See weaknesses", "limitations": "The limitations are discussed. This paper does not have a negative societal impact", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper is very technical. The paper is clearly written and lays out its contributions succinctly. \n\n2. The proposed framework achieves exact optimality in terms of both MSE and communication efficiency.\n", "weaknesses": "It would be better if the authors could discuss why shared randomness is necessary to achieve exact optimality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time in reading our manuscript carefully and for providing positive feedback. We are glad that the reviewer found our contributions valuable and liked the organization and writing of the manuscript. We discuss their point on shared randomness below. \n\n### **Shared randomness**\nIn our Randomly Rotating Simplex Coding (RRSC) scheme, the shared randomness is used to generate random rotation matrices that will be necessary for both encoding and decoding. We note that shared randomness is actually necessary for *any unbiased mean estimation scheme* that compresses the $d$-dimensional vectors to less than $b=\\log d-2$ bits (or equivalently any unbiased mean estimation scheme that uses less than $M=2^b=O(d)$ codewords) as shown in [1, Corollary~5.1]. We will add this clarification, together with the relevant reference, in the final version of the manuscript. \n\n[1] Chen, Kairouz, and Ozgur, \"Breaking the Communication-Privacy-Accuracy\nTrilemma\", IEEE Transaction on Information Theory, 2023.\n\n---\nWe again thank the reviewer for the careful reading of our manuscript and for asking an important clarifying question. We will include the above discussion on shared randomness in the final manuscript. We hope that we addressed the reviewer's point sufficiently. We are happy to discuss any remaining questions the reviewer may have. \n"}, {"review_id": "KrvOqG6jH5", "reviewer": "Reviewer_eu7R", "summary": "This paper studies the mean estimation problem under communication and local differential privacy constraints in the non-asymptotic (exact optimal) setting, and proposed a randomization mechanism that satisfies the identified necessary property of the exact optimality.", "questions": "For the choice of $k$, in the experiments are to minimize $C_k$ based on different $k$'s. How can such choice of $k$ guarantees the requirement in Theorem 3.6 (and its proof)?", "limitations": "Lack of intuition on k as described in weakness.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors proved a necessary condition that the codebook-generating distribution needs to be rotationally symmetric.\n\n2. The authors further proposed the first exact optimality algorithm Random Rotating Simplex Coding (RRSC) that matches the necessary condition.\n\n3. Empirical results in the paper showed that the proposed RRSC outperforms the state-of-art benchmarks (order-optimal) for the task.\n\n4. The authors proposed interesting conjectures and clear future directions based on the design and properties of the algorithm.", "weaknesses": "1. line 177, \"an random\" to \"a random\"\n\n2. The design of k-closest encoding and Theorem 3.6 (along with its proof in the Appendix) lacks the intuition on k, which seems to be valuable to explore both theoretically and empirically (as stated in the conjecture).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reading our manuscript and providing positive feedback on our contributions. Specifically, we are happy to see that the reviewer recognized our proposed algorithm, Random Rotating Simplex Coding (RRSC), as the first exact-optimal scheme for distribution mean estimation problem under privacy and communication constraints; appreciated the significant empirical improvements over the existing order-optimal schemes; and found the future directions and conjectures valuable to the community. The reviewer also raised some important questions that we would like to clarify below.\n### **The optimal choice of $k^\\star$**\nWe understand that it was not very clear how to select the right value for $k$ that satisfies the conditions in Theorem 3.6. We will try to elaborate on this here and will add this discussion in the final version of the manuscript as well. The optimal $k^\\star$ is the minimum achiever of Equation (30) that minimizes $r_k = \\frac{ke^\\epsilon + M-k}{e^\\epsilon-1} \\sqrt{\\frac{M-1}{M}}\\frac{1}{C_k},$\nsince the distortion is $r_k^2-1$ (as given in Eq (90) in the proof of Theorem 3.6. in Appendix E) -- i.e., the distortion is minimized if we minimize $r_k$.\n\nIn practice, to address the optimization problem outlined above, an approximation of $C_k$ is necessary,  defined as the anticipated sum of the top-$k$ coordinates of a uniformly random vector $a\\in\\mathbb{S}^{d-1}$. For every value of $k$, we can effectively estimate $C_k$ by obtaining a sufficient number of samples of uniform random vectors $\\{a_i\\}$.Then, we calculate the average of the sum of the top-$k$ components for each individual vector $a_i$. Given this efficient approximation of $C_k$ for $k$, the algorithm we provide in the pdf rebuttal file (Algorithm 1) finds $k^\\star$ that minimizes the $r_k$. We also provide a plot of the optimal $k^\\star$ (found by Algorithm 1 in the attached pdf) as a function of $M$ for a combination of parameters in Figure 1 of the attached pdf. \n\nIn the final version of the manuscript, we will add this algorithm to show the precise procedure to find the optimal $k^\\star$ value. We thank the reviewer for pointing out the unclarity around the choice of $k^\\star$.\n### **Intuition on $k$**\nThe intuition on the choice of $k$ can be developed from PrivUnit [1] -- the exact-optimal scheme for the same problem without the communication constraint. For a specific private vector $v\\in\\mathbb{S}^{d-1}$, PrivUnit assigns a higher probability to vector $w$\nthat is near $v$, i.e.,  to the vector $w$ that satisfies $\\langle v, w\\rangle > \\tau$ for some chosen threshold $\\tau$. In a similar fashion, our suggested scheme, Random Rotating Simplex Coding (RRSC), assigns a higher probability to the $k$-nearest codewords. The parameter $k$ in our scheme essentially corresponds to a threshold $\\tau$ in PrivUnit.\n\nIn our previous response above, we have explicitly stated that we find the optimal value $k^\\star$ by choosing $k$ that minimizes $r_k$,\nas described in equation (30). To identify such a $k^\\star$, we must be capable of calculating $C_k$ for each $k$, a task that can be carried out simply and efficiently through Monte Carlo methods as described above and in Algorithm 1 in the attached rebuttal in pdf format. We also would like to note that estimating the optimal $k^\\star$ in RRSC is significantly more straightforward and efficient \nthan estimating the optimal parameters in PrivUnit.\n\n[1] A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers. Protection against reconstruction and its applications in private federated learning. arXiv preprint arXiv:1812.00984, 335 2018.\n### **A typo on line 177**\nWe sincerely thank the reviewer for the careful reading of our manuscript. We will fix the typo (\"an random\") on line 177 to \"a random\".\n\n---\nWe thank the reviewer for the careful reading of our manuscript and for pointing us to the unclear parts of the proposed scheme. We hope we have addressed the reviewer's comments, and we will add the necessary discussions in the final version of the manuscript, which we believe will improve the manuscript. We are happy to discuss any remaining questions or concerns the reviewer may have."}, {"review_id": "UNei8Ff8Xm", "reviewer": "Reviewer_jPit", "summary": "The paper studies the distributed mean estimation (DME) problem with communication & privacy constraints.  The goal is to construct an unbiased estimate of a unit vector $v$ using $b$-bits that minimizes the mean squared error and provides $\\epsilon$-LDP. It is well known that any scheme achieving the above communication will have to quantize the unit sphere using $M=2^b$ points. Further, to achieve $\\epsilon$-LDP, a particular quantization point is chosen and returned according to an appropriate distribution. \n\nThe main contribution of this work is characterizing DME schemes that achieve optimal error in the presence of a communication budget and privacy constraints. The authors show that a random set of points generated using a rotationally symmetric distribution will achieve the optimal error. The intuition is that such a point set will be maximally separated and will most efficiently cover the sphere. $\\epsilon$-LDP is achieved using a randomized response mechanism. ", "questions": "1) As mentioned in the paper, the prior works of SQKR, MMRC, and FT21 can be seen as specific instantiations of random codebooks. Could it be possible that their schemes are exact-optimal as well and satisfy the conditions mentioned in this work? While a discussion is provided, can you comment on what condition is not met by each of these that confirms that they are not exact-optimal?\n\n2) Line 217-220 leading to Eq 29 needs further justification. Intuitively, this holds if the k points are equidistant, but I am not sure why the k-nearest neighbors will give an unbiased estimate. In the current manuscript, this is just a statement and not a formal proof of the fact that \"k-closest encoding consistently yields an unbiased scheme for any rotationally symmetric codebook.\" Further, it would be good to mention that for a rotationally symmetric codebook, the $\\sum_m U_m = 0$. \n\n3) Proof of Lemma 3.7 - What is top-k set? I am assuming it is the set of k-nearest neighbors to random a in s^M\nShould the summation have only $s_m$ and not $a^Ts_m $? \nTypo in eq 94 - the second summation should be over s_i.  \nEq 96 shows that you get an unbiased estimate of $e_1$ and not $a$. Also, other coordinates cannot be ignored. \n$r_k$ value is roughly $M$, so the error of the RRSC scheme will be $\\sim M^2$. So for $M = d$, there is an error of $d^2$ which is higher than the order optimal ones $(O(d/\\log d))$ for the same amount of allowed communication. A brief clarification on this would be great. \n\n4) For the shared randomness setup, will the server/nodes have to regenerate the codebook for each invocation of the algorithm? \n\n5) Some suggestions to improve the readability in my opinion would be: \n\n- Fix errors in proofs or provide better justifications\n- In Equation 26 the probability of choosing the k+1-th closest codeword is zero if k is an integer. This seems to be inconsistent with Algorithm 1, and the analysis that follows in Section 3.4\n- Clarify what the `=' in Def 3.3 means. It can be confusing to think that the two codebooks are equal (permutations of each other) rather than their distributions being identical. ", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Presents a DME scheme under exact communication constraints instead of asymptotic error bounds that are optimal. \n- The idea of treating the k-nearest codewords equally instead of just the closest seems to provide improvements over the prior works. This clean trick can be of independent interest. ", "weaknesses": "- The work provides sufficient conditions for a DME scheme to be optimal, i.e., an optimal scheme has a particular canonical setup. \nThese conditions are not necessary, and not all schemes satisfying the canonical setup achieve optimal error. \n\n- Either some proofs have (probably fixable) errors, or I have misunderstood. So at least rephrasing or an elaborate explanation is required. Details are provided in the next section (Questions)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reading our manuscript and providing positive and constructive feedback. The reviewer appreciated going beyond the asymptotic error bounds and found our k-nearest algorithm worthy of independent interest. The reviewer also asked clarifying questions, which we try to address below.\n### **Exact optimality conditions**\nThe reviewer is right that we show a sufficient condition as follows\n\"There exists an exact-optimal canonical scheme with rotationally symmetric codebook.\" We will revisit our abstract and discussion to reflect this more accurately.\n### **SQKR,FT21,MMRC**\nWhile it is clear from our experimental results that SQKR and MMRC fail to achieve exact optimality as RRSC significantly outperforms them, we now provide some intuitive reasoning why this is the case.\n\n**SQKR** produces a subset of indices $\\mathcal{I}$ from $\\lbrace1,2, \\dots, d \\rbrace$ with a size of $|\\mathcal{I}|=k$\nutilizing the shared randomness. Then, the codebook defined as  $\\lbrace\\sum_{i\\in \\mathcal{I}} a_i u_i: a_i=c/\\sqrt{d} \\mbox{ or } -c/\\sqrt{d} \\rbrace$ represents a tight frame for Kashin's representation. It is essential to recognize that the distribution generating the codebook is not rotationally symmetric; it is only permutation symmetric.\nMoreover, the codewords are not maximally separated. Thus, we strongly believe that the reason why SQKR does not reach exact optimality is that it does not generate maximally separated codewords.\n\n**FT21** aims to simulate the continuous PrivUnit scheme via pseudo-random generator (PRG) and rejection sampling. As FT21 operates without employing shared randomness, it requires a minimum communication cost of $\\Omega\\left(\\log d\\right)$ bits to attain an unbiased estimator. In addition, as we noted in the paper, the codebook associated with FT21 depends on the PRG it uses. Although the specific PRGs in FT21 are not explicitly outlined, we believe our simplex code would outperform codebooks that correspond to standard PRGs. For high communication budget (large b), codewords based on PRGs may offer computational efficiency, but our focus in this paper centers on scenarios with smaller or moderate values of b, and hence our approach can yield a better (non-asymptotical) MSE at a manageable computational cost.\n\n**MMRC** introduces an importance sampling approach where samples are drawn based on a uniform distribution across the sphere,\nsupplemented with a truncation technique. This is equivalent to producing i.i.d. codewords, which does not necessarily ensure maximal separation. We strongly believe that maximal separation of codewords, and hence the most effective coverage of the sphere, is important for exact optimality.\n### **Eq (29)**\nWe apologize for the confusion around lines 217-220. We try to clarify the step leading to Eq (29) here and will also revise it in the final manuscript. We note that in Eq (28), $\\mathbb{E}[\\sum_{m\\in T_k}U_m]$ can only have $e_1$ as the remaining component since we pick the k-closest codewords $U_m$ (i.e., $m\\in T_k$) and all directions other than $e_1$ are canceled out due to the rotational symmetry of the codewords. We hope this explanation clarifies the transition from Eq (28) to Eq (29). As suggested by the reviewer, we will clearly state in the final manuscript that $\\mathbb{E}[\\sum_m U_m]=0$ for all rotationally symmetric codebooks.\n### **Proof of Lemma 3.7**\nWe apologize for the confusion due to some typos. We will update the proof as follows. From (28), we want to find $r_k$ that satisfies $r_k \\times \\mathbb{E}[\\frac{e^\\epsilon-1}{ke^\\epsilon+M-k}\\sum_{m\\in T_k(e_1,U^M)}U_m]=e_1$, where $U_m=As_m$. The condition $m\\in T_k(e_1,U^M)$ implies that $<e_1,As_m>$ is one of the k-largest. Let $a_1^\\intercal$ be the first row of the matrix A. Since $s_m$ is a vertex of the simplex, $<e_1,As_m>=a_1^\\intercal s_m=\\sum_{i=1}^M a_{1,i} s_{m,i}=a_{1,m} \\sqrt{\\frac{M}{M-1}}-\\sum_{i=1}^M\\sqrt{\\frac{1}{M(M-1)}}a_{1,i}$. Since $\\sum_{i=1}^M \\sqrt{\\frac{1}{M(M-1)}}a_{1,i}$ is not a function of m, the condition $m \\in T_k(e_1,U^M)$ is equivalent to \"$a_{1,m}$ is top-k among $\\lbrace a_{1,i}\\rbrace_{i=1}^M$\". Also, due to the rotational symmetry, $\\mathbb{E}[\\sum_{i=1}^M \\sqrt{\\frac{1}{M(M-1)}}a_{1,i}]=0$. Thus, $r_k$ should satisfy $r_k \\times \\mathbb{E}[\\frac{e^\\epsilon-1}{ke^\\epsilon+M-k} \\sum_{m\\in top-k}a_{1,m}]=1$, where $m\\in$ top-k means that \"$a_{1,m}$ is top-k among $\\lbrace a_{1,i}\\rbrace_{i=1}^M$\".\n### **Order of $r_k$**\nSince the role of k is similar to that of the threshold in PrivUnit, the optimal choice of k grows with O(M). Please also see Figure 1 in the attached pdf, which demonstrates how the optimal k (found by Algorithm 1 in the attached pdf) changes with M. On the other hand, $C_k$ is an expected sum of top-k coordinates of the unit vector, which is roughly $O(k \\sqrt{1/d})$ for $k=O(M)$. Thus, unlike the reviewer's suspicion, $r_k$ **does not** scale with M; instead, it scales with $\\sqrt{d}$. We will emphasize this better in the final version.\n### **Non-Integer k**\nWe note that in Eq (26), if k is an integer, the probability of selecting k+1-th closest codeword is simply $1/(ke^\\varepsilon+M-k)$, which corresponds to the probability of the case \"otherwise\". The reason why we allowed k to be non-integer as well in Section 3.3 is to simplify the proof. In practice, however, both in Algorithm1 and in the experiments, we always pick an integer k. We also note that RRSC achieves impressive performance that matches PrivUnit even with an integer k.\n### **Clarification on the Notation**\nThe reviewer is indeed right that $\\stackrel{(d)}{=}$ implies that the distributions are identical, which we will clearly state in the final manuscript.\n\n---\nWe again thank the reviewer for carefully reading our manuscript and for providing positive feedback. We hope we have addressed all the questions. We are happy to engage in further discussion with the reviewer to resolve any remaining concerns."}, {"review_id": "1pJacehObI", "reviewer": "Reviewer_JsmV", "summary": "The authors consider the problem of high dimensional mean estimation with communication and privacy constraints. For federated learning or distributed SGD, model updates must be communicated to central server, but as models become much larger this can be a bottleneck within the computation. As a result, previous works has considered the setting in which there is a restriction on the number of bits that can be communicated, which the authors also follow. Furthermore, the authors consider the differentially private setting adding another constraint. This setting was also considered in previous work, some of which achieved optimality up to constant factors. The authors improve upon that work and achieve exact optimality and this theoretical improvement is backed by their empirical experiments.", "questions": "None", "limitations": "The authors adequately addressed the limitations", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Improves upon previous work for a reasonably well-studied problem and achieve optimal tradeoff between communication-privacy-utility and further show how the previous work are special cases in their method. ", "weaknesses": "Minor gripe that some of the notation could have been expanded upon more clearly (for example: P_U-almost) but can understand that page limits can add difficulty.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reading our manuscript and for providing positive and constructive feedback. We are glad that the reviewer acknowledged the improvements we provided over the prior order-optimal solutions and the importance of unifying the previous schemes under our exact-optimal solution. We also agree with the reviewer that some notations might need further clarification for some readers. We will provide more notational comments, e.g., $p$-almost means that it happens with probability 1 under measure $p$. We thank the reviewer for pointing out this. "}]

Author rebuttal:
We would like to thank all the reviewers for carefully reading our paper, and providing positive and constructive feedback to further improve it. All the reviewers seem to appreciate the technical contributions of the paper in studying the exact optimality of the distributed mean estimation problem under privacy and communication constraints. Specifically, all the reviewers found theoretical and empirical improvements over the existing order-optimal schemes worth praising. Moreover, Reviewer 69ED found one of our main results, namely, the exact optimality of the rotationally symmetric codebook, worthy of independent interest;  Reviewer FeU2 liked the clear and fluent presentation of the results and the organization of the manuscript; Reviewer eu7R highlighted that the proposed algorithm RRSC outperforms the state-of-the-art schemes and stressed the importance of the conjectures and future directions in the manuscript to the community; Reviewer jPit found the k-closest encoding algorithm, which we prove to be the exact-optimal approach for a simplex codebook, impressive, clean, and worthy of independent interest in general; and lastly Reviewer JsmV underlined the fact that previous order-optimal solutions can be viewed as special cases of the general setup we propose in this work -- namely the canonical protocol with rotationally symmetric codebook.

The reviewers also shared valuable suggestions that we believed improved the overall quality of our manuscript. We explain how we address them and how we will revise the manuscript in our separate responses to each reviewer below. We also submit another rebuttal file in pdf format to share an additional algorithm and a figure as part of our response to some comments.  


Meta-review: The paper studies distributed mean estimation in the local differential privacy model. The authors propose a near optimal method in terms of privacy-utility-communication tradeoff. While the previous work had established asymptotically tight bounds, the authors have made progress in achieving the optimal constants for this fundamental problem. 

The reviewers were all positive about this paper. The authors have adequately addressed the technical questions raised by the reviewers.
Decision: Accept (poster)