Can Learning Be Explained by Local Optimality in Robust Low-Rank Matrix Recovery?

We explore the local landscape of low-rank matrix recovery, focusing on reconstructing a $d_1\times d_2$ matrix $X^{\star }$ with rank r from m linear measurements, some potentially noisy. When the noise is distributed according to an outlier model, minimizing a nonsmooth ${\mathcal{\ell }}_1$-loss with a simple subgradient method can often perfectly recover the ground truth matrix $X^{\star }$. Given this, a natural question is what optimization property (if any) enables such learning behavior. The most plausible answer is that the ground truth $X^{\star }$ manifests as a local optimum of the loss function. In this paper, we provide a strong negative answer to this question, showing that, under moderate assumptions, the true solutions corresponding to $X^{\star }$ do not emerge as local optima, but rather as strict saddle points—critical points with strictly negative curvature in at least one direction. Our findings challenge the conventional belief that all strict saddle points are undesirable and should be avoided.

Funding: Financial support from the National Science Foundation (NSF) Division of Computing and Communication Foundations [CAREER Award CCF-2337776], the Office of Naval Research [Award N00014-22-1-2127], and the NSF Division of Mathematical Sciences [Award DMS-2152776] is gratefully acknowledged.