論文の概要: Smoothed Agnostic Learning of Halfspaces over the Hypercube

• arxiv url: http://arxiv.org/abs/2511.17782v1
• Date: Fri, 21 Nov 2025 20:59:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 18:34:24.420353
• Title: Smoothed Agnostic Learning of Halfspaces over the Hypercube
• Title（参考訳）: ハイパーキューブ上のハーフスペースの滑らかなアグノスティック学習
• Authors: Yiwen Kou, Raghu Meka,
• Abstract要約: 我々はブール入力のための新しいスムーズな学習フレームワークを導入し、乱数ビットフリップによって摂動をモデル化する。 入力分布の厳密な部分指数仮定の下では、ハーフスペースを学習するための効率的なアルゴリズムを与える。
• 参考スコア（独自算出の注目度）: 14.269955880630404
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Agnostic learning of Boolean halfspaces is a fundamental problem in computational learning theory, but it is known to be computationally hard even for weak learning. Recent work [CKKMK24] proposed smoothed analysis as a way to bypass such hardness, but existing frameworks rely on additive Gaussian perturbations, making them unsuitable for discrete domains. We introduce a new smoothed agnostic learning framework for Boolean inputs, where perturbations are modeled via random bit flips. This defines a natural discrete analogue of smoothed optimality generalizing the Gaussian case. Under strictly subexponential assumptions on the input distribution, we give an efficient algorithm for learning halfspaces in this model, with runtime and sample complexity approximately n raised to a poly(1/(sigma * epsilon)) factor. Previously, such algorithms were known only with strong structural assumptions for the discrete hypercube, for example, independent coordinates or symmetric distributions. Our result provides the first computationally efficient guarantee for smoothed agnostic learning of halfspaces over the Boolean hypercube, bridging the gap between worst-case intractability and practical learnability in discrete settings.
• Abstract（参考訳）: ブール半空間の非依存的な学習は、計算学習理論の基本的な問題であるが、弱い学習においても計算的に難しいことが知られている。 最近の研究 (CKKMK24) では、そのような硬さを回避できるスムーズな解析法が提案されているが、既存のフレームワークは加法的なガウス摂動に依存しており、離散ドメインには適さない。 我々はブール入力のための新しいスムーズな非依存学習フレームワークを導入し、乱数ビットフリップによって摂動をモデル化する。 これはガウスのケースを一般化する滑らかな最適性の自然な離散アナログを定義する。 入力分布の厳密な部分指数仮定の下では、このモデルで半空間を学習するための効率的なアルゴリズムが与えられ、実行時とサンプルの複雑さはポリ(1/(sigma * epsilon))因子に概ねnである。 以前はそのようなアルゴリズムは、例えば独立座標や対称分布など、離散超キューブの強い構造仮定でしか知られていなかった。 この結果,ブールハイパーキューブ上でのハーフスペースのスムーズな学習を計算的に効率よく保証し,個別設定における最悪の難解性と実践的学習性のギャップを埋めることができた。

関連論文リスト

• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-11-13T00:28:24Z)
• Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension [17.485243410774814]
  教師付き学習の伝統的なモデルでは、学習者の目標は、あるクラスから最も適した概念の競争的($epsilon$以内)な仮説を出力することである。 学習者が最高の無知としか競合しないスムーズな分析フレームワークを導入する。 時間内に$k$-halfspacesの交点を前向きに学習する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-07-01T04:58:36Z)
• Testing distributional assumptions of learning algorithms [5.204779946147061]
  テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。 データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
  論文  参考訳（メタデータ） (2022-04-14T19:10:53Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Agnostic Proper Learning of Halfspaces under Gaussian Marginals [56.01192577666607]
  ガウスの下の半空間を不可知的に学習する問題を考察する。 我々の主な成果は、この問題に対するエム第一固有学習アルゴリズムである。
  論文  参考訳（メタデータ） (2021-02-10T18:40:44Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。