論文の概要: Testing Support Size More Efficiently Than Learning Histograms

• arxiv url: http://arxiv.org/abs/2410.18915v1
• Date: Thu, 24 Oct 2024 17:05:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-25 12:48:54.423929
• Title: Testing Support Size More Efficiently Than Learning Histograms
• Title（参考訳）: ヒストグラムの学習よりも効率的なテスト支援
• Authors: Renato Ferreira Pinto Jr., Nathaniel Harms,
• Abstract要約: 分布のヒストグラムを$p$で学習するよりも, より効率的にテストを行うことができることを示す。 この証明は、チェビシェフ近似が良い近似であるように設計されている範囲外の分析に依存する。
• 参考スコア（独自算出の注目度）: 0.18416014644193066
• License:
• Abstract: Consider two problems about an unknown probability distribution $p$: 1. How many samples from $p$ are required to test if $p$ is supported on $n$ elements or not? Specifically, given samples from $p$, determine whether it is supported on at most $n$ elements, or it is "$\epsilon$-far" (in total variation distance) from being supported on $n$ elements. 2. Given $m$ samples from $p$, what is the largest lower bound on its support size that we can produce? The best known upper bound for problem (1) uses a general algorithm for learning the histogram of the distribution $p$, which requires $\Theta(\tfrac{n}{\epsilon^2 \log n})$ samples. We show that testing can be done more efficiently than learning the histogram, using only $O(\tfrac{n}{\epsilon \log n} \log(1/\epsilon))$ samples, nearly matching the best known lower bound of $\Omega(\tfrac{n}{\epsilon \log n})$. This algorithm also provides a better solution to problem (2), producing larger lower bounds on support size than what follows from previous work. The proof relies on an analysis of Chebyshev polynomial approximations outside the range where they are designed to be good approximations, and the paper is intended as an accessible self-contained exposition of the Chebyshev polynomial method.
• Abstract（参考訳）: 未知の確率分布に関する2つの問題を考える。$p$: 1.$p$のサンプルは、$n$要素で$p$がサポートされているかどうかをテストするために何回必要か? 具体的には、$p$のサンプルが与えられた場合、少なくとも$n$要素でサポートされているか、または$n$要素でサポートされているかから"$\epsilon$-far"(全変動距離)である。 2.$p$から$m$のサンプルが与えられたとき、私たちが生成できるサポートサイズで最も低い境界は何ですか? 問題 (1) の最もよく知られた上限は、分布のヒストグラムを学習するための一般的なアルゴリズムを使い、$\Theta(\tfrac{n}{\epsilon^2 \log n})$サンプルを必要とする。 O(\tfrac{n}{\epsilon \log n})$(/\epsilon)$(\tfrac{n}{\epsilon \log n})$(\tfrac{n}{\epsilon \log n})$)$(Omega(\tfrac{n}{\epsilon \log n})$)$(Omega(\tfrac{n}{\epsilon \log n})$)$(Omega(\tfrac{n}{\epsilon \log n})$)$)$(Omega(\tfrac{n}{\epsilon \log n})$)$(Omega)$)$(Omega(\tfrac{n}{\epsilon \log n})$)$(Omega(Omega(Omega(Omega(Omega(Omega(Omega)))$)$)$(Omega(Omega(Omega(Omega(Ome このアルゴリズムはまた、問題 (2) に対するより良い解を提供し、以前の研究よりもサポートサイズに対するより低い境界を生み出す。 この証明は、チェビシェフ多項式近似が良い近似であるように設計された範囲外における解析に依存しており、この論文はチェビシェフ多項式法の自己完結表現として意図されている。

関連論文リスト

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• 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)
• Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity [6.812247730094931]
  任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。 また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
  論文  参考訳（メタデータ） (2023-09-25T09:50:15Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Near-Optimal Bounds for Testing Histogram Distributions [35.18069719489173]
  ヒストグラム検査問題はサンプル複雑性$widetilde Theta (sqrtnk / varepsilon + k / varepsilon2 + sqrtn / varepsilon2)$であることを示す。
  論文  参考訳（メタデータ） (2022-07-14T01:24:01Z)
• List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
  そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。 特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。 Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
  論文  参考訳（メタデータ） (2022-06-10T17:38:18Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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