論文の概要: Fast Agnostic Learners in the Plane

• arxiv url: http://arxiv.org/abs/2510.18057v1
• Date: Mon, 20 Oct 2025 19:49:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:12.546758
• Title: Fast Agnostic Learners in the Plane
• Title（参考訳）: 飛行機内での高速アグノスティック学習者
• Authors: Talya Eden, Ludmila Glinskih, Sofya Raskhodnikova,
• Abstract要約: 平面におけるいくつかの基本的な幾何学的概念クラスに対する不可知学習の計算効率について検討する。 最適なサンプル複雑性を持ち,時間$tilde O(epsilon-6)$で実行される三角形のクラスに対する適切な非依存学習者を提案する。 また,一様分布下の凸集合に対して,動作時間$tilde O(epsilon-5)$の適切な学習器を設計する。
• 参考スコア（独自算出の注目度）: 4.4861549416559185
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the computational efficiency of agnostic learning for several fundamental geometric concept classes in the plane. While the sample complexity of agnostic learning is well understood, its time complexity has received much less attention. We study the class of triangles and, more generally, the class of convex polygons with $k$ vertices for small $k$, as well as the class of convex sets in a square. We present a proper agnostic learner for the class of triangles that has optimal sample complexity and runs in time $\tilde O({\epsilon^{-6}})$, improving on the algorithm of Dobkin and Gunopulos (COLT `95) that runs in time $\tilde O({\epsilon^{-10}})$. For 4-gons and 5-gons, we improve the running time from $O({\epsilon^{-12}})$, achieved by Fischer and Kwek (eCOLT `96), to $\tilde O({\epsilon^{-8}})$ and $\tilde O({\epsilon^{-10}})$, respectively. We also design a proper agnostic learner for convex sets under the uniform distribution over a square with running time $\tilde O({\epsilon^{-5}})$, improving on the previous $\tilde O(\epsilon^{-8})$ bound at the cost of slightly higher sample complexity. Notably, agnostic learning of convex sets in $[0,1]^2$ under general distributions is impossible because this concept class has infinite VC-dimension. Our agnostic learners use data structures and algorithms from computational geometry and their analysis relies on tools from geometry and probabilistic combinatorics. Because our learners are proper, they yield tolerant property testers with matching running times. Our results raise a fundamental question of whether a gap between the sample and time complexity is inherent for agnostic learning of these and other natural concept classes.
• Abstract（参考訳）: 平面におけるいくつかの基本的な幾何学的概念クラスに対する不可知学習の計算効率について検討する。 不可知学習のサンプル複雑度はよく理解されているが、その時間複雑度ははるかに少ない。 我々は三角形のクラスについて研究し、より一般的には、小さな$k$の頂点を持つ凸多角形のクラスと正方形の凸集合のクラスについて研究する。 最適なサンプル複雑性を持ち、時間$\tilde O({\epsilon^{-6}})$で実行し、時間$\tilde O({\epsilon^{-10}})$で実行されるDobkinとGunopulos(COLT `95)のアルゴリズムを改善した三角形のクラスに対する適切な非依存学習器を提案する。 4-角と5-角に対して、Fischer と Kwek (eCOLT `96), $\tilde O({\epsilon^{-8}})$ と $\tilde O({\epsilon^{-10}})$ のランニング時間を改善する。 また,一様分布の凸集合に対して,ランニングタイムを$\tilde O({\epsilon^{-5}})$とすることで,以前の$\tilde O(\epsilon^{-8})$バウンドをわずかに高めのコストで改善する。 特に、一般分布の下での凸集合のagnostic learningは、この概念クラスが無限のVC次元を持つため不可能である。 我々の知能学習者は、計算幾何学からのデータ構造とアルゴリズムを使用し、その解析は幾何学や確率的コンビネータのツールに依存している。 学習者は適切なため、実行時間にマッチした寛容なプロパティテスタが得られます。 以上の結果から,サンプルと時間複雑性のギャップが,これらと他の自然概念の学習に欠かせないものであるかどうかという根本的な疑問が浮かび上がっている。

関連論文リスト

• 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)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• 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)
• 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)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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