Sparse generalized eigenvalue problem: optimal statistical rates via truncated Rayleigh flow
Sparse generalized eigenvalue problem: optimal statistical rates via truncated Rayleigh flow
复制标题
DOI：
10.1111/rssb.12291
复制
发表时间：
2018-11-01
影响因子：
5.8
通讯作者：
Zhang, Tong
中科院分区：
文献类型：
--
作者：
Tan, Kean Ming;Wang, Zhaoran;Zhang, Tong
稀疏广义特征值问题（GEP）是一类重要的高维统计模型，包括稀疏Fisher判别分析、典型相关分析和充分降维等。稀疏GEP涉及解决非凸优化问题。大多数现有的方法和理论的背景下，特定的统计模型，稀疏GEP的特殊情况下，需要限制性的结构假设的输入矩阵。我们提出了一个两阶段的计算框架来解决稀疏GEP。在第一阶段，我们解决了稀疏GEP的凸松弛。以解为初始值，然后利用非凸优化的观点，提出了截断瑞利流方法（我们称之为rifle '）来估计领先的广义特征向量。我们表明，步枪线性收敛到一个解决方案的最佳统计收敛速度。从理论上讲，我们的方法显着改善现有的文献，消除输入矩阵的结构假设。为了实现这一点，我们的分析涉及两个关键组成部分：一个新的基于梯度的方法的非凸目标函数的分析，和细粒度的稀疏模式的演化特性沿着的解决方案路径。
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.