Timezone: »

 
Poster
Learning convex polytopes with margin
Lee-Ad Gottlieb · Eran Kaufman · Aryeh Kontorovich · Gabriel Nivasch

Thu Dec 06 02:00 PM -- 04:00 PM (PST) @ Room 210 #42
in Thu Poster Session B »

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.

Keywords: Learning Theory · Algorithms
[ Paper] 

Author Information

Lee-Ad Gottlieb (Ariel University)
Eran Kaufman (Ariel University)
Aryeh Kontorovich (Ben Gurion University)
Gabriel Nivasch (Ariel University)

More from the Same Authors