High-Probability Risk Bounds From Sequential Guarantees

From Sequential Performance to Population Risk

An online learner is evaluated round by round, while a batch learner is evaluated on a fresh observation from the data-generating distribution. A regret bound controls the learner's observed losses relative to a comparator on the sample that arrived. It does not, by itself, control population risk: observed losses fluctuate around their conditional expectations. A high-probability batch guarantee therefore needs two ingredients: a high-probability sequential guarantee and a concentration bound for that fluctuation.

The distinction matters even when the observations are iid. At round $t$, the predictor $h_t$ may depend on all earlier observations, so its loss and the data are not independent as a pair. The right concentration argument treats $h_t$ as chosen from the past and uses the fresh, independent observation $Z_t$ at that round.

Definition: Let $Z_1,\ldots,Z_n$ be iid observations with distribution $P$, and let $\mathcal F_{t-1}$ contain the learner's history before $Z_t$ is observed. A predictor $h_t$ is predictable if it is measurable with respect to $\mathcal F_{t-1}$. For a loss $\mathcal L(h,z)$, define its population risk by $R(h)=E_{Z\sim P}[\mathcal L(h,Z)]$, whenever this expectation exists. Conditional on $\mathcal F_{t-1}$, the mean loss of $h_t$ is $R(h_t)$.

For the basic result, assume the loss takes values in $[0,1]$, each $h_t$ is predictable, and the comparator $h^*$ is fixed before the observations. A comparator chosen using information independent of the observations is also allowed, provided that this information is included in every $\mathcal F_{t-1}$. Suppose the sequential guarantee states that, with probability at least $1-\delta_R$,

\sum_{t=1}^n \bigl\{\mathcal L(h_t,Z_t)-\mathcal L(h^*,Z_t)\bigr\} \leq B_n(\delta_R).

The guarantee may come from an online algorithm's regret analysis; here it is taken as an input. We now derive the additional step needed to replace the observed loss difference by a population-risk difference.

The Concentration Step

Write the observed excess loss and its conditional mean as

X_t=\mathcal L(h_t,Z_t)-\mathcal L(h^*,Z_t), \qquad \mu_t=R(h_t)-R(h^*), \qquad D_t=X_t-\mu_t.

Because $h_t$ is determined before $Z_t$ is observed and $Z_t$ is independent of the past, $E[D_t\mid\mathcal F_{t-1}]=0$. Also $X_t\in[-1,1]$, so conditionally its range has length at most $2$. The martingale differences $D_t$ therefore have controlled tails. The following result gives the precise allowance used below.

Theorem: Under the bounded-loss and predictability conditions above, for every $a>0$, $$ P\!\left(\sum_{t=1}^n D_t\leq-a\right) \leq \exp\!\left(-\frac{a^2}{2n}\right). $$ In particular, with probability at least $1-\delta_C$, $$ \sum_{t=1}^n D_t\geq-\sqrt{2n\log(1/\delta_C)}. $$

Proof. Hoeffding's lemma says that if a random variable $U$ has conditional mean zero and, conditionally, lies in an interval of length $c$, then $E[\exp(\lambda U)\mid\mathcal F]\leq\exp(\lambda^2c^2/8)$ for every real $\lambda$. Apply it conditionally to $D_t$, whose interval has length at most $2$. Iterated conditional expectation then gives, for every $\lambda>0$,

E\exp\!\left(-\lambda\sum_{t=1}^nD_t\right) \leq \exp\!\left(\frac{n\lambda^2}{2}\right).

Markov's inequality bounds the probability in the theorem by $\exp(-\lambda a+n\lambda^2/2)$. Choosing $\lambda=a/n$ gives $\exp(-a^2/(2n))$. Setting $a=\sqrt{2n\log(1/\delta_C)}$ makes this probability at most $\delta_C$. $\square$

The population excess summed over the rounds is $\sum_t\mu_t=\sum_tX_t-\sum_tD_t$. Thus an upper bound on observed regret becomes an upper bound on cumulative conditional risk excess when the martingale fluctuation is not too negative.

Theorem: Suppose the sequential regret guarantee above holds with probability at least $1-\delta_R$. Under the iid, predictability, and bounded-loss assumptions, with probability at least $1-\delta_R-\delta_C$, $$ \frac{1}{n}\sum_{t=1}^n\{R(h_t)-R(h^*)\} \leq \frac{B_n(\delta_R)+\sqrt{2n\log(1/\delta_C)}}{n}. $$ If the hypothesis domain is convex, the output $\bar h_n=n^{-1}\sum_{t=1}^n h_t$ is admissible, and $h\mapsto\mathcal L(h,z)$ is convex for every $z$, then the same right-hand side bounds $R(\bar h_n)-R(h^*)$.

Proof. By the concentration result, outside an event of probability at most $\delta_C$, $-\sum_tD_t\leq\sqrt{2n\log(1/\delta_C)}$. On the intersection of this event with the regret event,

\sum_{t=1}^n\mu_t =\sum_{t=1}^nX_t-\sum_{t=1}^nD_t \leq B_n(\delta_R)+\sqrt{2n\log(1/\delta_C)}.

The union bound says that the intersection has probability at least $1-\delta_R-\delta_C$. Dividing by $n$ proves the average-risk statement. For the averaged predictor, convexity gives $\mathcal L(\bar h_n,z)\leq n^{-1}\sum_t\mathcal L(h_t,z)$ for every $z$. Integrating this pointwise inequality against $P$, conditional on the training data, yields $R(\bar h_n)\leq n^{-1}\sum_tR(h_t)$. Subtract $R(h^*)$ and apply the average-risk bound. $\square$

Worked Conversions

Worked Example: Allocating the Failure Probability

Suppose $n=50$, the loss is bounded in $[0,1]$, and the online analysis supplies the valid regret bound $B_{50}(\delta_R)=2\sqrt{2(50)\log(1/\delta_R)}$. Choose $\delta_R=\delta_C=0.05$. Compute a batch risk bound for the averaged predictor, assuming the convexity conditions of the theorem.

The total failure probability is at most $0.05+0.05=0.10$, so the guarantee has confidence at least $0.90$. Since $\log(20)\approx2.995732$, the regret allowance is

B_{50}(0.05)=2\sqrt{2(50)\log(20)} =2\sqrt{100\log(20)} \approx34.62.

The theorem's sharper bounded-loss concentration allowance is $\sqrt{100\log(20)}\approx17.31$. For a deliberately conservative illustration, we may instead use the larger valid allowance $C_{50}(0.05)=2\sqrt{2(50)\log(20)}\approx34.62$. The resulting risk bound is

R(\bar h_{50})-R(h^*) \leq\frac{34.6164+34.6164}{50} \approx1.3847.

The unrounded expression is $4\sqrt{100\log(20)}/50\approx1.38465$. This is a valid but loose bound; a risk difference can never exceed $1$ under $[0,1]$-valued losses, so in this particular setting the bound can be capped at $1$. Keeping the looser calculation visible illustrates how the two allowances combine.

Worked Example: A Conditional Sub-Gaussian Tail Assumption

Bounded losses are sufficient, but not necessary. Suppose instead the centered differences satisfy, for every real $\lambda$,

E[\exp(\lambda D_t)\mid\mathcal F_{t-1}] \leq\exp(\lambda^2v_t/2), \qquad \sum_{t=1}^n v_t\leq V\quad\text{almost surely},

where $v_t$ are predictable and $V$ is a deterministic constant. Iterating the conditional moment bounds gives $E\exp(-\lambda\sum_tD_t)\leq\exp(\lambda^2V/2)$. Markov's inequality and the choice $\lambda=a/V$ yield $P(\sum_tD_t\leq-a)\leq\exp(-a^2/(2V))$. Thus the concentration allowance is $\sqrt{2V\log(1/\delta_C)}$.

For example, let $n=100$, $V=25$, $\delta_R=0.02$, and $\delta_C=0.01$, and suppose the online regret bound is $B_{100}(0.02)=20$. The joint guarantee has probability at least $1-0.02-0.01=0.97$. The concentration allowance is

\sqrt{2(25)\log(100)} =\sqrt{50\log(100)} \approx15.1743.

Consequently the average risk excess, and the averaged predictor's risk excess when the convexity conditions hold, is at most $(20+15.1743)/100\approx0.3517$. The tail assumption is on the centered online-minus-comparator loss difference, conditional on the past; an unconditional variance statement alone does not establish this bound.

Worked Example: Why an Average-Risk Bound Does Not Automatically Cover a Random Iterate

Suppose ten candidate predictors have excess risks $R(h_1)-R(h^*)=1$ and $R(h_t)-R(h^*)=0$ for $t=2,\ldots,10$. Their average excess risk is $1/10=0.1$. If the output is a uniformly selected iterate $h_J$, then its excess risk equals $1$ with probability $1/10$, not at most $0.1$ with certainty.

In particular, a claimed $0.1$ risk threshold fails with probability $0.1$, so it is not a $0.95$-confidence bound. The conversion theorem controls the average of the roundwise population risks. Convexity transfers that average to the deterministic average predictor's risk, but it does not make every iterate's risk small. A random-iterate high-probability guarantee requires an additional argument or assumption.

When the Conversion Applies

The proof isolates what a sequential guarantee does and does not provide. It does not require the algorithm to choose $h_t$ independently of earlier observations; predictability is enough. It does require the current observation to be fresh relative to the information used to choose $h_t$. If the data are dependent, or the predictor uses $Z_t$ before its round-$t$ loss is evaluated, the conditional mean-zero step for $D_t$ may fail.

The comparator condition also matters. A fixed comparator has population risk $R(h^*)$ that can be compared round by round. If the comparator is selected after inspecting the same sample, its losses need not have the stated conditional expectations. A data-dependent comparator may be possible, but it requires a guarantee that explicitly accounts for that dependence; it cannot be substituted into this proof without justification.

For bounded losses, the sharper one-sided concentration term is $\sqrt{2n\log(1/\delta_C)}$. If tails are unbounded, one needs a suitable conditional tail condition, such as the sub-Gaussian moment assumption in the second example, or another concentration result justified by the loss distribution. Without such an assumption, a high-probability regret bound on observed losses alone does not control the gap between observed and population excess losses.

Common Mistakes

Calling regret a population-risk bound. Regret compares losses on the realized sequence. Add a concentration step before interpreting it as a statement about fresh-data risk.
Ignoring adaptivity. The predictors depend on the past, so ordinary independence of $h_t$ and the whole sample is false. Use predictability and condition on the history before $Z_t$.
Omitting the comparator's role. The comparison must be to a fixed comparator, or to one for which the stated conditional expectation and concentration argument remain valid.
Forgetting confidence allocation. If the regret event fails with probability $\delta_R$ and concentration fails with probability $\delta_C$, the direct guarantee is $1-\delta_R-\delta_C$, not $1-\delta_R$.
Transferring average risk to a random iterate without justification. The average of risks controls an averaged predictor under convexity; it does not imply that a uniformly sampled iterate has low risk with high probability.

Key takeaway: A high-probability batch risk bound is a two-step conclusion: combine a sequential regret event with concentration of the centered online-versus-comparator loss differences. State the tail assumption, allocate the failure probabilities, and verify that the chosen output—especially an averaged predictor—supports the desired risk claim.

Check Your Understanding

Use the definitions and conversion argument to answer the following.

When the comparator is fixed or its independent selection information is included in $\mathcal F_{t-1}$, why does predictability of $h_t$, together with iid sampling, imply that the centered excess loss $D_t$ has conditional mean zero?
If the regret event has failure probability $0.03$ and the concentration event has failure probability $0.02$, what confidence level follows directly from the union bound?
For losses in $[0,1]$, write the one-sided concentration allowance for $n$ rounds and failure probability $\delta_C$.
Which additional conditions allow a bound on average roundwise risk excess to imply a bound on the averaged predictor's risk excess?
Why does a bound on the average risk of the iterates not, by itself, give the same high-probability bound for a uniformly selected iterate?