The Complexity of Statistical Algorithms

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. VempalaarXiv 2012 · arXiv · OpenReview

Abstract: We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle. For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution, rather than directly accessing samples. Most natural algorithms of interest in theory and in practice, e.g., moments-based methods, local search, standard iterative methods for convex optimization, MCMC and simulated annealing can be implemented in this framework. Our framework is based on, and generalizes, the statistical query model in learning theory (Kearns, 1998). Our main application is a nearly optimal lower bound on the complexity of any statistical query algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size $O(n^{1/2-\delta})$ for any constant $\delta > 0$. The assumed hardness of variants of these problems has been used to prove hardness of several other problems and as a guarantee for security in cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.

Introduction

In computational complexity theory, we frequently encounter problems that appear difficult to solve, yet proving their inherent hardness remains elusive. Most existing hardness results are conditional, relying on unproven assumptions such as $P \neq NP$. However, in the context of statistical problems—where the input consists of samples from an unknown distribution—it is possible to prove unconditional lower bounds for specific classes of algorithms.

This paper introduces a robust framework for establishing these bounds against "statistical algorithms." This category encompasses a vast majority of techniques used in modern machine learning and optimization, including Markov Chain Monte Carlo (MCMC), Gradient Descent, Expectation-Maximization (EM), and simulated annealing. By analyzing the fundamental limits of these methods, we provide a theoretical justification for why certain problems, such as detecting a "planted clique" in a random graph, remain computationally intractable despite decades of algorithmic effort.

The Statistical Query (SQ) Framework

The core of this research is the Statistical Query (SQ) model, originally proposed by Kearns (1998) for learning theory and generalized here for broader distributional problems. In this model, an algorithm does not interact with raw data samples directly. Instead, it interacts with a statistical query oracle.

To gain information about a distribution $D$, the algorithm submits a function $f$ to the oracle, which returns an estimate of the expected value $E_{x \sim D}[f(x)]$. This abstraction captures the essence of "natural" algorithms that rely on aggregate statistics rather than individual data points.

Key Innovations in the Framework

  1. The VSTAT Oracle: The authors introduce a refined oracle, $VSTAT(L)$, which more accurately models the power of an algorithm given a budget of $L$ samples. This allows for tighter, more realistic lower bounds than previous SQ models.
  2. Statistical Dimension (SDA): This is the framework's primary analytical tool. SDA is a combinatorial parameter that measures how many "nearly independent" versions of a problem exist. If a problem possesses a high statistical dimension, any SQ algorithm will require an exponentially large number of queries to distinguish the target distribution from noise.
  3. Average Correlation: By shifting the focus from pairwise correlations to average correlations across a set of distributions, the authors provide a more powerful method for proving hardness in complex problems like the Planted Clique.

The Planted Clique Problem and the $\sqrt{n}$ Barrier

The primary application of this framework is the Planted Clique problem. In this scenario, a small, fully connected subgraph (a clique) of size $k$ is hidden within a large random graph of $n$ nodes.

While simple algorithms can find a clique when $k \geq \sqrt{n}$, finding smaller cliques (where $k = O(n^{1/2-\delta})$) has long been suspected to be hard. This paper provides the first nearly optimal lower bound for this problem within the SQ framework. It demonstrates that for cliques smaller than the $\sqrt{n}$ threshold, any statistical algorithm requires super-polynomial ($n^{\Omega(\log n)}$) or even exponential queries to detect the planted structure.

This result is significant because the assumed hardness of the Planted Clique problem serves as the foundation for many other proofs in high-dimensional statistics and cryptography. Providing concrete evidence of its hardness for statistical algorithms reinforces these broader theoretical structures.

The "Gaussian Exception"

An important nuance of this research is the identification of what statistical algorithms cannot do. The authors highlight Gaussian Elimination as a prime example of a non-statistical algorithm. Algorithms that exploit the precise algebraic structure of data—such as solving linear equations over a finite field—do not fit the SQ model. This explains a well-known phenomenon in computer science: problems like "learning parities" are trivial for Gaussian elimination but impossible for any standard statistical method.

Conclusion and Future Impact

By formalizing the limits of statistical algorithms, this work provides a roadmap for understanding the Information-Computation Gap—the space where a problem may be statistically solvable (given enough data) but computationally impossible (given realistic time and algorithms).

While the bounds are restricted to statistical methods, the ubiquity of these methods in practice suggests that the $n^{1/2}$ barrier for Planted Clique is a fundamental feature of the computational landscape. Future work may extend this framework to other critical areas, such as Sparse Principal Component Analysis (PCA) and community detection in social networks, further mapping the boundaries of what our most common algorithms can achieve.

Summary updated

Abstract

We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle. For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution, rather than directly accessing samples. Most natural algorithms of interest in theory and in practice, e.g., moments-based methods, local search, standard iterative methods for convex optimization, MCMC and simulated annealing can be implemented in this framework. Our framework is based on, and generalizes, the statistical query model in learning theory (Kearns, 1998). Our main application is a nearly optimal lower bound on the complexity of any statistical query algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size $O(n^{1/2-\delta})$ for any constant $\delta > 0$. The assumed hardness of variants of these problems has been used to prove hardness of several other problems and as a guarantee for security in cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.
BibTeX
@misc{feldman2012complexity,
  author = {Vitaly Feldman and Elena Grigorescu and Lev Reyzin and Santosh S. Vempala},
  title = {{The Complexity of Statistical Algorithms}},
  year = {2012},
  eprint = {1201.1214},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1201.1214},
}
Figure