arXiv:2603.24493cs.LGmath.ST2026-03被引 3

在乘积空间中,用线性VC维刻画均匀大数定律的成立条件。

Uniform Laws of Large Numbers in Product Spaces

  • 引入线性VC维,定义为坐标轴对齐线上可破碎的最大点集大小
  • 在绝对连续于边缘乘积分布下,线性VC维有限等价于均匀收敛
  • 适用于低互信息、稀疏混合等自然场景,适合理论学习研究者

均匀大数定律是Vapnik--Chervonenkis理论的核心,通常由VC维有限性刻画。本文研究具有乘积结构的笛卡尔乘积空间中的均匀收敛现象,假设底层分布相对于其边缘分布的乘积绝对连续,该条件涵盖多种自然情形,如乘积分布、稀疏混合乘积分布、低互信息分布等。我们证明:在该假设下,一族事件满足均匀大数定律当且仅当其线性VC维有限。线性VC维定义为位于坐标轴对齐直线上的可破碎集合的最大大小,即所有坐标相同至多一个不同的向量集。该维度始终不超过经典VC维,但可能远小得多。例如,R^d中凸集族的线性VC维为2,而当d≥2时经典VC维为无穷。证明依赖于一种显著不同于标准经验均值估计器的新型估计器,其结构更复杂;我们还证明此类偏离在本设置下不可避免。全文提出多个开放问题,尤其关注样本复杂度的量化边界。

原文摘要 · Abstract (English)

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.

统计学习VC维概率不等式理论分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。