Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 38 min ago
PreprintarXiv licencearXiv

High-Arity Rademacher Complexity and Uniform Laws of Large Numbers

  • Aaron Anderson
  • Henry Towsner
Open at sourcePDFDOICite

Abstract

We characterize several properties of higher-arity function classes, specifically finite VCk-dimension, slicewise finite VC-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 VCk-dimension and slicewise finite VC-dimension. These include the preservation of finite VCk-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.

Related

  1. Large fluctuations of extended Rademacher random multiplicative functions
    Haozhe Gou, Max Wenqiang Xu
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryProbabilityarXiv
  2. Off-diagonal Ramsey numbers for 3-uniform tight hypergraph cycles
    Eng Keat Hng
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Graded Betti numbers of graded Möbius algebras of uniform matroids
    Louiza Fouli, Sean Grate, Selvi Kara +5
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. Uniform Intersection Numbers and Subgroup-Based Generating Graphs of Groups
    Projesh Nath Choudhury, Biswaranjan Khanra
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  5. Ordered Ramsey numbers of 3-uniform hypergraphs with bounded weak degeneracy
    Wen Chen, Zihan He, Qizhong Lin +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{anderson2026higharity,
  title = {{High-Arity Rademacher Complexity and Uniform Laws of Large Numbers}},
  author = {Aaron Anderson and Henry Towsner},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.18528},
  eprint = {2610.18528},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.18528},
}
RIS
TY  - UNPB
TI  - High-Arity Rademacher Complexity and Uniform Laws of Large Numbers
AU  - Aaron Anderson
AU  - Henry Towsner
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.18528
UR  - https://arxiv.org/abs/2610.18528
AB  - We characterize several properties of higher-arity function classes, specifically finite VC_k-dimension, slicewise finite VC-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-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.
ER  -