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 [Formula: see text] matrix [Formula: see text] with rank r from m linear measurements, some potentially noisy. When the noise is distributed according to an outlier model, minimizing a nonsmooth [Formula: see text]-loss with a simple subgradient method can often perfectly recover the ground truth matrix [Formula: see text]. Given this, a natural question is what optimization property (if any) enables such learning behavior. The most plausible answer is that the ground truth [Formula: see text] 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 [Formula: see text] 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.