Optimal PAC Bounds Without Uniform Convergence.
Ishaq Aden-AliYeshwanth CherapanamjeriAbhishek ShettyNikita ZhivotovskiyPublished in: CoRR (2023)
Keyphrases
- uniform convergence
- vc dimension
- covering numbers
- sample complexity
- empirical risk minimization
- worst case
- upper bound
- generalization bounds
- learning rate
- sufficient conditions
- statistical learning theory
- upper and lower bounds
- lower bound
- reproducing kernel hilbert space
- sample size
- risk minimization
- generalization error
- large deviations
- concept classes
- distribution free
- pac learning
- optimal solution
- theoretical analysis
- mistake bound
- active learning
- feature selection
- function classes
- machine learning
- learning machines
- inductive inference
- compression scheme
- generalization ability