# Adversarial Manifold Estimation

Eddie Aamari
<EMAIL_ADDRESS>
LPSM, CNRS
Université Paris Cité, Sorbonne Université
Paris, France Alexander Knop
<EMAIL_ADDRESS>
Department of Mathematics
University of California, San Diego
La Jolla, CA, USA

###### Abstract

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}(\tau)$ oracle and a
target Hausdorff distance precision $\varepsilon=\Omega(\tau^{2/(d+1)})$, the
resulting SQ manifold reconstruction algorithm has query complexity
$\tilde{O}(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.

###### Contents

  1. 1 Introduction
    1. 1.1 Context
    2. 1.2 Contribution
      1. 1.2.1 Main Results
      2. 1.2.2 Manifold Propagation Algorithm
      3. 1.2.3 Statistical Query Algorithms for the Routines
      4. 1.2.4 Lower Bound Techniques
  2. 2 Preliminaries
    1. 2.1 Statistical Query Framework
    2. 2.2 Manifold Regularity and Distributional Assumptions
      1. 2.2.1 General Notation and Differential Geometry
      2. 2.2.2 Geometric and Statistical Models
      3. 2.2.3 On Some Implicit Bounds on the Model Parameters
    3. 2.3 Manifold Reconstruction from Point Clouds
  3. 3 Manifold Propagation Algorithm
  4. 4 Geometric Routines with Statistical Queries
    1. 4.1 Projection
    2. 4.2 Tangent Space
    3. 4.3 Seed Point
  5. 5 Manifold Estimation with Statistical Queries
    1. 5.1 Fixed Point Model
    2. 5.2 Bounding Ball Model
  6. 6 Further Directions
  7. Acknowledgements
  8. A Proofs of the Properties of Manifold Propagation
  9. B Preliminary Geometric Results
    1. B.1 Local Mass of Balls Estimates
    2. B.2 Euclidean Packing and Covering Estimates
    3. B.3 Global Volume Estimates
  10. C Projection Routine
    1. C.1 Bias of the Local Conditional Mean for Projection
    2. C.2 Metric Projection with Statistical Queries
  11. D Tangent Space Estimation Routine
    1. D.1 Bias of Local Principal Component Analysis
    2. D.2 Matrix Decomposition and Principal Angles
    3. D.3 Low-rank Matrix Recovery
      1. D.3.1 Restricted Isometry Property and Low-Rank Matrix Recovery
      2. D.3.2 Building a Good Matrix Sensing Operator
      3. D.3.3 Mean Matrix Completion with Statistical Queries
    4. D.4 Tangent Space Estimation with Statistical Queries
  12. E Seed Point Detection
    1. E.1 Detecting a Raw Initial Point
    2. E.2 Refined Point Detection
  13. F Proof for the Main Statistical Query Manifold Estimators
  14. G Statistical Query Lower Bounds in Metric Spaces
    1. G.1 Information-Theoretic Lower Bound for Randomized SQ Algorithms
    2. G.2 Computational Lower Bound
      1. G.2.1 Probabilistic Covering and Packing Number
      2. G.2.2 Proof of the Computational Lower Bounds for Randomized SQ Algorithms
  15. H Lower Bounds for Manifold Models
    1. H.1 Diffeomorphisms and Geometric Model Stability
    2. H.2 Building a Large-Volume Submanifold with Small Euclidean Diameter
      1. H.2.1 The Statement
      2. H.2.2 Widget Gluing: From Paths on the Discrete Grid to Manifolds
      3. H.2.3 Existence of Long Paths on the Grid
    3. H.3 Informational Lower Bounds: Hypotheses for Le Cam’s Lemma
      1. H.3.1 Construction of the Hypotheses
      2. H.3.2 Proof of the Informational Lower Bounds for Manifold Estimation
    4. H.4 Computational Lower Bounds: Packing Number of Manifold Classes
      1. H.4.1 Global Ambient Packings
      2. H.4.2 Local Intrinsic Packings
      3. H.4.3 Proof of the Computational Lower Bounds for Manifold Estimation

##  1 Introduction

In the realm of massive data acquisition, the curse of dimensionality
phenomena led to major developments of computationally efficient statistical
and machine learning techniques. Central to them are topological data analysis
and geometric methods, which have recently garnered a lot of attention and
proved fruitful in both theoretical and applied areas [Was18]. These realms
refer to a collection of statistical methods that find intrinsic structure in
data. In short, this field is based upon the idea that data described with a
huge number of features $n$ may be subject to redundancies and correlations,
so that they include only $d\ll n$ intrinsic and informative degrees of
freedom. This low-dimensional paradigm naturally leads to the problem of
recovering this intrinsic structure, for data visualization or to mitigate the
curse of dimensionality. This problem is usually referred to as _support
estimation_ [CF97] or _dimensionality reduction_ [LV07].

Linear dimensionality reduction techniques, such as Principal Component
Analysis and LASSO-types methods [HTF09], assume that the data of interest lie
on a low-dimensional linear subspace. This assumption appears to be often too
strong in practice, so that one may use problem-specific featurization
techniques, or other non-linear methods. On the other hand, non-linear
dimensionality reduction techniques such as Isomap [Ten97], Local Linear
Embedding [RS00] and Maximum Variance Unfolding [ACP13], work under the
relaxed assumption that the data of interest lie on an embedded
$d$-dimensional manifold of $\mathbb{R}^{n}$ with $d\ll n$, hence allowing
natively for non-linearities.

###  1.1 Context

##### Geometric Inference from Samples.

The classical statistical framework, based on data points, is usually referred
to as _PAC-learning_ [Val84] or _sample framework_. In this setting, the
learner is given a set $\left\\{{x_{1},\dots,x_{s}}\right\\}$ of $s$ samples
drawn, most commonly independently, from an unknown distribution $D$. From
these samples, the learner then aims at estimating a parameter of interest
$\theta(D)$, which in our context will naturally be taken as the support
$\theta(D)=\mathrm{Supp}(D)\subseteq\mathbb{R}^{n}$. As described above, for
this problem to make sense, $D$ shall be assumed to be supported on (or near)
a low-dimensional structure, i.e. a $d$-dimensional submanifold with $d\ll n$.
Here, the precision is usually measured with the Hausdorff distance, a
$L^{\infty}$-type distance between compact subsets of $\mathbb{R}^{n}$.

The Hausdorff estimation of manifolds in the noiseless sample framework is now
well understood. The first minimax manifold estimation results in the sample
framework are due to [GPPVW12b, GPPVW12a]. At the core of their work is the
reach, a scale parameter that quantitatively encodes $\mathcal{C}^{2}$
regularity of the unknown manifold
$M=\mathrm{Supp}(D)\subseteq\mathbb{R}^{n}$, and that allows measuring the
typical scale at which $M$ looks like $\mathbb{R}^{d}$ [AKC+19] (see
Definition 2.3). Under reach assumptions, the estimator of [GPPVW12a] achieves
a worst-case average precision at most $O((\log s/s)^{2/d})$, but with a
computationally intractable method. This rate was later shown to be
$\log$-tight optimal by [KZ15]. Given a target precision $\varepsilon>0$,
these results hence reformulate to yield sample complexity of order
$s=O(\varepsilon^{-d/2}\log(1/\varepsilon))$. Later, [AL18] gave a
constructive estimator combining local PCA and the computational geometry
algorithm from [BG14], which outputs a triangulation of the sample points in
polynomial time, and linear time in the ambient dimension $n$ [BG14]. More
recently, [Div21a] proposed a computationally tractable minimax adaptive
method that automatically selects the intrinsic dimension and reach. Let us
also mention that by using local polynomials, faster sample rates can also be
achieved when the manifolds are smoother than $\mathcal{C}^{2}$ [AL19].

Manifold estimation in the presence of noise is by far less understood. The
only known optimal statistical method able to handle samples corrupted with
additive noise [GPPVW12b] is intractable. Currently, the best algorithmically
tractable estimators in this context require either the noise level to vanish
fast enough as the sample size grows [PS22], or very specific distributional
assumptions on the noise: either Gaussian [FILN19, DW21] or ambient uniform
[AS21]. To date, the only computationally tractable sample method that truly
is robust to some type of noise is due to [AL18], in which the authors
consider the so-called _clutter noise_ model introduced by [GPPVW12a]. In this
model, the samples are generated by a mixture of a distribution $D$ on $M$ and
a _uniform_ distribution in the ambient space, with respective coefficients
$\beta\in(0,1]$ and $(1-\beta)$. That is, the $s$-sample consists of
unlabelled points in $\mathbb{R}^{n}$, with approximately $\beta s$
informative points on $M$ and $(1-\beta)s$ non-informative ambient clutter
points. In [GPPVW12a, KZ15], the optimal sample complexity was shown to be
$s=O(\beta^{-1}\varepsilon^{-d/2}\log(1/\varepsilon))$, but this rate was
obtained with an intractable method. On the other hand, [AL18] proposed to
label the non-informative data points, which allows to apply a clutter-free
estimation procedure to the remaining decluttered points. This results in a
computationally tractable minimax optimal method, with an additional
computational cost due to the decluttering. However, the success of this extra
step relies heavily on the assumption that the ambient clutter is uniform.

Overall, the existing reasonable manifold estimation methods are heavily
attached to the _individual_ data points and do not tolerate much noise, as
the change of a single point may have the method fail completely. Let us
mention from now that in sharp contrast, the statistical query framework
considered in this work is inherently robust to clutter noise without an
artificial decluttering, no matter the clutter noise distribution (see Remark
2.2).

##### Private Learning.

Beyond the classical sample complexity, the modern practice of statistics
raised concerns leading to quantitative and qualitative estimation constraints
[Wai14]. For instance, in many applications of learning methods, the studied
data is contributed by individuals, and features represent their (possibly)
private characteristics such as gender, race, or health history. Hence, it is
essential not to reveal too much information about any particular individual.
The seminal paper [KLN+11] on this topic introduces the notion of private
learning, a learning framework inspired by differentially private algorithms
[DMNS06]. Given samples $\left\\{{x_{1},\dots,x_{s}}\right\\}$, this framework
imposes privacy to a learner by requiring it not to be significantly affected
if a particular sample $x_{i}$ is replaced with an arbitrary $x^{\prime}_{i}$.

In contrast to precision, which is analyzed with respect to a model, the level
of differential privacy is a worst-case notion. Hence, when analyzing the
privacy guarantees of a learner, no assumption should be made on the
underlying generative model. Indeed, such a generative assumption could fall
apart in the presence of background knowledge that the adversary might have:
conditioned on this background knowledge, the model may change drastically.

There are two main types of differentially private algorithms. _Global
differential privacy_ assumes that there is a trusted entity (i.e. a central
data aggregator) that can give private answers to database queries [KLN+11].
This approach was used by LinkedIn to share advertisements data [RSP+20], by
Uber’s system for internal analytics [JNS18], and is about to be implemented
by the U.S. Census Bureau for publishing data [Jar19].

In contrast, _local differential privacy_ , as defined by [EGS03, KLN+11],
even further restricts the learners. It requires that even if an adversary has
access to the personal revealed data of individuals, this adversary will still
be unable to learn too much about the user’s actual personal data. The
simplest example of a locally private learning protocol was originally
introduced to encourage truthfulness in surveys [War65]. In local differential
privacy, a trusted entity is not necessarily present, and each individual
protects their own privacy, for instance, by adding noise to their data
separately.

##### Statistical Queries.

Instead of sample complexity, this paper considers the notion of statistical
query complexity, which was proved to be equivalent to the locally private
learning complexity up to a polynomial factor [KLN+11], and that naturally
enforces robustness to clutter noise (see Remark 2.2).

First introduced by Kearns [Kea98], the statistical query (SQ) framework is a
restriction of PAC-learning, where the learner is only allowed to obtain
approximate averages of the unknown distribution $D$ via an adversarial
oracle, but cannot see any sample. That is, given a tolerance parameter
$\tau>0$, a $\mathrm{STAT}(\tau)$ oracle for the distribution $D$ accepts
functions $r:\mathbb{R}^{n}\to[-1,1]$ as queries from the learner, and can
answer _any_ value $\mathrm{a}\in\mathbb{R}$ such that
$|\\!\mathop{\mathbb{E}}_{x\sim D}[r(x)]-\mathrm{a}|\leq\tau$. Informally, the
fact that the oracle is adversarial is the counterpart to the fact that
differential privacy is a worst-case notion. We emphasize that in the
statistical query framework, estimators (or learners) are only given access to
such an oracle, and not to the data themselves. Limiting the learner’s
accessible information to adversarially perturbed averages both restricts the
range of the usable algorithms, and effectively forces them to be robust and
efficient.

Kearns showed that any statistical query learner can be transformed into a
classical PAC-learning algorithm with robustness to random classification
noise [Kea98]. Conversely, many commonly used PAC-learning algorithms have
statistical query implementations [Kea98, Byl94, DV08]. Though, Kearns also
showed that there are information-theoretic obstacles that are specific to the
statistical query framework; e.g. parity functions require an exponential
number of queries [Kea98]. In other words, PAC-learning is strictly stronger
than SQ-learning.

We have already mentioned the connection between statistical queries and
private learning. On top of this, the simplicity of the SQ framework allowed
its application in several other fields, such as (theoretical and practical)
learning algorithms for distributed data systems. Indeed, a problem has an
efficient SQ algorithm if and only if it has an efficient distributed learner
[BD98, SVW16]. Another incentive to study statistical queries arises from
quantum computations: general quantum PAC learners can perform complex
entangling measurements which do not seem realizable for near-term quantum
computers. To overcome this issue, Arunachalam, Grilo, and Yuen [AGY20]
introduced the notion of quantum statistical query learning, for which
practical implementations would only require to measure a single quantum state
at a time.

Overall, certainly the most interesting property of statistical query
algorithms is the possibility of proving unconditional lower bounds on the
complexity of statistical problems. Considering the number of learning
algorithms that are implementable in the statistical query framework, these
lower bounds provide strong evidence of hardness of these problems. Moreover,
for many learning problems, the known unconditional lower bounds for the
statistical query framework closely match the known computational complexity
upper bounds. For instance, [BFJ+94] proved that SQ algorithms require a
quasi-polynomial number of queries to learn disjunctive normal forms (DNF),
which matches the running time upper bound by Verbeurgt [Ver90]. Similar
results were proved by [FGR+17] for the planted clique problem, and by [DKS17]
for high-dimensional Gaussian mixtures learning. Finally, some problem-
specific statistical query lower bounds directly imply lower bounds against
general convex relaxations of Boolean constraint satisfaction problems [FPV18,
FGV21], lower bounds on approximation of Boolean functions by polynomials
[DFT+15], and lower bounds on dimension complexity of Boolean function classes
[She08, FGV21].

###  1.2 Contribution

This paper is the long and complete version of [AK21]. We establish nearly
matching upper and lower bounds on the statistical query complexity of
manifold learning. As a corollary, it provides an efficient and natural noise-
tolerant sample manifold estimation technique; as another side-product, it
also provides, to the best of our knowledge, the first private manifold
estimation method. In some regimes of the parameters, it also exhibits another
example of a natural statistical problem with different sample and statistical
query complexities.

####  1.2.1 Main Results

##### Upper Bounds.

The main contribution of this paper is the construction of a low-complexity
_deterministic_ SQ algorithm that uniformly estimates the compact connected
$d$-dimensional $\mathcal{C}^{2}$-manifolds $M\subseteq\mathbb{R}^{n}$ with
reach $\mathrm{rch}_{M}\geq\mathrm{rch}_{\min}>0$ (i.e. curvature roughly
bounded by $1/\mathrm{rch}_{\min}$), from distributions $D$ with support
$\mathrm{Supp}(D)=M$ that have a Lipschitz density function bounded below by
$f_{\min}>0$ on $M$ (i.e. volume of $M$ roughly bounded by $1/f_{\min}$). See
Definition 2.5 for a formal definition. The estimation error is measured in
Hausdorff distance, which plays the role of a sup-norm between compact subsets
of $\mathbb{R}^{n}$.

In Proposition 2.1, we prove that without any prior information about the
location of the manifolds, SQ algorithms cannot estimate them, even with an
unlimited number of queries. It is worth noting that this phenomenon is
specific to the SQ framework and does not occur in the sample framework. We
consider two ways to “localize” the model. Namely, we either assume: that the
manifold contains the origin (fixed point model), or that the manifold lies
within the ball of radius $R>0$ centered at the origin (bounding ball model).

[Fixed point model]

Theorem 5.1 presents a _deterministic_ algorithm which, given the information
that $0\in M$, achieves precision $\varepsilon$ using

$q=O\left(\frac{n\operatorname{polylog}(n)}{f_{\min}}\left(\frac{1}{\mathrm{rch}_{\min}\varepsilon}\right)^{d/2}\right)$

queries to a $\mathrm{STAT}(\tau)$ oracle, provided that

$\varepsilon=\Omega\left(\mathrm{rch}_{\min}\biggl{(}\frac{\tau}{f_{\min}\mathrm{rch}_{\min}^{d}}\biggr{)}^{2/(d+1)}\right),\text{
and }\tau=O(f_{\min}\mathrm{rch}_{\min}^{d}).$

[Bounding ball model]

Theorem 5.4 shows that the same estimation problem can still be solved using
$O(n\log(R/\varepsilon))$ extra queries to $\mathrm{STAT}(\tau)$ if $M$ is
only assumed to be contained in the ball $\mathrm{B}(0,R)$. That is, it shows
that manifold estimation with precision $\varepsilon$ in the bounding ball
model can be done deterministically with

$q=O\left(n\log\left(\frac{R}{\varepsilon}\right)+\frac{n\operatorname{polylog}(n)}{f_{\min}}\left(\frac{1}{\mathrm{rch}_{\min}\varepsilon}\right)^{d/2}\right)$

queries to a $\mathrm{STAT}(\tau)$ oracle, under similar conditions as above.

Notice the limited quasi-linear dependency on the ambient dimension $n$ in
these bounds. Actually, in the fixed point model, the given query complexity
corresponds to the sample complexity up to the $n\operatorname{polylog}(n)$
factor [KZ15, Div21a]. This apparent discrepancy can be explained by the fact
that a single sample of $M\subseteq\mathbb{R}^{n}$ corresponds to $n$
coordinates, while statistical queries are forced to be real-valued. More
interestingly, the extra cost $O(n\log(R/\varepsilon))$ in the bounding ball
model is specific to the statistical query framework and does not appear in
the sample framework [KZ15], although this term would dominate only in the
regime where $R$ is exponentially bigger than $\mathrm{rch}_{\min}$.

The insights underlying these upper bounds are described in Sections 1.2.2 and
1.2.3, and the formal statements in Sections 3, 4 and 5.

##### Differentially Private Manifold Estimation.

As a direct corollary (see [KLN+11, Theorem 5.7]), these SQ upper bounds
transform into private learning upper bounds. They yield, to the best of our
knowledge, the first private learning algorithms for manifold estimation. More
precisely, we proved that for all $\varepsilon=O(\mathrm{rch}_{\min})$, there
is a local $\delta$-differentially111As the present paper uses $\varepsilon$
for precision, we use $\delta$ as the privacy parameter, contrary to the
standard notation. private algorithm estimating the $d$-dimensional
$\mathcal{C}^{2}$-manifolds $M$ with precision $\varepsilon$ that requires no
more than

$\displaystyle s_{\delta\text{-private}}(\varepsilon)$
$\displaystyle=\tilde{O}\left(\frac{n}{(f_{\min}\mathrm{rch}_{\min}^{d})^{3}\delta^{2}}\left(\frac{\mathrm{rch}_{\min}}{\varepsilon}\right)^{(3d+2)/2}\right)$

samples in the fixed point model, where $\tilde{O}$ hides the logarithmic
terms of the complexity. See [KLN+11] for more formal and thorough
developments on differential privacy.

##### Lower Bounds.

Complementing these upper bounds on the statistical query complexity of
manifold estimation, we prove a _computational_ and an _informational_ lower
bound, that both nearly match. To examine whether or not randomness may
facilitate manifold learning, the below lower bounds apply to _randomized_ SQ
algorithms, which are allowed to use randomness and to fail with probability
at most $\alpha\in[0,1)$. Recall that the above upper bounds stand for
_deterministic_ ($\alpha=0$) SQ algorithms.

First, we prove the following computational lower bounds.

[Fixed point model]

Theorem 5.3 asserts that any _randomized_ SQ algorithm estimating $M$ with
precision $\varepsilon$ and probability of error at most $\alpha$ in the fixed
point model requires at least

$q=\Omega\left(\frac{\frac{n}{f_{\min}}\left(\frac{1}{\mathrm{rch}_{\min}\varepsilon}\right)^{d/2}+\log(1-\alpha)}{\log\left(1+\frac{1}{\tau}\right)}\right)$

queries to a $\mathrm{STAT}(\tau)$ oracle.

[Bounding ball model]

Theorem 5.6 states that any _randomized_ SQ algorithm estimating $M$ with
precision $\varepsilon$ and probability of error at most $\alpha$ in the
bounding ball model requires at least

$q=\Omega\left(\frac{n\log\left(\frac{R}{\varepsilon}\right)+\frac{n}{f_{\min}}\left(\frac{1}{\mathrm{rch}_{\min}\varepsilon}\right)^{d/2}+\log(1-\alpha)}{\log\left(1+\frac{1}{\tau}\right)}\right)$

queries to a $\mathrm{STAT}(\tau)$ oracle.

In words, this proves that for any fixed probability of error $\alpha<1$, the
above manifold estimators are optimal up to a
$\operatorname{polylog}(n,1/\tau)$ factor. Hence, randomized algorithms are
not significantly more powerful than deterministic ones in these models.

Second, we establish informational lower bounds (Theorems 5.2 and 5.5) that
advocate for the necessity of the requirements on $\varepsilon$ and $\tau$
made in the upper bounds. More precisely, they assert that if we either have
$\varepsilon=o\left(\mathrm{rch}_{\min}\left(\frac{\tau}{f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/d}\right)$,
or $\tau=\Omega(f_{\min}\mathrm{rch}_{\min}^{d})$ and
$\varepsilon=o(\mathrm{rch}_{\min})$, then no SQ algorithm (even randomized)
can estimate manifolds in these models with precision $\varepsilon$,
regardless of its number of queries. Said otherwise, the adversarial tolerance
parameter $\tau$ prevents the learner to have arbitrary precision
$\varepsilon$ , with quantitative lower bound

$\varepsilon=\Omega\left(\mathrm{rch}_{\min}\min\left\\{{1,\left(\frac{\tau}{f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/d}}\right\\}\right)$

no matter the computational power of the statistician.

The high level exposition of these lower bounds stands in Section 1.2.4, and
all the necessary details and formal statements in Section 5.

####  1.2.2 Manifold Propagation Algorithm

The core component of the upper bounds (Theorems 5.1 and 5.4) is a purely
geometric algorithm, which we call Manifold Propagation, parametrized by an
initialization method $\hat{x}_{0}$ and two routines $\hat{T}(\cdot)$ and
$\hat{\pi}(\cdot)$ related to the manifold $M$:

(Seed point)

This initialization method finds a point $\hat{x}_{0}$ that is $\eta$-close to
$M$, for some $\eta\geq 0$.

(Tangent space)

Given a point $x_{0}$ that is $\eta$-close to $M$, this routine finds a linear
subspace $\hat{T}(x_{0})$ that is $(\sin\theta)$-close to the tangent space
$T_{\pi_{M}(x_{0})}M$ at its projection $\pi_{M}(x_{0})$ (i.e. the closest
point on $M$), for some $\theta\geq 0$.

(Projection)

Given a point $x_{0}$ that is $\Lambda$-close to $M$, this routine finds a
point $\hat{\pi}(x_{0})$ that is $\eta$-close to its projection
$\pi_{M}(x_{0})$, where $\Lambda\geq\eta$.

Then, given a tuning scale parameter $\Delta>0$, Manifold Propagation
iteratively explores the connected manifold $M$ starting from the seed point,
and constructs a $\Omega(\Delta)$-sparse and $O(\Delta)$-dense point cloud
$\mathcal{O}$ of points close to $M$ (see Theorem 3.1). This algorithm is
reminiscent of breadth-first search and can be roughly described as follows:

  1. 1.

Start with the seed point $\hat{x}_{0}$ in the vicinity of the manifold and
initialize a queue of points to $\mathcal{Q}=\left\\{{\hat{x}_{0}}\right\\}$,
and the final output point cloud to $\mathcal{O}=\emptyset$.

  2. 2.

Pick a point $x_{0}\in\mathcal{Q}$, remove $x_{0}$ from $\mathcal{Q}$ and add
it to $\mathcal{O}$. Compute the approximate tangent space $\hat{T}(x_{0})$ of
$M$ at $x_{0}$.

  3. 3.

Consider a covering $y_{1}$, …, $y_{k}$ of a sphere of radius $\Delta$ in
$\hat{T}(x_{0})$. To avoid backtracking, remove all of these points that are
too close to (the already-visited) points from $\mathcal{Q}\cup\mathcal{O}$.
To account for the linear approximation made and the past estimation errors,
“project” the remaining points $y_{i}$’s on $M$ with $\hat{\pi}(\cdot)$ and
add them to $\mathcal{Q}$.

  4. 4.

If $\mathcal{Q}$ is empty, terminate and output $\mathcal{O}$. Otherwise go to
Step $2$.

Note the importance of the proximity check of Step 3, without which the
algorithm would not terminate, even with infinitely precise routines.

Then, given such a point cloud $\mathcal{O}$ that forms a $O(\Delta)$-dense
sample of $M$, existing algorithms from computational geometry (Theorem 2.1)
allow to reconstruct a manifold with precision
$O(\Delta^{2}/\mathrm{rch}_{\min})$. This quadratic gain is made possible by
the $\mathcal{C}^{2}$-smoothness of $M$ [BG14, AL18]. Hence, running Manifold
Propagation with step size $\Delta=O(\sqrt{\mathrm{rch}_{M}\varepsilon})$ and
applying Theorem 2.1 yields a dynamic method to estimate a manifold $M$ with
reach $\mathrm{rch}_{\min}>0$. Namely, to estimate $M$ with precision
$\varepsilon$ in Hausdorff distance, it shows that it is sufficient to design
routines for $M$ that have precision $\eta=O(\varepsilon)$ for the seed point,
$\sin\theta=O(\sqrt{\varepsilon/\mathrm{rch}_{\min}})$ for the tangent spaces,
and $\eta=O(\varepsilon)$ for the projection.

To our knowledge, this provides the first computational geometric result
involving the three routines above only. It also does a single call to
$\hat{x}_{0}$ for initialization, and provably no more than
$O(\mathcal{H}^{d}(M)/\Delta^{d})=O(\mathcal{H}^{d}(M)/(\mathrm{rch}_{\min}\varepsilon)^{d/2})$
calls to the routines $\hat{\pi}(\cdot)$ and $\hat{T}(\cdot)$, where
$\mathcal{H}^{d}(M)$ stands for the surface area of $M$. In particular, this
number of calls is blind to the ambient dimension. Overall, Manifold
Propagation manages to have this possible ambient dependency supported by
$\hat{x}_{0}$, $\hat{T}(\cdot)$ and $\hat{\pi}(\cdot)$ only. See Section 3 for
the formal statements and further discussion.

####  1.2.3 Statistical Query Algorithms for the Routines

In order to plug Manifold Propagation in the SQ framework, we then provide SQ
implementations of its geometric routines.

##### Projection Routine.

As mentioned above, the projection routine should allow to find a point
$\hat{\pi}(x_{0})$ that is $\eta$-close to $\pi_{M}(x_{0})$, provided that
$x_{0}$ is $\Lambda$-close to $M$. To implement this using a
$\mathrm{STAT}(\tau)$ oracle, we first note that the conditional expectation
of $D$ in the neighborhood of $x_{0}$ has small bias for estimating
$\pi_{M}(x_{0})$. That is, $\|\pi_{M}(x_{0})-\mathop{\mathbb{E}}_{x\sim
D}\left[x\left|\mathrm{B}(x_{0},h)\right.\right]\|$ is small for a properly
tuned bandwidth $h$ (see Lemma C.2). Hence, it is enough to estimate

$m_{D}(x_{0},h)=\mathop{\mathbb{E}}_{x\sim
D}\left[x\left|\mathrm{B}(x_{0},h)\right.\right]=x_{0}+h\frac{\mathop{\mathbb{E}}_{x\sim
D}\left[\frac{(x-x_{0})}{h}\cdot\mathbbm{1}_{\|x-x_{0}\|\leq
h}\right]}{D(\mathrm{B}(x_{0},h))},$

where $D(\mathrm{B}(x_{0},h))$ stands for the mass of the ball
$\mathrm{B}(x_{0},h)$ for distribution $D$. Written as a ratio of two means,
one easily sees how to estimate $m_{D}(x_{0},h)$ in $\mathrm{STAT}(\tau)$, as
we now explain. The denominator only requires one query
$r=\mathbbm{1}_{\mathrm{B}(x_{0},h)}$ to the oracle. As about the numerator,
which is a $n$-dimensional mean vector, the naive approach that would query
each coordinate of its integrand separately would end up with the dimension-
dependent precision $\sqrt{n}\tau$ in Euclidean norm. Instead, by using tight
frames, an algorithm of Feldman, Guzmán, and Vempala [FGV21] allows to get
precision $O(\tau)$ in only $2n$ queries.

At the end of the day, we achieve precision
$\eta=O\left(\Lambda^{2}/\mathrm{rch}_{\min}\right)$ with $O(n)$ queries to
$\mathrm{STAT}(\tau)$, provided that: (see Theorem 4.1)

$\Lambda=\Omega\left(\mathrm{rch}_{\min}\left(\frac{\tau}{f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{1/(d+1)}\right).$

##### Tangent Space Routine.

Here, the tangent space routine should allow to estimate the tangent space
$T_{\pi_{M}(x_{0})}M$ of $M$ at $\pi_{M}(x_{0})$, provided that $x_{0}$ is
$\eta$-close to $M$. Local Principal Component Analysis proved fruitful in the
sample framework [AL18]. Inspired by it, we notice that the local covariance
matrix of $D$ at $x_{0}$

$\Sigma_{D}(x_{0},h)=\mathop{\mathbb{E}}_{x\sim
D}\left[\frac{(x-x_{0}){(x-x_{0})}^{\top}}{h^{2}}\mathbbm{1}_{\|x-x_{0}\|\leq
h}\right]$

allows to approximate $T_{\pi_{M}(x_{0})}M$. That is, $\Sigma_{D}(x_{0},h)$ is
almost rank-$d$ and its first $d$ principal components span a $d$-plane close
to $T_{\pi_{M}(x_{0})}M$, for a properly tuned bandwidth $h$ (see Lemma D.1).
Next, aiming at estimating $\Sigma_{D}(x_{0},h)\in\mathbb{R}^{n\times n}$ in
$\mathrm{STAT}(\tau)$, we note that seeing it as a mean vector of
$\mathbb{R}^{n^{2}}$ and using tight frames [FGV21] directly would cost
$O(n^{2})$ queries for precision $O(\tau)$, but would not exploit the low-rank
(hence redundant) structure of $\Sigma_{D}(x_{0},h)$. Instead, we use matrix
compression arguments [FCRP08] to present a new general SQ algorithm
estimating low-rank mean matrices (Lemma D.4). This allows to mitigate the
query complexity from $O(n^{2})$ to $O(dn\log^{6}(n))$ while keeping precision
$O(\tau)$ in Frobenius norm.

At the end of the day, coming back to our initial problem of tangent space
estimation in $\mathrm{STAT}(\tau)$, we achieve precision
$\sin\theta=O\left(\sqrt{\eta/\mathrm{rch}_{\min}}\right)$ with
$O(dn\operatorname{polylog}(n))$ queries to $\mathrm{STAT}(\tau)$, provided
that: (see Theorem 4.2)

$\eta=\Omega\left(\mathrm{rch}_{\min}\left(\frac{\tau}{f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/(d+1)}\right).$

##### Seed Point Detection.

Finally, the seed point $\hat{x}_{0}$ should be $\eta$-close to $M$. In the
fixed point model, this method is trivial since $0\in M$ by assumption. In the
bounding ball model, where it is only assumed that
$M\subseteq\mathrm{B}(0,R)$, we proceed in two stages:

  * •

First, we use a divide and conquer strategy over $\mathrm{B}(0,R)$ (Theorem
E.1). The algorithm (SQ Ambient Binary Search) recurses down over a
discretization of $\mathrm{B}(0,R)$ with unions of small balls, maintained to
intersect $M=\mathrm{Supp}(D)$ by querying their indicator functions, i.e. by
checking that they have non-zero mass for $D$. It stops when there is only one
ball left and outputs its center $\hat{x}_{0}^{raw}$. Unfortunately, the
output point $\hat{x}_{0}^{raw}$ of this simple strategy might only be
$O(\mathrm{rch}_{\min}\left(\tau/(f_{\min}\mathrm{rch}_{\min}^{d})\right)^{1/d})$-close
to $M$, since this procedure does not use the $\mathcal{C}^{2}$-smoothness of
$M$.

  * •

Starting from $\hat{x}_{0}^{raw}$, the algorithm applies iteratively the
projection routine $\hat{\pi}(\cdot)$ described above. Since
$\hat{x}_{0}^{raw}$ is already close to $M$, the procedure is guaranteed to
improve precision quadratically at each step, and to output a point
$\hat{x}_{0}$ that is $\eta$-close to $M$ after a logarithmic number of
iterations.

At the end of the day, we achieve precision $\eta$ with $O(n\log(R/\eta))$
queries to $\mathrm{STAT}(\tau)$, provided that: (see Theorem 4.3)

$\eta=\Omega\left(\mathrm{rch}_{\min}\left(\frac{\tau}{f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/(d+1)}\right).$

####  1.2.4 Lower Bound Techniques

The standard SQ lower bound techniques, such as those involving the so-called
statistical dimension [Fel17], appear to be ill-suited to our context. In
fact, the informational bounds on the statistical dimension naturally involve
Kullback-Leibler or chi-squared divergences [Fel17, DKS17], which are non-
informative in non-dominated statistical models such as manifolds ones.
Indeed, two low-dimensional submanifolds $M_{0},M_{1}\subseteq\mathbb{R}^{n}$
that are not equal would differ in a non-trivial area, yielding distributions
are not absolutely continuous with respect to one another. This results in
infinite Kullback-Leibler and chi-squared divergences, and hence non-
informative lower bounds.

To overcome this issue, we present a two-step technique — involving a
computational and an informational lower bound — that does not involve these
quantities. The method applies in general metric spaces (see Appendix G),
although we shall limit its exposition and application to the case of
manifolds with Hausdorff distance in this introduction.

##### Computational Lower Bounds.

We aim at deriving a lower bound the number $q(\varepsilon)$ of queries
necessary to achieve precision $\varepsilon$. For this, we observe that since
a SQ algorithm should cope with _any_ adversarial oracle, it has to cope with
the oracle that answers roundings
$\mathrm{a}=\tau\left\lfloor\mathop{\mathbb{E}}_{x\sim
D}[r(x)]/\tau\right\rfloor$ of the true queried mean to the nearest integer
multiple of $\tau$ in $[-1,1]$. As this oracle only generates $(1+1/\tau)$
different answers, any SQ manifold estimation algorithm that makes only $q$
queries to this discrete oracle produces at most
$\mathcal{N}\leq(1+1/\tau)^{q}$ possible outputs $\hat{M}$. Hence, if this
estimator has precision $\varepsilon$, these outputs should form an
$\varepsilon$-covering of the manifold class of interest $\mathcal{M}$. Hence,
deriving a lower bound on
$q=q(\varepsilon)\geq\log\mathcal{N}(\varepsilon)/\log(1+1/\tau)$ boils down
to deriving a lower bound on the $\varepsilon$-covering number of
$\mathcal{M}$ for the Hausdorff distance, or equivalently, by duality, on its
$\varepsilon$-packing number. This argument also extends to randomized SQ
algorithms (see Section G.2).

We then explicitly build $\varepsilon$-packings of the manifold classes
associated to the models, with a general combinatorial scheme (see Proposition
H.5) based on a single initial manifold $M_{0}$. The construction bumps
$M_{0}$ at many different locations, with bumps of height
$\Omega(\varepsilon)$ scattered in all the available $(n-d)$ codimensions of
space, as shown in Figure 1.

Figure 1:  Construction of an $\varepsilon$-packing of the manifold class by
local bumping. Here, in dimension $d=1$ and codimension $n-d=1$, each bump has
the two options “upwards” and “downwards” within each of the $N\gg 1$
locations, yielding $2^{N}$ $\varepsilon$-separated manifolds.

Note that the $\mathcal{C}^{2}$-like assumption
$\mathrm{rch}_{M}\geq\mathrm{rch}_{\min}$ forces to spread each of these bumps
on a ball of radius $\Omega(\sqrt{\mathrm{rch}_{\min}\varepsilon})$.
Intuitively, in this construction, the larger the surface area
$\mathcal{H}^{d}(M_{0})$ of the base manifold $M_{0}$, the more room to
include many bumps on it, and hence the stronger the lower bound. Hence, in
the bounding ball model, we exhibit manifolds that can have large volume,
while remaining in $\mathrm{B}(0,R)$ and with reach
$\mathrm{rch}_{M}\geq\mathrm{rch}_{\min}$. This is done by gluing next to each
other linkable _widgets_ along a long path in the cubic grid in
$\mathrm{B}(0,R)$ (see Section H.2). Overall, this construction allows to get
the correct dependency in $1/f_{\min}$ — which plays the role of a maximal
volume, see Section 2.2.3 — in the bounds.

[Fixed point model]

If $0\in M_{0}$, the above construction is possible while preserving the point
$0\in\mathbb{R}^{n}$ within all the bumped manifolds, yielding the lower bound
(Theorem 5.3).

[Bounding ball model]

As in this model, no point is fixed, we build another type of
$\varepsilon$-packing by translating a base manifold
$M_{0}\subseteq\mathrm{B}(0,R/2)$ in the ambient space by all the possible
vectors of an $\varepsilon$-packing of the ambient ball $\mathrm{B}(0,R/2)$,
which has size $\Omega((R/\varepsilon)^{n})$. This yields the first term of
the lower bound, while the second term follows as described above, by locally
bumping a manifold $M_{0}\subseteq\mathrm{B}(0,R)$ (Theorem 5.6).

##### Informational Lower Bounds.

In addition, forgetting about the number of queries SQ algorithms may do, they
have a limited precision $\varepsilon$ given tolerance $\tau$. Hence, aiming
at lower bounding this best precision $\varepsilon(\tau)$ achievable in
$\mathrm{STAT}(\tau)$, we notice that two distributions that are closer than
$\tau/2$ in total variation distance allow an adversarial oracle to swap their
respective answers, and hence make them — and their supports —
indistinguishable using SQ’s. This idea is at the core of standard lower
bounds in the sample framework [Yu97], and is formalized in the so-called _Le
Cam’s lemma_ for SQ’s (Theorem G.1).

Figure 2: Indistinguishable manifolds for the informational lower bound. The
measure on which they differ being of order $O(\tau)$, an adversarial
$\mathrm{STAT}(\tau)$-oracle may fool the learner and force them to make an
error proportional to the Hausdorff distance between them.

To build such indistinguishable manifolds, we locally bump a base manifold
$M_{0}$ at a single location. As $M_{0}$ supports a $d$-dimensional measure
with density lower bounded by $f_{\min}$, the largest possible width of such a
bump is of order $\delta=\Omega((\tau/f_{\min})^{1/d})$, since the $d$-volume
of this area multiplied by $f_{\min}$ (i.e. total variation) gets of order
$\Omega(\tau)$. Similarly as above, given the width $\delta$ of this bump, its
largest possible height is
$\varepsilon=\Omega\left(\delta^{2}/\mathrm{rch}_{\min}\right)=\Omega\left(\mathrm{rch}_{\min}\left(\frac{\tau}{f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/d}\right)$,
which provides the $\varepsilon$-separated manifolds indistinguishable in
$\mathrm{STAT}(\tau)$. This yields the announced informational lower bounds
(Theorems 5.2 and 5.5), after picking manifolds $M_{0}$ in the fixed point and
bounding model respectively that have volume of order $1/f_{\min}$, and the
uniform distributions on them.

##  2 Preliminaries

###  2.1 Statistical Query Framework

To begin with the formal presentation of this work, let us define the
statistical query (SQ) framework used throughout the paper. In the SQ
framework, the algorithm (or learner) is allowed to access to the unknown
underlying distribution $D$ over $\mathbb{R}^{n}$ via an adversarial oracle
$\mathsf{O}$ who knows it perfectly. The learner also has access to some prior
information on $D$ via the knowledge of a _model_ $\mathcal{D}$, i.e. a set of
probability distributions over $\mathbb{R}^{n}$ assumed to contain $D$. For a
measurable function $r:\mathbb{R}^{n}\to[-1,1]$, called _query_ , the oracle
answers the mean value $\mathop{\mathbb{E}}_{x\sim D}[r(x)]$ of $r$ with
respect to $D$, up to some adversarial error $\tau$ known to both parties.

Let $\mathfrak{F}$ denote the set of Borel-measurable functions from
$\mathbb{R}^{n}$ to $[-1,1]$. An _oracle_ provides answers
$\mathrm{a}:\mathfrak{F}\to\mathbb{R}$. Given a query $r\in\mathfrak{F}$ and a
tolerance parameter $\tau\geq 0$, we say that $\mathsf{O}$ is a _valid_
$\mathrm{STAT}(\tau)$ oracle for the distribution $D$ over $\mathbb{R}^{n}$ if
its answers are such that $\left|\mathrm{a}(r)-\mathop{\mathbb{E}}_{x\sim
D}[r(x)]\right|\leq\tau$. Let us insist on the fact that the oracle is
adversarial, meaning that it can answer _any_ such values. Its adversarial
strategy can also adapt to the previous queries made by the learner. See
formal Definition 2.1).

We now describe the estimation framework using SQ’s. Given a metric space
$(\Theta,\rho)$, a target precision $\varepsilon>0$ and a parameter of
interest $\theta:\mathcal{D}\to\Theta$, the learner aims at estimating
$\theta(D)$ with precision $\varepsilon$ for the metric $\rho$ with a minimum
number of queries $r:\mathbb{R}^{n}\to[-1,1]$, uniformly over the model
$\mathcal{D}$. The present framework is a particular case of the _search
problems_ considered in [Fel17], where a metric on $\Theta$ is not necessarily
available.

######  Remark 2.1.

Manifold estimation will naturally bring us to consider the support
$\theta(D)=\mathrm{Supp}(D)\subseteq\mathbb{R}^{n}$ as the parameter of
interest, and the Hausdorff distance $\rho=\mathrm{d_{H}}$. However, we
present the broader setting of a general metric space $(\Theta,\rho)$ of
estimation, to also cover the intermediate results required by the SQ versions
of the routines of Manifold Propagation (see Section 4). Namely, it will
involve the Euclidean space $(\mathbb{R}^{n},\left\|\cdot\right\|)$ for point
estimation, and the matrix spaces $(\mathbb{R}^{n\times
n},\left\|\cdot\right\|_{\mathrm{F}})$ and $(\mathbb{R}^{n\times
n},\left\|\cdot\right\|_{\mathrm{op}})$.

This paper considers interactive SQ algorithms, meaning that the learner is
allowed to interact with the oracle dynamically and does not have to send all
their queries at once before any answer. That is, query functions are allowed
to depend arbitrarily on the previous answers given by the oracle. More
formally, we give the following Definition 2.1.

######  Definition 2.1 (Deterministic Statistical Query Estimation Framework).

  * •

A _statistical query algorithm making $q$ queries_ is a tuple
$\mathtt{A}=(r_{1},\dots,r_{q},\hat{\theta})$, where

$r_{1}\in\mathfrak{F},~{}r_{2}:\mathbb{R}\to\mathfrak{F},~{}\cdots,~{}r_{q}:\mathbb{R}^{q-1}\to\mathfrak{F},\text{
and }\hat{\theta}:\mathbb{R}^{q}\to\Theta.$

  * •

Let $\mathrm{a}_{1}:\mathfrak{F}\to\mathbb{R}$,
$\mathrm{a}_{2}:\mathfrak{F}^{2}\to\mathbb{R}$, …,
$\mathrm{a}_{q}:\mathfrak{F}^{q}\to\mathbb{R}$. We say that
$\mathsf{O}=(\mathrm{a}_{1},\dots,\mathrm{a}_{q})$ is a _$\mathrm{STAT}(\tau)$
oracle for SQ algorithms making $q$ queries on the distribution $D$_, if for
all $r_{1}\in\mathfrak{F}$, $r_{2}:\mathbb{R}\to\mathfrak{F}$, …,
$r_{q}:\mathbb{R}^{q-1}\to\mathfrak{F}$,

$\displaystyle\bigl{|}\mathrm{a}_{1}(r_{1})-\mathop{\mathbb{E}}_{x\sim
D}\bigl{[}r_{1}(x)\bigr{]}\bigr{|}$ $\displaystyle\leq\tau,$
$\displaystyle\bigl{|}\mathrm{a}_{2}(r_{1},r_{2})-\mathop{\mathbb{E}}_{x\sim
D}\bigl{[}r_{2}(\mathrm{a}_{1}(r_{1}))(x)\bigr{]}\bigr{|}$
$\displaystyle\leq\tau,$ $\displaystyle\vdots$
$\displaystyle\bigl{|}\mathrm{a}_{q}(r_{1},\dots,r_{q})-\mathop{\mathbb{E}}_{x\sim
D}\bigl{[}r_{q}(\mathrm{a}_{1}(r_{1}),\dots,\mathrm{a}_{q-1}(r_{1}))(x)\bigr{]}\bigr{|}$
$\displaystyle\leq\tau.$

  * •

The _output_ of $\mathtt{A}=(r_{1},\dots,r_{q},\hat{\theta})$ when it
interacts with the oracle $\mathsf{O}=(\mathrm{a}_{1},\ldots,\mathrm{a}_{q})$
is defined by

$\hat{\theta}(r_{1},\dots,r_{q};\mathsf{O})=\hat{\theta}(\mathrm{a}_{1}(r_{1}),\dots,\mathrm{a}_{q}(r_{1},\dots,r_{q})).$

  * •

Given a model $\mathcal{D}$ over $\mathbb{R}^{n}$ (i.e. a set of probability
distributions), we say that a SQ algorithm $\mathtt{A}$ is a
_$\mathrm{STAT}(\tau)$ estimator with precision $\varepsilon$ for the
statistical estimation problem $\theta:\mathcal{D}\to\Theta$_ if for all
$D\in\mathcal{D}$ and all valid $\mathrm{STAT}(\tau)$ oracle $\mathsf{O}$ for
$D$,

$\rho\big{(}\theta(D),\hat{\theta}(r_{1},\dots,r_{q};\mathsf{O})\big{)}\leq\varepsilon.$

Beyond deterministic algorithms, one may allow the learner to access
randomness, and to fail at estimating the parameter of interest with some
controlled probability $\alpha<1$ [Kea98, Fel17]. This gives rise to the
following Definition 2.2.

######  Definition 2.2 (Randomized SQ Estimation Framework).

  * •

A _randomized SQ algorithm_ $\mathcal{A}$ is a distribution over SQ
algorithms.

  * •

Given a model $\mathcal{D}$ over $\mathbb{R}^{n}$, we say that a randomized SQ
algorithm $\mathcal{A}$ is a _ $\mathrm{STAT}(\tau)$ algorithm with precision
$\varepsilon$ and probability of failure (or error) $\alpha$ over
$\mathcal{D}$_, if for all distribution $D\in\mathcal{D}$ and all valid
$\mathrm{STAT}(\tau)$ oracle $\mathsf{O}$ for $D$,

$\Pr_{\mathtt{A}=(r_{1},\dots,r_{q},\hat{\theta})\sim\mathcal{A}}\Big{[}\rho\big{(}\theta(D),\hat{\theta}(r_{1},\dots,r_{q};\mathsf{O})\big{)}\leq\varepsilon\Big{]}\geq
1-\alpha.$

Naturally, any SQ algorithm making at most $q$ queries can be emulated into a
PAC algorithm by considering empirical averages. Indeed, given independent and
identically distributed data $\\{X_{1},\ldots,X_{s}\\}$ with common
distribution $D$, Hoeffding’s inequality yields that the oracle which answers
$\mathrm{a}=\frac{1}{s}\sum_{i=1}^{s}r(X_{i})$ to any query
$r:\mathbb{R}^{n}\to[-1,1]$ satisfies
$|\mathrm{a}-\mathop{\mathbb{E}}_{P}[r]|\leq\tau$ with probability $\geq
1-2e^{-s\tau^{2}/2}$ . Therefore, if we can estimate
$\theta:\mathcal{D}\to\Theta$ “efficiently” in $\mathrm{STAT}(\tau)$, so do we
in the PAC (sample) framework, with sample complexity
$s\leq\frac{q\sqrt{\log(q/\alpha)}}{\tau^{2}}.$ .

A priori, randomized algorithms may require significantly less queries than
deterministic ones to achieve an estimation task [Fel17]. However, we will
show that this phenomenon does not occur for manifold estimation, as soon as
the probability of error $\alpha$ is not considerably close to $1$. For this,
we will exhibit upper bounds using _deterministic_ algorithms, and matching
lower bounds on _randomized_ algorithms. See Section 5 for the precise
statements.

######  Remark 2.2 (About Noise).

The statistical models considered in this work (Definition 2.5) are noise-
free, in the sense that the $\mathrm{STAT}(\tau)$ oracle — although
adversarial — has access to the exact underlying distribution $D$. Beyond such
an exact model, a noise model that is particularly popular in the manifold
estimation literature is the so-called _clutter noise_ model [AL18, GPPVW12a].
Given a nuisance parameter $\beta\in(0,1]$ and a fixed noise distribution
$Q_{0}$ over $\mathbb{R}^{n}$ — usually the ambient uniform distribution over
a compact set of $\mathbb{R}^{n}$ —, the associated clutter noise model is the
set of mixtures

$\mathcal{D}^{\mathrm{(clutter)}}_{\beta,Q_{0}}=\left\\{{\beta
D+(1-\beta)Q_{0},D\in\mathcal{D}}\right\\}.$

In particular, $\mathcal{D}^{\mathrm{(clutter)}}_{\beta=1,Q_{0}}$ coincides
with $\mathcal{D}$. For $\beta<1$, in the independent and identically
distributed (i.i.d.) sampling framework, it yields samples with a proportion
of approximately $\beta$ informative points and $(1-\beta)$ of non-informative
clutter points.

As mentioned in the introduction, this type of noise model gave rise to subtle
iterative decluttering procedures that rely heavily on the properties of
$Q_{0}$ (i.e. being ambient uniform) [AL18]. This noise-specificity is also a
limitation of the (intractable) estimator of [GPPVW12a], which would also fail
with clutter distributions $Q_{0}$ other than uniform. In contrast, in the
statistical query framework, if $\beta$ and $Q_{0}$ are known, then estimation
techniques need not be much more elaborate for the case $\beta<1$ than for
$\beta=1$. Indeed, the statistical query complexity of an estimation problem
in $\mathrm{STAT}(\tau)$ over $\mathcal{D}^{\mathrm{(clutter)}}_{\beta,Q_{0}}$
coincides with its counterpart in $\mathrm{STAT}(\tau/\beta)$ over
$\mathcal{D}$.

The correspondence is explicit: algorithms designed for $\beta=1$ naturally
generalize for $\beta<1$ and vice-versa. To see this, let
$r:\mathbb{R}^{n}\to[-1,1]$ be a query to a $\mathrm{STAT}(\tau)$ oracle with
true distribution $D^{\mathrm{(clutter)}}=\beta D+(1-\beta)Q_{0}$. Say that
the learner gets answer $\mathrm{a}\in\mathbb{R}$, then the function returning
$\mathrm{a}^{\prime}=(\mathrm{a}-(1-\beta)\mathop{\mathbb{E}}_{Q_{0}}[r])/\beta$,
which can be computed by the learner who knows $Q_{0}$ and $\beta$, clearly
simulates a valid $\mathrm{STAT}(\tau/\beta)$ oracle to the query for the
distribution $D$. For the same reason, conversely, any
$\mathrm{STAT}(\tau/\beta)$-algorithm over $\mathcal{D}$ yields a
$\mathrm{STAT}(\tau)$-algorithm in
$\mathcal{D}^{\mathrm{(clutter)}}_{\beta,Q_{0}}$.

This shows that the statistical query complexity in $\mathrm{STAT}(\tau)$ over
$\mathcal{D}$ coincides with its counterpart in $\mathrm{STAT}(\beta\tau)$
over $\mathcal{D}^{\mathrm{(clutter)}}_{\beta,Q_{0}}$ for any fixed
$0<\beta\leq 1$ and clutter distribution $Q_{0}$. Conversely, any SQ algorithm
in the clutter-free model can easily be made robust to clutter noise, as soon
as the clutter distribution $Q_{0}$ and noise level $0<\beta\leq 1$ are known
to the learner.

As a first illustration of a non-trivial SQ estimation problem, let us
describe that of the mean $\mathop{\mathbb{E}}_{x\sim D}[F(x)]$ of a bounded
vector-valued function ${F:\mathbb{R}^{n}\to\mathbb{R}^{k}}$, where
$\left\|F(x)\right\|\leq 1$, see [FGV21]. Here and below,
$\left\|\cdot\right\|$ stands for the Euclidean norm. This example will be
central in the construction of our SQ geometric routines (Theorems 4.1, 4.3
and 4.2), and hence for the final SQ manifold estimation algorithms (Theorems
5.4 and 5.1).

One query to a $\mathrm{STAT}(\tau)$ oracle allows to compute the mean value
of a function ranging in $[-1,1]$ with precision $\tau$. Hence, the $k$
coordinate functions
$r_{i}(x)=\left\langle{e_{i}},{F(x)}\right\rangle\in[-1,1]$ are valid queries,
and allow to estimate each coordinate of $\mathop{\mathbb{E}}_{x\sim D}[F(x)]$
with precision $\tau$. This naive strategy results in a deterministic SQ
algorithm making $k$ queries to $\mathrm{STAT}(\tau)$ and precision $\tau$ for
the sup-norm, but only $\sqrt{k}\tau$ for the Euclidean norm. The following
Lemma 2.1 shows that the learner may ask $2k$ queries to a
$\mathrm{STAT}(\tau)$ oracle, while still preserving a precision of order
$\tau$ for the Euclidean norm. The strategy consists in querying $F$ in a
suitable frame of $\mathbb{R}^{k}$ [FGV21, Theorem 3.9], i.e. a redundant
family of vectors of $\mathbb{R}^{k}$ which avoids the extra $\sqrt{k}$ factor
of the non-redundant coordinate-wise queries.

######  Lemma 2.1.

Let $D$ be a Borel probability distribution on $\mathbb{R}^{n}$, and
${F:\mathbb{R}^{n}\to\mathbb{R}^{k}}$ be such that $\left\|F(x)\right\|\leq 1$
for all $x\in\mathbb{R}^{n}$.

There exists a deterministic statistical query algorithm making $2k$ queries
to a $\mathrm{STAT}(\tau)$ oracle, and that estimates
$\mathop{\mathbb{E}}_{x\sim D}\left[F(x)\right]$ with precision $C\tau$ for
the Euclidean norm, where $C>0$ is a universal constant.

###### Proof of Lemma 2.1.

Let us denote by $D^{\prime}$ the pushforward distribution of $D$ by $F$. As
for all measurable function $r:\mathbb{R}^{k}\to[-1,1]$,

$\mathop{\mathbb{E}}_{x^{\prime}\sim
D^{\prime}}[r(x^{\prime})]=\mathop{\mathbb{E}}_{x\sim D}[r(F(x))],$

any valid $\mathrm{STAT}(\tau)$ oracle for $D$ simulates a valid
$\mathrm{STAT}(\tau)$ oracle for $D^{\prime}$. Hence, applying [FGV21, Theorem
3.9] to $D^{\prime}$, we get the desired result. ∎

###  2.2 Manifold Regularity and Distributional Assumptions

####  2.2.1 General Notation and Differential Geometry

From now on, $n\geq 2$ is referred to as the ambient dimension and
$\mathbb{R}^{n}$ is endowed with the Euclidean inner product
$\left\langle\cdot,\cdot\right\rangle$ and the associated norm
$\left\|\cdot\right\|$. The closed Euclidean ball of center $x$ and radius $r$
is denoted by $\mathrm{B}(x,r)$. The volume of the $d$-dimensional unit ball
$\mathrm{B}_{d}(0,1)$ is denoted by $\omega_{d}$, and that of the
$d$-dimensional unit sphere $\mathcal{S}^{d}(0,1)\subseteq\mathbb{R}^{d+1}$ by
$\sigma_{d}$.

We will consider compact connected submanifolds $M$ of $\mathbb{R}^{n}$,
without boundary, and with dimension $d<n$ [dC92]. Given a point $p\in M$, the
tangent space of $M$ at $p$, denoted by $T_{p}M$, is the $d$-dimensional
linear subspace of $\mathbb{R}^{n}$ spanned by the velocity vectors at $p$ of
$\mathcal{C}^{1}$ curves of $M$. The Grassmannian $\mathbb{G}^{n,d}$ is the
set of all the $d$-dimensional linear subspaces of $\mathbb{R}^{n}$, so that
$T_{p}M\in\mathbb{G}^{n,d}$ for all $p\in M$. In addition to the Euclidean
structure induced by $\mathbb{R}^{n}$ on $M\subseteq\mathbb{R}^{n}$, we also
endow $M$ with its intrinsic geodesic distance $\mathrm{d}_{M}$, with
$\mathrm{B}_{M}(p,s)$ denoting the closed geodesic ball of center $p\in M$ and
of radius $s$. More precisely, given a $\mathcal{C}^{1}$ curve
$c:[a,b]\rightarrow M$, the length of $c$ is defined as
$\mathrm{Length}(c)=\int_{a}^{b}\left\|c^{\prime}(t)\right\|dt$. Given $p,q\in
M$, there always exists a path $\gamma_{p\rightarrow q}$ of minimal length
joining $p$ and $q$ [dC92]. Such a curve $\gamma_{p\rightarrow q}$ is called
geodesic, and the geodesic distance between $p$ and $q$ is given by
$\mathrm{d}_{M}(p,q)=\mathrm{Length}(\gamma_{p\rightarrow q})$ [BBI01, Chapter
2]. In particular, $(M,\mathrm{d}_{M})$ is a length space [BBI01, Remark
5.1.7]. A geodesic $\gamma$ such that $\left\|\gamma^{\prime}(t)\right\|=1$
for all $t$ is called arc-length parametrized. Unless stated otherwise, we
always assume that geodesics are parametrized by arc-length. For all $p\in M$
and all unit vectors $v\in T_{p}M$, we denote by $\gamma_{p,v}$ the unique
arc-length parametrized geodesic of $M$ such that $\gamma_{p,v}(0)=p$ and
$\gamma^{\prime}_{p,v}(0)=v$ [dC92]; the exponential map is defined as
$\exp_{p}^{M}(vt)=\gamma_{p,v}(t)$. Note that from the compactness of $M$,
$\exp_{p}^{M}:T_{p}M\rightarrow M$ is defined globally on $T_{p}M$ [BBI01,
Theorem 2.5.28].

####  2.2.2 Geometric and Statistical Models

Let us detail the geometric assumptions we will make throughout. Besides the
differential structure given by low-dimensional submanifolds, the core
regularity assumption of this work will be encoded by the _reach_ , a central
quantity in the statistical analysis of geometric structures (see [AKC+19] and
references therein), and that we now describe.

To this aim, let us define the _medial axis_ $\mathrm{Med}(K)$ of a closed
subset $K\subseteq\mathbb{R}^{n}$ as the set of ambient points that have at
least two nearest neighbors on $K$. Namely, if we let
$\mathrm{d}(z,K)=\inf_{p\in K}\left\|p-z\right\|$ denote the distance function
to $K$,

$\displaystyle\mathrm{Med}(K)=\left\\{{z\in\mathbb{R}^{n}~{}|~{}\exists p\neq
q\in K,\left\|p-z\right\|=\left\|q-z\right\|=\mathrm{d}(z,K)}\right\\}.$

By definition of the medial axis, the _metric projection onto $K$_, given by

$\displaystyle\pi_{K}(z)=\operatornamewithlimits{argmin}_{p\in
K}\left\|p-z\right\|$

is well defined exactly on $\mathbb{R}^{n}\setminus\mathrm{Med}(K)$. The reach
of $K$ is then defined as the minimal distance from $K$ to $\mathrm{Med}(K)$.

######  Definition 2.3 ([Fed59, Theorem 4.18]).

The _reach_ of a closed subset $K\subseteq\mathbb{R}^{n}$ is defined by

$\displaystyle\mathrm{rch}_{K}$
$\displaystyle=\inf_{z\in\mathrm{Med}(K)}\mathrm{d}(z,K).$

Furthermore, if $K=M\subseteq\mathbb{R}^{n}$ is a
$\mathcal{C}^{2}$-submanifold, then its reach can be written as

$\displaystyle\mathrm{rch}_{M}$ $\displaystyle=\inf_{p\neq q\in
M}\frac{\left\|q-p\right\|^{2}}{\mathrm{d}(q-p,T_{p}M)}.$

The second formulation of Definition 2.3 assesses how a large positive reach
testifies of a quantitative uniform regularity of $M\subseteq\mathbb{R}^{n}$.
Indeed, the submanifold $M$ being $\mathcal{C}^{2}$-smooth essentially means
that locally, $M$ deviates at most quadratically from its tangent spaces.
Adding the condition $\mathrm{rch}_{M}\geq\mathrm{rch}_{\min}>0$ yields the
quantitative bound
$\mathrm{d}(q-p,T_{p}M)\leq\left\|q-p\right\|^{2}/(2\mathrm{rch}_{\min})$ for
all $p,q\in M$. In particular, this condition bounds curvature and intrinsic
metric properties (see Lemma 2.2). We shall refer the interested reader to
[AKC+19] for further discussions on the reach.

######  Definition 2.4.

We let $\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ denote the class of
compact connected $d$-dimensional $\mathcal{C}^{2}$-submanifolds $M$ of
$\mathbb{R}^{n}$, without boundary, that have reach bounded below by
$\mathrm{rch}_{M}\geq\mathrm{rch}_{\min}$.

Among the key properties shared by submanifolds $M$ with reach bounded below
$\mathrm{rch}_{M}\geq\mathrm{rch}_{\min}$ are a quantitative equivalence
between the Euclidean and geodesic distances, and the fact that their
curvature is uniformly bounded by $1/\mathrm{rch}_{\min}$.

######  Lemma 2.2.

Let $M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ and $p,q\in M$. If
$\left\|q-p\right\|<2\mathrm{rch}_{\min}$, then

$\displaystyle\left\|q-p\right\|\leq\mathrm{d}_{M}(p,q)\leq
2\mathrm{rch}_{\min}\arcsin{\left(\frac{\left\|q-p\right\|}{2\mathrm{rch}_{\min}}\right)}.$

In particular, for all $r<2\mathrm{rch}_{\min}$,

$\displaystyle\mathrm{B}\left(p,r\left(1-\left(r/\mathrm{rch}_{\min}\right)^{2}/24\right)\right)\cap
M$ $\displaystyle\subseteq\mathrm{B}_{M}(p,r)$
$\displaystyle\subseteq\mathrm{B}(p,r)\cap M$
$\displaystyle\subseteq\mathrm{B}_{M}\left(p,r\left(1+\left(r/\mathrm{rch}_{\min}\right)^{2}/4\right)\right).$

Furthermore, if $\gamma:[a,b]\to M$ is an arc-length parametrized geodesic,
then for all $t\in[a,b]$, $\left\|\gamma^{\prime\prime}(t)\right\|\leq
1/\mathrm{rch}_{\min}$.

###### Proof of Lemma 2.2.

We clearly have $\left\|q-p\right\|\leq\mathrm{d}_{M}(p,q)$, and the upper
bound comes from [BLW19, Lemma 3]. The ball inclusions then follow from the
elementary bounds $\sin s\geq s(1-s^{2}/6)$ for $s\geq 0$, and $\arcsin u\leq
u(1+u^{2})$ for $0\leq u\leq 1$. The last claim is a rephrasing of [NSW08,
Proposition 6.1]. ∎

These estimates will be used to compare, in a quantitative way, the (curved)
geometry of $M$ with that of the (flat) Euclidean $d$-dimensional space.
Finally, we present the following uniform estimate on the massivity of
submanifolds $M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$, which we will
use below to show that Manifold Propagation terminates. For $\delta>0$, the
$\delta$-packing number $\mathrm{pk}_{M}(\delta)$ of
$M\subseteq\mathbb{R}^{n}$ is the maximal cardinal $k$ of a set of points
$\left\\{{p_{i}}\right\\}_{1\leq i\leq k}\subseteq M$ such that
$\mathrm{B}(p_{i},\delta)\cap\mathrm{B}(p_{j},\delta)=\emptyset$ for all
$i\neq j$ (i.e. $\left\|p_{i}-p_{i}\right\|>2\delta$) (see Section B.2 for
more details).

######  Lemma 2.3.

Let $M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$. Then for all
$\delta\leq\mathrm{rch}_{\min}/8$,

$\mathrm{pk}_{M}(\delta)\leq\dfrac{\mathcal{H}^{d}(M)}{\omega_{d}(\delta/4)^{d}},$

where $\mathcal{H}^{d}(M)$ denotes the surface area of $M$.

###### Proof of Lemma 2.3.

Follows from Proposition B.2 and Proposition B.3. ∎

Based on the geometric model above (Definition 2.4), we now describe the
statistical model (i.e. set of probability distributions) of this work. Every
$M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ inherits a non-trivial
finite measure induced by the $d$-dimensional Hausdorff measure
$\mathcal{H}^{d}$ on $\mathbb{R}^{n}\supseteq M$, defined by
$\mathrm{vol}_{M}=\mathbbm{1}_{M}\mathcal{H}^{d}$, and called the volume
measure of $M$. Note that with this normalization,
$\mathrm{vol}_{M}(M)=\mathcal{H}^{d}(M)$ corresponds to the $d$-dimensional
surface area of $M$, and $\mathrm{vol}_{M}/\mathcal{H}^{d}(M)$ corresponds to
the uniform probability distribution on $M$.

######  Definition 2.5.

We let
$\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
denote the set of Borel probability distributions $D$ on $\mathbb{R}^{n}$ with
$M=\mathrm{Supp}(D)\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ and a
density $f$ with respect to $\mathrm{vol}_{M}$ such that:

  * •

$f$ is bounded away from zero and infinity: $0<f_{\min}\leq f(x)\leq
f_{\max}<\infty$ for all $x\in M$.

  * •

$f$ is $L$-Lipschitz over $M$: $|f(x)-f(y)|\leq L\left\|x-y\right\|$ for all
$x,y\in M$.

In this model, as will be clear below, the extra degree of freedom allowed by
the density $f$ being non-constant will contribute in the final estimation
rate and query complexity, especially through the lower bound $f_{\min}$. On
the geometric side, $f_{\min}^{-1}$ and $f_{\max}^{-1}$ impose quantitative
restrictions on the volume $\mathcal{H}^{d}(M)$ of $M$ (see Section 2.2.3).

Since $\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
is invariant by translations in $\mathbb{R}^{n}$, this model actually provides
insufficient prior information to derive any uniform SQ complexity bound over
it. This contrasts sharply with the sample framework [AL18, GPPVW12a], where
the sample points provide automatic location information and yields finite
sample complexity over
$\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$.

######  Proposition 2.1.

Assume that $\sigma_{d}f_{\min}\mathrm{rch}_{\min}^{d}\leq 1$. Then for all
$\varepsilon>0$, manifold estimation over
$\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$ with
precision $\varepsilon$ has infinite randomized statistical query complexity.

The assumption that $\sigma_{d}f_{\min}\mathrm{rch}_{\min}^{d}\leq 1$ is made
to preclude degeneracy of the model. It can be shown to be necessary (see
Section 2.2.3 below for a more detailed discussion). The proof of Proposition
2.1 relies on the fact that the supports $\mathrm{Supp}(D)$ of distributions
$D\in\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
form an unbounded class for the Hausdorff distance. It is therefore natural to
add an extra location constraint to the model. We study two different such
constraints. The first one fixes membership of a distinguished point to $M$,
which we take to be the origin $0\in\mathbb{R}^{n}$ without loss of
generality. The second one bounds the problem in an ambient ball of radius
$R>0$, which we take to be centered at the origin $\mathrm{B}(0,R)$ without
loss of generality.

######  Definition 2.6.

Completing the framework of Definition 2.5, we consider the two following
models.

  * •

Fixed point model:

    * –

$\left\\{{0}\right\\}\sqcup\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$
denotes the set of manifolds $M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$
such that $0\in M$;

    * –

The model
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
stands for the set of distributions
$D\in\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
with support such that $0\in M=\mathrm{Supp}(D).$

  * •

Bounding ball model: given $R>0$,

    * –

$\mathrm{B}(0,R)\sqcap\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ denotes the
set of manifolds $M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ such that
$M\subseteq\mathrm{B}(0,R)$;

    * –

The model
$\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
stands for the set of distributions
$D\in\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
with support such that $\mathrm{Supp}(D)=M\subseteq\mathrm{B}(0,R).$

Let us now discuss some features imposed by the above models.

####  2.2.3 On Some Implicit Bounds on the Model Parameters

Although not explicit in Definition 2.6, parameters of the models are not
arbitrary. That is,
$\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$ might
be degenerate or even empty in some regimes of parameters, making the manifold
estimation problem vacuous. The reason for this resides in implicit volume
bounds imposed by the reach. Indeed, if
$D\in\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
has support $M$, then since $D$ is a probability distribution,

$f_{\min}\mathcal{H}^{d}(M)\leq 1=\int_{M}f\mathrm{d}\mathcal{H}^{d}\leq
f_{\max}\mathcal{H}^{d}(M).$

As a result, the volume estimates of Proposition B.5 yield

$\displaystyle
f_{\min}\leq\frac{1}{\mathcal{H}^{d}(M)}\leq\frac{1}{\sigma_{d}\mathrm{rch}_{\min}^{d}}\leq\frac{1}{\omega_{d}\mathrm{rch}_{\min}^{d}}.$

If furthermore,
$D\in\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
(i.e. $M\subseteq\mathrm{B}(0,R)$), then

$\displaystyle
f_{\max}\geq\frac{1}{\mathcal{H}^{d}(M)}\geq\frac{1}{\left(\frac{18R}{\mathrm{rch}_{\min}}\right)^{n}\omega_{d}\left(\frac{\mathrm{rch}_{\min}}{2}\right)^{d}}.$

Note that Proposition B.5 also yields that
$R\geq\mathrm{rch}_{\min}/\sqrt{2}$. Consequently, to ensure non-vacuity of
the models, and without loss of generality, it is natural to take the
following setup. Here, $C_{\square}$ stands for a constant depending only on
$\square$.

  * •

When working over
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$,
we will always assume that $f_{\min}\leq f_{\max}$, $R\geq
C\mathrm{rch}_{\min}$, and

$\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}\leq C_{d}^{-1},$

for some large enough constant $C_{d}>0$.

  * •

When working over
$\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$,
we will always assume that $f_{\min}\leq f_{\max}$, $R\geq
C\mathrm{rch}_{\min}$,

$\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}\leq
C_{d}^{-1}\text{~{}~{}and~{}~{}}\omega_{d}f_{\max}\mathrm{rch}_{\min}^{d}\geq
C_{n,d}\left(\frac{\mathrm{rch}_{\min}}{R}\right)^{n},$

for some large enough constants $C,C_{d},C_{n,d}>0$.

See Appendix B for a more thorough exposition of the technical properties of
the models
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
and
$\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$.

###  2.3 Manifold Reconstruction from Point Clouds

Following the recent line of research on manifold estimation [GPPVW12b,
GPPVW12a, AL18, AL19, Div21a], we will measure the accuracy of estimators
$\hat{M}$ of manifolds $M$ via the so-called _Hausdorff distance_ , which
plays the role of an $L^{\infty}$-distance between compact subsets of
$\mathbb{R}^{n}$. To this aim, we will need the following piece of notation.
For $K\subseteq\mathbb{R}^{n}$ and $r\geq 0$, we let $K^{r}$ denote the _$r$
-offset of $K$_:

$\displaystyle K^{r}:=\left\\{{z\in\mathbb{R}^{n},\mathrm{d}(z,K)\leq
r}\right\\},$ (1)

where we recall that $\mathrm{d}(z,K)=\inf_{p\in K}\left\|p-z\right\|$ is the
function distance to $K$.

######  Definition 2.7 (Hausdorff Distance [BBI01, Section 7.3.1]).

Given two compact subsets $K,K^{\prime}\subseteq\mathbb{R}^{n}$, the
_Hausdorff distance_ between them is

$\displaystyle\mathrm{d_{H}}(K,K^{\prime})$
$\displaystyle=\sup_{x\in\mathbb{R}^{n}}|\mathrm{d}(x,K)-\mathrm{d}(x,K^{\prime})|$
$\displaystyle=\inf\left\\{{r>0,K\subseteq(K^{\prime})^{r}\text{ and
}K^{\prime}\subseteq K^{r}}\right\\}.$

Manifold reconstruction from point clouds has been extensively studied in the
area of computational geometry [Dey07, BG14]. In this field, the learner is
given a sample of $M$, usually seen as deterministic, and the goal is to build
efficiently a reliable triangulation $\hat{M}$ of $M$, either topologically,
geometrically, or both. Such a construction actually is always possible,
provided that the point cloud is sufficiently close and dense in $M$, and that
the learner is provided with tangent space estimates at these points. This is
formalized in the following Theorem 2.1, where
$\left\|\cdot\right\|_{\mathrm{op}}$ stands for the operator norm over the set
of matrices.

######  Theorem 2.1 (Adapted from [AL18, Theorem 4.4]).

There exists $\lambda_{d}>0$ such that for all
$\varepsilon\leq\lambda_{d}\mathrm{rch}_{\min}$ and all
$M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$, the following holds.

Let $\mathcal{X}\subseteq\mathbb{R}^{n}$ be a finite point cloud and
$\mathbb{T}_{\mathcal{X}}=\bigl{\\{}T_{x}\bigr{\\}}_{x\in\mathcal{X}}\subseteq\mathbb{G}^{n,d}$
be a family of $d$-dimensional linear subspaces of $\mathbb{R}^{n}$ such that

  * •

$\underset{x\in\mathcal{X}}{\max}\>\mathrm{d}(x,M)\leq\eta$,

  * •

$\underset{p\in M}{\max}\>\mathrm{d}(p,\mathcal{X})\leq\Delta$,

  * •

$\underset{x\in\mathcal{X}}{\max}\>\left\|\pi_{T_{\pi_{M}(x)}{M}}-\pi_{T_{x}}\right\|_{\mathrm{op}}\leq\sin\theta$.

If $\theta\leq\Delta/(1140\mathrm{rch}_{\min})$ and
$\eta\leq\Delta^{2}/(1140\mathrm{rch}_{\min})$, then one can build a
triangulation $\hat{M}=\hat{M}(\mathcal{X},\mathbb{T}_{\mathcal{X}})$ with
vertices in $\mathcal{X}$ such that

  * •

$\mathrm{d_{H}}\bigl{(}M,\hat{M}\bigr{)}\leq
C_{d}\Delta^{2}/\mathrm{rch}_{\min}$,

  * •

$M$ and $\hat{M}$ are ambient isotopic.

###### Proof of Theorem 2.1.

We apply [AL18, Theorem 4.4] on a sparsified subset $\mathcal{X}^{\prime}$ of
$\mathcal{X}$, which is a pruned version of $\mathcal{X}$ that is
$\varepsilon$-sparse but still dense enough in $M$. This subsample
$\mathcal{X}^{\prime}$ can be built explicitly by using the so-called farthest
point sampling algorithm to $\mathcal{X}$ [AL18, Section 3.3]. For this,
initialize $\mathcal{X}^{\prime}$ with
$\mathcal{X}^{\prime}=\left\\{{x_{0}}\right\\}$, where $x_{0}\in\mathcal{X}$
is chosen arbitrarily. Then, while
$\max_{x\in\mathcal{X}}\mathrm{d}(x,\mathcal{X}^{\prime})>\Delta$, find the
farthest point to $\mathcal{X}^{\prime}$ in $\mathcal{X}$, and add it to
$\mathcal{X}^{\prime}$. That is,
$\mathcal{X}^{\prime}\leftarrow\mathcal{X}^{\prime}\cup\left\\{{\operatornamewithlimits{argmax}_{x\in\mathcal{X}}\mathrm{d}(x,\mathcal{X}^{\prime})}\right\\}$
(and if the $\operatornamewithlimits{argmax}$ is not a singleton, pick an
arbitrary element of it). The output
$\mathcal{X}^{\prime}\subseteq\mathcal{X}$ of this algorithm clearly satisfies
$\min_{x^{\prime}\neq
y^{\prime}\in\mathcal{X}^{\prime}}\left\|y^{\prime}-x^{\prime}\right\|\geq\Delta$,
and furthermore,

$\max_{p\in M}\mathrm{d}(p,\mathcal{X}^{\prime})\leq\max_{p\in
M}\mathrm{d}(p,\mathcal{X})+\max_{x\in\mathcal{X}}\mathrm{d}(x,\mathcal{X}^{\prime})\leq
2\Delta.$

Therefore, [AL18, Theorem 4.4] applies to $\mathcal{X}^{\prime}$ and
$\mathbb{T}_{\mathcal{X}^{\prime}}$, and
$\hat{M}(\mathcal{X}^{\prime},\mathbb{T}_{\mathcal{X}^{\prime}})$ provides the
announced triangulation. ∎

Although we will not emphasize on exact topology recovery in the present work,
let us mention that the triangulation $\hat{M}$ actually exhibits the extra
feature of sharing the same topology as $M$, i.e. $M$ and $\hat{M}$ are
isotopy equivalent. Let us also mention that the triangulation can be built in
linear time in $n$, with an explicit polynomial time and space complexity
[BG14, Section 4.6].

Said otherwise, Theorem 2.1 asserts that manifold reconstruction with
precision $\varepsilon$ can be achieved if a sample that is
$(\sqrt{\mathrm{rch}_{\min}\varepsilon})$-dense and $\varepsilon$-close to
$M$, together with associated estimated tangent spaces with precision
$\sqrt{\varepsilon/\mathrm{rch}_{\min}}$, are available to the learner. As
opposed to the sample framework, the statistical framework does not provide
the learner with such data directly. In $\mathrm{STAT}(\tau)$, our strategy
will therefore be to build such a point cloud and tangent spaces iteratively
from queries, using the following purely geometric Manifold Propagation
algorithm.

##  3 Manifold Propagation Algorithm

We now present the Manifold Propagation algorithm and its properties, which
works in a setting where only geometric routines are available to the learner.
Although we will eventually apply this algorithm in the context of statistical
queries (see Section 5), let us insist on the fact that the framework detailed
in this Section 3 is purely geometric, and does not rely specifically on
statistical queries.

As mentioned in the introduction, the idea is to explore the unknown manifold
$M$ via the access to only three complementary geometric routines. Roughly
speaking, Manifold Propagation explores $M$ in a greedy way, while building a
point cloud with associated tangent spaces, by using:

  * •

A seed point $\hat{x}_{0}\in\mathbb{R}^{n}$, known to be close to $M$, and
that allows to initialize the process.

  * •

A tangent space routine $\hat{T}:\mathbb{R}^{n}\to\mathbb{G}^{n,d}$, that
allows to make linear approximations of $M$ nearby points, and hence to
provide local candidate directions to explore next.

  * •

A projection routine $\hat{\pi}:\mathbb{R}^{n}\to\mathbb{R}^{n}$, that
compensates for the errors made by the previous steps, by approximately
projecting points back to $M$.

To avoid redundancy, all this is done while checking that the new candidate
points are not too close to some already-visited region of the space. More
formally, the algorithm runs as described on algorithm 1.

0:

Seed point $\hat{x}_{0}\in\mathbb{R}^{n}$

Tangent space routine $\hat{T}:\mathbb{R}^{n}\to\mathbb{G}^{n,d}$

Projection routine $\hat{\pi}:\mathbb{R}^{n}\to\mathbb{R}^{n}$

Tuning parameters $\Delta,\delta>0$ (scales) and $0<\alpha<\pi/2$ (angle)

1: Initialize $\mathcal{Q}\leftarrow\\{\hat{x}_{0}\\}$,
$\mathcal{O}\leftarrow\emptyset$ and
$\mathbb{T}_{\mathcal{O}}\leftarrow\emptyset$

2: while $\mathcal{Q}\neq\emptyset$ do

3: Pick $x\in\mathcal{Q}$

4: Set $T\leftarrow\hat{T}(x)$ and
$\mathbb{T}_{\mathcal{O}}\leftarrow\mathbb{T}_{\mathcal{O}}\cup\left\\{{T}\right\\}$

5: Consider a maximal $(\sin\alpha)$-packing $v_{1},\dots,v_{k}$ of the sphere
$\mathcal{S}^{d-1}_{T}(0,1)\subseteq T$

6: for $i\in\\{1,\dots,k\\}$ do

7: if $\mathrm{d}\bigl{(}x+\Delta
v_{i},\mathcal{Q}\cup\mathcal{O}\bigr{)}\geq\delta$ then

8: $\mathcal{Q}\leftarrow\mathcal{Q}\cup\bigl{\\{}\hat{\pi}(x+\Delta
v_{i})\bigr{\\}}$

9: end if

10: end for

11: $\mathcal{Q}\leftarrow\mathcal{Q}\setminus\\{x\\}$ and
$\mathcal{O}\leftarrow\mathcal{O}\cup\\{x\\}$

12: end while

13: return $\mathcal{O}$ and $\mathbb{T}_{\mathcal{O}}$

Algorithm 1 Manifold Propagation

In spirit, Manifold Propagation is similar to the _marching cube algorithm_ of
[LC87] and the _tracing algorithm_ of [BKW19], which use calls to an
_intersection oracle_ answering whether a candidate element of a partition of
the ambient space intersects the manifold. However, the approaches of [LC87]
and [BKW19] use static partitions of $\mathbb{R}^{n}$ (cubes and a Coxeter
triangulation respectively), which translates into an exploration complexity
of $M$ — measured in the number of calls made to the oracles/routines — that
strongly depends on the ambient dimension [BKW19, Theorem 24]. In contrast,
Manifold Propagation builds a point cloud nearby $M$ dynamically, which allows
to adapt to its intrinsic low-dimensional geometry. This results in an
exploration complexity that is completely oblivious to the ambient space. That
is, the overall dependency in the ambient dimension is fully supported by the
geometric routines themselves. This can be explained by the intermediate
tangent space estimation routine, that allows the algorithm to only explore
the $d$ local (approximate) tangent directions of $M$ only, while being
oblivious to the $(n-d)\gg d$ non-informative codimensions. As a counterpart,
Manifold Propagation needs to compensate for these local linear approximations
which, although possibly negligible at each iteration, may cumulate into
substantial deviations from the manifold after several steps. This possible
global drift is taken care of via the projection routine, which somehow
reboots the precision of the process when a point is added. To the best of our
knowledge, Manifold Propagation is the first instance of an algorithm working
only with the three geometric routines described above. We now state the main
result presenting its properties.

######  Theorem 3.1 (Properties of Manifold Propagation).

Let $M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$, and assume that there
exist $0\leq\eta\leq\Lambda<\mathrm{rch}_{\min}$ and $0\leq\theta<\pi/2$ such
that:

  1. (i)

$\mathrm{d}(\hat{x}_{0},M)\leq\eta$;

  2. (ii)

For all $x\in\mathbb{R}^{n}$ such that $\mathrm{d}(x,M)\leq\eta$,
$\left\|\pi_{T_{\pi_{M}(x)}M}-\pi_{\hat{T}(x)}\right\|_{\mathrm{op}}\leq\sin\theta;$

  3. (iii)

For all $x\in\mathbb{R}^{n}$ such that $\mathrm{d}(x,M)\leq\Lambda$,
$\left\|\pi_{M}(x)-\hat{\pi}(x)\right\|\leq\eta$.

Assume furthermore that

$\displaystyle 64\eta\leq\Delta\leq\mathrm{rch}_{\min}/24,$
$\displaystyle~{}\max\left\\{{\sin\alpha,\sin\theta}\right\\}\leq 1/64,$
$\displaystyle
5\Delta^{2}/(8\mathrm{rch}_{\min})+\eta+\Delta\sin\theta\leq\Lambda,$
$\displaystyle~{}\text{and}~{}3\Delta/10\leq\delta\leq 7\Delta/10.$

Then, Manifold Propagation terminates, and the number $N_{\mathrm{loop}}$ of
iterations performed in the _while_ loop (Lines 2–12) satisfies

  1. 1.

$N_{\mathrm{loop}}\leq\dfrac{\mathcal{H}^{d}(M)}{\omega_{d}(\delta/32)^{d}},$
where $\mathcal{H}^{d}(M)$ denotes the surface area of $M$.

Furthermore, it outputs a finite point cloud
$\mathcal{O}\subseteq\mathbb{R}^{n}$ that:

  1. 2.

Is $\eta$-close to $M$: $\max_{x\in\mathcal{O}}\mathrm{d}(x,M)\leq\eta$;

  2. 3.

Is a $(\Delta+\eta)$-covering of $M$: $\max_{p\in
M}\mathrm{d}(p,\mathcal{O})\leq\Delta+\eta$;

together with a family
$\mathbb{T}_{\mathcal{O}}=\bigl{\\{}\hat{T}(x)\bigr{\\}}_{x\in\mathcal{O}}\subseteq\mathbb{G}^{n,d}$
of linear spaces that:

  1. 4.

$\theta$-approximate tangent spaces:
$\max_{x\in\mathcal{O}}\left\|\pi_{T_{\pi_{M}(x)}M}-\pi_{\hat{T}(x)}\right\|_{\mathrm{op}}\leq\sin\theta.$

To get to Theorem 3.1, we will need the following series of lemmas, which are
proved in Appendix A. The first statement asserts that the point clouds
$\mathcal{Q}$ and $\mathcal{O}$ that the algorithm builds remain $\eta$-close
to $M$ at all times. The reason for this resides in the fact that this
property holds for the seed point $\hat{x}_{0}$ by assumption, and that the
projection routine $\hat{\pi}$ maintains this $\eta$-closeness when points are
added to $\mathcal{Q}$, and hence to $\mathcal{Q}\cup\mathcal{O}$.

######  Lemma 3.1.

Let $M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$, and assume that
$\eta<\mathrm{rch}_{\min}$, $\Delta\leq\mathrm{rch}_{\min}/4$ and
$\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}+\eta+\Delta\sin\theta\leq\Lambda$.
Then when running Manifold Propagation, the following inequality is
maintained:

$\max_{x\in\mathcal{Q}\cup\mathcal{O}}\mathrm{d}(x,M)\leq\eta.$

The second statement ensures that points in $\mathcal{Q}\cup\mathcal{O}$
remain far away from each other, so that they always form a packing with fixed
radius. This property, maintained by the proximity test at Line 7 of Manifold
Propagation, is the key ingredient for the termination of the algorithm and
its complexity.

######  Lemma 3.2.

Let $M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$, and assume that
$\eta<\mathrm{rch}_{\min}$, $\Delta\leq\mathrm{rch}_{\min}/4$ and
$\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}+\eta+\Delta\sin\theta\leq\Lambda$.
Then when running Manifold Propagation, the following inequality is
maintained:

$\min_{\begin{subarray}{c}x,y\in\mathcal{Q}\cup\mathcal{O}\\\ x\neq
y\end{subarray}}\left\|x-y\right\|\geq\delta-\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}-2\eta-\Delta\sin\theta.$

The third and last statement roughly asserts that if Manifold Propagation
terminates, then all the $\Delta$-neighborhoods of $M$ have been visited by
the output $\mathcal{O}$, i.e. that the greedy tangential exploration strategy
is somehow exhaustive at scale $\Delta$.

######  Lemma 3.3.

Let $M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$, and assume that
$\Delta\leq\mathrm{rch}_{\min}/24$, $\eta<\Delta/64$, and
$\max\left\\{{\sin\alpha,\sin\theta}\right\\}\leq 1/64$. Assume furthermore
that,
$\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}+\eta+\Delta\sin\theta\leq\Lambda$
and $\delta\leq 7\Delta/10$. If Manifold Propagation terminates, then its
output $\mathcal{O}$ satisfies

$\max_{p\in
M}\min_{x\in\mathcal{O}}\mathrm{d}_{M}(p,\pi_{M}(x)\bigr{)}\leq\Delta,$

where $\mathrm{d}_{M}(\cdot,\cdot)$ is the geodesic distance of $M$.

We are now in position to prove Theorem 3.1.

###### Proof of Theorem 3.1.

  1. 1.

By construction of Manifold Propagation, any visit of the _while_ loop (Lines
2–12) finishes with the addition of a point to $\mathcal{O}$. Since
$\mathcal{O}=\emptyset$ at initialization, the number of already performed
loops is maintained to satisfy $N_{\mathrm{loop}}=|\mathcal{O}|$ when the
algorithm runs. Furthermore, by Lemma 3.1 and Lemma 3.2, we have at all times

$\displaystyle\min_{\begin{subarray}{c}x,y\in\mathcal{O}\\\ x\neq
y\end{subarray}}$ $\displaystyle\left\|\pi_{M}(x)-\pi_{M}(y)\right\|$
$\displaystyle\geq\min_{\begin{subarray}{c}x,y\in\mathcal{Q}\cup\mathcal{O}\\\
x\neq y\end{subarray}}\left\|\pi_{M}(x)-\pi_{M}(y)\right\|$
$\displaystyle\geq\min_{\begin{subarray}{c}x,y\in\mathcal{Q}\cup\mathcal{O}\\\
x\neq
y\end{subarray}}\bigl{(}\left\|x-y\right\|-\left\|x-\pi_{M}(x)\right\|-\left\|y-\pi_{M}(y)\right\|\bigr{)}$
$\displaystyle\geq\left(\delta-\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}-2\eta-\Delta\sin\theta\right)-2\eta$
$\displaystyle\geq\frac{173}{960}\Delta\geq\frac{173}{960}\frac{10}{7}\delta>\frac{\delta}{4}>0.$

