Sparse generalized eigenvalue problem: optimal statistical rates via truncated Rayleigh flow

Kean Ming Tan, Zhaoran Wang, Han Liu, Tong Zhang

Research output: Contribution to journalArticlepeer-review

29 Scopus citations


The sparse generalized eigenvalue problem (GEP) plays a pivotal role in a large family of high dimensional statistical models, including sparse Fisher's discriminant analysis, canonical correlation analysis and sufficient dimension reduction. The sparse GEP involves solving a non-convex optimization problem. Most existing methods and theory in the context of specific statistical models that are special cases of the sparse GEP require restrictive structural assumptions on the input matrices. We propose a two-stage computational framework to solve the sparse GEP. At the first stage, we solve a convex relaxation of the sparse GEP. Taking the solution as an initial value, we then exploit a non-convex optimization perspective and propose the truncated Rayleigh flow method (which we call ‘rifle’) to estimate the leading generalized eigenvector. We show that rifle converges linearly to a solution with the optimal statistical rate of convergence. Theoretically, our method significantly improves on the existing literature by eliminating structural assumptions on the input matrices. To achieve this, our analysis involves two key ingredients: a new analysis of the gradient-based method on non-convex objective functions, and a fine-grained characterization of the evolution of sparsity patterns along the solution path. Thorough numerical studies are provided to validate the theoretical results.

Original languageEnglish (US)
Pages (from-to)1057-1086
Number of pages30
JournalJournal of the Royal Statistical Society. Series B: Statistical Methodology
Issue number5
StatePublished - Nov 2018

Bibliographical note

Funding Information:
We thank the Joint Editor, Associate Editor and two reviewers for their helpful comments that improved an earlier version of this paper. We thank Gao Chao and Xiaodong Li for responding to our enquiries. Tong Zhang was supported by National Science Foundation grants NSF IIS-1250985 and NSF IIS-1407939 and National Institutes of Health grant NIH R01AI116744. Kean Ming Tan was supported by National Science Foundation grants NSF IIS-1250985, NSF IIS-1407939 and NSF DMS-1811315.

Publisher Copyright:
© 2018 Royal Statistical Society


  • Convex relaxation
  • Non-convex optimization
  • Sparse Fisher's discriminant analysis
  • Sparse canonical correlation analysis
  • Sparse sufficient dimension reduction


Dive into the research topics of 'Sparse generalized eigenvalue problem: optimal statistical rates via truncated Rayleigh flow'. Together they form a unique fingerprint.

Cite this