Online gradient descent regret bound

(OGD Regret Bound)

After $T$ steps, $\epsilon = [\sum_{i=1}^T f_i(\mathbf{x}^{(i)})]-[\sum_{i=1}^T f_i(\mathbf{x}^{*})] \leq RG\sqrt{T}$

average regret over time is bounded by $\frac{\epsilon}{T} \leq \frac{RG}{\sqrt{T}}$, goes $\rightarrow 0$ as $T \rightarrow \infty$

Note: no assumptions on how $f_1,…,f_T$ relate to each other, allowing even for these to be chosen adversarially, e.g. with $f_i$ depending on our choice of $\mathbf{x}_i$ and all previous choices.

See: Regret bound, Online regret bound