論文の概要: Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex
Optimization Approach
- arxiv url: http://arxiv.org/abs/2310.15411v1
- Date: Mon, 23 Oct 2023 23:55:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-25 21:23:49.808195
- Title: Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex
Optimization Approach
- Title(参考訳): ツィバコフ雑音を伴う効率的な能動学習半空間:非凸最適化手法
- Authors: Yinan Li, Chicheng Zhang
- Abstract要約: 我々はTsyybakovcite1epsilonNoisecite 2020$alpha13 unlabeled dataを用いて,効率的な能動学習ハーフスペースを計算的にラベル付けする問題について検討した。
本研究の本体では, $t(c), tildeThelasciteal,z, および, 既知効率の複雑さ間のギャップを低くする情報を用いる。
label $fractilde(d)(c), tildeThelasfoot3-1)$
- 参考スコア(独自算出の注目度): 33.69040519536114
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of computationally and label efficient PAC active
learning $d$-dimensional halfspaces with Tsybakov
Noise~\citep{tsybakov2004optimal} under structured unlabeled data
distributions. Inspired by~\cite{diakonikolas2020learning}, we prove that any
approximate first-order stationary point of a smooth nonconvex loss function
yields a halfspace with a low excess error guarantee. In light of the above
structural result, we design a nonconvex optimization-based algorithm with a
label complexity of $\tilde{O}(d
(\frac{1}{\epsilon})^{\frac{8-6\alpha}{3\alpha-1}})$\footnote{In the main body
of this work, we use $\tilde{O}(\cdot), \tilde{\Theta}(\cdot)$ to hide factors
of the form $\polylog(d, \frac{1}{\epsilon}, \frac{1}{\delta})$}, under the
assumption that the Tsybakov noise parameter $\alpha \in (\frac13, 1]$, which
narrows down the gap between the label complexities of the previously known
efficient passive or active
algorithms~\citep{diakonikolas2020polynomial,zhang2021improved} and the
information-theoretic lower bound in this setting.
- Abstract(参考訳): Tsybakov Noise~\citep{tsybakov 2004optimal} を用いた、構造化されていないデータ分布下での計算およびラベル付きPAC能動学習の課題について検討する。
ここでは, 滑らかな非凸損失関数の任意の1次定常点が, 過大な誤差の保証が低いハーフスペースとなることを証明した。
In light of the above structural result, we design a nonconvex optimization-based algorithm with a label complexity of $\tilde{O}(d (\frac{1}{\epsilon})^{\frac{8-6\alpha}{3\alpha-1}})$\footnote{In the main body of this work, we use $\tilde{O}(\cdot), \tilde{\Theta}(\cdot)$ to hide factors of the form $\polylog(d, \frac{1}{\epsilon}, \frac{1}{\delta})$}, under the assumption that the Tsybakov noise parameter $\alpha \in (\frac13, 1]$, which narrows down the gap between the label complexities of the previously known efficient passive or active algorithms~\citep{diakonikolas2020polynomial,zhang2021improved} and the information-theoretic lower bound in this setting.
関連論文リスト
- 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) - The First Optimal Algorithm for Smooth and
Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
本稿では,スムーズで強靭なミニマックス最適化問題を再考する。
既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。
我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
論文 参考訳(メタデータ) (2022-05-11T17:33:07Z) - Provable Robustness of Adversarial Training for Learning Halfspaces with
Noise [95.84614821570283]
ラベル雑音の存在下での敵対的ロバストなハーフスペースの特性を分析する。
我々の知る限りでは、これは敵の訓練がノイズの分類子を与えることを示す最初の研究である。
論文 参考訳(メタデータ) (2021-04-19T16:35: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) - 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) - Efficient active learning of sparse halfspaces with arbitrary bounded
noise [34.406103025985445]
我々は,同種$s$スパース半空間の非ラベルデータ分布が等方性対数凹であるような条件下で,$mathbbRd$におけるアクティブラーニングを研究する。
高レベルのラベルノイズの下では、計算効率のよいアルゴリズムによって達成されるラベルの複雑さ境界ははるかに悪化する。
これは、この設定で$frac11-2eta$にラベル複雑性を持つ最初の効率的なアルゴリズムである。
論文 参考訳(メタデータ) (2020-02-12T08:28:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。