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-Guassian, the tail probability around the origin behaves as if they were sub-Gaussian, and the tail probability decays align with the Orlicz Psiα-tail elsewhere. Specifically, for independent and identically distributed (i.i.d.) Xii=1n with finite Orlicz norm |X|Psiα, our theory unveils that there is an interesting phase transition at α = 2 in that PPl(l|sumi=1n Xi r| ≥ tr) with t > 0 is upper bounded by 2expl(-Cmaxlfract2n|X|_Psiα2,fractα nα-1 |X|_Psiααrr) for α≥ 2, and by 2expl(-Cminlfract2n|X|_Psiα2,fractα nα-1 |X|_Psiααrr) for 1≤ α≤ 2 with some positive constant C. In many scenarios, it is often necessary to distinguish the standard deviation from the Orlicz norm when the latter can exceed the former greatly. To accommodate this, we build a new theoretical analysis framework, and our sharp, flexible concentration inequalities involve the variance and a mixing of Orlicz Psiα-tails through the min and max functions. Our theory yields new, improved concentration inequalities even for the cases of sub-Gaussian and sub-exponential distributions with α = 2 and 1, respectively. We further demonstrate our theory on martingales, random vectors, random matrices, and covariance matrix estimation. These sharp concentration inequalities can empower more precise non-asymptotic analyses across different statistical and machine learning applications.