Download

Abstract

We characterize several properties of higher-arity function classes, specifically finite VC$_k$-dimension, slicewise finite VC$_k$-dimension, and finite slicewise Littlestone dimension, in terms of generalizations of Rademacher complexity.

These characterizations sets up simple new proofs of several results on finite VC$_k$-dimension and slicewise finite VC$_k$-dimension. These include the preservation of finite VC$_k$-dimension under taking expectations and uniform law of large numbers statements for both properties. All of these results apply naturally to real-valued function classes as well as boolean-valued classes.

We also prove a new adversarial uniform law of large numbers for classes with finite slicewise Littlestone dimension.

Citation

Aaron Anderson, Henry Towsner. 2026. “High-Arity Rademacher Complexity and Uniform Laws of Large Numbers.” arXiv preprint, https://arxiv.org/abs/2610.18528.

@unpublished{higharityrad,
  title={High-Arity Rademacher Complexity and Uniform Laws of Large Numbers}, 
      author={Aaron Anderson and Henry Towsner},
      year={2026},
      eprint={2610.18528},
      archivePrefix={arXiv},
      primaryClass={math.CO},
      url={https://arxiv.org/abs/2610.18528}, 
      note = {Preprint}
}