論文の概要: 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) - Nearly Optimal Sample Complexity for Learning with Label Proportions [54.67830198790247]
トレーニングセットの例をバッグにグループ化する部分情報設定であるLLP(Learning from Label Proportions)について検討する。
部分的な可観測性にもかかわらず、ゴールは個々の例のレベルで小さな後悔を達成することである。
我々は, LLPの2乗損失下でのサンプル複雑性について, 標本複雑性が本質的に最適であることを示す。
論文 参考訳（メタデータ） (2025-05-08T15:45:23Z) - Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
我々は$f$-divergence-regularized offline policy learningを分析する。
逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。
これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
論文 参考訳（メタデータ） (2025-02-09T22:14:45Z) - 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) - A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
本研究では、半教師付きPACモデルにおいて、時間攻撃をテストするために、逆向きに頑健な予測器を学習する問題について検討する。
最悪の分布自由モデルにおいても,半教師付き頑健な学習には大きなメリットがあることが示されている。
論文 参考訳（メタデータ） (2022-02-11T03:01:45Z) - 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) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-10-05T09:39:51Z) - Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。
双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
論文 参考訳（メタデータ） (2020-05-24T18:11:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。