論文の概要: Quadratic Sample Complexity for Strictly Replicable Realizable Learning with Unknown Marginals
- arxiv url: http://arxiv.org/abs/2610.26944v1
- Date: Sun, 18 Oct 2026 05:17:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-21 21:58:47.404487
- Title: Quadratic Sample Complexity for Strictly Replicable Realizable Learning with Unknown Marginals
- Title（参考訳）: 未知の母語を用いた厳密に再現可能な実現可能な学習のための二次的サンプル複雑度
- Abstract要約: 2つの独立したサンプルと1つの共有シードは、同じ関数を生成する必要がある。
for $varepsilon===10-4$, the worst case over $|H|le M$ is $(log M)2)$, without iterated logarithms.
for $dge1$, $0varepsilonle1/16$, $0,le10-3$, every randomized, potentially unroper learner valid across a explicit anchored realizable family requires $(d2/(varepsilon2)$ sample
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Under the quantifier $\exists A\,\forall D$, where the realizable distribution and its marginal are unknown, we determine the finite-class sample-complexity exponent for strict replicability: two independent samples and one shared seed must produce identical functions. For $\varepsilon=δ=ρ=10^{-4}$, the worst case over $|H|\le M$ is $Θ((\log M)^2)$, without iterated logarithms. For $d\ge1$, $0<\varepsilon\le1/16$, and $0<δ,ρ\le10^{-3}$, every randomized, possibly improper learner valid throughout an explicit anchored realizable family requires $Ω(d^2/(\varepsilonρ^2))$ samples. For the full Boolean class $P_d$, $d\ge2$, in the same parameter range, we prove the matching characterization $Θ(d^2/(\varepsilonρ^2)+\varepsilon^{-1}\log(1/δ))$ using a proper Poissonized ball-sampling algorithm. We also give an explicit proper Gibbs upper bound for every finite measurable Boolean class. Our lower bound uses square-root probabilities and volumetric packing; the Gibbs proof builds on established coupling and generalization identities. Finally, we characterize the known-marginal worst case for $P_d$, showing why that interface must be kept distinct.
- Abstract（参考訳）: 量子化器 $\exists A\,\forall D$ では、実現可能な分布とその限界が未知であり、厳密な複製性のために有限級のサンプル複素指数を決定する: 2つの独立標本と1つの共有シードは同じ関数を生成しなければならない。
$\varepsilon=δ=ρ=10^{-4}$ の場合、$|H|\le M$ 上の最悪のケースは、反復対数なしで$((\log M)^2)$ である。
$d\ge1$, $0<\varepsilon\le1/16$, $0<δ,ρ\le10^{-3}$の場合、明示的なアンカー化可能ファミリを通して有効な任意のランダム化学習者は、$Ω(d^2/(\varepsilonρ^2))$サンプルを必要とする。
同じパラメータ範囲のブールクラス $P_d$, $d\ge2$ に対して、適切なポアソン化ボールサンプリングアルゴリズムを用いて、マッチングされた特徴式 $\(d^2/(\varepsilonρ^2)+\varepsilon^{-1}\log(1/δ))$ を証明する。
また、すべての有限可測ブール類に対して、明示的な正則ギブス上界を与える。
我々の下界は平方根確率と体積パッキングを使い、ギブスの証明は確立された結合と一般化のアイデンティティに基づいている。
最後に、既知の$P_d$の最悪のケースを特徴付け、そのインターフェースを区別しなければならない理由を示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。