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 | Submitted
Book Section - Chapter Open

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.

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

1508.03769.pdf
Files (278.5 kB)
Name Size Download all
md5:139c2871abb842a4a6d86f400135e913
278.5 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 25, 2023