$\mathrm{pk}_{\mathrm{B}(0,R)}(r)\geq\mathrm{cv}_{\mathrm{B}(0,R)}(2r)$.
Furthermore, if $\cup_{i=1}^{N}\mathrm{B}(x_{i},2r)\supseteq\mathrm{B}(0,R)$
is a minimal $2r$-covering of $\mathrm{B}(0,R)$, then by a union bound,
$\omega_{n}R^{n}=\mathcal{H}^{n}(\mathrm{B}(0,R))\leq N\omega_{n}(2r)^{n},$ so
that
$\mathrm{pk}_{\mathrm{B}(0,R)}(r)\geq\mathrm{cv}_{\mathrm{B}(0,R)}(2r)=N\geq(R/(2r))^{n}$.

For the second bound, we use again Proposition B.2 to get
$\mathrm{cv}_{\mathrm{B}(0,R)}(r)\leq\mathrm{pk}_{\mathrm{B}(0,R)}(r/2)$, and
we notice that any maximal $(r/2)$-packing of $\mathrm{B}(0,R)$ with
cardinality $N^{\prime}$ provides us with a family of disjoint balls of radii
$r/2$, all contained in $\mathrm{B}(0,R)^{r/2}=\mathrm{B}(0,R+r/2)$. A union
bound hence yields
$\omega_{n}(R+r/2)^{n}=\mathcal{H}^{n}(\mathrm{B}(0,R+r/2))\geq
N^{\prime}\mathcal{H}^{n}(\mathrm{B}(0,r/2))=N^{\prime}\omega_{n}(r/2)^{n}$,
yielding
$\mathrm{cv}_{\mathrm{B}(0,R)}(r)\leq\mathrm{pk}_{\mathrm{B}(0,R)}(r/2)=N^{\prime}\leq(1+2R/r)^{n}$.

  * •

Notice that $\mathcal{S}^{k}(0,1)\subseteq\mathbb{R}^{n}$ is a compact
$k$-dimensional submanifold without boundary, reach
$\mathrm{rch}_{\mathcal{S}^{k}(0,1)}=1$, and volume
$\mathcal{H}^{k}(\mathcal{S}^{k}(0,1))=\sigma_{k}$. Applying Proposition B.3
together with elementary calculations hence yield

$\displaystyle\mathrm{pk}_{\mathcal{S}^{k}(0,1)}(r)$
$\displaystyle\geq\frac{\sigma_{k}}{\omega_{k}}\left(\frac{1}{4r}\right)^{k}$
$\displaystyle=\left(\dfrac{2\pi^{(k+1)/2}}{\Gamma\left(\frac{k+1}{2}\right)}\right)\left(\dfrac{\pi^{k/2}}{\Gamma\left(\frac{k}{2}+1\right)}\right)^{-1}\left(\frac{1}{4r}\right)^{k}$
$\displaystyle=2\sqrt{\pi}\frac{\Gamma\left(\frac{k}{2}+1\right)}{\Gamma\left(\frac{k+1}{2}\right)}\left(\frac{1}{4r}\right)^{k}$
$\displaystyle\geq 2\left(\frac{1}{4r}\right)^{k}.$

∎

###  B.3 Global Volume Estimates

The following bounds on the volume and diameter of low-dimensional
submanifolds of $\mathbb{R}^{n}$ with positive reach are at the core of
Section 2.2.3. They exhibit some implicit constraints on the parameters for
the statistical models not to be degenerate.

######  Proposition B.5.

For all $M\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$,

$\mathcal{H}^{d}(M)\geq\sigma_{d}\mathrm{rch}_{\min}^{d},$

with equality if and only if $M$ is a $d$-dimensional sphere of radius
$\mathrm{rch}_{\min}$. Furthermore, if $M\subseteq\mathrm{B}(0,R)$ then
$\mathrm{rch}_{\min}\leq\sqrt{2}R$ and

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

###### Proof of Proposition B.5.

For the first bound, note that the operator norm of the second fundamental
form of $M$ is everywhere bounded above by $1/\mathrm{rch}_{\min}$ [NSW08,
Proposition 6.1], so that [Alm86, (3)] applies and yields the result.

For the next statement, note that [Hat02, Theorem 3.26] ensures that $M$ is
not homotopy equivalent to a point. As a result, [AKC+19, Lemma A.3] applies
and yields

$\displaystyle\mathrm{rch}_{\min}$ $\displaystyle\leq\mathrm{rch}_{M}$
$\displaystyle\leq\mathrm{diam}(M)/\sqrt{2}$
$\displaystyle\leq\mathrm{diam}(\mathrm{B}(0,R))/\sqrt{2}$
$\displaystyle=\sqrt{2}R.$

For the last bound, consider a $(\mathrm{rch}_{\min}/8)$-covering
$\left\\{{z_{i}}\right\\}_{1\leq i\leq N}$ of $\mathrm{B}(0,R)$, which can be
chosen so that
$N\leq\left(1+\frac{2R}{\mathrm{rch}_{\min}/8}\right)^{n}\leq\left(\frac{18R}{\mathrm{rch}_{\min}}\right)^{n}$
from Proposition B.4. Applying Lemma B.1 with $h=\mathrm{rch}_{\min}/8$, we
obtain

$\displaystyle\mathcal{H}^{d}(M\cap\mathrm{B}(z_{i},\mathrm{rch}_{\min}/8))$
$\displaystyle\leq(5/4)^{d/2}\times
2^{d}\omega_{d}((\mathrm{rch}_{\min}/8)^{2}-\mathrm{d}(z_{i},M)^{2})_{+}^{d/2}$
$\displaystyle\leq\omega_{d}\left(\frac{\mathrm{rch}_{\min}}{2}\right)^{d},$

for all $i\in\left\\{{1,\ldots,N}\right\\}$. A union bound then yields

$\displaystyle\mathcal{H}^{d}(M)$
$\displaystyle=\mathcal{H}^{d}\left(\cup_{i=1}^{N}M\cap\mathrm{B}(z_{i},\mathrm{rch}_{\min}/8)\right)$
$\displaystyle\leq N\omega_{d}\left(\frac{\mathrm{rch}_{\min}}{2}\right)^{d}$
$\displaystyle\leq\left(\frac{18R}{\mathrm{rch}_{\min}}\right)^{n}\omega_{d}\left(\frac{\mathrm{rch}_{\min}}{2}\right)^{d},$

which concludes the proof. ∎

##  Appendix C Projection Routine

We now build the SQ projection routine
$\hat{\pi}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ (Theorem 4.1), which is used
repeatedly in the SQ emulation of Manifold Propagation (Theorems 5.1 and 5.4).
Recall that 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)$.
We follow the strategy of proof described in Section 4.1.

###  C.1 Bias of the Local Conditional Mean for Projection

In what follows, we will write

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

for the local conditional mean of $D$ given $\mathrm{B}(x_{0},h)$. In order to
study the bias of $m_{D}(x_{0},h)$ with respect to $\pi_{M}(x_{0})$, it will
be convenient to express it (up to approximation) with intrinsic geodesic
balls $\mathrm{B}_{M}(\cdot,\cdot)$ instead of the extrinsic Euclidean balls
$\mathrm{B}(\cdot,\cdot)$ that appears in its definition (Equation 8). This
change of metric is stated in the following result.

######  Lemma C.1.

Let
$D\in\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
have support $M=\mathrm{Supp}(D)$, and $p\in M$. Recall that
$\omega_{d}=\mathcal{H}^{d}\left(\mathrm{B}_{d}(0,1)\right)$ denotes the
volume of the $d$-dimensional unit Euclidean ball. Then for all
$r\leq\mathrm{rch}_{\min}/4$,

$\displaystyle\left\|\mathop{\mathbb{E}}_{x\sim
D}\left[x\mathbbm{1}_{\mathrm{B}_{M}(p,r)}(x)\right]-D\left(\mathrm{B}_{M}(p,r)\right)p\right\|$
$\displaystyle\leq
C^{d}\omega_{d}\left(\frac{f_{\max}}{\mathrm{rch}_{\min}}+L\right)r^{d+2},$

and for $r\leq\bar{r}\leq\mathrm{rch}_{\min}/4$,

$\displaystyle
D\left(\mathrm{B}_{M}(p,\bar{r})\setminus\mathrm{B}_{M}(p,r)\right)$
$\displaystyle\leq(C^{\prime})^{d}\omega_{d}f_{\max}\bar{r}^{d-1}(\bar{r}-r),$

where $C,C^{\prime}>0$ are absolute constants.

###### Proof of Lemma C.1.

First apply the area formula [Fed69, Section 3.2.5] to write the mean of any
measurable function $G$ defined on $M$ as

$\displaystyle\mathop{\mathbb{E}}_{x\sim
D}\left[G(x)\mathbbm{1}_{\mathrm{B}_{M}(p,r)}(x)\right]$
$\displaystyle=\int_{0}^{r}\int_{\mathcal{S}^{d-1}}J(t,v)f\left(\exp_{p}^{M}(tv)\right)G\left(\exp_{p}^{M}(tv)\right)dvdt,$

where $J(t,v)$ is the Jacobian of the volume form of $M$ expressed in polar
coordinates around $p$ for $0\leq t\leq r\leq\mathrm{rch}_{\min}/4$ and unit
$v\in T_{p}M$. That is,
$J(t,v)=t^{d-1}\sqrt{\det\left({A}^{\top}_{t,v}A_{t,v}\right)}$ where
$A_{t,v}=\mathrm{d}_{tv}\exp_{p}^{M}$. But from [AKC+19, Proposition A.1
(iv)], for all $w\in T_{p}M$, we have

$\left(1-\frac{t^{2}}{6\mathrm{rch}_{\min}^{2}}\right)\left\|w\right\|\leq\left\|A_{t,v}w\right\|\leq\left(1+\frac{t^{2}}{\mathrm{rch}_{\min}^{2}}\right)\left\|w\right\|.$

As a consequence,

$\left(1-\frac{t^{2}}{6\mathrm{rch}_{\min}^{2}}\right)^{d}\leq\sqrt{\det\left({A}^{\top}_{t,v}A_{t,v}\right)}\leq\left(1+\frac{t^{2}}{\mathrm{rch}_{\min}^{2}}\right)^{d}$

and in particular,

$\displaystyle R_{J}(t,v):=\left|J(t,v)-t^{d-1}\right|\leq
C^{d}t^{d-1}\left(\frac{t}{\mathrm{rch}_{\min}}\right)^{2},$

where $C>0$ is an absolute constant. Also, by assumption on the model, $f$ is
$L$-Lipschitz, so

$\displaystyle|R_{f}(t,v)|:=\left|f\left(\exp_{p}^{M}(tv)\right)-f(p)\right|$
$\displaystyle=\left|f\left(\exp_{p}^{M}(tv)\right)-f(\exp_{p}^{M}(0))\right|$
$\displaystyle\leq L\left\|\exp_{p}^{M}(tv)-\exp_{p}^{M}(0)\right\|$
$\displaystyle\leq Ld_{M}(\exp_{p}^{M}(0),\exp_{p}^{M}(tv))$
$\displaystyle=Lt.$

Finally, from [AL19, Lemma 1], we have

$\displaystyle\left\|R_{\exp}(t,v)\right\|:=\left\|\exp_{p}^{M}(tv)-(p+tv)\right\|\leq
5t^{2}/(8\mathrm{rch}_{\min}).$

Putting everything together, we can now prove the first bound by writing

$\displaystyle\left\|\mathop{\mathbb{E}}_{x\sim
D}\left[x\mathbbm{1}_{\mathrm{B}_{M}(p,r)}(x)\right]-D\left(\mathrm{B}_{M}(p,r)\right)p\right\|$
$\displaystyle=\left\|\int_{0}^{r}\int_{\mathcal{S}^{d-1}}J(t,v)f\left(\exp_{p}^{M}(tv)\right)\left(\exp_{p}^{M}(tv)-p\right)dvdt\right\|$
$\displaystyle=\left\|\int_{0}^{r}\int_{\mathcal{S}^{d-1}}\left(t^{d-1}+R_{J}(t,v)\right)\left(f(p)+R_{f}(t,v)\right)\left(tv+R_{\exp}(t,v)\right)dvdt\right\|$
$\displaystyle\leq\tilde{C}^{d}\omega_{d}\left(\frac{f_{\max}}{\mathrm{rch}_{\min}}+L\right)r^{d+2},$

where the last inequality used the fact that
$\int_{0}^{r}\int_{\mathcal{S}^{d-1}}t^{d}f(p)vdvdt=0$. Similarly, to derive
the second bound, we write

$\displaystyle
D\left(\mathrm{B}_{M}(p,\bar{r})\setminus\mathrm{B}_{M}(p,r)\right)$
$\displaystyle=\int_{r}^{\bar{r}}\int_{\mathcal{S}^{d-1}}J(t,v)f\left(\exp_{p}^{M}(tv)\right)dvdt$
$\displaystyle\leq\sigma_{d-1}f_{\max}\int_{r}^{\bar{r}}t^{d-1}\left(1+C^{d}\left(t/\mathrm{rch}_{\min}\right)^{2}\right)dt$
$\displaystyle\leq(C^{\prime})^{d}\sigma_{d-1}f_{\max}\int_{r}^{\bar{r}}t^{d-1}dt$
$\displaystyle\leq(C^{\prime\prime})^{d}\omega_{d}f_{\max}\bar{r}^{d-1}(\bar{r}-r),$

which concludes the proof. ∎

We are now in position to bound the bias of $m_{D}(x_{0},h)$.

######  Lemma C.2.

Let
$D\in\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
have support $M=\mathrm{Supp}(D)$, and $x_{0}\in\mathbb{R}^{n}$ be such that
$\mathrm{d}(x_{0},M)<h\leq\mathrm{rch}_{\min}/8$. Then,

$\displaystyle\left\|\pi_{M}(x_{0})-m_{D}(x_{0},h)\right\|\leq
C^{d}\left(\frac{f_{\max}+L\mathrm{rch}_{\min}}{f_{\min}}\right)\frac{hr_{h}}{\mathrm{rch}_{\min}},$

where $r_{h}=(h^{2}-\mathrm{d}(x_{0},M)^{2})^{1/2}$ and $C>0$ is an absolute
constant.

###### Proof of Lemma C.2.

For short, let us write $p_{0}=\pi_{M}(x_{0})$. All the expected values
$\mathop{\mathbb{E}}$ are taken with respect to $x\sim D$. Before any
calculation, we combine Proposition B.1 and Lemma 2.2 to assert that

$\displaystyle\mathrm{B}_{M}\left(p_{0},r_{h}^{-}\right)\subseteq\mathrm{B}(x_{0},h)\cap
M\subseteq\mathrm{B}_{M}\left(p_{0},R_{h}^{+}\right),$ (9)

where we wrote
$(r_{h}^{-})^{2}=\left(1-\mathrm{d}(x_{0},M)/\mathrm{rch}_{\min}\right)r_{h}^{2}$
and $R_{h}^{+}=r_{h}^{+}\left(1+(r_{h}^{+}/\mathrm{rch}_{\min})^{2}\right)$,
with
$(r_{h}^{+})^{2}=\left(1+{2\mathrm{d}(x_{0},M)}/{\mathrm{rch}_{\min}}\right)r_{h}^{2}$.
We note by now from the definition $0<r_{h}^{-}\leq
R_{h}^{+}\leq\mathrm{rch}_{\min}/4$ since
$\mathrm{d}(x_{0},M)<h\leq\mathrm{rch}_{\min}/8$, and that

$\displaystyle R_{h}^{+}-r_{h}^{-}$
$\displaystyle\leq\frac{C^{\prime}r_{h}}{\mathrm{rch}_{\min}}\left(\mathrm{d}(x_{0},M)+r_{h}^{2}/\mathrm{rch}_{\min}\right)\leq\frac{2C^{\prime}hr_{h}}{\mathrm{rch}_{\min}},$
(10)

for some absolute constant $C^{\prime}>0$.

We can now proceed and derive the asserted bound. From triangle inequality,

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

Combining Equation 9, Lemma C.1, Proposition B.1 and Lemma B.1, the first term
of the right hand side can be further upper bounded by

$\displaystyle\left\|\frac{\mathop{\mathbb{E}}\left[(x-p_{0})\mathbbm{1}_{\mathrm{B}(x_{0},h)}(x)\right]}{D(\mathrm{B}(x_{0},h))}-\frac{\mathop{\mathbb{E}}\left[(x-p_{0})\mathbbm{1}_{\mathrm{B}_{M}(p_{0},R_{h}^{+})}(x)\right]}{D(\mathrm{B}_{M}(p_{0},R_{h}^{+}))}\right\|$
$\displaystyle\leq\frac{\left\|\mathop{\mathbb{E}}\left[(x-p_{0})\mathbbm{1}_{\mathrm{B}(x_{0},h)}(x)\right]\right\|}{D(\mathrm{B}(x_{0},h))D(\mathrm{B}_{M}(p_{0},R_{h}^{+}))}\left|D(\mathrm{B}_{M}(p_{0},R_{h}^{+}))-D(\mathrm{B}(x_{0},h))\right|$
$\displaystyle~{}~{}~{}+\frac{\left\|\mathop{\mathbb{E}}\left[(x-p_{0})\left(\mathbbm{1}_{\mathrm{B}_{M}(p_{0},R_{h}^{+})}(x)-\mathbbm{1}_{\mathrm{B}(x_{0},h)}(x)\right)\right]\right\|}{D(\mathrm{B}_{M}(p_{0},R_{h}^{+}))}$
$\displaystyle\leq\frac{2R_{h}^{+}D\left(\mathrm{B}_{M}(p_{0},R_{h}^{+})\setminus\mathrm{B}_{M}(p_{0},r_{h}^{-})\right)}{D(\mathrm{B}_{M}(p_{0},R_{h}^{+}))}$
$\displaystyle\leq\frac{(C^{\prime\prime})^{d}\omega_{d}f_{\max}(R_{h}^{+})^{d}(R_{h}^{+}-r_{h}^{-})}{c^{d}\omega_{d}f_{\min}(R_{h}^{+})^{d}}$
$\displaystyle\leq\tilde{C}^{d}\frac{f_{\max}}{f_{\min}}\frac{hr_{h}}{\mathrm{rch}_{\min}},$

where the last bound uses (10). For the second term, we use Lemma C.1 and
Lemma B.1 to derive

$\displaystyle\frac{\left\|\mathop{\mathbb{E}}\left[(x-p_{0})\mathbbm{1}_{\mathrm{B}_{M}(p_{0},R_{h}^{+})}(x)\right]\right\|}{D(\mathrm{B}_{M}(p_{0},R_{h}^{+}))}$
$\displaystyle\leq\frac{(\tilde{C}^{\prime})^{d}\omega_{d}\left(\frac{f_{\max}}{\mathrm{rch}_{\min}}+L\right)(R_{h}^{+})^{d+2}}{c^{d}\omega_{d}f_{\min}(R_{h}^{+})^{d}}$
$\displaystyle\leq(\tilde{C}^{\prime\prime})^{d}\left(\frac{f_{\max}+L\mathrm{rch}_{\min}}{f_{\min}}\right)\frac{r_{h}^{2}}{\mathrm{rch}_{\min}}.$

Since $r_{h}\leq h$, this concludes the proof by setting
$C=\tilde{C}+\tilde{C}^{\prime\prime}$. ∎

###  C.2 Metric Projection with Statistical Queries

We finally prove the main announced statement of Appendix C.

###### Proof of Theorem 4.1.

First note that under the assumptions of the theorem,
$\mathrm{d}(x_{0},M)\leq\Lambda\leq\mathrm{rch}_{\min}/8$. We hence let $h>0$
be a bandwidth to be specified later, but taken such that
$\mathrm{d}(x_{0},M)<\sqrt{2}\Lambda\leq h\leq\mathrm{rch}_{\min}/8$.

