NeurIPS 2018poster22 citations
Learning convex polytopes with margin
Lee-Ad Gottlieb, Eran Kaufman, Aryeh Kontorovich, Gabriel Nivasch
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.
BibTeX
@inproceedings{NEURIPS2018_22b1f2e0,
author = {Gottlieb, Lee-Ad and Kaufman, Eran and Kontorovich, Aryeh and Nivasch, Gabriel},
booktitle = {Advances in Neural Information Processing Systems},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Learning convex polytopes with margin},
url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/22b1f2e0983160db6f7bb9f62f4dbb39-Paper.pdf},
volume = {31},
year = {2018}
}