Bubeck [1]} provides a general bound on the regret of OMD with \(\rho \) -strongly convex mirror map \(\Phi \)  w.r.t a norm \(\left\Vert .\right\Vert \)  on a convex set \(\mathcal {S}\) . The map \(\Phi (x) = \frac{1}{2}\left\Vert x\right\Vert _q^2, q \in (1, 2]\)  is \(\rho =q-1\)  strongly convex w.r.t \(\left\Vert .\right\Vert _q\)  over \(\mathcal {D} = \mathbb {R}^N\)  a direct result from [2]}, the dual norm of \(\left\Vert .\right\Vert _q\)  is \(\left\Vert .\right\Vert _p\)  (Hölder's inequality). The gradients are bounded in the dual norm \(\left\Vert \nabla f_{r}(\mathbf {x}_t)\right\Vert _p \le L, \forall \mathbf {r} \in \mathcal {R}\) , take \(\mathcal {S} = \mathcal {X}\) , OMD algorithm satisfies:
\(\mathrm {Regret}_T(\mathrm {OMD}_\Phi ) \le \frac{D_{\Phi }(\mathbf {x}_*, \mathbf {x}_1)}{\eta } + \frac{\eta }{2 \rho } \sum ^T_{t=1} \left\Vert \mathbf {g}_t\right\Vert ^2_p\) 
