Online Optimization - Regret in Absolute Error In the online convex optimization literature static regret is defined as $\sum_{t=1}^{T}\left(f_t\left(x_t\right)-f_t\left(x^*\right)\right)$ where $x^*=\arg min_{x\in\mathcal{X}}\sum_{t=1}^{T}f_t\left(x\right)$.
Does it make sense to consider a regret as $\sum_{t=1}^{T}|f_t\left(x_t\right)-f_t\left(x^*\right)|$? Or, is there any existing impossibility result which shows that this regret cannot be minimized?
 A: The measure of $\sum_{t=1}^{T}|f_t\left(x_t\right)-f_t\left(x^*\right)|$ does not really make sense. The ultimate goal of online learning is to minimize the cumulative loss $\sum_{t=1}^{T} f_t(x_t)$. 


*

*People typically compare it to an offline benchmark $\sum_{t=1}^{T} f_t(x^*)$. If the difference is small (aka, a low regret), then we think the algorithm behaves fairly well, because it is comparable to the offline player. 

*But in some cases there might not be a single fixed $x^*$ with small $\sum_{t=1}^{T} f_t(x^*)$, for example, non-stationary environments. So a clever algorithm might result in a negative regret,  i.e., $\sum_{t=1}^{T} f_t(x_t) - \sum_{t=1}^{T} f_t(x^*) < 0$ ! 

*Even in such cases, we still should not optimize the absolute value, which contradicts with our ultimate goal (minimizing the cumulative loss). Instead, we should optimize a measure called dynamic regret [1] (see [2] and [3] for a more general measure), $$\sum_{t=1}^{T} f_t(x_t) - f_t(x_t^*),$$ where $x_t^*$ is the optimizer of $f_t$. Obviously, the benchmark is changing and the best attainable decisions, and thus the dynamic regret will never be negative.

Reference:
[1] Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online
  optimization: Competing with dynamic comparators. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS), 2015.
[2] Lijun Zhang, ShiyinLu, and Zhi-Hua Zhou. Adaptive Online Learning in Dynamic Environments. In Advances in Neural Information Processing Systems 31 (NeurIPS), 2018.
[3] Peng Zhao, Guanghui Wang, Lijun Zhang, Zhi-Hua Zhou. Bandit Convex Optimization in Non-stationary Environments. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.

