arXiv:2511.21008cs.LGstat.ML2025-11被引 2

提出统一方法,高效估计伊辛模型在总变差距离下的参数。

Estimating Ising Models in Total Variation Distance

  • 用伪极大似然法分析两类伊辛模型的估计问题。
  • 在多种条件下实现近最优采样复杂度与多项式时间算法。
  • 适合研究统计学习与马尔可夫链收敛性的学者参考。

我们研究在给定 $l$ 个独立样本下,通过总变差(TV)距离估计 $n$ 变量伊辛模型的问题。尽管该问题的统计复杂性已明确 [DMR20],但设计计算与统计上高效的算法仍具挑战。此前在树状图 [DP21, BGPV21]、交互矩阵服从高斯分布 [GM24, CK24],或其大部分特征值位于小区间 [AJK+24, KLV24] 等特定情形取得显著进展,但尚无适用于多项式时间估计的统一框架。本文主贡献在于对两类通用伊辛模型的伪极大似然估计器(MPLE)进行统一分析:第一类满足有界算子范数且符合修正对数索博列夫不等式(MLSI),该不等式用于研究关联吉布斯动力学的收敛性;第二类中交互矩阵具有有界无穷范数(或有界宽度),这是文献中结构学习的常见假设。我们证明了这些通用结果可导出多种场景下的多项式时间算法与最优或近最优采样复杂度。证明过程结合了张量化不等式、测度分解及集中不等式等多种工具。

原文摘要 · Abstract (English)

We consider the problem of estimating Ising models over $n$ variables in Total Variation (TV) distance, given $l$ independent samples from the model. While the statistical complexity of the problem is well-understood [DMR20], identifying computationally and statistically efficient algorithms has been challenging. In particular, remarkable progress has occurred in several settings, such as when the underlying graph is a tree [DP21, BGPV21], when the entries of the interaction matrix follow a Gaussian distribution [GM24, CK24], or when the bulk of its eigenvalues lie in a small interval [AJK+24, KLV24], but no unified framework for polynomial-time estimation in TV exists so far. Our main contribution is a unified analysis of the Maximum Pseudo-Likelihood Estimator (MPLE) for two general classes of Ising models. The first class includes models that have bounded operator norm and satisfy the Modified Log-Sobolev Inequality (MLSI), a functional inequality that was introduced to study the convergence of the associated Glauber dynamics to stationarity. In the second class of models, the interaction matrix has bounded infinity norm (or bounded width), which is the most common assumption in the literature for structure learning of Ising models. We show how our general results for these classes yield polynomial-time algorithms and optimal or near-optimal sample complexity guarantees in a variety of settings. Our proofs employ a variety of tools from tensorization inequalities to measure decompositions and concentration bounds.

伊辛模型统计估计总变差距离伪极大似然

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。