# Neural Collapse versus Low-rank Bias:
Is Deep Neural Collapse Really Optimal?

Peter Súkeník
Institute of Science and Technology Austria
3400 Klosterneuburg, Austria
<EMAIL_ADDRESS>
&Marco Mondelli
Institute of Science and Technology Austria
3400 Klosterneuburg, Austria
<EMAIL_ADDRESS>
Christoph Lampert11footnotemark: 1
Institute of Science and Technology Austria
3400 Klosterneuburg, Austria
<EMAIL_ADDRESS>
Equal contribution

###### Abstract

Deep neural networks (DNNs) exhibit a surprising structure in their final
layer known as neural collapse (NC), and a growing body of works has currently
investigated the propagation of neural collapse to earlier layers of DNNs – a
phenomenon called deep neural collapse (DNC). However, existing theoretical
results are restricted to special cases: linear models, only two layers or
binary classification. In contrast, we focus on non-linear models of arbitrary
depth in multi-class classification and reveal a surprising qualitative shift.
As soon as we go beyond two layers or two classes, DNC stops being optimal for
the deep unconstrained features model (DUFM) – the standard theoretical
framework for the analysis of collapse. The main culprit is a low-rank bias of
multi-layer regularization schemes: this bias leads to optimal solutions of
even lower rank than the neural collapse. We support our theoretical findings
with experiments on both DUFM and real data, which show the emergence of the
low-rank structure in the solution found by gradient descent.

##  1 Introduction

What is the geometric structure of layers and learned representations in deep
neural networks (DNNs)? To address this question, Papyan et al. [40] focused
on the very last layer of DNNs at convergence and experimentally measured what
is now widely known as Neural Collapse (NC). This phenomenon refers to four
properties that simultaneously emerge during the terminal phase of training:
feature vectors of training samples from the same class collapse to the common
class-mean (NC1); the class means form a simplex equiangular tight frame or an
orthogonal frame (NC2); the class means are aligned with the rows of the last
layer’s weight matrix (NC3); and, finally, the classifier in the last layer is
a nearest class center classifier (NC4). Since the influential paper [40], a
line of research has aimed at explaining the emergence of NC theoretically,
mostly focusing on the unconstrained features model (UFM) [37]. In this model,
motivated by the network’s perfect expressivity, one treats the last layer’s
feature vectors as a free variable and explicitly optimizes them together with
the last layer’s weight matrix, “peeling off” the rest of the network [10,
24]. With UFM, the NC was demonstrated in a variety of settings, both as the
global optimum and as the convergence point of gradient flow.

The emergence of the NC in the last layer led to a natural research question –
does some form of collapse propagate beyond the last layer to earlier layers
of DNNs? A number of empirical works [21, 18, 44, 41, 36] gave evidence that
this is indeed the case, and we will refer to this phenomenon as Deep Neural
Collapse (DNC). On the theoretical side, the optimality of the DNC was
obtained _(i)_ for the UFM with two layers connected by a non-linearity in
[52], _(ii)_ for the UFM with several linear layers in [8], and _(iii)_ for
the deep UFM (DUFM) with non-linear activations in the context of binary
classification [49]. No existing work handles the general case in which there
are _multiple classes_ and the UFM is _deep_ and _non-linear_.

In this work, we close the gap and reveal a surprising behavior not occurring
in the simpler settings above: for multiple classes and layers, the DNC as
formulated in previous works is not an optimal solution of DUFM. In
particular, the class means at the optimum do not form an orthogonal frame
(nor an equiangular tight frame), thus violating the second property of DNC.

Let $L$ and $K$ denote the number of layers and classes, respectively. Then,
if either $L\geq 3$ and $K\geq 10$ or $L\geq 4$ and $K\geq 6$, we provide an
explicit combinatorial construction of a class of solutions that outperforms
DNC. Specifically, the loss achieved by our construction is a factor
$K^{(L-3)/(2L+2)}$ lower than the loss of the DNC solution. Our result holds
as long as all matrices are regularized.

We also identify the reason behind the sub-optimality of DNC: a _low-rank
bias_. Intuitively, this bias arises from the representation cost of a DNN
with $l_{2}$ regularization, which equals the Schatten-$p$ quasi norm [38] in
the deep linear case. The quasi norm is well approximated by the rank, and
this intuition carries over to the non-linear case as well. In fact, the rank
of our construction is $\Theta(\sqrt{K})$, while the rank of the DNC solution
is $K$. We note that after the application of the ReLU, the rank of the final
layer is again equal to $K$, in order to fit the training data. We also show
that the first property of neural collapse (convergence to class means)
continues to be strictly optimal even in this general setting and its deep
counterpart is approximately optimal with smoothed ReLU activations.

We support our theoretical results with empirical findings in three regimes:
_(i)_ DUFM training, _(ii)_ training on standard datasets (MNIST [32],
CIFAR-10 [29]) with DUFM-like regularization, and _(iii)_ training on standard
datasets with standard regularization. In all cases, gradient descent
retrieves solutions with very low rank, which can exhibit symmetric structures
in agreement with our combinatorial construction, see e.g. the lower-right
plot of Figure 4. We also investigate the effect of three common
hyperparameters – weight decay, learning rate and width – on the rank of the
solution at convergence. On the one hand, high weight decay, high learning
rate and small width lead to a strong low-rank bias. On the other hand, small
(yet still non-zero!) weight decay, small learning rate or large width (and
more complex datasets as well) lead to a higher-rank solution, even if that is
not the global optimum, and this solution often coincides with DNC, which is
in agreement with earlier experimental evidence. Altogether, our findings show
that if a DNC solution is found, it is not because of its global optimality,
but just because of an implicit bias of the optimization procedure.

The implications of our results go beyond deep neural collapse. In fact, our
theory suggests that even the NC2 in the last layer is not optimal, and this
is corroborated by our experiments, where the singular value structure of the
last layer’s class-mean matrices is imbalanced, ruling out orthogonality. This
means that standard single-layer UFM, as well as its deep-linear or two-layer
extensions, are not sufficient to describe the full picture, as they display a
qualitatively different phenomenology.

##  2 Related work

#### Neural Collapse.

Several papers (a non-exhaustive list includes [13, 16, 5, 33, 34, 59]) use
neural collapse as a practical tool in applications, among which OOD detection
and transfer learning are the most prevalent. On the theoretical side, the
emergence of NC has been investigated, with the majority of works considering
some form of UFM [37, 10]. [56, 35] show global optimality of NC under the
cross-entropy (CE) loss, and [60] under the MSE loss. Similar results are
obtained by [10, 50, 19, 9] for the class-imbalanced setting. [62, 24, 60]
refine the analysis by showing that the loss landscape of the UFM model is
benign – all stationary points are either local minima or strict saddle points
which can be escaped by conventional optimizers. A more loss-agnostic approach
connecting CE and MSE loss is considered in [61]. NC has also been analyzed
for a large number of classes [26], in an NTK regime [46], or in graph neural
networks [28]. We refer the reader to [27] for a survey.

The emergence of NC has also been studied through the lens of the gradient
flow dynamics. [37] considers MSE loss and small initialization, and [17] a
renormalized gradient flow of the last layer’s features after fixing the last
layer’s weights to be conditionally optimal. [24] studies the CE loss dynamics
and shows convergence in direction of the gradient flow to a KKT point of the
max-margin problem of the UFM, extending a similar analysis for the last
layer’s weights in [48]. The convergence speed under both losses is described
in [54]. Going beyond UFM, [58, 42, 43, 30] study the emergence of NC in
homogeneous networks under gradient flow; [39] provides sufficient conditions
for neural collapse; and [53] perturbs the unconstrained features to account
for the limitations of the model.

More recently, [21] mentions a possible propagation of the NC to earlier
layers of DNNs, giving preliminary measurements. These are then significantly
extended in [18, 44, 12, 41], which measure the emergence of some form of DNC
in DNNs. On the theoretical front, an extension to a two-layer non-linear
model is provided in [52], to a deep linear model in [8, 15] and to a deep
non-linear model for binary classification in [49]. Alternatively to DUFM, [4]
studies DNC in an end-to-end setting with a special layer-wise training
procedure.

#### Low-rank bias.

The low-rank bias is a well-known phenomenon, especially in the context of
matrix/tensor factorization and deep linear networks (see e.g. [2, 7, 45, 25,
55]). For non-linear DNNs, [51] studies the gradient flow optimization of ReLU
networks, giving lower and upper bounds on the average soft rank. [14] studies
SGD training on deep ReLU networks, showing upper bounds on the rank of the
weight matrices as a function of batch size, weight decay and learning rate.
[31] proves several training invariances that may lead to low-rank, but the
results require the norm of at least one weight matrix to diverge and the
architecture to end with a couple of linear layers. [3] presents bounds on the
singular values of non-linear layers in a rather generic setting, not
necessarily at convergence. More closely related to our work is [38], which
considers a deep linear network followed by a single non-linearity and then by
a single layer. Their arguments to study the low-rank bias are similar to the
intuitive explanation of Section 4. [20] shows that increasing the depth
results in lower effective rank of the penultimate layer’s Gram matrix both at
initialization and at convergence. The true rank is also measured, but on
rather shallow networks and it is far above the DNC rank. [1] shows a strong
low-rank bias of sharpness-aware minimization, although only in layers where
DNC does not yet occur and the rank is high. [11, 23] study special functional
ranks (Jacobi and bottleneck) of DNNs, providing asymptotic results and
empirical measurements. These results are refined in [22, 57], which show a
bottleneck structure of the rank both experimentally and theoretically. The
measurements of the singular values at convergence in [57] are in agreement
with those of Section 6.3. We highlight that none of the results above allows
to reason about DNC optimality, as they focus on infinite width/depth,
effective or functional ranks, orthogonal settings, or are not quantitative
enough.

##  3 Preliminaries

We study the class balanced setting with $N=Kn$ samples from $K$ classes, $n$
per class. Let $f(x)=W_{L}\sigma(W_{L-1}\sigma(\dots
W_{1}\mathcal{B}(x)\dots))$ be a DNN with backbone $\mathcal{B}(\cdot)$. The
backbone represents the majority of the deep network _before_ the last $L$
layers, e.g. the convolutional part of a ResNet20. Let
$X\in\mathbb{R}^{d\times N}$ be the training data, and
$H_{1}=\mathcal{B}(X_{0})\in\mathbb{R}^{d_{1}\times
N},H_{2}=\sigma(W_{1}X_{1})\in\mathbb{R}^{d_{2}\times
N},\dots,H_{L}=\sigma(W_{L-1}X_{L-1})\in\mathbb{R}^{d_{L}\times N}$ its
feature vector representations in the last $L$ layers, with $\tilde{X}_{l}$
denoting their counterparts before applying the ReLU $\sigma$. We refer to
$h^{l}_{ci}$ and $\tilde{h}^{l}_{ci}$ as to the $i$-th sample of $c$-th class
of $H_{l}$ and $\tilde{H}_{l}$, respectively. Let
$\mu^{l}_{c}=\frac{1}{n}\sum_{i=1}^{n}h^{l}_{ci}$ and
$\tilde{\mu}^{l}_{c}=\frac{1}{n}\sum_{i=1}^{n}\tilde{h}^{l}_{ci}$ be the class
means at layer $l$ after and before applying $\sigma$, and
$M_{l},\tilde{M}_{l}$ the matrices of the respective class means stacked into
columns. We organize the training samples so that the labels
$Y\in\mathbb{R}^{K\times N}$ equal $I_{K}\otimes\mathbf{1}_{n}^{T},$ where
$I_{K}$ is a $K\times K$ identity matrix, $\otimes$ is the Kronecker product
and $\mathbf{1}_{n}$ the all-one vector of size $n.$

#### Deep neural collapse (DNC).

As there are no biases in our network model, the second property of DNC
requires the class mean matrices to be orthogonal (instead of forming an ETF)
[44, 49].

######  Definition 1.

We say that layer $l$ exhibits DNC 1, 2 or 3 if the corresponding conditions
are satisfied (the properties can be stated for both after and before the
application of ReLU):

  * DNC1:

The within-class variability of either $H_{l}$ or $\tilde{H}_{l}$ is $0$.
Formally, $h_{ci}^{l}=h_{cj}^{l},\tilde{h}_{ci}^{l}=\tilde{h}_{cj}^{l}$ for
all $i,j\in[n]$ or, in matrix notation,
$H_{l}=M_{l}\otimes\mathbf{1}_{n}^{T},\tilde{H}_{l}=\tilde{M}_{l}\otimes\mathbf{1}_{n}^{T}.$

  * DNC2:

The class-mean matrices $M_{l},\tilde{M}_{l}$ are orthogonal, i.e.,
$M_{l}^{T}M_{l}\propto I_{K},\tilde{M}_{l}^{T}\tilde{M}_{l}\propto I_{K}$.

  * DNC3:

The rows of the weight matrix $W_{l}$ are either 0 or collinear with one of
the columns of the class-means matrix $M_{l}.$

#### Deep unconstrained features model.

To define DUFM, we generalize the model in [49] to an arbitrary number of
classes $K.$

######  Definition 2.

The $L$-layer deep unconstrained features model ($L$-DUFM) denotes the
following optimization problem:

$\displaystyle\min_{H_{1},W_{1},\dots,W_{L}}\ $
$\displaystyle\frac{1}{2N}\left\lVert W_{L}\sigma(W_{L-1}\sigma(\dots
W_{2}\sigma(W_{1}H_{1})\dots))-Y\right\rVert_{F}^{2}+\sum_{l=1}^{L}\frac{\lambda_{W_{l}}}{2}\left\lVert
W_{l}\right\rVert_{F}^{2}+\frac{\lambda_{H_{1}}}{2}\left\lVert
H_{1}\right\rVert_{F}^{2},$ (1)

where $\left\lVert\cdot\right\rVert_{F}$ denotes the Frobenius norm and
$\lambda_{H_{1}},\lambda_{W_{1}},\ldots,\lambda_{W_{L}}>0$ are regularization
parameters.

##  4 Low-rank solutions outperform deep neural collapse

#### Intuitive explanation of the low-rank bias.

Consider a simplified version of $L-$DUFM:

$\displaystyle\min_{H_{1},W_{1},\dots,W_{L}}\ $
$\displaystyle\frac{1}{2N}\left\lVert W_{L}\sigma(W_{L-1}\dots
W_{2}W_{1}H_{1})-Y\right\rVert_{F}^{2}+\sum_{l=1}^{L}\frac{\lambda_{W_{l}}}{2}\left\lVert
W_{l}\right\rVert_{F}^{2}+\frac{\lambda_{H_{1}}}{2}\left\lVert
H_{1}\right\rVert_{F}^{2}.$ (2)

Compared to (1), (2) removes all non-linearities except in the last layer,
making the remaining part of the network a deep linear model, a construction
similar to the one in [38]. Now, we leverage the variational form of the
Schatten-$p$ quasi-norm [47], which gives

$\displaystyle
c\left\lVert\tilde{H}_{L}\right\rVert_{S_{2/L}}^{2/L}=\underset{H_{1},W_{1},\dots,W_{L-1}:H_{1}W_{1}\dots
W_{L-1}=\tilde{H}_{L}}{\min}\sum_{l=1}^{L-1}\frac{\lambda_{W_{l}}}{2}\left\lVert
W_{l}\right\rVert_{F}^{2}+\frac{\lambda_{H_{1}}}{2}\left\lVert
H_{1}\right\rVert_{F}^{2},$

where $c$ can be computed explicitly. Thus, after solving for
$H_{1},W_{1},\dots,W_{L-1}$, the simplified $L$-DUFM problem (2) can be
reduced to

$\displaystyle\min_{\tilde{H}_{L}W_{L}}\ $
$\displaystyle\frac{1}{2N}\left\lVert
W_{L}\sigma(\tilde{H}_{L})-Y\right\rVert_{F}^{2}+\frac{\lambda_{W_{L}}}{2}\left\lVert
W_{L}\right\rVert_{F}^{2}+\frac{\lambda_{\tilde{H}_{L}}}{2}\left\lVert\tilde{H}_{L}\right\rVert_{S_{2/L}}^{2/L}.$

For large values of $L$,
$\left\lVert\tilde{H}_{L}\right\rVert_{S_{2/L}}^{2/L}$ is well approximated by
the rank of $\tilde{H}_{L}.$ Hence, the objective value is low when the output
$W_{L}H_{L}$ fits $Y$ closely, while keeping $\tilde{H}_{L}$ low-rank, which
justifies the low-rank bias. Crucially, the presence of additional non-
linearities in the $L$-DUFM model (1) does not change this effect much, as
long as one is able to define solutions for which most of the intermediate
feature matrices $\tilde{H}_{l}$ are non-negative (so that ReLU does not have
an effect).

#### Low-rank solution outperforming DNC.

We define the combinatorial solution that outperforms DNC, starting from the
graph structure on which the construction is based.

######  Definition 3.

A triangular graph $\mathcal{T}_{n}$ of order $n$ is a line graph of a
complete graph $\mathcal{K}_{n}$ of order $n$. $\mathcal{T}_{n}$ has
${n\choose 2}$ vertices, each representing an edge of the complete graph, and
there is an edge between a pair of vertices if and only if the corresponding
edges in the complete graph share a vertex. Moreover, let $T_{n}$ be the
normalized incidence matrix of $\mathcal{K}_{n},$ i.e.,
$(T_{n})_{i,j}=\frac{1}{\sqrt{n-1}}$ if vertex $i$ belongs to edge $j$ and 0
otherwise. Let $G_{n}$ denote the adjacency matrix of $\mathcal{T}_{n}.$

We recall that $\mathcal{T}_{n}$ is a strongly regular graph with parameters
$(n(n-1)/2,2(n-2),n-2,4)$ and spectrum $2(n-2)$ with multiplicity 1, $n-4$
with multiplicity $n-1$ and $-2$ with multiplicity $n(n-3)/2.$ Next, we
construct an explicit solution $(H_{1},W_{1},\dots,W_{L})$ based on the
triangular graph. For ease of exposition, we focus on the case where the
number of classes $K$ equals $r\choose 2$ for some $r\geq 4$, deferring the
general definition to Appendix A.1.

######  Definition 4.

