A One-Sided McDiarmid-Type Inequality for Heavy Tails via Reverse KL Tensorization

Hanuka Eshima, Amedeo Roberto Esposito, Andrea Paudice

We revisit McDiarmid's inequality, a central tool in statistical learning theory and algorithm analysis. We show that large deviations above the mean are exponentially unlikely for…