論文の概要: Agnostic learning in (almost) optimal time via Gaussian surface area

• arxiv url: http://arxiv.org/abs/2603.06027v1
• Date: Fri, 06 Mar 2026 08:22:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-09 13:17:45.382514
• Title: Agnostic learning in (almost) optimal time via Gaussian surface area
• Title（参考訳）: ガウス表面積による(ほぼ)最適時間における不可知学習
• Abstract要約: Klivans, Klivans (2008) は、$d = O(2 / varepsilon4)$ suffices が $varepsilon$-approximation を達成することを示している。 ダイアコニコラスによる下界に照らして、次数$d = tilde O (2 / varepsilon2)$が十分であることを示す。
• 参考スコア（独自算出の注目度）: 2.797422854005701
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The complexity of learning a concept class under Gaussian marginals in the difficult agnostic model is closely related to its $L_1$-approximability by low-degree polynomials. For any concept class with Gaussian surface area at most $Γ$, Klivans et al. (2008) show that degree $d = O(Γ^2 / \varepsilon^4)$ suffices to achieve an $\varepsilon$-approximation. This leads to the best-known bounds on the complexity of learning a variety of concept classes. In this note, we improve their analysis by showing that degree $d = \tilde O (Γ^2 / \varepsilon^2)$ is enough. In light of lower bounds due to Diakonikolas et al. (2021), this yields (near) optimal bounds on the complexity of agnostically learning polynomial threshold functions in the statistical query model. Our proof relies on a direct analogue of a construction of Feldman et al. (2020), who considered $L_1$-approximation on the Boolean hypercube.
• Abstract（参考訳）: 難しい無知モデルにおいてガウス境界の下で概念クラスを学ぶ複雑さは、その低次多項式による$L_1$-近似性と密接に関連している。 ガウス曲面が少なくとも$$$の任意の概念クラスに対して、Klivans et al (2008) は、$d = O(a^2 / \varepsilon^4)$ suffices が$\varepsilon$-approximation を達成することを示している。 これは、様々な概念クラスを学ぶことの複雑さに最もよく知られた境界をもたらす。 本項では、次数$d = \tilde O (a^2 / \varepsilon^2)$ が十分であることを示すことにより、それらの解析を改善する。 Diakonikolas et al (2021) による下界からすると、これは統計クエリモデルにおける多項式しきい値関数の複雑性に(ほぼ)最適境界をもたらす。 我々の証明は、ブールハイパーキューブ上の$L_1$-approximationを検討したフェルドマンら (2020) の直例に依拠する。

関連論文リスト

• A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces [0.0]
  半空間の平滑化学習の複雑性について,KM25のモデルにおける一様限界の下で検討した。
  論文  参考訳（メタデータ） (2026-05-04T08:53:40Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Statistical Query Lower Bounds for Smoothed Agnostic Learning [42.71001191804269]
  我々は,最近導入されたCKKMS24によるスムーズな学習の複雑さについて検討した。 具体的には、滑らかなモデルにおいて、ガウス分布の下で半空間を不可知的に学習することに焦点を当てる。
  論文  参考訳（メタデータ） (2026-02-24T18:46:46Z)
• Fast Agnostic Learners in the Plane [4.4861549416559185]
  平面におけるいくつかの基本的な幾何学的概念クラスに対する不可知学習の計算効率について検討する。 最適なサンプル複雑性を持ち,時間$tilde O(epsilon-6)$で実行される三角形のクラスに対する適切な非依存学習者を提案する。 また,一様分布下の凸集合に対して,動作時間$tilde O(epsilon-5)$の適切な学習器を設計する。
  論文  参考訳（メタデータ） (2025-10-20T19:49:33Z)
• Robust Learning of Multi-index Models via Iterative Subspace Approximation [36.138661719725626]
  ガウス分布下でラベルノイズを伴うマルチインデックスモデル(MIM)の学習課題について検討する。 一定の正則性特性を満たす有限範囲の良好なMIMに着目する。 ランダムな分類ノイズが存在する場合、我々のアルゴリズムの複雑さは1/epsilon$と不可知的にスケールする。
  論文  参考訳（メタデータ） (2025-02-13T17:37:42Z)
• A Theory of Interpretable Approximations [61.90216959710842]
  我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。 任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。 解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
  論文  参考訳（メタデータ） (2024-06-15T06:43:45Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• A Quadratic Sample Complexity Reduction for Agnostic Learning via Quantum Algorithms [0.0]
  我々は,$O(mboxlog(frac1delta)/epsilon)を$epsilon,deltarightarrow 0arrowとして新しいサンプル複雑性上限を求める。 一般学習の場合、学習速度の量子スピードアップは、$epsilon-1$の2乗である。
  論文  参考訳（メタデータ） (2023-10-24T07:39:16Z)
• 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)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals [10.06689891744466]
  本稿では,ガウス分布下での中間空間の学習に関するよく研究された問題について,難易度学習モデルを用いて考察する。 下界の2つの変種を証明し、それぞれがダイアコニコラスら (2021) の成分と、Boolean の設定に対する SQ 下界に対する異なる以前のアプローチ(拡張)を組み合わせた。
  論文  参考訳（メタデータ） (2022-02-10T15:34:10Z)
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals [47.81107898315438]
  そこで我々は,二元性LPを用いて,多種多様な問題に対するサンプルのハードファミリーを見つける手法を開発した。 L1$-regression は本質的には最適であり、概念クラスを学習する際の計算困難さは、クラスから任意の関数を近似するのに要する次数と密接に関連していることが示される。
  論文  参考訳（メタデータ） (2021-02-08T18:06:32Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)

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

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