Why Absolute Loss Usually Gives Only Slow Rates

Why the Shape of the Loss Matters

An aggregation guarantee depends not only on the number of candidate predictors and the amount of data, but also on the geometry of the loss. With suitable curvature or exp-concavity, one can sometimes obtain a sharp comparison whose complexity term scales like \(\log M/n\) for \(M\) candidates. Boundedness and convexity alone generally give a square-root term, of order \(\sqrt{\log M/n}\). Absolute loss is a useful example: it is convex, but its shape does not provide the exp-concavity that supports the sharper generic aggregation argument.

We consider regression predictions in a bounded interval and outcomes in the same interval. The aim is not to claim that absolute-loss methods can never have fast rates. Rather, we identify what follows from boundedness alone and why faster conclusions need additional assumptions on the model or the distribution.

Absolute Loss Is Not Exp-Concave

A loss \(\ell_y(u)\) is \(\eta\)-exp-concave on \(I\), for \(\eta>0\), if the function \(u\mapsto \exp(-\eta\ell_y(u))\) is concave on \(I\). This property is stronger than convexity of the loss and is what permits certain sharp exponential-weights bounds. Absolute loss fails this test on any nontrivial prediction interval when the outcome is in its interior.

The kink at \(u=y\) is conspicuous, but it is not the only issue: even away from the kink, the exponential transform bends the wrong way on either side. Convexity of \(u\mapsto |y-u|\) still ensures that a deterministic mixture of predictions has loss no greater than the corresponding weighted average of losses. It does not, by itself, give the exponential curvature needed for a sharp exp-concave bound.

A Risk Example With No Uniform Variance Control

Another way to see the difficulty is to compare excess risk with the variability of loss differences. Conditions that control the variance of a candidate's loss difference by its excess risk can support fast rates. Absolute loss does not supply such a condition uniformly over distributions and candidates.

The Generic Exponential-Weights Comparison

Although exp-concavity is unavailable, bounded loss still gives a useful comparison. Let there be \(M\) candidate predictions at each round, with losses \(\ell_{ij}\in[0,B]\) for candidate \(j\) on round \(i\). Start with prior weights \(\pi_j>0\), where \(\sum_{j=1}^M\pi_j=1\). Before observing the outcome at round \(i\), assign weights proportional to the prior times the exponential of negative cumulative loss so far. The resulting mixture uses those weights to combine the candidate predictions.

To prove the claim, write \(L_{ij}=\sum_{t=1}^i\ell_{tj}\), \(L_{0j}=0\), and \(Z_i=\sum_j\pi_j e^{-\eta L_{ij}}\). The normalized weights before round \(i\) are \(w_{ij}=\pi_j e^{-\eta L_{i-1,j}}/Z_{i-1}\). Hoeffding's lemma states that for any random variable \(V\) supported on an interval of length \(B\), \(\log E[e^{s(V-E[V])}]\leq s^2B^2/8\) for every real \(s\). Apply it to a variable taking the values \(\ell_{ij}\) with probabilities \(w_{ij}\), and take \(s=-\eta\). This gives

Summing over rounds yields \(\log Z_n\leq-\eta\sum_i\sum_jw_{ij}\ell_{ij}+\eta^2nB^2/8\). For any fixed \(j\), \(Z_n\geq\pi_j e^{-\eta L_{nj}}\), so \(\log Z_n\geq\log\pi_j-\eta L_{nj}\). Combining these inequalities and rearranging bounds the cumulative weighted loss by \(L_{nj}+\log(1/\pi_j)/\eta+\eta nB^2/8\). Convexity gives \(\ell_i(\hat g_i)\leq\sum_jw_{ij}\ell_{ij}\) on each round, proving the theorem. \(\square\)

For a uniform prior, \(\log(1/\pi_j)=\log M\). Optimizing the displayed upper bound over \(\eta\) gives \(\eta=\sqrt{8\log M/(nB^2)}\) when \(M>1\) and \(B>0\), and therefore the average-loss comparison

The dependence on sample size is a square-root rate, not a \(\log M/n\) rate. This is a pathwise online comparison; it does not, by itself, assert a population-risk guarantee for a predictor fitted and evaluated on the same observations.

A Finite-Class Population-Risk Comparison

For a simple statistical consequence, take \(M\) fixed predictors \(g_1,\ldots,g_M\), and let \((X_i,Y_i)\), \(i=1,\ldots,n\), be independent and identically distributed observations. Assume \(Y_i\in[a,b]\) almost surely and every \(g_j(X_i)\in[a,b]\). Write \(B=b-a\), \(R(g_j)=E[|Y-g_j(X)|]\), and \(\widehat R(g_j)=n^{-1}\sum_i|Y_i-g_j(X_i)|\). Let \(\hat j\) minimize empirical risk, breaking ties arbitrarily.

For each fixed \(j\), the losses are independent and lie in \([0,B]\). Hoeffding's inequality gives \(P(|\widehat R(g_j)-R(g_j)|>\varepsilon)\leq2\exp(-2n\varepsilon^2/B^2)\). A union bound over \(M\) candidates makes the probability that any deviation exceeds \(\varepsilon\) at most \(2M\exp(-2n\varepsilon^2/B^2)\). Choose \(\varepsilon=B\sqrt{\log(2M/\delta)/(2n)}\); this upper bound becomes \(\delta\). On the resulting event, every candidate satisfies \(|\widehat R(g_j)-R(g_j)|\leq\varepsilon\). If \(j^*\) minimizes population risk, empirical optimality gives

Substituting the chosen \(\varepsilon\) proves the claim. \(\square\)

What the Slow-Rate Comparison Does—and Does Not—Say

The exponential-weights theorem is a sequential, realized-loss guarantee; the finite-class theorem is a population-risk guarantee under independent sampling. Both exhibit the generic square-root dependence on the complexity term and sample size. Neither proves that every absolute-loss problem has only a slow rate. In particular, a distribution may impose useful structure around its conditional median, or a restricted model may satisfy a variance or margin condition. Such assumptions can make sharper analysis possible, but they are not consequences of bounded absolute loss alone.

• Common mistake: “The loss is convex, so the sharp exp-concave aggregation bound applies.” Convexity justifies the loss comparison for deterministic mixtures; it does not imply concavity of the exponential transform. The second-derivative calculation above directly disproves exp-concavity for absolute loss on a nontrivial interval.
• Common mistake: “A small excess risk automatically means low variability of the loss difference.” The Bernoulli example has excess risk \(\gamma\) and variance \(1-\gamma^2\), so no uniform linear variance control follows.
• Common mistake: “A square-root upper bound proves that faster rates are impossible.” It does not. It identifies what the generic bounded-loss argument guarantees; faster rates require additional structure and a proof that uses it.