Tighten after Relax: Minimax-Optimal Sparse PCA in Polynomial Time

Area of Science:

• Statistics
• Computational Science
• Machine Learning

Background:

• Sparse Principal Component Analysis (PCA) is crucial for high-dimensional data but is computationally challenging due to its non-convex nature.
• Existing methods offer either optimal statistical rates (computationally intractable) or tractable computation (suboptimal rates), with greedy methods lacking statistical guarantees.

Purpose of the Study:

• To develop a sparse PCA procedure that achieves optimal statistical convergence rates within polynomial time.
• To address the computational intractability and statistical suboptimality of current sparse PCA techniques.

Main Methods:

• A two-stage approach combining a convex formulation with early stopping for initialization and a novel nonconvex optimization algorithm (sparse orthogonal iteration pursuit) for the main stage.
• Integrated analytic framework to simultaneously analyze computational and statistical performance.

Main Results:

• The proposed procedure achieves minimax-optimal statistical rates for the principal subspace estimator concerning sparsity, dimension, and sample size.
• Demonstrates polynomial-time convergence (rate [Formula: see text]) in the initialization stage and geometric convergence in the main stage.

Conclusions:

• The two-stage sparse PCA procedure effectively balances computational efficiency and statistical accuracy in high dimensions.
• This work presents a general paradigm for solving non-convex statistical learning problems with provable guarantees.