Timezone: »
Poster
Improved Regret Bounds for Tracking Experts with Memory
James Robinson · Mark Herbster
We address the problem of sequential prediction with expert advice in a non-stationary environment with long-term memory guarantees in the sense of Bousquet and Warmuth [4]. We give a linear-time algorithm that improves on the best known regret bound [27]. This algorithm incorporates a relative entropy projection step. This projection is advantageous over previous weight-sharing approaches in that weight updates may come with implicit costs as in for example portfolio optimization. We give an algorithm to compute this projection step in linear time, which may be of independent interest.
Author Information
James Robinson (UCL)
Mark Herbster (University College London)
More from the Same Authors
-
2021 Poster: A Gang of Adversarial Bandits »
Mark Herbster · Stephen Pasteris · Fabio Vitale · Massimiliano Pontil -
2020 Poster: Online Matrix Completion with Side Information »
Mark Herbster · Stephen Pasteris · Lisa Tse -
2020 Poster: Online Multitask Learning with Long-Term Memory »
Mark Herbster · Stephen Pasteris · Lisa Tse -
2019 Poster: Online Prediction of Switching Graph Labelings with Cluster Specialists »
Mark Herbster · James Robinson -
2016 Poster: Mistake Bounds for Binary Matrix Completion »
Mark Herbster · Stephen Pasteris · Massimiliano Pontil -
2015 Poster: Online Prediction at the Limit of Zero Temperature »
Mark Herbster · Stephen Pasteris · Shaona Ghosh -
2012 Poster: Online Sum-Product Computation »
Mark Herbster · Fabio Vitale · Stephen Pasteris -
2008 Poster: Fast Prediction on a Tree »
Mark Herbster · Massimiliano Pontil · Sergio Rojas Galeano -
2008 Oral: Fast Prediction on a Tree »
Mark Herbster · Massimiliano Pontil · Sergio Rojas Galeano -
2008 Poster: On-Line Prediction on Large Diameter Graphs »
Mark Herbster · Massimiliano Pontil · Guy Lever -
2006 Poster: Prediction on a Graph with a Perceptron »
Mark Herbster · Massimiliano Pontil -
2006 Spotlight: Prediction on a Graph with a Perceptron »
Mark Herbster · Massimiliano Pontil