Let $K={r\choose 2}$ for $r\geq 4$. Then, a strongly regular graph (SRG)
solution of the $L$-DUFM problem (1) is obtained by setting the matrices
$(H_{1},W_{1},\dots,W_{L})$ as follows. For all $l,$ the feature matrices
$H_{l},\tilde{H}_{l}$ are DNC1 collapsed, i.e.,
$H_{l}=M_{l}\otimes\mathbf{1}_{n}^{T},\tilde{H}_{l}=\tilde{M}_{l}\otimes\mathbf{1}_{n}^{T}$.
For $2\leq l\leq L-1$, $M_{l}=\tilde{M}_{l}$, each row of $\tilde{M}_{l}$ is a
non-negative multiple of a row of $T_{r}$ (as in Definition 3), and the sum of
squared norms of the rows of $\tilde{M}_{l}$ corresponding to a row of $T_{r}$
is the same for each row of $T_{r}$. For $l=1,$ $W_{1},M_{1}$ are any pair of
matrices minimizing the objective conditionally on $M_{2}$ defined above. For
$l\geq 2$, $W_{l}$ minimizes the objective conditional to input and output to
that layer. Let $A_{L}$ be a $K\times r$ matrix where the set of rows equals
the set of vectors with two $(-1)$ entries and $r-2$ $(+1)$ entries. Then,
$M_{L}=\sigma(\tilde{M}_{L})$, the rows of $\tilde{M}_{L}$ are a non-negative
multiple of $A_{L}T_{r}$, and the sum of their squared norms corresponding to
either row of $A_{L}T_{r}$ is equal. Finally, the Frobenius norms (i.e.
scales) of $M_{1},W_{1},\dots,W_{L}$ are chosen so as to minimize (1) while
satisfying the construction above.

Figure 1: Strongly regular graph (SRG) solution with $L=4$, $K=10$ and $r=5$.
Left: Class-mean matrix of the third layer $M_{3}$. The non-zero entries of
each row have the same value and their number is $r-1$, which corresponds to
the degree of the complete graph $\mathcal{K}_{r}$. Middle: Class-mean matrix
of the fourth layer before ReLU $\tilde{M}_{4}$ (middle left), and its Gram
matrix $\tilde{M}_{4}^{T}\tilde{M}_{4}$ (middle right). The SRG construction
has very low rank before ReLU: ${\rm rank}(\tilde{M}_{4})=r$ and ${\rm
rank}(\sigma(\tilde{M}_{4}))=K$. Right: $\tilde{M}_{4}^{T}\tilde{M}_{4}$ for
DNC. The DNC solution has rank $K$ in all layers before and after ReLU.

In this construction, columns and rows of class-mean matrices are associated
to edges and vertices of the complete graph $\mathcal{K}_{r}$. Each row
(corresponding to a vertex) has non-zero entries at columns that correspond to
edges containing the vertex. In the final layer, each row of $\tilde{M}_{L}$
corresponds to a weighting of vertices in $\mathcal{K}_{r}$ s.t. exactly two
vertices get $-1$ weight and the rest $+1$, and the value at a column is the
sum of the values of the vertices of the edge. The class-mean matrices of the
SRG solution are illustrated in Figure 1 for $L=4$ and $K=10$ (which gives
$r=5$): we display $M_{3},\tilde{M}_{4},\tilde{M}_{4}^{T}\tilde{M}_{4}$ and,
for comparison, also $\tilde{M}_{4}^{T}\tilde{M}_{4}$ of a DNC solution. Very
similar solutions to SRG are shown for $K=6$ and $K=15$ in Figures 7 and 8 of
Appendix B.1.

Let us highlight the properties of the SRG solution, which are crucial to
outperform DNC. First, the rank of the intermediate feature and weight
matrices is very low, only of order $\Theta(K^{1/2})$, since by construction
there are only $r=\Theta(K^{1/2})$ linearly independent rows. This is
contrasted with the DNC solution that has rank $K$ in all intermediate feature
and weight matrices. The low rank of the SRG solution is due to the specific
structure of the triangular graph, which has many eigenvalues equal to $-2$
that become 0 after adding twice a diagonal matrix. Second, the definition of
$\tilde{M}_{L}$ ensures that $M_{L}=\sigma(\tilde{M}_{L})$ has full rank $K$.
This allows the output $W_{L}M_{L}$ to also have full rank and, therefore, fit
the identity matrix $I_{K}$, thus reducing the first term in the loss (1).
Finally, the highly symmetric nature of the SRG solution balances the feature
and weight matrices so as to minimize large entries and, therefore, the
Frobenius norms, thus reducing the other terms in the loss (1).

#### Main result.

For any $L$-DUFM problem (specified by $K,n$ and all the regularization
parameters), let $\mathcal{L}_{SRG},\mathcal{L}_{DNC}$ be the losses incurred
by the SRG and DNC solutions, see Definitions 4 and 1, respectively. At this
point we are ready to state our key result.

######  Theorem 5.

If $K\geq 6,L\geq 4$ or $K\geq 10,L=3$ and $d_{l}\geq K$ for all $l$, then
$\mathcal{L}_{SRG}<\mathcal{L}_{DNC}.$ Moreover, consider any sequence of
$L$-DUFM problems for which $K\xrightarrow[]{}\infty$ so that
$0.499>\mathcal{L}_{DNC}$ for each problem. In that case,

$\frac{\mathcal{L}_{SRG}}{\mathcal{L}_{DNC}}=\mathcal{O}(K^{\frac{3-L}{2(L+1)}}).$
(3)

In words, as long as the number of classes and layers is not too small, the
SRG solution always outperforms the collapsed one and the gap grows with the
number of classes $K$.

The proof first computes the conditionally optimal values of $\left\lVert
W_{l}\right\rVert_{F}^{2}$ for both the SRG and DNC solutions. The specific
structure of these solutions enables to calculate pseudoinverses of the
intermediate features, thus enabling the explicit computation of the weight
norms. All these values depend only on the singular values of the feature
matrices, which are explicitly given by their scale. As a result, both
$\mathcal{L}_{SRG}$ and $\mathcal{L}_{DNC}$ are expressed via an optimization
problem in a single scalar variable and, by comparing these problems, the
statement follows. The details are deferred to Appendix A.1.

Although the argument requires $L\geq 3,K\geq 10$ or $L\geq 4,K\geq 6,$ the
experiments in Appendix B.1 show that the DNC solution is not optimal when
$L\geq 4,K\geq 3$ or $L=3,K\geq 7$. Furthermore, for $L=3$ and large $K$,
there is a large gap between $\mathcal{L}_{SRG}$ and $\mathcal{L}_{DNC}$ (even
if (3) trivializes). For either $K=2$ or $L=2$, the DNC is optimal [52, 49].

##  5 Within-class variability collapse is still optimal

While the DNC2 property conflicts with the low-rank bias, the same is not true
for DNC1, as the within-class variability collapse supports a low rank. We
show below that the last-layer NC1 property remains optimal for any $L$-DUFM
problem. A proof sketch follows, with the complete argument deferred to
Appendix A.2.

######  Theorem 6.

The optimal solutions of the $L$-DUFM (1) exhibit DNC1 at layer $L$, i.e.,

$H_{L}^{*}=M_{L}^{*}\otimes\mathbf{1}_{n}^{T}$

holds for any optimal solution $(H_{1}^{*},W_{1}^{*},\dots,W_{L}^{*})$ of the
$L$-DUFM problem.

Proof sketch: Assume by contradiction that there exists an optimal solution of
(1) with regularization parameters
$(\lambda_{H_{1}},\lambda_{W_{1}},\dots,\lambda_{W_{L}})$, denoted as
$(H_{1}^{*},W_{1}^{*},\dots,W_{L}^{*})$, which does not exhibit neural
collapse at layer $L$. Then, we can construct two different optimal solutions
of the $L$-DUFM problem with $n=1$ and regularization parameters
$(n\lambda_{H_{1}},\lambda_{W_{1}},\dots,\lambda_{W_{L}})$ of the form
$(H_{1}^{(1)},W_{1}^{*},\dots,W_{L}^{*})$ and
$(H_{1}^{(2)},W_{1}^{*},\dots,W_{L}^{*})$. These two solutions share the
weight matrices, and $H_{1}$ (and, therefore, $H_{L}$) only differs in a
single column (w.l.o.g., the first column). The optimality of these solutions
can be proved using separability and symmetry of the loss function w.r.t. the
columns of $H_{1}.$

Denote the first (differing) columns of $H_{L}^{(1)}$ and $H_{L}^{(2)}$ as $x$
and $y$, respectively. By exploiting the linearity of the loss function on a
ray $\\{th_{11}^{1},t\geq 0\\}$ for any $h_{11}^{1}$, a direct computation
gives that $x$ and $y$ are not aligned. Let $\mathcal{L}$ be the loss in (1).
By optimality of both solutions, we get

$\left.\frac{\partial\mathcal{L}}{\partial
W_{L}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{(1)},W_{1}^{*},\dots,W_{L}^{*})}=0=\left.\frac{\partial\mathcal{L}}{\partial
W_{L}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{(2)},W_{1}^{*},\dots,W_{L}^{*})}.$
(4)

An application of the chain rule gives

$\frac{\partial\mathcal{L}}{\partial
W_{L}}=\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{L+1}}\frac{\partial\tilde{H}_{L+1}}{\partial
W_{L}}+\lambda_{W_{L}}W_{L}=\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{L+1}}H_{L}^{T}+\lambda_{W_{L}}W_{L},$

where $\tilde{H}_{L+1}$ is the model output and $\mathcal{L}_{F}$ the first
term of $\mathcal{L}$, corresponding to the label fit. Plugging this back into
(4) and using that $W_{L}^{*}$ is the same in both expressions, we get
$A(H_{L}^{(1)})^{T}=B(H_{L}^{(2)})^{T},$ where we have denoted by $A$ and $B$
the partial derivatives
$\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{L+1}}$ evaluated at
$(H_{1}^{(1)},W_{1}^{*},\dots,W_{L}^{*})$ and
$(H_{1}^{(2)},W_{1}^{*},\dots,W_{L}^{*})$, respectively. As $\mathcal{L}_{F}$
is separable with respect to the columns of $H_{l},\tilde{H}_{l}$ for all $l$,
the matrices $A,B$ can only differ in their first columns (denoted by $a,b$),
and they are identical otherwise. This implies that $ax^{T}=by^{T}$. After
some simple considerations and using that $x$ and $y$ are not aligned, we
reach a contradiction, as we conclude that $x\neq y$ is impossible. ∎

The difficulty in extending Theorem 6 to a result on the unique optimality of
DNC1 for all layers stems from the special role of $W_{L}$ as the loss is
differentiable w.r.t. it. By considering a differentiable relaxation of ReLU,
we show below an approximate result for a relaxed $L$-DUFM model.

######  Definition 7.

We denote by ReLUϵ (or $\sigma_{\epsilon}$) a function satisfying the
following conditions: (i) $\sigma_{\epsilon}(x)=\sigma(x)$, for
$x\in(-\infty,0]\cup[\epsilon,\infty),$ (ii)
$0<\sigma_{\epsilon}(x)<\sigma(x)$ for $x\in(0,\epsilon)$, and (iii)
$\sigma_{\epsilon}$ is continuously differentiable with derivative bounded by
a universal constant and strictly positive on $(0,\epsilon)$.

######  Theorem 8.

Denote by $L$-DUFMϵ the equivalent of (1), with $\sigma$ replaced by
$\sigma_{\epsilon}$. Let $D=\max\\{d_{2},d_{3},\dots,d_{L}\\}$ and
$\bar{\lambda}=\lambda_{H_{1}}\lambda_{W_{1}}\dots\lambda_{W_{L}}$, with the
regularization parameters upper bounded by $1/(L+1)$. Then, for any globally
optimal solution of the $L$-DUFMϵ problem, the distance between any two
feature vectors of the same class in any layer is at most

$\displaystyle\frac{6\epsilon\sqrt{D(L+1)}}{(L+1)^{L+1}\bar{\lambda}\sqrt{n}}.$
(5)

In words, as the activation function approaches ReLU (i.e., $\epsilon\to 0$),
the within-class variability tends to $0$. The proof starts with a similar
strategy as the argument of Theorem 6 and then explicitly tracks the error due
to replacing $\sigma$ with $\sigma_{\epsilon}$ through the layers. The full
argument is in Appendix A.2.

##  6 Numerical results

We employ the standard DNC1 metric
$\text{tr}(\Sigma_{W})/\text{tr}(\Sigma_{B}^{\dagger}),$ where
$\Sigma_{W},\Sigma_{B}$ are the within and between class variabilities and
$X^{\dagger}$ is a pseudo-inverse of $X.$ This is widely used in the
literature [53, 44, 4] and considered more stable than other metrics [44]. We
measure the DNC2 metric as the condition number of $M_{l}$ for $l\geq 1$ [49].
We do not measure DNC3 here, as it is not well-defined for solutions that do
not satisfy DNC2. For end-to-end DNN experiments, we employ a model from [49]
where an MLP with a few layers is attached to a ResNet20 backbone. The output
of the backbone is then treated as unconstrained features, and DNC metrics are
measured for the MLP layers.

###  6.1 DUFM training

We start with the $L$-DUFM model (1), training both features and weights. In
the top row of Figure 2, we consider a $4$-DUFM, with $K=10$ and $n=50$,
presenting the training progression of the losses (left plot), the DNC1
metrics (center plot) and the singular values at convergence (right plot).

The results are in excellent agreement with our theory. First, the training
loss outperforms that of the DNC solution, and it is rather close to that of
the SRG solution. Second, DNC1 holds in a clear way in all layers, especially
in the last ones. Third, the solution at convergence exhibits a strong low
rank bias: the ranks of intermediate layers range from 5 to 8, and they are
always the same in all intermediate layers within one run. For comparison, we
recall that the intermediate layers of the DNC solution have full rank $K=10$.
Finally, for a few runs, the Gram matrices of the intermediate class means
resulting from gradient descent training coincide with those of an SRG
solution.

Figure 2: Training loss compared against DNC and SRG losses (left), DNC1
metric training progression (middle) and singular value distribution at
convergence (right). Top row: $4$-DUFM training with $K=10$, $\lambda=0.004$
for all regularization parameters, learning rate of $0.5$ and width $30$.
Results are averaged over 10 runs, and we show the confidence intervals at $1$
standard deviation. Bottom row: Training of a ResNet20 with a 4-layer MLP head
on CIFAR10, using a DUFM-like regularization. We use weight decay $0.005$
except $\lambda_{H_{1}}=0.000005$ (to compensate for $n=5000$, which
significantly influences the total regularization strength), learning rate
$0.05$ and width $64$ for all the MLP layers. Results are averaged over 5
runs, and we show the confidence intervals at $1$ standard deviation.

#### Impact of number of classes and depth.

For $K=2$ or $L=2,$ we recover the results of [49, 52] irrespective of other
hyperparameters. The higher the number of classes, the more prevalent are low-
rank solutions, while finding DNC solutions becomes challenging. The same
holds for increasing the number of layers. For $L=3$ and low number of classes
($K\leq 6$), we weren’t able to experimentally find solutions that would
outperform DNC, which aligns nicely with the fact that SRG outperforms DNC
only from $K=10$ for $L=3$. For large number of classes, the difference
between the loss of low-rank solutions and the DNC loss is considerable
already for $L=3$ and becomes even larger for higher $L.$ This is illustrated
in the left plot of Figure 3.

For $L\leq 5$ and moderate number of classes ($K\leq 30$), gradient descent
solutions are as follows: until layer $L-1$, feature matrices share the same
rank and have similar Gram matrices; intermediate activations are typically
non-negative, and the ReLU has no effect; then, the rank jumps to $K$ after
the final ReLU, as pre-activations are also negative. For large $L$ or large
$K,$ the rank of the first few layers is low, growing gradually in the last
couple of layers (see Figure 6 in Appendix B.1); the ReLU is active only in
the final layers. This means that not only very low-rank solutions outperform
DNC (as shown by our theory), but such solutions are routinely reached by
gradient descent.

#### Impact of weight decay and width.

While neither weight decay nor width influence Theorem 5 – which shows that
DNC is not optimal – both quantities influence the nature of the solutions
found by gradient descent. In particular, the stronger the weight decay, the
lower the rank, see the middle plot in Figure 3. For very small weight decay,
DNC is sometimes recovered; for very high weight decay, it is never recovered.
The width has an opposite effect, see the right plot of Figure 3. For small
width, low-rank solutions are much more likely to be found; large width has a
strong implicit bias towards DNC and, thus, rank $K$ solutions. This means
that, surprisingly, a larger width leads to a larger loss, since low-rank
solutions exhibit a smaller loss than DNC. Thus, at least in DUFM, the
infinite-width limit prevents gradient descent from finding a globally optimal
solution, and sub-optimal solutions are reached with increasingly high
probability.

Figure 3: All experiments refer to the training of an $L$-DUFM model. Results
are averaged over 5 runs, and we show the confidence intervals at $1$ standard
deviation. Left: Ratio between SRG and DNC loss
($\mathcal{L}_{SRG}/\mathcal{L}_{DNC}$), as a function of $r$, where the
number of classes is $K={r\choose 2}$. Different curves correspond to
different values of $L\in\\{3,4,5\\}$. Middle: Average rank at convergence, as
a function of the weight decay in $\log_{2}$-scale, when $L=4$ and $K=15$.
Right: Empirical probability of finding a DNC solution as a function of the
width, when $L=4$ and $K=10$.

###  6.2 End-to-end experiments with DUFM-like regularization

Next, we train a DNN backbone with an MLP head, regularizing only the output
of the backbone and the layers of the MLP head (and not the layers of the
backbone). This regularization is closer to our theory than the standard one,
since we explicitly regularize the Frobenius norm of the unconstrained
features. We also note that training with such a regularization scheme is
easier than training with the standard regularization scheme. In the bottom
row of Figure 2, we consider a ResNet20 backbone with a 4-layer MLP head
trained on CIFAR10.

The results agree well with our theory, and they are qualitatively similar to
those of Section 6.1 for DUFM training. The DNNs consistently outperform the
DNC loss, but still achieve DNC1. The ranks of class-mean matrices range from
5 to 6, and they are always the same in all intermediate layers within one
run. Remarkably, the SRG solution was found by gradient descent also in this
setting.

Both weight decay and learning rate affect the average rank of the solutions
found by gradient descent. Varying the width can lead to unexpected results,
as it changes the ratio between the number of parameters in the MLP and that
in the backbone, so the effect of the width is harder to interpret. Similar
results can be seen on MNIST.

###  6.3 End-to-end experiments

Finally, we perform experiments with standard regularization and the same
architecture (i.e., DNN backbone plus MLP head) as in Section 6.2. In
particular, in Figure 4 we consider a ResNet20 backbone with a 5-layer MLP
head trained on CIFAR10 and MNIST with standard weight regularization.

Overall, the results remain qualitatively similar to those discussed above.
This demonstrates that, in spite of a different loss landscape compared to
previous settings, the low-rank bias is still responsible for DNC2 not being
attained. Specifically, for CIFAR10, the rank in the third layer ranges
between 8 and 9, and for MNIST ranges between 5 and 7; in contrast, the DNC
solution has rank $K=10$. All DNNs display DNC1 across all layers. Remarkably,
for the MNIST experiment the solution found by gradient descent is the SRG
solution (compare the gram matrices in bottom right plot of Figure 4 with the
right-most plot of Figure 1).

Figure 4: Training of a ResNet20 with a 5-layer MLP head on CIFAR-10 (top row)
and MNIST (bottom row), using the standard regularization. We pick a large
weight decay ($0.08$ for CIFAR-10 and $0.04$ for MNIST) and a large learning
rate ($0.005$ for CIFAR-10 and $0.01$ for MNIST). Results are averaged over 5
runs, and we show the confidence intervals at $1$ standard deviation. Left:
DNC1 metric training progression. Middle: Singular value distributions at
convergence for all the layers. Right: Gram matrices of $M_{3}$ (CIFAR-10) and
$M_{5}$ (MNIST).

The difficulty of the learning task plays a significant role in this setting:
when training on MNIST, it is rather easy to reach low-rank solutions and
rather difficult to reach DNC solutions and the rank depends heavily on the
regularization strength as shown in Figure 10 of Appendix B.3; when training
on CIFAR-10, the weight decay needs to be high for the class mean matrices to
be rank deficient. Moreover, the learning rate no longer exhibits a clear
relation with the rank, since gradient descent diverges when the learning is
too large. We also observe that the rank deficiency is the strongest in the
mid-layer of the MLP head, creating a “rank bottleneck”, as mentioned in [23,
22, 57]. In fact, these works also measure extremely low ranks, but [23, 22]
do it on synthetic data with very low inner dimension, while [57] focuses on
fully convolutional architectures trained with CE loss and including biases.

In summary, Figure 4 shows that both the low-rank bias and the optimality of
DNC1 carry over to the standard training regime. This means that there are
hyperparameter settings for which deep neural collapse, including in the very
last layer, is not reached (and likely not even optimal). Although the sub-
optimality of DNC in the last layer is not proved formally, this phenomenon is
supported by evidence across all experimental settings and further
corroborated by our theory where our SRG construction is far from being
DNC2-collapsed in the last layer.

##  7 Conclusion

In this work, we reveal that the deep neural collapse is not an optimal
solution of the deep unconstrained features model – the extension of the
widely used unconstrained features model. This finding considerably changes
our overall understanding of DNC, as all the previous models in simplified
settings showed the global optimality of neural collapse and of its deep
counterpart. The main culprit – the low-rank bias – makes the orthogonal frame
property of DNC, and thus DNC as a whole, too high rank to be optimal. We
demonstrate this low-rank bias across a variety of experimental settings, from
DUFM training to end-to-end training with the standard weight regularization.
While the structure of the Gram matrices of class means is not captured by
orthogonal matrices (or by the ETF), the within-class variability collapse
remains optimal. Our theoretical analysis proves this for the DUFM problem,
and our numerical results showcase the phenomenon across various settings.

Our analysis focuses on the MSE loss, but we expect similar results to hold
for the cross-entropy loss and, in particular, that the same SRG construction
proposed here would still refute the optimality of DNC. We leave as an open
question whether DNC1 is strictly optimal across all layers. While proving
this would likely require new ideas, we note that none of our experiments
converged to a solution that would not be DNC1-collapsed.

## Acknowledgements

M. M. is partially supported by the 2019 Lopez-Loreta Prize.

## References

  * [1] Maksym Andriushchenko, Dara Bahri, Hossein Mobahi, and Nicolas Flammarion.  Sharpness-aware minimization leads to low-rank features.  In Conference on Neural Information Processing Systems (NeurIPS), volume 36, 2023.
  * [2] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo.  Implicit regularization in deep matrix factorization.  In Conference on Neural Information Processing Systems (NeurIPS), 2019.
  * [3] Bradley T Baker, Barak A Pearlmutter, Robyn Miller, Vince D Calhoun, and Sergey M Plis.  Low-rank learning by design: the role of network architecture and activation linearity in gradient rank collapse.  arXiv preprint arXiv:2402.06751, 2024.
  * [4] Daniel Beaglehole, Peter Súkeník, Marco Mondelli, and Mikhail Belkin.  Average gradient outer product as a mechanism for deep neural collapse.  arXiv preprint arXiv:2402.13728, 2024.
  * [5] Ido Ben-Shaul and Shai Dekel.  Nearest class-center simplification through intermediate layers.  In Topological, Algebraic and Geometric Learning Workshops, 2022.
  * [6] James R Bunch, Christopher P Nielsen, and Danny C Sorensen.  Rank-one modification of the symmetric eigenproblem.  Numerische Mathematik, 31(1), 1978.
  * [7] Hung-Hsu Chou, Carsten Gieshoff, Johannes Maly, and Holger Rauhut.  Gradient descent for deep matrix factorization: Dynamics and implicit bias towards low rank.  Applied and Computational Harmonic Analysis, 68, 2024.
  * [8] Hien Dang, Tan Nguyen, Tho Tran, Hung Tran, and Nhat Ho.  Neural collapse in deep linear network: From balanced to imbalanced data.  In International Conference on Machine Learning (ICML), 2023.
  * [9] Hien Dang, Tho Tran, Tan Nguyen, and Nhat Ho.  Neural collapse for cross-entropy class-imbalanced learning with unconstrained ReLU feature model.  arXiv preprint arXiv:2401.02058, 2024.
  * [10] Cong Fang, Hangfeng He, Qi Long, and Weijie J Su.  Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training.  In Proceedings of the National Academy of Sciences (PNAS), volume 118, 2021.
  * [11] Ruili Feng, Kecheng Zheng, Yukun Huang, Deli Zhao, Michael Jordan, and Zheng-Jun Zha.  Rank diminishing in deep neural networks.  In Conference on Neural Information Processing Systems (NeurIPS), 2022.
  * [12] Tomer Galanti, Liane Galanti, and Ido Ben-Shaul.  On the implicit bias towards minimal depth of deep neural networks.  arXiv preprint arXiv:2202.09028, 2022.
  * [13] Tomer Galanti, András György, and Marcus Hutter.  Improved generalization bounds for transfer learning via neural collapse.  In First Workshop on Pre-training: Perspectives, Pitfalls, and Paths Forward at ICML, 2022.
  * [14] Tomer Galanti, Zachary S Siegel, Aparna Gupte, and Tomaso Poggio.  SGD and weight decay provably induce a low-rank bias in neural networks.  arXiv preprint arXiv:2206.05794, 2022.
  * [15] Connall Garrod and Jonathan P Keating.  Unifying low dimensional observations in deep learning through the deep linear unconstrained feature model.  arXiv preprint arXiv:2404.06106, 2024.
  * [16] Jarrod Haas, William Yolland, and Bernhard T Rabus.  Linking neural collapse and l2 normalization with improved out-of-distribution detection in deep neural networks.  Transactions on Machine Learning Research (TMLR), 2022.
  * [17] X. Y. Han, Vardan Papyan, and David L Donoho.  Neural collapse under mse loss: Proximity to and dynamics on the central path.  In International Conference on Learning Representations (ICLR), 2022.
  * [18] Hangfeng He and Weijie J Su.  A law of data separation in deep learning.  Proceedings of the National Academy of Sciences, 120(36), 2023.
  * [19] Wanli Hong and Shuyang Ling.  Neural collapse for unconstrained feature model under cross-entropy loss with imbalanced data.  arXiv preprint arXiv:2309.09725, 2023.
  * [20] Minyoung Huh, Hossein Mobahi, Richard Zhang, Brian Cheung, Pulkit Agrawal, and Phillip Isola.  The low-rank simplicity bias in deep networks.  Transactions on Machine Learning Research, 2022.
  * [21] Like Hui, Mikhail Belkin, and Preetum Nakkiran.  Limitations of neural collapse for understanding generalization in deep learning.  arXiv preprint arXiv:2202.08384, 2022.
  * [22] Arthur Jacot.  Bottleneck structure in learned features: Low-dimension vs regularity tradeoff.  In Conference on Neural Information Processing Systems (NeurIPS), 2023.
  * [23] Arthur Jacot.  Implicit bias of large depth networks: a notion of rank for nonlinear functions.  In International Conference on Learning Representations (ICLR), 2023.
  * [24] Wenlong Ji, Yiping Lu, Yiliang Zhang, Zhun Deng, and Weijie J Su.  An unconstrained layer-peeled perspective on neural collapse.  In International Conference on Learning Representations (ICLR), 2022.
  * [25] Ziwei Ji and Matus Telgarsky.  Gradient descent aligns the layers of deep linear networks.  In International Conference on Learning Representations (ICLR), 2018.
  * [26] Jiachen Jiang, Jinxin Zhou, Peng Wang, Qing Qu, Dustin G Mixon, Chong You, and Zhihui Zhu.  Generalized neural collapse for a large number of classes.  In Conference on Parsimony and Learning (Recent Spotlight Track), 2023.
  * [27] Vignesh Kothapalli.  Neural collapse: A review on modelling principles and generalization.  In Transactions on Machine Learning Research (TMLR), 2023.
  * [28] Vignesh Kothapalli, Tom Tirer, and Joan Bruna.  A neural collapse perspective on feature evolution in graph neural networks.  In Conference on Neural Information Processing Systems (NeurIPS), volume 36, 2023.
  * [29] Alex Krizhevsky and Geoffrey Hinton.  Learning multiple layers of features from tiny images.  Technical report, University of Toronto, 2009.
  * [30] Daniel Kunin, Atsushi Yamamura, Chao Ma, and Surya Ganguli.  The asymmetric maximum margin bias of quasi-homogeneous neural networks.  In International Conference on Learning Representations (ICLR), 2022.
  * [31] Thien Le and Stefanie Jegelka.  Training invariances and the low-rank phenomenon: beyond linear networks.  In International Conference on Learning Representations (ICLR), 2022.
  * [32] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11), 1998.
  * [33] Xiao Li, Sheng Liu, Jinxin Zhou, Xinyu Lu, Carlos Fernandez-Granda, Zhihui Zhu, and Qing Qu.  Principled and efficient transfer learning of deep models via neural collapse.  In Conference on Parsimony and Learning (Recent Spotlight Track), 2023.
  * [34] Zexi Li, Xinyi Shang, Rui He, Tao Lin, and Chao Wu.  No fear of classifier biases: Neural collapse inspired federated learning with synthetic and fixed classifier.  In Conference on Computer Vision and Pattern Recognition (CVPR), 2023.
  * [35] Jianfeng Lu and Stefan Steinerberger.  Neural collapse under cross-entropy loss.  Applied and Computational Harmonic Analysis, 59, 2022.
  * [36] Wojciech Masarczyk, Mateusz Ostaszewski, Ehsan Imani, Razvan Pascanu, Piotr Miłoś, and Tomasz Trzcinski.  The tunnel effect: Building data representations in deep neural networks.  Conference on Neural Information Processing Systems (NeurIPS), 36, 2023.
  * [37] Dustin G Mixon, Hans Parshall, and Jianzong Pi.  Neural collapse with unconstrained features.  arXiv preprint arXiv:2011.11619, 2020.
  * [38] Greg Ongie and Rebecca Willett.  The role of linear layers in nonlinear interpolating networks.  arXiv preprint arXiv:2202.00856, 2022.
  * [39] Leyan Pan and Xinyuan Cao.  Towards understanding neural collapse: The effects of batch normalization and weight decay.  arXiv preprint arXiv:2309.04644, 2023.
  * [40] Vardan Papyan, X. Y. 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 (PNAS), volume 117, 2020.
  * [41] Liam Parker, Emre Onal, Anton Stengel, and Jake Intrater.  Neural collapse in the intermediate hidden layers of classification neural networks.  arXiv preprint arXiv:2308.02760, 2023.
  * [42] Tomaso Poggio and Qianli Liao.  Explicit regularization and implicit bias in deep network classifiers trained with the square loss.  arXiv preprint arXiv:2101.00072, 2020.
  * [43] Tomaso Poggio and Qianli Liao.  Implicit dynamic regularization in deep networks.  Technical report, Center for Brains, Minds and Machines (CBMM), 2020.
  * [44] Akshay Rangamani, Marius Lindegaard, Tomer Galanti, and Tomaso Poggio.  Feature learning in deep classifiers through intermediate neural collapse.  Technical Report, 2023.
  * [45] Noam Razin, Asaf Maman, and Nadav Cohen.  Implicit regularization in tensor factorization.  In International Conference on Machine Learning (ICML), 2021.
  * [46] Mariia Seleznova, Dana Weitzner, Raja Giryes, Gitta Kutyniok, and Hung-Hsu Chou.  Neural (tangent kernel) collapse.  In Conference on Neural Information Processing Systems (NeurIPS), volume 36, 2023.
  * [47] Fanhua Shang, Yuanyuan Liu, Fanjie Shang, Hongying Liu, Lin Kong, and Licheng Jiao.  A unified scalable equivalent formulation for Schatten quasi-norms.  Mathematics, 8(8), 2020.
  * [48] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro.  The implicit bias of gradient descent on separable data.  In Journal of Machine Learning Research, volume 19, 2018.
  * [49] Peter Súkeník, Marco Mondelli, and Christoph Lampert.  Deep neural collapse is provably optimal for the deep unconstrained features model.  In Conference on Neural Information Processing Systems (NeurIPS), 2023.
  * [50] Christos Thrampoulidis, Ganesh Ramachandra Kini, Vala Vakilian, and Tina Behnia.  Imbalance trouble: Revisiting neural-collapse geometry.  In Conference on Neural Information Processing Systems (NeurIPS), 2022.
  * [51] Nadav Timor, Gal Vardi, and Ohad Shamir.  Implicit regularization towards rank minimization in relu networks.  In Algorithmic Learning Theory (ALT), 2023.
  * [52] Tom Tirer and Joan Bruna.  Extended unconstrained features model for exploring deep neural collapse.  In International Conference on Machine Learning (ICML), 2022.
  * [53] Tom Tirer, Haoxiang Huang, and Jonathan Niles-Weed.  Perturbation analysis of neural collapse.  In International Conference on Machine Learning (ICML), 2023.
  * [54] Peng Wang, Huikang Liu, Can Yaras, Laura Balzano, and Qing Qu.  Linear convergence analysis of neural collapse with unconstrained features.  In NeurIPS Workshop on Optimization for Machine Learning (OPT), 2022.
  * [55] Zihan Wang and Arthur Jacot.  Implicit bias of SGD in $L_{2}$-regularized linear DNNs: One-way jumps from high to low rank.  In International Conference on Learning Representations (ICLR), 2024.
  * [56] E Weinan and Stephan Wojtowytsch.  On the emergence of simplex symmetry in the final and penultimate layers of neural network classifiers.  In Mathematical and Scientific Machine Learning, 2022.
  * [57] Yuxiao Wen and Arthur Jacot.  Which frequencies do CNNs need? Emergent bottleneck structure in feature learning.  arXiv preprint arXiv:2402.08010, 2024.
  * [58] Mengjia Xu, Akshay Rangamani, Qianli Liao, Tomer Galanti, and Tomaso Poggio.  Dynamics in deep classifiers trained with the square loss: Normalization, low rank, neural collapse, and generalization bounds.  In Research, volume 6, 2023.
  * [59] Jiawei Zhang, Yufan Chen, Cheng Jin, Lei Zhu, and Yuantao Gu.  EPA: neural collapse inspired robust out-of-distribution detector.  arXiv preprint arXiv:2401.01710, 2024.
  * [60] Jinxin Zhou, Xiao Li, Tianyu Ding, Chong You, Qing Qu, and Zhihui Zhu.  On the optimization landscape of neural collapse under MSE loss: Global optimality with unconstrained features.  In International Conference on Machine Learning (ICML), 2022.
  * [61] Jinxin Zhou, Chong You, Xiao Li, Kangning Liu, Sheng Liu, Qing Qu, and Zhihui Zhu.  Are all losses created equal: A neural collapse perspective.  In Conference on Neural Information Processing Systems (NeurIPS), 2022.
  * [62] Zhihui Zhu, Tianyu Ding, Jinxin Zhou, Xiao Li, Chong You, Jeremias Sulam, and Qing Qu.  A geometric analysis of neural collapse with unconstrained features.  In Conference on Neural Information Processing Systems (NeurIPS), 2021.

##  Appendix A Proofs

###  A.1 Low-rank solutions outperform deep neural collapse

We start by providing more detailed definitions of SRG and DNC solutions.

######  Definition 9.

Let $K={r\choose 2}$ for $r\geq 4$. Then, a strongly regular graph (SRG)
solution of the $L$-DUFM problem (1) is obtained by setting the matrices
$(H_{1},W_{1},\dots,W_{L})$ as follows. For all $l$, the feature matrices
$H_{l},\tilde{H}_{l}$ are DNC1 collapsed, i.e.,
$H_{l}=M_{l}\otimes\mathbf{1}_{n}^{T},\tilde{H}_{l}=\tilde{M}_{l}\otimes\mathbf{1}_{n}^{T}.$
For $2\leq l\leq L-1$, $M_{l}=\tilde{M}_{l}$ and $M_{l}=A_{l}T_{r}$, where
each row of $A_{l}$ is a multiple of the standard basis vector of dimension
$r$ and the sum of squared multiples corresponding to one basis vector equals
the same parameter $\alpha_{l}.$ In other words, each row of $M_{l}$ is a
multiple of a row of $T_{r}$ and the sum of squared norms of the rows of
$M_{l}$ corresponding to a row of $T_{r}$ is the same for each row of $T_{r}$.
For $l=1,$ $W_{1},M_{1}$ are any pair of matrices that minimize the objective
conditionally on $M_{2}$ being defined as above. For $l\geq 2$, $W_{l}$
minimizes the objective conditional to the input and output to that layer. Let
$A_{L}^{(1)}$ be a $K\times r$ matrix where each row has exactly two $(-1)$
entries and exactly $r-2$ $(+1)$ entries. Then, normalize the matrix
$A_{L}^{(1)}T_{r}$ so that each row is unit norm and multiply from the left
with $A_{L}^{(2)}$ of dimension $d_{L}\times K$, where each of the rows of
$A_{l}^{(2)}$ is a multiple of a standard basis vector of dimension $K$ and
the total sum of squared multiples corresponding to each basis vector is
$\alpha_{L}.$ Then, $\tilde{M}_{L}$ is obtained via this procedure, and
$M_{L}=\sigma(\tilde{M}_{L}).$ Finally, the parameters
$\\{\alpha_{l}\\}_{l=2}^{L}$ satisfy

