资源分类
》 资源 》论文》Complexity Analysis of the Lasso Regularization Path

Complexity Analysis of the Lasso Regularization Path

2020-02-28 | |  40 |   38 |   0

Abstract

The regularization path of the Lasso can be shown to be piecewise linear, making it possible to “follow” and explicitly compute the entire path. We analyze in this paper this popular strategy, and prove that its worst case complexity is exponential in the number of variables. We then oppose this pessimistic result to an (optimistic) approximate analysis: We show ? that an approximate path with at most 图片.png linear segments can always be obtained, where every point on the path is guaranteed to be optimal up to a relative ε-duality gap. We complete our theoretical analysis with a practical algorithm to compute these approximate paths.

上一篇：Regularizers versus Losses for Nonlinear Dimensionality Reduction

下一篇：Fast Computation of Subpath Kernel for Trees

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...