Sample complexity of adaptive statistical queries

An analyst may choose each statistical query after seeing the earlier answers. The problem asks how many independent samples a mechanism needs to answer all the queries accurately despite that feedback.

Why it matters and what counts as progress

Why it matters: The result improves the leading sample term and closes a separate space gap for frequency-moment estimation when future updates can depend on earlier answers.

What counts as progress: Sharper sample bounds should state how accuracy, failure probability, query count and domain assumptions enter. A resource guarantee should identify the model it measures.

How the problem developed

  1. 2014 · Development [1]

    Cynthia Dwork and colleagues Established a connection between stability and statistical validity for adaptively chosen analyses.

  2. 13 Nov 2026 · Algorithm [2][3][4]

    Gemini 4 Argon Gave a statistical query mechanism with no log⁡k\log k factor on the leading k\sqrt{k} term and a related robust streaming algorithm.

AI contribution

Adaptive Data Analysis with α−2\alpha ^{-2} polylog Overhead, Interval Validation, and Adversarially Robust Turnstile F2F_{2} Estimation in ε−2\varepsilon ^{-2} polylog Bits

The Gemini manuscript gives a mechanism that answers k adaptively chosen bounded statistical queries over any measurable domain. Its leading sample term is proportional to k/α\sqrt{k}/\alpha with confidence-dependent factors and no log⁡k\log k multiplier. The same manuscript supplies a finite-precision interval validator and a single-pass algorithm that estimates the second frequency moment after every integer turnstile update using ε−2\varepsilon ^{-2} times a polylogarithmic number of bits.

AI involvementAI-autonomous
ImportanceNotable
Technical verificationFormal (Lean)
Human understandingFew
Paper date:

Sources

  1. Preserving statistical validity in adaptive data analysis
  2. Original manuscript
  3. Google’s account of the standalone Gemini proof
  4. Lean archive and theorem correspondence
  5. Companion paper’s AI methodology
Publication history