Entropy numbers of convex hulls and an application to learning algorithms

摘要

Given a positive sequence $ a = (a_n) in ell_{p,q} $ , for 0 < p < 2 and $ 0 < q leq infty $ , and a finite set $ A = {x_1, dots , x_m} subset ell_2 $ with $ |x_i| leq a $ for all $ i = 1, dots , m $ we prove¶¶ $ |(e_{n}(textrm{aco}A))|_{p,q} leq c_{p,q} sqrt{textrm{log}(m + 1)},, |a|_{p,q}, $ ¶¶where $ e_{n}(textrm{aco}A $ is the n th dyadic entropy number of the absolutely convex hull acoA of A and c p,q > 0 is a suitable constant only depending on p and q. Moreover we show that this is asymptotically optimal in M for the most interesting case $ q = infty $ .¶As an application we give an upper bound for the so-called growth function which is of special interest in the theory of learning algorithms.