Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
arXiv:2106.06574 · doi:10.1109/TSP.2022.3181333
Abstract
Spectral methods include a family of algorithms related to the eigenvectors of certain data-generated matrices. In this work, we are interested in studying the geometric landscape of the eigendecomposition problem in various spectral methods. In particular, we first extend known results regarding the landscape at critical points to larger regions near the critical points in a special case of finding the leading eigenvector of a symmetric matrix. For a more general eigendecomposition problem, inspired by recent findings on the connection between the landscapes of empirical risk and population risk, we then build a novel connection between the landscape of an eigendecomposition problem that uses random measurements and the one that uses the true data matrix. We also apply our theory to a variety of low-rank matrix optimization problems and conduct a series of simulations to illustrate our theoretical findings.
References in corpus (20)
- Finding community structure in networks using the eigenvectors of matrices
- An overview of gradient descent optimization algorithms
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Phase Retrieval via Wirtinger Flow: Theory and Algorithms
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Guaranteed Matrix Completion via Non-convex Factorization
- Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
- A Geometric Analysis of Phase Retrieval
- Spectral Methods for Data Science: A Statistical Perspective
- When Are Nonconvex Problems Not Scary?
- Efficient approaches for escaping higher order saddle points in non-convex optimization
- Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
- Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
- A Generic Approach for Escaping Saddle points
- The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
- Steepest descent algorithm on orthogonal Stiefel manifolds
- Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA
- A Cubic Regularized Newton's Method over Riemannian Manifolds
- The Landscape of Non-convex Empirical Risk with Degenerate Population Risk