Name
Title | ||
|---|---|---|
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 $epsilonu003e0$, 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. |
Year | Venue | DocType |
|---|---|---|
2018 | arXiv: Data Structures and Algorithms | Journal |
Volume | Citations | PageRank |
abs/1812.05524 | 1 | 0.37 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ilias Diakonikolas | 1 | 776 | 64.21 |
| Anastasios Sidiropoulos | 2 | 330 | 31.78 |
| Alistair Stewart | 3 | 175 | 17.04 |