[LG]《Replicable Composition》K Banihashem, M Bateni, H Esfandiari… [University of Maryland & Google Research] (2026)

在可复现算法领域，当需要同时求解 k 个统计问题时，资源消耗急剧膨胀。朴素方法通过提升每个算法的稳定性参数来组合，导致样本复杂度呈二次方增长至 O(nk²)，根本原因在于各算法的复现误差彼此独立叠加，无法抵消。

本文的核心洞见是：把"直接组合可复现算法"重新看作"在完美泛化算法空间中进行隐私式分析"。将每个可复现算法转化为完美泛化算法后，借助浓度不等式使误差参数按平方根方式累积而非线性叠加，再经相关采样映射回可复现算法，使样本复杂度降至近线性 O(Σnᵢ)，并证明自适应对手场景下 Ω(nk²) 为不可逾越的下界。

这项工作真正留下的遗产是为可复现性建立了首个高级组合定理，统一了此前针对具体问题的特设分析，并揭示了与差分隐私的本质差异——后者的高级组合对自适应场景同样成立，而可复现性中两者存在二次方级分离。它为后来者打开的新门是将"幻影运行"技术推广至充分统计量、序不变性与标签不变性等结构性刻画；但尚未跨过的门槛是如何在连续输出空间或无限域中消除对有限输出集的依赖。

arxiv.org/abs/2604.10423

机器学习 人工智能 论文 AI创造营