Concentration estimates for learning with ℓ¹-regularizer and data dependent hypothesis spaces

详细信息    查看全文

• 作者：Lei Shi^a ; ^{sl1983@mail.ustc.edu.cn"" rel=""nofollow} ; Yun-Long Feng^b ; ^{fyunlong2@student.cityu.edu.hk"" rel=""nofollow} ; Ding-Xuan Zhou^a ; ^{mazhou@cityu.edu.hk"" rel=""nofollow}
• 关键词：Learning theory ; Data dependent hypothesis space ; ; none ; color ; black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6WB3-51XR3RX-1&_mathId=mml7&_pii=S1063520311000157&_rdoc=9&_issn=10635203&_acct=C000053193&
• 刊名：Applied and Computational Harmonic Analysis
• 出版年：2011
• 出版时间：September 2011
• 年：2011
• 卷：31
• 期：2
• 页码：286-302
• 全文大小：277 K

文摘

We consider the regression problem by learning with a regularization scheme in a data dependent hypothesis space and ℓ¹-regularizer. The data dependence nature of the kernel-based hypothesis space provides flexibility for the learning algorithm. The regularization scheme is essentially different from the standard one in a reproducing kernel Hilbert space: the kernel is not necessarily symmetric or positive semi-definite and the regularizer is the ℓ¹-norm of a function expansion involving samples. The differences lead to additional difficulty in the error analysis. In this paper we apply concentration techniques with ℓ²-empirical covering numbers to improve the learning rates for the algorithm. Sparsity of the algorithm is studied based on our error analysis. We also show that a function space involved in the error analysis induced by the ℓ¹-regularizer and non-symmetric kernel has nice behaviors in terms of the ℓ²-empirical covering numbers of its unit ball.