論文の概要: Statistical Query Lower Bounds for Smoothed Agnostic Learning

• arxiv url: http://arxiv.org/abs/2602.21191v1
• Date: Tue, 24 Feb 2026 18:46:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-25 17:34:53.888575
• Title: Statistical Query Lower Bounds for Smoothed Agnostic Learning
• Title（参考訳）: Smoothed Agnostic Learningのための統計的検索下界
• Authors: Ilias Diakonikolas, Daniel M. Kane,
• Abstract要約: 我々は,最近導入されたCKKMS24によるスムーズな学習の複雑さについて検討した。 具体的には、滑らかなモデルにおいて、ガウス分布の下で半空間を不可知的に学習することに焦点を当てる。
• 参考スコア（独自算出の注目度）: 42.71001191804269
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the complexity of smoothed agnostic learning, recently introduced by~\cite{CKKMS24}, in which the learner competes with the best classifier in a target class under slight Gaussian perturbations of the inputs. Specifically, we focus on the prototypical task of agnostically learning halfspaces under subgaussian distributions in the smoothed model. The best known upper bound for this problem relies on $L_1$-polynomial regression and has complexity $d^{\tilde{O}(1/σ^2) \log(1/ε)}$, where $σ$ is the smoothing parameter and $ε$ is the excess error. Our main result is a Statistical Query (SQ) lower bound providing formal evidence that this upper bound is close to best possible. In more detail, we show that (even for Gaussian marginals) any SQ algorithm for smoothed agnostic learning of halfspaces requires complexity $d^{Ω(1/σ^{2}+\log(1/ε))}$. This is the first non-trivial lower bound on the complexity of this task and nearly matches the known upper bound. Roughly speaking, we show that applying $L_1$-polynomial regression to a smoothed version of the function is essentially best possible. Our techniques involve finding a moment-matching hard distribution by way of linear programming duality. This dual program corresponds exactly to finding a low-degree approximating polynomial to the smoothed version of the target function (which turns out to be the same condition required for the $L_1$-polynomial regression to work). Our explicit SQ lower bound then comes from proving lower bounds on this approximation degree for the class of halfspaces.
• Abstract（参考訳）: 本稿では,入力のガウス的摂動の下で,学習者が対象クラスで最高の分類器と競合する,スムーズな非依存学習の複雑さについて考察する。 具体的には、滑らかなモデルにおけるガウス分布の下で半空間を不可知的に学習する原型的タスクに焦点をあてる。 この問題の最もよく知られた上限は、$L_1$-ポリノミカル回帰に依存し、複雑さは$d^{\tilde{O}(1/σ^2) \log(1/ε)}$であり、$σ$は滑らかなパラメータであり、$ε$は余剰誤差である。 我々の主な結果は統計的クエリ(SQ)の下限であり、この上限が最良に近いという正式な証拠を提供する。 より詳しくは、ハーフ空間の滑らかな非依存学習のための任意のSQアルゴリズムは、d^{Ω(1/σ^{2}+\log(1/ε))}$である。 これは、このタスクの複雑さに関する最初の非自明な下界であり、既知の上界とほぼ一致する。 大まかに言えば、関数の滑らかなバージョンに$L_1$-polynomial回帰を適用するのが本質的に最適であることを示す。 我々の手法は、線形プログラミングの双対性により、モーメントマッチングのハード分布を見つけることを含む。 この双対プログラムは、ターゲット関数の滑らかなバージョンに対する低次近似多項式の発見(これは、仕事に対する$L_1$-ポリノミカル回帰に必要となる条件である)と正確に一致する。 我々の明示的な SQ 下界は、ハーフ空間のクラスに対するこの近似次数に対する下界の証明から得られる。

関連論文リスト

• 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)
• 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)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• 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)
• Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning [7.6146285961466]
  我々は、すべての$gamma 1$に対して一様に束縛されたサンプル複雑性を持つ新しいアルゴリズムのクラスを導入する。 最適化されたステップサイズシーケンスとQ-ラーニングアルゴリズムの共分散は、1/(1-ガンマ)$の二次関数であることを示す。
  論文  参考訳（メタデータ） (2020-02-24T15:12:41Z)

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

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