NeurIPS 2019poster17 citations
A Necessary and Sufficient Stability Notion for Adaptive Generalization
Moshe Shenfeld, Katrina Ligett
Abstract
We introduce a new notion of the stability of computations, which holds under post-processing and adaptive composition. We 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 notion and observe that all differentially private algorithms also satisfy this notion.
BibTeX
@inproceedings{NEURIPS2019_c5df4f4e,
author = {Shenfeld, Moshe and Ligett, Katrina},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {A Necessary and Sufficient Stability Notion for Adaptive Generalization},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/c5df4f4eabf1cbcfeb50fbbf97c5289f-Paper.pdf},
volume = {32},
year = {2019}
}