Globally Q-linear Gauss-Newton Method for Overparameterized Non-convex Matrix Sensing
Authors: Xixi Jia
Fangchen FENG
Deyu Meng
Defeng Sun
Venue: NeurIPS 2024 poster (2024)
Keywords: low-rank matrix sensing
non-convex optimization
Gaussian-Newton method
Primary area: optimization_for_deep_networks

Abstract: This paper focuses on the optimization of overparameterized, non-convex low-rank matrix sensing (LRMS)—an essential component in contemporary statistics and machine learning. Recent years have witnessed significant breakthroughs in first-order methods, such as gradient descent, for tackling this non-convex optimization problem. However, the presence of numerous saddle points often prolongs the time required for gradient descent to overcome these obstacles. Moreover, overparameterization can markedly decelerate gradient descent methods, transitioning its convergence rate from linear to sub-linear.  In this paper, we introduce an approximated Gauss-Newton (AGN) method for tackling the non-convex LRMS problem. Notably, AGN incurs a computational cost comparable to gradient descent per iteration but converges much faster without being slowed down by saddle points. We prove that, despite the non-convexity of the objective function, AGN achieves Q-linear convergence from random initialization to the global optimal solution. The global Q-linear convergence of AGN represents a substantial enhancement over the convergence of the existing methods for the overparameterized non-convex LRMS. The code for this paper is available at \url{https://github.com/hsijiaxidian/AGN}.

Globally Q-linear Gauss-Newton Method for Overparameterized Non-convex Matrix Sensing
Xixi Jia Fangchen Feng² Deyu Meng
Defeng Sun
School of Mathematics and Statistics, Xidian University
2.2TI Laboratory, University Sorbonne Paris Nord
School of Mathematics and Statisties. Xi' an Jiaotong University
4 Macao Institute of Systems Engineering, Macau University of Science and Technology
5 Department of Applied Mathematics, The Hong Kong Polytechnic University hs jiaiiiiiioi an@gmail. com, fangchen. fangchen.fengeee wangguuniv-pariste dymeng@xj tu. edu. cn, defeng sun@polyu. edu. edu. .kk
Abstract
This paper focuses on the optimization of overparameterized, non-convex low-rank matrix sensing (LRMS)-as an essential component in contemporary statistics and machine learning. Recent years have witnessed significant breakthroughs in first- order methods, such as gradient descent, for tackling this non-convex optimization problem. However, the presence of numerous saddle points often prolongs the time required for gradient descent to overcome these obstacles. Moreover, overparame- terization can markedly decelerate gradient descent methods, transitioning its con- vergence rate from linear to sub-linear. In this paper, we introduce an approximated Gauss-Newton (AGN) method for tackling the non-convex LRMS problem. No- tably, AGN incurs a computational cost comparable to gradient descent per iteration but converges much faster without being slowed down by saddle points. We prove that, despite the non-convexity of the objective function, AGN achieves Q-linear convergence from random initialization to the global optimal solution. The global Q-linear convergence of AGN represents substantial enhancement over the conver- gence of the existing methods for the overparameterized non-convex LRMS. The code for this paper is available at
githtb......... com cwwmhsi.iciccccccocccoooooo.c... wwwidia/////aaaaaaaa AGN
Introduction
Matrix sensing aims to recover unknown low-rank matrix M Rexa from its linear measurement A(M). Here each elements b, is defined as b, = (A; M), with i= 1,... m, and A(-) is only in practical applications but also in the realm of non-convex optimization (16).. As the problem often involves finding the optimal solution of non-convex minimization problem
nearly isometric linear operator. It holds significance
min TERREd.VERR.. f(U.V) = -1 - bb
where rank(M) = < of particular interest is the overparameterized case where d >> The objective function f(U, V) to be minimized is non-convex, non-smooth and meanwhile lacks
Part of this work was completed while Xixi Jia was a research fellow in the Department of Applied Mathematics at The Hong Kong Polytechnic University.
1 *Corresponding author.
?The non-smoothness pertains to (U, V), as the magnitudes of these matrices can be highly unhalanced.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

coercivity, presenting significant challenges in solving the optimization problem. Since the objective function exhibits certain key characteristics akin to the loss function of deep neural networks, problem ①1) stands as cornerstone in the study of more challenging non-convex problems, such as those For further discussions, please refer to
encountered in deep learning 7710.-
Recent years have witnessed significant progress in the study of this non-convex optimization problem.
(a) Progress on gradient descent algorithms. Existing works such 62 demonstrate that the non-convex objective function f(U, V) possesses benign loss landscape, wherein all local minima global, and concurrently, the Hessian exhibits negative eigenvalues at saddle points, allowing perturbed gradient descent algorithms to effectively escape them. To handle the non-smoot problem, prior studies 22] 12 14 [7 introduce regularization term | V Vll to the objective function. This regularization ensures balance between the norms of U and V.
Very recently, Ye and Du [8] make a breakthrough on low-rank matrix factorization (LRMF), specific setting of the problem ( (d r, m + oo), and prove that gradient descent, without perturbation and without the balance regularization on the objective function, converges at an R- linear rate to the global optimal solution of the non-convex problem from random initialization. Meanwhile, Stöger and Soltanolkotabi [19] study the global convergence of gradient descent for overparameterized (d > r) low-rank matrix sensing. However, overparameterizzaton can significantly slow down gradient descent from achieving linear convergence to sub-lineat rates, as analyzed in [3] 20 Furthermore, Xiong et al. (00 proves that imbalanced initialization can expedite the convergence of gradient descent from sub-linear to linear rate. Nevertheless, gradient descent still requires a considerable amount of time to navigate away from saddle points, as discussed in Section Additionally, the convergence rate of gradient descent is heavily reliant the condition numher of the matrix M, rendering it inefficient for solving ill-conditioned non-convex optimization problems.
4
(b) Progress on advanced algorithms. Given these deficiencies of first-order gradient meth- ods, it is intriguing and crucial to investigate how computationally efficient higher-order al- gorithms, behave this non-convex problem. Previously, Liu et al. [22) introduces a Gauss- Newton type method for symmetric LRMF (with d drr), and proved that Gauss-Newton method converges Q-linearly fast to critical point of the non-convex optimization problem. Recently, Zilber and Nadle (33 prove that the Gauss-Newton method enjoys local quadratic convergence if the initialization lies within a small basin of attraction of the global optimal solution. All these works only guarantee local convergence and neglect the influence of saddle points on the convergence. Global convergence of the -Newton method remains ambiguous. Yue et al. (4 proves that the Newton method with cubic regularization converges quadratically fast from random initialization. However, their results are only applicable for symmetric MS with d = r. and the computational cost of Newton method in (24 for LRMS is very high. Lee and Stöger (25 prove that for rank-one matrix sensing, alternating least square method converges to the global optimal solution at a linear rate from random initialization. However, it is uncertain whether the results of (25 are applicable to the r > 1 case as well as the challenging overparameterized scenario (d > r).
Comparisons of iteration complexity, with R. as the condition number of the n X n matrix. "init." denotes initialization.
Table I:
Algorithm GD 20
init.
Heration complexity
random
(og(1+77)) + 6 leg)x"/e)
PrecGD [S]
spectral
(e))
ScaledGD(X) AGN
random
log k log kn)) log(1/s)
random
log(1/e)
Another line of work deals with the deficiencies of gradient descent by incorporating preconditioning
matrices into the gradient direction, demonstrated by [15] 26 27 28). Tanner and Wei [26]
introduce a scaled alternating steepest descent method with diminishing step size and provides asymptotic convergence. Tong et al. [27 introduces ScaledGD and proves that, given spectral initialization, ScaledGD converges at a linear rate to the global optimal solution of problem (I) Additionally, the convergence rate is independent of the condition number of M. The works in [15] and [21] focus on the symmetric matrix sensing, extending the ScaledGD to the overparameterized case by introducing damping factor to control the singularity of the preconditioning matrix. However, the damping factor À can decelerate the ScaledGD from escaping the saddle regions and
the global iteration complexity becomes log k log(en) + log(1/s) as given in Table
Our contributions. In this paper, we focus on the general model (1) which covers both symmetric matrix sensing (M is symmetric and positive semi-definite) and asymmetric matrix sensing (M is rectangular matrix), particularly with d > r. Building upon the insights from [23 25 26). we use an approximated Gauss-Newtes (AGN) method for solving the non-convex optimization problem

---

Notably, in each iteration, AGN performs computations akin to gradient descent, yet it exhibits Q-linear convergence rate towards the global optimal solution from random initialization, with global iteration complexity log(1/E) as shown in Table AGN. Moreover, the Q-linear factor is independent of the condition number of M. Under certain conditions on the sensing operator A()), we can prove super-linear convergence of the AGN. This distinctive convergence property substantially enhances outcomes compared to existing methods in achieving global convergence, as shown in Table D Additionally, as a byproduct result, we establish that the prevailing preconditioned gradient descent methods are analogous to the Gevenberg-Marquuee
method within the Gauss-Newton framework.
To conclude, the contributions of this paper are as follows. First, we reformulate the symmetric and asymmetric matrix sensing
unified way, based on which we design an approximated Gauss- Newton (AGN) method. We show that the existing preconditioned gradient descent algorithms,, ScaledGD(A) and PrecGD in 15 21 respectively, correspond to a certain type of the method. Then we analyze the behavior of GD, Scaled ())PreC and AGN at e-neighborhood of the saddle points. The saddle point analysis shows that AGN is not attracted to saddle points, unlike GD) and PrecGD. Specifically, GD and Scaled A)/PrecGD achieve an objective function decrease of o(s), while AGN achieves a significantly larger, e-independent decrease (1). Finally, we prove the global Q-linear convergence of AGN for overparameterized non-convex LRMS. This significantly improves over algorithms like ScaledGD(A) and PrecGD, which achieve R-linear convergence but are hindered by saddle regions.
This paper organized in the following ways. Section provides an overview of related works. Section 3 Joutlnnes our AGN method for both symmetric MS and asymmetric MS, and explores the connections between AGN and (caled())PrreGGD.. Section| insights into the behavior of GD, ScaledGD, and AGN in the vicinity of saddle points. Section Sarionnjoouiiiii ooullines the main convergence result with a proof sketch, Section 6 presents experimental results, and Section 7 concludes the paper.
2 Related work
2.1
Overparametterizaton matrix sensing and beyond
Overparamettrrizatinn significantly impacts the optimization of both the non-convex low-rank matrix recovery problem [9
15 19 29 and deep learning 32.35 Specifically, [5 29 analyzed that
overparanterization can eliminate the spurious local minima of the non-convex low-rank matrix recovery problem. Meanwhile, since the exact rank parameter r is not predetermined, in woal-world applications one often relies on a moderately higher rank d > т, as elaborated in [21]. Geyer et al. (36) study the solution uniqueness in the overparamterized low-rank matrix sensing. Additional works examining overparameterized low-rank models include, but are not limited to 37759
2.2 Preconditionned/Saale gradient descent
Preconditionedd/calee gradient descent (ScaledGD) aims to enhance convergence by adjusting the gradient direction using preconditioning matrices, as specified in [6 27
21 28 40 It resolves
the non-convex optimization problem (1 by the following iteration
Ul41 U. - VVU VO vo
(2)
V4+1 V, V/ fU, ())
which corresponds to the methods in 27 28 40 for r = d. The author in (6) updates U and V in an alternating manner. If U V and d r, then the iteration becomes ScaledGDD(A/PreeGi) U = U, - V / (U., (U, U, + X,1)-
(3)
where Ae > 0 can be either constant or time-varying. and the itcration corresponds to the methods in 115 21). ScaledGD(A) (21) and PrecGD [15] have been shown achieve linear convergence to the global optimal solution, whether in a local context or in a global context. However, the parameter A can degrade the global convergence, shown in Fig. where PrecGD struggles escape saddle regions before achieving local linear convergence.
2.3 Gauss-Newton method
The Newtsn (GN) method is widely recognized approach for nonlinear least-square
a E (xx)
min
(4)
3

---

((xx)), and J(x,) J(xa) is an the second-order where Φ R + R is nonlinear, twice continuously differentiable function. In each iteration t, GN aims to solve least-squares of the linear approximation o(x) at point 2,
I++1 = + n7,, where A. = arg min (xx) } [1b(2z)) + J(=)) 2
(5)
AER
where J(x,)) (((x)) the Jacobian of the nonlinear function Φ6.) at 3t, and 1j > 0 the step- length, ") 1 corresponds to the GN method, " < 1 corresponds to the damped Gauss-Newton method. The A, is calculated by 4, - [xx)) [ax))
approximation of the Hessian (x,) J (xx) Jxx,) + Ei=1
term is small. The GN method generally has a local convergence guarantee, indicating its effectiveness
primarily within the vicinity of a solution [22] 23 41) When applied the LRMS problem ( we
will show in Section 3.3 that the AGN method is closely related to the ScaledGD(A//reecG)) method.
3 Proposed method
In this section, we begin by unifying the formulation of both symmetric matrix sensing (where U V and M positive semi-definite) and asymmetric matrix sensing problems. Based on the corresponding nonlinear least-squares problem, we introduce our approximated Gauss-Newton (AGN) method. Then we prove that the proposed AGN a descent method, Furthermore, when addressing symmetric matrix sensing, we explore two distinct parameterization settings and demonstrate that employing an asymmetric parameterization can significantly enhance convergence, At last, we give some discussions on the relation between ScaledGD(A/PreccD and the proposed AGN method.
3.1 Spproximated-Gaus--eeee (AGN) method for LRMS
We unify the formulation of symmetric and asymmetric LRMS into a single, simplified expression:
(XX) | Q) -b12.
1
min XER
(6)
0 I
where P [I
0] Rax2n
E Ruax and I E Raxn is the identity matrix. The
U V
U U
case X corresponds to asymmetric matrix sensing, X
corresponds symmetric
matrix sensing with U R=x= and V R=xn The function (X) be further rewritten as (X)) = ( 12 where x(x) A(PXXTQQ Q) - b. For simplicity in notation, we denote
B(X, = A(PXY Q). By employing the Gauss-Newton framework as presented in Section 2.3 one can update the variable as X++1 = X, + (X(,) where
((X,) arg
| X,) B B(X,, X,) -122- min AERaaxd
However, as the Jacobian of the linear operator in the 12-norm of Eq. 7 tends to be singular in our overparameterized setting (d r). the Gauss-Newton method cannot be directly applied and one may consult for the Levenberg- evenberg-Maaquurrd method. In this work, however, unlike the Levenberg-Maruuard Marquardt method, we resolve the problem in Eq. (7) using the Gauss Seidel method, whose advantages over the -Maqquurrd method will be discussed in Section 3.3 Specifically, we update X, by
X2+; =x, + A(X,), A(X.) = arg min AERinxd 2 | X.) + B(X,,XX,, bl2..
X1+1 = Xx+3 + AX(X y), A(X = arg min AeRa of
|B ++ A) + B(X ++ X.
b1l2.
(8)
The sub-problems in Eq. g are quadratic minimization problems that can generally be solved very easily. In our matrix sensing problem, leveraging the RIP condition, we can approximate A (X,)) by
((X,) arg* min AERanxa
|B AB -.))
Á(X++)) arg
min Aedaaxd
マ 1I (+ A) - A' (x44)

---

where Xi), - PAX; Q and B(x A) = PX A ATQ, arg" denotes the minimum norm solution as
((X,) Pt A X,) b)Q X,(xxxXX7 XXXTQQ0 x,
(10)
(B(=) x -)] P +X (x
which is natural choice for degenerate least squares problem. f denotes the inverse, and p PT, Q = Q in our context. Then the AGN becomes
X 1+ = X, ,X()) X++1 = X - ,
++
(11)
The specifics of the AGN method are presented in Algorithm T in Appendix. We demonstrate that the solution in Eq. (10) renders the AGN in Eq. (II) with a constant step-size 1 > 0 as a descent method.
Lemma 1. Descent lemma) For asymmetric matrix sensing. as long as < 1) < 2/ + 8) and the Assumption is satisfied, then there exists positive constant = (2n - (1 + 8)n²)/2 such that
v( < - (()B((( Xt)1 ((X++1) (Xx++)))+)))))))))x E|I 4 Á(X ())II
(12)
Lemma suggests that AGN with constant step-size is indeed a descent method for the overparame- terized LRMS. In Section we will prove that AGN converges globally at Q-linear rate.
The AGN method can be used not only for asymmetric MS but also for symmetric MS, as Eq. (6) offers a unified formulation for MS. While the application of AGN on symmetric MS will differ slightly from the asymmetric case.
3.2 Symmetric matrix sensing
Now we consider symmetric matrix sensing, which special case of model (6) and the matrix M E R=*= is symmetric positive semi-definite (PSD). There are two different ways to deal with the symmetric case, depending on whether we constrain E C (symmetrie parameterization) where
U
C= Z
U Raxd
c2aad
X
R 2nxd (asymmetric parameterization).
U
Setting 1: Symmetric parameterization. this case, the optimization variable E C such that
B X, , X = A(UUT) for matrix U E Raxd and B(A, Xi) = [B(X,, A)] thus the subproblems in Eq. 9 become
((x)) = arg min ; DEC 2 ((A (B(X,, b)ll
(13)
where X, E C. The optimal solution to the problem in Eq.
13 is provided by the following lemma.
Lemma 2. Let Á(X.) be the optimal solution of problem then the optimal solution of problem (P(XX)
130 is ((X,) P)(X.)
However, we find that if we constrain the search space to C and use the update ((X,), the AGN with a constant step-size 1) may not qualify as a descent method for our over-parameterized LRMS.
U;
Specifically, let X,+1 Xx 7å(X),, where Xz, Á(X,) C and assume X,
we have
U.
((++1)) 2 || X,) n ((X,)) ( (x), B((()) ((X,)) - bl T 7²² (B X.) B A(X)))
1
-(())) + (10)++1111111 -,1111(X,, ( n|I
| | A(X,))
X.). (B)
(14)
'The specific update is provided in Appendix Eq.
3
Eq.
32
and Eq.
33
5

---

IB < ||& are all bounded Note that the term | A I (1+ and are closely related to (X),, and & = (A(UU)) - b). While the higher-order term w.r.t. (Xx,)
( || U.) - & I
(15)
2 (1 (1- (1-
(U, U.) (U, &
can be extremely large such that (xx++1)) 2 (X.). as (E, [|
- ||&|1| is bounded
while Ug U2 tends to be singular in the over ever-parametrizer case. Therefore, one cannot guarantee that the AGN method decreases with a constant step-size 17. as illustrated by Fig. 3 AGN in Section o
How should we approach the symmetric matrix sensing problem using AGN? One possible strategy
is to relax the constraint X E C to a larger search space X E R2nx
Setting 2: Asymmetric parameterization. Despite M being symmetric PSD matrix, one still consider problem (6) with E TR. 2nd instead of X E C. Denote by X and X the optimal solution with X E 2 and X E C respectively, then is easy to verify that PX X Q = PX: x Q for symmetric matrix sensing. Therefore, one can readily apply AGN using Algorithm to solve problem (6) with M being a symmetric PSD matrix. We will achieve the same convergence guarantee as in the case of asymmetric matrix sensing.
Remark 1. The symmetric MS discussed in setting I is specific instance of problem (6). involving significantly fewer intrinsic variables compared to the asymmetric case discussed in setting 2, the search space C resides in lower dimensional subspace of R2axd Meanwhile, one can also explore the optimal solution for the symmetric MS within the expanded space TR. 2n while maintaining the same minimum objective function value, as demonstrated in setting 2. These two approaches lead to significantly different optimization paths. From the above analysis, it is evident that different optimization paths demonstrate distinet decreasing properties in our problem. If we confine the optimization variable to C, then the AGN with a constant step-size may not function as a descent method If we extend the optimization variable to the entire IR 22ix we have a larger search space from which we can find a solution path that guarantees a significant decrease in the objective function. In Section we will prove that in this case, AGN converges Q-linearly fast. These observations suggest that expanding the search space for a given optimization problem can lead to more efficient methods.
parammeeattee LRMS
3.3 Comparisons with related works
Of particular relevance to this work are ScaledGD(A) (2] and PrecGD [15,, which focus on over- parameterized symmetric low-rank matrix sensing. While these preconditioned gradient descent methods are not easily applicable to the general asymmetric matrix sensing problem, as we will discuss in the appendix Section A.1.3 In this section, we demonstrate that these preconditioned gradient descent methods are instances of the Levenberg-Marquuee method for singular least square problems) applied to the symmetric low-rank matrix sensing problem. However, the Levenberg Maraqurrd method is a more general approach than the preconditioned gradient descent method, particularly for nonlinear least square problems.
method (specifically, the Gauss-Newton
Since ScaledGD(A) 21 and PrecGD [55 consider ever-parameterized symmetric matrix sens- ing, we constraint X C where C is defined in Section 3.2] It can be easily verified that the ScaledGDD()/ProoGDD for problem (6) corresponds to
(X,, A), X = X, 11--7(( 7)(())))))))
Á(X.,A) arg min 1 |B X.) (B X.) b)]l + A
(16)
1
AEC 2
It is apparent from Eq. 16) that À constrains the magnitude of the update A(X,, A) to be small
compared to Eq. (13 thus ensuring that the preconditioned gradient descent method exhibits
monotonically decreasing behavior, analyzed in 44 and 21 The Lemma 6 in 42 ensures that PrecGD is descent method, as summarized by the following corollary
*One can employ line search algorithm to ensure the decrease in the objective function value. Nevertheless, line search will down the convergence and is not the primary focus of this paper.

---

Corollary 1. For symmetric matrix sensing, there exists positive constant fx.x such that as long as < 17 S 2/8x,0 the iteration given by Eq. (6) satisfies
xx.A
(X(+11 - (X.)
A),
(17)
[1B(A((+AA)xx))1 27 mmin Xi)+A
where xx,x= = (1 + +0) 4+ Mil X(x
Omin X +
Similar to the Lemma I of our AGN method, the value [ X. plays very important role for the convergence of ScaledGiD(A/PrreGGD While we observe that the parameter À can notably impede the progress of ScaledGGDDA)/PrecGGG)) in escaping the saddle point, as illustrated in Fig. and discussed in Section []] In Section we will prove that when X, is g-close to the saddle points, [I8(Á(X,, A), x.) 2 will be as small as o(e), which explains why ScaledGD(A/PPrecGD converges slowly near saddle points. While in contrast, even if X, E-close to the saddle points, the value (X))), I in Eq. (2) is almost independent of c, thus, saddle points cannot impede the convergence of the AGN method, which is also demonstrated in the left subfigure of Fig.
4 Saddle point analysis on the population risk
Saddle points are special critical points in non-convex optimization problem, contributing significantly to the global convergence analysis of gradient-based algorithms in non-convex optimization. Past researches [8] has demonstrated that gradient descent may encounter difficulties in navigating away from saddle points, while our empirical findings in Section demonstrate that the proposed AGN does not experience slowdowns caused by saddle points. Therefore, it's quite intriguing and crucial to understand the behaviors of gradient descent and AGN in the vicinity of saddle points. To this end, we study the saddle points of the population risk of the problem (6).
The population rish associated with the objective function in Eq. (6) corresponds to the following non-convex matrix factorization problem:
min X
- 1IXXX MI
(18)
The objective function corresponds to g(U, +IUVT= M U E Raxd, V E Raxd which plays very important role in the saddle point analysis of Eq. (6. The saddle point of the non-convex objective gUU V) is denoted by (U,, V.) E S. where the set S is defined as follows:
S (UU,, V.JUUV +MMEN M TEVT .M 22/3),
(19)
where M = ΦΣΦ T is the SVD of the matrix M and & E TRax W E Raxr, E Rexr, MR is the set of mask operato and J the identity operator.
Note that the gradient norm ggll is intricately linked to the reduction of the objective function for gradient descent method. In our approach, the values ((x,) Eq. 12.. which correspond to VV) 112 and (U) respectively, are directly tied to the reduction observed in the AGN method. Correspondingly for symmetric matrix sensing, the values [| A), X,) 13. in Eq. (7), which corresponds to VVug(UT U + A/) 113 is related the reduction of the non-convex objective by SclaedGI (2 and PrecGD 15). Now, we present the following theorem to describe the behavior of gradient descent,
and |)8(X,, Á(X,)) || in
and AGN in the vicinity of saddle points, by quantifying the values associated with their reductions in objective functions. For simplicity, we consider here rank(M) =
Ve, is at the vicinity of the saddle point (U,, Vz) E S and e is sufficiently small, N,, and N₂ are random Gaussian matrices that follow a standard normal distribution. Then with high probability we have the following results
Theorem 1. Assume that M is rank-1, the point (Ü, V) with t U. eN V
(GD)
V o(s)e, (a)e,+ool o(E2),
(20)
'The population risk of problem 6 corresponds m + xo in Eq. and Eq. 6
7 .M():: : xr gr is mask operator which maps the element Xt., of its input X into Xi.j.
7

---

= + + + o(E2)
(AGN)
(21)
(
where eg = |U,V M Furthermore, by constraining M to be positive semi-definite and U -=V, V. U, =-V,
V, (for symmetric matrix sensing), for bounded constant O, we have
VV ( Ü + A1) = (
(ScaledGD(A)
22// + o(s²).
(22)
Theorem I indicates that when the opti- mization variable (t", V) is e-close to the saddle point of the non-convex objective function g(,, V), the norm of the gradi- ent ? at (Ū, V) becomes as small as o(e). Hence, the convergence of gradient descent will be relatively slow, as shown in Fig. 2 Moreover, in Eq. (22). the value of X/e is typically much larger than e. Consequently, the reduction achieved by ScaledGD(A//PeeGDD for symmetric ma- trix sensing is nearly identical to that gradient descent ((E). In contrast, even if (Ū, V) is E-close to the saddle point, the reduction in the non-convex objective achieved by AGN in Eq. (21] is as sigmificant as e (1)e,, + o(E), where (1)e,, is larger than and is not dependent on thus ensuring that AGN achieves a substantial decrease the objective function near the saddle points. We also plot the gradient norm of GD, PrecGD) and AGN in Fig. for solving problem (6). It can be seen from Fig. that the gradient norm of AGN decreases linearly zero. While the gradient norm of PrecGD suffers from ups and downs before it is smaller than about x 10-7. This indicates that PrecGD is attracted to saddle points but can quickly escape, depending on the value of X as per Eq. 22 It becomes more challenging for GD to quickly escape all saddle points, which is due to Eq. 220p. As shown in Fig. I GD's iterations encounter multiple saddle points before reaching the global minimum.
20"
10
Gradent norm
20
ACBY 100
10
CD 10
GDD yt 1101
10
PrweltD
Prex x
10
1000 1500
2000
100
400
500
Figure 1: Illustration of the gradient norm for GD, PrecGD, and the proposed AGN, with the right subfig- ure showing a zoomed-in in region of the left for iterations from 100 to 500.
5
Global convergence analysis
We first recall the celebrated Restricted Isometry Property (RIP) 43 assumptions on the restricted isometry constant and the initialization of the variable Xo-
then we make some mild
5.1 Assumptions and main result
Assumption 1. The operator A(-) satisfies the rank-r + RIP with constant 8,41 8 for sufficiently small 6.
Assumption 2. Let Xu 2 be random Gaussian with elements sampled from N ()) with ca Ella/nnfor for small and the step size 0 < 2/ 8).
Now we present our main result, which characterizes the global Q-linear convergence of the proposed AGN for the werrparamettriized non-convex, low-rank matrix sensing problem.
Let 1/5" be the global minimal value of (xX) in Eq. (6) and X,, Vt > 0 is generated by Algorithm then there exists constants 1 2 t > 0 such that
Theorem (Global Q-linear convergence). Under the Assumption Aand Assumption
((X++1) - S S (X.) b0
0,
(23)
where cq (1- (7787 < and ė 2n - (1 + 8) Meanwhile, if 0, = 1, cg becomes
Theorem 2 ecchoes the observation in the left subfigure of Fig. 2 that AGN converges rapidly from random initialization and does not become trapped in saddle regions. The convergence result of AGN differs significantly from existing methods like ScaledGD()) 21. PrecGD [15] and GD [19 20
both empirically and thcoretically. In the next section, will present the sketch of our proof.

---

5.2 Proof sketch
The global Q-linear convergence of the AGN method relies on two conditions: monotonically decreasing (Temma[]) and decrease dominant (Lemma 3). The monotonically decreasing condition ensures that the objective function decreases in each iteration, while the decrease dominant condition guarantees that the decrease in the function value significantly larger than the distance between the current function value and the global minimum.
Lemma 3 (Decrease dominant). Under Assumption 7 2 2 let X, be updated by AGN method in Algorithu | then there exist T Tī and constant with max( T/) 2 ( 78) 2 7>> and for constant 8 >
0, 1 > 8, > Osuuch that
1 dc
[8(((X))) X.I
1+ T (xx,) - +1',,
(24)
1 - dc + x11((x++)) =,"
18 A(X 1+ D)
1 1+
where ((X)) and ((x++)) is from Eq.
10
Note that the linear operator A(-) and the 12-norm is unitarily invariant, therefore for simplicity we consider M to be a diagonal matrix Σ E IR"x" with r nonzero elements on the diagonal. Specifically one can simply write Σ + My where M ΦΣV is the SVD of matrix M, as analyzed
Up
in 18 and 20
Let X, =
then [I8()(X)), x.I (A E)) || and V
correspondingly (X,)) 30- ||A.U.. 1 According to the following Lemma and the RIP condition in Definition to guarantee the inequality in Eq. (4). we need to ensure that [(U.V VVVV 2 Ti &.,.
- E| as presented by Lemma
Lemma 4. Assume that the operator A(-) satisfies the RIP condition in Definition I and Assumption
with constant 8, for any U, V E Baxdd E nx and Z E BRxx, then we have that
ALUVT E) -1- (.VV -)
(25)
for some 0 < 6e 11
Lemma 5. Under Assumptions 7 Jnnd if Xx, Vt 0 is generated by the AGN method in Algorithm
U,
1 and let Xt
then there exist constant
T/. oi with max 7/} 2 muintr,rte 2 >>> 0
Vi
such that
I((UVV] - Σ)и | 2 V.VV =1 I[VVU - DJU++ リ اا 2 U0 V, EI
(26)
Theorem can be proven readily by combining all of these lemmas. Please refer to the Appendix for a more detailed proof.
6 Numerical experiments
In this section, we conduct experiments to demonstrate the effectiveness of the proposed AGN method for solving the over-parameterized non-convex matrix sensing problem. We set the ground truth matrix M = U' with U* E x V* E gaxr random orthogonal matrices and Σ is a diagonal matrix with condi- tion number We set and the number of sensing matrices m = 50nr. All experiments were conducted using MAT- LAB on a MacBook Pro with a 2.4 GHz quad- core Intel Core i5 CPU and 8 GB of memory.
Syddile Regorns
12
Relitve ontr
20*
Inear conoregence
PowflD
20
AGR
AG28 x 1BC
GDD
100, r 5, d = 3r
beration
Iteraion
Figure 2: Comparison of convergence for PrecGD, GD, and AGN across various condition numbers, with the right subfigure extending the left by iterat- ing from 300 1000.
Comparison with representative methods. We compare AGN with GD (20] and PrecGD [15] asymmetric wer-parameterized matrix sensing.

---

All the competing methods are initialized with random Gaussian matrix with zero mean the variance 1/n. We plot the training curves of the competing methods in Fig. 2 where the relative error is defined by ||UGV, M / /|| ||.. GD's slow convergence is evident it struggles escape saddle points, as shown in the saddle regions of Fig. 2 Meanwhile, GD's final convergence rate depends on the condition number k. Fig. further shows that PrecGD's s final convergence rate is independent of k, though it still progresses slowly in saddle regions. In contrast, the relative error of AGN decreases rapidly, and its convergence remains unaffected by saddle points, consistent with Theorem 2
Meanwhile, we compare the computational time of GD (20). PrecGD [15), ScaledGI(AA) [21], and the proposed AGN on matrices of varying dimensions n X under different condition num- ber K in Table It can be seen from Table that AGN is significantly faster than the competing methods, particularly PrecGD and (ca)edGD(A), while vanilla gradient descent converges much more slowly.
Table 2: Comparison of computational time for methods on matrices with varying dimensions n, measured in seconds. Here, a+ indicates time significantly exceeds a seconds.
Algorithm
X
500
500
10
K 50
10
K 50
GD 220
500+
500+
5000+
5000+
PreeGiD L5
87.12
94.53
1979.45
1921.83
ScaledGDDA1211
55.87
69.07
1218.83
1258.71
AGN((
27.24
25.52
617.58
632.24
Asymmerric vs. symmetric parameterization of the symmetric MS. We also conduct experiments to illustrate the differences between symmetric and asymmetric parameterization in symmetric matrix sensing, as discussed in subsection 3.2 As
analyzed in section 3.2 setting 1, the matrix U," Ue tends be singular in over-parameterized matrix A(X,)) II2 to become extremely large, leading to (xx++1) 2 (Xx)). as shown in Eq. (14). Thus, we cannot guarantee that AGN in symmetric parameterization is reliable descent method, as demonstrated by AGNaym in Fig. 3 However, with asymmetric parameterization, as outlined in subsection 3.2 setting 2, we can ensure the linear convergence of the AGN method,
sensing, causing
also illustrated by AGi asym in Fig. 3
Conclusion
In this paper, we present an approximated Gauss-Newton (AGN) method for overparameterized non-convex low-rank matrix sensing problem. We demonstrate the close relation- ship between existing methods like ScaledGD(A) and PrecGD, method, which is a variant of the Gauss-Newtor method. Through saddle point analysis, partially explain why gradient descent, Scaled(AWPreeGGD may be slowed down by saddle points, whereas the proposed AGN achieves fast convergence. Finally, we prove that the proposed AGN achieves Q-linear convergence from random Gauss initial- ization for the non-convex optimization problem. Our findings highlight the efficacy of (approximate) second-order methods in non-convex optimization, particularly for structured problems like non-convex matrix sensing. Moreover, our results can be extended to more complex challenges, such as optimizing deep neural networks.
AGN, R= 100
AGN 100
and the
10
Relativ
10
50
100
150
200
Iteration count
Figure 3: Convergence of AGN un- der Sym. and Asym. parameteriza- tion of symmetric LRMS.
Limitations: While the AGN method converges quickly and is efficient for low-rank matrix sensing problems, it may be less effective than gradient descent for general problems without low-rank structure due to the need to solve a least-squares problem for the Gauss-Newton direction. Future work will explore approximate methods, like the conjugate gradient, address this. Additionally, our current saddle point analysis focuses on simple non-convex LRMS case with zero RIP constant, which we will generalize more complex scenarios with larger RIP constants.
Acknowledgements
This research was supported by the National Key R&D Program of China 4022YFA1004100 the China NSFC projects under grant 62372359, 12226004, 62272375, the Research Center for Intelligent Operations Research and RGC Senior Research Fellow Scheme No. SRFS2223-5S02, and the Macao Science and Technology Development Fund under Grant 061/2020/A2.
10

---

References
[1] Chih-Fan Chen, Chia-Po Wei, and Yu-Chiang Frank Wang. Low-rank matrix recovery with structural incoherence for robust face recognition. In 2012 IEEE conference on computer vision and pattern recognition, pages 2618-2625. IEEE, 2012.
[2] Dohyung Park, Anastasios Kyrillidis, Constantine Carmanis, and Sujay Sanghavi. Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach. In Artificial Intelligence and Statistics, pages 65 74. PMLR, 2017.
[3] Emmanuel J Candes. The restricted isometry property and its implications for compressed sensing. Comptes rendus. Mathematique, 346(9-10))589 592, 2008
[4] Shuangjiang Li and Hairong Qi. A Douglas-Rachfort splitting approach to compressed sensing image recovery using low-rank regularization. IEEE Transactions on Image Processing, 24(11); 4240-4249, 2015.
[5] Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions Signal Processing, 67(20):5239-577) 2019.
[6] Vasileios Charisopoulos, Yudong Chen, Damek Davis, Mateo Díaz, Lijun Ding, and Dmitriy Drusvyatskiy. Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence. Foundations of Computational Mathemattics, (1); 505-5553,, 2021.
[7] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, pages 7413-7424, 2019.
[8] Jikai Jin, Zhiyuan Li, Kaifeng Lyu, Simon Shaolei Du, and Jason D Lee. Understanding incre- mental learning of gradient descent: A fine-grained analysis of matrix sensing. In International Conference on Machine Learning, pages 15238.15238. PMLR, 2023.
[9] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over- parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning T'heory, pages 2-47. PMLR, 2018.
[10] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019.
[11] Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homoge- neous models: Layers are automatically balanced. In Advances in neural information processing systems, pages 382-393, 2018
[12] Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pages 1233-1242. PMLR, 2017.
[13] Zhihui Zhu, Qiuwei Li, Gongguo Tang, and Michael B Wakin. The global optimization geometry of low-rank matrix optimization. IEEE Transactions on Information Theory, 67(2):1308-133) 2021.
[14] Xingguo Li, Junwei Lu, Raman Arora, Jarvis Haupt, Han Liu, Zhaoran Wang, and Tuo Zhao. Symmetry, saddle points, and global optimization landscape of nonconvex matrix factorization. IEEE Transactions on Information Theory, 65(6):3489-333 3514, 2019.
[15] Jialun Zhang, Salar Fattahi, and Richard Y Zhang. Preconditioned gradient descent for over- parameterized nonconvex matrix factorization. Advances in Neural Information Processing Systems, 34:5985-599 5996, 2021.
[16] Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Stebro. Global optimality of local search for low rank matrix recovery. In Advances in Neural Information Processing Systems, pages 3888, 2016.

---

[17] Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht. Low-rank solutions of linear matrix equations via procrustes flow. In International Conference on Machine Learning, pages 964-973. PMLR, 2016.
[18] Tian Ye and Simon S Du. Global convergence of gradient descent for asymmetric low-rank matrix factorization. In Advances in Neural Information Processing Systems, pages 1429-1439, 2021.
[19] Dominik Stöger and Mahdi Soltanolkotabi. Small random initialization akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction. Advances in Neural Information Processing Systems, 34:23831-23843, 2021.
[20] Nuoya Xiong, Lijun Ding, and Simon Shaolei Du. How preeeerraettiinnoo slows down gradient descent matrix sensing: The curses of symmetry and initialization. In The Twelfth International Conference on Learning Representations, 2023.
[21] Xingyu Xu, Yandi Shen, Yuejie Chi, and Cong Ma. The power of preconditioning in overpa- rameterized low-rank matrix sensing. In International Conference on Machine Learning, pages 38611-38653 PMLR, 2023.
[22] Xin Liu, Zaiwen Wen, and Yin Zhang. An efficient Gauss-Newton algorithm for symmetric low-rank product matrix approximations, SIAM Journal on Optimization, 25(3):1571-1608 2015.
[23] Pini Zilber and Boaz Nadler. Gnmr: A provable one- line algorithm for low rank matrix recovery. SIAM journal on mathematics of data science, 4(2):909 934, 2022.
[24] Man-Chung Yue, Zirui Zhou, and Anthony Man-Cho So. On the quadratic convergence of the cubic regularization method under a local error bound condition. SIAM Journal Optimization, 29(1):904 932, 2019.
[25] Kiryung Lee and Dominik Stöger. Randomly initialized alternating least squares: Fast con- vergence for matrix sensing. SIAM Journal on Mathematics of Data Science, 5(3):774-799, 2023.
[26] Jared Tanner and Ke Wei. Low rank matrix completion by alternating steepest descent methods. Applied and Computational Harmonic Analysis, 40(2):417-429, 2016.
[27] Tian Tong, Cong Ma, and Yuejie Chi. Accelcrating ill-conditioned low-rank matrix estimation via scaled gradient descent. Journal of Machine Learning Research, 22(150)) 2021.
[28] Xixi Jia, Hailin Wang, Jiangjun Peng, Xiangehu Feng, and Deyu Meng. Preconditioning matters: Fast global convergence of non-convex matrix factorization via scaled gradient descent. In Advances in Neural Information Processing Systems, volume 36, 2023.
[29] Richard Y Zhang. Sharp global guarantees for nonconvex low-rank matrix recovery in the overparameterized regime. arXiv preprint arXiv:2 104. 10790, 2021.
[30] Jianhao Ma and Salar Fattahi. Global convergence of sub- aub-gradient method for robust matrix recovery: Small initialization, noisy measurements, and preeeerratttiiiaatonnn Journal of Machine Learning Research, 24(96):1-84, 2023.
[31] Lijun Ding, Liwei Jiang, Yudong Chen, Qing Qu, and Zhihui Zhu. Rank overspecified robust matrix recovery: Subgradient method and exact recovery. Advances in Neural Information Processing Systems. 34:26767-26777 2021.
[32] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overpa- rameterized neural networks, going beyond two layers. In Advances in Neural Information Processing Systems, pages 6158 6158-6169, 2019.
[33] Cong Fang, Jason Lee, Pengkun Yang, and Tong Zhang. Modeling from features: mean-field framework for over-parameterized deep neural networks. In Conference on learning theory, pages 1887-1936. PMLR, 2021.
12

---

[34] Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. International conference on machine learning, pages 4433 1433-441. PMLR, 2018.
[35] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine learning, 109:467-492, 2020.
[36] Kelly Geyer, Anastasios Kyrillidiss and Amir Kalev. Low-rank regularization and solution uniqueness in over-poereee par-eeterateeeed matrix sensing. In International Conference on Artificial Intelligence and Statistics, pages 930-940. PMLR, 2020.
[37] Samet Oymak and Mahdi Soltanolkotabi. Overparameterrize nonlinear learning: Gradient descent takes the shortest path? In International Conference on Machine Learning, pages 4951-4960. PMLR, 2019.
[38] Mahdi Soltanolkotabi, Adel Javanmard, and Jason Lee. Theoretical insights into the op- timization landscape of over- vve-pparameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-76)) 2018.
[39] Richard Zhang. Improved global guarantees for the nonconvex burer- monteiro factorization via rank overparaamtterization.. arXiv preprint 2200:2207701788. 2022.
[40] K Adithya Apuroop. riemannian geometry for low-rank matrix completion. arXiv preprint arXiv: 2012.
[41] Serge Gratton, Amos S Lawless, and Nancy K Nichols. Approximate Gauss-Newton methods for nonlinear least squares problems. SIAM Journal on Optimization, 18(1):106 132, 2007.
[42] Gavin Zhang, Salar Fattahi, and Richard Y Zhang. Preconditioned gradient descent for over- parameterized nonconvex moner-oonteiro factorization with global optimality certification. Journal of Machine Learning Research, 24(163):1-55, 2023.
[43] Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471-501, 2010.
[44] Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
13

---

A Appendix supplemental material
A.1 Preliminaries and more details
A.1.1
The definition of RIP
Definition 1 (Restricted Isometry Property). The linear operator A(-) is said to satisfy rank-r RIP with constant 6, E [0. 1) if for all matrices M of rank at most r the following condition holds
(1 - M.) S (IA(M) S 2 (1+
(27)
A.1.2 The main AGN algorithm
Algorithm 1: AGN for matrix sensing
Data: A(-), b, r and the random Gauss initialization Xo, =
Result: The estimated solution X and the low-rank matrix MT = PXX while nof end do
t = 1;
Update the approximated Gauss-Newton direction by Eq. Update X, and X 1 by Eq. 11I;
10
end
A.1.3 ScaledGD(A/PreeD for LRMS problem (6
Directly applying the ScaledGD(A/PrecGD methods in 21 and 15 will lead the following iterative update
respectively to problem (6)
X X2 - V X, + X,1)
(28)
Up
where A can be either constant or time-varying. Note that in our LRMS problem (6). X,
V1
therefore the update in Eq.
28
becomes
U U. A(U,V, E)V, U. +
(29)
and
Vi+1 = 1--AAAAAUU,V - UU +
(30)
which leads to quite different method compared to our AGN with iterations in U, and Vi given by the following Eq. (32) and Eq. (33). Meanwhile, as shown in Fig. 4 using Eq. (28) for our LRMS (denoted by PrecGD) results in slower convergence compared to our AGN method, and moreover the convergence rate dependent on the condition number of M x(M). In contrast, the proposed AGN converges very quickly, and its convergence rate is independent of the condition number K( M).
A.1.4 Some detailed derivations.
Before presenting the proof, we first provide additional details regarding the update described in Eq. 11) Specifically, let X, =
U; Vi
Ü with U, = and V
V. K,
where Ú., V E B and
Jr
Σr
0
Jr, Ke E xn-r))dd Since E =
with E, E R Thus, the update in Eq. 11 can be 0
suceinctly expressed as
U1+1
U V4+1
X 14 x,-=x,-nAn x,xX,nAA ((()) =
X X - n)((x+4))= Vi
(31)
7
with U2+1 and Ve+1 given by
U141 U, mA* A(U.V. -E),(V.TT va)
(32)
14

---

100
PrecGD 10
Relative error
10
PrecGD
AGN 10
AGN K 50
10
10:15
0
500
1000
1500
2000
Iteration count
Figure 4: Convergence of AGN and the method by using Eq. with different condition numbers on matrix M.
28
(denoted by PrecGD) for LRMS
and
V4+1 = 1/2 1n---14-AA A(U:1V U
(33)
and correspondingly
Á(X,) [A -
(34)
3(X++4) |ATA(UGHIVT - Σ) Uni (
(35)
In consequence, we have
[B(A(X)), - A'UUVV VVV |B(( U AA E)).
(36)
and
UEL
(37)
Further more, we can reformulate U and V4+1
U2+1 = U. - 7A" - VVV VOJ
= U, n(u.V. - -V,, Vo) + AAANNU - EIGA
[0:
Σ, 0
(NTR++KTK.) K2
V.
= (1 (i-n) n1)
J.
+1
{0-
0
+ +n(11 AAA)
J.V.
Σ,
Ü.K
J,K,
1)
V
Kr
(CTV+KTTH
(38)
= -1-7) [
En (V.TV K, K.
+
(LiNT - Σ, U.K]] [J.VT
Vi
+ + A*
J.K,
Kg
and
V4+1 = V2 - -1A" A(U V.T - UETTUUUUUA
E,Ū U0+1 + JitsJett) "] '7
Vi
= (1-n)
+n
Kg
(39)
V2UTT - K,UT
V.J++1e+11
Ü Je+1]
+7(11 A*
K.J
15

---

We denote
Eu, EJ,
= (I (I-A-A)
J.V.
- Er
UKK
Vi
(1T + K2 (
KTT.),
(40)
J.V.
J.K.
[g]
and
Ev, EK.
ViU -2, Vide+10r11 KGU
U141] Jet1
(Diniee + +
(I-
(41)
KiJt+
Then it follows
U++1 = -1-1 n)Us + n (ve Vi V K2 Ki) nnEu.
(42)
similarly
V++1=
+ n22 (Uttz U0t1 + ((tadets) nEv. (L-n)V, 10-1=(1-ii)
(43)
and
J+-1 = [1 + n/,,,
(44)
K(+1= = (1- - nE
Now we give estimation of the norm of EU,, Ev. E., and EK. Note that
ACU,V - 2V vay
UA, - 2) AVV.V,
(45)
T.V.T Er U,K.
[A] [4]
J.V.
J.K
i=1
[A_]
where A, and A E RR*" A3 E (n) xn for all i i= 1, m. Thus we have A
Ev, (I AiAi) ([U,V, E, (,KT]) ViVV V, Aj,A V.VV V.VA.. V.)
(46)
where (;-A(() -I (4).)) and 1;A2(1)=>) (Af,-)44 Note that - AÇAi (L0,V, - E, (,KT]) V.VVV Vo)* S cz 0(c and for sufficiently small RIP constant d in Assumption 1 we can assume that
(47)
( VVVV VV(VVVVo)* vo)tll S Co2 |
(48)
where c, > 1 and C52 is constant, thus we know that the upper bound of Ev, lla is monotonically decreasing. The same results hold for Ev. Meanwhile, we have
) V3)¹ + Ai (LU,V, - E, (,KT]) V.(V. where A;;A(-) Σm (4 A3 and A+) Em= (A). A4.
E,. = (1 (JV,) VVVV
(49)
Under the Assumption ! for sufficiently small å and the RIP condition, we can assume that co, Wellle
- (AV (V Vo) V
for ca, I 1. Meanwhile we have
A2 (LOVT - Ex, (.KT)) V.CV. (.) < le> Ai (LÜVV - Er (xKT]) llr (50)
S Scyeed edl.
for constants Cā es > O, the first inequality is due to Lemma and e, = IAAAAUUVVT -E]lr-
Therefore we can guarantee that
|141l P S (1 - + cs, [1 + nostte,
S (1- - -3) + cs. E(1 () -i)e
(51)
==
16

---

where co2 my can be seen as small perturbation. Similarly, we have
K4talle $ (1 - + ca, 7) Kell + 7esptet
S (1 -8 Ko || + cba " Σ
(1-1((11 - -))----
(52)
1=
On the other hand we have
[6 V. (1 (1-1)
E,V, (v.
+ KT (.TKK) )i)
[V. K, +n
[VTTKK]]
Jt
0
(53)
Evi [VTKK,]
+ P.j.
which indicates that
U+IViT - E- (1- (11)))((i -
E,) + n Uees (Utti + Jitsdet)) ) Uit1 1 Er
1
+ +nüe+1EV + (1- n)m2ir
1/. (vi KJ k.) Vo
VT--1 -1 + (1 -nnnbbb Vo..
(54)
A.2
Proofs of the lemmas
A.2.1
Proof of Lemma
Proof. According to Eq.
we know that
1 (xx ( 2
B3 ( X bll
|1((x,, Xe) (,, ((x,)) - - - -b11
2
(55)
2 (111( X,) (B(X,, x,) b)1l
1
n - -
[B( Xi) b12
bb.
2
Note that
xx) X.).
= (I(A(X))XXIIE
(56)
and
|B(A(X.), x.) < el ((),) X.II where e - ||A11/3 (1 8) which due the RIP condition. Thus we have
(57)
(X (x))) 2n (1 8)m (()()))
(58)
Similarly, we can prove that
2n (1+ 8)7
(Xx+1) S (X(+4)
|B(X A(X
(59)
Therefore finish proof.
A.2.2 Proof of the Lemma 2
Proof. Note that the optimal solution Eq.
13 satisfies
7
T
PAX, QTTQQQTA x,
(B( x, 0,4 E CC
(60)
0
0
17

---

While the solution of Eq.
9 is
1
((x)) [
A" (B(X,, X.) bbQ" x QQ x,
(61)
which satisfies
! PAX, QQ x,
T [
A (B(XXX, X,) - bbQQ X. =
(62)
is easy to verify that the matrix Á(X,) = ()( PA(X.)
satisfies Eq. (60). thus it the solution of
the problem
A.2.3 Proof of the Lemma 3
Before proving the Lemma that of V as
first define the angle between the column space of VUT E and
coso, |1(VV E>VVile
(63)
NUVT-
and similarly
cosê,, I(VUT -2jUU
(64)
LUVT- Σ||r
where i stands for the inverse. We note that the cosê, in Eq. 63
and Eq.
64
are well
defined and are equivalent the following values.
Proposition 1. For any U, V Raxd and E Raxx, the cosO, and coso,,, in Eq. have the following equivalent formulations
63 and Eq. 64
-E,
cosê,
(65)
|||||==]
IUV - -
and
(VUT TOUT-EYYO -E,YUUI
cosê,
max ||||==1
(66)
|UVT
where Y _R
Now we present the proof of Lemma
Proof. Given the cosê, and coso, one can immediately writes
||UVT- - V) = cos0, cosO,,|UUVV | -ElFF,
(67)
and
I(VUT - - = cost,llUVV -ElF,
(68)
which indicate that the coso, and cosê., provide estimate to the vTi and / in Lemma with the Lemma Assumption T
Together
[nnd Definition [ we can establish that
( 2 (1 - 6.)IVVV >
(1
- 2 cos 20 (v(()) - 1
(69)
de
>
1 + 8
Similarly, we have
1 d
[ Á(X
+
1)
>
cos 20
20s20'th 10 ((((++3) -66
(70)
1 + 5
According to Lemma 5 we know that 20 2 n. and 20t 2 72, V1 and max max(Ti, 72) > Thus finish the proof.
18

---

A.2.4 Proof of the Lemma
We first prove the following lemma and the Lemma is natural result of the following lemma.
Lemma 6. If the sensing operator A(-) satisfies the RIP condition with constant 8, then we have the following result
A(x))( (1 -
(71)
where X,Y E Raxx and < 6, < 1.
Proof. We have the following inequality
A A(X)()] Σ (As, A)
max 1 r=
X)AX,
XA, ZX.
max
r=1
(72)
(A XA,,, 2XT
max
r=
m
(A.. XAA,,
min (A.) |
where the inequality ! is obtained by setting Z / and the last inequality is due to (A, B) 2 mmin Bl.. Then we obtain
vn
1
A(X)Y]=
2
min (A)]XY|I
(73)
Vn
With the help of the Theorem 2.7.5 in 44 cf Vn. Thus we have
we know that 3c > 0 with high probability amin (A:) >
m
o
(Ai) 2 mc² mc²/n3/2 //3/2
(74)
According to Lemma in (21) we know that if m 2 Cur 8 for sufficiently large universal constant C, then A(-) satisfies the RIP condition with constant Thus we obtain
170
Cet
min (A.) 2 me² 2/22 2
> (1 - -8))
(75)
82 /n
for some < de 1. We complete the proof by combining Eq.
73 and Eq.
75
19

---

A.2.5 Proof of the Lemma 5
Proof. Let Es = U.VV" - Σ, we have
cosO II(U.V. - VVVVV le IEVVVVV V2) V2) $11r
|
||Er|l
EVV. VV) VOJ 2,))
= max ||
|Eelle
(Ee, [V,
(V,
| Vo) 11==1
max
||
12 ====1
max
[UiT - Er J.V.
Ū,KT
V.V.T K,K," 22K,
J.K.
ZZV.
max Iz 1==1
(1 - E.] J.V.
[ J.K.
Zik.
+
Zzk,
(76)
max 1|2V," 1==1
|Edee
(10,E, - E,1. (2VT)
(OKKT2KK]
(J.VT, (T,TT
max |22V" 1==1
|EEB|F
||Edle
(IO.VT - ..V. + "AV.T.ZVV)
(O:K7. (O.KT.Z.KT) ZIKT)
max 12 1F=1
||Eg 1E
(10.CT - E VVV. + (J.VT. ,ZVTT
|10KK 1| ||
1 1|
12
max
l==1
||Ee|1
J.V. IE
(iill
IV
|Ell
|Eill
Similarly, we have
(V.UT - -x, (,,T) + (KUT,ZZU,))
J...V. l|F
cosO
1| |F
max 1207 ||==1
|
(77)
| (Ki)
|
To estimate the lower-bound of coso", and coset, according to Eq. 76) and Eq.
77 we can divide
the whole iterations into three stages based on the value of m (k)) and amin (J)).
Stage the first stage, there exists an iteration count Ti such that T (Kr;) Z Si and Jmin (Jr) 2 Çt. for small Çi > 0. Since A(-) satisfies the RIP condition with sufficiently small 8, we know that the EK, EJ, in Eq. (44p are akin to small perturbations. Therefore the minimum singular value of J, and K, are decreasing under the Assumption| 2 and one can guarantee that < Tı. Then the value Ç1 provides lower-bound for the values de?
Juin (K)) 2 Ç1 and mmin 2 <1. Vt
aç²
of casft' 2 T1 Foll and cosêt 2 T2 |FllFF for < Tí. Meanwhile, according to the update in Eq. (44) and the sufficiently small RIP constant E,, and Ek, can therefore be small enough such that miin (K₂) and amin (Ji) decrease almost linearly in stage I with Ti O(log 2 for very small (1.
Stage I: In the second stage, amin (K₂) < Ci and amin (J,) < S1, for T2 > 1 Ti for some T2, we can use the following inequalities to lower-bound the cosØ" and cosos.
- [V]] 2,0 + (K.UT. ZZU,) (KKUT.ZZU.T)
J... ||
coso"
2 11==1
max
|,, ||
|Z ||
(78)
20

---

[U.V.
-pp] LiVVV + ,JoVi",,2
1|Ü,K? IF |E
cos
max
1| K2 ||r
(79)
12
====1
|Elll
which come from Eq.
77 and Eq. (76)
By Lemma
7 we know that Jmin (Üs) > and min (V)) > 0, for t > T. Together with Eq.
78 and
Eq.
79 we have
[V,TT E, 1111=|1111 2,, |F + |KKUU, 1FlLZ J F
J.V.
|F
cosf'
(80)
|| ||
|F
where | 11 + J. + 1 11 =1
cos 2 | E, || V || + |J&V, |F IF
|0,K7 |
1| K2
(81)
|
||||
where
|2 |1 + 14 | + K ||3 = 1. The Eq.
(8 and Eq. 81
further imply that
V.ÚT Ex K.U,
||f
cos# 11 2 v 11-112 1z
(82)
E
and
T. V. 2r J.V.
||F
cos
1 1| 17:
1| Kel
(83)
|Eel
Meanwhile
|| | = | 1 + K, 11 + VU.V - E + IJ,KK 11
(84)
2 max V, T |.. | 11:} + max CI 11 I 12))
According to Eq. |1O00
51p Eq. 52) and Eq. 54 we know that ||0, - Σイ Z |J,K, 11 E / 2 1 1 which is true for random Gauss initialization with small value in
Assumption Thus, we have | s 2 [1 VTT 1B..111 ( + | - Σ, 12: and
D.V. Ex J.V. ||E
[.O, - K,U, |
||
||
max
2 V2/2.
(85)
Without loss of generality, assume || |K,K0, ||,, then consider Eq. 88 such that
cosO V 1 Krl
V2 2 KrZ
(86)
[| S 1/3, then we can guarantee that coso 2 1/3. Meanwhile, as Z K, || decreases, the lower bound of cosO', increases. Now we prove that in period T2, 2 K.llF S 1/3 and this period, the upper bound of || K2]l decreases monotonically.
Note that 2 min (2 < V T. 11 < 1, then || 1 S 1/0 (V). Moreover, according to Eq. (51) we know
| |l < (1 - 9) + cs w
(87)
for 3 < 1 and cs2 is related to the RIP condition 5 and can be sufficiently small. In consequence,
| || < (1 - |3) Koll //mi///mmmlll ( (V:) + Ca2 x /o (V)).
(88)
According to Lemma one guarantee that
2 K, || - t(1 K)lloo + two c.
(89)
21

---

Note that
/f I 7 E (1 1=
() o)et-s S con(1 - c)
(90)
for constant cp and by long as L > Ti The above inequality is due to that in stage the objective function decreases linearly such that e S c7(1 - (n)² for S Ti. Meanwhile, we can select Ç) in stage to be small with Ti = Ollog such that
1 K2 |F ((1 B) Koll teon(1 -c, < $1/3,
(91)
for T2 > > T1 for some Tz.
Stage III: Note that as long as || K2 || S 1/33, we can prove that the max mrax(cos0"". coso" in stage Il is lower-bounded by constant Ts 2 1/3, which guarantees that e decreases linearly in E [0, 72].
In consequence w. S <n7(1 - ", and
K || s t(1 - 3) KollFe, + to (1-(1-c)) cgy'
(92)
Now we prove that $ for all alll>>>>>> <>>>>>>>>>>> T2 such that max [ coso 2 1/3, by setting proper T2. It is easy to that is decreasing function when t > T for certain T,, As noted in stage II, we can set T2 > T such that
Z K7 IF Tu(1 |)oll T2con(1 1//3,
(93)
which is achievable by setting Ti to be large enough.
Together with all the three stages, we conclude that by setting 7?, Ti in Eq. 26 as coso and coso respectively, we have that the results in Eq. (26) hold for max(T) T(
A.2.6 Proof of the Lemma 7
Lemma 7. Suppose that the Assumption and Assumption holl. Let Ü. and V. be updated according to Eq. 442 and (43) Then, it follows that there exist constants Tn and To such that
o+(0,) 2 2./h, (v(V)) 2 8o/l.
(94)
Proof. Note that
= n) + n (V, K, K.T.K)) + +nE.
(95)
= (1- n)ū + nE (0:V.7) U.V. v. (V. K, K, k.) + nBu..
and
Ve+1 = (1 - v) + 7) U++1 (Utt20e41 + sende + nBv.
(96)
+ - (V,, Usz (UttaUeti + (etsdets) + nEv.
Therefore we have the upper-bound of the operator norm of Uet1 as
|1++1112 s (1 - 1)] + + (UA,T) lla |1 IIV V. (V.VV. Vi + KJ K. ll2 +nll Ees
s (1 + +1+- 1)) | + nll Ev, ll2 S (1 + nlre 1)) [10112 + nl Eu.llz
< (1 + 11+ - 1[(1 + 62)) | 22 + 1/ Fu, l12,
(97)
22

---

where 82 is due to the RIP condition in Assumption | and 82 < 1 is sufficiently small. Meanwhile
1 (D:VT) - 111 - [2, -.,V) (diV)) ll2
1 | U.V. 112/ (0mmi(UU (T
(98)
I Σr U.V, 1
E - Un 1| (1 (on)
CE
where og is due to Lemma (8). The last inequality is due to that long as m min ( (K2); miia (Ji) >
ç one can always guarantee that | Ü, V. || - (1 (11) Uo Therefore we have
for Se >
T2 - 11-11- O(,,),
(99)
with c 2 1. Together with Eq. 197 we obtain
||0e+11/2 s (1 + nec 11 ll2
n
(1 + ) (l + II (1 + ,((,,,")))oll
j=n
(100)
Σ (1+ n E Evo ll2 + II (1 + ,,
==
1=0
Cel Cy S cul
for constant CE, Cu, Cy. The inequality @ is due the monotonically decreasing of Er, 1l2, which
obtained from Eq. (47) and Eq. 48 The inequality b is due oT + necc, +) $ Cp for constant Cp. Similarly, one can guarantee that
|IVell S cut
(101)
for constant c.. In consequence, we obtain
o, S [1ú,l22 S cal, or (V)) S 11 S col.
(102)
According to Lemma 8 we know that the o, (Ū,V,) ce, together with Eq. 102) that
guarantee
(ú, 2
C
(v:)) 2 CE
(103)
tc,"
tc.'
where we use the fact or (ŪVT) $ |101]2o,(V), Let ē. = cc/ca and ē, = ce/cus we thus finish the proof.
A.2.7 Proof of the Lemma g
Lemma 8. Let Ün and Vt be updated according to Eq. 42 exist constants cę >> 0 such that
and Eq.
43
respectively. Then, there
(, 2 cE. > 0.
(104)
Proof. Note that
or d'HiillUT + Jean U E,) 2 (EL)),)),
(105)
Pet1
and
(2 Dest KIT Ketil VeTI) 2 (2(
(106)
Q+t1
23

---

According to Eq.
42 and Eq. 43 we have
U4t1 1 (1
Un U.VV + nUet1 (Uit20e+1 + Jot1) ) Utt2L,
+ +nuU++ F.v; + (1 n)TE (v: Vj + K2 k.) V.T + (1 - Pi, V.
i
= (1 1)) U00 + Σ (1- 1) P(+ P(-I-12 + 7(1 1) Σ (1 - 21 2,, Qu (107)
1=0
i=0
+ Σ (1 11) 2 U 1+1
1 F. + (1(1 - 71 Σ (1 11) 2$ Fur- V.T
2
Meanwhile
(x( 2 17
Σ (1 11--n)² 1) 21 0, (P1+1-12.) + 17(1 77 Σ 1) or (1) 1=0
(108)
The fact that or (P(z1) 2 or (P)) and or (Q(+1) 2 (Q)) gives to
o, (H) (o, (P)) + (1 n)) (Qn)) or (E,).
(109)
Moreover, according the RIP condition in Assumption the following inequalities hold
||uu V. 1l $ 12 VV.. Vo + Ko Ko) Vo 82ch
(110)
and
|lū++ Ey ll2 z 5211 U0Vo Ü.t1 [ Ueti J1+1 U Er 82c
(111)
for sufficiently small 82, and || S 2-1 82c
Since o= (1 2 < and 82 are very small, now we can lower bound the r-th singular value of Üz+1 V by
Ou 2 (H) (0,( ||
z nn, + (1 n)oo (Qo)) or (2i,) 0a (16V)) - 62( cy +
77 c 7)
(112)
which is simple result of the matrix perturbation theory and cg > 0 a universal constant.
A.3 Proofs of the theorems
A.3.1 Proof of the Theroem
Proof. Since M is rank one matrix, we have U, = E Raxd and V, 0 E Rnnx correspondingly
Ú= +NN =N,, V V, + EN, = =N..
(113)
Note that
V 11:
IIŪUT M)LI1B
= I[(.V. -M + +U.N + .N.V + + NU, +
ez
(114)
II(UUU] - -M+eZ)eNall -MJN
-IC(U.U-M))N++ =Z
o(()),+ +
24

---

Similarly we have VV | o(=)e, + + and therefore
|7l1 = |V 1 + VV 1 = o(s)e, + o(s
Meanwhile
V V) I1OV - MV
= -I(UAUU] M + EU, +ENUT + N N
(115)
-IINN, - CENNNN,NI ||NN, -ENNN I
Let VÊVT= N, be the SVD of N,N, then |M = = v' where M = =,,UV=+ is the SVD of the rank-1 M and V is the orthogonal basis of a random Gauss matrix No. then with high probability
have | || (1). As result, we obtain
Vic V) - e
(116)
Likewise, we have
Vgo (00
(117)
As for the symmetric matrix sensing, have
|V96 ( - I1òOT MUU + 21
-I(E2NNT M)NN(ENTT + -
(ANNT-M)s4L1 -I6e:NNTMM)SPN -M) 222 + 1B
-IMEBEN(E?EN + A1) - - -ENNNT N N - -
(118)
where N is random Gauss matrices that follows standard normal distribution and N = x V is the SVD of N. Note that
( 2 + AT) AT) t 1 = ofIleU*TTIN ( EN 2
(119)
=
where e a bounded constant which related the singular value of the matrix N, thus we have that
(
E² 2)
IV + P3-- o
+ o(E2).
(120)
52 -== N/C
Thus we finish our proof.
A.3.2 Proof of the Theorem 2
Proof. According Lemma
know that
vi s(X,) ((I(((())) 2.
(121)
v(X++1) < v (Xx++)) e||B - A(X I1,
where / -2n (1 + ) Together with Lemma 3 which shows
1-
()(((X))) x >
1 1+5 (X.) 3)
(122)
1
|8(x,,+ .+ Á(X 111 2
?1/0(( (X
+ 26*).
1
We arrived at
x(x+4)-- - (x,)))) - 30t - el (((((x)..)))))))))))))(()))))( xOI12
(1 (T] 1- - 8
(123)
1 |[,( -1
25

---

and
((X++1) - 30- (x(x+)) - -0- -eIB(Xx+ + A(X
5
(124)
- (1 - iTi
)1((((+)) - 47
1 + 5
Thus we hvve
(((++1) - 1²a S LT! 1 8
(1 - 1Tt 1 1-
[(b()))) - 4M
1+ 8
1+
(125)
- 8
$ (1 87
[b)())) - +,
8
where 7 = m r?) >
Meanwhile, if the RIP constant ò = 0. which means the number of the sampling m oc and A(-)
becomes the identity operator, one can set v = We know from the Eq. (32) and Eq. (33) that
1 ((x+1) - 30 2
11 - 2 II A.MUU++UUt 1
(126)
At the same time
U2 MVV..
(127)
Thus M U441 M, which indicates that
1
(X++1) - - |1 1+1 M
2
2
1
AM U2+1 U/ M 17,
(128)
01SIINTTUU 12:).
-0f)(X,) -x -1
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
27

---

Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
28

---

reproducible, they Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
public/guides http///oeaeaiiiiiinnonoooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
/ //nips http::ccpplllliggiiieeee httg///ddde/CodSubmmim seriissssonpoiioio
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper is theoretical and aims to prove the global Q-linear convergence the proposed AGN method for non-convex overparameterized low-rank matrix sensing. All the details of the code for the experimental results in the figures are provided in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
30

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
31

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "s5m7yD6wKa", "reviewer": "Reviewer_KSmV", "summary": "In this submission, the authors proposed an approximated Gaussian-Newton (AGN) method for overparameterized non-convex low-rank matrix sensing problem. The authors presented the corresponding theoretical analysis and partially explained the reason the proposed AGN method achieves fast convergence rates.", "questions": "The authors claims that the proposed method has superlinear convergence rate. Where is the theorem about the superlinear convergence rate?", "limitations": "The authors has presented the limitations in the last section.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "In this submission, the authors proposed a new AGN method The main idea is natural and the authors provide both theoretical analysis as well as some numerical experiments that provide empirical results consistent with the theoretical results. The main structure of this submission is clear and the presentation is of high quality.", "weaknesses": "There are major two drawbacks of this paper.\n\n1. The authors should put all the empirical results from the numerical experiments into one single section. The authors should proved more numerical experiments to compared the proposed method with other state-of-art algorithms and put all the figures and tables in one numerical experiment section.\n\n2. The authors didn't present or prove the superlinear convergence rate of the proposed AGN algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate the reviewer for your careful review, constructive suggestions and positive feedbacks. The followings are our responses to your concerns. We will greatly appreciate that you can raise your score if you find our responses resolve your concerns.\n\n**1. Question: About the experiments.**  \n**Answer:** Thank you for the reviewer’s suggestion. We have added comparisons of the iteration complexity of the proposed AGN with GD, PrecGD, and ScaledGD ($\\lambda$), as in the following table\n| reference | algorithm                        |  iteration complexity  |\n|:----------:| :----------------:|:-------------------|\n|[19]           | GD                                  | $\\kappa^8 + \\kappa^6\\log(\\kappa n / \\epsilon)$ |\n| [15]          | PrecGD                           | $\\kappa^8 + \\log(1/\\epsilon)$|\n|[27]           |ScaledGD($\\lambda$)     | $\\log \\kappa \\cdot \\log \\kappa n + \\log(1/\\epsilon)$|\n| ours         |  AGN                               | $\\log(1/\\epsilon)$|\n||  \n\nwhere $\\kappa$ is the conditional number of the target matrix, $n$ is the matrix dimension. These results are also presented in Table 1 (in the rebuttal PDF file). Additionally, we provide comparisons of the computational time of these competing methods across different dimensions in Table 2 (in the rebuttal PDF file). Both theoretical and experimental results demonstrate the superiority of the proposed AGN over the competing methods. We will include details of the experimental settings and the above comparisons in the revision.  \n\n**2. Question: About the superlinear convergence.**  \n**Answer:** The superlinear convergence is indicated by $c_q=0$ in Theorem 2, which is presented at the end of the Theorem 2. We will make it more clearer in the revision.", "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": "", "extra_scores": {}}, {"review_id": "8FUtMaQoLD", "reviewer": "Reviewer_L5qb", "summary": "This paper focuses on the optimization of overparameterized, non-convex low rank matrix sensing (LRMS)—an essential component in contemporary statistics and machine learning. \nThis paper introduces an approximated Gaussian-Newton (AGN) method for tackling the non-convex LRMS problem. Notably, AGN incurs a computational cost comparable to gradient descent per iteration but converges much faster without being slowed down by saddle points. This paper proves that, despite the non-convexity of the objective function, AGN achieves Q-linear convergence from random initialization to the global optimal solution. Moreover, under certain conditions on the sensing operator, AGN demonstrates super-linear convergence rate. The global Q-linear convergence of\nAGN represents a substantial enhancement over the convergence of the existing methods for the overparameterized non-convex LRMS.\n\n\nProblem:\n\nThere are some severe typos that will affect the readability of this paper.\n\n(1) Line 134, it should be $J(x_t) = \\phi'(x_t)$ instead of $J(x_t) = \\psi'(x_t)$.\n(2) Line 155, $\\mathcal{B}(X,X) = \\mathcal{A} (PXX^\\top Q)$, so, what is $\\mathcal{B}(\\Delta, X_t)$ in line Eq.(7)?\n(3) Why does Eq. (7) relate to Gauss-Newton? I known $\\phi(x) = \\mathcal{B}(X,X) - b$, but what is its Jacobian? what is $J\\Delta$? \n\nDue to these problems, I think this paper is hard to read.", "questions": "No", "limitations": "No", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper focuses on the optimization of overparameterized, non-convex low rank matrix sensing (LRMS)—an essential component in contemporary statistics and machine learning. \nThis paper introduces an approximated Gaussian-Newton (AGN) method for tackling the non-convex LRMS problem. Notably, AGN incurs a computational cost comparable to gradient descent per iteration but converges much faster without being slowed down by saddle points. This paper proves that, despite the non-convexity of the objective function, AGN achieves Q-linear convergence from random initialization to the global optimal solution. Moreover, under certain conditions on the sensing operator, AGN demonstrates super-linear convergence rate. The global Q-linear convergence of\nAGN represents a substantial enhancement over the convergence of the existing methods for the overparameterized non-convex LRMS.", "weaknesses": "No", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude for your valuable comments on our work. As for your concerns, we give detailed response below which we hope can help you fully understand our work. Please feel free to let us know if you have any further concerns. We will deeply appreciate that you can raise your score if you find our responses resolve your concerns.\n\n**1. Question: About the typos.**  \n**Answer:** We apologize for the typo here and will thoroughly review the entire manuscript to eliminate any remaining errors.\n\n**2. Question: For the expression $\\mathcal B(X,X)= \\mathcal A(PXX^TQ)$.**  \n**Answer:** We will restate the bilinear function as $\\mathcal B(X,Y)= \\mathcal A(PXY^TQ)$ to ensure clarity, such that $\\mathcal B(\\Delta, X) = \\mathcal A(P\\Delta X^TQ)$ is unambiguous.\n\n**3.Question: About the Jacobian and the first-order approximation of $\\mathcal B(X,X) - b$.**  \n**Answer:** It is straightforward to find that $J\\Delta = \\mathcal B(X, \\Delta) + \\mathcal B(\\Delta,X)= \\mathcal A(P\\Delta X^TQ) + \\mathcal A(PX\\Delta^TQ)$.\nNote that $\\phi(X+\\Delta) = \\mathcal A(P(X+\\Delta)(X+\\Delta)^TQ) = \\mathcal A(PXX^TQ) + \\mathcal A(P\\Delta X^TQ) + \\mathcal A(PX\\Delta^TQ) + \\mathcal O(\\Delta^2)$. Therefore the first-order Taylor expansion is $\\mathcal A(PXX^TQ) + \\mathcal A(P\\Delta X^TQ) + \\mathcal A(PX\\Delta^TQ)$.", "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": "", "extra_scores": {}}, {"review_id": "Sp5sOUwIkS", "reviewer": "Reviewer_aVzA", "summary": "This paper introduces a custom Guass-Newton method dubbed AGN to solve general over-parametrized matrix sensing problems, and demonstrated that 1) This new method is a descent method under benign assumptions and 2) it achieves Q-linear convergence under restrictive RIP assumptions.", "questions": "See some above.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. Introduced a new algorithm beyond GD based ones to solve this hard non-convex problem with some theoretical guarantees, which is nice. The framework of the problem is relatively relaxed, and is not tailored to very specific instances of matrix sensing.\n\n2. Showcases that AGN will not be trapped inside hessian points theoretically.\n\n3. The authors proves the quick convergence of this algorithm under small RIP constant.\n\n4. The structure of this paper is easy to follow, addresses appropriate prior works, and offers appropriate level of details. Overall, this paper is very well-written and a pleasure to read.", "weaknesses": "1. I still find computational cost and difficulty of obtaining a good AGN update to be hard to understand. It is well-known that GN methods perform better than GD in terms of landscape and convergence rate, while at the cost of computation. Therefore the readers need to know where this tradeoff stands in this scenario.’\n\n2. Section 5 offers the analysis under a very restrictive setting, which is an extremely small RIP constants. Such constants are hard to find in real life, and even GD methods perform very well under this setting, some achieving linear convergence when not too far from the ground truth. The readers need to know under this easy setting, how does AGN shine?\n\n3. Theorem 2 offers the convergence results in terms of function value, but this is a tricky choice because we don’t know whether the distance between $X_t$ and ground truth also shrinks at a linear rate, which is what we are after. Since in Theorem 2 a small RIP constant is used, I imagine the difference in function value can be transformed into matrix distances with a minor twist, i still find it intriguing why the authors made this choice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer for your positive evaluation of our work, and we also thank you for your valuable and constructive suggestions. As for your concerns, we make detailed responses as follows. \n\n**1. Question: The computational cost of AGN over GD.**  \n**Answer:** In general, the computational cost of the Gauss-Newton method is higher than that of GD. However, in our low-rank matrix recovery problem, the proposed AGN benefits from the low-rank structure, making the computational cost of solving equation (8) not much higher than that of GD, given that the dimension $d$ is much smaller than $n$. Specifically, equations (33) and (34) indicate that the main computational overhead of AGN compared to GD is the inversion of a matrix of size $d \\times d$, which is manageable for small $d$.\n\n**2. Question: About the RIP constant and the advantage of AGN over GD under special initialization.**  \n**Answer:** We aim to show that the proposed AGN method can effectively avoid saddle points with linear convergence of the function value. As a result, we may not need to improve the RIP constant, though this could be a valuable direction for our future research. With this small RIP constant, even with good initialization, GD converges sub-linearly for the over-parameterized low-rank matrix sensing model, as noted by [15]. Additionally, the convergence of GD highly depends on the condition number of the target matrix, as indicated by [26]. In contrast, AGN guarantees linear convergence that is independent of the condition number of the target matrix.\n\n**3. Question: The convergence in terms of the function value vs. the variables X.**  \n**Answer:** Our primary objective is to demonstrate that the AGN method avoids getting trapped in saddle points where the function value is high, but the gradient norm is low. We aim to illustrate the decrease in function value (as adopted by [15]), based on the premise that if an optimization method is hindered by saddle points, its function value will decrease very slowly near these points, as shown for GD in Fig. 1 of the main paper. The linear convergence at a constant rate of the AGN on function value clearly demonstrates that AGN does not get trapped in saddle points.  \n\nMoreover, with a small RIP constant, it is straightforward to derive the convergence of the variable $X$ based on the linear convergence of the function value and the following distance metric ${\\rm{dist}}(X_t, X^*) = \\min_Q \\frac{1}{2}||U_tQ-U^*||_F^2 + \\frac{1}{2}||V_tQ-V^*||_F^2$ with orthogonal matrix $Q$, where $X_t= \\begin{bmatrix} U_t^{\\top} &  V_t^{\\top} \\end{bmatrix}^{\\top}$, $X^* = \\begin{bmatrix} U^{* \\top} & V^{* \\top} \\end{bmatrix}^{\\top}$ is the global optimal solution. We thank the reviewer for the helpful comment. We will include the convergence of ${\\rm{dist}}(X_t, X^*)$ in our revision.", "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": "", "extra_scores": {}}]

Author rebuttal:
Dear ACs and reviewers,

Thank you very much for your valuable comments. We truly appreciate the time and effort you've taken to review our work. We're glad the reviewers found our work valuable and provided positive feedback. Your feedback is important to us, and in accordance with the reviewers' comments, we have carefully revised the manuscript and provided detailed responses to all your concerns (please refer to our rebuttal for each reviewer for more detailed responses).

Saddle points can significantly slow the convergence of gradient descent methods in non-convex optimization problems. Previous works have shown that over-parameterization further reduces the convergence rate of gradient descent from linear to sublinear for low-rank matrix sensing. This paper demonstrates that by employing an approximation of the Gauss-Newton method, AGN can effectively and efficiently escape all saddle points with a linear convergence rate, significantly improving upon the results of gradient descent. We include in the one-page rebuttal PDF comparisons of iteration complexity (Table 1) and computational time (Table 2) of AGN with most recent state-of-the-art methods.

We greatly appreciate the reviewer’s comments on the experiment section. In our revision, we will provide more detailed settings and analyses for the figures and tables in the experiment section. We are also grateful to the reviewers for pointing out the typos and their concerns, which are invaluable for improving our work.

Once again, thank you for taking the time to review our work and provide valuable insights. We will take all the reviewers' suggestions into consideration for future improvements. We are also open to further discussions with the reviewers if there are any additional concerns.

Regards,
Authors of #4376

Meta-review: This paper demonstrates that AGN achieves Q-linear convergence from random initialization to the global optimal solution despite the non-convexity of the objective function, and under certain conditions on the sensing operator, it further exhibits a super-linear convergence rate, representing a significant improvement over existing methods for overparameterized non-convex LRMS.
Decision: Accept (poster)