論文の概要: Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
- arxiv url: http://arxiv.org/abs/2501.09851v1
- Date: Thu, 16 Jan 2025 21:46:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-20 13:58:52.141168
- Title: Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
- Title（参考訳）: Marginでノイズの多いハーフスペースを学ぶ:Massartはランダムよりも難しい
- Authors: Gautam Chandrasekaran, Vasilis Kontonis, Konstantinos Stavropoulos, Kevin Tian,
- Abstract要約: 我々は、マスアートノイズを伴う$gamma$-marginハーフスペースのPAC学習問題について検討する。
本稿では,サンプル複雑性を$widetildeO((epsilongamma)-2)$とする単純な固有学習アルゴリズムPerspectronを提案する。
- 参考スコア（独自算出の注目度）: 17.56894435702055
- License:
- Abstract: We study the problem of PAC learning $\gamma$-margin halfspaces with Massart noise. We propose a simple proper learning algorithm, the Perspectron, that has sample complexity $\widetilde{O}((\epsilon\gamma)^{-2})$ and achieves classification error at most $\eta+\epsilon$ where $\eta$ is the Massart noise rate. Prior works [DGT19,CKMY20] came with worse sample complexity guarantees (in both $\epsilon$ and $\gamma$) or could only handle random classification noise [DDK+23,KIT+23] -- a much milder noise assumption. We also show that our results extend to the more challenging setting of learning generalized linear models with a known link function under Massart noise, achieving a similar sample complexity to the halfspace case. This significantly improves upon the prior state-of-the-art in this setting due to [CKMY20], who introduced this model.
- Abstract（参考訳）: 我々は、マスアートノイズを伴うPAC学習の問題を考察する。
我々は、サンプル複雑性$\widetilde{O}((\epsilon\gamma)^{-2})$の単純な固有学習アルゴリズムPerspectronを提案し、最大$\eta+\epsilon$の分類誤差を達成する。
以前の[DGT19,CKMY20]は、より悪いサンプルの複雑さを保証する($\epsilon$と$\gamma$の両方で)か、ランダムな分類ノイズ(DDK+23,KIT+23)にしか対応できなかった。
また、この結果は、Massartノイズの下で既知のリンク関数を持つ一般化線形モデルを学習するというより難しい設定にまで拡張され、ハーフスペースの場合と同様のサンプル複雑性が達成されることを示す。
これは、このモデルを導入した[CKMY20]ため、この設定における以前の最先端よりも大幅に改善される。
関連論文リスト
- A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise [36.29182619215646]
我々は、マスアートノイズの存在下で、PACが$gamma$-marginハーフスペースを学習する際の問題について検討する。
我々のアルゴリズムは単純で実用的であり、慎重に選択された凸損失の列にオンラインSGDを頼っている。
論文 参考訳（メタデータ） (2025-01-16T17:44:18Z) - 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) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Boosting in the Presence of Massart Noise [49.72128048499074]
マスアートノイズを伴う(分布に依存しない)PACモデルにおいて、弱い学習者の精度を高める問題について検討する。
我々の主な成果は、Massartノイズの存在下で最初の計算効率の良いブースティングアルゴリズムである。
正の結果の簡単な応用として、高次元矩形の和に対して、第一に効率的なMassart学習者を与える。
論文 参考訳（メタデータ） (2021-06-14T22:21:25Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Classification Under Misspecification: Halfspaces, Generalized Linear
Models, and Connections to Evolvability [39.01599245403753]
特に、Massartノイズ下でのハーフスペースの学習問題を$eta$で検討する。
我々は任意のSQアルゴリズムが$mathsfOPT + epsilon$を達成するのに超ポリノミカルな多くのクエリを必要とすることを示した。
また、Massartノイズ下でハーフスペースを学習するためのアルゴリズムを実証的に研究し、いくつかの魅力的なフェアネス特性を示すことを示した。
論文 参考訳（メタデータ） (2020-06-08T17:59:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。