List Decodable Subspace Recovery

Learning from data in the presence of outliers is a fundamental problem in statistics. In this work, we study robust statistics in the presence of overwhelming outliers for the fundamental problem of subspace recovery. Given a dataset where an $\alpha$ fraction (less than half) of the data is distributed uniformly in an unknown $k$ dimensional subspace in $d$ dimensions, and with no additional assumptions on the remaining data, the goal is to recover a succinct list of $O(\frac{1}{\alpha})$ subspaces one of which is nontrivially correlated with the planted subspace. We provide the first polynomial time algorithm for the 'list decodable subspace recovery' problem, and subsume it under a more general framework of list decoding over distributions that are "certifiably resilient" capturing state of the art results for list decodable mean estimation and regression.

• Publication year

  2020

• Venue

  Annual Conference Computational Learning Theory

• Publication date

  2020-02-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2002.03004
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• List-Decodable Subspace Recovery via Sum-of-Squares

  2020cited by this paper
• Quadratic Optimization Problems

  2020cited by this paper
• Recent Advances in Algorithmic High-Dimensional Robust Statistics

  2019cited by this paper
• Robust Subspace Recovery with Adversarial Outliers

  2019cited by this paper
• List Decodable Learning via Sum of Squares

  2019influential reference
• List-Decodable Linear Regression

  2019influential reference
• Smoothed Analysis in Unsupervised Learning via Decoupling

  2018cited by this paper
• An Overview of Robust Subspace Recovery

  2018cited by this paper
• Robust Statistics

  2018cited by this paper
• Better Agnostic Clustering Via Relaxed Tensor Norms

  2017cited by this paper
• List-decodable robust mean estimation and learning mixtures of spherical gaussians

  2017cited by this paper
• Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems

  2017influential reference
• Certified Defenses for Data Poisoning Attacks

  2017cited by this paper
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery

  2017cited by this paper
• Mixture models, robustness, and sum of squares proofs

  2017influential reference
• Outlier-robust moment-estimation via sum-of-squares

  2017cited by this paper
• Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers

  2017cited by this paper
• Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction

  2016cited by this paper
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs

  2016cited by this paper
• Learning from untrusted data

  2016influential reference
• Robust Subspace Clustering

  2013cited by this paper
• Algorithms and Hardness for Robust Subspace Recovery

  2012cited by this paper
• Sparse Subspace Clustering: Algorithm, Theory, and Applications

  2012influential reference
• Subspace clustering

  2012cited by this paper
• GPCA with denoising: A moments-based convex approach

  2010cited by this paper
• A discriminative framework for clustering via similarity functions

  2008cited by this paper
• Segmentation of Multivariate Mixed Data via Lossy Data Coding and Compression

  2007cited by this paper
• Generalized principal component analysis (GPCA)

  2005cited by this paper
• k-means projective clustering

  2004influential reference
• Nearest q-Flat to m Points

  2000cited by this paper
• Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization

  2000influential reference
• Global Optimization with Polynomials and the Problem of Moments

  2000cited by this paper
• k-Plane Clustering

  2000cited by this paper
• Squared Functional Systems and Optimization Problems

  2000cited by this paper
• Probabilistic Principal Component Analysis

  1999cited by this paper
• The ellipsoid method and its consequences in combinatorial optimization

  1981cited by this paper

• Efficient Certificates of Anti-Concentration Beyond Gaussians

  2024cites this paper
• Robust Mixture Learning when Outliers Overwhelm Small Groups

  2024cites this paper
• A New Approach to Learning Linear Dynamical Systems

  2023cites this paper
• A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm

  2023cites this paper
• A Combinatorial Approach to Robust PCA

  2023cites this paper
• Algorithms Approaching the Threshold for Semi-random Planted Clique

  2022cites this paper
• List-Decodable Sparse Mean Estimation

  2022cites this paper
• List-decodable covariance estimation

  2022cites this paper
• List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering

  2022cites this paper
• Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity

  2022cites this paper
• A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity

  2022cites this paper
• Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally

  2021cites this paper
• Semi-verified Learning from the Crowd with Pairwise Comparisons

  2021cites this paper
• A stress-free sum-of-squares lower bound for coloring

  2021cites this paper
• Privately Learning Mixtures of Axis-Aligned Gaussians

  2021cites this paper
• Semi-Verified PAC Learning from the Crowd

  2021cites this paper
• Statistical Query Lower Bounds for List-Decodable Linear Regression

  2021cites this paper
• List Decodable Mean Estimation in Nearly Linear Time

  2020cites this paper
• List-Decodable Mean Estimation via Iterative Multi-Filtering

  2020cites this paper
• Robust linear regression: optimal rates in polynomial time

  2020cites this paper
• Tight List-Sizes for Oblivious AVCs under Constraints

  2020cites this paper
• Learning a mixture of two subspaces over finite fields

  2020cites this paper
• List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time

  2020influential citation
• Robustly learning mixtures of k arbitrary Gaussians

  2020cites this paper
• MIT Open Access Articles A New Approach to Learning Linear Dynamical Systems

  year unknowncites this paper