1 Introduction↩︎

Federated learning is a collaborative distributed machine learning technique designed to address data governance and privacy concerns. It facilitates organizations or groups to collectively train a shared global model without the need to expose raw data externally. Federated learning has garnered increasing attention due to its applicability across a wide range of settings where data is collected and analyzed across disparate locations. This includes scenarios like medical data dispersed among different hospitals, financial customer data stored across various branches or databases, and the utilization of federated learning within user networks in modern technologies such as smartphones or self-driving cars. See, for example, [1]–[5]. In such contexts, privacy concerns often impede direct data pooling, making the development of efficient statistical inference methods that preserve privacy and harness the collective power of distributed data essential.

In this paper, we investigate federated nonparametric goodness-of-fit testing under distributed differential privacy (DP) constraints. Nonparametric hypothesis testing, a fundamental statistical problem, has been extensively studied in conventional settings, with a rich body of classical literature examining theoretically optimal performance. DP, introduced by Dwork et al. (2006), serves as a mathematical guarantee determining whether results or datasets can be deemed “privacy-preserving" and thus openly published. Many differentially private statistical methods have since been developed. See, for example, [6]–[8]. While several other privacy frameworks exist, DP holds a prominent position both theoretically and practically, finding application within industry giants like Google [9], Microsoft [10], Apple [11], as well as governmental entities such as the US Census Bureau [12].

DP may significantly impact the quality of statistical inference, particularly in testing problems where it may diminish statistical power that could be obtained with complete data availability. In the present paper, we quantify the cost of privacy in the canonical nonparametric goodness-of-fit testing setting, delineating the theoretical limits of performance achievable under DP constraints and developing methods that attain optimal performance. Contrasting our results with those derived for federated nonparametric estimation under DP [13], we observe that the differences persist and are exacerbated under privacy constraints, highlighting the unique challenges posed by privacy preservation in both testing and estimation contexts.

We first establish the minimax separation rate for the nonparametric goodness-of-fit testing problem and construct optimal tests in the oracle setting where the regularity parameters are known. The minimax separation rate serves as a benchmark for the difficulty of the testing problem. However, the regularity parameters are typically in applications. A natural question is: Without the knowledge of the regularity parameters, is it possible to construct a test that is as good as when the parameters are known? This is a question about adaptation, which has been a major goal in nonparametric statistics. We construct a data-driven test and show that the proposed method can adapt to unknown regularity parameters with minimal additional cost while adhering the same DP restrictions.

1.1 Federated privacy-constrained testing↩︎

We begin by formally introducing the general framework of federated inference under distributed DP constraints. Consider a family of probability measures \(\{P_f\}_{f \in \cF}\) on the measurable space \((\mathcal{X},\mathscr{X})\), parameterized by \(f \in \cF\). We consider a setting where \(N = mn\) i.i.d. observations are drawn from a distribution \(P_f\) and distributed across \(m\) servers. Each server \(j=1,\dots,m\) holding an equal amount (\(n\) many) observations.

Let us denote by \(X^{(j)} = (X^{(j)}_i)_{i=1}^{n}\) the \(n\) realizations from \(P_f\) on the \(j\)-th server. Based on \(X^{(j)}\), each server outputs a (randomized) transcript \(Y^{(j)}\) to the central server that satisfies the privacy constraint. The central server, utilizing all transcripts \(Y :=(Y^{(1)}, \dots,Y^{(m)})\), decides between a null hypothesis and an alternative hypothesis, through means of a test \(T=T(Y)\). Since we are concerned with testing between a null and alternative hypothesis, we shall consider the decision space \(\{0,1\}\), where \(0\) corresponds to \(\mathrm{\small do not reject}\) and \(1\) with \(\mathrm{\small reject}\). A test is then simply to be understood as a statistic taking values in \(\{0,1\}\). Figure 1 gives an illustration of a federated \((\epsilon,\delta)\)-DP-constrained testing procedure.

The transcript \(Y^{(j)}\) satisfies an \((\epsilon,\delta)\)-DP constraint, which, loosely speaking, means that the transcript \(Y^{(j)}\) cannot differ too much depending on whether a specific individual is in the data set or not. This is achieved through randomization, which is independent of the data. We will consider two types of sources for randomization; independently among the servers or through a shared source of randomness \(U\) (e.g., the same random seed). Formally, shared source of randomness means that the law of the transcript is given by a distribution conditionally on \(X^{(j)}\) and \(U\), \(A \mapsto \P( Y^{(j)} \in A | X^{(j)},U)\), defined on a measurable space \((\cY, \mathscr{Y})\). The presence of shared randomness is a slight, but important extension of the distributed protocols where \(Y^{(j)}\) is allowed to be random only through locally generated randomness. See further discussion below and in Section 2. To assure that the source of shared randomness does not erode the notion of privacy, only the local source of randomness is used in the privacy mechanism, i.e. to guarantee privacy. We formalize this as follows.

We shall call two data sets \(x,x' \in \mathcal{X}^{n}\) neighboring if they differ in one individual datum. That is, they are at most one apart in Hamming distance (see Section 1.6). A DP constraint is then defined as follows.

The above setting is concerned with distributed protocols for scenarios where multiple parties hold sensitive data and each publishes a differentially private summary, without sharing raw data between them. This approach is common in cases like separate studies by different hospitals on the same population, where privacy concerns prevent direct data pooling. We note that, in the above definition, the outcome of the shared source of randomness \(U\) does not diminish the privacy guarantee, even when it is publicly available. This is because the shared randomness is not used in the privacy mechanism, but as a means to enhance coordination between the transcripts, which allows the transcripts to be more informative about the underlying signal whilst each transcript is effectively sharing less information about their underlying individual data.

Formally, having access to shared randomness means that \(U\) can be defined on some probability space \((\cU,\mathscr{U}, \P^U)\), such that \(U\) is independent of the data (i.e. by taking the appropriate product space for \(\P^{X,U}\)). Having no access to shared randomness effectively corresponds to considering \(U\) to be a degenerate random variable, or \(\mathscr{U} = \{ \emptyset, \cU \}\). In order to stream line the notation between these two setups, we shall refer to the triplet \(( T, \{\left(\P^{Y^{(j)}|X^{(j)} = x, U=u}\right)_{x \in \cX^n, u \in \cU} \}_{j=1}^m, (\cU, \mathscr{U}, \P^U))\) as a \((\epsilon,\delta)\)-DP shared randomness distributed testing protocol with \(\{\left(\P^{Y^{(j)}|X^{(j)} = x,U=u}\right)_{x \in \cX^n, u \in \cU} \}_{j=1}^m\) satisfying Definition 1 for general \(U\) (i.e. general \((\cU, \mathscr{U}, \P^U)\)). The class of such triplets, but with \(\mathscr{U} = \{ \emptyset, \cU \}\), shall be referred to as **\((\epsilon,\delta)\)-DP local randomness distributed testing protocols. We shall denote these classes as \(\mathscr{T}^{(\epsilon,\delta)}_{\texttt{SHR}}\) and \(\mathscr{T}^{(\epsilon,\delta)}_{\texttt{LR}}\), respectively, and note that the former is a superset of the latter.

1.2 Problem formulation↩︎

The white-noise-with-drift model serves as a benchmark model for nonparametric testing and has been extensively studied outside of the DP setting, see [14]–[18]. Furthermore, the problem bares a close relationship with “classical” nonparametric goodness-of-fit testing in the sense of [19]–[22] and other nonparametric testing problems through asymptotic equivalence, see Section 1.4 in [23] and references therein.

In the distributed setting, the \(j=1,\dots,m\) machines each observe \(i=1,\dots,n\) i.i.d, \(X^{(j)}_i\) taking values in \(\cX \subset L_2[0,1]\) and subject to the stochastic differential equation \[\label{eq:snwn95function95model95dynamics} dX^{(j)}_{t;i} = f(t)dt + \sigma dW_{t;i}^{(j)}\tag{2}\] under \(P_f\), with \(t \mapsto W^{(1)}_{t;i},\dots,t \mapsto W^{(m)}_{t;i}\) i.i.d. Brownian motions and \(f \in L_2[0,1]\) for \(i=1,\dots,n\), with \(\sigma > 0\) the known noise level for each observation. For notational convenience, we shall use \(N=mn\) throughout the paper and will consider asymptotic regimes where \(N \to \infty\). We note that, when \(m=1\), we recover the classical white-noise-with-drift model.

We consider the canonical signal detection problem, where the goal is to test for the presence or absence of the “signal component” \(f\). More formally, we consider testing the null hypothesis \(H_0: f \equiv 0\) against the alternative hypotheses that \[\label{eq:alternative95hypothesis} f \in H_{\rho}^{s,R} \equiv H_{\rho}^{s,R,p,q} := \left\{ f \in \cB^{{s},R}_{p,q} : \|f\|_{L_2} \geq \rho \text{ and } \| f\|_{\cB^{s}_{p,q}} \leq R \right\}.\tag{3}\] Here, the alternative hypothesis consists of \({s}\)-smooth functions in a Besov space, with \(\|\cdot\|_{\cB^{s}_{p,q}}\) denoting the Besov-\(({s},p,q)\)-norm and \(\cB^{{s},R}_{p,q} \subset L_2[0,1]\) corresponds to the Besov ball of radius \(R\), see Section 11 in the Supplementary Material [24] for the definitions. Besov spaces are a very rich class of function spaces. They include many traditional smoothness spaces such as Hölder and Sobolev spaces as special cases. We refer the reader to [25] for a detailed discussion on Besov spaces.

Using a wavelet transform, the above testing problem is equivalent the observations under the Gaussian sequence model, where each of the \(j=1,\dots,m\) machines observes \(i=1,\dots,n\) observations \(X^{(j)}_i := (X_{lk;i}^{(j)})_{l \geq 1,k=1,\dots,2^l}\) \[\label{eq:sequence95model} X_{lk;i}^{(j)} = f_{lk} + \sigma Z_{lk;i}^{(j)},\tag{4}\] where the \(Z_{lk;i}^{(j)}\)’s are i.i.d. standard Gaussian. The equivalent hypotheses 3 in the sequence model simply follows by replacing the \(L_2[0,1]\)-norm with the \(\ell_2(\N)\)-norm and the Besov space \(\cB^{{s},R}_{p,q}\) set to \(\{ f \in \ell_2(\N) : \| f\|_{\cB^{s}_{p,q}} < \infty \}\), where the Besov norm on the sequence space \(\ell_2(\N)\) is defined as \[\label{eq:besov95norm} \| f\|_{\cB^{s}_{p,q}} := \begin{cases} \left( \underset{l=1}{\overset{\infty}{\sum}} \left(2^{l({s}+1/2-1/p)} \left\| (f_{lk})_{k=1}^{2^l} \right\|_p\right)^{q}\right)^{1/q} &\text{ for } 1 \leq q < \infty, \\ \; \underset{l\geq 1}{\sup} \; 2^{l({s}+1/2-1/p)} \left\| (f_{lk})_{k=1}^{2^l} \right\|_p &\text{ for } q = \infty. \end{cases}\tag{5}\] In other words, the results for testing under DP derived for the sequence model of 4 with hypothesis 3 apply to the model described by 2 also, with the same corresponding hypothesis.

Given a \(\{0,1\}\) valued test \(T\), where \(T(Y) = 1\) corresponds to rejecting the null hypothesis, we define the testing risk sum of the type I and worst case type II error over the alternative class; \[\cR( H_{\rho}^{s,R} , T) = \P_{0} T(Y) + \underset{{f} \in H_{\rho}^{{s},R}}{\sup} \, \P_f T(Y).\] For the range of values \(2 \leq p \leq \infty\), \(1 \leq q \leq \infty\), the minimax separation rate in the unconstrained case is known to be \(\rho \asymp {(\sigma^2/N)}^{\frac{{s}}{2{s} + 1/2}}\) (see e.g. [15]). This means that, for \(\rho \gg {(\sigma^2/N)}^{\frac{{s}}{2{s} + 1/2}}\), there exists a sequence of consistent tests \(T \equiv T_N\) such that \(\cR( H_{\rho}^{s,R} , T) \to 0\), whilst no such sequence of tests exists whenever \(\rho \ll {(\sigma^2/N)}^{\frac{{s}}{2{s} + 1/2}}\).

The minimax separation rate captures how the testing problem becomes easier, or more difficult, for different model characteristics. For distributed \((\epsilon,\delta)\)-DP testing protocols, the minimax separation rate depends on the stringency of the privacy requirement, given by \(\epsilon,\delta > 0\), as well as the model characteristics \(m,n,s\) and \(\sigma\). That is, we aim to find \(\rho\) as a function of \(m,n,s,\sigma,\epsilon,\delta\), such that \(\underset{T \in \mathscr{T}^{(\epsilon,\delta)}}{\inf} \cR( H_{\rho',R}^{s,p,q} , T)\) converges to either \(0\) or \(1\) depending on whether \(\rho' \ll \rho\) or \(\rho' \gg \rho\). The class of alternatives under consideration are subsets of the Besov ball \(\cB^{{s},R}_{p,q}\), where \(2 \leq p < \infty\), \(1 \leq q \leq \infty\), which offers a framework for functions in 2 with specific smoothness characteristics. Our results extend easily to the case where \(p = \infty\) at the cost of an additional logarithmic factor in the rate and a few additional technicalities in the proofs.

1.3 Main results and our contribution↩︎

We quantify the difficulty of the federated testing problem outlined in the previous section in terms of the minimax separation rate. To achieve this, we present constructive distributed \((\epsilon,\delta)\)-DP testing protocols that achieve consistent testing for the problem described above for certain values of \(\rho\) (Theorem 4 in Section 3). Additionally, we establish matching minimax lower bounds, up to logarithmic factor, for the testing risk (Theorem 5 in Section 5), providing a lower bound on the performance of distributed \((\epsilon,\delta)\)-DP testing protocols.

Our analysis uncovers several novel and intriguing findings, which we briefly highlight here. The performance guarantees for the methods demonstrated in Section 3, along with the lower bounds established in Section 5, indicate that the distributed \((\epsilon,\delta)\)-DP testing problem for the hypotheses given in 3 is governed by the minimax separation rate (up to logarithmic factors)

\[\label{eq:shared95randomness95rate95single95line} \rho^2 \asymp \left(\frac{\sigma^2}{mn}\right)^{\frac{2{s}}{2{s}+1/2}} + \left(\frac{\sigma^2}{m n^{3/2} \epsilon \sqrt{1 \wedge n \epsilon^2} } \right)^{\frac{2{s}}{2{s}+1}} \wedge \left( \left(\frac{\sigma^2}{\sqrt{m} n^{} \sqrt{1 \wedge n \epsilon^2}} \right)^{\frac{2{s}}{2{s}+1/2}} + \frac{\sigma^2}{mn^2 \epsilon^2} \right).\tag{6}\]

The precise statement is deferred to Theorem 1.

The derived rate indicates that the distributed testing problem under privacy constraints undergoes multiple phase transitions, resulting in different regimes where \(\epsilon\) affects the detection boundary differently. Specifically, a smaller \(\epsilon\), which implies a stronger privacy guarantee, leads to an increased detection threshold. When \(\delta\) decreases polynomially with \(N\), its impact on the detection boundary is limited to a logarithmic factor, making its effect on the error rate minor compared to that of \(\epsilon\).

For \(m=1\), our theorems establish the optimal separation rate for nonparametric goodness-of-fit testing in the central DP setting, where all data is available on a single machine. When \(\epsilon \lesssim 1/\sqrt{N}\), the privacy constraint affects the rate polynomially. In contrast, for \(\epsilon \gtrsim 1/\sqrt{N}\), the rate approximates the classical minimax rate, up to logarithmic factors. Thus, the privacy constraint significantly impacts the rate only when \(\epsilon\) is relatively small compared to the total number of observations \(N\).

When \(n=1\), we establish the optimal separation rate for the testing problem in the local DP setting. Here, \(\epsilon\) can be seen to have a pronounced effect on the rate whenever \(\epsilon \lesssim 1\).

In the general federated setting, with \(m \gg 1\), we see that \(m\) and \(n\) come into play with different powers in the minimax rate whenever \(\epsilon^2 \lesssim \sigma^{\frac{1}{2s+1}} m^{\frac{1}{4s+1}} n^{\frac{1/2-2s}{4s+1}}\). This means that if one distributes \(N=mn\) observations across \(m\) machines, the task becomes more challenging as the \(N\) observations are spread over a greater number of machines, rather than having many observations on a smaller number of machines. This phenomenon is also observed in the comparable estimation setting of nonparametric regression, as recently investigated in [13]. The phase transitions, however, are not observed in its estimation counterpart. We provide a detailed interpretation of the phase transitions in Section 2.

Our analysis also reveals that the minimax rate obtained in Theorem 1 becomes worse without access to shared randomness. This is revealed by Theorem 1 in Section 2. For certain values of \(\epsilon\), we show that the performance is strictly worse for methods that use only local randomness, and we exhibit optimal local and shared randomness methods for these regimes, respectively, in Sections 3.2 and 3.3. The shared source of randomness does not reveal any information on the identity of the individuals comprising the sample, even when it is publicly available. This means that the shared randomness does not violate the privacy constraints, and the improvement in the rate is a direct result of the shared randomness. We comment on this further in Section 2.

In many practical applications, the regularity parameter \(s\) is unknown. In Section 4, we extend the methods of Section 3 that attain the minimax rates, up to additional logarithmic factors, when the regularity is unknown. That is, establish that adaptive testing is possible under DP constraints with minimal additional cost in terms of the separation rate.

The lower bound relies on several technical innovations, which are summarized in Section 5. There, we provide a sketch of the proof and highlight the key innovations. The optimal methods proposed in this paper rely on carefully tailored private test statistics that extend to the adaptive setting with minimal cost due to exponential concentration bounds. We describe the construction of these tests in Sections 3 and 4.

1.4 Related Work↩︎

The literature on the theoretical properties of DP can be mostly divided into those studying local DP or central DP. In local DP, the privacy protection is applied at the level of individual data entries or observations, which corresponds to \(n=1\) in our setting. This is a stringent form of DP because each item of data is independently given privacy protection. In the other extreme, central DP, only the inference output needs to satisfy the DP constraint (i.e. \(m=1\) in our setting), meaning that if the output is a test, only the final decision needs to satisfy a DP constraint.

Locally differential private estimation has been studied in the context of the many-normal-means model, discrete distributions and parametric models in [26]–[29]. The problem of density estimation under local DP constraints has been considered by [27], [30]–[32], of which the latter three works consider adaptation. In the context of hypothesis testing, [33]–[39] study testing under local DP for discrete distributions. Nonparametric goodness-of-fit testing under local DP is considered in [40], [41], where in [41], the authors consider adaptation as well. In [42], the authors consider estimation of a quadratic functional under local differential privacy constraints, which has connections to goodness-of-fit testing. Settings in which the full data is assumed to be on a single server (i.e. \(m=1\)), where a single privacy constraint applies to all the observations, have also been studied for various parametric high-dimensional problems [43]–[51]. In [52], nonparametric density estimation with known smoothness is considered. When it comes to hypothesis testing under central DP, [53] study simple hypothesis testing. [54] considers uniformity and independence testing in the multinomial model and [55], [56] study signal detection in the many-normal-means model. In [57], hypothesis testing in a linear regression setting is considered.

Investigations into the more general federated setting have been much more limited, with estimation being considered in [58], [59], which study estimation for discrete distributions and [60], [61] which study mean estimation, [13] which study nonparametric regression, and [62] which consider sparse linear regression. In the paper [63], the authors consider discrete distribution testing in a two server setting (\(m=2\)) with differing DP constraints.

1.5 Organization of the paper↩︎

The rest of the paper is organized as follows. In Section 2, we present the main results of the paper, for the known smoothness case and the adaptive setting. Next, Section 3 presents the methods that achieve the optimal rates derived in Section 2. In Section 4, we extend these methods to be adaptive in the case that the smoothness is unknown. In Section 5, we present the lower bound theorems for the testing problem and give a sketch of its proof. Further proofs are deferred to the supplemental material to the article, [24].

1.6 Notation, definitions and assumptions↩︎

Throughout the paper, we shall write \(N := mn\). For two positive sequences \(a_k\), \(b_k\) we write \(a_k\lesssim b_k\) if the inequality \(a_k \leq Cb_k\) holds for some universal positive constant \(C\). Similarly, we write \(a_k\asymp b_k\) if \(a_k\lesssim b_k\) and \(b_k\lesssim a_k\) hold simultaneously and let \(a_k\ll b_k\) denote that \(a_k/b_k = o(1)\).

We use the notations \(a\vee b\) and \(a\wedge b\) for the maximum and minimum, respectively, between \(a\) and \(b\). For \(k \in \N\), \([k]\) shall denote the set \(\{1,\dots,k\}\). Throughout the paper \(c\) and \(C\) denote universal constants whose value can differ from line to line. The Euclidean norm of a vector \(v \in \mathbb{R}^d\) is denoted by \(\|v\|_2\). For a matrix \(M \in \R^{d \times d}\), the norm \(M \mapsto \| M \|\) is the spectral norm and \(\text{Tr}(M)\) is its trace. Furthermore, we let \(I_d\) denote the \(d \times d\) identity matrix.

Throughout the paper, \(\mathrm{d}_H\) is the Hamming distance on \(\cX^n\) is defined as \(\mathrm{d}_H(x,\breve{x}) := \sum_{i=1}^n \text{\usefont{U}{bbm}{m}{n}1}\left\{ x_i \neq \breve{x}_i \right\}\) for \(x = (x_i)_{i =1}^n, \breve{x} = (\breve{x}_i)_{i =1}^n \in \cX^n\). Furthermore, for a vector space \(\cX\) and \(x = (x_i)_{i \in [n]}\in \cX^n\), we shall write \(\overline{x}\) for the average \(n^{-1} \sum^n_{i=1} x_i\).

2 Minimax optimal testing rates under privacy constraints↩︎

In this section, we discuss the main results in detail. We start the discussion with results for the oracle case where the regularity parameter is known in Section 2.1. Section 2.2 describes the main results for when the regularity is not known.

2.1 Description of the minimax separation rate↩︎

We first give a precise statement concerning the minimax separation rate shown in 6 .

The proof of the theorem is given in Section 8.4 of the Supplementary Material [24]. It is based on a combination of upper and lower bounds, where the lower bound is established in Section 5. The upper bound is given in Section 3, where we present an \((\epsilon,\delta)\)-DP distributed testing protocol that attains the rate in Theorem 1. These upper and lower bounds are in fact non-asymptotic, meaning that they do not require the assumption that \(N \to \infty\).

Theorem 1 shows multiple regime changes, where the distributed testing problem under privacy constraints undergoes a change in the minimax separation rate. Later on in this section, we highlight the different regimes and give an interpretation to each of them.

Theorem 1 considers the minimax rate for the class of distributed protocols with access to shared randomness, \(\mathscr{T}^{(\epsilon,\delta)}_{\texttt{SHR}}\). Theorem 2 below considers the minimax rate for the (strictly smaller) class of distributed protocols without access to shared randomness, \(\mathscr{T}^{(\epsilon,\delta)}_{\texttt{LR}}\). Here, transcripts depend only on their local data and possibly a local source of randomness.

The proof of Theorem 1 is given in Section 8.4 of the supplemental material [24]. The theorem shows that, depending on the value of \(\epsilon\), the minimax rate for protocols that do not have access to shared randomness is strictly worse than those for protocols that do have access to shared randomness.

To more easily compare the two theorems, we provide a table in Table 1 below, where we separate six “regimes” to aid interpretability below. Each of the regimes correspond to the dominating term in the minimax separation rates of Theorems 1 and 2. Which term dominates depends on the value of \(\epsilon\), in comparison to \(n,m,\sigma\), \(s\) and the availability of shared randomness.

The rates in Regimes 4, 5 and 6 are the same for both types of protocols, and these rates are attained by the same testing protocol for each of the classes, which does not require shared randomness. We shall refer to Regime 4, 5 and 6 as the “low privacy-budget” regimes, as these rates occur for relatively small values of \(\epsilon\).

We shall refer to Regimes 1, 2 and 3 as the “high privacy-budget” regimes, as these rates occur for relatively large values of \(\epsilon\). These rates are achieved by a different protocol, for the classes of protocols with and without shared randomness, respectively. These protocols are given in Sections 3.2 and 3.3. Proving the tighter lower bound in case of the class of protocols with access to local randomness only, requires a different technique to that of the class of shared randomness protocols, which we outline in Section 5.

The improvement in the rate for the shared randomness protocols, compared to the local randomness protocols, are visible for Regime 2 and Regime 3, but also the values of \(\epsilon\) for which the different regimes occur are different for the two types of protocols. The improvement in the rate is loosely speaking a consequence of the improved coordination between the servers made possible by shared randomization. We exhibit a distributed \((\epsilon,\delta)\)-DP shared randomness protocol attaining the above rate in Section 3.3.

In case of access to shared randomness, the high privacy-budget regime occurs whenever \(\epsilon \gtrsim \sigma^{-\frac{2}{4s+1}} m^{-\frac{2{s}}{4{s}+1}} n^{\frac{1/2-2{s}}{4{s}+1}}\) and \(\epsilon \geq n^{-1/2}\), or \(\sigma^{-\frac{1}{2s}} m^{-\frac{1}{2}} n^{\frac{1-2{s}}{4{s}}} \leq \epsilon < n^{-1/2}\). In the case of local randomness only, the high privacy-budget regimes occur for larger values of \(\epsilon\), namely \(\epsilon \gtrsim \sigma^{-\frac{2}{4s+1}} m^{\frac{1}{4s+1}} n^{\frac{1/2-2s}{4s+1}}\) if \(\epsilon \geq n^{-1/2}\) or \(\epsilon \gtrsim \sigma^{-\frac{4}{4s-1}} m^{-\frac{1}{2}} n^{\frac{5/2-2s}{4s-1}}\) for \(\epsilon \lesssim n^{-1/2}\), whenever \(s > 1/4\). When \(s \leq 1/4\) and no shared randomness is available, we are always in the low privacy-budget regime for the range of \(N^{-1} \lesssim \sigma \lesssim 1\) and \(N^{-1} < \epsilon \lesssim 1\) considered.

The testing protocols that attains the rate in the high privacy-budget regimes are given in Section 3.2 and 3.3. These protocols bear some resemblance with the estimation strategy in [13], where transcripts constitute noisy, lower dimensional approximations of the original data. As \(\epsilon\) increases, the dimensionality of these approximations increases and the rate improves. In Regime 2 and 3, the minimax rate is at least a polynomial factor of \(\epsilon\) larger than the unconstrained, non-private minimax separation rate, which is attained in Regime 1 (up to a logarithmic factor). The observation that shared randomness can improve performance in our problem has been noted in other contexts involving distributed privacy and communication constraints, see for example [38], [39], [64]–[66]. [40], [42] studies interactive versus non-interactive protocols and finds a difference in terms of minimax performance between the two in the local differential privacy setting. Interestingly, when \(n=1\) (i.e. in the local differential privacy setting), we find the similar minimax rates for nonparametric goodness-of-fit testing in the high privacy-budget regimes, for the shared randomness and local randomness protocols, as they do for interactive and non-interactive protocols, whenever \(\epsilon\) is in the high-budget regime. Although they study a different model, observations from smooth densities; it is interesting to see that the same rates seem to be attainable without sequential interaction, by using shared randomness instead. We note here that, when sequential- or interactive protocols are allowed, shared randomness can be employed in particular. In real applications without interaction, one should always use shared randomness if at all possible.

In the low privacy-budget case, i.e. Regimes 4, 5 and 6, the minimax rate for both local and shared randomness protocols coincides. We note that the regimes occur at different values of \(\epsilon\) for the two types of protocols, however. Within the low privacy-budget range, we find essentially three different regimes. When \(n^{-1/2} \leq \epsilon < \sigma^{-\frac{2}{4s-1}} m^{\frac{1/4-s}{4s+1}} n^{\frac{1/2-2s}{4s+1}}\), the rate is given by \((\frac{\sigma^2}{\sqrt{m} n^{}} )^{\frac{2{s}}{2{s}+1/2}}\). What is remarkable here, is that whilst the rate is polynomially worse in \(m\) than the unconstraint rate, the rate is otherwise independent of \(\epsilon\). This regime essentially corresponds to a setting where, even though a high privacy-budget strategy is not feasible, the desired level of privacy is achieved “for free" with the locally optimal test statistic.

We exhibit an \((\epsilon,\delta)\)-DP distributed testing protocol that attains this rate in Section 3.1. This strategy can roughly be described as first computing a locally optimal private test statistic – a test statistic that would result in the optimal private test using just the local data – and then averaging these private test statistics; essentially combining the power of the local tests. That this strategy performs well when the privacy constraint is sufficiently stringent can intuitively be explained as that it is easier to retain privacy when only (a private version of) a single real valued local test statistic is shared, rather than a (private approximation of) the original data.

When \(\epsilon \lesssim n^{-1/2}\) within the low privacy-budget range, \(\epsilon\) affects the rate polynomially. For the smallest values of \(\epsilon\), i.e. \(\epsilon \lesssim \sigma^{\frac{1}{2s+1}} m^{-\frac{1}{2}} n^{-\frac{1+s}{2s+1}}\), the rate is given by \(\frac{\sigma^2}{mn^2 \epsilon^2}\). Strikingly, the regularity parameter does not appear in the rate in this regime. This phenomenon has the following explanation: for such small values of \(\epsilon\), signals of size \(\frac{\sigma^2}{mn^2 \epsilon^2}\) are of larger order than the local estimation rate of \((\frac{\sigma^2}{n})^{\frac{2{s}}{2{s}+1/2}}\). Consequently, signal can locally be estimated with high accuracy, and the bottleneck is purely the privacy constraint, not the high-dimensional nature of the problem.

In the case of central DP (i.e. \(m=1\)), only the low privacy-budget regime is observed. In this case, our results show that the non-private rate is attainable (up to logarithmic factors) for \(\epsilon \gtrsim 1/ \sqrt{N}\). This is in contrast to the local DP setting, where both the high- and low privacy budget regimes are observed (depending on the values of \(\sigma\) and \(s\)). Whenever \(m\) is larger than say polynomial in \(N\) in the low privacy-budget range, (i.e. \(m \asymp N^\omega\) for some \(\omega > 0\)) the unconstrained minimax rate cannot be reached.

To further illustrate the difference between these classes of protocols, we provide two plots in Figure 2. The plots show the relationship between the minimax testing rate \(\rho\) and \(\epsilon\) for fixed values of \(m,n,\sigma\) and four different choices for the regularity \(s\). The regimes correspond to the six regimes in Table 1. The plots show that the shared randomness setting strictly improves the rate for certain values of \(\epsilon\), and that the values of \(\epsilon\) for which the different regimes occur are different for the two types of protocols. A full case-wise breakdown of when each of the regimes occur is given in Section 9 of the Supplementary Material [24]. Below, we give an interpretation for each of the regimes.

What constitute “moderate” or “large” values, depends on the size of \(m\) relative to \(n\), as can be seen when comparing Figure 2, which compares \(N=30\) observations distributed either between \(m=15\) servers with \(2\) observations each, and \(m=5\) servers with \(n=6\) observations each. It can be seen that, as the local sample \(n\) is larger compared to the number of times the total number of data points \(N\) is divided \(m\), the cost of privacy is less. This underlines the idea that, in large samples, it is easier to retain privacy.

When \(\epsilon\) becomes “very small” (smaller than a threshold depending on \(s\), \(m\) and \(n\)), the smoothness starts to matter less and less, up to the point where the difficulty of the problem is no different for (very) different regularity levels. These scenarios correspond to settings where the privacy requirement underlying the problem is so stringent, that it effectively becomes the bottleneck of the testing problem.

2.2 Adaptation↩︎

In the previous section, we derived the minimax separation rate for the nonparametric distributed testing problem. However, the proposed tests constructed in Section 3 require knowledge of the regularity parameter \(s\) of the underlying \(f\). Typically, the regularity of the function is unknown in practice, necessitating the use of data-driven methods to find the best adaptive testing strategies.

Given that the regularity of the underlying signal class is unknown, it makes sense to consider the minimax testing risk \[\underset{s \in [s_{\min} , s_{\max}]}{\sup} \cR \left( H^{s,R}_{ M_{N,s} \rho_s}, T \right),\] for certain predetermined values \(0 < s_{\min} < s_{\max} < \infty\). Here, we consider separation rates \(\rho_s\) depending on the underlying smoothness. In the case that the true underlying smoothness is \(s = s_{\min}\), the separation rate is relatively larger than when (for example) \(s = s_{\max}\). In the case that the true smoothness \(s\) is larger than \(s_{\min}\), we would like to attain the smaller of the two rates \(\rho_{s}\).

In the non-privacy constraint setting, adaptation for the above risk can be achieved with only a minor additional cost in the separation rate (a \(\log\log N\) factor). See for example Theorem 2.3 in [17] or Section 7 in [23]. Theorem 3 below shows that also under privacy constraint, the optimal private rate can be attained by a protocol that is adaptive to the regularity parameter \(s\), with minimal additional cost; at most a logarithmic factor.

We construct such adaptive distributed \((\epsilon,\delta)\)-DP testing protocols in Section 4 and their resulting performance proofs the above theorem. The adaptive methods can be seen as extensions of the methods exhibited in Section 3 for when the smoothness is known. The adaptive methods can essentially be seen as a multiple testing extension of the known smoothness methods, testing along a grid of smoothness levels between \(s_{\min}\) and \(s_{\max}\). The strain on the privacy budget stemming from conducting multiple testing procedures is limited, due to the fact that the cardinality of this grid is order \(\log(N)\). The Type I error control is assured by a Bonferroni correction, which leverages the exponential bounds on the Type I error of the individual “known smoothness tests”.

3 Optimal differentially private testing procedures↩︎

In this section, we construct distributed \((\epsilon,\delta)\)-DP testing procedures that attain the minimax separation rates derived in Section 2.

The testing procedures are constructed in three steps. First, in Section 3.1, we construct a distributed \((\epsilon,\delta)\)-DP testing procedure that uses only local randomness and that is optimal in the low privacy-budget regime described in the previous section. We refer to this procedure as \(T_{\text{I}}\). Second, we construct two distributed \((\epsilon,\delta)\)-DP testing procedures that use local randomness and shared randomness, respectively, and that are optimal in their respective high privacy-budget regimes. We refer to these procedures as \(T_{\text{II}}\) and \(T_{\text{III}}\) and describe them in Sections 3.2 and 3.3, respectively.

The testing procedures differ in terms of the testing strategy. In the low privacy-budget case where \(T_{\text{I}}\) is optimal, the testing strategy can be seen to consist of first computing a locally optimal private test statistic in each machine; that is, a test statistic that would result in the optimal private test using just the local data. The locally optimal test statistic is based on the squared Euclidean norm of the truncated observation. To deal with the nonlinearity of the Euclidean norm, the strategy appropriately restricts the domain of the clipped locally optimal test statistic, after which we employ a Lipschitz-extension to obtain a test statistic that is well-defined on the sample space and more robust to outliers than the Euclidean norm itself. The noisy version of this test statistic is locally optimal under privacy constraints, in the sense that a corresponding (strict) p-value test attains the lower bound rate (up to a logarithmic factor) as established by Theorem 2 for the case where \(m=1\). When \(m>1\), the final test statistic is obtained by averaging the locally optimal private test statistics.

In the large \(\epsilon\) regime, instead of computing a locally optimal test statistic, both \(T^{}_{\text{II}}\) and \(T^{}_{\text{III}}\) are based on truncated, clipped and noisy versions of the local observations. The key difference between the two is that the latter uses the same random rotation of the local observations, which is made possible by the availability of shared randomness.

Together, the methods prove Theorem 4 below, which forms the “upper bound” part of the minimax separation rate described by Theorems 2 and 1. Unlike the formulation of the latter theorems, we note that the result is not asymptotic.

The proof of the theorem follows directly from the guarantees proven for each of the three testing protocols; we defer it to Section 8 in the supplement. Before giving the detailed construction of the three tests, we introduce some common notation. Let \(\Pi_L\) denote the projection of elements \(\R^\N\) onto the first \(d_L := \sum_{l = 1}^{L} 2^l\) coordinates, where the elements as ordered and indexed as follows; \[\Pi_L x = \left( x_{11},\dots,x_{12}, x_{21},\dots,x_{14},\dots, x_{L1},\dots,x_{L2^L},0,0,0,\dots\right).\] We shall also use the notation \(d_L := \sum_{l=1}^L 2^l\) and let \(X^{(j)}_{L;i}\) denote vector in \(\R^{d_L}\) formed by the first \(d_L\) coordinates of \(\Pi_L X^{(j)}_{i}\) and let \(X^{(j)}_L = (X^{(j)}_{L;i})_{i \in [n]}\). Furthermore, we recall that for \(v = (v_1,\dots,v_n) \in \cX^n\) for a vector space \(\cX\), \(\bar{v}\) denotes the vector space average \(n^{-1} \sum_{i=1}^n v_i\).

In order to obtain statistics with (uniformly) bounded sensitivity it is useful to bound quantities between certain thresholds. Formally, for \(a,b,x \in \R\) with \(a<b\), let \([ x ]_a^b\) denote \(x\) clipped between \(a\) and \(b\), that is \[\label{eq:def95clipping} [ x ]_{a}^b := \begin{cases} b \; \text{ if } x > b, \\ x \; \text{ if } a \leq x \leq b \\ a \; \text{ otherwise.} \end{cases}\tag{10}\] The distributed privacy protocols under consideration in this paper can be seen as noisy versions of statistics of the data. Roughly put, the “amount” of noise added depends on the sensitivity of the statistics. This brings us to the concept of sensitivity. Formally, consider a metric \(\mathrm{d}\) on a set \(\cY\). Given \(n\) elements \(x=(x_1,\dots,x_n)\) in a sample space \(\cX\), the \(\mathrm{d}\)-sensitivity at \(x\) of a map \(S: \cX^n \to \cY\) is \[\Delta_S(x) := \underset{\breve{x} \in \cX^n : \mathrm{d}_H(x,\breve{x}) \leq 1}{\sup} \mathrm{d} \left( S(x), S(\breve{x})\right),\] where \(\mathrm{d}_H\) is the Hamming distance on \(\cX^n\) (see Section 1.6 for a definition). The \(\mathrm{d}\)-sensitivity of \(S\) is defined as \(\Delta_S := \sup_x \Delta_S(x)\). In this paper, the main noise mechanism is the Gaussian mechanism. The Gaussian mechanism yields \((\epsilon,\delta)\)-differentially private transcripts for statistics that have bounded \(L_2\)-sensitivity, with the noise variance scaling with the \(L_2\)-sensitivity. See [67] for a thorough treatment. We remark that for the rates in Regime 3 up until 6 in Table 1, \((\epsilon,0)\)-DP can be attained by employing a Laplace mechanism instead. That is, for the values of \(\epsilon\) for which Regime 3 up until 6 in Table 1 are optimal, the test statistics in the sections have matching \(L_1\)- and \(L_2\)-sensitivity, so the Gaussian mechanism can be replaced by the Laplace mechanism instead in these regimes.

3.1 Private testing procedure I: low privacy-budget strategy↩︎

In the classical setting without privacy constraints (and \(m=1\)), a rate optimal test for the hypotheses of 3 is given by \[\label{eq:classically95optimal95test} \text{\usefont{U}{bbm}{m}{n}1}\left\{ S^{(j)}_{L_{{}}} > \kappa_{\alpha} \right\}, \text{ where } S^{(j)}_{L_{{}}} := \frac{1}{\sqrt{ d_{L_{}}}} \left( \left\| \sigma^{-1} \sqrt{n} \overline{X^{(j)}_{L_{}}} \right\|_2^2 - d_{L_{}} \right),\tag{11}\] where \(d_{L_{}} := \sum_{l=1}^{L_{}} 2^l\) and the rate optimal choice of \(L\) is \(L_{*} = \left \lceil \frac{1}{2s + 1/2} \log_2 (N) \right \rceil\). Under the null hypothesis, \(S^{(j)}_{L_{*}}\) is Chi-square distributed degrees of freedom. Under the alternative hypothesis, the test statistic picks up a positive “bias” as \(\| \sigma^{-1} \sqrt{n} \overline{X^{(j)}_{L_{*}}} \|^2 \sim \chi^2_{L_{*}}(\|\Pi_{L_{*}} f\|_2^2)\) under \(\P_f\), which could surpass the critical value \(\kappa_\alpha\) if \(\sigma^{-2} n \|\Pi_{L_{*}} f\|_2^2\) is large enough. Consequently, the level of the test is controlled by setting \(\kappa_{\alpha}\) appropriately large. For a proof of its rate optimality, see e.g. [68].

As is commonly the case for superlinear functions, the test statistic \(S_{L;\tau}^{(j)}\) has poor sensitivity uniformly over the sample space, meaning that a change in just one datum can result in a large change in the test statistic. This means that it forms a poor candidate to base a privacy preserving transcript on. For example, one would need to add a substantial amount of noise guarantee DP for the statistic. To remedy this, we follow a similar strategy as proposed in [55] and improved upon by [56]. We construct a clipped and symmetrized version of the test statistic above, which has small sensitivity on a set \(\cC_{L;\tau}\), in which \(X^{(j)}\) takes values with high probability. We define the test statistic explicitly on \(\cC_{L;\tau}\) only. By a version of the McShane–Whitney–Extension Theorem, we obtain a test statistic with the same sensitivity that is defined on the entire sample space.

Consider for \(\tau > 0\), \(L \in \N\), \(d_L := \sum^L_{l=1} 2^l\) and \(V^{(j)}_{L;\tau} \sim \chi^2_{d_L}\) independent of \(X^{(j)}\) the random map from \((\R^{d_L})^n\) to \(\R\) defined by \[\label{eq:clipped95Lips95stat95rescaled} \tilde{S}_{L;\tau}^{(j)}(x) = \left[\frac{1}{\sqrt{d_L}} \left(\left\| \sigma^{-1} \sqrt{n} \overline{ x} \right\|^2_2 - {V^{(j)}_{L;\tau}} \right)\right]_{-\tau}^{\tau}.\tag{12}\] For any \(\tau\), this test statistic \(\tilde{S}_{L;\tau}^{(j)}(X^{(j)}_{L})\) can be seen to have mean zero and bounded variance under the null hypothesis, by similar reasoning as for the test statistic in 11 (see the proof of Lemma 1 for details).

Loosely speaking, the test statistic \(\tilde{S}_{L;\tau}^{(j)}(X^{(j)}_L)\) retains the signal as long as \(\tau > 0\) is chosen appropriately in comparison to the signal size (i.e. \(\|\Pi_{L} f\|_2^2\)) and has good sensitivity for “likely” values of \(X^{(j)}\) under \(\P_f\), but not uniformly over the sample space. We make the latter statement precise as follows.

Let \(K_\tau = \lceil 2\tau D^{-1}_\tau \rceil\) and consider the set \(\cC_{L;\tau} = \cA_{L;\tau} \cap \cB_{L;\tau}\), where \[\begin{align} \label{eq:def95C195C2} \cA_{L;\tau} &= \left\{ (x_i) \in (\R^\infty)^n : \bigg|\| \sigma^{-1} \textstyle \sum_{i \in \cJ} \Pi_L x_i \|_2^2 - kd_L \bigg| \leq \frac{1}{8} k D_\tau n \sqrt{d_L} \;\; \forall \cJ \subset [n], |\cJ| = k \leq K_\tau \right\}, \\ \cB_{L;\tau} &= \left\{ (x_i) \in (\R^\infty)^n : \left| \langle \sigma^{-1} \Pi_L x_i, \sigma^{-1} \textstyle \sum_{k \neq i} \Pi_L x_k \rangle \right| \leq \frac{1}{8} k D_\tau n \sqrt{d_L}, \;\; \forall i=1,\dots,n \right\}. \nonumber \end{align}\tag{13}\] Lemma 18 in the supplement shows that \(X^{(j)}\) concentrates on \(\cC_{L;\tau}\) when the underlying signal is, roughly speaking, not too large compared to \(\tau\) (in particular under the null hypothesis).

It can be shown that, on the set \(\cC_{L;\tau}\), \(x \mapsto S^{(j)}(x)\) is \(D_\tau\)-Lipschitz with respect to the Hamming distance, see Lemma 19 in the supplement. Lemma 20 in the supplement shows that there exists a measurable function \({S}_{L;\tau}^{(j)} : (\R^{d_L})^n \to \R\), \(D_\tau\)-Lipschitz with respect to the Hamming distance, such that \({S}_{L;\tau}^{(j)}(X^{(j)}_L) = \tilde{S}_{L;\tau}^{(j)}(X^{(j)}_L)\) whenever \(X^{(j)} \in \cC_{L;\tau}\). Lemma 20 is essentially the construction of McShane [69] for obtaining a Lipschitz extension with respect to the Hamming distance, but our lemma verifies in addition the Borel measurability of the resulting map.

The Lipschitz constant upper bounds the sensitivity of a test statistic that is Lipschitz continuous with respect to the Hamming distance. Specifically, we have that \[\Delta_{S^{(j)}} = \underset{x,\breve{x} \in \ell_2(\N)^n : \mathrm{d}_H(x,\breve{x}) \leq 1}{\sup} \left| S^{(j)}(x) - S^{(j)}(\breve{x})\right| \leq D_\tau.\] Using the Gaussian mechanism, the transcripts \[\label{eq:transcript95private95Euclidean95norm95lips95ext95for95one95clipping} Y^{(j)}_{L;\tau} = \gamma_\tau \breve{S}_{L;\tau}^{(j)}(X^{(j)}_L) + W^{(j)}_\tau, \quad \text{where } W^{(j)}_\tau \sim N(0,1) \text{ independent for } j \in [m],\tag{14}\] \(\gamma_\tau = {\epsilon}/({D_\tau \sqrt{2 \mathfrak{c} \log (2 / \delta)}})\) and \(\tau > 0\), are \((\epsilon/\sqrt{\mathfrak{c}},\delta)\)-differentially private for any \(\epsilon > 0\) (see e.g. [67]). These transcripts are mean zero and have bounded variance under the null hypothesis, so a test of the form \[\label{eq:Lipschitz95ext95test95privacy95for95one95clipping} \varphi_\tau := \text{\usefont{U}{bbm}{m}{n}1} \left\{ \frac{1}{\sqrt{m}} \underset{j=1}{\overset{m}{\sum}} Y^{(j)}_{L;\tau} \geq \kappa (\gamma_\tau \vee 1) \right\}\tag{15}\] has an arbitrarily small level for large enough \(\kappa > 0\) (see Lemma 21 in the supplement). Furthermore, the lemma below shows that, if the signal size is large enough in the \(\sum_{l=1}^{L} 2^l\) first coordinates, the above test enjoys a small Type II error probability as well.

A proof of the above lemma is given in Section 8.1 of the supplement. The above test is calibrated for the detection of signals size between \(\tau/4\) and \(\tau/2\). In order to detect signals of any size larger than the right-hand side of 17 , we follow what is essentially a multiple testing procedure. For large signals, we need a larger clipping to detect them, as well as a larger set \(\cC_{L;\tau}\) to assure that the data is in \(\cC_{L;\tau}\) with high probability, as larger signals increase the probability of “outliers” from the perspective of the sensitivity of the \(L_2\)-norm.

It turns out that a sufficient range of clipping thresholds to consider (for detecting the signals \(f \in \cB^{{s},R}_{p,q}\) under consideration in Lemma 2) is given by \[\label{eq:collection95of95threshold95lips95test} \tau \in \mathrm{T}_L := \left\{ 2^{-k+2} \frac{ n (1-2^{-s})^{2 - 2/q} R^2}{\sigma^{2} \sqrt{2^{L}}} : k=1,\dots,\lceil1+2\log_2( N R / \sigma )\rceil \right\}.\tag{18}\] The \((\epsilon, \delta)\)-differentially private testing procedure \(T_{\text{I}}\) is now constructed as follows. For each \(\tau \in \mathrm{T}_L\), the machine transfers 14 with \(\mathfrak{c} = {|\mathrm{T}_L|}\). By the independence of the Gaussian noise added in 14 for each \(\tau \in \mathrm{T}_L\), the transcript \(Y^{(j)} = \{ Y^{(j)}_{L;\tau} : \tau \in \mathrm{T}_L \}\) is \((\epsilon,\delta)\)-differentially private (see e.g. Theorem A.1 in [67]).

The test \[\label{eq:definition95full95test95lips95ext95privacy} T_{\text{I}} := \text{\usefont{U}{bbm}{m}{n}1} \left\{ \underset{\tau \in \mathrm{T}_L}{\max} \, \frac{1}{\sqrt{m}} \underset{j=1}{\overset{m}{\sum}} Y^{(j)}_{L;\tau} \geq \kappa_\alpha \left( \frac{\epsilon}{D_\tau \sqrt{2 |\mathrm{T}_L| \log (2 / \delta)}} \vee 1 \right) \sqrt{\log |\mathrm{T}_L|} \right\}\tag{19}\] then satisfies \(\P_0 T_{\text{I}} \leq \alpha\) via a union bound and sub-exponential tail bound, we defer the reader to the proof of Lemma 2 for details. Furthermore, for \(f \in \cB^{{s},R}_{p,q}\), we have \(\|\Pi_L f\|_2\leq \|f\|_2 \lesssim R\). If \(f\) in addition satisfies 17 , there exists \(\tau^* \in \mathrm{T}_L\) such that 16 is satisfied and consequently \[\P_f (1 - T_{\text{I}}) \leq \P_f (1 - \varphi_{\tau^*}) \leq \alpha/2.\] The optimal choice of \(L\) depends on the regularity level of the signal \(f\), balancing the approximation error \(\| f - \Pi_L f\|_2^2\) and the right-hand side of 17 , for which we defer the details to Section 8.1 in the supplement. To summarize, we have obtained the following lemma.

3.2 Private testing procedure II: high privacy-budget strategy↩︎

In the high-privacy budget regime, we construct a testing procedure that consists essentially of two steps. In the first step, the data is truncated, clipped and averaged over the coordinates, after which Gaussian noise is added to obtain a private summary of the original data. Then, as a second step, the transcripts are averaged, and based on this average, a test statistic that is reminiscent of a chi-square test is computed in the central server. This is in contrast to the strategy of the previous section, where each server computes a (private version of) a chi-square test statistic.

The approach taken here is to divide the servers equally over the first \(d_L\) coordinates (i.e. as uniformly as possible), where we recall the notation \(d_L := \sum_{l=1}^L 2^l\). That is to say, for \(L,K_L \in \N\), we partition the coordinates \(\{ 1,\ldots,d_L \}\) into approximately \(d_L/K_L\) sets of size \(K_L\). The servers are then equally divided over each of these partitions and communicate the sum of the clipped \(X^{(j)}_{L;i}\)’s coefficients corresponding to their partition, were we also recall that the notation \(X^{(j)}_{L;i}\) denotes the vector in \(\R^{d_L}\) formed by the first \(d_L\) coordinates of \(\Pi_L X^{(j)}_{i}\).

More formally, take \(K_L = \lceil n \epsilon^2 \wedge d_L \rceil\) and consider sets \(\cJ_{lk;L} \subset [m]\) for indexes \((l,k) \in \{ l=1,\dots, L, k = 1,\dots,2^l \} =:I_L\), such that \(| \cJ_{lk;L} | = \lceil \frac{m K_L}{d_L} \rceil\) and each \(j \in \{1,\dots,m\}\) is in \(\cJ_{lk;L}\) for at least \(K_L\) different indexes \(k \in \{1,\dots,d_L\}\). For \((l,k) \in I_L\), \(j \in \cJ_{lk;L}\), generate the transcripts according to \[\label{eq:transcript95impure95DP95coordinate95wise} Y^{(j)}_{lk;L}|X^{(j)} \equiv Y^{(j)}_{lk;L}(X^{(j)}) = \gamma_L \, \sum_{i=1}^n \, [ \sigma^{-1} (X_i^{(j)})_{lk} ]_{-\tau}^\tau + W^{(j)}_{lk}\tag{20}\] with \(\gamma_L = {\epsilon}/({2\sqrt{2 K_L \log(2/\delta)}\tau})\), \(\tau = \tilde{\kappa}_\alpha \sqrt{\log(N/\sigma)}\) and \((W^{(j)}_{lk})_{j \in [m],(l,k) \in I_L}\) i.i.d. standard Gaussian noise.

Since \(x \mapsto \sum^n_{i=1} [ \sigma (x_i^{(j)})_{lk} ]_{-\tau}^\tau\) has sensitivity bounded by \(2 \tau\), for \(k=1,\dots,K\), releasing \[Y^{(j)}_L(X^{(j)})=(Y^{(j)}_{L,l_1 k_1}(X^{(j)}),\dots,Y^{(j)}_{L,l_{K_L}k_{K_L}}(X^{(j)}))\] satisfies \((\epsilon,\delta)\)-DP, see Lemma 23 in the supplement for details.

If the privacy budget were of no concern, submitting the above transcripts with \(2^L \asymp N^{1/(2s+1/2)}\) would be sufficient to construct a test statistic that attains the unconstrained rate of \(\rho^2 \asymp N^{-2s/(2s+1/2)}\). Under (more stringent) privacy constraints, however, the optimal number of coordinates to be transmitted should depend on the privacy budget. Whenever \(\epsilon \lesssim 1/\sqrt{n}\), it turns out that submitting just one coordinate is in fact rate optimal. Sending more than one coordinate leads to worse rates as the noise overpowers the benefit of having a higher dimensional transcript. As \(\epsilon\) increases, the optimal number of coordinates to be transmitted increases as well. Whenever \(\epsilon \gtrsim \sigma^{-\frac{2}{4s+1}} m^{\frac{1}{4s+1}} n^{\frac{1/2-2s}{4s+1}}\), the optimal number of coordinates to be transmitted is \(2^L \asymp N^{1/(2s+1/2)}\).

The test \[\label{eq:test95impure95DP95coordinate95wise95strat} T_{\text{II}} = \text{\usefont{U}{bbm}{m}{n}1}\left\{ \frac{1}{\sqrt{d_L}} \underset{(l,k) \in I_L}{\overset{}{\sum}} \left[ \left( \frac{1}{\sqrt{|\cJ_{lk;L}|}} \underset{j \in \cJ_{lk;L}}{\overset{}{\sum}} Y^{(j)}_{lk;L} \right)^2 - \frac{n\epsilon^2}{4{K_L}\tau^2} - 1 \right] \geq \kappa_\alpha \left(\frac{n\epsilon^2}{4{K_L}\tau^2} \vee 1\right) \right\}\tag{21}\] satisfies \(\P_0 T_{\text{II}} \leq \alpha\) by Lemma 24 in the supplement whenever \(\tilde{\kappa}_\alpha > 0\) and \(\kappa_\alpha > 0\) are chosen large enough.

The power that the test attains depends on the signal size up until resolution level \(L\), i.e. \(\|\Pi_L f \|_2\). Specifically, the test Type II error \(\P_f (1 - T_{\text{II}}) \leq \alpha\) whenever \[\label{eq:f95condition951coord} \| \Pi_L f \|_2^2 \geq C_\alpha \frac{ \log \log (N) \log(N) \log(1/\delta) 2^{(3/2)L}}{ m n^2 \epsilon^2}.\tag{22}\] The optimal choice of \(L\) for is determined by the trade-off between the approximation error \(\| f - \Pi_L f \|_2^2\) and the right-hand side of 22 . The proof of the following lemma is given in Section [ssec:supp:procedure95II] of the supplement.

3.3 Private testing procedure III: high privacy-budget shared randomness strategy↩︎

In this section, we construct a testing procedure that is based on the same principles as the one in the previous section, but with the difference that the servers a source of randomness. The transcripts are still based on the clipped and averaged coordinates of the truncated data, but instead of dividing the servers across the coordinates, we apply the same random rotation across the servers.

Next, we describe the testing procedure in detail. Consider for \(L \in \N\) the quantities \(d_L = \sum_{l=1}^L 2^l\) and \(K_L = \lceil n \epsilon^2 \wedge d_L \rceil\) and let \(U_L\) denote a random rotation uniformly drawn (i.e. from the Haar measure) on the group of random orthonormal \({d_L \times d_L}\)-matrices.

For \(I_L:= \{ (l,k) : l=1,\dots, \lceil \log_2(K_L) \rceil, \, k=1,\dots,2^l \}\), \((l,k) \in I_L\) and \(j=1,\dots,m\), generate the transcripts according to \[\label{eq:transcripts95pub95coin95privacy95impure95DP} Y^{(j)}_{lk;L} | (X^{(j)},U) = \gamma_L \, \underset{i=1}{\overset{n}{\sum}} [ (U X_{L;i}^{(j)})_{lk} ]^\tau_{-\tau} + W^{(j)}_{lk},\tag{23}\] with \(\gamma_L = \frac{\epsilon}{2\sqrt{2K_L \log(2/\delta) \log(N)}\tau}\), \(\tau = \tilde{\kappa}_\alpha \sqrt{\log(N/\sigma)}\), \(\tilde{\kappa}_\alpha > 0\) and \((W^{(j)}_l)_{j,l}\) i.i.d. centered standard Gaussian noise. By an application of Lemma 25, the transcript \(Y^{(j)}_L := (Y^{(j)}_{lk;L})_{(l,k)\in I_L}\) is \((\epsilon,\delta)\)-differentially private.

In the shared randomness strategy above, we essentially only send the first \(\sum_{l=1}^{\lceil \log_2(K_L) \rceil} 2^l\) coordinates. The random rotation \(U_L\) ensures that, roughly speaking, a sufficient amount of the signal is present in these first coordinates, with high probability.

We then construct the test \[\label{eq:test95pub95coin95privacy95impure95DP} T_{\text{III}} = \text{\usefont{U}{bbm}{m}{n}1}\left\{ \frac{1}{\sqrt{K_L}} \underset{(l,k) \in I_L}{\overset{}{\sum}} \left[ \left( \frac{1}{\sqrt{m}} \underset{j =1}{\overset{m}{\sum}} Y^{(j)}_{lk;L} \right)^2 - n\gamma^2_L - 1 \right] \geq \kappa_\alpha \left(n \gamma^2_L \vee 1\right) \right\},\tag{24}\] which satisfies \(\P_0 \varphi \leq \alpha/2\) by Lemma 26 in the supplement, for \(\kappa_\alpha > 0\) large enough. The lemma below is proven in Section 8 of the supplement, and yields that the Type II error of the test satisfies \(\P_f (1 - T_{\text{III}}) \leq \alpha\) whenever the coordinates up to resolution level \(L\) are of sufficient size. The optimal value for \(L\) depends on the truncation level \(s\), and is chosen by balancing the approximation error \(\| f - \Pi_L f \|_2^2\) and the right-hand side of 25 , we defer the reader to Section 8.3 of the supplement for details.

4 Adaptive tests under DP constraints↩︎

In the previous section we have derived methods that match (up to logarithmic factors) the theoretical lower bound established in Section 2. The proposed tests, however, depend on the regularity parameter \(s\) of the functional parameter of interest \(f\).

In this section we derive an distributed \((\epsilon,\delta)\)-DP testing protocol that adapts to the regularity when it is unknown. This method attains the optimal rate of Theorem 3, and consequently proves the aforementioned theorem.

The adaptive procedure builds on the tests constructed in Section 3 and combines them using essentially a multiple testing strategy. Roughly speaking, the method consists of taking approximately a \(1/\log N\)-mesh-size grid in the regularity interval \([s_{\min},s_{\max}]\), constructing optimal tests for each of the grid points and combining them using a type of Bonferroni’s correction. By design, the tests constructed in Section 3 are based on sub-exponential private test statistics, which allows a combination of the test statistics with a Bonferroni correction of the order of \(\log \log N\).

Combining \(\log N\) many \((\epsilon',\delta)\)-differentially private transcripts using Gaussian mechanisms, results in a \((\epsilon,\delta)\)-differentially private protocol, with \(\epsilon = \epsilon' \sqrt{\log N}\). This means that the erosion of the privacy budget by conducting a test for each grid-point is limited to a logarithmic factor, means the method greatly improves over the potentially polynomially worse rate of a non-adaptive method.

The detailed adaptive testing procedures are given as follows. Let \(\rho_s\) equal the right-hand side of 7 in case there is access to local randomness only, or the right-hand side of 6 in case shared randomness is available. Let \({L_{s}}=\lfloor s^{-1}\log_2 (1/\rho_s)\rfloor \vee 1\) and define furthermore \(\mathcal{S}:=\{L_{s_{\min}},\dots,L_{s_{\max}}\}\) such that \(L_s\in \cS\) for all \(s\in[s_{\min},s_{\max}]\). Furthermore, we note that the resulting “collection of resolution levels” satisfies \(|\mathcal{S}| \leq C_{s_{\max}} \log N\) for some constant \(C_{s_{\max}} > 0\) depending only on \(s_{\max}\).

Consider the first the case without access to shared randomness. We partition the collection of resolution levels \(\mathcal{S}\), depending on the model characteristics, as follows. \[\label{eq:partition95of95resolution95levels95local95randomness} \cS^{\texttt{LOW}}_{\texttt{LR}} = \left\{ L \in \cS : 2^L \leq \epsilon \sqrt{mn} (1 + \sqrt{n}\text{\usefont{U}{bbm}{m}{n}1}_{\{\sqrt{n} \epsilon > 1\}}) \right\}, \quad \cS^{\texttt{HIGH}}_{\texttt{LR}} = \cS \setminus \cS^{\texttt{LOW}}_{\texttt{LR}}.\tag{26}\] If the true regularity \(s_0\) is such that \(L_{s_0} \in \cS^{\texttt{LOW}}\), the low privacy-budget test of Section 3.1 (with \(L = L_{s_0}\)) is a rate optimal strategy. If \(L_{s_0} \in \cS^{\texttt{HIGH}}\), the high privacy-budget test of Section 3.2 is rate optimal.

For the case of shared randomness, the phase transitions occur for different values of \(s\in[s_{\min},s_{\max}]\), or their respective resolution levels \(L_s\). So in this case, we partition the collection of resolution levels as \[\label{eq:partition95of95resolution95levels95shared95randomness} \cS^{\texttt{LOW}}_{\texttt{SHR}} = \left\{ L \in \cS : 2^L \leq \epsilon^2 {mn} \right\}, \quad \cS^{\texttt{HIGH}}_{\texttt{SHR}} = \cS \setminus \cS^{\texttt{LOW}}_{\texttt{SHR}}.\tag{27}\] Consider some \(\cS' \subset \cS\). The “adaptive version” of the low privacy-budget test defined in 19 takes the form \[\label{eq:definition95full95test95lips95ext95privacy95adaptive} T_{\text{I}}^S := \text{\usefont{U}{bbm}{m}{n}1} \left\{ \underset{L \in \cS',\, \tau \in \mathrm{T}_L}{\max} \; \; \frac{1}{\sqrt{m} \left( \gamma_L \vee 1 \right) \sqrt{\log |\mathrm{T}_L||\cS'|}} \; \underset{j=1}{\overset{m}{\sum}} Y^{(j)}_{L;\tau} \geq \kappa_\alpha \right\},\tag{28}\] where \(\mathrm{T}_L\) is as defined in 18 and \(Y^{(j)}_L = \{ Y^{(j)}_{L;\tau} : \tau \in \mathrm{T}_L \}\) is generated according to 14 for \(L \in S\) with \[\gamma_\tau = \frac{\epsilon}{2 D_\tau \sqrt{ |\mathrm{T}_L| |\cS'| \log (4 / \delta)}}.\] The above choice of \(\epsilon\) yields that \((Y^{(j)}_L)_{L \in S}\) is \((\epsilon/2,\delta/2)\)-DP due to the Gaussian mechanism. The enlargement of the critical region, which is now effectively rescaled by \(\sqrt{\log |\mathrm{T}|_L|\cS'|}\) instead of \(\sqrt{\log |\mathrm{T}|_L}\), accounts for the potentially larger set of test statistics over which the maximum is taken. In the case of having access only to local sources of randomness, we set \(\cS' = \cS^{\texttt{LOW}}_{\texttt{LR}}\). If \(\cS^{\texttt{LOW}}_{\texttt{LR}}\) is empty, we set \(T_{\text{I}} = 0\) instead, which forms an \((0,0)\)-differentially private protocol.

In the case of having access to local sources of randomness only; if \(\cS^{\texttt{HIGH}}_{\texttt{LR}}\) is non-empty, the adaptive version of the high privacy-budget test defined in 21 is given by \[\label{eq:test95impure95DP95coordinate95wise95strat95adaptive} T_{\text{II}} = \text{\usefont{U}{bbm}{m}{n}1}\left\{ \underset{L \in \cS^{\texttt{HIGH}}_{\texttt{LR}}}{\max} \; \frac{1}{\sqrt{d_L} \left(\eta_L \vee 1\right)} \underset{(l,k) \in I_L}{\overset{}{\sum}} \left[ \left( \frac{1}{\sqrt{|\cJ_{lk;L}|}} \underset{j \in \cJ_{lk;L}}{\overset{}{\sum}} Y^{(j)}_{lk;L} \right)^2 - \eta_L - 1 \right] \geq \kappa_\alpha \sqrt{\log |\cS^{\texttt{HIGH}}|} \right\},\tag{29}\] where the transcripts are generated according to 20 for \(L \in \cS^{\texttt{HIGH}}\), with \(\gamma_L = {\epsilon}/({4 \sqrt{ |\cS^{\texttt{HIGH}}| K_L \log(4/\delta)}\tau})\), \(\eta_L = \frac{n\epsilon^2}{4{K_L}\tau^2}\), \(\tau = \tilde{\kappa}_\alpha \sqrt{\log(N/\sigma)}\). Due to the Gaussian mechanism, the transcripts satisfy an \((\epsilon/2,\delta/2)\)-DP constraint. As before, if \(\cS^{\texttt{HIGH}}\) is empty, set \(T_{\text{II}} = 0\) instead.

In the case of having access to local randomness only, the adaptive testing procedure then consists of computing the tests \(T_{\text{I}}^{\cS^{\texttt{LOW}}}\) and \(T_{\text{II}}^{}\), for which the released transcripts satisfy \((\epsilon,\delta)\)-DP. The final test is then given by \[\label{eq:final95adaptive95test95local95randomness} T = T_{\text{I}}^{\cS^{\texttt{LOW}}} \vee T_{\text{II}}.\tag{30}\] In Section 8 in the supplement, it is shown that this test is adaptive and rate optimal (up to logarithmic factors), proving the first part of Theorem 3.

In case of shared randomness, the adaptive version of the high privacy-budget test defined in 24 is given by \[\label{eq:test95pub95coin95privacy95impure95DP95adaptive} T_{\text{III}} = \text{\usefont{U}{bbm}{m}{n}1}\left\{ \underset{L \in S^{\texttt{HIGH}}_{\texttt{SHR}}}{\max} \; \frac{1}{\sqrt{K_L} \left(n \gamma_{L}^2 \vee 1\right)} \underset{(l,k) \in I_L}{\overset{}{\sum}} \left[ \left( \frac{1}{\sqrt{m}} \underset{j =1}{\overset{m}{\sum}} Y^{(j)}_{lk;L} \right)^2 - n\gamma^2_L - 1 \right] \geq \kappa_\alpha \sqrt{\log |\cS|} \right\},\tag{31}\] where the transcripts are generated according to 23 for \(L \in S^{\texttt{HIGH}}_{\texttt{SHR}}\), \(\gamma_L = \frac{\epsilon}{4\sqrt{K_L |S^{\texttt{HIGH}}_{\texttt{SHR}}| \log(4/\delta) \log(N)}\tau}\), \(\tau = \tilde{\kappa}_\alpha \sqrt{\log(N/\sigma)}\). By similar reasoning as earlier, the transcripts \(\{Y^{(j)}_L : L \in \S^{\texttt{HIGH}}_{\texttt{SHR}} \}\) are \((\epsilon/2,\delta/2)\)-DP. If \(S^{\texttt{HIGH}}_{\texttt{SHR}}\) is empty, we set \(T_{\text{III}} = 0\) instead.

The adaptive testing procedure in the case of shared randomness then consists of computing the tests \(T_{\text{I}}^{S^{\texttt{LOW}}}\) and \(T_{\text{III}}\), for which the released transcripts satisfy \((\epsilon,\delta)\)-DP. The final test is then given by \[\label{eq:final95adaptive95test95shared95randomness} T = T_{\text{I}}^{S^{\texttt{LOW}}_{\texttt{SHR}}} \vee T_{\text{III}}.\tag{32}\]

In the supplement’s Section 8, we prove that this test is adaptive, attaining the optimal rate for shared randomness protocols (up to logarithmic factors), giving us the second statement Theorem 3.

5 The minimax private testing lower bound↩︎

In this section, we present a single theorem outlining the lower bound for the detection threshold for distributed testing protocols that adhere to DP constraints, with and without the use of shared randomness. The theorem directly yields the “lower bound part” of Theorems 2 and 1 presented in Section 2. In conjunction with Theorem 4, the theorem shows that the tests constructed in Section 3 are rate optimal up to logarithmic factors.

The theorem states that, whenever the signal-to-noise ratio \(\rho\) is below a certain threshold times the minimax separation rate, no distributed testing protocol can achieve a combined Type I and Type II error rate below \(\alpha\). Its proof is lengthy and involves a combination of various techniques. We defer the full details of the proof to Section 7 of the supplement, but provide an overview of the main steps below.

For Steps 1, 2 and 3, there is no distinction between local and shared randomness. We use the same notation for distributed protocols in these steps, but simply assume \(U\) is degenerate in the case of local randomness.

1. The first step is standard in minimax testing analysis: we lower bound the testing risk by a Bayes risk, \[\label{eq:lb95proof95many-normal95bayes95risk95lb} \underset{T \in \mathscr{T}}{\inf} \, \cR(H_\rho,T) \geq \underset{T \in \mathscr{T}}{\inf} \, \underset{\pi}{\sup} \, \left( \P_0(T(Y) = 1) + \int \P_{f} ( T(Y) = 0) d\pi(f) - \pi(H_\rho^c) \right),\tag{36}\] where \(\mathscr{T}\) denotes either the class of local randomness or shared randomness \((\epsilon,\delta)\)-DP protocols. This inequality allows the prior \(\pi\) to be chosen adversarially to the distribution of the transcripts. This turns out to be crucial in the context of local randomness protocols, as is further highlighted in Step 4. The specific prior distribution is chosen to be a centered Gaussian distribution, with a finite rank covariance, where the rank is of the order \(2^{L}\), for some \(L \in \N\). This covariance is constructed in a way that it puts most of its mass in the dimensions in which the privacy protocol is the least informative, whilst at the same time it assures that the probability mass outside of the alternative hypothesis \(\pi(H_\rho^c)\) is small. The particular choice for a Gaussian prior (instead of e.g. the two point prior in [18]) is motivated by Step 3.

2. In this step, we approximate the distribution of the transcripts with another distribution that results in approximately the same testing risk, but has two particular favorable properties for our purposes.

   • Whenever the distribution of a transcript satisfies an \((\epsilon,\delta)\)-DP constraint with \(\delta > 0\), the transcript’s density can be unbounded on a set of small probability mass (proportional to \(\delta\)). Consequently, the local likelihoods of the transcripts can have erratic behavior in the tails. To remedy this, we consider approximations to the transcripts that have bounded likelihoods, that differ only on a set that is negligible in terms of its impact on the testing risk. Furthermore, these approximating transcripts satisfy a \((\epsilon,2\delta)\)-DP privacy constraint. These bounded likelihoods enable the argument of Step 5.

   • Similarly, whenever \(\delta > 0\), the distribution of the data conditionally on the transcript potentially has an unbounded density. For the argument employed in Step 3, we require a uniform abound on the density of the distribution of \(X|Y\). We mitigate this by approximating the distribution of the transcripts by a distribution that induces a bounded density for the data conditionally on the transcript. This approximation of the original transcript satisfies a \((\epsilon,3\delta)\)-DP constraint.

   Furthermore, we show that both approximations can be done in a way that the approximating transcript distribution is \((\epsilon,6\delta)\)-DP.

3. By standard arguments, on can further lower bound the testing risk in 36 for a particular transcript distribution \(\P^{Y|X,U} = \bigotimes^m_{j=1} \P^{Y^{(j)}|X^{(j)},U}\) and prior distribution \(\pi\) by a quantity depending on the chi-square divergence between \(\P_\pi^{Y|U=u}\) and \(\P_0^{Y|U=u}\); \[\label{eq:chi-sq-div-lb} 1 - \left( \sqrt{(1/2) \int \E_0^{Y|U=u} \left(\left( \frac{d\P_\pi^{Y|U=u}}{d\P_0^{Y|U=u}} \right)^2 - 1 \right)^2 d\P^U(u) } + \pi(H_\rho^c) \right).\tag{37}\] The likelihood ratio of the transcripts depends on the privacy protocol, and is difficult to analyze directly. We employ the technique developed in [66]. Specifically, Lemma 10.1 in [66], which states, roughly speaking, that the inequality \[\label{eq:brascamplieb-ineq} \E_0^{{Y}|U=u} \left( \frac{d\P_\pi^{Y|U=u}}{d\P_0^{Y|U=u}} \right)^2 \leq {G} \underset{j=1}{\overset{m}{\Pi}} \E_0^{{Y^{(j)}}|U=u} \left( \frac{d\P_\pi^{Y^{(j)}|U=u}}{d\P_0^{Y^{(j)}|U=u}} \right)^2\tag{38}\] holds for a finite constant \(0<{G}<\infty\) and equality with the smallest possible \({G}\) is attained whenever the conditional distribution of the data given the transcripts is Gaussian in an appropriate sense (we defer the details here to Section 7.3 in the supplement). This result is a type of Brascamp-Lieb inequality [70], [71]. There is an existing literature on Brascamp-Lieb inequality in relation to information theoretical problems, in relation to mutual information [72]–[74], in addition to the communication constraint testing problem in [66]. That 38 has a “Gaussian maximizer” allows tractable analysis of the chi-square divergence in 37 , yielding that the latter display is further lower bounded by \[1 - \sqrt{(1/2) \int \left( \mathrm{A}_u^\pi \mathrm{B}_u^\pi - 1 \right) d\P^U(u) } + \pi(H_\rho^c),\] where \[\label{eq:Au95Bu95defined} \mathrm{A}_u^\pi := \int e^{ f^\top \sum_{j=1}^{m} \Xi^j_u g} d(\pi \times \pi)(f,g), \quad \mathrm{B}_u^\pi := \underset{j=1}{\overset{m}{\Pi}} \E_0^{{Y^{(j)}}|U=u} \left( \frac{d\P_\pi^{Y^{(j)}|U=u}}{d\P_0^{Y^{(j)}|U=u}} \right),\tag{39}\] where \(\Xi^j_u\) denotes the covariance of (a subset of) the data \(X^{(j)}_L\) (defined as in 40 ) conditionally on the transcript \(Y^{(j)}\) and \(U=u\); \[\label{eq:def95Xi95uj} \Xi_u^{j} := \E_0^{Y^{(j)}|U=u} \E_0\left[ \underset{i=1}{\overset{n}{\sum}} \sigma^{-1} {X}^{(j)}_{L;i} \bigg| Y^{(j)}, U=u \right] \E_0\left[ \underset{i=1}{\overset{n}{\sum}} \sigma^{-1} {X}^{(j)}_{L;i} \bigg| Y^{(j)}, U=u \right]^\top.\tag{40}\] Whilst the quantities \(\mathrm{A}_u\) and \(\mathrm{B}_u^\pi\) are still not fully tractable, sharp bounds for both are possible and form the content of Steps 4 and 5, respectively.

4. As remarked earlier, class of local randomness protocols is a strictly smaller class. To attain the sharper (i.e. larger) lower bound for local randomness protocols, we exploit the fact that Step 2 allows us to choose the prior adversarially to the distribution of the transcripts. In particular, since \(U\) is degenerate in the case of local randomness only, this means that the covariance of \(\pi\) to be more diffuse in the directions in which \(\Xi^j_u\) is the smallest. When considering shared randomness protocols, \(U\) is not degenerate, and the lower bound follows by taking the covariance of \(\pi\) to be an order \(2^L\)-rank approximation of the identity map on \(\ell_2(\N)\). The bounds for \(\mathrm{A}_u^\pi\) are \[\mathrm{A}_u^\pi = \exp\left({ C \frac{\rho^4}{c_\alpha 2^{3L}} \text{Tr} \left( \Xi_u \right)^2 }\right) \quad \text{ and } \quad \mathrm{A}_u^\pi \leq \exp\left({ C \frac{\rho^4}{c_\alpha 2^{2L}} \|\Xi_u\| \text{Tr} \left( \Xi_u \right) }\right)\] for local randomness protocols and shared randomness protocols, respectively.

5. So far, Steps 1-4 have not used the fact that the transcripts are necessarily less informative than the original data, as a consequence of the transcripts being \((\epsilon,\delta)\)-DP. In this step, we exploit the privacy constraint to argue that \(\mathrm{A}_u^\pi\) and \(\mathrm{B}_u^\pi\) are small at the detection boundary for \(\rho\).

   In order to capture the information loss due to privacy in \(\mathrm{A}_u^\pi\), it suffices to bound the trace and operator norm of \(\Xi_u\). The quantity \(\Xi_u\) can be seen as the Fisher information of the finite dimensional submodel spanned by the covariance of \(\pi\). This quantity, loosely speaking, captures how much information the transcript contains on the original data. In order to analyze \(\Xi_u\), we rely on a “score attack” type of technique, as employed in [13], [75].

   The quantity \(\mathrm{B}_u^\pi\) corresponds to the (product of) the local likelihoods of the transcripts. Whenever \(\epsilon \geq 1/\sqrt{n}\), it suffices to consider the trivial bound \[\E_0^{{Y^{(j)}}|U=u} \left( \frac{d\P_\pi^{Y^{(j)}|U=u}}{d\P_0^{Y^{(j)}|U=u}} \right) \leq \E_0^{{X^{(j)}}|U=u} \left( \frac{d\P_\pi^{X^{(j)}}}{d\P_0^{X^{(j)}}} \right),\] and further bounding the right-hand side without privacy specific arguments. Whenever \(\epsilon < 1/\sqrt{n}\), more sophisticated methods are need to capture the effect of privacy. Our argument uses a coupling method, which, combined with the fact that the likelihoods of the transcripts are bounded in our construction, allows us to obtain a sharp bound for \(\mathrm{B}_u^\pi\). After obtaining the bounds in terms of the rank \(2^L\) and \(\rho\), the proof is finished by choosing \(L\) such that the second and third term in 37 are balanced (minimizing their sum).

6 Discussion↩︎

The findings in this paper highlight the trade-off between statistical accuracy and privacy in federated goodness-of-fit testing under differential privacy (DP) constraints. We characterize the problem in terms of the minimax separation rate, which quantifies the difficulty of the testing problem based on the regularity of the underlying function, the sample size, the degree of data distribution, and the stringency of the DP constraint. The minimax separation rate varies depending on whether the distributed testing protocol has access to local or shared randomness. Furthermore, we construct data-driven adaptive testing procedures that achieve the same optimal performance, up to logarithmic factors, even when the regularity of the functional parameter is unknown.

One possible extension of this work is to consider a more general distribution of the privacy budget across the servers. Our current analysis supports differing budgets to the extent that \(\epsilon_j \asymp \epsilon_k\), \(\delta_j \asymp \delta_k\), and \(n_j \asymp n_k\). However, one could explore more heterogeneous settings where severs differ significantly in their differential privacy constraints and number of observations. Although this would complicate the presentation of results, the techniques developed in this paper could, in principle, be extended to such settings.

Another interesting direction is to consider multiple testing problems, where the goal is to test multiple hypotheses simultaneously. We anticipate that the framework, insights, and theoretical results provided in the current paper will serve as valuable resources for future studies in this domain.

Regarding adaptation, not much is known about the cost of privacy outside the local DP setting (i.e., one observation per server; \(n=1\) in our context). Interestingly, the cost of adaptation is minimal in the privacy setting considered in this paper. It remains an open question whether this minimal cost is a general phenomenon, whether it can be characterized exactly, or whether the cost of adaptation is more severe in other settings. We leave these questions for future research.

7 Proof of the lower bound Theorem 5↩︎

In this section, we provide a proof for Theorem 5. The proof is divided into several steps, following the outline provided in Section 5.

It is convenient to introduce the following notation. In the notation that follows, we shall consider a local randomness protocol to consist of a triplet \[( T, \{\left(\P^{Y^{(j)}|X^{(j)} = x, U=u}\right)_{x \in \cX^n,u\in \cU} \}_{j=1}^m, (\cU,\mathscr{U},\P^U)),\] where the probability space \((\cU,\mathscr{U},\P^U)\) has the trivial sigma-algebra; \(\mathscr{U} = \{ \emptyset, \cU\}\). This allows streamlining the argument for both lower bounds of Theorem 5 into a single argument. Given an \((\epsilon,\delta)\)-DP distributed protocol triplet \[( T, \{\left(\P^{Y^{(j)}|X^{(j)} = x, U=u}\right)_{x \in \cX^n,u\in \cU} \}_{j=1}^m, (\cU,\mathscr{U},\P^U)),\] we shall use the notation \(P_f = \P_f^{X^{(j)}}\). For the Markov kernel \[(A,(x,u)) \mapsto \P^{Y^{(j)}|(X^{(j)},U)=(x,u)}(A),\] we shall use the shorthand \((A,(x,u)) \mapsto K^j(A|(x,u))\). If the transcript \(Y^{(j)}\) is \((\epsilon,\delta)\)-DP, the Markov kernel satisfies \[\begin{align} \label{eq:privacy95constraint} K^j(A&|x_1,\dots,x_i,\dots,x_n,u) \leq e^{\epsilon} K^j(A|x_1,\dots,x_i',\dots,x_n,u) + \delta \\ &\text{ for all } A \in \mathscr{Y}, \; x_i',x_1,\dots,x_i,\dots,x_n \in \cX, \; i \in \{1,\dots,n\}. \nonumber \end{align}\tag{41}\]

When the parameter underlying the true distribution of the data \(F\) is drawn from a prior distribution on \(\ell_2(\N)\), we obtain that the distributed testing protocol satisfies the Markov chain \[\label{def:32dist:test:MC} { \quad F} \qquad \begin{matrix} \put(-10,-4){\vector(3,1){20}} &\quad(X^{(1)},U) &\put(0,5){\vector(1,0){20}} &\qquad Y^{(1)}\quad&\put(-10,4){\vector(3,-1){20}} \\ \put(-10,3){\vector(1,0){20}}&\quad\vdots &\put(0,4){\vector(1,0){20}} &\qquad\vdots \quad&\put(-10,4){\vector(1,0){20}} \\ \put(-10,12){\vector(3,-1){20}}&\quad(X^{(m)},U) & \put(0,5){\vector(1,0){20}} &\qquad Y^{(m)}\quad&\put(-10,5){\vector(3,1){20}} \end{matrix} \qquad T,\tag{42}\] with \(\P^{Y^{(j)}|U=u}_f = P_f K^j(\cdot|X^{(j)},u)\) for all \(j \in [m]\). Let \(K_u = \bigotimes_{j=1}^m K^j(\cdot|\cdot,u)\) denote the product conditional distribution with \(U=u\), such that distribution of the collection of transcripts conditionally on \(U=u\) then satisfies \(\P^{Y|U=u}_f = P^m_f K_u()\).

If the transcript \(Y^{(j)}\) is \((\epsilon,\delta)\)-DP and generated from \(K^j_u, u \in \cU\), this translates to \[\begin{align} \label{uzenhlod} K^j(A&|x_1,\dots,x_i,\dots,x_n,u) \leq e^{\epsilon} K^j(A|x_1,\dots,x_i',\dots,x_n,u) + \delta \\ &\text{ for all } A \in \mathscr{Y}, \; x_i',x_1,\dots,x_i,\dots,x_n \in \cX, \; i \in \{1,\dots,n\}. \nonumber \end{align}\tag{43}\]

7.1 Step 1: Lower bounding the testing risk by the Bayes risk↩︎

As a first step, we lower bound the testing risk by the Bayes risk. Following the notation introduced above, let \(T\equiv ( T, \{{K}^j \}_{j=1}^m, (\cU,\mathscr{U},\P^U))\) be an \((\epsilon,\delta)\)-DP distributed testing protocol and let \({K}_u = \bigotimes_{j=1}^m {K}^j(\cdot|\cdot,u)\). The testing risk for \(T\) can be written as \[\cR( H_{\rho}^{{s},R} , T) = \int P_0^m K_u T d\P^U(u) + \underset{f \in H_{\rho}^{s,R}}{\sup} \int P_{f}^m K_u(1-T) d\P^U(u).\] Consider \(L \in \N\), \(d_L = \sum_{l=1}^L 2^l\) and consider \(\pi = N(0,c_\alpha^{-1/2} d^{-1}_L \rho^2 \bar{\Gamma})\) for a symmetric idempotent matrix \(\bar{\Gamma} \in \R^{d_L \times d_L}\). Consider also the linear operator \(\Psi_L : \R^{d_L} \to \ell_2(\N)\) defined by \(\Psi_L \tilde{f} = f\) for \[\label{eq32:32inverse32wavelet32transform} f_{lk} = \begin{cases} \tilde{f}_{lk} & \text{if } l \leq L, \\ 0 & \text{if } l > L, \end{cases}\tag{44}\] for \(\tilde{f}=(\tilde{f}_{11},\dots,\tilde{f}_{L 2^L}) \in \R^{d_L}\). Since \(\Psi_L\) is measurable, any probability distribution \(\pi_L\) on \(\R^{2^L}\), \(\pi_L \circ \Psi^{-1}_L\) defines a probability measure on the Borel sigma algebra of \(\ell_2(\N)\).

Using that \(0 \leq T \leq 1\), the above testing risk is lower bounded by the Bayes risk \[\label{eq:privacy95bayes95risk95breve-pre-pi-bound} \int \left( P_0^{m}{K}_u T + \int P_{f}^{m} {K}_u ( 1 - T) d\pi \circ \Psi^{-1}_L(f) \right) d\P^U(u) - \pi \circ \Psi^{-1}_L \left( (H_{\rho}^{s,R})^c \right).\tag{45}\] We highlight here that \(\bar{\Gamma}\) can depend on \(\{ {K}^j \}_{j=1}^m\).

To lower bound the testing risk further, it suffices to show that the prior \(\pi\) has little mass outside of \(H_\rho^{s,R}\). This follows by a standard Gaussian concentration argument, provided in Lemma 5 below, from which it follows that, for \(c_\alpha > 0\) small enough, it holds that \(\pi \circ \Psi^{-1} ((H_\rho^{s,R})^c) \leq \alpha/4\). This yields that 45 is lower bounded by \[\label{eq:privacy95bayes95risk95breve} \int \left( P_0^{m}{K}_u T + \int P_{f}^{m} {K}_u ( 1 - T) d\pi \circ \Psi^{-1}_L(f) \right) d\P^U(u) - \alpha/4.\tag{46}\]

The larger \(L\), the larger the effective dimension of the signal under the alternative hypothesis. Setting \(L\) such that \(2^L \asymp \rho^{-1/s}\) means that the requirement of the above lemma are satisfied and consequently the Gaussian prior most of it its mass in the alternative hypothesis. Recalling that \(d_L \asymp 2^L\), the condition 33 in the case of local randomness protocols can be written as \[\label{eq:nonasymptotic95testing95lower95bound95local95randomness95dL} \rho^2 \lesssim c_\alpha \sigma^2 \left( \frac{d_L^{3/2}}{ m n (n\epsilon^2 \wedge d_L)} \bigwedge \left( \frac{\sqrt{d_L}}{\sqrt{m}n \sqrt{n \epsilon^2 \wedge 1}} \bigvee \frac{1}{mn^2 \epsilon^2} \right) \right),\tag{48}\] and in the case of shared randomness protocols, 34 can be written as \[\label{eq:nonasymptotic95testing95lower95bound95shared95randomness95dL} \rho^2 \lesssim c_\alpha \sigma^2 \left( \frac{d_L}{ m n \sqrt{n \epsilon^2 \wedge 1} \sqrt{n\epsilon^2 \wedge d_L }} \bigwedge \left( \frac{\sqrt{d_L}}{\sqrt{m}n \sqrt{n \epsilon^2 \wedge 1} } \bigvee \frac{1}{mn^2 \epsilon^2} \right) \right).\tag{49}\]

7.2 Step 2: Approximating the distribution of the transcripts↩︎

In Step 3, we aim to use the Brascamp-Lieb type inequality Lemma 10.1 of [66], which we restate as Lemma 12 below. However, the forward-backward channel corresponding to \({K}_u\), \((x_1,x_2) \mapsto {q}_u(x_1,x_2)\), defined as \[\label{eq:forward95backward95kernel95def} {q}_u(x_1,x_2) := \int \frac{d {K}(\cdot|x_1,u) }{ d\P_0^{Y|U=u} } (y) \frac{d {K}(\cdot|x_2,u) }{ d\P_0^{Y|U=u}} (y) d\P^{Y|U=u}_0(y),\tag{50}\] is possibly unbounded when \(\delta > 0\). To overcome this, we use Lemma 6 below to construct \((\epsilon,3\delta)\)-DP Markov kernels \(\{ \tilde{K}^j \}_{j=1}^m\) such that the corresponding forward-backward channel \(\tilde{q}_u(x_1,x_2)\) is bounded. The construction of \(\{ \tilde{K}^j \}_{j=1}^m\) is such that the total variation distance between \(\tilde{K}^j\) and \(\tilde{K}^j\) is small.

By standard arguments (see also Lemma 9), the first term in 46 can be lower bounded as follows; \[\begin{align} P_0^{m}{K}_u T &= P_0^{m}\tilde{K}_u T + P_0^{m}{K}_u T - P_0^{m}\tilde{K}_u T \\ &\geq P_0^{m}\tilde{K}_u T - \sum_{j=1}^m \| P_0 \tilde{K}^j(\cdot|X^{(j)}) - P_0 {K}^j(\cdot|X^{(j)}) \|_{\mathrm{TV}}. \end{align}\] The same argument on the second term yields that, we obtain that 46 is lower bounded by \[\label{eq:sup:approx-bayes-risk-I} \int \left( P_0^{m}\tilde{K}_u T + \int P_{f}^{m} \tilde{K}_u ( 1 - T) d\pi \circ \Psi^{-1}_L(f) \right) d\P^U(u) - 3\alpha/8,\tag{54}\] for an \((\epsilon,3\delta)\)-DP distributed testing protocol \(\tilde{T} = ( T, \{\tilde{K}^j \}_{j=1}^m, (\cU,\mathscr{U},\P^U))\).

Another issue suffered by \((\epsilon,\delta)\)-DP Markov kernels with \(\delta > 0\), is that one has very poor control over the higher moments of the local likelihoods \[{\cL}^{j}_{\pi,u}(y) := \frac{dP_\pi \tilde{K}^j(\cdot|X^{(j)},u)}{dP_0 \tilde{K}^j(\cdot|X^{(j)},u)} (y),\] where \(P_\pi(A) := \int P_f(A) d\pi \circ \Psi^{-1}_L(f)\), which are required to sufficiently bound the corresponding quantity \(\mathrm{B}_u\) defined in 69 in Step 5. Using similar ideas as in the proof of Lemma 6, we can construct approximating kernels \(\{ \breve{K}^j \}_{j=1}^m\) such that the likelihoods \(\cL^{j}_{\pi,u}\) are bounded. This is the content of the following lemma.

We prove this lemma at the end of this section. The lemma above, in combination with the same argument as before (e.g. Lemma 9) allows us to replace the \((\epsilon,3\delta)\)-DP Markov kernel \(\tilde{K}^j\) of 54 with an \((\epsilon,6\delta)\)-DP Markov kernel \(\breve{K}^j\), whose transcripts have bounded likelihoods in the sense of 55 . Furthermore, by part (c) of the lemma, the Bayes risk of 54 is further lower bounded by \[\label{eq:sup:approx-bayes-risk-II} \int \left( P_0^{m}\breve{K}_u T + \int P_{f}^{m} \breve{K}_u ( 1 - T) d\pi \circ \Psi^{-1}_L(f) \right) d\P^U(u) - \alpha/2,\tag{56}\] where the \(\breve{K}^j\)’s satisfy 51 .

7.2.1 Proof of Lemma 7↩︎

We finish the section by providing the two technical lemmas mentioned in the earlier proofs above. We omit the presence of the shared randomness \(U\) in the statement of the lemmas, as it is of no consequence to the arguments below.

7.3 Step 3: Bounding the Chi-square divergence using the Brascamp-Lieb inequality↩︎

We proceed with lower bounding 56 , where in a slight abuse of notation, we shall denote \(\breve{K}^j\) by \(K^j\) for the remainder of the section.

To lower bound the Bayes risk, in light of the Neyman-Pearson lemma, it should suffice to show that \(\cL^{Y|U=u}_\pi(Y)\) is close to \(1\) with high probability. This is made precise below by showing that the right-hand side of 56 is further bounded from below by \[\label{eq32:32sup32inf32public32coin32divergence32lb} 1 - \left( \sqrt{(1/2) \int \E_0^{Y|U=u} \left(\cL^{Y|U=u}_\pi(Y) - 1 \right)^2 d\P^U(u) } - \alpha/2 \right).\tag{58}\] To see this, note that any \(T : \cY^m \to \{0,1\}\), we can write \(A_T = T^{-1}( \{ 0 \} )\) and note that \[\begin{align} P_0^{m}\tilde{K}_u T(Y) + P_\pi^{m}\tilde{K}_u ( 1 - T(Y) ) &= 1 - \left(P_0^{m}\tilde{K}_u \left(Y \in A_T \right) - P_\pi^{m}\tilde{K}_u \left(Y \in A_T \right)\right). \end{align}\] We obtain that \[\begin{align} \label{bound95lecam} \int \left( P_0^{m}\tilde{K}_u T + \int P_{f}^{m} \tilde{K}_u ( 1 - T) d\pi \circ \Psi^{-1}(f) \right) d\P^U(u) & \\ \geq 1 - \underset{A}{\sup} \, | \int P_0^{m}\tilde{K}_u (A) - P_\pi^{m}\tilde{K}_u (A) d\P^U(u) |.& \end{align}\tag{59}\] We find by Jensen’s inequality that \[\|\P_{0}^Y - \P_{\pi}^Y \|_{\mathrm{TV}} \leq \int \|\P_{0}^{Y|U=u} - \P_{\pi}^{Y|U=u} \|_{\mathrm{TV}} d\P^U(u).\] Combining the above with Pinsker’s second inequality a standard bound for the Kullback-Leibler divergence (see Lemma 35), we obtain 58 .

This brings us to a crucial part of the proof; the application of Lemma 10.1 in [66], which we restate as Lemma 10 below. We first introduce some notation.

We note that for \(f \in \R^{d_L}\), it holds that \[\frac{dP_{\Psi f}}{dP_0}(X^{(j)}_i) \overset{d}{=} \frac{dN\left({f}, \sigma^2 I_{d_L}\right)}{dN\left(0, \sigma^2 I_{d_L}\right)} =: \mathscr{L}_f^{ji}(X^{(j)}_i),\] where the equality in distribution is true under \(\P_0^{X}\).

Denote the “local” and “global” likelihoods of the data as \[\mathscr{L}_f^j(X^{(j)})= {\prod}_{i=1}^n \mathscr{L}_f^{ji}(X^{(j)}_i), \; \; \; \mathscr{L}_f(X) := {\prod}_{j=1}^m \mathscr{L}_f^j(X^{(j)}),\] and the mixture likelihoods as \[\mathscr{L}_\pi^j(X) = \int \mathscr{L}_f(X^{(j)}) d \pi (f) \; \text{ and } \; \mathscr{L}_\pi(X) = \int \mathscr{L}_f(X) d \pi (f).\]

In view of the Markov chain structure, the probability measure \(d\P_\pi(x,u,y)\) disintegrates as \(d\P^{Y|(X,U)=(x,u)}d\P^X_f(x)d\P^U(u)d\pi(f)\). Using this, \(\E_0^{Y|U=u} \left(L^{Y|U=u}_\pi(Y)\right)^2\) can be seen to equal \[\label{eq32:32conditional32exp4632form32of32chi-sq32div} \E_0^{Y|U=u} \E_0\left[ \mathscr{L}_\pi(X) \bigg| Y, U=u \right]^2 = \int \left( \int \mathscr{L}_\pi(x) \frac{dK(\cdot|x,u)}{d\P^{Y|U=u}_0} (y) d\P_0^X(x) \right)^2 d\P^{Y|U=u}_0(y),\tag{60}\] where it is used that \(K(\cdot | x, u) \ll \P^{Y|U=u}_0(\cdot)\), \(\P^{(X,U)}_f\)-almost surely (Lemma 39). Using Fubini’s theorem (“decoupling” in \(X\)), we can write the above display as \[\label{eq32:32numerator32key32ratio32q32notation} \int \mathscr{L}_\pi(x_1) \mathscr{L}_\pi(x_2) q_u(x_1,x_2) d(\P_0^X \times \P_0^X) (x_1,x_2),\tag{61}\] where \[\label{xkybwcag} q_u(x_1,x_2) := \int \frac{d K(\cdot|x_1,u) }{ d\P_0^{Y|U=u} } (y) \frac{d K(\cdot|x_2,u) }{ d\P_0^{Y|U=u}} (y) d\P^{Y|U=u}_0(y).\tag{62}\] Since \(K(\cdot|x,u)\) and \(\P^{Y|U=u}_0\) are product measures on \(\cY = \cY^m\), we can write \(q_u(x_1,x_2) = \Pi_{j=1}^m q_u^j(x_1,x_2)\) where \[\label{eq:marginal95forward95backward95kernel95def} q_u^j(x_1,x_2) = \int \frac{K^j(y^{j}|x_1^{j},u) K^j(y^{j}|x_2^{j},u) }{ \P_0^{Y^{j}|U=u}(y^{j}) } d\P^{Y^{(j)}|U=u}_0(y).\tag{63}\] The map \((x_1,x_2)\mapsto q_u(x_1,x_2)\) can be seen as capturing the dependence between the original data \(X\) and a random variable \(X'\) with conditional distribution \[\label{eq:backward95forward95channel95Xprime} X'|X=x \sim \int d\P^{X|(Y,U)=(y,u)}_0 d\P^{Y|(X,U)=(x,u)},\tag{64}\] which is sometimes referred to as the “forward-backward channel”, stemming from the fact that \(X \to Y \to X'\) forms a Markov chain. An easy computation using the law of total expectation shows that the covariance of \(q_u(x_1,x_2) d(P_0 \times P_0) (x_1,x_2)\), \[\label{eq32:32q32cov32condition} \int \left( \begin{matrix} x_1 \\ x_2 \end{matrix}\right) \left( \begin{matrix} x_1^\top & x_2^\top \end{matrix}\right) q_u(x_1,x_2) d(P_0 \times P_0) (x_1,x_2) \in \R^{2mnd_L \times 2mnd_L},\tag{65}\] is equal to \(\Sigma_u := \text{Diag}\left(\Sigma^{11}_u,\dots,\Sigma^{1n}_u,\dots,\Sigma^{m1}_u,\dots,\Sigma^{mn}_u\right) \in \R^{2mnd_L \times 2mnd_L}\) for \[\Sigma^{ji} := \sigma^{2} \left(\begin{matrix} I_{d_L} & \Xi_u^{ji} \\ \Xi_u^{ji} & I_{d_L} \end{matrix}\right),\] with \[\Xi_u^{ji} := \E_0^{Y^{(j)}|U=u} \E_0\left[ \sigma^{-1} {X}^{(j)}_{L;i} \bigg| Y^{(j)}, U=u \right] \E_0\left[ \sigma^{-1} {X}^{(j)}_{L;i} \bigg| Y^{(j)}, U=u \right]^\top.\] Define also \[\label{eq:def95Xi95u95j} \Xi_u^{j} := \E_0^{Y^{(j)}|U=u} \E_0\left[ \sigma^{-1} \underset{i=1}{\overset{n}{\sum}} {X}^{(j)}_{L;i} \bigg| Y^{(j)}, U=u \right] \E_0\left[ \sigma^{-1} \underset{i=1}{\overset{n}{\sum}} {X}^{(j)}_{L;i} \bigg| Y^{(j)}, U=u \right]^\top.\tag{66}\] We are now ready to state the lemma that forms the crux of our distributed testing lower bound proof.

The lemma has the following interpretation: the ratio of the second moment of the Bayes factor of the “global Bayesian hypothesis test” that of the product of second moments of the “local Bayes factors”, is maximized over the class of forward-backward channel with covariance \(\Sigma\) when the forward-backward channel is Gaussian.

There is an existing literature on Brascamp-Lieb inequality in relation to information theoretical problems, in relation to mutual information [72]–[74]. For a proof, we refer to Lemma 10.1 in [66], which uses that the prior \(\pi\) is Gaussian, exploiting the conjugacy between the prior and the model which enables the use of techniques from [71].

The main consequence of the above lemma is analytic expressions, which can be used to upper bound the chi-square divergence in 58 which is the content of Lemma 11 below.

The above lemma describes how the variance of the Bayes factor given \(U\) is bounded by two factors. One factor depends on the Fisher information of the transcript’s likelihood at \(f=0\) given \(U=u\); \(\Xi_u := \sum_{j=1}^{m} \Xi^j_u\). In this sense, \(\mathrm{A}_u^\pi\) captures how well the transcript allows for “estimation” of \(f\). The second factor can be seen as the \(m\)-fold product of the local Bayes factors, capturing essentially the power of combining the locally most powerful test statistics; the likelihood ratios.

7.4 Step 4: Adversarially choosing the prior based on shared or local randomness↩︎

Suppose that for some constant \(c > 0\), \[\label{eq32:32to32check32before326462462} { \varrho^2} \| \sqrt{\bar{\Gamma}}^\top \Xi_u \sqrt{\bar{\Gamma}} \| \leq c.\tag{70}\] If \(\bar{\Gamma} \in \R^{d_L \times d_L}\) is symmetric, idempotent with rank proportional to \(d_L\) and \(\pi = N(0,\varrho^2 \bar{\Gamma})\), standard results for the Gaussian chaos, e.g. Lemma 6.2.2 in [76] combined with 70 and the fact that \(\|\sqrt{\bar{\Gamma}}\| \leq 1\), yield that \[\mathrm{A}_u^\pi \leq \exp \left( { C \sigma^{-2} { \varrho^4} \text{Tr} \left((\sqrt{\bar{\Gamma}}^\top \Xi_u \sqrt{\bar{\Gamma}})^2 \right) } \right),\] for a constant \(C>0\) depending only on \(c\). As a final step of the testing risk lower bound technique, we use essentially a geometric argument to sharpen this bound in case the distributed protocol does not enjoy shared randomness. The \(d_L \times d_L\) matrix \(\Xi_u := \sum_{j=1}^m \Xi_u^j\) geometrically captures how well \(Y\) allows to “reconstruct” the compressed sample \(X\). When \(U\) is degenerate, \(\Xi_u\) is “known” to the prior, and \(\bar{\Gamma}\) can be chosen to exploit “direction” in which \(\Xi_u\) contains the least information. We finish this section by proving the lemma below, which makes this notion precise.

7.5 Step 5: Capturing the cost of privacy in trace of \(\Xi_u\) and the local Bayes factors↩︎

The cost of privacy is captured through bounds on \(\mathrm{A}_u^\pi\) and \(\mathrm{B}_u^\pi\). These bounds specifically use the fact that the Markov kernels that underlie these quantities are \((\epsilon,6\delta)\)-differentially private.

We start with the bound on \(\mathrm{A}_u^\pi\), for which we proceed by a data processing argument for the matrix \(\Xi_u\) under the \((\epsilon,6\delta)\)-DP constraint. This comes in the guise of Lemma 13 below. Its proof is deferred to the end of the section.

The lemma implies in particular that \(\| \Xi_u^j \| \leq (C n^2 \epsilon^2) \wedge n\), as \(\Xi_u^j\) is symmetric and positive definite. Combining this with 49 and the triangle inequality, we obtain \[\label{eq32:32to32check32before32646246232public32coin} { \varrho^2} \| \Xi_u \| \leq { \varrho^2} \underset{j=1}{\overset{m}{\sum}} \| \Xi_u^j \| \leq \frac{m\left((C n^2 \epsilon^2) \wedge n\right) \rho^2}{\sigma^{2} \sqrt{c_\alpha} d_L} \leq C\sqrt{c_\alpha}.\tag{73}\] Similarly, 48 yields \[\label{eq32:32to32check32before32646246232private32coin} \frac{2 \rho^2}{\sqrt{c_\alpha} d^2_L} \text{Tr}\left( \Xi_u^j \right) \leq \frac{m\left((C n^2 \epsilon^2) \wedge (n d_L) \right) \rho^2}{\sigma^{2}\sqrt{c_\alpha} d^2_L} \leq C\sqrt{c_\alpha} / \sqrt{d_L}.\tag{74}\] The last two displays together finish the verification of the conditions of Lemma 12. The above data processing inequalities for \(\Xi_u^j\) and bounds on \(\rho^2\) also yield a bound on \(\mathrm{A}_u^\pi\) as defined in Lemma 12. In case of shared randomness protocols, using 71 , 73 , Lemma 13 and 49 , we obtain \[\mathrm{A}_u^\pi \leq \exp \left( C^2 c_\alpha \right).\] In case of local randomness protocols, combining 72 with 74 and 48 yields the above bound on \(\mathrm{A}_u^\pi\).

Next, we turn to \(\mathrm{B}_u^\pi\). The first bound, given in Lemma 14, does not use privacy at all. This bound is only tight whenever \(\epsilon \gtrsim 1/\sqrt{n}\) (as a bound on \(\mathrm{B}_u^\pi\)), in which case it corresponds to the regime where majority voting bares no privacy cost.

Whenever \(\epsilon \leq n^{-1/2}\), a much more involved data processing argument is needed than the one above. In the argument that follows, we will use the bound on \(\cL_{\pi,u}^j\) obtained through Lemma 7 in Step 2. The data processing argument leads to the bound of Lemma 15 below. Its proof is based on coupling arguments, where the two different couplings constructed result in the different rates observed in the condition of the theorem.

Combining the lemma above with the bound \(\mathrm{B}^\pi_u \leq \exp(C \frac{mn^2\rho^4}{\sigma^2 d_L})\) (which follows from Lemma 14), we obtain that 76 holds whenever \(\rho\) satisfies 48 or 49 . Combining this with the bounds on \(\mathrm{A}_u^\pi\) derived earlier and considering 58 lower bounds the testing risk, we obtain that \[\cR( H_{\rho}^{{s},R} , T) > 1 -\alpha\] for \(c_\alpha > 0\) small enough, from which the result of Theorem 5 follows. To complete the proof, we provide the proofs of Lemmas 13 and 15 in the following subsection.

7.5.1 Proof of Lemma 15↩︎

Before providing the proof of Lemma 15, we first develop additional tools.

First off is the following general coupling lemma that will be used in the proof of Lemma 15. The lemma is in essence Lemma 6.1 in [77], but its proof might be easier to verify and is provided for completeness.

Next, we construct the coupling that will be used in the proof of Lemma 15, in conjunction with Lemma 16 above. The couplings use similar ideas to the one constructed in [49].

With the above two lemmas in hand, we are ready to prove Lemma 15.

7.5.2 Proof of Lemma 13↩︎

8 Proofs related to the optimal testing strategies↩︎

The proofs concerning the three sections 3.1, 3.2 and 3.3 are given in this section, divided across the subsections 8.1, [ssec:supp:procedure95II] and 8.3 respectively.

We recall the notations \(d_L = \sum_{l=1}^L 2^l\) for \(L \in \N\), \(f_L = \Pi_L f\) for \(f \in \ell_2(\N)\) and \(\overline{X^{(j)}_L} = n^{-1} \sum_{i=1}^n X^{(j)}_{L;i}\) for \(j=1,\dots,m\).

8.1 Procedure I↩︎

We briefly recall the testing procedure outlined in Section 3.1. Let \(\tau > 0\), \(L \in \N\), \(d_L := \sum^L_{l=1} 2^l\) and \(V^{(j)}_{L;\tau} \sim \chi^2_{d_L}\) independent of \(X^{(j)}\) the random map from \((\R^{d_L})^n\) to \(\R\) defined by \[\label{eq:supp:clipped95Lips95stat95rescaled} \tilde{S}_{L;\tau}^{(j)}(x) = \left[\frac{1}{\sqrt{d_L}} \left(\left\| \sigma^{-1} \sqrt{n} \overline{ x} \right\|^2_2 - {V^{(j)}_{L;\tau}} \right)\right]_{-\tau}^{\tau}.\tag{93}\] Define furthermore \[\label{eq:supp:lips95constant95defined} D_\tau = \frac{\tilde{\kappa}_\alpha \log (N) \left( \sqrt{n \sqrt{d_L} \tau} \vee \sqrt{nd_L} \right)}{n \sqrt{d_L}}.\tag{94}\]

Set \(K_\tau = \lceil 2\tau D^{-1}_\tau \rceil\) and consider the set \(\cC_{L;\tau} = \cA_{L;\tau} \cap \cB_{L;\tau}\), where \[\begin{align} \label{bfknsuxm} \cA_{L;\tau} &= \left\{ (x_i) \in (\R^\infty)^n : \bigg|\| \sigma^{-1} \textstyle \sum_{i \in \cJ} \Pi_L x_i \|_2^2 - kd_L \bigg| \leq \frac{1}{8} k D_\tau n \sqrt{d_L} \;\; \forall \cJ \subset [n], |\cJ| = k \leq K_\tau \right\}, \\ \cB_{L;\tau} &= \left\{ (x_i) \in (\R^\infty)^n : \left| \langle \sigma^{-1} \Pi_L x_i, \sigma^{-1} \textstyle \sum_{k \neq i} \Pi_L x_k \rangle \right| \leq \frac{1}{8} k D_\tau n \sqrt{d_L}, \;\; \forall i=1,\dots,n \right\}. \nonumber \end{align}\tag{95}\] Lemma 18 below shows that \(X^{(j)}\) concentrates on \(\cC_{L;\tau}\) under the null hypothesis.

In Lemma 19, it is shown that \(x \mapsto S^{(j)}(x)\) is \(D_\tau\)-Lipschitz with respect to the Hamming distance on \(\cC_{L;\tau}\), with \(D_\tau\) as defined in 94 .

Lemma 20 below show that there exists a measurable function \({S}_{L;\tau}^{(j)} : \R^{d_L} \to \R\), \(D_\tau\)-Lipschitz with respect to the Hamming distance, such that \({S}_{L;\tau}^{(j)}(X^{(j)}_L) = \tilde{S}_{L;\tau}^{(j)}(X^{(j)}_L)\) whenever \(X^{(j)} \in \cC_{L;\tau}\). That is, letting \(\Psi_L : \R^{\infty} \to \R^{d_L}\) be the coordinate projection for the first \(d_L\) coordinates, the lemma allows a Lipschitz extension of the test statistic defined in 93 on \(\Psi_L \cC_{L;\tau}\) to all of \(\R^{d_L}\). The proof follows essentially the construction of McShane [69] for obtaining a Lipschitz extension with respect to the Hamming distance, but our lemma verifies in addition the Borel-measurability of the resulting map.

We follow a construction that is in essence that of McShane [69], whilst also verifying that such an extension is Borel measurable.

8.1.1 Proof of Lemma 1↩︎

Consider the transcript of Section 3.1, which we recall here as \[\label{eq:supp:transcript95private95Euclidean95norm95lips95ext95for95one95clipping} Y^{(j)}_{L;\tau} = \gamma_\tau \breve{S}_{L;\tau}^{(j)}(X^{(j)}) + W^{(j)}_\tau, \quad \text{ with } \gamma_\tau := \frac{\epsilon}{D_\tau \sqrt{ 2 \mathfrak{c} \log (2 / \delta)}},\tag{101}\] \(\mathfrak{c}>0\), \(W^{(j)}_\tau \sim N(0,1)\) independent for \(j=1,\dots,m\) and \(\tau > 0\). These transcripts are \((\epsilon/{\mathfrak{c}},\delta)\)-differentially private for any \(\epsilon > 0\) (see e.g. [67]). Define the test \[\label{eq:supp:Lipschitz95ext95test95privacy95for95one95clipping} \varphi_\tau := \text{\usefont{U}{bbm}{m}{n}1} \left\{ \frac{1}{\sqrt{m}} \underset{j=1}{\overset{m}{\sum}} Y^{(j)}_{L;\tau} \geq \left( \gamma_\tau \vee 1 \right) \kappa \right\}.\tag{102}\] We will prove the following more general version of Lemma 1.

8.1.2 Proof of Lemma 2↩︎

We start by recalling the notation, before proving a slightly more general result. Consider for a set \(\cS \subset \N\) the test \[\label{eq:supp:definition95full95test95lips95ext95privacy} T_{\text{I}} := \underset{L \in \cS,\, \tau \in \mathrm{T}_L}{\max} \text{\usefont{U}{bbm}{m}{n}1} \left\{ \frac{1}{\sqrt{m}} \underset{j=1}{\overset{m}{\sum}} Y^{(j)}_{L;\tau} \geq \kappa_\alpha \left( \frac{\epsilon}{D_\tau \sqrt{2 |\mathrm{T}_L| |\cS| \log (2 / \delta)}} \vee 1 \right) \sqrt{\log |\mathrm{T}_L||\cS|} \right\},\tag{109}\] where \[\label{eq:supp:collection95of95threshold95lips95test} \mathrm{T}_L := \left\{ 2^{-k+2} \frac{n R^2}{\sqrt{2^{L+1}}} : k=1,\dots,\lceil1+2\log_2(N R / \sigma )\rceil \right\},\tag{110}\] and \(Y^{(j)}_L = \{ Y^{(j)}_{L;\tau} : \tau \in \mathrm{T}_L \}\) is generated according to 101 with \[\gamma_\tau = \frac{\epsilon}{D_\tau \sqrt{2 |\mathrm{T}_L| |\cS| \log (2 / \delta)}}.\] By the same reasoning as in the proof of Lemma 21, the test \(T_{\text{I}}\) is \((\epsilon,\delta)\)-differentially private. We will prove the following more general version of Lemma 2.

8.2 Procedure II↩︎

Let \(\epsilon,\delta > 0\) and \(\cS \subset \N\) be given. Consider for \(L \in \cS\), \(K_L = \lceil n \epsilon^2 \wedge d_L \rceil\) and take sets \(\cJ_{lk;L} \subset [m]\) such that \(| \cJ_{lk;L} | = \lceil \frac{m K_L}{d_L} \rceil\) and each \(j \in \{1,\dots,m\}\) is in \(\cJ_{lk;L}\) for \(K_L\) different indexes \(k \in \{1,\dots,d_L\}\). For \((l,k) \in \{ l=1,\dots, L, k = 1,\dots,2^l \} =:I_L\), \(j \in \cJ_{lk;L}\), generate the transcripts according to \[\label{cgbatqkd} Y^{(j)}_{L;lk}|X^{(j)} = \gamma_L \, \underset{i=1}{\overset{n}{\sum}} \sigma^{-1} \left[ (X_{L;i}^{(j)})_{lk} \right]_{-\tau}^\tau + W^{(j)}_{L;lk}\tag{114}\] with \(\gamma_L = \frac{\epsilon}{2\sqrt{ |\cS| K_L \log(2/\delta)\tau}}\), \(\tau = \tilde{\kappa}_\alpha \sqrt{\log(N)}\) and \((W^{(j)}_{L;lk})_{j,k}\) i.i.d. standard Gaussian noise.

Define \(Y^{(j)}_L : = (Y^{(j)}_{L;lk})_{(l,k) \in I_L:j \in \cJ_{lk;L}}\) and consider the transcripts \(Y^{(j)} : = (Y^{(j)}_L)_{L \in \cS}\), for \(j=1,\ldots,m\). The lemma below shows that \(Y^{(j)}\) satisfies DP.

Consider the test given by \[\label{eq:supp:test95impure95DP95coordinate95wise95strat} T_{\text{II}} := \text{\usefont{U}{bbm}{m}{n}1}\left\{ \underset{L \in \cS}{\max} \, \frac{1}{\sqrt{d_L} \left( n \gamma_L^2 \vee 1\right)} \underset{(l,k) \in I_L}{\overset{}{\sum}} \left[ \left( \frac{1}{\sqrt{|\cJ_{lk;L}|}} \underset{j \in \cJ_{lk;L}}{\overset{}{\sum}} Y^{(j)}_{L;lk} \right)^2 - \nu_{\epsilon,L} \right] \geq \kappa_\alpha \log \log (e\vee|\cS|) \right\},\tag{116}\] with \(\nu_{\epsilon,L} := \E_0 ( |\cJ_{lk;L}|^{-1/2} \sum_{j \in \cJ_{lk;L}} Y^{(j)}_{L;lk} )^2\).

8.3 Procedure III↩︎

Let \(\cS \subset \N\) and consider for \(L \in \N\), \(d_L := \sum_{l=1}^L 2^l\), \(K_L := \lceil n \epsilon^2 \wedge 2^L \rceil\), \(I_L:= \{ (l,k) : l=1,\dots, \lceil \log_2(K_L) \rceil, \, k=1,\dots,2^l \}\) and \(j=1,\dots,m\) the transcripts \[\label{lbnzopfa} Y^{(j)}_{lk} | (X^{(j)},U_L) = \gamma_L \, \underset{i=1}{\overset{n}{\sum}} [ (U_L X_{L;i}^{(j)})_{lk} ]^\tau_{-\tau} + W^{(j)}_{lk},\tag{122}\] with \(\gamma_L = \frac{\epsilon}{2\sqrt{K_L |\cS| \log(2 / \delta)\tau}}\), \(\tau = \tilde{\kappa}_\alpha \sqrt{\log(N)}\), \(U_L\) a \(d_L\)-by-\(d_L\) random rotation drawn uniformly (i.e. from the Haar measure on the special orthogonal group in \(\R^{d_L \times d_L}\)) and \((W^{(j)}_{lk})_{j,l,k}\) i.i.d. centered standard Gaussian noise. The following lemma shows that the transcript is \((\epsilon,\delta)\)-differentially private.

Based on these transcripts, one can compute \[\label{iyxtmkgh} T_{\text{III}} = \text{\usefont{U}{bbm}{m}{n}1}\left\{ \underset{L \in \cL}{\max} \; \frac{1}{\sqrt{K_L}\left(n \gamma_L^2 \vee 1\right)} \underset{(l,k) \in I_L}{\overset{}{\sum}} \left[ \left( \frac{1}{\sqrt{m}} \underset{j =1}{\overset{m}{\sum}} Y^{(j)}_{lk} \right)^2 - \nu_{L} \right] \geq \kappa_\alpha \log \log (e\vee|\cS|) \right\},\tag{123}\] where \(\nu_{L} = n\gamma_L^2 + 1\). The following lemma establishes the Type I and Type II error probability guarantees for the above test.

8.4 Proofs of the theorems in Section 2 and Theorem 4↩︎

The proofs of Theorems 2 and 1 in Section 2 are direct consequences of Theorem 4 and 5. To see this, note that for any sequences \(m_N \equiv m\), \(n_N \equiv N/m\), \(\sigma_N \equiv \sigma\), \(\epsilon_N \equiv \epsilon\) and \(\delta_N \equiv \delta\), Theorem 5 and Theorem 4 can be applied with an arbitrarily slow decreasing sequence \(\alpha_N \to 0\) or \(\alpha_N \to 1\) in order to obtain the desired convergence of the minimax risk.

Theorem 4 and Theorem 3 are consequences the lemmas proven earlier in the section. Below, we tie together the results of these lemmas to obtain both theorems.

9 Addendum to the main results of Section 2↩︎

In this section, we provide additional discussion on the minimax testing rate under privacy constraints, presented in Section 2.

We first consider the case of local randomness protocols, where the minimax rate is derived in Theorem 2. The minimax separation rate satisfies (up to logarithmic factors) the relationship: \[\rho^2 \asymp \left(\frac{\sigma^{2}}{mn}\right)^{\frac{2{s}}{2{s}+1/2}} + \left(\frac{\sigma^2}{m n^{2} \epsilon^2} \right)^{\frac{2{s}}{2{s}+3/2}} \wedge \left( \left(\frac{\sigma^2}{\sqrt{m} n^{} \sqrt{1 \wedge n \epsilon^2}} \right)^{\frac{2{s}}{2{s}+1/2}} + \left( \frac{\sigma^2}{mn^2 \epsilon^2} \right) \right).\]

We can find the dominant term in the above relationship for different values of \(\epsilon\). For \(s > 1/4\), this yields that the minimax rate is given by

\[\begin{align} \label{eq:nonparametric95local95randomness95rate95privacy} \rho^2 \asymp \begin{cases} (mn / \sigma^2)^{-\frac{2s}{2s+1/2}} &\text{ if } \epsilon \geq \sigma^{-\frac{2}{4s+1}} m^{\frac{1}{4s+1}} n^{\frac{1/2-2s}{4s+1}}, \\ (m n^{2} \epsilon^2 / \sigma^2 )^{-\frac{2s}{2s+3/2}} &\text{ if } \sigma^{-\frac{2}{4s+1}} m^{\frac{1/4-s}{4s+1}} n^{\frac{1/2-2s}{4s+1}} \leq \epsilon < \sigma^{-\frac{2}{4s+1}} m^{\frac{1}{4s+1}} n^{\frac{1/2-2s}{4s+1}} \text{ and } \epsilon \geq n^{-1/2}, \\ (m n^{2} \epsilon^2 / \sigma^2 )^{-\frac{2s}{2s+3/2}} &\text{ if } \sigma^{-\frac{4}{4s-1}} m^{-\frac{1}{2}} n^{\frac{5/2-2s}{4s-1}} \leq \epsilon < n^{-1/2}, \\ (\sqrt{m} n^{} / \sigma^2 )^{-\frac{2s}{2s+1/2}} &\text{ if } n^{-1/2} \leq \epsilon < \sigma^{-\frac{2}{4s+1}} m^{\frac{1/4-s}{4s+1}} n^{\frac{1/2-2s}{4s+1}}, \\ (\sqrt{m} n^{3/2} \epsilon / \sigma^2 )^{-\frac{2s}{2s+1/2}} &\text{ if } \sigma^{ \frac{1}{2s+1}} m^{-\frac{1}{2}} n^{-\frac{1+s}{2s+1}} \leq \epsilon < \sigma^{-\frac{4}{4s-1}} m^{-\frac{1}{2}} n^{\frac{5/2-2s}{4s-1}} \text{ and } \epsilon < n^{-1/2}, \\ (mn^2 \epsilon^2 / \sigma^2)^{-1} &\text{ if } \epsilon < \sigma^{\frac{1}{2s+1}} m^{-\frac{1}{2}} n^{-\frac{1+s}{2s+1}}. \end{cases} \end{align}\tag{134}\]

Whenever \(s \leq 1/4\), the first two cases in the above display become vacuous for \(\epsilon \lesssim 1\), since \(mn \to \infty\). Furthermore, the condition \[\left(\frac{\sigma^2}{m n^{2} \epsilon^2} \right)^{\frac{2{s}}{2{s}+3/2}} \asymp \left(\frac{\sigma^2}{\sqrt{m} n^{3/2} \epsilon} \right)^{\frac{2{s}}{2{s}+1/2}} \iff \epsilon^{\frac{2s-1/2}{2s+3/2}} \asymp \sigma^{-\frac{1}{2s+3/2}} m^{\frac{1}{2s+3/2}} n^{\frac{5/4-s}{2s+3/2}},\] cannot be satisfied when \(s \leq 1/4\), \(\epsilon \gtrsim (mn)^{-1}\) and \(\sigma^2 = O(1)\). Consequently, whenever \(s \leq 1/4\), the minimax rate simplifies to \[\begin{align} \label{eq:nonparametric95local95randomness95rate95privacy95small95s} \rho^2 \asymp \begin{cases} (\sqrt{m} n^{} / \sigma^2 )^{-\frac{2s}{2s+1/2}} &\text{ if } \epsilon \geq n^{-1/2}, \\ (\sqrt{m} n^{3/2} \epsilon / \sigma^2 )^{-\frac{2s}{2s+1/2}} &\text{ if } \sigma^{ \frac{2}{4s+1}} m^{-\frac{1}{2}} n^{-\frac{1+s}{2s+1}} \leq \epsilon < n^{-1/2}, \\ ( mn^2 \epsilon^2 / \sigma^2 )^{-1} &\text{ if } \epsilon < \sigma^{ \frac{2}{4s+1}} m^{-\frac{1}{2}} n^{-\frac{1+s}{2s+1}}. \end{cases} \end{align}\tag{135}\] That is, the minimax rates corresponding to the high privacy-budget regimes cannot be attained for any value of \(\epsilon\) when \(s \leq 1/4\).

Next, we consider the case of shared randomness protocols, where the minimax rate is derived in Theorem 1. The minimax separation rate satisfies (up to logarithmic factors) the relationship: \[\rho^2 \asymp \left(\frac{\sigma^2}{mn}\right)^{\frac{2{s}}{2{s}+1/2}} + \left(\frac{\sigma^2}{m n^{3/2} \epsilon \sqrt{1 \wedge n \epsilon^2} } \right)^{\frac{2{s}}{2{s}+1}} \wedge \left( \left(\frac{\sigma^2}{\sqrt{m} n^{} \sqrt{1 \wedge n \epsilon^2}} \right)^{\frac{2{s}}{2{s}+1/2}} + \frac{\sigma^2}{mn^2 \epsilon^2} \right).\]

Finding the dominant term in the above relationship, we obtain that the minimax rate for shared randomness protocols is given by

\[\begin{align} \label{eq:nonparametric95shared95randomness95rate95privacy} \rho^2 \asymp \begin{cases} (mn/\sigma^2)^{-\frac{2{s}}{2{s}+1/2}} &\text{ if } \epsilon \geq \sigma^{-\frac{2}{4s+1}} m^{\frac{1}{4{s}+1}} n^{\frac{1/2-2{s}}{4{s}+1}}, \\ (m n^{3/2} \epsilon /\sigma^2 )^{-\frac{2{s}}{2{s}+1}} &\text{ if } \sigma^{-\frac{2}{4s+1}} m^{-\frac{2{s}}{4{s}+1}} n^{\frac{1/2-2{s}}{4{s}+1}} \leq \epsilon < \sigma^{-\frac{2}{4s+1}} m^{\frac{1}{4{s}+1}} n^{\frac{1/2-2{s}}{4{s}+1}}, \text{ and } \epsilon \geq n^{-1/2},\\ (m n^{2} \epsilon^2 /\sigma^2 )^{-\frac{2{s}}{2{s}+1}} &\text{ if } \sigma^{-\frac{1}{2s}} m^{-\frac{1}{2}} n^{\frac{1-2{s}}{4{s}}} \leq \epsilon < n^{-1/2}, \\ (\sqrt{m} n^{} /\sigma^2 )^{-\frac{2{s}}{2{s}+1/2}} &\text{ if } n^{-1/2} \leq \epsilon < \sigma^{-\frac{2}{4s+1}} m^{-\frac{2{s}}{4{s}+1}} n^{\frac{1/2-2{s}}{4{s}+1}}, \\ (\sqrt{m} n^{3/2} \epsilon /\sigma^2 )^{-\frac{2{s}}{2{s}+1/2}} &\text{ if } \sigma^{\frac{1}{2s+1}} m^{-\frac{1}{2}} n^{-\frac{1+s}{2{s}+1}} \leq \epsilon < \sigma^{-\frac{1}{2s}} m^{-\frac{1}{2}} n^{\frac{1-2{s}}{4{s}}} \text{ and } \epsilon < n^{-1/2}, \\ (mn^2 \epsilon^2 /\sigma^2 )^{-1} &\text{ if } \epsilon < \sigma^{\frac{1}{2s+1}} m^{-\frac{1}{2}} n^{-\frac{1+s}{2{s}+1}}. \end{cases} \end{align}\tag{136}\]

Interestingly, even when \(s \leq 1/4\), the high privacy-budget regimes occur for shared randomness protocols for some large enough value of \(\epsilon\). This is in contrast to the case of local randomness protocols, where the minimax rates corresponding to the high privacy-budget regimes cannot be attained for any value of \(\epsilon\) when \(s \leq 1/4\).

In Figure [fig:nonpar_testing_large_m] below, we illustrate how the cost of privacy effectively increases the more data is distributed across multiple servers. In particular, we consider the case of \(N=16\) observations, \(m=8\) servers with each \(n=2\) observations. Even though the total number of observations is the same, comparison with Figure 2 shows that the separation rate in the more distributed setting (\(m=8\)) is much larger for any value of \(\epsilon\).

10 Auxiliary lemmas↩︎

10.1 General privacy related lemmas↩︎

A random variable \(V\) is called \(\nu\)-sub-gaussian if \[\label{eq:def:subgaus} \P( |V| \geq t ) \leq 2 e^{- t^2/\nu^2}, \; \text{ for all } t>0.\tag{137}\] It is well known (see e.g. [76]) that if \(\E V = 0\), the above inequality holds if and only if \[\E e^{t V} \leq e^{C \nu^2 t^2}, \; \text{ for all } t\geq 0,\] for a constant \(C> 0\). A random variable \(V\) is called \(\nu\)-sub-exponential if \[\label{eq:def:subexp} \P( |V| \geq t ) \leq 2 e^{- t/\nu}, \; \text{ for all } t\geq0.\tag{138}\] If \(\E V = 0\), the above inequality holds if and only if \(\E e^{t V} \leq e^{C \nu^2 t^2}\) for all \(0 \leq t \leq 1/(c\nu)\), with constants \(c,C > 0\).

The following lemma shows that clipping symmetric, mean zero random variables preserves sub-gaussianity and sub-exponentiality.

The next lemma gives a lower bound on the expectation of a clipped random variable that is symmetric around a real number \(\mu > 0\).

10.2 General auxiliary lemmas↩︎

The following lemmas are well known but included for completeness.

The following lemma is a standard tail bound for the maximum of sub-gaussian (resp. sub-exponential) random variables that is used to control the type I error of the adaptive tests.

Consider the following formal definition of coupling.

Lemma 32 below is a well known result showing that, for random variables \(X\) and \(\tilde{X}\) defined on a Polish space, small total variation distance between their corresponding laws guarantees the existence of a coupling such that they are equal with high probability.

For a proof, see e.g. Section 8.3 in [81].

The following lemma is well known and included for completeness.

The following lemma bounds the maximum of a possibly correlated Gaussian random vector.

The next lemma is a standard bound for the KL-divergence, see for instance Lemma 2.7 of [82].

The following lemma is a standard concentration result for chi-square random variables, and is included for completeness.

11 Appendix on Besov norms in sequence space↩︎

In this section we briefly introduce Besov spaces as subspaces of \(\ell_2(\N)\) and collect some properties used in the paper.

For \(s \in \R\), \(1 \leq p \leq \infty\) and \(1 \leq q \leq \infty\), we define the Besov norm for \(f \in \ell_2(\N)\) as \[\| f\|_{\cB^{s}_{p,q}} := \begin{cases} \left( \underset{l=1}{\overset{\infty}{\sum}} \left(2^{l({s}+1/2-1/p)} \left\| (f_{lk})_{k=1}^{2^l} \right\|_p\right)^{q}\right)^{1/q} &\text{ for } 1 \leq q < \infty, \\ \; \underset{l\geq 1}{\sup} \; 2^{l({s}+1/2-1/p)} \left\| (f_{lk})_{k=1}^{2^l} \right\|_p &\text{ for } q = \infty. \end{cases}\] This definition of the Besov norm is equivalent to the Besov norm as typically defined on a function space when considering the wavelet transform of a function in \(L_2[0,1]\), \[\begin{align} f=\sum_{j=j_0}^{\infty}\sum_{k=0}^{2^{j}-1}f_{jk}\psi_{jk}, \end{align}\] where \[\begin{align} \big\{ \phi_{j_0m},\psi_{jk}:\, m\in\{0,\ldots,2^{j_0}-1\},\quad j> j_0,\quad k\in\{0,\ldots,2^{j}-1\} \big\}, \end{align}\] are the orthogonal wavelet basis functions, for father \(\phi(.)\) and mother \(\psi(.)\) wavelets with \(N\) vanishing moments and bounded support on \([0,2N-1]\) and \([-N+1,N]\), respectively, following e.g. the construction of Cohen, Daubechies and Vial [83], [84], with \(N > s\). The Besov norm on the function space is then equivalent to the one defined above for the wavelet coefficients \((f_{jk})_{j\geq j_0, k \in \{0,...,2^{j}-1\} }\). See e.g. Chapter 4 in [68] for details.

Let \(\cB^s_{p,q}(R) \subset \ell_2(\N)\) denote the Besov ball of radius \(R\). The following lemmas are standard results, for which we provide a proof for completeness.

Using a similar proof, one obtains also the following lemma, see e.g. Chapter 9 in [85].

References↩︎