論文の概要: Sample-Optimal PAC Learning of Halfspaces with Malicious Noise

• arxiv url: http://arxiv.org/abs/2102.06247v1
• Date: Thu, 11 Feb 2021 20:18:20 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-15 21:47:23.201508
• Title: Sample-Optimal PAC Learning of Halfspaces with Malicious Noise
• Title（参考訳）: 悪騒音を有する半空間のサンプル最適PAC学習
• Authors: Jie Shen
• Abstract要約: Valiant(1985)の悪意のあるノイズの存在下で$mathRd$の半空間の効率的なPAC学習を研究します。 Awasthi et alのアルゴリズムのための新しい分析を提示します。 そして、ほぼ最適に近いサンプル複雑性を$tildeo(d)$という値で達成できることを示します。 Bbbshoutyetal (2002) のより一般的で強力なノイズモデルにアルゴリズムと解析を拡張し、ほぼ最適なノイズ耐性とサンプルの複雑さを時間内に達成可能であることを示す。
• 参考スコア（独自算出の注目度）: 4.8728183994912415
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study efficient PAC learning of homogeneous halfspaces in $\mathbb{R}^d$ in the presence of malicious noise of Valiant~(1985). This is a challenging noise model and only until recently has near-optimal noise tolerance bound been established under the mild condition that the unlabeled data distribution is isotropic log-concave. However, it remains unsettled how to obtain the optimal sample complexity simultaneously. In this work, we present a new analysis for the algorithm of Awasthi et al.~(2017) and show that it essentially achieves the near-optimal sample complexity bound of $\tilde{O}(d)$, improving the best known result of $\tilde{O}(d^2)$. Our main ingredient is a novel incorporation of a Matrix Chernoff-type inequality to bound the spectrum of an empirical covariance matrix for well-behaved distributions, in conjunction with a careful exploration of the localization schemes of Awasthi et al.~(2017). We further extend the algorithm and analysis to the more general and stronger nasty noise model of Bshouty~et~al. (2002), showing that it is still possible to achieve near-optimal noise tolerance and sample complexity in polynomial time.
• Abstract（参考訳）: Valiant~(1985)の悪意のあるノイズの存在下で、$\mathbb{R}^d$における均質な半空間の効率的なPAC学習について研究する。 これは困難なノイズモデルであり、最近まで、ラベルのないデータ分布が等方性ログ凹であるという穏やかな条件下で、ほぼ最適のノイズ耐性が確立された。 しかし、最適なサンプルの複雑さを同時に得る方法はまだ未定である。 本稿では, awasthi et al.~(2017) のアルゴリズムの新しい解析を行い,$\tilde{o}(d)$ という最適に近いサンプル複雑性を本質的に達成できることを示し,$\tilde{o}(d^2)$ の最もよく知られた結果を改善する。 我々の主成分は, awasthi et al.~(2017)の局所化スキームを注意深く探究すると共に, 経験的共分散行列のスペクトルに束縛する行列チャーノフ型不等式を新規に組み込んだものである。 さらにアルゴリズムと解析をBshouty~et~alのより汎用的で強力なノイズモデルに拡張する。 (2002年)、多項式時間でほぼ最適のノイズ公差とサンプル複雑性を達成できることを示した。

関連論文リスト

• Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
  非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。 対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。 我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
  論文  参考訳（メタデータ） (2024-05-27T00:53:18Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• Improved dimension dependence of a proximal algorithm for sampling [16.147290924171692]
  そこで本研究では,すべての古典的設定において,より優れた複雑性境界を実現するサンプリングアルゴリズムを提案する。 提案アルゴリズムは,2021年に導入した近位サンプルを用いた。 強い対数対数分布の場合、この手法は温度開始を伴わずに$tildemathcalO(kappa d1/2)$の複雑さを持つ。 LSI を満たす分布に対して、我々は $tilde MathcalO(hat kappa d1/2)$ ここで $hat kappa$ は滑らかさと滑らかさの比である。
  論文  参考訳（メタデータ） (2023-02-20T16:44:48Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD [73.55632827932101]
  SGLDにおけるノイズ構造を操作することにより,情報理論の一般化を最適化する。 低経験的リスクを保証するために制約を課すことで、最適なノイズ共分散が期待される勾配共分散の平方根であることを証明する。
  論文  参考訳（メタデータ） (2021-10-26T15:02:27Z)
• Forster Decomposition and Learning Halfspaces with Noise [60.691817861402676]
  フォースター変換 (Forster transform) は、分布を優れた反集中特性を持つものに変換する演算である。 本稿では,Forster変換が存在し,効率よく計算できる少数の分布の解離混合として,任意の分布を効率的に分解可能であることを示す。
  論文  参考訳（メタデータ） (2021-07-12T17:00:59Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance [21.76197397540397]
  本稿では,雑音下でのmathbbRd$における等質スパース半空間の計算的学習について述べる。 サンプルの複雑さは$tildeObig(frac 1 epsilon s2 log5 d big)$であり、属性効率も楽しめます。
  論文  参考訳（メタデータ） (2020-06-06T04:57:39Z)

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

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