Sample Complexity for Distributionally Robust Learning under chi-square divergence

Zhengyu Zhou, Weiwei Liu.

Year: 2023, Volume: 24, Issue: 230, Pages: 1−27


This paper investigates the sample complexity of learning a distributionally robust predictor under a particular distributional shift based on $\chi^2$-divergence, which is well known for its computational feasibility and statistical properties. We demonstrate that any hypothesis class $\mathcal{H}$ with finite VC dimension is distributionally robustly learnable. Moreover, we show that when the perturbation size is smaller than a constant, finite VC dimension is also necessary for distributionally robust learning by deriving a lower bound of sample complexity in terms of VC dimension.