Adaptive Data Analysis for Growing Data¶

会议: NeurIPS 2025
arXiv: 2405.13375
代码: 无
领域: 机器学习理论
关键词: 自适应数据分析, 差分隐私, 泛化界, 动态数据, 过拟合

一句话总结¶

本文首次给出了动态增长数据上自适应分析的泛化界，允许分析者根据数据规模自适应调度查询，并通过时变经验精度界和差分隐私机制实现随数据积累越来越紧的泛化保证。

领域现状：自适应数据分析研究数据在工作流中被重复使用时的过拟合和统计有效性问题。已有工作证明通过差分隐私算法与数据交互可以缓解过拟合，实现渐近最优的泛化保证。

现有痛点：所有已有工作假设数据是静态的、固定大小的，无法适应数据随时间增长的现实场景。在实践中，数据库持续增长，分析者可能根据当前数据量动态决定何时以及如何查询。

核心矛盾：静态数据分析的泛化界不能直接应用于动态增长数据，因为数据规模变化会影响查询的统计功效和过拟合程度。

本文目标：建立动态数据上自适应分析的泛化理论。

切入角度：允许分析者自适应调度查询（条件于当前数据规模、历史查询和响应），并引入时变的经验精度界和机制，使保证随数据积累变紧。

核心 idea：将差分隐私的自适应数据分析框架推广到动态数据设置，保持渐近最优性。

考虑一个持续增长的数据集，分析者自适应地提交查询（如统计量估计）。数据通过差分隐私机制回应查询。泛化界描述了查询结果在总体上的准确性，并随数据增长而收紧。

自适应查询调度:
- 功能：允许分析者根据数据规模动态决定查询时机
- 核心思路：分析者可以在数据到达特定规模时提交查询，查询本身可以依赖于之前所有查询的结果和当前数据规模。这比静态设置更灵活——分析者不需要预先确定所有查询
- 设计动机：现实中分析者通常根据数据量决定何时进行分析
时变精度界和机制:
- 功能：随数据积累提供越来越紧的泛化保证
- 核心思路：允许差分隐私机制的噪声水平和经验精度界随数据规模变化。数据越多，添加的噪声越小，精度界越紧。推导了在这种时变设置下的整体泛化界
- 设计动机：静态界是保守的——当数据量从1000增长到100万时，用同样的界浪费了大量统计功效
批量查询设置的渐近最优性:
- 功能：证明动态设置的理论紧性
- 核心思路：在批量查询设置中（分析者分批提交查询），证明泛化界的数据需求随自适应查询数量的平方根增长，匹配静态设置中已知的渐近最优结果
- 设计动机：确保推广到动态设置没有引入额外的统计代价

本文为纯理论工作。具体使用clipped Gaussian机制实例化泛化界，并在合成数据上验证。

方法	数据需求增长率	适用场景	说明
本文(动态)	\(\sqrt{k}\) (k=查询数)	增长数据	渐近最优
静态界	\(\sqrt{k}\)	固定数据	不适用动态
数据分割	\(k\)	均适用	次优