論文の概要: Testing Product Distributions: A Closer Look

• arxiv url: http://arxiv.org/abs/2012.14632v1
• Date: Tue, 29 Dec 2020 07:02:32 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-18 20:27:12.596301
• Title: Testing Product Distributions: A Closer Look
• Title（参考訳）: 製品配布をテストする - 詳しく見て
• Authors: Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, N. V. Vinodchandran
• Abstract要約: 私たちは、$n$次元製品分布のアイデンティティと近接性テストの問題を研究します。 私たちの研究は、耐性試験のサンプルの複雑さが製品分布の距離測定とどのように異なるか、きめ細かい理解を与えます。
• 参考スコア（独自算出の注目度）: 14.104329627455893
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problems of identity and closeness testing of $n$-dimensional product distributions. Prior works by Canonne, Diakonikolas, Kane and Stewart (COLT 2017) and Daskalakis and Pan (COLT 2017) have established tight sample complexity bounds for non-tolerant testing over a binary alphabet: given two product distributions $P$ and $Q$ over a binary alphabet, distinguish between the cases $P = Q$ and $d_{\mathrm{TV}}(P, Q) > \epsilon$. We build on this prior work to give a more comprehensive map of the complexity of testing of product distributions by investigating tolerant testing with respect to several natural distance measures and over an arbitrary alphabet. Our study gives a fine-grained understanding of how the sample complexity of tolerant testing varies with the distance measures for product distributions. In addition, we also extend one of our upper bounds on product distributions to bounded-degree Bayes nets.
• Abstract（参考訳）: 我々は,n$-dimensional 製品分布の同一性と密接性テストの問題点について検討する。 Canonne, Diakonikolas, Kane and Stewart (COLT 2017) と Daskalakis and Pan (COLT 2017) による以前の研究は、バイナリアルファベット上での非耐性テストのための厳密なサンプル複雑性境界を確立した: バイナリアルファベット上での2つの積分布$P$と$Q$が与えられた場合、$P = Q$と$d_{\mathrm{TV}}(P, Q) > \epsilon$。 この先行研究に基づいて、いくつかの自然距離測度および任意のアルファベット上での耐久試験を調査することにより、製品分布のテストの複雑さのより包括的なマップを提供する。 本研究は, 耐久試験における試料の複雑さが, 製品分布の距離測定値とどのように異なるか, 詳細に把握する。 さらに、製品分布の上限の1つを境界度ベイズネットに拡張します。

関連論文リスト

• Tester-Learners for Halfspaces: Universal Algorithms [13.13131953359806]
  広範に構造化された分布に対して普遍的に成功するハーフ空間に対して、最初のテスタ・ラーナーを与える。 学習者はラベル付きディストリビューションでエラー$mathrmopt + epsilon$を達成します。
  論文  参考訳（メタデータ） (2023-05-19T15:52:06Z)
• 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)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling [5.3098033683382155]
  本研究では,高次元分布におけるアイデンティティテスト問題について検討する。 私たちは、$mathsfCoordinate Oracle$という、非常に弱い条件付きサンプリングオラクルを考えています。 エントロピーの近似テンソル化(英語版)として知られる解析的性質が$n$-次元可視分布$mu$に対して成り立つならば、$tildeO(n/varepsilon)$クエリを使用して、隠れ分布$pi$に対して効率的なアイデンティティテストアルゴリズムが存在することを証明している。
  論文  参考訳（メタデータ） (2022-07-19T06:49:24Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)
• Testing Determinantal Point Processes [0.0]
  配電体の特性試験という新たな視点からDPPについて検討する。 DPPをテストするための最初のアルゴリズムを提案する。 より一般的な対数-部分モジュラ分布のクラスをテストする問題に対して、新しい硬度結果を示す。
  論文  参考訳（メタデータ） (2020-08-09T04:45:16Z)
• Downsampling for Testing and Learning in Product Distributions [24.48103093661132]
  未知確率分布が $mathbbRd$ 上の積分布であるような分布自由なプロパティテストと学習問題について検討する。 ハーフスペースの交叉、しきい値関数、凸集合、および$k$交互関数などの多くの重要な関数のクラスでは、既知のアルゴリズムは、分布のサポートサイズに依存する複雑さを持つ。 本稿では,これらの問題を解消する一般手法として,ダウンログ(downlog)を提案する。
  論文  参考訳（メタデータ） (2020-07-15T02:46:44Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。