論文の概要: Learning-based Support Estimation in Sublinear Time
- arxiv url: http://arxiv.org/abs/2106.08396v1
- Date: Tue, 15 Jun 2021 19:53:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-17 17:08:38.970807
- Title: Learning-based Support Estimation in Sublinear Time
- Title（参考訳）: サブ線形時間における学習に基づく支援推定
- Authors: Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep
Silwal, Tal Wagner
- Abstract要約: 本研究では,その要素のランダムなサンプルから,大規模データセット内の異なる要素数を推定する問題を考察する。
過去10年間にわたる一連の研究の結果、サンプルから最大$ pm varepsilon n$までのサポートを推定するアルゴリズムが作られた。
本稿では、任意の要素が与えられた場合、その周波数を推定する機械学習ベースの予測器を付加した推定アルゴリズムを検討する。
- 参考スコア（独自算出の注目度）: 21.920795956349327
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of estimating the number of distinct elements in a
large data set (or, equivalently, the support size of the distribution induced
by the data set) from a random sample of its elements. The problem occurs in
many applications, including biology, genomics, computer systems and
linguistics. A line of research spanning the last decade resulted in algorithms
that estimate the support up to $ \pm \varepsilon n$ from a sample of size
$O(\log^2(1/\varepsilon) \cdot n/\log n)$, where $n$ is the data set size.
Unfortunately, this bound is known to be tight, limiting further improvements
to the complexity of this problem. In this paper we consider estimation
algorithms augmented with a machine-learning-based predictor that, given any
element, returns an estimation of its frequency. We show that if the predictor
is correct up to a constant approximation factor, then the sample complexity
can be reduced significantly, to \[ \ \log (1/\varepsilon) \cdot
n^{1-\Theta(1/\log(1/\varepsilon))}. \] We evaluate the proposed algorithms on
a collection of data sets, using the neural-network based estimators from {Hsu
et al, ICLR'19} as predictors. Our experiments demonstrate substantial (up to
3x) improvements in the estimation accuracy compared to the state of the art
algorithm.
- Abstract（参考訳）: 本研究では,その要素のランダムなサンプルから,大きなデータセット内の個別の要素数(あるいは,データセットによって引き起こされる分布の支持サイズ)を推定する問題を考える。
この問題は生物学、ゲノム学、コンピュータシステム、言語学など多くの応用で発生する。
過去10年間にわたる一連の研究の結果、最大で$_pm \varepsilon n$ のサポートを、データセットサイズが$n$である$o(\log^2(1/\varepsilon) \cdot n/\log n)$ のサンプルから見積もるアルゴリズムが得られた。
残念ながら、この境界は厳密であることが知られており、この問題の複雑さをさらに改善している。
本稿では、任意の要素が与えられた場合、その周波数を推定する機械学習ベースの予測器を付加した推定アルゴリズムを検討する。
予測因子が定数近似係数まで正しければ、サンプルの複雑性は \[ \log (1/\varepsilon) \cdot n^{1-\Theta(1/\log(1/\varepsilon))} に著しく減少する。
目的〕提案アルゴリズムをデータセットの集合上で評価し,Hsu et al, ICLR'19} のニューラルネットワークに基づく推定器を予測器として利用した。
本実験は,artアルゴリズムの状態を比較検討した結果,推定精度が最大3倍向上したことを示す。
関連論文リスト
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。
それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。
技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
論文 参考訳（メタデータ） (2024-03-15T15:51:27Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Data Structures for Density Estimation [66.36971978162461]
p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。
また、Acharyaなどのアルゴリズムの改良版も提供します。
論文 参考訳（メタデータ） (2023-06-20T06:13:56Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Efficient One Sided Kolmogorov Approximation [7.657378889055477]
本研究の主な応用は, 時系列並列スケジュールにおいて, 欠落する確率を推定することである。
これらの確率の正確な計算はNPハードであるため,本論文で記述したアルゴリズムを用いて近似を求める。
論文 参考訳（メタデータ） (2022-07-14T10:03:02Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected
Error [0.3997680012976965]
目標は、最悪の予測エラーを最小限に抑える推定器を設計することである。
Chen, Valiant および Valiant は、データ値が $ell_infty$-normalized の場合、平均の推定値を計算する時間アルゴリズムが存在することを示した。
本稿では,オンライン凸最適化に基づく最適半線形推定器の近似アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-12-27T18:47:25Z) - Stochastic Approximation for Online Tensorial Independent Component
Analysis [98.34292831923335]
独立成分分析(ICA)は統計機械学習や信号処理において一般的な次元削減ツールである。
本稿では,各独立成分を推定する副産物オンライン時系列アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-28T18:52:37Z) - A Stochastic Path-Integrated Differential EstimatoR Expectation
Maximization Algorithm [19.216497414060658]
予測最大化(EM)アルゴリズムは、回帰器と専門家の混在を含む潜在変数モデルにおける推論において重要な要素である。
本稿では,条件予測推定器からの推測のための新しいEMであるtextttSPを提案する。
論文 参考訳（メタデータ） (2020-11-30T15:49:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。