Natural Analysts in Adaptive Data Analysis
  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.