Consider the map
$F(x)=\frac{(x-x_{0})}{h}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq h}$ for
$x\in\mathbb{R}^{n}$. As $\left\|F(x)\right\|\leq 1$ for all
$x\in\mathbb{R}^{n}$, Lemma 2.1 asserts that there exists a deterministic
statistical query algorithm making $2n$ queries to $\mathrm{STAT}(\tau)$ and
that outputs a vector $\hat{W}=\hat{V}/h\in\mathbb{R}^{n}$ such that
$\left\|\mathop{\mathbb{E}}_{x\sim D}\left[F(x)\right]-\hat{V}/h\right\|\leq
C\tau$. Furthermore, with the single query
$r=\mathbbm{1}_{\mathrm{B}(x_{0},h)}$ to $\mathrm{STAT}(\tau)$, we obtain
$\hat{a}\in\mathbb{R}$ such that
$\left|D(\mathrm{B}(x_{0},h)-\hat{a}\right|\leq\tau$. Let us set
$\hat{\pi}(x_{0}):=x_{0}+\hat{V}/\hat{a}$ and prove that it satisfies the
claimed bound. For this, use
$|V/a-\hat{V}/\hat{a}|\leq|a-\hat{a}|V/(a\hat{a})+|V-\hat{V}|/\hat{a}$ to
write

$\displaystyle\left\|m_{D}(x_{0},h)-\hat{\pi}(x_{0})\right\|$
$\displaystyle=\left\|\frac{\mathop{\mathbb{E}}_{x\sim
D}\left[(x-x_{0})\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]}{D(\mathrm{B}(x_{0},h))}-\frac{\hat{V}}{\hat{a}}\right\|$
$\displaystyle\leq\frac{\left|D(\mathrm{B}(x_{0},h))-\hat{a}\right|\left\|\mathop{\mathbb{E}}_{x\sim
D}\left[(x-x_{0})\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]\right\|}{D(\mathrm{B}(x_{0},h))\hat{a}}+\frac{\left\|\mathop{\mathbb{E}}_{x\sim
D}\left[(x-x_{0})\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]-\hat{V}\right\|}{\hat{a}}$
$\displaystyle\leq\frac{\left|D(\mathrm{B}(x_{0},h))-\hat{a}\right|h+\left\|\mathop{\mathbb{E}}_{x\sim
D}\left[(x-x_{0})\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]-\hat{V}\right\|}{D(\mathrm{B}(x_{0},h))-\left|D(\mathrm{B}(x_{0},h)-\hat{a}\right|}$
$\displaystyle\leq\frac{(C+1)\tau h}{D(\mathrm{B}(x_{0},h))-\tau}$
$\displaystyle\leq\frac{(C+1)\tau
h}{\tilde{c}^{d}\omega_{d}f_{\min}(h/\sqrt{2})^{d}-\tau},$

where the last inequality comes from Lemma B.1, and
$r_{h}=(h^{2}-\mathrm{d}(x_{0},M)^{2})^{d/2}\geq h/\sqrt{2}$ since
$h\geq\sqrt{2}\Lambda$. If in addition, one assumes that
$\tilde{c}^{d}\omega_{d}f_{\min}(h/\sqrt{2})^{d}\geq 2\tau$, we obtain the
lower bound
$\tilde{c}^{d}\omega_{d}f_{\min}(h/\sqrt{2})^{d}-\tau\geq\tilde{c}^{d}\omega_{d}f_{\min}(h/\sqrt{2})^{d}/2$,
so that the previous bound further simplifies to

$\displaystyle\left\|m_{D}(x_{0},h)-\hat{\pi}(x_{0})\right\|$
$\displaystyle\leq\frac{(C^{\prime})^{d}}{\omega_{d}f_{\min}}\tau h^{1-d}.$

On the other hand, Lemma C.2 yields that the bias term is not bigger than

$\displaystyle\left\|\pi_{M}(x_{0})-m_{D}(x_{0},h)\right\|\leq\tilde{C}^{d}\left(\frac{f_{\max}+L\mathrm{rch}_{\min}}{f_{\min}}\right)\frac{hr_{h}}{\mathrm{rch}_{\min}},$

with $r_{h}\leq h$. As a result,

$\displaystyle\left\|\pi_{M}(x_{0})-\hat{\pi}(x_{0})\right\|$
$\displaystyle\leq\left\|\pi_{M}(x_{0})-m_{D}(x_{0},h)\right\|+\left\|m_{D}(x_{0},h)-\hat{\pi}(x_{0})\right\|$
$\displaystyle\leq\frac{(C^{\prime}\vee\tilde{C})^{d}}{f_{\min}}\left(\left(f_{\max}+L\mathrm{rch}_{\min}\right)\frac{h}{\mathrm{rch}_{\min}}+\frac{\tau}{\omega_{d}h^{d}}\right)h.$

Taking bandwidth

$\displaystyle h$
$\displaystyle=\max\left\\{{2\Lambda,\left(\frac{\mathrm{rch}_{\min}}{f_{\max}+L\mathrm{rch}_{\min}}\right)^{\frac{1}{d+1}}\left(\frac{\tau}{\omega_{d}}\right)^{\frac{1}{d+1}}}\right\\}$
$\displaystyle=\max\left\\{{2\Lambda,\mathrm{rch}_{\min}\left(\frac{f_{\min}}{f_{\max}+L\mathrm{rch}_{\min}}\right)^{\frac{1}{d+1}}\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{\frac{1}{d+1}}}\right\\},$

we have by assumption on the parameters of the model that
$\mathrm{rch}_{\min}/8\geq h\geq 2\Lambda\geq\sqrt{2}\Lambda$, and that
$\tilde{c}^{d}\omega_{d}f_{\min}(h/\sqrt{2})^{d}\geq 2\tau$ as soon as $c>0$
is small enough. Finally, plugging the value of $h$ in the above bound and
recalling that $\Gamma=\frac{f_{\min}}{f_{\max}+L\mathrm{rch}_{\min}}$ yields

$\displaystyle\left\|\pi_{M}(x_{0})-\hat{\pi}(x_{0})\right\|$
$\displaystyle\leq\frac{\tilde{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\\},$

which concludes the proof. ∎

##  Appendix D Tangent Space Estimation Routine

We now build the SQ tangent space routine
$\hat{T}:\mathbb{R}^{n}\to\mathbb{G}^{n,d}$ (Theorem 4.2), which is used
repeatedly in the SQ emulation of Manifold Propagation (Theorems 5.1 and 5.4).
Recall that 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)$. We
follow the strategy of proof described in Section 4.2.

To fix notation from now on, we let
$\left\langle{A},{B}\right\rangle=\mathrm{tr}(A^{\ast}B)$ stand for the
Euclidean inner product between $A,B\in\mathbb{R}^{k\times k}$. We also write
$\left\|\Sigma\right\|_{\mathrm{F}}=\sqrt{\left\langle{\Sigma},{\Sigma}\right\rangle}$
for the Frobenius norm,
$\left\|\Sigma\right\|_{\mathrm{op}}=\max_{\left\|v\right\|\leq
1}\left\|\Sigma v\right\|$ for the operator norm, and
$\left\|\Sigma\right\|_{\ast}=\max_{\left\|X\right\|_{\mathrm{op}}\leq
1}\left\langle{\Sigma},{X}\right\rangle$ for the nuclear norm. In what
follows, for a symmetric matrix $A\in\mathbb{R}^{n\times n}$, we let
$\mu_{i}(A)$ denote its $i$-th largest singular value.

###  D.1 Bias of Local Principal Component Analysis

In what follows, we will write

$\displaystyle\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]$ (11)

for the re-scaled local covariance-like matrix of $D$ at
$x_{0}\in\mathbb{R}^{n}$ with bandwidth $h>0$. Notice that for simplicity,
this local covariance-like matrix is computed with centering at the current
point $x_{0}$, and not at the local conditional mean
$\mathop{\mathbb{E}}_{x\sim D}\left[x|\left\|x-x_{0}\right\|\leq h\right]$.
This choice simplifies our analysis and will not impact the subsequent
estimation rates. Let us first decompose this matrix and exhibit its link with
the target tangent space $T_{\pi_{M}(x_{0})}M\in\mathbb{G}^{n,d}$.

######  Lemma D.1.

Let
$D\in\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
have support $M=\mathrm{Supp}(D)$, $x_{0}\in\mathbb{R}^{n}$ and $h>0$. If
$\mathrm{d}(x_{0},M)\leq\eta\leq h/\sqrt{2}$ and
$h\leq\mathrm{rch}_{\min}/(8\sqrt{d})$, then there exists a symmetric matrix
$\Sigma_{0}\in\mathbb{R}^{n\times n}$ with
$\operatorname{Im}(\Sigma_{0})=T_{\pi_{M}(x_{0})}M$ such that

$\Sigma_{D}(x_{0},h)=\Sigma_{0}+R,$

with $\mu_{d}(\Sigma_{0})\geq\omega_{d}f_{\min}(ch)^{d}$ and
$\left\|R\right\|_{\ast}\leq\omega_{d}f_{\max}(Ch)^{d}\left(\frac{\eta}{h}+\frac{h}{\mathrm{rch}_{\min}}\right)$,
where $c,C>0$ are absolute constants.

###### Proof of Lemma D.1.

This proof roughly follows the ideas of [AL18, Section E.1], with a different
center point in the covariance matrix ($x_{0}$ itself instead of the local
mean around $x_{0}$) and finer (nuclear norm) estimates on residual terms. For
brevity, we let $p_{0}=\pi_{M}(x_{0})$. We first note that the integrand
defining $h^{2}\Sigma_{D}(x_{0},h)$ decomposes as

$\displaystyle(x-x_{0}){(x-x_{0})}^{\top}$
$\displaystyle=(x-p_{0}){(x-p_{0})}^{\top}+(x_{0}-p_{0}){(x_{0}-p_{0})}^{\top}$
(12)
$\displaystyle~{}~{}~{}~{}+(x-p_{0}){(x_{0}-p_{0})}^{\top}+(x_{0}-p_{0}){(x-p_{0})}^{\top},$

for all $x\in\mathrm{B}(x_{0},h)\cap M$. After integrating them with respect
to $x\sim D$, we bound the last two terms, by writing

$\displaystyle\left\|\mathop{\mathbb{E}}_{x\sim
D}\left[(x-p_{0}){(x_{0}-p_{0})}^{\top}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]\right\|_{\ast}$ $\displaystyle=\left\|\mathop{\mathbb{E}}_{x\sim
D}\left[(x_{0}-p_{0}){(x-p_{0})}^{\top}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]\right\|_{\ast}$ $\displaystyle\leq\mathop{\mathbb{E}}_{x\sim
D}\left[\left\|(x_{0}-p_{0}){(x-p_{0})}^{\top}\right\|_{\ast}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]$ $\displaystyle=\mathop{\mathbb{E}}_{x\sim
D}\left[\left\|x_{0}-p_{0}\right\|\left\|x-p_{0}\right\|\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]$ $\displaystyle\leq\eta hD(\mathrm{B}(x_{0},h))$ $\displaystyle\leq
C^{d}\omega_{d}f_{\max}\eta h^{d+1},$

where the last inequality uses Lemma B.1. Similarly, for the second term of
Equation 12, we have

$\displaystyle\left\|\mathop{\mathbb{E}}_{x\sim
D}\left[(x_{0}-p_{0}){(x_{0}-p_{0})}^{\top}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]\right\|_{\ast}$
$\displaystyle=\left\|x_{0}-p_{0}\right\|^{2}D(\mathrm{B}(x_{0},h))$
$\displaystyle\leq C^{d}\omega_{d}f_{\max}\eta^{2}h^{d}.$

Given $v\in\mathbb{R}^{n}$, write $v_{\sslash}=\pi_{T_{p_{0}}M}(v)$ and
$v_{\perp}=v-v_{\sslash}=\pi_{T_{p_{0}}M^{\perp}}(v)$. We now focus on the
first term of Equation 12, which we further decompose as

$\displaystyle(x-p_{0}){(x-p_{0})}^{\top}$
$\displaystyle=(x-p_{0})_{\sslash}{(x-p_{0})_{\sslash}}^{\top}+(x-p_{0})_{\perp}{(x-p_{0})_{\perp}}^{\top}$
(13)
$\displaystyle~{}~{}~{}~{}+(x-p_{0})_{\perp}{(x-p_{0})_{\sslash}}^{\top}+(x-p_{0})_{\sslash}{(x-p_{0})_{\perp}}^{\top},$

for all $x\in\mathrm{B}(x_{0},h)\cap M$. Note that for those points
$x\in\mathrm{B}(x_{0},h)\cap M$, we have
$\left\|(x-p_{0})_{\sslash}\right\|\leq\left\|x-p_{0}\right\|\leq 2h$, and
from [Fed59, Theorem 4.18],
$\left\|(x-p_{0})_{\perp}\right\|\leq\left\|x-p_{0}\right\|^{2}/(2\mathrm{rch}_{\min})\leq
4h^{2}/(2\mathrm{rch}_{\min})$. Hence, for the last two terms of Equation 13,

$\displaystyle\left\|\mathop{\mathbb{E}}_{x\sim
D}\bigl{[}(x-p_{0})_{\perp}{(x-p_{0})_{\sslash}}^{\top}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\bigr{]}\right\|_{\ast}$ $\displaystyle=\left\|\mathop{\mathbb{E}}_{x\sim
D}\left[(x-p_{0})_{\sslash}{(x-p_{0})_{\perp}}^{\top}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]\right\|_{\ast}$ $\displaystyle\leq\mathop{\mathbb{E}}_{x\sim
D}\bigl{[}\left\|(x-p_{0})_{\sslash}\right\|\left\|(x-p_{0})_{\perp}\right\|\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\bigr{]}$ $\displaystyle\leq
C^{d}\omega_{d}f_{\max}h^{d+3}/\mathrm{rch}_{\min},$

where we used Lemma B.1 again. Dealing now with the second term of Equation
13,

$\displaystyle\left\|\mathop{\mathbb{E}}_{x\sim
D}\bigl{[}(x-p_{0})_{\perp}{(x-p_{0})_{\perp}}^{\top}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\bigr{]}\right\|_{\ast}$ $\displaystyle\leq\mathop{\mathbb{E}}_{x\sim
D}\bigl{[}\left\|(x-p_{0})_{\perp}\right\|\left\|(x-p_{0})_{\perp}\right\|\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\bigr{]}$ $\displaystyle\leq
C^{d}\omega_{d}f_{\max}h^{d+4}/(4\mathrm{rch}_{\min}^{2}).$

Finally, let us write

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

The matrix $\Sigma_{0}$ is symmetric and clearly has image
$\operatorname{Im}(\Sigma_{0})\subseteq T_{p_{0}}M$. Furthermore, since
$\mathrm{d}(x_{0},M)\leq\eta\leq h/\sqrt{2}$ and $h\leq\mathrm{rch}_{\min}/8$,
Proposition B.1 and Lemma 2.2 yield that $M\cap\mathrm{B}(x_{0},h)\supseteq
M\cap\mathrm{B}\bigl{(}p_{0},\sqrt{7}h/4\bigr{)}\supseteq\mathrm{B}_{M}(p_{0},h/2)$.
Hence, for all $u\in T_{p_{0}}M$,

$\displaystyle h^{2}\left\langle{\Sigma_{0}u},{u}\right\rangle$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim
D}\left[\left\langle{(x-p_{0})_{\sslash}},{u}\right\rangle^{2}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]$ $\displaystyle=\mathop{\mathbb{E}}_{x\sim
D}\left[\left\langle{x-p_{0}},{u}\right\rangle^{2}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}\right]$ $\displaystyle\geq
f_{\min}\int_{\mathrm{B}_{M}(p_{0},h/2)}\left\langle{x-p_{0}},{u}\right\rangle^{2}\mathrm{d}\mathcal{H}^{d}(x)$
$\displaystyle=f_{\min}\int_{\mathrm{B}_{d}(0,h/2)}\left\langle{\exp_{p_{0}}^{M}(v)-p_{0}},{u}\right\rangle^{2}\left|\det\left(\mathrm{d}_{v}\exp_{p_{0}}^{M}\right)\right|\mathrm{d}v,$

where $\mathcal{H}^{d}$ is the $d$-dimensional Hausdorff measure on
$\mathbb{R}^{n}$, and $\exp_{p_{0}}^{M}:T_{p_{0}}M\to M$ is the exponential
map of $M$ at $p_{0}$. But [AL18, Proposition 8.7] states that there exists
$c>0$ such that for all $v\in\mathrm{B}_{d}(0,\mathrm{rch}_{\min}/4)$,
$\left|\det\left(\mathrm{d}_{v}\exp_{p_{0}}^{M}\right)\right|\geq c^{d}$, and
[AL19, Lemma 1] yields the bound
$\left\|\exp_{p_{0}}^{M}(v)-(p_{0}+v)\right\|\leq
5\left\|v\right\|^{2}/(8\mathrm{rch}_{\min})$. As a result, using the fact
that $(a-b)^{2}\geq a^{2}/2-3b^{2}$ for all $a,b\in\mathbb{R}$, we have

$\displaystyle h^{2}\left\langle{\Sigma_{0}u},{u}\right\rangle$
$\displaystyle\geq
c^{d}f_{\min}\int_{\mathrm{B}_{d}(0,h/2)}\left(\left\langle{v},{u}\right\rangle-\left\langle{\exp_{p_{0}}^{M}(v)-(p_{0}+v)},{u}\right\rangle\right)^{2}\mathrm{d}v$
$\displaystyle\geq
c^{d}f_{\min}\int_{\mathrm{B}_{d}(0,h/2)}\left\langle{v},{u}\right\rangle^{2}/2-3\left\langle{\exp_{p_{0}}^{M}(v)-(p_{0}+v)},{u}\right\rangle^{2}\mathrm{d}v$
$\displaystyle\geq
c^{d}f_{\min}\int_{\mathrm{B}_{d}(0,h/2)}\left\langle{v},{u}\right\rangle^{2}/2-3\left\|u\right\|^{2}\left(5\left\|v\right\|^{2}/(8\mathrm{rch}_{\min})\right)^{2}\mathrm{d}v$
$\displaystyle=c^{d}f_{\min}\sigma_{d-1}\left(\frac{1}{2d(d+2)}-\frac{3(5/8)^{2}}{d+4}\left(\frac{h}{2\mathrm{rch}_{\min}}\right)^{2}\right)\left(\frac{h}{2}\right)^{d+2}\left\|u\right\|^{2}$
$\displaystyle\geq(c^{\prime})^{d}\omega_{d}f_{\min}h^{d+2}\left\|u\right\|^{2},$

as soon as $h\leq\mathrm{rch}_{\min}/\sqrt{d}$. In particular, the last bound
shows that the image of $\Sigma_{0}$ is exactly $T_{p_{0}}M$, and that
$\mu_{d}(\Sigma_{0})\geq\omega_{d}f_{\min}(c^{\prime}h)^{d}$. Summing up the
above, we have shown that

$\Sigma_{D}(x_{0},h)=\Sigma_{0}+R,$

where $\Sigma_{0}$ is symmetric,
$\operatorname{Im}(\Sigma_{0})=T_{\pi_{M}(x_{0})}M$,
$\mu_{d}(\Sigma_{0})\geq\omega_{d}f_{\min}(c^{\prime}h)^{d}$, and

$\displaystyle\left\|R\right\|_{\ast}$
$\displaystyle\leq\omega_{d}f_{\max}(C^{\prime}h)^{d}\left(\frac{\eta}{h}+\frac{\eta^{2}}{h^{2}}+\frac{h}{\mathrm{rch}_{\min}}+\frac{h^{2}}{\mathrm{rch}_{\min}^{2}}\right)$
$\displaystyle\leq\omega_{d}f_{\max}(C^{\prime\prime}h)^{d}\left(\frac{\eta}{h}+\frac{h}{\mathrm{rch}_{\min}}\right),$

which is the announced result. ∎

###  D.2 Matrix Decomposition and Principal Angles

The following lemma ensures that the principal components of a matrix $A$ are
stable to perturbations, provided that $A$ has a large-enough spectral gap.
For a symmetric matrix $A\in\mathbb{R}^{n\times n}$, recall that $\mu_{i}(A)$
denotes its $i$-th largest singular value.

######  Lemma D.2 (Davis-Kahan).

Let $\hat{A},A\in\mathbb{R}^{n\times n}$ be symmetric matrices such that
$\mathrm{rank}(A)=d$. If $\hat{T}\in\mathbb{G}^{n,d}$ denotes the linear space
spanned by the first $d$ eigenvectors of $\hat{A}$, and
$T=\operatorname{Im}(A)\in\mathbb{G}^{n,d}$, then

$\angle\bigl{(}T,\hat{T}\bigr{)}:=\left\|\pi_{\hat{T}}-\pi_{T}\right\|_{\mathrm{op}}\leq\frac{2\left\|\hat{A}-A\right\|_{\mathrm{F}}}{\mu_{d}(A)}.$

###### Proof of Lemma D.2.

It is a direct application of [YWS15, Theorem 2] with $r=1$ and $s=d$. ∎

###  D.3 Low-rank Matrix Recovery

Proceeding further in the strategy described in Section 4.2, we now explain
how to estimate the local covariance matrix
$\Sigma_{D}(x_{0},h)\in\mathbb{R}^{n\times n}$ (Equation 11) in
$\mathrm{STAT}(\tau)$.

Because $\Sigma_{D}(x_{0},h)\in\mathbb{R}^{n\times n}=\mathbb{R}^{n^{2}}$ can
be seen as a mean vector with respect to the unknown distribution $D$,
$2n^{2}$ queries to $\mathrm{STAT}(\tau)$ would yield error $O(\tau)$ from
Lemma 2.1. However, this would not use the low-rank structure of
$\Sigma_{D}(x_{0},h)$, i.e. some redundancy of its entries. To mitigate the
query complexity of this estimation problem, we will use compressed sensing
techniques [FCRP08]. Mimicking the vector case (Lemma 2.1), we put our problem
in the broader context of the estimation of $\Sigma=\mathop{\mathbb{E}}_{x\sim
D}[F(x)]\in\mathbb{R}^{k\times k}$ in $\mathrm{STAT}(\tau)$, where
$F:\mathbb{R}^{n}\to\mathbb{R}^{k\times k}$ and $\Sigma$ are approximately low
rank (see Lemma D.4).

####  D.3.1 Restricted Isometry Property and Low-Rank Matrix Recovery

Let us first present some fundamental results coming of matrix recovery.
Following [FCRP08, Section II], assume that we observe $y\in\mathbb{R}^{q}$
such that

$\displaystyle y=\mathcal{L}(\Sigma)+z,$ (14)

where $\Sigma\in\mathbb{R}^{k\times k}$ is the matrix of interest,
$\mathcal{L}:\mathbb{R}^{k\times k}\to\mathbb{R}^{q}$ is a linear map seen as
a sampling operator, and $z\in\mathbb{R}^{q}$ encodes noise and has small
Euclidean norm $\left\|z\right\|\leq\xi$.

In general, when $q<k^{2}$, $\mathcal{L}$ has non-empty kernel, and hence one
has no hope to recover $\Sigma$ only from $y$, even with no noise. However, if
$\Sigma$ is (close to being) low-rank and that $\mathcal{L}$ does not shrink
low-rank matrices too much, $\mathcal{L}(\Sigma)$ may not actually censor
information on $\Sigma$, while compressing the dimension from $k^{2}$ to $q$.
A way to formalize this idea states as follows.

######  Definition D.1 (Restricted Isometry Property).

Let $\mathcal{L}:\mathbb{R}^{k\times k}\to\mathbb{R}^{q}$ be a linear map, and
$d\leq k$. We say that $\mathcal{L}$ satisfies the $d$-restricted isometry
property with constant $\delta>0$ if for all matrix $X\in\mathbb{R}^{k\times
k}$ of rank at most $d$,

$\displaystyle(1-\delta)\left\|X\right\|_{\mathrm{F}}\leq\left\|\mathcal{L}(X)\right\|\leq(1+\delta)\left\|X\right\|_{\mathrm{F}}.$

We let $\delta_{d}(\mathcal{L})$ denote the smallest such $\delta$.

