Dropping Convexity for Faster Semi-definite Optimization

Introduction

Consider the following standard convex semi-definite optimization problem:

Problems (1) and (2) will have the same optimum when $r=r^{\star}$. However, the recast problem is unconstrained and leads to computational gains in practice: e.g., iterative update schemes, like gradient descent, do not need to do eigen-decompositions to satisfy semi-definite constraints at every iteration.

In this paper, we also consider the case of $r<r^{\star}$, which often occurs in applications. The reasons of such a choice chould be three-fold: $(i)$ it might model better an underlying task (e.g., $f$ may have arisen from a relaxation of a rank constraint in the first place), $(ii)$ it leads to computational gains, since smaller $r$ means fewer variables to maintain and optimize, $(iii)$ it leads to statistical “gains”, as it might prevent over-fitting in machine learning or inference problems.

Such recasting of matrix optimization problems is empirically widely popular, especially as the size of problem instances increases. Some applications in modern machine learning includes matrix completion , affine rank minimization , covariance / inverse covariance selection , phase retrieval , Euclidean distance matrix completion , finding the square root of a PSD matrix , and sparse PCA , just to name a few. Typically, one can solve (2) via simple, first-order methods on $U$ like gradient descent. Unfortunately, such procedures have no guarantees on convergence to the optima of the original $f$, or on the rate thereof. Our goal in this paper is to provide such analytical guarantees, by using—simply and transparently—standard convexity properties of the original $f$.

Overview of our results. In this paper, we prove that updating $U$ via gradient descent in (2) converges (fast) to optimal (or near-optimal) solutions. While there are some recent and very interesting works that consider using such non-convex parametrization , their results only apply to specific examples. To the best of our knowledge, this is the first paper that solves the re-parametrized problem with attractive convergence rate guarantees for general convex functions $f$ and under common convex assumptions. Moreover, we achieve the above by assuming the first order oracle model: for any matrix $X$, we can only obtain the value $f(X)$ and the gradient $\nabla f(X)$.

To achieve the desiderata, we study how gradient descent over $U$ performs in solving (2). This leads to the factored gradient descent (Fgd) algorithm, which applies the simple update rule

We provide a set of sufficient conditions to guarantee convergence. We show that given a suitable initialization point, Fgd converges to a solution close to the optimal point in sublinear or linear rate, depending on the nature of $f$.

Our contributions in this work can be summarized as follows:

New step size rule and Fgd. Our main algorithmic contribution is a special choice of the step size $\eta$. Our analysis showcase that $\eta$ needs to depend not only on the convexity parameters of $f$ (as is the case in standard convex optimization) but also on the top singular value of the unknown optimum. Section 3 describes the precise step size rule, and also the intuition behind it. Of course, the optimum is not known a priori. As a solution in practice, we show that choosing $\eta$ based on a point that is constant relative distance from the optimum also provably works.

Convergence of Fgd under common convex assumptions. We consider two cases: $(i)$ when $f$ is just a $M$-smooth convex function, and $(ii)$ when $f$ satisfies also restricted strong convexity (RSC), i.e., $f$ satisfies strong-convexity-like conditions, but only over low rank matrices; see next section for definitions. Both cases are based on now-standard notions, common for the analysis of convex optimization algorithms. Given a good initial point, we show that, when $f$ is $M$-smooth, Fgd converges sublinearly to an optimal point $X^{\star}$. For the case where $f$ has RSC, Fgd converges linearly to the unique $X^{\star}$, matching analogous result for classic gradient descent schemes, under smoothness and strong convexity assumptions.

Furthermore, for the case of smooth and strongly convex $f$, our analysis extends to the case $r<r^{\star}$, where Fgd converges to a point close to the best rank-$r$ approximation of $X^{\star}$.In this case, we require $\|X^{\star}-X^{\star}_{r}\|_{F}$ to be small enough, such that the rank-constrained optimum be close to the best rank-$r$ approximation of $X^{\star}$. This assumption naturally applies in applications, where e.g., $X^{\star}$ is a superposition of a low rank latent matrix, plus a small perturbation term . In Section I, we show how this assumption can be dropped by using a different step size $\eta$, where spectral norm computation of two $n\times r$ matrices is required per iteration.

Both results hold when Fgd is initialized at a point with constant relative distance from optimum. Interestingly, the linear convergence rate factor depends not only on the convexity parameters of $f$, but also on the spectral characteristics of the optimum; a phenomenon borne out in our experiments. Section 4 formally states these results.

Initialization: For specific problem settings, various initialization schemes are possible (see ). In this paper, we extend such results to the case where we only have access to $f$ via the first-order oracle: specifically, we initialize based on the gradient at zero, i.e., $\nabla f(0)$. We show that, for certain condition numbers of $f$, this yields a constant relative error initialization (Section 5). Moreover, Section 5 lists alternative procedures that lead to good initialization points and comply with our theory.

The rest of the paper is organized as follows. Section 2 contains basic notation and standard convex definitions. Section 3 presents the Fgd algorithm and the step size $\eta$ used, along with some intuition for its selection. Section 4 contains the convergence guarantees of Fgd; the main supporting lemmas and proofs of the main theorems are provided in Section 6. In Section 5, we discuss some initialization procedures that guarantee a “decent” starting point for Fgd. This paper concludes with discussion on related work (Section 7).

Preliminaries

For any general symmetric matrix $X$, let the matrix $\mathcal{P}_{+}(X)$ be its projection onto the set of PSD matrices. This can be done by finding all the strictly positive eigenvalues and corresponding eigenvectors $(\lambda_{i},v_{i}:\lambda_{i}>0)$ and then forming $\mathcal{P}_{+}(X)=\sum_{i:\lambda_{i}>0}\lambda_{i}v_{i}v_{i}^{\top}$.

$\mathcal{O}$ is the set of $r\times r$ orthonormal matrices $R$, such that $R^{\top}R=I_{r\times r}$. The optimal $R$ satisfies $PQ^{\top}$ where $P\Sigma Q^{\top}$ is the singular value decomposition of $V^{\top}U$.

Assumptions. We will investigate the performance of non-convex gradient descent for functions $f$ that satisfy standard smoothness conditions only, as well as the case where $f$ further is (restricted) strongly convex. We state these standard definitions below.

This further implies the following upper bound:

Given the above definitions, we define $\kappa=\frac{M}{m}$ as the condition number of function $f$.

Finally, in high dimensional settings, often loss function $f$ does not satisfy strong convexity globally, but only on a restricted set of directions; see and Section F for a more detailed discussion.

A convex function $f$ is $(m,r)$-restricted strongly convex if:

Factored gradient descent

We solve the non-convex problem (2) via Factored Gradient Descent (Fgd) with update ruleThe true gradient of $f$ with respect to $U$ is $2\nabla f(UU^{\top})\cdot U$. However, for simplicity and clarity of exposition, in our algorithm and its theoretical guarantees, we absorb the 2-factor in the step size $\eta$.:

Fgd does this, but with two key innovations: a careful initialization and a special step size $\eta$. The discussion on the initialization is deferred until Section 5.

Even though $f$ is a convex function over $X\succeq 0$, the fact that we operate with the non-convex $UU^{\top}$ parametrization means that we need to be careful about the step size $\eta$; e.g., our constant $\eta$ selection should be such that, when we are close to $X^{\star}$, we do not “overshoot” the optimum $X^{\star}$.

In this work, we pick the step size parameter, according to the following closed-formConstant $16$ in the expression (8) appears due to our analysis, where we do not optimize over the constants. One can use another constant in order to be more aggressive; nevertheless, we observed that our setting works well in practice. :

Recall that, if we were just doing standard gradient descent on $f$, we would choose a step size of $\nicefrac{{1}}{{M}}$, where $M$ is a uniform upper bound on the largest eigenvalue of the Hessian $\nabla^{2}f(\cdot)$.

Standard convex optimization suggests that $\eta$ should be chosen such that $\eta<\nicefrac{{1}}{{\|\nabla^{2}g(\cdot)\|_{2}}}$. The above suggest the following step size selection rule for $M$-smooth $f$:

In stark contrast with classic convex optimization where $\eta\propto\tfrac{1}{M}$, the step size selection further depends on the spectral information of the current iterate and the gradient. Since computing $\left\|X\right\|_{2},\|\nabla f(X)\|_{2}$ per iteration could be computational inefficient, we use the spectral norm of $X^{0}$ and its gradient $\nabla f(X^{0})$ as surrogate, where $X^{0}$ is the initialization pointHowever, as we show in Section I, one could compute $\|X\|_{2}$ and $\|\nabla f(X)\|_{2}$ per iteration in order to relax some of the requirements of our approach..

To clarify $\eta$ selection further, we next describe a toy example, in order to illustrate the necessity of such a scaling of the step size. Consider the following minimization problem.

Consider the case where $u=\tfrac{\alpha}{2}v_{1}+\tfrac{\beta}{10}v_{2}$ is the current estimate. Then, the gradient of $f$ at $u$ is evaluated as:

Hence, according to the update rule $u^{+}=u-2\eta\nabla f(uu^{\top})\cdot u$, the next iterate satisfies:

Observe that coefficients of both $v_{1},~{}v_{2}$ in $u^{+}$ include $O(\alpha^{3})$ and $O(\beta^{3})$ quantities.

The quality of $u^{+}$ clearly depends on how $\eta$ is chosen. In the case $\eta=\tfrac{1}{M}=\tfrac{1}{2}$, such step size can result in divergence$/$“overshooting”, as $\|X^{\star}\|_{2}=O(\alpha^{2})$ and $\|\nabla f(X^{\star})\|_{2}=O(\beta^{2})$ can be arbitrarily large (independent of $M$). Therefore, it could be the case that ${\rm{\textsc{Dist}}}(u^{+},u^{\star})>{\rm{\textsc{Dist}}}(u,u^{\star})$.

In contrast, consider the step sizeFor illustration purposes, we consider a step size that depends on the unknown $X^{\star}$; in practice, our step size selection is a surrogate of this choice and our results automatically carry over, with appropriate scaling. $\eta=\tfrac{1}{16(M\|X^{\star}\|_{2}+\|\nabla f(X^{\star})\|_{2})}\propto\tfrac{1}{C(\alpha^{2}+\beta^{2})}$. Then, with appropriate scaling $C$, we observe that $\eta$ lessens the effect of $O(\alpha^{3})$ and $O(\beta^{3})$ terms in $v_{1}$ and $v_{2}$ terms, that lead to overshooting for the case $\eta=\tfrac{1}{2}$. This most possibly result in ${\rm{\textsc{Dist}}}(u^{+},u^{\star})\leq{\rm{\textsc{Dist}}}(u,u^{\star})$.

Computational complexity.

The per iteration complexity of Fgd is dominated by the gradient computation. This computation is required in any first order algorithm and the complexity of this operation depends on the function $f$. Apart from $\nabla f(X)$, the additional computation required in Fgd is matrix-matrix additions and multiplications, with time complexity upper bounded by $\text{{nnz}}(\nabla f(\cdot))\cdot r$, where $\text{{nnz}}(\nabla f(\cdot))$ denotes the number of non zeros in the gradient at the current point.It could also occur that gradient $\nabla f(X)$ is low-rank, or low-rank + sparse, depending on the problem at hand; it could also happen that the structure of $\nabla f(X)$ leads to “cheap” matrix-vector calculations, when applied to vectors. Here, we state a more generic –and maybe pessimistic– scenario where $\nabla f(X)$ is unstructured. Hence, the per iteration complexity of Fgd is much lower than traditional convex methods like projected gradient descent or classic interior point methods , as they often require a full eigenvalue decomposition per step.

Note that, for $r=O(n)$, Fgd and projected gradient descent have same per iteration complexity of $O(n^{3})$. However, Fgd performs only a single matrix-matrix multiplication operation, which is much “cheaper” than a SVD calculation. Moreover, matrix multiplication is an easier-to-parallelize operation, as opposed to eigen decomposition operation which is inherently sequential. We notice this behavior in practice; see Sections F, G and H for applications in matrix sensing and quantum state tomography.

Local convergence of Fgd

In this section, we present our main theoretical results on the performance of Fgd. We present convergence rates for the settings where $(i)$ $f$ is a $M$-smooth convex function, and $(ii)$ $f$ is a $M$-smooth and $(m,r)$-restricted strongly convex function. These assumptions are now standard in convex optimization. Note that, since the $UU^{\top}$ factorization makes the problem non-convex, it is hard to guarantee convergence of gradient descent schemes in general, without any additional assumptions.

We now state the main assumptions required by Fgd for convergence:

${\rm{\textsc{Dist}}}(U^{0},U^{\star}_{r})\leq\rho\sigma_{r}(U^{\star}_{r})$ for $\rho:=\frac{1}{100}\frac{\sigma_{r}(X^{\star})}{\sigma_{1}(X^{\star})}$ (Smooth $f$)

${\rm{\textsc{Dist}}}(U^{0},U^{\star}_{r})\leq\rho^{\prime}\sigma_{r}(U^{\star}_{r})$ for $\rho^{\prime}:=\frac{1}{100\kappa}\frac{\sigma_{r}(X^{\star})}{\sigma_{1}(X^{\star})}$ (Strongly convex $f$),

In many applications, an initial point $U^{0}$ with this type of guarantees is easy to obtain, often with just one eigenvalue decomposition; we refer the reader to the works for specific initialization procedures for different problem settings. See also Section 5 for a more detailed discussion. Note that the problem is still non-trivial after the initialization, as this only gives a constant error approximation.

Approximate rank-$r$ optimum: In many learning applications, such as localization and multilabel learning , the true $X^{\star}$ emerges as the superposition of a low rank latent matrix plus a small perturbation term, such that $\|X^{\star}-X^{\star}_{r}\|_{F}$ is small. While, in practice, it might be the case $\text{rank}(X^{\star})=n$—due to the presence of noise—often we are more interested in revealing the latent low-rank part. As already mentioned, we might as well set $r<\text{rank}(X^{\star})$ for computational or statistical reasons. In all these cases, further assumptions w.r.t. the quality of approximation have to be made. In particular, let $X^{\star}$ be the optimum of (1) and $f$ is $M$-smooth and $(m,r)$-strongly convex. In our analysis, we assume:

$\|X^{\star}-X^{\star}_{r}\|_{F}\leq\frac{1}{200\kappa^{1.5}}\frac{\sigma_{r}(X^{\star})}{\sigma_{1}(X^{\star})}\sigma_{r}(X^{\star})$ (Strongly convex $f$),

This assumption intuitively requires the noise magnitude to be smaller than the optimum and constrains the rank constrained optimum to be closer to $X^{\star}_{r}$.Note that the assumption $(A3)$ can be dropped by using a different step size $\eta$ (see Theorem I.4 in Section I). However, this requires two additional spectral norm computations per iteration.

We note that, in the results presented below, we have not attempted to optimize over the constants appearing in the assumptions and any intermediate steps of our analysis. Finding such tight constants could strengthen our arguments for fast convergence; however, it does not change our claims for sublinear or linear convergence rates. Moreover, we consider the case $r\leq\text{rank}(X^{\star})$; we believe the analysis can be extended to the setting $r>\text{rank}(X^{\star})$ and leave it for future work.Experimental results on synthetic matrix sensing settings have shown that, if we overshoot $r$, i.e., $r>\text{rank}(X^{\star})$, Fgd still performs well, finding an $\varepsilon$-accurate solution with linear rate.

Next, we state our first main result under smoothness condition, as in Definition 2.3. In particular, we prove that Fgd makes progress per iteration with sublinear rate. Here, we assume only the case where $r=r^{\star}$; for consistency reasons, we denote $X^{\star}=X^{\star}_{r}$. Key lemmas and their proofs for this case are provided in Section C.

Let $X^{\star}_{r}=U^{\star}_{r}U_{r}^{\star^{\top}}$ denote an optimum of $M$-smooth $f$ over the PSD cone. Let $f(X^{0})>f(X^{\star}_{r})$. Then, under assumption $(A1)$, after $k$ iterations, the FGD algorithm finds solution $X^{k}$ such that

The theorem states that provided $(i)$ we choose the step size $\eta$, based on a starting point that has constant relative distance to $U^{\star}_{r}$, and $(ii)$ we start from such a point, gradient descent on $U$ will converge sublinearly to a point $X^{\star}_{r}$. In other words, Theorem 4.1 shows that Fgd computes a sequence of estimates in the $U$-factor space such that the function values decrease with $O\left(\tfrac{1}{k}\right)$ rate, towards a global minimum of $f$ function. Recall that, even in the standard convex setting, classic gradient descent schemes over $X$ achieve the same $O\left(\tfrac{1}{k}\right)$ convergence rate for smooth convex functions . Hence, Fgd matches the rate of convex gradient descent, under the assumptions of Theorem 4.1. The above are abstractly illustrated in Figure 1.

2 Linear convergence rate under strong convexity assumption

Let the current iterate be $U$ and $X=UU^{\top}$. Assume ${\rm{\textsc{Dist}}}(U,U^{\star}_{r})\leq\rho^{\prime}\sigma_{r}(U^{\star}_{r})$ and let the step size be $\eta=\frac{1}{16\,(M\left\|X^{0}\right\|_{2}+\left\|\nabla f(X^{0})\right\|_{2})}$. Then under assumptions $(A2),(A3)$, the new estimate ${U}^{\scalebox{0.7}{+}}=U-\eta\nabla f(X)\cdot U$ satisfies

where $\alpha=1-\frac{m\sigma_{r}(X^{\star})}{64(M\|X^{\star}\|_{2}+\|\nabla f(X^{\star})\|_{2})}$ and $\beta=\frac{M}{28(M\|X^{\star}\|_{2}+\|\nabla f(X^{\star})\|_{2})}$. Furthermore, ${U}^{\scalebox{0.7}{+}}$ satisfies ${\rm{\textsc{Dist}}}({U}^{\scalebox{0.7}{+}},U^{\star}_{r})\leq\rho^{\prime}\sigma_{r}(U^{\star}_{r}).$

The theorem states that provided $(i)$ we choose the step size based on a point that has constant relative distance to $U^{\star}_{r}$, and $(ii)$ we start from such a point, gradient descent on $U$ will converge linearly to a neighborhood of $U^{\star}_{r}$. The above theorem immediately implies linear convergence rate for the setting where $f$ is standard strongly convex, with parameter $m$. This follows by observing that standard strong convexity implies restricted strong convexity for all values of rank $r$.

Last, we present results for the special case where $r=r^{\star}$; in this case, Fgd finds an optimal point $U^{\star}_{r}$ with linear rate, within the equivalent class of orthonormal matrices in $\mathcal{O}$.

Let $X^{\star}$ be the optimal point of $f$, over the set of PSD matrices, such that $rank(X^{\star})=r$. Consider $X$ as in Theorem 4.2. Then, under the same assumptions and with the same convergence factor $\alpha$ as in Theorem 4.2, we have

Further, for $r=n$ we recover the exact case of semi-definite optimization. In plain words, the above corollary suggests that, given an accuracy parameter $\varepsilon$, Fgd requires $K=O\left(\log\left(\nicefrac{{1}}{{\varepsilon}}\right)\right)$ iterations in order to achieve ${\rm{\textsc{Dist}}}(U^{K},U^{\star})^{2}\leq\varepsilon$; recall the analogous result for classic gradient schemes for $M$-smooth and strongly convex functions $f$, where similar rates can be achieved in $X$ space . The above are abstractly illustrated in Figure 2.

By the results above, one can easily observe that the convergence rate factor $\alpha$, in contrast to standard convex gradient descent results, depends both on the condition number of $X^{\star}_{r}$ and $\|\nabla f(X^{\star})\|_{2}$, in addition to $\kappa$. This dependence is a result of the step size selection, which is different from standard step sizes, i.e., $\nicefrac{{1}}{{M}}$ for standard gradient descent schemes. We also refer the reader to Section E for some discussion.

As a ramification of the above, notice that $\alpha$ depends only on the condition number of $X^{\star}_{r}$ and not that of $X^{\star}$. This suggests that, in settings where the optimum $X^{\star}$ has bad condition number (and thus leads to slower convergence), it is indeed beneficial to restrict $U$ to be a $n\times r$ matrix and only search for a rank-$r$ approximation of the optimal solution, which leads to faster convergence rate in practice; see Figure 8 in our experimental findings at the end of Section F.3.

In the setting where the optimum $X^{\star}$ is 0, directly applying the above theorems requires an initialization that is exactly at the optimum 0. On the contrary, this is actually an easy setting and the Fgd converges from any initial point to the optimum.

Initialization

In the previous section, we show that gradient descent over $U$ achieves sublinear$/$linear convergence, once the iterates are closer to $U^{\star}_{r}$. Since the overall problem is non-convex, intuition suggests that we need to start from a “decent” initial point, in order to get provable convergence to $U^{\star}_{r}$.

One way to satisfy this condition for general convex $f$ is to use one of the standard convex algorithms and obtain $U$ within constant error to $U^{\star}$ (or $U^{\star}_{r}$); then, switch to Fgd to get the high precision solution. See for a specific implementation of this idea on matrix sensing. Such initialization procedure comes with the following guarantees; the proof can be found in Section D:

Let $f$ be a $M$-smooth and $(m,r)$-restricted strongly convex function over PSD matrices and let $X^{\star}$ be the minimum of $f$ with $rank(X^{\star})=r$. Let ${X}^{\scalebox{0.7}{+}}=\mathcal{P}_{+}(X-\frac{1}{M}\nabla f(X))$ be the projected gradient descent update. Then, $\left\|{X}^{\scalebox{0.7}{+}}-X\right\|_{F}\leq\frac{c}{\kappa\sqrt{r}\tau(X_{r})}\sigma_{r}(X)$ implies,

Next, we present a generic initialization scheme for general smooth and strongly convex $f$. We use only the first-order oracle: we only have access to—at most—gradient information of $f$. Our initialization comes with theoretical guarantees w.r.t. distance from optimum. Nevertheless, in order to show small relative distance in the form of ${\rm{\textsc{Dist}}}(U^{0},U^{\star}_{r})\leq\rho\sigma_{r}(U^{\star}_{r})$, one requires certain condition numbers of $f$ and further assumptions on the spectrum of optimal solution $X^{\star}$ and rank $r$. However, empirical findings in Section F.3 show that our initialization performs well in practice.

see also Theorem 5.2. Thus, a scaling of $\mathcal{P}_{+}(-\nabla f(0))$ by $M$ could serve as a decent initialization. In many recent works this initialization has been used for specific applications.To see this, consider the case of least-squares objective $f(X):=\tfrac{1}{2}\|\mathcal{A}(X)-y\|_{2}^{2}$, where $y$ denote the set of observations and, $\mathcal{A}$ is a properly designed sensing mechanism, depending on the problem at hand. For example, in the affine rank minimization case , $\left(\mathcal{A}(X)\right)_{i}$ represents the linear system mechanism where $\operatorname{Tr}(A_{i}\cdot X)=b_{i}$. Under this setting, computing the gradient $\nabla f(\cdot)$ at zero point, we have: $-\nabla f(0)=\mathcal{A}^{*}(y)$, where $\mathcal{A}^{*}$ is the adjoint operator of $\mathcal{A}$. Then, it is obvious that the operation $\mathcal{P}_{+}\left(-\nabla f(0)\right)$ is very similar to the spectral methods, proposed for initialization in the references above. Here, we note that the point $\nicefrac{{1}}{{M}}\cdot\mathcal{P}_{+}\left(-\nabla f(0)\right)$ can be used as initialization point for generic smooth and strongly convex $f$.

We now present guarantees for the initialization discussed. The proof is provided in Section D.2.

Let $f$ be a $M$-smooth and $m$-strongly convex function, with condition number $\kappa=\frac{M}{m}$, and let $X^{\star}$ be its minimum over PSD matrices. Let $X^{0}$ be defined as:

While the above result guarantees a good initialization for only small values of $\kappa$, in many applications , this is indeed the case and $X^{0}$ has constant relative error to the optimum.

Now for the setting when the optimum is exactly rank-$r$ we get the following result.

Let $X^{\star}$ be rank-$r$ for some $r\leq n$. Then, under the conditions of Theorem 5.2, we get

Finally, for the setting when the function satisfies $(m,r)$-restricted strong convexity, the above corollary still holds as the optimum is a rank-$r$ matrix.

Convergence proofs for the Fgd algorithm

In this section, we first present the key techniques required for analyzing the convergence of Fgd. Later, we present proofs for both Theorems 4.1 and 4.2. Throughout the proofs we use the following notation. $X^{\star}$ is the optimum of problem (1) and $X^{\star}_{r}=U_{r}^{\star}R_{U}^{\star}(U_{r}^{\star}R_{U}^{\star})^{\top}$ is the rank-$r$ approximation; for the just smooth case, $X^{\star}=X^{\star}_{r}$, as we consider only the rank-$r^{\star}$ case and $r=r^{\star}$. Let $R_{U}^{\star}:=\operatorname*{argmin}_{R:R\in\mathcal{O}}\|U-U^{\star}_{r}R\|_{F}$ and $\Delta=U-U^{\star}_{r}R_{U}^{\star}$.

A key property that assists classic gradient descent to converge to the optimum $X^{\star}$ is the fact that $\langle{X}^{\scalebox{0.7}{+}}-X,~{}X^{\star}-X\rangle\geq 0$ for a smooth convex function $f$; in the case of strongly convex $f$, the inner product is further lower bounded by $\frac{m}{2}\|X-X^{\star}\|_{F}^{2}$ (see Theorem 2.2.7 of ). Classical proofs mainly use such lower bounds to show convergence (see Theorems 2.1.13 and 2.2.8 of ).

We follow broadly similar steps in order to show convergence of Fgd. In particular,

In section 6.1, we show a lower bound for the inner product $\left\langle U-{U}^{\scalebox{0.7}{+}},U-U_{r}^{\star}R_{U}^{\star}\right\rangle$ (Lemma 6.1), even though the function is not convex in $U$. The initialization and rank-$r$ approximate optimum assumptions play a crucial role in proving this, along with the fact that $f$ is convex in $X$.

In sections 6.2 and 6.3, we use the above lower bound to show convergence for $(i)$ smooth and strongly $f$, and $(ii)$ just smooth $f$, respectively, similar to the convex setting.

Next, we present the main descent lemma that is used for both sublinear and linear convergence rate guarantees of Fgd.

For $f$ being a $M$-smooth and $(m,r)$-strongly convex function and, under assumptions $(A2)$ and $(A3)$, the following inequality holds true:

Further, when $f$ is just $M$-smooth convex function and, under the assumptions $f({X}^{\scalebox{0.7}{+}})\geq f(X^{\star}_{r})$ and $(A1)$, we have:

First, we rewrite the inner product as shown below.

which follows by adding and subtracting $\tfrac{1}{2}X^{\star}_{r}$.

Strongly convex $f$ setting. For this case, the next 3 steps apply.

Step I: Bounding $\left\langle\nabla f(X),X-X^{\star}_{r}\right\rangle$. The first term in the above expression can be lower bounded using smoothness and strong convexity of $f$ and, involves a construction of a feasible point $X$. We construct such a feasible point by modifying the current update to one with bigger step size $\widehat{\eta}$.

Let $f$ be a $M$-smooth and $(m,r)$-restricted strongly convex function with optimum point $X^{\star}$. Moreover, let $X^{\star}_{r}$ be the best rank-$r$ approximation of $X^{\star}$. Let $X=UU^{\top}$. Then,

where $\widehat{\eta}=\frac{1}{16(M\|X\|_{2}+\|\nabla f(X)Q_{U}Q_{U}^{\top}\|_{2})}\geq\tfrac{5\eta}{6}$, by Lemma A.5.

Proof of this lemma is provided in Section B.1.

Step II: Bounding $\left\langle\nabla f(X),\Delta\Delta^{\top}\right\rangle$. The second term in equation (13) can actually be negative. Hence, we lower bound it using our initialization assumptions. Intuitively, the second term is smaller than the first one as it scales as ${\rm{\textsc{Dist}}}(U,U^{\star}_{r})^{2}$, while the first term scales as ${\rm{\textsc{Dist}}}(U,U^{\star}_{r})$.

