And we define its dual norm to be \(\Vert \nabla \hspace{-1.38885pt}\Vert _H^*=\sqrt{\nabla \hspace{-1.38885pt}^{\top } H^{-1} \nabla \hspace{-1.38885pt}}\) . In particular, we denote \({\mathcal {H}}=\lbrace  H| H\succeq 0, tr(H)\le d\rbrace \) . An optimal blackbox online learning algorithm is also needed for our construction. We consider Adagrad from [1]}, which is able to achieve the following regret if run on \(I=[s,t]\) :
\(\mbox{{Regret}}(I)=O\left(D d^{\frac{1}{2}} \min _{H\in {\mathcal {H}}} \sqrt{\sum _{\tau =s}^t \nabla \hspace{-1.38885pt}_{\tau }^{\top } H^{-1} \nabla \hspace{-1.38885pt}_{\tau }}\right)\) 
