Uniform Laws of Large Numbers in Product Spaces

• URL: http://arxiv.org/abs/2603.24493v1
• Date: Wed, 25 Mar 2026 16:36:09 GMT
• Title: Uniform Laws of Large Numbers in Product Spaces
• Abstract summary: We study uniform convergence phenomena in cartesian product spaces.<n>We show that 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.
• Score: 60.22626971185653
• License: http://creativecommons.org/licenses/by/4.0/
• 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 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.

Related papers

• Dimension Reduction for Curves: Simplified and Generalized [56.23281156053955]
  We revisit random projections for reducing the dimension of high-dimensional polygonal curves.<n>We give a simplified proof of the known $O(varepsilon-2log(nm))$ bound on the target dimension of a random projection.<n>Our proof is based on the concept of sparse oblivious subspace embeddings.
  arXiv  Detail & Related papers  (2026-07-03T08:48:35Z)
• Representational Capacity: Geometric Limits on Feature Representation in Transformer Language Models [51.56484100374058]
  We develop a framework for estimating how many near-orthogonal directions a model can support.<n>Applying this metric across dozens of open-source models reveals two classes: models with high $varepsilon$ whose embeddings lack near-orthogonal structure, and models with low $varepsilon$ that maintain it.
  arXiv  Detail & Related papers  (2026-06-01T18:28:56Z)
• Dimension-Independent Convergence of Underdamped Langevin Monte Carlo in KL Divergence [50.719298242863744]
  Underdamped Langevin dynamics (ULD) is a widely-used sampler for Gibbs distributions $propto e-V$.<n>We prove the first dimension-free KL divergence bounds for discretized ULD.
  arXiv  Detail & Related papers  (2026-03-02T22:14:38Z)
• Stronger Welch Bounds and Optimal Approximate $k$-Designs [0.13048920509133805]
  A fundamental question asks how uniformly finite sets of pure quantum states can be distributed in a Hilbert space.<n>Welch bounds address this question, and are saturated by $k$-designs, i.e. sets of states reproducing the $k$-th Haar moments.<n>We derive strengthened Welch-type inequalities that remain sharp in this regime by exploiting rank constraints from partial transposition and spectral properties of the partially transposed Haar moment operator.
  arXiv  Detail & Related papers  (2026-02-13T17:05:26Z)
• On consistent estimation of dimension values [45.52331418900137]
  A problem of estimating from a random sample of points, the dimension of a compact subset $S$ of the Euclidean space is considered.<n>We focus on three notions: the Minkowski dimension, the correlation dimension and the concept of pointwise dimension.<n>In particular, we explore the case in which the true volume function $V(r)$ of the target set $S$ is a on some interval starting at zero.
  arXiv  Detail & Related papers  (2024-12-18T14:40:37Z)
• Linear Convergence of Diffusion Models Under the Manifold Hypothesis [5.040884755454258]
  We show that the number of steps to converge in Kullback-Leibler(KL) divergence is linear (up to logarithmic terms) in the intrinsic dimension $Leid$.<n>We also show that this linear dependency is sharp.
  arXiv  Detail & Related papers  (2024-10-11T17:58:30Z)
• Unextendibility, uncompletability, and many-copy indistinguishable ensembles [49.1574468325115]
  We show that the complement of any bipartite pure entangled state is spanned by product states which form a nonorthogonal unextendible product basis (nUPB) of maximum cardinality.<n>We also report a class of multipartite many-copy indistinguishable ensembles for which local indistinguishability property increases with decreasing number of mixed states.
  arXiv  Detail & Related papers  (2023-03-30T16:16:41Z)
• Annihilating Entanglement Between Cones [77.34726150561087]
  We show that Lorentz cones are the only cones with a symmetric base for which a certain stronger version of the resilience property is satisfied. Our proof exploits the symmetries of the Lorentz cones and applies two constructions resembling protocols for entanglement distillation.
  arXiv  Detail & Related papers  (2021-10-22T15:02:39Z)
• From Geometry to Topology: Inverse Theorems for Distributed Persistence [0.0]
  We show that the correct invariant is not the persistence diagram of X, but rather the collection of persistence diagrams of many small subsets. This invariant, which we call "distributed persistence," is trivially parallelizable, more stable to outliers. Results are complemented by two synthetic experiments demonstrating the use of distributed persistence in practice.
  arXiv  Detail & Related papers  (2021-01-28T21:36:45Z)
• Concentration estimates for random subspaces of a tensor product, and application to Quantum Information Theory [0.0]
  Given a random subspace $H_n$ chosen uniformly in a tensor product of Hilbert spaces $V_notimes W$, we consider the collection $K_n$ of all singular values of all norm one elements of $H_n$. A law of large numbers has been obtained for this random set in the context of $W$ fixed and the dimension of $H_n$ and $V_n$ tending to infinity at the same speed.
  arXiv  Detail & Related papers  (2020-11-30T23:22:55Z)
• Linear Optimal Transport Embedding: Provable Wasserstein classification for certain rigid transformations and perturbations [79.23797234241471]
  Discriminating between distributions is an important problem in a number of scientific fields. The Linear Optimal Transportation (LOT) embeds the space of distributions into an $L2$-space. We demonstrate the benefits of LOT on a number of distribution classification problems.
  arXiv  Detail & Related papers  (2020-08-20T19:09:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.