Let $f$ be $M$-smooth and $(m,r)$-restricted strongly convex. Then, under assumptions $(A2)$ and $(A4)$, the following bound holds true:

Proof of this lemma can be found in Section B.2.

Step III: Combining the bounds in equation (13). For a detailed description, see Section B.3.

Smooth $f$ setting. For this case, the next 3 steps apply.

Step I: Bounding $\left\langle\nabla f(X),X-X^{\star}_{r}\right\rangle$. Similar to the strongly convex case, one can obtain a lower bound on $\left\langle\nabla f(X),X-X^{\star}_{r}\right\rangle$, according to the following Lemma:

Let $f$ be a $M$-smooth convex function with optimum point $X^{\star}_{r}$. Then, under the assumption that $f({X}^{\scalebox{0.7}{+}})\geq f(X^{\star}_{r})$, the following holds:

The proof of this lemma can be found in Appendix C.

Step II: Bounding $\left\langle\nabla f(X),\Delta\Delta^{\top}\right\rangle$. Here, we follow a different path in providing a lower bound for $\left\langle\nabla f(X),\Delta\Delta^{\top}\right\rangle$. The following lemma provides such a lower bound.

Let $X=UU^{\top}$ and define $\Delta:=U-U_{r}^{\star}R_{U}^{\star}$. Let $f({X}^{\scalebox{0.7}{+}})\geq f(X^{\star}_{r})$. Then, for ${\rm{\textsc{Dist}}}(U,U^{\star}_{r})\leq\rho\sigma_{r}\left(U^{\star}_{r}\right)$, where $\rho=\tfrac{1}{100}\frac{\sigma_{r}(X^{\star})}{\sigma_{1}(X^{\star})}$, and $f$ being a $M$-smooth convex function, the following lower bound holds:

The proof of this lemma can be found in Appendix C.

Step III: Combining the bounds in equation (13). For a detailed description, see Section C and Lemma C.4.

2 Proof of linear convergence (Theorem 4.2)

The proof of this theorem involves showing that the potential function ${\rm{\textsc{Dist}}}(U,U^{\star}_{r})$ is decreasing per iteration (up to approximation error $||X^{\star}-X^{\star}_{r}||_{F}$), using the descent Lemma 6.1. Using the algorithm’s update rule, we obtain

which follows by adding and subtracting $U$ and then expanding the squared term.

Step I: Bounding term $\left\langle U-{U}^{\scalebox{0.7}{+}},U-U^{\star}R\right\rangle$ in (14). By Lemma 6.1, we can bound the last term on the right hand side as:

Furthermore, we can substitute ${U}^{\scalebox{0.7}{+}}$ in the first term to obtain $\|{U}^{\scalebox{0.7}{+}}-U\|_{F}^{2}=\eta^{2}\|\nabla f(X)U\|_{F}^{2}$.

Step II: Combining bounds into (14). Combining the above two equations (14) becomes:

where $(i)$ is due to removing the negative part from the right hand side, $(ii)$ is due to $\tfrac{10}{11}\eta^{\star}\leq\eta\leq\tfrac{11}{10}\eta^{\star}$ by Lemma A.5, $(iii)$ follows from substituting $\eta^{\star}=\tfrac{1}{16(M\|X^{\star}\|_{2}+\|\nabla f(X^{\star})\|_{2})}$. This proves the first part of the theorem.

Step III: ${U}^{\scalebox{0.7}{+}}$ satisfies the initial condition. Now we will prove the second part. By the above equation, we have:

$(i)$ follows from substituting the assumptions on ${\rm{\textsc{Dist}}}(U,U^{\star}_{r})$ and $\|X^{\star}-X^{\star}_{r}\|_{F}$ and the last inequality is due to the term in the parenthesis being less than one.

3 Proof of sublinear convergence (Theorem 4.1)

Here, we show convergence of Fgd when $f$ is only a $M$-smooth convex function. At iterate $k$, we assume $f(X^{k})>f(X^{\star}_{r})$; in the opposite case, the bound follows trivially. Recall the updates of Fgd over the $U$-space satisfy

Our proof proceeds using the smoothness condition on $f$, at point ${X}^{\scalebox{0.7}{+}}$. In particular,

where $(i)$ follows from symmetry of $\nabla f(X)$, $X$ and

and $(ii)$ is due to (15) and the fact that $\eta\leq\tfrac{1}{16M\|X^{0}\|_{2}}\leq\tfrac{1}{14M\|X\|_{2}}$ (see Lemma A.5). Hence,

To bound the term $f(X)-f(X^{\star}_{r})$ on the right hand side of (17), we use standard convexity as follows:

From (18), we obtain to the following bound:

Define $\delta=f(X)-f(X^{\star}_{r})$ and ${\delta}^{\scalebox{0.7}{+}}=f({X}^{\scalebox{0.7}{+}})-f(X^{\star}_{r})$. Moreover, by Lemma C.5, we know that ${\rm{\textsc{Dist}}}(U,U^{\star}_{r})\leq{\rm{\textsc{Dist}}}(U^{0},U^{\star}_{r})$ for all iterations of FGD; thus, we have $\tfrac{1}{{\rm{\textsc{Dist}}}(U,U^{\star}_{r})}\geq\tfrac{1}{{\rm{\textsc{Dist}}}(U^{0},U^{\star}_{r})}$ for every update $U$. Using the above definitions and substituting (19) in (17), we obtain the following recursion:

since ${\delta}^{\scalebox{0.7}{+}}\leq\delta$ from equation (17). Since each $\delta$ and ${\delta}^{\scalebox{0.7}{+}}$ correspond to previous and new estimate in FGD per iteration, we can sum up the above inequalities over $k$ iterations to obtain

here, $\delta^{k}:=f(X^{k})-f(X^{\star}_{r})$ and $\delta^{0}:=f(X^{0})-f(X^{\star}_{r})$. After simple transformations, we finally obtainOne can further obtain a bound on the right hand side that depends on $\eta^{\star}=\frac{1}{16\,(M\left\|X^{\star}\right\|_{2}+\left\|\nabla f(X^{\star})\right\|_{2})}$. By Lemma A.5, we know $\eta\geq\tfrac{10}{11}\eta^{\star}$. Thus, the current proof leads to the bound: $\displaystyle f(X^{k})-f(X^{\star}_{r})\leq\frac{\tfrac{6}{\eta^{\star}}\cdot{\rm{\textsc{Dist}}}(U^{0},U^{\star}_{r})^{2}}{k+\tfrac{6}{\eta^{\star}}\cdot\tfrac{{\rm{\textsc{Dist}}}(U^{0},U^{\star}_{r})^{2}}{f(X^{0})-f(X^{\star}_{r})}}.$ :

Related work

Convex approaches. A significant volume of work has focused on solving the classic Semi-Definite Programming (SDP) formulation, where the objective $f$ (as well as any additional convex constraints) is assumed to be linear. There, interior point methods (IPMs) constitute a popular choice for small- and moderate-sized problems; see . For a comprehensive treatment of this subject, see the excellent survey in .

