Boosting with Structural Sparsity: A Differential Inclusion Approach
Preprint
Abstract
Boosting as gradient descent algorithms is one popular method in machine learning. In this paper a novel Boosting-type algorithm is proposed based on restricted gradient descent with structural sparsity control whose underlying dynamics are governed by differential inclusions. In particular, we present an iterative regularization path with structural sparsity where the parameter is sparse under some linear transforms, based on variable splitting and the Linearized Bregman Iteration. Hence it is called \emph{Split LBI}. Despite its simplicity, Split LBI outperforms the popular generalized Lasso in both theory and experiments. A theory of path consistency is presented that equipped with a proper early stopping, Split LBI may achieve model selection consistency under a family of Irrepresentable Conditions which can be weaker than the necessary and sufficient condition for generalized Lasso. Furthermore, some $\ell_2$ error bounds are also given at the minimax optimal rates. The utility and benefit of the algorithm are illustrated by several applications including image denoising, partial order ranking of sport teams, and world university grouping with crowdsourced ranking data.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- An Augmented ADMM Algorithm With Application to the Generalized Lasso ProblemJournal of Computational and Graphical Statistics, 2017
- Sparse recovery via differential inclusionsApplied and Computational Harmonic Analysis, 2016
- Fast and Flexible ADMM Algorithms for Trend FilteringJournal of Computational and Graphical Statistics, 2016
- Efficient Implementations of the Generalized Lasso Dual Path AlgorithmJournal of Computational and Graphical Statistics, 2016
- Split Bregman method for large scale fused LassoComputational Statistics & Data Analysis, 2011
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)IEEE Transactions on Information Theory, 2009
- On Early Stopping in Gradient Descent LearningConstructive Approximation, 2007
- Receiver operating characteristics curves and related decision measures: A tutorialChemometrics and Intelligent Laboratory Systems, 2006
- Greed is Good: Algorithmic Results for Sparse ApproximationIEEE Transactions on Information Theory, 2004
- Nonlinear total variation based noise removal algorithmsPhysica D: Nonlinear Phenomena, 1992