Aggregation with Exponential Weights is Optimal in Expectation

Technical Summary: Aggregation with Exponential Weights is Optimal in Expectation

Problem Statement
The paper addresses the model selection aggregation problem under squared loss (and more generally, bounded, Lipschitz, and strongly convex losses) in a random design setting. Given a finite dictionary of functions $\mathcal{F} = \{f_1, \dots, f_M\}$ and $n$ i.i.d. samples, the goal is to construct an estimator $\hat{f}$ that achieves an excess risk $R_P(\hat{f}) - \min_{k} R_P(f_k)$ close to the minimax rate of $\log(M)/n$.

The specific focus is on the Aggregation with Exponential Weights (AEW) estimator. While AEW is known to achieve this optimal rate under specific conditions (e.g., fixed design, or random design with a Bernstein condition), its performance in the general random design setting without such assumptions has been an open problem. Specifically, Lecu´e and Mendelson (2013) posed the question of whether AEW achieves the optimal rate in expectation for sufficiently large, constant temperatures $T$, without requiring a Bernstein-type assumption. Previous results indicated suboptimality for low temperatures and for temperatures growing with $n$.

Methodology
The authors resolve this open question by establishing a new deterministic leave-one-out bound for the AEW estimator, utilizing concepts of algorithmic stability. The core of their proof relies on two novel "tilting inequalities" (Lemmas 1 and 2) that analyze the behavior of exponential weights when a single observation is removed from the sample.

1. Leave-One-Out Reduction: The authors relate the expected risk of the AEW estimator on the full sample to the average risk of estimators trained on leave-one-out subsets. This allows them to bound the expected excess risk by a deterministic inequality involving the empirical risks of the dictionary elements.
2. Tilting Inequalities:
   • Lemma 1 (General Loss): For a general loss satisfying boundedness ($B$), Lipschitz continuity ($L$), and strong convexity ($\mu$), the authors prove that if the temperature $T$ satisfies $(L^2/T) \exp(B/T) \leq \mu/2$, the loss of the weighted average of functions (using "tilted" weights derived from removing one sample) is bounded by the weighted average of the individual losses. This inequality is tighter than what can be derived via standard Jensen's inequality, which would introduce a multiplicative factor of $e^{B/T} > 1$.
   • Lemma 2 (Squared Loss): For the specific case of squared loss on $[0, b]$, a similar inequality is proven under the condition $T \geq 4b^2$. The proof involves a specific analysis of the function $\phi(v) = \exp(v^2/T)/(v+r)$ to show monotonicity properties that allow for a tight bound without the exponential factor.
3. Variational Inequality: The proof concludes by applying a standard variational inequality for exponential weights (Lemma 3) to the deterministic bound derived from the leave-one-out analysis.

Key Contributions and Results

• Theorem 1 (Optimality in Expectation): The paper proves that for any distribution $P$ and dictionary $\mathcal{F}$, the AEW estimator achieves an expected excess risk bounded by:
  $$\mathbb{E}[R_P(\hat{f}_T)] \leq \min_{k} R_P(f_k) + \frac{T \log M}{n+1}$$
  provided the temperature $T$ satisfies $(L^2/T) \exp(B/T) \leq \mu/2$. For squared loss on $[0, b]$, this condition simplifies to $T \geq 4b^2$. Crucially, this result holds without a Bernstein condition.
• Resolution of the Open Question: This result provides a positive answer to the open question posed by Lecu´e and Mendelson (2013), confirming that AEW is minimax-rate optimal in expectation for large enough constant temperatures in random design.
• Phase Transition Characterization: The paper complements the positive result with lower bounds demonstrating a sharp phase transition:
  • Proposition 1: If the temperature $T$ grows unboundedly with $n$ (i.e., $T \to \infty$ as $n \to \infty$), AEW is suboptimal in expectation. The excess risk can be significantly larger than the minimax rate.
  • Proposition 2: For temperatures $T \geq c_2 \sqrt{n}/\log(n)$, AEW is suboptimal in probability, confirming that simply increasing the temperature does not guarantee optimality if it scales with the sample size.
• Tightness of Bounds: The authors show that their upper bound (Theorem 1) and lower bound (Proposition 1) are tight in the first order for large $M$ and $n$, implying that the constant factors in the temperature condition cannot be improved.

Significance
The paper settles a long-standing open problem regarding the optimality of exponential weights aggregation in the basic random design setting. By proving that AEW achieves the minimax rate in expectation for constant, sufficiently large temperatures without requiring favorable assumptions on the dictionary (Bernstein conditions), the authors clarify the precise conditions under which this widely used estimator is effective.

The work highlights a sharp phase transition in the performance of AEW: it is optimal for constant temperatures but becomes suboptimal if the temperature grows with the sample size. The proof technique, particularly the novel tilting inequalities (Lemmas 1 and 2), is presented as a significant methodological contribution that avoids the looseness of standard convexity arguments (like Jensen's inequality) which would otherwise fail to yield the optimal constant-free bound. The authors note that the proof idea for Lemma 2 was developed in interaction with an LLM, though the mathematical correctness and responsibility for the work rest with the authors.