𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Fat-Shattering and the Learnability of Real-Valued Functions

✍ Scribed by Peter L. Bartlett; Philip M. Long; Robert C. Williamson

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
1011 KB
Volume
52
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the problem of learning real-valued functions from random examples when the function values are corrupted with noise. With mild conditions on independent observation noise, we provide characterizations of the learnability of a real-valued function class in terms of a generalization of the Vapnik Chervonenkis dimension, the fat-shattering function, introduced by Kearns and Schapire. We show that, given some restrictions on the noise, a function class is learnable in our model if an only if its fat-shattering function is finite. With different (also quite mild) restrictions, satisfied for example by guassion noise, we show that a function class is learnable from polynomially many examples if and only if its fat-shattering function grows polynomially. We prove analogous results in an agnostic setting, where there is no assumption of an underlying function class.

πŸ“œ SIMILAR VOLUMES

Extension of FrΓ©chet valued real analyti
Extension of FrΓ©chet valued real analytic functions from subvarieties of ℝd
✍ Dietmar Vogt πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 156 KB

## Abstract It is shown that for an algebraic subvariety __X__ of ℝ^__d__^ every FrΓ©chet valued real analytic function on __X__ can be extended to a real analytic function on ℝ^__d__^ if and only if __X__ is of type (PL), i.e. all of its singularities are of a certain type. Necessity of this cond

On the Fourier-Coefficients of Vector-Va
On the Fourier-Coefficients of Vector-Valued Functions
✍ Hermann KΓΆnig πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 522 KB

We study the decay of the FOURIER-coefficients of vector-valued functions F :T --+ X, X a BANAFH space. Differentiable functions f generally have absolutely sumrnable FOURIER-coefficients, 1 Ilf(n)ll < 00, iff X is K-convex. More precise statements on the decay of Ilf(n)ll for regular functions fcan