TY - JOUR
T1 - How much restricted isometry is needed in nonconvex matrix recovery?
AU - Zhang, Richard Y.
AU - Sojoudi, Somayeh
AU - Josz, Cédric
AU - Lavaei, Javad
N1 - Funding Information:
We thank our three NIPS reviewers for helpful comments and suggestions. In particular, we thank reviewer #2 for a key insight that allowed us to lower-bound δ★ in Section 4. This work was supported by the ONR Awards N00014-17-1-2933 and ONR N00014-18-1-2526, NSF Award 1808859, DARPA Award D16AP00002, and AFOSR Award FA9550-17-1-0163.
Publisher Copyright:
© 2018 Curran Associates Inc.All rights reserved.
PY - 2018/1/1
Y1 - 2018/1/1
N2 - When the linear measurements of an instance of low-rank matrix recovery satisfy a restricted isometry property (RIP)-i.e. they are approximately norm-preserving-the problem is known to contain no spurious local minima, so exact recovery is guaranteed. In this paper, we show that moderate RIP is not enough to eliminate spurious local minima, so existing results can only hold for near-perfect RIP. In fact, counterexamples are ubiquitous: we prove that every x is the spurious local minimum of a rank-1 instance of matrix recovery that satisfies RIP. One specific counterexample has RIP constant δ = 1/2, but causes randomly initialized stochastic gradient descent (SGD) to fail 12% of the time. SGD is frequently able to avoid and escape spurious local minima, but this empirical result shows that it can occasionally be defeated by their existence. Hence, while exact recovery guarantees will likely require a proof of no spurious local minima, arguments based solely on norm preservation will only be applicable to a narrow set of nearly-isotropic instances.
AB - When the linear measurements of an instance of low-rank matrix recovery satisfy a restricted isometry property (RIP)-i.e. they are approximately norm-preserving-the problem is known to contain no spurious local minima, so exact recovery is guaranteed. In this paper, we show that moderate RIP is not enough to eliminate spurious local minima, so existing results can only hold for near-perfect RIP. In fact, counterexamples are ubiquitous: we prove that every x is the spurious local minimum of a rank-1 instance of matrix recovery that satisfies RIP. One specific counterexample has RIP constant δ = 1/2, but causes randomly initialized stochastic gradient descent (SGD) to fail 12% of the time. SGD is frequently able to avoid and escape spurious local minima, but this empirical result shows that it can occasionally be defeated by their existence. Hence, while exact recovery guarantees will likely require a proof of no spurious local minima, arguments based solely on norm preservation will only be applicable to a narrow set of nearly-isotropic instances.
UR - http://www.scopus.com/inward/record.url?scp=85064807283&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85064807283&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85064807283
VL - 2018-December
SP - 5586
EP - 5597
JO - Advances in Neural Information Processing Systems
JF - Advances in Neural Information Processing Systems
SN - 1049-5258
T2 - 32nd Conference on Neural Information Processing Systems, NeurIPS 2018
Y2 - 2 December 2018 through 8 December 2018
ER -