Fetching the paper…
Reading the bibliography…
We describe a general technique that yields the first {\em Statistical Query lower bounds} for a range of fundamental high-dimensional learning problems involving Gaussian distributions.
The generalization of student’s ratio
H. Hotelling · 1931
Earlier work this paper cites.
On the problem of the most efficient tests of statistical hypotheses
J. Neyman and E. S. Pearson · 1933
Earlier work this paper cites.
Robust estimation of a location parameter
P. J. Huber · 1964
Earlier work this paper cites.
Handbook of Mathematical Functions
M. Abramowitz and I. Stegun · 1972
Earlier work this paper cites.
Statistical Inference under Order Restrictions
R.E. Barlow, D.J. Bartholomew, J.M. Bremner, and H.D. Brunk · 1972
Earlier work this paper cites.
Mathematics and picturing of data
J.W. Tukey · 1975
Earlier work this paper cites.
A theory of the learnable
L. Valiant · 1984
Earlier work this paper cites.
Nonparametric Density Estimation: The L 1 L_{1} View
L. Devroye and L. Györfi · 1985
Earlier work this paper cites.
Robust statistics. The approach based on influence functions
F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel · 1986
Earlier work this paper cites.
Density Estimation
B. W. Silverman · 1986
Earlier work this paper cites.
Orthogonal Polynomials
G. Szegö · 1989
Earlier work this paper cites.
Breakdown properties of location estimates based on halfspace depth and projected outlyingness
D. L. Donoho and M. Gasko · 1992
Earlier work this paper cites.
Multivariate Density Estimation: Theory, Practice and Visualization
D.W. Scott · 1992
Earlier work this paper cites.
Weakly learning DNF and characterizing statistical query learning using Fourier analysis
A. Blum, M. Furst, J. Jackson, M. Kearns, Y. Mansour, and S. Rudich · 1994
Earlier work this paper cites.
On the learnability of discrete distributions
M. Kearns, Y. Mansour, D. Ron, R. Rubinfeld, R. Schapire, and L. Sellie · 1994
Earlier work this paper cites.
Effect of high dimension: by an example of a two sample problem
H. Saranadasa Z. Bai · 1996
Earlier work this paper cites.
Introduction to robust estimation and hypothesis testing
R. R. Wilcox · 1997
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
M. Kearns · 1998
Earlier work this paper cites.
Learning mixtures of Gaussians
S. Dasgupta · 1999
Earlier work this paper cites.
Estimating a mixture of two product distributions
Y. Freund and Y. Mansour · 1999
Earlier work this paper cites.
Testing that distributions are close
T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White · 2000
Earlier work this paper cites.
On testing expansion in bounded-degree graphs
O. Goldreich and D. Ron · 2000
Earlier work this paper cites.
Learning mixtures of arbitrary Gaussians
S. Arora and R. Kannan · 2001
Earlier work this paper cites.
Combinatorial methods in density estimation
L. Devroye and G. Lugosi · 2001
Earlier work this paper cites.
Evolutionary trees can be learned in polynomial time in the two state general Markov model
M. Cryan, L. Goldberg, and P. Goldberg · 2002
Earlier work this paper cites.
A spectral algorithm for learning mixtures of distributions
S. Vempala and G. Wang · 2002
Earlier work this paper cites.
On spectral learning of mixtures of distributions
D. Achlioptas and F. McSherry · 2005
Earlier work this paper cites.
Testing statistical hypotheses
E. L. Lehmann and J. P. Romano · 2005
Earlier work this paper cites.
Learning nonsingular phylogenies and Hidden Markov Models
E. Mossel and S. Roch · 2005
Earlier work this paper cites.
Map-reduce for machine learning on multicore
C.-T. Chu, S. K. Kim, Y. A. Lin, Y. Yu, G. Bradski, A. Y. Ng, and K. Olukotun · 2006
Earlier work this paper cites.
New results for learning noisy parities and halfspaces
V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami · 2006
Earlier work this paper cites.
PAC learning mixtures of Gaussians with no separation assumption
J. Feldman, R. O’Donnell, and R. Servedio · 2006
Cited alongside, same era.
Cryptographic hardness for learning intersections of halfspaces
A. Klivans and A. Sherstov · 2006
Cited alongside, same era.
Isotropic PCA and Affine-Invariant Clustering
S. C. Brubaker and S. Vempala · 2008
Cited alongside, same era.
Learning mixtures of product distributions over discrete domains
J. Feldman, R. O’Donnell, and R. A. Servedio · 2008
Cited alongside, same era.
Agnostically learning halfspaces
A. Kalai, A. Klivans, Y. Mansour, and R. Servedio · 2008
Cited alongside, same era.
The spectral method for general mixture models
R. Kannan, H. Salmasian, and S. Vempala · 2008
Cited alongside, same era.
Algorithmic aspects of machine learning
A. Moitra · 2014
Later among the works it cites.
Analysis of Boolean Functions
R. O’Donnell · 2014
Later among the works it cites.
Near-optimal-sample estimators for spherical gaussian mixtures
A. T. Suresh, A. Orlitsky, J. Acharya, and A. Jafarpour · 2014
Later among the works it cites.
Robust covariance matrix estimation via matrix depth
M. Chen, C. Gao, and Z. Ren · 2015
Later among the works it cites.
Optimal estimation and rank detection for sparse spiked covariance matrices
T. Cai, Z. Ma, and Y. Wu · 2015
Later among the works it cites.
Learning from satisfying assignments
A. De, I. Diakonikolas, and R. Servedio · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A test for the mean vector with fewer observations than the dimension
M. S. Srivastava and M. Du · 2008
Cited alongside, same era.
Robust statistics
P.J. Huber and E. M. Ronchetti · 2009
Cited alongside, same era.
On consistency and sparsity for principal components analysis in high dimensions
I. M. Johnstone and A. Y. Lu · 2009
Cited alongside, same era.
Polynomial learning of distribution families
M. Belkin and K. Sinha · 2010
Cited alongside, same era.
A two-sample test for high-dimensional data with applications to gene-set testing
S. X. Chen and Y. L. Qin · 2010
Cited alongside, same era.
Efficiently learning mixtures of two Gaussians
A. T. Kalai, A. Moitra, and G. Valiant · 2010
Cited alongside, same era.
Statistical query algorithms for stochastic convex optimization
V. Feldman, C. Guzman, and S. Vempala · 2015
Later among the works it cites.
On the complexity of random satisfiability problems with planted solutions
V. Feldman, W. Perkins, and S. Vempala · 2015
Later among the works it cites.
Learning mixtures of gaussians in high dimensions
R. Ge, Q. Huang, and S. M. Kakade · 2015
Later among the works it cites.
Tight bounds for learning a mixture of two gaussians
M. Hardt and E. Price · 2015
Later among the works it cites.
J. Li and L. Schmidt · 2015
Later among the works it cites.
Sum-of-squares lower bounds for sparse pca
T. Ma and A. Wigderson · 2015
Later among the works it cites.
Complexity theoretic limitations on learning halfspaces
A. Daniely · 2016
Closest in time.
A size-free CLT for poisson multinomials and its applications
C. Daskalakis, A. De, G. Kamath, and C. Tzamos · 2016
Closest in time.
Learning structured distributions
I. Diakonikolas · 2016
Closest in time.
Robust estimators in high dimensions without the computational intractability
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart · 2016
Closest in time.
The fourier transform of poisson multinomial distributions and its algorithmic applications
I. Diakonikolas, D. M. Kane, and A. Stewart · 2016
Closest in time.
Optimal learning via the fourier transform for sums of independent integer random variables
I. Diakonikolas, D. M. Kane, and A. Stewart · 2016
Closest in time.
Robust learning of fixed-structure bayesian networks
I. Diakonikolas, D. M. Kane, and A. Stewart · 2016
Closest in time.
A general characterization of the statistical query complexity
V. Feldman · 2016
Closest in time.
Statistical query learning
V. Feldman · 2016
Closest in time.
Beyond spectral: Tight bounds for planted gaussians
R. Kannan and S. Vempala · 2016
Closest in time.
Agnostic estimation of mean and covariance
K. A. Lai, A. B. Rao, and S. Vempala · 2016
Closest in time.
Statistical and computational trade-offs in estimation of sparse principal components
T. Wang, Q. Berthet, and R. J. Samworth · 2016
Closest in time.
Statistical and computational trade-offs in estimation of sparse principal components
T. Wang, Q. Berthet, and R.J. Samworth · 2016
Closest in time.
Sample-optimal density estimation in nearly-linear time
J. Acharya, I. Diakonikolas, J. Li, and L. Schmidt · 2017
Closest in time.
Computationally efficient robust estimation of sparse functionals
S. Du, S. Balakrishnan, and A. Singh · 2017
Closest in time.
Being robust (in high dimensions) can be practical
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart · 2017
Closest in time.
Robustly learning a gaussian: Getting optimal error, efficiently
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart · 2017
Closest in time.
Robust sparse estimation tasks in high dimensions
J. Li · 2017
Closest in time.