A survey on distribution testing: Your data is big. But is it blue?
CL Canonne - Theory of Computing, 2020 - theoryofcomputing.org
The field of property testing originated in work on program checking, and has evolved into
an established and very active research area. In this work, we survey the developments of …
an established and very active research area. In this work, we survey the developments of …
Optimal detection of sparse principal components in high dimension
Q Berthet, P Rigollet - 2013 - projecteuclid.org
We perform a finite sample analysis of the detection levels for sparse principal components
of a high-dimensional covariance matrix. Our minimax optimal test is based on a sparse …
of a high-dimensional covariance matrix. Our minimax optimal test is based on a sparse …
Complexity theoretic lower bounds for sparse principal component detection
Q Berthet, P Rigollet - Conference on learning theory, 2013 - proceedings.mlr.press
In the context of sparse principal component detection, we bring evidence towards the
existence of a statistical price to pay for computational efficiency. We measure the …
existence of a statistical price to pay for computational efficiency. We measure the …
Statistical algorithms and a lower bound for detecting planted cliques
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 …
distributions against algorithms that can be implemented using access to a statistical query …
A nearly tight sum-of-squares lower bound for the planted clique problem
We prove that with high probability over the choice of a random graph G from the Erdös--
Rényi distribution G(n,1/2), the n^O(d)-time degree d sum-of-squares (SOS) semidefinite …
Rényi distribution G(n,1/2), the n^O(d)-time degree d sum-of-squares (SOS) semidefinite …
Reducibility and statistical-computational gaps from secret leakage
M Brennan, G Bresler - Conference on Learning Theory, 2020 - proceedings.mlr.press
Inference problems with conjectured statistical-computational gaps are ubiquitous
throughout modern statistics, computer science, statistical physics and discrete probability …
throughout modern statistics, computer science, statistical physics and discrete probability …
Incoherence-optimal matrix completion
Y Chen - IEEE Transactions on Information Theory, 2015 - ieeexplore.ieee.org
This paper considers the matrix completion problem. We show that it is not necessary to
assume joint incoherence, which is a standard but unintuitive and restrictive condition that is …
assume joint incoherence, which is a standard but unintuitive and restrictive condition that is …
Optimal testing for properties of distributions
J Acharya, C Daskalakis… - Advances in Neural …, 2015 - proceedings.neurips.cc
Given samples from an unknown distribution, p, is it possible to distinguish whether p
belongs to some class of distributions C versus p being far from every distribution in C? This …
belongs to some class of distributions C versus p being far from every distribution in C? This …
[HTML][HTML] Reducibility and computational lower bounds for problems with planted sparse structure
M Brennan, G Bresler… - Conference On Learning …, 2018 - proceedings.mlr.press
Recently, research in unsupervised learning has gravitated towards exploring statistical-
computational gaps induced by sparsity. A line of work initiated in Berthet and Rigollet …
computational gaps induced by sparsity. A line of work initiated in Berthet and Rigollet …
Statistical and computational trade-offs in estimation of sparse principal components
Statistical and computational trade-offs in estimation of sparse principal components Page 1
The Annals of Statistics 2016, Vol. 44, No. 5, 1896–1930 DOI: 10.1214/15-AOS1369 © Institute …
The Annals of Statistics 2016, Vol. 44, No. 5, 1896–1930 DOI: 10.1214/15-AOS1369 © Institute …