论文标题
对抗歧管估计
Adversarial Manifold Estimation
论文作者
论文摘要
本文研究了$ \ mathbb {r}^n $估计$ d $ d $二维子手法的统计查询（sq）复杂性。我们提出了一种称为歧管传播的纯几何算法，将问题降低到三个自然几何例程：投影，切线空间估计和点检测。然后，我们在SQ框架中提供这些几何例程的构造。给定一个对抗性$ \ mathrm {stat}（τ）$ oracle和目标hausdorff距离精度$ \ varepsilon =ω（τ^{2 /（d + 1）} $，结果sq歧管重构算法质量复杂性$ o（ 2}）$，这几乎是最佳的。在此过程中，我们为一般度量空间中的随机SQ估计器建立了SQ的低率矩阵完成结果。
This paper studies the statistical query (SQ) complexity of estimating $d$-dimensional submanifolds in $\mathbb{R}^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 $\mathrm{STAT}(τ)$ oracle and a target Hausdorff distance precision $\varepsilon = Ω(τ^{2 / (d + 1)})$, the resulting SQ manifold reconstruction algorithm has query complexity $O(n \operatorname{polylog}(n) \varepsilon^{-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.
