A Note on High-Probability Analysis of Algorithms with Exponential, Sub-Gaussian, and General Light Tails
<|reference_start|>A Note on High-Probability Analysis of Algorithms with Exponential, Sub-Gaussian, and General Light Tails: 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.<|reference_end|>
@article{attia2024a,
    title={A Note on High-Probability Analysis of Algorithms with Exponential,
  Sub-Gaussian, and General Light Tails},
    author={Amit Attia, Tomer Koren},
    journal={arXiv preprint arXiv:2403.02873},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.02873},
    primaryClass={cs.LG cs.DS math.PR}
}