Stein’s method

A famous generic method for approximating distributions is Stein’s method of exchangeable pairs (Stein 1986, 1972). Wikipedia is good on this.

Meckes (2009) summarises.

Heuristically, the univariate method of exchangeable pairs goes as follows. Let \(W\) be a random variable conjectured to be approximately Gaussian; assume that \(\mathbb{E} W=0\) and \(\mathbb{E} W^{2}=1 .\) From \(W,\) construct a new random variable \(W^{\prime}\) such that the pair \(\left(W, W^{\prime}\right)\) has the same distribution as \(\left(W^{\prime}, W\right) .\) This is usually done by making a "small random change" in \(W\), so that \(W\) and \(W^{\prime}\) are close. Let \(\Delta=W^{\prime}-W\). If it can be verified that there is a \(\lambda>0\) such that \[ \begin{aligned} \mathbb{E}[\Delta \mid W]=-\lambda W+E_{1} \\ \mathbb{E}\left[\Delta^{2} \mid W\right]=2 \lambda+E_{2} \\ \mathbb{E}|\Delta|^{3}=E_{3} \end{aligned} \] with the random quantities \(E_{1}, E_{2}\) and the deterministic quantity \(E_{3}\) being small compared to \(\lambda,\) then \(W\) is indeed approximately Gaussian, and its distance to Gaussian (in some metric) can be bounded in terms of the \(E_{i}\) and \(\lambda\).

This comes out very nicely where there are natural symmetries to exploit, e.g. in low-d projections.

Non-Gaussian Stein

Multivariate Stein

The work of Elizabeth Meckes 1980—2020 whose papers serve as the canonical textbook in the area for now. Two foundational ones are (ChatterjeeMultivariate2008?) and Meckes (2009) and there is a kind of user guide in (MeckesApproximation2012?); These bounds are mostly about random projections although that is not required. The exchangeable pairs are very natural in that case though, you can just switch off you brain and turn the handle to produce results, or easier yet, a computer algebra system that can handle noncommutative algebra.

Two useful presentations:


Agueh, Martial, and Guillaume Carlier. 2011. “Barycenters in the Wasserstein Space.” SIAM Journal on Mathematical Analysis 43 (2): 904–24.
Barbour, A. D., and Louis H. Y. Chen, eds. 2005. An Introduction to Stein’s Method. Vol. 4. Lecture Notes Series / Institute for Mathematical Sciences, National University of Singapore, v. 4. Singapore : Hackensack, N.J: Singapore University Press ; World Scientific.
Chatterjee, Sourav. 2014. “A Short Survey of Stein’s Method.” April 4, 2014.
Chen, Louis H. Y. 1998. “Stein’s Method: Some Perspectives with Applications.” In Probability Towards 2000, edited by L. Accardi and C. C. Heyde, 97–122. Lecture Notes in Statistics. New York, NY: Springer.
Chwialkowski, Kacper, Heiko Strathmann, and Arthur Gretton. 2016. “A Kernel Test of Goodness of Fit.” In Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48, 2606–15. ICML’16. New York, NY, USA:
Cuturi, Marco, and Arnaud Doucet. 2014. “Fast Computation of Wasserstein Barycenters.” In International Conference on Machine Learning, 685–93. PMLR.
Gorham, Jackson, Anant Raj, and Lester Mackey. 2020. “Stochastic Stein Discrepancies.” October 22, 2020.
Liu, Qiang, Jason D. Lee, and Michael I. Jordan. 2016. “A Kernelized Stein Discrepancy for Goodness-of-Fit Tests and Model Evaluation.” July 1, 2016.
Liu, Qiang, and Dilin Wang. 2019. “Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm.” In Advances In Neural Information Processing Systems.
Loh, Wei-Liem. n.d. “Stein’s Method and Multinomial Approximation.”
Meckes, Elizabeth. 2006. “An Infinitesimal Version of Stein’s Method of Exchangeable Pairs.”
———. 2009. “On Stein’s Method for Multivariate Normal Approximation.” In High Dimensional Probability V: The Luminy Volume, 153–78. Beachwood, Ohio, USA: Institute of Mathematical Statistics.
Paulin, Daniel, Lester Mackey, and Joel A. Tropp. 2016. “Efron–Stein Inequalities for Random Matrices.” The Annals of Probability 44 (5): 3431–73.
Piccoli, Benedetto, and Francesco Rossi. 2016. “On Properties of the Generalized Wasserstein Distance.” Archive for Rational Mechanics and Analysis 222 (3): 1339–65.
Reinert, Gesine. 2000. “Stein’s Method for Epidemic Processes.” In Complex Stochastic Systems, 235–75. Boca Raton: Chapman & Hall/CRC. reinert/papers/episemrevnew.pdf.
———. 2005. “Three General Approaches to Stein’s Method.” In An Introduction to Stein’s Method, Volume 4:183–221. Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, Volume 4. CO-PUBLISHED WITH SINGAPORE UNIVERSITY PRESS.
Reinert, Gesine, and Adrian Röllin. 2007. “Multivariate Normal Approximation with Stein’s Method of Exchangeable Pairs Under a General Linearity Condition,” November.
Ross, Nathan. 2011. “Fundamentals of Stein’s Method.” Probability Surveys 8 (0): 210–93.
Schoutens, Wim. 2001. “Orthogonal Polynomials in Stein’s Method.” Journal of Mathematical Analysis and Applications 253 (2): 515–31.
Stein, Charles. 1972. “A Bound for the Error in the Normal Approximation to the Distribution of a Sum of Dependent Random Variables.” Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 2: Probability Theory, January, 583–602.
———. 1986. Approximate Computation of Expectations. Vol. 7. IMS.
Tan, Yue, Yingdong Lu, and Cathy Xia. 2018. “Relative Error of Scaled Poisson Approximation via Stein’s Method.” October 9, 2018.
Upadhye, Neelesh S., and Kalyan Barman. 2020. “A Unified Approach to Stein’s Method for Stable Distributions.” July 29, 2020.
Xu, Wenkai, and Takeru Matsuda. 2021. “Interpretable Stein Goodness-of-Fit Tests on Riemannian Manifolds.” March 1, 2021.
Xu, Wenkai, and Gesine Reinert. 2021. “A Stein Goodness of Fit Test for Exponential Random Graph Models.” February 28, 2021.

Warning! Experimental comments system! If is does not work for you, let me know via the contact form.

No comments yet!

GitHub-flavored Markdown & a sane subset of HTML is supported.