Sharp Oracle Bounds Under Exp-Concavity

Why Curvature Changes the Oracle Penalty

Exponential aggregation assigns more weight to candidates that have performed well, while retaining a controlled amount of weight on every candidate in the dictionary. With bounded losses alone, its general finite-class guarantee has a square-root dependence on sample size. Exp-concavity supplies a stronger property: the loss of a mixture is controlled by an exponential average of the candidates' losses. That property lets the cumulative guarantee add a fixed complexity cost rather than repeatedly paying a square-root fluctuation cost.

The resulting oracle inequality compares the aggregate directly with each candidate, including candidates given little prior mass. Its penalty makes that cost explicit: low prior mass is more expensive, stronger exp-concavity permits a larger learning rate, and a larger sample spreads the cost across more predictions.

Exp-Concavity and Its Aggregation Consequence

Concavity is the key: for candidates \(f_1,\ldots,f_M\) and nonnegative weights \(w_j\) summing to one, the mixture \(f_w=\sum_jw_jf_j\) lies in \(\mathcal F\), and \(\exp\{-\alpha\ell(f_w,z)\}\geq\sum_jw_j\exp\{-\alpha\ell(f_j,z)\}\). The inequality points in the direction needed to control the aggregate's loss.

Proof. Fix \(z\) and write \(g(f)=\exp\{-\alpha\ell(f,z)\}\), a positive concave function. Set \(r=\eta/\alpha\), so \(0<r\leq1\). The function \(u\mapsto u^r\) is increasing and concave on the positive reals (linear when \(r=1\)). Thus \(g^r\) is concave: for \(0\leq\lambda\leq1\), \[ g(\lambda f+(1-\lambda)h)^r \geq [\lambda g(f)+(1-\lambda)g(h)]^r \geq \lambda g(f)^r+(1-\lambda)g(h)^r. \] Since \(g(f)^r=\exp\{-\eta\ell(f,z)\}\), this proves \(\eta\)-exp-concavity. Applying concavity repeatedly to a finite convex combination gives the stated mixture inequality. \(\square\)

The lemma permits any learning rate up to \(\alpha\). The sharpest bound below uses \(\eta=\alpha\); a smaller rate remains valid but increases the penalty.

A Pathwise Oracle Inequality

Consider \(M\) candidate predictors \(f_1,\ldots,f_M\in\mathcal F\), with prior probabilities \(\pi_j>0\) satisfying \(\sum_{j=1}^M\pi_j=1\). Given observations \(Z_1,\ldots,Z_n\), define the cumulative candidate loss through time \(t\) by \(L_{t,j}=\sum_{s=1}^t\ell(f_j,Z_s)\), with \(L_{0,j}=0\). At time \(t\), use the weights based only on earlier observations: \(w_{t,j}=\pi_j\exp(-\eta L_{t-1,j})/\sum_k\pi_k\exp(-\eta L_{t-1,k})\). The prediction is \(f_t=\sum_jw_{t,j}f_j\). This is sequential exponential aggregation: the current outcome is not used to form its own prediction.

Proof. Define the positive potential \(W_t=\sum_{j=1}^M\pi_j\exp(-\eta L_{t,j})\), so \(W_0=1\). The weights at time \(t\) are \(w_{t,j}=\pi_j\exp(-\eta L_{t-1,j})/W_{t-1}\). By the lemma, applied at the observed outcome \(Z_t\), \[ \exp\{-\eta\ell(f_t,Z_t)\} \geq \sum_jw_{t,j}\exp\{-\eta\ell(f_j,Z_t)\} =\frac{W_t}{W_{t-1}}. \] Taking logarithms and rearranging gives \(\ell(f_t,Z_t)\leq\eta^{-1}\log(W_{t-1}/W_t)\). Summing over \(t\) telescopes: \[ \sum_{t=1}^n\ell(f_t,Z_t) \leq \frac{1}{\eta}\log\frac{W_0}{W_n} =-\frac{1}{\eta}\log W_n. \] For each fixed \(j\), \(W_n\geq\pi_j\exp(-\eta L_{n,j})\). Therefore \[ -\frac{1}{\eta}\log W_n \leq L_{n,j}+\frac{\log(1/\pi_j)}{\eta}, \] which proves the result. \(\square\)

This is pathwise: it holds for every realized sequence, without an independence assumption. The comparison is candidate-by-candidate, so it also yields the smallest of the bounds on its right-hand side.

From Cumulative Loss to Expected Risk

For a population interpretation, suppose \(Z_1,\ldots,Z_n\) are independent and identically distributed, each candidate has finite risk \(R_j=E[\ell(f_j,Z)]\), and each sequential prediction has an integrable loss. The prediction \(f_t\) depends only on \(Z_1,\ldots,Z_{t-1}\), so it is independent of \(Z_t\). Define \(R(f)=E[\ell(f,Z)]\), where \(Z\) has the common observation distribution.

Proof. Take expectations in the pathwise inequality. Independence of \(f_t\) and \(Z_t\) gives \(E[\ell(f_t,Z_t)]=E[R(f_t)]\); identical distribution gives \(E[\ell(f_j,Z_t)]=R_j\). Thus \[ \sum_{t=1}^nE[R(f_t)] \leq nR_j+\frac{\log(1/\pi_j)}{\eta}. \] Divide by \(n\), then apply the result for each \(j\) and take the minimum. \(\square\)

This is an average-risk guarantee for the sequence of predictions. Equivalently, if a time \(T\) is selected uniformly from \(1,\ldots,n\), independently of the data, the expected risk of \(f_T\) is bounded by the same left-hand side. It does not, without additional assumptions or a separate argument, assert the same bound for a predictor fitted once to the entire sample.

Worked Examples

Why the Bound Matters—and a Common Pitfall

The inequality is sharp in the oracle sense: the leading term is the risk of the comparison candidate, with no multiplicative factor inflating that risk. Its additive cost separates three ingredients: prior mass through \(\log(1/\pi_j)\), curvature through the available learning rate \(\eta\leq\alpha\), and sample size through division by \(n\). Better curvature can reduce the penalty because it permits a larger \(\eta\); it does not change which candidate has the smallest risk.

Common mistake: It is tempting to argue that because each candidate has bounded loss, the same logarithmic-over-\(n\) penalty follows for exponential weights. Boundedness alone does not give the mixture inequality used in the proof. Without exp-concavity (or another condition that supplies an appropriate exponential mixture guarantee), the potential comparison above need not hold for the aggregate's loss. The general bounded-loss analysis instead yields a square-root rate. To claim the fast rate, verify exp-concavity on the entire convex prediction set and use a learning rate no larger than its valid parameter.