Novel Bernstein-like Concentration Inequalities for the Missing Mass
Novel Bernstein-like Concentration Inequalities for the Missing Mass
复制标题
新颖的伯恩斯坦式失踪质量浓度不等式
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Gholamreza Haffari
中科院分区：
文献类型：
--
作者：
Bahman Yari Saeed Khanloo;Gholamreza Haffari
我们关心的是获得缺失质量的新浓度不等式，即样本中未观察到的结果的总概率质量。我们不仅首次推导了缺失质量偏差大小的次线性指数的无分布的类伯恩斯坦偏差界，而且改进了McAllester和Ortiz（2003）和berend和Kontorovich（2013, 2012）的小偏差结果，这是学习理论中最有趣的案例。众所周知，大多数标准不等式不能直接用于分析异质和，即其项在大小上有很大差异的和。我们的通用和直观的方法表明，在McAllester和Ortiz（2003）中引入的异质性问题是可以解决的，至少在缺失质量的情况下，通过使用我们的新阈值技术调节术语。
We are concerned with obtaining novel concentration inequalities for the missing mass, i.e. the total probability mass of the outcomes not observed in the sample. We not only derive - for the first time - distribution-free Bernstein-like deviation bounds with sublinear exponents in deviation size for missing mass, but also improve the results of McAllester and Ortiz (2003) andBerend and Kontorovich (2013, 2012) for small deviations which is the most interesting case in learning theory. It is known that the majority of standard inequalities cannot be directly used to analyze heterogeneous sums i.e. sums whose terms have large difference in magnitude. Our generic and intuitive approach shows that the heterogeneity issue introduced in McAllester and Ortiz (2003) is resolvable at least in the case of missing mass via regulating the terms using our novel thresholding technique.