Feature Learning in $L_2$-regularized DNNs: Attraction/Repulsion and Sparsity
Authors: Arthur Jacot
Eugene Golikov
Clément Hongler
Franck Gabriel
Venue: NeurIPS 2022 Accept (2022)
Keywords: Deep Learning
L2 regularization
feature learning

Abstract: We study the loss surface of DNNs with $L_{2}$ regularization. We
show that the loss in terms of the parameters can be reformulated
into a loss in terms of the layerwise activations $Z_{\ell}$ of the
training set. This reformulation reveals the dynamics behind feature
learning: each hidden representations $Z_{\ell}$ are optimal w.r.t.
to an attraction/repulsion problem and interpolate between the input
and output representations, keeping as little information from the
input as necessary to construct the activation of the next layer.
For positively homogeneous non-linearities, the loss can be further
reformulated in terms of the covariances of the hidden representations,
which takes the form of a partially convex optimization over a convex
cone.

This second reformulation allows us to prove a sparsity result for
homogeneous DNNs: any local minimum of the $L_{2}$-regularized loss
can be achieved with at most $N(N+1)$ neurons in each hidden layer
(where $N$ is the size of the training set). We show that this bound
is tight by giving an example of a local minimum that requires $N^{2}/4$
hidden neurons. But we also observe numerically that in more traditional
settings much less than $N^{2}$ neurons are required to reach the
minima.

Feature Learning in Le-reaularized DNNs: Attraction/Repulsion and Sparsity
Arthur Jacot
Eugene Golikov
Courant Institute of Mathematical Sciences
Chair of Statistical Field Theory
New York University arthur jac.jjay.o.uueeeooo.oo...
École Polytechnique Fédérale de Lausanne evgenii gol golikov@epfl.com
Clément Hongler
Franck Gabriel
Chair of Statistical Field Theory
Institut de Science Financière et d d'Assurances Université Lyon
ticole Polytechnique Fédérale de Lausanne clement. hon.eettnnnnllref.....c
Tranckr.gabrielgge.... com
Abstract
We study the loss surface of DNNs with L2 regularization. We show that the loss in terms of the parameters can be reformulated into loss terms the layerwise activations Ze of the training set. This reformulation reveals the dynamics behind feature learning: each hidden representations Ze are optimal w.r.t. to an attraction/repulsion problem and interpolate between the input and output representations, keeping as little information from the input as necessary to construct the activation of the next layer. For positively homogeneous non- linearities, loss can be further reformulated in terms the covariances of the hidden representations, which takes the form of partially convex optimization over a convex cone.
This second reformulation allows to prove sparsity result for homogeneous DNNs: any local minimum of the Ly-regularized loss can be achieved with at most N(N + neurons in each hidden layer (where N is the size of the training set). We show that this bound is tight by giving an example of a local minimum that requires N hidden neurons. But we also observe numerically that in more traditional settings much less than N2 neurons are required to reach the minima.
Introduction
is generally believed that success of deep learning hinges on the ability deep neural networks (DNNs) to learn features that are well suited to the task they are trained on. There is however little understanding of what these features are and how they are selected by the network.
On the other hand, recent results [12] have shown that it is possible to train DNNs without feature learning. This suggests the existence two regimes of DNNs. kernel regime (also called lazy or NTK regime) without feature learning and an active regime where features are learned. The presence or absence of feature learning can depend on multiple factors, such as the intializaaton//paammetzzzaoo of DNNs
25
13), very large depths [10 or large learning rate [16] 5).
feature learning in DNNs. This analysis further motivated by recent results g 9 which show that the implicit bias of gradient descent on losses such the cross entropy (which decay exponentially towards infinity) is essentially the
In this paper, focus the impact of L regularization
same as the bias induced by T-2 regularization DNNs.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Generally, the bias induced by the addition of Le-reuularization on the parameters 0 of a model fo can be described by the representation cost R(f) mino:fu=f ||0|| since ming C(fo) + X |101] miny C(f) + XR(f).
In deep linear networks, the addition of L2 regularization on the parameters corresponds to the addition of an Lp-Schatten norm regularization to the represented matrix, with p 3/2 where L is the depth of the network 19 6]. This implies a sparsity effect that increases with depth L.
In non-linaar networks the sparsity effect of Legreaulat has been described for shallow networks (I=2) 2) in I 20 23 or for shallow non-linear networks with added linear layers [19] Though seems natural that this effect should become stronger for deeper networks, to knowledge little theoretical work has been done this area.
1.1 Contributions
In this paper, we study the minima of the loss of Le regularized fully-connected DNNs of depth L. We propose two reformulations of the loss:
1. The first reformulation expresses the loss in terms of the representations Zi,..., layer pre-activations of every input in the training set) of every layer of the network. This reformulation has the advantage of being local - the optimal choice of layer Ze only depends on its neighboring layers Zr-1 and Ze+1. The optimal choice of representation Ze is at the balance between an attractive force (determined by the previous layer) and a repulsive force (coming from the next layer). It illustrates how the representations Zz,..., ZL-1 interpolates between the input layer Zo and output layer Z7
, Zr. (the
2.
The second reformulation expresses the loss in terms of the covariances of the representation before applying the non-linearity Kr = 2 Ze and after the non-linearity KÝ = (Zf)² z For positively homogeneous non-linearities and when the number of neurons ny in every hidden layer & is larger or equal to N(N + 1) for N the number of datapoints. this reformulation is optimization of (partially convex) loss over the covariances (K,, KT),..., (K2-1, Kg-1) and the outputs Zz, restricted to a (translated) convex cone. This reformulation does not depend on the number of neurons ny in the hidden layers (as long as n, 2 N(N + 1)).
The second reformulation implies that for positively homogeneous non-linearities such the ReLU, as the number of neurons in the hidden layers ne increase, the global minimum of the Lægregularized loss goes down until reaching plateau (i.e. adding neurons does not lead an improvement in the loss). This illustrates the sparsity effect of Lg-regularization, where the optimum reached on a very large network is equivalent a much smaller network.
The start of the plateau hence gives measure of sparsity of the global minimum. We show that the minimal number of neurons n, to reach this plateau is determined by a notion of rank Rank, (K₃, K?) of the covariance pairs. We show that Rank, (Ke, Kÿ) S (N + 1), i.c. the plateau must start before N(N + 1) and that the scaling of this upper bound is tight by giving example dataset such that at the optimum Rank, (K,, KT) 2 N2/4. We also present other datasets where the start of the plateau is either constant grows linearly with the number of datapoints. We also observe empirically that the plateau can start at much smaller widths for real data such as MNIST and the teacher/student setting.
2 Setup
We consider fully-connected deep neural networks with L, + 1 layers, numbered from 0 (the input layer) L (the output layer), with nonlinear activation function a R - R (e.g. the ReLU (xx) = max ma, of the network. Given an input dataset {aI,..., xN) } C I of size N, we consider the data matrix X (zo...., ,x,) E R and encode the activations and preactivations of the whole data set by considering the pre-activations (X; W) e R and activations 2 (X; W) 1)
20 ))) Each layer é contains ne neurons and we denote n (nI,..., nl.) the widths

