論文の概要: The Sample Complexity of Replicable Realizable PAC Learning
- arxiv url: http://arxiv.org/abs/2602.19552v1
- Date: Mon, 23 Feb 2026 06:52:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-24 17:42:02.705364
- Title: The Sample Complexity of Replicable Realizable PAC Learning
- Title（参考訳）: Replicable Realizable PAC Learning のサンプル複雑さ
- Authors: Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, Clement Svendsen,
- Abstract要約: サンプル複雑性は$(log|H|)3/2$に近い値で、仮説クラス $H$ のサイズに依存していることを示す。
我々の証明はいくつかの新しい手法を使用し、$H$に付随する特定のケイリーグラフを定義することで機能する。
- 参考スコア（独自算出の注目度）: 20.81839572366504
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider the problem of replicable realizable PAC learning. We construct a particularly hard learning problem and show a sample complexity lower bound with a close to $(\log|H|)^{3/2}$ dependence on the size of the hypothesis class $H$. Our proof uses several novel techniques and works by defining a particular Cayley graph associated with $H$ and analyzing a suitable random walk on this graph by examining the spectral properties of its adjacency matrix. Furthermore, we show an almost matching upper bound for the lower bound instance, meaning if a stronger lower bound exists, one would have to consider a different instance of the problem.
- Abstract（参考訳）: 本稿では,複製可能なPAC学習の問題について考察する。
特にハードラーニング問題を構築し、サンプル複雑性を$(\log|H|)^{3/2} に近い値で下界に示し、仮説クラス $H$ のサイズに依存する。
我々の証明はいくつかの新しい手法を用いており、特定のCayleyグラフを$H$で定義し、その隣接行列のスペクトル特性を調べて、このグラフ上の適切なランダムウォークを解析することによって機能する。
さらに、下界のインスタンスに対してほぼ一致する上界を示す。つまり、より強い下界が存在するなら、問題の別のインスタンスを考える必要がある。
関連論文リスト
- Learning Gaussian DAG Models without Condition Number Bounds [23.343281561400033]
ガウス図形モデルのトポロジを学習する問題について検討する。
以前の作業では、$O(d log n)$サンプルがこのタスクに十分であることがわかった。
基礎となるグラフを復元し,必要なサンプルの数が条件数に依存しないことを証明するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-11-08T23:42:36Z) - Transductive Learning Is Compact [10.168670899305232]
一般の損失関数を用いた教師あり学習において, 広範に保持されるコンパクト性結果を示す。
不適切な計量損失を伴う実現可能な学習のために、サンプルの複雑さの正確なコンパクトさは失敗する可能性があることを示す。
我々は、無知の場合においてより大きなギャップが可能であると推測する。
論文 参考訳（メタデータ） (2024-02-15T23:10:45Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。
Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:59:30Z) - The Performance of the MLE in the Bradley-Terry-Luce Model in
$\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
我々はBradley-Terry-Luceモデルの$ell_infty$推定誤差に関する新しい一般上限を導出する。
導出された境界は良好に機能し、場合によっては既知の結果よりもシャープであることを示す。
論文 参考訳（メタデータ） (2021-10-20T23:46:35Z) - Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。
双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
論文 参考訳（メタデータ） (2020-05-24T18:11:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。