Second-Order Regret Bounds From Loss Variance

Why Loss Spread Can Matter More Than the Loss Range

A worst-case regret bound treats every round as if the experts’ losses were as different as the allowed loss range permits. But experts can all have losses close together, or even identical, on many rounds. On those rounds, their relative performance is hard to distinguish, and the instantaneous spread of losses can be much smaller than its worst-case value. A second-order bound records that spread rather than charging the same amount on every round.

We consider a fixed collection of experts with losses in \([0,1]\). The learner maintains exponential weights and predicts with their weighted average loss. The key quantity will be the variance of the experts’ losses under the weights in force before observing that round’s loss vector. The resulting guarantee is pathwise: it holds for every realized sequence of loss vectors, without a stochastic assumption.

This is a variance across experts at one round, not a variance across repeated random samples. It is computed from the current weights and the current loss vector. It can be zero even when the common loss is large: if every expert has the same loss, none is separated from another on that round.

The Exponential-Weights Setup

Let \(\pi=(\pi_1,\ldots,\pi_K)\) be a prior distribution with \(\pi_i>0\) for every expert. Fix a learning rate \(0<\eta\leq1\), initialize weights with \(\pi\), and update by multiplying each expert’s weight by the exponential of its negative loss. In normalized form, the pre-loss weights at round \(t\) are

The learner incurs \(\langle p_t,\ell_t\rangle\). The prior allows experts to have different complexity costs: an expert assigned small prior mass pays a larger penalty \(\log(1/\pi_i)\). The argument below works for any loss sequence in \([0,1]^K\), including sequences chosen adaptively, provided the round’s weights are formed before its losses are used.

A Bounded-Moment Inequality

The proof uses a Bernstein-type bound on the exponential moment of a centered bounded random variable. Here, the randomness is simply a convenient way to represent sampling an expert according to \(p_t\).

Proof. For every integer \(k\geq2\), \(|Y|^k\leq Y^2\), since \(|Y|\leq1\). Expanding the exponential and using \(E[Y]=0\), with the series justified by boundedness of \(Y\), gives

For \(k\geq2\), \(k!\geq2\cdot3^{k-2}\): equality holds at \(k=2,3\), and each subsequent factorial factor is at least \(3\). Therefore, for \(0\leq s<3\),

It follows that \(E[\exp(sY)]\leq1+s^2E[Y^2]/[2(1-s/3)]\). Applying \(\log(1+x)\leq x\) for \(x\geq0\) proves the claim. Replacing \(Y\) by \(-Y\) preserves its mean and second moment, so the same argument proves the final statement. \(\square\)

Second-Order Regret Bound

Proof. Define the unnormalized total weight after \(t\) rounds by $$ W_{t+1}=\sum_{j=1}^K\pi_j\exp\!\left(-\eta\sum_{s=1}^{t}\ell_{s,j}\right), \qquad W_1=1. $$ The ratio \(W_{t+1}/W_t\) is \(\sum_jp_{t,j}\exp(-\eta\ell_{t,j})\). Let a random variable \(X_t\) take the value \(\ell_{t,j}\) with probability \(p_{t,j}\); its mean is \(\langle p_t,\ell_t\rangle\) and its variance is \(\operatorname{Var}_{p_t}(\ell_t)\). Since \(X_t\in[0,1]\), the centered variable \(\langle p_t,\ell_t\rangle-X_t\) has absolute value at most one. Applying the lemma with \(s=\eta\) yields

Summing this inequality over \(t\) telescopes the log-weight ratios, so

On the other hand, the term for expert \(i\) is one of the nonnegative terms in \(W_{T+1}\). Thus \(W_{T+1}\geq\pi_i\exp(-\eta\sum_t\ell_{t,i})\), and taking logs gives \(\log W_{T+1}\geq\log\pi_i-\eta\sum_t\ell_{t,i}\). Combining the upper and lower bounds on \(\log W_{T+1}\), then dividing by \(\eta>0\), proves the theorem. \(\square\)

Variance as Squared Loss Differences

The variance has an equivalent expression that makes its second-order character especially clear. If \(\bar\ell=\sum_i p_i\ell_i\), expand the squared differences and use \(\sum_i p_i=1\):

Consequently, $$ \operatorname{Var}_{p_t}(\ell_t) =\sum_{i<j}p_{t,i}p_{t,j}(\ell_{t,i}-\ell_{t,j})^2. $$ This identity says that the variance is a weighted sum of squared pairwise loss gaps. Differences matter most for pairs that both retain substantial weight. A large gap involving an expert with almost no current weight can contribute little.

When the Second-Order Bound Helps

For losses in \([0,1]\), the variance of any distribution over expert losses is at most \(1/4\). One way to see this is that \(X^2\leq X\) for \(X\in[0,1]\), so \(\operatorname{Var}(X)=E[X^2]-E[X]^2\leq m-m^2\leq1/4\), where \(m=E[X]\). Substituting \(1/4\) on every round recovers the worst-case form of the theorem: $$ \frac{\log(1/\pi_i)}{\eta} +\frac{\eta T}{8(1-\eta/3)}. $$ The data-dependent guarantee is sharper whenever the cumulative variance is below this worst-case allowance. This comparison concerns the worst-case version of the same Bernstein argument; it does not imply that a variance-sensitive bound always beats every alternative worst-case bound with different constants. For example, the familiar Hoeffding-based Hedge bound can have a smaller variance-independent term for some choices of \(\eta\).

With \(\eta=1\), the variance coefficient is \(3/4\), so the second-order complexity-and-variance expression is smaller than the Hoeffding expression \(\log(1/\pi_i)+T/8\) precisely when \((3/4)V_T<T/8\), or \(V_T<T/6\), where \(V_T=\sum_t\operatorname{Var}_{p_t}(\ell_t)\). This is a direct condition for improvement in that comparison, not a guarantee that the total bound is small in every setting: the complexity term remains.

Common Pitfall

A common mistake is to say, “The experts’ losses are close on average, so the regret must be zero.” The theorem does not say that. It bounds regret by a complexity cost plus a variance cost; even if the variance is zero on every round, a positive complexity term remains. Moreover, a small cumulative variance does not by itself establish that the learner has matched the best expert exactly. The correct interpretation is that rounds with little weighted disagreement contribute less to this particular upper bound, while the prior-weighted cost of selecting a comparator is still present.

The variance is also computed under \(p_t\), not under a fixed uniform distribution and not under the posterior weights after round \(t\)’s update. Using the wrong weights changes the quantity and breaks the potential argument that proves the result.