# Balanced Data, Imbalanced Spectra:
Unveiling Class Disparities with Spectral Imbalance

Chiraag Kaushik∗,1 Ran Liu∗,1 Chi-Heng Lin1,7 Amrit Khera4 Matthew Y Jin6
Wenrui Ma5 Vidya Muthukumar1,3 Eva L Dyer1,2

###### Abstract

Classification models are expected to perform equally well for different
classes, yet in practice, there are often large gaps in their performance.
This issue of class bias is widely studied in cases of datasets with sample
imbalance, but is relatively overlooked in balanced datasets. In this work, we
introduce the concept of spectral imbalance in features as a potential source
for class disparities and study the connections between spectral imbalance and
class bias in both theory and practice. To build the connection between
spectral imbalance and class gap, we develop a theoretical framework for
studying class disparities and derive exact expressions for the per-class
error in a high-dimensional mixture model setting. We then study this
phenomenon in 11 different state-of-the-art pretrained encoders, and show how
our proposed framework can be used to compare the quality of encoders, as well
as evaluate and combine _data augmentation_ strategies to mitigate the issue.
Our work sheds light on the class-dependent effects of learning, and provides
new insights into how state-of-the-art pretrained features may have unknown
biases that can be diagnosed through their spectra.

††footnotetext: ∗Equal contribution, name ordered
alphabetically††footnotetext: 1Department of Electrical and Computer
Engineering, Georgia Institute of Technology, GA, USA††footnotetext:
2Department of Biomedical Engineering, Georgia Institute of Technology, GA,
USA††footnotetext: 3School of Industrial and Systems Engineering, Georgia
Institute of Technology, GA, USA††footnotetext: 4School of Computer Science,
Georgia Institute of Technology, GA, USA††footnotetext: 5School of
Mathematics, Georgia Institute of Technology, GA, USA††footnotetext:
6Department of Computer Science, Stanford University, CA, USA††footnotetext:
7Samsung Research America

##  1 Introduction

A core objective of machine learning is building fair classification models
that provide good performance irrespective of the class to which the data
belongs. In practice, however, models are often biased towards better
performance on some classes of the data and may do a poor job on others.

Most studies and approaches for dealing with class bias have focused on sample
imbalance, or the fact that different classes often have different number of
samples [49]. In this case, mechanisms to reweight the loss or rebalance the
dataset can be used to correct the sample imbalance [35, 51]. Somewhat
surprisingly, _even without sample imbalance_ there can still be significant
performance gaps across classes, including on state-of-the-art encoders. These
effects can become more pronounced depending on the types of regularization
and/or data augmentation used during training [5, 23]. Thus, we need a better
understanding of the sources of class disparities and new approaches for
identifying and mitigating underlying biases in models. This is particularly
relevant in the age of foundation and pretrained models, where underlying
biases in the features may exist and impact performance on downstream tasks.

In this work, we introduce a new framework for studying class-dependent
generalization that relies on a concept that we call spectral imbalance. The
central idea behind this perspective is that differences, or shifts, in the
distribution of features across classes could be the source of class biases.
We characterize these differences in feature geometry using the distribution
of _eigenvalues_ , i.e. the _spectrum_ , for each class and show, both in
theory and in practice, that deviations in spectra across classes will indeed
produce interesting effects on the class gap.

First, we develop a theoretical framework for studying this phenomenon and dig
deeper into the distinct ways in which spectral imbalance may impact class
gap. In particular, we derive exact asymptotic expressions for the class-wise
error in a Gaussian mixture model with class-specific covariances. We use
these expressions to uncover different types of spectral imbalance and
characterize their consequences for the class gap. This theory provides a
strong basis for the investigation of the spectra in per-class generalization.

Next, in extensive empirical investigations, we study the class-dependent
spectra for 11 state-of-the-art pretrained encoders (with 6 distinct types of
architecture) on ImageNet. Across the board, we observe that the class gap is
strongly correlated with the spectral imbalance of the representation space
and that through measuring different statistics of this imbalance, we can
predict which classes will perform worse than others without actually testing
the model. Furthermore, we define a classwise _spectral quantile measure_ that
we use to diagnose different models, predict which encoders will have smaller
class gaps, and also determine smarter augmentation strategies. Our empirical
results provide strong evidence that spectral imbalance plays an important
role in the characteristics of representation space.

In summary, our major contributions are as follows:

  * •

In Section 2, we introduce the concept of spectral imbalance and study how
discrepancies in eigenvalues between classes are related to the problem of
class-dependent generalization.

  * •

In Section 3, we derive exact theoretical expressions for the per-class
generalization in a high-dimensional linear mixture-model setting (Theorem 1).
The resultant simulations demonstrate the effect of different spectral
imbalances on the per-class performance gap.

  * •

In Section 4, we empirically demonstrate that similar phenomena hold in the
representation space of pre-trained models. Thus, we design a _spectral
quantile score_ , that accurately measures the amount of ‘imbalance’ in
representation space.

  * •

Finally, in Section 4.4, we provide an initial exploration of how to improve
augmentation design to mitigate spectral imbalance, and design a simple
ensemble method to combine augmentations and improve performance across
classes without any re-training.

##  2 Why spectral imbalance?

Effectively addressing class bias necessitates a deep understanding of the
underlying structure of the representation space. One promising avenue is
through analyzing the spectral properties of the features corresponding to
each class. The spectrum, i.e., the set of eigenvalues of the covariance
matrix of the representation, serves as a powerful indicator of the features’
intrinsic geometry and dimensionality. It characterizes how variance is
distributed across different principal components, offering a window into the
structure of the representation space. We thus hypothesize that variations in
these spectral properties will provide crucial insights into class-specific
performance, potentially revealing biases that are not immediately discernible
through traditional measures of imbalance (e.g. sample size per class).

We explore in particular the extent to which spectral imbalance, or variation
in spectral characteristics across different classes, impacts class
performance. As a motivating example, in Figure 1, we estimate and examine the
spectrum for different classes in a pre-trained ResNet-50 [18]. We make two
important observations:

  * •

First, we find that the eigenvalue distributions differ significantly between
top-performing and worst-performing classes, with top-performing classes
exhibiting a uniformly _smaller_ spectrum (Figure 1(A)).

  * •

Second, when comparing eigenvalues of different pretrained encoders, we
observe that the distribution of the eigenvalues shifts considerably. For
example, classes might have similarly ranked eigenvalues in one encoder, but
vastly different eigenvalues in another (see Figure 1(B), more in Appendix
Figure 3).

Both of these observations motivate the need to understand the differences in
class-dependent spectra, and how different sources of spectral imbalance may
impact downstream performance.

Figure 1: Spectral imbalance in different pretrained models. (A) We plot the
spectrum of the top and bottom performing classes and find that classes that
achieve lower accuracy have larger eigenvalues. (B) Histogram of the $k=5$
eigenvalue across classes for two encoders (ResNet-50, ViT-B) with the
quartiles indicated. If we look at classes with similarly ranked or “adjacent”
eigenvalues (upper quartile) in ResNet-50, we find that they can be mapped to
very different positions in the distribution of eigenvalues in another encoder
(ViT-B).

###  2.1 Examining the role of the spectrum in class-dependent generalization

To see more concretely how spectral balance across classes can play a role in
_class-dependent generalization_ , we first consider a simple linear
classification setting, where the features follow a 2-class Gaussian mixture
model (GMM):

$\mathbf{x}\>|\>y\overset{\mathclap{\text{i.i.d.}}}{\sim}\mathcal{N}(y\boldsymbol{\theta}^{*},\boldsymbol{\Sigma}_{y}).$

Here, $\boldsymbol{\theta}^{*}\in\mathbb{R}^{p}$ is an unknown signal
controlling the class means, $y\in\\{-1,1\\}$ is the label, and
$\boldsymbol{\Sigma}_{y}$ are the covariance matrices for each class. For any
fixed estimator $\hat{\boldsymbol{\theta}}$, inference is performed as
$\hat{y}=\text{sign}(\mathbf{x}^{\top}\hat{\boldsymbol{\theta}})$. Then, the
class-dependent probability-of-error (POE) can be written as:

$\displaystyle\text{POE}(\hat{\boldsymbol{\theta}}|y)$
$\displaystyle\coloneqq\operatorname{\mathbb{P}}\\{\text{sign}(\mathbf{x}^{\top}\hat{\boldsymbol{\theta}})\neq
y|\mathbf{x}\text{ in class }y\\}$ (1)
$\displaystyle=Q\left(\frac{\langle\hat{\boldsymbol{\theta}},\boldsymbol{\theta}^{*}\rangle}{\|\boldsymbol{\Sigma}_{y}^{1/2}\hat{\boldsymbol{\theta}}\|_{2}}\right)$
(2)

where $Q(\cdot)$ is the Gaussian Q-function (see proof in Appendix A). Fixing
the estimator $\hat{\boldsymbol{\theta}}$, we can see that the class
dependency of the POE is captured by the term
$\|\boldsymbol{\Sigma}_{y}^{1/2}\hat{\boldsymbol{\theta}}\|_{2}$. Hence, it is
natural to consider differences in this quantity as indicators of how
differently an estimator can be expected to perform on the two classes. In
particular, an estimator $\hat{\boldsymbol{\theta}}$ will achieve small class
gap when
$\|\boldsymbol{\Sigma}_{y=1}^{1/2}\hat{\boldsymbol{\theta}}\|_{2}\approx\|\boldsymbol{\Sigma}_{y=-1}^{1/2}\hat{\boldsymbol{\theta}}\|_{2}$,
for which a sufficient (but by no means necessary) condition is that
$\boldsymbol{\Sigma}_{y=1}\approx\boldsymbol{\Sigma}_{y=-1}$.

As a concrete example, suppose for simplicity that the eigendecompositions of
the class covariances are
$\boldsymbol{\Sigma}_{y}=\sum_{j}\lambda_{j}^{(y)}\mathbf{v}_{j}\mathbf{v}_{j}^{T}$,
i.e., both share the same eigenvectors. Then,

$\textit{ClassGap}(\hat{\boldsymbol{\theta}})\coloneqq\left\lvert\text{POE}(\hat{\boldsymbol{\theta}}|y=-1)-\text{POE}(\hat{\boldsymbol{\theta}}|y=1)\right\rvert\\\
$

is positively correlated with the quantity

$\left\lvert\sum_{j}(\lambda_{j}^{(y=-1)}-\lambda_{j}^{(y=1)})\langle\hat{\boldsymbol{\theta}},\mathbf{v}_{j}\rangle^{2}\right\rvert$

From these expressions, we can see that if the eigenvalues of
$\boldsymbol{\Sigma}_{1}$ are uniformly smaller than those of
$\boldsymbol{\Sigma}_{-1}$, Class 1 will have smaller generalization error.
This conforms with the familiar intuition that classes with smaller variance
(i.e., less noise) should be “easier” to identify, as shown in Figure 1.
Moreover, the effect of an eigenvalue gap between the two classes is unevenly
distributed between different coordinates, depending on the structure of the
estimator $\hat{\boldsymbol{\theta}}$.

Of course, in general, the connection between the spectra of features
corresponding to a specific class and the per-class generalization is
considerably more nuanced, since $\hat{\boldsymbol{\theta}}$ is itself learned
from training examples and depends crucially on the properties of the spectra
of both classes. Indeed, many recent works on benign overfitting in linear
regression and classification [6, 32, 7, 44] have shown that the properties of
the (overall) data spectrum play a vital role in achieving good overall
performance, particularly in the overparameterized regime. In the forthcoming
sections, we extend these insights to a fundamental understanding of how the
_class-wise spectrum_ affects per-class performance, and build the framework
of spectral imbalance.

##  3 An exact characterization of the class gap

In this section, we explore the factors that govern class imbalances by
studying the case of high-dimensional linear classification in the GMM setting
introduced in Section 2, where the mixtures correspond to the classes. The GMM
is a natural way to study class covariance differences and provides insights
into the types of representations that might result in larger class biases in
practice. Here, we provide an exact asymptotic characterization of the per-
class generalization error and class gap. Our framework allows us to model
nuanced relationships between the eigenvalues of each class covariance,
providing a rigorous testbed for studying their effect on per-class
generalization.

#### The GMM model.

We consider a training scheme where we are given $n$ i.i.d. samples
$(\mathbf{x},y)$ from the GMM setting in Section 2.1, where $n_{1}$ (resp.,
$n_{-1}$) samples come from Class $1$ (resp., Class -1). We study _empirical
risk minimization_ (ERM) estimators of the form

$\hat{\boldsymbol{\theta}}\coloneqq\arg\min_{\boldsymbol{\theta}\in\mathbb{R}^{p}}\frac{1}{n}\sum_{i=1}^{n}\mathcal{L}(y_{i}\langle\mathbf{x}_{i},\boldsymbol{\theta}\rangle)+r\lVert\boldsymbol{\theta}\rVert_{2}^{2},$

where $\mathcal{L}$ is a convex loss function and $r>0$ is the ridge
regularization parameter. Our goal is to characterize the per-class test error
of the resultant $\hat{\boldsymbol{\theta}}$, given by Equation (1).

Our theory considers the modern high-dimensional setting where both the model
complexity and the number of training samples are large. Specifically, we
study the per-class error in the asymptotic limit where $n,p\to\infty$
jointly, with the ratios $\frac{n}{p}=\delta$, $\frac{n_{y}}{n}=\pi_{y}$ fixed
(and clearly, $\pi_{1}+\pi_{-1}=1)$.111We note here that the quantities
$\hat{\boldsymbol{\theta}},\boldsymbol{\Sigma}_{y},\boldsymbol{\theta}^{*}$,
and $\text{POE}(\hat{\boldsymbol{\theta}}\>|\>y)$ should be interpreted as
sequences indexed by $n$; however, we will suppress the dependence on $n$ in
the notation for clarity. Our theory allows for overparameterization
($\delta<1$) or underparameterization ($\delta>1$), and for any constant
regularization parameter $r>0$.

Figure 2: Spectral imbalance in the GMM for the settings in Section 3.1. Top
Row: Visualization of the spectra of both classes. Bottom Row: Theoretical
predictions of Theorem 1 (solid lines) and numerical simulations (average over
50 trials $\pm 1$ std.) for the per-class error.

#### Notation.

The Mahalanobis norm of a vector, defined for a positive semi-definite matrix
$\mathbf{H}$ is given by
$\|\mathbf{x}\|_{\mathbf{H}}=\sqrt{\mathbf{x}^{\top}\mathbf{H}\mathbf{x}}$. We
also define the following function, which we denote the $L$th order Moreau
envelope function of a given convex function $f:\mathbb{R}\to\mathbb{R}$:

$\mathcal{M}^{(L)}_{f}(x_{1},.\hfil.\hfil.,x_{L};\tau_{1},.\hfil.\hfil.,\tau_{L})\coloneqq\min_{v\in\mathbb{R}}f(v)+\sum_{\ell=1}^{L}\frac{1}{2\tau_{\ell}}(x_{\ell}-v)^{2}$

Note that for $L=1$ this is the classical Moreau envelope function of $f$. We
will often use the shorthand notation
$\mathcal{M}^{(2)}(x_{y};\tau_{y})=\mathcal{M}^{(2)}(x_{1},x_{-1};\tau_{1},\tau_{-1})$.
The notation $\overset{P}{\to}$ denotes convergence in probability,
$\overset{\mathcal{W}_{2}}{\to}$ denotes convergence in Wasserstein-2
distance, and the empirical distribution of a random variable $a_{j}$ is
denoted $\frac{1}{p}\sum_{j=1}^{p}\delta(a_{j})$.

#### Main results.

We now state our general asymptotic result for the GMM with spectral
imbalance. Our analysis relies on the Convex Gaussian Min-Max Theorem [39] and
is influenced (particularly in the treatment of anisotropic covariances) by
[31] and [37], who consider, respectively, max-margin classification and
adversarial training in the GMM _without_ spectral imbalance. After stating
the assumptions and theorem, we briefly outline major differences in the proof
technique while deferring the full proof to Appendix A.

######  Assumption 1.

The target signal $\boldsymbol{\theta}^{*}$ and class covariances
$\boldsymbol{\Sigma}_{y}$ satisfy the following:

  1. 1.

The $\boldsymbol{\Sigma}_{y}$ are diagonal.

  2. 2.

$\lVert\boldsymbol{\theta}^{*}\rVert_{\boldsymbol{\Sigma}_{y}^{-1}}\to\zeta_{y}$
and $\lVert\boldsymbol{\theta}^{*}\rVert_{2}\to C$ for some constants
$\zeta_{y},C>0$.

  3. 3.

The empirical joint distribution of
$(\sqrt{p}\boldsymbol{\theta}^{*}_{j},\lambda_{j}^{(1)},\lambda_{j}^{(-1)})$
converges to some distribution, denoted $\Pi$:
$\frac{1}{p}\sum_{j=1}^{p}\delta(\sqrt{p}\boldsymbol{\theta}^{*}_{j},\lambda_{j}^{(1)},\lambda_{j}^{(-1)})\overset{\mathcal{W}_{2}}{\to}\Pi$.

Due to rotational invariance, the first assumption is for simplicity and can
be relaxed to the setting where the covariances are simultaneously
diagonalizable. We also note that the last assumption is quite flexible; as we
will see in Section 3.1, various choices of $\Pi$ can reflect very different
types of spectral imbalance between the two classes.

######  Theorem 1.

Let $G,H_{1},H_{-1}\overset{\mathclap{\text{i.i.d.}}}{\sim}\mathcal{N}(0,1)$
and $(T,L_{1},L_{-1})\sim\Pi$. Under Assumption 1, the per-class POE can be
written as a function of scalars $\mu_{y}$, $\alpha_{y}$, and $\zeta_{y}$:

$\text{POE}(\hat{\boldsymbol{\theta}}\>|\>y)=Q\left(\frac{\langle\hat{\boldsymbol{\theta}},\boldsymbol{\theta}^{*}\rangle}{\|\boldsymbol{\Sigma}_{y}^{1/2}\hat{\boldsymbol{\theta}}\|_{2}}\right)\overset{P}{\to}Q\left(\frac{\mu_{y}\zeta_{y}^{2}}{\sqrt{\alpha_{y}^{2}+\mu_{y}^{2}\zeta_{y}^{2}}}\right),$

where ($\mu_{y}$, $\alpha_{y}$) are found in the optimal solution (if it is
unique) of the following min-max problem over 12 scalar variables:

$\displaystyle\min_{\begin{subarray}{c}\alpha_{y},\tau_{y}\geq 0\\\
\mu_{y}\in\mathbb{R}\end{subarray}}\max_{\begin{subarray}{c}\beta_{y},\gamma_{y}\geq
0\\\ \eta_{y}\in\mathbb{R}\end{subarray}}r\operatorname{\mathbb{E}}$
$\displaystyle\mathcal{M}^{(2)}_{(\cdot)^{2}}\left(\frac{\alpha_{y}\beta_{y}H_{y}}{\gamma_{y}\sqrt{\delta
L_{y}}}+\frac{\eta_{y}\alpha_{y}T}{\gamma_{y}\zeta_{y}^{2}L_{y}};\frac{\alpha_{y}r}{\gamma_{y}L_{y}}\right)+\sum_{y\in\\{-1,1\\}}\left[\pi_{y}\operatorname{\mathbb{E}}_{G}\mathcal{M}^{(1)}_{\mathcal{L}}\left(\mu_{y}\zeta_{y}^{2}+\sqrt{\mu_{y}^{2}\zeta_{y}^{2}+\alpha_{y}^{2}}G;\frac{\tau_{y}}{\beta_{y}}\right)\right.$
(3) $\displaystyle\hskip
85.35826pt\left.-\frac{\eta_{y}^{2}\alpha_{y}}{2\gamma_{y}\zeta_{y}^{2}}-\frac{\mu_{y}^{2}\gamma_{y}\zeta_{y}^{2}}{2\alpha_{y}}\right.-\left.\frac{\alpha_{y}\beta_{y}^{2}}{2\delta\gamma_{y}}+\frac{\beta_{y}\tau_{y}}{2}-\frac{\alpha_{y}\gamma_{y}}{2}+\eta_{y}\mu_{y}\right].$

First, we note that the min-max optimization specified in Theorem 1 is
straightforward to solve by gradient descent/ascent. Hence, this theorem
provides a simple analytical framework to assess the exact asymptotic impact
of various high dimensional and spectrally-imbalanced GMM settings.
Specifically, we can apply the above theorem for different choices of the
distribution of features and ground truth (i.e., $\Pi$) to characterize the
precise impact of various types of spectral imbalance. While these will be the
main factors which we study below, the theorem also provides the flexibility
to analyze the effect of other parameters like the choice of loss function
$\mathcal{L}$ or regularization strength $r$.

#### A note on the proof technique:

The objective function in Equation (3) is quite similar to the min-max program
derived for the GMM with equal class covariances in [37]; however, there are a
few key differences in our proof technique which allow us to generalize that
result and obtain a more refined per-class characterization of the error.
Firstly, we use a decoupling trick that introduces two variables (one for each
class) for each variable in the objective function of [37]. This allows us to
isolate the quantities of interest for each class and apply the CGMT
separately for each class. Secondly, in contrast to [37], our result features
the second order Moreau envelope term, which functions as a way to link the
decision variables corresponding to each class.

###  3.1 Insights on spectral imbalance

We can use the predictions of Theorem 1 to precisely study the impact of
various types of spectral imbalance on per-class performance. In Figure 2, we
plot the asymptotic predictions of the per-class error and the class gap for
three different types of spectral imbalance which can arise in GMMs. To
isolate the effect of spectral imbalance, the predictions in this section fix
the amount of data from each class as identical (i.e. $\pi_{y}=0.5$), the
parameterization ratio $\delta=2$, regularization parameter $r=0.5$ and the
loss as the squared hinge loss, $\mathcal{L}(t)=\max(0,1-t)^{2}$. In each
case, we verify the theoretical predictions via numerical simulations averaged
over $50$ independent draws of $n=1000$ training examples. The results
indicate that the asymptotic predictions accurately describe the per-class
behavior even for moderate values of $n$ and $p$. We provide further details
of the setup for these simulations in Appendix A.

#### (A) Impact of eigenvalue scaling:

In this example, we vary the relative scale of some of the eigenvalues of
Class $1$ while fixing the target signal as
$\sqrt{p}\boldsymbol{\theta}^{*}_{j}=1$ for all $j$. Specifically, we fix the
eigenvalues of Class -1 to be either $0.5$ or $2$, in equal proportion. Then,
we set all the eigenvalues for Class 1 to be a multiplicative scaling $s\geq
1$ of the eigenvalues of Class -1. We can see in Figure 2(A) that as $s$
increases, the performance of Class 1 degrades severely while that of Class -1
also degrades, but to a lesser extent. In line with the general intuitions in
Section 2.1, this results in a net increase in the class gap.

#### (B) Impact of eigenvalue decay rate:

Fixing $\sqrt{p}\boldsymbol{\theta}^{*}_{j}=1$ for all $i$, we again consider
a bi-level covariance model, where the eigenvalues of each class take one of
two values: $2$ or $0.5$. We fix the proportion of larger eigenvalues in Class
-1 to be $0.5$ while varying the proportion $p\in[0,1]$ of larger eigenvalues
for Class $1$. This example indicates that there can be an important trade-off
between overall performance and the class gap: the choice $p=0$ (all small
eigenvalues) yields the best per-class performance for both classes while
$p=0.5$ minimizes the class gap.

#### (C) Impact of alignment with the target signal:

The previous notions of spectral imbalance ignored the relative shape of each
marginal distribution with respect to the target signal
$\boldsymbol{\theta}^{*}$. We now consider a situation where the two class
covariances are misaligned, so that either
$(\lambda_{j}^{(1)},\lambda_{j}^{(-1)})=(0.5,2)$ or
$(\lambda_{j}^{(1)},\lambda_{j}^{(-1)})=(2,0.5)$. We then increase the
magnitude of $\boldsymbol{\theta}^{*}_{j}$ by a factor $a$, only in the
directions $j\in[p]$ where $\lambda_{j}^{(-1)}=2$. Here, as we increase the
parameter $a\geq 1$, the overall signal strength increases, so the global
performance improves. However, due to the differences in the covariance
alignment, the improvement is not uniform between the two classes, and Class
1, which has smaller variance in the directions of increased signal strength,
improves more quickly. Interestingly, for large $a$ the class gap decreases as
the effect of large signal strength outweighs the differences between the
class spectra.

##  4 Spectral imbalance in pretrained features

In this section, we build on our theoretical findings to explore how the
framework of spectral imbalance may be used to understand and mitigate class
bias in the image representation space of pre-trained models.

###  4.1 Experimental setup

#### Settings.

We consider a common scenario in representation learning, where encoders are
used to extract features, and linear classifiers are trained on these features
for downstream evaluation. Formally, a dataset
$D=\left\\{\left(\mathbf{x}_{i},y_{i}\right)\right\\}_{i=1}^{n}$ of $n$ images
is used to train a network consisting of a pretrained encoder
$f_{\omega}(\cdot)$ and a linear classifier
$g_{\theta}(\cdot)=\langle\theta,\cdot\rangle$. The encoder produces a latent
representation for each image following
$\mathbf{z}_{i}=f_{\omega}(\mathbf{x}_{i})$. In this work, we aim to
understand the properties of the resulting representation space
$\mathcal{Z}=\\{\mathbf{z}_{i}\\}_{i=1}^{n}$, and how the (estimated) spectral
properties of the distribution on $\mathcal{Z}$ can be correlated to the
classification results of the classifier $g_{\theta}(\cdot)$ for each class.
Note that the role of the latent features $\\{\mathbf{z}_{i}\\}_{i=1}^{n}$ in
representation learning is directly comparable to the role of the original
features $\\{\mathbf{x}_{i}\\}_{i=1}^{n}$ in the preceding GMM; this is
because in both cases the downstream model is linear.

#### Empirical estimation of the class-dependent spectra.

To obtain the estimated eigenspectrum, we first estimate the empirical class-
dependent covariance matrix as:

$\boldsymbol{\Sigma}_{C}\left({f}_{\omega}\right)=\frac{1}{\Omega_{C}}\sum_{i\in\Omega_{C}}(\mathbf{z}_{i}-\overline{\mathbf{z}}_{i})(\mathbf{z}_{i}-\overline{\mathbf{z}}_{i}))^{T},$

where $C$ is a class, $\Omega_{C}$ denotes the set of examples with label
$y_{i}=C$, and $\overline{\mathbf{z}}_{i}$ denotes the empirical mean of
features with class $C$.

The eigenvalue decomposition of the covariance matrix is then computed as
$\boldsymbol{\Sigma}_{C}=\mathbf{V}_{C}\mathbf{\Lambda}_{C}\mathbf{V}_{C}^{-1}$,
where $\mathbf{\Lambda}_{C}$ is a diagonal matrix with nonnegative entries
$\lambda_{i}^{(C)}$, and the columns of $\mathbf{\mathbf{V}}_{C}$ correspond
to the eigenvectors of $\boldsymbol{\Sigma}_{C}$. Without loss of generality,
we assume that
$\lambda_{1}^{(C)}\geq\lambda_{2}^{(C)}\ldots\geq\lambda_{m}^{(C)}$, where $m$
is the rank of $\boldsymbol{\Sigma}_{C}$. The resulting set of eigenvalues
$\lambda_{i}^{(C)}$ is the (empirical) eigenspectrum of class $C$.

