Accelerating Feature Selection in High Dimensions

102 concepts97 papers1 proposal

High-dimensional datasets—where the number of features can reach tens or hundreds of thousands—present a fundamental challenge for modern machine learning. Finding a minimal, highly informative feature subset is critical for reducing latency, memory consumption, and overfitting, as demonstrated by Lee et al. in AdFlush: A Real-World Deployable Machine Learning Solution for Effective Advertisement and Web Tracker Prevention.

However, traditional "wrapper" methods require repeatedly training models to evaluate feature subsets, creating an intractable computational bottleneck. To make feature selection practical at scale, researchers have developed algorithmic shortcuts that bypass exhaustive evaluation, reducing the computational complexity from exponential or quadratic down to linear, or even logarithmic time.

Streaming Features: From Quadratic to Linear Time

Traditional feature selection assumes all variables are available upfront, requiring global optimization passes over the entire feature matrix. Streaming feature selection flips this paradigm by evaluating features sequentially in a single pass.

Ungar et al. introduce this concept in Streaming Feature Selection using IIC using an information-investing framework. The algorithm manages a "wealth budget" that dynamically adjusts the statistical threshold for adding new features based on past successes. Building on this sequential paradigm, Wu et al. demonstrate in Online Streaming Feature Selection that by performing immediate local redundancy checks and delaying global sweeps, models can process an infinite stream of features efficiently.

Why it works: By making localized, immediate decisions on whether to accept or reject a feature as it arrives, the search space scales linearly ($O(d)$) with the number of features rather than quadratically ($O(d^2)$). This avoids the need to compute joint distributions across all variables simultaneously.

Residual Tracking: Eliminating Retraining Cycles

When selecting features incrementally, a major source of overhead is retraining the model from scratch to evaluate each candidate. Forward feature selection can be accelerated by changing what we measure: instead of measuring how well a feature predicts the target variable $Y$, we measure how well it predicts the current model's error.

In Forward feature selection using Residual Mutual Information, Schaffernicht et al. utilize Residual Mutual Information (RMI) to guide feature selection.

Why it works: The residual captures exactly what the current model has failed to learn. By selecting features that share high mutual information with the residual error rather than the raw target, the algorithm isolates the next most informative variable without executing full training cycles. This achieves wrapper-level accuracy at a fraction of the computational cost.

Two clever mechanisms achieve sublinear or single-pass exploration by embedding structural shortcuts directly into the training process.

Probing with Shadow Variables

In gradient boosting, determining when to stop adding features usually requires expensive cross-validation loops. Thomas et al. introduce "probing" in Probing for sparse and fast variable selection with model-based boosting by appending randomly shuffled "shadow variables" to the dataset.

Why it works: Because shadow variables are explicitly constructed to contain only noise, the exact moment the boosting algorithm selects a shadow variable serves as an automated, data-driven stopping criterion. This allows highly sparse feature selection to occur in a single training run, bypassing cross-validation entirely.

Group Testing

For tree-based models, Han proposes a group testing strategy in Scalable Feature Selection for (Multitask) Gradient Boosted Trees. Instead of evaluating features individually, the algorithm evaluates sums of features, known as pseudo-features.

Why it works: If a combined pseudo-feature shows no predictive power, the entire group of constituent features can be discarded at once. This enables a binary search process over the feature space, dropping the computational complexity of feature selection from linear to logarithmic ($O(\log d)$) relative to the total number of features.

Individual Testing (Linear Time):
[F1] -> [F2] -> [F3] -> [F4] -> [F5] -> [F6] -> [F7] -> [F8]  (8 evaluations)

Group Testing (Logarithmic Time):
[F1 + F2 + F3 + F4] vs [F5 + F6 + F7 + F8]  --> Discard right half
[F1 + F2]           vs [F3 + F4]           --> Discard left half
[F3]                vs [F4]                --> Identify F3 (3 evaluations)

Mathematical Shortcuts: Bypassing Iterative Optimization

Another frontier replaces iterative heuristic searches with direct mathematical approximations or closed-form solutions.

For discrete choice models, Kamiya et al. show in Feature subset selection for the multinomial logit model via mixed-integer optimization that embedding a quadratic approximation within an outer approximation framework reduces mixed-integer optimization runtimes by an order of magnitude.

For multi-label problems, where features must map to multiple targets simultaneously, Zhang et al. demonstrate in Multi-label Feature Selection via Global Relevance and Redundancy Optimization that feature weights can be solved through a closed-form matrix equation.

Why it works: Closed-form solutions and quadratic approximations compute the global relationship between features and labels in a single mathematical step. This completely eliminates the need for iterative greedy searches or combinatorial optimization, keeping computation stable even as the feature space expands.

Key Foundational Work

A Fast Algorithm for Feature Selection in Conditional Maximum Entropy Modeling (2003) — 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_efficient_feature_selection_004f98ef,
  title = {efficient feature selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efficient-feature-selection/rdr_004f98ef3a3c42fea43aedc732e15b1e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_efficient_feature_selection_004f98ef_v1,
  title = {efficient feature selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efficient-feature-selection/rdr_004f98ef3a3c42fea43aedc732e15b1e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake