自适应数据分析

重复查看同一数据集，好比一边答题一边偷看评分器：单次反馈未必暴露很多，但下一次尝试会专门利用已经泄露的信息。久而久之，留出集不再是独立裁判，而成为训练回路的一部分。问题的核心不是查询数量本身，而是公开记录让分析者对这份特定样本了解了多少。

reusable holdout 如何节制反馈 ​

传统留出集只在模型开发完成后使用一次。若研究者反复依据留出分数调模型，留出集便参与了选择，逐渐变成训练过程的一部分。reusable holdout 的目标是让同一留出集支持多轮模型比较，同时只释放经过阈值化、噪声化或稳定机制处理的信息。

典型设计不会对每次微小改进都返回精确分数，而只在新模型显著超过当前基线时更新公开答案。这样，许多无效尝试不消耗同等信息预算；真正发布的更新次数受到控制。该思想优化的是可复用性，而不是让测试集变成无限资源。

精度损失的三个来源 ​

回答 $a_t$ 与总体值的差可拆成：样本均值和总体均值之间的采样误差，机制加入噪声或近似计算造成的回答误差，以及自适应选择放大的选择偏差。只报告一个“置信区间”会掩盖另外两项。尤其是机制为保持稳定而加入的噪声不能在评估时假装不存在。

若查询是带方向的损失比较，还要明确是同时控制所有历史查询，还是只控制最终选中的一个。前者通常更昂贵；某些机制专门利用“只需保证最终发布结果”的较弱目标。

一棵两层比较树的完整记录 ​

设独立训练信息 $U$ 固定了三个模型 $A,B,C$，查询为它们的有界损失。第一轮机制仅返回一个比特：$u=0$ 表示留出风险上 $A$ 不高于 $B$，$u=1$ 表示 $B$ 更好，平局规则预先固定。第二轮比较第一轮胜者与 $C$：$v=1$ 表示保留胜者，$v=0$ 表示选择 $C$。

第二轮问题确实依赖第一轮反馈；运行中却只公开两个比较位，没有公开精确风险。完整记录有四种可能，故可用 $b=2$ 的界。当 $m=1000,\delta =0.05$ 时，最终模型的经验—总体差以至少 $95\mathrm{\%}$ 概率不超过约 $0.050375$。这里最终模型实际上只有三个，直接对这三个预训练模型应用有限类界，还可将 $b\ln 2=\ln 4$ 换成 $\ln 3$。比特界的好处是一般协议即使不能方便列举全部潜在模型，也能从反馈接口给出统一账本。

若每轮改为返回一个 8 位量化风险，后续算法便可以利用更多可能记录来选择新模型。十个固定的二元反馈位给出 $b=10$，在相同 $m,\delta$ 下界为约 $0.072871$；要求这个界至多为 $0.1$，充分样本数是

这个数量由潜在反馈分支决定，不是由这次实际走过的分支有几个“成功更新”决定。若更新发生在哪一轮也会公开，就需要把该时刻纳入记录。

短输出不等于少量信息访问 ​

设 $D$ 是 $[0,1]$ 上的均匀分布。如果分析者直接读到全部样本，可定义 $q_S(z)={\mathbf{1}}_{\{z\in \{Z_1,\dots ,Z_m\}\}}$。有限集合的总体概率为零，但每个样本点都被命中，所以 $P_S{q}_S=1$、$P{q}_S=0$。

即使最后只公开“经验值等于一”这一比特，也无法得到 $b=1$ 的泛化界：定义最终查询时已经使用了整个数据集，$q_S$ 不能由一个独立 $U$ 和该比特恢复。该反例准确定位了有限反馈定理所限制的信息入口。

能够获得新数据时的边界 ​

该领域不宣称所有探索都必须私有化或噪声化。若可以取得新的独立数据，最直接的修复通常是预注册最终分析，再在独立样本上复现；只有数据昂贵、样本必须复用且交互难以预先封闭时，稳定机制才体现其价值。

三条控制路线 ​

稳定性与差分隐私。 若整个交互机制对替换一个样本点不敏感，则自适应选中的查询难以记住单条记录。差分隐私理路差分隐私Differential privacy · DP · 差分隐私定义用相邻数据集输出分布的乘法比较与加法松弛，限制单条记录对发布结果的影响。提供可组合的稳定性定义，差分隐私蕴含泛化理路差分隐私蕴含泛化Differential privacy implies generalization · Differential privacy and generalization · 隐私稳定性泛化把相邻数据集上的差分隐私稳定性转化为自适应选择统计量的高概率泛化保证。再把它转成期望或高概率的总体误差保证。

信息约束。 上述有限反馈定理使用的是记录的可能值数量，也称描述长度约束。互信息和 max-information 则给出其他信息刻画，各有自己的保证；不能把同一个平方根公式直接赋给任意一种“信息量”。

限制交互结构。 样本切分、预注册分析、独立复现集或只允许少量有效更新，直接减少反馈回路。它们不如通用稳定机制灵活，却常是最透明、最容易审计的实践选择。

为什么只需对所有反馈分支作一次并集 ​

固定 $U=u$，将协议所有可能记录产生的最终查询放进集合

它至多包含 $2^b$ 个函数，而且在读取留出样本之前就由协议和 $u$ 确定。条件于 $U=u$，隐藏样本仍是 $D$ 的IID 样本理路独立同分布样本IID sample · Independent and identically distributed sample以乘积分布描述来自同一总体的独立重复观测。。对每个固定 $f\in {\mathcal{Q}}_u$，Hoeffding 不等式理路Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。给出

用并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。同时保护所有潜在最终查询，得到

实际选出的 $q$ 总在这个集合里，将右侧设为 $\delta$ 就得到所述界；最后用迭代期望理路全期望公式与全方差公式Law of total expectation · Law of total variance · Iterated expectation借助条件信息分解总体均值，并把总波动拆成组内与组间两部分。对独立的 $U$ 平均。机制可以怎样选择分支不影响这一步，因为已经同时保护了所有分支。这是有限假设类泛化界理路有限假设类泛化界Finite-class generalization bound固定假设的集中加上对有限类并集，得到同时成立的风险偏差界。在反馈协议上的应用。

证明没有条件于实际发生的 $H=h$ 再声称 $S$ 仍 IID。那种条件化恰会选择数据，是一开始需要解决的问题。正确顺序是固定独立信息，列出全部潜在查询，再作一次并集。

预算与回答精度的边界 ​

若允许任意长度不超过 $b$ 的二进制串，并且长度本身可见，可能记录数是 $1+2+\cdots +2^b=2^{b+1}-1$，不能直接按 $2^b$ 计数。固定长度或使用适当的完整编码，才能按照声明的范围大小应用定理。停止时间、失败信号和调参过程中展示的其他数字也属于公开记录。

该保证控制 $P_{S}q$ 与 $Pq$。若机制最终回答 $a$ 只是量化或加噪后的近似，还应使用

加入回答误差。若最终回答之后还会继续据此选择新查询，也须把这次回答计入新记录的预算。

若要同时保护 $k$ 个历史查询，最直接的候选计数至多为 $k{2}^b$，界中相应增加 $\ln k$；只证明最终查询并不会自动得到整段回答序列的统一精度。有限反馈也不等于差分隐私：公开一个精确敏感属性只需一位，仍可能完全泄露它。

与常规模型选择的关系 ​

交叉验证和嵌套留出理路留出法与交叉验证Holdout · Cross-validation · 交叉验证通过隔离训练、模型选择和最终评价的数据角色估计样本外风险，并识别反复查看测试集造成的选择偏差。通过协议隔离模型选择与最终评价，适合轮数有限、流程可预先安排的任务。自适应数据分析处理的是更开放的交互：后续问题本身由先前结果塑造。把每轮探索都塞入一次普通交叉验证，不能自动保住最终置信水平。