Learning Convex Polytopes with Margin
Abstract
We present improved algorithm for properly learning convex polytopes in the realizable PAC setting from data with a margin. Our learning algorithm constructs a consistent polytope as an intersection of about t log t halfspaces with margins in time polynomial in t (where t is the number of halfspaces forming an optimal polytope). We also identify distinct generalizations of the notion of margin from hyperplanes to polytopes and investigate how they relate geometrically; this result may be of interest beyond the learning setting.
Cite
Text
Gottlieb et al. "Learning Convex Polytopes with Margin." Neural Information Processing Systems, 2018.Markdown
[Gottlieb et al. "Learning Convex Polytopes with Margin." Neural Information Processing Systems, 2018.](https://mlanthology.org/neurips/2018/gottlieb2018neurips-learning/)BibTeX
@inproceedings{gottlieb2018neurips-learning,
title = {{Learning Convex Polytopes with Margin}},
author = {Gottlieb, Lee-Ad and Kaufman, Eran and Kontorovich, Aryeh and Nivasch, Gabriel},
booktitle = {Neural Information Processing Systems},
year = {2018},
pages = {5706-5716},
url = {https://mlanthology.org/neurips/2018/gottlieb2018neurips-learning/}
}