Agree to Disagree: Demystifying Homogeneous Deep Ensembles through Distributional Equivalence

W2. Distributional Equivalence Sensitivity

The distributional equivalence property is very stable regarding the hyperparameters. Different training setups (e.g. solvers, leaning rates, etc.) can affect the distribution $p_F$ and the ratio $\rho$. For example, if the models are trained using other schemes, the models may achieve higher/lower $\rho$ values. But within each $p_F$, the trained models follow the distributional equivalence property.

In Appendix E, we add the results of models trained using momentum and momentum & weight decay. In the final version, we will add more experiments regarding other hyperparameters, such as learning rates.

W3. Performance Estimations with Large Capacity

We thank the reviewer for bringing this up. We would like to clarify that our proposed theoretical results are capable of handling any level of capacity. As derived in Theorem 5.1, the expected loss of the ensemble of $M$ individual models is determined by two factors. The first one is the expected loss of the population mean of the entire distribution $p_F$, and the second term is positive, divided by the number of ensemble members $M$. As a result, this framework suggests that the loss decreases inverse-proportionally as $M$ increases. When the ensemble capacity $M$ is sufficiently large, the loss converges to the loss of the population mean of the entire distribution. These theoretical results are all verified empirically in Fig. 7.

References

[1] Taiga Abe, Estefany Kelly Buchanan, Geoff Pleiss, Richard Zemel, and John P Cunningham. Deep ensembles work, but are they necessary? Advances in Neural Information Processing Systems, 35: 33646–33660, 2022b.

[2] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12):124003, 2021.

[3] Kobayashi, Seijin, Johannes von Oswald, and Benjamin F. Grewe. "On the reversed bias-variance tradeoff in deep ensembles."

[4] Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40): 24652–24663, 2020

[5] Cao, Y., Chen, Z., Belkin, M., and Gu, Q. (2022). Benign overfitting in two-layer convolutional neural networks. Advances in neural information processing systems, 35:25237–25250.

We thank the reviewer very much for acknowledging the theoretical contributions and the comprehensive experiments. We now answer the reviewer's questions as follows.

Q1. The Neural Collapse Assumption

In this work, we are focusing on interpolation models that fit the training set. This is supported by the recent studies on the terminal phase of training DNNs, where overfitting does not harm the models' performance (e.g. [2,4,5]). And this has become a common practice in training models at scale. Therefore, it is safe to assume that the models fit the training distribution completely and have become confident.

Q2. Uncertainty Estimation

We appreciate the reviewer for mentioning the application of uncertainty estimation of deep ensembles. In fact, our theoretical analysis of deep ensembles also sheds light on the uncertainty estimation of deep ensembles. We now give a brief explanation of this benefit and will add a more detailed analysis in the updated manuscript:

Previous work [1] has demonstrated that for a single input $\mathbf{x}$, the ensemble uncertainty can be decomposed as the summation of the ensemble diversity and the average single model uncertainty: $U(\bar{f}(\mathbf{x}))=Var_{p_F}[F(\mathbf{x})]+\mathbb{E}_{p_F}[U(F(\mathbf{x}))]$

First, for the ensemble diversity $Var_{p_F}[F(\mathbf{x})]$ itself, our results section 4.2 demonstrate that it should be understood with the actual distributions of the predictions. Eq 6, 7 (L355-366) further shows that the point-wise diversity is highly associated with the ensemble predictions. That is, the more confident the ensemble is at this data $\mathbf{x}$, the lower the ensemble diversity will be. Previous works fall short in this analysis as the differences among $\mathbb{x}$ are not correctly assessed.

For instance, [1] test the hypothesis that the ensemble diversity $Var_{p_F}[F(\mathbf{x})]$ is responsible for improved UQ and conclude that if the ensemble diversity is responsible, then it is suggested that "the performance gains from ensembling are somehow fundamentally different than the performance gains from increasing a single model’s capacity". Since the experiments in [1] also suggest that the performance gains are similar, it was then concluded that the ensemble diversity is not responsible for the improved UQ. Our results show a deeper understanding of this issue. From Theorem 5.1, it is clear that the ensemble capacity $M$ and the single model capacity $k$ affect the performance gain in completely different ways. As for the observed "similar performance gain" in Fig. 2 of [1], we add a discussion section in Appendix C of the updated manuscript to show that the conclusion was insufficiently justified.

W1. Experiments Scale

We thank the reviewer for the question. We answer this question in the two following aspects:

• First, we deduce that the revealed distributional equivalence property shall hold in more complicated dataset such as Imagenet. This is because the phenomenon of neural collapse has been observed for an even more complicated dataset. Besides, the consistency from CIFAR-10 to CIFAR-100 and to TinyImagenet shows a good generalization of the phenomenon. As a result, it is deduced that for even more complicated datasets, the trained models will have lower $\rho$ (e.g. see each row in Fig 8 and 9). That is, the scaling of models and datasets should only influence the resulting model performance $\rho$ instead of the neural collapse phenomenon.

• Second, we would like to emphasize that the experiment scale in our work is the greatest in the existing work regarding this topic, surpassing previous work by a large margin. We follow the training criterion of the important work of deep double descent [2], where the single models' capacity is limited to $k=64$. We expand this to $k=160$, resulting in multiple times larger models. Besides, due to the requirement of training multiple models, previous works are mainly carried out on the CIFAR dataset, where we extend this to the much more complicated TinyImagnet dataset.

We thank the reviewer very much for the acknowledgment of the contribution of our work. We address the remaining concerns of the reviewer as follows.

W1. Training Stochasticity

The reviewer's understanding of the term "training stochasticity" is correct. Here we leverage the stochastic gradient descent (SGD) algorithms as suggested in various previous works [1-4]. In SGD, the stochasticity rises from both the random initialization and the random order of the batches of data.

W2. Sources of Distributional Equivalence

We appreciate the reviewer for the insightful question. We would like to consider the distributional equivalence property as a deeper understanding of the influence of model capacity. It has been commonly agreed that when the model capacity (e.g. ResNet-18) and the training scheme (e.g. SGD) are fixed, the resulting models would have "similar performance" (e.g. testing accuracy, testing loss, etc.). However, relations between the resulting performance and the capacity/scheme are unclear and difficult to identify. Distributional equivalence, on the other hand, pushes this "similar performance" one step ahead and reveals that not only do the models have similar accuracy, but they also have very similar distributions of the outputs. That is, when the capacity is fixed, if a model generalizes to a specific part of the testing distribution, another part of the testing distribution is destined to be missed continuously. This could be attributed to the counterintuitive geometric properties of high-dimensional data manifold, where most volumes are distributed near the surface. However, we admit that this is an interesting but very complicated phenomenon. Thus we leave the detailed study to future work.

References

[1] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12):124003, 2021.

[2] Ekaterina Lobacheva, Nadezhda Chirkova, Maxim Kodryan, and Dmitry P Vetrov. On power laws in deep ensembles. Advances In Neural Information Processing Systems, 33:2375–2385, 2020.

[3] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017

[4] Huang, Gao, Yixuan Li, Geoff Pleiss, Zhuang Liu, John E. Hopcroft, and Kilian Q. Weinberger. "Snapshot Ensembles: Train 1, Get M for Free." In International Conference on Learning Representations. 2022.

W3. Results of NLL

Among the convex and decreasing metrics, Brier score takes the square of the prediction errors, which is compatible with the expectations and variances. As a result, Brier score has been preferred in the analysis of ensembles. For example, the latest existing work on understanding deep ensembles is entirely based on Brier score [1]. Therefore, we leverage this and start from Brier score at the beginning, too. The close relation between Brier score and the variance provides an insightful understanding of the ensemble performances in section 4. Afterward, in section 5, leveraging the Taylor expansion, we are the first to theoretically derive rules regarding the NLL of ensembles. The derived results are also empirically verified in Fig. 7.

