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.
In the paper, \begin{equation} U_t=\frac{Q_t}{p_t}\,l(h(x_t),y_t)-L(h) \end{equation} 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.
