Averaging Predictors Under Convex Losses

Why Average Predictors?

An online learning algorithm produces a sequence of predictors, one at each round. A single iterate may have an unusually high risk, even when the sequence performs well on average. If predictions lie in a convex set and the loss is convex in the prediction, averaging the predictors gives a direct way to transfer the sequence’s average risk to one batch predictor.

The key is to average predictions, not merely to average recorded losses. Convexity applies to the prediction made at each input and outcome. Under an i.i.d. online protocol, a separate argument then relates the average population risk of the iterates to their observed online losses and to regret.

Predictors, Risk, and Convexity

Let \(Z=(X,Y)\) have distribution \(P\), where \(X\) is an input and \(Y\) is an outcome. Predictions take values in a convex set \(\mathcal C\) in a real vector space. A predictor \(f\) maps inputs to \(\mathcal C\), and the loss \(L(a,y)\) is a real-valued function of prediction \(a\in\mathcal C\) and outcome \(y\).

Definition: The population risk of a predictor \(f\) is \(R(f)=E_{Z\sim P}[L(f(X),Y)]\), when this expectation exists. The loss is convex in its prediction argument if, for every outcome \(y\), every \(a,b\in\mathcal C\), and every \(\lambda\in[0,1]\), \(L(\lambda a+(1-\lambda)b,y)\leq \lambda L(a,y)+(1-\lambda)L(b,y)\).

Given \(T\) predictors \(f_1,\ldots,f_T\), define their uniform prediction average by \(\bar f(x)=T^{-1}\sum_{t=1}^T f_t(x)\). Convexity of \(\mathcal C\) ensures \(\bar f(x)\in\mathcal C\). This definition averages outputs at each input; it does not require the predictors to have parameters that can meaningfully be averaged.

Assumptions for the averaging inequality: The predictors are measurable, their predictions lie in \(\mathcal C\), the loss is measurable and convex in its prediction argument, and the risks in the inequality are finite. These conditions ensure that the averages and expectations below are well-defined.

Worked Examples of Convex Averaging

Worked Example: Squared Loss Can Reward the Average

Suppose \(X\) is constant, \(Y=2\) with probability one, and \(L(a,y)=(a-y)^2\). Consider two constant predictors, \(f_1(x)=0\) and \(f_2(x)=4\). Their risks are

R(f_1)=(0-2)^2=4,\qquad R(f_2)=(4-2)^2=4.

The averaged predictor is \(\bar f(x)=(0+4)/2=2\), so

R(\bar f)=(2-2)^2=0 \leq \frac{R(f_1)+R(f_2)}{2} =\frac{4+4}{2}=4.

This example shows that averaging can improve on the average risk, but the general guarantee is an upper bound by average risk, not a claim that averaging always improves on every individual predictor.

Worked Example: Averaging Class Probabilities Under Log Loss

For a binary outcome, use probability vectors \((p,1-p)\) and log loss \(L(p,y)=-\log p_y\), where \(p_y\) is the probability assigned to the observed class. Suppose \(Y=1\) with probability one. Two predictors report probabilities \(0.8\) and \(0.4\) for class 1. Their risks are \(-\log(0.8)\approx0.2231\) and \(-\log(0.4)\approx0.9163\). The average probability assigned to class 1 is \((0.8+0.4)/2=0.6\), and the averaged risk is

-\log(0.6)\approx0.5108 \leq \frac{0.2231+0.9163}{2}=0.5697.

The inequality follows from convexity of \(-\log p\) for \(p>0\). The calculation uses probabilities strictly between zero and one, so all three log losses are finite.

The Risk Inequality for an Averaged Predictor

The first result is a direct consequence of Jensen’s inequality, applied separately at each input and outcome. It holds for a fixed sequence of predictors and also for each realized sequence when the predictors are random.

Theorem: Let \(f_1,\ldots,f_T\) satisfy the assumptions above, and let \(\bar f=T^{-1}\sum_{t=1}^T f_t\). If \(L(\,\cdot\,,y)\) is convex for every \(y\), then \(R(\bar f)\leq T^{-1}\sum_{t=1}^T R(f_t)\).

Apply finite Jensen at each observation.
For every input \(x\) and outcome \(y\), convexity gives \(L(\bar f(x),y)\leq T^{-1}\sum_{t=1}^T L(f_t(x),y)\).

Take expectation under the data distribution.
Integrate both sides with respect to \(Z=(X,Y)\sim P\). Finiteness of the risks permits the finite sum to pass through the expectation.

Identify each expected loss as risk.
The left side is \(R(\bar f)\), and the right side is \(T^{-1}\sum_{t=1}^T R(f_t)\). This proves the inequality. \(\square\)

For random predictors, the same argument is applied conditional on their realized values: the pointwise inequality holds for every realized sequence. If the sequence was built from training data, \(R(\bar f)\) is then the population risk of the resulting predictor, conditional on that training sequence.

From Regret to a Batch Risk Bound

The averaging theorem controls the batch predictor by the average population risk of the iterates. To connect that quantity to regret, assume an i.i.d. stream \(Z_1,\ldots,Z_T\sim P\). At round \(t\), the algorithm chooses \(f_t\) using only the previous observations and any randomization independent of the current observation. Its observed loss is \(\ell_t(f_t)=L(f_t(X_t),Y_t)\).

