# Demystifying Orthogonal Monte Carlo and Beyond

arXiv: https://arxiv.org/abs/2005.13590 · HTML: https://mlsanity.com/paper/2005.13590/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2020.

## Built on by (most cited first, 8 of 8)

- [On the Expressive Power of Self-Attention Matrices](https://mlsanity.com/paper/2106.03764/) (2021)
- [Quasi-Monte Carlo for 3D Sliced Wasserstein](https://mlsanity.com/paper/2309.11713/) (2023)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Collaborative Bayesian Optimization via Wasserstein Barycenters](https://mlsanity.com/paper/2504.10770/) (2025)
- [Unlocking Pixels for Reinforcement Learning via Implicit Attention](https://mlsanity.com/paper/2102.04353/) (2021)
- [Prediction-Enhanced Monte Carlo: A Machine Learning View on Control Variate](https://mlsanity.com/paper/2412.11257/) (2024)
- [Repulsive Monte Carlo on the sphere for the sliced Wasserstein distance](https://mlsanity.com/paper/2509.10166/) (2025)

## Abstract (arXiv)

Orthogonal Monte Carlo (OMC) is a very effective sampling algorithm imposing structural geometric conditions (orthogonality) on samples for variance reduction. Due to its simplicity and superior performance as compared to its Quasi Monte Carlo counterparts, OMC is used in a wide spectrum of challenging machine learning applications ranging from scalable kernel methods to predictive recurrent neural networks, generative models and reinforcement learning. However theoretical understanding of the method remains very limited. In this paper we shed new light on the theoretical principles behind OMC, applying theory of negatively dependent random variables to obtain several new concentration results. We also propose a novel extensions of the method leveraging number theory techniques and particle algorithms, called Near-Orthogonal Monte Carlo (NOMC). We show that NOMC is the first algorithm consistently outperforming OMC in applications ranging from kernel methods to approximating distances in probabilistic metric spaces.