Obtaining a set of $O(\log n)$ classifiers using multiplicative weights algorithms

Question

I'm trying to find an algorithm that uses the multiplicative weights algorithm to obtain a set of $O(\log n)$ classifiers that classify a set $X=\{x_1, x_2, ...,x_n\}$ where the set of labels is $l \in\{0,1\}.$

The original question goes as follows:

Suppose we have a set $X=\{x_1,...,x_n\}$, each with a label $l_i\in \{0,1\}$, an hypothesis class $H$ and a learning algorithm $A$ that for every distribution $D$ on $X$ outputs a classifier $h\in H$, such that $P_{i\sim D}[h(x_i)=l_i]\geq 0.51$. Show an algorithm that produces a set of $T= O(\log n)$ classifiers $h^{(1)},h^{(2)},...,h^{(T)}$, such that the majority vote among these $T$ classifiers yields the correct label for all $1 ≤ i ≤ n$.

My idea was to use multiplicative weights where each example $x_1,...,x_n$ is an expert and the initial weight for each one is $w_i^{(1)}=1$, and $p_i^{(1)}=\frac{1}{\Phi^{(1)}}=\frac{1}{n}$, where $\Phi^{(t)} = \sum_{i=1}^n w_{i}^{(t)}$. In each iteration of the algorithm we run the learning algorithm $A$ and use the output $h$ to determine $\sum_{i=1}^n {p_i^{(t)}h(x_i)}$ and act accordingly just like in the classic multiplicative weights algorithm. We update the distribution of our experts $p_{i}^{(t+1)}=\frac{w_i^{(t+1)}}{\Phi^{(t+1)}}$ and their weight: $w_i^{(t+1)} = w_i^{(t)}e^{\epsilon l_i\cdot h(x_i)}$ which means giving more weight to examples the classifier made an error on, and leaving the weights of correctly classified examples unchanged, thus increasing the probability of falsely classified examples to the point where their accumulated mass is at least $0.51\Phi$ and then we feed that new distribution $\bar{p}$ to the algorithm $A$ in the next iteration and the classifier we get will certainly be right on some of them. What I'm still struggling with is how do I know that at some point there's a majority among the classifiers produced so far that classify each example correctly?

Answer 1

At each step, you are dividing the weights of correctly labelled elements by $e^{-\epsilon}$, and multiplying the weights of wrongly labelled elements by $e^{\epsilon}$. If a $p \geq 1/2 + \delta$ fraction of elements were labelled correctly and the current total weight is $\Phi$ then the new total weight is $$ (e^{-\epsilon} p + e^\epsilon (1-p)) \Phi \leq (e^{-\epsilon}(1/2+\delta) + e^{\epsilon} (1/2-\delta))\Phi = (1-2\delta \epsilon + O(\epsilon^2)) \Phi. $$ For small enough $\epsilon$, this is at most $\rho \Phi$, for some constant $\rho < 1$.

Initially, $\Phi = n$. After $t = C\log n$ iterations, $\Phi$ drops to $\rho^t \Phi < 1$ (for an appropriate choice of $C$). This means that all weights are less than $1$. If $a$ of the classifiers are correct on an element and $b$ are incorrect, then its total weight is $e^{(b-a)\epsilon}$. Since all weights are less than $1$, we see that $b < a$, and so a majority of the classifiers are correct on the element.