Learning Low-Density Separators
  We define a novel, basic, unsupervised learning problem - learning the lowest
density homogeneous hyperplane separator of an unknown probability
distribution. This task is relevant to several problems in machine learning,
such as semi-supervised learning and clustering stability. We investigate the
question of existence of a universally consistent algorithm for this problem.
We propose two natural learning paradigms and prove that, on input unlabeled
random samples generated by any member of a rich family of distributions, they
are guaranteed to converge to the optimal separator for that distribution. We
complement this result by showing that no learning algorithm for our task can
achieve uniform learning rates (that are independent of the data generating
distribution).
