Maximum likelihood estimation of a multidimensional log concave density

Background

Modern non-parametric density estimation is a crucial problem that appears in many applications in computational statistics, machine learning and Bayesian inference. In [1] they provide a Maximum likelihood estimation of a multidimensional log-concave density given a set of n i.i.d. observations. They combine techniques from computational geometry and from non-differentiable convex optimisation. The algorithm is implemented in CRAN package LogConcDEAD. However, the algorithm requires the computation of a triangulation of the point-set. Thus, the run-time grows exponetially to the dimension and the efficiency of the algorithm is limited for dimensions larger than say ~20. The student will implement an approximation algorithm based in [1] using Markov Chain Monte Carlo integration to solve the optimization problem that appears in [1].

Details of your coding project

The student will implement (a) the MCMC integration algorithm in [2] (b) approximate Shor’s r-algorithm based on (a) and (c) an approximation algorithm Maximum likelihood estimation of a multidimensional log-concave density given a set of n i.i.d. observations.

Expected impact

The aim is the new implementation to be the most efficient among existing open source software packages for non-parametric density estimation.

Mentors

• Apostolos Chalkis <tolis.chal at gmail.com> is a PhD student in Computer Science. His research focuses on mathematical computing, optimization and computational finance. He has previous experience in GSoC 2018 and 2019 as a student under Org. R-project, implementing state-of-the-art algorithms for sampling from high dimensional multivariate distributions. He was GSOC mentor in three projects with Geomscale (2020). He is one of the authors of volesti.

• Ioannis Psarros < ipsarros at di.uoa.gr > is a postdoctoral researcher at the University of Bonn. He is an expert in geometric approximation algorithms and mathematical computing.

• Christos Konaxis < ckonaxis at gmail.com > is a postdoctoral researcher at ERGA group, University of Athens. His an expert in algebraic geometry and mathematical software.

Tests

• Easy: Download, compile and run a simple sampling example with both C++ and R interfaces of volesti. For example, you can sample uniformly distributed points from a 100-dimensional cube using all the implmented in volesti random walks and project the points onto the plane to demonstrate the mixing of the random walks.

• Medium: Given an evaluation oracle of a strongly convex function, implement ball walk to sample from the corresponding log-concave distribution truncated to a polytope. You are free to choose if the oracle is written in C++.

• Hard: Implement gradient-descent algorithm when additionally, an evaluation oracle is given for the gradient of a strongly convex function. Use the step size of Barzilai–Borwein method. Again you are free to choose if the gradient oracle is written in C++.