#### Pretrained networks.

In what follows, we evaluate the representation space of a diverse set of
classification models to understand their class bias. Specifically:

  * •

Residual networks: Using residual connections to bridge convolutional blocks,
ResNets are a class of deep convolutional neural networks (CNNs) that is
instrumental in many visual recognition tasks [18].

  * •

Improved CNNs: DenseNet [20] and EfficientNet [38] are two representative
convolutional architectures that aim to improve ResNets. They design different
strategies to build connections across layers to improve the information flow
inside the networks.

  * •

Vision transformers: The vision transformer splits an image into patches and
uses self-attention to study their interactions [14]. ViT aggregates global
information at earlier layers, creating significantly different
representations than CNNs [34].

  * •

Transformers without self-attention: Recent studies show that self-attention
is not required for obtaining good representations in vision. Along this line,
we study MLP-Mixer [40] and PoolFormer [48], which uses multi-layer
perceptrons and average pooling to mix information across patches,
respectively.

We found all checkpoints of the pretrained models in Torchvision [29] and timm
[47] (see details in Appendix B). For all experiments, we use the standard
ImageNet ILSVRC 2012 dataset [10], which contains $C=1000$ object classes with
an average of 1281/50 training/validation images per class.

Figure 3: Examining the relationship between class-dependent spectra and
performance. (left) The spectral offset of each class vs. their classification
accuracy, computed for ResNet-50 on the validation set of ImageNet. (right)
Pearson correlation coefficient between class accuracy and individual
eigenvalues (blue) and the power law offset (red).

###  4.2 Spectra correlate with class-wise performance

#### Individual eigenvalues.

We first analyze the correlation between the class-wise performance and the
magnitude of individual eigenvalues of each class. To do this, we compute the
Pearson correlation coefficient (PCC) between the set of eigenvalues
$\\{\lambda_{j}^{(c)}\\}$ (validation set) and the set of across-class
accuracies, $\\{\text{Accuracy}(c)\\}$, for every eigenvalue index $j$. In
Figure 3, we observe that the class-wise accuracy shows a strong negative
correlation with most individual eigenvalues (right), in line with the
theoretical results on eigenvalue scaling in Figure 2(A). Across the 11 models
examined, we obtained an average maximum negative correlation of -0.69.
Interestingly, unlike the examples in Section 3.1, the first few eigenvalues
do not show a strong correlation for most models, potentially illustrating
unique properties of the features learned by real-world encoders.

#### Power law decay offsets.

Natural images are known to exhibit a power law decay in their eigenvalues
[36]. Recent work has shown that this also holds in visual representations in
pretrained models [15] and can be used to examine the quality of learned
representations. Thus, we fit the class conditional spectrum to
$\lambda_{i}=ai^{-b}$, and observe how the parameters $(a,b)$ indicate the
class-wise accuracy. Interestingly, we observed that the scale $a$ (the offset
on a log-scale) correlates most strongly with class accuracy (an average of
-0.68 across 11 models), while the power (i.e. rate of decay) $b$ does not
strongly correlate with class-wise performance. This phenomenon demonstrates
that there is a nuanced relationship between the specific distribution and
decay rate of eigenvalues (cf. Figure 2(B)) and the class performance. We
provide further details and also measure the correlation between other decay
rate metrics and class-wise performance in Appendix B.2.

###  4.3 Spectral imbalance in your pretrained model

Next, we conduct a systematic investigation of the per-class accuracy
discrepancies across encoders and show that spectral imbalance is often a
measurable property of the encoder. Surprisingly, out of the 55 unique pairs
of encoders that we consider, an average of 31% classes had a ranking (with
duplicates) difference over 100 out of $C=1000$ total classes, with the input
data held constant. To better understand the large variability of per-class
accuracy across encoders, we propose the Spectral Quantile Score (SQS), which
measures the spectral imbalance between classes in a given encoder.

Spectral Quantile Score. Writing the set of per-class accuracies as a sorted
list of numbers $\\{{Acc}_{1},\dots,{Acc}_{C}\\}$ in descending order, we
define the empirical class bias score of an encoder as:

$\textit{Class
bias}=\left(\sum_{k=1}^{L}{Acc}_{k}-\sum_{k=C-L+1}^{C}{Acc}_{k}\right)/\left(L\times\overline{Acc}\right),$

where $C$ is the total number of classes, $\overline{Acc}$ is the average
accuracy over all classes, and $L$ is a selected cutoff. In our experiments on
ImageNet, we set $L=100$ throughout.

To compute the imbalance across classes in their spectra, we can similarly
sort our per-class spectral metric of interest (i.e., spectral offset,
specific eigenvalues) as $\\{s_{1},\dots,s_{C}\\}$ and compute the the
Spectral Quantile Score (SQS):

$\text{SQS}=s_{L}/s_{1}.$

Again, we set $L=100$ for our experiments. As shown in Figure 4(A), we found
the SQS of different encoders is indicative of their empirical class bias
(0.90 PCC), where latent spaces with a higher SQS would likely give higher
empirical class bias. The strong correlation between SQS and empirical class
bias emphasizes the importance of investigating the spectra imbalance in
encoders, which accurately reflects and evaluates the encoders’ empirical
class bias. Moreover, as the worst class performance is often strongly
associated with the final average performance of an encoder [4], understanding
spectral imbalance provides an additional lens into the representation space
without training actual classifiers.

#### Testing for class disparity in a new encoder.

Next, we investigate how class-dependent spectra can be used to estimate the
performance of a new encoder. Following [5], we used a one-sided Welch’s
t-test [45] to validate our hypothesis that the per-class accuracy is
significantly lower when their training set spectra have a higher offset
parameter $a$. We define the random variable as the accuracy difference
between two encoders
$\Delta_{f_{1},f_{2}}(c)\coloneqq\operatorname{Acc}_{f_{1}}(c)-\operatorname{Acc}_{f_{2}}(c)$,
and $\Delta_{-}$ represents the set of classes with spectral offset difference
$a_{f_{1}}(c)-a_{f_{2}}(c)<0$ being negative. We define the null hypothesis as
$H_{0}=\mathbb{E}[\Delta]>\mathbb{E}\left[\Delta_{-}\right]$.Intuitively,
rejecting the hypothesis means the classes with a higher spectral property
would give lower class-wise accuracies. We obtain that there is enough
evidence to reject this hypothesis with 95% confidence for 98 out of 110 pairs
of encoders; and 99% confidence for 80 out of 110 pairs of encoders. This
demonstrates that spectral properties might reliably predict class-wise
accuracies for new encoders, despite the noise in spectrum estimation.

Figure 4: Selecting model and data with spectra. (A) Given different encoders,
the Spectral Quantile Score (SQS) is predictive of the empirical class bias of
the representation spaces. Note that SQS is estimated on training set without
deploying the classifier(s). (B) Given different data augmentation plans, we
can use the class-level spectra to assign data to their optimal augmentation
plan in a class-dependent way. This assignment can be used at test time to re-
factor the prediction and boost performance across all classes without any re-
training or modification to the encoder.

###  4.4 Combine augmentations using spectral information

Recent work identified that commonly used data augmentations can in fact
worsen class gap [5]. Thus, we sought to study the effect of _data
augmentation_ on class disparity and ask whether different augmentations can
be used to alleviate gaps in class accuracies.

#### Do different augmentations impact spectral imbalance?

To begin, we supplement the results of Section 4.3 by showing that spectral
imbalance correlates strongly with class gap not only across encoders, but
also across data transformations. Following [19], we generated 16 versions of
ImageNet where the images are transformed differently. Specifically, given a
sample ${\bf x}$ from our train/test dataset $\mathcal{D}$, we start by
transforming every image with the 16 candidate augmentations as
$\mathbf{x}^{\ell}=t_{\ell}(\mathbf{x})$, where
$t_{\ell}\in\mathcal{T}_{\ell}$ is a sampled augmentation operation from the
$\ell^{\rm th}$ augmentation plan. After feeding these transformed images
through our pretrained encoder $f_{\omega}$, we obtain 16 different sets of
latents $\\{{\bf z}_{\ell}=f_{\omega}(\mathbf{x}^{\ell})\\}_{\ell=1}^{16}$.
Then, our prediction corresponding to the $\ell^{th}$ augmented test sample is
given by the $C$-dimensional logit output $\mathbf{L}_{\ell}=g_{\theta}({\bf
z}_{\ell})$.

As in Section 4.2, we fit a power law to all classes and use the offset
parameter $a$ as the studied spectral property. Between the training set
spectral properties and the testing set class bias, we compute the SQS score
across all 16 types of augmentations and obtain a PCC of $0.90$, demonstrating
strong positive correlation. Within each class, the spectral property is also
statistically significant for $78.9\%$ out of $1000$ classes. See Appendix B.4
for more details.

#### An ensembling method to combine augmentations using spectral information.

Based on the observed correlation between imbalance of the spectral offset and
performance for each class, we propose a spectral re-factoring method that
adaptively combines the predictions across different augmented views at _test
time_ to improve performance. To do this, we extract the spectral offset
parameter $a$ for each class ($C=1000$) across all candidate augmentations
($K=16$) on the training dataset. This results in a matrix
$\mathbf{M}\in\mathbb{R}^{K\times C}$, where each entry
$M_{\ell,c}=a_{\ell,c}$ denotes the offset parameter for all latents $\\{{\bf
z}_{\ell}\\}$ in class $c$.

Consider a test sample $\mathbf{x}$. Suppose that an ‘oracle’ could give us
its true class $c^{*}$. Then, we would use the prediction corresponding to the
augmented view that achieves minimum ‘spectral score’ of class $c^{*}$, i.e.
use the augmentation $\ell^{*}$ that minimizes $M_{\ell,c^{*}}$. We depict
this idea in Figure 4(B) with two candidates Zoom Blur (ZB) and Snow (SW). In
this case, ZB achieves a smaller spectral score for 623/1000 classes, while SW
acheives a smaller spectral score for the other 377/1000 classes. Thus, our
oracle would select the predictions of ZB for the 623 classes with smaller
spectra and SW for the next 377 classes. This approach would yield significant
improvement across all classes: $6.0\%$ on 623 classes (blue) and $10.2\%$ on
377 classes (yellow).

Of course, in reality we do not have access to the class information $c^{*}$
to apply the ‘correct augmentation’. Instead, we propose an ensembling method
for assigning final class probabilities based upon the spectral property
matrix ${\bf M}$:

  * (Step 1) Pass $K$ candidate augmentations of each sample through $f$ and $g$ to produce a multi-view logits matrix $\mathbf{L}\in\mathbb{R}^{K\times C}$, where $\mathbf{L}_{\ell}$ corresponds to the logits generated by prediction on augmented data $\mathbf{x}^{\ell}$.

  * (Step 2) Create a new logit vector $\hat{{\bf l}}_{c}={\bf L}_{\ell^{*}(c),c}$ where $\ell^{*}(c)$ _minimizes_ $M_{\ell,c}$. Intuitively, we select the logit corresponding to the ‘optimal’ augmentation for class $c$, based upon the spectral scores in $\bf M$.

  * (Step 3) Classify test data $\mathbf{x}$ as $c(\mathbf{x})={\arg\max}_{c\in[C]}\hat{L}_{c}$.

This re-factored prediction is depicted in Figure 4(B). Essentially, the
procedure first _estimates_ the correct augmentation from the training set for
each class to use in steps 1 and 2, selects the corresponding logit for that
class, and uses these adaptively selected logits in a standard classification
procedure in step 3. This ensembling procedure improves Zoom Blur ($65.01\%$)
and Snow ($65.12\%$) to a combined accuracy of $67.616\%$, giving an average
performance improvement of $2.55\%$ and an average class gap improvement of
$3.52\%$ without any re-training required.

##  5 Related work

Class-dependent generalization and class bias. Recently, [5, 23] put forward
the interesting observation that data augmentations can create class bias, and
that the issue worsens the stronger the augmentation(s) is. In contrast to our
work, these works focus exclusively on the impact of data augmentation and do
not identify or characterize the role of spectra in class bias. They propose a
different hypothesis that is less quantifiable; in particular, that classes
that are inherently more ‘fine-grained’, or harder to distinguish, are most
affected. Comparatively, our proposed measures of spectral imbalance are
precise, quantitative, and demonstrated to correlate with class bias through
formal statistical analysis.

The role of spectra in generalization. Many recent works have highlighted the
importance of the data spectrum in generalization [6, 32, 24], especially in
the overparameterized regime. Specifically, the works [8, 44, 7, 43]
characterize the behavior of overparameterized linear classifiers in GMMs
through non-asymptotic, finite-sample bounds and show good generalization
under favorable spectral properties of the data. However, they all assume
equal class covariances and do not explicitly consider the effects of spectral
imbalance. Another line of work provides exact asymptotic bounds on the
classification error achieved by linear classifiers in the GMM [11, 28, 27,
22, 37, 21]. Of these, only [27] allow for different covariances between
classes. Their work studies a more general multiclass setting, but does not
systematically study per-class generalization. By contrast, we focus on a
simpler binary classification setting and use an alternative proof technique
based on Gaussian comparison inequalities to obtain a much simpler expression
that is easier to numerically evaluate, and thus allows us to model various
spectral imbalances. Finally, our empirical results estimate the eigenspectra
either on validation/test data, on augmented training data, or on training
data but non-zero training error. This circumvents “neural collapse" on
training data [33] which would yield misleading estimates of eigenspectra.

