Abstract
We introduce a new notion of the stability of computations, 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.
Joint work with Katrina Ligett (Hebrew University).