Statistical Algorithms and a Lower Bound for Detecting Planted Clique

Introduction

We study the complexity of problems where the input consists of independent samples from an unknown distribution. Such problems are at the heart of machine learning and statistics (and their numerous applications) and also occur in many other contexts such as compressed sensing and cryptography. While several methods have been developed to estimate the sample complexity of such problems (e.g. VC dimension [Vapnik and Chervonenkis, 1971] and Rademacher complexity [Bartlett and Mendelson, 2002]), proving lower bounds on the computational complexity of these problems has been much more challenging. The traditional approach to proving lower bounds is via reductions and by finding distributions that can generate instances of some problem conjectured to be intractable (e.g., assuming $\mathsf{NP}\neq\mathsf{RP}$).

Here we present a different approach. We show that algorithms which access the unknown distribution only via a statistical query (SQ) oracle have high complexity, unconditionally. Most algorithmic approaches used in practice and in theory on a wide variety of problems can be implemented using only access to such an oracle; these include Expectation Maximization (EM) [Dempster et al., 1977], local search, MCMC optimization [Tanner and Wong, 1987, Gelfand and Smith, 1990], simulated annealing [Kirkpatrick et al., 1983, Černý, 1985], first and second order methods for linear/convex optimization, [Dunagan and Vempala, 2008, Belloni et al., 2009], $k$-means, Principal Component Analysis (PCA), Independent Component Analysis (ICA), Naïve Bayes, Neural Networks and many others (see [Chu et al., 2006] and [Blum et al., 2005] for proofs and many other examples). In fact, we are aware of only one algorithm that provably does not have a statistical query counterpart: Gaussian elimination for solving linear equations over a field (e.g. $\mod 2$).

Informally, a statistical query oracle provides an estimate of the expected value of any given bounded real-valued function within some tolerance. Many popular algorithms rely only on the average value of various functions over random samples (commonly referred to as empirical averages). Standard Chernoff-Hoeffding bounds imply that the average value of a bounded function on the independent samples will be highly concentrated around the expectation on the unknown distribution (and, indeed in many cases the empirical average is used precisely to obtain an estimate of the expectation). As a result such algorithms can often be equivalently analyzed in our oracle-based model.

Our approach also allows proving lower bounds against algorithms that rely on a $1$-bit sampling oracle, referred to as $1$-bit sampling algorithms. This oracle provides the value of any Boolean function on a fresh random sample from the distribution. Many existing algorithms require only such limited access to random samples. Others can be implemented using such access to samples (possibly using a polynomially larger number of samples). For brevity, we refer to algorithms that rely on either of these types of oracles as statistical algorithms.

For example, many problems over distributions are solved using convex programs. Such a problem is typically formulated as finding an approximation to $\min_{z\in K}\mathop{\mathbf{E}}_{x\sim D}[f(x,z)]$ for some convex set $K$ and functions $f(x,\cdot)$ that are convex in the second parameter $z$. A standard approach (both in theory and practice) to solve such a problem is to use a gradient descent-based technique. The gradient of the objective function is

and is usually estimated using the average value of $\nabla_{z}f(x,z)$ on (some of) the given random samples. However, standard analysis of gradient descent-based algorithms implies that a sufficiently accurate estimate of each of the coordinates of $\mathop{\mathbf{E}}_{x}[\nabla_{z}f(x,z)]$ would also suffice. Hence, for an objective function of the form above, gradient descent can be implemented using either of the above oracles (detailed analysis of such implementations can be found in a subsequent work [Feldman et al., 2015]).

The key motivation for our framework is the empirical observation that almost all algorithms that work on random samples are either already statistical in our sense or have natural statistical counterparts. Thus, lower bounds for statistical algorithms can be directly translated into lower bounds against a large number of existing approaches. We present the formal oracle-based definitions of statistical algorithms in Section 2.

Our model is based on the statistical query learning model [Kearns, 1998] defined as a restriction of Valiant’s PAC learning model. The primary goal of the restriction was to simplify the design of noise-tolerant learning algorithms. As was shown by Kearns and others in subsequent works, almost all classes of functions that can be learned efficiently can also be efficiently learned in the SQ model. A notable and so far unique exception is the algorithm for learning parities, based on Gaussian elimination. As was already shown by Kearns , parities require exponentially many queries to learn in the SQ model. Further, Blum et al. proved that the number of SQs required for weak learning (that is, for obtaining a non-negligible advantage over the random guessing) of a class of functions $C$ over a fixed distribution $D$ is characterized by a combinatorial parameter of $C$ and $D$, referred to as SQ-DIM$(C,D)$, the SQ dimension.

We consider SQ algorithms in the broader context of arbitrary computational problems over distributions. We also define an SQ oracle that strengthens the oracle introduced by Kearns . For any problem over distributions we define a parameter of the problem that lower bounds the complexity of solving the problem by any SQ algorithm in the same way that SQ-DIM lower bounds the complexity of learning in the SQ model. Our techniques for proving lower bounds are also based on methods developed for lower-bounding the complexity of SQ learning algorithms. However, as we will describe later, they depart from the known techniques in a number of significant ways that are necessary for our more general setting and our applications.

The $1$-bit sampling oracle and its more general $k$-bit version was introduced by Ben-David and Dichterman . They showed that it is equivalent (up to polynomial factors) to the SQ oracle. Using our stronger SQ oracle we sharpen this equivalence. This sharper relationship is crucial for obtaining meaningful lower bounds against $1$-bit sampling algorithms in our applications.

We demonstrate our techniques by applying them to the problems of detecting planted bipartite cliques and planted bipartite dense subgraphs. We now define these problems precisely and give some background.

Detecting Planted Cliques. In the planted clique problem, we are given a graph $G$ whose edges are generated by starting with a random graph $G_{n,1/2}$, then “planting,” i.e., adding edges to form a clique on $k$ randomly chosen vertices. Jerrum and Kucera introduced the planted clique problem as a potentially easier variant of the classical problem of finding the largest clique in a random graph [Karp, 1979]. A random graph $G_{n,1/2}$ contains a clique of size $2\log n$ with high probability, and a simple greedy algorithm can find one of size $\log n$. Finding cliques of size $(2-\epsilon)\log n$ is a hard problem for any $\epsilon>0$. Planting a larger clique should make it easier to find one. The problem of finding the smallest $k$ for which the planted clique can be detected in polynomial time has attracted significant attention. For $k\geq c\sqrt{n\log n}$, simply picking vertices of large degrees suffices [Kucera, 1995]. Cliques of size $k=\Omega(\sqrt{n})$ can be found using spectral methods [Alon et al., 1998, McSherry, 2001, Coja-Oghlan, 2010], via SDPs [Feige and Krauthgamer, 2000], combinatorial methods [Feige and Ron, 2010, Dekel et al., 2011], nuclear norm minimization [Ames and Vavasis, 2011] and belief propagation [Deshpande and Montanari, 2013].

While there is no known polynomial-time algorithm that can detect cliques of size below the threshold of $\Omega(\sqrt{n})$, there is a quasipolynomial algorithm for any $k\geq 2\log n$: enumerate subsets of size $2\log n$; for each subset that forms a clique, take all common neighbors of the subset; one of these will be the planted clique. This is also the fastest known algorithm for any $k=O(n^{1/2-\delta})$, where $\delta>0$.

