Generalization for Adaptively-chosen Estimators via Stable Median
Generalization for Adaptively-chosen Estimators via Stable Median
复制标题
通过稳定中位数自适应选择估计量的泛化
DOI：
10.48550/arxiv.2210.13386
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
T. Steinke
中科院分区：
文献类型：
--
作者：
V. Feldman;T. Steinke
通常使用数据集以一种自适应方式执行多个统计分析，其中每个分析可能取决于同一数据集对先前分析的结果。标准统计保证并未考虑这些依赖性，并且关于如何在自适应环境中避免过度拟合和错误发现知之甚少。我们考虑了此问题的自然形式化，在该问题中，目标是设计一种算法，鉴于来自未知分布的i.i.d.〜样品的数量有限，可以回答有关该分布的适应性选择的查询。
我们提出了一种算法，该算法估计了$ k $ intunaptry自适应选择的实价估计器的期望，该估计估计估计量使用多个样本将其缩放为$ \ sqrt {k} $。我们的算法给出的答案本质上是准确的，就像使用新鲜样品评估每个估计器一样。相比之下，先前的工作产生的错误可以确保每个估计器的最差敏感性尺度。我们还提供了一种算法的版本，该版本可用于验证此类查询的答案，在这种查询中，样本复杂性在对数$ k $的数量（如可重复使用的保留技术中）。
我们的算法基于一种简单的近似中位数算法，该算法满足了差异隐私的强大稳定性保证。我们的技术为分析差异私有算法的概括提供了一种新方法。
Datasets are often reused to perform multiple statistical analyses in an adaptive way, in which each analysis may depend on the outcomes of previous analyses on the same dataset. Standard statistical guarantees do not account for these dependencies and little is known about how to provably avoid overfitting and false discovery in the adaptive setting. We consider a natural formalization of this problem in which the goal is to design an algorithm that, given a limited number of i.i.d.~samples from an unknown distribution, can answer adaptively-chosen queries about that distribution.
We present an algorithm that estimates the expectations of $k$ arbitrary adaptively-chosen real-valued estimators using a number of samples that scales as $\sqrt{k}$. The answers given by our algorithm are essentially as accurate as if fresh samples were used to evaluate each estimator. In contrast, prior work yields error guarantees that scale with the worst-case sensitivity of each estimator. We also give a version of our algorithm that can be used to verify answers to such queries where the sample complexity depends logarithmically on the number of queries $k$ (as in the reusable holdout technique).
Our algorithm is based on a simple approximate median algorithm that satisfies the strong stability guarantees of differential privacy. Our techniques provide a new approach for analyzing the generalization guarantees of differentially private algorithms.