Minimizing Dynamic Regret and Adaptive Regret Simultaneously

Lijun Zhang, Shiyin Lu, Tianbao Yang

Abstract: Regret minimization is treated as the golden rule in the traditional study of online learning. However, regret minimization algorithms tend to converge to the static optimum, thus being suboptimal for changing environments. To address this limitation, new performance measures, including dynamic regret and adaptive regret have been proposed to guide the design of online algorithms. The former one aims to minimize the global regret with respect to a sequence of changing comparators, and the latter one attempts to minimize every local regret with respect to a fixed comparator. Existing algorithms for dynamic regret and adaptive regret are developed independently, and only target one performance measure. In this paper, we bridge this gap by proposing novel online algorithms that are able to minimize the dynamic regret and adaptive regret simultaneously. In fact, our theoretical guarantee is even stronger in the sense that one algorithm is able to minimize the dynamic regret over any interval.

Introduction

In Online Convex Optimization (OCO), a learner repeatedly chooses actions and suffers losses. Traditionally, the goal was to minimize static regret—the difference between the learner's total loss and the loss of the single best action chosen in hindsight. However, static regret is a poor metric for "non-stationary" environments where the optimal action changes over time, such as in stock market trends or shifting user preferences.

To handle change, researchers developed two more stringent metrics:

  1. Dynamic Regret: Compares the learner to a sequence of changing actions, providing a global view of performance.
  2. Adaptive Regret: Measures the learner's performance over every possible sub-interval of time, providing a local view of performance.

Until now, these two metrics were studied in isolation. Algorithms designed for dynamic regret didn't necessarily handle local shifts well, and vice versa. This paper bridges this long-standing gap by introducing algorithms that minimize both simultaneously.

Proposed Algorithms

The authors propose two novel algorithms based on the "prediction with expert advice" framework. This involves a hierarchical structure where a "meta-algorithm" manages a pool of "expert" algorithms running on different time intervals.

AOD: Adaptive Online learning with Dynamic regret

This algorithm uses Online Gradient Descent (OGD) as its base expert and introduces two key innovations:

  • Dense Geometric Covering (DGC): A specific way of partitioning time into overlapping intervals to ensure there is always an expert specialized for any given time window. As shown in the figure below, intervals are structured across different scales to maintain coverage.
  • Warm Starting: Unlike standard adaptive algorithms that start each expert from scratch, AOD "warm starts" new experts using the final state of the previous expert in that sequence. This allows the learner to maintain a continuous "path" that can track a moving target.
The Dense Geometric Covering (DGC) scheme partitions time into overlapping intervals of varying lengths to ensure local and global coverage.

AOA: Adaptive Online learning based on Ader

This is a more complex, three-layer algorithm. Instead of OGD, it uses Ader (an existing dynamic regret algorithm) as the middle layer. This allows the algorithm to minimize dynamic regret over any arbitrary interval, not just the full duration of the game. This makes the learner robust to "bursts" of high volatility in an otherwise stable environment.

Key Insights

  • The Power of Warm-Starting: The authors identified that the primary reason previous adaptive algorithms failed at dynamic regret was that they "forgot" information when a new interval started. By passing parameters from old experts to new ones, the algorithm preserves the continuity needed for dynamic tracking.
  • Bridging Local and Global: The paper proves that dynamic regret and adaptive regret are complementary. The same hierarchical structure can be tuned to satisfy both, showing that local adaptability and global tracking are not mutually exclusive.

Theoretical Results

The authors provide rigorous mathematical proofs for the following guarantees:

  • Adaptive Regret: Both algorithms achieve a regret bound of $O(\sqrt{\tau \log T})$ for an interval of length $\tau$, matching state-of-the-art "strongly adaptive" bounds.
  • Dynamic Regret: AOD achieves a bound of $O(\sqrt{T(1+P_T)\log T})$, where $P_T$ is the "path-length" (the total movement of the optimal action). AOA extends this to any interval, nearly matching theoretical lower bounds.

This is the first work to show that these two state-of-the-art bounds can be achieved by the same algorithm at the same time.

Limitations and Future Work

While groundbreaking, the current work assumes general convex functions. If loss functions exhibit more "curvature" (e.g., strong convexity), the bounds could potentially be tightened. Additionally, the AOA algorithm's three-layer hierarchy introduces computational overhead; simplifying this structure while maintaining guarantees remains an open challenge. Future research may also explore "data-dependent" bounds to improve performance on sparse or structured data.

Summary updated

Abstract

Regret minimization is treated as the golden rule in the traditional study of online learning. However, regret minimization algorithms tend to converge to the static optimum, thus being suboptimal for changing environments. To address this limitation, new performance measures, including dynamic regret and adaptive regret have been proposed to guide the design of online algorithms. The former one aims to minimize the global regret with respect to a sequence of changing comparators, and the latter one attempts to minimize every local regret with respect to a fixed comparator. Existing algorithms for dynamic regret and adaptive regret are developed independently, and only target one performance measure. In this paper, we bridge this gap by proposing novel online algorithms that are able to minimize the dynamic regret and adaptive regret simultaneously. In fact, our theoretical guarantee is even stronger in the sense that one algorithm is able to minimize the dynamic regret over any interval.
BibTeX
@inproceedings{zhang2020minimizing,
  author = {Lijun Zhang and Shiyin Lu and Tianbao Yang},
  title = {{Minimizing Dynamic Regret and Adaptive Regret Simultaneously}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=xvgrfBqD2L},
}
Figure