論文の概要: Samplability makes learning easier

• arxiv url: http://arxiv.org/abs/2512.01276v1
• Date: Mon, 01 Dec 2025 04:48:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-02 19:46:34.686761
• Title: Samplability makes learning easier
• Title（参考訳）: サンプル可能性によって学習が楽になる
• Authors: Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan,
• Abstract要約: PAC学習の標準的な定義は、学習者がすべての分布の下で成功することを要求する。 サンプリング可能なPACは,学習者の効率性を大幅に向上させることを示す。
• 参考スコア（独自算出の注目度）: 10.233615909288188
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The standard definition of PAC learning (Valiant 1984) requires learners to succeed under all distributions -- even ones that are intractable to sample from. This stands in contrast to samplable PAC learning (Blum, Furst, Kearns, and Lipton 1993), where learners only have to succeed under samplable distributions. We study this distinction and show that samplable PAC substantially expands the power of efficient learners. We first construct a concept class that requires exponential sample complexity in standard PAC but is learnable with polynomial sample complexity in samplable PAC. We then lift this statistical separation to the computational setting and obtain a separation relative to a random oracle. Our proofs center around a new complexity primitive, explicit evasive sets, that we introduce and study. These are sets for which membership is easy to determine but are extremely hard to sample from. Our results extend to the online setting to similarly show how its landscape changes when the adversary is assumed to be efficient instead of computationally unbounded.
• Abstract（参考訳）: PAC学習の標準的な定義(Valiant 1984)では、学習者はすべての分布で成功する必要がある。 これは、サンプリング可能なPAC学習(Blum, Furst, Kearns, Lipton 1993)とは対照的である。 本研究では,この区別について検討し,サンプリング可能なPACが学習者の効率を著しく向上させることを示す。 まず、標準PACでは指数的なサンプル複雑性を必要とするが、サンプリング可能なPACでは多項式サンプル複雑性で学習できる概念クラスを構築した。 次に、この統計的分離を計算条件に引き上げ、ランダムなオラクルに対する分離を得る。 我々の証明は、我々が導入し研究する新しい複雑さのプリミティブ、明示的な回避セットを中心にしている。 これらは、メンバーシップが容易に決定できるが、サンプリングが極めて難しいセットである。 我々の結果はオンライン設定にまで拡張され、同様に、敵が計算的に非有界ではなく効率的であると仮定した場合、その景観がどのように変化するかが示される。

関連論文リスト

• Nearly Optimal Sample Complexity for Learning with Label Proportions [54.67830198790247]
  トレーニングセットの例をバッグにグループ化する部分情報設定であるLLP(Learning from Label Proportions)について検討する。 部分的な可観測性にもかかわらず、ゴールは個々の例のレベルで小さな後悔を達成することである。 我々は, LLPの2乗損失下でのサンプル複雑性について, 標本複雑性が本質的に最適であることを示す。
  論文  参考訳（メタデータ） (2025-05-08T15:45:23Z)
• Towards Efficient Contrastive PAC Learning [6.209600119671225]
  我々はPAC学習の枠組みの下で対照的な学習について研究する。 本稿では,線形表現の基本概念の対照的な学習について考察する。 我々は,Rademacherの複雑性に基づいた保証を確立し,それとPACの保証を,ある対照的な大マルジン条件下で接続する。
  論文  参考訳（メタデータ） (2025-02-21T21:51:01Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。 データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-16T04:32:22Z)
• Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
  非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。 本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
  論文  参考訳（メタデータ） (2022-10-26T03:19:24Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  本研究では、半教師付きPACモデルにおいて、時間攻撃をテストするために、逆向きに頑健な予測器を学習する問題について検討する。 最悪の分布自由モデルにおいても,半教師付き頑健な学習には大きなメリットがあることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T03:01:45Z)
• On the Complexity of Learning from Label Proportions [4.111899441919163]
  ラベル付学習データを用いてラベル比率で学習する問題について検討する。 この学習モデルは、投票者による政治選挙における候補者の投票数を予測することを含む、幅広い設定に適用できる。 意外なことに、有限VCクラスでは、LPPが効率的に学習できることは、PACで効率的に学習できることの厳密なサブセットであることを示している。
  論文  参考訳（メタデータ） (2020-04-07T16:15:22Z)

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

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