Feature selection is a fundamental challenge in machine learning: how do we identify the most informative subset of variables from a high-dimensional space? While theoretically simple, the task is an NP-hard combinatorial optimization problem. To manage this complexity, practitioners often rely on greedy algorithms—strategies that make the locally optimal choice at each step, such as adding the single best feature (forward selection) or removing the worst (backward elimination).
However, a vast body of research indicates that these myopic strategies frequently fail to find the globally optimal subset. By prioritizing immediate gains, greedy methods become trapped in local optima, overlooking superior feature combinations that only reveal their utility when considered together.
The Problem of Irreversibility
The primary weakness of greedy selection is its lack of backtracking. Once a decision is made—whether to include a feature in a model or a viewpoint in a 3D reconstruction—it is rarely re-evaluated. Weiss and Indurkhya et al. argue that this additive search strategy prevents the discovery of more compact and accurate rule sets, as the algorithm cannot replace a previously selected feature with a better alternative that emerges later in the search.
This "short-sightedness" has practical consequences across domains:
- Structural Modeling: In Structure from Motion, Yan et al. found that greedy viewpoint selection leads to redundant image sets and fragmented models because the algorithm cannot revise its earlier choices.
- Data Approximation: Joneidi et al. observe that sequential data selection fails to approximate global dataset properties because it lacks iterative refinement.
- Sparse Representation: In kernel spaces, Andelic et al. note that sequential basis selection settles for local optima rather than the most efficient sparse representation.
Blindness to Synergistic Interactions
Greedy algorithms evaluate features based on their marginal contribution to the current set. This creates a "synergy gap": if two features are only powerful when used in tandem, a greedy search will likely ignore both because neither provides a significant boost on its own.
Sanger et al. highlight that standard iterative methods fail to identify essential components of complex interactions if those components lack independent utility. This is echoed in reinforcement learning, where the authors of the Conditional Mutual Information framework show that greedy selection fails to capture "implicit" dependencies—variables that are crucial for long-term success but offer no immediate reward signal.
Similarly, Uematsu and Umetani demonstrate that greedy heuristics fail in combinatorial optimization when elements exhibit high independent utility but poor mutual synergy. In such cases, the algorithm picks "strong" individual elements that do not work well together, missing the globally optimal "team" of features.
The Cost of Local Optima
Settling for a local optimum isn't just a theoretical failure; it imposes real-world costs. Miyazaki points out that in sequential data acquisition, a suboptimal inspection order leads to higher measurement costs. In the context of IoT, Chakraborty and Nevat show that greedy strategies may exclude highly informative features simply because they are slightly more expensive to extract, resulting in a set of low-value features that degrade overall performance.
Furthermore, Wang et al. demonstrate that greedy trajectories for feature importance (like those used in model explainability) provide an incomplete picture of model dependencies, as they can miss the global maximum of a given importance metric.
Beyond Greed: Global and Pareto Optimization
To overcome these limitations, researchers have proposed moving toward more exhaustive or multi-objective frameworks.
One prominent direction is Pareto Optimization. Instead of optimizing for a single fixed subset size, Qian et al. treat subset selection as a bi-objective problem, simultaneously minimizing error and subset size. This approach, implemented in the POSS algorithm, is proven to find global optima for specific data structures where greedy methods fail. Feng et al. extended this to unsupervised learning, showing that exploring the broader trade-off space prevents the myopic decision-making inherent in sequential algorithms.
Other researchers focus on mathematical guarantees. Meila and Koelle propose convex algorithms that provide more stable alternatives to brute-force searches, while Li and Tang emphasize the need for embedded approaches that jointly optimize feature selection and reconstruction to avoid the pitfalls of disjoint, greedy steps. By shifting from local heuristics to global perspectives, these methods ensure that the selected features represent the true underlying geometry of the data rather than just the easiest path to a local minimum.