Robustness Implies Generalization via Data-Dependent Generalization Bounds
This paper proves that robustness implies generalization via data-dependent
generalization bounds. As a result, robustness and generalization are shown to
be connected closely in a data-dependent manner. Our bounds improve previous
bounds in two directions, to solve an open problem that has seen little
development since 2010. The first is to reduce the dependence on the covering
number. The second is to remove the dependence on the hypothesis space. We
present several examples, including ones for lasso and deep learning, in which
our bounds are provably preferable. The experiments on real-world data and
theoretical models demonstrate near-exponential improvements in various
situations. To achieve these improvements, we do not require additional
assumptions on the unknown distribution; instead, we only incorporate an
observable and computable property of the training samples. A key technical
innovation is an improved concentration bound for multinomial random variables
that is of independent interest beyond robustness and generalization.