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?


The sup is over the whole expression

$$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 \} $$,

and by definition you have that the second terms is smaller than the first. So the difference between the two terms in brackets will always be positive.

| cite | improve this answer | |
  • $\begingroup$ Can you elaborate on the claim: "by definition you have that the second terms is smaller than the first"? $\endgroup$ – durdi Jul 1 at 10:24
  • $\begingroup$ 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)$. $\endgroup$ – Apprentice Jul 1 at 13:20
  • $\begingroup$ 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$. $\endgroup$ – durdi Jul 1 at 14:28
  • $\begingroup$ 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. $\endgroup$ – Apprentice Jul 1 at 15:22
  • $\begingroup$ 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)$. $\endgroup$ – durdi Jul 1 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.