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

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

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

(41)

• The overlap gap property in principal submatrix recovery
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Tensor clustering with planted structures: statistical optimality and computational limits
• Computational barriers to estimation from low-degree polynomials
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• Computational barriers in minimax submatrix detection
• Estimation of Wasserstein distances in the spiked transport model
• Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
• On the complexity of random satisfiability problems with planted solutions (extended abstract)
• On the complexity of random satisfiability problems with planted solutions
• A nearly tight sum-of-squares lower bound for the planted clique problem
• Statistical query lower bounds for tensor PCA
• Bilu-Linial stability, certified algorithms and the independent set problem
• Finding a planted clique by adaptive probing
• Statistical algorithms and a lower bound for detecting planted cliques
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• Polynomial‐time universality and limitations of deep learning
• Adversarial manifold estimation
• Algorithmic obstructions in the random number partitioning problem
• Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
• Almost-Linear Planted Cliques Elude the Metropolis Process
• Average-case complexity of tensor decomposition for low-degree polynomials
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• Computational lower bounds for graphon estimation via low-degree polynomials
• Subsampling suffices for adaptive data analysis
• Low-degree security of the planted random subgraph problem
• Finding planted cliques using gradient descent
• Sharp thresholds in inference of planted subgraphs
• Precise error rates for computationally efficient testing
• Clustering a mixture of Gaussians with unknown covariance
• Almost-linear planted cliques elude the Metropolis process
• SQ lower bounds for random sparse planted vector problem
• Sampling without compromising accuracy in adaptive data analysis
• Tensor factor model estimation by iterative projection
• The strongish planted clique hypothesis and its consequences
• Is the space complexity of planted clique recovery the same as that of detection?
• Computational complexity of deep learning: fundamental limitations and empirical phenomena
• Computational lower bounds for multi-frequency group synchronization
• Is it easier to count communities than find them?
• On finding randomly planted cliques in arbitrary graphs
• An optimized Franz-Parisi criterion and its equivalence with SQ lower bounds

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)