Sublinear-Query Relative-Error Testing of Halfspaces

Before describing our main results, we give some more context on halfspace testing in the standard model. Halfspace testing has primarily been studied under two distributions, which correspond to discrete and continuous domains. These are the usual uniform distribution over ${\{0,1\}}^n$ [37, 36] and the standard $N(0,I_n)$ Gaussian distribution over ${ℝ}^n$ [37, 41, 20, 21]. For $N(0,I_n)$, the “standard-model” distance between $f,g:{ℝ}^n\to \{\pm 1\}$ is simply

In the standard model [37] showed that halfspaces can be tested using only $\mathrm{poly}(1/\epsilon )$ queries under both the uniform distribution over ${\{0,1\}}^n$ and the Gaussian $N(0,I_n)$ distribution over ${ℝ}^n$. The [37] result for ${\{0,1\}}^n$ essentially uses their result over the Gaussian space as a subroutine.³³3We remark that a very different tester for the Gaussian space than the [37] tester was given by Mossel and Neeman in [41]; these results will be discussed in more detail later. Thus, developing relative-error halfspace testing algorithms for the Gaussian distribution is a natural first step towards obtaining improved results for the uniform distribution over ${\{0,1\}}^n$.

Towards this end, as the main results of this paper we provide three sublinear-query testing algorithms for halfspaces, all over the Gaussian space, where the relative distance between $f$ and another function $g$, where $f,g:{ℝ}^n\to \{0,1\},$ is defined (analogous to the Boolean setting) as

and in this setting a call to the random sample oracle $\mathrm{SAMP}(f)$ returns a draw from the Gaussian distribution conditioned on $f^{-1}(1)$. (See Section 3 for a more detailed definition of the model.)

To explain the main idea of Theorem 2, we start by recalling two fundamental notions in Gaussian analysis. For any set $A\subseteq {ℝ}^n$, its Gaussian volume, denoted by $\mathrm{Vol}(A)$, is ${\mathrm{𝐏𝐫}}_{𝒙\sim N(0,I_n)}[𝒙\in A]$. Furthermore, if $A$ is sufficiently smooth, we can also define its Gaussian surface area, denoted $\mathrm{𝗌𝗎𝗋𝖿}(A)$, as ${\int }_{x\in \partial A}{\phi }_n(x)𝑑\sigma (x)$, where ${\phi }_n(\cdot )$ denotes the standard $n$-dimensional Gaussian density; in other words, we integrate the standard Gaussian density over the surface of $A$. Given these notions of volume and surface area over the Gaussian space, one is naturally led to the “isoperimetric problem:” for a given (Gaussian) volume, what set minimizes the (Gaussian) surface area?

This question was answered by Borell [6] and Sudakov-Tsirelson [46], who showed that for any , for any measurable set $A\subseteq {ℝ}^n$ with $\mathrm{Vol}(A)=p$, it always holds that $\mathrm{𝗌𝗎𝗋𝖿}(A)\ge \mathrm{𝗌𝗎𝗋𝖿}(H_p)$ where $H_p$ is a halfspace with $\mathrm{Vol}(H_p)=p$. In other words, in the Gaussian space, for any given volume $p$, the halfspace with volume $p$ has minimal surface area. Subsequently, Ehrhard [26] showed that halfspaces are the unique minimizers of the Gaussian surface area. In other words, if a set $A\subseteq {ℝ}^n$ has $\mathrm{Vol}(A)=p$ and $\mathrm{𝗌𝗎𝗋𝖿}(A)=\mathrm{𝗌𝗎𝗋𝖿}(H_p)$, then the set $A$ is a halfspace.

One is now naturally led to the robustness question: Suppose a set $A$ has $\mathrm{Vol}(A)=p$ and $\mathrm{𝗌𝗎𝗋𝖿}(A)$ is $\delta$-close to $\mathrm{𝗌𝗎𝗋𝖿}(H_p)$. Then is it the case that $A$ is ${\delta }^{\prime }$-close to a halfspace, where ${\delta }^{\prime }\to 0$ as $\delta \to 0$? Cianchi et al. [16] were the first to affirmatively answer this question. Soon thereafter, in a significant breakthrough, Mossel and Neeman [40] obtained a “dimension free robust isoperimetry result”, i.e. one in which the dependence between ${\delta }^{\prime }$ and $\delta$ is independent of the ambient dimension $n$.

This result was quantitatively improved by Eldan [27] and then by Barchiesi et al. [2] (the latter result is the underlying technical ingredient we use in Theorem 2). A natural question at this point is “what is the connection between robust isoperimetry and testing halfspaces?”

