Novel Bernstein-like Concentration Inequalities for the Missing Mass
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheorySimilar Papers 제목 키워드 기반
Novel Deviation Bounds for Mixture of Independent Bernoulli Variables with Application to the Missing Mass
In this paper, we are concerned with obtaining distribution-free concentration inequalities for mixture of independent Bernoulli variables that incorporate a notion of variance. Missing mass is the total probability mass…
Learning TheorySplit-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables
We present a new concentration of measure inequality for sums of independent bounded random variables, which we name a split-kl inequality. The inequality is particularly well-suited for ternary random variables, which n…
Open-Ended Question AnsweringSome Hoeffding- and Bernstein-type Concentration Inequalities
We prove concentration inequalities for functions of independent random variables {under} sub-gaussian and sub-exponential conditions. The utility of the inequalities is demonstrated by an extension of the now classical …
Vocal Bursts Type PredictionEfron-Stein PAC-Bayesian Inequalities
We prove semi-empirical concentration inequalities for random variables which are given as possibly nonlinear functions of independent random variables. These inequalities describe concentration of random variable in ter…
Generalization BoundsOff-policy evaluationA Bennett Inequality for the Missing Mass
Novel concentration inequalities are obtained for the missing mass, i.e. the total probability mass of the outcomes not observed in the sample. We derive distribution-free deviation bounds with sublinear exponents in dev…
Learning Theory