Coresets for polytope distance Export

@inproceedings{citeulike:5280902, abstract = {Following recent work of Clarkson, we translate the coreset framework to the problems of finding the point closest to the origin inside a polytope, finding the shortest distance between two polytopes, Perceptrons, and soft- as well as hard-margin Support Vector Machines (SVM). We prove asymptotically matching upper and lower bounds on the size of coresets, stating that \&\#181;-coresets of size (1+o(1)) E*/\&\#181; do always exist as \&\#181;-0, and that this is best possible. The crucial quantity E* is what we call the excentricity of a polytope, or a pair of polytopes. Additionally, we prove linear convergence speed of Gilbert's algorithm, one of the earliest known approximation algorithms for polytope distance, and generalize both the algorithm and the proof to the two polytope case. Interestingly, our coreset bounds also imply that we can for the first time prove matching upper and lower bounds for the sparsity of Perceptron and SVM solutions.}, address = {New York, NY, USA}, author = {G\"{a}rtner, Bernd and Jaggi, Martin}, booktitle = {SCG '09: Proceedings of the 25th annual symposium on Computational geometry}, citeulike-article-id = {5280902}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1542362.1542370}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1542362.1542370}, doi = {10.1145/1542362.1542370}, isbn = {978-1-60558-501-7}, keywords = {latent-semantic-kernels-etc}, location = {Aarhus, Denmark}, pages = {33--42}, posted-at = {2009-10-27 05:38:01}, priority = {2}, publisher = {ACM}, title = {Coresets for polytope distance}, url = {http://dx.doi.org/10.1145/1542362.1542370}, year = {2009} }

TY - CONF ID - citeulike:5280902 L3 - citeulike-article-id:5280902 N2 - Following recent work of Clarkson, we translate the coreset framework to the problems of finding the point closest to the origin inside a polytope, finding the shortest distance between two polytopes, Perceptrons, and soft- as well as hard-margin Support Vector Machines (SVM). We prove asymptotically matching upper and lower bounds on the size of coresets, stating that µ-coresets of size (1+o(1)) E*/µ do always exist as µ-0, and that this is best possible. The crucial quantity E* is what we call the excentricity of a polytope, or a pair of polytopes. Additionally, we prove linear convergence speed of Gilbert's algorithm, one of the earliest known approximation algorithms for polytope distance, and generalize both the algorithm and the proof to the two polytope case. Interestingly, our coreset bounds also imply that we can for the first time prove matching upper and lower bounds for the sparsity of Perceptron and SVM solutions. CY - Aarhus, Denmark SN - 978-1-60558-501-7 AD - New York, NY, USA EP - 42 TI - Coresets for polytope distance PB - ACM T2 - SCG '09: Proceedings of the 25th annual symposium on Computational geometry SP - 33 KW - latent-semantic-kernels-etc AU - Gärtner, Bernd AU - Jaggi, Martin PY - 2009/// UR - http://dx.doi.org/10.1145/1542362.1542370 ER -