論文の概要: Perfect Sampling from Pairwise Comparisons
- arxiv url: http://arxiv.org/abs/2211.12868v1
- Date: Wed, 23 Nov 2022 11:20:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-24 16:28:02.457038
- Title: Perfect Sampling from Pairwise Comparisons
- Title（参考訳）: 対比較による完全サンプリング
- Authors: Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos
- Abstract要約: 分散分布$mathcalD$の与えられたアクセスから最適なサンプルを効率よく取得する方法を,サポート対象の要素のペア比較に限定して検討する。
固定分布が$mathcalD$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 26.396901523831534
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we study how to efficiently obtain perfect samples from a
discrete distribution $\mathcal{D}$ given access only to pairwise comparisons
of elements of its support. Specifically, we assume access to samples $(x, S)$,
where $S$ is drawn from a distribution over sets $\mathcal{Q}$ (indicating the
elements being compared), and $x$ is drawn from the conditional distribution
$\mathcal{D}_S$ (indicating the winner of the comparison) and aim to output a
clean sample $y$ distributed according to $\mathcal{D}$. We mainly focus on the
case of pairwise comparisons where all sets $S$ have size 2. We design a Markov
chain whose stationary distribution coincides with $\mathcal{D}$ and give an
algorithm to obtain exact samples using the technique of Coupling from the
Past. However, the sample complexity of this algorithm depends on the structure
of the distribution $\mathcal{D}$ and can be even exponential in the support of
$\mathcal{D}$ in many natural scenarios. Our main contribution is to provide an
efficient exact sampling algorithm whose complexity does not depend on the
structure of $\mathcal{D}$. To this end, we give a parametric Markov chain that
mixes significantly faster given a good approximation to the stationary
distribution. We can obtain such an approximation using an efficient learning
from pairwise comparisons algorithm (Shah et al., JMLR 17, 2016). Our technique
for speeding up sampling from a Markov chain whose stationary distribution is
approximately known is simple, general and possibly of independent interest.
- Abstract（参考訳）: そこで本研究では, 離散分布$\mathcal{D}$ から完全標本を効率よく取得する方法を, サポート対象要素のペア比較に限定して検討する。
具体的には、$(x, s)$ が$\mathcal{q}$ (比較される要素を示す) 上の分布から$s$ が引き出され、$x$ が条件付き分布 $\mathcal{d}_s$ (比較の勝者を示す) から引き出され、$\mathcal{d}$ に従って分散されたクリーンサンプル $y$ が出力される。
主に、すべての集合 S$ がサイズ 2 を持つペアワイズ比較の場合に焦点を当てる。
固定分布が$\mathcal{D}$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。
しかし、このアルゴリズムのサンプルの複雑さは分布 $\mathcal{D}$ の構造に依存し、多くの自然シナリオにおいて$\mathcal{D}$ のサポートにおいて指数関数的である。
我々の主な貢献は、$\mathcal{D}$の構造に依存しない効率的な正確なサンプリングアルゴリズムを提供することである。
この目的のために、静止分布のよい近似を考えるとかなり高速に混合するパラメトリックマルコフ連鎖を与える。
このような近似は対比較アルゴリズム(shah et al., jmlr 17, 2016)から効率的な学習を用いて得られる。
定常分布が大まかに知られているマルコフ鎖からのサンプリングを高速化する手法は単純で、汎用的で、おそらくは独立した関心事である。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。
本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文 参考訳（メタデータ） (2024-08-10T04:26:19Z) - Rényi-infinity constrained sampling with $d^3$ membership queries [2.209921757303168]
本稿では,エレガントな収束保証を有する原理的かつ単純なアルゴリズムである制約付き近位サンプリング手法を提案する。
R'enyi-infinity divergence(mathcal R_infty$)に収束することを示す。
論文 参考訳（メタデータ） (2024-07-17T19:20:08Z) - Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。
この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。
我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
論文 参考訳（メタデータ） (2023-02-21T17:52:23Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - 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) - Estimation of Shortest Path Covariance Matrices [21.772761365915176]
共分散行列 $mathbfSigma in mathbbRdtimes d$ of a distribution $mathcal D$ over $mathbbRd$ given independent sample。
単に$O(sqrtD)$エントリ複雑性と$tilde O(r)を使って、標準エラーまで$mathbfSigma$を推定するための非常に単純なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-11-19T17:37:46Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。