W4. Error Rate in Fig. 6

We appreciate the reviewer very much for the suggestion! We have included the figures of the error rates corresponding to the figures in Fig. 6. The error rate results are shown in Appendix E. It can be clearly observed that the error rates are consistent with the losses.

W5. Training Strategies

We thank the reviewer very much for pointing this out. We clarify that the training strategy follows the settings in [5], which provide a consistent and scalable way of training numerous models. To resolve the reviewer's concern, we carry out additional experiments to train models using SGD with momentums and weight decay. The results in Appendix E of the updated manuscript show that the revealed distributional equivalence property holds across various training strategies. We will add a more comprehensive study with a more complete set of variants such as different solvers in the final version.

References

[1] Taiga Abe, Estefany Kelly Buchanan, Geoff Pleiss, Richard Zemel, and John P Cunningham. Deep ensembles work, but are they necessary? Advances in Neural Information Processing Systems, 35: 33646–33660, 2022b.

[2] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017

[3] Kobayashi, Seijin, Johannes von Oswald, and Benjamin F. Grewe. "On the reversed bias-variance tradeoff in deep ensembles."

[4] Ryan Theisen, Hyunsuk Kim, Yaoqing Yang, Liam Hodgkinson, and Michael W Mahoney. When are ensembles really effective? arXiv preprint arXiv:2305.12313, 2023.

[5] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12):124003, 2021.

[6] Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40): 24652–24663, 2020

[7] Cao, Y., Chen, Z., Belkin, M., and Gu, Q. (2022). Benign overfitting in two-layer convolutional neural networks. Advances in neural information processing systems, 35:25237–25250.

We appreciate the reviewer very much for the acknowledgment of our work.

W1. Majority Vote

Although the majority vote is also a way of combining predictions of independent models, it is a relatively less focused way of ensembling in the studies of deep ensembles. Specifically, the deep ensembles are introduced and defined as the arithmetic average of the models (e.g. [1-3]). As a result, we focus mainly on deep ensembles. As for the reference to the majority vote in L135, it is meant to emphasize that when exploring the mechanism of the models and ensembles, the trained models have very special mathematical properties and should not be considered as general functions.

W2. Dataset Scales and Distributional Equivalence

First, we would like to argue that even for CIFAR-10, the distributional equivalence property is not trivial. It might have been established that independent models with the same capacity might have similar performance over the testing set (e.g. accuracy, loss), that is $\mathbb{E}\_{\mathbf{x}\sim p_X}[f(\mathbf{x})]\approx \mathbb{E}\_{\mathbf{\mathbf{x}}\sim p_X}[g(\mathbf{x})]$ for two independent models. However, the property of the distribution of the predictions has never been recognized. The distributional equivalence property suggests a much stronger property on the distribution as $P(f(\mathbf{x})=v)\approx P(g(\mathbf{x})=v)$ for any $v$

Second, we clarify that we are focusing on interpolation models that fit the training set. This is supported by the recent studies on the terminal phase of training DNNs, where overfitting does not harm the models' performance (e.g. [5-7]). Therefore, it is safe to assume that the models fit the training distribution completely and have become confident.

Finally, we emphasize that due to the requirement of training numerous models, the scale of the experiments in our work is already the greatest in the existing work regarding this topic, surpassing previous work by a large margin. We follow the training criterion of the important work of deep double descent [2], where the single models' capacity is limited to $k=64$. We expand this to $k=160$, resulting in multiple times larger models. Besides, due to the requirement of training multiple models, previous works are mainly carried out on the CIFAR-10 dataset, where we extend this to the much more complicated TinyImagnet dataset. And compared with studies of deep ensembles, we have $M=100$ ensemble members for each setting, which is the largest to our best knowledge.

Q1. Predicted Likelihood Vector

