CaltechAUTHORS
  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) https://resolver.caltech.edu/CaltechAUTHORS:20190626-101449888

[img] PDF - Submitted Version
See Usage Policy.

327Kb

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:
URLURL TypeDescription
http://arxiv.org/abs/1906.00930arXivDiscussion Paper
ORCID:
AuthorORCID
Ligett, Katrina0000-0003-2780-6656
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