Rademacher Complexity for Distributionally Robust Learning

The goal of distributionally robust learning is to learn models capable of performing well against distributional shifts, such as latent heterogeneous subpopulations, unknown covariate shifts, or unmodeled temporal effects. Recently, Duchi and Namkoong (2021) have proven an upper bound for the excess risk of distributionally robust learning through the lens of covering number argument. However, there are situations where the covering argument fails. This motivates us to study the generalization bound through the lens of Rademacher complexity. More specifically, we consider the Cressie-Read divergence \cite{Cressie1984}, $fk(t)\propto t^k-1$. Our theoretical results indicate that the excess risk is of the order $OP(n^{-\frac{1}{2k*}})$, where $k*=\frac{k}{k-1}$. The decay rate of the excess risk increases with increasing $k$. As illustrative examples, we consider three learning settings: 1) linear classifier; 2) Gaussian reproducing kernel Hilbert space; 3) one-hidden-layer networks. The empirical results validate our theoretical findings.