Timezone: »

 
Poster
Efficient Methods for Non-stationary Online Learning
Peng Zhao · Yan-Feng Xie · Lijun Zhang · Zhi-Hua Zhou

Tue Nov 29 02:00 PM -- 04:00 PM (PST) @ Hall J #537
in Poster Session 2 »
Non-stationary online learning has drawn much attention in recent years. In particular, \emph{dynamic regret} and \emph{adaptive regret} are proposed as two principled performance measures for online convex optimization in non-stationary environments. To optimize them, a two-layer online ensemble is usually deployed due to the inherent uncertainty of the non-stationarity, in which a group of base-learners are maintained and a meta-algorithm is employed to track the best one on the fly. However, the two-layer structure raises the concern about the computational complexity--those methods typically maintain $O(\log T)$ base-learners simultaneously for a $T$-round online game and thus perform multiple projections onto the feasible domain per round, which becomes the computational bottleneck when the domain is complicated. In this paper, we present efficient methods for optimizing dynamic regret and adaptive regret, which reduce the number of projections per round from $O(\log T)$ to $1$. Moreover, our obtained algorithms require only one gradient query and one function evaluation at each round. Our technique hinges on the reduction mechanism developed in parameter-free online learning and requires non-trivial twists on non-stationary online methods. Empirical studies verify our theoretical findings.
Keywords: Dynamic regret · non-stationary online learning · projection complexity · online ensemble · adaptive regret
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Peng Zhao (Nanjing University)
Yan-Feng Xie (Nanjing University)
Lijun Zhang (Nanjing University (NJU))
Zhi-Hua Zhou (Nanjing University)

More from the Same Authors