Online Learning: Stochastic and Constrained Adversaries

Alexander Rakhlin, Karthik Sridharan, Ambuj Tewari

Abstract

Classical learning theory often bifurcates into two extremes: the optimistic i.i.d. setting and the pessimistic worst-case online setting. This paper bridges this gap by introducing a unified theoretical framework for online learning against adversaries that are neither perfectly random nor completely malicious. By developing the concept of "distribution-dependent sequential Rademacher complexity," the authors demonstrate that many problems deemed "unlearnable" in worst-case scenarios—such as learning half-spaces—become tractable when the adversary’s actions are subject to even minor constraints or environmental noise.

Introduction

In learning theory, researchers typically operate within two distinct paradigms. The first is the classical statistical (i.i.d.) setting, where data points are drawn independently from a fixed distribution. While mathematically elegant, this model is often too optimistic for volatile real-world applications like high-frequency finance or robotics. The second is worst-case online learning, where a malicious adversary selects the most difficult data point at every step to maximize the learner's regret. This model is frequently too pessimistic, leading to "unlearnability" results for relatively simple models.

The gap between these two extremes is significant. Real-world data is rarely perfectly i.i.d., yet it is also rarely perfectly adversarial. This research addresses the lack of general tools to analyze the "in-between" scenarios where the adversary is restricted by physical constraints, budgets, or environmental noise.

Methodology: A Unified Analytical Framework

The authors treat online learning as a zero-sum game between a Learner and an Adversary (Nature) and analyze its minimax value. The primary technical contribution is a new analytical tool: Distribution-Dependent Sequential Rademacher Complexity.

Key technical components of this framework include:

  • Sequential Symmetrization: This is an extension of the classical symmetrization technique used in batch learning. It introduces "tangent sequences" to handle the temporal dependencies inherent in sequential data.
  • Tree-Based Complexity: Because online learning involves a sequence of moves and counter-moves, the authors represent the data-generating process as a probability tree rather than a static set.
  • Minimax Duality: By applying minimax theorems, the authors show that the optimal strategy for the learner can be determined by analyzing the "worst" restricted distribution the adversary is permitted to play.

Key Insights: The Spectrum of Adversaries

The paper formalizes a spectrum of adversarial behavior, providing a more granular view of online challenges:

  1. Worst-case: No restrictions; the adversary has total freedom.
  2. Constrained: The adversary has a "budget" (e.g., they cannot move too far from their previous choice).
  3. Smoothed: Adversarial choices are corrupted by a small amount of noise.
  4. i.i.d.: The adversary is forced to sample from a fixed, static distribution.

The Power of Smoothing

A major "aha moment" in the paper is the application of smoothed analysis. In a worst-case model, learning a simple threshold function (a half-space) is impossible if the adversary can pick points with infinite precision. However, the authors prove that if even an exponentially small amount of noise is added to the adversary's choices, the problem suddenly becomes learnable. This suggests that many "unlearnability" results in online settings are actually artifacts of unrealistic adversarial precision rather than inherent flaws in the models themselves.

Features vs. Labels

In the context of supervised learning, the authors find that the complexity of the problem is primarily driven by the selection of features ($x$). If the features are i.i.d., the problem remains learnable even if the labels ($y$) are chosen by a malicious adversary. Furthermore, they prove that online learnability against an i.i.d. adversary is fundamentally equivalent to classical batch learnability, effectively bridging the two major branches of the field.

Principal Results

  • Unified Regret Bound: The authors provide a general upper bound on minimax regret (Theorem 3) that scales with their new Rademacher complexity measure, applicable across the entire spectrum of adversaries.
  • Variance-Type Bounds: For "budgeted" adversaries—those who cannot change their moves significantly on average—the authors derive regret bounds that depend on the total variation of the adversary's sequence, rather than just the number of rounds $T$.
  • Half-Space Learnability: They prove that for a worst-case adversary corrupted by uniform noise $Unif[-\gamma/2, \gamma/2]$, the regret for learning half-spaces is bounded by $O(\sqrt{T \log(1/\gamma)})$. Without this noise ($\gamma=0$), the regret would be linear, rendering the problem unlearnable.

Limitations and Future Directions

As a work of pure theory, this paper establishes that certain problems are learnable (i.e., a strategy exists), but it does not always provide a computationally efficient algorithm to achieve the theoretical bounds. For the smoothed half-space result, the authors suggest an exponential weights algorithm on a discretized interval, but high-dimensional scenarios may require more sophisticated algorithmic approaches.

Future research may explore more complex "hybrid" scenarios and use these tools to compare the relative "power" of different adversarial constraints in a more granular way, potentially leading to more robust algorithms for real-world machine learning systems.

Summary updated

Abstract

Learning theory has largely focused on two main learning scenarios. The first is the classical statistical setting where instances are drawn i.i.d. from a fixed distribution and the second scenario is the online learning, completely adversarial scenario where adversary at every time step picks the worst instance to provide the learner with. It can be argued that in the real world neither of these assumptions are reasonable. It is therefore important to study problems with a range of assumptions on data. Unfortunately, theoretical results in this area are scarce, possibly due to absence of general tools for analysis. Focusing on the regret formulation, we define the minimax value of a game where the adversary is restricted in his moves. The framework captures stochastic and non-stochastic assumptions on data. Building on the sequential symmetrization approach, we define a notion of distribution-dependent Rademacher complexity for the spectrum of problems ranging from i.i.d. to worst-case. The bounds let us immediately deduce variation-type bounds. We then consider the i.i.d. adversary and show equivalence of online and batch learnability. In the supervised setting, we consider various hybrid assumptions on the way that x and y variables are chosen. Finally, we consider smoothed learning problems and show that half-spaces are online learnable in the smoothed model. In fact, exponentially small noise added to adversary's decisions turns this problem with infinite Littlestone's dimension into a learnable problem.
BibTeX
@misc{rakhlin2011online,
  author = {Alexander Rakhlin and Karthik Sridharan and Ambuj Tewari},
  title = {{Online Learning: Stochastic and Constrained Adversaries}},
  year = {2011},
  eprint = {1104.5070},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1104.5070},
}
Figure