Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
  We study efficient algorithms for Sparse PCA in standard statistical models
(spiked covariance in its Wishart form). Our goal is to achieve optimal
recovery guarantees while being resilient to small perturbations. Despite a
long history of prior works, including explicit studies of perturbation
resilience, the best known algorithmic guarantees for Sparse PCA are fragile
and break down under small adversarial perturbations.
  We observe a basic connection between perturbation resilience and
\emph{certifying algorithms} that are based on certificates of upper bounds on
sparse eigenvalues of random matrices. In contrast to other techniques, such
certifying algorithms, including the brute-force maximum likelihood estimator,
are automatically robust against small adversarial perturbation.
  We use this connection to obtain the first polynomial-time algorithms for
this problem that are resilient against additive adversarial perturbations by
obtaining new efficient certificates for upper bounds on sparse eigenvalues of
random matrices. Our algorithms are based either on basic semidefinite
programming or on its low-degree sum-of-squares strengthening depending on the
parameter regimes. Their guarantees either match or approach the best known
guarantees of \emph{fragile} algorithms in terms of sparsity of the unknown
vector, number of samples and the ambient dimension.
  To complement our algorithmic results, we prove rigorous lower bounds
matching the gap between fragile and robust polynomial-time algorithms in a
natural computational model based on low-degree polynomials (closely related to
the pseudo-calibration technique for sum-of-squares lower bounds) that is known
to capture the best known guarantees for related statistical estimation
problems. The combination of these results provides formal evidence of an
inherent price to pay to achieve robustness.
