严格可复现可实现学习：未知边际分布、有限类插值与共享随机性代价

该研究确定了边际分布未知条件下严格可复现可实现学习的样本复杂度，证明在大小为 $M$ 的有限类上最坏情况界为 $\Theta((\log M)^2)$。针对全布尔类 $P_d$，论文通过适定泊松化球采样算法给出了匹配的 $\Theta(d^2/(\varepsilon\rho^2)+\varepsilon^{-1}\log(1/\delta))$ 样本复杂度界，并给出了显式 Gibbs 上界。