論文の概要: Estimating Ising Models in Total Variation Distance
- arxiv url: http://arxiv.org/abs/2511.21008v1
- Date: Wed, 26 Nov 2025 03:15:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-27 18:37:58.9419
- Title: Estimating Ising Models in Total Variation Distance
- Title（参考訳）: 全変動距離におけるイジングモデルの推定
- Authors: Constantinos Daskalakis, Vardis Kandiros, Rui Yao,
- Abstract要約: モデルから独立して$l$の標本を与えられた場合、Isingモデルを総変分(TV)距離で$n$変数で推定する問題を考察する。
我々の主な貢献は、イジングモデルの2つの一般的なクラスに対する最大擬似等式エストリメータ(MPLE)の統一的解析である。
この結果から, 最適, 至近距離のアルゴリズムと, 様々な条件下での最適, 至近距離のサンプルの複雑性の保証が得られる。
- 参考スコア（独自算出の注目度）: 23.343281561400033
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: 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.
- Abstract（参考訳）: モデルから独立して$l$の標本を与えられた場合、Isingモデルを総変分(TV)距離で$n$変数で推定する問題を考察する。
問題の統計的複雑さはよく理解されている [DMR20] が、計算的および統計的に効率的なアルゴリズムの同定は困難である。
特に、基礎となるグラフが木[DP21, BGPV21]であるときや、相互作用行列のエントリがガウス分布[GM24, CK24]に従うとき、あるいはその固有値の大部分が小さな間隔[AJK+24, KLV24]にあるときなど、いくつかの設定で顕著な進展が起こったが、テレビにおける多項式時間推定の統一フレームワークは今のところ存在しない。
我々の主な貢献は、イジングモデルの2つの一般的なクラスに対する最大擬似等式推定器(MPLE)の統一的解析である。
第1級には、有界作用素ノルムを持ち、修正対数ソボレフ不等式 (Modified Log-Sobolev Inequality, MLSI) を満たすモデルが含まれ、これは、関連するグラウバー力学の定常性への収束を研究するために導入された関数的不等式である。
2級モデルのモデルにおいて、相互作用行列は無限大ノルム(または有界幅)を持つが、これはイジングモデルの構造学習の文献において最も一般的な仮定である。
これらのクラスに対する一般的な結果が多項式時間アルゴリズムをどのように生成するかを示し、様々な設定で最適あるいは準最適サンプル複雑性を保証する。
我々の証明は、分解と濃度境界を測定するために、テンソル化の不等式から様々なツールを用いる。
関連論文リスト
- Statistical Inference in Classification of High-dimensional Gaussian Mixture [1.2354076490479515]
高次元極限における正規化凸分類器の一般クラスの挙動について検討する。
我々の焦点は、推定器の一般化誤差と変数選択性である。
論文 参考訳（メタデータ） (2024-10-25T19:58:36Z) - Partial-Multivariate Model for Forecasting [28.120094495344453]
本稿では,問題予測のためのトランスフォーマーに基づく部分多変量モデルPMformerを提案する。
PMformerは様々な単変量モデルと完全多変量モデルより優れていることを示す。
また、PMformerの他の利点として、機能不足による効率性と堅牢性を強調します。
論文 参考訳（メタデータ） (2024-08-19T05:18:50Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。
この問題は楕円分布のペナルティ化された最大推定値として表される。
楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
論文 参考訳（メタデータ） (2022-10-21T13:19:45Z) - Sampling Approximately Low-Rank Ising Models: MCMC meets Variational
Methods [35.24886589614034]
一般相互作用が$J$である超キューブ上の二次定値イジングモデルを考える。
我々の一般的な結果は、低ランクのIsingモデルに対する最初のサンプリングアルゴリズムを示唆している。
論文 参考訳（メタデータ） (2022-02-17T21:43:50Z) - Optimal regularizations for data generation with probabilistic graphical
models [0.0]
経験的に、よく調和された正規化スキームは、推論されたモデルの品質を劇的に改善する。
生成的ペアワイドグラフィカルモデルの最大Aポストエリオーリ(MAP)推論におけるL2とL1の正規化について検討する。
論文 参考訳（メタデータ） (2021-12-02T14:45:16Z) - Generalized Matrix Factorization: efficient algorithms for fitting
generalized linear latent variable models to large data arrays [62.997667081978825]
一般化線形潜在変数モデル(GLLVM)は、そのような因子モデルを非ガウス応答に一般化する。
GLLVMのモデルパラメータを推定する現在のアルゴリズムは、集約的な計算を必要とし、大規模なデータセットにスケールしない。
本稿では,GLLVMを高次元データセットに適用するための新しい手法を提案する。
論文 参考訳（メタデータ） (2020-10-06T04:28:19Z) - Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。
本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
論文 参考訳（メタデータ） (2020-05-22T22:30:52Z) - Learning Ising models from one or multiple samples [26.00403702328348]
我々は一サンプル推定の保証を提供し、相互作用行列の族における計量エントロピーの観点から推定誤差を定量化する。
我々の技術的アプローチは、モデルの相互作用ネットワークをスパース化し、結果の条件分布への依存性を十分に弱める変数のサブセットを条件付けすることの恩恵を受ける。
論文 参考訳（メタデータ） (2020-04-20T15:17:05Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳（メタデータ） (2020-02-20T10:50:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。