严格可复制学习样本复杂度定了：最坏情况只需(log M)²，没有迭代对数！
Quadratic Sample Complexity for Strictly Replicable Realizable Learning with Unknown Marginals
📖 AI 总结
该论文研究在可实现分布及其边缘分布均未知的条件下，严格可复现学习所需的样本复杂度。所谓严格可复现，指两个独立样本与同一随机种子必须输出完全相同的函数。作者在有限假设类情形下确定了样本复杂度指数：当误差、置信度与复现参数均取10⁻⁴时，最坏情况下的复杂度为Θ((log M)²)，且不含迭代对数项。对于d维布尔类，论文证明样本量下界为Ω(d²/(ερ²))，并给出匹配的上界Θ(d²/(ερ²)+ε⁻¹log(1/δ))，通过恰当的泊松化球采样算法实现。下界证明借助平方根概率与体积填充技术，上界则基于耦合与泛化恒等式。研究还刻画了已知边缘分布情形的最坏情况，说明两种设定必须区分对待。该工作首次给出未知边缘分布下严格可复现学习的精确样本复杂度刻画，对可复现机器学习理论具有基础意义。
🔑 关键词速览
| 严格可复制性 | 要求两个独立样本和一个共享随机种子产生完全相同的函数。 |
| 可实现分布 | 目标函数属于假设类且数据由该函数无噪声生成的分布。 |
| 边缘分布 | 数据生成分布中特征变量的概率分布，与标签条件分布相对。 |
| 样本复杂度 | 学习器达到给定精度和置信度所需的样本数量。 |
| 泊松化球采样 | 一种基于泊松点过程和球覆盖的采样技术，用于构造正常学习算法。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