# Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint

arXiv: https://arxiv.org/abs/1401.0086 · HTML: https://mlsanity.com/paper/1401.0086/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Dec 2013.

## Built on by (most cited first, 4 of 4)

- [Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families](https://mlsanity.com/paper/2110.04719/) (2021)
- [Fast Feature Selection with Fairness Constraints](https://mlsanity.com/paper/2202.13718/) (2022)
- [skscope: Fast Sparsity-Constrained Optimization in Python](https://mlsanity.com/paper/2403.18540/) (2024)
- [Sparsity-Constraint Optimization via Splicing Iteration](https://mlsanity.com/paper/2406.12017/) (2024)

## Abstract (arXiv)

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) requires to solve a large number of optimization problems, thus it is not scalable for large-size problems. The FoBa-gdt algorithm, which uses the gradient information for feature selection at each forward iteration, significantly improves the efficiency of FoBa-obj. In this paper, we systematically analyze the theoretical properties of both forward-backward greedy algorithms. Our main contributions are: 1) We derive better theoretical bounds than existing analyses regarding FoBa-obj for general smooth convex functions; 2) We show that FoBa-gdt achieves the same theoretical performance as FoBa-obj under the same condition: restricted strong convexity condition. Our new bounds are consistent with the bounds of a special case (least squares) and fills a previously existing theoretical gap for general convex smooth functions; 3) We show that the restricted strong convexity condition is satisfied if the number of independent samples is more than barklog d where bark is the sparsity number and d is the dimension of the variable; 4) We apply FoBa-gdt (with the conditional random field objective) to the sensor selection problem for human indoor activity recognition and our results show that FoBa-gdt outperforms other methods (including the ones based on forward greedy selection and L1-regularization).