Large scale SDPs pointed research towards first-order approaches, which are more computationally appealing. For linear $f$, we note among others the work of , a provably convergent alternating direction augmented Lagrangian algorithm, and that of Helmberg and Rendl , where they develop an efficient first-order spectral bundle method for SDPs with the constant trace property; see also for extensions on this line of work. In both cases, no convergence rate guarantees are provided; see also . For completeness, we also mention the work of on second-order methods, that take advantage of data sparsity in order to handle large SDPs in a more efficient way. However, it turns out that the amount of computations required per iteration is comparable to that of log-barrier IPMs .

Standard SDPs have also found application in the field of combinatorial optimization; there, in most cases, even a rough approximation to the discrete problem, via SDP, is sufficiently accurate and computationally affordable, than exhaustive combinatorial algorithms. Goemans and Williamson were the first to propose the use of SDPs in approximating graph Max Cut, where a near-optimum solution can be found in polynomial time. propose an alternative approach for solving Max Cut and Graph Coloring instances, where SDPs are transformed into eigenvalue problems. Then, power method iterations lead to $\varepsilon$-approximate solutions; however, the resulting running-time dependence on $\varepsilon$ is worse, compared to standard IPMs. Arora, Hazan and Kale in derive an algorithm to approximate SDPs, as a hybrid of the Multiplicative Weights Update method and of ideas originating from an ellipsoid variant , improving upon existing algorithms for graph partitioning, computational biology and metric embedding problems.The algorithm in shows significant computational gains over standard IPMs per iteration, due to requiring only a power method calculation per iteration (versus a Cholesky factorization per iteration, in the latter case). However, the polynomial dependence on the accuracy parameter $\tfrac{1}{\varepsilon}$ is worse, compared to IPMs. Improvements upon this matter can be found in where a primal-dual Multiplicative Weights Update scheme is proposed.

Extending to non-linear convex $f$ cases, have shown how IPMs can be generalized to solve instances of (1), via the notion of self-concordance; see also for a more recent line of work. Within the class of first-order methods, approaches for nonlinear convex $f$ include, among others, projected and proximal gradient descent methods , (smoothed) dual ascent methods , as well as Frank-Wolfe algorithm variants . Note that all these schemes, often require heavy calculations, such as eigenvalue decompositions, to compute the updates (often, to remain within the feasible set).

Burer & Monteiro factorization and related work. Burer and Monteiro popularized the idea of solving classic SDPs by representing the solution as a product of two factor matrices. The main idea in such representation is to remove the positive semi-definite constraint by directly embedding it into the objective. While the problem becomes non-convex, Burer and Monteiro propose a method-of-multiplier type of algorithm which iteratively updates the factors in an alternating fashion. For linear objective $f$, they establish convergence guarantees to the optimum but do not provide convergence rates.

For generic smooth convex functions, Hazan in proposes SparseApproxSDP algorithm,Sparsity here corresponds to low-rankness of the solution, as in the Cholesky factorization representation. Moreover, inspired by Quantum State Tomography applications , SparseApproxSDP can also handle constant trace constraints, in addition to PSD ones. a generalization of the Frank-Wolfe algorithm for the vector case , where putative solutions are refined by rank-1 approximations of the gradient. At the $r$-th iteration, SparseApproxSDP is guaranteed to compute a $\tfrac{1}{r}$-approximate solution, with rank at most $r$, i.e., achieves a sublinear $O\left(\tfrac{1}{\varepsilon}\right)$ convergence rate. However, depending on $\varepsilon$, SparseApproxSDP is not guaranteed to return a low rank solution unlike Fgd. Application of these ideas in machine learning tasks can be found in . Based on SparseApproxSDP algorithm, further introduces “de-bias” steps in order to optimize parameters in SparseApproxSDP and do local refinements of putative solutions via L-BFGS steps. Nevertheless, the resulting convergence rate is still sublinear.For running time comparisons with Fgd see Sections G and H.

Specialized algorithms – for objectives beyond the linear case – that utilize such factorization include matrix completion /sensing solvers , non-negative matrix factorization schemes , phase retrieval methods and sparse PCA algorithms . Most of these results guarantee linear convergence for various algorithms on the factored space starting from a “good” initialization. They also present a simple spectral method to compute such an initialization. For the matrix completion /sensing setting, have shown that stochastic gradient descent achieves global convergence at a sublinear rate. Note that these results only apply to quadratic loss objectives and not to generic convex functions $f$.We recently became aware of the extension of the work for the non-square case $X=UV^{\top}$. consider the problem of computing the matrix square-root of a PSD matrix via gradient descent on the factored space: in this case, the objective $f$ boils down to minimizing the standard squared Euclidean norm distance between two matrices. Surprisingly, the authors show that, given an initial point that is well-conditioned, the proposed scheme is guaranteed to find an $\varepsilon$-accurate solution with linear convergence rate.

propose a first-order optimization framework for the problem (1), where the same parametrization technique is used to efficiently accommodate the PSD constraint.In this work, the authors further assume orthogonality of columns in $U$. Moreover, the proposed algorithmic solution can accommodate extra constraints on $X$.Though, additional constraints should satisfy the $X^{\star}$-faithfulness property: a constraint set on $U$, say $\mathcal{U}$, is faithful if for each $U\in\mathcal{U}$, that is within some bounded radius from optimal point, we are guaranteed that the closest (in the Euclidean sense) rotation of $U^{\star}$ lies within $\mathcal{U}$. The set of assumptions listed in include—apart from $X^{\star}$-faithfulness—local descent, local Lipschitz and local smoothness conditions in the factored space. E.g., the local descent condition can be established if $g(U):=f(UU^{\top})$ is locally strongly convex and $\nabla g(\cdot)$ at an optimum point vanishes. They also require bounded gradients as their step size doesn’t account for the modified curvature of $f(UU^{\top})$. One can define non-trivially conditions on the original space; we defer the reader to These conditions are less standard than the global assumptions of the current work and one needs to validate that they are satisfied for each problem, separately. presents some applications where these conditions are indeed satisfied. Their results are of the same flavor with ours: under such proper assumptions, one can prove local convergence with $O(1/\varepsilon)$ or $O(\log(1/\varepsilon))$ rate and for $f$ instances that even fail to be locally convex.

Finally, for completeness, we also mention optimization over the Grassmannian manifold that admits tailored solvers ; see for applications in matrix completion and references therein. presents a second-order method for (1), based on manifold optimization over the set of all equivalence class $\mathcal{O}$. The proposed algorithm can additionally accommodate constraints and enjoys monotonic decrease of the objective function (in contrast to ), featuring quadratic local convergence. In practice, the per iteration complexity is dominated by the extraction of the eigenvector, corresponding to the smallest eigenvalue, of a $n\times n$ matrix—and only when the current estimate of rank satisfies some conditions.

Table 1 summarizes the comparison of the most relevant work to ours, for the case of matrix factorization techniques.

Conclusion

In this paper, we focus on how to efficiently minimize a convex function $f$ over the positive semi-definite cone. Inspired by the seminal work , we drop convexity by factorizing the optimization variable $X=UU^{\top}$ and show that factored gradient descent with a non-trivial step size selection results in linear convergence when $f$ is smooth and (restricted) strongly convex, even though the problem is now non-convex. In the case where $f$ is only smooth, only sublinear rate is guaranteed. In addition, we present initialization schemes that use only first order information and guarantee to find a starting point with small relative distance from optimum.

