Approximating Parameterized Convex Optimization Problems.

We extend Clarkson's framework by considering parameterized convex optimization problems over the unit simplex, that depend on one parameter. We provide a simple and efficient scheme for maintaining an ε-approximate solution (and a corresponding ε-coreset) along the entire parameter path. We prove correctness and optimality of the method. Practically relevant instances of the abstract parameterized optimization problem are for example regularization paths of support vector machines, multiple kernel learning, and minimum enclosing balls of moving points. © 2010 Springer-Verlag.

Published in:
Proceedings of the 18th Annual European Symposium, part I, 524-535
Presented at:
European Symposia on Algorithms (ESA) 2010, Liverpool, UK, September 6-8, 2010

 Record created 2017-06-21, last modified 2018-09-13

Rate this document:

Rate this document:
(Not yet reviewed)