Loss Tails And Finite-Class Selection Guarantees

Why the Tail Assumption Matters

Selecting a predictor from a finite dictionary means comparing empirical losses with their population risks. The selected predictor can look unusually good simply because its observed losses fluctuate downward. How large that fluctuation can be depends on the tails of the losses. Boundedness and sub-Gaussian tails support penalties that grow logarithmically with the number of candidates; a finite-variance assumption alone generally gives a weaker penalty for the ordinary empirical-risk selector.

The goal here is to make that distinction explicit. We consider a fixed finite collection of predictors evaluated on independent, identically distributed observations. The resulting bounds are high-probability oracle inequalities: they compare the selected predictor's risk with the smallest risk available in the dictionary, without claiming that the dictionary contains an optimal predictor among all possible procedures.

Setup and a Selection Inequality

Let $Z_1,\ldots,Z_n$ be independent observations from a common distribution. A fixed dictionary contains $M\geq 1$ predictors, indexed by $j\in\{1,\ldots,M\}$. Write $\ell_j(Z_i)$ for predictor $j$'s loss on observation $Z_i$, and define its risk and empirical risk by

R_j=E[\ell_j(Z_1)],\qquad \widehat R_j=\frac{1}{n}\sum_{i=1}^n \ell_j(Z_i).

Assume these expectations are finite. An empirical risk minimizer is any index $\hat j$ satisfying $\widehat R_{\hat j}=\min_{1\leq j\leq M}\widehat R_j$; ties can be resolved by any fixed rule. The oracle risk in the dictionary is $\min_j R_j$.

Selection inequality: For any realized collection of empirical and population risks, let $D=\max_{1\leq j\leq M}|\widehat R_j-R_j|$. Then every empirical risk minimizer satisfies $$ R_{\hat j}\leq \min_{1\leq j\leq M}R_j+2D. $$

To prove it, fix any dictionary index $k$. By the definition of $D$, $R_{\hat j}\leq\widehat R_{\hat j}+D$. Empirical minimization gives $\widehat R_{\hat j}\leq\widehat R_k$, and again by the definition of $D$, $\widehat R_k\leq R_k+D$. Thus $R_{\hat j}\leq R_k+2D$. This holds for every $k$, so taking the minimum over $k$ proves the inequality. $\square$

This elementary inequality separates selection from concentration. To obtain an oracle guarantee, it remains to control all the empirical-risk deviations at once. The required tail assumption determines the size of that uniform deviation.

Bounded Losses: Hoeffding-Scale Deviations

Suppose there are constants $a<b$ such that, for every dictionary member $j$, $\ell_j(Z_1)\in[a,b]$ almost surely. Write $B=b-a$ for the common range width. The bounded-loss guarantee follows from Hoeffding's inequality, which in this setting gives

P\left(|\widehat R_j-R_j|>t\right) \leq 2\exp\left(-\frac{2nt^2}{B^2}\right).

For completeness, the exponential bound rests on Hoeffding's lemma: if a mean-zero random variable $W$ lies in an interval of width $B$, then $E[\exp(\lambda W)]\leq\exp(\lambda^2B^2/8)$ for every real $\lambda$. To see the lemma, let $g(\lambda)=\log E[\exp(\lambda W)]$. Boundedness permits differentiation, and $g''(\lambda)$ is the variance of $W$ under the exponentially tilted distribution. Any distribution supported on an interval of width $B$ has variance at most $B^2/4$: its variance is no greater than its mean squared distance from the interval midpoint, which is at most $B^2/4$. Since $g(0)=g'(0)=0$, integrating this bound on the second derivative gives $g(\lambda)\leq\lambda^2B^2/8$. Applying the lemma to independent centered losses, then using Markov's inequality and optimizing over $\lambda$, gives each one-sided tail $\exp(-2nt^2/B^2)$, and hence the displayed two-sided inequality.

Theorem (bounded-loss finite-class guarantee): If the observations are independent and identically distributed, the dictionary is fixed, and every loss lies almost surely in a common interval of width $B$, then for every $0<\delta<1$, with probability at least $1-\delta$, $$ R_{\hat j}\leq \min_{1\leq j\leq M}R_j +B\sqrt{\frac{2\log(2M/\delta)}{n}}. $$

