The landscape of empirical risk has been widely studied in a series of machine learning problems, including low-rank matrix factorization, matrix sensing, matrix completion, and phase retrieval. In this work, we focus on the situation where the corresponding population risk is a degenerate non-convex loss function, namely, the Hessian of the population risk can have zero eigenvalues. Instead of analyzing the non-convex empirical risk directly, we first study the landscape of the corresponding population risk, which is usually easier to characterize, and then build a connection between the landscape of the empirical risk and its population risk. In particular, we establish a correspondence between the critical points of the empirical risk and its population risk without the strongly Morse assumption, which is required in existing literature but not satisfied in degenerate scenarios. We also apply the theory to matrix sensing and phase retrieval to demonstrate how to infer the landscape of empirical risk from that of the corresponding population risk.
Shuang Li (Colorado School of Mines)
Gongguo Tang (Colorado School of Mines)
Gongguo Tang is an Assistant Professor in the Department of Electrical Engineering at Colorado School of Mines since 2014. Before that, he was a visiting scholar at Simons Institute for the Theory of Computing at University of California, Berkeley in Fall 2013 and a postdoc working with Professor Robert Nowak at the University of Wisconsin-Madison and Professor Benjamin Recht at the University of California, Berkeley from August 2011 to December 2013. He received his Ph.D. in Electrical Engineering from Washington University in St. Louis under the supervision of Professor Arye Nehorai.
Michael B Wakin (Colorado School of Mines)
More from the Same Authors
2019 Poster: Distributed Low-rank Matrix Factorization With Exact Consensus »
Zhihui Zhu · Qiuwei Li · Xinshuo Yang · Gongguo Tang · Michael B Wakin
2015 Poster: Sparse and Low-Rank Tensor Decomposition »
Parikshit Shah · Nikhil Rao · Gongguo Tang
2009 Workshop: Manifolds, sparsity, and structured models: When can low-dimensional geometry really help? »
Richard Baraniuk · Volkan Cevher · Mark A Davenport · Piotr Indyk · Bruno Olshausen · Michael B Wakin