We clarify that the use of the output of the target class is based on the following reasons: (1) Because of the neural collapse phenomenon, the predicted probability of the target class is either very close to 1 or very close to 0. When it's close to 1, the prediction of all other classes is naturally zeros. And when it's close to 0, there is usually one other dominant class. Therefore, taking the target class only is already sufficient for the analysis. (2) Negative log-likelihood only considers the target class. Therefore, it creates unnecessary inconsistency across the analysis. (3) Due to the softmax layer, the output of the target class already contains information from the prediction of all classes [5]. Thus they are almost equivalent. We elaborate on this as follows:

Note that discriminative models do not directly predict the likelihood vector $\mathbf{p}\in[0,1]^c$. Instead, they predict the logits $\mathbf{y}\in\mathbb{R}^c$, and then a softmax activation is applied to $\mathbb{y}$ to obtain the likelihood. Here $c$ is the number of classes and let $t$ denote the ground truth class. Then the target-class Brier score is $(1-p_t)^2=(\frac{\sum_{i\ne t}e^{y_i}}{\sum_{j=1}^ce^{y_j}})^2$

The all-class Brier score is $\|\|\mathbf{y} - \mathbf{1}\_t\|\|\_2^2 = \sum_{i\ne t}p_i^2 + (1-p_t)^2=\sum_{i\ne t}(\frac{e^{y_i}}{\sum_{j=1}^ce^{y_j}})^2+(\frac{\sum_{i\ne t}e^{y_i}}{\sum_{j=1}^ce^{y_j}})^2=\frac{\sum_{i\ne t}(e^{y_i})^2+(\sum_{i\ne t}e^{y_i})^2}{(\sum_{j=1}^ce^{y_j})^2}$ It can be observed that the numerators are $\sum_{i,j\ne t}e^{y_iy_j}$ and $\sum_{i,j\ne t}e^{y_iy_j}+\sum_{i\ne t}e^{2y_i}$, respectively. That is, the all-class Brier score upweights the weights of the non-target class by 1. The differentiation between them is one of extent rather than essence.

Besides, by Cauchy-Schwartz inequality, we have $(1-p_t)^2\le\|\|\mathbf{y} - \mathbf{1}_t\|\|_2^2\le 2(1-p_t)^2$ that tightly bounds the all-class Brier score with the single-class one.

References

[1] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017

[2] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12):124003, 2021.

[3] Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40): 24652–24663, 2020

[4] Cao, Y., Chen, Z., Belkin, M., and Gu, Q. (2022). Benign overfitting in two-layer convolutional neural networks. Advances in neural information processing systems, 35:25237–25250.

[5] Wang, Yipei, and Xiaoqian Wang. "“Why Not Other Classes?”: Towards Class-Contrastive Back-Propagation Explanations." Advances in Neural Information Processing Systems 35 (2022): 9085-9097.

We appreciate the reviewer very much for acknowledging our in-depth analysis and the contributions to understanding deep ensembles. To resolve the remaining concern of the reviewer, we now address all the questions as follows.

W1. & Q2. Loss Functions

We understand the reviewer's concern regarding the generalizations of the derived theories regarding different loss functions. We answer these questions from the two perspectives that the reviewer mentioned:

1. Theoretical Derivations: When the distributional equivalence property and neural collapse hold, the theoretical results should generalize easily to all convex and decreasing loss functions, where Brier scores (i.e. square of MSE) and NLL are the two most important types. In Appendix B.8, we have proved the same conclusions as Theorem 5.1 with a completely generalized setting. Should the audience be curious about any kind of loss functions or distributions, they can instantiate $p_{l,X}, p_X$, and $\phi$ to the instances they prefer.

2. Empirical Settings: We clarify that all models are trained with cross-entropy loss, which is the most commonly used method. This is because deep ensembles are famous for being simple to deploy by directly taking the average of several independently trained models [1]. Therefore, we focus on this most straightforward case -- interpolation models that fit the training set. This is supported by the recent studies on the terminal phase of training DNNs, where overfitting does not harm the models' performance (e.g. [2-4]). Therefore, it is safe to assume that the models fit the training distribution completely and have become confident.

W2. The Distributional Equivalence Property

We understand the reviewer's concern where the distributional equivalence property seems to be "too strong" in the proof. However, we emphasize that the missing property is exactly what has hindered the previous understanding of deep ensembles.

We have demonstrated in Fig 2(a), 8, and 9 that such a property is prevalent in trained models with common training criteria. In the proofs, we demonstrate this property is responsible for all the "mysterious" performance improvement of deep ensembles. Furthermore, the theoretical results accurately predict the performance of ensembles with an arbitrary number of members -- a theoretically guaranteed scaling law for ensembles. All of these results rely on the fact that independently trained models have this distributional equivalence property.

Besides, as mentioned above, we have demonstrated in Appendix B.8 that the theoretical derivations generalize to arbitrary distribution $p_{l,X},p_X$ and loss function $\phi$. In the manuscript, we instantiate them to the most commonly studied ones. However, they can be instantiated to any instances, too.

W3. The definition and importance of $\hat{f}$

We appreciate the reviewer very much for bringing up the importance of $\hat{f}$. However, we respectfully disagree with the reviewer's point that "$\hat{f}$ is not meaningful". Instead, $\hat{f}$ plays a crucial role in understanding the dynamics of deep ensembles. We elaborate on this as follows:

• The approximation to neural collapse: It has been both empirically and theoretically demonstrated in previous work that trained models enter a terminal phase called neural collapse, where deep models can become overconfident without falling into the traditional variance-bias trade-offs. In such scenarios, the predictions of models become extremely close to 0 and 1 for discriminative tasks. Therefore, $\hat{f}$ can be used as an approximation of $f$ in theoretical analyses.

• The approximation is very accurate: Although $\hat{f}$ approximates $f$ in a seemingly strong assumption, we have demonstrated that this approximation is very accurate.

  • Qualitatively, we have demonstrated in Fig. 2(a), 8, and 9 that this holds true for all kinds of models and datasets.
  • Quantitatively, we carry out ALL of our experiments using the original functions $f$ instead of the approximations. It has been verified that the theoretical results derived using the approximations accurately predict the behaviors of the original models. This provides support to the accuracy of the estimations.
  • Theoretically, we have proved rigorously in Appendix B.8 (L950-1012) that all the theoretical proof can be generalized to the original models $f$. The use of the surrogate models $\hat{f}$ is purely for tractability. Besides, it enables all the applications such as preciting the dynamics of ensembles of arbitrarily many members using only 2 members.

• The connection between $\hat{f}$ and the corrections: We are glad that the reviewer notices the tight connection between the surrogate models $\hat{f}$ and the correction rate of individual models. In fact, this contributes to a very interesting implication of this work that the dynamic of the entire ensemble system can be identified with very few factors. As demonstrated in Theorem 4.2 - 5.1, the improvement from ensembles is mainly influenced by (1) the correction rate $\rho$ and (2) the correlation between any two models.

W4. Notations and Conditions in Theorem 4.1

• The minimization term in Theorem 4.1: First, as mentioned in the response to W1, we appreciate the reviewer very much for pointing out the support of $p_F$ should be defined as $supp(p_F)\subset\mathcal{F}$. However, we emphasize that we are actually proving an even stronger version of Theorem 1. Because $supp(p_F)\subset\mathcal{F}$, the minimization over the support should be no smaller than the minimization over its superset $\mathcal{F}$. Formally: $\min_{f\in \mathcal{F}}\{\mathbb{E}_{X\sim p_X}[\phi(f(X))]\}\le\min_{f\in supp(p_F)}\{\mathbb{E}_{X\sim p_X}[\phi(f(X))]\}$ As a result, Theorem 4.1 holds for both minimization regions.

• The distributional equivalence property: The requirement that the reviewer mentioned is a weaker form of the distributional equivalence property revealed in our work, whose detailed descriptions and verifications can be found in sec 4.1 of our manuscript. We clarify that it should be "$\hat{F},\hat{G}\sim \hat{p}_F$" instead of for all $\hat{f},\hat{g}\in\hat{\mathcal{F}}$. We will revise this typo in the proof. However, this typo does not affect any of the theoretical results.

