論文の概要: On the Power of Localized Perceptron for Label-Optimal Learning of
Halfspaces with Adversarial Noise
- arxiv url: http://arxiv.org/abs/2012.10793v2
- Date: Wed, 20 Jan 2021 04:34:16 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-01 12:37:33.673884
- Title: On the Power of Localized Perceptron for Label-Optimal Learning of
Halfspaces with Adversarial Noise
- Title（参考訳）: 逆雑音をもつハーフスペースのラベル最適学習のための局所パーセプトロンのパワーについて
- Authors: Jie Shen
- Abstract要約: 対比雑音を伴う$mathbbRd$の同質半空間のオンラインアクティブ学習について研究する。
私たちの主な貢献は、時間内で動作するパーセプトロンライクなアクティブラーニングアルゴリズムです。
アルゴリズムは、ほぼ最適ラベルの複雑さで基礎となるハーフスペースを学習する。
- 参考スコア（独自算出の注目度）: 4.8728183994912415
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study {\em online} active learning of homogeneous halfspaces in
$\mathbb{R}^d$ with adversarial noise where the overall probability of a noisy
label is constrained to be at most $\nu$. Our main contribution is a
Perceptron-like online active learning algorithm that runs in polynomial time,
and under the conditions that the marginal distribution is isotropic
log-concave and $\nu = \Omega(\epsilon)$, where $\epsilon \in (0, 1)$ is the
target error rate, our algorithm PAC learns the underlying halfspace with
near-optimal label complexity of $\tilde{O}\big(d \cdot
polylog(\frac{1}{\epsilon})\big)$ and sample complexity of
$\tilde{O}\big(\frac{d}{\epsilon} \big)$. Prior to this work, existing online
algorithms designed for tolerating the adversarial noise are subject to either
label complexity polynomial in $\frac{1}{\epsilon}$, or suboptimal noise
tolerance, or restrictive marginal distributions. With the additional prior
knowledge that the underlying halfspace is $s$-sparse, we obtain
attribute-efficient label complexity of $\tilde{O}\big( s \cdot polylog(d,
\frac{1}{\epsilon}) \big)$ and sample complexity of
$\tilde{O}\big(\frac{s}{\epsilon} \cdot polylog(d) \big)$. As an immediate
corollary, we show that under the agnostic model where no assumption is made on
the noise rate $\nu$, our active learner achieves an error rate of $O(OPT) +
\epsilon$ with the same running time and label and sample complexity, where
$OPT$ is the best possible error rate achievable by any homogeneous halfspace.
- Abstract（参考訳）: 我々は、雑音ラベルの全体確率が最大$\nu$となるような逆ノイズを持つ$\mathbb{R}^d$における同次半空間のアクティブな学習について研究する。
私たちの主な貢献は、多項式時間で実行されるパーセプトロンのようなオンライン能動学習アルゴリズムであり、その限界分布が等方的対数凹であり、$\nu = \Omega(\epsilon)$, where $\epsilon \in (0, 1)$, our algorithm PAC learns the underlying halfspace of $\tilde{O}\big(d \cdot polylog(\frac{1}{\epsilon})\big)$ and sample complexity of $\tilde{O}\big(\frac{d}{\epsilon} \big)$である。
この研究に先立ち、対向雑音を許容するように設計された既存のオンラインアルゴリズムは、$\frac{1}{\epsilon}$のラベル複雑性多項式、もしくは準最適雑音耐性、もしくは制限的境界分布のいずれかの条件が課される。
基礎となる半空間が$s$-sparseであるという事前知識により、$\tilde{o}\big( s \cdot polylog(d, \frac{1}{\epsilon}) \big)$の属性効率の高いラベル複雑性と$\tilde{o}\big(\frac{s}{\epsilon} \cdot polylog(d) \big)$のサンプル複雑性が得られる。
即ち、ノイズレート$\nu$を仮定しない非依存モデルでは、我々のアクティブ学習者は、同じランニングタイムとラベルとサンプルの複雑さでエラーレート$O(OPT) + \epsilon$を達成し、$OPT$は任意の均質なハーフスペースによって達成可能な最良のエラーレートであることを示す。
関連論文リスト
- 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) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - 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) - 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) - Efficient active learning of sparse halfspaces with arbitrary bounded
noise [34.406103025985445]
我々は,同種$s$スパース半空間の非ラベルデータ分布が等方性対数凹であるような条件下で,$mathbbRd$におけるアクティブラーニングを研究する。
高レベルのラベルノイズの下では、計算効率のよいアルゴリズムによって達成されるラベルの複雑さ境界ははるかに悪化する。
これは、この設定で$frac11-2eta$にラベル複雑性を持つ最初の効率的なアルゴリズムである。
論文 参考訳（メタデータ） (2020-02-12T08:28:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。