Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR
This work provides theoretical guarantees for dynamic regret in online learning, which is important for applications with non-stationary environments, though it appears incremental as it builds on existing strongly adaptive methods and extends prior lower bounds.
The paper tackles dynamic regret in non-stationary online convex optimization, showing that strongly adaptive algorithms achieve regret bounds of $ ilde O(\sqrt{TV_T} \vee \log T)$ for strongly convex losses and $ ilde O(\sqrt{dTV_T} \vee d\log T)$ for exp-concave losses without prior knowledge of path variation $V_T$. It also addresses an open problem in online kernel regression, deriving a lower bound that establishes the near minimax optimality of online kernel ridge regression.
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.