压缩回归学习算法的泛化界

Abstract

Abstract:

This paper addresses the generalization performance of compressed least-square regression learning algorithm. A generalization error bound of this algorithm is established by using the random projection and the theory of the covering number. The obtained results show that the compressed learning can reduce the sample error at the price of increasing the approximation error, but the increment can be controlled. In addition, by using compressed projection, the overfitting problem for the learning algorithm can be overcome to a certain extent.

Key words: Machine learning, Compressed sensing, Regression learning algorithm, Error bound, Approximation

CLC Number:

41A25

CAO Fei-Long, DAI Teng-Hui, ZHANG Yong-Quan. Generalization Bounds of Compressed Regression Learning Algorithm[J].Acta mathematica scientia,Series A, 2014, 34(4): 905-916.

Trendmd

References

[1] Burges C J C. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 1998, 2: 121--167

[2] Blum A. Random projection, margins, kernels, and feature-selection. Lecture Notes in Computer Sciences, 2006, 3940: 52--68

[3] Cand\`{e}s E J. Compressive sampling. Proceedings of the International Congress of Mathematicians, 2006, 3: 1433--1452

[4] Cand\`{e}s E J. The restricted isometry property and its implications for compressed sensing. Compte Rendus Mathematique, 2008, 346: 589--592

[5] Cand\`{e}s, E J, Tao T. Near-optimal signal recovery from random projections: universal encoding strategies. IEEE Trans Infor Theory, 2006, 52: 5406--5425

[6] Calderbank R, Jafarpour Schapire S R. Compressed Learning: Universal Sparse Dimensionality Reduction and Learning in the Measurement Domain. Technical Report. Houston, TX: Rice University, 2009

[7] Cucker F, Smale S. On the mathematical foundations of learning. Bull Amer Math Soc (New Series), 2001, 39: 1--49

[8] Donoho D L. Compressed sensing.IEEE Trans Infor Theory, 2006, 52: 1289--1306

[9] Lee W S, Bartlett P L, Williamson R C. The importance of convexity in learning with least square loss. IEEE Trans Infor Theory, 1998, 44: 1974--1980

[10] Maillard O A, Munos R. Linear regression with random projections.The Journal of Machine Learning Research, 2012, 13(1): 2735--2772

[11] Maillard O A, Munos R.Compressed least-squares regression. In Proceedings of Advances in Neural Information
Processing Systems, 2009, 22: 1213--1221

[12] Rahimi A, Recht B. Random features for large-scale kernel machines. In Proceedings of Advances in Neural Information Processing Systems, 2007, 20: 1160--1168

[13] Tibshirani R. Regression shrinkage and selection via the Lasso. J Royal Statis Soc (Series B), 1996, 58(1): 267--288

[14] Tikhonov A N. Solution of incorrectly formulated problems and the regularization method. Soviet Mathematics Doklady, 1963, 4: 1035--1038

[15] Vapnik V N. An overview of statistical learning theory. IEEE Trans Neural Networks, 1999, 10: 988--999

[16] Wu Q, Ying Y M, Zhou D X. Learning rates of least-square regularized regression. Found Comput Math, 2006, 6: 171--192

[17] Zhou D X. The covering number in learning theory. J Complexity, 2002, 18: 739--767

[18] Zhang T. Covering number bounds of certain regularized linear function classes. J Mach Lear Res, 2002, 2: 527--550

[19] Zhou S H, Lafferty J, Wasserman L. Compressed regression. IEEE Trans Infor Theory, 2009, 55: 846--866

Generalization Bounds of Compressed Regression Learning Algorithm

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 10

[1]	Li Wenxia, Qi Qiulan. Complex Approximation Properties of the Baskakov-Kantorovich Operators in Compact Disks [J]. Acta mathematica scientia,Series A, 2018, 38(4): 641-648.
[2]	Zhang Qian, Yuan Yongxin. An Iterative Updating Method for Undamped Vibration Systems Using Acceleration and Displacement Feedback [J]. Acta mathematica scientia,Series A, 2018, 38(2): 358-371.
[3]	Yuan Yongxin, Zhao Wenhua, Liu Hao. An Effective Iterative Updating Method for Undamped Structural Systems [J]. Acta mathematica scientia,Series A, 2016, 36(5): 886-900.
[4]	CHEN Chao-Ping, CHENG Jun-Xiang. Approximation Formulas for the Landau Constants [J]. Acta mathematica scientia,Series A, 2014, 34(5): 1245-1253.
[5]	DENG Wei-Qi. Viscosity Method for Hierarchical Fixed Point Approach to Hierarchical Variational Inclusion Problems [J]. Acta mathematica scientia,Series A, 2014, 34(5): 1254-1263.
[6]	TAN Qi-Jian, PAN Chao-Yi, LENG Zhong-Jian. Diffraction Problems for Quasilinear Elliptic Systems with Boundary Intersecting Interfaces [J]. Acta mathematica scientia,Series A, 2014, 34(4): 777-788.
[7]	QIAN Tao, WANG Jin-Xun, YANG Yan. MATCHING PURSUITS AMONG SHIFTED CAUCHY KERNELS IN HIGHER-DIMENSIONAL SPACES [J]. Acta mathematica scientia,Series A, 2014, 34(3): 660-672.
[8]	FU Ke-Aong. A Note on Strong Approximation for Trimmed Sums [J]. Acta mathematica scientia,Series A, 2013, 33(2): 267-275.
[9]	XIE Dong-Xiu, ZHANG Zhong-Zhi. Structured Matrix Nearness Problem with Least Square Spectra Constraint and Its Perturbation Analysis [J]. Acta mathematica scientia,Series A, 2013, 33(1): 37-45.
[10]	PENG Da-Heng. Pricing of Perpetual American Put with Fast Diffusion Process [J]. Acta mathematica scientia,Series A, 2012, 32(6): 1056-1062.
[11]	DU Hong-Ke, GAO Gui-Bao, WANG Rue-Qing. Geometry Characterizations Between Two Subspaces [J]. Acta mathematica scientia,Series A, 2012, 32(5): 879-891.
[12]	HU Shu-He, LI Xiao-Qin, YANG Wen-Zhi, WANG Xue-Jun. Bernstein Inequalities and Inverse Moments for Mixing Sequences [J]. Acta mathematica scientia,Series A, 2012, 32(3): 441-449.
[13]	DUAN Li-Qin. The Gel'f'and Approximations on Generalized Besov Classes B_p, _θ^Ω in the Deterministic and Monte Carlo Settings [J]. Acta mathematica scientia,Series A, 2012, 32(1): 148-160.
[14]	TIAN Xiao-Hong, ZHANG Kai-Yuan. Iterative Method for Centro-symmetric Solution of the Linear Matrix Equations [J]. Acta mathematica scientia,Series A, 2011, 31(6): 1526-1536.
[15]	JIANG Li, ZHU Shan-Hua, LV Yong. Approximation Order and Balance Order of Orthonormal Multiwavelets with Scale a [J]. Acta mathematica scientia,Series A, 2011, 31(4): 946-957.