Indeed, a union bound over the $M$ predictors gives $P(D>t)\leq 2M\exp(-2nt^2/B^2)$. Choosing $t=B\sqrt{\log(2M/\delta)/(2n)}$ makes this probability at most $\delta$. On the complementary event, the selection inequality gives an excess risk of at most $2t$, which is the stated penalty. $\square$

Worked Example: Bounded Losses for Eight Candidates

Suppose $M=8$, $n=200$, and all losses lie in $[0,1]$, so $B=1$. For confidence level $1-\delta=0.95$, the bounded-loss oracle penalty is

\sqrt{\frac{2\log(2M/\delta)}{n}} = \sqrt{\frac{2\log(16/0.05)}{200}} = \sqrt{\frac{2\log(320)}{200}}.

Since $\log(320)\approx5.7683$, the quantity under the square root is approximately $11.5366/200=0.057683$, and its square root is approximately $0.2402$. Thus, with probability at least $0.95$, the selected risk is no more than the best dictionary risk plus about $0.2402$. This is a guarantee, not a prediction that the observed excess risk will equal that amount.

Sub-Gaussian Loss Fluctuations

Boundedness is sufficient for concentration but is not necessary. A loss can be unbounded and still have controlled fluctuations around its mean. We say that a centered random variable $U$ is sub-Gaussian with scale $\sigma$ if

E[\exp(\lambda U)]\leq \exp\left(\frac{\lambda^2\sigma^2}{2}\right) \quad\text{for every }\lambda\in\mathbb{R}.

Assume that for every $j$, $\ell_j(Z_1)-R_j$ is sub-Gaussian with the same scale $\sigma$. Independence across observations implies that the average deviation $\widehat R_j-R_j$ is sub-Gaussian with scale $\sigma/\sqrt n$: its moment generating function is the product of the individual moment generating functions evaluated at $\lambda/n$. Chernoff's bound, optimized over $\lambda$, therefore gives

P\left(|\widehat R_j-R_j|>t\right) \leq 2\exp\left(-\frac{nt^2}{2\sigma^2}\right).

A union bound and the selection inequality now give, with probability at least $1-\delta$,

R_{\hat j}\leq \min_{1\leq j\leq M}R_j +2\sigma\sqrt{\frac{2\log(2M/\delta)}{n}}.

The factor of two outside the deviation radius comes from comparing the selected predictor and a best-risk comparator. The sub-Gaussian condition concerns centered losses, not necessarily losses bounded below or above. For bounded losses of range width $B$, Hoeffding's lemma supplies sub-Gaussian scale $B/2$, recovering the bounded-loss penalty above.

Worked Example: Unbounded Sub-Gaussian Loss Fluctuations

Suppose a fixed dictionary has $M=5$ predictors. Each centered loss is sub-Gaussian with scale $\sigma=0.5$, and $n=400$. At confidence level $0.90$, $\delta=0.10$, so $2M/\delta=100$. The deviation radius for one predictor is

t=0.5\sqrt{\frac{2\log(100)}{400}} =0.5\sqrt{\frac{9.2103}{400}} \approx 0.5(0.1517) \approx 0.0759.

The selection penalty is $2t\approx0.1517$. Thus, with probability at least $0.90$, the empirical risk minimizer has risk at most the best risk in this dictionary plus approximately $0.1517$. The calculation uses the assumed scale of the centered loss; it does not require a bound on the loss itself.

Finite Variance: A Weaker Guarantee

Now suppose only that each loss has finite variance, with $\operatorname{Var}(\ell_j(Z_1))\leq v$ for every $j$. Independence across observations gives $\operatorname{Var}(\widehat R_j)=\operatorname{Var}(\ell_j(Z_1))/n\leq v/n$. Chebyshev's inequality then yields

P\left(|\widehat R_j-R_j|>t\right)\leq\frac{v}{nt^2}.

A union bound gives $P(D>t)\leq Mv/(nt^2)$. Set $t=\sqrt{Mv/(n\delta)}$, and apply the selection inequality on the event $D\leq t$. This proves the following guarantee.

