論文の概要: Find a witness or shatter: the landscape of computable PAC learning
- arxiv url: http://arxiv.org/abs/2302.04731v1
- Date: Mon, 6 Feb 2023 02:52:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-10 15:16:48.249696
- Title: Find a witness or shatter: the landscape of computable PAC learning
- Title（参考訳）: 証人や破砕者を見つける:計算可能なPAC学習の風景
- Authors: Valentino Delle Rose, Alexander Kozachinskiy, Cristobal Rojas, Tomasz
Steifer
- Abstract要約: 本稿では,最近の3つのオープンな質問を解き,CPAC学習可能性の研究に寄与する。
まず,全てのCPAC学習可能なクラスが,サンプルの複雑さで適切なCPAC学習が可能なクラスに含まれることを証明した。
第二に、適切に学習できるが、計算不能に急速に増加するサンプルの複雑さに限り、決定可能な仮説のクラスが存在することを示す。
- 参考スコア（独自算出の注目度）: 63.26015736148707
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper contributes to the study of CPAC learnability -- a computable
version of PAC learning -- by solving three open questions from recent papers.
Firstly, we prove that every improperly CPAC learnable class is contained in a
class which is properly CPAC learnable with polynomial sample complexity. This
confirms a conjecture by Agarwal et al (COLT 2021). Secondly, we show that
there exists a decidable class of hypothesis which is properly CPAC learnable,
but only with uncomputably fast growing sample complexity. This solves a
question from Sterkenburg (COLT 2022). Finally, we construct a decidable class
of finite Littlestone dimension which is not improperly CPAC learnable,
strengthening a recent result of Sterkenburg (2022) and answering a question
posed by Hasrati and Ben-David (ALT 2023). Together with previous work, our
results provide a complete landscape for the learnability problem in the CPAC
setting.
- Abstract（参考訳）: 本稿では,最近の論文から3つのオープンな問題を解き,計算可能なPAC学習版であるCPAC学習可能性の研究に寄与する。
まず、不適切なCPAC学習可能なクラスが、多項式サンプルの複雑さを適切に学習可能なクラスに含まれていることを証明する。
これは Agarwal et al (COLT 2021) による予想である。
第二に, cpac が適切に学習可能であるが, 高速に増大するサンプル複雑性を持つ場合のみ, 決定可能な仮説が存在することを示す。
これにより、sterkenburg (colt 2022) の疑問が解決される。
最後に,不適切に cpac を学習できない有限小石次元の決定可能なクラスを構築し,最近の sterkenburg (2022) の結果を強化し,hasrati と ben-david (alt 2023) による質問に答える。
過去の研究と合わせて,CPAC設定における学習可能性問題に対する完全な展望を提供する。
関連論文リスト
- On the Computability of Robust PAC Learning [9.507869508188266]
本稿では,頑健な計算可能PAC(robust CPAC)学習の問題を紹介する。
このセットアップにおける学習性は,コンポーネントの組み合わせによってもたらされるものではない。
我々はその有限性は必要であるが、堅牢なCPAC学習には不十分であることを証明した。
論文 参考訳（メタデータ） (2024-06-14T16:20:04Z) - Private PAC Learning May be Harder than Online Learning [14.180842831990999]
リトルストーン次元の任意の概念クラス$d$は、$mathrmpoly(d)$サンプルを用いてプライベートにPACが学習できることを示す。
これにより、オンライン学習者からプライベートPAC学習者への汎用的な変換が存在するかどうかという自然な疑問が提起される。
論文 参考訳（メタデータ） (2024-02-16T22:44:52Z) - When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。
我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。
これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
論文 参考訳（メタデータ） (2023-10-09T19:40:54Z) - Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
実現可能性の仮定を必要としない,単純かつ効率的なブースティングアルゴリズムを提案する。
本稿では,リスト学習者の向上に関する新たな結果と,マルチクラスPAC学習の特徴付けのための新しい証明を提案する。
論文 参考訳（メタデータ） (2023-07-02T19:26:58Z) - On characterizations of learnability with computable learners [0.0]
Agarwalらによる計算可能PAC(CPAC)学習について検討した。
我々は,強いCPAC学習という,密接に関連する概念を特徴づける。
我々は(計算可能な)PAC学習可能性の不決定性について考察する。
論文 参考訳（メタデータ） (2022-02-10T13:57:20Z) - Semi-verified PAC Learning from the Crowd [7.594050968868919]
本研究では,クラウドソース型PAC学習におけるしきい値関数の問題点について検討する。
本稿では,Charikar等の半検証モデルを用いて,PACが基礎となる仮説クラスを大量のラベルクエリで学習可能であることを示す。
論文 参考訳（メタデータ） (2021-06-13T20:05:16Z) - Sample-efficient proper PAC learning with approximate differential
privacy [51.09425023771246]
近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。
この結果は Bun et al の質問に答えます。
(FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
論文 参考訳（メタデータ） (2020-12-07T18:17:46Z) - Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU
Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。
正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文 参考訳（メタデータ） (2020-06-22T17:53:54Z) - Probably Approximately Correct Constrained Learning [135.48447120228658]
我々は、ほぼ正しい学習フレームワーク(PAC)に基づく一般化理論を開発する。
PAC学習可能なクラスも制約のある学習者であるという意味では,学習者の導入は学習問題を難しくするものではないことを示す。
このソリューションの特性を分析し,制約付き学習が公平でロバストな分類における問題にどのように対処できるかを説明する。
論文 参考訳（メタデータ） (2020-06-09T19:59:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。