---

given by:
X 26 (X; W) =
31%
Ze(X; W) WiZz--(X;
(X; ( (BL1 (o())
81%
where W (We).= is the collection of ny x (ne-1 + 1)-dim weight matrices We, (Zz) is obtained by applying elementwise the nonlinearity to the matrix Zr, and the scalar 3 E R represents amount of bias (i.e. when 3 = 0 there is no bias, when 3 this definition is equivalent to traditional definition of bias). The output of the network is the pre-activation of the L-th layer Z
We often drop the dependence on the weights W and on the dataset and simply write Ze and Z
We denote fw 12 + R the network function, which maps an input a to the pre-activation at the last layer.
2.1
L-- Lz-Regularized Loss and Representation Cost
Given general cost functional C 1 X.N + R, the Læ-regularized loss DNNs of widths
Lx W) C W)) + A ||]"
where [| is the L2-norm of W understood as a vector. Note that = |Well where F denotes the Frobenius norm. From now on, often omit specify the widths and simply write Cx.
The additional regularization cost should bias the network toward low norm solutions. This bias the parameters leads to a bias function space, which is described by the so-called representation cost Ra(f) defined on functions R + RRL;
Rn(
|W] W:fw=f
min
where the minimum is taken over all choices of parameters W of width n network, with fixed / bias amount, such that the network function fw equals f. By convention, if no such parameters exist then (f) = +
Similarly, given input-output pair X E RROxN, Y E R the representation cost R, R,(X, Y) is:
min Rn (X) WiZz(X.W)=Y
|/]]
with again the convention that if there exists no weight W such that (x(X, W) = Y, then R₂ (X.Y) = +oo. The representation cost Rn naturally describes the bias induced by the L2- regularized loss of DNNs since:
min C(Z,(X; W)) + X ||] = min C(Y) + (Y, W
Y
3 Two Reformulations of the Regularized Loss: Hidden Representation and Covariance Optimization
We now provide two reformulations of the Lz-regularized loss LA (W) and representation cost Rn (X, Y). which both put emphasis on the hidden representations Ze and how they are progressively modified throughout the neural network. The first reformulation holds for general non- non-linearities while the second only applies networks with homogeneous nonlinearities.
3.1 Feature optimization attraction/repulsion
The key observation is that the weights W; can be decomposed as follows:
W₂ Ze 12 + We.

---

(a) Inputs (f= 1)-
(b) Neurons (f 1).
(c) Inputs (e 2).
(d) Neurons (E = 2).
Figure 1: Attraction/Repulsinn: Visualization of the hidden representation Z and Zz of
ReLU DNN at the end of training (i.e. after T = 20k steps of gradient descent on the original loss Cx) on 3 digits (7,8 and of MNIST [T5] along with the attraction force in green and repulsion force in red (both forces are approximated with Tikhonov regularization). For both layers, we plot in (a) 42 lines (each corresponding to a datapoint) and in (b) and (d) the PCA 50 columns (each corresponding neuron in the layer & == 1 or = 2). We observe a clustering of the inputs according their digit, and of the neurons along 3 rays in grey dashed lines.
and (c) the PCA of the
the
where the residual matrix We is orthogonal Zi-1. i.e. W 0, and (-) the Moore-Penrooe pseudo-inverse. This stems from the fact that We W.P 1mp2. + W, where We == WyP (ImZ7_ and P Pim2y resp. P ((mm2g_))
1)+ the orthogonal projection ImZ resp. the orthogonal
complement of Im2g-1: :: one concludes using the facts that Pimzz_ = 2 (Z%_1)* and Ze = W.Zg-1-
Note that the matrix We does not affect either the hidden representations Ze nor the output Zr.. Besides, the Frobenius norm of We can be rewritten |Wel = 1Ze (Zi_,) 13 + [Wll When minimizing the Le-regularized cost, is therefore always optimal to consider null residual matrices We = 0, resulting a reformulation of the cost which only depends on the pre- arcaviiivtsoons Ze: Proposition 1. The infimum of (x(W) = ((Zz(X; W)) + W| over the parameters W e R." is equal to the infimum of
L (3 71......,,..- = O(Zz) Σ
Ze Z7 1'
over the set of hidden representations Z = (7t) such that Ze E RRexN, ImZ C
Im (2z),, with the notations Zī = ((13 (117 and Zi
X 31%
(Ze) 31
Furthermore, W is local minimizer of Lx then (7 (X; W), ..., Z (X; W)) is a local minimizer of Ex. Conversely, keeping the same notations, if (Ze)t=1..... is local minimizer of E then
W = (Z)_1))))= is a local minimizer of Lx.
Note that one can also reformulate the representation cost:
Σ 21 (ZZ-1)) min ZEZ,Z.=Y
R₂ Ra(X (X,Y) =
E=1
The representation in terms of the output and hidden representations have several interesting properties, especially when it comes to minimization:
1. The optimization becomes local in the sense that all terms and constraints depend either only
As result, the (projected) gradient of the loss (2, Zr.) w.r.t. to Ze only depends on Z 1, 2r and Ze+1. This is in contrast to the optimization of Lx(W), where the gradient of (Zz,) with respect to We depends all parameters Wi,.... Wi.
the output cost C(Zr.) or on two neighboring terms (e.g. Zx (2%_,)

---

111 represents a 'multiplicative distance' between Ze and 2z-1
2. The value Ze (Z7
(in contrast to the 'additive distance' || Zi=ıll;>:: the representation Zz therefore interpolates multiplicatively between Zz-1 and Ze+1- This is most obvious for linear networks (i.e. o id and | 0): in this case, one can check that at any global minimizer, the covariances of the hidden layers equal 2 Ze = (" 2 1)
interpolating between the input covariance X" X and output covariance 2I.
3. A lot of work has been done to propose biologically plausible training methods for DNNs
[1, in contrast to backpropagation which is not local. A line of work [21 (2], propose a biologically plausible optimization technique which minimizes cost which closely
resembles our first reformulation, with the multiplicative distances
Ze (zg_1)
replaced
Due to this change, there is no direct correspondence between the networks trained with this biologically plausible technique and those trained with backpropagation. If one could extend this training technique to work with multiplicative distances one could guarantee such a direct correspondence.
by additive ones Iee - -27-- I
4. The optimization leads to an attraction repulssoon algorithm. If we optimize only on the term Ze and fix all other representations, the only two terms that depend on Ze are
Ze (Z%_1) ||= and /eez1 (Zg)+ The former term is attractive it pushes the representations Ze towards the origin (and hence pushes the representations at depth & of every imput towards each other), especially along directions where 2 is small. The latter term is repulsive as it pushes the representations 27 away from the origin, especially along directions where Ze+1 1 is large.
5. This attraction repulsion process is similar to the Information Bottleneck theory [24]: the repulsive term ensure that Z, keeps enough information about the inputs to reconstruct Ze+1. while the attractive term pushes Ze to keep as little information as possible.
The attraction and repulsion forces of of the E-th layer are the derivative 0z, Ze (Z "1 and
dz. Ze+z (Zz)+ 2
which are both ny x N matrices. One can visualize these forces either column by column (each column corresponding to datapoint i ,,...,,, .N or line by line (each line corresponding to a neuron & = 1,..., n2.). These two visualizations of the forces are presented in Figure for the two hidden layers of a depth L network, projected the largest principal components of the columns resp. lines of Zz. Figures
how the inputs corresponding to different classes are pushed away from each other, leading to a clustering effect. Figures [ and 1d show that the neurons naturally align along rays starting from the origin. This happens for homogeneous linearirs,,,,ss, such as the ReI.U in this example, because if two neurons k; k have IR, then their attractive and repulsive forces will also be proportional with the same scaling a. As a result, the neuron is stable, i.c. the attraction and repulsion cancel each other, if and only if the neuron k' is stable.
proportional activations, i.c. Ze, aZi, for some
This phenomenon can be interpreted as a form of sparsity: a group of aligned neurons can be replaced by a single neuron without changing the resulting function Zz. Can we guarantee a degree of sparsity in the hidden representations? Can we bound the number of aligned groups in a neuron? In the next section, we introduce a further reformulation of the loss which allows us to partially answer these questions.
3.2 Covariance learning : partial convex optimization for positively homogeneous nonlinearities
The loss of the first reformulation C depends on the hidden representations Ze and Zj only through
the covariances K₂ = z3 7r and Ky = (zz)² T zy, since Ze (Z%_) = Tr Ke (K Hence, we provide a second reformulation expressed in terms of the tuple of covariance pairs KT), .. (K))...,,,K_1,, ((--1KK-1)) and the outputs Zz. Using the notations Kī =x"Xx + 821NNN
5

---

and K2 Zr we define:
ZL) +
Σ Tr Ke (Kz_1)") 2=1
It remains identify the set (X) of covariances K and outputs Zr. which be represented by a width n network with inputs X. For positively homogeneous nonlinearities of degree 1 such as the ReLU (i.e. when (AAr)= (a) for any positive A), the set K (X) can be expressed using the notion of conical hulls.
Definition 2. The conical
hull of c R is the set cone (S2) := the set
{E Ogwi 2 0, oz 2 O, wi EQ and its m-conical hull for m 2 cone (D) = (Σ Ogwi : og 2 0, @
Note that by Caratheodory's theorem for conical hulls, conem (9) = cone (S2) for any m 2 d. We proceed the description of the set K2 (X) and obtain the second formulation of the T2 regularized loss and of the representation loss Rr in terms of covariances:
Proposition 3. For positively homogeneous mon-linearitien a, the infimum of Cx(W) = C(Zr(X; W)) + I|| over the parameters W E IR. is equal to the infimum over Kn (X)
of
C ZL) C(Z)) + Σ Tr Ke (KZ-1) (KZ_)*)-
t=1
The set Kr, (X) ) the set of covariances K ((K), Kf), ..... (KL-1, K(.-1) (K),,..,KK...... that for all hidden layer 8 = 1....,
and outputs Z such
the pair (Ke, K?) belongs the (translated) ne-conical hull
S = cone,, (((x=" (x())o()))) x
: ER*)) + (0, 32 INxN),
ImKe C ImK with the notation Kğ = x + 1INNN and ImZz C ImK2-1-
Note that one can also reformulate the representation cost:
Ru (X
min K:KK K:(KY (X)
E Tr Ke (KZ
Remark 4. In contrast the first loss C whose local minima were in correspondence with the local minima of the original loss Lx, the second loss C can in some cases have strictly less critical points and local minima. Indeed, since the map W + (K, Zr) is continuous, if (K)W), Zz (W)) is local minimum, then so is W. However, the converse is not true: we provide a counterexample in the Appendix, i.e. set of weights W of a depth L = 2 network which is a local minimum of Lx and a local minimum C)
such that the corresponding (K, Zz)
Since the dimension of the space of pairs of symmetric N matrices N(N 2 N(N+1) then, by the Caratheodory's 's theorem for conical hulls,
Sny = S = cone ({ (((xx", (x))(()))) : a SN-1)) + (0, 1IxN).
Hence, as soon as ne 2 ((N + 1) for all hidden layers, the set K., (X) does not depend on the list of widths n. We denote
XC(X (KK, Zz) VE 1,...,
(Ke, K?) E S, ImKe
1mkK),,1m2 ImKī-1}
this width-independent set. The following proposition shows that for sufficiently wide networks with a positively homogeneous nonlinearity, training a deep DNN with L2 regularization is equivalent to partially convex optimization over a translated convex cone.
Proposition 5. The set K(X) is a translated convex cone: after the suitable translation, is equal to conical hull. The cost C) (K, Z1.) is partially convex w.rl. to the outputs Zt, and the pairs (Ke, K ). i.e. it is convex if one fixes the other parameters and let only (Ke, K2 ), or ZL, vary.

---

3.3 Direct optimization of the reformulations
natural at this point to wonder whether one could optimize directly over the representations Z (using the first reformulation) or over the covariances K and output Zy (using the second reformulation), and whether this would have an advantage over the traditional optimization of the weights.
For the first reformulation, one can simply use the projected gradient descent with updates given by
Z++1 Pz [Z, (Z)
for any projection Pz to the constraint space 2. For example, projection is obtained by mapping Ze to ZzPimzy_, sequentially from & = 1 to = L. Note however that the loss explodes as the constraints become unsatisfied so that for gradient flow, there is no need for the projections. This suggests that these projections might also be unnecessary as long as the learning rate is small enough. For more details, see Appendix B.1
For the second reformulation, there is obvious way to compute a projection to the constraint space K:: the cone is spanned by an infinite amount of points and we do not have an explicit formula for the dual cone 5 Wolle optimization can be used to overcome the need for computing the projections.
However, these direct optimizations of the reformulations lead to issues of computational complexity and stability. First, the computation of the gradients (Z) and V V Zr.) requires solving a linear equation of dimension N, which is very costly, in contrast to the traditional optimization of the weights W for which the gradient can be computed very efficiently. Second, if zŁ is not full-rank, the computation of its pscudo-inverse (ZZ)* and the projection Pimz; are very unstable. Therefore, we only have finite-precision knowledge of Ze, we cannot reliably compute (Zz)² nor Pimzy-
Although it could be possible to solve these problems (e.g. using the Tikhonov regularization for the unstability problem) and develop efficient algorithms optimize both reformulations efficiently, we decided in this paper to focus on the theoretical implications of these reformulations.
4 Sparsity of the Regularized Optimum for Homogeneous DNNs
In this section, assume that the non-linearity is positively homogenous. Under this assumption, the second reformulation of the loss (and of the representation cost) holds and implies the existence of sparsity phenomenon.
First observe that as the widths n increase, both the global minimizer of the loss minw Lx (W) and the representation cost [X, Y) diminish. We denote by Lx,n the Læ-regularized loss of DNNs with widths n. Recall that the depth is fixed.
Proposition 6. If < n' (in the sense that ne S n' for all E and no = nó and nt, n'yh then
min WER
Cx,( 2 min Lx.
WeR n
anr any X E R and Y E RREXN Rn (x, 2 (X,)).
Proof. Let assume that the parameters W are optimal for width network, the parameters can be mapped to parameters of a wider network by adding 'dead' neurons (i.e. neurons with zero incoming and outcoming weights) without changing the network function fw- nor the norm of the parameters ||]]
For DNNs with positively homogeneous nonlinearities, direct consequence of our reformulation through the hidden covariances is that both the global minimum of the loss LA and the representation cost R2 (X, Y) plateau for any widths such that n, N(N + 1).
Proposition 7. For any positively homogeneous nonlinearity a, any widths n and n' such that n0 T/y nt n'y, and for all E 1,...,, 1, ne, n 2 N(N + for all > 0, we have:
min Cx,n (W) WER
min We
Lx.
Under the same conditions Rn (, Rn (X, Y) for any X _ and Y E g
7

---

30
391
337
384
J00m
Figure 2: Loss plateau: Plots of the train loss (full lines) and test loss (dashed lines) as function of the width for depth L DNNs for different datasets: (left) cross-entropy loss for a subset of MNIST (N 1000) and two values of A; (right) MSE with À 10 on N 1000 Gaussian imputs and outputs evaluated on a fixed teacher network of depth L and width 10( (right). For the right plot we took (the minimum is taken over 3 independent trials, represented by the small blue dots). In both settings, the plateau appears to start around 10, much earlier than N2 10 The regularization term is included in the training loss but not the test, leading to smaller test loss on the right.
Proof. This follows directly from the second reformulation and the fact that by Caratheodory's theorem for conical hulls, S, = S i 2 N(N + 1) (see discussion after Remark
We can therefore define a width width-independent representation cost R(X,y, Y) (which still depends on the fixed depth L) equal the representation cost R, (xX, of any sufficiently wide network.
4.1 Rank of the Hidden Representations
Now that we have revealed the plateau phenomenon, natural question that we investigate in this section is when does this plateau begin. In order to do so, we introduce the notion of rank Rank, (K, K%) of a pair of Gram matrices (K) E S which is the minimal number such that
K Σ zz! and K"
( +11NNN
(4.1)
for some 21, . 2k R.,. This notion of rank describes exactly the minimal number of neurons required to recover a set of covariances K:
Proposition 8. Let (K, Zr.) E K((),, then there are parameters W of a width n network with covariances and oulputs K and only if 2 Rank, (Ke, K2) for all e l,...,
We now describe the plateau R {n minwer Cx, minm min Lx (W)) ie. the set of widths n such that the minimum minwer*. CX (..(W) is optimal over all possible widths:
Corollary 9, Let Kmin be the set of covariances sequences (K, ZL) which are global minima of the second reformulation. We have that n E R if and only if there is a (K, ZL) E Kmin such that ne 2 Rank, (Ke, K.)-
Hence, the investigation of Ranks is crucial to understand where the plateau begins; unfortunately, can be difficult to compute. However, from its definition and the Caratheodory'ss theorem for conical hulls (see our discussion after Remark g. we have the following natural bounds:
Lemma 10. For any pair (K, K S, have Rank (K) Rank, (K, K") < N(N 1).
We show in the next section that the order of magnitude of the upper bound is tight. More specifically, we construct a dataset for which any global optimum satisfies Rank, Kf) N²/4. This implies that, in this example, the plateau transition occurs when the number of hidden neurons is of order O(N2). Note however that, in our numerical experiments (see Figure 2 the rank of the global optimum can be much smaller for more traditional dataset such as MNIST.

---

Remark 11. The start of the plateau measures notion of sparsity of the learned network, since the networks learned in the plateau are equivalent a network at the start of the plateau, i.c. large networks are equivalent in terms of their covariances and outputs (K, Zt.) to (potentially much) smaller network.
Even though the set of pairs (Ke, in the cone S that are not full rank has measure zero, the optimal representations (Ke, K3) always lie on the border of the cone S (since the derivative of the cost L w.r.t. (Kr, K2) never vanishes) where the rank is lower. More precisely, the rank is determined by the dimension of the smallest face that contains the optimum (e.g. the pairs (Ke, Kz) on the edges of S have rank at most 2 for example, while those on the vertices are rank 1).
We can identify different degrees of sparsity depending on how the rank of the hidden representations scales with the number of datapoints N: if the rank is o(N) the covariances Kg, K2 are low-rank (in the traditional linear sense) and for shallow networks the effective number of parameters (i.e. the number of parameters at the start of the plateau) is of (N))), if the rank is o( (N)N) then for deep networks the effective number of parameters o(N). This could explain why very large networks with "too many parameters' are able to generalize, since their effective number of parameters is of the order of the number datapoints. Very large networks therefore be trained safely knowing that thanks to re-rguularization, the network is able to recognize what is the 'right' width of the network.
4.2 Tightness of the Upper-Bound
In this section, construct pair of input and output datasets X and Y. both in RNx such that for any optimal parameters W of a ReLU network of depth L = 2 with no bias (3 = 0), the rank of the hidden representation Rank, (K1,KT) is greater than N²/4.
Note that one can write the decomposition (4. as CCC and K, Bd B where C (z1,..., = and B = (eLU(()) is obtained by applying elementwise the ReLU to C. Key to our construction is the fact that B is then matrix with non-negative entries: the matrix K₂ completely positive and Rank, (K, K*) can be studied using the CP-rank of K:
Definition 12. A N x N matrix A is completely positive if A = B" B for a x N matrix B with non-negative entries. The CP-rank Rankep (A) of completely positive matrix A the minimal integer & such A B B for k N matrix B with non-negative entries.
When a is the ReLU, the kernel Kg is completely positive for all hidden layers E, and thus max (Rank (Ke). Rankep (K?))= S Rank, (K, )').
In order to obtain the tightness of the upper bound, we proceed in two steps: first we construct completely positive matrix with high CP-rank, and then construct inputs X and outputs Y such that the optimal hidden covariance K KÝ for a depth L 2 network equals the matrix A.
As shown in 77 bi-partite graphs can be used to construct matrices with high CP-rank. We refine this by showing that graphs on N vertices without cliques of 3 or more vertices lead to N x N matrices with Ca-rank equal to the number of edges, and as a corollary, we construct a completely positive matrix with CP-rank equal to ///
Proposition 13. Given a graph G with vertices and edges, consider the x N matrix E with entries Egg = if the vertex is an endpoint of the edge and Eev 0 otherwise. The matrix A= ET E is completely positive and if the graph G contains no cliques of 3 or more vertices then Rankep (A) = k.
Hence, to obtain a completely positive matrix of high CP-rank, it remains to find graph with no cliques and many edges possible. For even N, consider the complete bipartite graph, i.e. the graph with two groups of size N/2 and with edges between any two vertices they belong to different groups. For this graph, the matrix Bx ET E takes the form of a block matrix:
7
1gx I
By
1 1x
where 1s is the N/2 x N/2 matrix with all ones entries. Since this bipartite graph has no cliques 2 and N²/ edges, from the previous proposition, obtain Rankep (Bx) 4.
N²

---

The following proposition shows how for any completely positive matrix (with CP-rank k) there is dataset such that a shallow ReLU network will have a hidden representation pair (K1, KÝ jof rank
Proposition 14. Consider a width-n shallow network (L 2) with ReLU activation, no bias 3 0,
no = N, nı 2 N(N + 1), input dataset XN = IN. and any output dataset Yx such that (Y a completely positive matrix with CP-rank k.
At any global minimum of Ru Ra(Xx, Nx,, Yx), we have Rank, (K1, Kf) k. Furthermore for X small enough, at any global minimum of Xx, CXSE - [Xx:; W) 10--Yxlll Yv + + have Rank, (K1, Kg) 2 k.
By Proposition 14 with the outputs YN BN, the rank of the hidden representations (and the start the plateau) is larger equal to N² This shows that the order N2 of the bound of Lemma 10 is tight when it comes to data-agnostic bounds. However under certain assumptions on the data one can guarantee much earlier plateau.
[4aittioo[[[tto For example, if we instead apply Proposition 14 a task closer to classification, where the columns of the outputs YN E X are one-hot vectors, then (Y Y is (up to permutations of the columns/lines) block diagonal matrix with nt constant positive blocks, which is completely positive with CP-rank equal to the number of classes nz. This is in line with our empirical experiments in Figure 2 where we observe in MNIST plateau starting roughly at width of 10, which is the number of classes.
Another example where the structure of the data leads to an earlier plateau is when the input and output dimensions are both 1, in which case we can guarantee that the start of the plateau grows at most linearly with the number of datapoints N:
Proposition 15. Consider shallow networks (L= = 2) with scalar inputs and outputs (no = n2 1), ReLU nonlinearity, and a dataset X, Y E RIxN Both the representation cost (x,(, Y) and global (W) minimum minw Lx.n(W) ) for any À >> 0 are independent of the width
long as
4N.
More generally, we propose to view the start of the plateau as an indicator of how well a certain task is adapted to a DNN architecture. An early plateau suggests that the network is able to solve the task optimally with very few neurons, in contrast to a late plateau. The fact that the optimal network requires few neurons (and hence few parameters) can be used to guarantee good generalization.
4.3 Conclusion
We have given two reformulations of the loss of Ly-regularized DNNs. The first works for general non-linearity and shows how the hidden representations of the inputs Zi..... ZL-1 are learned to interpolate between the input and output representations, as a balance between attraction and repulsion forces for every layer. The second reformulation for homogeneous non-linearities allows us to analyze a sparsity effect of Le-regularized DNNs, where the learned networks are equivalent another network with much fewer neurons. This effect can be visualized by the appearance of a plateau in the minimal loss as the number of neurons grows, the earlier the plateau, the sparser the solution, since an early plateau means that very few neurons were required obtain the same loss as a network with an infinite number of neurons. We show that this plateau cannot start later than (NV + 1), and then show that the order of this bound tight by constructing toy dataset for which the plateau starts at N² /4, however, we observe that on more traditional datasets, the start of the plateau can be much earlier.
Acknowledgements
C. Hongler acknowledges support from the Blavatnik Family Foundation, the Latsis Foundation, and the NCCR Swissmap.
References
[1] Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-681, 2017.
10

---

[2] Yoshua Bengio, Dong- Hhynn Lee, Jorg Borncheen, Thomas Mesnard, and Zhouhan Lin. Towards biologically plausible deep learning. arXiv preprint arXiv: 1502.044004 2015.
[3] Lenaic Chizat and Francis Bach. A note on lazy training in supervised differentiable programming. arXiv preprini 1812.095,, 2018.
[4] Lénaïc Chizat and Francis Bach, Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory. volume 125 of Proceedings of Machine Learning Research, pages 1305-1338. PMLR, 09-12 Jul 2020.
[5] Jeremy Cohen, Simran Kaur, Yuanzhi Li. J Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. International Conference on Learning Representations, 2021.
[6] Zhen Dai, Mina Karzand, and Nathan Srebro. Representation costs of linear neural networks: Analysis and design. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[7] John H Drew, Charles R Johnson, and Raphael Loewy. Completely positive matrices associated with m-matrices. Linear and Multilinear Algebra, 37(4):303-310, 1994.
[8] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias terms of optimization geometry. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 1832-1841. PMLR, 10-15 Jul 2018.
[9] Suriya Gunasckar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[10] Boris Hanin and Mihai Nica. Finite depth and width corrections to the neural tangent kernel, 2019.
[11] Bernd Illing, Wulfram Gerstner, and Johanni Brea. Biologically plausible deep learning but how far can we go with shallow networks? Neural Networks, 1 11::90-101, 2019.
[12] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In Advances in Neural Information Processing Systems 31, pages 8580-8589. Curran Associates, Inc., 2018.
[13] Arthur Jacot, François Ged, Berfin Şimşek, Clément Hongler, and Franck Gabriel. Saddle-to- saddle dynamics in deep linear networks: Small initialization training, symmetry, and sparsity, 2022.
[14] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 69800 2014.
[15] Yann Lecun, Leon Bottou, Y. Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86:2278 - 2324, 12 1998.
[16] Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.02218. 2020.
[17] Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. In International Conference on Learning Representations, 2020.
[18] Dina Obeid, Hugo Ramambason, and Cengiz Pehlevan. Structured and deep similarity matching via structured and deep hebbian networks. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buce E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[19] Greg Ongie and Rebecca Willett. The role of linear layers in nonlinear interpolating networks. arXiv preprint arXiv:2202.00883 2022.
[20] Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. International Conference on Learning Representations, 2020.
11

---

[21] Cengiz Pehlevan, Anirvan M Sengupta, and Dmitri B Chklovskii. Why do similarity matching objectives lead hebbian/anti -eettin networks? Neural computation. 30(1):84-124, 2017.
[22] Shanshan Qin, Nayantara Mudur, and Cengiz Pehlevan. Contrastive similarity matching for supervised learning, Neural computation, 33(5): 100--138, 2021.
[23] Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2667-2690. PMLR, 25-28 Jun 2019.
[24] Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 ieee information theory workshop (itw), pages 1-5. IEEE, 2015.
[25] Greg Yang and Edward J. Hu. Feature learning in infinite-width neural networks, 2020.
12


Reviews:
[{"review_id": "igqho2chdu", "reviewer": "Reviewer_GKt8", "summary": "This paper provided two reformulations of the L2-regularized DNN using the framework of representation cost. The first reformulation characterizes feature learning process in terms of attraction and repulsion, and further established an interesting connection between training a L2-penalized DNN with a partial convex optimization over a translated convex cone. The second reformulation utilizes the covariance learning and provides a mechanism for learning the sparsity effect of the L2-regularization in training of DNN with homogeneous non-linearities.", "questions": "For the second reformulation, it is great to have the understanding of no later than when will we observe the plateau. Could we have any understanding of how early the plateau could occur? I think this might be interesting, especially since an early occurrence of the plateau is observed in many datasets.\n", "limitations": "Please see the comments in the previous 2 sections.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The two reformulations are interesting and lead to insightful understanding on the effect of L2 regularization in DNN trainings.\n\n2. The second reformulation establishes an interesting sparsity result for homogeneous DNN (Proposition 7), and the tightness of is further analyzed.\n\nWeakness:\n\nWhile I enjoy learning these insights and new understandings of the effect of L2 regularization in DNN, I would definitely find it helpful to have more discussions on their implications. Specifically,\n\n1. the first reformulation leads to the attraction-repulsion effects, which could potentially lead to better algorithmic understanding / design. As mentioned in point 3 in the bottom of pp.4, a block (of three layers) cordinate descent type of algorithm could be developed to minimize the multiplicative distances. But how would one deal with the interpolation requirement in the representation costs? While it might be natural to consider a projected gradient descent, going in this direction seems to be a waste of the established decomposition.\n\n2. Proposition 5 establishes the equivalence between training a L2-regularized DNN and a partially convex problem over a translated convex cone. What actual implication could we obtain? What actual benefit can the partial convexity offer?\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WtkW3FoLH0w", "reviewer": "Reviewer_UVbc", "summary": "The authors study deep feedforward neural network training with $\\ell^2$\nregularization on the weight matrices. They reformulate this cost (via\nan equivalent optimization problem) in two different ways, in order to get\ninsight into the features that are learned at optimality. The first\nreformulation expresses the network weights in terms of the preactivations, via\nan orthogonal projection trick; the authors interpret the resulting problem in\nterms of the local interactions between neighboring preactivations across\nlayers of the network. The second reformulation builds off the first: it\nreplaces the preactivations with the corresponding covariance matrices, and the\nauthors interpret the resulting cost in terms of the rank constraints imposed\nby this structure when the layer widths are sufficiently large relative to the\nnumber of samples, which implies some sparsity of the optimal features. Small\nexperiments are presented to illustrate the interpretations.\n\n", "questions": "I am not able to understand the claim in line 61 of the appendix that $\\Psi$ is\nnorm-preserving. Can you justify this? It seems like if some features are\npoorly conditioned, the norm of the image of $\\Psi$ will blow up. I am not sure\nabout the correspondence between minimizers asserted in Proposition 1 without\nthis justification.\n\nI was a bit confused about Figure 1 -- are these plots for a network trained on\nthe reformulated loss (i.e. not really a network -- just learning features), or\na standard optimization over the weights $W$? Are these figures showing the\ndifferent attractive/repulsive terms in the trained network, or the initial\nnetwork?\n\nQuadratic overparameterization may be more than is necessary for many tasks,\ne.g. as discussed in [1], or when data have low-dimensional structure [2].\nCan the requirements be relaxed (in principle?) in the latter case? What can\nbe said theoretically in this framework about networks that are less\noverparameterized than quadratic?\n\n[1] https://arxiv.org/abs/2205.10217\n[2] https://openreview.net/forum?id=O-6Pm_d_Q-\n", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n- The reformulation in terms of preactivations is insightful, and gives an\n  interesting framework for understanding global minimizers of the deep network\n  training cost.\n- The authors focus on tools that apply to deep networks, which is important --\n  many works in the theoretical literature are restricted to shallow networks.\n\n## Weaknesses\n\n- It is slightly unclear what to conclude from the authors' reformulations and\n  analysis. The authors discuss the fact that the reformulated optimization\n  problems are not computationally useful, given the undesirable scaling with\n  the number of data samples relative to training the network weights (section\n  3.3); for the second reformulation, there is no correspondence between the\n  objective landscapes of the original and reformulated problem (and see a\n  question below about the first reformulation). It could be helpful to see\n  some experiments on toy data where the scaling is less of an issue to see\n  whether or not the reformulated landscapes empirically have some similarities\n  to the original landscape, and/or provide useful insights.\n- The analysis is focused on understanding learned features in the network, but\n  it does not involve any specific structural assumptions on $Y$ and $X$. It\n  would be interesting to see if such assumptions can be made, and accordingly\n  the conclusions of the second reformulation in Section 4 could be\n  strengthened.\n\n\n## Minor Issues\n\n- line 78: is the 'plus one' in the weight matrix dimensions definition\n  misplaced? (the weights multiply the 'superscript sigma' preactivations,\n  which are the lifted ones)\n- line 112: orthogonal complement\n- Proposition 1 proof: there is a typo in the definition of the $\\Psi$ map (the\n  typo is repeated in other contexts in the proof).  The typo extends to the\n  statement of the proposition in the main paper, unless I am missing\n  something.  Also in the proof, there are missing $r$ superscripts on some\n  losses. \n- line 137 (item 2): how are these fractional powers to be interpreted for the\n  generally non-square features/input data?\n- Proposition 3: the usage of the $\\mathrm{cone}$ operator doesn't match the\n  way the notation is used above (are the braces and parentheses accidentally\n  placed in the wrong order at eqn below line 188 and similar?)\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FyyRvj78aNX", "reviewer": "Reviewer_LnjM", "summary": "This paper studies the minima of the loss of $L_2$ regularized fully-connected DNNs. They show that the loss in terms of the parameters can be reformulated into a loss in terms of the layerwise activations of the training set, which has an attraction/repulsion problem formulation. For positively homogeneous nonlinearities, they show that the loss can be further reformulated in terms of the covariances of the hidden representations, which take the form of a partially convex optimization over a convex cone. ", "questions": "Some typos:\n- Line 124 $\\mathcal{L}^r_{\\lambda}$, should be $\\mathcal{L}_{\\lambda}$?\n- Line 130, $\\mathcal{L}_{\\lambda}(Z_1, \\dots, Z_L)$ should be $\\mathcal{L}^r_{\\lambda}(Z_1, \\dots, Z_L)$?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The two reformulations of loss of $L_2$ regularized DNNs are very novel, which may be helpful for our understanding of DNNs.\n- The second reformulation has some implications for the sparsity of the local minimum of homogeneous DNNs.\n\nWeaknesses:\n- All the theoretical results are limited to the minima of the loss of $L_2$ regularized NN, i.e. based on the assumption that the minima can be achieved. They also assume the minima can perfectly interpolate the dataset.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept