論文の概要: Efficient Proper Agnostic Learning of Halfspaces

• arxiv url: http://arxiv.org/abs/2611.02344v1
• Date: Mon, 02 Nov 2026 00:47:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-12 04:58:56.352246
• Title: Efficient Proper Agnostic Learning of Halfspaces
• Title（参考訳）: 半空間の効率よい確率的学習
• Abstract要約: 任意の関数 $f:pm1n to pm1$ へのクエリアクセスが与えられた場合、我々のアルゴリズムは時間$mathrmpoly(n)+2mathrmpoly (1/varepsilon)$で実行される。 我々のアルゴリズムは、pm1n$の均一分布の下での最初の半空間学習者であり、ランニング時間は$n$で、指数は$varepsilon$である。
• 参考スコア（独自算出の注目度）: 9.553146229645789
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We give a proper membership-query algorithm for agnostically learning halfspaces under the uniform distribution on $\{\pm1\}^n$. Given query access to an arbitrary function $f:\{\pm1\}^n \to \{\pm1\}$, our algorithm runs in time $\mathrm{poly}(n)+2^{\mathrm{poly}(1/\varepsilon)}$ and outputs a halfspace with error at most $\mathrm{OPT}+\varepsilon$, where $\mathrm{OPT}$ is the error of the best-fitting halfspace for $f$. Previously, even with membership queries, the best known running time was $n^{\mathrm{poly}(1/\varepsilon)}$, achieved by the sample-based algorithm of Kalai, Klivans, Mansour, and Servedio (FOCS 2005). Our algorithm is the first agnostic halfspace learner under the uniform distribution on $\{\pm1\}^n$ whose running time is polynomial in $n$ with an exponent independent of $\varepsilon$. Combining our algorithm with a boosting argument yields a proper agnostic learner using only random examples. It achieves the same $\mathrm{OPT}+\varepsilon$ guarantee, with running time matching that of Kalai et al.\ up to an additive term depending only on $\varepsilon$. To our knowledge, this is the first sample-based proper agnostic learner in the Boolean setting with running time $2^{o(n)}$ for every fixed $\varepsilon>0$.
• Abstract（参考訳）: 我々は、$\{\pm1\}^n$ 上の一様分布の下で半空間を不可知的に学習するための適切なメンバシップクエリーアルゴリズムを与える。 任意の関数 $f:\{\pm1\}^n \to \{\pm1\}$ に対するクエリアクセスが与えられた場合、我々のアルゴリズムは時間で $\mathrm{poly}(n)+2^{\mathrm{poly}(1/\varepsilon)}$ を実行し、エラーを最大で $\mathrm{OPT}+\varepsilon$ で出力する。 以前は、メンバーシップクエリでさえ、最もよく知られた実行時間は、Kalai、Klivans、Mansour、Servedio (FOCS 2005)のサンプルベースのアルゴリズムによって達成された$n^{\mathrm{poly}(1/\varepsilon)}$であった。 我々のアルゴリズムは、$\{\pm1\}^n$の均一分布における最初の非依存半空間学習者であり、その実行時間は$\varepsilon$の指数独立な$n$の多項式である。 我々のアルゴリズムとブースティング引数を組み合わせることで、ランダムな例のみを用いて適切な無知学習者が得られる。 これは$\mathrm{OPT}+\varepsilon$の保証を達成し、Kalai et al \ のランニングタイムを $\varepsilon$ にのみ依存する加法項までマッチングする。 我々の知る限り、これはBoolean設定において、固定された$\varepsilon>0$に対して、実行時間2^{o(n)}$でサンプルベースの適切な非学習者である。

関連論文リスト

• Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model [37.35522173770848]
  対称ポリトープ$P=mathbfxinmathbbRd:|mathbfAmathbfx|_inftyle1$, $mathbfAinmathbbRntimes d$のジョン・エリプシドは、長いレバレッジスコアアルゴリズムによって計算される。
  論文  参考訳（メタデータ） (2026-06-18T11:00:03Z)
• Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals [5.7652356955571085]
  i.d.ラベル付きサンプルが$mathbbRd times pm 1$上の未知の分布からサンプリングされ、$mathbbRd$がガウシアンであることを考えると、目標はターゲットクラス$mathcalF$から仮説を出力することである。 我々のアルゴリズムは、$dO(K2 log (1/)/2) + (K/)O(K) で実行されます。
  論文  参考訳（メタデータ） (2026-05-26T19:07:06Z)
• Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
  我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。 コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。 我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
  論文  参考訳（メタデータ） (2025-09-25T07:39:25Z)
• Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
  未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。 我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。 このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
  論文  参考訳（メタデータ） (2024-02-22T02:20:24Z)
• A faster and simpler algorithm for learning shallow networks [10.595936992218856]
  ラベル付き例から、$k$ReLUアクティベーションの線形結合を学習する、よく研究された問題を再考する。 ここでは、アルゴリズムのよりシンプルなワンステージバージョンが十分であることを示し、そのランタイムは、わずか$(d/varepsilon)O(k2)$である。
  論文  参考訳（メタデータ） (2023-07-24T03:04:10Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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