How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?
Richard Zhang · Cedric Josz · Somayeh Sojoudi · Javad Lavaei
Wed Dec 05 01:15 PM -- 01:20 PM (PST) @ Room 517 CD
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: every $x$ is the spurious local minimum of a rank-1 instance of matrix recovery that satisfies RIP. One specific counterexample has RIP constant $\delta=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.
Richard Zhang (University of California, Berkeley)
Cedric Josz (UC Berkeley)
Somayeh Sojoudi (University of California, Berkeley)
Javad Lavaei (University of California, Berkeley)
Related Events (a corresponding poster, oral, or spotlight)
2018 Poster: How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery? »
Wed Dec 5th through Thu the 6th Room Room 210
More from the Same Authors
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