The online convex optimization (OCO) framework introduced in [1]} and [2]} is employed to solve various learning problems ranging from spam filtering to portfolio selection and network routing, cf. [3]}. At each round \(t\)  an algorithm selects an action \(x_t\)  from a convex set \(\mathcal {X}\subseteq \mathbb {R}^N\)  and incurs cost \(f_t(x_t)\) , where the convex function \(f_t:\mathcal {X}\mapsto \mathbb {R}\)  is revealed after \(x_t\)  is decided. The algorithm's performance is measured using the metric of regret:
\(\mathcal {R}_T=\textstyle \sum _{t=1}^{T}\big ( f_t(x_t)-f_t(x^\star ) \big ), \) 
