An Exponential Lower Bound on the Complexity of Regularization Paths

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

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 quadra…