A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs.
Alane M. de LimaMurilo V. G. da SilvaAndré Luís VignattiPublished in: J. Graph Algorithms Appl. (2023)
Keyphrases
- vc dimension
- upper bound
- empirical risk minimization
- sample complexity
- concept classes
- distribution free
- inductive inference
- statistical learning theory
- concept class
- vapnik chervonenkis dimension
- low dimensional
- shortest path
- sample size
- lower bound
- generalization bounds
- worst case
- euclidean space
- machine learning algorithms
- decision trees
- covering numbers