Learning Convex Polyhedra With Margin

DOI10.1109/TIT.2021.3134898MaRDI QIDQ5080039zbMATH OpenOpenAlexFDO

Authors Eran Kaufman, Gabriel Nivasch, Lee-Ad Gottlieb, Aryeh Kontorovich

Publication date 30 May 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.09719

zbMATH Keywords

learning algorithmquasi-properly learning convex polyhedra

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Abstract: 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 $tlogt$ 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.

Cited in

(1)

• An improved uniform convergence bound with fat-shattering dimension

This page was built for publication: Learning Convex Polyhedra With Margin

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080039)