Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues
Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues
复制标题
次乘 Glivenko-Cantelli 和收入均匀收敛
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Yehudayoff
中科院分区：
文献类型：
--
作者：
N. Alon;Moshe Babaioff;Yannai A. Gonczarowski;Y. Mansour;S. Moran;A. Yehudayoff
在这项工作中，我们推导了经典Glivenko-Cantelli定理的一个变体，该定理断言经验累积分布函数（CDF）与底层分布的CDF一致收敛。我们的变体允许对CDF的极值有更严格的收敛界。
In this work we derive a variant of the classic Glivenko-Cantelli Theorem, which asserts uniform convergence of the empirical Cumulative Distribution Function (CDF) to the CDF of the underlying distribution. Our variant allows for tighter convergence bounds for extreme values of the CDF.
We apply our bound in the context of revenue learning, which is a well-studied problem in economics and algorithmic game theory. We derive sample-complexity bounds on the uniform convergence rate of the empirical revenues to the true revenues, assuming a bound on the $k$th moment of the valuations, for any (possibly fractional) $k>1$.
For uniform convergence in the limit, we give a complete characterization and a zero-one law: if the first moment of the valuations is finite, then uniform convergence almost surely occurs; conversely, if the first moment is infinite, then uniform convergence almost never occurs.