aiqbench analysis
This research refines theoretical bounds on distributionally robust PAC learning by analyzing how Cressie-Read divergences alter sample complexity scaling for $0$-$1$ loss functions. The study successfully bridges gaps between upper and lower bounds, demonstrating that standard empirical risk minimization achieves these tight rates while correctly recovering classical limits as the perturbation radius vanishes. For researchers in statistical learning theory, this work clarifies the precise trade-offs between model robustness and data efficiency under specific divergence constraints.
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 $\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 $11$, 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.
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 $\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.
Machine Learning (cs.LG)
arXiv:2608.04686 [cs.LG]
(or arXiv:2608.04686v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2608.04686 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 298 words
