The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances.
Anne DriemelJeff M. PhillipsIoannis PsarrosPublished in: CoRR (2019)
Keyphrases
- vc dimension
- hausdorff distance
- distance measure
- upper bound
- distance function
- sample complexity
- inductive inference
- concept classes
- vapnik chervonenkis dimension
- sample size
- distribution free
- statistical learning theory
- lower bound
- euclidean distance
- metric space
- covering numbers
- euclidean space
- empirical risk minimization
- generalization bounds
- worst case
- compression scheme
- data sets
- point sets
- pac learning
- concept class
- uniform convergence
- face recognition
- np hard
- similarity measure
- decision trees
- function classes
- special case
- small number
- similarity search
- metric learning