Abstract
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 R" and an accuracy parametere>O,runs in time poly(n,d,1/e), 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 e 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 prohlem 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) gradicnts of thc objcctive function of this optimization problem is quite delicate,and is the main technical challenge in this work.