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

arXiv: https://arxiv.org/abs/2608.04686 · HTML: https://mlsanity.com/paper/2608.04686/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 20 references that are in the map.
- First posted on arXiv 5 Aug 2026.

## Builds on (most cited first, 3 of 3)

- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)

## Abstract (arXiv)

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.