Prevalence of Neural Collapse during the terminal phase of deep learning training

Introduction

Over the last decade, deep learning systems have steadily advanced the state-of-the-art in benchmark competitions, culminating in super-human performance in tasks ranging from image classification to language translation to game play. One might expect the trained networks to exhibit many particularities–making it impossible to find any empirical regularities across a wide range of datasets and architectures. On the contrary, in this article we present extensive measurements across image-classification datasets and architectures, exposing a common empirical pattern.

Our observations focus on today’s standard training paradigm in deep learning, an accretion of several fundamental ingredients that developed over time: Networks are trained beyond zero misclassification error, approaching negligible cross-entropy loss, interpolating the in-sample training data; networks are overparameterized, making such memorization possible; and these parameters are layered in ever-growing depth, allowing for sophisticated feature engineering. A series of recent works (1, 2, 3, 4, 5) highlighted the paradigmatic nature of the practice of training well beyond zero-error, seeking zero-loss. We call the post-zero-error phase the Terminal Phase of Training (TPT).

A scientist with standard preparation in mathematical statistics might anticipate that the linear classifier resulting from this paradigm, being a by-product of such training, would be quite arbitrary and vary wildly–from instance to instance, dataset to dataset, and architecture to architecture–thereby displaying no underlying cross-situational invariant structure. The scientist might further expect that the configuration of the fully-trained decision boundaries – and the underlying linear classifier defining those boundaries – would be quite arbitrary and vary chaotically from situation to situation. Such expectations might be supported by appealing to the overparameterized nature of the model, and to standard arguments whereby any noise in the data propagates during overparameterized training to generate disproportionate changes in the parameters being fit.

Defeating such expectations, we show here that TPT frequently induces an underlying mathematical simplicity to the trained deepnet model – and specifically to the classifier and last-layer activations – across many situations now considered canonical in deep learning. Moreover, the identified structure naturally suggests performance benefits. And indeed, we show that convergence to this rigid structure tends to occur simultaneously with improvements in the network’s generalization performance as well as adversarial robustness.

We call this process Neural Collapse, and characterize it by four manifestations in the classifier and last-layer activations:

As training progresses, the within-class variation of the activations becomes negligible as these activations collapse to their class-means.

The vectors of the class-means (after centering by their global-mean) converge to having equal length, forming equal-sized angles between any given pair, and being the maximally pairwise-distanced configuration constrained to the previous two properties. This configuration is identical to a previously studied configuration in the mathematical sciences known as Simplex Equiangular Tight Frame (ETF) (6). See Definition 1.

The class-means and linear classifiers – although mathematically quite different objects, living in dual vector spaces – converge to each other, up to rescaling. Combined with (NC2), this implies a complete symmetry in the network classifiers’ decisions: each iso-classifier-decision region is isometric to any other such region by rigid Euclidean motion; moreover the class-means are each centrally located within their own specific regions, so there is no tendency towards higher confusion between any two classes than any other two.

For a given deepnet activation, the network classifier converges to choosing whichever class has the nearest train class-mean (in standard Euclidean distance).

We give a visualization of the phenomena (NC1)-(NC3) in Figure 1Figure 1 is, in fact, generated using real measurements, collected while training the VGG13 deepnet on CIFAR10: For three randomly selected classes, we extract the linear classifiers, class-means, and a subsample of twenty last-layer features at epochs 2, 16, 65, and 350. These entities are then rotated, rescaled, and represented in three-dimensions by leveraging the singular-value decomposition of the class-means. We omit further details as Figure 1 serves only to illustrate Neural Collapse on an abstract level., and define Simplex ETFs (NC2) more formally as follows:

Properties (NC1)-(NC4) show that a highly symmetric and rigid mathematical structure with clear interpretability arises spontaneously during deep learning feature engineering, identically across many different datasets and model architectures.

(NC2) implies that the different feature means are ‘equally spaced’ around the sphere in their constructed feature space; (NC3) says the same for the linear classifiers in their own dual space; and moreover, that the linear classifiers are ‘the same as’ the class means, up to possible rescaling. These mathematical symmetries and rigidities vastly simplify the behavior and analysis of trained classifiers, as we show in Section 5 below, which contrasts the kind of qualitative understanding previously available from theory, against the precise and highly constrained predictions possible with (NC4).

(NC1)-(NC4) offer theoretically-established performance benefits: stability against random noise and against adversarial noise. And indeed, this theory bears fruit. We show that during TPT, while Neural Collapse is progressing, the trained models are improving in generalizability and in adversarial robustness.

In Section 7 below we discuss the broader significance of (NC1)-(NC4) and their relation to recent advances across several rapidly developing ‘research fronts.’

To support our conclusions, we conduct empirical studies that range over seven canonical classification datasets (7, 8, 9), including ImageNet (10), and three prototypical, contest-winning architectures (11, 12, 13). These datasets and networks were chosen for their prevalence in the literature as benchmarks (14, 15, 16), reaffirmed by their easy availability as part of the popular deep learning framework PyTorch (17). As explained below, these observations have important implications for our understanding of numerous theoretical and empirical observations in deep learning.

Setting and methodology

All subsequent experiments are built upon the general setting and methodology described below.

2 Deep learning for classification

3 Network architecture and feature engineering

The network is generally specified in two stages: First, an architecture is prescribed; and then, for a given architecture, there are a large number of parameters which determine the deep network’s feature engineering, $\bm{h}({\bm{x}})$. Collecting these parameters in a vector $\bm{\theta}$, we may also write $\bm{h}=\bm{h}_{\bm{\theta}}({\bm{x}})$.

When the architecture specifies a truly deep network – and not merely a shallow one – the variety of behaviors that the different choices of $\bm{\theta}$ can produce is quite broad. To evoke, in quite concrete terms, the process of specifying the nonlinear transformation ${\bm{x}}\mapsto\bm{h}_{\bm{\theta}}({\bm{x}})$, we speak of feature engineering. In contrast, traditional machine learning often dealt with a fixed collection of feature vectors that were not data-adaptive.

4 Training

Viewing the induced class labels as the network outputs, and the architecture and problem size as fixed in advance, the underlying class labelling algorithm depends on the parameter vector $(\bm{\theta},\bm{W},\bm{b})$. We think of $\bm{\theta}$ as determining the features to be used, and $(\bm{W},\bm{b})$ as determining the linear classifier that operates on the features to produce the labels. The number of parameters that must be determined is quite large. In practice, these parameters must be learned from data, by the process commonly known as training.

More concretely, consider a balanced dataset, having exactly $N$ training examples in each class, $\bigcup_{c=1}^{C}\{{\bm{x}}_{i,c}\}_{i=1}^{N}$, where ${\bm{x}}_{i,c}$ denotes the $i$-th example in the $c$-th class. The parameters $(\bm{\theta},\bm{W},\bm{b})$ are fit by minimizing, usually using stochastic gradient descent (SGD), the objective function:

5 Datasets

We consider the MNIST, FashionMNIST, CIFAR10, CIFAR100, SVHN, STL10 and ImageNet datasets (10, 7, 8, 9). MNIST was sub-sampled to $N{=}5000$ examples per class, SVHN to $N{=}4600$ examples per class, and ImageNet to $N{=}600$ examples per class. The remaining datasets are already balanced. The images were pre-processed, pixel-wise, by subtracting the mean and dividing by the standard deviation. No data augmentation was used.

6 Networks

We train the VGG, ResNet, and DenseNet architectures (11, 12, 13). For each of the three architecture types, we chose the network depth through trial-and-error in a series of preparatory experiments in order to adapt to the varying difficulties of the datasets. The final chosen networks were VGG19, ResNet152, and DenseNet201 for ImageNet; VGG13, ResNet50, and DenseNet250 for STL10; VGG13, ResNet50, and DenseNet250 for CIFAR100; VGG13, ResNet18, and DenseNet40 for CIFAR10; VGG11, ResNet18, and DenseNet250 for FashionMNIST; and VGG11, ResNet18, and DenseNet40 for MNIST and SVHN. DenseNet201 and DenseNet250 were trained using the memory-efficient implementation proposed in (18). We replaced the dropout layers in VGG with batch normalization and set the dropout rate in DenseNet to zero.

7 Optimization methodology

Following common practice, we minimize the cross-entropy loss using stochastic gradient descent (SGD) with momentum $0.9$. The weight decay is set to $1{\times}10^{-4}$ for ImageNet and $5{\times}10^{-4}$ for the other datasets. ImageNet is trained with a batch size of $256$, across 8 GPUs, and the other datasets are trained on a single GPU with a batch size of $128$. We train ImageNet for 300 epochs and the other datasets for $350$ epochs. The initial learning is annealed by a factor of $10$ at $1/2$ and $3/4$ for ImageNet; and $1/3$ and $2/3$ for the other the datasets. We sweep over $10$ logarithmically-spaced learning rates for ImageNet between $0.01$ and $0.25$, and $25$ learning rates for the remaining datasets between $0.0001$ and $0.25$–picking the model resulting in the best test error in the last epoch.

8 Large-scale experimentation

The total number of models fully trained for this paper is tallied below:

The massive computational experiments reported here were run painlessly using ClusterJob and ElastiCluster (19, 20, 21) on the Stanford Sherlock HPC cluster and Google Compute Engine virtual machines.

9 Moments of activations

During training, we snapshot the network parameters at certain epochs. For each snapshotted epoch, we pass the train images through the network, extract their last-layer activations (using PyTorch hooks (22)), and calculate these activations’ first and second moment statistics.

where $\operatorname*{Ave}$ is the averaging operator.

Unless otherwise specified, for brevity, we refer in the text to the globally-centered class-means, $\{\bm{\mu}_{c}-\bm{\mu}_{G}\}_{c=1}^{C}$, as just class-means, since the globally-centered class-means are of more interest.

Recall from multivariate statistics that:

10 Formalization of Neural Collapse

With the above notation, we now present a more mathematical description of Neural Collapse, where $\to$ indicates convergence as training progresses:

Results

To document the observations we make in Section 1, we provide a series of figures and tables below. We briefly list here our claims and identify the source of our evidence.

Means and classifiers become equinorm: Figure 2

Means and classifiers become maximally equiangular: Figures 3 and 4

Means and classifiers become self-dual: Figure 5

Train within-class covariance collapses: Figure 6

Classifier approaches nearest class-center: Figure 7

All figures in this article are formatted as follows: Each of the seven array columns is a canonical dataset for benchmarking classification performance – ordered left to right roughly by ascending difficulty. Each of the three array rows is a prototypical deep classifying network. On the horizontal axis of each cell is the epoch of training. For each dataset-network combination, the red vertical line marks the begining of the effective beginning of TPT, i.e, the epoch when the training accuracy reaches 99.6% for ImageNet and 99.9% for the remaining datasets; we do not use 100% as it has been reported (23, 24, 25) that several of these datasets contain inconsistencies and mislabels which sometimes prevent absolute memorization. Additionally, orange lines denote measurements on the network classifier, while blue lines denote measurements on the activation class-means.

Discussion

Taken together, Figures 2-7 give evidence for Neural Collapse. First, Figure 2 shows how, as training progresses, the variation in the norms of the class-means (and classifiers) decreases–indicating that the class-means (and classifiers) are converging to an equinormed state.

Then, Figure 3 indicates that all pairs of class-means (or classifiers) tend towards forming equal-sized angles. Figure 4 additionally reveals that the cosines of these angles converge to $-\frac{1}{C-1}$ – the maximum possible given the constraints. This maximal-equiangularity, combined with equinormness, implies that the class-means and classifiers converge to Simplex ETFs.

The above experiments by themselves do not indicate any relationship between the final converged states of the class-means and classifiers, even though both converge to some Simplex ETF. Such a relationship is revealed by Figure 5 – showing how they converge to the same Simplex ETF, up to rescaling.

Moreover, the above concerns solely the class-means. Yet, we can make a stronger claim about the activations themselves by looking at $\tr{\bm{\Sigma}_{W}\bm{\Sigma}_{B}^{\dagger}}$. This quantity, canonical in multivariate statistics, measures the inverse signal-to-noise ratio for classification problems and can be used to predict misclassification (27) . The intra-class covariance matrix $\bm{\Sigma}_{W}$ (the noise) is best interpreted once scaled and rotated by pseudo-inverse of the inter-class covariance matrix $\bm{\Sigma}_{B}$ (the signal), since such transformation maps the noise into a common frame of reference across epochs. According to Figure 6 , the normalized variation of the activations becomes negligible as training proceeds, indicating the activations collapse to their corresponding class means. This collapse continues well after the beginning of TPT.

A recurring theme across Figures 2-7 is the continuing process of Neural Collapse after zero error has been achieved. This explains TPT’s paradigmatic nature: While continuing training after zero error has already been achieved seems counter-intuitive, it induces significant changes in the underlying structure of the trained network.

This motivates Figure 8 and Table 1, which explore two of the benefits of TPT. Table 1 shows how the test accuracy continues improving steadily, and Figure 8 shows how adversarial robustness continues improving as well. In fact, most of the improvement in robustness happens during TPT.

Neural Collapse sharpens previous insights

Two notable prior works (28, 29) were able to significantly constrain the form of the structure of trained classifiers. However, in the presence of Neural Collapse, it is possible to say dramatically more about the structure of trained classifiers. Moreover, the structure which emerges is extremely simple and symmetric.

In particular, the prior work assumed fixed features, not subject to data-adaptive feature engineering which is so characteristic of deep learning training. In the modern context where deep-learning features are trained, and employing the assumption that the resulting last-layer entities undergo Neural Collapse, the mathematical constraints on the structure of trained classifiers tighten drastically.

As a preliminary step, we first formalize four possible properties of the end-state towards which Neural Collapse is tending:

$\frac{\bm{W}^{\top}}{\|\bm{W}\|_{F}}=\frac{\dot{\bm{M}}}{\|\dot{\bm{M}}\|_{F}}$

In (28), Webb and Lowe proved the following important result which, reformulated for the modern setting, could be written as follows.

Fix the deepnet architecture and the underlying tuning parameters $\bm{\theta}$, so that the activations $\bm{h}_{\bm{\theta}}({\bm{x}})$ involve no training, and so that only the classifier weights $\bm{W}$ and biases $\bm{b}$ need to be trained. Maintain the same definitions – $\bm{\Sigma}_{T}$, $\bm{\mu}_{c}$, $\bm{\mu}_{G}$ etc. – as in Section 2. Adopting the mean squared error loss in place of the cross-entropy loss, the optimal classifier weights and biases are given by

The form in is similar to the one first developed by R.A. Fisher in 1936 (30) – commonly referred to as Linear Discriminant Analysis (LDA) – although Fisher’s version uses $\bm{\Sigma}_{W}$ in lieu of $\bm{\Sigma}_{T}$. In other words, the above theorem states that a modified LDA is the optimal solution for the last-layer classifier

Webb and Lowe’s result admirably elucidates the structure of the optimal classifier; however, it also leaves a great deal unspecified about possible properties of the classifier. In our Theorem 2, immediately following, we supplement Webb and Lowe’s assumptions by adding the variability collapse and Simplex ETF properties; the result significantly narrows the possible structure of optimal classifiers, obtaining both self duality and behavioral agreement with NCC.

Adopt the framework and assumptions of Proposition 1, as well as the end state implied by (NC1)-(NC2), i.e. $\overrightarrow{(\text{NC{1})}}$-$\overrightarrow{(\text{NC{2})}}$. The Webb-Lowe classifier , in this setting, has the additional properties $\overrightarrow{(\text{NC{3})}}$-$\overrightarrow{(\text{NC{4})}}$.

By $\overrightarrow{(\text{NC{1})}}$, $\bm{\Sigma}_{W}=\mathbf{0}$, and we have $\bm{\Sigma}_{T}=\bm{\Sigma}_{B}$. Using now Proposition 1, we obtain

implies that $\bm{\Sigma}_{B}=\frac{1}{C}\dot{\bm{M}}\dot{\bm{M}}^{\top}$. Thus,

$\overrightarrow{(\text{NC{2})}}$ implies that $\dot{\bm{M}}$ has exactly $C-1$ non-zero and equal singular values, so $\dot{\bm{M}}^{\dagger}=\alpha\dot{\bm{M}}^{\top}$ for some constant $\alpha$. Combining the previous pair of displays, we obtain

[7a] demonstrates the asserted self-duality $\overrightarrow{(\text{NC{3})}}$, up to rescaling. The class predicted by the above classifier is given by:

Using the equal norm property of $\overrightarrow{(\text{NC{2})}}$, this display becomes

In words, the decision of the linear classifier based on $(\bm{W},\bm{b})$ is identical to that made by NCC $\overrightarrow{(\text{NC{4})}}$. ∎

Our theorem predicts that evidence of (NC1)-(NC2) as shown in Figures 2, 3, 4, and 6 should deterministically accompany both (NC3) and (NC4) – exactly as observed in our Figures 5 and 7.

2 Soudry et. al. (2018)

The authors of (29) consider $C$-class classification, again in a setting where the parameter vector $\bm{\theta}$ is not trained, so that the last-layer activations $\bm{h}_{i,c}=\bm{h}({\bm{x}}_{i,c})$ are fixed and not subject to feature engineering.

They proved an important result which explicitly addresses our paper’s focus on cross-entropy classifier loss minimization in the zero-error regime.

For (Lebesgue-) almost every dataset $\bm{H}\in\mathcal{H}$, gradient descent minimizing the cross-entropy loss, as a function of the classifier weights, tends to a limit. This limit is identical to the solution of the max-margin classifier problem:

This inspiring result significantly constrains the form of the trained classifier, in precisely the cross-entropy loss setting relevant to deep learning. However, because feature activations are here fixed, not learned, this result is only able to give indirect, implicit information about a deepnet trained model involving feature engineering and about the classification decisions that it makes.

Some authors of (29) have, in a series of highly influential talks and papers, laid great emphasis on the notion of an emergent, not superficially evident, ‘inductive bias’ as a reason for the surprising success of deep learning training, and have pointed to Proposition 3 as a foundational result indicating that ‘inductive bias’ can be implicit in the behavior of a training procedure that superficially shows no behavioral tendencies in the indicated direction.

We agree wholeheartedly with the philosophy underlying (29); our results support the further observation that inductive bias is far more constraining on the outcome of modern deepnet training than was previously known.

In effect, out of all possible max-margin classifiers that could be consistent with Proposition 3, the modern deepnet training paradigm is producing linear classifiers approximately belonging to the very tiny subset with the additional property of being Simplex ETFs. Moreover, such classifiers exhibit very striking behavioral simplicity in decision making.

Adopt the framework and assumptions of Proposition 3, as well as the end state implied by (NC1)-(NC2), i.e. $\overrightarrow{(\text{NC{1})}}$-$\overrightarrow{(\text{NC{2})}}$. The Soudry et. al. classifier , in this setting, has the additional properties $\overrightarrow{(\text{NC{3})}}$-$\overrightarrow{(\text{NC{4})}}$.

Since $\dot{\bm{M}}$ is the matrix of a Simplex ETF, it has $C-1$ equal-sized singular values with the remaining singular value being zero. Without loss of generality, we assume here that those singular values are 1, i.e. $\|\dot{\bm{M}}\|_{2}=1$. Notice the singular value assumption implies the columns are of norm $\|\bm{\mu}_{c}-\bm{\mu}_{G}\|_{2}=\sqrt{(C-1)/C}$ (not unity) for all $c$. At the assumed end-state of variability collapse $\overrightarrow{(\text{NC{1})}}$, the activations all collapse to their respective class-means, and the max-margin classifier problem reduces to

Rewriting with matrix notation and using a Pythagorean decomposition of the objective, the above becomes:

and $\bm{W}\bm{U}=\bm{A}\bm{U}^{\top}\bm{U}=\bm{A}$, transforms the optimization problem into the equivalent form

Averaging the constraints of over $c$ and summing over $c^{\prime}\neq c$, we obtain

Since $\bm{A}=\bm{V}$ optimizes , which involves the same objective as , but over a possibly enlarged feasible set, feasibility of $\bm{A}=\bm{V}$ implies that $\bm{A}=\bm{V}$ optimizes as well. The solution to is unique, since the problem minimizes a positive definite quadratic subject to a single nondegenerate linear constraint. In the optimization problem for $\bm{W}$ that we started with, recall that $\bm{W}=\bm{A}\bm{U}^{\top}$. Hence, the optimality of $\bm{A}=\bm{V}$ implies $\bm{W}=\bm{A}\bm{U}^{\top}=\bm{V}\bm{U}^{\top}=\dot{\bm{M}}^{\top}$, showing self-duality is achieved $\overrightarrow{(\text{NC{3})}}$. This equality becomes a proportionality in the more general case where the equal singular values of $\dot{\bm{M}}$ are not unity.

An argument similar to the one for Theorem 2 that the classifier is behaviorally equivalent to the NCC decision rule $\overrightarrow{(\text{NC{4})}}$. ∎

Much like Theorem 2, but now for cross-entropy loss, the above result again indicates that evidence of (NC1)-(NC2) as shown in Figures 2, 3, 4, and 6 should accompany both (NC3) and (NC4), as shown in Figures 5 and 7. In short, our results indicate an inductive bias towards NCC which is far more total and limiting than the max-margin bias proposed by (29).

Theoretical derivation of Simplex ETF emergence

We are unaware of suggestions, prior to this work, that Simplex ETFs emerge as the solution of an interesting and relevant optimization problem. Prompted by the seemingly surprising nature of the above empirical results, we developed theoretical results which show that the observed end-state of Neural Collapse can be derived directly using standard ideas from information theory and probability theory. Roughly speaking, the Simplex ETF property $\overrightarrow{(\text{NC{2})}}$, self-duality $\overrightarrow{(\text{NC{3})}}$, and behavioral simplification $\overrightarrow{(\text{NC{4})}}$ are derivable consequences of variability collapse $\overrightarrow{(\text{NC{1})}}$.

In our derivation, we consider an abstraction of feature engineering, in which an ideal feature designer chooses activations which minimize the classification error in the presence of nearly-vanishing within-class variability. Our derivation shows that the ideal feature designer should choose activations whose class means form a Simplex ETF.

2 Information theory perspective

The above can be recast as an optimal coding problem in the spirit of Shannon (31). The class means $\bm{\mu}_{c}$ are codewords and the matrix $\bm{M}$ represents a codebook, containing $C$ codewords. A transmitter transmits a codeword over a noisy channel, contaminated by white additive Gaussian noise, and then a receiver obtains the noisy signal $\bm{h}=\bm{\mu}_{c}+\bm{z}$ which it then decodes using a linear decoder $\hat{\gamma}$ in an attempt to recover the transmitted $\gamma$. The norm constraint on the means captures limits imposed on signal strength due to the distance between the transmitter and receiver. Our task is to design a codebook and decoder that would allow optimal retrieval of the class identity $\gamma$ from the noisy information $\bm{h}$.

3 Large-deviations perspective

To measure success in this task, we consider the large-deviations error exponent:

This is the right limit, as we are considering the situation where the noise is approaching zero due to variability collapse (NC1). Tools for deriving large deviations error exponents have been extensively developed in probability theory (32).

4 Theoretical result

Under the model assumptions just given in subsections 6.1, 6.2, and 6.3, the Optimal Error Exponent is

where the maximum is over $C\times C$ matrices $\bm{M}$ with at most unit-norm columns, and over $C\times C$ matrices $\bm{W}$ and $C\times 1$ vectors $\bm{b}$.

All matrices $\bm{M}$ achieving $\beta^{\star}$ are also Simplex ETFs – possibly in an isometric pose – deriving from $\bm{M}^{\star}$ via $\bm{M}=\bm{U}\bm{M}^{\star}$ with $\bm{U}$ a $C\times C$ orthogonal matrix. For such matrices, an optimal linear decoder is $\bm{W}={\bm{M}}^{\star}\bm{U}^{\top}$, $\bm{b}=\mathbf{0}$:

In words, if we engineer a collection of codewords to optimize the (vanishingly small) theoretical misclassification probability, we obtain as our solution the standard Simplex ETF, or a rotation of it.

We stress that the maximal equiangularity property of $\bm{M}^{\star}$ is crucial to this result, i.e.

this property is enjoyed by every collection of class-means optimizing the error exponent and is unique to Simplex ETFs.

The results of this section show that Simplex ETFs are the unique solution to an abstract optimal feature design problem. The fact that modern deepnet training practice has found this same Simplex ETF solution suggests to us that the training paradigm – SGD, TPT and so on – is finding the same solution as would an ideal feature engineer! Future research should seek to understand the ability of training dynamics to succeed in obtaining this solution.

Related works

The prevalence of Neural Collapse makes us view a number of previous empirical and theoretical observations in a new light.

Immediately prior to the modern era of purely empirical deep learning, (33) proposed a theory-derived machinery building on the scattering transform that promised an understandable approach for handwritten digit recognition. The theory was particularly natural for problems involving within-class variability caused by ‘small’ morphings of class-specific templates; In fact, the scattering transform was shown in (34) to tightly limit the variability caused by template morphings. Later, (35, 36, 37), complemented (33) with additional theory covering a larger range of mathematically-derived features, nonlinearities, and pooling operations – again designed to suppress within-class variability.

Our finding of Neural Collapse, specifically (NC1), shows that feature engineering by standard empirical deepnet training achieves similar suppression of within-class variability–both on the original dataset considered by (33) as well as six more challenging benchmarks. Thus, the original goal of (34, 33, 35, 36, 37), which can be phrased as the limiting of within-class variability of activations, turns out to be possible for a range of datasets; and, perhaps more surprisingly, to be learnable by stochastic gradient descent on cross-entropy loss. Recently, Mallat and collaborators were able to deliver results with scattering-transform features (combined with dictionary learning) that rival the foundational empirical results produced by AlexNet (38). So apparently, controlling within-class activation variability, whether this is achieved analytically or empirical, is quite powerful.

2 Observed structure of spectral Hessians

More recently, empirical studies of the Hessian of the deepnet training loss of image-classification networks observed surprising and initially baffling deterministic structure. First observed by (39, 40), on toy models, the spectrum exhibits $C$ outlier eigenvalues separated from a bulk, where $C$ is the number of classes of the image classification task. (41, 42, 43) corroborated these findings at scale on modern deep networks and large datasets. (41, 42) explained how the spectral outliers could be attributed to low-rank structure associated with class-means and the bulk could be induced by within-class variations (of logit-derivatives). It was essential that the class means have greater norm than the within-class standard deviation in order for these spectral outliers to emerge.

Under (NC1), the full matrix of last-layer activations converges to a rank-$(C{-}1)$ matrix, associated with class-means. So under (NC1), eventually the within-class standard deviation will be much smaller, and the outliers will emerge from the bulk. In short, the collapse of activation variability (NC1), combined with convergence of class means (NC2) to the Simplex ETF limit, explains these important and highly visible observations about deepnet Hessians.

3 Stability against random and adversarial noise

