BIC fitted-value risk bound

Let $S_1,\dots ,S_M$ be the finite ordered support list from [F1]. After the first support is processed, the incumbent has least score and earliest index among minimizers in the first one-element list. If this is true after $j<M$ supports, then the next score either is strictly smaller, in which case replacing the incumbent gives the new least score, or is at least the incumbent score, in which case retaining it preserves the minimum and keeps the earlier index in a tie. Induction proves the invariant through $M$, so the scan terminates and returns the least-scoring support with the stated tie rule.

Let $\widehat{S}$ be the selected support, $k=\mathrm{\mid }\widehat{S}\mathrm{\mid }$, $\widehat{\mu }={\widehat{\mu }}_{\mathrm{B}\mathrm{I}\mathrm{C}}$, and $\mathrm{\Delta }=\widehat{\mu }-X{\theta }^{\ast }$. The support $S^{\ast }$ is a candidate, and $X{\theta }^{\ast }\in V_{S^{\ast }}$. By step 1.1 and [F4], the selected penalized score is no larger than the score of the projection onto $V_{S^{\ast }}$, whose residual is no larger than $\mathrm{\parallel }\epsilon {\mathrm{\parallel }}_2^2$. Thus $\mathrm{\parallel }Y-\widehat{\mu }{\mathrm{\parallel }}_2^2+n{\tau }^{2}k\le \mathrm{\parallel }\epsilon {\mathrm{\parallel }}_2^2+n{\tau }^{2}s\mathrm{.}$ Expanding $Y=X{\theta }^{\ast }+\epsilon$ gives $\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_2^2\le 2⟨\epsilon ,\mathrm{\Delta }⟩+n{\tau }^2(s-k)$.

On the event $\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_2>0$, set $v=\mathrm{\Delta }\mathrm{/}\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_2$. Then $v\in W_{\widehat{S}}:=\mathrm{span}\{X_j:j\in \widehat{S}\cup S^{\ast }\}$, whose dimension is at most $k+s$. Young's inequality $2ab\le 2a^2+b^2\mathrm{/}2$ applied to $a=\mathrm{\mid }⟨\epsilon ,v⟩\mathrm{\mid }$ and $b=\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_2$ yields $\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_2^2\le 2n{\tau }^{2}s+4⟨\epsilon ,v{⟩}^2-2n{\tau }^{2}k\mathrm{.}$ If $\mathrm{\Delta }=0$, no tail event with a positive threshold can occur.

Assume ${\sigma }^2>0$ and fix $t>0$. First consider $k=0$. On the event $\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_2^2>2n{\tau }^{2}s+t$, step 3.1 implies $⟨\epsilon ,v{⟩}^2>t\mathrm{/}4$ for a unit vector in $V_{S^{\ast }}$. By [F6] and [F8], this forces $\mathrm{\parallel }{P}_{V_{S^{\ast }}}\epsilon {\mathrm{\parallel }}_2^2>t\mathrm{/}4$. Since $\dim V_{S^{\ast }}\le s$, [F2] gives, for ${\sigma }^2>0$, $\mathbb{P}(k=0,\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_2^2>2n{\tau }^{2}s+t)\le 2\cdot 6^s{e}^{-t\mathrm{/}(32{\sigma }^2)}\mathrm{.}$

Now fix $1\le k\le d$ and a candidate support $S$ of size $k$. On the event $\{\widehat{S}=S,\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_2^2>2n{\tau }^{2}s+t\}$, step 3.1 forces $⟨\epsilon ,v{⟩}^2>t\mathrm{/}4+n{\tau }^{2}k\mathrm{/}2$ for a unit vector in $W_S=\mathrm{span}\{X_j:j\in S\cup S^{\ast }\}$, whose dimension is at most $k+s$. By [F6] and [F8], this implies $\mathrm{\parallel }{P}_{W_S}\epsilon {\mathrm{\parallel }}_2^2>t\mathrm{/}4+n{\tau }^{2}k\mathrm{/}2$. By [F2], the probability for this support is at most $2\cdot 6^{k+s}\exp \text{\hspace{0.17em}⁣}(-\frac{t}{32{\sigma }^2}-\frac{n{\tau }^{2}k}{16{\sigma }^2})\mathrm{.}$

Union bound over the $\left(\genfrac{}{}{0px}{}{d}{k}\right)$ supports, use [F3], and substitute the specified ${\tau }^2$. Since $n{\tau }^2\mathrm{/}(16{\sigma }^2)=\log 6+2\log (ed)$, the sum over all $k\ge 1$ is at most $2e^{s\log 6-t\mathrm{/}(32{\sigma }^2)}{\sum }_{k=1}^d(ed{)}^{-k}\le 2e^{s\log 6-t\mathrm{/}(32{\sigma }^2)}\mathrm{.}$ The last inequality follows because each summand is at most $(ed{)}^{-1}$, there are $d$ terms, and $d(ed{)}^{-1}=1\mathrm{/}e<1$ by [F5].

Take $t=32{\sigma }^2[s\log 6+\log (4\mathrm{/}\delta )]$ in steps 4.1 and 6.1. Each branch has probability at most $\delta \mathrm{/}2$, so with probability at least $1-\delta$, $\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_2^2\le 2n{\tau }^{2}s+t={\sigma }^2[64s\log (ed)+64s\log 6+32\log 4+32\log (1\mathrm{/}\delta )]\mathrm{.}$ By [F5, F12], $\log (ed)=\log e+\log d=1+\log d\ge 1$ because $e=\exp (1)$, $\log e=1$, and $d\ge 1$. Since $s\ge 1$, the right side is at most $C_0{\sigma }^2[s\log (ed)+\log (1\mathrm{/}\delta )]$. Dividing by $n$ proves the positive-proxy bound. The probability event is for the squared fitted-value loss identified by [F10].

The centered vector proxy assumption is [F7], so [F2] applies to the identity subspace. If ${\sigma }^2=0$, for every integer $j\ge 1$, $\mathbb{P}(\mathrm{\parallel }\epsilon {\mathrm{\parallel }}_2^2>1\mathrm{/}j)=0$. Since $\{\mathrm{\parallel }\epsilon {\mathrm{\parallel }}_2^2>0\}={\bigcup }_{j\ge 1}\{\mathrm{\parallel }\epsilon {\mathrm{\parallel }}_2^2>1\mathrm{/}j\}$, [F9] gives $\epsilon =0$ almost surely. Then $Y=X{\theta }^{\ast }$; the true support has zero residual, and step 1.1 shows that the selected support also has zero residual because ${\tau }^2=0$. Its fitted vector therefore equals $Y=X{\theta }^{\ast }$. Thus the bound also holds in the zero-proxy case.