Online Convex Optimization sees optimization as a continuous process in which the algorithm learns new aspects of the problem and improves upon.
Every iteration consists of the player making a decision $x_t$ from a convex and bounded decision set $\mathcal{X}$. After we made our decision the adversary returns the loss for our decision, $f_t(x_t)$. Often the gradient of the loss function is accessible too, $\nabla_{x_t}f_t(x_t)$. This loss function $f_t$ can change, follow any distribution, but is always convex and bounded.
Any OCO algorithm (such as online mirrored descent or regularized follow the leader) aims to minimize regret, the loss of your decisions minus the loss of the best decisions in hindsight. This is defined as $\mathcal{R}_T := \sum_{t=1}^Tf_t(x_t) - \min_x \sum_{t=1}^Tf_t(x)$.
Using (a.o.) two bounds; $$ ||x - y|| \leq D \quad \forall \quad x, y \in \mathcal{X}$$ $$ ||\nabla_x f_i|| \leq G \quad \forall \quad i \leq T \quad \forall \quad x \in \mathcal{X}$$ it is possible to derive an upper bound on regret for most algorithms. Online Gradient Descent is for example guaranteed to converge with $\mathcal{R}_T \leq \mathcal{O}(GD\sqrt{T})$. Now, different algorithms benefit different convergence rates. Although most algorithms converge $\Big(\lim_{T\rightarrow\infty}\mathcal{R}_T/T = 0\Big)$, no matter how good your algorithm, at iteration 0 you have no information about $f_t$. It takes a certain number of iterations before you can make optimal decisions. Therefore there must be a fundamental lower bound any algorithm can achieve as an upper bound. It turns out to be $\mathcal{O}(GD\sqrt{T})$.
Theorem 3.2, in [1] states: Any algorithm for online convex optimization incurs $\Omega(DG\sqrt{T})$ regret in the worst case. This is true even if the cost functions are generated from a fixed stationary distribution
They don't proof it however. They give an example which sketches the proof, but if someone could explain the proof or give a different proof that any algorithm will have a an upper bound on its regret greater or equal than $\mathcal{O}(GD\sqrt{T})$.
**[1] E. Hazan - Introduction to Online Convex Optimization ** https://arxiv.org/pdf/1909.05207.pdf
