A 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 deviation size for missing mass and improve the results of Berend and Kontorovich (2013) and Yari Saeed Khanloo and Haffari (2015) for small deviations which is the most important case in learning theory.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheorySimilar Papers 제목 키워드 기반
Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote
We present a new second-order oracle bound for the expected risk of a weighted majority vote. The bound is based on a novel parametric form of the Chebyshev- Cantelli inequality (a.k.a. one-sided Chebyshev's), which is a…
FormA refinement of Bennett's inequality with applications to portfolio optimization
A refinement of Bennett's inequality is introduced which is strictly tighter than the classical bound. The new bound establishes the convergence of the average of independent random variables to its expected value. It al…
Portfolio OptimizationSharper Risk Bound for Multi-Task Learning with Multi-Graph Dependent Data
In multi-task learning (MTL) with each task involving graph-dependent data, existing generalization analyses yield a \emph{sub-optimal} risk bound of $O(\frac{1}{\sqrt{n}})$, where $n$ is the number of training samples o…
Multi-Task LearningSplit-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 AnsweringBennett-type Generalization Bounds: Large-deviation Case and Faster Rate of Convergence
In this paper, we present the Bennett-type generalization bounds of the learning process for i.i.d. samples, and then show that the generalization bounds have a faster rate of convergence than the traditional results. In…
Generalization Bounds