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

Abstract

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. A key concept of this two-stage framework is the basin of attraction. It represents a local region within which the `tighten' stage has desired computational and statistical guarantees. We prove that, the initial estimator obtained from the 'relax' stage falls into such a region, and hence SOAP geometrically converges to a principal subspace estimator which is minimax-optimal within a certain model class. Unlike most existing sparse PCA estimators, our approach applies to the non-spiked covariance models, and adapts to non-Gaussianity as well as dependent data settings. Moreover, through analyzing the computational complexity of the two stages, we illustrate an interesting phenomenon that larger sample size can reduce the total iteration complexity. Our framework motivates a general paradigm for solving many complex statistical problems which involve nonconvex optimization with provable guarantees.

64 pages, 8 figures

References in corpus (8)

• Generalized power method for sparse principal component analysis
• Sparse principal component analysis and iterative thresholding
• Sparse PCA: Optimal rates and adaptive estimation
• Optimal detection of sparse principal components in high dimension
• Optimal Solutions for Sparse Principal Component Analysis
• Truncated Power Method for Sparse Eigenvalue Problems
• Augmented sparse principal component analysis for high dimensional data
• Statistical analysis of latent generalized correlation matrix estimation in transelliptical distribution

Cited by in corpus (14)

• Guaranteed Matrix Completion via Non-convex Factorization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• DSD: Dense-Sparse-Dense Training for Deep Neural Networks
• Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Sparse CCA: Adaptive Estimation and Computational Barriers
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Sparse PCA with Oracle Property
• Sparse PCA via Bipartite Matchings
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• Phase Transitions for High Dimensional Clustering and Related Problems
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Simultaneous Parameter Learning and Bi-Clustering for Multi-Response Models