論文の概要: 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（参考訳）: ガウス表面積による(ほぼ)最適時間における不可知学習
• Authors: Lucas Pesenti, Lucas Slot, Manuel Wiedmer,
• 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) の直例に依拠する。

関連論文リスト

• Statistical Query Lower Bounds for Smoothed Agnostic Learning [42.71001191804269]
  我々は,最近導入されたCKKMS24によるスムーズな学習の複雑さについて検討した。 具体的には、滑らかなモデルにおいて、ガウス分布の下で半空間を不可知的に学習することに焦点を当てる。
  論文  参考訳（メタデータ） (2026-02-24T18:46:46Z)
• Robust Learning of Multi-index Models via Iterative Subspace Approximation [36.138661719725626]
  ガウス分布下でラベルノイズを伴うマルチインデックスモデル(MIM)の学習課題について検討する。 一定の正則性特性を満たす有限範囲の良好なMIMに着目する。 ランダムな分類ノイズが存在する場合、我々のアルゴリズムの複雑さは1/epsilon$と不可知的にスケールする。
  論文  参考訳（メタデータ） (2025-02-13T17:37:42Z)
• 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)

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

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