To recover $\Sigma$ only from the knowledge of $y$, consider the convex
optimization problem (see [FCRP08]) over $X\in\mathbb{R}^{k\times k}$:

$\displaystyle\begin{array}[]{ll}\text{minimize}&\left\|X\right\|_{\ast}\\\
\text{subject to}&\left\|y-\mathcal{L}(X)\right\|\leq\xi.\end{array}$ (17)

Let $\Sigma_{\text{opt}}$ denote the solution of Equation 17. To give
insights, the nuclear norm is seen here as a convex relaxation of the rank
function [FCRP08], so that Equation 17 is expected to capture a low-rank
matrix close to $\Sigma$. If $\mathcal{L}$ satisfies the restricted isometry
property, the next result states that (17) does indeed capture such a low-rank
matrix. In what follows, we let $\Sigma^{(d)}\in\mathbb{R}^{k\times k}$ denote
the matrix closest to $\Sigma$ among all the matrices of rank $d$, where
closeness is indifferently measured in nuclear, Frobenius, or operator norm.
That is, $\Sigma^{(d)}$ is the truncated singular value decomposition of
$\Sigma$.

######  Theorem D.1 ([FCRP08, Theorem 4]).

Assume that $\delta_{5d}<1/10$. Then the solution $\Sigma_{\text{opt}}$ of
Equation 17 satisfies

$\displaystyle\left\|\Sigma_{\text{opt}}-\Sigma\right\|_{\mathrm{F}}\leq
C_{0}\frac{\left\|\Sigma-\Sigma^{(d)}\right\|_{\ast}}{\sqrt{d}}+C_{1}\xi,$

where $C_{0},C_{1}>0$ are universal constants.

####  D.3.2 Building a Good Matrix Sensing Operator

We now detail a standard way to build a sampling operator $\mathcal{L}$ that
satisfies the restricted isometry property (Definition D.1), thereby allowing
to recover low-rank matrices from a few measurements (Theorem D.1). For purely
technical reasons, we shall present a construction over the complex linear
space $\mathbb{C}^{k\times k}$. This will eventually enable us to recover
results over $\mathbb{R}^{k\times k}$ via the isometry $\mathbb{R}^{k\times
k}\hookrightarrow\mathbb{C}^{k\times k}$.

First, we note that given an orthonormal $\mathbb{C}$-basis
$\mathbb{W}=(W_{1},\dots,W_{k^{2}})$ of $\mathbb{C}^{k\times k}$ for the
Hermitian inner product
$\left\langle{A},{B}\right\rangle=\mathrm{tr}(A^{*}B)$, we can build a
sampling operator $\mathcal{L}_{\mathbb{S}}:\mathbb{C}^{k\times
k}\to\mathbb{C}^{q}$ by projecting orthogonally onto the space spanned by only
$q$ (randomly) pre-selected $\mathbb{S}\subseteq\mathbb{W}$ elements of the
basis.

When $k=2^{\ell}$, an orthonormal basis of $\mathbb{C}^{k\times k}$ of
particular interest is the so-called _Pauli_ basis [Liu11]. Its construction
goes as follows:

  * •

For $k=2$ ($\ell=1$), it is defined by $W^{(1)}_{i}=\sigma_{i}/\sqrt{2}$,
where

$\sigma_{1}=\begin{pmatrix}0&1\\\
1&0\end{pmatrix},\quad\sigma_{2}=\begin{pmatrix}0&-i\\\
i&0\end{pmatrix},\quad\sigma_{3}=\begin{pmatrix}1&0\\\
0&-1\end{pmatrix},\quad\sigma_{4}=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}.$

Note that the $\sigma_{i}$’s have two eigenvalues, both belonging to
$\left\\{{-1,1}\right\\}$, so that they are both Hermitian and unitary. In
particular, $\left\|W^{(1)}_{i}\right\|_{\mathrm{op}}=1/\sqrt{2}$ and
$\left\|W^{(1)}_{i}\right\|_{\mathrm{F}}=1$ for all
$i\in\left\\{{1,\dots,4}\right\\}$. One easily checks that
$\bigl{(}W^{(1)}_{i}\bigr{)}_{1\leq i\leq 4}$ is an orthonormal basis of
$\mathbb{C}^{2\times 2}$.

  * •

For $k=2^{\ell}$ ($\ell\geq 2$), the Pauli basis
$\bigl{(}W^{(\ell)}_{i}\bigr{)}_{1\leq i\leq 2^{\ell}}$ is composed of
matrices acting on the tensor space
$\left(\mathbb{C}^{2}\right)^{\otimes\ell}\simeq\mathbb{C}^{2^{\ell}}$, and
defined as the family of all the possible $\ell$-fold tensor products of
elements of $\bigl{(}W^{(1)}_{i}\bigr{)}_{1\leq i\leq 4}$. As tensor products
preserve orthogonality, we get that $\bigl{(}W^{(\ell)}_{i}\bigr{)}_{1\leq
i\leq 2^{\ell}}$ is an orthonormal basis of $\mathbb{C}^{2^{\ell}\times
2^{\ell}}$. Furthermore, as $\left\|W\otimes
W^{\prime}\right\|_{\mathrm{op}}=\left\|W\right\|_{\mathrm{op}}\left\|W^{\prime}\right\|_{\mathrm{op}}$,
we get that for all $i\in\left\\{{1,\dots,2^{\ell}}\right\\}$,

$\displaystyle\left\|W^{(k)}_{i}\right\|_{\mathrm{op}}=\left(\frac{1}{\sqrt{2}}\right)^{\ell}=\frac{1}{\sqrt{k}}.$
(18)

Since
$\left\|W\right\|_{\mathrm{F}}\leq\sqrt{k}\left\|W\right\|_{\mathrm{op}}$, the
value $1/\sqrt{k}$ actually is the smallest possible common operator norm of
an orthonormal basis of $\mathbb{C}^{k\times k}$. As will be clear in the
proof of Lemma D.3, this last property — called incoherence in the matrix
completion literature [Liu11] — is key to design a good sampling operator.

Still considering the case $k=2^{\ell}$, we let
$\mathcal{L}_{\mathrm{Pauli}}:\mathbb{C}^{k\times k}\to\mathbb{C}^{q}$ denote
the random sampling operator defined by

$\displaystyle\mathcal{L}_{\mathrm{Pauli}}(X)=\left(\frac{k}{\sqrt{q}}\left\langle{W_{I_{i}}^{(\ell)}},{X}\right\rangle\right)_{1\leq
i\leq q},$ (19)

where $(I_{i})_{1\leq i\leq q}$ is an i.i.d. sequence with uniform
distribution over $\left\\{{1,\dots,k^{2}}\right\\}$. Up to the factor
$k/\sqrt{q}$, $\mathcal{L}_{\mathrm{Pauli}}$ is the orthogonal projector onto
the space spanned by $(W^{(\ell)}_{I_{1}},\dots,W^{(\ell)}_{I_{q}})$. This
normalisation $k/\sqrt{q}$ is chosen so that for all $X\in\mathbb{C}^{k\times
k}$,

$\displaystyle\mathop{\mathbb{E}}\bigl{[}\left\|\mathcal{L}_{\mathrm{Pauli}}(X)\right\|^{2}\bigr{]}$
$\displaystyle=\frac{k^{2}}{q}\sum_{i=1}^{k^{2}}q\Pr\left(I_{1}=i\right)\left|\left\langle{W_{i}^{(\ell)}},{X}\right\rangle\right|^{2}$
$\displaystyle=\sum_{i=1}^{k^{2}}\left|\left\langle{W_{i}^{(\ell)}},{X}\right\rangle\right|^{2}=\left\|X\right\|_{\mathrm{F}}^{2}.$

That is, roughly speaking, $\mathcal{L}_{\mathrm{Pauli}}$ satisfies the
restricted isometry property (RIP, Definition D.1) on average. Actually, as
soon as $q$ is large enough compared to $d$, the result below states that
$\mathcal{L}_{\mathrm{Pauli}}$ does fulfill a restricted isometry property
with high probability.

######  Lemma D.3.

Assume that $k=2^{\ell}$, and fix $0<\alpha\leq 1$. There exist universal
constants $c_{0},c_{1}>0$ such that if $q\geq
c_{0}kd\log^{6}(k)\log(c_{1}/\alpha)$, then with probability at least
$1-\alpha$, the following holds.

For all $X\in\mathbb{R}^{k\times k}$ such that
$\left\|X\right\|_{\ast}\leq\sqrt{5d}\left\|X\right\|_{\mathrm{F}}$,

$\left|\left\|\mathcal{L}_{\mathrm{Pauli}}(X)\right\|-\left\|X\right\|_{\mathrm{F}}\right|\leq\frac{\left\|X\right\|_{\mathrm{F}}}{20}.$

In particular, on the same event of probability at least $1-\alpha$,
$\delta_{5d}\left(\mathcal{L}_{\mathrm{Pauli}}\right)<1/10$.

###### Proof of Lemma D.3.

The Pauli basis is an orthonormal basis of $\mathbb{C}^{k\times k}$, and from
Equation 18, its elements all have operator norm smaller than $1/\sqrt{k}$.
Hence, applying [Liu11, Theorem 2.1] with $K=\sqrt{k}\max_{1\leq i\leq
k}\left\|W^{(\ell)}_{i}\right\|_{\mathrm{op}}=1$, $r=5d$,
$C=c_{0}\log(c_{1}/\alpha)$, and $\delta=1/20$ yields the first bound. The
second one follows by recalling that any rank-$r$ matrix
$X\in\mathbb{R}^{k\times k}$ satisfies
$\left\|X\right\|_{\ast}\leq\sqrt{r}\left\|X\right\|_{\mathrm{F}}$. ∎

####  D.3.3 Mean Matrix Completion with Statistical Queries

The low-rank matrix recovery of Sections D.3.1 and D.3.2 combined with mean
vector estimation in $\mathrm{STAT}(\tau)$ for the Euclidean norm (see Lemma
2.1) lead to the following result.

######  Lemma D.4.

For all $\alpha\in(0,1]$, there exists a family of statistical query
algorithms indexed by maps $F:\mathbb{R}^{n}\to\mathbb{R}^{k\times k}$ such
that the following holds on an event of probability at least $1-\alpha$
(uniformly over $F$).

Let $D$ be a Borel probability distribution over $\mathbb{R}^{n}$, and
$F:\mathbb{R}^{n}\to\mathbb{R}^{k\times k}$ be a map such that for all
$x\in\mathbb{R}^{n}$, $\left\|F(x)\right\|_{\mathrm{F}}\leq 1$ and
$\left\|F(x)\right\|_{\ast}\leq\sqrt{5d}\left\|F(x)\right\|_{\mathrm{F}}$.
Write $\Sigma=\mathop{\mathbb{E}}_{x\sim D}\left[F(x)\right]$, and
$\Sigma^{(d)}$ for the matrix closest to $\Sigma$ among all the matrices of
rank $d\leq k$. Assume that $\Sigma\in\Xi$, where
$\Xi\subseteq\mathbb{R}^{k\times k}$ is a known linear subspace of
$\mathbb{R}^{k\times k}$.

Then, there exists a statistical query algorithm making at most
$c_{0}dk\log^{6}(k)\log(c_{1}/\alpha)$ queries to $\mathrm{STAT}(\tau)$, and
that outputs a matrix $\hat{\Sigma}\in\Xi$ that satisfies

$\displaystyle\left\|\hat{\Sigma}-\Sigma\right\|_{\mathrm{F}}\leq
C_{0}\frac{\left\|\Sigma-\Sigma^{(d)}\right\|_{\ast}}{\sqrt{d}}+C_{1}\tau$

on the event of probability at least $1-\alpha$ described above, where
$C_{0},C_{1}>0$ are universal constants.

###### Proof of Lemma D.4.

Without loss of generality, we can assume that $k=2^{\ell}$. Indeed, one can
always embed $\mathbb{R}^{k\times k}$ isometrically into
$\mathbb{R}^{2^{\ell}\times 2^{\ell}}$, with
$2^{\ell}=2^{\left\lceil\log_{2}(k)\right\rceil}\leq 2k$, via the linear map

$\mathbb{R}^{k\times k}\ni
A\longmapsto\tilde{A}=\left(\begin{array}[]{c|c}A&0\\\ \hline\cr
0&0\end{array}\right)\in\mathbb{R}^{2^{\ell}\times 2^{\ell}},$

which preserves both the rank, the Frobenius and nuclear norms.

Let $q\geq 1$ be a fixed integer to be specified later, and $(I_{i})_{1\leq
i\leq q}$ be and i.i.d. sequence with uniform distribution over
$\left\\{{1,\dots,k^{2}}\right\\}$, and for $X\in\mathbb{R}^{k\times k}$,
write

$\displaystyle\mathcal{L}_{\mathrm{Pauli}}(X)=\left(\frac{k}{\sqrt{q}}\left\langle{W_{I_{i}}^{(\ell)}},{X}\right\rangle\right)_{1\leq
i\leq q}\in\mathbb{C}^{q}=\mathbb{R}^{2q},$ (20)

as in Equation 19. For $x\in\mathbb{R}^{n}$, write
$G(x)=\mathcal{L}_{\mathrm{Pauli}}(F(x))/2\in\mathbb{R}^{2q}$. From Lemma D.3,
with probability at least $1-\alpha$ (over the randomness of $(I_{i})_{1\leq
i\leq q}$),

$\displaystyle\left\|G(x)\right\|$
$\displaystyle=\left\|\mathcal{L}_{\mathrm{Pauli}}(F(x))\right\|/2\leq(1+1/20)\left\|F(x)\right\|_{\mathrm{F}}/2\leq\left\|F(x)\right\|_{\mathrm{F}}\leq
1$

holds simultaneously for all the described $F:\mathbb{R}^{k\times
k}\to\mathbb{R}^{2q}$. Hence, on this event of probability at least
$1-\alpha$, Lemma 2.1 applies to $G$ and provides a deterministic statistical
query algorithm making $4q$ queries to $\mathrm{STAT}(\tau)$, and that outputs
a vector $y\in\mathbb{R}^{2q}$ such that

$\left\|y-\mathop{\mathbb{E}}_{x\sim D}\left[G(x)\right]\right\|\leq C\tau,$

where $C>0$ is a universal constant. But on the other hand, by linearity,

$\displaystyle\mathop{\mathbb{E}}_{x\sim D}\left[2G(x)\right]$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim
D}\left[\mathcal{L}_{\mathrm{Pauli}}(F(x))\right]=\mathcal{L}_{\mathrm{Pauli}}\left(\mathop{\mathbb{E}}_{x\sim
D}\left[F(x)\right]\right)=\mathcal{L}_{\mathrm{Pauli}}(\Sigma),$

where all the expected values are taken with respect $D$, conditionally on
$(I_{i})_{1\leq i\leq q}$. Hence, as soon as $q\geq
c_{0}dk\log^{6}(k)\log(c_{1}/\alpha)$, Theorem D.1 and Lemma D.3 combined
together yields the following: on the same event of probability at least
$1-\alpha$ as before, the solution $\Sigma_{\text{opt}}$ to the convex
optimization problem over $X\in\mathbb{R}^{k\times k}$ given by

$\displaystyle\begin{array}[]{ll}\text{minimize}&\left\|X\right\|_{\ast}\\\
\text{subject to}&\left\|2y-\mathcal{L}_{\mathrm{Pauli}}(X)\right\|\leq
2C\tau,\end{array}$

satisfies

$\displaystyle\left\|\Sigma_{\text{opt}}-\Sigma\right\|_{\mathrm{F}}\leq
C_{0}\frac{\left\|\Sigma-\Sigma^{(d)}\right\|_{\ast}}{\sqrt{d}}+C_{1}(2C\tau).$

Hence, the projected solution $\hat{\Sigma}=\pi_{\Xi}(\Sigma_{\text{opt}})$
onto $\Xi\subseteq\mathbb{R}^{k\times k}$ belongs to $\Xi$ and satisfies

$\displaystyle\left\|\hat{\Sigma}-\Sigma\right\|_{\mathrm{F}}=\left\|\pi_{\Xi}(\Sigma_{\text{opt}}-\Sigma)\right\|_{\mathrm{F}}$
$\displaystyle\leq\left\|\Sigma_{\text{opt}}-\Sigma\right\|_{\mathrm{F}}$
$\displaystyle\leq
C_{0}\frac{\left\|\Sigma-\Sigma^{(d)}\right\|_{\ast}}{\sqrt{d}}+C_{1}^{\prime}\tau,$

which concludes the proof. ∎

###  D.4 Tangent Space Estimation with Statistical Queries

We finally prove the main announced statement of Appendix D.

###### Proof of Theorem 4.2.

Let $h>0$ be a bandwidth to be specified later, such that $\eta\leq
h/\sqrt{2}$ and $h\leq\mathrm{rch}_{\min}/(8\sqrt{d})$. First note that
$\Sigma_{D}(x_{0},h)=\mathop{\mathbb{E}}_{x\sim D}\left[F(x)\right]$, where
the function
$F(x)=(x-x_{0}){(x-x_{0})}^{\top}/h^{2}\mathbbm{1}_{\left\|x-x_{0}\right\|\leq
h}$ is defined for all $x\in\mathbb{R}^{n}$, and is such that
$\left\|F(x)\right\|_{\mathrm{F}}\leq 1$ and $\mathrm{rank}(F(x))\leq 1$. In
particular,
$\left\|F(x)\right\|_{\ast}=\left\|F(x)\right\|_{\mathrm{F}}\leq\sqrt{5d}\left\|F(x)\right\|_{\mathrm{F}}$
for all $x\in\mathbb{R}^{n}$. Furthermore, $\Sigma_{D}(x_{0},h)$ belongs to
the linear space $\Xi$ of symmetric matrices. Working on the event on which
Lemma D.4 holds (with $\alpha=1/2$, say), yields the existence of a
deterministic SQ algorithm making at most $c_{0}dn\log^{6}(n)\log(2c_{1})$
queries to $\mathrm{STAT}(\tau)$, and that outputs a symmetric matrix
$\hat{\Sigma}$ that satisfies

$\displaystyle\left\|\hat{\Sigma}-\Sigma_{D}(x_{0},h)\right\|_{\mathrm{F}}\leq
C_{0}\frac{\left\|\Sigma_{D}(x_{0},h)-\Sigma^{(d)}_{D}(x_{0},h)\right\|_{\ast}}{\sqrt{d}}+C_{1}\tau,$

with probability at least $1-\alpha$. On the other hand, from Lemma D.1,
provided that $\sqrt{2}\eta\leq h\leq\mathrm{rch}_{\min}/(8\sqrt{d})$, one can
write

$\Sigma_{D}(x_{0},h)=\Sigma_{0}+R,$

where the symmetric matrix $\Sigma_{0}$ satisfies
$\operatorname{Im}(\Sigma_{0})=T_{\pi_{M}(x_{0})}M$,
$\mu_{d}(\Sigma_{0})\geq\omega_{d}f_{\min}(ch)^{d}$ and
$\left\|R\right\|_{\mathrm{F}}\leq\left\|R\right\|_{\ast}\leq\omega_{d}f_{\max}(Ch)^{d}\left(\frac{\eta}{h}+\frac{h}{\mathrm{rch}_{\min}}\right)$.
As $\mathrm{rank}(\Sigma_{0})=d$, we have in particular that,

$\left\|\Sigma_{D}(x_{0},h)-\Sigma^{(d)}_{D}(x_{0},h)\right\|_{\ast}\leq\left\|\Sigma_{D}(x_{0},h)-\Sigma_{0}\right\|_{\ast}=\left\|R\right\|_{\ast}.$

Therefore, taking $\hat{T}(x_{0})$ as the linear space spanned by the first
$d$ eigenvectors of $\hat{\Sigma}$, Lemma D.2 yields

$\displaystyle\angle\bigl{(}T_{\pi_{M}(x_{0})}M,\hat{T}(x_{0})\bigr{)}$
$\displaystyle=\left\|\pi_{\hat{T}(x_{0})}-\pi_{T_{\pi_{M}(x_{0})}M}\right\|_{\mathrm{op}}$
$\displaystyle\leq\frac{2\left\|\hat{\Sigma}-\Sigma_{0}\right\|_{\mathrm{F}}}{\mu_{d}(\Sigma_{0})}$
$\displaystyle\leq
2\frac{\left\|\hat{\Sigma}-\Sigma_{D}(x_{0},h)\right\|_{\mathrm{F}}+\left\|\Sigma_{D}(x_{0},h)-\Sigma_{0}\right\|_{\mathrm{F}}}{\mu_{d}(\Sigma_{0})}$
$\displaystyle\leq\frac{2}{\omega_{d}f_{\min}(ch)^{d}}\left(C_{0}\frac{\left\|R\right\|_{\ast}}{\sqrt{d}}+C_{1}\tau+\left\|R\right\|_{\mathrm{F}}\right)$
$\displaystyle\leq\frac{C^{\prime
d}}{\omega_{d}f_{\min}}\left(\omega_{d}f_{\max}\left\\{\frac{\eta}{h}+\frac{h}{\mathrm{rch}_{\min}}\right\\}+\frac{\tau}{h^{d}}\right).$

We conclude by setting
$h=\mathrm{rch}_{\min}\left\\{\sqrt{\frac{\eta}{\mathrm{rch}_{\min}}}\vee\left(\frac{\tau}{\omega_{d}f_{\max}\mathrm{rch}_{\min}^{d}}\right)^{1/(d+1)}\right\\}$
in this last bound. This value for $h$ does satisfy $\sqrt{2}\eta\leq
h\leq\mathrm{rch}_{\min}/(8\sqrt{d})$ since
$\eta\leq\mathrm{rch}_{\min}/(64d)$ and
$\frac{\tau}{\omega_{d}f_{\max}\mathrm{rch}_{\min}^{d}}\leq\left(\frac{1}{8\sqrt{d}}\right)^{d+1}$,
so that the whole analysis applies, and yields the announced result. ∎

##  Appendix E Seed Point Detection

