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.
The Short-Sightedness of Monotonic Search
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:
- Forward Phase: Add features that maximize the reduction in loss.
- 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:
- Oracle-Order Recovery: In signal processing, Laming Chen et al. prove in Oracle-Order Recovery Performance of Greedy Pursuits With Replacement Against General Perturbations that greedy pursuits incorporating a replacement mechanism achieve "oracle-order" performance. This means they recover sparse signals as accurately as an imaginary "oracle" who knew the true feature locations in advance, even when the data is corrupted by noise.
- Support Consistency: In multi-task learning, Lu Tian et al. demonstrate in Forward Backward Greedy Algorithms for Multi-Task Learning with Faster Rates that the backward pruning step guarantees the recovery of the exact true feature support, achieving faster convergence rates than convex alternatives.
- General Convex Optimization: Ji Liu et al. extended these guarantees to non-linear, complex objective functions in Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint, introducing a highly efficient gradient-based variant (
FoBa-gdt) that maintains strict sparsity bounds without the computational overhead of traditional combinatorial search.
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:
- Covariance Estimation: Christopher C. Johnson et al. apply this to network structure discovery in High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods, proving that a greedy forward-backward approach recovers complex graphical models with fewer data points and under less restrictive conditions than standard Lasso-style optimization.
- Matrix Factorization: The authors of Learning overcomplete dictionaries with ℓ0-sparse Non-negative Matrix Factorisation utilize a backward elimination strategy starting from a full non-negative least squares solution to enforce true $\ell_0$ element-count sparsity, successfully learning overcomplete dictionaries where standard $\ell_1$ methods fail.
- Spatial Regularization: In neuroimaging, Yongxin Xi et al. incorporate backward steps into boosting in Boosting with Spatial Regularization, allowing the model to prune previously selected features that no longer align with the emerging spatial structure of the global importance map.
- High-Dimensional Optimization: To combat the curse of dimensionality in black-box optimization, Yihang Shen et al. introduce a momentum-based validation step in Computationally Efficient High-Dimensional Bayesian Optimization via Variable Selection to re-evaluate variable importance when function improvements stall, preventing the optimization process from being permanently derailed by noisy initial gradients. Similarly, Mingkui Tan et al. leverage a non-monotonic selection process over convex combinations of feature subsets in Learning Sparse SVM for Feature Selection on Very High Dimensional Datasets to prevent the permanent loss of features due to early local optima.
- Genomics and Healthcare: In complex biological domains, David Haws et al. demonstrate in Variable-Selection Emerges on Top in Empirical Comparison of Whole-Genome Complex-Trait Prediction Methods that bidirectional greedy selection handles marker redundancy better than standard dense models. This practical utility is mirrored in clinical diagnostics by Juanying Xie et al. in A Novel Hybrid Feature Selection Method Based on IFSFFS and SVM for the Diagnosis of Erythemato-Squamous Diseases, where floating search strategies successfully isolate minimal, highly accurate diagnostic feature sets by continuously re-evaluating the utility of previously selected medical variables.
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.