Sharp Concentration Inequalities: Phase Transition and Mixing of Orlicz Tails with Variance
arXiv:2603.25934v1 Announce Type: cross
Abstract: 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_alpha$-tail elsewhere. Specifically, for independent and identically distributed (i.i.d.) ${X_i}_{i=1}^n$ with finite Orlicz norm $|X|_{Psi_alpha}$, our theory unveils that there is an interesting phase transition at $alpha = 2$ in that $PPl(l|sum_{i=1}^n X_i r| geq tr)$ with $t > 0$ is upper bounded by $2expl(-Cmaxl{frac{t^2}{n|X|_{Psi_{alpha}}^2},frac{t^{alpha}}{ n^{alpha-1} |X|_{Psi_{alpha}}^{alpha}}r}r)$ for $alphageq 2$, and by $2expl(-Cminl{frac{t^2}{n|X|_{Psi_{alpha}}^2},frac{t^{alpha}}{ n^{alpha-1} |X|_{Psi_{alpha}}^{alpha}}r}r)$ for $1leq alphaleq 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_alpha$-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 $alpha = 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.
