An Introduction to Computational Learning Theory

For any class of functions H and distribution P, with probability 1 minus delta, for every h in H, the true error and empirical error on an i.i.d. sample of size m differ by at most a VC-dimension bound.

“A standard VC dimension bound (see, e.g. Kearns and Vazirani [1994]) states:”

For a data set of size n, with d1=VCDIM(H) and d2=VCDIM(G), the number of labellings induced by H and G is bounded as stated by Sauer's Lemma.

“Lemma 4.3 (Sauer's Lemma (see e.g. Kearns and Vazirani [1994])) . Let S be a data set of size n . Let d 1 = VCDIM( H ) and d 2 = VCDIM( G ) be the VC-dimensions of the two classes. Then”

With probability 1-δ, for every f in F_{H,G}, a uniform convergence inequality holds.

“This bound, together with a standard VC-Dimension based uniform convergence theorem (see e.g. Kearns and Vazirani [1994]) implies that with probability 1 , for every f h;g 2 F H ; G :”

A rigorous theory for how deep networks generalise might enable principled extrapolation from empirical testing on a limited validation domain to a broader test domain.

“For example, a rigorous theory for how deep networks generalise (as built towards by, e.g., Kearns & Vazirani, 1994;Watanabe, 2009;2018;Mingard et al., 2021;2020) might enable principled extrapolation from empirical testing on a limited validation domain to a broader test domain.”

Computational learning theory investigations have produced various formal guarantees for large classes of learning algorithms, primarily in the form of generalisation guarantees and regret bounds.

“These investigations have produced various formal guarantees for large classes of learning algorithms, primarily in the form of generalisation guarantees and regret bounds.”

These bounds typically show that a given learning algorithm under some given circumstances is guaranteed to attain a given level of performance with at least some given probability, and may also show how these probabilities scale in terms of the amount of training data.

“These bounds typically show that a given learning algorithm under some given circumstances is guaranteed to attain a given level of performance with at least some given probability, and may also show how these probabilities scale in terms of the amount of training data, etc (see e.g.Kearns & Vazirani, 1994).”