$\begin{split}\alpha_{l}&=\frac{\left(\sqrt{n\lambda_{H_{1}}\lambda_{W_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)\right)^{l-2}}{r^{l-2}\prod_{i=2}^{l-1}\lambda_{W_{i}}}q^{l},\qquad
2\leq l\leq L-1,\\\
\alpha_{L}&=\frac{\left(\sqrt{n\lambda_{H_{1}}\lambda_{W_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)\right)^{L-2}4((r-2)(r-3)+2)}{r^{L-1}(r-1)^{2}\prod_{i=2}^{L-1}\lambda_{W_{i}}}q^{L},\end{split}$
(6)

and the parameter $q\geq 0$ is chosen to minimize the objective function in
(1).

######  Definition 10.

A deep neural collapse (DNC) solution for any number of classes $K$ of the
$L$-DUFM problem (1) is obtained by setting the matrices
$(H_{1},W_{1},\dots,W_{L})$ as follows. For all $l,$ the feature matrices
$H_{l},\tilde{H}_{l}$ are DNC1 collapsed, i.e.,
$H_{l}=M_{l}\otimes\mathbf{1}_{n}^{T},\tilde{H}_{l}=\tilde{M}_{l}\otimes\mathbf{1}_{n}^{T}.$
For $2\leq l\leq L$, $M_{l}=\tilde{M}_{l}$ and
$M_{l}^{T}M_{l}=\alpha_{l}I_{K}.$ For $l=1,$ $W_{1},M_{1}$ are any pair of
matrices that minimize the objective conditionally on $M_{2}$ being defined as
above. For $l\geq 2$, $W_{l}$ minimizes the objective conditional to the input
and output to that layer. Finally, the parameters $\\{\alpha_{l}\\}_{l=2}^{L}$
satisfy

$\displaystyle\alpha_{l-1}$
$\displaystyle=\frac{\lambda_{W_{L-1}}^{l-1}}{\lambda_{H_{1}}n\prod_{i=1}^{l-1}\lambda_{W_{i}}}q^{l-1},\qquad
2\leq l\leq L-1,$ $\displaystyle\alpha_{L}$
$\displaystyle=\frac{\lambda_{W_{L-1}}^{L-1}}{\lambda_{H_{1}}n\prod_{i=1}^{L-2}\lambda_{W_{i}}}q^{L},$

and the parameter $q\geq 0$ is chosen to minimize the objective function in
(1).

Next, we define the SRG solution when $K\neq{r\choose 2}$ for any $r$, and
provide two constructions, each useful for different parts of the proof of
Theorem 5.

######  Definition 11.

A strongly regular graph (SRG) solution for $K\geq 6$ of the $L$-DUFM problem
(1), is obtained in one of the two following ways.

  1. 1.

First, we take the largest $r$ s.t. $K\geq{r\choose 2}$ and construct the SRG
solution $(\bar{H}_{1},\bar{W}_{1},\dots,\bar{W}_{L})$ as in Definition 9
setting the number of classes to $r\choose 2$. Next, we construct a DNC
solution $(\tilde{H}_{1},\tilde{W}_{1},\dots,\tilde{W}_{L})$ as in Definition
10 setting the number of classes to $K-{r\choose 2}.$ Then, to construct
$H_{1}$ of the SRG solution, we create it as a diagonal block matrix with
number of columns equal to $K$ and number of rows equal to
$\bar{d}_{1}+\tilde{d}_{1},$ where these are the numbers of rows of the
respective $H$ matrices; the first block is $\bar{H}_{1}$, the second block is
$\tilde{H}_{1}$111The order is not important, both the rows and the columns
can afterward be permuted if we accordingly permute also the weight matrices.,
and the off-diagonal blocks are zero matrices. Similarly, we extend the weight
matrices such that, for any $l$, $W_{l}$ is a block diagonal matrix where the
number of rows is $\tilde{d}_{l+1}+\bar{d}_{l+1}$ and the number of columns is
$\tilde{d}_{l}+\bar{d}_{l}$; the first block is $\bar{W}_{l}$, the second
block is $\tilde{W}_{l}$, and the off-diagonal blocks are zero matrices.

  2. 2.

First, we take the smallest $r$ s.t. $K\leq{r\choose 2}$ and construct the SRG
solution as in Definition 9 setting the number of classes to $r\choose 2$.
Then, we just remove the ${r\choose 2}-K$ columns of $H_{1}$ that achieve the
highest individual fit losses (in case of a tie choose arbitrarily), and
define the SRG solution as the original solution without these columns.

We recall our main result and give the proof.

See 5

###### Proof.

We start by considering the case $K={r\choose 2}$ for some $r.$ Without loss
of generality we can assume $n=1$, because all comparisons are between
solutions that are by definition DNC1 collapsed, and the ratio
$\mathcal{L}_{SRG}/\mathcal{L}_{DNC}$ in the theorem statement does not depend
on $n.$

We first compute the loss of the SRG solution as in Definition 9 up to only
one degree of freedom. Let us go term-by-term. The simplest to evaluate is
$\frac{\lambda_{W_{l}}}{2}\left\lVert W_{l}\right\rVert_{F}^{2}$ for $2\leq
l\leq L-2.$ Using Lemma 13 (which relies on Lemma 12), we get

$\frac{\lambda_{W_{l}}}{2}\left\lVert
W_{l}\right\rVert_{F}^{2}=\frac{r\lambda_{W_{l}}}{2}\frac{\alpha_{l+1}}{\alpha_{l}}.$

Similarly, for layer $L-1$, we use Lemma 14 (again relying on Lemma 12) to
compute:

$\frac{\lambda_{W_{L-1}}}{2}\left\lVert
W_{L-1}\right\rVert_{F}^{2}=\frac{r^{2}(r-1)^{2}\lambda_{W_{L-1}}}{8((r-2)(r-3)+2)}\frac{\alpha_{L}}{\alpha_{L-1}}.$

Combining Lemma 15 with Lemma 18 we get:

$\frac{\lambda_{W_{1}}}{2}\left\lVert
W_{1}\right\rVert_{F}^{2}+\frac{\lambda_{H_{1}}}{2}\left\lVert
H_{1}\right\rVert_{F}^{2}=\sqrt{\lambda_{W_{1}}\lambda_{H-1}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)\alpha_{2}^{\frac{1}{2}}.$

Finally, combining Lemma 17 with Lemma 16 we get:

$\displaystyle\frac{1}{2K}\left\lVert
W_{L}M_{L}-I_{K}\right\rVert_{F}^{2}+\frac{\lambda_{W_{L}}}{2}\left\lVert
W_{L}\right\rVert_{F}^{2}$
$\displaystyle=\frac{\lambda_{W_{L}}}{2}\frac{1}{\frac{(r-2)(5r-19)}{(r-2)(r-3)+2}\alpha_{L}+\frac{r(r-1)}{2}\lambda_{W_{L}}}$
$\displaystyle+\frac{\lambda_{W_{L}}}{2}\frac{r-1}{\frac{2(r-3)^{2}}{(r-2)(r-3)+2}\alpha_{L}+\frac{r(r-1)}{2}\lambda_{W_{L}}}$
$\displaystyle+\frac{\lambda_{W_{L}}}{2}\frac{\frac{r(r-3)}{2}}{\frac{2}{(r-2)(r-3)+2}\alpha_{L}+\frac{r(r-1)}{2}\lambda_{W_{L}}}.$

The total loss of the SRG solution is just the sum of all these terms, which
is expressed in terms of $\alpha_{2},\alpha_{3},\dots,\alpha_{L}.$ We now
verify that the choice in (6) minimizes the loss, having set
$q\equiv\alpha_{2}^{1/2}.$ To do so, we compute the partial derivatives of
$\mathcal{L}$ w.r.t. the $\alpha_{l}$’s and set them to $0$:

$\displaystyle 0$
$\displaystyle=\frac{\partial\mathcal{L}}{\partial\alpha_{2}}=-r\lambda_{W_{2}}\frac{\alpha_{3}}{\alpha_{2}^{2}}+\sqrt{\lambda_{W_{1}}\lambda_{H-1}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)\alpha_{2}^{-\frac{1}{2}}\iff$
$\displaystyle\frac{\alpha_{3}}{\alpha_{2}}$
$\displaystyle=\frac{\sqrt{\lambda_{W_{1}}\lambda_{H-1}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)}{r\lambda_{W_{2}}}q.$

For $3\leq l\leq L-2$, we have

$\displaystyle 0=\frac{\partial\mathcal{L}}{\partial\alpha_{l}}$
$\displaystyle=-\frac{r\lambda_{W_{l}}}{2}\frac{\alpha_{l+1}}{\alpha_{l}^{2}}+\frac{r\lambda_{W_{l-1}}}{2}\frac{1}{\alpha_{l-1}}\iff$
$\displaystyle\frac{\alpha_{l+1}}{\alpha_{l}}$
$\displaystyle=\frac{\lambda_{W_{l-1}}}{\lambda_{W_{l}}}\frac{\alpha_{l}}{\alpha_{l-1}}.$

And finally, for layer $L-1$, we have

$\displaystyle 0$
$\displaystyle=\frac{\partial\mathcal{L}}{\partial\alpha_{L-1}}=-\frac{\lambda_{W_{L-1}}}{2}\frac{r^{2}(r-1)^{2}}{4((r-2)(r-3)+2)}\frac{\alpha_{L}}{\alpha_{L-1}^{2}}+\frac{r\lambda_{W_{L-2}}}{2}\frac{1}{\alpha_{L-2}}\iff$
$\displaystyle\frac{\alpha_{L}}{\alpha_{L-1}}$
$\displaystyle=\frac{\lambda_{W_{L-2}}}{\lambda_{W_{L-1}}}\frac{4((r-2)(r-3)+2)}{r(r-1)^{2}}\frac{\alpha_{L-1}}{\alpha_{L-2}}.$

Denoting by
$p=\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)$,
we can express these fractions as

$\displaystyle\frac{\alpha_{l+1}}{\alpha_{l}}=\frac{p}{r\lambda_{W_{l}}}q,\qquad
2\leq l\leq L-2,$
$\displaystyle\frac{\alpha_{L}}{\alpha_{L-1}}=\frac{4((r-2)(r-3)+2)p}{r^{2}(r-1)^{2}\lambda_{W_{L-1}}}q,$

which gives the expressions in (6). Finally, plugging this back into the loss
function we get a univariate $q$-dependent function of the following form:

$\displaystyle\mathcal{L}_{SRG}(q)$
$\displaystyle=\frac{\lambda_{W_{L}}}{2}\frac{1}{\frac{4(r-2)(5r-19)\left(\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)\right)^{L-2}}{r^{L-1}(r-1)^{2}\prod_{i=2}^{L-1}\lambda_{W_{i}}}q^{L}+\frac{r(r-1)}{2}\lambda_{W_{L}}}$
$\displaystyle+\frac{\lambda_{W_{L}}}{2}\frac{r-1}{\frac{8(r-3)^{2}\left(\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)\right)^{L-2}}{r^{L-1}(r-1)^{2}\prod_{i=2}^{L-1}\lambda_{W_{i}}}q^{L}+\frac{r(r-1)}{2}\lambda_{W_{L}}}$
$\displaystyle+\frac{\lambda_{W_{L}}}{2}\frac{\frac{r(r-3)}{2}}{\frac{8\left(\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)\right)^{L-2}}{r^{L-1}(r-1)^{2}\prod_{i=2}^{L-1}\lambda_{W_{i}}}q^{L}+\frac{r(r-1)}{2}\lambda_{W_{L}}}$
$\displaystyle+\frac{L}{2}\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)q.$

The loss of the DNC solution can be computed by a simple extension of the
expression $(17)$ from [49]:

$\displaystyle\mathcal{L}_{DNC}(q)=\frac{\lambda_{W_{L}}}{2}\frac{\frac{r(r-1)}{2}}{\frac{\lambda_{W_{L-1}}^{L-1}}{\lambda_{H_{1}}\prod_{i=1}^{L-2}\lambda_{W_{i}}}q^{L}+\frac{r(r-1)}{2}\lambda_{W_{L}}}+\frac{L}{2}\frac{r(r-1)}{2}\lambda_{W_{L-1}}q.$

At this point, we split our analysis for $L=3$ and for $L>3$. We start with
$L>3$, which is simpler.

Analysis for $L>3$. As $K\geq 6$, the following upper bound holds:

$\displaystyle\mathcal{L}_{SRG}(q)\leq\bar{\mathcal{L}}_{SRG}(q):=$
$\displaystyle\frac{\lambda_{W_{L}}}{2}\frac{\frac{r(r-1)}{2}}{\frac{8\left(\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)\right)^{L-2}}{r^{L-1}(r-1)^{2}\prod_{i=2}^{L-1}\lambda_{W_{i}}}q^{L}+\frac{r(r-1)}{2}\lambda_{W_{L}}}$
$\displaystyle+\frac{L}{2}\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)q.$

Now we reparametrize $\mathcal{L}_{DNC}(q)$ and the upper bound on
$\mathcal{L}_{SRG}(q)$, so that they look as similar as possible. By replacing
$\lambda_{W_{L-1}}q$ with $q$, we get

$\displaystyle\underset{q\geq 0}{\min}\hskip
2.84526pt\mathcal{L}_{DNC}(q)=\underset{q\geq 0}{\min}\hskip
2.84526pt\frac{\lambda_{W_{L}}}{2}\frac{\frac{r(r-1)}{2}}{\frac{1}{\lambda_{H_{1}}\prod_{i=1}^{L-1}\lambda_{W_{i}}}q^{L}+\frac{r(r-1)}{2}\lambda_{W_{L}}}+\frac{L}{2}r\frac{(r-1)}{2}q.$
(7)

Similarly, by replacing
$\frac{\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)}{r}q$
with $q$, we get:

$\displaystyle\underset{q\geq 0}{\min}\hskip
2.84526pt\bar{\mathcal{L}}_{SRG}(q)=\underset{q\geq 0}{\min}\hskip 2.84526pt$
$\displaystyle\frac{\lambda_{W_{L}}}{2}\frac{\frac{r(r-1)}{2}}{\frac{8r}{\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)^{2}(r-1)^{2}\lambda_{H_{1}}\prod_{i=1}^{L-1}\lambda_{W_{i}}}q^{L}+\frac{r(r-1)}{2}\lambda_{W_{L}}}$
$\displaystyle+\frac{L}{2}rq.$

Next, by replacing
$\left(\frac{8r}{\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)^{2}(r-1)^{2}}\right)^{\frac{1}{L}}q$
with $q$, we get:

$\displaystyle\underset{q\geq 0}{\min}\hskip
2.84526pt\bar{\mathcal{L}}_{SRG}(q)=\underset{q\geq 0}{\min}\hskip 2.84526pt$
$\displaystyle\frac{\lambda_{W_{L}}}{2}\frac{\frac{r(r-1)}{2}}{\frac{1}{\lambda_{H_{1}}\prod_{i=1}^{L-1}\lambda_{W_{i}}}q^{L}+\frac{r(r-1)}{2}\lambda_{W_{L}}}$
(8)
$\displaystyle+\frac{L}{2}r\left(\frac{\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)^{2}(r-1)^{2}}{8r}\right)^{\frac{1}{L}}q.$

After the reparameterization, $\mathcal{L}_{DNC}(q)$ and
$\bar{\mathcal{L}}_{SRG}(q)$ have almost the same form except for the
multiplier $\frac{r-1}{2}$ in the DNC case and

$\left(\frac{\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)^{2}(r-1)^{2}}{8r}\right)^{\frac{1}{L}}$

in the SRG case. Therefore, the inequality between $\mathcal{L}_{DNC}$ and
$\bar{\mathcal{L}}_{SRG}$ is fully determined by the inequality between these
two terms. We can write:

$\displaystyle\frac{r-1}{2}$
$\displaystyle>\left(\frac{\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)^{2}(r-1)^{2}}{8r}\right)^{\frac{1}{L}}\iff$
$\displaystyle r(r-1)^{L-2}$
$\displaystyle>2^{L-3}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)^{2}$

We first solve it for $L=4$ and any $r\geq 4$ (which is guaranteed by $K\geq
6$). We get the inequality $r(r-1)^{2}>2(r-1)(r-2)+4+4\sqrt{2(r-1)(r-2)}.$
This inequality is equivalent to $(r-1)(r^{2}-3r+4)>4+4\sqrt{2(r-1)(r-2)}$,
which holds for all $r\geq 4$.

Compared to the case $L=4$, for general $L$ the LHS gets multiplied by
$(r-1)^{L-4}$ and the RHS gets multiplied by $2^{L-4},$ which is smaller for
$r\geq 4.$ Hence, the inequality holds as well.

Analysis for $L=3$. Here, we need a tighter upper bound than
$\bar{\mathcal{L}}_{SRG}(q)$. Thus, we write

$\displaystyle\mathcal{L}_{SRG}(q)$
$\displaystyle\leq\frac{\lambda_{W_{3}}}{2}\frac{r}{\frac{8(r-3)^{2}\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)}{r^{2}(r-1)^{2}\lambda_{W_{2}}}q^{3}+\frac{r(r-1)}{2}\lambda_{W_{3}}}$
$\displaystyle+\frac{\lambda_{W_{3}}}{2}\frac{\frac{r(r-3)}{2}}{\frac{8\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)}{r^{L-1}(r-1)^{2}\lambda_{W_{2}}}q^{3}+\frac{r(r-1)}{2}\lambda_{W_{3}}}$
$\displaystyle+\frac{3}{2}\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)q.$

We equivalently re-write this by extending both of the ratios by
$\frac{r-2}{r-2}\frac{r-1}{r-1}$ and then moving $\frac{r-2}{r-1}$ to
denominator. Thus,

$\displaystyle\mathcal{L}_{SRG}(q)\leq\tilde{\mathcal{L}}_{SRG}(q)$
$\displaystyle:=\frac{\lambda_{W_{3}}}{2}\frac{\frac{r(r-1)}{r-2}}{\frac{8(r-3)^{2}\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)}{r^{2}(r-1)(r-2)\lambda_{W_{2}}}q^{3}+\frac{r(r-1)}{2}\lambda_{W_{3}}}$
$\displaystyle+\frac{\lambda_{W_{3}}}{2}\frac{\frac{r(r-3)(r-1)}{2(r-2)}}{\frac{8\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)}{r^{2}(r-1)(r-2)\lambda_{W_{2}}}q^{3}+\frac{r(r-1)}{2}\lambda_{W_{3}}}$
$\displaystyle+\frac{3}{2}\sqrt{\lambda_{W_{1}}\lambda_{H_{1}}}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)q.$

Now, we perform the same reparametrizations as for $L>4$, with the only
exception of treating $(r-1)(r-2)$ in the denominator of the denominator of
the current ratios as $(r-1)^{2}$ in the previous case. Then, we have

