I want to solve the following problem:
Consider the noise-free classification setup. Let $\mathcal{F}$ denote an infinite class of (binary) classifiers with finite VC dimension $d$. Let $f* ∈ \mathcal{F}$ be the unknown target classifier. Assume we are in a semi-online setting, over $T$ rounds, described as follows: We are given the entire sample of unlabeled points $x_1, . . . , x_T$ offline (before the rounds start); but their labels $f^*(x_t)$ are still obtained one by one as in the standard online learning setup. In other words, at each round $t = 1, . . . , T$, we make a prediction for $f*(xt)$ using the entire unlabeled set $x_1, . . . , x_T$ and the labels $f*(x_1), . . . , f*(x_{t−1})$; a mistake corresponds to a prediction that is not equal to $f*(x_t)$. Prove that if $T ≥ d$, then there exists a semi-online learning algorithm that makes at most $d\log_2(\frac{eT}{d})$ mistakes.
I am allowed to use the following statements:
Assume that the Vapnik-Chervonenkis Dimension (VC-dim) of the family of events $\mathcal{A}=d$. Then for $n \geq d$ $$\mathcal{S}_\mathcal{A}(n) \leq \sum_{i=0}^d{n \choose i}$$ Where $\mathcal{S}_\mathcal{A}$ is the shatter function.
and
$$\sum_{i=0}^d{n \choose i} \leq (\frac{en}{d})^d$$
My idea is kind of using kmeans or the perceptron on the available data and use it to predict my next label. But I do not see how to achieve the bounds. Does anyone has an Idea?