A new class of Markov random fields enabling lightweight sampling

• URL: http://arxiv.org/abs/2511.02373v1
• Date: Tue, 04 Nov 2025 08:53:17 GMT
• Title: A new class of Markov random fields enabling lightweight sampling
• Authors: Jean-Baptiste Courbot, Hugo Gangloff, Bruno Colicchio,
• Abstract summary: This work addresses the problem of efficient sampling of Markov random fields (MRF)<n>The sampling of Potts or Ising MRF is most often based on Gibbs sampling, and is thus computationally expensive.<n>We consider in this work how to circumvent this bottleneck through a link with Gaussian Markov Random fields.
• Score: 3.5748387724309745
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: This work addresses the problem of efficient sampling of Markov random fields (MRF). The sampling of Potts or Ising MRF is most often based on Gibbs sampling, and is thus computationally expensive. We consider in this work how to circumvent this bottleneck through a link with Gaussian Markov Random fields. The latter can be sampled in several cost-effective ways, and we introduce a mapping from real-valued GMRF to discrete-valued MRF. The resulting new class of MRF benefits from a few theoretical properties that validate the new model. Numerical results show the drastic performance gain in terms of computational efficiency, as we sample at least 35x faster than Gibbs sampling using at least 37x less energy, all the while exhibiting empirical properties close to classical MRFs.

Related papers

• Lookahead Sample Reward Guidance for Test-Time Scaling of Diffusion Models [28.29554194279748]
  Diffusion models have demonstrated strong generative performance; however, generated samples often fail to fully align with human intent.<n>This paper studies a test-time scaling method that enables sampling from regions with higher human-aligned reward values.
  arXiv  Detail & Related papers  (2026-02-03T07:27:27Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  The MIDX-Sampler is a novel adaptive sampling strategy based on an inverted multi-index approach.<n>Our method is backed by rigorous theoretical analysis, addressing key concerns such as sampling bias, gradient bias, convergence rates, and generalization error bounds.
  arXiv  Detail & Related papers  (2025-01-15T04:09:21Z)
• Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics [21.976109703401114]
  We consider the problem of learning graphical models, also known as Markov random fields (MRFs) from temporally correlated samples. In particular, we show that given a trajectory with $widetildeO_k(n)$ site updates of an order $k$ MRF from the Glauber dynamics, there is an algorithm that recovers the graph and the parameters in $widetildeO_k(n2)$ time. Our results thus surprisingly show that this more realistic, but intuitively less tractable, model for MRFs actually leads to efficiency far beyond what
  arXiv  Detail & Related papers  (2024-09-09T02:32:45Z)
• On Optimal Sampling for Learning SDF Using MLPs Equipped with Positional Encoding [76.78321723602636]
  We devise a tool to determine the appropriate sampling rate for learning an accurate neural implicit field without undesirable side effects.<n>It is observed that a PE-equipped has an intrinsic frequency much higher than the highest frequency component in the PE layer.<n>We empirically show in the setting of SDF fitting, this recommended sampling rate is sufficient to secure accurate fitting results.
  arXiv  Detail & Related papers  (2024-01-02T10:51:52Z)
• Entropy-based Training Methods for Scalable Neural Implicit Sampler [20.35664492719671]
  In this paper, we introduce an efficient and scalable implicit neural sampler that overcomes limitations.<n>The implicit sampler can generate large batches of samples with low computational costs.<n>By employing the two training methods, we effectively optimize the neural implicit samplers to learn and generate from the desired target distribution.
  arXiv  Detail & Related papers  (2023-06-08T05:56:05Z)
• Arbitrary Point Cloud Upsampling with Spherical Mixture of Gaussians [1.2375561840897737]
  APU-SMOG is a Transformer-based model for Arbitrary Point cloud Upsampling (APU) APU-SMOG outperforms state-of-the-art fixed-ratio methods.
  arXiv  Detail & Related papers  (2022-08-10T11:10:16Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) is proposed to directly sample from the posterior distribution in contextual bandits. We prove that the proposed algorithm achieves the same sublinear regret bound as the best Thompson sampling algorithms for a special case of contextual bandits.
  arXiv  Detail & Related papers  (2022-06-22T17:58:23Z)
• NeuSample: Neural Sample Field for Efficient View Synthesis [129.10351459066501]
  We propose a lightweight module which names a neural sample field. The proposed sample field maps rays into sample distributions, which can be transformed into point coordinates and fed into radiance fields for volume rendering. We show that NeuSample achieves better rendering quality than NeRF while enjoying a faster inference speed.
  arXiv  Detail & Related papers  (2021-11-30T16:43:49Z)
• Reparameterized Sampling for Generative Adversarial Networks [71.30132908130581]
  We propose REP-GAN, a novel sampling method that allows general dependent proposals by REizing the Markov chains into the latent space of the generator. Empirically, extensive experiments on synthetic and real datasets demonstrate that our REP-GAN largely improves the sample efficiency and obtains better sample quality simultaneously.
  arXiv  Detail & Related papers  (2021-07-01T10:34:55Z)
• An MRF-UNet Product of Experts for Image Segmentation [1.7897459398362972]
  Markov random fields (MRFs) encode simpler over labels that are less prone to over-fitting. We propose to fuse both strategies by computing the product of distributions of a UNet and an MRF. The resulting MRF-UNet is trained jointly by back-propagation.
  arXiv  Detail & Related papers  (2021-04-12T14:25:32Z)
• Scalable Inference of Sparsely-changing Markov Random Fields with Strong Statistical Guarantees [10.127456032874978]
  We introduce a new class of constrained optimization problems for the inference of sparsely-changing MRFs. Our method is extremely efficient in practice: it can accurately estimate sparsely-changing graphical models with more than 500 million variables in less than one hour.
  arXiv  Detail & Related papers  (2021-02-06T13:53:00Z)
• Bandit Samplers for Training Graph Neural Networks [63.17765191700203]
  Several sampling algorithms with variance reduction have been proposed for accelerating the training of Graph Convolution Networks (GCNs) These sampling algorithms are not applicable to more general graph neural networks (GNNs) where the message aggregator contains learned weights rather than fixed weights, such as Graph Attention Networks (GAT)
  arXiv  Detail & Related papers  (2020-06-10T12:48:37Z)

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.