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

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>.