SOLIT oracle risk bound and spectral rates

Work in the supplied singular coordinates, and write $f_m=\mathbb{E}{\widehat{x}}_m$, ${\epsilon }_m={\widehat{x}}_m-f_m$, and $b_{a,b}=\mathrm{\parallel }{f}_b-f_a{\mathrm{\parallel }}_X$. By [F1] all these variables have finite second moments and $R_m=b_m^2+v_m$. Each finite observed-data sum in [F2] is a measurable $X$-valued random element. For each fixed candidate, its Cauchy set $C_m={\bigcap }_{r\ge 1}{\bigcup }_{N\ge 1}{\bigcap }_{p,q\ge N}\{\mathrm{\parallel }{\widehat{x}}_{m,p}^{\mathrm{o}\mathrm{b}\mathrm{s}}-{\widehat{x}}_{m,q}^{\mathrm{o}\mathrm{b}\mathrm{s}}{\mathrm{\parallel }}_X\le 1\mathrm{/}r\}$ is a measurable event, since it is a countable combination of measurable pairwise-distance events; completeness of $X$ makes it the convergence event. Its limit on $C_m$, extended by $0_X$ outside $C_m$, is measurable as a pointwise limit into separable $X$. Under the observation law, $y_j=s_j{\theta }_j+\sigma {\xi }_j$, so the pointwise construction in [F1] identifies this pointwise limit with the $L^2$ estimator almost surely; the finitely many candidates share a full-probability agreement event. Thus the finite comparison conditions are measurable, and [F2] ensures an accepted index exists. Hence $\widehat{m}$ is a measurable finite-valued index. Fix $k=m_{\ast }$; its defining condition gives $b_{a,b}\le \beta \sqrt{v_{a,b}}$ whenever $k\le a<b\le M$.

For later use, qualification gives $b_m^2\le {\rho }^2{C}_{\phi }^2\phi ({\alpha }_m{)}^2$. The filter bounds give $\lambda q_{\alpha }(\lambda {)}^2\le C_q^{\mathrm{\prime }}\mathrm{/}\alpha$ and $\lambda q_{\alpha }(\lambda {)}^2\le (C_q^{\mathrm{\prime }}{)}^2\lambda \mathrm{/}{\alpha }^2$. With $C=\max \{C_q^{\mathrm{\prime }},(C_q^{\mathrm{\prime }}{)}^2\}$, splitting eigenvalues at $\alpha$ and summing nonnegative terms therefore gives $V_{T,q}(\alpha ):={\sum }_j{\lambda }_j{q}_{\alpha }({\lambda }_j{)}^2\le \frac{C}{{\alpha }^2}(\alpha \mathrm{\Sigma }(\alpha )+{\sum }_{{\lambda }_j<\alpha }{\lambda }_j)=\frac{C}{{\alpha }^2}{\int }_0^{\alpha }\mathrm{\Sigma }(t)dt\le C{C}_{S}S(\alpha )\mathrm{/}\alpha \mathrm{.}$ The equality follows by integrating each indicator $1_{\{t\le {\lambda }_j\}}$; [F5] justifies the interchange. Further $u_m\le C_q^{\mathrm{\prime }}{\sigma }^2\mathrm{/}{\alpha }_m$, since ${\lambda }_j{q}_{{\alpha }_m}({\lambda }_j)\le 1$.

The centered difference $G_{a,b}$ has coordinate variances ${\sigma }^2{\lambda }_j(q_{{\alpha }_b}({\lambda }_j)-q_{{\alpha }_a}({\lambda }_j){)}^2$. By nonnegative coordinate ordering their sum and supremum satisfy $v_{a,b}\le v_b$ and $u_{a,b}\le u_b$. Applying [F3] to their squared weights gives $\sigma z_{a,b}(t)\le \sqrt{v_{a,b}}+\sqrt{2u_{a,b}t},\mathbb{E}\mathrm{\parallel }{\epsilon }_m{\mathrm{\parallel }}^4\le 3v_m^2\mathrm{.}$ Also the probability of exceeding the actual pairwise quantile is at most $e^{-t}$, including a degenerate difference. These are statements about the supplied normal sequence; no new infinite product law or general Gaussian concentration theorem is needed.

For the rates let $s={\sigma }^2\downarrow 0$ and $L=\log (1\mathrm{/}s)$. The initial variance is $v_0=s{V}_{T,q}({\alpha }_0)$ with a fixed positive factor, and the geometric lower ratio implies $M\le 1+\log (1\mathrm{/}{v}_0)\mathrm{/}\log {\theta }_1=O(L)$. In the mild case put $D=2\nu +1+1\mathrm{/}a$, $t=s^{1\mathrm{/}D}{L}^{2\tau \mathrm{/}D}$ and $r=s^{2\nu \mathrm{/}D}{L}^{-2\tau (1+1\mathrm{/}a)\mathrm{/}D}$. In the severe case put $p=1\mathrm{/}\vartheta \ge 2$, $D=2\nu +1$, $t=s^{1\mathrm{/}D}{L}^{(2\tau +p)\mathrm{/}D}$ and $r=s^{2\nu \mathrm{/}D}{L}^{(2\nu p-2\tau )\mathrm{/}D}$. In either case $\log (1\mathrm{/}t)\asymp L$, $r\to 0$, $r\mathrm{/}s\to \mathrm{\infty }$, and direct substitution gives $\phi (t{)}^2\asymp sS(t)\mathrm{/}t\asymp r$. All implicit constants in the rest of the argument are independent of the truth in the fixed source ball and of sufficiently small $s$.

On $\{\widehat{m}\le k\}$, acceptance gives $\mathrm{\parallel }{\widehat{x}}_{\widehat{m}}-{\widehat{x}}_k\mathrm{\parallel }\le {\eta }_{\widehat{m},k}$ when $\widehat{m}<k$, and the difference is zero when equality holds. For $m<k$, $x_m=2(1+\gamma )\log (v_{m+1}\mathrm{/}{v}_0)\le 2(1+\gamma )\log (v_k\mathrm{/}{v}_0)$, so step 2.1 bounds every ${\eta }_{m,k}$ by $D_k$. Minkowski's inequality in $L^2(\mathrm{\Omega })$ [F7], applied to the norm functions of the two Hilbert-valued errors, consequently bounds the early-selection contribution by $(\sqrt{R_k}+D_k{)}^2$. For $k=0$, this uses the identically zero difference and hence $D_0=0$.

For $m>k$, the event $\{\widehat{m}=m\}$ implies rejection of $m-1$. Its oracle bias bound from step 1.1 shows that a rejecting comparison with $\mathrm{\ell }\ge m$ must satisfy $\mathrm{\parallel }{G}_{m-1,\mathrm{\ell }}\mathrm{\parallel }>\sigma z_{m-1,\mathrm{\ell }}(x_{m-1})$. The union bound over $M-m+1$ such comparisons and the quantile-tail property from step 2.1 therefore give $\mathbb{P}(\widehat{m}=m)\le p_m$. Similarly $\{\widehat{m}>k\}$ implies rejection of $k$, so $\mathbb{P}(\widehat{m}>k)\le P_k$. Here $e^{-x_{m-1}}=(v_0\mathrm{/}{v}_m{)}^{2(1+\gamma )}$ exactly.

Let $j$ be the first candidate with $v_j\ge r$. For small $s$, $v_0<r<1$, so this index exists and $r\le v_j\le {\theta }_{2}r$. Step 1.2 implies $r\le CsS({\alpha }_j)\mathrm{/}{\alpha }_j$. First ${\alpha }_j\to 0$: otherwise a subsequence bounded away from zero has bounded $S({\alpha }_j)\mathrm{/}{\alpha }_j$, contradicting $r\mathrm{/}s\to \mathrm{\infty }$. In the mild case the function $S(\alpha )\mathrm{/}\alpha$ is comparable to ${\alpha }^{-1-1\mathrm{/}a}$, so the last inequality and $r\asymp s{t}^{-1-1\mathrm{/}a}$ give ${\alpha }_j\le C^{\mathrm{\prime }}t$. In the severe case it is comparable to $h(\alpha )={\alpha }^{-1}(\log (1\mathrm{/}\alpha ){)}^p$. For any fixed $A>1$, $h(At)\mathrm{/}h(t)\to 1\mathrm{/}A$ as $t\downarrow 0$; since $h$ is decreasing for small positive arguments, choosing $A$ larger than the fixed comparison constant gives the same conclusion ${\alpha }_j\le C^{\mathrm{\prime }}t$. Qualification and $\phi (C^{\mathrm{\prime }}t{)}^2\asymp \phi (t{)}^2$ now give $b_j^2\le C^{\mathrm{\prime }\mathrm{\prime }}r$.

Scalar Cauchy–Schwarz [F6] and step 2.1 give $\mathbb{E}[\mathrm{\parallel }{\epsilon }_m{\mathrm{\parallel }}^2{1}_{\{\widehat{m}=m\}}]\le \sqrt{3}{v}_m\sqrt{p_m}$. Summing gives a late selected-noise second moment at most $A_k$. By [F1], the corresponding selected bias has mean-square norm at most $b_k\sqrt{P_k}$. Minkowski's inequality [F7] thus bounds the late risk by $(b_k\sqrt{P_k}+\sqrt{A_k}{)}^2$. Alternatively, $\mathrm{\parallel }{\epsilon }_m+f_m-x{\mathrm{\parallel }}^2\le 2\mathrm{\parallel }{\epsilon }_m{\mathrm{\parallel }}^2+2b_k^2$ and $p_m\le \sqrt{p_m}$ give a late risk bound $2\sqrt{3}{\sum }_{m>k}(v_m+b_k^2)\sqrt{p_m}$. Since $v_m+b_k^2\le (v_m\mathrm{/}{v}_k)R_k$, dropping the minimum in $p_m$ yields exactly $B_k$. Together with step 3.1 these prove the first finite oracle inequality. If $k=M$, both late sums are empty.

Put $c_{\beta }={\beta }^2(\sqrt{{\theta }_1}-1{)}^2>0$ and choose a fixed nonnegative integer $J$ with ${\theta }_1^J\ge C^{\mathrm{\prime }\mathrm{\prime }}\mathrm{/}{c}_{\beta }$. For small $s$, ${\theta }_2^{J+1}r<1$, so the infinite candidate sequence has $\mathrm{\ell }=j+J<M$, $v_{\mathrm{\ell }}\le {\theta }_2^{J+1}r$, and $b_{\mathrm{\ell }}^2\le C^{\mathrm{\prime }\mathrm{\prime }}r\le c_{\beta }{v}_{\mathrm{\ell }}$. For every $\mathrm{\ell }\le a<b$, monotone bias gives $b_{a,b}^2\le b_a^2\le c_{\beta }{v}_a$. The reverse triangle inequality for the square-summable noise coefficient vectors follows from [F7] with counting measure and gives $v_{a,b}\ge (\sqrt{v_b}-\sqrt{v_a}{)}^2\ge (\sqrt{{\theta }_1}-1{)}^2{v}_a$. Thus $b_{a,b}^2\le {\beta }^2{v}_{a,b}$ and $k\le \mathrm{\ell }$. If $k<\mathrm{\ell }$, the oracle property implies $\mathbb{E}\mathrm{\parallel }{\widehat{x}}_k-{\widehat{x}}_{\mathrm{\ell }}{\mathrm{\parallel }}^2\le (1+{\beta }^2)v_{k,\mathrm{\ell }}\le (1+{\beta }^2)v_{\mathrm{\ell }}$. Hence $R_k\le 2(1+{\beta }^2)v_{\mathrm{\ell }}+2R_{\mathrm{\ell }}\le Cr$; the case $k=\mathrm{\ell }$ is immediate. In particular $v_k\le Cr$ and $\log (v_k\mathrm{/}{v}_0)\le CL$.

Suppose $M\ge 1$ and put $w=v_0{M}^{\delta }$. For $f(v)=v\min \{1,\sqrt{M}(v_0\mathrm{/}v{)}^{1+\gamma }\}$ one has $f(v)=v$ for $v\le w$ and $f(v)=w^{1+\gamma }{v}^{-\gamma }$ for $v>w$. The geometric variance lower ratio gives ${\sum }_{v_m\le w}{v}_m\le {\theta }_{1}w\mathrm{/}({\theta }_1-1)$ and ${\sum }_{v_m>w}{v}_m^{-\gamma }\le w^{-\gamma }\mathrm{/}(1-{\theta }_1^{-\gamma })$, by summing the backward and forward geometric series from the respective last and first indices. Thus $A_k\le \sqrt{3}Kw$. Also $v_m\mathrm{/}{v}_k\ge {\theta }_1^{m-k}$ and $\sqrt{M-m+1}\le \sqrt{M}$ in the definition of $B_k$ prove its stated simpler bound. The inequality $(a+b{)}^2\le 2a^2+2b^2$ applied to the first late alternative in step 4.1 gives the rate-oriented oracle bound. If $M=0$, the only index is zero, its risk equals $R_0$, and all late sums vanish as stipulated.

In the mild case the stated lower variance bound gives $v_k\ge cs{\alpha }_k^{-1-1\mathrm{/}a}$. Combined with step 4.2 and $r\asymp s{t}^{-1-1\mathrm{/}a}$, this yields ${\alpha }_k\ge c^{\mathrm{\prime }}t$. Therefore step 1.2 gives $u_k\log (v_k\mathrm{/}{v}_0)\le CsL\mathrm{/}t=o(r)$, because $L{t}^{1\mathrm{/}a}\to 0$. It follows that $D_k^2\le C(v_k+u_k\log (v_k\mathrm{/}{v}_0))\le Cr$ for $k\ge 1$, while $D_0=0$ handles $k=0$.

In the severe case put $H=\log (1\mathrm{/}t)\asymp L$. If ${\alpha }_k\ge t$, then ${\alpha }_k\ge t\mathrm{/}H$ for small $s$. If ${\alpha }_k<t$, the lower variance bound and $S(\alpha )\asymp (\log (1\mathrm{/}\alpha ){)}^p$ give $cs{\alpha }_k^{-1}{H}^{p-1}\le v_k\le Cr\le Cs{t}^{-1}{H}^p$, so again ${\alpha }_k\ge c^{\mathrm{\prime }}t\mathrm{/}H$. Hence $u_k\log (v_k\mathrm{/}{v}_0)\le CsHL\mathrm{/}t\le Cs{H}^2\mathrm{/}t\le Cs{H}^p\mathrm{/}t\asymp Cr$, using exactly $p\ge 2$. Consequently $D_k^2\le Cr$ in this case also, with $D_0=0$ as before.

By step 2.2, $W_M=O(s{L}^{\delta })=o(r)$: when $\nu >0$, $r\mathrm{/}s$ has a strictly positive power of $1\mathrm{/}s$ multiplied by a fixed logarithmic power; when $\nu =0$ and $\tau >0$, $r=L^{-2\tau }$. The rate-oriented oracle bound from step 5.1, together with $R_k\le Cr$, $b_k^2\le R_k$ and the two rate estimates just proved, therefore gives the asserted uniform risk upper bound $Cr$ in each regime. Substituting the explicit expressions for $r$ from step 2.2 gives exactly the two displayed rates and their $\nu =0$ specializations. The severe proof uses $\vartheta \le 1\mathrm{/}2$ at step 5.3 and asserts only the stated upper rate, preserving the given qualification and grid hypotheses. This completes both the finite oracle and rate conclusions.