# Conformal Frequency Estimation with Sketched Data

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 52 references that are in the map.
- First posted on arXiv 8 Apr 2022.

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

- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Conformal Inference of Counterfactuals and Individual Treatment Effects](https://mlsanity.com/paper/2006.06138/) (2020)
- [Testing for Outliers with Conformal p-values](https://mlsanity.com/paper/2104.08279/) (2021)
- [Distributional conformal prediction](https://mlsanity.com/paper/1909.07889/) (2019)
- [Nested conformal prediction and quantile out-of-bag ensemble methods](https://mlsanity.com/paper/1910.10562/) (2019)
- [Conformal Prediction using Conditional Histograms](https://mlsanity.com/paper/2105.08747/) (2021)
- [A comparison of some conformal quantile regression methods](https://mlsanity.com/paper/1909.05433/) (2019)
- [Flexible distribution-free conditional predictive bands using density estimators](https://mlsanity.com/paper/1910.05575/) (2019)
- [Conformalized Survival Analysis](https://mlsanity.com/paper/2103.09763/) (2021)
- [Isotonic Distributional Regression](https://mlsanity.com/paper/1909.03725/) (2019)
- [Distribution-Free Conditional Median Inference](https://mlsanity.com/paper/2102.07967/) (2021)
- [Count-Min-Log sketch: Approximately counting with approximate counters](https://mlsanity.com/paper/1502.04885/) (2015)
- [Count-Min: Optimal Estimation and Tight Error Bounds using Empirical Error Distributions](https://mlsanity.com/paper/1811.04150/) (2018)
- [A Bayesian nonparametric approach to count-min sketch under power-law data streams](https://mlsanity.com/paper/2102.03743/) (2021)

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

- [Adaptive conformal classification with noisy labels](https://mlsanity.com/paper/2309.05092/) (2023)
- [Conformal inference is (almost) free for neural networks trained with early stopping](https://mlsanity.com/paper/2301.11556/) (2023)
- [Conformal Frequency Estimation using Discrete Sketched Data with Coverage for Distinct Queries](https://mlsanity.com/paper/2211.04612/) (2022)
- [Towards Modeling Uncertainties of Self-explaining Neural Networks via Conformal Prediction](https://mlsanity.com/paper/2401.01549/) (2024)

## Abstract (arXiv)

A flexible conformal inference method is developed to construct confidence intervals for the frequencies of queried objects in very large data sets, based on a much smaller sketch of those data. The approach is data-adaptive and requires no knowledge of the data distribution or of the details of the sketching algorithm; instead, it constructs provably valid frequentist confidence intervals under the sole assumption of data exchangeability. Although our solution is broadly applicable, this paper focuses on applications involving the count-min sketch algorithm and a non-linear variation thereof. The performance is compared to that of frequentist and Bayesian alternatives through simulations and experiments with data sets of SARS-CoV-2 DNA sequences and classic English literature.