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 $\epsilon>0$, it runs in time $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.
Description
[1812.05524] A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities
%0 Journal Article
%1 diakonikolas2018polynomial
%A Diakonikolas, Ilias
%A Sidiropoulos, Anastasios
%A Stewart, Alistair
%D 2018
%K bayesian stats
%T A Polynomial Time Algorithm for Maximum Likelihood Estimation of
Multivariate Log-concave Densities
%U http://arxiv.org/abs/1812.05524
%X 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 $\epsilon>0$, it runs in time $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.
@article{diakonikolas2018polynomial,
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.},
added-at = {2020-02-26T13:38:16.000+0100},
author = {Diakonikolas, Ilias and Sidiropoulos, Anastasios and Stewart, Alistair},
biburl = {https://www.bibsonomy.org/bibtex/2072c54b90d2757ad0cdb3ac58cccf38e/kirk86},
description = {[1812.05524] A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities},
interhash = {1e69c37844611337def7fb803a7ecf99},
intrahash = {072c54b90d2757ad0cdb3ac58cccf38e},
keywords = {bayesian stats},
note = {cite arxiv:1812.05524},
timestamp = {2020-02-26T13:38:16.000+0100},
title = {A Polynomial Time Algorithm for Maximum Likelihood Estimation of
Multivariate Log-concave Densities},
url = {http://arxiv.org/abs/1812.05524},
year = 2018
}