Some evidence of the hardness of the problem was shown by Jerrum who proved that a specific approach using a Markov chain cannot be efficient for $k=o(\sqrt{n})$. Additional evidence of hardness is given in [Feige and Krauthgamer, 2003], where it is shown that Lovász-Schrijver SDP relaxations, which include the SDP used in [Feige and Krauthgamer, 2000], cannot be used to efficiently find cliques of size $k=o(\sqrt{n})$. Most recently, lower bounds against a constant level of the more powerful Sum-of-Squares SDP hierarchy were shown by Meka et al. and Deshpande and Montanari . The problem has been used to generate cryptographic primitives [Juels and Peinado, 2000], and as a hardness assumption in a large number of works (e.g. [Alon et al., 2007, Hazan and Krauthgamer, 2011, Minder and Vilenchik, 2009, Berthet and Rigollet, 2013, Dughmi, 2014]).

We focus on the bipartite planted clique problem, where a $(k\times k)$-biclique is planted in a random bipartite graph. A densest-subgraph version of the bipartite planted clique problem has been used as a hard problem for cryptographic applications [Applebaum et al., 2010]. The bipartite version can be easily seen to be at least as hard as the original version. At the same time all known bounds and algorithms for the $k$-clique problem can be easily adapted to the bipartite case (e.g. [Ames and Vavasis, 2011]). Therefore it is natural to expect that new upper bounds on the planted $k$-clique problem would also yield new upper bounds for the bipartite case.

The starting point of our investigation for this problem is the property of the planted $k$-biclique problem that it has an equivalent formulation as a problem over distributions defined as follows.

Fix an integer $k$, $1\leq k\leq n$, and a subset of $k$ indices $S\subseteq\{1,2,\ldots,n\}$. The input distribution $D_{S}$ on vectors $x\in\{0,1\}^{n}$ is defined as follows: with probability $1-(k/n)$, $x$ is uniform over $\{0,1\}^{n}$; and with probability $k/n$, $x$ is such that its $k$ coordinates from $S$ are set to $1$, and the remaining coordinates are uniform in $\{0,1\}$. For an integer $t$, the distributional planted $k$-biclique problem with $t$ samples is the problem of finding the unknown subset $S$ using $t$ samples drawn randomly from $D_{S}$.

One can view samples $x_{1},\ldots,x_{t}$ as adjacency vectors of the vertices of a bipartite graph as follows: the bipartite graph has $n$ vertices on the right (with $k$ marked as members of the clique) and $t$ vertices on the left. Each of the $t$ samples gives the adjacency vector of the corresponding vertex on the left. It is not hard to see that for $t=n$, conditioned on the event of getting exactly $k$ samples with planted indices, we will get a random bipartite graph with a planted $(k\times k)$-biclique (we prove the equivalence formally in Appendix A).

As we will see presently, these approaches can be easily implemented in our framework and will have provably high complexity. For the distributional planted biclique problem, SQ algorithms need $n^{\Omega(\log n)}$ queries to detect planted bicliques of size $k<n^{\frac{1}{2}-\delta}$ for any $\delta>0$. Even stronger exponential bounds apply for the more general problem of detecting planted dense subgraphs of the same size. These bounds match the known upper bounds. To describe these results precisely and discuss exactly what they mean for the complexity of these problems, we will need to define the models of statistical algorithms, the complexity measures we use, and our main tool for proving lower bounds, a notion of statistical dimension of a set of distributions. We do this in the next section. In Section 3 we prove our general lower bound results and in Section 5 we estimate the statistical dimension of detecting planted bicliques and dense subgraphs.

Definitions and Overview

Here we formally define statistical algorithms and the key notion of statistical dimension, and then describe the resulting lower bounds in detail.

We begin by formally defining the class of problems addressed by our framework.

For a domain $X$, let ${\mathcal{D}}$ be a set of distributions over $X$, let ${\mathcal{F}}$ be a set called solutions and ${\mathcal{Z}}:{\mathcal{D}}\rightarrow 2^{{\mathcal{F}}}$ be a map from a distribution $D\in{\mathcal{D}}$ to a subset of solutions ${\mathcal{Z}}(D)\subseteq{\mathcal{F}}$ that are defined to be valid solutions for $D$. The distributional search problem ${\mathcal{Z}}$ over ${\mathcal{D}}$ and ${\mathcal{F}}$ using $t$ samples is to find a valid solution $f\in{\mathcal{Z}}(D)$ given access (to an oracle or samples from) an unknown $D\in{\mathcal{D}}$.

In some settings it is natural to parameterize the set of valid solutions by additional parameters, such as accuracy. The extension of the definition to such settings is immediate. An example of a distributional search problem is the distributional planted $k$-biclique we described in Definition 1.1. In this case the domain $X$ is $\{0,1\}^{n}$, the set of input distributions is all the distributions with a planted $k$-biclique ${\mathcal{D}}=\{D_{S}\ |\ S\subset[n],\ |S|=k\}$ and the set of solutions is the set of all subsets of size $k$: ${\mathcal{F}}=\{S\ |\ S\subset[n],\ |S|=k\}$. For each $D_{S}$ there is a single valid solution $S$. For a second example, we point the reader to the distributional MAX-XOR-SAT problem in Section 4.

We note that this definition also captures decision problems by having ${\mathcal{F}}=\{0,1\}$. A simple example of a decision problem over distributions that is relevant to our discussion is that of distinguishing a planted biclique distribution from the uniform distribution over $\{0,1\}^{n}$ which we denote by $U$. Here the set of input distributions is ${\mathcal{D}}=\{U\}\cup\{D_{S}\ |\ S\subset[n],\ |S|=k\}$. The only valid solution for a planted biclique distribution $D_{S}$ is 1 and the only valid solution for $U$ is 0. For a solution $f\in{\mathcal{F}}$, we denote by ${\mathcal{Z}}_{f}$ the set of distributions in ${\mathcal{D}}$ for which $f$ is a valid solution.

It is important to note that the number of available random samples $t$ can have a major influence on the complexity of the problem. First, for most problems there is a minimum $t$ for which the problem is information-theoretically solvable. This value is often referred to as the sample complexity of the problem. But even for $t$ which is larger than the sample complexity of the problem, having more samples can make the problem easier computationally. For example, in the context of attribute-efficient learning, there is a problem that is intractable with few samples (under cryptographic assumptions) but is easy to solve with a larger (but still polynomial) number of samples [Servedio, 2000]. Our distributional planted biclique problem exhibits the same phenomenon.

2 Statistical Algorithms

The statistical query learning model of Kearns is a restriction of the PAC model [Valiant, 1984]. It introduces an oracle that allows a learning algorithm to obtain an estimate of the expectation of any bounded function of an example. A query to such an oracle is referred to as statistical query. Kearns showed that many known PAC learning algorithms can be expressed as algorithms using statistical queries instead of random examples themselves. The main goal of Kearns’ model was to give a simple way to design algorithms tolerant to random classification noise. Since the introduction of the model SQ algorithms have been given for many more learning tasks and the model itself found applications in a number of other contexts such as differential privacy [Blum et al., 2005, Kasiviswanathan et al., 2011], learning on massively parallel architectures [Chu et al., 2006] and evolvability [Feldman, 2008].

