betaFeedback

WorksMathematics

Greedy Empirical Bayes for Density Estimation

Abstract

Bayesian nonparametric density estimation is challenging in high dimensions, where traditional approaches like the Dirichlet process (DP) mixture rely on computationally intensive Markov chain Monte Carlo or approximations. We introduce the partition posterior bootstrap (PPB), where a flexible prior is constructed by smoothing a DP over a partition of the sample space. Conditioned on this partition, exact posterior sampling reduces to a simple Bayesian bootstrap-like algorithm. Importantly, we select the partition using a greedy empirical Bayes (GEB) algorithm which scales to high dimensions and large sample sizes. GEB greedily maximizes the closed-form marginal likelihood via local split decisions arising naturally from its factorization, yielding an adaptive binary tree partition. Our key theoretical result is that the GEB tree belongs to an admissible family with high probability, splitting all identifiable signals while avoiding over-splitting noise. As a result, the PPB posterior with the GEB tree attains adaptive contraction rates. Our theory holds under weak, verifiable assumptions, which we demonstrate in numerous examples. Empirically, PPB delivers accurate density estimates and uncertainty quantification at a fraction of the computational cost of other approaches, making it a practical off-the-shelf choice for high-dimensional Bayesian density estimation with theoretical guarantees.

Introduction

Density estimation given independent and identically distributed (i.i.d.) observations from a distribution PP is of key importance in statistics, where downstream tasks such as prediction or functional estimation depend on having an accurate density estimate. As datasets grow in size, it is important to identify flexible methods which remain scalable in high dimensions or with large sample sizes, while providing uncertainty quantification.

Bayesian nonparametric methods are popular for density estimation due to their flexibility, regularization of the density estimates, and built-in uncertainty quantification. A classic example is the Dirichlet process mixture model (DPMM) [9, 20] which models the density as an infinite mixture model, and typically relies on Markov chain Monte Carlo (MCMC) for inference. Besides mixture modeling, another popular class of methods is based on Pólya trees (PT; Lavine [ [17]) which recursively partition the sample space. While PTs are conjugate and computationally scalable, their performance relies on a fixed partition which limits adaptivity, leading to extensions such as Optional Pólya Trees (OPT; Wong and Ma [ [35]) which allow adaptive choice of the splitting variable and stopping. However, exact posterior inference for OPTs requires recursive marginalization over possible partition trees, making computation prohibitively expensive in higher dimensions. More recent extensions, such as hidden Markov Pólya trees (HMPT; Awaya and Ma [ [2]), additionally allow adaptive splitting locations and employ sequential Monte Carlo (SMC) to approximate the posterior over partitions to improve scalability in high dimensions.

While the more adaptive Bayesian nonparametric methods offer considerable flexibility, they face various computational challenges due to their reliance on MCMC, SMC or expensive recursive marginalization. In addition to their computational demands, existing Bayesian nonparametric methods often require careful specification of prior hyperparameters and algorithm settings, which can influence both estimation accuracy and computational efficiency. Outside the context of density estimation, but motivated by similar challenges in computation and hyperparameter tuning, recent work has revisited the Bayesian bootstrap [32, 24] as a means for default and scalable nonparametric inference on Euclidean functionals. Fong et al. [ [11] elicit a simple Dirichlet process (DP) prior on the probability measure and leverage the conjugacy of the DP to obtain a highly scalable posterior bootstrap algorithm for inference on parameters which does not require MCMC. Another key advantage is that only a scalar prior count hyperparameter and base measure are required to be specified. The scalability and ease of the posterior bootstrap have led to applications in robust inference [7], high-dimensional regression [25, 26], and the use of generative models for prior construction [27]. Connections to the Pólya urn have also spurred recent advances in predictive Bayes [13, 12]. However, due to the reliance on the DP, the posterior bootstrap cannot naturally handle the case where the target functional requires a density, or the density itself is of interest.

Our contribution

In this work, we follow in the spirit of the posterior bootstrap, and consider a simple default prior on the density by smoothing a DP over a partition of the sample space, yielding a closed-form posterior we term the partition posterior bootstrap (PPB). The key to maintaining scalability is to treat the partition of the sample space as a nonparametric hyperparameter, whose efficient selection forms the focus of the paper. This avoids the need for sampling or integration over nonparametric latent structures, such as the mixture allocations in DPMMs or the partitions of the sample space in OPTs and HMPTs. Our approach is a natural generalization of Bayesian histogram approaches as introduced in Hjort [1996], where Dirichlet conjugacy is also exploited. In particular, Simensen et al. [ [34] proposed a univariate Bayesian irregular histogram estimator which adaptively selects the number and locations of bins through approximate maximum a posteriori model selection, using a combination of search heuristics and dynamic programming. However, their optimization procedure exploits the natural ordering of intervals in one dimension and does not readily extend to multivariate settings.

Our main methodological contribution is a scalable selection procedure for the partition: we exploit a natural recursive factorization of the marginal likelihood under the smoothed DP prior, yielding closed-form Bayes factors for local splitting decisions. This motivates a deterministic greedy empirical Bayes (GEB) algorithm that recursively constructs a binary tree partition of the space. At each node, we evaluate the Bayes factors associated with potential splitting variables and locations, selecting the split with the largest Bayes factor and stopping if none exceeds one. Thus, both the partition structure and stopping decisions are automatically determined through local Bayesian model comparisons. Crucially, our GEB algorithm remains computationally scalable in higher dimensions and with large sample sizes, and is orders of magnitude faster than competing Bayesian methods while maintaining excellent performance in practice.

Our main theoretical contribution is to establish guarantees for the PPB posterior based on the partition actually selected by the GEB algorithm. This contrasts with existing results which study either globally optimal estimators (sieve MLE or MAP; [19, 34] or full posteriors over partitions [Castillo and Randrianarisoa, 2022, Liu et al. [19], both of which are computationally challenging or infeasible to obtain in higher dimensions. Our results can also be viewed as extending the asymptotic theory of empirical Bayes [29, 30] to the setting of data-adaptive recursive partitions. To handle the greedy nature of our algorithm, we introduce a family of admissible trees and show that the GEB partition belongs to this family with high probability, capturing all identifiable signals while avoiding unnecessary splitting in regions dominated by noise. We then establish contraction rates for the resulting PPB posterior, demonstrating adaptation to β\beta-Hölder continuity for 0<β≤10 < \beta\le1, anisotropic smoothness, axis-aligned discontinuities, and variable sparsity.

We conclude the introduction with a visualization of the partition obtained by our GEB algorithm in a simple simulation.

Example 1 (GEB partition). Consider the two-dimensional density formed as a product of independent marginals, each equal to the mixture 0.50.5 Beta(2,2)+0.5(2, 2) + 0.5 Uniform(0,1)(0, 1). Figure 1 compares the true density and three histogram estimates based on n=100,000n = 100{,}000 samples and different partitions. Panel (b) shows a standard equal-width histogram with a 7×7=497 \times7 = 49 grid, which struggles to capture the density’s geometry. Panel (c) depicts a partition guided by the true density’s contour level sets, which acts as an ideal but infeasible benchmark. Panel (d) then illustrates the GEB partition, which chooses 49 rectangular bins and approximates the contours of the true density well. The estimation quality is verified in Table 1, where the average test log-likelihood on held-out data is noticeably higher for the GEB partition than for the equal-width partition and close to the contour partition. Importantly, the number of bins is chosen automatically, and the total run-time is only 0.1 seconds.

Figure 1. Density estimates for a two-dimensional product mixture.

True densityEqual-widthContour-levelGEB tree
Avg. test log-likelihood (×10−2\times10^{-2})5.304.645.034.93

Table 1. Held-out average test log-likelihood.

We now outline the structure of the paper. § 2 introduces the smoothed DP prior and the resulting PPB algorithm. § 3 then addresses the central challenge of choosing the partition with our GEB algorithm, and § 4 establishes the theoretical guarantees of the approach. Finally, § 5 presents simulation and real-data experiments demonstrating the method’s performance and substantial computational savings over existing Bayesian nonparametric alternatives. We conclude with a discussion in § 6.

Partition posterior bootstrap

Let PP be the data-generating distribution with Lebesgue density pp from which we observe nn i.i.d. observations x1:n=(x1,…,xn)x_{1:n} = (x_1, \ldots, x_n) where xi∈A⊂RDx_i \in\mathcal{A} \subset\mathbb{R}^{D}. For a probability measure μ\mu and measurable sets AA, BB with μ(A)>0\mu(A) > 0, we adopt the shorthand μA:=μ(A)\mu_A := \mu(A) and μB∣A:=μA∩B/μA\mu_{B \mid A} := \mu_{A \cap B}/\mu_A throughout this paper. Let P={A1,…,AM}\mathcal{P} = \{A_1, \ldots, A_M\} denote a measurable partition of the sample space A\mathcal{A}, and let NA=∑i=1n1(xi∈A)N_A = \sum_{i=1}^{n} \mathbb{1}(x_i \in A).

The posterior bootstrap begins by specifying the nonparametric prior DP⁡(α,H)\operatorname{DP}(\alpha, H), where α\alpha is the concentration parameter and HH is a base measure representing our prior guess of PP. It is well known that the posterior given x1:nx_{1:n} is another Dirichlet process. However, a draw from a DP is almost surely discrete, making it unsuitable for modeling a continuous density pp directly. To address this, we consider augmenting the DP prior with a smoothing partition P\mathcal{P}, which preserves tractability in posterior sampling and admits a natural marginal likelihood which we exploit in § 3.

We now augment the DP prior of the posterior bootstrap with a partition P\mathcal{P}, where we assume HA>0H_A > 0 for every A∈PA \in\mathcal{P}. Let HH have a Lebesgue density hh, and assume that P≪HP \ll H. We then construct our smoothed DP prior on the density pp as

f(x)=∑A∈PGAh(x∣A),G∼DP⁡(α,H),(1)f(x) = \sum_{A \in\mathcal{P}} G_A h(x \mid A), \qquad G \sim\operatorname{DP}(\alpha, H), \tag*{(1)}

where h(x∣A)h(x \mid A) is the conditional density of the form

h(x∣A)=1(x∈A)h(x)HA.h(x \mid A) = \mathbb{1}(x \in A) \frac{h(x)}{H_A}.

The partition P\mathcal{P} thus controls the resolution at which the density ff can depart from the base density, where the shape of hh is retained locally within each AA.

As in the posterior bootstrap, the underlying random probability measure is specified through a single DP⁡(α,H)\operatorname{DP}(\alpha, H) prior. The additional ingredient is the partition P\mathcal{P} used to smooth this measure, which will be learned using a GEB algorithm in § 3. Our prior still contains simple and interpretable elements, and another useful feature of our specific prior is that it preserves the base density as the prior mean for any choice of P\mathcal{P}, that is

E[f(x)∣P]=∑A∈PHAh(x∣A)=h(x).\mathbb{E}[f(x) \mid\mathcal{P}] = \sum_{A \in\mathcal{P}} H_A h(x \mid A) = h(x).

Our construction can be viewed as a natural extension of the Bayesian histogram formulations of Hjort [ [15] and Simensen et al. [ [34] by replacing the uniform density within each cell with the conditional base density h(⋅∣A)h(\cdot\mid A), giving the above prior mean property. When HH is uniform, the construction coincides with the usual Dirichlet histogram model, and more generally our prior belongs to the class of smoothed Dirichlet process priors discussed by Hjort [1996]. The particular partition smoothing used here enables a simple posterior bootstrap algorithm for inference on the density or its functionals, which we outline in the next subsection. As we will see in § 3, the above prior has a marginal likelihood structure that is particularly suitable for our GEB algorithm for the partition.

Posterior computation

Since (GA:A∈P)∼Dirichlet⁡(αHA:A∈P)(G_A : A \in\mathcal{P}) \sim\operatorname{Dirichlet}(\alpha H_A : A \in\mathcal{P}), posterior inference conditioned on P\mathcal{P} follows from well-known properties of Dirichlet conjugacy which is usually leveraged for Bayesian histograms. A draw from the posterior distribution of pp given x1:nx_{1:n} can be represented as

f(x)=∑A∈PG~Ah(x∣A),G~∼DP⁡(α+n,αH+∑i=1nδxiα+n).f(x) = \sum_{A \in\mathcal{P}} \widetilde{G}_A h(x \mid A), \qquad\widetilde{G} \sim\operatorname{DP}\left(\alpha+n,\frac{\alpha H+\sum_{i=1}^{n}\delta_{x_i}}{\alpha+n}\right).

We choose the above representation for the posterior as it retains the smoothed DP interpretation. Unlike the posterior bootstrap, our prior induces a posterior predictive density and marginal likelihood. The posterior predictive density given P\mathcal{P}, which is the posterior mean of ff given P\mathcal{P}, is simply a reweighted version of the base density hh:

fˉ(x)=∑A∈PGˉAh(x∣A),GˉA=αHA+NAα+n.(2)\bar{f}(x) = \sum_{A \in\mathcal{P}} \bar{G}_A h(x \mid A), \qquad\bar{G}_A = \frac{\alpha H_A + N_A}{\alpha+n}. \tag*{(2)}

The marginal likelihood for P\mathcal{P}, which will be the main focus of § 3, is then

M(P)=Γ(α)Γ(α+n)∏A∈P(Γ(αHA+NA)Γ(αHA)∏i:xi∈Ah(xi∣A)).(3)\mathcal{M}(\mathcal{P}) = \frac{\Gamma(\alpha)}{\Gamma(\alpha+n)} \prod_{A \in\mathcal{P}} \left(\frac{\Gamma(\alpha H_A+N_A)}{\Gamma(\alpha H_A)} \prod_{i:x_i \in A} h(x_i \mid A)\right). \tag*{(3)}

Conditional on P\mathcal{P}, posterior sampling involves a partition posterior bootstrap as outlined in Algorithm 1. Functionals with closed-form expressions can be evaluated directly from each density draw. For a risk minimizer θ(f)=arg⁡min⁡θ∈Θ∫ℓ(x,θ)f(x) dx\theta(f) = \arg\min_{\theta\in\Theta} \int\ell(x,\theta) f(x)\,\mathrm{d}x, the expected loss can instead be approximated by Monte Carlo through S−1∑s=1Sℓ(xs,θ)S^{-1}\sum_{s=1}^{S} \ell(x_s,\theta), where xsx_s is drawn by first selecting a cell AA with probability GA(b)G_A^{(b)} and then drawing a sample from H(⋅∣A)H(\cdot\mid A).

Algorithm 1: Partition posterior bootstrap

  1. Compute cell counts NA=∑i=1n1(xi∈A)N_A = \sum_{i=1}^{n} \mathbb{1}(x_i \in A) for all A∈PA \in\mathcal{P}

  2. for b←1b \leftarrow1 to BB do

    1. Draw (GA(b):A∈P)∼Dirichlet⁡(αHA+NA:A∈P)(G_A^{(b)} : A \in\mathcal{P}) \sim\operatorname{Dirichlet}(\alpha H_A + N_A : A \in\mathcal{P})

    2. Set f(b)(x)=∑A∈PGA(b)h(x∣A)f^{(b)}(x) = \sum_{A \in\mathcal{P}} G_A^{(b)} h(x \mid A)

    3. Compute θ(b)=θ(f(b))\theta^{(b)} = \theta(f^{(b)})

  3. end

  4. return {f(1),…,f(B)}\{f^{(1)},\ldots,f^{(B)}\} and {θ(1),…,θ(B)}\{\theta^{(1)},\ldots,\theta^{(B)}\}

Greedy empirical Bayes for partition selection

In this section, we view P\mathcal{P} as a nonparametric structural hyperparameter to be selected using the marginal likelihood M(P)\mathcal{M}(\mathcal{P}), which is a natural criterion due to connections to prediction [10]. Since the space of partitions is enormous, global optimization is infeasible in practice. We thus seek a greedy alternative, as the PPB marginal likelihood lends itself to a natural scalable algorithm based on recursive partitioning.

Split Bayes factors

We begin by studying the key quantity related to the marginal likelihood defined in (3), which drives our greedy empirical Bayes algorithm. Consider a partition P\mathcal{P}, and define the refined partition P′\mathcal{P}' which splits a cell A∈PA \in\mathcal{P} into disjoint cells A0,A1A_0,A_1 so A=A0∪A1A = A_0 \cup A_1, that is P′=P∖{A}∪{A0,A1}\mathcal{P}' = \mathcal{P} \setminus\{A\} \cup\{A_0,A_1\}. We now define the ratio of marginal likelihoods BA(A0,A1):=M(P′)/M(P)\mathcal{B}_A(A_0,A_1) := \mathcal{M}(\mathcal{P}')/\mathcal{M}(\mathcal{P}) as the split Bayes factor at AA, which measures the evidence in favor of splitting AA into A0,A1A_0,A_1 relative to leaving AA unsplit. Crucially, the split Bayes factor satisfies the identity

References

  1. [1]A. Agresti. Categorical Data Analysis. John Wiley & Sons, Hoboken, NJ, 3rd edition, 2013.
  2. [2]N. Awaya and L. Ma. Hidden Markov Pólya trees for high-dimensional distributions. Journal of the American Statistical Association, 119(545):189–201, 2024.
  3. [3]A. Barron, L. Birgé, and P. Massart. Risk bounds for model selection via penalization. Probability theory and related fields, 113(3):301–413, 1999.DOI
  4. [4]A. Bhattacharya, D. Pati, and D. Dunson. Anisotropic function estimation using multi-bandwidth Gaussian processes. The Annals of Statistics, 42(1):352, 2014.pubmed.ncbi.nlm.nih.gov/25288827
  5. [6]C. M. Chi, P. Vossler, Y. Fan, and J. Lv. Asymptotic properties of high-dimensional random forests. The Annals of Statistics, 50(6):3415–3438, 2022.arxiv.org/abs/2004.13953
  6. [7]C. Dellaporta, J. Knoblauch, T. Damoulas, and F.-X. Briol. Robust Bayesian inference for simulator-based models via the MMD posterior bootstrap. In International Conference on Artificial Intelligence and Statistics, pages 943–970. PMLR, 2022.
  7. [8]M. Ernst, G. Reinert, and Y. Swan. First-order covariance inequalities via Stein’s method. Bernoulli, 26(3):2051 – 2081, 2020. doi: 10.3150/19-BEJ1182.
  8. [9]T. S. Ferguson. Bayesian density estimation by mixtures of normal distributions. In Recent Advances in Statistics, pages 287–302. Elsevier, 1983.
  9. [10]E. Fong and C. C. Holmes. On the marginal likelihood and cross-validation. Biometrika, 107(2):489–496, 01 2020. ISSN 0006-3444. doi: 10.1093/biomet/asz077.DOI
  10. [11]E. Fong, S. Lyddon, and C. Holmes. Scalable nonparametric sampling from multimodal posteriors with the posterior bootstrap. In International Conference on Machine Learning, pages 1952–1962. PMLR, 2019.arxiv.org/abs/1902.03175
  11. [12]E. Fong, C. Holmes, and S. G. Walker. Martingale posterior distributions. Journal of the Royal Statistical Society Series B: Statistical Methodology, 85(5):1357–1391, 2023.arxiv.org/abs/2103.15671
  12. [13]S. Fortini and S. Petrone. Quasi-Bayes properties of a procedure for sequential learning in mixture models. Journal of the Royal Statistical Society Series B: Statistical Methodology, 82(4):1087–1114, 2020.DOI
  13. [14]S. Ghosal and A. W. van der Vaart. Fundamentals of Nonparametric Bayesian Inference, volume 44. Cambridge University Press, 2017.
  14. [15]N. L. Hjort. Bayesian approaches to non- and semiparametric density estimation. In J. O. Berger, J. M. Bernardo, A. P. Dawid, and A. F. M. Smith, editors, Bayesian Statistics 5, pages 223–254. Oxford University Press, 1996. With discussion contributions.
  15. [16]M. Kelly, R. Longjohn, and K. Nottingham. The UCI Machine Learning Repository, 2023.
  16. [17]M. Lavine. Some aspects of Polya tree distributions for statistical modelling. The Annals of Statistics, pages 1222–1235, 1992.DOI
  17. [18]G. Leoni. A first course in Sobolev spaces: Second edition. American Mathematical Society, 2017.
  18. [19]L. Liu, D. Li, and W. H. Wong. Convergence rates of a class of multivariate density estimation methods based on adaptive partitioning. Journal of Machine Learning Research, 24(50):1–64, 2023.
  19. [20]A. Y. Lo. On a class of Bayesian nonparametric estimates: I. Density estimates. The Annals of Statistics, pages 351–357, 1984.DOI
  20. [23]R. Mazumder and H. Wang. On the convergence of CART under sufficient impurity decrease condition. Advances in Neural Information Processing Systems, 36:57754–57782, 2023.arxiv.org/abs/2310.17114
  21. [24]M. A. Newton and A. E. Raftery. Approximate Bayesian inference with the weighted likelihood bootstrap. Journal of the Royal Statistical Society Series B: Statistical Methodology, 56(1):3–26, 1994.DOI
  22. [25]M. A. Newton, N. G. Polson, and J. Xu. Weighted Bayesian bootstrap for scalable posterior distributions. Canadian Journal of Statistics, 49(2):421–437, 2021.DOI
  23. [26]L. Nie and V. Ročková. Bayesian bootstrap spike-and-slab LASSO. Journal of the American Statistical Association, 118(543):2013–2028, 2023.arxiv.org/abs/2011.14279
  24. [27]S. O’Hagan and V. Ročková. AI-powered Bayesian inference. arXiv preprint arXiv:2502.19231, 2025.
  25. [28]G. Papamakarios, T. Pavlakou, and I. Murray. Masked autoregressive flow for density estimation. In Advances in Neural Information Processing Systems, volume 30, 2017.arxiv.org/abs/1705.07057
  26. [29]S. Petrone, J. Rousseau, and C. Scricciolo. Bayes and empirical Bayes: do they merge? Biometrika, 101(2):285–302, 2014. ISSN 0006-3444.
  27. [30]S. Rizzelli, J. Rousseau, and S. Petrone. Empirical Bayes in Bayesian learning: understanding a common practice. Journal of the American Statistical Association, 0:1–89, 2026.
  28. [31]K. Rogers. Sharp van der corput estimates and minimal divided differences. Proceedings of the American Mathematical Society, 133(12):3543–3550, 2005.arxiv.org/abs/math/0311013
  29. [32]D. B. Rubin. The Bayesian bootstrap. The Annals of Statistics, pages 130–134, 1981.DOI
  30. [33]W. Shen, S. T. Tokdar, and S. Ghosal. Adaptive Bayesian multivariate density estimation with Dirichlet mixtures. Biometrika, 100(3):623–640, 2013.DOI
  31. [34]O. H. Simensen, D. Christensen, and N. L. Hjort. Random irregular histograms. Computational Statistics & Data Analysis, 220:108367, 2026.arxiv.org/abs/2505.22034
  32. [35]W. H. Wong and L. Ma. Optional Pólya Tree and Bayesian inference. The Annals of Statistics, 38(3):1433–1459, 2010. ISSN 0090-5364.DOI

Paper details

vlnc:W_qs86qfkj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT Astra

View statement
Looking for related papers…
Contents