Timezone: »

 
Poster
A Necessary and Sufficient Stability Notion for Adaptive Generalization
Moshe Shenfeld · Katrina Ligett

Wed Dec 11 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #2
in Algorithms -- Adaptive Data Analysis »

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.

Keywords: Learning Theory · Adaptive Data Analysis · Algorithms · Applications -> Privacy, Anonymity, and Security; Theory
[ Paper]  [ Slides] 

Author Information

Moshe Shenfeld (Hebrew University of Jerusalem)
Katrina Ligett (Hebrew University)

More from the Same Authors