A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret

Lachlan L. H. Andrew, Siddharth Barman, Katrina Ligett, Minghong Lin, Adam Meyerson, Alan Roytman, Adam Wierman

Abstract

We consider algorithms for “smoothed online convex optimization” problems, a variant of the class of online convex optimization problems that is strongly related to metrical task systems. Prior lit...
BibTeX
@inproceedings{andrew2013tale,
  author = {Lachlan L. H. Andrew and Siddharth Barman and Katrina Ligett and Minghong Lin and Adam Meyerson and Alan Roytman and Adam Wierman},
  title = {{A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret}},
  booktitle = {Conference on Learning Theory},
  year = {2013},
}
Figure