Sharp finite-sample concentration of independent variables
We show an extension of Sanov's theorem on large deviations, controlling the tail probabilities of i.i.d. random variables with matching concentration and anti-concentration bounds. This result has a general scope, applies to samples of any size, and has a short information-theoretic proof using elementary techniques.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Sharper Sub-Weibull Concentrations
Constant-specified and exponential concentration inequalities play an essential role in the finite-sample theory of machine learning and high-dimensional statistics area. We obtain sharper and constants-specified concent…
Sharp Concentration Results for Heavy-Tailed Distributions
We obtain concentration and large deviation for the sums of independent and identically distributed random variables with heavy-tailed distributions. Our concentration results are concerned with random variables whose di…
Sharp Concentration Inequalities: Phase Transition and Mixing of Orlicz Tails with Variance
In this work, we investigate how to develop sharp concentration inequalities for sub-Weibull random variables, including sub-Gaussian and sub-exponential distributions. Although the random variables may not be sub-Guassi…
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 TheoryStability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments
While algorithmic stability is a central tool for understanding generalization of learning algorithms, existing high-probability guarantees typically rely on uniform boundedness or sub-Gaussian/sub-Weibull tail assumptio…