# Conformal Frequency Estimation using Discrete Sketched Data with Coverage for Distinct Queries

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 100 references that are in the map.
- First posted on arXiv 9 Nov 2022.

## Builds on (most cited first, 30 of 33)

- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (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)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [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)
- [PAC Prediction Sets Under Covariate Shift](https://mlsanity.com/paper/2106.09848/) (2021)
- [With Malice Towards None: Assessing Uncertainty via Equalized Coverage](https://mlsanity.com/paper/1908.05428/) (2019)
- [Distribution-Free Prediction Sets for Two-Layer Hierarchical Models](https://mlsanity.com/paper/1809.07441/) (2018)
- [Isotonic Distributional Regression](https://mlsanity.com/paper/1909.03725/) (2019)
- [Integrative conformal p-values for powerful out-of-distribution testing with labeled outliers](https://mlsanity.com/paper/2208.11111/) (2022)
- [PAC Prediction Sets for Meta-Learning](https://mlsanity.com/paper/2207.02440/) (2022)
- [Ridge Regression: Structure, Cross-Validation, and Sketching](https://mlsanity.com/paper/1910.02373/) (2019)
- [(Learned) Frequency Estimation Algorithms under Zipfian Distribution](https://mlsanity.com/paper/1908.05198/) (2019)
- [Optimal Randomized First-Order Methods for Least-Squares Problems](https://mlsanity.com/paper/2002.09488/) (2020)
- [PAC-Wrap: Semi-Supervised PAC Anomaly Detection](https://mlsanity.com/paper/2205.10798/) (2022)
- [Origins of power-law degree distribution in the heterogeneity of human activity in social networks](https://mlsanity.com/paper/1304.4523/) (2013)
- [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)

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

- [Length Optimization in Conformal Prediction](https://mlsanity.com/paper/2406.18814/) (2024)
- [Adaptive conformal classification with noisy labels](https://mlsanity.com/paper/2309.05092/) (2023)
- [Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularization](https://mlsanity.com/paper/2502.13030/) (2025)
- [SymmPI: Predictive Inference for Data with Group Symmetries](https://mlsanity.com/paper/2312.16160/) (2023)
- [Conformal Information Pursuit for Interactively Guiding Large Language Models](https://mlsanity.com/paper/2507.03279/) (2025)
- [Statistical Methods in Generative AI](https://mlsanity.com/paper/2509.07054/) (2025)
- [Conformal Inference for Open-Set and Imbalanced Classification](https://mlsanity.com/paper/2510.13037/) (2025)
- [Tightening optimality gap with confidence through conformal prediction](https://mlsanity.com/paper/2503.04071/) (2025)
- [Singleton-Optimized Conformal Prediction](https://mlsanity.com/paper/2509.24095/) (2025)
- [Weighted Conformal Prediction Provides Adaptive and Valid Mask-Conditional Coverage for General Missing Data Mechanisms](https://mlsanity.com/paper/2512.14221/) (2025)

## Abstract (arXiv)

This paper develops conformal inference methods to construct a confidence interval for the frequency of a queried object in a very large discrete data set, based on a sketch with a lower memory footprint. This approach requires no knowledge of the data distribution and can be combined with any sketching algorithm, including but not limited to the renowned count-min sketch, the count-sketch, and variations thereof. After explaining how to achieve marginal coverage for exchangeable random queries, we extend our solution to provide stronger inferences that can account for the discreteness of the data and for heterogeneous query frequencies, increasing also robustness to possible distribution shifts. These results are facilitated by a novel conformal calibration technique that guarantees valid coverage for a large fraction of distinct random queries. Finally, we show our methods have improved empirical performance compared to existing frequentist and Bayesian alternatives in simulations as well as in examples of text and SARS-CoV-2 DNA data.