2018/06/19 by Matthew Brennan, Brennan, Matthew, Guy Bresler +3 · 7 citations
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning and Algorithms #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1806.07508
openalex publication_date 2018/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The prototypical high-dimensional statistics problem entails finding a\nstructured signal in noise. Many of these problems exhibit an intriguing\nphenomenon: the amount of data needed by all known computationally efficient\nalgorithms far exceeds what is needed for inefficient algorithms that search\nover all possible structures. A line of work initiated by Berthet and Rigollet\nin 2013 has aimed to explain these statistical-computational gaps by reducing\nfrom conjecturally hard average-case problems in computer science. However, the\ndelicate nature of average-case reductions has limited the applicability of\nthis approach. In this work we introduce several new techniques to give a web\nof average-case reductions showing strong computational lower bounds based on\nthe planted clique conjecture using natural problems as intermediates. These\ninclude tight lower bounds for Planted Independent Set, Planted Dense Subgraph,\nSparse Spiked Wigner, Sparse PCA, a subgraph variant of the Stochastic Block\nModel and a biased variant of Sparse PCA. We also give algorithms matching our\nlower bounds and identify the information-theoretic limits of the models we\nconsider.\n