  We present an improved algorithm for {\em quasi-properly} learning convex
polyhedra in the realizable PAC setting from data with a margin. Our learning
algorithm constructs a consistent polyhedron as an intersection of about $t
\log t$ halfspaces with constant-size margins in time polynomial in $t$ (where
$t$ is the number of halfspaces forming an optimal polyhedron). We also
identify distinct generalizations of the notion of margin from hyperplanes to
polyhedra and investigate how they relate geometrically; this result may have
ramifications beyond the learning setting.
