# A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families

arXiv: https://arxiv.org/abs/1907.08306 · HTML: https://mlsanity.com/paper/1907.08306/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jul 2019.

## Built on by (most cited first, 2 of 2)

- [Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more](https://mlsanity.com/paper/2606.11469/) (2026)
- [Nonparametric Hypothesis Testing of High-dimensional Clustering With Application to Single-cell RNA Data](https://mlsanity.com/paper/2609.05683/) (2026)

## Abstract (arXiv)

We consider the problem of computing the maximum likelihood multivariate log-concave distribution for a set of points. Specifically, we present an algorithm which, given n points in ℝd and an accuracy parameter ε>0, runs in time poly(n,d,1/ε), and returns a log-concave distribution which, with high probability, has the property that the likelihood of the n points under the returned distribution is at most an additive ε less than the maximum likelihood that could be achieved via any log-concave distribution. This is the first computationally efficient (polynomial time) algorithm for this fundamental and practically important task. Our algorithm rests on a novel connection with exponential families: the maximum likelihood log-concave distribution belongs to a class of structured distributions which, while not an exponential family, "locally" possesses key properties of exponential families. This connection then allows the problem of computing the log-concave maximum likelihood distribution to be formulated as a convex optimization problem, and solved via an approximate first-order method. Efficiently approximating the (sub) gradients of the objective function of this optimization problem is quite delicate, and is the main technical challenge in this work.