Doubt about definition of Regret in Online convex optimization setting

In online convex optimization, the regret of an algorithm $$\mathcal{A}$$ as defined in Introduction to Online Convex Optimization (Page 5) is: $$regret_T(\mathcal{A}) = \sup_{\{f_1,...,f_T\}} \sum_{t=1}^{T}f_t(x_t) − \min_{x \in \mathcal{K}} \sum_{t=1}^{T} f_t (x)$$ where at iteration t, the online player chooses a decision $$x_t \in \mathcal{K}$$ and $$\mathcal{K}$$ is a convex set in $$\mathbb{R}^n$$. Let set $$\mathcal{F}$$ consists of bounded family of cost functions available to the adversary and $$f_t \in \mathcal{F}: \mathcal{K} \rightarrow \mathbb{R}$$ is the convex cost function reveled after player chooses decision $$x_t$$.

As far as I have understood, the second term is the sum of $$T$$ convex functions, Hence the overall sum is a convex function in $$x$$ and we set the minimum of this convex function as a baseline for our algorithm $$i.e.$$ the performance of an algorithm is analyzed with respect to this minimum.

But as far as I can see the regret can still be negative because an algorithm can still play by always choosing the decision $$x_t = \min_{x \in \mathcal{K}} f_t (x)$$. which would result in a non-positive regret.

Am I mistaken somewhere or Is negative regret allowed in such settings?

$$regret_T(\mathcal{A}) = \sup_{\{f_1,...,f_T\}} \left \{ \sum_{t=1}^{T}f_t(x_t) − \min_{x \in \mathcal{K}} \sum_{t=1}^{T} f_t (x) \right \}$$,
• The claim stems by the elementary observation that for any function $f$ and any $x \in dom(f)$ you have that $\min_x f(x) < f(x)$. – Apprentice Jul 1 at 13:20
• But what you are saying is that, $\min_{x \in \mathcal{K}} \sum_{t=1}^T f_t(x) \leq \sum_{t=1}^T f_t(y)$, for any fixed $y \in \mathcal{K}$. However, in the first sum of the regret definition (i.e. $\sum_{t=1}^T f_t(x_t)$), the online player may choose a different action $x_t$ for each time $t$. – durdi Jul 1 at 14:28
• I honestly don't get what you mean. The loss $f_t(x_t)$ for any action $x_t$ that the online player can choose will always be larger than or equal to $min_{x} f_t(x)$. There is not much more to add to this very simple observation. – Apprentice Jul 1 at 15:22
• What I am saying is that $\min_{y \in \mathcal{K}} f_t (y) \leq f_t(x_t)$ does not imply that $\min_{x \in \mathcal{K}} \sum_{t=1}^{T}f_t(x) \leq \sum_{t=1}^{T}f_t(x_t)$, for all action sequences $x_1,\dots,x_T$. To see this, define $x^*_t := \text{arg}\min_{x \in \mathcal{K}} f_t(x)$ and $x^* := \text{arg}\min_{x \in \mathcal{K}} \sum_{t=1}^{T} f_t(x)$. By the definition of $x^*_t$, we have that $f_t (x^*) \geq f_t(x^*_t)$, for any $t$. Summing this inequality over $t = 1,\dots,T$, we have $\sum_{t=1}^{T} f_t(x^*) = \min_{x \in \mathcal{K}} \sum_{t=1}^{T}f_t(x) \geq \sum_{t=1}^{T}f_t(x^*_t)$. – durdi Jul 1 at 16:32