The Asymmetric Maximum Margin Bias of Quasi-Homogeneous Neural Networks
Authors: Daniel Kunin
Atsushi Yamamura
Chao Ma
Surya Ganguli
Venue: ICLR 2023 notable top 25% (2023)
Keywords: margin
maximum-margin
implicit regularization
neural networks
neural collapse
gradient flow
implicit bias
robustness
homogeneous
symmetry
classification

Abstract: In this work, we explore the maximum-margin bias of quasi-homogeneous neural networks trained with gradient flow on an exponential loss and past a point of separability. We introduce the class of quasi-homogeneous models, which is expressive enough to describe nearly all neural networks with homogeneous activations, even those with biases, residual connections, and normalization layers, while structured enough to enable geometric analysis of its gradient dynamics. Using this analysis, we generalize the existing results of maximum-margin bias for homogeneous networks to this richer class of models. We find that gradient flow implicitly favors a subset of the parameters, unlike in the case of a homogeneous model where all parameters are treated equally. We demonstrate through simple examples how this strong favoritism toward minimizing an asymmetric norm can degrade the robustness of quasi-homogeneous models. On the other hand, we conjecture that this norm-minimization discards, when possible, unnecessary higher-order parameters, reducing the model to a sparser parameterization. Lastly, by applying our theorem to sufficiently expressive neural networks with normalization layers, we reveal a universal mechanism behind the empirical phenomenon of Neural Collapse.

Published as a conference paper at ICLR 2023
THE ASYMMETRIC MAXIMUM MARGIN BIAS OF QUASI- HHASS-HOMOGENEOUS NEURAL NETWORKS
Daniel Kunin" & Atsushi Yamamura (11))))))))) Stanford University {kunin, st (
Chao Ma, Surya Ganguli
Stanford University (chaoma, gganguli
ABSTRACT
In this work, we explore the maximum-margin bias of quasi-homogeneous neu- ral networks trained with gradient flow on an exponential loss and past point of separability. We introduce the class of guasi-homogeneous models, which is expressive enough to describe nearly all neural networks with homogeneous ac- tivations, even those with biases, residual connections, and normalization layers, while structured enough to enable geometric analysis of its gradient dynamies. Using this analysis, we generalize the existing results of maximum-marge for homogeneous networks to this richer class of models. We find that gradient flow implicitly favors subset of the parameters, unlike in the case of homoge- neous model where all parameters are treated equally. We demonstrate through simple examples how this strong favoritism toward minimizing an asymmetric norm can degrade the robustness of quasi-homogeneous models. On the other hand, we conjecture that this comm-minimizationn discards, when possible, unnec- essary higher-rate parameters, reducing the model to sparser parameterization. Lastly, by applying our theorem to sufficiently expressive neural networks with normalization layers, we reveal a universal mechanism behind the empirical phe- nomenon of Neural Collapse
bias
INTRODUCTION
Modern neural networks trained with (stochastic) gradient descent generalize remarkably well de- spite being trained well past the point at which they interpolate the training data and despite having the functional capacity to memorize random labels Zhang et al. (202T). This apparent paradox has led the hypothesis that there must exist an implicit process biasing the network learn "good" generalizing solution, when one exists, rather than one of the many more "bad" interpolating ones. While much research has been devoted to identifying the origin of this implicil bias, much of the theory is developed for models that are far simpler than modern neural networks. In this work, we extend and generalize long line of literature studying the maximum marrgi bias of gradient descent in quasi-homo homoneneoss networks, a class of models we define that encompasses nearly all modern feedforward neural network architectures. works with homogeneous nonlincarities, bias parameters, residual connections, pooling layers, and normalization layers. For example, the ResNet-18 convolutional network introduced by He et al. 2016) is quasi- guasi-homogeneous. We prove that after surpassing certain threshold in training, gra- dient flow on an exponential loss, such as cross-entropy, drives the network to a aakiimuu-marginn solution under norm constraint the parameters. Our work is a direct generalization of the sults discussed for homogeneous networks in Lyu & 2019). However, unlike in the homogeneous setting, the norm constraint only involves subset of the parameters. For example, in the case of ResNet- 18 network, only the last layer's 's weight and bias parameters are constrained. This asymmet- ric norm can have non-trivial implications on the robustness and optimization of quasi-homogencous models, which we explore in sections 5 and 6
muasi-homogeneouu networks include feedforward net-
"Equal contribution. Correspondence Daniel Kumin and Atsushi Yamamura.

---

Published as a conference paper at ICLR 2023
2 BACKGROUND AND RELATED WORK
Early works studying the maximum-margin bias of gradient descent focused on the simple, yet insightful, setting of logistic regression Rosset et al. (2003); Soudry et al. (2018). Consider a binary classification problem with linearly separable" training dataset ( Vs where I; E Rd and y E {-1,1}, a linear model f(x; B) 3Tz, and the exponential loss [(3) E; -vf((==88) As shown in /oudry et al. (2018). the loss only has a minimum in 3 as its norm becomes infinite. Thus, even after the network correctly classifies the training data, gradient descent decreases the loss by foreing the norm of 3 to grow in an unbounded manner, yielding a slow alignment of 5 in the direction of the maximum l2- fz-margin solution, which is the configuration of / that minimizes ||š|] while keeping the margin min; ye (x;; 3) at least 1. But what if we parameterize the regression coefficients differently? As shown in Fig. [ different parameterizations, while not changing the space of learnable functions, can lead to classifiers with very different properties.
Linear networks. An early line of works ex- ploring the influence of the parameterization on the maximum marginn bias studied the same set- ting as logistic regression, but where the regres- sion coefficients are multilinear functions of parameters 0. Ji & Telgarsky (2018) showed that for deep linear networks, B == II, W the weight matrices asymptotically align to rank-1 1 matrix, while their product converges to the maximum fz-margin solution. Gunasekar jet al. (0188) showed that linear diagonal net- works,
12-
1.2
x
0.0
-066
-0.6
-12
-12
X1
(b) 3 = 0102
(a) 8
wi ..... O wn. converge to the maximum mmaggnn solution, demonstrat- ing that increasing depth drives the network to sparser solutions. They also show an analo- gous result holds in the frequency domain for full-width linear convolutional networks. Many other works have advanced this line of litera- ture, expanding to settings where the data is not linearly separableJJi & Telgarsky (2019), gener- alizing the analysis to other loss functions with exponential tails Nacson et al.] (2019b), con- sidering the effect of randomness introduced by stochastic gradient descent |acson et al. (2019)), and unifying these results under ten- sor formulation Yun et al. (2020).
Figure 1: Maximum-margin bias changes with parameterization. Logistic regression, f(r) = 3Tx, trained with gradient descent on a homo- geneous (left) and quasi-homogeneous (right) pa- rameterization of the regression coefficients B. The dashed black line is the maximum m2-margin solution and the solid black line the gradient de- scent trained classifier after 1e5 steps. Existing theory predicts the homogeneous model will con- verge the maximum f2-margin solution. In this work we will show that the quasi-homogeneous model is driven by different maximum-margin problem.
Homogeneous networks. While linear networks allowed for simple and interpretable analysis of the implicit bias in both the space of 0 (parameter space) and the space of 33 (function space), it unclear how these results on linear networks relate to the behavior of highly non-lineat networks used in practice. |Wei et al. (2019) and Xu et al. (2021) made progress towards analysis of non-linear networks by considering shallow, one or two layer, networks with
homooieeeoomm activations, i.e., there exists T. RR such that / fax) a² fxx for all a E R More recently, two concurrent works generalized this idea by expanding their analysis to all positive- haattie-homogencouus networks. Nac- son et al. (2019a) used vanishing regularization to show that long the training error converges to zero and the parameters converge in direction, then the rescaled parameters of a homogeneous (KKT) point of tion problem. Lyu & Li (2019) defined a normalized margin and showed that once the training loss drops below a certain threshold, a smoothed version of the normalized margin monotonically converges, allowing them to conclude that all rescaled limit points of the normalized parameters are first-order KKT points of the same optimization problem. follow up work. Ji & Telgarsky (2020). developed theory of unbounded, nonsmooth Burdyka-Lojasiewar stronger result of directional convergence of the parameters and alignment of the gradient with the parameters along the gradient flow path. Lyu & Li (2019) and Ji & Telgarsky (200)) also explored empirically non-homogeneous models with bias parameters and Nacson et al. (2019a) considered
model converges to a first-order
Kaah-KKunnTTuus
makiiuum-mrrginn optimiza-
incqualities to prove a
II Linearly separable implies there exists w. E Rd such that for all [p),, y.w. 2 1.
2

---

Published as a conference paper at ICLR 2023
theoretically homomomoogeuuu models defined ensemble of homogeneous models of differ- ent orders. While these works have significantly narrowed the gap between theory and practice, all three works have also highlighted the limitation in applying their analysis to architectures with bias parameters, residual connections, and normalization layers, a limitation we alleviate in this work. In a parallel literature studying low-rank biases in deep learning, Le & Jegelka (2022) analyzed non-homogeneous models where the nonlincarities are restricted to the first few layers.
3 DEFINING THE CLASS OF QUAST-HOMOGENEOUS MODELS
Here introduce the class of quasi-homogeneous models, which is expressive enough describe nearly all neural networks with positiv-homooeneouss activations, while structured enough to enable geometric analysis of its gradient dynamics. Throughout this work, we will consider binary clas- sifier [z; 0) Rd + R. where 0 E IR" is the vector concatenating all the parameters of the model. We assume the dynamics of ((t) over time t are governed by gradient flow de
= a0 on an ex- Oc
di
ponential loss (())
Σ; - computed over training dataset (111,11),.. ... -.. (In vn))
of size where 24 E Rd and y/ E 1-, In App. H generalize our results to multi-class classification with the cross- cross-entropy loss.
Definition 3.1 (A-Quate a model I (2; 0) is A-quasi-homogeneen
For a (non-zero) positive semi-desinite matrix mm if under the parameter transformation
va (0) == O0
the oulput of the model scales [(z; (0)) e (a; for all a E R and input x.
In this work, we assume A is diagona and let X; (A);s and Amax max; A be the maximum diagonal element, which must be positive. Definition (3.1) generalizes the notion of positive homo- geneous functions, allowing different scaling rates for different parameters to yield the same scaling of the output. Given two parameters with different values of X, we refer to the parameter with larger À higher-rate and the other as lower-rate.
Examples. We consider some simple quasi-homogeneous networks that are not homogeneous.
Unbalanced linear diagonal network. Consider a diagonal network as described in Gunasekar al. 2018). but with a varying depth for different dimensions of the data. The regression coefficient 3 for input component x; is parameterized as the product of D, E N parameters, yielding [(;;; 0) -
E, 0zz) When the D; are equal, the network is homogeneous, otherwise, the network is quasi-homogeneous where the choice of X can be D for 0eg.
Fully connected network with biases. One of the simplest quasi- massi-homoeeeouus models is a multi- layer, fully-connected network with bias parameters, such the two-layer network, fa; 0) wDo (E, w.t + b²) + 12, where af is a Rectified Linear Unit (ReLU). Without biases this net- work would be homogeneous, but their inclusion requires a quuai-hoooggneeon scaling of parame- ters to uniformly scale the output of the model. For example, the choice of X can be for b² and 1/2 for all other parameters.
Networks with residual connections. Similar to networks with biases, residual connections result in a computational path that requires a quasi-homogeneon scaling of the parameters. For example, the model fa; 8) Σ3 w (2, w 2i + 2z) is quasi- hoaasiihomogeeeuus, where the choice of X can be for w2 and 0 for w
Networks with normalization layers. As discussed in Kunin et al. (2020), when normalization lay- ers, such as batch normalization, are introduced into a homogeneous network, they induce scale invariance in the parameters in the preceding layer. However, as long the last layer is positive homogeneous, then a network with normalization layers is quasi-homogeseous.. For example, the network f (x:; A) = De wo,,(0', xx) + is nuasi-homogeneous, where is the weight of the last layer, b is the bias, 6 is the set of parameters in earlier layers, and (00', .x) is the activation of the last hidden layer after normalization. The choice of À can be 1 for and and 0 for 8'.
See App. A for more examples of quasi-homogeneous models and their relationship to ensembles of homogeneous networks of different orders, discussed in Nacson al. (2019)).
When A is not diagonal, by reparameterizing the model 0 ++ 09 with proper orthogonal matrix O, we can diagonalize A.
3

---

