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?


1 Answer 1


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.


[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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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