A Simple Online Algorithm for Competing with Dynamic Comparators

Yu-Jie Zhang, Peng Zhao, Zhi-Hua ZhouUAI 2020 · OpenReview

Abstract

Online learning in dynamic environments has recently drawn considerable attention, where dynamic regret is usually employed to compare decisions of online algorithms to dynamic comparators. In previous work, achieving "fully adaptive" bounds—those that automatically adapt to the best regularity measure of the environment—often required solving complex non-convex optimization problems at every iteration. This paper introduces a computationally efficient online learning algorithm that achieves state-of-the-art dynamic regret bounds using an ensemble of base learners and a novel optimistic master algorithm. Our approach provides a fully adaptive solution that excels in non-stationary environments while running orders of magnitude faster than previous methods.

Introduction

In Online Convex Optimization (OCO), a learner makes a sequence of decisions to minimize loss in an environment that may change over time. Traditionally, algorithms are evaluated using static regret, comparing the learner's performance to the single best fixed decision in hindsight. However, in non-stationary environments such as financial markets or sensor networks, a fixed decision is an inadequate benchmark.

Researchers instead utilize dynamic regret, which compares the learner to a sequence of optimal decisions ($x^*_1, \dots, x^*_T$). The challenge lies in the fact that dynamic regret bounds depend on "regularities"—measures of environmental or optimal decision fluctuation, such as path-length ($C_T$) or temporal variability ($V_T$). While previous state-of-the-art (SOTA) approaches achieved "fully adaptive" bounds, they relied on a "doubling trick" requiring the solution of a difficult non-convex optimization problem at every iteration to estimate variability. This computational burden makes such methods impractical for real-time applications.

Methodology

The proposed algorithm replaces the computationally expensive doubling trick with an efficient online ensemble approach.

  1. Base Learners: The system initiates a pool of base algorithms, specifically variants of Optimistic Mirror Descent (OMD). Each base learner is assigned a specific step size from a carefully constructed logarithmic grid. This ensures that at least one learner is always utilizing a near-optimal step size for the current, unknown environment regularity.
  2. Optimistic Master Algorithm: To combine predictions, a new master algorithm based on Optimistic Hedge is employed.
  3. Surrogate Linearized Loss: A key innovation is having the master algorithm operate on a "surrogate linearized loss." This allows the master to inherit the "optimism" (utilizing hints about future gradients) of the base learners.
  4. Efficiency Gain: By using this surrogate loss, the algorithm only needs to query the gradient of the loss function once per iteration, regardless of the number of base learners. This significantly improves upon naive ensemble methods.

Theoretical Guarantees

The primary theoretical contribution is the achievement of a "fully adaptive" regret bound. As shown in the table below, our method matches the best known theoretical rates while remaining significantly simpler to implement and execute.

Comparison of regret bounds for different complexity measures.

The algorithm achieves a dynamic regret of $O(\sqrt{D_T} + \min\{R_C, R_V\})$, where $D_T$ represents the gradient variation. The inclusion of the $O(\sqrt{D_T})$ term is made possible by the "optimistic" design of the master's weight update.

Empirical Evaluation

The algorithm was evaluated on a Matrix Regression problem with a nuclear norm penalty, simulating a 3-stage dynamic environment where the underlying optimal matrix $X^*$ changes abruptly every 2000 iterations.

Empirical performance comparison: (a) instantaneous loss, (b) running time, and (c) sensitivity to hint quality.

Key Results

  • Massive Speedup: In empirical tests, the proposed algorithm completed the matrix regression task in only 24 seconds, whereas the previous SOTA (AOMD) required approximately 6 hours. This is visible in the logarithmic scale of Figure (b) above.
  • Adaptivity to Hints: The experiments confirmed that the algorithm successfully exploits high-quality "hints" ($M_t$). As the quality of the hint ($\lambda$) increased, the instantaneous loss dropped significantly, as shown in Figure (c).
  • Lower Instantaneous Loss: Compared to vanilla OMD and AOMD, "Ours" maintained a lower and more stable instantaneous loss across environmental shifts (Figure (a)).

Conclusion and Future Work

This paper demonstrates that a well-constructed logarithmic pool of learners can cover the parameter space of non-stationarity more effectively and efficiently than complex doubling tricks. While the algorithm is computationally fast, it does introduce a memory overhead of $O(\log T)$ base learners. Future work may explore making the gradient and feasible set diameter parameters adaptive, as well as extending the framework to account for "squared path-length" ($S_T$) in strongly convex settings.

Summary updated

Abstract

Online learning in dynamic environments has recently drawn considerable attention, where dynamic regret is usually employed to compare decisions of online algorithms to dynamic comparators. In prev...
BibTeX
@inproceedings{zhang2020simple,
  author = {Yu-Jie Zhang and Peng Zhao and Zhi-Hua Zhou},
  title = {{A Simple Online Algorithm for Competing with Dynamic Comparators}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=6MDUmR73PJx},
}
Figure