The Landscape of Non-convex Empirical Risk with Degenerate Population Risk

Abstract

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.

References in corpus (13)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• An overview of low-rank matrix recovery from incomplete observations
• Guaranteed Matrix Completion via Non-convex Factorization
• Low-rank optimization for semidefinite convex problems
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Learning One-hidden-layer Neural Networks with Landscape Design
• The Non-convex Geometry of Low-rank Matrix Optimization
• The Landscape of Empirical Risk for Non-convex Losses
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Sample Complexity Analysis for Learning Overcomplete Latent Variable Models through Tensor Methods
• A Cubic Regularized Newton's Method over Riemannian Manifolds
• An inequality for the trace of matrix products, using absolute values
• Global Optimality in Distributed Low-rank Matrix Factorization

Cited by in corpus (2)

• The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
• Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem