
Using Lemma 1 in [1]} and equation (REF ) to bound the first term and Proposition REF  to bound the second term, we obtain that \(|{\langle g^{(m)}(\theta ),\hat{\theta }_m \rangle }-{\langle g(\theta ),\theta _\star  \rangle }|\le \gamma _m/2\)  with probability at least \(1-c/T\) . A standard calculation in Theorem 1 in [1]} implies a regret bound of \(\tilde{O}(d\sqrt{T}+d^{1.5}C)\)  with high probability. Hence, Theorem 4 in [3]} implies a regret bound of \(\tilde{O}(d\sqrt{T}+d^{1.5}C)\)  with high probability for G-COBE with unknown \(C\) . Applying Theorem REF  and proceeding as in equation (REF ) concludes the proof.
