Memory-Regret Tradeoff for Online Learning

Explore a lecture on the memory-regret tradeoff in online learning, presented by Binghui Peng from Columbia University at the Simons Institute. Delve into the experts problem, where an agent must choose between multiple experts' advice over a series of days, aiming to minimize cumulative loss. Discover fundamental results in learning theory regarding vanishing regret and investigate how an agent can perform well with limited memory. Examine two key extensions to existing research: a new algorithm against oblivious adversaries that improves upon previous memory-regret tradeoffs, and an exploration of adaptive adversaries who can observe the agent's past choices. Learn about novel algorithms and lower bounds that demonstrate the necessity and sufficiency of approximately √n memory for achieving sublinear regret. Gain insights into the intersection of sketching techniques and algorithm design in the context of online learning and decision-making under uncertainty.