Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoff
Authors: Arthur Jacot
Venue: NeurIPS 2023 poster (2023)
Keywords: Feature Learning
Symmetry Learning
Theory of Deep Learning
Weight Decay
TL;DR: We describe the low-dimensional features learned by large depth DNNs, using a Taylor expansion of the representation cost around infinite depth.

Abstract: Previous work has shown that DNNs with
large depth $L$ and $L_{2}$-regularization are biased towards learning
low-dimensional representations of the inputs, which can be interpreted
as minimizing a notion of rank $R^{(0)}(f)$ of the learned function
$f$, conjectured to be the Bottleneck rank. We compute finite depth
corrections to this result, revealing a measure $R^{(1)}$ of regularity
which bounds the pseudo-determinant of the Jacobian $\left\|Jf(x)\right\|\_\+$
and is subadditive under composition and addition. This formalizes
a balance between learning low-dimensional representations and minimizing
complexity/irregularity in the feature maps, allowing the network
to learn the `right' inner dimension. Finally, we prove the conjectured
bottleneck structure in the learned features as $L\to\infty$: for
large depths, almost all hidden representations are approximately
$R^{(0)}(f)$-dimensional, and almost all weight matrices $W_{\ell}$
have $R^{(0)}(f)$ singular values close to 1 while the others are
$O(L^{-\frac{1}{2}})$. Interestingly, the use of large learning rates
is required to guarantee an order $O(L)$ NTK which in turns guarantees
infinite depth convergence of the representations of almost all layers.

Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoff
Arthur Jacot
Courant Institute of Mathematical Sciences
New York University
New York, NY 10012 arthur. jac.tanyu.u.........o. edu
Abstract
Previous work [Jac23] has shown that DNNs with large depth L and L2- regularization are biased towards learning low-dimensional representations of the inputs, which can be interpreted as minimizing a notion rank (f) the learned function f. conjectured to be the Bottleneck rank. We compute finite depth corrections to this result, revealing a measure R()) of regularity which bounds the pseudo-determinant of the Jacobian [Jf(x)] and is subadditive under composi- tion and addition. This formalizes balance between learning low-dimensional representations and minimizing complexityirregulaiiy in the feature maps, al- lowing the network to Iearn the 'right' inner dimension. Finally, prove the conjectured bottleneck structure in the learned features as + oc: for large depths, almost all hidden representations are approximately R( (f)-dimensionaal and almost all weight matrices We have R(d) (f) singular values close to I while the others are O Interestingly, the use of large learning rates is required guarantee order ((L) NTK which in turns guarantees infinite depth conver- gence of the representations of almost all layers.
Introduction
can be defined for any model and de- scribes the bias in function space resulting from the minimization of the 72-norm of the parameters. While it can be computed explicitly for linear networks [DKS2I or shallow nonlinear ones [Bac17), the deep non- non-linear case remains ill-understood [TGHG22]
The representation cost L) ming.fo=/ | DKS21
of DNNs with homogeneous nonlin- earity converges to a notion of rank over nonlinear functionslim R(f:L.
Previous work [Jc223) has shown that the representation
L R()) Over large set of functions f. the limiting representation cost ((()) (f) was proven the so-called Bottleneck (BN) rank Ra (f) which the smallest integer & such that f 44. - Bd.. can factored = Rdi. -,, I N, Rddou with inner dimension (it is conjectured to match everywhere). This suggests that large depth Ingreeguariized DNNs are adapted for learning functions of the form f = g with small inner dimension.
This can also be interpreted as DNNs learning symmetries, since function f Ω + BRdw with symmetry group (i.c. xx) = f(x)) can be defined mapping the inputs Ω to embedding of the modulo space 9/G and then to the outputs RRdost, Thus function with lot of symmetries will have a small BN-rank, since Rankax(J) < dim (9/G) where dim (9fa) is the smallest dimension 9/G can be embedded into.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

This formalizes the balance between the bias towards minimizing the inner dimension described by R()) and a regularity measure R(1), As the depth grows, the low-rank bias R(O) dominates, but even in the infinite depth limit the regularity R(11) remains relevant since there are typically multiple A problem is that this notion of rank does not control the regularity of f. but results of [Jc23]] suggest that measure of regularity might be recovered by studying finite depths corrections the R(o) approximation. This formalizes the balance between minimizing the dimension of the learned features and their complexity.
Another problem that minimizing the rank ( does not uniquely describe the learned function, as there are many fitting functions with the same rank. Corrections allow to identify the learned function amongst those.
Finally, the theoretical results and numerical experiments of [Jac3 strongly suggest bottleneck
structure in the learned features for large depths, where the (possibly) high dimensional input data is mapped after a few layers to a low-dimensional hidden representation, and keeps the approximately same dimensionality until mapping back to the high dimensional outputs in the last few layers. We prove the existence of such a structure, but with potentially multiple bottlenecks.
1.1 Contributions
We analyze the Taylor approximation of the representation cost around infinite depth = oo:
1 R + +L.
R(J.L,L) (R(()(; ((:
The first correction (2()) measures some notion of regularity of the function that behaves sub- additively under composition (f o g) s (f) + (g) and under addition (f + + S (f) + H()) (g) (under some constraints), and controls the Jacobian of f: Vx, 2 log [f((1)) S
RO (S), where |-|, is the pseudo-determinaan, the product of the non-zero singular values.
fitting functions with matching (²(0) which can be differentiated by their R(1) value.
For linear networks, the second correction R(2) guarantees infinite depth convergence of the repre- sentations of the network. We recover several properties of R(2) in the nonlinear case, but we also give counterexample that shows that norm minimization does not guarantee convergence of the representation, forcing us to look at other sources of bias.
To solve this issue, show that O(L learning rate forces the NTK to be O(L) which in turn guarantees the convergence as L + 2o of the representations at almost every layer of the network.
Finally we prove the Bottleneck structure that was only observed empricially in [Jac23]: : we show that the weight matrices Wz are approximately rank (f), more precisely We has ()) sin- gular values that are O(I.+t) close to 1 and all the other are O(I=t). Together with the O(L) NTK assumption, this implies that the pre-activations (x( of general dataset at almost all layer approximately ((0) dfm-diimsi,, more precisely that the k + 1-th singular value of ae is OII-+).. +).
1.2
Related Works
The representation cost has mostly been studied in settings where an explicit formula can be ob- tained, such as in linear networks (DKS21, or shallow nonlinear networks [Bac17), or for deep networks with very specific structure [OW22 LJ22]. A low rank phenomenon in large depth L2- regularized DNNs has been observed in [VS222..
Regarding deep fully-connected networks, two reformulations of the representation cost optimiza- tion have been given in [GHG222 which also shows that the representation becomes independent of the width as long as the width is large enough.
The Bottleneck structure that we describe this paper similar to the Information Bottleneck theory TZZ15. It is not unlikely that the bias towards dimension reduction in the middle layers of the network could explain the loss of information that was observed in the first layers of the network in (TZ55..

---

2 Setup
In this paper, study fully connected DNNs with I + 1 layers numbered from 0 (input layer) to L (output layer). The layer & E {O...., ......,,] L} has ne neurons, with no = dip the input dimension and n dout the output dimension. The pre-activations āg(x) E m and activations ae(x) I2 defined by
(o(r)
āe(x) Wiar-1(s)+
ae(x) a (āz(z)),
for the ny X Ri-1 connection weight matrix We, the re-dim bias vector by and the nonlinearity - R applied entry-wise to the vector (g(x). The parameters the network are the collection of all connection weights matrices and bias vectors 0 = (W1, bi. Wt,br) The network function fo Rd + idout is the function that maps an input to the pre-activations of the last layer ā (1).
x
if 20
We assume that the nonlinearity is of the form (x)
for some a E (-1,1)
oz otherwise
(yielding the ReLU for a = 0), as any homogeneous nonlinearity (that is not proportional to the identity function, the constant zero function the absolute function) matches o, up scaling and inverting the inputs.
The functions that can be represented by networks with homogeneous nonlinearities and any finite depth/width are exactly the set of finite piecewise linear functions (FPLF) [ABMMI8] HL [LXZ18).
Remark 1. In most of our results, we assume that the width is sufficiently large so that the repre- sentation cost matches the infinite-width representation cost. For a dataset of size N, width of ((N + 1) suffices, as shown JGHG22) (though a much smaller width is often sufficient).
2.1 Representation Cost
The representation cost R[f; L) is the minimal squared parameter norm required to represent the function f over the input domain Ω:
R(IS,,) L)
min | 0:fon=
where the minimum taken over all weights of depth L network (with some finite widths M1..... #L-1) such that fe(x) = f(x) for all x E Ω. If no such weights exist, we define R(f xc.
The representation cost describes the natural bias on the represented function fo induced by adding L2 regularization on the weights 6:
min C(Jo) + A 11011 = min C()) + AR(J:2, 0
for any C' (defined functions Ω H Rdo)) and where the minimization the right is over all functions f that can be represented by depth L network with nonlinearity a.
For any two functions f.g. we denote f - the function h such that y h f. assuming it exists, and we write R(f - g: L) = R(h; f(2), L).
Remark 2. The representation cost also describes the implicit bias of networks trained with the cross-entropy loss [SHN+ 18 GLSSI8 CB20).
3 Representation Cost Decomposition
Since there are no explicit formula for the representation cost of deep nonlinear networks, we pro- pose to approximate it by Taylor decomposition in t/2 around L cc. This is inspired by the behavior of the representation cost of deep linear networks (which represent matrix as a product Ap Wr Wi), for which explicit formula exists IDKS21I:
RankA
R(A; L) = min
|10||
||
2/2 = Σ
8:4=Ao
1=1
3

---

where I1-1 is the Ly Sy-haatteen norm, the Lp norm on the singular values s, of A.
Approximating st = =1+ i log + 2. (log 3)² + O(L we obtain
A L) A + 2 log || + 2L
|log_ AT ATAl + 0).
where log., is the pseudo-log, which replaces the non-zero eigenvalues of A by their log.
We know that gradient descent will converge to parameters 0 representing a matrix Ag that locally minimize the loss ((A) + XR( AA L.). The approximation R(A; L.) R LRankA fails to recover the local minima of this loss, because the rank has zero derivatives almost everywhere. But this problem is alleviated with the second order approximation R( L) = LRankA + 2 log [44,- The minima can then interpreted as first minimizing the rank, and then choosing amongst same rank solutions the matrix with the smallest between minimizing the rank and the regularity of the matrix
Changing the depth allows one to tune the balance
3.1 First Correction: Regularity Control
As a reminder, the dominating term in the representation cost R is conjectured in [Jac23] to converge to the so-called Bottleneck rank R (ff: which is the smallest integer & such that can be decomposed as f = Ω _ R _ Rdout with inner dimension k and where and h are FPLF. A number of results supporting this conjecture are proven in [Jc23]: a sandwich bound
Ranks < Rº (f: S Rank (J;9)
for the Jacobian rank Ranks(f:9) max, RankJ f (I)) and three natural properties of ranks that R(O) satisfies:
1. R (f o 9; S min (R ())))
2. R (f + 92 S (f) + R()) (g).
3. R( (I + Ar; Ω) = RankA for any full dimensional and bounded Ω
These results imply that for any function f & A vo that is linear up to bijections o, v. the conjecture is true (((0) (2; = Rank (N: (f: = RankA.
The proof of the aforementioned sandwich bound in [Jac33] actually prove an upper bound of the form BN (f: O(1) thus proving that the R( term is upper bounded. The following theorem proves lower bound on R()) as well as some of its properties:
Theorem 3. For all inputs x where RankJ = R(O) ( 2 2 [f(())) further- more:
1. If ( (f o = (f( = (g), then R (f g) - (() (f) + (() R
2. If (()) (f+ g) = (f) + R(O) (g), then Rf < ( + (g)
3. If PImAT and AΩ are k = RankA dimensional and completely positive (í.e. they can be embedded isometrically into T. for some mi), then R()) (x + Ax; Q) = 2 log |A|
Notice how these properties clearly point to the first correction (f) measuring a notion of reg- ularity of f instead of a notion of rank. One can think of Izzrreglaarizdd deep nets learning functions ff that minimize
min C((()) + XL) (F)
The depth determines the balance between the rank regularization and regularity regularization. Without the (20))ttmm, the above minimization would never be unique since there can be multiple functions f with the same training outputs f(X) with the same rank (f).
Under the assumption that ( only takes integer value the above optimization can be rewritten as
ALk + min O.1.....
min
C(f(X)) XR.
(f)=k

---

2.0
Rank
Renk)Maa) -2
RankiMi,))
s(W,))
RankiMLa))
1.0
3. 32
21 34
D.
0.0
0.0
60
40
1.5
s(W)
20
0.5
0.6
0.0
(a) Parameter norm and depth
(b) Bottleneck structure at different depths.
Figure 1: (a) Plot of the parameter norm at the end of training (A = 0.001) over a range of depths, colored acoording to the rank (# of sing. vals above 0.1) of the weight matrices W1/2 the middle of the network, and marked with a dot ' or cross 'x' depending on whether the final train cost is below above 0.1. The training data is synthetic and designed to have optimal rank k- 2. We see different ranges of depth where the network converges to different rank, with larger depths leading to smaller rank, until training fails and recover the zero parameters for 25. Within each range the norm ||ø]| is well approximated by a affine function with slope equal to the rank. (b) Plot of the singular values of We throughout the networks for 4 trials, we see that the bottleneck structure remains essentially the same throughout each range of depth, with only the middle low-rank part growing with the depth.
Every inner minimization for rank that is attained inside the set { ( k} corresponds to a different local minimum. Note how these inner minimization do not depend on the depth, suggesting the existence of sequences of local minima for different depths that all represent approx- imately the same function f, can be seen in Figure We can classify these minima according to whether they recover the true BN-rank A- of the task, underestimate or overestimate it.
In linear networks [W23]] rank underestimating minima cannot fit the data, but it is always possi- ble fit any data with a BN-rank 1 function (by mapping injectively the datapoints to a line and then mapping them nonlinearly to any other configuration). We therefore need to also differentiate between underestimating minima that fit or do not fit the data. The non-fitting minima can in theory be avoided by taking a small enough ridge (along the lines of [W223). but we do observe them empricially for large depths in Figure]
In contrast, we have never observed fitting rank-underestimating minima, though their existence was proven for large enough depths in [Jac23]. possible explanation for why GD avoids these minima is their R(!) value explodes with the number of datapoints N, since these network needs to learn a space filling surface (a surface of dimension l < k- that visits random outputs ys that sampled from k* -dimensional distribution). More precisely Theorem 2 of [Jac23] implies that the R1(1) value of fitting BN-rank I minima explodes of datapoints N grows, which could explain why we rarely observe such minima in practice, but another explanation could be that these minima are very narrow, as explained in Section 4.1
rate of 2(1 A log N as the number
In our experiments we often encountered rank overestimating minima and we are less sure about how to avoid them, though it seems that increasing the depth helps (see Figure [T, and that SGD might help too by analogy with the linear case [W]23]. Thankfully overestimating the rank less problematic for generalization, as supported by the fact that it is possible to approximate BN-rank k* with higher rank function with any accuracy, while doing so with low rank function requires pathological function.
5

---

In linear networks the second correction (A) = 1 logg Al'All plays an important role, as it bounds the operator norm of A (which is not bounded by (A) RankA nor ( 2 log [AI,), thus guaranteeing the convergence of the hidden representations in the middle of net- work. We hoped at first that R?(2) would have similar properties in the nonlinear case, but we were not able to prove anything of the sort. Actually in contrast to the linear setting, the representations of 3.2 Second Correction
We now identify few properties of the second correction R(2);
Proposition 4. If there is a limiting representation as L 0 in the optimal representation of f, then R(2) (f) 2 Furthermore:
If ( o g) ( R and R e g) = R + (()) then
V [ (g)g) S. SV + (g)
2. If ( (f+ (f)++)) (g) and =
then (
9) - R (f) (())) (g).
3. If A is k-
and completely positive all p E [0, 11, where A has its non-zero singular taken to the p-th power, then R + Ax; 52) = logg, AT All.
While the properties are very similar to those of R the necessary conditions necessary to apply them are more restrictive. There might be case where the first two terms R(()) and R( do not uniquely determine a minimum, in which case the second correction R(2) needs to be considered.
the network can diverge as - oo, which explains why the R(2) does not give any similar control, which would guarantee convergence.
3.3 Representation geodesics
One can think of the sequence of hidden representations ãi, , âr. path from the input repre- sentation to the output representation that minimizes the weight norm ||e'll required map from one representation to the next. As the depth L. grows, we expect this sequence to converge to form of geodesic in representation space. Such an analysis has been done in [Owh20] for ResNet where these limiting geodesics are continuous.
Two issues appear in the fully-connected case. First a representation ãe remains optimal after any swapping of its neurons or other symmetries, but this can easily be solved by considering represen- tations Org up orthogonal transformation, i.e. focus the kernels K2, a²(x)² áz(v)- Second the limiting geodesics of fully-connected networks are not continuous, and as such they cannot be described by local metric.
We therefore turn to the representation cost of DNNs to describe the hidden representations of the network, since the f-th pre-activation function (( Ω + R in a network which minimizes the parameter norm must satisfy
R(;; 2, L.) 0,,6) + R(a(ā)) + f; e)-
Thus the limiting representations ā lim ātg (for sequence of layers f, such that lim 41/2 = E (0, 1)) must satisfy
(f; = (ā,: = (o(áp) - f: RO)) (f:S) = (a.) (o(āp) f:
Let us now assume that the limiting geodesic is continuous at p (up orthogonal transformation, which do not affect the representation cost), meaning that any other sequence of layers E converging the same ratio p E (0, 1) would converge to the same representation. The taking the limits with two sequences lim 4 = p lim & such that lim Ez l, +oo and and taking the limit of the equality
R(f R(āe, l,lz) R((((ee)) + +āg āzg - ( ++(o(á))) + f. L ft)).

---

we obtain that (o (āp) + Ep: = (f) and R (ā,) - dz: = O. This implies that (ā(x)) = a(x) at any point x where RankJ = (f: thus (id; (,()) (f and ( (2)) = 0 if RankJ (f: for all Ω.
3.3.1 Identity
When evaluated on the identity, the first two terms R (id; S2) and (id; Q2) describe properties of the domain f2.
For any notion of rank, Rank(id; 92) defines a notion of dimensionality of Q. The Jacobian rank Rank (id; S2) = m dim T252 is the maximum tangent space dimension, while the Bottleneck rank R (id; 52) is the smallest dimension Ω can be embedded into. For example, the circle 82-1 has Rank (id; ( 1 and Rank B.v (id; S2) 2.
On a domain f2 where the two notions of dimensionality match R [2) = Rankgy (id: Q2) = k, the first correction R (id: 92) is non-negative since for any I with dim T,2 = k, we have (id; Q2) 2 log Pr.l4 0. The (id;; Q2) value measures how non-planar the domain 12 is, being 0 only if 52 is k-planar, i.e. its linear span is k-dimensional:
Proposition 5. For domain with Rank, (id: 92) RankøN (id: (2) k, then (id) S2) 0 if and only Q is k-planar and completely positive.
This proposition shows that the R()) term does not only bound the Jacobian of f as shown in Theorem but also captures properties of the curvature of the domain/fumction.
Thus ratios p where the representation geodesics converge continuously, the representations (92) are & R (f; 1t)-planar, proving the Bottleneck structure that was only observed em- pirically in [Jac23]. But the assumption of convergence over which we build this argument does not hold in general, actually we give in the appendix an example of a simple function f whose optimal representations diverges in the infinite depth limit. This is in stark contrast to the linear case, where |log, A All guarantees convergence, since bounds the op- erator norm of A. To prove and describe the bottleneck structure in nonlinear DNNs, we therefore need turn to another strategy.
the second correction (2(2) (A)
Bottleneck Structure in Large Depth Networks
Up now we have focused on one aspect of the Bottleneck structure observed in [Jac3]]: that the representations (x(X) inside the Bottleneck are approximately k-planar. But another characteristic of this phenomenon is that the weight matrices W, the bottleneck have dominating singular values, all close to 1. This property does not require the convergence of the geodesics and can be proven with finite depth rates:
Theorem 6. Given parameters 0 of a depth L network, with |101] KL + and point x such that RankJ [x()) = k, then there are we x Seemi-Jorthonome V, such that Eken ||W,, - VVV 11 C1 2og [oglJ fo(x)) thus for any E (0,1) there at least (1 L
layers l with
W v2V2, C1 22-220 2og [oog)J
pL
Note how we not only obtain finite depth rates, but our result has the advantage of being applicable to any parameters with sufficiently small parameter norm (close to the minimal norm solution). The bound is tighter optimal parameters in which case e₁ (f)) but the theorem shows that the Bottleneck structure generalizes to points that are only almost optimal.
To prove that the pre-activations (x(X) are approximately k-dimensional for some dataset X (that may or may not be the training set) we simply need to show that the activations ax-1(X) do not diverge, since âz (X)
Wrat-1(X) + be (and one can show that the bias will be small at almost every layer too). By our counterexample we know that we cannot rule out such explosion in general, however if we assume that the NTK [IGHT8] (L) (x, 2) is of order (I.), then we can guarantee to convergence of the activations a--1 (X) at almost every layer:
7

---

Theorem 7. Given balanced parameters of depth L network, with [1011 2 +L+o, 0i and a point such that Rank.J fo(z) = k then Ir [0( (x, x)] - cL, then Ei | = emax|1.e
H[Jfa(a)1
and thus for all p (0, there at least (1 P)L layers such that
1 lemax{1,e
||a--1 (x)
P k
Note that the balancedness assumption is not strictly necessary and could easily be weakened to some form of approximate balancedness, since only require the fact that the parameter norm ||Well? is well spread throughout the layers, which follows from balancedness.
The NTK describes the narrowness of the minima [JH220], and the assumption bounded NTK thus related to stability under large learning rates. There multiple notions of narrowness that have been considered:
The operator norm of the Hessian H (which closely related to the top eigenvalue of the NTK Gram matrix ( (X, X) especially in the MSE case where any interpolating func- tion || N | (X, X) which needs be bounded by 2/n to have convergence
when training with gradient descent with learning rate 7).
The trace of the Hessian (in the MSE case TrH = 1 Tro which has N been shown to describe the bias of stochastic gradient descent or approximation thereof [DML21 LWA21].
Thus boundedness of almost all activations as L + 00 can be guaranteed by assuming either 1 [X, I cL (which implies (oueTrr(()) < cL) // (x, S cL directly, corresponding to either gradient descent with r7 = 2/cL or stochastic gradient descent with similar scaling of 17).
Note that one can find parameters that learn function with a NTK that scales linearly in depth, but it is not possible to represent non-trivial functions with a smaller NTK (L)) < L. This is why consider linear scaling in depth to be the 'normal' size of the NTK, and anything larger to be narrow.
Putting the two Theorems together, we can prove the Bottleneck structure for almost all representa- tions die (X): Corollary 8. Given balanced parameters 0 of depth L. network with |1@1| < kL + er and set of points .1.....2. EN such that RankJ foln)ff((x)) k and 1 Tr [e(t) s cL, then for all
N
p E (0, 1) there are at least (1 - p) layers such that
8k+1 1 ()((())) s va 2log []((()]
cmax (1
+ vP 1 ()Jfo(
N
PVL
4.1 Narrowness of rank-underestimating minima
We know that the large R(1) value of BN-rank fitting functions is related to the explosion of its derivative, but a large Jacobian also leads to blow up the NTK: Proposition 9, For any point x, we have
0 2L 21
where 82, 0(x x) is understood as dindout dont matrix.
Furthermore, for any two points v. y such that the pre-activations of all neurons of the network remain constant the segment [x, v). then either [1O(I, (1O y)llop is lower bounded by
1 x v|2 || fo(() vー 2/2
8

---

1.00
-4.0
SNWP
5.00
15
23
-0.08
-0.33
-0.32
-0.00
0.00
(a) Spectra of the Wés
(b) PCA of (x(X).
(c) Dist. (o2( (2) - 02 (2 )
Figure 2: A depth L 25 network with a width of 200 trained on the task described in Section with a ridge À = 0.0002. (a) Singular values of the weight matrices of the network, showing two outliers in the bottleneck, which implies that the network has recovered the rank of (b) Hidden representation of the 6-th layer projected to the first two dimensions, we see how images of GD paths do not cross in this space, showing that the dynamics on these two dimensions are self-consistent. (c) The distance ||α)(zo) a2 a2(2)] in the second hidden layer between the representations at fixed point zo (at the white pixel) and another point on a plane orthogonal the axis of rotation, see that all points on the same symmetry orbit are collapsed together, proving that the network has learned the rotation symmetry.
With some additional work, we can show the the NTK of such rank unnkereesttimating functions will blow up, suggesting a narrow minimum:
Theorem 10. Let f : + Rdduu be function with Jacobian rank k* > 1 (i.e. there is E Ω with RankJ (x) = = then with high probubility over the sampling of training set I1.... ... UN (sampled from distribution with support I), have that for any parameters @ of deep enough network that represent a BN-rank function fe that fits the training set fe( = fx,) with norm ||011² = L+ then there is a point a
E Ω where the NTK satisfies
Tr (O)) (x, 2 a
One the one hand, we know that e must satisfy C1 2 (f)) 2(1 - + N but if ej within a factor of 2 of this lower bound e₁ < 4(1 = log N, then the above shows that the NTK will blow up rate N L for positive
The previous explanation for why GD avoids BN-rank fitting functions was that when N is much larger than the depth L (exponentially larger), there is rank- recorrecvvriin function with lower pa- rameter norm than any wank-underestimating functions. But this relies on assumption that GD converges to the lower norm minima, and is only true for sufficiently small depths. In contrast the narrowness argument applies for any large enough depth and does not assume global convergence.
Of course the complete explanation might be a mix of these two reasons and possbily some other phenomenon too. Proving why GD avoids minima that underestimate the rank with rank 1 < k k* also remains an open question.
Numerical Experiment: Symmetry Learning
In general, functions with lot symmetries have low BN-rank since a function f with symmetry group G' can be decomposed as mapping the inputs Ω to the inputs module symmetries 2/6 and then mapping the outputs, thus Rank (f: (2) < dim 9/G where dim 9/6 is the smallest dimension 0/G can be embedded into. Thus the bias of DNNs to learn function with a low BN-rank can be interpreted as the network learning symmetries the rank corresponds to failing to learn all symmetries of the task, while underestimating the rank can be interpreted as the network learning spurious symmetries that not actual symmetries the task.
the task. With this interpretation, overestimating

---

To test this idea, we train network to predict high dimensional dynamics with high dimensional symmetries. Consider the loss C(v) = || (ww" + E']l where w E Hd a fixed unit vector and E' is a small noise d x d matrix. We optimize e with gradient descent to try and fit the true vector w (up to a sign). One can think of these dynamics as learning a shallow linear network vo with a single hidden neuron. We will train network to predict the evolution of the cost in time C(v(t)).
For small noise matrix E,, the GD dynamics of u(l) are invariant under rotation around the vector w. As a result, the high-dimensional dynamics of v(()) can captured by only two summary statistics u((v ((w" u) []
www") yell"): the first measures the position along the axis formed by w and the second the distance to this axis [AGJ22]. The evolution of the summary statistics is (approxi-
mately) self-consistent (using the fact that ||0||2 = (wTu) b)² + ||(TT ww") )el P
(, u)²² -8(11112 - 1) 0)² 011
0: [12 ww )oll -8 ||o|| ||[ ww )ol) ((11))
Our goal now is to see whether a DNN can learn these summary statistics, or equivalently learn the underlying rotation symmetry. To test this, we train network on the following supervised learning problem: given the vector (0) at initialization, predict the loss (C(u(1)),.... ((v(T)) over the next T GD steps. For E = O, the function f R -> IR. that is to be learned has BN-rank 2, since one can first map v(0) to the corresponding summary statisties u(v(0)) IR, and then solve the differential equation on the summary statistics (u(I),..., u(T)) over the next T steps, and compute the cost C(u) = || 2(w"n)² + 1 + FII from u.
We observe in Figure 2 that large depth Ingrregularized network trained on this task learns the rotation symmetry of the task and learns two dimensional hidden representations that are summary statisties (summary statisties are only defined up to bijections, so the learned representation match u(v) only up to bijection but they can be recognized from the fact that the GF paths do not cross on the 2D representation).
Conclusion
We have computed corrections the infinite depth description of the representation cost of DNNs given in [Jac23), revealing two regularity R()), R((2) measures that balance against the dominating low rank/dimension bias (())_ We have also partially described another regularity inducing bias that results from large learning rates. We argued that these regularity bias play a role in stopping the net- work from underestimating the 'true" BN-rank of the task (or equivalently overfitting symmetries).
We have also proven the existence of bottleneck structure in the weight matrices and under the condition of a bounded NTK of the learned representations, where most hidden representations are approximately & = ((O) (fo) -dimensional, with only few high-dimensional representations.
References
[ABMM18] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understand- ing deep neural networks with rectified linear units. In International Conference on Learning Representations, 2018
[AGJ22] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. High-dimensional limit theorems for SGD: Effective dynamics and critical scaling. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Infor- mation Processing Systems, 2022.
[Bac17] Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, (811)629-6811 2017.
[BHH59] Jillian Beardwood, J. H. Halton, and J. M. Hammersley. The shortest path through many points. Mathematical Proceedings of the Cambridge Philosophical Society, 55(4):299-327, 1959.
10

---

[CB20] Lénaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Jacob Abemneth and Shivani Agar- wal, 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.
[DKS21] Zhen Dai, Mina Karzand, and Nathan Srebro. Representation costs of linear neural net- works: Analysis and design. In A. Beygelzimer, Dauphin, P. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[DML21] Alex Damian, Tengyu Ma, and Jason D Lee. Label noise sgd provably prefers flat global minimizers. Advances in Neural Information Processing Systems, 34:27449- 27461, 2021.
[GLSSI8] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing im- plicit bias in terms of optimization geometry. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, vol- ume 80 of Proceedings of Machine Learning Research, pages 1832-1841, PMLR, 10- 15 Jul 2018
[HLXZ18] Juncai He, Lin Li, Jinchao Xu, and Chunyue Zheng. Relu deep neural networks and linear finite elements. arXiv preprint arXiv: arXiv:/807.03973 2018.
[Jac23] Arthur Jacot. Implicit bias of large depth networks: notion of rank for nonlinear functions. In The Eleventh International Conference on Learning Representations, 2023.
[JGHI8] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernel: Con- vergence and Generalization Neural Networks. In Advances in Neural Information Processing Systems 31, pages 9580-8589. Curran Associates, Inc., 2018.
[JGH20] Arthur Jacot, Franck Gabriel, and Clément Hongler. The asymptotic spectrum of the hessian dnn throughout training. In International Conference on Learning Repre- sentations, 2020.
[JGHG22] Arthur Jacot, Eugene Golikov, Clément Hongler, and Franck Gabriel. Feature learn- ing in lz-regularized dnns: Attraction/repulsion and sparsity. In Advances in Neural Information Processing Systems, volume 36, 2022.
[LJ22] Thien Le and Stefanie Jegelka. Training invariances and the low-rank phenomenon: beyond linear networks. In International Conference on Learning Representations, 2022.
[LWA21] Zhiyuan Li, Tianhao Wang, and Sanjeev Arora. What happens after sgd reaches zero loss?-a mathematical framework. arXiv preprint arXiv:2110.0691: 2021.
[OW22] Greg Ongic and Rebecca Willett. The role of linear layers in nonlinear interpolating networks. arXiv preprint 200.:0200..08856, 2022.
[Owh20] Houman Owhadi. Do ideas have shape? plato's 'ttoss theory of forms as the continuous limit of artificial neural networks. arXiv preprint arXiv:2008.0390 2020.
[8H Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Sre- bro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1 (9())2222-2878. 2018.
[TVS22] Nadav Timor, Gal Vardi, and Ohad Shamir. Implicit regularization towards rank mini- mization in relu networks. arXiv preprint arXiv:2201.12760, 2022.
[TZ15] Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 ieee information theory workshop (itw), pages 1-5. IEEE, 2015.
[WJ23] Zihan Wang and Arthur Jacot. Implicit bias of sgd in Iz-regularized linear dnns: One- way jumps from high to low rank, 2023.

---

A Properties of the Corrections
A.1 First Correction
Theorem 11 (Theorem from the main). For all inputs x where RankJ = R2 (f; we
have R (f) 2 2log Jf(z) furtherooee
1. If R (ʃ [ ()) 12(0) (g), then ( o o) S
2. If R( gf+ -R (f) R( (g), then (f &
3. If PInAT St and An are k RankA dimensional and completely positive (i.e. they can be embedded with an isometric linear map into 1 for some m), then R (x + Ax;
2 log |AI+
Proof. For the first bound, remember that RU;Ω, 2 L [J/1 therefore
(f:l))
lim R(f:2,
LR. (f:
1-000
RankJ
lim L
Σ
sx(f(())) -1
1.000
1=1
RankJ Σ
2
2oog (JS((z))
where we used s - = e logs
-12 7 log
(1) Since R(f 9g L2) & R(f: L1) + Rig: L2), we have
( ( g;
lim
R(ʃ o g; 9 In + T2) (I11 R()) g;
1
I lim R(f: L1) I, (0) (f: + lim R(g; L2) L22
11
12000
(f: + R2 (g)
(2) Since R(f + 9; < R(f L) + R(g: L), we have
R + 92) = lim R( + 9 Q, (2 L) - LR (f + 9: L
lim R(f; L) (R: lim R(g; L) (I(
L+000
-R (fi + R0)) (g: S2).
(3) By the first bound, we know that (x + Ar 2 2 log |A]4, we now need to show RO) + Ax; log | Let define the of completely positive representations the set of bilinear kernels K(x, y) = x" BB By such that Bx has non non-negative entries for all x (we say that kernel K is completely positive over Q if it can be represented in this way for some choice of B). The set of completely positive representations is convex, since for K(x, y) = x BT By and ((x y) = TT fT By, we have
Kx,, 4) + K K(
1 v2
B
B
JJ
2
B
y.
The conditions that there are On and Oout with O Oin
PImAT and O Oont = PimA such that S2 E 1R41 and O OuutAl E R&f is equivalent to saying that the kernels K (2, v) x" PImATyy and Kmut (x. v) x AT Ax completely positive over Ω.
By the convexity of completely positive representations, the interpolation K, = pk + (1 p) K out is completely positive for all [0, 1]. Now choose for all depths L and all layers l = 1, ..... L
12

---

matrix BL,e such that K Ky=4 (2, (2=4(2,)) = x²' x='B,, BL.Ey and then choose the weights We of the depth L network as
We = BL,
using the convention Br,0 = Id... and BL, = Lout. By induction, we show that for any input E S2 the activation of the 8-th hidden layer is BL,E.. This is true for l = 1, since W Br,1 and therefore (x) BI,1 which has positive entries so that (x)
(x) Br, Then
by induction
pe (x) (x) BI,BB -,, B1, = BL,E%
which has positive entries, so that again q¹ (x) a (x)) BL, In the end, we get p(l) (xx Ax as needed.
Let us now compute the Frobenius norms of the weight matrices |Welllr = Tr BL. (Bi...BL..))) as + oc, remember that B BL,E am AA) A. therefore the matrices B., BI,E and BL_e-1 1L, converge to each other, so that at first or- der BL BL.--1 converges to PIMAT, so that |Well + RankA, so that 1I 1i= IRankA A converges finite value -- To obtain this finite limit, need to study approximate the next order
RankA
W/ 3 RankA
Σ (, +0( i=1
= loog BL, BL,,--) + 2
log BL, BL,e - log 1L,,-1 + O(L
But as we sum all these second order terms, they cancel out, and we are left with
Σ Elwil LRankA = lolog |A4 2 lol Ima + +(L-)).
We have therefore build parameters that represent the function r + Ar with parameter norm |1011- = A 2og |4 +OL=")), which upper bounds the representation cost, thus implying that (x Ar; 12) log A| as needed.
A.2 Identity
Proposition 12 (Proposition from the main). For domain with Rank fank)(id: (id: 52)
Rank (id: Q2 k, then R()) (id: Ω) if and only if f k-planar and completely positive.
Proof. First if Ω is completely positive and k-planar one can represent the identity with depth L network of parameter norm Lk, by taking W1 = O, Wt Pimó. Wt O where O is the m x P Pspant2- Thus R2(1) (id; Q) (and all other corrections as well).
so that OΩ C R and Oº O
We will show that for any two points z, E Q with k-dim tangent spaces, their tangent spaces must match if R()) (id; ?) 0.
Let A (a (x) r.a and B Jall-1) (1) be the be the Jacobian of the last hidden activations restricted to the tangent spaces, we know that
Pr. WLA
Pr,a = WLB
so that given any weight matrix W,, whose image contains T,Ω and T,Ω, we can write
A = W Pr.g
B = WT Pr.n.
13

---

Without loss of generality, we may assume that the span of T.S and TySt is full output space, and therefore that Wa W is invertible.
Now we now that any parameters that represent the identity on and has A Jal (x) and B (a(l))) (y) (T,2 must have parameter norm at least
W2 k(L 1) max (2log |A| 2og B1+
Subtracting kL and taking + co, we obtain that
(id: 92) 2 min WL
W k + max m (2log wE Prasl log | Pr,al
we optimize WE only up to scaling (i.e. optimize aW' over a) we see that at the optimum, we always have 1 = k. This allows us to rewrite the optimization as
R (id: Z min max 2log W Preal, + 2og [ Pryal
[W k
The only way to put the first term inside the maximum to is to have WT.WZ = Pr.., but this leads to exploding second term if Pr.g # Pr,9-
Under the assumption of C-uniform Lipschitzness of the representations (that for all e, the functions āg and (at + fa) are C-Lipschitz), one can show stronger version of the above: Proposition 13. For a C-uniformly Lipschitz sequence of ReLU networks representing the function we have
R log loglJf(z)l= + log Jf(y))+
Jfo(v)ll.
Proof. The decomposition of the difference
Jfo(x) -
Wet1 (De(z) De(v)) WeDe-1(0)... D₁ (x)Wi, = Σ WDDL-1(U) (ff(o)
for the x we diagonal matrices De(x) diag(o(á. implies the bound
[Ifo(=) -(f())))fo(()l---- S
W WiDi-1(0) D [We+1 (De(x) De(v)) Well (P)-(()) W
C T-11
([eet1 (D((x) + De(v)) will.)
$
since ||B|]_ <
|||| and (De(x) De(1))² -D((s)-Deum)) Dz(1)).
2
Now since
L [1] <
(
L [[] 2/1
De(x)
with the convention Do(x) = Ld.. and Dz(x) = -don We obtain that
1
L 11) + <11Jf((0)
1W IDD.
t=1
2
Well 2
We - ( [(Dx(zz) - Dz(v)) W.ll
E=1
14

---

This implies the bound
L [1) 8/ + +L + (
11012= 2
2
and thus
R 2 log [f(())] + log
-
A.3 Second Correction
Proposition 14 (Proposition 4 from the main). If there is a limiting representation as L + 0 in the optimal representation of f. then R 2 0. Furthermore:
1. If R R g) = (f) = R (g) and R c = -R( + (Q), then
/ (R S (R() + (g)
2. If R (f+g) (f)+ (g) and (0)((+)==R))
then R ( +
9) S (f) (g).
3. If APΩ is Rank A A-dimensional and completely positive for all p E [0, 1]. where A has its non-zero singular taken to the p-th power, then R(2) (x + Ax; 52) log., ^T All
Proof. We start from the inequality
R(ʃ o g; Qt L, + Lg) S R(f:g(()))))))) Ly) + R(g; S2 Lg).
We subtract (Ly R (f (
R g) divide by Ly + Ly and take the limit of increasing
depths Lg, with lim L.
1, L,+h, = E (0,1) to obtain
1 R2 (fig(()) - (
1) S (fo
(1)
1 -
If Kp is the limiting representation ratio p E (0, 1), we have (f: R (Kp; ②2) +
I-p ((2)(((,) - f: and p must minimize the RHS since if it instead minimized different ratio p' + p. one could find lower norm representation by mapping to K, in the first p' L layers and then back to the outputs. Now there are two possiblities, either (2)) (Kp; 22) and R (K, + f;()) are non- -egativee in which case the minimum attained at some p E (0, 1) and (f: 2 0, or one or both is negative in which case the above minimized at p E {0, 1) and (f: -c0. Since assumed p (0, 1), we in the first case.
(1) To prove the first property, we optimize the RHS of possible choices of p (and assuming that (fig(())) (g: 22) 2 0) we obtain
(P) 9: S (fg(())(()) + (g:
(2) This follows from the inequality R(f + g: 22, L) s R(f:g({)) L) + R(g; Ω L) after subtracting the R()) and R(!) terms, dividing by and taking L + Dc.
(3) = USVT, one chooses Wt = U,StUr with Un = V. Ur = U and Ue chosen so that U.S/ VT R. choosing large enough widths nıg This choice of representation of A is optimal, i.e. its parameter matches the representation cost LTr [ LRank 2 log |A] +
log A O(L-2).
We know that
l2 l1
lim n argi R()) 92) ++000
lim I.
15

---

R (a; +
R (a + f:0) 2 (f:0)
p
1-p p
1
R( (a;; (?)
+ R(2 (a + f:0) 2 nº (1:0)
1-p
B Bottleneck Structure
This first result shows the existence of a Bottleneck structure on the weight matrices:
Theorem 15 (Theorem from the main), Given parameters 9 of a depth L network, with ||0|| kL + e₁ and a point x such that RankJ fo()) k. then there are we x monii-orthonormal Ue, V8 such that
4 Elw. UV- l|bell S a 21og []o(
t=1
thus for any p (0, 1) there are least (1 D)L layers l with
|| - Ue UeV llbell2 2oo [o()))
PL
Proof. Since
f W.DD
W,, (e ... PimJas (2) Di(x)W,
If the preimage of A matches the image of B then [AB] = |A] BB We therefore have
log [=))41) log WyPPmsann-ts))
+ +log Pimm(aa-----00aaa> DT- P4 1(0)) - -log| Pim. 1 2
log Pimjlar-soole Di PlmJan())) log P W1
This implies that
We f - - 2 PimJ(Ge-to00) W WePiman 1(0)_
2 log Pim.ifar (o) P((
||0| kL log [z)
S C1 2 log J (z))
with the convention (z(x)= Iw
Our goal is to show that the LHS is a sum of positive value which sum up to finite positive value, which will imply that most of the summands must be very small.
First observe that
log FmJ(ac-Soaay" De(x)) 2 k D(l
which is positive since the eigenvalues of De(x) are 1.
To show that the other part of the summands || - 2 2log Same)( We PimJaa Pan is positive, we give lower bound it. First, it can be rewritten
k 2 PimJ(a--SoMo))" W. Pim)or. + We Pin.f(ac- WeP Pm)
(I) PlmmJ((a--f)lee Wt WePimJar
16

---

Now for general matrix A, we have
RankA
||A||
RankA
2 log 1
s:(A)² 1 - 2 2og (A
RankA
ss(A)3 ((ss(A)) 1)
RankA
Σ (s;(A) - 1)²
= ||A -V
for the SVD decomposition A USVT. We can thus lower bound
Well l- - 2 log (imJ(6.-(o((e) Wel WePmmaac-stol4 2 l| - U.V?
where U2S is the SVD decomposition of P (mmm(aa W₂ WePlem/ar-aaa (which we know has rank & since it must match the rank of (x))
Since | Ee [Wlle + ||bell S KT. + c1, we have
Σ WWe-UVVi 1|2 + libell Sa 2 2og [ff(()))
And for any p 1) there most pL. layers l with
2log (o(x))
[We U. + 1bel s
pL
The fact that almost all weight matrices We are approximately k-dim would imply that the pre- activations āx(X)= (xae-1(X) are k-dim too under the condition that the activations ag-1 (X) do not diverge. Assuming a bounded NTK sufficient to guarantee that these activations converge at almost every layer:
Theorem 16 (Theorem 7 from the main). Given balanced parameters @ of a depth L network, with |10112 < kL + eι and a point such that RankJ [a(x:) k then if N
&Tr Tr [0(L) x)] S cl, then
E/ [1a6-1 < emax(1,e 7 L and thus for all E (0,1) there are at least (1 P)L layers {)Jfo(m)
such that
1 cemax
|10e (x:)
p kb k 3/x
Proof. We have
Tr 1000 (z, x2)
= Σ
|a | (z) [| + an)
1=1
we therefore need to lower bound [[ + as (z) to show that the activations [|ac-1(x)11 must be bounded at almost every layer.
We will lower bound []J > az)(r)) by [J(āz + Pell for Pt the orthogonal projec- tion to the image ImJāg(x). Note J(ā - (z) and J fo (x) have the same rank.
By the arithmetic-geommtricc mean inequality, we have || | 2 RankA 14
2/ yielding
[ + az) 2 k (( + P1
17

---

Now the balancedness of the parameters (i.e. [ + b2 - |We+1, ve, implies that the parameter norms are increasing |
11
2
|[ell and thus
W
| 1|
W + 1W&ll
--
Thus
(IWW1 +... -laall))
(11w111 +... ([eell))
Wi 2 +... + IW&ll?
--
7
e
1011
L
and
[J
3/ s
1 [|J
||1ll ....4 1[&el
11012
S 1
C1
k
kl
kL
kL
and therefore
[J fo) 2 fo)
[J
Ja(x))
[J
(1+ 9
(I] 4 f
x)J[f(zz) ftt min(1, 3-
Thus
Σ | (x)) (1, L
+|Jfo(x)
which implies that there most pI. layers l with
1 1emax ( 2 P k|Jff(z)
Note that for the MSE loss in the limit À > 0, the Hessian at global minimum (i.e. fe interpolates the training set) equals Tr [MC( = Nv Tr Hessian is bounded by cL, we get that Tr ( (X, x)] cNL and thus there least (1 p) layers where
x)] If we then assume that the trace of the
1 N
1 cc
(x
<
p {(J
thus guaranteeing the infinite depth convergence of training set activations (x) on those layers. Putting the two above theorems together, we can prove that the pre-activations are k-dim at almost every layer:
Corollary 17 (Corollary 8 from the main). Given balanced parameters O of depth L net-
work with |lll12 < kL + ci and a set of points ,I,..., EN such that RankJ fo(x,) k and 1 Tr [O( (X, (x,)) s cL, then for all E (0,1) there are at least (1 p) layers such that (X,
N
Sk+1 (x)) S SVa. -22og [fo(2)]
N (1,
vp
N
k|Jfo(2;)1
PVL
18

---

Proof. Since (x) = Wear-1(X) + bel%y we know that
1 ((a(())) - swe)
1 Ja
8k+1
+ +|bblll-
op
By Theorems
15 and 16
there are for any p (0. 2) at least (1 L layers such that
| VeV. +lbbel2 1 Zlog)Jfo(z)))
PL
2
1emax(1,ett
a4 (X)
so that
1 (xx((())
C1 2log|Jfo(z)4+
c cmax (1,
+1)
+1 VI
1
8k41
<
p
pN k|Jfo(D.)1
C Local Minima Stability
In this section motivate the assumption that the Jacobian Jūr(2)) is uniformly bounded in oper- ator norm as L - oo. The idea that solutions with a blowing up Jacobian (āz(z) correspond to very narrow local minima.
The narrowness of a local minimum is related to the Neural Tangent Kernel (or Fisher matrix). We have that
Tr (x,) Σ |ay (z) + fo)
large Jacobian fxx leads to blow up of the derivative of the NTK: Proposition 18 (Proposition from the main). For any point x. we have
O(r, 2 2L 2
where 82, (xr, x)) is understood din dont matrix.
Furthermore, for any two points v. such that the pre-activations of all neurons of the network remain constant the segment [x, v), then either [|0(z, x)) [|O y)llop is lower bounded by 2-2/2
v11 fo(z)
w=z
I-ー 2
Proof. (1) For any point x, we have
Dayy (o (2x,2)) (u, [u.u]= Σ u (T) .. (WDDD(()---D-1))))
Do(x)2... (D)
Σ De-1 D((:)): ( Dr-
On the other hand, we have
10 ToT [folz)ul
= / -
< ( (z)
19

---

where we used the fact that (e(x) = De(x)) This applies to the case & = L and & = 1 too, using the definition Dr,(z) Iooee and Do(z) La.. This implies
D ... D2
0 (z² (u, 2 10 Jf((t)
De((x) ... (1)
|uu12
2 J
(/-) D3 (z)))
8f J
[Jfo(z)ul1
where we used the geometric/arithmeti mean inequality for the second inequality.
If u, u are right and left singular vectors of (() with singular value 8, then the above bound equals Ls=-
(2) Now let consider segment 7(1) (1-1)= ()x ty between two points æ; y with changes of activations these paths (i.e. (t))(t)) is constant for all E [0, 1)). Defining -1- and
ffo(r) [ we have
v
0,u7 (()()( (()) || v/102 (1"0()())) [4] 11 vll (o (F0((()), [M]
and since a.. ()((t))))0))))))))))))))) x()) = and o,,, (c)(t), = 0 for all E 1]. we have
of (n))()(())))))))))) (1))m) = | v/l 2 ( (1"0()()), [u, 2 2L || - yl || ( 3-
Since aT (()((t) 2 0 for all t E [0, 1] then either
L || yll (1 3/2
J. 00(,z 2
4
or
L x vll (1 1011 [J
0 e
4
Rank-underestimating fitting functions typically feature exploding derivatives. which was used to show in [Jac23] that BN-rank 1 fitting functions must have R(1) term that blows up iwith the number of datapoints N. With some additional work, we can show that the NTK will blow up at some x::
Theorem 19 (Theorem from the main). Let f= S2 - gdout be a function with Jacobian rank k > 1 (i.e. there a x E 32 with RankJ (x) k)), then with high probability over the sampling of a training set Ti,..., EN (sampled from distribution with support Qt), we have that for any parameters of a deep enough network that represent a BN-rank I function fo that fits the training set [o(xx) (x,) with norm ||0||2 I + 01 then there is a point x E St where the NTK satisfies
( (x,x) 2 Le 2
Proof. For all we define d1.; and d2,; to be the distance between yi and its closest and second closest point V1,-... VN. Following the argument in [BHH59] the shortest path that goes through all points must be at least ΣN", to. (which would be tight if is possible to always jump to the closest second closest point along the path). Since the expected distances dj,; and d2,; are N- + since the yi are sampled from a k -dimensional distribution, the expected length of the shortest path is of order N Actually most of the distance d1,t and d2, will be of order N 3- with only a few outliers with larger or smaller distances, thus for any subset of indices I [N, that contains a finite ratio of all indices, the sum Eier di.stdd, will be order N f too.
2
2
Following the argument in the proof Theorem 2 from [Jc23], we can reorder the indices so that the segment [11, [N] will mapped fo to a path that goes through y1.-.., yN- We can therefore define the points .i...., N that are preimages of ......, YN the segment.
20

---

12-+ Now since Σ 11 3,ll a rıll I diag? there must be least p(N - 1) intervals with || - xell $ (1--)(N-I)- and amongst those is they would all satisfy || - well 2 cN y-
On the interval [T;, 0:+1] there must a point with [[ 2 1
dingf
except for few outliers. Thus we can for example guarantee that there are least ( 1) intervals [++, that contain a point x with [ 2 cN1-#t
First observe that by Theorem of [Jc23]] there must be point x E such that [JSo(z))lop 2
N1- thus by Theorem 6 there are at least pl. layers where
c1 2 oog [
|| - [
pl.
Consider one of those pL layers with activatons 2, az (ā.). Let i ...... iN be the ordering of the indices so that ui si.. is increasing in m. Then the hidden representations must satisfy
|| [ee(tm 2mm-1 )|l Wee flm+1)ll
| -( di + d22...
2 e
2
2
and
2 2oo |J [o(x))+ ||
Wi(c... m1m S uz (2im 2m
|| -2im-1 zim-1l1
pL
For any two indices mi < m2 separated by PN indices (where p >> 0 remains finite), we have
We 2 2 )| +
We(
2im++
ue (Zimg Zimm
2
m=
1
c1 2 log [f((z))
3.mm 21m-1 11 + 12mm.
2em+1
pl.
2
m=m++1 +1
(12-2)
my
d1.am + d22
2
m=mi+1
|ol1. 11 -(--)
0q - 2log (So(x)) diam??
(m2
mi)e
pl.
|
-2--1
|o00e-11122 ((-11)
2 log I fe( PL
(m2 mi)
ce
N- +
diams?
where we used the fact that up to a few outliers di, ++
Thus for 2 4 teatIN N & e 2oggg]]] (diami))) we have uf (Ztmn Zbmgy 2 (mz
| ||2 -(1-0
mi)ge
N d. which implies that at least half of the activations 2z have norm | -(--)) N
larger than f
This implies that at least one fourth of the indices satisfy for at least one fourth of the PL layers é
|cce11
| 8
N
Now amongst these indices there are at least some such that there is a point x in the interval [ī;; ã 1] with []fo(z) op 2 cV1- #. Since v is O(N O(N--)-close to ã; one can guarantee that []oe-((a)]] 2
o -(1-0
c'e
N 2 for some constant d.
21

---

But the Jacobian J(āu + fo) also explodes at since
[]]o((>)]
|ockey 3
[][( lolp z |Jār(x)]lop
2 c
c
We now lower bound the NTK
Tr [ (x. m))
= Σ | [|J(āz - fo)
2 pL ce -11o/ct2:011122 +1 22- &
f---0=-llot0 -1o1000001 2
e" Le -a-a N
This suggests that such points are avoided not only because they have a large R(!) value, but also (if not mostly) because they lie the bottom very narrow valley.
D Technical Results
D.1 Regularity Counterexample
We guve here example of a simple function whose optimal representation geodesic does not converge, due to it being not uniformly Lipschitz:
Example 20, The function f: + RR with Ω = [0, 1 defined by
f(x, v2 = (2.
if S if >
(z. y. + a(x v))
satisfies (f; and (); 0. The optimal representations of are not uniformly Lipschitz L 0o.
Proof. While are not able to identify exactly the optimal representation geodesic for the function f. we will first show that (f( and then show that the uniform Lipschitzness of the optimal representations would contradict with Proposition I3
0 0
(1) Since the Jacobian takes two values inside R either the identity 13 or 1010)
1
we
-1
know by Theorem 11 that (f: 2 44s1_ 0. We therefore only need to construct a sequence of parameters of different depths that represent f with squared parameter norm of order 3T. + o(1). For simplicity, we only do this construction for even depths (the odd case can be constructed similarly). We define:
0
L
We
0
e
for
l 1
0
0
2c
2
1
0
0
WE =
0
1
Vae
Vae
0
0
W 4+1
0
0
0
1
/a (L-2)e
0
L
W₂
0
for l =
22 +2..... ...,
0
0
2c
2
22

---

We have for all x E R.
e e
04 a4-1(x)
e 3 I2
(L- (L-2)e03 x3
and
122022
az(z)=
(4-32)
0 x2)
and
a (1))(xx)=
e _ x2
(L--2)) (Iz + 0 x22)
and
fa(x)
D3 + o 82)
The norm of the parameters is
L L-2 (2e2 + te= + (3+ + - + --2 (2e-2 1 t
2 -2e
2
=3 (62x 1) + (e- 1) 2e (L-2)- + 2(L 2) + (c-2e 2e 1) + (e -
If we take 6 - for E ( 1), then the terms 2e
and E -((--2) decay exponentially (at -L (L-
a rate of et e in addition the terms 2 (c2 - 1) + (e 1) and (e- - 1) + (c 1) are of order T. This proves that (² (J; = 0.
(2) Let assume that the optimal representation of f is C-uniform Lipschitz for constant
C, then by Proposition 13 we have that
0
0
)
(f:() log 1s, + log
0
1
0
+
-
13
0 1 0 0,
1
-1
1
-1
which contradicts with the fact that (f: = 0.
D.2 Extension outside FPLFs
Since all functions represented by finite depth and width networks are FPLFs, the representation cost of any such function is infinite. But we can define the representation cost of function that is the limit of sequence of FPLF as the infimum over all sequences f. + f converging of lim, R(fe (2) (for some choice of convergence type that implies convergence of the Jacobians ff((r) + Jx(x)). Note that since the representation cost R(f: is lower semi-continuous, i.e. lim f-fo R(f; 2 R(fo: 2)), this does not change the definition of the representation cost on the space of FPLFs.
E Numerical Experiments
For the first numerical experiment, the data pairs (z, y/) were generated as follows. First we sample 8-dimensional 'latent vector' from which define ((21,.... 28) 20 and y h(21, 22) 220 for two random functions : I + 20 and h R - R200 given by two shallow networks with random parameters. Assuming that g injective (which is with high probability), the function f = h o g which maps x to y has BN-rank 2.
23


Reviews:
[{"review_id": "RdRsUaGWSP", "reviewer": "Reviewer_dQhS", "summary": "This paper extends the theoretical framework around the representation cost of DNNs as defined in previous work. The authors introduce two corrections to the existing infinite depth description, namely two regularity measures $R^{(1)}$ and $R^{(2)}$, which balance against the dominating rank bias $R^{(0)}$. The authors propose that these regularity measures prevent networks from underestimating the 'true' bottleneck rank (BN-rank) and argue that large learning rates can also induce a bias toward regularity. The paper provides a theoretical description of the limiting representation geodesics as depth approaches infinity, proving under certain conditions a bottleneck structure in the learned representations. Simple experiment is presented to test the network's ability to learn underlying symmetries.", "questions": "* Can these findings be used to improve the training of DNNs, for example, by adjusting the learning rate or regularization?\n* Considering that the argument in Proposition 7 is incomplete, how much further work would be needed to provide a complete argument? \n", "limitations": "Included in weakness.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The paper makes a great analysis of the representation cost under the previous theoretical framework, better explaining some observed results and conjecture.\n* The theoretical arguments are well supported, with clear intuition and explanation.\n* Different aspects are considered in the paper such as the effect of learning rate and the representation geodesics which is particularly interesting.\n", "weaknesses": "* The definition of the term \"regularity\" requires a more specific definition for the problem. It is claimed in line-32 that \"this notion of rank does not control the regularity of f\". Intuitively, the rank $R^{(0)}$ still measures some notion of complexity of the function as a higher-rank matrix can represent a more complex linear transformation. The corrections are other levels of complexity measures. I guess the \"regularity\" is more like how simple a function is with the same rank?\n* Theorem 9 proves bottleneck structure for convergent function sequence with an infinite depth limit. But in practice, the network is trained with finite data points and depth. Could the authors comment on how the conclusions would change for practical networks?\n* Analyze of the learning rate appears somewhat disjointed from the rest of the paper. Could there be a more integrated discussion about its role?\n* I found the numerical experiment a bit hard to follow and would appreciate it if more explanation on the idea could be added. Additionally, is it applicable for some experiments on justifying the theoretical findings, such as the effect of learning rate?\n* Minor typos:\n    * Line32: \"...control the the regularity...\"\n    * Line34: \"This formalizes the a balance...\"\n    * Line156: \"...$k^*$ of he task...\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thoughtful review. To answer your remarks/questions:\n\n- When we use the term regularity of a function, we mean properties\nthat imply that the outputs of the function change little if the inputs\nare changed a little bit, e.g. continuity, Lipschitzness, or ($k$-times)\ndifferentiability. The $R^{(1)}$ term bounds some notion of scale\nof the Jacobian (the determinant), though it does not bound the largest\neigenvalue, hence why we have to consider minima stability as a further\nbias towards regularity.\n\n- We plan to update Theorem 9 to apply to a finite number of datapoints\nand with finite depth bounds (so that we can drop the assumption of\na sequence of representation) showing exactly at which rate the representation\nbecomes planar (in the sense of how fast thets $k+1$-th singular value\nof the hidden representation goes to zero). This makes the result\nmuch closer to practical settings.\n\n- We plan to update the structure of the paper to better motivate\nthe study of the bias of large learning rates: our first hope was\nthat the $R^{(2)}$ term would be sufficient to guarantee convergence\nof the representations (since this is what seems to happen in the\nlinear case), but we have a counterexample that shows that this is\nnot the case in the nonlinear case, we therefore propose the large\nlearning rate bias as a remedy to this problem.\n\n- We will take more time to explain the numerical experiments. It\ndoes exhibit a Bottleneck structure, thus supporting our theoretical\nfindings, but it is difficult to check whether this structure is a\nresult of the large learning rate or the $L_{2}$-regularization.\n\n- Thanks for pointing out these typos, we will fix them.\n\n- There are several practical implications of this result for the\ntraining of neural networks, or also pruning/compression. We plan\nto study those in follow-up papers.\n\n- For Proposition 7, we are looking at completing the argument the argument in the case\n$k=1$, but the case $k>1$ might require significantly more work. We consider Proposition 7 to be only a minor remark of this paper, the question of why GD seems to avoid rank-underestimating solutions would probably fit into its own paper, studying the Bottleneck structre in the large $N$ regime."}, {"review_id": "puGKVWRJgx", "reviewer": "Reviewer_SexW", "summary": "This paper introduces two corrections to previous work that relates the representation cost of infinite-depth nonlinear networks to the bottleneck rank. These two corrections are obtained by Taylor expansion of the representation cost. In addition to the previously-known rank term $R^{(0)}(f)$ that is directly related to the bottleneck rank, the authors consider two corrections (1) $R^{(1)}(f)$, which bounds the pseudo-determinant of the Jacobian, and (2) $R^{(2)}(f)$, which plays a role in the intermediate representations in the hidden layer of the network. The authors specifically discuss several theoretical properties of $R^{(1)}(f)$. This term acts as a notion of regularity in the learning process of deep nonlinear networks, and it explains various interesting properties, such as how deep networks trained with conventional L2-regularized loss are uniquely determined (i.e., which $f$ among candidates with the same $R^{(0)}(f)$ is selected) and why the rank of the true function is not underestimated. The authors also briefly demonstrate the relationship between the curvature of the domain manifold and $R^{(1)}$ using the rank of the identity function, and discuss the connection between the learning rate and the Lipschitzness of learned deep networks with the results of the neural tangent kernel. Finally, the authors discuss the dynamics of hidden representations, which in the few initial layers the representations undergo changes to minimize $R^{(0)}$, then, as they move into the low-dimensional space, they change smoothly influenced by $R^{(1)}$ and $R^{(2)}$, i.e., exhibit the bottleneck structure of networks.", "questions": "I couldn't find any major drawbacks in this paper. One small question is:\n\nI would like to hear the authors’ thoughts on whether the optimal latent dimensionality of a well-trained auto-encoder $f$, which is likely to be similar to the identity $id$, might be associated with $R^{(0)}(f;\\Omega)$ and $R^{(1)}(f;\\Omega)$, for the case when $Rank_{J}(id;\\Omega) = Rank_{BN}(id;\\Omega)$, and if possible, when $Rank_{J}(id;\\Omega) < Rank_{BN}(id;\\Omega)$  \n", "limitations": "The authors do not explicitly address the limitations. However, in some of the theorems/propositions, they briefly mention the limitations of the proposed one, indicating what it can only explain or what constraints it has.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper is a direct follow-up to [1], and since I am not very familiar with [1], my evaluation may not be very accurate.\n\nTheoretical understanding of deep nonlinear networks is a highly significant field and holds considerable interest among the NeurIPS audience. For me, the theoretical results of this paper are highly novel and intriguing. The paper successfully modifies the results of [1], and provides a rigorous yet intuitive explanation of why neural networks trained with our L2-regularized loss do not underestimate the rank of the true function. Additionally, it demonstrates that under some conditions, the representation dynamics of deep nonlinear dynamics exhibit a bottleneck structure, which consists of a sequence of long bottleneck dimensional representations. This result is also noteworthy.\n\n***\n\n[1] Arthur Jacot. Implicit bias of large depth networks: a notion of rank for nonlinear functions. In The Eleventh International Conference on Learning Representations, 2023.\n", "weaknesses": "I couldn't find any major drawbacks in this paper.\n\nThe frequent mention of $R^{(2)}$ in Remark 10, before its properties were clearly stated, was somewhat confusing to me, although it is not a critical issue.\n\n\nThere are just a few very minor typos:\n\nIn line 32, “… not control the the …”\n\nIn line 34, “… formalizes the a …”\n\nIn line 118, “… because the the …”\n\nIn line 156, “… $k^{*}$ of he task ...\"\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive review. \n\nWe plan to change the stucture of the paper and talk about the $R^{(2)}$\nterm earlier. The reason why we discussed $R^{(2)}$ towards the end\nof the paper is that it ended up playing little role in the overall analysis. At first,\ninspired by the linear network case, we expected that the $R^{(1)}$\nand $R^{(2)}$ terms together would impliy the Bottleneck structure, with $R^{(2)}$ term guaranteeing convergence/accumulation of the representations.\nBut the counterexample in the appendix shows that this fails in the nonlinear case, instead it\nis the combination of the $R^{(1)}$ term and the large learning rate\nbias that leads to the Bottleneck structure.\n\nThanks for pointing out these typos we have fixed them.\n\nTo answer your question: if $\\mathrm{Rank}_J (id; \\Omega) = \\mathrm{Rank}\\_{BN}(id; \\Omega) = k$,\nwe show that the accumulating representations will be $k$-dimensional,\nwhich can be interpreted as the network recovering the planar `latent\nspace' of the data, and doing some form of manifold learning. Note that the\npaper [1] also talks about implications for the autoencoder setting,\nwhere autoencoders are naturally denoising.\n\nFor the case $\\mathrm{Rank}\\_J(id; \\Omega) \\< \\mathrm{Rank}\\_{BN}(id;\\Omega)$\nit seems that significant theoretical work is required, but we are\nin agreement with [1] which conjectures that in such case it is\nthe BN-rank $\\mathrm{Rank}\\_{BN}(id;\\Omega)$ that matters in DNNs.\nWe would thus expect the inner representations to have dimension $\\mathrm{Rank}\\_{BN}(id;\\Omega)$.\nIndeed if the network was to learn representations of dimension strictly\nsmaller then $\\mathrm{Rank}\\_{BN}(id;\\Omega)$ (and still fit the data)\nit would imply that the network has found a way to embed $\\Omega$\ninto an even smaller dimension, when $\\mathrm{Rank}\\_{BN}(id;\\Omega)$\nshould in theory the smallest possible dimension $\\Omega$ can be\nembedded into.\n\n[1] Arthur Jacot, Implicit bias of large depth networks: a notion\nof rank for nonlinear functions, ICLR 2023."}, {"review_id": "PicDODoTW2", "reviewer": "Reviewer_tanV", "summary": "This paper looks at the representation cost $R(f)$ of networks as the $L_2$ norm of all of the parameters. The paper claims that for deep neural networks, computing the minimum cost representation of a function is not tractable. Hence, the look at the representation cost normalized by the number of layers $L$ as $L \\to \\infty$. The paper then computes the Taylor expansion with respect to $1/L$ at $L = \\infty$. \n\nUsing this expansion, they recover three terms, $R^{(0)}(f),R^{(1)}(f),R^{(2)}(f)$. They note that $R^{(0)}(f)$ is used as a regularize before and corresponded to regularizing this notion of rank called the bottleneck rank. However, they argue that this is not enough and present results that determine the type of regularity imposed by using $R^{(1)}(f), R^{(2)}(f)$ as regularizers as well. ", "questions": "1. On line 91, what is the infinite width representation cost?\n\nTypos\n\n1. Line 156 instead of \"of he task\" -> \"of the task\"", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is very interesting, as understanding the representation of functions via neural networks is very important. The description of the two new terms $R^{(1)}(f), R^{(2)}(f)$ are explored in depth from a variety of different angles. Hence I think it makes a good contribution to the understanding of neural representation learning. ", "weaknesses": "My main issue with the paper is its presentation. The paper feels very disjointed. It would be helpful if the authors included more connecting discussion and discussed the high level picture in more detail. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thoughtful review.\n\nWe plan to modify the structure of the paper for the final version\nto better explain how the results are related. We will move the discussion\nof the second correction $R^{(2)}$ to right after the discussion\nof the first correction $R^{(1)}$. At first we expected that similarly\nto the linear case, the $R^{(2)}$ would guarantee convergence of\nthe hidden representations, but it turns out to not be sufficient\nin the nonlinear case (as evidenced by the counterexample we present\nin the appendix). We then propose the minima stability as a remedy\nto this problem, as it guarantees convergence of the representation,\nand leads (together with the properties of $R^{(1)}$) to the Bottleneck\nstructure.\n\nThis should make the relation between the different proofs clearer.\n\nTo answer your questions, the infinite width representation cost is\nthe limit of the representation cost as the width goes to infinity.\nIndeed the representation cost depends on the depth and width, but\nwe rely on previous work that have shown that the representation cost\nconverges in a $O(0)$ rate in the width, thus implying that the infinite\nwidth and depth limits commute, thus allowing us to study in this\npaper the infinite depth limit on its own (we just need to assume\na wide enough network).\n\nThanks for noticing this typo, we fixed it."}, {"review_id": "SBGDw4mrWc", "reviewer": "Reviewer_expT", "summary": "This work studies the leading order expansions in $L$ of the representation cost for a large $L$, where $L$ is the depth of the model. The work concludes that there is a low-dimension and regularity tradeoff as one varies the depth", "questions": "See weakness", "limitations": "See weakness", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "I think the main strength of the work is the novelty of the message it delivers: there is a low-dimension and regularity tradeoff as one varies the depth. The simplicity of the proofs is a plus.\n\nAnother important contribution is the technique to expand representation loss for a large depth, though I believe to require a little more technical soundness. See the weakness section\n\nAnother interesting insight of the paper is the concept of \"symmetry learning,\" and relating the \"spurious symmetries\" to the representation cost is also insightful\n\nAt this moment, I have some reservation about accepting this paper. If the authors answer my questions below in a satisfactory manner, I would be happy to accept it", "weaknesses": "There are quite a few aspects that I think this work can be improved.\n\n1. Let $R(L)$ denote the representation cost as a function of $L$, the depth. The first step of the theory is to expand $R$ in $1/L$, which feels unjustified, why is this function Taylor-expandable? Why can we treat $L$ as a continuous variable? These points are not crucial problems in my opinion, but the authors do not explain these with sufficient emphasis, given how important they are for the results\n\n2. In my opinion, the most problematic aspect is the fact that it studies the representation cost of an almost infinite depth neural network at a finite weight decay (this also relates to point 1). See https://arxiv.org/abs/2202.04777. This reference (for example, see proposition 3 / theorem 3) implies that for a sufficiently deep neural network and a fixed weight decay, the global minimum is the origin ($\\theta=0$), independent of the depth $L$. As one decreases the depth, the global minimum jumps from the origin to a nonzero value. This means that if we restrict to the global minimum of the cost function $C$, the representation cost is not a differentiable function in $L$, and thus it is not Taylor-expandable. I think the authors need to explain why the expansion remains reasonable/correct in light of this result\n\n3. Given how strong the assumptions are (point 1), I think the authors really should have carried out some experiments to directly check the prediction. In particular, I believe the authors should present a numerical example where the author directly compute the first and second order terms of $R$ in $1/L$ and show how they change for real neural networks to make the arguments of the paper more convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thoughtful review. Let us answer your remarks/questions:\n\n1. This a good remark and it is true that we did not address it in\ndetails. Actually for functions $f$ where the Jacobian and Bottleneck\nrank match $\\mathrm{Rank}\\_{J}(f;\\Omega)=\\mathrm{Rank}\\_{BN}(f;\\Omega)=k$\none can easily prove that the first correction is of order $1$, indeed\nwe have for any $x\\in\\Omega$ such that $\\mathrm{Rank}Jf(x)=k$ the\nbounds\n$$\nkL+2\\log |Jf(x)|\\_{+}\\leq R(f;\\Omega,L)\\leq (L-L\\_{g}-L\\_{h})k+\\left\\Vert \\theta\\_{g}\\right\\Vert ^{2}+\\left\\Vert \\theta\\_{h}\\right\\Vert^{2}\n$$\nwhere $f=h\\circ g$ with inner dimension $k$ and the functions $g$\nand $h$ are represented by depth $L_{g}$ and $L_{h}$ networks with\nparameters $\\theta_{g}$ and $\\theta_{h}$ (this is always possible\nsince $h$ and $g$ are assumed to be finite piecewise linear functions).\nThese upper and lower bound already appear in the proof of the sandwich\nbound $\\mathrm{Rank}\\\\_{J}(f;\\Omega)\\leq R^{(0)}(f;\\Omega)\\leq\\mathrm{Rank}\\_{BN}(f;\\Omega)$\nin [1].\n\n\tThis sandwich bound clearly shows that $R(f;\\Omega,L)=kL+c+o(1)$. It is however less clear under which condition the next order term $R^{(2)}$ is well defined, but since this second correction plays no role in our main proofs, this is not an issue. If the $o(1)$ term is not $O(L^{-1})$ then we simply say $R^{(2)}(f;\\Omega)=+\\infty$.\n\n\tWe will add a discussion of these questions in the Appendix and mention them in the main.\n\n2. This is a very good remark and we have indeed thought this question\nand other related issues. We have not identified the perfect answer,\nbut there are multiple ways in which our results can be used without\nfalling into this problem:\n\n\t(a) First note that our results make no assumption on the ridge $\\lambda$, it is therefore possible to choose a ridge $\\lambda=\\frac{\\lambda_{0}}{L}$ that decays in depth, in which case for small enough $\\lambda_{0}$ the global minimum remains non-trivial in the infinite depth.\n\n\t(b) When studying the representation cost, the zero solution is ruled out since we only consider parameters that fit the function (except if the function was the zero function of course). This rules out the possibility that our results follow trivially from the fact that everything is zero.\n\n\t(c) In general we believe that GD typically converges to a local minima of the loss, and so we tried to express our results so that they can be applied to local minima of the loss too. For example our results can be applied to any local minima of the reformulation of the loss $\\mathcal{L}\\_{\\lambda}(f)=C(f(X))+\\lambda R(f;\\Omega,L)$ and for each local minimum $\\hat{f}$ of this loss, there is a local minimum $\\hat{\\theta}$ of the loss $\\mathcal{L}\\_{\\lambda}(\\theta)=C(f_{\\theta}(X))+\\lambda\\left\\Vert \\theta\\right\\Vert ^{2}$ with $\\hat{f}=f_{\\hat{\\theta}}$ (though it might not be the case that for all local minimum $\\hat{\\theta}$ of the second loss $f_{\\hat{\\theta}}$ is a local minimum of the first loss).\n\n\tActually one goal of our decomposition is to approximate the first loss $\\mathcal{L}_{\\lambda}(f)$ by \n\t$$ \\mathcal{L}\\_{\\lambda}(f)\\approx C(f(X))+\\lambda LR^{(0)}(f;\\Omega)+\\lambda R^{(1)}(f;\\Omega). $$\n\tSince $R^{(0)}$ is a notion of rank that is partially constant, it is clear that there can be multiple minima of different rank (and amongst them a rank $0$ minimum too). Our ultimate goal is to describe all of these minima (and their narrowness / stability to better describe how attrative they are), not just the global minimum, since there is no guarantee that GD will converge to the global minimum.\n\n\t(d) Even better, the results that we present apply in some cases to any sequence of parameters $\\theta_{L}$ of increasing depth with $\\left\\Vert \\theta_{L}\\right\\Vert ^{2}\\leq kL+c$ such that $Jf_{\\theta_{L}}(x)$ converges to a rank $k$ matrix, making it possible to apply them to points that are not even local minima. To make this more practical, we plan to update Theorem 9 so that it can be applied for finite depths $L$, in which case there is no need for a sequence of parameters $\\theta_{L}$ of increasing depth, it can be applied to any parameters that have norm bounded by some $kL+c$, with tighter bounds for smaller constant $c$.\n\n3. In the setting we consider, there is no need to check that $R^{(1)}$\ndoes not explode as discussed in out answer to your first point, but\nwe nevertheless did an empirical computations of\n$R^{(0)}$ and $R^{(1)}$ (the figure is linked to the author's rebuttal), by plotting the norm of the learned parameters against the depth (on a task with true rank $r^*=2$). But since there are mutliple local minima at every depth (each with their own\n$R^{(0)}$ and $R^{(1)}$ values in some sense), we observe multiple `lines' of the form $kL+c$ for different integers $k$ that mostly match the number of singular values of $W_4$ that are larger than $0.5$ confirming that the slope $k$ matches the inner dimensions. Even though the rank $k$ of the minima GD converges to depends on the depth, we believe that these minima of different ranks are still present for any depths. Nevertheless we observe a very good linear match $\\Vert \\theta \\Vert^2 \\sim kL+c$ within the regions of same rank (we wouldn't expect a match accross minima with different ranks, since the learned function $f_\\theta$ would be completely different), even for small depths, suggesting that the approximation $R \\approx L R^{(0)} + R^{(1)}$ is adequate already for reasonable depths.\n\n[1] Arthur Jacot, Implicit bias of large depth networks: a notion\nof rank for nonlinear functions, ICLR 2023."}]

Author rebuttal:
Before we answer to each of the reviewers individually, we describe
here two main changes that we plan to do for the final version, the
first change affects the structure of the paper, while the second
one changes some of the mathematical tools used in the proofs, yielding
stronger Theorems:

1. We want to better explain the relation between the bias related to the decomposition of the representation cost and the bias related
to large learning rates/bounds on the NTK. Essentially our first hope was that the second correction $R^{(2)}$ would guarantee convergence of the hidden representations by bounding e.g. the Lipschitzness of the activations, since this is what happens in the linear network case. But it turns out that norm minimization is not sufficient to guarantee these things, as made explicit by the counter-example presented in the appendix.

	This is where the large learning rate bias comes into play, yielding a bias that guarantees convergence (more details on that in the next point). We will therefore move the results about $R^{(2)}$ to just after those related to $R^{(1)}$ and better explain what is missing in comparison to the linear case, thus motivating the assumption of minima stability / bounded NTK.

2. The assumption of global Lipschitzness to guarantee convergence
/ accumulation is too strong, as a result it may not follow in general
from the boundedness of the NTK. We have now identified a better condition,
which can be understood as Lipschitzness of almost all layers' representations,
which follows from the boundedness of the NTK and is sufficient to
guarantee the existence of accumulation points and thus of a Bottleneck
structure. Furthermore with this better proof technique, we can identify
the rate in $L$ at which the representations become $k$-planar,
by bounding the $k+1$-th singular values of the representations.

More precisely, we will change Theorems 5 and 9 to the following (and change the discussions around them):

**Theorem 5:** Given balanced parameters $\theta$ of a depth $L$ network,
with $\left\Vert \theta\right\Vert ^{2}\leq kL+c_{1}$ and a point
$x$ such that $\mathrm{Rank}Jf_{\theta}(x)=k$ then if $\frac{1}{N} \mathrm{Tr}\left[\Theta^{(L)}(x,x)\right]\leq cL$,
then $\sum_{\ell=1}^{L}\left\Vert \alpha_{\ell-1}(x)\right\Vert_{2}^{2}\leq C_1 L$
and thus for all $p\in(0,1)$ there are at least $(1-p)L$ layers
such that $\left\Vert \alpha_{\ell-1}(x)\right\Vert _{2}^{2}\leq\frac{C_1}{p}. $

We will give a explicit formula for the constant $C_1$ (and the following constants $C_2,C_3$), independent of depth $L$. This new version of Theorem 5 shows that even though a bounded NTK
may not imply uniform Lipschitzness, it does imply convergence of
the representations at almost every layer.

**Theorem 6:** Given parameters $\theta$ of a depth $L$ network, with
$\left\Vert \theta\right\Vert ^{2}\leq kL+c_{1}$ and a point $x$
such that $\mathrm{Rank}Jf_{\theta}(x)=k$, then there are $w_{\ell}\times k$
(semi-)orthonormal $V_{\ell}$ such that $\sum_{\ell=1}^{L}\left\Vert W_{\ell}-V_{\ell}V_{\ell+1}^{T}\right\Vert_{F}^{2}\leq C$
thus for any $p\in(0,1)$ there are at least $(1-p)L$ layers $\ell$
with $\left\Vert W_{\ell}-U_{\ell}V_{\ell-1}^{T}\right\Vert_{F}^{2}\leq \frac{C_2}{pL}.$

This proves a Bottleneck structure on the weight matrices: almost
all $W_{\ell}$ have $k$ singular values $L^{-\frac{1}{2}}$-close
to one and all the other are $O(L^{-\frac{1}{2}})$. Interestingly this does not require the NTK to be bounded. 

Now together with the convergence of the representations proven earlier it implies the
Bottleneck structure on the representations, in the sense that almost
all hidden representations $\tilde{\alpha}_{\ell}(X)$ are approximately
$k$-planar:

**Corollary:** Given balanced parameters $\theta$ of a depth $L$ network
with $\left\Vert \theta\right\Vert ^{2}\leq kL+c_{1}$ and a set of
points $x_{1},\dots,x_{N}$ such that $\mathrm{Rank}Jf_{\theta}(x_{i})=k$
and $\frac{1}{N}\mathrm{Tr}\left[\Theta^{(L)}(X,X)\right]\leq cL$,
then for all $p\in(0,1)$ there are at least $(1-p)L$ layers such
that 
$
s_{k+1}\left( \frac{1}{\sqrt{N}}\tilde{\alpha}_{\ell}(X) \right) \leq \frac{C_3}{p\sqrt{L}}.
$

This removes the need for the assumption of global Lipschitzness replacing
it instead with a bounded NTK which follows from minima stability
in e.g. the MSE settings. Another advantage is that It can be applied
at finite depths and at general points with sufficiently small parameters
norm (thus removing the need to define a sequence of parameters of
increasing depth too).


Meta-review: This paper provides novel theoretical analysis deepening our understanding of the dimensionality-regularity tradeoff in deep networks. The authors relate the representation cost to these key properties through intuitive lower bounds and assumptions.

Reviewers raised important concerns around justification of key assumptions and expansion of the representation cost R(L). The authors have satisfactorily addressed these issues in the rebuttal and revision. The revised version better explains assumptions on R's smoothness and validates the expansions through comparisons.

While experiments were suggested for further validation, the theoretical contributions stand strongly on their own. This paper makes key conceptual advances regarding dimensionality and regularity that experiments would likely only incrementally improve.

In summary, I recommend acceptance given the novel theoretical insights and the authors' addressing of major concerns through the rebuttal and revision. This work will interest the NeurIPS community and move forward foundations of representation learning.
Decision: Accept (poster)