Efficient computation of the the volume of a polytope in high-dimensions using Piecewise Deterministic Markov Processes

Augustin Chevallier, Frédéric Cazals, Paul Fearnhead
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:10146-10160, 2022.

Abstract

Computing the volume of a polytope in high dimensions is computationally challenging but has wide applications. Current state-of-the-art algorithms to compute such volumes rely on efficient sampling of a Gaussian distribution restricted to the polytope, using e.g. Hamiltonian Monte Carlo. We present a new sampling strategy that uses a Piecewise Deterministic Markov Process. Like Hamiltonian Monte Carlo, this new method involves simulating trajectories of a non-reversible process and inherits similar good mixing properties. However, importantly, the process can be simulated more easily due to its piecewise linear trajectories – and this leads to a reduction of the computational cost by a factor of the dimension of the space. Our experiments indicate that our method is numerically robust and is one order of magnitude faster (or better) than existing methods using Hamiltonian Monte Carlo. On a single core processor, we report computational time of a few minutes up to dimension 500.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-chevallier22a, title = { Efficient computation of the the volume of a polytope in high-dimensions using Piecewise Deterministic Markov Processes }, author = {Chevallier, Augustin and Cazals, Fr\'ed\'eric and Fearnhead, Paul}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {10146--10160}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/chevallier22a/chevallier22a.pdf}, url = {https://proceedings.mlr.press/v151/chevallier22a.html}, abstract = { Computing the volume of a polytope in high dimensions is computationally challenging but has wide applications. Current state-of-the-art algorithms to compute such volumes rely on efficient sampling of a Gaussian distribution restricted to the polytope, using e.g. Hamiltonian Monte Carlo. We present a new sampling strategy that uses a Piecewise Deterministic Markov Process. Like Hamiltonian Monte Carlo, this new method involves simulating trajectories of a non-reversible process and inherits similar good mixing properties. However, importantly, the process can be simulated more easily due to its piecewise linear trajectories – and this leads to a reduction of the computational cost by a factor of the dimension of the space. Our experiments indicate that our method is numerically robust and is one order of magnitude faster (or better) than existing methods using Hamiltonian Monte Carlo. On a single core processor, we report computational time of a few minutes up to dimension 500. } }
Endnote
%0 Conference Paper %T Efficient computation of the the volume of a polytope in high-dimensions using Piecewise Deterministic Markov Processes %A Augustin Chevallier %A Frédéric Cazals %A Paul Fearnhead %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-chevallier22a %I PMLR %P 10146--10160 %U https://proceedings.mlr.press/v151/chevallier22a.html %V 151 %X Computing the volume of a polytope in high dimensions is computationally challenging but has wide applications. Current state-of-the-art algorithms to compute such volumes rely on efficient sampling of a Gaussian distribution restricted to the polytope, using e.g. Hamiltonian Monte Carlo. We present a new sampling strategy that uses a Piecewise Deterministic Markov Process. Like Hamiltonian Monte Carlo, this new method involves simulating trajectories of a non-reversible process and inherits similar good mixing properties. However, importantly, the process can be simulated more easily due to its piecewise linear trajectories – and this leads to a reduction of the computational cost by a factor of the dimension of the space. Our experiments indicate that our method is numerically robust and is one order of magnitude faster (or better) than existing methods using Hamiltonian Monte Carlo. On a single core processor, we report computational time of a few minutes up to dimension 500.
APA
Chevallier, A., Cazals, F. & Fearnhead, P.. (2022). Efficient computation of the the volume of a polytope in high-dimensions using Piecewise Deterministic Markov Processes . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:10146-10160 Available from https://proceedings.mlr.press/v151/chevallier22a.html.

Related Material