Statistical Query Complexity of Manifold Estimation

11/09/2020
by   Eddie Aamari, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset