Learning convex polytopes with margin
Authors: Lee-Ad Gottlieb, Eran Kaufman, Aryeh Kontorovich, Gabriel Nivasch
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present an 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. |
| Researcher Affiliation | Academia | Lee-Ad Gottlieb Ariel University leead@ariel.ac.il Eran Kaufman Ariel University erankfmn@gmail.com Aryeh Kontorovich Ben-Gurion University karyeh@bgu.sc.il Gabriel Nivasch Ariel University gabrieln@ariel.ac.il |
| Pseudocode | No | The paper describes algorithms in text (e.g., in Section 3.2 'Algorithms' and Theorem 7 proof) but does not provide structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not describe experiments with datasets. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical validation on datasets. |
| Hardware Specification | No | This is a theoretical paper and does not describe specific hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not specify software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup with specific hyperparameters or training configurations. |