Dynamic Regret of Strongly Adaptive Methods
This work addresses the challenge of adapting to changing environments in online learning, providing a novel theoretical link and practical algorithms that improve over previous methods by eliminating the need for prior knowledge, though it is incremental in building on existing concepts.
The paper tackles the problem of connecting adaptive regret and dynamic regret in online learning for changing environments, showing that dynamic regret can be expressed in terms of adaptive regret and functional variation, and presents strongly adaptive algorithms with small dynamic regrets for convex, exponentially concave, and strongly convex functions without needing prior knowledge of functional variation.
To cope with changing environments, recent developments in online learning have introduced the concepts of adaptive regret and dynamic regret independently. In this paper, we illustrate an intrinsic connection between these two concepts by showing that the dynamic regret can be expressed in terms of the adaptive regret and the functional variation. This observation implies that strongly adaptive algorithms can be directly leveraged to minimize the dynamic regret. As a result, we present a series of strongly adaptive algorithms that have small dynamic regrets for convex functions, exponentially concave functions, and strongly convex functions, respectively. To the best of our knowledge, this is the first time that exponential concavity is utilized to upper bound the dynamic regret. Moreover, all of those adaptive algorithms do not need any prior knowledge of the functional variation, which is a significant advantage over previous specialized methods for minimizing dynamic regret.