論文の概要: Testable Learning of General Halfspaces under Massart Noise
- arxiv url: http://arxiv.org/abs/2602.22300v1
- Date: Wed, 25 Feb 2026 18:30:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-27 18:41:22.367319
- Title: Testable Learning of General Halfspaces under Massart Noise
- Title（参考訳）: マスアート騒音下での一般半空間の検証可能な学習
- Authors: Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Sihan Liu,
- Abstract要約: ガウス分布の下で一般マスアート半空間を実証的に学習するアルゴリズム的タスクについて検討する。
テスト可能な学習環境では、以下の特性を満たすテスター-ラーナーペアの設計が目的である。
我々の主な成果は、Massartノイズと限界を持つ一般半空間に対する最初のテスト可能な学習アルゴリズムである。
- 参考スコア（独自算出の注目度）: 40.15176310729312
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the algorithmic task of testably learning general Massart halfspaces under the Gaussian distribution. In the testable learning setting, the aim is the design of a tester-learner pair satisfying the following properties: (1) if the tester accepts, the learner outputs a hypothesis and a certificate that it achieves near-optimal error, and (2) it is highly unlikely that the tester rejects if the data satisfies the underlying assumptions. Our main result is the first testable learning algorithm for general halfspaces with Massart noise and Gaussian marginals. The complexity of our algorithm is $d^{\mathrm{polylog}(\min\{1/γ, 1/ε\})}$, where $ε$ is the excess error and $γ$ is the bias of the target halfspace, which qualitatively matches the known quasi-polynomial Statistical Query lower bound for the non-testable setting. The analysis of our algorithm hinges on a novel sandwiching polynomial approximation to the sign function with multiplicative error that may be of broader interest.
- Abstract（参考訳）: ガウス分布の下で一般マスアート半空間を実証的に学習するアルゴリズム的タスクについて検討する。
テスト可能な学習環境では,(1) テスタが受け入れた場合,学習者が仮説と証明を出力し,(2) テスタが基礎となる仮定を満たすと拒否する可能性は極めて低い。
我々の主な成果は、Massartノイズとガウス限界を持つ一般半空間に対する最初のテスト可能な学習アルゴリズムである。
アルゴリズムの複雑さは$d^{\mathrm{polylog}(\min\{1/γ, 1/ε\})}$である。
アルゴリズムの解析は, より広い関心を持つ乗算誤差を持つ符号関数に対する, サンドイッチ多項式近似に基づく。
関連論文リスト
- Efficient Testable Learning of General Halfspaces with Adversarial Label Noise [37.4323638115877]
逆ラベル雑音を伴う一般半空間の検証可能な学習課題について検討する。
テスト可能な学習フレームワークでは、データがテスタを通過すると、データに対する堅牢な学習者のアウトプットを信頼できるように、テスタ-ラーナーを開発することが目標である。
我々のアプローチの核心は、一般的なハーフ空間の検証可能な学習を、より広い関心を持つであろうほぼ同質なハーフ空間の検証可能な学習に還元する新しい手法である。
論文 参考訳（メタデータ） (2024-08-30T10:08:21Z) - 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) - Efficient Testable Learning of Halfspaces with Adversarial Label Noise [44.32410859776227]
最近導入されたテスト可能な学習モデルでは、データがテスタを通過すると、データに対する堅牢な学習者の出力を信頼するように、テスタ-ラーナーを作成する必要がある。
テストラナーは、時間$poly(d/eps)$を実行し、ミス分類エラー$O(opt)+eps$でハーフスペースを出力します。
論文 参考訳（メタデータ） (2023-03-09T18:38:46Z) - 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) - Agnostic Proper Learning of Halfspaces under Gaussian Marginals [56.01192577666607]
ガウスの下の半空間を不可知的に学習する問題を考察する。
我々の主な成果は、この問題に対するエム第一固有学習アルゴリズムである。
論文 参考訳（メタデータ） (2021-02-10T18:40:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。