Nuclear norm penalization and optimal rates for noisy low rank matrix completion

Introduction

It will be convenient to write the model (1.1) in the form

Here $\Pi=\frac{1}{n}\sum_{i=1}^{n}\Pi_{i}$, where $\Pi_{i}$ denotes the distribution of $X_{i}$. The corresponding semi-norm $\|A\|_{L_{2}(\Pi)}$ is given by

Example 1. Matrix Completion. Assume that the design matrices $X_{i}$ are i.i.d. uniformly distributed on the set

One can also consider more general matrix measurement models in which, for a given orthonormal basis in the space of matrices, a random sample of Fourier coefficients of the target matrix $A_{0}$ is observed subject to a random noise. For more discussion on matrix completion with other types of sampling, see and references therein.

Example 4. Fixed design. Assume that all the $\Pi_{i}$ are Dirac measures, so that the design matrices $X_{i}$ are non-random. Then $\|A\|_{L_{2}(\Pi)}^{2}=\frac{1}{n}\sum_{i=1}^{n}\langle A,X_{i}\rangle^{2},$ and we get the problem of trace regression with fixed design, cf. . In particular, if $m_{1}=m_{2}$, and $A$ and $X_{i}$ are diagonal matrices the trace regression model (1.2) becomes the usual linear regression model. Accordingly, the rank of $A$ becomes the number of its non-zero diagonal elements. This observation will allow us to deduce, as a consequence of our general argument, an oracle inequality for the usual Lasso in sparse linear regression with fixed design improving in the sense that the inequality is sharp (cf. Theorem 2 and Section 5.4).

The general oracle inequalities that we will prove in Section 2 can be successfully applied to the above examples. The emphasis in this paper will be on the matrix completion problem (Example 1), for which the previously obtained results were suboptimal.

Statistical estimation of low-rank matrices has recently become a very active field with a rapidly growing literature. The most popular methods are based on penalized empirical risk minimization with nuclear-norm penalty . Estimators with other types of penalization, such as the Schatten-$p$ norm , the von Neumann entropy , penalization by the rank or some combined penalties are also discussed.

The emphasis in this paper is on the noisy matrix completion setting. Then the estimator ${\hat{A}}^{\lambda}$ has a particularly simple form; it is obtained from the matrix $\frac{m_{1}m_{2}}{n}\sum_{i=1}^{n}Y_{i}X_{i}$ by soft thresholding of its singular values. One of the main results of this paper is to show that our estimators are rate optimal (up to logarithmic factors) under the Frobenius error for a simple class of matrices ${\cal A}(r,a)$ defined by two restrictions: the rank of $A_{0}$ is not larger than given $r$ and all the entries of $A_{0}$ are bounded in absolute value by a constant $a$. This rather intuitive class has been first considered in . However, the construction of the estimator in requires the exact knowledge of ${\rm rank}(A_{0})$ and the upper bound on the Frobenius error obtained in is suboptimal (see the details in Section 3). The recent paper obtains suboptimal bounds of ”slow rate” type for matrix completion while focuses on complex-valued Hermitian matrices with nuclear norm equal to 1, which is motivated by density matrix estimation problem in quantum state tomography. These papers do not address the optimality issue. Optimal rates in noisy matrix completion are derived in , but on different classes of matrices and with the empirical prediction error rather than with the Frobenius error. Finally, discusses the optimality issue for the Frobenius error on the classes defined in terms of a ”spikiness index” of $A_{0}$, which are not related to ${\cal A}(r,a)$, and suggests estimators that require prior knowledge about this index.

The main contributions of this paper are the following. In Section 2 we derive a general oracle inequality for the prediction error $\|{\hat{A}}^{\lambda}-A_{0}\|_{L_{2}(\Pi)}^{2}$. This oracle inequality is sharp, i.e., with leading constant 1, both in the case of ”slow rate” (for matrices $A_{0}$ with small nuclear norm) and in the case of ”fast rate” (for matrices $A_{0}$ with small rank). As a particular instance of this general result, in Section 3 we obtain an oracle inequality for the matrix completion problem. In Section 4, we establish minimax lower bounds showing that the rates for matrix completion obtained in Section 3 are optimal up to a logarithmic factor. In Section 5, we briefly discuss some other implications and extensions of our method. Finally, Section 6 is devoted to the control of the stochastic term appearing in the proof of the upper bound.

