The statistical query (SQ) framework consists in replacing the usual access to samples from a distribution, by the access to adversarially perturbed expected values of functions interactively chosen by the learner. This framework provides a natural estimation complexity measure, enforces robustness through adversariality, and is closely related to differential privacy. In this talk, we study the SQ complexity of estimating d-dimensional submanifolds in R^n. We propose a purely geometric algorithm called Manifold Propagation, that reduces the problem to three local 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 precision ε=O(τ^{2/(d+1)}) for the Hausdorff distance, the resulting SQ manifold reconstruction algorithm has query complexity O(npolylog(n)τ^{d/2}), which is proved to be nearly optimal. In the process, we will present low-rank matrix completion results for SQ's and lower bounds for (randomized) SQ estimators in general metric spaces.
Travail publié dans : Adversarial Manifold Estimation (https://arxiv.org/pdf/2011.04259v2.pdf) Il combine deux champs assez indépendants : - Pour le volet "Statistical queries" : https://arxiv.org/pdf/2004.00557.pdf - Pour le volet "Manifold estimation" : https://arxiv.org/pdf/1512.02857.pdf ou bien https://arxiv.org/pdf/2108.03135.pdf