A comment and erratum on “Excess Optimism: How Biased is the Apparent Error of an Estimator Tuned by SURE?”

We first revisit the setting that Tibshirani and Rosset [4, Sec. 4] consider, when each matrix $H_{s}$ is an orthogonal projector. As a motiviating example, in linear regression, we may take $H_{s}=X_{s}(X_{s}^{T}X_{s})^{-1}X_{s}^{T}$, where $X_{s}$ denotes the submatrix of the design $X\in\mathbb{R}^{n\times p}$ whose columns $s$ indexes. In this case, as $H_{s}^{2}=H_{s}$, we have $\left|\!\left|\!\left|{H_{s}}\right|\!\right|\!\right|_{\rm op}\leq 1$ and $\mathop{\rm tr}(H_{s})=\left\|{H_{s}}\right\|_{\rm Fr}^{2}=p_{s}$. First consider the case that there is $s^{\star}$ satisfying $H_{s^{\star}}\theta_{0}=\theta_{0}$, that is, the true model belongs to the set $S$. Then because $s_{0}$ minimizes $\frac{1}{\sigma^{2}}\left\|{(I-H_{s})\theta_{0}}\right\|_{2}^{2}+p_{s}$, we have

$$\textup{edf}(\widehat{\theta}_{\widehat{s}})\lesssim\sqrt{p_{s^{\star}}\log|S|}+\log|S|\cdot\left(1+\log_{+}\frac{\log|S|}{p_{s^{\star}}}\right).$$

Whenever $p_{s^{\star}}\gtrsim\log|S|$, we have the simplified bound

$$\textup{edf}(\widehat{\theta}_{\widehat{s}})\lesssim\sqrt{p_{s^{\star}}\log|S|}.$$

An alternative way to look at the result is by replacing $r_{\star}$ with $\frac{1}{\sigma^{2}}R(s_{0})=\frac{1}{\sigma^{2}}\min_{s\in S}R(s)$. In this case, combining [4, Thm. 1] with Theorem 1, we obtain

$\displaystyle\textup{Risk}(\widehat{\theta}_{\widehat{s}})$

$\displaystyle\leq R(s_{0})+C\left(\sqrt{R(s_{0})\cdot\sigma^{2}\log|S|}+\sigma^{2}\log|S|\cdot\left(1+\log_{+}\frac{\sigma^{2}\log|S|}{R(s_{0})}\right)\right)$

for a (numerical) constant $C$. In particular, if $\min_{s\in S}\textup{Risk}(\widehat{\theta}_{s})\gtrsim\sigma^{2}\log|S|$, then we obtain that there exists a numerical constant $C$ such that for all $\eta>0$,

$\displaystyle\textup{Risk}(\widehat{\theta}_{\widehat{s}})$

$\displaystyle\leq(1+C\eta)\min_{s\in S}\textup{Risk}(\widehat{\theta}_{s})+C\frac{\sigma^{2}\log|S|}{\eta}.$

(5)

Additional perspective comes by considering some of the bounds Tibshirani and Rosset [4, Sec. 4] develop. While we cannot recover identical results because of the correction term (4) in the excess degrees of freedom, we can recover analogues. As one example, consider their Theorem 2. It assumes that $n\to\infty$ in the sequence model (1), and (implicitly letting $S$ and $s_{0}$ depend on $n$) that $\textup{Risk}(\widehat{\theta}_{s_{0}})/\log|S|\to\infty$. Then inequality (5) immediately gives the oracle inequality $\textup{Risk}(\widehat{\theta}_{\widehat{s}})=(1+o(1))\textup{Risk}(\widehat{\theta}_{s_{0}})$, and Theorem 1 moreover shows that

$$\frac{\textup{edf}(\widehat{\theta}_{\widehat{s}})}{\frac{1}{\sigma^{2}}\textup{Risk}(\widehat{\theta}_{s_{0}})}\lesssim\sqrt{\sigma^{2}\frac{\log|S|}{\textup{Risk}(\widehat{\theta}_{s_{0}})}}\to 0.$$

In brief, Tibshirani and Rosset’s major conclusions on subset regression estimators—and projection estimators more generally—hold, but with a few tweaks.

In more generality, the matrices $H_{s}\in\mathbb{R}^{n\times n}$ defining the estimators may be arbitrary. In common cases, however, they are reasonably well-behaved. Take as motivation nonparametric regression, where $Y_{i}=f(X_{i})+\varepsilon_{i}$, and we let $\theta_{i}=f(X_{i})$ for $i=1,\ldots,n$ and $X_{i}\in\mathcal{X}$, so that $\textup{Risk}(\widehat{\theta})$ measures the in-sample risk of an estimator $\widehat{\theta}$ of $[f(X_{i})]_{i=1}^{n}$. Here, standard estimators include kernel regression and local averaging [2, 6], both of which we touch on.

First consider kernel ridge regression (KRR). For a reproducing kernel $K:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$, the (PSD) Gram matrix $G$ has entries $G_{ij}=K(X_{i},X_{j})$. Then for $\lambda\in\mathbb{R}_{+}$, we define $H_{\lambda}=(G+\lambda I)^{-1}G$, which is symmetric and positive semidefinite, and satisfies $\left|\!\left|\!\left|{H_{\lambda}}\right|\!\right|\!\right|_{\rm op}\leq 1$. Assume the collection $\Lambda\subset\mathbb{R}_{+}$ is finite and define the effective dimension $p_{\lambda}=\mathop{\rm tr}(G(G+\lambda I)^{-1})$, yielding that $\textup{SURE}(\lambda)=\|{Y-H_{\lambda}Y}\|_{2}^{2}+2\sigma^{2}p_{\lambda}$. Then SURE-tuned KRR, with regularization $\widehat{\lambda}=\mathop{\rm argmin}_{\lambda\in\Lambda}\textup{SURE}(\lambda)$ and $\widehat{\theta}_{\widehat{\lambda}}=H_{\widehat{\lambda}}Y$, satisfies

$$\textup{edf}(\widehat{\theta}_{\widehat{\lambda}})\lesssim\sqrt{r_{\star}\log|\Lambda|}+\log|\Lambda|\cdot\left(1+\log_{+}\frac{\log|\Lambda|}{r_{\star}}\right)$$

where as usual, $r_{\star}=\min_{\lambda\in\Lambda}\{\frac{1}{\sigma^{2}}\left\|{(I-H_{\lambda})\theta_{0}}\right\|_{2}^{2}+\mathop{\rm tr}(G(G+\lambda I)^{-1})\}$.

A second example arises from $k$-nearest-neighbor ($k$-nn) estimators. We take $S=\{1,\ldots,n\}$ to indicate the number of nearest neighbors to average, and for $k\in S$ let $\mathcal{N}_{k}(i)$ denote the indices of the $k$ nearest neighbors $X_{j}$ to $X_{i}$ in $\{X_{1},\ldots,X_{n}\}$, so $\mathcal{N}_{k}^{-1}(i)=\{j\mid i\in\mathcal{N}_{k}(j)\}$ are the indices $j$ for which $X_{i}$ is a neighbor of $X_{j}$. Then the matrix $H_{k}\in\mathbb{R}^{n\times n}_{+}$ satisfies $[H_{k}]_{ij}=\frac{1}{k}1\!\left\{j\in\mathcal{N}_{k}(i)\right\}$, and we claim that $\left|\!\left|\!\left|{H_{k}}\right|\!\right|\!\right|_{\rm op}\leq\frac{1}{k}\max_{i}|\mathcal{N}_{k}^{-1}(i)|$. Indeed,

$$[H_{k}^{T}H_{k}]_{ij}=\frac{1}{k^{2}}\sum_{l=1}^{n}1\!\left\{i\in\mathcal{N}_{k}(l),j\in\mathcal{N}_{k}(l)\right\},$$

and as $H_{k}^{T}H_{k}$ is elementwise nonnegative, the Gershgorin circle theorem guarantees

$\displaystyle\left|\!\left|\!\left|{H_{k}}\right|\!\right|\!\right|_{\rm op}^{2}\leq\max_{i\leq n}\sum_{j=1}^{n}[H_{k}^{T}H_{k}]_{ij}$

$\displaystyle\leq\frac{1}{k^{2}}\max_{i\leq n}\sum_{l=1}^{n}\sum_{j=1}^{n}1\!\left\{i\in\mathcal{N}_{k}(l),j\in\mathcal{N}_{k}(l)\right\}\leq\frac{1}{k}\max_{i\leq n}\sum_{l=1}^{n}1\!\left\{i\in\mathcal{N}_{k}(l)\right\}$

as $|\mathcal{N}_{k}(l)|\leq k$ for each $l$. Additionally, we have $\left\|{H_{k}}\right\|_{\rm Fr}^{2}=\frac{nk}{k^{2}}=\frac{n}{k}$. The normalized risk of the $k$-nn estimator is then $r_{k}=\frac{1}{\sigma^{2}}\left\|{(I-H_{k})\theta_{0}}\right\|_{2}^{2}+\frac{n}{k}$, and certainly $r_{k}\geq\log n$ whenever $k\leq\frac{n}{\log n}$. Under a few restrictions, we can therefore obtain an oracle-type inequality: assume the points $\{X_{1},\ldots,X_{n}\}$ are regular enough that $\max_{i}|\mathcal{N}_{k}^{-1}(i)|\lesssim k$ for $k\leq\frac{n}{\log n}$. Then the SURE-tuned $k$-nearest-neighbor estimator $\widehat{\theta}_{k}$ satisfies the bound

$$\textup{edf}(\widehat{\theta}_{\widehat{k}})\lesssim\sqrt{\frac{1}{\sigma^{2}}\min_{k\leq n/\log n}\textup{Risk}(\widehat{\theta}_{k})\cdot\log n}$$

on its excess degrees of freedom. Via inequality (2), this implies the oracle inequality

$$\textup{Risk}(\widehat{\theta}_{\widehat{k}})\leq\min_{k\leq n/\log n}\left(1+C\eta\right)\textup{Risk}(\widehat{\theta}_{k})+\frac{C\sigma^{2}\log n}{\eta}~{}~{}~{}\mbox{for~{}all~{}}\eta>0.$$

Our proof strategy is familiar from high-dimensional statistics [cf. 6, Chs. 7 & 9]: we develop a basic inequality relating the risk of $\widehat{s}$ to that of $s_{0}$, then apply a peeling argument [5] to bound the probability that relative error bounds deviate far from their expectations. Throughout, we let $C$ denote a universal (numerical) constant whose value may change from line to line.

To prove the theorem, we first recall a definition and state two auxiliary lemmas.

Recall the notation $R(s)=\left\|{(H_{s}-I)\theta_{0}}\right\|_{2}^{2}+\sigma^{2}p_{s}$, and for $s\in S$ define the centered variables

$$\begin{split}W_{s}&\coloneqq\frac{1}{\sigma^{2}}Z^{T}(2H_{s}-H_{s}^{T}H_{s})Z+\mathop{\rm tr}(H_{s}^{T}H_{s})-2p_{s},\\ Z_{s}&\coloneqq\frac{1}{\sigma^{2}}\theta_{0}^{T}(H_{s}-I)^{T}(I-H_{s})Z.\end{split}$$

(6)

A quick calculation shows that for every $s\in S$,

$\displaystyle\frac{1}{\sigma^{2}}\textup{SURE}(s)$

$\displaystyle=\frac{1}{\sigma^{2}}R(s)+\frac{1}{\sigma^{2}}\left\|{Z}\right\|_{2}^{2}-W_{s}-2Z_{s}.$

As $\widehat{s}(Y)$ minimizes the SURE criterion, we therefore have the basic inequality

$$\frac{1}{\sigma^{2}}\left(R(\widehat{s}(Y))-R(s_{0})\right)\leq W_{\widehat{s}(Y)}-W_{s_{0}}+2(Z_{\widehat{s}(Y)}-Z_{s_{0}}).$$

(7)

We now provide a peeling argument using inequality (7). For each $l\in\mathbb{N}$ define the shell

$\displaystyle\mathcal{S}_{l}\coloneqq\{s\in S\mid(2^{l}-1)\sigma^{2}r_{\star}\leq R(s)-R(s_{0})\leq(2^{l+1}-1)\sigma^{2}r_{\star}\}.$

The key result is the following lemma.

As promised, we now show that $W_{s}-W_{s_{0}}$ and $Z_{s}-Z_{s_{0}}$ are sub-exponential and sub-Gaussian, respectively (recall Definition 2.1). Observe that

	$\displaystyle\frac{1}{\sigma^{2}}(R(s)-R(s_{0}))$	$\displaystyle=\frac{1}{\sigma^{2}}\left\|{(I-H_{s})\theta_{0}}\right\|_{2}^{2}-\frac{1}{\sigma^{2}}\left\|{(I-H_{s_{0}})\theta_{0}}\right\|_{2}^{2}+\left\|{H_{s}}\right\|_{\rm Fr}^{2}-\left\|{H_{s_{0}}}\right\|_{\rm Fr}^{2}$
		$\displaystyle\geq\left\|{H_{s}}\right\|_{\rm Fr}^{2}-r_{\star}$		(9)

by assumption that $r_{\star}\geq\frac{1}{\sigma^{2}}R(s_{0})=\frac{1}{\sigma^{2}}\left\|{(I-H_{s_{0}})\theta_{0}}\right\|_{2}^{2}+\left\|{H_{s_{0}}}\right\|_{\rm Fr}^{2}$ and that $\left\|{(I-H_{s})\theta_{0}}\right\|_{2}^{2}\geq 0$. In particular, inequality (9) shows that for each $s\in\mathcal{S}_{l}$ we have $\left\|{H_{s}}\right\|_{\rm Fr}^{2}-r_{\star}\leq(2^{l+1}-1)r_{\star}$ (and we always have $\left\|{H_{s_{0}}}\right\|_{\rm Fr}^{2}\leq r_{\star}$), so that

$$\left\|{H_{s}}\right\|_{\rm Fr}^{2}\leq 2^{l+1}r_{\star}~{}~{}~{}\mbox{and}~{}~{}~{}\left\|{H_{s_{0}}}\right\|_{\rm Fr}^{2}\leq r_{\star}~{}~{}~{}\mbox{for~{}}s\in\mathcal{S}_{l}.$$

(10)

For each $s$ we have

$$W_{s}-W_{s_{0}}=\frac{1}{\sigma^{2}}Z^{T}(2H_{s}-2H_{s_{0}}-H_{s}^{T}H_{s}+H_{s_{0}}^{T}H_{s_{0}})Z+\left\|{H_{s}}\right\|_{\rm Fr}^{2}-\left\|{H_{s_{0}}}\right\|_{\rm Fr}^{2}-2(p_{s}-p_{s_{0}}),$$

while

$$\left\|{2H_{s}-2H_{s_{0}}-H_{s}^{T}H_{s}+H_{s_{0}}^{T}H_{s_{0}}}\right\|_{\rm Fr}^{2}\leq 4\cdot\left(4\left\|{H_{s}}\right\|_{\rm Fr}^{2}+4\left\|{H_{s_{0}}}\right\|_{\rm Fr}^{2}+h_{\textup{op}}^{2}\left\|{H_{s}}\right\|_{\rm Fr}^{2}+h_{\textup{op}}^{2}\left\|{H_{s_{0}}}\right\|_{\rm Fr}^{2}\right)$$