Evaluating representations. Assessing the quality of representations is a
critical aspect of representation learning. The importance stems from its
ability to bypass the need for training classifiers, especially when the
quality and quantity of downstream data are lacking [30, 25, 26].
Representations can be studied from the perspective of manifold analysis [16];
Previous works show that estimated geometric properties like intrinsic
dimension correlate with performance [3, 9, 13, 42]. Recently, [15, 1] uses
the power law decay of eigenspectrum to measure the quality of
representations, and follow-up works show that spectral properties can also be
used to improve self-supervised learning [17, 50, 46]. In contrast to these
works, we especially evaluate the spectral properties of the representation
space from the perspective of class bias and class-dependent generalization
error.

##  6 Discussion

In this work, we have introduced the concept of spectral imbalance as a new
way to characterize class-dependent bias. We studied spectral imbalance in
theory and in practice, and provide a new framework for studying class and
spectral imbalance. While we identify spectral imbalance as _one of_ the
factors influencing class disparity, there could be others which we have as
yet not identified. Moreover, our theory assumes linear models and our
experiments assume pre-trained encoders. In the future, we would like to
understand how feature learning in neural networks could lead to spectral
imbalance in the first place. We hope such understanding will help us
effectively mitigate the class bias issue, either through re-training or post-
hoc manipulation of pre-trained features.

## Impact Statement

Our work provides new insights into how to mitigate class biases, and can have
major societal benefits in terms of fairness and auditing of pretrained
models.

## References

  * [1] Kumar K Agrawal, Arnab Kumar Mondal, Arna Ghosh and Blake Richards  “Assessing Representation Quality in Self-Supervised Learning by measuring eigenspectrum decay”  In _Advances in Neural Information Processing Systems_ 35, 2022, pp. 17626–17638
  * [2] Per Kragh Andersen and Richard D Gill  “Cox’s regression model for counting processes: a large sample study”  In _The annals of statistics_ JSTOR, 1982, pp. 1100–1120
  * [3] Alessio Ansuini, Alessandro Laio, Jakob H Macke and Davide Zoccolan  “Intrinsic dimension of data representations in deep neural networks”  In _Advances in Neural Information Processing Systems_ 32, 2019
  * [4] Martin Arjovsky, Kamalika Chaudhuri and David Lopez-Paz  “Throwing away data improves worst-class error in imbalanced classification”  In _arXiv preprint arXiv:2205.11672_ , 2022
  * [5] Randall Balestriero, Leon Bottou and Yann LeCun  “The effects of regularization and data augmentation are class dependent”  In _arXiv preprint arXiv:2204.03632_ , 2022
  * [6] Peter L Bartlett, Philip M Long, Gábor Lugosi and Alexander Tsigler  “Benign overfitting in linear regression”  In _Proceedings of the National Academy of Sciences_ 117.48 National Acad Sciences, 2020, pp. 30063–30070
  * [7] Yuan Cao, Quanquan Gu and Mikhail Belkin  “Risk bounds for over-parameterized maximum margin classification on sub-gaussian mixtures”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 8407–8418
  * [8] Niladri S Chatterji and Philip M Long  “Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime.”  In _J. Mach. Learn. Res._ 22, 2021, pp. 129–1
  * [9] Uri Cohen, SueYeon Chung, Daniel D Lee and Haim Sompolinsky  “Separability and geometry of object manifolds in deep neural networks”  In _Nature communications_ 11.1 Nature Publishing Group UK London, 2020, pp. 746
  * [10] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li and Li Fei-Fei  “Imagenet: A large-scale hierarchical image database”  In _2009 IEEE conference on computer vision and pattern recognition_ , 2009, pp. 248–255  Ieee
  * [11] Zeyu Deng, Abla Kammoun and Christos Thrampoulidis  “A model of double descent for high-dimensional binary linear classification”  In _Information and Inference: A Journal of the IMA_ 11.2 Oxford University Press, 2022, pp. 435–495
  * [12] Oussama Dhifallah and Yue Lu  “On the inherent regularization effects of noise injection during training”  In _International Conference on Machine Learning_ , 2021, pp. 2665–2675  PMLR
  * [13] Diego Doimo, Aldo Glielmo, Alessio Ansuini and Alessandro Laio  “Hierarchical nucleation in deep neural networks”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 7526–7536
  * [14] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold and Sylvain Gelly  “An image is worth 16x16 words: Transformers for image recognition at scale”  In _arXiv preprint arXiv:2010.11929_ , 2020
  * [15] Arna Ghosh, Arnab Kumar Mondal, Kumar Krishna Agrawal and Blake Richards  “Investigating power laws in deep representation learning”  In _arXiv preprint arXiv:2202.05808_ , 2022
  * [16] Michael Hauser and Asok Ray  “Principles of Riemannian geometry in neural networks”  In _Advances in neural information processing systems_ 30, 2017
  * [17] Bobby He and Mete Ozay  “Exploring the gap between collapsed & whitened features in self-supervised learning”  In _International Conference on Machine Learning_ , 2022, pp. 8613–8634  PMLR
  * [18] Kaiming He, Xiangyu Zhang, Shaoqing Ren and Jian Sun  “Deep residual learning for image recognition”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778
  * [19] Dan Hendrycks and Thomas Dietterich  “Benchmarking neural network robustness to common corruptions and perturbations”  In _arXiv preprint arXiv:1903.12261_ , 2019
  * [20] Gao Huang, Zhuang Liu, Laurens Van Der Maaten and Kilian Q Weinberger  “Densely connected convolutional networks”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 4700–4708
  * [21] Adel Javanmard and Mahdi Soltanolkotabi  “Precise statistical analysis of classification accuracies for adversarial training”  In _The Annals of Statistics_ 50.4 Institute of Mathematical Statistics, 2022, pp. 2127–2156
  * [22] Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak and Christos Thrampoulidis  “Label-imbalanced and group-sensitive classification under overparameterization”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 18970–18983
  * [23] Polina Kirichenko, Randall Balestriero, Mark Ibrahim, Shanmukha Ramakrishna Vedantam, Hamed Firooz and Andrew Gordon Wilson  “Understanding the class-specific effects of data augmentations”  In _ICLR 2023 Workshop on Pitfalls of limited data and computation for Trustworthy ML_ , 2023
  * [24] Chi-Heng Lin, Chiraag Kaushik, Eva L Dyer and Vidya Muthukumar  “The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspective”  In _arXiv preprint arXiv:2210.05021_ , 2022
  * [25] Ran Liu, Mehdi Azabou, Max Dabagia, Jingyun Xiao and Eva Dyer  “Seeing the forest and the tree: Building representations of both individual and collective dynamics with transformers”  In _Advances in neural information processing systems_ 35, 2022, pp. 2377–2391
  * [26] Ran Liu, Ellen L Zippi, Hadi Pouransari, Chris Sandino, Jingping Nie, Hanlin Goh, Erdrin Azemi and Ali Moin  “Frequency-aware masked autoencoders for multimodal pretraining on biosignals”  In _arXiv preprint arXiv:2309.05927_ , 2023
  * [27] Bruno Loureiro, Gabriele Sicuro, Cédric Gerbelot, Alessandro Pacco, Florent Krzakala and Lenka Zdeborová  “Learning gaussian mixtures with generalized linear models: Precise asymptotics in high-dimensions”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 10144–10157
  * [28] Xiaoyi Mai, Zhenyu Liao and Romain Couillet  “A large scale analysis of logistic regression: Asymptotic performance and new insights”  In _ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2019, pp. 3357–3361  IEEE
  * [29] Sébastien Marcel and Yann Rodriguez  “Torchvision the machine-vision package of torch”  In _Proceedings of the 18th ACM international conference on Multimedia_ , 2010, pp. 1485–1488
  * [30] Charles H Martin, Tongsu Peng and Michael W Mahoney  “Predicting trends in the quality of state-of-the-art neural networks without access to training or testing data”  In _Nature Communications_ 12.1 Nature Publishing Group UK London, 2021, pp. 4122
  * [31] Andrea Montanari, Feng Ruan, Youngtak Sohn and Jun Yan  “The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime”  In _arXiv preprint arXiv:1911.01544_ , 2019
  * [32] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu and Anant Sahai  “Classification vs regression in overparameterized regimes: Does the loss function matter?”  In _Journal of Machine Learning Research_ 22.222, 2021, pp. 1–69  URL: http://jmlr.org/papers/v22/20-603.html
  * [33] Vardan Papyan, XY Han and David L Donoho  “Prevalence of neural collapse during the terminal phase of deep learning training”  In _Proceedings of the National Academy of Sciences_ 117.40 National Acad Sciences, 2020, pp. 24652–24663
  * [34] Maithra Raghu, Thomas Unterthiner, Simon Kornblith, Chiyuan Zhang and Alexey Dosovitskiy  “Do vision transformers see like convolutional neural networks?”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 12116–12128
  * [35] Jiawei Ren, Cunjun Yu, Xiao Ma, Haiyu Zhao and Shuai Yi  “Balanced meta-softmax for long-tailed visual recognition”  In _Advances in neural information processing systems_ 33, 2020, pp. 4175–4186
  * [36] Daniel L Ruderman  “The statistics of natural images”  In _Network: computation in neural systems_ 5.4 IOP Publishing, 1994, pp. 517
  * [37] Hossein Taheri, Ramtin Pedarsani and Christos Thrampoulidis  “Asymptotic behavior of adversarial training in binary classification”  In _arXiv preprint arXiv:2010.13275_ , 2020
  * [38] Mingxing Tan and Quoc Le  “Efficientnet: Rethinking model scaling for convolutional neural networks”  In _International conference on machine learning_ , 2019, pp. 6105–6114  PMLR
  * [39] Christos Thrampoulidis, Ehsan Abbasi and Babak Hassibi  “Precise error analysis of regularized $M$-estimators in high dimensions”  In _IEEE Transactions on Information Theory_ 64.8 IEEE, 2018, pp. 5592–5628
  * [40] Ilya O Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers and Jakob Uszkoreit  “Mlp-mixer: An all-mlp architecture for vision”  In _Advances in neural information processing systems_ 34, 2021, pp. 24261–24272
  * [41] Alexander Tsigler and Peter L Bartlett  “Benign overfitting in ridge regression”  In _arXiv preprint arXiv:2009.14286_ , 2020
  * [42] Lucrezia Valeriani, Diego Doimo, Francesca Cuturello, Alessandro Laio, Alessio Ansuini and Alberto Cazzaniga  “The geometry of hidden representations of large transformer models”  In _arXiv preprint arXiv:2302.00294_ , 2023
  * [43] Ke Wang, Vidya Muthukumar and Christos Thrampoulidis  “Benign overfitting in multiclass classification: All roads lead to interpolation”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 24164–24179
  * [44] Ke Wang and Christos Thrampoulidis  “Binary classification of Gaussian mixtures: abundance of support vectors, benign overfitting and regularization”  In _arXiv preprint arXiv:2011.09148_ , 2021
  * [45] Bernard L Welch  “The generalization of ‘STUDENT’S’problem when several different population varlances are involved”  In _Biometrika_ 34.1-2 Oxford University Press, 1947, pp. 28–35
  * [46] Xi Weng, Yunhao Ni, Tengwei Song, Jie Luo, Rao Muhammad Anwer, Salman Khan, Fahad Shahbaz Khan and Lei Huang  “Modulate Your Spectrum in Self-Supervised Learning”  In _arXiv preprint arXiv:2305.16789_ , 2023
  * [47] Ross Wightman  “PyTorch Image Models”  In _GitHub repository_ GitHub, https://github.com/rwightman/pytorch-image-models, 2019  DOI: 10.5281/zenodo.4414861
  * [48] Weihao Yu, Mi Luo, Pan Zhou, Chenyang Si, Yichen Zhou, Xinchao Wang, Jiashi Feng and Shuicheng Yan  “Metaformer is actually what you need for vision”  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2022, pp. 10819–10829
  * [49] Yifan Zhang, Bingyi Kang, Bryan Hooi, Shuicheng Yan and Jiashi Feng  “Deep long-tailed learning: A survey”  In _IEEE Transactions on Pattern Analysis and Machine Intelligence_ IEEE, 2023
  * [50] Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz and Irwin King  “Spectral feature augmentation for graph contrastive learning and beyond”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 37.9, 2023, pp. 11289–11297
  * [51] Jianggang Zhu, Zheng Wang, Jingjing Chen, Yi-Ping Phoebe Chen and Yu-Gang Jiang  “Balanced contrastive learning for long-tailed visual recognition”  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 6908–6917

## Appendix

##  Appendix A Theoretical Results for the Gaussian Mixture Model

###  A.1 Proofs

This section contains the proofs for spectrally-imbalanced GMM setting in
Section 2.1.

######  Lemma 2 (Expression for the POE in the imbalanced GMM).

In the GMM setting of Section 2.1, given an estimator
$\hat{\boldsymbol{\theta}}\in\mathbb{R}^{p}$, the per-class error and class
gap satisfy

$\displaystyle\text{POE}(\hat{\boldsymbol{\theta}}|y)$
$\displaystyle\coloneqq\operatorname{\mathbb{P}}\\{\text{sign}(\mathbf{x}^{\top}\hat{\boldsymbol{\theta}})\neq
y|\mathbf{x}\text{ in class
}y\\}=Q\left(\frac{\langle\hat{\boldsymbol{\theta}},\boldsymbol{\theta}^{*}\rangle}{\|\boldsymbol{\Sigma}_{y}^{1/2}\hat{\boldsymbol{\theta}}\|_{2}}\right)$
$\displaystyle\text{ClassGap}(\hat{\boldsymbol{\theta}})$
$\displaystyle=\left\lvert
Q\left(\frac{\langle\hat{\boldsymbol{\theta}},\boldsymbol{\theta}^{*}\rangle}{\|\boldsymbol{\Sigma}_{1}^{1/2}\hat{\boldsymbol{\theta}}\|_{2}}\right)-Q\left(\frac{\langle\hat{\boldsymbol{\theta}},\boldsymbol{\theta}^{*}\rangle}{\|\boldsymbol{\Sigma}_{-1}^{1/2}\hat{\boldsymbol{\theta}}\|_{2}}\right)\right\rvert$
$\displaystyle\leq\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}\min_{y}\frac{\langle\tilde{\boldsymbol{\theta}},\boldsymbol{\theta}^{*}\rangle^{2}}{\lVert\boldsymbol{\Sigma}_{y}^{1/2}\hat{\boldsymbol{\theta}}\rVert_{2}^{2}}\right)\lvert\langle\hat{\boldsymbol{\theta}},\boldsymbol{\theta}^{*}\rangle\rvert\left\lvert\lVert\boldsymbol{\Sigma}_{y}^{1/2}\hat{\boldsymbol{\theta}}\rVert_{2}^{-1}-\lVert\boldsymbol{\Sigma}_{y}^{1/2}\hat{\boldsymbol{\theta}}\rVert_{2}^{-1}\right\rvert,$

