Tighten after Relax: Minimax-Optimal Sparse PCA in Polynomial Time
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 1/ √ t 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.
In the paper, a sparse PCA algorithm was studied. At the beginning, the authors introduced existing methods and theirdrawbacks in terms of both statistical and computational properties. Then, a two stage algorithm was proposed toovercome the drawbacks. In the first stage of the algorithm, a computationally efficient but statistically inefficientmethod based on the ADMM is used to obtain a preliminary solution. In the second step, the algorithm called sparseorthogonal iteration pursuit is used to improve the solution obtained in the first stage. Also, some theoreticalproperties of the estimator were investigated. Numerical experiments showed the usefulness of the proposed methodscompared to some existing methods. This paper is well written, though constants are very dense. Especially, theoretical studies include some remarkableresults such as the minimax-optimality of the algorithm, the blessing of large sample size, and analysis for non-Gaussor dependent data. Though I could not read the supplementary of the paper in such a short view period, I'll try to check it out in theremaining review period, and give some comments.