論文の概要: TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm

• arxiv url: http://arxiv.org/abs/2202.07172v1
• Date: Tue, 15 Feb 2022 03:49:28 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-17 06:29:04.889636
• Title: TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm
• Title（参考訳）: turf: 2要素法、普遍性、ロバスト性、高速分布学習アルゴリズム
• Authors: Yi Hao, Ayush Jain, Alon Orlitsky, Vaishakh Ravindrakumar
• Abstract要約: 最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
• 参考スコア（独自算出の注目度）: 64.13217062232874
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approximating distributions from their samples is a canonical statistical-learning problem. One of its most powerful and successful modalities approximates every distribution to an $\ell_1$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d$ polynomial, where $t\ge1$ and $d\ge0$. Letting $c_{t,d}$ denote the smallest such factor, clearly $c_{1,0}=1$, and it can be shown that $c_{t,d}\ge 2$ for all other $t$ and $d$. Yet current computationally efficient algorithms show only $c_{t,1}\le 2.25$ and the bound rises quickly to $c_{t,d}\le 3$ for $d\ge 9$. We derive a near-linear-time and essentially sample-optimal estimator that establishes $c_{t,d}=2$ for all $(t,d)\ne(1,0)$. Additionally, for many practical distributions, the lowest approximation distance is achieved by polynomials with vastly varying number of pieces. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation. Experiments combining the two techniques confirm improved performance over existing methodologies.
• Abstract（参考訳）: サンプルからの分布の近似は標準統計学習問題である。 その最も強力で成功したモダリティの1つは、すべての分布を、最も近い$t$-ピース次数-$d$多項式よりも本質的にほぼ一定の倍の大きさで、$t\ge1$と$d\ge0$に近似する。 c_{t,d}$ を最小の値とすると、明らかに$c_{1,0}=1$ であり、他のすべての$t$ と $d$ に対して$c_{t,d}\ge 2$ であることが示される。 しかし、現在の計算効率の良いアルゴリズムは$c_{t,1}\le 2.25$しか示さず、バウンドは$c_{t,d}\le 3$ for $d\ge 9$となる。 我々は、すべての$(t,d)\ne(1,0)$に対して$c_{t,d}=2$を確立する、ほぼ線形時間かつ本質的に標本最適推定器を導出する。 さらに、多くの実用分布において、最も低い近似距離は、非常に多くのピースを持つ多項式によって達成される。 本稿では,この数値をほぼ最適に推定する手法を提案する。 2つの手法を組み合わせる実験により、既存の手法よりも性能が向上した。

関連論文リスト

• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。 これは密度推定のための新しい統計計算トレードオフである。
  論文  参考訳（メタデータ） (2024-10-30T15:03:33Z)
• Testing Support Size More Efficiently Than Learning Histograms [0.18416014644193066]
  分布のヒストグラムを$p$で学習するよりも, より効率的にテストを行うことができることを示す。 この証明は、チェビシェフ近似が良い近似であるように設計されている範囲外の分析に依存する。
  論文  参考訳（メタデータ） (2024-10-24T17:05:34Z)
• Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
  誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。 我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
  論文  参考訳（メタデータ） (2024-06-10T17:48:36Z)
• Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
  仮説選択問題に対する最適2ドルの近似学習戦略を導出する。 これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2021-08-17T21:11:20Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• 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)
• Convergence of Sparse Variational Inference in Gaussian Processes Regression [29.636483122130027]
  計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
  論文  参考訳（メタデータ） (2020-08-01T19:23:34Z)
• 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)
• Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning [31.552581550603005]
  構成された高次元分布のいくつかのクラスに対する効率的な距離近似アルゴリズムを設計する。 我々の結果は、これらのよく研究された問題に対する最初の効率的な距離近似アルゴリズムである。
  論文  参考訳（メタデータ） (2020-02-13T07:42:06Z)

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

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