We now build the SQ point detection algorithm $\hat{x}_{0}\in\mathbb{R}^{n}$
(Theorem 4.3), which is used to initialize in the SQ emulation of Manifold
Propagation yielding the SQ reconstruction algorithm in the model
$\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
where no seed point is available (Definition 2.6).

Recall that 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)$. We follow the strategy of proof described in Section
4.3.

###  E.1 Detecting a Raw Initial Point

Starting from the whole ball $\mathrm{B}(0,R)$, the following result allows us
to find a point nearby $M$ using a binary search, with best precision of order
$\Omega(\tau^{1/d})$. Let us note that it does not explicitly rely on any
differential property of $M$, but only the behavior of the mass of balls for
$D$ (Lemma B.1).

######  Theorem E.1.

Let
$D\in\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
have support $M=\mathrm{Supp}(D)\subseteq\mathrm{B}(0,R)$. Let
$\Lambda_{0}\leq\mathrm{rch}_{\min}/8$ be fixed, and assume that
$\frac{\Lambda_{0}}{\sqrt{\log(6R/\Lambda_{0})}}\geq
21\mathrm{rch}_{\min}\sqrt{n}\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{1/d}$.

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

$\mathrm{d}(\hat{x}_{0}^{raw},M)\leq\Lambda_{0}.$

######  Remark E.1.

Recall from Section 2.2.3 that we always assume that
$R\geq\mathrm{rch}_{\min}/\sqrt{2}$ to ensure that the model is nonempty. As a
result $\log(6R/\Lambda_{0})\geq 0$ for all
$\Lambda_{0}\leq\mathrm{rch}_{\min}/8$.

###### Proof of Theorem E.1.

The idea is to use a divide and conquer strategy over a covering
$\left\\{{x_{i}}\right\\}_{1\leq i\leq N}$ of $\mathrm{B}(0,R)$. The algorithm
recurses over a subset of indices
$\mathcal{I}\subseteq\left\\{{1,\ldots,N}\right\\}$ that is maintained to
fulfill $\cup_{i\in\mathcal{I}}\mathrm{B}(x_{i},h)\cap M\neq\emptyset$ for
some known $h>0$. This property can be checked with the single query
$r=\mathbbm{1}_{\cup_{i\in\mathcal{I}}\mathrm{B}(x_{i},h)}$ to
$\mathrm{STAT}(\tau)$, provided that
$D(\cup_{i\in\mathcal{I}}\mathrm{B}(x_{i},h))>\tau$. To ensure the later, the
radius $h>0$ is dynamically increased at each iteration. The algorithm stops
when $\mathcal{I}$ is reduced to a singleton. More formally, we consider SQ
Ambient Binary Search.

0:

Model parameters $d,\mathrm{rch}_{\min},f_{\min}$

Precision $\Lambda_{0}>0$

1: Initialize value $h\leftarrow\Lambda_{0}/2$, and set
$\Delta=6\mathrm{rch}_{\min}\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{1/d}$

2: Consider a minimal $(\Lambda_{0}/2)$-covering
$\left\\{{x_{i}}\right\\}_{1\leq i\leq N}$ of $\mathrm{B}(0,R)$, where
$N=\mathrm{cv}_{\mathrm{B}(0,R)}(\Lambda_{0}/2)$

3: Initialize sets $\mathcal{I}\leftarrow\left\\{{1,\ldots,N}\right\\}$,
$\mathcal{L}\leftarrow\emptyset$ and $\mathcal{R}\leftarrow\emptyset$

4: while $|\mathcal{I}|>1$ do

5: Split $\mathcal{I}=\mathcal{L}\cup\mathcal{R}$ into two disjoint sets
$\mathcal{L}\cap\mathcal{R}=\emptyset$ such that
$\left||\mathcal{L}|-|\mathcal{R}|\right|\leq 1$

6: Query
$r=\mathbbm{1}_{\cup_{i\in\mathcal{L}}\mathrm{B}\left(x_{i},\sqrt{h^{2}+\Delta^{2}}\right)}$
to the $\mathrm{STAT}(\tau)$ oracle

7: $\mathrm{a}$ $\leftarrow$ Value answered by the oracle

8: if $\mathrm{a}>\tau$ then

9: $\mathcal{I}\leftarrow\mathcal{L}$

10: else

11: $\mathcal{I}\leftarrow\mathcal{R}$

12: end if

$h\leftarrow\sqrt{h^{2}+\Delta^{2}}$

13: end while

14: return The only element of $\hat{x}_{0}^{raw}$ of
$\left\\{{x_{i}}\right\\}_{i\in\mathcal{I}}$

Algorithm 2 SQ Ambient Binary Search

Because $|\mathcal{I}|$ is a decreasing sequence of integers, it is clear that
SQ Ambient Binary Search terminates, and that $|\mathcal{I}_{final}|=1$ so
that the output $\hat{x}_{0}^{raw}$ is well defined. As each _while_ loop does
only one query to $\mathrm{STAT}(\tau)$, and that
$N=\mathrm{cv}_{\mathrm{B}(0,R)}(\Lambda_{0}/2)\leq(6R/\Lambda_{0})^{n}$ from
Proposition B.4 and $\Lambda_{0}\leq R$, it makes at most
$\left\lfloor\log_{2}(N)+1\right\rfloor\leq\left\lfloor
n\log(6R/\Lambda_{0})/\log(2)+1\right\rfloor\leq 3n\log(6R/\Lambda_{0})$
queries in total.

Let us now prove that the output $\hat{x}_{0}^{raw}$ satisfies
$\mathrm{d}(\hat{x}_{0}^{raw},M)\leq\Lambda_{0}$. For this, we show that when
running SQ Ambient Binary Search, the inequality
$\min_{i\in\mathcal{I}}\mathrm{d}(x_{i},M)\leq h$ is maintained (recall that
both $\mathcal{I}$ and $h$ are dynamic), or equivalently that
$\cup_{i\in\mathcal{I}}\mathrm{B}\left(x_{i},h\right)\cap M\neq\emptyset$. At
initialization, this is clear because
$\mathcal{I}=\left\\{{1,\ldots,N}\right\\}$, $h=\Lambda_{0}/2$, and
$\left\\{{x_{i}}\right\\}_{1\leq i\leq N}$ is a $(\Lambda_{0}/2)$-covering of
$\mathrm{B}(0,R)\supseteq M$. Then, proceeding by induction, assume that
$\cup_{i\in\mathcal{I}}\mathrm{B}\left(x_{i},h\right)\cap M\neq\emptyset$ when
entering an iteration of the _while_ loop. Let $i_{0}\in\mathcal{I}$ be such
that $\mathrm{d}(x_{i_{0}},M)\leq h$. From Lemma B.1, provided that
$\sqrt{h^{2}+\Delta^{2}}\leq\mathrm{rch}_{\min}/8$, we have

$\displaystyle
D\left(\cup_{i\in\mathcal{I}}\mathrm{B}\left(x_{i},\sqrt{h^{2}+\Delta^{2}}\right)\right)$
$\displaystyle\geq
D\left(\mathrm{B}\left(x_{i_{0}},\sqrt{h^{2}+\Delta^{2}}\right)\right)$
$\displaystyle\geq(\sqrt{7/24})^{d}\omega_{d}f_{\min}\left((h^{2}+\Delta^{2})-\mathrm{d}(x_{i_{0}},M)^{2}\right)^{d/2}$
$\displaystyle\geq(\sqrt{7/24})^{d}\omega_{d}f_{\min}\Delta^{d}$
$\displaystyle=(\sqrt{7/24})^{d}6^{d}\tau$ $\displaystyle>2\tau.$ (21)

Hence, if we let $\mathrm{a}$ denote the answer of the oracle to the query
$r=\mathbbm{1}_{\cup_{i\in\mathcal{L}}\mathrm{B}\left(x_{i},\sqrt{h^{2}+\Delta^{2}}\right)}$,
we have:

  * •

If $\mathrm{a}>\tau$, then

$\displaystyle
D\left(\cup_{i\in\mathcal{L}}\mathrm{B}\left(x_{i},\sqrt{h^{2}+\Delta^{2}}\right)\right)\geq\mathrm{a}-\tau>0,$

so that after the updates $\mathcal{I}\leftarrow\mathcal{L}$ and
$h\leftarrow\sqrt{h^{2}+\Delta^{2}}$, we still have
$\cup_{i\in\mathcal{I}}\mathrm{B}\left(x_{i},h\right)\cap M\neq\emptyset.$

  * •

Otherwise $a\leq\tau$, so that from Equation 21,

$\displaystyle
D\left(\cup_{i\in\mathcal{R}}\mathrm{B}\left(x_{i},\sqrt{h^{2}+\Delta^{2}}\right)\right)$
$\displaystyle\geq
D\left(\cup_{i\in\mathcal{I}}\mathrm{B}\left(x_{i},\sqrt{h^{2}+\Delta^{2}}\right)\right)-D\left(\cup_{i\in\mathcal{L}}\mathrm{B}\left(x_{i},\sqrt{h^{2}+\Delta^{2}}\right)\right)$
$\displaystyle>2\tau-(\mathrm{a}+\tau)$ $\displaystyle\geq 0.$

So as above, after the updates $\mathcal{I}\leftarrow\mathcal{R}$ and
$h\leftarrow\sqrt{h^{2}+\Delta^{2}}$, we still have
$\cup_{i\in\mathcal{I}}\mathrm{B}\left(x_{i},h\right)\cap M\neq\emptyset.$

Consequently, when the algorithm terminates, we have

$\displaystyle\mathrm{d}(\hat{x}_{0}^{raw},M)$ $\displaystyle\leq h_{final}$
$\displaystyle\leq\sqrt{\left(\frac{\Lambda_{0}}{2}\right)^{2}+3n\log(6R/\Lambda_{0})\Delta^{2}}$
$\displaystyle\leq\frac{\Lambda_{0}}{2}+\sqrt{3n\log(6R/\Lambda_{0})}6\mathrm{rch}_{\min}\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{1/d}$
$\displaystyle\leq\Lambda_{0},$

since $\frac{\Lambda_{0}}{\sqrt{\log(6R/\Lambda_{0})}}\geq
21\mathrm{rch}_{\min}\sqrt{n}\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{1/d}$.
The above also shows that when running the algorithm we have
$\sqrt{h^{2}+\Delta^{2}}\leq
h_{final}\leq\Lambda_{0}\leq\mathrm{rch}_{\min}/8$, which ensures that
Equation 21 is valid throughout and concludes the proof. ∎

###  E.2 Refined Point Detection

We finally prove the main announced statement of Appendix E.

###### Proof of Theorem 4.3.

The idea is to first detect a possibly coarse base point $\hat{x}_{0}^{raw}$
using a divide and conquer strategy in the ambient space (Theorem E.1), and
then refine it by considering iterated projections of $\hat{x}_{0}^{raw}$
given by the local conditional mean (Theorem 4.1). More precisely, let
$\hat{x}_{0}^{raw}$ be the output of the point detection SQ algorithm of
Theorem E.1 applied with parameter

$\Lambda_{0}=\max\left\\{{\eta,\min\left\\{{\frac{1}{16},\frac{\Gamma}{2C^{d}}}\right\\}\mathrm{rch}_{\min}}\right\\},$

where $C^{d},\Gamma>0$ are the constants of Theorem 4.1. From the assumptions
on the parameters (recall also that we necessarily have
$R\geq\mathrm{rch}_{\min}/\sqrt{2}$, see Section 2.2.3), we have
$\Lambda_{0}\leq\mathrm{rch}_{\min}/8$ and

$\frac{\Lambda_{0}}{\sqrt{\log(6R/\Lambda_{0})}}\geq
21\mathrm{rch}_{\min}\sqrt{n}\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{1/d},$

so that Theorem E.1 applies and guarantees that $\hat{x}_{0}^{raw}$ can be
obtained with at most $3n\log(6R/\Lambda_{0})$ queries to
$\mathrm{STAT}(\tau)$ and satisfies
$\mathrm{d}(\hat{x}_{0}^{raw},M)\leq\Lambda_{0}$.

If $\Lambda=\eta$ — condition which can be checked by the learner since the
parameters $\eta,\Gamma,d$ and $\mathrm{rch}_{\min}$ are assumed to be known
—, then $\hat{x}_{0}:=\hat{x}_{0}^{raw}$ clearly satisfies
$\mathrm{d}(\hat{x}_{0},M)=\mathrm{d}(\hat{x}_{0}^{raw},M)\leq\eta$, and has
required at most $3n\log(6R/\Lambda_{0})=3n\log(6R/\eta)$ queries to
$\mathrm{STAT}(\tau)$. Otherwise, $\eta\leq\Lambda_{0}$, and we iterate the SQ
approximate projections $\hat{\pi}(\cdot)$ given by Theorem 4.1. Namely, we
let $\hat{y}_{0}=\hat{x}_{0}^{raw}$ and for all integer $k\geq 1$,
$\hat{y}_{k}=\hat{\pi}(\hat{y}_{k-1})$. In total, note that the computation of
$\hat{y}_{k}$ requires at most $3n\log(6R/\eta)+k(2n+1)\leq
3n\bigl{(}\log(6R/\eta)+k\bigr{)}$ queries to $\mathrm{STAT}(\tau)$. Similarly
as above, from the assumptions on the parameters, one easily shows by
induction that since
$\mathrm{d}(\hat{y}_{0},M)\leq\Lambda_{0}\leq\frac{\mathrm{rch}_{\min}}{16}$,
Theorem 4.1 applies to each $\hat{y}_{k}$ and guarantees that

$\displaystyle\mathrm{d}(\hat{y}_{k},M)$
$\displaystyle=\mathrm{d}(\hat{\pi}(\hat{y}_{k-1}),M)$
$\displaystyle\leq\left\|\hat{\pi}(\hat{y}_{k-1})-\pi_{M}(\hat{y}_{k-1}))\right\|$
$\displaystyle\leq\max\left\\{{\frac{C^{d}\mathrm{d}(\hat{y}_{k-1},M)^{2}}{\Gamma\mathrm{rch}_{\min}},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\\}$
$\displaystyle\leq\max\left\\{{\frac{\mathrm{d}(\hat{y}_{k-1},M)}{2},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\\}$
$\displaystyle\leq\max\left\\{{\frac{\Lambda_{0}}{2^{k}},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\\}.$

To conclude, fix
$k_{0}:=\left\lceil\log_{2}\left(\Lambda_{0}/\eta\right)\right\rceil\leq\log\left(6\Lambda_{0}/\eta\right)$,
and set $\hat{x}_{0}:=\hat{y}_{k_{0}}$. From the previous bound, we obtain
that

$\displaystyle\mathrm{d}(\hat{x}_{0},M)$
$\displaystyle\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\\},$

with $\hat{x}_{0}$ requiring at most
$3n\bigl{(}\log(6R/\eta)+\log\left(6\Lambda_{0}/\eta\right)\bigr{)}\leq
6n\log(6R/\eta)$ queries to $\mathrm{STAT}(\tau)$ to be computed, which
concludes the proof. ∎

##  Appendix F Proof for the Main Statistical Query Manifold Estimators

This section is devoted to the proof of the two SQ manifold estimation upper
bounds: the first one in the fixed point model
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
(Theorem 5.1), and the second one for the bounding ball model
$\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
(Theorem 5.4).

###### Proof of Theorem 5.1.

Let us write

$\Delta:=\mathrm{rch}_{\min}\max\left\\{{\sqrt{\varepsilon/(\mathrm{rch}_{\min}\bar{C}_{d})},\mathbf{C}^{\frac{3}{2}}\bigl{(}\tau/(\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d})\bigr{)}^{\frac{1}{d+1}}}\right\\},$

for some large enough $\bar{C}_{d}>0$ depending on $d$ and $\mathbf{C}$ to be
chosen later, and $\delta=\Delta/2$. We will run Manifold Propagation with
scale parameters $\Delta$, $\delta$, angle $\sin\alpha=1/64$, and
initialization point $\hat{x}_{0}=0\in M$, the SQ projection routine
$\hat{\pi}(\cdot)$ of Theorem 4.1 and the SQ tangent space routine
$\hat{T}(\cdot)$ of Theorem 4.2. If we prove that these routines are precise
enough, then Theorem 3.1 will assert that the output point cloud $\mathcal{O}$
and associated tangent space estimates $\mathbb{T}_{\mathcal{O}}$ of Manifold
Propagation fulfill the assumptions of Theorem 2.1. This will hence allow to
reconstruct $M$ with a good triangulation, as claimed.

Note by now that at each iteration Manifold Propagation, exactly one call to
each SQ routine $\hat{\pi}(\cdot)$ and $\hat{T}(\cdot)$ are made, yielding at
most $(2n+1)+Cdn\log^{6}(n)\leq C^{\prime}dn\log^{6}(n)$ statistical queries.
But if Theorem 3.1 applies, we get that the number of iteration
$N_{\mathrm{loop}}$ of Manifold Propagation satisfies

$\displaystyle N_{\mathrm{loop}}$
$\displaystyle\leq\dfrac{\mathcal{H}^{d}(M)}{\omega_{d}(\delta/32)^{d}}$
$\displaystyle\leq\frac{\bar{C}^{\prime}_{d}}{f_{\min}(\sqrt{\mathrm{rch}_{\min}\varepsilon})^{d}}$
$\displaystyle=\frac{\bar{C}^{\prime}_{d}}{f_{\min}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{\varepsilon}\right)^{d/2},$

where the second inequality comes from the fact that
$1=\int_{M}f\mathrm{d}\mathcal{H}^{d}\geq f_{\min}\mathcal{H}^{d}(M)$. In
total, the resulting SQ algorithm hence makes at most

$\displaystyle q$
$\displaystyle\leq\bigl{(}C^{\prime}dn\log^{6}(n)\bigr{)}\frac{\bar{C}^{\prime}_{d}}{f_{\min}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{\varepsilon}\right)^{d/2}$
$\displaystyle=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)$, which is the announced complexity. It only
remains to verify that the SQ routines $\hat{\pi}(\cdot)$ and $\hat{T}(\cdot)$
are indeed precise enough so that Theorem 3.1 applies, and to bound the final
precision given by the triangulation of Theorem 2.1.

To this aim, we notice that the assumption made on $\tau$ puts it in the
regime of validity of Theorem 4.1 and Theorem 4.2. Let us write

$\displaystyle\mathbf{C}:=\max\left\\{{C^{d}\Gamma^{\frac{2}{d+1}-1},\tilde{C}^{d}\frac{f_{\max}}{f_{\min}}}\right\\}\leq\frac{(\max\\{C,\tilde{C}\\})^{d}}{\Gamma},$

where $C>0$ is the constant of Theorem 4.1 and $\tilde{C}>1$ that of Theorem
4.2. Note by now that since $f_{\max}\geq f_{\min}$, we have $\mathbf{C}\geq
1$. For short, we also let
$\tilde{\tau}:=\tau/(\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d})$.

At initialization, and since
$D\in\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$,
the seed point $\hat{x}_{0}=0$ belongs to $M$, meaning that

$\displaystyle\mathrm{d}(\hat{x}_{0},M)=0\leq\eta:=\mathrm{rch}_{\min}\max\left\\{{\frac{1}{\mathbf{C}^{2}}\left(\frac{\Delta}{\mathrm{rch}_{\min}}\right)^{2},\mathbf{C}\tilde{\tau}^{\frac{2}{d+1}}}\right\\}.$

Note that from the assumptions on the parameters,
$\eta\leq\mathrm{rch}_{\min}/(64d)$. Hence, on the $\eta$-offset $M^{\eta}$ of
$M$, Theorem 4.2 asserts that $\hat{T}(\cdot)$ has precision

$\displaystyle\sin\theta$
$\displaystyle\leq\max\left\\{{\tilde{C}^{d}\frac{f_{\max}}{f_{\min}}\frac{1}{\mathbf{C}}\frac{\Delta}{\mathrm{rch}_{\min}},\tilde{C}^{d}\frac{f_{\max}}{f_{\min}}\sqrt{\mathbf{C}}\tilde{\tau}^{\frac{1}{d+1}}}\right\\}$
$\displaystyle\leq\max\left\\{{\frac{\Delta}{\mathrm{rch}_{\min}},\mathbf{C}^{\frac{3}{2}}\tilde{\tau}^{\frac{1}{d+1}}}\right\\}$

for estimating tangent spaces. As a result, we have

$\displaystyle\frac{5\Delta^{2}}{8\mathrm{rch}_{\min}}+\eta+\Delta\sin\theta$
$\displaystyle\leq
3\mathrm{rch}_{\min}\max\left\\{{\left(\frac{\Delta}{\mathrm{rch}_{\min}}\right)^{2},\frac{\eta}{\mathrm{rch}_{\min}},\frac{\Delta}{\mathrm{rch}_{\min}}\sin\theta}\right\\}$
$\displaystyle\leq
3\mathrm{rch}_{\min}\max\left\\{{\left(\frac{\Delta}{\mathrm{rch}_{\min}}\right)^{2},\frac{\eta}{\mathrm{rch}_{\min}},\sin^{2}\theta}\right\\}$
$\displaystyle\leq
3\mathrm{rch}_{\min}\max\left\\{{\left(\frac{\Delta}{\mathrm{rch}_{\min}}\right)^{2},\mathbf{C}^{3}\tilde{\tau}^{\frac{2}{d+1}}}\right\\}$
$\displaystyle:=\Lambda.$

Using again the assumptions on the parameters, we have
$\Lambda\leq\mathrm{rch}_{\min}/8$. Hence, applying Theorem 4.1 and elementary
simplifications given by the assumptions on the parameters yield that, over
the $\Lambda$-offset $M^{\Lambda}$ of $M$, the projection $\hat{\pi}(\cdot)$
has precision at most

