Skip to content
Open access

Minimax-Optimal Estimation of High-Order Missing Masses, and the Rare-Type Match Problem

Nov 2026 · IEEE Transactions on Information Theory · Vol 72, pp. 8577-8597 · 0 citations · 61 references

Abstract

Consider <inline-formula> <tex-math notation="LaTeX">$n\geq 1$ </tex-math></inline-formula> random samples <inline-formula> <tex-math notation="LaTeX">$\mathbf {X}_{n}=(X_{1},\ldots,X_{n})$ </tex-math></inline-formula> from an unknown distribution <inline-formula> <tex-math notation="LaTeX">$P=\sum _{j\geq 1}p_{j}\delta _{s_{j}}$ </tex-math></inline-formula> over a space of symbols <inline-formula> <tex-math notation="LaTeX">$\mathbb {S}$ </tex-math></inline-formula>, and let <inline-formula> <tex-math notation="LaTeX">$(Y_{n,j})_{j\geq 1}$ </tex-math></inline-formula> be the empirical frequencies of symbols <inline-formula> <tex-math notation="LaTeX">$s_{j}$ </tex-math></inline-formula>’s in the sample <inline-formula> <tex-math notation="LaTeX">$\mathbf {X}_{n}$ </tex-math></inline-formula>. For <inline-formula> <tex-math notation="LaTeX">$r\geq 1$ </tex-math></inline-formula>, the <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula>-order missing mass is defined as <inline-formula> <tex-math notation="LaTeX">$\theta _{r}(P;\mathbf {X}_{n})=\sum \limits_{j\geq 1}p^{r}_{j}I(Y_{n,j}=0),$ </tex-math></inline-formula> generalizing the celebrated missing mass, which corresponds to <inline-formula> <tex-math notation="LaTeX">$r=1$ </tex-math></inline-formula>. The problem of estimating <inline-formula> <tex-math notation="LaTeX">$\theta _{r}(P;\mathbf {X}_{n})$ </tex-math></inline-formula> has recently gained attention, and a nonparametric estimator <inline-formula> <tex-math notation="LaTeX">$\hat {\theta }_{r}^{\scriptscriptstyle \text {(GT)}}(\mathbf {X}_{n})$ </tex-math></inline-formula> has been proposed with theoretical guarantees of consistency and minimax optimality under the squared-loss function. In this paper, motivated by recent advances on <inline-formula> <tex-math notation="LaTeX">$\theta _{1}(P;\mathbf {X}_{n})$ </tex-math></inline-formula>, we study the estimation of <inline-formula> <tex-math notation="LaTeX">$\theta _{r}(P;\mathbf {X}_{n})$ </tex-math></inline-formula> under the multiplicative-loss function. Specifically, we show that consistent estimation is not feasible uniformly over all distributions on <inline-formula> <tex-math notation="LaTeX">$\mathbb {S}$ </tex-math></inline-formula>, and not even over distributions with regularly varying heavy-tails, which only guarantee pointwise consistency of <inline-formula> <tex-math notation="LaTeX">$\hat {\theta }_{r}^{\scriptscriptstyle \text {(GT)}}(\mathbf {X}_{n})$ </tex-math></inline-formula>. To overcome this impossibility result, we introduce a stronger assumption for the tail behaviour of <inline-formula> <tex-math notation="LaTeX">$P$ </tex-math></inline-formula>, proving it sufficient for minimax estimation and establishing the minimax optimality of <inline-formula> <tex-math notation="LaTeX">$\hat {\theta }_{r}^{\scriptscriptstyle \text {(GT)}}(\mathbf {X}_{n})$ </tex-math></inline-formula>. Beyond estimation, we provide a non-asymptotic confidence interval for <inline-formula> <tex-math notation="LaTeX">$\theta _{r}(P;\mathbf {X}_{n})$ </tex-math></inline-formula> without assumptions on the distribution <inline-formula> <tex-math notation="LaTeX">$P$ </tex-math></inline-formula>, leveraging novel concentration inequalities. Our interest in the <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula>-order missing mass arises from forensic statistics, where the estimation of the 2-order missing mass is central to estimating the likelihood ratio <inline-formula> <tex-math notation="LaTeX">$T(P,\mathbf {X}_{n})=\theta _{1}(P;\mathbf {X}_{n})/\theta _{2}(P;\mathbf {X}_{n})$ </tex-math></inline-formula> in the rare-type match problem, and we establish the first theoretical guarantees for its nonparametric estimation. We present an empirical validation of our methods for <inline-formula> <tex-math notation="LaTeX">$\theta _{r}(P;\mathbf {X}_{n})$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$T(P,\mathbf {X}_{n})$ </tex-math></inline-formula>.

Read PDF

Similar papers

Open access Dec 2024

Sparse PCA: Phase Transitions in the Critical Regime

This work studies sparse principal component analysis (PCA) in high dimensions. Given <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> independent <inline-formula> <tex-math notation="LaTeX">$p$ </tex-math></inline-formula>-dimensional Gaussian samples with covariance <inline-formula> <tex-m...

Michal Feldman, Theodor Misiakiewicz, Elad Romanov · 0 citations
Open access 2026

New Lower Bounds for Weak Superimposed Codes

A new general lower bound on the largest code rate of weak superimposed codes for all integers is derived by improving the best known lower bound on the largest asymptotic code rate of weak <inline-formula><tex-math notation="LaTeX">$(t,T)$</tex-math></inline-formula> by the Lovász local lemma.

Jin-Ping Fan, Yu-Jie Gu, Y. Miao · 0 citations
Open access 2026

RelSea: A Reliable L-Curve Search Region to Improve Regularization Parameter Selection

The selection of regularization parameters (<inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>) using the L-curve method is a well-established strategy for addressing ill-posed inverse problems. Several techniques have been developed to identify an appropriate <inline-formula> <tex-math...

Dorisney González-Caboverde, Gustavo Daniel Martín-del-Campo-Becerra, D. Torres-Román et al. · 0 citations
Open access 2026

Perfectly Private Lossless Variable-Length Coding With a Sequential Encoder

A lossless data compression problem with a privacy constraint is studied where a server has access to a database of <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> files, <inline-formula> <tex-math notation="LaTeX">$(Y_{1},\ldots,Y_{N})$ </tex-math></inline-formula>, each of size <inline-fo...

A. Zamani, Mikael Skoglund · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.