1 Introduction↩︎

The nonparametric maximum likelihood estimator (NPMLE) has recently emerged as a standard tool in modern data analysis, playing a central role in methods for principal components analysis [1], hierarchical linear modeling [2], and empirical partially Bayes multiple testing [3]; see also [4]. These advances rest on two complementary developments: a long line of work on the statistical properties of the NPMLE in mixture models, from [5], [6] to [7], [8], and substantial progress in computational methods and software [9]–[11]. In this paper, we push this line of work further by studying the NPMLE for general exponential family mixtures. We propose a generic computational approach that substantially improves efficiency, and we develop a unified theoretical framework to better understand the strong statistical performance of the NPMLE.

In many applications, the data are naturally modeled as arising from mixtures of some parametric family [12]. Let \(\{p_\theta : \theta \in \Theta\}\) be a family of densities on \(\mathbb{R}\), defined with respect to a common reference measure \(\mu\), where \(\Theta \subseteq \mathbb{R}\) is the parameter space. For a mixing distribution \(g\) on \(\Theta\), the corresponding mixture density is \[f_g(x) \mathrel{\vcenter{:}}= \int_{\Theta} p_\theta(x)\,\mathrm{d}g(\theta).\] Suppose we observe an i.i.d.sample \(X_1,\ldots,X_n \sim f_{g_0}\) for some unknown mixing distribution \(g_0\), and the goal is to recover certain features of \(g_0\). The NPMLE treats \(g_0\) as an unknown probability distribution supported on a known subset \(\Theta_0 \subseteq \Theta\), and estimates it by any maximizer \[\label{eq:NPMLE} \hat{g} \in \arg\sup_{g\in\mathcal{G}}\,\ell_n(f_g),\tag{1}\] where \[\label{eq:mixing} \mathcal{G} \mathrel{\vcenter{:}}= \{g : \mathrm{supp}(g)\subseteq \Theta_0\},\tag{2}\] and \(\ell_n(f) \mathrel{\vcenter{:}}= \sum_{i=1}^n \log f(X_i)\) denotes the log-likelihood.

Because \(\Theta_0\) often contains infinitely many points, the exact NPMLE \(\hat{g}\) is generally computationally intractable. A variety of methods have been proposed to approximate it, including the EM algorithm [13], interior-point methods [9], and the Frank–Wolfe algorithm [14]; see also [11] and [10] for more recent computational developments in the multivariate setting. A common feature of all these approaches is that the log-likelihood \(\ell_n(f)\), or its dual formulation, must be evaluated repeatedly. Consequently, for important models such as Gaussian mixtures [7] and chi-square mixtures [3], the computational cost of each iteration is at least linear in \(n\), making these methods burdensome for large-scale problems¹. An important exception arises in many discrete models, such as those in which \(p_\theta\) is Poisson or geometric. Indeed, if \(\mu\) is the counting measure on the natural numbers \(\mathbb{N}\) (including zero), then \[\label{eq:trick} \sum_{i=1}^n \log f(X_i)=\sum_{k=0}^{|X|_n} N_k \log f(k),\tag{3}\] where \(|X|_n \mathrel{\vcenter{:}}= \max_{i\in[n]} |X_i|\), \(N_k \mathrel{\vcenter{:}}= \#\{i\in[n]: X_i = k\}\), and \([n] \mathrel{\vcenter{:}}= \{1,\dots,n\}\). Consequently, when \(f_{g_0}\) is light-tailed, \(|X|_n\) may grow only logarithmically with \(n\), substantially reducing the cost of evaluating \(\ell_n(f)\). The first goal of this work is to extend this computational advantage beyond the discrete setting to more general models, in which the observations \(X_1,\dots,X_n\) are typically distinct.

Once the NPMLE \(\hat{g}\), or an approximation thereof, has been computed, a central theoretical question is how accurately the plug-in estimator \(f_{\hat{g}}\) approximates the true density \(f_{g_0}\). The existing literature is largely model-specific, with most results focusing on Poisson mixtures [15]–[17] and Gaussian location mixtures [2], [8], [13], [18]. More recently, theoretical guarantees have also been established for scaled chi-square mixtures [3]. A common feature of these results is that, when \(f_{g_0}\) has sufficiently light tails, \(f_{\hat{g}}\) converges to \(f_{g_0}\) at a nearly parametric rate, up to logarithmic factors, thereby illustrating a broad adaptivity property of the NPMLE. Beyond these model-by-model analyses, a unified theory is currently available only for a class of discrete models known as mixtures of power series distributions [19]. Since these models are supported on \(\mathbb{N}\), they also automatically enjoy the computational advantages described above. Our second goal in this work is to develop a unified theoretical framework for the nearly parametric convergence of the (approximate) NPMLE in marginal density estimation over exponential family mixtures.

2 Main results↩︎

Following [5], [6], we work with the following exponential family mixture model.

1. Let \(p_0\) be a base density on \(\mathbb{R}\) with respect to a dominating measure \(\mu\). Define its moment generating function \(Z\) and cumulant generating function \(\kappa\) by \[Z(\theta)\mathrel{\vcenter{:}}= \int \exp(\theta x)\, p_0(x)\,\mathrm{d}\mu(x), \qquad \kappa(\theta)\mathrel{\vcenter{:}}= \log Z(\theta),\] for \(\theta\) in the canonical parameter space \[\Theta \mathrel{\vcenter{:}}= \{\theta \in \mathbb{R} : Z(\theta) < \infty\}.\] The corresponding exponential family is given by \[p_\theta(x)\mathrel{\vcenter{:}}= \exp\bigl(\theta x-\kappa(\theta)\bigr)\,p_0(x), \qquad \theta\in\Theta.\] We assume that \(X_1,\dots,X_n\) are i.i.d. observations from \(f_{g_0}\), and that \[\mathrm{supp}(g_0)\subseteq \Theta_0 \mathrel{\vcenter{:}}= \{\theta\in\mathbb{R}: |\theta|\le M\}\subseteq \Theta\] for some known constant \(M\in(0,\infty]\).

Notable examples of the exponential family in [40EF41] include the following.

1. Scaled chi-square mixture: \(M<\infty\), and \[p_0(x)=\Bigl(\frac{\nu}{2\sigma^2}\Bigr)^{\nu/2}\frac{x^{\nu/2-1}}{\Gamma(\nu/2)} \exp\Bigl(-\frac{\nu x}{2\sigma^2}\Bigr),\] for some fixed integer \(\nu\ge 2\) and constant \(\sigma^2>0\).

2. Gaussian location mixture: \(M=\infty\), and \[p_0(x)=\frac{1}{\sqrt{2\pi}}\exp\Bigl(-\frac{x^2}{2}\Bigr).\]

To our knowledge, the study of the NPMLE for model [40SC41] was initiated only recently by [3], motivated by applications to multiple testing. By contrast, for model [40GL41], convergence rate analyses have a longer history: density estimation results go back at least to [18] and were further developed by [7], while convergence rate results for empirical Bayes estimation were established by [13]. We view these two examples as representative of two broader scenarios:

1. Assume [40EF41] holds. In addition, suppose that \(M<\infty\) and that there exists \(\tau>0\) such that \[[-M-\tau,\,M+\tau]\subseteq \Theta.\]

2. Assume [40EF41] holds. In addition, suppose that \(M=\infty\), that \(p_0\) has mean zero, and that there exist constants \(\alpha_1\ge \alpha_2>0\) such that \[\label{eq:CGF} c_1|\theta|^{1+1/\alpha_1}\le \kappa(\theta)\le c_2|\theta|^{1+1/\alpha_2}, \qquad |\theta|\ge c_0,\tag{4}\] for some constants \(c_0,c_1,c_2>0\).

These two scenarios place assumptions on one of the two main ingredients of the mixture model: the mixing class 2 , determined by \(M\), and the component family, determined by \(p_0\). Scenario [40S141] assumes that the mixing distribution is supported on a compact interval, while allowing the baseline density \(p_0\) to be fairly general. In particular, it permits \(p_0\) to have tails of the same order as the exponential distribution, which is essentially the heaviest tail compatible with the exponential family framework.

By contrast, scenario [40S241] allows the mixing distribution to have support on all of \(\mathbb{R}\), while imposing conditions on the tail behavior of \(p_0\). In particular, it requires the tails of \(p_0\) to be neither too heavy nor too light. The lower bound on \(\kappa(\theta)\) rules out compactly supported \(p_0\), whereas the upper bound excludes densities too close to exponential. A similar assumption appears in Theorem 5 of [20].

Prior work on the NPMLE 1 suggests that a light-tailed \(f_{g_0}\) is essential for \(f_{\hat{g}}\) to exhibit near-parametric behavior. We therefore assume:

1. There exists \(\beta_0>0\) such that \[\mathbb{P}(|X|_n \ge t)\le n\exp(-b_1 t^{\beta_0}), \qquad t\ge b_0,\] for some \(b_0,b_1>0\).

In scenario [40S141], this condition is automatically satisfied with \(\beta_0=1\). In scenario [40S241], by contrast, it requires additional assumptions on \(g_0\). See Lemma 9 for a discussion.

2.1 Approximate NPMLE via data compression↩︎

Under [40EF41], an important observation is that the NPMLE \(\hat{g}\in\mathcal{G}\) can equivalently be expressed as a maximizer of \[\int \log l_g(x)\,\mathrm{d}P_n(x)=\frac{1}{n}\sum_{i=1}^n \log l_g(X_i),\] where \(P_n\) denotes the empirical measure based on the observations, and \(l_g(x)\) is the likelihood ratio function given by \[l_g(x)\mathrel{\vcenter{:}}= \int l_\theta(x)\,\mathrm{d}g(\theta), \qquad l_\theta(x)\mathrel{\vcenter{:}}= \frac{p_\theta(x)}{p_0(x)}=\exp\bigl(\theta x-\kappa(\theta)\bigr).\] In the discrete setting, the key computational idea behind 3 is to compress \(P_n\) into a discrete measure whose number of support points is much smaller than \(n\). Guided by this perspective, we propose the following procedure for handling general observations.

Given a sequence of (possibly random) positive integers \(\{J_n\}_{n\ge1}\), let \(P_{J_n}\) denote an order-\(J_n\) Gaussian quadrature rule for \(P_n\). By construction, \(P_{J_n}\) and \(P_n\) share the same first \(2J_n-1\) moments. The existence of \(P_{J_n}\) is standard; see Theorem 2A of [21]. Based on \(P_{J_n}\), we define the approximate NPMLE by \[\label{eq:hatgJn} \hat{g}_{J_n}\in\arg\sup_{g\in\mathcal{G}}\int \log l_g(x)\,\mathrm{d}P_{J_n}(x).\tag{5}\] The construction is summarized in Algorithm 1. This procedure naturally includes the discrete setting discussed above. Indeed, it suffices to take \(J_n = |X|_n + 1\), in which case \(P_{J_n} = P_n\), and therefore \(\hat{g}_{J_n} = \hat{g}\). By contrast, in many important cases, such as [40SC41] and [40GL41], one typically has \(P_{J_n}\neq P_n\) unless \(J_n=n\), where no computational savings are obtained. This motivates the question of how large \(J_n\) should be in order for \(\hat{g}_{J_n}\) to be sufficiently close to \(\hat{g}\) under an appropriate criterion.

In classical discussions of NPMLE computation, one seeks an estimator \(\tilde{g}\in\mathcal{G}\) satisfying the likelihood criterion \[\label{eq:LRT} \ell_n(f_{\hat{g}})-\ell_n(f_{\tilde{g}})\le \Delta_n,\tag{6}\] where \(\{\Delta_n\}_{n\ge 1}\) is a sequence of tolerance levels. The presence of a positive gap \(\Delta_n\) in 6 is computationally unavoidable because \(\mathcal{G}\) is infinite-dimensional. Given a candidate \(\tilde{g}\), one can often compute an upper bound on this likelihood gap without explicitly evaluating \(\hat{g}\); see Section 6.4 of [12]. The central question is therefore how small \(\Delta_n\) must be for the approximate NPMLE \(\tilde{g}\) to inherit the key statistical properties of \(\hat{g}\). The answer is task-dependent: different inferential goals require different levels of likelihood accuracy. We give a brief discussion of known tolerance requirements in Section 4.1.

Our main result characterizes the relationship between \(J_n\) and \(\Delta_n\) when \(\tilde{g} = \hat{g}_{J_n}\).

Theorem 1 applies under the basic exponential family setup, without any further assumptions. The following corollary shows that, under both scenarios considered here, polylogarithmic growth of \(J_n\) is sufficient to ensure a strong likelihood approximation by \(\hat{g}_{J_n}\).

This corollary, however, does not by itself provide concrete guidance for the practical choice of \(J_n\). In practice, we suggest choosing \(J_n\) as the largest value for which \(P_{J_n}\) can still be computed in a numerically stable manner. In our implementation, we employ the Golub–Welsch algorithm [22], which computes \(P_{J_n}\) accurately and stably for \(J_n\) up to about 20–30. This range is typically adequate even for sample sizes as large as \(100{,}000\).

Although constructing \(P_{J_n}\) still incurs at least linear cost in \(n\), this one-time preprocessing step is substantially cheaper than computing the NPMLE on the full sample. In our simulations, it is more than two orders of magnitude faster than the implementations of [9] and [10]; see Section 4.3.

Algorithm 1 is presented in one dimension for theoretical clarity, but the same idea extends to multivariate settings. As an illustration, Section 4.2 treats the heteroscedastic Gaussian sequence model, where observing both \(X_i\) and its variability measure makes the computation essentially two-dimensional.

2.2 Marginal density estimation with approximate NPMLE↩︎

The purpose of this section is to show that, in the general exponential family settings [40S141] and [40S241], estimators that attain sufficiently high sample likelihood in the sense of 6 also enjoy strong guarantees for marginal density estimation. Earlier results of this kind were available only for particular models, such as Gaussian location mixtures [7], and were formulated in terms of the squared Hellinger distance \[H^2(f,f_0)\mathrel{\vcenter{:}}=\int \big(\sqrt{f(x)}-\sqrt{f_0(x)}\big)^2\mathrm{d}\mu(x),\] where \(f\) and \(f_0\) are densities with respect to \(\mu\).

Traditional analyses of the NPMLE typically proceed by controlling the entropy of the class of marginal densities \[\{f_g : g \in \mathcal{G}\},\] with respect to an appropriately restricted supremum norm. In general exponential family settings, however, this approach becomes difficult to implement, since the base density \(p_0\) may be highly irregular. A different argument is therefore required.

Under scenario [40S141], the parameter space \(\Theta_0\) is bounded. Using the notation introduced there, we define the surrogate density \[\bar{f}_g(x)\mathrel{\vcenter{:}}=\int \bar{p}_\theta(x)\,\mathrm{d}g(\theta), \qquad \bar{p}_\theta(x)\mathrel{\vcenter{:}}= l_\theta(x)\exp\bigl(-(M+\tau)|x|\bigr).\] By controlling the size of the class \[\bar{\mathcal{F}}\mathrel{\vcenter{:}}=\{\bar{f}_g:g\in\mathcal{G}\},\] as established in Lemma 4, we obtain the following convergence result.

In scenario [40S241], we have \(\Theta_0=\Theta=\mathbb{R}\). Instead of introducing a surrogate density, we work directly with the class of likelihood ratio functions \[\mathcal{L} \mathrel{\vcenter{:}}= \{l_g : g\in\mathcal{G}\}.\] A corresponding entropy bound for this class, established in Lemma 7, yields the following result.

3 Conclusions and discussion↩︎

Focusing on a broad class of exponential family mixture models, this paper makes two main contributions. First, we propose a data-compression strategy that changes the sample-size dependence of likelihood evaluations in NPMLE computation from linear to polylogarithmic order. Beyond its computational benefit, this perspective also has a clear theoretical implication: the fitting procedure depends only on the information contained in the first few moments. The same construction extends naturally to multivariate settings; see Section 4.2 for an illustration in the heteroscedastic Gaussian sequence model. More broadly, the idea applies whenever one seeks to evaluate expectations of smooth functions with respect to an empirical distribution.

Second, we establish an almost parametric rate for the NPMLE in marginal density estimation. In contrast to the classical theory of [7], [18], our analysis relies on entropy control for auxiliary classes beyond the marginal density class and uses complex-analytic arguments, leading to a more streamlined proof. The resulting theory not only provides statistical support for the approximate NPMLE developed in the first part of the paper, but also suggests a general framework for analyzing more complicated, including multivariate, models on a case-by-case basis.

Acknowledgement↩︎

The author thanks Xin Bing, Jiaying Gu, Ricardo Baptista and Wenlong Mou for helpful discussions and Stanislav Volgushev for substantial feedback during the preparation of this manuscript.

4 Supplement↩︎

4.1 Remarks on likelihood tolerance levels↩︎

The statistical requirement on the likelihood gap \(\Delta_n\) in 6 depends on the task. If \(\Delta_n=o(1)\), then \(\tilde{g}\) is asymptotically indistinguishable from \(\hat{g}\) from the perspective of likelihood ratio testing, and is therefore suitable for certain testing procedures, such as homogeneity tests [23], [24]. Moreover, for the Gaussian location model, [7] and [13] showed that the plug-in estimators based on \(\tilde{g}\) achieve nearly parametric performance in both density estimation and empirical Bayes estimation whenever \(\Delta_n\) is of logarithmic order, that is, \(\Delta_n = O\bigl((\log n)^\gamma\bigr)\) for some \(\gamma>0\). An analogous result is also available for the Poisson model [17]. For these two models, our recent work [25] further shows that the plug-in estimators based on \(\tilde{g}\) attain exact parametric performance in these estimation tasks when \(\Delta_n = O(1)\), provided that the true mixing distribution \(g_0\) is finitely discrete and \(\Theta_0\) is bounded.

4.2 Heteroscedastic Gaussian sequence model↩︎

This section extends the data-compression strategy from Section 2.1 to the heteroscedastic Gaussian sequence model [26].

1. Consider \[X_i\mid(\theta_i,\sigma_i^2)\overset{\mathrm{ind.}}{\sim}\mathcal{N}(\theta_i,\sigma_i^2), \qquad \theta_i\overset{\mathrm{i.i.d.}}{\sim} g_0, \qquad i=1,\dots,n,\] where \(\{(X_i,\sigma_i^2)\}_{i\in[n]}\) are observed, and \(g_0\) is interpreted as a common prior distribution belonging to the class 2 with \[\Theta_0 \mathrel{\vcenter{:}}= \{\theta\in\mathbb{R}: |\theta|\le M\}.\]

Under [40HG41], the marginal density of \(X_i\) given \(\sigma_i^2\) is \[f_{g_0}(x|\tau_i)\mathrel{\vcenter{:}}= \sqrt{\frac{\tau_i}{2\pi}}\int \exp\Big(-\frac{\tau_i(x-\theta)^2}{2}\Big)\,\mathrm{d}g_0(\theta),\] where \(\tau_i\mathrel{\vcenter{:}}= 1/\sigma_i^2\). The NPMLE in this setting is defined by \[\hat{g}\mathrel{\vcenter{:}}= \arg\sup_{g\in\mathcal{G}} \int \log f_g(x|\tau)\,\mathrm{d}P_n(x,\tau),\] where \(P_n\) is the empirical measure based on \(\{(X_i,\tau_i)\}_{i\in[n]}\).

As before, given a sequence of integers \(\{J_n\}_{n\ge 1}\), let \[P_{J_n}\mathrel{\vcenter{:}}= \text{a quadrature rule matching all moments of }P_n\text{ up to total degree }J_n.\] We construct this quadrature rule via Carathéodory–Tchakaloff subsampling [27]. This procedure produces a quadrature rule with at most \(\binom{J_n+2}{2}\) support points and satisfying \[\mathrm{supp}(P_{J_n})\subseteq \mathrm{supp}(P_n).\] We then define \[\hat{g}_{J_n}\mathrel{\vcenter{:}}= \arg\sup_{g\in\mathcal{G}} \int \log f_g(x|\tau)\,\mathrm{d}P_{J_n}(x,\tau).\] The following theorem extends Theorem 1 and Corollary 1 to the heteroscedastic Gaussian sequence model.

As shown in [26], a likelihood guarantee of this form for \(\hat{g}_{J_n}\) is already sufficient to obtain empirical Bayes risk guarantees.

4.3 Simulations↩︎

In this section, we consider the Gaussian location mixture model [40GL41] and generate data \(X_1,\dots,X_n\) from \(f_{g_0}\), where \(g_0\) is the uniform distribution on the interval \([-2,2]\). To approximate \(\hat{g}\) and \(\hat{g}_{J_n}\), we adopt a discretization approach, under which all computations are restricted to mixing distributions supported on a finite set of fixed grid points. In practice, we take 300 points uniformly spaced over the interval \[[\min_{i\in[n]} X_i,\;\max_{i\in[n]} X_i].\]

Since [9], the interior-point method has been the standard implementation under this framework, and it is also adopted by the R package REBayes for empirical Bayes applications [28]. More recently, [10] proposed an augmented Lagrangian method, which implicitly exploits the sparsity structure of the NPMLE [20] and thereby substantially accelerates computation. We therefore compare the following three methods:

• Approximate the NPMLE 1 using the interior-point method.

• Approximate the NPMLE 1 using the augmented Lagrangian method.

• Implement Algorithm 1, while approximating 5 using the interior-point method.

Algorithm 1 is not a direct competitor to (IPM) or (ALM), but rather a complementary procedure containing an additional preprocessing step. In principle, our approach could also be combined with the augmented Lagrangian method to further reduce computation time. In our framework, however, the main computational bottleneck is the preprocessing step, so such a combination yields only modest additional gains. That said, this hybrid approach may still be useful when one wishes to compute the NPMLE under multiple models on the same dataset, as is often the case when comparing several competing specifications.

We consider the case \(n=100{,}000\), set \(J_n=25\) for our method, and repeat the experiment 10 times. Let \(\tilde{g}\) denote a resulting estimator. Figure 2 compares the three methods in terms of computation time (in seconds), log-likelihood \(\ell_n(f_{\tilde{g}})\), and the sum of squared errors \[\sum_{i=1}^n \left(\theta_i-\frac{\int \theta\, p(X_i | \theta)\,\mathrm{d}\tilde{g}(\theta)}{f_{\tilde{g}}(X_i)}\right)^2,\] where \(\theta_i\) is the latent variable associated with \(X_i\) under the data-generating model \[X_i \mid \theta_i \overset{\mathrm{ind.}}{\sim} \mathcal{N}(\theta_i,1), \qquad \theta_i \overset{\mathrm{i.i.d.}}{\sim} g_0, \qquad i=1,\dots,n.\] The figure shows that our approach is substantially faster than the other two methods, while achieving statistically indistinguishable performance.

4.4 Bernstein’s theorem↩︎

It was first shown in §61 of [29] that analytic functions admit polynomial approximations with exponential convergence. A modern treatment appears as Theorem 8.2 of [30], which we restate below.

Theorem 5 extends to the multivariate setting; see [31] and [32]. We record a convenient formulation and include a brief proof for completeness.

4.5 Proof of main results in Section 2.1↩︎

Under [40EF41], for any \(g \in \mathcal{G}\) with compact support, it follows from Morera’s theorem (Theorem 5.1 of [34]) that the likelihood ratio function \(l_g(x)\) extends to an entire function. In addition, \(\log l_g(x)\) admits an analytic extension to a complex neighborhood of the real line. For \(z = x + iy \in \mathbb{C}\), we denote by \(\Re z \mathrel{\vcenter{:}}= x\) and \(\Im z \mathrel{\vcenter{:}}= y\) its real and imaginary parts.

Because the exact estimator \(\hat{g}_{J_n}\) in 5 is often intractable due to the infinite-dimensional nature of the set \(\mathcal{G}\), an approximate version is needed. Therefore, assuming the upper bound in 7 is available, we restrict our focus to approximate estimators \[\label{eq:tildegJn} \tilde{g}_{J_n}\in\Big\{g\in\mathcal{G}:\mathrm{supp}(g)\subseteq[-M_n,M_n],\int\log l_g(x)\mathrm{d}P_{J_n}(x)\ge\int\log l_{\hat{g}_{J_n}}(x)\mathrm{d}P_{J_n}(x)-\varepsilon_n\Big\},\tag{11}\] where \(\{\varepsilon_n\}_{n\ge1}\) is a sequence of tolerance levels. Accordingly, we present a theorem that accounts for this additional approximation error, yielding Theorem 1 as a special case when \(\varepsilon_n\equiv0\).

4.6 Proof of main results in Section 2.2↩︎

We first recall the \(\varepsilon\)-covering number of a general set \(\mathcal{S}\) with respect to a semimetric \(\rho\): \[N(\varepsilon,\mathcal{S},\rho) \mathrel{\vcenter{:}}= \inf\Bigl\{ N:\exists\, s_1,\dots,s_N\in\mathcal{S}\;\text{such that}\; \mathcal{S}\subseteq\bigcup_{j=1}^N B_\rho(s_j,\varepsilon) \Bigr\},\] where \[B_\rho(s,\varepsilon)\mathrel{\vcenter{:}}=\{s'\in\mathcal{S}:\rho(s,s')<\varepsilon\}.\]

Theorem 5 directly yields an entropy bound for a class of analytic functions. An analogous bound for the multivariate case is given in Theorem 2.7.16 of [36].

4.7 Proof of Theorem 4↩︎

Recalling the notation from Section 4.2, we establish the following lemma.

4.8 Auxiliary results↩︎

Our first auxiliary lemma clarifies how scenarios [40S141] and [40S241] imply the light-tail condition [40LT41].

In scenario [40S141], 7 holds with \(M_n=M\). An analogous result holds under scenario [40S241].

References↩︎

---

1. For example, Section 1.3 of [3] analyzes a methylation dataset with \(n=439{,}918\).↩︎

2. In practice, \(\hat{g}_{J_n}\) is rarely computed exactly. Instead, an approximation error is introduced to account for its deviation from the true maximizer. Theorem 7 formalizes this, yielding a stronger version of Theorem 1.↩︎

3. The condition \(|X|_n\ge 1\) is imposed only for simplicity of presentation, and will be omitted in subsequent applications of the lemma.↩︎