Reviews: Learning convex polytopes with margin

The paper considers the problem of PAC learning of fat convex polytopes in the realizable case. This hypothesis class is given by intersections of t fat hyperplanes, i.e., hyperplanes with margin gamma. Using standard results, the authors derive that the VC dimension of this class is quadratic in the inverse margin size and thus that the sample complexity is polylogerithmic in this quantity. As their main result, they provide two algorithms for finding with high probability a consistent fat polytope: one with exponential runtime in t and one polynomial greedy algorithm that, however, only guarantees to find a (t log n)-polytope. Complementary, the paper states two hardness of approximation results: one for finding an approximately consistent fat hyperplane, i.e., one with the minimum number of negative points on wrong side (and all positive correctly classified), and one for finding a consistent fat polytope with the minimum number of hyperplanes. Finally, the authors also show how their results relate to the alternative class of polytopes that separate points outside of their gamma-envelope (area with Euclidean distance less or equal to gamma from the polytope boundary).