Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities

Timothy Carpenter, Ilias Diakonikolas, Anastasios Sidiropoulos, Alistair Stewart
Proceedings of the 31st Conference On Learning Theory, PMLR 75:1234-1262, 2018.

Abstract

We study the problem of learning multivariate log-concave densities with respect to a global loss function. We obtain the first upper bound on the sample complexity of the maximum likelihood estimator (MLE) for a log-concave density on Rd, for all d≥4. Prior to this work, no finite sample upper bound was known for this estimator in more than 3 dimensions. In more detail, we prove that for any d≥1 and ϵ>0, given ˜Od((1/ϵ)(d+3)/2) samples drawn from an unknown log-concave density f0 on Rd, the MLE outputs a hypothesis h that with high probability is ϵ-close to f0, in squared Hellinger loss. A sample complexity lower bound of Ωd((1/ϵ)(d+1)/2) was previously known for any learning algorithm that achieves this guarantee. We thus establish that the sample complexity of the log-concave MLE is near-optimal, up to an ˜O(1/ϵ) factor.

Cite this Paper

BibTeX
@InProceedings{pmlr-v75-carpenter18a, title = {Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities}, author = {Carpenter, Timothy and Diakonikolas, Ilias and Sidiropoulos, Anastasios and Stewart, Alistair}, booktitle = {Proceedings of the 31st Conference On Learning Theory}, pages = {1234--1262}, year = {2018}, editor = {Bubeck, Sébastien and Perchet, Vianney and Rigollet, Philippe}, volume = {75}, series = {Proceedings of Machine Learning Research}, month = {06--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v75/carpenter18a/carpenter18a.pdf}, url = {https://proceedings.mlr.press/v75/carpenter18a.html}, abstract = {We study the problem of learning multivariate log-concave densities with respect to a global loss function. We obtain the first upper bound on the sample complexity of the maximum likelihood estimator (MLE) for a log-concave density on $\mathbb{R}^d$, for all $d \geq 4$. Prior to this work, no finite sample upper bound was known for this estimator in more than $3$ dimensions. In more detail, we prove that for any $d \geq 1$ and $\epsilon>0$, given $\tilde{O}_d((1/\epsilon)^{(d+3)/2})$ samples drawn from an unknown log-concave density $f_0$ on $\mathbb{R}^d$, the MLE outputs a hypothesis $h$ that with high probability is $\epsilon$-close to $f_0$, in squared Hellinger loss. A sample complexity lower bound of $\Omega_d((1/\epsilon)^{(d+1)/2})$ was previously known for any learning algorithm that achieves this guarantee. We thus establish that the sample complexity of the log-concave MLE is near-optimal, up to an $\tilde{O}(1/\epsilon)$ factor.} }
Endnote
%0 Conference Paper %T Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities %A Timothy Carpenter %A Ilias Diakonikolas %A Anastasios Sidiropoulos %A Alistair Stewart %B Proceedings of the 31st Conference On Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Sébastien Bubeck %E Vianney Perchet %E Philippe Rigollet %F pmlr-v75-carpenter18a %I PMLR %P 1234--1262 %U https://proceedings.mlr.press/v75/carpenter18a.html %V 75 %X We study the problem of learning multivariate log-concave densities with respect to a global loss function. We obtain the first upper bound on the sample complexity of the maximum likelihood estimator (MLE) for a log-concave density on $\mathbb{R}^d$, for all $d \geq 4$. Prior to this work, no finite sample upper bound was known for this estimator in more than $3$ dimensions. In more detail, we prove that for any $d \geq 1$ and $\epsilon>0$, given $\tilde{O}_d((1/\epsilon)^{(d+3)/2})$ samples drawn from an unknown log-concave density $f_0$ on $\mathbb{R}^d$, the MLE outputs a hypothesis $h$ that with high probability is $\epsilon$-close to $f_0$, in squared Hellinger loss. A sample complexity lower bound of $\Omega_d((1/\epsilon)^{(d+1)/2})$ was previously known for any learning algorithm that achieves this guarantee. We thus establish that the sample complexity of the log-concave MLE is near-optimal, up to an $\tilde{O}(1/\epsilon)$ factor.
APA
Carpenter, T., Diakonikolas, I., Sidiropoulos, A. & Stewart, A.. (2018). Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities. Proceedings of the 31st Conference On Learning Theory, in Proceedings of Machine Learning Research 75:1234-1262 Available from https://proceedings.mlr.press/v75/carpenter18a.html.

Related Material