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

This paper investigates the sample complexity of distributionally robust PAC learning for the 0–1 loss. Specifically, the authors examine how adversarial perturbations of the data distribution, constrained by Cressie–Read divergences of order k > 1 and radius ρ, affect the number of samples required to achieve a target accuracy. The study aims to close existing gaps in the literature and provide a unified framework that recovers classical PAC learning rates as the robustness radius ρ approaches zero.

The authors utilize the scalar reduction of robust 0–1 risk to ordinary classification error. By analyzing the Cressie–Read robust-risk map directly, they avoid the limitations of previous methods that relied on empirical-process control after dual reformulation. This approach allows them to capture the interaction between the statistical estimation of classification error and its amplification by robustness. They derive both realizable and agnostic sample-complexity bounds, characterizing the dependence on the VC dimension d, the accuracy ε, and the divergence order k.

The study establishes that for a fixed robustness radius ρ > 0, the sample complexity is significantly altered by the divergence order k. In the realizable setting, the ε-dependence shifts from ε⁻¹ to ε⁻ᵏ⋆ (where k⋆ = k/(k-1)). In the agnostic setting, the transition is more nuanced: for 1 < k < 2, the dependence shifts from ε⁻² to ε⁻ᵏ⋆, while for k ≥ 2, the exponent remains the classical 2, albeit with a non-trivial dependence on ρ. The authors demonstrate that ordinary empirical risk minimization (ERM) is sufficient to achieve these optimal rates up to logarithmic factors, effectively closing the gaps found in prior research on χ²-divergences.