Adaptive Learning with Robust Generalization Guarantees
  The traditional notion of generalization---i.e., learning a hypothesis whose
empirical error is close to its true error---is surprisingly brittle. As has
recently been noted in [DFH+15b], even if several algorithms have this
guarantee in isolation, the guarantee need not hold if the algorithms are
composed adaptively. In this paper, we study three notions of
generalization---increasing in strength---that are robust to postprocessing and
amenable to adaptive composition, and examine the relationships between them.
We call the weakest such notion Robust Generalization. A second, intermediate,
notion is the stability guarantee known as differential privacy. The strongest
guarantee we consider we call Perfect Generalization. We prove that every
hypothesis class that is PAC learnable is also PAC learnable in a robustly
generalizing fashion, with almost the same sample complexity. It was previously
known that differentially private algorithms satisfy robust generalization. In
this paper, we show that robust generalization is a strictly weaker concept,
and that there is a learning task that can be carried out subject to robust
generalization guarantees, yet cannot be carried out subject to differential
privacy. We also show that perfect generalization is a strictly stronger
guarantee than differential privacy, but that, nevertheless, many learning
tasks can be carried out subject to the guarantees of perfect generalization.
