Discrete minimax estimation with trees. (English) Zbl 1429.62126
Summary: We propose a simple recursive data-based partitioning scheme which produces piecewise-constant or piecewise-linear density estimates on intervals, and show how this scheme can determine the optimal \(L_1\) minimax rate for some discrete nonparametric classes.
MSC:
| 62G07 | Density estimation |
Keywords:
density estimation; minimax theory; discrete probability distribution; Vapnik-Chervonenkis dimension; monotone density; convex density; histogramReferences:
| [1] | Anevski, D. (2003). Estimating the derivative of a convex density., Statist. Neerlandica 57 245-257. · Zbl 1090.62524 · doi:10.1111/1467-9574.00229 |
| [2] | Assouad, P. (1983). Deux remarques sur l’estimation., C. R. Acad. Sci. Paris Sér. I Math. 296 1021-1024. · Zbl 0568.62003 |
| [3] | Balabdaoui, F. and Wellner, J. A. (2007). Estimation of a \(k\)-monotone density: limit distribution theory and the spline connection., Ann. Statist. 35 2536-2564. · Zbl 1129.62019 · doi:10.1214/009053607000000262 |
| [4] | Balabdaoui, F. and Wellner, J. A. (2010). Estimation of a \(k\)-monotone density: characterizations, consistency and minimax lower bounds., Stat. Neerl. 64 45-70. · Zbl 07881732 |
| [5] | Bellec, P. C. (2018). Sharp oracle inequalities for least squares estimators in shape restricted regression., Ann. Statist. 46 745-780. · Zbl 1408.62066 · doi:10.1214/17-AOS1566 |
| [6] | Biau, G. and Devroye, L. (2003). On the risk of estimates for block decreasing densities., J. Multivariate Anal. 86 143-165. · Zbl 1025.62015 · doi:10.1016/S0047-259X(02)00028-3 |
| [7] | Birgé, L. (1987). Estimating a density under order restrictions: nonasymptotic minimax risk., Ann. Statist. 15 995-1012. · Zbl 0631.62037 · doi:10.1214/aos/1176350488 |
| [8] | Birgé, L. (1987). On the risk of histograms for estimating decreasing densities., Ann. Statist. 15 1013-1022. · Zbl 0646.62033 · doi:10.1214/aos/1176350489 |
| [9] | Birgé, L. (1989). The Grenander estimator: a nonasymptotic approach., Ann. Statist. 17 1532-1549. · Zbl 0703.62042 · doi:10.1214/aos/1176347380 |
| [10] | Chatterjee, S., Guntuboyina, A. and Sen, B. (2015). On risk bounds in isotonic and other shape restricted regression problems., Ann. Statist. 43 1774-1800. · Zbl 1317.62032 · doi:10.1214/15-AOS1324 |
| [11] | Chen, X. R. and Zhao, L. C. (1987). Almost sure \(L_1\)-norm convergence for data-based histogram density estimates., J. Multivariate Anal. 21 179-188. · Zbl 0614.62044 · doi:10.1016/0047-259X(87)90106-0 |
| [12] | Dagan, Y. and Kur, G. (2019). The log-concave maximum likelihood estimator is optimal in high dimensions., arXiv e-prints abs/1903.05315. |
| [13] | Devroye, L. (1987)., A Course in Density Estimation. Progress in Probability and Statistics 14. Birkhäuser Boston, Inc., Boston, MA. · Zbl 0617.62043 |
| [14] | Devroye, L. and Györfi, L. (1985)., Nonparametric Density Estimation: The \(L_1\) View. Wiley Series in Probability and Mathematical Statistics: Tracts on Probability and Statistics. John Wiley & Sons, Inc., New York. · Zbl 0546.62015 |
| [15] | Devroye, L., Györfi, L. and Lugosi, G. (1996)., A Probabilistic Theory of Pattern Recognition. Applications of Mathematics (New York) 31. Springer-Verlag, New York. · Zbl 0853.68150 |
| [16] | Devroye, L. and Lugosi, G. (2001)., Combinatorial Methods in Density Estimation. Springer Series in Statistics. Springer-Verlag, New York. · Zbl 0964.62025 |
| [17] | Diakonikolas, I., Kane, D. M. and Stewart, A. (2017). Learning multivariate log-concave distributions. In, Proceedings of Machine Learning Research. COLT ’17 65 1-17. |
| [18] | Gao, C., Han, F. and Zhang, C.-H. (2017). Minimax risk bounds for piecewise constant models., Ann. Statist. |
| [19] | Gessaman, M. P. (1970). A consistent nonparametric multivariate density estimator based on statistically equivalent blocks., Ann. Math. Statist. 41 1344-1346. · Zbl 0203.51502 · doi:10.1214/aoms/1177696909 |
| [20] | Grenander, U. (1956). On the theory of mortality measurement. I, II., Skand. Aktuarietidskr. 39 70-96, 125-153. · Zbl 0073.15404 |
| [21] | Groeneboom, P. (1985). Estimating a monotone density. In, Proceedings of the Berkeley conference in honor of Jerzy Neyman and Jack Kiefer, Vol. II (Berkeley, Calif., 1983). Wadsworth Statist./Probab. Ser. 539-555. Wadsworth, Belmont, CA. · Zbl 1373.62144 |
| [22] | Groeneboom, P. and Jongbloed, G. (2014)., Nonparametric Estimation Under Shape Constraints: Estimators, Algorithms, and Asymptotics. Cambridge Series in Statistical and Probabilistic Mathematics 38. Cambridge University Press, New York. · Zbl 1338.62008 |
| [23] | Groeneboom, P., Jongbloed, G. and Wellner, J. A. (2001). Estimation of a convex function: characterizations and asymptotic theory., Ann. Statist. 29 1653-1698. · Zbl 1043.62027 · doi:10.1214/aos/1015345958 |
| [24] | Guntuboyina, A. and Sen, B. (2015). Global risk bounds and adaptation in univariate convex regression., Probab. Theory Related Fields 163 379-411. · Zbl 1327.62255 · doi:10.1007/s00440-014-0595-3 |
| [25] | Jankowski, H. K. and Wellner, J. A. (2009). Estimation of a discrete monotone distribution., Electron. J. Stat. 3 1567-1605. · Zbl 1326.62038 · doi:10.1214/09-EJS526 |
| [26] | Jongbloed, G. (1995). Three Statistical Inverse Problems, PhD thesis, Delft University of, Technology. |
| [27] | Kim, A. K. H. and Samworth, R. J. (2016). Global rates of convergence in log-concave density estimation., Ann. Statist. 44 2756-2779. · Zbl 1360.62157 · doi:10.1214/16-AOS1480 |
| [28] | Lugosi, G. and Nobel, A. (1996). Consistency of data-driven histogram methods for density estimation and classification., Ann. Statist. 24 687-706. · Zbl 0859.62040 · doi:10.1214/aos/1032894460 |
| [29] | Prakasa Rao, B. L. S. (1969). Estimation of a unimodal density., Sankhyā Ser. A 31 23-36. · Zbl 0181.45901 |
| [30] | Samworth, R. J. (2017). Recent progress in log-concave density estimation., arXiv e-prints abs/1709.03154. · Zbl 1407.62126 |
| [31] | Sason, I. and Verdú, S. (2016). \(f\)-divergence inequalities., IEEE Trans. Inform. Theory 62 5973-6006. · Zbl 1359.94363 · doi:10.1109/TIT.2016.2603151 |
| [32] | Scott, D. W. (2015)., Multivariate Density Estimation: Theory, Practice, and Visualization, second ed. Wiley Series in Probability and Statistics. John Wiley & Sons, Inc., Hoboken, NJ. · Zbl 1311.62004 |
| [33] | Silverman, B. W. (1986)., Density Estimation for Statistics and Data Analysis. Monographs on Statistics and Applied Probability. Chapman & Hall, London. · Zbl 0617.62042 |
| [34] | Vapnik, V. N. and Červonenkis, A. J. (1971). The uniform convergence of frequencies of the appearance of events to their probabilities., Teor. Verojatnost. i Primenen. 16 264-279. · Zbl 0247.60005 |
| [35] | Yu, B. (1997). Assouad, Fano, and Le Cam. In, Festschrift for Lucien Le Cam 423-435. Springer, New York. · Zbl 0896.62032 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
