Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR
We consider the framework of non-stationary Online Convex Optimization where a learner seeks to control its dynamic regret against an arbitrary sequence of comparators. When the loss functions are strongly convex or exp-concave, we demonstrate that Strongly Adaptive (SA) algorithms can be viewed as a principled way of controlling dynamic regret in terms of path variation $V_T$ of the comparator sequence. Specifically, we show that SA algorithms enjoy $\tilde O(\sqrt{TV_T} \vee \log T)$ and $\tilde O(\sqrt{dTV_T} \vee d\log T)$ dynamic regret for strongly convex and exp-concave losses respectively without apriori knowledge of $V_T$. The versatility of the principled approach is further demonstrated by the novel results in the setting of learning against bounded linear predictors and online regression with Gaussian kernels. Under a related setting, the second component of the paper addresses an open question posed by Zhdanov and Kalnishkan (2010) that concerns online kernel regression with squared error losses. We derive a new lower bound on a certain penalized regret which establishes the near minimax optimality of online Kernel Ridge Regression (KRR). Our lower bound can be viewed as an RKHS extension to the lower bound derived in Vovk (2001) for online linear regression in finite dimensions.
Code (0)
등록된 구현이 없습니다.
Tasks
Open-Ended Question AnsweringregressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Dynamic Regret of Strongly Adaptive Methods
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 th…
Dynamic Regret of Adaptive Gradient Methods for Strongly Convex Problems
Adaptive gradient algorithms such as ADAGRAD and its variants have gained popularity in the training of deep neural networks. While many works as for adaptive methods have focused on the static regret as a performance me…
Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Games
In two-player zero-sum games, the learning dynamic based on optimistic Hedge achieves one of the best-known regret upper bounds among strongly-uncoupled learning dynamics. With an appropriately chosen learning rate, the …
Parameter-free, Dynamic, and Strongly-Adaptive Online Learning
We provide a new online learning algorithm that for the first time combines several disparate notions of adaptivity. First, our algorithm obtains a ``parameter-free'' regret bound that adapts to the norm of the comparato…
Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond
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 ac…