Combinatorics, Probability and Computing

Research Article

Valid Generalisation from Approximate Interpolation

Martin Anthonya1, Peter Bartletta2, Yuval Ishaia3 and John Shawe-Taylora4

a1 Department of Mathematics, The London School of Economics and Political Science, Houghton Street, London WC2A 2AE, UK Email:

a2 Department of Systems Engineering, Research School of Information Sciences and Engineering, Australian National University, Canberra 0200, Australia Email:

a3 Department of Computer Science, Technion, Haifa 32000, Israel

a4 Computer Science Department, Royal Holloway, University of London, Egham Hill, Egham, Surrey TW20 0EX, UK Email:


Let S096354830000198Xxs1D4D7 and S096354830000198Xxs1D49E be sets of functions from domain X to xs211D. We say that S096354830000198Xxs1D4D7 validly generalises S096354830000198Xxs1D49E from approximate interpolation if and only if for each η > 0 and xs2208, δ xs2208 (0,1) there is m0(η, xs2208, δ) such that for any function t xs2208 S096354830000198Xxs1D49E and any probability distribution S096354830000198Xxs1D4AB on X, if m > m0 then with S096354830000198Xxs1D4ABm-probability at least 1 – δ, a sample X = (x1, X2,…,xm) xs2208 Xm satisfies


We find conditions that are necessary and sufficient for S096354830000198Xxs1D4D7 to validly generalise S096354830000198Xxs1D49E from approximate interpolation, and we obtain bounds on the sample length m0{η,xs2208,δ) in terms of various parameters describing the expressive power of S096354830000198Xxs1D4D7.

(Received June 17 1994)

(Revised April 27 1995)


† Part of this research was carried out while Martin Anthony was visiting the Department of Systems Engineering, Australian National University.