# Harnessing Hierarchical Label Distribution Variations
in Test Agnostic Long-tail Recognition

Zhiyong Yang  Qianqian Xu  Zitai Wang  Sicong Li  Boyu Han  Shilong Bao
Xiaochun Cao  Qingming Huang

###### Abstract

This paper explores test-agnostic long-tail recognition, a challenging long-
tail task where the test label distributions are unknown and arbitrarily
imbalanced. We argue that the variation in these distributions can be broken
down hierarchically into global and local levels. The global ones reflect a
broad range of diversity, while the local ones typically arise from milder
changes, often focused on a particular neighbor. Traditional methods
predominantly use a Mixture-of-Expert (MoE) approach, targeting a few fixed
test label distributions that exhibit substantial global variations. However,
the local variations are left unconsidered. To address this issue, we propose
a new MoE strategy, $\mathsf{DirMixE}$, which assigns experts to different
Dirichlet meta-distributions of the label distribution, each targeting a
specific aspect of local variations. Additionally, the diversity among these
Dirichlet meta-distributions inherently captures global variations. This dual-
level approach also leads to a more stable objective function, allowing us to
sample different test distributions better to quantify the mean and variance
of performance outcomes. Theoretically, we show that our proposed objective
benefits from enhanced generalization by virtue of the variance-based
regularization. Comprehensive experiments across multiple benchmarks confirm
the effectiveness of $\mathsf{DirMixE}$. The code is available at
https://github.com/scongl/DirMixE.

Machine Learning, ICML

##  1 Introduction

Traditional machine learning (ML) methods are usually designed for data with a
balanced distribution (Krizhevsky et al., 2009; Deng et al., 2009). In
contrast, most real-world data exhibits a long-tailed nature. Specifically, a
few classes have a large number of samples (i.e., head classes), while many
others have far fewer (i.e., tail classes) (Zhang et al., 2023b). This pattern
produces profound studies in many tasks, including species classification
(Horn et al., 2018; Miao et al., 2021), face recognition (Zhang et al., 2017;
Zhong et al., 2019), medical image diagnosis (Galdran et al., 2021), social
image understanding (Tang et al., 2016; Li et al., 2018), semantic
segmentation (Zhong et al., 2023; Zhang et al., 2020), and object detection
(Lin et al., 2017).

Hitherto, considerable methods have been developed to address this issue
seeing its widespread nature. To evaluate model performance with long-tail
distributions, most existing studies train their models on long-tailed data
and test them on a balanced dataset (Cui et al., 2019; Cao et al., 2019; Kang
et al., 2020; Menon et al., 2021; Kini et al., 2021b; Cui et al., 2021;
Rangwani et al., 2022; Alshammari et al., 2022; Wang et al., 2023). This
protocol poses an implicit assumption: the test distribution is balanced and
fixed. However, this assumption is often invalid, as the test distribution is
typically unknown and can change over time.

Figure 1: Traditional methods can only capture global variations of label
distribution. By contrast, our $\mathsf{DirMixE}$ learns from both global and
local variations, covering more test distributions.

To reduce the bias in test distribution, Zhang et al. (2022) recently proposed
a more practical setting called test-agnostic long-tailed recognition. This
setting aims at ensuring model efficacy across heterogeneous test
distributions, each exhibiting varying levels of imbalance (ranging from long-
tail and nearly uniform to inversely long-tail distributions). To address this
challenge, they propose a novel mixture of experts approach called SADE,
crafting distinct experts for each type of distribution. A typical feature of
SADE is that each expert therein is assigned to a fixed label distribution. We
argue that the random variation of the unseen test label distribution could be
decomposed into global and local variations. The global variations capture the
heterogeneous diversity across different distributions (say, the significant
gap between long-tail and inverse long-tail distribution). The local
variations capture the milder changes mostly concentrated within a neighbor.
Back to SADE, the fixed assignment scheme could capture global variations by
choosing sufficiently diverse target distributions for different experts.
However, the local variations of label distributions can hardly be discovered
by fixed points. In this sense, how to comprehensively utilize the
hierarchical random variations remains an open problem. To address this issue,
we propose a new mixture-of-experts strategy with the following contributions.

First, we explore how to better model the randomness of the unknown test label
distributions in a hierarchical manner. To this end, we propose a
probabilistic framework where the label distributions are presumed to be
sampled from a meta-distribution. To capture the global variations, we
formulate the meta-distribution as a mixture form of heterogeneous
distributions. Herein, each component is a Dirichlet distribution capturing
the local variations of a specific factor disentangled from the meta-
distribution. Furthermore, we allocate a specific expert for each component of
the meta-distribution to ensemble expert models enjoying diverse skills. The
overall effect is illustrated in Fig.1.

On top of this, we take a step further to explore how to evaluate the overall
performance on the meta-distribution and learn from it. We argue that the
average performance is not stable enough for the complex random variations of
the test label distributions. In this sense, we develop a Monte Carlo method
for estimating the mean and variance of the averaged training loss obtained
across different label distributions. From the optimization perspective,
minimizing the variance term might prevent the model from performing better
than the average level. We thus construct a semi-variance regularization as a
surrogate for the empirical variance, selectively penalizing performances
below the average level. The attained estimation forms the basis for our
objective function in training the expert ensemble.

Finally, we dive into the theoretical underpinnings for the generalization
ability of our method. We can attain a sharper upper bound of generalization
error thanks to the variance-based regularization scheme. Moreover, it also
indicates that Monte Carlo sampling offers better generalization than the
previous method developed on fixed test distributions.

##  2 Related Work

This paper will provide a brief overview of several areas closely related to
our study.

Loss Modification. The main problem with traditional methods is their poor
performance on tail classes. A direct solution is modifying the loss function
to enhance performance for these classes. Increasing the weights of tail-class
losses is a common tactic (Morik et al., 1999; Cui et al., 2019) along this
course. While seemingly reasonable, it can lead to unstable optimization (Cui
et al., 2019; Cao et al., 2019; Wang et al., 2023) and ruin the overall
performance. Cao et al. (2019) suggests using weighted terms mainly in the
later stages of training. To further address the optimization issues caused by
unequal weights, another line of research turns to adjust the logits through
class-specific operations. For instance, Tan et al. (2020) observes that
positive samples of one class can be negative for others, causing discouraging
gradients for tail samples. To address this issue they proposed the equalized
loss, adding class-dependent operations to ignore these gradients. LDAM
imposes a larger margin penalty on tail-class logits for stronger
regularization (Cao et al., 2019). The LA loss (Menon et al., 2021) uses
additive adjustments on the logits to maintain the consistency of balanced
error. Later, Kini et al. (2021a) combines additive and multiplicative terms
(Ye et al., 2020) to form a unified approach called the VS loss. Most
recently, Wang et al. (2023) provides a detailed generalization analysis of
these loss-modification methods using a local contraction lemma.

Experts Ensembling. In our paper, we address the long-tail issue using a
mixture of experts strategy. This approach is a specific form of ensemble
learning that combines multiple models to enhance overall model
generalization. Early long-tail ensemble learning methods (Zhou et al., 2020;
Guo & Wang, 2021) use two network branches to handle long-tail and uniform
distributions separately. During training, these branches’ outputs are
dynamically merged, shifting the focus progressively from head to tail
classes. Li et al. (2020) finds that balanced datasets often outperform long-
tail ones. As a result, they split the long-tail dataset into several more
balanced subsets and designed networks with multiple branches. Since model
diversity is crucial in ensemble learning, recent developments have turned
their focus to improving experts with different skills. For instance, in ACE
(Cai et al., 2021), three experts are created to learn from subsets containing
all classes, middle+tail classes, and tail classes, respectively. RIDE (Wang
et al., 2021) uses a KL-divergence based loss to encourage diversity among
experts. SADE (Zhang et al., 2022) introduces a concept called test-agnostic
long-tail recognition, which demands generalization across various test
distributions. This is achieved by combining diverse experts trained with
different logit adjustments using self-supervision. Finally, BalPoE (Aimar et
al., 2023) suggests a balanced product of experts approach, blending multiple
logit-adjusted experts using a product rule to suit the chosen test
distribution.

In this paper, we construct a distributional mixture of experts model for the
test-agnostic long-tail recognition task. Specifically, instead of using fixed
test distributions, we adopt a Dirichlet mixture distribution to
simultaneously model the global and local variations of the unseen label
distribution. Moreover, our method also enjoys a sharp generalization bound.

##  3 Problem Formulation

In this study, we focus on the challenge of training a good model in the
presence of a long-tail data distribution. We define our training data as
$\mathcal{S}=\left\\{\bm{x}_{i},y_{i}\right\\}_{i=1}^{N}$, sampled from
distribution $\mathcal{D}$, with a total of $N$ instances. Here,
$\bm{x}_{i}\in\mathcal{X}\subseteq\mathbb{R}^{d}$ represents the raw input
feature of dimensionality $d$ for instance $i$, and $y_{i}\in{1,2,\cdots,C}$
denotes the corresponding label in a $C$-class classification problem. Under
this setting, if we decompose the joint data distribution as
$\mathcal{D}=\mathbb{P}_{tr}\left[{\bm{x}|y}\right]\cdot\mathbb{P}_{tr}\left[{y}\right]$,
then the label distribution is often highly skewed in the sense that
$\max_{i}{\mathbb{P}_{tr}\left[{y=i}\right]}/\min_{j}{\mathbb{P}_{tr}\left[{y=j}\right]}>>1$.
This imbalance necessitates the design of specialized learning strategies to
ensure adequate performance in the tail classes.

Test Agnostic Long-tail Recognition. Contrary to the assumption of a uniform
test label distribution, we adopt the test agnostic long-tail recognition in
(Zhang et al., 2022). This approach evaluates model performance across
multiple test sets, each subjects to a different label distribution. From a
distributional standpoint, we can frame this as a label shift problem, where
i) $\mathbb{P}_{tr}\left[\bm{x}|y\right]=\mathbb{P}_{te}\left[\bm{x}|y\right]$
and ii) $\mathbb{P}_{tr}\left[y\right]\neq\mathbb{P}_{te}\left[y\right]$
generally. To model the uncertainty of the test label distributions, we assume
that the labels are sampled in the following hierarchical process:

  1. 1)

Due to label shift problem, the test label distribution
$\mathbb{P}_{te}\left[{y}\right]$ should be more than just a constant
function. In this paper, we assume that $\mathbb{P}_{te}\left[{y}\right]$ is
rather sampled from a meta-distribution $\mathcal{E}$ over the simplex
$\Delta^{C}$, i.e., $\mathbb{P}_{te}\left[y\right]\sim\mathcal{E}$. Moreover,
the selected meta-distribution should: i) reflect the diversity of the label
distributions with significant different degrees of imbalance (global
variations); ii) reflect the local variations of the label distributions to
make more stable predictions (local variations).

  2. 2)

The test data is then sampled from the observed test distribution:
$(\bm{x},y)\sim\mathbb{P}_{te}\left[{\bm{x},y}\right]=\mathbb{P}_{tr}\left[{\bm{x}|y}\right]\cdot\mathbb{P}_{te}\left[{y}\right]$.

Goal. We aim to develop a well-trained model that demonstrates good
performance across the entire spectrum of test label distributions within
$\mathcal{E}$. Moreover, if we denote the performance of a model $f$ on test
data $\mathcal{D}_{te}$ by a loss function $\ell$, the goal can be expressed
as:

$\displaystyle\operatorname*{\mathbb{E}}_{(\bm{x},y)\sim\mathbb{P}_{te}\left[{\bm{x},y}\right]}\ell\left(y,f(\bm{x})\right)~{}\text{is
small for most}~{}\mathbb{P}_{te}\left[y\right]\sim\mathcal{E}.$

##  4 Methodology

###  4.1 Preliminaries

To initiate our discussion, we revisit the approach to addressing the label
shift problem in scenarios where the test label distribution
$\mathbb{P}_{te}\left[y\right]$ is fixed but differs from the training
distribution.

Following the convention of the classification problem, we want to learn a
scoring function
$\\{f^{(1)}_{\theta},\cdots,f^{(C)}_{\theta}\\}:\mathbb{R}^{d}\rightarrow\Delta^{C}$
by minimizing the CE loss over the training data:

$\displaystyle\ell_{CE}(f_{\theta}(\bm{x}),y)=-\log\left(\mathsf{softmax}\left(f^{(y)}_{\theta}(\bm{x})\right)\right).$

With the adjusted logits (Menon et al., 2021), if the softmax function is
calibrated, we have
$\mathsf{softmax}(f^{(y)}_{\theta}(\bm{x}))\propto\mathbb{P}_{tr}\left[y|\bm{x}\right]$.
We can then achieve the Fisher consistency in the sense that:

$\displaystyle\hat{y}=\operatorname*{argmax}_{i\in\\{1,\cdots,C\\}}f^{(i)}_{\theta}(\bm{x})\approx\operatorname*{argmax}_{i\in\\{1,\cdots,C\\}}\mathbb{P}_{tr}\left[y=i|\bm{x}\right]$

However, due to the label shift problem, the prediction rule suffers a
distributional bias since
$\mathbb{P}_{tr}\left[{y|\bm{x}}\right]\neq\mathbb{P}_{te}\left[{y|\bm{x}}\right]$.
To address this issue, (Hong et al., 2021) proposes to employ the logit
adjustment method (Menon et al., 2021) to modify the loss function.
Specifically, one can use the following loss function denoted as
$\ell_{\mathsf{LA}}\left(f_{\theta}(\bm{x}),y;\mathbb{P}_{te}\right)$:

$\displaystyle\ell_{CE}\left(f^{(y)}_{\theta}(\bm{x})-\log\left(\frac{\mathbb{P}_{te}\left[{y}\right]}{\mathbb{P}_{tr}\left[{y}\right]}\right)\right).$
(1)

To see how the new logarithm factor eliminates the bias, we can again check
the probability correspondence when calibration of the softmax score is
achieved:

$\displaystyle\mathsf{softmax}(f^{(y)}_{\theta}(\bm{x}))\propto\mathbb{P}_{tr}\left[y|\bm{x}\right]\cdot\frac{\mathbb{P}_{te}\left[{y}\right]}{\mathbb{P}_{tr}\left[{y}\right]}\propto\mathbb{P}_{te}\left[y|\bm{x}\right]$

This implies that when the model is effectively trained, it is possible to re-
establish the Bayes rule.

###  4.2 $\mathsf{DirMixE}$: Learning with a Dirichlet Mixture of the Experts

We are ready to formulate our method, called $\mathsf{DirMixE}$, for unknown
label distributions $\mathbb{P}_{te}\left[y\right]$. Seeing the complicated
random variation, minimizing the mean error is not enough for a stable
prediction. In this sense, we aim to optimize the model performance from a
distributional perspective. In other words, we want to ensure the average
error is low for most possible choices of $\mathbb{P}_{te}\left[y\right]$. To
do this, we control the average error’s first (mean) and second (variance)
moment to be small. Mathematically, we try to minimize the following objective
function:

$\displaystyle\operatorname*{\mathbb{E}}_{\mathbb{P}_{te}\sim\mathcal{E}}\left[\mathcal{R}(f;\mathbb{P}_{te})\right]+\lambda\cdot\operatorname*{\mathbb{V}}_{\mathbb{P}_{te}\sim\mathcal{E}}\left[\mathcal{R}(f;\mathbb{P}_{te})\right]$
(2)

where
$\mathcal{R}(f;\mathbb{P}_{te})=\operatorname*{\mathbb{E}}_{(\bm{x},y)\in\mathbb{P}_{tr}}\ell_{\mathsf{LA}}(f_{\theta}(\bm{x}),y;\mathbb{P}_{te})$
is the expected logit adjustment loss (see Eq.1) given the label distribution
$\mathbb{P}_{te}$, and $\lambda$ is a trade-off coefficient.

It is hard to simultaneously minimize all the training losses over different
distributions by learning a single model. To address this issue, we propose an
ensemble learning strategy to deal with the heterogeneity among test
distributions with different experts. We will elucidate the technical aspects
of our approach by addressing three key questions: 1) How to model the
distribution $\mathcal{E}$ to capture the test distribution of interest
effectively, 2) How to assign different experts to distinct test
distributions, and 3) How to approximate the objective function using sampling
methods and empirical data.

Targeted $\mathcal{E}$. The target $\mathcal{E}$ is designed to capture the
global and local variations of the label distribution, where we resort to the
hierarchical structure of mixture distributions. Specifically, we define $K$
as the number of components in this mixture distribution, using a discrete
distribution to select a component $i$ with probability $p_{i}$. Given the
commonality of the Dirichlet distribution for sampling discrete probabilities
(label distributions are discrete probabilities ), we define the $i$-th
component itself as a Dirichlet distribution with parameters
$\bm{\alpha}^{(i)}=[\alpha^{(i)}_{1},\cdots,\alpha^{(i)}_{C}]$. This mixture
distribution framework facilitates the hierarchical sampling of
$\mathbb{P}_{te}$, offering a structured approach to model the variation of
test label distributions:

$\displaystyle\mathbb{P}_{te}|i~{}\sim~{}\mathsf{Dir}\left({\alpha}^{(i)}_{1},\cdots,{\alpha}^{(i)}_{C}\right)$
(3) $\displaystyle
i|\bm{p}~{}\sim~{}\mathsf{Discrete}\left(p_{1},\cdots,p_{K}\right)$ (4)

In the meta-distributions, the diversity across different distributions
captures the global variations. Moreover, within each component, the Dirichlet
distribution makes sure that the local variations concentrated on the mean can
be effectively characterized. In this sense, we can better utilize the
hierarchy of the variations by virtue of the meta-distribution.

Note that prior research (Aimar et al., 2023; Hong et al., 2021; Zhang et al.,
2022) can be regarded as a special case of the proposed approach, wherein the
Dirichlet distribution is substituted with a fixed point (Dirac delta
distribution). However, as we will demonstrate in the subsequent section, this
approach limits the generalization capacity of the resulting model. This
limitation arises because such fixed distribution schemes inadequately
represent the randomness inherent in the test label distributions.

Figure 2: Illustration of the training process, where a hierarchical sampling
process is employed to esitmate the empirical risk.

Mixture of Experts Strategy. The overall model is expressed in a compositional
structure

$\displaystyle
f^{(i)}_{\theta}(\cdot)=g^{(i)}\circ\psi(\cdot),~{}i=1,2,\cdots,K,$

where $f^{(i)}$ is the model allocated for the $i$-th component, $g^{(i)}$
reflects the distributional-specific feature, $\psi$ reflects the invariant
part and is shared across components.

In the upcoming discussions, we will see how $\mathcal{E}$ and the MoE
strategy will help us construct an estimation of the loss distribution.

Empirical Approximation of the Objective Function. To approximate the
population-level objective function (Eq.2), we utilize a Monte Carlo method to
estimate the expectation and variance over $\mathcal{E}$. This is achieved by
generating empirical data for test label distributions. Each time, we sample a
test label distribution ${\mathbb{P}}$ and a component $\xi$ from the
hierarchical model as outlined in equations (3)-(4). The generated data set is
represented as $\mathcal{P}=\\{{\mathbb{P}}_{j},\xi_{j}\\}_{j=1}^{M}$. In this
process, each expert $f_{\theta}^{(\xi_{j})}$ is assigned to the sampled pair
$({\mathbb{P}}_{j},\xi_{j})$. The performance of these experts is then
evaluated based on the following average loss:

$\displaystyle\hat{\ell}_{{\mathsf{LA}}_{j}}=\frac{1}{N}\sum_{(\bm{x},y)\in\mathcal{D}}{\ell_{\mathsf{LA}}}\left(f_{\theta}^{(\xi_{j})}(\bm{x}),y;\mathbb{P}_{j}\right).$

From all of the above, we get the Monte Carlo estimation of the population
mean and variance in (2) as:

$\displaystyle\hat{\mathbb{E}}(\ell_{\mathsf{LA}})=\frac{1}{M}\sum_{j=1}^{M}\hat{\ell}_{{\mathsf{LA}}_{j}},~{}\hat{\mathbb{V}}(\ell_{\mathsf{LA}})=\frac{1}{M}\sum_{j=1}^{M}\left(\hat{\ell}_{{\mathsf{LA}}_{j}}-\hat{\mathbb{E}}(\ell_{\mathsf{LA}})\right)^{2}.$

Practically, minimizing the variance term tends to punish
$\hat{\ell}_{{\mathsf{LA}}_{j}}$ being smaller than its empirical mean. This
over-regularization can impede the training process, particularly for test
distributions that are relatively easier to learn. To circumvent this
challenge, we replace the variance penalty with a semi-variance term, which
only penalizes $\hat{\ell}_{{\mathsf{LA}}_{j}}$ that are larger than the mean.

$\displaystyle\hat{\mathbb{V}}_{+}(\ell_{\mathsf{LA}})=\frac{1}{M}\sum_{j=1}^{M}\left(\left(\hat{\ell}_{{\mathsf{LA}}_{j}}-\hat{\mathbb{E}}(\ell_{\mathsf{LA}})\right)_{+}\right)^{2}.$

Please see Appendix A for the sampling process in details.

Putting all together, we come to the final objective function:

$\displaystyle\min_{g^{(1)},\cdots,g^{(K)},~{}\psi}~{}\hat{\mathbb{E}}(\ell_{\mathsf{LA}})+\lambda\cdot\hat{\mathbb{V}}_{+}(\ell_{\mathsf{LA}}).$

During testing, we adopt the self-supervision strategy as proposed in SADE
(Zhang et al., 2022) to learn a set of model averaging weights
$\omega^{(1)}_{te},~{}\omega^{(2)}_{te},~{}\cdots,~{}\omega^{(K)}_{te}$. The
prediction for a test data point is then determined by combining these
weights, leading to a weighted average of the outputs from the individual
models expressed as follows:

$\displaystyle f_{te}(\bm{x})=\sum_{i=1}^{K}\omega^{(i)}_{te}\cdot
f^{(i)}(\bm{x}).$ (5)

##  5 Theoretical Analysis

For the sake of simplicity, we will adopt asymptotic notations to perform
magnitude comparison. Specifically, $f(n)\lesssim g(n)$ denotes $\exists
C>0,f(n)\leq C\cdot g(n)$, and $f(n)\gtrsim g(n)$ vice versa. $f(n)\asymp
g(n)$ means $f(n)\lesssim g(n)$ and $f(n)\gtrsim g(n)$ hold simultaneously.
All the proofs are deferred to Appendix B and D.

(a) Density of Gamma w.r.t $\alpha$

(b) $\rho$ Bound for the Gamma

(c) Density of Pareto w.r.t $\theta$

(d) $\rho$ Bound for the Pareto

Figure 3:  The Upper Bound for $\rho$ for different distributions. (a) shows
the distribution density of the Gamma distribution with $\beta$ fixed as 0.5
and $\alpha$ varied. The corresponding distribution has a tailed shape when
$\alpha<1$. (b) shows the upper bound $\rho$ for $\alpha<1$. One can observe
that $\rho$ is roughly greater than $0.4$ in this range. (c) shows the
distribution density of the Pareto distribution with $\ell_{m}$ fixed as $0.1$
and $\theta$ varied. (d) shows the $\rho$ value for $2<\theta\leq 10$, we can
see that $\rho$ is slightly greater $0.2$ for large $\theta$. In all these
observed cases, the assumption
$\operatorname*{\mathbb{V}}_{+}\asymp\operatorname*{\mathbb{V}}$ is
admissible.

###  5.1 Generalization Ability of $\mathsf{DirMixE}$

To show the generalization ability of our proposed method, we attempt to
answer two questions theoretically. The first question is how well the
proposed training method can generalize to unseen label distributions. In the
following Thm., we answer this question by presenting an upper bound of
$\operatorname*{\mathbb{E}}^{\prime}({\ell_{\mathsf{LA}}})$, the expected loss
over all test label distributions sampled from $\mathcal{E}^{\prime}$ (which
is not necessarily identical to $\mathcal{E}$) and $\mathcal{D}$. We assume
that $\operatorname*{\mathbb{V}}\asymp\operatorname*{\mathbb{V}}_{+}$, which
will be justified in Sec.5.2.

######  Theorem 1 (Generalization Bound, Informal).

Let $\mathcal{E}$ be the true meta-distribution and $\mathcal{P}$ be an
observed empirical distribution sampled by the Monte Carlo method. Moreover,
the training data $\mathcal{S}$ are sampled in an i.i.d manner from its true
distribution $\mathcal{D}$. Assume that
$\operatorname*{\mathbb{V}}({\ell_{\mathsf{LA}}})\asymp\operatorname*{\mathbb{V}}_{+}({\ell_{\mathsf{LA}}})$,
then for any possible meta-distribution $\mathcal{E}^{\prime}$ defined on the
probability simplex $\mathbb{S}^{c-1}$ we denote
$\mathbb{E}^{\prime}({\ell_{\mathsf{LA}}})$ as the corresponding version of
the loss expectation, then the following inequality holds uniformly for all
$f\in\mathcal{F}$ with probability at least $1-\delta$ over the randomness of
the training data $\mathcal{S}$, and the sampled label distribution
$\mathcal{P}$:

$\displaystyle\mathbb{E}^{{}^{\prime}}({\ell_{\mathsf{LA}}})$
$\displaystyle\lesssim\underbrace{\operatorname*{\hat{\mathbb{E}}}({\ell_{\mathsf{LA}}})+\sqrt{\frac{\mathbb{C}_{1}}{M}\cdot\operatorname*{\hat{\mathbb{V}}}_{+}({\ell_{\mathsf{LA}}})}}_{(1)}+\underbrace{\frac{\|\mathcal{E}-\mathcal{E}^{\prime}\|_{\infty}}{C!}}_{(2)}$
$\displaystyle+\underbrace{\mathbb{C}_{2}\cdot\left(M^{-3/4}+M^{-1/2}N^{-1/4}+N^{-1/2}\right)}_{(3)},$

where $\mathbb{C}_{1},\mathbb{C}_{2}$ are complexity terms of the hypothesis
space $\mathcal{F}$.

The bound can be decomposed into three terms:

Empirical Error Term: The first component (1) in the theorem represents an
empirical error term that can be optimized during training. The implication of
this bound is that employing a semi-variance regularization approach enables
achieving a sharper bound compared to the traditional complexity of
$O(N^{-1/2}+M^{-1/2})$. Our proposed method accomplishes this by optimizing
$\operatorname*{\hat{\mathbb{E}}}({\ell_{\mathsf{LA}}})+\lambda\cdot\operatorname*{\hat{\mathbb{V}}}({\ell_{\mathsf{LA}}})$,
which serves as a smooth approximation of the empirical error term (1).

Approximation Error from Meta-Distribution Shift: The second term (2) provides
an upper bound on the stochastic error that may arise due to a potential shift
from the meta-distribution $\mathcal{E}$ to another distribution
$\mathcal{E}^{\prime}$. Following the insights from (Nguyen et al., 2020,
2023), employing sufficiently large components in the Dirichlet mixture can
reduce the difference $||\mathcal{E}-\mathcal{E}^{\prime}||_{\infty}$ to
nearly zero.

Hierarchical Stochastic Error: The third term (3) quantifies the hierarchical
stochastic error involved in using the sample sets $(\mathcal{S},\mathcal{P})$
instead of the true distributions $(\mathcal{D},\mathcal{E})$. As highlighted,
these results enjoy a sharper residual error compared to conventional ones.

Furthermore, the theorem suggests that in cases where the test label
distribution is not fixed, it is essential to sample a sufficiently large
number of test label distributions (a large $M$) to mitigate the stochastic
error components $M^{-3/4}+M^{-1/2}N^{-1/4}+N^{-1/2}$. This also underlines
the advantage of $\mathsf{DirMixE}$ over existing Mixture of Experts (MoE)
schemes, such as those referenced in (Aimar et al., 2023; Hong et al., 2021;
Zhang et al., 2022), where $M$ is typically fixed as $O(1)$ by using a fixed
distribution assignment.

The second question is how well we can merge the experts during test time. To
explore the answer, we check the performance of the self-supervised model
averaging result $f_{te}$ in (5).

######  Theorem 2 (Model Averaging Error).

Under the same setting as Thm.1, the following results hold:

$\displaystyle\operatorname*{\mathbb{E}}({\ell_{\mathsf{LA}}}(f_{te}))\lesssim$
$\displaystyle\sum_{i\in[K]}\operatorname*{\mathbb{E}}(\omega_{i})\cdot\operatorname*{\mathbb{E}}({\ell_{\mathsf{LA}}}(f^{(i)}))$
$\displaystyle+\sum_{i\in[K]}\mathbb{COV}(\omega_{i},{\ell_{\mathsf{LA}}}(f^{(i)})),$

where $\mathbb{COV}$ is the covariance operator and all the expectations are
taken over the joint distribution of $\mathcal{E}\otimes\mathcal{D}$.

The proof of Thm.2 directly follows (Zhang et al., 2023a) and thus is omitted.

The resulting upper bounds consist of two parts. The first part could be
regarded as a weighted loss, which can be guaranteed to have a similar
concentration as in Thm.2. The second term represents the covariance between
the model weights and the corresponding losses. A well-designed model
aggregation method should ideally assign lower weights to models that yield
higher losses. In this study, we utilize the self-supervised method described
in (Zhang et al., 2022), which effectively maximizes the mutual information
between predictions and ground truth under certain conditions. Consequently,
we anticipate a negative correlation between model weight and loss (negative
covariance), significantly reducing model averaging error.

###  5.2 Upper Bounding Variance with Semi-Variance

In $\mathsf{DirMixE}$, we replace the variance in empirical estimation with
the semi-variance of loss to enhance optimization. As shown in Thm.1, the
stochastic error associated with this approach remains small if
$\operatorname*{\mathbb{V}}({\ell_{\mathsf{LA}}})\asymp\operatorname*{\mathbb{V}}_{+}({\ell_{\mathsf{LA}}})$.
Given that semi-variance is inherently smaller than variance, our analysis
primarily focuses on validating the condition
$\operatorname*{\mathbb{V}}({\ell_{\mathsf{LA}}})\lesssim\operatorname*{\mathbb{V}}_{+}({\ell_{\mathsf{LA}}})$.

Note that, for a well-trained model, there should be a negative correlation
between the probability density and the magnitude of loss. Based on this
assumption, we show that
${\mathbb{V}}(\ell_{\mathsf{LA}})\lesssim{\mathbb{V}}_{+}(\ell_{\mathsf{LA}})$
for certain types of distributions satisfying the negative correlation,
ranging from light-tail (such as the exponential distribution) to heavy-tail
ones (such as the Pareto distribution) distributions. For clarity and
simplicity, we will henceforth use $\ell$ as shorthand for
${\ell_{\mathsf{LA}}}$ in this subsection.

######  Theorem 3.

Let $\rho=\frac{\mathbb{V}_{+}[\ell]}{\operatorname*{\mathbb{V}}[\ell]}$, then
we have the following results for different distributions:

  1. a)

If $\ell$ subjects to an exponential distribution, i.e the p.d.f
$p(\ell)\propto\exp(-c\ell)$, then we have: $\rho\geq\exp(-1)$.

  2. b)

If $\ell$ subjects a Gamma distribution with parameters $\alpha,\beta$, i.e,
the p.d.f $p(\ell)\propto\ell^{\alpha-1}\cdot\exp(-\beta\cdot\ell)$, then we
have: $\rho\geq
1-\alpha\cdot\frac{\Gamma^{\uparrow}(\alpha,\alpha)}{\Gamma(\alpha)}$, where
$\Gamma^{\uparrow}$ is the lower incomplete gamma :
$\Gamma^{\uparrow}(s,x)=\frac{1}{\Gamma(\alpha)}\cdot\int_{0}^{x}t^{s-1}\cdot\exp(-t)dt$.

  3. c)

If $\ell$ subjects to a Pareto distribution with parameter $\theta$, i.e the
p.d.f $p(\ell)\propto(\ell/\ell_{m})^{-\theta}$ for some $\ell_{m}>0$, then we
have:

$\displaystyle\rho=$
$\displaystyle(\theta-1)^{2}\cdot\left[1-\phi(\theta)^{2-\theta}\right]+$
$\displaystyle\theta\cdot(\theta-2)\cdot\left[2\cdot\phi(\theta)^{1-\theta}-\phi(\theta)^{-\theta}-1\right]$

where $\phi(\theta)={\theta}/({\theta-1})$.

(a) Our’s Setting

(b) SADE’s Setting

Figure 4:  Weight Assignment in the Self-supervised Aggregations on CIFAR-100.
F,U,B represent the forward, uniform and backward distributions, see Appendix
F for more.

According to the theorem, we present practical observation on the Gamma and
Pareto distribution in Fig.3-(a). The gamma distributions are tail-shaped when
$\alpha<1$. In this sense, we plot the theoretical lower bound $\rho$ for
$\alpha<1$ in Fig.3-(b). The results show that
$\operatorname*{\mathbb{V}}_{+}/\operatorname*{\mathbb{V}}>0.4$ in most cases.
Similar Fig.3-(c) shows that the Pareto distributions are generally tail-
shaped. We then plot $\rho$ for $2<\theta<10$ in Fig.3-(d). The results show
that the $\operatorname*{\mathbb{V}}_{+}/\operatorname*{\mathbb{V}}$ roughly
resides in $[0.1,0.3]$ when $\theta\geq 3$. Moreover, for the exponential
distribution, we have a universal upper bound for $\rho$ as $\exp(-1)$, which
is greater than $0.2$. In this sense, the proposed claim
$\operatorname*{\mathbb{V}}_{+}\asymp\operatorname*{\mathbb{V}}$ holds for a
wide span of tail-shaped distributions.

Table 1: CIFAR-10-LT (Ours Setting) Method | Forward-LT | Uniform | Backward-LT | Mean
---|---|---|---|---
1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3
LDAM | 89.66 | 90.50 | 90.30 | 74.27 | 74.39 | 74.77 | 60.65 | 59.89 | 60.42 | 74.98(±12.19)
LA | 89.74 | 88.98 | 90.51 | 79.02 | 79.07 | 79.27 | 72.90 | 71.67 | 72.51 | 80.41${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}7.17)}$
VS | 85.12 | 84.71 | 85.24 | 80.69 | 80.50 | 80.85 | 82.10 | 81.21 | 80.95 | 82.37${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}1.92)}$
LADE | 87.31 | 87.11 | 87.79 | 79.69 | 79.72 | 80.20 | 76.79 | 75.77 | 76.47 | 81.21${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}4.62)}$
DDC | 87.07 | 87.07 | 87.24 | 81.62 | 81.44 | 82.03 | 80.15 | 79.04 | 79.47 | 82.79${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}3.20)}$
RIDE | 86.47 | 85.63 | 87.33 | 81.92 | 81.89 | 81.98 | 81.34 | 81.25 | 81.19 | 83.22${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}2.35)}$
SADE | 90.26 | 89.94 | 91.05 | 83.14 | 82.71 | 83.38 | 88.89 | 88.29 | 89.48 | 87.46${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}3.19)}$
BalPoE | 91.30 | 91.54 | 92.72 | 81.58 | 81.78 | 81.89 | 78.97 | 77.28 | 77.87 | 83.88${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}5.86)}$
DirMixE | 90.46 | 89.90 | 91.30 | 83.24 | 82.98 | 83.71 | 89.39 | 88.78 | 88.40 | 87.57${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}3.12)}$
Table 2: Performance Comparison on CIFAR-100-LT (Ours Setting) Method | Forward-LT | Uniform | Backward-LT | Mean
---|---|---|---|---
1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3
LDAM | 64.17 | 63.59 | 66.43 | 38.16 | 37.35 | 38.07 | 17.32 | 15.04 | 16.95 | 39.68(±19.78)
LA | 58.71 | 58.77 | 61.39 | 44.93 | 45.35 | 43.75 | 31.94 | 29.49 | 30.96 | 45.03(±11.81)
VS | 58.20 | 58.30 | 59.99 | 39.32 | 41.24 | 42.13 | 27.37 | 24.53 | 28.14 | 42.14(±13.21)
LADE | 57.42 | 57.76 | 61.06 | 43.35 | 42.92 | 43.05 | 32.40 | 30.34 | 33.47 | 44.64(±11.01)
DDC | 59.26 | 56.89 | 60.90 | 45.05 | 44.86 | 45.59 | 32.59 | 32.05 | 34.41 | 45.73(±10.68)
RIDE | 63.34 | 62.72 | 65.68 | 45.30 | 45.35 | 47.81 | 30.82 | 27.61 | 30.75 | 46.60(±14.02)
SADE | 66.13 | 66.00 | 68.31 | 46.89 | 48.05 | 45.59 | 41.99 | 42.91 | 40.06 | 51.77(±10.90)
BalPoE | 67.75 | 67.80 | 69.98 | 45.05 | 46.86 | 48.81 | 29.80 | 26.32 | 31.17 | 48.17(±16.19)
DirMixE | 66.85 | 66.40 | 69.44 | 47.99 | 49.41 | 44.21 | 44.41 | 47.01 | 44.35 | 53.34(±10.22)
Table 3: ImageNet-LT (Ours Setting) Method | Forward-LT | Uniform | Backward-LT | Mean
---|---|---|---|---
1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3
LDAM | 61.74 | 62.22 | 61.49 | 47.51 | 47.37 | 48.63 | 32.67 | 32.54 | 32.00 | 47.35(±12.02)
LA | 60.94 | 60.32 | 59.78 | 50.82 | 50.86 | 50.86 | 40.39 | 40.16 | 40.14 | 50.47${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}8.22)}$
VS | 61.14 | 59.60 | 59.00 | 52.04 | 52.22 | 53.18 | 44.03 | 44.47 | 43.02 | 52.08${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}6.60)}$
LADE | 63.58 | 62.29 | 61.92 | 53.48 | 52.38 | 53.31 | 41.53 | 42.31 | 41.25 | 52.45${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}8.56)}$
DDC | 59.42 | 59.45 | 58.30 | 51.36 | 51.83 | 51.51 | 42.50 | 44.09 | 43.47 | 51.33${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}6.43)}$
RIDE | 65.32 | 64.28 | 63.49 | 55.18 | 55.02 | 55.98 | 43.49 | 44.52 | 43.16 | 54.49${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}8.47)}$
SADE | 69.64 | 69.77 | 70.35 | 58.51 | 58.96 | 58.69 | 53.54 | 53.13 | 53.82 | 60.71${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}6.86)}$
BalPoE | 69.82 | 69.32 | 70.26 | 58.26 | 58.78 | 58.47 | 52.08 | 51.46 | 52.36 | 60.09${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}7.37)}$
DirMixE | 70.13 | 70.88 | 70.29 | 58.38 | 58.85 | 58.02 | 55.59 | 55.09 | 56.25 | 61.50${}_{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(\pm\phantom{0}6.43)}$

In practical terms, $\mathbb{P}_{te}$ is sampled from a mixture distribution.
Consequently, it is probable that the loss function is subject to a mixture
distribution rather than a single distribution. The following theorem shows
that $\rho$ for a mixture distribution can also be lower bounded by the mean
of the respective $\rho_{i}$ values of its component distributions.

######  Theorem 4.

Let $\ell$ be sampled from a mixture distribution such that
$p(\ell)=\sum_{k=1}^{K}\omega_{k}\cdot p_{k}(\ell)$, where $p_{k}(\ell)$ is
the p.d.f. for the component $k$. Furthermore, for each component, we denote:
$\operatorname*{\mathbb{E}}_{k}[\ell]=\mu_{k},\operatorname*{\mathbb{V}}_{k}[\ell]=\sigma^{2}_{k}$.
Under the assumption that 1)
$\mathbb{P}\left[\ell\neq\operatorname*{\mathbb{E}}[\ell]\right]$ with
probability one w.r.t the mixture distribution, 2)
$\operatorname*{\mathbb{V}}[\ell]/\sigma_{i}^{2}\geq\max\left\\{\frac{\mathbb{V}_{-}[\ell]_{i,j}}{\mathbb{V}_{-}[\ell]_{i}},1\right\\}$,
then $\rho$ can be upper bounded by the average of $\rho_{i}$ in the sense
that:

$\displaystyle\rho\leq\sum_{i}\omega_{i}\cdot\rho_{i},$

where
$\mathbb{V}_{-}[\ell]=\operatorname*{\mathbb{V}}[\ell]-\mathbb{V}_{+}[\ell]$;
$\rho_{i},\mathbb{V}_{-}[\ell]_{i}$ are the corresponding versions of
$\rho,\mathbb{V}_{-}[\ell]$ on the $i$-th component, and

$\displaystyle\mathbb{V}_{-}[\ell]_{i,j}=\int_{0}^{\infty}\left((\ell-\mu_{i})_{-}\right)^{2}\cdot
p_{j}(\ell)\cdot d\ell.$

This implies that controlling $\rho$ is feasible if we can manage each
$\rho_{i}$. Ultimately, this leads to the conclusion that
${\mathbb{V}}(\ell_{\mathsf{LA}})\asymp{\mathbb{V}}_{+}(\ell_{\mathsf{LA}})$
holds under mild conditions.

##  6 Experiments

In this section, we conduct a series of empirical studies to demonstrate the
effectiveness of our proposed algorithm. Due to space limitations, please
refer to Appendix E and F for more details and experiments.

###  6.1 The Choice of meta-distribution and Experts

We briefly introduce the choice of (3) and (4) to define the mixture
distribution. Detailed implementations are shown in the appendix. Drawing
inspiration from the skill-diverse expert learning approach in prior art, we
employ a three-component mixture model for (3) to encapsulate three critical
skills: forward component aligns with the training label distribution,
indicative of performance in the head classes; uniform component corresponds
to the local variation around uniform distribution; backward component
represents the local variation around an inverse long-tail distribution of the
training set, signifying performance in the tail distribution. Please refer to
Appendix E.4 for more details.

(a) Expert 1 (Forward)

(b) Expert 2 (Uniform)

(c) Expert 3 (Backward)

Figure 5:  The Correlation between Expert Weights and Loss.

###  6.2 Experiment Protocols

Evaluation Protocols. We evaluate the performance of various methods across
multiple test datasets. Specifically, we employ two regimes to generate test
datasets: (a) Ours Setting. We generate test data by sampling from the
perturbed version of the meta-distribution in Sec.E. Subsequently, for each
Dirichlet distribution, we sample three label distributions for testing on
three forward/uniform/backward LT distributions, respectively (As in Tab.2).
(b) SADE’s Setting: (Zhang et al., 2022). Following SADE, the test datasets
usually fall into one of three distribution types: (forward) long-tail,
uniform, and backward long-tail, each defined by a different imbalance degree
$\rho$. Please see Appendix E for more details.

###  6.3 Overall Performance

Tab.1-3 compare the overall performance on CIFAR-10, CIFAR-100, ImageNet for
Our’s setting, while those for sade’s setting are shown in Appendix F.
Moreover, we also include the results for iNaturaList in Appdendix.F. For
fairness, we only compare the performance using MoE scheme and do not use
mixup for all the competitors. Moreover, we adopt the self-supervised
aggregation method of SADE to align test-time operations for all the MoE-based
Models (SADE, BalPoE, $\mathsf{DirMixE}$) except RIDE. The rationale for the
exception is that all the experts in RIDE are designed for the same
distribution, and there is already a routing strategy to choose the experts.
We have the following observations on the results:

  1. a)

Overall empirical trends: 1) Our method shows similar performance to state-of-
the-art (SOTA) methods like BalPoE and SADE for Forward-LT and Uniform. 2)
However, in Backward-LT, our method’s improvements are much more substantial.
For instance, in Tab.2 (CIFAR-100, our setting), the performance gain varies
from 2.4 to 4.1. In Tab.3 (ImageNet-LT, our setting), it ranges from 2.0 to
2.4. Thanks to these gains in Backward-LT, our method consistently achieves
the best average performances, demonstrating its effectiveness.

  2. b)

Performance differences across datasets: CIFAR series performances (CIFAR-10,
CIFAR-100) are comparable, likely due to their similar data distributions and
scales. In contrast, the ImageNet dataset, with its distinct data distribution
and scale, shows slightly different trends. Yet, the results still follow the
pattern noted in a). Even though our method slightly lags behind SOTA methods
on the ImageNet dataset for Uniform, the performance differences are mostly
less than 0.5. Conversely, the improvement in Backward distributions is more
significant, ensuring our method maintains the best average performances.

  3. c)

Explaining the differences: The distinct distribution of the ImageNet dataset
compared to CIFAR-10 and CIFAR-100 may account for these discrepancies. The
greater variation between different label distributions means the model must
focus more on Backward distributions, slightly compromising performance in
Uniform and Forward distributions to lead in overall performance.

please see Appdendix F.6 for comparisions with other baselines.

###  6.4 Experts Assignment

In this part, we validate the ability of the test-time self-supervised
aggregation by visualizing the weight assignments for different label
distributions in Fig.4. The forward and backward experts always tend to have a
significant weight for their corresponding distributions. Uniform
distributions tend to utilize all three experts. This is because tail and head
classes are equally crucial for uniform distribution.

###  6.5 Correlation between Weights and Losses

Fig.5 shows the correlation between expert weights of $\mathsf{DirMixE}$
during the test phase and their corresponding loss. We normalize the losses to
align the magnitude of the loss on different distributions, where the
normalized loss of the expert $i$ is $\ell_{i}/\sum_{i=1}^{3}\ell_{i}$. The
results show a strong negative correlation on the forward and backward
experts, and a much weaker positive correlation for uniform ones. This is
because uniform distributions do not have a significant bias on head/tail
classes, producing a relatively stable average performance across different
distributions. Above all, in most cases, we can observe negative correlations
between loss and expert weight. According to Thm.2, the negative correlation
tends to reduce the generalization error of the test-time aggregation scheme,
validating the reasonability of observed performance advantage.

###  6.6 The Semi-Variance/Variance Ratio

Recall Thm.1, we adopt the assumption that
$\operatorname*{\mathbb{V}}({\ell_{\mathsf{LA}}})\asymp
V_{+}({\ell_{\mathsf{LA}}})$. To validate this assumption, we calculate the
semi-variance/variance ratio ($\rho$) in CIFAR-10 and CIFAR-100. We find that
$\rho=0.503,0.509$, respectively for CIFAR-10 and 100, which obviously aligns
with the assumption.

##  7 Conclusion

We consider the hierarchy of the global and local variations of the test label
distributions in test agnostic long-tail recognition. To this end, we propose
a Dirichlet MoE method named $\mathsf{DirMixE}$. The label distributions are
sampled from a meta-distribution, characterized by a mixture of Dirichlet
distribution. In the proposed MoE strategy, each expert is assigned to a local
Dirichlet distribution for a specific skill. The global and local variations
are then captured by inter- and intra-component variations of the meta-
distribution. This also leverages a stable objective function minimizing the
mean and semi-variance of the loss with the help of Monte Carlo method. When
$\operatorname*{\mathbb{V}}_{+}({\ell_{\mathsf{LA}}})\asymp\operatorname*{\mathbb{V}}({\ell_{\mathsf{LA}}})$,
we show that the proposed objective function enjoys an sharper bound by semi-
variance regularization. Finally, extensive experiments demonstrate the
efficacy of $\mathsf{DirMixE}$.

##  8 Broader Impact

This work aims at general issues for the long-tail classification problems. If
applied to fairness-sensitive applications, it might be helpful to improve the
fairness for the minority classes (say specific group of people, minority
species, etc).

##  9 Acknowledgements

This work was supported in part by the National Key R&D Program of China under
Grant 2018AAA0102000, in part by National Natural Science Foundation of China:
62236008, U21B2038, U23B2051, U2001202, 61931008, 62122075 and
61976202,62206264, 92370102, in part by Youth Innovation Promotion Association
CAS, in part by the Strategic Priority Research Program of the Chinese Academy
of Sciences, Grant No. XDB0680000, in part by the Innovation Funding of ICT,
CAS under Grant No.E000000.

## References

  * Aimar et al. (2023) Aimar, E. S., Jonnarth, A., Felsberg, M., and Kuhlmann, M.  Balanced product of calibrated experts for long-tailed recognition.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 19967–19977, 2023.
  * Alshammari et al. (2022) Alshammari, S., Wang, Y., Ramanan, D., and Kong, S.  Long-tailed recognition via weight balancing.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition,_ , pp. 6887–6897, 2022.
  * Cai et al. (2021) Cai, J., Wang, Y., and Hwang, J.  ACE: ally complementary experts for solving long-tailed recognition in one-shot.  In _IEEE/CVF International Conference on Computer Vision_ , pp. 112–121, 2021.
  * Cao et al. (2019) Cao, K., Wei, C., Gaidon, A., Aréchiga, N., and Ma, T.  Learning imbalanced datasets with label-distribution-aware margin loss.  In _Annual Conference on Neural Information Processing Systems_ , pp. 1565–1576, 2019.
  * Cui et al. (2021) Cui, J., Zhong, Z., Liu, S., Yu, B., and Jia, J.  Parametric contrastive learning.  In _IEEE/CVF International Conference on Computer Vision_ , pp. 695–704, 2021.
  * Cui et al. (2023) Cui, J., Zhong, Z., Tian, Z., Liu, S., Yu, B., and Jia, J.  Generalized parametric contrastive learning.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , pp. 1–12, 2023.  doi: 10.1109/TPAMI.2023.3278694.
  * Cui et al. (2019) Cui, Y., Jia, M., Lin, T., Song, Y., and Belongie, S. J.  Class-balanced loss based on effective number of samples.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 9268–9277, 2019.
  * Deng et al. (2009) Deng, J., Dong, W., Socher, R., Li, L., Li, K., and Fei-Fei, L.  Imagenet: A large-scale hierarchical image database.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 248–255, 2009.
  * Duchi & Namkoong (2016) Duchi, J. and Namkoong, H.  Variance-based regularization with convex objectives.  _ArXiv_ , 2016.
  * Galdran et al. (2021) Galdran, A., Carneiro, G., and Ballester, M. Á. G.  Balanced-mixup for highly imbalanced medical image classification.  In _Medical Image Computing and Computer Assisted Intervention_ , pp. 323–333, 2021.
  * Guo & Wang (2021) Guo, H. and Wang, S.  Long-tailed multi-label visual recognition by collaborative training on uniform and re-balanced samplings.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 15089–15098, 2021.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _CVPR_ , pp. 770–778, 2016.
  * Hong et al. (2021) Hong, Y., Han, S., Choi, K., Seo, S., Kim, B., and Chang, B.  Disentangling label distribution for long-tailed visual recognition.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 6622–6632, 2021.
  * Horn et al. (2018) Horn, G. V., Aodha, O. M., Song, Y., Cui, Y., Sun, C., Shepard, A., Adam, H., Perona, P., and Belongie, S. J.  The inaturalist species classification and detection dataset.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 8769–8778, 2018.
  * Kang et al. (2020) Kang, B., Xie, S., Rohrbach, M., Yan, Z., Gordo, A., Feng, J., and Kalantidis, Y.  Decoupling representation and classifier for long-tailed recognition.  In _International Conference on Learning Representations_ , 2020.
  * Kini et al. (2021a) Kini, G. R., Paraskevas, O., Oymak, S., and Thrampoulidis, C.  Label-imbalanced and group-sensitive classification under overparameterization.  In _Annual Conference on Neural Information Processing Systems_ , pp. 18970–18983, 2021a.
  * Kini et al. (2021b) Kini, G. R., Paraskevas, O., Oymak, S., and Thrampoulidis, C.  Label-imbalanced and group-sensitive classification under overparameterization.  In _NIPS_ , volume 34, pp. 18970–18983, 2021b.
  * Krizhevsky et al. (2009) Krizhevsky, A., Hinton, G., et al.  Learning multiple layers of features from tiny images.  pp. 1–60, 2009.
  * Li et al. (2020) Li, Y., Wang, T., Kang, B., Tang, S., Wang, C., Li, J., and Feng, J.  Overcoming classifier imbalance for long-tail object detection with balanced group softmax.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 10988–10997, 2020.
  * Li et al. (2018) Li, Z., Tang, J., and Mei, T.  Deep collaborative embedding for social image understanding.  _IEEE transactions on pattern analysis and machine intelligence_ , 41(9):2070–2083, 2018.
  * Lin et al. (2017) Lin, T., Goyal, P., Girshick, R. B., He, K., and Dollár, P.  Focal loss for dense object detection.  In _IEEE International Conference on Computer Vision_ , pp. 2999–3007, 2017.
  * Liu et al. (2019) Liu, Z., Miao, Z., Zhan, X., Wang, J., Gong, B., and Yu, S. X.  Large-scale long-tailed f.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * Maurer & Pontil (2009) Maurer, A. and Pontil, M.  Empirical bernstein bounds and sample-variance penalization.  In _Conference on Learning Theory_ , 2009.
  * Menon et al. (2021) Menon, A. K., Jayasumana, S., Rawat, A. S., Jain, H., Veit, A., and Kumar, S.  Long-tail learning via logit adjustment.  In _International Conference on Learning Representations_ , 2021.
  * Miao et al. (2021) Miao, Z., Liu, Z., Gaynor, K. M., Palmer, M. S., Yu, S. X., and Getz, W. M.  Iterative human and automated identification of wildlife images.  _Nat. Mach. Intell._ , 3(10):885–895, 2021.
  * Morik et al. (1999) Morik, K., Brockhausen, P., and Joachims, T.  Combining statistical learning with a knowledge-based approach - A case study in intensive care monitoring.  In _International Conference on Machine Learning_ , pp. 268–277, 1999.
  * Nguyen et al. (2023) Nguyen, T., Chamroukhi, F., Nguyen, H. D., and McLachlan, G. J.  Approximation of probability density functions via location-scale finite mixtures in lebesgue spaces.  _Communications in Statistics-Theory and Methods_ , 52(14):5048–5059, 2023.
  * Nguyen et al. (2020) Nguyen, T. T., Nguyen, H. D., Chamroukhi, F., and McLachlan, G. J.  Approximation by finite mixtures of continuous density functions that vanish at infinity.  _Cogent Mathematics & Statistics_, 7(1):1750861, 2020.
  * Rangwani et al. (2022) Rangwani, H., Aithal, S. K., Mishra, M., and R., V. B.  Escaping saddle points for effective generalization on class-imbalanced data.  In _Annual Conference on Neural Information Processing Systems_ , pp. 22791–22805, 2022.
  * Robbins & Monro (1951) Robbins, H. and Monro, S.  A stochastic approximation method.  _The annals of mathematical statistics_ , pp. 400–407, 1951.
  * Tan et al. (2020) Tan, J., Wang, C., Li, B., Li, Q., Ouyang, W., Yin, C., and Yan, J.  Equalization loss for long-tailed object recognition.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 11659–11668, 2020.
  * Tang et al. (2016) Tang, J., Shu, X., Qi, G.-J., Li, Z., Wang, M., Yan, S., and Jain, R.  Tri-clustered tensor completion for social-aware image tag refinement.  _IEEE transactions on pattern analysis and machine intelligence_ , 39(8):1662–1674, 2016.
  * Wang et al. (2021) Wang, X., Lian, L., Miao, Z., Liu, Z., and Yu, S. X.  Long-tailed recognition by routing diverse distribution-aware experts.  In _International Conference on Learning Representations_ , 2021.
  * Wang et al. (2023) Wang, Z., Xu, Q., Yang, Z., He, Y., Cao, X., and Huang, Q.  A unified generalization analysis of re-weighting and logit-adjustment for imbalanced learning.  In _Annual Conference on Neural Information Processing Systems_ , 2023.
  * Xie et al. (2017) Xie, S., Girshick, R., Dollár, P., Tu, Z., and He, K.  Aggregated residual transformations for deep neural networks.  In _CVPR_ , pp. 1492–1500, 2017.
  * Ye et al. (2020) Ye, H., Chen, H., Zhan, D., and Chao, W.  Identifying and compensating for feature deviation in imbalanced deep learning.  _CoRR_ , abs/2001.01385, 2020.
  * Zhang et al. (2020) Zhang, D., Zhang, H., Tang, J., Hua, X.-S., and Sun, Q.  Causal intervention for weakly-supervised semantic segmentation.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), _NeurIPS_ , volume 33, pp. 655–666. Curran Associates, Inc., 2020.
  * Zhang et al. (2023a) Zhang, Q., Wu, H., Zhang, C., Hu, Q., Fu, H., Zhou, J. T., and Peng, X.  Provable dynamic fusion for low-quality multimodal data.  _ICML_ , 2023a.
  * Zhang et al. (2017) Zhang, X., Fang, Z., Wen, Y., Li, Z., and Qiao, Y.  Range loss for deep face recognition with long-tailed training data.  In _IEEE International Conference on Computer Vision_ , pp. 5419–5428, 2017.
  * Zhang et al. (2022) Zhang, Y., Hooi, B., Hong, L., and Feng, J.  Self-supervised aggregation of diverse experts for test-agnostic long-tailed recognition.  In _Annual Conference on Neural Information Processing Systems_ , pp. 34077–34090, 2022.
  * Zhang et al. (2023b) Zhang, Y., Kang, B., Hooi, B., Yan, S., and Feng, J.  Deep long-tailed learning: A survey.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 45(9):10795–10816, 2023b.
  * Zhong et al. (2019) Zhong, Y., Deng, W., Wang, M., Hu, J., Peng, J., Tao, X., and Huang, Y.  Unequal-training for deep face recognition with long-tailed noisy data.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 7812–7821, 2019.
  * Zhong et al. (2023) Zhong, Z., Cui, J., Yang, Y., Wu, X., Qi, X., Zhang, X., and Jia, J.  Understanding imbalanced semantic segmentation through neural collapse.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 19550–19560, 2023.
  * Zhou et al. (2020) Zhou, B., Cui, Q., Wei, X., and Chen, Z.  BBN: bilateral-branch network with cumulative learning for long-tailed visual recognition.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 9716–9725, 2020.
  * (45) Zhu, J., Wang, Z., Chen, J., Chen, Y. P., and Jiang, Y.  Balanced contrastive learning for long-tailed visual recognition.  In _CVPR_ , pp. 6898–6907.

dasdsa

## Contents

[sections] [sections]l1

##  Appendix A Detailed Explanation of the Sampling process

In our study, we aim to ensure good overall performance across the entire meta
distribution $\mathcal{E}$ of label distributions. Since our access is limited
to training data with a long-tailed distribution, we employ the Logit
Adjustment (LA) loss to tailor the model for specific test-label distributions
using only training data. Our objectives are to 1) construct a meta-
distribution $\mathcal{E}$ for test-label distributions, 2) assess the loss
for different test-label distributions in $\mathcal{E}$, and 3) maintain
minimal change in the mean and variance of the loss over $\mathcal{E}$. For
1), we model $\mathcal{E}$ as a Dirichlet mixture distribution, representing
global and local variations through the randomness across and within its
components, respectively. The Monte Carlo method is vital for implementing 2)
and 3), detailed further in below.

We have to deal with both the training data distribution and a meta-
distribution for test-label distribution, leading to a hierarchical process
for the calculation:

Layer 1: For a given test-label distribution $\mathbb{P}_{te}$, we measure a
model’s adaptability to this new distribution through the expected LA loss
over training data parametrized by $\mathbb{P}_{te}$:

$\hat{\ell}_{\mathsf{LA}}(f,\mathbb{P}_{te})\approx\frac{1}{N}\cdot\sum_{i=1}^{N}\ell_{\mathsf{LA}}(f_{\theta}(x_{i}),y_{i};\mathbb{P}_{te}),$

where $x_{i},y_{i}$ represent the $i$-th instance’s feature and label in the
training data.

Layer 2: Across various $\mathbb{P}_{te}$s, we calculate the mean and variance
of $\ell_{\mathsf{LA}}(f,\mathbb{P}_{te})$ over meta-distribution
$\mathcal{E}$, represented as

$\mathbb{E}_{\mathbb{P}_{te}\sim\mathcal{E}}\left[\hat{\ell}_{\mathsf{LA}}(f;\mathbb{P}_{te})\right],~{}\mathbb{V}_{\mathbb{P}_{te}\sim\mathcal{E}}\left[\hat{\ell}_{\mathsf{LA}}(f;\mathbb{P}_{te})\right],$

respectively.

To minimize both the mean and variance of the loss over $\mathcal{E}$, we
employ the following objective:

$\mathbb{E}_{\mathbb{P}_{te}\sim\mathcal{E}}\left[\hat{\ell}_{\mathsf{LA}}(f;\mathbb{P}_{te})\right]+\lambda\cdot\mathbb{V}_{\mathbb{P}_{te}\sim\mathcal{E}}\left[\hat{\ell}_{\mathsf{LA}}(f;\mathbb{P}_{te})\right],$

where $\lambda$ is a balancing coefficient.

Given the model $f$ as a neural network, we can’t obtain the mean and variance
in the closed-form. Instead, we have to approximate the mean and variance for
layer 2 using the Monte Carlo method, sampling a finite number of test
distributions $\mathbb{P}_{te}$ from $\mathcal{E}$ and then do the estimation.

Our training pipeline, based on the Monte Carlo method, includes:

\- a) Sampling a set of test-label distributions from the Dirichlet mixture
distribution $\\{(\mathbb{P}_{j},\xi_{j})\\}_{i=1}^{M}$, where
$\mathbb{P}_{j}$ is the sampled test-label-distribution, and $\xi_{j}$
indicates its component. \- b) Evaluating the empirical LA loss for each
$\mathbb{P}_{j}$ on the training data, adjusting the label distribution
accordingly, then computing the mean and (semi-)variance of these losses. \-
c) Training the model using backpropagation (BP).

Next, we outline each step of our process.

###  A.1 Step a)

In the main paper, we defined the meta distribution $\mathcal{E}$ as a
Dirichlet mixture distribution:

$\mathbb{P}_{te}|\xi\sim\mathsf{Dir}\left({\alpha}^{(\xi)}\right),$

$\xi|\boldsymbol{p}\sim\mathsf{Discrete}\left(p_{1},\cdots,p_{K}\right).$

To sample a test distribution $\mathbb{P}_{te}$, we first select a Dirichlet
component $\xi$ from $K$ options based on the discrete probability
$\left(p_{1},\cdots,p_{K}\right)$. We then sample $\mathbb{P}_{te}$ from the
$\xi$-th component $\mathsf{Dir}\left({\alpha}^{(\xi)}\right)$. This process
repeats to generate a set of distributions
$\\{\mathbb{P}_{j},\xi_{j}\\}_{i=1}^{M}$.

###  A.2 Step b)

For each pair $(\mathbb{P}_{j},\xi_{j})$, we then calculate the loss. In our
Mixture of Experts (MOE) strategy, the expert $\xi_{j}$ is assigned to its
corresponding Dirichlet distribution component, and we train
$f_{\theta}^{(\xi_{j})}$ for this task. With this assignment,, we get the
empirical LA loss average on the training data:
$\hat{\ell}_{\mathsf{LA}}(f^{(\xi_{j})};\mathbb{P}_{j})$ for this specific
test-label distribution. Repeating the calculate for each
$(\mathbb{P}_{j},\xi_{j})$, we can then obtain the empirical mean and variance
of $\hat{\ell}_{\mathsf{LA}}(f^{(\xi_{j})};\mathbb{P}_{j})$ as:

$\hat{\mathbb{E}}(\hat{\ell}_{\mathsf{LA}})=\frac{1}{M}\sum_{j=1}^{M}\hat{\ell}_{\mathsf{LA}}(f^{(\xi_{j})};\mathbb{P}_{j}),$

$\hat{\mathbb{V}}(\hat{\ell}_{\mathsf{LA}})=\frac{1}{M}\sum_{j=1}^{M}\left(\hat{\ell}_{\mathsf{LA}}(f^{(\xi_{j})};\mathbb{P}_{j})-\hat{\mathbb{E}}\left(\hat{\ell}_{\mathsf{LA}}(f^{(\xi_{j})};\mathbb{P}_{j})\right)\right)^{2}.$

Moreover, we find that the variance regularization tends to punish loss
functions smaller than its mean. We use semi-variance regularization, which
only penalizes loss deviations larger than the mean, as a surrogate to avoid
penalizing the smaller-than-mean losses:

$\hat{\mathbb{V}}_{+}(\hat{\ell}_{\mathsf{LA}})=\frac{1}{M}\sum_{j=1}^{M}\left(\left(\hat{\ell}_{\mathsf{LA}}(f^{(\xi_{j})};\mathbb{P}_{j})-\hat{\mathbb{E}}\left(\hat{\ell}_{\mathsf{LA}}(f^{(\xi_{j})};\mathbb{P}_{j})\right)\right)_{+}\right)^{2}.$

###  A.3 Step c)

We perform backpropagation (BP) based on the loss and train the MOE model.

Putting altogther, we summarize this procedure as the following algorithm.

Algorithm 1 Training Algorithm

0: Batch size $bs$, Dirichlet components
$\bm{\alpha}^{(1)},\bm{\alpha}^{(2)},\cdots,\bm{\alpha}^{(K)}$

0: Trained models $f_{\theta}^{(1)},f_{\theta}^{(2)},\cdots,f_{\theta}^{(K)}$

1: for $j\leftarrow 1$ to $M$ do

2: $\xi_{j}\leftarrow\text{RandomInteger}(1,K)$ with probability
$(p_{1},\cdots,p_{K})$

3: Sample $\mathbb{P}_{j}$ from Dirichlet Distribution
$Dir(\bm{\alpha}^{(\xi_{j})})$

4: Add sampled pair $(\mathbb{P}_{j},\xi_{j})$ to the test-label-distribution
set $\mathcal{P}$.

5: end for

6: while not converged do

7: Sample training data Batch $B$

8: Sample a subset $\mathcal{P}^{\prime}$ from $\mathcal{P}$

9: for each $(\mathbb{P}_{j},\xi_{j})\in\mathcal{P}^{\prime}$ do

10: Calculate $\hat{\ell}_{LA_{j}}=\frac{1}{bs}\sum_{(\bm{x},y)\in
B_{i}}\hat{\ell}_{LA}(f_{\theta}^{(\xi_{j})}(\bm{x}),y;\mathbb{P}_{j})$

11: end for

12: Calculate the mean $\hat{\mathbb{E}}(\ell_{\mathsf{LA}})$ and semi-
variance $\hat{\mathbb{V}}_{+}(\ell_{\mathsf{LA}})$

13: Calculate the objective function
$L\leftarrow\hat{\mathbb{E}}(\ell_{\mathsf{LA}})+\lambda\cdot\hat{\mathbb{V}}_{+}(\ell_{\mathsf{LA}})$

14: Perform SGD with respect to $L$ to update the model

15: end while

16: return $f_{\theta}^{(1)},f_{\theta}^{(2)},\cdots,f_{\theta}^{(K)}$

##  Appendix B Proof for the Upper Bound of $\rho$

###  B.1 Proof for Thm.1

###### Proof.

1): For exponential distribution, we have:

$\displaystyle
p_{\lambda}(\ell)=\lambda\cdot\exp(-\lambda\cdot\ell),~{}~{}\operatorname*{\mathbb{E}}_{\lambda}[\ell]=\frac{1}{\lambda},\operatorname*{\mathbb{V}}[\ell]_{\lambda}=\frac{1}{\lambda^{2}}.$

In this sense, we have:

$\displaystyle\operatorname*{\mathbb{V}}[\ell]-\mathbb{V}_{+}[\ell]$
$\displaystyle=\int_{0}^{1/\lambda}(\ell-\frac{1}{\lambda})^{2}\cdot
p_{\lambda}(\ell)\cdot d\ell$
$\displaystyle\leq\frac{1}{\lambda^{2}}\cdot\mathbb{P}\left[\ell<\frac{1}{\lambda}\right]$
$\displaystyle\leq\frac{1-\exp(-1)}{\lambda^{2}}$

Hence:

$\displaystyle\frac{\mathbb{V}_{+}[\ell]}{\operatorname*{\mathbb{V}}[\ell]}\geq
1-(1-\exp(-1))=\exp(-1)$

2): For the gamma distribution, we have:

$\displaystyle
p_{\alpha,\beta}(\ell)=\frac{\beta^{\alpha}}{\Gamma(\alpha)}\cdot\ell^{\alpha-1}\cdot\exp(-\beta\cdot\ell),~{}\operatorname*{\mathbb{E}}[\ell]=\frac{\alpha}{\beta},~{}\operatorname*{\mathbb{V}}[\ell]=\frac{\alpha}{\beta^{2}}.$

Similarly, we have:

$\displaystyle\operatorname*{\mathbb{V}}[\ell]-\mathbb{V}_{+}[\ell]$
$\displaystyle=\int_{0}^{\alpha/\beta}(\ell-\alpha/\beta)^{2}\cdot
p_{\alpha,\beta}(\ell)\cdot d\ell$
$\displaystyle\leq\left(\frac{\alpha}{\beta}\right)^{2}\cdot\frac{1}{\Gamma(\alpha)}\cdot\int_{0}^{\alpha/\beta}(\beta\cdot\ell)^{\alpha-1}\cdot\exp(-\beta\cdot\ell)\cdot
d(\beta\cdot\ell)$
$\displaystyle=\left(\frac{\alpha}{\beta}\right)^{2}\cdot\frac{1}{\Gamma(\alpha)}\cdot\int_{0}^{\alpha}(\ell)^{\alpha-1}\cdot\exp(-\ell)\cdot
d(\ell)$
$\displaystyle=\left(\frac{\alpha}{\beta}\right)^{2}\cdot\frac{\Gamma^{\uparrow}(\alpha,\alpha)}{\Gamma(\alpha)}$

Then we have:

$\displaystyle\frac{\mathbb{V}_{+}[\ell]}{\operatorname*{\mathbb{V}}[\ell]}\geq
1-\alpha\cdot\frac{\Gamma^{\uparrow}(\alpha,\alpha)}{\Gamma(\alpha)}$

3): For a Pareto distribution: we have

$\displaystyle
p_{\theta}(\ell)=\begin{cases}\frac{\theta\ell_{m}^{\theta}}{\ell^{\theta+1}},&\ell\geq\ell_{m},\\\
0,&\ell\leq\ell_{m}\end{cases},~{}\operatorname*{\mathbb{E}}[\ell]=\begin{cases}\infty,&\theta\leq
1,\\\
\frac{\theta}{\theta-1}\ell_{m},&\theta>1\end{cases},\operatorname*{\mathbb{V}}[\ell]=\begin{cases}\infty,&\theta\leq
2,\\\
\nicefrac{{\theta}}{{(\theta-1)^{2}\cdot(\theta-2)}}\cdot\ell_{m}^{2},&\theta>2\end{cases}$

In this sense, we have:

$\displaystyle\mathbb{V}_{+}[\ell]$
$\displaystyle=\int_{\ell_{m}}^{\frac{\theta}{\theta-1}\cdot\ell_{m}}\left(\ell-\frac{\theta}{\theta-1}\cdot\ell_{m}\right)^{2}\cdot\frac{\theta\ell_{m}^{\theta}}{\ell^{\theta+1}}d\ell$
$\displaystyle=\int_{\ell_{m}}^{\frac{\theta}{\theta-1}\cdot\ell_{m}}\frac{\theta\ell_{m}^{\theta}}{\ell^{\theta-1}}d\ell~{}-~{}2\cdot\int_{\ell_{m}}^{\frac{\theta}{\theta-1}\cdot\ell_{m}}\frac{\theta\cdot\ell_{m}^{\theta+1}}{(\theta-1)\cdot\ell^{\theta-1}}d\ell~{}+~{}\left(\frac{\theta}{\theta-1}\cdot\ell_{m}\right)^{2}\cdot\int_{\ell_{m}}^{\frac{\theta}{\theta-1}\cdot\ell_{m}}\frac{\theta\ell_{m}^{\theta}}{\ell^{\theta+1}}d\ell$

$\displaystyle\int_{\ell_{m}}^{\frac{\theta}{\theta-1}\cdot\ell_{m}}\frac{\theta\ell_{m}^{\theta}}{\ell^{\theta-1}}d\ell~{}=~{}\frac{\theta}{\theta-2}\cdot\ell_{m}^{2}\cdot\left[1-\left(\frac{\theta}{\theta-1}\right)^{2-\theta}\right]$
$\displaystyle
2\cdot\int_{\ell_{m}}^{\frac{\theta}{\theta-1}\cdot\ell_{m}}\frac{\theta\cdot\ell_{m}^{\theta+1}}{(\theta-1)\cdot\ell^{\theta-1}}\cdot
d\ell~{}=~{}2\cdot\left(\frac{\theta}{\theta-1}\cdot\ell_{m}\right)^{2}\cdot\left[1-\left(\frac{\theta}{\theta-1}\right)^{1-\theta}\right]$
$\displaystyle\left(\frac{\theta}{\theta-1}\cdot\ell_{m}\right)^{2}\cdot\int_{\ell_{m}}^{\frac{\theta}{\theta-1}\cdot\ell_{m}}\frac{\theta\ell_{m}^{\theta}}{\ell^{\theta+1}}d\ell~{}=~{}\left(\frac{\theta}{\theta-1}\cdot\ell_{m}\right)^{2}\cdot\left[1-\left(\frac{\theta}{\theta-1}\right)^{\theta}\right]$

Above all, we come to the conclusion:

$\displaystyle\frac{\mathbb{V}_{+}[\ell]}{\operatorname*{\mathbb{V}}[\ell]}=(\theta-1)^{2}\cdot\left[1-\left(\frac{\theta}{\theta-1}\right)^{2-\theta}\right]+\theta\cdot(\theta-2)\cdot\left[2\cdot\left(\frac{\theta}{\theta-1}\right)^{1-\theta}-\left(\frac{\theta-1}{\theta}\right)^{\theta}-1\right]$

∎

###  B.2 Proof for Thm.2

######  Lemma 1.

The function $f(x)=\left((x)_{-}\right)^{2}$ is a convex for $x\neq 0$.

###### Proof.

Denote $f_{1}(x)=x^{2},f_{2}(x)=(x)_{-}$, then we have:

$\displaystyle f^{\prime\prime}(x)=f^{\prime\prime}_{2}(x)\cdot
f^{\prime}_{1}(f_{2}(x))+f^{\prime\prime}_{1}(f_{2}(x))\cdot(f^{\prime}_{2}(x))^{2}=\begin{cases}0,&x>0\\\
2,&x<0.\end{cases}$

Obviously, we have $f^{\prime\prime}(x)\geq 0$. The proof is thus finished.

∎

###### Proof.

We consider a mixture distribution of K-components with a p.d.f function

$\displaystyle p_{m}(\ell)=\sum_{k=1}^{K}\omega_{k}\cdot p_{k}(\ell),$

where $p_{k}(\ell)$ is the p.d.f. for the $k$-th component, and $\omega_{k}$
is probability to observe the $k$-th component. In this sense, we have:

$\displaystyle\operatorname*{\mathbb{E}}[\ell]=\sum_{k=1}^{K}\omega_{k}\cdot\mu_{k},~{}\operatorname*{\mathbb{V}}[\ell]\overset{(a)}{\geq}\sum_{k=1}^{K}\omega_{k}\cdot\sigma^{2}_{k}.$

where $\mu_{k},\sigma^{2}_{k}$ are the corresponding means and variance given
the component $k$. Here $(a)$ follows from the total law of variance.

In this sense, we can bound the semi-variance as:

$\displaystyle\mathbb{V}_{-}[\ell]$
$\displaystyle=\int_{0}^{\infty}\left((\ell-\operatorname*{\mathbb{E}}[\ell])_{-}\right)^{2}\cdot
p_{m}(\ell)\cdot d\ell$
$\displaystyle=\int_{0}^{\infty}\left((\ell-\sum_{k=1}^{k}\omega_{k}\cdot\mu_{k})_{-}\right)^{2}\cdot
p_{m}(\ell)\cdot d\ell$
$\displaystyle\overset{(*)}{\leq}\sum_{k=1}^{k}\omega_{k}\cdot\int_{0}^{\infty}\left((\ell-\mu_{k})_{-}\right)^{2}\cdot
p_{m}(\ell)\cdot d\ell$
$\displaystyle=\sum_{i,j}\omega_{i}\cdot\omega_{j}\cdot\int_{0}^{\infty}\left((\ell-\mu_{i})_{-}\right)^{2}\cdot
p_{j}(\ell)\cdot d\ell$ $\displaystyle 1-\rho$
$\displaystyle~{}{\leq}\frac{1}{\operatorname*{\mathbb{V}}[\ell]}\cdot\left(\sum_{i,j}\omega_{i}\cdot\omega_{j}\cdot\int_{0}^{\infty}\left((\ell-\mu_{i})_{-}\right)^{2}\cdot
p_{j}(\ell)\cdot d\ell\right)$
$\displaystyle~{}\overset{(**)}{\leq}\sum_{i,j}\left(\omega_{i}\cdot\omega_{j}\cdot\int_{0}^{\infty}\left((\ell-\mu_{i})_{-}\right)^{2}\cdot
p_{i}(\ell)\cdot d\ell\cdot\frac{1}{\sigma_{i}^{2}}\right)$
$\displaystyle~{}\leq\sum_{i}\omega_{i}\cdot\frac{\mathbb{V}_{-}[\ell]_{i}}{\operatorname*{\mathbb{V}}[\ell]_{i}}$

$(*)$ is from the fact that $((\cdot)_{-})^{2}$ is a convex function when
$x\neq 0$, and that $(**)$ is from the assumption that:

$\displaystyle\frac{\mathbb{V}_{-}[\ell]_{i,j}}{\mathbb{V}_{-}[\ell]_{i}}\leq\frac{\operatorname*{\mathbb{V}}[\ell]}{\sigma_{i}^{2}},~{}\frac{\operatorname*{\mathbb{V}}[\ell]}{\sigma_{i}^{2}}>1$

which further implies that

$\displaystyle\frac{1}{\operatorname*{\mathbb{V}}[\ell]}\cdot{\int_{0}^{\infty}\left((\ell-\mu_{i})_{-}\right)^{2}\cdot
p_{j}(\ell)\cdot
d\ell}\leq\frac{1}{\sigma_{i}^{2}}\cdot{\int_{0}^{\infty}\left((\ell-\mu_{i})_{-}\right)^{2}\cdot
p_{i}(\ell)\cdot d\ell}$

It thus becomes clear that:

$\displaystyle\rho$ $\displaystyle=1-(1-\rho)$
$\displaystyle\overset{(***)}{\geq}1-\sum_{i}\omega_{i}\cdot\frac{\mathbb{V}_{-}[\ell]_{i}}{\operatorname*{\mathbb{V}}[\ell]_{i}}$
$\displaystyle=\sum_{i}\omega_{i}-\sum_{i}\omega_{i}\cdot\frac{\mathbb{V}_{-}[\ell]_{i}}{\operatorname*{\mathbb{V}}[\ell]_{i}}$
$\displaystyle=\sum_{i}\omega_{i}\cdot\left(1-\frac{\mathbb{V}_{-}[\ell]_{i}}{\operatorname*{\mathbb{V}}[\ell]_{i}}\right)$
$\displaystyle=\sum_{i}\omega_{i}\cdot\left(1-(1-\rho_{i})\right)$
$\displaystyle=\sum_{i=1}^{K}\omega_{i}\cdot\rho_{i}$

Here $(***)$ is from the proven fact that
$1-\rho~{}\leq~{}\sum_{i}\omega_{i}\cdot\frac{\mathbb{V}_{-}[\ell]_{i}}{\operatorname*{\mathbb{V}}[\ell]_{i}}$

∎

##  Appendix C Explanations for the Theoretical Results

Basic Notations: In our approach, we use a natural training dataset consisting
of images and their labels from the distribution $\mathcal{D}$, and a
constructed set of potential test-label distributions from $\mathcal{E}$. We
denote the training dataset as $\mathcal{S}$ and the constructed set as
$\mathcal{P}$. Additionally, the training sample size is $N$ and the
constructed set size is $M$.

Our primary theoretical findings relate to how well our method generalizes to
new, unseen test-label distributions. According to standard learning theory,
we measure generalization error by the difference between a) the expected
error across the joint distribution of test-label and training data, and b)
the empirical average across the sampled $\mathcal{S}$ and $\mathcal{P}$. This
difference results from stochastic errors in sampling and estimation.
Reflecting on the previous question, the Monte Carlo process incorporates a
hierarchical sampling approach, also leading to a hierarchical structure of
stochastic errors, a significant challenge in our theoretical analysis. This
explain this below.

###  C.1 Stochastic Errors

Inner Layer (training data): For a specific test label distribution
$\mathbb{P}_{i}$ in $\mathcal{P}$, we define
$\ell_{\mathcal{D},\mathcal{E},i}$ and $\ell_{\mathcal{S},\mathcal{E},i}$ as
the expected loss on training distribution $\mathcal{D}$ and the empirical
average loss on training data $\mathcal{S}$, respectively:

$\ell_{\mathcal{D},\mathcal{E},i}=\mathbb{E}_{(x,y)\sim\mathcal{D}}\left[\ell_{\mathsf{LA}}(f^{(\xi_{i})}(x),y;\mathbb{P}_{i})\right]$

$\ell_{\mathcal{S},\mathcal{E},i}=\frac{1}{N}\sum_{j=1}^{N}\ell_{\mathsf{LA}}(f^{(\xi_{i})}(x_{j}),y_{j};\mathbb{P}_{i})$

These values estimate the error of the inner layer concerning the training
data, specifically measuring the discrepancy when substituting expectation
with empirical average for a given test-label distribution $\mathbb{P}_{i}$.

Outer Layer (test label distributions): We also consider the expectation over
the meta-distribution $\mathcal{E}$ to assess the outer Monte Carlo sampling
error.

In practical training, we rely on Monte Carlo estimation results and finite
training data to compute the empirical average:

$\hat{\mathbb{E}}_{\mathcal{\mathcal{E}}}\left[\ell_{\mathcal{S},\mathcal{E},i}\right]=\frac{1}{NM}\sum_{i=1}^{M}\sum_{j=1}^{N}\ell_{\mathsf{LA}}(f^{(\xi_{i})}(x_{j}),y_{j};\mathbb{P}_{i})$

But Theoretically, the genearlization error should be measured by the expected
loss on the joint distribution of test label distribution
$\mathcal{E}^{\prime}$ (which could differ from $\mathcal{E}$ used in
training) and training data $\mathcal{D}$, expressed as:

${\mathbb{E}}_{\mathbb{P}\sim\mathcal{\mathcal{E}^{\prime}}}\left[\ell_{\mathcal{D},\mathcal{E}^{\prime},i}\right]=\mathbb{E}_{\mathbb{P}\sim\mathcal{E}^{\prime}}\left[\mathbb{E}_{(x,y)\sim\mathcal{D}}\left[\ell_{\mathsf{LA}}(f^{(\xi)}(x),y;\mathbb{P})\right]\right]$

Finally, we discuss the upper bound of the generalization error and briefly
introduce the proof’s key idea.

### Error Decomposition

Assume that our model is chosen from a hypothesis space $\mathcal{F}$ (for
instance, CNNs within certain weight norm limits). The generalization ability
of the entire hypothesis set is often measured by the worst-case performance
gap:

$\Delta=\sup_{f\in\mathcal{F}}\left[{\mathbb{E}}_{\mathbb{P}\sim\mathcal{\mathcal{E}^{\prime}}}\left[\ell_{\mathcal{D},\mathcal{E}^{\prime},i}\right]-\hat{\mathbb{E}}_{\mathcal{\mathcal{E}}}\left[\ell_{\mathcal{S},\mathcal{E},i}\right]\right].$

Analyzing this error directly is challenging due to its hierarchical nature.
Nevertheless, we can further derive an upper bound by summing three types of
error:

  1. i)

Meta-distribution Approximation Error: This error arises from approximating
the ideal meta-distribution $\mathcal{E}^{\prime}$ with $\mathcal{E}$,
expressed as:

$\sup_{f\in\mathcal{F}}\left[{\mathbb{E}}_{\mathbb{P}\sim\mathcal{\mathcal{E}^{\prime}}}\left[\ell_{\mathcal{D},\mathcal{E}^{\prime},i}\right]-{\mathbb{E}}_{\mathbb{P}\sim\mathcal{\mathcal{E}}}\left[\ell_{\mathcal{D},\mathcal{E},i}\right]\right].$

  2. ii)

Label Dist: This error stems from the approximation of the expected values
over $\mathcal{E}$ with a Monte Carlo average, which can be shown as:

$\sup_{f\in\mathcal{F}}\left[{\mathbb{E}}_{\mathbb{P}\sim\mathcal{\mathcal{E}}}\left[\ell_{\mathcal{D},\mathcal{E},i}\right]-\frac{1}{M}\sum_{i=1}^{M}\ell_{\mathcal{D},\mathcal{E},i}\right].$

  3. iii)

Data Estimation Error: This error is due to approximating the expectation over
the training distribution $\mathcal{D}$ with the empirical average from the
training data $S$:

$\sup_{f\in\mathcal{F}}\left[{\mathbb{E}}_{\mathbb{P}\sim\mathcal{\mathcal{E}}}\left[\frac{1}{M}\sum_{i=1}^{M}\ell_{\mathcal{D},\mathcal{E},i}-\frac{1}{M}\sum_{i=1}^{M}\ell_{\mathcal{S},\mathcal{E},i}\right]\right].$

###  C.2 Key Idea of the Proof:

From the error decomposition i)-iii) above, we outline an overall limit for
the generalization gap $\Delta$.

\- For i), we establish an upper bound using the loss function’s boundedness,
the probability simplex’s volume, and the largest variation between two label
distributions (measured by the inf-norm $\|\cdot\|_{\infty}$).

\- For ii), the most complex part of this proof, we extend the Bernstein-type
concentration bounds to upper bound the error with the empirical semi-variance
from our objective function. This approach shows how the objective function
directly enhances generalization.

\- For iii), we translate this into the uniform convergence bound, where the
covering number indicates the hypothesis class’s complexity.

##  Appendix D Proof for Overall Generalization Upper Bound

###  D.1 Basic Definitions of The Hypothesis Class

The Hypothesis Class. In this paper, we consider the Generalization ability
based on the employed architecture. This means that we only consider models
chosen from the following hypothesis class $\mathcal{F}$:

$\displaystyle\mathcal{F}=\left\\{\mathbb{R}^{C}\leftarrow\mathbb{R}^{d}:f^{(i)}_{\theta}(\cdot)=g^{(i)}\circ\psi(\cdot),i\in[K].,~{}g^{(i)},\psi~{}\text{are
chosen from specific subclass of deep neural networks}.\right\\}$

Note that since $f^{(i)}_{\theta}$ are scoring functions for multi-class
classification problems, they must be vector-valued functions. For the sake of
simplicity, we will use $f(x)$ under this context to denote the collection
$\\{f^{(i)}_{\theta}\\}_{i\in[K]}$. We use $f\in\mathcal{F}$ to express
choosing one such collections out of $\mathcal{F}$.

The Norm of Hypotheses. To measure the complexity of $\mathcal{F}$, we must
define a norm on each hypothesis $f$. To do this, we adopt the overall
infinity norm (over all K subbranches, all $C$ classes, and all input features
$x\in\mathcal{X}$ ):

$\displaystyle\|f\|_{\infty}=\max_{i\in[K]}\max_{j\in\\{1,2,\cdots,C\\}}\sup_{\bm{x}\in\mathcal{X}}\left|f^{(i)}_{\theta,j}(\bm{x})\right|.$

Here $f^{(i)}_{\theta,j}(\bm{x})$ means the output score of the $i$-th branch
and $j$-th (channel) for feature $\bm{x}$. It is easy to check that the new
infinity norm is also a norm.

Measuring Complexity with Covering Number. Given a functional class
$\mathcal{F}$, we can use the covering number
$\mathcal{N}_{\infty}(\mathcal{F},\epsilon,n)$ to measure its corresponding
complexity with the following definition.

$\displaystyle\mathcal{N}_{\infty}(\mathcal{F},\epsilon,n)=\sup_{\bm{x}\in\mathcal{X}^{n}}\mathcal{N}(\epsilon,\mathcal{F},||\cdot||_{\infty})$

where $\mathcal{N}(\epsilon,\mathcal{F},||\cdot||_{\infty})$ is the smallest
number of infinity norm open balls, denoted as $N_{o}$, such that there exist
$N_{o}$ open balls that covers entire class $\mathcal{F}$. In other words,
$\exists~{}\mathcal{B}_{i}\subseteq\mathcal{F}$, such that
$\mathcal{F}\subseteq\bigcup_{i=1}^{N_{o}}\mathcal{B}_{i}$, where
$\mathcal{B}_{i}=\\{f:\|f-f_{i}\|_{\infty}\leq\epsilon\\}$.

In the proof, we will the following lemmas to as basic tools.

###  D.2 Fundamental Inequalities

######  Lemma 2.

The volume of an $c$-dimensional probability simplex is $c!$. In other words,
we have:

$\displaystyle V_{c}=\int\limits_{\sum_{i=1}^{c}x_{i}=1}1\cdot dx_{1}\cdot
dx_{2}\cdots dx_{c}=\frac{1}{c!}$

###### Proof.

We proof it by induction.

Base Case, c=1 Obviously, we have:

$\displaystyle V_{1}=\int_{0}^{1}dx=1.$

Induction Supposes that $V_{i-1}=(i-1)!$, we have:

$\displaystyle V_{i}$ $\displaystyle=\int\limits_{\sum_{j=1}^{i}x_{j}=1}1\cdot
dx_{1}\cdot dx_{2}\cdots dx_{i}$
$\displaystyle=\int_{0}^{1}\left(\int\limits_{\sum_{j=1}^{i-1}x_{j}=1-x_{i}}1\cdot{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}dx_{1}\cdot
dx_{2}\cdots dx_{i-1}}\right)dx_{i}$
$\displaystyle\overset{\color[rgb]{0.97265625,0.6328125,0.26953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.97265625,0.6328125,0.26953125}u_{j}=x_{j}/(1-x_{i}),j=1,2,\cdots,i-1}{=}\int_{0}^{1}(1-x_{i})^{i-1}\cdot\left(\int\limits_{\sum_{j=1}^{i-1}u_{j}=1}1\cdot{\color[rgb]{0.97265625,0.6328125,0.26953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.97265625,0.6328125,0.26953125}du_{1}\cdot
du_{2}\cdots du_{i-1}}\right)dx_{i}$
$\displaystyle=V_{i-1}\cdot\int_{0}^{1}(1-x_{i})^{i-1}dx_{i}$
$\displaystyle=(1/i)\cdot V_{i-1}$ $\displaystyle=1/i!$

The proof is then completed by expanding the induction recursively. ∎

######  Lemma 3.

When $g(\cdot)$ is Lipschitz continuous, the following holds:

$\|g(x)-g(\tilde{x})\|_{\infty}\leq\sup\|\nabla_{x}g\|_{p}\cdot\|x-\tilde{x}\|_{q},$
(6)

where $\frac{1}{p}+\frac{1}{q}=1$.

###### Proof.

$\displaystyle|g(x)-g(\tilde{x})|$
$\displaystyle=~{}\left|\int_{0}^{1}\left\langle\nabla g(\tau
x+(1-\tau)\tilde{x}),x-\tilde{x}\right\rangle d\tau\right|$ (7)
$\displaystyle\leq~{}\sup_{x\in\mathcal{X}}\big{[}\|\nabla
g\|_{p}\big{]}\cdot\big{\|}x-\tilde{x}\big{\|}_{q}$

∎

######  Lemma 4.

Let $\mathbb{P}_{tr}[y]$ be training label distribution and
$\mathbb{P}_{te}[y]$ a test label distribution. We denote their ratio as
$q_{i}=\frac{\mathbb{P}_{te}[i]}{\mathbb{P}_{tr}[i]},~{}i=1,2,\cdots,C$. Then
we have the LA loss:

$\displaystyle\ell_{LA}\left(f^{\xi}_{\theta}(\bm{x}),j;\mathbb{P}_{j}\right)=\ell_{CE}\left(\mathsf{softmax}\left(f^{\xi}_{y,\theta}(\bm{x})-\log\left(q_{y}\right)\right)\right)$

is $2$-Lip. continuous w.r.t. the defined infinity norm.

###### Proof.

According to Lem.3, if for any fixed $\xi$:

$\displaystyle\sup_{(\bm{x},y)\in\mathcal{Z},f\in\mathcal{F}}\left\|\nabla_{f}\ell_{LA}\left(f^{\xi}_{\theta}(\bm{x}),j;\mathbb{P}_{tr}\right)\right\|_{1}\leq
2$ (8)

Then we have:

$\displaystyle\left|\ell_{LA}\left(f^{\xi}_{\theta}(\bm{x}),j;\mathbb{P}_{j}\right)-\ell_{LA}\left(\tilde{f}^{\xi}_{\theta}(\bm{x}),j;\mathbb{P}_{j}\right)\right|\leq
2\cdot\|f^{\xi}-\tilde{f}^{\xi}\|_{\infty}\leq
2\cdot\max_{i\in[K]}\|f^{(i)}-\tilde{f}^{(i)}\|_{\infty}=2\|f-\tilde{f}\|_{\infty}$

Hence, we only need to proof (8). To see this,

$\displaystyle\left|\frac{\partial\ell_{LA}\left(f_{\theta}(\bm{x}),j;\mathbb{P}_{tr}\right)}{\partial
f^{(j)}_{\theta}(\bm{x})}\right|$
$\displaystyle=\left|\frac{\partial\left(\log\left[\sum_{i}\exp(f^{(i)}(\bm{x})-q_{i})-(f_{y}-q_{y})\right]\right)}{\partial
f^{(j)}(\bm{x})}\right|$
$\displaystyle=\left|\mathsf{softmax}\left(f^{(j)}_{\theta}(\bm{x})-\log\left(q_{j}\right)\right)-I[j=y]\right|.$

Since we have:

$\displaystyle\left\|\nabla_{f}\ell_{LA}\left(f_{\theta}(\bm{x}),y;\mathbb{P}_{tr}\right)\right\|_{1}$
$\displaystyle=\sum_{j}\left|\mathsf{softmax}\left(f^{(j)}_{\theta}(\bm{x})-\log\left(q_{j}\right)\right)-I[j=i]\right|$
$\displaystyle=2\cdot\left(1-\mathsf{softmax}\left(f^{(y)}_{\theta}(\bm{x})-\log\left(q_{y}\right)\right)\right)$
$\displaystyle\leq 2.$

The proof is completed since $\bm{x},y,f$ are arbitrarily chosen.

∎

######  Lemma 5.

Given a meta-distribution $\mathcal{E}$ of label distributions, let
$\mathcal{E}$ be the Dirichlet mixture distribution of the components defined
in the main paper. Let

$\displaystyle\mathcal{P}\sim\mathcal{E}^{M},~{}\mathcal{P}=\left\\{\mathbb{P}_{1},\cdots,\mathbb{P}_{M}\right\\}$

For any function $\ell(f)$ with the property that $\ell(f)=\ell(f^{j})$, for
the $j$ Dirichlet component, if for any fixed $j$, $\ell(f^{j})$ is $L$-Lip.
continuous w.r.t to the infinity norm, then
$\operatorname*{\mathbb{E}}_{\mathcal{\mathcal{E}}}[\ell(f)],\operatorname*{\hat{\mathbb{E}}}_{\mathcal{E}}[\ell(f)]$
is also $L$-Lip. continuous w.r.t to the defined general infinity norm.

11

###### Proof.

We only prove the result for
$\operatorname*{\mathbb{E}}_{\mathcal{\mathcal{E}}}[\ell(f)]$, since the
result for $\operatorname*{\hat{\mathbb{E}}}_{\mathcal{\mathcal{E}}}[\ell(f)]$
can be proven similarly. Since

$\displaystyle\operatorname*{\mathbb{E}}_{\mathcal{\mathcal{E}}}[\ell(f)]=\sum_{i\in[K]}p_{i}\cdot\operatorname*{\mathbb{E}}_{\mathcal{\mathcal{E}}|i}[\ell(f^{i})],$

we have:

$\displaystyle|\operatorname*{\mathbb{E}}_{\mathcal{\mathcal{E}}}[\ell(f)]-\operatorname*{\mathbb{E}}_{\mathcal{\mathcal{E}}}[\ell(\tilde{f})]|\leq\sum_{i\in[K]}p_{i}\cdot|\operatorname*{\mathbb{E}}_{\mathcal{\mathcal{E}}|i}[\ell(f^{i})]-\operatorname*{\mathbb{E}}_{\mathcal{\mathcal{E}}|i}[\ell(\tilde{f}^{i})]|\leq\sum_{i\in[K]}L\cdot
p_{i}\cdot\|f^{i}-\tilde{f}^{i}\|_{\infty}\leq L\cdot\|f-\tilde{f}\|_{\infty}$

∎

###  D.3 Basic (Uniform) Concentration Inequalities

Please refer to Sec.D.1 for the basic definitions of hypothesis class
$\mathcal{F}$, covering number $\mathcal{N}_{\infty}$, and the infinity norm
$\|\cdot\|_{\infty}$.

######  Lemma 6.

(Duchi & Namkoong, 2016) Let $f:\mathbb{R}^{N}\rightarrow\mathbb{R}$ be convex
and $L$-Lip. continuous w.r.t to $\ell_{2}$ norm over $[a,b]^{n}$, and let
$Z_{1},\cdots,Z_{N}$ be independent random variables on $[a,b]$. Then for all
$t\geq 0$

$\displaystyle\max\bigg{\\{}\mathbb{P}\left[f(Z_{1:N})\geq\operatorname*{\mathbb{E}}\left[f(Z_{1:N})\right]\right]+t,~{}~{}\mathbb{P}\left[f(Z_{1:N})\leq\operatorname*{\mathbb{E}}\left[f(Z_{1:N})\right]-t\right]\bigg{\\}}\leq\exp\left(-\frac{t^{2}}{2L^{2}(b-a)^{2}}\right)$

######  Lemma 7 ((Maurer & Pontil, 2009)).

Let $\\{\bm{x}_{i},y_{i}\\}_{i=1}^{N}$ be i.i.d samples from a data
distribution, the loss function of a prediction is given by
$\ell(\bm{x}_{i},y_{i})=\ell(f(\bm{x}_{i}),y_{i})$ for a scoring function
$f\in\mathcal{F}$. For sufficiently large $N$ and sufficiently small $\delta$,
with probability at least $1-\delta$ over the randomness of the data sampling,
we have:

$\displaystyle\operatorname*{\mathbb{E}}[\ell]\lesssim\operatorname*{\hat{\mathbb{E}}}[\ell]+\sqrt{\frac{\operatorname*{\hat{\mathbb{V}}}[\ell]\cdot\log\left(\mathcal{M}/\delta\right)}{N}}+\frac{B\cdot\log\left(\mathcal{M}/\delta\right)}{N}$

holds uniformly for all $f\in\mathcal{F}$, with
$\mathcal{M}=\mathcal{N}_{\infty}(\mathcal{F},{1/N},{2N})$.

######  Lemma 8.

Let $\\{\bm{x}_{i},y_{i}\\}_{i=1}^{N}$ be i.i.d samples from a data
distribution, the loss function of a prediction is given by
$\ell(\bm{x}_{i},y_{i})=\ell(f(\bm{x}_{i}),y_{i})\in[0,B]$ for a scoring
function $f\in\mathcal{F}$. If the loss function is $L$-Lip. continuous w.r.t.
the infinity norm $||f||_{\infty}=\max_{\bm{x}\in\mathcal{X}}|f(\bm{x})|$.
Then the following inequality holds with probability at least $1-\delta$
uniformly for all $f\in\mathcal{F}$:

$\displaystyle\left|\operatorname*{\mathbb{E}}[\ell]-\operatorname*{\hat{\mathbb{E}}}[\ell]\right|\lesssim
B\cdot\sqrt{\frac{\log(\mathcal{M}^{\prime}/\delta)}{N}}$

where $\mathcal{M}^{\prime}=\mathcal{N}_{\infty}(\mathcal{F},{1/2LN},{N})$.

###### Proof.

According to the basic property of the covering number, we can find a covering
of $\mathcal{F}$ with a set of open ball
$\left\\{\mathcal{B}_{1},\cdots,\mathcal{B}_{\mathcal{M}^{\prime}}\right\\}$.
For each $\mathcal{B}_{j}$ the center is defined as $f_{j}$. In this sense, we
have
$\mathcal{B}_{j}=\\{f\in\mathcal{F}:\|f-f_{j}\|_{\infty}\leq\epsilon/3L\\}$

In this sense we have the following results according to the union bound:

$\displaystyle\mathbb{P}\left[\sup_{f\in\mathcal{F}}\left[{\left|\operatorname*{\mathbb{E}}[\ell]-\operatorname*{\hat{\mathbb{E}}}[\ell]\right|}\right]\geq
t+\epsilon\right]\leq\sum_{j=1}^{\mathcal{M}^{\prime}}\mathbb{P}\left[\sup_{f\in\mathcal{B}_{j}}\left[{\left|\operatorname*{\mathbb{E}}[\ell]-\operatorname*{\hat{\mathbb{E}}}[\ell]\right|}\right]\geq
t+\epsilon\right]$

Fix one $j$, we must have:

$\displaystyle\mathbb{P}\left[\sup_{f\in\mathcal{B}_{j}}\left[{\left|\operatorname*{\mathbb{E}}[\ell]-\operatorname*{\hat{\mathbb{E}}}[\ell]\right|}\right]\geq
t+\epsilon\right]\leq\mathbb{P}\left[\sup_{f\in\mathcal{B}_{j}}\left[{\left|\operatorname*{\mathbb{E}}[\ell]-\operatorname*{\mathbb{E}}[\ell_{j}]\right|}\right]\geq\frac{\epsilon}{2}\right]+\mathbb{P}\left[{\left|\operatorname*{\hat{\mathbb{E}}}[\ell_{j}]-\operatorname*{\hat{\mathbb{E}}}[\ell_{j}]\right|}\geq
t\right]+\mathbb{P}\bigg{[}\sup_{f\in\mathcal{B}_{j}}\left[{\left|\operatorname*{\hat{\mathbb{E}}}[\ell]-\operatorname*{\hat{\mathbb{E}}}[\ell_{j}]\right|}\right]\geq\frac{\epsilon}{2}\bigg{]}$

Since $\ell$ is $L$-Lip. w.r.t the infinity norm, we have:

$\displaystyle|\ell-\ell_{j}|\leq L\cdot\|{f-f_{j}}\|_{\infty}\leq
L\cdot\frac{\epsilon}{2L}\leq\frac{\epsilon}{2}.$

Hence,
$\sup_{f\in\mathcal{B}_{j}}\left[{\left|\operatorname*{\mathbb{E}}[\ell]-\operatorname*{\mathbb{E}}[\ell_{j}]\right|}\right]\geq\frac{\epsilon}{2}$,
$\sup_{f\in\mathcal{B}_{j}}\left[{\left|\operatorname*{\hat{\mathbb{E}}}[\ell]-\operatorname*{\hat{\mathbb{E}}}[\ell_{j}]\right|}\right]\geq\frac{\epsilon}{2}$
has probability 0.

Moreover, according to the Hoeffding’s inequality, we have:

$\displaystyle\mathbb{P}\bigg{[}{\left|\operatorname*{\mathbb{E}}[\ell_{j}]-\operatorname*{\hat{\mathbb{E}}}[\ell_{j}]\right|}\geq
t\bigg{]}\leq 2\cdot\exp\left(-\frac{2\cdot t^{2}}{B^{2}}\right)$

Combing the arguments all above, we have:

$\displaystyle\mathbb{P}\left[\sup_{f\in\mathcal{F}}\left[{\left|\operatorname*{\mathbb{E}}[\ell]-\operatorname*{\hat{\mathbb{E}}}[\ell]\right|}\right]\leq\epsilon\right]\geq
1-\mathcal{N}_{\infty}(\mathcal{F},{\epsilon/2L},{N})\cdot\exp\left(-\frac{2t^{2}}{B^{2}}\right).$

The proof is finished by setting
$\delta=\exp\left(-\frac{t^{2}}{B^{2}}\right)$ and $\epsilon=1/N$.

∎

######  Lemma 9.

Let $\\{\bm{x}_{i},y_{i}\\}_{i=1}^{N}$ be i.i.d samples from a data
distribution, the loss function of a prediction is given by
$\ell(\bm{x}_{i},y_{i})=\ell(f(\bm{x}_{i}),y_{i})\in[0,B]$ for a scoring
function $f\in\mathcal{F}$. If $\ell$ is $L$-Lip. continuous, then for any
$L_{g}$ Lip. continuous function of $f$, we have the following inequality
holds with probability at least $1-\delta$ uniformly for all
$f\in\mathcal{F}$:

$\displaystyle\left|g\bigg{(}\operatorname*{\mathbb{E}}[\ell]\bigg{)}-g\left(\operatorname*{\hat{\mathbb{E}}}[\ell]\right)\right|\lesssim
L_{g}\cdot B\cdot\sqrt{\frac{\log(\mathcal{M}^{\prime}/\delta)}{N}}$

where $\mathcal{M}^{\prime}=\mathcal{N}_{\infty}(\mathcal{F},{1/2LN},{N})$.

###### Proof.

Since $g$ is $L_{g}$ Lip., we have:

$\displaystyle\sup_{f\in\mathcal{F}}\left[{\left|g\bigg{(}\operatorname*{\mathbb{E}}[\ell]\bigg{)}-g\left(\operatorname*{\hat{\mathbb{E}}}[\ell]\right)\right|}\right]\leq
L_{g}\sup_{f\in\mathcal{F}}\left[{\left|\operatorname*{\mathbb{E}}[\ell]-\operatorname*{\hat{\mathbb{E}}}[\ell]\right|}\right]$

Thus we have:

$\displaystyle\mathbb{P}\left[\sup_{f\in\mathcal{F}}\left[{\left|g\bigg{(}\operatorname*{\mathbb{E}}[\ell]\bigg{)}-g\left(\operatorname*{\hat{\mathbb{E}}}[\ell]\right)\right|}\right]\geq
t+\epsilon\right]\leq\mathbb{P}\left[\sup_{f\in\mathcal{F}}\left[{\left|\operatorname*{\mathbb{E}}[\ell]-\operatorname*{\hat{\mathbb{E}}}[\ell]\right|}\right]\geq\frac{t+\epsilon}{L_{g}}\right]$

Then the claim follows from Lem.8 using
$\epsilon^{\prime}=\frac{\epsilon}{L_{g}},~{}t^{\prime}=\frac{t}{L_{g}}$.

∎

Table 4:  Some Important Notations Used in the Proof. Notation | Description
---|---
Basic Quantities |
$N$ | The number of data instances in the training data.
$M$ | The number of sampled test distributions in the Monte Carlo process.
$\tau$ | A specific test label distribution.
$\mathcal{E}$ | The meta-distribution of label distributions.
${\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}$ |  $\sum_{(\bm{x}_{i}y_{i})\in\mathcal{S}}{\ell_{\mathsf{LA}}}(f_{\theta}(\bm{x}_{i}),y_{i};\mathbb{P})$ The expected loss when the label distribution is fixed (for example $\mathbb{P}$).
${\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}$ | The empirical loss on training data $\mathcal{S}$ when the label distribution is fixed.
$\ell_{\mathcal{S},\mathcal{E},i}$ |  $\operatorname*{\hat{\mathbb{E}}}_{\mathcal{S}}\left[{\ell_{\mathsf{LA}}}(f^{(\xi_{i})}(\bm{x}),y;P_{i})\right]$ The empirical risk on training data $\mathcal{S}$ for $\mathcal{P}_{i}\in\mathcal{P}$
$\ell_{\mathcal{D},\mathcal{E},i}$ |  $\operatorname*{\mathbb{E}}_{\mathcal{D}}\left[{\ell_{\mathsf{LA}}}(f^{(\xi_{i})}(\bm{x}),y;P_{i})\right]$ The empirical risk on training data distribution $\mathcal{D}$ for $\mathcal{P}_{i}\in\mathcal{P}$
$\bar{\ell}_{\mathcal{P}}$ |  $\frac{1}{M}\sum_{m=1}^{M}{\ell_{\mathsf{LA}}}(f^{(\xi_{m})}(\bm{x}),y;P_{m})$ The empirical average over $\mathcal{P}$ given a fixed sample pair $(\bm{x},y)$.
| Estimations based on the true meta-distribution $\mathcal{E}$
$\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{E}}[{\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}]$ | The expected ${\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}$ over the meta-distribution of label distributions
$\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$ | The expected ${\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}$ over the meta-distribution of label distributions
$\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{\mathcal{E}}[{\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}]$ | The variance of ${\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}$ over the meta-distribution of label distributions
$\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$ | The variance ${\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}$ over the meta-distribution of label distributions
$\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}+},\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$ | The semi-variance ${\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}$ over the meta-distribution of label distributions
| Estimations based on Empirical meta-distribution $\mathcal{P}$
$\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}]$ | The empirical average of ${\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}$ over the sampled label distributions in the Monte Carlo process.
$\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$ | The empirical average of ${\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}$ oover the sampled label distributions in the Monte Carlo process.
$\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}]$ | The empirical variance of ${\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}$ over the sampled label distributions in the Monte Carlo process.
$\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$ | The empirical variance ${\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}$ over the sampled label distributions in the Monte Carlo process.
$\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}+},\mathcal{E}}[{\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}]$ | The empirical semi-variance of ${\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}$ over the sampled label distributions in the Monte Carlo process.
$\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}+},\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$ | The empirical semi-variance ${\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}$ over the sampled label distributions in the Monte Carlo process.
| Complexity Measures
$\mathcal{N}_{\infty}(\mathcal{F},\epsilon,n)$ | The covering number for a hypothesis class $\mathcal{F}$, with radius of the covering open ball chosen as $\epsilon$.

###  D.4 Proof of the Main Result

####  D.4.1 Notations in the Proof

The Hierarchy of Stochastic Error. Recall that we are using a stratified
sampling process for the Dirichlet mixture distribution. Hence, we each
component $j$ of the mixture, we sample $M$ label distributions, denoted as

