VC dimension and distribution-free sample-based testing.
Eric BlaisRenato Ferreira Pinto Jr.Nathaniel HarmsPublished in: STOC (2021)
Keyphrases
- distribution free
- vc dimension
- sample size
- concept class
- upper bound
- sample complexity
- lower bound
- inductive inference
- concept classes
- generalization bounds
- learning machines
- normal distribution
- pac learning
- statistical learning theory
- compression scheme
- model selection
- worst case
- large deviations
- covariance matrix
- theoretical analysis
- euclidean space
- computational complexity