Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond

Dheeraj Baby; Yu-Xiang Wang

Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond

Dheeraj Baby, Yu-Xiang Wang

Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:1805-1845, 2022.

Abstract

We study the framework of universal dynamic regret minimization with strongly convex losses. We answer an open problem in Baby and Wang 2021 by showing that in a proper learning setup, Strongly Adaptive algorithms can achieve the near optimal dynamic regret of

$\tilde O(d^{1/3} n^{1/3}\text{TV}[u_{1:n}]^{2/3} \vee d)$ against any comparator sequence

$u_1,\ldots,u_n$ simultaneously, where

$n$ is the time horizon and

$\text{TV}[u_{1:n}]$ is the Total Variation of comparator. These results are facilitated by exploiting a number of new structures imposed by the KKT conditions that were not considered in Baby and Wang 2021 which also lead to other improvements over their results such as: (a) handling non-smooth losses and (b) improving the dimension dependence on regret. Further, we also derive near optimal dynamic regret rates for the special case of proper online learning with exp-concave losses and an

$L_\infty$ constrained decision set.

Cite this Paper

BibTeX


@InProceedings{pmlr-v151-baby22a,
  title = 	 { Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond },
  author =       {Baby, Dheeraj and Wang, Yu-Xiang},
  booktitle = 	 {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics},
  pages = 	 {1805--1845},
  year = 	 {2022},
  editor = 	 {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel},
  volume = 	 {151},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {28--30 Mar},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v151/baby22a/baby22a.pdf},
  url = 	 {https://proceedings.mlr.press/v151/baby22a.html},
  abstract = 	 { We study the framework of universal dynamic regret minimization with strongly convex losses. We answer an open problem in Baby and Wang 2021 by showing that in a proper learning setup, Strongly Adaptive algorithms can achieve the near optimal dynamic regret of $\tilde O(d^{1/3} n^{1/3}\text{TV}[u_{1:n}]^{2/3} \vee d)$ against any comparator sequence $u_1,\ldots,u_n$ simultaneously, where $n$ is the time horizon and $\text{TV}[u_{1:n}]$ is the Total Variation of comparator. These results are facilitated by exploiting a number of new structures imposed by the KKT conditions that were not considered in Baby and Wang 2021 which also lead to other improvements over their results such as: (a) handling non-smooth losses and (b) improving the dimension dependence on regret. Further, we also derive near optimal dynamic regret rates for the special case of proper online learning with exp-concave losses and an $L_\infty$ constrained decision set. }
}

Endnote

%0 Conference Paper
%T  Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond 
%A Dheeraj Baby
%A Yu-Xiang Wang
%B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics
%C Proceedings of Machine Learning Research
%D 2022
%E Gustau Camps-Valls
%E Francisco J. R. Ruiz
%E Isabel Valera	
%F pmlr-v151-baby22a
%I PMLR
%P 1805--1845
%U https://proceedings.mlr.press/v151/baby22a.html
%V 151
%X  We study the framework of universal dynamic regret minimization with strongly convex losses. We answer an open problem in Baby and Wang 2021 by showing that in a proper learning setup, Strongly Adaptive algorithms can achieve the near optimal dynamic regret of $\tilde O(d^{1/3} n^{1/3}\text{TV}[u_{1:n}]^{2/3} \vee d)$ against any comparator sequence $u_1,\ldots,u_n$ simultaneously, where $n$ is the time horizon and $\text{TV}[u_{1:n}]$ is the Total Variation of comparator. These results are facilitated by exploiting a number of new structures imposed by the KKT conditions that were not considered in Baby and Wang 2021 which also lead to other improvements over their results such as: (a) handling non-smooth losses and (b) improving the dimension dependence on regret. Further, we also derive near optimal dynamic regret rates for the special case of proper online learning with exp-concave losses and an $L_\infty$ constrained decision set.

APA


Baby, D. & Wang, Y.. (2022).  Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:1805-1845 Available from https://proceedings.mlr.press/v151/baby22a.html.

Related Material

Download PDF