Ligett, Katrina and Shenfeld, Moshe (2019) A necessary and sufficient stability notion for adaptive generalization. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20190626-101449888
![]() |
PDF
- Submitted Version
See Usage Policy. 334kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190626-101449888
Abstract
We introduce a new notion of the stability of computations, which holds under post-processing and adaptive composition, and show that the notion is both necessary and sufficient to ensure generalization in the face of adaptivity, for any computations that respond to bounded-sensitivity linear queries while providing accuracy with respect to the data sample set. The stability notion is based on quantifying the effect of observing a computation's outputs on the posterior over the data sample elements. We show a separation between this stability notion and previously studied notions.
Item Type: | Report or Paper (Discussion Paper) | ||||||
---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||
ORCID: |
| ||||||
Record Number: | CaltechAUTHORS:20190626-101449888 | ||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20190626-101449888 | ||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
ID Code: | 96732 | ||||||
Collection: | CaltechAUTHORS | ||||||
Deposited By: | Tony Diaz | ||||||
Deposited On: | 26 Jun 2019 17:22 | ||||||
Last Modified: | 03 Oct 2019 21:24 |
Repository Staff Only: item control page