1 Introduction↩︎

Many fundamental distribution testing tasks—uniformity testing being the canonical example—become infeasible in high dimensional settings such as the Boolean hypercube \(\bn\), requiring exponentially many samples in the dimension [1], [2]. A central theme in the field has therefore been to identify structured settings that admit efficient testers: examples include Bayesian networks [3], [4], Markov random fields [5], [6], and structured truncations [7], [8].

Among such structural assumptions, one of the most extensively studied is monotonicity, the distributional analogue of the classical Boolean function property.¹ In the Boolean function setting, monotonicity has played a central role in sublinear algorithms for nearly three decades: it was among the first properties studied in Boolean function testing and continues to be actively investigated to this day [9]–[18]. In the distributional setting, monotonicity has similarly been studied in depth, leading to tight upper and lower bounds for tasks such as uniformity testing and property testing under various access models [19]–[27].

A closely related property in the Boolean function setting is unateness. Informally, a Boolean function is unate if each coordinate is either always non-decreasing or always non-increasing. The problem of testing unateness of Boolean functions was introduced alongside monotonicity testing in [10], and has since received considerable attention [28]–[33]. Both monotonicity and unateness are fundamental structural properties that arise naturally across many domains, for example in social choice (where we can view a Boolean function \(f\) as a voting rule), economics, learning theory, and circuit design.

Despite extensive work on unate functions, the analogous notion for distributions has, to the best of our knowledge, not been studied. In this work, we initiate the study of unate distributions over \(\bn\). The motivation for this is twofold:

• The study of monotone distributions has a well-developed literature precisely because monotonicity is a natural structural constraint arising in settings ranging from social choice to learning theory. Unateness is a strict and natural generalization—it captures the same “directional” structure without fixing a canonical orientation—and we believe its study for distributions will prove equally fruitful.

• Additionally, unate distributions, which we define shortly, form a broad and natural family of probability distributions. For example, every unate function \(f\) induces a unate distribution (the uniform distribution over \(f^{-1}(1))\), and the class of unate functions includes families such as halfspaces and read-once decision lists, which need not be monotone. Beyond this connection to functions, every product distribution over \(\bn\) is unate.

Finally, as this work demonstrates, unate distributions pose challenges that cannot be addressed by simply reducing to the monotone setting. Even for basic tasks such as uniformity testing, the sample complexity changes, and more broadly, new ideas are required to design and analyze optimal testers for this richer class of distributions.

1.1 Our Results↩︎

We start by formally defining unate distributions over \(\bits^n\):

Unate distributions immediately inherit many of the algorithmic challenges and lower bounds known from the monotone distribution setting. This includes, for example, the exponential sample lower bounds for tasks such as entropy estimation and independence testing [20]. In this work, we give efficient algorithms as well as lower bounds for two basic problems:

• Uniformity testing of unate distributions; and

• Testing unateness of an unknown distribution in the subcube conditional model introduced by Canonne, Ron, and Servedio [34] and Chakraborty, Fischer, Goldhirsh, and Matsliah [35].

In the subcube conditional model for distributions over \(\bn\), an algorithm can query \(\calD\) with a subcube \(\rho \in \{\pm1, \ast\}^n\) and receive an independent sample \(\bx\sim\calD\) conditioned on \(\bx_i = \rho_i\) for all \(i\) where \(\rho_i \neq \ast\). This model provides a distributional analogue of the “membership query” from learning theory and property testing of Boolean functions, and has received considerable attention in recent years.

We note that for both of the problems we consider, an easy argument using the Chernoff bound together with a union bound over all \(\sigma \in \bn\) (cf. 1) allow us to reduce to the corresponding problems for monotone distributions with a multiplicative \(O(n)\) sample/subcube query overhead. Our main algorithmic results improve on this naive approach for each task; we defer a technical overview of our results to 1.2 and survey related work in 1.3.

1.1.1 Uniformity Testing of Unate Distributions↩︎

Throughout, we write \(\calU = \calU_n\) for the uniform distribution over \(\bn\). Our first result gives an efficient uniformity tester for high-dimensional distributions under the promise of unateness:

Here \(\mathrm{d}_{\mathrm{TV}}(\cdot)\) refers to the total variation or statistical distance (2.2). This result should be contrasted with the \(\wt{O}(n/\eps^2)\) bound for uniformity testing of monotone distributions due to Rubinfeld and Servedio [20].² At a high level, moving from monotone to unate distributions introduces an unknown orientation vector \(\sigma\) (cf. 1); any naive strategy that first learns \(\sigma\) and then runs the [20] tester provably incurs an \(\Omega(n^2)\) sample overhead. Our algorithm bypasses this bottleneck by never learning \(\sigma\) explicitly. Instead, we introduce a weak-orientation learning framework whose errors are provably weakly correlated across coordinates. This allows a small average bias to be amplified into a global signal using only \(\widetilde{O}(n^{3/2})\) samples. We believe this structural result on limited correlations among marginals of unate distributions is of independent interest. We complement [thm:our-unif-test] with a matching lower bound:

Our proof of [thm:our-unif-lb] extends the “monotone decomposition method” of Rubinfeld and Servedio [20] to the setting of unate distributions; see 1.2 for more details.

1.1.2 Testing Unateness of Distributions↩︎

We now turn to the problem of testing whether an unknown distribution over \(\bn\) is itself unate. In the standard access model where one receives i.i.d. samples from the unknown distribution being tester, this task is intractable: even for the simpler case of monotonicity, classical “birthday paradox” arguments imply that exponential-in-\(n\) sample complexity is unavoidable [24], [25]. It is therefore necessary to consider stronger access models to obtain meaningful algorithms.

Motivated by this, Chakrabarty, Chen, Ristic, Seshadhri, and Waingarten [27] studied monotonicity testing in the subcube conditional model, where the tester can query samples conditioned on arbitrary coordinate restrictions. Building on their results, we give an efficient algorithm for testing unateness in the same model.

We note that the algorithm of [thm:our-subcube-UB] also works in the weaker coordinate oracle model of Blanca et al. [37] where queries are only made on one-dimensional subcubes. We complement [thm:our-subcube-UB] with the following lower bound:

We note that all prior lower bounds in the subcube model are based on product distributions as hard instances. Since every product distribution is trivially unate, these techniques cannot be applied to this setting. To the best of our knowledge, ours is the first lower bound that breaks this barrier; we return to this point in 1.4.

1.2 Main Ideas↩︎

We give a brief technical overview of our results. Although both of our upper bounds end up with the same asymptotic sample complexity of \(\wt{O}(n^{3/2}/\varepsilon^2)\), that the ideas underlying each of them are quite different.

1.2.1 Testing Uniformity of Unate Distributions↩︎

1.2.1.1 Upper Bound.

A natural first attempt is to adapt the Rubinfeld–Servedio [20] uniformity tester for monotone distributions to the unate setting. The idea would be to first learn the hidden “orientation vector” \(\sigma^\ast \in \bits^n\) (cf. 1) such that the reoriented distribution \(\calD^{\sigma^\ast}\), where \(\bx\sim\calD^{\sigma^\ast}\) is obtained by drawing \(\by \sim \calD\) and setting \(\bx_i = \sigma^\ast_i \cdot \by_i\), is monotone. Since total variation distance is preserved under bijections, \(\mathrm{d}_{\mathrm{TV}}(\calD, \calU) = \mathrm{d}_{\mathrm{TV}}(\calD^{\sigma^\ast}, \calU)\). Thus, if \(\sigma^\ast\) were known, one could directly apply the \(O(n/\varepsilon^2)\)-sample uniformity tester of [20], [21].

However, exactly recovering \(\sigma^\ast\) can be prohibitively expensive. Consider, for example, a product distribution where each coordinate has mean \(\pm \Theta(1/n)\). Such a distribution is \(\Omega(1)\)-far from uniform, but distinguishing \(\E[x_i]=0\) from \(\E[x_i]=\pm \Theta(1/n)\) for each coordinate requires \(\Omega(n^2)\) samples by Chernoff bounds. This naive approach of fully learning the orientation thus fails to give the desired sample complexity of \(\wt{O}(n^{3/2})\).

Our algorithm circumvents this barrier by avoiding the need to learn \(\sigma^\ast\) exactly. Instead, we estimate a weakly correlated proxy for \(\sigma^\ast\) using only \(\wt{O}(n^{3/2}/\varepsilon^2)\) samples. The key technical step (2; which may be of independent interest) shows that for unate distributions, the coordinate-wise sign estimates cannot exhibit strong correlations: indeed, their covariances decay at rate \(O(1/\sqrt{m})\) after \(m\) samples. This weak dependence is sufficient to amplify a small average bias across coordinates into a global signal, allowing us to test uniformity with \(\wt{O}(n^{3/2})\) samples.

1.2.1.2 Lower Bound.

Our lower bound builds on the “monotone decomposition” method of Rubinfeld and Servedio [20], which we briefly recall. Concretely, one starts from a (slightly biased) monotone product distribution \(\calD_\tau\), which admits a representation as a convex combination of uniform distributions on monotone subcubes (the “decomposition”). Using this representation, we define a random distribution \(\bq\) by sampling \(T\) such subcubes and averaging their uniform measures, and show that for appropriate parameters \(\bq\) is a monotone distribution that is (with high probability) very far from uniform even though it is indistinguishable from \(\calD_\tau\) with \(\ll n\) samples.

To lift this construction from monotone to unate distributions, we apply a random orientation: we draw a uniformly random \(\boldsymbol{\sigma}\in\{\pm1\}^n\) and output \(\bq' := \bq^{\boldsymbol{\sigma}}\) which is the distribution \(\bq\) but with output bits flipped according to \(\boldsymbol{\sigma}\) (see [notation:D-sigma] for a precise definition). This preserves the distance from uniformity since total variation distance is invariant under bijections, while hiding the global direction of bias and ensuring that \(\bq'\) is a valid hard instance in the unate class. The key point is that although \(\bq'\) is far from uniform with high probability, it is information-theoretically difficult to distinguish \(\bq'\) from \(U\) using fewer than \(\widetilde{\Omega}(n^{3/2})\) samples. The proof proceeds in two steps:

• First, a coupling argument shows that \(m\) samples from \(\bq'\) are close (in total variation distance) to \(m\) samples from the randomly oriented biased product distribution \(\calD_\tau^{\boldsymbol{\sigma}}\). (We note that this step holds for every \(m\).)

• Second, averaging over the random orientation \(\boldsymbol{\sigma}\) forces strong cancellations, and a \(\chi^2\)-divergence calculation on one-dimensional marginals shows that \((\calD_\tau^{\boldsymbol{\sigma}})^{\otimes m}\) itself is close to \(U^{\otimes m}\) whenever \(m \ll n^{3/2}\).

Putting these together yields our matching lower bound, up to polylogarithmic factors.

1.2.2 Testing Unate Distributions via Subcube Queries↩︎

1.2.2.1 Upper Bound.

For the task of testing whether an unknown distribution is itself unate, we work in the subcube conditional model, following the recent work of Chakrabarty et al. [27]. At a high level, our algorithm adapts the classical edge tester for Boolean unateness [10] to the distributional setting. The central tool is a structural lemma of [27], based on a real-valued “directed” generalization of an isoperimetric inequality due to Talagrand [38], which controls the “edge bias” of monotone distributions. We refer the reader to 5 for a precise statement. Using this lemma, we show that if \(\calD\) is \(\varepsilon\)-far from unate, then there exists some coordinate \(i\) that simultaneously witnesses both “monotone” and “anti-monotone” violations. This can then be detected by making \(\wt{O}(n^{3/2})\) subcube edge queries; the analysis requires an elementary but careful calculation.

1.2.2.2 Lower Bound.

On the lower-bound side, we reduce Boolean unateness testing to distributional unateness. Given a Boolean function \(f:\bn\to\{0,1\}\), let \(D_f\) be the uniform distribution on \(f^{-1}(1) \sse \bn\). Our reduction is based on two key facts:

• First, we show that (i) if \(f:\bn\to\zo\) is unate, then so is \(D_f\), and (ii) conversely, if \(f\) is \(\eps\)-far from unate (in Hamming distance), \(D_f\) is \(\Omega(\eps)\)-far from unate (in total variation distance).

• Second, we note that membership query access to \(f\) allows us to simulate unconditional samples from \(D_f\) and samples from \(D_f\) restricted to \(d\)-dimensional subcubes (with \(2^d\) queries per restriction).

Combining these observations with the \(\wt{\Omega}(n^{2/3})\) query lower bound for Boolean unateness testing [30] yields [thm:subcube-lower-bound].

1.3 Related Work↩︎

Monotonicity of Boolean functions is among the most extensively studied properties in sublinear algorithms; we will not attempt to survey the very large body of results here and instead refer the reader to the comprehensive discussion from [27]. The problem of unateness testing of Boolean functions was introduced alongside that of monotonicity testing in [10], and a sequence of works [10], [28]–[32] have pinned down its exact query complexity: \(\wt{\Theta}(n^{2/3})\) queries are both necessary and sufficient to test unateness of Boolean functions.

A number of natural distribution testing tasks have exponential sample complexity in high-dimensional settings. This includes uniformity testing over \(\bits^n\); see the surveys [1], [2] for more discussion on this. In order to overcome these lower bounds, many works either make structural assumptions on the distribution being tested, or assume stronger access models to the distribution. Examples of the former include monotonicity [20], [21], Bayesian networks [3], [4], Markov random fields [5], [6], various classes of structured truncations [7], [8], [39]; see also Section 7 of [1].

The subcube conditioning model, introduced by [34], [35], [40], takes the other route of assuming stronger access to the distribution being tested. This model has received much attention in recent years [27], [36], [37], [41]–[44], and has also found applications beyond distribution testing to problems in learning theory [26], [41]. There has also been a nascent line of work on using the subcube conditioning model to make high-dimensional distribution testing practical [45], [46].

The works most relevant to our results are [20] and [27]. Rubinfeld and Servedio [20] establish an essentially tight bound of \(\wt{\Theta}(n)\) samples for the problem of testing uniformity of an unknown monotone distribution, whereas Charkabarty et al. [27] give \(\wt{\Theta}(n)\)-query upper and lower bounds for testing monotonicity of an unknown distribution in the subcube model. Both our results—for uniformity testing as well as unateness testing—rely on ingredients going into the analyses of [20], [27] respectively.

1.4 Discussion↩︎

Our results raise a number of intriguing questions for further study; we highlight two compelling directions below.

1.4.0.1 Lower Bounds for Unateness Testing with Subcube Queries.

Recall that [thm:subcube-lower-bound] gives a \(\wt{\Omega}(n^{2/3})\) query lower bound against algorithms that make \(O(1)\)-dimensional subcube queries. At present, all known lower-bounds in the subcube conditional model [27], [36], [41] construct hard instances that are product distributions, which are amenable to moment-matching techniques [27], [41]. However, since product distributions are automatically unate, none of these techniques can be lifted the unateness setting. Improving on [thm:subcube-lower-bound] is thus likely to lead to new insights and techniques for proving lower bounds in the subcube conditional model.

1.4.0.2 \(k\)-Monotone Distributions.

Finally, one can consider distributional analogues of other structural generalizations of monotonicity. A natural candidate is the class of \(k\)-monotone distributions, where the distribution’s mass function changes direction at most \(k\) times along any monotone path from \(-1^n\) to \(1^n\). The class of \(k\)-monotone functions has already been studied in the Boolean function setting [47]–[49], and \(k\)-monotone distributions could provide another structured setting for distribution testing beyond monotonicity.

2 Preliminaries↩︎

We use boldfaced letters such as (e.g. \(\bx \sim \bits^n\)) to denote random variables. Unless explicitly stated otherwise, all probabilities and expectations will be with respect to the uniform distribution. Throughout, we will write \(\calU_n\) for the uniform distribution over \(\bn\) and when the dimension \(n\) is clear from context we will simply write \(\calU\) instead.

For a distribution \(\calD\), it will be convenient to write \(\calD^{\otimes m}\) for the distribution of \(m\) independent draws from \(\calD\). We will use the following notation throughout:

2.1 The Berry–Esseen Theorem↩︎

We will write \(N(0, I_d)\) for the \(d\)-dimensional standard Gaussian distribution, where \(I_d\) denotes the \(d\times d\) identity matrix. We recall the (multi-dimensional) Berry–Esseen theorem (which will be used to prove 2):

2.2 Distance Metrics Between Probability Distributions↩︎

We will identify a distribution \(\calD\) over a discrete domain \(\Omega\) with its density function \(\calD : \Omega \to [0,1]\). Recall that for two distributions \(\calD_1\), \(\calD_2\) over a discrete domain \(\Omega\), the total variation (or statistical) distance between \(\calD_1\) and \(\calD_2\) is \[\mathrm{d}_{\mathrm{TV}}(\calD_1,\calD_2) = \frac{1}{2}\sum_{x\in\Omega} \abs{\calD_1(x) - \calD_2(x)}\,.\] We will frequently make use of the fact that total variation distance is invariant under bijections.

We also recall the Kullback–Leibler (KL) and \(\chi^2\)-divergences: \[\mathrm{d}_{\mathrm{KL}}(\calD_1,\calD_2) = \sum_{x\in\Omega} \calD_1(x)\log\frac{\calD_1(x)}{\calD_2(x)} \qquad\text{and}\qquad \mathrm{d}_{\mathrm{\chi^2}}(\calD_1,\calD_2) = \sum_{x\in\Omega} \frac{\pbra{\calD_1(x) - \calD_2(x)}^2}{\calD_2(x)}\] respectively. The following relationships are standard: \[\label{eq:distance-relationships} \mathrm{d}_{\mathrm{TV}}(\calD_1, \calD_2) \leq \sqrt{\frac{1}{2}\mathrm{d}_{\mathrm{KL}}(\calD_1,\calD_2)} \leq \sqrt{\frac{1}{2}\log\pbra{1 + \mathrm{d}_{\mathrm{\chi^2}}(\calD_1,\calD_2)}}\,.\tag{1}\]

We will use the following version of the data processing inequality:

3 Testing Uniformity of Unate Distributions↩︎

We will prove [thm:our-unif-test,thm:our-unif-lb] in this section, starting with the former.

3.1 Upper Bound↩︎

We first recall the principal technical lemma of [20]’s uniformity tester for monotone distributions:

We now turn to our uniformity tester for unate distributions. First, note that if \(\calD\) is a unate distribution, then there exists some \(\sigma^\ast \in \bn\) such that \(\calD^{\sigma^\ast}\) is a monotone distribution. In particular, note that we may take \(\sigma^\ast_i = \sign(\Ex_{\bx \sim \calD}[\bx_i])\). This suggests a natural algorithm: estimate \(\sigma^\ast\) by drawing \(m\) samples \(\x{1}, \x{2}, \ldots, \x{m}\) from \(\calD\) and setting \[{\boldsymbol{\sigma}}_i := \sign\pbra{\sum_{j=1}^m \x{j}_i}\,,\] and then run the [20] uniformity tester on the monotone distribution \(\calD^{{\boldsymbol{\sigma}}}\). Indeed, since \[\mathrm{d}_{\mathrm{TV}}(\calD^{{\boldsymbol{\sigma}}}, \calU) = \mathrm{d}_{\mathrm{TV}}(\calD^{{\boldsymbol{\sigma}}}, \calU^{\boldsymbol{\sigma}}) = \mathrm{d}_{\mathrm{TV}}(\calD, \calU),\] replacing \(\calD\) with \(\calD^{\boldsymbol{\sigma}}\) preserves the uniformity (or distance from uniformity) of the distribution.

However, learning the whole sign vector \(\sigma^\ast\) can be too expensive. In particular, while 1 ensures that \(\sumi \Ex[\bx_i]\) is large, it gives no guarantee on the magnitude of each individual \(\Ex[\bx_i]\). In particular, note that distinguishing \(\Ex[\bx_i]=0\) (which corresponds to the uniform distribution) from \(\Ex[\bx_i]=\pm\Theta(1/n)\) requires \(\Theta(n^2)\) samples per coordinate by standard Chernoff lower bounds. We bypass this obstacle by not insisting on the exact orientation and instead weakly learning the sign vector \(\sigma^\ast\).

3.1.1 Warm-Up: A Sub-Quadratic Tester in a Special Case↩︎

As a warm-up, we show how to obtain a sub-quadratic tester in the hard instance just described above, where naively learning \(\sigma^\ast\) requires \(\Omega(n^2)\) queries. It will be convenient to write \[\mu_i \mathrel{\vcenter{:}}= \Ex_{\bx\sim\calD}[\bx_i]\,.\] We make one simplifying assumption for now: \(\mu_i = \frac{1}{n}\) holds for every \(i \in [n]\), i.e., the unate distribution \(\calD\) is in fact monotone, and each coordinate has the same bias of \(\Theta(1/n)\) towards \(+1\).

Let \(p > 0\) be a parameter that we will set later. By the assumption that \(\mu_i = \frac{1}{n}\), it can be verified that \(m = \Theta(n^2p^2)\) samples suffice for the “orientation step” to produce random signs \(\boldsymbol{\sigma}_1, \dots, \boldsymbol{\sigma}_n \in \bits\) with the promise that \[\Ex[\boldsymbol{\sigma}_i] \geq p~\text{for all}~i\in[n]\,.\] Equivalently, we correctly deduce that \(\sigma^*_i = +1\) with probability \(1/2 + \Omega(p)\), which is slightly better than a random guess.

Writing \(\bX \mathrel{\vcenter{:}}= \frac{1}{n} \sumi \boldsymbol{\sigma}_i \in [-1,1]\), note that \(\E[\bX] \geq p\). Applying Markov’s inequality to the non-negative random variable \(1-\bX\) gives \[\Prx\sbra{\bX \leq \frac{p}{2}} = \Pr\sbra{1 - \bX \geq 1-\frac{p}{2}} \leq \frac{\Ex\sbra{1-\bX}}{1-\frac{p}{2}} \leq \frac{1-p}{1-\frac{p}{2}} \leq 1-\Omega(p)\,.\]

In other words, the event \(\frac{1}{n} \sumi \boldsymbol{\sigma}_i \geq \frac{p}{2}\) holds with probability \(\Omega(p)\). Repeating this “orientation step” independently \(O(1/p)\) times ensures that with constant probability, at least one draw satisfies \(\bX \geq p/2\). Then, we note that, conditioning on the realization of \(\boldsymbol{\sigma}\in \bits^n\), the \(\boldsymbol{\sigma}\)-weighted Hamming weight \(\sum_{i=1}^{n}\boldsymbol{\sigma}_i\bx_i\) for \(\bx \sim \calD\) has an expectation of exactly \[\sum_{i=1}^{n}\boldsymbol{\sigma}_i \cdot \Ex_{\bx \sim \calD}\left[\bx_i\right] = \sum_{i=1}^{n}\boldsymbol{\sigma}_i \cdot \mu_i = \frac{1}{n}\sum_{i=1}^{n}\boldsymbol{\sigma}_i.\] Therefore, by estimating \(\frac{1}{n}\sum_{i=1}^{n}\boldsymbol{\sigma}_i\) to an additive error of \(O(p)\) using \(\widetilde{O}(n/p^2)\) additional samples, we obtain a tester with sample complexity (modulo polylogarithmic factors) \[\label{eq:stitch} \frac{1}{p}\cdot n^2p^2 + \frac{n}{p^2}.\tag{2}\] Setting \(p = n^{-1/3}\) gives a sample complexity of \(\widetilde{O}(n^{5/3})\), which already improves upon the easy \(\widetilde{O}(n^2)\) bound (cf. 1.1).

3.1.2 Main Technical Lemma↩︎

Recall from the warm-up that the sign estimates \(\boldsymbol{\sigma}_1, \boldsymbol{\sigma}_2, \ldots, \boldsymbol{\sigma}_n\) satisfy \(\Ex_{}\left[\boldsymbol{\sigma}_i\right] \ge p\), which implies \[\Prx_{\boldsymbol{\sigma}}\sbra{\frac{1}{n}\sum_{i=1}^{n}\boldsymbol{\sigma}_i \ge \Omega(p)} \ge \Omega(p)\,.\] Now, note that if we were able to replace the R.H.S. above with \(\Omega(1)\) instead of \(\Omega(p)\), then this stronger lower bound would imply that \(O(1)\) independent sign estimates would suffice for “catching” the \(\Omega(p)\) bias. Then, the sample complexity (up to polylogarithmic factors) would be (cf. 2 ), which reduces to if we set \(p = n^{-1/4}\).

We first note that the property \(\Ex_{}\left[\boldsymbol{\sigma}_i\right] \ge p\) alone does not imply the desired high-probability bound, namely, \[\Pr_{}\left[\frac{1}{n}\sum_{i=1}^{n}\boldsymbol{\sigma}_i \ge \Omega(p)\right] \ge \Omega(1).\] Suppose for the sake of simplicity that \(n\) is even, and imagine that \(\boldsymbol{\sigma}\in \{\pm 1\}^n\) is drawn from the following distribution:

• With probability \(p\), \(\boldsymbol{\sigma}= (+1, +1, \ldots, +1)\).

• With the remaining probability \(1 - p\), \(\boldsymbol{\sigma}\) is chosen as a uniformly random permutation of \(n/2\) copies of \(+1\) and \(n/2\) copies of \(-1\).

It can be easily verified that the above distribution satisfies \(\Ex_{}\left[\boldsymbol{\sigma}_i\right] = p\), yet \(\frac{1}{n}\sum_{i=1}^{n}\boldsymbol{\sigma}_i > 0\) only holds with probability \(p\).

Therefore, the crux is to show that the \(\boldsymbol{\sigma}_i\)’s cannot be too correlated (as in the example above). Concretely, proving the following will suffice for our purposes:

It is readily verified that 2 fails for non-unate distributions: consider, for example, the two-point distribution \(\calD(+1^n) = \calD(-1^n) = 0.5\). We defer the proof of 2 to 3.1.4, and first show why it implies the correctness of 1.

3.1.3 Proof of [thm:our-unif-test]↩︎

We will require the following lemma due to Qiao and Valiant [51]:

3.1.4 Proof of 2↩︎

Without loss of generality, we prove the lemma when the unate distribution \(\calD\) is monotone; the more general statement then follows from the observation that flipping the \(i^\text{th}\) coordinate of \(\calD\) leads to a flip in the distribution of \(\boldsymbol{\sigma}_i\), which preserves the magnitude of the covariances.

For \(i \in [n]\), we define \[\bS_i := \sum_{\ell=1}^m \x{\ell}_i \qquad\text{and}\qquad \mu_i := \Ex_{\bx\sim\calD}\sbra{\bx_i}\,.\] In particular, we have \(\boldsymbol{\sigma}_i = \sign(\bS_i) = 2\cdot \mathbf{1}\cbra{\bS_i\geq 0} - 1\), and so \[\label{eq:cov-in-terms-of-big-sig} \Cov[\boldsymbol{\sigma}_i,\boldsymbol{\sigma}_j] = 4\pbra{\Pr[\bS_i \geq 0,\bS_j \geq 0] - \Pr[\bS_i \geq 0]\Pr[\bS_j \geq 0] }\,.\tag{5}\]

We will prove 2 with \(i = 1\) and \(j = 2\); that is, we will show that \[\Cov[\boldsymbol{\sigma}_1, \boldsymbol{\sigma}_2] = O\pbra{\frac{1}{\sqrt{m}}}\,.\] Define \[\begin{align} p_{00} := \Prx_{\bx\sim\calD}\sbra{(\bx_1,\bx_2) = (-1,-1)}\,, \qquad&\qquad p_{10} := \Prx_{\bx\sim\calD}\sbra{(\bx_1,\bx_2) = (+1,-1)}\,, \\ p_{01} := \Prx_{\bx\sim\calD}\sbra{(\bx_1,\bx_2) = (-1,+1)}\,, \qquad&\qquad p_{11} := \Prx_{\bx\sim\calD}\sbra{(\bx_1,\bx_2) = (+1,+1)}\,. \end{align}\] Thanks to monotonicity of \(\calD\), we have \(p_{00} \leq p_{10} \leq p_{11}\) and \(p_{00}\leq p_{01} \leq p_{11}\). It also follows that \(\mu_1 = 1 - 2(p_{00} + p_{01}) \geq 0\) and \(\mu_2 = 1 - 2(p_{00} + p_{10}) \geq 0\). The proof considers two cases depending on the value of \(\mu_1 + \mu_2\):

Case 1: \(\mu_1 + \mu_2 > 1/2\)↩︎

We record the following easy bound on \(\Cov[\boldsymbol{\sigma}_1, \boldsymbol{\sigma}_2]\): \[\label{eq:easy-cov-ub} \abs{\Cov[\boldsymbol{\sigma}_1,\boldsymbol{\sigma}_2]} \leq 4\min\cbra{\Pr\sbra{\bS_1 < 0}, \Pr\sbra{\bS_2 < 0}}\,.\tag{6}\] Assuming 6 , a direct application of the Hoeffding bound gives \[\Pr[\bS_i <0] \leq e^{-m\mu_i^2/2}\,, \qquad\text{and so}\qquad |\Cov(s_1, s_2)|\leq 4e^{-m/32}\ll O\pbra{\frac{1}{\sqrt{m}}}\,,\] where we make use of the fact that \(\min\{\mu_1, \mu_2\} \geq 1/4\) by the assumption \(\mu_1 + \mu_2 > 1/2\).

We now justify 6 . It will be convenient to write \[A := \Pr[\bS_1\geq 0, \bS_2\geq0]\,, \qquad B := \Pr[\bS_1\geq0]\,, \qquad\text{and}\qquad C=\Pr[\bS_2\geq0]\,.\] Note that \(\E[\boldsymbol{\sigma}_1] = 2B - 1\) and \(\E[\boldsymbol{\sigma}_2] = 2C-1\). Writing \(D := 1 + A - B - C\), it is readily checked that \(D = \Pr[\bS_1 < 0, \bS_2 < 0]\). It follows from 5 that \(\Cov[\boldsymbol{\sigma}_1,\boldsymbol{\sigma}_2] = 4(A-BC)\). In particular, we have \[\frac{1}{4}\abs{\Cov[\boldsymbol{\sigma}_1,\boldsymbol{\sigma}_2]} = \abs{A - BC}\,.\] Now,

• If \(A \geq BC\), then \(A-BC \leq C(1 - B) \leq 1-B\).

• If \(A < BC\), then \(BC - A \leq C-(B+C-1) = 1-B\), since \(D \geq 0\) gives \(A \geq B+C -1\).

It follows that \(|\Cov[\boldsymbol{\sigma}_1,\boldsymbol{\sigma}_2]| \leq 4(1-B) = 4\Pr[\bS_1 < 0]\). By symmetry, the same holds with \(B\) and \(C\) swapped, which yields 6 .

Case 2: \(\mu_1 + \mu_2 \leq 1/2\)↩︎

In this case, we will control \(\Cov(\boldsymbol{\sigma}_1,\boldsymbol{\sigma}_2)\) via a Gaussian approximation to the sums \(\bS_1\) and \(\bS_2\). First, let \(\kappa := \Cov[\bx_1,\bx_2]\) for \(\bx\sim\calD\). Note that \(\kappa = p_{00} + p_{11} - p_{01} - p_{10} - \mu_1\mu_2\).

We will first control the covariance of the Gaussian approximation. Consider the standardized random vector \[\bT = (\bT_1, \bT_2) := \frac{1}{\sqrt{m}}(\bS_1 - m\mu_1, \bS_2 - m\mu_2)\, \qquad\text{and let}\qquad \Sigma:=\begin{pmatrix} \lambda_1^2 & \kappa \\[2pt] \kappa & \lambda_2^2\end{pmatrix}\] where \(\lambda_i^2 = 1 - \mu_i^2\). We will sometimes write \(\mu = (\mu_1, \mu_2)\). Finally, let \(\rho\) be the correlation between \(\bT_1\) and \(\bT_2\), that is, \[\rho := \frac{\kappa}{\lambda_1\lambda_2}\,.\]

Note that by the central limit theorem, \(\bT \to N(0, \Sigma)\) (in distribution) as \(m \to \infty\). Following 5 , the Gaussian approximation of the correlation is \[\Cov_{\approx} := 4\Bigl(\Pr\big[\bZ_1\geq -\sqrt{m}\mu_1,\bZ_2\geq-\sqrt{m}\mu_1\big]-\Pr\big[\bZ_1\geq-\sqrt{m}\mu_1\big]\Pr\big[\bZ_2\geq-\sqrt{m}\mu_2\big]\Bigr).\] Note that \(\Cov_{\approx} = \Cov[\boldsymbol{\tau}_1,\boldsymbol{\tau}_2]\) where \(\boldsymbol{\tau}_i = \sign(\bZ_i - \sqrt{m}\mu_i)\). Next, we will show that \(\Cov_{\approx} = O(m^{-1/2})\) via known estimates for computing bi-variate normal probabilities. In particular, applying Equation 3.6 of [52] gives \[\begin{align} |\Cov_{\approx}| &= 4\left|\frac{1}{2\pi}\int_0^\rho \frac{1}{\sqrt{1-z^2}}\exp\Bigl(-\frac{1}{2}\frac{(\sqrt{m}\tfrac{\mu_1}{\lambda_1})^2+(\sqrt{m}\tfrac{\mu_2}{\lambda_2})^2-2(\sqrt{m}\tfrac{\mu_1}{\lambda_1})(\sqrt{m}\tfrac{\mu_2}{\lambda_2})z}{1-z^2}\Bigr) \, dz\right| \nonumber \\ &\leq \frac{2}{\pi}\int_0^{|\rho|} \frac{1}{\sqrt{1-z^2}}\exp\Bigl(-\frac{m}{2}\left(\frac{(\tfrac{\mu_1}{\lambda_1}-\tfrac{\mu_2}{\lambda_2})^2}{1-z^2}+\frac{2\tfrac{\mu_1}{\lambda_1}\tfrac{\mu_2}{\lambda_2}}{1+z}\right)\Bigr) \, dz \tag{7} \\ &\leq \frac{2}{\pi}\int_0^{|\rho|} \frac{1}{\sqrt{1-z^2}}\exp\Bigl(-\frac{m}{8}(\tfrac{\mu_1}{\lambda_1}+\tfrac{\mu_2}{\lambda_2})^2\Bigr) \, dz \tag{8} \\ &\leq \frac{2}{\pi}\sin^{-1}|\rho|\exp\Bigl(-\frac{m}{8}(\mu_1+\mu_2)^2\Bigr) \nonumber \\ &\leq |\rho|\exp\Bigl(-\frac{m}{8}(\mu_1+\mu_2)^2\Bigr)\,, \tag{9} \end{align}\] where 7 relies on the fact that the integrand is larger on the positive \(z\) side, 8 uses \[\frac{(\tfrac{\mu_1}{\lambda_1}-\tfrac{\mu_2}{\lambda_2})^2}{1-z^2}+\frac{2\tfrac{\mu_1}{\lambda_1}\tfrac{\mu_2}{\lambda_2}}{1+z} \geq (\tfrac{\mu_1}{\lambda_1}-\tfrac{\mu_2}{\lambda_2})^2+\tfrac{\mu_1}{\lambda_1}\tfrac{\mu_2}{\lambda_2} = \frac{1}{4}(\tfrac{\mu_1}{\lambda_1}+\tfrac{\mu_2}{\lambda_2})^2+\frac{3}{4}(\tfrac{\mu_1}{\lambda_1}-\tfrac{\mu_2}{\lambda_2})^2\,,\] and 9 relies on \(\lambda_i\leq 1\) and \(\sin^{-1}(\theta) \leq \frac{\pi\theta}{2}\) for \(\theta\geq 0\).

We record the following lemma:

Combining 9 with 4, we get \[\label{eq:senior-fitness} |\Cov_{\approx}| \leq (\mu_1+\mu_2) \exp\Bigl(-\frac{m}{8}(\mu_1+\mu_2)^2\Bigr) = O\pbra{\frac{1}{\sqrt{m}}}\,.\tag{12}\]

Next, we will control the error in the Gaussian approximation to \(\Cov[\boldsymbol{\sigma}_1,\boldsymbol{\sigma}_2]\) itself by applying the multivariate Berry-Eseeen central limit theorem (cf. 1). It is readily verified using 5 and the triangle inequality that \[\frac{1}{4}\pbra{\Cov[\boldsymbol{\sigma}_1,\boldsymbol{\sigma}_2] - \Cov_{\approx}} \leq \sum_{i=1}^3 |\alpha_i - \beta_i|\] where \[\begin{gather} \alpha_1 = \Prx[\bS_1 \geq 0, \bS_2 \geq 0]\,,\quad \alpha_2 = \Pr[\bS_1 \geq 0]\,,\quad \alpha_3 = \Pr[\bS_2 \geq 0]\,,\\[0.5em] \beta_1 = \Pr\sbra{\bZ_1 \geq -\sqrt{m}\mu_1, \bZ_2 \geq -\sqrt{m}\mu_2}\,,\quad \beta_2 = \Pr\sbra{\bZ_1 \geq -\sqrt{m}\mu_1}\,, \quad \beta_3 = \Pr\sbra{\bZ_2 \geq -\sqrt{m}\mu_2}\,. \end{gather}\] 1 combined with the fact that both \(\mu_1, \mu_2 \leq 1/2\) immediately gives \(|\alpha_2-\beta_2|\), \(|\alpha_3-\beta_3| = O(m^{-1/2})\). In more detail, 1 gives \[|\alpha_2-\beta_2| = O\left(\frac{1}{\sqrt{m}}\cdot\frac{[|\bS_1-\mu_1|^3]}{\Ex[(\bS_1-\mu_1)^2]^{3/2}}\right) = O\left(\frac{1}{\sqrt{m}}\cdot\frac{(1+\mu_1)^3]}{(1-\mu_1^2)^{3/2}}\right) \leq O\pbra{\frac{1}{\sqrt{m}}}\,.\] An identical argument gives the same bound for \(|\alpha_3-\beta_3|\). Finally, in order to show that \(|\alpha_1-\beta_1| = O(m^{-1/2})\) using 1, it suffices to establish that \(\E[\|\Sigma^{-1/2}(\bS-\mu)\|_2^3] = O(1)\), where \(\bS = (\bS_1, \bS_2)\). To see this, first note that \[\Sigma^{-1/2} = \frac{1}{2}\begin{bmatrix} \alpha & \beta \\ \beta & \alpha \end{bmatrix}\begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix}^{-1}\] where \(\alpha = \frac{1}{\sqrt{1+\rho}}+\frac{1}{\sqrt{1-\rho}}\) and \(\beta = \frac{1}{\sqrt{1+\rho}}-\frac{1}{\sqrt{1-\rho}}\). Now, \[\begin{align} \|\Sigma^{-1/2}(\bS-\mu)\|_2^2 &= \frac{1}{4}\left((\alpha\lambda_1^{-1}(\bS_1-\mu_1)+\beta\lambda_2^{-1}(\bS_2-\mu_2))^2+(\beta\lambda_1^{-1}(\bS_1-\mu_1)+\alpha\lambda_2^{-1}(\bS_2-\mu_2))^2\right) \nonumber\\ &= \frac{1}{1-\rho^2}\left(\lambda_1^{-2}(\bS_1-\mu_1)^2+\lambda_2^{-2}(\bS_2-\mu_2)^2-\rho\lambda_1^{-1}\lambda_2^{-1}(\bS_1-\mu_1)(\bS_2-\mu_2)\right) \tag{13} \\ &\leq \frac{4}{1-\rho^2}\left(\lambda_1^{-2}+\lambda_2^{-2}+\rho\lambda_1^{-1}\lambda_2^{-1}\right) \tag{14} \\ &= 4\cdot\frac{2-(\mu_1^2+\mu_2^2)+\kappa}{(1-\mu_1^2)(1-\mu_2^2)-\kappa^2} \nonumber \\ &\leq 4\cdot \frac{2-\frac{1}{2}+\frac{1}{4}}{\frac{3}{4}-\left(\frac{4}{9}\right)^2} < 16 \tag{15}, \end{align}\] where in 13 we note that \(\alpha^2+\beta^2 = \frac{4}{1-\rho^2}\) and \(2\alpha\beta = -\frac{4\rho}{1-\rho^2}\), in 14 we use \(|X_i-\mu_i|\leq 2\), and in 15 we recall \((1-\mu_1^2)(1-\mu_2^2) \geq \frac{3}{4}\) and \(-\tfrac{4}{9} \leq \kappa \leq \tfrac{1}{4}\). The result follows immediately. 0◻

3.2 Lower Bound↩︎

Turning to lower bounds for uniformity testing of unate distribution, we will establish the following:

In particular, [thm:our-unif-lb] implies that the algorithm from 3.1 has essentially optimal sample complexity. Our proof of [thm:our-unif-lb] will rely on a slight modification of the construction used by Rubinfeld and Servedio [20] to show a tight lower bound for uniformity testing of monotone distributions.

3.2.1 Useful Preliminaries↩︎

Throughout this section, we set a parameter \[\tau := \Theta\pbra{\frac{\log n}{n}}\,.\] We write \(\calD_\tau\) for the product distribution over \(\bn\) where each marginal is a \(\tau\)-biased bit. In other words, for \(x\in\bn\), we have \[\calD_\tau(x) = \pbra{\frac{1}{2} + \tau}^{\abs{\{i:x_i = +1\}}}\pbra{\frac{1}{2} - \tau}^{\abs{\{i:x_i = -1\}}}\,.\] Claim 11 of [20] gives the following representation of \(\calD_\tau\) which will be useful for our purposes: \[\label{eq:RS-subcube-decomp} \calD_\tau(x) = \sum_{i=0}^n \sum_{\substack{y \in \bn \\ |i : y_i = +1| = i}} (2\tau)^i(1-2\tau)^{n-i} \calU_y(x) =: \sum_{y \in \bn} p_y \calU_y(x)\,,\tag{16}\] where we write \(\calU_y\) for the uniform distribution on the monotone subcube rooted at \(y\), i.e., the uniform distribution on \(\{z \in \bn : z_i \geq y_i~\text{for all}~i\in[n] \}\).

