The Non-convex Geometry of Low-rank Matrix Optimization

Introduction

Nonconvex reformulations of convex optimization problems have received a surge of renewed interest for efficiency and scalability reasons . Compared with the convex formulations, the non-convex ones typically involve many fewer variables, allowing them to scale to scenarios with millions of variables. Besides, simple algorithms applied to the non-convex formulations have surprisingly good performance in practice. However, a complete understanding of this phenomenon, particularly the geometrical structures of these non-convex optimization problems, is still an active research area. Unlike the simple geometry of convex optimization problems where local minimizers are also global ones, the landscapes of general non-convex functions can become extremely complicated. Fortunately, for a range of convex optimization problems, particularly for matrix completion and sensing problems, the corresponding non-convex reformulations have nice geometric structures that allow local-search algorithms to converge to global optimality .

We extend this line of investigation by working with a general convex function $f(\mathbf{X})$ and considering the following two popular optimization problems:

For these two problems, even fast first-order methods, such as the projected gradient descent algorithm , require performing an expensive eigenvalue decomposition or singular value decomposition in each iteration. These expensive operations form the major computational bottleneck and prevent them from scaling to scenarios with millions of variables, a typical situation in a diverse range of applications, including quantum state tomography , user preferences prediction , and pairwise distances estimation in sensor localization .

As we have seen, the extremely large dimension of the optimization variable $\mathbf{X}$ and the accordingly expensive eigenvalue or singular value decompositions on X form the major computational bottleneck of the convex optimization algorithms. An immediate question might be “Is there a way to directly reduce the dimension of the optimization variable $\mathbf{X}$ and meanwhile avoid performing the expensive eigenvalue or singular value decompositions?”

Since $r\ll\{p,q\}$, the resulting factored problems ($\mathcal{F}_{0}$)-($\mathcal{F}_{1}$) involve many fewer variables. Moreover, because the positive semi-definite constraint is removed from ($\mathcal{P}_{0}$) and the nuclear norm $\|\mathbf{X}\|_{*}$ in ($\mathcal{P}_{1}$) is replaced by $(\|\mathbf{U}\|_{F}^{2}+\|\mathbf{V}\|_{F}^{2})/2$, there is no need to perform an eigenvalue (or a singular value) decomposition in solving the factored problems.

The past two years have seen renewed interest in the Burer-Monteiro factorization for solving low-rank matrix optimization problems . With technical innovations in analyzing the non-convex landscape of the factored objective function, several recent works have shown that with an exact parameterization (i.e., $r=r^{\star}$) the resulting factored reformulation has no spurious local minima or degenerate saddle points . An important implication is that local-search algorithms such as gradient descent and its variants can converge to the global optima with even random initialization .

We generalize this line of work by assuming a general objective function $f(\mathbf{X})$ in ($\mathcal{P}_{0}$)-($\mathcal{P}_{1}$), not necessarily coming from a matrix inverse problem. This generality allows us to view the resulting factored problems ($\mathcal{F}_{0}$)-($\mathcal{F}_{1}$) as a way to solve the original convex optimization problems to the global optimum, rather than a new modeling method. This perspective, also taken by Burer and Monteiro in their original work , frees us from rederiving the statistical performances of the resulting factored optimization problems. Instead, the statistical performances of the resulting factored optimization problems inherit from that of the original convex optimization problems, whose statistical performance can be analyzed using a suite of powerful convex analysis techniques, which have accumulated from several decades of research. For example, the original convex optimization problems ($\mathcal{P}_{0}$)-($\mathcal{P}_{1}$) have information-theoretically optimal sampling complexity , achieve minimax denoising rate and satisfy tight oracle inequalities . Therefore, the statistical performances of the factored optimization problems ($\mathcal{F}_{0}$)-($\mathcal{F}_{1}$) share the same theoretical bounds as those of the original convex optimization problems ($\mathcal{P}_{0}$)-($\mathcal{P}_{1}$), as long as we can show that the two problems are equivalent.

In spite of their optimal statistical performance , the original convex optimization problems cannot be scaled to solve the practical problems that originally motivate their development even with specialized first-order algorithms. This was realized since the advent of this field where the low-rank factorization method was proposed as an alternative to convex solvers . When coupled with stochastic gradient descent, low-rank factorization leads to state-of-the-art performance in practical matrix recovery problems . Therefore, our general analysis technique also sheds light on the connection between the geometries of the original convex programs and their non-convex reformulations.

Although the Burer-Monteiro parameterization tremendously reduces the number of optimization variables from $n^{2}$ to $nr$ (or $nm$ to $(n+m)r$) when $r$ is very small, the intrinsic bi-linearity makes the factored objective functions non-convex and introduces additional critical points that are not global optima of the factored optimization problems. One of our main purposes is to show that these additional critical points will not introduce spurious local minima. More precisely, we want to figure out what properties of the convex function $f$ are required for the factored objective functions $g$ to have no spurious local minima.

2 Enlightening Examples

To gain some intuition about the properties of $f$ such that the factored objective function $g$ has no spurious local minima (which is one of the main goals considered in this paper), let us consider the following two examples: Weighted principal component analysis (weighted PCA) and the matrix sensing problem.

Consider the symmetric weighted PCA problem in which the lifted objective function is

where $\odot$ is the Hadamard product, $\mathbf{X}^{\star}$ is the global optimum we want to recover and $\mathbf{W}$ is the known weighting matrix (which is assumed to have no zero entries for simplicity). After applying the Burer-Monteiro parameterization to $f(\mathbf{X})$, we obtain the factored objective function

To investigate the conditions under which the bi-linearity $\phi(\mathbf{U})=\mathbf{U}\mathbf{U}^{\top}$ will (not) introduce additional local minima to the factored optimization problems, consider a simple (but enlightening) two-dimensional example where $\mathbf{W}=\begin{bmatrix}\sqrt{1+a}&1\\ 1&\sqrt{1+a}\end{bmatrix}\text{ for some }a\geq 0,\mathbf{X}^{\star}=\begin{bmatrix}1&1\\ 1&1\end{bmatrix},$ and $\mathbf{U}=\begin{bmatrix}x\\ y\end{bmatrix}$ for unknowns $x,y$. Then the factored objective function becomes

In this particular setting, we will see that the value of $a$ in the weighting matrix is the deciding factor for the occurrence of spurious local minima.

The factored objective function $g(\mathbf{U})$ in (1.1) has no spurious local minima when $a\in[0,2)$; while for $a>2$, spurious local minima will appear.

First of all, we compute the gradient $\nabla g(\mathbf{U})$ and Hessian $\nabla^{2}g(\mathbf{U})$:

Now we collect all the critical points by solving $\nabla g(\mathbf{U})=0$ and list the Hessian of $g$ at these points as followsNote that if $\mathbf{U}$ is a critical point, so is $-\mathbf{U}$, since $\nabla g(-\mathbf{U})=-\nabla g(\mathbf{U})$. Hence we only list one part of these critical points.

$\mathbf{U}_{1}=(0,0)$, $\nabla^{2}g(\mathbf{U}_{1})=-2\begin{bmatrix}a+1&1\\ 1&a+1\\ \end{bmatrix};$

$\mathbf{U}_{2}=(1,1)$, $\nabla^{2}g(\mathbf{U}_{2})=2\begin{bmatrix}2a+3&1\\ 1&2a+3\\ \end{bmatrix};$

$\mathbf{U}_{3}=(\sqrt{\frac{a}{a+2}},-\sqrt{\frac{a}{a+2}})$, $\nabla^{2}g(\mathbf{U}_{3})=\begin{bmatrix}4a+\frac{8}{a+2}-6&\frac{8}{a+2}-6\\ \frac{8}{a+2}-6&4a+\frac{8}{a+2}-6\\ \end{bmatrix};$

$\mathbf{U}_{4}=(\frac{\sqrt{\frac{\sqrt{a^{2}-4}+a}{a}}}{\sqrt{2}},-\frac{\sqrt{2}}{a\sqrt{\frac{\sqrt{a^{2}-4}+a}{a}}})$, $\nabla^{2}g(\mathbf{U}_{4})=\begin{bmatrix}a+3\sqrt{a^{2}-4}+2+\frac{2\sqrt{a^{2}-4}}{a}&-\frac{2(a+2)}{a}\\ -\frac{2(a+2)}{a}&a-3\sqrt{a^{2}-4}+2-\frac{2\sqrt{a^{2}-4}}{a}\\ \end{bmatrix}.$

