論文の概要: Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness

• arxiv url: http://arxiv.org/abs/2610.26944v2
• Date: Fri, 23 Oct 2026 01:18:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 01:38:06.20373
• Title: Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness
• Title（参考訳）: 厳密に再現可能な実現可能な学習:未知の行列、有限級補間、共有ランダムネスのコスト
• Abstract要約: 本研究では,未知の,未知の,未知の,未知の事例の残差に基づく実存可能なブール学習について検討する。 決定論的学習、任意の有限類に対する極小$$レギュレーション、VC 1 の有限類に対するすべての濃度-再現性レギュレーションを特徴付ける。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Strict replicability requires two independent training samples, processed with the same random seed, to produce exactly the same hypothesis. We study realizable Boolean learning under unknown and known instance marginals. For unknown marginals, we obtain the worst-case sample complexity $Θ(((\log M)^2/ρ^2+\log(1/δ))/\varepsilon)$ for classes of cardinality at most $M$, throughout a fixed small-parameter range. This resolves the distribution-free finite-class sample-complexity question up to universal constants and rules out a general $ρ^{-1}$ dependence. The upper bound uses a truncated-power distribution with a hard empirical-error budget. For known marginals, a control-variate learner uses $O(((1+\log M)^{3/2}/ρ+\log(1/δ))/\varepsilon)$ samples, and explicit uniform-marginal instances establish the matching class-size exponent. On a product of $d$ finite threshold chains of length $k$, we determine the exact rate $Θ((dk\log(1+\sqrt d/(kρ))+\log(1/δ))/\varepsilon)$. We also characterize deterministic learning, the very-small-$ρ$ regime for arbitrary finite classes, and every cardinality-replicability regime for finite classes of VC dimension one. A VC-covering-number bound yields the fixed-accuracy exponent $3/2$ independently of cardinality. Finally, we separate statistical complexity from implementation costs: we prove a sharp fixed-block trade-off, short-seed existence bounds, and a shared rejection-filter reduction from optimal learning of the full Boolean class to efficient public sampling of ordinary Bernoulli product distributions. Detailed proofs include the geometric lower bounds, the discrete posterior-kernel comparison, and the finite-bit constructions.
• Abstract（参考訳）: 厳密な複製性は、全く同じ仮説を生成するために、2つの独立した訓練サンプルを同じランダムシードで処理する必要がある。 本研究では,未知の,未知の,未知の,未知の事例の残差に基づく実存可能なブール学習について検討する。 未知の剰余類に対しては、固定された小パラメータの範囲で、濃度のクラスを最大$M$で、最悪のサンプルの複雑性を$((((\log M)^2/ρ^2+\log(1/δ))/\varepsilon)$とする。 これは分布自由な有限クラスサンプル-複素性問題を普遍定数まで解決し、一般的な$ρ^{-1}$依存を除外する。 アッパーバウンドは、ハードな経験的エラー予算を備えた、切り裂かれたパワー分布を使用する。 既知の境界値に対して、制御変数学習者は$O(((1+\log M)^{3/2}/ρ+\log(1/δ))/\varepsilon)$サンプルを使用し、明示的な一様行列インスタンスが一致するクラスサイズ指数を確立する。 長さ$k$の$d$有限しきい値連鎖の積上では、正確なレートが$\((dk\log(1+\sqrt d/(kρ))+\log(1/δ))/\varepsilon)$を決定する。 また、決定論的学習、任意の有限類に対する極小$ρ$レジーム、VC次元 1 の有限類に対するすべての濃度-再現性レジームを特徴づける。 VC被覆数境界は、基数とは独立に、固定精度指数を3/2$とする。 最後に、統計的複雑さを実装コストから分離する: 鋭い固定ブロックトレードオフ、短シード存在境界、および通常のベルヌーイ積分布の効率的な公開サンプリングのために、フルブールクラスの最適学習から共有拒否フィルタの削減を証明する。 詳細な証明としては、幾何学的下界、離散的後核比較、有限ビット構成などがある。

関連論文リスト

• Hypothesis Selection via Weighted Medians [0.0]
  我々は、$O(varepsilon-2log(n/))$ターゲットサンプルを使用して、$O(nvarepsilon-2log(n/))$timeを少なくとも1-$の確率で実行し、$H_hat i$を満足する$d_mathrmTV(P,H_hat i)leq 3min_iin[n]d_mathrmTV(P,H_i)+varepsilon.$
  論文  参考訳（メタデータ） (2026-10-14T15:45:01Z)
• Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure [50.58119214447535]
  マスク付き生成モデルは並列トークン予測を提供するが、正確な並列サンプリングはトークンを考慮しなければならない。 本研究は,発見を含む全評価がシーケンス長$N$のサブ線形であるかどうかを考察する。 本研究では, 森林構造を隠蔽した離散分布を, 固定された近似条件オラクルを通してアクセスする。
  論文  参考訳（メタデータ） (2026-09-29T15:39:50Z)
• Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
  我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。 多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
  論文  参考訳（メタデータ） (2026-08-04T23:38:54Z)
• The Sample Complexity of Fidelity Estimation to a Known Rank-$r$ Reference State Is $\widetildeΘ(r^2/\varepsilon^2)$ [0.0]
  量子スペクトル推定の精度を一定に抑えるために、ほぼ四分法以下の$widetilde(r2)$を証明した。 また、量子スペクトル推定を一定精度で行うために、ほぼ四分法以下の$widetilde(r2)$を証明した。
  論文  参考訳（メタデータ） (2026-08-03T06:43:01Z)
• Tight Sample Bounds for Renyi and Min-Entropy Estimation [4.866431869728017]
  サンプルからエントロピーを推定することは、情報理論とプロパティテストにおいて基礎となる。 定数加法精度に対する最小エントロピー推定が標本複雑性$(klog k)$であることを証明する。
  論文  参考訳（メタデータ） (2026-07-18T21:01:38Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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