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
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.