論文の概要: Learning Ising Models under Hard Constraints using One Sample

• arxiv url: http://arxiv.org/abs/2509.20993v1
• Date: Thu, 25 Sep 2025 10:42:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-26 20:58:12.848188
• Title: Learning Ising Models under Hard Constraints using One Sample
• Title（参考訳）: 1つのサンプルを用いた制約条件下でのIsingモデルの学習
• Authors: Rohan Chauhan, Ioannis Panageas,
• Abstract要約: 逆温度パラメータ $beta$ of a $n$-dimensional truncated Ising model を単一サンプルを用いて推定する問題を考察する。 グラフ $G = (V,E)$ with $n$ vertices が与えられたとき、truncated Ising Model は $n$-dimensional hypercube $-1,1n$ 上の確率分布であり、各構成 $mathbfsigma$ は truncation set $S subseteq -1,1n$ に置かれ、確率 $Pr(mathbfsigma) を持つ。
• 参考スコア（独自算出の注目度）: 17.761018390014602
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of estimating inverse temperature parameter $\beta$ 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{\sigma}$ is constrained to lie in a truncation set $S \subseteq \{-1,1\}^n$ and has probability $\Pr(\mathbf{\sigma}) \propto \exp(\beta\mathbf{\sigma}^\top A\mathbf{\sigma})$ 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{\sigma}$ from a truncated Ising model, with inverse parameter $\beta^*$, underlying graph $G$ of bounded degree $\Delta$ 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{\beta}$ that is $O(\Delta^3/\sqrt{n})$-consistent with the true parameter $\beta^*$ for $k \gtrsim \log(d^2k)\Delta^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.
• Abstract（参考訳）: 逆温度パラメータ $\beta$ of a $n$-dimensional truncated Ising model を単一サンプルを用いて推定する問題を考察する。 グラフ $G = (V,E)$ with $n$ vertices が与えられたとき、truncated Ising Model は $n$-dimensional hypercube $\{-1,1\}^n$ 上の確率分布であり、各構成 $\mathbf{\sigma}$ は truncation set $S \subseteq \{-1,1\}^n$ に置かれ、確率 $\Pr(\mathbf{\sigma}) \propto \exp(\beta\mathbf{\sigma}^\top A\mathbf{\sigma})$ が $A$ は $G$ の副次行列である。 我々は最近の[Galanis et al SODA'24] の設定を採用し、ここでは、truncation set $S$ を、$k$-SAT 式を満たす代入の集合として表現することができる。 a single sample $\mathbf{\sigma}$ from a truncated Ising model, with inverse parameter $\beta^*$, underlying graph $G$ of bounded degree $\Delta$ and $S$ be expressed as the set of fulfilling assignments of a $k$-SAT formula, we design in almost $O(n)$ time an estimator $\hat{\beta}$ that that is $O(\Delta^3/\sqrt{n})$-consistent with the true parameter $\beta^*$ for $k \gtrsim \log(d^2k)\Delta^3.$ estimator is based on the maximization of pseudolihood, have have a wide analysis for a probilator [Chatterels] 提案手法は,[Daskalakis et al STOC '19, Galanis et al SODA '24] の最近の手法を一般化し,難解なIsingモデルのより困難な設定に直面する。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Models [12.746888269949407]
  2進隠れマルコフモデルに対する高次元平均推定問題を考える。 ほぼ最小限の誤差率(対数係数まで)を $|theta_*|,delta,d,n$ の関数として確立する。
  論文  参考訳（メタデータ） (2022-06-06T09:34:04Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Chi-square and normal inference in high-dimensional multi-task regression [7.310043452300736]
  本稿では,Multi-Task(MT)線形モデルにおける未知の係数行列$B*$サイズ$ptimes T$に対するカイ二乗法および正規手法を提案する。
  論文  参考訳（メタデータ） (2021-07-16T11:19:49Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。 任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
  論文  参考訳（メタデータ） (2021-03-17T00:59:33Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。 本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。 スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
  論文  参考訳（メタデータ） (2020-11-21T01:33:15Z)
• Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
  i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。 疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
  論文  参考訳（メタデータ） (2020-06-17T09:21:00Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。