Why Expected Regret Can Control Population Risk
An online learner produces a sequence of predictions as data arrive. Its regret compares the cumulative losses of those predictions with the cumulative losses of a comparator. Population risk, by contrast, measures expected loss on a fresh observation. Under iid sampling, these quantities connect when each prediction is chosen before the observation on which its loss is evaluated. A uniformly sampled iterate then has expected population risk no larger than the comparator’s risk plus expected regret per round.
The conclusion concerns a randomly selected iterate, not automatically the last iterate or an average of the iterates. The random index is sampled independently of the data and the learner’s randomization. These details are part of the result, not merely implementation choices.
Protocol, Risk, and Regret
Let \(Z_1,\ldots,Z_n\) be iid observations with common distribution \(P\). A decision \(h\) belongs to a decision space \(\mathcal H\), and \(\ell(h,z)\) is its loss on observation \(z\). Assume the loss is jointly measurable and that the expectations below exist and are finite. In particular, bounded losses suffice.
The decision \(h_t\) may be random because it depends on the earlier data or on the learner’s independent random seed. The key requirement is that \(Z_t\) is still a fresh draw after \(h_t\) has been chosen. The comparator \(h^\circ\) is fixed independently of the sample. Regret itself can be negative on a particular data sequence, or even in expectation.
Let \(I\) be uniform on \(\{1,\ldots,n\}\), independently of the observations and of the learner’s randomization. The output is \(h_I\). The following identity explains why its population risk is linked to the losses used to define regret.
Proof. Write \(U\) for the learner’s external random seed, independent of the data. The decision \(h_t\) is a measurable function of \(U,Z_1,\ldots,Z_{t-1}\). Since \(Z_t\) is independent of these variables, for each fixed value of them the conditional expectation of \(\ell(h_t,Z_t)\) is the integral of \(\ell(h_t,z)\) with respect to \(P(dz)\), which is \(R(h_t)\). Integrability permits taking expectations over \(U,Z_1,\ldots,Z_{t-1}\), giving the identity. For nonnegative losses, Tonelli’s theorem gives the same interchange without a separate absolute-integrability assumption. \(\square\)
The Uniform-Random-Iterate Guarantee
Proof. Independence and uniformity of \(I\) give $$ E[R(h_I)]=\frac{1}{n}\sum_{t=1}^n E[R(h_t)]. $$ Apply the lemma at each round: $$ E[R(h_I)]=\frac{1}{n}\sum_{t=1}^n E[\ell(h_t,Z_t)]. $$ By the definition of regret, the sum of the learner’s expected losses equals the sum of the comparator’s expected losses plus expected regret. Because \(h^\circ\) is fixed and each \(Z_t\) has distribution \(P\), \(E[\ell(h^\circ,Z_t)]=R(h^\circ)\) for every \(t\). Therefore, $$ E[R(h_I)] =\frac{1}{n}\left(nR(h^\circ)+E[\operatorname{Reg}_n(h^\circ)]\right) =R(h^\circ)+\frac{1}{n}E[\operatorname{Reg}_n(h^\circ)]. $$ The inequality follows by substituting the assumed upper bound \(B_n\). \(\square\)
In particular, suppose the initial predictor \(h_1\) is fixed before any data are observed, and regret is measured against \(h^\circ=h_1\). Then the result reads $$ E[R(h_I)]\leq R(h_1)+\frac{E[\operatorname{Reg}_n(h_1)]}{n}. $$ Thus an expected regret bound that grows more slowly than \(n\) makes the sampled iterate’s expected risk approach the initial predictor’s risk. More generally, the comparator may be any fixed decision whose risk is preferable to the initial risk.
Worked Example: Bernoulli Outcomes and a Data-Dependent Iterate
Let \(Y_t\) be iid Bernoulli with success probability \(q=0.25\), and predict with \(p\in[0,1]\) using squared loss \(\ell(p,y)=(p-y)^2\). Set \(p_1=0.8\), and choose \(p_2=Y_1\). This is a valid online rule: the second prediction uses the first observation, not the second. Take \(n=2\) and compare with the fixed initial predictor \(p_1\).
For any fixed \(p\), the population risk is $$ R(p)=0.75p^2+0.25(1-p)^2. $$ Consequently, \(R(p_1)=0.75(0.64)+0.25(0.04)=0.49\). The second predictor equals \(0\) with probability \(0.75\) and \(1\) with probability \(0.25\). Since \(R(0)=0.25\) and \(R(1)=0.75\), $$ E[R(p_2)]=0.75(0.25)+0.25(0.75)=0.375. $$ The uniformly sampled iterate therefore has expected risk \((0.49+0.375)/2=0.4325\).
The first-round regret against \(p_1\) is zero. At the second round, \(p_2\) and \(Y_2\) are independent Bernoulli variables with the same success probability, so \(E[(p_2-Y_2)^2]=P(p_2\ne Y_2)=2(0.25)(0.75)=0.375\). The comparator’s expected second-round loss is \(0.49\). Thus \(E[\operatorname{Reg}_2(p_1)]=0.375-0.49=-0.115\), and the theorem gives $$ R(p_1)+\frac{E[\operatorname{Reg}_2(p_1)]}{2} =0.49-\frac{0.115}{2} =0.4325. $$ Here the identity holds with equality, and negative expected regret reflects that the second prediction improves on the comparator in expected loss.
Worked Example: Gaussian Observations With Squared Loss
Suppose \(Z_t\sim N(1,1)\) iid and a prediction \(a\in\mathbb R\) has loss \((a-Z_t)^2\). The risk is \(R(a)=1+(a-1)^2\). Let \(h_1=0\), and for \(t\geq2\) let \(h_t\) be the average of the first \(t-1\) observations. For \(n=3\), the three risks in expectation are as follows.
The first decision is \(h_1=0\), so \(E[R(h_1)]=2\). The second is \(h_2=Z_1\); since \(E[(Z_1-1)^2]=1\), \(E[R(h_2)]=1+1=2\). The third is \(h_3=(Z_1+Z_2)/2\), which has mean \(1\) and variance \(1/2\), so \(E[R(h_3)]=1+1/2=1.5\). The expected risk of a uniform draw is therefore $$ E[R(h_I)]=\frac{2+2+1.5}{3}=\frac{11}{6}. $$
Against the initial predictor \(0\), the comparator’s expected cumulative loss is \(3(2)=6\). By independence of the current observation from the predictor, the learner’s expected cumulative loss is \(2+2+1.5=5.5\); hence expected regret is \(5.5-6=-0.5\). The converted bound is \(2+(-0.5)/3=11/6\), again exactly the expected risk of the sampled iterate.
Worked Example: Turning a Bounded-Expert Regret Bound Into Risk
Consider four fixed experts whose losses lie in \([0,1]\), and iid observations. Suppose a Hedge learner has expected regret at most \(\sqrt{n\log(4)/2}\) against each fixed expert. If the chosen comparator expert has population risk \(0.18\) and \(n=50\), the uniform-iterate theorem gives $$ E[R(h_I)]\leq 0.18+\frac{\sqrt{50\log(4)/2}}{50}. $$ Since \(\log(4)\approx1.3863\), the regret bound is \(\sqrt{34.6575}\approx5.887\), and the per-round term is approximately \(0.1177\). Thus \(E[R(h_I)]\leq0.2977\). This is an expected-risk guarantee for the independently sampled round; it does not assert that every iterate, or the final iterate, has risk at most \(0.2977\).
What the Guarantee Does—and Does Not—Say
The conversion matters because many online analyses produce a cumulative regret bound more easily than a direct risk analysis of an output trained on the sample. If the expected regret is at most \(B_n\), the theorem immediately turns that sequential guarantee into an expected population-risk guarantee with additive term \(B_n/n\). For example, a regret bound of order \(\sqrt n\) yields an excess term of order \(1/\sqrt n\), while a logarithmic regret bound yields an order \((\log n)/n\) term. The conclusion is only as useful as the comparator risk and the regret guarantee that can actually be established.
A common mistake is to reason that iid observations alone make every training loss an unbiased estimate of population risk. That is false if the decision is allowed to use the observation on which it is evaluated. For instance, with a binary outcome and zero-one loss, choosing \(h_t=Y_t\) gives zero loss on observation \(Y_t\), while the same decision need not predict a fresh independent outcome correctly. The choice is not predictable from past data, so the lemma does not apply. The correction is to check the information available when \(h_t\) is chosen: it must be independent of the current fresh observation.
A second pitfall is changing the comparator after seeing the sample. The proof uses \(E[\ell(h^\circ,Z_t)]=R(h^\circ)\) for a fixed comparator. A comparator selected using the same data can be statistically dependent on the observations, so this equality need not hold. Likewise, the theorem samples the iterate uniformly and independently; choosing an index based on observed losses does not produce the same identity. These restrictions explain why the guarantee is specifically for a uniformly sampled online iterate against a fixed comparator.
Check Your Understanding
Answer each question using the assumptions and identities developed above.
- Which independence condition allows \(E[\ell(h_t,Z_t)]\) to equal \(E[R(h_t)]\)?
- Why must the comparator be fixed independently of the observations in the theorem’s proof?
- If expected regret against a fixed comparator is at most \(12\) over \(n=100\) rounds, what additive term appears in the risk bound?
- In the Bernoulli example, why is \(p_2=Y_1\) allowed while \(p_2=Y_2\) would not satisfy the protocol?
- Does the uniform-iterate guarantee by itself bound the population risk of the last iterate? Explain.