Title: Estimation of discrete distributions in relative entropy, and the deviations of the missing mass Show Chinese title

Title: 离散分布相对熵的估计及缺失质量偏差

Abstract: We study the problem of estimating a distribution over a finite alphabet from an i.i.d. sample, with accuracy measured in relative entropy (Kullback-Leibler divergence). While optimal expected risk bounds are known, high-probability guarantees remain less well-understood. First, we analyze the classical Laplace (add-one) estimator, obtaining matching upper and lower bounds on its performance and showing its optimality among confidence-independent estimators. We then characterize the minimax-optimal high-probability risk, which is attained via a simple confidence-dependent smoothing technique. Interestingly, the optimal non-asymptotic risk exhibits an additional logarithmic factor over the ideal asymptotic risk. Next, motivated by scenarios where the alphabet exceeds the sample size, we investigate methods that adapt to the sparsity of the distribution at hand. We introduce an estimator using data-dependent smoothing, for which we establish a high-probability risk bound depending on two effective sparsity parameters. As part of the analysis, we also derive a sharp high-probability upper bound on the missing mass. Show Chinese abstract

Abstract: 我们研究了从独立同分布样本估计有限字母表上分布的问题，并以相对熵（Kullback-Leibler散度）来衡量精度。尽管已知最优的期望风险界，高概率保证仍然较少为人所理解。首先，我们分析了经典的拉普拉斯（加一）估计器，得到了其性能的匹配上下界，并证明了它在无信心依赖估计器中的最优性。然后，我们刻画了最小最大高概率风险，通过简单的信心依赖平滑技术实现。有趣的是，最优的非渐近风险在理想渐近风险之上表现出额外的对数因子。接下来，受字母表超过样本量场景的启发，我们研究了适应分布稀疏性的方法。我们引入了一种使用数据依赖平滑的估计器，并建立了依赖于两个有效稀疏参数的高概率风险界。作为分析的一部分，我们还推导出了缺失质量的尖锐高概率上界。