\(\ell\)-norm and its application to learning theory (Q5936414)

We investigate connections between an important parameter in the theory of Banach spaces called the \(l\)-norm, and two properties of classes of functions which are essential in Learning Theory -- the uniform law of large numbers and the Vapnik-Chervonenkis (VC) dimension. We show that if the \(l\)-norm of a set of functions is bounded in some sense, then the set satisfies the uniform law of large numbers. Applying this result, we show that if \(X\) is a Banach space which has a nontrivial type, then the unit ball of its dual satisfies the uniform law of large numbers. Next, we estimate the \(l\)-norm of a set of \(\{0,1\}\)-functions in terms of its VC dimension. Finally, we present a `Gel'fand number' like estimate of certain classes of functions. We use this estimate to formulate a learning rule, which may be used to approximate functions from the unit balls of several Banach spaces.