# MISSION: Ultra Large-Scale Feature Selection using Count-Sketches

arXiv: https://arxiv.org/abs/1806.04310 · HTML: https://mlsanity.com/paper/1806.04310/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2018.

## Built on by (most cited first, 11 of 11)

- [Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning](https://mlsanity.com/paper/2310.04357/) (2023)
- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [On the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2202.13736/) (2022)
- [CountSketches, Feature Hashing and the Median of Three](https://mlsanity.com/paper/2102.02193/) (2021)
- [Comfetch: Federated Learning of Large Networks on Constrained Clients via Sketching](https://mlsanity.com/paper/2109.08346/) (2021)
- [Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2207.00956/) (2022)
- [Federated Gradient Matching Pursuit](https://mlsanity.com/paper/2302.10755/) (2023)
- [Scalable variable selection for two-view learning tasks with projection operators](https://mlsanity.com/paper/2307.01558/) (2023)
- [Communication-Efficient Federated Learning over Wireless Channels via Gradient Sketching](https://mlsanity.com/paper/2410.23424/) (2024)
- [A Recovery Guarantee for Sparse Neural Networks](https://mlsanity.com/paper/2509.20323/) (2025)
- [Optimized Learned Count-Min Sketch](https://mlsanity.com/paper/2512.12252/) (2025)

## Abstract (arXiv)

Feature selection is an important challenge in machine learning. It plays a crucial role in the explainability of machine-driven decisions that are rapidly permeating throughout modern society. Unfortunately, the explosion in the size and dimensionality of real-world datasets poses a severe challenge to standard feature selection algorithms. Today, it is not uncommon for datasets to have billions of dimensions. At such scale, even storing the feature vector is impossible, causing most existing feature selection methods to fail. Workarounds like feature hashing, a standard approach to large-scale machine learning, helps with the computational feasibility, but at the cost of losing the interpretability of features. In this paper, we present MISSION, a novel framework for ultra large-scale feature selection that performs stochastic gradient descent while maintaining an efficient representation of the features in memory using a Count-Sketch data structure. MISSION retains the simplicity of feature hashing without sacrificing the interpretability of the features while using only O(log^2(p)) working memory. We demonstrate that MISSION accurately and efficiently performs feature selection on real-world, large-scale datasets with billions of dimensions.