Statistical algorithms and a lower bound for detecting planted cliques

By Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Srinivas Vempala, Ying Xiao. 2012

247 citations recorded by the source corpus.

We introduce a framework for proving lower bounds on computational problems over distributions, based on a class of algorithms called statistical algorithms. 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, are statistical algorithms or have statistical counterparts. Our framework is inspired by and generalize the statistical query model in learning theory [34]. Our main application is a nearly optimal lower bound on the complexity of any statistical algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size O(n1/2-δ) for any constant δ > 0. Variants of these problems have been assumed to be hard to prove hardness for other problems and for cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, background): “7 We observe that the unifying treatment based on chi-square distance is reminiscent of the lower bounds for learning under statistical queries (SQ) derived in [24], [25], [47].”
Adversarial examples from computational constraints (2018, methodology): “The argument is fairly involved and uses the framework of [8] to reduce the question to that of upper bounding χ-correlation between the distributions.”
A tensor approach to learning mixed membership community models (2013, background): “While we obtained tight guarantees for MMSB models with uniform sized communities, our guarantees are weak when the community sizes are drastically different, such as in the planted clique setting where we do not match the computational lower bound [Feldman et al., 2012].”
Efficient Algorithms and Lower Bounds for Robust Linear Regression (2018, methodology): “A recent line of work [FGR + 13, FGV15, FPV15, Fel16a] developed a framework of SQ algorithms for search problems over distributions, which encompasses the linear regression problem studied here.”
A General Characterization of the Statistical Query Complexity (2016, methodology): “For completeness, we also describe the relationship to a simpler notion of average correlation introduced in (Feldman et al., 2012).”
Memory, Communication, and Statistical Queries (2016, methodology): “This model is equivalent to the 1-MSTAT(L) model (for L = 2b) considered by (Feldman et al., 2013b).”
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (2016, methodology): “, [18], [41] for a detailed discussion).”