2 8 6 Estimation Under Convex Constraints

A) Basic facts

1. We admit the existence and uniqueness of $\pi_{\mathscr{C}} y \in \mathscr{C}$.
Then if $u \in \mathscr{C}$ and $0 < t < 1$ are fixed, by convexity of $\mathscr{C}$ we have $tu + (1-t) \pi_{\mathscr{C}} y \in \mathscr{C}$ and by definition of $\pi_{\mathscr{C}} y$:

(1)

\begin{align} \left\| y - \left( t u+(1-t) \pi_{\mathscr{C}} y \right) \right\|^2 \geq \left\| y - \pi_{\mathscr{C}} y \right\|^2 \end{align}

2. If we denote $s(t) = y - \left(t u+(1-t) \pi_{\mathscr{C}} y \right)$ for $t \in [0, 1]$ then $\| s(\cdot) \|^2$ is differentiable and minimal at $0$, therefore its derivative at $0$ is positive:

(2)

\begin{align} 2 \langle s(0), s'(0) \rangle \geq 0 \end{align}

i.e.

(3)

\begin{align} \left\langle u - \pi_{\mathscr{C}} y, y - \pi_{\mathscr{C}} y \right\rangle \leq 0 \end{align}

Then:

(4)

\begin{aligned} \left\| \pi_{\mathscr{C}} y - y \right\|^2 &= \| u - y \|^2 + 2 \left\langle u - \pi_{\mathscr{C}} y, y - \pi_{\mathscr{C}} y \right\rangle - \left\| u - \pi_{\mathscr{C}} y \right\|^2 \\ &\leq \| u - y \|^2 - \left\| u - \pi_{\mathscr{C}} y \right\|^2 \end{aligned}

3. First equality: Using the same derivation technique but this time with the stronger hypothesis that $K$ is a closed cone, let us denote $s(t) = t \pi_K y - y$ for $t \in \mathbb{R}_+$.

This function is differentiable and minimal at $t = 1$, therefore its derivative at $1$ is zero:

(5)

\begin{align} 2 \langle s(0), s'(0) \rangle = 2 \langle \pi_K y - y, \pi_K y \rangle = 0 \end{align}

i.e

(6)

\begin{align} \langle \pi_K y, y \rangle = \| \pi_K y \|^2 \end{align}

Second equality: This one actually is order 0, though we will make use of the first inequality. For all $u \in K$ with $\| u \| = 1$ and $\lambda \geq 0$:

(7)

\begin{align} \| y - \pi_K y \|^2 \leq \| y - \lambda u \|^2 \end{align}

i.e.

(8)

\begin{align} 2 \lambda \langle u, y \rangle \leq \lambda^2 + \| \pi_K y \|^2 \end{align}

In particular, for $\lambda = \| \pi_K y \|$ we have:

(9)

\begin{align} \langle u, y \rangle \leq \| \pi_K y \| \end{align}

If $u = \frac{\pi_K y}{ \| \pi_K y \| }$, this last inequality becomes an equality, therefore:

(10)

\begin{align} \| \pi_K y \| = \max_{u \in K, \|u\| = 1} \langle u, y \rangle \end{align}

B) Global width

1. First, let us assume that $\mathscr{C}$ is a linear span of dimension $d$ and $u \in \mathscr{C}$.
In this particular case, $\pi_{K_{u, \mathscr{C}}}$ is a linear map, so $\pi_{K_{u, \mathscr{C}}} \varepsilon$ is a centered Gaussian vector with covariance matrix $\Pi \, \Pi^\top$ where $\Pi$ is the matrix representing $\pi_{K_{u, \mathscr{C}}}$ in the canonical basis of $\mathbb{R}^n$.

Therefore:

(11)

\begin{aligned} \delta (\mathscr{C}, u) &= \mathbb{E} \left[ \left\| \pi_{K_{u, \mathscr{C}}} \varepsilon \right\|^2 \right] \\ &= \mathrm{Tr} \, \mathrm{Cov} \, (\pi_{K_{u, \mathscr{C}}} \varepsilon) \\ &= \mathrm{Tr} \, (\pi_{K_{u, \mathscr{C}}} \circ \pi_{K_{u, \mathscr{C}}}^*) \\ &= \mathrm{Tr} \, \pi_{K_{u, \mathscr{C}}} = d \end{aligned}

because $\pi_{K_{u, \mathscr{C}}}$ is an orthogonal projection.

2. First inequality: Let us fix $u \in \mathscr{C}$. In A.2. we showed that:

(12)

\begin{align} \left\| \widehat{f}_{\mathscr{C}} - y \right\|^2 \leq \| u - y \|^2 - \left\| u - \widehat{f}_{\mathscr{C}} \right\|^2 \end{align}

which gives:

(13)

