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.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.11471 [cs.LG] |
| (or arXiv:2605.11471v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.11471 arXiv-issued DOI via DataCite (pending registration) |
From: Chao Li [view email]
[v1]
Tue, 12 May 2026 03:38:49 UTC (4,254 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。