Before revision:  Our first contribution is to identify distinct generalizations of the notion of margin from hyperplanes to polytopes and to understand how they relate geometrically; this result may be of interest beyond the learning setting. Our novel learning algorithm constructs a consistent polytope as an intersection of about t \log t halfspaces  in time polynomial in t (where t is the number of halfspaces forming an optimal polytope).
After revision:  Our first contribution is to identify distinct generalizations of the notion of margin learning algorithm constructs a consistent polytope as an intersection of about t \log t halfspaces in time polynomial in t (where t is the number of halfspaces forming an optimal polytope).