Statistical algorithms and a lower bound for detecting planted cliques

DOI10.1145/3046674MaRDI QIDQ4640281zbMATH OpenOpenAlexFDO

Authors Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Ying Xiao, Santosh S. Vempala

Publication date 17 May 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.1214

zbMATH Keywords

learning theorylower boundsplanted cliquestatistical algorithmsstatistical dimension

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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.

Recommendations

• Statistical algorithms and a lower bound for detecting planted cliques
• Finding a planted clique by adaptive probing
• Sum-of-squares Lower Bounds for Planted Clique
• On the complexity of random satisfiability problems with planted solutions
• On the complexity of random satisfiability problems with planted solutions (extended abstract)

Cited in

(24)

• Statistical algorithms and a lower bound for detecting planted cliques
• On the complexity of random satisfiability problems with planted solutions
• A nearly tight sum-of-squares lower bound for the planted clique problem
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Algorithmic obstructions in the random number partitioning problem
• Tensor clustering with planted structures: statistical optimality and computational limits
• Computational barriers in minimax submatrix detection
• Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
• Finding a planted clique by adaptive probing
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• Almost-Linear Planted Cliques Elude the Metropolis Process
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• Computational barriers to estimation from low-degree polynomials
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• Bilu-Linial stability, certified algorithms and the independent set problem
• Estimation of Wasserstein distances in the spiked transport model
• The overlap gap property in principal submatrix recovery
• Polynomial‐time universality and limitations of deep learning
• Computational lower bounds for graphon estimation via low-degree polynomials
• Average-case complexity of tensor decomposition for low-degree polynomials
• Statistical query lower bounds for tensor PCA
• On the complexity of random satisfiability problems with planted solutions (extended abstract)
• Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
• Adversarial manifold estimation

This page was built for publication: Statistical algorithms and a lower bound for detecting planted cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4640281)