High-Arity Rademacher Complexity and Uniform Laws of Large Numbers

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