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 in non-stationary environments. This paper addresses the challenge of performing well in environments that change both globally over long periods and locally in short bursts. By bridging the gap between two major performance metrics—dynamic regret and adaptive regret—the authors propose two novel hierarchical algorithms (AOD and AOA) that minimize both metrics simultaneously, ensuring optimal performance across varying environmental dynamics.

Introduction

In the field of Online Convex Optimization (OCO), a learner iteratively selects actions while an adversary reveals loss functions. The standard performance metric, static regret, evaluates the learner against the single best fixed action in hindsight. While useful, static regret fails to account for non-stationary environments where the optimal action evolves over time.

To address this, researchers have developed two more sophisticated metrics:

  1. Dynamic Regret: Compares the learner to a sequence of changing optimal actions, focusing on global performance over the entire time horizon.
  2. Adaptive Regret: Measures the maximum regret over any local time interval, ensuring the learner is locally optimal.

Until this work, algorithms were typically optimized for one metric at the expense of the other. This paper presents a unified framework to achieve the best of both worlds.

Methods: Hierarchical Algorithms

The authors propose a "prediction with expert advice" framework, where a meta-algorithm aggregates decisions from multiple parallel experts.

AOD (Adaptive Online learning with Dynamic regret)

AOD is a two-layer algorithm designed for computational efficiency. It manages multiple experts running Online Gradient Descent (OGD) over a structured set of intervals.

The Dense Geometric Covering (DGC) interval structure used in AOD to partition the time horizon and manage experts.
  • Experts: The base learners are instances of OGD, a standard iterative optimization method.
  • DGC Intervals: Experts operate over "Dense Geometric Covering" (DGC) intervals. This hierarchy ensures that for any arbitrary sub-interval, there is an active expert that has been properly initialized.
  • Warm-Start Strategy: A key innovation is the warm-start mechanism. When an interval ends, the subsequent expert of the same scale starts with the final parameters of the previous one. This continuity allows the algorithm to maintain a "memory" of the path-length, which is essential for bounding dynamic regret.
Algorithm 1: Online Gradient Descent (OGD), the base expert algorithm used within the hierarchical AOD framework.

AOA (Adaptive Online learning based on Ader)

AOA is a three-layer algorithm that provides even stronger theoretical guarantees. Instead of simple OGD, it uses Ader (a specialized dynamic regret minimizer) as its experts. AOA does not require prior knowledge of the total time horizon $T$ and can minimize dynamic regret over any arbitrary sub-interval, representing the strongest theoretical bound in this area to date.

Key Insights

  • The Importance of Continuity: The authors identified that previous adaptive algorithms failed at dynamic regret because their experts were isolated. The "warm-start" strategy bridges this gap by passing information across temporal boundaries.
  • Decoupling via Hierarchy: By nesting a dynamic-regret-minimizer within an adaptive framework, the authors show that adaptive regret can serve as a "container" for more specialized global tracking strategies.

Key Results

  • Simultaneous Optimality: Both algorithms achieve the state-of-the-art adaptive regret of $O(\sqrt{\tau \log T})$ for an interval of length $\tau$.
  • Near-Optimal Dynamic Regret: AOD achieves a dynamic regret of $O(\sqrt{T(1 + P_T) \log T})$, where $P_T$ is the "path-length" (a measure of how much the optimal action moves). This is only a logarithmic factor away from the theoretical lower bound.
  • Efficiency: AOD is highly efficient with a per-round computational complexity of $O(\log T)$. AOA is slightly more intensive at $O(\log^2 t)$.

Limitations and Future Work

AOD requires knowing the total time horizon $T$ in advance, which may not be feasible in all streaming scenarios. While AOA addresses this, it comes with increased complexity. Future research could explore tighter bounds for specific function classes (e.g., strongly convex or smooth functions) or further optimize the computational overhead of running multiple experts in parallel.

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 ...
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