論文の概要: Faster Algorithms for Agnostically Learning Disjunctions and their Implications
- arxiv url: http://arxiv.org/abs/2504.15244v1
- Date: Mon, 21 Apr 2025 17:16:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-29 15:55:56.65274
- Title: Faster Algorithms for Agnostically Learning Disjunctions and their Implications
- Title（参考訳）: 高速な解法学習アルゴリズムとその意味
- Authors: Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren,
- Abstract要約: 分布自由PACモデルにおけるブール解離学習のアルゴリズム的タスクについて検討する。
我々は,この概念クラスに対して,複雑性が 2tildeO(n1/2)$ であるような非依存的な学習者を開発する。
- 参考スコア（独自算出の注目度）: 37.35692862344027
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the algorithmic task of learning Boolean disjunctions in the distribution-free agnostic PAC model. The best known agnostic learner for the class of disjunctions over $\{0, 1\}^n$ is the $L_1$-polynomial regression algorithm, achieving complexity $2^{\tilde{O}(n^{1/2})}$. This complexity bound is known to be nearly best possible within the class of Correlational Statistical Query (CSQ) algorithms. In this work, we develop an agnostic learner for this concept class with complexity $2^{\tilde{O}(n^{1/3})}$. Our algorithm can be implemented in the Statistical Query (SQ) model, providing the first separation between the SQ and CSQ models in distribution-free agnostic learning.
- Abstract（参考訳）: 分布非依存型PACモデルにおけるブール解離学習のアルゴリズム的タスクについて検討する。
解離のクラスを$\{0, 1\}^n$で解く最もよく知られた無知学習者は、L_1$-ポリノミカル回帰アルゴリズムであり、複雑性を270tilde{O}(n^{1/2})}$とする。
この複雑性境界は相関統計クエリー (CSQ) アルゴリズムのクラスの中では最もよく可能であることが知られている。
本研究では,この概念クラスに対して,複雑性が 2,^{\tilde{O}(n^{1/3})}$ であるような非依存的な学習者を開発する。
我々のアルゴリズムは統計的クエリー(SQ)モデルで実装でき、分布に依存しない学習においてSQとCSQのモデルを分離する。
関連論文リスト
- 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) - Agnostic Membership Query Learning with Nontrivial Savings: New Results,
Techniques [0.0]
学習の最前線で授業の会員クエリによる学習を検討する。
このアプローチは、非自明な貯蓄を伴う線形学習の研究にインスパイアされ、継続する」。
ゲートのサブ線形数からなる回路の非依存学習アルゴリズムを確立する。
論文 参考訳（メタデータ） (2023-11-11T23:46:48Z) - 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) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。
双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
論文 参考訳（メタデータ） (2020-05-24T18:11:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。