Flat minima generalize for low-rank matrix recovery

Introduction

Recent advances in machine learning and artificial intelligence have relied on fitting highly overparameterized models, notably deep neural networks, to observed data tan2019efficientnet ; kolesnikov2020big ; huang2019gpipe ; zhang2021understanding . In such settings, the number of parameters of the model is much greater than the number of data samples, thereby resulting in models that achieve near-zero training error. Although classical learning paradigms caution against overfitting, recent work suggests ubiquity of the “double descent” phenomenon belkin2019reconciling , wherein significant overparameterization actually improves generalization. There is an important caveat, however, that is worth emphasizing. There is typically a continuum of models with zero training error; some of these models generalize well and some do not. Reassuringly, there is evidence that basic algorithms, such as the stochastic gradient method, are implicitly biased towards finding models that do generalize; see for example soudry2018implicit ; gunasekar2018implicitNN ; jacot2018neural ; heckel2020compressive ; jastrzkebski2017three ; smith2017bayesian ; hoffer2017train ; masters2018revisiting ; neyshabur2014search ; gunasekar2018implicit ; du2018algorithmic ; mulayoff2020unique . Other seminal works bartlett1998sample ; bartlett2002rademacher ; neyshabur2017exploring seeking to explain generalization have focused on quantifying stability, capacity, and margin bounds. Understanding generalization of overparameterized models remains an active area of research, and is the topic of our work.

Do flat minimizers generalize for a broad family of overparameterized problems?

Putting generalization aside, one would hope that flat solutions are in some sense regular, occurring in a benign region where algorithms perform well. For example, numerical methods for neural network training are strongly influenced by how balanced the parameters appear. Namely, the set of interpolating neural networks contains models with consecutive weight matrices that are poorly scaled relative to each other du2018algorithmic ; shamir2018resnets . It has recently been shown that gradient descent in continuous time keeps the factors balanced ye2021global ; ma2021beyond for matrix factorization and for deep learning du2018algorithmic ; mulayoff2020unique . Despite ubiquity of the three notions discussed so far—small norm, flatness, and balancedness—the exact relationship between them is unclear. Thus our secondary question is as follow:

Are flat minimizers nearly norm-minimal and nearly balanced for a broad family of overparameterized problems?

We answer both questions in the setting of low-rank matrix factorization—a prototypical problem class often used to gain insight into more general deep learning models li2018algorithmic ; du2018algorithmic ; ye2021global . Setting the stage, consider a ground truth matrix $M_{\natural}\in{}^{d_{1}\times d_{2}}$ with rank $r_{\natural}$. The goal is to recover $M_{\natural}$ from the observed measurements $b=\mathcal{A}(M_{\natural})$ under a linear measurement map $\mathcal{A}\colon{}^{d_{1}\times d_{2}}\rightarrow{}^{m}$. A common approach to this task is through the nonconvex optimization problem:

The set of minimizers of $f$, which we denote by $\mathcal{S}$, consists of all solutions to the equation $\mathcal{A}(LR^{\top})=b$. In order to model overparameterization, we focus on the rank-overparameterized setting $k\geq r_{\natural}$; indeed $k$ can be arbitrarily large. The three notions discussed so for can be formally defined for pairs $(L,R)\in\mathcal{S}$ as follows.

$(L,R)$ is norm-minimal if it minimizes over $\mathcal{S}$ the square Frobenius norm \mathopen{}\mathclose{{}\left\|L}\right\|_{\mbox{\tiny{F}}}^{2}+\mathopen{}\mathclose{{}\left\|R}\right\|_{\mbox{\tiny{F}}}^{2}.

$(L,R)$ is balanced if it satisfies $L^{\top}L=R^{\top}R$.

$(L,R)$ is flat if it minimizes over $\mathcal{S}$ the “scaled trace” of the Hessian, ${\textrm{str}}(D^{2}f(L,R))$.

Thus being norm-minimal means that $(L,R)$ is the closest pair from $\mathcal{S}$ to the origin in Frobenius norm. Being balanced amounts to requiring $L$ and $R$ to have the same singular values and right-singular vectors. Flat solutions are defined in terms of the “scaled trace” of the bilinear form $D^{2}f(L,R)$ defined as

For various statistical models, flat solutions of (1) exactly recover $M_{\natural}$. Moreover, flat solutions have nearly minimal norm and are almost balanced.

The exact recovery guarantee may be striking at first because flat solutions are distinct from minimal norm solutions, and thus do not correspond to nuclear norm minimization over $\mathcal{S}$. Yet, our main result shows that flat solutions do exactly recover the ground truth $M_{\natural}$ under standard statistical assumptions. The precise statistical models for which this is the case are matrix and bilinear sensing, robust PCA (or PCA with outliers), covariance matrix estimation, and single hidden layer neural networks with quadratic activation functions. Moreover, we prove weak recovery for the matrix completion problem, though our numerical experiments suggest that exact recovery holds here as well.

2 Main results and outline of the paper

We next outline our main results and the arguments that underpin them. We begin in Section 2 with the idealized “population level” setting where $\mathcal{A}$ is the identity map. In this case, we show that there is no distinction between flat, norm-minimal, and balanced solutions. As soon as $\mathcal{A}$ deviates from the identity, however, all three notions become distinct in general.

We will show in Theorem 3.2 that flat solutions can be identified with minimizers of the problem

It is worthwhile to note that without the $D_{1}$ and $D_{2}$ matrices and without the rank constraint, the problem (4) is classically known to characterize norm-minimal solutions and is known as nuclear norm minimization. Herein, we already see the distinction between the two solution concepts. A natural convex relaxation for flat solutions simply drops the rank constraint:

Summarizing, verifying that flat solutions exactly recover $M_{\natural}$ is reduced to showing that $M_{\natural}$ (which has rank $r_{\natural}$) is the unique solution of the convex problem (5).

Suppose that $\mathcal{A}$ is generated according to a Gaussian matrix sensing or bilinear sensing model. Then as long as we are in the regime $m\gtrsim r_{\natural}d_{\max}$ and $d_{\min}\gtrsim\log m$, with high probability, any flat solution $(L_{f},R_{f})$ satisfies $L_{f}R_{f}^{\top}=M_{\natural},$ and is nearly norm-minimal and nearly balanced.

Note that our requirement on the sample size $m\gtrsim r_{\natural}d_{\max}$ matches the known regime for exact recovery with nuclear norm minimization candes2011tight ; cai2015rop . Since we are interested in the high dimensional regime, the extra condition $d_{\min}\gtrsim\log(m)$ can be assumed without harm. Appendix A presents a generalization of this result when the measurements $b$ are corrupted by noise.

Suppose that $\mathcal{A}$ is generated from the Bernoulli matrix completion model with success probability $p>0$ and let $\mu>0$ be the incoherence parameter of $M_{\natural}$.See (34) for the definition of the incoherence parameter $\mu$. Then provided we are in the regime $p\gtrsim\frac{1}{\gamma}\sqrt{\frac{r_{\natural}\log(d_{\max})}{d_{\min}}}$, with high probability, any flat solution $(L_{f},R_{f})$ satisfies \mathopen{}\mathclose{{}\left\|L_{f}R_{f}^{\top}-M_{\natural}}\right\|_{*}\leq\gamma\mathopen{}\mathclose{{}\left\|M_{\natural}}\right\|_{*} and is nearly norm-minimal and nearly balanced.

Hence according to this theorem, in order to conclude that flat solutions achieve a constant relative error, we must be in the regime $p\gtrsim\sqrt{\frac{r_{\natural}\log d_{\max}}{d_{\min}}}$. This is a stronger requirement than is needed for exact recovery of the ground truth matrix by nuclear norm minimization chen2015incoherence , which is $p\gtrsim\mu r_{\natural}\log(\mu r_{\natural})\frac{\log(d_{\max})}{d_{\min}}$. We stress, however, that our numerical results suggest that flat solutions exactly recovery the ground truth matrix in this wider parameter regime.

We next focus on the problem of Robust Principal Component Analysis (PCA) in Section 6. Though this problem is not of the form (1), we will see that flat solutions (appropriately defined) exactly recover the ground truth under reasonable assumptions. Specifically, following candes2011robust ; chandrasekaran2011rank , the robust PCA problem asks to find a low-rank matrix $M_{\natural}\in{}^{d_{1}\times d_{2}}$ that has been corrupted by sparse noise $S_{\natural}$. Thus, we observe a matrix $Y\in{}^{d_{1}\times d_{2}}$ of the form

where the matrix $S_{\natural}$ is assumed to have at most $l_{\natural}$ nonzero entries in any column and in any row. A popular formulation of the problem (see (ha2020equivalence, , Eqn. (19)), (ge2017no, , Eqn. (6))) takes the form

Let $\mu$ be the strong incoherence parameter of $M_{\natural}$. See (48) for the definition of the strong incoherence parameter $\mu$. Then, in the regime $l_{\natural}\lesssim\frac{d_{\min}}{\mu r_{\natural}}$, any flat minimizer $(L_{f},R_{f})$ satisfies $L_{f}R_{f}^{\top}=M_{\natural}$.

Section 7 analyzes the last problem class of the paper, motivated by the problems of covariance matrix estimation and training of shallow neural networks. Setting the stage, consider a ground truth matrix $M_{\natural}$ satisfying

where $x_{1},\ldots,x_{m}\overset{\text{iid}}{\sim}N(0,I_{d})$. Note that in the special case $r_{2}=0$, this problem reduces to covariance matrix estimation chen2015exact and further reduces to phase retrieval when $r_{1}=1$ candes2013phaselift . The added generality allows to also model shallow neural networks with quadratic activation functions; see details below. A natural optimization formulation of the problem takes the form

where the sensing matrices are $A_{i}=x_{i}x_{i}^{\top}$ and $k_{i}\geq r_{i}$ for $i=1,2$. Since ${\textrm{str}}(D^{2}f(U_{1},U_{2})))=d\mathop{\rm tr}(D^{2}f(U_{1},U_{2}))$, we declare a minimizer $(U_{1,f},U_{2,f})$ to be flat if it has minimal trace $\mathop{\rm tr}(D^{2}f(U_{1},U_{2}))$ among all minimizers of (9). We prove the following.

In the regime $m\gtrsim C(r_{1}+r_{2})d$ and $d\gtrsim C\log m$, with high probability, any flat solution $(U_{f,1},U_{f,2})$ of (9) satisfies $U_{f,1}U_{f,1}^{\top}-U_{f,2}U_{f,2}^{\top}=M_{\natural}$.

with hidden weights $U\in{}^{d\times k}$ and output layer weights $u=(\mathbf{1}_{k_{1}},-\mathbf{1}_{k_{2}})$, where $k_{1}\geq r_{1}$, and $k_{2}\geq r_{2}$. It is straightforward to see that by partitioning the matrix $U=[U_{1},U_{2}]$, this problem is exactly equivalent to recovering the matrix $M_{\natural}=U_{\natural}\operatorname{diag}(v)U_{\natural}^{\top}$ from the observations (8).

Section 8 numerically validates our theoretical results. Section 9 summarizes our findings and speculates about the role of depth on generalization properties of flat solutions.

Norm-minimal, flat, and balanced solutions with an identity measurement map

In this section, we focus on the idealized objective (1) where the measurement map $\mathcal{A}$ is the identity:

We begin with the following lemma that provides a convenient expression for ${\textrm{str}}(D^{2}f(L,R))$.

The second-order derivative of the function $f$ at any $(L,R)\in\mathcal{S}$ is the quadratic form:

A straightforward computation shows for any pair $(L,R)$ the expression

We are now ready to prove the claimed equivalence between the three properties.

Norm-minimal, flat, and balanced solutions of (11) all coincide.

First, the equivalence of flat and norm-minimal solutions follows directly from the expression (13) in Lemma 2.1. Next, we prove the equivalence between minimal norm and balanced solutions. Suppose $(L,R)\in S$ is balanced. The equality $L^{\top}L=R^{\top}R$ implies that $L$ and $R$ have the same nonzero singular values and the same set of right singular vectors. Therefore, we may form compact singular value decompositions $L=U_{1}\Sigma V^{\top}$ and $R=U_{2}\Sigma V^{\top}$. Since equality $LR^{\top}=M_{\natural}$ holds, we see that $U_{1}\Sigma^{2}U_{2}^{\top}=M_{\natural}$. Hence, the nuclear norm of $M_{\natural}$ is simply \mathopen{}\mathclose{{}\left\|M_{\natural}}\right\|_{*}=\mathop{\rm tr}(\Sigma^{2}). Noting the equality \frac{1}{2}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\|L}\right\|_{\mbox{\tiny{F}}}^{2}+\mathopen{}\mathclose{{}\left\|R}\right\|_{\mbox{\tiny{F}}}^{2}}\right)=\mathop{\rm tr}(\Sigma^{2}) along with (10), we deduce that $(L,R)$ is a minimal norm solution, as claimed. Conversely, suppose that $(L,R)$ is a minimal norm solution. Define the function

over the open set of $k\times k$ invertible matrices $B$. Clearly $B=I_{k}$ is a local minimizer of $\varphi$ and therefore $\nabla\varphi(I_{k})$ must be the zero matrix. A quick computation yields the expression $\nabla\varphi(I_{k})=L^{\top}L-R^{\top}R,$ and therefore $(L,R)$ is balanced, as claimed. ∎

Convex relaxation and regularity of flat solutions

In this section, we begin investigating flat minimizers of the problem (1) with general linear measurement maps $\mathcal{A}$. It will be convenient to write the linear map $\mathcal{A}(X)$ in coordinates as

The section presents two main results: Theorems 3.2 and 3.3. The former presents a convex relaxation for verifying that a solution is flat, while the latter shows that flat solutions are nearly balanced and nearly norm-minimal, whenever the matrices $D_{1}$ and $D_{2}$ are well-conditioned.

Flat solutions are by definition minimizers of the highly nonconvex problem $\min_{(L,R)\in\mathcal{S}}{\textrm{str}}(D^{2}f(L,R)).$ The main result of this section is to present an appealing convex relaxation of this problem. We begin with a convenient expression for the scaled trace ${\textrm{str}}(D^{2}f(L,R))$. Namely, recall that Lemma 2.1 showed the equality {\textrm{str}}(D^{2}f(L,R))=2\mathopen{}\mathclose{{}\left\|L}\right\|_{\mbox{\tiny{F}}}^{2}+2\mathopen{}\mathclose{{}\left\|R}\right\|_{\mbox{\tiny{F}}}^{2} in the simplified setting $\mathcal{A}=\mathcal{I}$. Lemma 3.1 provides an analogous statement for general maps $\mathcal{A}$ up to rescaling the factors by $D_{1}$ and $D_{2}$.

The second-order derivative of the function $f$ at any $(L,R)\in\mathcal{S}$ is the quadratic form:

Moreover, the scaled trace can be written as

