mlsanityData to 7 Oct 2026

Adaptive Data Analysis with Correlated Observations

arXiv 2201.08704 ↗First posted 21 Jan 2022cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

The vast majority of the work on adaptive data analysis focuses on the case where the samples in the dataset are independent. Several approaches and tools have been successfully applied in this context, such as differential privacy, max-information, compression arguments, and more. The situation is far less well-understood without the independence assumption. We embark on a systematic study of the possibilities of adaptive data analysis with correlated observations. First, we show that, in some cases, differential privacy guarantees generalization even when there are dependencies within the sample, which we quantify using a notion we call Gibbs-dependence. We complement this result with a tight negative example. Second, we show that the connection between transcript-compression and adaptive data analysis can be extended to the non-iid setting.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 27 of its 55 references that are in the map. First posted on arXiv 21 Jan 2022.

Builds on

27 of 55 references.

References · 27

  1. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  2. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  3. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  4. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 102
  5. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  6. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  7. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  8. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
  9. 2015Generalization in Adaptive Data Analysis and Holdout Reusecited by 76
  10. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  11. 2015Sample compression schemes for VC classescited by 46
  12. 2019A New Analysis of Differential Privacy's Generalization Guaranteescited by 36
15 more
  1. 2014Preventing False Discovery in Interactive Data Analysis is Hardcited by 34
  2. 2015Simultaneous Private Learning of Multiple Conceptscited by 34
  3. 2020Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Boundcited by 31
  4. 2016Max-Information, Differential Privacy, and Post-Selection Hypothesis Testingcited by 25
  5. 2020Adversarially Robust Streaming Algorithms via Differential Privacycited by 21
  6. 2021Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Boundscited by 17
  7. 2018The Limits of Post-Selection Generalizationcited by 16
  8. 2019Generalization Bounds for Neural Networks via Approximate Description Lengthcited by 15
  9. 2019Learning from weakly dependent data under Dobrushin's conditioncited by 13
  10. 2018Statistical Estimation of Ergodic Markov Chain Kernel over Discrete State Spacecited by 10
  11. 2019Regression from Dependent Observationscited by 10
  12. 2021Separating Adaptive Streaming from Oblivious Streamingcited by 9
  13. 2021A Framework for Adversarial Streaming via Differential Privacy and Difference Estimatorscited by 9
  14. 2021Generalization in the Face of Adaptivity: A Bayesian Perspectivecited by 7
  15. 2016Typical Stabilitycited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 3; 2024: 2; 2025: 1; 2026: 2.

9 papers.

  1. 2023On Differential Privacy and Adaptive Data Analysis with Bounded Spacecited by 9
  2. 2022On the Robustness of CountSketch to Adaptive Inputscited by 5
  3. 2023Adaptive Data Analysis in a Balanced Adversarial Modelcited by 5
  4. 2023Streaming Algorithms for Learning with Experts: Deterministic Versus Robustcited by 3
  5. 2024Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysiscited by 3
  6. 2024Adaptive Data Analysis for Growing Datacited by 1
  7. 2025Tight Bounds for Answering Adaptively Chosen Concentrated Queriescited by 1
  8. 2026Efficient Adaptive Data Analysis over Dense Distributionscited by 0
  9. 2026Is Randomness Necessary for Adaptive Data Analysis?cited by 0