A Last-Step Regression Algorithm for Non-Stationary Online Learning
This addresses the challenge of non-stationary environments in applications like rating or ranking, though it appears incremental as it builds on existing frameworks like H_infinity filters.
The paper tackles the problem of online learning with drifting target functions, developing a last-step minmax optimal algorithm that maintains average loss close to the best slowly changing sequence of linear functions under sublinear drift, with improvements in some bounds and logarithmic regret in no-drift cases.
The goal of a learner in standard online learning is to maintain an average loss close to the loss of the best-performing single function in some class. In many real-world problems, such as rating or ranking items, there is no single best target function during the runtime of the algorithm, instead the best (local) target function is drifting over time. We develop a novel last-step minmax optimal algorithm in context of a drift. We analyze the algorithm in the worst-case regret framework and show that it maintains an average loss close to that of the best slowly changing sequence of linear functions, as long as the total of drift is sublinear. In some situations, our bound improves over existing bounds, and additionally the algorithm suffers logarithmic regret when there is no drift. We also build on the H_infinity filter and its bound, and develop and analyze a second algorithm for drifting setting. Synthetic simulations demonstrate the advantages of our algorithms in a worst-case constant drift setting.