Online Learning in Changing Environments

Lijun ZhangIJCAI 2020 · OpenReview

Abstract

The usual goal of online learning is to minimize the regret, which measures the performance of online learner against a fixed comparator. However, it is not suitable for changing environments in which the best decision may change over time. To address this limitation, new performance measures, including dynamic regret and adaptive regret have been proposed to guide the design of online algorithms. In dynamic regret, the learner is compared with a sequence of comparators, and in adaptive regret, the learner is required to minimize the regret over every interval. In this paper, we will review the recent developments in this area, and highlight our contributions. Specifically, we have proposed novel algorithms to minimize the dynamic regret and adaptive regret, and investigated the relationship between them.

Introduction

In the framework of Online Convex Optimization (OCO), a learner iteratively makes decisions $x_t$ from a convex set and observes a loss function $f_t$. The traditional performance metric is static regret, which compares the learner's cumulative loss against the single best fixed decision in hindsight. While effective for stationary environments, static regret fails to capture the complexities of non-stationary settings—such as financial markets or sensor networks—where the optimal decision evolves over time.

To address this, researchers have introduced more robust metrics: dynamic regret and adaptive regret. This paper explores the development of algorithms designed to minimize these measures, focusing on the Ader (Adaptive Learning for Dynamic Environment) framework and its theoretical foundations.

Performance Measures for Non-Stationary Environments

Dynamic Regret

Dynamic regret compares the learner's performance against a sequence of comparators $u_1, \dots, u_T$. It is defined as: $$R(u_1, \dots, u_T) = \sum_{t=1}^T f_t(x_t) - \sum_{t=1}^T f_t(u_t)$$ The difficulty of minimizing dynamic regret is often tied to the path-length $P_T = \sum_{t=2}^T \|u_t - u_{t-1}\|$, which quantifies how much the optimal decision changes over time.

Adaptive Regret

Adaptive regret measures the learner's performance over every possible sub-interval $[s, e] \subseteq [1, T]$. An algorithm with low adaptive regret ensures that it does not suffer from "bursts" of poor performance, even if its overall static regret is low. This metric is crucial for identifying local changes in the environment and ensuring consistent performance across all time windows.

The Ader Framework

The core contribution to this field is the Ader algorithm, which utilizes a two-layer "Meta-Expert" architecture to handle unknown environmental fluctuations without prior knowledge of the path-length.

  1. Expert Layer: A set of Online Gradient Descent (OGD) instances run in parallel. Each expert is assigned a different learning rate (step size), optimized for a specific potential path-length.
  2. Meta-Algorithm Layer: An expert-tracking algorithm, typically using exponentially weighted averages, aggregates the predictions from the experts. By monitoring the performance of each expert, the meta-algorithm shifts weight toward the learning rate that best matches the current environmental volatility.

A significant advancement in this framework is the use of surrogate loss functions. By linearizing the losses, the computational complexity is reduced from $O(\log T)$ gradient evaluations per round to just one, making the algorithm viable for high-frequency real-time applications.

Key Theoretical Insights

Optimality and Path-Length

Theoretical analysis shows that for general convex functions, the optimal dynamic regret scales with $O(\sqrt{T(1 + P_T)})$. The Ader algorithm achieves this bound, which matches the established lower bound of $\Omega(\sqrt{T(1 + P_T)})$, proving its optimality in the general case.

The Local-to-Global Connection

A pivotal insight in this research is the relationship between adaptive and dynamic regret. It has been demonstrated that adaptive regret can bound dynamic regret. Specifically, an algorithm that is "strongly adaptive" (performing well on every small interval) is inherently capable of tracking a sequence of changing comparators globally. This establishes a formal mathematical link between local stability and global adaptability.

Exploiting Function Curvature

While general convex functions yield $\sqrt{T}$-style regret, the research demonstrates that specific function properties—such as strong convexity or exp-concavity—can be exploited. In these cases, the regret can be significantly reduced to $O(P_T)$ or $O(\log T)$, effectively accelerating the learning process in structured environments. For example, the proposed universal algorithm achieves $O(\frac{d}{\alpha} \log \tau \log T)$ strongly adaptive regret for $\alpha$-exp-concave functions.

Conclusion and Future Directions

The transition from static to dynamic and adaptive regret represents a significant step toward making online learning algorithms robust for real-world deployment. The Ader framework provides a theoretically sound and computationally efficient method for navigating non-stationary environments.

However, several challenges remain. While the relationship between adaptive regret and worst-case dynamic regret is well-understood, the connection to general dynamic regret remains an open question. Furthermore, as the number of experts grows (particularly in "sleeping expert" frameworks used for adaptive regret), managing memory and computational overhead for long-running systems continues to be a critical area for future optimization.

Summary updated

Abstract

The usual goal of online learning is to minimize the regret, which measures the performance of online learner against a fixed comparator. However, it is not suitable for changing environments in which the best decision may change over time. To address this limitation, new performance measures, including dynamic regret and adaptive regret have been proposed to guide the design of online algorithms. In dynamic regret, the learner is compared with a sequence of comparators, and in adaptive regret, the learner is required to minimize the regret over every interval. In this paper, we will review the recent developments in this area, and highlight our contributions. Specifically, we have proposed novel algorithms to minimize the dynamic regret and adaptive regret, and investigated the relationship between them.
BibTeX
@inproceedings{zhang2020online,
  author = {Lijun Zhang},
  title = {{Online Learning in Changing Environments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=nUsajH5FIJ},
}
Figure