{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:33Z","timestamp":1759637913779},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bf00993410","type":"journal-article","created":{"date-parts":[[2005,1,14]],"date-time":"2005-01-14T18:17:14Z","timestamp":1105726634000},"page":"187-230","source":"Crossref","is-referenced-by-count":3,"title":["On the complexity of function learning"],"prefix":"10.1007","volume":"18","author":[{"given":"Peter","family":"Auer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip M.","family":"Long","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Maass","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"Auer, P., & Long, P.M. (1994). Simulating access to hidden information while learning,Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (pp. 263?272).","DOI":"10.1145\/195058.195152"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"Auer, P., Long, P.M., Maass, W., & Woeginger, G.J. (1993). On the complexity of function learning,Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, pp. 392?401.","DOI":"10.1145\/168304.168384"},{"issue":"4","key":"CR3","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D. (1988). Queries and concept learning,Machine Learning, 2(4):319?342.","journal-title":"Machine Learning"},{"key":"CR4","unstructured":"Barland, I. (1992). Some ideas on learning with directional feedback. Master's thesis, Computer Science Department, UC Santa Cruz."},{"key":"CR5","first-page":"61","volume-title":"Error Correcting Codes","author":"E.R. Berlekamp","year":"1968","unstructured":"Berlekamp, E.R. (1968). Block coding for the binary symmetric channel with noiseless, delayless feedback, InError Correcting Codes (pp. 61?85), New York: Wiley."},{"key":"CR6","first-page":"1224","volume":"13","author":"J.M. Barzdin","year":"1972","unstructured":"Barzdin, J.M., & Frievald, R.V. (1972). On the prediction of general recursive functions,Soviet Math. Doklady, 13:1224?1228.","journal-title":"Soviet Math. Doklady"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"Cesa-Bianchi, N., Freund, Y., Helmbold, D.P., & Warmuth, M.K. (in press). On-line prediction and conversion strategies. InProceedings of the First Euro-COLT Workshop, The Institute of Mathematics and its Applications, to appear.","DOI":"10.1007\/BF00115301"},{"key":"CR8","unstructured":"Cesa-Bianchi, N., Long, P.M., & Warmuth, M.K. (1993). Worst-case quadratic loss bounds for a generalization of the Widrow-Hoff rule. InProceedings of the 6th Annual Workshop on Comput. Learning Theory (pp. 429?438)."},{"key":"CR9","unstructured":"Dawid, A. (1984). Statistical theory: The sequential approach.Journal of the Royal Statistical Society (Series A), pp. 278?292."},{"issue":"2","key":"CR10","doi-asserted-by":"crossref","first-page":"145","DOI":"10.3233\/FI-1991-15205","volume":"15","author":"V. Faber","year":"1991","unstructured":"Faber, V., & Mycielski, J. (1991). Applications of learning theorems.Fundamenta Informaticae, 15(2):145?167.","journal-title":"Fundamenta Informaticae"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"1258","DOI":"10.1109\/18.144706","volume":"38","author":"M. Feder","year":"1992","unstructured":"Feder, M., Merhav, N., & Gutman, M. (1992). Universal prediction of individual sequences.IEEE Transactions of Information Theory, 38:1258?1270.","journal-title":"IEEE Transactions of Information Theory"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"Kimber, D., & Long, P.M. (1992). The learning complexity of smooth functions of a single variable. InProc. 5th Annu. Workshop on Comput. Learning Theory (pp. 153?159).","DOI":"10.1145\/130385.130402"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"Kearns, M.J., Schapire, R.E., & Sellie, L.M. (1992). Toward efficient agnostic learning. InProc. 5th Annu. Workshop on Comput. Learning Theory (pp. 341?352).","DOI":"10.1145\/130385.130424"},{"key":"CR14","first-page":"285","volume":"2","author":"N. Littlestone","year":"1988","unstructured":"Littlestone, N. (1988). Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm,Machine Learning, 2:285?318.","journal-title":"Machine Learning"},{"key":"CR15","unstructured":"Littlestone, N. (1989).Mistake Bounds and Logarithmic Linear-threshold Learning Algorithms PhD thesis. Technical Report UCSC-CRL-89-11, University of California Santa Cruz."},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"Littlestone, N., Long, P.M., & Warmuth, M.K. (1991). On-line learning of linear functions. InProc. of the 23rd Symposium on Theory of Computing (pp. 465?475).","DOI":"10.1145\/103418.103467"},{"key":"CR17","unstructured":"Littlestone, N., & Warmuth, M.K. (1991). The weighted majority algorithm, Technical Report UCSC-CRL-91-28, UC Santa Cruz. A preliminary version appeared inthe Proceedings of the 30th Annual IEEE Symposium of the Foundations of Computer Science."},{"key":"CR18","unstructured":"Long, P.M., & Warmuth, M.K. (in press). Composite geometric concepts and polynomial predictability.Inform. Comput."},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"Maass, W. (1991). On-line learning with an oblivious environment and the power of randomization.Proc. 4th Annu. Workshop on Comput. Learning Theory (pp. 167?175).","DOI":"10.1016\/B978-1-55860-213-7.50019-5"},{"key":"CR20","first-page":"107","volume":"9","author":"W. Maass","year":"1992","unstructured":"Maass, W., & Tur\u00e1n, G. (1992). Lower bound methods and separation results for on-line learning models.Machine Learning, 9:107?145.","journal-title":"Machine Learning"},{"issue":"2","key":"CR21","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1090\/S0002-9939-1988-0943082-5","volume":"103","author":"J. Mycielski","year":"1988","unstructured":"Mycielski, J. (1988). A learning algorithm for linear operators.Proceedings of the American Mathematical Society, 103(2):547?550.","journal-title":"Proceedings of the American Mathematical Society"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1016\/0022-0000(80)90014-8","volume":"20","author":"R.L. Rivest","year":"1980","unstructured":"Rivest, R.L., Meyer, A.R., Kleitman, D.J., Winklmann, K., & Spencer, J. (1980). Coping with errors in binary search procedures.Journal of Computer and System Sciences, 20:396?404.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N. Sauer","year":"1972","unstructured":"Sauer, N. (1972). On the density of families of sets.J. Combinatorial Theory (A), 13:145?147.","journal-title":"J. Combinatorial Theory (A)"},{"issue":"2","key":"CR24","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0304-3975(92)90270-P","volume":"95","author":"J. Spencer","year":"1992","unstructured":"Spencer, J. (1992). Ulam's searching game with a fixed number of lies.Theoretical Computer Science, 95(2):307?321.","journal-title":"Theoretical Computer Science"},{"key":"CR25","unstructured":"Uspensky, J.V. (1948).Theory of Equations, McGraw-Hill."},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"Vovk, V. (1990). Aggregating strategies. InProc. 3rd Annu. Workshop on Comput. Learning Theory (pp. 371?383).","DOI":"10.1016\/B978-1-55860-146-8.50032-1"},{"issue":"2","key":"CR27","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0890-5401(92)90050-P","volume":"96","author":"V. Vovk","year":"1992","unstructured":"Vovk, V. (1992). Universal forecasting algorithms.Inform. Comput., 96(2):245?277.","journal-title":"Inform. Comput."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00993410.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00993410\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00993410","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,4]],"date-time":"2021-07-04T02:07:19Z","timestamp":1625364439000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00993410"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"references-count":27,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[1995]]}},"alternative-id":["BF00993410"],"URL":"https:\/\/doi.org\/10.1007\/bf00993410","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}