3
$\begingroup$

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:

Theorem in question


The theorem is for this importance weighted active learning algorithm:

The theorem is for this importance weighted active learning algorithm

Any help would be appreciated,

Thank you.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Amir Sagiv Sep 27 '18 at 0:34
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.