How to use expert advice

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

How to use expert advice

Full text

Pdf (1.15 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 382 - 391

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Nicolò Cesa-Bianchi
Yoav Freund
David P. Helmbold
David Haussler
Robert E. Schapire
Manfred K. Warmuth

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 30, Citation Count: 34

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/167088.167198 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	T. M. Cover. Behaviour of sequential predictors of binary sequences. In Transactions of the Fourth Prague Conference on Information Theory, Statistical Decision Functions, Random Processes, pages 263-272. Publishing House of the Czechoslovak Academy of Sciences, 1965.
	2	T. M. Cover and A. Shanhar. CompoundBayes predictors for sequences with apparent Markov structure. IEEE Transactzons on Systems, Man and Cybernetics, SMC-7(6):421-424, Jmm 1977.
	3	A. Dawid. Prequential data analysis. Current Issues in Statistical Inference, to appear.
	4	A. P. Dawid. Statistical theory: The prequential approach. Journal of the Royal Statistical Society, Series A, pages 278- 292, 1984.
	5	A. P. Dawid. Prequential analysis, stochastic complexity and Bayesian inference. Bayesian Statistics 4, to appear.
	6	Alfredo DeSantis , George Markowsky , Mark N. Wegman, Learning probabilistic prediction functions, Proceedings of the first annual workshop on Computational learning theory, p.312-328, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	7	M. Feder, N. Merhav, and M. Gutman. Universal prediction of individual sequences. IEEE Transactions on Information Theory, 38:1258-1270, 1992.
	8	Amos Fiat , Dean P. Foster , Howard Karloff , Yuval Rabani , Yiftach Ravid , Sundar Vishwanathan, Competitive algorithms for layered graph traversal, Proceedings of the 32nd annual symposium on Foundations of computer science, p.288-297, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185381]
	9	Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
	10	A. Fiat, Y. Rabani, and Y. Ravid. Competitive k-server algorithms. In 31st Annual Symposium on Foundations of Computer Science, pages 454-463, 1990.
	11	J. Galambos. The Asymptotic Theory of Extreme Oreder Stat2stics. R. E. Kreiger, second edition, 1987.
	12	3. Hamlan. Approximation to Bayes risk in repeated play. ha Contributions to the theory of games, volume 3, pages 97-139. Princeton University Press, 1957.
	13	D. Haussler and A. Barron. How well do Bayes methods work for on-line prediction of {+1, - 1 } values? In Proceedings of the Third NEC Symposium on Computation and Cognition. SIAM, to appear.
	14	David Haussler , Michael Kearns, Equivalence of models for polynomial learnability, Information and Computation, v.95 n.2, p.129-161, Dec. 1991 [doi>10.1016/0890-5401(91)90042-Z]
	15	David Haussler , Michael Kearns , Robert E. Schapire, Bounds on the Sample Complexity of Bayesian Learning Using Information Theory and the VC Dimension, Machine Learning, v.14 n.1, p.83-113, Jan. 1994 [doi>10.1023/A:1022698821832]
	16	D. Haussler , N. Littlestone , M. K. Warmuth, PREDICTING {0,1}-FUNCTIONS ON RANDOMLY DRAWN POINTS, University of California at Santa Cruz, Santa Cruz, CA, 1990
	17	D. Helmbold and M. K. Warmuth. On weak learning. In Proceedings of the Third NEC Research Symposium on Co'rnpurational Learning and Cognition. SIAM, to appear.
	18	David P. Helmbold , Manfred K. Warmuth, Some weak learning results, Proceedings of the fifth annual workshop on Computational learning theory, p.399-412, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130428]
	19	M. J. Kearns and R. E. Schapire. Efficient distributiolL-free learning of probabilistic concepts. In 31st Annual Symposium on Foundations of Computer Science, pages 382-391, 1990.
	20	Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward efficient agnostic learning, Proceedings of the fifth annual workshop on Computational learning theory, p.341-352, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130424]
	21	Nick Littlestone, From on-line to batch learning, Proceedings of the second annual workshop on Computational learning theory, p.269-284, December 1989, Santa Cruz, California, United States
	22	Nicholas Littlestone , Philip M. Long , Manfred K. Warmuth, On-line learning of linear functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.465-475, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103467]
	23	N. Littlestone and M. Warmuth. The weighted majority algorithm, in 30th Annual IEEE Symposium on Foundations of Computer Science, pages 256-261, 1989. Long version: UCSC tech. rep. UCSC-CRL-91-28.
	24	Neri Merhav , Meir Feder, Universal sequential learning and decision from individual data sequences, Proceedings of the fifth annual workshop on Computational learning theory, p.413-427, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130430]
	25	J. Rissanen. Modeling by shortest data description. Automatica, 14:465-471, 1978.
	26	J. Rissanen. Stochastic complexity and modeling. The Annals of Statistics, 14(3):1080-1100, 1986.
	27	J. Rissanen and G. G. Langdon, Jr. Universal modeling and coding. IEEE Transactions on Information Theory, IT- 27(1):12-23, Jan. 1981.
	28	H. S. Seung, H. Sompolinsky, and N. Tishby. Stati,#tical mechanics of learning from examples. Physical Review A, 45(8):6056-6091, 1992.
	29	H. Sompolinsky, N. Tishby, and H. Seung. Learning from examples in large neural networks. Physical Review Led!ters, 65:1683-1686, 1990.
	30	M. Talagrand. Sharper bounds for Gaussian and empirical processes. Annals of Probability, to appear.
	31	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
	32	V. Vapnik. Principles of risk minimization for learning theory. In J. E. Moody, S. J. Hanson, and R. P. Lippman, editors, Advances in Neural information Processing Systems 4. Morgan Kaufmann, 1992.
	33	Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
	34	Volodimir G. Vovk, Aggregating strategies, Proceedings of the third annual workshop on Computational learning theory, p.371-386, August 06-08, 1990, Rochester, New York, United States
	35	V. G. Vovk. Prequential probability theory. Unpublished manuscript, 1990.
	36	V. G. Vovk, Universal forecasting algorithms, Information and Computation, v.96 n.2, p.245-277, Feb. 1992 [doi>10.1016/0890-5401(92)90050-P]
	37	Kenji Yamanishi, A loss bound model for on-line stochastic prediction strategies, Proceedings of the fourth annual workshop on Computational learning theory, p.290-302, August 05-07, 1991, Santa Cruz, California, United States

