A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities

Abstract

We study the problem of computing the maximum likelihood estimator (MLE) of multivariate log-concave densities. Our main result is the first computationally efficient algorithm for this problem. In more detail, we give an algorithm that, on input a set of $n$ points in ${\mathbb{R}}^d$ and an accuracy parameter $\epsilon >0$, it runs in time $\text{poly}(n,d,1/\epsilon )$, and outputs a log-concave density that with high probability maximizes the log-likelihood up to an additive $\epsilon$. Our approach relies on a natural convex optimization formulation of the underlying problem that can be efficiently solved by a projected stochastic subgradient method. The main challenge lies in showing that a stochastic subgradient of our objective function can be efficiently approximated. To achieve this, we rely on structural results on approximation of log-concave densities and leverage classical algorithmic tools on volume approximation of convex bodies and uniform sampling from convex sets.

References in corpus (7)

• Maximum likelihood estimation of a log-concave density and its distribution function: Basic properties and uniform consistency
• 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
• Monotone probability distributions over the Boolean cube can be learned with sublinear samples
• Geometry of Log-Concave Density Estimation
• An Efficient Algorithm for High-Dimensional Log-Concave Maximum Likelihood

Cited by in corpus (3)

• Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression
• Global Convergence of Least Squares EM for Demixing Two Log-Concave Densities
• A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families