Statistical query complexity of manifold estimation
Open Access
- 15 June 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 116-122
Abstract
This paper studies the statistical query (SQ) complexity of estimating d-dimensional submanifolds in ℝn. We propose a purely geometric algorithm called Manifold Propagation, that reduces the problem to three natural geometric routines: projection, tangent space estimation, and point detection. We then provide constructions of these geometric routines in the SQ framework. Given an adversarial STAT(τ) oracle and a target Hausdorff distance precision ε = Ω(τ2/(d+1)), the resulting SQ manifold reconstruction algorithm has query complexity O(n polylog(n) ε−d/2), which is proved to be nearly optimal. In the process, we establish low-rank matrix completion results for SQ’s and lower bounds for randomized SQ estimators in general metric spaces.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Manifold estimation and singular deconvolution under Hausdorff lossThe Annals of Statistics, 2012
- What Can We Learn Privately?SIAM Journal on Computing, 2011
- Halfspace Matricescomputational complexity, 2008
- A simple polynomial-time rescaling algorithm for solving linear programsMathematical Programming, 2007
- Nonlinear Dimensionality Reduction by Locally Linear EmbeddingScience, 2000
- Efficient noise-tolerant learning from statistical queriesJournal of the ACM, 1998
- Learning with Restricted Focus of AttentionJournal of Computer and System Sciences, 1998
- A plug-in approach to support estimationThe Annals of Statistics, 1997
- A theory of the learnableCommunications of the ACM, 1984
- Randomized Response: A Survey Technique for Eliminating Evasive Answer BiasJournal of the American Statistical Association, 1965