Title: Sparse generalized eigenvalue problem: Optimal statistical rates via truncated Rayleigh flow
Authors: Kean Ming Tan - University of Minnesota (United States) [presenting]
Zhaoran Wang - Northwestern University (United States)
Han Liu - Northwestern University (United States)
Tong Zhang - Tencent Technology (China)
Abstract: Sparse generalized eigenvalue problem plays a pivotal role in a large family of high-dimensional learning tasks, including sparse Fishers discriminant analysis, canonical correlation analysis, and sufficient dimension reduction. However, existing methods and theory in the context of specific statistical models require restrictive structural assumptions on the input matrices. We exploit a nonconvex optimization perspective to study the sparse generalized eigenvalue problem under a unified framework. In particular, we propose the truncated Rayleigh flow method (Rifle) to estimate the leading generalized eigenvector and show that it converges linearly to a solution with the optimal statistical rate of convergence. Theoretically, our method significantly improves upon the existing literature by eliminating the structural assumption on the input matrices. To achieve this, our analysis involves two key ingredients: (i) a new analysis of the gradient based method on nonconvex objective functions, as well as (ii) a fine-grained characterization of the evolution of sparsity patterns along the solution path. Thorough numerical studies are provided to back up our theory.