# Proving $\log (N)$ mistake bound is “tight” for a learner when learning thresholds

I'm studying the online learning model and the Halving algorithm.

We've seen the threshold problem:

The domain is $X=\left\{ 1,2,...,N-1\right\}$, the label set is $Y=\{-1,1\}$ and the hypotheses class is $H=\left\{ h_{\theta}(x)=sign(x-\theta):\theta\in\left\{ \frac{1}{2},1+\frac{1}{2},...,(N-1)+\frac{1}{2}\right\} \right\}$

I'll denote the number of mistakes the learner $A$ does on the environment $E$ by $M(A,E) = \left|\left\{ i:\hat{y_{i}}=A_{\mbox{pred}}(x_{i})\neq y_{i}\right\} \right|$ where $E=\left\{ (x_{i},y_{i})\right\} _{i=1}^{n}$

For any environment $E$, the mistake bound for Halving is $M$(Halving,$E$)$\leq\left\lfloor \log N\right\rfloor$

Now I must prove that this bound is "tight", i.e., for any learning algorithm $A$ there exists a realizable environment $E$ such that $M(A,E)\geq \left\lfloor \log N\right\rfloor$

My try - I came to the conclusion that finding the correct $h^{*} \in H$ is pretty similar in this case to finding a value in a sorted array. Since we'll need at least $\left\lfloor \log N\right\rfloor$ comparisons, an algorithm $A$ which can find $h^{*}$ and make less than $\left\lfloor \log N\right\rfloor$ mistakes "can find a value in a sorted array in less than $\left\lfloor \log N\right\rfloor$ comparisons for any given array, which is a contradiction."

The sentence in quotes is my intuition, but I'm having trouble proving it formally.

Is this the right way to go?

Many thanks.

• You can try showing that if you do less than $\log N$ queries then you don't have enough information to determine the correct hypothesis (since you only have less than $\log N$ bits and there are $N$ possibilities). Formally, you could show that with less than $\log N$ comparisons, there are always at least two possible hypotheses which haven't been ruled out. – Yuval Filmus Feb 24 '14 at 19:59
• If you add more details regarding your model (e.g. what the function $M$ is), more people could help you. – Yuval Filmus Feb 24 '14 at 19:59
• @YuvalFilmus I added a description of M (I'm new to ML and don't know yet what's taken for granted and what isn't). As to your "formal" suggestion, the difficult part for me was to match comparisons and mistakes. The learner might make some comparisons but give the correct answer. In that case $M$ wouldn't be the number of comparisons. Or am I wrong? – Paz Feb 24 '14 at 20:47
• "The number of mistakes the learner $M$ does on the environment $E$" - I have no idea what this means. Imagine that I don't know anything about machine learning, and explain your model. – Yuval Filmus Feb 24 '14 at 21:17

I am assuming the learning model described in Wikipedia. The environment will maintain a set of hypothesis forming an interval $S = [h_\alpha,h_\beta]$ consistent with its current answers, and will ensure that the first $\log N$ answers by the algorithm are wrong. In the beginning, $S = H$. At each step, the environment presents the middle point of the interval (we're identifying hypotheses with points in the domain in a natural way). Depending on the learner's answer, the interval $S$ is halved so that the learner is wrong. This process can go on for $\log N$ steps, in each of which the learner is mistaken, so that in total the learner makes at least $\log N$ mistakes.

• "Depending on the learner's answer", this is the subtle and fundamental point I want to make sure I'm understanding: Since the learner's answers for our $x_i$ are deterministic (all $\hat{y_{i}}$ are fixed in advance), we can create the corresponding environment on which the learner is mistaken $\log N$ times? – Paz Feb 24 '14 at 21:38
• They don't have to be deterministic. It's an adversary argument: the environment doesn't decide on the hypothesis in advance, but rather chooses it to maximize the number of errors made by the learner, while keeping its answers consistent with at least one hypothesis. – Yuval Filmus Feb 24 '14 at 22:55
• Oh. I'm sorry I forgot to mention that I'm assuming both the learner and the environment are deterministic. For non-deterministic players we'll be able to achieve at most $\log N$ mistakes, or even more (while staying consistent with prev. labels)? – Paz Feb 25 '14 at 6:18
• I'm not sure what you mean by the environment being deterministic; you can implement the environment algorithm I describe deterministically. – Yuval Filmus Feb 25 '14 at 13:09