Deviation bounds for the norm of a random vector under exponential moment conditions with applications

Abstract

Hanson-Wright inequality provides a powerful tool for bounding the norm ‖ξ‖ of a centered stochastic vector ξ with independent entries and sub-gaussian behavior. This paper extends the bounds to the case when ξ only has bounded exponential moments of the form log E exp⟨V⁻¹ξ,u⟩≤‖u‖²/2, where V²≥Var(ξ) and ‖u‖≤g for some fixed g. For a linear mapping Q, we present an upper quantile function z_c(B,x) ensuring P(‖Qξ‖>z_c(B,x))≤3e^−x with B=QV²Q^T. The obtained results exhibit a phase transition effect: with a value xc depending on g and B, for x≤x_c, the function z_c(B,x) replicates the case of a Gaussian vector ξ, that is, $z_{c}^{2}(B, x)=\operatorname{tr}(B)+ 2 \sqrt{x \operatorname{tr}\left(B^{2}\right)}+2 x\|B\|. $ For x>x_c, the function z_c(B,x) grows linearly in x. The results are specified to the case of Bernoulli vector sums and to covariance estimation in Frobenius norm.

Keywords

Upper quantiles / Phase transition / Vector Bernoulli sums / Frobenius loss

Acknowledgements

Financial support by the German Research Foundation (DFG) through the Collaborative Research Center 1294 “Data assimilation” is gratefully acknowledged.

References

[1] Abbe, E., Community detection and stochastic block models: Recent developments, Journal of Machine Learning Research, 2018, 18(177): 1-86.

[2] Bartlett, P. L., Long, P. M., Lugosi, G. and Tsigler, A., Benign overfitting in linear regression, Proceedings of the National Academy of Sciences, 2020, 117(48): 30063-30070.

[3] Bunea, F. and Xiao, L., On the sample covariance matrix estimator of reduced effective rank population matrices, with applications to fPCA, Bernoulli, 2015, 21(2): 1200-1230.

[4] Chen, P., Gao, C. and Zhang, A. Y., Optimal full ranking from pairwise comparisons, The Annals of Statistics, 2022, 50(3): 1775-1805.

[5] Cheng, C. and Montanari, A., Dimension free ridge regression, arXiv: 2210. 08571, 2022.

[6] Gao, C., Ma, Z., Zhang, A. Y. and Zhou, H. H., Achieving optimal misclassification proportion in stochastic block models, Journal of Machine Learning Research, 2017, 18(60): 1-45.

[7] Klochkov, Y. and Zhivotovskiy, N., Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method, Electronic Journal of Probability, 2020, 25: 1-30.

[8] Laurent, B. and Massart, P., Adaptive estimation of a quadratic functional by model selection, The Annals of Statistics, 2000, 28(5): 1302-1338.

[9] Lounici, K., High-dimensional covariance matrix estimation with missing observations, Bernoulli, 2014, 20(3): 1029-1058.

[10] Rudelson, M. and Vershynin, R., Hanson-Wright inequality and sub-Gaussian concentration, Electronic Communications in Probability, 2013, 18: 1-9.

[11] Spokoiny, V., Inexact Laplace approximation and the use of posterior mean in Bayesian inference, Bayesian Analysis, 2025, 20(1): 1303-1330.

[12] Spokoiny, V., Mixed Laplace approximation for marginal posterior and Bayesian inference in error-in-operator model, arXiv: 2305.09336, 2023.

[13] Tropp, J. A., An introduction to matrix concentration inequalities, Foundations and Trends in Machine Learning, 2015, 8(1-2): 1-230.

[14] Vershynin, R., High-Dimensional Probability: An Introduction with Applications in Data Science, Number 47 in Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 2018.