# 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?

• When you cross-post the same, or a very similar, question to other StackExchange sites, in this case to Math at Online Optimization Regret in Absolute Error, please provide a link a courtesy to anybody reading & trying to help you to avoid duplicating efforts. Thanks. Aug 5, 2019 at 6:04
• The question and answers therein might be of interest: stats.stackexchange.com/questions/385159/… Apr 7, 2020 at 13:25

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.