Abstract: This chapter shows how returning to the combinatorial nature of the Vapnik-Chervonenkis bounds provides simple ways to increase their accuracy, take into account properties of the data and of the learning algorithm, and provide empirically accurate estimates of the deviation between training error and testing error.

@incollection{bottou-2014c,
  author = {Bottou, L\'eon},
  title = {Making Vapnik-Chervonenkis bounds accurate},
  booktitle = {Measures of Complexity. Festschrift for Alexey Chervonenkis},
  publisher = {Springer},
  year = {2015},
  url = {http://leon.bottou.org/papers/bottou-2014c},
}