The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences

We study distributionally robust PAC learning for the 0--1-loss, where adversarial perturbations of the data distribution are constrained by a Cressie--Read divergence of order k>1 and radius ρ≥ 0. For hypothesis classes with VC dimension d, we establish realizable and agnostic sample-complexity bounds tight up to constant and logarithmic factors, respectively; ordinary empirical risk minimization attains both rates up to logarithmic factors. For target accuracy varepsilon∈(0,1) and confidence δ∈(0,1), their respective orders are [ max!leftfrac1varepsilon, fracρ^frac 1k-1varepsilonk_star right·(d+log δ-1) qquadandqquad max!leftfrac1varepsilon2, fracρ^frac1k-1varepsilonk_starvee 2 right·(d+log δ-1), ] where k_star=k/(k-1). For every fixed ρ>0, robustness changes the realizable varepsilon-dependence from varepsilon-1 to varepsilon-k_star as varepsilondownarrow0. In the agnostic case, for 1<k<2, robustness changes the varepsilon-dependence from varepsilon-2 to varepsilon-k_star, whereas for k≥2 the exponent remains the classical 2, with nontrivial ρ-dependence. Building on the known scalar reduction of robust 0--1 risk to ordinary classification error, our analysis reveals a scale-sensitive interaction between the statistical estimation of classification error and its amplification by robustness, sharply explaining the transition in the agnostic rate. We extend the previously studied chi2-divergence case to every Cressie--Read order k>1, close its upper--lower gaps, and recover standard PAC learning rates as ρ→0, unlike previous bounds that fail to interpolate correctly in this limit.