Abstract

We present an improved algorithm for properly learning convex polytopes inthe realizable PAC setting from data with a margin. Our learning algorithmconstructs a consistent polytope as an intersection of about $t \log t$halfspaces with margins in time polynomial in $t$ (where $t$ is the number ofhalfspaces forming an optimal polytope). We also identify distinct generalizations of the notion of margin fromhyperplanes to polytopes and investigate how they relate geometrically; thisresult may be of interest beyond the learning setting.

 

Quick Read (beta)