An elementary computation yields for any $(L,R)$ the expression

Noting that for any $(L,R)\in\mathcal{S}$ the first term on the right is zero yields the claimed expression (15). Next, we verify (16) by a direct calculation. To this end, the definition of the scaled trace (2) yields the expression

Let us analyze the second term on the right. Letting $A_{l,i}$ denote the $i$’th column of $A_{l}$, we compute

A similar argument shows \mathopen{}\mathclose{{}\left\|D_{2}R}\right\|_{\mbox{\tiny{F}}}^{2}=\frac{1}{md_{1}}\sum_{i=1}^{d_{1}}\sum_{j=1}^{k}\mathopen{}\mathclose{{}\left\|\mathcal{A}(e_{i}e_{j}^{\top}R^{\top})}\right\|_{2}^{2}, completing the proof. ∎

In particular, Lemma 3.1 implies that flat solutions are exactly the minimizers of the problem

In turn, it follows directly from (10) that so long as $D_{1}$, $D_{2}$ are invertible, the problem (19) is equivalent to minimizing the nuclear norm over rank constrained matrices:

Therefore, a natural convex relaxation for finding the flattest solution drops the rank constraint:

The following theorem summarizes these observations.

Suppose the matrices $D_{1}$ and $D_{2}$ are invertible. Then the problems (19) are (20) are equivalent in the following sense. Let $l=\min(k,d_{\min})$.

the optimal values of (19) and (20) are equal,

if $L,R$ solves (19), then $X=D_{1}LR^{\top}D_{2}$ is a minimizer of (20).

if a solution $X$ of (20) has a singular value decomposition $X=U\Sigma V^{\top}$ for some diagonal matrix $\Sigma\in{}^{l\times l}$ with nonnegative entries, then the matrices $L=D_{1}^{-1}U\sqrt{\Sigma}$ and $R=D_{2}^{-1}V\sqrt{\Sigma}$ are minimizers of (19) when $l\geq k$, and the matrices $L=[D_{1}^{-1}U\sqrt{\Sigma},0_{d_{1},(k-l)}]$ and $R=[D_{2}^{-1}V\sqrt{\Sigma},0_{d_{2},(k-l)}]$ are minimizers of (19) when $l<k$.

Moreover, if $X=D_{1}M_{\natural}D_{2}$ is the unique minimizer of the problem (21), then any flat solution $(L,R)$ satisfies $LR^{\top}=M_{\natural}$.

The three claims follow directly from making a variable substitution $L^{\prime}=D_{1}L$ and $R^{\prime}=D_{2}R$ and using (10). The “moreover” part follows from (21) being a convex relaxation of (20). ∎

Section 4 will verify that the convex relaxation (21) indeed recovers $M_{\natural}$ under restricted isometry properties on the measurement map $\mathcal{A}$, and therefore flat solutions exactly recover $M_{\natural}$.

2 Regularity of flat solutions

In this section, we show that the condition numbers of the rescaling matrices $D_{1}$ and $D_{2}$ determine balancedness and norm minimality of flat solutions. The main result is the following theorem.

Suppose that there exist constants $\alpha_{1},\alpha_{2}>0$ satisfying $\alpha_{1}I\preceq D_{i}\preceq\alpha_{2}I$ for each $i\in\{1,2\}$. Define the constant $\kappa:=\frac{\alpha_{2}}{\alpha_{1}}$. Then any flat solution $(L_{f},R_{f})$ of (1) satisfies the following properties.

Norm-minimal: the pair $(L_{f},R_{f})$ is approximately norm-minimal:

Balanced: The pair $(L_{f},R_{f})$ is approximately balanced:

The proof of Theorem 3.3 relies on the following simple linear algebraic lemma.

Lemma 2.2 implies that the pair $(Q_{1}L,Q_{2}R)$ is balanced, meaning $L^{\top}Q_{1}^{2}L=R^{\top}Q_{2}^{2}R$. Hence, we may decompose $L^{\top}L-R^{\top}R$ in the following way:

We bound the first term on the right as follows,

Here, $(a)$ and $(b)$ follow, respectively, from the basic inequalities: \mathopen{}\mathclose{{}\left\|FG}\right\|_{*}\leq\mathopen{}\mathclose{{}\left\|F}\right\|_{\mbox{\tiny{F}}}\mathopen{}\mathclose{{}\left\|G}\right\|_{\mbox{\tiny{F}}} and \|FG\|_{F}\leq\mathopen{}\mathclose{{}\left\|F}\right\|_{\mbox{\tiny{{op}}}}\mathopen{}\mathclose{{}\left\|G}\right\|_{\mbox{\tiny{F}}}, which hold for all matrices $F$ and $G$ with compatible dimensions. A similar argument yields the inequality

The claimed estimate (25) follows immediately. ∎

We first prove inequality (22). To this end, for any $(L,R)\in\mathcal{S}$, we successively estimate:

where the second inequality follows from the characterization (19) of flat solutions. Taking the infimum over pairs $(L,R)\in\mathcal{S}$ completes the proof of (22).

We next verify (23). To this end, define the matrix $X:=D_{1}L_{f}R_{f}^{\top}D_{2}$. Then clearly $(L_{f},R_{f})$ is a minimizer of the problem

Lemma 3.4 therefore guarantees the estimate

The already established estimate (22) ensures

In particular, minimizing the right hand-side over $L,R$ satisfying $M_{\natural}=LR^{\top}$ yields an upper bound of 2\kappa^{2}\mathopen{}\mathclose{{}\left\|M_{\natural}}\right\|_{*}. The proof is complete. ∎

Flat minima under RIP conditions: matrix and bilinear sensing

We say that $\mathcal{A}$ is a Gaussian ensemble if the entries of $A_{i}$ are i.i.d standard normal random variables $N(0,1)$.

We say that $\mathcal{A}$ is a Gaussian bilinear ensemble if the matrices $A_{i}$ take the form $A_{i}=a_{i}b_{i}^{\top}$ where the entries of $a_{i}$ and $b_{i}$ are i.i.d. standard normal random variables $N(0,1)$

The main results of the section is the following theorem, stated here informally.

$\mathcal{A}$ is a Gaussian ensemble and $m\gtrsim r_{\natural}d_{\max}$,

$\mathcal{A}$ is a Gaussian bilinear ensemble, $m\gtrsim r_{\natural}d_{\max}$, and $d_{\min}\gtrsim\log m$.

Then with high probability, any flat solution $(L_{f},R_{f})$ of (1) satisfies $L_{f}R_{f}^{\top}=M_{\natural},$ and is nearly norm-minimal and nearly balanced:

We begin by formally defining the restricted isometry property of a measurement map $\mathcal{A}(\cdot)$.

holds for all matrices $X\in{}^{d_{1}\times d_{2}}$ with rank at most $r$.

Our goal is to show that under RIP conditions, with reasonable parameters, flat solutions exactly recover the ground truth $M_{\natural}$. We will need the following lemma, whose proof is immediate from definitions.

The following lemma will be our main technical tool; it establishes that if $\mathcal{A}(\cdot)$ satisfies RIP, then so does the perturbed map $\mathcal{B}(\cdot)=\mathcal{A}(Q_{1}^{-1}\cdot Q_{2}^{-1})$, provided that the condition numbers of the positive definite matrices $Q_{1}$ and $Q_{2}$ are sufficiently close to one.

