Timezone: »
Poster
General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
Haixiang Zhang · Yingjie Bi · Javad Lavaei
This paper considers the global geometry of general low-rank minimization problems via the Burer-Monterio factorization approach. For the rank-$1$ case, we prove that there is no spurious second-order critical point for both symmetric and asymmetric problems if the rank-$2$ RIP constant $\delta$ is less than $1/2$. Combining with a counterexample with $\delta=1/2$, we show that the derived bound is the sharpest possible. For the arbitrary rank-$r$ case, the same property is established when the rank-$2r$ RIP constant $\delta$ is at most $1/3$. We design a counterexample to show that the non-existence of spurious second-order critical points may not hold if $\delta$ is at least $1/2$. In addition, for any problem with $\delta$ between $1/3$ and $1/2$, we prove that all second-order critical points have a positive correlation to the ground truth. Finally, the strict saddle property, which can lead to the polynomial-time global convergence of various algorithms, is established for both the symmetric and asymmetric problems when the rank-$2r$ RIP constant $\delta$ is less than $1/3$. The results of this paper significantly extend several existing bounds in the literature.
Author Information
Haixiang Zhang (University of California, Berkeley)
Yingjie Bi (University of California, Berkeley)
Javad Lavaei (University of California, Berkeley)
More from the Same Authors
-
2023 Poster: Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensing »
Ziye Ma · Javad Lavaei · Somayeh Sojoudi -
2023 Poster: Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities »
Donghao Ying · Yunkai Zhang · Yuhao Ding · Alec Koppel · Javad Lavaei -
2023 Poster: Geometric Analysis of Matrix Sensing over Graphs »
Haixiang Zhang · Ying Chen · Javad Lavaei -
2023 Poster: Adapt to Adapt: A Tempo-control Framework for Non-stationary Reinforcement Learning »
Hyunin Lee · Yuhao Ding · Jongmin Lee · Ming Jin · Javad Lavaei · Somayeh Sojoudi -
2023 Poster: No-Regret Learning in Dynamic Competition with Reference Effects Under Logit Demand »
Mengzi Amy Guo · Donghao Ying · Javad Lavaei · Zuo-Jun Shen -
2021 Poster: Stochastic $L^\natural$-convex Function Minimization »
Haixiang Zhang · Zeyu Zheng · Javad Lavaei -
2018 Poster: How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery? »
Richard Zhang · Cedric Josz · Somayeh Sojoudi · Javad Lavaei -
2018 Spotlight: How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery? »
Richard Zhang · Cedric Josz · Somayeh Sojoudi · Javad Lavaei -
2018 Poster: A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization »
Cedric Josz · Yi Ouyang · Richard Zhang · Javad Lavaei · Somayeh Sojoudi