Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensing
Authors: Ziye Ma
Javad Lavaei
Somayeh Sojoudi
Venue: NeurIPS 2023 poster (2023)
Keywords: non-convex optimization
low-rank matrix optimization
matrix sensing
implicit bias
tensor
over-parametrization
TL;DR: Our work proves that optimizing over the tensor space with gradient descent can also induce implicit bias, making over-parameterized models tractable to use.

Abstract: Gradient descent (GD) is crucial for generalization in machine learning models, as it induces implicit regularization, promoting compact representations. In this work, we examine the role of GD in inducing implicit regularization for tensor optimization, particularly within the context of the lifted matrix sensing framework. This framework has been recently proposed to address the non-convex matrix sensing problem by transforming spurious solutions into strict saddles when optimizing over symmetric, rank-1 tensors. We show that, with sufficiently small initialization scale, GD applied to this lifted problem results in approximate rank-1 tensors and critical points with escape directions. Our findings underscore the significance of the tensor parametrization of matrix sensing, in combination with first-order methods, in achieving global optimality in such problems.

Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensing
Ziye Ma Department of EECS
Javad Lavaei Department of IEOR UC Berkeley Lavae@bbereeles edu
Somayeh Sojoudi Department of EECS, ME
UC Berkeley ziyema@berkelly..o .du
UC Berkeley jojoudi@bekkelle edu
Abstract
Gradient descent (GD) is crucial for generalization in machine learning models, it induces implicit regularization, promoting compact representations. this work, we examine the role of GD in inducing implicit regularization for tensor optimiza- tion, particularly within the context the lifted matrix sensing framework. This framework has been recently proposed to address the non-convex matrix sensing problem by transforming spurious solutions into strict saddles when optimizing symmetrie, rank-1 I tensors. We show that, with sufficiently small initialization scale, GD applied to this lifted problem results in approximate rank-1 tensors and critical points with escape directions. Our findings underscore the significance the tensor parametrization of matrix sensing, in combination with first-order methods, in achieving global optimality in such problems.
Introduction
This paper dedicated addressing the non-convex problem matrix sensing, which has numerous practical applications and is rich in theoretical implications. Its canonical form can be written as:
find M E MER
(1)
s.t. A(M) A(M") rank(M) M
A(-): R" + R a linear operating consisting of m sensing matrices {A E 1 where A(M) = M) M)...., (Am. M)]". The sensing matrices and the measurements given, while M is an unknown low-rank matrix to be recovered from the measurements. The true rank M is bounded by r, usually much smaller than the problem size n. More importantly, since A is linear, one can replace A; with (A; + 4/)/2 without changing b, and therefore all sensing matrices can be assumed be symmetric.
A(M*) are
The aforementioned problem serves as an extension of both compressed sensing [ which is widely applied in the field of medical imaging, and matrix completion notable applications 4 Additionally, this problem emerges in variety of real-world situations such motion detection [8], and power system state estimation
which possesses an array of
IC recent study by [1] established that any polynomial optimization problem can be converted into series of problems following the structure of ( thereby underscoring the significance of investigating this specific non-convex formulation. Within the realm of contemporary machine learning, 1 holds relevance as is equivalent to the training problem for a two-layer neural network with quadratic activations [12] In this context, m denotes the number of training samples, r is the size of the hidden layer, and the sensing matrices A, J. are rank-1, with x; representing the ith datapoint.
as phase retrieval
To solve ①. an increasingly popular approach is the Burer-Monteiro (BM) factorization [3, in
which the low-rank matrix M is factorized into M X with X E gaxr thereby omitting the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

constraint, making it amenable to simple first-order methods such as gradient descent (GD), while scaling with O(nr) instead of (n²)). The formulation can be formally stated as follows:
1 -
min f(X) = 21===11Axx] - 61]2 = 2 11AAXXXX - )1? (Unlifted Problem) XER
(2)
with Z E R being any ground truth representation such that M ===77" Since 2 is a non- convex problem, it can have spurious local minima making it difficult recover M general. The pivotal concept in solving 1 and 2 to optimality is the notion of Restricted Isometry Property (RIP), which measures the proximity between [|A(M)) and || 1/ for all low-rank matrices M. This proximity is captured by a constant 6p. where 6p = O means A(M) = M for matrices up to rank p, leading exact isometry case, and ön - 1 implying a problematic scenario in which the proximity error is large. For a precise definition, please refer to Appendix A.3
Conventional wisdom suggests that there is sharp bound on the RIP constant that controls the recoverability of M with 1/2 being the bound for 2 14 151 prove that if و2r < 1/2, then all local minimizers are glohal minimizers, and conversely if 82. 2 1/2, counterexamples can be easily established. Similar bounds of 1 1/3 are also derived for general objectives [6 17. demonstrating the importance of the notion of RIP. However, more recent studies reveal that the technique of over-paramettization (by using X E IR instead, with Tsearch > r) can take the sharp RIP bound to higher values |S 19 Recently, it has also been shown that using a semidefinite programming (SDP) formulation (convex relaxation) can lead to guaranteed recovery with a larger RIP bound that approaches 1 in the transition to the high-rank regime when n 2r 20 These works all show the efficacy of over-vvrveet parametrization, shedding light on a powerful way to find the global solution of complex non-convex problems. However, all of these techniques fail to handle real-world cases with 62, + 1 in the low-rank regime. To this end, a recent work [21] drew on important concepts from the celebrated Lasserre's Hierarchy (22 and proposed a lifted framework based on tensor optimization that could convert spurious local minimizers of ( into strict saddle points in the lifted space, for arbitrary RIP constants in the r case. We state this lifted problem below:
min WERN
[I @1
w 00 w)
1|
(Lifted Problem, r r=
(3)
where is an I-way, n-dimensional tensor, and A @l and j89 are tensors "lifted" from A and 6 via tensor outer product. We defer the precise definition of tensors and their products to Section 2 The main theorem of 221 states that when r = 1, for some appropriate 1, the first-order points (FOP) of @ will be converted to FOPs of (3) via lifting, and that spurious second order points (SOP) of will be converted into strict saddles, under some technical conditions, provided that w is symmetric, and rank-1. This rank-1 constraint on the decision variable w is non-trivial, since finding the dominant rank-1 component of symmetric tensors is itself a non-convex problem in general, and requires a This does not even account for the difficulties of maintaining the symmetric properties of tensors, which also has no natural guarantees. Therefore, although this lifted formulation may be promising in the pursuit of global minimum, there are still major questions to be answered. Most importantly, it is desirable to know whether the symmetric, rank-1 condition is necessary, and so. how to achieve it without explicit constraints?
number of assumptions for it to be provably correct [2 24
The necessity of the condition in question can be better understood through insights from (25). The authors argue that over- wver-parametrizin non-convex optimization problems can reshape the optimization landscape, with the effect being largely independent of the cost function and primarily determined by the parametrization. This notion is consistent with [21]. which contends that over parametrizing vectors into tensors can transform spurious local solutions into strict saddles. However, [25 specifi- cally examines the parametrization from vectors/matrices to tensors, concluding that stationary points are not generally preserved under tensor parametrization, contradicting (21. This implies that the symmetric, rank-1 constraints required in 3 are crucial for the conversion of spurious points.
It is essential to devise a method to encourage tensors to be near rank- with implicit regularization as potential solution. There has been a recent surge in examining the implicit regularization effects in first-order optimization methods, such as gradient descent (GD) and stochastic gradient descent
(SGD) (26). which has been well-studied in matrix sensing settings 227-2g 12]. This intriguing observation has prompted us to explore the possible presence of similar implicit regularization in tensor spaces. Our findings indicate that when applying GD to the tensor optimization problem
A spurious point satisfies first-order and recond-order necessary conditions but is not global minimum.

---

B. an implicit bias can be detected with sufficiently small initialization points. This finding does not directly extend from its matrix counterparts due to the intricate structures of tensors, resulting in a scarcity of useful identities and well-defined concepts for even fundamental properties such as eigenvalues. Furthermore, we show that when initialized at a symmetric tensor, the entire GI) trajectory remains symmetric, completing the requirements.
In this paper, we demonstrate that over-parametrization alone does not inherently simplify non-convex problems. However, employing a suitable optimization algorithm offers a remarkably straightfor- ward solution, as this specific algorithm implicitly constrains our search to occur within a compact representation of the weerpaaametrried space without necessitating manual embeddings or transfor- mations. This insight further encourages the investigation of a (parametrization, algorithm) pair for solving non-convex problems, thereby enhancing our understanding of achieving global optimality in non-convex problems.
1.1 Related Works
Over-paramettrizatio in matrix sensing. Except for the lifting formulation ( there two mainstream approaches to over- wer-parametrizztionn in matrix sensing. The first one is done via searching over Y Ra instead of X E R"xr, and using some distance metric to minimize the distance between T) and 6. Using an l2 norm, 18 I9 established that if T wearch > r[(1 + 6,)/(1 6.) 1/2/4, with S T'earch < n., then every second-order point Ý E ReXrsmm satisfies that Y M 30) showed that even in the peee-paraettrized regime, noise can only finitely influence the optimization landscape. [29] offered similar results for an l loss under good enough RIP constant. Another popular approach to over-paramerization is to use a convex SDP formulation,
which is a convex relaxation of ① B1. It has been known for years that as long as 62r < 1/2, then the global optimality of the SDP formulation correspond the ground truth M
32 Recently 20
updated this bound to 2r/ nn + (n - 221 5)), which can approach 1 if n = 2r.
Algorithm regularization in over-parametrized matrix sensing. gence to global solution via GD is agnostic of Tearch, in that it only depends on initialization scale, step-size, and RIP property. 29 demonstrates the same effect for an l norm, and further showed that a small initialization nullifies the effect of over wver-parametrization. Besides these works,
12 +
prove that the conver-
[27] refined
this analysis, showing that via sufficiently small initialization, the GD trajectory will make the solution implicitly penalize towards rank-r matrices after small number of steps. (28) took it even further by showing that the GD trajectory will first make the matrix rank-1, rank-2, all the way to rank-r, in sequential way, thereby resembling incremental learning.
Implicit bias in tensor learning. The line of work [34 36] demonstrates that for class of tensor factorization problems, as long as the initialization scale is small, the learned tensor via GD will be approximately rank-1 after an appropriate number of steps. Our paper differs from this line of work in three meaningful ways: 1) The problem considered in those works are optimization problems over vectors, not tensors, and therefore the goal is to learn the structure of known tensor, rather than learning a tensor itself; 2) Our proof relies directly on tensor algebra instead of adopting a dynamical systems perspective, providing deeper insights into tensor training dynamics while dispensing with the impractical assumption of an infinitesimal step-size.
1.2 Main Contributions
1. We demonstrate that, beyond vector and matrix learning problems, optimization of differ- entiable objectives, such as the l2 norm, through Gradient Descent (GD) can encourage a more compact representation for tensors as decision variables. This results in tensors being approximately rank-1 after number of gradient steps. To achieve this, we employ an innovative proof technique grounded in tensor algebra and introduce a novel tensor eigenvalue concept, the variational eigenvalue (v-eigenvalue), which may hold independent significance due to its ease of use in optimization contexts.
2. We show that if tensor is a first-order point of the lifted objective 3 and is approximately rank-1, 1, then its rank- component can be mapped to an FOP of 2 implying that all FOPs of (3) lie in a small sphere around the lifted FOPs of @ Furthermore, these FOPs possess an escape direction when reasonably distant from the ground truth solution, irrespective of the Restricted Isometry Property (RIP) constants.
3

---

3. We present novel lifted framework that optimizes over symmetric tensors to accommodate the peraaaaraettiiatioonn of matrix sensing problems with arbitrary r. This approach is necessary because directly extending the work of [2]] from = to higher values may lead to non-cubical and, consequently, non-symmetric tensors.
Preliminaries
Please refer Appendix A and A.2 for the notations and definitions of first-order and second-order conditions. Here, we introduce two concepts that are critical in understanding our main results.
Definition (Tensors and Products). We define an 1-way tensor as:
( [1 S i S nua 1 S k S E R X
74. then we call this tensor an (-order (or l-way), n-dimensional tensor. R an abbreviated notion for n o == n X ... X π.. In this work, tensors are denoted with bold letters unless specified otherwise. The tensor outer product, denoted as 8, of tensors and b, respectively of orders and p. is tensor of order 1 + p. namely = @ with Ch.---hhh---p = ai...... 0,. We also use the shorthand a for repeated outer product of times for arbitrary tensor/matrix/veer a. (a. b) b....d. denotes tensor inner product along dimensions i1,.... .......... id (with respect to the first tensor), in which we simply sum over the specified dimensions after the outer product a @ b is calculated. This means that the inner product is of + p 2d orders. Please refer to Appendix A.3 for more in-depth review on tensors, especially on its symmetry and rank.
Moreover, n1
Definition 2 (Restricted Strong Smoothness (RSS) and Restricted Strong Convexity (RSC)), The linear operator A Rexn T satisfies the (Is --RSS property and the (as,, r)RCCC property if
L, | N
f(M) f(N) S (M - N, vf())) +
2
+ 0t& |M NIE
S(M) S(N) 2 (M - N, VS(N))
2
satisfied, respectively for all M, R with rank(M rank(N) Note that RSS and RSC provide a more expressible way to represent the RIP property, with 8, = (L. az)/ + a.).
The Lifted Formulation for General r
natural extension of B general requires that instead of optimizing X Raxr, optimize over Rinxrjol tensors, and simply making tensor outer products between to be inner products. However, such a tensor space is non-cubical, and subsequently not symmetric. This the higher-dimensional analogy of non-square matrices, which lacks number of desirable properties, as per the matrix scenario. In particular, it is necessary for our approach to optimize over a cubical, symmetric tensor space since in the next section we prove that there exists an implicit bias of the gradient descent algorithm under that setting.
In order to do so, we simply vectorize X E RRrr into vec(X) E """,, and optimize over the tensor space of Igrr which again is a cubical space. In order to convert a tensor w E Brrr back to R[axrjol to use a meaningful objective, we introduce a new 3-way permutation tensor P E Ruxrxer that "unstacks" vectorized matrices. Specifically,
(P, vcc(X))s = X VX e ReXr n,, Z
Such P can be easily constructed via filling appropriate scalar "1"s 's in the tensor. Via Lemma A.4 we also know that
p vec(X) 04 33.[ = ((P, vec(X)) X
(4)
where [4] denotes the integer set [l.... 4], and c [4] denotes [c. 2c,..., .....,,, c* for some E ž For notational convenience, we abbreviate (p@) w)s- as P(w) for any arbitrary z-dimensional tensor
where be broken down into the product of positive integers. Thus, using 4 we can extend 3 to problem of general r. yet still defined over a cubical tensor space:
min w
KA 81 (P(w), P P(w))2..)) - 6
(Lifted formulation, general r)
(5)

---

Let us define 3-way tensor A E Rm so that Aki = -AAeis Ak E [m], (i.j) E [n]] x [r]] Defin f') Beno2 + I and n²()) Riaxroo + R as (MM = [| 0i M) - 10 and
h'(w) = f' ((w, w)2- with vf(()) (+) and Vwh))
We prove that 5 has all the good properties detailed in 211 for 3 In particular, we prove that the symmetric, rank-1 FOPs of $ have a one-to-one correspondence with those of @ and that those FOPs that are reasonably separated from M or have small ndh singular value can be converted to strict saddle points via some level of lifting. For the detailed theorems and proofs, please refer to Appendix B
4 Implicit Bias of Gradient Descent in Tensor Space
In this section, we study why and how applying gradient descent to 5 will result in an implicit bias towards to rank-1 tensors. Prior to presenting the proofs, shall elucidate the primary intuition behind how GD contributes to the implicit regularization of ( This will aid in comprehending the impact of implicit bias on ( as they share several crucial observations, albeit encountering greater technical hurdles. Consider the first gradient step of 2 initialized at random point Xo waath =eX with || and Tsearch Z r:
X1 -o - (Xx)) =
)]) X - A(Xx((X)X) Xo =T A X; -
AA Xo
=(++ [[+T[["AAA"")) Xo xx
where 1) the step-size. Therefore, if chosen be small enough, we have that
X (1 A(M")
as e e 0
Again, according to the symmetric assumptions on A. we can apply spectral theorem on A' **A(MM) = Diz daaiy for which the eigenvectors are orthogonal to each other. It follows that X2 = +1+
Xu-
In many papers surveyed above on making argument of implicit bias, it is assumedd that there is very strong geometric uniformity, or under the context of this paper, it means that La/a, R 1. Under this assumption, we have f(M) R f(NN (M N, V ((M)) + M N N| leading to the fact that V2 V²f(M)= A x T. This immediately gives us A A( M*)** s M so that Art1, Xn R 0 as M is by assumption a rank-r matrix. This further implies that X, R (Ei, (1 + [u,,] Xp. which will become rank-r matrix, achieving the effect of implicit regularization, X is now wver-parametrized by having Tseach 2 r.
However, when tackling the implicit regularization problem in tensor space, one key deviation from the aforementioned procedure is that L./ax,, will be relatively large, as otherwise there will be no spurious solutions, even in the noisy case [14] 50), which is also the motivation for using a lifted M we aim to show that
framework in the first place. Therefore, instead of saying that A A'A(AMM *(M*)) the gap between the cigenvalues of comparable tensor term will enlarge we increase I, making the tensor predominantly rank- 1. This observation demonstrates the power of the lifting technique, while at the same time eliminates the critical dependence on small L,/a, factor that is in practice often unachievable due to requiring sample numbers m in the asymptotic regime [
Therefore, in order to establish an implicit regularization result for 5 there are four major steps that need to be taken:
1. Proving that a point on the GD trajectory w, admits a certain breakdown in the form W, (Ze, wo) E, for some Z, and E,.
2. Proving that the spectral norm (equivalence of largest singular value) of E, is small (scales with initialization scale c)
3. Proving that (Ze, wo) has large separation between its largest and second largest eigenval- ues using a tensor version of Weyl's inequality.
4. Showing that, with the above holding true, w, is predominantly rank-1 after some step f..
Lemmas and Theorem T correspond the above four steps, respectively. The reader referred to the lemmas and theorem for more details.
5

---

4.1 A Primer on Tensor Algebra and Maintaining Symmetric Property
We start with the spectral norm of tensors, which resembles the operator norm of matrices 33 Definition 3. Given a cubic tensor E 1Radl, its spectral norm || lls is defined respectively as:
|wlls = sup {l(w, ) Jull = 1, E R=
There are many definitions for tensor eigenvalues 13 and in this paper we introduce novel variational characterization of eigenvalues that resembles the Courant-Fisher minimax definition for eigenvalues of matrices, called the v-Figenvalue. We denote the jt v-Figenvalue of X (w). Note this is new definition that first introduced in this paper and might be of independent interest outside of the current scope.
Definition 4 (Variational Eigenvalue of Tensors). For a given tensor w E Rool, we define its Ath
variational eigenvalue (v-Eigenvalue) (w()) as
(w, u)| |u|
X[(w)= = max
min
E [n]]
uEs
dim(S)=
where S' is subspace of Roo that is spanned by a set of orthogonal, symmetric, rank-1 tensors. Its dimension denotes the number of orthogonal tensors that span this space. It is apparent from the definition that [w|ls- = (w)
Next, since most of our analysis relies on the symmetry of the underlying tensor, it is desirable to show that every tensor along the optimization trajectory of GD on (5) remains symmetric if started from symmetric tensor. Please find its proof in Appendix
Lemma 1.
If the GD trajectory of {wrJe will all be symmetric.
5 {weJe is initialized at symmetric rank-l tensor Wo, then
4.2 Main Ideas and Proof Sketch
In this subsection, we highlight the main ideas behind implicit bias in GD. Lemma 12 and 13 details the first and second step, and deferred to Appendix C.2 The proofs to the results of this section can also be found in that appendix. The lemmas alongside with their proofs are highly technical and not particularly enlightening, therefore omitted here for simplicity. However, the most important takeaway is that for the 9th iterate along the GD trajectory of ( we have the decomposition
W = (Ze we) - E. == W E2
for some Z₁ and Eg such that E = (c²)). This essentially means that by scaling the initialization Wo be small in scale, the error term E, can be ignored from spectral standpoint, and scales with at a cubic rate. This will soon be proven to be useful next.
Lemma 2. Given w, along the GD trajectory of ( its first v-eigenvalues, defined in
definition f satisfy the relation
(we)
|| + no (U))( |E I (O))
(6)
(w))
|0 2ol + not (U))= |EE]ls/e |u] xo (1 + (U))² 0(2)
where 0n (U) and oU( denote the first and second singular values U (A,A, E Rarxer and U1, U22 the associated singular vectors.
Lemma 2 showcases that when 6 is small, the ratio between the largest and second largest (U))*)
eigenvalues of w is dominated by (1l=ool3 (o)(())))))) (/u] 2o
Now, if either |ι=оlÍ is large or |u zol' approaches in value, then the ratio may be relatively large, contradicting claim. However, this issue be easily addressed by letting 2n + 9 R where is a vector with each entry being i.i.d sampled from the Gaussian distribution (0 p). Note that since U (A,, b)3, we can calculate U and directly. Lemma 14 in Appendix e shows that with this initialization, |u] zol' = O(1) and || O(1) with high probability if we select (1/nr). Therefore, the hh iterate along the GD trajectory of ( satisfies
Xg(w))
+ (U))
(we)
(1 a (1+

---

with hight probability if p is small. This implies that "the level of parametrization helps with separation of eigenvalues". since increasing will decrease ratio A5(w;)/Ai(w: Furthermore, regardless of the value of o1 (U), a larger 1 will make this ratio exponentially smaller, proving the efficacy of algorithmic regularization of GD in tensor space.
By combining the above facts, we arrive at major result showing how small initialization could make the points along the GD trajectory penalize towards rank-1 as increases
Theorem 1. Given the optimization problem 5 and its GD trajectory over some finite horizon T, i.e., [wr]izo with We+1 W. V/ ( where n is the stepsize, then there exist U(K, (), 2 1 and such that
X (we) X((w,)
S
VE [L(Ks, 1), [r]
(8)
We is initialized as wo exo s0t with sufficiently small e, where t(k, 1) is expressed as
I t(x, 1) = </lp moll
(1+
+++ moi (o)
By using the initialization introduced in Lemma 14 we can improve the result of Theoerem D which does not need to be arbitrarily small. The full details are presented in Corollary in Appendix 0.2 stating that as along as t x (1/k) In ((1 + moo (U)) +11+1000 (U))) -1 W, will be x-rank- as long is chosen as a function of U, Ls, and k. Note that we say tensor w is "k-rank-11 " if X (w)A[(()) S K.
5 Approximate Rank-1 Tensors are Benign
Now that we have established the fact that performing gradient descent on ( will penalize the tensor towards rank-1, it begs the question whether approximate rank-1 tensors can also escape from saddle points, which is the most important question under study in this paper. Please find the proofs to the results in this section in Appendix D
To do so, we first introduce a major spectral decomposition of symmetric tensors that is helpful.
Proposition 1. Given a symmetric tensor w E Rarrll, it can be decomposed into two terms, namely term consisting of its dominant component and another term that orthogonal to this direction:
w =Xi w + w! = Wa + w!,
W. E ER,
|[,, 1l =1
(10)
where (w, w (w) and (wl, w 0. Furthermore, if w is R-rank-1 tensor, then ||w||ls S kAf(w,))
Next, we characterize the first-order points of ( with approximate rank-1 tensors in mind. Previously, we showed that a given FOP of (5) symmetric and rank-1. has a one-to-one correspondence with FOPs of ( However, if the FOPs of ( are not exactly rank-1, but instead k-rank-l, I, it is essential understand whether they maintain the previous properties. This will be addressed below.
Proposition Assume that a symmetric tensor w Rurol is an FOP of (.. meaning that (7a) holds. If it is k-rank-1 tensor with < ( (Pe), then it admits a decomposition as
W = =X" ( (w)
sl + w
with mw)) E guxr being an FOP of
2 and || Ils <Xf(w) by definition.
The proposition above asserts that for any given FOP of (5. if is k-rank-1 I rather than being truly rank-1, it will consist of rank-1 term representing lifted version of an unlifted FOP, as well as
a term with small spectral norm. Referring to (58). it is possible to achieve a significantly low through a moderate number of iterations. This result, considered the cornerstone of this paper, demonstrates that the use of gradient descent with small initialization will find critical points that are lifted FOPs of ( with added noise, maintaining a robust association between FOPs of and ( This finding also facilitates this subsequent thcorem:
7

---

Theorem 2. Assume that a symmetric tensor w Rurol is an FOP of $ that is k-rank-1 with I (I)) Consider its major spectral decomposition w Aga + wi with Rr then it has rank-1 I escape direction if = mat(ā) satisfies the inequality
La (xx(T)) (r(()))))))))))))))M()) + O(rR!!)
|M - X
(11)
02s
where is odd and large enough so that
> 1/(1 10g2(23)) and 3 is defined as
B L. tr (M (MM))
a. a.ll - XX TTI 11 - ((r2)/1)
This theorem conveys the message that by running GD on S all critical points have escape directions as long as the point is not close to the ground truth solution. In Appendix B we present Theorem 7
provide sufficient conditions for the conversion to hold globally when [1 is hard to hold.
6 Numerical Experiments
In this sectior P after we run a given algorithm on e to completion and obtain a final tensor wy, we then apply tensor PCA (detailed in Appendix F on WT extract its dominant rank-1 component and recover X E lRxr such that (WT), X vec (Xr) @l Since wy will be approximately rank-1, the
success of this operation is expected 23 24 We consider trial be successful if the recovered
XT satisfies XT F S 0.05. We also initialize our algorithm as per Lemma 14
6.1 Perturbed Matrix Completion
The perturbed matrix completion problem is introduced in 20 matrix completion problems. The A operator introduced as
which is noisy version of classic
MMj if (i. E
AM =
(12)
(pMy otherwise
where Ω is measurement set such that Q = {(i, (i, (1,k),, (2k, i)I Vi E [n], [ln/2]]]. 220
has proved that each such instance has ((2(n/2) - spurious local minima, while it satisfies the RIP property with &2r = (1 - p)/(1 + p) for some sufficiently small p. This implies that common first-order methods fail with high probability for this class of problems. In our experiment, we apply both lifted and unlifted formulations to (12) with p = 0.01, yielding 82r
We test different values of n and e, using lifted level of 3. We ran 10 trials each calculate success rate. If unspecified in the plot, we default n = 10, = 10-7, Figure reveals a higher success rate for the lifted formulation across different problem sizes, with smaller problems performing better as expected (since larger problems require higher lifting level). Success rates improve with smaller e, emphasizing the importance of small initialization. We employed customGD, modified gradient descent algorithm with heuristic saddle escaping. This algorithm will deterministically escape from critical points utilizing knowledge from the proof of Theorem 4 For details please refer to Appendix Furthermore, to showcase the implicit penalization affects of GD, we obtained approximate measures for >5 A/::)//) (w:) (since exactly solving for them is NP-hard) along the trajectory, and presented the results and methods in Appendix E
Additionally, we examine different algorithms for 5 including customGD, vanilla GD, perturbed GD 4C. for its ability to escape saddles), and ADAM 41. Figure 2 suggest that ADAM is an effective optimizer with high success rate and rapid convergence, indicating that momentum acceleration may not hinder implicit regularization and warrants further research. Perturbed GD performed poorly, possibly due to random noise disrupting rank-1 penalization.
6.2 Shallow Neural Network Training with Quadratic Activation
has long been known that the matrix sensing problem @ includes the training of two-layer neural networks (NN) with quadratic activation as a special case 12 In summary, the output of the neural
Phag:://ghhbbccom//ooooeessssiie teeso .run 2021 Macbook Pro

---

Success Varying n
Success for Varying Initialization Scale
1.0
1.0
Lapent
unlifted
success Hate
0.8
0.8
litted
Legent unilited lifted
Success
0.4
0.2
0.2
12
1e-3
10-4
10-3
1
1
Problem Size
Init Scale
Figure I: Success rate of the lifted formulation versus the unlifted formulation against varying n and The algorithm of choice CustomGD (details Appendix
Success Rate Different Algorithms
Trajectory
1.0
CustomGD
GU
0.6
customGO
Lagend
20
ADAM
PerturbedGD
GT)
15
0.4
RertursedDD
ADMM
10-3
1
1
250 500
750 1000 1250 1300 2000
Scale
Iteration
Figure 2: Performance of different algorithms applied to the lifted formulation
network y E Rm with respect to m inputs {d E Th. can be expressed as yi 1 gX (XT d,). which implies yi (d.d," XXT), where g(-) is the element-wise quadratic function and X E gaxr in 2 represents the weights of the neural network. Thus represents the number of hidden neurons. outperforms
In our experiment, we demonstrate that when m is small, the lifted framework standard neural network training in success rate, yielding improved recovery of the true weights. We set the hidden neurons number to n for the standard network training, thereby comparing the existing over-pare parametrization framework (recall Section I.1 with I Psearch = n)) with the lifted one We employ the ADAM optimizer for both methods. Table 2 showcases the success rate under various problem and sample sizes. Sampling both data and true weights Z E Raxr from an i.i.d Gaussian distribution, we calculate the observations y and attempt to recover Z using both approaches. As the number of samples increases, does the success rate, with the lifted approach offering significantly better accuracy overall, even when the standard training has a 0% success rate.
Success Rate
m= 20
m=30
m=40
Success Rate
m 30
m=40
m=50
n=8
0.9(0)
1(0.3)
0.9(0.5)
n=8
0.3(0)
0.3(0)
0.8(0)
n=10
0.2(0)
0.6(0)
0.8(0)
n=10
10
0.3(0)
0.4(0)
0.2(0)
1=12
0.1(0)
0.4(0)
0.8(0)
n=12
0(0)
0(0)
0.2(0)
(a) Ground truth weight with r 1
(b) Ground truth weight with r
Table 2: Success rate of NN training using and original formulation. The number inside the parentheses denotes the success rate of the original formulations. 10-5 and / 3.
7 Conclusion
Our study highlights the pivotal role of gradient descent in inducing implicit regularization within tensor optimization, specifically in the context of the lifted matrix sensing framework. We reveal that GD can lead to approximate rank-1 1 tensors and critical points with escape directions when initialized at an adequately small scale. This work also contributes to the usage of tensors in machine learning models, as introduce novel concepts and techniques cope with the intrinsic complexities of tensors.

---

8 Acknowledgement
This work was supported by grants from ARO, ONR, AFOSR, NSF, and the UC Noyce Initiative.
References
[1] D. L. Donoho, "Compressed sensing," IEEE Transactions on information theory, vol. 52, no. 4, pp. 1289-1306, 2006.
[2] E. J. Candès and B. Recht, "Exact matrix completion via convex optimization," " Foundations of Computational Mathematics, vol. 9, no. 6, pp. 717-772, 2009.
[3] E. J. Candès and T. Tao, "The power convex relaxation: Near-optimal matrix completion," IEEE Transactions on Information Theory, vol. 56, no. 5, pp. 2053-2080, 2010.
[4] L. T. Nguyen, Kim, and B. Shim, "Low-rank matrix completion: A contemporary survey," IEEE Access, vol. 7, pp. 94215-94237, 2019.
[5] A. Singer, "Angular synchronization by cigenvectors and semidefinite programming," Applied and Computational Harmonic Analysis, vol. 30, no. I, pp. 20-36, 2011.
[6] N. Boumal, "Nonconvex phase synchronization," SIAM Journal on Optimization, vol. 26, no. 4, pp. 2355-2377, 2016.
[7] Y. Shechtman, Y. C. Eldar, O. Cohen, H. N. Chapman, J. Miao, and M. Segev, "Phase retrieval with application optical imaging: A contemporary overview," IEEE Signal Processing Magazine, vol. 32, no. 3, pp. 87-109, 2015.
[8] S. Fattahi and S. Sojoudi, "Exact guarantees on the absence of spurious local minima for non- negative rank-1 robust principal component analysis," Journal of Machine Learning Research, vol. 21, pp. 1-51, 2020.
[9] Y. Zhang, R. Madani, and Lavaei, "Conic relaxations for power system state estimation with line measurements," IEEE Transactions Control of Network Systems, vol. 5, no. pp. 199--1205, 2017.
[10] M. Jin, I. Molybog, R. Mohammadi-Ghun and J. Lavaei, "Towards robust and scalable power system state estimation." " in 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 1245-32522 IEEE, 2019.
[11] Molybog, Madani, and J. Lavaei, "Conic optimization for quadratic regression under sparse noise," The Journal of Machine Learning Research, vol. 21, no. 1, pp. 7994 8029, 2020.
[12] Y. Li, T. Ma, and H. Zhang, "Algorithmic regularization over- parammatmttri matrix sensing and neural networks with quadratic activations." " in Conference On Learning Theory, pp. 2-47, PMLR, 2018
[13] S. Burer and R. D. Monteiro, "A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization," Mathematical Programming, vol. 95, no. 2, pp. 329-357, 2003.
[14] R. Y. Zhang, S. Sojoudi, and Lavaei, "Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery," Journal of Machine Learning Research, vol. 20, no. 114, pp. 1-34, 2019.
[15] Z. Ma, Y. Bi, J. Lavaci, and S. Sojoudi, "Sharp restricted isometry property bounds for low- rank matrix recovery problems with corrupted measurements." in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, pp. 7672-7681, 2022.
[16] W. Ha, H. Liu, and R. F. Barber, "An equivalence between critical points for rank constraints versus low-rank factorizations." SIAM Journal on Optimization, vol. 30, no. 4, pp. 2927-2955. 2020.
10

---

[17] H. Zhang, Y. Bi, and J. Lavaei, "General low-rank matrix optimization: Geometric analysis and sharper bounds," Advances in Neural Information Processing Systems, vol. 34, pp. 27369-27380, 2021.
[18] R. Y. Zhang, "Sharp global guarantees for nonconvex wank matrix recovery in the overpa- rameterized regime," arXiv preprint arXiv:2104.10790, 2021.
[19] R. Y. Zhang, "Improved global guarantees for the nonconvex burer-monteiro factorization via rank overparameterization." arXiv preprint arXiv:2207.01789, 2022.
[20] B. Yalcin, Z. Ma, J. Lavaei, and S. Sojoudi, "Semidefinite programming versus burer-monteiro factorization for matrix sensing," in Proceedings of the AAAI Conference on Artificial Intelli- gence, 2023.
[21] Z. Ma, I. Molybog, J. Lavaei, and S. Sojoudi, "Over-pane paverrraramttiizaiionn via lifting for low-rank matrix sensing: Conversion of spurious solutions to strict saddle points," in International Conference on Machine Learning, PMLR, 2023.
[22] J. B. Lasserre, "Global optimization with polynomials and the problem of moments," SIAM Journal on optimization, vol. 11, no. 3, pp. 796-8777777 817, 2001.
[23] E. Kofidis and P. A. Regalia, "On the best rank-1 approximation of higher-order supersymmetrrc tensors," SIAM Journal Matrix Analysis and Applications, vol. 23, no. 3, pp. 863-884 2002.
[24] L. Wu, X. Liu, and Z. Wen, "Symmetric rank-1 I approximation of symmetric high-order tensors," Optimization Methods and Software, vol. 35, no. 2, pp. 416-438, 2020.
[25] E. Levin, J. Kileel, and N. Boumal, "The effect of smooth parametrizations nonconvex optimization landscapes," " arXiv preprint arXiv:2207.03511 2022.
[26] P. Li, X. Liang, and H. Song, "A survey on implicit bias of gradient descent," in 2022 14th International Conference Computer Research and Development (ICCRD), pp. (08-114, IEEE, 2022.
[27] D. Stöger and M. Soltanolkotabi. "Small random initialization is akin to spectral learning: Opti- mization and generalization guarantees for overparameterized low-rank matrix reconstruction." Advances in Neural Information Processing Systems, vol. 34, pp. 23831 128443, 2021.
[28] J. Jin, Z. Li, K. Lyu, S. S. Du, and J. D. Lee, "Understanding incremental learning of gradient descent: A fine-gr -ne-grained analysis of matrix sensing," " arXiv preprint arXiv:2301.11500 2023.
[29] J. Ma and S. Fattahi, "Global convergence of sub-gradient method for robust matrix recov- ery: Small initialization, noisy measurements, and parameterrizationn. " arXiv preprint arXiv:2202.08788 2022.
[30] Z. Ma, Y. Lavaei, and S. Sojoudi, "Geometric analysis of noisy low-rank matrix recovery in the exact parametrized and the overparametrized regimes INFORMS Journal on Optimization, 2023.
[31] B. Recht, M. Fazel, and P. A. Parrilo, "Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization." SIAM Review, vol. 52, no. 3, pp. 471-501 2010.
[32] T. T. Cai and A. Zhang, "Sharp rip bound for sparse signal and low-rank matrix recovery," Applied and Computational Harmonic Analysis, vol. 35, no. 1, pp. 74 74-93, 2013.
[33] J. Zhuo, J. Kwon, N. Ho, and C. Caramanis, "On the computational and statistical complexity of peraatteeeter matrix sensing." arXiv preprint arXiv:2 2021.
[34] N. Razin, A. Maman, and N. Cohen, "Implicit regularization in tensor factorization," Interna- tional Conference on Machine Learning, pp. 8913-8924, PMLR, 2021.
[35] N. Razin, A. Maman, and N. Cohen, "Implicit regularization in hierarchical tensor factorization and deep convolutional neural networks," " in International Conference on Machine Learning, pp. 18422-18462, PMLR, 2022.

---

[36] R. Ge, Y. Ren, X. Wang, and M. Zhou, "Understanding deflation process in over over- parametrized tensor decomposition, Advances in Neural Information Processing Systems, vol. 34, pp. 1299- 1311, 2021.
[37] E. J. Candes and Y. Plan, "Tight oracle inequalities for low-rank matrix recovery from minimal number of noisy random measurements," 2011.
[38] L. Qi, S. Hu, X. Zhang, and Y. Chen, "Tensor norm, cubic power and gelfand limit," arXiv preprint arXiv: 10942, 2019.
[39] L. Qi, "The spectral theory of tensors (rough version))" arXiv preprint arXiv:1201.342) 2012.
[40] C. Jin, Netrapalli, R. Ge. S. M. Kakade, and M. I. Jordan, "On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points," Journal of the ACM (JACM), vol. 68, no. 2. pp. 1-29, 2021.
[41] D. P. Kingma and Ba, "Adam: A method for stochastic optimization," arXiv preprint arXiv:1412.69800 2014.
[42] Q. Li, Z. Zhu, and G. Tang, "The non-convex geometry of low-rank matrix optimization."" Information and Inference: A Journal of the IMA, vol. 8, no. 1, pp. 51-96, 2019.
[43] T. G. Kolda, "Numerical optimization for symmetric tensor dccomposition." Mathematical Programming, vol. 151, no. I. pp. 225-248, 2015.
[44] K. B. Petersen. M. Pedersen, et al., "The matrix cookbook." Technical University of Denmark, vol. 7, no. 15, p. 510, 2008.
[45] Z. Ma and S. Sojoudi, "Noisy low-rank matrix optimization: Geometry of local minima and convergence rate," International Conference on Artificial Intelligence and Statistics, pp. 3125- 3 150, PMLR, 2023.
[46] G. Zhang and R. Y. Zhang, "How many samples is good initial point worth in low-rank matrix recovery?," in Advances in Neural Information Processing Systems, vol. 33, pp. 12583-12592, 2020.
[47] Y. Bi and Lavaei, "Global and local analyses of nonlinear low-rank matrix recovery problems," 2020. arXiv:2010.04349,
[48] L.-H. Lim and P. Comon, "Blind multilinear identification," IEEE Transactions on Information Theory, vol. 60, no. pp. 2260-1280, 2013.
[49] Comon, G. Golub, L.-H. Lim, and B. Mourrain, 'Symmetric tensors and symmetric tensor rank," SIAM Journal on Matrix Analysis and Applications, vol. 30, no. 3, pp. 1254-1279, 2008
[50] G. Ni, "Hermitian tensor and quantum mixed state," arXiv preprint 1922.00900 2019.
[51] S. Chang, "Hrnnon-wright inequality for random tensors under einstein product," arXiv preprint arXiv:2111.1119,, 2021.
[52] R. Vershynin, High-dimensional probability: An introduction with applications in data science, vol. 47. Cambridge university press, 2018.
12


Reviews:
[{"review_id": "7M7ZkykUCu", "reviewer": "Reviewer_RX1r", "summary": "Gradient descent induces implicit regularization for tensor optimization. Specifically, it has a bias towards approximately rank-1 solution in the lifted matrix sensing framework. In Theorem 1, the authors show that the ratio between the second v-eigenvalue and the first v-eigenvalue exponentially decays to 0 in terms of the number of iterations. In theorem 2, the authors show that any first-order solution of the lifted problem that is far away from the ground truth is a saddle point.\n", "questions": "line 232 typo: \"fist\" to \"first\"", "limitations": "The main results are theoretical results.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The authors carried out complicated proof and show non-trivial results. The generalization of lifted problems from r=1 to general r is very interesting. Given that this is very theoretical, the presentation is good enough to capture the main proof strategy. ", "weaknesses": "There is still some confusion and I hope the authors can better explain them in the paper. \n1) In Theorem 2, the authors show that if the approximation error is large, then GD can always find a direction to improve. However, it is not clear whether the lower bound is actually meaningful. For example, if $M^*$ is the identity matrix in the first $r$ dimension and $\\hat{X}\\hat{X}^T$ is the identity matrix in the next $r$ dimension. Then I would think $\\hat{X}\\hat{X}^T$ is not a good estimate for $M^*$ but the approximation error is 2r may not satisfy the lower bound $\\frac{L_s}{\\alpha_s}r $. Since the ratio $\\frac{L_s}{\\alpha_s}$ relates to the RIP condition and the authors have discussed how overparameterization can relax RIP constraints, I encourage authors to provide more discussions around the lower bound and possible connection to the RIP condition.\n\n2) On line 262, the authors mentioned that \"since increasing $l$ will decrease ratio $\\lambda_2^v(w_t)/\\lambda_1^v(w_t)$ provided that $\\sigma_1(U)\\geq 1$. I am not sure how strict this condition is and my guess is some simple tricks may make this condition always hold. \n\n3) From Theorem 1, it looks like the rank 1 regularization always holds regardless of the value of $l$, and lifting may not be necessary. Theorem 2 requires a large and odd value of $l$ which is not clear to me why this condition is needed. Some explanation would be nice.\n\n4) When $w_t$ is approximately rank-1, what does it implies about the rank of original estimate $\\hat{X}$ for general r? It is not very clear to me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the detailed comments and keen suggestions. The following are our responses to the review comments:\n\n(1) The reviewer raises a nice point regarding the specific example given. It is important to emphasize that the condition in (11) represents a sufficient condition rather than a necessary one. This implies that if the distance exceeds the RHS of (11), the conversion can be ensured based on the theory. However, even when (11) does not hold, it does not preclude the possibility of conversion. To address this concern, Theorem 7 in the appendix provides a proof that, irrespective of whether (11) is met, all spurious solutions can be converted to strict saddles as long as $||M^*||_F$ remains small. We intend to clarify this distinction more explicitly in the main text should the paper be accepted.\n\n(2) The condition $\\sigma_1(U) \\geq 1$ is not an important one because even if $\\sigma_1(U) < 1$, it still hold that $\\sigma_2^l(U) \\leq \\sigma_1^l(U)$, and that the RHS of (7) will be larger than 1 regardless. We thank the reviewer for pointing it out, and will delete this sentence to avoid confusion.\n\n(3) Our work builds upon [1], where the authors demonstrated that a large and odd $l$ is necessary for the conversion from spurious solutions to strict saddles. However, their theoretical analysis was limited to the special case of rank-1 matrices, a property that is difficult to maintain. In our study, we show that employing the gradient descent algorithm with a small initialization implicitly preserves this property without imposing any rank constraints. This finding is established in Theorem 1. In summary, a large $l$ is essential for the optimization landscape to possess favorable properties contingent on being rank-1, and Theorem 1 establishes that a simple algorithmic choice ensures the tensor's approximate rank-1 nature, irrespective of $l$. Furthermore, Theorem 2 demonstrates that this \"approximate\" rank-1 property is benign when compared to being truly rank-1.\n\n(4) Then tensor $w_t$ being approximate rank-1 has no implication on the rank of the original estimate $\\hat X$, and the maximum rank of $\\hat X$ is assumed to be known a priori in order for (5) to be established correctly.\n\n[1] Z. Ma, I. Molybog, J. Lavaei, and S. Sojoudi, “Over-parametrization via lifting for low-rank matrix sensing: Conversion of spurious solutions to strict saddle points,” in International Conference on Machine Learning, PMLR, 2023."}, {"review_id": "3sb6wKKnp1", "reviewer": "Reviewer_Dh4F", "summary": "This paper presents a new GD algorithm that is suitable for the problem of matrix sensing. Within this algorithm a 1-rank approximation of the corresponding tensor is made. A distinctive feature of this algorithm is that some points of local minima are turned into saddle points, which improves the convergence to the global optimum.", "questions": "Have you tried testing the algorithm on more complex real-world problems?", "limitations": "The theorems mention constraints on the operator $\\mathcal A$, which appears in the formulation of the matrix sensing problem. Thus, the developed method is restricted to problems that can be reduced to the matrix sensing conception and those for which certain conditions are imposed. It seems difficult to say in advance (without numerical experiments) whether the algorithm will work on this particular problem.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- A new modification of the gradient descent method was invented and implemented, which gives an advantage in certain problems\n\n- This article shows the importance and application of concepts from tensor algebra to machine learning.\n\n- All the algorithms are described in detail in Appendix\n\n- All the proofs are given in Appendix, and all the necessary terms are neatly given in the text of the article and Appendix.\n\n\n\n", "weaknesses": "- The article is overloaded with technical details and terms, many of which are only defined in appendix. This makes it difficult to understand the main idea of the article. Perhaps this style would be more suitable for people specializing in tensor algebra and matrix sensing problems.\n\n- Only few numerical experiments have demonstrated a strong advantage of the method.\n\n\n- Minor:\nline 156 possible typo, must be $2d$ instead of $d$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the detailed comments and keen suggestions. The following are our responses to the review comments:\n\n(1) We express our gratitude to the reviewer for bringing up this concern. To enhance the accessibility of our work, we intend to streamline the main text by providing concise details and devote more space to explaining the core theorems. This adjustment will facilitate comprehension for general readers less familiar with the subject matter. Furthermore, we propose to reorganize the appendix into separate sections, each self-contained, enabling readers to explore specific topics without the need to refer to other sections except when necessary for more in-depth investigation.\n\n(2) In our experiments, we focused on two problems that we believe are important in the class of matrix sensing. Due to the computationally intensive nature of the lifted framework, we conducted experiments with problem sizes that were within the limits of our available resources. Our experiments demonstrate that small initialization with a tensor parametrization can drastically increase the probability of reaching the global optimum, and that a proper choice of algorithm is very important in the over-parametrized regime. In fact, both experiments showed meaningful improvements across a number of different settings. Nevertheless, we recognize the value in applying our technique to larger-scale problems, and we have started working on how to use parallel computing and high-performance machines to solve large-scale lifted problems. The issue is that since this is a new framework, developing fast algorithms tailored to this problem is beyond simply coding the problem and passing it to an off-the-shelf solver. We hope to complete the simulations with larger sizes in a month and add them to the next version of the paper.     \n\n(3) We appreciate the reviewer for pointing out our typo on line 156.\n\n(4) Regarding the limitations, this lifted technique can to be applied to general matrix sensing problems and does not need anything to be checked in advance, as long as the problem can be written in the form of equation (2). Theorem 2 is only a sufficient condition to ensure the conversion of spurious solution, and the only requirement is that the unlifted problem should have a non-zero $\\alpha_s$, which can be easily satisfied with full-rank sensing matrices. Alternatively, this non-zero $\\alpha_s$ can also be expected to hold with high probability if the sensing matrices are sampled from i.i.d. Gaussians [1].\n\n[1] Candes, E. J. and Plan, Y. (2011). Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements."}, {"review_id": "CiSMuao0aG", "reviewer": "Reviewer_t1t9", "summary": "Studies the implicit regularization of gradient descent for a certain tensor optimization problem, obtained through the “lifted” matrix sensing framework. Lifting matrix sensing problems is a technique for transforming the original (non-convex) landscape into a new (still non-convex) landscape with favorable properties. In particular, spurious local minima are converted into strict saddle points.\n\nThe current paper establishes that, under near-zero initialization, gradient descent over the lifted matrix sensing problem leads to approximate rank one tensors until a certain time step. Furthermore, it shows that one can extract a first-order point for the original matrix sensing problem from approximately rank one first-order points of the lifted problem. Along the way, derives a lifting framework over symmetric tensors for matrix sensing problems with a ground truth matrix of arbitrary rank. Experiments corroborate the theory by demonstrating that optimizing the lifted problem may lead to better reconstruction than optimizing the original problem.", "questions": "1. In the numerical experiments, is there a reason for comparing success rates as opposed to normalized reconstruction errors? How was the threshold of 0.05 chosen?\n\n2. Why not parameterize the tensor as a symmetric rank one matrix from the get go, as opposed to optimizing over the full tensor. The former is more efficient in terms of the number of parameters and guarantees that the trajectory stays rank one. Is it a matter of optimization, i.e. that a symmetric rank one parameterization may converge to spurious local minima/non-strict saddles?\n", "limitations": "As detailed in the review above, I believe there is room for improvement in terms of explicitly addressing the limitations and gaps of the current theory.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Establishes a novel implicit regularization of gradient descent for tensor optimization problems. In particular, as far as I am aware, this work is the first to show for the specific problem of (5) that gradient descent will lead to a trajectory that is approximately rank one until a certain time step.\n\n2. Existing analyses of implicit regularization in tensor problems have focused on gradient flow (gradient descent with an infinitesimally small step size), while the current work supports the more realistic gradient descent with a finite step size.\n\n3. The technical tools used, e.g. the v-eigenvalue definition, may be of use for future work on the implicit regularization in tensor problems.\n\n4. The paper reads relatively well. Ample explanations and high-level intuitions are provided regarding the theoretical analysis.\n", "weaknesses": "1. There seem to be gaps in the theory that are not adequately addressed (or mentioned explicitly). Specifically:\n\n    - Theorem 1 applies for some k < 1. In principle, at least from the theorem statement, it seems that k can be close to one, in which case the tensor is not really approximately rank one. For Theorem 2, k needs to be upper bounded by a quantity depending on the target matrix. The matter of when we can expect this to hold is not treated.\n\n    - Theorem 1 and 2 establish that the tensor will be approximately rank one until some time step, and that first-order points of tensors that are approximately rank one, but do not correspond to a global minimum, have an escape direction. Yet, it is not guaranteed that we will reach a critical point while the tensor is still approximately rank one.\n\n    - In Theorem 1, it is not specified how small the initialization scale needs to be. Does the theory suggest a scale of practical size and not exponentially small in the problem parameters?\n\n    - In Theorem 2, is the rank one escape direction in the same direction of \\hat{x}? Otherwise the rank could increase upon escaping, in which case the fact that we can map rank one tensors to first-order points of the original problem may be of less use.\n\n    Obtaining full characterizations for the dynamics of gradient descent in non-convex problems is challenging, and it is not out of the ordinary to have gaps in the theory. Yet, I firmly believe that such gaps should be explicitly discussed and perhaps reconciled via experiments (e.g. showing that indeed the tensor stays approximately rank one until convergence).\n\n&nbsp;\n\n2. A large part of the motivation behind looking at the lifted problem (5) and analyzing the implicit regularization of gradient descent for it, is the possibility of achieving better reconstruction in matrix sensing problems. I find the empirical evidence provided unsatisfactory in establishing the importance of the lifted formulation. The matrix sensing experiments cover only a very specific perturbed matrix completion problem and matrix sensing problem with rank one measurements. Showing that using the lifted problem (5) is viable in more generic cases or real-world datasets can greatly boost the significance and interest of the results in my opinion.\n\n    Furthermore, for the lifting technique to be practical, $l$ cannot be too large as the size of the tensor grows exponentially with it. It is not clear whether this is limiting for typical matrix sensing problems or not from the current evaluations.\n\n&nbsp;\n\n3. Empirical support for Theorem 1, which establishes that the tensor will be approximately rank one until a certain time step, is lacking. The experiments only examine the resulting performance after extracting a rank one tensor from the last gradient descent iterate. However, they do not show whether the tensor is approximately rank one as the theory suggests, or it has grown in rank (i.e. the norm of the residual after reducing the rank one component is non-negligible). If it is the former, it strengthens the viability of the theory, while if the latter holds, then it is unclear whether the theory indeed explains the observed empirical phenomenon. I recommend reporting, e.g., the norm of the tensor after reducing from it the extracted rank one component or some other measure of how close to rank one the tensor is.\n\nAdditional (more minor) comments:\n- In the empirical evaluation, success rate is too crude of a measure in my opinion, as it is possible that the difference in reconstruction error is not large while the difference in success rate is. I believe comparing (normalized) reconstruction errors will allow for a better comparison of the performance of the lifted and unlifted techniques.\n\n- I found the inner product notation (without any subindices) to be confusing. One would expect the output to be a scalar.\n\n- Escape direction from a critical point is not formally defined.\n\n- In Theorem 1, it is not specified what t_T stands for.\n\n- Experiments are for a custom version of gradient descent that does not quite align with the theory. I would recommend clarifying briefly in words (even if in an appendix) what are the modifications it introduces and why, rather than just referring to pseudo-code.\n\n- In line 124 it is claimed that the objective considered in this paper is more general than those studied in related works. However, it seems to me that the setting is simply different/incomparable rather than more general. For example, the analysis of [1] considers any differentiable (locally smooth) loss.\n\n[1] Razin, Noam, Asaf Maman, and Nadav Cohen. \"Implicit regularization in hierarchical tensor factorization and deep convolutional neural networks.\" International Conference on Machine Learning. PMLR, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the detailed comments and keen suggestions. \n\n(1) Due to space constraints, some explanations were placed in the appendix. We apologize for any confusion and will address each concern:\n\n- Points 1 and 3: Theorem 1 outlines a relationship between ratio $\\kappa$ and iteration $t$. $\\kappa$ has no upper limit and can be achieved with enough steps, given a small initialization scale. To avoid using an arbitrarily small $\\epsilon$, we presented Corollary 1 in Appendix C.2, which establishes the order of magnitude for $\\epsilon$ and the number of iterations needed for random initialization. For instance, to achieve the value of $\\kappa$ required in Theorem 2, we need $t$ to be on the magnitude of $\\ln(||M^*||^2_F) \\ln \\left( \\frac{1+ \\eta \\sigma^l_1(U)}{1+ \\eta \\sigma^l_2(U)}\\right)^{-1}$, which has a value around 100 in the specific problem presented in Section 6.1.\n\n- Point 2: Proposition 2 shows that while the tensor remains approximately rank-1, it can reach critical points of the lifted problem, with the lifted critical point comprising a dominant term and some noise.\n\n- The rank-1 escape direction differs from $\\hat{x}$ but can be computed deterministically. As we only require the tensor to be approximately rank-1, we can set the learning rate to the same order of magnitude as the desired $\\kappa$.\n\n(2) We used perturbed matrix completion instead of standard matrix completion because its RIP constant can be easily calculated and better aligns with our theory. In both scenarios, the lifted formulation showed clear superiority even with $l=3$, but its high computational demands limit scaling with our current computational budget. Still, we explored various problem sizes and found the success of the lifted framework to be independent of the scale itself. We have started working on how to use parallel computing and high-performance machines to solve large-scale lifted problems. Since this is a new framework, developing fast, tailored algorithms is beyond simply modifying an off-the-shelf solver. We hope to complete the simulations with larger sizes in a month and add them to the next version of the paper. \n\n(3) We do not directly showcase the rank of the tensor along the optimization trajectory because tensor rank, unlike matrix rank, is not easily computable, being NP-Hard to approximate even when $l=3$ [1]. Furthermore, for the same tensor, its rank, symmetric rank, and rank based on v-Eigenvalue can all be different [2], so there is no standard metric. This is why we instead use success rate as a surrogate measure, for which a higher success rate means higher probability of escaping from saddle points, which is a hallmark of approximate rank-1 tensors.\n\nHowever, we agree with the reviewer's comment that this is an important aspect of our paper. Thus, we used the algorithm (S-HOPM) in [3] to extract the dominant rank-1 component of tensors along the trajectory (which we call $w_1$), and then subtract this main component from the tensor, and repeat the extraction procedure for $w-w_1$ to get $w_2$. We then calculate the ratio of $\\frac{||w_1||_2}{||w_2||_2}$. Using the problem defined in Section 6.1 with n=8, we get the following results for the ratio along the optimization trajectory for gradient descent:\n\n\n|  iteration  | 20 | 40 | 60 | 80 | 100 | 120 | 140 | 160 | 180 | \n| -------- | ------- | ------- | ------- | ------- | ------- |------- | ------- | ------- | ------- | \n| $\\epsilon=10^{-5}$   | 1.16 | 0.95 | 0.82 | 0.05 | 0.03 | 0.018 | 0.026 | 0.028 | 0.013 | \n| $\\epsilon=10^{-3}$ | 0.13 | 0.43 |0.44 | 0.031 |0.036| 0.0008 |0.034 | 0.028 |0.022|\n| $\\epsilon=0.1$ |0.14 | 0.02 | 0.05 | 0.034| 0.031 |0.026 | 0.022 | 0.034| 0.037 |\n\nThe table shows that the tensor gradually becomes more \"rank-1\", complying with Theorem 1. This phenomenon is not limited to small initialization scales, which is promising. However, it's essential to note that the computed ratio is not a precise reflection of $\\kappa$, as rank-1 approximation may not be globally optimal for arbitrary tensors [3]. Nevertheless, this ratio provides meaningful insights into the training dynamics, further supporting Theorem 1.\n\n(4) Regarding the minor comments/questions:\n\n- We'll use different notation for tensor inner-product.\n\n- Escape direction refers to a direction where the Hessian has a negative eigenvalue.\n\n- $t_T$ denotes the maximum allowed number of iterations, with $T$ being finite.\n\n- customGD differs from vanilla GD as it finds descent directions deterministically at a critical point.\n\n- Our techniques can analyze a wider range of tensor problems than [4], but it's not a generalization as the settings differ. We'll clarify this.\n\n- The threshold of 0.05 is chosen manually in order to avoid huge reconstruction errors to corrupt our data, especially in the sense that we do not distinguish between failed cases with reconstruction errors of 0.5 and 10.\n\n- If we parametrize the problem as a symmetric rank-1 tensor from the beginning, then no escape directions can be established using the techniques in Theorem 4, so it defeats the purpose of using a lifted framework.\n\n[1] Swernofsky, Joseph. \"Tensor rank is hard to approximate.\" Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.\n\n[2] Comon, Pierre, et al. \"Symmetric tensors and symmetric tensor rank.\" SIAM Journal on Matrix Analysis and Applications 30.3 (2008): 1254-1279\n\n[3] E. Kofidis and P. A. Regalia, “On the best rank-1 approximation of higher-order supersymmetric tensors,” SIAM Journal on Matrix Analysis and Applications, vol. 23, no. 3, pp. 863–884, 2002.\n\n[4] Razin, Noam, Asaf Maman, and Nadav Cohen. \"Implicit regularization in hierarchical tensor factorization and deep convolutional neural networks.\" International Conference on Machine Learning. PMLR, 2022."}, {"review_id": "NWMaemHfV6", "reviewer": "Reviewer_rWmQ", "summary": "This paper examines the role of gradient descent in inducing implicit regularization for tensor optimization, within the lifted matrix sensing framework. The authors show that with sufficiently small initialization, gradient descent applied to the lifted problem results in rank-1 tensors and critical points with escape directions. These findings show the significance of tensor parameterization for matrix sensing, combined with first-order methods, in achieving global optimality.", "questions": "- Line 27-29: What are the practical applications of two-layer neural networks with quadratic activations?\n- Line 137: I'm assuming FOP stands for \"first-order point\", and this acronym should be explicitly clarified.\n- Line 232: \"fist\" to \"first\"\n- Line 278: \"that wether\" to \"whether\"", "limitations": "- The authors do not provide an explicit discussion of the limitations.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Seems well-written overall.\n- Has some useful insights, like \"our findings indicate that when applying GD to the tensor optimization problem (3) an implicit bias can be detected with sufficiently small initialization points.\"\n- And also they show that, \"...when initialized at a symmetric tensor, the entire GD trajectory remains symmetric, completing the requirements\", which is interesting.", "weaknesses": "- Needs more convincing or discussion that the theory can be useful for practical applications. I find the theory interesting, but unsure of the practicality. Of course, it's nice that they give an experiment on a two-layer neural network with quadratic activations, but I'm not sure quadratic activations have been used all that much practically. Also, the last \"layer\" of the neural network just sums the outputs of the \"hidden\" layer, which is not as general. I believe this is the biggest weakness of the paper.\n\n- Hyperparameters for the different optimizations algorithms used are not found. This makes it hard to believe that the authors made a good effort to optimize the unlifted problem via perhaps a hyperparameter search.\n    - For Section 6.2, the experiment is under \"low-sample\" conditions, but this needs to be quantified and perhaps an experiment where there are \"high-sample\" (or at least non-\"low-sample\") conditions may be of interest just for completeness.\n\n- A minor point: While I did look over the proofs in the appendix, the number of pages of proof in the appendix is a bit long at 21 pages. It might help the paper to condense the proofs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the detailed comments and constructive suggestions. The following are our responses to the review comments:\n\n(1) We agree with the reviewer's observation that a two-layer neural network with quadratic activation alone is not a widely used model in modern day machine learning and solely focusing on it will not greatly benefit the machine learning community. However, the intent of this paper is not to provide a \"trick\" that only targets specific models, and instead we intent to theoretically prove that when optimizing over tensors for low-rank problems, which is an action that is implicitly done in deep neural networks including CNN [1], implicit regularization can be expected and it will eventually lead to better optimization results in the process. We thank the reviewer for raising this important question, and will take this opportunity to elucidate the importance of this work and its applicability in more detail:\n\n- Firstly, this paper focused on the general problem of matrix sensing, which includes many direct applications like medical imaging, matrix completion/recommendation systems, motion detection, and power system state estimation [2-4]. Since many of these applications are safety-critical, it is often desirable to search for the global optimum. It has been previously shown that a tensor parametrization can be helpful in pursuit of the global solution in a special case [5], and therefore we aim to prove that no explicit constraint is needed with this parametrization due to the implicit regularization effect. In this work, we focused on two specific problems to streamline the presentation, but the theoretical analysis can be readily extended to all matrix sensing problems, thereby providing merit to a wide variety of applications. \n\n- Secondly, this problem has been extensively studied in the literature as an instance of non-convex optimization, to further promote the understanding of non-convex optimization and the process of training (Please see Section 1.1 for more references). This is why it is important to focus on this specific benchmark problem, since it will advance the current understanding of the interplay between over-parametrization and non-convexity. We find that over-parametrization is only a part of the story, since an appropriate optimization algorithm that can induce implicit regularization is also key to mitigating non-convexity. Enlarging the parametrization space is very similar to increasing the number of layers in a neural network, and therefore this work provides a different angle to the usefulness of large/deep neural networks, even if three-layer networks are already universal approximators [6], and to the problem of how to best utilize the rich parametrization via a random initialization.\n\nWe will add more discussions and simulations to the paper to show the importance in applications such as state estimation.\n\n(2) For the quadratic neural network training process, the only hyper-parameter that is involved is the initial learning rate (since we use the ADAM optimizer), which is set to the default value of 0.001. We appreciate the reviewer's suggestion and tried out the success rate for the same problem described in Table 2(a) with n=8, and obtained the following values:\n\n|  n=8, unlifted  | lr = 1e-5 | lr=1e-4 | lr = 1e-3 | lr = 1e-2 | lr = 0.1 |\n| -------- | ------- | ------- | ------- | ------- | ------- |\n| m=20   | 0 | 0 | 0 | 0 | 0 |\n| m=30 | 0.1 | 0.3 |0.3 | 0.4 |0.2|\n| m=40 |0.1 | 0.4 | 0.5 | 0.6| 0.2 |\n\nThe above table shows that the initial learning rate in this setting does not affect the success rate too much, and will not make the unlifted problem have comparable performance to the lifted problem.\n\nAs for the \"low-sample\" and \"high-sample\" terminology, it simply denotes the value of $m$, as $m$ is the number of observations. It is well known in the literature [2] that when $m$ is very large and the sensing matrices are sampled i.i.d. from a normal distribution, the RIP constant of the problem will be close to 0, and all local minimizers will correspond to global solutions, meaning the problem can be solved globally. We thank the reviewer for pointing it out, and we will provide more explanations in the main text should the paper be accepted.\n\n(3) We appreciate the reviewer's suggestion of condensing the appendix, and will try to make it better compartmenlized, so that readers only need to refer to short sections at a time. We also thank the reviewer for pointing out a few typos, and we will fix those as well.\n\n[1] N. Razin, A. Maman, and N. Cohen, “Implicit regularization in hierarchical tensor factorization and deep convolutional neural networks,” in International Conference on Machine Learning, pp. 18422–18462, PMLR, 2022.\n\n[2] L. T. Nguyen, J. Kim, and B. Shim, “Low-rank matrix completion: A contemporary survey,” IEEE Access, vol. 7, pp. 94215–94237, 2019.\n\n[3] Y. Shechtman, Y. C. Eldar, O. Cohen, H. N. Chapman, J. Miao, and M. Segev, “Phase retrieval with application to optical imaging: A contemporary overview,” IEEE Signal Processing Magazine, vol. 32, no. 3, pp. 87–109, 2015.\n\n[4] Y. Zhang, R. Madani, and J. Lavaei, “Conic relaxations for power system state estimation with line measurements,” IEEE Transactions on Control of Network Systems, vol. 5, no. 3, pp. 1193–1205, 2017.\n\n[5] Z. Ma, I. Molybog, J. Lavaei, and S. Sojoudi, “Over-parametrization via lifting for low-rank matrix sensing: Conversion of spurious solutions to strict saddle points,” in International Conference on Machine Learning, PMLR, 2023\n\n[6] Wang, Ming-Xi, and Yang Qu. \"Approximation capabilities of neural networks on unbounded domains.\" Neural Networks 145 (2022): 56-67."}]

Author rebuttal:

Meta-review: This paper examines the role of gradient descent in inducing implicit regularization for tensor optimization within the context of the lifted matrix sensing framework. The paper offers interesting insights in the usefulness of tensor overparameterization for matrix problems, which translates spurious solutions to strict saddle points. After the rebuttal process, the reviewers were able to lift some initial doubts and reached a consensus for accepting this paper.
Decision: Accept (poster)