General oracle inequalities

The Schatten-$p$ (quasi-)norm $\|A\|_{p}$ of matrix $A$ is defined by

Recall the well-known trace duality property:

We will also use the fact that the subdifferential of the convex function $A\mapsto\|A\|_{1}$ is the following set of matrices:

We will need the following assumption on the distribution of the matrices $X_{i}$.

where we set for brevity $\Delta=\|{\bf M}\|_{\infty}$. Under the assumption $\lambda\geq 2\Delta$ this yields

where $\hat{V}\in\partial\|\hat{A}^{\lambda}\|_{1}.$ The condition that $-B$ belongs to the normal cone at the point $\hat{A}^{\lambda}$ implies that $\langle B,\hat{A}^{\lambda}-A\rangle\leq 0,$ and (2.6) follows.

for an arbitrary $V\in\partial\|A\|_{1}.$ By monotonicity of subdifferentials of convex functions, $\langle\hat{V}-V,{\hat{A}}^{\lambda}-A\rangle\geq 0.$ On the other hand, by (2.1), the following representation holds

where $W$ is an arbitrary matrix with $\|W\|_{\infty}\leq 1.$ It follows from the trace duality that there exists $W$ with $\|W\|_{\infty}\leq 1$ such that

where in the first equality we used that $A$ has the support $(S_{1},S_{2}).$ For this particular choice of $W,$ (2.7) implies that

To provide an upper bound on $2\langle{\bf M},{\hat{A}}^{\lambda}-A\rangle$ we use the following decomposition

where ${\cal P}_{A}({\bf M})={\bf M}-P_{S_{1}^{\perp}}{\bf M}P_{S_{2}^{\perp}}$. This implies, due to the trace duality,

and ${\rm rank}(P_{S_{j}})\leq{\rm rank}(A)$, $j=1,2$, we have

and to Assumption 1, it follows from (2) and (2) that

Using the above bounds on $\Lambda$ and $\Gamma,$ we obtain from (2) that

The following immediate corollary of Theorem 1 provides a bound for the Frobenius error.

and, for $c_{0}\geq 0,$ define the following cone of matrices:

Upper bounds for matrix completion

We can also write ${\hat{A}}^{\lambda}$ explicitly:

where $x_{+}=\max\{x,0\}$, $\sigma_{j}({\mathbf{X}})$ are the singular values and $u_{j}({\mathbf{X}}),v_{j}({\mathbf{X}})$ are the left and right singular vectors of ${\mathbf{X}}=\sum_{j=1}^{{\rm rank}({\mathbf{X}})}\sigma_{j}({\mathbf{X}})u_{j}({\mathbf{X}})v_{j}({\mathbf{X}})^{\top}$. Thus, ${\hat{A}}^{\lambda}$ has a particularly simple form; it is obtained by soft thresholding of singular values in the SVD of ${\mathbf{X}}$. To see why (3.2) gives the solution of (3.1), note that, in view of (2.1), the subdifferential of $F(A)=\|A-{\mathbf{X}}\|_{2}^{2}+\lambda m_{1}m_{2}\|A\|_{1}$ is the set of matrices

where $r,u_{j},v_{j},S_{1},S_{2}$ correspond to the SVD of $A$. Since $A\mapsto F(A)$ is strictly convex, the minimizer ${\hat{A}}^{\lambda}$ is unique, and the condition ${\bf 0}\in\partial F({\hat{A}}^{\lambda})$ is necessary and sufficient characterization of the minimum, where ${\bf 0}$ is the zero $m_{1}\times m_{2}$ matrix. Considering

it is easy to check that (3.2) satisfies this condition.

We will see that the soft thresholding representation (3.2) helps to understand in an easy way some theoretical properties of ${\hat{A}}^{\lambda}$. However, it may not be always preferable for computational issues. Indeed, the standard techniques of computation of the SVD can become numerically instable when the dimension is high. On the other hand, we can always compute ${\hat{A}}^{\lambda}$ from (3.1) using the methods of convex programming free from this drawback.

In view of Theorem 1, to get the oracle inequalities in a closed form it remains only to specify the value of regularization parameter $\lambda$ such that $\lambda\geq 2\|{\bf M}\|_{\infty}$ with high probability. This requires some assumptions on the distribution of $(X_{i},Y_{i})$, and the value of $\lambda$ will be different under different assumptions. We will consider only the following two cases of particular interest.

and $\max_{i,j}|a_{0}(i,j)|\leq a$ for some constant $a$.

Statistical learning setting. There exists a constant $\eta$ such that $\max_{i=1,\dots,n}|Y_{i}|\leq\eta$ almost surely.

In both cases, we obtain the upper bounds for $\|{\bf M}\|_{\infty}$ (that we call the stochastic error) using the non-commutative Bernstein inequalities, cf. Section 6. The resulting values of $\lambda$ and the corresponding oracle inequalities are given in the next two theorems.

Set $m=m_{1}+m_{2}$. In what follows, we will denote by $C$ absolute positive constants, possibly different on different occasions.

Let $X_{i}$ be i.i.d. uniformly distributed on $\mathcal{X}$, and the pairs $(X_{i},Y_{i})$ be i.i.d. Assume that $\max_{i,j}|a_{0}(i,j)|\leq a$ for some constant $a$, and that condition (3.3) holds. For $t>0,$ consider the regularization parameter $\lambda$ satisfying

Let $X_{i}$ be i.i.d. uniformly distributed on $\mathcal{X}$. Assume that $\max_{i=1,\dots,n}|Y_{i}|\leq\eta$ almost surely for some constant $\eta$. For $t>0$ consider the regularization parameter $\lambda$ satisfying

Theorems 3 and 4 follow immediately from Theorem 1 and Lemmas 1, 2 and 3 with $\mu=\sqrt{m_{1}m_{2}}$.

Note that the natural choice of $t$ in Theorems 3 and 4 is of the order $\log(m)$, since a larger $t$ leads to slower rate of convergence and a smaller $t$ does not improve the rate but makes the concentration probability smaller. Note also that, under this choice of $t$, the second terms under the maxima in (3.4) and (3.6) are negligible for the values of $n,m_{1},m_{2}$ such that the term containing ${\rm rank}(A_{0})$ in (3.5) is meaningful. Indeed, if $t$ is of the order $\log(m)$, the condition that $m_{1}m_{2}\lambda^{2}\ll 1$ necessarily implies $n\gg(m_{1}\vee m_{2})\log(m)$. On the other hand, the negligibility of the second terms under the maxima in (3.4) and (3.6) is approximately equivalent to $n>(m_{1}\wedge m_{2})\log^{1+2/\alpha}(m)$ and $n>(m_{1}\wedge m_{2})\log(m)$ respectively. Based on these remarks, we can choose $\lambda$ in the form

where $c_{*}$ equals either $\sigma\vee a$ or $\eta$ and the constant $C_{*}>0$ is large enough, and we can state the following corollary that will be further useful for minimax considerations. Define $\tau>0$ by

where $M=\max(m_{1},m_{2})$, and $m=m_{1}+m_{2}$.

Let one of the sets of conditions (i) or (ii) below be satisfied:

(ii) The assumptions of Theorem 4 with $n>4(m_{1}\wedge m_{2})\log(m)$, $\lambda$ as in (3.7), $c_{*}=\eta$, and $C_{*}=4$.

Then, with probability at least $1-3/(m_{1}+m_{2})$,

where $M=\max(m_{1},m_{2})$, and $m=m_{1}+m_{2}$. Furthermore, with the same probability,

proof. Inequalities (3.8) and (3.9) are straightforward in view of Theorems 3 and 4. To prove (3.10) it suffices to note that, for any $\kappa>0$, $0<q\leq 2$,