In the same spirit, for general search problems over a distribution, we define SQ algorithms as algorithms that do not see samples from the distribution but instead have access to a SQ oracle. The first SQ oracle we define is the natural generalization of the oracle defined by Kearns to samples from an arbitrary distribution.

Let $D$ be the input distribution over the domain $X$. For a tolerance parameter $\tau>0$, ${\mbox{STAT}}(\tau)$ oracle is the oracle that for any query function $h:X\rightarrow$, returns a value

The general algorithmic techniques mentioned earlier can all be expressed as algorithms using STAT oracle instead of samples themselves, in most cases in a straightforward way. We would also like to note that in the PAC learning model some of the algorithms, such as the Perceptron algorithm, did not initially appear to fall into the SQ framework but SQ analogues were later found for all known learning techniques except Gaussian elimination (for specific examples, see [Kearns, 1998] and [Blum et al., 1998]). We expect the situation to be similar even in the broader context of search problems over distributions.

The most natural realization of ${\mbox{STAT}}(\tau)$ oracle is one that computes $h$ on $O(1/\tau^{2})$ random samples from $D$ and returns their average. Chernoff’s bound implies that the estimate is within the desired tolerance (with constant probability). However, if $h(x)$ is very biased (e.g. equal to 0 with high probability), it can be estimated with fewer samples. Our primary application requires a tight bound on the number of samples necessary to solve a problem over distributions. Therefore we define a stronger version of STAT oracle which tightly captures the accuracy of an estimate of the expectation given by random samples. More formally, for a Boolean query function $h:X\rightarrow\{0,1\}$, ${\mbox{VSTAT}}(t)$ can return any value $v$ for which the Binomial distribution $B(t,v)$ (sum of $t$ independent Bernoulli variables with bias $v$) is statistically close (for some constant distance) to $B(t,\mathop{\mathbf{E}}[h])$. See Sec. 3.3 for more details on this correspondence.

Let $D$ be the input distribution over the domain $X$. For a sample size parameter $t>0$, ${\mbox{VSTAT}}(t)$ oracle is the oracle that for any query function $h:X\rightarrow$, returns a value $v\in\left[p-\tau,p+\tau\right],$ where $p=\mathop{\mathbf{E}}_{x\sim D}[h(x)]$ and $\tau=\max\left\{\frac{1}{t},\sqrt{\frac{p(1-p)}{t}}\right\}$.

Note that ${\mbox{VSTAT}}(t)$ always returns the value of the expectation within $1/\sqrt{t}$. Therefore it is no weaker than ${\mbox{STAT}}(1/\sqrt{t})$ and no stronger than ${\mbox{STAT}}(1/t)$.

The STAT and VSTAT oracles we defined can return any value within the given tolerance and therefore can make adversarial choices. We also aim to prove lower bounds against algorithms that use a more benign, $1$-bit sampling oracleIn the STOC 2013 extended abstract, this oracle is also called the unbiased statistical oracle. The $1$-bit sampling oracle gives the algorithm the true value of a Boolean query function on a randomly chosen sample. This oracle is a special case of the $k$-bit sampling oracle introduced by Ben-David and Dichterman who refer to it as the weak Restricted Focus of Attention (wRFA) model and is also equivalent to the Honest SQ oracle of Yang . Learning in this model has been studied in more recent work motivated by communication constraints on data processing in a distributed computing system. [Zhang et al., 2013, Steinhardt and Duchi, 2015, Steinhardt et al., 2016].

Let $D$ be the input distribution over the domain $X$. The 1-STAT oracle is the oracle that given any function $h:X\rightarrow\{0,1\}$, takes an independent random sample $x$ from $D$ and returns $h(x)$.

Note that the 1-STAT oracle draws a fresh sample upon each time it is called. Without re-sampling each time, the answers of the 1-STAT oracle could be easily used to recover any sample bit-by-bit, making it equivalent to having access to random samples. Note that the 1-STAT oracle can be used to simulate VSTAT (with high probability) by taking the average of $O(t)$ replies of 1-STAT for the same function $h$. While it might seem that access to 1-STAT gives an algorithm more power than access to VSTAT we will show that $t$ samples from 1-STAT can be simulated using access to ${\mbox{VSTAT}}(O(t))$. This will allow us to translate our lower bounds on SQ algorithms with access to VSTAT to lower bounds against $1$-bit sampling algorithms.

3 Statistical Dimension

The main tool in our analysis is an information-theoretic bound on the complexity of statistical algorithms. Our definitions originate from the statistical query (SQ) dimension [Blum et al., 1994] used to characterize SQ learning algorithms. Roughly speaking, the SQ dimension corresponds to the number of nearly uncorrelated labeling functions in a class (see Section 6.1 for the details of the definition and the relationship to our bounds).

We introduce a natural generalization and strengthening of this approach to search problems over arbitrary sets of distributions and prove lower bounds on the complexity of statistical algorithms based on the generalized notion. Our definition departs from SQ dimension in three aspects. (1) Our notion applies to any set of distributions; in the learning setting all known definitions of statistical dimension require fixing the distribution over the domain and only allow varying the labeling function. Such an extension was not known even in the context of PAC learning. (2) Instead of relying on a bound on pairwise correlations, our dimension relies on a bound on average correlations in a large set of distributions. This weaker condition allows us to derive tight bounds on the complexity of SQ algorithms for the planted $k$-biclique problem. (3) We show that our notion of dimension also gives lower bounds for the stronger VSTAT oracle (without incurring a quadratic loss in the parameter).

We now define our dimension formally. For two functions $f,g:X\rightarrow\mathop{\mathbf{R}}$ and a distribution $D$ with probability density function $D(x)$, the inner product of $f$ and $g$ over $D$ is defined as

The norm of $f$ over $D$ is $\|f\|_{D}=\sqrt{\langle f,f\rangle_{D}}$. We remark that, by convention, the integral from the inner product is taken only over the support of $D$, i.e. for $x\in X$ such that $D(x)\not=0$. Given a distribution $D$ over $X$ let $D(x)$ denote the probability density function of $D$ relative to some fixed underlying measure over $X$ (for example uniform distribution for discrete $X$ or Lebesgue measure over $\mathop{\mathbf{R}}^{n}$). Our bound is based on the inner products between functions of the following form: $(D^{\prime}(x)-D(x))/D(x)$ where $D^{\prime}$ and $D$ are distributions over $X$. For this to be well-defined, we will only consider cases where $D(x)=0$ implies $D^{\prime}(x)=0$, in which case $D^{\prime}(x)/D(x)$ is treated as 1. To see why such functions are relevant to our discussion, note that for every real-valued function $f$ over $X$,

This means that the inner product of any function $f$ with $(D^{\prime}-D)/D$ is equal to the difference of expectations of $f$ under the two distributions. Analyzing this quantity for an arbitrary set of functions $f$ was the high-level approach of statistical query lower bounds for learning. Here we depart from this approach, by defining a pairwise correlation of two distributions, independent of any specific query function. For two distributions $D_{1},D_{2}$ and a reference distribution $D$, their pairwise correlation is defined as:

When $D_{1}=D_{2}$, the quantity $\langle\frac{D_{1}}{D}-1,\frac{D_{1}}{D}-1\rangle_{D}$ is known as the $\chi^{2}(D_{1},D)$ distance and is widely used for hypothesis testing in statistics [Pearson, 1900].

A key notion for our statistical dimension is the average correlation of a set of distributions ${\mathcal{D}}^{\prime}$ relative to a distribution $D$. We denote it by $\rho({\mathcal{D}}^{\prime},D)$ and define as follows:

Bounds on pairwise correlations easily imply bounds on the average correlation (see Lemma 3.10 for a proof). In Section 3.2 we describe a pairwise-correlation version of our bounds. It is sufficient for some applications and generalizes the statistical query dimension from learning theory (see Section 6.1 for the details). However, to obtain our nearly tight lower bounds for planted biclique, we will need to bound the average pairwise correlation directly, and with significantly better bounds than what is possible from pairwise correlations alone.

We are now ready to define the concept of statistical dimension. We first define the statistical dimension with average correlation of a set of distributions relative to some reference distribution. It captures the complexity of distinguishing distributions in ${\mathcal{D}}$ from $D$.

Intuitively, the definition says that any $1/d$ fraction of the set of distributions has low pairwise correlation; the largest such $d$ is the statistical dimension.

For general search problems over distributions we define the statistical dimension by reducing it to the statistical dimension of some set of input distributions relative to some reference distribution.

The statistical dimension with average correlation $\bar{\gamma}$ of a search problem over distributions gives a lower bound on the complexity of any deterministic statistical algorithm for the problem that uses queries to ${\mbox{VSTAT}}(1/(3\bar{\gamma}))$.

At a high level, our proof works as follows. The first step of the proof is a reduction from a decision problem in which the algorithm only needs to distinguish all the distributions in the set ${\mathcal{D}}_{D}$ (except those in ${\mathcal{Z}}_{f}$ for some $f$) from the reference distribution $D$. To distinguish between distributions the algorithm needs to ask a query $g$ such that $\mathop{\mathbf{E}}_{D}[g]$ cannot be used as a response of ${\mbox{VSTAT}}(1/(3\bar{\gamma}))$ for $D^{\prime}\in{\mathcal{D}}_{f}$. In the key component of the proof we show that if a query function $g$ to ${\mbox{VSTAT}}(1/(3\bar{\gamma}))$ distinguishes between a distribution $D$ and any distribution $D^{\prime}\in{\mathcal{D}}^{\prime}$, then ${\mathcal{D}}^{\prime}$ must have average correlation of at least $\bar{\gamma}$ relative to $D$. The condition that for any $|{\mathcal{D}}^{\prime}|\geq|{\mathcal{D}}_{f}|/d$, $\rho({\mathcal{D}}^{\prime},D)<\bar{\gamma}$ then immediately implies that at least $d$ queries are required to distinguish any distribution in ${\mathcal{D}}_{f}$ from $D$. We remark that an immediate corollary of this proof technique is that the decision problem in which the algorithm needs to decide whether the input distribution is in ${\mathcal{D}}_{f}$ or is equal to the reference distribution $D$ also has statistical dimension at least $d$. We elaborate on this in Theorem 3.7 where we give a simplified version of our lower bound for decision problems of this type.

4 Applications to the Planted Biclique Problem

We prove the following lower bound for the distributional planted biclique problem.

For any constant $\delta>0$, any $k\leq n^{1/2-\delta}$ and $r>0$, at least $n^{\Omega(\log{r})}$ queries to ${\mbox{VSTAT}}(n^{2}/(rk^{2}))$ are required to solve the distributional planted $k$-biclique with probability at least $2/3$. In particular, no polynomial-time statistical algorithm can solve the problem using queries to ${\mbox{VSTAT}}(o(n^{2}/k^{2}))$ and any SQ algorithm requires $n^{\Omega(\log{n})}$ queries to ${\mbox{VSTAT}}(n^{2-\delta}/k^{2})$. This lower bound also applies to the problem of distinguishing any planted $k$-biclique distribution from the uniform distribution over $\{0,1\}^{n}$ (no planting).

This bound is essentially tight. For every index in the planted set $S$, the probability that the corresponding bit of a randomly chosen point is set to $1$ is $1/2+k/(2n)$, whereas for every index not in $S$, this probability is $1/2$. Therefore using $n$ queries to ${\mbox{VSTAT}}(16n^{2}/k^{2})$ (i.e., of tolerance $k/4n$) it is easy to recover $S$. Indeed, this can be done by using the query functions $h_{i}(x)=x_{i}$, for each $i\in[n]$. So, the answers of the VSTAT oracle represent the expected value of the $i$th bit over the sample.

There is also a SQ algorithm that uses $n^{O(\log{n})}$ queries to ${\mbox{VSTAT}}(25n/k)$ (corresponding to a significantly smaller number of samples) to find the planted set for any $k\geq\log n$. In fact, the same algorithm can be used for the standard planted clique problem that achieves complexity $n^{O(\log n)}$. We enumerate over subsets $T\subseteq[n]$ of $\log n$ indices and query ${\mbox{VSTAT}}(25n/k)$ with the function $g_{T}:\{0,1\}^{n}\rightarrow\{0,1\}$ defined as $1$ if and only if the point has ones in all coordinates in $T$. Therefore, if the set $T$ is included in the planted set then

With this expectation, ${\mbox{VSTAT}}(25n/k)$ has tolerance at most $\sqrt{k(k+1)/25n^{2}}\leq(k+1)/5n$ and will return at least $k/n-(k+1)/(5n)>3k/(4n)$. If, on the other hand, at least one element of $T$ is not from the planted set, then $\mathop{\mathbf{E}}_{D}[g_{T}]\leq k/(2n)+1/n$ and ${\mbox{VSTAT}}(25n/k)$ will return at most $(k+2)/(2n)+(k+2)/(5n)<3k/(4n)$. Thus, we will know all $(\log n)$-sized subsets of the planted set and hence the entire planted set. We remark that this algorithm demonstrates the difference between STAT and VSTAT oracles. Implementing this algorithm using the STAT oracle would require tolerance of $\Omega(k/n)$ which corresponds to $O(n^{2}/k^{2})$ samples. This is the same tolerance as the polynomial-time degree-based algorithm needs (estimate degree of each vertex), so one cannot hope to have a superpolynomial lower bound against ${\mbox{STAT}}(k/n)$.

To summarize, $n$ samples directly correspond to having access to ${\mbox{VSTAT}}(O(n))$. The discussion above shows that the distributional planted biclique problem can be solved in polynomial time when $k=\Omega(\sqrt{n})$. At the same time, Theorem 2.9 implies that for $k\leq n^{1/2-\delta}$, any SQ algorithm will require $n^{\Omega(\log{n})}$ queries to ${\mbox{VSTAT}}(n^{1+\delta})$.

We now turn to stating our bounds for $1$-bit sampling algorithms.

For any constant $\delta>0$ and any $k\leq n^{1/2-\delta}$, any $1$-bit sampling algorithm that with probability at least $2/3$ can distinguish between the uniform distribution and any planted $k$-biclique distribution requires $\Omega(n^{2}/k^{2})$ queries to 1-STAT.

A closely related problem is the planted densest subgraph problem, where edges in the planted subset appear with higher probability than in the remaining graph. This is a variant of the densest $k$-subgraph problem, which itself is a natural generalization of $k$-clique that asks to recover the densest $k$-vertex subgraph of a given $n$-vertex graph [Feige, 2002, Khot, 2004, Bhaskara et al., 2010, 2012]. The conjectured hardness of its average case variant, the planted densest subgraph problem, has been used in public key encryption schemes [Applebaum et al., 2010] and in analyzing parameters specific to financial markets [Arora et al., 2010]. We define the following distributional version of this problem:

Fix $0<q<p\leq 1$. For $1\leq k\leq n$, let $S\subseteq[n]$ be a set of $k$ vertex indices and $D_{S}$ be a distribution over $\{0,1\}^{n}$ such that when $x\sim D_{S}$, with probability $1-(k/n)$ the entries of $x$ are independently $q$-biased Bernoulli variables, and with probability $k/n$ the $k$ coordinates in $S$ are independently chosen $p$-biased Bernoulli variables, and the rest are independently chosen $q$-biased Bernoulli variables. The distributional $(p,q)$-planted densest $k$-subgraph problem is to find the unknown subset $S$ given access to samples from $D_{S}$.

Our approach and lower bounds extend in a straightforward manner to this problem. In Section 5.2 we analyze this general setting and give lower bounds for all settings of $p$ and $q$. Here we describe a special case of our lower bounds when $q=1/2$ and $p=1/2+\alpha$. Our lower bound becomes exponential as $\alpha$ becomes (inverse-polynomially) close to . Specifically:

The upper and lower bounds we described for statistical algorithms match the state of the art for the average-case planted $k$-biclique and planted $k$-clique problems. Moreover, our lower bounds for the distributional versions of the planted $k$-biclique problem have implications for the hardness of the average-case planted $k$-biclique problem. An instance of the latter problem is a random $n\times n$ bipartite graph with a $k\times k$ biclique planted randomly. In Appendix A, we show that the average-case planted $k$-biclique is equivalent to our distributional planted $k$-biclique with $n$ samples. Specifically, a single sample corresponds to the adjacency list of a vertex on the left, and $n$ samples correspond to the adjacency matrix of the bipartite graph. By this equivalence, an algorithm that solves the average-case planted bipartite $k$-clique problem will also solve the distributional planted $k$-biclique with $n$ samples. Our lower bounds for the distributional problem therefore imply that the planted $k$-biclique problem would require a non-statistical approach, i.e., one for which there is no statistical analogue.

5 Subsequent Work

In subsequent work, Feldman, Perkins and Vempala introduced a notion of statistical dimension that is based on the spectral norm of the correlation matrix of large sets of distributions. It is always at least as large as the average correlation-based dimension defined here and also leads to lower bounds on the complexity of SQ algorithms using VSTAT. Using this dimension they proved tight lower bounds on the complexity of statistical algorithms for planted $k$-SAT and Goldreich’s pseudo-random generator. In addition, they described statistical algorithms based on power iteration with nearly matching upper bounds. Finally, they demonstrate that lower bounds against SQ algorithms can be used to derive concrete lower bounds for convex relaxations of the problem.

Feldman et al. have also extended the lower bounds against 1-STAT to lower bounds against the $k$-bit version of 1-STAT at the expense of factor $2^{k}$ blow-up in the number of queries. Steinhardt, Valiant and Wager gave a more direct approach for proving lower bounds against this oracle that is closely related to the techniques here and in Feldman et al. . They have further showed that statistical queries can be used to simulate the oracle that that extracts $k$ bits from each sample in an interactive way (rather than at once).

Building on our approach, Feldman described new notions of statistical dimension and proved that they tightly characterize the SQ complexity of solving general search problems over distributions for both STAT and VSTAT oracle. He also simplified the analysis of ${\mbox{VSTAT}}(t)$ by showing that it is equivalent (up to constant factors) to returning any value $v$ such that $|\sqrt{v}-\sqrt{\mathop{\mathbf{E}}_{D}[h]}|\leq 1/\sqrt{t}$. Some additional recent applications of SQ lower bounds that are related to our work include learning of the Ising model [Bresler et al., 2014], convex optimization [Feldman et al., 2015] and distribution-independent PAC learning of lines over finite fields [Feldman, 2016].

The distributional planted $k$-biclique problem introduced here is a simple and natural problem that shows a remarkable property: information-theoretically it can be solved with many fewer samples than is necessary for any known efficient algorithm (and no efficient statistical algorithm exists). In particular, any algorithm that solves our problem with less than $n$ samples will also solve the average-case $k$-biclique problem (that is at least as hard as the usual planted $k$-clique problem). In several more recent works, reductions from the planted clique problem were used to demonstrate a similar phenomenon in a number of important problems in statistics and machine learning [Berthet and Rigollet, 2013, Ma and Wu, 2013, Hajek et al., 2015, Gao et al., 2014, Wang et al., 2014, Cai et al., 2015].

Lower Bounds from Statistical Dimension

In this section we prove the general lower bounds. In later sections, we will compute the parameters in these bounds for specific problems of interest.

We start by proving Theorem 2.7 which is the basis of all our lower bounds. In fact, we will prove a stronger version of this theorem which also applies to randomized algorithms. For this version we need an additional parameter in the definition of SDA.

We prove our lower bound by exhibiting a distribution over inputs (which are distributions over $X$) for which every deterministic SQ algorithm that solves ${\mathcal{Z}}$ with probability $\alpha$ (over the choice of input) requires at least $(\alpha-\eta)\cdot d/(1-\eta)$ calls to ${\mbox{VSTAT}}(1/(3\bar{\gamma}))$. The claim of the theorem will then follow by Yao’s minimax principle [Yao, 1977].

Using the notation of Definition 3.1, let $D$ be the reference distribution and ${\mathcal{D}}_{D}$ be a set of distributions for which the value $d$ is achieved. Let ${\mathcal{A}}$ be a deterministic SQ algorithm that uses $q$ queries to ${\mbox{VSTAT}}(1/(3\bar{\gamma}))$ to solve ${\mathcal{Z}}$ with probability $\alpha$ over the random and uniform choice of a distribution from ${\mathcal{D}}_{D}$. Consider the execution of ${\mathcal{A}}$ in which to each query $h$ of ${\mathcal{A}}$, the oracle returns exactly $\mathop{\mathbf{E}}_{D}[h]$ and let $f$ denote the output. Let the set ${\mathcal{D}}_{D}^{+}\subseteq{\mathcal{D}}_{D}$ be the set of distributions on which ${\mathcal{A}}$ is successful for all valid responses of ${\mbox{VSTAT}}(1/(3\bar{\gamma}))$. Let ${\mathcal{D}}^{+}={\mathcal{D}}_{f}\cap{\mathcal{D}}_{D}^{+}$ (recall that we defined ${\mathcal{D}}_{f}={\mathcal{D}}_{D}\setminus{\mathcal{Z}}_{f}$). We observe that ${\mathcal{D}}^{+}={\mathcal{D}}_{D}^{+}\setminus({\mathcal{D}}_{D}\setminus{\mathcal{D}}_{f})$ and therefore

Let $h_{1},h_{2},\ldots,h_{q}$ be the queries asked by ${\mathcal{A}}$ when executed on $D$ with the exact responses of the oracle. Let $m=|{\mathcal{D}}^{+}|$ and we denote the distributions in ${\mathcal{D}}^{+}$ by $\{D_{1},D_{2},\ldots,D_{m}\}$. For every $k\leq q$, let $A_{k}$ be the set of all distributions $D_{i}$ such that

where we use $t$ to denote $1/(3\bar{\gamma})$ and $p_{i,k}$ to denote $\mathop{\mathbf{E}}_{D_{i}}[h_{k}(x)].$ To prove the desired bound we first prove the following two claims:

for every $k\leq q$, $|A_{k}|\leq|{\mathcal{D}}_{f}|/d$.

Combining these two implies that $q|{\mathcal{D}}_{f}|/d\geq m$ or, equivalently, $q\geq d|{\mathcal{D}}^{+}|/|{\mathcal{D}}_{f}|$.

To prove the second claim, suppose that for some $k\in[d]$, $|A_{k}|>|{\mathcal{D}}_{f}|/d$. Let $p_{k}=\mathop{\mathbf{E}}_{D}[h_{k}(x)]$ and assume that $p_{k}\leq 1/2$ (when $p_{k}>1/2$ we just replace $h_{k}$ by $1-h_{k}$ in the analysis below). First we note that:

Let $\hat{D}_{i}(x)=\frac{D_{i}(x)}{D(x)}-1$, (where the convention is that $\hat{D}_{i}(x)=0$ if $D(x)=0$). We will next show upper and lower bounds on the following quantity

To evaluate the last term of this inequality we use the fact that $|p_{i,k}-p_{k}|\geq\tau_{i,k}=\max\{1/t,\sqrt{p_{i,k}(1-p_{i,k})/t}\}$. Next we use a simple fact (proved in Lemma 3.5 below) that $|p_{i,k}-p_{k}|\geq\max\{1/t,\sqrt{p_{i,k}(1-p_{i,k})/t}\}$ implies that $|p_{k}-p_{i,k}|\geq\sqrt{\frac{\min\{p_{k},1-p_{k}\}}{3t}}$ to obtain: For every $D_{i}\in A_{k}$,

By substituting equation (4) into (3) we get that $\Phi^{2}\geq\frac{p_{k}}{3t}\cdot|A_{k}|^{2}$.

We remark that for algorithms using the STAT oracle, the proof can be simplified somewhat. For $\tau=\sqrt{\bar{\gamma}}$,

and the proof could be obtained by directly combining equations (2) and (3) to get a contradiction. This also eliminates the factor of $3$ in the bound and the assumption that queries are $$-valued can be relaxed to$$-valued queries since it suffices that $\|h_{k}\|^{2}\leq 1$. This leads to an identical lower bound on the number of queries for ${\mbox{STAT}}(\sqrt{\bar{\gamma}})$ in place of ${\mbox{VSTAT}}(1/(3\bar{\gamma}))$.

We now prove a bound on the distance between any $p\in$ and $p^{\prime}$ which is returned by ${\mbox{VSTAT}}(t)$ on a query with expectation $p$ in terms of $p^{\prime}$ that we used in the proof of Lemma 3.3.

For an integer $t$ and any $p\in$, let $p^{\prime}\in$ be such that $|p^{\prime}-p|\geq\tau=\max\left\{\frac{1}{t},\sqrt{\frac{p(1-p)}{t}}\right\}$. Then $|p^{\prime}-p|\geq\sqrt{\frac{\min\{p^{\prime},1-p^{\prime}\}}{3t}}$.

First note that our conditions and bounds do not change if we replace both $p$ and $p^{\prime}$ with $1-p$ and $1-p^{\prime}$, respectively. Therefore it is sufficient to prove the bound when $p\leq 1/2$. We know that $|p^{\prime}-p|\geq\tau=\max\{1/t,\sqrt{p(1-p)/t}\}$. If $p\geq 2p^{\prime}/3$ then certainly

Otherwise (when $p<2p^{\prime}/3$), $p^{\prime}-p\geq p^{\prime}-2p^{\prime}/3=p^{\prime}/3$. We also know that $|p-p^{\prime}|\geq\tau\geq 1/t$ and therefore $|p-p^{\prime}|\geq\sqrt{\frac{p^{\prime}}{3t}}$. ∎

For decision problems, our dimension and lower bounds can be simplified. We denote by ${\mathcal{B}}({\mathcal{D}},D)$ a decision problem in which the input distribution $D^{\prime}$ either equals $D$ or belongs to ${\mathcal{D}}$ and the goal of the algorithm is to identify whether $D^{\prime}=D$ or $D^{\prime}\in{\mathcal{D}}$. For example, for the distributional planted $k$-biclique problem, the decision version is to determine whether the given input distribution corresponds to a planted $k$-biclique or to one with no planting (uniform distribution on $\{0,1\}^{n}$.

For the decision problem ${\mathcal{B}}({\mathcal{D}},D)$ our notion of dimension simplifies to the following.

Our technique gives the following lower bound for decision problems:

${\mathcal{A}}$ has success probability $\alpha>1/2$ and therefore, when executed on $D$ with exact responses to queries, it must correctly identify $D$ (say it outputs 0 in this case). We then define ${\mathcal{D}}^{+}\subseteq{\mathcal{D}}_{D}$ as the set of distributions on which ${\mathcal{A}}$ is successful (that is outputs $1$). The probability of success of ${\mathcal{A}}$ implies that $|{\mathcal{D}}^{+}|\geq(2\alpha-1)|{\mathcal{D}}_{D}|$. Now, the set ${\mathcal{D}}_{D}$ is included in the set of distributions ${\mathcal{D}}$ for which is not a valid solution. Therefore we can apply Lemma 3.3 with ${\mathcal{D}}_{f}={\mathcal{D}}_{D}$ to obtain that the number of queries to ${\mbox{VSTAT}}(1/(3\bar{\gamma}))$ is $q\geq(2\alpha-1)d$. ∎

2 Statistical Dimension Based on Pairwise Correlations

We say that a set of $m$ distributions ${\mathcal{D}}=\{D_{1},\ldots,D_{m}\}$ over $X$ is $(\gamma,\beta)$-correlated relative to a distribution $D$ over $X$ if:

3 Lower Bounds for 111-bit Sampling Algorithms

Next we address lower bounds on algorithms that use the 1-STAT oracle. We recall that the 1-STAT oracle returns the value of a function on a single randomly chosen point. To estimate the expectation of a function, an algorithm can simply query this oracle multiple times with the same function and average the results.

We note that responses of 1-STAT do not have the room for the possibly adversarial deviation afforded by the tolerance of the STAT and VSTAT oracles. The ability to use these slight deviations in a coordinated way is used crucially in our lower bounds against VSTAT and in all known lower bounds for SQ learning algorithms. While it is possible to derive lower bounds against $1$-bit sampling algorithms using $m$ queries from lower bounds against algorithms that use $O(m)$ queries to ${\mbox{STAT}}(1/m)$ [Ben-David and Dichterman, 1998], such lower bound will not suffice for our main application. It would only imply the trivial lower bound of $\Omega(n/k)$ queries to 1-STAT for the planted $k$-biclique problem. Proving tighter lower bounds against $1$-bit sampling algorithms directly is harder and indeed lower bounds for the equivalent Honest SQ learning model required a substantially more involved argument than lower bounds for the regular SQ model [Yang, 2005].

Our lower bounds for $1$-bit sampling algorithms rely on a direct simulation of the 1-STAT oracle using the VSTAT oracle. This simulation allows us to derive lower bounds against $1$-bit sampling algorithms from Theorem 3.2. We also provide a reverse simulation of VSTAT oracle using 1-STAT oracle.

Let ${\mathcal{Z}}$ be a search problem and let ${\mathcal{A}}$ be a (possibly randomized) $1$-bit sampling algorithm that solves ${\mathcal{Z}}$ with probability at least $\alpha$ using $m$ samples from 1-STAT. For any $\delta\in(0,1/4]$, there exists a SQ algorithm ${\mathcal{A}}^{\prime}$ that uses at most $m$ queries to ${\mbox{VSTAT}}(m/\delta^{2})$ and solves ${\mathcal{Z}}$ with probability at least $\alpha-\delta$.

Our proof relies on a simple simulation. Given query $h_{1}:X\rightarrow\{0,1\}$ from ${\mathcal{A}}$ to 1-STAT, we make the same query $h_{1}$ to ${\mbox{VSTAT}}(t)$ for $t=m/\delta^{2}$. Let $p^{\prime}_{1}$ be the response. We flip a coin with bias $p^{\prime}_{1}$ (that is one that outputs $1$ with probability $p^{\prime}_{1}$ and with probability $1-p^{\prime}_{1}$) and return it to the algorithm. We do the same for the remaining $m-1$ queries which we denote by $h_{2},h_{3},\ldots,h_{m}$. We then prove that the true $m$ samples of 1-STAT and our simulated coin flips are statistically close by upper bounding the expected ratio of their density functions (which is equal to the $\chi^{2}$ divergence plus 1) . This implies that the success probability of the simulated algorithm is not much worse than that of the $1$-bit sampling algorithm.

In our proof we will, for simplicity and without loss of generality, assume that ${\mbox{VSTAT}}(t)$ always outputs a value in the interval $[1/t,1-1/t]$. We can always replace a value $v$ returned by ${\mbox{VSTAT}}(t)$ by $v^{\prime}$ which is the closest value to $v$ in the above interval. It is easy to see that if $v$ is a valid answer of ${\mbox{VSTAT}}(t)$ then so is $v^{\prime}$.

We will need the following lemmas for our proof. The first one bounds the total variation distance between two distributions in terms of the expected ratio of probability density functions.

Let $D_{1}$ and $D_{2}$ be two distribution over a domain $X$ of finiteThis assumption is simply for convenience of notation. It holds in our applications. size such that $D_{2}(x)$ is non-vanishing. Denote the total variation distance between $D_{1}$ and $D_{2}$ by $\Delta_{TV}(D_{1},D_{2})$. Then $\Delta_{TV}(D_{1},D_{2})\leq\sqrt{\rho}/2$, where $\rho=\mathop{\mathbf{E}}_{D_{1}}\left[\frac{D_{1}(x)}{D_{2}(x)}\right]-1$.

The key observation is that the $\chi^{2}$-divergence between $D_{1}$ and $D_{2}$ is exactly the expected ratio minus 1.

The second lemma is that if $p^{\prime}$ is an answer of ${\mbox{VSTAT}}(t)$ for a query $h$, such that $\mathop{\mathbf{E}}_{D}[h]=p$, then the expected ratio of density functions of Bernoulli random variables with biases $p$ and $p^{\prime}$, denoted $B(p)$ and $B(p^{\prime})$, is small.

For an integer $t$ and $p\in$ let $p^{\prime}\in[1/t,1-1/t]$ such that $|p^{\prime}-p|\leq\max\left\{\frac{1}{t},\sqrt{\frac{p(1-p)}{t}}\right\}$. Then

If $b=1$, the ratio is $p/p^{\prime}$ and when $b=0$, then it is $(1-p)/(1-p^{\prime})$. Thus, the expected ratio is

We can assume without loss of generality that $p^{\prime}\leq 1/2$.

Now if $p\leq 3p^{\prime}$ then $p(1-p)\leq 3p^{\prime}(1-p^{\prime})$. Otherwise (when, $p>3p^{\prime}$), we know that $p\geq 3p^{\prime}\geq 3/t$. This implies that $p-p^{\prime}\geq 2p/3\geq 2/t$. This means that

This can only be true when $p\leq(3/2)^{2}/t=9/(4t)$, contradicting our assumption that $p\geq 3/t$. This implies that

By using this bound in the ratio equation we get that

We can now complete the proof of Theorem 3.13.

We simulate ${\mathcal{A}}$ using ${\mbox{VSTAT}}(t)$ as described above. We now prove that for any algorithm the total variation distance between the true answers of 1-STAT and the simulated distribution is at most $\delta$. Formally, let $R$ denote the set of all outcomes of ${\mathcal{A}}$’s random bits and for $r\in R$, let ${\mathcal{A}}^{r}$ denote the execution of ${\mathcal{A}}$ when its random bits are set to $r$. let $\Pi_{\mathcal{A}}$ denote the distribution over the $m$ bits obtained by the algorithm ${\mathcal{A}}$ when it is run with 1-STAT oracle. Similarly, let $\Pi^{\prime}_{\mathcal{A}}$ denote the distribution over $\{0,1\}^{m}$ obtained by running the algorithm ${\mathcal{A}}$ simulated using ${\mbox{VSTAT}}(t)$ as above. By definition, $\Pi_{\mathcal{A}}=\mathop{\mathbf{E}}_{r\in R}\Pi_{{\mathcal{A}}^{r}}$ and similarly $\Pi^{\prime}_{\mathcal{A}}=\mathop{\mathbf{E}}_{r\in R}\Pi^{\prime}_{{\mathcal{A}}^{r}}$. This implies that,

The algorithm ${\mathcal{A}}^{r}$ is deterministic and it is therefore sufficient to prove the bound on total variation distance for deterministic algorithms. For conciseness we assume henceforth that ${\mathcal{A}}$ is deterministic.

For any $i\in[m]$ let $\Pi_{{\mathcal{A}}_{i}}$ denote the probability distribution on the first $i$ samples of ${\mathcal{A}}$ executed with 1-STAT. For $j\leq i$ let $z^{j}$ denote the first $j$ bits of $z$. Let $\Pi_{{\mathcal{A}}_{i}}(z\ |\ z^{i-1})$ denote the probability that the first $i$ samples of ${\mathcal{A}}$ executed with 1-STAT oracle are equal to $z$ conditioned on the probability that the first $i-1$ samples are equal to $z^{i-1}$. We define $\Pi^{\prime}_{{\mathcal{A}}_{i}}(z)$ and $\Pi^{\prime}_{{\mathcal{A}}_{i}}(z\ |\ z^{i-1})$ analogously. We also denote by $h_{z}$ the query that ${\mathcal{A}}$ asks after getting $z$ as the response to first $i$ samples and let $p_{z}=\mathop{\mathbf{E}}_{D}[h_{z}]$. Let $p^{\prime}_{z}$ denote the response of ${\mbox{VSTAT}}(t)$ on $h_{z}$.

For $i\in[m]$ and any $z\in\{0,1\}^{i}$, $\Pi_{{\mathcal{A}}_{i}}(z\ |\ z^{i-1})=\mathop{\mathbf{Pr}}[B(p_{z^{i-1}})=z_{i}]$ and hence $\Pi_{{\mathcal{A}}_{i}}(z)=\Pi_{{\mathcal{A}}_{i-1}}(z^{i-1})\mathop{\mathbf{Pr}}[B(p_{z^{i-1}})=z_{i}]$. Similarly, $\Pi^{\prime}_{{\mathcal{A}}_{i}}(z\ |\ z^{i-1})=\mathop{\mathbf{Pr}}[B(p^{\prime}_{z^{i-1}})=z_{i}]$ and $\Pi^{\prime}_{{\mathcal{A}}_{i}}(z)=\Pi^{\prime}_{{\mathcal{A}}_{i-1}}(z^{i-1})\mathop{\mathbf{Pr}}[B(p^{\prime}_{z^{i-1}})=z_{i}]$. This implies that:

Now by Lemma 3.15, this implies that for any $z$ of length $i\in[m]$,

By our definition, $t=m/\delta^{2}\geq 16m$. Therefore, $3m/t\leq 1/5$ and hence $e^{3m/t}\leq 1+4m/t$. By Lemma 3.14, we get that $\Delta_{TV}(\Pi_{\mathcal{A}},\Pi^{\prime}_{\mathcal{A}})\leq\sqrt{(1+4m/t-1)}/2=\sqrt{m/t}=\delta$. This implies that the success probability of ${\mathcal{A}}$ using the simulated oracle is at least $\alpha-\delta$.

We now combine Theorems 3.7 and 3.13 to obtain the following lower bound for decision problems.

In particular, any algorithm with success probability of at least $2/3$ requires at least $\min\{d/6,1/(432\bar{\gamma})\}$ queries to 1-STAT.

Assuming the existence of a $1$-bit sampling algorithm using less than $m$ queries, we apply Theorem 3.13 for $\delta=(2\alpha-1)/4$ to simulate the algorithm using VSTAT. The bound on $m$ ensures that the resulting algorithm uses less than $d(2\alpha-1)/2$ queries to ${\mbox{VSTAT}}(\frac{1}{3\bar{\gamma}})$ and has success probability of at least $\alpha-\delta=(2\alpha+1)/4$. By substituting these parameters into Theorem 3.7 we obtain a contradiction. ∎

For general search problems this leads to the following lower bound.

In particular, if $\eta\leq 1/6$ then any algorithm with success probability of at least $2/3$ requires at least $\min\{d/4,1/(48\bar{\gamma})\}$ queries to 1-STAT.

To conclude, we formally state a simple reduction in the other direction, namely that ${\mbox{VSTAT}}(t)$ oracle can be simulated using the 1-STAT oracle. It has been observed that, given a Boolean query function $h$ one can obtain an estimate of $\mathop{\mathbf{E}}_{D}[h]$ using $t=O(\log(1/\delta)/\tau^{2})$ $1$-bit samples which with probability at least $1-\delta$ will be within $\tau$ of $\mathop{\mathbf{E}}_{D}[h]$ [Ben-David and Dichterman, 1998]. Using the multiplicative Chernoff bound, it is not hard to see that $O(t\log(1/\delta))$ samples are sufficient to estimate $p=\mathop{\mathbf{E}}_{D}[h]$ within tolerance guaranteed by ${\mbox{VSTAT}}(t)$. In addition, we will show how to use 1-STAT oracle to estimate the expectation of real-valued queries.

Let $t,q>0$ be any integers and $\delta>0$. There exists an algorithm ${\mathcal{A}}^{\prime}$ that for any input distribution $D$ and any algorithm ${\mathcal{A}}$ that asks at most $q$ queries to VSTAT, with probability at least $1-\delta$, provides valid for ${\mbox{VSTAT}}(t)$ answers to all the queries of ${\mathcal{A}}$. ${\mathcal{A}}^{\prime}$ uses $O(qt\cdot\log(q/\delta))$ queries to 1-STAT for the same input distribution $D$.

For every query $h:X\rightarrow$ of ${\mathcal{A}}$, the algorithm ${\mathcal{A}}^{\prime}$ estimates $p=\mathop{\mathbf{E}}_{D}[h]$ as follows. To generate a random Bernoulli variable with bias $p$, ${\mathcal{B}}$ draws $\theta\in$ randomly and uniformly and defines: $h_{\theta}(x)=1$ if $h(x)\leq\theta$ and $h_{\theta}(x)=0$ otherwise. It then makes the query $h_{\theta}$ to 1-STAT. Observe that

The algorithm ${\mathcal{B}}$ repeats this $m$ times (each time choosing a new random $\theta$) and then answers the query $h$ with the mean of the obtained samples (for $m$ to be defined later). We denote the mean by $v$.

Assuming that $p\leq 1/2$, multiplicative Chernoff bounds imply that

The bound in the case of $p>1/2$ follows from the symmetric argument.

Choosing $m=6t\cdot\ln(2q/\delta)$ ensures that $\mathop{\mathbf{Pr}}[|v-p|\geq\sqrt{p(1-p)/t}]\leq\delta/q$. This implies that $q$ arbitrary queries for ${\mbox{VSTAT}}(t)$ can be answered correctly with probability at least $1-\delta$ using $6qt\cdot\ln(2q/\delta)$ queries to 1-STAT. ∎

Warm-up: MAX-XOR-SAT

In this section, we demonstrate our techniques on a warm-up problem, MAX-XOR-SAT. For this problem, it is sufficient to use pairwise correlations, rather than average correlations.

For $\epsilon\geq 0$, the $\epsilon$-approximate MAX-XOR-SAT problem is defined as follows. Given samples from some unknown distribution $D$ over XOR clauses on $n$ variables, find an assignment that maximizes up to additive error $\epsilon$ the probability a random clause drawn from $D$ is satisfied.

In the worst case, it is known that MAX-XOR-SAT is NP-hard to approximate to within $1/2-\delta$ for any constant $\delta$ [Håstad, 2001]. In practice, local search algorithms such as WalkSat [Selman et al., 1995] are commonly applied as heuristics for maximum satisfiability problems. We give strong evidence that the distributional version of MAX-XOR-SAT is hard for algorithms that locally seek to improve an assignment by flipping variables as to satisfy more clauses, giving some theoretical justification for the observations of [Selman et al., 1995]. Moreover, our proof even applies to the case when there exists an assignment that satisfies all the clauses generated by the target distribution.

The bound we obtain can be viewed as a restatement of the known lower bound for learning parities using statistical query algorithms (indeed, the problem of learning parities is a special case of our distributional MAX-XOR-SAT).

To formalize the search problem, we will denote by $C=\{0,1\}^{n}$ the set of XOR clauses in $n$ variables, such that for $c\in C$, if for $i\in[n]$ we have $c_{i}=1$ then the $i$th variable appears in $c$, and otherwise it does not; for simplicity, no variables are negated in the clauses. Let $A=\{0,1\}^{n}$ denote the set of possible assignments to the variables. We will say that the assignment $a\in A$ satisfies the clause $c\in C$ if $a\cdot c=1$ (where $a\cdot c$ denotes the inner product modulo $2$).