Natural Analysts in Adaptive Data Analysis

By Tijana Zrnic, Moritz Hardt. 2019

17 citations recorded by the source corpus.

Adaptive data analysis is frequently criticized for its pessimistic generalization guarantees. The source of these pessimistic bounds is a model that permits arbitrary, possibly adversarial analysts that optimally use information to bias results. While being a central issue in the field, still lacking are notions of natural analysts that allow for more optimistic bounds faithful to the reality that typical analysts aren't adversarial. 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.

Subfields: Artificial Intelligence, Statistics and Probability, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Natural Language Processing

Citations in the corpus

The Effect of Natural Distribution Shift on Question Answering Models (2020, background): “A number of works have proffered explanations for why adaptive overﬁtting does not occur in machine learning (Blum & Hardt, 2015; Mania et al., 2019; Feldman et al., 2019; Zrnic & Hardt, 2019).”
A Meta-Analysis of Overfitting in Machine Learning (2019, background): “The adaptive data analysis literature [6, 17] provides a range of theoretical explanations for how the common machine learning workﬂow may implicitly mitigate overﬁtting [3, 8, 12, 23].”
Model Similarity Mitigates Test Set Overuse (2019, background): “Zrnic and Hardt [21] offered improved guarantees for adaptive analysts that satisfy natural assumptions, e.g. the analyst is unable to arbitrarily use information from queries asked far in the past.”
Are We Learning Yet? A Meta Review of Evaluation Failures Across Machine Learning (2021, background): “An active line of research investigates the question of overﬁtting from test set reuse, also known as adaptive overﬁtting [5, 9, 14, 37, 42, 91, 175].”