Excess-Risk Rates From Strongly Convex Online Regret

From Online Regret to Population Risk

An online learner chooses a decision before seeing the next observation. Regret compares the learner's cumulative loss with that of a fixed comparator, but a statistical learner ultimately wants to control risk on a fresh observation. Under iid sampling, expected regret can connect these two quantities: each decision is based on past data, while the next observation has the population distribution. When the losses are strongly convex, the available regret bound can grow only logarithmically with sample size, producing a correspondingly fast excess-risk bound after averaging.

The output matters. A regret bound controls the sum of losses incurred by the sequence of decisions. It does not, by itself, assert that the last decision has small population risk. The result below converts regret into risk for the average decision, using convexity of the risk.

Definition: Let \(\mathcal W\) be a convex subset of a Euclidean space, let \(Z\) have distribution \(P\), and let \(\ell(w;z)\) be a loss. The population risk of \(w\in\mathcal W\) is \(R(w)=E[\ell(w;Z)]\), when this expectation exists. The optimal population risk is \(R^*=\inf_{u\in\mathcal W}R(u)\). A loss is \(\alpha\)-strongly convex on \(\mathcal W\), for \(\alpha>0\), if for every \(x,y\in\mathcal W\) and every subgradient \(g\in\partial\ell(x;z)\), \(\ell(y;z)\geq \ell(x;z)+g^\mathsf{T}(y-x)+\frac{\alpha}{2}\lVert y-x\rVert^2\).

Suppose \(Z_1,\ldots,Z_n\) are iid with distribution \(P\). At round \(t\), the learner chooses \(w_t\in\mathcal W\) using only past observations and any randomness available before observing \(Z_t\). Write \(\mathcal F_{t-1}\) for that past information, so \(w_t\) is \(\mathcal F_{t-1}\)-measurable. The average decision is \(\bar w_n=n^{-1}\sum_{t=1}^n w_t\), which belongs to \(\mathcal W\) by convexity.

The Expected Excess-Risk Conversion

Theorem: Assume \(\mathcal W\) is convex, the observations are iid, each \(w_t\) is measurable with respect to past information, and the losses are convex in \(w\). Assume the risks and expectations below are finite. If, for every deterministic \(u\in\mathcal W\), \(E[\sum_{t=1}^n\{\ell(w_t;Z_t)-\ell(u;Z_t)\}]\leq B_n\), then \(E[R(\bar w_n)]-R^*\leq B_n/n\). In particular, a regret bound \(B_n\leq C\log(en)/\alpha\) gives \(E[R(\bar w_n)]-R^*\leq C\log(en)/(\alpha n)\). Here \(C\) may include other problem scales, such as a squared gradient bound.

Proof. Conditional on \(\mathcal F_{t-1}\), the decision \(w_t\) is fixed and \(Z_t\) is independent of that information with distribution \(P\). Therefore \(E[\ell(w_t;Z_t)\mid\mathcal F_{t-1}]=R(w_t)\). Taking expectations and summing gives \(E[\sum_{t=1}^n\ell(w_t;Z_t)]=E[\sum_{t=1}^n R(w_t)]\). For any deterministic \(u\), iid sampling also gives \(E[\sum_{t=1}^n\ell(u;Z_t)]=nR(u)\). The assumed regret inequality consequently implies \(E[n^{-1}\sum_{t=1}^n R(w_t)]\leq R(u)+B_n/n\). Convexity of \(\ell(\cdot;z)\) implies convexity of \(R\), by taking expectations in the convexity inequality. Jensen's inequality, applied to each realized sequence of decisions, yields \(R(\bar w_n)\leq n^{-1}\sum_{t=1}^nR(w_t)\). Thus \(E[R(\bar w_n)]\leq R(u)+B_n/n\) for every deterministic \(u\). Taking the infimum over \(u\in\mathcal W\) proves the claim, whether or not the infimum is attained. \(\square\)

The iid and timing conditions are essential to the risk identity in this proof: the current observation must have distribution \(P\) independently of the decision made before it is seen. The theorem gives an expectation guarantee for a specified output, \(\bar w_n\). It does not turn an adversarial regret inequality into a statement about every data-dependent decision or about the last iterate.

Why Strong Convexity Gives a Logarithm

The conversion theorem needs a regret bound; it does not require a particular online algorithm. One standard source of the logarithmic bound is projected online gradient descent. The following derivation makes explicit how curvature and gradient size enter.

Proposition: Suppose \(\mathcal W\) is closed and convex, every round's loss is \(\alpha\)-strongly convex on \(\mathcal W\), and the subgradient \(g_t\in\partial\ell(w_t;Z_t)\) used at round \(t\) satisfies \(\lVert g_t\rVert\leq G\). For the update \(w_{t+1}=\Pi_{\mathcal W}(w_t-g_t/(\alpha t))\), every comparator \(u\in\mathcal W\) satisfies the pathwise bound \(\sum_{t=1}^n\{\ell(w_t;Z_t)-\ell(u;Z_t)\}\leq \frac{G^2}{2\alpha}H_n\leq\frac{G^2}{2\alpha}(1+\log n)\), where \(H_n=\sum_{t=1}^n1/t\).

Proof. Write \(D_t=\lVert w_t-u\rVert^2\). The projection inequality gives \(D_{t+1}\leq\lVert w_t-g_t/(\alpha t)-u\rVert^2\). Expanding the square and rearranging, \(g_t^\mathsf{T}(w_t-u)\leq\frac{\alpha t}{2}(D_t-D_{t+1})+\frac{G^2}{2\alpha t}\). Strong convexity, applied to the subgradient \(g_t\), gives \(\ell(w_t;Z_t)-\ell(u;Z_t)\leq g_t^\mathsf{T}(w_t-u)-\frac{\alpha}{2}D_t\). Combining these inequalities, \(\ell(w_t;Z_t)-\ell(u;Z_t)\leq\frac{\alpha(t-1)}{2}D_t-\frac{\alpha t}{2}D_{t+1}+\frac{G^2}{2\alpha t}\). On summing from \(t=1\) to \(n\), the distance terms telescope: the coefficient of \(D_1\) is zero, each intermediate \(D_t\) has net coefficient zero, and the remaining term is \(-\alpha nD_{n+1}/2\leq0\). The sum is therefore at most \(G^2H_n/(2\alpha)\). Finally, \(H_n\leq1+\log n\) for \(n\geq1\), by comparison of the terms \(1/t\), \(t\geq2\), with the integral of \(1/x\) from \(1\) to \(n\). \(\square\)

Combining this pathwise inequality with the conversion theorem gives, under its iid and integrability conditions, \(E[R(\bar w_n)]-R^*\leq \frac{G^2}{2\alpha n}(1+\log n)\). The inverse dependence on \(\alpha\) comes from the regret bound; the additional factor \(1/n\) comes from converting cumulative regret to average risk. If a different online method supplies a logarithmic regret bound with another constant, the conversion theorem applies with that bound instead.

Worked Rates and Models

Worked Example: Substituting a Gradient Bound

Suppose an online method has the regret guarantee in the proposition with \(G=2\), curvature \(\alpha=0.5\), and \(n=100\). The conversion gives \(E[R(\bar w_{100})]-R^*\leq\frac{2^2}{2(0.5)(100)}(1+\log 100)\). Since \(2(0.5)(100)=100\) and \(\log 100\approx4.6052\), the bound is \(\frac{4}{100}(5.6052)\approx0.2242\).

This is an upper bound on expected excess risk, not a prediction that the realized excess risk equals \(0.2242\). The calculation also shows the scales transparently: at fixed \(n\) and \(G\), reducing curvature increases this bound in inverse proportion.

Worked Example: Averaged Prediction for Bernoulli Data

Let \(Z_t\) be iid Bernoulli with success probability \(0.3\), let \(\mathcal W=[0,1]\), and use the loss \(\ell(w;z)=\frac12(w-z)^2\). Its derivative with respect to \(w\) is \(w-z\), whose absolute value is at most \(1\) on this domain for \(z\in\{0,1\}\). Its second derivative is \(1\), so the loss is \(1\)-strongly convex and the proposition applies with \(G=1\), \(\alpha=1\).

The population risk can be calculated directly: \(R(w)=\frac12E[(w-Z)^2]=\frac12\{0.3(w-1)^2+0.7w^2\}\). Expanding gives \(R(w)=\frac12(w^2-0.6w+0.3)=\frac12(w-0.3)^2+0.105\). Hence \(R^*=0.105\), attained at \(w=0.3\).

For \(n=50\), the excess-risk guarantee for the average of the online decisions is \(E[R(\bar w_{50})]-0.105\leq\frac{1}{2(50)}(1+\log 50)\). Using \(\log 50\approx3.9120\), this is at most \(4.9120/100=0.04912\). The online sequence's average prediction is thus controlled in expected population risk, even though the individual predictions were made before their respective observations arrived.

Worked Example: An Infimum Without an Optimizer

Consider \(\mathcal W=(0,1)\) and the deterministic loss \(\ell(w;z)=w+\frac12w^2\), which does not depend on \(z\). Its second derivative is \(1\), so it is \(1\)-strongly convex. Its risk is \(R(w)=w+\frac12w^2\), with \(R^*=0\) as \(w\) decreases toward \(0\); the infimum is not attained because \(0\notin\mathcal W\).

Suppose a sequence has regret at most \(B_n\) against every fixed \(u\in(0,1)\). The conversion argument gives \(R(\bar w_n)\leq u+\frac12u^2+B_n/n\) for every such \(u\). Taking \(u=0.01\) gives \(R(\bar w_n)\leq0.01005+B_n/n\); taking the infimum over \(u\) gives \(R(\bar w_n)-R^*\leq B_n/n\). No optimizer needs to exist. The essential point is that the regret guarantee holds for each fixed comparator, however close to optimal.

Interpretation and a Common Pitfall

With a regret bound proportional to \(G^2\log(en)/\alpha\), the averaged predictor's expected excess risk is proportional to \(G^2\log(en)/(\alpha n)\). This is an expectation bound under the stated sampling assumptions. The strong convexity parameter describes curvature of the per-observation losses in the decision variable; the formula should not be read as a claim about curvature in every possible parameterization or norm.

Pitfall: concluding a last-iterate guarantee from cumulative regret. The incorrect reasoning is that a small average of the \(n\) losses must mean the final decision \(w_n\) has small risk. A cumulative bound controls the sequence as a whole; it does not rule out one poorly performing term. The conversion proved here uses convexity to control the risk of \(\bar w_n\), not \(w_n\).
Pitfall: dropping the iid timing condition. The identity \(E[\ell(w_t;Z_t)]=E[R(w_t)]\) follows because \(w_t\) is chosen before an independent \(Z_t\). If the decision can depend on \(Z_t\), this conditional-expectation step need not hold.
Pitfall: overlooking constants and curvature. A statement of order \(\log n/n\) suppresses the factor in the regret bound. For the projected-gradient guarantee derived above, that factor includes \(G^2/\alpha\); it is not a universal numerical constant.

Key takeaway: Under iid sampling, predictability, and convex losses, an expected regret bound \(B_n\) yields expected excess risk at most \(B_n/n\) for the average online decision. Strongly convex logarithmic regret therefore gives a rate proportional to \(\log(en)/(\alpha n)\), with any additional problem scales retained in the regret constant.

Check Your Understanding

Use the assumptions and arguments above to answer the following.

Why does the expected loss at round \(t\) equal \(E[R(w_t)]\) when the decisions are based only on past observations?
If the regret bound is \(B_n=K(1+\log n)/\alpha\), what is the resulting excess-risk bound for the average decision?
In the projected-gradient proposition, where do the factors \(G^2\) and \(1/\alpha\) enter the regret calculation?
Why does convexity allow a risk bound for \(\bar w_n\) without giving the same conclusion for \(w_n\)?
Does the conversion require the population-risk infimum to be attained? Explain using the comparator argument.