論文の概要: Forster Decomposition and Learning Halfspaces with Noise

• arxiv url: http://arxiv.org/abs/2107.05582v1
• Date: Mon, 12 Jul 2021 17:00:59 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-13 16:06:32.290608
• Title: Forster Decomposition and Learning Halfspaces with Noise
• Title（参考訳）: 雑音を伴うフォスター分解と学習ハーフスペース
• Authors: Ilias Diakonikolas and Daniel M. Kane and Christos Tzamos
• Abstract要約: フォースター変換 (Forster transform) は、分布を優れた反集中特性を持つものに変換する演算である。 本稿では,Forster変換が存在し,効率よく計算できる少数の分布の解離混合として,任意の分布を効率的に分解可能であることを示す。
• 参考スコア（独自算出の注目度）: 60.691817861402676
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A Forster transform is an operation that turns a distribution into one with good anti-concentration properties. While a Forster transform does not always exist, we show that any distribution can be efficiently decomposed as a disjoint mixture of few distributions for which a Forster transform exists and can be computed efficiently. As the main application of this result, we obtain the first polynomial-time algorithm for distribution-independent PAC learning of halfspaces in the Massart noise model with strongly polynomial sample complexity, i.e., independent of the bit complexity of the examples. Previous algorithms for this learning problem incurred sample complexity scaling polynomially with the bit complexity, even though such a dependence is not information-theoretically necessary.
• Abstract（参考訳）: フォースター変換 (Forster transform) は、分布を優れた反集中特性を持つものに変換する演算である。 Forster変換は常に存在するわけではないが、Forster変換が存在し、効率的に計算できる少数の分布の解離混合として、任意の分布を効率的に分解できることを示す。 この結果の主応用として, 半空間の分布非依存pac学習における最初の多項式時間アルゴリズムを, 実例のビット複雑性とは無関係に, 強い多項式サンプル複雑性を持つマッサート雑音モデルで求めた。 この学習問題の以前のアルゴリズムは、そのような依存が情報理論上必要ではないにもかかわらず、ビット複雑性と多項式的にスケーリングするサンプル複雑性を引き起こした。

関連論文リスト

• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning [56.86097988183311]
  フォースター変換(フォースターりゅう、英: Forster transform)は、データセットを放射等方性位置に配置し、その性質のいくつかを維持しながら、データセットを正規化する方法である。
  論文  参考訳（メタデータ） (2022-12-06T14:32:02Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Sample-Optimal PAC Learning of Halfspaces with Malicious Noise [4.8728183994912415]
  Valiant(1985)の悪意のあるノイズの存在下で$mathRd$の半空間の効率的なPAC学習を研究します。 Awasthi et alのアルゴリズムのための新しい分析を提示します。 そして、ほぼ最適に近いサンプル複雑性を$tildeo(d)$という値で達成できることを示します。 Bbbshoutyetal (2002) のより一般的で強力なノイズモデルにアルゴリズムと解析を拡張し、ほぼ最適なノイズ耐性とサンプルの複雑さを時間内に達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-02-11T20:18:20Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Learning Structured Distributions From Untrusted Batches: Faster and Simpler [26.57313255285721]
  本稿では,Qiao と Valiant [QV17] が導入した信頼できないバッチから学ぶことの問題点を再考する。 我々は,[JO19] と [CLM19] の技法を合成して両世界の長所を与える,魅力的な方法を見出した。
  論文  参考訳（メタデータ） (2020-02-24T18:32:10Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2020-02-22T01:03:33Z)

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

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