論文の概要: Efficient active learning of sparse halfspaces with arbitrary bounded
noise
- arxiv url: http://arxiv.org/abs/2002.04840v3
- Date: Fri, 13 Aug 2021 08:18:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-01 19:23:06.604321
- Title: Efficient active learning of sparse halfspaces with arbitrary bounded
noise
- Title（参考訳）: 任意有界雑音をもつスパース半空間の効率的な能動学習
- Authors: Chicheng Zhang and Jie Shen and Pranjal Awasthi
- Abstract要約: 我々は,同種$s$スパース半空間の非ラベルデータ分布が等方性対数凹であるような条件下で,$mathbbRd$におけるアクティブラーニングを研究する。
高レベルのラベルノイズの下では、計算効率のよいアルゴリズムによって達成されるラベルの複雑さ境界ははるかに悪化する。
これは、この設定で$frac11-2eta$にラベル複雑性を持つ最初の効率的なアルゴリズムである。
- 参考スコア（独自算出の注目度）: 34.406103025985445
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study active learning of homogeneous $s$-sparse halfspaces in
$\mathbb{R}^d$ under the setting where the unlabeled data distribution is
isotropic log-concave and each label is flipped with probability at most $\eta$
for a parameter $\eta \in \big[0, \frac12\big)$, known as the bounded noise.
Even in the presence of mild label noise, i.e. $\eta$ is a small constant, this
is a challenging problem and only recently have label complexity bounds of the
form $\tilde{O}\big(s \cdot \mathrm{polylog}(d, \frac{1}{\epsilon})\big)$ been
established in [Zhang, 2018] for computationally efficient algorithms. In
contrast, under high levels of label noise, the label complexity bounds
achieved by computationally efficient algorithms are much worse: the best known
result of [Awasthi et al., 2016] provides a computationally efficient algorithm
with label complexity $\tilde{O}\big((\frac{s \ln
d}{\epsilon})^{2^{\mathrm{poly}(1/(1-2\eta))}} \big)$, which is label-efficient
only when the noise rate $\eta$ is a fixed constant. In this work, we
substantially improve on it by designing a polynomial time algorithm for active
learning of $s$-sparse halfspaces, with a label complexity of
$\tilde{O}\big(\frac{s}{(1-2\eta)^4} \mathrm{polylog} (d, \frac 1 \epsilon)
\big)$. This is the first efficient algorithm with label complexity polynomial
in $\frac{1}{1-2\eta}$ in this setting, which is label-efficient even for
$\eta$ arbitrarily close to $\frac12$. Our active learning algorithm and its
theoretical guarantees also immediately translate to new state-of-the-art label
and sample complexity results for full-dimensional active and passive halfspace
learning under arbitrary bounded noise. The key insight of our algorithm and
analysis is a new interpretation of online learning regret inequalities, which
may be of independent interest.
- Abstract（参考訳）: 非ラベルのデータ分布が等方的対数凹であり、各ラベルが有界雑音として知られるパラメータ $\eta \in \big[0, \frac12\big)$ に対して最大$\eta$ の確率で反転する設定の下で、同種$s$スパース半空間の活性学習を$\mathbb{R}^d$で研究する。
軽いラベルノイズがある場合でも、例えば$\eta$は小さな定数であり、これは難しい問題であり、計算効率の良いアルゴリズムのために [Zhang, 2018] で確立された $\tilde{O}\big(s \cdot \mathrm{polylog}(d, \frac{1}{\epsilon})\big)$ という形のラベル複雑性境界を持つのは最近である。
対照的に、高レベルなラベルノイズ下では、計算効率のよいアルゴリズムによって達成されるラベルの複雑さの境界は、かなり悪い: [awasthi et al., 2016] の最もよく知られている結果は、ラベルの複雑さを持つ計算効率の良いアルゴリズム$\tilde{o}\big((\frac{s \ln d}{\epsilon})^{2^{\mathrm{poly}(1/(1-2\eta))}} \big)$であり、これはノイズレート$\eta$が固定定数である場合にのみラベル効率である。
本研究では、$s$ スパース半空間のアクティブ学習のための多項式時間アルゴリズムを設計し、ラベル複雑性を$\tilde{O}\big(\frac{s}{(1-2\eta)^4} \mathrm{polylog} (d, \frac 1 \epsilon) \big)$とする。
これは、ラベル複雑性多項式が$\frac{1}{1-2\eta}$のこの設定で最初の効率的なアルゴリズムであり、$\eta$が$\frac12$に任意に近い場合でもラベル効率が良い。
任意の有界雑音下でのフル次元アクティブ・パッシブ・ハーフスペース学習では,能動学習アルゴリズムとその理論的保証は,新たな最先端ラベルとサンプル複雑性に直ちに変換される。
我々のアルゴリズムと分析の鍵となる洞察は、オンライン学習の後悔の不平等の新たな解釈である。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - 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) - 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) - 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) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。