This shows that $\pi_{M}:\mathcal{O}\to\pi_{M}(\mathcal{O})$ is one-to-one,
and that the set $\pi_{M}(\mathcal{O})\subseteq M$ is a $(\delta/8)$-packing
of $M$. As a consequence, we have at all times

$\displaystyle
N_{\mathrm{loop}}=|\mathcal{O}|=|\pi_{M}(\mathcal{O})|\leq\mathrm{pk}_{M}(\delta/8)\leq\dfrac{\mathcal{H}^{d}(M)}{\omega_{d}(\delta/32)^{d}},$

where the last inequality follows from Lemma 2.3.

As $N_{\mathrm{loop}}<\infty$, this first item also shows that Manifold
Propagation terminates.

  1. 2.

This statement follows directly from Lemma 3.1.

  2. 3.

We have already shown that Manifold Propagation terminates. Therefore, Lemma
3.3 applies, and combining it with Item 2, we get

$\displaystyle\max_{p\in M}\mathrm{d}(p,\mathcal{O})$
$\displaystyle=\max_{p\in M}\min_{x\in\mathcal{O}}\left\|p-x\right\|$
$\displaystyle\leq\max_{p\in
M}\min_{x\in\mathcal{O}}\left\|p-\pi_{M}(x)\right\|+\max_{x\in\mathcal{O}}\left\|x-\pi_{M}(x)\right\|$
$\displaystyle\leq\max_{p\in
M}\min_{x\in\mathcal{O}}\mathrm{d}_{M}(p,\pi_{M}(x))+\eta$
$\displaystyle\leq\Delta+\eta.$

  3. 4.

Follows straightforwardly from Item 2 above, and the assumption that
$\left\|\pi_{T_{\pi_{M}(x)}M}-\pi_{\hat{T}(x)}\right\|_{\mathrm{op}}\leq\sin\theta$
for all $x\in\mathbb{R}^{n}$ such that $\mathrm{d}(x,M)\leq\eta$.

∎

##  4 Geometric Routines with Statistical Queries

Coming back to manifold estimation with SQ’s, we notice that by combining
together:

(Exploration)

the greedy point cloud construction of Theorem 3.1 using geometric routines
only,

(Reconstruction)

the point cloud-based reconstruction method of Theorem 2.1,

we have reduced the problem to constructing SQ algorithms emulating these
routines with a $\mathrm{STAT}(\tau)$ oracle. We now present constructions of
SQ algorithms for the projection routine $\hat{\pi}(\cdot)$ (Section 4.1), the
tangent space estimation routine $\hat{T}(\cdot)$ (Section 4.2), and the seed
point detection $\hat{x}_{0}$ (Section 4.3).

###  4.1 Projection

Given a point $x_{0}\in\mathbb{R}^{n}$ nearby $M=\mathrm{Supp}(D)$, we aim at
estimating its metric projection $\pi_{M}(x_{0})$ onto $M$ with statistical
queries to $\mathrm{STAT}(\tau)$. As mentioned earlier, the reasoning we adopt
is as follows:

  * •

