Learning Multivariate Log-concave Distributions

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\ge 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.

To appear in COLT 2017

References in corpus (5)

• Optimal Testing for Properties of Distributions
• Learning mixtures of structured distributions over discrete domains
• A Size-Free CLT for Poisson Multinomials and its Applications
• Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
• Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms

Cited by in corpus (7)

• Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression
• Monotone probability distributions over the Boolean cube can be learned with sublinear samples
• Near-Optimal Closeness Testing of Discrete Histogram Distributions
• A Concentration Inequality for Random Polytopes, Dirichlet-Voronoi Tiling Numbers and the Geometric Balls and Bins Problem
• Near-optimal Sample Complexity Bounds for Robust Learning of Gaussians Mixtures via Compression Schemes
• An Efficient Algorithm for High-Dimensional Log-Concave Maximum Likelihood
• Some techniques in density estimation