Implicit regularization via Spectral Neural Networks and non-linear matrix sensing
Authors: Subhroshekhar Ghosh
Thanh Lam
Soumendu Sundar Mukherjee
Venue: Submitted to ICLR 2023 (2023)

Abstract: The phenomenon of \textit{implicit regularization} has attracted interest in the recent years as a fundamental aspect of the remarkable generalizing ability of neural networks. In a nutshell, it entails that gradient flow dynamics in many neural nets, even without any explicit regularizer in the loss function, converges to the solution of a regularized learning problem. However, known results attempting to theoretically explain this phenomenon focus overwhelmingly on the setting of linear neural nets, and the simplicity of the linear structure is particularly crucial to existing arguments. In this paper, we explore this problem in the context of more realistic neural networks with a general class of non-linear activation functions, and rigorously demonstrate the implicit regularization phenomenon for such networks in the setting of matrix sensing problems. This is coupled with rigorous rate guarantees that ensure exponentially fast convergence of gradient descent, complemented by matching lower bounds which stipulate that the exponential rate is the best achievable. In this vein, we contribute a network architecture called Spectral Neural Networks (\textit{abbrv.} SNN) that is particularly suitable for matrix learning problems. Conceptually, this entails coordinatizing the space of matrices by their singular values and singular vectors, as opposed to by their entries, a potentially fruitful perspective for matrix learning. We demonstrate that the SNN architecture is inherently much more amenable to theoretical analysis than vanilla neural nets and confirm its effectiveness in the context of matrix sensing, supported via both mathematical guarantees and empirical investigations. We believe that the SNN architecture has the potential to be of wide applicability in a broad class of matrix learning scenarios.