$\displaystyle\eta^{\prime}$
$\displaystyle\leq\mathrm{rch}_{\min}\max\left\\{\left(\frac{9C^{d}}{\Gamma}\left(\frac{\Delta}{\mathrm{rch}_{\min}}\right)^{2}\right)\left(\frac{\Delta}{\mathrm{rch}_{\min}}\right)^{2},\right.$
$\displaystyle\hskip
80.00012pt\left.\max\left\\{{\frac{9C^{d}\mathbf{C}^{6}}{\Gamma}\tilde{\tau}^{2/(d+1)},C^{d}\Gamma^{\frac{2}{d+1}-1}}\right\\}\tilde{\tau}^{2/(d+1)}\right\\}$
$\displaystyle=\mathrm{rch}_{\min}\max\left\\{{\left(\frac{9C^{d}}{\Gamma}\left(\frac{\Delta}{\mathrm{rch}_{\min}}\right)^{2}\right)\left(\frac{\Delta}{\mathrm{rch}_{\min}}\right)^{2},C^{d}\Gamma^{\frac{2}{d+1}-1}\tilde{\tau}^{2/(d+1)}}\right\\}$
$\displaystyle\leq\mathrm{rch}_{\min}\max\left\\{{\frac{1}{\mathbf{C}^{2}}\left(\frac{\Delta}{\mathrm{rch}_{\min}}\right)^{2},\mathbf{C}\tilde{\tau}^{2/(d+1)}}\right\\}$
$\displaystyle=\eta.$

Additionally, one easily checks that $\Delta\leq\mathrm{rch}_{\min}/24$,
$\eta\leq\Delta/24$ and $\max\left\\{{\sin\alpha,\sin\theta}\right\\}\leq
1/64$, so that Theorem 3.1 applies: Manifold Propagation terminates and
outputs a finite point cloud $\mathcal{O}$ such that
$\max_{x\in\mathcal{O}}\mathrm{d}(x,M)\leq\eta$ and $\max_{p\in
M}\mathrm{d}(p,\mathcal{O})\leq\Delta+\eta\leq 2\Delta$, together with tangent
space estimates $\mathbb{T}_{\mathcal{O}}$ with error at most $\sin\theta$.
Hence, applying Theorem 2.1 with parameters $\Delta^{\prime}=2\Delta$, $\eta$
and $\sin\theta$ (for which one easily checks that they fulfill its
assumptions), we get that the triangulation $\hat{M}$ of Theorem 2.1 computed
over $\mathcal{O}$ and $\mathbb{T}_{\mathcal{O}}$ achieves precision

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

which yields the announced result since
$\mathbf{C}\leq(C\vee\tilde{C})^{d}/\Gamma$. ∎

###### Proof of Theorem 5.4.

The proof follows the same lines as that of Theorem 5.1, except for the seed
point $\hat{x}_{0}$ which is not trivially available, and requires extra
statistical queries. More precisely, we let $\hat{x}_{0}$ be the output point
given by the SQ detection algorithm of Theorem 4.3 applied with precision
parameter $\varepsilon/2$. This point requires no more than
$6n\log(6R/\varepsilon)$ statistical queries to $\mathrm{STAT}(\tau)$.
Furthermore, adopting the same notation as in the proof of Theorem 5.1 we have

$\displaystyle\mathrm{d}(\hat{x}_{0},M)$
$\displaystyle\leq\max\left\\{{\frac{\varepsilon}{2},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\\}$
$\displaystyle\leq\mathrm{rch}_{\min}\max\left\\{{\frac{1}{\mathbf{C}^{2}}\left(\frac{\Delta}{\mathrm{rch}_{\min}}\right)^{2},\mathbf{C}\tilde{\tau}^{\frac{2}{d+1}}}\right\\},$

so that the rest of the proof runs exactly as that of Theorem 5.1, and yields
the result. ∎

##  Appendix G Statistical Query Lower Bounds in Metric Spaces

In spirit, the lower bound techniques developed below are similar to the
_statistical dimension_ of [Fel17], developed for general search problems.
However, when working with manifold models, this tool appears difficult to
handle, due to the singular nature of low-dimensional distributions, yielding
non-dominated models. Indeed, if $D_{0}$ and $D_{1}$ are distributions that
have supports being $d$-dimensional submanifolds
$M_{0},M_{1}\subseteq\mathbb{R}^{n}$, and that $M_{0}\neq M_{1}$, then $D_{0}$
and $D_{1}$ cannot be absolutely continuous with respect to one another. As a
result, any lower bound technique involving Kullback-Leibler or chi-squared
divergences becomes non-informative (see for instance [Fel17, DKS17]).

Instead, we present techniques that are well-suited for non-dominated models.
They apply for SQ estimation in metric spaces $(\Theta,\rho)$ (see Section
2.1), as opposed to the (more general) setting of _search problems_ of
[Fel17]. We decompose these results into two different types of lower bounds:

  * •

(Section G.1) The _information-theoretic_ ones, yielding a maximal estimation
precision $\varepsilon=\varepsilon(\tau)$ given a tolerance $\tau$;

  * •

(Section G.2) The _computational_ ones, yielding a minimal number of queries
$q=q(\varepsilon)$ to achieve a given precision $\varepsilon$.

###  G.1 Information-Theoretic Lower Bound for Randomized SQ Algorithms

The proofs of the informational lower bounds Theorems 5.2 and 5.5 are based on
the following Theorem G.1, which is similar to so-called _Le Cam’s Lemma_
[Yu97]. To introduce this result we define the _total variation distance_
between probability distributions.

######  Definition G.1 (Total Variation Distance).

Given two probability distributions $D_{0}$ and $D_{1}$ over
$(\mathbb{R}^{n},\mathcal{B}(\mathbb{R}^{n}))$, the _total variation distance_
between them is defined by

$\displaystyle\mathop{\mathrm{TV}}(D_{0},D_{1})$
$\displaystyle=\sup_{B\in\mathcal{B}(\mathbb{R}^{n})}\bigl{|}D_{0}(B)-D_{1}(B)\bigr{|}$
$\displaystyle=\sup_{\begin{subarray}{c}r:\mathbb{R}^{n}\to[-1,1]\\\
\text{measurable}\end{subarray}}\frac{1}{2}\bigl{|}\mathop{\mathbb{E}}_{D_{0}}[r]-\mathop{\mathbb{E}}_{D_{1}}[r]\bigr{|}.$

The second formula above for the total variation suggests how it can measure
an impossibility of estimation with $\mathrm{STAT}(\tau)$ oracles: two
distributions that are close in total variation distance provide a malicious
oracle to make them — and their parameter of interest — indistinguishable
using SQ’s, . This lower bound insight is what underlies Le Cam’s Lemma [Yu97]
in the sample model, and it adapts easily to (randomized) SQ’s in the
following way.

######  Theorem G.1 (Le Cam’s Lemma for Statistical Queries).

Consider a model $\mathcal{D}$ and a parameter of interest
$\theta:\mathcal{D}\to\Theta$ in the metric space $(\Theta,\rho)$. Assume that
there exist _hypotheses_ $D_{0},D_{1}\in\mathcal{D}$, such that

$\mathop{\mathrm{TV}}(D_{0},D_{1})\leq\tau/2\text{~{}and~{}}\delta<\rho\bigl{(}\theta(D_{0}),\theta(D_{1})\bigr{)}/2.$

If $\alpha<1/2$, then no $\mathrm{STAT}(\tau)$ randomized SQ algorithm can
estimate $\theta$ with precision $\varepsilon\leq\delta$ and probability of
success $1-\alpha$ over $\mathcal{D}$ (no matter how many queries it does).

###### Proof of Theorem G.1.

We prove the contrapositive. For this purpose, assume that a randomized SQ
algorithm $\mathtt{A}\sim\mathcal{A}$ estimates $\theta$ with precision
$\varepsilon\leq\delta$ and probability at least $1-\alpha$ over
$\mathcal{D}$. We will show that $\alpha\geq 1/2$.

Consider the oracle which, given a query $r:\mathbb{R}^{n}\to[-1,1]$ to the
distribution $D\in\mathcal{D}$, returns the answer:

  * •

$\mathrm{a}=\mathop{\mathbb{E}}_{D_{0}}[r]$ if $D=D_{1}$;

  * •

$\mathrm{a}=\mathop{\mathbb{E}}_{D}[r]$ if
$D\in\mathcal{D}\setminus\left\\{{D_{1}}\right\\}$.

As for all query $r:\mathbb{R}^{n}\to[-1,1]$,
$|\mathop{\mathbb{E}}_{D_{0}}[r]-\mathop{\mathbb{E}}_{D_{1}}[r]|\leq
2\mathop{\mathrm{TV}}(D_{0},D_{1})\leq\tau$, it is a valid
$\mathrm{STAT}(\tau)$ oracle. Furthermore, notice that the answers of this
oracle are the same for $D=D_{0}$ and $D=D_{1}$. Writing
$\mathtt{A}=(r_{1},\dots,r_{q},\hat{\theta})\sim\mathcal{A}$, we denote these
answers by $\mathrm{a}_{1},\dots,\mathrm{a}_{q}$. The $\mathrm{a}_{i}$’s are
random variables, with randomness driven by the randomness of
$\mathtt{A}\sim\mathcal{A}$. For $i\in\left\\{{0,1}\right\\}$, let us consider
the event

$B_{i}=\left\\{{\rho\left(\theta(D_{i}),\hat{\theta}(\mathrm{a}_{1},\dots,\mathrm{a}_{q})\right)\leq\varepsilon}\right\\}.$

The fact that $\mathcal{A}$ estimates $\theta$ with precision $\varepsilon$
and probability at least $1-\alpha$ over $\mathcal{D}$ translates into
$\Pr_{\mathtt{A}\sim\mathcal{A}}(B_{i})\geq 1-\alpha$, for
$i\in\left\\{{0,1}\right\\}$. But since
$\varepsilon\leq\delta<\rho(\theta(D_{0}),\theta(D_{1}))/2$, the events
$B_{0}$ and $B_{1}$ are disjoint (i.e. $B_{0}\cap B_{1}=\emptyset$). As a
result,

$\displaystyle 1\geq\Pr_{\mathtt{A}\sim\mathcal{A}}\left(B_{0}\cup
B_{1}\right)=\Pr_{\mathtt{A}\sim\mathcal{A}}(B_{0})+\Pr_{\mathtt{A}\sim\mathcal{A}}(B_{1})\geq
2(1-\alpha),$

which yields $\alpha\geq 1/2$ and concludes the proof. ∎

###  G.2 Computational Lower Bound

This section is dedicated to prove the following Theorem G.2, that provides a
computational lower bound for support estimation in Hausdorff distance. It
involves the generalized notion of metric packing, which is defined right
below.

######  Theorem G.2.

Given a model $\mathcal{D}$ over $\mathbb{R}^{n}$, any randomized SQ algorithm
estimating $M=\mathrm{Supp}(D)\subseteq\mathbb{R}^{n}$ with precision
$\varepsilon$ for the Hausdorff distance, and with probability of success at
least $1-\alpha$, must make at least

$q\geq\frac{\log\bigl{(}(1-\alpha)\mathrm{pk}_{(\mathcal{M},\mathrm{d_{H}})}(\varepsilon)\bigr{)}}{\log(1+\left\lfloor
1/\tau\right\rfloor)}$

queries to $\mathrm{STAT}(\tau)$, where
$\mathcal{M}=\left\\{{\mathrm{Supp}(D),D\in\mathcal{D}}\right\\}$.

Similarly to Section G.1, we put Theorem G.2 in the broader context of SQ
estimation in metric spaces (see Section 2.1), and state the more general
Theorem G.3 below. To this aims, and similarly to the Euclidean case
(Definition B.1), let us recall the definitions of metric packings and
coverings. We let $(\Theta,\rho)$ be a metric space,
$\mathcal{M}\subseteq\Theta$ a subset of $\Theta$, and a radius
$\varepsilon>0$.

  * •

An _$\varepsilon$ -covering_ of $\mathcal{M}$ is a subset
$\left\\{{\theta_{1},\dots,\theta_{k}}\right\\}\subseteq\mathcal{M}$ such that
for all $\theta\in\mathcal{M}$, we have $\min_{1\leq i\leq
k}\rho(\theta,\theta_{i})\leq\varepsilon$. The covering number
$\mathrm{cv}_{(\mathcal{M},\rho)}(\varepsilon)$ of $\mathcal{M}$ at scale
$\varepsilon$ is the smallest cardinality $k$ of such an
$\varepsilon$-covering.

  * •

An _$\varepsilon$ -packing_ of $\mathcal{M}$ is a subset
$\left\\{\theta_{1},\dots,\theta_{k}\right\\}\subseteq\mathcal{M}$ such that
for all $1\leq i<j\leq k$,
$\mathrm{B}_{(\Theta,\rho)}(\theta_{i},\varepsilon)\cap\mathrm{B}_{(\Theta,\rho)}(\theta_{j},\varepsilon)=\emptyset$
(or equivalently $\rho(\theta_{i},\theta_{j})>2\varepsilon$), where
$\mathrm{B}_{(\Theta,\rho)}(\theta,\varepsilon)=\left\\{{\theta^{\prime}\in\Theta,\rho(\theta,\theta^{\prime})\leq\varepsilon}\right\\}$
is the closed ball in $(\Theta,\rho)$. The covering number
$\mathrm{pk}_{(\mathcal{M},\rho)}(\varepsilon)$ of $\mathcal{M}$ at scale
$\varepsilon$ is the largest cardinality $k$ of such an $\varepsilon$-packing.

######  Theorem G.3.

Given a model $\mathcal{D}$ and a parameter of interest
$\theta:\mathcal{D}\to\Theta$ in the metric space $(\Theta,\rho)$, any
randomized SQ algorithm estimating $\theta(D)$ over $\mathcal{D}$ with
precision $\varepsilon$ and probability of success at least $1-\alpha$, must
make at least

$q\geq\frac{\log\bigl{(}(1-\alpha)\mathrm{pk}_{(\theta(\mathcal{D}),\rho)}(\varepsilon)\bigr{)}}{\log(1+\left\lfloor
1/\tau\right\rfloor)}$

queries to $\mathrm{STAT}(\tau)$, where
$\theta(\mathcal{D})=\left\\{{\theta(D),D\in\mathcal{D}}\right\\}$.

###### Proof of Theorem G.2.

Apply Theorem G.3 with parameter of interest $\theta(D)=\mathrm{Supp}(D)$ and
distance $\rho=\mathrm{d_{H}}$. ∎

####  G.2.1 Probabilistic Covering and Packing Number

To prove Theorem G.3, we will use the following notion of probabilistic
covering. Given a set $S$ and an integer $k\geq 0$, we denote by
$\binom{S}{\leq k}$ the set of all subsets of $S$ of cardinality at most $k$.

######  Definition G.2.

Let $(\Theta,\rho)$ be a metric space. We say that a probabilistic measure
$\mu$ over $\binom{\Theta}{\leq d}$ is a probabilistic
$(\varepsilon,\alpha)$-covering of $(\Theta,\rho)$ by $d$ points if for all
$\theta\in\Theta$,

$\Pr_{\mathbf{p}\sim\mu}\left[\theta\in\bigcup_{q\in\mathbf{p}}\mathrm{B}_{(\Theta,\rho)}(q,\varepsilon)\right]\geq
1-\alpha.$

We denote by $\mathrm{cv}_{(\Theta,\rho)}(\varepsilon,\alpha)$ the minimal $d$
such that there is a probabilistic $(\varepsilon,\alpha)$-covering of
$(\Theta,\rho)$ with $d$ points.

This clearly generalizes (deterministic) coverings, since
$\mathrm{cv}_{(\Theta,\rho)}(\varepsilon,\alpha=0)$ coincides with the
standard covering number $\mathrm{cv}_{(\Theta,\rho)}(\varepsilon)$. However,
this quantity might be involved to compute since it involves randomness.
Before proving Theorem G.3, let us show how to lower bound
$\mathrm{cv}_{(\Theta,\rho)}(\varepsilon,\alpha)$ in practice.

######  Theorem G.4.

Let $(\Theta,\rho)$ be a metric space. Assume that there is a probability
measure $\nu$ on $\Theta$ such that for all $q_{1},\dots,q_{\ell}\in\Theta$,

$\nu\left(\bigcup_{i=1}^{\ell}\mathrm{B}_{(\Theta,\rho)}(q_{i},\varepsilon)\right)<1-\alpha.$

Then $\mathrm{cv}_{(\Theta,\rho)}(\varepsilon,\alpha)>\ell$.

###### Proof of Theorem G.4.

Take any probability measure $\mu$ over $\binom{\Theta}{\leq\ell}$, and
consider the map
$f(\mathbf{p},\theta)=\mathbbm{1}_{\cup_{q\in\mathbf{p}}\mathrm{B}_{(\Theta,\rho)}(q,\varepsilon)}(\theta)$
for all $\mathbf{p}\in\binom{\Theta}{\leq\ell}$ and $\theta\in\Theta$. By
assumption, for all fixed $\mathbf{p}\in\binom{\Theta}{\leq\ell}$,

$1-\alpha>\nu\left(\bigcup_{q\in\mathbf{p}}\mathrm{B}_{(\Theta,\rho)}(q,\varepsilon)\right)=\int_{\Theta}f(\mathbf{p},\theta)\nu(d\theta);$

hence, by integration with respect to $\mu(d\mathbf{p})$ and Fubini–Tonelli,

$\displaystyle 1-\alpha$
$\displaystyle>\int_{\binom{\Theta}{\leq\ell}}\left(\int_{\Theta}f(\mathbf{p},\theta)\nu(d\theta)\right)\mu(d\mathbf{p})=\int_{\Theta}\left(\int_{\binom{\Theta}{\leq\ell}}f(\mathbf{p},\theta)\mu(d\mathbf{p})\right)\nu(d\theta).$

As $\nu$ is a probability distribution, this yields the existence of a fixed
$\theta=\theta_{\mu}\in\Theta$ such that

$1-\alpha>\int_{\binom{\Theta}{\leq\ell}}f(\mathbf{p},\theta)\mu(d\mathbf{p})=\Pr_{\mathbf{p}\sim\mu}\left[\theta\in\bigcup_{q\in\mathbf{p}}\mathrm{B}_{(\Theta,\rho)}(q,\varepsilon)\right].$

In other words, we have shown that no probability distribution $\mu$ over
$\binom{\Theta}{\leq\ell}$ can be an $(\varepsilon,\alpha)$-covering of
$(\Theta,\rho)$ (Definition G.2). Hence,
$\mathrm{cv}_{(\Theta,\rho)}(\varepsilon,\alpha)>\ell$. ∎

As a byproduct of Theorem G.4, we can now show that probabilistic coverings
are closely related to the usual notions of metric covering and packing
numbers.

######  Theorem G.5.

Let $(\Theta,\rho)$ be a metric space, and $\alpha<1$. Then,

$\mathrm{cv}_{(\Theta,\rho)}(\varepsilon)\geq\mathrm{cv}_{(\Theta,\rho)}(\varepsilon,\alpha)\geq(1-\alpha)\mathrm{pk}_{(\Theta,\rho)}(\varepsilon).$

###### Proof of Theorem G.5.

If any of the three terms is infinite, then all the terms involved clearly are
infinite, so that the announced bounds hold. Otherwise, any given
$\varepsilon$-covering of $(\Theta,\rho)$ is also a
$(\varepsilon,\alpha)$-covering (where we identify a finite set to the uniform
measure on it), which gives the left-hand bound. For the right-hand bound,
write $k=\mathrm{pk}_{(\Theta,\rho)}(\varepsilon)<\infty$, and let
$\\{\theta_{1},\dots,\theta_{k}\\}$ be an $\varepsilon$-packing of
$(\Theta,\rho)$. That is, for all $i\neq j$,
$\rho(\theta_{i},\theta_{j})>2\varepsilon$.

Take $\nu$ to be the uniform probability distribution over this packing, that
is set $\nu(S)=|\\{\theta_{1},\dots,\theta_{k}\\}\cap S|/k$ for all
$S\subseteq\Theta$. Note that since $\\{\theta_{1},\dots,\theta_{k}\\}$ is an
$\varepsilon$-packing, we have
$\nu\bigl{(}\mathrm{B}_{(\Theta,\rho)}(\theta,\varepsilon)\bigr{)}\leq 1/k$
for all $\theta\in\Theta$, and as a result,

$\nu\left(\bigcup_{i=1}^{\ell}\mathrm{B}_{(\Theta,\rho)}(\theta_{i},\varepsilon)\right)\leq\frac{\ell}{k}$

for all $\theta_{1},\dots,\theta_{\ell}\in\Theta$.

Taking $\ell=\left\lceil(1-\alpha)k\right\rceil-1$, Theorem G.4 implies that
$\mathrm{cv}_{(\Theta,\rho)}(\varepsilon,\alpha)>\left\lceil(1-\alpha)k\right\rceil-1$,
and hence

$\mathrm{cv}_{(\Theta,\rho)}(\varepsilon,\alpha)\geq\left\lceil(1-\alpha)k\right\rceil\geq(1-\alpha)k=(1-\alpha)\mathrm{pk}_{(\Theta,\rho)}(\varepsilon).$

∎

####  G.2.2 Proof of the Computational Lower Bounds for Randomized SQ
Algorithms

We are now in position to prove the lower bounds on (randomized) SQ algorithms
in general metric spaces.

###### Proof of Theorem G.3.

For all $i\in\left\\{{0,\dots,\left\lceil 1/\tau\right\rceil}\right\\}$, write
$L_{i}=\min\left\\{{-1+(2i+1)\tau,1}\right\\}$. The $L_{i}$’s form a
$\tau$-cover of $[-1,1]$, meaning that for all $t\in[-1,1]$, there is a least
one $0\leq i\leq\left\lfloor 1/\tau\right\rfloor$ with $|L_{i}-t|\leq\tau$.
Hence we can define $f:[-1,1]\to[-1,1]$ by $f(t)=L_{i_{0}}$, where $L_{i_{0}}$
is smallest $L_{i}$ such that $|L_{i}-t|\leq\tau$. Note that $f$ takes only
$\left\lfloor 1/\tau\right\rfloor+1$ different values, and that
$|f(t)-t|\leq\tau$ for all $t\in[-1,1]$.

Let us now consider the oracle $\mathsf{O}$ which, given a query
$r:\mathbb{R}^{n}\to[-1,1]$ to the distribution $D$, returns the answer
$\mathrm{a}_{D}(r)=f(\mathop{\mathbb{E}}_{D}[r])$. Roughly speaking, the
oracle discretizes the segment $[-1,1]$ into $\left\lfloor
1/\tau\right\rfloor+1$ points and returns the projection of the correct mean
value $\mathop{\mathbb{E}}_{D}[r]$ onto this discretization. Clearly,
$\mathsf{O}$ is a valid $\mathrm{STAT}(\tau)$ oracle since $|f(t)-t|\leq\tau$
for all $t\in[-1,1]$.

Let $\mathcal{A}$ be a randomized SQ algorithm estimating $\theta$ over
$\mathcal{D}$, and
$\mathtt{A}=(r_{1},\dots,r_{q},\hat{\theta})\sim\mathcal{A}$. Let us write
$d=(\left\lfloor 1/\tau\right\rfloor+1)^{q}$, and consider the random subset
of $\Theta$ given by

$C(\mathtt{A})=\left\\{{\hat{\theta}\biggl{(}\mathrm{a}_{D}(r_{1}),\dots,\mathrm{a}_{D}(r_{q})\biggr{)}}\right\\}_{D\in\mathcal{D}}.$

Note that by construction of the oracle $\mathsf{O}$,
$C(\mathtt{A})\in\binom{\mathcal{D}}{\leq d}$. Let us consider the probability
distribution $\mu$ over $\binom{\mathcal{D}}{\leq d}$ such that the measure of
a set $S$ is equal to $\Pr_{\mathtt{A}\sim\mathcal{A}}[C(\mathtt{A})\in S].$

It is clear that if a deterministic algorithm $\mathtt{A}_{0}$ estimates
$\theta(D)$ with precision $\varepsilon$ using the oracle $\mathsf{O}$, then
$\theta(D)\in\cup_{t\in
C(\mathtt{A}_{0})}\mathrm{B}_{(\Theta,\rho)}(t,\varepsilon)$. As $\mathcal{A}$
estimates $\theta$ with precision $\varepsilon$ and probability at least
$1-\alpha$ over $\mathcal{D}$, this means that $\mu$ is a probabilistic
$(\varepsilon,\alpha)$-covering of $\theta(\mathcal{D})$ with $(\left\lfloor
1/\tau\right\rfloor+1)^{q}$ points (Definition G.2). As a result, by
definition of $\mathrm{cv}_{(\theta(\mathcal{D}),\rho)}(\varepsilon,\alpha)$,
we have $(\left\lfloor
1/\tau\right\rfloor+1)^{q}\geq\mathrm{cv}_{(\theta(\mathcal{D}),\rho)}(\varepsilon,\alpha)$.
Finally, from Theorem G.5 we have
$\mathrm{cv}_{(\theta(\mathcal{D}),\rho)}(\varepsilon,\alpha)\geq(1-\alpha)\mathrm{pk}_{(\theta(\mathcal{D}),\rho)}(\varepsilon)$,
which gives the announced result. ∎

##  Appendix H Lower Bounds for Manifold Models

###  H.1 Diffeomorphisms and Geometric Model Stability

The following result will allow us to build different elements of
$\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ in a simple way, by considering
diffeomorphic smooth perturbations of a base manifold $M_{0}$. Here and below,
$I_{n}$ is the identity map of $\mathbb{R}^{n}$. Given a regular map
$\Phi:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$, $d_{x}\Phi$ and
$d_{x}^{2}\Phi$ stand for its first and second order differentials at
$x\in\mathbb{R}^{n}$.

######  Proposition H.1.

Let $M_{0}\in\mathcal{M}^{{n},{d}}_{2\mathrm{rch}_{\min}}$ and
$\Phi:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be a proper $\mathcal{C}^{2}$
map, i.e. $\lim_{\left\|x\right\|\to\infty}\left\|\Phi(x)\right\|=\infty$. If
$\sup_{x\in\mathbb{R}^{n}}\left\|I_{n}-d_{x}\Phi\right\|_{\mathrm{op}}\leq
1/(10d)$ and
$\sup_{x\in\mathbb{R}^{n}}\left\|d^{2}_{x}\Phi\right\|_{\mathrm{op}}\leq
1/\left(4\mathrm{rch}_{\min}\right)$, then $\Phi$ is a global diffeomorphism,
and $\Phi(M_{0})\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$. Furthermore,
$1/2\leq\mathcal{H}^{d}(\Phi(M_{0}))/\mathcal{H}^{d}(M_{0})\leq 2$.

###### Proof of Proposition H.1.

As $\sup_{x}\left\|d_{x}\Phi-I_{n}\right\|_{\mathrm{op}}<1$, $d_{x}\Phi$ is
invertiblefor all $x\in\mathbb{R}^{n}$. Hence, the inverse function theorem
yields that $\Phi$ is everywhere a local diffeomorphism. As,
$\lim_{\left\|x\right\|\rightarrow\infty}\left\|\Phi(x)\right\|=\infty$ this
diffeomorphism is global by the Hadamard-Cacciopoli theorem [DMGZ94]. In
particular, $\Phi(M_{0})$ is a compact connected $d$-dimensional submanifold
of $\mathbb{R}^{n}$ without boundary. In addition, by Taylor’s theorem, $\Phi$
is Lipschitz with constant
$\sup_{x}\left\|d_{x}\Phi\right\|_{\mathrm{op}}\leq(1+\sup_{x}\left\|I_{n}-d_{x}\Phi\right\|_{\mathrm{op}})\leq
11/10$, $\Phi^{-1}$ is Lipschitz with constant
$\sup_{x}\left\|d_{x}\Phi^{-1}\right\|_{\mathrm{op}}\leq({1-\sup_{x}\left\|I_{n}-d_{x}\Phi\right\|_{\mathrm{op}}})^{-1}\leq
10/9$, and $d\Phi$ is Lipschitz with constant
$\sup_{x}\left\|d^{2}_{x}\Phi\right\|_{\mathrm{op}}\leq
1/(4\mathrm{rch}_{\min})\leq 1/(2\mathrm{rch}_{M_{0}})$. Hence, [Fed59,
Theorem 4.19] yields

$\displaystyle\mathrm{rch}_{\Phi(M)}$
$\displaystyle\geq\frac{(2\mathrm{rch}_{M_{0}})(1-\sup_{x}\left\|I_{n}-d_{x}\Phi\right\|_{\mathrm{op}})^{2}}{\sup_{x}\left\|d^{2}_{x}\Phi\right\|_{\mathrm{op}}(2\mathrm{rch}_{M})+(1+\sup_{x}\left\|I_{n}-d\Phi\right\|_{\mathrm{op}})}\geq(2\mathrm{rch}_{M_{0}})/2\geq\mathrm{rch}_{\min}.$

As a result, we have
$\Phi(M_{0})\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$. For the last
claim, we use the properties of the Hausdorff measure $\mathcal{H}^{d}$ under
Lipschitz maps [ACLZ17, Lemma 6] to get

$\displaystyle\mathcal{H}^{d}(\Phi(M))$
$\displaystyle\leq\sup_{x}\left\|d_{x}\Phi\right\|_{\mathrm{op}}^{d}\mathcal{H}^{d}(M)$
$\displaystyle\leq\left(1+1/(10d)\right)^{d}\mathcal{H}^{d}(M)$
$\displaystyle\leq 2\mathcal{H}^{d}(M),$

and symmetrically,

$\displaystyle\mathcal{H}^{d}(M)$
$\displaystyle\leq\sup_{x}\left\|d_{x}\Phi^{-1}\right\|_{\mathrm{op}}^{d}\mathcal{H}^{d}(\Phi(M))$
$\displaystyle\leq\frac{1}{\left(1-1/(10d)\right)^{d}}\mathcal{H}^{d}(\Phi(M))$
$\displaystyle=2\mathcal{H}^{d}(\Phi(M)),$

which concludes the proof. ∎

Among the smooth perturbations $\Phi:\mathbb{R}^{n}\to\mathbb{R}^{n}$ nearly
preserving $\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$, the following
localized bump-like functions will be of particular interest for deriving
lower bounds.

######  Lemma H.1.

Let $\delta,\eta>0$ be positive reals. Fix
$p_{1},\dots,p_{N}\in\mathbb{R}^{n}$ be such that
$\left\|p_{i}-p_{j}\right\|>2\delta$ for all $i\neq
j\in\left\\{{1,\dots,N}\right\\}$. Given a family of unit vectors
$\mathbf{w}=(w_{i})_{1\leq i\leq N}\in\left(\mathbb{R}^{n}\right)^{N}$, we let
$\Phi_{\mathbf{w}}$ be the function that maps any $x\in\mathbb{R}^{n}$ to

$\displaystyle\Phi_{\mathbf{w}}(x)$
$\displaystyle=x+\eta\left(\sum_{i=1}^{N}\phi\left(\frac{x-p_{i}}{\delta}\right)w_{i}\right),$

where $\phi:\mathbb{R}^{n}\to\mathbb{R}$ the real-valued bump function defined
by

$\displaystyle\phi:\mathbb{R}^{n}$ $\displaystyle\longrightarrow\mathbb{R}$
$\displaystyle y$
$\displaystyle\longmapsto\exp\left(-{\left\|y\right\|^{2}}/{(1-\left\|y\right\|^{2})}\right)\mathbbm{1}_{\mathrm{B}(0,1)}(y).$

Then $\Phi_{\mathbf{w}}$ is $\mathcal{C}^{\infty}$ smooth,
$\lim_{\left\|x\right\|\to\infty}\left\|\Phi_{\mathbf{w}}(x)\right\|=\infty$,
and $\Phi_{\mathbf{w}}$ satisfies
$\sup_{x\in\mathbb{R}^{n}}\left\|x-\Phi_{\mathbf{w}}(x)\right\|\leq\eta$,

$\displaystyle\sup_{x\in\mathbb{R}^{n}}\left\|I_{n}-d_{x}\Phi_{\mathbf{w}}\right\|_{\mathrm{op}}\leq\frac{5\eta}{2\delta}\text{
and
}\sup_{x\in\mathbb{R}^{n}}\left\|d^{2}_{x}\Phi_{\mathbf{w}}\right\|_{\mathrm{op}}\leq\frac{23\eta}{\delta^{2}}.$

###### Proof of Lemma H.1.

Straightforward calculations show that the real-valued map
$\phi:\mathbb{R}^{n}\longrightarrow\mathbb{R}$ is $\mathcal{C}^{\infty}$
smooth over $\mathbb{R}^{n}$, equals to $0$ outside $\mathrm{B}(0,1)$, and
satisfies $0\leq\phi\leq 1$, $\phi(0)=1$,

$\displaystyle\sup_{y\in\mathrm{B}(0,1)}\left\|d_{y}\phi\right\|\leq 5/2\text{
and }\sup_{y\in\mathrm{B}(0,1)}\left\|d_{y}^{2}\phi\right\|_{\mathrm{op}}\leq
23.$

By composition and linear combination of $\mathcal{C}^{\infty}$ smooth
functions, $\Phi_{\mathbf{w}}$ is therefore $\mathcal{C}^{\infty}$ smooth.
Also, $\Phi_{\mathbf{w}}$ coincides with the identity map outside the compact
set $\cup_{i=1}^{N}\mathrm{B}(p_{i},\delta)$. Furthermore, for $i\neq
j\in\left\\{{1,\dots,N}\right\\}$,
$\mathrm{B}(p_{i},\delta)\cap\mathrm{B}(p_{j},\delta)=\emptyset$, since
$\left\|p_{i}-p_{j}\right\|>2\delta$. Therefore, if
$x\in\mathrm{B}(p_{i},\delta)$, we have
$\Phi_{\mathbf{w}}(x)=x+\eta\phi\left(\frac{x-p_{i}}{\delta}\right)w_{i}$.
This directly gives
$\sup_{x\in\mathbb{R}^{n}}\left\|x-\Phi_{\mathbf{w}}(x)\right\|\leq\eta$, and
by chain rule,

$\displaystyle\sup_{x\in\mathbb{R}^{n}}\left\|I_{n}-d_{x}\Phi_{\mathbf{w}}\right\|_{\mathrm{op}}$
$\displaystyle=\max_{1\leq i\leq
N}\sup_{x\in\mathrm{B}(p_{i},\delta)}\eta\left\|d_{x}\left(\phi\left(\frac{\cdot-
p_{i}}{\delta}\right)w_{i}\right)\right\|_{\mathrm{op}}$
$\displaystyle=\max_{1\leq i\leq
N}\sup_{y\in\mathrm{B}(0,1)}\left\|w_{i}(d_{y}\phi)^{\top}\right\|_{\mathrm{op}}\frac{\eta}{\delta}$
$\displaystyle=\sup_{y\in\mathrm{B}(0,1)}\left\|d_{y}\phi\right\|\frac{\eta}{\delta}$
$\displaystyle\leq\frac{5\eta}{2\delta},$

and

$\displaystyle\sup_{x\in\mathbb{R}^{n}}\left\|d_{x}^{2}\Phi_{\mathbf{w}}\right\|_{\mathrm{op}}$
$\displaystyle=\max_{1\leq i\leq
N}\sup_{y\in\mathrm{B}(0,1)}\left\|w_{i}d_{y}^{2}\phi\right\|_{\mathrm{op}}\frac{\eta}{\delta^{2}}$
$\displaystyle\leq\frac{23\eta}{\delta^{2}},$

which concludes the proof. ∎

###  H.2 Building a Large-Volume Submanifold with Small Euclidean Diameter

The proofs of Theorems 5.5 and 5.6 will involve the construction of
submanifolds $M\subseteq\mathbb{R}^{n}$ with prescribed and possibly large
volume $\mathcal{H}^{d}(M)$. Informally, this will enable us to build
hypotheses and packings with large cardinality by local variations of it (see
Propositions H.3 and H.5) under nearly minimal assumptions on $f_{\min}$
(which can be seen as an inverse volume, for uniform distributions). For the
reasons mentioned in Section 2.2.3, one easily checks that the volume of
$M\in\mathrm{B}(0,R)\sqcap\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ can
neither be too small nor too large, when $\mathrm{rch}_{\min}$ and $R$ are
fixed (Proposition B.5). Conversely, this section is devoted to prove the
_existence_ of submanifolds
$M\in\mathrm{B}(0,R)\sqcap\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ that
nearly achieve the minimum and maximum possible such volumes given by
Proposition B.5.

####  H.2.1 The Statement

Namely, the goal of Section H.2 is to prove the following result.

######  Proposition H.2.

Assume that $\mathrm{rch}_{\min}\leq R/36$. Writing
$C_{d}^{\prime}=9(2^{2d+1}\sigma_{d-1})$, let $\mathcal{V}>0$ be such that

$1\leq\frac{\mathcal{V}}{C_{d}^{\prime}\mathrm{rch}_{\min}^{d}}\leq\max_{1\leq
k\leq n}\left(\frac{R}{48\mathrm{rch}_{\min}\sqrt{k}}\right)^{k}.$

Then there exists $M_{0}\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ such
that $M_{0}\subseteq\mathrm{B}(0,R)$ and

$\displaystyle\mathcal{V}/24\leq\mathcal{H}^{d}(M_{0})\leq\mathcal{V}.$

Informally, in codimension one (i.e. $D=d+1$), the manifold $M_{0}$ of
Proposition H.2 can be though of as the boundary of the offset of a Hilbert
curve in $\mathrm{B}(0,R)$ of prescribed length. This intuition, however, is
only limited to codimension one, and requires extra technical developments for
general $d<D$.

###### Proof of Proposition H.2.

Consider the discrete grid $G_{0}$ in $\mathbb{R}^{n}$ centered at
$0\in\mathbb{R}^{n}$, with vertices
$\left(24\mathrm{rch}_{\min}\mathbb{Z}^{n}\right)\cap\mathrm{B}(0,R/2)$, and
composed of hypercubes of side-length $24\mathrm{rch}_{\min}$. By considering
a $k_{0}$-dimensional sub-grid parallel to the axes, we see that the grid
$G_{0}$ contains a square grid $G$ with side cardinality
$\kappa=\left\lceil\frac{R/2}{24\mathrm{rch}_{\min}\sqrt{k_{0}}}\right\rceil$,
where $k_{0}$ belongs to $\operatornamewithlimits{argmax}_{1\leq k\leq
n}\left(\frac{R}{48\mathrm{rch}_{\min}\sqrt{k}}\right)^{k}$. Let us write
$\ell=\left\lfloor\mathcal{V}/(C_{d}^{\prime}\mathrm{rch}_{\min}^{d})\right\rfloor$.
By assumption on $\mathcal{V}$, $\mathrm{rch}_{\min}$ and $R$, we have

$\displaystyle
1\leq\ell\leq\frac{\mathcal{V}}{C_{d}^{\prime}\mathrm{rch}_{\min}^{d}}\leq\max_{1\leq
k\leq
n}\left(\frac{R}{48\mathrm{rch}_{\min}\sqrt{k}}\right)^{k}\leq\kappa^{k_{0}}.$

Hence, Lemma H.4 asserts that there exists a connected open simple path
$L_{n}(\ell)$ in $G\subseteq G_{0}$ with length $|L_{n}(\ell)|=\ell$.
Furthermore, Lemma H.3 applied with reach parameter $2\mathrm{rch}_{\min}$
provides us with a closed $d$-dimensional submanifold $M_{0}^{\prime}$ of
class $C^{1,1}$ such that $M_{0}^{\prime}=M(L_{n}(\ell))\subseteq
G^{12\mathrm{rch}_{\min}}\subseteq\mathrm{B}(0,R/2)^{12\mathrm{rch}_{\min}}\subseteq\mathrm{B}(0,2R/3)$
since $\mathrm{rch}_{\min}\leq R/36$, reach $\mathrm{rch}_{M_{0}^{\prime}}\geq
2\mathrm{rch}_{\min}$. Furthermore, writing $C_{d}=9(2^{d}\sigma_{d-1})$ for
the constant of Lemma H.3, we also have

$\displaystyle\mathcal{H}^{d}(M_{0}^{\prime})$
$\displaystyle\leq(C_{d}(2\mathrm{rch}_{\min})^{d})|L_{n}(\ell)|$
$\displaystyle\leq(C_{d}(2\mathrm{rch}_{\min})^{d})\frac{\mathcal{V}}{C_{d}^{\prime}\mathrm{rch}_{\min}^{d}}$
$\displaystyle\leq\mathcal{V}/2,$

and

$\displaystyle\mathcal{H}^{d}(M_{0}^{\prime})$
$\displaystyle\geq(C_{d}(2\mathrm{rch}_{\min})^{d}/3)|L_{n}(\ell)|$
$\displaystyle\geq(C_{d}(2\mathrm{rch}_{\min})^{d}/3)\frac{\mathcal{V}}{2C_{d}^{\prime}\mathrm{rch}_{\min}^{d}}$
$\displaystyle=\mathcal{V}/12,$

where we used that $\left\lfloor t\right\rfloor\geq t/2$ for all $t\geq 1$ To
conclude the proof, we use the density of $\mathcal{C}^{2}$ submanifolds in
the space of $\mathcal{C}^{1,1}$ submanifolds to obtain a closed
$d$-dimensional submanifold $M_{0}$ of class $\mathcal{C}^{2}$ such that
$\mathrm{rch}_{M_{0}}\geq\mathrm{rch}_{M_{0}^{\prime}}/2\geq\mathrm{rch}_{\min}$,
$\mathrm{d_{H}}(M_{0},M_{0}^{\prime})\leq\mathrm{rch}_{\min}$ (and hence
$M_{0}\subset\mathrm{B}(0,2R/3+\mathrm{rch}_{\min})\subset\mathrm{B}(0,R)$),
and $1/2\leq\mathcal{H}^{d}(M_{0})/\mathcal{H}^{d}(M_{0}^{\prime})\leq 2$ (and
hence $\mathcal{V}/24\leq\mathcal{H}^{d}(M_{0})\leq\mathcal{V}$). ∎

####  H.2.2 Widget Gluing: From Paths on the Discrete Grid to Manifolds

######  Lemma H.2.

Given $\mathrm{rch}_{\min}>0$ and $d\geq 1$, there exist four $d$-dimensional
$\mathcal{C}^{1,1}$-submanifolds with boundary:

$M_{E},M_{S},M_{TB}\subseteq[-6\mathrm{rch}_{\min},6\mathrm{rch}_{\min}]^{d+1}$
and $M_{NB}\subseteq[-6\mathrm{rch}_{\min},6\mathrm{rch}_{\min}]^{d+2}$,

called respectively _end_ , _straight_ , _tangent bend_ and _normal bend_
widgets (see Figure 3), that:

  * •

are smooth:
$\mathrm{rch}_{M_{E}},\mathrm{rch}_{M_{S}},\mathrm{rch}_{M_{TB}},\mathrm{rch}_{M_{NB}}\geq\mathrm{rch}_{\min}$;

  * •

have the following topologies:

    * –

$M_{E}$ is isotopic to a $d$-ball $\mathrm{B}_{d}(0,1)$,

    * –

$M_{S}$, $M_{TB}$ and $M_{NB}$ are isotopic to a $d$-cylinder
$\mathcal{S}^{d-1}\times[0,1]$;

  * •

are linkable: writing $s=6\mathrm{rch}_{\min}$, we have

    * –

For the tip widget $M_{E}$:

      * *

$M_{E}\cap\left([-s/2,s/2]^{d+1}\right)^{c}=M_{E}\cap\left([s/2,s]\times\mathbb{R}^{d}\right)=[s/2,s]\times\mathcal{S}^{d-1}(0,s/3).$

    * –

For the straight widget $M_{S}$:

      * *

$M_{S}\cap\left([-s/2,s/2]^{d+1}\right)^{c}=M_{S}\cap\left(\left([-s,-s/2]\times\mathbb{R}^{d}\right)\cup\left([s/2,s]\times\mathbb{R}^{d}\right)\right),$

      * *

$M_{S}\cap\left([-s,-s/2]\times\mathbb{R}^{d}\right)=[-s,-s/2]\times\mathcal{S}^{d-1}(0,s/3)$,

      * *

$M_{S}\cap\left([s/2,s]\times\mathbb{R}^{d}\right)=[s/2,s]\times\mathcal{S}^{d-1}(0,s/3).$

    * –

For the tangent bend widget $M_{TB}$:

      * *

$M_{TB}\cap\left([-s/2,s/2]^{d+1}\right)^{c}=M_{TB}\cap\left(\left([-s,-s/2]\times\mathbb{R}^{d}\right)\cup\left(\mathbb{R}^{d}\times[-s,-s/2]\right)\right),$

      * *

$M_{TB}\cap\left([-s,-s/2]\times\mathbb{R}^{d}\right)=[-s,-s/2]\times\mathcal{S}^{d-1}(0,s/3)$,

      * *

$M_{TB}\cap\left(\mathbb{R}^{d}\times[-s,-s/2]\right)=\mathcal{S}^{d-1}(0,s/3)\times[-s,-s/2].$

    * –

For the normal bend widget $M_{NB}$:

      * *

$M_{NB}\cap\left([-s/2,s/2]^{d+2}\right)^{c}=M_{NB}\cap\left(\left([-s,-s/2]\times\mathbb{R}^{d}\times\left\\{{0}\right\\}\right)\cup\left(\left\\{{0}\right\\}\times\mathbb{R}^{d}\times[-s,-s/2]\right)\right),$

      * *

$M_{NB}\cap\left([-s,-s/2]\times\mathbb{R}^{d}\times\left\\{{0}\right\\}\right)=[-s,-s/2]\times\mathcal{S}^{d-1}(0,s/3)\times\left\\{{0}\right\\}$,

      * *

$M_{NB}\cap\left(\left\\{{0}\right\\}\times\mathbb{R}^{d}\times[-s,-s/2]\right)=\left\\{{0}\right\\}\times\mathcal{S}^{d-1}(0,s/3)\times[-s,-s/2].$

Furthermore,

$(C_{d}/3)\mathrm{rch}_{\min}^{d}\leq\mathcal{H}^{d}(M_{E}),\mathcal{H}^{d}(M_{S}),\mathcal{H}^{d}(M_{TB}),\mathcal{H}^{d}(M_{NB})\leq
C_{d}\mathrm{rch}_{\min}^{d},$

where $C_{d}=9(2^{d}\sigma_{d-1})$ depends only on $d$.

(a)  End widget $M_{E}$.

(b)  Straight widget $M_{S}$.

(c)  Tangent Bend widget $M_{TB}$.

(d)  Normal Bend widget $M_{NB}$.

Figure 3:  The widgets built in Lemma H.2 and used in the proof of Lemma H.3.

###### Proof of Lemma H.2.

First notice that by homogeneity, we can carry out the construction in the
unit hypercubes $[-1,1]^{d+1}$ (respectively $[-1,1]^{d+2}$) and conclude by
applying an homothetic transformation. Indeed, for all closed set
$K\subseteq\mathbb{R}^{n}$ and $\lambda\geq 0$, $\mathrm{rch}_{\lambda
K}=\lambda\mathrm{rch}_{K}$ and $\mathcal{H}^{d}(\lambda
K)=\lambda^{d}\mathcal{H}^{d}(K)$.

  * •

End widget: the idea is to glue in a $\mathcal{C}^{2}$ way a half $d$-sphere
with a $d$-cylinder. Namely, let us consider

$\displaystyle M_{E}^{(0)}$
$\displaystyle=\left(\mathcal{S}^{d}(0,1/3)\cap\left([-1,0]\times[-1,1]^{d}\right)\right)\cup\left([0,1]\times\mathcal{S}^{d-1}(0,1/3)\right).$

Elementary calculations yield the intersections

$M_{E}^{(0)}\cap\left([-1/2,1/2]^{d+1}\right)^{c}=M_{E}^{(0)}\cap\left([1/2,1]\times\mathbb{R}^{d}\right)=[1/2,1]\times\mathcal{S}^{d-1}(0,1/3).$

In addition, its medial axis is
$\mathrm{Med}(M_{E}^{(0)})=[0,1]\times\left\\{{0}\right\\}^{d}$, so that

$\mathrm{rch}_{M_{E}^{(0)}}=\inf_{z\in\mathrm{Med}(M_{E}^{(0)})}\mathrm{d}(z,M_{E}^{(0)})=1/3.$

Finally, $M_{E}^{(0)}$ is isotopic to the half $d$-sphere
$\mathcal{S}^{d}(0,1/3)\cap\left([-1,0]\times[-1,1]^{d}\right)$, or
equivalently to a $d$-ball.

  * •

Straight widget: a simple $d$-cylinder satisfies our requirements. Similarly
as above, the set

$\displaystyle M_{S}^{(0)}$
$\displaystyle=[-1,1]\times\mathcal{S}^{d-1}(0,1/3)$

clearly is (isotopic to) a $d$-cylinder, has reach
$\mathrm{rch}_{M_{S}^{(0)}}=1/3$, and all the announced intersection
properties with $s=1$.

  * •

Tangent Bend widget: we will glue two orthogonal straight $d$-cylinders via a
smoothly rotating $(d-1)$-sphere. More precisely, consider the $d$-cylinders
$C_{1}=\mathcal{S}^{d-1}(0,1/3)\times[-1,-1/2]$ and
$C_{2}=[-1,-1/2]\times\mathcal{S}^{d-1}(0,1/3)$. We will connect smoothly
their tips, which are the $(d-1)$-spheres
$S_{1}=\mathcal{S}^{d-1}(0,1/3)\times\left\\{{-1/2}\right\\}\subseteq C_{1}$
and $S_{2}=\left\\{{-1/2}\right\\}\times\mathcal{S}^{d-1}(0,1/3)\subseteq
C_{2}$ of same radius. To this aim, take the trajectory of $S_{1}$ via the
affine rotations of center $x_{c}=(-1/2,0_{\mathbb{R}^{d-1}},-1/2)$ and linear
parts

$\displaystyle R_{\theta}=\begin{pmatrix}\cos\theta&0&\cdots&0&-\sin\theta\\\
0&1&\cdots&0&0\\\ \vdots&&\ddots&&\vdots\\\ 0&0&\cdots&1&0\\\
\sin\theta&0&\cdots&0&\cos\theta\end{pmatrix}\in\mathbb{R}^{(d+1)\times(d+1)},$

when $\theta$ varies in $[0,\pi/2]$. Hence, letting
$f_{\theta}(x)=x_{c}+R_{\theta}(x-x_{c})$, we have $f_{0}(S_{1})=S_{1}$,
$f_{\pi/2}(S_{1})=S_{2}$. In addition, for all $\theta\in[0,\pi/2]$ and
$x\in[-1/2,1/2]^{d}\times\left\\{{-1/2}\right\\}$, we have
$f_{\theta}(x)\in[-1/2,1/2]^{d+1}$. Hence, letting

$\displaystyle
M_{TB}^{(0)}=C_{1}\cup\biggl{(}\bigcup_{0\leq\theta\leq\pi/2}f_{\theta}(S_{1})\biggr{)}\cup
C_{2},$

we directly get that $M_{TB}^{(0)}$ is isotopic to a $d$-cylinder, and that it
satisfies all the announced intersection properties with $s=1$. To conclude,
by symmetry, the medial axis of this widget writes as

$\displaystyle\mathrm{Med}(M_{TB}^{(0)})$
$\displaystyle=\left\\{{0}\right\\}^{d}\times[-1,-1/2]\cup\biggl{(}x_{c}+\bigcup_{t\geq
0}(-t,0_{\mathbb{R}^{d-1}},-t)\biggr{)}\cup[-1,-1/2]\times\left\\{{0}\right\\}^{d},$

so that straightforward calculations yield
$\mathrm{rch}_{M_{TB}^{(0)}}=\min\left\\{{1/3,\mathrm{d}(x_{c},M_{TB}^{(0)})}\right\\}=1/6$.

  * •

Normal Bend widget: same as for the tangent bend widget, we glue the two
orthogonal straight $d$-cylinders
$C_{1}=\left\\{{0}\right\\}\times\mathcal{S}^{d-1}(0,1/3)\times[-1,-1/2]$ and
$C_{2}=[-1,-1/2]\times\mathcal{S}^{d-1}(0,1/3)\times\left\\{{0}\right\\}$. via
their respective tips,
$S_{1}=\left\\{{0}\right\\}\times\mathcal{S}^{d-1}(0,1/3)\times\left\\{{-1/2}\right\\}\subseteq
C_{1}$ and
$S_{2}=\left\\{{-1/2}\right\\}\times\mathcal{S}^{d-1}(0,1/3)\left\\{{0}\right\\}\subseteq
C_{2}$. To this aim, take trajectory of $S_{1}$ via the affine rotation of
center $x_{c}=(-1/2,0_{\mathbb{R}^{d}},-1/2)$ and linear parts
$R_{\theta}\in\mathbb{R}^{(d+2)\times(d+2)}$ for $\theta\in[0,\pi/2]$. As
before, letting $f_{\theta}(x)=x_{c}+R_{\theta}(x-x_{c})$, we have
$f_{0}(S_{1})=S_{1}$, $f_{\pi/2}(S_{1})=S_{2}$. Also, for all
$\theta\in[0,\pi/2]$ and
$x\in\left\\{{0}\right\\}\times[-1/2,1/2]^{d}\times\left\\{{-1/2}\right\\}$,
we have $f_{\theta}(x)\in[-1/2,1/2]^{d+1}$. Hence, letting

$\displaystyle
M_{NB}^{(0)}=C_{1}\cup\biggl{(}\bigcup_{0\leq\theta\leq\pi/2}f_{\theta}(S_{1})\biggr{)}\cup
C_{2},$

we get the announced results with $s=1$, and in a similar way as above,
$\mathrm{rch}_{M_{NB}^{(0)}}=\min\left\\{{1/3,1/2}\right\\}=1/3$.

Also one easily checks in all the four above cases that

$\frac{\sigma_{d-1}/3^{d-2}}{3}\leq\mathcal{H}^{d}(M_{E}^{(0)}),\mathcal{H}^{d}(M_{S}^{(0)}),\mathcal{H}^{d}(M_{TB}^{(0)}),\mathcal{H}^{d}(M_{NB}^{(0)})\leq\sigma_{d-1}/3^{d-2}.$

Finally, letting

$C^{-1}=\min\left\\{{\mathrm{rch}_{M_{E}^{(0)}},\mathrm{rch}_{M_{S}^{(0)}},\mathrm{rch}_{M_{TB}^{(0)}},\mathrm{rch}_{M_{NB}^{(0)}}}\right\\}=1/6$

and considering the dilations $M_{E}=(C\mathrm{rch}_{\min})M_{E}^{(0)}$,
$M_{S}=(C\mathrm{rch}_{\min})M_{S}^{(0)}$,
$M_{TB}=(C\mathrm{rch}_{\min})M_{TB}^{(0)}$ and
$M_{NB}=(C\mathrm{rch}_{\min})M_{NB}^{(0)}$ yields the result by homogeneity,
with $C_{d}=C^{d}\sigma_{d-1}/3^{d-2}=9(2^{d}\sigma_{d-1})$. ∎

######  Lemma H.3.

Let $G$ be a discrete grid in $\mathbb{R}^{n}$ composed of hypercubes of side-
length $12\mathrm{rch}_{\min}$. Then any connected open simple path $L$ in $G$
(see Lemma H.4) defines a $\mathcal{C}^{1,1}$ $d$-dimensional closed
submanifold, denoted by $M(L)$, such that:

  * •

$M(L)\subseteq G^{6\mathrm{rch}_{\min}}$;

  * •

$M(L)\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$;

  * •

$C_{d}/3\leq\dfrac{\mathcal{H}^{d}(M(L))}{|L|\mathrm{rch}_{\min}^{d}}\leq
C_{d}$, where $C_{d}$ is the constant of Lemma H.2;

  * •

If $L$ and $L^{\prime}$ are two different such paths in $G$,

$\displaystyle\mathrm{d_{H}}(M(L),M(L^{\prime}))>2\mathrm{rch}_{\min}.$

######  Remark H.1.

The construction of Lemma H.3 shows that, given one discrete path $L$, one
could actually define several different manifolds $M(L)$ with the same
properties. We will not exploit this fact as the construction is enough for
our purpose.

###### Proof of Lemma H.3.

For short, we let $s=6\mathrm{rch}_{\min}$. Let $L$ be a fixed connected open
simple path on $G$. If $|L|=1$, take $M(L)$ to be a $d$-sphere of radius
$2\mathrm{rch}_{\min}$ centered at the only vertex of $L$. Assuming now that
$|L|\geq 2$, we will build $M(L)$ iteratively by adding appropriate widgets of
Lemma H.2 along the consecutive vertices that $L$ goes through. We pick one of
the two degree $1$ vertices (endpoints) of $L$ arbitrarily, and denote the
consecutive vertices of $L$ as $x_{1},\dots,x_{[L|-1}$.

  1. (i)

The path $L$ has exactly one edge at $x_{0}$, called $v^{+}_{0}$, which is
parallel to the axes of $\mathbb{R}^{n}$ since $G$ is the square grid. In the
cube $x_{0}+[-6\mathrm{rch}_{\min},6\mathrm{rch}_{\min}]^{n}$, we define
$M(L)$ to coincide with the End widget
$M_{E}\times\left\\{{0}\right\\}^{n-(d+1)}$, rotated in the
$(e_{1},v^{+}_{0})$ plane so that $-e_{1}$ is sent on $v^{+}_{0}$. In this
first cube, $M(L)$ hence presents a $d$-cylinder, obtained by a rotation of
$[-s,-s/2]\times\mathcal{S}^{d-1}(0,s/3)\times\left\\{{0}\right\\}^{n-(d+1)}$
around $x_{0}$, and pointing towards $v^{+}_{0}$. Let us call this cylinder
$C^{+}_{0}$.

  2. (ii)

Assume now that we have visited the consecutive vertices $x_{0},\dots,x_{k-1}$
of $L$, for some $k\geq 1$, and that in the cube around $x_{k-1}$, $M(L)$
presents a cylinder $C^{+}_{k-1}$ in the direction $v^{+}_{k-1}$. If $x_{k}$
is not the other endpoint of $L$, there are exactly two edges at $x_{k}$,
represented by the axis-parallel vectors
$v^{-}_{k}=(x_{k-1}-x_{k})=-v^{+}_{k-1}$ and $v^{+}_{k}=(x_{k+1}-x_{k})$.
There are three possible cases depending on the turn that $L$ takes at
$x_{k}$:

    1. (a)

If $v^{-}_{k}$ and $v^{+}_{k}$ are aligned, take
$M(L)\cap\left(x_{k}+[-s,s]^{n}\right)$ to coincide with the Straight widget
$M_{S}\times\left\\{{0}\right\\}^{n-(d+1)}$, rotated in the
$\\{e_{1},v^{+}_{k}\\}$-plane so that $e_{1}$ is sent on $v^{+}_{k}$.

    2. (b)

If $v^{+}_{k}$ belongs to the $(d+1)$-plane spanned by $C^{+}_{k-1}$ but
$v^{-}_{k}$ and $v^{+}_{k}$ are not aligned, proceed similarly by rotating the
Tangent Bend widget $M_{TB}\times\left\\{{0}\right\\}^{n-(d+1)}$ so that
$(e_{1},e_{d+1})$ is sent on $(-v^{-}_{k-1},v^{+}_{k})$.

    3. (c)

Otherwise, if $v^{+}_{k}$ does not belong to the $(d+1)$-plane spanned by
$C^{+}_{k-1}$, then $\\{v^{+}_{k},C^{+}_{k-1}\\}$ defines a $(d+2)$-plane.
Hence, we proceed similarly by rotating the Normal Bend widget
$M_{NB}\times\left\\{{0}\right\\}^{n-(d+2)}$ so that $(e_{1},e_{d+2})$ is sent
on $(-v^{-}_{k-1},v^{+}_{k})$. Note that this case can only occur if $n\geq
d+2$.

  3. (iii)

If we reached the other endpoint of $L$ ($k=|L|-1$), add a rotated End widget
oriented in the direction of $C^{+}_{k-1}$.

Now that the construction of $M(L)$ has been carried out, let us move to its
claimed properties.

  * •

By construction of the widgets and the fact that all of them are centered at
points of the grid $G$, $M(L)$ is included in the offset of $G$ of radius
$6\mathrm{rch}_{\min}$.

  * •

By induction on the length of the path, it is clear that the union of the
straight and bend widgets (without the ends) is isotopic to a cylinder
$\mathcal{S}^{d-1}(0,1)\times[0,1]$. As a result, adding the two end widgets
at the endpoints of the path yields that $M(L)$ is isotopic to a
$d$-dimensional sphere $\mathcal{S}^{d}(0,1)$. It is also clear that $M(L)$
connected, by connectedness of $L$. In particular, $M(L)$ is a compact
connected $d$-dimensional submanifold of $\mathbb{R}^{n}$ without boundary.

What remains to be proved is that
$\mathrm{rch}_{M(L)}\geq\mathrm{rch}_{\min}$. To see this, notice that by
construction, the widgets connect smoothly through sections of facing straight
cylinders $C^{\pm}=\mathcal{S}^{d-1}(0,s/3)\times[0,\pm
s/2]\times\left\\{{0}\right\\}^{n-(d+1)}$ (rotated), which are included in the
boxes $[-s/2,s/2]^{n}$ centered a the midpoints of the grid. Apart from these
connected ingoing and outgoing cylinders, the widgets are included in boxes
$[-s/2,s/2]^{n}$, which are separated by a distance $s$. Hence, if two points
$x,y\in M(L)$ are such that $\left\|y-x\right\|\leq s/2$, then they must
belong to either the same widget or the same connecting cylinder $C^{-}\cup
C^{+}$. As a result, from [Fed59, Theorem 4.18] and the fact that
$\mathrm{d}(y-x,T_{x}M(L))\leq\left\|y-x\right\|$ for all $x\in M(L)$, we get

$\displaystyle\mathrm{rch}_{M(L)}$ $\displaystyle=\inf_{x\neq y\in
M(L)}\frac{\left\|y-x\right\|^{2}}{2\mathrm{d}(y-x,T_{x}M(L))}$
$\displaystyle=\min\left\\{{\inf_{\begin{subarray}{c}x,y\in M(L)\\\
\left\|y-x\right\|\geq
s/2\end{subarray}}\frac{\left\|y-x\right\|^{2}}{2\mathrm{d}(y-x,T_{x}M(L))},\inf_{\begin{subarray}{c}x\neq
y\in M(L)\\\ \left\|y-x\right\|\leq
s/2\end{subarray}}\frac{\left\|y-x\right\|^{2}}{2\mathrm{d}(y-x,T_{x}M(L))}}\right\\}$
$\displaystyle\geq\min\left\\{{s/4,\min\left\\{{\mathrm{rch}_{M_{E}},\mathrm{rch}_{M_{S}},\mathrm{rch}_{M_{TB}},\mathrm{rch}_{M_{NB}}}\right\\}}\right\\}$
$\displaystyle\geq\min\left\\{{6\mathrm{rch}_{\min}/4,\mathrm{rch}_{\min}}\right\\}$
$\displaystyle=\mathrm{rch}_{\min},$

which ends proving that $M(L)\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$.

  * •

As $M(L)$ is the union of $|L|$ of the widgets defined in Lemma H.2, it
follows

$\displaystyle\mathcal{H}^{d}(M(L))$
$\displaystyle\leq|L|\max\left\\{{\mathcal{H}^{d}(M_{E}),\mathcal{H}^{d}(M_{S}),\mathcal{H}^{d}(M_{TB}),\mathcal{H}^{d}(M_{NB})}\right\\}$
$\displaystyle\leq|L|C_{d}\mathrm{rch}_{\min}^{d},$

and similarly, as the intersection of the consecutive widgets (i.e.
$(d-1)$-spheres) is $\mathcal{H}^{d}$-negligible, we have

$\displaystyle\mathcal{H}^{d}(M(L))$
$\displaystyle\geq|L|\min\left\\{{\mathcal{H}^{d}(M_{E}),\mathcal{H}^{d}(M_{S}),\mathcal{H}^{d}(M_{TB}),\mathcal{H}^{d}(M_{NB})}\right\\}$
$\displaystyle\geq|L|(C_{d}/3)\mathrm{rch}_{\min}^{d}.$

  * •

Let us now fix two different connected open simple paths $L$ and $L^{\prime}$
in $G$. Since $L\neq L^{\prime}$, $L$ passes through a vertex, say
$x_{0}\in\mathbb{R}^{n}$, where $L^{\prime}$ doesn’t. Regardless of the widget
used at $x_{0}$ to build $M(L)$, this widget contains, up to rotation centered
at $x_{0}$, the set
$x_{0}+\left\\{{-s/2}\right\\}\times\mathcal{S}^{d-1}(0,s/3)\times\left\\{{0}\right\\}^{n-(d+1)}$.
As a result, $\mathrm{d}(x_{0},M(L))\leq\sqrt{(s/2)^{2}+(s/3)^{2}}$. On the
other hand, $M(L^{\prime})$ does not intersect the cube $x_{0}+[-s,s]^{n}$, so
$\mathrm{d}(x_{0},M(L^{\prime}))\geq s$. Finally, we get

$\displaystyle\mathrm{d_{H}}(M(L),M(L^{\prime}))$
$\displaystyle=\sup_{x\in\mathbb{R}^{n}}\left|\mathrm{d}(x,M(L^{\prime}))-\mathrm{d}(x,M(L))\right|$
$\displaystyle\geq\left|\mathrm{d}(x_{0},M(L^{\prime}))-\mathrm{d}(x_{0},M(L))\right|$
$\displaystyle\geq s-\sqrt{(s/2)^{2}+(s/3)^{2}}$
$\displaystyle=6(1-\sqrt{13}/6)\mathrm{rch}_{\min}$
$\displaystyle>2\mathrm{rch}_{\min},$

which concludes the proof.

∎

####  H.2.3 Existence of Long Paths on the Grid

In order to complete the construction of Proposition H.2, we need the
existence of paths of prescribed length over the $n$-dimensional discrete
grid. Although standard, we include this construction for sake of
completeness.

######  Lemma H.4.

Let $\kappa\geq 1$ be an integer and consider the square grid graph $G_{n}$ on
$\left\\{{1,\dots,\kappa}\right\\}^{n}$. Then for all
$\ell\in\left\\{{1,\dots,\kappa^{n}}\right\\}$, there exists a connected open
simple path $L_{n}(\ell)$ of length $\ell$ in $G_{n}$. That is, $L_{n}(\ell)$
is a subgraph of $G_{n}$ such that:

  * •

$L_{n}(\ell)$ is connected;

  * •

$L_{n}(\ell)$ has vertex cardinality $\ell$;

  * •

if $\ell\geq 2$, $L_{n}(\ell)$ has maximum degree $2$, and exactly two
vertices with degree $1$.

###### Proof of Lemma H.4.

For $\kappa=1$, $G_{n}$ consists of a single point, so that the result is
trivial. We hence assume that $\kappa\geq 2$. Let us first build the paths
$L_{n}=L_{n}(\kappa^{n})$ by induction on $n$. For $n=1$, simply take $L_{1}$
to be the full graph $G_{n}$. We orientate $L_{1}$ by enumerating its adjacent
vertices in order: $L^{\rightarrow}_{1}[i]=i$ for all $1\leq i\leq\kappa$.
Given an orientation $L^{\rightarrow}$ of some path $L$ in $G_{n}$, we also
let $L^{\leftarrow}[i]=L^{\rightarrow}[|L|-i]$ denote its backwards
orientation. Now, assume that we have built $L_{n}$ for some $n\geq 1$,
together with an orientation $L^{\rightarrow}_{n}$. To describe $L_{n+1}$, we
list an orientation $L_{n+1}^{\rightarrow}$ of it: an edge of $G_{n}$ hence
belongs to $L_{n}$ if an only if it joins two consecutive vertices in
$L_{n+1}^{\rightarrow}$. Namely, for $1\leq i\leq\kappa^{n}$, we let

$\displaystyle L_{n+1}^{\rightarrow}[i]$
$\displaystyle=\left(L_{n}^{\rightarrow}[i],1\right)$ $\displaystyle
L_{n+1}^{\rightarrow}[\kappa^{n}+i]$
$\displaystyle=\left(L_{n}^{\leftarrow}[i],2\right)$ $\displaystyle\vdots$
$\displaystyle L_{n+1}^{\rightarrow}[(\kappa-1)\kappa^{n}+i]$
$\displaystyle=\left(L_{n}^{\leftrightarrow}[i],\kappa\right),$

where for the last line, $\leftrightarrow$ stands for $\rightarrow$ if
$\kappa$ is odd, and $\leftarrow$ otherwise. $L_{n+1}$ clearly is connected
and visits all the vertices $\left\\{{1,\dots,\kappa}\right\\}^{n}$. Its edges
all have degree two, except $\left(L_{n}^{\rightarrow}[1],1\right)$ and
$\left(L_{n}^{\leftrightarrow}[\kappa^{n}],\kappa\right)$ which have degree
$1$, which concludes the construction of $L_{n}=L_{n}(\kappa^{n})$. To
conclude the proof, take $L_{n}(\ell)$ ($1\leq\ell\leq\kappa^{n}$) to be the
first $\ell$ consecutive vertices of $L_{n}^{\rightarrow}(\kappa^{n})$. ∎

###  H.3 Informational Lower Bounds: Hypotheses for Le Cam’s Lemma

This section is devoted to prove the two informational lower bounds Theorems
5.2 and 5.5. We will use the general informational lower bound from Theorem
G.1 in 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})$
respectively, and parameter of interest $\theta(D)=\mathrm{Supp}(D)$ that lies
in the metric space formed by the non-empty compact sets of $\mathbb{R}^{n}$
equipped with the metric $\rho=\mathrm{d_{H}}$.

