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

arXiv:2608.04686v1 Announce Type: new Abstract: 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 rhogeq 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 arepsilonin(0,1) and confidence eltain(0,1), their respective orders are [ max!left{frac{1}{arepsilon}, frac{rho^{frac 1{k-1}}}{arepsilon^{k_star}} right}dot(d+log elta^{-1}) qquadext{and}qquad max!left{frac{1}{arepsilon^2}, frac{rho^{frac1{k-1}}}{arepsilon^{k_staree 2}} right}dot(d+log elta^{-1}), ] where k_star={k}/{(k-1)}. For every fixed rho>0, robustness changes the realizable arepsilon-dependence from arepsilon^{-1} to arepsilon^{-k_star} as arepsilonownarrow0. In the agnostic case, for 11, close its upper--lower gaps, and recover standard PAC learning rates as rhoo0, unlike previous bounds that fail to interpolate correctly in this limit.

Source: arXiv cs.LG | 2026-08-06