Source-linked AI summary
Settling the Sample Complexity of R\'enyi Entropy Estimation
Qisheng Wang
TL;DR
Prior noninteger-order Rényi entropy estimation results left gaps between sample-complexity upper and lower bounds. This paper develops matching upper and lower bounds and settles the sample complexity for every noninteger order.
Problem
Prior results left gaps between upper and lower bounds on the sample complexity of noninteger-order Rényi entropy estimation.
Source: §1 · p. 3Method
The paper presents optimal estimators together with matching lower bounds for noninteger orders.
Source: §1 · p. 4Results
For noninteger α > 0, the paper establishes sufficient and necessary sample complexities for additive-ε estimation, optimal up to a constant depending only on α.
Source: §1.1 · p. 4Takeaways & Limitations
The results settle the noninteger-order sample complexity and complete the complexity picture of Rényi entropy estimation.
Source: §1 · p. 4
Abstract
from arXiv · showhide
R\'enyi entropy estimation has been comprehensively investigated by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015; IEEE Trans. Inf. Theory 2017) and consequent works, whereas only the sample complexity of R\'enyi entropy estimation of integer order has been settled. In this paper, we settle the sample complexity of R\'enyi entropy estimation of noninteger order, thereby completing the complexity picture of R\'enyi entropy estimation. Specifically, we show that for any noninteger $\alpha > 0$, it is sufficient and necessary to use \[ \Theta\!\left(\frac{d^{\max\{1/\alpha,1\}}}{\varepsilon^{1/\alpha}\log(d)} + \frac{d^{|1-1/\alpha|}}{\varepsilon^2}\right) \] samples to estimate the R\'enyi entropy of order $\alpha$ of an unknown discrete distribution over an alphabet of size $d$ to within additive error $\varepsilon$. For the upper bound, we reduce the bias using a refined polynomial approximation estimator for large probabilities. For the lower bound, we employ a different hard instance equipped with a new moment matching construction. The constructive moment matching has constant bounded high-order moments, while attaining a fixed ratio between the $\alpha$-th moments, which is of independent interest.
1 Introduction
Rényi entropy estimation extends the entropy-estimation problem, but prior results left gaps in the sample complexity for noninteger orders. The paper closes those gaps with matching upper and lower bounds and presents the techniques behind them.
1 Introduction
- Earlier noninteger-order results left gaps between sample-complexity upper and lower bounds, which this paper closes.The paper identifies this as completing the complexity picture for Rényi entropy estimation.Source: §1 · pp. 3–4
1.1 Main results
- For every noninteger α > 0, the paper proves matching sufficient and necessary sample complexities for additive-ε estimation, optimal up to a constant depending only on α.The guarantee has success probability at least 2/3.Source: §1.1 · p. 4
- The paper reports that its upper bound improves on the compared bound for all noninteger α > 1/2, and its lower bound improves on the compared lower bound for all noninteger α > 0.It also states an upper-bound improvement for 1 < α < 3/2, without identifying the comparison as [JVHW15].Source: §1.1 · p. 5
1.2 Techniques
- Poissonization makes the empirical counts independent Poisson variables, and its sample complexity is equivalent to multinomial sampling up to a constant factor.This is the sampling model used to prove the results.Source: §1.2 · p. 5
1.2.1 Lower bounds
- A constructive moment-matching pair unifies lower-bound arguments for 0 < α < 1 and noninteger α > 1, with bounded second, α-th, and 2α-th moments.The construction matches K moments and may be of independent interest.Source: §1.2.1 · p. 6
- The constructions give Ω(d^(1−γ)) and Ω(d^(1/α−γ)) lower bounds, with m chosen arbitrarily large, and yield the first term of the lower bound in Theorem 1.1.The first bound concerns distinguishing p_x and p_y after a uniformly random label permutation. For the second bound, β = 1/α − 1 − η/2.Source: §1.2.1 · p. 6
1.2.2 Upper bounds
- The improved estimator retains the prior estimator for small probabilities and uses a Taylor-expansion-based estimator for large probabilities to reduce bias.This removes an unexpected bias term and yields the stated upper bound.Source: §1.2.2 · pp. 7–8
2 Preliminaries
The preliminaries collect results used later: a dimension-dependent moment inequality, approximation bounds for x^α, and inequalities for Poisson variables.
2 Preliminaries
- Section 2 collects known results that the paper uses later.Source: §2 · p. 8
2.1 Basic inequalities
- For α > 1/2, α ≠ 1, F_(2α−1)(p)/(F_α(p))^2 is bounded by d^|1−1/α|.Source: §2.1 · p. 8
2.2 Best polynomial approximation
- A best degree-k approximation to x^α on [0,1] has error O(k^(−2α)), with coefficient sum at most (3/2)8^k.Source: §2.2 · p. 8
2.3 Inequalities for Poisson distributions
- Section 2.3 lists inequalities for Poisson distributions and identifies sources for the stated results.Source: §2.3 · p. 9
3 Lower Bounds
The section develops a moment-matching construction and uses it in a hypothesis-testing argument to prove lower bounds for noninteger-order Rényi entropy estimation.
3.1 Constructive Moment Matching
- Lemma 3.1 constructs distributions on [0,K^2] that match K moments and share mean µ; µ_b^(α) denotes their α-th moment.Source: §3.1 · p. 9
3.2 The lower bound
- For noninteger α > 0, the lower bound includes a term scaling as d^max{1/α,1}/(ε^(1/α) log(d)).Source: §3.2 · p. 11
- The proof reduces estimation to distinguishing equally likely hypotheses whose associated entropy values differ by 8ε.Source: §3.2 · pp. 11–12
- An accurate entropy estimator would distinguish the hypotheses with success at least 2/3 − 0.01, while the proposed sampling budget limits success to at most 0.55.Source: §3.2 · p. 12
4 Upper Bounds
This section presents an estimator and analyzes its correctness and sample complexity. The estimator achieves additive ε accuracy with probability at least 2/3 for every distribution over an alphabet of size d.
4.1 The estimator
- The estimator uses independent Poisson counts Xi and Yi, each with mean npi, for each symbol in a distribution over d symbols.Source: §4.1 · p. 14
- The estimator in Equation (20) achieves additive ε accuracy with probability at least 2/3 for every distribution over d symbols.Source: §4.1 · p. 15
4.2 Correctness and complexity analysis
- The correctness analysis splits terms according to whether Y is at most 10L or greater than 10L, using a polynomial-based term in the first case.Source: §4.2 · pp. 15–16