Time-uniform Chernoff bounds via nonnegative supermartingales
Time-uniform Chernoff bounds via nonnegative supermartingales
复制标题
DOI：
10.1214/18-ps321
复制
发表时间：
2020-01-01
影响因子：
1.6
通讯作者：
Sekhon, Jasjeet
中科院分区：
文献类型：
--
作者：
Howard, Steven R.;Ramdas, Aaditya;Sekhon, Jasjeet
我们开发了一类指数界的概率，鞅序列穿过一个时间依赖的线性阈值。我们的主要观点是，以这种方式制定指数浓度不等式既自然又富有成效。我们通过提出一个单一的假设和定理来说明这一点，这些假设和定理统一并加强了鞅的许多尾界，包括伯恩斯坦，班尼特，Hoeffding和Freedman的经典不等式（1960-80）;当代不等式（1980-2000）由Shorack和Wellner、Pinelis、Blackwell、货车de Geer和de la佩纳;以及Khan、Tropp、Bercu和Touati、Delyon等人的几个现代不平等（2000年后）。在每一种情况下，我们给出了最强和最一般的声明，到目前为止，量化的时间均匀浓度的标量，矩阵，和Banach空间值鞅，在离散和连续时间的各种非参数假设。在这样做时，我们弥合现有的线交叉不等式，顺序概率比检验，Cramer-Schiff方法，自归一化过程，和其他部分的文献之间的差距差距。
We develop 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 theorem that together unify and 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.