Inequality (3.9) guarantees that the normalized Frobenius error $(m_{1}m_{2})^{-1}\|{\hat{A}}^{\lambda}-A_{0}\|_{2}^{2}$ of the estimator ${\hat{A}}^{\lambda}$ is small whenever $n>C(m_{1}\vee m_{2})\log(m){\rm rank}(A_{0})$ with a large enough $C>0$. This quantifies the sample size $n$ necessary for successful matrix completion from noisy data.

Note that we can choose $\lambda$ not necessarily equal but also greater or equal to the right hand side of (3.7), or equivalently, $\lambda=tC_{*}c_{*}\sqrt{\frac{\log(m)}{(m_{1}\wedge m_{2})n}}$ for any $t\geq 1$. Then the resulting oracle inequalities will remain of the same form with $\tau^{2}$ multiplied by the constant $t^{2}$.

Keshavan et al. , Theorem 1.1, under a sampling scheme different from ours (sampling without replacement) and sub-gaussian errors, proposed an estimator ${\hat{A}}$ satisfying, with probability at least $1-(m_{1}\wedge m_{2})^{-3}$,

where $C>0$ is a constant, and $\beta=(m_{1}\vee m_{2})/(m_{1}\wedge m_{2})$ is the aspect ratio. A drawback is that the construction of ${\hat{A}}$ in requires the exact knowledge of ${\rm rank}(A_{0})$ (although it does not seem to require the knowledge of $a$). Furthermore, the bound (3.11) is suboptimal for ”very rectangular” matrices, i.e., when $\beta\gg 1$. Candes and Plan provide a coarser bound than (3.11), not guaranteeing a simple consistency when $n\to\infty$ whatever are $M$ and ${\rm rank}(A_{0})$ (see for more detailed comments on ).

Lower Bounds

In this section, we prove the minimax lower bounds showing that the rates attained by our estimator are optimal up to logarithmic factors. The argument here is close to where the lower bounds are obtained on the Schatten balls. However, we consider different classes that consist of matrices with uniformly (in $m_{1},m_{2},n$) bounded entries. We cannot apply directly the lower bounds of Theorem 6 in for USR matrix completion on the Schatten balls because they are achieved on matrices with entries, which are not uniformly bounded for $m_{1}m_{2}\gg n$.

We will need the following assumption, which is similar in spirit but, in general, substantially weaker than the usual Restricted Isometry condition.

(Restricted Isometry in Expectation.) For some $1\leq r\leq\min(m_{1},m_{2})$ and some $0<\mu<\infty$ that there exists a constant $\delta_{r}\in[0,1)$ such that

For the particular case of fixed $X_{i}$ (cf. Example 4 in the Introduction), Assumption 2 coincides with the matrix version of scaled restricted isometry with scaling factor $\mu$ .

Remark 1. Inspection of the proof of Theorem 5 shows that it remains valid if we replace $1-\delta_{r}$ and $1+\delta_{r}$ by arbitrary positive constants $\nu_{1}$ and $\nu_{2}$ such that $\nu_{1}\leq\nu_{2}$. We use the formulation involving $\delta_{r}$ only to ease parallels to the usual restricted isometry condition.

Fix $a>0$ and an integer $1\leq r\leq\min(m_{1},m_{2})$. Let Assumption 2 be satisfied with some $\mu>0$. Assume that $\mu^{2}r\leq n\min(m_{1},m_{2})$, and that conditionally on $X_{i}$, the variables $\xi_{i}$ are Gaussian ${\cal N}(0,\sigma^{2})$, $\sigma^{2}>0$, for $i=1,\dots,n$. Then there exist absolute constants $\beta\in(0,1)$ and $c>0$, such that

proof. Without loss of generality, assume that $M=\max(m_{1},m_{2})=m_{1}\geq m_{2}$. For some constant $0\leq\gamma\leq 1$ we define

and consider the associated set of block matrices

