Generalization in the Face of Adaptivity: A Bayesian Perspective
Authors: Moshe Shenfeld, Katrina Ligett
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In the present work, we prove the following new and better generalization guarantees for simple Gaussian noise-addition algorithms: Theorem 1.1 (Informal versions of main theorems). With probability > 1 δ, the error of the responses produced by a mechanism which only adds Gaussian noise to the empirical values of the queries it receives is bounded by , even after responding to k adaptively chosen queries, if the range of the queries is bounded by , their variance is bounded by σ2, and the size of the dataset n = (Theorem 5.1), or the queries are σ2-sub-Gaussian and the size of the dataset n = (Theorem 5.3). This paper focuses on proving theoretical guarantees and theorems related to generalization in adaptive data analysis, primarily through mathematical derivations and characterizations. It presents theorems (e.g., Theorem 1.1, 3.4, 4.4, 4.6, 5.1, 5.3) and lemmas (e.g., 3.1, 3.2, 3.5, 4.3, 4.5) which are characteristic of theoretical computer science or mathematics papers. |
| Researcher Affiliation | Academia | Moshe Shenfeld Department of Computer Science The Hebrew University of Jerusalem moshe.shenfeld@mail.huji.ac.il Katrina Ligett Department of Computer Science Federmann Center for the Study of Rationality The Hebrew University of Jerusalem katrina@cs.huji.ac.il |
| Pseudocode | No | The paper describes algorithms (like the Gaussian mechanism) verbally and mathematically, but it does not include any formal pseudocode blocks or algorithms labeled as such. |
| Open Source Code | No | The paper does not contain any statement about releasing source code, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper describes a theoretical framework and does not conduct experiments on specific datasets. Therefore, it does not mention public dataset availability. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets that would require training, validation, or test splits. |
| Hardware Specification | No | This is a theoretical paper presenting mathematical proofs and analyses. It does not describe any computational experiments or hardware used. |
| Software Dependencies | No | This paper is theoretical and focuses on mathematical proofs and definitions. It does not describe any software implementation or dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical, presenting mathematical proofs and analyses rather than empirical experiments. Therefore, it does not include details on an experimental setup, hyperparameters, or training configurations. |