The Everlasting Database: Statistical Validity at a Fair Price
The problem of handling adaptivity in data analysis, intentional or not, permeates a variety of fields, including test-set overfitting in ML challenges and the accumulation of invalid scientific discoveries. We propose a mechanism for answering an arbitrarily long sequence of potentially adaptive statistical queries, by charging a price for each query and using the proceeds to collect additional samples. Crucially, we guarantee statistical validity without any assumptions on how the queries are generated. We also ensure with high probability that the cost for $M$ non-adaptive queries is $O(\log M)$, while the cost to a potentially adaptive user who makes $M$ queries that do not depend on any others is $O(\sqrt{M})$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Clearing price distributions in call auctions
We propose a model for price formation in financial markets based on clearing of a standard call auction with random orders, and verify its validity for prediction of the daily closing price distribution statistically. T…
Private Truly-Everlasting Robust-Prediction
Private Everlasting Prediction (PEP), recently introduced by Naor et al. [2023], is a model for differentially private learning in which the learner never publicly releases a hypothesis. Instead, it provides black-box ac…
PredictionCapuchin: Causal Database Repair for Algorithmic Fairness
Fairness is increasingly recognized as a critical component of machine learning systems. However, it is the underlying data on which these systems are trained that often reflect discrimination, suggesting a database repa…
FairnessA Discussion of Discrimination and Fairness in Insurance Pricing
Indirect discrimination is an issue of major concern in algorithmic models. This is particularly the case in insurance pricing where protected policyholder characteristics are not allowed to be used for insurance pricing…
FairnessReview of Mathematical frameworks for Fairness in Machine Learning
A review of the main fairness definitions and fair learning methodologies proposed in the literature over the last years is presented from a mathematical point of view. Following our independence-based approach, we consi…
BIG-bench Machine LearningFairnessregression