論文の概要: Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains

• arxiv url: http://arxiv.org/abs/2305.05097v3
• Date: Sun, 28 Jan 2024 22:04:51 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-30 22:57:06.179888
• Title: Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains
• Title（参考訳）: 一般グラフ上の自己反発ランダムウォーク --非線形マルコフ連鎖による最小サンプリング変動の実現
• Authors: Vishwaraj Doshi, Jie Hu and Do Young Eun
• Abstract要約: ランダムウォーカーは、サンプリングと近傍探索により、ネットワークトポロジ上のターゲット量を近似するように設計されている。 目的とする確率分布に対応するマルコフ連鎖が与えられた場合、過去に頻繁に訪れたノードに遷移する可能性が低く、滅多に訪れないノードに遷移する可能性が低い自己反発ランダムウォーク(SRRW)を設計する。 正の実アルファでパラメータ化されたSRRWのクラスに対して、プロセスの経験的分布がターゲットにほぼ確実に収束することを証明する。
• 参考スコア（独自算出の注目度）: 11.3631620309434
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We consider random walks on discrete state spaces, such as general undirected graphs, where the random walkers are designed to approximate a target quantity over the network topology via sampling and neighborhood exploration in the form of Markov chain Monte Carlo (MCMC) procedures. Given any Markov chain corresponding to a target probability distribution, we design a self-repellent random walk (SRRW) which is less likely to transition to nodes that were highly visited in the past, and more likely to transition to seldom visited nodes. For a class of SRRWs parameterized by a positive real {\alpha}, we prove that the empirical distribution of the process converges almost surely to the the target (stationary) distribution of the underlying Markov chain kernel. We then provide a central limit theorem and derive the exact form of the arising asymptotic co-variance matrix, which allows us to show that the SRRW with a stronger repellence (larger {\alpha}) always achieves a smaller asymptotic covariance, in the sense of Loewner ordering of co-variance matrices. Especially for SRRW-driven MCMC algorithms, we show that the decrease in the asymptotic sampling variance is of the order O(1/{\alpha}), eventually going down to zero. Finally, we provide numerical simulations complimentary to our theoretical results, also empirically testing a version of SRRW with {\alpha} increasing in time to combine the benefits of smaller asymptotic variance due to large {\alpha}, with empirically observed faster mixing properties of SRRW with smaller {\alpha}.
• Abstract（参考訳）: 一般非向グラフのような離散状態空間上のランダムウォークを考えると、ランダムウォーカーはマルコフ連鎖モンテカルロ (mcmc) 手順の形でサンプリングと近傍探索を通じてネットワークトポロジー上の対象量を近似するように設計されている。 目的とする確率分布に対応するマルコフ連鎖が与えられた場合、過去に頻繁に訪れたノードに遷移する可能性が低く、滅多に訪れないノードに遷移する可能性が低い自己反発ランダムウォーク(SRRW)を設計する。 正の実 {\alpha} でパラメータ化された SRRW のクラスに対して、過程の経験的分布は、基礎となるマルコフ連鎖核の標的(定常的)分布にほぼ確実に収束することを示す。 すると、中心極限定理を提供し、生成する漸近共分散行列の正確な形を導出し、より強い忌避性を持つsrrw( larger {\alpha})が常により小さい漸近共分散(英語版)(loewner order of co-variance matrice)となることを示すことができる。 特に、SRRW駆動のMCMCアルゴリズムでは、漸近サンプリング分散の減少はO(1/{\alpha})の次数であり、最終的には0となる。 最後に, 理論結果に補完する数値シミュレーションを行い, srrwのバージョンと時間とともに増加する {\alpha} を実験的に実験し, より大きな {\alpha} による漸近的分散の利点と, より小さな {\alpha} を持つsrrwのより高速な混合特性を経験的に観測した。

関連論文リスト

• Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks [11.3631620309434]
  エージェントのネットワークをランダムウォーク方式で横断するトークンによって勾配をサンプリングする分散最適化アルゴリズムの一群について検討する。 我々は、正則線型マルコフトークンを非線形マルコフ連鎖、すなわち自己推進ラドムウォーク(SRRW)に従うものに置き換えることで、新しいアプローチをとる。 結果のSA-SRRWの最適化誤差はほぼ確実にゼロに収束し、中心極限定理を証明する。
  論文  参考訳（メタデータ） (2024-01-18T00:50:37Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。 本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
  論文  参考訳（メタデータ） (2023-06-27T08:15:28Z)
• When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm? [4.657614491309671]
  本研究では, 磁化ハミルトン・モンテカルロ (HMC) と跳躍フロッグ積分器の混合時間について解析した。 連続HMC力学の離散化における位置と速度変数の結合分布は, ほぼ不変であることを示す。
  論文  参考訳（メタデータ） (2023-04-10T17:35:57Z)
• Stochastic Gradient Descent under Markovian Sampling Schemes [3.04585143845864]
  マルコフ型サンプリングスキームにのみアクセス可能なバニラ勾配勾配の変動について検討する。 我々は、基礎となるマルコフ連鎖で可能な最小限の制限的な仮定の下で収束率を得ることに焦点をあてる。
  論文  参考訳（メタデータ） (2023-02-28T09:18:00Z)
• Random Forest Weighted Local Fr\'echet Regression with Random Objects [52.25304029942005]
  本稿では,新しいランダム森林重み付き局所Fr'echet回帰パラダイムを提案する。 最初の方法は,これらの重みを局所平均として利用し,条件付きFr'echet平均を解く。 第二の手法は局所線形Fr'echet回帰を行い、どちらも既存のFr'echet回帰法を大幅に改善した。
  論文  参考訳（メタデータ） (2022-02-10T09:10:59Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  ハイブリッドモンテカルロ(Hybrid Monte Carlo)は、複素連続分布からサンプリングする強力なマルコフ連鎖モンテカルロ法である。 本稿では,SurVAEフローを用いたモンテカルロ法の拡張に基づく新しい手法を提案する。 本稿では,統計学,計算物理学,機械学習など,様々な分野におけるアルゴリズムの有効性を実証し,代替アルゴリズムと比較した改良点を考察する。
  論文  参考訳（メタデータ） (2021-02-04T02:21:08Z)

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

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