  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.
