تقرير
Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains
| العنوان: | Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains |
|---|---|
| المؤلفون: | Doshi, Vishwaraj, Hu, Jie, Eun, Do Young |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Probability, Computer Science - Machine Learning |
| الوصف: | We consider random walks on discrete state spaces, such as general undirected graphs, where the random walkers are designed to approximate a target quantity over the network topology via sampling and neighborhood exploration in the form of Markov chain Monte Carlo (MCMC) procedures. Given any Markov chain corresponding to a target probability distribution, we design a self-repellent random walk (SRRW) which is less likely to transition to nodes that were highly visited in the past, and more likely to transition to seldom visited nodes. For a class of SRRWs parameterized by a positive real {\alpha}, we prove that the empirical distribution of the process converges almost surely to the the target (stationary) distribution of the underlying Markov chain kernel. We then provide a central limit theorem and derive the exact form of the arising asymptotic co-variance matrix, which allows us to show that the SRRW with a stronger repellence (larger {\alpha}) always achieves a smaller asymptotic covariance, in the sense of Loewner ordering of co-variance matrices. Especially for SRRW-driven MCMC algorithms, we show that the decrease in the asymptotic sampling variance is of the order O(1/{\alpha}), eventually going down to zero. Finally, we provide numerical simulations complimentary to our theoretical results, also empirically testing a version of SRRW with {\alpha} increasing in time to combine the benefits of smaller asymptotic variance due to large {\alpha}, with empirically observed faster mixing properties of SRRW with smaller {\alpha}. Comment: Selected for oral presentation at ICML 2023. Recipient of Outstanding Paper award |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2305.05097 |
| رقم الأكسشن: | edsarx.2305.05097 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |