Adaptive Learning with Robust Generalization Guarantees

By Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, Zhiwei Steven Wu. 2016

63 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Differential Privacy for Growing Databases (2018, neutral): “A recent line of work [DFH + 15, CLN + 16, BNS + 16] showed deep connections between diﬀerential privacy and adaptive data analysis of a static database.”
Online Learning via the Differential Privacy Lens (2017, unknown): “For example, the DP lens has been used successfully in designing coalition-proof mechanisms [25] and preventing false discovery in statistical analysis [10, 13, 17, 28].”
Max-Information, Differential Privacy, and Post-selection Hypothesis Testing (2016, methodology): “[24] give a third method—compression schemes—which can also guarantee validity in adaptive data analysis in the context of learning.”
The Role of Interactivity in Local Differential Privacy (2019, background): “y (in which the input may be permuted before used in the protocol) [4, 21], and hence the distribution on transcripts would be almost unchanged even if the entire dataset was resampled i.i.d. from D. [13, 28]. Thus, for such protocols, the transcript distribution is governed by the data distribution”
A New Class of Private Chi-Square Tests (2016, background): “There have been several follow up works [9, 4, 1] that improve and extend the connection between differential privacy and generalization guarantees in adaptive data analysis.”
The Role of Differential Privacy in GDPR Compliance (2018, background): “This guarantee also provides strong generalization guarantees for differentially private algorithms, which have also been observed in other machine learning applications [4, 5].”