Aggregation with Exponential Weights is Optimal in Expectation

Mikael M{\o}ller H{\o}gsgaard; Patrick Rebeschini; Tobias Wegel

arxiv: 2607.02247 · v1 · pith:HZ5BVZ4Lnew · submitted 2026-07-02 · 🧮 math.ST · cs.LG· stat.ML· stat.TH

Aggregation with Exponential Weights is Optimal in Expectation

Mikael M{\o}ller H{\o}gsgaard , Patrick Rebeschini , Tobias Wegel This is my paper

Pith reviewed 2026-07-03 03:50 UTC · model grok-4.3

classification 🧮 math.ST cs.LGstat.MLstat.TH

keywords model selection aggregationexponential weightsexcess riskstrong convexityminimax optimalityphase transitionrandom design

0 comments

The pith

The aggregation with exponential weights estimator achieves the excess risk bound T log(M)/(n+1) in expectation for sufficiently large constant temperatures, without a Bernstein-type assumption.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper proves that aggregation with exponential weights attains the excess risk T log(M)/(n+1) in expectation for model selection aggregation with squared loss. The bound holds for arbitrary distributions when the loss is bounded by B, L-Lipschitz, and mu-strongly convex, as long as the temperature T satisfies (L squared over T) times exp(B over T) is at most mu over 2. No Bernstein-type assumption on the loss is needed. For squared loss with predictions and labels in [0,b], any T at least 4b squared works. The result shows AEW becomes minimax optimal in expectation once T exceeds a fixed constant threshold, resolving an open question from 2013.

Core claim

Without requiring a Bernstein-type assumption, the AEW estimator achieves the excess risk T log(M)/(n+1) in expectation whenever the temperature T satisfies (L^2/T)exp(B/T) ≤ mu/2. Here the loss is bounded by B, L-Lipschitz continuous and mu-strongly convex, M is the number of dictionary elements, and n i.i.d. samples are observed from any distribution. For squared loss, T ≥ 4b^2 suffices when predictions and labels are [0,b]-valued.

What carries the argument

The aggregation with exponential weights (AEW) estimator, which assigns weights to each of the M models proportional to exp(-T times its empirical risk) and forms their convex combination.

Load-bearing premise

The loss must be bounded by B, L-Lipschitz continuous, and mu-strongly convex, and the temperature T must satisfy the inequality (L squared over T) times exp(B over T) at most mu over 2.

What would settle it

An explicit loss that is bounded, L-Lipschitz and mu-strongly convex together with a temperature T meeting the inequality, yet for which the expected excess risk of AEW exceeds T log(M)/(n+1) on some distribution with n samples and M models, would falsify the claim.

Figures

Figures reproduced from arXiv: 2607.02247 by Mikael M{\o}ller H{\o}gsgaard, Patrick Rebeschini, Tobias Wegel.

read the original abstract

The aggregation with exponential weights (AEW) estimator is not fully understood in the basic setting of model selection aggregation with squared loss. In particular, whether it is minimax-rate optimal in expectation for large enough fixed temperatures and under random design has been an open problem since its introduction, which was explicitly posed by Lecu\'{e} and Mendelson (2013). In this paper, we settle this problem by showing that \emph{without} requiring a Bernstein-type assumption, the AEW indeed achieves the excess risk $T \log (M) / (n+1)$ in expectation, whenever the temperature $T$ satisfies $(L^2/T)\exp(B/T)\leq \mu /2$. Here, the number of dictionary elements is $M$, the estimator has observed $n$ i.i.d. samples from any distribution, and the loss is assumed to be bounded by $B$, $L$-Lipschitz continuous and $\mu$-strongly convex. For squared loss, we show that $T\geq 4 b^2$ suffices when the predictions and labels are $[0,b]$-valued. Because AEW is known to be suboptimal in expectation for temperatures below some constant, this shows that AEW has a sharp phase transition when the temperature is large enough but constant, as conjectured by Lecu\'{e} and Mendelson.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper settles the Lecué-Mendelson open question on AEW optimality in expectation for large fixed T but its general temperature condition fails to cover the squared loss example at the stated threshold.

read the letter

The main point is that this work proves AEW attains the T log(M)/(n+1) excess risk rate in expectation without Bernstein assumptions, provided the temperature satisfies (L²/T)exp(B/T) ≤ μ/2. This removes a standing restriction from earlier results and gives an explicit sufficient condition on T.

It does well by making the phase transition for large constant T concrete and by verifying the condition works for squared loss when T ≥ 4b² under [0,b]-valued data.

The soft spot is the constants. For squared loss the natural parameters are L=2b, B=b², μ=2. Substituting T=4b² into the general inequality yields exp(0.25) ≈ 1.28 on the left side, which exceeds μ/2 = 1. So the claimed T does not satisfy the stated sufficient condition for the motivating case. This suggests either the general theorem needs a larger T, the displayed bound has loose or incorrect constants, or the Lipschitz/strong-convexity parameters are defined differently than the obvious ones. Any of these would make the phase-transition claim rest on an unverified step.

The paper is aimed at researchers working on model selection aggregation and minimax rates. Readers tracking the 2013 question will get value from the explicit condition, provided the mismatch is resolved. It deserves peer review because the underlying question is substantive and the approach is direct, even if the constants require tightening.

Referee Report

1 major / 0 minor

Summary. The manuscript claims to resolve the open problem of Lecué and Mendelson (2013) by proving that aggregation with exponential weights (AEW) achieves the excess risk bound T log(M)/(n+1) in expectation (without Bernstein-type assumptions) whenever the temperature satisfies (L²/T)exp(B/T) ≤ μ/2, for losses that are B-bounded, L-Lipschitz and μ-strongly convex; it further states that T ≥ 4b² suffices for squared loss on [0,b]-valued data.

Significance. If correct, the result establishes minimax-rate optimality in expectation for AEW at large enough constant temperatures under random design, confirming the conjectured sharp phase transition and providing a parameter-free derivation of the bound under the stated loss and temperature conditions.

major comments (1)

[Abstract] Abstract (paragraph 2): the general sufficient condition (L²/T)exp(B/T)≤μ/2 is violated by the squared-loss parameters at the claimed T=4b². Substituting μ=2, L=2b, B=b² yields (4b²/T)exp(B/T)=exp(0.25)≈1.284 >1=μ/2. This is load-bearing for the central claim, as the phase-transition result for the motivating example therefore rests on either an unstated adjustment to the general theorem or a separate argument whose details must be supplied and verified.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the inconsistency between the general sufficient condition and the claimed temperature for squared loss. We address the point below and will revise the manuscript to improve clarity.

read point-by-point responses

Referee: [Abstract] Abstract (paragraph 2): the general sufficient condition (L²/T)exp(B/T)≤μ/2 is violated by the squared-loss parameters at the claimed T=4b². Substituting μ=2, L=2b, B=b² yields (4b²/T)exp(B/T)=exp(0.25)≈1.284 >1=μ/2. This is load-bearing for the central claim, as the phase-transition result for the motivating example therefore rests on either an unstated adjustment to the general theorem or a separate argument whose details must be supplied and verified.

Authors: We agree that the general condition (L²/T)exp(B/T) ≤ μ/2 is not met at T=4b² under the squared-loss parameters (μ=2, L=2b, B=b²). The manuscript treats the squared-loss case via a separate, direct argument (detailed in Section 4) that establishes the excess-risk bound for T ≥ 4b² without relying on the general sufficient condition derived for arbitrary losses. This separate argument exploits the specific structure of the squared loss to obtain the stated temperature. We acknowledge that the abstract does not make this separation explicit, which can create the impression that the general theorem applies directly. We will revise the abstract to state clearly that the squared-loss result is obtained by a tailored analysis, and we will add a brief pointer in the abstract to the relevant section so that the details are readily verifiable. revision: yes

Circularity Check

0 steps flagged

No significant circularity; bound derived from explicit assumptions

full rationale

The paper states a theorem giving the excess-risk bound T log(M)/(n+1) under the explicit loss assumptions (bounded by B, L-Lipschitz, μ-strongly convex) and the temperature condition (L²/T)exp(B/T)≤μ/2. This is presented as a direct consequence of those inputs rather than a self-referential or fitted construction. The squared-loss case is handled by a separate sufficient condition T≥4b². No load-bearing self-citation, self-definitional step, or reduction of a prediction to a fitted input appears in the abstract or skeptic analysis. The noted numerical mismatch between the general condition and the squared-loss parameters is a potential correctness issue, not a circularity reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on three loss properties (boundedness, Lipschitz continuity, strong convexity) and an explicit lower bound on temperature; these are standard domain assumptions rather than new entities or fitted constants.

axioms (2)

domain assumption Loss is bounded by B, L-Lipschitz, and μ-strongly convex
Invoked in abstract paragraph 2 to obtain the temperature condition and the rate T log(M)/(n+1)
domain assumption Data are i.i.d. from an arbitrary distribution (random design)
Stated in abstract paragraph 2; required for the expectation bound to hold uniformly

pith-pipeline@v0.9.1-grok · 5793 in / 1446 out tokens · 31931 ms · 2026-07-03T03:50:47.726291+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Alquier, P. (2021). User-friendly introduction to PAC-Bayes bounds.arXiv preprint arXiv:2110.11216

work page arXiv 2021
[2]

Audibert, J.-Y. (2007). Progressive mixture rules are deviation suboptimal.Advances in Neural Information Processing Systems (NeurIPS)

work page 2007
[3]

Audibert, J.-Y. (2009). Fast learning rates in statistical inference through aggregation.Annals of Statistics

work page 2009
[4]

(2004).Statistical learning theory and stochastic optimization: Ecole d’Et´ e de Probabilit´ es de Saint-Flour XXXI-2001

Catoni, O. (2004).Statistical learning theory and stochastic optimization: Ecole d’Et´ e de Probabilit´ es de Saint-Flour XXXI-2001. Springer

work page 2004
[5]

(2007).PAC-Bayesian supervised classification: The thermodynamics of statistical learning

Catoni, O. (2007).PAC-Bayesian supervised classification: The thermodynamics of statistical learning. Institute of Mathematical Statistics

work page 2007
[6]

Dai, D., Rigollet, P., and Zhang, T. (2012). Deviation optimal learning using greedy Q-aggregation.Annals of Statistics

work page 2012
[7]

and Tsybakov, A

Dalalyan, A. and Tsybakov, A. B. (2008). Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity.Machine Learning

work page 2008
[8]

and Warmuth, M

Forster, J. and Warmuth, M. K. (2002). Relative expected instantaneous loss bounds.Journal of Computer and System Sciences

work page 2002
[9]

Hoeven, D., Erven, T., and Kot lowski, W. (2018). The many faces of exponential weights in online learning. Proceedings of the Conference on Learning Theory (COLT)

work page 2018
[10]

Juditsky, A., Rigollet, P., and Tsybakov, A. B. (2008). Learning by mirror averaging.Annals of Statistics

work page 2008
[11]

and Levy, K

Koren, T. and Levy, K. (2015). Fast rates for exp-concave empirical risk minimization.Advances in Neural Information Processing Systems (NeurIPS). Lecu´ e, G. and Mendelson, S. (2009). Aggregation via empirical risk minimization.Probability theory and related fields. Lecu´ e, G. and Mendelson, S. (2013). On the optimality of the aggregate with exponential...

work page 2015
[12]

and Barron, A

Leung, G. and Barron, A. R. (2006). Information theory and mixing least-squares regressions.IEEE Transactions on Information Theory

work page 2006
[13]

and Warmuth, M

Littlestone, N. and Warmuth, M. K. (1994). The weighted majority algorithm.Information and computation

work page 1994
[14]

Mourtada, J., Vaˇ skeviˇ cius, T., and Zhivotovskiy, N. (2023). Local risk bounds for statistical aggregation.Proceedings of the Conference on Learning Theory (COLT)

work page 2023
[15]

and Tsybakov, A

Rigollet, P. and Tsybakov, A. B. (2012). Sparse estimation by exponential weighting.Statistical Science

work page 2012
[16]

Tsybakov, A. B. (2003). Optimal rates of aggregation.Proceedings of the Conference on Learning Theory (COLT)

work page 2003
[17]

Vovk, V. G. (1990). Aggregating strategies.Proceedings of the Conference on Learning Theory (COLT)

work page 1990
[18]

Yang, Y. (2000). Mixing strategies for density estimation.Annals of Statistics. 12

work page 2000

[1] [1]

Alquier, P. (2021). User-friendly introduction to PAC-Bayes bounds.arXiv preprint arXiv:2110.11216

work page arXiv 2021

[2] [2]

Audibert, J.-Y. (2007). Progressive mixture rules are deviation suboptimal.Advances in Neural Information Processing Systems (NeurIPS)

work page 2007

[3] [3]

Audibert, J.-Y. (2009). Fast learning rates in statistical inference through aggregation.Annals of Statistics

work page 2009

[4] [4]

(2004).Statistical learning theory and stochastic optimization: Ecole d’Et´ e de Probabilit´ es de Saint-Flour XXXI-2001

Catoni, O. (2004).Statistical learning theory and stochastic optimization: Ecole d’Et´ e de Probabilit´ es de Saint-Flour XXXI-2001. Springer

work page 2004

[5] [5]

(2007).PAC-Bayesian supervised classification: The thermodynamics of statistical learning

Catoni, O. (2007).PAC-Bayesian supervised classification: The thermodynamics of statistical learning. Institute of Mathematical Statistics

work page 2007

[6] [6]

Dai, D., Rigollet, P., and Zhang, T. (2012). Deviation optimal learning using greedy Q-aggregation.Annals of Statistics

work page 2012

[7] [7]

and Tsybakov, A

Dalalyan, A. and Tsybakov, A. B. (2008). Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity.Machine Learning

work page 2008

[8] [8]

and Warmuth, M

Forster, J. and Warmuth, M. K. (2002). Relative expected instantaneous loss bounds.Journal of Computer and System Sciences

work page 2002

[9] [9]

Hoeven, D., Erven, T., and Kot lowski, W. (2018). The many faces of exponential weights in online learning. Proceedings of the Conference on Learning Theory (COLT)

work page 2018

[10] [10]

Juditsky, A., Rigollet, P., and Tsybakov, A. B. (2008). Learning by mirror averaging.Annals of Statistics

work page 2008

[11] [11]

and Levy, K

Koren, T. and Levy, K. (2015). Fast rates for exp-concave empirical risk minimization.Advances in Neural Information Processing Systems (NeurIPS). Lecu´ e, G. and Mendelson, S. (2009). Aggregation via empirical risk minimization.Probability theory and related fields. Lecu´ e, G. and Mendelson, S. (2013). On the optimality of the aggregate with exponential...

work page 2015

[12] [12]

and Barron, A

Leung, G. and Barron, A. R. (2006). Information theory and mixing least-squares regressions.IEEE Transactions on Information Theory

work page 2006

[13] [13]

and Warmuth, M

Littlestone, N. and Warmuth, M. K. (1994). The weighted majority algorithm.Information and computation

work page 1994

[14] [14]

Mourtada, J., Vaˇ skeviˇ cius, T., and Zhivotovskiy, N. (2023). Local risk bounds for statistical aggregation.Proceedings of the Conference on Learning Theory (COLT)

work page 2023

[15] [15]

and Tsybakov, A

Rigollet, P. and Tsybakov, A. B. (2012). Sparse estimation by exponential weighting.Statistical Science

work page 2012

[16] [16]

Tsybakov, A. B. (2003). Optimal rates of aggregation.Proceedings of the Conference on Learning Theory (COLT)

work page 2003

[17] [17]

Vovk, V. G. (1990). Aggregating strategies.Proceedings of the Conference on Learning Theory (COLT)

work page 1990

[18] [18]

Yang, Y. (2000). Mixing strategies for density estimation.Annals of Statistics. 12

work page 2000