A note on a scale-sensitive dimension of linear bounded functionals in Banach spaces

Author: Leonid Gurvits*
Email: gurvits@research.nj.nec.com

Source: Theoretical Computer Science Vol. 261, Issue 1, 17 June 2001, pp. 81-90.

Abstract. We show that "B is of type p > 1" is a necessary and sufficient condition for a learnability of a class of linear bounded functionals with norm less_equal 1 restricted to the unit ball in Banach space B. On the way, we give very short probabilistic proof for Vapnik's result (Hilbert space and improved) and improve our result with Pascal Koiran for convex halls of indicator functions. The approach we use in this paper allows to connect various results about learnability and approximation.

*Research at Rutgers partially supported by the US Air Force Grant AFOSR-94-0293.

©Copyright 2001 Elsevier Science