On page 17 on the paper Online Learning with Predictable Sequences, we find a regret of an algorithm equal to

$$ \text{Reg}_T=\frac{R^2}{\eta}+\frac{\eta}{2}\sigma^2(T+logT+1) $$ where $T$ is the entire time, $\eta$ is learning rate, $R$ is constant, and $\sigma^2$ is the variance of data. The above using arithmetic mean-geometric mean inequality can be lower bounded by

$$ \sqrt{2}R\sigma\sqrt{T+logT+1}\leq \frac{R^2}{\eta}+\frac{\eta}{2}\sigma^2(T+logT+1) $$

why the left hand side is $\tilde{{O}}(\sigma\sqrt{T})$?

According to $\tilde{{O}}$ vs $O$, $\tilde{{O}}$ ignores logarithmic factors that means when $f(n) \in \tilde{O}(g(n))$ there exist a $k$ such that $f(n) \in O(g(n)\log^k g(n))$, now I have $f(T)=\sqrt{2}R\sigma\sqrt{T+logT+1}$, why I can write it $O(\sigma\sqrt{T}log^kT)=\tilde{O}(\sigma\sqrt{T})$? and what is my $k$?


What is $\tilde O$? There are two different definitions.

  • According to exercise 3.5 of Introduction to Algorightms by Corman et al., $\tilde O$ can mean $O$ with logarithmic factors ignored: $$\tilde O(g(n))= \{f(n): \text{there exist nonnegative constant } k \\ \text{ and positive constants } c, k, \text{ and }n_0 \text{ such that }\\ 0\le f(n)\le cg(n)(\log n)^k\text{ for all }n\ge n_0\}$$
  • According to Wikipedia entry, $f(n) = \tilde O(g(n))$ is shorthand for $f(n) = O(g(n)\left(\log g(n)\right)^k)$ for some $k$.

For any value $x>0$, $x^0=1$. If we take $k=0$ simply, we can see that for either definition, $$f(T)=\sqrt{2}R\sigma\sqrt{T+\log T+1}=O(\sigma \sqrt{T}) =O(\sigma \sqrt{T}\,1)=\tilde{O}(\sigma\sqrt{T})$$

Here is the explanation for the second equality in the above equation.

$\log T=o(T) \Rightarrow T+\log T+1=\Theta(T) \Rightarrow \sqrt{T+\log T+1}=\Theta(\sqrt T)$

W can also proceed more rigorously, using L'Hôpital's rule once.

$$\lim_{T\to\infty}\frac{\sqrt{T+\log T+1}}{\sqrt T} = \sqrt{\lim_{T\to\infty}\frac{T+\log T+1}{T}} = \sqrt{\lim_{T\to\infty}\frac{1+\frac1T}{1}}=1$$

  • $\begingroup$ my question is why $\tilde{\mathcal{O}}$ not $\mathcal{O}$ ? Could you address that? $\endgroup$
    – Saeed
    Dec 27 '18 at 15:56
  • $\begingroup$ I revised the statement to elaborate my question clearly, please take a look. $\endgroup$
    – Saeed
    Dec 27 '18 at 16:20
  • $\begingroup$ $\textbf{Wikipedia entry:}$ This notation is often used to obviate the "nitpicking" within growth-rates that are stated as too tightly bounded for the matters at hand (since $n\log k$ is always $o(n\epsilon)$ for any constant k and any $\epsilon > 0$). $\endgroup$
    – Sagnik
    Dec 29 '18 at 8:18
  • $\begingroup$ @Sagnik: I understand that. What I do not understand is why $O(T+\log T)=O(T\log T)$? $\endgroup$
    – Saeed
    Dec 30 '18 at 18:52
  • 1
    $\begingroup$ @Apass.Jack : But it is not in your answer anymore. You have revised your answer, and I want the accepted answer stands alone. $\endgroup$
    – Saeed
    Dec 30 '18 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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