Convergence rates of a partition based Bayesian multivariate density estimation method
We study a class of non-parametric density estimators under Bayesian settings. The estimators are obtained by adaptively partitioning the sample space. Under a suitable prior, we analyze the concentration rate of the posterior distribution, and demonstrate that the rate does not directly depend on the dimension of the problem in several special cases. Another advantage of this class of Bayesian density estimators is that it can adapt to the unknown smoothness of the true density function, thus achieving the optimal convergence rate without artificial conditions on the density. We also validate the theoretical results on a variety of simulated data sets.
Note: Below, I use [#M] for references in the main paper and [#S] for references in the supplement, since these are indexed differently.
Summary: This paper proposes and analyzes a Bayesian approach to nonparametric density estimation. The proposed method is based on approximation by piecewise-constant functions over a binary partitioning of the unit cube, using a prior that decays with the size of the partition. The posterior distribution of the density is shown to concentrate around the true density f_0, at a rate depending on the smoothness r of f_0, a measure in terms of how well f_0 can be approximated by piecewise-constant functions over binary partitionings. Interestingly, the method automatically adapts to unknown r, and r can be related to more standard measures of smoothness, such as Holder continuity, bounded variation, and decay rate of Haar basis coefficients. As corollaries, posterior concentration rates are shown for each of these cases; in the Holder continuous case, this rate is minimax optimal.
Major Comments:
The theoretical results of this paper appear quite strong to me. In particular, the results on adaptivity (to unknown effective dimension and smoothness) are quite striking, especially given that this seems an intrinsic part of the estimator design, rather than an additional step (as in, e.g., Lepski's method). Unfortunately, I'm not too familiar with Bayesian or partition-based approaches to nonparametric density estimation, and my main issue is that the relation of this work to previous work isn't very clear. Looking through the supplement, it appears that most of proofs are based on the results of [9M] and [14M], so there is clearly some established closely related literature. I'd likely raise my score if this relation could be clarified, especially regarding the following two questions:
1) Is the prior introduced in Section 2.2 novel? If so, how does it differ from similar prior work (if such exists), and, if not, which aspects, precisely, of the paper are novel?
2) Much of the proof of Theorem 3.1 appears to depend on results from prior work (e.g., Lemmas A.2, A.4, B.1, and B.2, and Theorem A.3 are from [4S] and [6S]). Corrolaries 3.2, 3.3, and 3.4 all follow by combining Theorem 3.1 with results from [4S] and [1S] that relate the respective smoothness condition to smoothness in terms of approximability by piecewise-constant functions on binary partitions. Thus, much of this work appears to be a re-working of previous work, while Lemma B.4 and the remainder of Theorem 3.1 appear to be the main contributions. My question is: at a high level, what were the main limitations of the previous results/proof techniques that had to be overcome to prove Theorem 3.1, and, if it's possible to summarize, what were the main innovations required to overcome these?
Minor Comments:
Lines 36-44: It would help to mention here that rates are measured in Hellinger divergence.
Line 40-41: (the minimax rate for one-dimensional Hölder continuous function is (n/log n)^{−\beta/(2\beta+1)}): If I understand correctly, the log factors stem from the fact that \beta is unknown (I usually think of the minimax rate as n^{−\beta/(2\beta+1)}, when \beta is treated as known). If this is correct, it would help to mention this here.
Line 41: small typo: "continuous function" should be "continuous functions"
Lines 60-72: There's an issue with the current notation: As written, \Omega_2,...,\Omega_I aren't well-defined partition by this recursive procedure. If we split \Omega_j at step i, then \Omega_j should be removed from the list of partitions and replaced by two smaller partitions. I think I understand what is meant (Figure 1 is quite clear), but I don't see a great way to explain this with concise mathematical notation - the options I see are (a) describing the process as a tree with a set at each node, and then taking all the leaves of the tree or (b) using a pseudocode notation where the definition of \Omega_j can change over the course of the recursive procedure.
Line 185: I believe the minimax rate for the bounded variation class is of order n^(-1/3) (see, e.g., Birgé, Lucien. "Estimating a density under order restrictions: Nonasymptotic minimax risk." The Annals of Statistics (1987): 995-1012.) Perhaps this is worth mentioning?
Lines 157-175: Section 3.1 considers the case of a weak-\ell^p constraint on the Haar basis coefficients of the density. The paper calls this a spatial sparsity constraint. I feel this is misleading, since the sparsity assumption is over the Haar basis coefficients, rather than over spatial coordinates (as in [1M]). As a simple example, the uniform distribution is extremely sparse in the Haar basis, but is in no way spatially concentrated. I believe this is actually a smoothness assumption, since Haar basis coefficients can be thought of as identifying the discontinuities of a piecewise constant approximation function. Indeed, the weak-\ell^p constraint on the Haar coefficients is roughly equivalent to a bound on the Besov norm of the density (see Theorem 5.1 of Donoho, David L. "De-noising by soft-thresholding." IEEE transactions on information theory 41.3 (1995): 613-627.)
Line 246: small typo: "based adaptive partitioning" should be "based on adaptive partitioning".
Line 253: Citation [1M] is missing the paper title. I believe the intended citation is "Abramovich, F., Benjamini, Y., Donoho, D. L., & Johnstone, I. M. (2006). Special invited lecture: adapting to unknown sparsity by controlling the false discovery rate. The Annals of Statistics, 584-653."