An Exponential Lower Bound on the Complexity of Regularization Paths - Computer Science > LearningReportar como inadecuado




An Exponential Lower Bound on the Complexity of Regularization Paths - Computer Science > Learning - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: 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 singleparameter, as for example the Support Vector Machine SVM. Solution pathalgorithms do not only compute the solution for one particular value of theregularization parameter but the entire path of solutions, making the selectionof an optimal parameter much easier.It has been assumed that these piecewise linear solution paths have onlylinear complexity, i.e. linearly many bends. We prove that for the supportvector machine this complexity can be exponential in the number of trainingpoints in the worst case. More strongly, we construct a single instance of ninput points in d dimensions for an SVM such that at least \Theta2^{n-2} =\Theta2^d many distinct subsets of support vectors occur as theregularization parameter changes.



Autor: Bernd Gärtner, Martin Jaggi, Clément Maria

Fuente: https://arxiv.org/







Documentos relacionados