A. R. Klivans, P. M. Long and A. K. Tang. Baum's
Algorithm Learns Intersections of Halfspaces with respect to
Log-Concave Distributions. RANDOM'09.
Abstract
In 1990, E. Baum gave an elegant polynomial-time algorithm for
learning the intersection of two origin-centered halfspaces with
respect to any symmetric distribution. Here we prove that his
algorithm also succeeds with respect to any mean zero distribution
with a log-concave density (a broad class of distributions that
need not be symmetric). As far as we are aware, prior to this work, it
was not known how to efficiently learn any class of intersections of
halfspaces with respect to log-concave distributions.
The key to our proof is a ``Brunn-Minkowski'' inequality for
log-concave densities that may be of independent interest.