# Why does the assumption $|U_t| \le \frac1{p_{\min}}$ work in this paper?

I am reading a 2009 paper right now "Importance Weighted Active Learning" and on page 5, there is a theorem that uses the inequality $$|U_t| \leq \frac{1}{p_{\min}}$$. I am not sure how the paper found this assumption.

Theorem in question:

The theorem is for this importance weighted active learning algorithm:

Any help would be appreciated,

Thank you.

• Hi and Welcome to MO. I suggest you seriously edit your question, so that someone could read it without going through papers. Surely, you can write a self-contained question so that an expert can read it and respond. As it is, most chances you won't receive help. – Amir Sagiv Sep 27 '18 at 0:34

In the paper, $$$$U_t=\frac{Q_t}{p_t}\,l(h(x_t),y_t)-L(h)$$$$ and $$p_{\min}=\min_t p_t$$, where the values of $$Q_t$$ are in $$\{0,1\}$$ and the values of $$p_t$$ are in $$[0,1]$$. It appears that the condition that the values of the loss function $$l$$ are also in $$[0,1]$$ is missing in the paper before Theorem 1 on page 5; however, on page 6 I see "Since the loss values are normalized to lie in $$[0, 1]$$". Assuming that condition, we see that $$L(h)$$, being an expected value of $$l$$, is in $$[0, 1]$$ as well and hence in $$[0,1/p_{\min}]$$. So, $$U_t$$ is the difference of two values, each of them in $$[0,1/p_{\min}]$$. So, $$|U_t|\le1/p_{\min}$$.
Of course, without the condition that the values of $$l$$ are in $$[0,1]$$, the conclusion $$|U_t|\le1/p_{\min}$$ would in general be false.