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

12/13/2018
by   Ilias Diakonikolas, et al.
0

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 R^d and an accuracy parameter ϵ>0, it runs in time poly(n, d, 1/ϵ), and outputs a log-concave density that with high probability maximizes the log-likelihood up to an additive ϵ. 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset