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

• 成果类型: Article; Early Access
• 署名作者: Ma, Jianhao; Fattahi, Salar
• 署名单位: University of Michigan System; University of Michigan
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.0371
• 发表日期: 2025
• 关键词: factorization; inequalities; optimization; CONVERGENCE; Incoherence; geometry; minima

摘要

We explore the local landscape of low-rank matrix recovery, focusing on reconstructing a d1 x d2 matrix X* with rank r from m linear measurements, some potentially noisy. When the noise is distributed according to an outlier model, minimizing a nonsmooth & ell;1-loss with a simple subgradient method can often perfectly recover the ground truth matrix X*. 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* 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* 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.