CS Paper Radar

Daily listing

2026-11-17 · math.ST

2 papers first submitted this day (UTC) in math.ST — math.ST. arXiv announces a day's submissions the next evening, so the newest day fills up over ~24 h.

Score = weighted mean ofCitations 20%Upvotes 10%Code stars 10%Venue 15%Code/data 10%Novelty 15%Momentum 15%Substance 5%how it works

AI & Machine Learning 1

The Price of Hard Coverage Constraints in Online Conformal Prediction

cs.LG math.STstat.ML ·2026-11-17 ·Mingrui Liu
Abstract

Conformal prediction provides distribution-free uncertainty quantification, but in sequential deployment, standard coverage guarantees can still allow substantial fluctuations in the number of miscoverages over time. We study an online setting in which prediction sets are produced one round at a time and the cumulative number of miscoverages must stay within a prescribed budget throughout deployment.Such a hard coverage guarantee can be enforced by enlarging prediction sets, but how much additional prediction-set size is fundamentally necessary remains unclear. We characterize this unavoidable efficiency cost over $T$ prediction rounds. Remarkably, the cost persists even with i.i.d.\ data, a known score distribution, and perfect knowledge of the population-optimal prediction set. Under suitable regularity conditions relating coverage and prediction-set size, we determine the minimum cumulative excess prediction-set size required by any online method satisfying the hard coverage constraint. This minimum cost is $Θ(\log T)$ for expected cost at a fixed time known in advance, $Θ(T^{1/3})$ for the largest expected cost over all fixed times up to $T$, and $Θ(\sqrt{T})$ for the expected worst realized cost when the evaluation time is chosen in hindsight. We further show that these rates can be attained using past scores, without knowing the score distribution. Thus, even perfect statistical knowledge does not make sequential reliability free.

0.10

Theory & Algorithms 1

Optimal Min-Entropy Estimation with High Probability

cs.IT math.STquant-ph ·2026-11-17 ·Qisheng Wang
Abstract · 9 pages

Min-entropy plays a fundamental role in assessing the unpredictability of randomness sources. In particular, NIST SP 800-90B specifies min-entropy estimation as a key procedure for entropy sources used in cryptographic random bit generators, illustrating the practical importance of reliable min-entropy estimation. In this paper, we settle the sample complexity of min-entropy estimation with high probability in both the classical and quantum cases. Specifically, for min-entropy estimation with additive error $\varepsilon$ and probability at least $1-δ$, the sample complexity is $Θ(d\log(d/δ)/\varepsilon^2)$ for classical distributions on $d$ symbols and $Θ((d^2+d\log(1/δ))/\varepsilon^2)$ for quantum states on a $d$-dimensional Hilbert space. Our results admit short and simple proofs.

0.35