Abstract
We present a near-optimal algorithm for properly learning convex polytopes inthe realizable PAC setting from data with a margin. Our first contribution isto identify distinct generalizations of the notion of {\em margin} fromhyperplanes to polytopes and to understand how they relate geometrically; thisresult may be of interest beyond the learning setting. Our novel learningalgorithm constructs a consistent polytope as an intersection of about $t \logt$ halfspaces in time polynomial in $t$ (where $t$ is the number of halfspacesforming an optimal polytope). This is an exponential improvement over the stateof the art [Arriaga and Vempala, 2006]. We also improve over thesuper-polynomial-in-$t$ algorithm of Klivans and Servedio [2008], whileachieving a better sample complexity. Finally, we provide the first nearlymatching hardness-of-approximation lower bound, whence our claim of nearoptimality.