Learning and Adaptive Data Analysis via Maximal Leakage

There has been growing interest in studying connections between generalization error of learning algorithms and information measures. In this work, we generalize a result that employs the maximal leakage, a measure of leakage of information, and explore how this bound can be applied in different scenarios. The main application can be found in bounding the generalization error. Rather than analyzing the expected error, we provide a concentration inequality. In this work, we do not require the assumption of sigma-sub gaussianity and show how our results can be used to retrieve a generalization of the classical bounds in adaptive scenarios (e.g., McDiarmid's inequality for c-sensitive functions, false discovery error control via significance level, etc.).