Unified Lower Bounds for Interactive High-dimensional Estimation under Information Constraints
Authors: Jayadev Acharya
Clement Louis Canonne
Ziteng Sun
Himanshu Tyagi
Venue: NeurIPS 2023 poster (2023)
Keywords: statistical estimation; interactivity; local differential privacy; communication constraint
TL;DR: We develop a new lower bound framework for statistical estimation under measurement or information constraints, letting us easily derive new and known minimax rates,

Abstract: We consider distributed parameter estimation using interactive protocols subject to local information constraints such as bandwidth limitations, local differential privacy, and restricted measurements. We provide a unified framework enabling us to derive a variety of (tight) minimax lower bounds for different parametric families of distributions, both continuous and discrete, under any $\ell_p$ loss. Our lower bound framework is versatile and yields “plug-and-play” bounds that are widely applicable to a large range of estimation problems, and, for the prototypical case of the Gaussian family, circumvents limitations of previous techniques. In particular, our approach recovers bounds obtained using data processing inequalities and Cramér–Rao bounds, two other alternative approaches for proving lower bounds in our setting of interest. Further, for the families considered, we complement our lower bounds with matching upper bounds.

Unified lower bounds for interactive high-dimensional estimation under information constraints
Jayadev Acharya Cornell University acharya@cornell. edu edu
Clément Canonne University of Sydney
cl ement. canonne @sydney. edu, au
Ziteng Sun Google Research, New York zitengsun@@oogle. com
Himanshu Tyagi
Indian Institute of Science, Bangalore htyagi @iisc.ac.
Abstract
We consider distributed parameter estimation using interactive protocols subject to local information constraints such bandwidth limitations, local differential privacy, and restricted measurements. to derive variety of (tight) minimax lower bounds for different parametric families of distributions, both continuous and discrete, under any l, loss. Our lower bound framework is versatile and yields "plug-and-play bounds that are widely applicable to a large range of estimation problems. In particular, our approach recovers bounds obtained using data processing inequalities and Cramér-Rao bounds, two other alternative approaches for proving lower bounds in our setting of interest. Further, for the families considered, complement lower bounds with matching upper bounds.
provide a unified framework enabling
Introduction
We consider the problem of parameter estimation under local information constraints, where the estimation algorithm has access to only limited information about each sample. These constraints can be of various types, including communication constraints, where each sample must be described using a few (e.g., constant number of) bits; (local) privacy constraints, where each sample is obtained from different user and the users seek to reveal little as possible about their specific data; as well as many others, e.g., noisy communication channels, or limited types of data access such as linear measurements. Such problems have received significant attention in recent years, motivated by applications such as data analytics in distributed systems and federated learning.
Our main focus is on the sample complexity) of these problems. Several recent works have provided bounds that apply to specific constraints work for specific parametric estimation problems, sometimes without allowing for interactive protocols. Indeed, handling interactive protocols technically challenging, and several results in prior work exhibit flaws in their analysis. In particular, the most basic Gaussian mean estimation problem using interactive communication remains, surprisingly, open.
lower bounds for the minimax enror rates (or, equivalently,
We present general, "plug-and- aaad-p lower bounds for parametric estimation under information constraints that can used for any local information constraint and allows for interactive protocols. Our abstract bound requires very simple (and natural) assumptions to hold for the underlying parametric family; in particular, we do not require technical "regularity" conditions that are common in asymptotic statistics.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

We apply our general bound to canonical problems of high- gigh-dimensional mean estimation and dis- tribution estimation, under privacy and communication constraints. for the entire family of lp loss functions for p 2 1. In addition, we provide complementary schemes that show that our lower bounds are tight for most settings of interest.
1.1 Our results
Our main contribution is general approach to establish lower bounds in distributed information- constrained parameter estimation. The setup is described in detail in Section 2 and is illustrated are generated from an unknown distribution p from a parametric family Pe = {po. A E )) of distributions. Only limited information Y, about datum X; is available to the algorithm. The goal is to estimate the underlying parameter 0 associated with p. Furthermore, we consider interactive estimation, wherein Y, can depend on ,,,.., -1 Our general lower bound, which we develop Section 3, takes the following form: Consider collection of distributions (p=)=e(-1,+1) C Pe contained in the parametric family. This collection represents a "difficult subproblem" that underlies the parametric estimation problem being considered; such constructions are often used when deriving information-theoree
in Fig. 1. In short, independent samples X"
lower bounds (e.g., in Assouad's s method [33]). Note that each coordinate of 2 represents, in essence, a different "direction" of uncertainty for the parameter space. The difficulty of the estimation problem can be related to the difficulty of determining a randomly chosen 2 (or most of the coordinates of 2), denoted Z, by observing samples from P.- Once Z is fixed, independent samples X" (X 1, X,,) are generated from P= and the limited information Y; about X, is passed to an estimator.
Our most general result, stated as Theorem 1, is an upper bound for the average discrepancy, an average distance quantity related to average probability of error in determining coordinates of Z by observing the limited information Y (Yi...., Yn). Our bounding term reflects the underlying information constraints using a quantity that captures how "aligned" we can make our information about the sample to the uncertainty in different coordinates of Z. Importantly, under minimal assumptions. In particular, in contrast to many previous works, our results do not require any "bounded ratio" assumption density function change by at most a constant factor if we modify one coordinate of 2. When we impose additional structure for pa such orthogonality of the random changes in density when we modify different coordinates of z and, more stringently, independence and subgaussianity of these changes- we get concrete bounds which are readily applicable different problems. These plug-and-pley bounds are stated as consequences of our main result in Theorem 2. The interested reader can also directly consider the applications local privacy (Corollary 1) or communication constraints (Corollary 2).
results hold
the collection =e=)
which would ask that the
We demonstrate the versatility of the framework by showing that it readily yields tight (and in some cases nearly tight) bounds for parameter estimation (both in the sparse and dense cases) for several fundamental families of continuous and discrete distributions, several families of information constraints such as communication and local differential privacy (LDP), and for the family of &, loss functions for p 2 1, all when interactive protocols are allowed. To complement our lower bounds, we provide algorithms (protocols) which attain the stated rates, thus establishing optimality of our results. We discuss these results in Section 5, where we provide the corresponding statements. In terms of the applications, our contributions are two-fold:
1. We obtain several results from a diverse set of prior works in a unified fashion as simple corollaries of our main result: As discussed further in Section 1.2, the lower bounds for mean estimation for product Bernoulli under & loss and those for estimation of discrete distributions under & and & losses, for both communication and LDP constraints, were known from previous work. However, our approach allows us to easily recover those results and extend them to arbitrary L, losses, with interaction allowed, in a unified fashion.
2. Our bounds also yield new lower bounds for some canonical problems. The prototypical example being mean estimation for nigh-dimensional Gaussian distributions under infor- mation constraints. As discussed in the next section, while some prior work claimed lower bounds for this problem, their arguments appear to be flawed at high level, due to the
'Up to logarithmic factor in the case of t.o loss, or, for some of our bounds, with a mild restriction on being large enough.
2

---

"bounded ratio" assumption their techniques rely on, which Gaussian distributions do not satisfy, and which our framework does not require. To the best of our knowledge our work is the first to obtain those lower bounds for interactive mean estimation of high-dimensional Gaussian distributions under communication or local privacy constraints.
1.2 Previous and related work
There a significant amount of work in the literature dedicated to parameter estimation under various constraints and settings. Here, we restrict our discussion to works that are most relevant to the current paper, with a focus on the interactive setting (either the sequential or blackboard model; see Section for definitions).
The work arguably closest to ours is the recent work [5], which focuses on density estimation and goodness-of-fft testing of discrete distributions, under the & metric, for sequentially interactive protocols under general local information constraints (including. as special cases, local privacy and communication constraints, as in the present paper). This work can be seen as a significant generalization of the techniques of [5], allowing us to obtain lower bounds for estimation a variety of settings, notably high-dimensional parameter estimation.
Among other works on high-dimensiona mean estimation under communication constraints, [17, 10] consider communication wat.uuuiicctooccoostainnee. Gaussian mean estimation in the blackboard communication model, under &g loss. The protocols for the upper bounds in these works do not require interactivity and are complemented with lower bounds which show that the bounds are tight up to constant factors in the dense case and up to logarithmic factors in the sparse case. However, the proof of the lower bound in [10] seems to present gap (specifically, in the truncation argument of [10, Theorem 4.3)), as confirmed in personal communication with the authors. Correcting the issue in the truncation argument would lead to result significantly weaker than the claimed lower bound, and it is unclear whether this can be fixed using the techniques from that paper.
In this work, we present interactive protocols for the sparse case which improve over the nonin- teractive protocols and strenghten the upper bounds by a logarithmic factor in the interactive case (see Remark 1). Further, using our general framework, we establish a mearly-matching lower bound for the problem, recovering the rate lower bound originally claimed in [10] up a logarithmic factor. In a slightly different setting, [26] considers the mean estimation problem for product Bernoulli distributions when the mean vector is 1-sparse, under & loss. The lower bound in [26], too, allows sequentially interactive protocols. In the blackboard communication model, [19] and [18] obtained tight bounds for mean estimation and density estimation under &2 and & loss, respectively.
Turning to local privacy, [23] provide upper bounds (as well as some partial lower bounds) for one- dimensional Gaussian mean estimation under LDP under the &g loss, in the sequentially interactive model. Recent works of [7] and [8] obtain lower bounds for mean estimation in the blackboard communication model and under LDP, respectively, for both Gaussian and product Bernoulli distribu- tions; as well as density estimation for discrete distributions. Their approach is based on the classic Cramér Rao bound and, as such, is tied inherently to the use of the & loss. recent independent work, [25] extended these methods to obtain lower bounds under general Ep loss under communication constraints, which are tight for Gaussian mean estimation under noninteractive protocols. [14], by developing locally private counterpart of some of the well-known information-theorett tools for establishing statistical lower bounds (namely, Le Cam, Fano, and Assouad), establish tight or nearly tight bounds for several mean estimation problems in the LDP setting.
More recently, drawing on machinery from the communication complexity literature, [13] develop a methodology for proving lower bounds under LDP constraints in the blackboard communication model. They obtain lower bounds for mean estimation of product Bernoulli distributions under general lp losses which match ours (in the high-privacy regime, i.e., small e). Similar to the results under communication constraints [17, 10], their approach relies heavily on the assumption that the distributions on each coordinate are independent, which fails to generalize to discrete distributions. Further, their bounds are tailored to the LDP constraints and do not seem to extend to arbitrary information constraints. Finally, while [13] also claims tight bounds for mean estimation of Gaussian and sparse Gaussian distributions under Eg loss, their argument invokes the analogous (flawed) result from [10] and thus it is unclear whether the stated lower bound can be shown using their techniques.
3

---

Finally, we mention that very recently, following the appearance of [5], an updated version of [19] appeared online as [21], which has similar results as ours for the high-dimensional mean estimation problem under communication constraints. Both our work and [21] build upon the framework presented for the discrete setting in [5]. Moreover, their work still need the "bounded ratio", and hence their lower bound for sparse Gaussian family only works for noninteractive protocols.
Notation. Hereafter, we write log and In for the binary and natural logarithms, respectively. For dis- tributions PI, P2 over X, denote their Kullback-Leibler divergence (in nats) by D(Pi [[2), and their
Hellinger distance by (Pr P2) ( f(V d - / d )² d'i2//2, where we assume pI, P2 < X for some underlying measure on X. Further, we denote the Shannon entropy of a random variable X by (X) and the mutual information between X and Y by I(X;; Y); we will sometimes write H (p)) for the entropy of random variable with distribution p. We refer the reader to [12] for details on these notions and their properties, which will be used throughout. Given two functions f.g, we write I S g there exists an absolute constant C > 0 such that ((x S Cg(æ) for all x;; and f x if ʃ S 9 and f ž g both hold. Finally, we use the standard asymptotic notation O()), S(S). @())
Organization. In Section 2, we formalize our setting of interactive inference under local information constraints. The general lower bound framework and results are presented in Section 3, where we provide implications of the general result under additional structures and specific information constraints such as local privacy (LDP) and communication constraints. Finally, we use our framework to readily derive lower bounds for a wide range of applications in Section 5. Due to space constraints, all proofs, as well as our upper bounds (algorithms) are provided in the Supplement, where we also discuss how our techniques compare with other existing approaches for proving lower bounds under information constraints, namely, those based on strong data processing inequalities (SDPI) or on the van Trees inequality.
2 The setup
We consider standard parametric estimation problems. For some θ C Rd let Pe (po, 0 E Q} be a family of distributions over some measurable space (x, namely each po is a distribution over ()) Suppose n independent samples X (X Xn) from an unknown pa E Pe are obtained. The goal in parametric estimation is to design estimators 0 xm - θ, and form estimates ((X²) of using independent samples X" from Pa. We illustrate our results using two specific distribution families: discrete probability mass functions (pmfs) and high-dimensional product distributions with unknown mean vectors. We will describe the precise minimax setting in detail later in this section.
We are interested in an information constttronn-ottttiinnede setting, where we do not have direct access to the samples X" from Po- Instead, we can only obtain limited information about each datapoint X; Following [3], we model these information constraints by specifying an allowed set of channels W with input alphabet X' and some output space y. Each sample X, is passed through a channel from W. chosen appropriately, and its output Y; is the observation we get. This setting is quite general and captures special cases the popular communication and privacy constraints, we will describe momentarily.
We now formally describe the setting, which is illustrated in Fig. 1. n i..dd samples X1..... X2 from an unknown distribution Рy E Pe are observed by players (users) where player t observes X,- Player t E [n] selects channel W, E W and sends the message Y, to referee, where Y, is drawn from the probability measure Wt( X,, Yi,..,,, The referee observes y (Vi..., Y.)) and seeks to estimate the parameter 0.
The freedom allowed in the choice of W. at the players gives rise to various communication protocols. We focus on interactive protocols, where channels are chosen by one player at a time, and they can use all previous messages to make this choice. We describe this class of protocols below, where we further allow each player t to have a different set of constraints W; (e.g., a different communication budget), and W, must be in We For simplicity of exposition, and as these already encapsulate most
Formalll, a channel is a Markov kernel W: ② x X' + [0, 1]. which we assume to be absolutely continuous with respect to some underlying measure μ on ()), D). When clear from the context, we will drop the reference the alagebrss X and D: in particular, in the case of finite X' or y.

---

X1
X
X3
Xn-2
Xn-1
Xn
W3
W
W
15
Yn-2
Y
Yn
Referce
output
Figure 1: The enformation-constrailee distributed model. In the interactive setting, W can depend on the previous messages .,,..., Y (dotted, upwards arrows).
of the difficulties, we focus here on the case of sequentially interactive protocols, which has been widely considered in the literature and captures many settings of interest. However, we emphasize that our results extend to the more general class of fully interactive protocols (see Supplement).
Definition 1 (Sequentially Interactive Protocols). Let XI.... X, be i.i.d. samples from pe. 0 E O. sequentially interactive protocol 11 using W = (W,.... W.) involves mutually independent random variables U, UI...., Un (independent of the input XI....,XX. Xx)) and mappings 9r (U, U2) - We E W2 for selecting the channel in round E [n). In round t. player uses the channel W, to produce the message (output) Y, according to the probability distribution Wi(- Xx. Yı..... Vi.....Yy-J. Y--1). The messages Y (Y,...., Y,) received by the referee and the public randomness (available to all players) constitute the transcript of the protocol II; the private randomness .1...., Un (where Ug is local to player !) is not part of the transcript. In other words, the channel at player as a (randomized) mapping W: X' y V/ which depends input X' and the previous messages y'11 E y outputs some E y.
For concreteness, we now instantiate this definition for the two aforementioned types of information constraints, communication and (local) privacy.
Communication constraints Let y = (0, 13" U (0, 13 For E 2 and & 2 1, let
W.commm.
(W:''>> + 10,
be the family of channels with input alphabet X' and output alphabet the set of all (-bit strings. This captures the constraint where the message from each player can be at most bits long, and corresponds to the choice W (Wrcomm.e_. ..... Wecom..e). Note that allowing different communication budget to each player can be done by setting W (Woomm,,61 ..... Wooom.,f.).
Local differential privacy constraints For e and 1, a channel W X' yt-1 is e-locally differentially private (LDP) [16, 15, 2f
W(S 21,3²=1) 1 W(S 12, S e Va1,22 E X.
sup sup SE
(2)
We denote by Wypriv,s the set of all e c-LDP channels. For sequentially interactive protocols, the c-LDP condition is captured by setting n = (Mypriv,s Wpriv.s). As before, one can allow different privacy parameters for each player by setting n (yppriv.s1 ,..., Wprrv..e.).
Finally, we formalize the interactive parametric estimation problem for the family po= (po, E @). We consider the problem of estimating 0 under t, loss. For [o), the lp distance between
5

---

1/p ( ii vz
u, R& is (,( ||u u||p
This definition extends in natural way
p = oo by taking the limit."
Definition 2 (Sequentially Interactive Estimates). Fix d E and p E [0, oo). Given a family Pe of distributions on X, with θ C _24, an estimate for Pe consists of a sequentially interactive protocol with transcript (Y'" U') and estimator 0: (Y U) + 0(Y",U) E O. The referee observes the transcript (Y"", U) and forms the estimate 8(Y",, U) of the unknown 6. Further, for n E and E 1), (II, 0) constitutes an (n, -estimaatr for Pe using W under ep loss if for every A E θ the transcript (Y", U)) of II satisfies
1/
Epp
Note that the expectation over the input X ~ P for the protocol Il and the randomness of 11.
3 Main result: The information contraction bound
Our main result is unified framework to bound the information revealed about the unknown 0 by the transcript of the messages obtained via the constraints defined by the channel family W. The framework is versatile and provides tight bounds for several families of continuous and discrete distributions, several families of information constraints such as communication and local differential privacy, and for the family of Ep loss functions for 2 1.
Our approach at high-level proceeds below: We first consider the "pertubation space" Z == +-1,+1}A for some suitable k. We associate with each z E a parameter 8₂ E O, and refer to po. simply as p=- These distributions are designed in way that the distance between 0₂ and 0.. is large when the Hamming distance between 2 and z' is large. With this, the difficulty of estimating A will be captured in the difficulty of estimating the associated This will make our approach compatible with the standard Assouad's method for deriving lower bounds (ef. [33]).
Then, we let Z (Zi,... Zx) be a random variable over Z. Under some assumptions the distribution of Z, we will bound the information between the individual Z,s and the transcript (Y", U) induced by family of channels W. Combining the two steps above provides desired lower bounds. Formally, let 2 = (-1, ) for some & and {p>}=ez (where P>- Po.) be a collection of distributions over X, indexed by E 2. For z E 2, denote by g E 2 the vector obtained by flipping the sign of the ith coordinate of z. To bound the information that can be obtained about the underlying = from the observations, we make the following assumptions:
with the
Assumption (Densities Exist). For every 2 Z and E [X] it holds that pooi < Pa. and there
exist measurable functions 62,4: X + R such that dp_ei = =1+ 22.1-
dp.
The functions dz.1 capture the change in density when the coordinate is flipped. In our applications below, we will have discrete distributions continuous densities, and the Radon-Nikodyn derivatives above can be replaced with the corresponding ratios between the pmfss and pdfs, respectively. Assumption 2 (Orthogonality). There exists some a² 2 such that, for all E Z and distinct i E [k]. Ep. ) = 0 and Ep_102 a²
Note that from Assumption 1 we have that Epp, [d=..] = 0 for each i. In conjunction with Assumption this implies that for any fixed E 2, the family (1, (1,1..1...... 2z.x) is orthogonal and uniformly bounded in L (2, p.). Taken together, Assumption and Assumption 2 roughly say that the densities can be decomposed into uncorrelated "perturbations" across coordinates of Z. In later sections, we will show that for several families, such as discrete distributions, product Bernoulli distributions, and spherical Gaussians, well-known constructions for lower bounds satisfy these assumptions.
Our first bound given in (3) only requires Assumption 1; by imposing the additional structure of Assumption 2, we obtain the more specialized bound given in (4). Interestingly, (3) can be strengthened further when the following subgaussianity assumption holds.
By Hölder's inequality. we also have Eoo (u, v) < Ep(u, v) dd//e v) for all p > and v Rd which implies that for p log d we have loo (u, (p(u,r) v) < 28oc (u, v): i.e., flog dlu, v) gives a factor-2 approximation of the for loss. This further extends s-sparse vectors, with factor s/p instead of dl/p,

---

Assumption& 3 (Subgaussianity). There exists some 2 0 such that, for all 2 E Z, the random vector (X) == (#z,) (X) E R is o² subgaussssinn for X P..
Let Z = (Z,...., Zx)) be random variable over Z such that Pr| Z, 1] for all E [k] and the 7,8 are all independent; we denote this distribution by Rad(r) sk Our main result is an upper bound on the average amount of information that can be obtained about a coordinate of Z from the transcript (Y", U) of a sequentially interactive protocol, as function of the information constraint channels and iz,i8. This result only requires Assumption I, and is presented below in its most general form, suited to applications beyond those discussed in the current paper.
Theorem (Information contraction bound: Technical form). Fix T E (0, 1/2. Let 11 be a se- quentially interactive protocol using W and let Z be random variable Z with distribution Rad(T)Sk Sk Let (Y", U) be the transcript of ll when the input .1....,N, is i.i.d with common distribation pz, with density function pz= Then, under Assumption 1,
2
- T C drv (pir.
Ep.lo 10 (X) X)]
Σ
2 max max 2E WEW.
Ep. (W [X] du
(3)
1=1 y
where p
E D
21 = +11, p
E
Pz
Z -
We now instantiate this result, invoking Assumptions 2 and 3, to give simple "plug-and-play bounds which can be applied readily to several inference problems and information constraints.
Theorem 2. Fix E (0, 1/2). Let lI be a sequentially interactive protocol using W and let Z be a random variable on Z with distribution Rad(T) 60 Let (Y", ,U) be the transcript of II when the impul X 1 ........ Xn i.i.d. with common distribution pz. Then, under Assumptions and 2, we have
E
k
7
max max SEZ WEW,
/
Varp. [W X)] du.
(4)
K
K
P. [W X)]
Moreover, Assumption holds as well, we have
k 1. dr (P (PI..
dn
14
n
0²
max max I(p:: W), ZE WEW.
(5)
where 1 (p.; W) denotes the mutual information I I() between the input X Ps and the output Y of the channel W with X input.
As an illustrative and important corollary, we now derive the implications of this theorem for communication and privacy constraints. For both constraints our tight (or nearly tight) bounds in Section 5 follow directly from these corollaries.
Corollary 1 (Local privacy constraints). For W = Wpriv,e and any family of distributions {P 2 {-1,+1} satisfying Assumptions 1
and 2, with the notation of Theorem 2, we have
1
TV Σ
1 drv @e
7 na ((e² 1)² Ae.)
(6)
k
Moreover, if Assumption 3 holds as well, we have
14
drv (pts pa (ptr. p
no²=.
Corollary (Communication constraints). For any family of channels W with finite output space Y and any family of distributions {pr,2 E {-1, (11,+1}k) satisfying Assumptions I and 2, with the notation of Theorem we have
k Σ drv (pfr, (p...
2 D.:)
7
(8)
K
'Recall that L... Y is subbauausni if |||] = 0 and EjeAy < e 22 for all X E I: and that vector- valuue L.v. Y is su-suaaassi if its projection (Y, u) is 0² -ubbausssiann for every unit vector u.
7

---

Moreover, if Assumption 3 holds as well, we have
(plt yn drv (Ptt p=:)
1 k
14
no log 1
k
i=1
4 An Assouad-type bound
In the previous section we provided an upper bound on 1 Ei=1 drv (pir, -P"")- We now prove a lower bound for this quantity in terms of the parameter estimation task set out solve. This is an "Assouad's lemma-type" bound, which when combined with Theorem 2 will establish the bounds for n; and, reorganizing, the minimax rate lower bounds. To state the result, we require the following assumption, which relates the lp distance between parameters 0g8 to the distance between 2s.
E
Assumption 4 (Additive loss). Fix p E (0). For every 2, z E Z C ([1,,+1)
( (Aittm ( (2,z²) 1/v
Ep(02,021) 47
TK
where damm (2,=) = Et= 12z # +/} denotes the Hamming distance.
Lemma (Assouad-type bound), Lel p 2 and assume that {Px, z E 2), T E 1/2 satisfy As- sumption 4. Let Z be random variable on Z {-1,+1} with distribution Rad(r) Suppose that (II, 8) constitutes an (n, esstimatto of Pe using W under lp loss (see Definition 2) and Prz Pz Pel T/4. Then the transcript (Y", UU of II satisfies
drv P p : N 4'
1=1
where P =
E
12
74 = +1], p E 12
Z = 1].
5 Applications
We now consider three distribution families: product Bernoulli distributions and Gaussian distributions with identity covariance matrix (and s-sparse mean vectors), and discrete distributions (multinomialls) to illustrate the generality and efficacy of our bounds. We describe these three families below, before addressing each of them in their respective subsection. Due space constraints, we present the proof of the upper bounds in Appendix C, and proof of the lower bounds in Appendix G.
Sparse Product Bernoulli (Ba,s). Let 1 S S d, θ e
|101| S&) }. and X {-1, Let Pe := Ba.s be the family of d-dimensional s- s-sparse product Bernoulli distributions over X. Namely, for 0 = (f1....,6d) O2) E O. the distribution pa is equal to 80 Rad( [ (0, + 1)): distribution on (-1,+1}4 such that the marginal distributions are independent, and for which the mean of the jth marginal is 0z.
Sparse Gaussian (Ga,s). Let S s < d, θ = { 0 E [], ||0l|o S 5 and X' = Rdd Let Pe : Gd., be the family of d-dimensional spherical Gaussian distributions with bounded s-sparse mean. That is, for E θ, Po = G( I) with mean @ and covariance matrix I. We note that this general formulation assumes |@@l I 1 (from the choice of +).
{0 10, ΣL, 0 S Rd and X (1,2....,d) dd.. Let Pe == Ad. where A, is the standard (d 1)-simplex of all proba- bility mass functions over X. Namely, the distribution po a distribution on X, where, for j E [d], the probability assigned to the element j is po(j) = 0,. For a unified presentation. we view as the mean vector of the "categorical distribution." namely the distribution of vector (1{X- x X) for X with distribution pa.
Discrete distributions (Aa). Let θ
"This assumption that the mean is hounded, in our case in foc (0. 1), is standard, and necessary in order to obtain finite upper bounds: indeed, packing argument shows that if the mean assumed be in hall of radius H, then log R(1) A dependence in the sample complexity is necessary in both the -onuniictttiocccstrrannedddd and LDP settings. Our choice of radius is arbitrary, and upper bounds can be generalized to any R > 1.
8

---

We now define our measure of interest, the minimax error rate of mean estimation.
Definition 3 (Minimax rate of mean estimation). Let P be family of distributions parameterized by θ C Rd. For p E [1, ool, n E N. and a family of channels W. the minimax error rate of mean estimation for P using W under Ep loss, denoted (p, W, r.). is the least y (0, 1] such that there exists an (n, 7) esstimator for P using W under Ep loss (see Definition 2).
We obtain lower bounds on the minimax rate of mean estimation for the different families above by specializing our general bound. Importantly, our methodology is not specific to lp losses, and can be used for arbitrary additive losses such as (squared) Hellinger or, indeed, for any loss function for which an analogue of Lemma can be derived.
Product Bernoulli family.
We first establish the following bounds for Basa under privacy and communication constraints.
Theorem 3 (Product Bernoulli), Fix E (o). For 4logd d S s S d, E E (0, oo), and f 2 1,
ds2iv niE N&) A S Ep, Marri,s mn) n(e3 A1)
ds2ir
(10)
and
ds2ip
/2/ log 2d A Ep W.oom. ,n) S V
ds2/p
$2/P 2d
(11)
nl n
nl n
For p = 00, we have the upper bounds
Eod (Ba..: Marriv n) o0 d ns² [
d
log d n
and Eoe (Ba,s, Weoum. .n :n)=0((
nl
while the lower bounds given in Eqs. (10) and (11) hold for p oo, too.
Remark 1. Previous work had shown, in the simpler noninteractive model, a rate lower bound scaling
as v ds/ (nL) log(2d/s) for the specific case of Eg loss (see, for instance, [21, Theorem 7] for the sparse Gaussian case, which implies the Bernoulli one). An analogous phenomenon was observed for local privacy (e.g., [14]). Thus, by removing this logarithmic factor from the upper bound, our result establishes the first (to the best of our knowledge) separation between interactive and noninteractive protocols for sparse mean estimation under communication or local privacy constraints.
Remark 2. Although we stated for simplicity the lower bounds of Theorem 3 in the case where all players have a similar local constraints (i.e., same privacy parameter E, or same bandwidth constraint E), it is immediate check from the application of Theorem 2 that the result extends to different constraints for each player; replacing ni(² ^e) and ne in the statement by >i= of A& and Ei= 4. respectively. A similar remark applies the Gaussian and discrete families.
Gaussian family. We derive lower bound for E, (Gd.s W,n) under local privacy (captured by W Wprrvv.e and communication (captured by W Wxoom..) constraints." Recall that for product Bernoulli mean estimation we had optimal bounds for both privacy and communication constraints for all finite p. For Gaussians, will obtain tight bounds for privacy constraints for E E (0, 1]. However, for communication constraints and privacy constraints when E 2 1, our bounds for Gaussian distributions lose a (single) logarithmic factor in some parameter regimes.
Theorem 4 (Gaussian distributions). Fix p oo). For 4 log d < S d, under LDP constraints, when ε E (0, 1].
ds2iv
ds2/v
A A1S Ep(9d.s Mirriv,s serrives,n. S n²²
(12)
ne²
and when >> 1,
ds2/p
ds2/p
A S Ep Mapriv, n) S ns log (nd)
(13)
'That is, the upper and lower bounds only differ by a log factor for p = oc. 7 As in the Bernoulli case, we here focus for simplicity on the case where the communication (resp., privacy) parameters the same for all players, but our lower bounds easily extend.

---

Under commumication constraints,
ds22rr 22/r log A A Ep W .n) S nl ldg(An)
ds2/r ne.
22/r log
(14)
The same bound in Theorem 3 hold for
We emphasize that, as discussed in Sections 1.1 and 1.2, to the best of our knowledge our results provides the first lower bounds for interactive Gaussian mean estimation under these constraints.
Discrete distribution estimation. We are able to derive lower bound for Ep( W, n),, the minimax rate for discrete density estimation, under local privacy and communication constraints. In the interest of space, focus here on two important corollaries; first, for the case of total variation distance (&1), where combining it with known upper bounds we obtain optimal bounds for all > 0. In particular, for & E (0, 1] (high-privacy regime) we retrieve the lower bound established in [5], which matches the upper bound from [4]. For & > (low-privacy regime), our bound matches the upper bound for the noninteractive case, established in [32, 1J, showing that even in this low-privacy regime interactivity cannot lead to better rates, except maybe up to constant factors.
Corollary (Total variation distance). For O, we have
d2
E (Ad, Wpeivie, x V n((e - 113
A1.
(15)
For l 1
d2
Ei(s,, W.oomm, n) x
A1.
(16)
m2 A d)
For the case of l2 estimation, we also obtain order-optimal bounds: Corollary (&2 density estimation). For 0, we have
(d,,,, Wprivee n) x V n(es 1)2 1E))
n(c 122 Al.
(17)
For 2 1,
d
Eg(Ad, Woomm. n) x / n2(2 A dd
A1. (18)
V
n(2 Ad)
Acknowledgment
The authors would like to thank Yanjun Han, and the anonymous reviewers for helpful comments an earlier version of this paper.
References
[1] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Hadamard response: Estimating distributions privately, efficiently, and with little communication. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pages 1 1120-1129, PMLR, 16-18 Apr 2019. URL http: //proceedings.ot mlr. ppwss/v89/
wtt../......r//////ceeeeeeeeeeee www.raaaaaaaaa..aaa/aaaaa html.
[2] Jayadev Acharya, Clément L. Canonne, and Himanshu Tyagi. Distributed signal detection under communication constraints. volume 125 of Proceedings of Machine Learning Re- search, pages 41-63. PMLR, July 2020. URL http://prooceedings mlr. S....ppees/vv2., acharya20b. html.
[3] Jayadev Acharya, Clément L. Canonne, and Himanshu Tyagi. Inference under information constraints I: Lower bounds from chi-square contraction. IEEE Trans. Inform. Theory, 66 doi: 10. (099/TT.2020.3228444 URL https:
(12):7835-7855, 2020. ISSN 0018 84488.
//doi. org 10. TIT. 2020 3028440. Preprint available at arXivaabs/8812
10

---

[4] Jayadev Acharya, Clément L. Canonne, Cody Freitag, Ziteng Sun, and Himanshu Tyagi. Inference under information constraints III: local privacy constraints. IEEE J. Sel. Areas Inf. Theory, 2(1):253-267, 2021.
[5] Jayadev Acharya, Clément L. Canonne, Yuhan Liu, Ziteng Sun, and Himanshu Tyagi. Interactive inference under information constraints. IEEE Trans. Inform. Theory, 68(1 (8(():5022 1):50-5516 2022. ISSN 0018-9448. doi: 10.1 109/000,002111311222 2021 3123905.
URL https:///oi...... ottp:///dooooo///eeooooo 10. 1109/tit..
[6] Ziv Bar- Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Comput. System Sci., 68(4):702-732, 2004. ISSN 0022-0000. doi: j0.1016/f.jcss.2000 2003. 11.006. URL httpp::///ol org/10.1016/] jcss 2003. 11.006.
[7] Leighto Barnes, Yanjun Han, and Ayfer Özgür. Fisher information for distributed estimation under a blackboard communication protocol. In ISIT, pages 2704-2708 IEEE, 2019.
[8] Leighton Pate Barnes, Wei-Ning Chen, and Ayfer Özgür. Fisher information under local differential privacy. IEEE J. Sel. Areas Inf. Theory, (3)::45-659) 2020.
[9] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: Nonasymptotic Theory of Independence. OUP Oxford, 2013.
[10] Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David P. Woodruff. Com- munication lower bounds for statistical estimation problems via a distributed data processing inequality. In Symposium on Theory of Computing Conference, STOC' 16, pages 1011-1020. ACM, 2016.
[11] Clément Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, and Lydia Zakyn- thinou. Private identity testing for high-dimensional distributions. In Advances in Neural Infor- mation Processing Systems 33, 2020. To appear. Preprint available at arXiv:abs/190) 11947.
[12] Thomas M. Cover and Joy A. Thomas. Elements of information theory. Intersenne [John Wiley & Sons], Hoboken, NJ, second edition, 2006. ISBN 978-0-471-24195-99 0-471-24195-4
[13] John Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Secont Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1161-1191, Phoenix, USA, June 2019. PMLR.
[14] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Minimax optimal procedures for locally private estimation. J. Amer. Statist. Assoc., 1136521):82-201, 2018. ISSN 0162-1459.
[15] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography, volume 3876 of Lecture Notes in Compul. Sci., pages 265-284. Springer, Berlin, 2006.
[16] Alexandre V. Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In PODS, pages 211-222. ACM, 2003.
[17] Ankit Garg, Tengyu Ma, and Huy L. Nguyen. On communication cost of distributed statistical estimation and dimensionality. In Advances in Neural Information Processing Systems 27, pages 2726-2734, 2014.
[18] Yanjun Han, Pritam Mukherjee, Ayfer Özgür, and Tsachy Weissman. Distributed statistical estimation of high-dimensional and non-parametric distributions. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISFT' 18), pages 506-510, 2018.
[19] Yanjun Han, Ayfer Özgür, and Tsachy Weissman. Geometric lower bounds for distributed parameter estimation under communication constraints. In Proceedings of the 31st Conference on Learning Theory, COLT2018, volume of Proceedings of Machine Learning Research, pages 3163-3188, PMLR, 2018.
11

---

[20] Yanjun Han, Ayfer Özgür, and Tsachy Weissman. Geometrie Lower Bounds for Distributed Parameter Estimation under Communication Constraints. ArXiv e-prints. 102./800.08417v1, February 2018. First version (https://abl) arwivv httpa//////.ooooo/aaa//////s//// (00bb//00000011111)
[21] Yanjun Han, Ayfer Ozgur, and Tsachy Weissman. Geometric lower bounds for distributed parameter estimation under communication constraints. IEEE Transactions on Information Theory, 67(12), 2021.
[22] T. S. Jayram. Hellinger strikes back: note the multi multi-pprty information complexity of AND. In Approximation, randomization, and combinatorial optimization, volume 5687 of Lecture Notes in Comput. Sci., pages 562-573. Springer, Berlin, 2009. doi: 10.1007/978-3-642-00800
42. URL https:///diii http::///oooooo/1//// org/ 1007 /90000077777700 978- 0----42-0000 0004222366599---
[23] Matthew Joseph, Janardhan Kulkarni, Jieming Mao, and Steven Z. Wu. Locally private gaussian estimation. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bin Buce E. Fox, and R. Gameet, editors, Advances in Neural Information Processing Systems 32, pages 2984-29999 2993.
Curran Associates, Inc., 2019.
[24] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM J. Comput., 40(3):793-826, 2011. ISSN 0097-5397.
[25] Septimia Sarbu and Abdellatif Zaidi. On learning parametric distributions from quantized samples. Proceedings of the 2021 IEEE International Symposium on Information Theory (ISTT"21), June 2021.
[26] Ohad Shamir. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In Advances in Neural Information Processing Systems 27, pages 163-171, 2014.
[27] Ramon van Handel. Probability High Dimensions. December 2016. URL https:/wwb/ math. pwinceton. aadu/"vva/AAPCSSS pdf.
[28] Martin J. Wainwright. Information-theoreer limits sparsity recovery in the hign-dimensional and noisy setting. IEEE Trans. Inform. Theory, 55(12))5728- 5741, 2009. ISSN 0018-9448. doi: 10.1 2tW.IITT.20092032881.. URL https://////oi org/10 111//1TTTTTTT 2009 2032816.
[29] Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63-69, 1965. doi: 10. 1080/ 01621459. 110.9.1155.....07777.1 10480775
[30] Yihong Wu. Lecture notes on: Information-theorrii methods for high-dimensional statisties, 2020. URL http: /twp://wwwwwaa http//tttttttttt//////t/////.... yale. http///y/6//ttccch///itti stttttgggttttttttttttsesssssssst stats, .df...s.........
[31] Aolin Xu and Maxim Raginsky. Information-ttheoreiee lower bounds on Bayes risk in decentral- ized estimation. IEEE Transactions on Information Theory, 1300),1500- 2017.
[32] Min Ye and Alexander Barg. Optimal schemes for discrete distribution estimation under locally differential privacy. IEEE Trans. Inform. Theory, 64()))5662-5676 2018. ISSN 0018-9448. 2018. 2809790.
doi: 10.1 (00p/TTT.211.28097777 URL U
[33] Bin Yu. Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam, pages 423-435. Springer, 1997. doi: 010777978---412-11888 178-1-4612- 1-8-0----8
URL http: //tx. doi. org/10.... 1007/
[34] Yuchen Zhang, John Duchi, Michael I. Jordan, and Martin J. Wainwright. cntrmatiion-hhoreete lower bounds for distributed statistical estimation with communication constraints. In Advances in Neural Information Processing Systems 26, pages 2328-2333 2013.
12

---

A Fully interactive model
In this appendix, we describe how extend results, presented in the sequentially interactive model, to the more general interactive setting. We first formally define this setting and the corresponding notion of protocols. Hereafter, we use for the Kleene star operation, i.e., V U V".
Desinition 4 (Interactive Protocols). Let X,,..., n. be i.i.d. samples from po. 0 E O, and W be a collection of sequences of pairs of channel families and players; that is, each element of W is sequence JeleeN where Jt E [n]. An interactive protocol II using W comprises a random variable U (independent of the input 11, ,....,,,,, X,) and, for each t E N, mappings
0:: V1 Y.,, U + N, E [1]
9e: Y1, Y U W.
with the constraint that N1) ..... (W,, N))) must be consistent with some sequence from W"; that is, there exists (W).)e))es E W such that Wa E W. and N, = Js for all 1 I S t. These two mappings respectively indicate (i) whether the protocol is stop (symbol 1), and, if not, which player is to speak at round & E N, and (ii)) which channel this player selects at this round.
In round f, if N, = 1, the protocol ends. Otherwise, player N, (as selected by the protocol, based on the previous messages) uses the channel W, to produce the message (output) Y; according to the probability measure W,(- [N.)). We further require that T == inf E N N, I } is finite a.s. The messages y (Yi,.... YT) received by the referee and the public randomness constitute the transcript of the protocol II.
In other terms, the channel used by the player No speaking at time t is a Markov kernel W,: 2) x X' x yd + [0, 1].
with V/ C y and, for player j E [ni]. the allowed subsequences Je)eNN) capture the possible sequences of channels allowed to the player. As example, if we were to require that any single player can speak at most once, then for every j E [n] and every jttee E W", we would have
Ee 1 = j} 1.
In the interactive model, we can then capture the constraint that each player must communicate at most & bits in total by letting W be the set of sequences (Wr (omom.. .Jt)en such that
DC
Vj E [n],
Σ
4 1 = }} jjst. St.
In the simpler sequentially interactive model, this condition simply becomes the choice of W (Wpcomm,, W)comm.)).
A.1 Lower Bounds under Full Interactive Model
Next discuss how technique extends the full interactive model. For any full interactive protocol II, let Y* E y* be the message sequence generated by the protocol. Then, for all y" e e we have
Pr Y y=]== X
II We "xx(((-11,
The following lemma states that if X are generated from a product distribution, the distribution of the transcript satisfies a property similar to the "cut-and satt-and-pac paste" property from [6].
Lemma ([20)). If X p @ Ps, the transcript of the protocol satisfies
Pr Y = 4-1 II E Ex.-pa (go( Xx)]]
(19)
X=
where ge(y", j==1 W5(y
xr, - (1 = =1]
Hence, when X" ~ o we have
Ddd =
Y = 1/"
II Ex, -p. 1x Xx)]-
X
13

---

Here we can define similar notion of "channel" for communication protocol II for the ith player when the underlying distribution is p. by setting
(v" x)) ,z)
Ex, xx)]]
(20)
jØt
Then we have, for all t [n].
Exper W.P. (v" 1x,)
Pr [Y* = 3²}. X"rup
We proceed to prove bound similar to Theorem in terms of the "channel" defined in Eq. (20), as stated below.
Theorem (Information contraction bound), Fix T (0, 1/2]. Let be a fully inteructive pro- tocol using W and let be random variable on Z with distribution Rad(r) Let (Y*, U) be the transcript of II when the input XI...., Xn is i..dd with common distribution pz. Then, under Assumption I,
2
dT pp (P):.P
Ep. 22 (X),, s.p. (v" x)) x
7
$
a
max
du
222 (Wede)
i=1
Ep,
Wip. (0" |x)
where p = 1E P
2 1 2-
24 =1 1].
We can see the bound is in identical form to Theorem except that we replace each player's channel with the WAPx''' (y' X) we defined. Other similar bounds in Section 3 can also be derived under additional assumptions and specific constraints. We present the proof for Theorem 5 below and omit
the detailed statements and proof for other bounds.
Proof. Analogously Eq. (36), we can get
k
d TV
p pH..P:))
<
14
Ez
du
Pz Y , Pi-zas
(21)
K
For all E 1-1,+11 and i, by the definition of Hellinger distance and Eq. (19), we have
2
2dh ( Ps p
II
Ex (,,(v"xx,)) (V loc x.)) v 1ol Xx)]
dp
y'E
13j5n
JEL
J Jeyy
(Exirps loo (0=,(xX)) x.)) - Exixp, loclu" ;x,])] du, Ex,=p, (90 Xx))
EI
E (os(y" X,)1) j#1
Proceeding from above, we get under Assumption 1,
2dh (p. Y -01
sa² )
f wey.
Ex 19)0 jtt
E Exirp, (o (Xi)e (U)))
dp
Ex.xpa (g X1)]
Exipp. (2,((X)))ee) X₂) II ji Ex L0s (v", x;)] 2 du
a
y'Ey.
Ex ge(y", X.) II ii Exymp. (9,(", [x))
Exiop (x) W. (v* x))
a
dj.
-'
Exiop. W.P. (3² x)
Plugging the above bound into Eq. (21), we can obtain the bound in Theorem by taking the maximum over all [-1,+1) and all possible channel sequences.
D
14

---

B A measure change bound
We here provide variant of Talagrand's transportation-cost inequality which is used in deriv- ing Eq. (5) (under Assumption 3) in the second part of Theorem 2. We note that this type of result novel, and can be derived from standard arguments in the literature (see, e.g., [9, Chapter 8] or [27, Chapter 4J). However, the lemma below is specifically tailored for our purposes, and we provide the proof for completeness. A similar bound was derived in [2], where Gaussian mean testing under communication constraints was considered.
Lemma (A measure change bound). Consider a random variable X taking values X and with distribution P. Let o: X' - IR be such that the random vector (xX) is o² -u-uaaaussian. Then, for any function a: X [0, (C) such that [[a(X)] < C0, we have
LE [ (X)a())I
20 B((()) Ina(X)] +20 In E [[a(X)]
B[a(X))*
E[a(X)]
Proof. By an application Gibb's variational principle (ef. [9, Corollary 4.14)) the following holds: For random variable Z and distributions P and Q on the underlying probability space satisfying Q (that is, such that Q absolutely continuous with respect to P), we have
Z < In Ep + P).
To apply this bound, set P to be the distribution of X and let Q < P be defined using its density (Radon-Nikodym derivative) with respect P given by
dQ x(X)
dp Epla(X))
Now, note that for any unit vector we have, setting Z = uT (X) and using the of (X), that
- a'-subaaussianity
d²1²
AE AE S In Ep (cT
D(QIIP) <
+ P(QI)P)
2
In particular, for - (D) we get
EQq ( S <aV22((11)
Applying this to the unit vector o: :
[x(x (X]],, then yields
EQ (X))l,, I a. /
To conclude, then suffices to observe that
D(QIIP) Ep(a(() (X)] In Ep (x))
Ep [a(]]
The proof is completed by combining the bounds above, as Eq [X() =
(x( Ep (x))
C Upper bounds
We now describe and analyze the interactive algorithms for the estimation tasks we consider.
C.1 Product Bernoulli Distributions
Recall that Ba the family of d-dimensional s-sparse product Bernoulli distributions, is defined
Ba,a
X Radt (1g + 1)) :
: e |Pllo S s
(22)
We now provide the interactive protocols achieving the upper bounds of Theorem 3 for sparse product Bernoulli mean estimation under LDP and communication constraints.
Our protocols has two ingredients described below:
15

---

Estimating non-zero mean coordinates.In this step we will start with So = [c]. the set of all possible coordinates. Then we will iteratively prune the set So S - ... ST, such that |Sr| 38 (this step is skipped if 8 2 d/3) is good estimate for the set of coordinates with non-zero mean.
Estimating the non-zero means. We then estimate the means of the coordinates in Sr, which is equivalent to solving a dense mean estimation problem in 3s dimensions.
In the next sections, provide the details of the algorithm that matches the lower bounds obtained in Section 5 for interactive protocols under LDP and communication constraints respectively.
C.1.1 LDP constraints
In this subsection, we will focus on the case E E (0. 1] (high-privacy regime). For the case E > rely privatization of the communication-limice algorithm, which will be discussed at the end of Appendix C.1.2. Our protocol for Bernoulli mean estimation under LDP constraints is described in Algorithm 1. As stated above, in each round t = 1..... T, for each players apply the well known binary Randomized Response (RR) mechanism [29, 24] to their jth coordinate. Using these messages we then guess set of coordinates with highest possible means (in absolute value) and prune the set to S. This is done in Lines 2-6 of Algorithm 1.
St-1 a group of
In Lines 7-12, the algorithm uses the same approach to estimate the means of coordinates within Sr and sets remaining coordinates to zero.
The privacy guarantee follows immediately from that of the RR mechanism, and further, this only requires one bit of communication per player.
Algorithm LDP protocol for mean estimation for the product of Bernoulli family
Require: n players, dimension d, sparsity parameter s, privacy parameter e. d
1: Set T = logs 36
_ So [d]. Ng = a
2: for = 1,2.....
do
3:
for forj eerjs.... S do
4: Get group of new players Gt.j of size N₂ No 2
5: Player i Gr.j upon observing X₁ {-1, +13d sends the message Y {-1, +1}
such that
(Xi);
w.p. a.
Yi -(xi);
(23)
w.p. -
6:
Set Mt.j = Eiege, Y, Let S S S be the set of the |S--1/3 indices with the
largest MM,il
7: for ST do
8: Get a group of new players Grjij E ST of size Nr+1 = No 2
9: Player i GT,j- sends the message Y, E {-1,+1} according Eq. (23) and Mr
Σigrn Y:
10: for E [d] do
M (2- 1,444
if E ST. otherwise.
12: return f2.
The performance guarantee of Algorithm is stated below, which matches the lower bounds obtained in Section 5.
Proposition Fix E [o). For n 2 1 and e E (0, 1]. Algorithm is an (n, -sstimmtato
using We under lp loss for Ba,s with y 0 pds2/v p 2 log
for p S 2log and 7 O ((V /dog for ng
nE²
16

---

Proof. The total number of players used by Algorithm uses is
T+1
T+1
2
Σ
S N₂ = |5o| No
6 No = n.
3
To prove the utility guarantee, bound the estimation error in the estimated set ST and the error outside the set Sr in the following lemma.
Lemma 4. Let Sy be the subset obtained from the first stage of Algorithm 1. Then,
}
pd nE
p/2
max
Σ lu - -i1
E
Σ Mg JEST
JEST
The proposition follows directly from the lemma. Indeed, for > 2 2lggs. s. by monotonicity of ép norms we have || Lllp I || All for all p' $ p. and thus choosing p' 2 log s sufficient to obtain the stated bound.
Proof of Lemma 4. We prove the bound on each term individually. The first term captures the performance of our estimator within coordinates in SI and the second term states that we do not "prune" too many coordinates with high non-zero means.
Bounding the first term. For & Sr, we output 7ú = 0. Therefore,
Rgg 1
-EElIA
Ellas - 2U1"- 1(j ST = Σ 1uy Pr[j & Sr
JIST
Since fa is s-sparse, it will suffice show that for all j with | >
lnsl Pr[j &Sr o ( pd
p/2
(24)
ne?
Let
d
H 20,
n22a 1)2
Note that for (0, 1], have 2a
c+1 8. Therefore, [pyl H, then Eq. (24) holds since
Pr[. & S] 1. 1. We hereafter assume ||y
H. and let (4 = 3 H with 35 1. Let Ft, be the given j E St Then we have
event that coordinate j is removed in round
T
PrLi $ ST S
Σ Ers
We proceed to bound each Pr[ E separately. Note that for E Grj. Yi E (-1,+1) and by Eq. (23)
E E = (2a - 1) = (2o 1)33 H.
(25)
Let arjj be the number of coordinates j' with pt 0 and |Ma'' N. H1 Since select the 15,-1//3 coordinates with the largest magnitude of the sum, for j $ S; to happen at least one of the following must occur: (i) at.j > S s, or (ii) Mc, No 1)3,
By Hoeffding's inequality, we have
Pr Mt,j N, 1)3, < exp
1 N
cxp(-5.
Let Pt.j := e -3,2"33 Similarly, for any j' such that 14 =0,
Pr M 2 Ni(a - 1)3,
$ 2pr.j
17

---

Since all coordinates are independent, at,j is binomially distributed with mean at most 2pr,, ( By Markov's inequality, we get
1 3 11 -
E B
Pr
anj
S Pt.j.
S
recalling that |St-1|
d3 11
2 9s. By union bound and summing over E [T', we get
T
Pr[j $ Srl
Pr[ Bag
3pc.
3
Σ
exp(-22 (23)))) (-33)
1=1
Not that for x > O, x
tc) (c)
p/2 Hence
(c pdl P/2 NE?
lag/p. Pr[j Sr S 6HP S.e 583
for absolute constant C 0, completing the proof.
Bounding the second term. Note that S a random variable itself. We show that the bound holds for any realization of Sz. We need the following result which follows from standard moment bounds on binomial distributions.
Fact 1. Let p 2 m EN, L, and N Bin(m, q). Then, E|JN mq "1 2 2 p/22
Applying this with m = NN 2 6d the transformation from Bernoulli to {-1, and the scaling by 2a yields for j E ST, and using Eq. (25)
(n/6d) (T_/ P
p/2
E||e p,1" =
(2a - 1)33
Upon summing over j E ST, obtain
(6(e+1))2 1)3d ( P/2
pd
p/2
E
s 3s
((e (e-1))ne
S 3 6"
JEST
C.1.2 Communication constraints
In Algorithm 2 propose a protocol to estimate the mean of product Bernoulli distributions under b-bit communication constraints. As mentioned the previous subsection, the e-LDP algorithm with will follow from simple modification of the communication-ccnstraann. one; diseuss how to privatize the latter to obtain the former at the end of the section. As in the LDP case when E (0, 1). in 2-10 the algorithm iteratively prunes initial set So [d] to obtain set Sy of size max(3s, f). which denotes the set of potential non-zero coordinates. We then estimate the mean of coordinates in ST. If > 3s, then we can directly send the values of all coordinates in ST and use it for estimation; otherwise, when 3s > f, we again partition Sy into sets of size & and each player sends the bits of its sample in this set. This is done in Lines 11-18. We state the performance of Algorithm 2 below.
Proposition 2. Fix P E oc). For n 2 1 and e S d, we have Algorithm 2 is an (n,7) esttimatoo
using We under Ep loss for Bd,s with 7 = O (
pdle/r ni +
(pt lottog( 25/s)))2/v for p S 2 log s and
= = dloge nf
Log
for p > 2 2 s.
When ( 3s, the bound we get 7 S pols2/p LDP constraints, since in both cases, the information we get about coordinate ý are samples from Rademacher distribution with mean (2a L)μg. There are only two differences. (i) instead of
nt The analysis is almost identical to the case under
18

---

Algorithm 2 E-bit protocol for estimating product of Bernoulli family
Require: players, dimension d, sparsity parameter 8, communication bound L.
1: Set 7 == (d/ [3s, f}). So :- [d], No =- nf
18d
2: for = 1.2..... T do
3: Set P := Ip. and partition St-1 into P subsets St-1,1, St-1.P, each of size L.
4:
for jo 1.2......4 do
5:
Get group of new players Gt, of size No NNo=No11 . Player ((x))=
6:
Gt.j upon observing X; E +-1,+11e sends the message Y
7:
For x E St-1j, let Me,, Eieg., (Xi)a.
8:
Set S St-1 to be the set of indices with the largest Me,z and |S| = S1,-1/3.
9:
if < 3s then
10:
Partition Sy into 35/l subsets size each, Sry.j E [3s/O. for .........///............... .3//L do
11:
12:
Get a new group GT+1,5 of players of size nł (6s). Player i GT+13 sends the message Y, {(X)) ((X))))uEST.
13:
14:
For E ST. let MT-1* EiEGrI (Xi)a. Set
68
Ps = MT+1,1
nt
15:
For x & Sr, set Phx 16: if > 3s then,
Get n/2 new players GT+1 and for i E Gr+1, player sends Y, ((Xi)) This can be done since |ST| = 1==-ii if > 3s.
18:
For x E Sy, let MT+1. E EiEGrIAS (Xi).. Set ST41 S Sr be the of indices with the largest |M+11al and |St+l| = 38. For all x E ST41, set
2
Pe Mr+1,. n
and for all x & ST+1, Pe = 19: return ft.
(c²)). (ii) There is factor of l more players in the corresponding groups. Combing both factors, can obtain the desired bound by replacing g2 by l. We omit the detailed proof in this
When >> 3s, after T x log(d/E) rounds, we can find subset Sr of size which contains most of the coordinates with large biases. The protocol then asks new players to send all coordinates within ST using bits. In this case, would be enough to prove Lemma since for the coordinates outside Sr, we show the error is small following exactly the same steps the proof for bouding the first term Lemma 4 as we explained in the case when E S 3s.
Lemma 5. Let ST be the subset obtained from the first stage of Algorithm 2, we have
P/2
p p log
E
Σ JEST
|og - Pug1 = =0
Proof. Similar Lemma 4, we will prove that the statement is true for any realization of ST, which a stronger statement than the claim.
E
|0g
E
P3 S
E
Σ
Srt1l
JEST
JEST
JEST
E
Σ
|My p
Σ
1n Pr[j o ST+1].
JEST+1
jESr
19

---

Fix S1+1- For each j E Sr+1, Mr+1.1 is binomially distributed with mean M4 and n/2 trials. By similar computations Lemma have
E
Σ
Jg T2518 = =0 (-) p/2
(2)))))
(26)
gEST+1
Next we show for all j E ST such that juj + 0,
0/2
p V 64 2
MrPP $ STH1] 2
(27)
7
layl E H' == 8V In Eq. (27) always holds since Pr[j j $ S] S that |pyl > H', and write Hj = H. for some B3 > 1.
Hence we hereafter assume
Let ar+1, be the number of coordinates j' with M4 and |Mr+1,5l 2 3, Then since Sr+1 contains the top 3s coordinates with the largest magnitude of the sum, we have j $ Sr+1
happens only if least one of the following occurs (i) 0r+1, > 2s, or (ii) Mr+1, < n H,
By Hoeffding's inequality, we have
-403
Pr MT+1,
1
333H')
S exp
1 n
8,
28
= pr+15
2
2
2
2
Similarly, for any j' such that py = 0,
8
Pr MM++15
<
2pr-1.f
Since all coordinates are independent, or+1,j is binomially distributed with mean at most 2pr+1.jf, and therefore, by Markov's inequality,
2pT+156
28
1-133
-393
Pr[aT+1j > 2s] -
<
2s
the last step since 8, > By a union bound, we have
1n
3
2
-383
Pr[j & Sr Pr[aTTI,5 > 2s] + Pr
MT+1J <
<
2
42
2
Using the inequality xaa Ize) p/2
which holds for all x
get overall
403
26
p/2
|ep1 Prij & Sr 211 3r
2
establishing Eq. (27). Combining Eq. (26) and Eq. (27) concludes the proof Lemma since there are
most unbiased coordinates.
Algorithm under LDP with s>> 1 To get a s-LDP algorithm in the regime & > 1 (low-privacy regime), we perform the following changes to obtain private algorithm from Algorithm 2:
Each user independently flips each coordinate of their local sample to get Z; where. for all c and (Z,).z
x E [d), (Z,)., (Xt)z with probability e+I (note that this corresponds applying Randomized Response independently each bit with privacy parameter 1).
(X,)., with probability a+I
Users then follow Algorithm 2 with the setting E = [E] and local data (Zeie))) and obtain estimate ft.
The final estimate is then st
20

---

The privacy guarantee of the algorithm comes from the fact that Algorithm sends at most & = [E] coordinates of each Zi and for any S with [S] S
[E]
Pr| (Z Pr[ (=(((())))es
X
Pr (Z,), (X))z]
S els)
X
Pr| (Z:). [x()=]
#ES
The utility guarantee follows from observing that pz be preserved up constant.
= jr and hence any lp error guarantee will
C.2 Gaussian Mean Estimation
Recall that Gd.s denotes the family of d-dimensional spherical Gaussian distributions with s-sparse mean in [], ie..
Ga.- = (p, | S L, ll s }
(28)
We will prove the following results for LDP and communication constraints, respectively.
Proposition 3. Fix E [0]. For n 2 and & E (0, 1). there exists an (n, - using
We under Eo loss for Ga,s with 7 = =oV
pde2/p net
for p I 2log and 7 = o o(V d'oog
for
ne
p 2logs.
Proposition 4. Fix P E [1, For n 2 and l S there exists an (n, (1.7))=ee ---tiimato using
We under Ep loss for Ga, with 7 0
pds2/n nl
(p+ (p=log(2l/a))s2/ for p S 2log s and 7 12
(V Alog ne
log for > 2oggs.
+
n
We reduce the problem of Gaussian mean estimation to that of Bernoulli mean estimation and then invoke Propositions and 2 from the previous section. At the heart of the reduction simple idea that was used in, e.g., [10, 2, 11]: the sign of a Gaussian random variable already preserves sufficient information about the mean. Details follow.
Let p Gá.s with mean μ(p) = (u(p)
For X ~ p. let Y
(-1,+1)d be a random variable indicating the signs of the d coordinates of X. By the independence of the coordinates of X, note that is distributed as a product Bernoulli distribution (in Ba) with mean vector v(p) given by
> 0] 11 Erf (()),
(p): Pr Xx X-p
E [d],
(29)
and, since [μ(p){| < 1, we have ( E [-n, where == Er((1//2) zs 0.623. Moreover, immediate see that each player. given sample from p. can convert it to a sample from the corresponding product Bernoulli distribution. We now show that a good estimate for u(p) yields good estimate for μ(P).
Lemma 6. Fix any p (c) and p E Gd. For D [].. define To [-1, by Tr /2 Erf E all E [d]. Then
[p(p)) - -il, <
ET 2
[[((p)) - 811
Proof. By computing the maximum of its derivative, 8 we observe that the function Erf-1 is yen Lipschitz on [-n. By the definition of f and recalling Eq. (29), we then have
2
(l((p) 2 Σ
(p(); -pal" p 20/2.
Erf Erf (w,) Erf Erf (2.)"
(eT)
P/2
14
Dz
where we used the fact that v, D E [-1], 1/d
*Specifically, we have that maxxe(-n.n) Erf (x) = 1/v2 by definition of 1 and monotonicity of Erf. Recalling then that, for all [-n.n], (Erf (Erl-)((x) (BF Lipschitzness claim.
(x)) < ya e
get the
21

---

As previously discussed, combining Lemma 6 with Propositions and (with r = )) immediately implies Propositions and 4 for p E [o]. Remark Note that for the Gaussian family, we also consider the linear measurement constraint. Under linear measurement constraints, we can use the linear measurement matrix to obtain out of d coordinates and perform the above reduction to product of Bernoulli family. The obtained bound will be same as that under communication constraints.
D Relation to other lower bound methods
We now discuss how our techniques compare with other existing approaches for proving lower bounds under information constraints. Specifically, we clarify the relationship between our technique and the approach using strong data processing incqualities (SDPI) as well as that based on van Trees inequality (a generalization of the Cramér-Rao bound).
D.1 Strong data processing inequalities
We note first that the bound in Eq. (5) can be interpreted as a strong data processing inequality. Indeed, the average discrepancy on the left-side of inequality can be viewed as the average information Y" reveals about each bit of Z. Here the information measured in terms of total variation distance. The information quantity on the right-side denotes the information between the input X and the output y of the channels. Since the Markov relation z" X y* holds, the inequality is thus strong data processing inequality with strong data processing constant roughly o /k. Such strong data processing incqualities were used to derive lower bounds for statistical estimation under communication constraints in [34, 10, 31]. We note that our approach recovers these bounds, and further applies to arbitrary constraints captured by W.
D.2 Connection to the van Trees inequality
The average information bound in (3), in fact, allows us to recover bounds similar to the van Trees inequality-ban bounds developed in [7] and [8].
For θ C IR and parametric family? Pe = {pg. 0 E @), recall that the Fisher information matrix (0) a & matrix given by, under some mild regularity conditions,
1og log Pa (X)
J(O), Ep
i,j E [k]]
00,00,
In particular, the diagonal entries equal
1
Opo
)
J(O).. Ep
(x)
i E [A:].
(X)
00,
For our application, given a channel W W, we consider the family P == (p) 0 θ) of distributions induced on the output of the channel W when the input distributions are from Pg. We denote the Fisher information matrix for this family by JW (0), which we compute next under refined version of our Assumption I described below.
Let 0 be a point the interior of θ and pa be differentiable at O. We set 02 (-1, and make the following assumption about the structure of the parametric family of distribution: For all E {11, and i E (k),
dp dp
1+ 7E2, + 2
(30)
where Ep. (x){] and Ep. (x)2 are assumed to be uniformly bounded for y sufficiently small; for concreteness, we assume Ep, [v] (12,(()) < c² for constant c, for all y sufficiently small. Let (x) = lim (x), for all
We assume that each distribution pa has density with respect to common measure and, with slight abuse of notation, denote the density of po also (xX)
22

---

In applications, we expect the dependence of f2, on y to be "mild," and, in essence, the assumption above provides linear expansion of the term iz, from Assumption 1 as function of the perturbation parameter ?, Assuming that the densities are differentiable distribution P of the oulput of a channel W with input X ~ Pa. we get
function of for the
Öpp (v)
P. (v)
Po W
(v)
24 lim
00,
7-00
2, lim Ep. [(57, + 7 2 (X)) x)]
7-00
ISs,, W(y x));
where we used Eq. (30), the fact that lim 0- 0, the fact that Ep. [V,, (v xx] s / E..
W
xy S c, and the dominated convergence theorem. Thus, we get
IP LE, (X) X))² E po [Wy X)]
((JW(O)) =
du.
(31)
Our information contraction bound will be seen later (Section 5) to yield lower bounds for expected estimation error. For concreteness, we give preview of version here. We assume for simplicity that W; W for all t and consider the & loss function for the dense (T = 1/2) case. By following the proof of Lemma below, given an (n,7) -estimatto & = 0(Y", U) of Pe using W under & loss, we can find an estimator 2 "(Y", U) such that
k
Pr
24 + Z
E
0211]]
s 4y2
whereby
& Σ drv y .P 2
8n2
Σ
Pr
24 x Z4
2
Upon setting = 4//v v Th we get that the left-side of Eq. (3) is bounded below by 1/4. For the same y and under Eq. (30). the right-side evaluates
4 k
Ep. (x)2,(X) + (,),, [x))²
max sEZ WEW
Σ
du
BW X)]
n
E [c] (X)W (v) x)] + 7 (x),(W) x))
max max
du
k
2E WEW
Ep. [W X)]
1=1
128-7n
k
Ep. (X), (y) x)]²
du + 227
max max
k-2
WEW
Ep. (Wy)) X)]
1=1
where we used (a (6+b) 6)2 S 2(a² + 62) and
E. (X) x))²
Ep. (W X)] du S / Ep. (V.)) (x) du Ep. (V)(())) s c
Therefore, Eq. (3) yields
1.2
72
256 n
maxxca maxwew Σk Sy
Epe (X) Fp. (W X) dp o²
This bound is, in effect, the same as the van Trees inequality with Tr (JW(O) replaced by
Pp. 10 (X)W (y) x)12
g(r) =
du.
Ep. W(y X)]
1=1
23

---

In fact, in view of Eq. (31), Tr(J lom =: g(0). Thus, our general lower bound will recover van Trees inequality- We note that Eq. (30) holds for all the families considered this paper (see Eq. (40) for product Bernoulli, Eq. (42) for Gaussian, and Eq. (50) for discrete distributions). We close this discussion by noting that results in Section are obtained by deriving bounds for g(7) which apply for all y and, therefore, also for g(0)
bounds when Eq. (30) holds and g(?) ~ g(0).
(J)())
E
Missing proofs in Section 3
E.1 Proof of Theorem
Consider = .x) E {-1,1}* where Zi...., Zy are iid. with Pr| Z, = 1] = т. For fixed i [k], let
y = Rg
7: = +1
Σ
11zj (1 (1 1 83 Y
Pz
T
P
#:2,+11
p
Ez
Pz r"
Z: -
Σ 2:2,--1
(1-
بيي P
j71
the partial mixtures of message distributions conditioned on 24- We will rely on the following lemma, which relates the desired average discrepancy between the p and p", to the sum of "local" discrepancy measures (in the form of Hellinger distances between local messages). Each local measure can then be easily bounded in terms of the density p3 and the channel W to get the desired bound.
Lemma 7, With the notation of Theorem we have
1 Edv drv (ptt.. S
14
max max SE2 W WEW:
Σ
du
(32)
where D denotes the distribution of ~ W (X) when X ~ P
The proof of the lemma is rather involved and constitutes the core of the argument. We defer it to the end of the section and show first how it implies Theorem For all z and W, we have
du (p_
W P Pg
1
(V [X)] E... (W X))
du
2 yEy
1
/
IW X)] Ep Eppe. (W X)]
dj
2
E.. [W X)
Bppoo (W(y) x)) [W X)I)
(Ep. (W (y X)] Ep
< 2 //y
du.
(33)
Ep. IW (y X)]
Moreover, under Assumption 1; for any W E W2 and y E y,
dd
Ep .0 [W X)] = Ep.
W(y) x) = Ep, [(1 + (x,(()) W x)).
dp:
Plugging this back into (33), we get
W 1 (X) x)] du (p
p
(W X)) du.
Combining this with Lemma 7 concludes the proof of Theorem 1.
24

---

Proof of Lemma 7. Our first step is to use the Cauchy-Schwarz inequality, followed by an inequality relating total variation and Hellinger distances:
ya vm) Σ dTv Pfi ph.
yn rn)e P4s:P-i
dTV
h
==1
dh P+i p- v
i=1
k
Ex du Pz yn )²
<
Σ
2i = +1
1=1
Ez dh Pz y" rn Pzzii }2]
Σ 1=1
(34)
where the last inequality uses joint convexity of squared Hellinger distance, and the final identity is due independence of each coordinate of and symmetry of Hellinger whereby Ez du (p%
y pZz.)
Zi +1 Ez (p r. p2Z.) Z -11
In order to bound the resulting terms of the sum, we will rely on the so-called cut-paste property of Hellinger distance [6]. Before doing so, we will require an additional piece of notation: for fixed
2 2, i E [k), t E [n]. let p/r denote the message distribution where player t gets a sample from Ps0: and all other players get samples from Pa. That is, for all y" )" the density of p)- with respect to the underlying product measure 8n is given by
dp Pioee dy
(v")) ExExxxpp- W (y/ Xi)
IxxxpD Wo'' (ys xx)]
(35)
The following lemma, due [22], allows relate du (p. , P ), the distance between mes- sage distributions when all players get observations from Ps. or all from Paat, to the distances du (p. P. -)-gas) where only one of the n players gets sample from Paac.
Lemma 8 ([22, Theorem 7]). There exists such that for all z E Z and E [k]]
n
du pp P
S CH
du P
-Pi
Moreover, one can take cH = 2 1-2- <7
Combining Eq. (34) and Lemma 8, we get
1 drv P+i p p.:i)
27
< 14
Σ
Ez
du
pz y"
Pii200
y"
k
i=1 1=1
= 14 Σ
Ez
Σ
dh
pz TM
PP4-2
(36)
1=1
im
25

---

In view of bounding the RHS of (36) tern by term, fix j E [n] and E 2. Recalling the expression of p Pirz0: from (35), unrolling the definition of Hellinger distance, and recalling (35), we have
2 1=1
Hh P2 rr
:pi )²
dp T dyron
dp 2
du 8n
dn
ym
2
Σ
Epp
W.
(3s xx] (
Ppp. Pp. [Wot '(ve x)] V F P... [Wve-(yv (yre x)]
dn Rn
1+
= .ve)
Epp
Wo'' (Us x3] / fiellt 31)) 1mm- f
II Ep.
Ww' (v) x)] dp 01 1) du dp d(a-
532
Woo''00s (0s x3] / Fiol ,.)) y:
Wo''' 'ws (0s x)] d( ) dus(t-1) dp
Ep
E
jot
Ep. /wo' (ws x3] / fialls vi) (u)dddd du d(t-1)) 1(--1)
&
Ep.
Wo' (ug
x) Σ
/ fiallt ,e) du du 3(--1) i=1
y
JKt
where the second-to- identity uses the observation that, for any fixed J E )r
[ II E.p 3>t
Ww (us xx] dr d =1
which in turn follows upon taking marginal integrals for each coordinate. We then get from the pointwise inequality Sye- fo, (,)) du S supy Ei Sy fe,( vi) du that
2 Σ du P y"
-
2 )²=
II Ep.
Wo'''(00 (21
xx)
Σ
(1 fulls's ve) du) du 0(1-1)
sup E'EYt-1
1=1
yx-1 jct
Σ / frall', ,31) du
E [wo' (w; xx] d
sup WEY'-1 1=1
3 JKct
k / (
2 V Eppe WW'' (y x)]
sup -
(V Fp. IW (v X)]
dp
/ Bp. (W XX] Ep
< sup wew.
IW Fo
X3] du
2 sup
Σ
dn w p
(37)
WEW.
the second identity follows upon taking marginal integrals, and by replacing fú, by its definition; and the second incquality using that Wy' : y E y } C Wr, so that we are taking a supremum over larger Plugging this back into (36) and upper bounding the inner expectation by maximum concludes the proof of the lemma
D
26

---

E.2 Proof of Theorem 2
Our starting point is Eq. (3) which holds under Assumption We will bound the right-hand- side of Eq. (3) under assumptions of orthogonality and subgaussianity to prove the two bounds Theorem
First, under orthogonality (Assumption 2), we apply Bessel's inequality to Eq. (3). For a fixed E 2, write V2.1
6z.1 and complete (1, 1,,,,..., 12,a) to get an orthonormal basis B for
VB [o..]
(2, Ps). Fix any W E W and y E V, and, for brevity, define a: + R as a(x) = W (y x)) Then, we have
Σ E (
S a²
E B (X) {aa(X)}² =n² a² >
(a,))
a² Σ {a [a) Vh.,)
i=1
a
(a B[a], x)) = =a² Varla(X)),
BEB
where for the second identity we used the assumption that (E[a), v2,)) = 0 for all i E [k] (since 1 and 2/., are orthogonal). This establishes Eq. (4).
Turning to Eq. (5), suppose that Assumption 3 holds. Fix E 2, and consider any W E W and y E y Upon applying Lemma 4 of the Supplement (See Supplement (Appendix B) for the precise statement and proof) to the oussugaausia random vector (z and with a(x) set to W (y x) E [0, 1]. we get that
k
Σ E. (X) x))² = | 10 (X)W(y X1112
W IX) Ep. (W X)]
< 2 E. Ep. (W X)] Ep. W(y X)
Integrating over V, this gives
E 1=11 E. Io,,
(X) x)12
du S 20² / Ep. W(v | X) ))
W X) Ep. [W X)]
du
E W X)]
20 20'2(p,; W),
which yields the claimed bound.
E.3 Proof of Corollary 1
For any W E Wariv,e the s-LDP condition from Eq. (2) can be seen to imply that, for every E ),
W(y xT) Wyy x²) < (e - (y xz), Vz 23 E X
By taking expectation over 2y then again either over 22 (all distributed according to p.), this yields
(w æ) - Ep. (W(v (y) X)] S (e 1) (W X)],
d'.
Squaring and taking the expectation on both sides, we obtain
Varp. (W X)] < (ef 1)a Ep. (y x)]².
Dividing by Ep. (W X)), summing over y V, and using fy Ep. (W(y) X)] du gives
/ Varp. (W X)]
E. ( X)] du < (ee 1)² / Ww x)] = (e 1))
thus establishing (6). For the bound of ef, observe that, for all y E V,
Varp, X)] < Ep. [ x) < e min W(y I) (W(v) X)]. xEx
27

---

Hence
Varp. ( X)] W X)] dp See
/ ( x) e.. ZEd
yeu
min W Wy dp Se min BEx
The bound (7) (under Assumption 3) will follow from (5), and the relation between differential privacy and KL divergence. Indeed, the mutual information [p.; W) can be rewritten as the expected (over
X Pz) KI. divergence between the distribution p Wix = ( X) over y induced by the channel W on input X, and the distribution p == Extop [W( X') over Y induced by the input distribution p3 and the channel W:
In W(Y X) Ex [WY X
]]
(p:: W) Ex-p, [DD W. "Ipp ) = Ex-p,
By Eyap w.
but the E-LDP condition from Eq. (2) guarantees that the log- ligllikllihodd ratio in the inner expectation is (almost surely) at most e, that / (psi W) I for every and W E Wyprime, This yields (7).
E,4 Proof of Corollary 2
In view of (4), to establish (8), it suffices show that
Varp, (W Ep. [x
S 1 for every y y. Since
Wyy æ) E (0, 1] for all E X' and E V so that
Varp. [W X)] S E. [W x) S P. (W X)).
The second bound (under Assumption 3) will follow from (5). Indeed, recalling that the entropy of the output of a channel is bounded below by the mutual information between input and the output, we have [(p=; W) I (p ), where " [ X)] the distribution over y induced by the input distribution P. and the channel W. Using the fact that the entropy of distribution over y
most log [)] (5) gives (9).
F
Missing proofs in Section 4
F.1 Proof of Lemma 1
Given an (n, -estimmttor (II, 0), define an estimate 2 for Z as
ž = argmin
0. 0(Y U1
262
By the triangle inequality,
|02 - 0211, - 10 - 0( -0r-0 OOrrmU)| + 102 0(X) U)) 52|(0(r (000", 02|1
Since (II, 8) is an (n2 - under lp loss for Pe.
Ez E |10z [
< 2n' Pr(P2 Pz E Pel + max "f2'
10, - Pr(pp $ Pe]
2 +42y0 1 7 3
(38)
T 4
< 4py0
(39)
where Eq. (38) follows from Assumption and Pr[pz E 10121-7/4 Next, for p e oc).
by Assumption 4, ||0 8g
1|
Σk 1 {z+ # 3.}. Combining with Eq. (39) this shows rk
that 1
7% E Pr Z + 2, 7
Furthermore, since the Markov relation Z, (Y", U) 2, holds for all i, we can lower bound Pr| Z, + 2g using the standard relation between total variation distance and hypothesis testing as
28

---

follows, using that r - 1/2 in the second inequality:
Pr 2i + 2,
2 r Pr
2i =-=11 -1
Z: - 1
+ + - (1-r) 2: = Z: = -1]
2 r Pr 2, = -1 2, 2, +r 2, = 1 2 = -
2 r drv - p
Summing over 1 si and combining it with the previous bound, obtain
3 1
_ Tk i=1
Pr
21 k Σ
drv pti
yn 1m
4
and reorganizing proves the result.
G Missing statements and proofs in Section
G.1 Proof of Theorem
Fix p E [1, 20). Let k d, 3 = (-1,+11) and r z and suppose that, for some y E (0, 1/8]. there exists an (n, -estsmmmto for Ba., under Ep loss. We fix a parameter y E (0, 1/2), which will be chosen as a function of y; d. p later. Consider the set of 2d product Bernoulli distributions {Ps)sez where p(p)) μ4 72 + 1a) (so the sparsity of the mean vector is equal the number of positive coordinates of 2). We have, for 2 2.
d
p2(x) 2d i=1
1 + 2
+ 5
x x X.
follows for 2 Z and [d] that
P20 (x) 1 (1 - 2; 2;)x;
(x(x) 11 1 1 + 21)00
2,20
Po(x) (1 (x)
+ 71 + 2,)
(40)
where (2,)(x)) = 1+ 1+17(1+a))or
7::3;
We verify that, for #
72
E (X)] O, Ep. [x). 1- --2 +
and Ep, (X)) (X) 0,
so that Assumptions 1 and 2 are satisfied for a² = 272. Moreover, using, e.g., Hoeffding's lemma (ef. [9), for < 1, the random vector (X) = (X)) is "لー subgaussian. Thus, Assumption holds as well, and we can invoke both parts of Theorem 2.
Let ||=||,, := Hi [d] 2 1H.. that || Σí [1 2,)= || The next claim, which follows from standard bounds for binomial random variables, states that when Z Rad(r) uzz is s-sparse with high probability.
Fact Let ~ Rad(r) @d, where rd 2 4 log d. Then Pr Pr[11 S 2rd]
2 1 T/4.
Hence the construction satisfies Prz P2 E Ba,, S 1 T/4, as required in Lemma
We now choose ? =<(p)
1y E (0, 1/2], which implies that Assumption 4 holds since
[3/2]1/
t ((((::),u(p:))) (z, 1/0 = =47 (dHamm (2, z!) (
1/P
rd
Therefore, we can apply Lemma as well. For Wprriv,, we prove the two parts of the lower bound separately, depending whether E < 1. First, upon combining the bounds obtained by Corollary 1 and Lemma (specifically, for the former, (6)), we get
d < 112na (e 1)²
29

---

whereby, upon recalling that a² = 22?. and using the value of y (p) above, it follows that d s 22 S 448n78e,
d(s/2) 3584 reee - 1) 5²
Thus, (B W n) = Ω
for E (0, 1]. For the second part of the bound, which dominates for > 1, observe that Assumption holds with o² == (I~22y² S 2y²; allowing us to apply the second part of Corollary 1, (7), which as before combined with Lemma yields
de2/y ne²
and again from the setting of we get (B W n)) = 92 .2(v
ds3/v nE
Similarly. for Weomm. again since Assumption holds with 0² s 227?, upon combining the bounds obtained by Corollary 2 and Lemma 1, we get
ds 28672mé S 72,
which gives (Ba,s Weomm.. nt) = O ds3/y 1). Finally, note that for 2 d, the lower bound follows from the minimax rate in the unconstrained setting, which can be seen to be ((vs30 log(2/s))) [28, 30]. This completes the proof.
nf
This handles the case p oo). For p = oo, the lower bounds immediately follow from plugging p log in the previous expressions, as discussed in Footnote 3.
G.2 Proof Theorem
We denote the mean by instead of 0, denote the estimator by j., and consider the minimax error rate (9 W,n) n) of mean estimation for Pe = Ga.s using W under lp loss.
Proof of Theorem 4. Let & denote probability density function of the standard Gaussian dis- tribution (00, I). Fix E x1). Let k = d. 2 1-1, +1]4 and T 2 and suppose that,
for some 7 E (0, 1/8], there exists an etttiimar for Ga.s under E, loss. We fix a param- eter := (p) = (s/2)1/r E (0, 1/2], and consider the set of distributions {p=).ez of all 24 spherical Gaussian distributions with mean /² == 7(2 1a), where 2. Again, note that ||mI||o = Σ [ 1] = || + and Fact 2 applies here too. Then by the definition Gaussian density, for 2 E Z,
(= = - >
11x21///2 (a, sp(x).
(41)
Therefore, for z E 2 and E [d], we have
P Pa (x) = 2y 21 px(x) = (1 + 0x,(2)) pz(x),
(42)
where (x,;(x) = 1 2ra By using the Gaussian moment-generating function, for * j.
Ep (x), =0 Ep. [... = = - and E.,,
= 0,
so that Assumptions and are satisfied for a² A12 - By our choice of y and the assumption on one can check that Assumption 4 holds:
(p(p(p)), u(p::) 47 (H)mm(z,2)) 1/p
Td
Moreover, similar to the product of Bernoulli case, using Fact 2, we can show that Prz (pz E Gd.s 1 7/4. This allows us to apply Lemma 1.
30

---

G.2.1
Privacy constraints for E (0,1)
For Wprin,e, upon combining the bounds obtained by Corollary I and Lemma 1, we get
d S 112ma (e - 1)²
whereby, upon noting that a² y (()) above, follows that
4r - S 8y2 holds since S 1/2, and using the value of
d(s/2)²
7²
14336 n2(e - 1)
Thus, (g,,s W n) ?
// ne²
A This establishes the lower bounds for Wprives
(Recall that the bound for oo then follows from setting p = log d.)
G.2.2 Communication constraints, and privacy constraints for 2
For these cases, to prove a lower bound with the desired dependence on é or É, we will need to use the tighter bounds in Corollaries and 2 which hold only under Assumption 3. This, however, leads
to an issue: the random vector (X) = (d=.a( (X) (X)) ){E(d)) is not subgaussian, due to the one-sided
exponential growth, and therefore Assumption 3 does not hold.
To overcome this and still obtain a linear dependence on (or s) (instead the suboptimal 2 (or e )), we will consider instead the class of "truncated" Gaussian distributions, whose corresponding functions are subgaussian; and argue that these truncated distributions are close enough to the original Gaussian distributions such a lower bound in the truncated case implies one in the original Gaussian case.
In particular, we consider the following collection of truncated Gaussian distributions. For E 2, let РN be the density function spherical Gaussian distribution with mean μl= as defined Eq. (41). For truncation bound B, let Pz,8 be the distribution of X P= conditioned on the event that || < B. That is, we have, for x E Rdd
Px) = (=) B},
where C₁ = 1/Pr || < B]. Then the following bound follows from standard Gaussian concentration bound on each dimension and a union bound over all dimensions.
Fact 3. Setting B = AvIn(dn), we for every = E Z, dr < d'n
Let P be the distribution the messages obtained by executing the protocol when each user gets a sample from Pa,B and let the corresponding mixtures be denoted by p and p Then we have
drv p.T.pp" p
< drv B+ PiiB drv Pti Thi
y : Pti.B) drv Aerv(p-) yd (".....""")
< drv
P+i,Br p
y" P-i.B
max dry P3 y" yn
P2,B)
+rV (P....."))
< drv
pn P p p
max drv P P @0
I drv
(PH5,B P P
2n dT (=..B.P.)
$ <dyv
F P4.,B: P
YR
2
d
The third inequality follows from data processing inequality and the fourth incquality follows from subadditivity of TV distance.
Combining this with Lemma 1, for any protocol that correctly learns the Gaussian family, must have
drv PHr.B. D D
(43)
31

---

Next we show that the ø functions corresponding to Ps,B'S ' are subgaussian and establish the corresponding upper bounds on the average information bound above. Note that
P (z)
Czor 2yziei e 1 s B3 C2
2
(44)
p x
By the inequality lab 11 S |a|
16 - 1 + la - 1/, we have have, for all E 2,
Cze0
1
1
Cze:
1| +
$
+
Pr
[||
I B] B
C2
C2
C₂
Prxmp.e.llaa S
X-p:
10
d
Moreover, for all 2 E 2, for 7 S 3B
e 2y 20 f11=1100 S B} - 1 S 22yB -1 S leh -1| 11
(45)
Hence, applying the inequality lab 1 v |a| - 1| + la 1 again Eq. (44), we have for 7 37
10 1 R (1) S 12 d'n Thus, we get that for all = 2,i E [d], o subgaussian with proxy oB = 12yB + Z..
Under communication constraints, applying Corollary 2, we get
1 Σ drv (prtppii..PP.. )) S d
14 onnl.
To conclude, we observe that by plugging our setting of = (p) in the above inequality, we must have
dss22)²
14336 n B
in order to satisfy Eq. (43), hence proving the desired lower bound. The lower bound for LDP with 8 > 1 follows similarly by applying Corollary 1.
G.3 Detailed results for discrete family
We derive a lower bound for E, (Ad, W, the minimax rate for discrete density estimation, under local privacy and communication constraints.
Theorem 6. Fix E oo). For 0, and l 2 1, we have
d2/9
( - Ne=)
Ep(Ad, Mypriv,s ,n) 2 "n(le= - -122 1
A1
(46)
and
d3/D
Ep(Ad. 8 .n) 2
n2 A
A1
(47)
n2
In particular, for n((e= - 10- d and n2 A d) > d,, the first term the corresponding lower bounds dominates. Before turning to the proof of this theorem, we note that Corollary 3 and Corollary are direct corollaries of the theorem.
We now establish Theorem 6.
Proof of Theorem 6. Fix p E [1, oo), and suppose that, for some ? E (0, 1/16/ there exists an (n, esttimatoo for Aa under Ep loss. Set
-
D dd
167
32

---

and assume, without loss of generality, that D is even. By definition, we then have y E (0, 1/ and D S d; we can therefore restrict ourselves to the first D elements of the domain, embedding Ap into Aa, prove our lower bound.
Let & = 2. 2 (11,+1) and r = 2 and suppose that, for some 7 (0.1/(16D\1//)) there exists (n, -esttmmatto for Åp under Ep loss. (We will the fact that 7 S (1((1D1-)//) for Eq. (49) be valid distribution with positive mass,
will need ly| D: and to bound a?
later on, as we will require |r| S 2b.) Define 7 = (p) as
7(p) == 4 4.2%/py
(48)
D2/PP
which implies E ()2)) Consider the set of D-ary distributions P Discrete {p=}=Ez defined as follows. For E 2, and X [D]
if x 2i,
(x)
D
(49)
if x 2i 1.
1
For E and i E [D/2], we have
2D7z
2D72i
P2 (x) 1 Dyzi
1xx=
+
11x= - -1] p=
Dyzi
(1 + (z)(())))
(50)
where
2Dy
22.1 (x) = 24 1 D2
((1 Dyz)
2i 2 (1-Dyz)](fz 21)).
Once again, we can verify that for j
Ep. [x)] Ep. (x) = 8-2 722 and Ep, (X)s = 0,
so that Assumptions and 2 are satisfied for a² == 16>2 (using that Dy S 1/2 to simplify the bound)." 10 Thus, invoke the first part of Theorem 2. Note that Assumption 4 holds, since
(p(P.. Ps.) = cHam (2, 2) = 47 ddomm (=.=") 1/p Therefore, we can apply Lemma as well.
DD
For Wpriivee by combining the bounds obtained by Corollary and Lemma 1, we get
D < 56na² ((e" - 1)2 A Ae
whereby, upon recalling the value of a² and using the setting of = T(p) from Eq. (48), it follows that
D
f/p 2/(p-11)
2
7168 2 n((e Ae)
n((e - 1c²
Thus obtain the bound Eq. (46) claimed.
Similarly, for Wecomm.t, upon combining the bounds obtained by Corollary and Lemma and recalling that [}]| 2º, we get
D
7168
22/P n2
which gives Ep W.oom.. n) 22
a/v
1=1
concluding the proof.
n2r
10 is worth noting that Assumption 3 will not hold for any useful choice of the subgaussianity parameter. 11 Finally, note that could replace the quantity 2f above by 2 A d. or even 2 as 2 D there no additional information any player can send beyond the first log, D) bits, which encode their full observation. However, this small improvement would lead to more cumbersome expressions, and not make any difference for the main case of interest, p 1.
33


Reviews:
[{"review_id": "XXvPeejE4v", "reviewer": "Reviewer_D6mk", "summary": "The work considers the problem of proving sample complexity lower bounds for parameter/density estimation in a distributed setting with information constraints (local privacy, communication constraints etc). What distinguishes this paper from prior work is that it focuses on the scenario where there is interaction between the users who share their data. Thus, while the data-points are initially generated in an i.i.d. fashion, when the time comes for the data-points to be subjected to the information constraints, the results depend on previous users' actions.\n\nThe authors develop general tools for obtaining lower bounds in this setting, where the main challenge involves dealing with the dependencies implied by the interactions between users. The main tool developed is a lemma that is essentially reminiscent of Assouad's method that is adapted to the setting of sequentially interactive distributed protocols with information constraints. The resulting framework manages to capture various existing techniques such as strong data-processing inequalities and bounds derived using the distributed version of the Bayesian Cramer-Rao bound know as the Van Trees inequality. The paper also includes applications of these techniques to a number of estimation problems, while the derived lower bounds are in most cases complemented by nearly-matching upper bounds. Finally, there's a description of how the techniques could be adapted to work in the fully interactive setting as well.", "questions": "I have one question. The applications given in this paper within the context of parameter estimation for high-dimensional distributions all involve independent marginals (binary product distributions, spherical Gaussians). Additionally, the lemma the proofs of these statements rely on (lemma 3) is an analogue of Assouad's method. Assouad's method assumes that the family of distributions considered as part of proving the lower bound are parameterized by the vertices of the boolean hypercube, with each coordinate being drawn independently. This frequently ends up limiting the applicability of the method to problems involving distributions with independent marginals. Is this a limitation of the work, or is there evidence the method can lead to tight lower bounds even with non-product distributions (e.g., for Gaussian covariance estimation)?", "limitations": "This is a purely theoretical work with a focus on lower bounds. Thus, there is no apparent societal impact (positive or negative).", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This is a quite strong paper with technical contributions that improve our understanding of statistical estimation tasks in the distributed setting. The work provides both techniques (which are presented in a quite general way) and applications (which confirm the effectiveness of said techniques). The applications include the fundamental tasks of mean estimation for binary product distributions and Gaussian distributions under the $\\ell_p$-norm, as well as density estimation for discrete distributions. The work is also notable for identifying mistakes in previous papers where some of these results were claimed and using the developed framework to fix the proofs. Finally, the writing is very clear and the work is clearly positioned within the overall literature.", "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 the very positive assessment of our work. We refer the reviewer to the global response for our discussion on generalizing the technique beyond distributions with independent marginals."}, {"review_id": "dySaxMylJH", "reviewer": "Reviewer_DETb", "summary": "This paper studies distributed parameter estimation under local information constraints. In this problem, independent samples $X_1,..., X_n$ are generated from an unknown distribution $p_\\theta$ from a parametric family $P_\\Theta$ of distributions. The samples are not accessible directly, rather available is only partial inofmration $Y_1, ..., Y_n$  generated by passing the original samples through classical channels $W_i$. The goal is to estimate the underlying parameter $\\theta$ by accessing $Y_1, ..., Y_n$. The channels can be interactive, dependig on the past observations. They also local information constraints,  including communication constraints, and privacy constraints. \n\nThis paper derives lower bounds on the sample compelxity of this problem in a general framework. Moreover, this work explores applications of the general bound to problems of high-dimensional mean estimation and distribution estimation, under privacy and communication constraints, for the entire family of $l_p$ loss functions for $p \\geq 1$.", "questions": "As another point, the current approach focuses on a finite perturbation subset of $\\Theta$. How does this approach work for continuous parameter space $\\Theta$ ? Do we need to make sure that the Z space is a good representation of $\\Theta$? ", "limitations": "See weaknesses. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem formulation and the related results are substantially general and can be used in various problems involving different constraints. \nThe paper is rigorous and well written. ", "weaknesses": "It is not clear how significant the generalization is compared to previous works (i.e., reference [4]). Is the paper generalizing [4] to $l_p$ loss functions? If that is the case, I am not sure how important that is beyond a mathematical curiosity. \n\nMinor comment: it looks like that the symbol $\\wedge$ is not defined. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed reading and acknowledging the generality of our technique. Below we address the questions raised by the reviewer.\n\n#### ***The significance of the generalization compared to [4]***\nWe stress that the results and techniques of [4] are specific to discrete distributions: extending these techniques to handle general distribution classes (e.g., high dimensional distributions) is a non-trivial task. For example, for high-dimensional distributions, to get the correct dependence of $d/\\ell$ under communication constraints, we use a measure change bound (Lemma 3 in the appendix) to prove an upper bound of $\\log|\\mathcal{Y}|$ instead of $|\\mathcal{Y}|$ in the information contraction bound (see Corollary 2). For discrete distributions, the latter will be sufficient. Moreover, the proof of the result in [4] relies on the sum of mutual information as a key step, which will inherently cause an “bounded ratio” assumption in the distribution family similar to [16]  (see details in the response to reviewer Zd1o regarding comparison to [16]). We resort to average TV distance as the discrepancy measure to remove this assumption. This being said, [4] also provides bounds for *testing* (and not just estimation), which our paper doesn’t include.\n\nAs such, our paper is a considerable generalization of [4], going way beyond the simple extension to other $L_p$ norms.\n\n#### ***How does this approach work for continuous parameter space? Do we need to make sure that the $Z$ space is a good representation of $\\Theta$?***\n\nYes, indeed. Making sure that the $Z$ space captures the hardness of $\\Theta$ is an important step for using our framework to prove information-theoretic lower bounds. This typically requires an understanding of the structure of the parametric estimation problem, which is also necessary for proving lower bounds for parameter estimation in classic settings without local information constraints. Our framework captures the additional cost imposed by local information constraints on top of this.\n"}, {"review_id": "C7SjnbZd3q", "reviewer": "Reviewer_7efN", "summary": "This paper studies parameter estimation problem in a setting with the following two important assumptions:\n1. Raw samples X_i's are generated from a certain parametric distribution, however, they are not directly observed. Instead, Y_i's which are generated from channels subject to certain constraints are observed. These constraints can encapsulate various problems of interest, notably communication constraints and local privacy. \n2. Interaction is allowed. That is, Y_i's are generated with memory. \n\nThe main result is a general abstract upper bound on the sensitivity of the transcript (i.e., public view Y_i's and common randomness if any) of the interactive protocol. \nThis, upon nontrivial specification, yields a suite of tight or nearly tight impossibility results for problems mentioned above. ", "questions": "Major questions:\n1. Is it possible to explain why in the main bounds (Theorem 1 & 2), TV distance was used? Is this the only reasonable choice? If so, why?\nIf not, is using other distance/info measure beneficial in any way, e.g., simplifying the proof, improving leading constant factors, etc.?\n\n2. I saw that most examples in this paper are regarding product (or \"product-like\") distributions (e.g., product binary distribution, isotropic Gaussian). And my shallow understanding is that this seems to be a limitation of the technique. \nThis question may go beyond the scope of the paper, but I'm wondering if it is possible to obtain similar results when certain structured correlation is present. \nE.g., Gaussian with general covariance, or simple temporal correlation such as Markovian structure. \n\nOther comments:\n\n1. Line 28, \"local information constraint\". I'm not familiar with this line of work and this may be a silly question. Could the authors offer some examples of non-local/global constraints?\n\n2. I feel like already in line 44, the buzz word \"Assouad\" should have been mentioned. This is a rather standard tool and a general audience can smell that when reading upon line 44. \n\n3. Mysteriously the line breaks at 193. \n\n4. In Equation (2), the Gothic letter under the first sup was defined in footnote 2. It took me a while to find it. Perhaps upgrade this footnote to the main text?\n\n5. To information theorists the notation y^t (perhaps more commonly: y_1^t) for (y_1, ..., y_t) is common but I'm not sure how standard it is to a general reader, especially given that this can be confused with the t-th power of a number. \nI encourage the authors define this notation somewhere. \n\n6. The notation p_Z^{Y^n} denotes the density of (Y^n, U), not just Y^n. Somehow U is dropped. Is there a reason for doing so?\n\n7. In Equation (3), the integral is against y w.r.t. mu. Sometimes it might be slightly more clear to explicitly write $\\mathrm{d}\\\\, \\mu(y)$. \nAlso, this measure mu was defined in footnote 2, which is somewhat hidden. \n\n8. A typo on line 359, double commas following \"i.e.\". ", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I'm not an expert in this field. \nThough the main text is somewhat dense, I found it pretty accessible. \nMost importantly, the results seem pretty satisfactory. ", "weaknesses": "I don't see obvious weaknesses. \nPlease instead see my questions below (most of which are very minor). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed reading and suggestions on improving the presentation of the paper. Below we address technical concerns raised by the reviewer.\n\n#### ***Is it possible to explain why in the main bounds (Theorem 1 & 2), TV distance was used? Is this the only reasonable choice?***\nThanks for the great question. Here we discuss three commonly used discrepancy measures, including TV distance, Hellinger squared distance ($d_H$), and mutual information (expected KL divergence). In general, it holds that $d_{TV}^2 \\le d_H^2 \\le d_{KL}$. Our main bounds also hold if we switch to $d_H^2$, which is also how Theorem 1 is approved (see Appendix E.1). Further relaxing discrepancy measures to mutual information (or KL) is trickier. In particular, [16] (as referred in our paper) uses mutual information as their discrepancy measure, and as a result, their bound would require an additional “bounded ratio” assumption in the distribution family, which fails for the sparse Gaussian family (see details in the response to reviewer Zd1o regarding the comparison to [16]). To summarize, both $d_{TV}^2$ and $d_H^2$ could be used, and would lead to similar results, comparable both in terms of proof length and resulting constants (which, for the sake of this paper, we didn’t focus on optimizing). TV distance was chosen here mainly because of its convenience and more widespread use.\n\n#### ***Examples of \"non-local constraints.\"***\nThe central version of differential privacy [Dwork and Roth 14] requires that a private algorithm should output similar outputs for neighboring datasets (those differ by at most one data point). The constraint cannot be expressed as a local constraint to the best of our knowledge.\n\nAnother type of “non-local constraint” would be adversarial corruptions of data (see, e.g., https://sites.google.com/view/ars-book/): while one can model the Huber contamination model as a local constraint (as each data point is corrupted in an i.i.d. fashion), the common “strong contamination model” which allows an adversary to corrupt say 10% of the samples (of its choice) in an arbitrary fashion is not a local constraint, as it allows for arbitrary correlations among corrupted samples. \n\n#### ***... if it is possible to obtain similar results when certain structured correlation is present. E.g., Gaussian with general covariance ...***\nSee answer in the global response.\n\n[Dwork and Roth 14] Dwork, Cynthia, and Aaron Roth. \"The algorithmic foundations of differential privacy.\" Foundations and Trends in Theoretical Computer Science 9.3–4 (2014): 211-407.\n"}, {"review_id": "jv2V5oPDEg", "reviewer": "Reviewer_VD3C", "summary": "This work investigates the distributed parameter estimation problem under local information constraints such as communication constraints, local privacy constraints, and restricted measurements. The authors focus on information-theoretic lower bounds for the minimax error rates of these problems and present \"plug-and-play\" lower bounds that can be applied to various estimation problems. In addition, for most cases, the lower bounds are complemented with matching upper bounds.", "questions": "no", "limitations": "NA", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work presents a unified framework for deriving a variety of minimax lower bounds for various families of distributions under local information constraints for the distributed parameter estimation problem. Additionally, matching upper bounds have been provided to demonstrate that the lower bounds are tight for most settings.", "weaknesses": "It would be beneficial to see a table displaying the lower/upper bounds for the various cases considered in this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments. We will improve our paper based on the suggestions in future revisions."}, {"review_id": "kljcB1Mafx", "reviewer": "Reviewer_Zd1o", "summary": "This paper discusses parametric estimation under a communication setup. This setup adds variation to classic parametric estimation and focuses on the setup $\\theta \\to X^n \\to Y^n$ where the goal is to estimate $\\theta$ given $Y^n$, which is generated in an interactive, sequential manner with $Y_i$ possibly dependent on other signals. \n\nThe main result of this paper is Theorem 1, which gives an information contraction bound. With additional assumptions on orthogonality and subgaussianity, the paper's next result is Theorem 2, which gives two corollary information contraction bounds expressed in terms of variance, mean and mutual information terms relating to channels.\n\nThe authors then provide several examples of tightness (and near tightness) for these bounds by looking at minimax rates for examples such as product Bernoulli, sparse Gaussian, and discrete distributions under information or communication constraints. \n\n", "questions": "1. While the paper focuses on *interactive* protocols, it is curious whether similar techniques can be applied to the general parametric estimation model (i.e., in the setting where Y = X) and achieve tighter lower bounds than previous works, considering the techniques used in this paper do not depend on \"bounded ratio\" type assumptions as claimed in the paper. Would it be possible to use results in the paper to achieve significant improvement to classic minimax bounds for sparse/non-sparse Gaussians with non-identity covariance $\\mathbb{I}$ such as in the cases where covariance matrix eigenvalues are largely varying (i.e., on a different order)? \n\n2. How much are we sacrificing by using the inequality in (30) within the supplementary material? Would not dropping the second term in the denominator give improved results?\n\n3. How limiting is the assumption of Assumption 4 and its corresponding Lemma 1? In other words, how easy is it to find $\\theta$'s that satisfy this assumption?\n\n4. It may be beneficial to add some references to the parts of the paper where it is claimed that previous works regarding bounded ratio type assumptions are \"flawed\" (for example, maybe previous papers that analyze this flaw).\n\n\nSome additional suggestions/typos/confusions:\n\na. The term $S$ is not clearly defined in Equation (2). It may help to add some description of what this means.\n\nb. Line 193 seems to be incorrectly formatted.", "limitations": "There does not appear to be any negative societal impact associated with this paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**: The paper builds upon the classic framework of parametric estimation under an interactive framework. While the problem setup itself is not original, this paper contributes new findings to minimax theory for these setups, particularly with communication and privacy constraints.\n\n**Quality**: The paper is nicely written, and the authors explain the setting and results well. No glaring issues were found with regards to technicalities.\n\n**Clarity**: Overall, the paper is cleanly written, bar some comments stated in below sections. \n\n**Significance**: The interactive parametric estimation problem considered by the paper is an interesting one and is directly relevant to the community. ", "weaknesses": "Overall, the paper itself is quite nicely written and the topic is interesting. Some comments regarding weaknesses include:\n\n1. The paper is somewhat structured reversely in many scenarios, where the paper references equations that appear later on in the paper. This may cause a little bit of confusion for readers.\n\n2. It may be helpful to highlight the difference in technical contributions (for example, proof techniques) between this work, [4], and [16], considering the problem setup is quite similar and both this paper and [16] \"build upon the framework presented for the discrete setting in [4]\". What are some scenarios where the minimax results in this paper can significantly improve upon results in [16]?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed reading and acknowledging the novelty and significance of the paper. Below we address technical questions raised in the review.\n\n#### ***It may be helpful to highlight the difference in technical contributions (for example, proof techniques) between this work, [4], and [16], ...***\nFor comparison of our result to [4], see response to Reviewer DETb. While [16] does build on [4] as well, our goal and results are significantly more general: our objective was to obtain results under minimal assumptions, and in particular without any “bounded ratio assumption”. This is in particular apparent in the results of [16]:\n\n- Their Assumption 2 (“Likelihood ratio condition”) is exactly such a bounded-ratio assumption.\n- As a result, their bound for the sparse Gaussian case (Theorem 3 in their arXiv version: https://arxiv.org/abs/1802.08417) cannot use their general theorem (as the sparse case does not satisfy that assumption), and so they must use a completely different argument (Appendix D of their paper) which is restricted to the *non-interactive* case (termed simultaneous message passing protocols in their paper).\n\nThis is to be contrasted to our general approach, which, free of that assumption, directly applies to sparse Gaussians in the interactive case as well (see lines 353-354, and Theorem 5 (Section G.2) of the supplemental of our paper)\n\n#### ***Would it be possible to use results in the paper to achieve significant improvement to classic minimax bounds ...***\nOur result can be viewed as an extension of classic methods for proving lower bounds of general parametric estimation problems to the case under information constraints in the interactive setting. Without information constraints, our technique will reduce back to these classic methods, e.g. Assouad’s method. In particular, the “bounded ratio” assumption we get rid of in this work is not needed without these information constraints since the divergence measures will have explicit forms when Y = X and the distribution of X is known.\n\n#### ***How much are we sacrificing by using the inequality in (30) within the supplementary material?***\nWe drop that term to relate Hellinger distance to chi-square distance. It is critical for us, since we exploit the bilinear form of chi-square distance to get a handle over contraction in distances due to information constraints. In all the examples we have seen, this weakening does not hurt us. However, it is of course conceivable that there could be examples where this weakening of Hellinger distance to chi-square distance becomes the limitation.\n\n#### ***How limiting is the assumption of Assumption 4 and its corresponding Lemma 1?***\nThis is a good question, with two (complementary) answers. \n\n- The first is that it is indeed limiting, analogously to the widespread Assouad’s lemma in standard minimax lower bounds: i.e., Assumption 4 does not really restrict further our results than it would using Assouad’s lemma in the “non-constrained” estimation literature. \n- The second is that it is not *really* limiting, in that this assumption (and corresponding lemma) is completely independent from Assumptions 1-3 and our main theorems. Namely, Theorems 1 and 2 (the key contribution of our work) allow to upper bound a given quantity, the average discrepancy (AD), and do not rely on Assumption 4 in any way. Then, Lemma 1 provides a lower bound on this same quantity (AD) (and does not rely on assumptions 1-3): putting the two together gives the minimax lower bounds. But if one found another, different way to lower bound (AD) that doesn’t need Assumption 4 (e.g., via a Fano-type argument instead of Assouad-type), or anything else really, then the same template would go through and one would readily get a minimax lower bound by combining this with Theorem 1 or 2. While we do not provide an alternative to Assumption 4/Lemma 1 in our paper (as this Assouad-like bound suffices for our purposes), such an alternative is entirely conceivable.\n\n#### ***It may be beneficial to add some references to the parts of the paper where it is claimed that previous works regarding bounded ratio type assumptions are \"flawed\"***\nThis is a good suggestion, and we will do our best to incorporate it in the final version. Yet, as several of these flaws were confirmed via personal communication with the authors, we felt it would be awkward (and potentially in violation of the double-blind policy) to include them in the submission."}]

Author rebuttal:
We thank the reviewers for their careful reading of our submission, and are delighted to see their very positive assessments of our work. We will take into account their comments and suggestions in the final version of our paper, and respond individually to their questions below. We first address a question mentioned by several reviewers.

#### ***Whether our techniques could apply beyond identity-covariance matrix or independent coordinates.***

This is, indeed, a very natural question: while we believe our techniques can provide lower bounds for this case (for a suitable family of hard instances, such as the one described in Lemma 6.11 of [https://arxiv.org/abs/1805.00216 ], which is indeed parameterized by a vector of $\binom{d}{2}$ independent $\pm 1$ parameters), such a lower bound would most likely be quite technical, and lengthen the paper significantly. As our main focus here was to establish the general lower bound framework and demonstrate its applicability via a few notable examples, we left these additional applications for future work.


Meta-review: The authors propose a framework for proving lower bounds for high dimensional estimation in the interactive setting with communication constraints.

 The reviewers found the authors contributions in finding a tight and unifying approach (which recovers some well-known lower bounds) significant and well presented. I therefore recommend acceptance.
Decision: Accept (poster)