Entropy numbers of convex hulls and an application to learning algorithms
Abstract. 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 nth dyadic entropy number of the absolutely convex hull acoA of A and cp,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.
