Implicit Bias of Large Depth Networks: a Notion of Rank for Nonlinear Functions
Authors: Arthur Jacot
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Deep Neural Networks
implicit bias
representation cost
sparsity

Abstract: We show that the representation cost of fully connected neural networks with homogeneous nonlinearities - which describes the implicit bias in function space of networks with $L_2$-regularization or with losses such as the cross-entropy - converges as the depth of the network goes to infinity to a notion of rank over nonlinear functions. We then inquire under which conditions the global minima of the loss recover the `true' rank of the data: we show that for too large depths the global minimum will be approximately rank 1 (underestimating the rank); we then argue that there is a range of depths which grows with the number of datapoints where the true rank is recovered. Finally, we discuss the effect of the rank of a classifier on the topology of the resulting class boundaries and show that autoencoders with optimal nonlinear rank are naturally denoising.

IMPLICIT BIAS OF LARGE DEPTH NETWORKS: A NOTION OF RANK FOR NONLINEAR FUNCTIONS
Arthur Jacot
Courant Institute of Mathematical Sciences
New York University New York, NY 10012, USA arthur, jac.otjcctttuueeeoooo
ABSTRACT
We show that the representation cost of fully connected neural networks with ho- mogeneous nonlinearities which describes the implicit bias in function space of networks with Lg-regularization or with losses such as the cross-entropy con- verges the depth of the network goes infinity to notion of rank over nonlin- ear functions. We then inquire under which conditions the global minima of the loss recover the 'true' rank of the data: show that for too large depths the global minimum will be approximately rank (underestimating the rank); we then argue that there is range of depths which grows with the number of datapoints where the true rank is recovered. Finally, we discuss the effect of the rank of a classifier on the topology of the resulting class boundaries and show that autoencoders with optimal nonlinear rank are naturally denoising.
INTRODUCTION
There has been lot of recent interest in the so-called implicit bias of DNNs, which describes what functions are favored by a network when fitting the training data. Different network architectures (choice of nonlinearity, depth, width of the network, and more) and training procedures (initializa- tion, optimization algorithm, loss) can lead to widely different biases.
In contrast to the so-called kernel regime where the implicit bias is described by the Neural Tangent Kernel (Jacot et al., 2018), there are several active regimes (also called rich or feature-learning regimes), whose implicit bias often feature form sparsity that is absent from the kernel regime. Such active regimes have been observed for example in DNNs with small initialization (Chizat Bach 2018 Rotskoff & Vanden-EEjnneen 2018 Li al. 2020 Jacot al.; 2022a),, with L2- regularization (Savarese et 2019] Ongie et al. 2020 Jacot et al.) 2022b) or when trained on exponentially decaying losses (Gunasekar al. 201 Sa bj Soudry et al.) 2018 Du et al.) [2018] Ji & Telgarsky 2018 Chizat & Bach 2020 Ji & Telgarsky 2020). In the latter two cases, the implicit
bias described by the representation cost:
R()) = min
| W:fw=f
where / is a function that can be represented by the network and the minimization is over all param- eters W that result network function fw equal to f, the parameters W form vector and || [[] is the Lg-norm.
The representation cost can in some cases be explicitly computed for linear networks. For diagonal linear networks, the representation cost of a linear function f(x) = w x equals the L, norm R(f)
L ||wl| of the vector V for p the depth of the network. For fully-connected linear networks, the representation cost of a linear
(Gunasekar et al. 2018a Moroshko et al. 2020 where L is
function f(x) Ar equals the Ly-Schhtten norm (the Lp norm of the singular values) R(f)
L ||All DDai et al. 2021).
common thread between these examples is a bias towards some notion of sparsity: sparsity of the entries of the vector in diagonal networks and sparsity of the singular values in fully connected

---

networks. Furthermore, this bias becomes stronger with depth and in the infinite depth limit L + oo the rescaled representation cost R(f)/L converges to the Lo norm |ollo (the number of non-zero entries in w) in the first case and to the rank Rank(A) in the second.
For shallow (L = 2) nonlinear networks with a homogeneous activation, the representation cost also takes the form of L1 norm (Bach 2017 Chizat & Bach 2020 Ongie et al. 2020). leading to sparsity in the effective number of neurons in the hidden layer of the network.
However, the representation cost of deeper networks does not resemble any typical norm (Lp not), though it still leads to some form of sparsity (Jacot et al. 2022b). Despite the absence of explicit formula, will show that the rescaled representation cost R(T)/ converges to some notion of rank in nonlinear networks as L + oc, in analogy to infinite depth linear networks.
CONTRIBUTIONS
We first introduce two notions of rank: the Jacobian rank Rank = max, Rank [x)( and the
Bottleneck rank Rank (J) which is the smallest integer & such that f can be factorized f = h with inner dimension k. In general, Ranky( S Rank (f). but for functions of the form f & A o & (for linear map A and two bijections & and o), we have Rank,(f) = Rank (f)
RankA. These two notions of rank satisfy the properties (1) Rankf E E; (2) Rank (f g) S
min(Rankf Rankg); (3) Rank(f g) I R + Rankg; (4) Rank(r Ar + b) RankA.
We then show that in the infinite depth limit L - oc the rescaled representation cost of DNNs with general homogeneous nonlinearity is sandwiched between the Jacobian and Bottleneck ranks:
R()) L
Rank, J (f) S lim
RankBN (f).
L-+00
Furthermore lim R(F) satisfies properties (2-4) above. We also conjecture that the limiting representation cost equals its upper bound Rank
We then study how this bias towards low-rank functions translates to finite but large depths. We first show that for large depths the rescaled norm of the parameters [w]|// at any global minimum W upper bounded by 1+ Cv/z /L for a constant CN which depends on the training points. This implies that the resulting function has approximately rank 1 w.r.t. the Jacobian and Bottleneck ranks.
This however problematic if we are trying to fit 'true function' f whose 'true rank' k Rank f is larger than 1. Thankfully we show that if > 1 the constant C' explodes as N + co, so that the above bound (I) (l//]]// /L < 1+ Cw/L) is relevant only for very large depths when N is large. We show another upper bound || 11/r. < k + C/1. with constant C' independent of N, suggesting the existence of a range of intermediate depths where the network recovers the true rank k.
Finally, we discuss how rank recovery affects the topology of decision boundaries in classification and leads autoencoders to naturally be denoising, which we confirm with numerical experiments.
RELATED WORKS
The implicit bias of deep homogeneous networks has, to our knowledge, been much less studied than those of either linear networks or shallow nonlinear ones. (Ongie & Willett (022) study deep networks with only one nonlinear layer (all others being linear). Similarly (Le & Jegelkal (002)) show a low-rank alignment phenomenon in network whose last layers are linear.
Closer to our setup the analysis of the representation cost of deep homogeneous networks in (Jacot et al. 2022b), which gives two reformulations for the optimization in the definition of the representation cost, with some implications on the sparsity of the representations, though the infinite depth limit is not studied.
A very similar analysis of the sparsity effect of large depth on the global minima of Le-regularized networks is given in (Timor et al., 2022), however, they only show how the optimal weight matrices are almost rank (and only on average), while we show low-rank properties of the learned function, well as the existence of layer with almost rank hidden representations.
2

---

2 PRELIMINARIES
In this section, we define fully-connected DNNs and their representation cost.
FULLY CONNECTED DNNs
In this paper, we study fully connected DNNS with I. 1 layers numbered from (input layer) to L (output layer). Each layer & E {0....,7,, 1.} has ng neurons, with no = din the input dimension and n dout the output dimension. The pre-activations (x((x) R and activations a2(x:) R of the layers of the network are defined inductively as
oo(x)
āe(x) W1ae-1(z)+bb
(e(x) a (āz(z)),
for the ny X connection weight matrix We, the me bias vector by and the nonlinearity or : - applied entrywise to the vector (x). The parameters of the network are the collection of all connection weights matrices and bias vectors W (Wibb...... WL,
We call the network function fw Rddn + idd the function that maps an input æ to the pre- activations of the last layer (z).
In this paper, we will focus on homogeneous nonlinearities a, i.e. such that (Axx) = (x for any A 0 and E R. such as the traditional ReLU (xx) max (0, 2). In our theoretical analysis
will assume that the nonlinearity is of the form ox(x) x if 2
or otherwise for some a (-1, 1),
since for general homogeneous nonlinearity (which is not proportional to the identity function, the constant zero function or the absolute function), there are scalars a E (-1, 1), b E R and e E {+1,- 11 such that (xx) co. (bz); as result, the global minima and representation cost are the same up to scaling.
Remark 1. By a simple generalization of the work of (Arora et al. 2018), the set of functions that can be represented by networks (with any finite widths and depth) with such nonlinearities is the set of piecewise linear functions with finite number of linear regions. In contrast, the three types of homogeneous nonlinearities we rule out (the identity, the constant, or the absolute value) lead to different sets of functions: the linear functions, the constant functions, or the piecewise linear functions ff such that lim (tx() - f(-tz)ll is finite for all directions x E id (or possibly subset of this class of functions). While some of the results of this paper could probably be generalized to the third case up to a few details, we rule it out for the sake of simplicity.
Remark 2. All of our results will be for sufficiently wide networks, i.e. for all widths n such that ne 2 n for some minimal widths nž- Moreover these results are O(0) in the width, in the sense that above the threshold nž the constants do not depend on the widths ng. When there are a finite number of datapoints N, was shown by (Jacot et al., 2022b) that width of NN + 1) always sufficient, that is we can always take nž N(N + 1) (though it is observed empirically that much smaller width can be sufficient in some cases). When we are trying fit piecewise linear function over the whole input domain Ω the width required depends on the number of linear regions (He jet al. 2018).
REPRESENTATION COST
The representation cost R(fA,, L) is the squared norm of the optimal weights W which repre- sents the function fln:
Rif: Wifwa=fa
min
|
where the minimum is taken over all weights W of a depth L network (with some finite widths n)
such that fw(x) = fx) for all x Ω. If no such weights exist, we define R( S2, L) co.
The representation cost describes the natural bias on the represented function /w induced by adding La regularization on the weights W:
min C(Jw) + A 2 min C(J) + AR(f:
mjn
3

---

for any cost C' (defined on functions Ω + Rd and where the minimization the right is over all functions f that can be represented by a depth L network with nonlinearity a. Therefore, can give a simple description of the representation cost of a function f, we can better understand what type of functions f are favored by a DNN with nonlinearity a and depth L.
Remark 3. Note that the representation cost does not only play role in the presence of L2- regularization, it also describes the implicit bias of networks trained on an exponentially decaying loss, such the cross-entropy loss, described in (Soudry et al. 2018 Gunasekar et al. 2018a Chizat & Bach 2020).
INFINITELY DEEP NETWORKS
In this section, we first give 4 properties that a notion of rank on piecewise linear functions should satisfy and introduce two notions of rank that satisfy these properties. We then show that the infinite- depth limit L + oo of the rescaled representation cost Rff: Jas L) L is sandwiched between the two notions of rank we introduced, and that this limit satisfies of the 4 properties we introduced.
RANK PIECEWISE LINEAR FUNCTIONS
There is no single natural definition of rank for nonlinear functions, but we will provide two of them in this section and compare them. We focus on notions of rank for piecewise linear functions with a finite number of linear regions since these are the function that can be represented by DNNs with homogeneous nonlinearities (this is a Corollary of Theorem 2.1 from (Arora et al.) (018). for more details, see Appendix E.1). We call such functions finite piecewise linear functions (FPLF).
Let us first state a set of properties that any notion of rank on FPLF should satisfy, inspired by properties of rank for linear functions:
1. The rank of a function is an integer Rank(f) E N.
2. Rank( ogg g) S min min(RankJ, Rankg).
3. Rank(f + gg S Rankf + Rankg.
4. If f is affine (f) Ar b) then Rankf RankA.
Taking g id or f = id in (2) implies Rank(f) S min doue Properties (2) and (4) also imply that for any bijection Φ on Rd, Rank(()) = Rank(d-
Note that these properties do not uniquely define a notion of rank. Indeed we will now give two notions of rank which satisfy these properties but do not always match. However any such notion of rank must agree large family of functions: Property 2 implies that Rank is invariant under pre- and post-composition with bijections (see Appendix A), which implies that the rank of functions of the form s f á for affine function f(x) Ar + and two (piecewise linear) bijections v and 6 always equals RankA.
The first notion of rank we consider is based on the rank of the Jacobian of the function: Definition 1. The Jacobian rank of a FPLF f is Rank, (f: max, Rank.J taking the max over points where x is differentiable.
Note that since the jacobian is constant over the linear regions of the FPLF f, we only need to take the maximum over every linear region. As observed in (Feng et al. 2022). the Jacobian rank measures the intrinsic dimension of the output set fS22).
The second notion of rank is inspired by the fact that for linear functions f. the rank of f equals the minimal dimension & such that f can be written as the composition of two linear function f = g with inner dimension k. We define the bottleneck rank as:
Definition 2.
The bottleneck rank Rank (2) the smallest integer i E N such that there is a factorization as the composition of two FPLFs flz (g o h) with inner dimension k.
The following proposition relates these two notions of rank:
Proposition 1. Both Rank, y and Rank AN satisfy properties 1 4 above. Furthermore:
4

---

For any FPLF and any set Ω2 (f:k) - RankøN (f:
There exists FPLF F²a IR² and domain Q such that Ranks(f:S0) and Rank (f: (f: 2.
INFINITE-DEPTI REPRESENTATION COST
In the infinite-depth limit, the (rescaled) representation cost DNNs (f:
limg-+o R(I.R.o.LL) converges to value 'sandwiched" between the above two notions of rank: Theorem 1. For any bounded domain Q and any FPLF
Rf - R (f: - Rank (f;
Furthermore the limiting representation cost Ri (f: 92 o.) satisfies properties 2 to 4.
Proof. The lower bound follows from taking I + oc in Proposition (see Section 4. The upper bound constructive: a function f g can represented as network three consecutive parts: first part (of depth Lg) representing g. final part (of depth LA) representing h, and in the middle Lg La. identity layers on a k-dimensional space. The contribution to the norm of the parameters of the middle part is k(L-Lg L.) and it dominates L oo, since the contribution of the first and final parts are finite.
Note that (fa(f; (f; (2 o.) might satisfy property as well, we were simply not able to prove v o A á for bijections vi and ø,
it. Theorem implies that for functions of the form Rank (f; = RankA.
Roc (f aa) = Rf:
Remark 4, Motivated by some aspects of the proofs and general intuition (which is described in Section 4 we conjecture that Roo (f: o.) Rank B (f: This would imply that the limiting representation cost does not depend the choice of nonlinearity, long it is of the form (which we already proved is the case for functions the form o A σ).
This result suggests that large-depth neural networks are biased towards function which have a low Jacobian rank and (if our above mentioned conjecture true) low Bottleneck rank, much like linear networks are biased towards low-rank linear maps. It also suggests that the rescaled norm of the parameters IWI|/2 an approximate upper bound on the Jacobian rank (and our conjecture is true on the Bottleneck rank too) of the function fw. In the next section, we partly formalize these ideas.
4 RANK RECOVERY IN FINITE DEPTH NETWORKS
In this section, we study how the (approximate) rank minimizer functions fw (i.e. functions at global minimum W) for the MSE Lx (W) En (Sw (o;))=() + || with data sampled from distribution with support is affected by the depth L. In particular, when the outputs are generated from true function f (i.e. yi (xx)) with is Rank (2), we study in which condition the 'true rank' ls is recovered.
APPROXIMATE RANK REGIME
One can build function with BN-rank 1 that fits any training data (for example by first projecting the input to a line with no overlap and then mapping the points from the line the outputs with piecewise linear function). This implies the following bound:
Proposition 2. There a constant ON (which depends on the training data only) such that for any large enough L, at any global minimum W of the loss Lx the represented function f satisfies
ON L
R 9, L
Proof. We use the same construction in the proof of Theorem for any fitting rank function. n

---

This bound implies that the function fw represented by the network global minimum is approx-
imately rank both w.r.t. to the Jacobian and Bottleneck ranks, showing the bias towards low-rank functions even for finite (but possibly very large) depths.
Jacobian Rank: For any function f. the rescaled norm representation cost Ri S2, oa. L) bounds the Ly-Schatten norm of the Jacobian (with p = 7 at any point: Proposition 3. Let f be FPLF, then any differentiable point have
Rank fw (x)
|Jf(z))l = E
Sk (x(f(()))
1 =
where 84 (Jfw(x)) is the k-th singular value of the Jucobian J (sw
Together with Proposition this implies that the second singular value of the Jacobian of any minimizer function must be exponentially small 82 (Jfw - 1+ &
in
Bottleneck Rank: We can further prove the existence of bottleneck in the network in any mini- mizer network, i.e. layer l whose hidden representation is approximately rank 1:
Proposition For any global minimum W of the Le-regularized loss Lx with set of N datapoints X E R.dd (which do not have to be the training set X) with non-constant outputs, there is layer to such that the first singular values $1, of the hidden representation Zto E 1 (whose columns are the activations ogg (2:) for all the inputs in X) satisfies 22 OLL
0 and any
81
The fact that the global minima of the loss are approximately rank 1 not only in the Jacobian but also in the Bottleneck sense further supports our conjecture that the limiting representation cost equals the Bottleneck rank Ro Rank BN. Furthermore, it shows that the global minimum of the I-greegularized biased towards low-rank functions for large depths, since fits the data with (approximately) the smallest possible rank.
RANK RECOVERY FOR INTERMEDIATE DEPTHS
However, learning rank functions not always good thing. Assume that we are trying to fit 'true function' f Ω + ddout with a certain rank & Rank (f* If k the global minima large depth network will end up underestimating the true rank
In contrast, in the linear setting underestimating the true rank is almost never problem: for example in matrix completion one always wants to find a minimal rank solution (Candès & Recht, 2009 Arora et al. 2019). The difference is due to the fact that rank nonlinear functions can fit any finite training set, which is not the case in the linear case.
Thankfully, for large datasets it becomes more and difficult to underestimate the rank, since for large N fitting the data with a rank function requires large derivatives, which turn implies a large parameter norm:
Theorem 2. Given a Jacobian-raat rank true function f : Ω + Bduu on a bounded domain Q then for all e there is a constant c. such that for any BN-rank function f S2 + Rdoou that fits f(x.) = ff(xx) a dataset II,...,IN sampled i.idd from a distribution p with support Q we have 1. RRff:S.... L) > (. with prob. at least 1 c.
TSP(pL RN) for the Proof. We show that there is point Ω with large derivative (z) diam .1... Traveling Salesman Problem TSP(Y MN), i.e. the length the shortest path passing through every point .1...., Bm. and the diameter tiam(zi....,... from the fact that the image of f is line going through all y,8, and if and j the first and last points visited, the image of segment [z,, æ.] is a line from ys to yı passing through all y&s. The diameter is bounded by diam? while the TSP scales ! (Beardwood al. 1959) since the y:s are sampled from k-diimensionl distribution. The bound on the parameter norm then follows from Proposition 3
of the points . This follows

---

I22 Zell (2/11
Figure 1: DNN (depth L = 11 and width n1 - 300) trained on a MSE task with rank true function f* 1250 R550 with N 300 and À = 0.05/L. At the end of training, we obtain [IW l/r. 8. (left) First 10 singular values of the matrix of activations Ze for all L. The representations are appr. rank in the middle layers. (middle) The impact of the nonlinearity at each layer l, measured by the ratio [ e/|l where Ze is the matrix of preactivations with entries a (x:)). This impact vanishes in the middle layers, supporting intuition that the middle layers represent approximate identities. (right) First 10 singular values of the Jacobian J (z) at 10 random points.
This implies that the constant Cy in Proposition exxplodes as the number of datapoints N increases, Le. as N increases, larger and larger depths are required for the bound in Proposition to be meaningful. In that case, better upper bound the norm of the parameters can be obtained, which implies that the functions f at global minima are approximately rank k or less (at least in the Jacobian sense, according to Proposition B)
Proposition 5. Let the 'true function' f Ω + RRout be piecewise linear with RankBN(f* k then there is a constant which depends on f only such that any minimizer function fw satisfies
R(fwioo oa, 2)
5k+ L
Theorem 2 and Proposition 5 imply that if the number of datapoints N is sufficiently large (N
). there are parameters W that fit the function f" with a smaller parameter norm than any choice of parameters W that fit the data with rank function. In that case, the global minima will not be rank 1 and might instead recover the true rank k.
A++
Another interpretation is that since the constant C' does not depend on the number of training points N (in contrast to CN). there is range of depths (which grows as N - oo) where the upper bound of Proposition 5 is below that of Proposition 2
We expect rank recovery to happen roughly in this range of depths: too small depths can lead to an overestimation of the rank while too large depths can lead to underestimation.
Remark 5. Note that in our experiments, to a solution that underestimates the true rank, even for very deep networks. This is probably due gradient descent converging to of the many local minima in the loss surface of very deep Le-regularized DNNs. Some recent thcoretical results offer a possible explanation for why gradi- descent naturally avoids rank solutions: the proof of Proposition shows that rank I fitting functions have exploding gradient as N + oo, and such high gradient tunctions are known (at the moment only for shallow networks with ID inputs) correspond narrow minima (Mulayoff al., 2021
not able to observe gradient descent converging
Some of our results can be applied to local minima Wwith small norm: Proposition implies that the Jacobian rank of fw is approximately bounded by || Proposition 4 also applies to local minima, but only if [[w]]] [1/l// C/L for some constant C, though it could be generalized.
DISCUSSION
We now propose tentative explanation for the phenomenon observed in this section. In contrast to the rest of the paper, this discussion is informal.
Note that traditional regression models, such as Kernel Ridge Regression (KRR) typically overestimate the rank, described in Appendix D.I.
7

---

Ideally, want learn functions f which can be factorized composition ho g so that not only the inner dimension is small but the two functions g. h are not "too complex'. These two objectives often contradictory and one needs to find trade-off between the two. Instead of optimizing the bottleneck rank, one might want to optimize with regularization term of the form
min k y (C(g) C(h)).
f=hog
optimizing over all possible factorization f == h 9 of f with inner dimension k, where C(g) and and h resp. The parameter y 2 allows us to tune the
C(h) are measures of the complexity balance between the minimization of the inner dimension and the complexity of and h, recovering the Bottleneck rank when 7 = For small y the minimizer always rank 1 (since possible to fit finite dataset with a rank 1 function in the absence of restriction on the complexity on g and h), but with the right choice one can recover the true rank.
always
Some aspects of the proofs techniques we used in this paper suggest that large-depth DNNs are optimizing such cost (or an approximation thereof). Consider a deep network that fits with minimal parameter norm a function f; if we add more layers the network it is natural to assume that the new optimal representation of f will be almost the same as that of the shallower network with some added (approximate) identity layers. The interesting question is where those identity layers added? The cost of adding an identity layer at layer l equals the dimension de of the hidden representation of the inputs at It is therefore optimal add identity layers where the hidden representations have minimal dimension.
This suggests that for large depths the optimal representation of function f approximately takes the form of Lg layers representing g. then L L, - LA identity layers, and finally Ln. layers representing h, for some factorization f hog g with inner dimension k. We observe in Figure such three-part representation structure in an MSE task with a low-rank true function. The rescaled parameter norm would then take the form
1
W 2
T, L.g Ta L
where W g and WA are the parameters of the first and last part of the network. For large depths, we can make the approximation مي 1 to recover the same structure as Equation | with 1/z, C(u)= = ||W]| and C(h) = | This intuition offers a possible explanation for rank recovery in DNNs, though we are not yet able to prove it rigorously.
5 PRACTICAL IMPLICATIONS
In this section, we describe the impact of rank minimization on two practical tasks: multiclass classification and autoencoders.
MULTICLASS CLASSIHCATION
Consider function fw- di + " which solves a classification task with m classes, i.c. for all training points x, with class yi [l....,m) m) the y--th entry of the vector fw- is strictly larger than all other entries. The Bottleneck rank k = RankaN(fw" of the resulting partition of the input space 52 into classes, leading to topological properties typical of partition on k-dimensional space rather than those of a partition on a d;n- -ia-dmmiiiioal space.
of fw- has an impact on the topology
When & 1. the partition will be topologically equivalent a classification on line, which implies the absence of tripoints, i.e. points at the boundary of 3 (or more) classes. Indeed any boundary point x E will be mapped to a boundary point 2 = g(x) by the first function g Ω -> TK in the factorization of fw-; since has at most two neighboring classes, then so does
This property is illustrated in Figure 2 for a classification task on four classes on the plane, we observe that the partitions obtained by shallow networks (L = 2) leads to tripoints which are absent in deeper networks (L = 9). Notice also that the presence or absence of Lę Le-reuularizztion has little effect the final shape. which is in line with the observation that the cross-entropy loss leads to an implicit Legullalationionn (Soudry et al.) 2018 Gunasekar et al. 2018a Chizat Bach 2020).
reducing the necessity of an explicit T-grreuularization
8

---

(8) L = 2, = (b) 2, X 10
(c) L 9
9, 10-3
Figure 2: Classification on 4 classes (whose sampling distribution are identical inverted 'S' shapes translated along the r-axis) for two depths and with or without Læ-regularization. The class bound- aries shallow networks (A,B) feature tripoints, which are not observed in deeper networks (C,D).
1.00
2
0.5
5
0.4
0.25
0.03
2
5
3
0.5
-0.7
-08
-107
-3.50-0.25 a:o ads a5e eds 1,0
-4.5
0.0
1.
=
(b) L
L
Figure 3: Autoencoders trained on MNIST (A) and ID dataset on the plane (B, C) with a ridge
= 10-4, 4 Plot (A) shows noisy inputs in the first line with corresponding outputs below. In plots (B) and (C) the blue dots are the training data, and green dots are random inputs that are mapped to the orange dots pointed by the arrows. We see that for large depths (A, B) the learned autoencoder naturally denoising, projecting points to the data distribution, which is not the case for shallow networks (C).
AUTOENCODERS
Consider learning autoender data of the form =g)) where z is sampled (with full dimen- sional support) in a latent space IR* and : IR* + IRd an injective FPLE this setting, the true rank is the intrinsic dimension & of the data, since the minimal rank function that equals the identity on the data distribution has rank k.
Assume that the learned autoencoder f R$ + R fits the data f(x) for all g(2) and recovers the rank Rank k. At any datapoint xo = g(2) such that g differentiale at zo. the data support gRR*) is locally a k-dimensional affine subspace T zu + ImJg(2z0) In the linear region of f that contains f is affine projection to T since it equals the identity when restricted to and Jacobian is rank This proves that rank recovering autocncoders are naturally (locally) denoising.
CONCLUSION
We have shown that infinitely deep networks, Inzrregularization leads bias towards low-rank functions, for some notion of rank on FPLFs. We have then shown set of results that suggest that this low-rank bias extends to large but finite depths. With the right depths, this leads to 'rank recovery', where the learned function has approximately the same rank as the 'true function'. We proposed a tentative explanation for this rank recovery: for finite but large widths, the network is biased towards function f which can be factorized f h with both small inner dimension and small complexity of g and h. Finally, we have shown how rank recovery affects the topology of the class boundaries in classification task and leads natural denoising abilities in autoencoders.

---

REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference Learning Representations, 2018. URL UtLsttsss//pppeeeviii
net/ wttt//oormmiid-dee rgRRW
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019. ISSN 1049-5258.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629 6819,68822222 2017.
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-32) -299, 1959. doi: 10.1017V500050044100 100334990
Emmanuel Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational mathematics, 9(6):717-772 2009.
Lénaic Chizat and Francis Bach. On the Global Convergence of Gradient Descent for Advances in Neural Infor- mation Processing Systems 31, pp. 3040-3050. Curran Associates, Inc., 2018. URL
Over-parameterized Models using Optimal Transport.
pracient-descenn org.ap/ce.........aaaaaaaaaaaaaa transport.
Lénaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural net- works trained with the logistic loss. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory. volume 125 of Proceedings of Machine Learn ing Research, pp. 13388-138. PMLR, 09-12 Jul 2020. URL http::
mir.
press/ cteas/vv25/chh.
http1//5/cciit22aa.hhara. prees//
Zhen Dai, Mina Karzand, and Nathan Srebro. Representation costs linear neural networks: Anal- ysis and design. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems, 2021. forum? 3oodyyyyyBBBb
Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. Advances in Neural Information Processing Systems, 31, 2018.
Ruili Feng, Kecheng Zheng, Yukun Huang, Deli Zhao, Michael Jordan, and Zheng- Jun Zha. Rank diminishing in deep neural networks. arXiv preprint arXiv:2206.06072, 2022.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1832-1841. PMLR, 10-15 Jul 2018a. htt:: http://prroeedding mlr. btteess/v8D//uaaaseee
8a. html
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient de- scent linear convolutional networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Beanaa Bianchi,,chi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018b. URL htR.httss:/ htt.tt:::pppoccee..... ngs www.riiua...... cc/ 623.5444666622299034444488488888 Pcpppeee.....--.prrr..o.o pdf.
Juncai He, Lin Li, Jinchao Xu, and Chunyue Zheng. Relu deep neural networks and linear finite
elements. arXiv preprint a 807.00973, 2018.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernel: Conver- Advances in Neural Information
gence and Generalization in Neural Networks. Processing Systems 31, pp. 8580 8589-8589. Curran Associates, Inc.. 2018. URL http: connergeeoovveeeeeee
10

---

Arthur Jacot, François Ged, Berfin Şimşek, Clément Hongler, and Franck Gabriel. so-ddele dynamics in deep linear networks: Small initialization training. symmetry, and sparsity, 2022a.
Arthur Jacot, Eugene Golikov, Clément Hongler, and Franck Gabriel. Feature learning in l2- regularized dnns: Attraction/repulsion and sparsity, 2022b.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. CoRR, abs/1810.00 010.0203,, 2018. http::////ax/...cooo
aass/8100 02032]
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. In H. Larochelle. M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 17176-17186. Curran Asso- ciates, Inc., 2020. URL httpttttss//rroceeinnn.ggno httpa///sssscccpppp///////////// (e4e22aa5s15501111acacl11....cC
Thien Le and Stefanie Jegelka. Training invariances and the low-rank phenomenon: beyond linear networks. In International Conference on Learning Representations, 2022. URL https://
openreview foteet/oooommmdxxeeeg0ggg
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 Learning Representations, 2020.
Edward Moroshko, Blake E Woodworth, Suriya Gunasekar, Jason D Lee, Nati Srebro, and Daniel Soudry. Implicit bias in deep linear classification: Initialization scale training curacy. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 22182-22193, Curran As- sociates, Inc., 2020. URL UtLphttpss///rroceednngg hwwp://wwwdddnn.......e.ee....ee heurips cc cc/ppaper/2222//iieee 0222222800ll11//bbbbe99813333333
pdf
Rotem Mulayoff, Tomer Michaeli, and Daniel Soudry. The implicit bias of minima stability; view
from function space. 34:17799-17711, 2021. URL https: htttps:/pproceeee/et http:///ppoc.ee....//.o. neurips.
Greg Ongie and Rebecca Willett. The role of linear layers in nonlinear interpolating networks. arXiv preprint arXiv:2202.00856, 2022.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. In International Conference on Learning
Representations, 2020. StRlsttps:/ /tpptt/t/////ereeeeiieee//e// htt.:/iwwwweeeeeeeeeeeeeeeeeeeee wtt.///rrmmmmioo d= NNP*HKDH
Grant Rotskoff and Eric Vanden-Eijnden convergence and asymptotic error scaling of neural networks. In Advances in Neural In- formation Processing Systems 31, pp. 7146-7155. Curran Associates, Inc., 2018. URL.
Parameters as interacting particles: long time
www-nnuurl--eeeeee newuuaks pdf
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 (eds.), Proceedings of the Secooy- Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 2667-2690, PMLR, 25-28 Jun 2019. URL https: httpass///cccceeigs..oo mml.
stess//99/savareeee19 html
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19 (1):2822-2878, 2018.
Nadav Timor, Gal Vardi, and Ohad Shamir. Implicit regularization towards rank minimization in relu networks. arXiv preprint arXiv:2201. /2760, 2022.
11


Reviews:
[{"review_id": "q_96-Y-9FO", "reviewer": "Reviewer_44KN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces two notions of rank for nonlinear functions, the Jacobian rank, and the bottleneck rank. The authors then consider fully connected neural networks with homogeneous nonlinearities. They first show that for $L\\rightarrow\\infty$, the reconstruction cost of any piecewise linear function is sandwiched between the two notions of rank. Next, they show several results regarding the reconstruction cost of any minimizer of the $\\ell_2$-regularized empirical risk minimization problem when $L$ is large but finite. They have a discussion on some of the implications of these theoretical results.", "summary_of_the_review": "The paper looks at the problem of implicit bias of fully connected neural networks in the large depth regime and introduces notions of rank that can explain the nature of the implicit bias for deep enough networks. This problem might be interesting and worthwhile to look at, however the results are not well presented and unless the conjecture the authors present is correct, the results do not directly imply there is a bias towards smaller bottleneck ranks.", "strength_and_weaknesses": "## Strengths\n - The paper looks at the implicit bias that depth of fully connected networks induce. This problem is interesting and different implicit biases have attracted a lot of attention in the past few years.\n\n - The paper tries to characterize this implicit bias theoretically and shows a few examples of what these theoretical results might imply in practice.\n\n## Weakness\n - The paper is hard to follow. At times it is not clear how one results implies the other. The proofs in the main paper are very terse and even following some of the proofs in the appendix are not easy.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "mfGOOIpSaQw", "reviewer": "Reviewer_jUL5", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the representation cost of piecewise linear functions by deep homogeneous nonlinear networks.\n\nThe representation cost of f is defined as R(f) = \\min_{W : f_W = f} ||W||^2, where ||.|| is the L2 norm of the parameters and f_W is the neural network parametrized by W. This representation cost arises in the analysis of neural networks in a variety of settings, including training with cross-entropy loss, training with ridge regularization, and training with a small initialization.\n\n1. The paper proves that in the limit of infinite depth L \\to \\infty, the representation cost of f : R^{d_{in}} \\to R^{d_{out}} is sandwiched between two bounds: a lower bound based on the maximum rank of the Jacobian of the function at a point, and an upper bound called the \"bottleneck\" upper bound, based on the minimum inner dimension k such that one can write f = g \\circ h, where g : R^{k} \\to R^{d_{out}} and h : R^{d_{in}} \\to R^{k}. Furthermore, \\lim_{L \\to\\infty} R(f) / L satisfies several properties that one would like to have for a rank.\n\n2. The paper also studies why, for large but finite depth L, the representation cost R(f) / L of the function f restricted to the training dataset does not trivialize to be approximately equal to 1 (Theorem 2).\n\n3. Finally, practical implications are discussed, including qualitative differences between the classification boundaries learned by deep networks vs. shallow networks.", "summary_of_the_review": "This was a very enjoyable and informative paper to read. It is novel, well-written, and interesting.", "strength_and_weaknesses": "Strengths:\nThis is a refreshing paper, which provides a novel and elegant perspective on the representation cost of functions by nonlinear, deep neural networks. I found the practical implications of the result particularly interesting -- specifically that deeper neural networks should find classification boundaries on a finite number of data points that do not have tripoints.\n\nI wonder whether a finer quantitative statement can be made for multiclass classification of a finite number of data points N and finite depth L, in the style of Theorem 2 and Proposition 5 -- which bounds the number of tripoints in the minimum-representation-cost classification boundary.\n\nThere is also the intriguing open question about whether the upper bound is tight. And you can also ask about what happens if you add residual connections, which would seemingly lead to quite different behavior.\n\nWeaknesses:\n* I found the practical implications section relating to autoencoders a bit sparse, and would appreciate if more information could be added to clarify what is meant.\n* In the proof of Theorem 1 in the appendix, maybe add a note that you are shifting f and g so that you only have to represent the identity on the upper quadrant (because Omega is bounded.) This is only mentioned in the proof of the second part of Theorem 1, and was a point of confusion for me before I read that.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "OFQ_Ppwcaq", "reviewer": "Reviewer_BGRP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "the authors consider the implicit bias of deep neural networks with homogeneous\nactivations and linear layers, trained to minimize the square loss against a\ngiven piecewise linear target function with $\\ell^2$ regularization. previous\nworks have explored the functions achieving the minimum \"representation cost\"\n(the minimum weight norm of a network that interpolates the data) in simpler\ncases, such as linear networks and depth-two relu networks. the authors\nconsider a representation cost that is minimized over all networks of\nsufficiently large widths, and show that in the asymptotics where the network\ndepth goes to infinity, the normalized representation cost converges to a\nsuitable nonlinear notion of \"rank\" that the authors define. they study various\nperturbations off this limit (finite but large depth, on a loss taken over $n$\nempirical samples), and interpret the resulting conclusions in positive and\nnegative lights of this \"low-rank bias\". simple experiments are presented that\nconnect to classification and autoencoding problems.\n\n", "summary_of_the_review": "The work is very creative, and the connections between the bottleneck rank and\nthe training of neural networks for classification and autoencoding mentioned\nin the last section of the paper is very interesting. However, the theoretical\ntechniques do not seem to have much relevance to the regimes encountered in the\ntraining of practical networks, given that the theory seems to apply only to\nnetworks of untrainable depths and the representation cost defined takes an\ninfimum over architectures (widths), which makes it challenging to conclusively\nlink the work's contributions to these applications.\n\n", "strength_and_weaknesses": "## Strengths\n\nThe work considers an important and challenging problem in the study of\nimplicit bias of interpolating neural networks -- the case of nonlinear neural\nnetworks of depth larger than two -- which has not been successfully treated in\nany significant generality in any of the prior works in this area.\n\n## Weaknesses\n\nThe results are all phrased in terms of \"representation costs of piecewise\nlinear functions for homogeneous neural networks of sufficient width\", where\nthe width needs to depend on the target function $f$ -- in particular the\ndefinition at the bottom of page 3 does not pertain to any fixed class of\narchitectures. This makes it hard to compare to prior work, e.g. most relevant\nis by Ongie et al. (2020) -- why not just formulate everything in terms of\n\"infinite width\" networks as Ongie et al. do? This would seem to greatly\nfacilitate comparison. The authors draw an analogy to the\nrank minimization implicit bias in deep linear networks throughout the paper,\nbut it seems worth noting in this connection that the authors' results seem\nmuch weaker (for deep linear networks, the representation cost characterization\nholds for very general width-depth configurations, rather than only the case of\ndepth $\\gg$ width here).\n\nIn the proofs, one sees that the limiting representation cost (imagine it in\nterms of the bottleneck rank, since the lower bound in terms of the Jacobian\nrank seems rather coarse -- it doesn't capture any information about the\ncomplexity/variability/number/etc. of the different piecewise linear components\nof $f$, only their maximum slopes), is realized by a network that is infinitely\ndeep, and has fixed width (although this width in general depends on $f$). Such\nnetworks are impossible to learn with gradient descent -- e.g. one thinks of\nthe dying ReLU issue http://arxiv.org/abs/1903.06733. Could the authors comment\non why conclusions drawn from this limit can still be relevant for practical\nnetworks? It seems that the theory (including in section 4, where \"finite-depth\nnetworks\" are considered) does not have any implications for networks whose\nwidth is growing together with the depth. Similarly, the upper bound developed\nin the proofs on the representation cost seems to have no ability to capture\ninteresting practical phenomena in the study of representation by deep\nhomogeneous networks such as depth separations (where a certain function $f$\ncan be represented with far greater efficiency by a network of $L+1$ layers\nthan a network of $L$ layers).\n\nThere are some technical imprecisions that make it hard to assess the\ncorrectness of the theory (see below for some more minor ones).\n- Since piecewise linear functions are not generally differentiable, it would\n  sense to comment quickly on this issue when defining the Jacobian rank (since\n  a maximum is taken over $\\Omega$, involving points where it will not be\n  defined). \n- Proof of Theorem 1 (second inequality): the argument seems to be using\n  implicitly the claim \"if a piecewise linear $f$ can be written as $f = g\n  \\circ h$, then $g$ and $h$ are also piecewise linear\". This does not seem to\n  be true -- consider any diffeomorphism $\\phi$ on $h(\\Omega)$, then $f = (g\n  \\circ \\phi^{-1}) \\circ (\\phi \\circ h)$ gives another decomposition of $f$\n  into two functions that need not be piecewise linear. The claim seems more\n  subtle than it is treated in the proof (it does not seem immediate to me that\n  all such decompositions are related in this way).\n- It is not made clear in the main body that Theorem 1 is only shown to satisfy\n  the bijection property for piecewise linear bijections.\n\n\n## Minor / Questions\n\nLast line in first graf of \"Contributions\" on page 2: it would seem to be\npreferrable to actually state the five properties here--if they are somewhat\ntechnical, perhaps in \"informal\" form? \n\nI was trying to find the references for the representation costs of linear\nnetworks quoted in the introduction and in the appendices, but I could not find\nanywhere in the cited references (the authors give Gunasekar 2018, Moroshko\n2020, Soudry 2018) the specific results that were being invoked. It would be\nbetter if an actual specific pointer to where in these papers the results being\ninvoked can be found were added, or a more direct reference was included (for\nexample,\nhttps://proceedings.neurips.cc/paper/2021/hash/e22cb9d6bbb4c290a94e4fff4d68a831-Abstract.html\nseems to have the requisite results).\n\nSome technical imprecisions:\n- Section 1 defines the Jacobian rank with a minimum, but Definition 1 defines it\n  with a maximum.\n- Given the context, it seems the authors are focusing on the class of\n  piecewise linear functions under consideration those with finitely many\n  pieces (otherwise it does not make sense to me to write $\\max$ for the\n  definition of the Jacobian rank rather than $\\sup$).\n- Page 4 after five properties: I cannot see how property 2 implies invariance\n  under composition with bijections (property 2 does not involve a statement\n  about composition). It is not clear to me how to deduce this from these five\n  properties even thinking of linear maps and their rank function.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "HXWJIyA9qe6", "reviewer": "Reviewer_JJ6D", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces two new notions of rank for nonlinear functions (Jacobian rank and bottleneck rank). These definitions satisfy a set of properties of matrix ranks and thus generalize this classical notion. Moreover, under these rank notions, there exists regimes (large depth, large sample size) where the authors showed that neural networks that minimize a regularized ERM objective have low rank (and sometimes may recover the rank of the true teacher function) - suggesting a form of implicit bias. Experiments are done to support the claim and application to autoencoders are discussed.\n\n\n\n\n\n\n\n\n\n\n", "summary_of_the_review": "The paper has very interesting and strong theoretical results; and potentially opens doors to a lot more directions in understanding how deep learning works rigorously. I therefore recommend acceptance in anticipation that the writing is touched up a bit more in the final version, as well as more discussions on techniques/results. ", "strength_and_weaknesses": "Strengths\n\n1. The generalization of the notion of rank to regular but nonlinear function is indeed a very difficult task to attempt in general. I would characterize this paper as a sensible and thought-provoking attempt since the resulting notion is not trivial in certain regimes (large dataset, large depth, etc.). \n2. Traditional low rank literature usually requires linear separability or low rankness of the data matrix or whitened input. This paper does not make such assumptions. \n3. The theoretical analysis is done rigorously, with great intuition and explanation (although the Discussion subsection in section 4 is informal, it helps getting the general idea of the proof and feasible future directions).\n4. Experiments and applications well-support the theoretical findings. \n\nWeaknesses\n1. The rank characterization in the main results are done for some global minimizer of the regularized ERM, and not what is actually learnt by specific algorithms such as gradient descent or stochastic gradient descent. In practice, it is very hard for GD/SGD to find said global minimizer. \n2. The infinite depth regime is not something one expects to see in practice. \n3. Theorem 2 only addresses that the representation cost for rank-1 functions would be high if the true function has rank k. It is not clear how the representation cost penalty interplays with the underestimation of rank (for example, can we get some kind of high cost guarantee for rank-m functions where 1 < m < k?) The point made in the section would be a lot more convincing if this interplay is made quantitative. \n\nAdditional remarks and questions\n\n1. The definition of Jacobian rank in the paper can be problematic, especially with the use of ReLU/piecewise linear function since the Jacobian is not defined everywhere. Changing this to maximum rank over all affine pieces should address this problem (but would limit future applicability to neural networks that are not piecewise linear). The most general way to address this would probably involve defining the Jacobian rank for an appropriate subdifferential model (say Clarke), but this requires a lot more work. \n2. Theorem 1 has a reference to Proposition 3, which only appears later in the paper. \n3. In page 4, section 3, the author claims that “This result (of Theorem 1) suggests that large-depth neural networks are biased towards functions which have a low Jacobian or bottleneck rank…”. However, assuming that the representation cost of the optimal function is low (which is reasonable given that it is a term in the optimization objective), only the Jacobian rank is constrained to be small. The bottleneck rank can be arbitrarily large (unless the author’s conjecture that the representation cost in the infinite depth limit equals the bottleneck rank is true).  \n4. The use of TSP in the proof of Theorem 2 comes as quite a surprise and it would be more intuitive if there are some discussion of this proof technique (also, it’s not immediately clear what metric space the TSP is being formulated in). What conditions are required for the scaling of Beardwood et al 1959 to hold? (If all the y_i’s are in a straight line, I don’t suppose this scaling holds?) ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "85ai5dk7izs", "reviewer": "Reviewer_mVym", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the rank behavior of deep neural networks with three different types of rank definitions: the maximum of network Jacobi rank, bottlenet rank, and representation cost. The authors rigorously demonstrate the intrinsic connections among those three concepts, revealing a fascinating property of general deep learning models. The authors also show the representation cost of  BN rank-1 and rank-k functions. The results in this paper are appealing to a broad audience in machine learning.", "summary_of_the_review": "See comments above.", "strength_and_weaknesses": "Strengths:\n1. This paper is very well written; the notations are clear and very carefully designed; the organization of this paper is very clear.\n2. The topic of rank in deep networks are very important for a broad range of domains. Many previous works are not as successful in establishing a general enough yet elegant theory analysis framework for this topic. The three metrics, representation cost, Jacobi rank, and BN-Rank in this work are convincing, general, and elegant to use.\n3. Suffcicent numerical studies validates the theory justifications very well.\n4. Theory results on the connections between ranks and representation costs are very interesting and compelling.\n\n\nI have the following questions:\n\n1. In the representation cost, the norm || || is spectral norm or what?\n2. In the proof to Th1, do we assume that f tends to have a constant dimension for most of the intermediate layers? I think this makes sense for neural networks constructed manually, but may not be that reasonable for the underlying target function, the property of which is unknown.\n3. In definition 1, I think perhaps a better intuition for this definition of rank would be, considering Sard's Theorem and the Rank theorem of manifolds, only those regions of the highest rank are of true influences in the output manifold, as in [1].\n4. Some previou work[1] also discusses rank behavior of network ranks from the opinion of random matrix theory. The problem of using Jacobi rank directly is that, the rank of matrix is instable under small noises and errors, thus it is impossible to measure them in practice. So perhaps using the counting measure of significant singular values could be better.\n\n[1] Rank Diminishing in Deep Neural Networks, NeurIPS2022.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "3CmwlUpK70", "reviewer": "Reviewer_YMQ3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a notion of rank for non-linear functions, which is defined as the minimum possible $L^2$ norms of the weights of a neural network which matches the function, averaged over the layers, and asymptotically where the number of layers tends to infinity. \nIt is conjectured that this notion of rank is equivalent to that of \"bottleneck rank\", which is the minimum embedding dimension of an encoder decoder network that represents the function. The idea is that as the number of layers tends to infinity (and is much larger than the minimum required depth to represent the function), most layers are identity functions, which have Frobenius norm k where k is the embedding dimension at those layers. Hence minimizing the notion of rank defined in this paper becomes similar to minimizing the bottleneck rank. \n\nIt is shown that the rank defined here enjoys several sanity check properties with respect to compositions of functions etc. The first main theorem (Theorem 1) states that the rank defined here is sandwiched between the maximum rank of the jacobian of the function and the bottleneck rank. Later in Section 4, the paper studies the slightly more concrete situation of finite architectures. Proposition 2 is a non asymptotic version of Theorem 1, but it then leads onto proposition 4, which shows that if the ground truth rank is 1, then the global minimum of the regularized objective (corresponding to training a regularized neural network) has a very small ratio between the first two eigenvalues of its weights at at least one layer. \n\nIn the next section, a concern is raised: BN rank 1 functions are universal approximators of piecewise linear functions with a one dimensional output, thus the bias for low rank or rank one models could prevent one from learning the true rank. However, it is shown that for iid data, the cost of fitting the training set with a rank one function is prohibitively large for a large number of samples. It is therefore suggested that the depth should be chosen at an appropriate regime depending on the amount of data. \n\nIn the experiments, it is shown that deeper networks do learn \"low-rank\" functions at least in some cases (cf. figure 2). It is also shown that training deep neural networks on data of low BN rank results in a solution which contains many intermediate representations of rank approximately equal to the ground truth rank", "summary_of_the_review": "To the best of my knowledge (I may not know all the relevant literature, which makes vouching for originality harder), this appears to be an excellent paper making non trivial advances in the fundamental understanding of the behavior of deep neural networks. I couldn't find any mistake in the proofs and read most of them (I had some trouble with proposition 4 though). The topic is also fascinating and the tone just right (explaining some intuition as well as proving some more rigorous theorems). I like that one can see the thought process of the writers as they performed the research. Some of the proofs should be polished and made longer with more thorough explanations. \n\n\nI would give a score of 9 if the option was available. ", "strength_and_weaknesses": "Strengths: \n\nThis is an extremely interesting topic at the forefront of AI theoretical research \n\nThe results themselves are very interesting and appear to break new ground (I am not familiar enough with the recent literature to  fully vouch for this though). \n\nThe paper is quite well written in general\n\n\nWeaknesses: \n\nNot much, but if one is being picky: \n\nSome of the proofs should have more justifications\n\nThere are a few typos\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%