Timezone: »
Spotlight
How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?
Richard Zhang · Cedric Josz · Somayeh Sojoudi · Javad Lavaei
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.
Author Information
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 #46
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: Asymmetric Certified Robustness via Feature-Convex Neural Networks »
Samuel Pfrommer · Brendon Anderson · Julien Piet · 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 -
2021 Poster: General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds »
Haixiang Zhang · Yingjie Bi · Javad Lavaei -
2020 Poster: Implicit Graph Neural Networks »
Fangda Gu · Heng Chang · Wenwu Zhu · Somayeh Sojoudi · Laurent El Ghaoui -
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