Adaptive Forward-Backward Greedy Algorithm for Sparse Learning with Linear Models
Consider linear prediction models where the target function is a sparse linear combination of a set of basis functions. We are interested in the problem of identifying those basis functions with non-zero coefficients and reconstructing the target function from noisy observations. Two heuristics that are widely used in practice are forward and backward greedy algorithms. First, we show that neither idea is adequate. Second, we propose a novel combination that is based on the forward greedy algorithm but takes backward steps adaptively whenever beneficial. We prove strong theoretical results showing that this procedure is effective in learning sparse representations. Experimental results support our theory.
Code (0)
등록된 구현이 없습니다.
Tasks
Sparse LearningSimilar Papers 제목 키워드 기반
Nonparametric Greedy Algorithms for the Sparse Learning Problem
This paper studies the forward greedy strategy in sparse nonparametric regression. For additive models, we propose an algorithm called additive forward regression; for general multivariate regression, we propose an algor…
Additive modelsregressionSparse LearningVariable SelectionForward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint
We consider forward-backward greedy algorithms for solving sparse feature selection problems with general convex smooth functions. A state-of-the-art greedy method, the Forward-Backward greedy algorithm (FoBa-obj) requir…
Activity Recognitionfeature selectionSparse Optimization on General Atomic Sets: Greedy and Forward-Backward Algorithms
We consider the problem of sparse atomic optimization, where the notion of "sparsity" is generalized to meaning some linear combination of few atoms. The definition of atomic set is very broad; popular examples include t…
A Forward Backward Greedy approach for Sparse Multiscale Learning
Multiscale Models are known to be successful in uncovering and analyzing the structures in data at different resolutions. In the current work we propose a feature driven Reproducing Kernel Hilbert space (RKHS), for which…
Homotopy based algorithms for $\ell_0$-regularized least-squares
Sparse signal restoration is usually formulated as the minimization of a quadratic cost function $\|y-Ax\|_2^2$, where A is a dictionary and x is an unknown sparse vector. It is well-known that imposing an $\ell_0$ const…
Heuristic Search