Exercise 5.4: From VC Dimension to Metric Entropy
(a)
Denote the symmetric difference of sets by \(A \symdif B = (A \setminus B) \cup (B \setminus C)\), and observe \(\| \ind_{S_i} - \ind_{S_j} \|_1 = \P (S_i \symdif S_j) > \delta\). The probability that each set of picked out points differs from any of the other sets by at least one point is \begin{align} 1 - \P(\exists i \neq j \colon X_k \in S_i \cap S_j, \forall k) &= 1 - \P\bigl( \bigcup_{i < j} \bigcap_{k=1}^n \lbrace X_k \in S_i \cap S_j \rbrace \bigr) \newline &\overset{\text{(i)}}{\geq} 1 - \sum_{i < j} \prod_{k} \P (X_k \in S_i \cap S_j) \newline &\overset{\text{(ii)}}{\geq} 1 - {N \choose 2} (1 - \delta)^n \, , \end{align} where (i) is by \(X_k \overset{\text{i.i.d.}}{\sim} \P\) combined with a union bound, and (ii) follows by \begin{align} \delta < \P (S_i \symdif S_j) \leq \P (S_i^\c \cup S_j^\c) = 1 - \P (S_i \cap S_j) \, . \end{align}
(b)
Take \(n = \frac{3}{\delta}\log N\) (or the smallest larger integer), and note \begin{align} {N \choose 2} (1 - \delta)^n \leq {N \choose 2} e^{-\delta n} \leq {N \choose 2} e^{-3 \log N} = \frac{N (N - 1)}{2 N^3} < 1 \end{align} which means there must exist a set of points \(x_1^n = x_1, \ldots, x_n\) from which \(\S\) picks out at least \(N\) non-identical subsets (otherwise the probability bound from (a) could not be larger than zero). Therefore \begin{align} N \leq \card(\S (x_1^n)) \leq \left( \frac{en}{\nu} \right)^\nu \leq \left( \frac{3 e \log N}{\delta \nu} \right)^\nu \end{align} where the second inequality is by the tighter version of the Sauer-Shelah lemma from Exercise 4.11(b).
(c)
Let us first assume \(\log x \leq m^{1 - 2 / m} x^{1 / m}\) for all \(x , m > 0\). If this is true, then from (b) \begin{gather} N \leq e^\nu \left( \frac{\log N}{\nu} \right)^\nu \left( \frac{3}{\delta} \right)^\nu \leq e^\nu \left( \frac{(2\nu)^{1 - 1 / \nu} N^{1 / (2 \nu)}}{\nu} \right)^\nu \left( \frac{3}{\delta} \right)^\nu \newline \implies N \leq \frac{(2e)^{2\nu}}{(2\nu)^2} \left( \frac{3}{\delta} \right)^{2\nu} \, , \end{gather} where \((2e)^{2\nu} (2\nu)^{-2}\) is better than the required \((2\nu)^{2\nu - 1}\) for all \(\nu \geq 2\).
All that remains is thus to prove the initial inequality. The first-derivative \begin{align} \nabla_x [m^{1 - 2 / m} x^{1 / m} - \log x] = m^{-2 / m} x^{1 / m - 1} - x^{-1} \, , \end{align} shows there is a critical point at \(x = m^2\), where the second derivative equals \((1 - \frac{1}{m})m^{-4}\), implying \(x = m^2\) is a local minimum. Since \begin{gather} \lim_{x \to 0^+} m^{1 - 2 / m} x^{1 / m} - \log x = \infty \newline \lim_{x \to \infty} m^{1 - 2 / m} x^{1 / m} - \log x = \lim_{x \to \infty} \left(m^{1 - 2/m} \frac{x^{1/m}}{\log x} - 1 \right) \log x = \infty \end{gather} applying the L’Hopital’s rule in the last equality, \(x = m^2\) is the global minimum for any \(m > 0\). Substituting, the equation for the minimum is \(m - 2 \log m\) which can be shown to be positive with minimum at \(m = 2\). Hence \(m^{1 - 2 / m} x^{1 / m} > \log x\) for all \(x, m > 0\), as desired.
Notes
- In (b), we could have taken \(n = \frac{2}{\delta} \log N\), which would yield a slightly tighter bound. Substituting this result in (c), we would have obtained an improved bound of the order \(\bigl(\frac{2}{\delta}\bigr)^{\nu}\) instead.