揭示了矩阵乘积算子玻恩机在何种条件下可高效逼近，何时则不可行。
On the Approximation Complexity of Matrix Product Operator Born Machines
- 从理论证明：连续情形下KL近似为NP难问题
- 在局部性和谱隙条件下，多项式维数即可实现有保证的近似
- 只需多项式次数的梯度查询，就能获得可靠近似结果
矩阵乘积算子玻恩机（MPO-BMs）是可用于概率建模的可计算张量网络模型，但其高效近似能力尚不明确。本文从正反两方面刻画了这一边界：首先，在连续设置下，证明了KL近似对MPO-BMs是NP难的，排除了最坏情况下的普遍高效近似；其次，针对基于得分的变分推断，若损失诱导哈密顿量满足局部性和谱隙条件，则结构化目标（如路径图马尔可夫随机场）可由多项式键维数的MPO-BM实现，并具备可证明的KL保证；第三，在相同局部结构下，证明了多项式数量的得分查询足以估计出诱导哈密顿量并获得上述保证。本研究为MPO-BMs在何种情形下本质难以逼近、何种情形下可高效学习提供了理论解释。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。