%0 Journal Article %1 diakonikolas2016learning %A Diakonikolas, Ilias %A Kane, Daniel M. %A Stewart, Alistair %D 2016 %K learning probability stats %T Learning Multivariate Log-concave Distributions %U http://arxiv.org/abs/1605.08188 %X We study the problem of estimating multivariate log-concave probability density functions. We prove the first sample complexity upper bound for learning log-concave densities on $R^d$, for all $d 1$. Prior to our work, no upper bound on the sample complexity of this learning problem was known for the case of $d>3$. In more detail, we give an estimator that, for any $d 1$ and $\epsilon>0$, draws $O_d łeft( (1/\epsilon)^(d+5)/2 \right)$ samples from an unknown target log-concave density on $R^d$, and outputs a hypothesis that (with high probability) is $\epsilon$-close to the target, in total variation distance. Our upper bound on the sample complexity comes close to the known lower bound of $Ømega_d łeft( (1/\epsilon)^(d+1)/2 \right)$ for this problem.

@article{diakonikolas2016learning, abstract = {We study the problem of estimating multivariate log-concave probability density functions. We prove the first sample complexity upper bound for learning log-concave densities on $\mathbb{R}^d$, for all $d \geq 1$. Prior to our work, no upper bound on the sample complexity of this learning problem was known for the case of $d>3$. In more detail, we give an estimator that, for any $d \ge 1$ and $\epsilon>0$, draws $\tilde{O}_d \left( (1/\epsilon)^{(d+5)/2} \right)$ samples from an unknown target log-concave density on $\mathbb{R}^d$, and outputs a hypothesis that (with high probability) is $\epsilon$-close to the target, in total variation distance. Our upper bound on the sample complexity comes close to the known lower bound of $\Omega_d \left( (1/\epsilon)^{(d+1)/2} \right)$ for this problem.}, added-at = {2020-02-26T13:46:03.000+0100}, author = {Diakonikolas, Ilias and Kane, Daniel M. and Stewart, Alistair}, biburl = {https://www.bibsonomy.org/bibtex/2583e107987773f761bc2ffb29b141eee/kirk86}, description = {[1605.08188] Learning Multivariate Log-concave Distributions}, interhash = {c60eae9ba4905733eccbce5aef8f4958}, intrahash = {583e107987773f761bc2ffb29b141eee}, keywords = {learning probability stats}, note = {cite arxiv:1605.08188Comment: To appear in COLT 2017}, timestamp = {2020-02-26T13:46:03.000+0100}, title = {Learning Multivariate Log-concave Distributions}, url = {http://arxiv.org/abs/1605.08188}, year = 2016 }