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

1. to implement the random walks for uniform sampling that are not implemented in volesti,
2. to implement the most important statistical tests for checking convergence to the target distribution,
3. to compare the mixing times in practice through extensive experiments.

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

Difficulty: Easy

Skills

• Required: C++, R, Probability theory
• Preferred: Experience with statistical or other mathematical software is a plus

Expected impact

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

Mentors

• Apostolos Chalkis <tolis.chal at gmail.com> is an expert in statistical software, computational geometry, and optimization, and has previous GSoC student experience (2018 & 2019) and mentoring experience with GeomScale (2020 & 2021).

• 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).

• Marios Papachristou < papachristoumarios at gmail.com > is a PhD student in the Computer Science Department at Cornell University. His primary research interests lie within the field of Data Science. He has previous experience in GSoC 2018 and 2020 as a student under Org. FOSS and GeomScale. He was GSoC mentor in GSoC 2019.

Students, please contact all mentors 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 distributed points from a 100-dimensional hypercube using the implemented 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: Use 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.