Tensor Bernstein concentration inequalities with an application to sample estimators for high-order moments

Abstract

This paper develops the Bernstein tensor concentration inequality for random tensors of general order, based on the use of Einstein products for tensors. This establishes a strong link between these and matrices, which in turn allows exploitation of existing results for the latter. An interesting application to sample estimators of high-order moments is presented as an illustration.

Keywords

Random tensors / concentration inequality / Einstein products / sub-sampling / computational statistics

References

[1] Aclioptas D, McSherry F. Fast computation of low rank matrix approximations. In: Proc 33rd Ann ACM Symposium on Theory of Computing. 2001, 611–618

[2] Ahlswede R, Winter A. Strong converse for identification via quantum channels. IEEE Trans Inform Theory, 2002, 48(3): 569–579

[3] Bellavia S, Gurioli G, Morini B. Theoretical study of an adaptive cubic regularization method with dynamic inexact Hessian information. arXiv: 1808.06239

[4] Bellavia S, Gurioli G, Morini B, Toint Ph L. Deterministic and stochastic inexact regularization algorithms for nonconvex optimization with optimal complexity. arXiv: 1811.03831

[5] Bellavia S, Krejić N, Krklec Jerinkić N. Subsampled inexact Newton methods for minimizing large sums of convex function. arXiv: 1811.05730

[6] Brazell M, Li N, Navasca C, Tamon Ch. Solving multilinear systems via tensor inversion. SIAM J Matrix Anal Appl, 2013, 34(2): 542–570

[7] Cartwright D, Sturmfels B. The number of eigenvalues of a tensor. Linear Algebra Appl, 2013, 438(2): 942–952

[8] Chen X, Jiang B, Lin T, Zhang S. On adaptive cubic regularization Newton's methods for convex optimization via random sampling. arXiv: 1802.05426

[9] Donoho D L. Compressed sensing. IEEE Trans Inform Theory, 2006, 52(4): 1289–1306

[10] Einstein A. The foundation of the general theory of relativity. In: The Collected Papers of Albert Einstein, Vol 6. Princeton: Princeton Univ Press, 1997, 146–200

[11] Forrester P J. Log-Gases and Random Matrices. London Math Soc Monogr Ser, 34. Princeton: Princeton Univ Press, 2010

[12] Frieze A, Kannan R, Vempala S. Fast Monte-Carlo algorithms for finding low-rank approximations. In: Proc 39th Ann Symposium on Foundations of Computer Science. 1998, 370–378

[13] Kohler J M. Lucchi A. Sub-sample cubic regularization for non-convex optimization. In: Proc 34th International Conference on Machine Learning, Sydney, 2017. arXiv: 1705.05933v3

[14] Lai W M, Rubin D H, Krempl E. Introduction to Continuum Mechanics. Oxford: Butterworth-Heinemann, 2009

[15] Luo Z, Qi L, Ye Y. Linear operators and positive semidefiniteness of symmetric tensor spaces. Sci China Math, 2015, 58(1): 197–212

[16] Miao Y, Qi L, Wei Y. Generalized tensor function via the tensor singular value decomposition based on the T-product. Linear Algebra Appl, 2020, 590: 258–303

[17] Qi L. Eigenvalues of a real supersymmetric tensor. J Symbolic Comput, 2005, 40(6): 1302–1324

[18] Qi L, Luo Z. Tensor Analysis: Spectral Theory and Special Tensors. Philadelphia: SIAM, 2017

[19] Qi L, Yu G, Wu E X. Higher order positive semidefinite diffusion tensor imaging. SIAM J Imaging Sci, 2010, 3(3): 416–433

[20] Sun L, Zheng B, Bu C, Wei Y. Moore-Penrose inverse of tensors via Einstein product. Linear Multilinear Algebra, 2016, 64(4): 686–698

[21] Thomson W. Elements of a mathematical theory of elasticity. Proc Roy Soc Lond, 1856, 8: 85–87

[22] Tropp J. An Introduction to Matrix Concentration Inequalities. Found Trends Machine Learning, Number 8: 1-2. Boston: Now Publ, 2015

[23] Williams C K I, Seeger N. Using the Nystrom method to speed up kernel machines. In: Advances in Neural Information Processing Systems 13. 2001, 682–688

[24] Wishart J. The generalized product moment distribution in samples from a multivariate normal population. Biometrika, 1928, 20A(1-2): 32–52

[25] Xu P, Roosta-Khorasani F, Mahoney M W. Newton-type methods for non-convex optimization under inexact Hessian information. arXiv: 1708.07164v3

[26] Xu P, Roosta-Khorasani F, Mahoney M W. Second-order optimization for non-convex machine learning: an empirical study. arXiv: 1708.07827v2

RIGHTS & PERMISSIONS

Higher Education Press