mlsanityData to 7 Oct 2026

Conformal Frequency Estimation with Sketched Data

arXiv 2204.04270 ↗First posted 8 Apr 2022stat.ME stat.MLcited by 4

Not on the map. Why?

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.

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

Builds on

18 of 52 references.

References · 18

  1. 2016Distribution-Free Predictive Inference For Regressioncited by 657
  2. 2019Conformalized Quantile Regressioncited by 620
  3. 2020Classification with Valid and Adaptive Coveragecited by 390
  4. 2020Uncertainty Sets for Image Classifiers using Conformal Predictioncited by 365
  5. 2016Least Ambiguous Set-Valued Classifiers with Bounded Error Levelscited by 270
  6. 2020Conformal Inference of Counterfactuals and Individual Treatment Effectscited by 150
  7. 2021Testing for Outliers with Conformal p-valuescited by 133
  8. 2019Distributional conformal predictioncited by 104
  9. 2019Nested conformal prediction and quantile out-of-bag ensemble methodscited by 88
  10. 2021Conformal Prediction using Conditional Histogramscited by 77
  11. 2019A comparison of some conformal quantile regression methodscited by 76
  12. 2019Flexible distribution-free conditional predictive bands using density estimatorscited by 64
6 more
  1. 2021Conformalized Survival Analysiscited by 53
  2. 2019Isotonic Distributional Regressioncited by 28
  3. 2021Distribution-Free Conditional Median Inferencecited by 7
  4. 2015Count-Min-Log sketch: Approximately counting with approximate counterscited by 6
  5. 2018Count-Min: Optimal Estimation and Tight Error Bounds using Empirical Error Distributionscited by 5
  6. 2021A Bayesian nonparametric approach to count-min sketch under power-law data streamscited by 3

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 2; 2024: 1.

4 papers.

  1. 2023Adaptive conformal classification with noisy labelscited by 24
  2. 2023Conformal inference is (almost) free for neural networks trained with early stoppingcited by 14
  3. 2022Conformal Frequency Estimation using Discrete Sketched Data with Coverage for Distinct Queriescited by 10
  4. 2024Towards Modeling Uncertainties of Self-explaining Neural Networks via Conformal Predictioncited by 10