Uniform Laws of Large Numbers in Product Spaces

Ron Holzman, Shay Moran, Alexander Shlimovich
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3224-3279, 2026.

Abstract

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 \emph{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 \emph{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 \emph{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 an estimator that departs substantially from the standard empirical mean estimator and exhibits a 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-holzman26a, title = {Uniform Laws of Large Numbers in Product Spaces}, author = {Holzman, Ron and Moran, Shay and Shlimovich, Alexander}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {3224--3279}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/holzman26a/holzman26a.pdf}, url = {https://proceedings.mlr.press/v336/holzman26a.html}, abstract = {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 \emph{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 \emph{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 \emph{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 an estimator that departs substantially from the standard empirical mean estimator and exhibits a 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.} }
Endnote
%0 Conference Paper %T Uniform Laws of Large Numbers in Product Spaces %A Ron Holzman %A Shay Moran %A Alexander Shlimovich %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-holzman26a %I PMLR %P 3224--3279 %U https://proceedings.mlr.press/v336/holzman26a.html %V 336 %X 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 \emph{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 \emph{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 \emph{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 an estimator that departs substantially from the standard empirical mean estimator and exhibits a 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.
APA
Holzman, R., Moran, S. & Shlimovich, A.. (2026). Uniform Laws of Large Numbers in Product Spaces. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:3224-3279 Available from https://proceedings.mlr.press/v336/holzman26a.html.

Related Material