論文の概要: Efficient Testable Learning of Halfspaces with Adversarial Label Noise
- arxiv url: http://arxiv.org/abs/2303.05485v1
- Date: Thu, 9 Mar 2023 18:38:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-10 13:37:32.891788
- Title: Efficient Testable Learning of Halfspaces with Adversarial Label Noise
- Title（参考訳）: 逆ラベル雑音をもつハーフスペースの効率的なテスト可能学習
- Authors: Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos
Zarifis
- Abstract要約: 最近導入されたテスト可能な学習モデルでは、データがテスタを通過すると、データに対する堅牢な学習者の出力を信頼するように、テスタ-ラーナーを作成する必要がある。
テストラナーは、時間$poly(d/eps)$を実行し、ミス分類エラー$O(opt)+eps$でハーフスペースを出力します。
- 参考スコア（独自算出の注目度）: 44.32410859776227
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give the first polynomial-time algorithm for the testable learning of
halfspaces in the presence of adversarial label noise under the Gaussian
distribution. In the recently introduced testable learning model, one is
required to produce a tester-learner such that if the data passes the tester,
then one can trust the output of the robust learner on the data. Our
tester-learner runs in time $\poly(d/\eps)$ and outputs a halfspace with
misclassification error $O(\opt)+\eps$, where $\opt$ is the 0-1 error of the
best fitting halfspace. At a technical level, our algorithm employs an
iterative soft localization technique enhanced with appropriate testers to
ensure that the data distribution is sufficiently similar to a Gaussian.
- Abstract（参考訳）: ガウス分布下での逆ラベル雑音の存在下での半空間の検証可能な学習に対して,最初の多項式時間アルゴリズムを与える。
最近導入されたテスト可能な学習モデルでは、データがテスタを通過すると、データに対する堅牢な学習者の出力を信頼するように、テスタ-ラーナーを作成する必要がある。
私たちのtester-learnerは$\poly(d/\eps)$で実行し、ミスクラス化エラーである$o(\opt)+\eps$でハーフスペースを出力する。
技術的レベルでは,データ分布がガウスと十分に類似していることを保証するために,適切なテスタによって拡張された反復的ソフトローカライズ手法を用いる。
関連論文リスト
- Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds [9.036777309376697]
Klivans、Stavropoulos、Vasilyanは、分散シフトを伴うテスト可能な学習の研究を始めた。
それらのモデルは、$mathcalD'$に仮定されないという点で、以前のすべての作業から逸脱している。
論文 参考訳（メタデータ） (2024-04-02T23:34:39Z) - Testable Learning with Distribution Shift [9.036777309376697]
分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。
テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。
ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
論文 参考訳（メタデータ） (2023-11-25T23:57:45Z) - 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) - An Efficient Tester-Learner for Halfspaces [13.13131953359806]
本稿では、Rubinfeld と Vasilyan が最近定義したテスト可能な学習モデルにおいて、ハーフスペースを学習するための最初の効率的なアルゴリズムを提案する(2023)。
このモデルでは、学習者は、トレーニングセットがテストに合格するたびに、その出力仮説の精度がほぼ最適であると認定する。
論文 参考訳（メタデータ） (2023-02-28T18:51:55Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。
データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
論文 参考訳（メタデータ） (2022-04-14T19:10:53Z) - Provable Robustness of Adversarial Training for Learning Halfspaces with
Noise [95.84614821570283]
ラベル雑音の存在下での敵対的ロバストなハーフスペースの特性を分析する。
我々の知る限りでは、これは敵の訓練がノイズの分類子を与えることを示す最初の研究である。
論文 参考訳（メタデータ） (2021-04-19T16:35:38Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。