Sparse Generalized Eigenvalue Problem: Optimal Statistical Rates via Truncated Rayleigh Flow

DOI10.48550/ARXIV.1604.08697zbMATH Open1407.62212arXiv1604.08697OpenAlexW2963763664WikidataQ129229539 ScholiaQ129229539MaRDI QIDQ148604FDOQ148604

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

Publication date: 29 April 2016

Published in: Journal of the Royal Statistical Society Series B: Statistical Methodology (Search for Journal in Brave)

Abstract: 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. 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. In this paper, 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 nonconvex optimization perspective and propose the truncated Rayleigh flow method (Rifle) to estimate the leading generalized eigenvector. We show that Rifle converges linearly to a solution with the optimal statistical rate of convergence for many statistical models. Theoretically, our method significantly improves upon the existing literature by eliminating structural assumptions on the input matrices for both stages. To achieve this, our analysis involves two key ingredients: (i) a new analysis of the gradient based method on nonconvex objective functions, and (ii) a fine-grained characterization of the evolution of sparsity patterns along the solution path. Thorough numerical studies are provided to validate the theoretical results.

Full work available at URL: https://arxiv.org/abs/1604.08697

zbMATH Keywords

convex relaxationnon-convex optimizationsparse canonical correlation analysissparse Fisher's discriminant analysissparse sufficient dimension reduction

Mathematics Subject Classification ID

Applications of statistics to biology and medical sciences; meta analysis (62P10) Measures of association (correlation, canonical correlation, etc.) (62H20)

Cited In (19)

• Supervised Principal Component Regression for Functional Responses with High Dimensional Predictors
• Eigenvectors from Eigenvalues Sparse Principal Component Analysis
• Double-slicing assisted sufficient dimension reduction for high-dimensional censored data
• Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems
• A Bregman proximal subgradient algorithm for nonconvex and nonsmooth fractional optimization problems
• Subspace Estimation with Automatic Dimension and Variable Selection in Sufficient Dimension Reduction
• An \(\ell_1\)-penalized adaptive normalized quasi-Newton algorithm for sparsity-aware generalized eigen-subspace tracking
• Sparse SIR: optimal rates and adaptive estimation
• Continuous and atlas-free analysis of brain structural connectivity
• First-Order Algorithms for a Class of Fractional Optimization Problems
• Tensor Canonical Correlation Analysis With Convergence and Statistical Guarantees
• Misspecified nonconvex statistical optimization for sparse phase retrieval
• Minimax Quasi-Bayesian Estimation in Sparse Canonical Correlation Analysis via a Rayleigh Quotient Function
• rifle
• Partially Observed Dynamic Tensor Response Regression
• Slicing-free inverse regression in high-dimensional sufficient dimension reduction
• Tensor canonical correlation analysis
• High-dimensional sparse single-index regression via Hilbert-Schmidt independence criterion
• Sparse Minimum Discrepancy Approach to Sufficient Dimension Reduction with Simultaneous Variable Selection in Ultrahigh Dimension

Recommendations

• Sparsistency and rates of convergence in large covariance matrix estimation 👍 👎
• Sparse PCA: optimal rates and adaptive estimation 👍 👎
• Estimating sparse precision matrix: optimal rates of convergence and adaptive estimation 👍 👎
• Penalized Orthogonal Iteration for Sparse Estimation of Generalized Eigenvalue Problem 👍 👎
• A majorization-minimization approach to the sparse generalized eigenvalue problem 👍 👎
• Sparse Generalized Eigenvalue Problem Via Smooth Optimization 👍 👎
• Optimal computational and statistical rates of convergence for sparse nonconvex learning problems 👍 👎
• Sparse Stochastic Processes and Discretization of Linear Inverse Problems 👍 👎
• Optimal rates of convergence for sparse covariance matrix estimation 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Sparse Generalized Eigenvalue Problem: Optimal Statistical Rates via Truncated Rayleigh Flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q148604)