Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics

• URL: http://arxiv.org/abs/2409.05284v2
• Date: Mon, 4 Nov 2024 18:37:07 GMT
• Title: Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
• Authors: Jason Gaitonde, Ankur Moitra, Elchanan Mossel,
• Abstract summary: 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
• Score: 21.976109703401114
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of learning graphical models, also known as Markov random fields (MRFs) from temporally correlated samples. As in many traditional statistical settings, fundamental results in the area all assume independent samples from the distribution. However, these samples generally will not directly correspond to more realistic observations from nature, which instead evolve according to some stochastic process. From the computational lens, even generating a single sample from the true MRF distribution is intractable unless $\mathsf{NP}=\mathsf{RP}$, and moreover, any algorithm to learn from i.i.d. samples requires prohibitive runtime due to hardness reductions to the parity with noise problem. These computational barriers for sampling and learning from the i.i.d. setting severely lessen the utility of these breakthrough results for this important task; however, dropping this assumption typically only introduces further algorithmic and statistical complexities. In this work, we surprisingly demonstrate that the direct trajectory data from a natural evolution of the MRF overcomes the fundamental computational lower bounds to efficient learning. In particular, we show that given a trajectory with $\widetilde{O}_k(n)$ site updates of an order $k$ MRF from the Glauber dynamics, a well-studied, natural stochastic process on graphical models, there is an algorithm that recovers the graph and the parameters in $\widetilde{O}_k(n^2)$ time. By contrast, all prior algorithms for learning order $k$ MRFs inherently suffer from $n^{\Theta(k)}$ runtime even in sparse instances due to the reductions to sparse parity with noise. Our results thus surprisingly show that this more realistic, but intuitively less tractable, model for MRFs actually leads to efficiency far beyond what is known and believed to be true in the traditional i.i.d. case.

Related papers

• Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models [49.81937966106691]
  We develop a suite of non-asymptotic theory towards understanding the data generation process of diffusion models. In contrast to prior works, our theory is developed based on an elementary yet versatile non-asymptotic approach.
  arXiv  Detail & Related papers  (2023-06-15T16:30:08Z)
• Multisample Flow Matching: Straightening Flows with Minibatch Couplings [38.82598694134521]
  Simulation-free methods for training continuous-time generative models construct probability paths that go between noise distributions and individual data samples. We propose Multisample Flow Matching, a more general framework that uses non-trivial couplings between data and noise samples. We show that our proposed methods improve sample consistency on downsampled ImageNet data sets, and lead to better low-cost sample generation.
  arXiv  Detail & Related papers  (2023-04-28T11:33:08Z)
• Smoothly Giving up: Robustness for Simple Models [30.56684535186692]
  Examples of algorithms to train such models include logistic regression and boosting. We use $Served-Served joint convex loss functions, which tunes between canonical convex loss functions, to robustly train such models. We also provide results for boosting a COVID-19 dataset for logistic regression, highlighting the efficacy approach across multiple relevant domains.
  arXiv  Detail & Related papers  (2023-02-17T19:48:11Z)
• Learning from aggregated data with a maximum entropy model [73.63512438583375]
  We show how a new model, similar to a logistic regression, may be learned from aggregated data only by approximating the unobserved feature distribution with a maximum entropy hypothesis. We present empirical evidence on several public datasets that the model learned this way can achieve performances comparable to those of a logistic model trained with the full unaggregated data.
  arXiv  Detail & Related papers  (2022-10-05T09:17:27Z)
• The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
  We show that deviating from this assumption can actually lead to better statistical estimators. In particular, the optimal noise distribution is different from the data's and even from a different family.
  arXiv  Detail & Related papers  (2022-03-02T13:59:20Z)
• 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)
• Learning based signal detection for MIMO systems with unknown noise statistics [84.02122699723536]
  This paper aims to devise a generalized maximum likelihood (ML) estimator to robustly detect signals with unknown noise statistics. In practice, there is little or even no statistical knowledge on the system noise, which in many cases is non-Gaussian, impulsive and not analyzable. Our framework is driven by an unsupervised learning approach, where only the noise samples are required.
  arXiv  Detail & Related papers  (2021-01-21T04:48:15Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  We study the problem of least squares linear regression where the data-points are dependent and are sampled from a Markov chain. We establish sharp information theoretic minimax lower bounds for this problem in terms of $tau_mathsfmix$. We propose an algorithm based on experience replay--a popular reinforcement learning technique--that achieves a significantly better error rate.
  arXiv  Detail & Related papers  (2020-06-16T04:26:50Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)

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.