\begin{aligned} &\| \widehat{f}_{\mathscr{C}} - f \|^2 + 2 \langle y - f, f - \widehat{f}_{\mathscr{C}} \rangle + \| y - f \|^2 \\ \leq \, &\| u - f \|^2 + 2 \langle y - f, f - u \rangle + \| y - f \|^2 - \left\| u - \widehat{f}_{\mathscr{C}} \right\|^2 \end{aligned}

which in turn gives the first inequality:

(14)

\begin{aligned} \left\| \widehat{f}_{\mathscr{C}} - f \right\|^2 &\leq \|u - f\|^2 + 2 \sigma \langle \varepsilon, \widehat{f}_{\mathscr{C}} - u \rangle - \left \| u - \widehat{f}_{\mathscr{C}} \right\|^2 \\ \end{aligned}

Second inequality: Let us fix $v \in K_{u, \mathscr{C}}$. Then:

(15)

\begin{align} \| \varepsilon - \pi_{K, \mathscr{C}} \varepsilon \|^2 \leq \| \varepsilon - v \|^2 \end{align}

i.e.

(16)

\begin{align} 2 \langle \varepsilon, v \rangle - \| v \|^2 \leq \| \pi_K \varepsilon \|^2 \end{align}

With the choice $v = \sigma^{-1} (\widehat{f}_{\mathscr{C}} - u) \in K_{u, \mathscr{C}}$, we obtain the second inequality:

(17)

\begin{aligned} \|u - f\|^2 + 2 \sigma \langle \varepsilon, \widehat{f}_{\mathscr{C}} - u \rangle - \left \| u - \widehat{f}_{\mathscr{C}} \right\|^2 \leq \| u - f \|^2 + \sigma^2 \left\| \pi_{K_{u, \mathscr{C}}} \varepsilon \right\|^2 \end{aligned}

3. Let us fix $L>0$ and $u \in \mathscr{C}$ such that:

(18)

\begin{align} u \in \underset{u \in \mathscr{C}}{\operatorname{argmin}} \left\{ \| u - f \|^2 + \sigma^2 \left( \sqrt{\delta (\mathscr{C}, u)} + \sqrt{2x} \right)^2 \right\} \end{align}

Since the map $\varepsilon \rightarrow \| \pi_{K_{u, \mathscr{C}}} \varepsilon \|$ is $1$-Lipschitz, the Gaussian concentration inequality (B.2), page 301, ensures that there exist $\xi \sim \mathcal{E} (1)$ such that:

(19)

\begin{align} \| \pi_{K_{u, \mathscr{C}}} \varepsilon \| \leq \mathbb{E} [ \| \pi_{K_{u, \mathscr{C}}} \varepsilon \| ] + \sqrt{2 \xi} \end{align}

Combined with Jensen inequality using $\sqrt{}$, this gives:

(20)

\begin{align} \| \pi_{K_{u, \mathscr{C}}} \varepsilon \| \leq \sqrt{\delta(\mathscr{C}, u)} + \sqrt{2 \xi} \end{align}

From last question we deduce:

(21)

\begin{align} \left\| \widehat{f}_{\mathscr{C}} - f \right \|^2 \leq \| u - f \|^2 + \sigma^2 \left( \sqrt{\delta (\mathscr{C}, u)} + \sqrt{2 \xi} \right)^2 \end{align}

In conclusion, with probability at least $1-e^{-L}$, we have:

(22)

\begin{align} \left\| \widehat{f}_{\mathscr{C}} - f \right\|^2 \leq \inf_{u \in \mathscr{C}} \left\{ \| u - f \|^2 + \sigma^2 \left( \sqrt{\delta (\mathscr{C}, u)} + \sqrt{2L} \right)^2 \right\} \end{align}

C) Local width

Let $t>0$ and $u \in \mathbb{R}^n$. We define

(23)

\begin{align} F_{u, \mathscr{C}}(t)=\mathbb{E}\left[\sup _{c \in \mathscr{C},\|u-c\| \leq t}\langle\varepsilon, c-u\rangle\right] . \end{align}

1. We showed in B.2. that:

(24)

\begin{aligned} \left\| \widehat{f}_{\mathscr{C}} - f \right\|^2 &\leq \|u - f\|^2 + 2 \sigma \langle \varepsilon, \widehat{f}_{\mathscr{C}} - u \rangle - \left \| u - \widehat{f}_{\mathscr{C}} \right\|^2 \\ &\leq \|u - f\|^2 + 2 \sigma \langle \varepsilon, \widehat{f}_{\mathscr{C}} - u \rangle \end{aligned}

In particular, if $\left\|\widehat{f}_{\mathscr{C}}-u\right\| \leq t$, then

(25)

\begin{align} \left\| \widehat{f}_{\mathscr{C}} - f \right\|^2 \leq \| u - f \|^2 + 2 \sigma Z_t, \quad \text { where } \quad Z_t = \sup _{c \in \mathscr{C}, \| u - c \| \leq t} \langle \varepsilon, c - u \rangle \end{align}

2. In order for $Z_t$ to be well defined, we will also assume: $u \in \mathscr{C}$. We showed in A.2. that:

(26)

\begin{align} \left\| \widehat{f}_{\mathscr{C}} - y \right\|^2 \leq \| u - y \|^2 - \left\| \widehat{f}_{\mathscr{C}} - u \right\|^2 \end{align}

so that for any $\lambda \in \mathbb{R}$:

(27)

\begin{aligned} \left\| \widehat{f}_{\mathscr{C}} - y \right\|^2 - \| u - y \|^2 &\leq \left( \| \widehat{f}_{\mathscr{C}} - u \| - \lambda \right)^2 - \left\| \widehat{f}_{\mathscr{C}} - u \right\|^2 \\ \left\| \widehat{f}_{\mathscr{C}} - y \right\|^2 - \| u - y \|^2 + 2 \lambda \| \widehat{f}_{\mathscr{C}} - u \| &\leq \lambda^2 \end{aligned}

In particular, for $\lambda = \frac{\langle \sigma \varepsilon, \widehat{f}_{\mathscr{C}} - u \rangle}{\left\| \widehat{f}_{\mathscr{C}} - u \right\|}$:

(28)

\begin{align} \left\| \widehat{f}_{\mathscr{C}} - y \right\|^2 - \| u - y \|^2 + 2 \langle \sigma \varepsilon, \widehat{f}_{\mathscr{C}} - u \rangle \leq \left\langle \sigma \varepsilon, \frac{\widehat{f}_{\mathscr{C}} - u}{\left\| \widehat{f}_{\mathscr{C}} - u \right\|} \right\rangle^2 \end{align}

For $c = u + \frac{t}{\| \widehat{f}_{\mathscr{C}} - u \|} (\widehat{f}_{\mathscr{C}} - u)$:

(29)

\begin{align} \left\| \widehat{f}_{\mathscr{C}} - f \right\|^2 \leq \| u - f \|^2 + \left( \frac{\sigma \langle \varepsilon, c - u \rangle}{t} \right)^2 \end{align}

Since $\| \widehat{f}_{\mathscr{C}} - u \| > t$, we have $c \in \mathscr{C}$ and $\| c - u \| \leq t$. Therefore:

(30)

\begin{align} \left\| \widehat{f}_{\mathscr{C}} - f \right\|^2 \leq \| u - f \|^2 + \left( \frac{\sigma Z_t}{t} \right)^2 \end{align}

3. Let us fix $L>0$ and $u \in \mathscr{C}$ such that:

(31)

\begin{align} u \in \underset{u \in \mathscr{C}}{\operatorname{argmin}} \left\{ \|u - f \|^2 + \left( t(u) + \sigma \sqrt{2L} \right)^2 \right\} \end{align}

Let $t(u)>0$ be such that $F_{u, \mathscr{C}}(t(u)) \leq(t(u))^2 /(2 \sigma)$.

Since $\frac{Z_{t(u)}}{t(u)}$ is a $1$-Lipschitz function of $\varepsilon$, the Gaussian concentration inequality (B.2), page 301, ensures that there exist $\xi \sim \mathcal{E} (1)$ such that:

(32)

\begin{align} \frac{Z_{t(u)}}{t(u)} \leq \frac{F_{u, \mathscr{C}} (t(u))}{t(u)} + \sqrt{2 \xi} \leq \frac{t(u)}{2 \sigma} + \sqrt{2 \xi} \end{align}

From which we deduce:

(33)

\begin{align} 2 \sigma Z_{t(u)} \leq t(u)^2 + 2\, t(u)\, \sigma \sqrt{2 \xi} \leq \left( t(u) + \sigma \sqrt{2 \xi} \right)^2 \end{align}

and

(34)

\begin{align} \left( \frac{\sigma Z_{t(u)}}{t(u)} \right)^2 \leq \left( \frac{t(u)}2 + \sigma \sqrt{2 \xi} \right)^2 \leq \left( t(u) + \sigma \sqrt{2 \xi} \right)^2 \end{align}

Combining the last two inequalities with the last two questions, for all $u \in \mathscr{C}$:

(35)

\begin{align} \left \| \widehat{f}_{\mathscr{C}} - f \right \|^2 \leq \|u - f \|^2 + \left( t(u) + \sigma \sqrt{2L} \right)^2 \end{align}

Then with probability at least $1-e^{-L}$ we have:

(36)

\begin{align} \left \| \widehat{f}_{\mathscr{C}} - f \right \|^2 \leq \inf_{u \in \mathscr{C}} \left\{ \|u - f \|^2 + \left( t(u) + \sigma \sqrt{2L} \right)^2 \right\} \end{align}