Best of Both Worlds Online Learning with Adversarial Corruption

This direction is merged into another direction: adversarial corruption robustness. Its last version stays readable and citable here.

Version 1 of 127 papers33 conceptsfrozen 2026-10-04

In classical online learning, researchers typically design algorithms for one of two extremes. In the stochastic setting, data is independent and identically distributed (i.i.d.), allowing algorithms to converge quickly by exploiting stability. In the adversarial setting, data is chosen by a malicious opponent, forcing algorithms to be cautious and pessimistic to avoid being misled.

However, real-world data is rarely purely one or the other. A system might be mostly stable but suffer from occasional sensor failures, malicious "poisoning" attacks, or sudden distribution shifts. A new line of research focuses on "Best-of-Both-Worlds" (BOBW) algorithms that automatically adapt to the environment's actual level of chaos without knowing it in advance.

The Corrupted Stochastic Model

The bridge between these two extremes is the corrupted stochastic model. In this framework, the environment is primarily stochastic, but an adversary is allowed a "corruption budget" $C$. This adversary can intercept the true feedback and replace it with arbitrary, even unbounded, values.

The goal is to achieve robustness: the algorithm should perform nearly as well as a specialized stochastic algorithm when $C$ is small, but its performance should degrade gracefully as $C$ increases, never performing worse than a standard adversarial algorithm.

Graceful Degradation and the Square Root of Corruption

A recurring discovery across this research is that the "cost" of corruption—measured as regret—often scales with the square root of the total corruption ($\sqrt{C}$).

Shinji Ito established fundamental limits in On Optimal Robustness to Adversarial Corruption in Online Decision Problems, proving that for multi-armed bandits and expert advice problems, the regret penalty scales with $\sqrt{C}$ rather than linearly. This sub-linear growth is crucial; it means that as long as the corruption is limited, the learner can still extract significant signal from the underlying stochastic process.

This pattern holds even in complex scenarios. For instance, in Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds, Shinji Ito and Kei Takemura demonstrate that linear bandits can achieve variance-adaptive bounds that simultaneously respect this $\sqrt{C}$ scaling.

Mechanisms for Robustness

How do these algorithms actually ignore the "noise" while following the "signal"? Several key mechanisms have emerged:

1. Hybrid Regularizers

Standard algorithms often use Follow-the-Regularized-Leader (FTRL). To achieve BOBW performance, researchers engineer specific regularizers that blend different properties. Liad Erez and Tomer Koren introduced a hybrid Tsallis-Shannon entropy regularizer in Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs, which allows the algorithm to switch its behavior based on the observed feedback.

2. Selective Filtering

Sometimes the best way to handle a corrupted data point is to ignore it entirely. In Robust Online Convex Optimization in the Presence of Outliers, Sarah Sachs, Tim van Erven, and colleagues show that a simple strategy of filtering out rounds with exceptionally large gradients can protect adaptive algorithms from being "poisoned" by adversarial outliers.

3. Directional Stability

When gradients are corrupted, their magnitude is often the most misleading component. Berkay Turan, Hoi To Wai, and Mahnoosh Alizadeh found that the Normalized Subgradient Method (NSM)—which ignores magnitude and only uses the direction of the gradient—is naturally robust to unbounded corruptions that occur intermittently (On Robustness of the Normalized Subgradient Method with Randomly Corrupted Subgradients).

Expanding the Horizon

The push for corruption-robustness is moving beyond simple bandits into structured decision-making:

By moving away from "worst-case" assumptions and toward "adaptive" robustness, this research direction provides a theoretical foundation for algorithms that are both efficient in practice and resilient under attack.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_best_of_both_worlds_online_learning_with_b5a486fa,
  title = {Best of Both Worlds Online Learning with Adversarial Corruption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/best-of-both-worlds-online-learning-with-adversarial-corruption/rdr_b5a486fae6104f8d9e8213f4f0ae0d44},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_best_of_both_worlds_online_learning_with_b5a486fa_v1,
  title = {Best of Both Worlds Online Learning with Adversarial Corruption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/best-of-both-worlds-online-learning-with-adversarial-corruption/rdr_b5a486fae6104f8d9e8213f4f0ae0d44/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}