Near Optimal Memory-Regret Tradeoff for Online Learning

Binghui Peng, Aviad Rubinstein

Abstract

This paper provides a near-complete characterization of the memory-regret tradeoff in the classic "experts problem" of online learning. While standard algorithms like Multiplicative Weights Update (MWU) require $O(n)$ memory to track $n$ experts, modern large-scale applications often necessitate sublinear storage. The authors establish that for oblivious adversaries, regret scales as $\tilde{O}(\sqrt{nT/S})$ given $S$ memory. Crucially, they identify a fundamental phase transition for adaptive adversaries: achieving vanishing regret requires a minimum memory of $\Omega(\sqrt{n})$. This work bridges the gap between memory-constrained learning and adversarial robustness, providing both optimal algorithms and tight lower bounds.

Introduction

In the classic experts problem, an agent must select one of $n$ experts to follow each day over a horizon of $T$ days. After each selection, the losses of all experts are revealed (full feedback). The objective is to minimize regret—the difference between the agent's cumulative loss and the loss of the best-performing expert in hindsight.

While the theoretical foundations of this problem are well-established, practical implementations face a significant bottleneck: memory. Standard approaches require $O(n)$ space to maintain weights for every expert. In contexts involving millions of features or models, this storage requirement becomes prohibitive. This paper investigates the memory-regret tradeoff: if an agent is restricted to space $S < n$, what is the minimum achievable regret? The authors explore this question across two primary adversarial models: oblivious adversaries (where losses are fixed in advance) and adaptive adversaries (where losses can change based on the agent's past actions).

Algorithmic Framework

To address the memory constraint, the authors introduce several novel algorithmic components designed to manage a dynamic "pool" of experts within limited space.

The Covering Benchmark and Monocarpic Experts

For oblivious adversaries, the challenge lies in deciding which experts to evict when memory is full. The authors utilize a "Covering Benchmark," comparing an expert's performance against a hypothetical algorithm that can switch between experts. If an expert is "covered" (outperformed) by the existing pool, it is deemed redundant and evicted.

To manage this process, the paper introduces Monocarpic Experts. In this variant of the "sleeping experts" problem, experts enter and exit the memory pool exactly once. By developing a low-memory algorithm for this specific setting, the authors can provide robust regret guarantees over discrete time intervals, which are then aggregated to cover the full horizon $T$.

Handling Adaptive Adversaries

Against adaptive adversaries, the eviction process itself can be exploited. To counter this, the authors propose a two-pronged strategy:

  1. RandomExpert Procedure: This samples small subsets of experts to handle short-term adversarial shifts.
  2. LongExpert Procedure: This identifies and tracks experts that demonstrate sustained performance over long durations.

These procedures are combined with a robust merging technique and amortization to ensure that the cost of "bad epochs" (where the best expert might not be in memory) does not dominate the total regret.

The Fundamental Limit of Adaptive Learning

One of the paper's most significant contributions is the discovery of a "hard floor" for memory against adaptive opponents. While the tradeoff for oblivious adversaries is continuous (where increasing memory $S$ consistently reduces regret), adaptive adversaries present a phase transition at $S \approx \sqrt{n}$.

Using a reduction from Set Disjointness in communication complexity, the authors prove that any algorithm with less than $\Omega(\sqrt{n})$ memory can be forced into suffering linear regret ($O(T)$). In this scenario, the agent essentially "forgets" which experts are performing well faster than it can identify them, allowing the adversary to systematically trick the agent. This establishes $\sqrt{n}$ as the fundamental memory requirement for any meaningful learning in adaptive environments.

Key Results and Insights

Adversary Type Memory ($S$) Regret Bound
Oblivious $S < n$ $\tilde{O}(\sqrt{nT/S})$
Adaptive $S \ge \sqrt{n}$ $o(T)$ (Vanishing Regret)
Adaptive $S < \sqrt{n}$ $\Omega(T)$ (Linear Regret)
  • Optimal Scaling: For oblivious adversaries, the $\sqrt{nT/S}$ scaling matches known lower bounds up to polylogarithmic factors, confirming that memory and regret are directly tradable.
  • Oblivious vs. i.i.d.: The results show that oblivious adversaries do not impose a higher memory-regret penalty than the simpler i.i.d. setting (where losses are drawn from a fixed distribution), a fact previously unproven for the sublinear memory regime.
  • The Adaptive Barrier: The $\sqrt{n}$ lower bound provides a definitive answer to the limits of sublinear memory in robust online learning.

Limitations and Future Directions

While this work provides a near-complete characterization for the full-feedback setting, several avenues remain open:

  • Bandit Feedback: A major challenge is extending these bounds to the bandit setting, where the agent only observes the loss of the chosen expert rather than the entire vector of losses.
  • Structural Exploitation: The current bounds are worst-case. Future research could investigate whether structural assumptions (such as low Littlestone dimension) allow algorithms to bypass the $\sqrt{n}$ barrier for adaptive adversaries.
  • Algorithmic Efficiency: While the proposed algorithms are computationally efficient in terms of memory, the polylogarithmic factors in the regret bounds are currently high (e.g., $O(\log^{20} n)$). Optimizing these constants would be necessary for practical deployment in production systems.

Summary updated

BibTeX
@inproceedings{peng2023near,
  author = {Binghui Peng and Aviad Rubinstein},
  title = {{Near Optimal Memory-Regret Tradeoff for Online Learning}},
  booktitle = {FOCS},
  year = {2023},
  doi = {10.1109/focs57990.2023.00069},
}
Figure