# Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time

arXiv: https://arxiv.org/abs/2311.01435 · HTML: https://mlsanity.com/paper/2311.01435/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 27 references that are in the map.
- First posted on arXiv 2 Nov 2023.

## Builds on (most cited first, 3 of 3)

- [Polynomial Time and Sample Complexity for Non-Gaussian Component Analysis: Spectral Methods](https://mlsanity.com/paper/1704.01041/) (2017)
- [Fourier PCA and Robust Tensor Decomposition](https://mlsanity.com/paper/1306.5825/) (2013)
- [Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error](https://mlsanity.com/paper/2302.12289/) (2023)

## Built on by (most cited first, 1 of 1)

- [Sum-of-squares lower bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2410.21426/) (2024)

## Abstract (arXiv)

We give a polynomial-time algorithm for learning high-dimensional halfspaces with margins in d-dimensional space to within desired TV distance when the ambient distribution is an unknown affine transformation of the d-fold product of an (unknown) symmetric one-dimensional logconcave distribution, and the halfspace is introduced by deleting at least an ε fraction of the data in one of the component distributions. Notably, our algorithm does not need labels and establishes the unique (and efficient) identifiability of the hidden halfspace under this distributional assumption. The sample and time complexity of the algorithm are polynomial in the dimension and 1/ε. The algorithm uses only the first two moments of suitable re-weightings of the empirical distribution, which we call contrastive moments; its analysis uses classical facts about generalized Dirichlet polynomials and relies crucially on a new monotonicity property of the moment ratio of truncations of logconcave distributions. Such algorithms, based only on first and second moments were suggested in earlier work, but hitherto eluded rigorous guarantees. Prior work addressed the special case when the underlying distribution is Gaussian via Non-Gaussian Component Analysis. We improve on this by providing polytime guarantees based on Total Variation (TV) distance, in place of existing moment-bound guarantees that can be super-polynomial. Our work is also the first to go beyond Gaussians in this setting.