Metraipolis › archive › dc_4958e224af63
The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences — arXiv:2608.04686
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.04686
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T11:34:54.127Z
- SHA-256 of the archived text
82f35f218a52687ee6c3fd400e9a0a4b892b0eeb7fec428e57fc047b42556e7a- Stable URL of this page
https://metraipolis.com/documento/dc_4958e224af63
How to cite
The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences — arXiv:2608.04686 — arXiv (en), https://arxiv.org/abs/2608.04686 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4958e224af63 (Metraipolis archive dc_4958e224af63, sha256 82f35f218a52687ee6c3fd400e9a0a4b892b0eeb7fec428e57fc047b42556e7a)
BibTeX
@misc{dc4958e224af63,
title = {The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences — arXiv:2608.04686},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.04686},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4958e224af63; sha256 82f35f218a52687ee6c3fd400e9a0a4b892b0eeb7fec428e57fc047b42556e7a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.04686. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\rho\geq 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\in(0,1)$ and confidence $\delta\in(0,1)$, their respective orders are \[ \max\!\left\{\frac{1}{\varepsilon}, \frac{\rho^{\frac 1{k-1}}}{\varepsilon^{k_\star}} \right\}\cdot(d+\log \delta^{-1}) \qquad\text{and}\qquad \max\!\left\{\frac{1}{\varepsilon^2}, \frac{\rho^{\frac1{k-1}}}{\varepsilon^{k_\star\vee 2}} \right\}\cdot(d+\log \delta^{-1}), \] where $k_\star={k}/{(k-1)}$. For every fixed $\rho>0$, robustness changes the realizable $\varepsilon$-dependence from $\varepsilon^{-1}$ to $\varepsilon^{-k_\star}$ as $\varepsilon\downarrow0$. In the agnostic case, for $1<k<2$, robustness changes the $\varepsilon$-dependence from $\varepsilon^{-2}$ to $\varepsilon^{-k_\star}$, whereas for $k\geq2$ the exponent remains the classical $2$, with nontrivial $\rho$-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 $\chi^2$-divergence case to every Cressie--Read order $k>1$, close its upper--lower gaps, and recover standard PAC learning rates as $\rho\to0$, unlike previous bounds that fail to interpolate correctly in this limit.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-06 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2608.04686 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T11:24:48.792Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).