論文の概要: PolytopeWalk: Sparse MCMC Sampling over Polytopes
- arxiv url: http://arxiv.org/abs/2412.06629v1
- Date: Mon, 09 Dec 2024 16:20:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-10 14:56:48.133675
- Title: PolytopeWalk: Sparse MCMC Sampling over Polytopes
- Title（参考訳）: PolytopeWalk: ポリトープ上のスパースMCMCサンプリング
- Authors: Benny Sun, Yuansi Chen,
- Abstract要約: これは、ポリトープを均一にサンプリングするために設計された新しいスケーラブルなPythonライブラリである。
このライブラリは、顔認識などの前処理アルゴリズムを含むエンドツーエンドソリューションを提供する。
我々は,Netlibおよび構造化ポリトープのサンプリング効率と点定コストの改善を実証した。
- 参考スコア（独自算出の注目度）: 3.399289369740637
- License:
- Abstract: High dimensional sampling is an important computational tool in statistics and other computational disciplines, with applications ranging from Bayesian statistical uncertainty quantification, metabolic modeling in systems biology to volume computation. We present $\textsf{PolytopeWalk}$, a new scalable Python library designed for uniform sampling over polytopes. The library provides an end-to-end solution, which includes preprocessing algorithms such as facial reduction and initialization methods. Six state-of-the-art MCMC algorithms on polytopes are implemented, including the Dikin, Vaidya, and John Walk. Additionally, we introduce novel sparse constrained formulations of these algorithms, enabling efficient sampling from sparse polytopes of the form $K_2 = \{x \in \mathbb{R}^d \ | \ Ax = b, x \succeq_k 0\}$. This implementation maintains sparsity in $A$, ensuring scalability to high dimensional settings $(d > 10^5)$. We demonstrate the improved sampling efficiency and per-iteration cost on both Netlib datasets and structured polytopes. $\textsf{PolytopeWalk}$ is available at github.com/ethz-randomwalk/polytopewalk with documentation at polytopewalk.readthedocs.io .
- Abstract（参考訳）: 高次元サンプリングは統計学やその他の計算分野において重要な計算ツールであり、ベイズ統計の不確実性定量化、システム生物学におけるメタボリックモデリングから体積計算まで幅広い応用がある。
これは、ポリトープ上の一様サンプリング用に設計された新しいスケーラブルなPythonライブラリである。
このライブラリは、顔の縮小や初期化メソッドなどの前処理アルゴリズムを含むエンドツーエンドソリューションを提供する。
ポリトープ上での最先端MCMCアルゴリズムは、Dikin、Vaidya、John Walkの6つ実装されている。
さらに、これらのアルゴリズムの新しいスパース制約式を導入し、$K_2 = \{x \in \mathbb{R}^d \ | \ Ax = b, x \succeq_k 0\}$ という形でスパースポリトープから効率的なサンプリングを可能にする。
この実装は、$A$の間隔を維持し、高次元設定へのスケーラビリティを$(d > 10^5)$に保証します。
我々は,Netlibデータセットと構造化ポリトープの両方において,サンプリング効率の改善とイテレーションあたりのコストを実証した。
$\textsf{PolytopeWalk}$はgithub.com/ethz-randomwalk/polytopewalkで利用可能で、polytopewalk.readthedocs.ioでドキュメントが公開されている。
関連論文リスト
- Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams [0.0]
本稿では,主成分分析 (PCA) のための新しいアルゴリズムについて紹介する。
外れ値が存在する場合でも、PCAの最適部分空間にナビゲートする。
このアプローチは、$nd+mathcalO(1)textpoly(n,d)$の時間複雑性を持つ最適解を得る。
論文 参考訳（メタデータ） (2024-08-13T13:05:36Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。
我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
論文 参考訳（メタデータ） (2024-02-21T19:55:01Z) - Modified Step Size for Enhanced Stochastic Gradient Descent: Convergence
and Experiments [0.0]
本稿では,$frac1sqrtttをベースとした変形ステップサイズを改良することにより,勾配降下法(SGD)アルゴリズムの性能向上に新たなアプローチを提案する。
提案されたステップサイズは対数的なステップ項を統合し、最終イテレーションでより小さな値を選択する。
提案手法の有効性について,FashionMNISTとARARを用いて画像分類タスクの数値実験を行った。
論文 参考訳（メタデータ） (2023-09-03T19:21:59Z) - Sparse Gaussian Graphical Models with Discrete Optimization:
Computational and Statistical Perspectives [8.403841349300103]
本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。
擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。
実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
論文 参考訳（メタデータ） (2023-07-18T15:49:02Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov
Decision Processes [61.11090361892306]
Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。
この分離は線形MDPの設定には存在しないことを示す。
我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-01-26T22:09:59Z) - Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs
with a Generative Model [3.749193647980305]
本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。
モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
論文 参考訳（メタデータ） (2021-05-28T17:49:39Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳（メタデータ） (2020-02-20T10:50:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。