For a properly chosen bandwidth $h>0$, the local conditional mean

$\displaystyle m_{D}(x_{0},h)$ $\displaystyle=\mathop{\mathbb{E}}_{x\sim
D}\left[x\left|\mathrm{B}(x_{0},h)\right.\right]=x_{0}+h\frac{\mathop{\mathbb{E}}_{x\sim
D}\left[\frac{(x-x_{0})}{h}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]}{D(\mathrm{B}(x_{0},h))}$

of $D$ around $x_{0}$ has small bias for estimating $\pi_{M}(x_{0})$ (Lemma
C.2).

  * •

As $m_{D}(x_{0},h)\in\mathbb{R}^{n}$ writes as a functional of the two means
$D(\mathrm{B}(x_{0},h))=\mathop{\mathbb{E}}_{x\sim
D}[\mathbbm{1}_{\left\|x-x_{0}\right\|\leq h}]\in\mathbb{R}$, and
$\mathop{\mathbb{E}}_{x\sim
D}\left[\frac{(x-x_{0})}{h}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]\in\mathbb{R}^{n}$, it can be estimated using $2n+1$ queries (Lemma
2.1).

The proof of these results are to be found in Appendix C. Combined together,
we then prove the correctness of the SQ projection estimation procedure
(Theorem 4.1) in Section C.2.

######  Theorem 4.1 (SQ Projection Estimation).

Let
$D\in\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
have support $M=\mathrm{Supp}(D)$. Assume that

$\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\leq
c^{d(d+1)}\Gamma^{d}\text{~{}and~{}}\Lambda\leq\frac{\mathrm{rch}_{\min}}{16},$

for some small enough absolute constant $c>0$, where
$\Gamma=\Gamma_{f_{\min},f_{\max},L}=\frac{f_{\min}}{f_{\max}+L\mathrm{rch}_{\min}}.$

Then for all $x_{0}\in\mathbb{R}^{n}$ such that
$\mathrm{d}(x_{0},M)\leq\Lambda$, there exists a SQ algorithm making $2n+1$
queries to $\mathrm{STAT}(\tau)$, that outputs a point
$\hat{\pi}(x_{0})\in\mathbb{R}^{n}$ estimating $\pi_{M}(x_{0})$ with precision

$\left\|\hat{\pi}(x_{0})-\pi_{M}(x_{0})\right\|\leq\eta=\frac{C^{d}}{\Gamma}\max\left\\{{\frac{\Lambda^{2}}{\mathrm{rch}_{\min}},\Gamma^{\frac{2}{d+1}}\mathrm{rch}_{\min}\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{\frac{2}{d+1}}}\right\\},$

where $C>0$ is an absolute constant.

###  4.2 Tangent Space

Given a point $x_{0}\in\mathbb{R}^{n}$ nearby $M=\mathrm{Supp}(D)$, we aim at
estimating the tangent space $T_{\pi_{M}(x_{0})}M$ with statistical queries to
$\mathrm{STAT}(\tau)$. The strategy we propose is based on local Principal
Components Analysis, combined with low-rank matrix recovery with SQ’s. This
local PCA approach is similar to that of [ACLZ17, AL18]. As described above,
the reasoning is as follows:

  * •

For a properly chosen bandwidth $h>0$, the local (rescaled) covariance matrix

$\Sigma_{D}(x_{0},h)=\mathop{\mathbb{E}}_{x\sim
D}\left[\frac{(x-x_{0}){(x-x_{0})}^{\top}}{h^{2}}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]\in\mathbb{R}^{n\times n}$

of $D$ around $x_{0}$ is nearly rank-$d$, and its first $d$ components span a
$d$-plane close to $T_{\pi_{M}(x_{0})}M\in\mathbb{G}^{n,d}$ (Lemma D.1).

  * •

Principal components being stable to perturbations (Lemma D.2), estimating
$\Sigma_{D}(x_{0},h)\in\mathbb{R}^{n\times n}$ is sufficient to estimate
$T_{\pi_{M}(x_{0})}M\in\mathbb{G}^{n,d}$.

  * •

Estimating $\Sigma_{D}(x_{0},h)\in\mathbb{R}^{n\times n}=\mathbb{R}^{n^{2}}$
using $O(n^{2})$ queries (Lemma 2.1) is too costly and would be redundant
since $\Sigma_{D}(x_{0},h)$ is nearly rank $d\ll n$. Instead, we use matrix
compression arguments (Theorem D.1) and an explicit construction of a matrix
sensing operator (Lemma D.3) to derive a general mean low-rank matrix SQ
algorithm (Lemma D.4). This result roughly asserts that a mean matrix
$\Sigma=\mathop{\mathbb{E}}_{x\sim D}[F(x)]\in\mathbb{R}^{n\times n}$ of a
bounded function $F:\mathbb{R}^{n}\to\mathbb{R}^{n\times n}$ that has nearly
rank $d$ can be estimated with precision $C\tau$ using
$nd\operatorname{polylog}(n)$ queries to $\mathrm{STAT}(\tau)$.

The proof of these results are to be found in Appendix D. All combined
together, we then prove the correctness of the SQ tangent space estimation
procedure (Theorem 4.2) in Section D.4.

######  Theorem 4.2 (SQ Tangent Space Estimation).

Let
$D\in\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
have support $M=\mathrm{Supp}(D)$. Assume that

$\frac{\tau}{\omega_{d}f_{\max}\mathrm{rch}_{\min}^{d}}\leq\left(\frac{1}{8\sqrt{d}}\right)^{d+1}\text{
and }\eta\leq\frac{\mathrm{rch}_{\min}}{64d}.$

Then for all $x_{0}\in\mathbb{R}^{n}$ such that $\mathrm{d}(x_{0},M)\leq\eta$,
there exists a deterministic SQ algorithm making at most $Cdn\log^{6}(n)$
queries to $\mathrm{STAT}(\tau)$, and that outputs a $d$-plane
$\hat{T}(x_{0})\in\mathbb{G}^{n,d}$ estimating $T_{\pi_{M}(x_{0})}M$ with
precision

$\displaystyle\left\|\pi_{\hat{T}(x_{0})}-\pi_{T_{\pi_{M}(x_{0})}M}\right\|_{\mathrm{op}}$
$\displaystyle\leq\sin\theta$
$\displaystyle=\tilde{C}^{d}\frac{f_{\max}}{f_{\min}}\max\left\\{{\sqrt{\frac{\eta}{\mathrm{rch}_{\min}}},\left(\frac{\tau}{\omega_{d}f_{\max}\mathrm{rch}_{\min}^{d}}\right)^{\frac{1}{d+1}}}\right\\},$

where $\tilde{C}>0$ is an absolute constant.

###  4.3 Seed Point

Given a ball of radius $R>0$ guaranteed to encompass
$M=\mathrm{Supp}(D)\subseteq\mathrm{B}(0,R)$, and a target precision $\eta>0$,
we aim at finding a point that is $\eta$-close to $M$ with statistical queries
to $\mathrm{STAT}(\tau)$. The strategy we propose is as follows:

  * •

Starting from $\mathrm{B}(0,R)$, we use a divide and conquer strategy (Theorem
E.1). The algorithm (SQ Ambient Binary Search) queries indicator functions of
an interactively chosen union of balls (i.e. the queried balls depend on the
previous answers of the oracle), stops when there is only one ball left and
outputs its center $\hat{x}_{0}^{raw}$. This method only uses estimates on the
local mass of balls for $D$ (Lemma B.1), and forgets about the differential
structure and $\mathcal{C}^{2}$-smoothness of $M$. Hence, although efficient,
it only obtains a precision $O(\max\left\\{{\eta,\tau^{1/d}}\right\\})$, that
can be much larger than the prescribed one
$O(\max\left\\{{\eta,\tau^{2/(d+1)}}\right\\})$.

  * •

Starting from $\hat{x}_{0}^{raw}$, we then refine this detected point by
iterating the SQ projection routine $\hat{\pi}(\cdot)$ (Theorem 4.1), which
does use extensively the $\mathcal{C}^{2}$-smoothness of $M$. As
$\hat{x}_{0}^{raw}$ is close to $M$, this procedure is guaranteed to enhance
precision quadratically at each step, and is hence satisfactory (i.e. has
precision $\eta$) after a logarithmic number of iterations.

The proof of these results are to be found in Appendix E.

######  Theorem 4.3 (SQ Point Detection).

Let
$D\in\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
have support $M=\mathrm{Supp}(D)\subseteq\mathrm{B}(0,R)$. Assume that

$\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\leq
c\Gamma^{d}\min\left\\{{c^{d},\left(n\log\left(R/(\Gamma\mathrm{rch}_{\min}\right)\right)^{-1/2}}\right\\}^{d},\text{
and }\eta\leq\frac{\mathrm{rch}_{\min}}{16}$

for some small enough $c>0$, where
$\Gamma=\Gamma_{f_{\min},f_{\max},L}=\frac{f_{\min}}{f_{\max}+L\mathrm{rch}_{\min}},$

Then there exists a deterministic SQ algorithm making at most
$6n\log(6R/\eta)$ queries to $\mathrm{STAT}(\tau)$, and that outputs a point
$\hat{x}_{0}\in\mathrm{B}(0,R)$ such that

$\mathrm{d}(\hat{x}_{0},M)\leq\max\left\\{{\eta,C^{d}\Gamma^{\frac{2}{d+1}-1}\mathrm{rch}_{\min}\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{\frac{2}{d+1}}}\right\\},$

where $C>0$ is the absolute constant of Theorem 4.1.

##  5 Manifold Estimation with Statistical Queries

We are now in position to state the main results of this work, namely bounds
on the statistical query complexity of manifold estimation in
$\mathrm{STAT}(\tau)$. We split the results into the two studied models
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
and
$\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$.
For each model, we get an upper bound by combining the results of Sections 3
and 4. It is followed by an informational and a computational lower bound,
coming from the general lower bound techniques of Appendix G and the
constructions of Appendix H.

###  5.1 Fixed Point Model

In
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$,
the origin $0\in\mathbb{R}^{n}$ is known to belong to $M$. The SQ algorithm we
propose consists in running Manifold Propagation with seed point
$\hat{x}_{0}=0$ and the SQ projection and tangent space routines of Theorems
4.1 and 4.2. This leads to the following upper bound. Let us mention that one
could easily extend this result and relax the assumption that $0\in M$ to
$\mathrm{d}(0,M)$ being small enough.

######  Theorem 5.1.

Let
$D\in\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
have support $M=\mathrm{Supp}(D)$. Writing
$\Gamma=\Gamma_{f_{\min},f_{\max},L}=\frac{f_{\min}}{f_{\max}+L\mathrm{rch}_{\min}},$
let us assume that

$\frac{\tau}{f_{\min}\mathrm{rch}_{\min}^{d}}\leq
c^{d}\Gamma^{7(d+1)/2}\text{~{}and~{}}\varepsilon\leq\tilde{c}^{d}\Gamma^{3}\mathrm{rch}_{\min},$

for some small enough absolute constants $c,\tilde{c}>0$. Then there exists a
deterministic SQ algorithm making at most

$q\leq
n\log^{6}n\frac{C_{d}}{f_{\min}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{\varepsilon}\right)^{d/2}$

queries to $\mathrm{STAT}(\tau)$, and that outputs a finite triangulation
$\hat{M}\subseteq\mathbb{R}^{n}$ that has the same topology as $M$, and such
that

$\displaystyle\mathrm{d_{H}}(M,\hat{M})\leq\max\left\\{{\varepsilon,\frac{\tilde{C}^{d}}{\Gamma^{3}}\mathrm{rch}_{\min}\left(\frac{\tau}{f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/(d+1)}}\right\\},$

where $C_{d}>0$ depends on $d$ and $\tilde{C}>0$ is an absolute constant.

The algorithm of Theorem 5.1 has a statistical query complexity comparable to
the optimal sample complexity $s=O(\varepsilon^{-2/d}\log(1/\varepsilon))$
over the model
$\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
[GPPVW12a, KZ15, AL18], and can provably achieve precision
$O(\tau^{2/(d+1)})$. Furthermore, the assumptions made as well as the final
precision are completely insensitive to $n$. The ambient dimension $n$ only
appears as a quasi-linear factor in the query complexity. This contrasts with
the sample complexity which does not depends on $n$. However, notice that a
single sample nearby $M\subseteq\mathbb{R}^{n}$ consists of $n$ coordinates,
while statistical queries are forced to be real-valued (one dimensional)
pieces of information, which explains this apparent discrepancy.

Discussing its optimality, one may first wonder if the assumption made on
$\tau$ is necessary, and whether the precision barrier of order
$O(\tau^{2/(d+1)})$ is improvable in $\mathrm{STAT}(\tau)$. The following
statement answers to these questions, regardless the statistical query
complexity.

######  Theorem 5.2.

Let $\alpha<1/2$ be a probability of error. Assume that $f_{\min}\leq
f_{\max}/4$ and

$2^{d+1}\sigma_{d}f_{\min}\mathrm{rch}_{\min}^{d}\leq 1.$

Then no randomized SQ algorithm can estimate $M=\mathrm{Supp}(D)$ over
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
with precision

$\varepsilon<\frac{\mathrm{rch}_{\min}}{2^{21}}\min\left\\{{\frac{1}{2^{20}d^{2}},\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/d}}\right\\}$

and probability $1-\alpha$, no matter its number of queries.

This result justifies why the quantity
$\tau/(\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d})$ is required to be small
enough in Theorem 5.1: this actually is necessary so as to reach a precision
of order at least $O(\mathrm{rch}_{\min})$. Second, this informational lower
bound shows that the learner cannot hope to achieve precision better than

$\varepsilon=\Omega\bigl{(}\mathrm{rch}_{\min}\left(\tau/(\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d})\right)^{2/d}\bigr{)},$

even with the most costly randomized SQ algorithms. In fact, the precision
$O(\tau^{2/(d+1)})$ of Theorem 5.1 is nearly optimal. Here, the assumptions
made on $f_{\min},f_{\max}$ and $\mathrm{rch}_{\min}$ are also necessary to
ensure non-degeneracy of the model
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$,
as mentioned in Section 2.2.3. Beyond the above informational considerations,
we turn to the computational one, i.e. to the minimal number of queries to
$\mathrm{STAT}(\tau)$ that a learner must make to achieve precision
$\varepsilon$.

######  Theorem 5.3.

Let $\alpha<1$ be a probability of error, and
$\varepsilon\leq\mathrm{rch}_{\min}/(2^{34}d^{2})$. Assume that $f_{\min}\leq
f_{\max}/4$ and

$2^{d+1}\sigma_{d}f_{\min}\mathrm{rch}_{\min}^{d}\leq 1.$

Then any randomized SQ algorithm estimating $M=\mathrm{Supp}(D)$ over
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
with precision $\varepsilon$ and with probability of success at least
$1-\alpha$ must make at least

$q\geq\left(n\frac{1}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{2^{21}\varepsilon}\right)^{d/2}+\log(1-\alpha)\right)\big{/}\log(1+1/\tau)$

queries to $\mathrm{STAT}(\tau)$.

For deterministic SQ algorithms ($\alpha=0$), the statistical query complexity
of the algorithm of Theorem 5.1 is therefore optimal up to
$\operatorname{polylog}(n,1/\tau)$ factors. It even performs nearly optimally
within all the possible randomized algorithms, provided that their probability
of error $\alpha$ is not too close to $1$, which would allow for a naive
random pick among an $\varepsilon$-covering of the space
$\bigl{(}\left\\{{0}\right\\}\sqcup\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}},\mathrm{d_{H}}\bigr{)}$
(with zero query to $\mathrm{STAT}(\tau)$) to be a valid algorithm.

###  5.2 Bounding Ball Model

In
$\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$,
no distinguished point of $\mathbb{R}^{n}$ is known to belong to $M$, but a
location area $\mathrm{B}(0,R)$ containing $M$ is available to the learner.
Hence, the strategy of the previous section cannot initialize directly.
However, Theorem 4.3 allows to find a seed point $\hat{x}_{0}$ close to $M$
using a limited number of queries to $\mathrm{STAT}(\tau)$. Starting from
$\hat{x}_{0}$ and, as above, running Manifold Propagation with the SQ
projection and tangent space routines of Theorems 4.1 and 4.2 leads to the
following upper bound.

######  Theorem 5.4.

Let
$D\in\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
have support $M=\mathrm{Supp}(D)$. Writing
$\Gamma=\Gamma_{f_{\min},f_{\max},L}=\frac{f_{\min}}{f_{\max}+L\mathrm{rch}_{\min}},$
let us assume that

$\frac{\tau}{f_{\min}\mathrm{rch}_{\min}^{d}}\leq\min\left\\{{c^{d}\Gamma^{7(d+1)/2},\Gamma^{d}\left(n\log\left(R/(\Gamma\mathrm{rch}_{\min}\right)\right)^{-d/2}}\right\\}$

and

$\varepsilon\leq\tilde{c}^{d}\Gamma^{3}\mathrm{rch}_{\min},$

for some small enough absolute constants $c,\tilde{c}>0$. Then there exists a
deterministic SQ algorithm making at most

$q\leq
Cn\log\left(\frac{R}{\varepsilon}\right)+n\log^{6}n\frac{C_{d}}{f_{\min}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{\varepsilon}\right)^{d/2}$

queries to $\mathrm{STAT}(\tau)$, and that outputs a finite triangulation
$\hat{M}\subseteq\mathbb{R}^{n}$ that has the same topology as $M$, and such
that

$\displaystyle\mathrm{d_{H}}(M,\hat{M})\leq\max\left\\{{\varepsilon,\frac{\tilde{C}^{d}}{\Gamma^{3}}\mathrm{rch}_{\min}\left(\frac{\tau}{f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/(d+1)}}\right\\},$

where $C_{d}>0$ depends on $d$ and $\tilde{C}>0$ is an absolute constant.

Compared to Theorem 5.1, observe the extra $O(n\log(R/\varepsilon))$ queries
made in Theorem 5.4, which come from the seed point search performed at
initialization. Passed this difference, the two results are tightly similar.
In the same fashion as above, we first discuss the necessity of the
assumptions made on $\tau$ and the precision threshold $O(\tau^{2/(d+1)})$.

######  Theorem 5.5.

Let $\alpha<1/2$ be a probability of error. Assume that
$\mathrm{rch}_{\min}\leq R/144$ and $f_{\min}\leq f_{\max}/96$, and

$\min_{1\leq k\leq
n}\left(\frac{192\mathrm{rch}_{\min}\sqrt{k}}{R}\right)^{k}\leq 36\times
8^{d}\sigma_{d-1}f_{\min}\mathrm{rch}_{\min}^{d}\leq 1.$

Then no randomized SQ algorithm can estimate $M=\mathrm{Supp}(D)$ over
$\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
with precision

$\varepsilon<\frac{\mathrm{rch}_{\min}}{2^{31}}\min\left\\{{\frac{1}{2^{10}d^{2}},\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/d}}\right\\}$

and probability $1-\alpha$, no matter its number of queries.

As above, we emphasize the fact that the assumptions made on $f_{\min}$,
$f_{\max}$, $\mathrm{rch}_{\min}$ and $R$ are necessary to guarantee the non-
degeneracy of the model
$\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$,
and hence a non-trivial estimation problem (see Section 2.2.3). As for the
fixed point model, we hence see that the assumptions made on $\tau$ and the
precision $\varepsilon$ cannot be omitted. Let us though notice the slightly
more stringent assumption made on $\tau$ that depends on $n$ in the upper
bound (Theorem 5.4) but not in the lower bound (Theorem 5.5). This dependency
originates from the seed point detection method that we developed (Theorem
4.3) and we do not claim it to be optimal. As about the computational lower
bound for this model, we state the following result.

######  Theorem 5.6.

Let $\alpha<1$ be a probability of error, and
$\varepsilon\leq\mathrm{rch}_{\min}/(2^{34}d^{2})$. Assume that
$\mathrm{rch}_{\min}\leq R/144$, $f_{\min}\leq f_{\max}/96$, and

$\min_{1\leq k\leq
n}\left(\frac{192\mathrm{rch}_{\min}\sqrt{k}}{R}\right)^{k}\leq 36\times
8^{d}\sigma_{d-1}f_{\min}\mathrm{rch}_{\min}^{d}\leq 1.$

Then any randomized SQ algorithm estimating $M=\mathrm{Supp}(D)$ over
$\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
with precision $\varepsilon$ and with probability of success at least
$1-\alpha$ must make at least

$q\geq\dfrac{n\max\left\\{{\log\left(\frac{R}{4\varepsilon}\right),\frac{1}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{2^{31}\varepsilon}\right)^{d/2}}\right\\}+\log(1-\alpha)}{\log(1+1/\tau)}$

queries to $\mathrm{STAT}(\tau)$.

As a result, the extra $O(n\log(R/\varepsilon))$ queries of Theorem 5.4 are
necessary in the SQ framework. This contrasts sharply with the sample model,
where no prior location information is necessary appears in the sample
complexity [GPPVW12a, KZ15, AL18]. Roughly speaking, this is explained by the
fact that a single sample (the first, say) does provide location information
for free, while in the SQ framework, the learner is left with the whole ball
$\mathrm{B}(0,R)$ to explore at initialization. However, as mentioned above,
note that the term $\Omega(n\log(R/\varepsilon))$ attributable to this
initialization step would only dominate in the regime where $R$ is
exponentially bigger than $\mathrm{rch}_{\min}$.

##  6 Further Directions

As mentioned above, a byproduct of these results is that manifold estimation
is possible in a locally private way. However, the transformation used to pass
from statistical query learning to locally private learning has a polynomial
blowup [KLN+11]. Hence, the derived locally private upper bound may not be
optimal, so that a close study of the private framework directly is still
necessary. Coming back to SQ’s, the derived bounds on the best achievable
precision $\varepsilon$ in $\mathrm{STAT}(\tau)$ do not match, as they are
respectively of the form
$\varepsilon=O\left(\mathrm{rch}_{\min}\left(\frac{\tau}{f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/(d+1)}\right)$
for the upper bounds, and
$\varepsilon=\Omega\left(\mathrm{rch}_{\min}\left(\frac{\tau}{f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/d}\right)$
for the lower bounds, so that this gap remains to be breached.

The case of smoother $\mathcal{C}^{k}$ manifolds ($k>2$) would be of
fundamental interest, as their estimation is at the basis of plugin methods of
higher order. This includes, for instance, density estimation [BHHS22], or
distribution estimation in Wasserstein distance [Div21b]. For $k>2$, local
linear approximations are not optimal [AL19], and local polynomials of higher
order — that were shown to be optimal in the sample framework — might adapt to
statistical queries.

On a more technical side, note that we have assumed throughout that the
density $f$ is $L$-Lipschitz and satisfies $f_{\min}\leq f\leq f_{\max}$,
although the lower bounds do not let $L$ and $f_{\max}$ appear, but only
$f_{\min}$. While the Lipschitz assumption could be dropped for the tangent
space routine, it actually is crucial in the proposed projection routine to
bound the bias term. Hence, it remains unclear to us how to design an
efficient projection routine without this assumption, as well as how to carry
the whole analysis with $f_{\max}=\infty$.

## Acknowledgements

This work was partially funded by CNRS PEPS JCJC. The authors would like to
thank warmly the Department of Mathematics of UC San Diego, the Steklov
Institute, and all the members of the Laboratoire de Probabilités,
Statistiques et Modélisation for their support and insightful comments.

##  Appendix A Proofs of the Properties of Manifold Propagation

When running Manifold Propagation, linear approximations of the manifold are
done via its (approximate) tangent spaces. A key point in the proof of its
correctness is the (quantitative) validity of this approximation, which is
ensured by the reach assumption $\mathrm{rch}_{M}\geq\mathrm{rch}_{\min}$,
which bounds curvature. Recall from (1) that
$M^{r}=\\{z\in\mathbb{R}^{n},\mathrm{d}(z,M)\leq r\\}$ stands for the
$r$-offset of $M$.

######  Lemma A.1.

Let $M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$, and $x\in M^{\eta}$
with $\eta<\mathrm{rch}_{\min}$. Take $T\in\mathbb{G}^{n,d}$ such that
$\left\|\pi_{T_{\pi_{M}(x)}M}-\pi_{T}\right\|_{\mathrm{op}}\leq\sin\theta$.
Then for all $\Delta\leq\mathrm{rch}_{\min}/4$, and all unit vector $v\in T$,

$\mathrm{d}\bigl{(}x+\Delta
v,M\bigr{)}\leq\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}+\eta+\Delta\sin\theta.$

###### Proof of Lemma A.1.

By assumption on $T$, there exists a unit vector $v^{\prime}\in
T_{\pi_{M}(x)}M$ such that $\left\|v-v^{\prime}\right\|\leq\sin\theta$. Hence,
since $\mathrm{d}(\cdot,M)$ is $1$-Lipschitz, we have

$\displaystyle\mathrm{d}\bigl{(}x+\Delta v,M\bigr{)}$
$\displaystyle\leq\mathrm{d}\bigl{(}x+\Delta
v^{\prime},M\bigr{)}+\Delta\sin\theta$
$\displaystyle\leq\mathrm{d}\bigl{(}\pi_{M}(x)+\Delta
v^{\prime},M\bigr{)}+\eta+\Delta\sin\theta$
$\displaystyle\leq\left\|\pi_{M}(x)+\Delta
v^{\prime}-\exp_{\pi_{M}(x)}^{M}(\Delta
v^{\prime})\right\|+\eta+\Delta\sin\theta$
$\displaystyle\leq\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}+\eta+\Delta\sin\theta,$

where the last inequality follows from [AL19, Lemma 1]. ∎

We are now in position to prove Lemma 3.1, that guarantees that Manifold
Propagation builds point clouds that do not deviate from $M$.

###### Proof of Lemma 3.1.

The points added to $\mathcal{O}$ are all first added to $\mathcal{Q}$:
therefore, it is sufficient to check that all the points $x$ added to
$\mathcal{Q}$ satisfy $\mathrm{d}(x,M)\leq\eta$. To see this, proceed by
induction:

  * •

As $\mathcal{Q}$ is initialized to $\left\\{{\hat{x}_{0}}\right\\}$ with
$\mathrm{d}(\hat{x}_{0},M)\leq\eta$, the inequality holds true at Line 1,
before the first loop.

  * •

If $\bar{x}\neq\hat{x}_{0}$ was added to $\mathcal{Q}$, it can be written as
$\bar{x}=\hat{\pi}(x_{0}+\Delta v_{i})$, for some point $x_{0}\in\mathcal{Q}$
and a unit vector $v_{i}\in\hat{T}(x_{0})$. By induction, we have
$\mathrm{d}(x_{0},M)\leq\eta$. But since $\hat{T}(\cdot)$ is assumed to have
precision $\sin\theta$ over $M^{\eta}$, we hence obtain that
$\left\|\pi_{T_{\pi_{M}(x_{0})}M}-\pi_{\hat{T}(x_{0})}\right\|_{\mathrm{op}}\leq\sin\theta$.
As a result, from Lemma A.1,

$\displaystyle\mathrm{d}(x_{0}+\Delta
v_{i},M)\leq\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}+\eta+\Delta\sin\theta\leq\Lambda,$

and therefore

$\mathrm{d}(\bar{x},M)\leq\left\|\bar{x}-\pi_{M}(x_{0}+\Delta
v_{i})\right\|=\left\|\hat{\pi}(x_{0}+\Delta v_{i})-\pi_{M}(x_{0}+\Delta
v_{i})\right\|\leq\eta$

since $\hat{\pi}(\cdot)$ is assumed to have precision $\eta$ over
$M^{\Lambda}$.

This concludes the induction and hence the proof. ∎

Next we show Lemma 3.2, asserting that the radius of sparsity of the point
clouds built by Manifold Propagation is maintained at all times.

###### Proof of Lemma 3.2.

At initialization of Manifold Propagation,
$\mathcal{Q}\cup\mathcal{O}=\left\\{{\hat{x}_{0}}\right\\}$, so that the
inequality trivially holds at Line 1. Then, if a point $\bar{x}$ is added to
$\mathcal{Q}$ at Line 8, it means that it can be written as
$\bar{x}=\hat{\pi}(x_{0}+\Delta v_{i_{0}})$, with $\mathrm{d}(x_{0}+\Delta
v_{i_{0}},\mathcal{Q}\cup\mathcal{O})\geq\delta$. Consequently, by induction,
we have

$\displaystyle\min_{\begin{subarray}{c}x,y\in\mathcal{Q}\cup\mathcal{O}\cup\left\\{{\bar{x}}\right\\}\\\
x\neq y\end{subarray}}\left\|x-y\right\|$
$\displaystyle=\min\Bigl{\\{}\min_{\begin{subarray}{c}x,y\in\mathcal{Q}\cup\mathcal{O}\\\
x\neq
y\end{subarray}}\left\|x-y\right\|,\mathrm{d}\left(\bar{x},\mathcal{Q}\cup\mathcal{O}\right)\Bigr{\\}}$
$\displaystyle\geq\min\Bigl{\\{}\delta-\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}-2\eta-\Delta\sin\theta,$
$\displaystyle\hskip 40.00006pt\mathrm{d}(x_{0}+\Delta
v_{i_{0}},\mathcal{Q}\cup\mathcal{O})-\left\|(x_{0}+\Delta
v_{i_{0}})-\bar{x}\right\|\Bigr{\\}}$
$\displaystyle\geq\min\left\\{\delta-\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}-2\eta-\Delta\sin\theta,\delta-\left\|(x_{0}+\Delta
v_{i_{0}})-\bar{x}\right\|\right\\}.$

In addition, Lemma A.1 and Lemma 3.1 combined yield

$\displaystyle\left\|(x_{0}+\Delta v_{i_{0}})-\bar{x}\right\|$
$\displaystyle=\left\|(x_{0}+\Delta v_{i_{0}})-\hat{\pi}(x_{0}+\Delta
v_{i_{0}})\right\|$ $\displaystyle\leq\left\|\hat{\pi}(x_{0}+\Delta
v_{i_{0}})-\pi_{M}(x_{0}+\Delta v_{i_{0}})\right\|$
$\displaystyle~{}~{}~{}+\left\|\pi_{M}(x_{0}+\Delta v_{i_{0}})-(x_{0}+\Delta
v_{i_{0}})\right\|$
$\displaystyle\leq\eta+\left(\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}+\eta+\Delta\sin\theta\right).$

As a result, after the update
$\mathcal{Q}\leftarrow\mathcal{Q}\cup\left\\{{\bar{x}}\right\\}$, the
announced inequality still holds. Finally, we notice that Line 11, which swaps
a point from $\mathcal{Q}$ to $\mathcal{O}$, leaves
$\mathcal{Q}\cup\mathcal{O}$ unchanged. By induction, this concludes the
proof. ∎

Finally we prove Lemma 3.3, that states that if Manifold Propagation
terminates, it outputs a point cloud dense enough nearby $M$.

###### Proof of Lemma 3.3.

Assume for contradiction that there exists $p_{0}\in M$ such that for all
$x\in\mathcal{O}$, $\mathrm{d}_{M}\bigl{(}p_{0},\pi_{M}(x)\bigr{)}>\Delta$.
Let $x_{0}\in\mathcal{O}$ (which is not empty since
$\hat{x}_{0}\in\mathcal{O}$) be such that

$\mathrm{d}_{M}\bigl{(}p_{0},\pi_{M}(x_{0})\bigr{)}=\min_{x\in\mathcal{O}}\mathrm{d}_{M}(p_{0},\pi_{M}(x)\bigr{)}:=r_{0}>\Delta,$

and write $y_{0}:=\pi_{M}(x_{0})$. Let $\gamma:=\gamma_{y_{0}\to
p_{0}}:[0,r_{0}]\to M$ denote an arc-length parametrized geodesic joining
$y_{0}$ and $p_{0}$. Finally, set $q_{0}:=\gamma(\Delta)\in M$ and
$v_{0}:=\gamma^{\prime}(0)\in T_{y_{0}}M$.

Consider the sets $\mathcal{Q}$ and $\mathcal{O}$ of Manifold Propagation
right after $x_{0}$ was removed from $\mathcal{Q}$ and added to $\mathcal{O}$
(Line 11). By construction, all the elements $v_{1},\dots,v_{k}$ of a maximal
$(\sin\alpha)$-packing of $\mathcal{S}^{d-1}_{\hat{T}(x_{0})}$ were tested to
enter $\mathcal{Q}$ (Loop from Line 6 to Line 10). Because the packing is
maximal, it is also a $(2\sin\alpha)$-covering of
$\mathcal{S}^{d-1}_{\hat{T}(x_{0})}$ (see the proof of Proposition B.2). As a
result, by assumption on the precision of $\hat{T}(x_{0})$, there exists
$v_{i_{0}}$ in this packing such that $\left\|v_{0}-v_{i_{0}}\right\|\leq
2\sin\alpha+\sin\theta$.

As $\gamma$ is a distance-minimizing path on $M$ from $y_{0}$ to $p_{0}$, so
it is along its two sub-paths with endpoint $q_{0}$, as otherwise, one could
build a strictly shorter path between $y_{0}$ and $p_{0}$. In particular,
since $\Delta<r_{0}=\mathrm{d}_{M}(y_{0},p_{0})$, we have
$\mathrm{d}_{M}(y_{0},q_{0})=\mathrm{d}_{M}(y_{0},\gamma(\Delta))=\Delta$ and
$\mathrm{d}_{M}(p_{0},q_{0})=\mathrm{d}_{M}(p_{0},\gamma(\Delta))=r_{0}-\Delta$.
As a result,

$\displaystyle\mathrm{d}_{M}\left(p_{0},\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right)$
$\displaystyle\leq\mathrm{d}_{M}\left(p_{0},q_{0}\right)+\mathrm{d}_{M}\left(q_{0},\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right)$
$\displaystyle=r_{0}-\Delta+\mathrm{d}_{M}\left(q_{0},\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right).$ (2)

But from Lemma 2.2, we get

$\displaystyle\mathrm{d}_{M}\left(q_{0},\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right)$ $\displaystyle\leq
2\mathrm{rch}_{\min}\arcsin{\left(\frac{\left\|q_{0}-\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right\|}{2\mathrm{rch}_{\min}}\right)}$
$\displaystyle\leq\frac{\left\|q_{0}-\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right\|}{\sqrt{1-\left(\frac{\left\|q_{0}-\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right\|}{2\mathrm{rch}_{\min}}\right)^{2}}},$ (3)

and furthermore,

$\displaystyle\left\|q_{0}-\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right\|$ $\displaystyle\leq\left\|q_{0}-(y_{0}+\Delta
v_{0})\right\|+\left\|(y_{0}+\Delta v_{0})-(x_{0}+\Delta v_{i_{0}})\right\|$
$\displaystyle~{}~{}~{}+\left\|(x_{0}+\Delta
v_{i_{0}})-\hat{\pi}\left(x_{0}+\Delta v_{i_{0}}\right)\right\|$
$\displaystyle~{}~{}~{}+\left\|\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)-\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right\|.$ (4)

We now bound the right hand side of Appendix A term by term. The first term is
bounded by

$\displaystyle\left\|q_{0}-(y_{0}+\Delta v_{0})\right\|$
$\displaystyle=\left\|\gamma(\Delta)-(\gamma(0)+\Delta\gamma^{\prime}(0))\right\|\leq\frac{\Delta^{2}}{2\mathrm{rch}_{\min}},$

where the inequality follows from a Taylor expansion and Lemma 2.2. For the
second term, write

$\displaystyle\left\|(y_{0}+\Delta v_{0})-(x_{0}+\Delta v_{i_{0}})\right\|$
$\displaystyle\leq\left\|y_{0}-x_{0}\right\|+\Delta\left\|v_{0}-v_{i_{0}}\right\|\leq\eta+\Delta(2\sin\alpha+\sin\theta).$

For the third term, we combine Lemma A.1 and Lemma 3.1 to get

$\displaystyle\left\|(x_{0}+\Delta v_{i_{0}})-\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right\|$ $\displaystyle\leq\mathrm{d}\left(x_{0}+\Delta
v_{i_{0}},M\right)$ $\displaystyle~{}~{}~{}+\left\|\pi_{M}(x_{0}+\Delta
v_{i_{0}})-\hat{\pi}\left(x_{0}+\Delta v_{i_{0}}\right)\right\|$
$\displaystyle\leq\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}+2\eta+\Delta\sin\theta,$

and for the fourth term, applying again Lemma A.1 and Lemma 3.1 yields

$\displaystyle\left\|\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)-\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right\|$
$\displaystyle=\mathrm{d}\bigl{(}\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right),M\bigr{)}$ $\displaystyle\leq\eta.$

Plugging these four bounds in Appendix A, we have shown that

$\displaystyle\left\|q_{0}-\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right\|$
$\displaystyle\leq\frac{9\Delta^{2}}{8\mathrm{rch}_{\min}}+4\eta+2\Delta(\sin\alpha+\sin\theta).$
(5)

Combining Equation 5, Appendix A, and the assumptions on the parameters
$\Delta,\eta,\theta,\alpha$ hence yields

$\displaystyle\mathrm{d}_{M}\left(y_{0},\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right)\leq
2\left\|q_{0}-\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right\|\leq\Delta/2,$

so that Appendix A gives

$\displaystyle\mathrm{d}_{M}\left(p_{0},\pi_{M}\left(\hat{\pi}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)\right)$ $\displaystyle\leq r_{0}-\Delta+\Delta/2$
$\displaystyle<r_{0}$
$\displaystyle=\mathrm{d}_{M}(p_{0},\pi_{M}(x_{0}))=\min_{x\in\mathcal{O}}\mathrm{d}_{M}(p_{0},\pi_{M}(x)\bigr{)}.$

In particular, $\hat{\pi}\left(x_{0}+\Delta v_{i_{0}}\right)$ was not added to
$\mathcal{Q}$ in the Loop of Lines 6 to 10 investigating the neighbors of
$x_{0}$ (i.e. when $x_{0}$ was picked Line 3). Since
$\mathcal{Q}\cup\mathcal{O}$ is an increasing sequence of sets as Manifold
Propagation runs and that $\mathcal{Q}=\emptyset$ when it terminates, this
means that there exists $x_{1}$ in the final output $\mathcal{O}$ such that
$\left\|x_{0}+\Delta v_{i_{0}}-x_{1}\right\|\leq\delta$.

The existence of this particular point $x_{1}$ in $\mathcal{O}$ which is
$\delta$-close to $x_{0}+\Delta v_{i_{0}}$ will lead us to a contradiction: we
will show that $\pi_{M}(x_{1})$ will be closer to $p_{0}$ than
$\pi_{M}(x_{0})$ is in geodesic distance. To get there, we first notice that
any such $x_{1}\in\mathcal{O}$ would satisfy $\mathrm{d}(x_{1},M)\leq\eta$
from Lemma 3.1, so that

$\displaystyle\left\|\pi_{M}\left(x_{0}+\Delta
v_{i_{0}}\right)-\pi_{M}(x_{1})\right\|$
$\displaystyle\leq\left\|\pi_{M}\left(x_{0}+\Delta
v_{i_{0}}\right)-\left(x_{0}+\Delta v_{i_{0}}\right)\right\|$
$\displaystyle~{}~{}~{}+\left\|\left(x_{0}+\Delta
v_{i_{0}}\right)-x_{1}\right\|+\left\|x_{1}-\pi_{M}(x_{1})\right\|$
$\displaystyle\leq\delta+\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}+2\eta+\Delta\sin\theta$
$\displaystyle\leq\delta+\frac{17}{192}\Delta\leq\frac{25}{192}\mathrm{rch}_{\min},$

where the last-but-one line follows from Lemma A.1, and the last one from the
assumptions on the parameters $\Delta,\eta,\theta$ and $\delta$. As a result,
from Lemma 2.2,

$\displaystyle\mathrm{d}_{M}(\pi_{M}\left(x_{0}+\Delta
v_{i_{0}}\right),\pi_{M}(x_{1}))$
$\displaystyle\leq\frac{\left\|\pi_{M}\left(x_{0}+\Delta
v_{i_{0}}\right)-\pi_{M}(x_{1})\right\|}{\sqrt{1-\left(\frac{25}{2\times
192}\right)^{2}}}$
$\displaystyle\leq\left(1+\frac{3}{10000}\right)\left(\delta+\frac{17}{192}\Delta\right).$
(6)

Furthermore, using a similar decomposition as for Equation 5, we have

$\displaystyle\left\|q_{0}-\pi_{M}\left(x_{0}+\Delta v_{i_{0}}\right)\right\|$
$\displaystyle\leq\left\|q_{0}-\left(y_{0}+\Delta
v_{0}\right)\right\|+\left\|\left(y_{0}+\Delta v_{0}\right)-\left(x_{0}+\Delta
v_{i_{0}}\right)\right\|$ $\displaystyle~{}~{}~{}+\left\|\left(x_{0}+\Delta
v_{i_{0}}\right)-\pi_{M}\left(x_{0}+\Delta v_{i_{0}}\right)\right\|$
$\displaystyle\leq\frac{\Delta^{2}}{2\mathrm{rch}_{\min}}+\left(\eta+\Delta\left(2\sin\alpha+\sin\theta\right)\right)$
$\displaystyle~{}~{}~{}+\left(\frac{5}{8}\frac{\Delta^{2}}{\mathrm{rch}_{\min}}+\eta+\Delta\sin\theta\right)$
$\displaystyle\leq\frac{11}{64}\Delta\leq\frac{11}{1536}\mathrm{rch}_{\min},$

from which we finally get

$\displaystyle\mathrm{d}_{M}\left(q_{0},\pi_{M}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)$
$\displaystyle\leq\frac{\left\|q_{0}-\pi_{M}\left(x_{0}+\Delta
v_{i_{0}}\right)\right\|}{\sqrt{1-\left(\frac{11}{2\times 1536}\right)^{2}}}$
$\displaystyle\leq\frac{3}{16}\Delta.$ (7)

This takes us to the desired contradiction, since:

  * •

on one hand, $x_{1}\in\mathcal{O}$ forces to have

$\displaystyle\mathrm{d}_{M}(p_{0},\pi_{M}(x_{1}))\geq
r_{0}=\min_{x\in\mathcal{O}}\mathrm{d}_{M}(p_{0},\pi_{M}(x)\bigr{)}=\mathrm{d}_{M}(p_{0},\pi_{M}(x_{0}));$

  * •

on the other hand, Appendix A and Appendix A combined yield

$\displaystyle\mathrm{d}_{M}(p_{0},\pi_{M}(x_{1}))$
$\displaystyle\leq\mathrm{d}_{M}(p_{0},q_{0})+\mathrm{d}_{M}\left(q_{0},\pi_{M}\left(x_{0}+\Delta
v_{i_{0}}\right)\right)$
$\displaystyle~{}~{}~{}+\mathrm{d}_{M}(\pi_{M}\left(x_{0}+\Delta
v_{i_{0}}\right),\pi_{M}(x_{1}))$ $\displaystyle\leq
r_{0}-\Delta+\frac{3}{16}\Delta+\left(1+\frac{3}{10000}\right)\left(\delta+\frac{17}{192}\Delta\right)$
$\displaystyle<r_{0},$

where we used that $\delta\leq 7\Delta/10$.

As a result, we have proved that

$\max_{p\in
M}\min_{x\in\mathcal{O}}\mathrm{d}_{M}(p,\pi_{M}(x)\bigr{)}\leq\Delta,$

which is the announced result. ∎

##  Appendix B Preliminary Geometric Results

###  B.1 Local Mass of Balls Estimates

To prove the properties of the statistical query routines, we will need the
following two geometric results about manifolds with bounded reach. In what
follows, $t_{+}:=\max\\{0,t\\}$ stands for the positive part of
$t\in\mathbb{R}$.

######  Proposition B.1 ([AL18, Proposition 8.2]).

Let $M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$, $x\in\mathbb{R}^{n}$
such that $\mathrm{d}(x,M)\leq\mathrm{rch}_{\min}/8$, and
$h\leq\mathrm{rch}_{\min}/8$. Then,

$\displaystyle\mathrm{B}\left(\pi_{M}(x),r_{h}^{-}\right)\cap
M\subseteq\mathrm{B}(x,h)\cap
M\subseteq\mathrm{B}\left(\pi_{M}(x),r_{h}^{+}\right)\cap M,$

where $r_{h}=(h^{2}-\mathrm{d}(x,M)^{2})_{+}^{1/2}$,
$(r_{h}^{-})^{2}=\left(1-\frac{\mathrm{d}(x,M)}{\mathrm{rch}_{\min}}\right)r_{h}^{2}$,
and
$(r_{h}^{+})^{2}=\left(1+\frac{2\mathrm{d}(x,M)}{\mathrm{rch}_{\min}}\right)r_{h}^{2}$.

As a result, one may show that any ball has large mass with respect to a
measure
$D\in\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$.

######  Lemma B.1.

Let
$D\in\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
have support $M=\mathrm{Supp}(D)$.

  * •

For all $p\in M$ and $h\leq\mathrm{rch}_{\min}/4$,

$a_{d}f_{\min}h^{d}\leq D\bigl{(}\mathrm{B}(p,h)\bigr{)}\leq
A_{d}f_{\max}h^{d},$

where $a_{d}=2^{-d}\omega_{d}$ and $A_{d}=2^{d}\omega_{d}$.

  * •

For all $x_{0}\in\mathbb{R}^{n}$ and $h\leq\mathrm{rch}_{\min}/8$,

$a^{\prime}_{d}f_{\min}(h^{2}-\mathrm{d}(x_{0},M)^{2})_{+}^{d/2}\leq
D\bigl{(}\mathrm{B}(x_{0},h)\bigr{)}\leq
A^{\prime}_{d}f_{\max}(h^{2}-\mathrm{d}(x_{0},M)^{2})_{+}^{d/2},$

where $a^{\prime}_{d}=(7/8)^{d/2}a_{d}$ and $A^{\prime}_{d}=(5/4)^{d/2}A_{d}$.

###### Proof of Lemma B.1.

The first statement is a direct consequence of [AL18, Propositions 8.6 & 8.7].
The second one follows by combining the previous point with Proposition B.1. ∎

###  B.2 Euclidean Packing and Covering Estimates

For sake of completeness, we include in this section some standard packing and
covering bounds that are used in our analysis. We recall the following
definitions.

A $r$-covering of $K\subseteq\mathbb{R}^{n}$ is a subset
$\mathcal{X}=\left\\{{x_{1},\ldots,x_{k}}\right\\}\subseteq K$ such that for
all $x\in K$, $\mathrm{d}(x,\mathcal{X})\leq r$. A $r$-packing of $K$ is a
subset $\mathcal{Y}=\left\\{y_{1},\ldots,y_{k}\right\\}\subseteq K$ such that
for all $y,y^{\prime}\in\mathcal{Y}$,
$\mathrm{B}(y,r)\cap\mathrm{B}(y^{\prime},r)=\emptyset$ (or equivalently
$\left\|y^{\prime}-y\right\|>2r$).

######  Definition B.1 (Covering and Packing numbers).

For $K\subseteq\mathbb{R}^{n}$ and $r>0$, the covering number
$\mathrm{cv}_{K}(r)$ of $K$ is the minimum number of balls of radius $r$ that
are necessary to cover $K$:

$\displaystyle\mathrm{cv}_{K}(r)$ $\displaystyle=\min\left\\{{{k>0}~{}|\text{
there exists a }r\text{-covering of cardinality }k}\right\\}.$

The packing number $\mathrm{pk}_{K}(r)$ of $K$ is the maximum number of
disjoint balls of radius $r$ that can be packed in $K$:

$\displaystyle\mathrm{pk}_{K}(r)$ $\displaystyle=\max\left\\{{{k>0}~{}|\text{
there exists a }r\text{-packing of cardinality }k}\right\\}.$

Packing and covering numbers are tightly related, as shown by the following
well-known statement.

######  Proposition B.2.

For all subset $K\subseteq\mathbb{R}^{n}$ and $r>0$,

$\displaystyle\mathrm{pk}_{K}(2r)\leq\mathrm{cv}_{K}(2r)\leq\mathrm{pk}_{K}(r).$

###### Proof of Proposition B.2.

For the left-hand side inequality, notice that if $K$ is covered by a family
of balls of radius $2r$, each of these balls contains at most one point of a
maximal $2r$-packing. Conversely, the right-hand side inequality follows from
the fact that a maximal $r$-packing is always a $2r$-covering. Indeed, if it
was not the case one could add a point $x_{0}\in K$ that is $2r$-away from all
of the $r$-packing elements, which would contradict the maximality of this
packing. ∎

We then bound the packing and covering numbers of the submanifolds with reach
bounded below. Note that these bounds depend only on the intrinsic dimension
and volumes, but not on the ambient dimension.

######  Proposition B.3.

For all $M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ and
$r\leq\mathrm{rch}_{\min}/8$,

$\mathrm{pk}_{M}(r)\geq\frac{\mathcal{H}^{d}(M)}{\omega_{d}(4r)^{d}},$

and

$\mathrm{cv}_{M}(r)\leq\frac{\mathcal{H}^{d}(M)}{\omega_{d}(r/4)^{d}}.$

###### Proof of Proposition B.3.

First, we have $\mathrm{pk}_{M}(r)\geq\mathrm{cv}_{M}(2r)$ from Proposition
B.2. In addition, if $\left\\{{p_{i}}\right\\}_{1\leq i\leq N}\subseteq M$ is
a minimal $(2r)$-covering of $M$, then by considering the uniform distribution
$D_{M}=\mathbbm{1}_{M}\mathcal{H}^{d}/\mathcal{H}^{d}(M)$ over $M$, using a
union bound and applying Lemma B.1, we get

$\displaystyle
1=D_{M}\left(\cup_{i=1}^{N}\mathrm{B}(p_{i},2r)\right)\leq\sum_{i=1}^{N}D_{M}(\mathrm{B}(p_{i},2r))\leq
N2^{d}\omega_{d}(2r)^{d}/\mathcal{H}^{d}(M).$

As a result,
$\mathrm{pk}_{M}(r)\geq\mathrm{cv}_{M}(2r)=N\geq\frac{\mathcal{H}^{d}(M)}{\omega_{d}(4r)^{d}}.$

For the second bound, use again Proposition B.2 to get
$\mathrm{cv}_{M}(r)\leq\mathrm{pk}_{M}(r/2)$. Now, by definition, a maximal
$(r/2)$-packing $\left\\{{q_{j}}\right\\}_{1\leq j\leq N^{\prime}}\subseteq M$
of $M$ provides us with a family of disjoint balls of radii $r/2$. Hence, from
Lemma B.1, we get

$\displaystyle 1\geq
D_{M}\left(\cup_{i=j}^{N^{\prime}}\mathrm{B}(q_{j},r/2)\right)=\sum_{j=1}^{N^{\prime}}D_{M}(\mathrm{B}(q_{j},r/2))\geq
N^{\prime}2^{-d}\omega_{d}(r/2)^{d}/\mathcal{H}^{d}(M),$

so that
$\mathrm{cv}_{M}(r)\leq\mathrm{pk}_{M}(r/2)=N^{\prime}\leq\frac{\mathcal{H}^{d}(M)}{\omega_{d}(r/4)^{d}}.$
∎

Bounds on the same discretization-related quantities computed on the Euclidean
$n$-balls and $k$-spheres will also be useful.

######  Proposition B.4.

  * •

For all $r>0$,

$\mathrm{pk}_{\mathrm{B}(0,R)}(r)\geq\left(\frac{R}{2r}\right)^{n}\text{ and
}\mathrm{cv}_{\mathrm{B}(0,R)}(r)\leq\left(1+\frac{2R}{r}\right)^{n}.$

  * •

For all integer $1\leq k<n$ and $r\leq 1/8$,

$\mathrm{pk}_{\mathcal{S}^{k}(0,1)}(r)\geq 2\left(\frac{1}{4r}\right)^{k}.$

###### Proof of Proposition B.4.

  * •

From Proposition B.2, we have