It is well understood classically that when solving linear systems $\bm{y}=\bm{M}{\bm{x}}$ by standard methods, some matrices $\bm{M}$ are prone to solution instability, blowing up small noise in $\bm{y}$ to produce large noise in ${\bm{x}}$; other matrices are less prone. Stability problems arise if the nonzero singular values of $\bm{M}$ are vastly different and don’t arise if the nonzero singular values are all identical. The Simplex ETF offers equal nonzero singular values, and so a certain resistance to noise amplification. This is a less well known path to equal singular values, partial orthogonal matrices being of course the more well known.

In the deepnet literature, the authors of (44, 45, 46, 47, 48) studied the stability of deepnets to adversarial examples. They proposed that stability can be obtained by making the matrices defined by the network weights close to orthogonal. However, no suggestion was offered for why trained weights, under the current standard training paradigm, would tend to become orthogonal.

In (49), the authors modified the standard training paradigm, forcing linear and convolutional layers to be approximate tight frames; they showed this leads both to better robustness to adversarial examples, as well as improved accuracy and faster training. To get these benefits, they imposed orthogonality explicitly during training.

Both (44, 45) and (49) showed how concerns about stability can be addressed by explicit interventions in the standard training paradigm. By demonstrating a pervasive Simplex ETF structure, this paper has shown that, under today’s standard training paradigm, deepnets naturally achieve an implicit form of stability in the last-layer. In light of the previous discussions of the benefits of equal singular values, we of course expected the trained deep network would become more robust to adversaries, as the training progresses towards the Simplex ETF. The measurements we reported here support this prediction, and evidence in (50) gives further credence to this hypothesis.

Conclusion

This paper studied the terminal phase of training (TPT) of today’s canonical deepnet training protocol. It documented that during TPT a process called Neural Collapse takes place, involving four fundamental and interconnected phenomena: (NC1)-(NC4).

Prior to this work, it was becoming apparent, due to (29) and related work, that the last-layer classifier of a trained deepnet exhibits appreciable mathematical structure – a phenomenon called ‘inductive bias’ which was gaining ever-wider visibility. Our work exposes considerable additional fundamental, and we think, surprising, structure: (i) the last-layer features are not only linearly separable, but actually collapsed to a $C$-dimensional Simplex ETF, and (ii) the last-layer classifier is behaviorally equivalent to the Nearest Class-Center decision rule. Through our thorough experimentation on seven canonical datasets and three prototypical networks, we show that these phenomena persist across the range of canonical deepnet classification problems. Furthermore, we document that convergence to this simple structure aids in the improvement of out-of-sample network performance and robustness to adversarial examples. We hypothesize that the benefits of the interpolatory regime of overparametrized networks are directly related to Neural Collapse.

From a broader perspective, the standard workflow of empirical deep learning can be viewed as a series of arbitrary steps that happened to help win prediction challenge contests, which were then proliferated by their popularity among contest practitioners. Careful analysis, providing a full understanding of the effects and benefits of each workflow component, was never the point. One of the standard workflow practices is training beyond zero-error to zero-loss, i.e. TPT. In this new work, we give a clear understanding that TPT benefits today’s standard deep learning training paradigm by showing how it leads to the pervasive phenomenon of Neural Collapse. Moreover, this work puts older results on a new footing, expanding our understanding of their contributions. Finally, because of the precise mathematics and geometry, the doors are open for new formal insights.

This work was partially supported by NSF DMS 1407813, 1418362, and 1811614 and by private donors. Some of the computing for this project was performed on the Sherlock cluster at Stanford University; we thank the Stanford Research Computing Center for providing computational resources and support that enabled our research. Some of this project was also performed on Google Cloud Platform: thanks to Google Cloud Platform Education Grants Program for research credits that supplemented this work. Moreover, we thank Riccardo Murri and Hatef Monajemi for their extensive help with the Elasticluster and ClusterJob frameworks, respectively.

References

Supplementary Material

Suppose we ‘feature engineer’ (i.e., in some way, design) a matrix $\bm{M}$ of feature activation class means, with columns $[\bm{\mu}_{c}:c=1,\dots,C]$. We are given an observation $\bm{h}=\bm{\mu}_{\gamma}+\bm{z}$, $\bm{z}\sim\mathcal{N}(\mathbf{0},\sigma^{2}\bm{I})$, where $\gamma$ is an unknown class index, $\gamma\in\{1,\dots,C\}$. Moreover, we assume that $\gamma\sim\mbox{unif}\{1,\dots,C\}$ independently from $\bm{z}$. Our task is to recover $\gamma$ from $\bm{h}$, with as small an error rate as possible. Our basic question is

Which feature means matrices $\bm{M}$ will enable the optimal error rate?

In Information Theory terminology, the feature means $\bm{\mu}_{c}$ are codewords, and the matrix $\bm{M}$ is a codebook containing $C$ codewords. A transmitter transmits a codeword over a noisy channel, contaminated by white additive Gaussian noise, and then a receiver obtains the noisy signal $\bm{h}=\bm{\mu}_{\gamma}+\bm{z}$ which it then decodes in an attempt to recover the transmitted $\gamma$. Our task is to design a codebook and decoder that would allow optimal retrieval of the class identity $\gamma$ from the noisy information $\bm{h}$. Using the language of Information Theory (31), we could speak of codebook design, rather than feature engineering from Machine Learning. We will use a linear decoder, with weights $\bm{W}=[\bm{w}_{c}:c=1,\dots,C]$ and biases $\bm{b}=(b_{c})$:

In this language, our question then becomes

Which codebook $\bm{M}$ and linear decoder $\bm{W},\bm{b}$ will enable the optimal error rate?

Appendix B Theorem 5 from main manuscript

To measure success in this task, we consider the Large-Deviations Error Exponent:

where the maximum is over $C\times C$ matrices $\bm{M}$ with at most unit-norm columns, $C\times C$ matrices $\bm{W}$, and $C\times 1$ vectors $\bm{b}$.

All matrices $\bm{M}$ achieving $\beta^{\star}$ are also Simplex ETFs – possibly in another pose – deriving from $\bm{M}^{\star}$ via $\bm{M}=\bm{U}\bm{M}^{\star}$ with $\bm{U}$ a $C\times C$ orthogonal matrix. For such matrices, an optimal linear decoder is $\bm{W}={\bm{M}}^{\star}\bm{U}^{\top}$, $\bm{b}=\mathbf{0}$:

The proof follows from a series of lemmas – established in the following pages – and is given in Section G.G.2. ∎

Appendix C Large Deviations

Suppose that $\mathbf{0}\not\in\mathcal{K}$, and that $\mathcal{K}$ is a closed set. Suppose that $\bm{z}\sim\mathcal{N}(\mathbf{0},\sigma^{2}\bm{I})$. Then, as $\sigma\rightarrow 0$:

This lemma defines an optimization problem:

Denote the solution of the optimization problem $(P_{LD})$ by $\bm{z}^{\star}(\mathcal{K})$ and the value of the optimization problem by $\beta(\mathcal{K})=\frac{1}{2}\|\bm{z}^{\star}(\mathcal{K})\|_{2}^{2}$. The solution $\bm{z}^{\star}(\mathcal{K})$ is the closest point in $\mathcal{K}$ to $\{\mathbf{0}\}$. Conceptually, $\bm{z}^{\star}(\mathcal{K})$ is the “most likely way” for the “rare event” $\bm{z}\in\mathcal{K}$ to happen. The likelihood of this rare event obeys

C.2 Fundamental events causing misclassification

In this section, we identify fundamental events causing misclassification, and apply the large deviations result from Lemma 1 to study the misclassification probability $P\{\hat{\gamma}(\bm{h})\neq\gamma\}$.

Consider the event: $\mathcal{E}_{c,c^{\prime}}=$ “item from true underlying class $c$ is misclassified as $c^{\prime}$.” Correspondingly, consider the larger event

While $\mathcal{F}_{c,c^{\prime}}$ does not by itself imply $\mathcal{E}_{c,c^{\prime}}$, of course

Moreover, consider the event: $\mathcal{E}_{c}=$ “item from true underlying class $c$ is misclassified.” Then,

So the events $\mathcal{F}_{c,c^{\prime}}$ are fundamental.

Conceptually, $\bm{z}^{\star}(\mathcal{K}_{c,c^{\prime}})$, the optimal solution to , is the most likely way noise can cause a ‘pre-misclassification’ of $c$ as $c^{\prime}$. Label $\bm{z}^{\star}_{c,c^{\prime}}=\bm{z}^{\star}(\mathcal{K}_{c,c^{\prime}})$; set $\beta_{c,c^{\prime}}=\frac{1}{2}\|\bm{z}^{\star}_{c,c^{\prime}}\|_{2}^{2}$.

Considering the misclassification event $\mathcal{E}_{c}$, a large deviations analysis as $\sigma\rightarrow 0$ gives:

Finally, for the misclassification event $\mathcal{E}=\cup_{c}\mathcal{E}_{c}$, we have the LD exponent,

Thus, in this setting, minimizing the misclassification probability corresponds to maximizing $\beta$. This motivates the optimization problem studied in the following sections.

Appendix D Optimization Interpretation

Denote the optimum as $\bm{z}^{\star}=(\bm{z}^{\star}_{c,c^{\prime}}:c\neq c^{\prime})$ (in the cases of interest here it will be unique). Although phrased as a multi-component optimization problem across components $(\bm{z}_{c,c^{\prime}})$, it is actually separable, so $\beta_{c,c^{\prime}}=\frac{1}{2}\|\bm{z}^{\star}_{c,c^{\prime}}\|_{2}^{2}$. Moreover, the value of the optimization problem, $\mbox{\sc val}(P_{\bm{M},\bm{W},\bm{b}})$, is actually $\beta\equiv\min_{c^{\prime}\neq c}\beta_{c,c^{\prime}}$.

The value of the optimization problem, $\beta=\beta(\bm{M},\bm{W},\bm{b})=\mbox{\sc val}(P_{\bm{M},\bm{W},\bm{b}})$, implicitly defines a function of $\bm{M}$, $\bm{W}$, and $\bm{b}$. This notation shows that the LD exponent of misclassification error depends on $\bm{M}$ the codebook and the linear classifier $(\bm{W},\bm{b})$.

Recall the main problem we are trying to solve in this supplement:

Which codebook $\bm{M}$ and linear decoder $\bm{W},\bm{b}$ will enable the optimal error rate?

Using our new notation, this problem can be stated as follows:

Appendix E A Lower Bound

Suppose we are given $\bm{\mu}_{c}$ and $\bm{\mu}_{c^{\prime}}$, that $\bm{z}\sim\mathcal{N}(\mathbf{0},\sigma^{2}\bm{I})$, and that $\bm{h}=\bm{\mu}_{\gamma}+\bm{z}$, where $\gamma\in\{c,c^{\prime}\}$. Let $P_{c,\sigma}$ denote the probability measure governing $\bm{h}$, when $\gamma=c$ and $\sigma$ are as specified. We have this fundamental lower bound:

Consider the minimax test between $H_{0}:P_{c,\sigma}$ and $H_{1}:P_{c^{\prime},\sigma}$, minimizing the maximum of type I and type II errors. Let $\delta=\frac{1}{2}\|\bm{\mu}_{c}-\bm{\mu}_{c^{\prime}}\|_{2}$. The minimax error obeys:

Consider the $1$-dimensional parametric family $Q_{\theta}$ for $\theta\in$ with $Q_{0}=P_{c,\sigma}$, $Q_{1}=P_{c^{\prime},\sigma}$, where, in general, $Q_{\theta}$ is the probability measure of $\bm{h}=\bm{\nu}_{\theta}+\bm{z}$, and the mean vector $\bm{\nu}_{\theta}=\theta\bm{\mu}_{c}+(1-\theta)\bm{\mu}_{c^{\prime}}$. Note that $\delta=\|\bm{\nu}_{0}-\bm{\nu}_{1/2}\|_{2}$; also, let $\bm{u}=(\bm{\mu}_{c}-\bm{\mu}_{c^{\prime}})/\|\bm{\mu}_{c}-\bm{\mu}_{c^{\prime}}\|_{2}$, and note:

In general, by sufficiency and standard factorization properties of the multivariate normal $\mathcal{N}(\mathbf{0},\sigma^{2}\bm{I})$ which governs $\bm{z}$, the Neyman-Pearson test between $H_{0}$ and $H_{1}$ has the form

where the threshold derives from symmetry considerations. When $H_{1}$ is true,

and $P(\{\mbox{accept }H_{0}|H_{1}\})=P\{\mathcal{N}(0,\sigma^{2})>\delta\}$. Similarly, when $H_{0}$ is true,

and $P(\{\mbox{reject }H_{0}|H_{0}\})=P\{\mathcal{N}(0,\sigma^{2})<-\delta\}$. ∎

Let $\hat{\gamma}(\cdot)$ be a decision procedure that takes values in $\{c,c^{\prime}\}$ and suppose

Suppose that $\bm{z}\sim\mathcal{N}(\mathbf{0},\sigma^{2}\bm{I})$, and that $\bm{h}=\bm{\mu}_{\gamma}+\bm{z}$. Let $P_{c,\sigma}$ denote the probability measure governing $\bm{h}$, when $\gamma=c$ and $\sigma$ are as specified. Then, as $\sigma\rightarrow 0$:

The rule $\hat{\gamma}$ cannot possibly have worst-case (across $\gamma\in\{c,c^{\prime}\}$) probability of error better than the minimax test described in Lemma 2. Hence,

Since $\delta=\frac{1}{2}\|\bm{\mu}_{c}-\bm{\mu}_{c^{\prime}}\|_{2}$, we obtain:

Let $\bm{M}$ be a given codebook matrix with columns $\{\bm{\mu}_{c}\}_{c=1}^{C}$. Define

Then, for any decision rule $\hat{\gamma}$,

This motivates us to define the maximin codeword distance,

This distance controls the optimal $\beta$:

Appendix F Δ\Delta-Optimality of the Simplex Tight Frame

Let the columns of ${\bm{M}}^{\star}$ be denoted $\bm{\mu}_{c}^{\star}$ and those of $\bm{I}$ be denoted $\bm{\delta}_{c}$, $c=1,\dots,C$. By a side calculation $\|\bm{\mu}_{c}^{\star}\|=1$, $c=1,\dots,C$. The result then follows from

Moreover, the only matrices that achieve equality are ${\bm{M}}^{\star}$ or else matrices equivalent to it by orthogonal transformations from the left, $\bm{M}=\bm{U}{\bm{M}}^{\star}$, $\bm{U}^{\top}\bm{U}=\bm{I}$.

The argument follows four steps. First, for any matrix $\bm{M}$ with column lengths $\|\bm{\mu}_{c}\|_{2}\leq 1$, there is another matrix $\widetilde{\bm{M}}$ with all columns of unit length, obeying $\Delta(\widetilde{\bm{M}})\geq\Delta(\bm{M})$; see Lemma 8. Hence, for determining the global maximizer,

Thus, without loss of generality, we focus on the matrices $\bm{M}$ with column lengths $\|\bm{\mu}_{c}\|_{2}=1$, $c=1,\dots,C$.

Second, for any matrix $\bm{M}$ with column lengths $\|\bm{\mu}_{c}\|_{2}=1$, the off-diagonal entries of $\bm{M}^{\top}\bm{M}$ are at least $\frac{-1}{C-1}$. See Lemma 9.

Third, for two vectors $\bm{p}$, $\bm{q}$ both of norm 1, $\|\bm{p}\|_{2}=\|\bm{q}\|_{2}=1$, the distance $\|\bm{p}-\bm{q}\|_{2}^{2}=2-2\langle\bm{p},\bm{q}\rangle$. Hence, if $\langle\bm{p},\bm{q}\rangle\geq\frac{-1}{C-1}$, then

However, from the Lemma 5, we already know $\Delta(\bm{M}^{\star})=\sqrt{\frac{2C}{C-1}}$, so we conclude that:

In step 4, we show that every $C$ by $C$ matrix $\bm{M}$ attaining equality must be left-equivalent to $\bm{M}^{\star}$ by orthogonal rotation. This is handled in Lemma 11. ∎

By hypothesis, the standard unit “solid” sphere $\mathcal{B}_{1}$ contains the points $\{\bm{\mu}_{c}\}_{c=1}^{C}$. However, because at least one of the points is interior to $\mathcal{B}_{1}$, the standard unit sphere $\mathcal{S}^{C-1}$ is not the MES of those points by Lemma 7. The MES therefore has a radius $0<r<1$. The MES has a center $\bm{p}_{0}$, say, and we have

The Gram matrix $\bm{G}=(\langle\bm{\mu}_{c},\bm{\mu}_{c^{\prime}}\rangle)=\bm{M}^{\top}\bm{M}$ has diagonal entries $1$, and off-diagonal entries $\leq\rho$. Thus,

But, $\bm{G}$ is nonnegative semidefinite. Hence,

The Gram matrix $\bm{G}=(\langle\bm{\mu}_{c},\bm{\mu}_{c^{\prime}}\rangle)=\bm{M}^{\top}\bm{M}$ has diagonal entries $1$ and off-diagonal entries $\leq\frac{-1}{C-1}$. By assumption,

Suppose that $\bm{M}$ is a matrix having all columns vectors of length $1$, and every pair of interpoint distances

Then, $\bm{M}=\bm{U}{\bm{M}}^{\star}$, where $\bm{U}^{\top}\bm{U}=\bm{I}$.

Equivalently, since $\|\bm{\mu}_{c}\|_{2}=1$, $c=1,\dots,C$ by hypothesis,

The singular value decomposition of $\bm{M}=\bm{U}_{\bm{M}}\bm{D}\bm{V}^{\top}_{\bm{M}}$ can be taken to have $\bm{V}_{\bm{M}}=\bm{V}_{{\bm{M}}^{\star}}$, and with $\bm{U}_{\bm{M}}$ defined as follows: First, set $\bm{U}_{\bm{M}}^{0}=\bm{M}\bm{V}_{{\bm{M}}^{\star}}\sqrt{\bm{\Lambda}_{{\bm{M}}^{\star}}^{\dagger}}$, $\bm{U}^{0}_{{\bm{M}}^{\star}}={{\bm{M}}^{\star}}\bm{V}_{{\bm{M}}^{\star}}\sqrt{\bm{\Lambda}_{{\bm{M}}^{\star}}^{\dagger}}$. One can check that these are each partial isometries, omitting a one-dimensional range. Then, via a rank-one modification, we can generate the orthogonal matrices $\bm{U}_{\bm{M}}$ and $\bm{U}_{{\bm{M}}^{\star}}$.

We next verify that $\bm{M}=\bm{U}_{\bm{M}}\bm{D}\bm{V}^{\top}_{{\bm{M}}^{\star}}$ is a valid SVD of $\bm{M}$, where $\bm{D}=\text{diag}(\bm{\Lambda}_{{\bm{M}}^{\star}}^{1/2})$, and that ${\bm{M}}^{\star}=\bm{U}_{{\bm{M}}^{\star}}\bm{D}\bm{V}_{{\bm{M}}^{\star}}$ is also a valid SVD of ${\bm{M}}^{\star}$. Set $\bm{U}=\bm{U}_{\bm{M}}\bm{U}^{\top}_{{\bm{M}}^{\star}}$; it is orthogonal. Then, $\bm{M}=\bm{U}{{\bm{M}}^{\star}}$, where ${{\bm{M}}^{\star}}$ is the matrix of the standard Simplex ETF. Therefore, $\bm{M}$ is also the matrix of a Simplex ETF, only not the standard one.

Appendix G β\beta-Optimality of the Simplex Tight Frame

Solve the instance $\beta({\bm{M}}^{\star},{\bm{M}}^{\star},\mathbf{0})$ of the optimization problem $\beta(\bm{M},\bm{W},\bm{b})$ defined in . The solution $\bm{z}^{\star}=(\bm{z}^{\star}_{c,c^{\prime}})$ obeys:

For a given linear classifier rule $\hat{\gamma}(\bm{h})=\hat{\gamma}(\bm{h};\bm{W},\bm{b})$, define the decision regions $\Gamma_{c}\equiv\Gamma_{c}(\bm{W},\bm{b})\equiv\{\bm{h}:\hat{\gamma}(\bm{h})=c\}$, $c=1,\dots,C$. Note that these regions are invariant under simultaneous rescaling of $(\bm{W},\bm{b})\mapsto(a\bm{W},a\bm{b})$ for $a>0$:

Put $\hat{\gamma}^{\star}\equiv\hat{\gamma}(\bm{h};{\bm{M}}^{\star},{\bm{M}}^{\star},\mathbf{0})$, and define the decision regions $\Gamma_{c}^{\star}=\{\bm{h}:\hat{\gamma}^{\star}(\bm{h})=c\}$, $c=1,\dots,C$. Since the decision regions $\Gamma_{c}^{\star}$ do not change under a global rescaling of the $\bm{W}$-matrix, we propose that, instead of using the announced matrix $\bm{W}=\bm{M}^{\star}$, we instead use the rescaled matrix $\bm{W}^{\star}=\sqrt{\frac{C-1}{C}}\bm{M}^{\star}$. Namely, since $\Gamma_{c}^{\star}=\Gamma_{c}(\bm{W}^{\star},\mathbf{0})$, we compute the latter one. Note that $\bm{W}^{\star}$ has all singular values $1$ or , so it is a partial isometry, which will have calculational advantages.

Let $\bm{e}_{c,c^{\prime}}^{\star}$ denote the Euclidean closest member of $\Gamma_{c^{\prime}}$ to $\bm{\mu}_{c}$. An alternate, but equivalent, way of describing the optimization problem $\beta({\bm{M}}^{\star},\bm{W}^{\star},\mathbf{0})$ is to say that

In short, $\bm{z}_{c,c}^{\star}$ is precisely the least Euclidean norm displacement that can translate from $\bm{\mu}_{c}^{\star}$ to a member of $\Gamma_{c^{\prime}}^{\star}$, and the closest point in $\Gamma^{\star}_{c^{\prime}}$ arrived at in this way is precisely $\bm{e}^{\star}_{c,c^{\prime}}$. Hence,

i.e. the halfway point between $\bm{\mu}^{\star}_{c}$ and $\bm{\mu}^{\star}_{c^{\prime}}$. The statement to be proved, , is therefore equivalent to

We will verify that the candidate $\bm{m}^{\star}_{c,c^{\prime}}$ is indeed the Euclidean closest point to $\bm{\mu}^{\star}_{c}$ within $\Gamma_{c^{\prime}}^{\star}$. Such a candidate point is actually the halfway point along the line segment ${\cal S}_{c,c^{\prime}}$ joining $\bm{\mu}_{c}$ to $\bm{\mu}_{c^{\prime}}$. The candidate point is, therefore, identical to the closest point in $\Gamma_{c^{\prime}}^{\star}$ exactly when:

the candidate point is on the decision boundary;

the decision boundary is orthogonal to said line segment.

The decision boundary is, more explicitly,

We first show [a]: that $\bm{m}_{c,c^{\prime}}^{\star}\in\partial\Gamma_{c^{\prime}}(\bm{W}^{\star},\mathbf{0})$. Clearly,

Now, because $\bm{W}^{\star}=\sqrt{\frac{C-1}{C}}\bm{M}^{\star}$, which is symmetric and a partial isometry,

Hence, $\bm{W}^{\star}\bm{\mu}^{\star}_{c}=\bm{\mu}_{c}^{\star}$ and $\bm{W}^{\star}\bm{\mu}^{\star}_{c^{\prime}}=\bm{\mu}_{c^{\prime}}^{\star}$. Our explicit formula for ${\bm{M}}^{\star}$ shows that all on-diagonal terms are equal to each other and all off-diagonal terms are equal to each other. Hence, these off-diagonal terms obey

i.e. $\bm{m}^{\star}_{c,c^{\prime}}\in\partial\Gamma_{c^{\prime}}(\bm{W}^{\star},\mathbf{0})$; the candidate point is in the decision boundary, namely [a].

We now consider [b]: orthogonality. Define the linear space $\bm{N}=\{\bm{h}:(\bm{W}^{\star}\bm{h})(c)-(\bm{W}^{\star}\bm{h})(c^{\prime})=0\}$ and the linear space $\bm{G}=\mbox{lin}({\cal S}_{c,c^{\prime}}-\bm{m}^{\star}_{c,c^{\prime}})$, where $\mbox{lin}()$ denotes linear span. Our orthogonality assertion is equivalent to

Define $\bm{u}=(\bm{\mu}^{\star}_{c}-\bm{\mu}^{\star}_{c^{\prime}})/2$; in fact $\bm{G}=\mbox{lin}(\{\bm{u}\})$. So, we must show

Now each $\bm{h}\in\bm{N}$ can be decomposed as $\bm{h}=\bm{h}_{0}+\bm{h}_{1}$ where $\bm{h}_{0}\in\mbox{ker}({\bm{W}^{\star}})$ while $\bm{h}_{1}\in\mbox{range}({\bm{W}^{\star}})$. Explicit formulas for ${\bm{W}^{\star}}$ show that

Hence, $\bm{h}_{0}(c)=\bm{h}_{0}(c^{\prime})$. On the other hand, ${\bm{W}^{\star}}\bm{h}_{1}=\bm{h}_{1}$. Combining these two, if $(\bm{W}^{\star}\bm{h})(c)=(\bm{W}^{\star}\bm{h})(c^{\prime})$, then $\bm{h}_{1}(c)=\bm{h}_{1}(c^{\prime})$; and since always $\bm{h}_{0}(c)=\bm{h}_{0}(c^{\prime})$, we obtain $\bm{h}(c)=\bm{h}(c^{\prime})$. Rewriting as

which of course is true. This establishes orthogonality, [b], and completes the demonstration of , and hence of the main claim . ∎

By our earlier definitions, if $\bm{z}^{\star}=(\bm{z}_{c,c^{\prime}}^{\star})$ denotes a solution to $(P_{{\bm{M}}^{\star},\bm{M}^{\star},\mathbf{0}})$, then

G.2 Proof of Theorem 5

In view of the inequality and Theorem 6, we know that

From Corollary 13 and Theorem 6, we know that equality holds for the standard Simplex ETF:

Hence, $\beta^{\star}_{C}=\beta({\bm{M}}^{\star},{\bm{M}}^{\star},0)$; the Simplex ETF is $\beta$-optimal. It follows by orthogonal invariance of the decision problem, that for a Simplex ETF in any isometric pose, equality also holds:

So, Simplex ETF’s are all optimal. Finally, since such $\bm{M}$s are the only solutions to $\Delta^{\star}(\bm{M})=\Delta_{C}^{\star}$ obeying $\|\bm{M}\|_{2,\infty}\leq 1$, suppose we have some other candidate $\breve{\bm{M}}$, obeying $\|\breve{\bm{M}}\|_{2,\infty}\leq 1$ but not obeying $\breve{\bm{M}}=\bm{U}{\bm{M}}^{\star}$ for some orthogonal matrix $\bm{U}$. Then, Theorem 6 implies $\Delta(\breve{\bm{M}})<\Delta_{C}^{\star}$, and so,

Applying inequality to such a candidate $\breve{\bm{M}}$, we have

In short, any such candidate is suboptimal. We have thus described all choices of $\bm{M}$ achieving $\beta_{C}^{\star}$; just as claimed. ∎