####  H.3.1 Construction of the Hypotheses

First, we show how to build hypotheses, i.e probability distributions for Le
Cam’s Lemma (Theorem G.1). We present a generic construction in the manifold
setting by perturbing a base submanifold $M_{0}$. Note that the larger the
volume $\mathcal{H}^{d}(M_{0})$, the stronger the result. See also Proposition
H.5 for a result similar in spirit, and used to derive computational lower
bounds instead of informational ones.

######  Proposition H.3.

For all $M_{0}\in\mathcal{M}^{{n},{d}}_{2\mathrm{rch}_{\min}}$, $x_{0}\in
M_{0}$ and $\tau\leq 1$, there exists a manifold
$M_{1}\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ such that $x_{0}\in
M_{1}$, $\mathcal{H}^{d}(M_{0})/2\leq\mathcal{H}^{d}(M_{1})\leq
2\mathcal{H}^{d}(M_{0})$,

$\frac{\mathrm{rch}_{\min}}{2^{18}}\min\left\\{{\frac{1}{2^{22}d^{2}},\left(\frac{\mathcal{H}^{d}(M_{0})\tau}{\omega_{d}\mathrm{rch}_{\min}^{d}}\right)^{2/d}}\right\\}\leq\mathrm{d_{H}}(M_{0},M_{1})\leq\mathrm{rch}_{\min}/10,$

