A Note on the Chernoff Bound for Random Variables in the Unit Interval
The Chernoff bound is a well-known tool for obtaining a high probability bound on the expectation of a Bernoulli random variable in terms of its sample average. This bound is commonly used in statistical learning theory to upper bound the generalisation risk of a hypothesis in terms of its empirical risk on held-out data, for the case of a binary-valued loss function. However, the extension of this bound to the case of random variables taking values in the unit interval is less well known in the community. In this note we provide a proof of this extension for convenience and future reference.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheorySimilar Papers 제목 키워드 기반
Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
This chapter collects several probabilistic tools that proved to be useful in the analysis of randomized search heuristics. This includes classic material like Markov, Chebyshev and Chernoff inequalities, but also lesser…
Chernoff Bounds for Tensor Expanders on Riemannian Manifolds Using Graph Laplacian Approximation
This paper addresses the advancement of probability tail bound analysis, a crucial statistical tool for assessing the probability of large deviations of random variables from their expected values. Traditional tail bound…
A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices
We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a regular (aperiodic and irreducible) finite Markov chain. Specially, consider a random walk on a regular Markov chain and a Hermitian…
Graph LearningGraph Representation LearningRepresentation LearningPAC-Bayes-Chernoff bounds for unbounded losses
We introduce a new PAC-Bayes oracle bound for unbounded losses that extends Cram\'er-Chernoff bounds to the PAC-Bayesian setting. The proof technique relies on controlling the tails of certain random variables involving …
Near-Optimal Confidence Sequences for Bounded Random Variables
Many inference problems, such as sequential decision problems like A/B testing, adaptive sampling schemes like bandit selection, are often online in nature. The fundamental problem for online inference is to provide a se…
valid