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

TL;DR

This paper reveals a fundamental incompatibility between achieving low regret and a constant competitive ratio in smoothed online convex optimization (SOCO). While no algorithm can simultaneously achieve both, the authors propose a novel algorithm that offers a tunable tradeoff, allowing for sublinear regret with a slowly growing competitive ratio in one-dimensional settings.

What Problem Does This Paper Address?

Online convex optimization (OCO) is a framework where an agent learns to make sequential decisions in an environment that reveals cost functions over time. Two key performance metrics are used to evaluate OCO algorithms: regret, which measures the additive difference between the agent's total cost and the cost of the best static decision, and the competitive ratio, which measures the multiplicative difference between the agent's cost and the cost of the best dynamic decision.

This paper focuses on a variant called smoothed online convex optimization (SOCO). In SOCO, there's an additional "switching cost" incurred when the agent changes its decision from one round to the next. This is motivated by real-world scenarios like dynamic resource provisioning in data centers, where changing server configurations or migrating data incurs costs.

The problem arises because the literature has developed algorithms that excel at one metric but fail at the other. OCO research often focuses on achieving "no regret" (sublinear regret), while metrical task systems (MTS) research (closely related to SOCO) emphasizes constant competitive ratios. The core question is: can we design algorithms that perform well on both metrics simultaneously?

Methods

The authors first establish a fundamental incompatibility between sublinear regret and constant competitive ratio in SOCO. They prove this through theoretical arguments, demonstrating that any algorithm achieving sublinear regret will necessarily have an infinite competitive ratio, and vice-versa. This incompatibility holds even for simplified cases like linear cost functions and one-dimensional decision spaces, and applies to both deterministic and randomized algorithms.

To overcome this incompatibility, they propose a novel algorithm called Randomly Biased Greedy (RBG). RBG is designed for one-dimensional decision spaces and uses a single random number to introduce a "bias" in its decision-making. The key idea is to allow for a tunable tradeoff between regret and competitive ratio by adjusting the norm used by the algorithm. By using a "larger" norm, the algorithm can encourage less drastic changes in actions, leading to smaller regret at the cost of a slightly larger (but still constant) competitive ratio.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic design, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Fundamental Tradeoff: The most striking insight is the inherent conflict between minimizing regret and achieving a constant competitive ratio in SOCO. This isn't a limitation of current algorithms but a fundamental property of the problem itself.
  • "Off-by-One" Incompatibility: The incompatibility is particularly pronounced when comparing metrics that use slightly different time horizons (e.g., comparing regret at time $t$ with competitive ratio at time $t+1$).
  • The Power of Norm Choice: For one-dimensional SOCO, the choice of the norm used by the algorithm is crucial for balancing regret and competitive ratio. A carefully selected norm can achieve a desired tradeoff.
  • RBG as a Flexible Tool: The RBG algorithm provides a principled way to navigate this tradeoff, offering a spectrum of performance guarantees rather than a single fixed outcome.

Key Results

  • Incompatibility Theorems: The paper presents Theorems 2, 3, and 4, which formally prove the incompatibility between sublinear regret and constant competitive ratio in SOCO, even for linear cost functions and one-dimensional spaces.
  • RBG Algorithm: The authors introduce the Randomly Biased Greedy (RBG) algorithm for one-dimensional SOCO.
  • RBG Performance Guarantees: For a one-dimensional SOCO problem, RBG with a tunable norm achieves an $\alpha$-unfair competitive ratio of $(1+\theta)/\min\{\theta, \alpha\}$ and a regret of $O(\max\{T/\theta, \theta\})$, where $\theta$ is a parameter related to the norm choice. This allows for sublinear regret with an arbitrarily slowly growing competitive ratio, or vice-versa.

Limitations and Future Work

  • One-Dimensional Focus: The primary result on balancing regret and competitive ratio with RBG is limited to one-dimensional decision spaces. Extending this to higher dimensions is a significant open question.
  • Adversarial Setting: The analysis assumes an adversarial environment for cost functions. Exploring performance in stochastic or random environments would be valuable.
  • General SOCO: The paper notes that the SOCO formulation is still "under-explored," suggesting that many variations and extensions of the problem remain to be understood.
  • Other Metrics: The authors suggest investigating other hybrid benchmarks or exploring how the incompatibility might change with different cost function structures or problem settings (e.g., k-armed bandit problems with switching costs).

Summary updated

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 literature on these problems has focused on two performance metrics: regret and the competitive ratio. There exist known algorithms with sublinear regret and known algorithms with constant competitive ratios; however, no known algorithm achieves both simultaneously. We show that this is due to a fundamental incompatibility between these two metrics - no algorithm (deterministic or randomized) can achieve sublinear regret and a constant competitive ratio, even in the case when the objective functions are linear. However, we also exhibit an algorithm that, for the important special case of one-dimensional decision spaces, provides sublinear regret while maintaining a competitive ratio that grows arbitrarily slowly.
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