The DOI matches its Crossref record; 53 of the 53 references it cites were found in a registry or an index.
On the Generalization Ability of On-Line Learning Algorithms
Abstract
In this paper, it is shown how to extract a hypothesis with small risk from the ensemble of hypotheses generated by an arbitrary on-line learning algorithm run on an independent and identically distributed (i.i.d.) sample of data. Using a simple large deviation argument, we prove tight data-dependent bounds for the risk of this hypothesis in terms of an easily computable statistic M/sub n/ associated with the on-line performance of the ensemble. Via sharp pointwise bounds on M/sub n/, we then obtain risk tail bounds for kernel perceptron algorithms in terms of the spectrum of the empirical kernel matrix. These bounds reveal that the linear hypotheses found via our approach achieve optimal tradeoffs between hinge loss and margin size over the class of all linear functions, an issue that was left open by previous results. A distinctive feature of our approach is that the key tools for our analysis come from the model of prediction of individual sequences; i.e., a model making no probabilistic assumptions on the source generating the data. In fact, these tools turn out to be so powerful that we only need very elementary statistical facts to obtain our final risk bounds.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Wu, Y. (1999) · Technometrics · doi:10.1080/00401706.1999.10485951 · Cited by 27,221
The perceptron: A probabilistic model for information storage and organization in the brain.
Rosenblatt, F. (1958) · Psychological Review · doi:10.1037/h0042519 · Cited by 12,280
Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond
Schölkopf, B., & Smola, A. J. (2001) · The MIT Press eBooks · doi:10.7551/mitpress/4175.001.0001 · Cited by 11,703
The Nature of Statistical Learning Theory
Vapnik, V. N. (2000) · Springer eBooks · doi:10.1007/978-1-4757-3264-1 · Cited by 10,696
An Introduction to Support Vector Machines
Cristianini, N., & Shawe-Taylor, J. S. (2000) · ePrints Soton (University of Southampton) · Cited by 4,115
A Probabilistic Theory of Pattern Recognition
Devroye, L., Györfi, L., & Lugosi, G. (1996) · Stochastic Modelling and Applied Probability · doi:10.1007/978-1-4612-0711-5 · Cited by 3,274
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (2015) · Measures of Complexity · doi:10.1007/978-3-319-21852-6_3 · Cited by 3,105
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (1971) · Theory of Probability & Its Applications · doi:10.1137/1116025 · Cited by 2,448
Boosting the margin: a new explanation for the effectiveness of voting methods
Bartlett, P., Freund, Y., Lee, W. S., & Schapire, R. E. (1998) · The Annals of Statistics · doi:10.1214/aos/1024691352 · Cited by 2,306
The Weighted Majority Algorithm
Littlestone, N., & Warmuth, M. K. (1994) · Information and Computation · doi:10.1006/inco.1994.1009 · Cited by 1,975
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results
Bartlett, P. L., & Mendelson, S. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44581-1_15 · Cited by 1,949
Angluin, D. (1988) · Machine Learning · doi:10.1007/bf00116828 · Cited by 1,905
Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms
White, B. W., & Rosenblatt, F. (1963) · The American Journal of Psychology · doi:10.2307/1419730 · Cited by 1,792
Theoretical Foundations of the Potential Function Method in Pattern Recognition Learning
Айзерман, М. А. (1964) · Automation and Remote Control · Cited by 1,485
Bartlett, P. L. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.661502 · Cited by 1,166
Weighted sums of certain dependent random variables
Azuma, K. (1967) · Tohoku Mathematical Journal · doi:10.2748/tmj/1178243286 · Cited by 1,084
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
Ridge Regression Learning Algorithm in Dual Variables
Saunders, C. J., Gammerman, A., & Vovk, V. (1998) · ePrints Soton (University of Southampton) · Cited by 811
Ridge Regression: Biased Estimation for Nonorthogonal Problems
Hoerl, A. E., & Kennard, R. W. (2000) · Technometrics · doi:10.1080/00401706.2000.10485983 · Cited by 808
(2000) · CrossRef Listing of Deleted DOIs · doi:10.1162/153244302760200704 · Cited by 636
Cesa-Bianchi, N., Freund, Y., Haussler, D., Helmbold, D. P., Schapire, R. E., & Warmuth, M. K. (1997) · Journal of the ACM · doi:10.1145/258128.258179 · Cited by 634
Self-citationLarge Margin Classification Using the Perceptron Algorithm
Freund, Y., & Schapire, R. E. (1999) · Machine Learning · doi:10.1023/a:1007662407062 · Cited by 604
Structural risk minimization over data-dependent hierarchies
Shawe-Taylor, J., Bartlett, P. L., Williamson, R. C., & Anthony, M. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.705570 · Cited by 527
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm
Littlestone, N. (1988) · Machine Learning · doi:10.1007/bf00116827 · Cited by 497
Bousquet, O., Elisseeff, A., & Ron, D. (2001) · MPG.PuRe (Max Planck Society) · Cited by 493
Empirical Margin Distributions and Bounding the Generalization Error of Combined Classifiers
Koltchinskii, V., & Panchenko, D. (2002) · The Annals of Statistics · doi:10.1214/aos/1015362183 · Cited by 451
The Perceptron: A Model for Brain Functioning. I
Block, H. D. (1962) · Reviews of Modern Physics · doi:10.1103/revmodphys.34.123 · Cited by 396
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
Relative Loss Bounds for On-Line Density Estimation with the Exponential Family of Distributions
Azoury, K. S., & Warmuth, M. K. (2001) · Machine Learning · doi:10.1023/a:1010896012157 · Cited by 298
Model Selection and Error Estimation
Bartlett, P. L., Boucheron, S., & Lugosi, G. (2002) · Machine Learning · doi:10.1023/a:1013999503812 · Cited by 297
A Game of Prediction with Expert Advice
Vovk, V (1998) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1556 · Cited by 281
Beating the hold-out: bounds for K-fold and progressive cross-validation
Blum, A., Kalai, A., & Langford, J. (1999) · Proceedings of the twelfth annual conference on Computational learning theory · doi:10.1145/307400.307439 · Cited by 265
Additive versus exponentiated gradient updates for linear prediction
Kivinen, J., & Warmuth, M. K. (1995) · Proceedings of the twenty-seventh annual ACM symposium on Theory of computing - STOC '95 · doi:10.1145/225058.225121 · Cited by 223
A Second-Order Perceptron Algorithm
Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539703432542 · Cited by 196
Self-citationA sharp concentration inequality with applications
Boucheron, S., Lugosi, G., & Massart, P. (2000) · Random Structures and Algorithms · doi:10.1002/(sici)1098-2418(200005)16:3<277::aid-rsa4>3.0.co;2-1 · Cited by 185
Sequential prediction of individual sequences under general loss functions
Haussler, D., Kivinen, J., & Warmuth, M. K. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.705569 · Cited by 161
From On-line to Batch Learning
Littlestone, N. (1989) · Elsevier eBooks · doi:10.1016/b978-0-08-094829-4.50022-2 · Cited by 146
The Robustness of the p-Norm Algorithms
Gentile, C. (2003) · Machine Learning · doi:10.1023/a:1026319107706 · Cited by 145
Self-citationFrom on-line to batch learning
Littlestone, N. (1989) · Conference on Learning Theory · doi:10.5555/93335.93365 · Cited by 121
General Convergence Results for Linear Discriminant Updates
Grove, A. J., Littlestone, N., & Schuurmans, D. (2001) · Machine Learning · doi:10.1023/a:1010844028087 · Cited by 118
Linear Hinge Loss and Average Margin
Gentile, C., & Warmuth, M. K. (1998) · Cited by 110
Self-citationGeneralization error bounds for Bayesian mixture algorithms
Meir, R., & Zhang, T. (2003) · Cited by 107
Auer, P. L., & Warmuth, M. K. (1998) · Machine Learning · doi:10.1023/a:1007472513967 · Cited by 105
On the generalization of soft margin algorithms
Shawe-Taylor, J. S., & Cristianini, N. (2002) · IEEE Transactions on Information Theory · doi:10.1109/tit.2002.802647 · Cited by 84
Helmbold, D. P., & Warmuth, M. K. (1995) · Journal of Computer and System Sciences · doi:10.1006/jcss.1995.1044 · Cited by 74
Self bounding learning algorithms
Freund, Y. (1998) · doi:10.1145/279943.279993 · Cited by 48
The robustness of the p -norm algorithms
Gentile, C., & Littlestone, N. (1999) · Conference on Learning Theory · doi:10.1145/307400.307405 · Cited by 46
Self-citationVapnik, V. N. (1989) · Elsevier eBooks · doi:10.1016/b978-0-08-094829-4.50004-0 · Cited by 44
The complexity of learning according to two models of a drifting environment
Long, P. M. (1998) · Conference on Learning Theory · doi:10.1145/279943.279968 · Cited by 34
Herbrich, R., & Williamson, R. C. (2002) · ANU Open Research (Australian National University) · doi:10.1162/153244303765208368 · Cited by 29
An Improved Predictive Accuracy Bound for Averaging Classifiers
Langford, J. C., Seeger, M., & Megiddo, N. (2001) · Cited by 28
A Second-Order Perceptron Algorithm
Cesa‐Bianchi, N., Conconi, A., & Gentile, C. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45435-7_9 · Cited by 21
Self-citationMicrochoice Bounds and Self Bounding Learning Algorithms
Langford, J. C., & Blum, A. L. (2003) · Machine Learning · doi:10.1023/a:1022806918936 · Cited by 16
Cited by
(2010) · Cited by 8,261
Optimization Methods for Large-Scale Machine Learning
Bottou, L., Curtis, F. E., & Nocedal, J. (2018) · SIAM Review · doi:10.1137/16m1080173 · Cited by 3,128
Pegasos: primal estimated sub-gradient solver for SVM
Shalev-Shwartz, S., Singer, Y., Srebro, N., & Cotter, A. (2011) · Mathematical Programming · doi:10.1007/s10107-010-0420-4 · Cited by 1,477
Online Learning and Online Convex Optimization
Shalev-Shwartz, S. (2012) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000018 · Cited by 1,246
Foundations of Machine Learning
Mohri, M., Rostamizadeh, A., & Talwalkar, A. (2018) · doi:10.7551/mitpress/10290.001.0001 · Cited by 1,122
Metadata
- Authors
- Cesa-Bianchi, N., Conconi, A., & Gentile, C.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2004-09
- Volume
- 50
- Issue
- 9
- Pages
- 2050-2057
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2109339818
- Cited by
- 426
- References
- 53
- FWCI
- 11.52
- Type
- journal article
- Language
- en
- Open access
- closed
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.