Research map / Learning theory and algorithms / Kernels and regression theory
Adaptive Data Analysis for Growing Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first generalization bounds for adaptive data analysis on growing datasets, using a non-uniform differential privacy stability measure and time-varying accuracy, instantiated for the clipped Gaussian mechanism on statistical queries.
Problem
Adaptive data analysis guarantees have only been studied for static datasets; many real workflows reuse data that grows over time, and analysts may schedule queries based on current dataset size.
Approach
Extends the posterior-stability transfer theorem to growing data by marginalizing the posterior over future unseen data, converts a non-uniform (per-time-step delta) DP definition into posterior stability, and uses time-varying snapshot accuracy so the bound tightens as data accumulates.
Key results
- Ours-N (non-uniform privacy) generally outperforms the baselines in number of answerable adaptive statistical queries across final dataset sizes, under growth ratio n/n0=3.
- Batched setting: asymptotic data requirements grow with square root of number of adaptive queries, matching the static-data improvement over splitting.
- Ours-U and Ours-N show quadratic growth in n, Split linear, JLNRSS/JLNRSS+ slower quadratic growth.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Non-uniform (per-time-step) delta DP stability instead of uniform delta | Clipped Gaussian mechanism for adaptive statistical queries on growing data · Batched statistical queries, growth ratio n/n0=3, alpha=0.1, 95% coverage | number of answerable adaptive queries | Helped |
| Time-varying accuracy bounds and growing-data DP-to-posterior-stability transfer (vs. static bounds composed over batches) | Adaptive statistical queries, clipped Gaussian mechanism · Batched statistical queries, growth ratio n/n0=3, alpha=0.1, 95% coverage | number of answerable adaptive queries | Helped |
| Data growth ratio held constant; required data grows with square root of number of queries | Ours bound in batched setting · Asymptotic data requirements | data requirement scaling in number of queries | No clear effect |
| Split baseline (linear data requirement) vs. stability-based bounds | Sample splitting for growing data · Batched statistical queries, growth ratio n/n0=3, alpha=0.1, 95% coverage | scaling of answerable queries with n | Hurt |
Limitations
- Bounds are mostly worst-case with respect to analyst and distribution, not conditioned on actual queries or data.
- Assumes i.i.d. data; non-i.i.d. growing data is left to future work.
- Additional factor in error proportional to data growth; epsilon' grows linearly in n under uniform delta.
Experimental setup
Metrics: number of adaptive statistical queries answerable at error 0 scaling with final dataset size n
Baselines: JLNRSS JLNRSS+ Split (sample splitting) Ours-U (uniform privacy)
Builds on: transfer theorem for adaptive data analysis (Dwork et al.) posterior stability (Rogers et al. / Jung et al.) privacy filters (Whitehouse et al.) personalized privacy zCDP
Closest papers by meaning
- Tight Bounds for Answering Adaptively Chosen Concentrated Queries (NeurIPS 2025 · similarity 0.87)
- Efficient Adaptive Data Analysis over Dense Data Distributions (NeurIPS 2026 · similarity 0.87)
- Adaptive Data Optimization: Dynamic Sample Selection with Scaling Laws (ICLR 2025 · similarity 0.86)
- Real-Time Selection Under General Constraints via Predictive Inference (NeurIPS 2024 · similarity 0.83)
- Theoretical Analysis of Learned Database Operations under Distribution Shift through Distribution Learnability (ICML 2024 · similarity 0.82)
- Towards Establishing Guaranteed Error for Learned Database Operations (ICLR 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.