Valid Generalisation from Approximate Interpolation
Martin Anthony, Peter L. Bartlett, Yuval Ishai, John S. Shawe-Taylor · Combinatorics Probability Computing · 1996
Let and be sets of functions from domain X to ℝ. We say that validly generalises from approximate interpolation if and only if for each η > 0 and ∈, δ ∈ (0,1) there is m 0 (η, ∈, δ) such that for any function t ∈ and any probability distribution on X , if m > m 0 then with m -probability at least 1 – δ, a sample X = ( x 1 , X 2 ,…, x m ) ∈ X m satisfies We find conditions that are necessary and sufficient for to validly generalise from approximate interpolation, and we obtain bounds on the sample length m 0 {η,∈,δ) in terms of various parameters describing the expressive power of .