Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time
Xinyuan Cao Santosh S. Vempala
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 $\epsilon$ 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/\epsilon$.
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.