Consider two positive definite matrices $Q_{1},Q_{2}$ and constants $\alpha_{1},\alpha_{2}>0$ satisfying $\alpha_{1}I\preceq Q_{i}\preceq\alpha_{2}I$ for each $i\in\{1,2\}$. Define $\kappa=\alpha_{2}/\alpha_{1}$ and let $\mathcal{A}(\cdot)$ be a linear map satisfying one of the following conditions.

Then $Q_{1}M_{\natural}Q_{2}$ is the unique solution of the following convex program

In the proof of Lemma 3.1 (equation (18)), we actually showed the expression:

A similar argument shows that $D_{2}$ satisfies the analogous inequality with $v\in{}^{d_{2}}$. ∎

Let $\mathcal{A}$ be a Gaussian bilinear ensemble. Then there exist constant $c_{1},c_{2},c_{3},c_{4}>0$ such that for any $\delta\in(0,1)$ as long as we are in the regime $m\geq\frac{c_{3}d_{\max}}{\delta^{2}}$ and $\log(m)\leq c_{4}\delta^{2}d_{\min}$, the estimate holds:

First observe $A_{i}A_{i}^{\top}=\|b_{i}\|^{2}_{2}a_{i}a_{i}^{\top}$ for each index $i$. Bernstein’s inequality (vershynin2018high, , Theorem 2.8.3) implies

Taking a union bound, we can therefore be sure that with probability at least $1-m\exp(-c_{1}d_{2}\delta^{2})$ the estimate

holds simultaneously for all $i=1,\ldots,m$. In this event, we estimate

Therefore, after summing for $i=1,\ldots,m$ we deduce

Concentration of covariance matrices (vershynin2018high, , Exercise 4.7.3) in turn implies that the estimate

holds with probability at least $1-2\exp(-u)$. Taking a union bound, we therefore deduce

holds with probability at least $1-m\exp(-c_{1}d_{2}\delta^{2})-2\exp(-u)$. Setting $u=d_{1}$, we see that there is a constant $c_{3}$ such that as long as $m\geq c_{3}\frac{\max\{d_{1},d_{2}\}}{\delta^{2}}$, we have

with probability at least $1-m\exp(-c_{1}d_{2}\delta^{2})-2\exp(-d_{1})$. The result follows. ∎

The following are the two main results of the section.

Suppose that $\mathcal{A}$ is a Gaussian ensemble. Then there exists a constant $c_{0}$ such that the following hold for any $\delta\in(0,c_{0})$. There exist constants $c,C>0$ depending only on $\delta$ such that in the regime $m\geq cr_{\natural}(d_{1}+d_{2})$, with probability at least $1-\exp(-Cm)$, any flat solution $(L_{f},R_{f})$ of (1) satisfies $L_{f}R_{f}^{\top}=M_{\natural}$ and is automatically nearly norm-minimal and nearly balanced:

Suppose that $\mathcal{A}$ is a Gaussian bilinear ensemble. Then for any $\delta\in(0,1)$ there exist numerical constants $c,C,c_{1},c_{2},c_{3},c_{4}>0$ depending only on $\delta$ such that in the regime $m\geq cr_{\natural}(d_{1}+d_{2})$ and $\log(m)\leq c_{4}d_{\min}$, with probability at least $1-c_{3}\exp(-Cd_{\min})$ any flat solution $(L_{f},R_{f})$ of (1) satisfies $L_{f}R_{f}^{\top}=M_{\natural}$ and is automatically nearly norm-minimal and nearly balanced:

Therefore in this regime, we may upper bound the condition number $\kappa$ of $D_{1}$ and $D_{2}$ by $\frac{1+\delta}{1-\delta}$. In light of Lemma 4.7, in order to ensure exact recovery, it remains to simply choose a large enough $l$ such that the inequality $\frac{\delta_{2}}{\delta_{1}}\cdot(\frac{1+\delta}{1-\delta})^{2}\leq\sqrt{l}$ holds (recall $\delta_{1},\delta_{2}$ are numerical constants). An application of Lemma 4.7 and Theorem 3.3 completes the proof. ∎

Appendix A generalizes the material in this section to the noisy observation setting, wherein $b=\mathcal{A}(M_{\natural})+e$ with $e\sim N(0,\sigma^{2}I)$ for some $\sigma^{2}>0$.

Matrix completion and approximate recovery

In this section, we focus on the matrix completion problem recht2011simpler ; candes2009exact . This is an instance of (1) where the linear measurement map $\mathcal{A}$ is generated as follows. For each $i\in[d_{1}]$ and $j\in[d_{2}]$, let $\xi_{ij}$ be independent Bernoulli random variables with success probability $p$. The linear map $\mathcal{A}\colon{}^{d_{1}\times d_{2}}\to{}^{d_{1}\times d_{2}}$ is then defined by the relation

The difficulty of recovering the matrix $M_{\natural}$ is typically measured by an incoherence parameter, which we now define. Given a singular value decomposition $M_{\natural}=U_{\natural}\Sigma_{\natural}V_{\natural}^{\top}$ with $\Sigma_{\natural}\in{}^{r_{\natural}\times r_{\natural}}$, the incoherence parameter is the smallest $\mu>0$ satisfying

Suppose that $\mathcal{A}$ is a random sampling map described in (33). Then there exist numerical constants $c,C>0$ such that the following is true. Given any $\gamma\in(0,1)$, provided we are in the regime

with probability at least $1-cd_{\min}^{-5}$, any flat solution $(L_{f},R_{f})$ satisfies

Hence according to Theorem 5.1, in order to conclude that flat solutions achieve a constant relative error, we must be in the regime $p\gtrsim\sqrt{\frac{r_{\natural}\log d_{\max}}{d_{\min}}}$. This is a stronger requirement than is needed for exact recovery of the ground truth matrix chen2015incoherence , which is $p\gtrsim\mu r_{\natural}\log(\mu r_{\natural})\frac{\log(d_{\max})}{d_{\min}}$. Our numerical experiments, however, suggest that flat solutions exactly recover the ground truth.

As the first step towards proving Theorem 5.1, we estimate the condition numbers of $D_{1}$, $D_{2}$.

For any given $\delta\in(0,1)$ and $c\geq 1$, as long as p\geq\frac{(1+c)\log\mathopen{}\mathclose{{}\left(d_{\max}}\right)}{2\delta^{2}d_{\min}}, with probability at least $1-4d^{-c}_{{\min}}$, the estimate

Let $m=d_{1}d_{2}$ and set the sensing matrices $A_{ij}=\xi_{ij}e_{i}e_{j}^{\top}$ for all pairs $i\in[d_{1}]$ and $j\in[d_{2}]$. Therefore the equality $A_{ij}A_{ij}^{\top}=\xi_{ij}e_{i}e_{i}^{\top}$ holds, and we can write

Bernstein’s inequality (vershynin2018high, , Theorem 2.8.1) implies for each index $i\in[d_{2}]$ the estimate

Taking the union bound over $i\in[d_{1}]$ we deduce that the condition

Using the same argument for $D_{2}$ and taking a union bound completes the proof. ∎

Next, we will show that flat solutions are almost optimal for the standard convex relaxation of the matrix completion problem:

Suppose that $M_{\natural}$ is a solution of the problem (39) and suppose that the condition numbers of $D_{1}$ and $D_{2}$ are upper bounded by some constant $\kappa>0$. Then any flat solution $(L_{f},R_{f})$ of (1) is nearly optimal for the convex relaxation (39) in the sense that:

where the first and last inequalities follow from (10) and the second inequality follows from Theorem 3.3. We therefore deduce \mathopen{}\mathclose{{}\left\|L_{f}R_{f}^{\top}}\right\|_{*}-\mathopen{}\mathclose{{}\left\|M_{\natural}}\right\|_{*}\leq(\kappa^{2}-1)\mathopen{}\mathclose{{}\left\|M_{\natural}}\right\|_{*}, as claimed. ∎

It remains to translate the suboptimality gap (40) into an estimate on the distance \mathopen{}\mathclose{{}\left\|L_{f}R_{f}^{\top}-M_{\natural}}\right\|_{*}. This is the content of the following lemma.

Suppose the linear map $\mathcal{A}$ is generated according to the matrix completion model. Then there exist constants $c,c_{1},C>0$ such that in the regime $p\geq\frac{C\mu r_{\natural}\log(\mu r_{\natural})\log(d_{\max})}{d_{\min}}$, with probability at least $1-c_{1}d_{\min}^{-5}$, any feasible matrix $X$ of the problem (39) satisfies the inequality:

Set $P_{\mathcal{T}^{\perp}}(Z):=Z-P_{\mathcal{T}}(Z)$. Observe that we may bound \mathopen{}\mathclose{{}\left\|R}\right\|_{*} as follows:

where the step $(a)$ is due to the fact that $P_{\mathcal{T}}(R)$ has rank no more than $3r_{\natural}$. We now bound \mathopen{}\mathclose{{}\left\|P_{\mathcal{T}^{\perp}}(R)}\right\|_{*} and \mathopen{}\mathclose{{}\left\|P_{\mathcal{T}}(R)}\right\|_{\mbox{\tiny{F}}} separately. As verified in (ding2020leave, , Section 6), the premise in (chen2015incoherence, , Proposition 2) is satisfied with probability at least $1-c_{3}d_{1}^{-5}-c_{3}d_{2}^{-5}$ for some universal $c_{3}>0$ under the condition $p\geq\frac{C\mu r_{\natural}\log(\mu r_{\natural})\log(d_{\max})}{d_{\min}}$. Hence, the result (chen2015incoherence, , Proposition 2 and its proof)Specifically, the first displayed equation above (chen2015incoherence, , Lemma 5) shows that with probability at least $1-c_{3}d_{1}^{-5}-c_{3}d_{2}^{-5}$, there holds the inequality

Moreover, the premise in (chen2015incoherence, , Lemma 5) is satisfied with probability at least $1-c_{4}d_{1}^{-5}-c_{4}d_{2}^{-5}$ for some universal constant $c_{4}>0$ as verified in (candes2009exact, , Lemma 4.1) or in (chen2013low, , Lemma 11). Hence, (chen2015incoherence, , Lemma 5 and its proof)In the displayed equation in the statement of the lemma, one can simply replace $n^{5}$ by $\frac{1}{\sqrt{p}}$ and set $Z=R$. shows that with probability at least $1-c_{4}d_{1}^{-5}-c_{4}d_{2}^{-5}$, the inequality

holds. Combining (43),(44), and (45), yields the desired inequality (41). ∎

Putting all the lemmas together, we can now prove Theorem 5.1.

Lemma 5.4 ensures that in the regime $p\geq C\frac{\mu r_{\natural}\log(\mu r_{\natural})\log(d_{\max})}{d_{\min}}$, with probability at least $1-c_{1}d_{\min}^{-5}$, the estimate

holds for all $X$ satisfying $\mathcal{A}(X)=\mathcal{A}(M_{\natural})$. In this event, $M_{\natural}$ is clearly a minimizer of (39). Lemma 5.3 therefore ensures that the matrix $X:=L_{f}R_{f}^{\top}$ satisfies

where $\kappa$ is an upper bound on the condition numbers of $D_{1}$ and $D_{2}$. Lemma 5.2 in turn ensures that for any $\delta\in(0,1)$, in the regime p\geq\frac{3\log\mathopen{}\mathclose{{}\left(d_{\max}}\right)}{\delta^{2}d_{\min}}, with probability at least $1-4d_{\min}^{-5}$, the upper bound $\kappa\leq\sqrt{\frac{1+\delta}{1-\delta}}$ is valid. Algebraic manipulations therefore yield, within these events, the estimate:

for a some numerical constant $C>0$. To summarize, there exist numerical constants $c_{1},c_{2},C>0$ such that the following is true. Given any $\delta\in(0,1)$, provided we are in the regime

with probability at least $1-c_{2}d_{\min}^{-5}$, any flat solution $(L_{f},R_{f})$ satisfies (46). Let us now try to set

This choice is consistent with the requirement (47) as long as (35) holds. With this choice of $\delta$, the estimate (46) becomes \mathopen{}\mathclose{{}\left\|L_{f}R_{f}^{\top}-M_{\natural}}\right\|_{*}\leq\gamma\mathopen{}\mathclose{{}\left\|M_{\natural}}\right\|_{*}, as claimed. ∎

Robust principal component analysis (PCA)

In this section, we focus on problem of principal component analysis (PCA) with outliers, also known as “robust PCA”, following the approach in candes2011robust ; chandrasekaran2011rank . Though this problem is not of the form (1), we will see that flat solutions (appropriately defined) exactly recover the ground truth under reasonable assumptions. The robust PCA problem asks to find a matrix $M_{\natural}\in{}^{d_{1}\times d_{2}}$ that has been corrupted by sparse noise $S_{\natural}$. More precisely, we observe a matrix $Y\in{}^{d_{1}\times d_{2}}$ of the form

The matrix $S_{\natural}$ is assumed to have at most $l_{\natural}$ many nonzero entries in any column and in any row, and $M_{\natural}$ has rank $r_{\natural}$. Moreover, following existing literature we assume that the matrix $M_{\natural}$ is strongly incoherent with parameter $\mu$. That is, given a singular value decomposition $M_{\natural}=U_{\natural}\Sigma_{\natural}V_{\natural}^{\top}$ with $\Sigma_{\natural}\in{}^{r_{\natural}\times r_{\natural}}$, we let $\mu>0$ denote the smallest constant satisfying

where \mathopen{}\mathclose{{}\left\|\cdot}\right\|_{\infty} denotes the entrywise sup-norm.

One common approach for recovering $M_{\natural}$ is to solve the problem:

Observe that we may express the problem (51) more compactly as

The following is the main result of the section.

There is a numerical constant $c>0$ such that in the regime $l_{\natural}\leq\frac{d_{\min}}{\mu r_{\natural}}$, any flat minimizer $(L_{f},R_{f})$ of (50) satisfies $L_{f}R_{f}^{\top}=M_{\natural}$.

Let $(L_{0},R_{0})\in\mathcal{S}$ be a solution of (50). Since $f(L_{0},R_{0})=0$, the equality $f_{L_{0},R_{0}}(L_{0},R_{0})=0$ holds. In particular, we may write $f_{L_{0},R_{0}}(L,R)$ as

where we define $W_{\natural}:=Y-P_{\Omega}(Y-L_{0}R_{0}^{\top})$. Therefore appealing to Lemma 2.1, we may write the scaled trace as

Thus any flat solution $(L_{f},R_{f})$ of (50) solves the problem:

Equivalently, the characterization (10) implies that the matrix $X_{f}=L_{f}R_{f}^{\top}$ solves the problem

