# Categorical Feature Compression via Submodular Optimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2019.

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

- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)
- [Dynamic Algorithms for Matroid Submodular Maximization](https://mlsanity.com/paper/2306.00959/) (2023)
- [Feature Cross Search via Submodular Optimization](https://mlsanity.com/paper/2107.02139/) (2021)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [Stochastic Submodular Maximization via Polynomial Estimators](https://mlsanity.com/paper/2303.09960/) (2023)
- [Greedy PIG: Adaptive Integrated Gradients](https://mlsanity.com/paper/2311.06192/) (2023)
- [Fairness in Monotone k-submodular Maximization: Algorithms and Applications](https://mlsanity.com/paper/2411.05318/) (2024)

## Abstract (arXiv)

In the era of big data, learning from categorical features with very large vocabularies (e.g., 28 million for the Criteo click prediction dataset) has become a practical challenge for machine learning researchers and practitioners. We design a highly-scalable vocabulary compression algorithm that seeks to maximize the mutual information between the compressed categorical feature and the target binary labels and we furthermore show that its solution is guaranteed to be within a 1-1/e ≈ 63% factor of the global optimal solution. To achieve this, we introduce a novel re-parametrization of the mutual information objective, which we prove is submodular, and design a data structure to query the submodular function in amortized O(log n ) time (where n is the input vocabulary size). Our complete algorithm is shown to operate in O(n log n ) time. Additionally, we design a distributed implementation in which the query data structure is decomposed across O(k) machines such that each machine only requires O(frac n k) space, while still preserving the approximation guarantee and using only logarithmic rounds of computation. We also provide analysis of simple alternative heuristic compression methods to demonstrate they cannot achieve any approximation guarantee. Using the large-scale Criteo learning task, we demonstrate better performance in retaining mutual information and also verify competitive learning performance compared to other baseline methods.