論文の概要: Statistical-Computational Trade-offs for Density Estimation

• arxiv url: http://arxiv.org/abs/2410.23087v1
• Date: Wed, 30 Oct 2024 15:03:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-31 14:24:08.752193
• Title: Statistical-Computational Trade-offs for Density Estimation
• Title（参考訳）: 密度推定のための統計計算トレードオフ
• Authors: Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal, Haike Xu,
• Abstract要約: 幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。 これは密度推定のための新しい統計計算トレードオフである。
• 参考スコア（独自算出の注目度）: 60.81548752871115
• License:
• Abstract: We study the density estimation problem defined as follows: given $k$ distributions $p_1, \ldots, p_k$ over a discrete domain $[n]$, as well as a collection of samples chosen from a ``query'' distribution $q$ over $[n]$, output $p_i$ that is ``close'' to $q$. Recently~\cite{aamand2023data} gave the first and only known result that achieves sublinear bounds in {\em both} the sampling complexity and the query time while preserving polynomial data structure space. However, their improvement over linear samples and time is only by subpolynomial factors. Our main result is a lower bound showing that, for a broad class of data structures, their bounds cannot be significantly improved. In particular, if an algorithm uses $O(n/\log^c k)$ samples for some constant $c>0$ and polynomial space, then the query time of the data structure must be at least $k^{1-O(1)/\log \log k}$, i.e., close to linear in the number of distributions $k$. This is a novel \emph{statistical-computational} trade-off for density estimation, demonstrating that any data structure must use close to a linear number of samples or take close to linear query time. The lower bound holds even in the realizable case where $q=p_i$ for some $i$, and when the distributions are flat (specifically, all distributions are uniform over half of the domain $[n]$). We also give a simple data structure for our lower bound instance with asymptotically matching upper bounds. Experiments show that the data structure is quite efficient in practice.
• Abstract（参考訳）: 与えられた$k$ 分布 $p_1, \ldots, p_k$ は離散領域 $[n]$ 上、および ``query'' 分布 $q$ over $[n]$, output $p_i$ は ``close'' から $q$ に選択されたサンプルの集合である。 最近~\cite{aamand2023data} は、多項式データ構造空間を保ちながらサンプリング複雑性とクエリ時間の両方のサブ線形境界を達成する最初の、唯一の既知の結果を与えた。 しかし, 線形試料および時間に対する改良は, 副次的因子によってのみ行われる。 我々の主な結果は、幅広いデータ構造に対して、その境界が著しく改善されないことを示す低い境界である。 特に、ある定数$c>0$と多項式空間に対して$O(n/\log^c k)$サンプルを使用する場合、データ構造のクエリ時間は少なくとも$k^{1-O(1)/\log \log k}$でなければならない。 これは密度推定のための新しい 'emph{statistical-computational} トレードオフであり、任意のデータ構造が線形なサンプル数に近づいたり、線形なクエリ時間に近づいたりしなければならないことを証明している。 下限は、$q=p_i$ for some $i$, and the distributions are flat (具体的には、すべての分布は領域の半分以上である)の場合にも成り立つ。 また、漸近的に一致した上界を持つ下界のインスタンスに対して、単純なデータ構造を与える。 実験により、データ構造は実際に非常に効率的であることが示されている。

関連論文リスト

• Data Structures for Density Estimation [66.36971978162461]
  p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。 また、Acharyaなどのアルゴリズムの改良版も提供します。
  論文  参考訳（メタデータ） (2023-06-20T06:13:56Z)
• 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)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Faster DBSCAN via subsampled similarity queries [42.93847281082316]
  DBSCANは密度に基づくクラスタリングアルゴリズムとして人気がある。 本稿では,サブサンプルである$epsilon$-neighborhoodグラフに基づいてクラスタをクラスタ化するSNG-DBSCANを提案する。
  論文  参考訳（メタデータ） (2020-06-11T18:57:54Z)

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

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