Aggregation with Exponential Weights is Optimal in Expectation Mikael Møller Høgsgaard1 , Patrick Rebeschini1 , and Tobias Wegel2 1 2
Department of Statistics, University of Oxford Department of Computer Science, ETH Zurich
arXiv:2607.02247v1 [math.ST] 2 Jul 2026
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é and Mendelson (2013). In this paper, we settle this problem by showing that 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 (L2 /T ) exp(B/T ) ≤ µ/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 µ-strongly convex. For squared loss, we show that T ≥ 4b2 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é and Mendelson.
1
Introduction and Main Results
Let (X , Σ) be some abstract measurable space, Y ⊂ R convex, and P be an arbitrary distribution on n (X × Y, Σ ⊗ B(Y)). Denote S = (Xi , Yi )i=1 with n ∈ N an i.i.d. sample from P and let F = {f1 , . . . , fM } with M ∈ N be an arbitrary but fixed finite dictionary of measurable functions fk : X → Y. Given a loss function ℓ : Y 2 → [0, ∞) where ℓ(b y , y) measures the loss of predicting yb when the label is y, the model selection aggregation problem is to learn a function f : X → Y using the sample S that achieves small risk RP (f ) :=
E
[ℓ(f (X), Y )]
(X,Y )∼P
when compared to the best function in F, that is, to achieve small excess risk RP (f ) − min1≤k≤M RP (fk ). In this paper, we consider loss functions that satisfy the following assumption: Assumption 1. Let B, L, µ > 0. The loss function ℓ : Y 2 → [0, ∞), satisfies that: 1. ℓ is bounded by B: for all yb, y ∈ Y, ℓ(b y , y) ≤ B. 2. ℓ(·, y) is L-Lipschitz continuous for any y ∈ Y: for all y, yb, yb′ ∈ Y, |ℓ(b y , y) − ℓ(b y ′ , y)| ≤ L |b y − yb′ |. 3. ℓ(·, y) is µ-strongly convex for any y ∈ Y: for all y ∈ Y, the map yb 7→ ℓ(b y , y) − µ2 yb2 is convex on Y. An important instance of such a loss function is the squared loss ℓ(b y , y) = (b y − y)2 on the label space 2 Y = [0, b], in which case Assumption 1 holds with B = b , L = 2b and µ = 2. Model selection aggregation is well-studied (Audibert, 2007, 2009; Lecué and Mendelson, 2009; Lecué and Rigollet, 2014), and the minimax rate in expectation for squared loss was proven by Tsybakov (2003) to be, up to constant factors independent of n and M , h i log(M ) inf sup E n RP (fbS ) − min RP (fk ) ≍ min 1, . 1≤k≤M n fb P,|F |=M S∼P Authors are listed alphabetically.
1
We refer to Mourtada et al. (2023) for a recent overview of the literature on model selection aggregation. Perhaps one of the most well-known estimators that one can apply to this setting is the PAC-Bayesian aggregation with exponential weights (AEW) algorithm, which has its origins in online learning (Vovk, 1990; Littlestone and Warmuth, 1994; Hoeven et al., 2018) and has been studied extensively over the years (Yang, 2000; Catoni, 2004; Leung and Barron, 2006; Dalalyan and Tsybakov, 2008; Juditsky et al., 2008; Rigollet and Tsybakov, 2012; Alquier, 2021; Mourtada et al., 2023). Denoting the empirical risk b S (f ) = 1 Pn ℓ(f (Xi ), Yi ), the AEW is defined as with respect to the sample S as R i=1 n fbT =
M X k=1
θbk fk
where
b S (fk ) exp − Tn R b θk = PM n b j=1 exp − T RS (fj )
for all k ∈ {1, . . . , M } .
(1)
The AEW assigns a weight to each dictionary element which scales exponentially in the negative of the b S with respect to the sample S. Here T > 0 is a hyperparameter chosen by the estimator, empirical risk R and is called the temperature of the exponential weights. The name “temperature” has its origin in the fact that the exponential weights can be viewed as a Gibbs posterior distribution over the dictionary, inspired by thermodynamics (Catoni, 2004). The larger the temperature, the more uniform the weights θbk are. In particular, for small temperatures, the AEW estimator behaves similarly to empirical risk minimization on the dictionary, whereas larger temperatures induce a hedging effect. The known bounds for AEW are summarized by Lecué and Mendelson (2013); we restate them here for simplicity for squared loss on [0, 1]. In short, it is known (Catoni, 2004; Audibert, 2007; P Mourtada et al., n 1 b(i) 2023) that if the AEW estimator is averaged into the progressive mixture rule fbpm = n+1 i=0 fT , where (i) each fbT is an AEW estimator on the first i samples and with large enough constant temperature T (e.g., T = 8), then the minimax rate is achieved, that is, E[RP (fbpm )] ≤ min1≤j≤M RP (fj ) + 8 log(M )/(n + 1). Moreover, it is known that in fixed design and for certain assumptions on the noise, an analogous guarantee can be obtained in-sample by AEW with large enough fixed temperature (Dalalyan and Tsybakov, 2008; Dai et al., 2012). Finally, for random design, it has been shown that AEW can achieve the guarantee E[RP (fbT )] ≤ min1≤j≤M RP (fj ) + C log(M )/(n + 1) under a Bernstein condition (that is, assuming a favorable position of the dictionary relative to the distribution), where now C depends on that assumption (Catoni, 2007; Lecué and Mendelson, 2013; Alquier, 2021). The proof techniques appearing in those results are substantially different from those used in this work. For random design and without assuming any Bernstein-type condition, only the following is known for the AEW estimator itself, as summarized in Lecué and Mendelson (2013) (again for squared loss for simplicity). For low temperatures T ≤ c1 , where c1 is a small enough constant independent of M, n, the AEW √ estimator is suboptimal both in expectation and in probability. And for any temperature T ≤ c2 n/ log(n) (including moderately large temperatures), the AEW estimator is suboptimal on an event of constant probability. Intuitively, the negative result for low temperatures is in line with the AEW mimicking empirical risk minimization, as the latter is also known to be suboptimal (Juditsky et al., 2008). However, to the best of our knowledge, the optimality of exponential weights in expectation and under random design when T ≥ c3 for some constant c3 has remained an open problem, posed explicitly by Lecué and Mendelson (2013), who also conjectured the answer to be positive:1 Open Question: In random design model selection aggregation with squared loss, is there a universal constant c3 > 0 such that for T ≥ c3 , the AEW estimator with temperature T achieves the optimal rate of aggregation log(M )/n in expectation, uniformly over dictionaries F of size M and arbitrary distributions P on X × [0, b], without a Bernstein condition? In this paper, we give a positive resolution to the question, showing that for sufficiently large constant temperatures, the exponential weights estimator is optimal in expectation. We prove this under the more general Assumption 1, which contains the squared loss as a special case; however, for squared loss, we also provide a more direct proof that yields a slightly tighter bound (in terms of constant factors).
1 A previous version of the paper Lecué and Mendelson (2013) states the open question of optimality as “Question 1.2” and explicitly conjectures the phase transition proved in the present work, as well as providing some more commentary. This previous version can be found at https://maths-people.anu.edu.au/%7Emendelso/papers/LM6-07-07-10.pdf.
2
suboptimal (Lecué and Mendelson, 2013)
optimal (Theorem 1)
gap
suboptimal (Proposition 1)
in expectation T ≤ c1
in probability
c1 c3 T ≥ c3 and constant suboptimal (Lecué and Mendelson, 2013) √ T ≤ c2 n/ log n
T → ∞ as n → ∞ suboptimal (Proposition 2) √ c2 n log(n)
√ T ≥ c2 n/ log n
Figure 1: Minimax rate optimality and suboptimality of the AEW estimator for squared loss as a function of the temperature T , when considered uniformly over M , dictionaries of size M , and distributions. Theorem 1 (Minimax-rate optimality of AEW in expectation). Let the loss ℓ satisfy Assumption 1 with parameters B, L and µ. For every M, n ∈ N, temperature T ∈ (0, ∞) satisfying (L2 /T ) exp(B/T ) ≤ µ/2, dictionary F = {f1 , . . . , fM } of measurable functions fk : X → Y, and distribution P on X × Y, the aggregation with exponential weights estimator (1) satisfies h i T log M E n RP (fbT ) ≤ min RP (fk ) + . S∼P 1≤k≤M n+1 For squared loss on Y = [0, b], the condition (L2 /T ) exp(B/T ) ≤ µ/2 can be replaced by T ∈ [4b2 , ∞). Remark 1. For squared loss on [0, b], the parameters from Assumption 1 are given by B = b2 , L = 2b and µ = 2, and so the first condition of Theorem 1 yields T ≥ b2 /W (1/4) ≈ 4.904b2 where W is the Lambert-W-function; our proof in the special case of squared loss hence lowers that bound on T to be just 4b2 . In particular, for squared loss on [0, 1], choosing T = 4 yields the excess risk 4 log(M )/(n + 1). Note that in Theorem 1 no Bernstein condition is assumed. This resolves the open question from above. We now complement the positive result of Theorem 1 by showing that if the temperature grows unboundedly with n (i.e., T → ∞ as n → ∞) then AEW is suboptimal in expectation. See also Figure 1. In contrast to Theorem 1, the following propositions are somewhat straightforward to prove. Proposition 1. Let ℓ be the squared loss and Y = [0, 1]. For every T > 0, n ∈ N, and M ∈ N with M ≥ 2, there exists a dictionary F of size M , a distribution P on X × [0, 1], and a γM ∈ [1/4, 1] depending only on M , such that AEW with any temperature T has excess risk lower bounded almost surely as T log(M − 1) P n RP (fbT ) ≥ min RP (fj ) + γM min 1, = 1. 1≤j≤M S∼P n Moreover, it holds that γM → 1 as M → ∞. Now let Tn,M be any schedule of temperatures depending on n and M . Then, if for any sequence Mn ≥ 3 it holds that log(Mn )/n → 0 and Tn,Mn → ∞ as n → ∞, AEW with this schedule is minimax-rate suboptimal (in expectation). Whenever Tn,M is independent of M and Tn,M = Tn → ∞ as n → ∞, such a sequence can be chosen so that the lower bound converges to 1. Along any sequence Mn with log(Mn )/n → 0 and Tn,Mn → ∞, the ratio between the lower bound in Proposition 1 and the minimax rate goes to infinity. Hence, AEW is minimax-rate suboptimal in expectation along such sequences. Remark 2. Notice that the fact that γM → 1 as M → ∞ implies that for large n and M , our lower bound from Proposition 1 and the upper bound from Theorem 1 witness each other’s tightness not only up to constants, but in the first order. Therefore, the universal constant factors in both bounds cannot be improved whenever T ≥ 4. For T ≤ c1 , the lower bound in Proposition 1 is necessarily not tight in first order, due to the stronger lower bound by Lecué and Mendelson (2013). By a similar argument, we now complement the lower bound in probability from Lecué and Mendelson √ (2013) for T ≤ c2 n/ log(n) by showing that, unsurprisingly, choosing T larger does not help in general.
3
√ Proposition 2. Let ℓ be the squared loss and Y = [0, 1]. For every n ≥ 2 and every T ≥ c2 n/ log(n) (where c2 is the universal constant from Lecué and Mendelson (2013)), there exist M ≤ n1/c2 + 2, a dictionary F = {f1 , . . . , fM } with values in [0, 1], and a distribution P on X × [0, 1] such that 1 P n RP (fbT ) ≥ min RP (fj ) + √ = 1. 1≤j≤M S∼P 4 n Notice that since M ≤ n1/c2 + 2, the dictionary size can grow at most polynomially √ in the sample size, and therefore the optimal rate of aggregation would be log(M )/n ≲ log(n)/n ≪ 1/ n. Hence, the AEW estimator is minimax rate suboptimal for temperatures in this regime. Together with the known results described above, this fills in the remaining gaps in the understanding of the AEW estimator for squared loss on [0, 1], up to the difference in constants. This is visualized in Figure 1. Indeed, the AEW is always suboptimal in probability, and for temperatures below some constant c1 or growing with n, it is also suboptimal in expectation. But for T large enough and constant, it is optimal in expectation. This covers all values of T , except for the gap between these constants. We now prove Theorem 1 in Section 2 and then Propositions 1 and 2 in Sections 3.1 and 3.2.
2
Proof of Theorem 1
The proof of Theorem 1 reduces to a deterministic leave-one-out bound that uses ideas of algorithmic stability. Recall that the loss ℓ satisfies Assumption 1 with parameters B, L, µ. N
Let N = n + 1 ≥ 2 and (xi , yi )i=1 ⊂ X × Y be an arbitrary fixed deterministic sample. Denote PN ℓij = ℓ(fj (xi ), yi ), the loss of the i-th observation for function fj , and Sj = i=1 ℓij , the total loss for (−i) (−i) function fj . We now let p1 , . . . , pM be the exponential weights formed on the sub-sample of size n after removing the ith observation and with temperature T , that is, for each j ∈ [M ] (−i)
pj
exp (−(Sj − ℓij )/T ) pj exp (ℓij /T ) = PM = PM k=1 exp (−(Sk − ℓik )/T ) k=1 pk exp (ℓik /T )
where
exp (−Sj /T ) pj = PM . k=1 exp (−Sk /T )
Proposition 3 (A deterministic leave-one-out inequality). In the setting described above, if the loss satisfies Assumption 1 with parameters B, L, µ, and T satisfies (L2 /T ) exp(B/T ) ≤ µ/2, it holds that N M N 1 X X (−i) 1 X T log M ℓ pj fj (xi ), yi ≤ min ℓ (fj (xi ), yi ) + , (2) 1≤j≤M N N i=1 N j=1 i=1 PM (−i) where j=1 pj fj is the AEW estimator on the sample with the i-th observation removed. For squared loss on Y = [0, b], the condition (L2 /T ) exp(B/T ) ≤ µ/2 can be replaced by T ∈ [4b2 , ∞). N
Before proving Proposition 3, we show how it implies Theorem 1. Let S′ = (Xi , Yi )i=1 be an i.i.d. sample from P . For each i, we can compute the exponential weights estimator on the sample with (Xi , Yi ) (−i) (−i) removed; let fbT denote the estimator with the i’th observation removed and θbj its weight on fj . By (−N ) exchangeability and independence of the data points, we can rewrite the risk of fbT = fb as T
h
i
h i (−N ) E n RP (fbT ) = E ℓ(fbT (XN ), YN ) S∼P S′ ∼P N h i (−i) = E ℓ(fbT (Xi ), Yi ) S′ ∼P N " # N 1 X b(−i) = E ℓ(fT (Xi ), Yi ) S′ ∼P N N i=1 N M X X 1 (−i) = E ℓ θbj fj (Xi ), Yi . N i=1 S′ ∼P N j=1
4
(for any i ∈ [N ])
(−i) (−i) We can now apply Proposition 3 with the sample (Xi , Yi )N = θbj . By Equation (2), we i=1 and pj 2 2 observe that, as long as (L /T ) exp(B/T ) ≤ µ/2, or T ≥ 4b for squared loss, the right-hand side is bounded above by # " N h i 1 X T log M b E RP (fT ) ≤ E min ℓ(fj (Xi ), Yi ) + S∼P n N S′ ∼P N 1≤j≤M N i=1 N
1 X T log M E [ℓ(fj (Xi ), Yi )] + 1≤j≤M N N (Xi ,Yi )∼P i=1
≤ min
= min RP (fj ) + 1≤j≤M
T log M , n+1
which concludes the proof of Theorem 1. It remains to prove Proposition 3.
2.1
Proof of Proposition 3
PN Recall the notation ℓij = ℓ(fj (xi ), yi ) and Sj = i=1 ℓij . In the first step, we apply the following lemmas. Here we make the case distinction between general losses satisfying Assumption 1 and squared loss, as the proof for both is somewhat different. They are the key to our proof and seem to be novel in the literature. Lemma 1 (A tilting inequality). Suppose Assumption 1 holds. Let M ∈ N, (p1 , . . . , pM ) be a probability distribution, and y, yb1 , . . . ybM ∈ Y be any fixed values. Define the tilted probability distribution (q1 , . . . , qM ) as pj exp( T1 ℓ(b yj , y)) qj = PM . 1 yk , y)) k=1 pk exp( T ℓ(b If T > 0 satisfies (L2 /T ) exp(B/T ) ≤ µ/2, then it holds that M M X X ℓ qj ybj , y ≤ pj ℓ(b yj , y). j=1
(3)
j=1
The proof of Lemma 1 is in Section 2.2. For squared loss we can prove the same with a slightly weaker requirement on the temperature. We split this into a separate lemma, because the proof is quite different. The proof of Lemma 2 is in Section 2.3. Lemma 2 (A tilting inequality for squared loss). Let M ∈ N, b > 0, and (p1 , . . . , pM ) be a probability distribution, and y, yb1 , . . . , ybM ∈ [0, b] be any fixed values. Define the tilted probability distribution (q1 , . . . , qM ) as pj exp( T1 (b yj − y)2 ) qj = PM . 1 yk − y)2 ) k=1 pk exp( T (b If T ∈ [4b2 , ∞), then the following inequality is true: 2 M M X X qj ybj − y ≤ pj (b yj − y)2 . j=1
(4)
j=1
We use Lemmas 1 and 2 with ybj = fj (xi ), y = yi by recalling that the weights of the exponential weights estimator with the ith datapoint removed are given by (−i)
pj
pj exp (ℓij /T ) pj exp (ℓ(fj (xi ), yi )/T ) exp (−(Sj − ℓij )/T ) = PM = PM , = PM exp (−(S − ℓ )/T ) p exp (ℓ /T ) k ik ik k=1 k=1 k k=1 pk exp (ℓ(fk (xi ), yi )/T )
where in turn pj are the weights of the exponential weights estimator with the full sample. Since we assumed the necessary conditions on the temperature T , for a single datapoint i we obtain from Lemmas 1 5
and 2 that
M M M X X X (−i) ℓ pj fj (xi ), yi ≤ pj ℓ(fj (xi ), yi ) = pj ℓij . j=1
j=1
j=1
We can sum this inequality over samples i and obtain that N M M N M X X X X X (−i) ℓ pj fj (xi ), yi ≤ pj ℓij = pj Sj . i=1
j=1
j=1
i=1
j=1
To conclude the proof, we can now apply the following elementary lemma to the right-hand side. It is well-known; we restate and prove (in Section 2.4) it for completeness. Lemma 3 (An elementary variational inequality for exponential weights). Let M ∈ N, let S1 , . . . , SM ∈ R exp(−Sj /T ) be real numbers, let T > 0 and define pj = PM exp(−S for j = 1, . . . , M . Then it holds that /T ) k
k=1
M X
pj Sj ≤ min Sj + T log M. 1≤j≤M
j=1
Applying Lemma 3, to the last display and dividing by N yields Proposition 3.
2.2
Proof of Lemma 1
To start, we rederive the following well-known fact: due to the strong convexity from Assumption 1 and convexity of Y, it holds that 2 2 M M M M X X X X µ µ pj ybj + pj ybj ℓ pj ybj , y = ℓ pj ybj , y − 2 2 j=1 j=1 j=1 j=1 2 M X µ µ ≤ pj ℓ(b yj , y) − ybj2 + pj ybj (Jensen’s inequality and strong convexity) 2 2 j=1 j=1 2 M M M X X µ X = pj ℓ(b yj , y) − pj ybj2 − pj ybj 2 j=1 j=1 j=1 M X
h
i
M X
M
µX = pj ℓ(b yj , y) − pj 2 j=1 j=1
ybj −
M X
!2 pk ybk
.
(5)
k=1
Here the last step uses the fact that for any real-valued random variable X, it holds E[(X − E[X])2 ] = E[X 2 ] − (E[X])2 . See also Lecué and Rigollet (2014, Proposition 2) for an analogous statement. We can then apply Lipschitz continuity and strong convexity (through (5)) from Assumption 1 as follows: M M M M X X X X ℓ qj ybj , y = ℓ qj ybj , y − ℓ pj ybj , y + ℓ pj ybj , y j=1
j=1 M X
j=1 M X
j=1 M X
M
µX ≤L qj ybj − pj ybj + pj pj ℓ(b yj , y) − 2 j=1 j=1 j=1 j=1
=L
M X j=1
qj
ybj −
M X k=1
! pk ybk
ybj −
M X
!2 pk ybk
k=1
(By L-Lipschitz continuity and (5)) !2 M M M X X µX + pj ℓ(b yj , y) − pj ybj − pk ybk . (6) 2 j=1 j=1 k=1
6
PM yj , y)) be the normalization constant of the distribution (q1 , . . . , qM ). To Let now Z = j=1 pj exp ( T1 ℓ(b bound the first term in (6), we can use ! ! M M M M X X X X exp ( T1 ℓ(b yj , y)) qj ybj − pk ybk = pj ybj − pk ybk Z j=1 j=1 k=1 k=1 !!# " ! M M M X X 1 1 1 X pj exp ℓ(b yj , y) − exp ℓ pk ybk , y ybj − pk ybk (7) = Z j=1 T T k=1
k=1
PM
PM
where the last equality follows by j=1 cpj (b yj − k=1 pk ybk ) = 0 for any c ∈ R, especially for c = PM 1 exp ( T ℓ( k=1 pk ybk , y)). Taking the absolute value on both sides and using the triangle inequality, we obtain that the first term of (6) is bounded by ! !! M M M M M X X X X X 1 pj 1 ybj − exp pk ybk . qj ybj − pk ybk ≤ ℓ(b yj , y) − exp ℓ pk ybk , y Z T T j=1 j=1 k=1
k=1
k=1
One can verify that the Mean Value Theorem implies the inequality Z a a x 1 1 b max {a, b} exp ∀a, b ∈ R, ∀T > 0 : − exp = dx ≤ exp exp |a − b|. T T T T T b T Applying this to Equation (7), we further obtain using B-boundedness of the loss that ! M M X X qj ybj − pk ybk j=1
k=1
! ( !)! M M M X X X 1 pk ybk yj , y) − ℓ pk ybk , y · ybj − max ℓ(b yj , y), ℓ pk ybk , y · ℓ(b T k=1 k=1 k=1 !2 X M M X L B pj ≤ exp pk ybk (By L-Lipschitz continuity of ℓ, and ℓ ≤ B) ybj − T T j=1 Z k=1 !2 X M M X L B ≤ exp pj ybj − pk ybk T T j=1 M X
pj exp ≤ T Z j=1
k=1
PM PM where the last inequality holds because Z = j=1 exp ( T1 ℓ(b yj , y))pj ≥ j=1 pj = 1. Thus, plugging this bound into the display (6), we obtain that !2 ! M M M M M M X X X X X X µ pj ybj − pk ybk ℓ qj ybj , y ≤ L qj ybj − pk ybk + pj ℓ(b yj , y) − 2 j=1 j=1 j=1 j=1 k=1
k=1
≤
L2 exp T
B T
−
µ 2
X M
pj
j=1
ybj −
M X k=1
!2 pk ybk
+
M X
pj ℓ(b yj , y)
j=1
2
µ where the condition on T implies LT exp ( B T ) − 2 ≤ 0, so the last display in the above is bounded by the last term, which concludes the proof of Lemma 1.
2.3
Proof of Lemma 2
Let U be a random variable that takes the value uj := ybj − y ∈ [−b, b] with probability pj and denote V = |U | and r = (E V 2 )1/2 , both taking values in [0, b]. If r = 0, then since V 2 = U 2 ≥ 0 is a non-negative random variable we know that U = 0 p-almost surely, that is, pj uj = 0 for all j ∈ [M ]. Therefore, we have that M M X X uj pj exp u2j /T qj uj = = 0, PM 2 k=1 pk exp (uk /T ) j=1 j=1 7
and so the left hand side of (4) vanishes. As the right hand side is always non-negative, (4) follows. Assume now that r > 0. Define the function ϕ : [0, b] → R as ϕ(v) = exp v 2 /T /(v + r). A calculation using the quotient rule yields that its derivative is given by (2v exp v 2 /T (v + r)/T − exp v 2 /T ) exp v 2 /T ϕ′ (v) = = (2v(v + r)/T − 1) . (v + r)2 (v + r)2 Since the first factor of the latter display is always positive, the sign of ϕ′ is determined by the sign of 2v(v + r)/T − 1, and since v, r ∈ [0, b], we know that 2v(v + r)/T ≤ 4b2 /T ≤ 1 where we used the assumption that T ≥ 4b2 . Therefore, on [0, b] we have ϕ′ ≤ 0 and ϕ is non-increasing. By making a case distinction between v ≥ r and v < r, we can show that this monotonicity implies (v − r) exp v 2 /T ≤ ϕ(r)(v 2 − r2 ). (8) Case v ≥ r: In this case, because ϕ(v) ≤ ϕ(r) and v 2 − r2 ≥ 0, we know that (v 2 − r2 )ϕ(v) ≤ (v 2 − r2 )ϕ(r), and so (v − r) exp v 2 /T = (v − r)(v + r)ϕ(v) = (v 2 − r2 )ϕ(v) ≤ (v 2 − r2 )ϕ(r). Case v < r: In this case, because ϕ(v) ≥ ϕ(r) and v 2 − r2 < 0, we know that (v 2 − r2 )ϕ(v) ≤ (v 2 − r2 )ϕ(r), and so by the same calculation, we have that (v − r) exp v 2 /T ≤ (v 2 − r2 )ϕ(r). By taking expectation over V in (8) we obtain that E (V − r) exp V 2 /T ≤ ϕ(r) E V 2 − r2 = 0 where the equality follows by definition of r = (E V 2 )1/2 . This implies E V exp V 2 /T ≤ r E exp V 2 /T , whereby we get M X j=1
qj uj
M X
uj pj exp u2j /T E U exp U 2 /T = = PM 2 E [exp (U 2 /T )] k=1 pk exp (uk /T ) j=1 E |U | exp U 2 /T E V exp V 2 /T = ≤ r. ≤ E [exp (U 2 /T )] E [exp (V 2 /T )]
Squaring both sides and expanding the definition of r2 we get that 2 M M X X qj uj ≤ r2 = E V 2 = pj u2j . j=1
j=1
This concludes the proof of Lemma 2 by plugging back in uj = ybj − y.
2.4
Proof of Lemma 3 exp(−S /T )
j Recall that for all j ∈ [M ], we defined pj = PM exp(−S . Since pj > 0, we can take the logarithm and k /T ) k=1 obtain ! M X Sj log pj = − − log exp (−Sk /T ) . T
k=1
We can multiply each side by pj and sum over j ∈ [M ] to obtain that ! M M X 1X pj log pj = − pj Sj − log exp (−Sk /T ) , T j=1 j=1
M X
k=1
8
where the last term remains unchanged because it is independent of j and and rearranging this, we obtain that M X
pj Sj = −T
j=1
M X
pj log pj − T log
j=1
M X
PM
j=1 pj = 1. Multiplying by T
! exp (−Sk /T )
k=1
≤ T log M − T log exp − min Sk /T 1≤k≤M
= T log M + min Sj , 1≤j≤M
where the first inequality follows because 0 ≤ −
PM
j=1 pj log pj ≤ log M (as it is the entropy of a probability PM distribution on M points), and the second holds because k=1 exp (−Sk /T ) ≥ exp (− min1≤k≤M Sk /T ).
That concludes the proof of Lemma 3.
3
Proofs of the Lower Bounds
3.1
Proof of Proposition 1
To prove Proposition 1, we construct a dictionary and a distribution. Fix n ∈ N and M ∈ N with M ≥ 2. If M = 2, then the lower bound is trivially true as log(M − 1) = 0, so assume without loss of generality that M ≥ 3, so that log(M − 1) > 0. Define for some α ∈ (0, 1] to be chosen later T log(M − 1) 2 a = αr where r = min 1, . n Let the distribution P of (X, Y ) be such that Y = 0 almost surely, and choose the dictionary f1 ≡ 0, as well as f2 = · · · = fM ≡ a. Thus f1 is the optimal dictionary element, whereas all others are suboptimal. For every sample S, almost surely, we have that b S (f1 ) = 0, R
b S (fj ) = a2 R
for j ≥ 2.
Hence the total mass put on the suboptimal functions with index j ≥ 2 is 1 − θb1 =
M X
exp −na2 /T (M − 1) exp −na2 /T . = PM 2 1 + (M − 1) exp (−na2 /T ) k=2 exp (−na /T ) j=2 1 +
Because r ≤ T log(M − 1)/n by definition of r, we get that na2 /T = αnr/T ≤ α log(M − 1). Therefore, we obtain that (M − 1) exp(−na2 /T ) ≥ (M − 1)1−α and so 1 − θb1 ≥
(M − 1)1−α . 1 + (M − 1)1−α
Notice that because the AEW estimator on this dictionary is fbT ≡ a(1 − θb1 ), and because f1 has risk zero, this means it has P n -almost surely an excess risk of at least RP (fbT ) − min RP (fj ) ≥ a2 (1 − θb1 )2 ≥ α
1≤j≤M
(M − 1)1−α 1 + (M − 1)1−α
2 r.
Since this lower bound is true for every α ∈ (0, 1], we can define γM = sup α α∈(0,1]
(M − 1)1−α 1 + (M − 1)1−α
2
and the excess risk is lower bounded by γM r for the α ∈ (0, 1] attaining the maximum (which exists). Notice that γM ∈ [1/4, 1] since for α = 1 the term is 1/4, so γM must be larger, and γM ≤ 1, follows from α ≤ 1 and ((M − 1)1−α /(1 + (M − 1)1−α ) ≤ 1. We now show that γM → 1 as M → ∞. To 9
that end, denote the function to be optimized as hM (α) = α((M −p1)1−α /(1 + (M − 1)1−α ))2 . To prove the limit, consider αM defined as αM = 1 − 1/ log(M − 1). Then we get that p the sequence 1−αM (M − 1) = exp log(M − 1) and so
hM (αM ) =
1 1− p log(M − 1)
2 log(M − 1) p → 1 1 + exp log(M − 1)
!
exp
p
as M → ∞.
By definition, we then have that γM ≥ hM (αM ) → 1 and γM ≤ 1, implying that γM → 1 as M → ∞. Plugging in the definition of r yields the proof of the first two claims in Proposition 1. Now, let Mn ≥ 3 be such that log(Mn )/n → 0 and Tn,Mn → ∞. By the first part, for each n there is a distribution and dictionary for which Tn,Mn log(Mn − 1) RP (fbTn,Mn ) − min RP (fj ) ≥ γMn min 1, . 1≤j≤M n Since Mn ≥ 3, there exists a universal constant c > 0 such that log(Mn − 1) ≥ c log Mn . Therefore RP (fbTn,Mn ) − min1≤j≤M RP (fj ) 1 n ≥ min , cTn,Mn → ∞ log(Mn )/n 4 log Mn
as n → ∞.
Thus, the excess risk is of order larger than log(Mn )/n, and hence suboptimal. It remains to show that whenever Tn,M is independent of M and Tn,M = Tn → ∞ as n → ∞, there exists a sequence Mn → ∞ such that log(Mn )/n → 0 but r = 1 for all n. By the first part, that then yields the lower bound √ γMn converging to 1 because √ Mn → ∞. To that end, consider the sequence Mn = ⌈exp(max {n/Tn , n})⌉ + 1 ≤ 3 exp(max {n/Tn , n}). Then log 3 log(Mn ) 1 1 + ≤ max → 0 as n → ∞, ,√ n Tn n n and at the same time, r = 1 because the other term in the minimum of the definition of r is lower bounded by √ Tn log(⌈exp(max {n/Tn , n})⌉) Tn (n/Tn ) Tn log(Mn − 1) ≥ ≥ = 1. n n n That concludes the proof of Proposition 1.
3.2
Proof of Proposition 2
To prove Proposition 2, we construct a dictionary and a distribution. We proceed almost identically to Section 3.1. Let the distribution P of (X, Y ) be such that Y = 0 almost surely, and choose the dictionary f1 ≡ 0, as well as f2 = · · · = fM ≡ a, where we choose a > 0 as a2 = n−1/2 . Moreover, we choose the number of dictionary elements M to satisfy √ M − 1 = exp n/T . √ The assumption on T that T ≥ c2 n/ log(n) gives √ M = exp n/T + 1 ≤ ⌈exp (log(n)/c2 )⌉ + 1 ≤ n1/c2 + 2, confirming that the dictionary is not too large. For every sample S, we have by construction that P -almost surely, b S (f1 ) = 0, b S (fj ) = a2 for j ≥ 2. R R Hence the total mass put on the suboptimal functions with index j ≥ 2 is √ M X exp −na2 /T (M − 1) exp −na2 /T (M − 1) exp (− n/T ) 1 √ 1 − θb1 = = = ≥ PM 2 /T ) 2 1 + (M − 1) exp (−na 2 1 + (M − 1) exp (− n/T ) k=2 exp (−na /T ) j=2 1 + 10
√ √ where the last inequality follows from M −1 ≥ exp ( n/T ) implying (M −1) exp (− n/T ) ≥ 1. Therefore, by noticing that fbT ≡ (1 − θb1 )a, and since f1 has risk zero, 1 RP (fbT ) − min RP (fj ) = ((1 − θb1 )a)2 ≥ n−1/2 . 1≤j≤M 4 The above holds almost surely, so the event has probability one. That concludes the proof.
4
Discussion
In this short paper, we prove that the aggregation with exponential weights estimator achieves the minimax optimal rate of aggregation T log(M )/(n + 1) with respect to M and n, for large enough fixed temperatures T , when the loss is bounded, Lipschitz continuous, and strongly convex. Importantly, this does not require a Bernstein condition and includes the squared loss as a special case. The proof at its core uses an average leave-one-out stability argument (Proposition 3). The reduction to such a leave-one-out bound is similar in spirit to existing bounds, see for instance Forster and Warmuth (2002); Koren and Levy (2015). However, the main difference and novelty of our approach is in the proof of that stability result, specifically in Lemmas 1 and 2, which explicitly makes use of the tilting of the exponential weights distribution when one sample is left out. Lemmas 1 and 2 seem to be novel, and they may also be of independent interest. We would like to remark that the tightness of Lemmas 1 and 2 is crucial. Indeed, a weaker version of Lemmas 1 and 2 can be obtained via an application of Jensen’s inequality. In the notation of Lemma 1, M M M M X X X X pj exp (ℓ(b yj , y)/T ) B/T ℓ qj ybj , y ≤ qj ℓ(b yj , y) = ℓ(b y , y) ≤ e pj ℓ(b yj , y), PM j yk , y)/T ) k=1 pk exp (ℓ(b j=1 j=1 j=1 j=1 where first inequality is Jensen, and the second inequality uses that the loss is bounded ℓ ≤ B Pthe M and k=1 pk exp (ℓ(b yk , y)/T ) ≥ 1. The resulting bound is worse than Equations (3) and (4) by the factor eB/T , which for any T ∈ (0, ∞) is strictly larger than 1. Importantly, any factor strictly larger PN than 1 means that the final bound has the same factor in front of min1≤j≤M N1 i=1 (yi − fj (xi ))2 in Proposition 3, respectively min1≤k≤M RP (fk ) in Theorem 1. Therefore, this approach would not yield a positive conclusion to the open question. This highlights the importance of Lemmas 1 and 2. We also remark that the phenomenon of achieving fast rates at the cost of a worse comparator is common in some PAC-Bayesian analyses of AEW, see for instance Alquier (2021, Example 3.1 and surrounding discussion). Together with the suboptimality results by Lecué and Mendelson (2013), Theorem 1 and Proposition 1 show that the AEW estimator undergoes a sharp phase transition when the temperature is constant, and in particular the exact value of that constant is crucial. This further demonstrates the sensitivity of the AEW to the temperature parameter, as argued by Lecué and Mendelson (2013).
Acknowledgements The authors thank Tomas Vaškevičius for helpful input. Tobias Wegel was supported by SNSF Grant 204439. Mikael Møller Høgsgaard was supported by a Carlsberg Internationalisation Fellowship. Patrick Rebeschini was funded by UK Research and Innovation (UKRI) under the UK government’s Horizon Europe funding guarantee [grant number EP/Y028333/1]. LLM Usage. The proof idea of Theorem 1, and specifically Lemma 2, is based on interactions the authors had with ChatGPT 5.5. While the authors take full responsibility for the contents of this work and the correctness of the proof, they acknowledge the significant impact the LLM had on this work.
11
References Alquier, P. (2021). User-friendly introduction to PAC-Bayes bounds. arXiv preprint arXiv:2110.11216. Audibert, J.-Y. (2007). Progressive mixture rules are deviation suboptimal. Advances in Neural Information Processing Systems (NeurIPS). Audibert, J.-Y. (2009). Fast learning rates in statistical inference through aggregation. Annals of Statistics. Catoni, O. (2004). Statistical learning theory and stochastic optimization: Ecole d’Eté de Probabilités de Saint-Flour XXXI-2001. Springer. Catoni, O. (2007). PAC-Bayesian supervised classification: The thermodynamics of statistical learning. Institute of Mathematical Statistics. Dai, D., Rigollet, P., and Zhang, T. (2012). Deviation optimal learning using greedy Q-aggregation. Annals of Statistics. Dalalyan, A. and Tsybakov, A. B. (2008). Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity. Machine Learning. Forster, J. and Warmuth, M. K. (2002). Relative expected instantaneous loss bounds. Journal of Computer and System Sciences. Hoeven, D., Erven, T., and Kotlowski, W. (2018). The many faces of exponential weights in online learning. Proceedings of the Conference on Learning Theory (COLT). Juditsky, A., Rigollet, P., and Tsybakov, A. B. (2008). Learning by mirror averaging. Annals of Statistics. Koren, T. and Levy, K. (2015). Fast rates for exp-concave empirical risk minimization. Advances in Neural Information Processing Systems (NeurIPS). Lecué, G. and Mendelson, S. (2009). Aggregation via empirical risk minimization. Probability theory and related fields. Lecué, G. and Mendelson, S. (2013). On the optimality of the aggregate with exponential weights for low temperatures. Bernoulli. Lecué, G. and Rigollet, P. (2014). Optimal learning with Q-aggregation. Annals of Statistics. Leung, G. and Barron, A. R. (2006). Information theory and mixing least-squares regressions. IEEE Transactions on Information Theory. Littlestone, N. and Warmuth, M. K. (1994). The weighted majority algorithm. Information and computation. Mourtada, J., Vaškevičius, T., and Zhivotovskiy, N. (2023). Local risk bounds for statistical aggregation. Proceedings of the Conference on Learning Theory (COLT). Rigollet, P. and Tsybakov, A. B. (2012). Sparse estimation by exponential weighting. Statistical Science. Tsybakov, A. B. (2003). Optimal rates of aggregation. Proceedings of the Conference on Learning Theory (COLT). Vovk, V. G. (1990). Aggregating strategies. Proceedings of the Conference on Learning Theory (COLT). Yang, Y. (2000). Mixing strategies for density estimation. Annals of Statistics.
12