What is the Inductive Bias of Flatness Regularization? A Study of Deep Matrix Factorization Models
Authors: Khashayar Gatmiry
Zhiyuan Li
Tengyu Ma
Sashank J. Reddi
Stefanie Jegelka
Ching-Yao Chuang
Venue: NeurIPS 2023 poster (2023)
Keywords: Sharpness minimization
Deep learning
Matrix factorization
Deep linear networks
Implicit bias
SGD
Trace of Hessian regularizer

Abstract: Recent works on over-parameterized neural networks have shown that  the stochasticity in optimizers has the implicit regularization effect of minimizing the sharpness of the loss function (in particular, the trace of its Hessian) over the family zero-loss solutions. More explicit forms of flatness regularization also empirically improve the generalization performance. However, it remains unclear why and when flatness regularization leads to better generalization. 
This work takes the first step towards understanding the inductive bias of the minimum trace of the Hessian solutions in an important setting: learning deep linear networks from linear measurements, also known as \emph{deep matrix factorization}. We show that with the standard Restricted Isometry Property (RIP) on the measurements, minimizing the trace of Hessian is approximately equivalent to minimizing the Schatten 1-norm of the corresponding end-to-end matrix parameters (i.e., the product of all layer matrices), which in turn leads to better generalization.

The Inductive Bias of Flatness Regularization for Deep Matrix Factorization
Khashayar Gatmiry MIT gatmirydmit. edu
Zhiyuan Stanford University zhi iastanni@safffoo ord. edu
Ching-Yao Yao Chuang MIT cychuang@mit. edu
Sashank Reddi
Tengyu Ma Stanford University Sanegymm@@ttaffoddo
Stefanie Jegelka TU Munich & MIT stef stef je@ssail .mi edu
Google sashank@google.com com
Abstract
Recent works weer-parameterized neural networks have shown that the stochas- ticity in optimizers has the implicit regularization effect of minimizing the sharpness of the loss function (in particular, the trace of its Hessian) over the family zero-loss solutions. More explicit forms flatness regularization also empirically improve the generalization performance. However, it remains unclear why and when flatness regularization leads to better generalization. This work takes the first step toward understanding the inductive bias of the minimum trace of the Hessian solutions in an important setting: learning deep linear networks from linear measurements, also known as deep matrix factorizution. We show that for all depth greater than one, with the standard Restricted Isometry Property (RIP) on the measurements, mini- mizing the trace Hessian is approximately equivalent to minimizing the Schatten I-norm of the corresponding end-to-end matrix parameters (i.c., the product of all layer matrices), which in turn leads to better generalization. We empirically verify our theoretical findings on synthetic datasets.
Introduction
Modern deep neural networks typically over-parametrizer and equipped with huge model capacity, but surprisingly, they generalize well when trained using stochastic gradient descent (SGD) or its variants [51]. recent line of research suggested the implicit bias of SGD possible explanation to this mysterious ability. In particular, Damian et al. [10], Li et al. [29], Arora et al. [4], Lyu et al. [33], Wen al. [48], Liu al. [31] have shown that SGD can implicitly minimize the sharpness of the training loss, in particular, the trace of the Hessian of the training loss, to obtain the final model. However, despite the strong empirical evidence the correlation between various notions of sharpness and generalization [25, 23, 38, 24] and the effectiveness of using sharpness regularization on improving generalization [16, 49, 53, 39], the connection between penalization of the sharpness of training loss and better generalization still remains majorly unclear [13, 2] and has only been proved the context of two-layer linear models [29, 37. 12]. To further understand this connection beyond the two layer case, we study the inductive bias of penalizing the trace of the Hessian of training loss and its effect on the generalization in an important theoretical deep learning setting: deep linear networks (or equivalently, deep matrix factorization [3]). We start by briefly describing the problem setup.
Deep Matrix Factorization. Consider an L-layer deep network where L E N+ L> is the depth of the model. Let W2 E ddd and d, denote the layer weight matrix and width of the 7th (i E [4)
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

layer respectively. We use W to denote the concatenation of all the parameters (Wi...., WI) and define the end-to-end matrix of W as
((W) & W
(I)
In this paper, we focus on models that are linear in the space of the end-to-end matrix E(W). Suppose M E Rd is the target end-to-end matrix, and we observe n. linear measurements (matrices) A; E Idd xda and the corresponding labels b, = (Ai, M)). The training loss of W is the mean-squared error (MSE) between the prediction (A,, WL L- WW) and the observation b,:
1 Σ 1=1
((W)
WLW-1- ... Wi) -b,)².
(2)
Throughout this paper, we assume that d: 2 min(do, dr.) for each i E [L] and, thus, the image of the function E() is the entire Rd x do, In particular, this ensures that the deep models are sufficiently expressive in the sense that min L(W) O. For this setting, we aim understand the structure of W the trace of the Hessian minimization, as described below. The trace of Hessian is the sum of the cigenvalues of Hessian, which is an indicator of sharpness and it is known that variants of SGD, such as label noise SGD or 1-SAM, are biased toward models with smaller trace of Hessian [29, 48).
Min Trace of Hessian Interpolating Solution. Our primary object of study the interpolating solution with the minimum trace of Hessian, defined as:
W E arg min tr[r><(()) W:
As we shall see shortly, the solution to the above optimization problem is not unique. We are interested in understanding the underlying structure of any minimizer W This will, in turn, inform us about the generalization nature of these solutions.
1.1 Main Results
Before delving into the technical details, we state our main results in this section. This also serves the purpose of highlighting the primary technical contributions of the paper. First, since the generalization of W only depends on its end-to-end matrix E(W), it is informative E(W*) for any min trace of the Hessian interpolating solution W defined in (3). Indeed, penalizing the trace Hessian the W space induces an equivalent penalization in the space of the end-to-end parameters. More concretely, given an end-to-end parameter M, let the induced regularizer F(M) denote the minimum trace of Hessian of the training loss at W among all W's that instantiate the end-to-end matrix M i.e., E(W)= = M.
derive the properties of
Definition 1 (Induced Regularizer). Suppose M E Igd is end-to-end parameter that fits the training data perfectly (that is, (Ai, .M) = b,, Vi E [m]).. We define the induced regularizer as
F(M) & min tr L(())
W:E(W)=M
Since the image of FE()) is the entire Rd xdo by our assumption that de 2 min(do, dz.). function F well-defined for all M E IR Xoo, It is easy to see that minimizing the trace of the Hessian in the original parameter space (see (3)) is equivalent to penalizing F(M) in the end-to-end parameter. Indeed, the minimizers of the implicit regularizer in the end-to-end space are related to the minimizers of the implicit regularizer in the W space, i.e.,
arg min F(M)- E(W")) W' E arg min 1r[b>[())] M:
Wi
where for any M E Rd we define C'(M) & E ((A, 62)² 2 and thus L(W) L' (E)). This directly follows from the definition of F in (4). Our main result characterizes the induced regularizer F(M) when the data satisfies the RIP property.
n
Theorem (Induced regularizer under RIP). Suppose the linear measurements {A, satisfy the (L, 8) RIP condition.

---

Settings
Induced Regularizer F(M)/L
Theorem
(1, RIPP
(1+ (
Theorem 1
(*A.AT)) 1/2 M
A7 A,) "11
L 2
Theorem 5 ([12))
(A'M) AT
L-1
2/L
71 = 1
Theorem 7
S2/2
Table Summary of properties of the induced regularizer the end-to-en matrix space. Here II-Ils, denotes the Schatten p-norm for p E [1, oo] and Schatten p-quasinorm for p E (0, 1) (see Definition 2). ||-Il, denotes the Schatten I-norm, also known as the nuclear norm.
1. For any M E BRdxx xdo such that (A,, b,, vi [n]. it holds that
(1 (1-8)L(dodz) 1/4 11M S F(M) < (1+ ()dd)) (1
(5)
2. Let W E arg min w (ttp)/or/VV/// ((W)) be interpolating solution with minimal trace of Hessian. Then E(W*) roughly minimizes the nuclear norm among all interpolating solutions of C'. That is,
1+ 8 PlW -
min || 1 1 C(M)=0
However, for more general cases, it is challenging to compute the closed-form expression of F. In this work, we derive closed-form expressions for F in the following two cases: (1) depth L is equal to and (2) there is only one measurement, i.e., n (see Table 1). Leveraging the above characterization of induced regularzier, we obtain the following result on the generalization bounds:
Theorem (Recovery of the ground truth under RIP). Suppose the linear measurements { {A,))
satisfy the (2, ((1))) RIP (Definition 3). Then for any W E arg min tr[v=((W)), we have
W:C(W)=0
86( |M
||E(W*) M E
8(n))²
where 8(n) depends on the number of measurements n and the distribution of the measurements.
If we further suppose {A, J are independently sampled from some distribution over [Rd satisfying that EA (A, M) || | e.g., the standard multivariate Gaussian distribution, denoted
by Gauxdo- we know 8(n) = Ol do from Candes and Plan [7] (see Section 5.1 for more examples).
Theorem 3. For n 2 M(r(dg + d1)), with probability at least 1 - exp(Si(do + d1)) over the randomly sampled {A, 1/, from multivariate Gaussian distribution G. for any minimum trace of Hessian interpolating solution W E arg min ur[22[(W)), the population loss I(W*) & W=
(sA,((AAFW))))) (A, M satisfies that
[[E(W)) [(E()) M S 0 do dl | 1|2 n).
Z(W")
n
Next, we state a lower bound for the conventional estimator for overparameterized models that minimizes the norm. The lower bound states that, achieve small error, the number of samples should be as large as the product of the dimensions of the end-to-end matrix dod,, as opposed to do dz in case of the min trace of Hessian minimizer. It is proved in Appendix F.
Theorem 4 (Lower bound for & regression). Suppose { are randomly sampled from multivari- ate Gaussian distribution G. let W arg min == E [) to be the minimum Frobenius norm interpolating solution, then the expected population loss is
E ((W) (1- min[n,dode)
|M"
dodi.

---

The lower bound in Theorem 4 shows in order to obtain an (1)-rellatvvly accurate estimates of the ground truth in expectation, namely to guarantee E L(W) I [ 11 the minimum Frobenius norm interpolating solution needs at least l(dddr,) samples. In contrast, the minimizer of trace of Hessian in the same problem only requires (((do + [||||
samples, which is at least Ō minn(do.ee) times smaller. We further illustrate experimentally the superior generalization abilitt of sharpness minimization algorithms like label noise SGD [6, 10, 29] compared to vanilla mini-bactch SGD Figure 1. Due to the space limits, we defer the full setting for experiments into Appendix A.
2 Related Work
Connection Between Sharpness and Generalization. Research on the connection between gener- alization and sharpness dates back to Hochreiter and Schmidhuber [21]. Keskar et al. [25] famously observe that when increasing the batch size of SGD, the test error and the sharpness of the learned solution both increase. Jastrzebski et al. [23] extend this observation and found that there is a pos- itive correlation between sharpness and the ratio between learning rate and batch size. Jiang et al. [24] perform a large-scale empirical study on various notions of generalization measures and show that charpness-bused measures correlate with generalization best. Liu et al. [31] find that among language models with the same validation pretraining loss, those that have smaller sharpness can have better downstream performance. On the other hand, Dinh al. [13] argue that for networks with scaling invariance, there always exist models with good generalization but with arbitrarily large sharpness. We note this does not contradict our main result here, which only asserts the interpo- lation solution with a minimal trace of Hessian generalizes well, but not vice versa. Empirically, sharpness minimization is also a popular and effective regularization method for overparametrizee models [39, 17, 53, 49, 26, 32, 54, 52, 1].
Implicit Bias of Sharpness Minimization. Recent theoretical works [6. 10, 29, 31] show that SGD with label noise is implicitly biased toward local minimizers with a smaller trace of Hessian under the assumption that the minimizers locally connect as manifold. Such a manifold setting is empirically verified by Draxler et al. [14], Garipov et al. [18] in the sense that the set of minimizers of the training loss path-connected. It the same situation for the deep matrix factorization problem studied in this paper, although we do not study the optimization trajectory. Instead, we directly study properties of the minimum trace of Hessian interpolation solution.
Sharpness-reduction implicit bias can also happen for deterministic GD. Arora et al. [4] show that normalized GD implicitly penalizes the largest eigenvalue of the Hessian. Ma et al. [35] argues that such sharpness reduction phenomena can also be caused by a multi-scale loss landscape. Lyu al. [33] show that GD with weight decay on scale-invariant loss function implicitly decreases the spherical sharpness, i.e., the largest eigenvalue of the Hessian evaluated at the normalized parameter. Another line of work focuses on the sharpness minimization effect of large learning rate in GD, assuming that it converges at the end of training. This has been studied mainly through linear stability analysis [50, 8, 34, 9]. Recent theoretical analysis [1 30) showed that the sharpness minimization effect of a large learning rate in GD does not necessarily rely on convergence and linear stability, through a four-phase characterization of the dynamics at the Edge of Stability regime [8].
3 Preliminaries
|| || and Notation. We use [n] to denote {1, (1.2....,7) n) for every n e N. We use [|
tr(M) to denote the Frobenius norm, nuclear norm, spectral norm and trace of matrix M respectively. For any function if defined over set S such that minges f(x exists, we use arg ming f to denote the set (y S 1 f(y) minzes fx)) Given matrix M, use has denote the linear map A (A, M). We use H, to denote the set H, (har [[M] S r). Mi. and My are used to denote the ith row and jth column of the matrix M.
The following definitions will be important to the technical discussion in the paper.

---

Rademacher Complexity. Given data points {A:)-= the empirical Rademacher complexity of function class H. defined as
1
R (H) 1
sup (,)) hEHt i=1
Given distribution P, the population Rademacher complexity is defined follows: R, (H) E A, R2 (H). This is mainly used to upper bound the generalization gap of SGD.
Definition 2 (Schatten p-(quasi)norm). Given any d, d' N+ , É (0, 00) matrix M Rdxd' with singular values (M)..... minn(d,d") (MM) we define the Schattern p-(semi norm as
| Σ min(a,d)
1/r
o{(M)
i=1
Note that in this definition I|-1ls, a norm only when p 2 1. When p E (0, 1), the triangle inequality does not hold. Note that when p E (0, 1), ||A Blls, - 2// 2/2//=((144) (I|Alls, + B for any matrices A and B, however, 2//-11 1.
We L denote the depth of the linear model and W (W1,... ...... WE) to denote the parameters, where W; E x We assume that de 2 min(do, dz. for each i [L- 1] and, thus, the image of E(W) is the entire Xdoo Following is a simple relationship between nuelear norm and Frobenius norm that is used frequently the paper.
Lemma 1. For any matrices A and B, it holds that ||AB||. < ||A||=|B|||..
4 Exact Formulation of Induced Regularizer by Trace of Hessian
In this section, we derive the exact formulation of trace of Hessian for l2 loss over deep matrix factorization models with linear measurements minimization problem over W. We shall later approximate this formula by different function in Section 5, which allows us to calculate the implicit bias in foseddffrrm in the space of end-to-end matrices.
We first introduce the following simple lemma showing that the trace the Hessian of the loss equal to the sum of squares of norms of the gradients of the neural network output.
Lemma 2. For any twice-differentiaalee function (Ji real-valued labels (bx) loss function C(W) = ( - -b,)², and any W satisfying L(W) = 0, it holds that
tr tr(v=c(W)
[F((W]]
Using Lemma 2, we calculate the trace Hessian for the particular loss defined in (2). To do this, we consider W in Lemma 2 to be the concatenation of matrices (W1.... WL) and we set fi (W) be the linear measurement (A,, E (W)). where E(W) W, ... W1 (see (1)). To calculate the trace of Hessian, according Lemma fixed i, we compute the gradient of (A;, F(W)) with respect to one of the weight matrices W,-
need to caleulate the gradient of L(W) in (2). To this end, for
Vw, E(W) = Vw, W.....Wi Wi)
WL... WL...WW+:)W,)) Vw,tt((W, 5-1 ... WiA
(W,-1... W1A, Wz T
According to Lemma 2, trace of Hessian is given by
L
tr( Lr(v Vw, (A,, B( 1
W, W
i=1=
As mentioned earlier, our approach characterize the minimizer of the trace of Hessian among all interpolating solutions by its induced regularizer in the end-to-end matrix space. The above
5

---

calculation provides the following more tractable characterization of induced regularizer F in (12):
F(M)
ΣΣ IW W1 W B(W)= 1=1==1
min
(7)
In general, we cannot solve F in closed form for general linear measurements {- however, interestingly, we show that can be solved approximately under reasonable assumption the mea- surements. In particular, we show that the induced regularizer, as defined in (7), will be approximately proportional to power of the nuclear norm of E(W) given that the measurements {A,]; 1. j== satisfy natural norm-preserving property known as the Restricted Isometry Property (RIP) 42].
Before diving into the proof of the general result for RIP, we first illustrate the connection between nuclear norm and the induced regularizer for the depth-two case. In this case, fortunately, we can compute the closed form of the induced regularizer. This result first proved by Ding et al. [12]. For celf-compls,,ness, we also provide a short proof.
Theorem 5 (Ding et al. [12]). For any M E Rdd. xdo, it holds that
F(M)& A min tr("> =2 ( (.AAAA 1/2 M A (,
1/2
(8)
W2W1=M
Proof of Theorem 5. We first define Bi = 1E A:A;²) and B₂ = (Ei=1 A, T A.) Therefore
have that
v = Σ (IA + IWA = W. 1/+ + || 1
Further applying Lemma 1, we have that
F(M) min W
min
Σ
(114, TIA,TW, W2 ||AA7,11
W.Wi=M
W2W = B W
min
Next we show this lower bound of F(M) can be attained. Let UAVT be the SVD of M The equality condition happens for W = B, 122 Wi A //22TT B2", where we have that 1| = B|| M MB 12. This completes the proof.
Σ ||4," W2 11? A.TA,"10
The right-hand side in (8) will be very close the nuclear norm of M if the two extra multiplicative terms are close to the identity matrix. It turns out that {A, satisfying the (1, R)RIP exactly guarantees the two extra terms are -cloos to identity. However, the case for deep networks where depth is larger than two is fundamentally different from the two-layer case, where one can obtain closed form for F. To the best of our knowledge, it open whether one obtain closed form for the induced-reee reguuaazeer for the trace of Hessian when L > 2. Nonetheless, in Section 5.1, show that under RIP, we can still approximate it with the nuclear norm.
5 Results for Measurements with Restricted Isometry Property (RIP)
In this section, we present our main results for the generalization benefit of flatness regularization in deep linear networks. We structure the analysis follows:
1. In Section 5.1, first recap some preliminaries the RIP property.
2. In Section 5.2, we prove that the induced regularizer by trace of Hessian is approximately the power of nuclear norm for (1, RIPP measurements (Theorem 1).
3. In Section 5.3, we prove that the minimum trace of Hessian interpolating solution with (2, d)- RIP measurements can recover the ground truth M up to error 5 ||M* For [
sampled from Gaussian distributions, we know d = O( do+td.)
4. In Section 5.4, we prove generalization bound with faster rate dotdd ||M using local Rademacher complexity based techniques from Srebro et al. [44].
"
Next, we discuss important distributions of measurements for which the RIP property holds.

---

5.1 Preliminaries for RIP
Definition (Restricted Isometry Property (RIP).. family of matrices {Ailim satisfies the (r, 6)- RIP for any matrix X with the same dimension and rank at most r:
(1 1-1
Σ X), (1+0)) x)
Next, we give two examples of distributions where (dr + dz)) samples guarantee (r, O(L))-RIP. The proofs follow from Theorem 2.3 in [7].
Example Suppose for every E [l,...,nh each entry in the matrix A, an independent standard
Gaussian random variable, i.c., A, t.td. Gdz x For every constant (0, 1). if ((r((doddz)) then with probability 1 (()) {-, satisfies (r, -RRP.
Example 2. If each entry of A, is from symmetric Bernoulli random variable with variance 1, i.e. for all i, k. e, entry [Ai)k,t is either equal to 1 or or with equal probabilities. then for any r and (r. 8)- RIP holds with same probability as in Example 1 if the same condition there is satisfied.
5.2 Induced Regularizer of Trace of Hessian is Approximately Nuclear Norm
This section focuses primarily the proof of Theorem 2. Our proof consists of two steps: (1) show that the trace of Hessian of training loss at the minimizer W is multiplicatively O(0)-s to the regularizer R(W) defined below (Lemma 3) and (2) we show that the induced regularizer of Rt (MM,,, proportional to |1M1]12211 (Lemma 4).
R(W) [Wr.... do +
Σ 3=2
IW, W H- 11 Wi I| Willidd.
(10)
Lemma 3. Suppose the linear measurement {A, satisfy (1,5)-RIP. Then, for any W such that
L(W)- = 0, it holds that
(1- () S (r(V)))(W) < (1 + R(W)).
Since tr( (r(V?C)(W) closely approximates RWW, ), we can study instead of tr V C] to understand the implicit bias up to multiplicative factor (1 + 8). In particular, want to solve the induced regularizer ((W) W)) on the space end-to-end matrices, F'MM):
('MM) A
min
R(W).
(11)
W:W.--Wi-M
Surprisingly, solve this problem in closed form.
Lemma 4. For any M E Rdd, it holds that
min F'MM) WL..W,
R(W) V1I
(12)
Proof of Lemma 4. Applying the L-version the AM-GM to Equation (10):
(R(W)/L)* 2d WoollW -.- -. | W ... Wall ... W ... W1 11
(13)
---1
Tppp II f=1
(IW22
..,.W 16 [W will?)
Now using Lemma 1, we have for every < 1-
[[ W, 11: ... W1 W1 2 W ... wi = [
(14)
Multiplying Equation (14) for all < 1 < and combining with Equation (13) implies
R(W) > I(dod)) 1)/-
min [W] W;
(15)
7

---

Now we show that equality can indeed be attained. To construct an example in which the equality happens, consider the singular value decomposition of M: M UAV", where A is square matrix with dimension rank(M).
For S S L, we pick Qi E R4:xran((M) to be any matrix with orthonormal columns. Note that rank(M) larger than d, for all S L. hence such orthonormal matrices Qi exist. Then define the following with a, a' > 0 being constants to be determined:
WL a'a 2 U T R Xdz
W; = aQ xdixd-1, V2 Li
W1 a' a0 Q/ Rdixd.
Note that A is a square matrix with dimension rank(M). First of all, note that the defined matrices satisfy
a ( M.
To gain some intuition, we check that the equality case for all the inequalities that we applied above. We set the value of a in a way that these equality cases can hold simultaneously. Note that for the matrix holder inequality that we applied in Equation (14):
[|W.... Wi+1 W1 ||, ... Will
| Wi = 1
independent of the choice of a. It remains to check the equality case for the AM-GM inequality that we applied in Equation (13). We have for all 2 J <
WW... ... W - WilFF
a 2 (T. 2)/2 1-jj1 a (L- 2)/ MIAIIIAAA 1/2 | 1=aa 11
(16)
Hence, equality happens for all of them. Moreover, for cases j = 1 and L, have
doll W. W2 = || do a 2 = | 1 a 22/2
(17)
... Wi L.llW....... 1/2 Fd 1 a -11-2)/1)) ||A | || 2 a (L-2)/2
(1--2)/2
(18)
Thus it suffices to set a' + 112 and a ||A ya/ of (16), (17), and (18) equal, which implies that the lower bound in Equation (15) is actually an equality. The proof is complete.
( )1/T. so that the left-hand sides
ddddz
Now can prove Theorem an implication of Lemma 4.
Proof of Theorem I. The first claim a corollary of Lemma 3. We note that
F(M)- = min tr V (M) < (1 + 5) min
R (W) = (1 +1 51)
Wi...Wi.Mh
Wz... WI=M
F(M) min ur ( 2 8)
min
R(W) = (1 (1- (M)
W....WF.M
Wz W....i:MM
For the second claim, pick W that minimizes R( R(W) over all W's that satisfy the linear measurements, thus have that
R(W) = L(d,dd)) 2(1-1)/L = L(dodz)
min 2(M)=0
|M] 1(.-
(19)
Now from the definition of E(W*),
ur( ur(v") L)V < (r(V))(() s (1+))R(W)
(20)
where the last inequality follows from the definition of W. On the other hand tr( (w(") 2 (1 R)R (1 1" (0 Combining (19), (20) and (21),
2(L-1)/2
(21)
1 + 8 (
((-
min ||
1-8 8 ((M
The proof is completed by noting that 2TL-13 < 1 for all 2.
8

---

Thus combining Example and Theorem with = 1/2, we have the following corollary.
Corollary 1. Let {Ai] be sampled independently from Gaussian distribution Gd where n 2 Q((do + dr.),, with probability at least exp(S((n)) we have
|E(W*) I]- 3 min |M (|
CM(M==U
5.3 Recovering the Ground truth
In this section, we prove Theorem 2. The idea is to show that under RIP, the empirical loss L(W) is good approximation for the Frobenius distance of F(W) the ground truth M To this end, first introduce a very useful Lemma 5 below, whose proof is deferred to Appendix E.
Lemma 5. Suppose the measurements 1 {A satisfy the (2, RRPI condition. Then for any matrix M E Rd xda, we have that
Σ i-
MM 2
We note that if {Ar are i.i.d. random matrices with each coordinate being independent, zero mean, and unit variance (like standard Gaussian distribution), then || .M" 1/2 the population squared loss corresponding to W. Thus, Theorem 2 implies generalization bound for this case. Now we are ready to prove Theorem 2.
Proof of Theorem 2. Note that from Theorem 1,
1+6 8 |E(W") - 1-8 C'())=
|M], - 1+ 8
min
II 1|
8
which implies the following by triangle inequality,
(E(W*) M - || I|+ + ||M| S 2
-811M4 |1
(22)
Combining (22) with Lemma 5 (with M = E(W) -
1 Σ (Ai, E(W") (('"")M-">" (E(--E(()) M 1/
86
M
(1 8)2
Since W* satisfies the linear constraints tr( ((A,F((W") = by 1 E (A,, F(W*) - -Ma,²
1 Ei= (A,, E(W*)) - b,)² 0, which completes the proof.
5.4 Generalization Bound
In this section, we prove the generalization bound in Theorem 3, which yields a faster rate of 0 0f [[3) compared to O( do []M+ in Theorem 2. The intuition for this is as follows: By Corollary 1, we know that with very high probability, the learned solution has a bounded where M is the ground truth. The upper bound on the population error of the learned interpolation solution that is proportional to the square of the Rademacher complexity of the function class Haijar ||. {loM [[M]] S 3 3lMM"
key mathematical tool is Theorem 6, which provides | |M
nuclear norm for its end-to-end matrix, no larger than 3
Theorem 6 (Theorem 1, Srebro et al. [44]). Let H be class of real-valued functions and E R x - R be differentiable non-negative loss function satisfying that (1) for any fixed y R, the partial derivative E(;, g) with respect to its first coordinate H H-Lipschitz and (2) supa, E(x, y)1 I B, where H, B are some positive constants. Then for any p > O, we have that with probability at least 1 - over random sample of size n, for any h E H with zero training loss.
E(h) S 2 O
(H log nR
(H) nR2((H)
13 Bog(L1/))
(23)
n
One technical difficulty is that Theorem 6 only works for bounded loss functions, but the &g loss on Gaussian data unbounded. To cireumvent this issue, we construct a smoothly truncated variant of l2 loss (41) and apply Theorem 6 that. Finally, we show that with carefully chosen threshold, this truncation happens very rarely and, thus, does not change the population loss significantly. The proof can be found in Appendix E.

---

L-2
L-3
L-5
L-10
18"1
37"
Lanel Node
50-
mf taze Mode
23"
Al Lakel hede
Latsl
Noan
Alu Mowe
10"
33
treration
Ieeration
Berattn
tteration
wi Label Nooe
137
we Labe hode
Test
Noba
Lase Natse 672 Label Nome
Label Nobs 4/0 Label Natio
6n2 Label Nowe
Decetion
Iecettion
Figure 1: Train and test loss. Label noise SGD leads to better generalization results due to the sharpness-mininen minimizaioon implicit biases (as shown in Figure 2), while mini-batch SGD without label noise finds solutions with much larger test loss.
6 Result for the Single Measurement Case
Quite surprisingly, even though in the general case we cannot compute the closed-form of the induced regularizer in (12), we can find its minimum a quasinorm function of the E(W) which only depends on the singular values of E(W. This yields the following result for multiple layers L (possibly L > 2) with a single measurement.
Theorem 7. Suppose there is only single measurement matrix A, i.e., = 1. For any M E IRdz the following holds:
tr u(V2A](W) = (.. -AT(( A7
4-1
2/L
F(M) = min W
(24)
82yl
To hetter illustrate the behavior of this induced regularizer, consider the case where the measurement easy to see that F(M) in (24) is equal to F(M) = Σ, 2(4-1)/1 Interestingly, we see that the value of F(M) converges to the Frobenius norm M and not the nuclear norm L becomes large, which behaves quite differently (e.g. in the context of sparse recovery). This means that beyond RIP, the induced regularizer can behave very differently, and perhaps the success of training deep networks with SGD is closely tied to the properties of the dataset.
matrix A identity and M is symmetric with eigenvalues {o.) Then,
7 Conclusion and Future Directions
In this paper, we study the inductive bias of the minimum trace of the Hessian solutions for learning deep linear networks from linear mcasurements. We show that trace of Hessian regularization of loss on the end-to-end matrix of deep linear networks roughly corresponds to nuclear norm regularization under restricted isometry property (RIP) and yields way to recover the ground truth matrix. Furthermore, leveraging this connection with the nuclear norm regularization, we show generalization bound which yields a faster rate than Frobenius (or & norm) regularizer for Gaussian distributions. Finally, going beyond RIP conditions, we obtain closed-form solutions for the case of single measurement. Several avenues for future work remain open, e.g., more general characterization of trace of Hessian regularization beyond RIP settings and understanding it for neural networks with non-linear activations.
Acknowledgement
TM and ZI. would like to thank the support from NSF 2045685, KG and acknowledge support by NSF award CCF-2112665 (TILOS AI Institute) and NSF award 2134108.
10

---

References
[1] Maksym Andriushchenko and Nicolas Flammarion. Towards understanding sharpness-aware minimization. In International Conference on Machine Learning, pages 639-6688 PMLR, 2022.
[2] Maksym Andriushchenko, Francesco Croce, Maximilian Müller, Matthias Hein, and Nicolas Flammarion. A modern look at the relationship between sharpness and generalization. arXiv preprint arXiv:2302.070/1 1, 2023.
[3] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, pages 7411-7422, 2019.
[4] Sanjeev Arora, Zhiyuan Li, and Abhishek Panigrahi. Understanding gradient descent on edge of stability in deep learning, arXiv preprint WrXiv:2205.09745. 2022.
[5] Mohamed Ali Belabbas. On implicit regularization: Morse functions and applications to matrix factorization. arXiv preprint urXiv:2001.044 04420444 2020.
[6] Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an ornstein-uhlenbeek like process. arXiv preprint arXiv:1904.00 09080, 2019.
[7] Emmanuel J Candes and Yaniv Plan. Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements. IEEE Transactions on Information Theory, 57(4):2342-2359 2011.
[8] Jeremy M. Cohen, Simran Kaur, Yuanzhi Li, J. Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability, 2021.
[9] Jeremy M Cohen, Behrooz Ghorbani, Shankar Krishnan, Naman Agarwal, Sourabh Medapati, Michal Badura, Daniel Suo, David Cardoze, Zachary Nado, George E Dahl, et Adaptive gradient methods at the edge of stability. arXiv preprint arXiv:2207. 1...22277..444, 2022.
[10] Alex Damian, Tengyu Ma, and Jason Lee. Label noise sgd provably prefers flat global minimiz- ers, 2021.
[11] Alex Damian, Eshaan Nichani, and Jason D Lee. Self-stabilizzatio:: The implicit bias of gradient descent at the edge of stability. arXiv preprint arXiv:2209. 15594, 2022.
[12] Lijun Ding, Dmitriy Drusvyatskiy, and Maryam Fazel. Flat minima generalize for low-rank matrix recovery. arXiv preprint (:X.::22330037566 2022.
[13] Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In Proceedings of the 34th International Conference on Machine Bharning-Volumee 70, pages 1019-1028. JMLR. org, 2017.
[14] Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred Hamprecht. Essentially no barriers in neural network energy landscape. In International conference on machine learning, pages 1309-1318, PMLR, 2018.
[15] Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data, arXiv preprint arXiv: 100..770000000 2017.
[16] Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware mini- mization for efficiently improving generalization. arXiv preprint arXiv:2010.01412, 2020.
[17] Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware min- imization for efficiently improving generalization. In International Conference on Learning Representations, 2021.
[18] Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. Advances neural information processing systems, 31, 2018.

---

[19] Daniel Gissin, Shai Shalev-Shwariz and Amit Daniely. The implicit bias of depth: How incremental learning drives generalization. arXiv preprint arXiv: 12051, 2019.
[20] Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pages 6151-6159, 2017.
[21] Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 9(1):1-42, 1997.
[22] Arthur Jacot, François Ged, Franck Gabriel, Berfin Simsek, and Clément Hongler. Deep linear networks dynamics: Low-rank biases induced by initialization scale and 12 regularization. arXiv preprint vrXiv:2106.15933 3, 2021.
[23] Stanishaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint arXiv:1711004623, 2017.
[24] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. arXiv preprint 1rXiv:191.00/// 2019.
[25] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: (16699048366 2016.
[26] Jungmin Kwon, Jeongscop Kim, Hyunseo Park, and In Kwon Choi. Asam: Adaptive sharpness- aware minimization for scale-invariant learning of deep neural networks. In International Conference on Machine Learning, pages 9905-5914. PMLR, 2021.
[27] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. arXiv preprint arXiv:1712.09200 pages 2-47, 2017.
[28] Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. arXiv preprint arXiv:2012.09839) 2020.
[29] Zhiyuan Li, Tianhao Wang, and Sanjeev Arora. What happens after sgd reaches zero loss?-a mathematical framework. In International Conference on Learning Representations, 2021.
[30] Zhouzi Li, Zixuan Wang, and Jian Li. Analyzing sharpness along gd trajectory: Progressive sharpening and edge of stability. arXiv preprint 2rxiv:2207.12678 2022.
[31] Hong Liu, Sang Michael Xie, Zhiyuan Li, and Tengyu Ma. Same pre-training loss, better downstream: Implicit bias matters for language models. 2022.
[32] Yong Liu, Siqi Mai, Xiangning Chen, Cho-Jui Hsieh, and Yang You. Towards efficient and scalable sharpness-aware minimization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12360-12370, 2022.
[33] Kaifeng Lyu, Zhiyuan Li, and Sanjeev Arora. Understanding the generalization benefit of normalization layers: Sharpness reduction. arXiv preprint wxXiv:2266.07033 2022.
[34] Chao Ma and Lexing Ying. On linear stability of sgd and inoutesmo of neural networks. Advances in Neural Information Processing Systems,
16810, 2021.
[35] Chao Ma, Lei Wu, and Lexing Ying. The multiscale structure of neural network loss functions: The effect on optimization and origin. arXiv preprint arXh::2204.11326 2022.
[36] Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in noncon- vex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pages 3345-3354. PMLR, 2018.
12

---

[37] Mor Shpigel Nacson, Kavya Ravichandran, Nathan Srebro, and Daniel Soudry. Implicit bias of the step size in linear diagonal neural networks. In International Conference on Machine Learning, pages 16270-16295. PMIR, 2022.
[38] Behnam Neyshabur, Srinadh Bhojamapalli, David McAllester, and Nati Srebro. Exploring generalization in deep learning. In Advances in Nearal Information Processing Systems, pages 5947-5956, 2017.
[39] Matthew Norton and Johannes O Royset. Diametrical risk minimization: Theory and computations, Machine Learning, pages 1-19, 2021.
[40] Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms. arXiv preprint arXiv:2005.06339, 2020.
[41] Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in tensor factorization. In International Conference on Machine Learning, pages 8913-8922 8924. PMLR, 2021.
[42] Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471-501, 2010.
[43] Mark Rudelson and Roman Vershynin. Non-asymptotic theory of random matrices: extreme singular values. In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II-IV: Invited Lectures, pages 1576-1602. World Scientific, 2010.
[44] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. Advances in neural information processing systems, 23, 2010.
[45] Dominik Stöger and Mahdi Soltanolkotabi. Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterizedd low-rank matrix reconstruction. Advances in Neural Information Processing Systems, 34:23831-23843, 2021.
[46] Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. In Advances in Neural Information Processing Systems, pages 9722-9733, 2019.
[47] Colin Wei and Tengyu Ma. Improved sample complexities for deep networks and robust classification via an all-layer margin. arXiv preprini
2019.
[48] Kaiyue Wen, Tengyu Ma, and Zhiyuan Li. How does sharpness-aware minimization minimize sharpness? arXiv preprint (tt::2211.05729 2022.
[49] Dongxian Wu, Shu-Tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust generalization. Advances in Neural Information Processing Systems, 33:2958-2969 2020.
[50] Lei Wu, Chao Ma, and Weinan E. How sgd selects the global minima in werrpaaameetrrized learning: A dynamical stability perspective. Advances in Neural Information Processing Systems, 31, 2018.
[51] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations (ICLR), 2017.
[52] Yang Zhao, Hao Zhang, and Xiuyuan Hu. Penalizing gradient norm for efficiently improving generalization in deep learning. arXiv preprint vmXiv:2202.0359) 2022.
[53] Yaowei Zheng, Richong Zhang, and Yongyi Mao. Regularizing neural networks via adversarial model perturbation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1166-8165, 2021.
[54] Juntang Zhuang, Boqing Gong, Liangzhe Yuan, Yin Cui, Hartwig Adam, Nicha Dvornek, Sekhar Tatikonda, James Duncan, and Ting Liu. Surrogate gap minimization improves charpness-aware training. arXiv preprint arXiv:2203 08065, 2022.
13


Reviews:
[{"review_id": "kEjQHEItrT", "reviewer": "Reviewer_sgkx", "summary": "This work considers the implicit regularization of deep neural networks with linear activations and linear data. While previous works have shown that stochasticity in optimizers has the effect of smoothing the loss function, this work derives how this less sharp loss function can result in better generalization performance under certain assumptions. Specifically, the authors derive the induced regularizer in three cases: (1) two-layer linear networks, (2) networks learned with a single example, and (3) data that satisfies the restricted isometry property. Then, in these settings, generalization bounds are derived. ", "questions": "* I found the terminology of \"end-to-end parameters\" (e.g. L52+53) to be slightly non-intuitive for its intended meaning. Possibly because in other parts of the machine learning literature this terminology refers to a different concept (models that are trained jointly in a non-modular way). Is this standard terminology in this literature? If not, it might be helpful to use an alternative or make this more clear.  ", "limitations": "Yes. I cannot foresee any potential negative societal impact of this work", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "* I found this work to be very well presented and clear. In general, I found the presentation made the content quite accessible for a reader not familiar with the literature. I appreciate the author's effort to ensure the content was as self-contained as possible with all required background knowledge neatly included. \n* I found Sec. 1.1 summarizing the main results of the work to be extremely helpful before proceeding into the details later. \n* Notation was well-considered, clear, and consistent.\n* The related work section was extensive between the main text and the appendix. Although I am not familiar with this literature, this section provided a helpful summary (although I cannot comment on its accuracy). \n* The claims made in the abstract are an accurate reflection of the paper's contributions. \n* Some synthetic numerical experiments are provided to validate the theoretical findings. ", "weaknesses": "* My single major issue with this work is with respect to its practical significance. Almost the entire contribution of this work lies in the theoretical results derived within. However, all of these results are derived under extremely restrictive assumptions/conditions. My understanding is that they assume (at a minimum):\n   - A neural network with linear activations. \n   - The regression setting (I believe results would not hold under e.g. cross-entropy loss?) \n   - The relationship between the observations and their ground truth targets is linear. \n   - No hidden layer within the network has fewer hidden neurons than either the input or output layer. This would rule out any problem with a single label per observation. \n\n   Then, the results are derived within three even more restricted settings: (1) the network has exactly two layers (2) the network is learned upon a dataset consisting of a single example or (3) the data satisfies the RIP property. Some of the later theorems require even more assumptions such as $iid$ observations satisfying $\\mathbb{E}_A \\braket{A,M}^2 = ||M||^2_F$. I believe it is uncontroversial to say these results cannot be applied to any practical task. Therefore, I would challenge the authors to make the case as to how this work contributes itself or could have some downstream contribution to real-world problems/tasks. While this conference is a suitable venue for a theory-style paper such as this, I would argue that the choice of whether to accept such a paper should be heavily weighted by its potential practical impact (otherwise we can always invent interesting, but purely fictitious problems). \n\nMinor issues/clarifications:\n* While I realize that the experiment was straightforward, it is always nice to include the code used to generate the results. Could this be added to a camera-ready version? \n* On L22+23 the paper states that \"despite the overwhelming empirical evidence on ... the effectiveness of using sharpness regularization on improving generalization [15, 47, 51, 37], the connection between penalization of the sharpness of training loss and better generalization still remains unclear.\" Could the authors clarify how these are not the same thing? I suspect the point is clear to the authors but could just be worded more clearly. \n* On L169: is this intended to refer to eqn (12)? \n* Should the experiments in Fig 2 not also include a baseline of a model trained without label noise? \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**\"While this conference is a suitable venue for a theory-style paper such as this, I would argue that the choice of whether to accept such a paper should be heavily weighted by its potential practical impact (otherwise we can always invent interesting, but purely fictitious problems)\"**\n\n**Reply**: Deep matrix factorization is a practically significant setting which was not invented in this work; it is established by previous Neurips papers, e.g., [Implicit regularization in matrix factorization, Gunasekar et al., NIPS 2017](https://proceedings.neurips.cc/paper_files/paper/2017/file/58191d2a914c6dae66371c9dcdc91b41-Paper.pdf), [Implicit regularization in deep matrix factorization, Arora et al., NIPS 2019](https://proceedings.neurips.cc/paper_files/paper/2020/file/f21e255f89e0f258accbe4e984eef486-Paper.pdf).\n\n**\"The activations are linear.\"**\n\n**Reply**: As we pointed out, understanding the trace of Hessian regularizer for deep linear models is highly non-trivial as the regularizer is not computable in closed-form for depth beyond two. Therefore, similar to some of the previous impactful papers in the theory of deep learning, here we also focus on the first major difficult problem which is dealing with deep linear models.\n\n**\"No hidden layer within the network has fewer hidden neurons than either the input or output layer. This would rule out any problem with a single label per observation.\"** \n\n**Reply**: This is not the case, for example if one chooses $A_i$ to be in the rank-one form $w^\\top x_i$, for fixed weight vector $w$ and input vector $x_i$, then the single output prediction problem is recovered. The purpose of our work is to illustrate the surprising almost equivalence of the trace of hessian regularizer with the nuclear norm of the end-to-end matrix in deep matrix factorization, and the RIP condition is a natural and fairly general assumption on the data which allows the analysis to go through in a clean way without unnecessary lengthy derivations (indeed one can probably regenerate this result using some other concentration techniques but its beyond the purpose of this work.)\n\n## Minor Issues and Questions:\n**It is always nice to include the code used to generate the results. Could this be added to a camera-ready version?**\n\n  **Reply**: Yes we will include the code in the camera-ready version.\n\n**On L22+23 the paper states that \"despite the overwhelming empirical evidence on ... the effectiveness of using sharpness regularization on improving generalization [15, 47, 51, 37], the connection between penalization of the sharpness of training loss and better generalization still remains unclear.\" Could the authors clarify how these are not the same thing?**\n\n   **Reply**: Penalizing the sharpness of the training loss is an implicit bias mechanism, but it is not clear how this bias will impact the generalization behavior for general networks.\n\n**On L169: is this intended to refer to eqn (12)?**\n\n  **Reply**: Yes, but since it is a forward reference it might be clearer if we remove it, so we will rephrase this in the final version. \n\n**Should the experiments in Fig 2 not also include a baseline of a model trained without label noise?**\n\n  **Reply**: We will add the no label noise case to the final version, and also more settings. See the plots in the pdf included with this rebuttal.\n\n**I found the terminology of \"end-to-end parameters\" (e.g. L52+53) to be slightly non-intuitive for its intended meaning.**\n\n  **Reply**: We thank the reviewer for mentioning this delicate point, we will change this phrase to end-to-end matrix in the final version.\n\n"}, {"review_id": "0rFPxfrr9u", "reviewer": "Reviewer_PGyv", "summary": "The manuscript seeks to understand Hessian trace regularization in the case of deep linear network training with the mean squared error of linear measurements. It obtains a description of the effective regulariser which can be approximated and made more explicit in some cases. The manuscript obtains results on matrix recovery and generalization.", "questions": "* In Theorem 1 it is indicated that the data should satisfy an RIP assumption, but this condition is not described explicitly. The (1,\\delta)-RIP condition should be described explicitly before or at the time of stating the theorem. \n* After Theorem 1 it is stated that in more general cases it is challenging to compute F, but it is not clearly stated what is meant by more general cases.\n* In Theorem 2, what is the dependence on n? \n* In Theorem 3, what is r? This seems to be introduced 3 pages later in Definition 3. \n* Theorem 4 appears to consider regularization of the end to end matrix. What would be the result if one instead minimises the l2 norm of the parameters (factor matrices)? \n* There are typos in the display equation following line 166. \n* In Theorem 5 the argument of the Hessian of the Loss should be the factor matrices? \n* Example 1, missing negative sign in exponent? \n* Please add an explanation for the second inequality in (13).  \n* In proof of Theorem 1, argument is W_1,\\ldots, W_L instead of M? ", "limitations": "* The work considers deep linear networks with no bottlenecks, in which case the image function space contains all matrices. \n* It would be interesting to combine and compare the discussion of trace of Hessian minimisation with l2 regularization of the parameters. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The problem under investigation, to characterize solutions with minimum Hessian trace, is interesting. \n* The work obtains results indicating that the number of measurements needed to obtain a good approximation of a target matrix is smaller when using trace regularization as opposed to l2 regularization of the end to end matrix. ", "weaknesses": "* The presentation of the results does not make the assumptions sufficiently clear in a timely manner. \n* The settings are restrictive. The networks are assumed to have no bottlenecks, so that the set of representable end to end matrices have no constraints. The considered objective function is a sum of squared errors of linear measurements, whereby it is assumed that the measurements satisfy an RIP property, or that the network has only two layers, or that there is only one measurement. \n* The theoretical results could have been strengthened by numerical experiments, particularly given the restricted conditions for which the theoretical results are obtained. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **The presentation of the results does not make the assumptions sufficiently clear in a timely manner.**\n\n     **Reply**: We would like to point out that the RIP and width assumptions are mentioned in pages 2 and 3, but we are happy to follow the reviewers’ suggestions on stating them earlier.\n\n2. **The settings are restrictive.**\n\n     **Reply**: In the general case of multiple measurements, that we analyze here, the trace of hessian regularizer does not have a closed form, so it is very challenging to analyze (e.g., prior works make strong assumptions such as 2 layers). Yet, we manage to approximate it with a function of the nuclear norm under RIP, which is highly non-trivial. Of course, it is an interesting future direction to understand the behavior of the implicit bias in other remaining settings, e.g. when the distribution of the matrices are heavy-tailed.\n\n3. **The theoretical results could have been strengthened by numerical experiments**: \n\n     **Reply**: Some preliminary experiments are included in Appendix F. We will include more detailed experiments in the final version, see the plots in the included pdf.\n\n## Questions:\n1. **The (1,$\\delta$)-RIP condition should be described explicitly before or at the time of stating the theorem.**\n\n   **Reply**: We will define RIP before the main result to make it clearer for the reader.\n\n2. **After Theorem 1 it is stated that in more general cases it is challenging to compute F, but it is not clearly stated what is meant by more general cases.**\n\n     **Reply**: By more general cases, we mean beyond the one-measurement case and the RIP condition for multiple-measurements. As we mentioned, the case of multiple measurements for depth more than two (unlike the depth two case) is not solvable in closed form. We will clarify this in the final version.\n\n3. **In Theorem 2, what is the dependence on n?**\n\n     **Reply**: Note that in general in the definition of RIP (Definition 3) $\\delta$ implicitly depends on $n$ and this dependency can vary for different distributions. But for example, for the Gaussian case we have $\\delta(n) = \\sqrt{\\frac{d_L + d_0}{n}}$ as stated right after Theorem 2.\n\n4. **In Theorem 3, what is r? This seems to be introduced 3 pages later in Definition 3.**\n\n     **Reply**: $r$ should be set to one here, thanks for pointing to this typo.\n\n5. **Theorem 4 appears to consider regularization of the end to end matrix. What would be the result if one instead minimizes the l2 norm of the parameters (factor matrices)?**\n\n     **Reply**: While in this work we are interested to see the effect of trace of hessian regularization as a function of the end to end matrix, the problem of regularizing the factor matrices, e.g., with l2 as the reviewer mentioned, is indeed interesting on its own. We conjecture the induced regularizer of $\\ell_2$ norm minimization is the Schatten-$2/L$- (semi)norm of the end-to-end matrix, though we don’t have a proof for depth $L$ larger than $3$.\n\n\n6. **There are typos in the display equation following line 166.**\n\n   **Reply**: Thanks for pointing this out, we will add the missing gradient to this equation.\n\n7. **In Theorem 5 the argument of the Hessian of the Loss should be the factor matrices?**\n\n   **Reply**:We see $\\min\\{W_1W_2=M\\}tr[\\nabla^2 \\mathcal L]$ in total as a function of $M$, which is why we put its argument to be $M$.\n\n8. **Example 1, missing negative sign in exponent?**\n\n    **Reply**: Thanks for pointing this out, we will fix it in the final version.\n\n9. **Please add an explanation for the second inequality in (13).**\n\n   **Reply**: That is a rearrangement of the terms and indeed it is an equality, we will clarify it further in the final version.\n\n10. **In proof of Theorem 1, argument is $W_1,\\ldots, W_L$ instead of $M$?**\n\n     **Reply**: Same response as case 7 above.\n"}, {"review_id": "TMLFkMiiS3", "reviewer": "Reviewer_ecS4", "summary": "In the context of matrix sensing with deep matrix factorizations, the paper analyzes the inductive bias of interpolators with minimal Hessian trace, which is a well-known measure of sharpness. Specifically, under a Restricted Isometry Property (RIP) assumption on the linear measurements, it establishes that the minimal Hessian trace with which the deep matrix factorization can express an interpolator is approximately equal to the latter’s nuclear norm. In turn, this yields guarantees on the recovery of the ground truth matrix, as well as a separation result from the recovery obtained by the minimal Frobenius norm interpolator.\n\nAs an additional contribution, develops a closed form expression for the minimal Hessian trace of an interpolator when there is only a single linear measurement.", "questions": "Have you considered other notions of sharpness besides the trace of the Hessian, e.g. its the maximal eigenvalue? In particular, can minimizing the maximal eigenvalue of the Hessian ensure generalization in the considered setting, or is it too weak and one must look at the trace of the Hessian?", "limitations": "The authors have adequately addressed limitations of the work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Well-written and easy to follow. The motivation, problem at hand, and main results are clearly described.\n\n2. Helpful discussions are provided for each of the technical results, in particular regarding their implications and relation to existing work.\n\n3. The technical contributions establish a new connection between flatness, in terms of minimal Hessian trace, and generalization for deep matrix factorizations (previous work of Ding et al. 2022 studies only depth two factorizations). Despite conventional wisdom and empirical evidence suggesting that flatness may lead to good generalization, formally showing that this is the case has proven challenging. This attests to the significance of the current paper’s results.\nPersonally, I found it interesting that depth does not help in the analyzed setting, in the sense that minimizing the Hessian trace amounts to approximately minimizing the nuclear norm, similar to the depth L = 2 case. This may suggest that deep matrix factorization with RIP measurements is an unsatisfactory setting for uncovering the benefits of depth in deep learning and its (possible) relation with flatness.\n", "weaknesses": "The points below pertain to the scope of the technical contributions, suggesting places for improvement. I do not believe that points (2) and (3) significantly harm the quality of the current paper and are perhaps considerations for future work. For (1), it seems that it may be straightforward to incorporate, in which case I believe it can increase the generality of the current work.\n\n1. Only interpolators with exactly minimal Hessian trace are considered. Since in practice a more realistic view is that it is only approximately minimized, if possible, it is worth (even if in an appendix) extending the generalization results to interpolators whose Hessian trace is approximately minimal.\n\n2. The current paper characterizes the regularizer induced by minimizing the Hessian trace only for interpolators. Since using explicit regularization can lead to solutions that don't entirely minimize the loss to zero, I believe it is important to understand the inductive bias of minimizing the Hessian trace for non-interpolating linear mappings as well. While more complex, it may be more realistic.\n\n3. The current paper only treats the question of what interpolating the data with minimal Hessian trace implies, and not the complementary question of whether it, or other measures of sharpness more generally, are implicitly minimized in deep matrix factorization by standard optimizers.\n\nAdditional (minor) comments and typos:\n- Typo in line 75: “regularzier” should be “regularizer”.\n- Typo in line 101: I believe “observe” should have been “observed”.\n- Typo in equation after line 166: I believe there is a missing gradient symbol in the middle expression and a factor of two in both the middle and right expressions.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **If possible, it is worth (even if in an appendix) extending the generalization results to interpolators whose Hessian trace is approximately minimal.**\n\n   **Reply**: We will include this generalization in the appendix in the final version of the work.\n\n2. **Since using explicit regularization can lead to solutions that don't entirely minimize the loss to zero, I believe it is important to understand the inductive bias of minimizing the Hessian trace for non-interpolating linear mappings as well. While more complex, it may be more realistic.**\n\n   **Reply**: Note that for points where the loss is non-zero, the form of trace of hessian of the loss is not given by Lemma 2 and Equation (7). Therefore, our approach in approximating the minimizers of these terms given a fixed end-to-end matrix and recovering the nuclear norm of the end to end matrix is not valid anymore; namely, this approximation will further depend on the distance to the manifold of zero loss. While beyond the scope of this work, our guess is that given some measure of closeness to the manifold (i.e. close to satisfying the linear constraints), one should still be able to use the same approach to approximate the trace of hessian regularizer.\n\n\n3. **The current paper only treats the question of what interpolating the data with minimal hessian trace implies, and not the complementary question of whether it, or other measures of sharpness more generally, are implicitly minimized in deep matrix factorization by standard optimizers.**\n\n    **Reply**: The problem of convergence of label noise SGD to the minimizer of trace of hessian for deep linear models is open and can be an interesting future direction.\n\n\n **Typos**: Thanks for pointing them out, we will fix them in the final version.\n\n## Question:\n\n**Have you considered other notions of sharpness besides the trace of the hessian, e.g. its maximal eigenvalue?**\n\n **Reply**: The maximum eigenvalue regularizer can be obtained via different algorithms and a possible analysis for deep matrix factorization with maximum eigenvalue does not seem to be relevant to the analysis of the trace of hessian we are presenting, but is certainly an interesting future direction. Empirically, label noise SGD is observed to decrease the trace of hessian; this behavior is also proved mathematically in the limit of step size going to zero, in [28].\n"}, {"review_id": "IIEOFXGb71", "reviewer": "Reviewer_JwkB", "summary": "The paper studies the minimizers of the loss surface of deep matrix factorization that have a minimal trace of the Hessian. The trace of the Hessian is a measure of flatness of the minimum, that is favored by SGD.\n\nThe authors show that for matrix sensing with observations that satisfy RIP (which is in particular true for enough Gaussian observations) the parameters that are the flatest have end-to-end matrix that approximately minimize the nuclear norm amongst fitting matrices. This in turn implies generalization guarantees that are significantly faster than the if one were to minimize the Frobenius norm instead of the nuclear norm.", "questions": "A shallow linear network with L2 regularization is also known to recover the minimal nuclear norm solution [Dai et al., Representation Costs of Linear Neural Networks: Analysis and Design]. Do you think that there is any advantage to rely on the flatness bias instead of the L2 regularization?", "limitations": "The biggest limitation is clearly the RIP condition, but it is well discussed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The description of the flatness bias given by this paper is to my knowledge new, and some of the results are a bit unexpected.\n\nThe writing is clear and thorough and the proofs are easy to understand.", "weaknesses": "The results hangs on the fact that the trace of the Hessian is the right notion of flatness for SGD, which is to my knowledge not decided yet. For GD the relevant measure of flatness is instead the largest eigenvalue of the Hessian, which will probably lead to a quite different implicit bias. And since SGD can in some cases be quite similar to GD, it seems unlikely that the bias would simply be described by the trace of Hessian, instead this exact bias could change depending on the learning rate and batch size.\n\nThe lack of empirical experiments to test whether the bias described here is observed for SGD, label noise SGD or 1-SAM would help motivate this assumption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**implicit bias**: We would like to point out that in the paper [28] authors mathematically show that in the limit of step size going to zero, label noise SGD evolves according to a gradient flow according to the trace of hessian of the loss. The same fact can be seen for 1-SAM,  but the reviewer is right that it might not be the right notion for vanilla SGD.  \n\n**Experiments**: In the final version, we will include additional experiments that show how the trace of Hessian evolves for SGD with and without label noise, see also the pdf included with this rebuttal. Indeed, we do observe that label noise SGD decreases the trace of the Hessian.\n"}]

Author rebuttal:
We would like to thank the reviewers for their effort to provide helpful comments regarding our work. In the following, we have replied to their comments separately.

Meta-review: Recent studies involving over-parameterized neural networks have illuminated the fact that the inherent stochastic nature of optimizers has an implicit regulatory impact on reducing the steepness of the loss function in particular as it relates to the trace of its Hessian matrix, particularly when considering solutions where the loss is reduced to zero. Additionally, there have been empirical observations indicating that more explicit variations of flatness regularization contribute to an enhancement in the generalization capabilities of these networks. This paper aims to study this typo of phenomenon for training of deep linear networks and shows under RIP minimizing the trace of the Hessian is approximately equivalent to minimizing the nuclear norm. 

Most reviewers thought the paper was well written. They did raise concerns about the limitations to linear networks, the result not being directly about first order methods etc. One reviewer in particular expressed concerns about the practical relevance of these assumptions. Some of these concerns were alleviated in the discussion. My own reading of the paper is that is well written, it is a cute but not substantial or particularly hard result to prove from a theoretical standpoint. I also agree with the limitations raised by the reviewer. However, I still think the paper would be of interest as an initial study and merits publication in Neurips.
Decision: Accept (poster)