Localization of VC classes: beyond local Rademacher complexities
DOI10.1016/j.tcs.2017.12.029zbMath1398.68471arXiv1606.00922OpenAlexW3022373602MaRDI QIDQ1663641
Steve Hanneke, Nikita Zhivotovskiy
Publication date: 22 August 2018
Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1606.00922
VC dimensionPAC learningstatistical learningempirical risk minimizationERMstar numberAlexander's capacitydisagreement coefficientlocal metric entropylocal Rademacher processMassart's noise conditionoffset Rademacher processshifted empirical process
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Empirical entropy, minimax regret and minimax risk
- Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
- Risk bounds for statistical learning
- Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
- Using the doubling dimension to analyze the generalization of learning algorithms
- Rates of growth and sample moduli for weighted empirical processes indexed by sets
- 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
- Consistency for the least squares estimator in nonparametric regression
- Model selection in nonparametric regression
- Information-theoretic determination of minimax rates of convergence
- ``Local vs. ``global parameters -- breaking the Gaussian complexity barrier
- A general lower bound on the number of examples needed for learning
- Learning and generalisation. With applications to neural networks.
- Oracle inequalities for cross-validation type procedures
- Local Rademacher complexities and oracle inequalities in risk minimization. (2004 IMS Medallion Lecture). (With discussions and rejoinder)
- A new PAC bound for intersection-closed concept classes
- Concentration inequalities and asymptotic results for ratio type empirical processes
- Convergence of estimates under dimensionality restrictions
- Local Rademacher complexities
- Minimax Analysis of Active Learning
- Refined Error Bounds for Several Learning Algorithms
- Theory of Classification: a Survey of Some Recent Advances
- Empirical and Poisson processes on classes of sets or functions too large for central limit theorems
- Neural Network Learning
- Theory of Disagreement-Based Active Learning
- Information-Based Complexity, Feedback and Dynamics in Convex Programming
- Upper and Lower Bounds for Stochastic Processes
- Combinatorial methods in density estimation
This page was built for publication: Localization of VC classes: beyond local Rademacher complexities
