Research map / Learning theory and algorithms / Prediction and decision losses
The Everlasting Database: Statistical Validity at a Fair Price
Blake E Woodworth, Vitaly Feldman, Saharon Rosset, Nati Srebro
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Charge per query and use the revenue to purchase additional samples across rounds | EverlastingValidation · Arbitrary adaptive statistical queries | answer accuracy: 1 - \frac{\beta}{2} | Improved |
| Use a decreasing low price for queries and charge a high price when a query prematurely ends a round | EverlastingValidation · M non-adaptive queries | total cost: \frac{96}{\tau^2}\parens{1 + \ln(M)} | Improved |
| Use ValidationRound with truncated Gaussian noise and a check comparing empirical means on two datasets | EverlastingValidation · M autonomous adaptive queries | total cost: 1890\sqrt{M}\ln^2\parens{16M^2/\beta}/\tau^2 | Improved |
| Replace ValidationRound with Thresholdout and tune the tradeoff parameter p | EverlastingTO · Non-adaptive and potentially adaptive queries | total cost: O\parens{\ln^{1/p}(M) + B^{\frac{1}{2-3p}}} | Mixed |
Closest papers by meaning
- Adaptive Data Analysis for Growing Data (NeurIPS 2025 · similarity 0.89)
- Tight Bounds for Answering Adaptively Chosen Concentrated Queries (NeurIPS 2025 · similarity 0.87)
- Efficient Adaptive Data Analysis over Dense Data Distributions (NeurIPS 2026 · similarity 0.84)
- Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries (ICML 2025 · similarity 0.83)
- Adaptive Data Optimization: Dynamic Sample Selection with Scaling Laws (ICLR 2025 · similarity 0.83)
- Clustering with Non-adaptive Subset Queries (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
