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

2018/12/13 by Diakonikolas, Ilias, Sidiropoulos, Anastasios, Stewart, Alistair
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1812.05524

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 ℝ^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.

Related

• An Efficient Algorithm for High-Dimensional Log-Concave Maximum Likelihood
• A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families
• Fast Multivariate Log-Concave Density Estimation
• Maximum likelihood estimation of a multidimensional log-concave density
• A new computational framework for log-concave density estimation