An Exponential Lower Bound on the Complexity of Regularization Paths

By Bernd Gärtner, Martin Jaggi, Clément Maria. 2009

38 citations recorded by the source corpus.

For a variety of regularized optimization problems in machine learning, algorithms computing the entire solution path have been developed recently. Most of these methods are quadratic programs that are parameterized by a single parameter, as for example the Support Vector Machine (SVM). Solution path algorithms do not only compute the solution for one particular value of the regularization parameter but the entire path of solutions, making the selection of an optimal parameter much easier. It has been assumed that these piecewise linear solution paths have only linear complexity, i.e. linearly many bends. We prove that for the support vector machine this complexity can be exponential in the number of training points in the worst case. More strongly, we construct a single instance of n input points in d dimensions for an SVM such that at least \Theta(2^{n/2}) = \Theta(2^d) many distinct subsets of support vectors occur as the regularization parameter changes.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Scaling & Learning Theory

Citations in the corpus

Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, methodology): “In addition, Gärtner et al. (2012) show that, in the worst case, the regularization path for binary SVM contains an exponential number of break points. Although the exact path following methods for SVM are still developed (Sentelle et al., 2015), approximate methods might be more suited for practica”
Suboptimal Solution Path Algorithm for Support Vector Machine (2011, methodology): “Another diﬃculty is in starting the solution path algorithm from an approximated solution, for example obtained by SMO, because it does not satisfy the strict optimality requirement.”
Approximating Concavely Parameterized Optimization Problems (2012, methodology): “Finally, we provide an implementation of the oracle for soft-margin support vector machines, and a parameterized semi-definite program for matrix completion.”
An Equivalence between the Lasso and Support Vector Machines (2013, result): “This is inspired by a similar result by [13] which holds for the `1-SVM.”