PaperlayerView exact revision on arXiv

Source-linked AI summary

Natural Analysts in Adaptive Data Analysis

Tijana Zrnic, Moritz Hardt

arXiv:1901.11143v2cs.LGmath.STstat.MLstat.TH

TL;DR

Adaptive data analysis has pessimistic generalization guarantees, while a comprehensive class of intermediate, natural analysts has been lacking. The paper models analysts as dynamical systems with progressive or conservative constraints; these classes achieve generalization error essentially independent of query count, unlike arbitrary adversarial analysts.

  • Problem

    Adaptive data analysis permits arbitrary analyst behavior and lacks a comprehensive formalization of intermediate analysts, despite the recognized gap between typical and adversarial analysts.

    Source: §1 · pp. 1–2

  • Method

    The paper models analysts’ knowledge as a hidden state updated by revealed information, then constrains state transitions to define progressive and conservative analyst classes.

    Source: §1.1 · p. 2

  • Results

    Natural analysts achieve generalization error essentially independent of query count, unlike arbitrary adversarial analysts whose error scales polynomially.

    Source: §7 · p. 13

  • Takeaways & Limitations

    The proposed analyst classes also capture iterative algorithms such as value iteration and gradient descent.

    Source: §7 · p. 13

    The truncated-analyst argument does not generally yield time-independent differential-privacy composition because uncertainty in the full analyst’s history can accumulate and make later queries unstable.

    Source: §3.3 · p. 8

Abstract

from arXiv · show

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.

1 Introduction

Adaptive data analysis lacks a comprehensive class of intermediate analysts, leaving generalization guarantees shaped by arbitrary, potentially adversarial behavior. The paper models analysts as dynamical systems and uses constraints on their state transitions to define natural analyst classes and analyze their generalization.

1 Introduction

  • Differential-privacy-based adaptive bounds still depend polynomially on query count, and no comprehensive class of intermediate, non-adversarial analysts had been formalized.The statistical-query model permits future queries to depend arbitrarily on past queries and answers.Source: §1 · pp. 1–2

1.1 Our Contributions

  • The analyst’s knowledge is modeled as a hidden state updated by revealed answers, with queries chosen from that state; constant and unrestricted states recover non-adaptive and fully adaptive analysis.Progressive and conservative analysts impose different control-theoretic constraints on this dynamical model.Source: §1.1 · p. 2
  • Progressive analysts formalize recency bias through contractive state transitions, which have a regularizing effect on generalization.For λ = 1 − 1/t, the bound reduces to the adaptive Hoeffding bound; for constant λ bounded away from 1, it recovers the non-adaptive bound.Source: §1.1 · pp. 2–3
  • Conservative analysts formalize anchoring bias by making state transitions increasingly Lipschitz in new information over time.When η = 1 − 1/t, their bound reduces to a multidimensional generalization of the hard-to-improve adaptive bound.Source: §1.1 · p. 3

1.2 Proof Technique Overview

  • The proof technique truncates each analyst to a time-independent number of adaptive rounds, then uses approximation to transfer the truncated analyst’s generalization properties to the full analyst.With progressiveness or conservatism parameters constant in the number of interactions, the resulting error scales logarithmically with the number of queries.Source: §1.2 · p. 3

2 Analysts as Dynamical Systems

The paper formulates adaptive data analysis as interaction between an analyst and a statistical mechanism over a dataset. The analyst uses a hidden state to encode past interactions, while the mechanism aims to answer accurately and preserve generalization to the underlying distribution.

2.1 Problem Setting

  • A statistical query may be a bounded vector-valued function, equivalent to a set of scalar queries, which accommodates procedures such as gradient descent that request vectors.The data consist of n i.i.d. samples from a distribution, and the mechanism answers analyst queries using access to the dataset.Source: §2.1 · p. 4
  • The analyst’s hidden state is a possibly lossy encoding of past interactions and determines the next query through a measurable function.The transcript comprises prior query-answer pairs, but the analyst accesses it through the state.Source: §2.1 · p. 4
  • The mechanism aims for small generalization error because answering with the dataset’s empirical query values can quickly overfit.The mechanism does not know the underlying distribution, and the paper connects sample accuracy plus differential privacy with generalization.Source: §2.1 · p. 4
  • The analysis assumes analyst histories lie on a discrete grid with coordinate-wise resolution Δ, so sufficiently close histories are semantically identical.The passage motivates this assumption by finite numerical precision in computer-stored transcripts and by analysts using only a few decimal digits.Source: §2.1 · p. 5

