Fast global convergence of gradient methods for high-dimensional statistical recovery

Introduction

Many of these programs are instances of convex conic programs, and so can (in principle) be solved to $\epsilon$-accuracy in polynomial time using interior point methods, and other standard methods from convex programming (e.g., see the books ). However, the complexity of such quasi-Newton methods can be prohibitively expensive for the very large-scale problems that arise from high-dimensional data sets. Accordingly, recent years have witnessed a renewed interest in simpler first-order methods, among them the methods of projected gradient descent and mirror descent. Several authors (e.g., ) have used variants of Nesterov’s accelerated gradient method to obtain algorithms for high-dimensional statistical problems with a sublinear rate of convergence. Note that an optimization algorithm, generating a sequence of iterates $\{\theta^{t}\}_{t=0}^{\infty}$, is said to exhibit sublinear convergence to an optimum $\widehat{\theta}$ if the optimization error $\|\theta^{t}-\widehat{\theta}\|$ decays at the rate $1/t^{\kappa}$, for some exponent $\kappa>0$ and norm $\|\cdot\|$. Although this type of convergence is quite slow, it is the best possible with gradient descent-type methods for convex programs under only Lipschitz conditions .

It is known that much faster global rates—in particular, a linear or geometric rate—can be achieved if global regularity conditions like strong convexity and smoothness are imposed . An optimization algorithm is said to exhibit linear or geometric convergence if the optimization error $\|\theta^{t}-\widehat{\theta}\|$ decays at a rate $\kappa^{t}$, for some contraction coefficient $\kappa\in(0,1)$. Note that such convergence is exponentially faster than sub-linear convergence. For certain classes of problems involving polyhedral constraints and global smoothness, Tseng and Luo have established geometric convergence. However, a challenging aspect of statistical estimation in high dimensions is that the underlying optimization problems can never be strongly convex in a global sense when $d>n$ (since the $d\times d$ Hessian matrix is rank-deficient), and global smoothness conditions cannot hold when $d/n\rightarrow+\infty$. Some more recent work has exploited structure specific to the optimization problems that arise in statistical settings. For the special case of sparse linear regression with random isotropic designs (also referred to as compressed sensing), some authors have established fast convergence rates in a local sense, meaning guarantees that apply once the iterates are close enough to the optimum . The intuition underlying these results is that once an algorithm identifies the support set of the optimal solution, the problem is then effectively reduced to a lower-dimensional subspace, and thus fast convergence can be guaranteed in a local sense. Also in the setting of compressed sensing, Tropp and Gilbert studied finite convergence of greedy algorithms based on thresholding techniques, and showed linear convergence up to a certain tolerance. For the same class of problems, Garg and Khandekar showed that a thresholded gradient algorithm converges rapidly up to some tolerance. In both of these results, the convergence tolerance is of the order of the noise variance, and hence substantially larger than the true statistical precision of the problem.

The results in panel (a) exhibit an interesting property: the convergence rate is dimension-dependent, meaning that for a fixed sample size, projected gradient descent converges more slowly for a large problem than a smaller problem—compare the squares for $d=20000$ to the diamonds for $d=5000$. This phenomenon reflects the natural intuition that larger problems are, in some sense, “harder” than smaller problems. A notable aspect of our theory is that in addition to guaranteeing geometric convergence, it makes a quantitative prediction regarding the extent to which a larger problem is harder than a smaller one. In particular, our convergence rates suggest that if the sample size $n$ is re-scaled in a certain way according to the dimension $d$ and also other model parameters such as sparsity, then convergence rates should be roughly similar. Panel (b) provides a confirmation of this prediction: when the sample size is rescaled according to our theory (in particular, see Corollary 2 in Section 3.2), then all three curves lie essentially on top of another.

Although high-dimensional optimization problems are typically neither strongly convex nor smooth, this paper shows that it is fruitful to consider suitably restricted notions of strong convexity and smoothness. Our notion of restricted strong convexity (RSC) is related to but slightly different than that introduced in a recent paper by Negahban et al. for establishing statistical consistency. As we discuss in the sequel, bounding the optimization error introduces new challenges not present when analyzing the statistical error. We also introduce a related notion of restricted smoothness (RSM), not needed for proving statistical rates but essential in the setting of optimization. Our analysis consists of two parts. We first show that for optimization problems underlying many regularized $M$-estimators, appropriately modified notions of restricted strong convexity (RSC) and smoothness (RSM) are sufficient to guarantee global linear convergence of projected gradient descent. Our second contribution is to prove that for the iterates generated by our first-order method, these RSC/RSM assumptions do indeed hold with high probability for a broad class of statistical models, among them sparse linear models, models with group sparsity constraints, and various classes of matrix estimation problems, including matrix completion and matrix decomposition.

The remainder of this paper is organized as follows. We begin in Section 2 with a precise formulation of the class of convex programs analyzed in this paper, along with background on the notions of a decomposable regularizer, and properties of the loss function. Section 3 is devoted to the statement of our main convergence result, as well as to the development and discussion of its various corollaries for specific statistical models. In Section 4, we provide a number of empirical results that confirm the sharpness of our theoretical predictions. Finally, Section 5 contains the proofs, with more technical aspects of the arguments deferred to the Appendix.

Background and problem formulation

In this section, we begin by describing the class of regularized $M$-estimators to which our analysis applies, as well as the optimization algorithms that we analyze. Finally, we introduce some important notions that underlie our analysis, including the notions of a decomposable regularization, and the properties of restricted strong convexity and smoothness.

where $\rho>0$ is a user-defined radius, as well as to the regularized $M$-estimator

where the regularization weight $\lambda_{n}>0$ is user-defined. Note that the radii $\rho$ and $\bar{\rho}$ may be different in general. Throughout this paper, we impose the following two conditions:

for any data set $Z_{1}^{n}$, the function $\mathcal{L}_{n}(\cdot;Z_{1}^{n})$ is convex and differentiable over $\Omega$, and

The focus of this paper is on two simple algorithms for solving the above optimization problems. The method of projected gradient descent applies naturally to the constrained problem (1), whereas the composite gradient descent method due to Nesterov is suitable for solving the regularized problem (2). Each routine generates a sequence $\{\theta^{t}\}_{t=0}^{\infty}$ of iterates by first initializing to some parameter $\theta^{0}\in\Omega$, and then applying the recursive update

in the case of projected gradient descent, or the update

for the composite gradient method. Note that the only difference between the two updates is the addition of the regularization term in the objective. These updates have a natural intuition: the next iterate $\theta^{t+1}$ is obtained by constrained minimization of a first-order approximation to the loss function, combined with a smoothing term that controls how far one moves from the current iterate in terms of Euclidean norm. Moreover, it is easily seen that the update (3) is equivalent to

2 Restricted strong convexity and smoothness

In this section, we define the conditions on the loss function and regularizer that underlie our analysis. Global smoothness and strong convexity assumptions play an important role in the classical analysis of optimization algorithms . In application to a differentiable loss function $\mathcal{L}_{n}$, both of these properties are defined in terms of a first-order Taylor series expansion around a vector $\theta^{\prime}$ in the direction of $\theta$—namely, the quantity

We refer the reader to Bertsekas [5, Prop. 1.2.3, p. 145], or Nesterov [31, Thm. 2.2.8, p. 88] for such results on projected gradient descent, and to Nesterov for composite gradient descent.

Unfortunately, in the high-dimensional setting ($d>n$), it is usually impossible to guarantee strong convexity of the problem (1) in a global sense. For instance, when the data is drawn i.i.d., the loss function consists of a sum of $n$ terms. If the loss is twice differentiable, the resulting $d\times d$ Hessian matrix $\nabla^{2}\mathcal{L}(\theta;Z_{1}^{n})$ is often a sum of $n$ matrices each with rank one, so that the Hessian is rank-degenerate when $n<d$. However, as we show in this paper, in order to obtain fast convergence rates for the optimization method (3), it is sufficient that (a) the objective is strongly convex and smooth in a restricted set of directions, and (b) the algorithm approaches the optimum $\widehat{\theta}$ only along these directions. Let us now formalize these ideas.

If this inequality is violated, then the right-hand side of the bound (8) is non-positive, in which case the RSC constraint (8) is vacuous. Thus, restricted strong convexity imposes a non-trivial constraint only on pairs $\theta\neq\theta^{\prime}$ for which the inequality (8) holds, and a central part of our analysis will be to prove that, for the sequence of iterates generated by projected gradient descent, the optimization error $\widehat{\Delta}^{t}:=\theta^{t}-\widehat{\theta}$ satisfies a constraint of the form (9). We note that since the regularizer $\mathcal{R}$ is convex, strong convexity of the loss function $\mathcal{L}_{n}$ also implies the strong convexity of the regularized loss $\phi_{n}$ as well.

For the least-squares loss, the RSC definition depends purely on the direction (and not the magnitude) of the difference vector $\theta-\theta^{\prime}$. For other types of loss functions—such as those arising in generalized linear models—it is essential to localize the RSC definition, requiring that it holds only for pairs for which the norm $\|\theta-\theta^{\prime}\|_{2}$ is not too large. We refer the reader to Section 2.4.1 for further discussion of this issue.

Finally, as pointed out by a reviewer, our restricted version of strong convexity can be seen as an instance of the general theory of paraconvexity (e.g., ); however, we are not aware of convergence rates for minimizing general paraconvex functions.

We also specify an analogous notion of restricted smoothness:

We say the loss function $\mathcal{L}_{n}$ satisfies restricted smoothness with respect to $\mathcal{R}$ and with parameters $(\gamma_{u},\tau_{u}(\mathcal{L}_{n}))$ over the set $\Omega^{\prime}$ if

As with our definition of restricted strong convexity, the additional tolerance $\tau_{u}(\mathcal{L}_{n})$ is not present in analogous smoothness conditions in the optimization literature, but it is essential in our set-up.

3 Decomposable regularizers

Given a subspace pair $(\mathcal{M},{\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp})$ such that $\mathcal{M}\subseteq\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}$, we say that a norm $\mathcal{R}$ is $(\mathcal{M},{\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp})$-decomposable if

To gain some intuition for this definition, note that by triangle inequality, we always have the bound $\mathcal{R}(\alpha+\beta)\leq\mathcal{R}(\alpha)+\mathcal{R}(\beta)$. For a decomposable regularizer, this inequality always holds with equality. Thus, given a fixed vector $\alpha\in\mathcal{M}$, the key property of any decomposable regularizer is that it affords the maximum penalization of any deviation $\beta\in{\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp}$.

For a given error norm $\|\cdot\|$, its interaction with the regularizer $\mathcal{R}$ plays an important role in our results. In particular, we have the following:

Given the regularizer $\mathcal{R}(\cdot)$ and a norm $\|\cdot\|$, the associated subspace compatibility is given by

The quantity $\Psi(\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}})$ corresponds to the Lipschitz constant of the norm $\mathcal{R}$ with respect to $\|\cdot\|$, when restricted to the subspace $\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}$.

4 Some illustrative examples

The composite gradient update for this problem amounts to solving

corresponding to all vectors supported only on $S$. Defining $\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}(S)=\mathcal{M}(S)$, its orthogonal complement (with respect to the usual Euclidean inner product) is given by

A calculation using the mean-value theorem shows that for the loss function (13), the error in the first-order Taylor series, as previously defined in equation (6), can be written as

Such a condition corresponds to a variant of the restricted eigenvalue (RE) conditions that have been studied in the literature . Such RE conditions are significantly milder than the restricted isometry property; we refer the reader to van de Geer and Buhlmann for an in-depth comparison of different RE conditions. From past work, the condition (17) is satisfied with high probability for a broad classes of anisotropic random design matrices , and parts of our analysis make use of this fact.

4.2 Matrices and nuclear norm regularization

where $w_{i}$ is an additive observation noise. In many contexts, it is natural to assume that $\Theta^{*}$ is exactly low-rank, or approximately so, meaning that it is well-approximated by a matrix of low rank. In such settings, a number of authors (e.g., ) have studied the $M$-estimator

or the corresponding regularized version. Here the nuclear or trace norm is given by $|\!|\!|\Theta|\!|\!|_{{1}}:=\sum\limits_{j=1}^{d}\sigma_{j}(\Theta)$, corresponding to the sum of the singular values. This optimization problem is an instance of a semidefinite program. As discussed in more detail in Section 3.3, there are various applications in which this estimator and variants thereof have proven useful.

For the M-estimator (19), the projected gradient updates take a very simple form—namely

Finally, let us verify the decomposability of the nuclear norm . By construction, any pair of matrices $\Theta\in\mathcal{M}(U^{r},V^{r})$ and $\Gamma\in{\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp}(U^{r},V^{r})$ have orthogonal row and column spaces, which implies the required decomposability condition—namely $|\!|\!|\Theta+\Gamma|\!|\!|_{{1}}=|\!|\!|\Theta|\!|\!|_{{1}}+|\!|\!|\Gamma|\!|\!|_{{1}}$.

In some special cases such as matrix completion or matrix decomposition that we describe in the sequel, $\Omega^{\prime}$ will involve an additional bound on the entries of $\Theta^{*}$ as well as the iterates $\Theta^{t}$ to establish RSC/RSM conditions. This can be done by augmenting the loss with an indicator of the constraint and using cyclic projections for computing the updates as mentioned earlier in Example 2.4.1.

Main results and some consequences

We are now equipped to state the two main results of our paper, and discuss some of their consequences. We illustrate its application to several statistical models, including sparse regression (Section 3.2), matrix estimation with rank constraints (Section 3.3), and matrix decomposition problems (Section 3.4).

We now provide the notation necessary for a precise statement of this claim. Our main result actually involves a family of upper bounds on the optimization error, one for each pair $(\mathcal{M},{\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp})$ of $\mathcal{R}$-decomposable subspaces (see Definition 3). As will be clarified in the sequel, this subspace choice can be optimized for different models so as to obtain the tightest possible bounds. For a given pair $(\mathcal{M},{\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp})$ such that $16\Psi^{2}(\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}})\tau_{u}(\mathcal{L}_{n})<\gamma_{u}$, let us define the contraction coefficient

In addition, we define the tolerance parameter

where $\Delta^{*}=\widehat{\theta}-\theta^{*}$ is the statistical error, and $\Pi_{\mathcal{M}^{\perp}}(\theta^{*})$ denotes the Euclidean projection of $\theta^{*}$ onto the subspace $\mathcal{M}^{\perp}$.

In terms of these two ingredients, we now state our first main result:

The result of Theorem 1 takes a simpler form when there is a subspace $\mathcal{M}$ that includes $\theta^{*}$, and the $\mathcal{R}$-ball radius is chosen such that $\rho\leq\mathcal{R}(\theta^{*})$. In this case, by appropriately controlling the error term, we can establish that it is of lower order than the statistical precision —namely, the squared difference $\|\widehat{\theta}-\theta^{*}\|^{2}$ between an optimal solution $\widehat{\theta}$ to the convex program (1), and the unknown parameter $\theta^{*}$.

This coefficient accounts for the residual amount of strong convexity after accounting for the lower tolerance terms. In addition, we define the compound contraction coefficient as

Recall that the regularized problem (2) involves both a regularization weight $\lambda_{n}$, and a constraint radius $\bar{\rho}$. Our theory requires that the constraint radius is chosen such that $\bar{\rho}\geq\mathcal{R}(\theta^{*})$, which ensures that $\theta^{*}$ is feasible. In addition, the regularization parameter should be chosen to satisfy the constraint

where $\mathcal{R}^{*}$ is the dual norm of the regularizer. This constraint is known to play an important role in proving bounds on the statistical error of regularized $M$-estimators (see the paper and references therein for further details). Recalling the definition (2) of the overall objective function $\phi_{n}(\theta)$, the following result provides bounds on the excess loss $\phi_{n}(\theta^{t})-\phi_{n}(\widehat{\theta}_{\scriptsize{\lambda_{n}}})$.

Then for any tolerance parameter $\delta^{2}\geq\frac{\epsilon^{2}(\Delta^{*};\mathcal{M},\makebox[0.0pt][l]{\hskip 1.43501pt\hskip 0.0pt\rule[5.68752pt]{5.47148pt}{0.3014pt}}{\mathcal{M}})}{(1-\kappa)}$, we have

Note that the bound (31) guarantees the excess loss $\phi_{n}(\theta^{t})-\phi_{n}(\widehat{\theta})$ decays geometrically up to any squared error $\delta^{2}$ larger than the compound tolerance (28). Moreover, the RSC condition also allows us to translate this bound on objective values to a bound on the optimization error $\theta^{t}-\widehat{\theta}$. In particular, for any iterate $\theta^{t}$ such that $\phi_{n}(\theta^{t})-\phi_{n}(\widehat{\theta})\leq\delta^{2}$, we are guaranteed that

In conjunction with Theorem 2, we see that it suffices to take a number of steps that is logarithmic in the inverse tolerance $(1/\delta)$, again showing a geometric rate of convergence.

Whereas Theorem 1 requires setting the radius so that the constraint is active, Theorem 2 has only a very mild constraint on the radius $\bar{\rho}$, namely that it be large enough such that $\bar{\rho}\geq\mathcal{R}(\theta^{*})$. The reason for this much milder requirement is that the additive regularization with weight $\lambda_{n}$ suffices to constrain the solution, whereas the extra side constraint is only needed to ensure good behavior of the optimization algorithm in the first few iterations. The regularization parameter $\lambda_{n}$ must satisfy the so-called dual norm condition (29), which has appeared in past literature on statistical estimation, and is well-characterized for a broad range of statistical models (e.g., see the paper and references therein).

It seems that the updates (3) and (4) need to know the smoothness bound $\gamma_{u}$ in order to set the step-size for gradient updates. However, we can use the same doubling trick as described in Algorithm (3.1) of Nesterov . At each step, we check if the smoothness upper bound holds at the current iterate relative to the previous one. If the condition does not hold, we double our estimate of $\gamma_{u}$ and resume. This guarantees a geometric convergence with a contraction factor worse at most by a factor of 2, compared to the knowledge of $\gamma_{u}$. We refer the reader to Nesterov for details.

2 Sparse vector regression

Our convergence rate on the optimization error $\theta^{t}-\widehat{\theta}$ is stated in terms of the contraction coefficient

With this set-up, we have the following consequence of Theorem 1:

Under conditions of Theorem 1, suppose that we solve the constrained Lasso with $\rho\leq\|\theta^{*}\|_{1}$.

Exact sparsity: If $\theta^{*}$ is supported on a subset of cardinality $s$, then with probability at least $1-\exp(-c_{1}\log d)$, the iterates (3) with $\gamma_{u}=2\sigma_{\operatorname{max}}(\Sigma)$ satisfy

We provide the proof of Corollary 2 in Section 5.4. Here we compare part (a), which deals with the special case of exactly sparse vectors, to some past work that has established convergence guarantees for optimization algorithms for sparse linear regression. Certain methods are known to converge at sublinear rates (e.g., ), more specifically at the rate $\mathcal{O}(1/t^{2})$. The geometric rate of convergence guaranteed by Corollary 2 is exponentially faster. Other work on sparse regression has provided geometric rates of convergence that hold once the iterates are close to the optimum , or geometric convergence up to the noise level $\nu^{2}$ using various methods, including greedy methods and thresholded gradient methods . In contrast, Corollary 2 guarantees geometric convergence for all iterates up to a precision below that of statistical error. For these problems, the statistical error $\frac{\nu^{2}s\log d}{n}$ is typically much smaller than the noise variance $\nu^{2}$, and decreases as the sample size is increased.

The tolerance factor in the optimization is given by

Under conditions of Theorem 2, suppose that we solve the regularized Lasso with $\lambda_{n}=6\sqrt{\frac{\nu\log d}{n}}$, and that $\theta^{*}$ is supported on a subset of cardinality at most $s$. Suppose that we have the condition

Then with probability at least $1-\exp(-c_{4}\log d)$, for any $\delta^{2}\geq\epsilon_{\tiny{\mbox{{tol}}}}^{2}$, for any optimum $\widehat{\theta}_{\scriptsize{\lambda_{n}}}$, we have

As with Corollary 2(a), this result guarantees that $\mathcal{O}(\log(1/\epsilon_{\tiny{\mbox{{tol}}}}^{2}))$ iterations are sufficient to obtain an iterate $\theta^{t}$ that is within squared error $\mathcal{O}(\epsilon_{\tiny{\mbox{{tol}}}}^{2})$ of any optimum $\widehat{\theta}_{\scriptsize{\lambda_{n}}}$. The condition (40) is the specialization of Equation 30 to the sparse linear regression problem, and imposes an upper bound on admissible settings of $\bar{\rho}$ for our theory. Moreover, whenever $\frac{s\log d}{n}=o(1)$—a condition that is required for statistical consistency of any method—the optimization tolerance $\epsilon_{\tiny{\mbox{{tol}}}}^{2}$ is of lower order than the statistical error $\|\theta^{*}-\theta\|_{2}^{2}$.

3 Matrix regression with rank constraints

where $\chi_{n}(\Sigma):=\frac{c_{1}\zeta_{\tiny{\mbox{mat}}}(\Sigma)}{\sigma_{\operatorname{max}}(\Sigma)}\;R_{q}\big(\frac{d}{n}\big)^{1-q/2}$ for some universal constant $c_{1}$. In the case $q=0$, corresponding to matrices with rank at most $r$, note that we have $R_{0}=r$. With this notation, we have the following convergence guarantee:

Under conditions of Theorem 1, consider the semidefinite program (19) with $\rho\leq|\!|\!|\Theta^{*}|\!|\!|_{{1}}$, and suppose that we apply the projected gradient updates (20) with $\gamma_{u}=2\sigma_{\operatorname{max}}(\Sigma)$.

Exactly low-rank: In the case $q=0$, if $\Theta^{*}$ has rank $r<d$, then with probability at least $1-\exp(-c_{0}d)$, the iterates (20) satisfy the bound

Although quantitative aspects of the rates are different, Corollary 4 is analogous to Corollary 2. For the case of exactly low rank matrices (part (a)), geometric convergence is guaranteed up to a tolerance involving the statistical error $|\!|\!|\widehat{\Theta}-\Theta^{*}|\!|\!|_{{F}}^{2}$. For the case of approximately low rank matrices (part (b)), the tolerance term involves an additional factor of $R_{q}\big(\frac{d}{n}\big)^{1-q/2}$. Again, from known results on minimax rates for matrix estimation , this term is known to be of comparable or lower order than the quantity $|\!|\!|\widehat{\Theta}-\Theta^{*}|\!|\!|_{{F}}^{2}$. As before, it is also possible to derive an analogous corollary of Theorem 2 for estimating low-rank matrices; in the interests of space, we leave such a development to the reader.

3.2 Bounds for matrix completion

In this model, observation $y_{i}$ is a noisy version of a randomly selected entry $\Theta^{*}_{a(i),b(i)}$ of the unknown matrix $\Theta^{*}$. Applications of this matrix completion problem include collaborative filtering , where the rows of the matrix $\Theta^{*}$ correspond to users, and the columns correspond to items (e.g., movies in the Netflix database), and the entry $\Theta^{*}_{ab}$ corresponds to user’s $a$ rating of item $b$. Given observations of only a subset of the entries of $\Theta^{*}$, the goal is to fill in, or complete the matrix, thereby making recommendations of movies that a given user has not yet seen.

Matrix completion can be viewed as a particular case of the matrix regression model (18), in particular by setting $X_{i}=E_{a(i)b(i)}$, corresponding to the matrix with a single one in position $(a(i),b(i))$, and zeroes in all other positions. Note that these observation matrices are extremely sparse, in contrast to the compressed sensing model. Nuclear-norm based estimators for matrix completion are known to have good statistical properties (e.g., ). Here we consider the $M$-estimator

Again a similar corollary of Theorem 2 can be derived by combining the proof of Corollary 5 with that of Theorem 2. An interesting aspect of this problem is that the condition 30(b) takes the form $\lambda_{n}>\frac{c\alpha\sqrt{d\log d/n}}{1-\kappa}$, where $\alpha$ is a bound on $\|\Theta\|_{\infty}$. This condition is independent of $\bar{\rho}$, and hence, given a sample size as stated in the corollary, the algorithm always converges geometrically for any radius $\bar{\rho}\geq|\!|\!|\Theta^{*}|\!|\!|_{{1}}$.

4 Matrix decomposition problems

In order to estimate the unknown pair $(\Theta^{*},\Gamma^{*})$, we consider the $M$-estimator

With this set-up, consider the projected gradient algorithm when applied to the matrix decomposition problem: it generates a sequence of matrix pairs $(\Theta^{t},\Gamma^{t})$ for $t=0,1,2,\ldots$, and the optimization error is characterized in terms of the matrices $\widehat{\Delta}^{t}_{\Theta}:=\Theta^{t}-\widehat{\Theta}$ and $\widehat{\Delta}^{t}_{\Gamma}:=\Gamma^{t}-\widehat{\Gamma}$. Finally, we measure the optimization error at time $t$ in terms of the squared Frobenius error $e^{2}(\widehat{\Delta}^{t}_{\Theta},\widehat{\Delta}^{t}_{\Gamma}):=|\!|\!|\widehat{\Delta}^{t}_{\Theta}|\!|\!|_{{F}}^{2}+|\!|\!|\widehat{\Delta}^{t}_{\Gamma}|\!|\!|_{{F}}^{2}$, summed across both the low-rank and column-sparse components.

Under the conditions of Theorem 1, suppose that $\|\Theta^{*}\|_{\infty,2}\leq\frac{\alpha}{\sqrt{{d_{2}}}}$ and $\Gamma^{*}$ has at most $s$ non-zero columns. If we solve the convex program (48) with $\rho_{\Theta}\leq|\!|\!|\Theta^{*}|\!|\!|_{{1}}$ and $\rho_{\Gamma}\leq\|\Gamma^{*}\|_{1,2}$, then for all iterations $t=0,1,2,\ldots$,

This corollary has some unusual aspects, relative to the previous corollaries. First of all, in contrast to the previous results, the guarantee is a deterministic one (as opposed to holding with high probability). More specifically, the RSC/RSM conditions hold deterministic sense, which should be contrasted with the high probability statements given in Corollaries 2-5. Consequently, the effective conditioning of the problem does not depend on sample size and we are guaranteed geometric convergence at a fixed rate, independent of sample size. The additional tolerance term is completely independent of the rank of $\Theta^{*}$ and only depends on the column-sparsity of $\Gamma^{*}$.

Simulation results

In this section, we provide some experimental results that confirm the accuracy of our theoretical results, in particular showing excellent agreement with the linear rates predicted by our theory. In addition, the rates of convergence slow down for smaller sample sizes, which lead to problems with relatively poor conditioning. In all the simulations reported below, we plot the log error $\|\theta^{t}-\widehat{\theta}\|$ between the iterate $\theta^{t}$ at time $t$ versus the final solution $\widehat{\theta}$. Each curve provides the results averaged over five random trials, according to the ensembles which we now describe.

For this random ensemble of problems, we have investigated convergence rates for a wide range of dimensions $d$ and radii $R_{q}$. Since the results are relatively uniform across the choice of these parameters, here we report results for dimension $d=20,000$, and radius $R_{q}=\lceil(\log d)^{2}\rceil$. In the case $q=0$, the radius $R_{0}=s$ corresponds to the sparsity level. The per iteration cost in this case is $\mathcal{O}(nd)$. In order to reveal dependence of convergence rates on sample size, we study a range of the form $n=\lceil\alpha\;s\log d\rceil$, where the order parameter $\alpha>0$ is varied.

On the other hand, Corollary 2 also predicts that convergence rates should be slower when the condition number of $\Sigma$ is worse. In order to test this prediction, we again studied an exactly sparse problem ($q=0$), this time with the fixed sample size $n=\lceil 25s\log d\rceil$, and we varied the correlation parameter $\omega\in\{0,0.5,0.8\}$. As shown in panel (b) of Figure 3, the convergence rates slow down as the correlation parameter is increased and for the case of extremely high correlation of $\omega=0.8$, the optimization error curve is almost flat—the method makes very slow progress in this case.

A third prediction of Corollary 2 is that the convergence of projected gradient descent should become slower as the sparsity parameter $q$ is varied between exact sparsity ($q=0$), and the least sparse case ($q=1$). (In particular, note for $n>\log d$, the quantity $\chi_{n}$ from equation (3.2) is monotonically increasing with $q$.) Panel (c) of Figure 3 shows convergence rates for the fixed sample size $n=25s\log d$ and correlation parameter $\omega=0$, and with the sparsity parameter $q\in\{0,0.5,1.0\}$. As expected, the convergence rate slows down as $q$ increases from $0$ to $1$. Corollary 2 further captures how the contraction factor changes as the problem parameters $(s,d,n)$ are varied. In particular, it predicts that as we change the triplet simultaneously, while holding the ratio $\alpha=s\log d/n$ constant, the convergence rate should stay the same. We recall that this phenomenon was indeed demonstrated in Figure 1 in Section 1.

2 Low-rank matrix estimation

In our second set of matrix experiments, we studied the behavior of projected gradient descent for the problem of matrix completion, as described in Section 3.3.2. For this problem, we again studied matrices of dimension $d=200$ and rank $R_{0}=5$, and we varied the sample size as $n=\alpha\>R_{0}\>d\log d$ for $\alpha\in\{1,2,5,25\}$. As shown in panel (b) of Figure 4, projected gradient descent for matrix completion also enjoys geometric convergence for $\alpha$ large enough.

Proofs

In this section, we provide the proofs of our results. Recall that we use $\widehat{\Delta}^{t}:=\theta^{t}-\widehat{\theta}$ to denote the optimization error, and $\Delta^{*}=\widehat{\theta}-\theta^{*}$ to denote the statistical error. For future reference, we point out a slight weakening of restricted strong convexity (RSC), useful for obtaining parts of our results. As the proofs to follow reveal, it is only necessary to enforce an RSC condition of the form

which is milder than the original RSC condition (8), in that it applies only to differences of the form $\theta^{t}-\widehat{\theta}$, and allows for additional slack $\delta$. We make use of this refined notion in the proofs of various results to follow.

With this relaxed RSC condition and the same RSM condition as before, our proof shows that

Note that this result reduces to the previous statement when $\delta=0$. This extension of Theorem 1 is used in the proofs of Corollaries 5 and 6.

Recall that Theorem 1 concerns the constrained problem (1). The proof is based on two technical lemmas. The first lemma guarantees that at each iteration $t=0,1,2,\ldots$, the optimization error $\widehat{\Delta}^{t}=\theta^{t}-\widehat{\theta}$ belongs to an interesting constraint set defined by the regularizer.

Let $\widehat{\theta}$ be any optimum of the constrained problem (1) for which $\mathcal{R}(\widehat{\theta})=\rho$. Then for any iteration $t=1,2,\ldots$ and for any $\mathcal{R}$-decomposable subspace pair $(\mathcal{M},{\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp})$, the optimization error $\widehat{\Delta}^{t}:=\theta^{t}-\widehat{\theta}$ belongs to the set

The proof of this lemma, provided in Appendix A.1, exploits the decomposability of the regularizer in an essential way.

The structure of the set (51) takes a simpler form in the special case when $\mathcal{M}$ is chosen to contain $\theta^{*}$ and $\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}=\mathcal{M}$. In this case, we have $\mathcal{R}(\Pi_{\mathcal{M}^{\perp}}(\theta^{*}))=0$, and hence the optimization error $\widehat{\Delta}^{t}$ satisfies the inequality

An inequality of this type, when combined with the definitions of RSC/RSM, allows us to establish the curvature conditions required to prove globally geometric rates of convergence.

We now state a second lemma under the more general RSC condition (49):

Under the RSC condition (49) and RSM condition (10), for all $t=0,1,2,\ldots$, we have

The proof of this lemma, provided in Appendix A.2, follows along the lines of the intermediate result within Theorem 2.2.8 of Nesterov , but with some care required to handle the additional terms that arise in our weakened forms of strong convexity and smoothness.

Using these auxiliary results, let us now complete the the proof of Theorem 1. We first note the elementary relation

We now use Lemma 2 and the more general form of RSC (49) to control the cross-term, thereby obtaining the upper bound

We now observe that by triangle inequality and the Cauchy-Schwarz inequality,

Recall the definition of the optimization error $\widehat{\Delta}^{t}:=\theta^{t}-\widehat{\theta}$, we have the upper bound

We now apply Lemma 1 to control the terms involving $\mathcal{R}^{2}$. In terms of squared quantities, the inequality (51) implies that

where we recall that $\Psi^{2}({\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp})$ is the subspace compatibility (12) and $\nu^{2}(\Delta^{*};\mathcal{M},\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}})$ accumulates all the residual terms. Applying this bound twice—once for $t$ and once for $t+1$—and substituting into equation (55) yields that $\big\{1-\frac{16\Psi^{2}({\makebox[0.0pt][l]{\hskip 1.43501pt\hskip 0.0pt\rule[5.68752pt]{5.47148pt}{0.3014pt}}{\mathcal{M}}}^{\perp})\tau_{u}(\mathcal{L}_{n})}{\gamma_{u}}\big\}\|\Delta^{t+1}\|^{2}$ is upper bounded by

Under the assumptions of Theorem 1, we are guaranteed that $\frac{16\Psi^{2}(\makebox[0.0pt][l]{\hskip 1.43501pt\hskip 0.0pt\rule[5.68752pt]{5.47148pt}{0.3014pt}}{\mathcal{M}}^{\perp})\tau_{u}(\mathcal{L}_{n})}{\gamma_{u}}<1/2$, and so we can re-arrange this inequality into the form

where $\kappa$ and $\epsilon^{2}(\Delta^{*};\mathcal{M},\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}})$ were previously defined in equations (22) and (23) respectively. Iterating this recursion yields

The assumptions of Theorem 1 guarantee that $\kappa\in(0,1)$, so that summing the geometric series yields the claim (24).

2 Proof of Theorem 2

The Lagrangian version of the optimization program is based on solving the convex program (2), with the objective function $\phi(\theta)=\mathcal{L}_{n}(\theta)+\lambda_{n}\mathcal{R}(\theta)$. Our proof is based on analyzing the error $\phi(\theta^{t})-\phi(\widehat{\theta})$ as measured in terms of this objective function. It requires two technical lemmas, both of which are stated in terms of a given tolerance $\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}>0$, and an integer $T>0$ such that

Our first technical lemma is analogous to Lemma 1, and restricts the optimization error $\widehat{\Delta}^{t}=\theta^{t}-\widehat{\theta}$ to a cone-like set.

Let $\widehat{\theta}$ be any optimum of the regularized $M$-estimator (2). Under condition (57) with parameters $(T,\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta})$, for any iteration $t\geq T$ and for any $\mathcal{R}$-decomposable subspace pair $(\mathcal{M},{\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp})$, the optimization error $\widehat{\Delta}^{t}:=\theta^{t}-\widehat{\theta}$ satisfies

Our next lemma guarantees sufficient decrease of the objective value difference $\phi(\theta^{t})-\phi(\widehat{\theta})$. Lemma 3 plays a crucial role in its proof. Recall the definition (27) of the compound contraction coefficient $\kappa(\mathcal{L}_{n};\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}})$, defined in terms of the related quantities $\xi(\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}})$ and $\beta(\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}})$. Throughout the proof, we drop the arguments of $\kappa$, $\xi$ and $\beta$ so as to ease notation.

Under the RSC (49) and RSM conditions (10), as well as assumption (57) with parameters $(\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta},T)$, for all $t\geq T$, we have

where $\varepsilon:=2\min(\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}/\lambda_{n},\bar{\rho})$ and $\bar{\epsilon}_{\text{stat}}:=8\Psi(\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}})\|\Delta^{*}\|+8\mathcal{R}(\Pi_{\mathcal{M}^{\perp}}(\theta^{*}))$.

We are now in a position to prove our main theorem, in particular via a recursive application of Lemma 4. At a high level, we divide the iterations $t=0,1,2,\ldots$ into a series of disjoint epochs $[T_{k},T_{k+1})$ with $0=T_{0}\leq T_{1}\leq T_{2}\leq\cdots$. Moreover, we define an associated sequence of tolerances $\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{0}>\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{1}>\cdots$ such that at the end of epoch $[T_{k-1},T_{k})$, the optimization error has been reduced to $\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{k}$. Our analysis guarantees that $\phi(\theta^{t})-\phi(\widehat{\theta})\leq\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{k}$ for all $t\geq T_{k}$, allowing us to apply Lemma 4 with smaller and smaller values of $\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}$ until it reduces to the statistical error $\bar{\epsilon}_{\text{stat}}$.

At the first iteration, we have no a priori bound on the error $\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{0}=\phi(\theta^{0})-\phi(\widehat{\theta})$. However, since Lemma 4 involves the quantity $\varepsilon=\min(\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}/\lambda_{n},\bar{\rho})$, we may still apply it It is for precisely this reason that our regularized $M$-estimator includes the additional side-constraint defined in terms of $\bar{\rho}$. at the first epoch with $\varepsilon_{0}=\bar{\rho}$ and $T_{0}=0$. In this way, we conclude that for all $t\geq 0$,

Now since the contraction coefficient $\kappa\in(0,1)$, for all iterations $t\geq T_{1}:=(\lceil\log(2\,\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{0}/\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{1})/\log(1/\kappa)\rceil)_{+}$, we are guaranteed that

This same argument can now be applied in a recursive manner. Suppose that for some $k\geq 1$, we are given a pair $(\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{k},T_{k})$ such that condition (57) holds. An application of Lemma 4 yields the bound

We now define $\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{k+1}:=\frac{4\,\xi\beta}{1-\kappa}(\varepsilon_{k}^{2}+\bar{\epsilon}_{\text{stat}}^{2})$. Once again, since $\kappa<1$ by assumption, we can choose $T_{k+1}:=\lceil\log(2\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{k}/\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{k+1})/\log(1/\kappa)\rceil+T_{k}$, thereby ensuring that for all $t\geq T_{k+1}$, we have

In this way, we arrive at recursive inequalities involving the tolerances $\{\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{k}\}_{k=0}^{\infty}$ and time steps $\{T_{k}\}_{k=0}^{\infty}$—namely

Now we claim that the recursion (59a) can be unwrapped so as to show that

Taking these statements as given for the moment, let us now show how they can be used to upper bound the smallest $k$ such that $\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{k}\leq\delta^{2}$. If we are in the first epoch, the claim of the theorem is straightforward from equation (59a). If not, we first use the recursion (60) to upper bound the number of epochs needed and then use the inequality (59b) to obtain the stated result on the total number of iterations needed. Using the second inequality in the recursion (60), we see that it is sufficient to ensure that $\frac{\bar{\rho}\lambda_{n}}{4^{2^{k-1}}}\;\leq\;\delta^{2}$. Rearranging this inequality, we find that the error drops below $\delta^{2}$ after at most

epochs. Combining the above bound on $k_{\delta}$ with the recursion 59b, we conclude that the inequality $\phi(\theta^{t})-\phi(\widehat{\theta})\leq\delta^{2}$ is guaranteed to hold for all iterations

It remains to prove the recursion (60), which we do via induction on the index $k$. We begin with base case $k=1$. Recalling the setting of $\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{1}$ and our assumption on $\lambda_{n}$ in the theorem statement (30), we are guaranteed that $\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{1}/\lambda_{n}\leq\bar{\rho}/4$, so that $\varepsilon_{1}\leq\varepsilon_{0}=\bar{\rho}$. By applying equation (59a) with $\varepsilon_{1}=2\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{1}/\lambda_{n}$ and assuming $\varepsilon_{1}\geq\bar{\epsilon}_{\text{stat}}$, we obtain

where step (i) uses the fact that $\frac{\makebox[0.0pt][l]{\hskip 0.90417pt\hskip 0.40833pt\rule[3.91806pt]{2.66728pt}{0.3014pt}}{\eta}_{1}}{\lambda_{n}}\leq\frac{\bar{\rho}}{4}$, and step (ii) uses the condition (30) on $\lambda_{n}$. We have thus verified the first inequality (60) for $k=1$. Turning to the second inequality in the statement (60), using equation 61, we have

where step (iii) follows from the assumption (30) on $\lambda_{n}$. Turning to the inductive step, we again assume that $2\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}_{k}/\lambda_{n}\geq\bar{\epsilon}_{\text{stat}}$ and obtain from inequality (59a)

Here step (iv) uses the second inequality of the inductive hypothesis (60) and step (v) is a consequence of the condition on $\lambda_{n}$ as before. The second part of the induction is similarly established, completing the proof.

3 Proof of Corollary 1

If $\rho\leq\mathcal{R}(\theta^{*})$, then for any solution $\widehat{\theta}$ of the constrained problem (1) and any $\mathcal{R}$-decomposable subspace pair $(\mathcal{M},\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}^{\perp})$, the statistical error $\Delta^{*}=\widehat{\theta}-\theta^{*}$ satisfies the inequality

Using this lemma, we can complete the proof of Corollary 1. Recalling the form (23), under the condition $\theta^{*}\in\mathcal{M}$, we have

4 Proofs of Corollaries 2 and 3

with probability at least $1-\exp(-c_{0}\,n)$.

Note that this lemma implies that the RSC and RSM conditions both hold with high probability, in particular with parameters

This lemma has been proved by Raskutti et al. for obtaining minimax rates in sparse linear regression.

where $\chi_{n}(\Sigma):=\frac{c_{2}\zeta(\Sigma)}{\sigma_{\operatorname{max}}(\Sigma)}\;\frac{s\log d}{n}$ for some universal constant $c_{2}$. A similar calculation shows that the tolerance term takes the form

Since $\rho\leq\|\theta^{*}\|_{1}$, then Lemma 5 (as exploited in the proof of Corollary 1) shows that $\|\Delta^{*}\|^{2}_{1}\leq 4s\|\Delta^{*}\|_{2}^{2}$, and hence that $\epsilon^{2}(\Delta^{*};\mathcal{M},\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}})\leq c_{3}\;\chi_{n}(\Sigma)\;\|\Delta^{*}\|_{2}^{2}$. This completes the proof of the claim (37) for $q=0$.

We now turn to the case $q\in(0,1]$, for which we bound the term $\epsilon^{2}(\Delta^{*};\mathcal{M},\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}})$ using a slightly different choice of the subspace pair $\mathcal{M}$ and ${\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp}$. For a truncation level $\mu>0$ to be chosen, define the set $S_{\mu}:=\big\{j\in\{1,2,\ldots,d\}\,\mid\,|\theta^{*}_{j}|>\mu\big\}$, and define the associated subspaces $\mathcal{M}=\mathcal{M}(S_{\mu})$ and ${\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp}=\mathcal{M}^{\perp}(S_{\mu})$. By combining Lemma 5 and the definition (23) of $\epsilon^{2}(\Delta^{*};\mathcal{M},\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}})$, for any pair $(\mathcal{M}(S_{\mu}),\mathcal{M}^{\perp}(S_{\mu}))$, we have

where to simplify notation, we have omitted the dependence of $\mathcal{M}$ and $\mathcal{M}^{\perp}$ on $S_{\mu}$. We now choose the threshold $\mu$ optimally, so as to trade-off the term $\|\Pi_{\mathcal{M}^{\perp}}(\theta^{*})\|_{1}$, which decreases as $\mu$ increases, with the term $\sqrt{S_{\mu}}\|\Delta^{*}\|_{2}$, which increases as $\mu$ increases.

By definition of $\mathcal{M}^{\perp}(S_{\mu})$, we have

Setting $\mu^{2}=\,\frac{\log d}{n}$ then yields

Finally, let us verify the stated form of the contraction coefficient. For the given subspace $\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}^{\perp}=\mathcal{M}(S_{\mu})$ and choice of $\mu$, we have $\Psi^{2}(\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}^{\perp})=|S_{\mu}|\leq\mu^{-q}R_{q}$. From Lemma 6, we have

and hence, by definition (22) of the contraction coefficient,

5 Proof of Corollary 4

Under the conditions of Corollary 4, there are universal positive constants $(c_{0},c_{1})$ such that

with probability at least $1-\exp(-c_{0}\,n)$.

We now prove Corollary 4 in the special case of exactly low rank matrices ($q=0$), in which $\Theta^{*}$ has some rank $r\leq d$. Given the singular value decomposition $\Theta^{*}=UDV^{T}$, let $U^{r}$ and $V^{r}$ be the $d\times r$ matrices whose columns correspond to the $r$ non-zero (left and right, respectively) singular vectors of $\Theta^{*}$. As in Section 2.4.2, define the subspace of matrices

as well as the associated set ${\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp}(U^{r},V^{r})$. Note that $\Theta^{*}\in\mathcal{M}$ by construction, and moreover (as discussed in Section 2.4.2, the nuclear norm is decomposable with respect to the pair $(\mathcal{M},{\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp})$.

where $\chi_{n}(\Sigma):=\frac{c_{2}\zeta_{\tiny{\mbox{mat}}}(\Sigma)}{\sigma_{\operatorname{max}}(\Sigma)}\;\frac{rd}{n}$ for some universal constant $c_{2}$. A similar calculation shows that the tolerance term takes the form

Since $\rho\leq|\!|\!|\Theta^{*}|\!|\!|_{{1}}$ by assumption, Lemma 5 (as exploited in the proof of Corollary 1) shows that $|\!|\!|\Delta^{*}|\!|\!|_{{1}}^{2}\leq 4r|\!|\!|\Delta^{*}|\!|\!|_{{F}}^{2}$, and hence that

Now by a combination of Lemma 5 and the definition (23) of $\epsilon^{2}(\Delta^{*};\mathcal{M},\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}})$, for any pair $(\mathcal{M}(S_{\mu}),{\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp}(S_{\mu}))$, we have

Setting $\mu^{2}=\frac{d}{n}$ then yields

as claimed. The stated form of the contraction coefficient can be verified by a calculation analogous to the proof of Corollary 2.

6 Proof of Corollary 5

There is a constant $c$ such that for all iterations $t=0,1,2,\ldots$ and integers $r=1,2,\ldots,d-1$, with probability at least $1-\exp(-d\log d)$,

There is a constant $c$ such that for all iterations $t=0,1,2,\ldots$ and integers $r=1,2,\ldots,d-1$, with probability at least $1-\exp(-d\log d)$, the difference $\Gamma^{t}:=\Theta^{t+1}-\Theta^{t}$ satisfies the inequality $\frac{\|\mathfrak{X}_{n}(\Gamma^{t})\|_{2}^{2}}{n}\leq 2|\!|\!|\Gamma^{t}|\!|\!|_{{F}}^{2}+\delta_{u}(r)$, where

We can now complete the proof of Corollary 5 by a minor modification of the proof of Theorem 1. Recalling the elementary relation (54), we have

Consequently, as long as $\min\{|\!|\!|\widehat{\Delta}^{t}|\!|\!|_{{F}}^{2},\;|\!|\!|\widehat{\Delta}^{t+1}|\!|\!|_{{F}}^{2}\}\geq c_{3}\alpha\frac{rd\log d}{n}$ for a sufficiently large constant $c_{3}$, we are guaranteed the existence of some $\kappa_{t}\in(0,1)$ decreasing with $t$ such that

Since $\kappa_{t}$ is decreasing in $t$, we observe that the second term in the above bound is at most

We also define $\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.0pt\rule[5.59721pt]{4.2464pt}{0.43057pt}}{\kappa}_{t}=(\sum_{s=1}^{t}\kappa_{t})/t$. Then the arithmetic mean-geometric mean inequality yields the upper bound $\prod_{s=1}^{t}\kappa_{s}\leq\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.0pt\rule[5.59721pt]{4.2464pt}{0.43057pt}}{\kappa}_{t}^{t}$. Combining this with our earlier upper bound further yields the inequality

holds. Now by the Cauchy-Schwarz inequality we have

7 Proof of Corollary 6

Again the main argument in the proof would be to establish the RSM and RSC properties for the decomposition problem. We define $\widehat{\Delta}^{t}_{\Theta}=\Theta^{t}-\widehat{\Theta}$ and $\widehat{\Delta}^{t}_{\Gamma}=\Gamma^{t}-\widehat{\Gamma}$. We start with giving a lemma that establishes RSC for the differences $(\widehat{\Delta}^{t}_{\Theta},\widehat{\Delta}^{t}_{\Gamma})$. We recall that just like noted in the previous section, it suffices to show RSC only for these differences. Showing RSC/RSM in this example amounts to analyzing $|\!|\!|\widehat{\Delta}^{t}_{\Theta}+\widehat{\Delta}^{t}_{\Gamma}|\!|\!|_{{F}}^{2}$. We recall that this section assumes that $\Gamma^{*}$ has only $s$ non-zero columns.

There is a constant $c$ such that for all iterations $t=0,1,2,\dots$,

This proof of this lemma follows by a straightforward modification of analogous results in the paper .

Matrix decomposition has the interesting property that the RSC condition holds in a deterministic sense (as opposed to with high probability). The same deterministic guarantee holds for the RSM condition; indeed, we have

by Cauchy-Schwartz inequality. Now we appeal to the more general form of Theorem 1 as stated in Equation 50, which gives

The stated form of the corollary follows by an application of Cauchy-Schwarz inequality.

Discussion

All three authors were partially supported by grants AFOSR-09NL184; in addition, AA was partially supported by a Microsoft Graduate Fellowship and Google PhD Fellowship, and SN and MJW acknowledge funding from NSF-CDI-0941742. We would like to thank the anonymous reviewers and associate editor for their helpful comments that helped to improve the paper, and Bin Yu for inspiring discussions on the interaction between statistical and optimization error.

Appendix A Auxiliary results for Theorem 1

In this appendix, we provide the proofs of various auxiliary lemmas required in the proof of Theorem 1.

Since $\theta^{t}$ and $\widehat{\theta}$ are both feasible and $\widehat{\theta}$ lies on the constraint boundary, we have $\mathcal{R}(\theta^{t})\leq\mathcal{R}(\widehat{\theta})$. Since $\mathcal{R}(\widehat{\theta})\leq\mathcal{R}(\theta^{*})+\mathcal{R}(\widehat{\theta}-\theta^{*})$ by triangle inequality, we conclude that

Since $\theta^{*}=\Pi_{\mathcal{M}}(\theta^{*})+\Pi_{\mathcal{M}^{\perp}}(\theta^{*})$, a second application of triangle inequality yields

Now define the difference $\Delta^{t}:=\theta^{t}-\theta^{*}$. (Note that this is slightly different from $\widehat{\Delta}^{t}$, which is measured relative to the optimum $\widehat{\theta}$.) With this notation, we have

where steps (i) and (ii) each use the triangle inequality. Now by the decomposability condition, we have $\mathcal{R}\big(\Pi_{\mathcal{M}}(\theta^{*})+\Pi_{\bar{\mathcal{M}}^{\perp}}(\Delta^{t})\big)=\mathcal{R}(\Pi_{\mathcal{M}}(\theta^{*}))+\mathcal{R}(\Pi_{\bar{\mathcal{M}}^{\perp}}(\Delta^{t}))$, so that we have shown that

Combining this inequality with the earlier bound (75) yields

The final step is to translate this inequality into one that applies to the optimization error $\widehat{\Delta}^{t}=\theta^{t}-\widehat{\theta}$. Recalling that $\Delta^{*}=\widehat{\theta}-\theta^{*}$, we have $\widehat{\Delta}^{t}=\Delta^{t}-\Delta^{*}$, and hence

where inequality (i) uses the bound (76), and inequality (ii) uses the definition (12) of the subspace compatibility $\Psi$. Combining with the inequality (77) yields

Since projection onto a subspace is non-expansive, we have $\|\Pi_{\bar{\mathcal{M}}}(\Delta^{t})\|\leq\|\Delta^{t}\|$, and hence

Combining the pieces, we obtain the claim (51).

A.2 Proof of Lemma 2

We start by applying the RSC assumption to the pair $\widehat{\theta}$ and $\theta^{t}$, thereby obtaining the lower bound

Here the second inequality follows by adding and subtracting terms.

where the last step follows from adding and subtracting $\theta^{t+1}$ in the inner product.

and the claim (53) follows after some simple algebraic manipulations.

Appendix B Auxiliary results for Theorem 2

In this appendix, we prove the two auxiliary lemmas required in the proof of Theorem 2.

This result is a generalization of an analogous result in Negahban et al. , with some changes required so as to adapt the statement to the optimization setting. Let $\theta$ be any vector, feasible for the problem (2), that satisfies the bound

and assume that $\lambda_{n}\geq 2\mathcal{R}^{*}(\nabla\mathcal{L}_{n}(\theta^{*}))$. We then claim that the error vector $\Delta:=\theta-\theta^{*}$ satisfies the inequality

For the moment, we take this claim as given, returning later to verify its validity.

By applying this intermediate claim (82) in two different ways, we can complete the proof of Lemma 3. First, we observe that when $\theta=\widehat{\theta}$, the optimality of $\widehat{\theta}$ and feasibility of $\theta^{*}$ imply that assumption (81) holds with $\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}=0$, and hence the intermediate claim (82) implies that the statistical error $\Delta^{*}=\theta^{*}-\widehat{\theta}$ satisfies the bound

Since $\Delta^{*}=\Pi_{\bar{\mathcal{M}}}(\Delta^{*})+\Pi_{\bar{\mathcal{M}}^{\perp}}(\Delta^{*})$, we can write

using the triangle inequality in conjunction with our earlier bound (83). Similarly, when $\theta=\theta^{t}$ for some $t\geq T$, then the given assumptions imply that condition (81) holds with $\makebox[0.0pt][l]{\hskip 1.29167pt\hskip 0.58333pt\rule[5.59721pt]{2.93578pt}{0.43057pt}}{\eta}>0$, so that the intermediate claim (followed by the same argument with triangle inequality) implies that the error $\Delta^{t}=\theta^{t}-\theta^{*}$ satisfies the bound

Now let $\widehat{\Delta}^{t}=\theta^{t}-\widehat{\theta}$ be the optimization error at time $t$, and observe that we have the decomposition $\widehat{\Delta}^{t}=\Delta^{t}+\Delta^{*}$. Consequently, by triangle inequality

where step (i) follows by applying both equation (84) and (85); step (ii) follows from the definition (12) of the subspace compatibility that relates the regularizer to the norm $\|\cdot\|$; and step (iii) follows from the fact that projection onto a subspace is non-expansive. Finally, since $\Delta^{t}=\widehat{\Delta}^{t}-\Delta^{*}$, the triangle inequality implies that $\|\Delta^{t}\|\leq\|\widehat{\Delta}^{t}\|+\|\Delta^{*}\|$. Substituting this upper bound into inequality (86) completes the proof of Lemma 3.

It remains to prove the intermediate claim (82). Letting $\theta$ be any vector, feasible for the program (2), and satisfying the condition (81), and let $\Delta=\theta-\theta^{*}$ be the associated error vector. Re-writing the condition (81), we have

Subtracting $\big\langle\nabla\mathcal{L}_{n}(\theta^{*}),\,\Delta\big\rangle$ from each side and then re-arranging yields the inequality

The convexity of $\mathcal{L}_{n}$ then implies that $\mathcal{L}_{n}(\theta^{*}+\Delta)-\mathcal{L}_{n}(\theta^{*})-\big\langle\nabla\mathcal{L}_{n}(\theta^{*}),\,\Delta\big\rangle\geq 0$, and hence that

Applying Hölder’s inequality to $\big\langle\nabla\mathcal{L}_{n}(\theta^{*}),\,\Delta\big\rangle$, as expressed in terms of the dual norms $\mathcal{R}$ and $\mathcal{R}^{*}$, yields the upper bound

where step (i) uses the fact that $\lambda_{n}\geq 2\mathcal{R}^{*}(\nabla\mathcal{L}_{n}(\theta^{*}))$ by assumption.

For the remainder of the proof, let us introduce the convenient shorthand $\Delta_{\bar{\mathcal{M}}}:=\Pi_{\bar{\mathcal{M}}}(\Delta)$ and $\Delta_{\bar{\mathcal{M}}^{\perp}}:=\Pi_{\bar{\mathcal{M}}^{\perp}}(\Delta)$, with similar shorthand for projections involving $\theta^{*}$. Making note of the decomposition $\Delta=\Delta_{\bar{\mathcal{M}}}+\Delta_{\bar{\mathcal{M}}^{\perp}}$, an application of triangle inequality then yields the upper bound

where we have rescaled both sides by $\lambda_{n}>0$.

It remains to further lower bound the left-hand side (87). By triangle inequality, we have

Let us now write $\theta^{*}+\Delta=\theta^{*}_{\mathcal{M}}+\theta^{*}_{\mathcal{M}^{\perp}}+\Delta_{\bar{\mathcal{M}}}+\Delta_{\bar{\mathcal{M}}^{\perp}}$. Using this representation and triangle inequality, we have

Finally, since $\theta^{*}_{\mathcal{M}}\in\mathcal{M}$ and $\Delta_{\bar{\mathcal{M}}^{\perp}}\in{\makebox[0.0pt][l]{\hskip 2.05pt\hskip 0.0pt\rule[8.12498pt]{6.76082pt}{0.43057pt}}{\mathcal{M}}}^{\perp}$, the decomposability of $\mathcal{R}$ implies that $\mathcal{R}(\theta^{*}_{\mathcal{M}}+\Delta_{\bar{\mathcal{M}}^{\perp}})=\mathcal{R}(\theta^{*}_{\mathcal{M}})+\mathcal{R}(\Delta_{\bar{\mathcal{M}}^{\perp}})$, and hence that

Adding together equations (88) and (89), we obtain the lower bound

Combining this lower bound with the earlier inequality (87), some algebra yields the bound

corresponding to the bound (82) when $\eta/\lambda_{n}$ achieves the final minimum. To obtain the final term involving $\bar{\rho}$ in the bound (82), two applications of triangle inequality yields

where we have used the fact that $\mathcal{R}(\Delta)\leq\mathcal{R}(\theta)+\mathcal{R}(\theta^{*})\leq 2\bar{\rho}$, since both $\theta$ and $\theta^{*}$ are feasible for the program (2).

B.2 Proof of Lemma 4

The proof of this result follows lines similar to the proof of convergence by Nesterov . Recall our notation $\phi(\theta)=\mathcal{L}_{n}(\theta)+\lambda_{n}\mathcal{R}(\theta)$, $\widehat{\Delta}^{t}=\theta^{t}-\widehat{\theta}$, and that $\eta^{t}_{\phi}=\phi(\theta^{t})-\phi(\widehat{\theta})$. We begin by proving that under the stated conditions, a useful version of restricted strong convexity (49) is in force:

Under the assumptions of Lemma 4, we are guaranteed that

where $v:=\bar{\epsilon}_{\text{stat}}+2\min(\frac{\makebox[0.0pt][l]{\hskip 0.90417pt\hskip 0.40833pt\rule[3.91806pt]{2.66728pt}{0.3014pt}}{\eta}}{\lambda_{n}},\bar{\rho})$.