Optimal Private and Communication Constraint Distributed Goodness-of-Fit Testing for Discrete Distributions in the Large Sample Regime

Authors: lasse  vuursteen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 17:11:19

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.

Main paper: 
 introduction: 
 Federated learning is a fundamental problem in statistics and machine learning, where 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. The primary goal in these distributed data settings is to perform a 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 information constraints originated in the electrical engineering community, under the names "decentralized decision theory / the CEO problem" e.g. [90, 12, 92, 18, 58, 87] or "inference under multiterminal compression" (see [88] for an overview). These were largely motivated by applications where data is by construction observed and processed locally, such as astronomy, meteorology, 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) or networks of cellphone users, applied in areas such as word prediction, facial and voice recognition, virtual assistants like Siri or Google Assistant, autonomous vehicles, and earthquake prediction [65, 56, 51, 73, 67, 31] . In these settings, bandwidth often becomes a limited or 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 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 a 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 [35] , 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 to 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-means model, discrete distributions and parametric models in [37, 38, 1, 98, 3] , and density estimation [75, 59, 21] , and nonparametric regression in [23] . Bandwidth constraints have been studied for the many-normal-means and parametric models in e.g. [101, 39, 77, 20, 97, 50, 26, 25] , as well as nonparametric models, including Gaussian white noise [102] , nonparametric regression [82] , 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 [29] .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 observations each from a distribution on a 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, 86] 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 [15] 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 observations. To date, matching rates have been established only when each machine observes a single observation [9, 10, 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-fit testing for discrete distributions under bandwidth and differential privacy constraints in scenarios where the number of samples n 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 an 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-fit 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 is the same as the minimax rate for the latter problem, which was established in [85] and [22] , 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-equivalent.The rest of the paper is organized as follows. After a brief section on related work and notation, the article continues with a precise problem formulation in Section 2. 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-fit testing for discrete distributions under bandwidth and differential privacy constraints. In Section 3, the main results concerning the minimax rates are presented. Section 4 briefly outlines the main idea of the proof technique. Section 5 gives further insight into the comparison between discrete distributions and its comparable multivariate Gaussian model. The article ends with a 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.Minimax goodness-of-fit testing knows a rich literature within the statistics and machine learning communities, see [46, 53, 64, 80, 52] . The d-ary discrete distribution uniformity testing problem bares a close relationship with "classical" nonparametric goodness-of-fit testing in the sense of [14, 79, 33, 96] and other nonparametric testing problems, see Section 1.4 in [54] and references therein.For distributed goodness-of-fit 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 [8, 84, 85] and differential privacy constraints in [22] , with the authors deriving matching minimax upper-and lower-bounds for the goodness-of-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, 10, 5] . See also [28] for an overview. In these aforementioned works, the authors derive minimax rates goodness-of-fit 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-fit density testing for under local DP is considered in [36, 61] , where in [61] , the authors consider adaptation as well. For some investigations into the multiple observations per server case, see [34, 47] .For estimation, the bandwidth constraint estimation discrete distributions in the large sample-perserver case has been studied by [3] , who derive matching upper and lower-bounds up to logarithmic factors. However, their technique does not extend to the goodness-of-fit testing problem.Throughout this paper, we shall use the following notation. For two positive sequences a k and b k , we use A non-negative sequence M k is said to be of poly-logarithmic order in non-negative sequencesa k ≲ b k to mean that a k ≤ Cb k for some universal positive constant C. We write a k ≍ b k if both a k ≲ b k and b k ≲ a k , and a k ≪ b k if a k /b k = o(1).a k , b k , c k if there exists a constant c > 0 such that M k ≲ (log(a k ) log(b k ) log(c k )) c .Given measurable spaces (X , X ) and (Y, Y ), a Markov kernel K (between (X , X ) and target(Y, Y )) is a map K ≡ K(•|•) : Y × X → [0, 1]with the following two properties: The map x → K(A|x) is measurable for all A ∈ Y , and the map A → K(A|x) is a probability measure on Y for every x ∈ X .If S is a random variable on a probability space (X , X , P), we let P S denote its push-forward measure, i.e. the measure defined by P S (B) := P(S -1 (B)). We shall use E and E S as the expectation operator corresponding to P and P S . Random variables X, Y, Z form a Markov chain X → Y → Z whenever their joint distribution P (X,Y,Z) disintegrates as dP (X,Y,Z) = dP X dP Y |X dP Z|Y . 
problem formulation: 
 We begin by formally introducing the general framework of distributed inference.Consider a measurable space (X , X ) with a statistical model P = {P f : f ∈ F} defined on it. In the distributed framework, we consider j = 1, . . . , m servers, each receiving data X (j) drawn from a given distribution P f ∈ P. Each of the servers communicates a transcript Y (j) based on the data to a central server, which in turn computes its solution to the testing problem T (Y ) ∈ {0, 1} based on the aggregated transcripts Y = (Y (1) , . . . , Y (m) ). We shall use the convention that T (Y ) = 1 means rejecting the null hypothesis. The transcript generating mechanisms are then given by Markov kernels {K j } j=1,...,m , with the Markov kernel (i.e. conditional distribution) of the transcript Y (j) given the data X (j) and the randomness U shared by the servers denoted by K j (•|X (j) , U ). We formalize this in the following definition. Definition 1. A distributed testing protocol for the model P consists of a triplet{T, {K j } m j=1 , (U, U , P U )}, where {K j } m j=1 is a collection of Markov kernels K j : Y (j) ×X ×U → [0, 1] defined on a measurable space (Y (j) , Y (j) ), T : m j=1 Y (j) → {0, 1} is a measurable map and (U, U , P U ) is probability space.The probability space (U, U , P U ) is used to (possibly) generate a 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 to be a local randomness protocol if P U is trivial 1 . In an abuse of notation, we shall often refer to the entire triplet {T, {K j } j=1,...,m , (U, U , P U )} using just T . Given a distributed protocol and i.i.d. data from P f we shall use P f to denote the joint distribution of Y = (Y (1) , . . . , Y (m) ), the data X under P m f and the shared randomness U ∼ P U . Writing x = (x (1) , . . . , x (m) ) ∈ X m , let x → K(A|x, u) denote the Markov kernel m j=1 K j (•|x (j) , u) (i.e. the product measure). The independence structure of the data yields that P m f K = m j=1 P f K j and the push-forward measure of Y can be seen to disintegrate asP Y f (A) = P m f P U K(A) = P U P m f K(A) = K(A|x, u)dP m f (x)dP U (u),where the second equality follows from the independence of U with the data drawn from P f . The above disintegration of the push-forward measure of Y and the product structure of K can be interpreted as (X, Y, T (Y )) forming a Markov chain given U , in the sense of the diagramEQUATIONThe diagram indicates the flow of dependencies. The m servers each obtain data X (j) from P f , and generate a transcript Y (j) based on the data and shared randomness U . The central server then makes a decision T (Y ) based on the aggregated transcripts Y . For a definition of Markov kernels and Markov chains, see Section 1.2.Allowing transcript-generating mechanisms to access both shared and local randomness is important for our analysis, as shared randomness has been found to yield strictly better performance in distributed goodness-of-fit testing, see e.g. [9, 10, 5, 8, 84, 85, 22] . Shared randomness protocols can be seen as a subset of common interactive procedures, such as sequential and blackboard protocols (see e.g. [6] ). The aforementioned paper shows that for discrete distribution goodness-of-fit testing in the single observation per server case, sequential and blackboard protocols offer no benefit over shared randomness 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 large-number-of-observations case by comparing with a Gaussian model with 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.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 kernels {K j } j=1,...,m are defined on measurable spaces (Y (j) , Y (j) ) satisfying |Y (j) | ≤ 2 b for j = 1, . . . , m.We use T Lastly, we introduce the notion of differential privacy in the distributed setting. We will be focusing on the notion of differential privacy as put forward by [43, 44] . Differential privacy provides a mathematical framework that guarantees preservation of privacy in a notion akin to cryptographical guarantees. Formally, a differential privacy constraint on a transcript in our setting is formulated as follows.EQUATIONfor all A ∈ Y (j) , x, x ′ ∈ X , i ∈ {1, . . . , n}.A distributed testing protocol {T, {K j } m j=1 , (U, U , P U )}, is said be a distributed (ϵ, δ)-differentially private testing protocol if {K j } j=1,...,m satisfies (2) P U -a.s.Small values of ϵ and δ ensure that, even when the transcript Y (j) is publicly available, the sample X (j) underlying Y (j) is unidentifiable. We stress that this type of differential privacy guarantee concerns the local data X (j) in full, even X (j) consists of multiple observations. This is often referred local differential privacy, where the privacy guarantee regards each server as 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 T (ϵ,δ) LR and T (ϵ,δ) SR to denote the classes of all local-and shared randomness (ϵ, δ)-differentially private distributed testing protocols, respectively. We note that the machinery developed in Section A.2 allows consideration of both types of constraints simultaneously. In the main text of the article, we shall focus on the bandwidth constraint and differential privacy constraint separately as 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.We start by giving a formal description of sampling from a discrete distribution in the distributed setting. Consider a set with cardinality d; for simplicity, we take X = {1, . . . , d}. Any probability distribution such a set can be characterized by an element of the d -1-dimensional probability simplex S d , defined as q = (q 1 , . . . , q d ) ∈ [0, 1] d :d i=1 q i = 1 .In our distributed framework, each server j = 1, . . . , m observes a data X(j) taking values in {1, . . . , d}EQUATIONThat is, each server obtains n i.i.d. draws from a multinomial distribution with parameter q.The statistical decision problem of interest shall be that of goodness-of-fit or uniformity testing, i.e. distinguishing the hypothesesEQUATIONwhere q 0 = (q 01 , . . . , q 0d ) = (1/d, . . . , 1/d) ∈ S d andEQUATIONfor some fixed constant R > 0. The statistical model under consideration shall be denoted by Q = {Q n q : q ∈ F}. We define the testing risk for a distributed testing protocol T , for the hypotheses (4) (and statistical model Q) by sum of the type I and worst case type II error over the alternative class;R Q (T, H ρ ) := Q Y q0 T (Y ) + sup f ∈Hρ Q Y f (1 -T (Y )) .The minimax testing risk over a class of distributed protocols T is then defined asinf T ∈T R Q (T, H ρ ).It is clear that, as ρ tends to 0, the minimax testing risk should increase. We are interested in finding the so called minimax separation rate, or detection boundary, which is a sequence ρ * depending on the model characteristics n, d, m and T such that the minimax testing risk converges to0 if ρ ≪ ρ * or 1 if ρ ≫ ρ * .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 ρ 2 ≍ √ d mn when T consists of the class of all testing protocols, as was established in [70] and [94] .When T is taken to be one of the bandwidth or privacy constraint classes of tests, i.e. T , it is sensible to expect ρ * to depend on the bandwidth or differential privacy parameters, b and (ϵ, δ), respectively. In the distributed discrete distribution setupj described above with n = 1, such minimax rates have been derived in [9, 10] . 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/ √ n = 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-fit 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 a d-dimensional distributed Gaussian model, as 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 D of the appendix.Theorem 1. Consider sequences m ≡ m ν , b ≡ b ν , d ≡ d ν and n ≡ n ν such that md → ∞ whilst md log d/ √ n ν→∞ → 0.Suppose that ρ ≡ ρ ν is a nonnegative sequence satisfyingEQUATIONThen, LR in the above display), the minimax separation rate is given byinf T ∈T (b) SR R Q (T, H Mν ρ ) → 0 for any M ν → ∞, 1 for any M ν → 0.EQUATIONThe theorem above shows that the minimax rate for the distributed multinomial model under bandwidth 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 a signal detection problem in a d-dimensional distributed Gaussian model, as derived in [85] , Theorems 3.1 and 3.2. In Section 4, we shall provide a proof of this result through the notion of statistical equivalence, where we explicitly use that the multinomial model is asymptotically similar to a 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 = 1 is established in [9, 10] . Specifically, they find thatρ 2 ≍ d m √ 2 b ∧din case of access to shared randomness, Several aspects of this minimax rate are intriguing. First, unlike in the "large n case" for the same model and hypothesis (( 6) and ( 7)), there is no elbow effect. Secondly, the benefit (i.e. "efficiency gain") from an increase in bandwidth is exponential, whereas in the large sample scenario of Theorem 4 it is 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 2. For any sequences m ≡ m ν , d ≡ d ν and n ≡ n ν such that md → ∞, md log d √ n ν→∞ → 0, n -1/4 ≪ ϵ ≡ ϵ ν ≤ 1, δ ≡ δ ν ≍ (md) -p for some p > 1.The minimax separation rate in the distributed multinomial model Q for testing the hypotheses (4) using locally (ϵ, δ)-differentially private protocols isρ 2 ≍ poly-log(d, m, n) d mnϵ 2 if ϵ ≥ √ d √ m , √ d √ mnϵ if 1 √ md ≤ ϵ < √ d √ m (9)in the case of having access to shared randomness. In the case of having only access to local randomness, it is given byEQUATION)We provide a proof of the theorem in Section D 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 4 and 5 in [22] , who describe a more general setup which includes signal detection in the d-dimensional distributed Gaussian model as a special case 2 . Also in the case of privacy, there is 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 minimax rate in the multinomial model for n = 1 is derived in [9, 5] ;ρ 2 ≍ d mϵ 2 in case of access to shared randomness, d √ dmϵ 2 without access to shared randomness. (11) Comparing this rate to 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 to the cardinality of the sample space.4 Deriving the minimax rates through statistical equivalenceThe 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 a powerful tool for establishing minimax rates in statistical decision theoretic problems. In this section, we shall provide a brief introduction to statistical equivalence, and show how it can be used to derive the minimax rates for the distributed multinomial model under bandwidth and differential privacy constraints. Further details on the statistical equivalence and a 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. If a model is close to another model in Le Cam's distance, then there is a mapping of solutions to decision theoretic problems from one model to the other. Whenever the risk of the decision problem is bounded, this means that similar performance can be achieved in the two models. Consequently, studying the complex model can be reduced to 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 P = {P f : f ∈ F } (a collection of probability distributions) on a measurable space (X , X ) (the sample space). For this article, we consider only models with Polish sample spaces and corresponding Borel sigma-algebras and dominated models, meaning that there exists a sigma-finite measure µ such that P f ≪ µ for all f ∈ F. This greatly simplifies the definition of deficiency, given next.Given another model Q = {Q f : f ∈ F} indexed by the same set F and sample space ( X , X ), we define the deficiency of P with respect to Q asEQUATION)where the infimum is taken over all Markov kernels C : X × X → [0, 1] and the probability measureP f C : X → [0, 1] is understood as P f C(A) := x∈X C(A|x)dP f (x). This is equivalent to the more general notion of deficiency of [27] for dominated models on Polish spaces (see Proposition 9.2 in [68] ).Le Cam's deficiency distance between P and Q is then defined as ∆(P, Q) = max {d(P; Q), d(Q, P)}. This semi-metric becomes a metric whenever P and Q are identified whenever d(P; Q) + d(Q, P) = 0. Two sequences of experiments P ν and Q ν are called asymptotically equivalent if their difference ∆(P ν , Q ν ) tends to zero as ν approaches infinity. Conversely, such sequences shall be called asymptotically nonequivalent if∆(P ν , Q ν ) > c as ν → ∞ for a fixed constant c > 0.In Section A.2, we prove that models that are close in the Le Cam metric (compared to m) have similar testing risks in the distributed setup. We leverage this result in combination with the fact that the distributed multinomial model is asymptotically equivalent to a d-dimensional distributed Gaussian model, which we describe next.Consider for q ∈ F and i = 1, . . . , d the random variablesEQUATIONLetEQUATIONd ). Let P denote the corresponding experiment. It is shown in [30] 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 7 in [30] thatEQUATIONwhere C R > 0 is a 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 distance is small. Its proof is given in Section A.2 of the appendix. Lemma 1. Suppose m∆(Q; P) ≤ ϱ for ϱ > 0. Then, it holds that inf T ∈T (P)R P (T, H 1 ) -inf T ∈T (Q) R Q (T, H 1 ) ≤ 2ϱ,whereT is either T b SR , T b LR , T (ϵ,δ) SR or T (ϵ,δ) LR .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: Yes.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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
experimental result reproducibility: 
 Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: NA Justification: No code / experiments are provided.• The answer NA means that the paper does not include experiments.• 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 a 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 a 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 to 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 to 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 NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
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 a 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. In 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 N (j) = (NEQUATIONd ) taking values in {1, . . . , n} d , whereN (j) k ≡ N (j) k X(j) = i : X(j) i = k . Let Q ′ denote the model generated by the observations N (j) . This model is equivalent to Q, meaning ∆(Q, Q ′ ) = 0.To see this, note that forx = (x 1 , . . . , x n ) ∈ {1, . . . , d} n , Q X(j) = x = n Π i=1 Q X(j) i = x i = Π k∈{1,...,d} q |{i:xi=k}| k for all Q ∈ Q,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 statistics N (j) to obtain a statistic that tends towards a d-dimensional Gaussian random vector. When d and m are not too large with respect to n, 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 N (j) takes values in {1, . . . , n} d , the full data can be transmitted whenever there are at least d log 2 n-bits are available per server. However, recalling that the observation X(j) takes values in the space {1, . . . , d} n , which has cardinality bounded above by 2 n log 2 d , we also obtain that the full data can be transmitted whenever n log 2 d-bits are available. Consequently, whenever b ≳ d log 2 (n + 1) ∧ n log 2 d, the distributed problem has the same minimax separation rate for the hypothesis in (4) as the unconstrained problem with nm observations;ρ 2 Q ≍ √ d mn .For the Gaussian problem, this is only the case whenever b ≳ d, as can be seen from Theorem 4. This indicates a kind of "tipping point" occuring whenever n gets small compared to d, where in a 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 a distributed testing under bandwidth constraints perspective, as there are sub-regimes in which the Gaussian model has a 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 a 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 that for any n, d ∈ N withEQUATIONit holds thatEQUATION)where P is the experiment generated by the observations in (13), Q is generated according to (3), both indexed by F as given in (5) .The proof of the theorem is given in Section D. It leverages that there exist distributed, b-bit bandwidth constraint settings in which the (distributed) multinomial model allows for consistent goodness-of-fit 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√ d/ log 2 (d) ≥ d/n ≫ 1.This reasoning crucially exploits the differing minimax rates that occur under the bandwidth constraint, since without such a constraint, the same goodness-of-fit testing problem of (4) would have similar minimax performance for both of the models.Question: Does the paper provide open access to the data and code, with sufficient instructions 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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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 md 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 to distinctly different phenomena.The applicability of our results is somewhat constrained by the requirement that md log d/ √ n = o(1), which limits the range of model characteristics we can consider. Consequently, further work is needed to understand the behavior of the distributed multinomial model in other regimes. The non-equivalence 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 a different Gaussian model that is equivalent to the distributed multinomial model even in the small n regime.The results in this paper are derived through the notion of statistical equivalence, which is a powerful tool for establishing minimax rates in statistical decision theoretic problems. The results and techniques can be applied more generally to other distributed inference problems, and proving more general results concerning statistical equivalence and distributed inference is an interesting avenue for future research.A downside of leveraging statistical equivalence is that it generally does not provide a direct path to obtain methods that are minimax rate optimal. However, Theorem 1 and Section 7 in [30] provide a specific transformation that converts the local multinomial sample into a statistic approximately distributed as a 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.We introduce some formal notions of Le Cam theory first in Section A.1. Then, in Section A.2, we study the equivalence of models in the distributed setting. The theoretical developments presented in this section apply to general models denoted by P and Q; 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 statistical experiment is a set of probability distributions P = {P f : f ∈ F} (a model) on a measurable space (X , X ) (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-finite measure µ such that P f ≪ µ for all f ∈ F. In a slight abuse of terminology, we shall sometimes refer to P as the experiment, suppressing the presence of the sample space and indexing set.Given another statistical experiment with model Q = {Q f : f ∈ F } indexed by the same set F and sample space ( X , X ), we define the deficiency of P with respect to Q asEQUATION)where the infimum is taken over all Markov kernels C : X × X → [0, 1] and the probability measureEQUATIONThis is equivalent to 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 to which Q can be approximated by an experiment P. If d(P; Q) ≤ ϱ, it 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 a multiple of ϱ.To make this precise, let F be a measurable space and consider a function ℓ : F × D → [0, 1] on a measurable space (D, D), such that t → ℓ(f, t) is measurable for all f ∈ F, which we shall refer to a loss functions. We shall consider a decision procedure for (Q, D) to be a Markov kernelD : D × X → [0, 1]. If d(P; Q) ≤ ϱ, there exists C : X × X → [0, 1]such that for all decision procedures D for (Q, D) we have thatℓ(f, φ)dP f CD(φ) ≤ ℓ(f, φ)dQ f D(φ) + 2ϱ, for all f ∈ F.Here, the Markov kernel Q f D is to be understood in the sense of (18) and CD : D × X → [0, 1] asCD(A|x) = D(A|x)dC(x|x).There is also the following reverse implication; suppose that there exists a loss function ℓ : F × D → [0, 1] on a measurable space (D, D), andinf C inf D sup f ∈F ℓ(f, φ)dQ f D(φ) - ℓ(f, φ)dP f CD(φ) > 2ϱ,where the two infimums are over all decision procedures D and Markov kernels C : X × X → [0, 1]. Then, d(Q, P) > ϱ. This follows immediately from e.g. Lemma 12 in the appendix, since x → ℓ(f, φ)dD(φ|x) is measurable. In the more extensive framework considered in e.g. [27] , such a reverse implication for risk functions fully characterizes the deficiency between two models, but this framework is not needed in what follows.Le Cam's deficiency distance between P and Q is then defined as∆(P, Q) = max {d(P; Q), d(Q, P)} .This semi-metric becomes a metric whenever P and Q are identified whenever d(P; Q) + d(Q, P) = 0. Two sequences of experiments P ν and Q ν are called asymptotically equivalent if their difference ∆(P ν , Q ν ) tends to zero as ν approaches infinity. Conversely, such sequences shall be called asymptotically nonequivalent if ∆(P ν , Q ν ) > c as ν → ∞ for a fixed constant c > 0.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 ∈ X there exists a measurable map ψ A : X → R such thatP f A ∩ S -1 (B) = B ψ A (x)dP S f (x) for all B ∈ X and f ∈ F.Here, the measure P S f is to be understood as the push-forward measure P S f (B) = P f (S -1 (B)). A sufficient statistic allows for transforming observations from one model to 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 ′ := {P S f : f ∈ F} satisfies ∆(P, P ′ ) = 0. The next lemma is the Neyman-Fisher factorization theorem gives a useful characterization of sufficiency of a statistic for models that admit densities with respect to the same dominating measure. Lemma 2. Suppose that P f ≪ µ for all P f ∈ P with µ a sigma-finite measure. A statistic S : X → X is sufficient for P if and only if there exists measurable functions g f : R → R and h : X → R such that dP f dµ (x) = g f (S(x))h(x) for almost every x ∈ X and every f ∈ F.A proof for both the lemma and the last statement of the previous paragraph can be found in Chapter 5 of [62] .We now turn to the distributed setting considered in the paper, where j = 1, . . . , m servers each receive data X (j) drawn from a distribution P f and sample space (X , X ). 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. [6, 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).A distributed protocol for the experiment P with decision space (D, D) consists of a triplet {D, K, (U, U , P U )}, a Markov kernel D : D × m j=1 Y (j) → [0, 1] and a probability space (U, U , P U ), and K is a collection of Markov kernels.To unpack all this notation: the Markov kernel D takes the role of the decision procedure, where the decision is to made on the basis of the transcripts generated by the Markov kernels K. The transcripts are in turn generated based on the data and a source of shared randomness independent of the data. The probability space (U, U , P U ) plays the role of the source of randomness that is shared by the servers. The distributed protocol is said to have no access to shared randomness or to be a local randomness protocol if U is the trivial sigma-algebra.In this section, we shall consider three types of communication architectures:• One shot protocols: K = {K j } j=1,...,m where K j : Y(j) × (X × U) → [0, 1]. Theseprotocols are what are considered in the main text of the paper.• Sequential protocols: K = {K j } j=1,...,m where K j :Y (j) × (X × U × Y (1) × • • • × Y (j-1) ) → [0, 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:• Blackboard protocols: K = {K j t } j=1,...,m,t=1,...,T where K j 1 :Y (j) × (X × U) → [0, 1] and K j t : Y (j) × X × U × (Y (1) × • • • × Y (m) ) ⊗(t-1) → [0, 1],for t = 2, . . . , T . That is, the transcript generated by server j is based on the data, the shared randomness, and the transcripts of all the servers from the previous round.For one shot protocols, we have in terms of random variables that X (j) ∼ P f , U ∼ P U , Y (j) |(X (j) , U ) ∼ K j (•|X (j) , U ) for j = 1, . . . , m and φ ∼ D(•|Y ) with Y = (Y (1) , . . . , Y (m) ). This gives rise to a Markov chainEQUATIONFor x = (x (1) , . . . , x (m) ) ∈ X m , u ∈ U and {K j } j=1,...,m , let x → K(A|x) be the Markov kernel product distribution m j=1 K j (•|x (j) , u). Given a distributed protocol and i.i.d. data from P f we shall use P f to denote the joint distribution the data X ∼ P m f , the shared randomness U ∼ P U and Y = (Y (1) , . . . , Y (m) ) with Y |(X, U ) ∼ K(Y |X, U ). We have that P m f K = m j=1 P f K j and the push-forward measure of Y then disintegrates asEQUATIONwhere the second equality follows from the independence of U with the data X := (X (1) , . . . , X (m) ) drawn from P f .For sequential protocols, the push-forward measure of Y instead disintegrates asEQUATIONFor blackboard protocols, a similar disintegration applies for each of the rounds.A one shot or sequential distributed protocol is said to satisfy a b-bit bandwidth constraint if its kernels {K j } j=1,...,m are defined on spaces satisfying |Y (j) | ≤ 2 b . For blackboard protocols, various bandwidth constraints can be imposed, such as a b-bit bandwidth constraint for each round t = 1, . . . , T .Given Markov Kernels C j : X × X → [0, 1], j = 1, . . . , m, a distributed one shot protocol {D, {K j } j=1,...,m , (U, U , P U )} for the model P, yields a distributed protocol for the model Q: {D, {CK j } j=1,...,m , (U, U , P U )}. If {K j } j=1,...,m is b-bit bandwidth constraint, the collection of kernels {C j K j } j=1,...,m do so too, as each C j K j is defined on Y (j) × X .Similarly, for a sequential protocol, the Markov kernels C j and K j yield a distributed sequential protocol for the model Q with kernels {C j K j } j=1,...,m . If each K j is b-bit bandwidth constraint, so is each C j K j . For blackboard protocols, the same reasoning applies to each round t = 1, . . . , T . That is, type of protocol defined by the kernels K is "closed under composition" with kernels C j between X with target space X , where bandwidth constraints are preserved.EQUATION)Since the definition of differential privacy depends heavily on what one defines as the sample space, it is difficult to obtain a similar "transfer of distributed protocols" that respects the (ϵ, δ)-differential privacy constraint, hence the choice to consider local constraints only.A one shot or sequential distributed protocol shall be called locally ϵ-differentially private if (23) holds for each K j ; j = 1, . . . , m. For blackboard protocols, one can impose a (ϵ, δ)-differential privacy constraint for each round t = 1, . . . , T , or for the entire output over t = 1, . . . , T rounds.The following lemma shows that local ϵ-differential privacy, just like bandwidth constraints, carry over from one model to the other. Lemma 3. Let (X , X ) and ( X , X ) be measurable spaces and consider Markov kernels C :X × X → [0, 1] and K : Y × X → [0, 1]. If K is b-bit bandwidth constraint, so is the Markov kernel CK : Y × X → [0, 1].If K is locally ϵ-differentially private, so is CK. Furthermore, for any collection of Markov kernels K, the same reasoning applies to the collection {CK} K∈K , preserving bandwidth constraints and local differential privacy, as well as the protocol's architecture.Proof. The first statement has been remarked on earlier in the section. For the second statement, consider arbitrary x, x′ ∈ X and A ∈ Y . Using that C is a Markov kernel and applying (23) to K yieldsCK(A|x) = K(A|x)dC(x|x) = K(A|x)dC(x|x)dC(x ′ |x ′ ) ≤ e ϵ K(A|x ′ )dC(x ′ |x ′ ) + δ = e ϵ CK(A|x ′ ) + δ,which shows CK is locally (ϵ, δ)-differentially 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, {K j } j=1,...,m , (U, U , P U )} P f K j (•|X (j) , u)(y)dP U (u).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 one of the main tools for deriving the main results. It states roughly that, whenever there is 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 (ϵ, δ)-differentially private distributed procedure in the one model and there is small deficiency with another model, it means that there is comparable risk for the privacy constraint distributed decision problem. Lemma 4. Let m ∈ N. Consider two experiments P and Q with indexing set F, satisfying md(Q; P) ≤ ϱ for some ϱ > 0. Let J P and J Q denote the class of b-bit bandwidth constraint shared randomness protocols for the models P and Q respectively.Then, for any loss function ℓ :F × D → [0, 1], inf D∈J Q R Q (D, ℓ) -inf D∈J P R P (D, ℓ) ≤ ϱ.where in the infimum, in an abuse of notation, D denotes the entire distributed protocol triplet {D, {K j } j=1,...,m , (U, U , P U )}.The same statement is holds for J P and J Q denoting either classes of b-bit bandwidth constraint local randomness, sequential protocols, or any of these distributed protocols satisfying local (ϵ, δ)differential privacy constraints, for the respective models P and Q. If T md(Q; P) ≤ ϱ, the same statement holds for blackboard protocols with T rounds.Remark 1. This exemplifies also that, even though models P m = {P m f : f ∈ F } and Q m = {Q m f : f ∈ 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 2 in [62] , md(Q; P) ≤ ϱ implies that there exists a kernel C :EQUATION)By Lemma 3, the kernels K = {CK : K ∈ K} satisfy the a b-bit bandwidth constraint or local (ϵ, δ)differential privacy constraint if the collection {K j } j=1,...,m does. To illustrate this further, consider a one shot distributed protocol for P, {D, {K j } j=1,...,m , (U, U , P U )} ∈ J P , the distributed protocol D = {D, {CK j } j=1,...,m , (U, U , P U )} is then an element of J Q .Using the fact that ℓ is bounded by one and Lemma 13 in the appendix, it follows thatR Q ( D, ℓ) -R P (D, ℓ) ≤ ∥P U m j=1 P f K j -P U m j=1 Q f CK j ∥ TV ≤ m j=1 ∥P U P f K j -P U Q f CK j ∥ TV .By Lemma 14 in the appendix,∥P U P f K j -P U Q f CK j ∥ TV ≤ ∥P U P f -P U Q f C∥ TV = ∥P f -Q f C∥ TV ,which combined with (24) finishes for one shot protocols.Similar reasoning applies to sequential protocols. We start by noting that∥P f K 1 (• | u) -Q f CK 1 (• | u)∥ TV ≤ ∥P f -Q f C∥ TV ≤ ϱ/m,Lemma 11 implies that (for any u) there exists a coupling P of Y (1) ∼ P f K 1 (• | u) and Ỹ (1) ∼ Q f CK 1 (• | u) such that 2P(Y (1) ̸ = Ỹ (1) ) ≤ ϱ/m. Write K m:2 (• | x m , . . . , x 2 , u, y 1 ) := • • • dK m (y m | x m , u, y m-1 , . . . , y 1 ) • • • dK 2 (y 2 | x 2 , u, y 1 ).Using the disintegration relationship of ( 22), we obtain∥P U P m f K -P U Q f CK∥ TV ≤ ∥P m f K(• | u) -Q f CK(• | u)∥ TV dP U (u) ≤ ϱ/m + E Y (1) |U =u f ∥P m f K m:2 (• | u, Y (1) ) -Q f CK m:2 (• | u, Y (1) )∥ TV dP U (u).Iterating the above argument m -1 times, we the statement for sequential protocols. The statement for blackboard protocols follows by combining the above arguments for each round t = 1, . . . , T .In the remainder of this text, we shall constrain ourselves to a 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 a simple null versus a compositive alternative hypothesis in the distributed setting. To that extent, consider a test of the hypothesesEQUATIONand an experiment P with indexing set F satisfying {f 0 }∪H 1 ⊂ F. Consider for m ∈ N a distributed testing protocol for the model P to be a distributed protocol T ≡ {D, {K j } j=1,...,m , (U, U , P U )}, where in a slight abuse of notation, we shall also use T to denote the (possibly randomized) test T |Y ∼ D(•|Y ). Recalling the notation P Y f = P m f P U K as given in (21) , define the distributed testing risk for the hypotheses in (25) and the model P as R P (T, H 1 ) := P Y f0 D(T |Y ) + sup f ∈H1 P Y f (1 -D(T |Y )) .R P (T, H 1 ) ≤ inf T ∈T (Q) R Q (T, H 1 ) + 2ϱ, where T is either T b SR , T b LR , T (ϵ,δ) SR or T (ϵ,δ) LR .Proof. Given {T, {K j } j=1,...,m , (U, U , P U )} ∈ T (P), Lemma 4 applied to the loss functionℓ(f, t) := t1 {f0} (f ) + (1 -t)1 H1 (f )and using that {f 0 } ∪ H 1 ⊂ F givesP Y f0 D(T |Y ) < Q Y f0 D(T |Y ) + ϱ and sup f ∈H1 P Y f (1 -D(T |Y )) < sup f ∈H1 Q Y f (1 -D(T |Y )) + ϱfor some distributed testing protocol {D, { Kj } j=1,...,m , (U, U , P U )} in T (Q), which yields the first statement. The second statement follows by symmetry of the argument.The implications of Lemma 4 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 P ν is ρ ν , the bounded loss functionℓ ν (f, g) = 1 {d(f, g) ≤ Cρ ν } for C > 0can be used describe minimax estimation rates (in probability) between models P and Q. Since the paper is about testing, we shall not pursue this direction any further beyond this remark.In the next sections, we will explore the consequences of Lemma 5 for minimax distributed testing rates for both bandwidth-and privacy 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, or total variation; [3, 6, 7, 16? , 49, 9, 99, 13, 84, 85, 23, 22] .The proof techniques used for discrete distribution estimation employed in [3, 6] and [7] , tight lower-bounds can often be obtained by "tensorizing" the divergence-breaking the problem into a sum of local divergences. The inferential cost incurred due to bandwidth or privacy constraints are then captured via data processing arguments. Similar tensorization techniques are employed in other estimation problems, see for example [16, 99] .However, this tensorization approach does not yield tight bounds for testing problems. For example, [84] uses mutual information in a tensorization framework for testing but only recovers optimal rates when each server communicates a single bit. Similarly, [8] attempts an estimation-based approach for goodness-of-fit 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, 85, 22] employ methods that significantly diverge from those used in estimation. In [9] , a combinatorial expansion of the likelihood is used, effective for small sample sizes in the multinomial model but not generalizable to large numbers of 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-likelihood. This approach is not directly applicable to discrete models, due to the lack of quadratic structure in the log-likelihood of the multinomial model.For completeness, we provide the relevant results for the Gaussian model studied in [85] and [22] .The first two 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 ∈ {1, . . . , m} observesEQUATIONwith f ∈ R d and Z(j) i∼ N (0, I d ), i.i.d. for i = 1, . . . , n. The null hypothesis constitutes that f = 0 versus the alternative hypothesis thatEQUATION)The following is Theorem 3.1 from [85] . Theorem 4. For each α ∈ (0, 1) there exists a constant c α > 0 (depending only on α) such that ifEQUATIONthen in the shared randomness protocol caseinf T ∈T (b) SR R(H ρ , T ) > α for all n, m, d, b ∈ N.Similarly, forEQUATION)we have under the local randomness protocol thatinf T ∈T (b) LR R(H ρ , T ) > α for all n, m, d, b ∈ N.Following the proof Theorem 3.1 from [85] , we obtain the following lemma. Lemma 6. Let T b denote the class of b-bit bandwidth constrained shared-or local randomness distributed testing protocols and let ρ satisfy either (28) or (29), respectively. For any α ∈ (0, 1), there exists c α > 0 such that for all T ∈ T (b) it holds that infT ∈T R(H ρ , T ) > α -π(H c ρ ),where π = N (0, c -1/2 α d -1 ρ 2 Γ) for a symmetric, idempotent matrix Γ ∈ R d×d with d/2 ≤ rank( Γ) ≤ d.Similarly, the following result can be derived from the proof of Theorem 5 in [22] , by taking s > 0 in the theorem such that d Ls = d. Theorem 5. For each α ∈ (0, 1) there exists a constant c α > 0 (depending only on α), such that for any n, m, d ∈ N and0 < ϵ ≤ 1 and 0 ≤ δ ≤ c α m -3/2 ∧ nd -1 ϵ 2 ∧ n 1/2 d -1/2 ϵ 2 1+pfor some p > 0, (30) the conditionEQUATION)implies inf T ∈T (ϵ,δ) SR R(H ρ , T ) > α.Similarly, for any n, m, d ∈ N and ϵ, δ satisfying (30), the conditionEQUATION)implies that infT ∈T (ϵ,δ) LR R(H ρ , T ) > α.Following its proof, we obtain the following the following sub-result. Lemma 7. Let T denote the class of shared-or local randomness distributed testing protocols satisfying an (ϵ, δ)-differential privacy constraint for 0< ϵ ≤ 1, 0 ≤ δ ≤ c α m -1 ∧ c α ϵm -1/2 ∧ nϵ 2 ∧ n 2 d -1 ϵ 2 ∧ n 3/2 d -1/2 ϵ 2and let ρ satisfy either (28) or (29), respectively. For any α ∈ (0, 1), there exists c α > 0 such that for all T ∈ T (ϵ,δ) it holds thatR(H ρ , T ) > α -π(H c ρ ), where π = N (0, c -1/2 α d -1 ρ 2 Γ)EQUATION)Let ρ * ≡ ρ * ν be the minimax rate of the P-distributed problem, over the class T P , in the sense that ρ * equals (up to constants) the right-hand side of ( 6), ( 7), ( 9) or (10) . We split the proof into showing that ρ * is an upper and lower-bound for the Q-distributed problem over the class T P .The rate ρ * is an upper-bound (up to a poly-logarithmic factor) for the minimax rate in Q: Write, for q ∈ F, √ q = ( √ q i ) i∈ [d] . Since X (j) -√ q 0 is a sufficient statistic for X (j) , the model ( 13) is equivalent in the Le Cam sense the one generated byEQUATIONfor q ∈ F, which we shall denote by P. Consequently, by another application of Lemma 5, it suffices to show infT ∈T P R P (H ρν , T ) → 0. If ∥q -q 0 ∥ 1 ≥ ρ, Lemma 15 implies that ∥ √ q - √ q 0 ∥ 2 ≥ ρ/2. Consequently, if ρ ≡ ρ ν ≫ M ν ρ *where ρ * is of equal order of the minimax rate for the respective class of distributed protocols T P and M ν is an appropriately large factor (of poly-logarithmic order in case of differential privacy constraints), a distributed protocol T ∈ T P exists for the Gaussian model that achieves the separation rate for whenever H 0 : √ q -√ q 0 = 0 versus H ρ : ∥ √ q -√ q 0 ∥ 2 ≥ ρ/2. By the established equivalence of the minimax risks (33) , this implies that a protocol T ∈ T Q exists for the multinomial model as well. Thus, ρ ν is an upper-bound for the minimax separation rate for the class of distributed protocols T Q of the multinomial model.The rate ρ * is a lower-bound for the minimax rate in Q: Suppose that ρ ≡ ρ ν is of smaller order than the minimax rate ρ * of the class T P , in the sense that ρ * /ρ → ∞ as ν → ∞. We aim to use the Bayes risk lower-bound of Lemmas 6 and 7, which apply to a Gaussian prior. To accommodate a Gaussian prior with sufficient mass on the alternative hypothesis, we first need to address the "constraint on the signal" imposed by d i=1 q i = 1 for q ∈ F. To that extent, consider without loss of generality d to be divisible by two. LetI R := [-(R -1)/(R + 1), (R -1)/(R + 1)]. For all (f i ) i∈[d/2] ∈ I d/2 R / √ d, there exists a q f := (q f i ) i∈[d] ∈ F such that q f i = 1/d + f i / √ d for i = 1, . . . , d/2 and q f i = 1/d -f i / √ d for i = d/2 + 1, . . . , d. To see that q f ∈ F, note that d i=1 q f i = 1, q f ≥ 0 and max 1≤i,k≤d q f i q f k ≤ max c∈I R 1 + c 1 -c = R.Define F ′ as the setEQUATIONH ′ ρ := {q : q ∈ F ′ , ∥q -q 0 ∥ 1 ≥ ρ} . We have F ′ ⊂ F, which in turn implies that H ′ ρ ⊂ H ρ .Combined with the fact that the testing risk decreases by considering smaller alternative hypotheses, this results in infEQUATIONDefineg f = (1/2)(f, -f ) ∈ R d. By Pinsker's inequality,P nm √ q f - √ q0 -P nm g f TV ≤ 1 ∧ mn 4 D KL (P √ q-√ q0 ; P g f ) = 1 ∧ √ mn 2 q 0 + 2g f / √ d - √ q 0 -g f 2 =: D f ,where P n √ q-√ q0 denotes the distribution of (34) and the square root is to be understood as applied coordinate wise.Let π = N (0, d -1 (ρ * ) 2 Γ) for a symmetric, idempotent matrix Γ ∈ R d/2×d/2 with d/4 ≤ rank( Γ) ≤ d/2.We have that infT ∈T P R P (T, H ′ ρ ) ≥ inf T ∈J P P 0 T (Y ) + P g f (1 -T (Y ))dπ(f ) -2 D f dπ(f ) -π f : f / ∈ (I R / √ d) d/2 or (q f i ) i∈[d] -q 0 1 < ρ .By Lemma 8, the model{P g f : f ∈ I d/2 R /√ d} is equivalent to the model generated by the observations S (j) iEQUATIONEQUATIONwhere P is the model generated by the observations in display (36) for i = 1, . . . , d/2 and P ′ f denotes the distribution of the distributed protocol with data generated from f ∈ P.It follows from Lemma 6 in the case of bandwidth constraints or Lemma 7 in the case of privacy constraints (using that ρ ≪ ρ * in both cases) that the latter distributed testing risk is lower-bounded byEQUATION)Addressing the third term in the display above; the theorem(s) assume that md log d/ √ n ν→∞ → 0, b ≥ 1 and ϵ ≫ n -1/4 , we have that ρ * ≪ 1/ log(d), which gives ∥ √ df i ∥ ∞ → 0 with π-probability tending to one (see e.g. Lemma 16) , which in turn implies thatEQUATIONNext, we show that ∥(q f i ) i∈[d] -q 0 ∥ 1 ≥ ρ with π-probability tending to one. Sinced i=1 |q f i -q 0 | = 2 d/2 i=1 |f i / √d|, we have that for some constants c, c ′ > 0,π q f -q 0 1 < ρ ≤ π f / √ d 1 < ρ ≤ 1 -Pr ∥ ΓZ∥ 1 ≥ c ′ d ρ ρ * .where in the expression on the right-hand side, Z ∼ N (0, I d/2 ). Since ρ ≪ ρ * and Γ is idempotent with rank of the order d, we can conclude that the expression vanishes. This takes care of the third term in (38) .For the last term in (38) , the Taylor approximation√ 1 + y -1 = y/2 -y 2 /8 + y 3 16(1+η 5/2 y ) for some η ∈ [0, y], combined with the fact that ∥ √ df ∥ ∞ = o π (1) yields that 2 D f dπ(f ) ≤ 1 ∧ √ mnd (f 2 i ) i∈[d/2] 2 dπ(f ) ≲ √ mnρ 2 .Since the theorem(s) assume that md log d/ √ n ν→∞ → 0, b ≥ 1 and ϵ ≫ n -1/4 , the right-hand side of the above display vanishes.Proof of Theorem 3. Let T Q , T P denote the class of distributed b-bit bandwidth constrained testing protocols with b ∈ N, m ∈ N, d ∈ 2N and n ∈ 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 can assume d and n are both larger than some constant; and in particular we can assume d ∈ 2N without loss of generality. Assume d and n satisfy (15) , for a 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 b and m.Consider the hypothesis test given in (4), with H 0 : q 0 = (1/d, . . . , 1/d) ∈ S d and H ρ as in the display.Set b = ⌈n log 2 (d)⌉. When b ≥ n log 2 (d), the observations X(j) in the multinomial model as given in (3) are valid b-bit transcripts, since |{1, . . . , d} n | ≤ n log 2 (d). These transcripts are therefore sufficient for the nondistributed / unconstrained model Q m , i.e. corresponding to observations X ∼ Q q,nm for q ∈ F.Consequently, the distributed, b-bit bandwidth constraint testing risk for Q is equal to the testing riskQ m ; inf T ∈T Q R Q (H ρ , T ) = inf T R Q m (H ρ , T ).This means that, for all α ∈ (0, 1), there exists C α > 0 and a distributed protocol T satisfying a b-bandwidth constraint for distributed experiment Q such that infT ∈T Q R Q (H ρ , T ) < α whenever ρ 2 ≥ C α √ d mnwhere H ρ as defined in (4), as the minimax rate for the unconstrained problem with mn observations is ρ 2 Q m := √ d/(mn) (see e.g. Theorem 3 in [70] ).On the other hand, whenever mb = m⌈n log 2 (d)⌉ ≤ d, the minimax rate for the distributed testing risk of P for the (comparable) hypothesesH 0 : q = q 0 versus Hρ : ∥ √ q - √ q 0 ∥ 2 ≥ ρ is bounded from below by ρ 2 P ≍ √ d/( √ mn), as a consequence of Theorem 4. Specifically, following the proof of Theorem 1 above, we have that infT ∈T P R P (H ρ , T ) ≥ inf T ∈T P R P ( Hρ , T ),whereHρ := f ∈ (I R / √ d) d/2 : ∥f ∥ 1 ≥ ρ , for I R := [ √ 2(1 - √ R)/ √ 1 + R, √ 2( √ R -1)/ √ 1 + R],P is generated by the observationsX (j) = f + 1 √ n Z (j)for Z (j) ∼ N (0,I d/2 ), indexed by f ∈ (I R / √ d) d/2and the class T P is to be understood as the b-bit bandwidth constraint distributed testing protocols for the model P and j = 1, . . . , m machines. Lemma (6) implies that for all α ∈ (0, 1) the latter is bounded byα -N (0, c -1/2 α d -1 ρ 2 Γ) Hc ρ , for a symmetric, idempotent matrix Γ ∈ R d/2×d/2 with d/4 ≤ rank( Γ) ≤ d/2 α ∈ (0, 1), whenever ρ 2 ≤ c α √ d √mn for some small enough constant c α > 0. By the same analysis as conducted in the proof of Theorem 1 above (using that n ≤ log(d)), we find that the second term is at most α/2 for c α > 0 small enough. Summarizing, we find in particular that for some constant c α > 0, infT ∈T P R P (T, H ρ ) > 1/3, for all ρ 2 ≤ c √ d/( √ mn) and m, n, b, d such that mb ≤ d, where the number 1/3 is chosen without particular significance.EQUATIONfor some C α > 0 large enough and c α > 0 small enough. Take the constantC = ⌈C 2 α /c 2 α ⌉ such that if m = C, it holds that C α √ d mn ≤ ρ 2 ≤ c α √ d √ mn , with ρ 2 := C α √ d √ M √ mn .Now suppose that Cd(Q, P) ≤ 1/6. Lemma 5 then implies in that infT ∈T P R P (H ρ , T ) ≤ inf T ∈T Q R Q (H ρ , T ) + 1/6 < 1/3.This contradicts (40) . We conclude thatEQUATIONwhenever d/⌈n log 2 (d)⌉ > C. The result now follows with c = 1/(6C).The following lemma is used in the comparison of the multinomial model to the many-normal-means model.Lemma 8. Let d ∈ 2N, F ⊂ R d/2, and consider for i = 1, . . . , d independent random variables X i = h i + σZ i with σ > 0 and Z i ∼ N (0, 1) satisfyingh i = a i f i if i ≤ d/2, -a i f i-d/2 if i > d/2,for some f ∈ F and a = (a i ) ∼ N (0, 1) and f ∈ F.Then, ∆(P, Q) = 0.Proof. The statistic S = (a i X i -a i X d/2+1 ) i∈ [d] is sufficient for the model P by using Neyman-Fisher (Lemma 2). We havedP f dP 0 (X) = d Π i=1 exp σ -1 X i h i - 1 2σ 2 h 2 i = d/2 Π i=1 exp σ -1 (a i X i -a i X d/2+1 )f i - 1 σ 2 f 2 i = e σ -1 S ⊤ f -1 σ 2 ∥f ∥ 2 2 .In distribution, X = ( Xi ) i∈[d] is equal to S, which implies ∆(P, Q) = 0 per Lemma 2.The following lemmas are well known but included for completeness. Proof. By Pinsker's inequality,∥P n f -P n g ∥ TV ≤ n 2 D KL (P f ; P g ).A straightforward calculation gives that the latter is bounded by√ n 2σ ∥f -g∥ 2 .The following lemma relates the total variation distance between P, Q to the L 1 -distance between corresponding densities. Lemma 10. Let P, Q be probability measures dominated by a sigma-finite measure µ with corresponding probability densities p = dP dµ and q = dQ dµ . It holds that ∥P -Q∥ TV = 1 2 |p(x) -q(x)|dµ(x).Proof. See e.g. Section 2.4 in [93] .Lemma 11. For any two probability measures P and Q on a measurable space (X , X ) with X a Polish space and X its Borel sigma-algebra. There exists a coupling P X, X such that∥P -Q∥ TV = 2P X, X 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 , X ) and suppose that P ≪ ν for a sigma-finite measure ν. It holds thatEQUATION)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 ≥ 0}, {f ≤ 0} ∈ X , so |f | ≤ 1 means thatf dP ≤ f 1 {f ≥0} dP + -f 1 {f ≤0} dP - ≤ 1 {f ≥0} dP + + 1 {f ≤0} dP - ≤ ∥P + ∥ TV + ∥P -∥ TV ≤ 2∥P ∥ TV .For the other direction, note that f = sign(p -q) is measurable and bounded by 1, which gives1 2 f dP = |p -q|dν = ∥P -Q∥ TV ,where the last equality follows from Lemma 10.Lemma 13. Let P = m j=1 P j and Q = m j=1 Q j for probability measures P j , Q j defined on a common measurable space (X , X ), with probability densities p j , q j for j = 1, . . . m. It holds that∥P -Q∥ TV ≤ m j=1 ∥P j -Q j ∥ TV .Proof. The measures P j and Q j admit densities with respect to P j + Q j , which we shall denote by p j and q j , respectively, withp := m Π j=1 p j = d m j=1 P j d m j=1 (P j + Q j ) and q := m Π j=1 q j = d m j=1 Q j d m j=1 (P j + Q j ).Writing µ = m j=1 (P j + Q j ) and applying Lemma 10 we obtainEQUATIONBy the telescoping product identityEQUATIONand Fubini's Theorem, the right-hand side of ( 43) is bounded bym j=1 1 2 |p j (x j ) -q j (x j )|d(P j + Q j )(x j ) = m j=1 ∥P j -Q j ∥ TV .The following lemma can be seen as a data processing inequality for the total variation distance. Lemma 14. Let (X , X ) and (Y, Y ) be two measurable spaces and let K : Y × X → [0, 1] be a Markov kernel. For any probability measures P, Q defined on X it holds that ∥P K -QK∥ TV ≤ ∥P -Q∥ TV .Proof. This follows immediately from the representation in Lemma 12 combined with the fact that, for |f | ≤ 1, x → f (y)dK(y|x) is a measurable function bounded by 1, since K is Markov kernel. Hence,sup A |P K(A) -QK(A)| = 1 2 sup f f (y)dK(y|x)d(P -Q)(x) ≤ 1 2 sup f f (x)d(P -Q)(x).The next lemma bounds the L 1 -distance ∥p -q∥ 1 between densities with a multiple of the Hellinger distance 2 -1/2 ∥ √ p -√ q∥ 2 .Lemma 15. For two probability densities p, q with respect to µ, it holds that1 2 |p(x) -q(x)| dµ(x) ≤ p(x) -q(x) 2 dµ(x).Proof. The result follow from the Cauchy-Schwarz inequality and the fact that pdµ = qdµ = 1. See e.g. [93] for details.Lemma 16. Let K ∈ N and M ∈ R K×K be symmetric and positive definite. Consider the random vector G = (G 1 , . . . , G K ) ∼ N (0, M ). It holds that E max1≤i≤K |G i | ≤ 3∥M ∥ log(K) ∨ log(2) and Pr max 1≤i≤K G 2 i ≥ ∥M ∥ 2 x ≤ 2K e x/4, for all x > 0.Proof. It holds thatG d = √ M Z, with Z ∼ N (0, I K ).Since M is symmetric, positive definite, it has SVD decompositionM = V Diag(λ 1 , . . . , λ K )V ⊤ . Since V is orthonormal, √ M Z = V Diag(λ 1 , . . . , λ K )(V ⊤ Z) d = V Diag(λ 1 , . . . , λ K )Z. Writing V = [v 1 . . . v K ]where v k are orthogonal unit vectors, the latter display equalsK k=1 λ k v k Z k ∼ N (0, Diag(λ 1 , . . . , λ K )) .Consequently, maxk∈[K] |G k | d = max k∈[K] |λ k Z k | ≤ ∥M ∥ max k∈[K] |Z k |.Hence, it suffices to show thatPr max 1≤i≤K Z 2 i ≥ x ≤ 2K e x/4 .The case where K = 1 follows by standard Gaussian concentration properties. Assume K ≥ 2. For 0 ≤ t ≤ 1/4, Ee t maxi (Zi) 2 = e t E max i e t(Z 2 i -1) ≤ Ke 2t 2 +t .Taking t = 1/4 and applying Markov's inequality yields the second statement of the lemma. Furthermore, in view of Jensen's inequalityE max i (Z i ) 2 ≤ log(K) t + 2t + 1, which in turn yields E max i |Z i | ≤ 3 log(K).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, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of 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, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: NA Justification:Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a 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, or as supplemental material. 
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 are accompanied by error bars, confidence 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. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: NA Justification:Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it 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 https://neurips.cc/public/EthicsGuidelines? 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or 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 no societal 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 not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 as 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: NA Justification: All the results are of theoretical nature; no data or models are released. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?Answer: NA Justification:Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are 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 creators. 
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 of 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 is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: NAU is the trivial sigma-algebra (meaning U ∼ P U is a degenerate random variable)The above rates do not observe all phase transitions present in the more general setup of[22], as it pertains to the local differential privacy case in that paper, with σ = 1/ √ n in their notation. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.