IMPLICIT REGULARIZATION VIA SPECTRAL NEURAL NETWORKS AND NON-LINEAR MATRIX SENSING
Anonymous authors Paper under double-blind review
ABSTRACT
The phenomenon of implicit regularization has attracted interest in recent years a fundamental aspect of the remarkable generalizing ability of neural networks. In a nutshell, it entails that gradient flow dynamics in many neural nets, even without any explicit regularizer the loss function, converges the solution of a regularized learning problem. However, known results attempting to theoretically explain this phenomenon focus overwheelmingly on the setting of linear neural nets, and the simplicity of the linear structure is particularly crucial to existing arguments. In this paper, we explore this problem in the context of more realistic neural networks with general class of non- non-linear activation functions, and rigorously demonstrate the implicit regularization phenomenon for such networks in the setting of matrix sensing problems. This is coupled with rigorous rate guarantees that ensure exponentially fast convergence of gradient descent, complemented by matching lower bounds which stipulate that the exponential rate is the best achievable. In this vein, we contribute network architecture called Spectral Neural Networks (abbrv. SNN) that is particularly suitable for matrix learning problems. Conceptually, this entails coordinatizing the space of matrices by their singular values and singular vectors, as opposed to by their entries, a potentially fruitful perspective for matrix learning. We demonstrate that the SNN architecture is inherently much more amenable to theoretical analysis than vanilla neural nets and confirm its effectiveness in the context of matrix sensing, supported via both mathematical guarantees and empirical investigations. We believe that the SNN architecture has the potential to be of wide applicability in broad class of matrix learning scenarios.
INTRODUCTION
longstanding pursuit of deep learning theory is to explain the astonishing ability of neural networks to generalize despite having far more learnable parameters than training data, even in the absence of any explicit regularization. An established understanding of this phenomenon is that the gradient descent algorithm induces so-called implicit regularization effect. In very general terms, implicit regularization entails that gradient flow dynamics in many neural nets, even without any explicit regularizer in the loss function, converges the solution of regularized learning problem. In sense, this creates a learning paradigm that automatically favors models characterized by "low complexity".
standard test-bed for mathematical analysis in studying implicit regularization in deep learning is the matrix sensing problem. The goal is to approximate matrix X* from set of measurement matrices AI..... Am and observations ....... 3m where y: (A,, X*). A common approach. matrix factorization, parameterizes the solution as product matrix, i.e., X ===10 UVT, and optimizes the resulting non-convex objective to fit the data. This is equivalent to training depth-2 neural network with a linear activation function.
In an attempt to explain the generalizing ability of over-parameterized neural networks, Neyshabur et al. (2014) first suggested the idea of an implicit regularization effect of the optimizer, which entails a bias towards solutions that generalize well. Gunasekar et al. (2017) investigated the possibility of an implicit regulaagulaizttioon effect of gradient descent in the context of shallow matrix factorization. In particular, they studied the standard Burer- Monteiro approach [uueer & Monteiro (2003) to matrix factorization, which may be viewed as depth-2 linear neural network. They were able

---

theoretically demonstrate implicit norm-regularization phenomenon, where a suitably initialized gradient flow dynamics approaches a solution to the nuclear-norm minimization approach to low- rank matrix recovery Recht et al. (2010), in setting where the involved measurement matrices commute with each other. They also conjectured that this latter restriction on the measurement matrices is unnecessary. This conjecture was later resolved by L et al.] (2018) in the setting where the measurement matrices satisfy a restricted isometry property. Other aspects of implicit regularization in matrix factorization problems were investigated in several follow-up papers (Neyshabur al.)
2019 Razin & Cohen 2020 T'rmmou et al., 2021 Razin et al. (021). For instance, Arora et al. (2019) showed that the implicit norm-regularization property of gradient flow, as studied by Gunasekar et al. (017), does not hold in the context of deep matrix factorization. |azin & Cohen
2017 et al.
2 example, where the gradient flow dynamies lead to an eventual blow-up of any matrix norm, while certain relaxation of rank-the so-called e-rank-is minimized in the limit. These works suggest that implicit regularization in deep networks should be interpreted through the lens of rank minimization, not norm minimization. Incidentally, Razin et al. (202T) have recently demonstrated similar phenomena in the context of tensor factorization.
(2020) constructed simple
Researchers have also studied implicit regularization in several other learning problems, including linear models (Soudry et al.) 2018 Zhao et al. 2019 Du & Hu 2019), neural networks with one or
two hidden layers (Li al. 2018 Blanc al.] 2020 Gidel et al. 2019 Kubo al., 2019 [axx et al.)
2019). Besides norm-regularizatte
several of these works demonstrate the implicit regularization
effect of gradient descent in terms of other relevant quantities such as margin (Soudry al. 2018).
the number of times the model changes its convexity (Blanc et al. 2020), linear interpolation (Kubo
al. 2019), 3 or structural bias (Gidel et 2019).
A natural use case scenario for investigating the implicit regularization phenomenon is the problem of matrix sensing. Classical works in matrix sensing and matrix factorization utilize convex relaxation approaches. i.e., minimizing the nuclear norm subject to agreement with the observations, and deriving tight sample complexity bound (Srebro & Shraibman, 2005 Candès & Recht] 2009 Recht et al. 2010 Candès & Tao 2010, Keshavan et al. 2010, Recht, (011)) Recently, many works analyze gradient descent on the matrix sensing problem. Ge et al. (2016) and [Bhojanapalli et al. (2016) show that the non-convex objectives matrix sensing and matrix completion with low- rank parameterization do not have any spurious local minima. Consequently, the gradient descent algorithm converges to the global minimum.
Despite the large body of works studying implicit regularization, most of them consider the linear setting. It remains an open question understand the behavior of gradient descent in the presence of non-linearities, which are more realistic representations of neural nets employed in practice.
In this paper, we make an initial foray into this problem, and investigate the implicit regularization phenomenon in more realistic neural networks with a general class of non-linear activation functions. We rigorously demonstrate the occurrence of an implicit regularization phenomenon in this setting for matrix sensing problems, reinforced with quantitative rate guarantees ensuring exponentially fast convergence of gradient descent to the best approximation a suitable class of matrices. Our convergence upper bounds are complemented by matching lower bounds which demonstrate the optimality of the exponential rate of convergence.
In the bigger picture, we contribute a network architecture that we refer to as the Spectral Neural Network architecture (abbrv. SNN), which is particularly suitable for matrix learning scenarios. Conceptually, this entails coordinatizing the space of matrices by their singular values and singular vectors, as opposed to by their entries. We believe that this point of view can be beneficial for tackling matrix learning problems in neural network setup. SNNs are particularly well-suited for theoretical analysis due to the spectral nature of their non- -oneinnaassies, as opposed to vanilla neural nets, while at the same time provably guaranteeing effectiveness in matrix learning problems. We also introduce much more general counterpart of the near-zero initialization that is popular in related literature, and our methods are able to handle much more robust class of initializing setups that constrained only via certain inequalities. Our theoretical contributions include a compact analytical representation of the gradient flow dynamics, accorded by the spectral nature of our network architecture. We demonstrate the efficacy of the SNN architecture through its application to the matrix sensing problem, bolstered via both theoretical guarantees and extensive empirical studies. We believe that the SNN architecture has the potential to be of wide applicability in a broad class of matrix learning problems. In particular, we believe that the SNN architecture would be natural for the study of rank (or e-rank)
2

---

minimization effect of implicit regularization in deep matrix/tensor factorization problems, especially given the fact that e-rank is essentially a spectrally defined concept.
2 PROBLEM SETUP
Let X E Rulid2 be an unknown rectangular matrix that we aim to recover. Let At,..., Am E Rdixd2 be measurement matrices, and the lahel vector y IR is generated by
1/1 (A,,X")
(1)
where (A, B) = =tr(A' (B B) denotes the Frobenius inner product. We consider the following squared loss objective
((X) = 2
(A; (3).
(2)
This setting covers problems including matrix completion (where the A,'s 's are indicator matrices), matrix sensing from linear measurements, and multi-task learning (in which the columns of X are predictors for the tasks, and A, has only one non-zero column). We are interested in the regime where m < d1 X d2, i.c., the number of measurements much less than the number of entries in X in which case is under-determined with many global minima. Therefore, merely minimizing 2 does not guarantee correct recovery or good generalization.
Following previous works, instead of working with X directly, consider non-linear factorization of as follows
K
X Σ (U
(3)
where a R. Ug E Rdi 1/8 E Bddxxd and the matrix-valued function r: Rd xd2 -> Rd: xd2 transforms matrix by applying nonlinear real-valued function 7(-) on its singular values. We focus on the wer-parameterized setting d 2 d2 2 d1, i... the factorization does not impose any rank constraints on X. Let {a1, (01...... O.K) } be the collection of the og ss Similarly, we define U and V to be the collections of Us s and V ss
2.1 GRADIENT FLOW
For each E [K]. let (t)( (1), Vt( denote the trajectories of gradient flow, where
on (0), (O), Vi are the initial conditions. Consequently, (4) = Σ Ou (O))())))))
The dynamics of gradient flow given by the following differential equations. for k [K]
0,ar Va, (()())), O,U - Vu, (((()),,), 0.V. Vv. (((()))
(4)
THE SNN ARCHITECTURE
In this work, contribute novel neural network architecture, called the Spectral Neural Network (abbrv: SNN), that is particularly suitable for matrix learning problems. At the fundamental level, the SNN architecture entails an application of non-linear activation function on matrix valued input in the spectral domain. This may be followed by linear combination of several such spectrally transformed sttrix-ttructured data.
To be precise, let us focus an elemental neuron, which manipulates single matrix-valued input X. If we have a singular value decomposition
X where Φ V are orthogonal matrices and X is the diagonal matrix of singular values of X. Let be any activation function of choice. Then the elemental neuron acts on as follows
+ (X) Vr
(5)
where ((X) is diagonal matrix with the non- non-linearity 7 applied entrywise the diagonal of X. block in the SNN architecture comprises of K 2 elemental neurons as above, taking in K matrix- valued inputs X1 X1y..., X Each input matrix X; is then individually operated upon by elemental
3

---

Anatomy
1
xX1
7
X
Oy
Xx
0x
4
X x
V x
7(Xx)
V
Spectral Neural Network Architecture
Layer
Layer
Layer
Figure I: Visualization of the anatomy an SNN block and a depth- D SNN architecture. Each SNN block takes input K matrices and outputs matrix, both the input and output matrices are of size Rd. xd2, In layer i of the SNN, there are L; blocks, which aggregate matrices from the previous layers produce L, output matrices inputs for the next layer. The number of input matrices to a block equals the number of neurons in the previous layer. For example, blocks in layer have K Lo, blocks in layer have K L1, and blocks in layer have K Li-1-
neuron, and finally, the resulting matrices aggregated linearly to produce matrix-valued output for the block. The coefficients of this linear combination are also parameters in the SNN architecture, and are to be learned during the process of training the network.
The comprehensive SNN architecture is finally obtained by combining such blocks into multiple layers of deep network, as illustrated in [
MAIN RESULTS
For the purposes of theoretical analysis, in the present article, we specialize the SNN architecture to focus on the setting of (quasi-) commuting measurement matrices A; and spectral near zero initialization: c.f. Assumptions [ beloo.. Similar settings have attracted considerable attention the literature, including the foundational works of Gunasekar et al. (2017) and and/Arora et al. (2019). Furthermore, our analysis holds under very general analytical requirements on the activation function 7; see Assumption 3 in the following.
Assumption The measurement matrices AI,..., Am share the same left and right singular vectors. Specifically, there exists two orthogonal matrices & E gd and v e igd and sequence of (rectangular) diagonal matrices AA....,AA. Am E [Rd x such that for any E [m]. we have
A, T.
Let (+) be the vector containing the singular values of A,, i.c. (+) diag(A.) (A,). Furthermore, assume that there exist real coefficients am that
(1)(1) am (m) 1.
RRctannglaar diagonal matrices arise in the singular value decomposition of rectangular matrices, Appendix D.
4

---

We let X = = diag(X"). Without loss of generality, we may also assume that o* coordinatewise non-zero. This be easily ensured by adding the rectangular identity matrix (c.f. Appendix D) cla, xd2 to X for some large enough positive number c.
X and o* be the vector containing the diagonal elements of X", i.e., a*
Eq. 6 postulates that the measurement matrices share the same (left- and right-) singular vectors. This holds if and only if the measurement matrices pair-wise quasi-commen the sense that for any i E [m²] we have
A.4] = A AT =
AA] AJA, A.
(8)
A natural class of examples of such quasi-commuting measurement matrices comes from families of commuting projections. In such a scenario Eq. / stipulates that these projections cover all the coordinate directions, which may be related conceptually to notion of the measurements being sufficiently informative. For example, in this setting, Eq. 7 would entail that the trace of X* can be directly computed on the basis of the measurements.
Eq. 7 acts as a regularity condition on the singular values of the measurement matrices. For example, it prohibits peculiar scenarios where of 0 for all i, i.., all measurement matrices have their smallest singular values, which makes it impossible to sense the smallest singular value of X from linear measurements.
Note that
=r(;; -' x*) Tr(A, x (A,, क x
(9)
where in the above we use the fact that A; = AT (since A; is diagonal) and the cyclic property of trace. We have
y4 = (A, = . -0) 00)
(10)
where the second equality is due A being diagonal.
We further define vectors (8) and three matrices B, C, and H follows
2 (k) [V]aiVV]a
B [a(1) ... [(m)]] Rddix
C BBT E gduxd xd1
H = [>(=()) (x((8)) E Rdix
Under these new notations, we can write the label vector y as BT TT
Assumption 2. (Spectral Initialization) Let & and V be the matrices containing the left and right singular vectors of the measurement matrices from Assumption [| Let G dddd is any arbitrary orthogonal matrix. We initialize X X(0) such that the following condition holds: for any k = 1...., K, we have
(a) (0) = (0G and V2 VV(O),, and (b) (x and (0) are diagonal, and
(c) Σ = 0 (Üx (0), V (0)a) af for any i= 1, 1,...,d
Assumption especially part (c) therein, may be thought of as much more generalized counterpart of the "near-zero" initialization which is widely used in the related literature (Gunasekar al. (2017); Liet 2018);; Arora et al. 2019)). A direct consequence of Assumption that at initialization, the matrix X X0) has and V as its left and right singular vectors. As we will see later, this initialization imposes a distinctive structure on the gradient flow dynamics, allowing for explicit analytical expression for the flow of each component X.
Assumption The function γ : R + R is bounded between [0, 1). and differentiable and non-decreasing R.
5

---

Assumption [ imposes regularity conditions on the non-linearity y, Common non- non- lineariitiiies that used in deep learning such as Sigmoid, ReLU or tanh satisfy the differentiability and non-decreasing conditions, while the boundedness can be achieved by truncating the outputs of these functions if necessary.
Our result provides compact representation of the gradient flow dynamics in suitable coordinates.
The derivation of this dynamics involves matrix differentials utilizing the Khatri-Rao product v X of the matrices v and & (see Eq. 21 in Appendix of the supplement).
Theorem 1. Suppose Assumptions
7 2
hold. Then the gradient flow dynamics in 4 are
0,a H HCO(00" Ho)),
0,U; T v TV,, and
0.V₂ = ( Uk.
where La E Rddxdd is a diagonal matrix whose diagonal is given by
(aa)(Lx)= = (A) = [1 1 = cu.' (2 C(a' - Ho).
(11)
Proof. (Main ideas full details in Appendix We leverage the fact that the non-linearity 7() only changes the singular values of the product matrix U&VV while keeping the singular vectors intact. Therefore, the gradient flow in preserves the left and right singular vectors. Furthermore, by Assumption 2 V has and as its left and right singular vectors at initialization, which remains the same throughout. This property also percolates to VULVT Mathematically speaking, V.vv l becomes diagonalizable by T and V, i.e.,
VUNT - t= TAA T
for some diagonal matrix Ag. turns out that A = La as given in the statement of the theorem. In view of Eq. 4 this explains the expressions for 0,U& and 0, Vg. Finally, since or is scalar, the partial derivative of E with respect to og is relatively straightforward to compute.
Li
Theorem D provides closed-form expressions for the dynamics of the individual components of X, namely Oi Ug and Vg. We want to highlight that the compact analytical expression and the simplicity of the gradient flow dynamics on the components are direct result of the spectral non-linearity. In other words, if we use the conventional element-win non-linean non-linearity commonly used in deep learning, the above dynamics will be substantially more complicated, containing several Hadamard products and becoming prohibitively harder for theoretical analysis.
As a direct corollary of Theorem the gradient flow dynamics on Ux and V are
0,ú₂ = LA VR, V.Vi L Us.
(12)
Under Assumption 2 (0) and (0) are diagonal matrices. From the gradient flow dynamics in Eq. 12 and recalling that the L3's 's diagonal, infer that 0,Ux(0) and (0) are also diagonal. Consequently, U& (t) and (t) remain diagonal for all t 2 0 since the gradient flow dynamics in Eq. 12 does not induce any change in the off-diagonal elements. Thus, (t)))V((), also remains
diagonal throughout.
consequence of the spectral initialization is that the left and right singular vectors of X(() stay constant at & and i throughout the entire gradient flow procedure. To this end, the gradient flow dynamics is completely determined by the evolution of the singular values of X (t),, i... Ha. The next result characterizes the convergence of the singular values of X (t)..
Theorem 2. Under Assumptions and 2 for any i = .....,d,, there are constants Tj, C₁ > 0 such that we have
0 o of (H)())(()), S S.e
On the other hand, we have the lower bound
10o (H(t)a(t))la 2 nt
for some constants 1); C

---

Proof. (Main ideas full details in Appendix B) By part (c) of Assumption 2 initialization, have that H (0) S. o", in which the symbol S. denotes the element-wise wise less than or equal to relation. Therefore, prove Theorem [ it is sufficient to show that (t) is increasing to a* element-wise at an exponential rate. To achieve that, we show that the evolution Ha over time can be expressed as
(H = 4 Σ o o((=" Ha)
(f x0) a000000 c(t))) + +H Ho)).
By definition, the matrix B contains the singular values of the A,'s, and therefore its entries non- negative. Consequently, since C BB", the entries of C are also non-negative. By Assumption 3 we have that 7(.) [0, 1]. thus the entries of И are non-negative. Finally, by Assumption 2 we have (0))((0) < a² entry-wise. For these reasons, each entry in ò, (Ha) is non-negative at initialization, and indeed, for each i, the quantity (Ha);; is increasing as long as (Ho:); < oj As Ha approaches o², the gradient 0, (Ha) decreases. If it so happened that Ha = o² at some finite time, then O, (Ha) would exactly equal O, which would then cause Ha a to stay constant at o² from then on.
Thus, each (Ha); is non-decreasing and bounded above by of, and therefore must converge to limit S o. If this limit was strictly smaller than or then by the above argument (Har); would be still increasing, indicating that this cannot be the case. Consequently, we may deduce that
lim (()))(()=o'. t1000
remains to show that the convergence is exponentially fast. To achieve this, we show in the detailed proof that each entry of 0 H is not only non-negative but also bounded away from O, i.e.
(Ha), 2 nooo - (Ha):):
for some constant > 0. This would imply that Ha converges to a² at an exponential rate.
The limiting matrix output by the network is, therefore, "Diag(o*)VT, and given the fact that o' = diag( < X**),, this would be the best approximation of X among matrices with (the columns of) & and V as their left and right singular vectors. This perhaps reasonable, given the fact that sensing matrices A, also share the same singular vectors, and it is natural to expect approximation that is limited by their properties. In particular, when the A, are symmetric and hence commuting, under mild lincar independence assumptions, DDiag ) would be the best approximation of X" in the algebra generated by the As-S, which is again a natural class given the nature of the measurements.
We are now ready to rigorously demonstrate the phenomenon of implicit regularization in our setting. To this end, following the gradient flow dynamics, are interested in the behavior of Xxx in the limit when time goes to infinity.
Theorem 3. Lei Xxc = lim, X().. Under Assumptions 7 and the following hold:
(a) ((xx)) and
(b) Xoc solves the optimization problem
min XER
|X|| subject to
3/4 (A,,X) Vi [m].
(13)
Proof. (Main ideas full details in Appendix C
A direct corollary of Theorem 2 is that
H H(c))a(oo) o²
By some algebraic manipulations, we show that the limit of X takes the form
X + Diag(o TT
Now, let us look at the prediction given by Noc. For any 1...., we have
(A, ( @Diag(o*) (0(0), o*) yi.
7

---

where the last equality holds due 10
This implies that xxXx))= 0, proving (a).
To prove (b), we will show that X
satisfies the Karush- Kuunn- The conditions are
Kuhh-Tucker Tucker (KKT) conditions of the
optimization problem stated in Eq. 74
EF E R s.t. E [m], (A,
and Vx +
Σ v4A, = 0. 2=1
The solution matrix X satisfies the first condition as proved in part (a). As for the second condition, note first that the gradient of the nuclear norm of X is given by
xo =
Therefore the second condition becomes
T T
=A
+ $ 8
M =0
Bv = 1. +
However, by Assumption D the vector lies in the column space of B, which implies the existence of such a vector v. This concludes the proof of part (b).
5 NUMERICAL STUDIES
In this section, we present numerical studies to complement our theoretical analysis. Additional experiments the multi-layer SNN architecture, well with relaxed assumptions, can be found in Appendix
We highlight that gradient flow can be viewed as gradient descent with an infinitesimal learning rate. Therefore, the gradient flow model only acts as good proxy to study gradient descent when the learning rate sufficiently small. Throughout our experiments, we shall consider gradient descent with varying learning rates, and demonstrate that the behavior suggested by our theory is best achieved using small learning rates.
We generate the true matrix by sampling each entry of X independently from standard Gaussian distribution, suitably normalized. For every measurement matrix A,, i 1,.... m, we sample each entry of the diagonal matrix A, from the uniform distribution on (0, 1), sort them in decreasing
order, and set A; = Φ where and V are randomly generated orthogonal matrices. We then record the measurements y; (A,, X*), = I,..., m. For every & = I,..,, K, we initialize Ü (0) and ((0 to be diagonal matrices, whose diagonal entries are sampled uniformly from (0, 10 10-3). and sorted in descending order. Similarly, aę is also sampled uniformly from (0, 10-3). We take di = d2 10 (thus X* has 100 entries), m 60 measurement matrices, and K = 3. As for the non-linearity, use the sigmoid (xx) 1/(1 ²)
In the first experiment (c.f. Fig. 2). we empirically demonstrate that the singular values of the solution matrices converge o* at an exponential rate as suggested by Theorem 2 From the leftmost plot of Fig. 2 we observe that when running gradient descent with a small learning rate, i.c., 10-4 the singular values of X converges a* exponentially fast. By visual inspection, it takes only less than 4000 iterations of gradient descent for the singular values of X to converge. As we increase the learning rate, the convergence rate slows down significantly, as demonstrated by the middle and rightmost plots of Fig. For the learning rates of 10-3 and 10-2, e it takes approximately 6000 and more than 10000 iterations respectively to converge. We re-emphasize that our theoretical results are for gradient flow, which only acts good surrogate to study gradient descent when the learning rates are infinitesimally small. As a result, our theory cannot characterize the behavior gradient descent algorithm with substantially large learning rates.
In the second experiment (c.f. Fig. B), we show the evolution of the nuclear norm over time. Interestingly, but perhaps not surprisingly, the choice of the learning rate dictates the speed of convergence. Moderate values of the learning rate seem to yield the quickest convergence to stationarity.
8

---

Ra 30.00 XUP UN 1pm
Mumber of Farnttore x307 13:300
Number tenatina kto 10
Figure 2: The evolution of X largest 3 singular values when running gradient descent the matrix sensing problem with learning rates of different magnitudes. The first 100 iterations have vastly different values and omitted for clarity of presentation.
40
LR 10
10 10" Ln x0010000 x
105
0.1. 10
15
LA 0.1 x0
10
25
19
10-1
15
10
10
Herations
Namber Berations
Figure 3: The evolution of X's training error (left panel) and nuclear norm (right panel) over time with learning rates (LR) of different magnitudes.
SUMMARY OF CONTRIBUTIONS AND FUTURE DIRECTIONS
In this work, we investigate the phenomenon of implicit regularization via gradient flow in neural networks, using the problem of matrix sensing as canonical test bed. We undertake our investigations in the more realistic scenario of non-linear activation functions, compared to the mostly linear structure that has been explored in the literature. In this endeavor, we contribute novel neural network architecture called Spectral Neural Network (SNN) that particularly well-suited for matrix learning problems. SNNs are characterized by spectral application of a non-linear activation function to matrix-vald valuud input, rather than an entrywise one. Conceptually, this entails coordinatizing the space of matrices by their singular values and singular vectors, as opposed to by their entries. We believe that this perspective has the potential to gain increasing salience in a wide array of matrix learning scenarios. SNNs are particularly well-suited for theoretical analysis due to their spectral nature of the non-linearities, as opposed to vanilla neural nets, while at the same time provably guaranteeing effectiveness matrix learning problems. We also introduce much more general counterpart of the near-zero initialization that is popular in related literature, and our methods are able to handle much more robust class of initializing setups that are constrained only via certain incqualities. Our theoretical contributions include a compact analytical representation of the gradient flow dynamics, accorded by the spectral nature our network architecture. We demonstrate rigorous proof of exponentially fast convergence of gradient descent to an approximation to the original matrix that is best in a certain class, complemented by a matching lower bound, Finally, we demonstrate the matrix-valued limit of the gradient flow dynamics achieves zero training loss and is minimizer of the matrix nuclear norm, thereby rigorously establishing the phenomenon of implicit regularization in this setting.
Our work raises several exciting possibilities for follow-up and future research. A natural direction is to extend analysis to extend our detailed analysis to the most general setting when the sensing matrices A, are non-commuting. An investigation of the dynamics in the setting of discrete time gradient descent (as opposed to continuous time gradient flow) is important question, wherein the optimal choice of the learning rate appears to be an intriguing question, especially in the context of numerical studies (c.f. Fig. 3.. Finally, it would be of great interest to develop general theory of SNNs for applications of neural network- based techniques to matrix learning problems.

---

7 REPRODUCIBILITY STATEMENT
In our paper, we dedicate substantial effort to improving the reproducibility and comprchensibilit of both our theoretical results and numerical studies. We formally state and discuss the necessity and implications of our assumptions (please see the paragraphs following each assumption) before presenting our theoretical results. We also provide proof sketches of our main theoretical results. In these sketches, we present the key ideas and high-level directions and refer the reader to more detailed and complete proofs in the Appendices. For the numerical studies, we provide details of different settings in Section 5 and Appendix E] The python code used to conduct our experiments included the supplementary material as a zip file and is also publicly available at https 7/github. htwpuu/.omm/oorccccceeee wttpaa/......ooooooooooooo////ee
neural-neeee
REFERENCES
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global optimality of local search for low rank matrix recovery. Advances in Neural Information Processing Systems, 29, 2016.
Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an onstein-ublenheck like process. In Conference on learning theory, pp. 483-513. PMLR, 2020.
Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95(2):329-357, 2003.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 96):777777 2009.
Emmanuel Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix
completion. IEEE Transactions on Information Theory, (5665):2053-2088) 2010.
Simon Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. In International Conference Machine Learning, pp. 1655-1664, PMLR, 2019.
Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. Advances in neural information processing systems, 29, 2016.
Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien. Implicit regularization of discrete gradient dynamics in linear neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, 30, 2017.
Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from a few entries. IEEE transactions on information theory, (666))2980-2999) 2010.
Masayoshi Kubo, Ryotaro Banno, Hidetaka Manabe, and Masataka Minoji. Implicit regularization in over-parameterizee neural networks. arXiv preprint arXiv: meee:i903009999 2019.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pp. 2-47, PMLR, 2018.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. arXiv preprint arXiv: |412.66144 2014.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generalization in deep learning. Advances in neural information processing systems, 30, 2017.
10

---

Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms, Advances in neural information processing systems, 33:21174-211811 2020.
Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in tensor factorization. In International Conference Machine Learning, pp. 8913-8924. PMLR, 2021.
Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12), 2011.
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-50,, 2010.
Andrew M Saxe, James L McClelland, and Surya Ganguli. A mathematical theory of semantic development in deep neural networks. Proceedings of the National Academy Sciences, 116(23): 11537-11546, 2019.
Daniel Soudry. Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018.
Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm, In International Conference Computational Learning Theory, pp. 545-560. Springer, 2005.
Salma Tarmoun, Guilherme Franca, Benjamin D Haeffele, and Rene Vidal. Understanding the dynamics of gradient flow in overparameteriiee linear models. In International Conference on Machine Learning, pp. 10153-10161. PMLR, 2021.
Peng Zhao, Yun Yang, and Qiao-Chu He. Implicit regularization via hadamard product over- parametrization in high-dimensional linear regression, arXiv preprint
2019.

---

Supplementary Material
Implicit regularization via Spectral Neural Networks and non-linear matrix sensing
A PROOF OF THEOREM
Before presenting the Proof of Theorem we define the few notations. Let A E agdixd2,er ,d, < d2 be rectangular matrix and I2dh be vector. We let Asj denote the (i.j)-entry of A, As. denote the i-th row of A, and An denote the j-th column A. We define the following functions on the matrix A.
vec: Edixds xd2 + R2
vec(A) [AM
A
(14)
diag: Rdixda xd2 - dR
diag(A) = [An
Adjd
(15)
[a
0
0
Diag: Rd + 1ddxxda
Diag(a)
(16)
ad
We are now ready present the Proof of Theorem
We first recall the definition of X in Eq. 3
K
X Σ ((UVV
where r(.) is a matrix-valued function that applies a non-linear scalar- scalar-valued function 7(-) on the matrix's singular values. Under Assumption [ we can write Un and Vx
U (&U, T G) V T ΦÜg V V. TT.
Since both Ug and V₁ are diagonal matrices, their product Ug V is also diagonal. Consequently, we can write
r(VVV (T(UVVV "
where 7(-) is applied entry-wise on the matrix V. We can now write the matrix X as
X
a 2 (U +
Σ Can((UNET) VT.
(17)
For notational convenience, define the following notations to be used throughout this section:
x (Uv(( e dg xd2 Diagonal matrix containing the singular values of X
(18)
X = diag X) E Rdd Vector containing the singular values of
(19)
X vee( X) E Rdidd The matrix X expressed as vector
(20)
θ V X + diidaxd Khatri Rao product between Vi and +
(21)
(e(X)
G = 0X
Σ
(u (A,, E dd dddxxs, xds Gradient of ((X) with respect to X
(22)
1=1
g = vec(G) dddid
The gradient expressed as a vector
(23)
2₁ = V.V. E Edixd2 Product matrix between U2 and V.T.
(24)
The Khatri-Ras product in Eq. 2 defined as follows: the columns of the matrix θ are Kronecker products of the corresponding columns of v and &. In other words, the i-th column of O can be
12

---

expressed as the vectorization of the outer product between the i-th column of & and the i-th column of V, i...
. = vec(
(25)
We shall see the next paragraph that by leveraging the Khatri-Rao product, we can write the differentials of many quantities of interest compactly, facilitating the derivation of the gradient flow dynamics in Theorem 4
Therefore, use the Khatri-Raa product to expand vec(X) as follows:
x +XV
X Knbel
(26)
di > OxO OX.
x = vec(X) = Σ X =
(27)
1=1
From here, we can write the differential of X as
dx OdX.
(28)
Since x, is the i-th singular value of the matrix X, we can express the differential of X, as follows:
dx. (dev) dx)) (bet) aw/ (2, (*) ddZn) = (au>' (2) (k) Joi dla),
(29)
where the first equality is due to Eq. and the second equality is due to ag and (x()()) being scalars. Notice that we can write the vector X as sum over its entries follow
X
X
Cj.
where e; denote the i-th canonical basis vectors of Rdi, We have
di dx, e, Σ (an' (1) )oie. dba)) e, = ax) (8)
d
e di dZx), (30)
dx
where denotes the tensor product, i.e., e; T
Rdixdi xdx d is third-order tensor. Since d7, has dimension d1 x d2, the above Frobenius product returns a vector of dimension d,, which matches that of dx. Substituting Eq. 30 this into the differential of ((X) gives
Oe dx
de(x)
(G, g dx g Odxx
0x
di
= aan' =3n (
Σ (g (o.) ).
(31)
Let us define the scalar 21 as
X - - (k)) g T
(a) -ou
(k) g TO.:
(
aun (K) T vec(orv!)
- (k) (G,
(x) (
(ug (Ag, X)) onv.
j=1
=an (K)
Σ
(34 (A,, Ag (.v.
13

---

k
(25
(k) (k())
(000 0²) - Σ
an(ol)) ((((o),><=(11))) o.
==l
1=1
(
a (1)) (1))
B 0- - B Ha o
aan' row; (B)B (o' Ha.)
where (a) is due to Oe, equals to the i-column O (b) due to Eq. 25 (c) is due to definition
of the matrix G in Eq. 22 (d) is due to Eq. 10 and (e) is due the definitions of B and H.
Let ( E Rd denote the vector containing the (k) we can write
(k) og 7 (x(()) BB (o+ Ha) = az ( - - Ha).
(32)
The differential of dd( becomes
de(X)
X Diu!! dZz).
(k)
O1(X)
d1
Σ
1 Di
(33)
07k
where (k) is diagonal matrix whose diagonal entries are X x(t), i.e, ((n) (*a)(A(*)) Since
Z V have
0((X)
X (M) p.o. - Va.
(34)
OUk
(((X)
d1
(k) \
D.0! ( T
(35)
0V,
This concludes the proof for the gradient flow dynamics on Us and Vg. In the remaining, shall derive the gradient of ((X) with respect to the scalar dg..
OE(X)
Σ(s (1s (Aj, (.)
Ooo
J=l
K Σ an(( (000) (0(0))))())))
= =- Σ
(0
1=l
1=1
((2(())TC((0
Σ an(()1))
->(()(0)) C(o - Ha),
where the second equality is due to Eq. vector a is
10 Consequently, the gradient of {(X) with respect the
a((x)
-HT - Ha),
(36)
da
which concludes the proof of Theorem
B PROOF OF THEOREM 2
Let us direct attention to the evolution of the diagonal elements. Restricting 12 to the diagonal elements gives us system of differential equations for each E [m]:
[a,0<]a -x (Vela.
[a.Volas
> (Uk]a.
(37)
14

---

We we-weite the above into single matrix differential equation
Ukle a
[ 1
U
A
(38)
[V
0
[V
For the remaining of this section, define the following notations for ease of presentation:
U K
(39)
A = 1
0
(40)
1 0
w (1)
x
(K) (K)
-2 Vi
(41)
0mm (K)
(K)T 0xx!
(42)
=
2 X
(K)T
Ax: = [Unla[Val
(43)
0,2, (1) (R)T (R)
Ad,x
(44)
The above matrix differential equation becomes
0, (k)
A
(8) (K)
Ax
T
0xx (k) X;
(B)T X (1) Ax
Ow (K) = 22 (()
(45)
On another note, we also have
01x (K) 1( (x)xx Ax(1))
(T)T
A0xx (k) 11 (R)T AAx,") (K)
0, (k) (k) w;
(46)
We now ready to prove the main result. In the remaining proof, will derive the differential equation for Ho. By the product rule of calculus, we have
d((Ha) (0,1) a (0,a.).
(47)
We shall derive a and aθ,a separately. First, let us consider the evolution of H over time.
H ... (=)( I...]
(48)
((((1))) o 2x()), (
(49)
= [-... (2(())) 20(0" Ha) o (x)) [...] Diag(a).
(50)
where the first equality follows from the definition of и and the chain rule of calculus, the second equality is due to Eq. [46] and the last equality follows from Theorem T Multiplying the vector a from the right on both sides gives:
K
(0.H)a = Σ ax (2'6(())300(0 - Ha) o (+))
(51)
1=1
Recall that from Theorem
we have
0,a = H CCO" Ha).
(52)
Multiplying the matrix H from the left on both sides gives
H(O,a)= HH C(o" Ha).
(53)
Combining Eq. 51 and Eq. 53 gives
K
(Ha) = Σ ot (2 C(la" Ha) w(()) + HH C(o" Ha).
(54)
15

---

Notice that by definition, the matrix B contains the singular values of A, ss and therefore its entries are non-negative. Consequently, since = BB C's entries are also non-negative. Finally, by definition Eq. 41 wx(k) has non-negative entries. Therefore, all quantities Eq. a4 non-negative entry-wise, except for the vectors (o" Ha). Consequently, both quantities (Or Ja and H (0,a) have the same sign as (o* - Ha). By our initialization, this sign is non-negative.
Furthermore, this non-negativity implies that
(.H))) 2 HH C(o" Ha).
(55)
O, Σ a (1(221)))oo(0 - Ha) (()))
(56)
We will have the occasion use both inequalities depending on the situation. Finally, we can also write down similar differential equation for each (Hij from Eq. 50 as
0, = / ) Ple(a Ha))
(57)
By Assumption 2. part (c), at initialization, we have (0))a((0) a* entry-wise. This implies that each entry in a (Ha) is positive at initialization, and therefore Ha is increasing in a neighborhood of O. As Ha approaches o², the gradient 0e(Ho, (Ha) decreases and reaches 0 exactly when Ha o*, which then causes Ha to stay constant from then on. Thus, we have shown that
lim H(I)((I)= =o and (.H 2 O.
(58)
1-00
Combining Eq. 46 and Eq.
45
we have
Oew! (k)
w (k)
0,2;
0.
(59)
Integrating both sides with respect to time, we have that for any f > 0
(w) (k) (t)) - (z (t) = Q.
(60)
for some constant Q which does not depend time. Since wi (k) is non-negative by definition, the above implies that w: (t) 2 Q for all t > 0; note that Q > 0 can be ensured via initialization, as discussed below. To this end, notice that
(w: (0) - (z) (0))² - (0), + (0) - (0.
(0) (0))2))
Thus this always be arranged simply by initializing (0), (0) suitably.
This, in particular, implics that w (k) is bounded away from 0 in time.
In the remainder of this section, we will show that the convergence rate is exponential. In the below, we shall establish lower bound on 0 (Ha).
Case 1: The ag are upper bounded by finite constant O'max > 0 for all & E [K] and E R..
Let h1 b1....,hy h,, denote the rows of H, and th....,bu ba, denote the rows B. We have
Hθ,a HH CCoo HHa) (HH (BBB
HHa
(61)
ho hT h2 hi hd,
bT
bTb2 b2
b báj
(0- (o"))
(62)
he hd,
hT ha,
hT, ha.
69 ba.
bj ba.
bT bu.
hT h
b bi
hT 1z2
bJ bz
(o'-Ho)
(63)
di has
6T, ba.
16

---

h1 h1 by br
h h2 by b2
(o" (H)
(64)
hd, ha, bbd bdi.
[[h h1 6, bi
hd hd. b, ba.]
o (o" Ho))
(65)
where the first inequality is due to the non-negativity of the entries of H and B. Let us focus our attention on the evolution of the i-th entry of Ha.
O,(Ha); [(,H)aa; + (dra)) 2 [H(aa))) 2 (b. hy b.))) (Ha))),
(66)
where the first inequality is due to [t)) S o7 which causes (ā,H)a; to be non-negative.
Notice that by are constants with respect to time, and are non-zero because of the condition that the all-ones vector lies in the range of B. Therefore, to show a lower bound on 0 (Ha),. it remains to show that h h; (or [[A,]]) is bounded away from O.
In the previous part, we have shown that H (t)a(tt) approaches a² as t + co. Therefore, for any >> O, there exists a time to after which loz - (Ha):l S e. Notice that (Ha); h a. By Cauchy-Schwand inequality, we have for / lo:
[+)(())] [t)l z (t)
a 2 |at| oo
10
(67)
where the second inequality is due to the Triangle inequality. Choose e e 1o071/2, we have
la-i 2|(a(t)]l
lop KyKKmax
[ha(t)]] 2
(68)
Let us define the constant 7/s - -lo Kmmx)) by bi, and = (27-(Ha), Notice that y is constant with respect to t. We have the following differential inequality:
0, = a, (Ha), S -n,
(69)
Integrating the above differential inequality we get that
Bt(t)= = of (H()) S Ce
(70)
for some constant C > 0 for all large enough This shows that Ha converges to af at an exponential rate.
Definition, In the complement of Case 1, we define the subset S C [K] such that j implies that lim;- (4) = +00
In order deal with the complement of Case above, we now proceed to handle the convergence of Ha to o* coordinate-wise. To this end, we consider two types of coordinates i E [d1]. depending on the limiting behavior of the H,y tandem with that of a, (as j ranges over S for this i).
Case 2 The index E [dı] is such that Hijaj + 0 as t + oc for all j E S. In this case, we consider the left and right sides of 54 for the i-th co-ordinate, and notice that in fact we have of = lim EjØs Hıjay. Since a, for each j $ S converges to finite real number, this implies that for this particular index E [d1] can employ the argument of Case 1, with lower dimensional vector (az)ses instead of (a5))E[K]-
The index E [d1] is such that 3j with Hıja, does not converge to zero as -> Do and H, remains bounded away from 0 for this j. In this case, we notice that the i-th row of H, denoted h,, satisfies the condition that | is bounded away from 0 as oo, thanks to the above co-ordinate j. As such, are able to apply the exponential decay argument of Case I by combining Eq (66 and Eq 169
Case 3:
Case 4: The index E [di] is such that 3j E S with Hija; does not converge to zero t + and H, + 0 for this j. For the proof of Case 4 in Theorem 2, we further assume that if xg is a zero of the activation function % then (((x) 2 (z(x) for sufficiently close to Fo, and This covers the case of To = -00, as in the case of sigmoid functions, where the condition would be taken be satisfied for sufficiently large and negative. This condition is satisfied by nearly all of
being a constant.
17

---

the activation functions of our interest, including sigmoid functions, the tanh function, and truncated ReLu with quadratic smoothing, among others. We believe that this condition a technical artifact of our proof, and endeavor to remove it in upcoming version of the manuseript.
In this setting, we invoke Eq 54 in its i-th component and lower bound its right-hand side by the k j summand therein; in other words, write
O,(Ha); 4aj''(z (ic(o" Ha))aw!
(71)
Since Hi = (22 therefore for large enough t, we have 2, is close to the zero of r (in the event 2g = 0G, this means that 2(") is large and negative). By the properties of the activation function y, this implies that the inequality /= 2 c>(2!() holds true with appropriate constant c > 0 for large enough t. Notice that a t +oo and from Eq (57) we have H,H 2 for large enough time t, which implies that Hij is non-decreasing for large time. As result, Hıja is non-decreasing for large time. But recall that Hijay does not converge to zero as - oe by the defining condition of this case, which when combined with the non-decreasing property established above, implies that Hıja is bounded away from 0 for large time. Finally, recall that w Z vlQI. Combining these observations, we may deduce from Eq 72 that, for an appropriate constants C1 C2 > 0 we have
(Ha): 2 (2) ( (
(M) 2 u
|C(o - Ha))
(72)
We now proceed as in Eg 69 and obtain exponentially fast convergence, desired.
Establishing a matching exponential lower bound on (t( is not very important from a practical point of view. So, only show such bound under the assumption that the (1) remains bounded by some constant Ommxx > 0, for all For simplicity, we also assume that the non-linearity y is such that (())) O Viøi + toc. (This mild assumption, satisfied, e.g., by the logistic or the
(k)
can grow at most linearly 2, (see Eq. (60 ) this assumption ensures that (2 remains bounded uniformly for all and k. Further, the entries of H uniformly bounded, and C' is fixed matrix. Therefore, for some constant Ç >> O, we have, for all i [d1], that
tanh non- non-linearities.) Since w.;
0, (Ha),
Σ ( (2(1) (C(o" Ha), + k=1
> (HH (iy(o' - Ha));
00 Haae.
fortiori,
0. Σ Bi Σ 0.Bi = Σ (HH))
-
2 2- 3e
= Σ Bz.
Integrating this differential inequality, we conclude that for some constant C₁ > 0,
Σ 3,(1) Ge
for all / >> 0. The Cauchy-Schward bound E.8(1 S vdll) then implies that for all / 0,
||o" H(t)a(t)]l+ [|8())]22 ||8()] Ci
dist nt
ddi
where C= CL and diç. This completes the proof of the lower bound. Vdi
18

---

C PROOF OF THEOREM 3
By our definition of X we have
X
lim (()
10000
lim
(=((T(UV(())1))))))
(-+00
1=1
lim
lim
((1
(-+00
lim
ar (0(())1( TT
1-+00
lim
a0(0(((+())( v
K
lim Diag +-c
on (1 k=
T
lim Diag ((())(()) TT 600
+
Diag
lim H(t)a(tt) T
+
Diag
where the fourth equality is due to the orthogonality of G, and the last equality is due to Theorem Now, let look the prediction given by Xoc. for any 1,..., m,, have
Xox) ( "Diag(o")ur = (0
yis
(73)
where the last equality is due to Equation This implies that ((Xxo) proving (a).
To prove (b), we will show that X satisfies the Karush-Kuhn- KuckeTukkerr (KKT) conditions of the following optimization problem
min XEX41x4;
|X||. subject to Di =Ai, X), Vi E [m].
(74)
The KKT optimality conditions for the optimization in 74 are
EV E Rm s.t. Vi [m], X)
y and Vx|| + Σ v4 = 0.
(75)
The solution matrix X satisfies the first condition from the first claim of Theorem it remains to prove that X also satisfies the second condition. The gradient of the nuclear norm of X given by
X
= T
(76)
Therefore, the second condition becomes
v; = 0
i=1
U.A.A. A,
19

---

Φ T- 2 U:A.) v/
1, Aj E [di
BV=1
By Assumption T the vector 1 lies in the column space of B, which implies the existence of a vector v that satisfies the condition above. This proves (b) and concludes the proof of Theorem
D SINGULAR VALUE DECOMPOSITION
In this appendix, we explain in detail the singular value decomposition of rectangular matrix. By doing we also explain some of the non-standard notations used in the paper (e.g., rectangular diagonal matrix).
In our paper, we consider a rectangular measurement matrix A of dimension di x d2 and rank Without loss of generality, we assume that r I d1 S d2. Then the singular value decomposition of the matrix A is given by
A = TAv
(77)
where & E IRd1xd1, E Rdaxxd are two orthogonal matrices whose columns represent the left and right singular vectors of A, and A Rdixd is diagonal matrix whose diagonal entries represent the singular values of A.
This is similar the notion of compact SVD commonly used in the literature, but truncate the matrix V to di columns, instead of r columns like in compact SVD.
This choice of compact SVD is taken lightly, it is crucial for the proof of Theorem via the use of the Khatri-Rao product. More specifically, the Khatri-Rao product in Eq. requires that & and v/ have the same number of columns. This is generally not true in the standard singular value decomposition.
Next, precisely define the notion of rectangular diagonal matrix. Suppose A E Rdh xd2 with dj < dg is diagonal matrix, then A takes the following form:
a1
A
(78)
a.
Here, we start with a standard square diagonal matrix of size dj x dj. and add d2 - d2 columns of all 0''s to the right of that matrix. Similarly, define rectangular identity matrix of size dj d2 by setting d1 ad, 1.
E ADDITIONAL NUMERICAL STUDIES
In this section, we complement the numerical studies in the main paper with some simulation results on the SNN architecture of Fig. [
We empirically demonstrate that gradient descent dynamics SNN minimizes the nuclear norm of the solution matrix, and leads to favorable generalization performance. We also investigate some settings in which the assumptions made in our theoretical study are relaxed.
Do the results in Theorem and Theorem 3 extend to multi-layer SNN?
We generate the true matrix by sampling each entry of X independently from a standard Gaussian distribution, suitably normalized. For every measurement matrix A,, 1,..., we sample each entry of the diagonal matrix A, from the uniform distribution on (0. 1). sort them in decreasing order, and set A, & y where &b and v randomly generated orthogonal matrices. We then record the measurements y; = (A,X**) half of them are used for training and the other half are used for testing (m 60 in this case).
X*), i 1..... m. A total of 120 measurement matrices are generated,
20

---

We use two-layer SNN of size [5,3, i..., the input layer has 5 blocks, the hidden layer has 3 blocks, and the output layer has block. These blocks are initialized with spectral initialization (see Assumption 2
We take d1 = d2 (thus X has 100 entries), m = 60 mcasurement matrices, and K = 3. As the shifted and scaled sigmoid
for the non-linearity,
(()) 1+e
0.8.
(79)
In the figures below, we demonstrate the evolution of the nuclear norm, the train error, and the test етrо of our SNN over time as we run gradient descent. Even though we only analyze gradient flow dynamics for single block in our theoretical investigation, the empirical results suggest that the same phenomenon extends to more general multi-layer SNN.
Nucker Nom (log scale]
4.5
Train Love (og scare)
Teat Lose Day scalel
0-
4.5-
4.4
-15
-16
-20
-20
100000
200000
100000
Iterations
llerations
Heratione
-6- x 10
1 10
-5- 20
1x10
-4--5 x0100
Figure 4: The evolution of SNN's nuclear norm, train error, and test error over time with learning rates (LR) of different magnitudes. In the left plot, the nuclear norm decays time and converges to the same minimum value regardless of the learning rates.
Nublea Norm lloe soalo)
Train Loss log sean)
Test Loos tog soste)
good dopo Strepge
100000
200000
100000
200000
100000
200000
Blraainn
Ierations
Barations
1-block -B- J-bayer - 2-byer -<-. 3-ayer
Figure 5: The evolution SNN's nuclear norm, train error, and test eтrоr over time with various SNN architectures. We learning rate of 10-5, The left plot shows that gradient descent minimizes the nuclear norm of the solution matrix for all architectures, although they converge to slightly different final solutions. In the right plot, we observe that there substantial difference in the test error between different architectures. In this particular simulation, a 2-layer SNN achieves the lowest test error. This hints at the ad adnattage of going beyond a single block multi-layer SNN architecture as we proposed in Section
Do the results Theorem 2 and Theorem still hold when we relax the assumptions?
We investigate scenario in which Assumption (commuting measurement matrices) and Assumption 2 (spectral initialization) are relaxed.
We generate the true matrix by sampling each entry of X independently from standard Gaussian distribution, suitably normalized. For every measurement matrix A,, 1, m, we sample each entry of A, from standard Gaussian distribution. We then record the measurements y: = (A, X*). i 1..... m. A total of 120 measurement matrices are generated, half of them are used for training and the other half are used for testing (m 60 in this case).
21

---

In this setting, still observe that the nuclear generally decreases time, although not in strict sense like before. We again observe that there are advantages in going from a single block to multi-layer SNN from the generalization perspective.
Nudear Norm (og soako)
Test Lase (leg scare)
2.57
-10
-10
2.55
Train
-16
-15-
100000
200000
100000
200000
100000
200000
nonations
Figure 6: The evolution of SNN's nuclear norm, train error, and error over time with learning rates (LR) of different magnitudes. From the left plot, the nuclear norm generally decreases over time and converges to the same value albeit with some erratic movements the early iterations.
Nuckear Norm (oa scale)
Train Loss (og soale)
Ted Lowe Dlog posel))
-10
-15
-15
100000
200000
100000
200000
100000
200000
Baratona
Boralions
Iarraonns
3-block
1-kayrr -6-
layor
3-layr
Figure 7: The evolution of SNN's nuclear norm, train error, and test error over time with various numbers of layers. We use a learning of 10-5 In the middle and right plots, it shows that the single-block 1-layer SNN the easiest to optimize but does not result in the best generalization performance: the error decreases quickly first, but then plateaus; the other hand, for the more complex SNNs, the loss improves slowly but reaches better solutions.
F
CODE AVAILABILITY
The python code used to conduct experiments is publicly available athttps://qttub.co porichoy-guuto/speett -ww.eeeeaaaeeeee -nets
22


Reviews:
[{"review_id": "khACaBV17F", "reviewer": "Reviewer_xZxU", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 proposes spectral neural networks (SNNs), an architecture that applies the nonlinear activation function to the singular values of a matrix, to demonstrate the role of implicit regularization in deep learning. Section 3 introduces the SNN architecture, and then Section 4 presents Theorem 3 suggesting that under the assumptions made the SNN training will converge to the nuclear-norm minimzing solution, indicating the implicit regularization of the gradient flow. A few numerical results are discussed in Section 5 to support SNNs and the implicit regularization in training them via gradient descent.", "summary_of_the_review": "This paper proposes a novel neural network architecture for matrix learning problems. The paper contributes several nice ideas; however, it can still be improved by including additional numerical results and some explanation of the role and necessity of the assumptions in section 4.", "strength_and_weaknesses": "Strengths:\n\n1) The paper proposes a novel neural network architecture (Spectral neural networks) for matrix learning problems.\n\n2) The paper is well-written, and the theoretical discussion clearly states the assumptions and theorems. \n\nWeaknesses:\n\n1) The assumptions in section 4 look too strong to me. Especially the assumptions that the neural network and measurement matrices share the same left and right singular vectors seem restrictive to me. I recommend the authors include more explanation on the role of these assumptions in the theoretical analysis.\n\n2) While I understand this is a theoretical work, the numerical results look preliminary. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "hH_Ai_oyTUJ", "reviewer": "Reviewer_yAZt", "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 focuses on the implicit regularization phenomenon in neural network with gradient descent. Different from the previous work, the authors works on the more general neural nets with non-linear activation functions. In particular, the authors demonstrated the implicit regularization phenomenon with non-linear activation function for matrix sensing problem. A new neural network structure called spectral neural network is proposed for solving the matrix learning problem. Both theoretical analysis and empirical evaluations are reported to support the proposed solution.", "summary_of_the_review": "This paper focuses on a really interesting topic and proposed the first analysis of the implicit regularization for neural network with non-linear activation function (for matrix sensing problem). The proposed SNN structure is well suited for the matrix sensing problem and the corresponding theoretical analysis supports the claims. Empirical evaluations also demonstrates the effectiveness of the proposed solution. Overall, this paper has high quality and I would recommend accept the paper.", "strength_and_weaknesses": "This paper focuses on an interesting topic of the implicit regularization for neural network with non-linear activation functions. It should attract a lot of attention from the community. The paper is well-written and well-organized, every concept is well explained and easy to follow. I feel really pleasure reading the paper. To analyze the implication regularization for matrix sensing problem, the authors proposed the spectral neural network architecture. Such structure incorporate the singular values and singular vectors of the matrix, instead of the entries, which is quite interesting. Besides, the following theoretical analysis and empirical evaluation support the claims and shows the effectiveness of the proposed solution.\n\nOverall, this paper is good. I have some minor suggestions and questions. \nFirst, for the matrix sensing problem this paper focuses on, is there any assumption on the matrix X*, e.g., low rank matrix? I didn't see any claims in the problem setting section (correct me if I am wrong).\nThe illustration of the SNN structure is a little bit confusing. For example, is every blue rectangular in the SNN corresponding to the block, or it is just one row of the block? I would suggest the authors to provide more details of the figure to help readers better understand the structure. Besides, what is the relation between the K in the block and the L in the SNN structure? How to choose the value of K and L in experiments, are they related to the property of the matrix?\nMinor: the size of the font could be enlarged in the result figures, e.g. ,Figure 3", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "g4JMLAv3cGJ", "reviewer": "Reviewer_p8b1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 proposes a nonlinear neural network (SNN) to solve the matrix sensing problem, and show that the gradient flow on SNN leads to a minimum nuclear norm solution to the matrix sensing problem.", "summary_of_the_review": "While this paper proposes a nonlinear neural network to study the implicit regularization in matrix sensing problem, it suffers from multiple major technical drawbacks and unrealistic assumption. Due to the above major concerns, I recommend rejection.", "strength_and_weaknesses": "Strength: this paper tries to use a nonlinear neural network to solve the matrix sensing problem.\n\nWeakness: There are several major concerns and technical drawbacks of this paper.\n\n1. Unclear motivation and contribution: previous works [Gunasekar et al. (2017) and Arora et al. (2019)] already showed that gradient flow by linear neural network achieves the minimum nuclear norm solution, this paper proposes a computationally expensive nonlinear neural network which leads to the same minimum nuclear norm solution (however, under very unrealistic assumption, see below). It is not clear what is the theoretical contribution or insight provided by this paper. \n\nThis paper presented a very vague description regarding the contribution, \"Despite the large body of works studying implicit regularization, most of them consider the linear setting. It remains an open question to understand the behavior of gradient descent in the presence of\nnon-linearities...\"\n\nAs stated above, one studies nonlinear neural network in the hope of brining theoretical benefits to the matrix sensing problem (or its implicit regularization property, that is, the minimum nuclear norm solution). However, this paper fails to provide any such benefit.\n\n2. Unrealistic assumption: the main result of this paper relies on a key Assumption 2: note that one needs to access the information of the oracle (in terms of $\\sigma^*$ obtained from $X^*$) in condition (c) of assumption 2, which is very unrealistic both theoretically and empirically. \n\n3. Expensive computation: the feed-forward of the proposed network requires SVD on the input (see eq. (5)), and condition (a) in Assumption (2) is achieved by performing SVD of the sensing matrices, which are all computationally expensive, and in strong intransitive to existing works [Gunasekar et al. (2017), Arora et al. (2019), Li et al. (2018)].", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "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": "8YZY2ix2gOM", "reviewer": "Reviewer_Ajzu", "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": "This paper proposed a novel Spectral Neural Network for matrix learning problems. Some theoretical results are proven to show the effectiveness of SNN in matrix sensing. Several numerical experiments show the convergence of the matrix singular values.", "summary_of_the_review": "This paper proposed a novel SNN architecture for matrix learning problems. More numerical experiments are required to show the effectiveness of SNN.", "strength_and_weaknesses": "Strength:\n1. The target problem is interesting. \n2. This paper proposed a novel SNN architecture.\n3. Both theoretical and numerical results are given to demonstrate the effectiveness of the proposed methods.\n\nWeakness:\n1. It would be better to present more details of the target problem and proposed architecture in the introduction and discuss a few more related works.\n2. There are many parameters in SNN. It would be better to present more numerical experiments to study the sensitivity of SNN.\n3. It would be interesting to perform SNN on some classical problems, such as matrix completion.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject