Bidirectional Greedy Selection for Sparse Learning

26 concepts21 papers1 proposal

When building sparse models, the ideal goal is to find the smallest subset of features that maximizes predictive power. In a perfect world, we would evaluate every possible combination of features. In reality, this combinatorial explosion is NP-hard, forcing us to rely on greedy heuristics like Forward Selection or Orthogonal Matching Pursuit.

Standard greedy methods are monotonic: they make a series of one-way decisions. Forward selection adds the single best feature at each step and locks it in forever. Backward elimination starts with everything and systematically drops variables. While computationally efficient, this one-way constraint introduces a fundamental flaw: short-sightedness.

As Franz Pernkopf notes in Bayesian Network Classifiers Versus k-NN Classifier Using Sequential Feature Selection, simple sequential methods suffer from the nesting problem. A feature that looks incredibly informative at step 1 might become completely redundant by step 5 once other correlated variables enter the mix. Conversely, a pair of features might be powerful together but useless individually, meaning a forward-only search will pass them over.

Because monotonic algorithms cannot undo past choices, they easily get trapped in suboptimal configurations. As Xiaoyi Dong et al. observe in the context of adversarial optimization in GreedyFool: Distortion-Aware Sparse Adversarial Attack, without a secondary process to re-evaluate and remove unnecessary modifications, greedy choices ultimately yield models that are far less sparse and robust than they could be.

The Non-Monotonic Solution: Adding an "Undo" Button

Bidirectional greedy selection fixes this short-sightedness by introducing a backward pruning step into the forward search loop. Instead of treating feature selection as a one-way street, it treats the objective function as a non-monotonic function of the feature set size.

[Empty Set] ──(Forward Step: Add Feature)──> [Feature Set]
     ▲                                              │
     │                                              ▼
     └──────(Backward Step: Prune Redundancies)─────┘

Tong Zhang formalized this framework in Adaptive Forward-Backward Greedy Algorithm for Sparse Learning with Linear Models. The algorithm operates in two alternating phases:

  1. Forward Phase: Add features that maximize the reduction in loss.
  2. Backward Phase: Re-evaluate all currently selected features. If any feature's contribution falls below a specific threshold—because newly added features have rendered it redundant—it is adaptively pruned from the active set.

By allowing the model to "change its mind," this bidirectional approach corrects early selection errors. Stan Z. Li et al. applied this exact intuition to ensemble learning with FloatBoost in FloatBoost Learning for Classification, demonstrating that deleting previously added weak classifiers during training results in significantly more compact and accurate models than standard AdaBoost.

Why It Works: Overcoming Correlation and Local Optima

The primary reason bidirectional selection outperforms one-shot regularizers (like the Lasso) or pure forward selection comes down to how it navigates feature correlation.

When variables are highly correlated, noise in the dataset can easily trick a forward-only algorithm into picking a suboptimal variable early on. Once that variable is locked in, the model's trajectory is permanently skewed.

Tracy Ke et al. analyze this phenomenon in A Comparison of Hamming Errors of Representative Variable Selection Methods, demonstrating that Forward-Backward selection dramatically minimizes false positives and false negatives (Hamming error) compared to the Lasso when features are correlated. The backward step acts as a dynamic contextual filter: as the global model evolves, the algorithm continuously re-evaluates whether older features still pull their weight in the presence of newer ones.

This bidirectional flexibility provides an escape hatch from local optima. As Chao Tang et al. show in EEG channel selection based on sequential backward floating search for motor imagery classification, floating search strategies that alternate between elimination and re-inclusion reliably bypass the local minima that trap rigid, single-direction heuristics. This is echoed by Kazuya Yasueda et al. in Stepwise-based optimizing approaches for arrangements of loudspeaker in multi-zone sound field reproduction, where a bidirectional strategy allows a physical system to continuously optimize its configuration by discarding components that become redundant as the global layout takes shape.

Theoretical Guarantees and Consistency

While bidirectional selection sounds like an intuitive heuristic, it is backed by strict mathematical guarantees that often surpass convex relaxations:

Generalization Across Machine Learning Paradigms

Because the core mechanism—interleaving addition and subtraction—is model-agnostic, it has been successfully adapted across a wide variety of domains:

Key Foundational Work

Bayesian Network Classifiers Versus k-NN Classifier Using Sequential Feature Selection (2004) — contributed 2 concept elements to this direction.
FloatBoost Learning for Classification (2002) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sequential_floating_search_681dde23,
  title = {sequential floating search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-floating-search/rdr_681dde23a56247c08ef3b3b8beb3ed39},
  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_sequential_floating_search_681dde23_v1,
  title = {sequential floating search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-floating-search/rdr_681dde23a56247c08ef3b3b8beb3ed39/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake