  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 $\mathbb{R}^d$ and an accuracy parameter
$\epsilon>0$, runs in time $poly(n,d,1/\epsilon),$ 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
$\epsilon$ 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.
