論文の概要: Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs
- arxiv url: http://arxiv.org/abs/2505.18300v1
- Date: Fri, 23 May 2025 18:46:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-27 16:58:42.332177
- Title: Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs
- Title（参考訳）: 自己反発カーネルを超えて: 汎用グラフ上での効率的な非線形MCMCに向けた履歴駆動目標
- Authors: Jie Hu, Yi-Ting Ma, Do Young Eun,
- Abstract要約: 我々はマルコフ・チェイン・モンテカルロ(MCMC)における履歴駆動型目標(HDT)フレームワークを提案し、離散状態空間におけるランダムウォークアルゴリズムを改善する。
また,HDTは,現在の状態と提案状態の局所的な情報のみを必要とすることにより,軽量な実装を保っていることを示す。
グラフサンプリング実験は、一貫したパフォーマンス向上を示し、メモリ効率の高いLRUキャッシュは、大規模な汎用グラフへのスケーラビリティを保証する。
- 参考スコア（独自算出の注目度）: 7.434126318858966
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose a history-driven target (HDT) framework in Markov Chain Monte Carlo (MCMC) to improve any random walk algorithm on discrete state spaces, such as general undirected graphs, for efficient sampling from target distribution $\boldsymbol{\mu}$. With broad applications in network science and distributed optimization, recent innovations like the self-repellent random walk (SRRW) achieve near-zero variance by prioritizing under-sampled states through transition kernel modifications based on past visit frequencies. However, SRRW's reliance on explicit computation of transition probabilities for all neighbors at each step introduces substantial computational overhead, while its strict dependence on time-reversible Markov chains excludes advanced non-reversible MCMC methods. To overcome these limitations, instead of direct modification of transition kernel, HDT introduces a history-dependent target distribution $\boldsymbol{\pi}[\mathbf{x}]$ to replace the original target $\boldsymbol{\mu}$ in any graph sampler, where $\mathbf{x}$ represents the empirical measure of past visits. This design preserves lightweight implementation by requiring only local information between the current and proposed states and achieves compatibility with both reversible and non-reversible MCMC samplers, while retaining unbiased samples with target distribution $\boldsymbol{\mu}$ and near-zero variance performance. Extensive experiments in graph sampling demonstrate consistent performance gains, and a memory-efficient Least Recently Used (LRU) cache ensures scalability to large general graphs.
- Abstract（参考訳）: 我々はマルコフ・チェイン・モンテカルロ(MCMC)において、ターゲット分布から効率的にサンプリングするために、一般的な無向グラフのような離散状態空間におけるランダムウォークアルゴリズムを改善するために、履歴駆動型ターゲット(HDT)フレームワークを提案する。
ネットワーク科学と分散最適化の幅広い応用により、近年の自己反発ランダムウォーク(SRRW)のような革新は、過去の訪問頻度に基づく遷移カーネル修正を通じてアンダーサンプル状態の優先順位付けによって、ほぼゼロの分散を実現する。
しかし、SRRWが各ステップにおけるすべての隣人に対する遷移確率の明示的な計算に依存していることは、かなりの計算オーバーヘッドをもたらす一方、時間的に可逆なマルコフ連鎖への厳密な依存は、高度な非可逆MCMC法を除外する。
これらの制限を克服するため、遷移カーネルを直接修正するのではなく、HDTは履歴に依存したターゲット分布 $\boldsymbol{\pi}[\mathbf{x}]$ を導入し、元のターゲットである $\boldsymbol{\mu}$ を置き換える。
この設計は、現在の状態と提案状態の間のローカル情報のみを必要とすることで軽量な実装を保ち、ターゲット分布が$\boldsymbol{\mu}$とほぼゼロの分散性能を持つ未バイアスのサンプルを保持しながら、可逆および非可逆MCMCMCサンプルとの互換性を実現する。
グラフサンプリングにおける大規模な実験は、一貫したパフォーマンス向上を示し、メモリ効率の高いLRUキャッシュは、大規模な汎用グラフへのスケーラビリティを保証する。
関連論文リスト
- Self-Repellent Random Walks on General Graphs -- Achieving Minimal
Sampling Variance via Nonlinear Markov Chains [11.3631620309434]
ランダムウォーカーは、サンプリングと近傍探索により、ネットワークトポロジ上のターゲット量を近似するように設計されている。
目的とする確率分布に対応するマルコフ連鎖が与えられた場合、過去に頻繁に訪れたノードに遷移する可能性が低く、滅多に訪れないノードに遷移する可能性が低い自己反発ランダムウォーク(SRRW)を設計する。
正の実アルファでパラメータ化されたSRRWのクラスに対して、プロセスの経験的分布がターゲットにほぼ確実に収束することを証明する。
論文 参考訳（メタデータ） (2023-05-08T23:59:09Z) - Stochastic Gradient Descent under Markovian Sampling Schemes [3.04585143845864]
マルコフ型サンプリングスキームにのみアクセス可能なバニラ勾配勾配の変動について検討する。
我々は、基礎となるマルコフ連鎖で可能な最小限の制限的な仮定の下で収束率を得ることに焦点をあてる。
論文 参考訳（メタデータ） (2023-02-28T09:18:00Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳（メタデータ） (2023-02-08T08:17:43Z) - Least Squares Regression with Markovian Data: Fundamental Limits and
Algorithms [69.45237691598774]
マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。
この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。
本稿では,経験的リプレイに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-16T04:26:50Z) - 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) - AMAGOLD: Amortized Metropolis Adjustment for Efficient Stochastic
Gradient MCMC [37.768023232677244]
ハミルトニアン・モンテカルロ(英語版)(SGHMC)は、連続分布からサンプリングする効率的な方法である。
本稿では、しばしばメトロポリス・ハスティング(M-H)補正を用いてバイアスを除去する2次SG-MCMCアルゴリズム--AMAGOLDを提案する。
我々は, AMAGOLD が減少するステップサイズではなく, 目標分布に収束し, 収束速度が全バッチベースラインよりも遅くなることを証明した。
論文 参考訳（メタデータ） (2020-02-29T06:57:43Z) - Improving Sampling Accuracy of Stochastic Gradient MCMC Methods via
Non-uniform Subsampling of Gradients [54.90670513852325]
サンプリング精度を向上させるための一様でないサブサンプリング手法を提案する。
EWSGは、一様勾配MCMC法がバッチ勾配MCMC法の統計的挙動を模倣するように設計されている。
EWSGの実践的な実装では、データインデックス上のMetropolis-Hastingsチェーンを介して、一様でないサブサンプリングを効率的に行う。
論文 参考訳（メタデータ） (2020-02-20T18:56:18Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z) - Targeted stochastic gradient Markov chain Monte Carlo for hidden Markov models with rare latent states [48.705095800341944]
隠れマルコフモデルのためのマルコフ連鎖モンテカルロ (MCMC) アルゴリズムは、しばしば前向きのサンプリング器に依存する。
これにより、時系列の長さが増加するにつれて計算が遅くなり、サブサンプリングベースのアプローチの開発が動機となる。
本稿では,パラメータの勾配を計算する際に,希少な潜伏状態に対応するオーバーサンプリング観測を対象とするサブサンプリング手法を提案する。
論文 参考訳（メタデータ） (2018-10-31T17:44:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。