Uniform Laws of Large Numbers in Product Spaces
This work addresses foundational theoretical problems in statistical learning theory, particularly for researchers in VC theory and high-dimensional probability, by extending uniform convergence results to product spaces with practical distributional assumptions, though it is incremental in building upon existing VC theory.
The paper tackles the problem of establishing uniform laws of large numbers in cartesian product spaces under distributional assumptions, showing that such laws hold if and only if the linear VC dimension is finite, which can be arbitrarily smaller than the classical VC dimension, as demonstrated with convex sets in ℝ^d having linear VC dimension 2 versus infinite classical VC dimension for d≥2.
Uniform laws of large numbers form a cornerstone of Vapnik--Chervonenkis theory, where they are characterized by the finiteness of the VC dimension. In this work, we study uniform convergence phenomena in cartesian product spaces, under assumptions on the underlying distribution that are compatible with the product structure. Specifically, we assume that the distribution is absolutely continuous with respect to the product of its marginals, a condition that captures many natural settings, including product distributions, sparse mixtures of product distributions, distributions with low mutual information, and more. We show that, under this assumption, a uniform law of large numbers holds for a family of events if and only if the linear VC dimension of the family is finite. The linear VC dimension is defined as the maximum size of a shattered set that lies on an axis-parallel line, namely, a set of vectors that agree on all but at most one coordinate. This dimension is always at most the classical VC dimension, yet it can be arbitrarily smaller. For instance, the family of convex sets in $\mathbb{R}^d$ has linear VC dimension $2$, while its VC dimension is infinite already for $d\ge 2$. Our proofs rely on estimator that departs substantially from the standard empirical mean estimator and exhibits more intricate structure. We show that such deviations from the standard empirical mean estimator are unavoidable in this setting. Throughout the paper, we propose several open questions, with a particular focus on quantitative sample complexity bounds.