A Caltech Library Service

A necessary and sufficient stability notion for adaptive generalization

Ligett, Katrina and Shenfeld, Moshe (2019) A necessary and sufficient stability notion for adaptive generalization. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription Paper
Ligett, Katrina0000-0003-2780-6656
Record Number:CaltechAUTHORS:20190626-101449888
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96732
Deposited By: Tony Diaz
Deposited On:26 Jun 2019 17:22
Last Modified:03 Oct 2019 21:24

Repository Staff Only: item control page