Forward-Backward Greedy Selection for Sparse Learning

This direction is merged into another direction: sequential floating search. Its last version stays readable and citable here.

Version 1 of 112 papers19 conceptsfrozen 2026-10-04

In high-dimensional data analysis, we often search for a small subset of features that explains the most variance—a property known as sparsity. The simplest way to find this subset is a "greedy" approach: start with an empty set and keep adding the single best feature until you reach a limit.

However, this simple forward selection has a fundamental flaw: it is short-sighted. A feature that looks like the best choice in step one might become completely redundant by step ten because of how it interacts with other variables. Traditional greedy algorithms are "nested," meaning once a feature is chosen, it is locked in forever.

Forward-backward greedy algorithms break this nesting by adding an "undo" button. By interleaving forward steps (adding features) with backward steps (pruning features), these methods can correct early mistakes and find more accurate, stable, and parsimonious models.

The Problem of Greedy Myopia

When we select features one by one, we are essentially navigating a massive search space of possible combinations. Simple Sequential Forward Selection (SFS) is computationally efficient but often gets trapped in local optima.

As Franz Pernkopf notes in Bayesian Network Classifiers Versus k-NN Classifier Using Sequential Feature Selection, the "nesting problem" occurs because SFS cannot account for the evolving dependencies between features. A variable that was highly informative on its own might provide no new information once three other related variables are added to the model.

The Floating Mechanism

To solve this, researchers developed "floating" search methods. Instead of a one-way street, the algorithm becomes bidirectional.

In Selection of speaker independent feature for a speaker verification system, Josef Kittler and colleagues describe a $(l, r)$ search strategy: add $l$ features and then take away $r$ features. This flexibility allows the algorithm to "float" the size of the feature subset, re-evaluating the contribution of every included variable at each step.

Similarly, Sequential Forward Floating Selection (SFFS) adds a feature and then immediately checks if any previously selected features have become redundant. As Juanying Xie demonstrates in A Novel Hybrid Feature Selection Method Based on IFSFFS and SVM for the Diagnosis of Erythemato-Squamous Diseases, this bidirectional flexibility is what allows a model to escape local optima and find a truly minimal, highly accurate feature set.

Adaptive Pruning and Consistency

In the late 2000s and early 2010s, this intuition was formalized into the "Forward-Backward" (FoBa) framework. The key innovation here is an adaptive backward step.

In Adaptive Forward-Backward Greedy Algorithm for Sparse Learning with Linear Models, Tong Zhang showed that by including a pruning phase that removes features if their removal results in a negligible increase in loss, the algorithm achieves much stronger theoretical guarantees. This approach is often more robust than standard $L_1$ regularization (the Lasso) because it directly optimizes for sparsity rather than using a convex proxy.

Ali Jalali and sujay sanghavi further refined this in A New Greedy Algorithm for Multiple Sparse Regression, arguing that the backward step is essential for "support recovery"—the ability of the algorithm to find the exact set of "true" features that generated the data. Without the backward step, a single wrong choice in an early iteration can permanently contaminate the model.

Scaling to High Dimensions

A common critique of bidirectional search is that it might be slow. However, recent work has shown that forward-backward methods can actually be faster than their one-way counterparts.

Ji Liu and Ryohei Fujimaki introduced FoBa-gdt in Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint. By using gradient information to make selection and pruning decisions rather than solving a full optimization problem at every step, they achieved 10x speedups while maintaining accuracy.

This efficiency makes the approach viable for massive datasets, such as:

By treating feature selection as a dynamic, reversible process rather than a one-shot sequence of decisions, forward-backward algorithms provide a robust bridge between simple greedy heuristics and complex global optimization.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_forward_backward_greedy_selection_for_sp_6f18bd72,
  title = {Forward-Backward Greedy Selection for Sparse Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/forward-backward-greedy-selection-for-sparse-learning/rdr_6f18bd72d441468ab5ee84f4e6578949},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_forward_backward_greedy_selection_for_sp_6f18bd72_v1,
  title = {Forward-Backward Greedy Selection for Sparse Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/forward-backward-greedy-selection-for-sparse-learning/rdr_6f18bd72d441468ab5ee84f4e6578949/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}