Repelling Random Walks

• URL: http://arxiv.org/abs/2310.04854v2
• Date: Fri, 24 May 2024 11:05:47 GMT
• Title: Repelling Random Walks
• Authors: Isaac Reid, Eli Berger, Krzysztof Choromanski, Adrian Weller,
• Abstract summary: We present a novel quasi-Monte Carlo mechanism to improve graph-based sampling, coined repelling random walks. We showcase the effectiveness of repelling random walks in a range of settings including estimation of graph kernels, the PageRank vector and graphlet concentrations. To our knowledge, repelling random walks constitute the first rigorously studied quasi-Monte Carlo scheme correlating the directions of walkers on a graph, inviting new research in this exciting nascent domain.
• Score: 42.75616308187867
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a novel quasi-Monte Carlo mechanism to improve graph-based sampling, coined repelling random walks. By inducing correlations between the trajectories of an interacting ensemble such that their marginal transition probabilities are unmodified, we are able to explore the graph more efficiently, improving the concentration of statistical estimators whilst leaving them unbiased. The mechanism has a trivial drop-in implementation. We showcase the effectiveness of repelling random walks in a range of settings including estimation of graph kernels, the PageRank vector and graphlet concentrations. We provide detailed experimental evaluation and robust theoretical guarantees. To our knowledge, repelling random walks constitute the first rigorously studied quasi-Monte Carlo scheme correlating the directions of walkers on a graph, inviting new research in this exciting nascent domain.

Related papers

• von Mises Quasi-Processes for Bayesian Circular Regression [57.88921637944379]
  We explore a family of expressive and interpretable distributions over circle-valued random functions. The resulting probability model has connections with continuous spin models in statistical physics. For posterior inference, we introduce a new Stratonovich-like augmentation that lends itself to fast Markov Chain Monte Carlo sampling.
  arXiv  Detail & Related papers  (2024-06-19T01:57:21Z)
• Statistical inverse learning problems with random observations [0.0]
  We provide an overview of recent progress in statistical inverse problems with random experimental design, covering both linear and nonlinear inverse problems. We discuss recent results in spectral regularization methods and regularization by projection, exploring both approaches within the context of Hilbert scales. We demonstrate the application of these concepts to nonlinear inverse problems in pharmacokinetic/pharmacodynamic (PK/PD) models, where the task is to predict changes in drug concentrations in patients.
  arXiv  Detail & Related papers  (2023-12-23T20:34:49Z)
• Learning in Deep Factor Graphs with Gaussian Belief Propagation [25.46318505434071]
  We treat all relevant quantities as random variables in a graphical model, and view both training and prediction as inference problems with different observed nodes. Our experiments show that these problems can be efficiently solved with belief propagation (BP), whose updates are inherently local. Our approach can be scaled to deep networks and provides a natural means to do continual learning.
  arXiv  Detail & Related papers  (2023-11-24T18:31:11Z)
• Quasi-Monte Carlo Graph Random Features [38.762964164013226]
  We present a novel mechanism to improve the accuracy of graph random features (GRFs) Our method induces negative correlations between the lengths of the algorithm's random walks by imposing antithetic termination. We derive strong theoretical guarantees on the properties of these quasi-Monte Carlo GRFs.
  arXiv  Detail & Related papers  (2023-05-21T14:12:02Z)
• Monte Carlo generation of localised particle trajectories [0.0]
  We introduce modifications to Monte Carlo simulations of the Feynman path integral that improve sampling of localised interactions. The new algorithms generate trajectories in simple background potentials designed to concentrate them about the interaction region. This improves statistical sampling of the system and overcomes a long-time "undersampling problem" caused by the spatial diffusion inherent in Brownian motion.
  arXiv  Detail & Related papers  (2023-04-20T17:50:30Z)
• From Pseudorandomness to Multi-Group Fairness and Back [17.677928204060628]
  We identify and explore connections between the recent literature on multi-group fairness for prediction algorithms and the pseudorandomness notions of leakage-resilience and graph regularity. We frame our investigation using new, statistical distance-based variants of multicalibration that are closely related to the concept of outcome indistinguishability.
  arXiv  Detail & Related papers  (2023-01-21T00:37:12Z)
• Reachability analysis in stochastic directed graphs by reinforcement learning [67.87998628083218]
  We show that the dynamics of the transition probabilities in a Markov digraph can be modeled via a difference inclusion. We offer a methodology to design reward functions to provide upper and lower bounds on the reachability probabilities of a set of nodes.
  arXiv  Detail & Related papers  (2022-02-25T08:20:43Z)
• Bayesian Graph Contrastive Learning [55.36652660268726]
  We propose a novel perspective of graph contrastive learning methods showing random augmentations leads to encoders. Our proposed method represents each node by a distribution in the latent space in contrast to existing techniques which embed each node to a deterministic vector. We show a considerable improvement in performance compared to existing state-of-the-art methods on several benchmark datasets.
  arXiv  Detail & Related papers  (2021-12-15T01:45:32Z)
• SGCN:Sparse Graph Convolution Network for Pedestrian Trajectory Prediction [64.16212996247943]
  We present a Sparse Graph Convolution Network(SGCN) for pedestrian trajectory prediction. Specifically, the SGCN explicitly models the sparse directed interaction with a sparse directed spatial graph to capture adaptive interaction pedestrians. visualizations indicate that our method can capture adaptive interactions between pedestrians and their effective motion tendencies.
  arXiv  Detail & Related papers  (2021-04-04T03:17:42Z)
• Bayesian Deep Learning and a Probabilistic Perspective of Generalization [56.69671152009899]
  We show that deep ensembles provide an effective mechanism for approximate Bayesian marginalization. We also propose a related approach that further improves the predictive distribution by marginalizing within basins of attraction.
  arXiv  Detail & Related papers  (2020-02-20T15:13:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.