Note that the critical point $\mathbf{U}_{4}$ exists only for $a\geq 2$. By checking the signs of the two eigenvalues (denoted by $\lambda_{1}$ and $\lambda_{2}$) of these Hessians, we can further classify these critical points as a local minimum, a local maximum, or a saddle pointThis classification of the critical points using the Hessian information is known as the second derivative test, which says a critical point is a local maximum if the Hessian is negative definite, a local minimum is the Hessian is positive definite, and a saddle point if the Hessian matrix has both positive and negative eigenvalues.:

$\lambda_{1}=-2(a+2),\lambda_{2}=-2a$. So, $\mathbf{U}_{1}$ is a local maximum for $a>0$ and a strict saddle for $a=0$ (see Definition 3).

$\lambda_{1}=4(a+1)>0,\lambda_{2}=4(a+2)>0.$ So, $\mathbf{U}_{2}$ is a local minimum (also a global minimum as $g(\mathbf{U}_{2})=0$).

$\lambda_{1}=\frac{4(a-2)(a+1)}{a+2}\begin{cases}<0,&a\in[0,2)\\ >0,&a>2\end{cases},\lambda_{2}=4a>0$. So, $\mathbf{U}_{3}$ is $\begin{cases}\text{a saddle point},&a\in[0,2)\\ \text{a \emph{spurious} local minimum},&a>2\end{cases}$

From the determinant, we have $\lambda_{1}\cdot\lambda_{2}=-\frac{8(a-2)(a+1)(a+2)}{a}<0$ for $a>2$. So, $\mathbf{U}_{4}$ is a saddle point for $a>2$.

In this example, the value of $a$ controls the dynamic range of the weights as ${\max W_{ij}^{2}}/{\min W_{ij}^{2}}=1+a$. Therefore, Claim 1 can be interpreted as a relationship between the spurious local minima and the dynamic range: if the dynamic range ${\max W_{ij}^{2}}/{\min W_{ij}^{2}}$ is smaller than 3, there will be no spurious local minima; while if the dynamic range is larger than 3, spurious local minima will appear. We also plot the landscapes of the factored objective function $g(\mathbf{U})$ in (1.1) with different dynamic ranges in Figure 1.

As we have seen, the dynamic range of the weighting matrix serves as a determinant factor for the appearance of the spurious local minima for $g(\mathbf{U})$ in (1.1). To extend the above observations to general objective functions, we now interpret this condition (on the dynamic range of the weighting matrix) by relating it with the condition number of the Hessian matrix $\nabla^{2}f(\mathbf{X})$. This can be seen from the following directional-curvature form for $f(\mathbf{X})$

where $[\nabla^{2}f(\mathbf{X})](\mathbf{D},\mathbf{D})$ is the directional curvature of $f(\mathbf{X})$ along the matrix $\mathbf{D}$ of the same dimension as $\mathbf{X}$, defined by $\sum_{i,j,l,k}\frac{\partial^{2}f(\mathbf{X})}{\partial X_{ij}\partial X_{lk}}D_{ij}D_{lk}.$ This implies that the condition number $\lambda_{\max}(\nabla^{2}f(\mathbf{X}))/\lambda_{\min}(\nabla^{2}f(\mathbf{X}))$ is upper-bounded by this dynamic range:

Therefore, we conjecture that the condition number of the general convex function $f(\mathbf{X})$ would be a deciding factor of the behavior of the landscape of the factored objective function and a large condition number is very likely to introduce spurious local minima to the factored problem.

holds for all $n\times n$ matrices $\mathbf{D}$ with $\operatorname{rank}(\mathbf{D})\leq r$.

Note that the required condition (1.3) essentially says that the condition number of Hessian matrix $\nabla^{2}f(\mathbf{X})$ should be small at least in the directions of the low-rank matrices $\mathbf{D}$, since the directional curvature form of $f(\mathbf{X})$ is computed as $[\nabla^{2}f(\mathbf{X})](\mathbf{D},\mathbf{D})=\|{\mathcal{A}}(\mathbf{D})\|_{F}^{2}$.

From these two examples, we see that as long as the Hessian matrix of the original convex function $f(\mathbf{X})$ has a small (restricted) condition number, the resulting factored objective function has a landscape such that all local minima correspond to the globally optimal solution. Therefore, we believe that such a restricted well-conditionedness property might be the key factor bring us a benign factored landscape, i.e.,

which says that the landscape of $f(\mathbf{X})$ in the lifted space is bowl-shaped, at least in the directions of low-rank matrices.

3 Our Results

Before presenting the main results, we list a few necessary definitions.

For a twice differentiable function $f$, a critical point $\mathbf{x}$ is a strict saddle if the Hessian matrix $\nabla^{2}f(\mathbf{x})$ has at least one strictly negative eigenvalue.

A twice differentiable function satisfies strict saddle property if each critical point either corresponds to the local minima or is a strict saddle.

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 that 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. This nice geometric structure ensures that many local-search algorithms, such as noisy gradient descent , vanilla gradient descent with random initialization and the trust region method , can escape from all the saddle points along the directions associated with the Hessian’s negative eigenvalues, and hence converge to a local minimum.

The strict saddle propertyTo be precise, Lee et al. showed that for any function that has a Lipschitz continuous gradient and obeys the strict saddle property, first-order methods with a random initialization almost always escape all the saddle points and converge to a local minimum. The Lipschitz-gradient assumption is commonly adopted for analyzing the convergence of local-search algorithms, and we will discuss this issue after Theorem 3. To obtain explicit convergence rate, other properties (like the gradient at the points that are away from the critical points is not small) about the objective functions may be required . In this paper, similar to , we mostly focus on the properties of the critical points, and we omit the details about the convergence rate. However, we should note that, by utilizing the similar approach in , it is possible to extend the strict saddle property so that we can obtain explicit convergence rate for certain algorithms when applied for solving the factored low-rank problems. allows many local-search algorithms to escape all the saddle points and converge to a local minimum.

Our primary interest is to understand how the original convex landscapes are transformed by the factored parameterization $\mathbf{X}=\mathbf{U}\mathbf{U}^{\top}$ or $\mathbf{X}=\mathbf{U}\mathbf{V}^{\top}$, particularly how the original global optimum is mapped to the factored space, how other types of critical points are introduced, and what are their properties. To answer these questions and conclude from the previous two examples, we require that the function $f(\mathbf{X})$ in ($\mathcal{P}_{0}$)-($\mathcal{P}_{1}$) be restricted well-conditionedNote that the constant $1.5$ for the dynamic range $\frac{\beta}{\alpha}$ in ($\mathcal{C}$) is not optimized and it is possible to slightly relax this constraint with more sophisticated analysis. However, the example of the weighted PCA in (1.1) implies that the room for improving this constant is rather limited. In particular, Claim 1 and (1.2) indicate that when $\frac{\beta}{\alpha}>3$, the spurious local minima will occur for the weighted PCA in (1.1). Thus, as a sufficient condition for any general objective function to have no spurious local minima, a universal bound on the condition number should be at least no larger than 3, i.e., $\frac{\beta}{\alpha}\leq 3$. Also aside from the lack of spurious local minima, as stated in Theorem 2, the strict saddle property is the other one that needs to be guaranteed.:

We show that as long as the function $f(\mathbf{X})$ in the original convex programs satisfies the restricted well-conditioned assumption ($\mathcal{C}$), each critical point of the factored programs either corresponds to the low-rank globally optimal solution of the original convex programs or is a strict saddle point where the Hessian matrix $\nabla^{2}g$ has a strictly negative eigenvalue. This nice geometric structure coupled with the powerful algorithmic tools provided in Theorem 1 thus allows simple iterative algorithms to solve the factored programs to a global optimum.

Suppose the objective function $f(\mathbf{X})$ satisfies the restricted well-conditioned assumption ($\mathcal{C}$). Assume $\mathbf{X}^{\star}$ is an optimal solution of ($\mathcal{P}_{0}$) or ($\mathcal{P}_{1}$) with $\operatorname{rank}(\mathbf{X}^{\star})=r^{\star}$. Set $r\geq r^{\star}$ for the factored variables $\mathbf{U}$ and $\mathbf{V}$. Then any critical point $\mathbf{U}$ (or $(\mathbf{U},\mathbf{V})$) of the factored objective function $g$ in ($\mathcal{F}_{0}$)-($\mathcal{F}_{1}$) either corresponds to the global optimum $\mathbf{X}^{\star}$ such that $\mathbf{X}^{\star}=\mathbf{U}\mathbf{U}^{\top}$ for ($\mathcal{P}_{0}$) (or $\mathbf{X}^{\star}=\mathbf{U}\mathbf{V}^{\top}$ for ($\mathcal{P}_{1}$)) or is a strict saddle point (which includes a local maximum) of $g$.

First note that our result covers both over-parameterization where $r>r^{\star}$ and exact parameterization where $r=r^{\star}$, while most existing results in low-rank matrix optimization problems mainly consider the exact-parameterization case, i.e., $r=r^{\star}$, due to the hardness of fulfilling the gap between the metric in the factored space and the one in the lifted space for the over-parameterization case. The geometric property established in the theorem ensures that many iterative algorithms converge to a square-root factor (or a factorization) of $\mathbf{X}^{\star}$, even with random initialization. Therefore, we can recover the rank-$r^{\star}$ global minimizer $\mathbf{X}^{\star}$ of ($\mathcal{P}_{0}$)-($\mathcal{P}_{1}$) by running local-search algorithms on the factored function $g(\mathbf{U})$ (or $g(\mathbf{U},\mathbf{V})$) if we know an upper bound on the rank $r^{\star}$. For problems with additional linear constraints, such as those studied in , one can combine the original objective function with a least-squares term that penalizes the deviation from the linear constraints. As long as the penalization parameter is large enough, the solution is equivalent to that of the constrained minimization problems and hence is also covered by our result.

4 Stylized Applications

Our main result only relies on the restricted well-conditionedness of $f(\mathbf{X})$. Therefore, in addition to low-rank matrix recovery problems , it is also applicable to many other low-rank matrix optimization problems with non-quadratic objective functions, including $1$-bit matrix recovery, robust PCA , and low-rank matrix recovery with non-Gaussian noise . For ease of exposition, we list the following stylized applications regarding the PSD matrices. But we note that the results listed below also hold for the cases where $\mathbf{X}$ are general nonsymmetric matrices.

Since $\beta/\alpha$ is a restricted condition number (conditioning on directions of low-rank matrices), which must be no larger than the standard condition number ${\lambda_{\max}(\nabla^{2}f(\mathbf{X}))}/{\lambda_{\min}(\nabla^{2}f(\mathbf{X}))}$. Thus, together with (1.2), we have

Now we apply Theorem 2 to characterize the geometry of the factored problem of (1.4).

Suppose the weighting matrix $\mathbf{W}$ has a small dynamic range $\frac{\max W_{ij}^{2}}{\min W_{ij}^{2}}\leq 1.5$. Then the objective function of (1.4) with $r\geq r^{\star}$ satisfies the strict saddle property and has no spurious local minima.

4.2 Matrix Sensing

We now consider the matrix sensing problem which is presented before in Section 1.2. To apply Theorem 2, we first compare the RIP (1.3) with our restricted well-conditionedness ($\mathcal{C}$), which is copied below

Clearly, the restricted well-conditionedness ($\mathcal{C}$) would hold if the linear measurement operator ${\mathcal{A}}$ satisfies the $4r$-RIP with a constant $\delta_{r}$ such that

Now we can apply Theorem 2 to characterize the geometry of the following matrix sensing problem after the factored parameterization:

Suppose the linear map ${\mathcal{A}}$ satisfies the $4r$-RIP (1.3) with $\delta_{4r}\in[0,1/5]$. Then the objective function of (1.5) with $r\geq r^{\star}$ satisfies the strict saddle property and has no spurious local minima.

4.3 1-bit Matrix Completion

1-bit matrix completion, as its name indicates, is the inverse problem of completing a low-rank matrix from a set of 1-bit quantized measurements

One typical choice for $\sigma(x)$ is the sigmoid function $\sigma(x)=\frac{e^{x}}{1+e^{x}}$. To recover $\mathbf{X}^{\star}$, the authors of propose to minimizing the negative log-likelihood function

and show that if $\|\mathbf{X}^{\star}\|_{*}\leq cn\sqrt{r^{\star}}$, $\max_{ij}|\mathbf{X}^{\star}_{ij}|\leq c$ for some small constant $c$, and $\Omega$ follows certain random binomial model, solving the minimization of the negative log-likelihood function with some nuclear-norm constraint would be very likely to produce a satisfying approximation to $\mathbf{X}^{\star}$ [17, Theorem 1].

However, when $\mathbf{X}^{\star}$ is extremely high-dimensional (which is the typical case in practice), it is not efficient to deal with the nuclear norm constraint and hence we propose to minimize the factored formulation of (1.6)

In order to utilize Theorem 2 to understand the landscape of the factored objective function (1.7), we then check the following directional Hessian quadratic from of $f(\mathbf{X})$

For simplicity, consider the case where $\Omega=[n]\times[n]$, i.e., observe full quantized measurements. This will not increase the acquisition cost too much, since each measurement is of 1 bit. Under this assumption, we have

Let $\Omega=[n]\times[n].$ Assume $\|\mathbf{X}\|_{\infty}:=\max|X_{i,j}|$ is bounded by $1.3169$. Then the negative log-likelihood function (1.6) $f(\mathbf{X})$ satisfies the restricted well-conditioned property.

First of all, we claim $\sigma(x)$ is an even, positive function and decreasing when $x\geq 0$. This is because the sigmoid function $\sigma(x)$ is odd, $\sigma^{\prime}(x)=\sigma(x)(1-\sigma(x))>0$ by $\sigma(x)\in(0,1)$, and $\sigma^{\prime\prime}(x)=-\frac{e^{x}\left(e^{x}-1\right)}{\left(e^{x}+1\right)^{3}}<0$ for $x\geq 0$. Therefore, for any $|X_{ij}|\leq 1.3169,$ we have $\frac{\max\sigma^{\prime}(X_{ij})}{\min\sigma^{\prime}(X_{ij})}=\frac{\max\sigma^{\prime}(0)}{\min\sigma^{\prime}(1.3169)}\leq 1.49995\leq 1.5.$ ∎

Set $r\geq r^{\star}$ in (1.7). Then the objective function (1.7) satisfies the strict saddle property and has no spurious local minima in $\mathcal{B}_{\mathbf{U}}.$

We remark that such a constraint on $\|\mathbf{X}\|_{\infty}$ is also required in the seminal work , while by using the Burer-Monteiro parameterization, our result removes the time-consuming nuclear norm constraint.

4.4 Robust PCA

4.5 Low-rank Matrix Recovery with Non-Gaussian Noise

Consider the PCA problem where the underlying noise is non-Gaussian:

5 Prior Arts and Inspirations

The past few years have seen a surge of interest in non-convex reformulations of convex optimization problems for efficiency and scalability reasons. However, fully understanding this phenomenon, mainly the landscapes of these non-convex reformulations could be hard. Even certifying the local optimality of a point might be an NP-hard problem . The existence of spurious local minima that are not global optima is a common issue . Also, degenerate saddle points or those surrounded by plateaus of small curvature could also prevent local-search algorithms from converging quickly to local optima . Fortunately, for a range of convex optimization problems, particularly those involving low-rank matrices, the corresponding non-convex reformulations have nice geometric structures that allow local-search algorithms to converge to global optimality. Examples include low-rank matrix factorization, completion and sensing , tensor decomposition and completion , dictionary learning , phase retrieval , and many more. Based on whether smart initializations are needed, these previous works can be roughly classified into two categories. In one case, the algorithms require a problem-dependent initialization plus local refinement. A good initialization can lead to global convergence if the initial iterate lies in the attraction basin of the global optima . For low-rank matrix recovery problems, such initializations can be obtained using spectral methods ; for other problems, it is more difficult to find an initial point located in the attraction basin . The second category of works attempt to understand the empirical success of simple algorithms such as gradient descent , which converge to global optimality even with random initialization . This is achieved by analyzing the objective function’s landscape and showing that they have no spurious local minima and no degenerate saddle points. Most of the works in the second category are for specific matrix sensing problems with quadratic objective functions. Our work expands this line of geometry-based convergence analysis by considering low-rank matrix optimization problems with general objective functions.

In , the authors also considered low-rank and PSD matrix optimization problems with general objective functions. They characterized the local landscape around the global optima, and hence their algorithms require proper initializations for global convergence. We instead characterize the global landscape by categorizing all critical points into global optima and strict saddles. This guarantees that several local-search algorithms with random initialization will converge to the global optima. Another closely related work is low-rank and PSD matrix recovery from linear observations by minimizing the factored quadratic objective function . Low-rank matrix recovery from linear measurements is a particular case of our general objective function framework. Furthermore, by relating the first order optimality condition of the factored problem with the global optimality of the original convex program, our work provides a more transparent relationship between geometries of these two problems and dramatically simplifies the theoretical argument. More recently, the authors of showed that for general SDPs with linear objective functions and linear constraints, the factored problems have no spurious local minimizers. In addition to showing non-existence of spurious local minimizers for general objective functions, we also quantify the curvature around the saddle points, and our result covers both over and exact parameterizations.

The most related work is nonsymmetric matrix sensing from linear observations, which minimizes the factored quadratic objective function . The ambiguity in the factored parameterization

tends to make the factored quadratic objective function badly-conditioned, especially when the matrix $R$ or its inverse is close to being singular. To overcome this problem, the regularizer

is proposed to ensure that $\mathbf{U}$ and $\mathbf{V}$ have almost equal energy . In particular, with the regularizer in (1.8), it was shown in that $\widetilde{g}(\mathbf{U},\mathbf{V})=f(\mathbf{U}\mathbf{V}^{\top})+\mu\Theta_{E}(\mathbf{U},\mathbf{V})$ with a properly chosen $\mu>0$ has similar geometric result as the one provided in Theorem 1 for ($\mathcal{P}_{1}$), i.e., $\widetilde{g}(\mathbf{U},\mathbf{V})$ also obeys the strict saddle property. Compared with , our result shows that it is not necessary to introduce the extra regularization (1.8) if we solve ($\mathcal{P}_{1}$) with the factorization approach. Indeed, the optimization form $\|\mathbf{X}\|_{*}=\min_{\mathbf{X}=\mathbf{U}\mathbf{V}^{\top}}(\|\mathbf{U}\|_{F}^{2}+\|\mathbf{V}\|_{F}^{2})/2$ of the nuclear norm implicitly requires $\mathbf{U}$ and $\mathbf{V}$ to have equal energy. On the other hand, we stress that our interest is to analyze the non-convex geometry of the convex problem ($\mathcal{P}_{1}$) which as we explained before, has a very nice statistical performance such as it achieves minimax denoising rate . Our geometrical result implies that instead of using convex solvers to solve ($\mathcal{P}_{1}$), one can turn to apply local-search algorithms to solve its factored problem ($\mathcal{F}_{1}$) efficiently. In this sense, as a reformulation of the convex program ($\mathcal{P}_{1}$), the non-convex optimization problem ($\mathcal{F}_{1}$) inherits all the statistical performance bounds for ($\mathcal{P}_{1}$). Cabral et al. worked on a similar problem and showed all global optima of ($\mathcal{F}_{1}$) corresponds to the solution of the convex program ($\mathcal{P}_{1}$). The work applied the factorization approach to a more broad class of problems. When specialized to matrix inverse problems, their results show that any local minimizer $\mathbf{U}$ and $\mathbf{V}$ with zero columns is a global minimum for the over-parameterization case, i.e., $r>\operatorname{rank}(\mathbf{X}^{\star})$. However, there are no results discussing the existence of spurious local minima or the degenerate saddles in these previous works. We extend these works and further prove that as long as the loss function $f(\mathbf{X})$ is restricted well-conditioned, all local minima are global minima and there are no degenerate saddles with no requirement on the dimension of the variables. We finally note that compared with , our result (Theorem 2) does not depend on the existence of zero columns at the critical points and hence can provide guarantees for many local-search algorithms.

6 Notations

Problem Formulation

This work considers two problems: (i) the minimization of a general convex function $f(\mathbf{X})$ with the domain being positive semi-definite matrices; (ii) the minimization of a general convex function $f(\mathbf{X})$ regularized by the matrix nuclear norm $\|\mathbf{X}\|_{*}$ with the domain being general matrices. Let $\mathbf{X}^{\star}$ be an optimal solution of ($\mathcal{P}_{0}$) or ($\mathcal{P}_{1}$) of rank $r^{\star}$. To develop faster and scalable algorithms, we apply Burer-Monteiro style parameterization to the low-rank optimization variable $\mathbf{X}$ in ($\mathcal{P}_{0}$)-($\mathcal{P}_{1}$):

Inspired by the lifting technique in constructing SDP relaxations, we refer to the variable $\mathbf{X}$ as the lifted variable, and the variables $\mathbf{U},\mathbf{V}$ as the factored variables. Similar naming conventions apply to the optimization problems, their domains, and objective functions.

First the restricted well-conditionedness assumption reduces to (1.3) when the objective function is quadratic. Moreover, the restricted well-conditioned assumption ($\mathcal{C}$) shares a similar spirit with (1.3) in that the operator $\frac{2}{\beta+\alpha}[\nabla^{2}f(\mathbf{X})]$ preserves geometric structure for low-rank matrices:

Let $f(\mathbf{X})$ satisfy the restricted well-conditionedness assumption ($\mathcal{C}$). Then

for any matrices $\mathbf{X},\mathbf{G},\mathbf{H}$ of rank at most $2r$.

We extend the argument in to a general function $f(\mathbf{X})$. If either $\mathbf{G}$ or $\mathbf{H}$ is zero, (2.1) holds since both sides are . For nonzero $\mathbf{G}$ and $\mathbf{H}$, we can assume $\|\mathbf{G}\|_{F}=\|\mathbf{H}\|_{F}=1$ without loss of generalityOtherwise, we can divide both sides of the equation (2.1) by $\|\mathbf{G}\|_{F}\|\mathbf{H}\|_{F}$ and use the homogeneity to get an equivalent version of Proposition 1 with $\mathbf{G}=\mathbf{G}/\|\mathbf{G}\|_{F}$ and $\mathbf{H}=\mathbf{H}/\|\mathbf{H}\|_{F}$, i.e., $\|\mathbf{G}\|_{F}=\|\mathbf{H}\|_{F}=1$.. Then the assumption ($\mathcal{C}$) implies

We complete the proof by dividing both sides by $\beta+\alpha$:

where in the last inequality we use the assumption that $\beta/\alpha\leq 1.5.$ ∎

Another immediate consequence of this assumption is that if the original convex program ($\mathcal{P}_{0}$) has an optimal solution $\mathbf{X}^{\star}$ with $\operatorname{rank}(\mathbf{X}^{\star})\leq r$, then there is no other optimum of ($\mathcal{P}_{0}$) of rank less than or equal to $r$:

Suppose the function $f(\mathbf{X})$ satisfies the restricted well-conditionedness ($\mathcal{C}$). Let $\mathbf{X}^{\star}$ be an optimum of ($\mathcal{P}_{0}$) with $\operatorname{rank}(\mathbf{X}^{\star})\leq r$. Then $\mathbf{X}^{\star}$ is the unique global optimum of ($\mathcal{P}_{0}$) of rank at most $r$.

For the sake of a contradiction, suppose there exists another optimum $\mathbf{X}$ of ($\mathcal{P}_{0}$) with $\operatorname{rank}(\mathbf{X})\leq r$ and $\mathbf{X}\neq\mathbf{X}^{\star}$. We begin with the second order Taylor expansion, which reads

for some $t\in$. The KKT conditions for the convex optimization problem ($\mathcal{P}_{0}$) states that $\nabla f(\mathbf{X}^{\star})\succeq 0$ and $\nabla f(\mathbf{X}^{\star})\mathbf{X}^{\star}=\mathbf{0}$, implying that the second term in the above Taylor expansion

since $\mathbf{X}$ is feasible and hence PSD. Further, since $\operatorname{rank}(t\mathbf{X}^{\star}+(1-t)\mathbf{X})\leq\operatorname{rank}(\mathbf{X})+\operatorname{rank}(\mathbf{X}^{\star})\leq 2r$ and similarly $\operatorname{rank}(\mathbf{X}-\mathbf{X}^{\star})\leq 2r<4r$, then from the restricted well-conditionedness assumption ($\mathcal{C}$) we have

Combining all, we obtain a contradiction when $\mathbf{X}\neq\mathbf{X}^{\star}$:

where the second inequality follows from the optimality of $\mathbf{X}^{\star}$ and the third inequality holds for any $\mathbf{X}\neq\mathbf{X}^{\star}$. ∎

At a high-level, the proof essentially depends on the restricted strongly convexity of the objective function of the convex program ($\mathcal{P}_{0}$), which is guaranteed by the restricted well-conditionedness assumption ($\mathcal{C}$) on $f(\mathbf{X})$. The similar argument holds for ($\mathcal{P}_{1}$) by noting that the sum of a (restricted) strongly convex function and a standard convex function is still (restricted) strongly convex. However, showing this requires a slightly more complicated argument due to the non-smoothness of $\|\mathbf{X}\|_{*}$ around those nonsingular matrices. Mainly, we need to use the concept of subgradient.

Suppose the function $f(\mathbf{X})$ satisfies the restricted well-conditionedness ($\mathcal{C}$). Let $\mathbf{X}^{\star}$ be a global optimum of ($\mathcal{P}_{1}$) with $\operatorname{rank}(\mathbf{X}^{\star})\leq r$. Then $\mathbf{X}^{\star}$ is the unique global optimum of ($\mathcal{P}_{1}$) of rank at most $r$.

For the sake of contradiction, suppose that there exists another optimum $\mathbf{X}$ of ($\mathcal{P}_{1}$) with $\operatorname{rank}(\mathbf{X})\leq r$ and $\mathbf{X}\neq\mathbf{X}^{\star}$. We begin with the second order Taylor expansion of $f(\mathbf{X})$, which reads

for some $t\in$. From the convexity of $\|\mathbf{X}\|_{*}$, for any $\mathbf{D}\in\partial\|\mathbf{X}^{\star}\|_{*}$, we also have

where ① holds for any $\mathbf{D}\in\partial\|\mathbf{X}^{\star}\|_{*}$. For ②, we use fact that $\partial f_{1}+\partial f_{2}=\partial(f_{1}+f_{2})$ for any convex functions $f_{1},f_{2},$ to obtain that $\nabla f(\mathbf{X}^{\star})+\lambda\partial\|\mathbf{X}^{\star}\|_{*}=\partial(f(\mathbf{X}^{\star})+\lambda\|\mathbf{X}^{\star}\|_{*})$, which includes $\mathbf{0}$ since $\mathbf{X}^{\star}$ is a global optimum of ($\mathcal{P}_{1}$). Therefore, ② follows by choosing $\mathbf{D}\in\partial\|\mathbf{X}^{\star}\|_{*}$ such that $\nabla f(\mathbf{X}^{\star})+\lambda\mathbf{D}=\mathbf{0}$. ③ uses the restricted well-conditionedness assumption ($\mathcal{C}$) as $\operatorname{rank}(t\mathbf{X}^{\star}+(1-t)\mathbf{X})\leq 2r$ and $\operatorname{rank}(\mathbf{X}-\mathbf{X}^{\star})\leq 4r$. ④ comes from the assumption that both $\mathbf{X}$ and $\mathbf{X}^{\star}$ are global optimal solutions of ($\mathcal{P}_{1}$). ⑤ uses the assumption that $\mathbf{X}\neq\mathbf{X}^{\star}.$ ∎

Understanding the Factored Landscapes for PSD Matrices

In the convex program ($\mathcal{P}_{0}$), we minimize a convex function $f(\mathbf{X})$ over the PSD cone. Let $\mathbf{X}^{\star}$ be an optimal solution of ($\mathcal{P}_{0}$) of rank $r^{\star}$. We re-parameterize the low-rank PSD variable $\mathbf{X}$ as

Our primary interest is to understand how the landscape of the lifted objective function $f(\mathbf{X})$ is transformed by the factored parameterization $\phi(\mathbf{U})=\mathbf{U}\mathbf{U}^{\top}$, particularly how its global optimum is mapped to the factored space, how other types of critical points are introduced, and what their properties are.

We show that if the function $f(\mathbf{X})$ is restricted well-conditioned, then each critical point of the factored objective function $g(\mathbf{U})$ in ($\mathcal{F}_{0}$) either corresponds to the low-rank global solution of the original convex program ($\mathcal{P}_{0}$) or is a strict saddle where the Hessian $\nabla^{2}g(\mathbf{U})$ has a strictly negative eigenvalue. This implies that the factored objective function $g(\mathbf{U})$ satisfies the strict saddle property.

Suppose the function $f(\mathbf{X})$ in ($\mathcal{P}_{0}$) is twice continuously differentiable and is restricted well-conditioned ($\mathcal{C}$). Assume $\mathbf{X}^{\star}$ is an optimal solution of ($\mathcal{P}_{0}$) with $\operatorname{rank}(\mathbf{X}^{\star})=r^{\star}$. Set $r\geq r^{\star}$ in ($\mathcal{F}_{0}$). Let ${\mathbf{U}}$ be any critical point of $g(\mathbf{U})$ satisfying $\nabla g(\mathbf{U})=\mathbf{0}$. Then $\mathbf{U}$ either corresponds to a square-root factor of $\mathbf{X}^{\star}$, i.e.,

with $\rho(\cdot)$ denoting the smallest nonzero singular value of its argument. This further implies

Several remarks follow. First, the matrix $\mathbf{D}$ is the direction from the saddle point $\mathbf{U}$ to its closest globally optimal factor $\mathbf{U}^{\star}\mathbf{R}$ of the same dimension as $\mathbf{U}$. Second, our result covers both over-parameterization where $r>r^{\star}$ and exact parameterization where $r=r^{\star}$. Third, we can recover the rank-$r^{\star}$ global minimizer $\mathbf{X}^{\star}$ of ($\mathcal{P}_{0}$) by running local-search algorithms on the factored function $g(\mathbf{U})$ if we know an upper bound on the rank $r^{\star}$. In particular, to apply the results in where the first-order algorithms are proved to escape all the strict saddles, aside from the strict saddle property, one needs $g(\mathbf{U})$ to have a Lipschitz continuous gradient, i.e., $\|\nabla g(\mathbf{U})-\nabla g(\mathbf{V})\|_{F}\leq L_{c}\|U-\mathbf{V}\|_{F}$ or $\|\nabla^{2}g(\mathbf{U})\|\leq L_{c}$ for some positive constant $L_{c}$ (also known as the Lipschitz constant). As indicated by the expression of $\nabla^{2}g(\mathbf{U})$ in (3.5), it is possible that one can not find such a constant $L_{c}$ for the whole space. Similar to which considers the low-rank matrix factorization problem, suppose the local-search algorithm starts at $\mathbf{U}_{0}$ and sequentially decreases the objective value (which is true as long as the algorithm obeys certain sufficient decrease property ). Then it is adequate to focus on the sublevel set of $g$

and show that $g$ has a Lipschitz gradient on $\operatorname{Lev}_{f}({\mathbf{U}_{0}})$. This is formally established in Proposition 4, whose proof is given in Appendix A.

Under the same setting as in Theorem 3, for any initial point $\mathbf{U}_{0}$, $g(\mathbf{U})$ on $\operatorname{Lev}_{f}({\mathbf{U}_{0}})$ defined in (3.1) has a Lipschitz continuous gradient with the Lipschitz constant

where $\rho(\cdot)$ denotes the smallest nonzero singular value of its argument.

2 Metrics in the Lifted and Factored Spaces

Before continuing this geometry-based argument, it is essential to have a good understanding of the domain of the factored problem and establish a metric for this domain. Since for any $\mathbf{U}$, $\phi(\mathbf{U})=\phi(\mathbf{U}\mathbf{R})$ where $\mathbf{R}\in{\mathcal{O}}_{r}$, the domain of the factored objective function $g(\mathbf{U})$ is stratified into equivalence classes and can be viewed as a quotient manifold . The matrices in each of these equivalence classes differ by an orthogonal transformation (not necessarily unique when the rank of $\mathbf{U}$ is less than $r$). One implication is that, when working in the factored space, we should consider all factorizations of $\mathbf{X}^{\star}:$

A second implication is that when considering the distance between two points $\mathbf{U}_{1}$ and $\mathbf{U}_{2}$, one should use the distance between their corresponding equivalence classes:

An optimal solution for the orthogonal Procrustes problem:

In particular, when one matrix is of full rank, we have a similar but tighter result to relate these two distances.

3 Proof Idea: Connecting the Optimality Conditions

The proof is inspired by connecting the optimality conditions for the two programs ($\mathcal{P}_{0}$) and ($\mathcal{F}_{0}$). First of all, as the critical points of the convex optimization problem ($\mathcal{P}_{0}$), they are global optima and are characterized by the necessary and sufficient KKT condition

The factored optimization problem ($\mathcal{F}_{0}$) is unconstrained, with the critical points being specified by the zero gradient condition

To classify the critical points of ($\mathcal{F}_{0}$), we compute the Hessian quadratic form $[\nabla^{2}g(\mathbf{U})](\mathbf{D},\mathbf{D})$ as

Roughly speaking, the Hessian quadratic form has two terms – the first term involves the gradient of $f(\mathbf{X})$ and the Hessian of $\phi(\mathbf{U})$, while the second term involves the Hessian of $f(\mathbf{X})$ and the gradient of $\phi(\mathbf{U})$. Since $\phi(\mathbf{U}+\mathbf{D})=\phi(\mathbf{U})+\mathbf{U}\mathbf{D}^{\top}+\mathbf{D}\mathbf{U}^{\top}+\mathbf{D}\mathbf{D}^{\top}$, the gradient of $\phi$ is the linear operator $[\nabla\phi(\mathbf{U})](\mathbf{D})=\mathbf{U}\mathbf{D}^{\top}+\mathbf{D}\mathbf{U}^{\top}$ and the Hessian bilinear operator applies as $\frac{1}{2}[\nabla^{2}\phi(\mathbf{U})](\mathbf{D},\mathbf{D})=\mathbf{D}\mathbf{D}^{\top}$. Note in (3.5) the second quadratic form is always nonnegative since $\nabla^{2}f\succeq 0$ due to the convexity of $f$.

For any critical point $\mathbf{U}$ of $g(\mathbf{U})$, the corresponding lifted variable $\mathbf{X}:=\mathbf{U}\mathbf{U}^{\top}$ is PSD and satisfies $\nabla f(\mathbf{X})\mathbf{X}=\mathbf{0}$. On one hand, if $\mathbf{X}$ further satisfies $\nabla f(\mathbf{X})\succeq 0$, then in view of the KKT conditions (3.3) and noting $\operatorname{rank}(\mathbf{X})=\operatorname{rank}(\mathbf{U})\leq r$, we must have $\mathbf{X}=\mathbf{X}^{\star}$, the global optimum of ($\mathcal{P}_{0}$). On the other hand, if $\mathbf{X}\neq\mathbf{X}^{\star}$, implying $\nabla f(\mathbf{X})\nsucceq 0$ due to the necessity of (3.3), then additional critical points can be introduced into the factored space. Fortunately, $\nabla f(\mathbf{X})\nsucceq 0$ also implies that the first quadratic form in (3.5) might be negative for a properly chosen direction $\mathbf{D}$. To sum up, the critical points of $g(\mathbf{U})$ can be classified into two categories: the global optima in the optimal factor set ${\mathcal{A}}^{\star}$ with $\nabla f(\mathbf{U}\mathbf{U}^{\top})\succeq 0$ and those with $\nabla f(\mathbf{U}\mathbf{U}^{\top})\nsucceq 0$. For the latter case, by choosing a proper direction $\mathbf{D}$, we will argue that the Hessian quadratic form (3.5) has a strictly negative eigenvalue, and hence moving in the direction of $\mathbf{D}$ in a short distance will decrease the value of $g(\mathbf{U})$, implying that they are strict saddles and are not local minima.

Plugging this choice of $\mathbf{D}$ into the first term of (3.5), we simplify it as

where both the second line and last line follow from the critical point property $\nabla f(\mathbf{U}\mathbf{U}^{\top})\mathbf{U}=\mathbf{0}$. To gain some intuition on why (3.3) is negative while the second term in (3.5) remains small, we consider a simple example: the matrix PCA problem.

Consider the PCA problem for symmetric PSD matrices

where $\mathbf{X}^{\star}$ is a symmetric PSD matrix of rank $r^{\star}$. Trivially, the optimal solution is $\mathbf{X}=\mathbf{X}^{\star}$. Now consider the factored problem

Since $\nabla f_{\operatorname{PCA}}(\mathbf{X})=\mathbf{X}-\mathbf{X}^{\star}$, by (3.3), the first term of $[\nabla^{2}g(\mathbf{U})](\mathbf{D},\mathbf{D})$ in (3.5) becomes

which is strictly negative when $\mathbf{X}\neq\mathbf{X}^{\star}$.

This means $(\mu_{j},\mathbf{v}_{j})$ forms an eigenvalue-eigenvector pair of $\mathbf{X}^{\star}$ for each $j=1,\ldots,r^{\prime}$. Consequently,

Hence $[\nabla^{2}g(\mathbf{U})](\mathbf{D},\mathbf{D})$ is simply determined by its first term

where the second line follows from Lemma 3 and the last line follows from the fact that all the eigenvalues of $\mathbf{U}\mathbf{U}^{\top}$ come from those of $\mathbf{X}^{\star}$. Finally, we obtain the desired strict saddle property of $g(\mathbf{U})$:

This simple example is ideal in several ways, particularly the gradient $\nabla f(\phi(\mathbf{U}))=\phi(\mathbf{U})-\phi(\mathbf{U}^{\star})$, which directly establishes the negativity of the first term in (3.5); and by choosing $\mathbf{D}=\mathbf{U}-\mathbf{U}^{\star}\mathbf{R}$ and using $\mathbf{D}\mathbf{U}^{\top}=\mathbf{0}$, the second term vanishes. Neither of these simplifications hold for general objective functions $f(\mathbf{X})$. However, the example does suggest that the direction $\mathbf{D}=\mathbf{U}-\mathbf{U}^{\star}\mathbf{R}$ is a good choice to show $[\nabla^{2}g(\mathbf{U})](\mathbf{D},\mathbf{D})\leq-\tau\|\mathbf{D}\|_{F}^{2}\text{ for some }\tau>0$. For a formal proof, we will also use the direction $\mathbf{D}=\mathbf{U}-\mathbf{U}^{\star}\mathbf{R}$ to show that those critical points $\mathbf{U}$ not corresponding to $\mathbf{X}^{\star}$ have a negative directional curvature for the general factored objective function $g(\mathbf{U}).$

4 A Formal Proof of Theorem 3

We present a formal proof of Theorem 3 in this section. The main argument involves showing each critical point $\mathbf{U}$ of $g(\mathbf{U})$ either corresponds to the optimal solution $\mathbf{X}^{\star}$ or its Hessian matrix $\nabla^{2}g(\mathbf{U})$ has at least one strictly negative eigenvalue. Inspired by the discussions in Section 3.3, we will use the direction $\mathbf{D}=\mathbf{U}-\mathbf{U}^{\star}\mathbf{R}$ and show that the Hessian $\nabla^{2}g(\mathbf{U})$ has a strictly negative directional curvature in the direction of $\mathbf{D}$, i.e., $[\nabla^{2}g(\mathbf{U})](\mathbf{D},\mathbf{D})\leq-\tau\|\mathbf{D}\|_{F}^{2},\text{ for some }\tau>0.$

We first list two lemmas. The first lemma separates $\|(\mathbf{U}-\mathbf{Z}){\mathbf{U}}^{\top}\|_{F}^{2}$ into two terms: $\|\mathbf{U}\mathbf{U}^{\top}-\mathbf{Z}\mathbf{Z}^{\top}\|_{F}^{2}$ and $\|(\mathbf{U}\mathbf{U}^{\top}-\mathbf{Z}\mathbf{Z}^{\top}){\mathbf{Q}}{\mathbf{Q}}^{\top}\|_{F}^{2}$ with $\mathbf{Q}\mathbf{Q}^{\top}$ being the projection matrix onto $\operatorname{Range}(\mathbf{U})$. It is crucial for the first term $\|\mathbf{U}\mathbf{U}^{\top}-\mathbf{Z}\mathbf{Z}^{\top}\|_{F}^{2}$ to have a small coefficient. In the second lemma, we will further control the second term as a consequence of $\mathbf{U}$ being a critical point. The proof of Lemma 5 is given in Section C.

Next, we control the distance between $\mathbf{U}\mathbf{U}^{\top}$ and the global solution $\mathbf{X}^{\star}$ when $\mathbf{U}$ is a critical point of the factored objective function $g(\mathbf{U})$, i.e., $\nabla g(\mathbf{U})=\mathbf{0}$. The proof, given in Section D, relies on writing $\nabla f(\mathbf{X})=\nabla f(\mathbf{X}^{\star})+\int_{0}^{1}[\nabla^{2}f(t\mathbf{X}+(1-t)\mathbf{X}^{\star})](\mathbf{X}-\mathbf{X}^{\star})dt$ and applying Proposition 1.

Suppose the objective function $f(\mathbf{X})$ in ($\mathcal{P}_{0}$) is twice continuously differentiable and satisfies the restricted well-conditionedness assumption ($\mathcal{C}$). Further, let $\mathbf{U}$ be any critical point of ($\mathcal{F}_{0}$) and $\mathbf{Q}$ be the orthonormal basis spanning $\operatorname{Range}(\mathbf{U})$. Then

In the following, we will bound $\Pi_{1}$ and $\Pi_{2}$, respectively.

where ① follows from the Taylor’s Theorem for vector-valued functions [39, Eq. (2.5) in Theorem 2.1], and ② follows from the restricted strong convexity assumption ($\mathcal{C}$) since the PSD matrix $t\mathbf{X}+(1-t)\mathbf{X}^{\star}$ has rank of at most $2r$ and $\operatorname{rank}(\mathbf{X}^{\star}-\mathbf{X})\leq 4r.$

Then, we relate the lifted distance $\|\mathbf{X}^{\star}-\mathbf{X}\|_{F}^{2}$ with the factored distance $\|\mathbf{U}-\mathbf{U}^{\star}\mathbf{R}\|_{F}^{2}$ using Lemma 3 when $r>r^{\star}$, and Lemma 4 when $r=r^{\star}$, respectively:

For the special case where $\mathbf{U}=\mathbf{0}$, we have

and the last line follows from $\mathbf{D}=\mathbf{0}-\mathbf{U}^{\star}\mathbf{R}=-\mathbf{U}^{\star}\mathbf{R}$ when $\mathbf{U}=\mathbf{0}.$ Here $\sigma_{i}(\cdot)$ denotes the $i$-th largest singular value of its argument. ∎

Understanding the Factored Landscapes for General Non-square Matrices

In this section, we will study the second convex program ($\mathcal{P}_{1}$): the minimization of a general convex function $f(\mathbf{X})$ regularized by the matrix nuclear norm $\|\mathbf{X}\|_{*}$ with the domain being general matrices. Since the matrix nuclear norm $\|\mathbf{X}\|_{*}$ appears in the objective function, the standard convex solvers or even faster tailored ones require performing singular value decomposition in each iteration, which severely limits the efficiency and scalability of the convex program. Motivated by this, we will instead solve its Burer-Monteiro re-parameterized counterpart.

Recall the second problem is the nuclear norm regularization ($\mathcal{P}_{1}$):

This convex program has an equivalent SDP formulation [43, page 8]:

When the PSD constraint is implicitly enforced as the following equality constraint

we obtain the Burer-Monteiro factored reformulation ($\mathcal{F}_{1}$):

The factored formulation ($\mathcal{F}_{1}$) can potentially solve the computational issue of ($\mathcal{P}_{1}$) in two major respects: (i) avoiding expensive SVDs by replacing the nuclear norm $\|\mathbf{X}\|_{*}$ with the squared term $(\|\mathbf{U}\|_{F}^{2}+\|\mathbf{V}\|_{F}^{2})/2$; (ii) a substantial reduction in the number of the optimization variables from $nm$ to $(n+m)r$.

2 Transforming the Landscape for General Non-square Matrices

Our primary interest is to understand how the landscape of the lifted objective function $f(\mathbf{X})+\lambda\|\mathbf{X}\|_{*}$ is transformed by the factored parameterization $\psi(\mathbf{U},\mathbf{V})=\mathbf{U}\mathbf{V}^{\top}$. The main contribution of this part is establishing that under the restricted well-conditionedness of the convex loss function $f(\mathbf{X})$, the factored formulation ($\mathcal{F}_{1}$) has no spurious local minima and satisfies the strict saddle property.

Suppose the function $f(\mathbf{X})$ satisfies the restricted well-conditioned property ($\mathcal{C}$). Assume that $\mathbf{X}^{\star}$ of rank $r^{\star}$ is an optimal solution of ($\mathcal{P}_{1}$) where $\lambda>0$. Set $r\geq r^{\star}$ in the factored program ($\mathcal{F}_{1}$). Let ${(\mathbf{U},\mathbf{V})}$ be any critical point of $g(\mathbf{U},\mathbf{V})$ satisfying $\nabla g(\mathbf{U},\mathbf{V})=\mathbf{0}$. Then $(\mathbf{U},\mathbf{V})$ either corresponds to a factorization of $\mathbf{X}^{\star}$, i.e.,

or is a strict saddle of the factored problem:

where $W:=\begin{bmatrix}\mathbf{U}^{\top}&\mathbf{V}^{\top}\end{bmatrix}^{\top}$ and $\rho(\mathbf{W})$ is the smallest nonzero singular value of $\mathbf{W}$.

Theorem 4 ensures that many local-search algorithmsThe Lipschitz gradient of $g$ at any its sublevel set can be obtained with similar approach for Proposition 4. when applied for solving the factored program ($\mathcal{F}_{1}$), can escape from all the saddle points and converge to a global solution that corresponds to $\mathbf{X}^{\star}$. Several remarks follow.

Although the generalization from the PSD case might not seem technically challenging at first sight, we must overcome several technical difficulties to prove this main theorem. We make a few other technical contributions in the process. In fact, the non-triviality of extending to the nonsymmetric case is also highlighted in . The major technique difficulty to complete such an extension is the ambiguity issue existed in the nonsymmetric case: $\mathbf{U}\mathbf{V}^{\top}=(t\mathbf{U})(1/t\mathbf{V})^{\top}$ for any nonzero $t$. This tends to make the factored quadratic objective function badly-conditioned, especially when $t$ is very large or small. To prevent this from happening, a popular strategy utilized to adapt the result for the symmetric case to the non-symmetric case is to introduce an additional balancing regularization to ensure that $\mathbf{U}$ and $\mathbf{V}$ have equal energy . Sometimes these additional regularizations are quite complicated (see Eq. (13)-(15) in ). Instead, we find for nuclear norm regularized problems, the critical points are automatically balanced even without these additional complex balancing regularizations (see Section 4.4 for details). In addition, by connecting the optimality conditions of the convex program ($\mathcal{P}_{1}$) and the factored program ($\mathcal{F}_{1}$), we dramatically simplify the proof argument, making the relationship between the original convex problem and the factored program more transparent.

We try to understand how the parameterization $\mathbf{X}=\psi(\mathbf{U},\mathbf{V})$ transforms the geometric structures of the convex objective function $f(\mathbf{X})$ by categorizing the critical points of the non-convex factored function $g(\mathbf{U},\mathbf{V})$. In particular, we will illustrate how the globally optimal solution of the convex program is transformed in the domain of $g(\mathbf{U},\mathbf{V})$. Furthermore, we will explore the properties of the additional critical points introduced by the parameterization and find a way of utilizing these properties to prove the strict saddle property. For those purposes, the optimality conditions for the two programs ($\mathcal{P}_{1}$) and ($\mathcal{F}_{1}$) will be compared.

3 Optimality Condition for the Convex Program

As an unconstrained convex optimization, all critical points of ($\mathcal{P}_{1}$) are global optima and are characterized by the necessary and sufficient KKT condition :

where $\partial\|\mathbf{X}^{\star}\|_{*}$ denotes the subdifferential (the set of subgradient) of the nuclear norm $\|\mathbf{X}\|_{*}$ evaluated at $\mathbf{X}^{\star}$. The subdifferential of the matrix nuclear norm is defined by

Combining this representation of the subdifferential and the KKT condition (4.3) yields an equivalent expression for the optimality condition

where we assume the compact SVD of $\mathbf{X}^{\star}$ is given by

Consequently, with the optimal factors $\mathbf{U}^{\star},\mathbf{V}^{\star}$ defined in (4.5), we can rewrite the optimal condition (4.4) as

Stacking $\mathbf{U}^{\star},\mathbf{V}^{\star}$ as $\mathbf{W}^{\star}=\begin{bmatrix}\mathbf{U}^{\star}\\ \mathbf{V}^{\star}\end{bmatrix}$ and defining

yields a more concise form of the optimality condition:

4 Characterizing the Critical Points of the Factored Program

To begin with, the gradient of $g(\mathbf{U},\mathbf{V})$ can be computed and rearranged as

where the last equality follows from the definition (4.7) of $\Xi(\cdot)$. Therefore, all critical points of $g(\mathbf{U},\mathbf{V})$ can be characterized by the following set

We will see that any critical point $(\mathbf{U},\mathbf{V})\in{\mathcal{X}}$ forms an balanced pair, which is defined as follows:

We call $(\mathbf{U},\mathbf{V})$ is a balanced pair if the Gram matrices of $\mathbf{U}$ and $\mathbf{V}$ are the same: $\mathbf{U}^{\top}\mathbf{U}-\mathbf{V}^{\top}\mathbf{V}=\mathbf{0}.$ All the balanced pairs form the balanced set, denoted by ${\mathcal{E}}:=\left\{(\mathbf{U},\mathbf{V}):\mathbf{U}^{\top}\mathbf{U}-\mathbf{V}^{\top}\mathbf{V}=\mathbf{0}\right\}.$

By Definition 5, to show that each critical point forms an balanced pair, we rely on the following fact:

Now we are ready to relate the critical points and balanced pairs, the proof of which is given in Appendix E.

Any critical point $(\mathbf{U},\mathbf{V})\in{\mathcal{X}}$ forms a balanced pair in ${\mathcal{E}}.$

In this part, we introduce some important properties of the balanced set ${\mathcal{E}}$. These properties basically compare the on-diagonal-block energy and the off-diagonal-block energy for a certain block matrix. Hence, it is necessary to introduce two operators defined on block matrices:

According to the definitions of $\mathcal{P_{\operatorname{on}}}$ and $\mathcal{P_{\operatorname{off}}}$ in (4.11), when $\mathcal{P_{\operatorname{on}}}$ and $\mathcal{P_{\operatorname{off}}}$ are acting on the product of two block matrices $\mathbf{W}_{1}\mathbf{W}_{2}^{\top}$,

Now, we are ready to present the properties regarding the set ${\mathcal{E}}$ in Lemma 7 and Lemma 8, whose proofs are given in Appendix F and Appendix G, respectively.

Let $\mathbf{W}=\begin{bmatrix}\mathbf{U}^{\top}&\mathbf{V}^{\top}\end{bmatrix}^{\top}$ with $(\mathbf{U},\mathbf{V})\in{\mathcal{E}}$. Then for every $\mathbf{D}=\begin{bmatrix}\mathbf{D}_{\mathbf{U}}^{\top}&\mathbf{D}_{\mathbf{V}}^{\top}\end{bmatrix}^{\top}$ of proper dimension, we have

Let $\mathbf{W}_{1}=\begin{bmatrix}\mathbf{U}_{1}^{\top}&\mathbf{V}_{1}^{\top}\end{bmatrix}^{\top}$, $\mathbf{W}_{2}=\begin{bmatrix}\mathbf{U}_{2}^{\top}&\mathbf{V}_{2}^{\top}\end{bmatrix}^{\top}$ with $(\mathbf{U}_{1},\mathbf{V}_{1}),(\mathbf{U}_{2},\mathbf{V}_{2})\in{\mathcal{E}}$. Then

5 Proof Idea: Connecting the Optimality Conditions

First observe that each $(\mathbf{U}^{\star},\mathbf{V}^{\star})$ in (4.5) is a global optimum for the factored program (we prove this in Appendix H):

Any $(\mathbf{U}^{\star},\mathbf{V}^{\star})$ in (4.5) is a global optimum of the factored program ($\mathcal{F}_{1}$):

However, due to non-convexity, only characterizing the global optima is not enough for the factored program to achieve the global convergence by many local-search algorithms. One should also eliminate the possibility of the existence of spurious local minima or degenerate saddles. For this purpose, we focus on the critical point set ${\mathcal{X}}$ and observe that any critical point $(\mathbf{U},\mathbf{V})\in{\mathcal{X}}$ of the factored problem satisfies the first part of the optimality condition (4.8):

Therefore, it remains to study the additional critical points (which are introduced by the parameterization $\mathbf{X}=\psi(\mathbf{U},\mathbf{V})$) that violate $\|\nabla f(\mathbf{U}\mathbf{V}^{\top})\|\leq\lambda$. In fact, we intend to show the following: for any critical point $(\mathbf{U},\mathbf{V})$, if $\mathbf{X}^{\star}\neq\mathbf{U}\mathbf{V}^{\top}$, we can find a direction $\mathbf{D}$, in which the Hessian $\nabla^{2}g(\mathbf{U},\mathbf{V})$ has a strictly negative curvature $[\nabla^{2}g(\mathbf{U},\mathbf{V})](\mathbf{D},\mathbf{D})<-\tau\|\mathbf{D}\|_{F}^{2}$ for some $\tau>0$. Hence, every critical point $(\mathbf{U},\mathbf{V})$ either corresponds to the global optimum $\mathbf{X}^{\star}$, or is a strict saddle point.

where the second term is always nonnegative by the convexity of $f$. The sign of the first term $\langle\Xi(\mathbf{X}),\mathbf{D}\mathbf{D}^{\top}\rangle$ depends on the positive semi-definiteness of $\Xi(\mathbf{X})$, which is related to the boundedness condition $\|\nabla f(\mathbf{X})\|\leq\lambda$ through the Schur complement theorem [8, A.5.5]:

Equivalently, whenever $\|\nabla f(\mathbf{X})\|>\lambda$, we have $\Xi(\mathbf{X})\nsucceq 0$. Therefore, for those non-globally optimal critical points $(\mathbf{U},\mathbf{V})$, it is possible to find a direction $\mathbf{D}$ such that the first term $\langle\Xi(\mathbf{X}),\mathbf{D}\mathbf{D}^{\top}\rangle$ is strictly negative. Inspired by the weighted PCA example, we choose $\mathbf{D}$ as the direction from the critical point $\mathbf{W}=\begin{bmatrix}\mathbf{U}^{\top}&\mathbf{V}^{\top}\end{bmatrix}^{\top}$ to the nearest globally optimal factor $\mathbf{W}^{\star}\mathbf{R}$ with $\mathbf{W}^{\star}=\begin{bmatrix}{\mathbf{U}^{\star}}^{\top}&{\mathbf{V}^{\star}}^{\top}\end{bmatrix}^{\top}$, i.e.,

6 A Formal Proof of Theorem 4

Suppose the function $f(\mathbf{X})$ in ($\mathcal{P}_{1}$) is restricted well-conditioned ($\mathcal{C}$). Let $\mathbf{W}=\begin{bmatrix}\mathbf{U}^{\top}&\mathbf{V}^{\top}\end{bmatrix}^{\top}$ with $(\mathbf{U},\mathbf{V})\in{\mathcal{X}}$, $\mathbf{W}^{\star}=\begin{bmatrix}{\mathbf{U}^{\star}}^{\top}&{\mathbf{V}^{\star}}^{\top}\end{bmatrix}^{\top}$ correspond to the global optimum of ($\mathcal{P}_{1}$) and $\mathbf{Q}\mathbf{Q}^{\top}$ be the orthogonal projector onto $\operatorname{Range}(\mathbf{W})$. Then

where ① follows from $\nabla g(\mathbf{U},\mathbf{V})=\Xi(\mathbf{X})\mathbf{W}=\mathbf{0}$ and (4.9). For ②, we note that $\langle\Xi(\mathbf{X}^{\star}),\mathbf{W}^{\star}\mathbf{W}^{\star\top}-\mathbf{W}\mathbf{W}^{\top}\rangle\leq 0$ since $\Xi(\mathbf{X}^{\star})\mathbf{W}^{\star}=\mathbf{0}$ in (4.8) and $\Xi(\mathbf{X}^{\star})\succeq 0$ by the optimality condition. For ③, we first use $*=(\int_{0}^{1}[\nabla^{2}f(\mathbf{X}^{\star}+t(\mathbf{X}-\mathbf{X}^{\star}))](\mathbf{X}-\mathbf{X}^{\star})dt)^{\top}$ for convenience and then it follows from the Taylor’s Theorem for vector-valued functions [39, Eq. (2.5) in Theorem 2.1]:

where ④ uses the restricted well-conditionedness ($\mathcal{C}$) since $\operatorname{rank}(\mathbf{X}^{\star}+t(\mathbf{X}-\mathbf{X}^{\star}))\leq 2r$, $\operatorname{rank}(\mathbf{X}-\mathbf{X}^{\star})\leq 4r$ and $\operatorname{rank}(\mathbf{D}_{\mathbf{U}}\mathbf{V}^{\top}+\mathbf{U}\mathbf{D}_{\mathbf{V}}^{\top})\leq 4r.$ ⑤ comes from Lemma 8 and the fact $\|\mathbf{A}+\mathbf{B}\|_{F}^{2}\leq 2(\|\mathbf{A}\|_{F}^{2}+\|\mathbf{B}\|_{F}^{2})$. ⑥ follows from Lemma 7. ⑦ first uses Lemma 5 to bound $\|\mathbf{D}\mathbf{W}^{\top}\|_{F}^{2}=\|(\mathbf{W}-\mathbf{W}^{\star}\mathbf{R})\mathbf{W}^{\top}\|_{F}^{2}$ since $\mathbf{W}^{\top}\mathbf{W}^{\star}\succeq 0$ and then uses Lemma 9 to further bound $\|(\mathbf{W}^{\star}-\mathbf{W})\mathbf{Q}\mathbf{Q}^{\top}\|_{F}^{2}$. ⑧ holds when $\beta/\alpha\leq 1.5$. ⑨ uses the similar argument as in the proof of Theorem 3 to relate the lifted distance and factored distance. Particularly, three possible cases are considered: (i) $r>r^{\star}$; (ii) $r=r^{\star}$; (iii) $\mathbf{W}=\mathbf{0}$. We apply Lemma 3 to Case (i) and Lemma 4 to Case (ii). For the third case that $\mathbf{W}=\mathbf{0}$, we obtain from ⑧ that