A comparative study of uniform high dimensional samplers

Overview

Sampling from the uniform distribution of a convex region is a well studied problem useful in many applications and lies in the core of GeomScale activities. This project aims (a) to implement the random walks for uniform sampling that are not implemented in volesti, (b) to implement the most important statistical tests for checking convergence to the target distribution, (c) to compare the mixing times in practice through extensive experiments.

Related work

Details of your coding project

• New algorithms for uniform sampling
• Comparison with existing ones / Implement statistical tests for convergence
• Polytope database for evaluation of the methods
• Documentation / R vignette

Expected impact

The projects aims in creating a reference point in practical sampling from convex regions in high-dimensions (up-to order of thousands).

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 is one of the authors of volesti.

• Vissarion Fisikopoulos <vissarion.fisikopoulos at gmail.com> is an international expert in mathematical software, computational geometry and optimization, and has previous GSOC mentoring experience with Boost C++ libraries (2016-2017) and the R-project (2017).

• Elias Tsigaridas <elias.tsigaridas at inria.fr> is an expert in computational nonlinear algebra and geometry with experience in mathematical software. He has contributed to the implementation, in C and C++, of several solving algorithms for various open source computer algebra libraries and has previous GSOC mentoring experience with the R-project (2019).

Students, please contact both mentors below after completing at least one of the tests below.

Tests

Students, please do one or more of the following tests before contacting the mentors above.

• Easy: compile and run VolEsti. Use the R extension to visualize sampling in a polytope.
• Medium: Sample approximate uniformly points from a 100-dimensional hypercube using the implmented in volesti random walks, for various walk lengths. For each sample project the points to the plane and comment on the mixing of the random walks.
• Hard: Implement a simple statistical test for convergence of a random walk sampler. Check the convergence of the implemented in volesti random walks for a 100-dimensional hypercube.

Solutions of tests

Students, please post a link to your test results here.

• EXAMPLE STUDENT 1 NAME, LINK TO GITHUB PROFILE, LINK TO TEST RESULTS.