cs.LGFeb 7, 2026

Efficient Adaptive Data Analysis over Dense Distributions

Authors: Joon Suk Huh

Organizations: Computer Science Department, University of Wisconsin–Madison

Abstract

Modern data workflows are inherently adaptive, repeatedly querying the same dataset to refine and validate sequential decisions, but such adaptivity can lead to overfitting and invalid statistical inference. Adaptive Data Analysis (ADA) mechanisms address this challenge; however, there is a fundamental tension between computational efficiency and sample complexity. For TT rounds of adaptive analysis, computationally efficient algorithms typically incur suboptimal O(T)O(\sqrt{T}) sample complexity, whereas for arbitrary distributions, algorithms with O(log⁡T)O(\log T) sample complexity are computationally intractable under standard cryptographic assumptions. In this work, we shed light on this trade-off by identifying a natural class of data distributions under which both computational efficiency and logarithmic sample complexity in TT are achievable. We propose a computationally efficient ADA mechanism that attains O(log⁡T)O(\log T) sample complexity, optimal in its dependence on TT, when the data distribution is dense with respect to a known prior. This setting includes, in particular, feature-label data distributions arising in distribution-specific learning. As a consequence, our mechanism also yields a sample-efficient (i.e., O(log⁡T)O(\log T) samples) statistical query oracle in the distribution-specific setting. Moreover, although our algorithm is not based on differential privacy, it satisfies a relaxed privacy notion known as Predicate Singling Out (PSO) security (Cohen and Nissim 2020) whenever the number of its possible update transcripts is polynomial in the sample size. Our results thus reveal an inherent connection between adaptive data analysis and privacy beyond differential privacy.

Explore similar work

Jul 8, 2026

Is Randomness Necessary for Adaptive Data Analysis?

The Adaptive Data Analysis (ADA) problem formalizes the challenge of preventing false discovery and overfitting when a dataset is repeatedly reused. Formally, our input is a dataset containing nn i.i.d. samples from an unknown distribution P\mathcal{P} over a domain X\mathcal{X}, and our goal is to answer a sequence of kk adaptively chosen statistical queries with respect to P\mathcal{P}. The main question is how many queries we can support (i.e., how large kk can be), primarily as a function of the number of samples nn. This question has been intensively studied and is relatively well-understood for randomized mechanisms: there are computationally efficient mechanisms that support k≈n2k \approx n^2 queries, and no computationally efficient mechanism can answer k≫n2k \gg n^2 queries. In this paper, we address a fundamental question: is randomness necessary for ADA? Despite a decade of work on ADA, this question remains open. A folklore observation dating back to the initial works on ADA is that randomness is not necessary when the analyst is computationally bounded. Yet, the necessity of randomness against computationally unbounded analysts has remained elusive. Our main contribution resolves this gap in the information-theoretic Random Oracle model. Perhaps surprisingly, we show that randomness is strictly necessary to answer a non-trivial number of adaptive queries: when the analyst is unbounded, any deterministic mechanism can be forced to fail after just k=O~(n)k = \tilde{O} (n) queries.
Oct 17, 2024

Adaptive and oblivious statistical adversaries are equivalent

We resolve a fundamental question about the ability to perform a statistical task, such as learning, when an adversary corrupts the sample. Such adversaries are specified by the types of corruption they can make and their level of knowledge about the sample. The latter distinguishes between sample-adaptive adversaries which know the contents of the sample when choosing the corruption, and sample-oblivious adversaries, which do not. We prove that for all types of corruptions, sample-adaptive and sample-oblivious adversaries are equivalent up to polynomial factors in the sample size. This resolves the main open question introduced by [BLMT22] and further explored in [CHL+23]. Specifically, consider any algorithm AA that solves a statistical task even when a sample-oblivious adversary corrupts its input. We show that there is an algorithm A′A' that solves the same task when the corresponding sample-adaptive adversary corrupts its input. The construction of A′A' is simple and maintains the computational efficiency of AA: It requests a polynomially larger sample than AA uses and then runs AA on a uniformly random subsample.
Oct 22, 2026

Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy

We study learning a discrete distribution under person-level differential privacy in the batched setting. Given nn users, each contributing mm i.i.d. samples from an unknown distribution μμ over [k][k], we seek an estimate of μμ with total-variation error αα. We give polynomial-time algorithms under both pure and approximate differential privacy. Under pure (ε,0)(\varepsilon,0)-DP, we achieve n=O~(k/(α2m)+k/(αmε)+k/ε)n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k/\varepsilon), the first polynomial-time pure-DP guarantee matching the information-theoretic optimum up to logarithmic factors. Under approximate (ε,δ)(\varepsilon,δ)-DP, we achieve n=O~(k/(α2m)+k/(αmε)+k+log⁡(1/δ)/ε)n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k+\log(1/δ)/\varepsilon). At δ=2−Θ(k)δ=2^{-Θ(k)}, this is O~(k)\widetilde O(k) for fixed α,ε,mα,\varepsilon,m and failure probability. Our algorithms use a new degree-6 sum-of-squares estimator for learning from untrusted batches. Its key ingredient is a trace-bounded diagonal majorizer for the difference between the empirical covariance of the repaired batch averages and the multinomial covariance predicted by their mean. We prove that clean data admit this certificate through semidefinite-programming duality and a new application of the stronger symmetric form of Grothendieck's inequality due to Friedland and Lim. The certificate preserves the mean-dependent variance of multinomial batch averages, yielding the near-optimal robust rate O(ηlog⁡(1/η)/m)O(η\sqrt{\log(1/η)/m}) and providing the score required by the privacy reduction. We also prove a statistical query lower bound ruling out a uniformly smaller order of error under fixed polynomial SQ resource bounds.