Name
Title | ||
|---|---|---|
Symmetry. Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization |
Abstract | ||
|---|---|---|
We propose a general theory for studying the geometry of nonconvex objective functions with underlying symmetric structures. In specific, we characterize the locations of stationary points and the null space of the associated Hessian matrices via the lens of invariant groups. As a major motivating example, we apply the proposed general theory to characterize the global geometry of the low-rank matrix factorization problem. In particular, we illustrate how the rotational symmetry group gives rise to infinitely many nonisolated strict saddle points and equivalent global minima of the objective function. By explicitly identifying all stationary points, we divide the entire parameter space into three regions: (R
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub>
) the region containing the neighborhoods of all strict saddle points, where the objective has negative curvatures; (R
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub>
) the region containing neighborhoods of all global minima, where the objective enjoys strong convexity along certain directions; and (R
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sub>
) the complement of the above regions, where the gradient has sufficiently large magnitudes. We further extend our result to the matrix sensing problem. This allows us to establish strong global convergence guarantees for popular iterative algorithms with arbitrary initialization. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/ITA.2018.8503215 | 2018 Information Theory and Applications Workshop (ITA) |
Keywords | Field | DocType |
global geometry,rotational symmetry group,matrix sensing problem,nonconvex matrix factorization,nonconvex objective functions,symmetric structures,Hessian matrices,global convergence,global optimization,strict saddle points | Phase retrieval,Saddle point,Global optimization,Matrix (mathematics),Matrix decomposition,Pure mathematics,Hessian matrix,Maxima and minima,Stationary point,Mathematics | Conference |
ISBN | Citations | PageRank |
978-1-7281-1995-3 | 7 | 0.44 |
References | Authors | |
31 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xingguo Li | 1 | 96 | 19.95 |
| Jarvis D. Haupt | 2 | 11 | 3.23 |
| Junwei Lu | 3 | 387 | 34.94 |
| Zhaoran Wang | 4 | 157 | 33.20 |
| R. Arora | 5 | 489 | 35.97 |
| Han Liu | 6 | 434 | 42.70 |
| Tuo Zhao | 7 | 222 | 40.58 |