$\displaystyle\mathcal{P}\sim\mathcal{E}^{M},~{}\mathcal{P}=\left\\{\mathbb{P}_{1},\cdots,\mathbb{P}_{M}\right\\}$

This forms an empirical sample of the test label distributions. We denote
corresponding overall estimation as
$\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}],\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$.
Moreover, we also have a fixed training dataset

$\displaystyle\mathcal{S}\sim\mathcal{D}^{N},\mathcal{S}=\\{\bm{x}_{i},y_{i}\\}_{i=1}^{N},$

This forms an empirical estimation of the training data distribution. We mark
the corresponding empirical (population resp.) estimations with subscript
$\mathcal{S}$ ($\mathcal{D}$ resp.). To estimate the excess risk, we must
estimate the hierarchical stochastic error coming from label distribution
sampling and data sampling. To do this, we present the following error
decompose regime.

In this proof, we will employ two groups of intermediate empirical
estimations.

The first group involves quantities for a fixed test label distribution
$\mathbb{P}_{i}\in\mathcal{P}$. Specifically, we denote
$\ell_{\mathcal{D},\mathcal{E},i},\ell_{\mathcal{S},\mathcal{E},i}$ as the
expected loss on distribution $\mathcal{D}$ (empirical average loss on the
training data $\mathcal{D}$ resp.):

$\displaystyle\ell_{\mathcal{D},\mathcal{E},i}=\operatorname*{\mathbb{E}}_{\mathcal{D}}\left[{\ell_{\mathsf{LA}}}(f^{(\xi_{i})}(\bm{x}),y;P_{i})\right]$
$\displaystyle\ell_{\mathcal{S},\mathcal{E},i}=\operatorname*{\hat{\mathbb{E}}}_{\mathcal{S}}\left[{\ell_{\mathsf{LA}}}(f^{(\xi_{i})}(\bm{x}),y;P_{i})\right]$
(9)

The other groups of quantities regard the average loss under all sampled label
distributions as a fixed loss and then evaluate their sample- and population-
level means. Specifically, let

$\displaystyle\bar{\ell}_{\mathcal{P}}=\frac{1}{M}\sum_{m=1}^{M}{\ell_{\mathsf{LA}}}(f^{(\xi_{m})}(\bm{x}),y;P_{m}),$

then we can rewrite
$\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}],\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}]$
as:

$\displaystyle\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]=\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{D}}\left[\bar{\ell}_{\mathcal{P}}\right]$
$\displaystyle\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}]=\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{S}}\left[\bar{\ell}_{\mathcal{P}}\right]$
(10)

####  D.4.2 The Formal Restate and Proof

######  Theorem 5 (Restate of Thm.1).

For label distributions, let $\mathcal{E}$ be the true meta-distribution and
$\mathcal{P}$ be a observed empirical distribution for label distribution
sampled by the Monte Carlo method. Moreover, the training data $\mathcal{S}$
are sampled in a i.i.d manner from its true distribution $\mathcal{D}$. Assume
that
$\mathcal{N}_{\infty}(\mathcal{F},{\epsilon},{M})\leq\left(\frac{r}{\epsilon}\right)^{\nu}$,
$\ell(\cdot)\in[0,B]$, and
$\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]\asymp\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}+},\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$
following the notations in Tab.4, all any possible meta-distribution
$\mathcal{E}^{\prime}$ defined on the probability simplex $\mathbb{S}^{c-1}$,
the following inequality holds uniformly for all $f\in\mathcal{F}$ with
probability at least $1-\delta$ over the randomness of
$\mathcal{S},\mathcal{P}$:

$\displaystyle\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{E}’}[\ell_{\mathcal{D},\mathcal{E}^{\prime}}]$
$\displaystyle\lesssim\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}]+\sqrt{\frac{\nu\cdot\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}+},\mathcal{E}}[{\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}]\cdot\log\left(\zeta_{1}\right)}{M}}+\frac{B\cdot\|\mathcal{E}-\mathcal{E}^{\prime}\|_{\infty}}{C!}+B\cdot\sqrt{\nu^{3/2}\cdot\frac{\log^{3/2}\left(\zeta_{1}\right)}{M\sqrt{M}}}$
$\displaystyle~{}~{}+B\cdot\sqrt{\nu^{3/2}\cdot\frac{\sqrt{\log\left(\zeta_{2}\right)}\cdot\log\left(\zeta_{1}\right)}{M\sqrt{N}}}+\frac{B\cdot\nu\cdot\log\left(\zeta_{1}\right)}{M}+B\cdot\sqrt{\nu\cdot\frac{\log(\zeta_{2})}{N}},$

where

$\displaystyle
C_{M}=3M+4,~{}~{}\zeta_{1}=\left(C_{M}BM/\delta\right)^{(1/\nu)}\cdot
r,~{}~{}\zeta_{2}=\left(C_{M}N/\delta\right)^{(1/\nu)}\cdot r,$

###### Proof.

this is the begining
this is the begining
NOTE: Please see Tab.4 and Sec.D.4.1 for all the necessary notations not
explained herein.

The Error Decomposition. The overall uniform excess risk can be decomposed
into three parts:

$\displaystyle\sup_{f\in\mathcal{F}}\left[{\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{E}’}[\ell_{\mathcal{D},\mathcal{E}^{\prime}}]-\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}]}\right]\leq\underbrace{\sup_{f\in\mathcal{F}}\left[{\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{E}’}[\ell_{\mathcal{D},\mathcal{E}^{\prime}}]-\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]}\right]}_{(1)}+\underbrace{\sup_{f\in\mathcal{F}}\left[{\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]-\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]}\right]}_{(2)}+\underbrace{\sup_{f\in\mathcal{F}}\left[{\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]-\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}]}\right]}_{(3)}$

The first part is due to the meta-distribution shift from the known
distribution $\tau$ to an unknown distribution $\tau^{\prime}$; the second
part reflects the random error produced from using the Monte Carlo estimation;
while the third part reflects the error coming from the empirical estimation
of the population-level mean loss when the Monte Carlo result is given.

Since bounding (1) and (3) are relatively simple, the derivation will be
presented following the order $(1)\rightarrow(3)\rightarrow(2)$.

The Bound for (1). Since $\ell\in[0,B]$, we have:

$\displaystyle\sup_{f\in\mathcal{F}}\left[{\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{E}’}[\ell_{\mathcal{D},\mathcal{E}^{\prime}}]-\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]}\right]$
$\displaystyle\leq
B\cdot\int_{\mathbb{S}_{c-1}}|\mathcal{E}^{\prime}(\mathbb{P})-\mathcal{E}(\mathbb{P})|d\mathbb{P}$
$\displaystyle\overset{(a)}{\leq}\frac{B\cdot\|\mathcal{E}^{\prime}(\mathbb{P})-\mathcal{E}(\mathbb{P})\|_{\infty}}{C!}$

$\mathbb{S}_{c-1}$ is the probabilistic simplex on $\mathbb{R}^{c}$,
$\mathbb{P}$ is a $c$-dimensional probability allocation sampled either from
$\mathcal{E}$ or $\mathcal{E}^{\prime}$. In the derivation, $(a)$ is a direct
result from Lem.2.

The Bound for (3). According to (D.4.1), we have the following result:

$\displaystyle\sup_{f\in\mathcal{F}}\left[{\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]-\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}]}\right]=\sup_{f\in\mathcal{F}}\left[{\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{D}}\left[\bar{\ell}_{\mathcal{P}}\right]-\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{S}}\left[\bar{\ell}_{\mathcal{P}}\right]}\right]$

Under this reformulation, we then derive an upper bound by concentration over
the randomness of $\bar{\ell}_{\mathcal{P}}$. By applying Lem.8, we have the
following result holds with probability at least $1-\delta/(C_{M})$ for all
$f\in\mathcal{F}$:

$\displaystyle\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]-\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\hat{\ell}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\mathcal{S}},\mathcal{E}}}]\lesssim
B\cdot\sqrt{\frac{\log(C_{M}\cdot\mathcal{N}_{1}/\delta)}{N}},$

where $\mathcal{N}_{1}=\mathcal{N}_{\infty}(\mathcal{F},{1/4N},{N})$, where we
used the fact of the Lip. constant in Lem.4-5 and the basic property of
expectation.

The Bound for (2). Applying Lem.7 to the Monte Carlo process, we have the
following result holds uniformly with probability at least $1-\delta/(C_{M})$:

$\displaystyle\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]\lesssim\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]+\sqrt{\frac{\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]\cdot\log\left(C_{M}\cdot\mathcal{M}/\delta\right)}{M}}+\frac{B\cdot\log\left(C_{M}\cdot\mathcal{M}/\delta\right)}{M}$

with $\mathcal{M}=\mathcal{N}_{\infty}(\mathcal{F},{\frac{1}{4M}},{2M})$. We
present the rest of derivation in two steps

Step 1. We first upper bound
$\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$
with
$\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}+},\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$
and get a resulting inequality.

First we show that
$\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$
is 1-Lip w.r.t $\ell_{2}$ norm defined on the empirical measure $\mathcal{P}$:

$\displaystyle\|f-g\|_{2,M}=\sqrt{\sum_{i=1}^{M}\left(f(\mathbb{P}^{(j)}_{M})-g(\mathbb{P}^{(j)}_{M})\right)^{2}}.$

To do this, we denote
${\bm{\ell}=[\ell_{\mathcal{D},\mathcal{E},1},\cdots,\ell_{\mathcal{D},\mathcal{E},M}]}$,
where

$\displaystyle\ell_{\mathcal{D},\mathcal{E},{\color[rgb]{0.9921875,0.6796875,0.6796875}\definecolor[named]{pgfstrokecolor}{rgb}{0.9921875,0.6796875,0.6796875}i}}=\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{D}}\left[{\ell_{\mathsf{LA}}}(f^{(\xi_{\color[rgb]{0.9921875,0.6796875,0.6796875}\definecolor[named]{pgfstrokecolor}{rgb}{0.9921875,0.6796875,0.6796875}i})}(\bm{x}),y;P_{\color[rgb]{0.9921875,0.6796875,0.6796875}\definecolor[named]{pgfstrokecolor}{rgb}{0.9921875,0.6796875,0.6796875}i})\right]$

is the expected loss given a fixed test label distribution
$P_{\color[rgb]{0.9921875,0.6796875,0.6796875}\definecolor[named]{pgfstrokecolor}{rgb}{0.9921875,0.6796875,0.6796875}i}$.
Then, one can rewrite
$\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$
as:

$\displaystyle\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$
$\displaystyle=\frac{1}{M}\left(\bm{\ell}^{\top}\bm{\ell}-\frac{1}{M}\cdot\bm{\ell}^{\top}1_{M\times
M}\bm{\ell}\right)$
$\displaystyle=\frac{1}{M}\left\|(\bm{I}-\frac{1}{m}1_{M\times
M})\bm{\ell}\right\|^{2}$

where $\bm{\ell}^{\top}1_{M\times M}$ is an $M$ by $M$ all-one matrix. Here we
used the property:

$\displaystyle(\bm{I}-\frac{1}{m}1_{M\times
M})^{\top}(\bm{I}-\frac{1}{m}1_{M\times M})=(\bm{I}-\frac{1}{m}1_{M\times
M}).$

$\displaystyle\nabla_{\ell}\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]=\frac{2}{M}\cdot(\bm{I}-\frac{1}{m}1_{M\times
M})\cdot\bm{\ell}$

According to Lem.3, we need to bound:

$\displaystyle\left\|\nabla_{\ell}\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]\right\|_{2,M}$
$\displaystyle=\frac{2}{M}\cdot\left\|(\bm{I}-\frac{1}{m}1_{M\times
M})\cdot\bm{\ell}\right\|_{2}$
$\displaystyle\leq\frac{2}{M}\cdot\left\|(\bm{I}-\frac{1}{m}1_{M\times
M})\right\|_{sp}\cdot\left\|\bm{\ell}\right\|_{2}$
$\displaystyle\leq\frac{2}{M}\cdot\left(1-\frac{1}{M}\cdot\lambda_{min}\left(1_{M\times
M}\right)\right)\cdot MB$ $\displaystyle={2\cdot B},$

where for a real square matrix $\bm{A}\in\mathbb{R}^{M\times M}$,
$||\bm{A}||_{sp}=\lambda_{max}(\bm{A})$ is the spectral norm. The last
equality follows that $\lambda_{min}\left(1_{M\times M}\right)=0$ since the
rank of all-one matrix is 1. According to Lem.6, we have the following
inequality holds for a fixed $f\in\mathcal{F}$ with probability at least
$1-\delta/(C_{M})$:

$\displaystyle\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]\lesssim\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]+B^{2}\cdot\sqrt{\frac{\log(C_{M}/\delta)}{M}}.$

To construct a uniform bound, we derive the Lip. constant for
$\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}|j}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$
and
$\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{\mathcal{E}|j}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$
w.r.t the change of $f$ in terms of the infinity norm.

First we have:

$\displaystyle|\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]-\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[\tilde{\ell}_{\mathcal{D},\mathcal{E}}]|\leq
2\cdot
B\left\|{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}-\tilde{\ell}_{\mathcal{D},\mathcal{E}}\right\|_{2,M}\leq
4\cdot B\cdot\left\|f-\tilde{f}\right\|_{\infty},$

where $\tilde{\ell}_{\mathcal{D},\mathcal{E}}$ is the loss function evaluated
on $\tilde{f}$. The second inequality used the fact that
$\ell_{\mathcal{D},\mathcal{E}}$ is $4B$-Lip. continuous (a direct result of
Lem.4 and the basic property of the expectation).

Moreover, since
$\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]=(1-\frac{1}{M})\cdot\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}[\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]]$.
Thus, we have
$\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$
is also $4B$-Lip continuous. Above all, following a similar proof as Lem.8, we
have:

$\displaystyle\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{V}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]\lesssim\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]+B^{2}\cdot\sqrt{\frac{\log(C_{M}\cdot\mathcal{M}_{1}/\delta)}{M}}$

holds uniformly over all $f\in\mathcal{F}$ with practicality at least
$1-\delta/C_{M}$, where
$\mathcal{M}_{1}=\mathcal{N}_{\infty}(\mathcal{F},{1/8BM},{M})$.

Putting all together, we have the following result holds uniformly with
probability at least $1-2\cdot\delta/(C_{M})$:

$\displaystyle\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{E}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$
$\displaystyle\lesssim\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]+\sqrt{\frac{\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]\cdot\log\left(C_{M}\cdot\mathcal{M}/\delta\right)}{M}}+B\cdot\sqrt{\frac{\log\left(C_{M}\cdot\mathcal{M}_{1}/\delta\right)\cdot\log\left(C_{M}\cdot\mathcal{M}/\delta\right)}{M\sqrt{M}}}+\frac{B\cdot\log\left(C_{M}\cdot\mathcal{M}/\delta\right)}{M}$
(11)
$\displaystyle\asymp\operatorname*{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}\hat{\mathbb{E}}}}_{\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]+\sqrt{\frac{\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}+},\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]\cdot\log\left(C_{M}\cdot\mathcal{M}/\delta\right)}{M}}+B\cdot\sqrt{\frac{\log\left(C_{M}\cdot\mathcal{M}_{1}/\delta\right)\cdot\log\left(C_{M}\cdot\mathcal{M}/\delta\right)}{M\sqrt{M}}}+\frac{B\cdot\log\left(C_{M}\cdot\mathcal{M}/\delta\right)}{M}.$
(12)

Step 2. We now derive an upper bound for
$\operatorname*{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathbb{V}}}_{{\color[rgb]{0.19921875,0.55859375,0.65625}\definecolor[named]{pgfstrokecolor}{rgb}{0.19921875,0.55859375,0.65625}+},\mathcal{E}}[{\ell_{{\color[rgb]{0.45703125,0.6171875,0.22265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.45703125,0.6171875,0.22265625}\mathcal{D}},\mathcal{E}}}]$
by