Online Prediction in Sub-linear Space
This solves an open problem in online learning theory by enabling efficient memory usage while maintaining performance guarantees, with implications for resource-constrained applications.
The authors developed the first sub-linear space and sub-linear regret algorithm for online learning with expert advice against an oblivious adversary, achieving T^{1-α} regret, and proved a linear memory lower bound for any sub-linear regret algorithm against adaptive adversaries, demonstrating a separation between adversary types.
We provide the first sub-linear space and sub-linear regret algorithm for online learning with expert advice (against an oblivious adversary), addressing an open question raised recently by Srinivas, Woodruff, Xu and Zhou (STOC 2022). We also demonstrate a separation between oblivious and (strong) adaptive adversaries by proving a linear memory lower bound of any sub-linear regret algorithm against an adaptive adversary. Our algorithm is based on a novel pool selection procedure that bypasses the traditional wisdom of leader selection for online learning, and a generic reduction that transforms any weakly sub-linear regret $o(T)$ algorithm to $T^{1-α}$ regret algorithm, which may be of independent interest. Our lower bound utilizes the connection of no-regret learning and equilibrium computation in zero-sum games, leading to a proof of a strong lower bound against an adaptive adversary.