A Note on High-Probability Analysis of Algorithms with Exponential,
  Sub-Gaussian, and General Light Tails
Amit Attia Tomer Koren
This short note describes a simple technique for analyzing probabilistic
algorithms that rely on a light-tailed (but not necessarily bounded) source of
randomization. We show that the analysis of such an algorithm can be reduced,
in a black-box manner and with only a small loss in logarithmic factors, to an
analysis of a simpler variant of the same algorithm that uses bounded random
variables and often easier to analyze. This approach simultaneously applies to
any light-tailed randomization, including exponential, sub-Gaussian, and more
general fast-decaying distributions, without needing to appeal to specialized
concentration inequalities. Analyses of a generalized Azuma inequality and
stochastic optimization with general light-tailed noise are provided to
illustrate the technique.