Timezone: »
Sparse Principal Component Analysis (SPCA) and Sparse Linear Regression (SLR) have a wide range of applications and have attracted a tremendous amount of attention in the last two decades as canonical examples of statistical problems in high dimension. A variety of algorithms have been proposed for both SPCA and SLR, but an explicit connection between the two had not been made. We show how to efficiently transform a black-box solver for SLR into an algorithm for SPCA: assuming the SLR solver satisfies prediction error guarantees achieved by existing efficient algorithms such as those based on the Lasso, the SPCA algorithm derived from it achieves near state of the art guarantees for testing and for support recovery for the single spiked covariance model as obtained by the current best polynomial-time algorithms. Our reduction not only highlights the inherent similarity between the two problems, but also, from a practical standpoint, allows one to obtain a collection of algorithms for SPCA directly from known algorithms for SLR. We provide experimental results on simulated data comparing our proposed framework to other algorithms for SPCA.
Author Information
Guy Bresler (MIT)
Sung Min Park (MIT)
Madalina Persu (Two Sigma Investments, MIT)
More from the Same Authors
-
2022 : A Unified Framework for Comparing Learning Algorithms »
Harshay Shah · Sung Min Park · Andrew Ilyas · Aleksander Madry -
2023 Workshop: Attributing Model Behavior at Scale (ATTRIB) »
Tolga Bolukbasi · Logan Engstrom · Kelvin Guu · Andrew Ilyas · Sung Min Park · Ellie Pavlick · Anders Søgaard -
2021 Poster: The staircase property: How hierarchical structure can guide deep learning »
Emmanuel Abbe · Enric Boix-Adsera · Matthew S Brennan · Guy Bresler · Dheeraj Nagaraj -
2020 Poster: Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth »
Guy Bresler · Dheeraj Nagaraj -
2020 Poster: Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms »
Dheeraj Nagaraj · Xian Wu · Guy Bresler · Prateek Jain · Praneeth Netrapalli -
2020 Spotlight: Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms »
Dheeraj Nagaraj · Xian Wu · Guy Bresler · Prateek Jain · Praneeth Netrapalli -
2020 Poster: Learning Restricted Boltzmann Machines with Sparse Latent Variables »
Guy Bresler · Rares-Darius Buhai -
2019 Poster: Sample Efficient Active Learning of Causal Trees »
Kristjan Greenewald · Dmitriy Katz · Karthikeyan Shanmugam · Sara Magliacane · Murat Kocaoglu · Enric Boix-Adsera · Guy Bresler -
2017 : Community Detection and Invariance to Distribution »
Guy Bresler