On the Approximation Complexity of Matrix Product Operator Born Machines

• URL: http://arxiv.org/abs/2605.11471v1
• Date: Tue, 12 May 2026 03:38:49 GMT
• Title: On the Approximation Complexity of Matrix Product Operator Born Machines
• Abstract summary: Matrix product operator Born machines (MPO-BMs) are tractable tensor-network models for probabilistic modeling.<n>We prove that KL approximation is NP-hard for MPO-BMs in the continuous setting.<n>We also show that, under a locality and spectral-gap conditions on the loss-induced Hamiltonian, structured targets admit MPO-BM approximations with bond and provable KL guarantees.
• Score: 27.03788036535737
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Matrix product operator Born machines (MPO-BMs) are tractable tensor-network models for probabilistic modeling, but their efficient approximation capability remains unclear. We characterize this boundary from both negative and positive perspectives. First, we prove that KL approximation is NP-hard for MPO-BMs in the continuous setting, ruling out universal efficient approximation in the worst case. Second, for score-based variational inference, we show that, under a locality and spectral-gap conditions on the loss-induced Hamiltonian, structured targets (e.g., path-graph Markov random fields) admit MPO-BM approximations with polynomial bond dimension and provable KL guarantees. Third, under the same locality structure, we prove that polynomially many score queries suffice to estimate the induced Hamiltonian and obtain such guarantees. Our results provide a theoretical characterization of when MPO-BMs are fundamentally hard to approximate and when they become efficiently learnable.

Related papers

• Gaussian mixtures and non-parametric likelihoods through the lens of statistical mechanics [6.219242821194725]
  We investigate the problem of non parametric maximum likelihood estimation (it abbrv NPMLE) from the perspective of statistical mechanics.<n>We establish stability guarantees for the NPMLE procedure that extend well beyond the state of the art.<n>We provide high probability upper bounds on the KL divergence between the NPMLE and the true density that are of the order of $minbigfrac(log n)d+2n, fraclog nsqrt nbig$.
  arXiv  Detail & Related papers  (2026-03-24T13:42:57Z)
• Learning Overspecified Gaussian Mixtures Exponentially Fast with the EM Algorithm [5.625796693054093]
  We investigate the convergence properties of the EM algorithm when applied to overspecified Gaussian mixture models.<n>We demonstrate that the population EM algorithm converges exponentially fast in terms of the Kullback-Leibler (KL) distance.
  arXiv  Detail & Related papers  (2025-06-13T14:57:57Z)
• Conditional Distribution Quantization in Machine Learning [83.54039134248231]
  Conditional expectation mathbbE(Y mid X) often fails to capture the complexity of multimodal conditional distributions mathcalL(Y mid X)<n>We propose using n-point conditional quantizations--functional mappings of X that are learnable via gradient descent--to approximate mathcalL(Y mid X)
  arXiv  Detail & Related papers  (2025-02-11T00:28:24Z)
• A relativistic continuous matrix product state study of field theories with defects [0.0]
  We propose a method to compute expectation values in massive Quantum Field Theories with line defects.<n>We use a quantization scheme where (imaginary) time runs perpendicularly to the defect.<n>We demonstrate the effectiveness of this machinery by computing correlation functions of local bulk and defect operators in $phi4$ theory with a magnetic line defect.
  arXiv  Detail & Related papers  (2025-01-16T19:00:23Z)
• Statistical Inference for Temporal Difference Learning with Linear Function Approximation [55.80276145563105]
  We investigate the statistical properties of Temporal Difference learning with Polyak-Ruppert averaging.<n>We make three theoretical contributions that improve upon the current state-of-the-art results.
  arXiv  Detail & Related papers  (2024-10-21T15:34:44Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity [2.685668802278156]
  We show that Q-learning for standard Borel MDPs via quantization of states and actions converges to a limit. Our paper presents a very general convergence and approximation result for the applicability of Q-learning for continuous MDPs.
  arXiv  Detail & Related papers  (2021-11-12T15:47:10Z)
• Non-Markovian Stochastic Schr\"odinger Equation: Matrix Product State Approach to the Hierarchy of Pure States [65.25197248984445]
  We derive a hierarchy of matrix product states (HOMPS) for non-Markovian dynamics in open finite temperature. The validity and efficiency of HOMPS is demonstrated for the spin-boson model and long chains where each site is coupled to a structured, strongly non-Markovian environment.
  arXiv  Detail & Related papers  (2021-09-14T01:47:30Z)
• Emergent statistical mechanics from properties of disordered random matrix product states [1.3075880857448061]
  We introduce a picture of generic states within the trivial phase of matter with respect to their non-equilibrium and entropic properties. We prove that disordered random matrix product states equilibrate exponentially well with overwhelming probability under the time evolution of Hamiltonians. We also prove two results about the entanglement Renyi entropy.
  arXiv  Detail & Related papers  (2021-03-03T19:05:26Z)
• The Variational Method of Moments [65.91730154730905]
  conditional moment problem is a powerful formulation for describing structural causal parameters in terms of observables. Motivated by a variational minimax reformulation of OWGMM, we define a very general class of estimators for the conditional moment problem. We provide algorithms for valid statistical inference based on the same kind of variational reformulations.
  arXiv  Detail & Related papers  (2020-12-17T07:21:06Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)

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.