Improved bounds on the sample complexity of learning
From MaRDI portal
Publication:5943102
DOI10.1006/jcss.2000.1741zbMath0990.68081OpenAlexW1991417304MaRDI QIDQ5943102
Aravind Srinivasan, Yi Li, Philip M. Long
Publication date: 9 September 2001
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.2000.1741
Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Logic in artificial intelligence (68T27)
Related Items (32)
Optimal approximations made easy ⋮ Unnamed Item ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ Journey to the Center of the Point Set ⋮ The VC dimension of metric balls under Fréchet and Hausdorff distances ⋮ Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning ⋮ Near-optimal coresets of kernel density estimates ⋮ Estimating the clustering coefficient using sample complexity analysis ⋮ Range minima queries with respect to a random permutation, and approximate range counting ⋮ Relative \((p,\varepsilon )\)-approximations in geometry ⋮ Shape matching under rigid motion ⋮ Unnamed Item ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ Core-Sets: Updated Survey ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ Fast approximation of betweenness centrality through sampling ⋮ A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sampling-based algorithm for link prediction in temporal networks ⋮ Two proofs for shallow packings ⋮ Learning big (image) data via coresets for dictionaries ⋮ Theory of Classification: a Survey of Some Recent Advances ⋮ On coresets for support vector machines ⋮ Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction ⋮ Unnamed Item ⋮ The Communication Complexity of Distributed epsilon-Approximations ⋮ Subsampling in Smoothed Range Spaces ⋮ Safe Multi-Agent Pathfinding with Time Uncertainty ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- Sharper bounds for Gaussian and empirical processes
- Predicting \(\{ 0,1\}\)-functions on randomly drawn points
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- A theory of the learnable
- Balls and bins: A study in negative dependence
- Probability Inequalities for Sums of Bounded Random Variables
- An inequality involving multinomial probabilities
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Convergence of stochastic processes
This page was built for publication: Improved bounds on the sample complexity of learning
