論文の概要: The Complexity of Adversarially Robust Proper Learning of Halfspaces
with Agnostic Noise
- arxiv url: http://arxiv.org/abs/2007.15220v1
- Date: Thu, 30 Jul 2020 04:18:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-05 13:51:21.851260
- Title: The Complexity of Adversarially Robust Proper Learning of Halfspaces
with Agnostic Noise
- Title(参考訳): 雑音を伴わない半空間の対向的ロバストな固有学習の複雑さ
- Authors: Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
- Abstract要約: 分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。
この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
- 参考スコア(独自算出の注目度): 67.27523616312428
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the computational complexity of adversarially robust proper learning
of halfspaces in the distribution-independent agnostic PAC model, with a focus
on $L_p$ perturbations. We give a computationally efficient learning algorithm
and a nearly matching computational hardness result for this problem. An
interesting implication of our findings is that the $L_{\infty}$ perturbations
case is provably computationally harder than the case $2 \leq p < \infty$.
- Abstract(参考訳): 分布非依存的pacモデルにおける半空間の可逆的ロバストな固有学習の計算複雑性を,$l_p$摂動に着目して検討した。
この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
我々の発見の興味深い意味は、$L_{\infty}$摂動の場合が、$2 \leq p < \infty$よりも明らかに計算が難しいことである。
関連論文リスト
- 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) - Sample Complexity Bounds for Robustly Learning Decision Lists against
Evasion Attacks [25.832511407411637]
敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。
我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。
すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
論文 参考訳(メタデータ) (2022-05-12T14:40:18Z) - Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。
提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
論文 参考訳(メタデータ) (2020-06-22T17:58:54Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳(メタデータ) (2020-06-11T14:25:02Z) - Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。
双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
論文 参考訳(メタデータ) (2020-05-24T18:11:57Z) - Efficiently Learning Adversarially Robust Halfspaces with Noise [69.01459748050453]
本研究では,分布に依存しない環境下で,逆向きに頑健なハーフスペースを学習する問題について検討する。
実現可能な設定では、ハーフ空間が効果的に学習可能な対向摂動集合に対して必要かつ十分な条件を提供する。
論文 参考訳(メタデータ) (2020-05-15T17:13:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。