Optimal Private and Communication Constraint Distributed Goodness-of-Fit Testing for Discrete Distributions in the Large Sample Regime
Authors: Lasse Vuursteen
Venue: NeurIPS 2024 poster (2024)
Keywords: hypothesis testing
federated learning
distributed inference
goodness-of-fit
differential privacy
communication constraint
Primary area: learning_theory
TL;DR: We derive minimax rates for distributed goodness-of-fit testing for discrete distribution under bandwidth and differential privacy constraints in the regime where each server contains many observations.

Abstract: We study distributed goodness-of-fit testing for discrete distribution under bandwidth and differential privacy constraints. Information constraint distributed goodness-of-fit testing is a problem that has received considerable attention recently. The important case of discrete distributions is theoretically well understood in the classical case where all data is available in one "central" location. In a federated setting, however, data is distributed across multiple "locations" (e.g. servers) and cannot readily be shared due to e.g. bandwidth or privacy constraints that each server needs to satisfy. We show how recently derived results for goodness-of-fit testing for the mean of a multivariate Gaussian model extend to the discrete distributions, by leveraging Le Cam's theory of statistical equivalence. In doing so, we derive matching minimax upper- and lower-bounds for the goodness-of-fit testing for discrete distributions under bandwidth or privacy constraints in the regime where number of samples held locally are large.

Optimal Private and Communication Constraint Distributed Goodness-of-Fit Testing for Discrete Distributions in the Large Sample Regime
Lasse Vuursteen
Department of Statistics and Data Science
The Wharton School of the University of Pennsylvania
Philadelphia, PA 19104
lassevOwharton. upw.n.. edu
Abstract
We study distributed goodness-of-fit testing for discrete distribution under band- width and differential privacy constraints. Information constraint distributed goodness-of-fi testing is problem that has received considerable attention recently. The important case of discrete distributions is theoretically well understood in the classical case where all data available in one "central" location. In a federated setting, however, data is distributed across multiple "locations" (e.g. servers) and cannot readily be shared due to e.g. bandwidth or privacy constraints that each server needs to satisfy. We show how recently derived results for goodness-On of fit testing for the mean of multivariate Gaussian model extend to the discrete distri- butions, by leveraging Le Cam's 's theory of statistical equivalence. In doing we derive matching minimax upper- and lower-bounds for the goodness-of-fe testing for discrete distributions under bandwidth where number of samples held locally are large.
privacy constraints in the regime
Keywords: distributed inference, goodness-of-fit testing, differential privacy, com- munication constraint, federated learning, statistical equivalence.
1 Introduction
Federated learning is a fundamental problem in statisties and machine learning, where data is distributed across multiple locations (c.g. servers) and cannot readily be shared due to c.g. bandwidth or privacy constraints that each server needs satisfy. The primary goal in these distributed data settings is to perform single global inference task, such as hypothesis testing, regression, or classification, by aggregating the local information from each server.
Starting a few decades ago, investigations into distributed settings with bandwidth and other informa- tion constraints originated in the electrical engineering community, under the names "decentralized 92 18
decision theory/ / the CEO problem" e.g. [90 12
(58) 87) or "inference under multiterminal compression" (see [88] for overview). These were largely motivated by applications where data
is by construction observed and processed locally, such as astronomy, metcorology, seismology, surveillance systems, wireless communication, military radar or air traffic control systems.
Modern federated learning often involves data distributed across siloed data centers (e.g., hospitals) networks of cellphone users, applied in areas such word prediction, facial and voice recognition, virtual assistants like Siri or Google Assistant, autonomous vehicles, and earthquake prediction [65]
56 73 67 31. In these settings, bandwidth often becomes limited costly resource [57]
Similarly, with advances in electronic record keeping, privacy has become a more and more pressing issue These issues are prominent in tech industry products 32 including many federated learning
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