Published as a conference paper at ICLR 2023
Geometric properties. Like homogeneous functions, quasi-homogeneourr functions have certain geometric properties of their derivatives. Analogous to Euler's Homogeneous Function Theorem, for wuagi-homogeneous f(z; 0), have ( = fa: 9), which is easily derived by evaluating the derivative Val t/a (f)) at a = O, the identity element of the transformation. Analogous to how the derivative of a homogeneous function of order I. homogeneous function of function under the same transformation respects the following property, [ef da (f)) = ca(T-A) ( Vef 0). See App. A for a derivation of the geometric properties of
order 1-1, the derivative of a quasi-homooeneeeee
functions.
Characteristic curves. Throughout this work
consider the partition of parameter space into the family of one-dimensional character-
1.2
12
0.6
0.6
istic curves mapped out by the parameter trans- formation in Eq. The vector field generating Hyhe
0.0
0.0
-066
-0.6
the transformation, de a=0 = A6, is tangent to the characteristic curve and thus we will refer to this vector as the langent vector. We define d9 the angle w between the velocity di and tangent vector such that the cosine similarity between these two vectors is 3 == cos(w)
-12
-12
(a) A1 = (b) A1 1, A2 0.5
(A0, mi
Figure 2: A natural coordinate system for quasi-homogeneous models. A useful coordi- nate system for studying the gradient dynamics of houuii-oomoeeeouus models is the decomposi- tion of parameter space into characteristic curves (solid lines) and level sets of the A-seminorm (dashed lines). For homogeneous function (left), this decomposition is equivalent to a polar de- composition. For quasi-homogeneous func- tion (right), then the directions of the charac- teristic curves are eventually dominated by the highest-rate parameters and the level sets of the A-seminorm are concentric ellipsoids.
A-Seminorm. The characteristic curves per- pendicularly intersect family of concentric el- lipsoids defined by the A-seminorm, [|0]|, ==
L; X.OP. Together, the intersection of given characteristic curve with an ellipsoid of given A-seminorm uniquely defines single point in parameter space. In the setting of homogeneous networks, this geometric structure is equivalent to a polar decomposition of parameter space. We also define the A-normalized parameters (0) where r()) is implicitly defined such that ||01% = 1. This corresponds to unique projection of parameter 0 onto the unit A-seminorm ellipsoid by moving along a characteristic curve.
As shown in Fig. 2 for homogeneous function, the characteristics are rays and the A-seminorm is proportional to the Euclidean norm ||0||. For a muasi--homoeneeuur function, then the directions of the characteristic curves and the A-seminorm eventually dominated by the highest-rate parame- ters. Thus, we will also find it helpful to define the Amax--Sminng meminnemmo as ||0]|3
Amax -Ex,=Amax X:03-
4
MAXIMUM-MARGIA BIAS
Having defined the class of quasi-homogeneous models and identified natural coordinate system to explore their gradient dynamics, we now generalize the maximum-margin bias theory developed in Lyu & Li (2019) for homogeneous models to a general quasi- mossi-homogeneous model fx; 6). Fol-
lowing the analysis strategy of Lyu & Li 2011), make the following assumptions:
A1 (ooose-oooogee)euss) There exists non-zero diagonal positive semi-definite matrix A, such that the model [(x; 0) is A-quasi-homooeneouu.
A2 (Regularity). For any fixed x. [a; 0) locally Lipschitz and admits chain rule
A3 (Exponential Loss). C(0) = 1
n Σ, 4 where f = e (a..0)
A4 (Gradient Flow). Learning dynamics are governed by de
E 0 for all / > 0.
के A5 (Strong Separability). There exists a time to such that ((o()))) < n
We also make the following additional assumptions not presented in Lyu & Li (0119:
3 Nearly all neural networks have this property, including those with ReLU activations. For details, Davis et al. (2020) or Ly & (2019).
"The Clarke's subdifferentia of 2 is generalization of VoL. for locally Lipschitz functions. For details,
App.
4

---

Published as a conference paper at ICLR 2023
A6 (Normalized Convergence). lim (tt) exists.
A7 (Conditional Separability). There exists a > 0 such that only 0 with |i0|lAmme 2 can separate the training data.
A implies the convergence of the decision boundary and A implies that Amax parameters play a role in the classification task. Ao is necessary for technical reason, but we expect that this assumption can be weakened by exploiting the argument in Di Telgarsky (2020). i trivially true for homogeneous model where ||@]|amx =
||0| 1, but not for haaasi-oooogeeouus model. In section 5 we will consider what happens when we remove this assumption. We now state our main theoretical result:
Theorem 4.1 QuaasiHomogeneeee Maximum- Mariinn)-M Under assumptions Al to A7, there exists 5 of the optimization problem:
an R such that da 2 f(t)) is first-order KKT poin
minimize 1011 Amax
subject to (xf((x0)22) Vi e
Significance. Theorem 4.1 implies that after interpolating the training data, the learning dynamics of the model driven by competition between maximizing the margin in function space and minimizing the -emiinom in parameter space. At first glance, this might seem like a straight- forward generalization of the result discussed in Lyu Li (2019) for homogeneous networks, but crucially, whenever A is quasi-homogeneous, which is the case for nearly all realistic networks, then the optimization problems
different, as ||0|| * ||0||- In the quasi-homogeneou setting, the Amax- seminorm will only depend on subset of the parameters, and potentially an unexpected sub- set, such as just the last layer bias parameters for a standard fully-connected network. In section and 6 we will further discuss the implications of this result.
The heart of the argument proving Theorem 4.1 essentially relies on showing that after all the assumptions are satisfied, then as & - do the A-seminorm diverges ||б]| + oo and the angle w converges w -> 0. The convergence of implies that the training trajectory converges to certain characteristic curve and the divergence of ||Ø]| implies that the trajectory diverges along this curve away from the origin. In the homogeneous setting the characteristic curves are rays, implying that as - oo the velocity de
Intuition.
ăr aligns in direction to 0. This alignment of the velocity with V ||]|22 is the key property allowing previous works to derive 1|10| as the objective function of the implicit optimization problem. However, in the quasi-homogeneous setting, the directions of the characteristic curves are eventually dominated by the Amax parameters, which is what gives rise to the asymmetric objective function ] in our work.
Proof sketch. We defer most of the technical details of the proof of Theorem 4.1 but state the central lemma and the overall logical structure below. As in Lyu & Li (019)) the key mathematical object of our analysis a normalized margin. The margin, defined as Imin (f) == min; (x;; 0), is non-differentiable and unbounded, making it difficult to study. Thus, we define the normalized margin, r()) : (win(()
App.
and the smooth normalized margin, ||o| Amax
log((n2)2) which is a smooth approximation of 7. We then prove the following key [101)
7(0) =
lemma lower bounding changes in the A-seminorm ||0]] and the smooth normalized margin 5. This lemma holds throughout training, even before separability is achieved, and we believe could be of independent interest to understanding the learning dynamics.
Lemma 4.1 (Dynamics of ||θ]| and 7). Under assumptions AT A2 A and A4 the dynamics of the A-seminorm and smooth normalized margin are governed by the following inequalities.
1 d |0113 2 Clog((nL))))
d
log(5) 2 Amax log([10]A)) tan(w)? dt
(2)
for all i for the first inequality, and for almost every >> 0 for the second inequality.
Notice that once the separability assumption is met, the lower bound on the tieevveriatiie of ||0113 strictly positive. This allows to conclude that the A-seminorm diverges and the loss converges
*This KKT condition is necessary for the optimality since every feasible point satisfies Mangasarian- Fromovitz constraint qualification (MFCQ) condition (Lemma A.4).
5

---

Published as a conference paper at ICLR 2023
We then seek to prove the directional convergence of the parameters to the tangent vector Ad generating the characteristic curves. We first prove that ÿ is upper bounded using the definition of the margin and A7 (Lemma E.3). Combining this upper bound with the monotonicity of Ý proved in Lemma 4.1 we can conclude by monotone convergence argument that & will converge. Taken together, the convergence of & and the divergence of ||01] implies the angle w + 0 on specific sequence of time (Lemma [.4]. Finally, we use the divergence ||0]|A + 3o and the convergence w + 0 to prove there exists scaling of the normalized parameters that converges to first-order KKT point of the optimization problem Pin in Theorem
C c-0 (Lemma E.2
function f. the value of A, and the Amax parameter set, is not necessarily unique and therefore one may think T. looks inconsistent. However, the conditional separability (A7). which is required to apply Theorem 4.1 removes this possibility.
Non-uniqueness of A. For
See App. B for discussion on how to determine the highest-rate Xmax parameter set.
5 QUASI-HOMOGENEOUS MAXIMUM-
CAN DEGRADE ROBUSTNESS
In section[4] we showed how gradient flow on a quasi- sosii-hooogeeeuus model will implicitly minimize the norm of only the highest-rate parameters. To explore the implications that this bias has on func- tion space, we will consider simple problem where analytic solu- tions exist. We will analyze the binary classification task of learn- ing linear classifier w that separates two balls in Rd. Consider a dataset that forms two disjoint dense balls B r) with centers at =N E R2 and radii r E R.+. The label y/s of a data point x; deter- mined by which ball it belongs to, such that y/ and y4 = -1 if v E B(-,,,), r). We assume | = 1 and that r <1 to ensure linear separability. We measure the quality of a classifier by its robustness, the minimum Euclidean distance between the de- cision boundary {I Rd (w, z)) 0} and the balls B( See Fig. for depiction of the problem setup.
B(+p.)) r)
if E (u,rr)
B(-).r)
2 O.
Figure 3: An illustrative ex- ample. A 2D depiction of the binary classification task of learning a linear classi- fier w to separate two balls B(+,, The robustness 1(w) is measured by the min- imum Euclidean distance be- tween the decision boundary and the balls.
We will consider two parameterizations of linear classifier, that is homogeneous fnom (I; 0) = Σ; 0,x; and one that is quasi- D; homogencous fquass hom (x; 0) = E, j=1 Ozy)az; where D;
for the first m-coordinattss and D; 1 for the last (d - m)- coordinates. For the quasi- muusi--hmogeneouu model, the parameters as- sociated with the first m-coordinates are the Amax parameters. Let
P E Rdxd be the projection matrix into the subspace spanned by the first m-coordinates, P1 I- P be the one into the last (d-m)- coordinates, and Pa := ||P1μ0||| be the norm of μ projected into this subspace. As long as the radius r > Pu. then the conditional separability assumption of Theo- rem 4.1 is satisfiedd) Applying Theorem 4. we can conclude that for appropriate initialization fhom and qusssi /quasi-hom hom converge to the linear classifiers defined by the following optimization problems respectively,
min ||m|| s.t. y()) (w,, xt) 2 Vo E B(+u,r)
(3)
wERd
min
Pw|l s.t. g(x) (w. x)) 2 Yo E B(+,r)).
(4)
#EER
Each of these two optimization problems is convex and has a unique minimizer, which we can derive exact expressions for by considering the subspace spanned by the vectors pμ and Piμ.
Lemma 5.1. !f separability (r < 1) and conditional separability (r > p,)) hold, then Eq. 3 and Eq. have unique minimizers, Whom and W guuasi hom respectively, which satisfy,
1 1- r 2p2
Whom OK ue
W Uquasi homm O
V
Pk + r 1P Pb
(5)
"For all to E IRd that separate the two balls B(+,,r), ||Pw|]] > O. Thiis problem does not have local minima, but it does have saddle points.

---

