論文の概要: Attribute-Efficient Learning of Halfspaces with Malicious Noise:
Near-Optimal Label Complexity and Noise Tolerance
- arxiv url: http://arxiv.org/abs/2006.03781v5
- Date: Tue, 2 Mar 2021 07:19:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-24 21:24:47.864525
- Title: Attribute-Efficient Learning of Halfspaces with Malicious Noise:
Near-Optimal Label Complexity and Noise Tolerance
- Title（参考訳）: 有害雑音をもつハーフスペースの属性効率学習:ほぼ最適ラベル複雑性と耐雑音性
- Authors: Jie Shen and Chicheng Zhang
- Abstract要約: 本稿では,雑音下でのmathbbRd$における等質スパース半空間の計算的学習について述べる。
サンプルの複雑さは$tildeObig(frac 1 epsilon s2 log5 d big)$であり、属性効率も楽しめます。
- 参考スコア（独自算出の注目度）: 21.76197397540397
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper is concerned with computationally efficient learning of
homogeneous sparse halfspaces in $\mathbb{R}^d$ under noise. Though recent
works have established attribute-efficient learning algorithms under various
types of label noise (e.g. bounded noise), it remains an open question when and
how $s$-sparse halfspaces can be efficiently learned under the challenging
malicious noise model, where an adversary may corrupt both the unlabeled
examples and the labels. We answer this question in the affirmative by
designing a computationally efficient active learning algorithm with
near-optimal label complexity of $\tilde{O}\big({s \log^4 \frac d \epsilon}
\big)$ and noise tolerance $\eta = \Omega(\epsilon)$, where $\epsilon \in (0,
1)$ is the target error rate, under the assumption that the distribution over
(uncorrupted) unlabeled examples is isotropic log-concave. Our algorithm can be
straightforwardly tailored to the passive learning setting, and we show that
the sample complexity is $\tilde{O}\big({\frac 1 \epsilon s^2 \log^5 d} \big)$
which also enjoys the attribute efficiency. Our main techniques include
attribute-efficient paradigms for instance reweighting and for empirical risk
minimization, and a new analysis of uniform concentration for unbounded data --
all of them crucially take the structure of the underlying halfspace into
account.
- Abstract（参考訳）: 本稿では,雑音下での$\mathbb{R}^d$における均質なスパース半空間の計算効率のよい学習について述べる。
最近の研究は、様々な種類のラベルノイズ(例えば有界雑音)の下で属性効率の学習アルゴリズムを確立しているが、いつ、どのように$s$スパースハーフスペースが困難な悪質なノイズモデルの下で効率的に学習できるかという未解決の疑問が残る。
計算効率のよい能動学習アルゴリズムを設計し、ほぼ最適ラベル複雑性の$\tilde{O}\big({s \log^4 \frac d \epsilon} \big)$および耐雑音性$\eta = \Omega(\epsilon)$, where $\epsilon \in (0, 1)$は目標誤差率であり、未ラベルの例の分布が等方的対数対数対数対数対数対数対数対数対数と仮定して、この疑問に答える。
我々のアルゴリズムは受動的学習環境に直列に調整することができ、サンプルの複雑さは$\tilde{O}\big({\frac 1 \epsilon s^2 \log^5 d} \big)$であることを示す。
私たちの主な技術には、再重み付けや経験的リスク最小化といった属性効率の高いパラダイムや、無制限データに対する統一的な集中度に関する新たな分析が含まれています。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach [28.518140532315776]
本稿では,効率的な能動学習を計算的にラベル付けする問題について検討する。
本稿では, 近似値の証明を行う。
構造化された未ラベルデータセットの1階定常光点。
論文 参考訳（メタデータ） (2023-10-23T23:55:28Z) - 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) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Improved Algorithms for Efficient Active Learning Halfspaces with
Massart and Tsybakov noise [29.890039126644776]
我々は,Massart noisecitepmassart2006riskとTsybakov noiseciteptsybakov 2004を許容できる$d$次元同質半空間に対するPAC能動学習アルゴリズムを開発した。
より難易度の高いツィバコフ雑音条件の下では、2つの雑音条件のサブファミリを同定し、その下でアルゴリズムは計算効率を達成し、ラベルの複雑さを保証する。
論文 参考訳（メタデータ） (2021-02-10T08:17:17Z) - On the Power of Localized Perceptron for Label-Optimal Learning of
Halfspaces with Adversarial Noise [4.8728183994912415]
対比雑音を伴う$mathbbRd$の同質半空間のオンラインアクティブ学習について研究する。
私たちの主な貢献は、時間内で動作するパーセプトロンライクなアクティブラーニングアルゴリズムです。
アルゴリズムは、ほぼ最適ラベルの複雑さで基礎となるハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-12-19T22:04:10Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Efficient active learning of sparse halfspaces with arbitrary bounded
noise [34.406103025985445]
我々は,同種$s$スパース半空間の非ラベルデータ分布が等方性対数凹であるような条件下で,$mathbbRd$におけるアクティブラーニングを研究する。
高レベルのラベルノイズの下では、計算効率のよいアルゴリズムによって達成されるラベルの複雑さ境界ははるかに悪化する。
これは、この設定で$frac11-2eta$にラベル複雑性を持つ最初の効率的なアルゴリズムである。
論文 参考訳（メタデータ） (2020-02-12T08:28:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。