論文の概要: The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

• arxiv url: http://arxiv.org/abs/2610.25062v1
• Date: Sun, 18 Oct 2026 07:08:13 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-10-20 22:19:49.765081
• Title: The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning
• Title（参考訳）: ポイントワイズ・リプリケータブル・アグノスティック・ラーニングにおける最適サンプル複雑度
• Abstract要約: ポイントワイドの再現性は、同じランダムシードを使用して、独立に訓練された2つの予測器が、高い確率でそれぞれの固定クエリに一致することを要求する。 有限および可算領域上で、その最適サンプル複雑性を決定する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Pointwise replicability asks that two independently trained predictors, using the same random seed, agree at each fixed query with high probability. We determine its optimal agnostic sample complexity on finite and countable domains. For every nonempty binary class of finite VC dimension $d\ge1$, the required number of independent examples is $Θ\!\left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right)$, uniformly over independent accuracy, failure, and disagreement parameters $α,β,ρ\in(0,1/10)$. The learner returns one binary function, may be improper, and uses unrestricted shared randomness. Its sample budget is fixed before observing data, and the replicability guarantee includes queries of zero marginal mass. The main construction combines an ensemble of empirical-risk minimizers with a smooth, signal-dependent risk decomposition. A single shared phase selects the final binary predictor. Record times certify its weak-signal risk, while a uniform bound protects the strong-signal risk at that same selected time. A phase-comparison theorem controls the actual shared-seed execution under simultaneous changes in the marginals and risk coefficients. A rare repair step then makes the confidence cost additive. Together with matching lower bounds, this removes the remaining logarithmic overhead and parameter restrictions in the general countable-domain sample-complexity problem. This extended version also retains the earlier explicit constructions and their proofs, including proper learning for VC-one classes, the full finite-atom class, a faster realizable bound, and counterexamples that separate restrictions of particular algorithms from restrictions of the learning problem.
• Abstract（参考訳）: ポイントワイドの再現性は、同じランダムシードを使用して、独立に訓練された2つの予測器が、高い確率でそれぞれの固定クエリに一致することを要求する。 有限および可算領域上での最適非依存サンプル複雑性を決定する。 有限 VC 次元 $d\ge1$ の任意の空でないバイナリクラスに対して、必要となる独立例の数は $ \! \left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right)$、独立精度、失敗、不一致パラメータ$α,β,ρ\in(0,1/10)$に対して一様である。 学習者は1つのバイナリ関数を返し、不適切な場合があり、制限のない共有ランダム性を使用する。 サンプル予算はデータを見る前に固定され、複製性保証には限界質量ゼロのクエリが含まれる。 主な構造は、経験的リスク最小化器のアンサンブルと、スムーズで信号依存的なリスク分解を組み合わせたものである。 単一の共有フェーズが最終バイナリ予測子を選択する。 レコードタイムは、その弱い信号リスクを証明し、均一なバウンドは、同じ選択されたタイミングで強い信号リスクを保護する。 位相比較定理は、限界係数とリスク係数の同時変化の下で実際の共有シード実行を制御する。 そして、稀な修理工程により、信頼性コストを加算する。 一致した下界とともに、一般的な可算領域のサンプル複雑度問題における残りの対数的オーバーヘッドとパラメータ制限を除去する。 この拡張バージョンは、VC-oneクラスの適切な学習、完全な有限原子クラス、より高速な実現可能な境界、学習問題の制約から特定のアルゴリズムの制限を分離する反例を含む、初期の明示的な構成と証明も保持している。

関連論文リスト

• Constrained Learning with Universally Learnable Concept Classes [2.5998827435861633]
  双対アルゴリズムの解の解の普遍的な PACC 学習性を確立する。 最適性は、凸性によって支配される普遍性と強ラグランジアン双対性の間に捕えられる。
  論文  参考訳（メタデータ） (2026-08-09T02:13:57Z)
• Replicable Composition [35.262362690798014]
  そこで本研究では,複製性を維持しつつ,$widetildeO(sum_i n_i)$サンプルを共同で解決できることを述べる。 提案手法では, 各レプリカブルアルゴリズムを完全一般化アルゴリズムに変換し, プライバシスタイルの分析により構成し, 相関サンプリングによりマッピングする。
  論文  参考訳（メタデータ） (2026-04-12T02:43:42Z)
• Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
  本研究では、固定されたファミリー$U$からデータ生成分布を適応的に選択できる分布敵の下でのシーケンシャルな意思決定について検討する。 一般化滑らか性(Generalized smoothness)という概念の観点で学習可能性を認めるファミリー$U$のほぼ完全な特徴付けを提供する。 一般化された滑らかさは,分布制約下での個人学習性も特徴付けることを示す。
  論文  参考訳（メタデータ） (2026-02-24T06:15:59Z)
• 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)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
  我々は、一様収束論の極限を超えるフレームワークを通して、最適な高確率リスク境界を提供する。 我々のフレームワークは、置換不変予測器の残余誤差を高い確率リスク境界に変換する。 具体的には, 1-inclusion graph アルゴリズムの特定のアグリゲーションが最適であることを示す。
  論文  参考訳（メタデータ） (2023-04-18T17:57:31Z)
• Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning [36.015585972493575]
  本稿では,一般値関数近似を用いたバッチ強化学習(RL)について考察する。 Empirical Risk Minimizer (ERM) の過剰リスクは、関数クラスの Rademacher 複雑性によって有界である。 高速統計率は局所ラデマッハ複雑性のツールを使用することで達成できる。
  論文  参考訳（メタデータ） (2021-03-25T14:45:29Z)

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

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