applications mentioned earlier, as well as in scientific fields like medical sciences [60] and social sciences 69
Methods that preserve privacy have been around in the statistics community for some time, starting in the 1980's 40 41 The current leading formal privacy framework is that of differential privacy (DP), as introduced in [42]. DP is mathematical guarantee, describing whether results or data sets can be considered "privacy preserving" and hence can be openly published. Whilst many other privacy frameworks exist, this notion of privacy holds a prominent position both theoretically and practically, finding application within industry giants like Google [45], Microsoft
[3), Apple 89 as well as
governmental entities such as the US Census Bureau
74
Quantifying the trade-off between privacy and statistical power means that researchers and data analysts can make an appropriate balance between data privacy and meaningful analysis. Similarly, by quantifying the impact of bandwidth constraints, systems can be designed work as efficiently as possible within such bandwidth constraints.
The performance of distributed inference under bandwidth or differential privacy is well-studied for various estimation problems. For instance, distributed estimation under differential privacy has been studied for the many-normal-mmans model, discrete distributions and parametric models in 37 38 98 3), and density estimation [75 59 21,, and nonparametric regression in [23].
Bandwidth constraints have been studied for the many-normas meanns and parametric models in e.g. [0I 39 77 20 99 50 26, 25], as well as nonparametric models, including Gaussian white noise [102] nonparametric regression (22. density estimation 17 4, general, abstract settings (99) and online learning (95]. Distributed adaptive estimation methods under bandwidth constraints, where adaptation occurs to the unknown regularity of the functional parameter of interest, were derived in [82 83 25]. Testing simple hypotheses under bandwidth constraints has been studied by e.g. [92
and under differential privacy constraints by 22
In this paper, we consider goodness-of fit testing for discrete distributions (i.e. the multinomial model) in scenarios where the number of samples received by each server is large. Specifically, we study testing a simple null versus a composite alternative, in the setting where m servers receive n obser- vations each from a distribution on sample space of cardinality d, where n is large comparatively to m and d. Recently, such multinomial distributed data have found many applications in areas that handle very large samples over (possibly also large) discrete domains. For example, in population genetics [71 [6) and computer science; where it is used for e.g. information retrieval [100] 76),, speech and text and classification [55], text mining (24 and large language models [72]. This has
sparked recent interest in studying the statistical decision theoretic properties of the multinomial
model, see 155 for an overview.
Deriving minimax rates for goodness-of fit testing of discrete distributions under bandwidth and differential privacy constraints is particularly challenging when each server holds multiple obser- vations. To date, matching rates have been established only when each machine observes a single observation [ TO 5 (see also our discussion of related work below). The techniques used to derive lower-bounds in the aforementioned paper heavily rely on the fact that each server contains only one observation, see (9. Moreover, whilst tight lower-bounds for the multiple observations case exist for the Gaussian model, the functional analytic techniques used to derive these results heavily rely on Gaussianity, see (85) and [22] for the respective bandwidth constraint and DP lower-bounds. Additionally, lower-bound techniques developed for estimation problems generally do not yield tight impossibility results for goodness-of-fit testing problems (see also the discussion in Section B of the appendix).
We derive matching upper- and lower-bounds for goodness-of-fi testing for discrete distributions under bandwidth and differential privacy constraints in scenarios where the number of samples held by each of the servers is large in comparison to d and m:; md log d/ /n o(1). This is achieved by leveraging the theory of statistical equivalence, as introduced by Le Cam (see e.g. [62 81 for introduction). Leveraging existing results concerning statistical equivalence of multinomial data with a multivariate Gaussian model proven in [30] allow us to show, roughly speaking, that the distributed goodness-of-it testing problem for discrete distributions is statistically equivalent a distributed goodness-of-fit testing problem for the mean of a multivariate Gaussian model, and hence the minimax rate for the former problem the same as the minimax rate for the latter problem, which was established in [85] and [2]. for bandwidth and differential privacy constraints respectively. Furthermore, we exploit the bandwidth constraint distributed setting in which these two models have

---

different minimax rates to show that, when n is small compared to d and m, the multinomial model and multivariate Gaussian model are statistically non-equive equivalent.
The rest of the paper is organized as follows. After a brief section on related work and notation, the article continues with precise problem formulation in Section [ Section 2.1 outlines the distributed framework, for both bandwidth and differential privacy constraints. In Section 2.2 we introduce the problem of distributed goodness-of-fi testing for discrete distributions under bandwidth and differential privacy constraints. In Section 3 the main results concerning the minimax rates are presented. Section briefly outlines the main idea of the proof technique. Section | gives further insight into the comparison between discrete distributions and its comparable multivariate Gaussian model. The article ends with brief discussion of the derived results. In the appendix, the tools of asymptotic equivalence within the distributed framework are presented and the technical proofs are provided.
1.1 Related work
Minimax goodness-of-fi fit testing knows rich literature within the statistics and machine learning
communities, see [46 53 64 80 [2). The d-ary discrete distribution uniformity testing problem
bares a close relationship with "classical" nonparametric goodness-of-ff fit testing in the sense of [14]
79 33
96
and other nonparametrie testing problems, see Section 1.4 in [54) and references therein.
For distributed goodness-of-He testing specifically, much less is known. For multivariate Gaussian models under communication or differential privacy constraints, solutions have been established for the case where each server holds multiple observations. Communication constraints have been studied in B 84 85] and differential privacy constraints [22]. with the authors deriving matching minimax upper- and lower- bounds for the goodness of-fit fit testing for the mean of a multivariate Gaussian model.
For testing in discrete distributions, only the scenario where each server receives just one observation
has been fully characterized in terms of the minimax rate in (9 I0 5). See also [28) for an overview.
In these aforementioned works, the authors derive minimax rates goodness-of-fi testing for discrete
distributions under bandwidth and differential privacy constraints. See [48] 78 11 2 19] for investigations specifically under local DP (i.e. one observation per server with DP constraint).
Nonparametric goodness-of-fe density testing for under local DP is considered in [36] 61], where in [6],, the authors consider adaptation as well. For some investigations into the multiple observations per server case, see
For estimation, the bandwidth constraint estimation discrete distributions in the large sample-per- server case has been studied by (3) who derive matching upper and lower-bounds up logarithmic factors. However, their technique does not extend to the goodness-of-fi testing problem.
1.2 Notation and notions
Throughout this paper, we shall use the following notation. For positive sequences ag and by, we use ag S by to mean that ag S. Cbyy for some universal positive constant C.. We write as x by if both ag S by and by S ag. and ax < by if az/b; o(1).
We denote the maximum of a and b by a V b and the minimum by a A For & E N, [k] represents the set {1, {1..... k). Universal constants and C' may vary between lines. The Euclidean norm of vector e E Rd is denoted by ||w||2. For matrix M E Rdxd, ||M]] represents the spectral norm, and Tr(M) (f) denotes its trace. Ta is the d x identity matrix.
A non-negative sequence Mr is said to be of poly-logarithmic order in non-negative sequences ag, bk, Cb if there exists a constant e such that M4 S (log(aи) log(bs) log(cx))"
Given measurable spaces (X, 2) and ()), 3) a Markov kernel K (between (X' 2") and target (),. () is map K = K(-l.) 2 X + [o. 1] with the following two properties: The map I + K(Alz) is measurable for all E V and the map A b K(Alz) is probability measure on y for every x X.
If S is a random variable on a probability space (X, 2, 8 P), we let pS denote its push-forward measure, i.c the measure defined by 1p$ (B)) ;= (B)). We shall use E and E as the expectation
3

---

operator corresponding to P and Ps. Random variables X,Y, Z form Markov chain X + Y + Z
whenever their joint distribution pxX.X.2) disintegrates as dP(X.Y.Z) dP dp dP2
2
Problem formulation
We begin by formally introducing the general framework of distributed inference.
2.1 The distributed framework
Consider measurable space (X, 2") with statistical model p = {P, E defined on it. In the distributed framework, consider 1...., servers, each receiving data X drawn from given distribution Pf E P. Each of the servers communicates a transcript YO) based on the data to central server, which turn computes its solution to the testing problem T(Y) E {0, 1} based on aggregated transcripts = rejecting the null hypothesis. The transcript generating mechanisms are then given by Markov kernels {K*}, j=-1....mm with the Markov kernel (i.e. conditional distribution) of the transcript y given the data X ( and the randomness U shared by the servers denoted by K (-)x)0)) U). We formalize this in the following definition.
(m)). We shall use the convention that T(Y) = means
Definition 1. A distributed testing protocol for the model P consists of triplet (T,(K*) (24, 2, ",P'')) ,P')),, where {K is a collection of Markov kernels K (/) x xxu -
[0, 1] defined on a measurable space (2/6), (ااا)مم01) ()), T 2 セー {0, 13 is a measurable map and (U, 2, 2 is probability space.
The probability space (u, V (P") is used to (possibly) generate source of randomness (independent of the data) that is shared by the servers. The distributed protocol is said to have no access to shared randomness or be local randomness protocol if TP is trivial) [1]
In abuse of notation, we shall often refer to the entire triplet (T, {K')j=,....,. (4, 2 P()) using just T.
Given a distributed protocol and i.i.d. data from Pj we shall use I to denote the joint distribution of Y (L) (m)),, the data X under pT and the shared randomness U ppU Writing (x(1), (m)) E X let + (AA2,, u) denote the Markov kernel X f- (+(+))() u) (i.e. the product measure). The independence structure of the data yields that PTr the fosh-forward measure of can be seen to disintegrate as
P, and
/ K(A),, u)dP, (x)ap" (u),
Py (A) = (")
where the second equality follows from the independence of U with the data drawn from Pj. The above disintegration of the push-forward measure of Y and the product structure of K can be interpreted (X, T(Y)) forming a Markov chain given U, in the sense of the diagram
X
T(Y).
(m)
The diagram indicates the flow of dependencies. The m servers each obtain data X from Pf- and generate transcript ( based on the data and shared randomness U. The central server then makes decision T(Y) based on the aggregated transcripts Y. For definition of Markov kernels and Markov chains, see Section 1.2
Allowing transeript-enneraiing mechanisms to access both shared and local randomness is impor- tant for our analysis, as shared randomness has been found to yield strictly better performance in distributed goodness-of-fit testing, e.g. 10 44 85 22 Shared randomness protocols
be seen as a subset of common interactive procedures, such as sequential and blackboard protocols
o is the trivial igma--alebra (meaning U ~ pd degenerate random variable)

---

(see e.g. (6]. The aforementioned paper shows that for discrete distribution goodness-of testing in the single observation per server case, sequential and blackboard protocols offer no benefit over shared randomeess protocols. Similarly, for mean shift problems in the multivariate Gaussian case, no advantage of sequential protocols over shared randomness protocols is known, except in the case of estimation with unknown variance [? ]. Since we study goodness-of-fit testing for discrete distributions in the known variance, we restrict the setting of the main article to local and shared randomness protocols only. Nevertheless, our theoretical framework is general enough to handle interactive protocols, which we discuss in Section A.2 of the appendix.
case by comparing with a Gaussian model with
Next, we introduce the notion of a bandwidth constraint in the distributed setting. Definition 2. A distributed protocol is said to satisfy a b-bit bandwidth constraint if its ker- nels (K*) -== are defined on measurable spaces (yG), (g) satisfying [ I 2 for j
We use T and testing protocols with communication budget b per machine, respectively.
Th SR to denote the classes of all local randomness and shared randomness distributed
Lastly, we introduce the notion differential privacy in the distributed setting. We will be focusing on the notion of differential privacy as put forward by [3 44). Differential privacy provides mathematical framework that guarantees preservation privacy in a notion akin to cryptographical guarantees. Formally, differential privacy constraint transcript in setting is formulated as follows.
Definition 3. Ler E 2 0,8 2 0. The transcript ( generated from K3, u U is said to be (e, diffferrrentlll private if
(3 u) S e' K* u) +
for all A y x, a' E X, i (1,.....11)
A distributed testing protocol {T, (T. )ー (u, 2 V,I"),, }, is said be distributed (c, (), difffrreeniil private testing protocol if [K* j==1.... { satisfies 2 pl aa.s.
Small values of e and 8 ensure that, even when the transcript y is publicly available, the sample x underlying yū) is unidentifiable We stress that this type of differential privacy guarantee concerns the local data XG) in full, even ( consists of multiple observations. This often referred local differential privacy, where the privacy guarantee regards each server essentially pertaining data to "one indiviual". For a thorough introduction on differential privacy guarantees, we refer the reader to [42]. We also note that the use of shared randomness does not affect the privacy guarantee provided by the protocol, as the guarantee holds even if the outcome of the shared randomness is known.
We use g/(.6) and F.(..5) to denote the classes of all local- and shared randomness (c, 8) diifferrentll private distributed testing protocols, respectively. We note that the machinery developed in Section[A.2 allows consideration both types of constraints simultaneously. In the main text of the article, we shall focus on the bandwidth constraint and differential privacy constraint separately minimax rates for the joint constraints are not known for the Gaussian model we use for comparison to the multinomial model in the main article.
2.2 Distributed goodness-of-ft testing
We start by giving formal deseription of sampling from discrete distribution in the distributed setting. Consider set with cardinality d; for simplicity, take X' fl,.... dd. Any probability distribution such a set can be characterized by an element of the d - 1-dimensional probability simplex gd. defined as
q (qI..... .q........ .a). [0, 11dh
Σ 9: 1==1
In our distributed framework, each server = 1.... m observes a data X taking values in (1....,d) d)"
x01 (x(() x()) Q =Qnar x lid Multinomial(1.g) for g E sd.
(3)
5

---

That is, each server obtains n i..d. draws from multinomial distribution with parameter q.
The statistical decision problem of interest shall be that of goodness-of-fit uniformity testing, i.e. distinguishing the hypotheses
Hu : 9 = versus H1 : E {q F llg - golli 2 p =: Hp:
(4)
where qo (qu1. ................................ -9od) (1/d, ................................ .1/d,...., ../........d........ E ES and
F -=99 "
max; 9i - R R min; 9
(5)
for some fixed constant
The statistical model under consideration shall be denoted by
Q = ( q FF.
We define the testing risk for distributed testing protocol T, for the hypotheses (and statistical model Q) by sum of the type I and worst case type Il error over the alternative class;
Ro(T, Ho) Q T()) sup Qy (1 (1-)()))
SEH,
The minimax testing risk over class of distributed protocols g is then defined as infre. Ro(T, Hp).
is clear that, as p tends to 0, the minimax testing risk should increase. We are interested in finding the called minimax separation rate, or detection boundary, which is sequence p depending the model characteristics n, d, m and / such that the minimax testing risk converges to if < p* or if p >> p"
The minimax separation rate captures how the testing problem becomes easier, or more difficult, for different model characteristics, The minimax rate for the hypothesis above case is p² x vd when T consists of the class of all testing protocols, as was established in 770 and 94
When 9 taken to be one of the bandwidth or privacy constraint classes of tests, i.c. T. and T((h) (c.5) and (c.6) it is sensible expect p" depend on the bandwidth differential privacy parameters, b and (), respectively. In the distributed discrete distribution setupj described above with n 1, such minimax rates have been derived in [ [OO]. We discuss these results in the next section, contrasting them with the minimax separation rate derived in this paper for the case where md log d/ vn o(1)
Minimax rates in the large sample regime
We now turn to the main results of this paper, which concern the minimax rates for goodness-of-ft testing for discrete distributions under bandwidth and differential privacy constraints in the large sample regime. We shall show that the minimax rates for the distributed multinomial model under bandwidth and differential privacy constraints are the same as the minimax rates for d-dimensional distributed Gaussian model, derived in [85 and 22], respectively.
The first theorem establishes the minimax rate for the distributed multinomial model under bandwidth constraints. A proof can be found in Section of the appendix.
Theorem 1. Consider sequences = b = bw d = du and n = nu such that mdd - oo whilst
mn log d/ /T "=
Suppose that Pu is nonnegative sequence satisfying
Vd Vmn
p²
(6)
Vd bmnn
Then,
for any M, + 00, for any Mo + 0.
inf Ro,T. + Te 3
Haspp)

---

When considering the class of only local randomness protocols (i.e. replacing Fsh with Fi in the above display), the minimax separation rate is given by
d3/2
p² (d (d
A
V mn
The theorem above shows that the minimax rate for the distributed multinomial model under band- width constraints is given by (6) in the case of access to shared randomness, and 7 in the case of no access to shared randomness. Both rates are the same as those established for signal detection problem in d-dimenniionl distributed Gaussian model, as derived in [85]. Theorems 3.1 and 3.2. In Section 4 we shall provide a proof this result through the notion of statistical equivalence, where explicitly use that the multinomial model is asymptotically similar to specific Gaussian model and a corresponding signal detection problem.
The distributed b-bit bandwidth constraint minimax rate for the hypotheses 4 in the multinomial model with n established in 10
Specifically, they find that
case access to shared randomness, without access to shared randomness.
MEV Ab
(2
Several aspects of this minimax rate are intriguing, First, unlike in the "large case" for the same model and hypothesis (6) and (7)), there is elbow effect. Secondly, the benefit (i.e. "efficiency gain") from an increase in bandwidth is exponential, whereas in the large sample scenario of Theorem Di sub-linear. We shall comment on this "communication super-efficiency phenomenon further below.
We now turn to the distributed multinomial model under differential privacy constraints. As in the case of the bandwidth constraint uniformity testing problem, we shall show that the minimax rate for the distributed multinomial model under differential privacy constraints is the same as the minimax rate for a d-dimensional distributed Gaussian model, as derived in [22].
The following theorem describes that the above rates are the minimax rates for uniformity testing in the distributed multinomial model under differential privacy constraints, for shared randomness and local randomness only protocols, respectively.
Theorem For any sequences
My, d = d, and n ny such that md + 0C,
and log u "2
/n
1/14 e 6 S 1, = 8, x (md) for some p > The minimax separation rate in the distributed multinomial model Q for testing the hypotheses private protocols
using locally (c, 8) (e,))d(ieeeedee -idfifferentially
if f
p² x poly-log(d, m. m.
mnez Ja /mnz
mm
Vmdd
SE<
Vd 7m
in the case of having access to shared randomness. In the case of having only access local randomness, it is given by
mie if
A
p² = poly-log(d, m. n)
Vmn
(10)
dd
if Vmd
Viin
mm
We provide a proof of the theorem in Section of the appendix. As with the bandwidth constraint case, the minimax separation rates for the distributed multinomial model under differential privacy constraints are derived by comparing the model and hypothesis test to a signal detection problem for the d-dimensional distributed Gaussian model. The rates for the latter problem follow from the proofs of Theorems and 22 who describe a more general setup which includes signal detection in the d-dimensional distributed Gaussian model as special case
Also in the case of privacy, there a difference between the one observation per server case minimax rate (n 1) and the multiple observations per server with local differential privacy case. The
"The above rates do not observe all phase transitions present in the more general setup of [22] as it pertains the local differential privacy case in that paper, with = 1/ in their notation.
7

---

minimax rate in the multinomial model for n 1 is derived in 59;
in case of access to shared randomness,
(11)
without access to shared randomness.
Comparing this rate the rate obtained in Theorem 2 we observe phase transitions in the distributed testing problem for multinomial model under local differential privacy constraints which only occurs if the number of observations locally is large compared the cardinality of the sample space.
Deriving the minimax rates through statistical equivalence
The minimax rates for the distributed multinomial model under bandwidth and differential privacy constraints are derived through the notion of statistical equivalence (Le Cam theory), which is powerful tool for establishing minimax rates in statistical decision theoretic problems. In this section, shall provide brief introduction to statistical equivalence, and show how it can be used derive the minimax rates for the distributed multinomial model under bandwidth and differential privacy constraints. Further details on the statistical equivalence and detailed proof are deferred Section A of the appendix.
Le Cam theory is a general framework for decision problems. At the core of this theory is the notion of a distance between statistical models, known as Le Cam's deficiency distance. The objective of this distance is to quantify the extent to which a complex statistical model can be approximated by a more simple one. a model is close to another model in Le Cam's distance, then there is mapping of solutions to decision theoretic problems from one model to the other. Whenever the risk the decision problem is bounded, this means that similar performance can achieved in the two models. Consequently, studying the complex model can be reduced studying the corresponding simple model. For an extensive introduction to Le Cam theory, see e.g. [62 81]. For a
brief introduction; (63 66).
Consider a model f (a collection of probability distributions) on a measurable space (X, 2¹) (the sample space). For this article, consider only models with Polish sample spaces and corresponding Borel sigma-algebras and dominated models, meaning that there exists higma-finite measure μ such that Ps < μ for all E F. This greatly simplifies the definition of deficiency, given next.
Given another model 2= {Q : f F} indexed by the same set F and sample space (2,2). we define the deficiency of P with respect to Q as
oPP Q) inf sup | JEF
(12)
where the infimum is taken over all Markov kernels C: 2' x X + [0, and the probability measure PjC 2 > [0. 1] is understood as P,C(A) == Jaex (A)x))dP,(a This is equivalent to the more general notion of deficiency of (27 for dominated models Polish spaces (see Proposition 9.2 in (68
A(P, Q) max (o(P; 2),0()),))))) ( This semi-metrie becomes a metric whenever P and Q are identified O. Two sequences of experiments P, and Q, are called asymptot- ically equivalent if their difference (PP, 2x) tends to zero as v approaches infinity. Conversely, such sequences shall be called asymptotically nonequivalent if (PP,. Q2) > cas + co for fixed constant c 0.
Le Cam's deficiency distance between P and Q is then defined
whenever o(P; Q) D(O,
In Section A.2 we prove that models that are close in the Le Cam metric (compared to m) have similar testing risks the distributed setup. We leverage this result in combination with the fact that the distributed multinomial model is asymptotically equivalent to d-dimensional distributed Gaussian model, which we describe next.
Consider for E F and = 1,..., d the random variables
x!!) = V +
2(0) 2n
with
z = , (z(,)...,ZZ() N(O, Ia)-
(13)
8

---

Let Pa Pf denote the distribution of X = (x(")
x Let P denote the corresponding
experiment. It is shown in [3) that Q is close to P in the Le Cam metric when d is relatively small compared to n. More precisely, it follows from Theorem 1 and Section in (30 that
d dlogd Vn
A(P, 2) S CR
(14)
where CR 0 is constant depending only on R. For the testing problem in Gaussian model, with hypotheses (4), the minimax rate can be derived using the results of [85] in case of bandwidth constraints and [22] in case of differential privacy constraints. The key tool from which the minimax
rates can then be derived for the multinomial model is the following lemma, which allows comparison
of the minimax testing risks for the multinomial and Gaussian models in regimes where the Le Cam of the appendix.
distance is small. Its proof is given in Section A.2
Lemma 1. Suppose m& @ P) S for @ > O. Then, holds that
inf TE)(P)
R2 (T, (T, H1)
inf Re(T, H1) (E)(Q)
S 20,
where T is either T&e. Tike F(ce)) or g.c.8)
5 Statistical non-equivalence of discrete and multivariate Gaussian distributions
Theorem 1 describing uniformity testing in the large sample regime and the result derived for n = 1, as displayed in (8). shows striking difference terms of the role of the communication budget. Specifically, in the n 1 regime, an exponential communication efficiency is observed, whereas in the large sample regime, the benefit is only linear. this section, we shall provide some explanation for this phenomenon, and shall actually leverage this difference to show that the distributed multinomial model and the distributed Gaussian model are asymptotically non-equivalent: Two models are considered asymptotically nonequivalent if their Le Cam distance remains bounded away from zero, even as the amount of data increases in both models.
The multinomial model is equivalent to a model in which one observes NO) = (N(") N2O)
taking values in (1...., ,.)", where N²(1) = -N()) (xx) = { x(x)))) = k}} Let Q' denote the model generated by the observations NO), This model is equivalent to Q, meaning A(2, Q') 0. To see this, note that for x = (.i,...,,3 xx) E {I,...,,d] ,d)",
@ (xx))=)== ii (x (x)" be (I....d)
4k [ for all Q E Q,
11
after which the aforementioned equivalence follows by the Neyman-Fisher factorization criterion, e.g. Lemma 2 in the appendix. When n is large compared to d, one could standardize the count statisties NG) to obtain a statistic that tends towards d-dimensional Gaussian random vector. When and m are not too large with respect to one can obtain transcripts and corresponding test statistics from these approximately Gaussian vectors, that resemble those one would consider in the Gaussian model, and attain the corresponding minimax rates.
Since the observation NT(1) takes values in (I. the full data can be transmitted whenever there are at least d log2 re-bits are available per server. However, recalling that the observation (r) takes values in the space {I,...,d] which has cardinality bounded above by 2 log, d we also obtain that the full data can be transmitted whenever n log, d-bits are available. Consequently, whenever
b 2 dlogz(n + 1) log.d, d,
the distributed problem has the same minimax separation rate for the hypothesis in (4) as the unconstrained problem with nm observations; p x vi For the Gaussian problem, this only the case whenever b Z d, as can be seen from Theorem This indicates kind of "tipping point" occuring whenever n gets small compared to d, where bandwidth constraint distributed setting, the testing problem in for the Gaussian model starts to exhibit very different behavior.

---

Interestingly, this does not imply that the multinomial model is "easier" from distributed testing under bandwidth constraints perspective, as there are sub-regimes in which the Gaussian model has solution whereas the multinomial model does not and vice versa. It indicates that the "communication complexity" of the sample space matters in the respective decision problems. We can leverage this fact to obtain lower-bound on the Le Cam distance between the multinomial model and the Gaussian model; which is the content of the next theorem.
Theorem 3. There exists constants C 0 and c 0 such for any d E N with
n log(d) 2 C and n nz Vdlog(d),
(15)
holds that
(16)
where P is the experiment generated by the observations in both indexed by F given in (
13 Q is generated according to (3)
The proof of the theorem is given in Section D leverages that there exist distributed, b-bit bandwidth
constraint settings in which the (distributed) multinomial model allows for consistent goodness-of- testing, whereas the (distributed) Gaussian model does not. The result then readily follows from the distributed equivalence results derived in Section A.2 The fact that the separation in the respective (distributed) testing risks occurs for a constant number of servers, yields that the two models are asymptotically nonequivalent whenever vd/ log" (d) 2 d/n >> 1. This reasoning crucially exploits the differing minimax rates that occur under the bandwidth constraint, since without such constraint, the same goodness-of testing problem of (4) would have similar minimax performance for both of the models.
6 Discussion
We have derived minimax separation rates for uniformity testing in the distributed multinomial model under bandwidth and differential privacy constraints, in the large sample regime where mnd log d/ /n = o(1). When contrasted with existing results for large sample regimes, the minimax rates show that the large sample regime is subject distinctly different phenomena.
The applicability of our results somewhat constrained by the requirement that mnd d/ o(1), which limits the range of model characteristics to understand the behavior the distributed multinomial model other regimes. The non-cquivalence result in Theorem 3 indicates that the distributed multinomial model and the distributed Gaussian model are fundamentally different regarding distributed statistical decision problems when the sample size is small. Therefore, direct analysis of the distributed multinomial model might be necessary, requiring new techniques to derive minimax rates. We note, however, that this pertains to the specific Gaussian model formulated in (13), and there might be different Gaussian model that is equivalent to the distributed multinomial model even in the small n regime.
consider. Consequently, further work is needed
The results in this paper are derived through the notion of statistical equivalence, which is powerful tool for establishing minimax rates in statistical decision theoretic problems. The results and techniques can be applied more generally other distributed inference problems, and proving more general results concerning statistical equivalence and distributed inference is an interesting avenue for future research.
downside of leveraging statistical equivalence is that generally does not provide a direct path to obtain methods that are minimax rate optimal. However, Theorem and Section 7 in (30] provide a specific transformation that converts the local multinomial sample into a statistic approximately distributed as Gaussian random vector. Such a transformation, combined with the rate optimal methods given in (85) and (22, provide guidance to construct methods that attain the minimax rates described in this article.
Acknowledgments and Disclosure of Funding
The author is grateful to the anonymous reviewers for their valuable feedback and suggestions and to Aad van der Vaart for his thorough reading of earlier draft.
10

---

References
[1] ACHARYA, J., BONAWITZ, K., KAIROUZ, P., RAMAGE, D., AND SUN, Z. Context aware local differential privacy. In Proceedings of the 37th International Conference Machine Learning (13-18 Jul 2020), H. D. and A. Singh, Eds., vol. 119 of Proceedings of Machine Learning Research, PMLR. pp. 62-62.
[2] ACHARYA, J., CANONNE, C.,, FREITAG, C.,, AND TYAGI, H. Test without trust: Optimal locally private distribution testing, In Proceedings of the Twenty-Second International Confer- ence on Artificial Intelligence and Statistics (16-18 Apr 2019), K. Chaudhuri and M. Sugiyama, Eds., vol. 89 of Proceedings of Machine Learning Research, PMLR, pp. 2067-2076.
[3] ACHARYA, J., CANONNE, C., LIU, Y., SUN, Z., AND TYAGI, H. Distributed estimation with multiple samples per user: Sharp rates and phase transition. In Advances in Neural Information Processing Systems (2021), M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34, Curran Associates, Inc., pp. 18920-18931.
[4] ACHARYA, J., CANONNE, C., SINGH, A. V., AND TYAGI, H. Optimal rates for nonpara- metric density estimation under communication constraints. Advances in Neural Information Processing Systems 34 (2021), 26754-26766.
[5] ACHARYA, J., CANONNE, C. L., FREITAG, C., SUN, Z., AND TYAGI, H. Inference under information constraints ii:: Local privacy constraints. IEEE Journal Selected Areas in Information Theory 2, 1 (2021), 253-267.
[6] ACHARYA, J., CANONNE, C. L., LIU, Y., SUN, Z., AND TYAGI, H. Interactive inference under information constraints. IEEE Transactions on Information Theory 68, (2022), 502- 516.
[7] ACHARYA, J., CANONNE, C. L., SUN, Z., AND TYAGI, H. Unified lower bounds for interactive high-dimensional estimation under information constraints. Advances in Neural Information Processing Systems 36 (2024).
[8] ACHARYA,, J., CANONNE, C. L., AND TYAGI, H. Distributed signal detection under commu- nication constraints. Conference on Learning Theory (2020), PMLR, pp. 41-63.
[9] ACHARYA, J., CANONNE, C. L., AND TYAGI, H. Inference under information constraints i: Lower bounds from chi-square contraction. IEEE Transactions Information Theory 66, 12 (2020), 7835-7855.
[10] ACHARYA, J., CANONNE, C. L., AND TYAGI, H. Inference under information constraints ii: Communication constraints and shared randomness. IEEE Transactions on Information Theory 66, 12 (2020), 7856-7877.
[11] ACHARYA, J., SUN, Z., AND ZHANG, H. Differentially private testing of identity and closeness of discrete distributions. Advances in Neural Information Processing Systems 31 (2018).
[12] AHLSWEDE, R., AND CSISZÁR, I. Hypothesis testing with communication constraints. IEEE transactions on information theory 32, (1986), 533-542.
[13] AHN, S., CHEN, W.-N., AND ÖZGÜR, A. Estimating sparse distributions under joint communication and privacy constraints. In 2022 IEEE International Symposium on Information Theory (ISIT) (2022), pp. 3144-3149.
[14] AN, K. Sulla determinazione empirica di una legge didistribuzione. Giorn Dell' inst Ital Degli Att 4 (1933), 89-91.
[15] BALAKRISHNAN. S., AND WASSERMAN, L. Hypothesis testing for nigh-dimmnsional multi- nomials: A selective review. The Annals of Applied Statistics 12, 2 (2018), 8), 727 1 744.
[16] BARNES, L. P., HAN, Y., AND ÖZGÜR, A. Fisher information for distributed estimation under blackboard communication protocol. 2019 IEEE International Symposium on Information Theory (ISIT) (2019), IEEE, pp. 7708-2708.

---

[17] BARNES, L. P., HAN, Y., AND ÖZGÜR, A. Lower bounds for learning distributions under communication constraints via fisher information. The Journal of Machine Learning Research 21, (2020), 9583-9612.
[18] BERGER, T., AND ZHANG, Z. On the ceo problem. In Proceedings 1994 IEEE International Symposium on Information Theory (1994), pp. 201-
[19] BERRETT, T., AND BUTUCEA, C. Locally private non-asymptotic testing of discrete distri- butions faster using interactive mechanisms. Advances Neural Information Processing Systems 33 (2020), 3164-3173.
[20] BRAVERMAN, M.. GARG, A., MA, T., NGUYEN, L., AND WOODRUFF, D. Com- munication lower bounds for statistical estimation problems via distributed data processing inequality. Proceedings of the forty- annual ACM symposium on Theory of Computing (2016), pp. 1011-1020.
[21] BUTUCEA, C., DUBOIS, A., KROLL, M., AND SAUMARD, A. Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids. Bernoulli 26, 3 (2020), 1727 1764.
[22] CAL, T. T., CHAKRABORTY, A., AND VUURSTEEN, L. Federated nonparametric hypoth- esis testing with differential privacy constraints: Optimal rates and adaptive tests, 2024. arXiv:2406.06749 [m)
[23] CAL, T. T., CHAKRABORTY, A., AND VUURSTEEN, L. Optimal federated learning for nonparametric regression with heterogeneous distributed differential privacy constraints, 2024. arXiv:2406.06755 [m].
[24] CAL, T. T., KE, Z. T., AND TURNER, P. Testing high-dimensional multinomials with applications to text analysis. Journal of the Royal Statistical Society Series B: Staristical Methodology 86, 4 (02 2024), 922-942.
[25] CAL, T. T., AND WEI, H. Distributed adaptive gaussian mean estimation with unknown variance: Interactive protocol helps adaptation. The Annals of Statistics 50, 4 (2022), 1992- 2020.
[26] CAL, T. T., AND WEI, H. Distributed gaussian mean estimation under communication constraints: Optimal rates and catpuuiiiaaiinfffffieetee algorithms. Journal of Machine Learning Research 25, 37 (2024), 1-63.
[27] CAM, L. L. Sufficiency and Approximate Sufficiency. The Annals of Mathematical Statisties 35, 4 (1964), 1419 1455.
[28] CANONNE, C. L., ET AL. Topics and techniques in distribution testing: A biased but representative sample. Foundations and Trends@ Communications and Information Theory 19, 6 (2022), 1032-1198.
[29] CANONNE, C. L., KAMATH, G., McMILLAN, A., SMITH, A., AND ULLMAN, J. The structure of optimal private tests for simple hypotheses. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019), pp. 310-321.
[30] CARTER, A. V. Deficiency distance between multinomial and multivariate normal experiments.
The Annals of Statistics 30, (2002), 708 - 730..
[31] COCHRAN, E. S., LAWRENCE, J. F., CHRISTENSEN, C., AND JAKKA, R. S. The quake- catcher network: Citizen science expanding seismic horizons. Seismological Research Letters 80, (2009), 26-30.
[32] CRAIN, M. The limits of transparency: Data brokers and commodification. new media & society 20, (2018), 88-104.
[33] CRAMÉR, On the composition elementary emoors: First paper: Mathematical deductions. Scandinavian Actuarial Journal 1928, 1 (1928), 13-74.
12

---

[34] DIAKONIKOLAS, I., GOULEAKIS, T., KANE, D. M., AND RAO, S. Communication and memory efficient testing of discrete distributions. In Proceedings of the Thirty-Secone Confer- ence on Learning Theory (Phoenix, USA, 25-28 Jun 2019). A. Beygelzimer and D. Hsu, Eds., vol. 99 of Proceedings of Machine Learning Research, PMIR, pp. 1070-1106.
[35] DING, B., KULKARNI, J., AND YEKIIANIN, Collecting telemetry data privately, Advances in Neural Information Processing Systems 30 (2017).
[36] DUBOIS, A., BERRETT, T., AND BUTUCEA, C. Goodness-of-Fit Testing for Hölder Con- tinuous Densities Under Local Differential Privacy. In Foundations of Modern Statisties, vol. PROMS-425 of Springer Proceedings in Mathematics & Statistics. Springer International Publishing, 2023, pp. 53-119.
[37] DUCHI, J. C.. JORDAN, M. I., AND WAINWRIGHT, M. J. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (2013), IEEE, pp. 429-438.
[38] DUCHI, J. C., JORDAN, M. I., AND WAINWRIGHT, M. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association 1 113, 521 (2018), 182-201.
[39] DUCHI, J. C., JORDAN, M. I., WAINWRIGHT, M. J., AND ZIIANG, Y. Optimality guarantees for distributed statistical estimation. arXiv preprint 1405. 0.88 (2014).
[40] DUNCAN, G., AND LAMBERT, D. The risk of disclosure for microdata. Journal of Business & Economic Statistics 2 (1989), 207-217.
[41] DUNCAN, G. T., AND PEARSON, R. W. Enhancing access to microdata while protecting confidentiality: Prospects for the future. Statistical Science 6, (1991), 219-232.
[42] DWORK, C. Differential privacy. In International colloquium on automata, languages, and programming (2006), Springer, pp. 1-12.
[43] DWORK, C., MCSHERRY, F., NISSIM, K., AND SMITH, A. Calibrating noise sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3 (2006), Springer. pp. 265-284.
[44] DWORK, C., AND SMITH, A. Differential privacy for statistics: What know and what want to learn. Journal of Privacy and Confidentiality 1, 2 (2010).
[45] ERIINGSSON, U., PTHUR, V., AND KOROLOVA, A. Rappor: Randomized aggregatable ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference Computer and Communications Security (New York, NY, USA, 2014), CCS 14, Association for Computing Machinery, p. 1054-1067.
[46] ERMAKOV, M. Asymptotically minimax tests for nonparametric hypotheses concerning the distribution density. Journal of Soviet Mathematics $2 (1990), 2891-2898.
[47] FISCHER,, O.,, MEIR, U., AND OSIMAN, R. Distributed uniformity testing. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (New York, NY, USA, 2018), PODC 18, Association for Computing Machinery, p. 455-464.
[48] GABOARDI, M., LIM, H., ROGERS, R., AND VADHAN, S. Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing. In Proceedings of The 33rd International Conference
Machine Learning (New York, New York, USA, 20 22 Jun 2016), M. F. Balcan and K. Q. Weinberger, Eds., vol. 48 of Proceedings of Machine Learning Research, PMLR, pp. 21 2111-211 1-2120.
[49] HAN, Y., MUKHERJEE, P., OZGUR, A., AND WEISSMAN, T. Distributed statistical estimation of high-dimensional and nonparametric distributions. In 2018 IEEE International Symposium Information Theory (ISIT) (2018), IEEE, pp. 506-510.
[50] HAN, Y., ÖZGÜR, A., AND WEISSMAN, T. Geometric lower bounds for distributed parameter estimation under communication constraints. In Conference On Learning Theory (2018), PMLR, pp. 3163-3188.
13

---

[51] HARD, A., RAO. K., MATHEWS, R., RAMASWAMY, S., BEAUFAYS, F., AUGENSTEIN, S., EICHNER, H., KIDDON, C., AND RAMAGE, D. Federated learning for mobile keyboard prediction. arXiv preprint arXiv: 1.110300104444 (2018).
[52] INGSTER, Y., AND SUSLINA, I. A. Nonparametric goodness-of of-fit testing under Gaussian models, vol. 169. Springer Science & Business Media, 2003.
[53] INGSTER, Y. I. Asymptotically minimax hypothesis testing for nonparametric alternatives. i, ii, iii. Math. Methods Statist 2, 2 (1993), 85-114.
[54] INGSTER, Y. I., AND SUSLINA, I. Nonparametric Goodness-of-Fit Fit Testing Under Gaussian Models, vol. 169 of Lecture Notes in Statistics. Springer New York, New York, NY, 2003.
[55] JURAFSKY, D., AND MARTIN, J. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, vol. 2. 02 2008.
[56] KONEČNÝ, J., MCMAHAN, H. B., RAMAGE, D.., AND RICHTÁRIK, P. Federated optimiza- tion: Distributed machine learning for on-device intelligence. arXiv preprint arXiv:1610.02527 (2016).
[57] KONEČNÝ, J., McMAHAN, H. B., Y., RICHTÁRIK, P., SURESH, A. T., AND BACON, D. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492 (2016).
[58] KREIDL, O. P.. TSITSIKLIS, J. N., AND ZOUMPOULIS, S. I. On Decentralized Detection With Partial Information Sharing Among Sensors. IEEE Transactions on Signal Processing 59, 4 (Apr. 2011), 1759-1765. Number: 4.
[59] KROLL, M. On density estimation at a fixed point under local differential privacy. Electronic Journal of Statistics 15, 1 (2021), 1783 1813.
[60] KULYNYCH, J., AND GREELY, H. T. Clinical genomics, big data, and electronic medical records: reconciling patient rights with research when privacy and science collide. Journal of Law and the Biosciences 4, (2017), 94-132.
[61] LAM-WEIL, J., LAURENT, B., AND LOUBES, J.-M. Minimax optimal goodness-of-ff testing for densities and multinomials under a local differential privacy constraint. Bernoulli 28, (2022), 579-600.
[62] LE CAM, L. Asymptotic methods in statistical decision theory. Springer Science & Business Media, 2012.
[63] LE CAM, L., AND YANG, G. L. Asymptotics in statistics: some basic concepts. Springer Science & Business Media, 2000.
[64] LEPSKII, O. Asymptotically minimax adaptive estimation. i: Upper bounds. optimally adaptive estimates. Theory of Probability & Its Applications 36, (1992), 682-697.
[65] LI, T., SAHU, A. K., TALWALKAR, A., AND SMITH, V. Federated learning: Challenges, methods, and future directions. IEEE signal processing magazine 37, 3 (2020), 50-60.
[66] MARIUCCI, E. Le cam theory on the comparison of statistical models. arXiv preprint arXiv:1605.0333) 03301 (2016).
[67] NGUYEN, A., Do, T., TRAN, M., NGUYEN, B. X., DUONG, C., PHAN, T., THIPURR,, E., AND TRAN, Q. D. Deep federated learning for autonomous driving. In 2022 IEEE Intelligent Vehicles Symposium (IV) (2022), IEEE, pp. 1824-1830,
[68] NUSSBAUM, M. Asymptotic equivalence of density estimation and Gaussian white noise. The Annals of Statistics 24, 6 (1996), 2399 2430.
[69] OBERSKI, L.., AND KREUTER, Differential privacy and social science: urgent puzzle. Harvard Data Science Review 2, (2020), 1-21.
14

---

[70] PANINSKI, L. A Coincidence-Basee Test for Uniformity Given Very Sparsely Sampled Discrete Data. IEEE Transactions on Information Theory 54, 10 (Oct. 2008), 4750-4755.
[71] PRITCHARDD, K., STEPHENS,, M., AND DONNELLY, P. Inference of population structure using multilocus genotype data. Genetics 155, 2 (2000), 945-959.
[72] RADFORD, A., Wu, J., CHILD, R., LUAN, D., AMODEI, D., SUTSKEVER, I., ET AL. Language models are unsupervised multitask learners. OpenAl blog 1, (2019), 9.
[73] RAMASWAMY, S., MATHEWS, R., RAO, K., AND BEAUFAYS, F. Federated learning for emoji prediction in mobile keyboard, 2019.
[74] RODRIGUEZ, I. M., SEXTON 2, W. N., SINGER, P. E., AND VILHUBER, L. The moderniza- tion of statistical disclosure limitation at the us census bureau.
[75] SART, M. Density estimation under local differential privacy and Hellinger loss. Bernoulli 29, 3 (2023), 2318 2341.
[76] SCHÜTZE, H., MANNING, C. D., AND RAGHAVAN, P. Introduction to information retrieval, vol. 39. Cambridge University Press Cambridge, 2008.
[77] SHAMIR, O. Fundamental limits of online and distributed algorithms for statistical learning and estimation. Advances in Neural Information Processing Systems 27 (2014), 163-171.
[78] SHEFFET, O. Locally private hypothesis testing. In International Conference on Machine Learning (2018), PMLR, pp. 4605-4614.
[79] SMIRNOV, N. Table for Estimating the Goodness of Fit of Empirical Distributions. The Annals of Mathematical Statistics 19, 2 (1948), 279 281.
[80] SPOKOINY, V. G. Adaptive hypothesis testing using wavelets. The Annals of Statistics 24, 6 (Dec. 1996).
[81] STRASSER, Mathematical theory of statistics: statistical experiments and asymptotic decision theory. No. 7 in De Gruyter studies in mathematics. W. de Gruyter, Berlin New York, 1985.
[82] SZABO, B., AND VAN ZANTEN, H. Adaptive distributed methods under communication constraints. The Annals of Statistics 48, 4 (2020), 2347-2380.
[83] SZABÓ, B., AND VAN ZANTEN, H. Distributed function estimation: Adaptation using minimal communication. Mathematical Statistics and Learning 5, 3 (2022), 159-199.
[84] SZABÓ, B., VUURSTEEN, L., AND VAN ZANTEN, H. Optimal distributed composite testing in high-dimensional gaussian models with 1-bit communication. IEEE Transactions on Information Theory 68, 6 (2022), 4070-4084
[85] SZABB B., VCURSTEEN, L.,, AND VAN ZANTEN, H. Optimal high-dimensional and nonparametric distributed testing under communication constraints. The Annals of Statistics 51, 3 (2023), 909-934.
[86] TAL, Y. C., AND SPEED, P. A multivariate empirical Bayes statistic for replicated microarray time course data. The Annals of Statistics 34, 5 (2006), 2387 2412.
[87] TARIGHATI, A., GROSS, J., AND JALDEN, J. Decentralized Hypothesis Testing in Energy Harvesting Wireless Sensor Networks. IEEE Transactions Signal Processing 65, 18 (Sept. 2017), 4862-4873.
[88] TE SUN HAN, AND AMARI, S. Statistical inference under multiterminal data compression. IEEE Transactions on Information Theory 44, 6 (Oct. 1998), 2300-2322 Number: 6.
[89] TEAM, A. D. P. Learning with privacy at scale.
[90]
TENNEY, R. R., AND SANDELL., N. R. Detection with Distributed Sensors. IEEE Transactions Aerospace and Electronic Systems AES-17, 17,4 4 (July 1981), 501-510. Number: 4.
15

---

[91] THORISSON. H. Coupling, Stationarity, and Regeneration. Probability and Its Applications. Springer New York, 2000.
[92] TSITSIKLIS, J. N. Decentralized detection by a large number of sensors. Mathematics of Control, Signals, and Systems 1, 2 (June 1988), 167-182. Number: 2.
[93] TSYBAKOV, A. B. Introduction nonparametric estimation. Springer series in statistics. Springer, New York ; London, 2009. OCLC: ocn300399286.
[94] VALIANT, G., AND VALIANT, P. An automatic inequality prover and instance optimal identity testing. SIAM Journal on Computing 46, (2017), 429-455.
[95] VAN DER HOEVEN, D., HADIJ, H., AND VAN ERVEN, Distributed online learning for joint regret with communication constraints. In Proceedings of The 33rd International Conference on Algorithmic Learning Theory (29 Mar-01 Apr 2022), Dasgupta and N. Haghtalab, Eds., vol. 167 of Proceedings of Machine Learning Research, PMLR, pp. 1003-1042.
[96] VON MISES, R. Statistik und wahrheit. Julius Springer 20 (1928).
[97] XU, A., AND RAGINSKY, M. Information-Theoretii Lower Bounds Bayes Risk in Decentralized Estimation. arXiv: [cs, math, stat] (July 2016). arXiv: 1607.00550.
[98] YE, M., AND BARG, A. Optimal schemes for discrete distribution estimation under locally differential privacy. IEEE Transactions on Information Theory 64, 8 (2018), 5662-5676.
[99] ZAMAN, A., AND SZABÓ, B. Distributed nouparametric estimation under communication constraints. arXiv preprint arXiv:2204. 10373 (2022).
[100] ZHAL, C., AND LAFFERTY, J. A study of smoothing methods for language models applied to information retrieval. ACM Transuctions on Information Systems (TOIS) 22, (2004), 179-214.
[101] ZHANG, Y., DUCHI, J., JORDAN, M. I., AND WAINWRIGHT, M. J. information-theoreee theoretic lower bounds for distributed statistical estimation with communication constraints. Advances in Neural Information Processing Systems 26 (2013).
[102] ZII, Y., AND LAFFERTY, J. Distributed nonparametric regression under communication constraints. In Proceedings of the 35th International Conference on Machine Learning (10-15 Jul 2018), Dy and Krause, Eds., vol. 80 of Proceedings of Machine Learning Research, PMLR, pp. 6009-6017.
16

---

A Le Cam theory in distributed setting
We introduce some formal notions of Le Cam theory first in A..1 Then, Section A.2 we study the equivalence of models in the distributed setting. The theoretical developments presented in this section apply general models denoted by P and 2: although the main text specifically focuses on the Gaussian location model for P and the multinomial model for Q, the machinery developed here is applicable to general statistical models.
A.1 Preliminary notions of Le Cam theory
A statistical experiment is a set of probability distributions P == {P; E F} (a model) on a measurable space (X, 22) (the sample space). For the purpose of simplification, we shall consider only statistical experiments with Polish sample spaces and corresponding Borel sigma-algebras. Furthermore, we shall only consider dominated models, meaning that there exists a sigma-fing finite measure μ such that Py < for all f E F. In slight abuse of terminology, we shall sometimes refer P the experiment, suppressing the presence of the sample space and indexing set.
: f E F) indexed by the same set F and sample space (X, )), we define the deficiency of P with respect to Q as
Given another statistical experiment with model Q {Q,
OP, Q)
inf sup || Q5 |TV. feF
(17)
where the infimum is taken over all Markov kernels C: 2 x + [0, 1] and the probability measure PyC: : 2 - [0, 1] is understood as
[ C(Alr)dP((x).
PjC(A)==
(18)
JZEX
This is equivalent the more general notion of deficiency of [27] for dominated models on Polish spaces (see Proposition 9.2 in (68).
The deficiency D(P; Q) quantifies the degree which Q can be approximated by an experiment P. If Q) S o, implies that for bounded loss functions, each decision procedure within Q has an associated procedure in P that achieves nearly the same risk, up to multiple of
To make this precise, let F be a measurable space and consider a function FxDD [0, on measurable space (D, 9). such that {(f,t) is measurable for all f E F. which we shall refer to a loss functions. We shall consider a decision procedure for (Q, D) to Markov kernel D 2 x & + [0, 1]. If (PP; Q) S 0. there exists C I x X + [0, 1] such that for all decision procedures D for (2,7) D) we have that
I (U..))P;CD(S) S
((S+)) (LL0))))))((_00000000000000)
+ 20,
for all E F.
Here, the Markov kernel 2 D is to be understood the sense of 18 and CD: 2 x X' - [0, as
CD(A(=) D(A())dC(E(a).
There is also the following reverse implication; suppose that there exists a loss function É: FFxx x D [0, 1] on measurable space (D, 9), and
/ () - -f (LF.)))) > 2e.
inf inf sup C D fer
where the two infimums are over all decision procedures D and Markov kernels C: 2 x X [0, 1]. Then, 0 P) > p. This follows immediately from e.g. Lemma 12 in the appendix, since measurable. In the more extensive framework considered in e.g. 27], such reverse implication for risk functions fully characterizes the deficiency between two models, but this framework is not needed in what follows.
+ (L)(f))))(((p)))
Le Cam's deficiency distance between P and Q is then defined as
APP Q) max (o(P; O(,)
17

---

This metric becomes a metric whenever P and Q are identified whenever d(P: + Two sequences of experiments Pa and 2, are called asymptotically equivalent if their difference (PPu, Qu) tends to zero as y approaches infinity. Conversely, such sequences shall be called asymptotically nonequivalent if A(Pe. 2x) > cas + oo for fixed constant c O.
The final notion we shall recall is that of sufficiency. A statistic S X + X' is sufficient for the model P if for any A E 2 there exists a measurable map V X - IR such that
Py (AnS-1(())) S A (Z))PP(( for all B E L and FEF.
Here, the measure Pÿ is to be understood as the push-forward measure Pf = P)() A sufficient statistic allows for transforming observations from one model another, "sufficient" model which is equivalent in the sense of Le Cam distance. That is, if S is a sufficient statistic for P, then the model P' := {Pp f E F} satisfies A(P, = O.
The next lemma is the Neyman-Fisher factorization theorem gives useful characterization of sufficiency of a statistic for models that admit densities with respect to the same dominating measure.
Lemma 2. Suppose that Pj & μ for all Pf E P with μ sigma-finite measure. A statistic
S X X is sufficient for P if and only if there exists measurable functions 95 R + and
h X' - R such that
dPI dp
- (5(x)))) for almost every x X and every f fEE. F.
(19)
proof for both the lemma and the last statement of the previous paragraph can found in Chapter
5 of [62]
A.2 Equivalence of distributed decision problems
We now turn the distributed setting considered in the paper, where j 1, I....; m servers each receive data X drawn from distribution Py and sample space (X', 2"). Each of the servers communicates a transcript based on the data to a central server, which based on the aggregated transcripts computes its solution to the decision problem at hand.
The tools developed in this section apply to wider range of distributed architectures than the one considered in the main text of the paper, as introduced in Section 2 The framework introduced here accommodates various forms of interaction between servers, including sequential and blackboard protocols (see e.g. 16). In contrast, the main text focuses on servers that either do not communicate (local randomness protocols) or utilize a shared randomness source (a special case of sequential or blackboard communication).
distributed protocol for the experiment P with decision space (D, D) consists of triplet (D, K. (U, W, IU)),, a Markov kernel : 2 3 yt) [0, 1] and probability space (U, 2, P.). and IC is collection of Markov kernels.
To unpack all this notation: the Markov kernel 1) takes the role of the decision procedure, where the decision is to made on the basis the transcripts generated by the Markov kernels K. The transcripts in turn generated based on the data and source of shared randomness independent of the data. The probability space (14, V, )oه) plays the role of the source of randomness that is shared by the servers. The distributed protocol is said have no access shared randomness to be a local randomness protocol if V is the trivial sigma-algebra.
In this section, we shall consider three types of communication architectures:
One shot protocols: K. ) where K g (X' x 21) [0. 1]. These protocols are what are considered in the main text of the paper.
Sequential protocols: K. {K*) {K*),= j= where K () x (X 4 x (01) x y(--1) - |o. 1]. That is, the transcript generated by server j is based on the data, the shared randomness and the transcripts of the previous servers.
Blackboard protocols:
18

---

Blackboard protocols: K. = {K?} f= ttt.... where KJ 2033 x (X' x U) + [0 and
Ki 2 (x x u (D1))
)(() ( [0. 11,
for t 2 .....,T. T. randomness, and the transcripts of all the servers from the previous round.
That is, the transcript generated by server j is based on the data, the shared
For one shot protocols, we have in terms of random variables that X ~ Pt. U pe, (( U) ~ (+ U) for j = 1,...,m m and ip ~ D(-IY) with Y = (..m)....)) This gives rise to Markov chain
,..., yim)).
(
Yau
(20)
((m)
For = (z(1), (m)) E xmm E u and {K* j== m let ((Aa²) be the Markov kernel product distribution 8 y= () u). Given a distributed protocol and i.i.d. data from Py we shall use Fy to denote the joint distribution the data X ~ Pf the shared randomness U ~ pp and Y = (Y) (m)) with (X,, U) ~ ( U). We have that P K ²z P,K and the push-forward measure of Y then disintegrates as
- PA ((A) = P2 PT
( , ()(A)dPP(()) (21)
where the second equality follows from the independence of U with the data X = (x.))..... X(m)) drawn from Py. For sequential protocols, the fush-forward measure of Y instead disintegrates as
Py (y(A) - (A)
V.. 1A(W)ddP (1TH (mm) (w)) ...
....dyKK(0 (P' 1x u))
u) dPu (u):
(22)
For blackboard protocols, a similar disintegration applies for each of the rounds.
A one shot or sequential distributed protocol is said to satisfy b-bit bandwidth constraint if its kernels {K*},= are defined on spaces satisfying |)> < 2h. For blackboard protocols, various bandwidth constraints can be imposed, such as a b-bit bandwidth constraint for each round
t T.
Given Markov Kernels Ci L x E + 11. I,... m. a distributed one shot protocol (D, (K*) (U1 V p() }} for the model P, yields a distributed protocol for the model Q: {D, (O,CCK)) (CK')== }j=I...,. (U, W. pp)) }}. If [K') j==.....m {T')) is b-bit bandwidth constraint, the collection of kernels {O'K) |= do so too, as each C* is defined on (i) x &.
Similarly, for sequential protocol, the Markov kernels C and K2 yield distributed sequential protocol for the model Q with kernels {C' _z m. If each K b-bit bandwidth constraint, so is each C2 KJ, For blackboard protocols, the same reasoning applies to each round f = 1.... T. That is, type of protocol defined by the kernels K. is "closed under composition" with kernels C between X' with target space X, where bandwidth constraints preserved.
We shall consider the notion of local c-differential privacy of Definition 3 K y x X + [0, 1] is called locally (e, -dffferrrett private if
A Markov kernel
K(A[z) S e (AAaa') + 5 for all A E y and x E X'
(23)
Since the definition of differential privacy depends heavily on what one defines as the sample space, is difficult to obtain a similar "transfer of distributed protocols" that respects the ddifffrrrett privacy constraint, hence the choice consider local constraints only.
19

---

A one shot or sequential distributed protocol shall be called locally e-differentially private if (23 holds for each K²; j ....., m. For blackboard protocols, one can impose (c, -difffriinna privacy constraint for each round / = ,,.... T, or for the entire output over / == 1, 1,.... 7 rounds. The following lemma shows that local e-differential privacy, just like bandwidth constraints, carry over from one model to the other.
Lemma 3. Let (X, 2 and (X, 2) be measurable spaces and consider Markov kernels C L x X + [0, 1] and K y x X [0, 11. If K is b-bit bandwidth constraint, so is the Markov kernel CK V x X [0, 1]. If K is locally e-differentially private, is C.. Furthermore, for any collection of Markov kernels KC, the same reasoning applies to the collection (CK) JKEK, preserving bandwidth constraints and local differential privacy, as well as the protocol's 's architecture.
Proof. The first statement has been remarked on earlier in the section. For the second statement, consider arbitrary ã, F E & and A E V. Using that C' is Markov kernel and applying (33 to K yields
CK(A - K(A = / ((AA))dC(=R)))CCC
S 5 ((AAA)))(())))) - ((CK(A)E)) +
which shows CK locally (c, ddifferrnntil private. The above argument applies pointwise for
all other conditional arguments in the Markov kernel, hence the same reasoning applies to shared randomness, sequential and blackboard protocols.
In an abuse of notation, let D denote the entire distributed protocol (triplet)
{D, (D,(K) [D,(K'))=I.....n (41 V PP"))
for the experiment P (indexed by F) with decision space (D, D). Given D and loss function e: Fx [-1, 1], we define the distributed risk of D in P for as
Rp(D,)) = sup /EF / ((.,))D(el)) PjK'(1XX), (NX((I u)(v) (u).
[
m
We are now ready to formulate a straightforward consequence for the distributed risk, following from models being close in Le Cam distance. This finding, formulated in Lemma 4 shall serve as of the main tools for deriving the main results. It states roughly that, whenever there a b- bit bandwidth constrained distributed protocol that achieves a certain risk is one model and there is small deficiency with the other model relative to the number of servers, there exists a b-bit distributed protocol that achieves comparable risk for the other model. A similar statement holds under local differential privacy constraints. If there is a locally (c, diffiffrrett private distributed procedure in the one model and there small deficiency with another model, it means that there is comparable risk for the privacy constraint distributed decision problem.
Lemma 4. Let m E N. Consider two experiments P and Q with indexing set F, satisfying mo((; P) S e for some @ >> O. Let JT and I o denote the class of b-bit bandwidth constraint shared randomness protocols for the models P and Q respectively.
Then, for any loss function ê F x D + 10,
inf RD(D, inf RD( 5. DE
DE
where in the infimum, in an abuse of notation, D denotes the entire distributed protocol triplet (D, (K') (K'))=...... (14, V (pt))).
The same statement is holds for IT and Jo denoting either classes of b-bit bandwidth constraint local randomness, sequential protocols, or any of these distributed protocols satisfying local (e, 6)- differential privacy construints, for the respective models P and Q. 1f mmd Q P) S 0. the same statement holds for blackboard protocols with T rounds.
20

---

Remark 1. This exemplifies also that, even though models pm = = (PT f F) and Q' = (Qp E F) are close in Le Cam distance, distributed decision problems formulated in terms the models P and Q, can have greatly different performance in terms of associated risks.
Proof. By e.g. Theorem in 662. md(2; P) < g implies that there exists a kernel C:: L' & [0, such that
sup fEF
P - 1 S g/m.
(24)
By Lemma 3. the kernels == (CK; K E KC} satisty the b-bit bandwidth constraint or local (c, 8)- differential privacy constraint if the collection {K* )==...... does. To illustrate this further, consider one shot distributed protocol for P. {D, {
(U, 1,,,,,Pu ,P(i)} E Ip, the distributed protocol δ {D, (CCK))=,,...... (U, 2 }P is then an element of fo.
Using the fact that is bounded by one and Lemma 13 in the appendix, it follows that
Re(D,1) RD(D, |
PyK - pV X
Qgc
==1
P PP"
By Lemma 14 in the appendix,
||P P,K³ P QOO,CK'IIV S
= - - -Q,CllTv
which combined with (24) finishes for one shot protocols.
Similar reasoning applies to sequential protocols. We start by noting that
|| K ( u) QjCK'( u)llTv s [1 Q,Cl|Tv S e/m;
Lemma implies that (for any u) there exists a coupling P of y()) ~ P,K' u) and ÿ()) ~
QjCK* u) such that (1) & (1)) s e/m. Write
kmm:( -m" , v') f ... dk (ym x"' "u," ....,,') ..l))....((()))
dk2 | x2, u,,'
Using the disintegration relationship of (22). we obtain
1P K
Pd QOQCKIITV S |IPT u) - Q2CK(( ( uu]l (u)
semm+ f by w Pp pp
u, -Q, I y " (u).
Iterating the above argument
times, we the statement for sequential protocols. The statement for blackboard protocols follows by combining the above arguments for each round / 1....,77 T.
In the remainder of this text, we shall constrain ourselves to particular bounded risk function and distributed decision problem; distributed hypothesis testing. The following corollary formalizes the statement at the start of the paragraph for the testing simple null versus compositive alternative hypothesis in the distributed setting. To that extent, consider a test of the hypotheses
Ho : f = Jo versus the alternative hypothesis f Hi
(25)
and an experiment P with indexing set F satisfying {f)) C F. Consider for E M distributed testing protocol for the model P to be a distributed protocol T = (D, (K*) )=,,,.. (4, H ",P") PP)), where in slight abuse of notation, we shall also use T to denote the (possibly randomized) test T|Y D(-IY). Recalling the notation PY Pr
prpt K as given in (2 define the distributed testing
risk for the hypotheses in (25) and the model P
(T, H1) == I.y D(T(Y) + sup I. (1 D(T[Y)).
fell,
21

---

Here, D(T == D(()))), but one can equivalently consider a deterministic measurable map m 1 + [0, 1] without loss of generality. Let -T (P) (resp. ... (P)) denote the set of shared T:
randomness (resp. local randomness) distributed testing protocols for P satisfying a b-bit bandwidth constraint. Similarly, let -Tk (P) (resp. {(k.') denote the set of shared randomness (resp. local randomness) distributed testing protocols for satisfying local (c, d)ddifferel privacy
constraint. Define the same classes for the model Q in the obvious way. Using Lemma we obtain
the following result, which is more general version of Lemma
Lemma 5. Consider experiments P, 2 such that md(2; P) S e @ > It holds that inf TE)(2)
inf RT H1) - TE)(P)
RT H1) 20.
where I is either Tsh. F.. Flc,) gle.5)
Proof. Given (T, (K*) /= m (u, U1 PU)) (P), Lemma applied to the loss function
((ftt) = tl (1) + +(1 -1 m) (f)
and using that {fo] C F gives D(TIY) < D(TIY) and sup p (1 (1- D(T < sup Q7 (1- (I-D(T)))) + SEH,
JEH,
for some distributed testing protocol {D, [= (4, 2, ),, in I()), which yields the first statement. The second statement follows by symmetry of the argument.
The implications of Lemma have implications beyond the testing framework. Whilst in distributed estimation settings, the loss function under consideration is typically not bounded, rates can still be derived in probability. That is, if the minimax rate for the distance d on F in the model Pa is Pe. the bounded loss function
(x = (d(f.g) Cp.} for C>
can be used describe minimax estimation rates (in probability) between models P and Q. Since the paper about testing, we shall not pursue this direction any further beyond this remark.
In the next sections, we will explore the consequences of Lemma 3 for minimax distributed testing rates for both bandwidth- and privacy constraints.
B Difficulties in direct analysis of the multinomial model under information constraints
Lower-bounds for both estimation and testing problems are typically established by bounding divergence measures between probability distributions, such as the chi-square divergence, mutual information, total variation: 3 16?
40
g
99
85
The proof techniques used for discrete distribution estimation employed in S and 77, tight lower-bounds often be obtained by "tensorizing" the divergence breaking the problem into sum of local divergences. The inferential cost incurred due to bandwidth or privacy constraints are then captured via data processing arguments. Similar tensorization techniques employed in other estimation problems, see for example 16 [9).
However, this tensorization approach does not yield tight bounds for testing problems. For exam- plc, [84] uses mutual information in a tensorization framework for testing but only recovers optimal rates when each server communicates single bit. Similarly, [8] attempts an estimation- based ap- proach for goodness-of-fi testing but obtains tight lower-bounds only under 1-bit constraints, as detailed in Section 4 of their paper.
To achieve tight lower-bounds in testing problems, especially under communication and privacy constraints, different techniques are required. Papers 9
employ methods that significantly diverge from those used in estimation. In (9. combinatorial expansion of the likelihood is used, effective for small sample sizes in the multinomial model but not generalizable to large numbers of
85 22
22

---

observations. 85 and [22] address this limitation in the Gaussian setting by utilizing the Brascamp- Lieb inequality from functional analysis, which explicitly leverages the Gaussian properties of the log-lik he.likeliiood. This approach is not directly applicable to discrete models, due to the lack of quadratic structure in the oogliikelhhodd of the multinomial model.
C Separation rates for the Gaussian model
For completeness, we provide the relevant results for the Gaussian model studied in [85 and
22
The first results come in the form of lower-bounds for the minimax detection thresholds under bandwidth- and differential privacy constraints for the distributed signal detection problem presented in the introduction. We recall that in this problem, each local machine j E [1.....m] observes
x
f + -,0)
(26)
with f E Rd and 2 ~ N(0, Ta), i.idd for 1...., n. The null hypothesis constitutes that f versus the alternative hypothesis that
f Hp := (
lf 2 p
(27)
The following is Theorem 3.1 from 85
Theorem 4. For each E (0, 1) there exists constant > O (depending only on a) such that if
Vd
(V bad A V
p² < Ca
(28)
then in the shared randomness protocol case
inf TE
R(H T) > a for all n, m, d E N.
10)
Similarly, for
p² <a Va d
b d vm).
(29)
n
have under the local randonness protocol that
inf TE
R) > a for all n, n,m, e
Following the proof Theorem 3.1 from 85), we obtain the following lemma.
Lemma Let Tb denote the class of b-bit bandwidth constrained shared- or local randomness distributed testing protocols and let p satisfy either (28) 29.. respectively. For any E (0, 1),
there exists co 0 such that for all T E gb) holds that
inf R(H,, a (H,) TEY
where (O. 1/2 for symmetric, idempotent matrix ddd with d/2 < rank(T) sd
Similarly. the following result can be derived from the proof of Theorem 5 in 22 by taking > 0 in the theorem such that dz, d.
Theorem 5. For each (0,1) there exists constant Ca 0 (depending only a), such that for any n, m. E N and
0 <<< 0<651 and 0 < 85
Cam 3/2 332 A 1d2 A 1/2 A21/20-1/222
1tp
for some 0, (30)
the condition
d
Vd
p² < Ca
(31)
mnvne" A Avne Ad
Vmmnvnee
mn?e²
23

---

implies
inf TE
R(Hp:T) > a.
Similarly, for any n, m, d E N and e, 8 satisfying 33p, the condition
dvd
Vd
p² ca mn(nn² A d)
A
(32)
Vmnvnne A
mn²e²
implies that
inf R(Hp.T) TE
Following its proof, we obtain the following the following sub-result.
Lemma 7. Let I denote the class of shared- or local randomness distributed testing pro- (e, (e.8)-differential privacy constraint for 0 <
tocols satisfying (cam=1 A caem 11/2 A ne² A 222 An2(2d-1/222) and let p satisfy either (28) 29 respec- tively. For any a E (0, 1), there exists Ca > 0 such that for all T E g(c,8) holds that
6 I
RH T) (HH
where π N(0, ca 1/120-1-1----00000000000 for symmetric, idempotent matrix I TRaxd with rank(T) x
D Proofs of Theorems and 3
Proof of Theorems 7 and 2 what follows, let F denote a class of distributed protocols satisfying
either 6 = bit bandwidth constraint or a local (e, d)-differential privacy constraint for e = Ev, 8 = dy allowing either for shared randomness or only local randomness.
For any sequences m = my, = dy and n = ny with CR md d/ Ví = o(1), follows from Lemma 5 and the bound (14) that the testing risks satisfy
inf (H T) TEPe
inf Rr, (H p T) o11) TEPp
(33)
Let p² = P be the minimax rate of the P-distributed problem, over the class Tp. in the sense that p" equals (up constants) the right-hand side of (6). 7 9 (TO.. We split the proof into showing that p" is upper and lower-bound for the Q-distributed problem over the class Fp.
The rate p² is upper-bound (up poly-logarithmic factor) for the minimax rate in Q: Write, for q F, q (Vīi)seld Since x() /To is a sufficient statistic for X the model (13 is equivalent in the Le Cam sense the one generated by
x = / v0
Z with Z ~ (O, 22n
(34)
for q F. which we shall denote by P. Consequently, by another application of Lemma it suffices to show
inf TES
(Hp T) + 0.
If llg go/l1 2 p. Lemma 15 implies that |l voll2 p/2. Consequently, if Pv > Mop" where p² is equal order of the minimax rate for the respective class of distributed protucols Pp and M, is appropriately large factor (of log-rthgai order in case of differential privacy constraints), a distributed protocol E Tp exists for the Gaussian model that achieves the separation rate for whenever Ho //- equivalence the minimax risks (33) this implies that protocol Te exists for the multinomial
Qg 0 versus H, IIV /qollz > p/2. By the established
model well. Thus, P. is upper- bound for the minimax separation rate for the class of distributed protocols To of the multinomial model.
upper-bound
The rute p" is a lower-bound for the minimax rate in Q: Suppose that Pv is of smaller order than the minimax rate p² the class Tp, the sense that p² /'pp - xc as + co. We aim to use the Bayes risk lower-bound of Lemmas and 7 which apply Gaussian prior. To accommodate
24

---

Gaussian prior with sufficient mass on the alternative hypothesis, we first need to address the
"constraint the signal" imposed by Σ 9: for q E F.
To that extent, consider without loss of generality d to be divisible by two. Let In := 1- 1), (R (R + 1)]. For all (fi)ee(d/2) E /d/2 /vd, there exists q' == (g) )iE(d] E F such that
d' = 1/d + Ji/Va for 1....,,// d/2 and qf 1/d d fi/vd for = d/2 + 1,.... d. To see that
o' E F, note that Σi= of 1, of 2 0 and
1 max cEtn -c
max
R.
0k
Define F as the set
(a)ie EF (fi)ae4))))
E s.t. of = 1/d (1- 21/22
In
St
for = 1, I.....dd .
vd
Vd
and
H 9E
p
We have F C F, which in turn implies that H³ C H Combined with the fact that the testing risk decreases by considering smaller alternative hypotheses, this results in
RT H₂) 2 inf Rp H)). TE.P
inf
(35)
TE.p
Define gf = (1/2) Rd. By Pinsker's inequality,
pam 4 -00
Pum
11A
mn DKL (Pva- Pa-
TV
1A
/mn
V9 24/gg//Va - /q0 91 =: Dy,
where pm_ /8-v00 denotes the distribution of (34) and the square root to be understood as applied coordinate wise.
Let क N(, d 22") for symmetric, idempotent matrix I' e gd/2xd/2 with d/4 rank(T') s d/2.
We have that
[POT()) + / /Po, (1-(11))))7(()) - 2 (f
RT H²) 2 inf TET,
inf
Tr
π (5 f (In/ or
00/| < <))
By Lemma observations
the model {Pgr f 1 /Vd is equivalent to the model generated by the
stn) = f: Fn 2,
(36)
i l,...,,,,, d/2. Since F' is bijective with (Iz/ /1///a//22 Lemma implies that
(oT(Y)) + / [P,, (1- (L,, ((Y))((())(())) = inf TE
PT(()++ / P2(1 11/(1- -
inf TE
-(()))(((((
(37)
where P is the model generated by the observations in display (36 for i 1,....,/].. and Py denotes
the distribution of the distributed protocol with data generated from f P..
follows from Lemma the case of bandwidth constraints or Lemma 7 in the case of privacy constraints (using that < p" in both cases) that the latter distributed testing risk is lower-bounded by
1 1-o(1) (FERd/ :f f (In/Vaja/2 or (d))ee -ool, <p) - DydT(f). (38)
25

---

Addressing the third term in the display above: the (heorem(s) assume that md d/ /í "= 0, b 2 1 and > n n-14 we have that o² < 1/ Iog(d), which gives |/ 0 with r-probability tending to one (see e.g. Lemma 16 which turn implics that
fx IR/ /d for all i ........d3.. d/2.
(39)
Next, we show that (1 NE(4 2olli 2 with x- r-probability tending to one. Since Σ d/2 > 1 [// we have that for some constants e, > 0,
10! qol
=
π (1lg - 201l, p) = (11/vv) < s1)
[T 2 é'd
0-
where in the expression on the right-hand side, Z ~ NVO,,d//2) Since p < pa and I is idempotent with rank of the order d, we can conclude that the expression vanishes. This takes care of the third term 38
For the last term in 38). the Taylor approximation vT + 1- y/2 ///8
for some
16(1+9 2
1 E [0, v). combined with the fact that ||v - or (1) yields that
2 / D (dd((f) f Vmnd (f (ff)) dm(() 2 Vmnp".
Since the theorem(s) assume that md log d/ "0 0. b 2 and e > n-1/ 1/4 the right-hand side of the above display vanishes.
Proof of Theorem 3 Let To. Fp denote the class of distributed b-bit bandwidth constrained testing protocols with b E N, m E N, d E 2N and n E N and no access to shared randomness for the models Q and P, respectively. We note here that under the conditions of the theorem, we assume d and are both larger than some constant; and in particular we can assume d E 2N without loss of generality. Assume d and satisfy (15), for constant C to be set later. The proof follows by the fact that the distributed testing problems have different minimax testing rates, for certain values of and m.
Consider the hypothesis test given in with Ho 40 (1/d. ...,, 1/d) E Sd and H, in the display.
Set 6 = I log, (d) When b 2 n (d)) the observations X in the multinomial model as given in (3) are valid b-bit transcripts, since |f1..., ..l.....d) d}"1
< n (d). These transcripts are therefore sufficient for the nondistributed/ unconstrained model Q i.e. corresponding to observations
X~ Qq for E F.
Consequently, the distributed, b-bit bandwidth constraint testing risk for Q is equal to the testing risk Q"
inf Ro(H,,T) TEHe
= inf R@ (Hp.T) T
This means that, for all a (0,1). 1). there exists C. > and distributed protocol T' satisfying b-bandwidth constraint for distributed experiment @ such that
Vd
Re(Hp, 7) < a whenever p² 2 Ca mn TET
inf
where H. as defined (4) as the minimax rate for the unconstrained problem with mn observations is p3... := /d/ (mn) (see e.g. Theorem in (70).
On the other hand, whenever mb = m n logg (d)1 s d, the minimax rate for the distributed testing risk of P for the (comparable) hypotheses
Ho q 90 versus H, Ilvg- /goll2 2
bounded from below by 2 x Vd/(Vmm)) as a consequence of Theorem Specifically, following the proof of Theorem I above, have that
inf Rx (H,, T) 2 inf TEFp
R. T), TET,
26

---

where
:p: = (s (In/ :11fl: 2 zp)
for 1o: -BB=\//VVB//VI+ V2(VR 1101--1//// 11/v1+ R). P generated by the observations
x f+ 1/1 vn =700
for 26) (0, Ta/2), indexed by f E (In/ (n/Vayd/2 and the class Fp is to understood as the b-bit bandwidth constraint distributed testing protocols for the model P and 1...., m machines.
Lemma (6) implies that for all E (0, 1) the latter is bounded by
a N(0, ca 1 (
for a symmetric, idempotent matrix R4/2xd/2 with d/4 S rank(T) & d/2 E (0, 1), whenever Va for some small enough constant C, O. By the same analysis as conducted in the 0² < Co. ymnn
proof of Theorem above (using that n S. log(d)), we find that the second term is at most a/2 for Co 0 small enough. Summarizing, find in particular that for some constant Ca 0,
inf Rp (T, Hp) > 1/3, TEEP
for 0² S ccdd/VVm)) and m, n, d such that mb S where the number 1/3 is chosen without particular significance.
Whenever mb m log2(d) S d,
inf Re T) < 1/6 < 1/3 TEHe
inf TEFP (p T).
(40)
for some C. > 0 large enough and > 0 small enough. Take the constant C = [C2/c2 / such that m C, holds that
vd 2² S ca
Vd /mn
Vd
Co
with p² Ca
mn
VM VMymn mn
Now suppose that CO(Q. P) < 1/6. Lemma then implies in that
inf TE3p
Rp (Hp. T) s
inf Ro(H,, T) + 1/6 1/3. TE%o
This contradicts (40) We conclude that
Co(Q, > 1/6,
(41)
whenever lo (d) > C. The result now follows with e = 1/(6C).
O
E
Auxilliary lemmas
The following lemma used in the comparison of the multinomial model to the many-normal-means model.
Lemma 8. Let d e 2N, F Rd/2, and consider for 1.... ... independent random variables
X, = h4 + ob with > 0 and Z, ~ NO, 1) satisfying
(affs
if d/2.
l: = -a.f
if d/2.
for some f E F and = (as) E Rd. Let P denote the model generated by the observations X = (X Xa) Py. f E F and let Q denote the model generated by
X; = (a, + aaf2+:)ft+ V202,, for i = 1, d/2,
ltd. with Z; ~ N(0, 1) and f F. Then, (PP, Q) 0.
27

---

Proof. The statistic S = (a; X; - a/X4/2+1)sel is sufficient for the model P by using Neyman-
Fisher (Lemma 2) We have
dP'j I (X) - II
d
1xih; 20
exp
dPo
im1
d/2
II exp
(a;;; a;
02 0
c
1 9 f- f- 11/
i=1
In distribution, X = (Xi)) is equal to S, which implies (P,, = 0 per Lemma 2
The following lemmas are well known but included for completeness.
Lemma 9. Let Py denote the distribution of a [f,, oIa) distributed random vector for f E I and let Pj denote the distribution of i.idd draws (i.e. Pf = 80=1 py).
holds that
P7
Pr
S
Il gll2 20
IV
Proof. By Pinsker's inequality,
P - Po ITv S
1 2 (Pp: Pg).
straightforward calculation gives that the latter is bounded by
// [1 - -912 26
The following lemma relates the total variation distance between P.Q the -idittancce between corresponding densities.
Lemma 10. Let P. Q be probability measures dominated by sigma-finite measure p with corre- sponding probability densities p dp
dP and q du It holds that
1 / [p(x) g(z)ldu(xx.
PP-Q
Proof. See e.g. Section 2.4
93
Lemma 11. For any two probability measures P and measurable space (X, 2) with X Polish space and V its Borel sigma-algebra. There exists coupling xpx.X such that
1P-QQIev = 2P. (x+ x))
Proof. See e.g. Section 8.3 in 91
The next lemma gives a useful characterization of the total variation distance between two probability measures.
Lemma 12. Let P be a signed, bounded measure defined on measurable space (X, 2) and suppose that P v for a sigma-finite measure v. holds that
||||TV = sup {
fdP:: Ifl fddP:If and f X + P. is measurable
(42)
Proof. Consider the Jordan measure decomposition P p+ p-, where P- P- are both positive, bounded measures such that p+ P For any measurable f. {f 2 0), (f $ 50) E L, so ff < means that
I sap
fl
/ fLirsondP
$ 11200 / (sso
$ <| + ||P ||Tv s 2||T/
28

---

For the other direction, note that f = sign(p q) is measurable and bounded by 1, which gives
2 ʃ fdP=
gldv P Qlivv,
where the last equality follows from Lemma 10
Lemma 13. Let P = 2
j=1 Pj and Q
2 j= Q3 for probability measures Pj, Qj defined on
common measarable space (X, H) with probability densities Pjs Qj for =,. 1,... m. It holds thut
-P-QUITV S Σ - OPP-Q2yITV.
3=1
Proof. The measures Pj and Qj admit densities with respect to Pj + Qj. which we shall denote by Pj and qj. respectively, with
P and g
Qj j=1 P3 + Q2)
m II
m2
Pj
II
93
1=1 Pj Q2)
Writing μ
x m2 j=1
PP + Qÿ) and applying Lemma 10 we obtain
P QV 1
IT
m
p5()))
(pl Tmm)
(43)
By the telescoping product identity
m
01 02 Oyn. bi b2 bm
Σ
aj
II
ah
m
by
(44)
k=j+1
j=1
and Fubini's Theorem, the right-hand side of (43) is bounded by
Σ f (1) -2))) 1,1lv.
m
The following lemma can be seen as data processing inequality for the total variation distance.
Lemma 14. Let (X, 2)) and (y, 3 be two measurable spaces and let y x X - [0, 1] be Markov kernel. For any probability measures P, Q defined on Y. it holds that
PP QKI S || Qll
Proof. This follows immediately from the representation in Lemma combined with the fact that, for | < 1, f (w)d (y/æ) is measurable function bounded by 1, since K is Markov kernel. Hence,
supl PK(() - =
2 dnue
1
/
(())aK(lla)(PP--11 Q)
A
$ sup / [(a)d(P-Q(())
1
The next lemma bounds the Li-dittacce ||p gll1 between densities with multiple of the Hellinger distance 2 2-1/211 V Lemma 15. For two probability densities p. q with respect to it holds that
/ (p(z) q(x)) < / vo(x) du(z)).
29

---

Proof. The result follow from the Cauchy-Schwarz inequality and the fact that / pdp f qd See e.g. 993 for details.
1.
Lemma 16. Let K EN and M RRKK be symmetric and positive definite. Consider the random
vector G (G.....,, Gk) N(0, M). It holds that E max
|G,| 3|| log(2) and
ISiSK
2K
Pr
max IS:SK
G 2 |1
e0/4
for all x > 0.
Proof. It holds that
G VMZ, with Z N(
Since M is symmetric, positive definite, it has SVD decomposition M VD Ax) Since V is orthonormal,
VM2 V / Diag(>i,....... Ax)(( 2) _ V Diag(Ai..... A
Ax)
Writing
[0]
uk] where Us are orthogonal unit vectors, the latter display equals
VaviZee N (0, Di. Ax)))
Consequently,
max G KE(K]
max d Zkl S [| kE[K]
max Z KE[K]
Hence, it suffices show that
2K e=/4"
Pr
max ISiSK
Z
The case where K = 1 follows by standard Gaussian concentration properties. Assume K 2 2. For s 1/4,
max, max, (2,)² e' max 122 < 2
Taking 1/4 and applying Markov's inequality yields the second statement the lemma. Further- more, in view of Jensen's inequality
log K)
E max (Z,)² <
+ 2t + 1,
which in turn yields E max; /zl| S 3 /lo((K).
30

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: Yes.
Justification: Proofs of all theory are provided.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: Yes.
Justification:
See discussion
31

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
Yes.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: NA
Justification: No code experiments are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
32

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: NA
Justification: No code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (nttps://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7 /ttppp.cc/pbllc/guudeeee http://odebbbbiiiooooooooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
33

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: NA
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: NA
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: NA
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
34

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
Yes
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: NA
Justification: The paper focuses on theoretical developments in statistical models without negative societal applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: NA
Justification: All the results of theoretical nature; data models released.
Guidelines:
35

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: NA
Justification:
Guidelines:
The answer NA means that the paper does existing
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: NA
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: NA
36

---

Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: NA
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
37


Reviews:
[{"review_id": "gmTkudtds4", "reviewer": "Reviewer_Nun8", "summary": "The paper addresses distributed goodness-of-fit testing problems under user-level communication and local differential privacy (DP) constraints. In this scenario, each of the m users receives n samples, and a central server aims to test whether the underlying discrete distribution is uniform. This classical problem has been extensively studied in similar settings, such as when n = 1 or when the task is to estimate the underlying distribution.\n\nThe main contribution of this paper is a tight characterization of the separation rates in the large-sample regime (where n is sufficiently large). The primary technical tool employed in the proof is Le Cam's statistical equivalence. By leveraging the equivalence between the Gaussian location model (GLM) and the multinomial model in large local sample regimes, the problem is reduced to the GLM, which has been addressed in previous works.\n\nWhile Le Cam's statistical equivalence is indeed a powerful and elegant method for establishing minimax rates, I find the novelty and contribution of this work to be somewhat limited. The main technical tools are well-established, and the primary theorem applies only to a restricted parameter regime. Additionally, the discussion of related prior works could be more comprehensive. Lastly, the presentation of the paper could be significantly improved.\n\n============== Post rebuttal =========\nI have updated my score accordingly, given that the authors claim that the techniques used in this work can be extended to prove lower bounds under interactive models.", "questions": "N/A", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The main technical tool, the notion of statistical equivalence, seems to be a suitable and powerful method for addressing this class of problems, as it allows for the reduction of one problem to another.", "weaknesses": "1. **Limited Contributions**: The main technical contribution of this paper appears to be limited, as the statistical distance between multinomial models and Gaussian location models is derived from prior works. Additionally, distributed testing for GLM under local DP/communication constraints is also well-established. The main theorems only establish the separation rates in a limited regime (i.e., large \\(n\\)). The proposed reduction, and consequently the statistical equivalence, apply only to the non-interactive setting, and it is well-known that establishing interactive lower bounds is significantly more challenging.\n\n2. **Insufficient Discussion of Prior Works**: There are several relevant works that need further discussion. For instance, the \"communication super-efficiency\" effect, which has appeared in the \"estimation\" version of the problem in [1], is not discussed in the current draft. Although the paper is included in the references, I could not find the corresponding citation in the main text.\n\n3. **Presentation**: The organization and presentation of the paper can be significantly improved. For example, the symbols \\(\\mathcal{Q}\\) and \\(\\mathcal{P}\\) are sometimes used to refer to multinomial and Gaussian models (e.g., in the proof of Theorem 1) without being explicitly stated, and at other times they refer to two general statistical models (e.g., in Section A.2), which is confusing. It would be helpful to explicitly specify these notations. There are also many minor typos and unclear notations that reduce readability. Some examples include:\n   - Line 286: \"identified\" should be \"identical\"?\n   - Line 303: unclear reference []\n   - Line 642: missing reference\n   - Line 673: missing reference\n\n\n[1] Archaya et. al., \"Distributed estimation with multiple samples per user: Sharp rates and phase transition\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our sincere thanks to the Reviewer for taking the time and effort to thoroughly review, the insightful comments and constructive feedback on our paper. The Reviewer identifies areas for improvement, which we will address point-by-point below.\n\n### *Limited contribution:* \n\n\"*The main technical contribution of this paper appears to be limited, as the statistical distance between multinomial models and Gaussian location models is derived from prior works. Additionally, distributed testing for GLM under local DP/communication constraints is also well-established. The main theorems only establish the separation rates in a limited regime (i.e., large (n)).*\"\n\nFederated goodness-of-fit testing for discrete distributions under bandwidth and differential privacy constraints is a notoriously hard problem to study, which has been solved for the case of $n=1$ in a series of articles by Acharya et. al. We believe that the $n \\geq 1$ problem is very interesting, as it encompasses a very important class of models in a setting where bandwidth and differential privacy constraints are very natural. \n\nCurrently, the tools available in the literature seem insufficient to tackle the problem for all regimes (i.e. small $n$, large $n$ and everything in between). The tools developed by Acharya et. al. are, roughly speaking, combinatorial in nature, which more or less constrains its application to the $n=1$ case. The tools developed in the Gaussian setting recover the full regime, but do not apply outside the Gaussian setting. This is unlike federated estimation setting, which has been solved for \"all regimes\" and where boardly applicable / general theory for deriving upper- and lower-bounds exist, such as those developed in [3].\nBecause we believe the problem to be both very difficult to solve but also highly important. Therefore, we are of the opinion that although our main theorems only establish the minimax separation rates in a limited regime, our paper still provides an important contribution.\n\n\"*The proposed reduction, and consequently the statistical equivalence, apply only to the non-interactive setting, and it is well-known that establishing interactive lower bounds is significantly more challenging.*\"\n\nThank you for raising this point. For the problem of goodness-of-fit testing, it is known that there is no benefit to having interactive protocols, when shared randomness is available. Shared randomness, which can be seen as a subset of sequentially interactive protocols, is considered in our work. It is known that shared randomness protocols are sufficient to obtain optimal rates in the problems that we consider in our article, in the sense that e.g. general sequential protocols do not improve upon it performance wise, see for example [2].\n\nThat said, we agree that for our general theory, as developed in Section A, interactive protocols are certainly interesting to consider; there known settings where e.g. sequentially interactive protocols strictly improve over non-interactive protocols, such as adaptation (see e.g. [5]). We have been able to extend the theory here to the sequential and blackboard protocols such as considered in [4]. In the revised version of our article, we also discuss interactive protocols more generally, including the works of [2,3,4,5]. \n\n### *Insufficient discussion of prior works:* \n\nWe thank the Reviewer for the suggestion of discussing [1] and other related work more expansively. Beyond our introduction, we have used some of the space provided by the additional page of the revised version to provide a more detailed comparison of our results to [1,2,6,7]. Below, we outline the extended discussion of these relevant results.\n\nWe cited [1] in our introduction, and we agree that their work is directly relevant to our results. They study what can be seen as the (bandwidth constrained) `estimation version' of the testing problem considered by us. Their results indeed describe a similar communication super-efficiency phenomenon as we find in the testing setting: the small $n$ exponential benefit of additional communication budget is lost as the number of observations locally become large comparatively to $d$. We contrast our main theorems with those of [1] in Section 3: \"Minimax rates in the large sample regime\" in the revised version of our manuscript.\n\nSuch a communication super-efficiency phenomenon can also be observed in continuous data, when contrasting the work of [6] with [7], who study density estimation in a distributed setting under bandwidth constraints. We have included a discussion of these results in our revised version also.\n\n### *The Presentation:* \nThank you for your suggestions on how to further improve the presentation of the paper. Indeed, the statements / machinery of Section A of the appendix apply to general models (denoted by $\\mathcal{P}$ and $\\mathcal{Q}$), whereas in the main text of the article, $\\mathcal{P}$ and $\\mathcal{Q}$ specifically refer to the Gaussian location model and the multinomial model, respectively. To clarify this, we open Section A in our revised manuscript with the sentence: *\"In this section, we present results and theoretical developments that apply to general models denoted by $\\mathcal{P}$ and $\\mathcal{Q}$. While the main text specifically focuses on the Gaussian location model for $\\mathcal{P}$ and the multinomial model for $\\mathcal{Q}$, the machinery developed here is applicable to general statistical models.\"* By doing so, we hope to provide a clear distinction between the general models discussed in Section A and the specific models explored in the main text. If you believe distinct notation, e.g. $\\mathcal{P}^{gauss}$ and $\\mathcal{Q}^{mult}$ is more helpful, we are also open such a change.\n\nWe thank you also for pointing out the typos and missing references. On top of fixing the ones you pointed out, we have conducted a very careful proofread, making sure the revised manuscript does not contain such mistakes.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bA9qs8D5cE", "reviewer": "Reviewer_aGfz", "summary": "This paper investigates the problem of Goodness-of-fit testing for multinomial distributions in federated learning in the case where the number of samples n per federated agent is large, and under a bandwidth or privacy constraint. Under certain scaling regimes, the authors characterize the number of samples needed for risk (defined as sum of Type I and Type II error) to vanish asymptotically. The authors provide an excellent description of Le Cam theory, and discuss it’s relation to their work.", "questions": "The title says \"Optimal Private *and* Communication Constraint Distributed Goodness-of-Fit Testing\". However, it seems that you consider \"Optimal Private *or* Communication Constraint\", as Theorem 1 and 2 consider these constraints separately. Can you comment on this? What would happen if you consider these jointly?", "limitations": "I think this paper is thorough, and details the exact theoretical setting where the proven results apply.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "This paper is very well written. It is both thorough and rigorous, while still being approachable and well-written. Section 4 and 5 specifically are very nicely done and explain a complex idea simply. The results are interesting, and novel to my knowledge.", "weaknesses": "The paragraphs after Theorem 1 and 2 respectively could be expanded somewhat. It would be interesting to see some discussion about the theorems in context.\n\nSmall Comments\n\n166: the the sample\n\n303: citation missing", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the time and effort spent on evaluating our paper, the positive feedback and the insightful question. Below, we address the  suggestions and questions raised by the Reviewer.\n\n*\"The paragraphs after Theorem 1 and 2 respectively could be expanded somewhat. It would be interesting to see some discussion about the theorems in context.\"* \n\nWe appreciate your suggestion to expand the discussion following Theorems 1 and 2. We agree that there are interesting phenomena that are not remarked on, or could be discussed further. In the revised version, we have expanded the discussion surrounding Theorem 1 and 2 to include the following:\n\n*After Theorem 1:* We have extended our discussion of the rate derived in the theorem when compared to the small $n$ rate. We now elaborate on the phase transition observed in our results, which is not observed in the $n = 1$ regime. We have also added a detailed discussion comparing our results to those of Acharya et al. [1] in the estimation setting. Specifically, we highlight the similar communication super-efficiency phenomenon observed in their work for distributed estimation of discrete distributions under bandwidth constraints. We explain how their results show a transition in the estimation risk depending on the relationship between the number of local observations $n$, the dimension $d$, and the communication budget $b$. Such a super-efficiency is also observed when comparing [6] and [7], but for continuous densities. See also our reply to Reviewer (Nun8).\n\n*After Theorem 2:* Similarly to the result of Theorem 1, the large $n$ problem undergoes phase transitions that are not observed in the $n=1$ version under differential privacy constraints. Even though there is no direct privacy equivalent to the communication super-efficiency phenomenon in Theorem 1, these phase transitions do mean that the problem undergoes significant changes in terms of its dynamics in the large $n$ regime. We discuss the meaning of these phase transitions in more detail in the revised version of the article.\n\n\"*The title says \"Optimal Private and Communication Constraint Distributed Goodness-of-Fit Testing\". However, it seems that you consider \"Optimal Private or Communication Constraint\", as Theorem 1 and 2 consider these constraints separately. Can you comment on this? What would happen if you consider these jointly?*\"\n\nThank you for this very interesting question. Indeed, Theorem 1 and 2 consider the constraints separately. The reason for this, is that for the Gaussian model for which leverage asymptotic equivalence, only results under both constraints separately have been established. Although we did not explicitly state this in the original version of the manuscript, the general theory we develop in Section A.2 could also be applied to settings in which bandwidth and differential privacy hold simultaneously. We have extended the results of Section A.2 to explicitly include protocols where both constraints hold at the same time. In general, we believe the setting were both constraints hold simultaneously could lead to very interesting questions; for example whether one one of the constraints necessarily more stringent. We know of [8], who consider  a setting with both constraints at the same time, for discrete distributions specifically. However, only the one observation per server setting ($n=1$) is considered in [8], which makes it impossible to leverage their results to the Gaussian model. Regardless, we have incorporated this discussion in the revised version of manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZetIZgtDcR", "reviewer": "Reviewer_4qfs", "summary": "This paper explores distributed goodness-of-fit testing for discrete distributions under bandwidth and differential privacy constraints. The authors extend results from multivariate Gaussian models using Le Cam’s theory of statistical equivalence. They derive matching minimax upper and lower bounds for the goodness-of-fit testing problem when the number of samples held locally is large.", "questions": "- How practical are the assumption $md\\log d/\\sqrt{n}=o(1)$ in real-world federated learning scenarios? Can you provide examples or case studies where these conditions hold?\n\n- The paper assumes large sample regimes for the derivation of the minimax rates. How would the results change if the sample size was not large? Are there any extensions or modifications of the theory to handle smaller sample sizes?\n\n- How does the proposed method compare with existing methods for distributed goodness-of-fit testing in terms of computational efficiency and communication overhead?", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The framework presented for extending goodness-of-fit testing from Gaussian models to discrete distributions is novel and addresses practical issues in federated learning scenarios. The derivation of matching minimax upper and lower bounds is rigorous and thorough, leveraging statistical equivalence effectively. The paper addresses key challenges in distributed settings, specifically under bandwidth and privacy constraints, which are crucial for modern applications in federated learning.", "weaknesses": "The results rely on the assumption $md\\log d/\\sqrt{n}=o(1)$, which can be attained when the number of data is large. When $n$ is large, the setting naturally gets close to the Gaussian case, from which some existing tools can be leveraged. In this sense, the analyses presented in this paper are not too surprising. Moreover, the absence of empirical validation or simulations to demonstrate the practical performance of the theoretical results limits the impact of the findings in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the time and effort invested in evaluating our work, the kind words, the constructive feedback and the interesting questions raised. We respond pointwise below.\n\n*\"The paper addresses key challenges in distributed settings, specifically under bandwidth and privacy constraints, which are crucial for modern applications in federated learning.\"*\n\nThank you for highlighting the importance of our work. \n\n*\"The results rely on the assumption $m d \\log d / \\sqrt{n} = o(1)$, which can be attained when the number of data is large. Moreover, the absence of empirical validation or simulations to demonstrate the practical performance of the theoretical results limits the impact of the findings in practice.\"*\n\nThe problem of federated goodness-of-fit testing for discrete distributions under bandwidth and differential privacy constraints is notoriously difficult to study (see also our reply to Reviewer (Nun8)). Just like the works covering the $n=1$ case, this work poses just one step in uncovering the principle phenomena underlying the problem. Whilst it is true that our work is theoretical in nature, and covers only the large local data regime, we believe the results offer practical guidance as well. For example, it provides guidance on whether methods that work for Gaussian models also perform well in the discrete setting, as turns out to be the case in the large local data regime. Furthermore, the optimal performance described by the separation rate provides a benchmark for further development of both methods and theory.\n\n*\"How practical are the assumption $m d \\log d / \\sqrt{n} = o(1)$ in real-world federated learning scenarios? Can you provide examples or case studies where these conditions hold?\"* \n\nThere are interesting real-world federated scenarios where $m d \\log d / \\sqrt{n} = o(1)$ is feasible. One such example is text mining, where even though the dictionary $d$ is large, it is feasible that the number of words mined $n$ is much larger still. Scenarios where $d$ is small to begin with might not be so interesting under bandwidth constraints, but often still are when considering differential privacy; for example in the case of categorical data observed by $m$ different hospitals adhering to a privacy constraint, with a patient pool of $n \\gg m^2$ in each hospital.\n\n*\"The paper assumes large sample regimes for the derivation of the minimax rates. How would the results change if the sample size was not large? Are there any extensions or modifications of the theory to handle smaller sample sizes?\"*\n\nFor goodness-of-fit testing in the Gaussian model, non-asymptotic minimax results are available (i.e. holding for any $d,n,m \\in \\mathbb{N}$), derived for bandwidth constraints in [11] and differential privacy constraints in [12]. For goodness-of-fit testing in discrete distributions under bandwidth and differential privacy constraints, the results of [13] assume $n=1$, but extend to any $n \\asymp 1$ without a change in the minimax rate. Matching upper- and lower-bounds have not been derived in the literature in the intermediate regime where $m^2 d^2 \\log^2 d \\lesssim n \\gg 1$, however. We have tried, but it turns out that goodness-of-fit testing for discrete distributions is more difficult in the federated setting. The techniques of [11,12] seem very specialized for Gaussian models, and the essentially combinatorial argument of [13] becomes cumbersome for large $n$, see also our reply to Reviewer (Nun8). \n\n*\"How does the proposed method compare with existing methods for distributed goodness-of-fit testing in terms of computational efficiency and communication overhead?\"* \n\nThis is an interesting question with a slightly involved answer. The overhead of transforming the discrete observations to \"Gaussian-like\" data as proposed in for example [14] is small; it essentially consists adding uniform perturbations to average frequencies. The overhead of the rate-optimal procedures in the Gaussian models depends heavily on whether bandwidth or differential privacy constraints are under consideration. Under bandwidth constraints, the methods proposed for Gaussian data in [11] enjoy decent computational overhead, depending on the \"regime\" (i.e. large $b$ compared to $m$ and $d$). We refer to Section 4 in [11] for details. Under differential privacy constraints, existing rate-optimal methods in the Gaussian models, for example those used in [12], are computationally expensive in $d$ in the regime where $\\epsilon \\ll \\sqrt{d}/\\sqrt{m}$ for shared randomness protocols, and $\\epsilon \\ll d / \\sqrt{m}$ for local randomness protocols. Computationally more feasible methods exist, but those attain slightly worse rates. We refer to [9, 10] for a discussion. In future research, we hope to develop methods that computationally efficient and rate optimal for the goodness-of-fit testing problem with discrete distributions. We included comments on this in the revised version of our manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DGWGMWfZJl", "reviewer": "Reviewer_3Xr9", "summary": "The paper focuses on the minmax rate for goodness-of-fit testing for discrete distributions under bandwidth and differential privacy constraints in a distributed setting, leveraging Le Cam’s theorem. The main distinction from previous literature lies in the consideration of the distributed setting.", "questions": "See Weaknesses", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written, well-organized, and mathematically rigorous, with a clear exposition of the concepts using probability theory. The key contribution is the extension of the optimal rate for goodness-of-fit testing under differential privacy to the distributed case. However, I have concerns regarding this extension, which I detail in Weaknesses.", "weaknesses": "I might be wrong, but I didn't see the difference between the distributed formulation in this paper and the central setting in other works (where data is available at one central location). The only exception is that the distributed formulation posits that each server adopts a local protocol (local privacy-mapping with bandwidth constraints). However, given that the raw data \n$X^{(j)},j=1,\\ldots,m$ are i.i.d., wouldn’t the optimal rate be achieved when all local protocols are equivalent? If one server has a better protocol than others, the risk defined after line 190 is not minimized. If this is true, the question is what distinguishes the proposed distributed protocol from the privacy-preserving case in a central setting? For the latter, the min-max rate has already been derived, as seen in:\n\n\"Local Privacy and Statistical Minimax Rates\"\n\n\"Robust Estimation of Discrete Distributions under Local Differential Privacy\"\n\n\"The Cost of Privacy: Optimal Rates of Convergence Performance Estimation with Differential Privacy\"\n\nThe paper needs to clearly articulate the differences and potential advantages of the distributed approach over these established results in the central setting. Without this clarification, the novelty and implications of the results may be unclear.\n\nMy score will change based on the authors' response to this question.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the time and effort dedicated to evaluating our paper and we thank you for your thoughtful review. We appreciate your recognition of the paper’s mathematical rigor, organization, and clarity. We would like to address the concerns and the question you raised regarding the differences between our distributed setting and the central setting in existing literature.\n\n\"*The paper needs to clearly articulate the differences and potential advantages of the distributed approach over these established results in the central setting. Without this clarification, the novelty and implications of the results may be unclear.*\" \n\nThank you for this constructive feedback. In our revised version of the manuscript, we now describe this difference explicitly, see also our response to your question below. \n\n\"*I might be wrong, but I didn't see the difference between the distributed formulation in this paper and the central setting in other works (where data is available at one central location). The only exception is that the distributed formulation posits that each server adopts a local protocol (local privacy-mapping with bandwidth constraints). However, given that the raw data are i.i.d., wouldn’t the optimal rate be achieved when all local protocols are equivalent? If one server has a better protocol than others, the risk defined after line 190 is not minimized. For the latter, the min-max rate has already been derived, as seen in: [15,16,17]*\"\n\nThis is a natural question to ask. The testing risk, as defined after line 190, is non-linear in the transcripts $Y = (Y^{(1)},\\ldots,Y^{(m)})$, (i.e. the output of the servers). As a result, it is not apriori clear whether optimal federated procedures have each server follow the same locally optimal protocol, even though the data is i.i.d. for each of the servers. It turns out that for certain values of $n$, $m$, $d$ and `contraint-budget' $b$ or $\\epsilon$, optimal distributed protocols have each server execute a different strategy. For example, for small budgets $b$, optimal certain servers might communicate information which only concerns a specific part of a partition of the domain, with each server \"covering\" a different part of the partition. We refer for the details of these methods of Section 4 in [11] and Section 3 in [12], whose methods extend to the discrete distribution setting using the theory developed in our paper.\n\nWhat separates the federated setting considered by us and e.g. [1,2,3,4,5,6,7,11,12] from [15,16,17] is indeed that protocol adopted by each server satisfies an individual bandwidth or privacy constraint, instead of just the final output of the inference (i.e. the final estimator in [15,16,17]). This turns out to have a profound impact on the best possible theoretical performance. Due to the non-linear nature of the risk considered, the differences between these settings are substantial, both in terms of optimal methods and best possible performance. Our theory underlines this general finding. For example, the rate described by Theorem 1 yields that there is always a benefit of increasing the number of servers $m$, as the separation rate decreases as $1/\\sqrt{m}$ (or faster, depending on $b$ and $d$). The non-linearity of the risk is what drives this difference between the two types of settings. If instead one would consider e.g. the average of local risks, the results would reflect those in the central / single server setting. In certain estimation settings, such an \"average of local losses\" makes sense to consider in a federated framework. For the problem of goodness-of-fit testing we consider, however, the non-linear nature of the problem is inherent. We have revised our explanation in the article to better reflect these differences.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
First of all, we would like to thank the Reviewers for carefully reading our paper and their interest in our work. We are happy to hear that the majority of the Reviewers found our paper "very well written" (aGfz), "well-written, well-organized" (3Xr9) and the theory derived "rigorous and thorough" (4qfs), "mathematically rigorous" (3Xr9), "thorough and rigorous, while still being approachable" (aGfz). We are also delighted to hear that our paper "addresses key challenges in distributed settings" (4qfs), and that "the results are interesting" (aGfz) and novel (q4fs, aGfz).

The Reviewers have also raised a few concerns and provided several suggestions which we have addressed point-by-point in the individual rebuttals. Here we collect the main changes in the manuscript.

* We have extended the discussion of our results, following the suggestions of each of the Reviewers (see the comments below for details). We have also followed suggestions on further improving the presentation and clarity.

* We extended the general theoretical machinery developed in Section A of the supplement, showing that these tools apply to the other federated settings; such as sequential protocols, blackboard protocols and settings where a bandwidth constraint and a differential privacy constraint are jointly imposed.

* Following suggestions of the Reviewers, we have added references to existing literature and have provided additional discussion of existing articles. Besides exploring interesting contrasts between existing work with ours, this also provides additional context for our work.   

* The reviewers identified some typos and missing references. In addition to addressing these issues, we conducted a thorough proofreading to ensure that the revised manuscript is free of such errors.

We would like to thank all the Reviewers for their consideration.

---

References discussed in the individual rebuttals:

[1] Acharya et. al., "Distributed estimation with multiple samples per user: Sharp rates and phase transition".

[2] Acharya et. al., "Interactive Inference under Information Constraints".

[3] Acharya et. al., "Unified Lower Bounds for Interactive High-dimensional Estimation under Information Constraints"

[4] Barnes et. al., "Fisher Information for Distributed Estimation under a Blackboard Communication Protocol"

[5] Cai et. al., "Distributed adaptive gaussian mean estimation with unknown variance: interactive protocol helps adaptation"

[6] Han et. al., "Distributed Statistical Estimation of High-Dimensional and Nonparametric Distributions"

[7] Szabo and Zaman, "Distributed nonparametric estimation under communication
constraints."

[8] Surin Ahn et. al., "Estimating Sparse Distributions Under Joint Communication and Privacy Constraints"

[9] Canonne et. al., "Private identity testing for high-dimensional distributions."

[10] Narayanan, "Private high-dimensional hypothesis testing"

[11] Szabo et. al., "Optimal high-dimensional and nonparametric distributed testing under communication constraints"

[12] Cai et. al., "Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests"

[13] Acharya et. al., "Lower Bounds from Chi-Square Contraction"

[14] Carter, "Deficiency distance between multinomial and multivariate normal experiments"

[15] Cai et. al., "The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy"

[16] Chhor and Sentenac, "Robust Estimation of Discrete Distributions under Local Differential Privacy"

[17] Duchi et. al., "Local Privacy and Statistical Minimax Rates"

Meta-review: This paper studies distributed goodness-of-fit testing for discrete distribution under bandwidth and differential privacy constraints. The authors consider the important extension from the $n=1$ case studied in detail by Archaya and co-authors to the interesting regime of $n\ge 1$ where some new techniques need to be employed. The authors derive matching minimax upper- and lower-bounds for the goodness-of-fit testing. Generally, reviewers acknowledge that the paper is interesting and makes some advancements, though one questioned the amount of novelty going from the $n=1$ case to the $n\ge 1$ case. The AC believes this paper crosses the bar and should be of interest to the statistical learning community at NeurIPS.
Decision: Accept (poster)