論文の概要: SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm

• arxiv url: http://arxiv.org/abs/2002.09589v2
• Date: Thu, 11 Feb 2021 19:10:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-29 19:18:32.026247
• Title: SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm
• Title（参考訳）: SURF: シンプルで普遍的でロバストで高速な分布学習アルゴリズム
• Authors: Yi Hao, Ayush Jain, Alon Orlitsky, Vaishakh Ravindrakumar
• Abstract要約: SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
• 参考スコア（独自算出の注目度）: 64.13217062232874
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sample- and computationally-efficient distribution estimation is a fundamental tenet in statistics and machine learning. We present SURF, an algorithm for approximating distributions by piecewise polynomials. SURF is: simple, replacing prior complex optimization techniques by straight-forward {empirical probability} approximation of each potential polynomial piece {through simple empirical-probability interpolation}, and using plain divide-and-conquer to merge the pieces; universal, as well-known polynomial-approximation results imply that it accurately approximates a large class of common distributions; robust to distribution mis-specification as for any degree $d \le 8$, it estimates any distribution to an $\ell_1$ distance $< 3$ times that of the nearest degree-$d$ piecewise polynomial, improving known factor upper bounds of 3 for single polynomials and 15 for polynomials with arbitrarily many pieces; fast, using optimal sample complexity, running in near sample-linear time, and if given sorted samples it may be parallelized to run in sub-linear time. In experiments, SURF outperforms state-of-the art algorithms.
• Abstract（参考訳）: サンプルおよび計算効率の分布推定は統計学と機械学習の基本的な要素である。 分割多項式による分布の近似アルゴリズム SURF を提案する。 SURF is: simple, replacing prior complex optimization techniques by straight-forward {empirical probability} approximation of each potential polynomial piece {through simple empirical-probability interpolation}, and using plain divide-and-conquer to merge the pieces; universal, as well-known polynomial-approximation results imply that it accurately approximates a large class of common distributions; robust to distribution mis-specification as for any degree $d \le 8$, it estimates any distribution to an $\ell_1$ distance $< 3$ times that of the nearest degree-$d$ piecewise polynomial, improving known factor upper bounds of 3 for single polynomials and 15 for polynomials with arbitrarily many pieces; fast, using optimal sample complexity, running in near sample-linear time, and if given sorted samples it may be parallelized to run in sub-linear time. 実験では、SURFは最先端のアルゴリズムより優れている。

関連論文リスト

• Learning Submodular Sequencing from Samples [11.528995186765751]
  本稿では,いくつかの複合部分モジュラー関数を最適化するために,シーケンス内の項目の選択とランク付けの問題に対処する。 本稿では,各部分モジュラ関数の曲率に依存する近似比を求めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-09T01:33:13Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints [8.261182037130407]
  局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。 我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
  論文  参考訳（メタデータ） (2023-01-09T18:36:49Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Optimal Randomized Approximations for Matrix based Renyi's Entropy [16.651155375441796]
  整数次数$alpha$の場合のランダム近似と非整数$alpha$の場合の直列近似を開発する。 大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証する。
  論文  参考訳（メタデータ） (2022-05-16T02:24:52Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Forster Decomposition and Learning Halfspaces with Noise [60.691817861402676]
  フォースター変換 (Forster transform) は、分布を優れた反集中特性を持つものに変換する演算である。 本稿では,Forster変換が存在し,効率よく計算できる少数の分布の解離混合として,任意の分布を効率的に分解可能であることを示す。
  論文  参考訳（メタデータ） (2021-07-12T17:00:59Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)

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

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