Instance-Specific Sharp Convergence Rate of the Add-$\lambda$ Estimator via Feature Space Decomposition

Abstract

Using the Feature Space Decomposition framework, we establish non-asymptotic matching upper and lower bounds for the expected Kullback-Leibler estimation error of the Add-$\lambda$ estimator of a discrete probability distribution, for any signal, any dimension, any sample size, and any $\lambda >0$.