Reference Request for VC Classes of Functions

Question

Vapnik-Chervonenkis (VC) classes of functions are important in empirical process theory, and in statistical learning theory. However, recovering the VC index (or VC dimension) of a class of functions is not easy.

I would like to compile a list of (useful) function classes that are also VC classes, but it has been surprisingly hard to find many examples of VC classes either online or in the classic empirical process texts...

Does anyone know of a reference that gives good (and many) examples of VC classes?

Answer 1

Unfortunately, I don't know of any such comprehensive list, but let me gather some of the disparate resources I've seen. Maybe it could be useful. Most of it is from the learning perspective.

---

Understanding Machine Learning: From Theory to Algorithms. Shalev-Schwartz & Ben-David. 2014.

• Has a relatively short section on VC dimension with some examples; however, it does recur in the book.

Foundations of Machine Learning. Mohri, Rostamizadeh, Talwalkar. 2012.

• Has a single section on VC dimension, but also quite a few examples (especially in the exercises).

Statistical Learning Theory. Vapnik. 1998.

• This one has a pretty significant exploration of VC dimensions and their applications, though the examples are a little scattered throughout the book.

The Nature of Statistical Learning Theory. Vapnik. 2013.

• Has some examples, but fewer than the other Vapnik book.

An Elementary Introduction to Statistical Learning Theory. Kulkarni & Harman. 2001

• Has two chapters on VC dimension but is a little light on examples.

Theory of Classification: A Survey of Some Recent Advances. Boucheron et al. 2005.

• This one discusses VC dimension a fair bit; however, I think its many references might be more useful.

---

Overall, perhaps surprisingly, I get the feeling that such a list will have to be constructed from individual papers in the literature on specific examples. Most of the recent VC dimension work I am aware of relates to neural networks (e.g. Nearly-tight VC-dimension bounds for piecewise linear neural networks. Harvey et al. 2017.) or other learners, like decision trees

---

Other related questions:

• Resource listing models with known VC dimension [TCS]

• Resource / book for recent advances in statistical learning theory [TCS]

• Introductory resources on Computational Learning Theory [TCS]