# Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Oct 2024.

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

- [Instance Dependent Testing of Samplers using Interval Conditioning](https://mlsanity.com/paper/2512.06458/) (2025)
- [Cheap to Draw, Expensive to Trust: Certifying Test-Time Scaling Curves](https://mlsanity.com/paper/2609.40190/) (2026)

## Abstract (arXiv)

Suppose we have a memory storing 0s and 1s and we want to estimate the frequency of 1s by sampling. We want to do this I/O-efficiently, exploiting that each read gives a block of B bits at unit cost; not just one bit. If the input consists of uniform blocks: either all 1s or all 0s, then sampling a whole block at a time does not reduce the number of samples needed for estimation. On the other hand, if bits are randomly permuted, then getting a block of B bits is as good as getting B independent bit samples. However, we do not want to make any such assumptions on the input. Instead, our goal is to have an algorithm with instance-dependent performance guarantees which stops sampling blocks as soon as we know that we have a probabilistically reliable estimate. We prove our algorithms to be instance-optimal among algorithms oblivious to the order of the blocks, which we argue is the strongest form of instance optimality we can hope for. We also present similar results for I/O-efficiently estimating mean with both additive and multiplicative error, estimating histograms, quantiles, as well as the empirical cumulative distribution function. We obtain our above results on I/O-efficient sampling by reducing to corresponding problems in the so-called sequential estimation. In this setting, one samples from an unknown distribution until one can provide an estimate with some desired error probability. We then provide non-parametric instance-optimal results for several fundamental problems: mean and quantile estimation, as well as learning mixture distributions with respect to ℓ_∞ and the so-called Kolmogorov-Smirnov distance.