High-Dimensional Sparse Generalized Eigenvalue Problem and Its Applications to Multivariate Statistics

• Activity Number: 354 - Topics in Machine Learning
• Type: Contributed
• Date/Time: Tuesday, July 31, 2018 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Learning and Data Science
• Author(s): Kean Ming Tan* and Zhaoran Wang and Han Liu and Tong Zhang
• Companies: University of Minnesota and Northwestern University and Northwestern University and Tencent Technology
• Keywords: Convex relaxation; nonconvex optimization; sparse Fisher's discriminant analysis; sparse canonical correlation analysis; sparse sufficient dimension reduction

Abstract

Sparse generalized eigenvalue problem plays a pivotal role in a large family of high-dimensional learning tasks, including sparse Fisher's 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. In this paper, 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.