Demystifying Orthogonal Monte Carlo and Beyond
By Han Lin, Haoxian Chen, Tianyi Zhang, Clément Laroche, Krzysztof Marcin Choromanski. 2020
11 citations recorded by the source corpus.
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.
Subfields: Numerical Analysis, Statistics and Probability, Probabilistic & Bayesian Methods, Numerical Methods & Scientific Computing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Numerical Analysis
In Statistics and Probability
In Probabilistic & Bayesian Methods
In Numerical Methods & Scientific Computing
Citations in the corpus
- Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers (2020, methodology): “2.4, we know that if instead we use G-ORFs, then space complexity is reduced to O ( M log( d ) + Ld + ML ) and if the H-ORFs mechanism is used, then space is further reduced to O ( M + Ld + ML ) = O ( Ld + ML ) .”