論文の概要: Boosting in the Presence of Massart Noise
- arxiv url: http://arxiv.org/abs/2106.07779v1
- Date: Mon, 14 Jun 2021 22:21:25 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-16 15:28:47.039365
- Title: Boosting in the Presence of Massart Noise
- Title（参考訳）: マスアート騒音の存在下でのブースティング
- Authors: Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane, Rex Lei, Jessica
Sorrell, Christos Tzamos
- Abstract要約: マスアートノイズを伴う(分布に依存しない)PACモデルにおいて、弱い学習者の精度を高める問題について検討する。
我々の主な成果は、Massartノイズの存在下で最初の計算効率の良いブースティングアルゴリズムである。
正の結果の簡単な応用として、高次元矩形の和に対して、第一に効率的なMassart学習者を与える。
- 参考スコア（独自算出の注目度）: 49.72128048499074
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of boosting the accuracy of a weak learner in the
(distribution-independent) PAC model with Massart noise. In the Massart noise
model, the label of each example $x$ is independently misclassified with
probability $\eta(x) \leq \eta$, where $\eta<1/2$. The Massart model lies
between the random classification noise model and the agnostic model. Our main
positive result is the first computationally efficient boosting algorithm in
the presence of Massart noise that achieves misclassification error arbitrarily
close to $\eta$. Prior to our work, no non-trivial booster was known in this
setting. Moreover, we show that this error upper bound is best possible for
polynomial-time black-box boosters, under standard cryptographic assumptions.
Our upper and lower bounds characterize the complexity of boosting in the
distribution-independent PAC model with Massart noise. As a simple application
of our positive result, we give the first efficient Massart learner for unions
of high-dimensional rectangles.
- Abstract（参考訳）: 本研究では,マスアートノイズを伴う(分布非依存)pacモデルにおいて,弱い学習者の精度を高める問題について検討する。
massart ノイズモデルでは、各例のラベル $x$ は確率 $\eta(x) \leq \eta$ と独立に分類され、ここで $\eta<1/2$ である。
マスアートモデルは、ランダム分類ノイズモデルと不可知モデルの間にある。
我々の主な肯定的な結果は、Massartノイズの存在下で初めて計算効率のよいブースティングアルゴリズムであり、任意に$\eta$に近い誤分類誤差を実現する。
我々の研究の前には、この設定では非自明なブースターは知られていなかった。
さらに,この誤差上限は,標準暗号仮定の下で多項式時間ブラックボックスブースターに最適であることを示す。
我々の上界と下界はマッサートノイズを伴う分布非依存pacモデルにおけるブースティングの複雑さを特徴付ける。
正の結果の簡単な応用として、高次元矩形の和に対して、最初の効率的なマッサート学習者を与える。
関連論文リスト
- Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Robust Learning under Strong Noise via SQs [5.9256596453465225]
各SQ学習可能なクラスは、幅広いノイズモデルに対して、OPT + $epsilon Misilon誤分類誤差を持つ効率的な学習アルゴリズムを許容することを示す。
この設定は、既知の雑音確率を持つRCNの下で広く研究されている問題分類を大幅に一般化する。
論文 参考訳（メタデータ） (2020-10-18T21:02:26Z) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。
結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文 参考訳（メタデータ） (2020-06-29T21:06:52Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Towards Deep Learning Models Resistant to Large Perturbations [0.0]
敵対的堅牢性は、機械学習アルゴリズムの必須特性であることが証明されている。
とよばれるアルゴリズムは、大きくても合理的で摂動のマグニチュードが与えられたディープニューラルネットワークのトレーニングに失敗することを示した。
論文 参考訳（メタデータ） (2020-03-30T12:03:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。