Statistical Query Complexity of Manifold Estimation

Title - HTML
Nom de l'orateur
Eddie Aamari
Etablissement de l'orateur
LPSM
Date et heure de l'exposé
07-11-2023 - 11:00:00
Lieu de l'exposé
Salle des séminaires
Résumé de l'exposé

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

comments