# Why $2R\sigma\sqrt{T+logT+1}=\tilde{{O}}(\sigma\sqrt{T})$?

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$$

• my question is why $\tilde{\mathcal{O}}$ not $\mathcal{O}$ ? Could you address that? – Saeed Dec 27 '18 at 15:56
• I revised the statement to elaborate my question clearly, please take a look. – Saeed Dec 27 '18 at 16:20
• $\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$). – Sagnik Dec 29 '18 at 8:18
• @Sagnik: I understand that. What I do not understand is why $O(T+\log T)=O(T\log T)$? – Saeed Dec 30 '18 at 18:52
• @Apass.Jack : But it is not in your answer anymore. You have revised your answer, and I want the accepted answer stands alone. – Saeed Dec 30 '18 at 20:22