We emphasize that this property is the main cause of the performance gain of homogeneous deep ensembles, which has never been discovered before. Due to the lack of this property, previous work can only refer to ensembles as "a reliable black box" (L61-63).

References

[1] Taiga Abe, Estefany Kelly Buchanan, Geoff Pleiss, Richard Zemel, and John P Cunningham. Deep ensembles work, but are they necessary? Advances in Neural Information Processing Systems, 35: 33646–33660, 2022b.

[2] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12):124003, 2021.

[3] Kobayashi, Seijin, Johannes von Oswald, and Benjamin F. Grewe. "On the reversed bias-variance tradeoff in deep ensembles."

We appreciate the reviewer very much for the effort in reviewing our work and providing insightful feedback!

We understand that the reviewer's main concern lies in the definitions of the distributions of trained models, functions of models, etc. Here we address the reviewers's concerns as follows:

W1. The settings of $p_F$

• The set of trained models: In this work, we focus on models optimized regarding the training distribution. This is a very common setup in the studies of deep ensembles (e.g. [1]) and related topics (e.g. [2,3]). We denote by $\mathcal{F}$ the set of all these models. Empirically, they can be models that interpolate the training set.
• The distribution of trained models (L179-181): Deep ensembles train $M$ models independently with the same stochastic algorithm. This process leads to the distribution $p_F$ of interpolation models over $\mathcal{F}$. As a consequence, training a model is equivalent to sampling from such a distribution $F\sim p_F$.
• The relations between $p_F$ and $\mathcal{F}$: In summary, as we defined in L181, $p_F$ is a distribution of interpolation models over $\mathcal{F}$. This also answers the reviewer's question about the support of $p_F$. That is, $supp(p_F)\subset\mathcal{F}$. We add a clear and formal definition of the support of $p_F$ in the updated manuscript for a better presentation.
• Rigorous Definitions: We would also clarify that the set $\mathcal{F}$ and the distributions $p_F$ are distinguished purposely for a rigorous study. For instance, in eq. 1, we specifically define the ensemble as the expectation over the distribution $p_F$ instead of the expectation over the entire set $\mathcal{F}$ of interpolation models because the ensembles implicitly sample trained models under $p_F$ from $\mathcal{F}$ instead of uniformly. On the other hand, as defined in the "best model" should be the best one over the entire set $\mathcal{F}$ instead of the distribution $p_F$.

W2. The proof of Proposition 3.1

We thank the reviewer very much for pointing out this. The fact that the lower gap LG(\mathbf{x})\ being non-positive follows naturally the arithmetic laws. In plain language, the expectation is always between the maximum and minimum, thus leading to a greater value than the minimum under a monotonic function. We provide the formal proof below and have added this to the upgraded appendix:

Proof: WLOG, let $\phi$ be monotonically increasing. Then $\min_{f\in\mathcal{F}}\{\phi(f(\mathbf{x}))\}=\phi(\min_{f\in\mathcal{F}}\{f(\mathbf{x})\})$ Since $\min_{f\in\mathcal{F}}\{f(\mathbf{x})\}\le\mathbb{E}\_{F\sim p_F}[F(\mathbf{x})]$ and $\phi$ is monotonically increasing, we have $\phi(\min_{f\in\mathcal{F}}\{f(\mathbf{x})\})\le\phi(\mathbb{E}\_{F\sim p_F}[F(\mathbf{x})])$ Combining them results in $\min_{f\in\mathcal{F}}\{\phi(f(\mathbf{x}))\}\le\phi(\mathbb{E}\_{F\sim p_F}[F(\mathbf{x})])$ Therefore $LG(\mathbf{x})=\min_{f\in\mathcal{F}}\{\phi(f(\mathbf{x}))\}-\phi(\mathbb{E}_{F\sim p_F}[F(\mathbf{x})])\le0$ This proves the proposition.$\Box$