論文の概要: Many processors, little time: MCMC for partitions via optimal transport couplings

• arxiv url: http://arxiv.org/abs/2202.11258v1
• Date: Wed, 23 Feb 2022 01:20:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-25 04:18:09.502482
• Title: Many processors, little time: MCMC for partitions via optimal transport couplings
• Title（参考訳）: 多くのプロセッサ、わずかな時間:最適輸送結合による分割のためのMCMC
• Authors: Tin D. Nguyen and Brian L. Trippe and Tamara Broderick
• Abstract要約: 既存の結合概念の離散クラスタリング変数への直接的な応用は、すぐには満たされないことを示す。 この失敗は「ラベルスイッチング問題(label-switching problem)」から生じ、意味論的に等価なクラスタレバリングは結合鎖の高速な一致を妨げる。 分割空間上の計量を用いて、最適な輸送結合を用いて実用的なアルゴリズムを定式化する。
• 参考スコア（独自算出の注目度）: 17.248439315751227
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Markov chain Monte Carlo (MCMC) methods are often used in clustering since they guarantee asymptotically exact expectations in the infinite-time limit. In finite time, though, slow mixing often leads to poor performance. Modern computing environments offer massive parallelism, but naive implementations of parallel MCMC can exhibit substantial bias. In MCMC samplers of continuous random variables, Markov chain couplings can overcome bias. But these approaches depend crucially on paired chains meetings after a small number of transitions. We show that straightforward applications of existing coupling ideas to discrete clustering variables fail to meet quickly. This failure arises from the "label-switching problem": semantically equivalent cluster relabelings impede fast meeting of coupled chains. We instead consider chains as exploring the space of partitions rather than partitions' (arbitrary) labelings. Using a metric on the partition space, we formulate a practical algorithm using optimal transport couplings. Our theory confirms our method is accurate and efficient. In experiments ranging from clustering of genes or seeds to graph colorings, we show the benefits of our coupling in the highly parallel, time-limited regime.
• Abstract（参考訳）: マルコフ連鎖モンテカルロ法(MCMC)は、無限時間極限における漸近的に正確な期待を保証するため、クラスタリングにおいてしばしば用いられる。 しかし、有限時間では、遅い混合はしばしば性能を低下させる。 現代の計算環境は膨大な並列性を提供するが、並列MCMCの実装には重大なバイアスが生じる。 連続確率変数のMCMCサンプリングでは、マルコフ連鎖結合はバイアスを克服することができる。 しかしこれらのアプローチは、少数の移行の後、ペアのチェーンミーティングに大きく依存します。 分散クラスタリング変数に対する既存の結合アイデアの直接的な応用は、すぐには満たせないことを示す。 この失敗は「ラベルスイッチング問題(label-switching problem)」から生じ、意味論的に等価なクラスタレバリングは結合鎖の高速な一致を妨げる。 チェーンは、パーティションの(任意な)ラベル付けではなく、パーティションの空間を探索するものだと考えています。 分割空間上の計量を用いて最適な輸送結合を用いた実用的なアルゴリズムを定式化する。 我々の理論は、この方法が正確で効率的であることを確認する。 遺伝子や種子のクラスタリングからグラフの着色まで幅広い実験において,高度に並列な時間制限された構造における結合の利点を示す。

関連論文リスト

• Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
  実用的な分散システムでは、労働者は概して均質ではなく、非常に多様な処理時間を持つ。 本稿では、任意に遅い計算を扱うための新しい並列手法Freyaを提案する。 Freyaは従来の手法と比較して,複雑性の保証が大幅に向上していることを示す。
  論文  参考訳（メタデータ） (2024-05-24T13:33:30Z)
• Adversarial Schrödinger Bridge Matching [66.39774923893103]
  反復マルコフフィッティング(IMF)手順は、マルコフ過程の相互射影と相互射影を交互に交互に行う。 本稿では、プロセスの学習を離散時間でほんの少しの遷移確率の学習に置き換える新しい離散時間IMF(D-IMF)手順を提案する。 D-IMFの手続きは、数百ではなく数世代のステップで、IMFと同じ品質の未完成のドメイン翻訳を提供できることを示す。
  論文  参考訳（メタデータ） (2024-05-23T11:29:33Z)
• Distributed MCMC inference for Bayesian Non-Parametric Latent Block Model [0.24578723416255754]
  ベイジアン非パラメトリック潜在ブロックモデル(DisNPLBM)のための分散マルコフ連鎖モンテカルロ(MCMC)推論手法を提案する。 我々の非パラメトリックコクラスタリングアルゴリズムは、潜在多変量ガウスブロック分布を用いて観測と特徴を分割する。 DisNPLBMは、実験結果を通じてクラスタラベリングの精度と実行時間に与える影響を実証する。
  論文  参考訳（メタデータ） (2024-02-01T22:43:55Z)
• SpreadNUTS -- Moderate Dynamic Extension of Paths for No-U-Turn Sampling & Partitioning Visited Regions [0.0]
  本稿では,no-U-turn sampler (NUTS) として知られる特定のハミルトンモンテカルロ (HMC) アルゴリズムの変更を紹介する。 NUTS は NUTS よりも早くサンプル空間を探索することを目的としており、真分布への収束が NUTS より高速なサンプリング器を提供する。
  論文  参考訳（メタデータ） (2023-07-09T05:00:25Z)
• Improved Bound for Mixing Time of Parallel Tempering [4.68299658663016]
  パラレルテンパリングのための新しい下限を、$log L$を除く全てのパラメータにマルチモーダル依存を持つスペクトルギャップ上で提示する。 これにより、モードの数に指数関数的に依存する最良の既存の境界が改善される。 スペクトルギャップ上の仮定上界は$log L$に指数関数依存しており、ある意味では我々の境界は密であることを示す。
  論文  参考訳（メタデータ） (2023-04-03T19:03:22Z)
• Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic [61.968469104271676]
  本稿では,アクター・アクターとアクター・アクター・アクター・アルゴリズムに埋め込まれた平均報酬に対して,マルチレベルモンテカルロ推定器を用いて混合時間に適応したRL手法を提案する。 不安定な報酬を伴うRL問題において,安定性に要求される技術的条件の緩和効果が,実用上優れた性能に変換されることを実験的に示す。
  論文  参考訳（メタデータ） (2023-01-28T04:12:56Z)
• Parallel Approaches to Accelerate Bayesian Decision Trees [1.9728521995447947]
  本稿では,MCMCにおける並列性を利用した2つの手法を提案する。 第一に、MCMCを別の数値ベイズ的アプローチで置き換える。 第2に、データのパーティショニングについて検討する。
  論文  参考訳（メタデータ） (2023-01-22T09:56:26Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  本稿では、最適化問題を解くための一般的な枠組みとして、ディラックの制約付きハミルトン系理論の散逸拡張を提案する。 我々の(加速された)アルゴリズムのクラスは単純で効率的なだけでなく、幅広い文脈にも適用できる。
  論文  参考訳（メタデータ） (2021-07-23T13:43:34Z)
• What Are Bayesian Neural Network Posteriors Really Like? [63.950151520585024]
  ハミルトニアンモンテカルロは、標準およびディープアンサンブルよりも大きな性能向上を達成できることを示す。 また,深部分布は標準SGLDとHMCに類似しており,標準変動推論に近いことが示された。
  論文  参考訳（メタデータ） (2021-04-29T15:38:46Z)
• Contrastive learning of strong-mixing continuous-time stochastic processes [53.82893653745542]
  コントラスト学習(Contrastive Learning)は、ラベルのないデータから構築された分類タスクを解決するためにモデルを訓練する自己指導型の手法のファミリーである。 拡散の場合,小～中距離間隔の遷移カーネルを適切に構築したコントラスト学習タスクを用いて推定できることが示される。
  論文  参考訳（メタデータ） (2021-03-03T23:06:47Z)
• AMAGOLD: Amortized Metropolis Adjustment for Efficient Stochastic Gradient MCMC [37.768023232677244]
  ハミルトニアン・モンテカルロ(英語版)(SGHMC)は、連続分布からサンプリングする効率的な方法である。 本稿では、しばしばメトロポリス・ハスティング(M-H)補正を用いてバイアスを除去する2次SG-MCMCアルゴリズム--AMAGOLDを提案する。 我々は, AMAGOLD が減少するステップサイズではなく, 目標分布に収束し, 収束速度が全バッチベースラインよりも遅くなることを証明した。
  論文  参考訳（メタデータ） (2020-02-29T06:57:43Z)

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

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