Definition: For a fixed comparator predictor \(u\), the cumulative regret is \(\operatorname{Reg}_T(u)=\sum_{t=1}^T [L(f_t(X_t),Y_t)-L(u(X_t),Y_t)]\). The comparator is fixed independently of the current observations; the regret may itself be random.

Theorem: Suppose the loss is convex in its prediction argument, the predictors are chosen before their respective observations, the observations are i.i.d. from \(P\), and the losses have finite expectations. Let \(\bar f=T^{-1}\sum_{t=1}^T f_t\), and let \(u\) be a fixed predictor of finite risk. Then \(E[R(\bar f)]\leq R(u)+E[\operatorname{Reg}_T(u)]/T\). The outer expectation averages over the training stream and learner randomization; \(R(\bar f)\) is the population risk evaluated on a fresh observation.

To prove the theorem, condition at round \(t\) on the information available when \(f_t\) is chosen. Since \(Z_t\) is independent of that information and distributed as \(P\), the conditional expectation of the online loss is \(R(f_t)\). The fixed comparator has expected loss \(R(u)\) on each round. Taking expectations and summing therefore gives

E[\operatorname{Reg}_T(u)] =\sum_{t=1}^T E[R(f_t)]-T R(u).

Rearranging this equality yields \(T^{-1}\sum_{t=1}^T E[R(f_t)]=R(u)+E[\operatorname{Reg}_T(u)]/T\). Apply the averaging theorem to each realized sequence and then take expectation over the sequence:

E[R(\bar f)] \leq \frac{1}{T}\sum_{t=1}^T E[R(f_t)] = R(u)+\frac{E[\operatorname{Reg}_T(u)]}{T}.

This establishes the result. In particular, if an online guarantee gives \(E[\operatorname{Reg}_T(u)]\leq B_T\), then the averaged batch predictor satisfies \(E[R(\bar f)]\leq R(u)+B_T/T\). A pathwise regret bound \(\operatorname{Reg}_T(u)\leq B_T\) also implies this expected bound.

Worked Example: Turning a Regret Value Into a Risk Bound

Let \(X\) be constant, \(Y=1\) with probability one, and use squared loss. Over \(T=4\) rounds, suppose the online predictions are \(0,\ 0.5,\ 1.5,\ 1.0\). Their observed losses, which equal their population risks in this deterministic example, are

(0-1)^2=1,\quad (0.5-1)^2=0.25,\quad (1.5-1)^2=0.25,\quad (1-1)^2=0.

The total online loss is \(1.5\). Choose the fixed comparator \(u(x)=0.5\), whose loss on each round is \((0.5-1)^2=0.25\), for total comparator loss \(4(0.25)=1\). Thus \(\operatorname{Reg}_4(u)=1.5-1=0.5\). The regret-based average-risk bound is

\frac{1}{4}\sum_{t=1}^4 R(f_t) =0.375 =R(u)+\frac{\operatorname{Reg}_4(u)}{4} =0.25+0.125.

The averaged prediction is \((0+0.5+1.5+1)/4=0.75\), with risk \((0.75-1)^2=0.0625\), which is indeed no greater than \(0.375\). The regret calculation bounds average iterate risk; convexity then transfers that bound to the batch predictor.

What the Guarantee Does—and Does Not—Say

The result matters because an online regret guarantee can yield a population-risk guarantee for one predictor that is constructed after the data stream. Convexity is the link: it controls the loss of the averaged prediction without requiring that any particular iterate be the best one. The bound is against a fixed comparator, and its statistical interpretation uses the i.i.d. and predictability conditions stated above.

A frequent mistake is to average model parameters automatically. The proof requires that the prediction itself satisfy \(\bar f(x)=T^{-1}\sum_t f_t(x)\), with all predictions in a convex set where the loss is convex. For a nonlinear model, averaging parameter vectors need not produce the average predictions, and convexity in the prediction does not imply convexity in the parameters. Another mistake is to replace population risks by observed losses without checking the sampling conditions: the equality between expected online loss and expected iterate risk relies on each iterate being selected before its current observation.

Key takeaway: Under convex prediction loss, the population risk of the uniform average predictor is at most the average population risk of its iterates. Under an i.i.d. predictable online protocol, expected regret against a fixed comparator turns this into \(E[R(\bar f)]\leq R(u)+E[\operatorname{Reg}_T(u)]/T\).

Check Your Understanding

Use the definitions and conditions above to answer the following.

Which part of the averaging argument requires convexity, and in which argument is the loss required to be convex?
Why does the online-to-batch theorem require \(f_t\) to be selected before observing \(Z_t\)?
If an online regret bound against a fixed comparator is \(B_T\), what population-risk bound follows for the averaged predictor?
Explain why convexity of the loss in the prediction does not, by itself, justify averaging parameters in a nonlinear model.
In the squared-loss example with predictions \(0\) and \(4\) and outcome \(2\), calculate the average iterate risk and the averaged predictor’s risk.