論文の概要: Improved Algorithms for Efficient Active Learning Halfspaces with
Massart and Tsybakov noise
- arxiv url: http://arxiv.org/abs/2102.05312v1
- Date: Wed, 10 Feb 2021 08:17:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-11 14:45:05.617444
- Title: Improved Algorithms for Efficient Active Learning Halfspaces with
Massart and Tsybakov noise
- Title（参考訳）: Massart および Tsybakov ノイズを用いた効率的なアクティブ学習半空間のアルゴリズムの改善
- Authors: Chicheng Zhang and Yinan Li
- Abstract要約: 我々は,Massart noisecitepmassart2006riskとTsybakov noiseciteptsybakov 2004を許容できる$d$次元同質半空間に対するPAC能動学習アルゴリズムを開発した。
より難易度の高いツィバコフ雑音条件の下では、2つの雑音条件のサブファミリを同定し、その下でアルゴリズムは計算効率を達成し、ラベルの複雑さを保証する。
- 参考スコア（独自算出の注目度）: 29.890039126644776
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop a computationally-efficient PAC active learning algorithm for
$d$-dimensional homogeneous halfspaces that can tolerate Massart
noise~\citep{massart2006risk} and Tsybakov noise~\citep{tsybakov2004optimal}.
Specialized to the $\eta$-Massart noise setting, our algorithm achieves an
information-theoretic optimal label complexity of $\tilde{O}\left(
\frac{d}{(1-2\eta)^2} \mathrm{polylog}(\frac1\epsilon) \right)$ under a wide
range of unlabeled data distributions (specifically, the family of "structured
distributions" defined in~\citet{diakonikolas2020polynomial}). Under the more
challenging Tsybakov noise condition, we identify two subfamilies of noise
conditions, under which our algorithm achieves computational efficiency and
provide label complexity guarantees strictly lower than passive learning
algorithms.
- Abstract（参考訳）: 我々は,マッサートノイズ~\citep{massart2006risk} と tsybakov noise~\citep{tsybakov2004optimal} を許容する,次元一様半空間に対する計算効率の高いpac能動学習アルゴリズムを開発した。
このアルゴリズムは、$\eta$-Massartノイズ設定に特化し、$\tilde{O}\left( \frac{d}{(1-2\eta)^2} \mathrm{polylog}(\frac1\epsilon) \right)$の幅広いラベルなしデータ分布(特に、~\citet{diakonikolas2020polynomial}で定義された「構造分布」のファミリー)の情報理論的最適ラベル複雑性を実現します。
より難解なツィバコフ雑音条件下では,提案アルゴリズムが計算効率を達成し,パッシブ学習アルゴリズムよりもラベルの複雑さを保証する2つのノイズ条件のサブファミリを同定する。
関連論文リスト
- 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) - 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) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - The Complexity of Adversarially Robust Proper Learning of Halfspaces
with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。
この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文 参考訳（メタデータ） (2020-07-30T04:18:51Z) - 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) - Efficiently Learning Adversarially Robust Halfspaces with Noise [69.01459748050453]
本研究では,分布に依存しない環境下で,逆向きに頑健なハーフスペースを学習する問題について検討する。
実現可能な設定では、ハーフ空間が効果的に学習可能な対向摂動集合に対して必要かつ十分な条件を提供する。
論文 参考訳（メタデータ） (2020-05-15T17:13:54Z) - Efficient active learning of sparse halfspaces with arbitrary bounded
noise [34.406103025985445]
我々は,同種$s$スパース半空間の非ラベルデータ分布が等方性対数凹であるような条件下で,$mathbbRd$におけるアクティブラーニングを研究する。
高レベルのラベルノイズの下では、計算効率のよいアルゴリズムによって達成されるラベルの複雑さ境界ははるかに悪化する。
これは、この設定で$frac11-2eta$にラベル複雑性を持つ最初の効率的なアルゴリズムである。
論文 参考訳（メタデータ） (2020-02-12T08:28:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。