Reproduce “Online Convex Optimization with Unbounded Memory” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Raunak Kumar, Sarah Dean, Robert Kleinberg
This research introduces a generalized Online Convex Optimization framework with unbounded memory, along with a novel `p-effective memory capacity (H_p)` metric, to characterize the influence of past decisions. It establishes tight upper and lower bounds on policy regret for this framework and provides the first non-trivial lower bound for OCO with finite memory, yielding improved regret bounds for online linear control and performative prediction.
Key insights
- By formalizing history evolution with linear operators in functional spaces, the framework unifies the analysis of diverse online learning problems exhibiting long-term dependencies.
- The `p-effective memory capacity (H_p)` serves as a critical parameter that directly influences regret bounds, providing a quantitative measure of memory's impact.
- Specific adversarial constructions, utilizing block-wise random signs, can demonstrate the inherent complexity of online learning with memory and establish tight lower bounds that depend on memory length.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.