mlsanityData to 7 Oct 2026

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

arXiv 2211.04612 ↗First posted 9 Nov 2022stat.ME math.ST stat.MLcited by 10

Not on the map. Why?

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.

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

Builds on

33 of 100 references.

References · 33

  1. 2016Distribution-Free Predictive Inference For Regressioncited by 657
  2. 2019Conformalized Quantile Regressioncited by 620
  3. 2019Conformal Prediction Under Covariate Shiftcited by 511
  4. 2020Classification with Valid and Adaptive Coveragecited by 390
  5. 2020Uncertainty Sets for Image Classifiers using Conformal Predictioncited by 365
  6. 2022Conformal prediction beyond exchangeabilitycited by 348
  7. 2014Sketching as a Tool for Numerical Linear Algebracited by 285
  8. 2016Least Ambiguous Set-Valued Classifiers with Bounded Error Levelscited by 270
  9. 2020Conformal Inference of Counterfactuals and Individual Treatment Effectscited by 150
  10. 2021Testing for Outliers with Conformal p-valuescited by 133
  11. 2019Distributional conformal predictioncited by 104
  12. 2019Nested conformal prediction and quantile out-of-bag ensemble methodscited by 88
21 more
  1. 2021Conformal Prediction using Conditional Histogramscited by 77
  2. 2019A comparison of some conformal quantile regression methodscited by 76
  3. 2019Flexible distribution-free conditional predictive bands using density estimatorscited by 64
  4. 2021Conformalized Survival Analysiscited by 53
  5. 2019With Malice Towards None: Assessing Uncertainty via Equalized Coveragecited by 43
  6. 2021PAC Prediction Sets Under Covariate Shiftcited by 42
  7. 2018Distribution-Free Prediction Sets for Two-Layer Hierarchical Modelscited by 34
  8. 2019Isotonic Distributional Regressioncited by 28
  9. 2022Integrative conformal p-values for powerful out-of-distribution testing with labeled outlierscited by 19
  10. 2022PAC Prediction Sets for Meta-Learningcited by 16
  11. 2019Ridge Regression: Structure, Cross-Validation, and Sketchingcited by 15
  12. 2019(Learned) Frequency Estimation Algorithms under Zipfian Distributioncited by 10
  13. 2020Optimal Randomized First-Order Methods for Least-Squares Problemscited by 10
  14. 2022PAC-Wrap: Semi-Supervised PAC Anomaly Detectioncited by 10
  15. 2013Origins of power-law degree distribution in the heterogeneity of human activity in social networkscited by 9
  16. 2021Distribution-Free Conditional Median Inferencecited by 7
  17. 2015Count-Min-Log sketch: Approximately counting with approximate counterscited by 6
  18. 2018Count-Min: Optimal Estimation and Tight Error Bounds using Empirical Error Distributionscited by 5
  19. 2022Conformal Frequency Estimation with Sketched Datacited by 4
  20. 2021A Bayesian nonparametric approach to count-min sketch under power-law data streamscited by 3
  21. 2020Frequency Estimation in Data Streams: Learning the Optimal Hashing Schemecited by 1

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 1; 2025: 7.

10 papers.

  1. 2024Length Optimization in Conformal Predictioncited by 39
  2. 2023Adaptive conformal classification with noisy labelscited by 24
  3. 2025Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularizationcited by 11
  4. 2023SymmPI: Predictive Inference for Data with Group Symmetriescited by 8
  5. 2025Conformal Information Pursuit for Interactively Guiding Large Language Modelscited by 7
  6. 2025Statistical Methods in Generative AIcited by 4
  7. 2025Conformal Inference for Open-Set and Imbalanced Classificationcited by 3
  8. 2025Tightening optimality gap with confidence through conformal predictioncited by 2
  9. 2025Singleton-Optimized Conformal Predictioncited by 2
  10. 2025Weighted Conformal Prediction Provides Adaptive and Valid Mask-Conditional Coverage for General Missing Data Mechanismscited by 0