Theorem (finite-variance finite-class guarantee): If observations are independent and identically distributed, the dictionary is fixed, and every loss has variance at most $v<\infty$, then for every $0<\delta<1$, with probability at least $1-\delta$, $$ R_{\hat j}\leq \min_{1\leq j\leq M}R_j +2\sqrt{\frac{Mv}{n\delta}}. $$

This bound does not require bounded or sub-Gaussian losses. Its penalty, however, grows like $\sqrt{M}$ rather than $\sqrt{\log M}$, and like $1/\sqrt{\delta}$ rather than $\sqrt{\log(1/\delta)}$. Those differences arise from using Chebyshev's inequality with only a variance assumption; they are not typographical changes to the bounded-loss result.

Worked Example: Comparing the Cost of a Variance-Only Assumption

Let $M=4$, $n=100$, and suppose every loss has variance at most $v=0.09$. For $\delta=0.05$, the finite-variance penalty is

2\sqrt{\frac{Mv}{n\delta}} = 2\sqrt{\frac{4(0.09)}{100(0.05)}} = 2\sqrt{\frac{0.36}{5}} = 2\sqrt{0.072} \approx 2(0.2683) \approx 0.5367.

Consequently, the risk of the empirical risk minimizer is at most the best dictionary risk plus approximately $0.5367$, with probability at least $0.95$. This can be much looser than a logarithmic-cardinality guarantee, but the assumption used is correspondingly weaker: finite variance alone does not justify the bounded or sub-Gaussian deviation radius.

Reading the Guarantees Correctly

The three bounds have the same selection structure: a concentration radius controls the largest empirical-risk error, and the selection inequality turns that radius into an oracle penalty. The assumptions differ in how effectively they control that largest error.

Loss assumption	Deviation control used	Order of the selection penalty
Common bounded range of width $B$	Hoeffding exponential tail	$B\sqrt{\log(M/\delta)/n}$
Centered sub-Gaussian losses with scale $\sigma$	Sub-Gaussian exponential tail	$\sigma\sqrt{\log(M/\delta)/n}$
Variance at most $v$	Chebyshev inequality and union bound	$\sqrt{Mv/(n\delta)}$

These are guarantees for a fixed dictionary. If candidates are constructed using the same observations on which their empirical risks are evaluated, the fixed-dictionary argument does not automatically apply: the candidate losses may then depend on the sample in a way that invalidates the stated union-bound analysis. A conditional argument or another complexity control would be needed.

Common mistake: A finite variance is sometimes treated as if it automatically gave the sub-Gaussian bound, perhaps by substituting the standard deviation for $\sigma$. That substitution is not valid. The sub-Gaussian condition controls the moment generating function at every real $\lambda$, while a variance bound controls only a second moment. Heavy-tailed distributions can have finite variance and fail to have a finite moment generating function for positive $\lambda$. With only the variance assumption, the Chebyshev-based guarantee is justified; a sharper result needs additional assumptions or a different procedure.

Key takeaway: For finite-class empirical risk selection, identify the loss-tail assumption before choosing a deviation penalty. Bounded or sub-Gaussian losses support a logarithmic dependence on dictionary size; finite variance alone gives a weaker Chebyshev-based guarantee for the ordinary empirical risk minimizer.

Check Your Understanding

For each question, distinguish the oracle comparison from the tail assumption used to justify its penalty.

Why does the deterministic selection inequality contain twice the maximum empirical-risk deviation?
What assumptions are needed to use the bounded-loss guarantee, and how does its penalty depend on $M$ and $n$?
Can the sub-Gaussian guarantee apply when losses are unbounded? State the condition it requires.
Under a variance-only assumption, which inequality controls each candidate's empirical-risk deviation, and why does the union bound introduce a factor involving $M$?
Why is it invalid to use the sub-Gaussian penalty merely because each loss has finite variance?

Loss assumption	Deviation control used	Order of the selection penalty
Common bounded range of width \(B\)	Hoeffding exponential tail	\(B\sqrt{\log(M/\delta)/n}\)
Centered sub-Gaussian losses with scale \(\sigma\)	Sub-Gaussian exponential tail	\(\sigma\sqrt{\log(M/\delta)/n}\)
Variance at most \(v\)	Chebyshev inequality and union bound	\(\sqrt{Mv/(n\delta)}\)