The 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.

While 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.

============== Post rebuttal =========
I 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.
strength_weakness: strength_weakness: 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.

2. **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.

3. **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:
   - Line 286: "identified" should be "identical"?
   - Line 303: unclear reference []
   - Line 642: missing reference
   - Line 673: missing reference


[1] Archaya et. al., "Distributed estimation with multiple samples per user: Sharp rates and phase transition".
questions: questions: N/A
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Small Comments

166: the the sample

303: citation missing
questions: 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: limitations: I think this paper is thorough, and details the exact theoretical setting where the proven results apply.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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?

- 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?

- How does the proposed method compare with existing methods for distributed goodness-of-fit testing in terms of computational efficiency and communication overhead?
limitations: limitations: The authors adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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 
$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:

"Local Privacy and Statistical Minimax Rates"

"Robust Estimation of Discrete Distributions under Local Differential Privacy"

"The Cost of Privacy: Optimal Rates of Convergence Performance Estimation with Differential Privacy"

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.

My score will change based on the authors' response to this question.
questions: questions: See Weaknesses
limitations: limitations: The authors adequately addressed the limitations.

Comments: title: Reply to the rebuttal
Reply to Rebuttal
comment: Thanks for your response. My questions have been addressed. I'll raise the score.
We thank Reviewer (Nun8) for their response. We are happy to hear that they agree the $n\geq 1$ setting is interesting and that the extension is non-trivial.

We also find that there seems to be no known lower bound for blackboard or sequential protocols when $n > 1$ in the case of testing. In [2], the authors show that for $n=1$, there is no benefit to a sequential setup when compared to a shared randomness setup for uniformity testing with discrete data. For the Gaussian location model, we note that the proof of the shared randomness lower bounds of [11] can be extended to obtain the same (rate) results for sequential setups as well. Our (extended) machinery of the revised version then explicitly implies that there is no benefit of a sequential setups (outside of shared randomness) for uniformity testing with discrete data in the regime where $md \log (d) / \sqrt{n} = o(1)$. We will add details of this particular extension to the revised version of our paper.

Admittedly, this does not mean that we can conclude anything concerning the benefit of a sequential setup in the regime(s) where $n > 1$ and $md \log (d) / \sqrt{n} \gtrsim 1$. Also, we note that for blackboard protocols, much less is known and we can indeed not exclude to benefit of a blackboard protocol. Proving lower bounds in the testing setting for blackboard protocols specifically is an interesting but difficult problem with many open questions in the literature.

We will also include a discussion on why the technique of [1] does not yield an optimal lower bound in the testing setting in our revised version. We agree that including such a discussion is important to highlight the contribution of our work. We briefly sketch the reasons that this (and certain other) estimation techniques do not extend to the testing setting below.

