Coresets for polytope distance
Authors:
Open Access
- 8 June 2009
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 33-42
Abstract
Following recent work of Clarkson, we translate the coreset framework to the problems of nding the point closest to the origin inside a polytope, nding 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 sized(1 +o(1))E = 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 algo- rithms for polytope distance, and generalize both the algo- rithm and the proof to the two polytope case. Interestingly, our coreset bounds also imply that we can for the rst time prove matching upper and lower bounds for the sparsity of Perceptron and SVM solutions.Keywords
This publication has 17 references indexed in Scilit:
- Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoidsOptimization Methods and Software, 2008
- On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoidsDiscrete Applied Mathematics, 2007
- Generalized Core Vector MachinesIEEE Transactions on Neural Networks, 2006
- A geometric approach to Support Vector Machine (SVM) classificationIEEE Transactions on Neural Networks, 2006
- Approximating extent measures of pointsJournal of the ACM, 2004
- A fast iterative nearest point algorithm for support vector machine classifier designIEEE Transactions on Neural Networks, 2000
- Finding the Point of a Polyhedron Closest to the OriginSIAM Journal on Control, 1974
- An Iterative Procedure for Computing the Minimum of a Quadratic Form on a Convex SetSIAM Journal on Control, 1966
- The perceptron: A probabilistic model for information storage and organization in the brain.Psychological Review, 1958
- An algorithm for quadratic programmingNaval Research Logistics Quarterly, 1956