Solution Path Complexity
11 / 2010
en | de
Home
Icon

Finally, we rewrote that thing in more details, and show that for SVMs, essentially all (exponentially many) subsets of support vectors can indeed occur, as the regularization parameter changes.

This also shows exponential worst-case complexity for the solution path of parametric quadratic programs:

B. Gärtner, M. Jaggi and C. Maria.
An Exponential Lower Bound on the Complexity of Regularization Paths.
Journal of Computational Geometry, 2012

If you are not scared by the potentially large complexity in the worst case, you can also try that solution path algorithm.