-
Notifications
You must be signed in to change notification settings - Fork 3
Efficient MCMC sampling based on the underdamped Langevin diffusion
This project is about sampling from high dimensional log-concave distributions. The student will implement in C++ a Markov chain Monte Carlo (MCMC) algorithm based on the underdamped Langevin (ULD) and add the implementation to volesti
package. In particular she/he will use a framework to discretize stochastic differential equations and simulate ULD, which converges to the target distribution. This framework is the current theoretical state-of-the-art for sampling from log-concave densities and is based on the paper at https://arxiv.org/pdf/1909.05503.pdf.
There are not any open source software to sample from a probability distribution by solving stochastic differential equations. Hence this implementation would be a prototype one and would aspire to be beyond fastest implementations. Besides the log-concave sampling problem the proposed framework can be used to solve any problem that involves simulating stochastic differential equations (SDEs). There are various open source software to solve a SDE but the proposed method guarantees fast computations, within arbitrarily small error and evolves only two gradient evaluations per iteration. So an additional outcome of this project would be an efficient SDE solver.
What other software, libraries or packages with similar functionality already exist? What are their limitations that your project will overcome?
The student has a) to implement a SDE solver when evaluations oracles are given for a strongly convex function and its gradient, b) to use this solver to sample from the corresponding log-concave distribution without truncation and c) to employ boundary reflections on the computed, by the SDE, trajectory to sample from polytopes. The proposed programming language is C++ because the implemented code will have to be added to volesti
package and GeomScale
project in general. Of course, the implementation will be based on the current software of volesti
, so the basic geometrical concepts (polytopes, boundary reflections, other random walks) are ready to be used.
This project is expected to be very important to GeomScale
project as it is about efficient sampling from log-concave distributions which appear in many applications. Moreover, it will be the starting point towards to efficient SDE solvers which is a new area for GeomScale
project with numerous of applications to require such computations.
-
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, implementing state-of-the-art algorithms for sampling from high dimensional multivariate distributions. He is one of the authors of
volesti
. - Zafeirakis Zafeirakopoulos [email protected]
Students, please do one or more of the following tests before contacting the mentors above.
-
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++ or R.
-
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++ or R.
Students, please post a link to your test results here.
EXAMPLE STUDENT 1 NAME, LINK TO GITHUB PROFILE, LINK TO TEST RESULTS.
Name:Rohit Email:[email protected] GitHub:https://github.com/phoenixrao885/gsoc-monte-carlo-solutions Test done :monte carlo integration -Easy,Medium,Hard,Bonus
Name: Prajwal Bagal Email: [email protected] Github: https://github.com/Prajwalbagal/GeomScaleTest
Name:Abhishek Agrawal Email:[email protected] GitHub:Easy-task: https://github.com/abhishek8764/Monte-Carlo-Integration
Name: Divesh Kuamar Email: [email protected] Task-Link(Easy Randomized LP solver): https://github.com/diveshkr-code/Geomscale_Gsoc2020`
Name: Deifilia To Email: [email protected] Task-link: (Easy and Medium of Apothesis): https://github.com/DeifiliaTo/Apothesis_gsoc
Name: Soumyajit Chakraborty Email: [email protected] Task-Link(Easy Task of Apothesis): https://github.com/soumyajit1729/Apothesis
Name: Soumyajit Chakraborty Email: [email protected] Task-Link(Medium Task of Apothesis): https://github.com/soumyajit1729/Apothesis
Name: Soumyajit Chakraborty Email: [email protected] Task-Link(Hard Task of Apothesis): https://docs.google.com/presentation/d/1mX4UA3x8cs6--aCZ_cN2ZNB6jr3eC7P5sbiEB92YEC0/edit?usp=sharing
Name:Abhishek Agrawal Email:[email protected] GitHub:Medium-task: https://github.com/abhishek8764/Monte-Carlo-Integration
Name: Alexandros Manochis, Email: [email protected], Github: https://github.com/AlexManochis/volume_approximation/tree/gsoc20, Project: A comparative study of uniform high dimensional samplers, Tests completed: Easy, Medium, Hard
Name: Sunit Gautam Email: [email protected], [email protected] GitHub: https://github.com/gsunit/Monte-Carlo-Intergration Tasks completed: Monte Carlo integration - Easy, Medium, Hard
Name: Vaibhav Thakkar
Email: [email protected]
GitHub: https://github.com/vaithak/GeomScale_LP
Tasks completed: Randomized LP - Easy, Medium, Hard
Name: Sharat Bhat Email: [email protected] Github: https://github.com/Sharat-Bhat Tasks: https://github.com/Sharat-Bhat/GSoC_volesti
Name: Kunal Katiyar Email: [email protected] GitHub: https://github.com/KunalKatiyar/GSoC_RandLP
Name: Reyan Ahmed Email: [email protected] GitHub: https://github.com/abureyanahmed/VolEsti_test
Name:Abhishek Agrawal Email:[email protected] GitHub:Easy-task: https://github.com/abhishek8764/A-comparative-study-of-uniform-high-dimensional-samplers
Name: Sushovan Haldar Email: [email protected] Github: Easy task of using volesti : https://github.com/SushovanHaldar/geomscalecodes
Name: Anastasios Sourpis Email: [email protected] Github: Apothesis : https://github.com/pithonas/Apothesis
Name: Daniel Pozo Email: [email protected] GitHub: https://github.com/danipozo/uld-test-solutions
Name: Iasonas Nikolaou Email: [email protected] GitHub: (Easy and medium task, randomized LP) https://github.com/jasonNikolaou/GeomScale_gsoc
Name: Fernando Martin Email: fdmartin92 (at) gmail (dot) com GitHub: https://github.com/fmartin92/GeomScale_MonteCarlo (All tasks corresponding to the Monte Carlo integration proposal)
Name: Marios Papachristou Email: papachristoumarios [at) gmail (dot] com GitHub: https://github.com/papachristoumarios/geomscales-challenge (All challenges for ULD)
Name: Eugenio Borghini Email: [email protected] GitHub: https://github.com/eugenusb/GeomScale_LP (Easy and medium test projects for the randomized LP solver)
Name: Muhammad Ali Nayeem Email: [email protected] GitHub: https://github.com/ali-nayeem Test: https://github.com/ali-nayeem/gsoc2020_rand_LP_solver
Name: Bychkov Andrey Email: [email protected] GitHub: https://github.com/AndreyBychkov Test: https://github.com/AndreyBychkov/LIPA (Hard for Optimization and SOS)
Name: Yuan Yuan Email: [email protected] Github:https://github.com/yzy0014 Test:https://github.com/yzy0014/GeomScale Test demo:https://rpubs.com/yzy0014/584976, https://rpubs.com/yzy0014/585064 (High dimensional sampling with applications to structural biology)
Name: Haris Zafeiropoulos Email: [email protected] Github:https://github.com/hariszaf/ Test:https://hariszaf.github.io/gsoc2020/
Name: Mokhwa Lee
Email: [email protected] OR [email protected]
Github: https://github.com/Mokhwalee
Test: https://github.com/Mokhwalee/Exercise-Gsos
( Monte Carlo - Easy, Medium, Hard, Bonus )
Name: Antonis Skarlatos
Email: [email protected]
Github: https://github.com/Hepic/
Test: https://github.com/Hepic/Monte-Carlo-integration
(Monte-Carlo-integration: easy/medium/hard/bonus Languages used: R/C++)
Name: Konstantinos Emmanouilidis
Email: [email protected]
Github: https://github.com/emmanouilidisk
Test: https://github.com/emmanouilidisk/GeomScale_challenges
(Challenges for Randomised LP Solver)
Name: Imrane Belhadia Email: [email protected] Github:https://github.com/ImraneBELH Test: https://github.com/ImraneBELH/gsocEvaluation-MonteCarlo.git (Monte Carlo)
Name: Repouskos Panagiotis Email: [email protected] Github: https://github.com/panagiotisrep/volume_approximation/tree/Optimization , https://github.com/panagiotisrep/volume_approximation/tree/SDP-cutting-plane Test: Randomized SDP solver (medium, hard)
Name: Mohammad Taufeeque
Email: [email protected]
Github: https://github.com/taufeeque9
Test: https://github.com/taufeeque9/GSoC_Randomized_SDP_Solver_Test
(Easy and hard task for Randomized SDP Solver)
Name: Bento Natura
Email: [email protected]
Github: https://github.com/platformconclude/volume_approximation/tree/spectra_sampling
Test: Randomized SDP solver (medium)
Github: https://github.com/platformconclude/simple_LP_IPM
Test: Interior point method for linear programming (IPM)
Name: Ritwik Chakraborty
Email: [email protected]
Github: https://github.com/ritwikchakraborty123
Test: :A comparative study of uniform high-dimensional samplers (medium)