A Rate Separation for Agnostic Direct Sums
Mihir More, Aritra Das, Debayan Gupta
cs.LG
Submitted: 2026-08-07
Updated: 2026-08-10
License: http://creativecommons.org/licenses/by/4.0/
The gist: Hanneke, Moran, and Waknine asked how the agnostic PAC learning curve of the direct sum C r depends on the single-instance learning curve (n C) and on r.
Terminology
Abstract
Hanneke, Moran, and Waknine asked how the agnostic PAC learning curve of the direct sum C r depends on the single-instance learning curve (n C) and on r. We show that the single-instance learning rate does not determine the direct-sum rate. Let be the class of the two constant binary functions and let consist of the zero function and the identity function. Both classes have agnostic learning curve of order n-1/2.
Sources
- Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
- The Optimal Sample Complexity of Multiclass and List Learning
- Direct sum theorems beyond query complexity
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