3 Progressive Analysts: Motivation and Generalization

Progressive analysts formalize recency-biased adaptivity through state transitions that forget prior information, and the section develops a truncation-based route to generalization guarantees. It also describes optimization examples and limitations of privacy-based and naive transcript truncation approaches.

3 Progressive Analysts: Motivation and Generalization

  • λ-progressive analysts have contractive state transitions; λ=0 yields non-adaptive queries, while λ=1 permits full adaptivity.The parameter λ captures the recency-bias analogy: lower values mean faster forgetting; stable recurrent neural networks are another progressive example.Source: §3 · pp. 5–7
  • Repeated Bellman updates contract history by γ, making value iteration and many dynamic-programming solvers γ-progressive analysts.The example concerns analysts that use learned value estimates to adaptively change their state set.Source: §3 · p. 6

3.1 Truncated Analyst

  • A truncated analyst follows the full analyst’s update maps but receives only its last k answers; its queries have time-independent generalization error.Contractiveness keeps the full and truncated analysts’ histories close; sufficiently large truncation can make them identical, with a time-independent threshold depending on the history-set radius.Source: §3.1 · p. 7, §3.2 · p. 7

3.2 Generalization via Compression

  • n = ˜O(K(λ)dq log(t)/ǫ^2) samples suffice for ǫ-generalization error with high probability, independently of history dimension.Under additional commonly satisfied assumptions, the bound also applies to history sets without finite resolution.Source: §3.2 · p. 8

3.3 Limitations

  • The proof uses rounded, unobscured empirical answers because the truncated analyst generally lacks time-independent differential-privacy composition.Changes in the data can accumulate in the full analyst’s history and eventually yield an unstable query; a time-independent guarantee would require a framework not relying on differential privacy.Source: §3.3 · p. 8
  • Limiting an analyst to the last K transcript pairs does not rule out full adaptivity or guarantee better generalization, regardless of response mechanism.The paper contrasts this naive transcript truncation with its progressive-analyst framework.Source: §3.3 · p. 8

4 Conservative Analysts, Type A: Motivation and Generalization

Type A conservative analysts become progressively less sensitive to new evidence, capturing gradient descent with decaying step sizes. Truncation and differential privacy yield generalization guarantees governed by an effective horizon rather than the full interaction history.

4 Conservative Analysts, Type A: Motivation and Generalization

  • Type A conservatism means state transitions become less sensitive to new evidence over time, and gradient descent with a decreasing step is ηt-conservative.Source: §4 · p. 9
  • The authors connect this conservatism to anchoring: ηt = 0 means complete anchoring and no adaptivity, while slow decay represents a mild anchoring effect.Source: §4 · p. 9
  • The rate of step-size decay determines saturation speed, spanning polynomial schedules and epoch-wise constant-factor learning-rate drops.Source: §4 · p. 9

4.1 Truncated Analyst

  • The Type A truncated analyst sees the first k true answers, then deterministically sets its second input to zero in later rounds.Source: §4.1 · p. 10

4.2 Generalization via Differential Privacy

  • ˜O(K(ηt)dq log(t)/ε²) samples suffice for ε-generalization by a Type A ηt-conservative analyst, with no direct dependence on history dimension.Source: §4.2 · p. 11

5 Conservative Analysts, Type B: Motivation and Generalization

Type B conservative analysts have linear dynamics and histories that saturate despite non-decreasing sensitivity to revealed information. Their truncation and differential-privacy analysis yields generalization guarantees governed by the contraction-dependent effective horizon.

5 Conservative Analysts, Type B: Motivation and Generalization

  • Type B conservatism combines contraction on empirical answers with linear analyst dynamics; it models histories that saturate despite non-decreasing sensitivity.Source: §5 · p. 11
  • Gradient-based methods can saturate even without step decay; for smooth, strongly convex losses, the stated step-size condition is η ≤ 2/(β+µ).Source: §5 · p. 11

5.1 Truncated Analyst

  • The Type B truncated analyst interacts with the mechanism only during the last k rounds, and its history is shown close to the full analyst’s under the Gaussian mechanism.Source: §5.1 · pp. 11–12

5.2 Generalization via Differential Privacy

  • The truncated analyst’s privacy composition depends on truncation depth, yielding a time-independent privacy bound for the full analyst.Source: §5.1 · p. 12, §5.2 · p. 12
  • ˜O(K(λ)dq log(t)/ε²) samples suffice for ε-generalization by a Type B λ-conservative analyst.Source: §5.2 · p. 12

6 Beyond the Discrete Setting

Without discretization, general contraction alone does not prevent progressive and Type A analysts from overfitting as much as fully adaptive analysts. Type B admits a result for continuous hypothesis sets under additional matrix conditions.

6 Beyond the Discrete Setting

  • Without assumptions on H, progressive and nontrivial Type A analysts can overfit as much as fully adaptive analysts.Source: §6 · pp. 12–13
  • Without discretization, Type B admits an efficient accuracy mechanism when each Bt is positive- or negative-definite with minimum absolute eigenvalue bounded below as specified.Source: §6 · p. 13

7 Summary

The paper defines progressive and conservative analysts through control-theoretic constraints on evolving knowledge, capturing both cognitive biases and iterative algorithms. These analysts achieve generalization error essentially independent of query count, unlike arbitrary adversarial analysts, whose error scales polynomially.

7 Summary

  • Progressive and conservative analysts are defined by different control-theoretic constraints on how their knowledge evolves.The categories also model cognitive biases and capture iterative algorithms such as value iteration and gradient descent.Source: §7 · p. 13
  • Their generalization error is essentially independent of query count, unlike the polynomially scaling error of arbitrary adversarial analysts.Source: §7 · p. 13
  • The analysis combines control-theoretic stability with algorithmic stability, a connection the authors identify as worth further study.Source: §7 · p. 13

8 Preliminaries on Differential Privacy

This section reviews differential-privacy properties used throughout the manuscript: post-processing, composition, and the Gaussian mechanism.

8 Preliminaries on Differential Privacy

  • Post-processing an output of a differentially private algorithm with an arbitrary randomized function preserves its privacy parameters.Source: §8 · p. 15
  • Composing two differentially private mechanisms adds their respective privacy parameters under linear composition.Source: §8 · p. 15
  • Strong composition gives a quadratic-style privacy bound for repeated mechanisms, and the paper uses a more convenient bound when α is in [0, 1].The convenient bound uses 2i log(1/β′)α + 2iα² and privacy parameter iβ + β′.Source: §8 · p. 15
  • The Gaussian mechanism’s privacy guarantee is reviewed for independent Gaussian noise added to neighboring data sets’ empirical query answers.The stated guarantee is (√dq/(nσ), β)-differential privacy.Source: §8 · p. 15

9 Progressive Analysts: Proofs

These proofs establish bounds for progressive analysts by combining concentration, truncation, stability, and finite-history arguments. They also show that limiting access to the immediately preceding query-answer pair alone does not prevent arbitrary adaptivity.

9.1 Proof of Lemma 1

  • A fixed-query Hoeffding bound and union bounds over query coordinates and possible answer histories yield a generalization bound when the number of histories is polynomial in n.The proof counts at most A^k d_q possibilities for the relevant answer history.Source: §9.1 · p. 16

9.2 Proof of Lemma 2

  • Progressiveness and Lipschitz state transitions bound the difference between the full analyst’s history and its truncated version.The proof starts from their shared answers and recursively applies the transition-map Lipschitz properties.Source: §9.2 · p. 16

9.3 Proof of Theorem 1

  • Discretizing the history and projecting answers onto a finite grid lets a union bound establish the theorem’s generalization bound.The proof uses the history separation parameter Δ and a grid of projected empirical answers.Source: §9.3 · pp. 16–17

9.4 Proof of Claim 1

  • Even when each round sees only the preceding query-answer pair, a reserved query value can encode the full transcript and permit arbitrary adaptivity.Bijective encodings allow recursive recovery of prior answers and query-answer pairs.Source: §9.4 · p. 17

10 Conservative Analysts, Type A: Proofs

The proofs show how type A conservativeness limits dependence on recent answers and how that restriction supports privacy and generalization bounds. The final theorem uses a truncated Gaussian mechanism and a differential-privacy transfer argument.

10.1 Proof of Lemma 3

  • Once η_t C1 falls below Δ, the analyst’s history no longer depends on the current answer, so later answers can be replaced by zero without changing its history sequence.The proof identifies this cutoff as K(η_t).Source: §10.1 · pp. 17–18

10.2 Proof of Lemma 4

  • After the first k rounds, data-independent constant answers add no privacy cost, so composition bounds the privacy of the history using the first k rounds.The stated bound depends on k and the composition parameters rather than the total number of later rounds.Source: §10.2 · p. 18

10.3 Proof of Proposition 1

  • The proof of Proposition 1 follows directly from Lemmas 3 and 4.Source: §10.3 · p. 18

10.4 Proof of Theorem 2

  • A truncated Gaussian mechanism yields sample accuracy and differential privacy, which the transfer theorem uses to establish a generalization bound.The proof combines a sub-Gaussian tail bound and a union bound with the privacy and sample-accuracy guarantees.Source: §10.4 · p. 18

11 Conservative Analysts, Type B: Proofs

These proofs bound the gap between full and truncated conservative analysts, compose privacy across rounds, and apply those bounds with Gaussian noise to obtain a generalization guarantee.

11.1 Proof of Lemma 5

  • Sharing identical noise at each round lets the proof compare truncated and full analysts; λ-conservatism and bounded H control the recursive discrepancy.The recursive argument also uses that the truncated history is zero before the retained rounds.Source: §11.1 · p. 19

11.2 Proof of Lemma 6

  • Starting from a data-independent zero history, the proof uses linear composition for the first answer and strong composition over the last k private answers to bound history privacy.The stated composed parameters are (2k log(1/β′)α + 2kα^2, kβ + β′).Source: §11.2 · p. 19

11.3 Proof of Proposition 2

  • Distinct histories are separated by Δ, while Lemma 5 bounds truncation error by λ^kD; this supports choosing a truncation level for Proposition 2’s privacy bound.The resulting privacy expression uses K(λ) in the composition parameters.Source: §11.3 · p. 19

11.4 Proof of Theorem 3

  • The Gaussian mechanism is shown to be sample accurate, and its privacy and accuracy guarantees yield ǫ-generalization error with probability at least 1−δ via the transfer theorem.The proof uses the main transfer theorem of Bassily et al. [1].Source: §11.4 · pp. 19–20

12 Beyond the Discrete Setting: Proofs

The proofs construct transcript encodings that remain compatible with progressive or conservative updates, then use Gaussian-noise privacy arguments and a transfer theorem to establish generalization.

12.1 Proof of Proposition 3

  • Interlacing the decimal digits of an answer and history creates an encoding from which both can be perfectly recovered.The proof first contracts values to [0, 1] when necessary.Source: §12.1 · p. 20
  • The constructed λ-progressive and ηt-conservative updates retain the full transcript losslessly, so either analyst can still be fully adaptive.The construction uses interlaced encodings in both cases.Source: §12.1 · p. 20

12.2 Proof of Theorem 4

  • The privacy comparison reduces to independent Gaussian noise by zeroing off-diagonal covariance entries and using a lower bound on the absolute diagonal entries.The simplified histories use independent Gaussian entries with variance at least λ^2 min σ^2.Source: §12.2 · p. 21
  • To obtain the target history-privacy parameters, the proof keeps αξ proportional to ǫ while choosing the other parameters as arbitrarily small constants.This is the stated main requirement for (O(ǫ), O(ǫδ))-differential privacy.Source: §12.2 · p. 22
  • Combining (O(ǫ), O(ǫδ))-differential privacy and sample accuracy through Bassily et al.’s [1] transfer theorem yields ǫ-generalization error with probability at least 1−δ.The proof applies the transfer theorem to the history mechanism.Source: §12.2 · p. 22
Loading 1901.11143v2…