Tighten after Relax: Minimax-Optimal Sparse PCA in Polynomial Time
Tighten after Relax: Minimax-Optimal Sparse PCA in Polynomial Time
复制标题
DOI：
--
复制
发表时间：
2014-12
期刊：
影响因子：
--
通讯作者：
Zhaoran Wang;Huanran Lu;Han Liu
中科院分区：
文献类型：
--
作者：
Zhaoran Wang;Huanran Lu;Han Liu
我们提供了高维稀疏主成分分析（PCA）的统计和计算分析。稀疏PCA问题本质上是高度非凸的。因此，尽管它的全局解达到了最优的统计收敛速率，但这种解在计算上难以获得。同时，尽管它的凸松弛易于计算，但它们产生的估计量具有次优的统计收敛率。另一方面，现有的非凸优化方法，如贪心方法，缺乏统计保证。本文提出一种两阶段稀疏主成分分析方法，在多项式时间内获得最优主子空间估计量。主阶段采用稀疏正交迭代寻优算法，迭代求解底层非凸问题。然而，我们的分析表明，该算法仅在一个有限的区域（即吸引力盆地）内具有所需的计算和统计保证。为了得到落在这个区域内的期望初始估计量，我们求解了一个具有早停止的稀疏主成分分析的凸公式。在一个综合的分析框架下，我们同时描述了这两阶段过程的计算和统计性能。在计算上，我们的过程在初始化阶段以[公式：见文本]的速率收敛，在主阶段以几何速率收敛。统计上，最终的主子空间估计量实现了相对于稀疏度水平s*，维数d和样本量n的最小-最优统计收敛率。我们的过程激发了解决具有可证明统计保证的非凸统计学习问题的一般范例。
We provide statistical and computational analysis of sparse Principal Component Analysis (PCA) in high dimensions. The sparse PCA problem is highly nonconvex in nature. Consequently, though its global solution attains the optimal statistical rate of convergence, such solution is computationally intractable to obtain. Meanwhile, although its convex relaxations are tractable to compute, they yield estimators with suboptimal statistical rates of convergence. On the other hand, existing nonconvex optimization procedures, such as greedy methods, lack statistical guarantees. In this paper, we propose a two-stage sparse PCA procedure that attains the optimal principal subspace estimator in polynomial time. The main stage employs a novel algorithm named sparse orthogonal iteration pursuit, which iteratively solves the underlying nonconvex problem. However, our analysis shows that this algorithm only has desired computational and statistical guarantees within a restricted region, namely the basin of attraction. To obtain the desired initial estimator that falls into this region, we solve a convex formulation of sparse PCA with early stopping. Under an integrated analytic framework, we simultaneously characterize the computational and statistical performance of this two-stage procedure. Computationally, our procedure converges at the rate of [Formula: see text] within the initialization stage, and at a geometric rate within the main stage. Statistically, the final principal subspace estimator achieves the minimax-optimal statistical rate of convergence with respect to the sparsity level s*, dimension d and sample size n. Our procedure motivates a general paradigm of tackling nonconvex statistical learning problems with provable statistical guarantees.