3 6 4 Non Parametric Lower Bounds

1.

Let $\delta > 0$ and $\{f_1, ..., f_{N_d(\delta)}\} \subset S$ a $\delta$-separated set of maximal size.

Then we have

(1)

\begin{align} \forall f \in S, \exists i \in \{1, ..., {N_d(\delta)}\} ~s.t~ f_i \in B(f, \delta), \end{align}

otherwise the maximality of $N_d(\delta)$ would be contradicted.

This means that the balls $B(f_i, \delta), i \in \{1, ..., {N_d(\delta)}\}$ are $N_d(\delta)$ balls centered in $S$, with radius $\delta$, which cover $S$. By minimality of $N_{cov}(\delta)$, we have $N_{cov}(\delta) \leq N_d(\delta)$

2.

Let $f \in S$. We know that $f$ belongs to one of the balls of radius $r$ centered on $\{g_1, ..., g_{N_{cov}(r)}\}$, and we suppose without loss of generality that it belongs to $B(g_1, r)$.

Because $\mathbb{Q} \geq \frac{P_{g_1}}{N_{cov}(r)}$, we have

(2)

\begin{align} KL(\mathbb{P}_f, \mathbb{Q})&=\int_{\mathcal{Y}} \log \left(\frac{d P}{d Q}\right) d P \\ &\leq \int_{\mathcal{Y}} \log \left(\frac{d P}{d P_{g_1} / N_{cov}(r)}\right) d P\\ &= \int_{\mathcal{Y}} \log N_{cov}(r) d P + KL(P_f, P_{g_1}) \\ &\leq \log N_{cov}(r) + n d(f, g_1)^2 \\ &\leq \log N_{d}(r) + n d(f, g_1)^2 ~(question ~1) \\ &\leq log N_{d}(r) + n r^2 ~ because~ f \in B(g_1, r) \\ \end{align}

3.

Using the assumed inequality, we have

(3)

\begin{align} n r^{2}+\log N_{d}(r) \geq n r^{2} + C_{-} \delta^{-\alpha}, \end{align}

thus

(4)

\begin{align} (n r^{2}+\log N_{d}(r))_{r\to 0, r\to+\infty} \rightarrow +\infty \end{align}

This means that

(5)

\begin{align} \inf _{r>0}\left\{n r^{2}+\log N_{d}(r)\right\} = \min _{r>0}\left\{n r^{2}+\log N_{d}(r)\right\} := n r_{min}^{2}+\log N_{d}(r_{min}). \end{align}

Let

(6)

\begin{align} \mathbb{Q}=\frac{1}{N_{c o v}(r_{min})} \sum_{j=1}^{N_{c o v}(r_{min})} \mathbb{P}_{g_{j}}. \end{align}

Then using question 2, we have:

(7)

\begin{align} \frac{1}{N} \sum_{j=1}^{N} K L\left(P_{f_{j}}, \mathbb{Q}\right) \leq \frac{1}{N} \sum_{j=1}^{N} \inf _{r>0}\left\{n r^{2}+\log N_{d}(r)\right\} = \inf _{r>0}\left\{n r^{2}+\log N_{d}(r)\right\} \end{align}

4.

Let $\{f_1, ..., f_{N_d(\delta)}\} \subset S$ be a $\delta$-separated subset of S. We have:

(8)

\begin{align} \inf _{\hat{f}: \mathcal{Y} \stackrel{\text { meas. }}{\rightarrow} S} \max _{f \in S} \mathbb{E}_{f}\left[d(\hat{f}(Y), f)^{2}\right] & \geq \min _{\hat{f}: \mathcal{Y} \stackrel{\text { meas }}{\longrightarrow} S} \max _{j=1, \ldots, N} \mathbb{E}_{f_{j}}\left[d\left(\hat{f}(Y), f_{j}\right)^{2}\right] \\ & \geq \inf _{\hat{f}: \mathcal{Y} \stackrel{\text { meas }}{\longrightarrow} S} \frac{1}{N} \sum_{j=1}^{N} \mathbb{E}_{f_{j}}\left[d\left(\hat{f}(Y), f_{j}\right)^{2}\right] \\ &\geq 2^{-2}\left(1-\frac{1+\frac{1}{N} \sum_{j=1}^{N} K L\left(\mathbb{P}_{f_{j}}, \mathbb{Q}\right)}{\log (N)}\right) \inf _{i \neq k} d\left(f_{i}, f_{k}\right)^{2}, ~~(corrolary~ 3.4)\\ &\geq 2^{-2}\left(1-\frac{1+\frac{1}{N} \sum_{j=1}^{N} K L\left(\mathbb{P}_{f_{j}}, \mathbb{Q}\right)}{\log (N)}\right) \delta^2 \\ & \geq 2^{-2} ( 1 - \frac{1 + inf_{r > 0}n r^2 + log N_d(r)}{\log N_d(\delta)})\delta^2, ~~(using~question~3)\\ & \geq 2^{-2} ( 1 - \frac{1 + n r^2 + C_+ r^{-\alpha}}{C_- \delta^{-\alpha}})\delta^2 ~~for~any~r > 0, \end{align}

.

If we take $\delta = K n^{-1 / 2 + \alpha}$ and $r = n^{-1 / 2 + \alpha}$, with $K$ constant depending only on $C_+$, $C_-$ and $\alpha$, we have:

(9)

\begin{align} \frac{1 + n r^2 + C_+ r^{-\alpha}}{C_- \delta^{-\alpha}} & \leq \frac{n^{\alpha / 2 + \alpha} + n r^2 + C_+ r^{-\alpha}}{C_- \delta^{-\alpha}} ~ (n \geq 2)\\ & = \frac{n^{\alpha / 2 + \alpha}(2 + C_+)}{n^{\alpha / 2 + \alpha}C_- K } \\ &= \frac{(2 + C_+)}{C_- K } \end{align}

Taking $K \geq \frac{1}{2}\frac{(2 + C_+)}{C_-}$, we have $1 - \frac{1 + n r^2 + C_+ r^{-\alpha}}{C_- \delta^{-\alpha}} \geq \frac{1}{2}$, and

(10)

\begin{align} \inf _{\hat{f}: \mathcal{Y} \stackrel{\text { meas. }}{\rightarrow} S} \max _{f \in S} \mathbb{E}_{f}\left[d(\hat{f}(Y), f)^{2}\right] \geq 2^{-3} * K^2 * n^{-2 / 2 + \alpha} \end{align}