論文の概要: Efficient sampling from the Bingham distribution
- arxiv url: http://arxiv.org/abs/2010.00137v2
- Date: Fri, 8 Dec 2023 19:43:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-13 03:54:24.550213
- Title: Efficient sampling from the Bingham distribution
- Title（参考訳）: ビンガム分布からの効率的なサンプリング
- Authors: Rong Ge, Holden Lee, Jianfeng Lu, Andrej Risteski
- Abstract要約: 我々は、Bingham分布の$p(x)propto exp(xtop A x)$と、$operatornamepoly(d, lambda_max(A)-lambda_min(A))$の期待ランタイムを持つ球面$mathcal Sd-1$の正確なサンプリングアルゴリズムを与える。
直接応用として、ランク1行列推論問題の後方分布を時間内にサンプリングする。
- 参考スコア（独自算出の注目度）: 38.50073658077009
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a algorithm for exact sampling from the Bingham distribution
$p(x)\propto \exp(x^\top A x)$ on the sphere $\mathcal S^{d-1}$ with expected
runtime of $\operatorname{poly}(d, \lambda_{\max}(A)-\lambda_{\min}(A))$. The
algorithm is based on rejection sampling, where the proposal distribution is a
polynomial approximation of the pdf, and can be sampled from by explicitly
evaluating integrals of polynomials over the sphere. Our algorithm gives exact
samples, assuming exact computation of an inverse function of a polynomial.
This is in contrast with Markov Chain Monte Carlo algorithms, which are not
known to enjoy rapid mixing on this problem, and only give approximate samples.
As a direct application, we use this to sample from the posterior
distribution of a rank-1 matrix inference problem in polynomial time.
- Abstract（参考訳）: ビンガム分布から正確にサンプリングするためのアルゴリズムを与える: $p(x)\propto \exp(x^\top a x)$ on the sphere $\mathcal s^{d-1}$ で、$\operatorname{poly}(d, \lambda_{\max}(a)-\lambda_{\min}(a)$ の期待実行時間を持つ。
このアルゴリズムは、提案分布がpdfの多項式近似である拒絶サンプリングに基づいており、球面上の多項式の積分を明示的に評価することでサンプル化することができる。
我々のアルゴリズムは多項式の逆関数の正確な計算を仮定して、正確なサンプルを与える。
これは、マルコフ・チェイン・モンテカルロのアルゴリズムとは対照的であり、この問題を素早く混合することは知られておらず、近似サンプルのみを与える。
直接の応用として, 多項式時間でのrank-1行列推論問題の後方分布から, これをサンプルとして用いる。
関連論文リスト
- Rényi-infinity constrained sampling with $d^3$ membership queries [2.209921757303168]
本稿では,エレガントな収束保証を有する原理的かつ単純なアルゴリズムである制約付き近位サンプリング手法を提案する。
R'enyi-infinity divergence(mathcal R_infty$)に収束することを示す。
論文 参考訳（メタデータ） (2024-07-17T19:20:08Z) - Diffusion Posterior Sampling is Computationally Intractable [9.483130965295324]
後方サンプリングは、塗装、超解像、MRI再構成などのタスクに有用である。
暗号における最も基本的な仮定では、一方通行関数が存在する。
また,指数時間回帰サンプリングは,指数時間で逆転する一方向関数が存在するという強い仮定の下で,本質的に最適であることを示す。
論文 参考訳（メタデータ） (2024-02-20T05:28:13Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。
提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
論文 参考訳（メタデータ） (2022-06-22T17:58:23Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - 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) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Faster Differentially Private Samplers via R\'enyi Divergence Analysis
of Discretized Langevin MCMC [35.050135428062795]
ランゲヴィン力学に基づくアルゴリズムは、統計距離のようなある程度の距離測度の下で、はるかに高速な代替手段を提供する。
我々の手法は単純で汎用的で、アンダーダムドランゲヴィン力学に適用できる。
論文 参考訳（メタデータ） (2020-10-27T22:52:45Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。