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

The submission provides a polynomial-time approximation algorithm for finding the maximum-likelihood log-concave density for a given set of data points in R d, for arbitrary d. The work is theoretical in nature, with proofs and no experiments. The problem is very interesting, since log-concave distributions include may of the commonly used parametric families (such as Gaussian), and the log-concave MLE has also other interesting properties. Previously the sample-complexity of learning a log-concave distribution has been studied, but a polynomial-time algorithm has been lacking. The present work provides such an algorithm.