Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2013 | public
Book Section - Chapter Open

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


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.

Additional Information

Copyright is held by the author/owner(s). This work was supported by NSF grants CCF 0830511, and CNS 0846025, Microsoft Research, the Lee Center for Advanced Networking, and ARC grants FT0991594 and DP130101378.

Attached Files

Submitted - 1508.03769.pdf


Files (278.5 kB)
Name Size Download all
278.5 kB Preview Download

Additional details

August 19, 2023
August 19, 2023