$\ell_1$-norm rank-one symmetric matrix factorization has no spurious second-order stationary points

Jiewen Guan, Anthony Man–Cho SoarXiv 2024 · DOI · arXiv

TL;DR

Researchers have proven that for $\ell_1$-norm rank-one symmetric matrix factorization, every "second-order stationary point" is a global optimum. This means that in the mathematical landscape of this problem, there are no "traps" (spurious local minima) that can fool an algorithm into thinking it has found the best solution when it hasn't—a major win for robust data analysis.

What Problem Does This Paper Address?

Matrix factorization is the engine behind everything from Netflix recommendations to dimensionality reduction (PCA). Traditionally, we use the $\ell_2$-norm (Frobenius norm) to measure how well our factorization fits the data. The $\ell_2$-norm is mathematically "smooth," and we’ve known for years that its optimization landscape is "benign"—it has a "strict saddle" property, meaning any point that isn't a local minimum has a clear path downward.

However, the $\ell_2$-norm is notoriously sensitive to outliers. A single corrupted data point can pull the entire factorization off track. To fix this, researchers use the $\ell_1$-norm, which is far more robust. The catch? The $\ell_1$-norm is nonsmooth (it has sharp "kinks" like an absolute value function). This nonsmoothness breaks the standard calculus tools we use to analyze optimization landscapes. Until now, we didn't know for sure if the $\ell_1$ version of this problem was riddled with "spurious" local minima that could trap our algorithms.

Methods

The authors tackle the rank-one symmetric case: $\min_{u} \frac{1}{2} \|uu^T - u^*u^{*T}\|_1$. To navigate this "spiky" terrain, they employ second-order variational analysis.

Instead of standard gradients and Hessians (which don't exist at the "kinks"), they use generalized derivatives:

  • Subdifferentials: To handle first-order stationarity in nonsmooth functions.
  • Second Subderivatives: A sophisticated tool that generalizes the idea of "curvature" to functions that aren't twice-differentiable.

By meticulously characterizing the set of all stationary points, they were able to test the "curvature" at every point where an algorithm might stop.

Datasets

As a theoretical mathematics paper, it does not use large-scale empirical datasets. Instead, it relies on:

  • Synthetic Ground Truths: Vectors $u^*$ (including standard Gaussian vectors) used to construct the target matrix.
  • Constructed Counter-examples: Specifically designed functions (Examples 4.2, 4.3, and 4.4) to demonstrate how nonsmooth landscapes behave differently than smooth ones under perturbation.

Key Insights and Ideas

  • The "No Spurious Traps" Guarantee: The headline result is that any point satisfying second-order optimality conditions is guaranteed to be a global minimizer. If you find a point where the "slope" is zero and there's no "downward curvature" (in the generalized sense), you've found the ground truth.
  • Negative Curvature at Spurious Points: The authors show that at every "bad" stationary point (points that aren't the global minimum), there is always a direction with negative second subderivative. Essentially, there's always a way out of the trap if your algorithm is smart enough to look for it.
  • The Danger of "Tilting": In smooth optimization, adding a tiny linear "tilt" to a function usually doesn't change the landscape much. The authors show that in the nonsmooth $\ell_1$ world, a tiny tilt can create an infinite number of new local minima or drift the global minimum arbitrarily far away. This is a major warning for practitioners who use "regularization" or "perturbation" tricks.
  • Absence of Active Manifolds: They prove that for some simple $\ell_1$ problems, the "active manifold" (a smooth surface where the function behaves nicely) doesn't even exist. This means many standard convergence proofs for nonsmooth algorithms simply don't apply here.

Key Results

  • Theorem 3.1: Provides a complete mathematical characterization of all stationary points for the $\ell_1$ rank-one problem.
  • Theorem 3.8 & Corollary 3.11: Proves that all second-order stationary points (SOSPs) are globally optimal. There are no spurious SOSPs.
  • Example 3.3: Demonstrates a striking difference from the $\ell_2$ case—at the origin (zero vector), the $\ell_1$ objective can actually have positive curvature in some directions, whereas the $\ell_2$ objective is always a local maximum or saddle.

Limitations and Future Work

  • Rank-One and Symmetry: The proof is currently limited to the symmetric, rank-one case ($uu^T$). Real-world problems often involve asymmetric matrices and higher-rank factorizations ($UV^T$).
  • Algorithmic Gap: While the paper proves the landscape is benign, it doesn't provide a deterministic algorithm that is guaranteed to find these SOSPs. The authors propose Conjecture 4.5, suggesting that standard subgradient descent with random initialization should work almost surely, but a formal proof remains elusive.
  • Outlier Conditions: The study assumes a "clean" ground truth. Future work is needed to see if these benign properties hold when the data is actually corrupted by the very outliers the $\ell_1$-norm is meant to handle.

Summary updated

Abstract

This paper studies the nonsmooth optimization landscape of the $\ell_1$-norm rank-one symmetric matrix factorization problem using tools from second-order variational analysis. Specifically, as the main finding of this paper, we show that any second-order stationary point (and thus local minimizer) of the problem is actually globally optimal. Besides, some other results concerning the landscape of the problem, such as a complete characterization of the set of stationary points, are also developed, which should be interesting in their own rights. Furthermore, with the above theories, we revisit existing results on the generic minimizing behavior of simple algorithms for nonsmooth optimization and showcase the potential risk of their applications to our problem through several examples. Our techniques can potentially be applied to analyze the optimization landscapes of a variety of other more sophisticated nonsmooth learning problems, such as robust low-rank matrix recovery.
BibTeX
@misc{guan2024ell,
  author = {Jiewen Guan and Anthony Man–Cho So},
  title = {{$\textbackslash\{\}ell\_1$-norm rank-one symmetric matrix factorization has no spurious second-order stationary points}},
  year = {2024},
  eprint = {2410.05025},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.05025},
}
Figure