A General Reduction for High-Probability Analysis with General Light-Tailed Distributions
This provides a theoretical tool for researchers in machine learning to simplify high-probability analyses, though it is incremental as it builds on existing reduction methods.
The paper tackles the problem of analyzing learning algorithms with light-tailed randomness by introducing a general reduction technique that simplifies analysis to bounded random variables with minimal loss in logarithmic factors, applicable to various distributions like exponential and sub-Gaussian without specialized inequalities.
We describe a general reduction technique for analyzing learning algorithms that are subject to light-tailed (but not necessarily bounded) randomness, a scenario that is often the focus of theoretical analysis. 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 is 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. Derivations of a generalized Azuma inequality, convergence bounds in stochastic optimization, and regret analysis in multi-armed bandits with general light-tailed randomization are provided to illustrate the technique.