Random-Iterate Conversion With a Data-Dependent Output

Why Select an Iterate at Random?

An online procedure produces a sequence of predictors, each based on the observations available before its prediction. A regret guarantee controls their cumulative losses, but it does not, by itself, say that the last predictor has small population risk. A simple way to turn the sequence into one output is to choose an iterate uniformly at random. The output is still data-dependent: both the iterates and their risks can vary with the training sample.

The key link is that an iterate chosen before observing the current example is independent of that example. Under an independent and identically distributed sampling model, its expected loss on that example equals its expected population risk. Summing this identity lets us convert a regret guarantee against a population-risk minimizer into an expected excess-risk bound for the randomized output.

Setup and Definitions

Let $Z_1,\ldots,Z_n$ be independent observations from a distribution $P$ on a measurable sample space $\mathcal Z$. A predictor $h$ incurs loss $\ell(h,z)$ on example $z$. Assume the loss is jointly measurable and integrable for every predictor considered. Its population risk is

R(h)=E_{Z\sim P}[\ell(h,Z)].

The online procedure chooses $h_t$ before observing $Z_t$, using past observations and, possibly, internal randomization independent of the data. More precisely, $h_t$ is measurable with respect to the information available before $Z_t$ is observed. This condition is called predictability. It ensures that $h_t$ is independent of the fresh observation $Z_t$. A comparator $h^*$ is a fixed predictor satisfying $R(h^*)=\inf_{h\in\mathcal H}R(h)$, where $\mathcal H$ contains the iterates. In this tutorial, assume such a minimizer exists and has finite risk.

Definition: Let $J$ be uniform on $\{1,\ldots,n\}$, independent of the observations and the procedure’s internal randomization. The random-iterate output is $h_J$. Its population risk $R(h_J)$ is random because the selected predictor depends on the training data and on $J$. Its expected excess risk is $E[R(h_J)-R(h^*)]$, where the expectation is over the training data, internal randomization, and $J$.

Risk here means performance on a fresh draw from $P$, not the loss on the data used to construct the predictor. Equivalently, one can introduce an independent test observation $Z'\sim P$; conditional on the output, $R(h_J)=E[\ell(h_J,Z')\mid h_J]$, when this conditional expectation is defined.

The Risk Identity for a Predictable Iterate

Proposition: If $h_t$ is predictable and the relevant losses are integrable, then $E[\ell(h_t,Z_t)]=E[R(h_t)]$.

To see why predictability matters, condition on all information available just before $Z_t$ is observed. Given that information, $h_t$ is fixed, while $Z_t$ still has distribution $P$. The conditional expected loss is therefore $R(h_t)$. Taking expectations gives the proposition. In detail, independence gives the conditional integration identity

E[\ell(h_t,Z_t)\mid \mathcal F_{t-1}] = \int_{\mathcal Z}\ell(h_t,z)\,dP(z) = R(h_t),

where $\mathcal F_{t-1}$ denotes the information available before $Z_t$. Integrability justifies the conditional expectations. Taking expectation of both sides proves the claim. $\square$

The proposition is an expectation identity, not a claim that the realized training loss equals the population risk. It also depends on the timing of the prediction: if $h_t$ uses $Z_t$ before incurring loss on it, the conditional-independence argument need not hold.

Conversion Theorem

Theorem: Suppose the assumptions above hold, $h^*$ minimizes population risk over a class containing every $h_t$, and the procedure has expected cumulative regret at most $B_n$ against $h^*$: $$ E\!\left[\sum_{t=1}^n\bigl(\ell(h_t,Z_t)-\ell(h^*,Z_t)\bigr)\right]\le B_n. $$ If $J$ is uniform and independent of the data and internal randomization, then $$ E[R(h_J)-R(h^*)]\le \frac{B_n}{n}. $$

Proof. Conditional on the training data and the iterates, averaging over the independent uniform index gives

E[R(h_J)-R(h^*)\mid h_1,\ldots,h_n] = \frac{1}{n}\sum_{t=1}^n\bigl(R(h_t)-R(h^*)\bigr).

Taking expectations and applying the risk identity to each predictable $h_t$ yields

\begin{aligned} E[R(h_J)-R(h^*)] &=\frac{1}{n}\sum_{t=1}^n E[R(h_t)-R(h^*)]\\ &=\frac{1}{n}E\!\left[\sum_{t=1}^n\bigl(\ell(h_t,Z_t)-\ell(h^*,Z_t)\bigr)\right]\\ &\le \frac{B_n}{n}. \end{aligned}

This establishes the claimed bound. $\square$

Since $h^*$ minimizes risk over a class containing the iterates, each $R(h_t)-R(h^*)$ is nonnegative. The theorem controls the expected excess risk of the randomized output, not a high-probability deviation or the risk of every individual iterate.

Worked Examples

Worked Example: Converting a Bounded-Expert Regret Bound

Suppose an online procedure predicts among $K=4$ experts with losses in $[0,1]$. Use the standard Hedge regret bound $ \log(K)/\eta+\eta n/8 $, valid against every fixed expert, and take $n=100$. We want a bound against the expert with smallest population risk.

That expert is a fixed comparator, so the regret guarantee applies to it even though its identity is defined by its population risk. Set $A=\log 4$. The bound is minimized at $\eta=\sqrt{8A/n}$, since differentiating $A/\eta+\eta n/8$ gives $-A/\eta^2+n/8=0$. Numerically, $A\approx1.3863$, so $\eta\approx\sqrt{11.0904/100}\approx0.3330$. The two terms are approximately

\frac{1.3863}{0.3330}+\frac{0.3330\cdot100}{8} \approx 4.163+4.163=8.326.

The conversion theorem therefore gives expected excess risk at most $8.326/100=0.08326$ for the uniformly selected expert. The population comparator is essential: it identifies a fixed expert, and the online regret guarantee is compared with that expert’s losses on the same sequence of examples.

Worked Example: A Data-Dependent Sequence of Predictors

Let $Z_t\sim\mathrm{Bernoulli}(0.8)$, independently, and use binary predictions $0$ and $1$ with zero-one loss. Set $h_1=0$, and for $t\ge2$, let $h_t=Z_{t-1}$. Each predictor is based only on past observations. The population risks of the two possible predictions are $R(0)=0.8$ and $R(1)=0.2$, so $h^*=1$ and $R(h^*)=0.2$.

For the first round, $R(h_1)-R(h^*)=0.8-0.2=0.6$. On each later round, $h_t=1$ with probability $0.8$ and $h_t=0$ with probability $0.2$. Thus

E[R(h_t)-R(h^*)] =0.8(0.2-0.2)+0.2(0.8-0.2) =0.12,\qquad t\ge2.

With $n=3$, a uniform independent choice of iterate has expected excess risk $(0.6+0.12+0.12)/3=0.28$. Directly, the selected predictor is $1$ with probability $(2/3)(0.8)=8/15$, and $0$ with probability $7/15$. Its expected risk is

\frac{8}{15}(0.2)+\frac{7}{15}(0.8) =\frac{7.2}{15}=0.48, \qquad 0.48-0.2=0.28.

The iterates are data-dependent, yet the risk identity applies because each is chosen before its own observation.

Worked Example: Why the Index Must Be Independent

Suppose two fixed candidate predictors have risks $R(h_1)=0$ and $R(h_2)=1$. A uniform index independent of the data has expected output risk $(0+1)/2=0.5$. Now change the rule and always select $h_2$, so the index is no longer uniform. The output risk is $1$, not $0.5$.

The theorem’s averaging step gives the uniform average of the iterates’ risks only because $J$ is independently uniform. For a data-dependent selection rule with probabilities $q_t$, the corresponding conditional average is $\sum_t q_t R(h_t)$; it is not generally $n^{-1}\sum_t R(h_t)$. A selected output might still admit a useful bound, but it requires an argument that accounts for the selection rule.

What the Guarantee Does—and Does Not—Say

If a regret analysis gives $B_n=o(n)$, the theorem implies that the random iterate’s expected excess risk tends to zero. If $B_n$ grows on the order of $\sqrt n$, for example, the resulting bound is on the order of $1/\sqrt n$. The conversion does not improve the regret bound; it divides cumulative regret by the number of iterates.

A common mistake is to treat the output as though its training loss were its population risk, or to assume the last iterate inherits the average-regret guarantee. Neither follows from this argument. The proof controls the average expected risk across predictable iterates, and uniform randomization selects from exactly that average. A last-iterate claim needs an additional result.

Key takeaway: For predictable iterates and an independent uniform index, expected excess risk is the expected cumulative regret against a population-risk minimizer divided by $n$. The selected predictor may depend on all the training data; what must remain independent is the selection index.

Check Your Understanding

Use the setup and assumptions in this tutorial.

Why must $h_t$ be chosen before $Z_t$ is observed to use the risk identity?
If expected cumulative regret against $h^*$ is at most $12$ over $n=60$ rounds, what excess-risk bound follows for a uniform independent random iterate?
In the Bernoulli example, what is the expected excess risk of the uniform output when $n=5$?
What changes in the proof if the selection index is chosen using the observed data?
Does the theorem guarantee that every iterate has excess risk at most $B_n/n$? Explain.