The DOI matches its Crossref record; 48 of the 48 references it cites were found in a registry or an index.
How to use expert advice
Open accessAbstract
We analyze algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts. Our analysis is for worst-case situations, i.e., we make no assumptions about the way the sequence of bits to be predicted is generated. We measure the performance of the algorithm by the difference between the expected number of mistakes it makes on the bit sequence and the expected number of mistakes made by the best expert on this sequence, where the expectation is taken with respect to the randomization in the predictins. We show that the minimum achievable difference is on the order of the square root of the number of mistakes of the best expert, and we give efficient algorithms that achieve this. Our upper and lower bounds have matching leading constants in most cases. We then show how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently know in this context. We also compare our analysis to the case in which log loss is used instead of the expected number of mistakes.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Neural Networks: A Comprehensive Foundation
Haykin, S. (1998) · Cited by 30,070
Advances in Neural Information Processing Systems 14: Proceedings of the 2001 Conference
(2002) · The MIT Press eBooks · doi:10.7551/mitpress/1120.001.0001 · Cited by 8,890
Neural networks: A comprehensive foundation
Tadeusiewicz, R. (1995) · Control Engineering Practice · doi:10.1016/0967-0661(95)90080-2 · Cited by 7,218
Modeling by shortest data description
Rissanen, J. (1978) · Automatica · doi:10.1016/0005-1098(78)90005-5 · Cited by 6,011
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279
Estimation of Dependences Based on Empirical Data
Vapnik, V. (2006) · Information Science and Statistics · doi:10.1007/0-387-34239-7 · Cited by 2,238
The Weighted Majority Algorithm
Littlestone, N., & Warmuth, M. K. (1994) · Information and Computation · doi:10.1006/inco.1994.1009 · Cited by 1,975
Self-citationLearnability and the Vapnik-Chervonenkis dimension
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989) · Journal of the ACM · doi:10.1145/76359.76371 · Cited by 1,839
Self-citationThe Asymptotic Theory of Extreme Order Statistics
Angus, J. E. (1990) · Technometrics · doi:10.1080/00401706.1990.10484616 · Cited by 1,830
Contributions to the theory of games.
(1960) · Journal of the Franklin Institute · doi:10.1016/0016-0032(60)90366-5 · Cited by 1,824
Proceedings of the 56th Annual ACM Symposium on Theory of Computing
(2024) · doi:10.1145/3618260 · Cited by 1,730
THE ASYMPTOTIC THEORY OF EXTREME ORDER STATISTICS
GALAMBOS, J. (1977) · The Theory and Applications of Reliability with Emphasis on Bayesian and Nonparametric Methods · doi:10.1016/b978-0-12-702101-0.50014-7 · Cited by 1,512
Dawid, A. P. (1984) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2981683 · Cited by 1,085 · cited 1×
“We take the extreme position, as advocated by Dawid and Vovk in the theory of prequential probability [Dawid 1984; 1991; 1996; Vovk 1993], Rissanen in his theory of stochastic complexity [Rissanen 1978; 1986; Rissanen and Langdon Jr. 1981; Yamanishi 1995], and Cover, Lempel and Ziv, Feder and…”
BackgroundStochastic Complexity and Modeling
Rissanen, J. (1986) · The Annals of Statistics · doi:10.1214/aos/1176350051 · Cited by 922
Estimation of Dependences Based on Empirical Data.
Shoesmith, E., Vapnik, V., & Kotz, S. (1984) · The Statistician · doi:10.2307/2988246 · Cited by 764
Principles of Risk Minimization for Learning Theory
Vapnik, V. N. (1991) · neural information processing systems · Cited by 692
Vovk, V. G. (1990) · Conference on Learning Theory · doi:10.5555/92571.92672 · Cited by 551
Statistical mechanics of learning from examples
Seung, H. S., Sompolinsky, H., & Tishby, N. (1992) · Physical Review A · doi:10.1103/physreva.45.6056 · Cited by 532
Sharper Bounds for Gaussian and Empirical Processes
Talagrand, M. (1994) · The Annals of Probability · doi:10.1214/aop/1176988847 · Cited by 480
Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., & Young, N. E. (1991) · Journal of Algorithms · doi:10.1016/0196-6774(91)90041-v · Cited by 457
Rissanen, J., & Langdon, G. (1981) · IEEE Transactions on Information Theory · doi:10.1109/tit.1981.1056282 · Cited by 454
Universal prediction of individual sequences
Feder, M., Merhav, N., & Gutman, M. (1992) · IEEE Transactions on Information Theory · doi:10.1109/18.144706 · Cited by 373
Efficient distribution-free learning of probabilistic concepts
Kearns, M. J., & Schapire, R. E. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80062-5 · Cited by 373
Self-citationToward efficient agnostic learning
Kearns, M. J., Schapire, R. E., & Sellie, L. M. (1992) · Proceedings of the fifth annual workshop on Computational learning theory · doi:10.1145/130385.130424 · Cited by 330
Self-citationStone, M. (1978) · Series Statistics · doi:10.1080/02331887808801414 · Cited by 220
Rates of convergence for minimum contrast estimators
Birgé, L., & Massart, P. (1993) · Probability Theory and Related Fields · doi:10.1007/bf01199316 · Cited by 211
Toward Efficient Agnostic Learning
Kearns, M. J., Schapire, R. E., & Sellie, L. M. (1994) · Machine Learning · doi:10.1007/bf00993468 · Cited by 172
Self-citationLearning from examples in large neural networks
Sompolinsky, H., Tishby, N., & Seung, H. S. (1990) · Physical Review Letters · doi:10.1103/physrevlett.65.1683 · Cited by 152
Cesa‐Bianchi, N., Freund, Y., Helmbold, D. P., Haussler, D. H., Schapire, R. E., & Warmuth, M. K. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167198 · Cited by 143
Self-citationCompetitive k-server algorithms
Fiat, A., Rabani, Y., & Ravid, Y. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80060-1 · Cited by 135
Equivalence of models for polynomial learnability
Haussler, D. H., Kearns, M. J., Littlestone, N., & Warmuth, M. K. (1991) · Information and Computation · doi:10.1016/0890-5401(91)90042-z · Cited by 134
Self-citationFrom on-line to batch learning
Littlestone, N. (1989) · Conference on Learning Theory · doi:10.5555/93335.93365 · Cited by 121
A Logic of Probability, with Application to the Foundations of Statistics
Vovk, V. (1993) · Journal of the Royal Statistical Society Series B (Statistical Methodology) · doi:10.1111/j.2517-6161.1993.tb01904.x · Cited by 113
BEHAVIOR OF SEQUENTIAL PREDICTORS OF BINARY SEQUENCES.
Cover, T. M. (1966) · Cited by 108
Universal schemes for sequential decision from individual data sequences
Merhav, N., & Feder, M. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.243445 · Cited by 102
Tight worst-case loss bounds for predicting with expert advice
Haussler, D. H., Kivinen, J., & Warmuth, M. K. (1995) · Lecture notes in computer science · doi:10.1007/3-540-59119-2_169 · Cited by 99
Self-citationLearning probabilistic prediction functions
Santis, A. D., Markowsky, G., & Wegman, M. N. (1988) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1988.21929 · Cited by 95
Helmbold, D. P., & Warmuth, M. K. (1995) · Journal of Computer and System Sciences · doi:10.1006/jcss.1995.1044 · Cited by 74
Self-citationDawid, A. P. (1992) · Lecture notes-monograph series · doi:10.1214/lnms/1215458842 · Cited by 61
Universal forecasting algorithms
Vovk, V. (1992) · Information and Computation · doi:10.1016/0890-5401(92)90050-p · Cited by 53
Competitive algorithms for layered graph traversal
Fiat, A., Foster, D. P., Karloff, H. J., Rabani, Y., Ravid, Y., & Viswanathan, S. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1991.185381 · Cited by 46
Compound Bayes Predictors for Sequences with Apparent Markov Structure
Cover, T. M., & Shenhar, A. J. (1977) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1977.4309738 · Cited by 37
On-line learning of linear functions
Littlestone, N., Warmuth, M. K., & Long, P. M. (1995) · Computational Complexity · doi:10.1007/bf01277953 · Cited by 29
Self-citationUsing Experts for Predicting Continuous OutcomesPreprint
Kivinen, J., & Warmuth, M. K. (1994) · RePEc: Research Papers in Economics · Cited by 22
Self-citationApproximate methods for sequential decision making using expert advice
Chung, T. H. (1994) · Annual Conference on Computational Learning Theory (COLT) · doi:10.1145/180139.181097 · Cited by 21
A Loss Bound Model for On-Line Stochastic Prediction Algorithms
Yamanishi, K. (1995) · Information and Computation · doi:10.1006/inco.1995.1076 · Cited by 14
Bounds on the Sample Complexity of Bayesian Learning Using Information Theory and the VC Dimension
Haussler, D. H., Kearns, M., & Schapire, R. E. (1994) · Machine Learning · doi:10.1023/a:1022698821832 · Cited by 8
Self-citationValiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Cited by
Pattern Recognition and Neural Networks
Ripley, B. D. (1996) · Cambridge University Press eBooks · doi:10.1017/cbo9780511812651 · Cited by 6,459
Prediction, Learning, and Games
Cesa-Bianchi, N., & Lugosi, G. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546921 · Cited by 3,162
Self-citation(2002) · doi:10.1137/s0097539701398375 · Cited by 2,275
Foundations of Machine Learning
Mohri, M., Rostamizadeh, A., & Talwalkar, A. (2018) · doi:10.7551/mitpress/10290.001.0001 · Cited by 1,122
Large margin classification using the perceptron algorithm
Freund, Y., & Schapire, R. E. (1998) · Proceedings of the eleventh annual conference on Computational learning theory · doi:10.1145/279943.279985 · Cited by 1,071
Self-citation
Metadata
- Authors
- Cesa-Bianchi, N., Freund, Y., Haussler, D., Helmbold, D. P., Schapire, R. E., & Warmuth, M. K.
- Venue
- Journal of the ACM
- Published
- 1997-05
- Volume
- 44
- Issue
- 3
- Pages
- 427-485
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W1979675141
- Cited by
- 634
- References
- 48
- FWCI
- 26.34
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.