Fugu-MT 論文翻訳(概要): Testing Determinantal Point Processes

論文の概要: Testing Determinantal Point Processes

arxiv url: http://arxiv.org/abs/2008.03650v1
Date: Sun, 9 Aug 2020 04:45:16 GMT
ステータス: 処理完了
システム内更新日: 2022-11-01 04:06:59.761497
Title: Testing Determinantal Point Processes
Title（参考訳）: 決定点プロセスのテスト
Authors: Khashayar Gatmiry (1), Maryam Aliakbarpour (1), Stefanie Jegelka (1) ((1) Massachusetts Institute of Technology)
Abstract要約: 配電体の特性試験という新たな視点からDPPについて検討する。 DPPをテストするための最初のアルゴリズムを提案する。より一般的な対数-部分モジュラ分布のクラスをテストする問題に対して、新しい硬度結果を示す。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Determinantal point processes (DPPs) are popular probabilistic models of diversity. In this paper, we investigate DPPs from a new perspective: property testing of distributions. Given sample access to an unknown distribution $q$ over the subsets of a ground set, we aim to distinguish whether $q$ is a DPP distribution, or $\epsilon$-far from all DPP distributions in $\ell_1$-distance. In this work, we propose the first algorithm for testing DPPs. Furthermore, we establish a matching lower bound on the sample complexity of DPP testing. This lower bound also extends to showing a new hardness result for the problem of testing the more general class of log-submodular distributions.
Abstract（参考訳）: 決定点過程(DPP)は多様性の確率論的モデルとして人気がある。本稿では,分布特性テストという新たな視点から,dppsについて検討する。基底集合の部分集合上の未知分布へのサンプルアクセス$q$を仮定すると、$q$が DPP 分布であるか、$\epsilon$-far が $\ell_1$-distance のすべての DPP 分布と区別することを目指している。本研究では, DPP テストのための最初のアルゴリズムを提案する。さらに, DPP テストのサンプルの複雑さに一致した低い境界を確立する。この下限はまた、より一般的なlog-submodular分布のクラスをテストする問題に対する新たなハードネス結果の提示にも拡張される。

関連論文リスト

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)
Differentially-Private Bayes Consistency [70.92545332158217]
差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
論文参考訳（メタデータ） (2022-12-08T11:57:30Z)
A Faster Sampler for Discrete Determinantal Point Processes [10.355938901584567]
Discrete Determinantal Point Processs (DPP) は、データセットのサブサンプル化に幅広い可能性を持つ。最悪の場合、サンプリングコストは$O(n3)$で、nは基底集合の要素の数である。この禁止コストに対する一般的な回避策は、低ランクカーネルによって定義されたDPPをサンプリングすることである。
論文参考訳（メタデータ） (2022-10-31T14:37:54Z)
Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes [45.40646054226403]
決定点プロセス(DPP)は、$n$アイテムの全てのサブセットに確率を割り当てる。最近の研究は、NDPPに対する近似連鎖モンテカルロサンプリングアルゴリズムを、サイズ-k$サブセットに限定して研究している。低ランクカーネルを持つ$k$-NDPPに対するスケーラブルなMCMCサンプリングアルゴリズムを開発した。
論文参考訳（メタデータ） (2022-07-01T15:22:12Z)
Scalable Sampling for Nonsymmetric Determinantal Point Processes [47.18450267217498]
M$アイテムの集合上の決定点過程(DPP)は、対称的なカーネル行列によってパラメータ化されるモデルである。最近の研究は、非対称DPP(NDPPs)を生じるカーネル対称性の制約を取り除くことで、機械学習アプリケーションにおいて大幅な性能向上が期待できることを示している。コールスキー分解に基づくDPPサンプリングアルゴリズムは1つしか知られておらず、NDPPにも直接適用できる。 NDPPカーネルに特定の構造的制約を課すことで、カーネルのランクに依存する方法で拒絶率を制限できることが示される。
論文参考訳（メタデータ） (2022-01-20T19:21:59Z)
Robust Learning of Optimal Auctions [84.13356290199603]
本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-07-13T17:37:21Z)
Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文参考訳（メタデータ） (2020-09-14T16:09:17Z)
Learning from DPPs via Sampling: Beyond HKPV and symmetry [2.0305676256390934]
行列点過程(DPP)の線形統計量の分布関数を近似する方法を示す。我々のアプローチはスケーラブルであり、従来の対称カーネルを超えて非常に一般的なDPPに適用できる。
論文参考訳（メタデータ） (2020-07-08T17:33:45Z)
Sampling from a $k$-DPP without looking at all items [58.30573872035083]
カーネル関数とサブセットサイズ$k$が与えられた場合、我々のゴールは、サブセットによって誘導されるカーネル行列の行列式に比例する確率を持つ$n$アイテムから$k$をサンプリングすることである(つまり$k$-DPP)。既存の$k$-DPPサンプリングアルゴリズムは、すべての$n$アイテムを複数回パスする高価な前処理ステップを必要とするため、大規模なデータセットでは利用できない。そこで我々は, 十分大きなデータの均一なサンプルを適応的に構築し, より小さな$k$のアイテムを効率よく生成するアルゴリズムを開発した。
論文参考訳（メタデータ） (2020-06-30T16:40:44Z)

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