Exact solutions in log-concave maximum likelihood estimation. (English) Zbl 07628622
Summary: We study probability density functions that are log-concave. Despite the space of all such densities being infinite-dimensional, the maximum likelihood estimate is the exponential of a piecewise linear function determined by finitely many quantities, namely the function values, or heights, at the data points. We explore in what sense exact solutions to this problem are possible. First, we show that the heights given by the maximum likelihood estimate are generically transcendental. For a cell in one dimension, the maximum likelihood estimator is expressed in closed form using the generalized \(W\)-Lambert function. Even more, we show that finding the log-concave maximum likelihood estimate is equivalent to solving a collection of polynomial-exponential systems of a special form. Even in the case of two equations, very little is known about solutions to these systems. As an alternative, we use Smale’s \(\alpha \)-theory to refine approximate numerical solutions and to certify solutions to log-concave density estimation.
MSC:
| 62G07 | Density estimation |
Keywords:
log-concavity; maximum likelihood estimation; polynomial-exponential systems; certified solutions; transcendence theory; Smale’s \(\alpha\)-theory; Lambert functions; polyhedral subdivisionsReferences:
| [1] | Améndola, C.; Drton, M.; Sturmfels, B., Maximum likelihood estimates for Gaussian mixtures are transcendental, (Int. Conf. on Math. Asp. of Comput. and Inf. Sci. (2015), Springer), 579-590 · Zbl 1460.62081 |
| [2] | Axelrod, B.; Diakonikolas, I.; Stewart, A.; Sidiropoulos, A.; Valiant, G., A polynomial time algorithm for log-concave maximum likelihood via locally exponential families, (Adv. Neural Inform. Process. Syst. 32 (2019), Curran Associates, Inc.), 7723-7735 |
| [3] | Ayer, M.; Brunk, H. D.; Ewing, G. M.; Reid, W. T.; Silverman, E., An empirical distribution function for sampling with incomplete information, Ann. Math. Stat., 26, 641-647 (1955) · Zbl 0066.38502 |
| [4] | Bagnoli, M.; Bergstrom, T., Log-concave probability and its applications, Econom. Theory, 26, 2, 445-469 (2005) · Zbl 1077.60012 |
| [5] | Baker, A., Transcendental Number Theory (1990), Cambridge Mathematical Library, Cambridge University Press: Cambridge Mathematical Library, Cambridge University Press Cambridge · Zbl 0715.11032 |
| [6] | Balabdaoui, F.; Wellner, J. A., Estimation of a k-monotone density, part 1: characterizations consistency, and minimax lower bounds (2005), arXiv preprint |
| [7] | Balabdaoui, F.; Wellner, J. A., Estimation of a k-monotone density: limit distribution theory and the spline connection, Ann. Stat., 35, 6, 2536-2564 (2007) · Zbl 1129.62019 |
| [8] | Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Numerically Solving Polynomial Systems with Bertini, Software, Environments, and Tools, vol. 25 (2013), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 1295.65057 |
| [9] | Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and Real Computation (1998), Springer-Verlag: Springer-Verlag New York, with a foreword by Richard M. Karp |
| [10] | Carpenter, T.; Diakonikolas, I.; Sidiropoulos, A.; Stewart, A., Near-optimal sample complexity bounds for maximum likelihood estimation of multivariate log-concave densities, (Bubeck, S.; Perchet, V.; Rigollet, P., Proc. 31 Conf. Learn. Theory. Proc. 31 Conf. Learn. Theory, Proceedings of Machine Learning Research, PMLR, vol. 75 (2018)), 1234-1262 |
| [11] | Chonev, V.; Ouaknine, J.; Worrell, J., On recurrent reachability for continuous linear dynamical systems, (Proc. of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science (LICS 2016) (2016), ACM: ACM New York), 10 · Zbl 1388.68044 |
| [12] | Chonev, V.; Ouaknine, J.; Worrell, J., On the Skolem problem for continuous linear dynamical systems, (43rd International Colloquium on Automata, Languages, and Programming. 43rd International Colloquium on Automata, Languages, and Programming, LIPIcs. Leibniz Int. Proc. Inform., vol. 55 (2016), Schloss Dagstuhl. Leibniz-Zent. Inform.: Schloss Dagstuhl. Leibniz-Zent. Inform. Wadern), Article 100 pp. · Zbl 1388.68043 |
| [13] | Cule, M.; Samworth, R., Theoretical properties of the log-concave maximum likelihood estimator of a multidimensional density, Electron. J. Stat., 4, 254-270 (2010) · Zbl 1329.62183 |
| [14] | Cule, M.; Gramacy, R.; Samworth, R., LogConcDEAD: an R package for maximum likelihood estimation of a multivariate log-concave density, J. Stat. Softw., 29, 2 (2009) |
| [15] | Cule, M.; Samworth, R.; Stewart, M., Maximum likelihood estimation of a multi-dimensional log-concave density, J. R. Stat. Soc., Ser. B, Stat. Methodol., 72, 5, 545-607 (2010) · Zbl 1411.62055 |
| [16] | De, A.; Long, P. M.; Servedio, R. A., Density estimation for shift-invariant multidimensional distributions, (10th Innovations in Theoretical Computer Science. 10th Innovations in Theoretical Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 124 (2019), Schloss Dagstuhl. Leibniz-Zent. Inform.: Schloss Dagstuhl. Leibniz-Zent. Inform. Wadern), Article 28 pp. · Zbl 07559071 |
| [17] | De Loera, J. A.; Rambau, J.; Santos, F., Triangulations. Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, vol. 25 (2010), Springer-Verlag: Springer-Verlag Berlin · Zbl 1207.52002 |
| [18] | Dharmadhikari, S.; Joag-Dev, K., Unimodality, Convexity, and Applications (1988), Elsevier · Zbl 0646.62008 |
| [19] | Diakonikolas, I.; Kane, D. M.; Stewart, A., Learning multivariate log-concave distributions, (Kale, S.; Shamir, O., Proc. 2017 Conf. Learn. Theory. Proc. 2017 Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 65 (2017), PMLR: PMLR Amsterdam, Netherlands), 711-727 |
| [20] | Doss, C. R.; Wellner, J. A., Global rates of convergence of the MLEs of log-concave and s-concave densities, Ann. Stat., 44, 3, 954-981 (2016) · Zbl 1338.62101 |
| [21] | Dümbgen, L.; Rufibach, K., Maximum likelihood estimation of a log-concave density and its distribution function: basic properties and uniform consistency, Bernoulli, 15, 1, 40-68 (2009) · Zbl 1200.62030 |
| [22] | Dümbgen, L.; Rufibach, K., logcondens: computations related to univariate log-concave density estimation, J. Stat. Softw., 39, 6, 1-28 (2011) |
| [23] | Dümbgen, L.; Samworth, R.; Schuhmacher, D., Approximation by log-concave distributions, with applications to regression, Ann. Stat., 39, 2, 702-730 (2011) · Zbl 1216.62023 |
| [24] | Eggermont, P. P.B.; LaRiccia, V. N., Maximum likelihood estimation of smooth monotone and unimodal densities, Ann. Stat., 28, 3, 922-947 (2000) · Zbl 1105.62332 |
| [25] | Eggermont, P. P.B.; LaRiccia, V. N., Maximum Penalized Likelihood Estimation. Vol. I: Density Estimation, Springer Series in Statistics (2001), Springer-Verlag: Springer-Verlag New York · Zbl 0984.62026 |
| [26] | Fix, E.; Hodges, J., Discriminatory Analysis: Nonparametric Discrimination, Consistency Properties (1951), USAF School of Aviation Medicine, Randolph Field: USAF School of Aviation Medicine, Randolph Field Texas · Zbl 0715.62080 |
| [27] | Grenander, U., On the theory of mortality measurement. II, Skand. Aktuarietidskr., 39, 125-153 (1956), (1957) · Zbl 0077.33715 |
| [28] | Groeneboom, P.; Jongbloed, G., Nonparametric estimation under shape constraints, (Estimators, Algorithms and Asymptotics. Estimators, Algorithms and Asymptotics, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 38 (2014), Cambridge University Press: Cambridge University Press New York) · Zbl 1338.62008 |
| [29] | Groeneboom, P.; Jongbloed, G.; Wellner, J. A., Estimation of a convex function: characterizations and asymptotic theory, Ann. Stat., 29, 6, 1653-1698 (2001) · Zbl 1043.62027 |
| [30] | Grosdos, A.; Heaton, A.; Kubjas, K.; Kuznetsova, O.; Scholten, G.; Sorea, M.-S., Github repository (2020) |
| [31] | Hauenstein, J. D.; Levandovskyy, V., Certifying solutions to square systems of polynomial-exponential equations, J. Symb. Comput., 79, part 3, 575-593 (2017) · Zbl 1357.14071 |
| [32] | Hauenstein, J. D.; Sottile, F., Algorithm 921: alphaCertified: certifying solutions to polynomial systems, ACM Trans. Math. Softw., 38, 4, Article 28 pp. (2012) · Zbl 1365.65148 |
| [33] | Kim, A. K.H.; Samworth, R. J., Global rates of convergence in log-concave density estimation, Ann. Stat., 44, 6, 2756-2779 (2016) · Zbl 1360.62157 |
| [34] | Kim, A. K.H.; Guntuboyina, A.; Samworth, R. J., Adaptation in log-concave density estimation, Ann. Stat., 46, 5, 2279-2306 (2018) · Zbl 1408.62062 |
| [35] | Kur, G.; Dagan, Y.; Rakhlin, A., Optimality of maximum likelihood for log-concave density estimation and bounded convex regression (2019), arXiv preprint |
| [36] | Leykin, A., Numerical algebraic geometry, J. Softw. Algebra Geom., 3, 5-10 (2011) · Zbl 1311.14057 |
| [37] | Liu, Y.; Wang, Y., cnmlcd: maximum likelihood estimation of a log-concave density function (2018), r package version 1.2-0 |
| [38] | Maignan, A., Solving one and two-dimensional exponential polynomial systems, (Proc. of the 1998 Int. Symp. Symb. and Algebr. Comput.. Proc. of the 1998 Int. Symp. Symb. and Algebr. Comput., ISSAC ’98 (1998), ACM: ACM New York, NY, USA), 215-221 · Zbl 0924.65044 |
| [39] | Maignan, A.; Scott, T. C., Fleshing out the generalized Lambert W function, ACM Commun. Comput. Algebra, 50, 2, 45-60 (2016) · Zbl 1367.33017 |
| [40] | McCallum, S.; Weispfenning, V., Deciding polynomial-transcendental problems, J. Symb. Comput., 47, 1, 16-31 (2012) · Zbl 1243.03015 |
| [41] | Mező, I. (2017), r-Lambert-function |
| [42] | Mező, I.; Baricz, A., On the generalization of the Lambert W function, Trans. Am. Math. Soc., 369, 11, 7917-7934 (2017) · Zbl 1375.33034 |
| [43] | Pal, J. K.; Woodroofe, M.; Meyer, M., Estimating a Polya frequency function_2, (Complex Datasets and Inverse Problems. Complex Datasets and Inverse Problems, IMS Lecture Notes Monogr. Ser., Inst. Math., vol. 54 (2007), Statist: Statist Beachwood, OH), 239-249 |
| [44] | Parzen, E., On estimation of a probability density function and mode, Ann. Math. Stat., 33, 1065-1076 (1962) · Zbl 0116.11302 |
| [45] | Rathke, F., Fast multivariate log-concave density estimation in (2018) |
| [46] | Rathke, F.; Schnörr, C., Fast multivariate log-concave density estimation, Comput. Stat. Data Anal., 140, 41-58 (2019) · Zbl 1496.62021 |
| [47] | Richardson, D., Roots of real exponential functions, J. Lond. Math. Soc. (2), 28, 1, 46-56 (1983) |
| [48] | Robeva, E.; Sturmfels, B.; Tran, N.; Uhler, C., Maximum likelihood estimation for totally positive log-concave densities, Scand. J. Stat. (2018) |
| [49] | Robeva, E.; Sturmfels, B.; Uhler, C., Geometry of log-concave density estimation, Discrete Comput. Geom., 61, 1, 136-160 (2019) · Zbl 1416.62202 |
| [50] | Rosenblatt, M., Remarks on some nonparametric estimates of a density function, Ann. Math. Stat., 27, 832-837 (1956) · Zbl 0073.14602 |
| [51] | Rufibach, K., Computing maximum likelihood estimators of a log-concave density function, J. Stat. Comput. Simul., 77, 7-8, 561-574 (2007) · Zbl 1146.62027 |
| [52] | Samworth, R. J., Recent progress in log-concave density estimation, Stat. Sci., 33, 4, 493-509 (2018) · Zbl 1407.62126 |
| [53] | Scott, D. W., Multivariate Density Estimation: Theory, Practice, and Visualization, Wiley Series in Probability and Statistics (2015), John Wiley & Sons: John Wiley & Sons Hoboken, New Jersey · Zbl 1311.62004 |
| [54] | Shub, M.; Smale, S., Complexity of Bézout’s theorem. I. Geometric aspects, J. Am. Math. Soc., 6, 2, 459-501 (1993) · Zbl 0821.65035 |
| [55] | Silverman, B. W., Density Estimation for Statistics and Data Analysis, Monographs on Statistics and Applied Probability (1986), Chapman & Hall: Chapman & Hall London · Zbl 0617.62042 |
| [56] | Smale, S., Newton’s method estimates from data at one point, (The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics (1986), Springer: Springer New York), 185-196 · Zbl 0613.65058 |
| [57] | Tsybakov, A. B., Introduction to Nonparametric Estimation, Springer Series in Statistics (2009), Springer: Springer New York, revised and extended from the 2004 French original, Translated by Vladimir Zaiats · Zbl 1176.62032 |
| [58] | Walter, G.; Blum, J., Probability density estimation using delta sequences, Ann. Stat., 7, 2, 328-340 (1979) · Zbl 0403.62025 |
| [59] | Walther, G., Detecting the presence of mixing with multiscale maximum likelihood, J. Am. Stat. Assoc., 97, 458, 508-513 (2002) · Zbl 1073.62533 |
| [60] | Xu, M.; Li, Z.-B.; Yang, L., Quantifier elimination for a class of exponential polynomial formulas, J. Symb. Comput., 68, 146-168 (2015) · Zbl 1382.03056 |
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.