Note, in particular, that the value of \(T\) in [prop:RS-claim-7] is unconstrained. We will also require the following due to Rubinfeld and Servedio, which states that for \(T = n^3\), with high probability the distribution \(\bq\) constructed in [prop:RS-claim-7] is far from uniform:

We note that Rubinfeld and Servedio [20] proved their Lemma 13 with \(T= n^2\), but we require a larger \(T\) for our result. The variant above readily follows from inspecting their proof and adjusting the constant hidden by \(\Theta(\cdot)\) in \(\tau\).

3.2.2 Proof of [thm:our-unif-lb]↩︎

Let \(T = n^3\), \(m = \Theta(n^{3/2}/\log^2(n))\), and let \(\calD_\tau\) be as in the previous section. (Note that \(m \leq 0.1\sqrt{T}\) for \(n\) large enough.) We will show that there exists a distribution \(\calF\) over unate distributions over \(\bn\) such that

1. With probability \(1-o(1)\) over the draw of \(\bq'\sim\calF\), \(\mathrm{d}_{\mathrm{TV}}(\bq', \calU) \geq 1-n^{-9}\).

2. The statistical distance between (a) the distribution of \(m\) independent samples from \(\calU\), and (b) the draw of \(m\) independent samples from \(\bq'\) where \(\bq' \sim\calF\), is at most \(0.2\).

Items 1 and 2 immediately imply that any algorithm with performance guarantee as in [thm:our-unif-test] must draw \(m = \Omega(n^{3/2})\) samples.

We now define the family \(\calF\) of hard distributions. A distribution \(\bq'\sim\calF\) is generated as follows:

1. First generating \(\bq\) as in [prop:RS-claim-7] and drawing \(\boldsymbol{\sigma}\sim\bn\).

2. Returning the distribution \(\bq' := \bq^{\boldsymbol{\sigma}}\) (cf. [notation:D-sigma]).

Note that since every \(\bq\) generated as in [prop:RS-claim-7] is monotone, it follows that every \(\bq' = \bq^{\boldsymbol{\sigma}}\) is a unate distribution. Item 1 follows immediately from [prop:RS-lemma-13]; all that remains is to establish Item 2 above.

It will be convenient to write \(\calD'\) for the distribution of \(m\) independent samples from \(\bq'\) after drawing \(\bq'\sim\calF\). For \(\boldsymbol{\sigma}\) as in Item (a) above, we have \[\begin{align} \mathrm{d}_{\mathrm{TV}}\pbra{\calD', \calU^{\otimes m}} &\leq \mathrm{d}_{\mathrm{TV}}\pbra{\calD', (\calD_\tau^{\boldsymbol{\sigma}})^{\otimes m}} + \mathrm{d}_{\mathrm{TV}}\pbra{(\calD_\tau^{\boldsymbol{\sigma}})^{\otimes m}, \calU^{\otimes m}}\\ &= \mathrm{d}_{\mathrm{TV}}\pbra{\bS_1, \bS_2} + \mathrm{d}_{\mathrm{TV}}\pbra{(\calD_\tau^{\boldsymbol{\sigma}})^{\otimes m}, \calU^{\otimes m}} \\ &\leq \frac{1}{100} + \mathrm{d}_{\mathrm{TV}}\pbra{(\calD_\tau^{\boldsymbol{\sigma}})^{\otimes m}, \calU^{\otimes m}}\,, } \end{align}\] where \(\bS_1, \bS_2\) are as in [prop:RS-claim-7]. Note that in the first item above, \((\calD_\tau^{\boldsymbol{\sigma}})^{\otimes m}\) refers to the distribution of \(m\) samples obtained by first drawing \(\boldsymbol{\sigma}\) and then drawing \(m\) independent samples from \(\calD_\tau^{\boldsymbol{\sigma}}\).

The remainder of the argument will establish \[\label{eq:unif-LB-final-goal} \mathrm{d}_{\mathrm{TV}}\pbra{(\calD_\tau^{\boldsymbol{\sigma}})^{\otimes m}, \calU^{\otimes m}} \leq 0.1\,,\tag{17}\] which will complete the proof of [thm:our-unif-lb]. Since each marginal is independent in both \(\calD_\tau^{\boldsymbol{\sigma}}\) and \(\calU\), it follows from additivity of the KL divergence that \[\begin{align} \mathrm{d}_{\mathrm{TV}}\pbra{(\calD_\tau^{\boldsymbol{\sigma}})^{\otimes m}, \calU^{\otimes m}} &\leq \sqrt{\frac{1}{2}\mathrm{d}_{\mathrm{KL}}\pbra{(\calD_\tau^{\boldsymbol{\sigma}})^{\otimes m}, \calU^{\otimes m}}} } \\ &= \sqrt{\frac{1}{2}\sumi \mathrm{d}_{\mathrm{KL}}\pbra{(\calD_\tau^{\boldsymbol{\sigma}})_i^{\otimes m}, (\calU)_i^{\otimes m}}}\,, \end{align}\] where we use the subscript \(i\in [n]\) to denote the marginal of the draw of \(m\) samples, each restricted to the \(i^\text{th}\) bit. Note that for any fixed \(i\in [n]\), the quantity \(\mathrm{d}_{\mathrm{KL}}\pbra{(\calD_\tau^{\boldsymbol{\sigma}})_i^{\otimes m}, (\calU)_i^{\otimes m}}\) is the KL divergence between (i) the uniform mixture of \(\mathsf{Binomial}(m,1/2-\tau)\) and \(\mathsf{Binomial}(m, 1/2+\tau)\), and (ii) \(\mathsf{Binomial}(m, 1/2)\).

Let \(p_\pm:=\tfrac12\pm\tau\) with \(0<\tau<\tfrac12\), and define the distributions \[P(k)=\tfrac12\binom{m}{k}p_-^{\,k}(1-p_-)^{m-k} +\tfrac12\binom{m}{k}p_+^{\,k}(1-p_+)^{m-k}, \qquad Q(k)=\binom{m}{k}\,2^{-m}\] for notational convenience. Note that \(P\) is the uniform mixture from above, while \(Q\) is \(\mathsf{Binomial}(m, 1/2 + \tau)\) . Finally, let \[f_{\pm}(k) := \frac{P_{\pm}(k)}{Q(k)} = \frac{P_\pm(k)}{Q(k)} =\bigl(2p_\pm\bigr)^{k}\bigl(2(1-p_\pm)\bigr)^{m-k}\,,\] and note that \(\E_{Q}[f_{\pm}] = 1\). We have from 1 that \[\begin{align} \mathrm{d}_{\mathrm{KL}}\pbra{(\calD_\tau^{\boldsymbol{\sigma}})_i^{\otimes m}, (\calU)_i^{\otimes m}} &\leq \mathrm{d}_{\mathrm{\chi^2}}\pbra{(\calD_\tau^{\boldsymbol{\sigma}})_i^{\otimes m}, (\calU)_i^{\otimes m}} \\ &=\Ex_Q\!\left[\left(\tfrac12(f_-+f_+)-1\right)^{\!2}\right]\\ &=\tfrac14\,\Ex_Q\!\bigl[(f_-+f_+)^2\bigr]-1\\ &=\tfrac14\Bigl(\Ex_Q[f_-^2]+\Ex_Q[f_+^2]+2\,\Ex_Q[f_-f_+]\Bigr)-1\\ &=\tfrac12\Bigl((1+4\tau^2)^m+(1-4\tau^2)^m\Bigr)-1\\ &=8m(m-1)\tau^4+O\!\bigl(m\tau^6\bigr)\,. \end{align}\] Combining this with the earlier bound, we get \[\mathrm{d}_{\mathrm{TV}}\pbra{(\calD_\tau^{\boldsymbol{\sigma}})^{\otimes m}, \calU^{\otimes m}} \leq O(1)\cdot \sqrt{n m^2 \tau^4} \ll 1 ~\qquad\text{for}~m = \Theta\pbra{\frac{n^{3/2}}{\log^2 n}}\,,\] which establishes 17 and completes the proof of [thm:our-unif-lb]. 0◻

4 Testing Unateness with Subcube Conditioning↩︎

We now turn to the proofs of [thm:our-subcube-UB,thm:subcube-lower-bound], starting with the former.

4.1 Upper Bound↩︎

We start by recalling [thm:our-subcube-UB]:

4.1.1 Preliminaries from [27]↩︎

Chakrabarty, Chen, Ristic, Seshadhri, and Waingarten [27] gave an \(\widetilde{O}(n/\eps^2)\)-query algorithm for monotonicity testing of a distribution over \(\{\pm 1\}^n\) in the subcube conditional model. Our \(\widetilde{O}(n^{3/2}/\eps^2)\)-query algorithm for unateness testing will rely on their principal technical lemma, which we state after introducing some relevant notation.

For any \(x \in \{\pm 1\}^n\) and \(i \in [n]\), we define \[\delta_{x,i} \mathrel{\vcenter{:}}= \frac{\calD(x^{i\to -1}) - \calD(x^{i\to +1})}{\calD(x^{i\to -1}) + \calD(x^{i\to +1})} \in [-1, 1]\] as the bias on the edge \(\{x, x^{\oplus i}\}\). Note that if \(\calD\) is monotone, we always have \(\delta_{x,i} \le 0\), so a positive \(\delta_{x,i}\) witnesses a violation of monotonicity.

Central to the analysis in [27] is the following lemma, which is implicit in the proof of [27]. For \(x \in \R\), we write \((x)_+ \mathrel{\vcenter{:}}= \max\{x, 0\}\).

The proof of 5 relies on a real-valued “directed” isoperimetric inequality proved in [27]. In particular, it follows from 5 that if we draw a random \(\bw \le O(\log(n/\eps))\) with probability \(\bw = w\) proportional to \(2^{-w}\), we have \[\label{eq:MIT-tech-review} \Prx_{\bw, \bx \sim \calD, \bi \sim [n]}\sbra{(\delta_{\bx, \bi})_+^2 \ge 2^{-\bw}} \ge \sum_{w=1}^{O(\log(n/\eps))}2^{-w}\cdot\Prx_{\bx \sim \calD \atop \bi \sim [n]}\sbra{(\delta_{\bx, \bi})_+^2 \ge 2^{-w}} \ge \widetilde{\Omega}\left(\frac{\eps^2}{n}\right).\tag{18}\]

Give the lemma above, the algorithm of [27] is natural: we simply sample \(\widetilde{O}(n/\eps^2)\) triples \((\bw, \bx, \bi)\), in the hope of finding at least one with \((\delta_{\bx, \bi})_+^2 \ge 2^{-\bw}\). For each triple, we make \(\widetilde{O}(2^w)\) queries to the subcube (or edge) \(\{x, x^{\oplus i}\}\) to check whether \((\delta_{x,i})_+^2 \ge 2^{-w }\) holds. If this holds for any triple, we reject distribution \(\calD\). Over the randomness in \(\bw\), we make \(\sum_{w=1}^{O(\log(n/\eps))}2^{-w}\cdot\widetilde{O}(2^w) = \widetilde{O}(1)\) queries for each triple, so the overall query complexity is \(\widetilde{O}(n/\eps^2)\).

4.1.2 Proof of [thm:our-subcube-UB]↩︎

We first introduce some additional notation before proving [thm:our-subcube-UB]. Recall from [notation:D-sigma] that, for \(\sigma \in \bn\), \(\calD^\sigma\) is the distribution of \[\bx^\sigma \mathrel{\vcenter{:}}= (\sigma_1 \bx_1, \sigma_2 \bx_2, \ldots, \sigma_n \bx_n)\,,\] where \(\bx \sim \calD\), i.e., \(\calD^\sigma\) is obtained from \(\calD\) by flipping the coordinates indexed by \(\{i \in [n]: \sigma_i = -1\}\). Recall that, with respect to distribution \(\calD\), we defined \[\delta_{x,i} \mathrel{\vcenter{:}}= \frac{\calD(x^{i\to -1}) - \calD(x^{i\to +1})}{\calD(x^{i\to -1}) + \calD(x^{i\to +1})}\,.\] In the following, we will write \(\delta^{\calD}_{x,i}\) to avoid confusion and emphasize dependence on \(\calD\). While the next identity is notation-heavy, it states an intuitive fact: if \(\calD^\sigma\) has a bias on an edge adjacent to \(x\) along the \(i^\text{th}\) direction, \(\calD\) should also have a bias at \(x^\sigma\), albeit flipped by \(\sigma_i\). More formally, \[\begin{align} \delta^{\calD^\sigma}_{x,i} &= \frac{\calD^\sigma(x^{i\to -1}) - \calD^\sigma(x^{i\to +1})}{\calD^\sigma(x^{i\to -1}) + \calD^\sigma(x^{i\to +1})} \nonumber \\ &= \frac{\calD((x^{i\to -1})^\sigma) - \calD((x^{i\to +1})^\sigma)}{\calD((x^{i\to -1})^\sigma) + \calD((x^{i\to +1})^\sigma)}\nonumber \\ &= \frac{\sigma_i \cdot \left[\calD((x^\sigma)^{i\to -1}) - \calD((x^\sigma)^{i\to +1})\right]}{\calD((x^\sigma)^{i\to -1}) + \calD((x^\sigma)^{i\to +1})} \nonumber \\ &= \sigma_i \cdot \delta^P_{x^\sigma, i}\,. \label{eq:banana} \end{align}\tag{19}\]

We now record a corollary of 5 which will be crucial to our analysis of 2. Since \(\calD\) is \(\eps\)-far from unate, for every sign pattern \(\sigma \in \{\pm 1\}^n\), the distribution \(\calD^\sigma\) is \(\eps\)-far from monotone. Applying 5 (or more precisely, 18 ) to \(\calD^\sigma\) then gives \[\begin{align} \wt{\Omega}\pbra{\frac{\eps^2}{n}} &\leq \Prx_{\bw, \bx\sim \calD^\sigma, \bi \sim [n]}\sbra{(\delta^{\calD^\sigma}_{\bx, \bi})_+^2 \ge 2^{-\bw}} \nonumber \\ &= \Prx_{\bw, \bx\sim \calD^\sigma, \bi \sim [n]}\sbra{(\sigma_i\cdot\delta^{\calD}_{\bx^\sigma, \bi})_+^2 \ge 2^{-\bw}} } \nonumber \\ &= \Prx_{\bw, \bx\sim \calD, \bi \sim [n]}\sbra{(\sigma_i\cdot\delta^{\calD}_{\bx, \bi})_+^2 \ge 2^{-\bw}}\,, \label{eq:super-nice-bakery} \end{align}\tag{20}\] where 20 relies on the fact that for \(\bx\sim\calD^\sigma\), the random variable \(\bx^\sigma\) is distributed as \(\calD\). We record this consequence of 5 for future use:

1 suggests a natural test to detect distributions that are far from unate and forms the basis of 2: iterating over each coordinate \(i\in [n]\), we reject if there exist two pairs \((\bw, \bx)\) and \((\bw', \bx')\) such that \[\label{eq:subcube-reject-condition} (\delta^\calD_{\bx,i})_{+}^2 \ge 2^{-\bw} \quad\text{and}\quad (-\delta^\calD_{\bx',i})_{+}^2 \ge 2^{-\bw'}\,.\tag{21}\] Intuitively, the former condition rules out the possibility that \(\calD\) is monotone in direction \(i\), and the latter rules out that \(\calD\) is anti-monotone in direction \(i\). Note that if \(\calD\) is unate, then both conditions above can never hold simultaneously.

We now turn to the proof of [thm:our-subcube-UB]:

4.2 Lower Bound↩︎

We prove the following lower bound for testing unateness of distributions in the subcube model, which applies to all testers that only make subcube queries on either the entire hypercube (to get an unconditional sample) or a small subcube.

Recall that our tester for [thm:our-subcube-UB], like the monotonicity tester of [27], only makes subcube queries on edges (i.e., one-dimensional subcubes) in addition to drawing unconditional samples. In other words, our tester satisfies the precondition of [thm:subcube-lower-bound] with \(d = 1\). The theorem then implies that all such testers must make at least \(\widetilde{\Omega}(n^{2/3})\) queries in total.

We prove this lower bound by reducing the unateness testing of a Boolean function \(f: \bits^n \to \zo\) to that of a distribution over \(\bits^n\).³ For a non-zero Boolean function \(f\), let \(\calD_f\) denote the uniform distribution over \(f^{-1}(1) \mathrel{\vcenter{:}}= \{x \in \bits^n: f(x) = 1\}\). [thm:subcube-lower-bound] is an immediate consequence of the following observations and a lower bound of Chen, Waingarten, and Xie [30] for testing unateness of Boolean functions:

• (7) If function \(f: \bits^n \to \zo\) is unate, distribution \(\calD_f\) is also unate. If \(f\) is \(\eps\)-far from unate, \(\calD_f\) is \(\Omega(\eps)\)-far from unate.

• (8) Given membership query access to \(f: \bits^n \to \zo\), we can sample from \(\calD_f\) and its restrictions to small subcubes. Assuming that \(f\) is \(\eps\)-far from the zero function, \(O(1/\eps)\) queries suffice for drawing an unconditional sample from \(\calD_f\). Moreover, \(2^d\) queries suffice for sampling from \(\calD_f\) restricted to a \(d\)-dimensional subcube.

• By [30], testing the unateness of an \(n\)-variable Boolean function requires \(\widetilde{\Omega}(n^{2/3})\) queries.

We state and prove [lemma:unate-function-to-dist,lemma:function-to-dist-reduction] in the rest of this section.

Acknowledgements↩︎

D.L. is supported by the MIT Undergraduate Research Opportunities Program (UROP). S.N. is partially supported by Elchanan Mossel’s Vannevar Bush Faculty Fellowship ONR-N00014- 20-1-2826. R.R. is supported by the NSF TRIPODS program (award DMS-2022448) and CCF-2310818.

References↩︎

---

1. Formally, a distribution \(\calD\) over \(\bn\) is monotone if its probability mass function \(\calD : \bn\to[0,1]\) is monotone, i.e., \(\calD(x) \leq \calD(y)\) whenever \(x_i \leq y_i\) for all \(i\in[n]\).↩︎

2. See also Adamaszek, Czumaj, and Sohler [21] who improved the sample complexity to \(O(n/\eps^2)\).↩︎

3. In this section, we assume that the co-domain of the Boolean function is \(\zo\) (instead of \(\bits\)), which is more convenient when dealing with probability mass functions.↩︎