AN EXPONENTIAL LOWER BOUND ON THE COMPLEXITY OF REGULARIZATION PATHS

DOI10.20382/JOCG.V3I1A9MaRDI QIDQ2968091zbMATH OpenOpenAlexFDO

Authors Martin Jaggi, Clément Maria, B. Gärtner

Publication date 9 March 2017

Full work available at URL https://arxiv.org/abs/0903.4817

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Learning and adaptive systems in artificial intelligence (68T05) Quadratic programming (90C20)

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 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.

Recommendations

• On the structure of regularization paths for piecewise differentiable regularization terms
• Exact Regularization of Convex Programs
• Gradient methods with regularization for constrained optimization problems and their complexity estimates
• Sample Complexity and Minimax Properties of Exponentially Stable Regularized Estimators
• scientific article; zbMATH DE number 4046973
• Convergence Properties of an Objective-Function-Free Optimization Regularization Algorithm, Including an \(\boldsymbol{\mathcal{O}(\epsilon^{-3/2})}\) Complexity Bound
• On the complexity of solving feasibility problems with regularized models
• <inline-formula> <tex-math notation="LaTeX">$\ell _{p}$ </tex-math></inline-formula>-Regularized Least Squares <inline-formula> <tex-math notation="LaTeX">$(0&lt;p&lt;1)$ </tex-math></inline-formula>
• On Regularized Least Norm Problems
• A new complexity bound for the least-squares problem

Cited in

(5)

• LASSO for streaming data with adaptative filtering
• Moser's shadow problem
• On the structure of regularization paths for piecewise differentiable regularization terms
• Root-finding approaches for computing conformal prediction set
• Zero order algorithm for decentralized optimization problems

This page was built for publication: AN EXPONENTIAL LOWER BOUND ON THE COMPLEXITY OF REGULARIZATION PATHS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2968091)