where $O$ denotes the $m_{1}\times(m_{2}-r\lfloor m_{2}/r\rfloor)$ zero matrix, and $\lfloor x\rfloor$ is the integer part of $x$.

is satisfied for any $\alpha>0$ if $\gamma>0$ is chosen as a sufficiently small numerical constant depending on $\alpha$. In view of (4.3) and (4.5), the result now follows by application of Theorem 2.5 in .

Fix $a>0$ and an integer $r$ such that $1\leq r\leq\min(m_{1},m_{2})$, $Mr\leq n$. Let the matrices $X_{i}$ be i.i.d. uniformly distributed on $\mathcal{X}$ and let, conditionally on $X_{i}$, the variables $\xi_{i}$ be Gaussian ${\cal N}(0,\sigma^{2})$, $\sigma^{2}>0$, for $i=1,\dots,n$. Then there exist absolute constants $\beta\in(0,1)$ and $c>0$, such that

Comparing Theorem 6 with Corollary 2(i) we see that, in the case of Gaussian errors $\xi_{i}$, the rate of convergence of our estimator $\hat{A}^{\lambda}$ given in (3.9) is optimal (up to a logarithmic factor) in a minimax sense on the class of matrices ${\cal A}(r,a)$.

Similar conclusion can be obtained for the statistical learning setting. Indeed, assume that the pairs $(X_{i},Y_{i})$ are i.i.d. realizations of a random pair $(X,Y)$ with distribution $P_{XY}$ belonging to the class

where $\Pi_{0}$ is the uniform distribution on $\mathcal{X}$, $1\leq r\leq\min(m_{1},m_{2})$ is an integer, and $\eta>0$.

Let $n,m_{1},m_{2},r$ be as in Theorem 5. Let $(X_{i},Y_{i})$ be i.i.d. realizations of a random pair $(X,Y)$ with distribution $P_{XY}$. Then there exist absolute constants $\beta\in(0,1)$ and $c>0$, such that

proof. We act as in the proof of Theorem 5 with some modifications. Assuming that $M=\max(m_{1},m_{2})=m_{1}\geq m_{2}$ and $0\leq\gamma\leq 1/2$ we define the class of matrices

Using the inequality $-\log(1+u)\leq-u+u^{2}/2$, $\forall\ u>-1$, and the fact that $1/4\leq p_{A}(X)\leq 3/4$, we find that the expression under the expectation in (4.8) is bounded by $2(p_{\bf 0}(X)-p_{A}(X))^{2}$. This implies

The remaining arguments are analogous to those in the proof of Theorem 5.

Further results and examples

A notable property of the estimator ${\hat{A}}^{\lambda}$ in matrix completion setting is that it has the same rank as the underlying matrix $A_{0}$ with probability close to 1. As a consequence we can establish a lower bound for the Frobenius error of $\hat{A}^{\lambda}$ with the rates matching up to constants the upper bounds of Corollary 2.

Let $X_{i}$ be i.i.d. uniformly distributed on $\mathcal{X}$ and let $\lambda$ satisfy the inequality $\lambda\geq 2\|{\bf M}\|_{\infty}$ (as in Theorem 1). Consider the estimator ${\hat{A}}^{\lambda^{\prime}}$ with $\lambda^{\prime}=\lambda/(1-\delta)$ for some $0<\delta<1$. Set ${\hat{r}}={\rm rank}({\hat{A}}^{\lambda^{\prime}})$. Then

If, in addition, $\displaystyle{\min_{j:\,\sigma_{j}(A_{0})\neq 0}}\sigma_{j}(A_{0})\geq\lambda^{\prime}m_{1}m_{2}$, then

proof. Note that ${\bf X}-A_{0}=m_{1}m_{2}{\bf M}$. Using standard matrix perturbation argument (cf. , page 203), we get, for all $j=1,\dots,m_{1}\wedge m_{2}$,

Since, by (3.2), $\sigma_{\hat{r}}({\bf X})>\lambda^{\prime}m_{1}m_{2}/2$, we find that $\sigma_{\hat{r}}(A_{0})>\delta\lambda^{\prime}m_{1}m_{2}/2$. This implies (5.1). Now, if $\sigma_{j}(A_{0})\geq\lambda^{\prime}m_{1}m_{2}$ we get

Let the assumptions of Corollary 2 be satisfied. Consider the estimator ${\hat{A}}^{\lambda^{\prime}}$ with

for some $0<\delta<1$. Set ${\hat{r}}={\rm rank}({\hat{A}}^{\lambda^{\prime}})$. Then ${\hat{r}}\leq{\rm rank}(A_{0})$ with probability at least $1-3/(m_{1}+m_{2})$. If, in addition,

then ${\hat{r}}\geq{\rm rank}(A_{0})$ and

We note that the lower bound for $\sigma_{j}(A_{0})$ in (5.4) is not excessively high, since $\sqrt{m_{1}m_{2}}$ is a ”typical” order of the largest singular value $\sigma_{1}(A_{0})$ for non-lacunary matrices $A_{0}$. For example, if all the entries of $A_{0}$ are equal to some constant $a$, the left hand side of (5.4) is equal to $\sigma_{1}(A_{0})=a\sqrt{m_{1}m_{2}}$.

2 Risk bounds in statistical learning

We illustrate this by an example dealing with USR matrix completion. Specifically, Theorem 4 is reformulated in the following way.

Let $X_{i}$ be i.i.d. uniformly distributed on $\mathcal{X}$. Assume that $|Y|\leq\eta$ almost surely for some constant $\eta$. For $t>0$ consider the regularization parameter $\lambda$ satisfying (3.6). Then with probability at least $1-e^{-t}$ we have

This theorem can be also viewed as a result about the approximate sparsity. We do not know whether the true underlying model is described by some matrix $A_{0},$ but we can guarantee that our estimator is not far from the best approximation provided by matrices $A$ with small rank or small nuclear norm.

Note that the results of Theorem 9 are uniform over the class of distributions

where $\Pi_{0}$ is the uniform distribution on $\mathcal{X}$, and $\eta>0$ is a constant. The corresponding lower bound is given in the next theorem.

Let $n,m_{1},m_{2},r$ be as in Theorem 5. Let $(X_{i},Y_{i})$ be i.i.d. realizations of a random pair $(X,Y)$ with distribution $P_{XY}$. Then

where $\beta\in(0,1)$ and $c>0$ are absolute constants.

Inequalities (5.7) and (5.8) imply minimax rate optimality of ${\hat{A}}^{\lambda}$ up to a logarithmic factor in the statistical learning setting.

3 Risks bounds in spectral norm

Let $X_{i}$ be i.i.d. uniformly distributed on $\mathcal{X}$. Consider the estimator $\hat{A}^{\lambda}$ defined in (3.1). If $\lambda\geq\|\mathbf{M}\|_{\infty}$, then

As a consequence of the above theorem, we can derive the optimal rate (up a to logarithmic factor) of USR matrix completion for the spectral norm when the noise is sub-exponential or in the statistical learning setting.

Let one of the sets of conditions (i) or (ii) in Corollary 2 be satisfied. Then, with probability at least $1-3/(m_{1}+m_{2})$, we have

proof. The proof of this result is immediate by combining Theorem 11 and Lemmas 1, 2 and 3.

(i) Let the conditions of Theorem 6 be satisfied. Then

where $\beta\in(0,1)$ and $c>0$ are absolute constants.

(ii) Let the conditions of Theorem 7 be satisfied. Then

where $\beta\in(0,1)$ and $c>0$ are absolute constants.

proof. Note first that, in the USR matrix completion problem, Assumption 2 is satisfied with $\delta_{r}=0$ and $\mu=\sqrt{m_{1}m_{2}}$.

We prove part (i) of the theorem. Consider the set of matrices $\mathcal{A}_{0}$ introduced in the proof of Theorem 5. For any two distinct matrices $A_{1},A_{2}$ of $\mathcal{A}_{0}$, we have

Next, (4.5) is satisfied for any $\alpha>0$ if $\gamma>0$ is chosen as a sufficiently small numerical constant depending on $\alpha$.

Combining (5.11) with (4.5) and Theorem 2.5 in gives the result.

The proof of (ii) follows the same arguments.

4 Sharp oracle inequalities for the Lasso

As we already mentioned in Example 4 and in the remark after Theorem 2, one can exploit (2.19) to derive sparsity oracle inequalities for the usual Lasso. This is detailed in the present subsection. It is noteworthy that the obtained inequalities are sharp (i.e., with leading constant $1$), which was not achieved in the previous work on the Lasso.

Note that, if $m_{1}=m_{2}=p$ and $A$ and $X_{i}$ are diagonal matrices, then the trace regression model (1.2) becomes

The estimator $\hat{A}^{\lambda}$ defined in (1.7) becomes the usual Lasso estimator

For simplicity, the result is stated only in the case of Gaussian noise.

where $C=3b\sqrt{2},b\geq 1.$ Then, with probability at least $1-\frac{1}{p^{b^{2}-1}\sqrt{\pi\log p}}$, we have

proof. Combine Theorem 2 and a standard bound on the tail of the Gaussian distribution, which assures that with probability at least $1-\frac{1}{p^{b^{2}-1}\sqrt{\pi\log p}}$ ,

We recall the Restricted Eigenvalue condition of :

Condition $\mathbf{RE}(s,c_{0})$. For some integer $s$ such that $1\leq s\leq p$, and a positive number $c_{0}$ the following condition holds:

Let the assumptions of Theorem 14 hold, and let condition $\mathbf{RE}(s,5)$ be satisfied for some $1\leq s\leq p$. Then, with probability at least $1-\frac{1}{p^{b^{2}-1}\sqrt{\pi\log p}},$

Since Condition $\mathbf{RE}(s,5)$ is satisfied, Theorem 14 yields the result.

Remark 2. Oracle inequalities (5.12) and (5.13) extend straightforwardly to the model

Control of the stochastic error

In this section, we obtain the probability inequalities for the stochastic error $\|{\bf M}\|_{\infty}$. For brevity, we will write throughout $\|\cdot\|_{\infty}=\|\cdot\|$. The following proposition is an immediate consequence of the matrix version of Bernstein’s inequality (Corollary 9.1 in ).

Then, for all $t>0,$ with probability at least $1-e^{-t}$ we have

Furthermore, it is possible to replace the $L_{\infty}$-bound $U$ on $\|Z\|$ in the above inequality by bounds on the weaker $\psi_{\alpha}$-norms of $\|Z\|$ defined by

This is an easy consequence of Proposition 2 in , which provides an analogous result for Hermitian matrices $Z$. Its extension to rectangular matrices stated in Proposition 2 is straightforward via the self-adjoint dilation, cf., for example, the proof of Corollary 9.1 in .

The next lemma gives a control of the stochastic error for USR matrix completion in the statistical learning setting.

Let $X_{i}$ be i.i.d. uniformly distributed on $\mathcal{X}$. Assume that $\max_{i=1,\dots,n}|Y_{i}|\leq\eta$ almost surely for some constant $\eta$. Then for any $t>0$ with probability at least $1-e^{-t}$ we have

Therefore, $\|Z_{i}\|\leq 2\eta$, $\sigma_{Z}\leq\eta\sigma_{X}$, and the result follows from Proposition 1.

We now consider the USR matrix completion with sub-exponential errors. Recall that in this case we assume that the pairs $(X_{i},Y_{i})$ are i.i.d. We have

We treat the terms $\Delta_{1}$ and $\Delta_{2}$ separately in the two lemmas below.

Finally, in view of Condition (3.3) and Bernstein’s inequality for sub-exponential noise, we have for any $t>0$, with probability at least $1-e^{-t}$,

Let $X_{i}$ be i.i.d. random variables uniformly distributed in $\mathcal{X}$. Then, for all $t>0,$ with probability at least $1-e^{-t}$ we have

If $\max_{i,j}|a_{0}(i,j)|\leq a$ for some $a>0$, then with the same probability

References