{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T21:14:59Z","timestamp":1718658899764},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":4394,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1996,9]]},"abstract":"<jats:p>Let <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830000198Xxs1D4D7\" \/> and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830000198Xxs1D49E\" \/> be sets of functions from domain <jats:italic>X<\/jats:italic> to \u211d. We say that <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830000198Xxs1D4D7\" \/> validly generalises <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830000198Xxs1D49E\" \/> from approximate interpolation if and only if for each \u03b7 &gt; 0 and \u2208, \u03b4 \u2208 (0,1) there is <jats:italic>m<\/jats:italic><jats:sub>0<\/jats:sub>(\u03b7, \u2208, \u03b4) such that for any function <jats:italic>t<\/jats:italic> \u2208 <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830000198Xxs1D49E\" \/> and any probability distribution <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830000198Xxs1D4AB\" \/> on <jats:italic>X<\/jats:italic>, if <jats:italic>m<\/jats:italic> &gt; <jats:italic>m<\/jats:italic><jats:sub>0<\/jats:sub> then with <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830000198Xxs1D4AB\" \/><jats:sup>m<\/jats:sup>-probability at least 1 \u2013 \u03b4, a sample X = (<jats:italic>x<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>X<\/jats:italic><jats:sub>2<\/jats:sub>,\u2026,<jats:italic>x<\/jats:italic><jats:sub>m<\/jats:sub>) \u2208 <jats:italic>X<\/jats:italic><jats:sup>m<\/jats:sup> satisfies<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S096354830000198XeqnU1\" \/><\/jats:disp-formula><\/jats:p><jats:p>We find conditions that are necessary and sufficient for <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830000198Xxs1D4D7\" \/> to validly generalise <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830000198Xxs1D49E\" \/> from approximate interpolation, and we obtain bounds on the sample length <jats:italic>m<\/jats:italic><jats:sub>0<\/jats:sub>{\u03b7,\u2208,\u03b4) in terms of various parameters describing the expressive power of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830000198Xxs1D4D7\" \/>.<\/jats:p>","DOI":"10.1017\/s096354830000198x","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T07:13:14Z","timestamp":1221203594000},"page":"191-214","source":"Crossref","is-referenced-by-count":3,"title":["Valid Generalisation from Approximate Interpolation"],"prefix":"10.1017","volume":"5","author":[{"given":"Martin","family":"Anthony","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Bartlett","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Shawe-Taylor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S096354830000198X_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5254-2"},{"key":"S096354830000198X_ref024","doi-asserted-by":"crossref","unstructured":"[24] Anthony M. and Bartlett P. L. (1994) Function learning from interpolation. In preparation.","DOI":"10.1007\/3-540-59119-2_179"},{"key":"S096354830000198X_ref020","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"S096354830000198X_ref001","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"S096354830000198X_ref018","volume-title":"COLT'90, Proceedings 3rd Annual Workshop on Computational Learning Theory","author":"Anthony","year":"1990"},{"key":"S096354830000198X_ref019","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90179-R"},{"key":"S096354830000198X_ref017","volume-title":"Computational Learning Theory: EUROCOLT'93","author":"Anthony","year":"1994"},{"key":"S096354830000198X_ref022","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90126-9"},{"key":"S096354830000198X_ref010","volume-title":"COLT'89, Proceedings 2nd Workshop on Computational Learning Theory","author":"Ben-David","year":"1989"},{"key":"S096354830000198X_ref016","volume-title":"Estimation of Dependences Based on Empirical Data.","author":"Vapnik","year":"1982"},{"key":"S096354830000198X_ref023","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1008"},{"key":"S096354830000198X_ref021","doi-asserted-by":"publisher","DOI":"10.1007\/BF00114804"},{"key":"S096354830000198X_ref006","volume-title":"Proceedings IEEE Symposium on Foundations of Computer Science","author":"Alon","year":"1993"},{"key":"S096354830000198X_ref015","volume-title":"Computational Learning Theory: EUROCOLT'93","author":"Simon","year":"1994"},{"key":"S096354830000198X_ref013","volume-title":"Proceedings 6th ACM Workshop on Computational Learning Theory","author":"Natarajan","year":"1993"},{"key":"S096354830000198X_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"S096354830000198X_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90039-L"},{"key":"S096354830000198X_ref003","volume-title":"Computational Learning Theory: An Introduction.","author":"Anthony","year":"1992"},{"key":"S096354830000198X_ref012","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"S096354830000198X_ref002","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"S096354830000198X_ref014","volume-title":"Proceedings 6th ACM Workshop on Computational Learning Theory","author":"Simon","year":"1993"},{"key":"S096354830000198X_ref007","volume-title":"Proceedings 7th Annual ACM Conference on Computational Learning Theory","author":"Bartlett","year":"1994"},{"key":"S096354830000198X_ref011","volume-title":"Proceedings IEEE Symposium on Foundations of Computer Science","author":"Kearns","year":"1990"},{"key":"S096354830000198X_ref004","volume-title":"Machine Learning: A Theoretical Approach","author":"Natarajan","year":"1991"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354830000198X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T16:42:49Z","timestamp":1557679369000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354830000198X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,9]]}},"alternative-id":["S096354830000198X"],"URL":"https:\/\/doi.org\/10.1017\/s096354830000198x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}