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

arXiv:2608.04686 · cs.LG · Submitted 2026-08-05 · Read on arXiv

Elad Aigner-Horev, Daniel Rosenberg, Roi Weiss

cs.LG

Submitted: 2026-08-05

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Sample Complexity — 40× in this paper · explained in 20 episodes
• Inflation — 27× in this paper · explained in 2 episodes
• Robustness — 13× in this paper · explained in 6 episodes
• Accuracy — 12× in this paper · explained in 1 episode
• Monotonicity — 4× in this paper · explained in 2 episodes
• VC Dimension — 4× in this paper · explained in 2 episodes
• Consistency — 3× in this paper · explained in 3 episodes
• Self-Consistency — 3× in this paper · explained in 3 episodes
• Covariate Shift — 2× in this paper · explained in 3 episodes
• Chance Constraints — 1× in this paper · explained in 2 episodes
• Domain Adaptation — 1× in this paper · explained in 5 episodes
• Editor — 1× in this paper · explained in 2 episodes
• Goodness-of-Fit Tests — 1× in this paper · explained in 2 episodes
• Kullback–Leibler Divergence — 1× in this paper · explained in 2 episodes
• Localization — 1× in this paper · explained in 2 episodes
• Loss Function — 1× in this paper · explained in 2 episodes
• Papers — 1× in this paper · explained in 3 episodes

Related papers

• Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
• AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
• Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
• Convergence issues in Relational Concept Analysis based on AOC-posets
• Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
• Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks