Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time

Understand

Sparse principal component analysis (PCA) involves nonconvex optimization for which the global solution is hard to obtain.

• To address this issue, one popular approach is convex relaxation.
• However, such an approach may produce suboptimal estimators due to the relaxation effect.
• To optimally estimate sparse principal subspaces, we propose a two-stage computational framework named "tighten after relax": Within the 'relax' stage, we approximately solve a convex relaxation of sparse PCA with early stopping to obtain a desired initial estimator; For the 'tighten' stage, we propose a novel algorithm called sparse orthogonal iteration pursuit (SOAP), which iteratively refines the initial estimator by directly solving the underlying nonconvex problem.