Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures.
Ilias DiakonikolasDaniel M. KaneAlistair StewartPublished in: Electron. Colloquium Comput. Complex. (2016)
Keyphrases
- gaussian mixture
- robust estimation
- lower bound
- statistical queries
- high dimensional
- concept class
- upper bound
- gaussian mixture model
- em algorithm
- least squares
- low dimensional
- closed form
- probability density function
- covariance matrix
- mixture model
- noisy data
- concept classes
- dimensionality reduction
- vc dimension
- objective function
- expectation maximization
- similarity search
- optimal solution
- np hard
- feature space
- density estimation
- worst case
- motion field
- membership queries
- uniform distribution
- data points
- nearest neighbor
- learning theory
- high dimensional data
- generative model
- pac learning
- feature extraction
- probabilistic model
- boolean functions
- learning algorithm
- sample complexity
- supervised learning
- decision trees