Question 6 Exam 2019

I have a question concerning question 6 exam 2019.

When I try with numerical values (b=3, a=0.5), I find that the upper bounds are equal for a much smaller value than 10b. Indeed, I obtains for the lower bounds of both t the following values :
\( T_C = \frac{\log(\frac{\epsilon}{100b})}{\log(1-\frac{a}{100})} \) and \( T_D = \frac{\log(\frac{\epsilon - b}{100b})}{\log(1-a)} \)
Which are not equal for \( \epsilon = 10b \), \( a \in (0,1) \)

Is it the right way to proceed? Does anyone have answered to that question ?

Top comment

Hello,
You're right that the threshold is not exactly at \(\varepsilon = 10b\), but it is definitely true that Oracle D is better than C in this regime. All other answers are false.
Hope that helps!

@thijs said:
Hello,
You're right that the threshold is not exactly at \(\varepsilon = 10b\), but it is definitely true that Oracle D is better than C in this regime. All other answers are false.
Hope that helps!

Could you please explain the full procedure on how to find the correct answer on this question? I am pretty lost, some guidance would be much appreciated.

My thought process is like this:

Observation:

  • Both rates have a term exponential in \(t\), which initially is 100b. For oracle D, this decays much faster.
  • Oracle D has an additional \(+b\), which is initially quite small compared to \(100b\), but it doesn't improve ever. If we want \(\varepsilon < b\), oracle D is in trouble.

Excluding answers that cannot be correct:

  • the algorithms do not converge equally fast
  • "oracle D over C if eps < 10b" is false, because we just said that if eps < b, oracle D doesn't work.

We now test whether "oracle D over C if eps > 10b" is correct.

  • The ">" looks correct: we know D is bad for small epsilon, and if \(\varepsilon >> b\), the second term is negligible.
  • Now we have to verify if \((1-a)^t < \frac{9}{100}\) happens quicker than \( (1-a/100)^t < \frac{10}{100} \). (edit)
    • Intuitively, 1/10 and 9/100 are very close, and the exponential terms make a big difference, so it sounds reasonable.
      • If \(a\) is close to 1, the D is clearly faster (requires only one step).
      • If \(a\) is close to 0, \(\log(1-a)\) behaves as \(-a\) (Taylor expansion), and hence \((1-a)^t\) like \( \exp(-at) \) so here it is also faster.
      • Now I'm sufficiently confident that everywhere in between it should hold too.

Hi. I am not the OP. Thanks for the explanation! I guess you meant \((1-a)^t < \frac{9}{100}\) and vice versa?

Page 1 of 1

Add comment

Post as Anonymous Dont send out notification