Exponential line-crossing inequalities
Exponential line-crossing inequalities
复制标题
DOI：
--
复制
发表时间：
2018-08
期刊：
影响因子：
--
通讯作者：
Steven R. Howard;Aaditya Ramdas;Jon D. McAuliffe;J. Sekhon
中科院分区：
文献类型：
--
作者：
Steven R. Howard;Aaditya Ramdas;Jon D. McAuliffe;J. Sekhon
本文针对鞅序列越过一个与时间相关的线性阈值的概率，推导出了一类指数界。我们的关键见解是，以这种方式构建指数集中不等式既自然又富有成效。我们通过提出一个单一假设和一个单一定理来说明这一点，它们共同强化了许多鞅的尾界，包括伯恩斯坦、贝内特、霍夫丁和弗里德曼在1960 - 1980年提出的经典不等式；肖拉克和韦尔纳、皮内利斯、布莱克韦尔、范德吉尔和德拉佩尼亚在1980 - 2000年提出的当代不等式；以及汗、特罗普、贝尔库和图阿蒂、德利翁等人在2000年后提出的若干现代不等式。在每一种情况下，我们都给出了迄今为止最强且最通用的表述，在离散和连续时间的各种非参数假设下，对标量值、矩阵值和巴拿赫空间值的鞅的时间一致集中性进行了量化。通过这样做，我们弥合了现有的越线不等式、序贯概率比检验、克拉默 - 切尔诺夫方法、自归一化过程以及文献中其他部分之间的差距。
This paper develops a class of exponential bounds for the probability that a martingale sequence crosses a time-dependent linear threshold. Our key insight is that it is both natural and fruitful to formulate exponential concentration inequalities in this way. We illustrate this point by presenting a single assumption and a single theorem that together strengthen many tail bounds for martingales, including classical inequalities (1960-80) by Bernstein, Bennett, Hoeffding, and Freedman; contemporary inequalities (1980-2000) by Shorack and Wellner, Pinelis, Blackwell, van de Geer, and de la Pena; and several modern inequalities (post-2000) by Khan, Tropp, Bercu and Touati, Delyon, and others. In each of these cases, we give the strongest and most general statements to date, quantifying the time-uniform concentration of scalar, matrix, and Banach-space-valued martingales, under a variety of nonparametric assumptions in discrete and continuous time. In doing so, we bridge the gap between existing line-crossing inequalities, the sequential probability ratio test, the Cramer-Chernoff method, self-normalized processes, and other parts of the literature.