Converting High-Probability Bounds to Expected Excess Risk

Why Convert a Probability Guarantee?

A high-probability risk guarantee says that an estimator performs well on most samples. An expected guarantee measures its average performance over repeated samples. These are related, but a small probability of a very large error can matter substantially to the average. Converting one guarantee into the other therefore requires accounting for the size of the excess risk on the exceptional event, or controlling how quickly its tail decays.

Let $\mathcal F$ be a class of predictors, let $R(f)$ denote the risk of $f$, and define the best-in-class risk by $R^*=\inf_{f\in\mathcal F}R(f)$. Suppose $\widehat f$ is a random estimator and $R(\widehat f)$ is measurable. The membership condition below is essential: without it, the difference from the best risk in $\mathcal F$ need not be nonnegative.

Definition: Assume $R^*$ is finite, $R(\widehat f)$ is finite almost surely, and $\widehat f\in\mathcal F$ almost surely. The excess risk is the random variable $Z=R(\widehat f)-R^*$. Since $R^*$ is the infimum over $\mathcal F$, these assumptions imply $Z\geq 0$ almost surely. The expected excess risk is $E[Z]$, when this expectation is defined, possibly as $+\infty$.

A probability guarantee often has the form $P(Z\leq r_\delta)\geq 1-\delta$, where $0<\delta<1$ and $r_\delta$ is a bound at confidence level $1-\delta$. The guarantee says little by itself about the values of $Z$ on the remaining event of probability at most $\delta$. The next results make clear what additional information is enough.

The Tail-Integral Identity

The basic conversion tool is an identity for any nonnegative random variable. It expresses the mean as the total area under the survival-probability curve.

Theorem (Tail-Integral Identity): If $Z\geq 0$ is a measurable random variable, then $$ E[Z]=\int_0^\infty P(Z>t)\,dt, $$ where either side may be infinite.

Proof. For every fixed outcome, the length of the interval of values $t\geq 0$ satisfying $t<Z$ is exactly $Z$. Thus $$ Z=\int_0^\infty \mathbf{1}\{t<Z\}\,dt. $$ The integrand is a nonnegative measurable function of the outcome and $t$. Tonelli's theorem therefore permits interchange of expectation and integration without assuming in advance that $E[Z]$ is finite. Since $E[\mathbf{1}\{t<Z\}]=P(Z>t)$, we obtain $$ E[Z]=\int_0^\infty E[\mathbf{1}\{t<Z\}]\,dt =\int_0^\infty P(Z>t)\,dt. $$ $\square$

In particular, if a measurable function $\psi:[0,\infty)\to[0,1]$ satisfies $P(Z>t)\leq\psi(t)$ for all $t\geq0$, then $E[Z]\leq\int_0^\infty\psi(t)\,dt$. If that tail control is known only for $t\geq t_0$, use $P(Z>t)\leq1$ below $t_0$ to get $E[Z]\leq t_0+\int_{t_0}^\infty\psi(t)\,dt$. A finite integral gives a finite expected excess risk.

Bounded Excess Risk and a High-Probability Bound

A particularly direct conversion applies when the excess risk cannot exceed a known constant. This condition may follow, for example, when risks in the predictor class lie in a known bounded interval. It must be established for the excess risk itself; it does not follow merely from having a high-probability bound.

Theorem: Suppose $0\leq Z\leq B$ almost surely for a finite constant $B$, and $P(Z\leq r_\delta)\geq1-\delta$. Then $$ E[Z]\leq r_\delta+B\delta. $$

Proof. Let $A=\{Z\leq r_\delta\}$. On $A$, $Z\leq r_\delta$; on its complement, $Z\leq B$. Therefore $$ E[Z]=E[Z\mathbf{1}_A]+E[Z\mathbf{1}_{A^c}] \leq r_\delta P(A)+B P(A^c) \leq r_\delta+B\delta. $$ Here $P(A)\leq1$ and $P(A^c)\leq\delta$. $\square$

The result separates two contributions: the typical error $r_\delta$ and the maximum possible contribution $B\delta$ from the exceptional event. If a family of bounds is available for every $\delta$, one can choose the confidence level to balance these terms. The bound is valid even when $r_\delta>B$, though then it may be loose.

Worked Example: A Bounded Excess Risk

Consider two predictors, $f_0$ and $f_1$, with risks $R(f_0)=0.20$ and $R(f_1)=0.35$. A sample-dependent procedure selects $f_1$ with probability $0.10$ and $f_0$ with probability $0.90$. Its output always belongs to $\mathcal F=\{f_0,f_1\}$, and the best-in-class risk is $R^*=0.20$.

The excess risk is $Z=0$ when $f_0$ is selected and $Z=0.35-0.20=0.15$ when $f_1$ is selected. Thus $0\leq Z\leq B=0.15$, and $P(Z\leq0)=0.90$. Taking $r_{0.10}=0$ and $\delta=0.10$, the theorem gives $$ E[Z]\leq 0+(0.15)(0.10)=0.015. $$ Direct calculation checks the bound: $E[Z]=(0)(0.90)+(0.15)(0.10)=0.015$. The example also shows why membership in $\mathcal F$ matters: it makes the excess risk nonnegative relative to the infimum over that class.

Integrating an Explicit Tail Bound

A known upper bound on the tail can replace boundedness. The next result is an immediate consequence of the tail-integral identity, but its conditions are important: the upper bound must hold across the range of thresholds being integrated, and its integral must be finite for the conclusion to be informative.

Theorem: Let $Z\geq0$ be measurable. If $P(Z>t)\leq\psi(t)$ for every $t\geq0$, where $\psi$ is measurable and takes values in $[0,1]$, then $$ E[Z]\leq\int_0^\infty\psi(t)\,dt. $$

Proof. By the tail-integral identity and the assumed pointwise bound, $$ E[Z]=\int_0^\infty P(Z>t)\,dt \leq\int_0^\infty\psi(t)\,dt. $$ The inequality also holds if the integral on the right is infinite. $\square$

Often the available result is indexed by confidence level rather than threshold: for each $s\geq0$, suppose $P(Z>b(s))\leq e^{-s}$, where $b(s)$ is increasing, differentiable, and unbounded. Then thresholds $t=b(s)$ have tail probability at most $e^{-s}$. Integrating this tail uses $dt=b'(s)\,ds$. The following example carries out that conversion for a commonly occurring square-root form.

Worked Example: Integrating an Exponential Confidence Bound

Let $T$ have an exponential distribution with mean $1$, so $P(T>s)=e^{-s}$ for $s\geq0$. Define a nonnegative excess-risk variable by $$ Z=2\sqrt{\frac{2+T}{100}}. $$ For every $s\geq0$, the threshold $b(s)=2\sqrt{(2+s)/100}$ satisfies $P(Z>b(s))=P(T>s)=e^{-s}$. We now derive an expected-risk bound from this entire family of tail statements.

At $s=0$, $b(0)=2\sqrt{2/100}$. Since $b$ increases, the tail-integral identity gives $$ E[Z]=\int_0^{b(0)}P(Z>t)\,dt+\int_{b(0)}^\infty P(Z>t)\,dt \leq b(0)+\int_0^\infty e^{-s}b'(s)\,ds. $$ The first integral is at most $b(0)$, because probabilities are at most $1$. Differentiating the threshold gives $b'(s)=1/(10\sqrt{2+s})$, so $b'(s)\leq1/(10\sqrt{2})$ for all $s\geq0$. Hence $$ E[Z]\leq 2\sqrt{\frac{2}{100}}+\frac{1}{10\sqrt{2}}\int_0^\infty e^{-s}\,ds =\frac{2\sqrt{2}}{10}+\frac{1}{10\sqrt{2}} \approx 0.3536. $$ The conversion works because the confidence statement is available for every $s$, giving enough information to control the whole tail, not just one exceptional event.

From a Confidence-Indexed Rate to an Expected Rate

A typical high-probability result has $b(s)=A\sqrt{(c+s)/n}$, where $A>0$, $c>0$, and $n$ is the sample size, with $P(Z>b(s))\leq e^{-s}$ for every $s\geq0$. The same integration gives a convenient general expression. The threshold at $s=0$ is $A\sqrt{c/n}$, and $$ b'(s)=\frac{A}{2\sqrt{n}\sqrt{c+s}}\leq\frac{A}{2\sqrt{nc}}. $$ Consequently, $$ E[Z]\leq A\sqrt{\frac{c}{n}}+\frac{A}{2\sqrt{nc}}. $$ For example, when $c=2$, $A=2$, and $n=100$, this bound is $2\sqrt{2/100}+2/(2\sqrt{200)}$, which is approximately $0.3536$, as in the preceding example. The constants may be conservative; the point is that the expected bound follows from integration of the full confidence-indexed tail.

Alternatively, if a bounded-excess-risk argument applies and the high-probability rate is $r_\delta=C\sqrt{(d+\log(1/\delta))/n}$, one may select $\delta=1/n$ for $n>1$. With $Z\leq B$, the bounded-risk theorem yields $$ E[Z]\leq C\sqrt{\frac{d+\log n}{n}}+\frac{B}{n}. $$ This route retains a small exceptional-event term. The integrated-tail route and the bounded-risk route use different assumptions, so one should use whichever matches the available guarantee.

Why One Confidence Level Is Not Enough

A single high-probability statement does not generally control expected excess risk when the exceptional values are unbounded. For any fixed $\delta\in(0,1)$, consider a class containing predictors $f_0$ and $f_M$ with risks $0$ and $M$, respectively. Suppose the estimator selects $f_M$ with probability $\delta$ and $f_0$ otherwise. Then $P(Z\leq0)=1-\delta$, but $E[Z]=\delta M$. As $M$ increases, the expectation is arbitrarily large while the same confidence statement remains true. A tail condition across thresholds or a bound on the exceptional values is therefore substantive, not a technical convenience.

Worked Example: A Fixed-Confidence Bound with Uncontrolled Mean

Take $\delta=0.01$, let $R(f_0)=0$ and $R(f_M)=1000$, and select $f_M$ with probability $0.01$. The estimator belongs to $\{f_0,f_M\}$ on every sample, and the best-in-class risk is $R^*=0$. Thus $Z$ equals $1000$ with probability $0.01$ and $0$ with probability $0.99$.

The fixed-confidence statement $P(Z\leq0)\geq0.99$ holds exactly, yet $$ E[Z]=(0)(0.99)+(1000)(0.01)=10. $$ Replacing $1000$ by any larger finite risk makes the expectation arbitrarily large without changing the confidence statement. This is why one cannot infer a useful expectation bound from that statement alone.

Common Mistakes and Practical Use

Omitting estimator membership. If $\widehat f$ can fall outside $\mathcal F$, $R(\widehat f)-\inf_{f\in\mathcal F}R(f)$ can be negative. State $\widehat f\in\mathcal F$ almost surely before treating this difference as a nonnegative excess risk.
Ignoring the exceptional event. A bound that holds with probability $1-\delta$ does not mean the error is zero, or small, on the remaining event. Bound its magnitude or integrate a valid tail bound.
Integrating a confidence statement outside its range. A result for one $\delta$ controls only one threshold. To integrate, establish a bound over all thresholds of interest, or have a confidence-indexed family that can be inverted.
Calling an infinite integral an expectation guarantee. The tail-integral identity remains valid when the expectation is infinite. A useful finite upper bound requires an integrable tail envelope or another suitable control.

Expected excess risk is useful when performance is assessed over repeated samples or when a learning procedure is compared by its average risk. High-probability guarantees remain valuable for reliability statements about a particular run. Neither form automatically replaces the other: boundedness or tail decay supplies the bridge, and checking that assumption is part of the argument.

Check Your Understanding

Use nonnegativity and the tail behavior explicitly in each answer.

Why must $\widehat f\in\mathcal F$ almost surely to conclude $R(\widehat f)-R^*\geq0$?
If $0\leq Z\leq B$ and $P(Z\leq r_\delta)\geq1-\delta$, derive an upper bound for $E[Z]$.
Suppose $P(Z>t)\leq e^{-t}$ for $t\geq0$. Use the tail-integral identity to bound $E[Z]$.
Give a two-risk example in which a fixed-confidence guarantee holds but the expected excess risk can be made arbitrarily large.
For a confidence-indexed bound $P(Z>A\sqrt{(c+s)/n})\leq e^{-s}$, identify the threshold at $s=0$ and the derivative used to integrate the remaining tail.