where $Q(\cdot)$ is the Gaussian Q-function.

###### Proof.

Note we can write $\mathbf{x}$ as
$y\boldsymbol{\theta}^{*}+\boldsymbol{\Sigma}_{y}^{1/2}\mathbf{z}$, for
$\mathbf{z}\sim\mathcal{N}(0,\mathbf{I})$. Then,

$\displaystyle\operatorname{\mathbb{P}}\\{\text{sign}(\mathbf{x}^{\top}\hat{\boldsymbol{\theta}})\neq
y|\mathbf{x}\text{ in class }y\\}$
$\displaystyle=\operatorname{\mathbb{P}}\\{y(\mathbf{x}^{\top}\hat{\boldsymbol{\theta}})<0|\mathbf{x}\text{
in class }y\\}$
$\displaystyle=\operatorname{\mathbb{P}}\\{y((y\boldsymbol{\theta}^{*}+\boldsymbol{\Sigma}_{y}^{1/2}\mathbf{z})^{\top}\hat{\boldsymbol{\theta}})<0\\}$
$\displaystyle=\operatorname{\mathbb{P}}\\{\langle\hat{\boldsymbol{\theta}},\boldsymbol{\theta}^{*}\rangle+y\hat{\boldsymbol{\theta}}^{\top}\boldsymbol{\Sigma}_{y}^{1/2}\mathbf{z}<0\\}$
$\displaystyle=\operatorname{\mathbb{P}}\\{\langle\hat{\boldsymbol{\theta}},\boldsymbol{\theta}^{*}\rangle+\lVert\boldsymbol{\Sigma}_{y}^{1/2}\hat{\boldsymbol{\theta}}\rVert_{2}z<0\\}$
$\displaystyle=\operatorname{\mathbb{P}}\left\\{z<-\frac{\langle\hat{\boldsymbol{\theta}},\boldsymbol{\theta}^{*}\rangle}{\lVert\boldsymbol{\Sigma}_{y}^{1/2}\hat{\boldsymbol{\theta}}\rVert_{2}}\right\\}$
$\displaystyle=Q\left(\frac{\langle\hat{\boldsymbol{\theta}},\boldsymbol{\theta}^{*}\rangle}{\|\boldsymbol{\Sigma}_{y}^{1/2}\hat{\boldsymbol{\theta}}\|_{2}}\right),$

where, in the fourth line, we use the fact that
$y\hat{\boldsymbol{\theta}}^{\top}\boldsymbol{\Sigma}_{y}^{1/2}\mathbf{z}\overset{d}{=}\lVert\boldsymbol{\Sigma}_{y}^{1/2}\hat{\boldsymbol{\theta}}\rVert_{2}z,$
for a scalar $z\sim\mathcal{N}(0,1).$ The upper bound on the class gap follows
from the mean value theorem, after noting that the derivative of the
Q-function is the negative of the Gaussian pdf. ∎

Before proceeding with the full proof of our main technical result, we first
provide a brief sketch of the proof technique and the primary differences from
previous works which study the balanced GMM setting.

#### Proof outline and remarks

Our proof generalizes the result of [37] to the case where each class has a
different covariance and allows us to characterize the error in a per-class
way. To make the connections to this analysis (and the key differences) clear,
we make an attempt to follow the same notation when possible. Due to the
covariate imbalance between classes, our analysis of the ERM objective
function differs in a few important respects. Typically, application of the
CGMT to anisotropic covariates requires a “whitening” step to obtain standard
normal variables. The key step in our proof is to separately whiten the data
from each class, which “decouples” the objective function into a portion
corresponding to each class with its own decision variables. These two
portions are tied together via the introduction of a new constraint.

We then invoke the CGMT once for each class (or more precisely, via a
multivariate extension of [12]) to write the problem as an equivalent
“Auxiliary Optimization” (AO) objective which has a similarly decoupled form.
Each of these portions of the AO can be simplified separately using the
same“scalarization” techniques as in [37]. The additional constraint we
introduced during the whitening step then plays a role in the final step of
the proof, yielding the second-order Moreau envelope function which depends on
the decision variables corresponding to both classes. Finally, we note that,
unlike [37], we do not consider the effect of adversarial training; however,
the same proof technique can be extended in a natural way to deal with this
case.

We now proceed to the full proof of Theorem 1

###### Proof of Theorem 1.

We first analyze the ERM optimization through a series of simplifications.

$\displaystyle\min_{\boldsymbol{\theta}\in\mathbb{R}^{p}}\frac{1}{n}\sum_{i=1}^{n}\mathcal{L}(y_{i}\langle\mathbf{x}_{i},\boldsymbol{\theta}\rangle)+r\lVert\boldsymbol{\theta}\rVert_{2}^{2}$
$\displaystyle=\min_{\boldsymbol{\theta}\in\mathbb{R}^{p}}\frac{1}{n}\sum_{i=1}^{n}\mathcal{L}(y_{i}\langle
y_{i}\boldsymbol{\theta}^{*}+\boldsymbol{\Sigma}_{y_{i}}^{1/2}\mathbf{z}_{i},\boldsymbol{\theta}\rangle)+r\lVert\boldsymbol{\theta}\rVert_{2}^{2}$
$\displaystyle\overset{d}{=}\min_{\boldsymbol{\theta}\in\mathbb{R}^{p}}\frac{1}{n}\sum_{i=1}^{n}\mathcal{L}(\langle\boldsymbol{\theta}^{*}+\boldsymbol{\Sigma}_{y_{i}}^{1/2}\mathbf{z}_{i},\boldsymbol{\theta}\rangle)+r\lVert\boldsymbol{\theta}\rVert_{2}^{2},$

where the last line follows from
$y_{i}\mathbf{z}_{i}\overset{d}{=}\mathbf{z}_{i}$. Then, we re-index the data
points as $\mathbf{z}_{y,i}$ for $y\in\\{-1,1\\}$ and $i\in[n_{y}]$ to get

$\displaystyle\min_{\boldsymbol{\theta}\in\mathbb{R}^{p}}\frac{1}{n}\sum_{y\in\\{-1,1\\}}\sum_{i=1}^{n_{y}}\mathcal{L}(\langle\boldsymbol{\theta}^{*}+\boldsymbol{\Sigma}_{y}^{1/2}\mathbf{z}_{y,i},\boldsymbol{\theta}\rangle)+r\lVert\boldsymbol{\theta}\rVert_{2}^{2}$

Next, let
$\tilde{\boldsymbol{\theta}}_{y}\coloneqq\boldsymbol{\Sigma}_{y}^{1/2}\boldsymbol{\theta}$
and
$\tilde{\boldsymbol{\theta}}^{*}_{y}\coloneqq\boldsymbol{\Sigma}_{y}^{-1/2}\boldsymbol{\theta}^{*}$.
We now use a change of variable to write the problem as an optimization over
the two variables $\tilde{\boldsymbol{\theta}}_{1}$ and
$\tilde{\boldsymbol{\theta}}_{-1}$ while enforcing that both correspond to the
same $\boldsymbol{\theta}$.

$\displaystyle\min_{\begin{subarray}{c}\tilde{\boldsymbol{\theta}}_{y}\in\mathbb{R}^{p}\\\
\text{s.t.}\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\theta}}_{1}=\boldsymbol{\Sigma}_{-1}^{-1/2}\tilde{\boldsymbol{\theta}}_{-1}\end{subarray}}r\lVert\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\theta}}_{1}\rVert_{2}^{2}+\frac{1}{n}\sum_{y\in\\{-1,1\\}}\sum_{i=1}^{n_{y}}\mathcal{L}(\langle\tilde{\boldsymbol{\theta}}_{y},\tilde{\boldsymbol{\theta}}^{*}_{y}\rangle+\langle\mathbf{z}_{y,i},\tilde{\boldsymbol{\theta}}_{y}\rangle)$

By duality, we can now write this as a min-max problem.

$\displaystyle=\min_{\tilde{\boldsymbol{\theta}}_{y}\in\mathbb{R}^{p}}\max_{\mathbf{w}\in\mathbb{R}^{p}}\quad
r\lVert\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\theta}}_{1}\rVert_{2}^{2}+\langle\mathbf{w},\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\theta}}_{1}-\boldsymbol{\Sigma}_{-1}^{-1/2}\tilde{\boldsymbol{\theta}}_{-1}\rangle+\frac{1}{n}\sum_{y}\sum_{i=1}^{n_{y}}\mathcal{L}(\langle\tilde{\boldsymbol{\theta}}_{y},\tilde{\boldsymbol{\theta}}^{*}_{y}\rangle+\langle\mathbf{z}_{y,i},\tilde{\boldsymbol{\theta}}_{y}\rangle)$
$\displaystyle=\min_{\tilde{\boldsymbol{\theta}}_{y}\in\mathbb{R}^{p}}\max_{\mathbf{w}\in\mathbb{R}^{p}}\quad
r\lVert\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\theta}}_{1}\rVert_{2}^{2}+\langle\mathbf{w},\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\theta}}_{1}-\boldsymbol{\Sigma}_{-1}^{-1/2}\tilde{\boldsymbol{\theta}}_{-1}\rangle$
$\displaystyle\hskip
80.00012pt+\frac{1}{n}\sum_{y}\left[\sum_{i=1}^{n_{y}}\mathcal{L}(\langle\tilde{\boldsymbol{\theta}}_{y},\tilde{\boldsymbol{\theta}}^{*}_{y}\rangle+\langle\mathbf{z}_{y,i},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\rangle+\langle\mathbf{z}_{y,i},\boldsymbol{\Theta}_{y}^{\perp}\tilde{\boldsymbol{\theta}}_{y}\rangle)\right]$

where we define
$\boldsymbol{\Theta}_{y}\coloneqq\frac{\tilde{\boldsymbol{\theta}}^{*}_{y}\tilde{\boldsymbol{\theta}}^{*\top}_{y}}{\lVert\tilde{\boldsymbol{\theta}}^{*}_{y}\rVert_{2}^{2}}$
as the orthogonal projection matrix onto
$\tilde{\boldsymbol{\theta}}^{*}_{y}$. Now, introduce the constraints
$v_{y,i}=\langle\tilde{\boldsymbol{\theta}}_{y},\tilde{\boldsymbol{\theta}}^{*}_{y}\rangle+\langle\mathbf{z}_{y,i},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\rangle+\langle\mathbf{z}_{y,i},\boldsymbol{\Theta}_{y}^{\perp}\tilde{\boldsymbol{\theta}}_{y}\rangle$,
corresponding to dual variables $\mathbf{u}_{y}$ to get:

$\displaystyle\min_{\begin{subarray}{c}\tilde{\boldsymbol{\theta}}_{y}\in\mathbb{R}^{p}\\\
\mathbf{v}_{y}\in\mathbb{R}^{n_{y}}\end{subarray}}\max_{\begin{subarray}{c}\mathbf{w}\in\mathbb{R}^{p}\\\
\mathbf{u}_{y}\in\mathbb{R}^{n_{y}}\end{subarray}}\quad
r\lVert\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\theta}}_{1}\rVert_{2}^{2}+\langle\mathbf{w},\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\theta}}_{1}-\boldsymbol{\Sigma}_{-1}^{-1/2}\tilde{\boldsymbol{\theta}}_{-1}\rangle$
(4) $\displaystyle\hskip
40.00006pt+\frac{1}{n}\sum_{y\in\\{-1,1\\}}\left[\mathbf{1}^{\top}\mathcal{L}(\mathbf{v}_{y})+\langle\mathbf{u}_{y},\mathbf{1}\rangle\langle\tilde{\boldsymbol{\theta}}^{*}_{y},\tilde{\boldsymbol{\theta}}_{y}\rangle+\langle\mathbf{u}_{y},\mathbf{Z}_{y}\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\rangle+\langle\mathbf{u}_{y},\mathbf{Z}_{y}\boldsymbol{\Theta}_{y}^{\perp}\tilde{\boldsymbol{\theta}}_{y}\rangle-\langle\mathbf{u}_{y},\mathbf{v}_{y}\rangle\right]$

Here, $\mathcal{L}(\mathbf{v}_{y})\in\mathbb{R}^{n_{y}}$ is a vector
containing $\mathcal{L}(\mathbf{v}_{y,i})$ and
$\mathbf{Z}_{y}\in\mathbb{R}^{n_{y}\times p}$ is a matrix with the
$\mathbf{z}_{y,i}$ as rows. We call this problem the Primary Optimization
(PO). We note here that for each $y$,
$\mathbf{Z}_{y}\boldsymbol{\Theta}_{y}\perp\mathbf{Z}_{y}\boldsymbol{\Theta}_{y}^{\perp}$.
Furthermore, $\mathbf{Z}_{1}\perp\mathbf{Z}_{-1}$. So, for each $y$, we can
replace $\mathbf{Z}_{y}\boldsymbol{\Theta}_{y}^{\perp}$ by
$\hat{\mathbf{Z}}_{y}\boldsymbol{\Theta}_{y}^{\perp}$ for an independent
Gaussian matrix $\hat{\mathbf{Z}}_{y}$. Conditioning on the $\mathbf{Z}_{y}$,
we can see that the objective function can be written in the form

$\sum_{y\in\\{-1,1\\}}\langle\mathbf{u}_{y},\hat{\mathbf{Z}}_{y}\boldsymbol{\Theta}_{y}^{\perp}\tilde{\boldsymbol{\theta}}_{y}\rangle+\psi((\tilde{\boldsymbol{\theta}}_{y},\mathbf{v}_{y}),(\mathbf{w},\mathbf{u}_{y}))$

for a convex-concave function $\psi$. Here, we can apply Theorem 3 of [12],
which formalizes the repeated application of the CGMT in this setting and
allows us to write a corresponding Auxiliary Optimization (AO) problem. It is
important to note that using this theorem requires that the optimization be
over compact sets. This can be relaxed as in [39] by arguing that the optimal
solution in the limit is bounded so we can equivalently consider the PO to be
over a sufficiently large bounded set without changing its solution.

This theorem states that if the optimal solution of the AO converges in
probability to some value $\phi$, then the optimal solution of the PO
converges to the same value. Moreover, if we restrict the AO decision
variables to lie outside of some set $\mathcal{S}$ and the resultant problem
converges to some $\phi^{\prime}>\phi$, we can conclude that the optimal
minimizers/maximizers of the PO belong to $\mathcal{S}$ with probability
tending to $1$.

Applying the CGMT, we arrive at the following AO:

$\displaystyle\min_{\begin{subarray}{c}\tilde{\boldsymbol{\theta}}_{y}\in\mathbb{R}^{p}\\\
\mathbf{v}_{y}\in\mathbb{R}^{n_{y}}\end{subarray}}\max_{\begin{subarray}{c}\mathbf{w}\in\mathbb{R}^{p}\\\
\mathbf{u}_{y}\in\mathbb{R}^{n_{y}}\end{subarray}}\quad
r\lVert\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\theta}}_{1}\rVert_{2}^{2}+\langle\mathbf{w},\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\theta}}_{1}-\boldsymbol{\Sigma}_{-1}^{-1/2}\tilde{\boldsymbol{\theta}}_{-1}\rangle$
(5) $\displaystyle\hskip
40.00006pt+\frac{1}{n}\sum_{y\in\\{-1,1\\}}\left[\mathbf{1}^{\top}\mathcal{L}(\mathbf{v}_{y})+\langle\mathbf{u}_{y},\mathbf{1}\rangle\langle\tilde{\boldsymbol{\theta}}^{*}_{y},\tilde{\boldsymbol{\theta}}_{y}\rangle+\langle\mathbf{u}_{y},\mathbf{Z}_{y}\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\rangle+\lVert\boldsymbol{\Theta}^{\perp}_{y}\tilde{\boldsymbol{\theta}}_{y}\rVert_{2}\mathbf{g}_{y}^{\top}\mathbf{u}_{y}\right.$
$\displaystyle\hskip
80.00012pt+\left.\lVert\mathbf{u}_{y}\rVert_{2}\mathbf{h}_{y}^{\top}\boldsymbol{\Theta}_{y}^{\perp}\tilde{\boldsymbol{\theta}}_{y}-\langle\mathbf{u}_{y},\mathbf{v}_{y}\rangle\right],$

where $\mathbf{g}_{y}\sim\mathcal{N}(0,\mathbf{I}_{n_{y}})$ and
$\mathbf{h}_{y}\sim\mathcal{N}(0,\mathbf{I}_{p})$ are independent random
vectors. We will now perform a series of simplifications that show that this
min-max problem converges in probability to the solution of the scalar problem
provided in Theorem 1.

First, observe that the terms inside the summation are identical to the terms
which appear in the AO which is studied in [37] (ignoring the terms in their
analysis which correspond to adversarial training). So, we can “scalarize” the
AO problem by applying the same analysis separately over each $y$. Due to the
similarity of the steps of this part of the proof, we omit some of the details
and emphasize places where the simplification of the AO differs.

To begin, we can decouple the optimization over $\mathbf{u}_{y}$ into the
optimization over its norm and its unit direction and explicitly solve the
maximization over its direction. Hence, we are left only with the maximization
over its norm, which we denote through the variables
$\beta_{y}=\lVert\mathbf{u}_{y}\rVert_{2}/\sqrt{n}$. As in [37], we introduce
new variables $\tilde{\boldsymbol{\rho}}_{y}=\tilde{\boldsymbol{\theta}}_{y}$
(enforced via the dual variables $\boldsymbol{\lambda}_{y}$) to allow us to
separate the terms inside the summation from the terms outside the summation:

$\begin{aligned}
&\min_{\begin{subarray}{c}\tilde{\boldsymbol{\rho}}_{y},\tilde{\boldsymbol{\theta}}_{y}\in\mathbb{R}^{p}\\\
\mathbf{v}_{y}\in\mathbb{R}^{n_{y}}\end{subarray}}\max_{\begin{subarray}{c}\mathbf{w},\boldsymbol{\lambda}_{y}\in\mathbb{R}^{p}\\\
\beta_{y}\in\mathbb{R}_{+}\end{subarray}}\quad
r\lVert\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}\rVert_{2}^{2}+\langle\mathbf{w},\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}-\boldsymbol{\Sigma}_{-1}^{-1/2}\tilde{\boldsymbol{\rho}}_{-1}\rangle\\\
&\hskip
40.00006pt+\sum_{y\in\\{-1,1\\}}\left[\frac{1}{n}\mathbf{1}^{\top}\mathcal{L}(\mathbf{v}_{y})+\frac{\beta_{y}}{\sqrt{n}}\left\lVert-\mathbf{v}_{y}+\langle\tilde{\boldsymbol{\theta}}^{*}_{y},\tilde{\boldsymbol{\theta}}_{y}\rangle\mathbf{1}+\mathbf{Z}_{y}\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}+\mathbf{g}_{y}\lVert\boldsymbol{\Theta}_{y}^{\perp}\tilde{\boldsymbol{\theta}}_{y}\rVert_{2}\rVert_{2}\right.\\\
&\hskip
80.00012pt\left.+\frac{\beta_{y}}{\sqrt{n}}\langle\mathbf{h}_{y},\boldsymbol{\Theta}^{\perp}_{y}\tilde{\boldsymbol{\theta}}_{y}\rangle+\frac{1}{\sqrt{p}}\langle\boldsymbol{\lambda}_{y},\tilde{\boldsymbol{\rho}}_{y}-\tilde{\boldsymbol{\theta}}_{y}\rangle\right]\end{aligned}\par
Next,weexplictlysolvetheminimizationover\boldsymbol{\Theta}^{\perp}_{y}\tilde{\boldsymbol{\theta}}_{y}andlet\alpha_{y}=\lVert\boldsymbol{\Theta}^{\perp}_{y}\tilde{\boldsymbol{\theta}}_{y}\rVert_{2}toget\par\begin{equation}\begin{aligned}
&\min_{\begin{subarray}{c}\tilde{\boldsymbol{\rho}}_{y},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\in\mathbb{R}^{p}\\\
\mathbf{v}_{y}\in\mathbb{R}^{n_{y}}\\\
\alpha_{y}\in\mathbb{R}_{+}\end{subarray}}\max_{\begin{subarray}{c}\mathbf{w},\boldsymbol{\lambda}_{y}\in\mathbb{R}^{p}\\\
\beta_{y}\in\mathbb{R}_{+}\end{subarray}}\quad
r\lVert\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}\rVert_{2}^{2}+\langle\mathbf{w},\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}-\boldsymbol{\Sigma}_{-1}^{-1/2}\tilde{\boldsymbol{\rho}}_{-1}\rangle\\\
&\hskip
40.00006pt+\sum_{y\in\\{-1,1\\}}\left[\frac{1}{n}\mathbf{1}^{\top}\mathcal{L}(\mathbf{v}_{y})+\frac{\beta_{y}}{\sqrt{n}}\left\lVert-\mathbf{v}_{y}+\langle\tilde{\boldsymbol{\theta}}^{*}_{y},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\rangle\mathbf{1}+\mathbf{Z}_{y}\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}+\mathbf{g}_{y}\alpha_{y}\right\rVert_{2}\right.\\\
&\hskip
80.00012pt\left.-\alpha_{y}\left\lVert-\frac{\boldsymbol{\Theta}_{y}^{\perp}\boldsymbol{\lambda}_{y}}{\sqrt{p}}+\frac{\beta_{y}\boldsymbol{\Theta}_{y}^{\perp}\mathbf{h}_{y}}{\sqrt{n}}\right\rVert_{2}+\frac{1}{\sqrt{p}}\langle\boldsymbol{\lambda}_{y},\boldsymbol{\Theta}_{y}(\tilde{\boldsymbol{\rho}}_{y}-\tilde{\boldsymbol{\theta}}_{y}\rangle+\frac{1}{\sqrt{p}}\langle\boldsymbol{\lambda}_{y},\boldsymbol{\Theta}^{\perp}_{y}\tilde{\boldsymbol{\rho}}_{y}\rangle\right].\end{aligned}\end{equation}Notethatthissteprequiresswitchingthe\min
and\max(whichisallowedbythecompactificationargumentdiscussedearlier).Thenextstepistorewritethe\lVert\cdot\rVert_{2}as\lVert\cdot\rVert_{2}^{2}usingthetrickx=\min_{\tau\geq
0}\frac{x^{2}}{2\tau}+\frac{\tau}{2}.Thisresultsinnewdecisionvariables\tau_{y},\eta_{y}\geq
0:\par\begin{equation}\begin{aligned}
&\min_{\begin{subarray}{c}\tilde{\boldsymbol{\rho}}_{y},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\in\mathbb{R}^{p}\\\
\mathbf{v}_{y}\in\mathbb{R}^{n_{y}}\\\ \alpha_{y},\tau_{y}\geq
0\end{subarray}}\max_{\begin{subarray}{c}\mathbf{w},\boldsymbol{\lambda}_{y}\in\mathbb{R}^{p}\\\
\beta_{y},\gamma_{y}\geq 0\end{subarray}}\quad
r\lVert\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}\rVert_{2}^{2}+\langle\mathbf{w},\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}-\boldsymbol{\Sigma}_{-1}^{-1/2}\tilde{\boldsymbol{\rho}}_{-1}\rangle\\\
&\hskip
40.00006pt+\sum_{y\in\\{-1,1\\}}\left[\frac{1}{n}\mathbf{1}^{\top}\mathcal{L}(\mathbf{v}_{y})+\frac{\beta_{y}}{2\tau_{y}n}\left\lVert-\mathbf{v}_{y}+\langle\tilde{\boldsymbol{\theta}}^{*}_{y},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\rangle\mathbf{1}+\mathbf{Z}_{y}\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}+\mathbf{g}_{y}\alpha_{y}\right\rVert_{2}^{2}\right.\\\
&\hskip
60.00009pt+\frac{\beta_{y}\tau_{y}}{2}\left.-\frac{\alpha_{y}}{2\gamma_{y}p}\left\lVert-\frac{\boldsymbol{\Theta}_{y}^{\perp}\boldsymbol{\lambda}_{y}}{\sqrt{p}}+\frac{\beta_{y}\boldsymbol{\Theta}_{y}^{\perp}\mathbf{h}_{y}}{\sqrt{n}}\right\rVert_{2}^{2}-\frac{\alpha_{y}\gamma_{y}}{2}+\frac{1}{\sqrt{p}}\langle\boldsymbol{\lambda}_{y},\boldsymbol{\Theta}_{y}(\tilde{\boldsymbol{\rho}}_{y}-\tilde{\boldsymbol{\theta}}_{y}\rangle+\frac{1}{\sqrt{p}}\langle\boldsymbol{\lambda}_{y},\boldsymbol{\Theta}^{\perp}_{y}\tilde{\boldsymbol{\rho}}_{y}\rangle\right].\end{aligned}\end{equation}\par\par
Then,weoptimizeover\boldsymbol{\lambda}_{y}.Thisstepinvolvesafewintermediatesimpifications(completingthesquareandseparatelyoptimizingover\boldsymbol{\Theta}\boldsymbol{\lambda}and\boldsymbol{\Theta}^{\perp}\boldsymbol{\lambda}separately.Thesestepsareidenticaltothosein\cite[cite]{[\@@bibref{}{taheri2020asymptotic}{}{}]},andhencethedetailsareomittedhere.Thisstepresultsintheadditionalconstraint\mu_{y}=\frac{\langle\tilde{\boldsymbol{\theta}}^{*}_{y},\tilde{\boldsymbol{\rho}}_{y}\rangle}{\lVert\tilde{\boldsymbol{\theta}}^{*}_{y}\rVert_{2}^{2}},whichenforces\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}=\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\rho}}_{y}.Againusingstrongduality,wewritethisasamaximizationoverthedualvariables\eta_{y}andultimatelyobtain\par\begin{equation}\begin{aligned}
&\min_{\begin{subarray}{c}\tilde{\boldsymbol{\rho}}_{y}\in\mathbb{R}^{p}\\\
\mathbf{v}_{y}\in\mathbb{R}^{n_{y}}\\\ \alpha_{y},\tau_{y}\in\mathbb{R}_{+}\\\
\mu_{y}\in\mathbb{R}\end{subarray}}\max_{\begin{subarray}{c}\mathbf{w}\in\mathbb{R}^{p}\\\
\beta_{y},\gamma_{y}\in\mathbb{R}_{+}\\\
\eta_{y}\in\mathbb{R}\end{subarray}}\quad
r\lVert\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}\rVert_{2}^{2}+\langle\mathbf{w},\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}-\boldsymbol{\Sigma}_{-1}^{-1/2}\tilde{\boldsymbol{\rho}}_{-1}\rangle\\\
&\hskip
40.00006pt+\sum_{y\in\\{-1,1\\}}\left[\frac{1}{n}\mathbf{1}^{\top}\mathcal{L}(\mathbf{v}_{y})+\frac{\beta_{y}}{2\tau_{y}n}\left\lVert-\mathbf{v}_{y}+\langle\tilde{\boldsymbol{\theta}}^{*}_{y},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\rangle\mathbf{1}+\mathbf{Z}_{y}\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}+\mathbf{g}_{y}\alpha_{y}\right\rVert_{2}^{2}\right.\\\
&\hskip
80.00012pt\left.+\frac{\beta_{y}\tau_{y}}{2}-\frac{\alpha_{y}\gamma_{y}}{2}+\frac{\gamma_{y}}{2p\alpha_{y}}\left\lVert\tilde{\boldsymbol{\rho}}_{y}\sqrt{p}+\frac{\alpha_{y}\beta_{y}}{\gamma_{y}\sqrt{\delta}}\mathbf{h}_{y}\right\rVert_{2}^{2}-\frac{\mu_{y}^{2}\gamma_{y}\lVert\tilde{\boldsymbol{\theta}}_{y}\rVert_{2}^{2}}{2\alpha_{y}}-\frac{\alpha_{y}\beta_{y}^{2}\lVert\boldsymbol{\Theta}_{y}^{\perp}\mathbf{h}_{y}\rVert^{2}}{2n\gamma_{y}}\right.\\\
&\hskip
80.00012pt\left.-\frac{\alpha_{y}\beta_{y}^{2}}{2p\gamma_{y}\delta}\lVert\boldsymbol{\Theta}_{y}\mathbf{h}_{y}\rVert_{2}^{2}-\frac{2\beta_{y}}{\sqrt{n}}\langle\mathbf{h},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\rho}}_{y}\rangle+\eta_{y}\left(\mu_{y}-\frac{\langle\tilde{\boldsymbol{\theta}}^{*}_{y},\tilde{\boldsymbol{\rho}}_{y}\rangle}{\lVert\tilde{\boldsymbol{\theta}}^{*}_{y}\rVert_{2}^{2}}\right)\right]\end{aligned}\end{equation}\par
Notehere,asin\cite[cite]{[\@@bibref{}{taheri2020asymptotic}{}{}]},thattheterms\frac{\alpha_{y}\beta_{y}^{2}}{2p\gamma_{y}\delta}\lVert\boldsymbol{\Theta}_{y}\mathbf{h}_{y}\rVert_{2}^{2}and\frac{2\beta_{y}}{\sqrt{n}}\langle\mathbf{h},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\rho}}_{y}\rangle
tendto0inthelimit.\par\par
Next,optimizationover\mathbf{v}_{1}and\mathbf{v}_{-1}isdonebynotingthat\begin{aligned}
&\min_{\mathbf{v}_{1},\mathbf{v}_{-1}}\sum_{y\in\\{-1,1\\}}\left[\frac{1}{n}\mathbf{1}^{\top}\mathcal{L}(\mathbf{v}_{y})+\frac{\beta_{y}}{2\tau_{y}n}\left\lVert-\mathbf{v}_{y}+\langle\tilde{\boldsymbol{\theta}}^{*}_{y},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\rangle\mathbf{1}+\mathbf{Z}_{y}\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}+\mathbf{g}_{y}\alpha_{y}\right\rVert_{2}^{2}\right]\\\
&=\sum_{y\in\\{-1,1\\}}\pi_{y}\min_{\mathbf{v}_{y}\in\mathbb{R}^{n_{y}}}\left[\frac{1}{n_{y}}\mathbf{1}^{\top}\mathcal{L}(\mathbf{v}_{y})+\frac{\beta_{y}}{2\tau_{y}n_{y}}\left\lVert-\mathbf{v}_{y}+\langle\tilde{\boldsymbol{\theta}}^{*}_{y},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\rangle\mathbf{1}+\mathbf{Z}_{y}\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}+\mathbf{g}_{y}\alpha_{y}\right\rVert_{2}^{2}\right]\\\
&=\sum_{y\in\\{-1,1\\}}\pi_{y}\frac{1}{n_{y}}\sum_{i=1}^{n_{y}}\mathcal{M}_{\mathcal{L}}^{(1)}\left(\langle\tilde{\boldsymbol{\theta}}^{*}_{y},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\rangle+\langle\mathbf{z}_{y,i},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\rangle+\alpha_{y}\mathbf{g}_{y,i};\frac{\tau_{y}}{\beta_{y}}\right)\\\
&=\sum_{y\in\\{-1,1\\}}\pi_{y}\frac{1}{n_{y}}\sum_{i=1}^{n_{y}}\mathcal{M}_{\mathcal{L}}^{(1)}\left(\mu_{y}\lVert\tilde{\boldsymbol{\theta}}_{y}\rVert_{2}^{2}+\langle\mathbf{z}_{y,i},\boldsymbol{\Theta}_{y}\tilde{\boldsymbol{\theta}}_{y}\rangle+\alpha_{y}\mathbf{g}_{y,i};\frac{\tau_{y}}{\beta_{y}}\right)\end{aligned}Finally,weoptimizeover\tilde{\boldsymbol{\rho}}.Thisstepdiffersfromthatin\cite[cite]{[\@@bibref{}{taheri2020asymptotic}{}{}]}sinceitaccountsfortheextraconstraintthat\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}=\boldsymbol{\Sigma}_{-1}^{-1/2}\tilde{\boldsymbol{\rho}}_{-1}.\par\begin{aligned}
&\min_{\begin{subarray}{c}\tilde{\boldsymbol{\rho}}_{1},\tilde{\boldsymbol{\rho}}_{-1}\\\
\text{s.t.
}\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}=\boldsymbol{\Sigma}_{-1}^{-1/2}\tilde{\boldsymbol{\rho}}_{-1}\end{subarray}}r\lVert\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}\rVert_{2}^{2}+\sum_{y}\left[\frac{\gamma_{y}}{2p\alpha_{y}}\left\lVert\tilde{\boldsymbol{\rho}}_{y}\sqrt{p}+\frac{\alpha_{y}\beta_{y}}{\gamma_{y}\sqrt{\delta}}\mathbf{h}_{y}\right\rVert_{2}^{2}-\frac{\eta_{y}\langle\tilde{\boldsymbol{\theta}}^{*}_{y},\tilde{\boldsymbol{\rho}}_{y}\rangle}{\lVert\tilde{\boldsymbol{\theta}}^{*}_{y}\rVert_{2}^{2}}\right]\\\
&=\min_{\begin{subarray}{c}\tilde{\boldsymbol{\rho}}_{1},\tilde{\boldsymbol{\rho}}_{-1}\\\
\text{s.t.
}\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}=\boldsymbol{\Sigma}_{-1}^{-1/2}\tilde{\boldsymbol{\rho}}_{-1}\end{subarray}}r\lVert\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}\rVert_{2}^{2}+\sum_{y}\left[\frac{\gamma_{y}}{2p\alpha_{y}}\left\lVert\tilde{\boldsymbol{\rho}}_{y}\sqrt{p}+\frac{\alpha_{y}\beta_{y}}{\gamma_{y}\sqrt{\delta}}\mathbf{h}_{y}-\frac{\eta_{y}\alpha_{y}\sqrt{p}}{\gamma_{y}\lVert\tilde{\boldsymbol{\theta}}^{*}_{y}\rVert_{2}^{2}}\tilde{\boldsymbol{\theta}}^{*}_{y}\right\rVert_{2}^{2}-\frac{\eta_{y}^{2}\alpha_{y}}{2\gamma_{y}\lVert\tilde{\boldsymbol{\theta}}^{*}_{y}\rVert_{2}^{2}}\right]\\\
\end{aligned}\par
Here,wehaverewrittentheterminvolving\mathbf{w}asanexplicitconstraintonthe\tilde{\boldsymbol{\rho}}_{y},usingstrongduality.Now,notethatthisisequivalenttooptimizingoverasinglevariable\boldsymbol{\rho}=\boldsymbol{\Sigma}_{1}^{-1/2}\tilde{\boldsymbol{\rho}}_{1}=\boldsymbol{\Sigma}_{-1}^{-1/2}\tilde{\boldsymbol{\rho}}_{-1},sowecanwritethisas\par\begin{aligned}
&\min_{\boldsymbol{\rho}}r\lVert\boldsymbol{\rho}\rVert_{2}^{2}+\sum_{y}\left[\frac{\gamma_{y}}{2p\alpha_{y}}\left\lVert\boldsymbol{\Sigma}_{y}^{1/2}\left(\boldsymbol{\rho}\sqrt{p}+\frac{\alpha_{y}\beta_{y}}{\gamma_{y}\sqrt{\delta}}\boldsymbol{\Sigma}_{y}^{-1/2}\mathbf{h}_{y}-\frac{\eta_{y}\alpha_{y}\sqrt{p}}{\gamma_{y}\lVert\tilde{\boldsymbol{\theta}}^{*}_{y}\rVert_{2}^{2}}\boldsymbol{\Sigma}_{y}^{-1}\boldsymbol{\theta}^{*}\right)\right\rVert_{2}^{2}-\frac{\eta_{y}^{2}\alpha_{y}}{2\gamma_{y}\lVert\tilde{\boldsymbol{\theta}}^{*}_{y}\rVert_{2}^{2}}\right]\\\
&=\frac{r}{p}\sum_{i=1}^{p}\mathcal{M}^{(2)}_{\ell_{2}^{2}}\left(\frac{\alpha_{y}\beta_{y}}{\gamma_{y}\sqrt{\delta\lambda_{y,i}}}\mathbf{h}_{y,i}+\frac{\eta_{y}\alpha_{y}\sqrt{p}}{\gamma_{y}\lVert\tilde{\boldsymbol{\theta}}^{*}_{y}\rVert_{2}^{2}\lambda_{y,i}}\boldsymbol{\theta}^{*}_{i};\frac{\alpha_{y}r}{\gamma_{y}\lambda_{y,i}}\right)-\sum_{y}\frac{\eta_{y}^{2}\alpha_{y}}{2\gamma_{y}\lVert\tilde{\boldsymbol{\theta}}^{*}_{y}\rVert_{2}^{2}}\end{aligned}\par
WehavenowexpressedtheAOentirelyintermsofascalaroptimizationproblem.WethencanconsidertheasymptoticsofeachtermintheobjectivefunctionofthescalarizedAO,usingthefactthat\lVert\tilde{\boldsymbol{\theta}}^{*}_{y}\rVert_{2}\to\zeta_{y}andtheMoreauenvelopetermsconvergeinprobabilitytotheirexpectationsasn,p\to\infty.Thisshowspointwiseconvergenceoftheobjectivefunction.Wecanusethefactthatpointwiseconvergenceofcontinuous,convexfunctionsovercompactsetsisuniform(e.g.,CorII.1in\cite[cite]{[\@@bibref{}{andersen1982cox}{}{}]})toconcludethattheoptimalvalueoftheAOconvergestotheoptimalvalueofthescalarmin-
maxproblem.Hence,bytheCGMT,theoptimalvalueoftheoriginalERMproblem(thePO)alsoconvergesinprobabilitytothisvalue.\par
Wenowneedtoextendthistoastatementaboutthe\textit{test
error},asgiveninLemma\ref{lem:poe}.ByLemma7in\cite[cite]{[\@@bibref{}{taheri2020asymptotic}{}{}]},thedesiredresultfollowsifwecanshowthatthesolution\tilde{\boldsymbol{\theta}}_{y}ofthePOEsatisfies$$\frac{\langle\tilde{\boldsymbol{\theta}}_{y},\tilde{\boldsymbol{\theta}}^{*}\rangle}{\lVert\tilde{\boldsymbol{\theta}}^{*}\rVert_{2}^{2}}\overset{P}{\to}\mu_{y}^{*},\quad\lVert\boldsymbol{\Theta}_{y}^{\perp}\tilde{\boldsymbol{\theta}}_{y}\rVert_{2}\overset{P}{\to}\alpha_{y}^{*},$$where\mu_{y}^{*}and\alpha_{y}^{*}aretheoptimaldecisionvariablesfrom\ref{thm:main_thm}.Theproofofthesetwostatementsareidentical,soweonlyshowthelatter.Firstfix\epsilon>0anddefinethesets\mathcal{S}_{y}=\left\\{\tilde{\boldsymbol{\theta}}_{y}\colon\left\lvert\lVert\boldsymbol{\Theta}_{y}^{\perp}\tilde{\boldsymbol{\theta}}_{y}\rVert_{2}-\alpha_{y}^{*}\right\rvert<\epsilon\right\\}.NowweconsiderthesameAObutwiththeadditionalconstraint\tilde{\boldsymbol{\theta}}_{y}\in\mathcal{S}_{y}^{C}.Byassumptionthatthescalarmin-
maxin\ref{thm:main_thm}hasauniquesolution,thiscanonlystrictlyincreasetheoptimalvalue.Hence,wecanapplythethirdpartofTheorem3in\cite[cite]{[\@@bibref{}{dhifallah2021inherent}{}{}]}toconcludethat\operatorname{\mathbb{P}}\\{\tilde{\boldsymbol{\theta}}_{y}\notin\mathcal{S}_{y}\\}\to
0andthedesiredconvergenceinprobabilityto\alpha_{y}^{*}holds.SubstitutingthesevaluesintotheexpressionforthePOEinLemma7of\cite[cite]{[\@@bibref{}{taheri2020asymptotic}{}{}]},wecanconcludethattheper-
classPOEconvergestothedesiredquantity.\par\qed\end@proof\par\par$ (9)

###  A.2 Additional details for the numerical simulations

In this section, we provide additional details about the results displayed in
Figure 2.

In each of the three spectral imbalance settings, we apply Theorem 1 with
$\pi_{y}=0.5$, the overparameterization ratio $\delta=2$, regularization
parameter $r=0.5$ and the loss as the squared hinge loss,
$\mathcal{L}(t)=\max(0,1-t)^{2}$. The scalar min-max problem is solved using
gradient descent/ascent with learning rate 0.01. The choice of $\Pi$ used for
each of the three settings is given below:

  1. 1.

Impact of eigenvalue scaling:

$(\sqrt{p}\boldsymbol{\theta}^{*}_{i},\lambda_{i}^{(1)},\lambda_{i}^{(-1)})\overset{\mathclap{\text{i.i.d.}}}{\sim}\begin{cases}(1,2s,2)&\text{with
prob. }0.5\\\ (1,0.5s,0.5)&\text{with prob. }0.5\end{cases}$

  2. 2.

Impact of eigenvalue decay:

$(\sqrt{p}\boldsymbol{\theta}^{*}_{i},\lambda_{i}^{(1)},\lambda_{i}^{(-1)})\overset{\mathclap{\text{i.i.d.}}}{\sim}\begin{cases}(1,2,2)&\text{with
prob. }0.5p\\\ (1,2,0.5)&\text{with prob. }0.5p\\\ (1,0.5,2)&\text{with prob.
}0.5(1-p)\\\ (1,0.5,0.5)&\text{with prob. }0.5(1-p)\end{cases}$

  3. 3.

Impact of alignment with target signal:

$(\sqrt{p}\boldsymbol{\theta}^{*}_{i},\lambda_{i}^{(1)},\lambda_{i}^{(-1)})\overset{\mathclap{\text{i.i.d.}}}{\sim}\begin{cases}(1,2,0.5)&\text{with
prob. }0.5\\\ (a,0.5,2)&\text{with prob. }0.5\end{cases}$

In each case, the numerical simulations are averaged over $50$ independent
draws of $n=1000$ training examples (so $p=500$) from the GMM. For each trial,
we solve the ERM objective function using gradient descent.

##  Appendix B Additional Experimental Details

In Section B.1, we first provide additional visualizations to supplement the
visualizations presented in the main text. In Section B.2, we record the
Pearson correlation coefficient score and other statistical metrics for each
encoder. In Section B.3, we record the performance and details of the pre-
trained models studied. In Section B.4, we record the details of the
ImageNet-C dataset created and used in Section 4.4 and also expand on the
results in Section 4.4.

###  B.1 Additional visualizations

In Figure 1, we visualize the eigenspectrum in VIT-B as an additional example
to complement Figure 1(A), which visualized the eigenspectrum for ResNet-50.
Specifically, the left panel plots the eigenspectrum on regular scale (as in
Figure 1(A)) for VIT-B; the right panel plots the eigenspectrum on log-log
scale to reveal the power law behavior, which was also observed and analyzed
for ResNet-50 in Section 4.

Figure 1: Eigenspectrum visualization plots in normal scale and log scale for
VIT-B.

Additionally, in Figure 2, we show the direct visualization of eigenspectrum
in other encoders. The distributional differences across classes are
consistent and strong in all observed representation spaces.

Figure 2: Eigenspectrum visualization plots for other encoders.

In Figure 3, we show that the distribution of eigenvalues across encoders are
different for additional eigenvalue positions. The same figure as in Figure
1(B) (which was plotted for $\lambda_{5}$) is plotted for $\lambda_{50}$ and
$\lambda_{100}$. We observed similar trends for all other eigenvalue indexes
as well.

Figure 3: Comparing the eigenvalue distributions across encoders for
$\lambda_{50}$ and $\lambda_{100}$ (for all classes $C=1000$).

Finally, in Figure 4, we show the Pearson correlation coefficient plots
corresponding to Figure 3(B) (which corresponded to ResNet-50) for all the
other models.

Figure 4: Correlation plots for other encoders.

###  B.2 Correlation analysis of all the encoders

First, we systematically record the average accuracy of the bottom 10, bottom
100, top 100, and top 10 classes of each encoder in Table 1 to highlight the
extent of the class bias.

Table 1: The prevalence of class bias across encoders.  Model | Bottom 10 | Bottom 100 | Top 100 | Top 10
---|---|---|---|---
Densenet | 21.40% | 40.76% | 96.44% | 99.80%
EfficientNet-B1 | 24.60% | 44.00% | 97.64% | 100.00%
EfficientNet-B3 | 25.60% | 44.64% | 98.00% | 100.00%
Resnet-18 | 15.40% | 34.06% | 94.34% | 99.60%
Resnet-50 | 28.80% | 46.94% | 98.40% | 100.00%
Resnet-101 | 29.60% | 49.44% | 98.64% | 100.00%
VIT-S | 25.20% | 41.22% | 96.02% | 100.00%
VIT-B | 26.40% | 48.86% | 98.54% | 100.00%
MLPMixer | 20.80% | 38.52% | 96.08% | 100.00%
Poolformer-S24 | 27.40% | 48.10% | 98.60% | 100.00%
Poolformer-S36 | 27.20% | 49.04% | 98.80% | 100.00%
AVG | 24.76% | 44.14% | 97.41% | 99.95%

Second, we record the Pearson correlation coefficient (PCC) between per-class
accuracy and class-dependent eigenspectrum properties for each encoder in
Table 2. Aside from the individual eigenvalue scaling and power law offset, we
also record the power law slope and two effective ranks that measure the
_rate_ of eigenvalue decay in different ways. The definition of the studied
two effective ranks are as below:

######  Definition 3 (Effective Rank).

For any covariance matrix (spectrum) $\boldsymbol{\Sigma}$, we define its two
effective ranks:

$\rho_{k}({\boldsymbol{\Sigma}})=\frac{\sum_{i>k}\lambda_{i}}{\lambda_{k+1}},~{}~{}R_{k}({\boldsymbol{\Sigma}}):=\frac{(\sum_{i>k}\lambda_{i})^{2}}{\sum_{i>k}\lambda_{i}^{2}}.$
(10)

This definition was proposed in [6] and has been shown to constitute a
“sufficient" statistic to explain average generalization error across
regression and classification tasks [6, 41, 32, 44]. We examine the
relationship between effective ranks for $k=0$ and defer a more detailed study
for other values of $k$ to future work.

Table 2: Examining the correlation between spectral properties and per-class accuracy on different pre-trained encoders.  Model | Max Corr. |  PL Corr $a$. |  PL Corr $b$. | Effective Rank 1 | Effective Rank 2
---|---|---|---|---|---
Densenet | -0.6677 | -0.6636 | -0.0598 | -0.5107 | -0.5384
EfficientNet-B1 | -0.7599 | -0.7476 | -0.0107 | -0.6283 | -0.6131
EfficientNet-B3 | -0.7505 | -0.7210 | 0.0007 | -0.6209 | -0.5816
Resnet-18 | -0.6229 | -0.5649 | 0.0968 | -0.4434 | -0.4722
Resnet-50 | -0.6293 | -0.6270 | 0.0447 | -0.4943 | -0.4952
Resnet-101 | -0.6560 | -0.6454 | 0.0170 | -0.4869 | -0.4896
VIT-S | -0.6891 | -0.6783 | -0.0571 | -0.5195 | -0.5399
VIT-B | -0.6536 | -0.6531 | -0.1493 | -0.4824 | -0.4934
MLPMixer | -0.7785 | -0.7715 | 0.0460 | -0.7074 | -0.6707
Poolformer-S24 | -0.6961 | -0.6755 | 0.0708 | -0.5544 | -0.5895
Poolformer-S36 | -0.7062 | -0.6904 | 0.0006 | -0.5652 | -0.5638
AVG | -0.6918 | -0.6762 | -0.0002 | -0.5466 | -0.5497

Interestingly, we observe across models that the spectral metrics that measure
_relative rate_ of eigenvalue decay — such as the power law decay parameter
$b$ and the effective ranks — do not strongly correlate with class-wise
accuracy, while the spectral metrics that are more absolute — i.e. the
individual eigenvalues and the power law parameter $a$ — do strongly
correlate.

###  B.3 Details of pretrained networks

In this section we record the details of the pre-trained networks that we used
and evaluated to allow for reproducibility of our results.

  * •

Residual Networks. ResNet is instrumental in many visual recognition tasks, as
it addresses the vanishing gradient problem, allowing very deep networks to be
trained effectively. In this paper, we used the pre-trained weights for ResNet
from TorchVision. We list their performance, model card name, and parameters
below.

    * –

For ResNet-101, we used the v2 weight from the new training recipe of
torchvision. The Top1 accuracy is 81.886% and Top5 accuracy is 95.78% on
ImageNet-1K, with 44.5M parameters. Its representation dimensionality is equal
to 2048.

    * –

For ResNet-50, we used the v2 weight from the new training recipe of
torchvision. The Top1 accuracy is 80.858% and Top5 accuracy is 95.434% on
ImageNet-1K, with 25.6M parameters. Its representation dimensionality is equal
to 2048.

    * –

For ResNet-18, we used the default weight (or v1 weight from torchvision). The
Top1 accuracy is 69.758% and Top5 accuracy is 89.078% on ImageNet-1K, with
11.7M parameters. Its representation dimensionality is equal to 512.

  * •

Improved CNNs. Many research works propose variants of convolutional
architectures to improve ResNets. Among these efforts, DenseNet [20] and
EfficientNet [38] are two representative architectures that are more
parameter-efficient. They design different strategies to connect layers
differently to improve the parameter-efficiency as well as information flow
inside the networks. DenseNet improves the flow of information and gradients
throughout the network by densely connecting all layers directly with each
other. EfficientNet designs a compound coefficient that uniformly scales the
depth, width, and resolution of CNNs and thus improves performance with fewer
parameters.

    * –

For DenseNet, we used the weights from timm (model card densenet121.ra_in1k).
The Top1 accuracy is 75.57% and Top5 accuracy is 92.61%, with 8.0M parameters.
Its representation dimensionality is equal to 1024.

    * –

For EfficientNet-B3, we used the weights from timm (model card
efficientnet_b3.ra2_in1k). The Top1 accuracy is 77.60% and Top5 accuracy is
93.59%, with 12.2M parameters. Its representation dimensionality is equal to
1536.

    * –

For EfficientNet-B1, we used the weights from timm (model card
efficientnet_b1.ft_in1k), The Top1 accuracy is 78.54% and Top5 accuracy is
94.38%, with 7.8M parameters. Its representation dimensionality is equal to
1280.

  * •

Vision Transformers. Recently, the transformer architecture has achieved
strong performance even in the vision domain [14]. The vision transformer
splits an image into patches and uses self-attention to study the interaction
of patches. By doing so, it aggregates global information at an early stage,
creating significantly different representations than CNNs [34].

    * –

For VIT-B, we used the weights from timm
(vit_base_patch16_224.augreg2_in21k_ft_in1k), The Top1 accuracy is 81.10% and
Top5 accuracy is 95.72%, with 86.6M parameters. Its representation
dimensionality is equal to 768. We note that the model is pre-trained on
ImageNet21k and later fine-tuned on ImageNet1k.

    * –

For VIT-S, we used the weights from timm
(vit_small_patch16_224.augreg_in21k_ft_in1k). The Top1 accuracy is 74.63% and
Top5 accuracy is 92.67%, with 22.1M parameters. Its representation
dimensionality is equal to 384. We note that the model is pre-trained on
ImageNet21k and later fine-tuned on ImageNet1k.

  * •

Transformers without Self-Attention. Recent studies show that self-attention
is not required for obtaining good representations in vision. We study in
particular MLP-Mixer [40] and PoolFormer [48], which uses multi-layer
perceptrons and average pooling to mix information across patches,
respectively.

    * –

For MLP-Mixer, we used weights from timm (model card
mixer_b16_224.goog_in21k_ft_in1k). The Top1 accuracy is 72.57% and Top5
accuracy is 90.06%, with 59.9M parameters. Its representation dimensionality
is equal to 768. We note that it is pre-trained on ImageNet21k and later fine-
tuned on ImageNet1k.

    * –

For PoolFormer-S36, we used the weights from timm (model card
poolformerv2_s36.sail_in1k). The Top1 accuracy is 81.54% and Top5 accuracy is
95.69%, with 30.8M parameters. Its representation dimensionality is equal to
512.

    * –

For PoolFormer-S24, we used the weights from timm (model card
poolformerv2_s24.sail_in1k). The Top1 accuracy is 80.76% and Top5 accuracy is
95.39%, with 21.3M parameters. Its representation dimensionality is equal to
512.

###  B.4 Details of ImageNet-C results

We created the “augmented" ImageNet-C datasets based on [19]. The
preprocessing plans (corruptions) we selected are:

  * •

Gaussian Noise, Shot Noise, Impulse Noise, Defocus Blur, Motion Blur, Zoom
Blur, Snow, Fog, Brightness, Contrast, Elastic, Pixelate, JPEG, Speckle Noise,
Spatter, and Saturate.

Note that these corruptions correspond to the $16$ augmentations discussed in
Section 4.4. While [19] only augment the test dataset, we perform the image
altering operations on the training set as well, as we wish to estimate the
eigenvalues using the training data.

Figure 5: Spectral Quantile Score (SQS) of different data manipulation plans.

In Figure 5, we show the Spectral Quantile Score (SQS) of applying the same
encoder on different data with different data manipulation plans (as discussed
in Section 4.4). The PCC is 0.90, showing strong correlation (again) between
class bias and the SQS.

For the statistical significance results for each class, we first compute the
Pearson correlation coefficient $r$ for each class, and calculate the
$p$-value as below:

$p=2P(T_{n-2}>t),\text{ where }t=\frac{r\sqrt{n-2}}{\sqrt{1-r^{2}}}$ (11)

where $n$ is the number of samples, and $T_{n-2}$ is a Student $t$’s
distribution with $n-2$ degrees of freedom.