論文の概要: Fast parallel sampling under isoperimetry
- arxiv url: http://arxiv.org/abs/2401.09016v1
- Date: Wed, 17 Jan 2024 07:24:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-18 16:35:18.095716
- Title: Fast parallel sampling under isoperimetry
- Title（参考訳）: イソペリメトリーによる高速並列サンプリング
- Authors: Nima Anari, Sinho Chewi, Thuy-Duong Vuong
- Abstract要約: ログソボレフの不等式を満たすディストリビューション$pi$ over $mathbb Rd$から並列にサンプリングする方法を示す。
提案アルゴリズムは分布$hatpi$からKullback-Leibler分散の$pi$に近いサンプルを出力する。
- 参考スコア（独自算出の注目度）: 10.619901778151336
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show how to sample in parallel from a distribution $\pi$ over $\mathbb
R^d$ that satisfies a log-Sobolev inequality and has a smooth log-density, by
parallelizing the Langevin (resp. underdamped Langevin) algorithms. We show
that our algorithm outputs samples from a distribution $\hat\pi$ that is close
to $\pi$ in Kullback--Leibler (KL) divergence (resp. total variation (TV)
distance), while using only $\log(d)^{O(1)}$ parallel rounds and
$\widetilde{O}(d)$ (resp. $\widetilde O(\sqrt d)$) gradient evaluations in
total. This constitutes the first parallel sampling algorithms with TV distance
guarantees.
For our main application, we show how to combine the TV distance guarantees
of our algorithms with prior works and obtain RNC sampling-to-counting
reductions for families of discrete distribution on the hypercube $\{\pm 1\}^n$
that are closed under exponential tilts and have bounded covariance.
Consequently, we obtain an RNC sampler for directed Eulerian tours and
asymmetric determinantal point processes, resolving open questions raised in
prior works.
- Abstract（参考訳）: 対数ソボレフの不等式を満たす分布 $\pi$ over $\mathbb R^d$ から並列にサンプリングする方法を示し、Langevin (resp. underdamed Langevin) アルゴリズムを並列化することにより、スムーズな対数密度を持つ。
提案アルゴリズムは,Kullback--Leibler (KL) の分散(resp) における$\pi$に近い分布からサンプルを出力する。
total variation (TV) distance, while using only $\log(d)^{O(1)}$ parallel rounds and $\widetilde{O}(d)$ (resp).
$\widetilde O(\sqrt d)$) Gragient Evaluations in total。
これはテレビ距離保証を備えた最初の並列サンプリングアルゴリズムを構成する。
本論文では,本アルゴリズムのテレビジョン距離保証を先行研究と組み合わせる方法を示し,指数的傾きの下で閉ざされ有界共分散を持つ超立方体$\{\pm 1\}^n$ 上の離散分布系に対するrncサンプリング・ツー・カウンティング低減法を提案する。
そこで,本研究では,有向オイラー旅行と非対称行列点過程に対して,先行研究で提起された問題を解くためのrncサンプラーを得る。
関連論文リスト
- Rényi-infinity constrained sampling with $d^3$ membership queries [2.209921757303168]
本稿では,エレガントな収束保証を有する原理的かつ単純なアルゴリズムである制約付き近位サンプリング手法を提案する。
R'enyi-infinity divergence(mathcal R_infty$)に収束することを示す。
論文 参考訳（メタデータ） (2024-07-17T19:20:08Z) - Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel [10.840582511203024]
我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでのみ実行できるように並列化可能であることを示す。
また、我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでしか実行できないことを示す。
論文 参考訳（メタデータ） (2024-06-03T01:34:34Z) - Perfect Sampling from Pairwise Comparisons [26.396901523831534]
分散分布$mathcalD$の与えられたアクセスから最適なサンプルを効率よく取得する方法を,サポート対象の要素のペア比較に限定して検討する。
固定分布が$mathcalD$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-11-23T11:20:30Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Optimal Sublinear Sampling of Spanning Trees and Determinantal Point
Processes via Average-Case Entropic Independence [3.9586758145580014]
強いレイリー分布から繰り返しサンプリングする高速アルゴリズムを設計する。
グラフ $G=(V, E)$ に対して、$G$ in $widetildeO(lvert Vrvert)$ time per sample から一様にランダムに散らばる木を概算する方法を示す。
$n$要素の基底集合の$k$のサブセット上の決定的点プロセスに対して、$widetildeO(komega)$ time の最初の $widetildeO(nk) の後に、$widetildeO(komega)$ time のサンプルを概算する方法を示す。
論文 参考訳（メタデータ） (2022-04-06T04:11:26Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Complexity of zigzag sampling algorithm for strongly log-concave
distributions [6.336005544376984]
強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。
ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
論文 参考訳（メタデータ） (2020-12-21T03:10:21Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - 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) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。