and so that the uniform distributions $D_{0},D_{1}$ over $M_{0},M_{1}$ satisfy
$\mathop{\mathrm{TV}}(D_{0},D_{1})\leq\tau/2.$

###### Proof of Proposition H.3.

Let $p_{0}\in M_{0}$ be an arbitrary point such that
$\left\|p_{0}-x_{0}\right\|\geq\mathrm{rch}_{\min}$. For instance, by taking
the geodesic variation $p_{0}=\gamma_{x_{0},v_{0}}(2\mathrm{rch}_{\min})$,
where $v_{0}\in T_{x_{0}}M_{0}$ is a unit tangent vector, a Taylor expansion
of $\gamma_{x_{0},v_{0}}$ and Lemma 2.2 yields

$\displaystyle\left\|p_{0}-x_{0}\right\|$
$\displaystyle\geq\left\|2\mathrm{rch}_{\min}v_{0}\right\|-\left\|\gamma_{x_{0},v_{0}}(\mathrm{rch}_{\min})-(x_{0}+2\mathrm{rch}_{\min}v_{0})\right\|$
$\displaystyle\geq
2\mathrm{rch}_{\min}-(2\mathrm{rch}_{\min})^{2}/(2\mathrm{rch}_{M_{0}})$
$\displaystyle\geq\mathrm{rch}_{\min},$

since $\mathrm{rch}_{M_{0}}\geq 2\mathrm{rch}_{\min}$. Let us denote by
$w_{0}\in\left(T_{p_{0}}M_{0}\right)^{\perp}$ a unit normal vector of $M_{0}$
at $p_{0}$. For $\delta,\eta>0$ to be chosen later, let $\Phi_{w_{0}}$ be the
function that maps any $x\in\mathbb{R}^{n}$ to

$\displaystyle\Phi_{w_{0}}(x)$
$\displaystyle=x+\eta\phi\left(\frac{x-p_{0}}{\delta}\right)w_{0},$

where $\phi:\mathbb{R}^{n}\to\mathbb{R}$ is the real bump function
$\phi(y)=\exp\left(-{\left\|y\right\|^{2}}/{(1-\left\|y\right\|^{2})}\right)\mathbbm{1}_{\mathrm{B}(0,1)}(y)$
of Lemma H.1. We let $M_{1}=\Phi_{w_{0}}(M_{0})$ be the image of $M_{0}$ by
$\Phi_{w_{0}}$. Roughly speaking, $M_{0}$ and $M_{1}$ only differ by a bump of
width $\delta$ and height $\eta$ in the neighborhood of $p_{0}$. Note by now
that $\Phi_{w_{0}}$ coincides with the identity map outside
$\mathrm{B}(p_{0},\delta)$ and in particular, $p_{0}=\Phi_{w_{0}}(p_{0})\in
M_{1}$ as soon as $\delta\leq\mathrm{rch}_{\min}$.

Combining Proposition H.1 and Lemma H.1, we get that
$M_{1}\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ and
$\mathcal{H}^{d}(M_{0})/2\leq\mathcal{H}^{d}(M_{1})\leq
2\mathcal{H}^{d}(M_{0})$ as soon as

$\displaystyle\frac{5\eta}{2\delta}\leq\frac{1}{10d}\text{ and
}\frac{23\eta}{\delta^{2}}\leq\frac{1}{4\mathrm{rch}_{\min}}.$

Under these assumptions, we have in particular that
$\mathrm{d_{H}}(M_{0},M_{1})\leq\left\|\Phi_{w_{0}}-I_{n}\right\|_{\infty}\leq\eta\leq\mathrm{rch}_{\min}/10.$
Also, by construction, $\Phi_{w_{0}}(p_{0})=p_{0}+\eta w_{0}$ belongs to
$M_{1}$, so that

$\displaystyle\mathrm{d_{H}}(M_{0},M_{1})\geq\mathrm{d}(p_{0}+\eta
w_{0},M_{0})=\eta,$

since $w_{0}\in\left(T_{p_{0}}M_{0}\right)^{\perp}$ [Fed59, Theorem 4.8 (12)].
Let us now consider the uniform probability distributions $D_{0}$ and $D_{1}$
over $M_{0}$ and $M_{1}$ respectively. These distributions have respective
densities $f_{i}=\mathcal{H}^{d}(M_{i})^{-1}\mathbbm{1}_{M_{i}}$
($i\in\left\\{{0,1}\right\\}$) with respect to the $d$-dimensional Hausdorff
measure $\mathcal{H}^{d}$ on $\mathbb{R}^{n}$. Furthermore, $\Phi_{w_{0}}$ is
a global diffeomorphism that coincides with the identity map on
$\mathrm{B}(p_{0},\delta)^{c}$. As a result, since
$\frac{5\eta}{2\delta}\leq\frac{1}{10d}\leq(2^{1/d}-1)$, [AKC+19, Lemma D.2]
yields that for $\delta\leq\mathrm{rch}_{\min}/2$,

$\displaystyle\mathop{\mathrm{TV}}(D_{0},D_{1})$ $\displaystyle\leq
12D_{0}\left(\mathrm{B}(0,\delta)\right)$
$\displaystyle=12\mathcal{H}^{d}(M_{0}\cap\mathrm{B}(0,\delta))/\mathcal{H}^{d}(M_{0})$
$\displaystyle\leq 12(2^{d}\omega_{d}\delta^{d})/\mathcal{H}^{d}(M_{0}),$

where we applied the upper bound of Lemma B.1 to get the last inequality,
using that $\mathrm{rch}_{M_{0}}\geq 2\mathrm{rch}_{\min}$.

Finally, setting $\eta=\delta^{2}/(92\mathrm{rch}_{\min})$ yields a valid
choice of parameters for all $\delta\leq\mathrm{rch}_{\min}/(2300d)$. Hence,
we have shown that for all
$\delta\leq\mathrm{rch}_{\min}/(2^{12}d)\leq\mathrm{rch}_{\min}/(2300d)$,

$\displaystyle\mathrm{d_{H}}(M_{0},M_{1})\geq\frac{\delta^{2}}{92\mathrm{rch}_{\min}}\text{
and }\mathop{\mathrm{TV}}(D_{0},D_{1})\leq
12(2^{d}\omega_{d}\delta^{d})/\mathcal{H}^{d}(M_{0}).$

Equivalently, setting
$\tau/2=12(2^{d}\omega_{d}\delta^{d})/\mathcal{H}^{d}(M_{0})$ and
$\tau_{(0)}:=24\omega_{d}(\mathrm{rch}_{\min}/(2^{11}d))^{d}/\mathcal{H}^{d}(M_{0})$,
we have shown that for all $\tau\leq\tau_{(0)}$, there exists
$M_{1}\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ such that

$\displaystyle\mathrm{d_{H}}(M_{0},M_{1})\geq\frac{1}{92\mathrm{rch}_{\min}}\left(\frac{\mathcal{H}^{d}(M_{0})\tau}{24(2^{d}\omega_{d})}\right)^{2/d}\text{
and }\mathop{\mathrm{TV}}(D_{0},D_{1})\leq\tau/2.$

We conclude the proof for $\tau\leq\tau_{(0)}$ by further bounding the term

$\displaystyle\mathrm{d_{H}}(M_{0},M_{1})$
$\displaystyle\geq\frac{1}{92\mathrm{rch}_{\min}}\left(\frac{\mathcal{H}^{d}(M_{0})\tau}{24(2^{d}\omega_{d})}\right)^{2/d}$
$\displaystyle=\frac{\mathrm{rch}_{\min}}{368\times
24^{2/d}}\left(\frac{\mathcal{H}^{d}(M_{0})\tau}{\omega_{d}\mathrm{rch}_{\min}^{d}}\right)^{2/d}$
$\displaystyle\geq\frac{\mathrm{rch}_{\min}}{2^{18}}\left(\frac{\mathcal{H}^{d}(M_{0})\tau}{\omega_{d}\mathrm{rch}_{\min}^{d}}\right)^{2/d}.$

Otherwise, if $\tau>\tau_{(0)}$, then the above construction applied with
$\tau_{(0)}$ yields the existence of some
$M_{1}\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ with the same
properties, and

$\displaystyle\mathrm{d_{H}}(M_{0},M_{1})$
$\displaystyle\geq\frac{\mathrm{rch}_{\min}}{2^{18}}\left(\frac{\mathcal{H}^{d}(M_{0})\tau_{(0)}}{\omega_{d}\mathrm{rch}_{\min}^{d}}\right)^{2/d}\text{
and }\mathop{\mathrm{TV}}(D_{0},D_{1})\leq\tau_{(0)}/2\leq\tau/2.$

Summing up the two cases above, for all $\tau\leq 1$ we have exhibited some
$M_{1}\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ with properties as
above, $\mathop{\mathrm{TV}}(D_{0},D_{1})\leq\tau/2$ and

$\displaystyle\mathrm{d_{H}}(M_{0},M_{1})$
$\displaystyle\geq\frac{\mathrm{rch}_{\min}}{2^{18}}\left(\frac{\mathcal{H}^{d}(M_{0})\min\left\\{{\tau,\tau_{(0)}}\right\\}}{\omega_{d}\mathrm{rch}_{\min}^{d}}\right)^{2/d}$
$\displaystyle\geq\frac{\mathrm{rch}_{\min}}{2^{18}}\min\left\\{{\frac{1}{2^{22}d^{2}},\left(\frac{\mathcal{H}^{d}(M_{0})\tau}{\omega_{d}\mathrm{rch}_{\min}^{d}}\right)^{2/d}}\right\\},$

which concludes the proof.

∎

Applying the technique of Proposition H.3 with manifolds $M_{0}$ having
largest possible volume (typically of order $1/f_{\min}$) in 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})$
yields the following result. The proof follows the ideas of [AL19, Lemma 5].
To our knowledge, the first result of this type dates back to [GPPVW12a,
Theorem 6].

######  Lemma H.5.

  * •

Assume that $f_{\min}\leq f_{\max}/4$ and that

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

Then for all $\tau\leq 1$, there exist
$D_{0},D_{1}\in\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
with respective supports $M_{0}$ and $M_{1}$ such that

$\displaystyle\mathrm{d_{H}}(M_{0},M_{1})\geq\frac{\mathrm{rch}_{\min}}{2^{20}}\min\left\\{{\frac{1}{2^{20}d^{2}},\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/d}}\right\\}\text{
and }\mathop{\mathrm{TV}}(D_{0},D_{1})\leq\tau/2.$

  * •

Assume that $\mathrm{rch}_{\min}\leq R/144$ and $f_{\min}\leq f_{\max}/96$.
Writing $C_{d}^{\prime}=9(2^{2d+1}\sigma_{d-1})$, assume that

$\min_{1\leq k\leq
n}\left(\frac{192\mathrm{rch}_{\min}\sqrt{k}}{R}\right)^{k}\leq
2^{d+1}C_{d}^{\prime}f_{\min}\mathrm{rch}_{\min}^{d}\leq 1.$

Then for all $\tau\leq 1$, there exist
$D_{0},D_{1}\in\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
with respective supports $M_{0}$ and $M_{1}$ such that

$\displaystyle\mathrm{d_{H}}(M_{0},M_{1})\geq\frac{\mathrm{rch}_{\min}}{2^{30}}\min\left\\{{\frac{1}{2^{10}d^{2}},\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/d}}\right\\}\text{
and }\mathop{\mathrm{TV}}(D_{0},D_{1})\leq\tau/2.$

###### Proof of Lemma H.5.

For both models, the idea is to first build a manifold
$M_{0}\in\mathcal{M}^{{n},{d}}_{2\mathrm{rch}_{\min}}$ with prescribed volume
close to $1/f_{\min}$, and then consider the variations of it given by
Proposition H.3.

  * •

Let $M_{0}$ be a $d$-dimensional sphere of radius
$r_{0}=\left(\frac{1}{2\sigma_{d}f_{\min}}\right)^{1/d}$ in
$\mathbb{R}^{d+1}\times\left\\{{0}\right\\}^{n-(d+1)}\subseteq\mathbb{R}^{n}$
containing $x_{0}=0\in\mathbb{R}^{n}$. By construction,
$\mathrm{rch}_{M_{0}}=r_{0}\geq 2\mathrm{rch}_{\min}$, so that
$M_{0}\in\mathcal{M}^{{n},{d}}_{2\mathrm{rch}_{\min}}$, and one easily checks
that $\mathcal{H}^{d}(M_{0})=1/(2f_{\min})$. For all $\tau\leq 1$, Proposition
H.3 asserts that there exists a manifold
$M_{1}\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ such that $x_{0}\in
M_{1}$, with volume

$1/f_{\max}\leq
1/(4f_{\min})\leq\mathcal{H}^{d}(M_{0})\leq\mathcal{H}^{d}(M_{1})\leq
2\mathcal{H}^{d}(M_{0})\leq 1/f_{\min},$

such that

$\displaystyle\mathrm{d_{H}}(M_{0},M_{1})$
$\displaystyle\geq\frac{\mathrm{rch}_{\min}}{2^{18}}\min\left\\{{\frac{1}{2^{22}d^{2}},\left(\frac{\tau}{2\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/d}}\right\\}$
$\displaystyle\geq\frac{\mathrm{rch}_{\min}}{2^{20}}\min\left\\{{\frac{1}{2^{20}d^{2}},\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/d}}\right\\},$

and with respective uniform distributions $D_{0}$ and $D_{1}$ over $M_{0}$ and
$M_{1}$ that satisfy $\mathop{\mathrm{TV}}(D_{0},D_{1})\leq\tau/2$. Since the
densities of $D_{0}$ and $D_{1}$ are constant and equal to
$\mathcal{H}^{d}(M_{0})^{-1}$ and $\mathcal{H}^{d}(M_{1})^{-1}$ respectively,
the bounds on the volumes of $M_{0}$ and $M_{1}$ show that $D_{0}$ and $D_{1}$
belong to
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L=0})\subseteq\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$,
which concludes the proof.

  * •

Let $M_{0}\subseteq\mathbb{R}^{n}$ be a submanifold given by Proposition H.2
applied with parameters $\mathrm{rch}_{\min}^{\prime}=2\mathrm{rch}_{\min}$,
$\mathcal{V}=1/(2f_{\min})$ and $R^{\prime}=R/2$. That is,
$M_{0}\in\mathcal{M}^{{n},{d}}_{2\mathrm{rch}_{\min}}$ is such that
$1/(48f_{\min})\leq\mathcal{H}^{d}(M_{0})\leq 1/(2f_{\min})$ and
$M_{0}\subseteq\mathrm{B}(0,R/2)$. For all $\tau\leq 1$, Proposition H.3
asserts that there exists a manifold
$M_{1}\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ such that
$\mathrm{d_{H}}(M_{0},M_{1})\leq\mathrm{rch}_{\min}/10$, with volume

$1/f_{\max}\leq
1/(96f_{\min})\leq\mathcal{H}^{d}(M_{0})/2\leq\mathcal{H}^{d}(M_{1})\leq
2\mathcal{H}^{d}(M_{0})\leq 1/f_{\min},$

and

$\displaystyle\mathrm{d_{H}}(M_{0},M_{1})$
$\displaystyle\geq\frac{\mathrm{rch}_{\min}}{2^{18}}\min\left\\{{\frac{1}{2^{22}d^{2}},\left(\frac{\tau}{48\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/d}}\right\\}$
$\displaystyle\geq\frac{\mathrm{rch}_{\min}}{2^{30}}\min\left\\{{\frac{1}{2^{10}d^{2}},\left(\frac{\tau}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\right)^{2/d}}\right\\},$

and such that the respective uniform distributions $D_{0}$ and $D_{1}$ over
$M_{0}$ and $M_{1}$ satisfy $\mathop{\mathrm{TV}}(D_{0},D_{1})\leq\tau/2$.
Because $M_{0}\subseteq\mathrm{B}(0,R/2)$ and
$\mathrm{d_{H}}(M_{0},M_{1})\leq\mathrm{rch}_{\min}/10\leq R/2$, we
immediately get that $M_{1}\subseteq\mathrm{B}(0,R/2+R/2)=\mathrm{B}(0,R)$. As
a result, this family clearly provides the existence of the announced
$\varepsilon$-packing of
$\bigl{(}\mathrm{B}(0,R)\sqcap\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}},\mathrm{d_{H}}\bigr{)}$.
As above, the bounds on the volumes of $M_{0}$ and $M_{1}$ show that
$D_{0},D_{1}\in\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L=0})\subseteq\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$,
which concludes the proof.

∎

####  H.3.2 Proof of the Informational Lower Bounds for Manifold Estimation

With all the intermediate results above, the proofs of Theorem 5.2 and Theorem
5.5 follow straightforwardly.

###### Proof of Theorem 5.2 and Theorem 5.5.

These are direct applications of Theorem G.1 for parameter of interest
$\theta(D)=\mathrm{Supp}(D)$ and distance $\rho=\mathrm{d_{H}}$, with the