論文の概要: Near-Optimal Statistical Query Lower Bounds for Agnostically Learning
Intersections of Halfspaces with Gaussian Marginals
- arxiv url: http://arxiv.org/abs/2202.05096v1
- Date: Thu, 10 Feb 2022 15:34:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-11 21:41:58.701727
- Title: Near-Optimal Statistical Query Lower Bounds for Agnostically Learning
Intersections of Halfspaces with Gaussian Marginals
- Title（参考訳）: ガウス辺数をもつ半空間の無知学習交叉に対する近似最適統計クエリ下限
- Authors: Daniel Hsu, Clayton Sanford, Rocco Servedio, Emmanouil-Vasileios
Vlatakis-Gkaragkounis
- Abstract要約: 本稿では,ガウス分布下での中間空間の学習に関するよく研究された問題について,難易度学習モデルを用いて考察する。
下界の2つの変種を証明し、それぞれがダイアコニコラスら (2021) の成分と、Boolean の設定に対する SQ 下界に対する異なる以前のアプローチ(拡張)を組み合わせた。
- 参考スコア（独自算出の注目度）: 10.06689891744466
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the well-studied problem of learning intersections of halfspaces
under the Gaussian distribution in the challenging \emph{agnostic learning}
model. Recent work of Diakonikolas et al. (2021) shows that any Statistical
Query (SQ) algorithm for agnostically learning the class of intersections of
$k$ halfspaces over $\mathbb{R}^n$ to constant excess error either must make
queries of tolerance at most $n^{-\tilde{\Omega}(\sqrt{\log k})}$ or must make
$2^{n^{\Omega(1)}}$ queries. We strengthen this result by improving the
tolerance requirement to $n^{-\tilde{\Omega}(\log k)}$. This lower bound is
essentially best possible since an SQ algorithm of Klivans et al. (2008)
agnostically learns this class to any constant excess error using $n^{O(\log
k)}$ queries of tolerance $n^{-O(\log k)}$. We prove two variants of our lower
bound, each of which combines ingredients from Diakonikolas et al. (2021) with
(an extension of) a different earlier approach for agnostic SQ lower bounds for
the Boolean setting due to Dachman-Soled et al. (2014). Our approach also
yields lower bounds for agnostically SQ learning the class of "convex subspace
juntas" (studied by Vempala, 2010) and the class of sets with bounded Gaussian
surface area; all of these lower bounds are nearly optimal since they
essentially match known upper bounds from Klivans et al. (2008).
- Abstract（参考訳）: ガウス分布下でのハーフ空間の交叉学習に関するよく研究された問題を,挑戦的な「emph{agnostic learning}」モデルで考察する。
diakonikolas et al. (2021) の最近の研究は、任意の統計クエリ (sq) アルゴリズムが、$\mathbb{r}^n$ から一定の過大なエラーに対して$k$ 半空間の交点のクラスを無知に学習するためには、最大$n^{-\tilde{\omega}(\sqrt{\log k})}$ または$$$2^{n^{\omega(1)}} の許容性クエリをしなければならないことを示している。
この結果は、寛容要件を$n^{-\tilde{\Omega}(\log k)}$に改善することで強化される。
この下限は、klivans et al. (2008) の sq アルゴリズムが $n^{o(\log k)}$ query of tolerance $n^{-o(\log k)}$ を使ってこのクラスを常に過大なエラーに無意識的に学習するため、本質的に最良である。
我々は,Dachman-Soled et al. (2014) によるブール設定に対する,Diakonikolas et al. (2021) の成分と (拡張) 以前のSQ下界に対する異なるアプローチを組み合わせた下界の2つの変種を証明した。
このアプローチはまた、「凸部分空間(convex subspace juntas)」のクラス(Vempala, 2010)と有界ガウス曲面を持つ集合のクラス(これらすべての下界は、Klivans et al. (2008) の既知の上界と本質的に一致するため、ほぼ最適である。
関連論文リスト
- Reliable Learning of Halfspaces under Gaussian Marginals [34.64644162448095]
本稿では,カライらの信頼的無知モデルにおけるPAC学習ハーフスペースの問題について検討する。
我々の主な肯定的な結果は、サンプルおよび計算複雑性を持つ$mathbbRd$上のガウス半空間の信頼性学習のための新しいアルゴリズムである。
論文 参考訳（メタデータ） (2024-11-18T02:13:11Z) - Improved Hardness Results for Learning Intersections of Halfspaces [2.1393480341554736]
不適切な設定でハーフ空間の弱学習交差点に対して、強い(そして驚くほど単純な)下界を示す。
我々は、$omega(log log N)$ halfspaces を$N$で学習しても超多項式時間を要することを示すことで、このギャップを著しく狭めている。
具体的には、次元$N$の任意の$k$ハーフスペースに対して、精度$N-Omega(k)$、指数関数的に多くのクエリが必要であることを示す。
論文 参考訳（メタデータ） (2024-02-25T05:26:35Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - 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) - Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces
and ReLU Regression under Gaussian Marginals [43.0867217287089]
ガウス分布の下で半空間を不可知的に学習する作業について検討する。
この課題に対して,ほぼ最適計算硬度を証明した。
論文 参考訳（メタデータ） (2023-02-13T16:46:23Z) - Order-Optimal Error Bounds for Noisy Kernel-Based Bayesian Quadrature [42.129843613950285]
我々は、Match'ern-$nu$ kernel を用いて、Em Reproduction Kernel Hilbert Space (RKHS) の関数を考える。
ブラックボックスクエリが分散$sigma2$のガウスノイズを受ける場合、最大で$T$のアルゴリズムは平均絶対誤差$Omega(T-fracnud-1 + sigma T-frac12)$を発生しなければならない。
論文 参考訳（メタデータ） (2022-02-22T01:49:41Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。