July 02, 2026
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 [1]. 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 \((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é and Mendelson.
Let \((\mathcal{X},\Sigma)\) be some abstract measurable space, \(\mathcal{Y}\subset \mathbb{R}\) convex, and \(P\) be an arbitrary distribution on \((\mathcal{X}\times \mathcal{Y}, \Sigma \otimes \mathcal{B}(\mathcal{Y}))\). Denote \(\mathbf{S}=\left(X_i,Y_i \right)_{i=1}^n\) with \(n\in\mathbb{N}\) an i.i.d.sample from \(P\) and let \(\mathcal{F}=\left\{f_1,\ldots,f_M \right\}\) with \(M\in\mathbb{N}\) be an arbitrary but fixed finite dictionary of measurable functions \(f_k:\mathcal{X}\to\mathcal{Y}\). Given a loss function \(\ell:\mathcal{Y}^2\to[0,\infty)\) where \(\ell(\widehat{y},y)\) measures the loss of predicting \(\widehat{y}\) when the label is \(y\), the model selection aggregation problem is to learn a function \(f:\mathcal{X}\to \mathcal{Y}\) using the sample \(\mathbf{S}\) that achieves small risk \[\mathcal{R}_P(f):=\mathop{\mathrm{\mathbb{E}}}_{(X,Y)\sim P} \left[\ell(f(X),Y) \right]\] when compared to the best function in \(\mathcal{F}\), that is, to achieve small excess risk \(\mathcal{R}_P(f)-\min_{1\leq k \leq M} \mathcal{R}_P(f_k)\). In this paper, we consider loss functions that satisfy the following assumption:
Assumption 1. Let \(B,L,\mu>0\). The loss function \(\ell:\mathcal{Y}^2\to[0,\infty)\), satisfies that:
\(\ell\) is bounded by \(B\): for all \(\widehat{y},y\in\mathcal{Y}\), \(\ell(\widehat{y},y)\leq B\).
\(\ell(\cdot,y)\) is \(L\)-Lipschitz continuous for any \(y\in \mathcal{Y}\): for all \(y, \widehat{y}, \widehat{y}' \in \mathcal{Y}\), \(\left|\ell(\widehat{y},y)-\ell(\widehat{y}',y) \right| \leq L \left|\widehat{y}-\widehat{y}' \right|\).
\(\ell(\cdot,y)\) is \(\mu\)-strongly convex for any \(y\in \mathcal{Y}\): for all \(y\in \mathcal{Y}\), the map \(\widehat{y}\mapsto \ell(\widehat{y},y)-\frac{\mu}{2}\widehat{y}^2\) is convex on \(\mathcal{Y}\).
An important instance of such a loss function is the squared loss \(\ell(\widehat{y},y)=(\widehat{y}-y)^2\) on the label space \(\mathcal{Y}=[0,b]\), in which case 1 holds with \(B=b^2\), \(L=2b\) and \(\mu=2\).
Model selection aggregation is well-studied [2]–[5], and the minimax rate in expectation for squared loss was proven by [6] to be, up to constant factors independent of \(n\) and \(M\), \[\inf_{\widehat{f}} \sup_{P, \left|\mathcal{F} \right|=M} \left[\mathop{\mathrm{\mathbb{E}}}_{\mathbf{S}\sim P^n}\left[\mathcal{R}_P(\widehat{f}_{\mathbf{S}}) \right]-\min_{1\leq k \leq M} \mathcal{R}_P(f_k) \right] \asymp \min\left\{1,\frac{\log(M)}{n} \right\}.\] We refer to [7] 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 [8]–[10] and has been studied extensively over the years [7], [11]–[17]. Denoting the empirical risk with respect to the sample \(\mathbf{S}\) as \(\widehat{\mathcal{R}}_\mathbf{S}(f) = \frac{1}{n}\sum_{i=1}^n \ell(f(X_i),Y_i)\), the AEW is defined as \[\label{eqn:EW-definition} \widehat{f}_T = \sum_{k=1}^M \widehat{\theta}_k f_k \qquad \text{where} \qquad \widehat{\theta}_k = \frac{\exp\big(-\tfrac{n}{T}\widehat{\mathcal{R}}_\mathbf{S}(f_k)\big)}{\sum_{j=1}^M\exp\big(-\tfrac{n}{T}\widehat{\mathcal{R}}_\mathbf{S}(f_j)\big)} \qquad \text{for all }k\in \left\{1,\ldots,M \right\}.\tag{1}\] The AEW assigns a weight to each dictionary element which scales exponentially in the negative of the empirical risk \(\widehat{\mathcal{R}}_\mathbf{S}\) with respect to the sample \(\mathbf{S}\). Here \(T>0\) is a hyperparameter chosen by the estimator, 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 [12]. The larger the temperature, the more uniform the weights \(\widehat{\theta}_k\) 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 [1]; we restate them here for simplicity for squared loss on \([0,1]\). In short, it is known [2], [7], [12] that if the AEW estimator is averaged into the progressive mixture rule \(\smash{\widehat{f}_{\operatorname{pm}} = \frac{1}{n+1}\sum_{i=0}^n \widehat{f}_{T}^{(i)}}\), where each \(\widehat{f}_{T}^{(i)}\) 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, \(\mathop{\mathrm{\mathbb{E}}}[\mathcal{R}_P(\widehat{f}_{\operatorname{pm}})]\leq \min_{1\leq j\leq M} \mathcal{R}_P(f_j) + 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 [14], [18]. Finally, for random design, it has been shown that AEW can achieve the guarantee \(\mathop{\mathrm{\mathbb{E}}}[\mathcal{R}_P(\widehat{f}_T)]\leq \min_{1\leq j\leq M} \mathcal{R}_P(f_j) + 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 [1], [17], [19]. 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 [1] (again for squared loss for simplicity). For low temperatures \(T\leq c_1\), where \(c_1\) 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 \leq c_2 \sqrt{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 [15]. However, to the best of our knowledge, the optimality of exponential weights in expectation and under random design when \(T\geq c_3\) for some constant \(c_3\) has remained an open problem, posed explicitly by [1], 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 \(c_3>0\) such that for \(T\geq c_3\), the AEW estimator with temperature \(T\) achieves the optimal rate of aggregation \(\log(M)/n\) in expectation, uniformly over dictionaries \(\mathcal{F}\) of size \(M\) and arbitrary distributions \(P\) on \(\mathcal{X}\times [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 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).
Theorem 1 (Minimax-rate optimality of AEW in expectation). Let the loss \(\ell\) satisfy 1 with parameters \(B,L\) and \(\mu\). For every \(M,n\in\mathbb{N}\), temperature \(T\in(0,\infty)\) satisfying \((L^2/T)\exp(B/T)\leq \mu/2\), dictionary \(\mathcal{F}=\left\{f_1,\ldots,f_M \right\}\) of measurable functions \(f_k:\mathcal{X}\to \mathcal{Y}\), and distribution \(P\) on \(\mathcal{X}\times \mathcal{Y}\), the aggregation with exponential weights estimator 1 satisfies \[\mathop{\mathrm{\mathbb{E}}}_{\mathbf{S}\sim P^n} \left[\mathcal{R}_P(\widehat{f}_T) \right] \leq \min_{1\leq k \leq M} \mathcal{R}_P(f_k) +\frac{T\log M}{n+1}.\] For squared loss on \(\mathcal{Y}=[0,b]\), the condition \((L^2/T)\exp(B/T)\leq \mu/2\) can be replaced by \(T\in[4b^2,\infty)\).
Remark 1. For squared loss on \([0,b]\), the parameters from 1 are given by \(B=b^2\), \(L=2b\) and \(\mu =2\), and so the first condition of 1 yields \(T\geq b^2/W(1/4) \approx 4.904 b^2\) 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 \(4b^2\). In particular, for squared loss on \([0,1]\), choosing \(T=4\) yields the excess risk \(4\log(M)/(n+1)\).
Note that in 1 no Bernstein condition is assumed. This resolves the open question from above.
None
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..
We now complement the positive result of 1 by showing that if the temperature grows unboundedly with \(n\) (i.e., \(T\to \infty\) as \(n\to \infty\)) then AEW is suboptimal in expectation. See also 1. In contrast to 1, the following propositions are somewhat straightforward to prove.
Proposition 1. Let \(\ell\) be the squared loss and \(\mathcal{Y}=[0,1]\). For every \(T>0\), \(n\in\mathbb{N}\), and \(M\in\mathbb{N}\) with \(M\geq 2\), there exists a dictionary \(\mathcal{F}\) of size \(M\), a distribution \(P\) on \(\mathcal{X}\times [0,1]\), and a \(\gamma_M\in[1/4,1]\) depending only on \(M\), such that AEW with any temperature \(T\) has excess risk lower bounded almost surely as \[\mathop{\mathrm{\mathbb{P}}}_{\mathbf{S}\sim P^n}\left(\mathcal{R}_P(\widehat{f}_{T})\geq \min_{1\leq j\leq M} \mathcal{R}_P(f_j)+ \gamma_M\min\left\{1,\frac{T\log(M-1)}{n} \right\} \right)=1.\] Moreover, it holds that \(\gamma_M\to 1\) as \(M\to \infty\). Now let \(T_{n,M}\) be any schedule of temperatures depending on \(n\) and \(M\). Then, if for any sequence \(M_n\geq 3\) it holds that \(\log(M_n)/n\to 0\) and \(T_{n,M_n} \to \infty\) as \(n\to \infty\), AEW with this schedule is minimax-rate suboptimal (in expectation). Whenever \(T_{n,M}\) is independent of \(M\) and \(T_{n,M}=T_{n}\to \infty\) as \(n\to\infty\), such a sequence can be chosen so that the lower bound converges to \(1\).
Along any sequence \(M_n\) with \(\log(M_n)/n\to 0\) and \(T_{n,M_n}\to \infty\), the ratio between the lower bound in 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 \(\gamma_M\to 1\) as \(M\to \infty\) implies that for large \(n\) and \(M\), our lower bound from 1 and the upper bound from 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\geq 4\). For \(T\leq c_1\), the lower bound in 1 is necessarily not tight in first order, due to the stronger lower bound by [1].
By a similar argument, we now complement the lower bound in probability from [1] for \(T\leq c_2\sqrt{n}/\log(n)\) by showing that, unsurprisingly, choosing \(T\) larger does not help in general.
Proposition 2. Let \(\ell\) be the squared loss and \(\mathcal{Y}=[0,1]\). For every \(n\ge 2\) and every \(T\ge c_{2}\sqrt{n}/\log (n)\) (where \(c_{2}\) is the universal constant from [1]), there exist \(M\le n^{1/c_{2}}+2\), a dictionary \(\mathcal{F}=\{f_1,\dots,f_M\}\) with values in \([0,1]\), and a distribution \(P\) on \(\mathcal{X}\times[0,1]\) such that \[\mathop{\mathrm{\mathbb{P}}}_{\mathbf{S}\sim P^n}\left(\mathcal{R}_P(\widehat{f}_T)\geq \min_{1\le j\le M}\mathcal{R}_P(f_j) + \frac{1}{4\sqrt n} \right)=1.\]
Notice that since \(M\leq n^{1/c_2}+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 \lesssim \log(n)/n \ll 1/\sqrt{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 1. Indeed, the AEW is always suboptimal in probability, and for temperatures below some constant \(c_1\) 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 1 in 2 and then 1 2 in [proof:EW-suboptimal-growing-temperature] [proof:EW-suboptimal-super-high-temperatures].
The proof of 1 reduces to a deterministic leave-one-out bound that uses ideas of algorithmic stability. Recall that the loss \(\ell\) satisfies 1 with parameters \(B,L,\mu\).
Let \(N=n+1\geq 2\) and \(\left(x_i,y_i \right)_{i=1}^N\subset \mathcal{X}\times \mathcal{Y}\) be an arbitrary fixed deterministic sample. Denote \(\ell_{ij}=\ell(f_j(x_i),y_i)\), the loss of the \(i\)-th observation for function \(f_j\), and \(S_j = \sum_{i=1}^N \ell_{ij}\), the total loss for function \(f_j\). We now let \(p_1^{(-i)},\ldots,p_M^{(-i)}\) be the exponential weights formed on the sub-sample of size \(n\) after removing the \(i\)th observation and with temperature \(T\), that is, for each \(j\in[M]\) \[p_j^{(-i)} = \frac{\exp\left(-(S_j-\ell_{ij})/T \right)}{\sum_{k=1}^M \exp\left(-(S_k-\ell_{ik})/T \right)} = \frac{p_j \exp\left(\ell_{ij}/T \right)}{\sum_{k=1}^M p_k \exp\left(\ell_{ik}/T \right)} \quad \text{where} \quad p_j = \frac{\exp\left(-S_j/T \right)}{\sum_{k=1}^M \exp\left(-S_k/T \right)}.\]
Proposition 3 (A deterministic leave-one-out inequality). In the setting described above, if the loss satisfies 1 with parameters \(B,L,\mu\), and \(T\) satisfies \((L^2/T)\exp(B/T)\leq \mu/2\), it holds that \[\label{eqn:leave-one-out} \frac{1}{N} \sum_{i=1}^N \ell\left(\sum_{j=1}^M p_j^{(-i)}f_j(x_i),y_i \right) \leq \min_{1\leq j\leq M} \frac{1}{N}\sum_{i=1}^N\ell\left(f_j(x_i),y_i \right) + \frac{T\log M}{N},\qquad{(1)}\] where \(\sum_{j=1}^M p_j^{(-i)}f_j\) is the AEW estimator on the sample with the \(i\)-th observation removed. For squared loss on \(\mathcal{Y}=[0,b]\), the condition \((L^2/T)\exp(B/T)\leq \mu/2\) can be replaced by \(T\in[4b^2,\infty)\).
Before proving 3, we show how it implies 1. Let \(\mathbf{S}'=\left(X_i,Y_i \right)_{i=1}^N\) be an i.i.d.sample from \(P\). For each \(i\), we can compute the exponential weights estimator on the sample with \((X_i,Y_i)\) removed; let \(\widehat{f}_T^{(-i)}\) denote the estimator with the \(i\)’th observation removed and \(\widehat{\theta}^{(-i)}_j\) its weight on \(f_j\). By exchangeability and independence of the data points, we can rewrite the risk of \(\widehat{f}_T=\widehat{f}_T^{(-N)}\) as \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{\mathbf{S}\sim P^n}\left[\mathcal{R}_P(\widehat{f}_T) \right]&=\mathop{\mathrm{\mathbb{E}}}_{\mathbf{S}'\sim P^N}\left[\ell(\widehat{f}_T^{(-N)}(X_N),Y_N) \right] \\ &= \mathop{\mathrm{\mathbb{E}}}_{\mathbf{S}'\sim P^N}\left[\ell(\widehat{f}_T^{(-i)}(X_i),Y_i) \right]\\ &= \mathop{\mathrm{\mathbb{E}}}_{\mathbf{S}'\sim P^N}\left[\frac{1}{N}\sum_{i=1}^N\ell(\widehat{f}_T^{(-i)}(X_i),Y_i) \right] \\ &= \mathop{\mathrm{\mathbb{E}}}_{\mathbf{S}'\sim P^N}\left[\frac{1}{N}\sum_{i=1}^N\ell\left(\sum_{j=1}^M \widehat{\theta}_j^{(-i)}f_j(X_i),Y_i \right) \right]. \end{align}\] We can now apply 3 with the sample \((X_i,Y_i)_{i=1}^N\) and \(p_j^{(-i)}=\widehat{\theta}_j^{(-i)}\). By ?? , we observe that, as long as \((L^2/T)\exp(B/T)\leq \mu/2\), or \(T\geq 4b^2\) for squared loss, the right-hand side is bounded above by \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{\mathbf{S}\sim P^n}\left[\mathcal{R}_P(\widehat{f}_T) \right] &\leq \mathop{\mathrm{\mathbb{E}}}_{\mathbf{S}'\sim P^N}\left[ \min_{1\leq j\leq M} \frac{1}{N}\sum_{i=1}^N \ell(f_j(X_i),Y_i) + \frac{T\log M}{N} \right] \\ &\leq \min_{1\leq j\leq M} \frac{1}{N}\sum_{i=1}^N \mathop{\mathrm{\mathbb{E}}}_{(X_i,Y_i)\sim P}\left[\ell(f_j(X_i),Y_i) \right] + \frac{T\log M}{N} \\ &= \min_{1\leq j\leq M} \mathcal{R}_P(f_j) + \frac{T \log M}{n+1}, \end{align}\] which concludes the proof of 1. It remains to prove 3.
Recall the notation \(\ell_{ij}=\ell(f_j(x_i), y_i)\) and \(S_j = \sum_{i=1}^N \ell_{ij}\). In the first step, we apply the following lemmas. Here we make the case distinction between general losses satisfying 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 1 holds. Let \(M\in\mathbb{N}\), \((p_1,\ldots,p_M)\) be a probability distribution, and \(y,\widehat{y}_1,\ldots \widehat{y}_M\in\mathcal{Y}\) be any fixed values. Define the tilted probability distribution \((q_1,\ldots,q_M)\) as \[q_j = \frac{p_j \exp(\tfrac{1}{T} \ell(\widehat{y}_j,y))}{\sum_{k=1}^M p_k \exp(\tfrac{1}{T} \ell(\widehat{y}_k,y))}.\] If \(T>0\) satisfies \((L^2/T)\exp(B/T)\leq \mu/2\), then it holds that \[\label{eqn:tilt-inequality-general} \ell\left(\sum_{j=1}^{M}q_{j}\widehat{y}_j,y \right) \leq \sum_{j=1}^{M}p_{j}\ell(\widehat{y}_j,y).\tag{2}\]
The proof of 1 is in 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 2 is in 2.3.
Lemma 2 (A tilting inequality for squared loss). Let \(M\in\mathbb{N}\), \(b>0\), and \((p_1,\ldots,p_M)\) be a probability distribution, and \(y,\widehat{y}_1,\ldots,\widehat{y}_M\in[0,b]\) be any fixed values. Define the tilted probability distribution \((q_1,\ldots,q_M)\) as \[q_j = \frac{p_j \exp(\tfrac{1}{T} (\widehat{y}_j-y)^2)}{\sum_{k=1}^M p_k \exp(\tfrac{1}{T} (\widehat{y}_k-y)^2)}.\] If \(T\in[4b^2,\infty)\), then the following inequality is true: \[\label{eqn:squared-tilt-inequality} \left(\sum_{j=1}^M q_j \widehat{y}_j-y \right)^2 \leq \sum_{j=1}^M p_j (\widehat{y}_j-y)^2.\tag{3}\]
We use 1 2 with \(\widehat{y}_j=f_j(x_i),y=y_i\) by recalling that the weights of the exponential weights estimator with the \(i\)th datapoint removed are given by \[p_j^{(-i)} = \frac{\exp\left(-(S_j-\ell_{ij})/T \right)}{\sum_{k=1}^M \exp\left(-(S_k-\ell_{ik})/T \right)} = \frac{p_j \exp\left( \ell_{ij}/T \right)}{\sum_{k=1}^M p_k \exp\left( \ell_{ik}/T \right)} = \frac{p_j \exp\left(\ell(f_j(x_i),y_i)/T \right)}{\sum_{k=1}^M p_k \exp\left(\ell(f_k(x_i),y_i)/T \right)},\] where in turn \(p_j\) 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 1 2 that \[\begin{align} \ell\left(\sum_{j=1}^M p_j^{(-i)}f_j(x_i),y_i \right) \leq \sum_{j=1}^M p_j\ell(f_j(x_i),y_i) = \sum_{j=1}^M p_j\ell_{ij}. \end{align}\] We can sum this inequality over samples \(i\) and obtain that \[\sum_{i=1}^N \ell\left(\sum_{j=1}^M p_j^{(-i)}f_j(x_i),y_i \right) \leq \sum_{j=1}^M p_j \sum_{i=1}^N\ell_{ij} = \sum_{j=1}^M p_j S_j.\] 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 2.4) it for completeness.
Lemma 3 (An elementary variational inequality for exponential weights). Let \(M\in\mathbb{N}\), let \(S_1,\ldots, S_M\in \mathbb{R}\) be real numbers, let \(T>0\) and define \(p_j = \frac{\exp\left(-S_j/T \right)}{\sum_{k=1}^M \exp\left(-S_k/T \right)}\) for \(j=1,\ldots, M\). Then it holds that \[\sum_{j=1}^M p_j S_j \leq \min_{1\leq j \leq M} S_j + T\log M.\]
Applying 3, to the last display and dividing by \(N\) yields 3.
To start, we rederive the following well-known fact: due to the strong convexity from 1 and convexity of \(\mathcal{Y}\), it holds that \[\begin{align} \ell\left(\sum_{j=1}^M p_j \widehat{y}_j,y \right) &= \left[\ell\left(\sum_{j=1}^M p_j \widehat{y}_j,y \right) -\frac{\mu}{2}\left(\sum_{j=1}^M p_j \widehat{y}_j \right)^2 \right] +\frac{\mu}{2}\left(\sum_{j=1}^M p_j \widehat{y}_j \right)^2 \nonumber \\ &\leq \sum_{j=1}^M p_j \left[\ell(\widehat{y}_j,y)-\frac{\mu}{2}\widehat{y}_j^2 \right] +\frac{\mu}{2}\left(\sum_{j=1}^M p_j \widehat{y}_j \right)^2 \\ &= \sum_{j=1}^M p_j \ell(\widehat{y}_j,y) -\frac{\mu}{2} \left[ \sum_{j=1}^M p_j \widehat{y}_j^2 - \left(\sum_{j=1}^M p_j \widehat{y}_j \right)^2 \right] \nonumber \\ &= \sum_{j=1}^M p_j \ell(\widehat{y}_j,y)-\frac{\mu}{2} \sum_{j=1}^M p_j \left(\widehat{y}_j-\sum_{k=1}^M p_k\widehat{y}_k \right)^2. \label{eqn:Jensen-gap-strong-convexity} \end{align}\tag{4}\] Here the last step uses the fact that for any real-valued random variable \(X\), it holds \(\mathop{\mathrm{\mathbb{E}}}[(X-\mathop{\mathrm{\mathbb{E}}}[X])^2]=\mathop{\mathrm{\mathbb{E}}}[X^2]-(\mathop{\mathrm{\mathbb{E}}}[X])^2\). See also [5] for an analogous statement.
We can then apply Lipschitz continuity and strong convexity (through 4 ) from 1 as follows: \[\begin{align} \ell\left(\sum_{j=1}^{M}q_{j}\widehat{y}_j,y \right) &=\ell\left(\sum_{j=1}^{M}q_{j}\widehat{y}_j,y \right) -\ell\left(\sum_{j=1}^{M}p_{j}\widehat{y}_j,y \right) +\ell\left(\sum_{j=1}^{M}p_{j}\widehat{y}_j,y \right) \nonumber \\ &\leq L\left|\sum_{j=1}^{M}q_{j}\widehat{y}_j-\sum_{j=1}^{M}p_{j}\widehat{y}_j \right| +\sum_{j=1}^{M}p_{j}\ell(\widehat{y}_j,y)-\frac{\mu}{2}\sum_{j=1}^{M}p_{j}\left(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k \right)^{2} } \nonumber \\ &= L\left|\sum_{j=1}^{M}q_{j}\left(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k\right) \right| +\sum_{j=1}^{M}p_{j}\ell(\widehat{y}_j,y)-\frac{\mu}{2}\sum_{j=1}^{M}p_{j}\left(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k \right)^{2}. \label{eqn:loss-decomposition} \end{align}\tag{5}\] Let now \(Z= \sum_{j=1}^{M} p_{j}\exp{(\frac{1}{T}\ell(\widehat{y}_j,y)) }\) be the normalization constant of the distribution \((q_1,\ldots,q_M)\). To bound the first term in 5 , we can use \[\begin{align} \label{eqn:meanvaluetheorystep} \sum_{j=1}^{M}q_{j}\left(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k\right) &=\sum_{j=1}^{M}\frac{ \exp{(\frac{1}{T}\ell(\widehat{y}_j,y)) } }{Z}p_{j}\left(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k\right)\nonumber \\ &=\frac{1}{Z}\sum_{j=1}^{M}p_{j}\left[\exp\left(\frac{1}{T}\ell(\widehat{y}_j,y) \right)-\exp\left(\frac{1}{T}\ell\left(\sum_{k=1}^{M}p_{k}\widehat{y}_k,y \right) \right) \right]\left(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k\right) \end{align}\tag{6}\] where the last equality follows by \(\sum_{j=1}^{M} c p_{j}(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k)=0\) for any \(c\in \mathbb{R}\), especially for \(c=\exp{(\frac{1}{T}\ell(\sum_{k=1}^{M}p_{k}\widehat{y}_k,y)) }\). Taking the absolute value on both sides and using the triangle inequality, we obtain that the first term of 5 is bounded by \[\begin{align} \left|\sum_{j=1}^{M}q_{j}\left(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k\right) \right| \leq\sum_{j=1}^{M}\frac{p_{j}}{Z}\left|\exp\left(\frac{1}{T}\ell(\widehat{y}_j,y) \right)-\exp\left(\frac{1}{T}\ell\left(\sum_{k=1}^{M}p_{k}\widehat{y}_k,y \right) \right) \right|\left|\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k \right|. \end{align}\] One can verify that the Mean Value Theorem implies the inequality \[\forall a,b\in \mathbb{R}, \forall T>0:\qquad \left|\exp\left(\frac{a}{T} \right)-\exp\left(\frac{b}{T} \right) \right|=\left|\int_b^a\frac{1}{T}\exp\left(\frac{x}{T} \right)dx \right|\leq \frac{1}{T} \exp\left(\frac{\max\left\{a,b \right\}}{T} \right) |a-b|.\] Applying this to 6 , we further obtain using \(B\)-boundedness of the loss that \[\begin{align} &\left|\sum_{j=1}^{M}q_{j}\left(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k\right) \right|\\ &\leq \sum_{j=1}^{M}\frac{p_{j}}{TZ} \exp\left(\frac{1}{T}\max\left\{\ell(\widehat{y}_j,y),\ell\left(\sum_{k=1}^{M}p_{k}\widehat{y}_k,y \right) \right\} \right) \cdot\left|\ell(\widehat{y}_j,y)-\ell\left(\sum_{k=1}^{M}p_{k}\widehat{y}_k,y \right) \right|\cdot\left|\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k \right| \\ &\leq \frac{L}{T} \exp\left(\frac{B}{T} \right) \sum_{j=1}^{M}\frac{p_{j}}{Z} \left(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k \right)^{2}\\ &\leq \frac{L}{T} \exp\left(\frac{B}{T} \right) \sum_{j=1}^{M} p_{j} \left(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k \right)^{2} \end{align}\] where the last inequality holds because \(Z=\sum_{j=1}^{M} \exp{(\frac{1}{T}\ell(\widehat{y}_j,y)) } p_{j} \geq \sum_{j=1}^M p_j= 1\). Thus, plugging this bound into the display 5 , we obtain that \[\begin{align} \ell\left(\sum_{j=1}^{M}q_{j}\widehat{y}_j,y \right) &\leq L\left|\sum_{j=1}^{M}q_{j}\left(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k\right) \right| +\sum_{j=1}^{M}p_{j}\ell(\widehat{y}_j,y)-\frac{\mu}{2}\sum_{j=1}^{M}p_{j}\left(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k \right)^{2} \\ &\leq \left(\frac{L^{2}}{T}\exp\left(\frac{B}{T} \right) -\frac{\mu}{2} \right) \sum_{j=1}^{M} p_{j} \left(\widehat{y}_j-\sum_{k=1}^{M}p_{k}\widehat{y}_k \right)^{2} +\sum_{j=1}^{M}p_{j}\ell(\widehat{y}_j,y) \end{align}\] where the condition on \(T\) implies \(\frac{L^{2}}{T}\exp{(\frac{B}{T})} -\frac{\mu}{2} \leq 0\), so the last display in the above is bounded by the last term, which concludes the proof of 1.
Let \(U\) be a random variable that takes the value \(u_j:= \widehat{y}_j-y \in[-b,b]\) with probability \(p_j\) and denote \(V=\left|U \right|\) and \(r=(\mathop{\mathrm{\mathbb{E}}}V^2)^{1/2}\), both taking values in \([0,b]\). If \(r=0\), then since \(V^2=U^2\geq 0\) is a non-negative random variable we know that \(U=0\) \(p\)-almost surely, that is, \(p_j u_j = 0\) for all \(j\in [M]\). Therefore, we have that \[\sum_{j=1}^M q_j u_j = \sum_{j=1}^M \frac{u_j p_j \exp\left(u_j^2/T \right)}{\sum_{k=1}^M p_k \exp\left(u_k^2/T \right)} = 0,\] and so the left hand side of 3 vanishes. As the right hand side is always non-negative, 3 follows.
Assume now that \(r>0\). Define the function \(\phi:[0,b]\to \mathbb{R}\) as \(\phi(v) = \exp\left(v^2/T \right)/(v+r)\). A calculation using the quotient rule yields that its derivative is given by \[\phi'(v) = \frac{(2v \exp\left(v^2/T \right)(v+r)/T-\exp\left(v^2/T \right))}{(v+r)^2} = \frac{\exp\left(v^2/T \right)}{(v+r)^2}\left(2v(v+r)/T-1 \right).\] Since the first factor of the latter display is always positive, the sign of \(\phi'\) is determined by the sign of \(2v(v+r)/T-1\), and since \(v,r\in [0,b]\), we know that \(2v(v+r)/T\leq 4b^2/T \leq 1\) where we used the assumption that \(T \geq 4b^2\). Therefore, on \([0,b]\) we have \(\phi'\leq 0\) and \(\phi\) is non-increasing.
By making a case distinction between \(v\geq r\) and \(v<r\), we can show that this monotonicity implies \[\label{eqn:tilted-intermediate-1} (v-r)\exp\left( v^2/T \right) \leq \phi(r)(v^2-r^2).\tag{7}\] Case \(v\ge r\): In this case, because \(\phi(v)\leq \phi(r)\) and \(v^2-r^2\ge 0\), we know that \((v^2-r^2) \phi(v)\leq (v^2-r^2) \phi(r)\), and so \[(v-r)\exp\left( v^2/T \right) = (v-r)(v+r)\phi(v) = (v^2-r^2) \phi(v)\leq (v^2-r^2) \phi(r).\] Case \(v<r\): In this case, because \(\phi(v)\geq \phi(r)\) and \(v^2-r^2<0\), we know that \((v^2-r^2) \phi(v)\leq (v^2-r^2) \phi(r)\), and so by the same calculation, we have that \((v-r)\exp\left( v^2/T \right)\leq (v^2-r^2) \phi(r)\).
By taking expectation over \(V\) in 7 we obtain that \[\mathop{\mathrm{\mathbb{E}}}\left[(V-r)\exp\left( V^2/T \right) \right] \leq \phi(r) \left(\mathop{\mathrm{\mathbb{E}}}V^2-r^2 \right) = 0\] where the equality follows by definition of \(r=(\mathop{\mathrm{\mathbb{E}}}V^2)^{1/2}\). This implies \(\mathop{\mathrm{\mathbb{E}}}\left[V \exp\left( V^2/T \right) \right]\leq r \mathop{\mathrm{\mathbb{E}}}\left[\exp\left( V^2/T \right) \right]\), whereby we get \[\begin{align} \left|\sum_{j=1}^M q_j u_j \right| = \left|\sum_{j=1}^M \frac{u_j p_j \exp\left( u_j^2/T \right)}{\sum_{k=1}^M p_k \exp\left( u_k^2/T \right)} \right| &= \left|\frac{\mathop{\mathrm{\mathbb{E}}}\left[U \exp\left( U^2/T \right) \right]}{\mathop{\mathrm{\mathbb{E}}}\left[\exp\left( U^2/T \right) \right]} \right| \\ &\leq \frac{\mathop{\mathrm{\mathbb{E}}}\left[\left|U \right| \exp\left( U^2/T \right) \right]}{\mathop{\mathrm{\mathbb{E}}}\left[\exp\left( U^2/T \right) \right]} = \frac{\mathop{\mathrm{\mathbb{E}}}\left[V \exp\left( V^2/T \right) \right]}{\mathop{\mathrm{\mathbb{E}}}\left[\exp\left( V^2/T \right) \right]}\leq r. \end{align}\] Squaring both sides and expanding the definition of \(r^2\) we get that \[\left(\sum_{j=1}^M q_j u_j \right)^2 \leq r^2 = \mathop{\mathrm{\mathbb{E}}}V^2 = \sum_{j=1}^M p_j u_j^2.\] This concludes the proof of 2 by plugging back in \(u_j=\widehat{y}_j-y\).
Recall that for all \(j\in[M]\), we defined \(p_j = \frac{\exp\left(-S_j/T \right)}{\sum_{k=1}^M \exp\left(-S_k/T \right)}\). Since \(p_j>0\), we can take the logarithm and obtain \[\log p_j = -\frac{S_j}{T} -\log \left(\sum_{k=1}^M \exp\left(-S_k/T \right) \right).\] We can multiply each side by \(p_j\) and sum over \(j\in[M]\) to obtain that \[\sum_{j=1}^M p_j \log p_j = -\frac{1}{T}\sum_{j=1}^M p_j S_j - \log \left(\sum_{k=1}^M \exp\left(-S_k/T \right) \right),\] where the last term remains unchanged because it is independent of \(j\) and \(\sum_{j=1}^M p_j =1\). Multiplying by \(T\) and rearranging this, we obtain that \[\begin{align} \sum_{j=1}^M p_j S_j &= -T \sum_{j=1}^M p_j \log p_j- T \log \left(\sum_{k=1}^M \exp\left(-S_k/T \right) \right) \\ &\leq T \log M -T \log \left(\exp\left(-\min_{1\leq k \leq M} S_k/T \right) \right)\\ &= T \log M + \min_{1\leq j \leq M } S_j, \end{align}\] where the first inequality follows because \(0\leq -\sum_{j=1}^M p_j\log p_j\leq \log M\) (as it is the entropy of a probability distribution on \(M\) points), and the second holds because \(\sum_{k=1}^M \exp\left(-S_k/T \right) \geq \exp\left(-\min_{1\leq k \leq M} S_k/T \right)\). That concludes the proof of 3.
To prove 1, we construct a dictionary and a distribution. Fix \(n\in\mathbb{N}\) and \(M\in\mathbb{N}\) with \(M\geq 2\). If \(M=2\), then the lower bound is trivially true as \(\log(M-1)=0\), so assume without loss of generality that \(M\geq 3\), so that \(\log(M-1)>0\). Define for some \(\alpha\in(0,1]\) to be chosen later \[a^2 = \alpha r \qquad \text{where} \qquad r= \min\left\{1,\frac{T\log(M-1)}{n} \right\}.\] Let the distribution \(P\) of \((X,Y)\) be such that \(Y= 0\) almost surely, and choose the dictionary \(f_1\equiv 0\), as well as \(f_2=\cdots=f_M\equiv a\). Thus \(f_1\) is the optimal dictionary element, whereas all others are suboptimal. For every sample \(\mathbf{S}\), almost surely, we have that \[\widehat{\mathcal{R}}_\mathbf{S}(f_1)=0, \qquad \widehat{\mathcal{R}}_\mathbf{S}(f_j)=a^2 \quad \text{for } j\ge2.\] Hence the total mass put on the suboptimal functions with index \(j\geq 2\) is \[1-\widehat{\theta}_1 = \sum_{j=2}^M \frac{\exp\left(-na^2/T \right)}{1+\sum_{k=2}^M \exp\left(-na^2/T \right)} = \frac{(M-1)\exp\left(-na^2/T \right)}{1+(M-1)\exp\left(-na^2/T \right)}.\] Because \(r \leq T\log (M-1)/n\) by definition of \(r\), we get that \(na^2/T = \alpha nr/T\leq \alpha \log(M-1)\). Therefore, we obtain that \((M-1)\exp(-na^2/T) \geq (M-1)^{1-\alpha}\) and so \[1-\widehat{\theta}_1 \geq \frac{(M-1)^{1-\alpha}}{1+(M-1)^{1-\alpha}}.\] Notice that because the AEW estimator on this dictionary is \(\widehat{f}_{T} \equiv a(1-\widehat{\theta}_1)\), and because \(f_1\) has risk zero, this means it has \(P^n\)-almost surely an excess risk of at least \[\mathcal{R}_P(\widehat{f}_T)- \min_{1\leq j \leq M} \mathcal{R}_P(f_j) \geq a^2(1-\widehat{\theta}_1)^2 \geq \alpha \left(\frac{(M-1)^{1-\alpha}}{1+(M-1)^{1-\alpha}} \right)^2 r.\] Since this lower bound is true for every \(\alpha\in(0,1]\), we can define \[\gamma_M =\sup_{\alpha\in (0,1]} \alpha \left(\frac{(M-1)^{1-\alpha}}{1+(M-1)^{1-\alpha}} \right)^2\] and the excess risk is lower bounded by \(\gamma_M r\) for the \(\alpha\in(0,1]\) attaining the maximum (which exists). Notice that \(\gamma_M\in [1/4,1]\) since for \(\alpha=1\) the term is \(1/4\), so \(\gamma_M\) must be larger, and \(\gamma_M\leq 1\), follows from \(\alpha\leq 1\) and \(((M-1)^{1-\alpha}/(1+(M-1)^{1-\alpha})\leq 1\). We now show that \(\gamma_M\to 1\) as \(M\to \infty\). To that end, denote the function to be optimized as \(h_M(\alpha) = \alpha ((M-1)^{1-\alpha}/(1+(M-1)^{1-\alpha}))^2\). To prove the limit, consider the sequence \(\alpha_M\) defined as \(\alpha_M = 1-1/\sqrt{\log(M-1)}\). Then we get that \((M-1)^{1-\alpha_M} =\exp\left(\sqrt{\log(M-1)} \right)\) and so \[h_{M}(\alpha_M)= \left(1-\frac{1}{\sqrt{\log(M-1)}} \right)\left(\frac{\exp\left(\sqrt{\log(M-1)} \right)}{1+\exp\left(\sqrt{\log(M-1)} \right)} \right)^2 \to 1 \quad \text{as } M\to\infty.\] By definition, we then have that \(\gamma_M \geq h_M(\alpha_M) \to 1\) and \(\gamma_M\leq 1\), implying that \(\gamma_M\to 1\) as \(M\to \infty\). Plugging in the definition of \(r\) yields the proof of the first two claims in 1.
Now, let \(M_n\ge3\) be such that \(\log(M_n)/n\to0\) and \(T_{n,M_n}\to\infty\). By the first part, for each \(n\) there is a distribution and dictionary for which \[\mathcal{R}_P(\widehat f_{T_{n,M_n}})-\min_{1\leq j\leq M} \mathcal{R}_P(f_j) \ge \gamma_{M_n}\min\left\{1,\frac{T_{n,M_n}\log(M_n-1)}{n} \right\}.\] Since \(M_n\ge3\), there exists a universal constant \(c>0\) such that \(\log(M_n-1)\ge c\log M_n\). Therefore \[\frac{\mathcal{R}_P(\widehat f_{T_{n,M_n}})-\min_{1\leq j \leq M} \mathcal{R}_P(f_j)}{\log(M_n)/n} \geq \frac{1}{4} \min\left\{\frac{n}{\log M_n}, c T_{n,M_n} \right\}\to\infty \quad \text{as } n\to \infty.\] Thus, the excess risk is of order larger than \(\log(M_n)/n\), and hence suboptimal.
It remains to show that whenever \(T_{n,M}\) is independent of \(M\) and \(T_{n,M}=T_{n}\to \infty\) as \(n\to\infty\), there exists a sequence \(M_n\to \infty\) such that \(\log (M_n) / n\to 0\) but \(r=1\) for all \(n\). By the first part, that then yields the lower bound \(\gamma_{M_n}\) converging to \(1\) because \(M_n\to \infty\). To that end, consider the sequence \(M_n = \left\lceil \exp(\max\left\{n/T_n,\sqrt{n} \right\}) \right\rceil+1 \leq 3\exp(\max\left\{n/T_n,\sqrt{n} \right\})\). Then \[\frac{\log(M_n)}{n} \leq \max\left\{\frac{1}{T_n},\frac{1}{\sqrt{n}} \right\} + \frac{\log 3}{n} \to 0 \quad \text{as } n\to \infty,\] and at the same time, \(r=1\) because the other term in the minimum of the definition of \(r\) is lower bounded by \[\frac{T_n \log(M_n-1)}{n} \geq \frac{T_n \log(\left\lceil \exp(\max\left\{n/T_n,\sqrt{n} \right\}) \right\rceil)}{n} \geq \frac{T_n(n/T_n)}{n} =1.\] That concludes the proof of 1.
To prove 2, we construct a dictionary and a distribution. We proceed almost identically to 3.1. Let the distribution \(P\) of \((X,Y)\) be such that \(Y= 0\) almost surely, and choose the dictionary \(f_1\equiv 0\), as well as \(f_2=\cdots=f_M\equiv a\), where we choose \(a>0\) as \(a^2=n^{-1/2}\). Moreover, we choose the number of dictionary elements \(M\) to satisfy \[M-1=\left\lceil \exp\left(\sqrt n/T \right) \right\rceil.\] The assumption on \(T\) that \(T\geq c_2\sqrt{n}/\log(n)\) gives \[M=\left\lceil \exp\left(\sqrt n/T \right) \right\rceil+1\leq \left\lceil \exp\left(\log(n)/c_2 \right) \right\rceil+1 \le n^{1/c_{2}}+2,\] confirming that the dictionary is not too large. For every sample \(\mathbf{S}\), we have by construction that \(P\)-almost surely, \[\widehat{\mathcal{R}}_\mathbf{S}(f_1)=0, \qquad \widehat{\mathcal{R}}_\mathbf{S}(f_j)=a^2 \quad \text{for } j\ge2.\] Hence the total mass put on the suboptimal functions with index \(j\geq 2\) is \[1-\widehat{\theta}_1 = \sum_{j=2}^M \frac{\exp\left(-na^2/T \right)}{1+\sum_{k=2}^M \exp\left(-na^2/T \right)} = \frac{(M-1)\exp\left(-na^2/T \right)}{1+(M-1)\exp\left(-na^2/T \right)} = \frac{(M-1)\exp\left(-\sqrt n/T \right)}{1+(M-1)\exp\left(-\sqrt n/T \right)} \ge \frac{1}{2}\] where the last inequality follows from \(M-1\geq \exp\left(\sqrt{n}/T \right)\) implying \((M-1)\exp\left(-\sqrt n/T \right)\geq 1\). Therefore, by noticing that \(\widehat{f}_T\equiv (1-\widehat{\theta}_1)a\), and since \(f_1\) has risk zero, \[\mathcal{R}_P(\widehat{f}_T)-\min_{1\leq j\leq M}\mathcal{R}_P(f_j)=((1-\widehat{\theta}_1)a)^2 \ge \frac{1}{4} n^{-1/2}.\] The above holds almost surely, so the event has probability one. That concludes the proof.
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 (3). The reduction to such a leave-one-out bound is similar in spirit to existing bounds, see for instance [20], [21]. However, the main difference and novelty of our approach is in the proof of that stability result, specifically in 1 2, which explicitly makes use of the tilting of the exponential weights distribution when one sample is left out. 1 2 seem to be novel, and they may also be of independent interest.
We would like to remark that the tightness of 1 2 is crucial. Indeed, a weaker version of 1 2 can be obtained via an application of Jensen’s inequality. In the notation of 1, \[\ell\left(\sum_{j=1}^M q_j \widehat{y}_j,y \right)\leq \sum_{j=1}^M q_j \ell(\widehat{y}_j,y) = \sum_{j=1}^M \frac{p_j \exp\left( \ell(\widehat{y}_j,y)/T \right)}{\sum_{k=1}^M p_k \exp\left( \ell(\widehat{y}_k,y)/T \right)} \ell(\widehat{y}_j,y) \leq e^{B/T} \sum_{j=1}^M p_j \ell(\widehat{y}_j,y),\] where the first inequality is Jensen, and the second inequality uses that the loss is bounded \(\ell \leq B\) and \(\sum_{k=1}^M p_k \exp\left(\ell(\widehat{y}_k,y)/T \right)\geq 1\). The resulting bound is worse than 2 3 by the factor \(e^{B/T}\), which for any \(T\in(0,\infty)\) is strictly larger than \(1\). Importantly, any factor strictly larger than \(1\) means that the final bound has the same factor in front of \(\min_{1\leq j\leq M} \frac{1}{N}\sum_{i=1}^N (y_i-f_j(x_i))^2\) in 3, respectively \(\min_{1\leq k \leq M} \mathcal{R}_P(f_k)\) in 1. Therefore, this approach would not yield a positive conclusion to the open question. This highlights the importance of 1 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 [17].
Together with the suboptimality results by [1], 1 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 [1].
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].
The proof idea of 1, and specifically 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.
A previous version of the paper [1] 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.↩︎