There are many possible directions for future work, extending the idea of using non-convex formulation for semi-definite optimization. Showing convergence under weaker initialization condition or without any initialization requirement is definitely of great interest. Another interesting direction is to improve the convergence rates presented in this work, by using acceleration techniques and thus, extend ideas used in the case of convex gradient descent . Finally, it would be valuable to see how the techniques presented in this paper can be generalized to other standard algorithms like stochastic gradient descent and coordinate descent.

Furthermore, we identify applications, such as sparse PCA , that require non-smooth constraints on the factors $U$. That being said, an extension of this work to proximal techniques for the non-convex case is a very interesting future research direction.

References

Appendix A Supporting lemmata

Let $A$ and $B$ be two PSD $n\times n$ matrices. Also let $A$ be full rank. Then,

The following lemma shows that Dist, in the factor $U$ space, upper bounds the Frobenius norm distance in the matrix $X$ space.

Let $X=UU^{\top}$ and $X^{\star}_{r}=U^{\star}_{r}U_{r}^{\star\top}$ be two $n\times n$ rank-$r$ PSD matrices. Let ${\rm{\textsc{Dist}}}(U,U^{\star}_{r})\leq\rho\sigma_{r}(U^{\star}_{r})$, for some rotation matrix $R_{U}^{\star}$ and constant $\rho>0$. Then,

By substituting $X=UU^{\top}$ and $X^{\star}_{r}=U^{\star}_{r}U_{r}^{\star\top}$ in $\|X-X^{\star}_{r}\|_{F}$, we have:

where $(i)$ is due to the orthogonality $R_{U}^{\star\top}R_{U}^{\star}=I_{r\times r}$, $(ii)$ is due to the triangle inequality, the Cauchy-Schwarz inequality and the fact that spectral norm is invariant w.r.t. orthogonal transformations and, $(iii)$ is due to the following sequence of inequalities, based on the hypothesis of the lemma:

and thus $\|U\|_{2}\leq(1+\rho)\cdot\|U^{\star}_{r}\|_{2}$. The final inequality $(iv)$ follows from the hypothesis of the lemma. ∎

The following lemma connects the spectrum of $U$ to $U^{\star}_{r}$ under the initialization assumptions.

Let $U$ and $U^{\star}_{r}$ be $n\times r$ matrices such that ${\rm{\textsc{Dist}}}(U,U^{\star}_{r})\leq\rho\sigma_{r}\left(U^{\star}_{r}\right)$, for $\rho=\tfrac{1}{100}\tfrac{\sigma_{r}(X^{\star})}{\sigma_{1}(X^{\star})}$. Withal, define $X^{\star}_{r}=U^{\star}_{r}U_{r}^{\star\top}$. Then, the following bounds hold true:

Moreover, by definition of $\tau(V):=\tfrac{\sigma_{r}(V)}{\sigma_{1}(V)}$ for some $V$ matrix, we also observe:

Using the norm ordering $\|\cdot\|_{2}\leq\|\cdot\|_{F}$ and the Weyl’s inequality for perturbation of singular values (Theorem 3.3.16 ) we get,

Then, the first two inequalities of the lemma follow by using triangle inequality and the above bound. For the last two inequalities, it is easy to derive bounds on condition numbers by combining the first two inequalities. Viz.,

while the last bound can be easily derived since $\tau\left(U^{\star}_{r}\right)=\sqrt{\tau\left(X^{\star}_{r}\right)}$. ∎

The following lemma shows that Dist, in the factor $U$ space, lower bounds the Frobenius norm distance in the matrix $X$ space.

Let $X=UU^{\top}$ and $X^{\star}_{r}=U^{\star}_{r}U_{r}^{\star\top}$ be two rank-$r$ PSD matrices. Let ${\rm{\textsc{Dist}}}(U,U^{\star}_{r})\leq\rho\sigma_{r}\left(U^{\star}_{r}\right)$, for $\rho=\tfrac{1}{100}\tfrac{\sigma_{r}(X^{\star})}{\sigma_{1}(X^{\star})}$. Then,

This proof largely follows the arguments for Lemma 5.4 in , from which we know that

Hence, $\left\|X-X^{\star}_{r}\right\|_{F}^{2}\geq\tfrac{3\sigma_{r}(X^{\star})}{4}{\rm{\textsc{Dist}}}(U,U^{\star}_{r})^{2}$, for the given value of $\rho$. ∎

The following lemma shows equivalence between various step sizes used in the proofs.

Let $X^{0}=U^{0}U^{0\top}$ and $X=UU^{\top}$ be two $n\times n$ rank-$r$ PSD matrices such that ${\rm{\textsc{Dist}}}(U,U^{\star}_{r})\leq{\rm{\textsc{Dist}}}(U^{0},U^{\star}_{r})\leq\rho\sigma_{r}(U^{\star}_{r})$, where $\rho=\tfrac{1}{100}\cdot\tfrac{\sigma_{r}(X^{\star})}{\sigma_{1}(X^{\star})}$. Define the following step sizes:

$\eta=\tfrac{1}{16(M\|X^{0}\|_{2}+\|\nabla f(X^{0})\|_{2})}$,

$\widehat{\eta}=\tfrac{1}{16(M\|X\|_{2}+\|\nabla f(X)Q_{U}Q_{U}^{\top}\|_{2})}$, and

$\eta^{\star}=\tfrac{1}{16(M\|X^{\star}\|_{2}+\|\nabla f(X^{\star})\|_{2})}$.

Then, $\widehat{\eta}\geq\tfrac{5}{6}\eta$ holds. Moreover, assuming $\|X^{\star}-X^{\star}_{r}\|_{F}\leq\frac{\sigma_{r}(X^{\star})}{100}\sqrt{\tfrac{\sigma_{r}(X^{\star})}{\sigma_{1}(X^{\star})}}$, the following inequalities hold:

By the assumptions of this lemma and based on Lemma A.3, we have, $\nicefrac{{98}}{{100}}\left\|X^{\star}\right\|_{2}\leq\left\|X^{0}\right\|_{2}\leq\nicefrac{{103}}{{100}}\left\|X^{\star}\right\|_{2}$; similarly $\nicefrac{{98}}{{100}}\left\|X^{\star}\right\|_{2}\leq\left\|X\right\|_{2}\leq\nicefrac{{103}}{{100}}\left\|X^{\star}\right\|_{2}$. Hence, we can combine these two set of inequalities to obtain bounds between $X^{0}$ and $X$, as follows:

To prove the desiderata, we show the relationship between the gradient terms $\|\nabla f(X)Q_{U}Q_{U}^{\top}\|_{2}$, $\|\nabla f(X^{0})\|_{2}$ and $\|\nabla f(X^{\star}_{r})\|_{2}$. In particular, for the case $\widehat{\eta}\geq\tfrac{5}{6}\eta$, we have:

where $(i)$ follows from the triangle inequality, $(ii)$ is due to the smoothness assumption, $(iii)$ is due to the triangle inequality, $(iv)$ follows by applying Lemma A.2 on the first two terms on the right hand side and, $(v)$ is due to the fact $\|U^{\star}_{r}\|_{2}\cdot\sigma_{r}(U^{\star}_{r})\leq\|X^{\star}\|_{2}$ and by substituting $\rho=\tfrac{1}{100}\cdot\tfrac{\sigma_{r}(X^{\star})}{\sigma_{1}(X^{\star})}\leq\tfrac{1}{100}$. Last inequality follows from $\nicefrac{{98}}{{100}}\left\|X^{\star}\right\|_{2}\leq\left\|X^{0}\right\|_{2}$. Hence, using the above bounds in step size selection, we get

where $(i)$ is based also on the bound $\|X\|_{2}\leq\tfrac{103}{98}\|X^{0}\|_{2}$.

Similarly we show the bound $\tfrac{10}{11}\eta^{\star}\leq\eta\leq\tfrac{11}{10}\eta^{\star}$. First observe that,

Combining the above bound with $\nicefrac{{98}}{{100}}\left\|X^{\star}_{r}\right\|_{2}\leq\left\|X^{0}\right\|_{2}\leq\nicefrac{{103}}{{100}}\left\|X^{\star}_{r}\right\|_{2}$ gives, $\eta\geq\frac{10}{11}\eta^{\star}$. Similarly we can show the other bounds. ∎

Appendix B Main lemmas for the restricted strong convex case

In this section, we present proofs for the main lemmas used in the proof of Theorem 4.2, in Section 6.

Here, we prove the existence of a non-trivial lower bound for $\left\langle\nabla f(X),X-X^{\star}_{r}\right\rangle$. Our proof differs from the standard convex gradient descent proof (see ), as we need to analyze updates without any projections. Our proof technique constructs a pseudo-iterate to obtain a bigger lower bound than the error term in Lemma 6.3. Here, the nature of the step size plays a key role in achieving the bound.

Let us abuse our notation and define ${U}^{\scalebox{0.7}{+}}=U-\widehat{\eta}\nabla f(X)U$ and ${X}^{\scalebox{0.7}{+}}={U}^{\scalebox{0.7}{+}}U^{\scalebox{0.7}{+}\top}$. Observe that we use the surrogate step size $\widehat{\eta}$, where according to Lemma A.5 satisfies $\widehat{\eta}\geq\tfrac{5}{6}\eta$. By smoothness of $f$, we get:

where $(i)$ follows from optimality of $X^{\star}$ and since ${X}^{\scalebox{0.7}{+}}$ is a feasible point $({X}^{\scalebox{0.7}{+}}\succeq 0)$ for problem (1). Further, note that $X^{\star}_{r}$ is a PSD feasible point. By smoothness of $f$, we also get

where $(i)$ is due to KKT conditions : since $\nabla f(X^{\star})$ is orthogonal to $X^{\star}$, it is also orthogonal to the $n-r$ bottom eigenvectors of $X^{\star}$. Viz., $\left\langle\nabla f(X^{\star}),X^{\star}_{r}-X^{\star}\right\rangle=0$. Finally, since $\text{rank}(X^{\star}_{r})=r$, by the $(m,r)$-restricted strong convexity of $f$, we get,

Combining equations (22), (23), and (24), we obtain:

Substituting the above in (25), we obtain:

where $(i)$ follows from symmetry of $\nabla f(X)$ and $X$, and $(ii)$ follows from

Finally, $(iii)$ follows by observing that $\widehat{\eta}\leq\tfrac{1}{16M\|X\|_{2}}$. Thus, we achieve the desiderata:

B.2 Proof of Lemma 6.3

We lower bound $\left\langle\nabla f(X),\Delta\Delta^{\top}\right\rangle$ as follows:

Note that $(i)$ follows from the fact $\Delta=Q_{\Delta}Q_{\Delta}^{\top}\Delta$ and $(ii)$ follows from $|\operatorname{Tr}(AB)|\leq\|A\|_{2}\operatorname{Tr}(B)$, for PSD matrix $B$ (Von Neumann’s trace inequality ). For the transformation in $(iii)$, we use that fact that the column space of $\Delta$, $\text{{Span}}(\Delta)$, is a subset of $\text{{Span}}(U\cup U^{\star}_{r})$, as $\Delta$ is a linear combination of $U$ and $U_{r}^{\star}R_{U}^{\star}$.

To bound the first term in equation (26), we observe:

At this point, we desire to introduce strong convexity parameter $m$ and condition number $\kappa$ in our bound. In particular, to bound term $A$, we observe that $\|Q_{U}Q_{U}^{\top}\nabla f(X)\|_{2}\leq\tfrac{m\sigma_{r}(X)}{40}$ or $\|Q_{U}Q_{U}^{\top}\nabla f(X)\|_{2}\geq\tfrac{m\sigma_{r}(X)}{40}$. This results into bounding $A$ as follows:

Combining the above inequalities, we obtain:

where $(i)$ follows from $\widehat{\eta}\leq\tfrac{1}{16M\|X\|_{2}}$, $(ii)$ is due to Lemma A.3 and bounding ${\rm{\textsc{Dist}}}(U,U^{\star}_{r})\leq\rho^{\prime}\sigma_{r}(U^{\star}_{r})$ by the hypothesis of the lemma, $(iii)$ is due to $\sigma_{r}(X^{\star})\leq 1.1\sigma_{r}(X)$ by Lemma A.3 and due to the facts $\sigma_{r}(X)\|Q_{U}Q_{U}^{\top}\nabla f(X)\|_{2}^{2}\leq\|U^{\top}\nabla f(X)\|_{F}^{2}$ and $(41\kappa\tau(X^{\star}_{r})+1)\leq 42\kappa\tau(X^{\star}_{r})$. Finally, $(iv)$ follows from substituting $\rho^{\prime}$ and using Lemma A.3.

Next, we bound the second term in equation (26):

where $(i)$ follows from $\nabla f(X^{\star})X^{\star}=0$, $(ii)$ is due to smoothness of $f$ and $(iii)$ follows from Lemma A.2. Finally $(iv)$ follows from ${\rm{\textsc{Dist}}}(U,U^{\star}_{r})\leq\rho^{\prime}\sigma_{r}(U^{\star}_{r})$ and substituting $\rho^{\prime}=\frac{1}{100\kappa\tau(U^{\star}_{r})}$.

B.3 Proof of Lemma 6.1

Recall ${U}^{\scalebox{0.7}{+}}=U-\eta\nabla f(X)U$. First we rewrite the inner product as shown below.

which follows by adding and subtracting $\tfrac{1}{2}X^{\star}_{r}$.

Let, $\widehat{\eta}=\tfrac{1}{16(M\|X\|_{2}+\|\nabla f(X)Q_{U}Q_{U}^{\top}\|_{2})}$. Using Lemmas 6.2 and 6.3, we have:

where $(i)$ follows from $\|X^{\star}-X^{\star}_{r}\|\leq\frac{\sigma_{r}(X^{\star})}{100\kappa^{1.5}}\frac{\sigma_{r}(X^{\star})}{\sigma_{1}(X^{\star})}\leq\frac{\sigma_{r}(X^{\star})}{100\kappa^{1.5}}\leq\frac{\sigma_{r}(X^{\star})}{100\kappa}$ and $(ii)$ follows from Lemma A.4. Finally the result follows from $\widehat{\eta}\geq\tfrac{5}{6}\eta$ from Lemma A.5.