Natural Analysts in Adaptive Data Analysis
Authors: Tijana Zrnic, Moritz Hardt
ICML 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we propose notions of natural analysts that smoothly interpolate between the optimal non-adaptive bounds and the best-known adaptive generalization bounds. To accomplish this, we model the analyst s knowledge as evolving according to the rules of an unknown dynamical system that takes in revealed information and outputs new statistical queries to the data. This allows us to restrict the analyst through different natural control-theoretic notions. One such notion corresponds to a recency bias, formalizing an inability to arbitrarily use distant information. Another complementary notion formalizes an anchoring bias, a tendency to weight initial information more strongly. Both notions come with quantitative parameters that smoothly interpolate between the non-adaptive case and the fully adaptive case, allowing for a rich spectrum of intermediate analysts that are neither non-adaptive nor adversarial. Natural not only from a cognitive perspective, we show that our notions also capture standard optimization methods, like gradient descent in various settings. This gives a new interpretation to the fact that gradient descent tends to overfit much less than its adaptive nature might suggest. Theorem 1 (Informal result for progressive analysts). There is a computationally efficient algorithm to an-swer t statistical queries chosen adaptively by a λprogressive analyst so that the error on each query is at most O p K(λ)dq log(t)/n , where K(λ) = O log(1/(1 λ)) log(1/λ) , dq is the dimension of the queries, and n is the size of the data set. |
| Researcher Affiliation | Academia | Tijana Zrnic 1 Moritz Hardt 1 1Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, USA. Correspondence to: Tijana Zrnic <tijana@eecs.berkeley.edu>. |
| Pseudocode | No | The paper describes various algorithms (e.g., Bellman equation, gradient descent) in text and mathematical equations, but it does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information for source code, such as a repository link or an explicit statement about code release. |
| Open Datasets | No | The paper is theoretical and does not describe experiments using specific datasets, therefore no public dataset information is provided. |
| Dataset Splits | No | The paper is theoretical and does not report on experimental data, therefore no dataset split information (training, validation, test) is provided. |
| Hardware Specification | No | The paper does not provide specific hardware details, as it is a theoretical work that does not report on experimental setups requiring hardware. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers, as it is a theoretical paper and does not describe a software implementation for its findings. |
| Experiment Setup | No | The paper is theoretical and does not describe any specific experimental setup details, hyperparameters, or system-level training settings. |