Demystifying Fixed k-Nearest Neighbor Information Estimators

1 Introduction

• The paper motivates fixed-k nearest-neighbor methods for continuous information estimation, where they often outperform alternatives in simulations and high-dimensional applications.It contrasts this setting with discrete functional estimation and identifies mutual information as the primary focus.Source: §1 · pp. 1–2

1.2 KSG Estimator: Consistency and Convergence Rate

• A correlation-boosting explanation motivates BI-KSG, whose theoretical guarantees match KSG but whose empirical improvement is pronounced for small k and moderate N.BI-KSG uses ℓ2 distances and replaces selected digamma terms with logarithms.Source: §1 · p. 2, §1.2 · p. 4

1.1 KL Entropy Estimator and Convergence Rate

• The paper shows KL entropy estimation has eO(1/√N) ℓ2 error for d ≤2, with variance eO(1/N) up to polylogarithmic factors.The result applies to a class of bounded-support densities including the uniform and truncated Gaussian, and the d=1 case is new under these conditions.Source: §1.1 · p. 3

1.2 KSG Estimator: Consistency and Convergence Rate

• The KSG estimator is consistent, with bias eO(N^−1/(d_x+d_y)), variance eO(1/N), and ℓ2 error eO(1/√N) when d_x=d_y=1.The equal one-dimensional case achieves the parametric ℓ2 rate, which cannot be improved upon.Source: §1.2 · p. 4

1.3 Outline of this paper

• The paper formally develops these results, explains KSG and BI-KSG, generalizes KSG to multivariate mutual information, reviews related literature, and relegates proofs to Sections 7–13.Sections 4–6 cover correlation boosting and BI-KSG, multivariate generalization, and context in entropy and mutual-information estimation.Source: §1.3 · p. 4

2.1 Upper Bounds

• Under Assumption 1, for finite k = O(1) and d = O(1), the truncated KL entropy estimator using N i.i.d. samples has MSE bounded by N 2/d plus ( log log N )2 ( log N )(2k+2)(1+δ).Assumption 1.(e) limits boundary bias to ˜O(N −1/d); in the smooth interior, bias is ˜O(N −2/d), so boundary bias dominates.Source: §2.1 · pp. 6–7

2.2 Minimax Lower Bound

• For entropy estimation from N i.i.d. samples, the minimax ℓ2 error is lower bounded by the parametric term Ω(N^-1) and by Ω(N^-16/(d+8)) from.The argument uses standard techniques, including Le Cam’s method in general and in particular, and considers a class of smooth distributions.Source: §2.2 · p. 7

2.3 Comparing the Bounds

• The upper and lower MSE bounds match for d ≤ 2, achieving the parametric ˜O(1/√N) rate, but retain an exponent gap for d > 2.The optimality-gap exponent is min{1/2, 8/(d+8)} − min{0.5, 1/d}, and closing the higher-dimensional gap remains open.Source: §2.3 · p. 7
• Simulations on uniform distributions show MSE slopes close to the theoretical upper-bound rates, suggesting that sharper lower bounds suited to k-NN estimation may be needed.For independent Beta(2,2) variables in six dimensions, k-NN methods empirically outperform KDE-based estimators at modest sample sizes despite slower theoretical asymptotic rates, indicating an important role for constants.Source: §2.3 · pp. 7–8

3.1 Consistency

• KSG and BI-KSG are consistent in probability under the stated assumptions, for finite k > max{d_x/d_y, d_y/d_x} with d_x,d_y = O(1).The assumptions include integrability, bounded conditional densities, and twice-continuous differentiability with bounded Hessian; bounded support is not required.Source: §3.1 · pp. 8–9

3.2 Convergence rate

• Under Assumption 3, truncated KSG and BI-KSG have upper bounds on bias, variance, and MSE convergence rates for finite k and bounded dimensions.The rate conditions include smoothness, density bounds, tail controls, and finite-measure exceptional sets; truncated multivariate Gaussians and uniform random variables satisfy them.Source: §3.2 · pp. 10–11
• KSG, BI-KSG, and 3KL have the same MSE-rate scaling through their stated upper bounds.This comparison is made between the convergence-rate upper bounds for the three estimators.Source: §3.2 · p. 11
• 1/N is the one-dimensional MSE convergence rate for KSG, BI-KSG, and 3KL up to a poly-logarithmic factor, and it cannot be improved parametrically.The result applies when d_x = d_y = 1.Source: §3.2 · p. 11

Correlation Boosting Effect

• Positive bias correlation reduces KSG error, is stronger than for 3KL, and can be higher for BI-KSG.This correlation is observed for independent uniforms and Gaussians and is proposed as the main reason KSG has lower mean-square error than 3KL.Source: §4 · p. 12, Table 1 · p. 12

New Estimator of Mutual Information

• BI-KSG replaces KSG’s ℓ∞ distances with ℓ2 distances and uses logarithms of marginal neighbor counts instead of digamma terms.The ℓ∞ construction can over-estimate one marginal entropy, introducing bias of order 1/n_y,i,∞ or 1/n_x,i,∞ depending on which boundary contains the joint k-NN sample.Source: §4 · p. 13
• O(1/n_x,i,2 + 1/n_y,i,2) bias is eliminated by replacing digamma functions with logarithms, yielding the bias-improved KSG estimator.The resulting marginal entropy estimate is based on log(n_x,i,2) and the analogous y term.Source: §4 · p. 14
• eO(1/√N + N^−1/(d_x+d_y)) ℓ2 error follows for BI-KSG, with eO(N^−1/(d_x+d_y)) bias and eO(1/N) variance.Theorem 10 also establishes consistency.Source: §4 · p. 14
• BI-KSG has the best sample complexity at moderate N in the joint Gaussian experiment, while all estimators converge to the ground truth as N increases.The gains are most visible for small k and moderate sample sizes when X and Y are dependent; asymptotic rates do not explain the effect, which may lie in multiplicative constants.Source: §4 · p. 14, Table 2 · p. 14

• The standard multivariate mutual information estimators generalize KSG and BI-KSG through balanced entropy sums, including the fixed k-NN-based (L + 1)-KL estimator.MMI is routinely used in unsupervised clustering and correlation extraction.Source: §5 · pp. 14–15
• Balance across every variable transfers the pairwise mutual-information theory, including consistency, to the multivariate setting.Each positive entropy term involving X_ℓ is matched by a negative term involving X_ℓ.Source: §5 · p. 15
• Correlation-boosted MMI estimators perform significantly better than the simpler (L + 1)-KL estimator, while BI-KSG performs marginally better than KSG in Figure 6.Figure 6 evaluates MSE for L = 3 jointly Gaussian variables with N = 100 ∼3000.Source: Figure 6 · p. 15, §5 · p. 15
• For broader balanced set-function metrics, the estimator reuses joint-space k-NN distances to estimate subset entropies, with the shared distance canceled by balance.The construction applies to a four-variable causal-strength example involving pairwise and marginal entropy terms and inherits the theoretical and empirical flavor of the earlier KSG results.Source: §5 · pp. 15–16

Problem context

• The paper studies continuous estimation, where Euclidean geometry and domain dimensionality shape entropy and mutual-information estimation, distinct from discrete minimax-functional estimation [22] [66].The broader problem is also established across statistics, machine learning [16] [26], information theory [66], and theoretical computer science [1].Source: §6 · p. 16

KDE approaches

• KDE estimates fX,Y, fX, and fY separately before resubstitution, with data splitting used to reduce overfitting.Related results achieve the parametric rate for differential entropy when dimension is at most 6, while strong density conditions can yield exponential rates.Source: §6 · p. 16

Alternative estimators

• Related entropy estimators use spacings, Edgeworth expansions, convex optimization, growing-k k-NN methods [28], and generalized nearest-neighbor graphs.Fixed-k alternatives include experimental comparisons and local Gaussian methods combining local likelihood estimation with k-NN bandwidth choices [16] [17].Source: §6 · p. 16

Smoothness and rates

• Standard Hölder smoothness does not yield refined convergence rates for the fixed-k-NN KL and KSG estimators studied here.The analysis shows the relevant density-approximation condition remains unchanged for smoother Hölder families.Source: §6 · p. 17

Scope and limitations

• The analysis complements by covering higher dimensions and bounded-support densities with strictly positive densities, while covers smooth unbounded-support densities.The two analyses handle different boundary and near-zero-density conditions, and neither result implies the other even for d = 1.Source: §6 · p. 17

Future extensions

• Ensembles of k-NN estimators may achieve the parametric rate O(1/N) through weighted combinations across k, but require first-order constants that may depend on the distribution [36].For fixed-distance estimators, the expected bias rate is O((k/N)1/d), while the variance rate is expected to be independent of k.Source: §6 · p. 17

7 Proof of Theorem 3

• Theorem 3’s bias bound follows by separately controlling three terms: truncated k-NN distances and discrepancies between fN,x(u) and fx(u).The proof combines the bounds for I1(x), I2(x), and I3(x), using aN = ((log N)1+δ/N)1/d and bN = e^-ψ(k)cd(log N)1+δ.Source: §7 · pp. 18, 20, 21

7.1 Proof of Lemma 1

• Lemma 1 derives the reference distribution of the transformed k-NN distance and shows its expected log value matches the entropy expression.The derivation uses the continuous CDF Fx(u), a change of variables, and the identity involving ψ(k).Source: §7.1 · pp. 21–22

7.2 Proof of Lemma 2

• Lemma 2 bounds the difference between the finite-sample density fN,x(u) and its limiting density fx(u) using local ball-mass approximation and a binomial-to-Poisson comparison.The analysis treats regions S1 and S2 separately and applies bounds on the probability mass of p-norm balls.Source: §7.2 · pp. 22–23

7.3 Proof of Lemma 3

• Lemma 3 controls the CDF difference |FN,x(u) − Fx(u)| by expressing FN,x through binomial probabilities and applying the ball-mass approximation.For x ∈ S2, the supplied bound is kC2u + (k − 1)!C3(eψ(k)Ca)2u2/N.Source: §7.3 · pp. 24–25

7.4 Proof of Lemma 4

• Lemma 4 bounds the error in approximating probability mass inside a p-norm ball by density times volume, using smoothness on S1 and a supremum-density bound on S2.The argument uses a second-order expansion and surface-measure control for p-norm balls.Source: §7.4 · p. 25

7.5 Proof of Lemma 5

• Lemma 5 bounds the binomial-to-Poisson approximation error for sufficiently small q by applying logarithmic inequalities and Stirling’s formula.The proof assumes q < C/N for a sufficiently small constant C.Source: §7.5 · p. 26

8 Proof of Theorem 4

• Combining Lemmas 6 and 7 establishes the desired statement for Theorem 4.The proof uses the decomposition into a variance term and a covariance term: ≤ 1 N Var [ ξk,1(X) ] + Cov [ ξk,1(X), ξk,2(X) ].Source: §8 · p. 26

8.1 Proof of Lemma 6

• The variance of ξk,i(X) is upper bounded using corresponding pdfs fN,x(u) and fx(u); for u < 1, the argument invokes Lemma 2 and uses f(x) ≤Ca.Source: §8.1 · p. 27

8.2 Proof of Lemma 7

• Lemma 7 bounds covariance by splitting cases ∥x − y∥ ≤ 2aN and ∥x − y∥ > 2aN, obtaining C4(log log N)^2(log N)^(1+δ)/N for the first case.For separated points, the corresponding balls are disjoint, and substituting bN = (log N)^(1+δ) completes the claim.Source: §8.2 · pp. 28, 29, 31

9 Proof of Theorem 5 on the minimax lower bound

• Le Cam’s method proves the Ω(1/N) lower bound by comparing Gaussian distributions with covariances Id and (1 + δ)Id and distinct entropies.Both Gaussian distributions belong to the smoothness class because their Hessian norms are bounded.Source: §9 · p. 31
• The perturbation construction partitions [0,1]^d into hypercubes and adds a smoothness-class perturbation to the uniform distribution, yielding the minimax lower bound N^-16/(d+8) with γ = 2.The proof uses an extension of Le Cam’s method.Source: §9 · pp. 32–33

9.1 Proof of Lemma 9

• Lemma 9 shows that the uniform distribution has higher entropy than the constructed perturbations, while Lemma 10 supplies divergence bounds using Cauchy–Schwarz and exponential inequalities.These lemmas support the entropy separation and testing bounds in the minimax construction.Source: §9.1 · p. 33, §9.2 · p. 34

10 Proof of Theorem 6 on the consistency of KSG estimator

• KSG and BI-KSG mutual-information estimators are consistent because their marginal entropy estimates converge, while joint entropy estimates converge in probability by [29].The proof concludes the desired claim from these componentwise convergence results.Source: §10 · p. 35

10.1 Proof of Lemma 11

• If k > dy/dx, the three error terms in the marginal-entropy analysis each vanish as N →∞.The bounds for the local approximation, auxiliary, and nearest-neighbor terms are independent of z, enabling the convergence argument.Source: §10.1 · p. 40
• Lemma 11 proves that the estimated marginal entropy converges to the true entropy in probability.The proof combines convergence of empirical-mean error and density-estimation error.Source: §10 · p. 35, §10.1 · p. 40

11.1 Proof of Lemma 12

• Under Assumptions 3.(c) and (d), the probability that the kth-neighbor radius exceeds aN is bounded by a term decaying faster than 1/N^c for every constant c.The proof sets aN = ((log N)^(1+δ)/N)^(1/d) and separates the support according to local regularity to control this tail event.Source: §11 · p. 41, §11.1 · p. 42

11 Proof of Theorem 7 on the bias of KSG estimator

• Combining Theorem 3, Lemma 13, and Lemma 12 yields the desired bias convergence statement for KSG and BI-KSG.The joint term uses a local d-dimensional Kozachenko–Leonenko estimator, while marginal convergence follows by exchanging X and Y when k ≥ dx/dy.Source: §11 · p. 41, §11.2 · p. 44

11.2 Proof of Lemma 13

• For marginal entropy estimation, the small-radius event satisfies P(ρk,1 < r) ≤ 2(NC_ac_d r^d)^k, yielding P(ρk,1 < rN) ≤ C(log N)^(2kd)/N.This bound is combined with logarithmic-radius integration and the condition k ≥ dx/dy to control the marginal bias.Source: §11.2 · pp. 43–44

12 Proof of Theorem 8 on the variance of KSG estimator

• Theorem 8 follows by rewriting mutual information with a truncated KL entropy estimator and bounding the adaptive entropy variances for X and Y.The argument combines the Cauchy–Schwarz reduction with Theorem 4.Source: §12 · pp. 46–47

12.1 Proof of Lemma 14

• The variance bound for bH(X) decomposes into a scaled single-sample variance and covariance term, and combining Lemmas 15 and 16 completes the proof.Source: §12.1 · p. 47

12.2 Proof of Lemma 15

• Lemma 15 bounds the variance of each entropy summand by controlling h(nx,1), using k < nx,1 < N and the tail bound for the k-nearest-neighbor radius.Here h(x) is either log(x) or ψ(x + 1).Source: §12.2 · pp. 47–48

12.3 Proof of Lemma 16

• Lemma 16 controls covariance by splitting point configurations into disjoint, partially overlapping, and intersecting neighborhoods, using multinomial analysis or Cauchy–Schwarz.For disjoint strips, the covariance is bounded by 3/N; the intersecting-ball case is controlled through conditional variances and event probabilities.Source: §12.3 · pp. 49–50

Partition argument

• The proof uses exchangeability of i.i.d. samples to assign equal probabilities to the distance-ordering events defined by each partition.Each event identifies the k − 1 closer samples, the kth neighbor, and the remaining farther samples.Source: §13 · p. 52

Conditional independence

• Conditioning on the kth-neighbor event makes the remaining X-distance indicators i.i.d., because their corresponding joint samples are independent of the conditioning on the other coordinates.This independence establishes the binomial structure of nx,i − k.Source: §13 · p. 52

Conditional distribution

• Conditioned on Zi = z and ρk,i = r, nx,i − k has a Binomial distribution represented by the sum of indicators Ul for l = k + 1, …, N − 1.The indicators correspond to samples whose X-distance from x is smaller than r.Source: §13 · p. 52

Moment and approximation bounds

• The proof then bounds the mean of Ul using Lemma 4 and bounds the difference between p and fX(x)cdxrdx.These bounds provide the final quantitative step in the theorem’s proof.Source: §13 · pp. 52–53