<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>The nonconvex geometry of low-rank matrix optimizations with general objective functions</title></titleStmt>
			<publicationStmt>
				<publisher></publisher>
				<date>11/01/2017</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10099581</idno>
					<idno type="doi">10.1109/GlobalSIP.2017.8309158</idno>
					<title level='j'>The nonconvex geometry of low-rank matrix optimizations with general objective functions</title>
<idno></idno>
<biblScope unit="volume"></biblScope>
<biblScope unit="issue"></biblScope>					

					<author>Qiuwei Li</author><author>Gongguo Tang</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[This work considers the minimization of a general convex function f (X) over the cone of positive semi-definite matrices whose optimal solution X* is of low-rank. Standard first-order convex solvers require performing an eigenvalue decomposition in each iteration, severely limiting their scalability. A natural nonconvex reformulation of the problem factors the variable X into the product of a rectangular matrix with fewer columns and its transpose. For a special class of matrix sensing and completion problems with quadratic objective functions, local search algorithms applied to the factored problem have been shown to be much more efficient and, in spite of being nonconvex, to converge to the global optimum. The purpose of this work is to extend this line of study to general convex objective functions f (X) and investigate the geometry of the resulting factored formulations. Specifically, we prove that when f (X) satisfies the restricted well-conditioned assumption, each critical point of the factored problem either corresponds to the optimal solution X* or a strict saddle where the Hessian matrix has a strictly negative eigenvalue. Such a geometric structure of the factored formulation ensures that many local search algorithms can converge to the global optimum with random initializations.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.">INTRODUCTION</head><p>Consider a general semi-definite program (SDP) where a convex objective function f (X) is minimized over the cone of positive semi-definite (PSD) matrices: minimize X&#8712;R n&#215;n f (X) subject to X 0.</p><p>(1)</p><p>For this problem, even fast first-order methods, such as the projected gradient descent algorithm <ref type="bibr">[2]</ref>, require performing an expensive eigenvalue decomposition in each iteration. These expensive operations form the major computational bottleneck of the algorithms and prevent them from scaling Full version appears as <ref type="bibr">[1]</ref>. This work was supported by NSF grant CCF-1464205. Email: {qiuli, gtang}@mines.edu.</p><p>to scenarios with millions of variables, a typical situation in a diverse of applications, including quantum state tomography <ref type="bibr">[3]</ref>, user preferences prediction <ref type="bibr">[4]</ref>, and pairwise distances estimation in sensor localization <ref type="bibr">[5]</ref>.</p><p>When the SDP (1) admits a low-rank solution X , in their pioneer work <ref type="bibr">[6]</ref>, Burer and Monteiro proposed to factorize the variable X = U U T , where U &#8712; R n&#215;r with r n, and solved a factored nonconvex problem minimize U &#8712;R n&#215;r g(U ), where g(U ) := f (U U T ).</p><p>(</p><p>There, they dealt with standard SDPs with a linear objective function and several linear constraints, and argued that when the factorization X = U U T is overparameterized, i.e., r &gt; r := rank(X ), any local minimum of (2) corresponds to the solution X , provided some regularity conditions are satisfied. Unfortunately, these regularity conditions are generally hard to verify for specific SDPs arising in applications.</p><p>Our work differs in that the convex objective function f (X) is generally not linear and there are no additional linear constraints.</p><p>The past few years have seen renewed interest in the Burer-Monteiro factorization for solving low-rank matrix recovery inverse problems. With technical innovations in analyzing the nonconvex landscape of the factored objective function, several recent works have shown that with exact parameterization (i.e., r = r ) the factored objective function g(U ) in has no spurious local minima or degenerate saddle points <ref type="bibr">[7]</ref><ref type="bibr">[8]</ref><ref type="bibr">[9]</ref><ref type="bibr">[10]</ref><ref type="bibr">[11]</ref><ref type="bibr">[12]</ref>. An important implication is that local search algorithms, such as gradient descent and its variants, are able to converge to the global optimum with even random initialization <ref type="bibr">[13]</ref>.</p><p>We generalize this line of work by assuming a general objective function f (X) in the optimization <ref type="bibr">(1)</ref>. Viewing the factored problem (2) as a way to solve the convex optimization (1) to the global optimum, frees us from rederiving the statistical performances of the factored optimization <ref type="bibr">(2)</ref>. Instead, its performance inherits from that of the convex optimization (1), whose performance can be developed using a suite of powerful convex analysis techniques accumulated from several decades of research. As a specific example, the optimal sampling complexity <ref type="bibr">[14]</ref> and minimax denoising rate <ref type="bibr">[15]</ref> need not to be rederived once one knows the equivalence between the convex and the factored formulations.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">MAIN THEOREM</head><p>Before presenting our main result, we provide several necessary definitions. We call a vector x a critical point of some differentiable function f (&#8226;) if the gradient &#8711;f (x) = 0. When f (&#8226;) is twice continuously differentiable, a critical point x is called a strict saddle or riddable saddle <ref type="bibr">[16]</ref> if the Hessian has a strictly negative eigenvalue, i.e., &#955; min (&#8711; 2 f (x)) &lt; 0. A twice continuously differentiable function satisfies the strict saddle property if every critical point is either a local minimum or is a strict saddle <ref type="bibr">[7]</ref>.</p><p>Heuristically, the strict saddle property describes a geometric structure of the landscape: if a critical point is not a local minimum, then it is a strict saddle, which implies the Hessian matrix at this point has a strictly negative eigenvalue. Hence, we can continue to decrease the function value at this point along the negative-curvature direction.</p><p>Theorem 1 (Local convergence <ref type="bibr">[13,</ref><ref type="bibr">17,</ref><ref type="bibr">18]</ref>). The strict saddle property allows many local search algorithms to escape all the saddle points and converge to a local minimum.</p><p>Our governing assumption on the objective function f (X) is the (2r, 4r)-restricted well-conditioned assumption:</p><p>for any D of rank(D) &#8804; 4r and any PSD matrix X with rank(X) &#8804; 2r. Here, [&#8711; 2 f (X)](D, D) is the directional curvature along D, defined as i,j,l,k</p><p>This restricted well-conditioned assumption (3) is standard in matrix inverse problem <ref type="bibr">[19,</ref><ref type="bibr">20]</ref>. We show that if the original objective function f (X) is (2r, 4r)-restricted well conditioned, then each critical point of the factored objective function g(U ) either corresponds to the low-rank global solution of the original convex program or is a strict saddle where the Hessian &#8711; 2 g(U ) has a strictly negative eigenvalue. This implies the factored objective function g(U ) satisfies the strict saddle property.</p><p>Theorem 2 (Global landscape). Suppose the function f (X) in (1) is twice continuously differentiable and restricted wellconditioned (3). Assume X is an optimal solution of the minimization (1) with rank(X ) = r . Set r &#8805; r in (2). Let U be any critical point of g(U ) satisfying &#8711;g(U ) = 0. Then U either corresponds to a square-root factor of X , i.e.,</p><p>or is a strict saddle of the factored problem (2):</p><p>with &#964; := min{&#961;(U ) 2 , &#961;(X )} and &#961;(W ) denoting the smallest nonzero singular value.</p><p>Remarks. First, the matrix D is the direction from the saddle point U to its closest globally optimal factor U R of the same size as U . Second, our result covers both overparameterization where r &gt; r and exact parameterization where r = r . Third, this strict saddle property ensures that many iterative algorithms, for example, stochastic gradient descent <ref type="bibr">[17]</ref>, trust-region method <ref type="bibr">[18]</ref>, and gradient descent with sufficiently small stepsize <ref type="bibr">[13]</ref>, all converge to a square-root factor of X , even with random initialization.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.">APPLICATIONS</head><p>Our main result only relies on the restricted well-conditioned property. Therefore, in addition to the traditional low-rank matrix recovery problems with a quadratic loss function, it is also applicable to a lot of other low-rank matrix optimization problems with possibly non-quadratic loss functions. We compiled the following list of applications that are covered by our theory.</p><p>Weighted PCA Problem. Formally, in the weighted-PCA problem, given a pointwisely-weighted observation of a PSD matrix X, i.e., Y = W X where is the Hadamard product or its perturbed version with W being the sensing matrix, one aims to recover the principle component U by minimizing the nonconvex objective function g</p><p>F . The weighted-PCA problem has no known analytic solution and it is shown to be NP-hard <ref type="bibr">[21]</ref>. Fortunately, by defining</p><p>F . Hence, as long as the weights have a smaller dynamic range:</p><p>it is guaranteed to recover U through local search algorithms. Symmetric Robust PCA. In the symmetric variant of robust PCA, the observed matrix Y = X + S with S being sparse and X being PSD. Traditionally, we recover X by minimizing ||Y -X|| 1 = ij |Y ij -S ij | subject to a PSD constraint. However, this formulation doesn't fit into our framework naively due to the non-smoothness of the 1 norm. An interesting bypass would be solving X by minimizing ij h a (Y ij -S ij ) where h a (.) is chosen to be a convex smooth approximation to the absolute value function. A possible choice is h a (x) = a log((exp(x/a) + exp(-x/a))/2), which is shown to be strictly convex and smooth in [22, Lemma A.1].</p><p>1-Bit Matrix Recovery. Given quantized measurements: y j = bit(A j &#8226; X ) where &#8226; denotes the inner product and bit(x) outputs 0 or 1 in a probabilistic manner, we attempt to recover X &#8712; R n&#215;m by minimizing f (X) = j (y j log(&#963;(A j &#8226;X))+(1-y j ) log(1-&#963;(A j &#8226;X))), where &#963;(x) = e x 1+e x is the logistic regression function <ref type="bibr">[23]</ref>. Moreover, the Hessian quadratic form of f 2 . Then as long as the number of Gaussian measurements is comparable to the degrees of freedom in X and the elements of A j concentrate in a certain range (which ensures &#963; (&#8226;) has small dynamic range), 1-bit matrix recovery fits into our framework. In particular, when we get full measurements, i.e., we have</p><p>with E ij being the canonical basic in R n&#215;m . For this special case, the Hessian quadratic form is given as</p><p>F . Direct computations give that the derivative &#963; (x) has a smaller dynamic range for small x:</p><p>min x&#8712;[-1,1] &#963; (x) &#8804; 1.27. Therefore, when we restrict the values |X ij | to be small: max ij |X ij | &#8804; 1, 1-bit matrix recovery fits into our framework. Such an constraint on max ij |X ij | is also required in <ref type="bibr">[23]</ref> to obtain an accurate estimate of X .</p><p>Low-rank Matrix Recovery with Non-Gaussian Noise. Consider a matrix sensing or PCA problem. When the noise is from the normal distribution, the according maximum likelihood estimation (MLE) is the minimizer of a squared loss function. However, in practice, the noise in data is often from other distributions. In this case the resulting MLE is obtained by minimizing the negative log-likelihood function, which is not the square loss. Such a noise-adaptive estimator is more effective than square-loss minimization. To have a strongly convex and smooth objective function so that our theory can apply, the noise distribution should be log-strongly-concave. The reference <ref type="bibr">[24]</ref> contains many examples of such distributions.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.">PROBLEM FORMULATIONS AND PRELIMINARIES</head><p>This paper considers the problem (1) of minimizing a convex function f (X) over the PSD cone. Let X be an optimal solution of (1) of rank r . When the PSD variable X is reparameterized as</p><p>where U &#8712; R n&#215;r with r &#8805; r is a rectangular, matrix square root of X, the convex program is transformed into the factored problem (2) whose objective function is g(U ) := f (&#966;(U )). Inspired by the lifting technique in constructing SDP relaxations, we refer to the variable X as the lifted variable, and the variable U as the factored variable. Similar naming conventions apply to the optimization problems, their domains, and objective functions. The nonlinear parametrization X = &#966;(U ) makes g(U ) a nonconvex function and introduces additional critical points (i.e., those U with &#8711;g(U ) = 0 that are not global optima of the factored optimization (2)). Our goal is to show that each critical points either corresponds to X or is a strict saddle where the Hessian has a strictly negative eigenvalue.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.1.">Metrics in the Lifted and Factored Spaces</head><p>Since for any U , &#966;(U ) = &#966;(U R) where R &#8712; O r with O r being all r &#215; r orthonormal matrices, the domain of the factored objective function g(U ) is stratified into equivalent classes and can be viewed as a quotient manifold. The matrices in each of these equivalent classes differ by an orthogonal transformation (not necessarily unique when the rank of U is less than r). One implication is that, when working in the factored space, we should consider all factorizations of X :</p><p>A second implication is that when considering the distance between two points U 1 and U 2 , one should use the distance between their corresponding equivalent classes:</p><p>For any two matrices U 1 , U 2 &#8712; R n&#215;r , the following lemma relates the distance &#966;(U 1 ) -&#966;(U 2 ) F in the lifted space to the distance d(U 1 , U 2 ) in the factored space, with the proof deferred to <ref type="bibr">[1]</ref>:</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.">PROOF: CONNECTING THE OPTIMALITY CONDITIONS</head><p>The proof is inspired by connecting the optimality conditions for the two programs (1) and <ref type="bibr">(2)</ref>. First of all, as a constrained convex optimization, all critical points of (1) are global optima and are characterized by the necessary and sufficient KKT condition <ref type="bibr">[2]</ref>:</p><p>The factored optimization (2) is unconstrained, whose critical points are specified by the zero gradient condition:</p><p>To classify the critical points, we compute the Hessian bilinear form [&#8711; 2 g(U )](D, D) as:</p><p>For any critical point U of g(U ), the corresponding lifted variable &#966;(U ) = U U T is PSD and satisfies &#8711;f (&#966;(U ))&#966;(U ) = 0. On one hand, if &#966;(U ) further satisfies &#8711;f (&#966;(U )) 0, then in view of the KKT conditions <ref type="bibr">(7)</ref> and noting rank(&#966;(U )) &#8804; r, we must have &#966;(U ) = X , the global optimum of (1). On the other hand, if &#966;(U ) = X , implying &#8711;f (&#966;(U )) 0 due to the necessity of <ref type="bibr">(7)</ref>, then additional critical points can be introduced into the factored space. Fortunately, &#8711;f (&#966;(U )) 0 also implies that the first quadratic form in ( <ref type="formula">9</ref>) might be negative for a properly chosen direction D. To sum up, the critical points of g(U ) can be classified into two categories: the global optima in the optimal factor set A with &#8711;f (&#966;(U )) 0 and those with &#8711;f (&#966;(U )) 0. For the latter case, by choosing a proper direction D, we will argue that the Hessian quadratic form (9) has a strictly negative eigenvalue, and hence moving along D in a short distance will decrease the value of g(U ), implying that they are strict saddles and are not local minima.</p><p>We argue that a good choice of D is the direction from current U to its closest point in the optimal factor set A . Formally, D = U -U R where R = argmin R&#8712;Or U -U R F is the optimal rotation for the orthogonal Procrustes problem. Plugging D into the first term of ( <ref type="formula">9</ref>), we simplify it as</p><p>where in the second equality the last three terms involving U were canceled and in the last equality the term -U U T was reintroduced both due to the critical point property &#8711;f (&#966;(U ))U = 0. To build intuition on why <ref type="bibr">(10)</ref> is negative while the second term in (9) remains small, we consider a simple example: the matrix Principal Component Analysis (PCA) problem.</p><p>Example 1. Matrix PCA Problem. Consider the PCA problem for symmetric PSD matrices:</p><p>where X is a symmetric PSD matrix of rank r . Apparently, the optimal solution is X = X . Now consider the factored problem:</p><p>where U &#8712; R n&#215;r satisfies &#966;(U ) = X . Our goal is to show that any critical point U such that &#966;(U ) = X is a strict saddle. Since &#8711;f (&#966;(U )) = &#966;(U ) -&#966;(U ), by <ref type="bibr">(10)</ref>, the first term of [&#8711; 2 g(U )](D, D) in (9) becomes</p><p>which is strictly negative.</p><p>The second term [&#8711; 2 f (&#966;(U ))](DU T + U D T , DU T + U D T ), essentially vanishes since we will see in the next that DU T = 0 (hence U D T = 0). For this purpose, let X = r i=1 &#955; i q i q T i be the reduced eigenvalue decomposition of X , where q i 's are orthonormal and &#955; i &gt; 0. Similarly, let &#966;(U ) = r i=1 &#181; i v i v T i be the reduced eigenvalue decomposition of &#966;(U ), where r = rank(U ). The critical point U satisfies -&#8711;g(U ) = 2(X -&#966;(U ))U = 0, i.e.,</p><p>implying {&#181; j , v j } r j=1 form eigenvalue-eigenvector pairs of X (so r &#8804; r ). Then, by reordering the indices if necessary, &#181; j = &#955; j and v j = q j , j = 1, . . . , r .</p><p>. By the Procrustes Lemma in <ref type="bibr">[25]</ref>, we get R = V T . Finally,</p><p>&#955; j q j q T j -r j=1 &#955; j q j q T j = 0.</p><p>Hence [&#8711; 2 g(U )](D, D) is simply determined by its first term <ref type="bibr">(11)</ref>:</p><p>F , where the inequality follows from Lemma 1 and the last equality holds since all eigenvalues of &#966;(U ) come from those of X . This further implies &#955; min (&#8711; 2 g(U )) &#8804; -2&#961;(X ).</p><p>This simple example is ideal in several ways, particularly the gradient &#8711;f (&#966;(U )) = &#966;(U ) -&#966;(U ), which directly establishes the negativity of the first term in <ref type="bibr">(9)</ref>; and by choosing D = U -U R and using DU T = 0, the second term vanishes. Both are not true any more for general objective functions f (X). However, the example does suggest that the direction D = U -U R is a good choice to show [&#8711; 2 g(U )](D, D) &#8804; -&#964; D 2 F for some &#964; &gt; 0. For a formal proof, we will also use the direction D -U -U R to show those critical points U not corresponding to X have a negative directional curvature for general factored objective function g(U ).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="6.">CONCLUSIONS</head><p>This work investigates the minimization of a convex function f (X) over the cone of PSD matrices. To improve computational efficiency, we focus on the factored problem, and show it has a benign landscape: each critical point is either a factor of the globally optimal solution X , or a strict saddle.</p></div>			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" xml:id="foot_0"><p>978-1-5090-5990-4/17/$31.00 &#169;2017 IEEE GlobalSIP 2017</p></note>
		</body>
		</text>
</TEI>