On the other hand, the result (chen2013low, , Theorem 3)The result (chen2013low, , Theorem 3) actually shows that $(M_{\natural},S_{\natural})$ uniquely solves minimize \displaystyle\quad\mathopen{}\mathclose{{}\left\|X}\right\|_{*}+\lambda\mathopen{}\mathclose{{}\left\|S}\right\|_{1,1} (55) subject to $\displaystyle\quad Y=X+S,$ for some $\lambda>0$. Now for any solution $X_{1}$ to (56), the pair $(X_{1},Y-X_{1})$ is feasible for (55) and satisfies \mathopen{}\mathclose{{}\left\|X_{1}}\right\|_{*}+\lambda\mathopen{}\mathclose{{}\left\|Y-X_{1}}\right\|_{1,1}\leq\mathopen{}\mathclose{{}\left\|M_{\natural}}\right\|_{*}+\lambda\mathopen{}\mathclose{{}\left\|S_{\natural}}\right\|_{1,1}, by definition of $\Omega$. Hence by the uniqueness of (55), we know $X_{1}=M_{\natural}$. shows that $M_{\natural}$ is the unique minimizer of the convex relaxation

Hence, we know $M_{\natural}$ also uniquely solves (54) and we conclude $M_{\natural}=X_{f}=L_{f}R_{f}^{\top}$, as claimed. ∎

Neural networks with quadratic activations and covariance matrix estimation

In this section, we investigate flat minimizers of a one hidden layer neural network, considered in the work soltanolkotabi2018theoretical ; li2018algorithmic for the purpose of analyzing the energy landscape around saddle points. Though this problem is not in the form (1), we will see that flat minimizers (naturally defined) exactly recover the ground truth under reasonable statistical assumptions. As a special case, we will obtain guarantees for flat minimizers of the overparameterized covariance matrix estimation problem.

We aim to fit the data with an overparameterized neural network with a single hidden layer with weights $U\in{}^{d\times k}$ and an output layer with weights $u=(\mathbf{1}_{k_{1}},-\mathbf{1}_{k_{2}})$, where $k_{1}\geq r_{1}$, and $k_{2}\geq r_{2}$. The prediction $\hat{y}$ of the neural network on input $x$ is thus given by

Thus the overparameterized problem we aim to solve is

with high probability over the training set $\{(x_{i},y_{i})\}_{i=1,\ldots,n}$ flat solutions $U_{f}$

Indeed, we will prove a stronger result by relating the problem (58) to low-rank matrix factorization. To see this, we can write $\hat{y}(U,x)-y(U_{\natural},x)$ as:

Here, we write $U=[U_{1},U_{2}]$ with $U_{1}\in{}^{d\times k_{1}}$ and $U_{2}\in{}^{d\times k_{2}}$. Note that the matrix $M_{\natural}$ is symmetric. Using (59), we may rewrite the objective of (58) as

where the linear map $\mathcal{A}$ is defined as $\mathcal{A}:{}^{d\times d}\rightarrow{}^{m}$ with $[\mathcal{A}(Z)]_{i}=\langle Z,x_{i}x_{i}^{\top}\rangle$ for any $Z\in{}^{d\times d}$. In particular, from the second equation in (59) and our assumption on $v$, there always exists a matrix $U=[U_{1},U_{2}]$ satisfying $U_{1}U_{1}^{\top}-U_{2}U_{2}^{\top}=M_{\natural}$. Therefore, the set of minimizers of $f$ is nonempty and it coincides with $\mathcal{S}$. Note that in the special case $r_{2}=k_{2}=0$, the problem (60) becomes covariance matrix estimation chen2015exact and further reduces to phase retrieval when $k_{1}=r_{1}=1$ candes2013phaselift .

There exist numerical constant $c,C>0$, such that in the regime $m\geq Cr_{\natural}d$ and $d\geq C\log m$, with probability at least $1-C\exp(-cd)$, any flattest solution $U_{f}=(U_{f,1},U_{f,2})$ of (58) satisfies

The rest of the section is devoted to the proof of Theorem 7.1. The general strategy is very similar to the one pursued in Section 4. We begin with the following lemma that expresses the trace of the Hessian in the same spirit as Lemma 3.1. With this in mind, we define the matrix

The second order derivative of the function $f$ at any matrix $[U_{1},U_{2}]\in\mathcal{S}$ is the quadratic form:

The expression for $D^{2}f(U_{1},U_{2})[V_{1},V_{2}]$ follows immediately from algebraic manipulations. The trace of the Hessian therefore can be written as

Using the symmetry of the matrices $A_{i}$, the first term can be written as

Following exactly the same computation as (18) completes the proof. ∎

In particular, Lemma 7.2 implies that flat solutions are exactly the minimizers of the problem

We would like to next rewrite this problem in terms of minimizing a nuclear norm of a $d\times d$ matrix. With this in mind, we will require the following two lemmas in the spirit of the characterization of the nuclear norm (10).

$X$ admits a decomposition $X=U_{1}U_{1}^{\top}-U_{2}U_{2}^{\top}$ for some matrices $U_{i}\in{}^{d\times k_{i}}$,

$X$ has at most $k_{1}$ non-negative eigenvalues and $k_{2}$ non-positive eigenvalues.

The implication $\ref{it:2syms}\Rightarrow\ref{it:1syms}$ follows immediately from an eigenvalue decomposition of $X$. Conversely, suppose that 1 holds. Observe that 1 clearly is equivalent to being able to write $X=A-B$ with $A,B\succeq 0$, $\operatorname{rank}(A)\leq k_{1}$, and $\operatorname{rank}(B)\leq k_{2}$. Let $r_{1}$ be the number of strictly positive eigenvalues of $X$ and let $r_{2}$ be the number of strictly negative eigenvalues of $X$. We now prove $r_{1}\leq k_{1}$ by contradiction. A similar arguments yields $r_{2}\leq k_{2}$. Suppose indeed $r_{1}>k_{1}$ and consider the matrix $A:=X+B$. Let $\mathcal{U}$ be the span of eigenspaces corresponding to the top $r_{1}$ eigenvalues of $X$. Note that $\mathcal{U}$ has dimension $r_{1}$. Cauchy’s interlacing theorem implies that the $r_{1}$-th largest eigenvalue of $X+B$ satisfies that $\lambda_{r_{1}}(X+B)\geq\min_{v\in\mathcal{U}\setminus\{0\}}\frac{v^{\top}(X+B)v}{v^{\top}v}$. Since $B\succeq 0$, for any $v\in\mathcal{U}\setminus\{0\}$ we estimate $\frac{v^{\top}(X+B)v}{v^{\top}v}=\frac{v^{\top}Xv+v^{\top}Bv}{v^{\top}v}\geq\frac{v^{\top}Xv}{v^{\top}v}\geq\lambda_{r_{1}}(X)>0$. We conclude that that rank of $A$ is at least $r_{1}$, which is a contradiction since $A$ has rank at most $k_{1}$. ∎

Lemma 7.3 and 7.4 directly imply that the problem (67), which characterizes flat solutions, is equivalent to the rank constrained problem:

Therefore a natural convex relaxation simply drops the requirements on the eigenvalues:

The following theorem summarizes these observations.

Suppose that the matrix $D$ is invertible. Then the problems (67) and (68) are equivalent in the following sense.

The optimal values of (67) and (68) are equal.

If $[U_{1},U_{2}]$ solves (67), then $X=D(U_{1}U_{1}^{\top}-U_{2}U_{2}^{\top})D$ is optimal for (68).

Moreover, if $X=DM_{\natural}D$ is the unique minimizer of the problem (69), then any flat solution $[U_{1},U_{2}]$ satisfies $U_{1}U_{1}^{\top}-U_{2}U_{2}^{\top}=M_{\natural}$.

Define the linear map $\mathcal{A}_{1}:{}^{d\times d}\rightarrow{}^{\lfloor m\rfloor/2}$ by

and consider the convex optimization program

If $DM_{\natural}D$ is the unique solution of (71), then it is also the unique solution of (69).

It follows immediately that any $X$ that is feasible for (69) is also feasible for (71). Consequently, if the symmetric matrix $DM_{\natural}D$ is a unique minimizer of (71), then it must also be a unique minimizer of (69). This completes the proof. ∎

Exactly the same proof as that of Lemma 4.9 ensures that there exist constants $c_{1},c_{2},c_{3},c_{4}>0$ such that as long as we are in the regime, $m\geq c_{3}d$ and $\log(m)\leq c_{4}d$, the estimate holds:

Consequently, in this regime we may upper bound the condition number $\kappa$ of $D$ by $3$. In light of Lemma 4.7, in order to ensure that $DM_{\natural}D$ is the unique minimizer of (71), it remains to simply choose $k$ such that the inequality $\frac{9\delta_{2}}{\delta_{1}}\leq\sqrt{k}$ holds. Using Lemmas 7.5-7.6 completes the proof. ∎

Numerical experiments

Recall that we have proved that for a variety of overparameterized problems, under standard statistical assumptions, in the noiseless setting, (1) flat solutions recover the ground truth and (2) flat solutions are nearly norm-minimal and nearly-balanced (but not exactly). In this section, we numerically validate both of the claims, in order. Note that finding flat solutions in these examples, amounts to solving a convex optimization problem as long as the number of measurements is sufficiently large.

We consider four problems described earlier in the paper: (a) matrix sensing, (b) bilinear sensing, (c) matrix completion, and (d) neural networks with quadratic activation. For each setting, we consider different combination of the dimension $d=d_{1}=d_{2}$ and the number of measurements $m$ ($p$ for matrix completion). For each combination $(d,m)$ ( $(d,p)$ for matrix completion), we randomly generate a rank $2$ ground truth unit Frobenius norm matrix $M_{\natural}$ (rank $3$ for the setting of neural network with quadratic activation), then repeatedly generate the linear measurement map $\mathcal{A}$ and solve ten times the convex relaxation associated with being a flat solution and the nuclear norm minimization problem.

To measure the success of exact recovery, for a solution $\hat{X}$ from the convex relaxation of the scaled trace problem (or from the nuclear norm minimization), we measure the Frobenius norm error \mathopen{}\mathclose{{}\left\|D_{1}^{-1}\hat{X}D_{2}^{-1}-M_{\natural}}\right\|_{\mbox{\tiny{F}}} (or \mathopen{}\mathclose{{}\left\|\hat{X}-M_{\natural}}\right\|_{\mbox{\tiny{F}}} for the nuclear norm minimization). Our criterion for exact recovery is whether this error is smaller than $10^{-6}$ or not. Figure 3 shows the empirical probability of success recovery (averaging over ten times) for each combination of dimension and number of measurements. The figure is in gray scale and the whiter color indicates higher success probability. We observe that the frequency of exact recovery by flat solutions almost matches the frequency of exact recovery by nuclear norm minimization. Notice moreover that flat solutions exactly recover the ground truth matrix, though we are only able to show weak recovery for matrix completion.

Next we test the regularity of flat solutions for the (a) matrix sensing, (b) bilinear sensing, (c) matrix completion problems. We only consider the pairs $(d,m)$ such that the matrices $D_{1},D_{2}$ are nonsingular. Let $\hat{X}$ be the solution of the convex relaxation for being a flat solution and let $\hat{X}_{\texttt{nuc}}$ be the solution to the nuclear norm minimization problem. We compute the factors $L_{f}=D_{1}^{-1}U\sqrt{\Sigma}$ and $R_{f}=D_{2}^{-1}V\sqrt{\Sigma}$ using the full SVD of $\hat{X}=U\Sigma V^{\top}$. We then use the quantity \frac{\mathopen{}\mathclose{{}\left\|L_{f}}\right\|_{\mbox{\tiny{F}}}^{2}+\mathopen{}\mathclose{{}\left\|R_{f}}\right\|_{\mbox{\tiny{F}}}^{2}}{2\mathopen{}\mathclose{{}\left\|\hat{X}_{\texttt{nuc}}}\right\|_{*}} to measure the norm-minimality of flat solutions, and the quantity \mathopen{}\mathclose{{}\left\|L_{f}^{\top}L_{f}-R_{f}^{\top}R_{f}}\right\|_{*}/\mathopen{}\mathclose{{}\left\|M_{\natural}}\right\|_{*} to measure balancedness. Whenever one of the matrices $D_{1},D_{2}$ is singular, we set both measures to be $10^{20}$. The result (in $\log 10$ scale) is shown in Figure 4. We observe that whenever flat solutions exactly recover the ground truth, both measures are small but not exactly zero. In particular, the norm-minimal and flat solutions are distinct.

Conclusion and discussion on depth

In this paper, we analyzed a variety of low rank matrix recovery problems in rank-overparameterized settings. We considered overparameterized matrix and bilinear sensing, robust PCA, covariance matrix estimation, and single hidden layer neural networks with quadratic activation functions. In all cases, we showed that flat minima, measured by the scaled trace of the Hessian, exactly recover the ground truth under standard statistical assumptions. For matrix completion, we established weak recovery, although empirical evidence suggests exact recovery holds here as well.

Matrix factorization problems are suggestive of the behavior one may expect for two layer neural networks. Therefore, an appealing question is to consider the effect that depth may have on generalization properties of flat solutions. In this section, we argue that depth may not bode well for generalization of flat solutions. As a simple model, we consider the setting of sparse recovery under a “deep” overparameterization. Namely, consider a ground truth vector $x_{\natural}\in{}^{d}$ with at most $r_{\natural}$ nonzero coordinates. The goal is to recover $x_{\natural}$ from the observed measurements $b=Ax_{\natural}$ under a linear map $A\colon{}^{d}\rightarrow{}^{m}$. We assume that $A$ satisfies the restricted isometry property (RIP): there exist $(\delta_{1},\delta_{2})$ such that

The flat solutions are naturally defined as those $(v_{i})_{i=1}^{k}$ solving the following problem:

To compute the Hessian $\mathop{\rm tr}(D^{2}f(v_{1},\dots,v_{k}))$, let $a_{i}$ be the $i$-th column of $A$. Following a similar calculation as in Lemma 3.1 yields the expression

for any $(v_{i})_{i=1}^{k}\in{}^{d\times k}$ where

The following lemma shows that $D$ is close to the identity matrix.

Suppose that the linear map $A$ satisfies $(1-\delta,1+\delta)$ RIP for some $\delta\in(0,1)$. Then the matrix $D$ satisfies

Indeed, since $D$ is diagonal, we only need to show $\frac{1}{m}a_{i}^{\top}a_{i}\in[(1-\delta)^{2},(1+\delta)^{2}]$ for each index $i$. Note that \frac{1}{m}\mathopen{}\mathclose{{}\left\|Ae_{i}}\right\|_{2}^{2}=\frac{1}{m}a_{i}^{\top}a_{i}. Since $e_{i}$ is a sparse vector with only one nonzero, using the $(1-\delta,1+\delta)$ RIP, we have \frac{1}{m}a_{i}^{\top}a_{i}=\frac{1}{m}\mathopen{}\mathclose{{}\left\|Ae_{i}}\right\|_{2}^{2}\in[(1-\delta)^{2}\mathopen{}\mathclose{{}\left\|e_{i}}\right\|_{2},(1+\delta)^{2}\mathopen{}\mathclose{{}\left\|e_{i}}\right\|_{2}^{2}]=[(1-\delta)^{2},(1+\delta)^{2}] and our proof is complete. ∎

The next lemma shows that the following optimization problem is equivalent to the optimization problem defining flat solutions (76).

Denote by $v_{h,j}$ the $j$-th component of the vector variable $v_{h}$ for $1\leq h\leq k$.

Problem (76) is equivalent to Problem (79) in the following sense:

If $x$ solves (79), then any $v_{i}$ satisfying $x=v_{1}\odot\dots\odot v_{k}$ and $|v_{1,j}|=\dots=|v_{k,j}|$ for any $1\leq j\leq d$ solves (76).

If $v_{1},\dots,v_{k}$ solves (76), then $x=v_{1}\odot\dots\odot v_{k}$ solves (79).

According to (77), the trace of the Hessian is

In the step $(a)$, we use the well-known AM-GM inequality. The equality holds if and only if $|v_{1,j}|=\dots=|v_{k,j}|$ for any $1\leq j\leq d$. The rest follows by letting $x=v_{1}\odot\dots\odot v_{k}$.

There is a universal constant $c>0$ such that if the linear map $A$ satisfying $(1-\delta,1+\delta)$ RIP with $0<\delta<c$. Then for $k=2$, any solution $(v_{1},v_{2})$ to (76) satisfies $x_{\natural}=v_{1}\odot v_{2}$.

On the other hand, higher values of $k$ do not encourage sparsity. In the extreme case $k\rightarrow\infty$, the objective function in (79) is close to \mathopen{}\mathclose{{}\left\|x}\right\|_{2}^{2} which should give a dense solution in general. Indeed, in Figure 5, we plot the solution performance of (79) for different values $k=\{2,3,\dots,10\}$ and $r_{\natural}=\{1,2,3,4,5\}$ measured by the relative error \frac{\mathopen{}\mathclose{{}\left\|x-x_{\natural}}\right\|_{2}}{\mathopen{}\mathclose{{}\left\|x_{\natural}}\right\|_{2}}. We set $d=1000$ and $m=3\lceil r_{\natural}\log d\rceil$ and generate the signal $x_{\natural}$ with first $k$ components being $1$ and zero otherwise. For each configuration of $(k,r_{\natural})$, we randomly generate $25$ realizations of the Gaussian sensing matrix $A$ and solve (79) for each $A$. The performance metric \frac{\mathopen{}\mathclose{{}\left\|x-x_{\natural}}\right\|_{2}}{\mathopen{}\mathclose{{}\left\|x_{\natural}}\right\|_{2}} is averaged over these $25$ trials. Indeed, exact recovery is observed for $k=2$, while the relative error degrades significantly as $k$ increases.

References

Appendix A Extension to noisy observation

This section considers an extension of the flat solution concept to the setting where the observations are corrupted by noise:

where $\sigma>0$ is the noise level and $N(0,I_{m})$ is the standard $m$-dimensional Gaussian. Our discussion in the rest of the paper focused on the simpler case $\sigma=0$. We define the flat solution in this setting as follows. We continue to use the scaled trace ${\textrm{str}}(D^{2}f(L,R))$ as the flatness measure of the objective function. However, instead of considering all solutions $(L,R)$ that interpolate the data, we consider those pairs $(L,R)$ that are in the sublevel set:

The reason for this choice is that in the noisy observation setting, the global solution of (1) (with $k=\min\{d_{1},d_{2}\}$) has the potential of overfitting no matter what regularization has been enforced. Indeed, consider the simplest case $\mathcal{A}=\mathcal{I}$, i.e., the map $\mathcal{A}$ is the identity map. In this setting, any global minimizer $LR^{\top}$ is simply the observation $b=M_{\natural}+e$ itself. With the above preparation, we define the flat solutions to be the minimizers of the following problem.

The goal of the section is to prove the following.

Suppose that $\mathcal{A}$ is a Gaussian ensemble and the noise follows $e\sim N(0,\sigma^{2}I_{m})$. Then there exists universal constants $c,C$ such that for any $m\geq Cr_{\natural}d_{\max}$, with probability at least $1-C\exp(-c(d_{1}+d_{2}))$, any solution $(L_{f},R_{f})$ of (83) satisfies

Note that the bound $\sigma\sqrt{\frac{r_{\natural}(d_{1}+d_{2})}{m}}$ is minimax optimal according to .

Following (19) and (20) in Section 3.1, we see that (83) is equivalent to (in the sense of Theorem 3.2) minimizing the nuclear norm over rank constrained matrices so long as $D_{1},D_{2}$ matrices are invertible Note that the condition $\mathcal{A}(LR^{\top})=b$ is not needed for (16) to hold, which is critical for the step (19) to hold in the noisy case. :

Our proof is based on the argument in . Starting with the feasibility of $\hat{Y}$, we have

First, let us introduce a lemma that decomposes $\Delta$.

[47, Lemma 2.3 and 3.4] For any $A,B\in{}^{d\times d}$, there exists $B_{1},B_{2}$ such that (1) $B=B_{1}+B_{2}$, (2) $\operatorname{rank}(B_{1})\leq\operatorname{rank}(A)$, (3) $AB^{\top}_{2}=0$ and $A^{\top}B_{2}=0$, (4) \mathopen{}\mathclose{{}\left\|A+B_{2}}\right\|_{*}=\mathopen{}\mathclose{{}\left\|A}\right\|_{*}+\mathopen{}\mathclose{{}\left\|B_{2}}\right\|_{*}, and (5) $\langle B_{1},B_{2}\rangle=0$.

Using Lemma A.2, we can decompose $\Delta=R_{0}+R_{c}$ such that $Y_{0}R_{c}^{\top}=0,Y_{0}^{\top}R_{c}=0$, $R_{0}\leq 2r_{\natural}$, $\langle R_{0},R_{c}\rangle=0$, and \mathopen{}\mathclose{{}\left\|Y_{0}+R_{c}}\right\|_{*}=\mathopen{}\mathclose{{}\left\|Y_{0}}\right\|_{*}+\mathopen{}\mathclose{{}\left\|R_{c}}\right\|_{*}. Hence, we have

Using the optimality of \mathopen{}\mathclose{{}\left\|\hat{Y}}\right\|_{*}\leq\mathopen{}\mathclose{{}\left\|Y_{0}}\right\|_{*}, we have that

Using the fact that $R_{0}$ has rank no more than $2r_{\natural}$ and $\langle R_{0},R_{c}\rangle=0$, we have

Here in the first step, we use the triangle inequality for \mathopen{}\mathclose{{}\left\|\Delta}\right\|_{*}. This finishes the upper bound of \mathopen{}\mathclose{{}\left\|\Delta}\right\|_{*}.

Next we partition $R_{c}$ into a sum of matrices $R_{1},R_{2},\ldots$ each of rank at most $3r_{\natural}$ as in [47, Theorem 3.3]. Let $R_{c}=U\operatorname{diag}(\sigma)V^{\prime}$ be the singular value decomposition of $R_{c}$. For each $i\geq 1$ define the index set $I_{i}=\{3r_{\natural}(i-1)+1,\ldots,3r_{\natural}i\}$, and let $R_{i}:=U_{I_{i}}\operatorname{diag}(\sigma_{I_{i}})V_{I_{i}}^{\prime}$. Using the fact that $\langle R_{c},R_{0}\rangle=0$ and the construction of $R_{i}$, $i\geq 1$, we also have