仅用一个样本，就能高效估算受限伊辛模型的逆温度参数。
Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample
- 基于伪似然最大化设计估计算法，适用于单一样本场景。
- 在 $k o ext{log}(d^2k)Δ^3$ 条件下，估计误差为 $O(Δ^3/ ext{√}n)$。
- 适合处理带硬约束的统计物理与组合优化问题，如满足性公式约束的模型。
我们研究在单一样本条件下估计 $n$ 维截断伊辛模型的逆温度参数 $β$。给定图 $G = (V,E)$ 有 $n$ 个顶点，截断伊辛模型是在超立方体 $\\-1,1\ $ 上的概率分布，其中每个配置 $\mathbfσ$ 被限制在截断集 $S \subseteq \\-1,1\ $ 内，且概率满足 $\Pr(\mathbfσ) \propto \exp(β\mathbfσ^\top A\mathbfσ)$，$A$ 为图 $G$ 的邻接矩阵。我们采用 [Galanis et al. SODA'24] 的设定，即截断集 $S$ 可表示为某个 $k$-SAT 公式的满足赋值集合。给定一个来自截断伊辛模型的单一样本 $\mathbfσ$，真实逆温度为 $β^*$，图 $G$ 为有界度 $Δ$，$S$ 由 $k$-SAT 表示，在近 $O(n)$ 时间内可构造出估计量 $\hatβ$，其与真实值 $β^*$ 的误差为 $O(Δ^3/\sqrt{n})$，条件是 $k \gtrsim \log(d^2k)Δ^3$。该方法基于伪似然最大化，推广了 [Daskalakis et al. STOC '19, Galanis et al. SODA '24] 的技术，以应对更复杂的截断伊辛模型设置。
原文摘要 · Abstract (English)
We consider the problem of estimating inverse temperature parameter $β$ of an $n$-dimensional truncated Ising model using a single sample. Given a graph $G = (V,E)$ with $n$ vertices, a truncated Ising model is a probability distribution over the $n$-dimensional hypercube $\{-1,1\}^n$ where each configuration $\mathbfσ$ is constrained to lie in a truncation set $S \subseteq \{-1,1\}^n$ and has probability $\Pr(\mathbfσ) \propto \exp(β\mathbfσ^\top A\mathbfσ)$ with $A$ being the adjacency matrix of $G$. We adopt the recent setting of [Galanis et al. SODA'24], where the truncation set $S$ can be expressed as the set of satisfying assignments of a $k$-SAT formula. Given a single sample $\mathbfσ$ from a truncated Ising model, with inverse parameter $β^*$, underlying graph $G$ of bounded degree $Δ$ and $S$ being expressed as the set of satisfying assignments of a $k$-SAT formula, we design in nearly $O(n)$ time an estimator $\hatβ$ that is $O(Δ^3/\sqrt{n})$-consistent with the true parameter $β^*$ for $k \gtrsim \log(d^2k)Δ^3.$ Our estimator is based on the maximization of the pseudolikelihood, a notion that has received extensive analysis for various probabilistic models without [Chatterjee, Annals of Statistics '07] or with truncation [Galanis et al. SODA '24]. Our approach generalizes recent techniques from [Daskalakis et al. STOC '19, Galanis et al. SODA '24], to confront the more challenging setting of the truncated Ising model.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。