Adaptive Data Analysis for Growing Data

Conference: NeurIPS 2025 arXiv: 2405.13375 Code: None Area: Machine Learning Theory Keywords: Adaptive data analysis, differential privacy, generalization bounds, dynamic data, overfitting

TL;DR

This paper establishes the first generalization bounds for adaptive analysis over dynamically growing data, permitting analysts to schedule queries adaptively based on current dataset size, and achieving increasingly tight guarantees as data accumulates via time-varying empirical accuracy bounds and differential privacy mechanisms.

Background & Motivation

Background: Adaptive data analysis studies overfitting and statistical validity when data is reused across a workflow. Prior work has shown that interacting with data through differentially private algorithms can mitigate overfitting and yield asymptotically optimal generalization guarantees.

Limitations of Prior Work: All existing work assumes a static, fixed-size dataset, which fails to address the practical scenario where databases grow over time. In practice, analysts may dynamically decide when and how to query based on the current volume of data.

Key Challenge: Generalization bounds from static data analysis cannot be directly applied to dynamically growing data, as changes in dataset size affect the statistical power of queries and the degree of overfitting.

Goal: Establish a generalization theory for adaptive analysis over dynamic, growing data.

Key Insight: Allow analysts to adaptively schedule queries (conditioned on current dataset size, historical queries, and responses), and introduce time-varying empirical accuracy bounds and mechanisms so that guarantees tighten as data accumulates.

Core Idea: Extend the differential-privacy-based adaptive data analysis framework to the dynamic data setting while preserving asymptotic optimality.

Method

Overall Architecture

A continuously growing dataset is considered, in which an analyst adaptively submits queries (e.g., statistical estimations). Data responds to queries through differentially private mechanisms. Generalization bounds characterize the accuracy of query results with respect to the population and tighten as data grows.

Key Designs

1. Adaptive Query Scheduling:

   • Function: Allows analysts to dynamically determine query timing based on dataset size.
   • Mechanism: Analysts may submit queries once the data reaches a certain size; each query may depend on all prior query results and the current dataset size. This is more flexible than the static setting, as analysts need not pre-specify all queries.
   • Design Motivation: In practice, analysts typically decide when to conduct analysis based on data volume.

2. Time-Varying Accuracy Bounds and Mechanisms:

   • Function: Provide increasingly tight generalization guarantees as data accumulates.
   • Mechanism: The noise level of the differentially private mechanism and the empirical accuracy bound are both allowed to vary with dataset size. As more data is collected, less noise is injected and the accuracy bound tightens. Overall generalization bounds are derived for this time-varying setting.
   • Design Motivation: Static bounds are conservative — applying the same bound as the dataset grows from 1,000 to 1,000,000 samples wastes substantial statistical power.

3. Asymptotic Optimality in the Batch Query Setting:

   • Function: Establish the theoretical tightness of bounds in the dynamic setting.
   • Mechanism: In the batch query setting (where the analyst submits queries in batches), the data requirement for generalization bounds is shown to grow as the square root of the number of adaptive queries, matching the known asymptotically optimal result from the static setting.
   • Design Motivation: Ensure that the generalization to the dynamic setting incurs no additional statistical cost.

Loss & Training

This is a purely theoretical work. The generalization bounds are instantiated concretely using the clipped Gaussian mechanism and validated on synthetic data.

Key Experimental Results

Main Results

Method	Data Requirement Growth	Applicable Setting	Notes
Ours (Dynamic)	\(\sqrt{k}\) (\(k\) = # queries)	Growing data	Asymptotically optimal
Static bound	\(\sqrt{k}\)	Fixed data	Not applicable to dynamic setting
Data splitting	\(k\)	Both	Suboptimal

Ablation Study

Configuration	Effect	Notes
Time-varying mechanism	Tighter	Exploits data growth
Static mechanism	Looser	Ignores data growth
Non-uniform DP	Tightest	Different privacy budget per step

Key Findings

• Generalization bounds for dynamic data are asymptotically as strong as static bounds, incurring no additional cost.
• Time-varying mechanisms substantially outperform the baseline of directly applying static bounds to dynamic data.
• The clipped Gaussian mechanism empirically outperforms methods based on composition of static bounds.

Highlights & Insights

• Naturalness of the Theoretical Contribution: The extension from static to dynamic data is both natural and important — nearly all real-world data analysis scenarios involve growing data.
• Preservation of Asymptotic Optimality: The paper demonstrates that the generalization to the dynamic setting entails no loss of asymptotic optimality, which is an elegant theoretical result.
• Practical Significance: The work provides a statistically guaranteed adaptive analysis framework for continuously growing databases, such as those arising in medical research and A/B testing.

Limitations & Future Work

• Generalization bounds may remain loose in finite-sample regimes; practical performance may exceed theoretical guarantees.
• Only statistical queries are considered; extensions to more complex query classes remain unexplored.
• Noise injection from differential privacy may affect practical utility, and privacy budget management warrants further study.
• The case of distribution shift over time is not addressed.

Related Work & Insights

• vs. Dwork et al. 2015 (Transfer Theorem): Their results are restricted to static data; this paper extends the framework to the dynamic setting.
• vs. Bassily et al. 2016 (Max Information): Also an optimal bound for the static setting; this paper matches that result in the dynamic setting.
• vs. Data Splitting: Data splitting requires data requirements that grow linearly, whereas the bounds in this paper grow as the square root, yielding higher efficiency.

Rating

• Novelty: ⭐⭐⭐⭐ — A natural yet important theoretical extension
• Experimental Thoroughness: ⭐⭐⭐ — Primarily theoretical, with synthetic experiments for validation
• Writing Quality: ⭐⭐⭐⭐ — Theoretical derivations are clearly presented
• Value: ⭐⭐⭐⭐ — A foundational contribution to the adaptive data analysis literature

Related Papers

• [NeurIPS 2025] Learning Dense Hand Contact Estimation from Imbalanced Data
• [NeurIPS 2025] Inferring Stochastic Dynamics with Growth from Cross-Sectional Data
• [NeurIPS 2025] Radar: Benchmarking Language Models on Imperfect Tabular Data
• [NeurIPS 2025] Weight Weaving: Parameter Pooling for Data-Free Model Merging
• [NeurIPS 2025] Improving Forecasts of Suicide Attempts for Patients with Little Data