Improved bounds on the sample complexity of learning
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 1445318
- A general lower bound on the number of examples needed for learning
- Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension
- scientific article; zbMATH DE number 2087696
- Bounding sample size with the Vapnik-Chervonenkis dimension
Cites work
- A theory of the learnable
- An inequality involving multinomial probabilities
- Balls and bins: A study in negative dependence
- Convergence of stochastic processes
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- scientific article; zbMATH DE number 3904630 (Why is no real title available?)
- scientific article; zbMATH DE number 67607 (Why is no real title available?)
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Predicting \(\{ 0,1\}\)-functions on randomly drawn points
- Probability Inequalities for Sums of Bounded Random Variables
- Sharper bounds for Gaussian and empirical processes
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
Cited in
(57)- Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension
- Microchoice bounds and self bounding learning algorithms
- Fast approximation of betweenness centrality through sampling
- A general lower bound on the number of examples needed for learning
- On the sample complexity of weak learning
- Shape matching under rigid motion
- The true sample complexity of active learning
- Optimal approximations made easy
- The \(\varepsilon\)-\(t\)-net problem
- Near-optimal coresets of kernel density estimates
- Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
- Sampling-based algorithm for link prediction in temporal networks
- Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
- Estimation of the hardness of the learning with errors problem with a restricted number of samples
- Learning big (image) data via coresets for dictionaries
- The VC dimension of metric balls under Fréchet and Hausdorff distances
- The optimal sample complexity of PAC learning
- Refined error bounds for several learning algorithms
- Subsampling in smoothed range spaces
- Characterizing the sample complexity of private learners
- Core-sets: updated survey
- Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
- Theory of Classification: a Survey of Some Recent Advances
- scientific article; zbMATH DE number 408770 (Why is no real title available?)
- Submodular functions: learnability, structure, and optimization
- Improving the sample complexity using global data
- scientific article; zbMATH DE number 2087696 (Why is no real title available?)
- scientific article; zbMATH DE number 1827090 (Why is no real title available?)
- scientific article; zbMATH DE number 1445318 (Why is no real title available?)
- The Communication Complexity of Distributed epsilon-Approximations
- Practical low-dimensional halfspace range space sampling
- Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction
- scientific article; zbMATH DE number 7525513 (Why is no real title available?)
- Journey to the Center of the Point Set
- Distribution-sensitive bounds on relative approximations of geometric ranges
- Computing approximate statistical discrepancy
- Approximating the distribution of the median and other robust estimators on uncertain data
- scientific article; zbMATH DE number 7164746 (Why is no real title available?)
- scientific article; zbMATH DE number 7164768 (Why is no real title available?)
- The Learning Rate of lp -coefficient Regularized Shannon Sampling Algorithm
- PAC-MDL bounds.
- Bounds for validation
- On multiplicative \(\lambda\)-approximations and some geometric applications
- A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
- Safe multi-agent pathfinding with time uncertainty
- Computational sample complexity and attribute-efficient learning
- On coresets for support vector machines
- Estimating the clustering coefficient using sample complexity analysis
- Range minima queries with respect to a random permutation, and approximate range counting
- Relative (p, )-approximations in geometry
- Realizable learning is all you need
- Turning big data into tiny data: coresets for unsupervised learning problems
- Dimension-independent kernel -covers
- The impossibility of parallelizing boosting
- Metric entropy duality and the sample complexity of outcome indistinguishability
- Two proofs for shallow packings
- O(1)-Round MPC algorithms for multi-dimensional grid graph connectivity, Euclidean MST and DBSCAN
This page was built for publication: Improved bounds on the sample complexity of learning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5943102)