Published as a conference paper at ICLR 2023
such that the robustness of these optimal classifiers is
[Whhom) r, I( (WQuasi-hom) /1 11 p (V
Pf.
(6)
From these expressions is easy to confirm that ((Uquasi hom) I [(ham) for all Pp < 1. For a fixed Pu. the gap in robustness between the homo- geneous and quasi-homogeneous models increases r + Pp- These expressions demonstrate that the quasi- homogeneous maximum mamggnn bias can lead lution with vanishing robustness in function space. To confirm this conclusion, gradient flow and keep track of the classifier to and ro- bustness ((w) for the models, while sweeping the ra-
Normalized Classifier w/|w|
1.00
0.75
0.50
W2
0.25
W3
train fhom and Squsi hom hom with
0.00
dius from Ps. to 1. As shown in Fig. 4 we see a sharp drop in the highest-rate parameters (Wi) and the robust- ness of the quasi-homogenese while for the homogeneous model, the parameters are sta- ble and the robustness is linear in expected from Lemma (5.T)
0.00
0.25
0.50
0.75
1.00
Radius
model as r P= 0.5),
1.00
Homogeneous
Quasi-Homageneeus
Theorem 4,1
(tw) K(w
0.75
Robustness
So far we have restricted our analysis to the setting Pu. such that we can be certain the conditional separa- bility assumption is met. But what happens to the per- formance the guasi-homogeneous model below this threshold S Pp? As shown in Fig. it appears that the model learns to discard the highest-rate parameters they unnecessary and the maximum-margin bias continues on the resulting sub-model. In Fig. 4 when 0.5, the second highest-rate parameters (w2) for the quasi-homogeneous model begins to collapse and the ro- bustness curve repeats another swell, eventually collaps- ing again when r = 0.25. Based on this, we conjecture stronger version of Theorem [. without the conditional separability assumption. This conjecture is very similar to an informal conjecture discussed in Nacson et al. (2019a) for ensembles of homogeneous models.
0.50
0.25
0.00
0.00
0.25
0.50
0.75
1.00
Radlus
Figure 4: Asymmetric maximum- margin can collapse robustness. Tracking the elements of classifier w and its robustness l(w) for ho- mogeneous and muasi-homogeneous model, trained by gradient flow on the binary classification problem in R for a sweep of radii r. As predicted by Lemma [.1] for the homogeneous model the classifier w x μ and ro- bustness is linear in r, while for the quaii-homogeneous model the highest- rate parameters and the robustness collapses when value of μ = [0.87, 0.43. 0.25 and A [1, 0.1]. See App. for experimental details.
Conjecture 5.1 (Cascading Minimization). Under as- sumptions Al to A6, there exists a À E R4 and an a e R such that vo poo ((t)) is a firstorrdrr KKT point of the optimization problem:
minimize
=11011245
Pp. 0.5. The
subject to
(1 0) 2 Vi E
0 Ay > X
where 15 is diagonal matrix whose entry (4z)a h is if = and 0 otherwise.
As shown in Fig. 4 find evidence of cascading minimization of the first and then second highest-rate parameters as the radius drops below the respective thresholds that make these parame- ters necessary.
A MECHANISM BEHIND NEURAL COLLAPSE
In this section, we move away from linear models and consider the implications the quasi- homogeneous maxinum-margin bias has in the setting of highly-expressive neural networks used
$If we consider higher-order homogeneous models, such as deep linear network, then the resulting maxi- margin hias would prefer sparse solutions, which could erode the robustness.

---

Published as a conference paper at ICLR 2023
in practice. We identify that for sufficiently expressive neural networks with normalization layers, the asymmetric norm minimization drives the network to Neural Collapse, an intriguing empirical phenomenon of the last layer parameters and features recently reported by Papyan et al. (2020). In their paper, they demonstrate that the following four properties can be universally observed in the learning trajectories of deep neural networks once the training error converges to zero: (1) The hast-hidden-layer feature vector converges to single point for all the training data with the same class label. (2) The convex hull of the convergent feature vectors forms a regular (C L centered at the origin, where C' is the number of possible class labels. (3) The last-layer weight vector for each class label converges to the corresponding feature vector up to re-scaling. (4) For a new input, the neural network classifies it as the class whose convergent feature vector is closest to the feature vector of the given input.
A considerable amount of effort has been made to theoretically understand this mysterious phe- nomenon. HHan et al. (202T); Poggio & Liao (2019); Mixon et al. (2022); |aangamani & Banburski- Fahey| (2022) studied Neural Collapse in the setting of mean-squared loss and Fang al. (2021):
Tirer & Bruna (002)); Weinan & Wojtowytsch (2022); Zhu et al. (202T): Ji et al. (2021) introduced
toy models to explain Neural Collapse in the setting of cross-entropy loss. These toy models are optimization problems over the hast-hidden-layer feature vectors and the last-layer parameters, but not including parameters in the earlier layers. Many of these works introduced unjustified explicit regularizations or constraints on the feature vectors in their model. recent work, [J et al.] (202T). showed how gradient dynamics on the space of the last-hidden-layer layer feature vectors and last-layer weights, without any explicit regularization, would lead to Neural Collapse as a result of the implicit maximum-marghn bias. However, the real gradient dynamics of neural networks happen in the space of all parameters of the model, and hence it is not clear how an implicit bias that leads the model to Neural Collapse, can be induced by the parameter gradient dynamics.
In this section, we show that the parameter gradient dynamics of any present-day neural networks can universally show Neural Collapse as long as they are sufficiently expressive, apply normalization to the last hidden layer, and are trained with the cross-entropy loss. Our theoretical analysis is based on the regularization by normalization and the quasi-homogeneone maximum maximum-margiin bias. Note that in Papyan et al. (2020), all the neural networks showing Neural Collapse are trained with the cross-entropy loss and have normalization.
Specifically, we consider the C-class classification model fe(z) hxx, 8*) + be where the last layer weights We E Rd and bias be for e E [C] and the last-layer feature h(z, 8') E Rd. The feature vector hxx 0') ") is obtained with layer normalization [o] and therefore satisfies
Σ hh 0, Σ h3(00,0) -1 Vi E [m].
where (Mi, y:)ss is the training data. This model is quasi-homogeneous with for the we and be, and À = 0 for parameters in the earlier layers 0', Thanks to this muasi-homogeneity, our result for multi-class classification tasks (see App. [H] reveals that the rescaled parameters converge to first-order KKT point of the following optimization problem:
min (10,b,81)
|wee? + 1612 s.t. min 1E ml
(wy,)) M,,,, 0') + by, max CFU
0') + be) 2 1. (8)
-E|O]
We further make the following assumptions on expressivity and data distribution:
* A8 (Sufficient Expressiviry). For any {(2,, h.)ke( satisfying Σ,(),, 0 and
E [m), there exists 0' satisfying h(r, 8') W for any E [m]. A9 (Existence of All Labels). For each class [C], there exists at least one data point in {(z W))eee whose label y; belongs to c.
Σ (M,)
=1 =1
The first assumption is to eliminate the possibility that any parameter configuration 0' cannot realize Neural Collapse. Under these assumptions, the global minimum satisfies Neural Collapse:
A regular (C -imimple the convex hull of C points where the distance hetween any pair is the same. Papyan et al. 2020) refer to this simplex centered at the origin as general simplex Equiangular Tight Frame. Here we layer normalization, but similar theorems would hold for other normalization schemes, such batch normalization.
8

---

Published as a conference paper at ICLR 2023
Theorem 6.1 (Neural Collapse, short version). Under assumptions A 8 optimum of satisfies the four properties of Neural Collapse
A9 and d 2 C, any global
Note that we do not exclude the possibility that Eq 8 has saddles or local minima. Therefore, depending on the ini- tialization of the learning dynamics, it may end up with those sub-optimal first-order KKT points, which may not show Neural Collapse.
Eq.
Essentially, the proof of Theorem 6. relies on first re- laxing Eq. 8 to the optimization problem
min (M)
S.L. min Le 2 1,
(9)
Figure 5: Geometric intuition. An il- lustration Eq. The black circle rep- resents the origin, the solid lines repre- sent the class vectors W., and the dot- ted lines represent the distance Le- In- tuitively, minimizing the lengths of the solid lines while maintaining mini- mum lenghh of the dotted lines will re- sult in a regular simplex centered the origin.
eE[C]
where Le is the minimum distance from we to the (C-2)-
simplex formed by the convex hull of {we bee With accordance to our geometric intuition, the mini- mizer of this optimization problem is regular (C - 1)- simplex. See Fig. 5 for a visual depiction of this relaxed optimization problem and App. G for the details of the proof.
7 CONCLUSION
In this work, we extend and generalize long line of literature studying the maximum marggn bias of gradient descent to quasi-homogeneous networks. We show that after reaching a point of sep- arability, the gradient flow dynamics are driven by competition between maximizing the margin in function space and minimizing the Amax-Seminorm in parameter space. We demonstrate, with a simple linear example, how this strong favoritism for the highest-rate parameters can degrade the bustness of quasi- homogeneous models and conjecture that this process, when possible, will reduce the model sparser parameterization. Additionally, by applying our theorem sufficiently ex- pressive neural networks with normalization layers, we reveal a universal mechanism behind Neural Collapse. Here we propose some future directions for this work.
Discretization effect. In this work, we only considered gradient flow, but generalizing the theo- retical results (stochastic) gradient descent is an important future step. In particular, is well understood that the discretization effect introduced by finite learning rate has empirically measur- able effects for parameters that are cale-invariant, such as those before normalization layers. While gradient flow would predict the norm of these parameters to be constant through training, gradient descent predicts that they monotonically diverge, as demonstrated by Kunin et al. (2020). Thus, extending our results the setting of gradient descent could reshape Theorem
Optimality of convergence points. We are only able to guarantee by Theorem 4.1 that the learning dynamics will converge to a first-order KKT point of the constrained optimization problem, but not whether this point is locally or globally optimal. Better understanding the landscape of this opti- mization problem and determining when stronger statements
be made is promising direction for future work. Works such as Chizat & Bach (2020); Ji & Telgarsky (2020); Vardi et al. (2021); Lyu al. 202T) have made progress in this direction for simple homogeneous networks and could provide a strategy for investigating more complex quasi-homogeneous models.
Influence of initialization. A major limitation of analyzing the maximum-margin bias of gradient flow is that the dynamics in this terminal phase of training are slow to converge or only become evident at extremely unpractical training loss levels. Motivated by this limitation, WWoowwothh et al. (2020) and Moroshko et al. (2020) studied the gradient flow trajectories for diagonal linear networks and showed that there is a transition from a "kernel" regime to "rich" regime controlled by the scale of the initialization and the final training loss level. Extending this analysis to guasi-homooeneeon networks would be a valuable future direction.
Impact on performance. An important takeaway from work is that the maximum-marge bias can actually degrade the performance of quasi-homooeeeeon model. The benefit depends on the parameterization of model and its relationship to the geometry of the data. Better understanding this interaction could be essential for diagnosing performance gaps of modern neural networks and provide route towards designing robust architectures.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We thank Kaifeng Lyu, Ben Sorscher, Daniel Soudry, and Hidenori Tanaka for helpful discussions. D.K. thanks the Open Philanthropy AI Fellowship for support. A.Y. thanks the Masason Foundation for support. S.G. thanks the James S. McDonnell and Simons Foundations, NTT Research, and an NSF CAREER Award for support while at Stanford.
REFERENCES
Lenaic Chizat and Francis Bach. Implicit bias gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference Learning Theory, pp. 1305-1338. PMLR, 2020.
Francis H Clarke, Yuri Ledyaev, Ronald Stern, and Peter Wolenski. Nonsmooth analysis and control theory, volume 178. Springer Science & Business Media, 2008.
Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D Lee. Stochastic subgradient method converges on tame functions. Foundations of computational mathematics, 20(1):119- 154. 2020.
Joydeep Dutta, Kalyanmoy Deb, Rupesh Tulshyan, and Ramnik Arora. Approximate kkt points and proximity measure for termination. Journal of Global Optimization, 56(4):1463-1499) 2013.
Cong Fang, Hangfeng He, Qi Long, and Weijie J Su. Exploring deep neural networks via layer- peeled model: Minority collapse in imbalanced training. Proceedings of the National Academy of Sciences, 118(4))=2110309111 2021.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. Advances in Neural Information Processing Systems, 31, 2018.
XY Han, Vardan Papyan, and David L Donoho. Neural collapse under mse loss: Proximity to and dynamics on the central path. arXiv preprint arXiv:2106.02077 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Wenlong Ji, Yiping Lu, Yiliang Zhang, Zhun Deng, and Weijie Su. An unconstrained layer-peeled perspective on neural collapse. arXiv preprint 10.02221 2021.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv: 1ato.0200.0222 0..02022. 2018
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference on Learning Theory, pp. 1772-1798. PMLR, 2019.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems, 33:17176-171888 2020.
Daniel Kunin, Javier Sagastuy-Brena, Surya Ganguli, Daniel LK Yamins, and Hidenori Tanaka. Neural mechanics: Symmetry and broken conservation laws in deep learning dynamics. arXiv preprint arXiv:2012.04728. 2020.
Thien Le and Stefanie Jegelka. Training invariances and the low-rank phenomenon: beyond linear
networks. In International Conference on Learning Representations, 2022. URL. https:// openreview net. fortmm ietrrummiixxee X
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv:1906.0580 2019.
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 34:1 14:19978-12991, 2021.
10

---

Published as a conference paper at ICLR 2023
Dustin G Mixon, Hans Parshall, and Jianzong Pi. Neural collapse with unconstrained features. Sampling Theory, Signal Processing, and Data Analysis, 20 2022.
Edward Moroshko, Blake E Woodworth, Suriya Gunasekar, Jason D Lee, Nati Srebro, and Daniel Soudry. Implicit bias in deep linear classification: Initialization scale vs training accuracy. Ad- vances in neural information processing systems,
2020.
Mor Shpigel Nacson, Suriya Gunasekar, Jason Lee, Nathan Srebro, and Daniel Soudry. Lexico- graphic and depth-sensitive margins in homogeneous and non-homogeneous deep models. In International Conference Machine Learning, pp. 1683-4692. PMLR, 2019a.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3420- 3428. PMLR, 2019b.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with fixed learning rate. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 3051-3059. PMLR, 2019c.
Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40): 24652-24663, 2020.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Tomaso Poggio and Qianli Liao. Generalization in deep network classifiers trained with the square loss. CBMM Memo, 2019.
Akshay Rangamani and Andrzej Banburski-Fahey, Neural collapse in deep homogeneous classifiers and the role of weight decay. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4243-4247. IEEE, 2022.
Saharon Rosset, Ji Zhu, and Trevor Hastie. Margin maximizing loss functions. Advances in neural information processing systems, 16, 2003.
Carl P Simon, Lawrence Blume, et al. Mathematics for economists, volume 7. Norton New York, 1994.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19 (1):2822-2878, 2018
Tom Tirer and Joan Bruna. Extended unconstrained features model for exploring deep neural col- lapse. arXiv preprint arXiv:2202.08087, 2022.
Gal Vardi, Ohad Shamir, and Nathan Srebro. On margin maximization in linear and relu networks. arXiv preprint 10.00733,, 2021.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Courna- peau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. Nel- son, Eric Jones, Robert Kern, Eric Larson, C J Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, António H. Ribeiro, Fabian Pedregosa, Paul van Mul- bregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272 2020. doi: 10.1038/s41 192--099-0686--
Colin Wei. Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, 32, 2019.
11

---

Published as a conference paper at ICLR 2023
E Weinan and Stephan Wojtowytsch. On the emergence of simplex symmetry in the final and penul- timate layers of neural network classifiers. In Mathematical and Scientific Machine Learning, pp- 270-290, PMLR, 2022.
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pp. 06335-373.. PMLR, 2020.
Tengyu Xu, Yi Zhou, Kaiyi Ji, and Yingbin Liang- When will gradient methods converge max- margin classifier under relu models? Stat, 10(1):e354, 2021.
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. A unifying view implicit bias in training linear neural networks. arXiv preprint arXiv:20/0002501, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
Zhihui Zhu, Tianyu Ding, Jinxin Zhou, Xiao Li, Chong You, Jeremias Sulam, and Qing Qu A ge- ometric analysis of neural collapse with unconstrained features. Advances Neural Information Processing Systems, 34:29820-2900 29834, 2021.
12

---

Published as a conference paper at ICLR 2023
CONTENTS
Introduction
Background and Related Work
Defining the Class of Quase--Hooogeneuus Models
Homogeeens Maximum-Margin Bias
4
Qusoe-Homogeneous Maximum-Margin can Degrade Robustness
Mechanism Behind Neural Collapse
7
Conclusion
More Details on Quasi-homogeneous Models
14
The Consistency of Theorem 4.1 and the Proper Choice of A
17
Limitations of our Current Assumptions
24
Proof of Lemma 4.1
25
Proof of Theorem 4.1
27
Proof of Lemma 5.1
32
Proof of Theorem
34
Extension to Multi-class Classification
39
Experiment Details
41
13

---

Published as a conference paper at ICLR 2023
A
MORE DETAILS ON QUASI-HOMOGENEOUT MODELS
A A-normalization. Here we provide more details on A-normalization as discussed in section The A-normalized parameters 0 are given by
(E T ( .1..0,..........................
pm)
s.t. |011%
The value of r is implicitly defined through the constraint ||013 cases does an explicit expression for exist. For example, in the homogeneous setting when I, as would be expected.
1. Only in a select number of
т = l and 0
Lemma A.1. For all E Th such that |0||A > 0, the A-normalized parameters å are unique.
Proof. Proving uniqueness of is equivalent to proving uniqueness of T. For given 0 and A, then T T= ==oog11//3 where z the positive root of the polynomial Σ, X,0? - O. The coefficients o. 2 0 are non-negative, and because ||0]| > O, we know there exists at least one positive coefficient X,0 > O. Thus, there is exactly one sign change in the coefficients of this polynomial, which by Descartes' rule of signs, implies the polynomial has exactly one positive root, and thus unique.
Locally Lipschitz Quasi-homogenenn models. To apply our analysis and Theorem 4.1 to many deep neural network settings including those with non-smooth ReLU activations, we here consider quasi-homogeseeus functions with local Lipschitz property. For such functions f(0) IRd + R, Clarke's subdifferential 8g defined as follows Clarke et al. (2008).
Definition A.1 (Clarke's 's subdifferential).
(0) = conv lim Vof (0c): lim 0g = 0, f is differentiable at 0g k+000
(10)
k+000
Similar to Theorem B.2 in Lyu & Li (011)), we can show that f(0) satisfies scaling property and version of Fuler's theorem.
Lemma A.2. Let f(0) Id + R be locally Lipschitz and N-quasi-homogeneous S satisfies the following scaling property:
(g = {ealt- h 08,(0))
(11)
for any 0 and 0 E Rd.
Proof. For any sequence (0x tEEN on which f is differentiable and converging to 8, {Va (fx)
converges to via(() (f) and f is differentiable on this sequence, whose derivative is given by
Vof(Wa(0s))= = = aee- A(e-a((0))
a
= (e0(1-A)
00
00
ae
(9.)
(Uw)
(o()))
where the last expression equivalent to (Ox) (v (0x))eeN on which is differentiable and converging to via (0), JKEN converges to 0 and f is differentiable on it as well, with the above scaling property. Hence,
Conversely, for any sequence
lim Vol (0x) lim 0g (0), is differentiable 0g 10000
k0000
a(a(l--)) lim Vol (0x): lim 0s 0, is differentiable at 0g A=+00
Thus taking the convex hulls of both sets, and by the commutativity between conv and the linear operation ea(I-N), we conclude that Eq holds.
By further assuming that f(0) admits chain rule (See Davis al. 2020 Lyu & Li (2019) for its definition), we can show that ff satisfies a version of Euler's s theorem, similar to the case of homogeneous functions.
14

---

Published as a conference paper at ICLR 2023
Lemma A.3. If (0) Rd - IR is locally Lipschitz admitting chain rule and A-quasi- homogeneous, then it satisfies a version of Euler's 's theorem, i.e., for all 0 E Rd,
(h. A0) = (() for any h E (0).
(12)
Proof. Since f admits a chain rule, there exists a > such that f(c*A0) is differentiable with respect and
d f(e = = deaso) da (()) f(ca00) = - A0)
(g. eard e0)
da
do
for any g E 0g (c) Therefore
1(0) = a d
da
By Lemma A.2 for any h E (f), we can find g E ( such that
(0, = (e (e-ate (a(-a()) g.0) f(0).
The properties above immediately implies that any feasible point of optimization problem (P) sat- isfies Mangasarian Fromovvtz constraint qualification (MFCQ) condition, which implies the first- order KKT condition necessary for the optimality.
Lemma A... Any feasible point of optimization problem (P satisfies Mangasarian- Frommvvitz constraint qualification (MFCQ) condition, i.e., there exists v R such that for all i E [n]] with (r,
{u, h) > foror any h E (y: 0)
Proof. Notice that for any h E 0g (y, fxx, 0) - 1), there exists H/' 0g. [2,,, 0) such that (A0,
ya (A0, N'). Hence, choosing A6, by Lemma A.3
(A0, h) ys (A0, L0,, M) = 2s Vx 0) 1>
Ensembles of homogeneous models. In Nacson et al. (2019a), they considered the maximum- margin bias of gradient descent for non-homogeneous models that can be expressed as finite sums of
models different orders. In particular, for some K E N, they consider functions (æ; 0) that can be expressed as
f(x; 0) = Σ (1; 0k),
(13)
k=
where 0 = [#1..... 0x] and (x;; 0x) is ag positivve homogeneous such that 0 < a1 <... a-- While this class of models is not homogeneous because of the varying orders of the sub-models, quasi-homogeneous. If we choose A such that for all parameters in 02 the value of X 0 then f(x; 0) is A-Quasi-Homoggneuuss. Therefore, the theoretical results discussed should align with the results discussed in Nacson et al. (2019b) for the setting of ensembles of positive-homogeneee
- this work
models. Indeed Theorem [4 and Conjecture 5. agree with analysis stated their work that "an ensemble on neural networks will aim to discard the shallowest network in the ensemble", which is the sub-model with the highest-rate parameters.
While all ensembles of Dositive-homogeneee homogeneous models are ensembles. Here we provide short list of quasi-hhmoogneous models that cannot be written the form of Eq. [3]
models are quasi-homogeneous, not all quasi-
Deep fully connected network with biases. Consider again the two-layer fully connected network with biases discussed in section 3
f(r:0) = w²o
Σ wtas +b2 b b²
15

---

Published as a conference paper at ICLR 2023
If we arrange terms such that f()) (z: b²) = ba and (2; w/ b', ==)====>- w²o aa + b'), then we can express fa; 0) f (a;; b2) + f(2) (x; w bb w²), which is ensemble of two positive- homogeneous models with 01 = and
= 2. However, notice that if we consider a third layer with parameters w and b², then this decoupling of the network not possible unless some of the sub-models share parameters, preventing us from expressing / (a;; 0) in the form of Eq. 13 All fully connected networks with biases, and depth greater than two, are quasi-homogeneous models, but not an ensemble of hontoieeoo models.
Networks with degenerate As presented carlier, for huusi-homogenouus networks with residual connections normalization layers, we can choose A to have zero values. Thus, even if these networks could decoupled into sum sub-models that don't 't share parameters, the sub-models associated with the zero À parameters would not be hesitive-homogeneuus.
In summary, the results presented this work coincide with the results presented in Nacson et al. (2019a) for ensembles of positve-hoomoeneous models, but also apply far general class of non-homogeneous models.
16

---

Published as a conference paper at ICLR 2023
B THE CONSISTENCY OF THEOREM 4.1 AND THE PROPER CHOICE OF A
As briefly discussed in section 4 for a huage-homo function f. the value of A, and the Amax parameter set, is not necessarily unique and therefore one may think Theorem 1.1eem44..look looks inconsistent. However, the conditional separability (A7). which is required to apply Theorem 4.1 removes this possibility. Here provide some insightful examples and then provide complete proof.
Examples of quasi-homogeneous models with non-unique A. We here clarify through examples how our theorem can be consistent with cases where the model f(0) is quasi-homogeneous with multiple choice of A due to additional symmetry.
A linear model with two parameters. We consider the following model,
f(x; 01, 02) 0,02a.
This is quasi-homogeneee with (A1, = (1-25, for any & [0, 1/2]. There are three possible sets parameters with largest value:
f > 1/3, 0, has the largest À value.
[ 1/3, 02 has the largest À value.
. [ 1/3, 0, and 02 have the same À value.
one naively applies the theorem to these cases, they might think that the learning process converges to a separable solution minimizing of for the first case, 82 for the second case, and 0f + 0 for the latter case, which is inconsistent. However, the first two cases do not satisfy the conditional separability assumption. This is because we can make [0,] or [02] as small as possible while fixing the function itself. Therefore the correct choice of should be (A1,Ao)
(1/3, 1/3).
Two-layer quadratic activation with biases. For the sake of simplicity, we assume that all the layer widths are one, i.c. the model is given by four scalar parameters as follows:
f(; 0) = 0g (01æ 02)² + 04-
We can easily generalized our argument to wider networks. This model is quasi-homogeneous with the following choices of A:
(21, λ3, A4) = (E - 1) for any & E [0.].
Again, there are three possibilities.
If E 0, 0z have the largest À value.
* If & 10,1 02 has the largest À value.
I = 1/2, 01, 02, 04 have the largest value.
All of the cases can satisfy the conditional separability condition. For the first case, our theorem tells that the gradient dynamics minimizes 6 + 62. However, by making Q and 02 large, we can make Og arbitrary small without changing the output, and hence, it is equivalent to minimizing 0g alone. This argument also holds for the third case. Thus, for all three cases 0f is the objective function for the minimization.
neural network with normalization. We consider the following model,
fx:;
Σ w F (h(0', ,))) b. CE|C]
where we E dRdd E RCC are the weight and bias on the last layer, O' is the set of parameters in the earlier layers, and h(0', .x) E Rd is the feature vector on the last hidden layer, which we assume is homogeneous" i.e., ed h((':
R with certain X 0. Fnom a normalizer of the feature vector h1(6:; so that the normalized feature vector Fnom (h(f': x)) hieaX 0';z) for any a E R. In this setting, possible choices of values are for the last layer parameters and for parameter 0
h(caX 2)) for any
is invariant under scaling transformation of 0', i.c.. h(0'=z)
where & is an arbitrary neganege number. Thus there are at least following three possible sets of parameters with largest
Our discussion here works with quasi-homogeneity, hut assume homogeneity here for simplicity.
17

---

Published as a conference paper at ICLR 2023
If Ş 1, the parameters 8 in the earlier layers have the largest A.
* If Ç 1, all the parameter have the same value of A.
I & < 1, the last-layer weights and biases have the largest A.
In the first case, by the scale invariance of xx), we can make ||0']| as small as possible while not changing f(0. 2)). which implies that it does not satisfy the conditional separability condition. On the other hand, in the second case, it satisfies the conditional separability, since there need to be non-zero last-layer weights bias correctly classify data points. By applying the theorem, we can conclude that the learning process converges to minimizer of E. [| + |]]] + |/0'112. However, we can minimize ||0']| as much as we want, while fixing f(0:z), and hence is equivalent to minimizing E. |/ + |[6]] . In the third case, we can apply the theorem as well, which means that the learning process converges to a minimizer of sum of >. ||w=|| + ||611
In summary, while the choice of A is necessarily unique because of intrinsic symmetries in the parameterization of the model, the set of highest-rate parameters well defined by the constraints imposed by the conditional separability assumption. This makes Theorem 4.1 well defined.
A complete proof of uniqueness of the resulting optimization problem As we discussed above going through three examples, we can identify which we should choose, which Amax parameters we should choose, solely by analyzing the model, independent of the data set. In this section, we generalize the previous discussions on examples and prove that the resulting first-order KKT condition derived from Theorem 4. is unique, even if the model itself is quasi-homogeneous with multiple choices of scaling parameters A. Note that the following argument is independent of the data and properties derived here in this section is solely the properties of the architecture of the model itself.
In the following argument, to simplify proof, we assume [(; 0) is differentiable with respect to in addition its continuity. Let S Rd the set {Aileed with which the model satisfies the quasi-homogeenity. i.e..
S = E f(z;0) 0) >=quashhomoeencous))
Definition B.1. A called proper if there exists separable data set ((r,, Willet with which the model satisfies and (x; 0) is bounded in {0 E Rd [|0[]Amme 1}.
Definition B.2. Let X2 X2 S proper. We say they are equivalent terms of first-order KKT conditions, for any data set ((x, (:) the sets first-order KKT points for the following two optimization problems
; 1101
minimize
Amax
(14)
subject to (x,( 21 Vi Viel [n]
equivalent with & = 1,2.
We are going to prove the following theorem in this section.
Theorem B.1. All proper points in S are equivalent in terms of their first-order KKT conditions.
Before going to the proof of this theorem, we prove several lemmas for preparation.
Lemma B.1. S is convex.
Proof. Let X3, X2 S. It suffices to show that for any E [0, 1]. ax + (1 a){2 E S. By the quasi-homogeneity of f(;; 0) with respect to A and for any 3 B R.
f(r; Mass (1-a)==((--)))))))))) e--a3 a3 f(x; agxt 0) = e @ f(r; 0).
Hence, f(x:0) is ax as (1 3 quasihomogeeeouus, i.e, at (1 - a)X² E S.
Consider non-empty line segment in S
L : (v E Rd Çt. + 2 with some / / RR S.
(15)
18

---

Published as a conference paper at ICLR 2023
where S, A E Rd. This set is connected since S is convex. Moreover, it has at least single end point, because L E R Hence, without loss of generality, we can assume that X the end point and takes non-negative values. We define a set of indexes I C [d] by
T= fie [d] X 0, L, > 03.
Furthermore, for X E S, we define MM by
My = field [d] : = max 23}-
jE(d]
Lemma B.2. I is non-empty, if L contains at least two different points.
Proof. Suppose I is empty. In the following, we will show that there exists < 0 such that (t) = + X" S. Since this contradicts with the fact that X an end point of L, we conclude is
non-empty.
Since I, contains least two different points, there exists 1 0 such that A v(it) E L. By quasi-homogeneity of the model with respect to X and A for any a, E R,
f(z; ((=;)0)0)))) 0) = f(z; (100 0) = f(x; # ea c
= """""" f(x; (x;;
(16)
Since we assume I empty, for any E [d] such that S, # 0, Xp > 0. By the continuity of y())
with respect to f, this means that there exists an open neighborhood of t = 0 where (t) > 0 for
any E [d] such that G * For the other indexes, i.e. i E (d) such that G 0, clearly (1) 2
in the open neighborhood. Therefore, in the neighborhood, y/ (t) 2 0 for all E [d]. In particular,
there exists < 0 such that ytt, 2 0 for any i E [d]. Combining this fact with Eq 16 we conclude that there exists é < 0 such that y(t) E S. By contradiction, / is non-empty.
Lemma B.3. For any proper element X E L/{X")
Mx n + 0,
(17)
and hence
max X t" max Co. xE[d]
(18)
VE
Proof. Since X is proper, there exists data set with which the model satisfies the conditional separability, i.e., there exists x > O such that all the parameter values {0: Hit which separate the data satisfies ||o||n, > K. Let {0] heed be a parameter values separating the data. By the continuity of the model, without loss of generality, we can assume that 07 * for any E [d].
In the following, we show Mx I A ( by contradiction. Suppose Mx. n n = 0. We derive the contradiction by showing that there exists parameter value 8 which correctly separates the data, but breaks the conditional separability condition with A*. This clearly contradicts with the fact that X is proper.
We consider the following transformation
0+ -ay(000
with some a This transformation does not change (0) her, but other parameters are scaled down to 0; + e -a 0r. Then Eie(d/r (e-ea 0,)² can be arbitrarily small by taking a + co. (Notice that here we exploited the fact that if XO 0, since X; > 0 and |0; 0 for any E 1,
X 0 for any E [d]/T.) On the other hand,
||e
(0 ay(0 0 Il
Σ 15 000000003 > Σ (e my)00) vE(d]
NEl
is lower bounded by a positive constant. (Here we exploit the fact that is non-empty by Lemma B.2) Hence by further transforming the parameter
-0 g* - -= = e- -BA cov((0)
19

---

Published as a conference paper at ICLR 2023
with proper choice of B O, we normalize the A seminoom ||0" 1 while keeping Eie[d// X (01)² arbitrarily small. In particular, it is smaller than A with large enough a > 0. By assumption, we know [d]/T= argmax,e|d X, and hence,
10
Σ KE(d)/T
x100) <K.
By the muaii-homogeneity of the model, the model classifies the data set correctly even with this transformed parameter 0'. However, this means that it breaks the conditional separability condition, which contradicts with the fact that X is proper. Therefore, Mx- n I +
Lastly max Xo l" maxier Sa can be derived as follows:
max A VE[d]
max X = t" max Sz.
XEI
RE1
Lemma B.4. For any proper element X E L/{X"),
Mx n ([d/IT) +
Proof. Suppose Mx- ([d/I) ie., Mx I. Let {0; hield be a parameter values separating data. Notice that there exists E [d// such that Xς + 0 and 0 + Otherwise,
ef(z; 0") = fax; e v(t" v(t)) 00) f(z;e 2u(e' (2) e² f(z;0"),
which is a contradiction. We denote such an index by j. We consider the following transformation
8' e By(tt)
for some 0. 3 0 here is chosen to satisfy ||0' IlA 1. By the quasi-homogeneity of the model, the model still correctly classifies the data with this transformed parameters. By taking a arbitrarily large, (e*)(0)0"), en 0- becomes arbitrarily large, and thus 3 needs to be arbitrarily large to renormalize the A A--seminorm. Therefore for any I, 0 - -S. 0f can be arbitrarily small. Therefore, we can find a large enough a such that
|10'11
Σ
xT S Σ 12000) <x
iEargmin Ag
This contradicts with the fact that X is proper. Therefore, Mx- n ([d]/T) +0.
Lemma B.5. If there exists proper X E Int S, it is unique, where Int S is the interior of S.
Proof. Suppose there exists two different proper point A1, Int In the following argument, will show that X X², which is contradiction. We consider a line including the two points X and Xz. Without loss generality it can be represented as
= {y E RS
<l X with some 2 0),
(19)
where < x2 A and X is an end point of this line. Let X" = y((*) be a proper point in the interior of the line. X can be either 2 or X2. In the following, we will derive an explicit formula which uniquely determines t", implying X = X². By applying Lemma B.3 we obtain
max x = 1" max G.
iE d]]
NE!
Suppose the line has the other end point fmax O. We apply Lemma B.3 again with this other end point, and we can derive the corresponding equality
X
(fimax
t*) max Ci, (EJ
where J C [d] is given by
J= [ [d] ((lmax)) 0, YF E T,,9 > 0).
20

---

Published as a conference paper at ICLR 2023
By comparing these two equality, obtain
maxieJ G
Imax-
max,eJ Se max Ca
This uniquely determines t" and hence =
Next, we consider the other case where L does not have end point other than X² Notice that
max & iEf
Sa- ae|d/1
(20)
This due to the following reason: Suppose there exists j E [d]/L such that Cj 2 maxier Çi- Since Ç 0, j & implies that X2 > Hence, y(t"); {s + X9 Xmaxo which is clearly
contradiction.
The inequality Eq 20 means that for any j [d/r,
{t 2 0: max yt), y(t),} = -1t/,00)
GE1
with some 1j 2 Hence
1" E
max y();
max v(),:) yeja//s (1 0: v()) > v(0i} 10,,,),,
iel tE[d]
where e' = maxje(d//t
In the region (t', oo), jr y(); C I, and hence by Lemma B.4 to & (t', oo). Hence t" t'. The uniqueness of t' implies that A = X²
The argument above shows that in any case X X2, which contradicts with the assumption that they are different. Therefore, the claim follows.
Lemma B.6. For any proper element X E S and any À E S,
min (): x < O, nEM,,
max (As {1 2 0. MEM
Proof. we show this by contradiction. Suppose there exist X, X E such that mingeM,- (A;-1;) > or max (A- < O. Let 8" be parameter values with which the model can separate data set. We consider transformation eor()) with
y(t) = t(x- -
with some a, E R. By quasihomogeneity of the model with respect to À and A we know that fx; )))()))))))) = e" f(; 0). By assumption, there exists E R such that (t) s 0 for any e My. This implics that (f(z; e0v()))) ||eav(0))]a;,.) < |10|| at E R} unbounded, which contradicts with our assumption. Hence, the claim follows.
Lemma B.7. Let X²,X² E S be proper. If the following two conditions are met, X and X2 are equivalent in terms of the first-order KKT condition.
Either minseM, at (A - X²) = 0 or maxiMM, (A) x3) = 0 holds for both l = 1,2
{i E My 2 = X²} = {i E Ma X1 =7]
Proof. Let = Eie My i = x² (i Maa X1 {?)). suffices to show that of the first-order KKT points of the following problem
minimize
10 max
(21)
subject to
H.f 0) 2 Vi E
21

---

Published as a conference paper at ICLR 2023
is equivalent to the set of the first-order KKT points of the following problem
minimize
A max 02
2
iEL
(22)
subject to
21 Vi [n]
0, =
Vi (Mx) U UMa)/L
for any data set {(rs, yi) he(ml for 1,2. Since the second optimization problem is clearly
restriction of the first optimization problem with some additional constraints, it suffices to show that any first-order KKT point of the first problem satisfies the constraint 0; = O for any (Mx² Mx)/L
To prove this statement, first we show that for it 1, and any E Idd one-parameter family of parameter values (O(a) := = --aaa"- E R} satisfies
d (z; (())) = 0 da
If da a= [|((a)lAa*.. 0, 0: = 0 for any E M2t/L.
The first point can be easily seen by the quasi-homogeneity of the model with respect to X and X² Indeed, for any a E I,
O(a)) f(; e an ca = e 0) [x;;0) 0):
Regarding the second point, first notice that for any i i I., Oc(a:) 0; for any a E TR and hence
d
[((())last
Amax
d
Σ (f()).
da a=
aa
/L
X < O for any i E Mat/I. and thus, unless 0: = 0 for any minieM, (1) - 23) = 0, A1 i e M2*/L,
d
07(a) =- Σ
a(4 x?)0? 00
da
a= M
iEM,,/L
On the other hand, if maxicM,
21 (A) - (1)= - A1- X2
0 for any E Ma LL, and thus, unless
0: 0 for any Mx+/T.
d
Σ o7(a) < O.
da a= LLM,
Therefore, in either case, the second claim holds.
Let a first-order KKT point of Eq with a KKT multiplier μ E IR.. The stationary condition along the one-parameter family ((a))
d 1
d f(z;; 0. Σ وزرر da la=0
[(a))
de o=
jE(m]
Hence by the two properties above with both 1, we obtain 0 for any E (Mx Therefore 0 is a first-order KKT point of 22
By exploiting all of the lemmas above, we are now going to prove Theorem B.I
proof of Theorem B.1 least either of X or X2 on the boundary as of S. Without loss of generality, we assume that X E aS. We consider a line segment in S
Suppose there exists two different proper points A 1² e S. By Lemma B.5
L (v(() E Rdd v(( = = X 0},
(23)
22

---

Published as a conference paper at ICLR 2023
where ( X2 R
We first consider the case where L has a single end point A We will show that X and X² are equivalent in terms of the resulting optimization problem, by applying Lemma B.7 Hence going to verify each condition required in the lemma.
Notice that the fact that L has single end point implies that Si for any i E [d]. Combined with Lemma B.6 this means that
min (A - 2/)
M
for = 1.2. Furthermore, clearly {i E Mx x = {3} = Mx This is because for any [d].
i {i E Ma² X { and
23 Gtt 2/.
where the inequality above hold as an equality if and only if j E {i E Mx : 1 = =3).
{i E Mx X = x {i E MA X = X
immediately follows from (i E MA X = { = Ma Hence by applying Lemma B.7 we obtain that A and X² are equivalent.
Next, we consider the other case where L has two end points. Let ((fmax) denote the other end point. Suppose X² is an interior point, i.e., X² # y(lmax). By exploiting Lemma B.3 we obtain
Mma
mmax max G (Imax - 12) max So X maxx &EJ
(24)
iEJ
where 12 is given by y(12) X and J [d] is given by
J = Uj E [d] y((max); = O, YE L,,
On the other hand, by applying Lemma B.6 at A know that there exists i E M2 such that < 2 Hence X 2 A = Amax This clearly contradicts with Eq 24 Hence, X2 = y
Lastly, we show that د and X² y((max) are equivalent in terms of the resulting optimization problem by applying Lemma B.7 Hence, we are going to verify the conditions required in the lemma. Since M,n Ss S by Lemma B.6 there exists j E Mx such that Sj S 0, and hence
X = X2 A3 mmmxx < X3 <
X1 Amax
By applying Lemma B.6 X2, similarly we obtain
A 1 X2 Max- Therefore
> X2 X
Suppose there exists E My such that Si > O. Then, \ = X X2 -2-32 Gilmax X2 < X2 max This is a contradiction, and hence max Çi S O. Combining this with Lemma O. Similarly, suppose there exists E M2² such that Si < O. Then, A max This a contradiction, and hence minGeM,2 Si =
B.6 maxiEM, Si = X + Sitmax <
A1
Let {i E Ma =}= = Then X
X 2 Hence (i MA : t X 22 Xmxx -Naxx Hence & E fi E Mş X!
Similarly if k E ii MA² A X?1- 1. A/ X?). Therefore
X2
E My : X = X2) = (i e M Ma : x7).
Now, all the conditions in Lemma B.7 are satisfied, and hence A and X2 are equivalent. In summary, regardless of the finiteness of the line L,, X and X2 are equivalent in terms of the first-order KKT condition.
23

---

Published as a conference paper at ICLR 2023
C LIMITATIONS OF OUR CURRENT ASSUMPTIONS
A While, many modern neural network architectures are A-quasi-homogenan models cannot represent models with non-homogeneous activations such as the hyperbolic tangent function or the sigmoid function. While these activation functions are less common in practice, it would be interesting if there exists a direction towards generalizing our analysis to models us- ing these functions. This could be of interest to the computational biology community as these monotonic activations that saturate are much more petogically-plausiiie then non- non-saturating homo- geneous activations. One route could be studying the properties of homothetic functions, which are monotonic transformations of homogeneous functions. This class of functions has the same ordinal properties of homogeneous functions and is used extensively in economics Simon et al. 1994)..
this class of
These assumptions are equivalent, up to order, to the assumptions presented in Lyu & 2019 and are all quite standard in the literature studying the maximum margin bias of gradient descent. The strongest of these assumptions is A4] which assumes the training dynamiis of the model are governed by the first-order ODE gradient flow. As discussed in section [ important future step would be to generalize our results to stochastic gradient descent (SGD). It is very possible that the hyperparameters of SGD, such the learning rate and batch size, play important role in determining the forces driving the limiting dynamics.
AZ A5
No. This assumption implies the convergence of the decision boundary and is equivalent direc- tional convergence for a homogeneous model. This assumption is necessary to show that the model's prediction is bounded on the normalized training trajectory (Lemma E.T and for a technical reason to show the alignment of dê dt and Ae (Lemma E.4p. While a necessary assumption, we expect that this assumption can be weakened by exploiting the argument in Ji & Telgarsky (2020), which was applied for homogeneous functions. This could be an important step for future work as it is possible to construct settings where gradient flow will violate this assumption. See Appendix J of of Li (219)) for an example of smooth homogeneous function where the limiting dynamics of gradient flow provably don't converge after normalization, but move along a circle. Another, more practical example, occurs for models where the residual block diverges. Because these parameters necessarily have À value of 0, then the normalized parameter i diverge as well. The divergence of residual block essentially means that the skip connection of the model is effectively negligible and does not play an important role in the classification. Thus, we believe that if the skip connections play an im- portant role for the classification task, then residual block does not diverge, and this assumption is satisfied. Additionally, like A7 this assumption restricts the possible proper values of A as discussed in App. B
N7 This assumption implies that Amax parameters play a role in the classification task. This is the strongest of the assumptions we introduce in our work. This assumption is restriction on the interaction of the parameterization of model and the dataset, and thus it is difficult to assert its validity for general settings, without directly modeling the data as in 3] That said, there are some standard settings where we can assert that this assumption is always true. First, it is trivially true that for a homogeneous model where [[]] = ||θ|| that A7 is always true. Additionally, for ResNet-18 model, then A
all models with batch normalization on the last hidden layer, such is also true, as the last layer parameters are Amax parameters, and thus necessary for classification. However, there are other settings where it is less clear that A7 is satisfied. For example, for fully- connected network with bias parameters the validity of 7 will depend on the data. This limitation why we introduced Conjecture 5. which does not involve A7 and provided empirical evidence supporting its claim in section 5 The challenge to proving Conjecture 5.1 will be showing that version of Lemma 4. Istill holds once the parameter space restricted such that the Amax parameters are zero. It is likely the case that an argument in this direction will require proof by induction on the highest-rate parameters and their importance to the classification task.
24

---

Published as a conference paper at ICLR 2023
D PROOF OF LEMMA 4.1
Throughout this section, we assume A1 to A4. To simplify notation our proof, we define
V/ 2 dt
|| 3
(25)
We make of the following two simple statements: Lemma D.1. The derivative of loss is given by
dC
d0
(26)
dt
dt
for almost every Hence, it non- non-increasing for
Proof. Since L is locally Lipschitz function admitting chain rule, by applying Lemma 5.2 in Davis
et al. 2020) to [(O(t)), we immediately obtain dc de de
for almost every t 0.
di
Lemma D.2. For all & E R", ||A0|| 2 & Amax 111
Proof.
||A Σ X S Amax Σ x.0% = Amax 1013.
We will now prove the main lemmas described in section
Proof of Lemma 4.1 We first prove
2 [log((n()-)), By Lemma A.3
we can express
d0
A0
= -1
Σ e Vala(0) (0).
dt
Using this equality the statement can be shown by the following inequality
L f-vv loggoo)(
Σ e (afo(())
Σ (afe log(nL)
Σ Pa log Pa 2 0,
where Pa = (E, -oass(())- -1 Nofo0))) We now prove d ái log(?) 2 Ama log((18[(a) tan(w)?
dt log(?) dt (log log(l A log (1011a)
(log(n())1) -1 (-4---dd)) d.C
(AB, d8
dt
Amax 0 13
dL
(AO,
d0
dt
||
where the last inequality applied Lemma t >> 0, we can further simplify the RHS,
4.1 and Lemma D.2
Since
-1
d8 1|2 for almost every Zf
dt
d8
(AO, d0 )2
di
2l
AOOT
A
d0
|
| ||0||
|012
tan(w)?
|2
25

---

Published as a conference paper at ICLR 2023
where the normal component and the rangent component are defined
AOOTA
d0
AOOTA d0 |aaa di.
(27)
|0o
di
and the last equality used ||=|
π지 and the definition of Applying Lemma D.2 and श gives the final result,
d log(110)aa) de
tan(w)2 = Xmax d log((10]aa) tan(w)?
log(9)
X 1
dt
dt
Here an important direct consequence Lemma 4.1 Corollary D.1. 7(t) is non-decreasing for to-
Proof. Notice the following inequality derived using Lemma 4.1
Lemma D.1 and A5
d
L [log((n
0.
dt
|
|
It follows by Lemma 4.1 that d de
log(f) 2 0 and thus ý is non-decreasing.
26

---

Published as a conference paper at ICLR 2023
E PROOF OF THEOREM 4.1
We first prove the following four lemmas by utilizing Lemma
4.1
Lemma E.1 (Bounded f(; 0) on ((t)) Under assumptions Al 42 and 16 thenfor all i E [n]
f 8) is bounded on the normalized training trajectory 0(t) (i.e. 3k O such that (f ((t)) S
for all 2 0 and all i E (n)).
Lemma E.2 (Divergence of C-1 9minn [011))- Under assumptions Al A5, as oo the quanti- lies C 4min:
|0
0O.
Lemma E.3 (Upper bound on 7). Under assumptions Al A7, the normalized margin Ý bounded above by constant.
Lemma E,4 (Alignment of d# and A6). Under assumptions Al to A7, there exists sequence of dt time {tx hee on which cosine similarity B(tx)
Proof of Lemma E.1 By A4 and the uniqueness of the normalization procedure (Lemma A.
know the normalized training trajectory (() is continuous. Combined with the convergence of the normalized parameters (A6), this implies that (θ(t) z 0} is bounded. Which, by the continuity of f. further implies that for any fixed æ E Rd (x; ((t) t 2 0} is bounded. Thus, there exists k > 0 such that for all E [n], (x ((t)) - le for all t 2 0.
Proof of Lemma
E.2
We first prove that L-1 + oo as t co. By Lemma D.1
dC
A |A0 2
de
v2
dt
dt
dt
max 1013
where the first equality holds almost everywhere sense, and for the last inequality we use definition of and Lemma D.2 Applying Lemma bound
4.1 we can lower bound giving the lower
d.
L (on((n))-1))
dt 2 A
1001
2Amax
[log(((()))
-m L² log((n())1) 22mm))))
Amaxx
(2-22mmx) 2 A log(())))) 12022200000 ((40) 22 )
where the last inequality holds almost everywhere sense via Corollary D.I Rearranging terms on both sides of the inequality gives,
dL
L-
-2(1-Aam)))) 2 > 21max
dt
Integration from la to 4, with the substitution dc 28
L-2
6-1, -igves
2
(0)
(log n 122= 2(1 2m11))xx) dz 2 X A 22max (t to).
(-1(1))
The RHS diverges as + co. and the LHS as a function is denreacrn for 2 2 n, which true for all i. 2 by Lemma D.1 and A5 Thus Imin + oc as > oc, because Jmin is lower bounded by
conclude that L- - oo. This implies
log(C-)) < gmin-
We now show ||O||a - Do as / + co. We can upper bound Jmin by
Gmin (0) Qmin I E Tamax(10]1a)
sup [f ((t)),
iE(n],220
where Tmax( defined as
Timax (p) max(r(0) ||0|| p) -1 log P:
27

---

Published as a conference paper at ICLR 2023
and Amint minx, >0 As. By Lemma
E.1 sup
Papeein E2 (f ((t))
implying
9min k
min
|
and thus ||0||a
as
Proof of Lemma E.3
We prove by construction a constant upper bound of 7. Notice, |0 | and thus easily upper bound by
log (og((n()=1)
log(E-1)
|
|101|
Amiy
Notice that ||0|| X0 e² 2|000|
Amox Amax
and by A7
we know that || 2 K. Therefore, we can
further upper bound 7 as
log((-1)
Amin
e Mnmma
where the last inequality used suPielm),r20 (f ((t)) S k and therefore & is upper bounded by constant,
(1)
Quiin-
By Lemma E.1
T Umin
k
K Amar
Proof of Lemma E.4
We will inductively construct a sequence (4x JeeN such that 3(4x) - < k -- for any k N. Assume that sequence satisfies this condition for any k < with positive integer We show that we can find t
ft-1 such that the conditions above are met at f, as well. By can find N such that 4--1 and
Lemma E.3 and Corollary D.I
log Tmax (20) log 7max(s) (s) < 1_
Here > 0 a constant make sure that (1+ JEN goes to infinity. Furthermore, by the fact that p oc, can find s' > such that
log logp(s') log p(s) = 1.
This choice of and s' satisfies
log (5') - log 7max((1) (tz) log p(s') log p(x) < 1-1
D :
Assume that for any (,, g 2(1) D. Then
log Amax (8') log 7max (+) < (3-2- dlogg dt.
dt
On the other hand, by Lemma 4.1 the right hand side can be upper bounded as follows.
[ [((02-1] d log <
dl dol Tmax dt log Fraxx (s') - Tmmxx (s).
dt
dt
This is contradiction, implying that there exists (s,8²) such that (3(s) 2 D. Thus,
|| (() 1 1/VD+1
+
ie.. 4 satisfies the condition. Note that limu- 4 + co since 2 4-11 + e for any I.
Equipped with these convergence results, on the approximate KKT condition introduced in Dutta et al. (2013). In this paper, they defined a notion of KKKT point, which can be stated for optimization problem P as follows:
now prove Theorem 4.1 by exploiting the argument
A point 0 e R is a first-order (c, 8KK Point of there exist multipliers μ = (P (4n)
such that the following four conditions are satisfied:
28

---

Published as a conference paper at ICLR 2023
1. Primal Feasibility: yef( 0) for all [n].
2. Dual Feasability: μ4 2 for e [n]]
3. Approximate Stationarity: Vez 1011 - Ei P.y.h.]] S with some h; E fx 0) for each i [m].
4. Approximate Complementarity: E, Mi (uaf 0) 1) 8.
We call this of four conditions as the first-order (e, 0KT condition. In the proof for Theorem we use the following fact.
Lemma E.5. Under assumptions Al to A5 and A7 (0(t) with (og((min)) satisfies the first- order (e(t), 6()) KKT condition with multiplier p(t), where E(t), 8(t), ((t) are given as follows:
((T)))KKTTCC
(tt) A Amaax (2(1 - mm 2(A--Amar 1/2
Jwin
8(1) - =
nm 2-mmxx-2mma 22mar log((n()=))-
(28)
(4(()) c-1 c-1guin 21-22mma) e- vi E [m].
Imin
Here de ||||
We prove this lemma right after showing the proof of Theorem 4.1
Proof of Theorem 4.7 By Corollary of Theorem 3.6 in Dutta et al. (2013) (or Theorem C.4 in Lyu Li 2019)). suffices to show the following two statements:
There exist a sequence of time [t*)Aen and a sequence of real numbers fau JeN such that Uag (0(tx)) satisfies the first-order (Ek: -KTT condition, where Eky 62 and Von (0(tz)) converges.
4o oo (f(tx)) satisfies MFCQ condition.
prove the first statement with the result of Lemma E.5 By Lemma E.4 we can find sequence of time [eN which 3 + 1. Furthermore, because Y is lower bounded by Lemma E.3 Amin + oo by Lemma E.2 and L + 0 by Lemma E.2 e(t),8(t on this sequence converge to O: ((tz),,(ta)) + 0. Lastly show Vaatt.) (0(tx)) converges. Notice that (((tk))((t)) = q ((tx). where quin (t&) is the minimum margin of the model f(; ((tx)). By A6 ((tx) converges, and by the continuity of f(:;; 0), gmin (tx) converges. There- fore to show the convergence of vatt, (0(4)), ), it suffices to show that Jmin (1) is lower-bounded by positive value. This can be follows:
The second point directly follows from Lemma A.4
| 0
log C-
Jmin
Arnax
Imin
Quin Amax Amax
7,
Amax
|
110 A
where 7 is non-decreasing and upper-bounded by Corollary D.I
Proof of Lemma E5.5
We verify each of four conditions one by one.
Primal Feasibility:
It is straight forward to check that this choice of a implies (0) satisfies primal feasibility, for all i [m].
(n (0) = e vn 2 et Umin = 1.
Dual Feasibility:
It is clear that this choice of μ satisfies dual feasibility as Jmin
29

---

Published as a conference paper at ICLR 2023
3. Approximate Stationarity:
By Lemma A.2 for any h E fgf((; 0), we can expand the sum as follows:
m.y.Og (0) = Σ (1-A) (1- (xz;)())))) Σ
c
Amin
(Amas) (-I+A)
amin
Σ
e vi y:00 0.08(x2:00
=c (A-22max) (-8g1).
Umin
Hence, there exists a combination of h; E 0g. (x+, Va (0)) such that E, Mayhii = =c-1 (2mmm)))) d0 By substituting the expression of c, we obtain
Inii
dt-
d9
Σ Psyyh
Amaox
|
Amin
de
where Q is a diagonal matrix such that Qia = Iuin
(mxxx)
Now consider the derivative,
V 2 I (0)1l DA (f) = qmin
Amux DAO,
where D is diagonal indicator matrix such that D;; = 1 iff X Amax. Combining these last two expressions together, we can now bound the squared norm,
de ||
2
Vo 2 //a (0)]8
Σ Euesiie
Amax DAO
Amia
Imin
AO
de
9min
||881
D |alMl
d
|| at
II
2mmax
< Amax
Qmin
D ||A0
A0
27
[m0]
|| dz
A0
de
S Amax 7 -2Amax
d de
|
ZE
where the second to last inequality applies Lemma D.2 and the last inequality applies the definition of the normalized margin. We now bound the squared norm in the RHS using the definition of 3,
A0
d0
2
AO
de
dA di
D
di
D
dff
(D
Q)
|
|
de
dt
dt
de
AO
de
d8
W
D
di
+ (D Q)
|
49
d9
A0
VA
+ 1112
|AO|
de
de
A0
da
2(A,-Amas
|A0|
Imin
$
2(1
(8) m max
Juin
2(): Amax)
A
Combing the upper bounds we get
Ve (0)1
Σ Maichs
5
Amax 7 2Amax
2(1 -3) + m max Amax
2(2x-amax)
2())
30

---

Published as a conference paper at ICLR 2023
4. Approximate Complementary:
Expand the following sum with the defined values for a and pias
Σ us (yi (0)) 1) Σ Ms (yminii. (11,; (111;
1)
Ms
(q: mmin
Qmin
- 2hmax Imin
(g:
Qmin)
Notice the lower bound on the scalar
de
dd dE
T
Ad
)
Clog((nL)-1) Amin log (nlg(n)))))
A0
||00||
|
||012
|
where the last inequality follows from L 2 e Qmin. Using this lower bound for we can upper bound the previous expression as
Σ ps (yef(Im (0)) 1) S 4min
2Amax |0 1og((n))-1))
Σ (oi Qmi-) (q: Qminn)
The function f(2) = = attains its global maximum at 2 = 1, implying we can further upper bound this quantity
Σn ue (ynJ tha (0)) 1) S e
nomin
22mar
|| (og](()))
2Amma
S e n
Amin
log((n(C)1)) Amax
||0|
Amax A
ing
2Amax
log( Amax
8(t),
where the second to last inequality applies Lemma D.2
31

---

Published as a conference paper at ICLR 2023
F PROOF OF LEMMA 5.1
In this section, we provide a proof of Lemma 5.1
Proof of Lemma 5.7 Notice that in the homogeneous case, all the parameters have the largest X, and therefore P I and P = O. By substituting these to the expressions of Qqussi hom and ((Iqussi- hom) in Eq 5.1 we can obtain those of Whom and [(hhom) Therefore in the following, we focus on proving expressions for the guasi-homogeneous case.
By symmetry, Eq can be reduced the following optimization problem over single ball,
Eq
min
|Pwll:
min (w, x) 2 1 B(urr)
WER-
The minimization over Bu,, r) above can be further reduced as follows:
min (w,z) #e ((.r))
(w. 2EB(U.r
(w,r)
(w, - -rl(w|
(Pw, Pμ) (P.w, r ||
Hence, the optimization problem Eg can be reduced as follows:
Eq 4
min
[||
(Pw, Pи) + (Pi w. Pi n1 - -r|lw|| 2
wERd
min ER [|wll (wi, PA) + (w2, PL1) Vll 12 +
|22 2
2 (29)
Here we split the optimization over Rd by considering the orthogonal vectors Wi and Wh PL separately. Because the objective function ||w]|] is independent of w2, the last expression above equivalent the following:
Pw
min 1 E Rm
[|aa]| (wi, Pp) +
max Rdd-n
(wn P1H) TV w1 11 2 +
Ww ?
2
The maximization over wa pm-d is achieved if wa parallel PiÇ, μ. and hence, by letting pm denote ||wel|.
(W2, P1H) TV
112
10g E
PuPu -T DeVV/// 11 P
Pi ERo
Pu/r
p4./r2
Pμ
||w2|1|
-r
|| 12
0///² / |1il|
D///12
1
1
///0221wall1
(30)
where the maximization over Pr E T2z on the second line of the equation above is achieved if only Pn/r
/1-02/ra [|w ||. and hence the maximization over W2 IRd-m on the first line is achieved
Pp
and only
|w
W2
P. n.
(31)
/3//10 r
32

---

Published as a conference paper at ICLR 2023
Therefore, by substituting Bq
30
obtain
Eq 4
min
||
||
||will
W1
PR))
rv
p/. r2
wyy EIL"M
min
W1 Pu) -rve //2
Pµd TV 1 - pf./22 0
wi Ell"
|wwll
Pμ} - rr / 1 - pf./2 1 o1)
W1
W1
max 1i EM
PH)) - /v pg.//2
||y|l"
u1
(IPMll - 1-pp//1
= -V11- Ph - r 02/122
Note that this quantity is positive since r < by assumption, and the minimization over R is achieved if and only if wi is parallel to P/u,
W O Pμ.
(32)
Notice that the optimizers of Eq 29 and hence those of Eq need to satisfy both Eq This means that the optimizer is unique and is given as follows:
32 and Eq
31
Uquasi-hom = - -2/1))//7)
Pu
Pite
V
PB.
" TV
02/122
By normalizing this, obtain the expression in E is obtained as
At this minimizer Wquasi-hom- the robustness (
(gqusi-hho))
||
W0 Uuqasi-hom
||
min (Wquasi-hom x) =EB(,.A)
liqusi--oom
(uquasi-hom: p1) -
2 ph 1 - P7. + r pg
V1-r3pp
(VI
P7 12 p7
33

---

Published as a conference paper at ICLR 2023
G PROOF OF THEOREM 6.1
We here first state the rigorous version of Theorem 6.1
Theorem G.1 (Neural Collapse). Under assumptions A8 A9 and d 2 C, any global optimum of the optimization problem Eqg8 satisfies Neural Collapse, i.e.,
For any class [C], there exists vector he such that h; h, for any data E [r]] with
1/1 c.
The convex hull of {wo]eetcy forms regular (C - 1)-simplex, centered at the origin.
For any C [C1, he and we are equivalent up re-scaling.
arg w + be argmince(c] || - hell for any h E IRd, i.e., any feature vector is classified to the class c with the nearest class mean he-
Proof sketch for Theorem G.1
To prove Theorem G.I we study a sequence of three relaxed
optimization problems, starting from Eq and introduce five lemmas (Lemma G.1 to G.5 charac- terizing the minimizers of these relaxed problems. The optimization problem Eq g can be reduced to the following by 48
mimegin di 2 E (h:), = 0, E, =1 e
min (an b,)
We + 1612 s.t.
(33)
eE|C]
where yi is defnied
q: = (wy)) + by.
max c#
[(w=)²h; + be]
(34)
The minimizers of this optimization problem are characterized in Lemma G.5 we will consider the following further relaxed problem,
To prove Lemma
G.5
minne(m) qi 2 1
min (w.bbh)
ww/ +
16|2 s.t.
(35)
Σ (he) =1 vi
[m].
cE|C]
This problem is analyzed in Lemma G.4 This optimization problem is equivalent to our last relaxed problem.
mii
| 2 + 11/22 s.t. CE(C]
max (cu
min iE(n)
11a) =1 Vi [m]
21
(36)
The minimizers of this problem are analyzed Lemma
G.3 with the help of Lemma G.2
which
analyzes a further relaxed problem and Lemma G.I which analyzes the constraint in Eq 36
We will
now introduce and prove Lemmas G.I through G.5
Let H/ denote the set of (ea satisfying the constraints Σ, for any [n]], A. denote
the (C 2)-simplex formed by (we )cEC)//(/// and denote the standard (C 22--2, 20))--impplex.
Lemma G.1. Under assumption A9 the following equality holds
max min q: min Ler
(37)
(h.EH sE(n) cE[C]
with
: min w|w. w'((a)) + (b (b- (a))), aEA
(38)
where (a) A + A. and (a) A + R are defined as w'((a) := Ederci/te) Wi.le and ((((a) E C/C//// diebe, where ic()) [C]/(c) - IC is given by ic(c') é' if d' < and ic() otherwise. Any maximizer of the quantity above given by h; = h where
W. w²
h-
(39)
lwe w.
with w w(((a) with minimizing Eq 38
34

---

Published as a conference paper at ICLR 2023
Proof.
max min di (K RE
min max <Ein k=||/||==1
(wy,) ) 1hh h by.
max
[(we)) h+ + bel
e'elo1/luu)
min max cE|C] b=]AA||=1
(we) ) h lb
max c'eCC/(cc
[(we) + Do]
where the maximization over (ht is achieved when
h; E arg max h:][A|||1
(wyy)" 7T h + by.
max e'(cI//u
[(wz) + der
The quantity inside the parenthesis can be reduced as follows.
(we)"h. h be
max c'(CI//cc
[(we)" be]
(we ww)) (b b²) ee|CI/(c)
min
min (we u')a)) h + (b - b((a)),
Therefore by the minimax theorem,
(wa) h b
[(we) + bor
max
h: A||=11
de(cc//ct
max min - (we-w'(()) T h + (b - b((a))
M aEA
min max (wo - w'(a))) h + (b K((a))
oE he| A||=1
min || - w((a)) (b (())))
aE
Le
where the maximization over is achieved if and only if = the maximizer is h,
Hence Eq 37
holds. Clearly,
w [w--wll will
W4, " || wt,
By Lemma G.1 the optimization problem 36 reduced to
min (an,6)
| 2 + ]b|2 s.t. min Le 1.
(40)
cE(C]
We will later show that this minimization is achieved when the convex hull of {weleetc] forms regular simplex. However, before dealing with 40) we first solve the minimization of the following casier problem.
Lemma G.2. Consider
Z: = w| - w/ (a))l + (b (a)),,
(41)
where ā of the following optimization problem
(C- is the bary-center of simplex A. The minimizer
min (Wweheete)
Σ wwe + |b|
s.t.
min Ze 2 1, cE|C]
(42)
is achieved if and only if the following conditions are met:
||wel| = C-l
Σ EeE We = O
(43)
O.
Furthermore, at these minimizers Z, 1 for any [C).
35

---

Published as a conference paper at ICLR 2023
Proof. Notice that the constraint of this optimization problem is translationally invariant, i..., for any w E I' and any (we satisfying min Ze 2 1, {we + [eE[c also satisfies the constraint. Hence, the minimizer of Eq Sq]42]soo should satisfy the stationary condition with respect to the derivative of ie for all e [d]. i.e.
E CE(C]
w. =.
(44)
In the following, we consider the optimization with this new constraint Eq 44
Next, we relax the
constraint min, Ze to E. Ze 2 1 (clearly C- E- Ze min Zc). By the help of Eq this averaged value is calculated as
C-1 Σ %he cE[C]
C-
Σ
||
w/ (a)]l (he (((ā)))
cE(C]
=
C-1
Σ
-1
+ (be - (C
be
C
<E[C]
e'ECc//tc
C
C-1 Σ
C - ||wlll + (be (c
ber c'ECc//cc
cE|C]
(C 1)-1
||we|l
cE(C]
Hence, the relaxed problem can be stated follows:
min
|well"
||b|22 s.t.
|wa/| 2 --
(0),8)
eE[C]
Clearly, this can be achieved if and only if and ||well = Cd Notice that this configuration
satisfics C-1 E. Ze = min,elc! Ze, and hence it also the global optimum of the original problem Eq 42 Lastly, is easy that these minimizers satisfies
C Ze = C-1
||wlll +
b 60
Σ e'(C)/())
b = 1.
for any c E [C].
Lemma G.3. Under assumptions A9 and d 2 C, the minimization Eq achieved if and only if the following conditions are met:
The convex hull of [wa]ee[c] forms regular (C - 1)-simplex |woll E-l
Ve
[C]
(45)
Eeec We ===0 b-0.
Proof. First we show that any point satisfying Eq 45 is a minimizer of Eq Notice that the set of (fweloejo). b) satisfying E5 non-empty since 2 C. All elements of this set satisfy Ze Le for any [C] by the first condition in Eq and clearly minimizers of Eg 42 by the other conditions in Bq as shown Lemma G.2 Thus, the elements satisfy min toe 2 1. For any
e E [C], Ze 2 Le, and hence
((wa)oeto) b): min Z, 1 2 ((wa)oet0) b): min The 2 1 cE(C]
cE|C]
Therefore, point satisfying 45 is minimizer 3q
Next we prove the inverse. We assume that ([waheejc)- b) is a minimizer of Eq 36 This point must
also be minimizer of Eq 42 because showed previously, there exists minimizer of Eq 42
36

---

Published as a conference paper at ICLR 2023
satisfying [c] Le 2 1. By Lemma G.2 this point satisfies Eq Hence, this point satisfies Eq|45 if the convex hull [we)eeC forms regular (C (C-33 s--smpleex Since Ze for any e E [C] by Lemma G.2 and Ze 2 The 2 1, T.e Z = This implies that the bary-center w((ā) the point in Ae closest we. In the following, is independent the choice distinct pair C1, 02 [C], implying that the convex hull [ee]e forms regular simplex.
argue that this property implies that l|we, Wey
For any 01 E [C], w'a (a)ll = || ||(C - 1) = C- Since Le > for any c E [C], all the vector we are distinct, and hence, w/, (ā) perpendicular to Wez - wy (a). Therefore,
(C 1)2 C C
Wee w/, (a)ll ||we,
1| (a)l|=
C
Thus,
|0eg - Wez 11 = Wee - w/, (a)
+ |lles w/, (a)ll²
(C - 2)/C++
CC-1(C-1))
This is independent of o and C2 implying that the simplex is regular.
Lemma G.4. Under assumption A and d 2 C, the minimization Eq 35 is achieved if and only if the following conditions are met:
The convex hull of (waJeercy forms regular (C - 1)-smpllex
|well = edl Ve
[C]
Exeloy We =a=0 =0
(46)
b=
h4 = u
wyy
Vi E [m].
Proof. We first show that a minimizer of 3q satisfies Eq 46
For a minimizer Thus, by Lemma G.3
(fwaleejo). b, (helvel)) of 35 (fwe)ee(c) is a minimizer of Eq the minimizer satisfies the first four properties. Additionally, by Lemma
G..
max (h.)
min gi [E(m]
E(h3==1 vi vie vie
min Le
cE(C]
Therefore, to satisfy the constraint minjelni Øi 2 1 in Eq 35 [hcheenn needs to be maximizer of the equation above. Again by Lemma G.I this maximizer given by
w Wy:
Wy: w/y, (a)
h
C-1 Wyo
[wy.
w7.
w.y. w/y (a)
which is the last condition.
We now prove the inverse. We assume that ([we]oe[C]- b, (h4)ee(m) satisfies Eq 46 By Lemma G.3
(fwe (we)oejo). b) is minimizer of Eq Since the minimum value of Eq 36 is equivalent to the minimum value of Eq[35] it suffices to show that ([w.Jee(c)- b, (hi)ee()) satisfies the constraints
in Eq 35 which can seen as follows:
C-1
min = min min
(w,, wx)x 0-1 Wy,
sE(n] xE(n)
cE(C)/(M)
C
Σ (h.)) = -
Wg. 1.
37

---

Published as a conference paper at ICLR 2023
Lemma G.S. Under assumption A9 and d C, the minimization Eq is achieved if and only if the following conditions are met:
The convex hull of (we]ae[c] forms regular (C - simmlex |well| = C-1
ve [C]
Ejelc ===
=0
(47)
b=
h; c-
Uyy Vi E [n]
Eield (We)i = Ve E [C].
Proof. Since Eq 33 has additional constraint
(h.);= E
(48)
compared to 35
35 by Lemma G.4 suffices to show
(Wweleejy b, ( (e())))) satisfies Eq 46 and Eq
48 if and only if Eq 47 is met.
There exists ((weleetc) b, (h)) satisfying Eq
47
First we show the first statement. We assume 46 and Eq follows:
48
Then the last equality in Eq 47 holds
Σ (we); jEld
ha
0
jE(d]
where i E [n] is such that yi = The existence is assured by Ag
The other equalities in Eq 47
trivially holds since they are equivalent Eq 46 Conversely, if Eq and Eq 48 holds as well since
holds, Eq trivially holds
E01), = Σ JELd
Wyy
0.
The existence of (Awa)eejo) b, he(m) satisfying Eq 47 can be seen by the fact that regular (C 1)-simplex is in (C - -dimensional subspace, and we can rotate the simplex such that it is inside the (d di-dimensional subspace constrained by Eieja (we); 0 Ve [C]. without violating
the other equalities in Eq
proof of Theorem G.1 By AB the optimization problem Eq S can reduced to Eq 33 Hence, by Lemma G.5l the minimizer's condition is given by Eq which implies the first three properties of Neural Collapse hold with he hg. The last property can be proved as follows.
The distance between h and ha given by
|| hill2
||b]] + 2
2h h%
20
||b] +1
1 We-
C 1
Hence,
2C
argminge(c] ||/ - hill = argmin
|Ail| +
h2t We
0 0-1
argmax.elc hTt
argmax hiT wa + bo.
38

---

Published as a conference paper at ICLR 2023
H EXTENSION TO MULTI-CLASS CLASSIFICATION
In this section, we extend Theorem 4.1 to the case of multi-classification tasks with cross-entropy loss. The analysis here largely relies Appendix G in Lyu & Li (2019).
We consider a classification task of data {æi, Me Hi[n) whose label yi which now takes values in [C], where C & N the number of classes. Our model's output is given by (x;;) E RC, and the cross-entropy loss with this model defined as
exp(fu, (xz:0)) Eee[c] exp(fc(z);())
-
Σ log JE(M)
n Σ jE(m]
log(1 + t
(49)
where 0j == - log (cee)
and $jc == fug (zy : 0) fe(zy; 8). Notice that $je is a
quasi-homogeneous function. Hence, if Lemma E.2 holds and 0 goes to infinity - oo, which we will show later in this section, Sjc goes to infinity. Therefore, when & > 1,
i - log
max cE(CI//u,)
min $30 (+ 00), cE(C)/(,)
and by Taylor expansion of logarithm log(1 + e e0) ~ e 4;
L
Σ log(1 + +) JE(N)
Σ の
JEIN]
This expression now equivalent to the of binary classification tasks with the exponential loss.
Note that the effective margin is now given by mineeeCC/(v,, Sjc. which implies that its asymptotic behavior the later stage of training similar the one with the exponential loss. Being aware of
this fact, we can show variant of Theorem 4.1 with modified version of separability condition:
A10 (Strong Separability for CE Loss). There exists a time to such that ((O(t))) n- ''oogg
A6 and, AI with cross-entropy loss Eq there exists an a E IR such that v/a (lime+oc B(t) is a first-order KKT point of the following optimization problem
Under A
minimize
|
2
mas
subject to
min cE(CI/ty,)
$Jc 2
Vj E [n].
The modification of our proof of Theorem 4.1 is quite similar to the extension done in Lyu & Li d show the lower bound of dt log [[[||, and divergence ||]| + co. Hence here we will focus on this non-trivial part and ask readers to refer Lyu Li 2019) and Nacson al. (2019b) for the other details.
2019) and straightforward except the part where
Similar to the first inequality of Lemma
we can show the following:
dt 3 2 (1 - e ene) -n2))log log (e - 1).
(50)
is easy to see that
1 d
d0
|1011% =
A6
2 dt
dt
Σ
-
(hye,
(hje is some element of 87
jE(n)
cE(C)/(b))
Σ
Σ
1te is
JE(M]
cE(C)/(31)
Σ 330
jE(n)
(E(C)/(s))
It -
JE(x]
39

---

Published as a conference paper at ICLR 2023
Since d can be uniformly lower bounded by L as follows
n -1 log(1 + + + i.., qs 2 -log (ene -)),
log (erel clos(ene-1)
the 4;
[1 e log( + e- 2 (1 + elog(ene-1)) log(1 + clogiene-
jEIn]
- (ene - 1) log -1
nLene
Here for the inequality, we exploit the fact that function With the help of this inequality, we
ze (Ite log(1+e-=) an increasing function.
101
Σ log(1 + te
dl
(1 (1 (0=4:)100 log(1 + E-
jE
rere 1) log (ene - 1)
log(1 + e
WLene
jEfni
c n2) log (cne-11
Next, we show a variant of Lemma
E.2 By utilizing the lower bound of d at
||01 and introducing
newly defined smoothed normalized margin ý == ||0|| A Amax
dC
A (1 - e1-e-ncys log (enL 1)²
dl
11012
(- e (eet
2Amax
X - 1)² log(e 1)(2 2dman) 12(2mn)))))
11011mmme
A (E - 1)² log(e"E 1)(2- -2222ma) 2Att))mmxx
22mmx
where the last inequality relies on version of Corollary D.I the inequality gives,
Rearranging terms on both sides of
dC (e (ene- 1)-2 log(e 11-21111111 1ogge - -1) -maax) 2 A 7 2Amax 22m))
dt
Integration from to to f, with the substitution -n dC (cnC - 11)- d(c"C-11 1) gives
n (1
(ond 1)-1 (-log 0 2(1 2(1--max)) dz A
2m ((1)) 10)-
The RHS diverges as l + 0o, and the LHS as a function of is non-decreasing for 2 < 1, which is true for all to by Lemma D.I and 10 Thus can conclude that f- co. Exploiting this fact, we can easily show ||0|| + oc as we discussed in the proof of Lemma E.2
40

---

Published as a conference paper at ICLR 2023
I EXPERIMENT DETAILS
All empirical figures this work were generated by the attached notebook. Here we briefty sum- marize the experimental conditions used generate these figures.
Logistic Regression (Fig. D.
This plot was generated by sampling 100 sample from two Gaussian distributions. j+ oT) in I where μ [1/v2, 1/v2] and 0.25. The parameters for both the homogeneous and quasi- homogeneous model were initialized as standard random Gaussian vectors. The parameters were trained with full batch gradient descent with a learning rate 1) = 0.5 for 1e5 steps. The maximum lz-margin solution was computed using scikit-leam's 's SVM package Pedreggsa et al. (201I).
Ball Classification (Fig.
This plot was generated by sampling 1e4 random samples from the surface of two balls B r) in R for 100 linearly spaced radii [0, 1]. The mean μ [0.8660254, 0.4330127, 0.25 was chosen such that Pa 0.5 and Pptμ م = 0.25. The guage-oomogeneous model was defined such [1.0.2, 0.1). The parameters for the homogeneous and quasi-homogeneous model were initialized with the all ones vector. Using these initializations and SciPy's initial value problem ODE solver Virtanen et al. (2020) we then simulated gradient flow until T 1e5. The final value of the classifier for both models and their respective robustness was recorded and used to generate the final plots.
that D, 1, D2 5, and D3 10 leading to A-values
41


Reviews:
[{"review_id": "_c3rTGjQn5l", "reviewer": "Reviewer_i1KS", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the implicit bias of gradient flow with an exponential loss on a class of neural networks called “quasi-homogeneous networks”. This class, which is introduced in the paper, is very rich and includes, e.g., ReLU networks with bias terms and residual connections. The implicit bias of such networks is not implied by previous results, which consider mostly homogeneous networks. The results hold for both binary classification, and multiclass classification with the cross-entropy loss. The implicit bias of quasi-homogeneous networks is characterized by asymmetric margin maximization (which involves only a subset of the parameters). The authors also conjecture that an even more general property holds (a certain cascading weight minimization property). Also, they obtain some implications in the context of robustness and neural collapse. ", "summary_of_the_review": "As I discussed above, I think that it is a strong paper and recommend “strong accept”.\n\n-----------------------------------------------\n\nAfter reading the authors' response, I stick with my high score.", "strength_and_weaknesses": "The implicit bias of gradient flow in neural networks has been extensively studied in recent years. It is believed that understanding the implicit bias may be a key to understanding generalization in deep learning. In the context of classification with exponential-type losses, the most prominent prior result is by Lyu and Li (2019), and it implies a bias towards margin maximization in parameter space (or at least towards stationary points of the margin maximization problem) in homogeneous networks. The current work extends this result to a large family of non-homogenous networks, which includes ResNets and networks with bias terms. I believe that this contribution is very significant, as it makes a step towards understanding the implicit bias in practical settings. Therefore, I think that it is a very strong paper. \n\nMy main comment is that I think that the paper can benefit from a more detailed discussion on the assumptions made in Theorem 4.1. The authors give several examples of quasi-homogeneous networks, both in the main text and in the appendix, and convince the reader that the class of quasi-homogeneous networks is very rich and includes “nearly all neural networks with homogeneous activations”. While I agree with this statement, I think that the more relevant question is when the other assumptions hold. For example, the authors discuss “networks with residual connections” as an example of quasi-homogeneous networks. However, it seems that these networks do not satisfy Assumption A2, since f is not bounded on the unit “sphere” (in this example, the lambda of the first layer is 0 and of the second layer is positive, hence the unit sphere includes all networks where the second layer’s weight is 1, and by increasing the first layer we can get arbitrarily large outputs). I suspect that many readers might get the impression that since the family of quasi-homogeneous networks is very rich, then the theorem essentially holds in all interesting settings, but it does not seem to be the case. Therefore, such a discussion, in my opinion, is important. A more concrete question for discussion is: when does the theorem apply in ResNets? (I suppose that if the residual block includes only trainable parameters, both skipping and non-skipping, and does not include the identity matrix, then the assumptions should hold if the skip-connections are necessary for separating the data and assuming directional convergence, right?)\n\nSome additional comments:\n- In the proof of Theorem 4.1, you show that the KKT point satisfies the MFCQ condition. It implies that the KKT conditions are necessary for optimality, right? I think that it is a useful fact and it might be worth mentioning in the main text.\n- Page 6: “See App. C for a discussion on how to determine the highest-order…” — Do you mean App. A?\n- Page 7: “$(w_3)$” should be “$(w_1)$”?\n- In Sec. 5, it might be worth discussing that also homogeneous linear networks may converge to non-robust solutions. For example, diagonal linear networks prefer sparse solutions and do not maximize the $\\ell_2$ margin.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JX2P7Mo_hs", "reviewer": "Reviewer_bFVN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the max margin bias that arise in the gradient flow training procedure of *quasi-homogeneous* neural networks. Quasi-homogeneous networks can be thought of as a generalization of homogeneous networks that are previously studied in the literature (e.g., Lyu & Li (2019) and Ji & Telgarsky (2020)), and they contain a significantly wider range of networks such as ones with bias terms, skip connections, normalization layers, etc. \n\nFor this general class of networks, the paper extends the results by Lyu & Li (2019) to show that the direction at which the network parameter vector converges to corresponds to a first-order KKT point of a (nonconvex) optimization problem (denoted as (P) in the paper). The key difference from Lyu & Li (2019) is that the objective function in (P) is no longer the standard $\\ell_2$ norm; instead, it is the $\\ell_2$ norm of a *subset* of parameters defined by the quasi-homogeneity.\n\nThis result highlights that the gradient flow dynamics is biased toward achieving the maximum margin with respect to only a subset of network parameters. This \"asymmetry\" leads to some interesting consequences, namely that 1) it can hurt robustness of the resulting classifier and 2) it can provide an explanation to the recently observed *neural collapse* phenomenon.", "summary_of_the_review": "The paper investigates the max margin bias in a very general class of neural networks referred to as quasi-homogeneous networks. The investigation uncovers some interesting and unexpected bias, namely the implicit bias applies with respect to only a subset of parameters. Also, this theoretical result has some important implications to neural collapsing which is of interest.\n\nWhile the paper presents interesting theoretical results, one crucial downside is that the quasi-homogeneity is not completely well-defined. For a given network there can be multiple \"subsets\" of network parameters, and fully disambiguating these cases could use some additional effort.\n\nOverall, my current rating is positive but not too positive; I would be happy to raise my score based on the authors' response.\n", "strength_and_weaknesses": "Strengths\n\n1. This paper generalizes the existing theoretical research on homogeneous networks to a greater extent, and the newly introduced class of quasi-homogeneous networks is very general. Hence, the paper develops a theory that applies to many practical networks. \n\n2. Through this extension, the paper uncovers that the max margin bias of gradient flow only applies with respect to a subset of parameters, which is quite an interesting discovery. Moreover, this observation can help explain the empirically observed neural collapse phenomenon.\n\n3. Although I believe assumption A7 is unrealistic in some practical scenarios (see the weaknesses part), the authors present a motivating example (Section 5) that allows us to imagine what might happen without the assumption. They propose a neat conjecture (Conjecture 5.1) which naturally extends Theorem 4.1 to settings without A7. This uncovers an interesting future research direction.\n\nWeaknesses\n\n4. Among the assumptions required for Theorem 4.1, the one that seemed the most unrealistic to me was A7, namely that the highest-degree parameters must contribute to the classifier for it to separate the dataset. The assumption does not hold in some practical scenarios, for example when we have a 1-hidden-layer fully-connected network with bias terms (hence the bias $b^2$ of the output layer is the highest-degree parameter) and the dataset can be separated without the use of $b^2$.\n\n5. As noted by the authors, the diagonal PSD matrix $\\Lambda$ that defines quasi-homogeneity may not be unique. For example, for networks with normalization layers, one can choose *any* values of $\\lambda$ for scale-invariant parameters. The authors discuss in Appendix A on how we can disambiguate between different possible choices of $\\Lambda$ by leveraging assumption A7 and taking a closer look at the optimization problem (P). However, this is only a \"proof by example\" and the paper does not concretely prove that there is only one possible choice of $\\Lambda$ for which Theorem 4.1 applies. Also, it is unclear how we can disambiguate the equivalently working values of $\\Lambda$ without the help of A7. I believe this is the main downside of this paper. \n\nMinor comments\n- To me, the word \"highest-order\" for parameters with $\\lambda_{\\max}$ seems a bit counterintuitive, because these parameters are often those with the lowest \"polynomial degree.\" For example, for $f(x;\\theta) = w^2 \\sigma(w^1 x + b^1) + b^2$, the $b^2$ term with the smallest \"degree.\"\n- In \"Geometric properties\" paragraph on page 4, $\\nabla_\\alpha f(x; \\psi_\\alpha(\\theta)) = \\nabla_\\alpha e^\\alpha f(x;\\theta)$?\n- From Lyu and Li (2019) I believe A2 is stated for a fixed given value of $x$, but the paper doesn't clearly state that. As a result, I once got confused why $|f(x;\\theta)| \\leq k$ must hold for all $x$.\n- It'd be good to put a label (P) next to the optimization problem in Theorem 4.1?\n- At the end of Section 4, \"See App C\" -> \"See App A\".\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "IBbmqhCqEC8", "reviewer": "Reviewer_CPzm", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work studies the implicit bias of quasi-homogeneous networks. Under a conditional separation assumption, it is proved that gradient flow converges to a KKT solution of a certain minimum norm optimization problem. The latter norm depends on a subset of the parameters such as the last layer bias of a fully connected network. Based on the main result, it is shown in a certain setting that the inductive bias of quasi-homogeneous networks is towards non-robust solutions. Furthermore, it is proved that the neural collapse phenomenon occurs for quasi-homogeneous models under certain assumptions.", "summary_of_the_review": "This paper presents new and interesting results on the inductive bias of non-homogeneous networks. However, I cannot accept this paper in its current form, because one of the theoretical results is currently inconsistent. If the authors can clarify the statements and write a consistent theorem then I will increase the score.", "strength_and_weaknesses": "Strengths:\n1. Strong and novel theoretical results.\n2. Novel definition of quasi-homogeneous networks that may help to understand neural networks in new settings.\n3. Interesting experiments on robustness.\n\nWeaknesses:\n\nThe major weakness is that Theorem 4.1 in its current form is inconsistent. Since the quasi-homogeneous parameter is not unique, for a given network the theorem implies that gradient flow converges to different minimum norm problems. This is impossible, unless:\n1. All such problems are equivalent, or:\n2. Given the assumptions, there is a unique parameterization.\n\nThe authors provide several examples where (1) or (2) above hold, but there is no general proof that they hold for all quasi-homogeneous models. If the theorem implies that either (1) or (2) hold for all quasi-homogeneous models, then this should be stated in the theorem. \n\nAnother issue with the inconsistency is that Definition 3.1 holds for all x. However, the main result only concerns with the training set, therefore it seems that the definition can be only with respect to x in the training set. If we change definition 3.1 to hold for x in the training set, this changes the possible parameterizations of quasi-homogeneous models and the main result. It is not clear which definition should be used.\n\n\nAnother weakness is that conditional separation assumption seems strong. There should be more discussion on this assumption and maybe proofs that it holds in certain realistic settings.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1bXF0fw1cBx", "reviewer": "Reviewer_UHdE", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes the maximum-margin bias of gradient flow on quasi-homogeneous networks under data separation. In contrast to homogeneous networks, different parameters in a quasi-homogeneous network are allowed to have different homogeneity factors; this model can represent bias terms, skip connections, normalization layers, etc. This paper shows that the final maximum-margin bias is determined by the parameters with the maximum homogeneity factor, which naturally generalizes prior results on homogeneous networks. Specifically, it is proved that the final solution is a KKT point of a norm-minimization problem for the parameters with the maximum homogeneity factor, under a data separation condition. It is also discussed that quasi-homogeneous maximum margin can degrade robustness and induce neural collapse.", "summary_of_the_review": "This paper introduces an expressive model of quasi-homogeneous networks, and analyzes the maximum-margin bias of gradient flow on such models.", "strength_and_weaknesses": "I think this is a nice paper. The quasi-homogeneous model is very expressive and allows common layers used in deep learning, which can be an interesting model to analyze. The proof naturally generalizes prior analysis on homogeneous networks, and reveals that gradient flow will asymptotically focus on the parameters with largest homogeneity factors. I have the following comments:\n1. Part of Assumption A2 can be included in the definition of quasi-homogeneity, otherwise the definition may look too flexible. For example, given a deep linear network with no bias, we can let lambda be 1 for the last layer and 0 for other layers; this does not violate the definition, but the boundedness condition in A2 does not hold.\n2. Since some $\\lambda_i$ can be 0, $\\hat{\\theta}$ may not be uniquely defined. Can you make its definition more rigorous?\n3. Can you explain how conditional separation (Assumption A7) is used in the proof?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%