1. Approximating parameterized convex optimization problems
- Author
-
Sören Laue, Martin Jaggi, Joachim Giesen, de Berg, Mark, Meyer, Ulrich, Pandu Rangan, C., Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, and Nierstrasz, Oscar
- Subjects
Convex analysis ,Mathematical optimization ,Simplex ,Optimization problem ,Proper convex function ,Linear matrix inequality ,Parameterized complexity ,Subderivative ,Vector optimization ,Mathematics (miscellaneous) ,Convex optimization ,Proximal gradient methods for learning ,Convex combination ,Conic optimization ,Mathematics - Abstract
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 e-approximate solution (and a corresponding e-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.
- Published
- 2012