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.

通过对未知对称一维对数凹分布的 d 维空间的 d 倍积的未知仿射变换的环境分布内带有一定间距的高维半空间的多项式时间学习算法，从一个组分分布的数据中删除至少一个 ε 分数的数据引入了半空间。值得注意的是，我们的算法不需要标签，并在这种分布假设下确立了隐藏半空间的独特性（以及高效性）。该算法的样本和时间复杂度在维度和 1/ε 上是多项式的。该算法只使用经验分布的适当重新加权的前两个矩，我们称之为对比矩；其分析使用了关于广义狄利克雷多项式的经典事实，并且关键地依赖于对对数凹分布截断的矩比的新的单调性属性。此前的研究处理了当底层分布是通过非高斯成分分析来进行的非高斯分布的特殊情况。我们通过提供基于总变分距离而不是现有的可以是超多项式的矩边界保证，改进了这一点。我们的工作也是在这个设置中首次超越高斯分布。