When building machine learning models, selecting the right subset of features is a fundamental challenge. Traditional approaches rely heavily on greedy heuristics, such as forward selection (adding the best performing feature one by one) or backward elimination (removing the worst). While computationally cheap, these step-by-step methods suffer from a critical flaw: they make irreversible, local decisions that completely miss complex feature interactions.
If two features are highly predictive only when used together, a greedy algorithm evaluating them individually will discard them both. To overcome this limitation, a powerful paradigm has emerged: global feature subset optimization. Instead of selecting features sequentially, this approach formulates feature selection as a unified mathematical programming problem where all feature weights or selection variables are optimized simultaneously.
The Pitfalls of Local Decisions
To understand why simultaneous optimization works, we must first look at where greedy methods fail. As shown by Masaeli et al. in From Transformation-Based Dimensionality Reduction to Feature Selection, globally optimizing a feature subspace consistently outperforms greedy forward searches, even when both methods use the exact same evaluation criteria.
Greedy algorithms get trapped in local optima because they evaluate features in isolation or relative only to what has already been chosen. In contrast, simultaneous optimization treats the entire feature pool as a coupled system. This global perspective allows the framework to discover synergistic combinations—where individual variables might appear uninformative on their own but provide high predictive power when evaluated together.
Formulating Global Competition
How do we force all features to compete simultaneously without resorting to an exhaustive, brute-force search of every possible combination? One common strategy is to use continuous relaxations combined with sparsity-inducing penalties.
In A New View of Automatic Relevance Determination, Wipf et al. demonstrate that sparse feature selection can be driven by an iterative re-weighted $\ell_1$ minimization framework. This mathematical framing facilitates a mechanism of "global competition" among all potential features, outperforming incremental selection methods in overcomplete dictionaries.
Similarly, Jitkrittum et al. in Feature Selection via l1-Penalized Squared-Loss Mutual Information optimize all feature weights at the same time using a squared-loss mutual information objective. By avoiding sequential selection, their approach successfully captures non-linear dependencies and complex feature interactions that greedy metrics routinely overlook.
The Machinery of Quadratic and Conic Programming
A widely adopted formulation for this global competition is Quadratic Programming (QP). In a typical QP setup, the objective function balances two competing forces: maximizing individual feature relevance while minimizing pairwise redundancy.
Minimize: [Pairwise Redundancy between Features] - [Individual Feature Relevance]
Subject to: Sparsity and Budget Constraints
By framing selection this way, Lim et al. demonstrate in Multi-Label Learning Using Mathematical Programming and Accelerating Multi-Label Feature Selection Based on Low-Rank Approximation that simultaneous optimization prevents the loss of label-dependency information in multi-label tasks. Because the relationships between all features and the collective label set are preserved during the optimization process, the resulting subset is both highly informative and diverse. This balancing act is highly versatile; for example, Liu et al. apply a similar QP framework in Emotional Analysis and Annotation of Tourism Landscape Images Based on Tourist Experience to automatically isolate a subset of visual concepts that maximizes emotional representation while filtering out noise.
One historical challenge of feature selection has been determining how many features to pick. Simultaneous optimization solves this elegantly. In Size Adaptive Selection of Most Informative Features, Liu et al. introduce a method that relaxes the combinatorial search into a continuous QP task, allowing the system to determine the optimal subset size and its constituent features at the same time. Bypassing greedy search entirely, Cui et al. leverage a sparse weight vector optimized via QP in Adaptive Feature Selection Based on the Most Informative Graph-Based Features to let the data naturally dictate the ideal number of features.
For scenarios requiring strict mathematical guarantees, the optimization can be tightened further. Peleg et al. show in A Feature Selection Algorithm Based on the Global Minimization of a Generalization Error Bound that by using a change of variables, a messy, non-convex generalization error bound can be transformed into a convex Conic Quadratic Programming (CQP) task. This guarantees a global optimum for the feature set, even when the number of features significantly exceeds the number of samples.
Exact Discrete Optimization
Instead of relaxing the problem into continuous weights, another branch of global optimization tackles the discrete nature of feature selection head-on using binary variables ($x_i \in \{0, 1\}$) to represent the exclusion or inclusion of a feature.
By multiplying continuous feature weights with these binary selection variables, Nguyen et al. in On General Definition of L1-norm Support VectorMachines for Feature Selection formulate selection as a polynomial mixed 0-1 programming task. Applying branch-and-bound algorithms to a linearized version of this objective allows them to search the entire power set of feature combinations. This global search guarantees the absolute best combination for maximizing the classification margin, overcoming the limitations of local search heuristics.
Similarly, Ustun et al. develop SLIM (Supersparse Linear Integer Models) in Supersparse Linear Integer Models for Predictive Scoring Systems, utilizing mixed-integer programming to optimize over the entire space of integer coefficients simultaneously. This prevents the sub-optimal results typically produced when continuous weights are rounded after the fact.
With the advent of specialized hardware, these discrete formulations can be mapped directly to physical optimization systems. Niu et al. in CRUISE on Quantum Computing for Feature Selection in Recommender Systems frame feature selection as a Quadratic Unconstrained Binary Optimization (QUBO) problem. This allows the combinatorial search to be solved via quantum annealing or classical simulated annealing, evaluating the global impact of the entire feature configuration simultaneously.
Discrete optimization also allows for structural constraints that enforce global model properties. For instance, Norrenbrock et al. introduce QPM in QPM: Discrete Optimization for Globally Interpretable Image Classification, which uses a quadratic programming formulation to assign a fixed, small number of binary features to each class. This global constraint forces the model to share features across classes, ensuring it develops generalizable concepts rather than relying on isolated, class-specific shortcuts.
Why Global Optimization Matters: Budgets and Synergy
The intuition for why global optimization fundamentally outperforms greedy selection becomes clearest when we introduce resource or acquisition costs. In real-world applications like IoT networks or medical diagnostics, extracting a feature is not free—it costs CPU, memory, time, or money.
Under strict budget constraints, a greedy algorithm evaluates features sequentially based on their immediate cost-benefit ratio. If a single high-cost feature provides massive utility, a greedy algorithm will often reject it early on because its individual cost seems prohibitive. The algorithm instead fills the budget with multiple low-cost, low-utility features, leading to a sub-optimal local minimum.
As Chakraborty et al. demonstrate in Cost-Aware Feature Selection for IoT Device Classification, holistic optimization approaches mitigate these performance drops by evaluating the collective impact of feature subsets rather than making sequential, local decisions. This ensures that high-value, high-cost features are preserved if their combined utility justifies the expense.
A similar phenomenon occurs when optimizing ensembles. In Pruning Random Forests for Prediction on a Budget, Nan et al. point out that traditional pruning strategies evaluate model components in isolation. By switching to a global 0-1 integer program, their method accounts for feature reuse across the entire ensemble, identifying globally efficient feature sets that minimize the total system's resource consumption.
Finally, starting from a global pool and pruning down is inherently more powerful than building up step-by-step. As Shen et al. show in Asymmetric Pruning for Learning Cascade Detectors, selecting an optimal subset by pruning an over-complete pool of high-quality candidates allows for a more global optimization relative to the final objective than selecting features one-by-one from scratch.
By shifting the problem from a sequence of short-sighted choices to a single, global optimization task—as summarized by Zhang et al. in Multi-label Feature Selection via Global Relevance and Redundancy Optimization—we allow features to cooperate. This global view ensures that features which are only powerful in combination are never prematurely discarded, resulting in subsets that are fundamentally more robust, interpretable, and efficient.
Key Foundational Work
A Feature Selection Algorithm Based on the Global Minimization of a Generalization Error Bound (2004) — contributed 1 concept elements to this direction.
A New View of Automatic Relevance Determination (2007) — contributed 1 concept elements to this direction.