by assumption that $\left|\!\left|\!\left|{H_{s}}\right|\!\right|\!\right|_{\rm op}\leq h_{\textup{op}}$ for all $s\in S$. Lemma 2.2 and the bounds (10) on $\left\|{H_{s}}\right\|_{\rm Fr}$ thus give that $W_{s}-W_{s_{0}}$ is $(C\cdot 2^{l}h_{\textup{op}}^{2}r_{\star},C\cdot h_{\textup{op}}^{2})$-sub-exponential, so that for $t\geq 0$, a Chernoff bound implies

$\displaystyle\mathbb{P}\left(\max_{s\in\mathcal{S}_{l}}(W_{s}-W_{s_{0}})\geq t\right)$

$\displaystyle\leq|\mathcal{S}_{l}|\exp\left(C\cdot 2^{l}\lambda^{2}h_{\textup{op}}^{2}r_{\star}-\lambda t\right),$

valid for $0\leq\lambda\leq\frac{1}{Ch_{\textup{op}}}$. Taking $t=\frac{1}{2}(2^{l}-1)r_{\star}$ and $\lambda=\frac{1}{C^{\prime}h_{\textup{op}}^{2}}$ yields that for a numerical constant $c>0$,

$$\mathbb{P}\left(\max_{s\in\mathcal{S}_{l}}(W_{s}-W_{s_{0}})\geq\frac{1}{2}(2^{l}-1)r_{\star}\right)\leq|\mathcal{S}_{l}|\exp\left(-c\frac{2^{l}r_{\star}}{h_{\textup{op}}^{2}}\right).$$

We can provide a similar bound on $Z_{s}-Z_{s_{0}}$ for $s\in\mathcal{S}_{l}$. It is immediate that $Z_{s}\sim\mathsf{N}(0,\frac{1}{\sigma^{2}}\left\|{(H_{s}-I)^{T}(I-H_{s})\theta_{0}}\right\|_{2}^{2})$. Using inequality (9) and that $\frac{1}{\sigma^{2}}\left\|{(I-H_{s_{0}})\theta_{0}}\right\|_{2}^{2}+\left\|{H_{s_{0}}}\right\|_{\rm Fr}^{2}\leq r_{\star}$, for each $s\in\mathcal{S}_{l}$ we have

	$\displaystyle\frac{1}{\sigma^{2}}\left\|{(I-H_{s})\theta_{0}}\right\|_{2}^{2}$	$\displaystyle=\frac{1}{\sigma^{2}}(R(s)-R(s_{0}))+\frac{1}{\sigma^{2}}\left\|{(I-H_{s_{0}})\theta_{0}}\right\|_{2}^{2}+\left\|{H_{s_{0}}}\right\|_{\rm Fr}^{2}-\left\|{H_{s}}\right\|_{\rm Fr}^{2}$
		$\displaystyle\leq r_{\star}(2^{l+1}-1)+r_{\star}-p_{s}\leq 2^{l+1}r_{\star}.$

Similarly, $Z_{s_{0}}\sim\mathsf{N}(0,\frac{1}{\sigma^{2}}\left\|{(H_{s_{0}}-I)^{T}(I-H_{s_{0}})\theta_{0}}\right\|_{2}^{2})$ and $\frac{1}{\sigma^{2}}\left\|{(I-H_{s_{0}})\theta_{0}}\right\|_{2}^{2}\leq r_{\star}$. Using that $\left|\!\left|\!\left|{I-H_{s}}\right|\!\right|\!\right|_{\rm op}\leq(1+h_{\textup{op}})$, for each $s\in\mathcal{S}_{l}$ we have $Z_{s}-Z_{s_{0}}\sim\mathsf{N}(0,\tau^{2}(s))$ for some $\tau^{2}(s)\leq C\cdot h_{\textup{op}}^{2}2^{l}r_{\star}$. This yields the bound

$\displaystyle\mathbb{P}\left(\max_{s\in\mathcal{S}_{l}}(Z_{s}-Z_{s_{0}})\geq\frac{1}{4}r_{\star}(2^{l}-1)\right)$

$\displaystyle\leq|\mathcal{S}_{l}|\exp\left(-c\frac{r_{\star}(2^{l}-1)^{2}}{2^{l}h_{\textup{op}}^{2}}\right)\leq|\mathcal{S}_{l}|\exp\left(-c^{\prime}\frac{2^{l}r_{\star}}{h_{\textup{op}}^{2}}\right),$

where $c,c^{\prime}>0$ are numerical constants. Returning to the events (8), we have shown

	$\displaystyle\mathbb{P}(\widehat{s}(Y)\in\mathcal{S}_{l})$	$\displaystyle\leq\mathbb{P}\left(\max_{s\in\mathcal{S}_{l}}(W_{s}-W_{s_{0}})\geq\frac{1}{2}(2^{l}-1)r_{\star}\right)+\mathbb{P}\left(\max_{s\in\mathcal{S}_{l}}(Z_{s}-Z_{s_{0}})\geq\frac{1}{4}r_{\star}(2^{l}-1)\right)$
		$\displaystyle\leq 2|\mathcal{S}_{l}|\exp\left(-c\frac{2^{l}r_{\star}}{h_{\textup{op}}^{2}}\right)$

as desired. ∎

We leverage the probability bound in Lemma 2.3 to give our final guarantees. We expand Define the (centered) linear and quadratic terms

$$Q_{s}\coloneqq\frac{1}{\sigma^{2}}Z^{T}H_{s}Z-p_{s}~{}~{}~{}\mbox{and}~{}~{}~{}L_{s}\coloneqq\frac{1}{\sigma^{2}}Z^{T}H_{s}\theta_{0},$$

so that $\textup{edf}(\widehat{\theta}_{\widehat{s}})=\mathbb{E}[Q_{\widehat{s}(Y)}]+\mathbb{E}[L_{\widehat{s}(Y)}]$. Expanding this equality, we have

$$\textup{edf}(\widehat{\theta}_{\widehat{s}})=\sum_{l=0}^{\infty}\mathbb{E}[Q_{\widehat{s}(Y)}1\!\left\{\widehat{s}(Y)\in\mathcal{S}_{l}\right\}]+\mathbb{E}[L_{\widehat{s}(Y)}1\!\left\{\widehat{s}(Y)\in\mathcal{S}_{l}\right\}].$$

As in the proof of Lemma 2.3, the bounds (10) that $\left\|{H_{s}}\right\|_{\rm Fr}^{2}\leq 2^{l+1}r_{\star}$ and Lemma 2.2 guarantee that $Q_{s}$ is $(2^{l+3}r_{\star},4h_{\textup{op}})$-sub-exponential. Thus we have

	$\displaystyle\mathbb{E}\left[Q_{\widehat{s}(Y)}1\!\left\{\widehat{s}(Y)\in\mathcal{S}_{l}\right\}\right]$	$\displaystyle\leq\mathbb{E}\left[\max_{s\in\mathcal{S}_{l}}Q_{s}1\!\left\{\widehat{s}(Y)\in\mathcal{S}_{l}\right\}\right]\stackrel{{\scriptstyle(i)}}{{\leq}}\mathbb{E}\left[\max_{s\in\mathcal{S}_{l}}Q_{s}^{2}\right]^{1/2}\mathbb{P}(\widehat{s}(Y)\in\mathcal{S}_{l})^{1/2}$
		$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\lesssim}}\max\left\{\sqrt{2^{l}r_{\star}\log|\mathcal{S}_{l}|},h_{\textup{op}}\log|\mathcal{S}_{l}|\right\}\min\left\{1,\sqrt{|\mathcal{S}_{l}|}\exp\left(-c\frac{2^{l}r_{\star}}{h_{\textup{op}}^{2}}\right)\right\},$

where inequality $(i)$ is Cauchy-Schwarz and inequality $(ii)$ follows by combining Lemma 2.1 (take $k=2$) and Lemma 2.3. We similarly have that $L_{s}$ is $C\cdot 2^{l}r_{\star}$-sub-Gaussian, yielding

$$\mathbb{E}[L_{\widehat{s}(Y)}1\!\left\{\widehat{s}(Y)\in\mathcal{S}_{l}\right\}]\lesssim\sqrt{2^{l}r_{\star}\log|\mathcal{S}_{l}|}\min\left\{1,\sqrt{|\mathcal{S}_{l}|}\exp\left(-c\frac{2^{l}r_{\star}}{h_{\textup{op}}^{2}}\right)\right\}.$$

Temporarily introduce the shorthand $r=\frac{r_{\star}}{h_{\textup{op}}^{2}}$. Substituting these bounds into the $\textup{edf}(\widehat{\theta}_{\widehat{s}})$ expansion above and naively bounding $|\mathcal{S}_{l}|\leq|S|$ yields

	$\displaystyle\textup{edf}(\widehat{\theta}_{\widehat{s}})$
		$\displaystyle\lesssim\sqrt{r_{\star}\log|S|}\int_{0}^{\infty}\sqrt{2^{t}\min\{1,|S|\exp(-c2^{t}r)\}}dt+h_{\textup{op}}\log|S|\int_{0}^{\infty}\sqrt{\min\{1,|S|\exp(-c2^{t}r)\}}dt$
		$\displaystyle\qquad\qquad~{}+\sqrt{r_{\star}\log|S|}+h_{\textup{op}}\log|S|$
		$\displaystyle\lesssim\sqrt{\log|S|}\int_{cr/2}^{\infty}u^{-\frac{1}{2}}\min\{1,\sqrt{|S|}e^{-u}\}du+h_{\textup{op}}\log|S|\int_{cr/2}^{\infty}\frac{1}{u}\min\{1,\sqrt{|S|}e^{-u}\}du$
		$\displaystyle\qquad\qquad~{}+\sqrt{r_{\star}\log|S|}+h_{\textup{op}}\log|S|,$

where we made the substitution $u=c2^{t-1}r$. We break each of the integrals into the regions $\frac{1}{2}cr\leq u\leq\frac{1}{2}\max\{cr,\log|S|\}$ and $u\geq\frac{1}{2}\max\{cr,\log|S|\}$. Thus

$\displaystyle\sqrt{\log|S|}\int_{cr/2}^{\infty}u^{-\frac{1}{2}}\min\{1,\sqrt{|S|}e^{-u}\}du$

$\displaystyle\leq\begin{cases}\sqrt{2}\log|S|+\sqrt{2}&\mbox{if}~{}\log|S|\geq cr\\ \sqrt{2}&\mbox{if~{}}cr\geq\log|S|.\end{cases}$

where we have used $\int_{b}^{\infty}u^{-1/2}e^{-u}du\leq b^{-1/2}e^{-b}$ for $b>0$ and that $\frac{\sqrt{|S|\log|S|}}{\sqrt{cr/2}}\exp(-\frac{1}{2}cr)\leq\sqrt{2}$ whenever $cr\geq\log|S|$. For the second integral, we have

$\displaystyle\log|S|\int_{cr/2}^{\infty}\frac{1}{u}\min\{1,\sqrt{|S|}e^{-u}\}du$

$\displaystyle\leq\begin{cases}\log|S|\cdot\log\frac{\log|S|}{cr}+2&\mbox{if~{}}\log|S|\geq cr\\ 2&\mbox{if}~{}cr\geq\log|S|,\end{cases}$

where we have used that $\int_{b}^{\infty}\frac{1}{u}e^{-u}du\leq e^{-b}/b$ for any $b\geq 0$. Replacing $r=r_{\star}/h_{\textup{op}}^{2}$, Theorem 1 follows.