Let us start with describing a similarity: for both the estimation and the testing problem, lower bounds are typically proven by bounding a divergence measure between probability distributions, such as the chi-square divergence, mutual information or total variation [1,3,7,11,12,13,18,19]. 

For estimation problems such as the one considered in [1], or those of the examples considered in [3], it suffices to essentially "tensorize" the divergence, which, loosely speaking, breaks the problem into the ``sum of the local divergences''. This is essentially the role of Theorem C.2 in [1] (see also Theorem 1 and 2 in [3]), which bounds the total variation between elements of a perturbed family of probability distributions by the sum of the local conditional "scores", local conditional variances of the transcript densities or the local mutual information, see (16), (17) and (18) in [1]'s supplement. The loss due to a bandwidth constraints (in [1]) or privacy constraint (in [3]) is then captured by data processing arguments. For estimation, such tensorization bounds turn out to give tight lower bounds. We note that a lot more goes into the proof of [1] (e.g. Poissonisation, sub-Gaussian concentration), but the principle difference with estimation and testing is this kind of tensorization step. Similar tensorization arguments can also be found in other estimation problems such as [4,7], for the Fisher information and mutual information respectively.

Such a "tensorization approach" does not yield tight bounds in testing problems. Using mutual information, [19] tries this tensorization approach for the testing problem, but they only recover the optimal testing rates when each server communicates only one bit ($b=1$). Another "estimation" approach tried for a goodness-of-fit testing problem can be found [18], which similarly obtain a lower bound for testing that is only tight for $b=1$, through a direct Taylor expansion of the likelihood (which can also be seen as tensorizing a divergence). The authors of [18] provide a detailed discussion of the shortcomings of the latter approach in Section 4 of their paper.

To obtain tight lower bounds for the testing problem, the papers that successfully do so for $b > 1$ and privacy constraints (i.e. [11,12,13]) use techniques that differ greatly from the techniques employed in [1,3]. In [13], the authors use a combinatorial expansion of the likelihood that works specifically for $n=1$ in the multinomial model, which does not generalize to large numbers of observations. [11,12] circumvent the latter issue in the Gaussian setting by employing a Brascamp-Lieb inequality, an inequality from functional analysis. This inequality explicitly uses the Gaussianity of the log-likelihood explicitly.

We hope that above additions to our work are satisfactory and we would like to thank you again for your consideration of our work.

Additional references:

[18] Acharya et. al., "Distributed signal detection under communication constraints"

[19] Szabo et. al., "Optimal distributed composite testing in high-dimensional Gaussian models with 1-bit communication"
Thank you for your response. I agree that the regime where $n \geq 1 $ is indeed interesting. However, my primary concern remains with the technical novelty of the work. The statistical distance between multinomial models and GLMs has already been established, and distributed testing for GLMs under local DP is known too. As such, the main technical contribution appears to be bridging these two results. While I acknowledge that this involves some non-trivial extension to distributed settings, I still find the overall contribution somewhat limited.

Regarding the interactive protocols, I also agree that, as in many other statistical tasks, interaction may not necessarily reduce the error. However, I believe there is currently no established lower bound for the $ n \geq 1 $ regime with sequential or blackboard interaction. In my view, developing such an interactive lower bound would significantly strengthen the work. Nevertheless, based on the current draft and the authors' response, it's unclear whether the framework developed in this paper can be extended to address this scenario.

I appreciate the authors' attention to the references and the presentation issues. Please do include a discussion of [1] explaining why their techniques do not apply to the testing problem.
We would like to thank the the Reviewer (aGfz) again for the time and effort spent on evaluating our work and for their response to our rebuttal.
Thank you for your response. I will maintain my rating.