The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Rademacher penalties and structural risk minimization
Abstract
We suggest a penalty function to be used in various problems of structural risk minimization. This penalty is data dependent and is based on the sup-norm of the so-called Rademacher process indexed by the underlying class of functions (sets). The standard complexity penalties, used in learning problems and based on the VC-dimensions of the classes, are conservative upper bounds (in a probabilistic sense, uniformly over the set of all underlying distributions) for the penalty we suggest. Thus, for a particular distribution of training examples, one can expect better performance of learning algorithms with the data-driven Rademacher penalties. We obtain oracle inequalities for the theoretical risk of estimators, obtained by structural minimization of the empirical risk with Rademacher penalties. The inequalities imply some form of optimality of the empirical risk minimizers. We also suggest an iterative approach to structural risk minimization with Rademacher penalties, in which the hierarchy of classes is not given in advance, but is determined in the data-driven iterative process of risk minimization. We prove probabilistic oracle inequalities for the theoretical risk of the estimators based on this approach as well.
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
The Nature of Statistical Learning Theory
Vapnik, V. N. (1995) · doi:10.1007/978-1-4757-2440-0 · Cited by 39,138
Wu, Y. (1999) · Technometrics · doi:10.1080/00401706.1999.10485951 · Cited by 27,221
Weak Convergence and Empirical Processes
van der Vaart, A. W., & Wellner, J. A. (1996) · Springer Series in Statistics · doi:10.1007/978-1-4757-2545-2 · Cited by 5,014
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279
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
Learnability 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
On the method of bounded differences
McDiarmid, C. (1989) · Surveys in Combinatorics, 1989 · doi:10.1017/cbo9781107359949.008 · Cited by 1,425
Weighted sums of certain dependent random variables
Azuma, K. (1967) · Tohoku Mathematical Journal · doi:10.2748/tmj/1178243286 · Cited by 1,084
Uniform Central Limit Theorems
Dudley, R. M. (1999) · Cambridge University Press eBooks · doi:10.1017/cbo9780511665622 · Cited by 785
Asymptotic Theory of Finite Dimensional Normed Spaces
(1986) · Lecture Notes in Mathematics · doi:10.1007/bfb0075912 · Cited by 778
Risk bounds for model selection via penalization
Barron, A., Birgé, L., & Massart, P. (1999) · Probability Theory and Related Fields · doi:10.1007/s004400050210 · Cited by 657
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
New concentration inequalities in product spaces
Talagrand, M. (1996) · Inventiones Mathematicae · doi:10.1007/s002220050108 · Cited by 501
A Theory of Pattern Recognition
Амари, Ш.-И. (1968) · Jidō seigyo/Jido seigyo · Cited by 433
Some Limit Theorems for Empirical Processes
Gine, E., & Zinn, J. (1984) · The Annals of Probability · doi:10.1214/aop/1176993138 · Cited by 432
From Model Selection to Adaptive Estimation
Birgé, L., & Massart, P. (1997) · Festschrift for Lucien Le Cam · doi:10.1007/978-1-4612-1880-7_4 · Cited by 344
A Theory of Learning and Generalization
Vidyasagar, M. (1997) · Cited by 337
Talagrand, M. (1996) · The Annals of Probability · doi:10.1214/aop/1042644705 · Cited by 325
Model Selection and Error Estimation
Bartlett, P. L., Boucheron, S., & Lugosi, G. (2002) · Machine Learning · doi:10.1023/a:1013999503812 · Cited by 297
About the constants in Talagrand's concentration inequalities for empirical processes
Massart, P. (2000) · The Annals of Probability · doi:10.1214/aop/1019160263 · Cited by 280
On Talagrand's deviation inequalities for product measures
Ledoux, M. (1997) · ESAIM: Probability and Statistics · doi:10.1051/ps:1997103 · Cited by 255
Rademacher Processes and Bounding the Risk of Function Learning
Koltchinskii, V., & Panchenko, D. (2000) · High Dimensional Probability II · doi:10.1007/978-1-4612-1358-1_29 · Cited by 209
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
A central limit theorem for empirical processes
Pollard, D. (1982) · Journal of the Australian Mathematical Society Series A Pure Mathematics and Statistics · doi:10.1017/s1446788700018371 · Cited by 134
Model Selection and Error EstimationPreprint
Bartlett, P. L., Boucheron, S., & Lugosi, G. (2000) · SSRN Electronic Journal · doi:10.2139/ssrn.248567 · Cited by 88
Improved sample complexity estimates for statistical learning control of uncertain systems
Koltchinskii, V. I., Abdallah, C. T., Ariola, M., Dorato, P., & Panchenko, D. (2000) · IEEE Transactions on Automatic Control · doi:10.1109/9.895579 · Cited by 70
Self-citationConcept learning using complexity regularization
Lugosi, G., & Zeger, K. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.481777 · Cited by 64
Self bounding learning algorithms
Freund, Y. (1998) · doi:10.1145/279943.279993 · Cited by 48
Learning by canonical smooth estimation. II. Learning and choice of model complexity
Buescher, K. L., & Kumar, P. R. (1996) · IEEE Transactions on Automatic Control · doi:10.1109/9.489276 · Cited by 26
Valiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Cited by
(2006) · The MIT Press eBooks · doi:10.7551/mitpress/9780262033589.001.0001 · Cited by 4,280
A survey of cross-validation procedures for model selection
Arlot, S., & Celisse, A. (2010) · Statistics Surveys · doi:10.1214/09-ss054 · Cited by 3,522
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
Concentration Inequalities: A Nonasymptotic Theory of Independence
Boucheron, S., Lugosi, G., & Massart, P. (2013) · doi:10.1093/acprof:oso/9780199535255.001.0001 · Cited by 1,768
Kernel methods in machine learning
Hofmann, T., Schölkopf, B., & Smola, A. J. (2008) · The Annals of Statistics · doi:10.1214/009053607000000677 · Cited by 1,651
Metadata
- Authors
- Koltchinskii, V.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2001-07
- Volume
- 47
- Issue
- 5
- Pages
- 1902-1914
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2087258353
- Cited by
- 373
- References
- 32
- FWCI
- 10.51
- 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.