An Exponential Lower Bound on the Complexity of Regularization Paths
An Exponential Lower Bound on the Complexity of Regularization Paths
复制标题
正则化路径复杂度的指数下界
DOI：
10.20382/jocg.v3i1a9
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Clément Maria
中科院分区：
文献类型：
--
作者：
B. Gärtner;Martin Jaggi;Clément Maria
对于机器学习中的各种正则化优化问题，最近已经开发了计算整个解路径的算法。这些方法中的大多数是由单个参数参数化的二次规划，例如支持向量机（SVM）。解路径算法不仅计算正则化参数的一个特定值的解，而且计算整个解路径，使得最佳参数的选择更容易。
已经假设这些分段线性解路径仅具有线性复杂性，即线性地许多弯曲。我们证明了支持向量机的复杂性在最坏的情况下可以是训练点数量的指数。更强的是，我们为SVM构造了一个d维n个输入点的单个实例，使得至少\Theta（2^{n/2}）= \Theta（2^d）随着正则化参数的变化，出现了许多不同的支持向量子集。
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.
影响因子：
1.3
作者：
Giesen, Joachim;Jaggi, Martin;Laue, Soeren
通讯作者：
Laue, Soeren