An algorithmic theory of learning: Robust concepts and random projection
Open accessThe DOI matches its Crossref record; 47 of the 47 references it cites were found in a registry or an index.
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
Cortes, C., & Vapnik, V. (1995) · Machine Learning · doi:10.1007/bf00994018 · Cited by 59,421
The Nature of Statistical Learning Theory
Vapnik, V. N. (1995) · doi:10.1007/978-1-4757-2440-0 · Cited by 39,138
An introduction to probability theory and its applications
(1958) · Journal of the Franklin Institute · doi:10.1016/0016-0032(58)90688-4 · Cited by 29,269
Probability Inequalities for sums of Bounded Random Variables
Hoeffding, W. (1994) · Springer Series in Statistics · doi:10.1007/978-1-4612-0865-5_26 · Cited by 6,666
Advances in kernel methods: support vector learning
Schölkopf, B., Burges, C. J. C., & Smola, A. J. (1999) · doi:10.5555/299094 · Cited by 5,789
Basic objects in natural categories
Rosch, E., Mervis, C. B., Gray, W. D., Johnson, D. M., & Boyes-Braem, P. (1976) · Cognitive Psychology · doi:10.1016/0010-0285(76)90013-x · Cited by 5,643
Probability Inequalities for Sums of Bounded Random Variables
Hoeffding, W. (1963) · Journal of the American Statistical Association · doi:10.1080/01621459.1963.10500830 · Cited by 4,852
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Perceptrons: An Introduction to Computational Geometry
Minsky, M., & Papert, S. A. (1969) · Cited by 3,742
Geometric Algorithms and Combinatorial Optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1988) · Algorithms and Combinatorics · doi:10.1007/978-3-642-97881-4 · Cited by 3,431
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279
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
Extensions of Lipschitz mappings into a Hilbert space
Johnson, W. B., & Lindenstrauss, J. (1984) · Contemporary Mathematics · doi:10.1090/conm/026/737400 · Cited by 2,523
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
Mullin, A. A., & Rosenblatt, F. (1963) · The American Mathematical Monthly · doi:10.2307/2312103 · Cited by 2,209
An Introduction to Probability Theory and Its Applications
Feller, W., & Morse, P. M. (1958) · Physics Today · doi:10.1063/1.3062516 · Cited by 2,040
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
An Introduction to Computational Learning Theory
Kearns, M. J., & Vazirani, U. (1994) · doi:10.7551/mitpress/3897.001.0001 · Cited by 1,697
An Introduction To Probability Theory And Its Applications
Feller, W. (1950) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 1,246
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
Rosch, E. (1988) · Readings in Cognitive Science · doi:10.1016/b978-1-4832-1446-7.50028-5 · Cited by 946 · cited 5×
“These analogous characteristics would give rise to a protypical family member (say Robin for the bird family) because it embodies many of the characteristics which have a greater probability of appearing in these " random summaries " since they are more common in the family (small, feathers, flies) and not other chara…”
BackgroundResultInfluentialDatabase-friendly random projections
Achlioptas, D. (2001) · Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/375551.375608 · Cited by 699
Large Margin Classification Using the Perceptron Algorithm
Freund, Y., & Schapire, R. E. (1999) · Machine Learning · doi:10.1023/a:1007662407062 · Cited by 604
The Relaxation Method for Linear Inequalities
Agmon, S. (1954) · Canadian Journal of Mathematics · doi:10.4153/cjm-1954-037-2 · Cited by 549
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm
Littlestone, N. (1988) · Machine Learning · doi:10.1007/bf00116827 · Cited by 497
Recent views of conceptual structure.
Komatsu, L. K. (1992) · Psychological Bulletin · doi:10.1037//0033-2909.112.3.500 · Cited by 435
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
Two algorithms for nearest-neighbor search in high dimensions
Kleinberg, J. M. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258653 · Cited by 348
The Johnson-Lindenstrauss lemma and the sphericity of some graphs
Frankl, P., & Maehara, H. (1988) · Journal of Combinatorial Theory, Series B · doi:10.1016/0095-8956(88)90043-3 · Cited by 299
Generalization Performance of Support Vector Machines and Other Pattern Classifiers
Bartlett, P. L., & Shawe-Taylor, J. S. (1998) · The MIT Press eBooks · doi:10.7551/mitpress/1130.003.0007 · Cited by 286
The geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365733 · Cited by 190
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm
Littlestone, N. (1987) · 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · doi:10.1109/sfcs.1987.37 · Cited by 186
Early category and concept development: making sense of the blooming, buzzing confusion
(2009) · Choice Reviews Online · doi:10.5860/choice.46-5328 · Cited by 174
A polynomial-time algorithm for learning noisy linear threshold functions
Blum, A. L., FRIEZE, A. M., Kannan, R., & Vempala, S. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548492 · Cited by 129
Self-citationLearning linear threshold functions in the presence of classification noise
Bylander, T. (1994) · Conference on Learning Theory · doi:10.1145/180139.181176 · Cited by 105
An algorithmic theory of learning: robust concepts and random projection
Arriaga, R. I., & Vempala, S. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814637 · Cited by 96
Self-citationLimitations of Learning via Embeddings in Euclidean Half-Spaces
Ben-David, S., Eiron, N., & Simon, H. U. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44581-1_25 · Cited by 89
On learning a union of half spaces
Baum, E. B. (1990) · Journal of Complexity · doi:10.1016/0885-064x(90)90012-3 · Cited by 80
Efficient distribution-free learning of probabilistic concepts
Kearns, M. J., & Schapire, R. E. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89557 · Cited by 60
Learning noisy perceptrons by a perceptron in polynomial time
Cohen, E. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646140 · Cited by 56
What can neuropsychology tell us about category learning?
Knowlton, B. J. (1999) · Trends in Cognitive Sciences · doi:10.1016/s1364-6613(99)01292-9 · Cited by 37
Math modeling, neuropsychology, and category learning: Response to B. Knowlton (1999)
Nosofsky, R. M. (1999) · Trends in Cognitive Sciences · doi:10.1016/s1364-6613(99)01291-7 · Cited by 23
Perceptual vs conceptual categorization
Reed, S. K., & Friedman, M. P. (1973) · Memory & Cognition · doi:10.3758/bf03198087 · Cited by 23
On Kernels, Margins, and Low-Dimensional Mappings
Balcan, M.-F., Blum, A. L., & Vempala, S. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30215-5_16 · Cited by 21
Self-citationA neuroidal architecture for cognitive computation
Valiant, L. G. (1998) · Lecture notes in computer science · doi:10.1007/bfb0055091 · Cited by 11
Valiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Cited by
Analysis of Representations for Domain Adaptation
Ben-David, S., Blitzer, J., Crammer, K., & Pereira, F. (2007) · Advances in Neural Information Processing Systems 19 · doi:10.7551/mitpress/7503.003.0022 · Cited by 2,019
“Arriaga and Vempala [1] show that one c an achieve good prediction with random projections as long as the margin is sufficiently larg e.”
BackgroundDatabase-friendly random projections: Johnson-Lindenstrauss with binary coins
Achlioptas, D. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00025-4 · Cited by 1,392
Random projection in dimensionality reduction: applications to image and text data
Bingham, E., & Mannila, H. (2001) · Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/502512.502546 · Cited by 1,274
An elementary proof of a theorem of Johnson and Lindenstrauss
Dasgupta, S., & Gupta, A. (2003) · Random Structures & Algorithms · doi:10.1002/rsa.10073 · Cited by 932
Linformer: Self-Attention with Linear Complexity
Wang, S., Li, B. Z., Khabsa, M., Fang, H., & Ma, H. (2020) · arXiv · doi:10.48550/arxiv.2006.04768 · Cited by 867
“The main proof idea is based on the distributional Johnson–Lindenstrauss lemma (Linden-strauss, 1984) (JL, for short), the following version is from (Arriaga & Vempala, 2006).”
Background
Metadata
- Authors
- Arriaga, R. I., & Vempala, S.
- Venue
- Machine Learning
- Published
- 2006-03-28
- Volume
- 63
- Issue
- 2
- Pages
- 161-182
- ISSN
- 0885-6125 (ISSN-L)
- 1573-0565
- OpenAlex
- W1516726196
- Cited by
- 316
- References
- 47
- FWCI
- 19.14
- 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.