Approximating Parameterized Convex Optimization Problems

作者：Giesen Joachim^*; Jaggi Martin; Laue Soeren

来源：ACM Transactions on Algorithms, 2012, 9(1): 10.

DOI：10.1145/2390176.2390186

• Algorithms
• Theory
• Computational geometry
• convex optimization
• machine learning

We consider parameterized convex optimization problems over the unit simplex, that depend on one parameter. We provide a simple and efficient scheme for maintaining an epsilon-approximate solution (and a corresponding epsilon-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.

• 出版日期2012-12