論文の概要: Convergence of linear programming hierarchies for Gibbs states of spin systems

• arxiv url: http://arxiv.org/abs/2506.06125v1
• Date: Fri, 06 Jun 2025 14:35:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-09 17:28:43.517491
• Title: Convergence of linear programming hierarchies for Gibbs states of spin systems
• Title（参考訳）: スピン系のギブス状態に対する線形計画的階層の収束
• Authors: Hamza Fawzi, Omar Fawzi,
• Abstract要約: 本稿では,スピン系のギブス分布の下での局所関数の期待値の計算問題を考察する。 第1階層は局所スピンフリップ平等を課し、高エネルギー物理学におけるブートストラップの文献において検討されている。 2番目の階層は、ギブズ状態を固定点とするマルコフ連鎖に基づいており、最適化文献、最近ではブートストラップ文献で研究されている。
• 参考スコア（独自算出の注目度）: 11.479315794880343
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of computing expectation values of local functions under the Gibbs distribution of a spin system. In particular, we study two families of linear programming hierarchies for this problem. The first hierarchy imposes local spin flip equalities and has been considered in the bootstrap literature in high energy physics. For this hierarchy, we prove fast convergence under a spatial mixing (decay of correlations) condition. This condition is satisfied for example above the critical temperature for Ising models on a $d$-dimensional grid. The second hierarchy is based on a Markov chain having the Gibbs state as a fixed point and has been studied in the optimization literature and more recently in the bootstrap literature. For this hierarchy, we prove fast convergence provided the Markov chain mixes rapidly. Both hierarchies lead to an $\varepsilon$-approximation for local expectation values using a linear program of size quasi-polynomial in $n/\varepsilon$, where $n$ is the total number of sites, provided the interactions can be embedded in a $d$-dimensional grid with constant $d$. Compared to standard Monte Carlo methods, an advantage of this approach is that it always (i.e., for any system) outputs rigorous upper and lower bounds on the expectation value of interest, without needing an a priori analysis of the convergence speed.
• Abstract（参考訳）: 本稿では,スピン系のギブス分布の下での局所関数の期待値の計算問題を考察する。 特に,この問題に対する線形プログラミング階層の2つのファミリについて検討する。 第1階層は局所スピンフリップ平等を課し、高エネルギー物理学におけるブートストラップの文献において検討されている。 この階層に対して、空間混合(相関のデカイ)条件下での高速収束を証明した。 この条件は例えば、$d$次元格子上のイジングモデルの臨界温度以上で満たされる。 2番目の階層は、ギブズ状態を固定点とするマルコフ連鎖に基づいており、最適化文献、最近ではブートストラップ文献で研究されている。 この階層に対して、マルコフ連鎖が急速に混合されるとき、高速収束が証明される。 どちらの階層も$\varepsilon$-approximation for local expectation value for a linear program of size quasi-polynomial in $n/\varepsilon$, where $n$ is the total number of sites, if the interaction can embedded in a $d$-dimensional grid with constant $d$. 標準モンテカルロ法と比較して、このアプローチの利点は、収束速度の先行解析を必要とせず、常に(任意の系に対して)利子の期待値に対して厳密な上限と下限を出力することである。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• A hierarchy of eigencomputations for polynomial optimization on the sphere [0.0]
  単位球面上の実形式の最小値に下界の収束階層を導入する。 実和-二乗階層に対する我々の階層の主な実用的利点は、各レベルの下限が最小の固有値によって得られることである。
  論文  参考訳（メタデータ） (2023-10-27T00:28:12Z)
• Generalization Bounds for Stochastic Gradient Descent via Localized $\varepsilon$-Covers [16.618918548497223]
  本稿では,SGDの軌道に局在する新しい被覆手法を提案する。 このローカライゼーションは、境界数によって測定されるアルゴリズム固有のクラスタリングを提供する。 これらの結果は様々な文脈で導き出され、既知の最先端のラベルレートが向上する。
  論文  参考訳（メタデータ） (2022-09-19T12:11:07Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  バイレベル最適化は、幅広い機械学習モデルに適用されている。 既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。 そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-30T05:29:52Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• An Improved Analysis of Gradient Tracking for Decentralized Machine Learning [34.144764431505486]
  トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。 エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。 ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
  論文  参考訳（メタデータ） (2022-02-08T12:58:14Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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