Published June 26, 2019
| Submitted
Report
Open
A necessary and sufficient stability notion for adaptive generalization
- Creators
- Ligett, Katrina
- Shenfeld, Moshe
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.
Attached Files
Submitted - 1906.00930.pdf
Files
1906.00930.pdf
Files
(334.9 kB)
Name | Size | Download all |
---|---|---|
md5:02fabb7f117cee2567030fdf7e9d2a67
|
334.9 kB | Preview Download |
Additional details
- Eprint ID
- 96732
- Resolver ID
- CaltechAUTHORS:20190626-101449888
- Created
-
2019-06-26Created from EPrint's datestamp field
- Updated
-
2023-06-02Created from EPrint's last_modified field