The connection arises from a 2014 result of Neeman [42], who gave an algorithm for testing surface area over Gaussian space. The precise technical guarantee is somewhat cumbersome to state, but roughly speaking, the algorithm makes $\mathrm{poly}(S,1/\epsilon )$-queries to an unknown set $A$ and (i) accepts with high probability if $\mathrm{𝗌𝗎𝗋𝖿}(A)\le S$, but (ii) rejects with high probability if $\mathrm{𝗌𝗎𝗋𝖿}(B)>(1+\epsilon )S$ for every set $B$ which is $\epsilon$-close to $A$⁴⁴4This perturbation of $A$ is necessary because one can increase the surface area of a set arbitrarily by modifying on a measure zero set.. Now, observe that if an unknown set $A$ of some given volume $p$ is a halfspace, then its surface area is exactly given by $\phi ({\mathrm{\Phi }}^{-1}(p))$ where $\mathrm{\Phi }$ is the cdf and $\phi$ is the pdf of the standard Gaussian. So to test whether $A$ is a halfspace, we can use Neeman’s algorithm to test whether its surface area is essentially that of a halfspace of volume $p$, and accept if and only if that is the case. Correctness of this simple algorithm is established using the dimension-free robust isoperimetry result of Barchiesi et al. [2] that was mentioned above.

Our starting point for Theorem 3 is the work of Matulef, O’Donnell, Rubinfeld, and Servedio [37] which gives an algorithm (the “MORS algorithm”) that tests halfspaces over ${ℝ}^n$ using $O_{\epsilon }(1)$ queries. The MORS algorithm relies on two structural ingredients:

• $\mathrm{■}$

  First, there is a function $U:[0,1]\to ℝ$ (see the full version) which, given as input the volume $\mathrm{Vol}(f)$ of a function $f:{ℝ}^n\to \{0,1\}$, tells us exactly what the level-$1$ Hermite weight

  $${𝐖}^{=1}[f]:=\sum _{i=1}^n\underset{𝒙\sim N(0,I_n)}{𝐄}{\left[f(𝒙)\cdot {𝒙}_i\right]}^2$$

  would be if the function $f$ were the indicator function of a halfspace.

• $\mathrm{■}$

  Second, if $U(\mathrm{Vol}(f))\approx {𝐖}^{=1}[f]$, then the set $f$ is close to some halfspace.

The above facts suggest a natural algorithm: estimate $\mathrm{Vol}(f)$ and ${𝐖}^{=1}[f]$, and then compare $U(\mathrm{Vol}(f))$ to ${𝐖}^{=1}[f]$. (We remark that the MORS algorithm uses queries to do this.)

The algorithm Hermite-Test (see the full version) that yields Theorem 3 can be viewed as a relative-error, sample-based variant of the MORS algorithm. Our main technical lemma (see the full version) shows that if $U(\mathrm{Vol}(f))$ is sufficiently close to ${𝐖}^{=1}[f]$ in a suitable sense, then $f$ is close under relative distance to some halfspace. In this sense, this lemma can be viewed as a relative-error strengthening of the second structural ingredient of the MORS algorithm above. With this lemma in hand, we apply a test which is similar in spirit to the MORS algorithm: estimate ${𝐖}^{=1}[f]$ and see if it is (sufficiently) close to $U(\mathrm{Vol}(f))$.

This leads to a second technical challenge: in order to get a sample-based algorithm we must accurately estimate ${𝐖}^{=1}[f]$ using access to samples from $\mathrm{SAMP}(f)$ alone. (Note that the MORS algorithm relies on query access to the function $f$, and there are sample-based testers [1, 32] that rely on labeled samples from $f$ as opposed to just positive samples from $\mathrm{SAMP}(f)$.) To accomplish this, we employ a recent estimator used in a different context by [22, 19] (for the problem of detecting distribution truncation) which is as follows: given a draw of $2m$ i.i.d. samples ${𝒙}^{(1)},\mathrm{\dots },{𝒙}^{(m)},{𝒚}^{(1)},\mathrm{\dots },{𝒚}^{(m)}\leftarrow \mathrm{SAMP}(f)$, we compute the statistic

It is readily verified that $𝐄[𝑻]=\mathrm{Vol}{(f)}^{-2}\cdot {𝐖}^{=1}[f]$; since $\mathrm{Vol}(f)$ is known, we can estimate ${𝐖}^{=1}[f]$ if we can estimate $𝐄[𝑻]$. To estimate $𝐄[𝑻]$, we must establish a bound on the variance of $𝑻$; to do this, we employ (consequences of) hypercontractivity of the Gaussian measure (see Chapters 9 and 11 of [44]), drawing inspiration from recent work [19].

We obtain the algorithm of Theorem 4, which does not need to have (an estimate of) the value of $p$, by combining the ideas underlying Theorem 2 and Theorem 3, as well as bringing in new ideas. In particular, a crucial structural property of LTFs which we use for Theorem 4 is the following: not only does the level-$1$ Hermite weight of an LTF $f$ depend only on the bias of the function $𝐄[f]$ as mentioned earlier, but under the Gaussian distribution LTFs are in fact robustly extremal, among all $\{0,1\}$-valued functions, in terms of how their level-1 Hermite weight depends on on the bias of the function. In more detail, writing $h_p$ to denote a halfspace with Gaussian volume $p$, it is the case that any function $f:{ℝ}^n\to \{0,1\}$ with Gaussian volume $p$ must satisfy

