Dynamic Regret of Strongly Adaptive Methods

Lijun Zhang, Tianbao Yang,  jin, Zhi-Hua Zhou
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:5882-5891, 2018.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-zhang18o, title = {Dynamic Regret of Strongly Adaptive Methods}, author = {Zhang, Lijun and Yang, Tianbao and rong jin and Zhou, Zhi-Hua}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {5882--5891}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/zhang18o/zhang18o.pdf}, url = {https://proceedings.mlr.press/v80/zhang18o.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Dynamic Regret of Strongly Adaptive Methods %A Lijun Zhang %A Tianbao Yang %A jin %A Zhi-Hua Zhou %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-zhang18o %I PMLR %P 5882--5891 %U https://proceedings.mlr.press/v80/zhang18o.html %V 80 %X 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.
APA
Zhang, L., Yang, T., jin, & Zhou, Z.. (2018). Dynamic Regret of Strongly Adaptive Methods. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:5882-5891 Available from https://proceedings.mlr.press/v80/zhang18o.html.

Related Material