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

doi:10.1007/s11464-020-0830-4

Front. Math. China

2020, Vol. 15

Issue (2) : 367-384 https://doi.org/10.1007/s11464-020-0830-4

RESEARCH ARTICLE

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

Ziyan LUO¹, Liqun QI^2,³(

), Philippe L. TOINT⁴

¹. Department of Applied Mathematics, School of Science, Beijing Jiaotong University, Beijing 100044, China
². Department of Mathematics, School of Science, Hangzhou Dianzi University, Hangzhou 310018, China
³. Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China
⁴. Namur Center for Complex Systems (naXys), University of Namur, 61, rue de Bruxelles, B-5000 Namur, Belgium

Download: PDF(310 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Liqun QI

Issue Date: 18 May 2020

Cite this article:

Ziyan LUO,Liqun QI,Philippe L. TOINT. Tensor Bernstein concentration inequalities with an application to sample estimators for high-order moments[J]. Front. Math. China, 2020, 15(2): 367-384.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-020-0830-4
https://academic.hep.com.cn/fmc/EN/Y2020/V15/I2/367

1	D Aclioptas, F McSherry. Fast computation of low rank matrix approximations. In: Proc 33rd Ann ACM Symposium on Theory of Computing. 2001, 611–618 https://doi.org/10.1145/380752.380858
2	R Ahlswede, A Winter. Strong converse for identification via quantum channels. IEEE Trans Inform Theory, 2002, 48(3): 569–579 https://doi.org/10.1109/18.985947
3	S Bellavia, G Gurioli, B Morini. Theoretical study of an adaptive cubic regularization method with dynamic inexact Hessian information. arXiv: 1808.06239
4	S Bellavia, G Gurioli, B Morini, Ph L Toint. Deterministic and stochastic inexact regularization algorithms for nonconvex optimization with optimal complexity. arXiv: 1811.03831
5	S Bellavia, N Krejić, N Krklec Jerinkić. Subsampled inexact Newton methods for minimizing large sums of convex function. arXiv: 1811.05730
6	M Brazell, N Li, C Navasca, Ch Tamon. Solving multilinear systems via tensor inversion. SIAM J Matrix Anal Appl, 2013, 34(2): 542–570 https://doi.org/10.1137/100804577
7	D Cartwright, B Sturmfels. The number of eigenvalues of a tensor. Linear Algebra Appl, 2013, 438(2): 942–952 https://doi.org/10.1016/j.laa.2011.05.040
8	X Chen, B Jiang, T Lin, S Zhang. On adaptive cubic regularization Newton's methods for convex optimization via random sampling. arXiv: 1802.05426
9	D L Donoho. Compressed sensing. IEEE Trans Inform Theory, 2006, 52(4): 1289–1306 https://doi.org/10.1109/TIT.2006.871582
10	A Einstein. 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	P J Forrester. Log-Gases and Random Matrices. London Math Soc Monogr Ser, 34. Princeton: Princeton Univ Press, 2010 https://doi.org/10.1515/9781400835416
12	A Frieze, R Kannan, S Vempala. Fast Monte-Carlo algorithms for finding low-rank approximations. In: Proc 39th Ann Symposium on Foundations of Computer Science. 1998, 370–378
13	J M Kohler. A Lucchi. Sub-sample cubic regularization for non-convex optimization. In: Proc 34th International Conference on Machine Learning, Sydney, 2017. arXiv: 1705.05933v3
14	W M Lai, D H Rubin, E Krempl. Introduction to Continuum Mechanics. Oxford: Butterworth-Heinemann, 2009 https://doi.org/10.1016/B978-0-7506-8560-3.00001-3
15	Z Luo, L Qi, Y Ye. Linear operators and positive semidefiniteness of symmetric tensor spaces. Sci China Math, 2015, 58(1): 197–212 https://doi.org/10.1007/s11425-014-4930-z
16	Y Miao, L Qi, Y Wei. Generalized tensor function via the tensor singular value decomposition based on the T-product. Linear Algebra Appl, 2020, 590: 258–303 https://doi.org/10.1016/j.laa.2019.12.035
17	L Qi. Eigenvalues of a real supersymmetric tensor. J Symbolic Comput, 2005, 40(6): 1302–1324 https://doi.org/10.1016/j.jsc.2005.05.007
18	L Qi, Z Luo. Tensor Analysis: Spectral Theory and Special Tensors. Philadelphia: SIAM, 2017 https://doi.org/10.1137/1.9781611974751
19	L Qi, G Yu, E X Wu. Higher order positive semidefinite diffusion tensor imaging. SIAM J Imaging Sci, 2010, 3(3): 416–433 https://doi.org/10.1137/090755138
20	L Sun, B Zheng, C Bu, Y Wei. Moore-Penrose inverse of tensors via Einstein product. Linear Multilinear Algebra, 2016, 64(4): 686–698 https://doi.org/10.1080/03081087.2015.1083933
21	W Thomson. Elements of a mathematical theory of elasticity. Proc Roy Soc Lond, 1856, 8: 85–87 https://doi.org/10.1098/rspl.1856.0030
22	J Tropp. An Introduction to Matrix Concentration Inequalities. Found Trends Machine Learning, Number 8: 1-2. Boston: Now Publ, 2015 https://doi.org/10.1561/9781601988393
23	C K I Williams, N Seeger. Using the Nystrom method to speed up kernel machines. In: Advances in Neural Information Processing Systems 13. 2001, 682–688
24	J Wishart. The generalized product moment distribution in samples from a multivariate normal population. Biometrika, 1928, 20A(1-2): 32–52 https://doi.org/10.1093/biomet/20A.1-2.32
25	P Xu, F Roosta-Khorasani, M W Mahoney. Newton-type methods for non-convex optimization under inexact Hessian information. arXiv: 1708.07164v3
26	P Xu, F Roosta-Khorasani, M W Mahoney. Second-order optimization for non-convex machine learning: an empirical study. arXiv: 1708.07827v2

Viewed

Full text

Abstract

Cited

Shared

Discussed