(As alluded to in the last paragraph of Section 2.2, the LHS of the inequality above is precisely $\mathrm{Vol}{(f)}^2\cdot {𝐄}_{𝒙,𝒚\sim f^{-1}(1)}[𝒙\cdot 𝒚].$) Moreover the inequality can only be an equality if $f$ is a halfspace, and it can only be close to an equality if $f$ is close to a halfspace. Versions of this structural property are established, in varying degrees of explicitness, in Theorem 7 of [34], Theorem 26 of [37], and Theorem 3.3.4 of [31]; our result (see the full version) gives a version of this which is – crucially, for our purposes – quantitatively stronger than those earlier results in the small-$p$ regime.

With this perspective, we can reinterpret the testing algorithm of Theorem 3 in the following light: if the algorithm were not given $p$, it could compute an estimate $\tau$ of ${𝐄}_{𝒙,𝒚\sim f^{-1}(1)}[𝒙\cdot 𝒚]$ using draws from $\mathrm{SAMP}(f)$ and solve the equation

for the value $p_2$. If $f$ were an LTF and the value of $\tau$ were precisely the value of ${𝐄}_{𝒙,𝒚\sim f^{-1}(1)}[𝒙\cdot 𝒚]$, then this would give us the exact correct value $p_2=p$. On the other hand, because of the extremal property (1) mentioned above, if $f$ is far from every LTF then (up to a small factor due to estimation error) the value of $p_2$ will be significantly larger than the true value $p=\mathrm{Vol}(f).$

Now let us return to Theorem 2; the key for our analysis is that this result relies on a robust extremal property of LTFs that goes in the other direction. Recall that the Theorem 2 algorithm essentially works by estimating

(where “$𝒚\sim N_{\lambda }(𝒙)$” means that $𝒚$ is a $\lambda$-correlated random perturbation of $𝒙$; see Section 4.2 for a formal definition), and checking whether it takes the “right value” that it should take for an 0/1-valued LTF with expectation $p$, which is $\frac{1}{2p}{\mathrm{Sens}}_{\lambda }(LT{F}_p)=C\sqrt{\lambda \ln (1/p)}.$ In the Theorem 2 algorithm we use a value of $\lambda$ which depends on $p$, but for a fixed value of $\lambda$, the function $\frac{1}{2p}{\mathrm{Sens}}_{\lambda }(LT{F}_p)$ is a decreasing function of $p$; as we will see, this will be crucial for us.

Now, known isoperimetric properties of halfspaces can be shown to imply that if $f$ is any $\{0,1\}$-valued function $f$ with $\mathrm{Vol}(f)=p$, then $f$ must (essentially) satisfy

i.e. that halfspaces are minimizers of the quantity ${𝐏𝐫}_{𝒙\sim f^{-1}(1),𝒚\sim N_{\lambda }(𝒙)}[f(𝒙)\ne f(𝒚)]$, which the algorithm of Theorem 2 estimates from samples and queries. This means that if we run the algorithm of Theorem 2 with the value $p_2$ obtained from the modified algorithm of Theorem 3 as described earlier, there are two possibilities:

• $\mathrm{■}$

  If $f$ is a halfspace, then $p_2$ will be (approximately) equal to the true value of $p$, and since we are running the algorithm of Theorem 2 with (essentially) the right value of $p$, it will accept.

• $\mathrm{■}$

  On the other hand, if $f$ is far from every halfspace, then as explained earlier $p_2$ will be significantly larger than the true value of $p$. But since $\frac{1}{2p}{\mathrm{Sens}}_{\lambda }(LT{F}_p)$ is a decreasing function of $p$, the algorithm of Theorem 2 can only accept if it is run on a “guessed” value of $\mathrm{Vol}(f)$ which is either equal to or smaller than the true value of $\mathrm{Vol}(f)$. So in this case, the algorithm will reject.

This concludes the overview of the proof of Theorem 4. One point of technical interest is that the actual proof of Theorem 4 does not use Theorem 2 as a black-box. In fact, unlike Theorem 2 which crucially relies on the robust isoperimetry results of [2], Theorem 4 only relies on the classical result of Borell [7] which states that halfspaces are the minimizers of noise sensitivity. The result of Borell has many proofs by now, including some quite elementary (see [18] and references therein). So, arguably, the proof of Theorem 4 is significantly simpler than that of Theorem 2 (though conceptually, Theorem 4 is inspired by Theorem 2).

We begin by recalling the notion of surface area in the Gaussian space.

There is a close connection between the notion of surface area and noise sensitivity, as shown by Ledoux [35]:

A near-converse of this result was shown by Neeman [42]: every set $A$ as above is close to a set $B$ whose surface area can be bounded in terms of the noise sensitivity of $A$.

We recall (see e.g. Chapter 5 of [44]) that the function

is sometimes known as the Gaussian isoperimetric function (cf. Fact 14 below). This function will be used in various ways throughout our arguments, including in the proof of the following simple fact:

We now have all the necessary ingredients required to prove Theorem 2. The algorithm alluded to in Theorem 2, called GSA-Test, is given in Algorithm 1.