$\displaystyle\underset{q\geq 0}{\min}\hskip
2.84526pt\tilde{\mathcal{L}}_{SRG}(q)=\underset{q\geq 0}{\min}\hskip
2.84526pt$
$\displaystyle\frac{\lambda_{W_{3}}}{2}\frac{\frac{r(r-1)}{r-2}}{\frac{(r-3)^{2}}{\lambda_{H_{1}}\lambda_{W_{1}}\lambda_{W_{2}}}q^{3}+\frac{r(r-1)}{2}\lambda_{W_{3}}}$
$\displaystyle+\frac{\lambda_{W_{3}}}{2}\frac{\frac{r(r-3)(r-1)}{2(r-2)}}{\frac{1}{\lambda_{H_{1}}\lambda_{W_{1}}\lambda_{W_{2}}}q^{3}+\frac{r(r-1)}{2}\lambda_{W_{3}}}$
$\displaystyle+\frac{3}{2}r\left(\frac{\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)^{2}(r-1)(r-2)}{8r}\right)^{\frac{1}{3}}q.$

Assume that the following inequality holds:

$\frac{1}{\frac{(r-3)^{2}}{\lambda_{H_{1}}\lambda_{W_{1}}\lambda_{W_{2}}}q^{3}+\frac{r(r-1)}{2}\lambda_{W_{3}}}\leq\frac{1}{2}\frac{1}{\frac{1}{\lambda_{H_{1}}\lambda_{W_{1}}\lambda_{W_{2}}}q^{3}+\frac{r(r-1)}{2}\lambda_{W_{3}}}.$
(9)

Then,

$\displaystyle\underset{q\geq 0}{\min}\hskip
2.84526pt\tilde{\mathcal{L}}_{SRG}(q)\leq\underset{q\geq 0}{\min}\hskip
2.84526pt\bar{\mathcal{L}}_{SRG}(q):=\underset{q\geq 0}{\min}\hskip 2.84526pt$
$\displaystyle\frac{\lambda_{W_{3}}}{2}\frac{\frac{r(r-1)}{2}}{\frac{1}{\lambda_{H_{1}}\lambda_{W_{1}}\lambda_{W_{2}}}q^{3}+\frac{r(r-1)}{2}\lambda_{W_{3}}}$
$\displaystyle+\frac{3}{2}r\left(\frac{\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)^{2}(r-1)(r-2)}{8r}\right)^{\frac{1}{3}}q.$

The only difference between the expression considered here and the one
considered in the $L>3$ case is that here we have $(r-1)(r-2)$ instead of
$(r-1)^{2}$ within the expression. By comparing against $\mathcal{L}_{DNC}$
again, we get that $\bar{\mathcal{L}}_{SRG}<\mathcal{L}_{DNC}$ if and only if
$r(r-1)^{2}>\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)^{2}(r-2)$. This is
equivalent to $(r-1)(3r-4)>2(r-2)+2(r-2)\sqrt{2(r-1)(r-2)}$, which holds for
all $r\geq 4$.

It remains to show that (9) holds, and it suffices to do so for the minimizer
$q^{*}$ of $\mathcal{L}_{DNC}$, as $\min_{q\geq
0}\tilde{\mathcal{L}}_{SRG}(q)\leq\tilde{\mathcal{L}}_{SRG}(q^{*})\leq\bar{\mathcal{L}}_{SRG}(q^{*})<\mathcal{L}_{DNC}(q^{*})=\min_{q\geq
0}\mathcal{L}_{DNC}(q)$. Note that this is equivalent to

$\frac{r(r-1)}{2}\lambda_{W_{3}}<\frac{(r-3)^{2}-2}{\lambda_{W_{1}}\lambda_{W_{2}}\lambda_{H_{1}}}(q^{*})^{3}.$

Note that the minimum of the function in (7) (having the same
reparametrization as $\bar{\mathcal{L}}_{SRG}$) – if it is not at $q^{*}=0,$
in which case the statement of the theorem is trivial – must come after the
unique inflection point of the function. A direct computation yields that this
inflection point satisfies

$\frac{r(r-1)}{2}\lambda_{W_{3}}=\frac{2}{\lambda_{W_{1}}\lambda_{W_{2}}\lambda_{H_{1}}}q^{3}.$

Therefore, the minimum of (7) is attained at $q^{*}$ for which

$\frac{r(r-1)}{2}\lambda_{W_{3}}<\frac{2}{\lambda_{W_{2}}\lambda_{W_{1}}\lambda_{H_{1}}}(q^{*})^{3}.$

For $r\geq 5,$ this implies that such a $q^{*}$ satisfies (9), which concludes
the argument for $K={r\choose 2}.$

For a general $K$, the extension is rather simple. Note that the first type of
SRG solution in Definition 11 is constructed in a way so that the losses
attained by the SRG and DNC parts sum up. Therefore, we can split the analysis
for the SRG and DNC parts. The DNC part obviously attains equal loss to the
DNC solution. For the SRG part, the analysis done above applies, and the
argument is complete.

It remains to show the statement on the asymptotic relationship between
$\mathcal{L}_{SRG}$ and $\mathcal{L}_{DNC}$ for $K\xrightarrow[]{}\infty$ when
$L\geq 4$. Formally, we should consider sequences of the problems and label
everything with an extra index corresponding to the order within the sequence.
However, with an abuse of notation, we drop this indexing and switch to the
$\mathcal{O},\Theta$ notations whenever convenient.

As before, we start by considering $K$ of the form $r\choose 2$ for some $r$.
Let $\Lambda=\lambda_{H_{1}}\prod_{i=1}^{L}\lambda_{W_{i}}$ and
$\Psi(K)=\left(\frac{2^{L-3}\left(\sqrt{2}+\sqrt{(r-1)(r-2)}\right)^{2}}{r(r-1)^{L-2}}\right)^{\frac{1}{L}}$,
where $r$ corresponds to the value s.t. ${r\choose 2}=K$. We note that
$\Psi(K)=\Theta(K^{\frac{3-L}{2L}}).$ Since we are interested in the ratio
$\frac{\mathcal{L}_{SRG}}{\mathcal{L}_{DNC}},$ we do a few changes and
reparametrizations to the expressions in (7) and (8): we multiply both by 2,
divide all terms in the left summands by $\lambda_{W_{L}},$ rewrite
$\frac{r(r-1)}{2}$ as $K,$ plug in the defined quantities, divide all the
terms in the left summands by $K$ and finally replace
$\Lambda^{-\frac{1}{L}}K^{-\frac{1}{L}}q$ with $q$ to obtain the following
expression

$\frac{1}{q^{L}+1}+LK^{\frac{L+1}{L}}\Lambda^{\frac{1}{L}}q$ (10)

for the DNC loss, and the following expression

$\frac{1}{q^{L}+1}+LK^{\frac{L+1}{L}}\Lambda^{\frac{1}{L}}\Psi(K)q$ (11)

for the SRG loss. Using a similar trick as in the previous analysis for $L=3$,
we have that the minimum of the function in (10) is achieved when $q>1$.
Hence, we can lower bound (10) by

$\frac{1}{3}q^{-L}+LK^{\frac{L+1}{L}}\Lambda^{\frac{1}{L}}q.$

For this convex expression, we can find the optimal solution by setting to
zero the derivative, which gives that the optimal solution is
$(1+L)3^{-\frac{1}{L+1}}K\Lambda^{\frac{1}{L+1}}.$ Similarly, we can upper
bound (11) by

$q^{-L}+LK^{\frac{L+1}{L}}\Lambda^{\frac{1}{L}}\Psi(K)q$

and after finding the optimal solution we get that it equals
$(1+L)K\Lambda^{\frac{1}{L+1}}\Psi(K)^{\frac{L}{L+1}}.$ This allows us to
conclude that

$\frac{\mathcal{L}_{SRG}}{\mathcal{L}_{DNC}}=\mathcal{O}(K^{\frac{3-L}{2(L+1)}}).$

To get the same formula when the number of classes is not of the form
${r\choose 2},$ we only need simple adjustments. For this part, we will employ
the upper-index notation to denote the number of classes $K$ to which the
solution corresponds. First, note that the optimal value of (10) is continuous
in the coefficient in front of the linear term $q.$ Therefore, if
$\mathcal{L}_{DNC}^{K}<0.499$, then, choosing the smallest $r$ for which
$K\leq{r\choose 2}:=\bar{K}$, we see that $\mathcal{L}^{\bar{K}}_{DNC}<0.5$
for the same set of regularization parameters, as
$\frac{\bar{K}}{K}\xrightarrow[]{K\xrightarrow[]{}\infty}1.$ Since the
argument above does not need $\mathcal{L}_{DNC}<0.499$ but only
$\mathcal{L}_{DNC}<0.5$, we can now use that $\mathcal{L}^{\bar{K}}_{SRG}$
with the same regularization parameters is still
$\mathcal{O}(K^{\frac{3-L}{2(L+1)}}).$ Finally, choosing the second
construction in Definition 11, we construct the SRG solution for $K$ classes
from the SRG solution for $\bar{K}$ classes with the same regularization
parameters (thus also the same regularization as for the DNC solution with $K$
classes). To conclude, it just suffices to see that
$\mathcal{L}^{\bar{K}}_{SRG}\geq\mathcal{L}^{K}_{SRG}$ because we removed
columns from $H_{1},$ decreasing its norm and the fit loss is at most as big
because the columns with the worst fit loss were removed and the fit loss is
an average over the columns. This concludes the proof also for general $K.$ ∎

We conclude the section by stating and proving a few auxiliary lemmas that
were used in the proof of Theorem 5.

######  Lemma 12.

Consider the following optimization problem:

$\displaystyle\underset{w}{\min}$ $\displaystyle\left\lVert w\right\rVert^{2}$
(12) s.t. $\displaystyle z^{T}=w^{T}A_{l}T_{r}.$ (13)

Then, the value of the optimal solution is

$\frac{(r-1)^{2}}{\alpha_{l}(r-2)^{2}}z^{T}T_{r}^{T}\left(I_{r}-\frac{3r-4}{4(r-1)^{2}}\mathbf{1}_{r}\mathbf{1}_{r}^{T}\right)T_{r}z.$

###### Proof.

Multiplying the constraint with $T_{r}^{T}(T_{r}T_{r}^{T})^{-1}$ from the
right we get $z^{T}T_{r}^{T}(T_{r}T_{r}^{T})^{-1}=w^{T}A_{l}.$ Now, we can use
that the minimum $l_{2}$ norm solution of such a system can be computed by
multiplying with the right pseudoinverse of $A_{l}.$ Thus, we get
$w=A_{l}(A_{l}^{T}A_{l})^{-1}(T_{r}T_{r}^{T})^{-1}T_{r}z=1/\alpha_{l}A_{l}(T_{r}T_{r}^{T})^{-1}T_{r}z.$
Then the squared norm of this is simply:

$w^{T}w=\frac{1}{\alpha_{l}^{2}}z^{T}T_{r}^{T}(T_{r}T_{r}^{T})^{-1}A_{l}^{T}A_{l}(T_{r}T_{r}^{T})^{-1}T_{r}z=\frac{1}{\alpha_{l}}z^{T}T_{r}^{T}(T_{r}T_{r}^{T})^{-2}T_{r}z.$

Now, we know that

$T_{r}T_{r}^{T}=\frac{r-2}{r-1}I_{r}+\frac{1}{r-1}\mathbf{1}\mathbf{1}^{T}=\frac{r-2}{r-1}\left(I+\frac{1}{r-2}\mathbf{1}\mathbf{1}^{T}\right).$

This can be seen by looking at the structure of $\mathcal{K}_{n}$ where two
vertices have exactly one edge between them. Now we can compute the the
inverse of this matrix using the Sherman-Morrison formula

$\left(I+\frac{1}{r-2}\mathbf{1}\mathbf{1}^{T}\right)^{-1}=I-\frac{1}{2(r-1)}\mathbf{1}\mathbf{1}^{T}$

and the square is:

$\left(I+\frac{1}{r-2}\mathbf{1}\mathbf{1}^{T}\right)^{-2}=I-\frac{3r-4}{4(r-1)^{2}}\mathbf{1}\mathbf{1}^{T}.$

Putting this all together, the proof is complete. ∎

######  Lemma 13.

Let $2\leq l\leq L-2.$ Consider $\tilde{M}_{l+1},M_{l}$ as in Definition 9 of
the SRG solution. Then, the following optimization problem:

$\displaystyle\underset{W}{\min}$ $\displaystyle\left\lVert
W\right\rVert_{F}^{2}$ (14) s.t. $\displaystyle\tilde{M}_{l+1}=WM_{l}$ (15)

achieves optimal value of $\frac{r\alpha_{l+1}}{\alpha_{l}}.$

###### Proof.

This is a direct consequence of Lemma 12. Denote $\gamma z_{0}$ a row from
$\tilde{M}_{l+1}$ which corresponds to the first row of $T_{r}$ and such that
$\left\lVert z_{0}\right\rVert=1.$ Then, $T_{r}\gamma
z_{0}=\gamma(1,1/(r-1),\dots,1/(r-1))^{T}.$ Directly evaluating the expression
in Lemma 12 will yield $\gamma^{2}\alpha_{l}^{-1}$ for a single row and thus
for all rows we get the value from the lemma statement. ∎

######  Lemma 14.

Consider $\tilde{M}_{L},M_{L-1}$ as in Definition 9 of the SRG solution. Then,
the following optimization problem:

$\displaystyle\underset{W}{\min}$ $\displaystyle\left\lVert
W\right\rVert_{F}^{2}$ (16) s.t. $\displaystyle\tilde{M}_{L}=WM_{L-1}$ (17)

achieves optimal value of

$\frac{\alpha_{L}}{\alpha_{L-1}}\frac{r^{2}(r-1)^{2}}{4((r-2)(r-3)+2)}.$

###### Proof.

We first need to characterize the rows of $\tilde{M}_{L}$. Note that
$\tilde{M}_{L}$ comes from the multiplication of $T_{r}$ and $A_{L}^{(1)}$,
see Definition 9. This operation can be seen as weighting vertices of
$\mathcal{K}_{r}$ (rows of $T_{r}$) and then looking at what the sum of the
weights of adjacent vertices of each edge (column of $T_{r}$) is. We can
easily see that the resulting vector has exactly one “$-1$” entry (for the
edge corresponding to the two vertices given negative weight) and exactly
${r-2\choose 2}$ entries with “$+1$”. Therefore, it must be scaled with the
inverse of $s:=\sqrt{\frac{(r-2)(r-3)}{2}+1}$ to be unit norm. Now, let
$z_{1}$ be one of these vectors with the negative edge between first two
vertices. Then,

$T_{r}z_{1}=\left(-\frac{1}{s\sqrt{r-1}},-\frac{1}{s\sqrt{r-1}},\frac{r-3}{s\sqrt{r-1}},\frac{r-3}{s\sqrt{r-1}},\dots\right)^{T},$

which can be easily derived if we imagine doing edge-wise dot-product between
two vertex weightings, one with two “$-1$s” for $z_{1}$ and the other type
with one “$+1$” representing the rows of $T_{r}.$ For the other vectors in
$\tilde{H}_{L}$, the resulting vectors would be similar, except they would
have the negative entries for different pairs of vertices of
$\mathcal{K}_{r}.$ Note that

$\displaystyle z_{1}^{T}T_{r}^{T}T_{r}z$
$\displaystyle=\frac{2}{s^{2}(r-1)}+\frac{(r-3)^{2}(r-2)}{s^{2}(r-1)},$
$\displaystyle z_{1}^{T}T_{r}^{T}\mathbf{1}_{r}\mathbf{1}_{r}^{T}T_{r}z$
$\displaystyle=\frac{\left((r-3)(r-2)-2\right)^{2}}{s^{2}(r-1)}.$

Therefore, if we are optimizing for $\gamma z_{1}$, then an application of
Lemma 12 gives

$w^{T}w=\gamma^{2}\alpha_{L-1}^{-1}\frac{(r-1)^{2}}{(r-2)^{2}}\left(\frac{2}{s^{2}(r-1)}+\frac{(r-3)^{2}(r-2)}{s^{2}(r-1)}-\frac{3r-4}{4(r-1)^{2}}\frac{((r-3)(r-2)-2)^{2}}{s^{2}(r-1)}\right),$

where $w$ denotes a row of $W$. Simplifying this expression, we get

$w^{T}w=\gamma^{2}\alpha_{L-1}^{-1}\frac{r(r-1)}{2((r-2)(r-3)+2)}.$

To conclude, it suffices to sum up $\frac{r(r-1)}{2}$ such rows having total
$l_{2}$ norm squared $\alpha_{L}$ (and, hence, $\gamma^{2}=\alpha_{L}$), which
gives

$\left\lVert
W\right\rVert_{F}^{2}=\frac{\alpha_{L}}{\alpha_{L-1}}\frac{r^{2}(r-1)^{2}}{4((r-2)(r-3)+2)},$

and concludes the proof. ∎

######  Lemma 15.

For $2\leq l\leq L-1$, consider $M_{l},\tilde{M}_{l}$ as in Definition 9 of
the SRG solution. Then, $M_{l}=\tilde{M}_{l}$ and the eigenvalues of
$M_{l}^{T}M_{l}$ are:

$\displaystyle\mu_{1}$ $\displaystyle=2\alpha_{l}\hskip 8.53581pt\text{with
multiplicity }\hskip 2.84526pt1,$ $\displaystyle\mu_{2}$
$\displaystyle=\frac{r-2}{r-1}\alpha_{l}\hskip 8.53581pt\text{with
multiplicity }\hskip 2.84526ptr-1,$ $\displaystyle\mu_{3}$
$\displaystyle=0\hskip 8.53581pt\text{with multiplicity }\hskip
2.84526pt\frac{r(r-3)}{2}.$

###### Proof.

From the definition, it readily follows that $M_{l}=\tilde{M}_{l}$, so let us
compute $M_{l}^{T}M_{l}.$ Looking at any row of $M_{l},$ we see that it has
non-negative equal entries of value $\sqrt{\alpha_{ij}}/\sqrt{r-1},$ where
$\sum_{j}\alpha_{ij}=\alpha_{l}$ on all the $r-1$ edges of $\mathcal{K}_{r}$
that contain the vertex corresponding to that row. Therefore, by definition of
$\alpha_{l}$, the sum of squares of all entries corresponding to one row type
within any column is $\alpha_{l}/(r-1)$. Each edge (and, thus, column)
contains exactly two vertices, thus the diagonal elements of $M_{l}^{T}M_{l},$
which are the $l_{2}$ norms squared of the columns of $M_{l}$, are simply
equal to $\frac{2\alpha_{l}}{r-1}.$ There are two possible off-diagonal
values. One is for the pairs of columns that correspond to edges that share a
vertex and one is for those pairs that do not share a vertex. The pairs of
columns whose edges do not share a vertex do not have any entries which would
both be jointly positive, because either a vertex does not belong to one edge
or to the other. Therefore, the value of off-diagonal entries corresponding to
such pairs is simply 0. On the other hand, there is exactly one vertex that
has non-zero values for both edges corresponding to columns whose edges do
share a vertex – it is the shared vertex. Therefore the value of off-diagonal
entries of this type is $\frac{\alpha_{L}}{r-1}.$ Crucially, the structure of
the off-diagonal entries is fully determined by the graph $\mathcal{T}_{r}$,
because two edges in $\mathcal{K}_{r}$ share a vertex if and only if they are
connected in the graph $\mathcal{T}_{r}$. Therefore, $M_{l}^{T}M_{l}$ can be
written as a weighted sum of $I_{K}$ and the adjacency matrix $G_{r}$ of
$\mathcal{T}_{r}$, where the weight of $I_{K}$ simply corresponds to the size
of the diagonal term and the weight of $G_{r}$ to the positive off-diagonal
term. In conclusion, we get

$\displaystyle
M_{l}^{T}M_{l}=\frac{2\alpha_{l}}{r-1}I_{K}+\frac{\alpha_{l}}{r-1}G_{r}.$

As $\mathcal{T}_{r}$ is a strongly regular graph with parameters
$(r(r-1)/2,2(r-2),r-2,4)$, $G_{r}$ has a single eigenvalue equal to $2(r-2)$,
$r-1$ eigenvalues equal to $r-4$ and $r(r-3)/2$ eigenvalues equal to $-2$,
which concludes the proof. ∎

######  Lemma 16.

Consider $M_{L}$ as in Definition 9 of the SRG solution. Then, the eigenvalues
of $M_{L}^{T}M_{L}$ are:

$\displaystyle\mu_{1}$
$\displaystyle=\frac{(r-2)(5r-19)\alpha_{L}}{(r-2)(r-3)+2}\hskip
8.53581pt\text{with multiplicity}\hskip 2.84526pt1,$ $\displaystyle\mu_{2}$
$\displaystyle=\frac{2(r-3)^{2}\alpha_{L}}{(r-2)(r-3)+2}\hskip
8.53581pt\text{with multiplicity}\hskip 2.84526ptr-1,$ $\displaystyle\mu_{3}$
$\displaystyle=\frac{2\alpha_{L}}{(r-2)(r-3)+2}\hskip 8.53581pt\text{with
multiplicity}\hskip 2.84526pt\frac{r(r-3)}{2}.$

###### Proof.

Let us compute $M_{L}^{T}M_{L}.$ Looking at any row of $M_{L},$ we see that it
has non-negative equal entries of value $\sqrt{\alpha_{ij}}/s,$ where
$s=\sqrt{\frac{(r-2)(r-3)}{2}+1}$ and $\sum_{j}\alpha_{ij}=\alpha_{L}$ on all
edges in a subgraph of $\mathcal{K}_{r}$ of size $r-2.$ Therefore, by
definition of $\alpha_{L}$, the sum of squares of all entries corresponding to
one row type within any column is $\alpha_{L}/s^{2}$. However, not all row
types have non-zero value on any particular column. Namely, a row type will
only have non-zero value on a column, if the row-type corresponds to such a
subgraph of $\mathcal{K}_{r}$, which is disjoint with the edge corresponding
to the column. This is because all edges outside the complete subgraph of
$r-2$ vertices corresponding to the row type are assigned 0 in $M_{L}.$
Therefore, the number of row types that assign non-zero value in a particular
column is equal to the number of $r-2$ vertex sets. This corresponds to the
number of edges in $\mathcal{K}_{r}$, which is equal to ${r-2\choose
2}=s^{2}-1.$ Thus, the diagonal elements of $M_{L}^{T}M_{L},$ which are the
$l_{2}$ norms squared of the columns of $M_{L}$, are simply equal to
$\frac{(s^{2}-1)\alpha_{L}}{s^{2}}.$ There are two possible off-diagonal
values. One is for the pairs of columns that correspond to edges that share a
vertex, and one is for those pairs that don’t share a vertex. Let us compute
the number of row types assigning positive value to both of these columns
jointly. Using the same interpretation, the columns correspond to edges and
only row types that correspond to $r-2$ vertex subsets disjoint with them
assign positive value to the column of that edge. If we want this to be
satisfied for both rows jointly, we need to take the intersection of those
$r-2$ vertex subsets, which in this case will result in an $r-3$ vertex
subset. Thus, exactly $r-3\choose 2$ row types will jointly assign a positive
value. Therefore, we have value $\frac{(r-3)(r-4)\alpha_{L}}{2s^{2}}$ on these
off-diagonal entries. For the pairs of columns that correspond to edges with
disjoint vertices, the same intersection will now yield a set of vertices of
size only $r-4.$ Therefore, the value of this off-diagonal entry is
$\frac{(r-4)(r-5)\alpha_{L}}{2s^{2}}.$ Crucially, the structure of the off-
diagonal entries is fully determined by the graph $\mathcal{T}_{r}$, because
two edges in $\mathcal{K}_{r}$ share a vertex if and only if they are
connected in the graph $\mathcal{T}_{r}$. Therefore, $M_{L}^{T}M_{L}$ can be
written as a weighted sum of $\mathbf{1}_{K}\mathbf{1}_{K}^{T},I_{K}$ and the
adjacency matrix $G_{r}$ of $\mathcal{T}_{r}$. The weights can be determined
as follows: we first subtract a multiple of $\mathbf{1}_{K}\mathbf{1}_{K}^{T}$
to make the smaller off-diagonal entry of $M_{L}^{T}M_{L}$ zero, then we
subtract what is left of the diagonal and we take the rest to be a multiple of
$G_{r}.$ In conclusion, we get

$\displaystyle M_{L}^{T}M_{L}=$
$\displaystyle\frac{(r-4)(r-5)\alpha_{L}}{2s^{2}}\mathbf{1}_{K}\mathbf{1}_{K}^{T}$
$\displaystyle+$
$\displaystyle\left(\frac{(s^{2}-1)\alpha_{L}}{s^{2}}-\frac{(r-4)(r-5)\alpha_{L}}{2s^{2}}\right)I_{K}$
$\displaystyle+$
$\displaystyle\left(\frac{(r-3)(r-4)\alpha_{L}}{2s^{2}}-\frac{(r-4)(r-5)\alpha_{L}}{2s^{2}}\right)G_{r}.$

As $\mathcal{T}_{r}$ is a strongly regular graph with parameters
$(r(r-1)/2,2(r-2),r-2,4)$, $G_{r}$ has a single eigenvalue equal to $2(r-2)$,
$r-1$ eigenvalues equal to $r-4$ and $r(r-3)/2$ eigenvalues equal to $-2$. The
summation with $I_{K}$ only shifts all the eigenvalues. The term
$\mathbf{1}_{K}\mathbf{1}_{K}^{T}$ has only one non-zero eigenvalue, and the
eigenvector is identical to that of the eigenvector corresponding to the
dominant eigenvalue of $G_{r}$. This concludes the proof. ∎

######  Lemma 17.

Assuming DNC1, let $M_{L}$ be the mean matrix of the last layer. Let
$M_{L}=U\Sigma V^{T}$ be the full SVD of $M_{L}$ and let $\sigma_{i},\hskip
2.84526pti\in[K]$, be the singular values of $M_{L}.$ Then, the following
optimization problem:

$\displaystyle\underset{W_{L}}{\min}\frac{1}{2K}\left\lVert
W_{L}M_{L}-I_{K}\right\rVert_{F}^{2}+\frac{\lambda_{W_{L}}}{2}\left\lVert
W_{L}\right\rVert_{F}^{2}$

attains the minimum of

$\frac{\lambda_{W_{L}}}{2}\sum_{i=1}^{K}\frac{1}{\sigma_{i}^{2}+K\lambda_{W_{L}}}.$

###### Proof.

The proof consists in a direct computation. Let $W_{L}^{*}$ denote the
minimizer. Computing the gradient and setting it to $0$ gives that

$\displaystyle
W_{L}^{*}=M_{L}^{T}(M_{L}M_{L}^{T}+\lambda_{W_{L}}KI_{d_{L}})^{-1}=V\Sigma^{T}(\Sigma\Sigma^{T}+\lambda_{W_{L}}KI_{d_{L}})^{-1}U^{T},$

which readily implies that

$\displaystyle\left\lVert W_{L}^{*}\right\rVert_{F}^{2}$
$\displaystyle=\sum_{i=1}^{K}\frac{\sigma_{i}^{2}}{(\sigma_{i}^{2}+\lambda_{W_{L}}K)^{2}},$
$\displaystyle\left\lVert W_{L}M_{L}-I_{K}\right\rVert_{F}^{2}$
$\displaystyle=\left\lVert
V\Sigma^{T}(\Sigma\Sigma^{T}+\lambda_{W_{L}}KI_{d_{L}})^{-1}\Sigma
V^{T}-VV^{T}\right\rVert_{F}^{2}$
$\displaystyle=\sum_{i=1}^{K}\left(\frac{\sigma_{i}^{2}}{\sigma_{i}^{2}+\lambda_{W_{L}}K}-1\right)^{2}=\sum_{i=1}^{K}\frac{K^{2}\lambda_{W_{L}}^{2}}{(\sigma_{i}^{2}+\lambda_{W_{L}}K)^{2}},$

thus concluding the argument. ∎

######  Lemma 18.

The optimization problem

$\min_{A,B;C=AB}\quad\frac{\lambda_{A}}{2}\left\lVert
A\right\rVert_{F}^{2}+\frac{\lambda_{B}}{2}\left\lVert B\right\rVert_{F}^{2}$
(18)

attains the minimum of $\sqrt{\lambda_{A}\lambda_{B}}\left\lVert
C\right\rVert_{*}$, and the minimizers are of the form
$A^{*}=\gamma_{A}U\Sigma^{1/2}R^{T},B^{*}=\gamma_{B}R\Sigma^{1/2}V^{T}$. Here,
the constants $\gamma_{A},\gamma_{B}$ only depend on
$\lambda_{A},\lambda_{B}$; $U\Sigma V^{T}$ is the SVD of $C$; and $R$ is an
orthogonal matrix.

###### Proof.

See Lemma C.1 of [52]. ∎

###  A.2 No within-class variability is still optimal

See 6

###### Proof.

Step 1: Reduction to $n=1.$ In the first step, assume by contradiction that
there exists an optimal solution of (1) with regularization parameters
$(\lambda_{H_{1}},\lambda_{W_{1}},\dots,\lambda_{W_{L}})$ denoted as
$(H_{1}^{*},W_{1}^{*},\dots,W_{L}^{*})$ which does not exhibit deep neural
collapse at layer $L$. This means that there exist indices $c,i,j$ s.t.
$h_{ci}^{L}\neq h_{cj}^{L}.$ Let us construct two solutions of the $n=1$
$L$-DUFM. They will share the weight matrices which will equal
$(W_{1}^{*},\dots,W_{L}^{*})$ – the weight matrices of the original solution.
To construct the features, for every class except the $c$-th, pick any sample
and share it between both solutions. For the class $c,$ take the samples
$h_{ci}^{L},h_{cj}^{L}$ and put one in one solution and the other one in the
other solution. Denote $H_{1}^{(1)},H_{1}^{(2)}$ the two $n=1$ sample
matrices. It is not hard to see that both
$(H_{1}^{(1)},W_{1}^{*},\dots,W_{L}^{*})$ and
$(H_{1}^{(2)},W_{1}^{*},\dots,W_{L}^{*})$ are optimal solutions of (1) with
regularization parameters
$(n\lambda_{H_{1}},\lambda_{W_{1}},\dots,\lambda_{W_{L}}).$ To prove it,
assume by contradiction that, without loss of generality,
$(H_{1}^{(2)},W_{1}^{*},\dots,W_{L}^{*})$ is not an optimal solution of the
corresponding problem. Then, there exists an alternative
$(H_{1}^{(0)},\hat{W}_{1}^{*},\dots,\hat{W}_{L}^{*})$ that achieves smaller
loss for this problem. Let us duplicate all the samples of $\hat{H}_{1}^{(0)}$
for $n$ times, thus constructing
$\hat{H}_{1}^{*}=H_{1}^{(0)}\otimes\mathbf{1}_{n}^{T}.$ The solution
$(\hat{H}_{1}^{*},\hat{W}_{1}^{*},\dots,\hat{W}_{L}^{*})$ has the same loss
under the $L$-DUFM problem with regularization parameters
$(\lambda_{H_{1}},\lambda_{W_{1}},\dots,\lambda_{W_{L}})$ as the solution
$(H_{1}^{(0)},\hat{W}_{1}^{*},\dots,\hat{W}_{L}^{*})$ for the $L$-DUFM with
$n=1$ and parameters
$(n\lambda_{H_{1}},\lambda_{W_{1}},\dots,\lambda_{W_{L}}).$ This is easy to
see from the separability of both $\left\lVert H_{1}\right\rVert_{F}^{2}$ and
the fit part of the loss in (1) w.r.t. the columns of $H_{1}.$ For the same
reasons, the loss functions for $(H_{1}^{*},W_{1}^{*},\dots,W_{L}^{*})$ in the
original problem equals the loss function of the solutions
$(H_{1}^{(1)},W_{1}^{*},\dots,W_{L}^{*})$ or
$(H_{1}^{(2)},W_{1}^{*},\dots,W_{L}^{*})$ in the reduced problem. In fact, if
this was not the case, there would need to be an inequality between the losses
exhibited by two different columns of $H_{1}$ belonging to the same class,
from which we could arrive at a contradiction by taking the better column and
multiplying it to all columns within that class, thereby obtaining a better
solution. This means that the loss of
$(\hat{H}_{1}^{*},\hat{W}_{1}^{*},\dots,\hat{W}_{L}^{*})$ in the original
problem is smaller than the loss of $(H_{1}^{*},W_{1}^{*},\dots,W_{L}^{*}),$
which is a contradiction.

Step 2: Excluding an aligned case. By assumption we know that not only
$H_{1}^{(1)}$ and $H_{1}^{(2)}$ differ in the $c$-th column (from now on we
assume without loss of generality that it is the first column) but also
$H_{L}^{(1)}$ and $H_{L}^{(2)}$ do. Denote for simplicity the first
(differing) columns of $H_{L}^{(1)}$ and $H_{L}^{(2)}$ as $x,y$ respectively.
We now show that it is not possible that $y=\alpha x.$ First, $\alpha$ has to
be non-negative since $x,y$ are entry-wise non-negative given that they come
after the application of $\sigma.$ Assume w.l.o.g. $\alpha>1$ (otherwise, we
can just exchange the roles of $x$ and $y$). Consider a reduced problem where
we only optimize for the size of the first column of either $H_{L}^{(1)}$ or
$H_{L}^{(2)},$ focusing on that part of the problem (1) which is relevant for
this column, being:

$\underset{t\geq 0}{\min}\hskip 2.84526pt\frac{1}{2N}\left\lVert
tW_{L}h_{11}^{L(i)}-e_{1}\right\rVert_{2}^{2}+\frac{n\lambda_{H_{1}}}{2}\left\lVert
th_{11}^{1(i)}\right\rVert_{2}^{2}.$

This problem is strongly convex, quadratic and simple enough to give the
following: if $\alpha>1,$ then $\left\lVert
h_{11}^{1(1)}\right\rVert_{2}^{2}>\left\lVert
h_{11}^{1(2)}\right\rVert_{2}^{2}$ and simultaneously $\left\lVert
W_{L}x-e_{1}\right\rVert_{2}^{2}>\left\lVert
W_{L}y-e_{1}\right\rVert_{2}^{2}.$ This means that $H_{1}^{(2)}$ is a strictly
better solution than $H_{1}^{(1)}$ – a contradiction.

Step 3: Contradiction by zero gradient condition. By optimality of both
solutions we get

$\left.\frac{\partial\mathcal{L}}{\partial
W_{L}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{(1)},W_{1}^{*},\dots,W_{L}^{*})}=0=\left.\frac{\partial\mathcal{L}}{\partial
W_{L}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{(2)},W_{1}^{*},\dots,W_{L}^{*})}.$

An application of the chain rule gives

$\frac{\partial\mathcal{L}}{\partial
W_{L}}=\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{L+1}}\frac{\partial\tilde{H}_{L+1}}{\partial
W_{L}}+\lambda_{W_{L}}W_{L}=\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{L+1}}H_{L}^{T}+\lambda_{W_{L}}W_{L},$

where $\tilde{H}_{L+1}$ is the output of our model. Plugging this back to the
previous equation and using that $W_{L}^{*}$ is the same in both expressions,
we get

$\left.\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{L+1}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{(1)},W_{1}^{*},\dots,W_{L}^{*})}(H_{L}^{(1)})^{T}=\left.\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{L+1}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{(2)},W_{1}^{*},\dots,W_{L}^{*})}(H_{L}^{(2)})^{T}.$

Let us denote

$A=\left.\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{L+1}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{(1)},W_{1}^{*},\dots,W_{L}^{*})},\,\,\,B=\left.\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{L+1}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{(2)},W_{1}^{*},\dots,W_{L}^{*})}.$

Due to the separability of $\mathcal{L}_{F}$ with respect to the columns of
$H_{1}$ (and, thus, also of $H_{l},\tilde{H}_{l}$ for all $l\leq L+1$), we get
that the matrices $A,B$ can only differ in their first columns and are
identical otherwise. We denote these columns $a,b$ for $A,B,$ respectively.
This implies that $ax^{T}=by^{T}.$

Now we exclude a few cases. First, neither $a$ nor $b$ can be zero, because by
the exact formula that exists for them, this would mean that exact fit was
achieved for either of the columns. This is impossible with non-zero weight-
decay, because decreasing the norm of the column of $H_{1}^{(1)}$ or
$H_{1}^{(2)}$ that achieves the exact fit by a sufficiently small value would
necessarily lead to an improvement on the objective value. Moreover, if
$x=y=0$, then this is a contradiction with the assumption that $x\neq y.$
Finally, the case $x\neq y=0$ or $0=x\neq y$ is excluded already in the step
2.

Thus we get $x,y,a,b$ are all non-zero. Looking at any fixed row (column) of
$ax^{T}$ and $by^{T}$ we see that necessarily $x,y$ ($a,b$) are aligned.
However, this case is already solved in step 2 and leads to $x=y,$ which is
the contradiction. This concludes the proof. ∎

For proof enthusiasts, we include an alternative proof of the same theorem
which uses an explicit formula for the conditionally optimal $W_{L}$ instead
of the necessary condition on the zero gradient:

###### Proof.

The first two steps are identical to the previous proof.

