A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret
Abstract
We consider algorithms for “smoothed online convex optimization” (SOCO) problems, which are a hybrid between online convex optimization (OCO) and metrical task system (MTS) problems. Historically, the performance metric for OCO was regret and that for MTS was competitive ratio (CR). There are algorithms with either sublinear regret or constant CR, but no known algorithm achieves both simultaneously. We show that this is a fundamental limitation – no algorithm (deterministic or randomized) can achieve sublinear regret and a constant CR, even when the objective functions are linear and the decision space is one dimensional. However, we present an algorithm that, for the important one dimensional case, provides sublinear regret and a CR that grows arbitrarily slowly.
Cite
Text
Andrew et al. "A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret." Annual Conference on Computational Learning Theory, 2013. doi:10.1145/2465529.2465533Markdown
[Andrew et al. "A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret." Annual Conference on Computational Learning Theory, 2013.](https://mlanthology.org/colt/2013/andrew2013colt-tale/) doi:10.1145/2465529.2465533BibTeX
@inproceedings{andrew2013colt-tale,
title = {{A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret}},
author = {Andrew, Lachlan L. H. and Barman, Siddharth and Ligett, Katrina and Lin, Minghong and Meyerson, Adam and Roytman, Alan and Wierman, Adam},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2013},
pages = {741-763},
doi = {10.1145/2465529.2465533},
url = {https://mlanthology.org/colt/2013/andrew2013colt-tale/}
}