CITED BY 34

	Nicolò Cesa Bianchi , Philip M. Long , Manfred K. Warmuth, Worst-case quadratic loss bounds for a generalization of the Widrow-Hoff rule, Proceedings of the sixth annual conference on Computational learning theory, p.429-438, July 26-28, 1993, Santa Cruz, California, United States
	David P. Helmbold , Robert E. Schapire, Predicting nearly as well as the best pruning of a decision tree, Proceedings of the eighth annual conference on Computational learning theory, p.61-68, July 05-08, 1995, Santa Cruz, California, United States
	Jyrki Kivinen , Manfred K. Warmuth, Additive versus exponentiated gradient updates for linear prediction, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.209-218, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Susanne Albers , Stefano Leonardi, On-line algorithms, ACM Computing Surveys (CSUR), v.31 n.3es, Sept. 1999
	Yoav Freund , Robert E. Schapire, Game theory, on-line prediction and boosting, Proceedings of the ninth annual conference on Computational learning theory, p.325-332, June 28-July 01, 1996, Desenzano del Garda, Italy
	Thomas H. Chung, Approximate methods for sequential decision making using expert advice, Proceedings of the seventh annual conference on Computational learning theory, p.183-189, July 12-15, 1994, New Brunswick, New Jersey, United States
	William W. Cohen , Yoram Singer, Context-sensitive learning methods for text categorization, ACM Transactions on Information Systems (TOIS), v.17 n.2, p.141-173, April 1999
	Avrim Blum , Adam Kalai, Universal portfolios with and without transaction costs, Proceedings of the tenth annual conference on Computational learning theory, p.309-313, July 06-09, 1997, Nashville, Tennessee, United States
	Avrim Blum, Empirical Support for Winnow and Weighted-MajorityAlgorithms: Results on a Calendar Scheduling Domain, Machine Learning, v.26 n.1, p.5-23, Jan. 1997
	Philip M. Long, On-line evaluation and prediction using linear functions, Proceedings of the tenth annual conference on Computational learning theory, p.21-31, July 06-09, 1997, Nashville, Tennessee, United States
	Robert D. Carr , Srinivas Doddi , Goran Konjevod , Madhav Marathe, On the red-blue set cover problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.345-353, January 09-11, 2000, San Francisco, California, United States
	Nicolò Cesa-Bianchi , Yoav Freund , David Haussler , David P. Helmbold , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Journal of the ACM (JACM), v.44 n.3, p.427-485, May 1997
	Yoav Freund , Robert E. Schapire , Yoram Singer , Manfred K. Warmuth, Using and combining predictors that specialize, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.334-343, May 04-06, 1997, El Paso, Texas, United States
	Olga Mitina , Nikolai Vereshchagin, How to use expert advice in the case when actual values of estimated events remain unknown, Proceedings of the eighth annual conference on Computational learning theory, p.91-97, July 05-08, 1995, Santa Cruz, California, United States
	Sally A. Goldman , Manfred K. Warmuth, Learning binary relations using weighted majority voting, Proceedings of the sixth annual conference on Computational learning theory, p.453-462, July 26-28, 1993, Santa Cruz, California, United States
	Michael Kearns , H. Sebastian Seung, Learning from a population of hypotheses, Proceedings of the sixth annual conference on Computational learning theory, p.101-110, July 26-28, 1993, Santa Cruz, California, United States
	V. Vovk, Derandomizing stochastic prediction strategies, Proceedings of the tenth annual conference on Computational learning theory, p.32-44, July 06-09, 1997, Nashville, Tennessee, United States
	Chamy Allenberg, Individual sequence prediction—upper bounds and application for complexity, Proceedings of the twelfth annual conference on Computational learning theory, p.233-242, July 07-09, 1999, Santa Cruz, California, United States
	Fernando Pereira , Yoram Singer, An efficient extension to mixture techniques for prediction and decision trees, Proceedings of the tenth annual conference on Computational learning theory, p.114-121, July 06-09, 1997, Nashville, Tennessee, United States
	Yoav Freund, Predicting a binary sequence almost as well as the optimal biased coin, Information and Computation, v.182 n.2, p.73-94, 01 May 2003
	David Helmbold , Sandra Panizza, Some label efficient learning results, Proceedings of the tenth annual conference on Computational learning theory, p.218-230, July 06-09, 1997, Nashville, Tennessee, United States
	Yoav Freund, Predicting a binary sequence almost as well as the optimal biased coin, Proceedings of the ninth annual conference on Computational learning theory, p.89-98, June 28-July 01, 1996, Desenzano del Garda, Italy
	V. G. Vovk, A game of prediction with expert advice, Proceedings of the eighth annual conference on Computational learning theory, p.51-60, July 05-08, 1995, Santa Cruz, California, United States
	Peter Auer , Philip M. Long, Simulating access to hidden information while learning, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.263-272, May 23-25, 1994, Montreal, Quebec, Canada
	Leslie G. Valiant, A neuroidal architecture for cognitive computation, Journal of the ACM (JACM), v.47 n.5, p.854-882, Sept. 2000
	David P. Helmbold , Robert E. Schapire, Predicting Nearly As Well As the Best Pruning of a Decision Tree, Machine Learning, v.27 n.1, p.51-68, April 1997
	Amotz Bar-Noy , Yishay Mansour, Competitive on-line paging strategies for mobile users under delay constraints, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Avrim Blum , Adam Kalai, Universal Portfolios With and Without Transaction Costs, Machine Learning, v.35 n.3, p.193-205, June 1999
	Nageswara S.V. Rao, On Fusers that Perform Better than Best Sensor, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.8, p.904-909, August 2001
	V. Vovk, Derandomizing Stochastic Prediction Strategies, Machine Learning, v.35 n.3, p.247-282, June 1999
	Shai Ben-David , Eyal Kushilevitz , Yishay Mansour, Online Learning versus Offline Learning, Machine Learning, v.29 n.1, p.45-63, Oct. 1997
	Adam J. Grove , Nick Littlestone , Dale Schuurmans, General convergence results for linear discriminant updates, Proceedings of the tenth annual conference on Computational learning theory, p.171-183, July 06-09, 1997, Nashville, Tennessee, United States
	Yoram Singer, Adaptive Mixtures of Probabilistic Transducers, Neural Computation, v.9 n.8, p.1711-1733, November 15, 1997
	Avrim Blum , Carl Burch, On-line Learning and the Metrical Task System Problem, Machine Learning, v.39 n.1, p.35-58, April 2000