論文の概要: Efficient computation of the volume of a polytope in high-dimensions using Piecewise Deterministic Markov Processes

• arxiv url: http://arxiv.org/abs/2202.09129v1
• Date: Fri, 18 Feb 2022 11:19:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-21 19:51:19.436463
• Title: Efficient computation of the volume of a polytope in high-dimensions using Piecewise Deterministic Markov Processes
• Title（参考訳）: Piecewise Deterministic Markov Processes を用いた高次元ポリトープ体積の効率的な計算
• Authors: Augustin Chevallier, Fr\'ed\'eric Cazals, Paul Fearnhead
• Abstract要約: そこで我々はPiecewise Deterministic Markov Processを用いた新しいサンプリング戦略を提案する。 実験の結果,我々の手法は数値的に頑健であり,ハミルトン・モンテカルロを用いた既存手法よりも1桁早く(あるいはよい)ことが示唆された。
• 参考スコア（独自算出の注目度）: 1.5469452301122175
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Computing the volume of a polytope in high dimensions is computationally challenging but has wide applications. Current state-of-the-art algorithms to compute such volumes rely on efficient sampling of a Gaussian distribution restricted to the polytope, using e.g. Hamiltonian Monte Carlo. We present a new sampling strategy that uses a Piecewise Deterministic Markov Process. Like Hamiltonian Monte Carlo, this new method involves simulating trajectories of a non-reversible process and inherits similar good mixing properties. However, importantly, the process can be simulated more easily due to its piecewise linear trajectories - and this leads to a reduction of the computational cost by a factor of the dimension of the space. Our experiments indicate that our method is numerically robust and is one order of magnitude faster (or better) than existing methods using Hamiltonian Monte Carlo. On a single core processor, we report computational time of a few minutes up to dimension 500.
• Abstract（参考訳）: ポリトープの体積を高次元で計算するのは計算が難しいが、幅広い応用がある。 このようなボリュームを計算する現在の最先端のアルゴリズムは、例えばハミルトニアンモンテカルロを用いて、ポリトープに制限されたガウス分布の効率的なサンプリングに依存している。 そこで我々はPiecewise Deterministic Markov Processを用いた新しいサンプリング戦略を提案する。 ハミルトニアンモンテカルロと同様に、この新手法は非可逆過程の軌道をシミュレートし、同様の良好な混合特性を継承する。 しかし、重要なことに、この過程は分割された線形軌道のためにより容易にシミュレーションすることができ、これは空間の次元の係数による計算コストの削減に繋がる。 実験の結果,本手法は数値的に頑健であり,既存の手法よりも1桁高速(あるいはそれ以上)であることがわかった。 単一のコアプロセッサ上では,数分間の計算時間を次元500まで報告する。

関連論文リスト

• Gaussian Processes Sampling with Sparse Grids under Additive Schwarz Preconditioner [6.408773096179187]
  本稿では,GPモデルの前と後をランダムに実現するためのスケーラブルなアルゴリズムを提案する。 提案アルゴリズムはスパースグリッドを用いた点近似と加法的シュワルツプレコンディショナーを利用する。
  論文  参考訳（メタデータ） (2024-08-01T00:19:36Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood Estimation for Latent Gaussian Models [69.22568644711113]
  我々は,モンテカルロサンプリングと反復線形解法を組み合わせた確率的アンローリングを導入し,行列逆転を回避した。 理論的解析により,解法の繰り返しによる解法の解法と逆転が最大値推定の勾配推定を高速化することを示した。 シミュレーションおよび実データ実験において、確率的アンロールは、モデル性能の損失を最小限に抑えながら、勾配EMよりも桁違いに高速な潜在ガウスモデルを学習することを示した。
  論文  参考訳（メタデータ） (2023-06-05T21:08:34Z)
• Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo [104.9535542833054]
  我々は、強化学習のためのトンプソンサンプリングに基づくスケーラブルで効果的な探索戦略を提案する。 代わりに、Langevin Monte Carlo を用いて、Q 関数をその後部分布から直接サンプリングする。 提案手法は,Atari57スイートからのいくつかの挑戦的な探索課題において,最先端の深部RLアルゴリズムと比較して,より優れた,あるいは類似した結果が得られる。
  論文  参考訳（メタデータ） (2023-05-29T17:11:28Z)
• Monte Carlo Neural PDE Solver for Learning PDEs via Probabilistic Representation [59.45669299295436]
  教師なしニューラルソルバのトレーニングのためのモンテカルロPDEソルバを提案する。 我々は、マクロ現象をランダム粒子のアンサンブルとみなすPDEの確率的表現を用いる。 対流拡散, アレン・カーン, ナヴィエ・ストークス方程式に関する実験により, 精度と効率が著しく向上した。
  論文  参考訳（メタデータ） (2023-02-10T08:05:19Z)
• Gaussian process regression and conditional Karhunen-Lo\'{e}ve models for data assimilation in inverse problems [68.8204255655161]
  偏微分方程式モデルにおけるデータ同化とパラメータ推定のためのモデル逆アルゴリズムCKLEMAPを提案する。 CKLEMAP法は標準的なMAP法に比べてスケーラビリティがよい。
  論文  参考訳（メタデータ） (2023-01-26T18:14:12Z)
• Learning Gaussian Mixtures Using the Wasserstein-Fisher-Rao Gradient Flow [12.455057637445174]
  ガウス混合モデルを用いて非パラメトリック最大推定器(NPMLE)を計算するための新しいアルゴリズムを提案する。 この手法は、ワッサーシュタイン-フィッシャー-ラオ幾何学を備えた確率測度空間上の勾配降下に基づく。 提案アルゴリズムの有効性を確認するため,広範囲な数値実験を行った。
  論文  参考訳（メタデータ） (2023-01-04T18:59:35Z)
• Fermion Sampling Made More Efficient [19.50440110966488]
  本稿では,フェミオン数で時間複雑で,システムサイズで線形なフェミオンサンプリングアルゴリズムを提案する。 このアルゴリズムは、最もよく知られたアルゴリズムよりも、時間内で約100%効率が良い。 我々は,多体システムにおけるフェルミオンのサンプリングやテキスト要約の機械学習タスクなど,いくつかのテストアプリケーションでそのパワーを実証する。
  論文  参考訳（メタデータ） (2021-09-15T15:11:33Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  ハイブリッドモンテカルロ(Hybrid Monte Carlo)は、複素連続分布からサンプリングする強力なマルコフ連鎖モンテカルロ法である。 本稿では,SurVAEフローを用いたモンテカルロ法の拡張に基づく新しい手法を提案する。 本稿では,統計学,計算物理学,機械学習など,様々な分野におけるアルゴリズムの有効性を実証し,代替アルゴリズムと比較した改良点を考察する。
  論文  参考訳（メタデータ） (2021-02-04T02:21:08Z)

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

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