A New Proof of Sub-Gaussian Norm Concentration Inequality
Zishun Liu, Sam Power, Yongxin Chen · 2025
Read A New Proof of Sub-Gaussian Norm Concentration Inequality by Zishun Liu, Sam Power, Yongxin Chen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-14347.txt.
Introduction
Zishun Liu, Sam Power, and Yongxin Chen give a new proof of a core concentration inequality for sub-Gaussian random variables. The inequality bounds how sharply the norm of a random vector, or the operator norm of a random matrix, concentrates around its expectation. Standard proofs use epsilon-nets and union bounds.
Their method instead works with an averaged version of the moment generating function. Avoiding the union bound promises tighter concentration estimates. The argument covers both the vector and matrix cases in a unified way. Such inequalities underpin high-dimensional statistics and random matrix theory, so a cleaner proof with better constants has broad technical value.
Catalog record
| CREATOR | Zishun Liu, Sam Power, Yongxin Chen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-14347
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A New Proof of Sub-Gaussian Norm Concentration Inequality Zishun Liu, Sam Power, Yongxin Chen Abstract We present a new method for proving the norm concentration inequality of sub-Gaussian variables. Our proof is based on an averaged version of the moment generating function, termed the averaged moment generating function. Our method applies to both vector cases to bound the vector norm and matrix cases to bound the operator norm. Compared with the widely adopted ε \varepsilon -net technique-based proof of the sub-Gaussian norm concentration inequality, our method does not rely on the union bound and promises a tighter concentration bound. 1 Sub-Gaussian Norm Concentration Inequality Concentration inequalities are mathematical tools in probability theory that describe how a random variable deviates from some value, typically its expectation. Some commonly used instances include Markov’s inequality, Chebyshev’s inequality, and Chernoff bounds. These concentration inequalities play an essential role in various fields, including probability theory, statistics, machine learning, finance, etc, providing probabilistic guarantees when dealing with random quantities. Many probability distributions exhibit concentration properties, among which we consider an important class known as sub-Gaussian distribution. The sub-Gaussian random variable is formally defined as follows. Definition 1.1 . A random variable X\in\mathbb{R} is said to be sub-Gaussian with variance proxy \sigma^{2}>0 if \mathbb{E}_{X}(e^{\lambda X})\leq e^{\frac{\lambda^{2}\sigma^{2}}{2}},~\forall\lambda\in\mathbb{R}. (1) A random vector X\in\mathbb{R}^{n} is sub-Gaussian with variance proxy \sigma^{2}>0 if \langle\ell,X\rangle is sub-Gaussian for any unit vector \ell , that is, \mathbb{E}_{X}(e^{\lambda\langle\ell,X\rangle})\leq e^{\frac{\lambda^{2}\sigma^{2}}{2}},~\forall\lambda\in\mathbb{R},~\forall\ell\in\mathcal{S}^{n-1}, (2) where \mathcal{S}^{n-1}=\{x\in\mathbb{R}^{n}:~\|x\|=1\} denotes the Euclidean unit sphere in \mathbb{R}^{n} . Sub-Gaussian distributions include a wide range of distributions such as Gaussian distribution, uniform distribution, and any distributions with finite supports as special cases. For a Gaussian random variable, the variance proxy equals its variance. In this work, we consider one important concentration inequality for sub-Gaussian distributions known as norm concentration [ 1 , 2 ] , which describes the concentration property of the norm \|X\| for a sub-Gaussian random vector X . Theorem 1 . For a sub-Gaussian vector X\in\mathbb{R}^{n} with variance proxy \sigma^{2} , there exist constants C_{1} , C_{2} such that, for any \delta\in(0,1) , \mathbb{P}\left(\|X\|\leq\sigma\sqrt{C_{1}n+C_{2}\log\frac{1}{\delta}}\right)\geq 1-\delta. (3) The choice of constants C_{1},C_{2} depends on the proof techniques. When n=1 , a direct application of the Markov’s inequality points to \mathbb{P}\left(X>r\right)=\mathbb{P}\left(e^{\lambda X}>e^{\lambda r}\right)\leq\frac{\mathbb{E}_{X}(e^{\lambda X})}{e^{\lambda r}}\leq e^{\frac{\lambda^{2}\sigma^{2}}{2}-\lambda r} for any \lambda>0,r>0 . Minimizing the above over \lambda yields \mathbb{P}\left(X>r\right)\leq e^{-\frac{r^{2}}{2\sigma^{2}}} . Similarly, \mathbb{P}\left(X<-r\right)\leq e^{-\frac{r^{2}}{2\sigma^{2}}} . Combining them with the union bound, we obtain \mathbb{P}\left(\|X\|>r\right)\leq 2e^{-\frac{r^{2}}{2\sigma^{2}}} . This corresponds to ( 3 ) with constants C_{1}=2\log 2 and C_{2}=2 . When n\geq 2 , one can follow a similar idea and apply Markov’s inequality to bound \mathbb{P}\left(\ell^{\top}X>r\right) for each \ell\in\mathcal{S}^{n-1} and then combine them to establish a probabilistic bound for \|X\|=\max_{\ell\in\mathcal{S}^{n-1}}\ell^{\top}X . However, the union bound is no longer applicable since the maximum is over an unaccountable set \mathcal{S}^{n-1} . To circumvent this issue, the \varepsilon -net technique has been developed and has become a standard proof for sub-Gaussian norm concentration [ 1 , 3 ] . Following this technique, one constructs an \varepsilon -net \mathcal{N} [ 1 , Definition 1.17] for the Euclidean unit ball such that \mathcal{N} has finite elements and \max_{\ell\in\mathcal{S}^{n-1}}\ell^{\top}X\leq\frac{1}{1-\varepsilon}\max_{\ell\in\mathcal{N}}\ell^{\top}X [ 3 , Exercise 4.4.2] . The union bound can be applied since \mathcal{N} is a finite set. This method results in ( 3 ) with constants C_{1} and C_{2} determined by C_{1}=\frac{2\log(1+2/(1-\varepsilon))}{\varepsilon^{2}},~\,\,C_{2}=\frac{2}{\varepsilon^{2}} (4) where \varepsilon can take any value in the interval (0,1) . When \varepsilon=\frac{1}{2} , we have C_{1}=8\log 5\approx 16 and C_{2}=8 , which is commonly used in existing literature, e.g. [ 1 ] . 2 New Proof based on Averaged Moment Generating Function To analyze the concentration property of \|X\| , the \varepsilon -net strategy as described above first analyzes the concentration of the one-dimensional projection \ell^{\top}X of X using the Markov’s inequality and then applies the union bound to establish the concentration bound for \|X\| . This gives rise to one question: is there a more direct approach to establish the concentration of \|X\| ? One natural attempt is to bound \mathbb{E}_{X}(e^{\lambda\|X\|}) with \lambda>0 and apply the Markov’s inequality to get bound \mathbb{P}\left(\|X\|>r\right)\leq\mathbb{E}_{X}(e^{\lambda\|X\|})/e^{\lambda r} directly. However, it is not easy to bound \mathbb{E}_{X}(e^{\lambda\|X\|}) from the definition ( 2 ) of the sub-Gaussian random vector. In fact, researchers often follow an opposite direction and bound \mathbb{E}_{X}(e^{\lambda\|X\|}) using the concentration property of \|X\| . In this paper, we present a new proof of the sub-Gaussian norm concentration inequality that directly analyzes \|X\| . The key of our proof is a novel mathematical tool named the averaged moment generating function (AMGF) that bears similarity with \mathbb{E}_{X}(e^{\lambda\|X\|}) . Definition 2.1 (AMGF) . The Averaged Moment Generating Function \Phi_{X}(\lambda) of a random vector X\in\mathbb{R}^{n} is defined as \Phi_{X}(\lambda)=\mathbb{E}_{X}(\Phi_{n}(\lambda X)) where the energy function \Phi_{n}(\lambda X)=\mathbb{E}_{\ell\sim\mathcal{S}^{n-1}}\left(e^{\lambda\langle\ell,X\rangle}\right). (5) The AMGF was first introduced in [ 4 ] to study Langevin algorithms in sampling problems. The AMGF is an average of the moment generating function (MGF) \mathbb{E}_{X}(e^{\lambda\langle\ell,X\rangle}) over the unit sphere \ell\sim\mathcal{S}^{n-1} . It can also be viewed as an MGF with the exponential energy function e^{\lambda\langle\ell,X\rangle} being replaced by its average \Phi_{n}(\lambda X)=\mathbb{E}_{\ell\sim\mathcal{S}^{n-1}}\left(e^{\lambda\langle\ell,X\rangle}\right) . Similar to e^{\lambda\|X\|} , the energy function \Phi_{n}(\lambda X) only depends on the norm \|X\| . In fact, \Phi_{n}(\lambda X)=\phi_{n}(\|\lambda X\|), (6) where \phi_{n}(z)=\mathbb{E}_{\ell\sim\mathcal{S}^{n-1}}\left(e^{\langle\ell,z\,\eta\rangle}\right),~\forall\eta\in\mathcal{S}^{n-1} admits a closed-form expression of \phi_{1}(z)=\cosh(z) and \phi_{n}(z)=\Gamma(n/2)(2/z)^{(n-2)/2}I_{(n-2)/2}(z) when n\geq 2 where \Gamma denotes the Gamma function and I is the modified Bessel function of the first kind [ 4 ] . In addition to these similarities to e^{\lambda\|x\|} , we show below that the value of \Phi_{n}(\lambda X) is closely related to e^{\|\lambda X\|} . Lemma 2.1 . For any X\in\mathbb{R}^{n} and any \varepsilon\in(0,1) , \Phi_{n}(\lambda X) satisfies \Phi_{n}(\lambda X)\geq(1-\varepsilon^{2})^{\frac{n}{2}}e^{\varepsilon\|\lambda X\|}. (7) Proof. In view of \Phi_{n}(\lambda X)=\phi_{n}(\|\lambda X\|) , it suffices to show that \phi_{n}(z)\geq(1-\varepsilon^{2})^{\frac{n}{2}}e^{\varepsilon z} (8) holds for any z\geq 0 and any \varepsilon\in(0,1) . When n=1 , \phi_{1}(z)=\cosh(z) and ( 7 ) becomes \cosh(z)\geq\sqrt{1-\varepsilon^{2}}e^{\varepsilon z},~\forall z\geq 0,~\forall\varepsilon\in(0,1). (9) This is a straightforward consequence of the convexity of \log\cosh(z)-\log\left(\sqrt{1-\varepsilon^{2}}e^{\varepsilon z}\right) with respect to z . We next focus on the case of n\geq 2 . As pointed out in [ 4 ] , directly from the definition, the derivative of \log\phi_{n} admits an elegant expression \frac{d}{dz}\log\phi_{n}(z)=\frac{I_{\frac{n}{2}}(z)}{I_{\frac{n}{2}-1}(z)}. (10) The ratio of Bessel functions can be bounded below as [ 5 ] \frac{I_{\frac{n}{2}}(z)}{I_{\frac{n}{2}-1}(z)}\geq\sqrt{1+\left(\frac{n}{2z}\right)^{2}}-\frac{n}{2z}. (11) Denote g(z)=\sqrt{1+(\frac{n}{2z})^{2}}-\frac{n}{2z} and G(z)=\int_{0}^{z}g(y)dy , then, by ( 10 )-( 11 ), \log\phi_{n}(z)\geq G(z)+\log\phi_{n}(0)=G(z),\quad\forall z\geq 0. (12) Since g(z) is monotonically increasing over z>0 , G(z) is convex on z>0 . Thus, by the definition of convexity, given any z_{0}>0 , G(z)\geq g(z_{0})(z-z_{0})+G(z_{0}). (13) Set z_{0}=\frac{\varepsilon n}{1-\varepsilon^{2}} , then g(z_{0})=\varepsilon,\quad G(z_{0})=\frac{n\varepsilon^{2}}{1-\varepsilon^{2}}+\frac{n}{2}\log(1-\varepsilon^{2}). (14) Plugging ( 14 ) into ( 12 )-( 13 ) yields \log\phi_{n}(z)\geq\varepsilon z+\frac{n}{2}\log(1-\varepsilon^{2}). (15) The conclusion ( 8 ) and thus ( 7 ) follow by taking the exponential of ( 15 ). This completes the proof. ∎ By Lemma 2.1 , the AMGF can be viewed as a surrogate function of \mathbb{E}_{X}(e^{\lambda\|X\|}) . One distinguishing feature of the AMGF compared with \mathbb{E}_{X}(e^{\lambda\|X\|}) is that the AMGF shares the same bound as the MGF in ( 2 ). More specifically, by ( 2 ), \mathbb{E}_{X}(e^{\lambda\langle\ell,X\rangle})\leq e^{\frac{\lambda^{2}\sigma^{2}}{2}} for any \ell\in\mathcal{S}^{n-1} , and thus the AMGF satisfies \Phi_{X}(\lambda)=\mathbb{E}_{X}(\Phi_{n}(\lambda X))=\mathbb{E}_{X}\mathbb{E}_{\ell\sim\mathcal{S}^{n-1}}(e^{\lambda\langle\ell,X\rangle})=\mathbb{E}_{\ell\sim\mathcal{S}^{n-1}}\mathbb{E}_{X}(e^{\lambda\langle\ell,X\rangle})\leq e^{\frac{\lambda^{2}\sigma^{2}}{2}}. (16) By combining ( 16 ) with Lemma 2.1 ,