論文の概要: Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models

• arxiv url: http://arxiv.org/abs/2004.10805v1
• Date: Wed, 22 Apr 2020 19:21:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-10 18:50:11.824923
• Title: Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
• Title（参考訳）: 制限ボルツマンマシンとポッツモデルに対するアイデンティティテストの硬さ
• Authors: Antonio Blanca, Zongchen Chen, Daniel \v{S}tefankovi\v{c} and Eric Vigoda
• Abstract要約: 制限ボルツマンマシン(RBM)のアイデンティティテストについて検討する。 例えば、$RP neq NP$ ならば、$beta d=omega(logn)$ ならば、RBMの同一性テストは行われず、$beta d = O(logn)$ ならば、効率的な学習アルゴリズムが存在する。
• 参考スコア（独自算出の注目度）: 4.370097023410272
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study identity testing for restricted Boltzmann machines (RBMs), and more generally for undirected graphical models. Given sample access to the Gibbs distribution corresponding to an unknown or hidden model $M^*$ and given an explicit model $M$, can we distinguish if either $M = M^*$ or if they are (statistically) far apart? Daskalakis et al. (2018) presented a polynomial-time algorithm for identity testing for the ferromagnetic (attractive) Ising model. In contrast, for the antiferromagnetic (repulsive) Ising model, Bez\'akov\'a et al. (2019) proved that unless $RP=NP$ there is no identity testing algorithm when $\beta d=\omega(\log{n})$, where $d$ is the maximum degree of the visible graph and $\beta$ is the largest edge weight in absolute value. We prove analogous hardness results for RBMs (i.e., mixed Ising models on bipartite graphs), even when there are no latent variables or an external field. Specifically, we show that if $RP \neq NP$, then when $\beta d=\omega(\log{n})$ there is no polynomial-time algorithm for identity testing for RBMs; when $\beta d =O(\log{n})$ there is an efficient identity testing algorithm that utilizes the structure learning algorithm of Klivans and Meka (2017). In addition, we prove similar lower bounds for purely ferromagnetic RBMs with inconsistent external fields, and for the ferromagnetic Potts model. Previous hardness results for identity testing of Bez\'akov\'a et al. (2019) utilized the hardness of finding the maximum cuts, which corresponds to the ground states of the antiferromagnetic Ising model. Since RBMs are on bipartite graphs such an approach is not feasible. We instead introduce a general methodology to reduce from the corresponding approximate counting problem and utilize the phase transition that is exhibited by RBMs and the mean-field Potts model.
• Abstract（参考訳）: 我々は、制限ボルツマンマシン(rbms)のアイデンティティテスト、より一般的には無向グラフィカルモデルについて研究する。 未知または隠れたモデル $m^*$ に対応するgibbs ディストリビューションへのサンプルアクセスと、明示的なモデル $m$ が与えられると、$m = m^*$ か、あるいは(統計的に)遠く離れているかどうかを区別できるだろうか? Daskalakis et al. (2018) は強磁性イジングモデルに対するアイデンティティテストのための多項式時間アルゴリズムを提示した。 対照的に、反強磁性(反発的)イジングモデルに対して、bez\'akov\'a et al. (2019) は、$rp=np$ でなければ、$\beta d=\omega(\log{n})$ が可視グラフの最大次数であり$\beta$ が絶対値の最大エッジウェイトであるとき、同一性テストアルゴリズムが存在しないことを証明した。 rbms(すなわち、二成分グラフ上の混合イジングモデル)の類似の硬さ結果が、潜在変数や外部フィールドが存在しない場合でも証明される。 具体的には、$RP \neq NP$ ならば、$\beta d=\omega(\log{n})$ は RBM の恒等性テストのための多項式時間アルゴリズムはなく、$\beta d =O(\log{n})$ ならば、Klivans と Meka (2017) の構造学習アルゴリズムを利用する効率的な恒等性テストアルゴリズムが存在することを示す。 さらに, 純強磁性RBMと非整合外部場, 強磁性ポッツモデルに対して, 同様の下界を証明した。 bez\'akov\'a et al. (2019) の同一性試験における以前のハードネスは、反強磁性イジングモデルの基底状態に対応する最大カットを見つけるハードネスを利用した。 RBMは二部グラフ上であるため、そのようなアプローチは実現不可能である。 代わりに、対応する近似計数問題から減少する一般的な方法を導入し、rbmsと平均場ポッツモデルによって示される相転移を利用する。

関連論文リスト

• A computational transition for detecting correlated stochastic block models by low-degree polynomials [13.396246336911842]
  一対のランダムグラフにおける相関性の検出は、近年広く研究されている基本的な統計的および計算上の問題である。 一対の相関ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ を共通の親ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ からサブサンプリングする。 隣接部のエントリーのエンスロー度に基づくテストに焦点をあてる
  論文  参考訳（メタデータ） (2024-09-02T06:14:05Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix [1.74048653626208]
  我々は$similarity$matrix$W$で動作するアルゴリズムの性能を調査し、$W_ij$は$i$と$j$の両方を含むハイパーエッジの数を報告する。 ほぼ線形な実行時間を持つ単純かつ高効率なスペクトルアルゴリズムを設計し,min-bisectionしきい値を達成することを示す。
  論文  参考訳（メタデータ） (2022-08-23T15:22:05Z)
• Neural Implicit Manifold Learning for Topology-Aware Density Estimation [15.878635603835063]
  現在の生成モデルは、ニューラルネットワークを介して$m$次元の潜在変数をマッピングすることで、$mathcalM$を学ぶ。 我々のモデルは、プッシュフォワードモデルよりも複雑なトポロジーを持つ多様体支持分布を正確に学習できることが示される。
  論文  参考訳（メタデータ） (2022-06-22T18:00:00Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• 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)
• Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably [23.372021234032363]
  サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。 私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
  論文  参考訳（メタデータ） (2020-10-19T07:15:38Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。 格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。 NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
  論文  参考訳（メタデータ） (2020-02-25T19:18:36Z)

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

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