Step 3: Reducing the non-aligned case to an algebraic statement. We are left
with the assumption that $a,b$ (taking the notation from the step 2) are not
aligned. The strategy of this step is simple – we will show that in at least
one of the two solutions $(H_{1}^{(1)},W_{1}^{*},\dots,W_{L}^{*})$ and
$(H_{1}^{(2)},W_{1}^{*},\dots,W_{L}^{*}),$ the last weight matrix $W_{L}^{*}$
is not, in fact, conditionally optimal conditioned on the rest of the
solution. To this end, let us realize that if we condition on the rest of the
solution, then the optimization of $W_{L}$ only depends on
$H_{L}^{(i)},i=1,2.$ Moreover, there exists an explicit formula for this
conditionally optimal $W_{L}$ since the resulting problem is just a ridge
regression. The solution is:

$(W_{L}^{(i)})^{T}=((H_{L}^{(i)})(H_{L}^{(i)})^{T}+\mu
I_{d_{L}})^{-1}H_{L}^{(i)},\hskip 5.69054pti=1,2$

for $\mu=K\lambda_{L}.$ If we show that necessarily $W_{L}^{(1)}\neq
W_{L}^{(2)},$ then the $W_{L}^{*}$ can only equal one of them thus not being
the conditionally optimal for the other solution. This can be seen as an
abstract algebraic questoin: given two matrices $H_{L}^{(1)};H_{L}^{(2)}$ that
only differ in their first columns that are not aligned, are the
$(W_{L}^{(i)})^{T}=((H_{L}^{(i)})(H_{L}^{(i)})^{T}+\mu
I_{d_{L}})^{-1}H_{L}^{(i)}$ for $i=1,2$ necessarily different?

Step 4: Solving the algebraic statement. We will prove that indeed they have
to be different. Write the two feature matrices in their SVDs as follows:
$H_{L}^{(1)}=U_{1}\Sigma_{1}V_{1}^{T}$ and
$H_{L}^{(2)}=U_{2}\Sigma_{2}V_{2}^{T}.$ Assume for contradiction that the
corresponding solutions are equal. Then, without loss of generality we can
assume the feature matrices are equal in rank, denoted $r$, and we can afford
writing the compact SVD. After simple algebraic manipulations, we can rewrite
the solutions in terms of the SVDs as:

$(W_{L}^{(i)})^{T}=U_{i}f(\Sigma_{i})V_{i}^{T},$

where $f(\cdot)$ is a function $\frac{x}{x^{2}+\mu}$ applied entry-wise. If
the corresponding solutions equal, then we know the following:

$U_{1}f(\Sigma_{1})V_{1}^{T}=U_{2}f(\Sigma_{2})V_{2}^{T}.$

Since the SVD is unique up to permutations of the singular values and the
corresponding left and right singular vectors and up to shared orthogonal
transformations of the left and right singular spaces corresponding to a
single singular value, we know that there exists such an
$R\in\mathbb{R}^{r\times r}$ orthogonal that $U_{1}R=U_{2}$ and
$R^{T}V_{1}^{T}=V_{2}^{T}.$ Furthermore, $f(\Sigma_{1})$ and $f(\Sigma_{2})$
have the same singular values with the same multiplicities. We can now write:

$H_{L}^{(2)}-H_{L}^{(1)}=U_{2}\Sigma_{2}V_{2}^{T}-U_{1}\Sigma_{1}V_{1}^{T}=U_{1}R\Sigma_{2}R^{T}V_{1}^{T}-U_{1}\Sigma_{1}V_{1}^{T}=U_{1}(R\Sigma_{2}R^{T}-\Sigma_{1})V_{1}^{T}.$

We know that $H_{L}^{(2)}-H_{L}^{(1)}$ is a rank 1 matrix with only the first
column non-zero. Therefore, $R\Sigma_{2}R^{T}-\Sigma_{1}$ must be rank 1.
Since it is symmetric, we can write $R\Sigma_{2}R^{T}-\Sigma_{1}=cuu^{T}$ for
some $c\in\mathbb{R}$ and $u\in\mathbb{R}^{r}.$ Without loss of generality we
can assume $c>0.$ Furthermore, since $U_{1}$ is orthogonal and the matrix
itself only has the first column non-zero, we know that $u$ is in null-space
of $(V_{1})_{2:,:}.$ We will now work with the following two equations:

$\displaystyle Rf(\Sigma_{2})R^{T}$ $\displaystyle=f(\Sigma_{1})$ (19)
$\displaystyle R\Sigma_{2}R^{T}$ $\displaystyle=\Sigma_{1}+cuu^{T}$ (20)

We see that $R$ is a matrix of eigenvectors in both equations. In the
following, we will be investigating the possible structure of eigenvalues and
eigenvectors of $\Sigma_{1}+cuu^{T}.$ Denote $\sigma_{i}^{(j)},\hskip
2.84526pti\in[r],j=1,2$ the non-decreasing ordering of the diagonal entries of
$\Sigma_{j}.$ The $\sigma_{i}^{(2)}$ happen to be eigenvalues of
$\Sigma_{1}+cuu^{T}$ either. According to standard interlacing results [6], we
know that
$\sigma_{1}^{(1)}\leq\sigma_{1}^{(2)}\leq\sigma_{2}^{(1)}\leq\sigma_{2}^{(2)}\leq\dots\leq\sigma_{r}^{(1)}\leq\sigma_{r}^{(2)}$
and the total increase in the eigenvalues is exactly equal $c.$

Let us consider any eigenvector of $\Sigma_{1}+cuu^{T},$ i.e. we have
$(\Sigma_{1}+cuu^{T})x=\gamma x.$ After small manipulations we get:
$cu^{T}xu=(\gamma I-\Sigma_{1})x.$ We have a few observations:

  * •

The function $f$ is unimodal with 0 and $\sqrt{c}$ being the extremes.
Moreover except $0$ and $\sqrt{c},$ there is an exact pairing of inputs
smaller than $\sqrt{c}$ and bigger than $\sqrt{c}.$ The function $f$ is
injective everywhere except within the pairs. The pairs share the function
value.

  * •

The $x,$ being eigenvector of $f(\Sigma_{1}),$ must only have non-zero values
at at most two distinct eigenvalues of $\Sigma_{1}$ (based on the previous
item).

  * •

If $u^{T}x=0$ then $x$ is eigenvector of $\Sigma_{1}$ itself. If $u^{T}x\neq
0$ then for each non-zero entry in $u,$ the corresponding entry in $x$ must
also be non-zero.

To find out what the eigenvectors of $\Sigma_{1}+cuu^{T}$ are, we further
observe the following: If $u\equiv 0$ on all entries corresponding to some
eigenvalue of $\Sigma_{1},$ then $\Sigma_{1}$ and $\Sigma_{1}+cuu^{T}$ share
the corresponding eigenspace including the multiplicity of the corresponding
eigenvalue. This is easy to see because we can just plug all the eigenvectors
of $\Sigma_{1}$ for that eigenvalue into the equation
$(\Sigma_{1}+cuu^{T})x=\gamma x$ and conclude that they are eigenvectors of
$\Sigma_{1}+cuu^{T}$ with the same eigenvalue. Furthermore, the dimension of
the eigenspace corresponding to this eigenvalue in $\Sigma_{1}+cuu^{T}$ cannot
be higher, because the “new” eigenvector could not be orthogonal to any vector
in the original eigenspace (as it is composed of all the vectors with zero
values everywhere except the entries corresponding to the eigenvalue of
$\Sigma_{1}$ in question).

For the opposite case assume that $u\neq 0$ on the entries corresponding to
some eigenvalue $\sigma$ of $\Sigma_{1},$ and denote its multiplicity $m.$ In
this case, $\sigma$ will have multiplicity at least $m-1$ in
$\Sigma_{1}+cuu^{T},$ since there is $m-1$ dimensional sub-space of
eigenvectors in the eigenspace of $\sigma$ of $\Sigma_{1}$ that are orthogonal
to $u.$ The multiplicity, however, can still be also $m$ since $cuu^{T}$ can
create new eigenvectors.

For all the eigenvectors that were not enumerated yet (i.e. all within the
eigenspace where $u\equiv 0$ and $m-1$ for the eigenspace where $u\neq 0$), we
must have $u^{T}x\neq 0$ because otherwise $x$ would need to be eigenvector of
$\Sigma_{1}$ itself and would only have non-negative entries corresponding to
a single eigenvalue of $\Sigma_{1}$ but then it could not be orthogonal to $u$
since we have already enumerated all eigenvectors orthogonal to $u$ that are
non-zero only on one eigenvalue.

To this end we can infer that every $x$ left (thus $u^{T}x\neq 0$) has non-
zero entries on a superset of those of $u.$ But since we already know that $x$
can only have non-zero entries on at most two eigenvalues of $\Sigma_{1},$
this means that $u$ must as well. But then the number of eigenvectors for
which $u^{T}x=0$ is at least $r-2$ and we can have at most $2$ new
eigenvectors. This also means that at most two eigenvalues of
$\Sigma_{1}+cuu^{T}$ differ from those of $\Sigma_{1}.$

First assume that $u$ has non-zero entries on two distinct eigenvalues of
$\Sigma_{1}$, call them $\lambda_{1}<\lambda_{2}.$ Since $x$ also has non-zero
values on both, we must have $f(\lambda_{1})=f(\lambda_{2}).$ What are the
possible corresponding eigenvalues in $\Sigma_{1}+cuu^{T}$? Let
$\gamma_{1},\gamma_{2}$ be the two new eigenvalues. Since these are the
entries in $\Sigma_{2}$ and $f(\Sigma_{1})=f(\Sigma_{2}),$ neither of the
$f(\gamma_{1}),f(\gamma_{2})$ can be outside of the (multi-)set
$\\{f(\sigma_{1}),f(\sigma_{2}),\dots,f(\sigma_{r})\\}$ as then
$f(\Sigma_{2})$ would have some values that $f(\Sigma_{1})$ has not. Moreover,
from the interlacing we know $\gamma_{1}\geq\lambda_{1};\hskip
2.84526pt\gamma_{2}\geq\lambda_{1}.$ Furthermore, since the multiplicity of
$f(\lambda_{1})=f(\lambda_{2})$ eigenvalue of $f(\Sigma_{1})$ must stay the
same in $f(\Sigma_{2}),$ we also get $\gamma_{1}\leq\lambda_{2}$ and
$\gamma_{2}\leq\lambda_{2}.$ Even further, since only
$\lambda_{1},\lambda_{2}$ can change and both exhibit the same $f(\cdot)$
value, the $\gamma_{1},\gamma_{2}$ must be equal to either of these, otherwise
the number of $f(\lambda_{1})$ singular values in $f(\Sigma_{1})$ would be
strictly bigger than in $f(\Sigma_{2}).$ Altogether, this creates only one
possibility: $\gamma_{1}=\gamma_{2}=\lambda_{2}.$ However, this is a
contradiction, because if $\lambda_{2}=\gamma_{2}$ then we have
$cu^{T}xu=(\gamma_{2}I-\Sigma_{1})x=(\lambda_{2}I-\Sigma_{1})x.$ This cannot
happen since the LHS has a non-zero entry corresponding to the $\lambda_{2}$
eigenvalue in $\Sigma_{1}$ (assumption), while the matrix
$\lambda_{2}I-\Sigma_{1}$ has zero-diagonal at exactly those positions,
zeroing out the corresponding non-zero entries of $x$ and forcing inequality.

From this we judge that $u$ only has non-negative entries corresponding to one
single singular value (say $\lambda$) in $\Sigma_{1}.$ There can only be one
eigenvalue that changes and moreover $x=u,$ because $x$ cannot have any non-
zero entries not-corresponding to $\lambda,$ as it would fail to be orthogonal
to the other eigenvectors. Moreover for the entries corresponding to $\lambda$
it needs to be aligned to $u$ because all the other eigenvectors corresponding
to $\lambda$ form an orthogonal complement of $u$ on that eigenspace.

Now, since $u\in\mathcal{N}((V_{1})_{2:,:}),$ we know that
$u^{T}V_{1}^{T}=de_{1}^{T}$ for some $d\in\mathbb{R}.$ Then multiplying from
right with $V_{1}$ we get $u^{T}=de_{1}^{T}V_{1}.$ The RHS is just the first
row of $V_{1}.$ Therefore $u$ is aligned with the first row of $V_{1}.$222This
fact alone is deducible far sooner in the proof but the following
argumentation is crucial to make the proof work. Moreover, since $u$ is only
non-zero on the entries corresponding to the $\lambda$ eigenvalue, this means
that so does the first row of $V_{1}.$ We can now see that the first column of
$H_{1}^{(1)}$ is just a combination of the columns in $U_{1}$ corresponding to
$\lambda$ with the corresponding entries of $(V_{1})_{1:}.$ At the same time,
the first column of the $H_{1}^{(2)}-H_{1}^{(1)},$ which is nothing else than
$U_{1}cuu^{T}V_{1}^{T}$ happens to be the very same combination of the columns
of $U_{1}.$ Therefore, the first column of $H_{1}^{(1)}$ and that of
$H_{1}^{(2)}-H_{1}^{(1)}$ are aligned, which is a contradiction. This
concludes the proof of the theorem. ∎

See 8

###### Proof.

In order not to mix approximation technical details with the gist of the
proof, we split the argument into two parts: in the first part, we provide a
heuristic for $\epsilon=0$ by assuming that ReLU is differentiable at 0; in
the second part, we discuss what changes in the proof if we use the relaxation
and then execute a technical computation that bounds the error based on the
strength of the approximation (the size of $\epsilon$). It is useful to split
the loss function $\mathcal{L}$ into the two terms $\mathcal{L}_{F}$ and
$\mathcal{L}_{R}$. The former represents the fit part of the loss (which
penalizes for deviation of the predictions from $Y$), and the latter
represents the regularization part of the loss.

Part 1: Heuristic for $\epsilon=0$. We start identically to the proof of
Theorem 6. As in Step 1 of that argument, if we have a globally optimal
solution that does not exhibit DNC1 in the first layer, we can construct two
different solutions of the $n=1$ $L$-DUFM problem where the two solutions only
differ in the first column of the $H_{1}$ matrix. Let us denote two such
constructions $H_{1}^{x}\neq H_{1}^{y},$ where we denote $x\neq y,$ to be the
mentioned first columns, respectively. We emphasize that $H_{1}^{x},H_{1}^{y}$
both form optimal solutions of the $n=1$ $L$-DUFM with the same tuple of
weight matrices $(W_{1}^{*},\dots,W_{L}^{*}).$ In particular, this means that

$\left.\frac{\partial\mathcal{L}}{\partial
W_{1}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{x},W_{1}^{*},\dots,W_{L}^{*})}=0=\left.\frac{\partial\mathcal{L}}{\partial
W_{1}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{y},W_{1}^{*},\dots,W_{L}^{*})}.$

An application of the chain rule gives

$\frac{\partial\mathcal{L}}{\partial
W_{1}}=\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{2}}\frac{\partial\tilde{H}_{2}}{\partial
W_{1}}+\lambda_{W_{1}}W_{1}=\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{2}}H_{1}^{T}+\lambda_{W_{1}}W_{1}.$

Plugging this back to the previous equation and using that the $W_{1}^{*}$ is
the same in both expressions, we get

$\left.\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{2}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{x},W_{1}^{*},\dots,W_{L}^{*})}(H_{1}^{x})^{T}=\left.\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{2}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{y},W_{1}^{*},\dots,W_{L}^{*})}(H_{1}^{y})^{T}.$

Let us denote

$A=\left.\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{2}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{x},W_{1}^{*},\dots,W_{L}^{*})},\,\,\,B=\left.\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{2}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{y},W_{1}^{*},\dots,W_{L}^{*})}.$

Due to the separability of $\mathcal{L}_{F}$ with respect to the columns of
$H_{1}$ (and, thus, also $H_{l}$ for all $l\leq L$), we get that the matrices
$A,B$ can only differ in their first columns and are identical otherwise. We
denote these columns $a,b$ for $A,B,$ respectively. This implies that
$ax^{T}=by^{T}.$

Now, we treat a few cases. First, assume $a=b=0.$ Since it holds that
$(H_{1}^{x},W_{1}^{*},\dots,W_{L}^{*})$ is the optimal solution, then
necessarily

$0=\left.\frac{\partial\mathcal{L}}{\partial
h_{11}^{1}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{x},W_{1}^{*},\dots,W_{L}^{*})}=(W_{1}^{*})^{T}a+\lambda_{H_{1}}x\iff
0=x.$

Similarly, we get $y=0,$ but that is a contradiction with $x\neq y.$
Therefore, at least one of $a,b$ is non-zero. Next assume $x=0.$ Then
$ax^{T}=0.$ If $b=0$ then $y=0$ and we have a contradiction. On the other
hand, if $b\neq 0,$ then the row of $by^{T}$ that corresponds to a non-zero
entry of $b$ must be zero and thus $y=0$. Similarly, if $y=0$ we can get
$x=0.$

Let us therefore assume $x,y$ are both non-zero, which also implies $a,b$ are
both non-zero. Looking at any fixed row (column) of $ax^{T}$ and $by^{T}$ we
see that necessarily $x,y$ ($a,b$) are aligned. Let us write $x=\alpha y$ and
$\alpha a=b$ for some $\alpha\neq 0.$ We will first show that if $\alpha>0$
then necessarily $\alpha=1$ and $x=y.$ For this, let us fix any ray
$r\in\mathbb{R}^{d_{1}}.$ The ray $r$ represents a set of possible first
columns in $H_{1}.$ Let us fix any $(W_{1},\dots,W_{L})$. Since $\mathcal{L}$
is separable in the columns of $H_{1},$ we can consider an optimization over
$\beta\geq 0$ to minimize $\mathcal{L}$ on $(\beta r,W_{1},\dots,W_{L}).$
However, $\mathcal{L}_{F}$ is convex by assumption and the mapping
$h_{11}^{1}\xrightarrow[]{}h_{11}^{L}$ is ray-linear, therefore
$\mathcal{L}_{F}$ is convex in $\beta.$ Moreover $\mathcal{L}_{R}$ is strongly
convex in $h_{11}^{1}$ and therefore $\mathcal{L}$ is strongly convex in
$\beta.$ This means it has a unique optimal solution $\beta^{*}.$

We have just showed that, if $\alpha>0,$ then since $x,y$ are aligned and thus
lie on the same ray and are both optimal together with the same tuple of
weight matrices, they must necessarily be identical and so $\alpha=1,x=y.$
This is a contradiction and thus we are left with the case $\alpha<0.$ Denote
$s=W_{1}^{*}x$, $t=W_{1}^{*}y.$ From linearity, we have $s=\alpha t.$ Note
that if $s=t=0,$ then necessarily $x=y=0$ because they don’t have any effect
on $\mathcal{L}_{F}$ and they minimize $\mathcal{L}$ at $0$. Thus, $s,t$ are
non-zero and negative entries of $s$ are positive entries of $t$ and vice-
versa. This means that $\sigma(s)$ and $\sigma(t)$ have different sets of
positive entries. However, from the optimality of the both solutions we know:

$\left.\frac{\partial\mathcal{L}}{\partial
W_{2}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{x},W_{1}^{*},\dots,W_{L}^{*})}=0=\left.\frac{\partial\mathcal{L}}{\partial
W_{2}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{y},W_{1}^{*},\dots,W_{L}^{*})}.$

Again, using the chain rule we get:

$\frac{\partial\mathcal{L}}{\partial
W_{2}}=\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{3}}\frac{\partial\tilde{H}_{3}}{\partial
W_{2}}+\lambda_{W_{2}}W_{2}=\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{3}}H_{2}^{T}+\lambda_{W_{2}}W_{2}.$

Plugging this back to the previous equation and using that $W_{2}^{*}$ is the
same in both expressions, we get

$\left.\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{3}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{x},W_{1}^{*},\dots,W_{L}^{*})}(H_{2}^{x})^{T}=\left.\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{3}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{y},W_{1}^{*},\dots,W_{L}^{*})}(H_{2}^{y})^{T}.$

Let us denote

$C=\left.\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{3}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{x},W_{1}^{*},\dots,W_{L}^{*})},\,\,\,D=\left.\frac{\partial\mathcal{L}_{F}}{\partial\tilde{H}_{3}}\right|_{(H_{1},W_{1},\dots,W_{L})=(H_{1}^{y},W_{1}^{*},\dots,W_{L}^{*})}.$

Due to the separability of $\mathcal{L}_{F}$ with respect to the columns of
$H_{1}$ (and, thus, also $H_{l}$ for all $l\leq L$), we get that the matrices
$C,D$ can only differ in their first columns and are identical otherwise. We
denote these columns $c,d$ for $C,D$ respectively. This implies that
$c\sigma(s)^{T}=d\sigma(t)^{T}.$

As above, if either $c$ or $d$ is zero, using the chain rule we would get that
$x$ or $y$ (respectively) are zero too, which cannot happen. Therefore, both
$c$ and $d$ are non-zero and $\sigma(s),\sigma(t)$ must be aligned. Since they
are non-zero, non-negative and with different supports, we have reached a
contradiction. This proves that $\alpha<0$ is also impossible and the only
possible case is $\alpha=1,$ but that forces $x=y,$ which is also a
contradiction.

Part 2: Relaxation to ReLUϵ. The difficulty in making the previous heuristic
rigorous is that ReLU is not differentiable at 0 and, thus, we do not have the
desired analytical statement that global solutions must necessarily admit zero
derivative (because the loss might not be differentiable at them at all). If
we tried to use the same proof as in part 1 with the differentiable relaxed
version of ReLU – ReLU${}_{\epsilon},$ an issue would occur when showing that,
if $x,y$ are aligned and $\alpha\geq 0$, then $\alpha$ must be 1. The reason
is that the mapping $h_{11}^{1}\xrightarrow[]{}h_{11}^{L}$ is no longer ray-
linear and the corresponding optimization problem on any fixed ray is no
longer quadratic and strongly convex. However, we can prove that the
optimization problem admits a solution that is close to the solution of the
corresponding ReLU optimization problem. For this, let us fix any direction
$r$ such that $\left\lVert r\right\rVert=1$ and an optimization parameter
$t\geq 0$, and define the following two losses:

$\displaystyle L_{0}(t,r)$ $\displaystyle=\frac{1}{2K}\left\lVert
W_{L}^{*}\sigma(W_{L-1}^{*}\sigma(\dots
W_{2}^{*}\sigma(W_{1}^{*}tr)\dots))-e_{1}\right\rVert_{F}^{2}+\frac{n\lambda_{H_{1}}}{2}t^{2},$
(21) $\displaystyle L_{\epsilon}(t,r)$ $\displaystyle=\frac{1}{2K}\left\lVert
W_{L}^{*}\sigma_{\epsilon}(W_{L-1}^{*}\sigma_{\epsilon}(\dots
W_{2}^{*}\sigma_{\epsilon}(W_{1}^{*}tr)\dots))-e_{1}\right\rVert_{F}^{2}+\frac{n\lambda_{H_{1}}}{2}t^{2}.$
(22)

We now bound $\underset{t\geq 0}{\max}\hskip
2.84526pt|L_{0}(t,r)-L_{\epsilon}(t,r)|.$ For this, we fix any $t\geq 0$, and
bound the accumulated $l_{2}$ error of using $\sigma_{\epsilon}$ instead of
$\sigma$ throughout the layers. For this, a useful statement that we will need
is the following:

$\frac{\lambda_{W_{L}}}{2}\left\lVert
W_{L}^{*}\right\rVert_{F}^{2}=\frac{\lambda_{W_{L-1}}}{2}\left\lVert
W_{L-1}^{*}\right\rVert_{F}^{2}=\dots=\frac{\lambda_{W_{1}}}{2}\left\lVert
W_{1}^{*}\right\rVert_{F}^{2}=\frac{n\lambda_{H_{1}}}{2}\left\lVert
H_{1}^{*}\right\rVert_{F}^{2}\leq\frac{1}{2(L+1)}.$

This is true because, by a simple computation, we get that the terms must be
balanced and the inequality comes from the fact that the solution
$(0,0,\dots,0)$ achieves full loss $1/2$ in the $L$-DUFM as well as $L$-DUFMϵ
problems and, thus, $\mathcal{L}_{R}$ is trivially upper-bounded by this. This
implies that, for each $W_{l}$ (and $H_{1}$), $\left\lVert
W_{l}\right\rVert\leq\left\lVert
W_{l}\right\rVert_{F}\leq\frac{1}{\sqrt{(L+1)\lambda_{W_{l}}}}.$

For ease of exposition, we set $t=1$ (the same argument would work for all
$t$). We see that $W_{1}r$ does not introduce any $l_{2}$ error. Then, the
$l_{2}$ error that is introduced in the application of the ReLU is trivially
upper-bounded by $\epsilon\sqrt{d_{2}}.$ After applying $W_{2},$ we can use
the bound on the operator norm $\left\lVert W_{2}\right\rVert$ obtained above
to upper bound the propagated $l_{2}$ error by

$\frac{1}{\sqrt{(L+1)\lambda_{W_{2}}}}\epsilon\sqrt{d_{2}}.$

After that, we obtain an additive $l_{2}$ error of $\epsilon\sqrt{d_{3}}$ by
applying $\sigma_{\epsilon}$, which gives a total $l_{2}$ error of

$\frac{1}{\sqrt{(L+1)\lambda_{W_{2}}}}\epsilon\sqrt{d_{2}}+\epsilon\sqrt{d_{3}}.$

Then, again, we multiply this whole expression with
$\frac{1}{\sqrt{(L+1)\lambda_{W_{3}}}}$ to account for the multiplication by
$W_{3}.$ Inductively, the upper bound on the $l_{2}$ error in the output space
is

$\epsilon\sum_{l=2}^{L}\frac{\sqrt{d_{l}}}{(L+1)^{\frac{L-l+1}{2}}}\prod_{j=l}^{L}\frac{1}{\sqrt{\lambda_{W_{j}}}}.$

This can be further upper bounded as

$\frac{\epsilon\sqrt{D}\sqrt{\lambda_{H_{1}}\lambda_{W_{1}}}}{(L+1)^{\frac{L-1}{2}}\sqrt{\bar{\lambda}}}.$

Using the triangle inequality, the upper bound on
$|L_{0}(t,r)-L_{\epsilon}(t,r)|$ is this expression squared. On the other
hand, the second derivative of $L_{0}(t,r)$ with respect to $t$ is lower
bounded by $n\lambda_{H_{1}}.$

Given two functions $f_{1}$ and $f_{2}$, with $f_{1}$ strongly convex with
second derivative at least $c$ and $f_{2}$ everywhere at most $d$ distant from
$f_{1}$, then the distance between their global minimizers is at most
$2\sqrt{d/c}$. Applying this to our case, we get that the distance between the
minimizers $t_{0}$ and $t_{\epsilon}$ of $L_{0}(t,r)$ and $L_{\epsilon}(t,r)$
is at most

$\frac{2\epsilon\sqrt{D(L+1)}}{(L+1)^{\frac{L+1}{2}}\sqrt{\bar{\lambda}n}}.$

Since the ray $r$ is unit-norm, this is also the upper bound on the distance
between two feature vectors of any globally optimal solution in the first
layer. To obtain the upper bound on the distance between two vectors in any
layer, we proceed as follows.

Assume we have two input vectors of the first class (now we know they need to
be aligned): $x^{1},y^{1}=\alpha^{1}x^{1},$ where $\alpha^{1}>1$. As before,
$\tilde{x}^{l},x^{l},\tilde{y}^{l},y^{l}$ are the $l$-th layer representations
of these vectors before and after $\sigma_{\epsilon}.$ If we would compute
$\frac{\partial\mathcal{L}}{\partial W_{l}}$ with respect to any layer $l\geq
2$ and used the same arguments as in part 1 (that still carry to the analysis
for $\sigma_{\epsilon}$), we would find out that in each layer, we need to
have $y^{l}=\alpha^{l}x^{l}.$ Moreover, we can assume that
$\tilde{x}^{l},x^{l},\tilde{y}^{l},y^{l}$ are non-zero at all layers because
otherwise the same argument in part 1 would trivialize the rest of the proof.
By a simple inductive argument, since $\alpha_{1}>1,$ we know that
$\alpha_{2}>1$ as well because $\sigma_{\epsilon}$ is strictly increasing on
$[0,\infty).$ Similarly, $\alpha_{l}>1$ for all $l.$ Note that, if there
exists at least one index $i$ on which $x^{l}_{i}$ is bigger or equal than
$\epsilon,$ then necessarily $\alpha^{l}=\alpha^{l-1},$ because
$\sigma_{\epsilon}$ is the identity on inputs of at least $\epsilon$, and the
$\alpha_{l}$ can be uniquely determined from
$y_{i}^{l}/x_{i}^{l}=y_{i}^{l-1}/x_{i}^{l-1}.$ Having
$\alpha^{l}=\alpha^{l-1}$ makes us have more control over the distance between
$x^{l}$ and $y^{l}.$ If this fails to hold at some layer, we need a separate
analysis.

For this, let $l_{0}$ denote the first layer (assuming it exists), where
$\tilde{x}^{l_{0}}$ does not have any entries that are bigger or equal than
$\epsilon.$ This means that $\left\lVert
x^{l_{0}}\right\rVert\leq\epsilon\sqrt{d_{l_{0}}}.$ We now compute the maximal
possible norm of $y^{l_{0}}$. Since
$\alpha_{1}=\alpha_{2}=\dots=\alpha_{l_{0}-1},$ for all $2\leq l<l_{0}$ and
for each index $i,$ either $\tilde{x}^{l}_{i},\tilde{y}^{l}_{i}\leq\epsilon$
or $\epsilon\leq\tilde{x}^{l}_{i},\tilde{y}^{l}_{i}.$ Otherwise, since
$\sigma_{\epsilon}(x)<x\hskip 2.84526pt\forall x\in(0,\epsilon),$
$y_{i}^{l}/x_{i}^{l}>\alpha_{l},$ a contradiction. Thus, we get
$\left\lVert\tilde{x}^{l}-\tilde{y}^{l}\right\rVert\geq\left\lVert
x^{l}-y^{l}\right\rVert.$ Therefore, $\left\lVert x^{l}-y^{l}\right\rVert$ can
only grow by applying $W_{l}.$ Thus, after applying
$W_{1},W_{2},\dots,W_{l_{0}-1}$ and using the operator norm bound with all of
the matrices, we get

$\left\lVert
x^{l}-y^{l}\right\rVert\leq\frac{2\epsilon\sqrt{D(L+1)}}{(L+1)^{\frac{L+1}{2}}\sqrt{\bar{\lambda}n}}\frac{1}{(L+1)^{\frac{l_{0}-1}{2}}\sqrt{\lambda_{W_{1}}\lambda_{W_{2}}\dots\lambda_{W_{l_{0}-1}}}}.$

Combining with $\left\lVert x^{l_{0}}\right\rVert\leq\epsilon\sqrt{d_{l_{0}}}$
and using the triangle inequality, we get

$\left\lVert
y^{l}\right\rVert\leq\frac{2\epsilon\sqrt{D(L+1)}}{(L+1)^{\frac{L+1}{2}}\sqrt{\bar{\lambda}n}}\frac{1}{(L+1)^{\frac{l_{0}-1}{2}}\sqrt{\lambda_{W_{1}}\lambda_{W_{2}}\dots\lambda_{W_{l_{0}-1}}}}+\epsilon\sqrt{d_{l_{0}}}.$

Applying the operator norm bound with $W_{l_{0}},W_{l_{0}+1},\dots,W_{L-1},$
we get:

$\displaystyle\left\lVert y^{L}\right\rVert$
$\displaystyle\leq\frac{2\epsilon\sqrt{D(L+1)}}{(L+1)^{\frac{L+1}{2}}\sqrt{\bar{\lambda}n}}\frac{1}{(L+1)^{\frac{L-1}{2}}\sqrt{\lambda_{W_{1}}\lambda_{W_{2}}\dots\lambda_{W_{L-1}}}}$
$\displaystyle\hskip
40.00006pt+\epsilon\sqrt{d_{l_{0}}}\frac{1}{(L+1)^{\frac{L-l_{0}}{2}}\sqrt{\lambda_{W_{l_{0}}}\lambda_{W_{l_{0}+1}}\dots\lambda_{W_{L-1}}}}$
$\displaystyle\leq\frac{3\epsilon\sqrt{D(L+1)}}{(L+1)^{L+1}\bar{\lambda}\sqrt{n}}.$

Since $\left\lVert x^{L}\right\rVert\leq\left\lVert y^{L}\right\rVert$ we can
use the triangle inequality again to obtain the final:

$\left\lVert
x^{L}-y^{L}\right\rVert\leq\frac{6\epsilon\sqrt{D(L+1)}}{(L+1)^{L+1}\bar{\lambda}\sqrt{n}}.$

Note that the same bound is an upper bound for any layer, since in each layer
we are increasing the upper bound by at least a factor
$(L+1)^{-1/2}\lambda_{W_{l}}^{-1/2}$.

In case such a layer $l_{0}$ does not exist, the upper bound above is still
valid, since we can simply use the error propagation through all the layers,
as we did for $l<l_{0}$ in the previous case. We would arrive at the same
bound as above but with $4$ instead of $6$ as a multiplicative factor (because
we would not introduce the additive error $\epsilon\sqrt{d_{l_{0}}}$). ∎

##  Appendix B Further experimental evidence

###  B.1 $L$-DUFM experiments

#### Experiments on small number of classes and layers.

For $L=3,$ we weren’t able to find any solutions that would outperform DNC for
$K\leq 6$. For $K=7,$ the difference in the losses is extremely small. For
$K=6,$ we did find some low rank solutions, but these were either slightly
worse than DNC or the losses were the same up to four decimal places. Already
for $L\geq 4,$ we find low-rank solutions for all $K\geq 3.$ We present some
of them for $K\in\\{3,4,5\\}$ in Figure 5. Note, that all these solutions were
found automatically by gradient descent through the optimization process.

Figure 5: $4$-DUFM training for $K=3$ (top), $K=4$ (middle), and $K=5$
(bottom). Left: Loss progression, also decomposed into the fit and
regularization terms. Middle left: Visualization of the matrix $M_{3}$. Middle
right: Visualization of the matrix $\tilde{M}_{4}$. Right: Visualization of
the matrix $M_{3}^{T}M_{3}$.

We specifically highlight the solution for $K=4$, as it represents another
graph structure different from SRG. Namely, this solution is based on the
square graph. We see that each column (edge) has positive scalar product with
exactly two other columns (the corresponding edges share a vertex), and it is
orthogonal to one other column (the non-touching sides of a square). Each row
(vertex) has only two positive values, and these correspond to the two sides
(edges) to which they belong.

#### Experiments on large number of classes or layers.

For large $L$ or $K,$ the behavior of the low-rank solutions is slightly
different from the behavior when both $L$ and $K$ are moderate. When $l$ is
close to $L$, it no longer holds that $\tilde{M}_{l}=M_{l}$, and the rank of
$M_{l}$ is larger as the singular values do not decay sharply to $0$. However,
we note that the singular values are rather small and, thus, it is not clear
whether they would disappear with a longer training (we trained for 200000
steps of full gradient descent with learning rate 0.5). In Figure 6, we take
$L=7,K=15$, and weight decay $0.0025$ in all layers. We highlight that
$\tilde{M}_{6}\neq M_{6}$ and the singular values of $M_{6}$ are small but
non-zero after the 3 dominant values. We also highlight that the rank of
previous layers is 3, which is remarkably small (and also smaller than the
rank of the SRG solution).

Figure 6: Class-mean matrices and singular values at convergence for a DUFM
model with $K=15$ and $L=7$. Top row: Singular values of $\tilde{M}_{2}$, and
visualization of the matrices $\tilde{M}_{2},\tilde{M}_{6},M_{6}$ and Bottom
row: Singular values of $\tilde{M}_{6}$ and $M_{6}$.

#### SRG solutions.

In Figure 1 presented in the main body, we recover the SRG solution for
$K=10$. In Figures 7 and 8, we show that solutions very similar to SRG are
recovered for $K=6$ and $K=15$, respectively. The only difference with SRG is
in the construction of $\tilde{M}_{L}$. We note that the losses of these
solutions are slightly lower than the loss of our construction, which proves
that the SRG solution itself is not necessarily globally optimal.

Figure 7: $4$-DUFM training for $K=6$. Top row: Visualization of the matrices
$\tilde{M}_{3}^{T}\tilde{M}_{3},\tilde{M}_{3}$, and $\tilde{M}_{4}.$ Bottom
row: Singular values of $H_{3},$ and loss progression including its
decomposition into fit and regularization terms.

Figure 8: $4$-DUFM training for $K=15$. Top row: Visualization of the matrices
$\tilde{M}_{3}^{T}\tilde{M}_{3},\tilde{M}_{3}$ and $\tilde{M}_{4}$. Bottom
row: Loss progression including its decomposition into fit and regularization
terms.

###  B.2 End-to-end experiments with DUFM-like regularization

We complement the experiments of Figure 3 with two extra ablation studies for
ResNet20 trained on CIFAR-10 with a 4-layer MLP head. We focus on the
dependence of the average rank on the weight decay and the learning rate, and
present the results in Figure 9. The weight decay has a clear effect on the
rank of the solutions found by gradient descent, similarly to the results in
Figure 3 for the $L$-DUFM model. The effect of the learning rate is slightly