Timezone: »

 
Poster
A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families
Brian Axelrod · Ilias Diakonikolas · Alistair Stewart · Anastasios Sidiropoulos · Gregory Valiant

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #217
in Theory -- Learning Theory »
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 $\eps>0$, runs in time $\poly(n,d,1/\eps),$ 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 $\eps$ 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.
Keywords: Learning Theory · Theory
[ Paper]  [ Poster] 

Author Information

Brian Axelrod (Stanford)
Ilias Diakonikolas (UW Madison)
Alistair Stewart (University of Southern California)
Anastasios Sidiropoulos (University of Illinois at Chicago)
Gregory Valiant (Stanford University)

More from the Same Authors