# Learning-based Support Estimation in Sublinear Time

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 32 references that are in the map.
- First posted on arXiv 15 Jun 2021.

## Builds on (most cited first, 11 of 11)

- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Spreading vectors for similarity search](https://mlsanity.com/paper/1806.03198/) (2018)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [A Deep Learning Approach to Structured Signal Recovery](https://mlsanity.com/paper/1508.04065/) (2015)
- [Learning to Hash for Indexing Big Data - A Survey](https://mlsanity.com/paper/1509.05472/) (2015)
- [Testing probability distributions underlying aggregated data](https://mlsanity.com/paper/1402.3835/) (2014)
- [Learning-based Compressive Subsampling](https://mlsanity.com/paper/1510.06188/) (2015)

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

- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Online Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [(Optimal) Online Bipartite Matching with Degree Information](https://mlsanity.com/paper/2110.11439/) (2021)
- [Learning-Augmented Maximum Flow](https://mlsanity.com/paper/2207.12911/) (2022)
- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)
- [Improved Learning-augmented Algorithms for k-means and k-medians Clustering](https://mlsanity.com/paper/2210.17028/) (2022)
- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [Learning-Based Algorithms for Graph Searching Problems](https://mlsanity.com/paper/2402.17736/) (2024)
- [Daisy Bloom Filters](https://mlsanity.com/paper/2205.14894/) (2022)
- [Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster L-/L^natural-Convex Function Minimization](https://mlsanity.com/paper/2302.00928/) (2023)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Learning-Augmented Streaming Algorithms for Correlation Clustering](https://mlsanity.com/paper/2510.10705/) (2025)
- [Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions](https://mlsanity.com/paper/2603.04635/) (2026)
- [Learning the Positions in CountSketch](https://mlsanity.com/paper/2306.06611/) (2023)

## Abstract (arXiv)

We consider the problem of estimating the number of distinct elements in a large data set (or, equivalently, the support size of the distribution induced by the data set) from a random sample of its elements. The problem occurs in many applications, including biology, genomics, computer systems and linguistics. A line of research spanning the last decade resulted in algorithms that estimate the support up to  ± varepsilon n from a sample of size O(log2(1/varepsilon) · n/log n), where n is the data set size. Unfortunately, this bound is known to be tight, limiting further improvements to the complexity of this problem. In this paper we consider estimation algorithms augmented with a machine-learning-based predictor that, given any element, returns an estimation of its frequency. We show that if the predictor is correct up to a constant approximation factor, then the sample complexity can be reduced significantly, to [  log (1/varepsilon) · n1-Theta(1/log(1/varepsilon)). ] We evaluate the proposed algorithms on a collection of data sets, using the neural-network based estimators from Hsu et al, ICLR'19 as predictors. Our experiments demonstrate substantial (up to 3x) improvements in the estimation accuracy compared to the state of the art algorithm.