2021/06/24 by James B. Robinson, Robinson, James, Mark Herbster +1
Computer Science · Decision Sciences · Physics and Astronomy · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Model Reduction and Neural Networks
paper · pdf · doi:10.48550/arxiv.2106.13021
openalex publication_date 2021/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 bounds [26]. 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.