Move from Perturbed scheme to exponential weighting average

Chunyang XiaoarXiv 2015 · OpenReview

Abstract

In online decision problems, an agent must make sequential choices from a pool of experts without prior knowledge of future costs. The objective is to minimize regret—the difference between the agent's total cost and that of the best-performing expert in hindsight. While Exponential Weighting (EW) has long been the standard for achieving optimal regret bounds, Follow the Perturbed Leader (FPL) has emerged as a computationally efficient alternative. This paper demonstrates that these two paradigms are not merely similar but can be mathematically identical. By employing a Gumbel distribution for perturbations, we show that FPL reduces exactly to EW. This equivalence allows for the application of EW’s theoretical guarantees to complex, structured problems where FPL’s optimization-based approach is more computationally feasible.

Introduction

The "prediction from expert advice" framework is a cornerstone of online learning. In this setting, an algorithm selects an expert at each time step $t$, observes a cost, and aims to perform nearly as well as the best expert in the pool. Historically, this has been addressed through two distinct lenses: the probabilistic approach of Exponential Weighting and the optimization-centric approach of Follow the Perturbed Leader.

Exponential Weighting (EW) assigns probabilities to experts based on an exponential function of their cumulative losses. While theoretically elegant, EW faces significant hurdles in structured environments—such as finding the shortest path in a large graph—where the number of experts (paths) grows exponentially with the size of the input. In contrast, Follow the Perturbed Leader (FPL) adds random noise to historical costs and selects the expert with the minimum perturbed cost. This transforms the learning problem into a standard "offline" optimization problem, which can often be solved efficiently using existing algorithms.

The Core Equivalence: The Gumbel Connection

The primary contribution of this work is bridging the gap between EW and FPL. The author investigates the probability ratios between experts in both schemes to identify the conditions under which they converge.

Algorithm 1: Exponential Weighting (EW)

In the weighted average scheme, the probability $P(e)$ of choosing expert $e$ is defined as: $$P(e) \propto e^{-\beta L_e}$$ where $L_e$ is the historical loss of expert $e$ and $\beta$ is the learning rate.

Algorithm 2: Follow the Perturbed Leader (FPL)

In the FPL scheme, the algorithm selects the expert $e$ that minimizes: $$\text{argmin}_e (L_e - p_e)$$ where $p_e$ is a random perturbation drawn from a specific distribution.

The "aha moment" of the paper lies in the selection of the Gumbel distribution. By leveraging a unique property of Gumbel-distributed random variables—specifically that the difference between two Gumbel variables follows a logistic distribution—the author proves Theorem 3. This theorem establishes that FPL using Gumbel perturbations is mathematically equivalent to EW with a learning rate $\beta' = 1/\beta$.

Decoupling Optimization from Learning

This equivalence is more than a mathematical curiosity; it provides a framework for "decoupling" the learning process. By using FPL, the problem is split into two distinct phases:

  1. The Perturbation Step: Introducing randomness (the "learning" component).
  2. The Optimization Step: Solving a deterministic problem (the "efficiency" component).

This decoupling allows researchers to utilize highly optimized "offline" solvers—such as the Bellman-Ford algorithm for shortest paths or Viterbi for sequence labeling—to solve online learning problems. Instead of maintaining a weight for every possible expert, one only needs to perturb the underlying components (e.g., edge weights in a graph) and run the solver.

Efficiency in Structured Problems

The paper highlights the Online Shortest Path Problem as a primary use case. In a graph where the number of paths is exponential relative to the number of edges, EW would require updating and storing a weight for every single path, which is computationally prohibitive.

However, by applying FPL with Gumbel noise to the edges rather than the paths, the algorithm can find the "exponentially weighted" path using a simple shortest-path oracle. This approach achieves the same theoretical regret bounds as EW but with a fraction of the computational overhead, demonstrating how FPL naturally extends to structured online problems.

Limitations and Future Outlook

While the Gumbel distribution provides a perfect bridge, the paper notes several areas for further exploration:

  • Distributional Mapping: The current work focuses on Uniform, Exponential, and Gumbel distributions. A broader framework mapping arbitrary distributions to specific weighting or penalization schemes remains an open question.
  • Practical Stability: The theoretical equivalence is clear, but the practical stability of sampling from Gumbel distributions in high-dimensional or non-linear cost environments (like Markov Random Fields in image segmentation) requires further empirical study.
  • Adversarial Models: The proofs assume a standard adaptive adversary. Future research could investigate how these equivalencies behave under more restrictive or specialized adversarial models.

Conclusion

By proving that Follow the Perturbed Leader is a generalization of Exponential Weighting, this paper provides a unified view of online learning. It justifies the use of perturbation-based methods not just as heuristics, but as theoretically sound algorithms that offer massive computational advantages for complex, structured decision-making tasks.

Summary updated

Abstract

In an online decision problem, one makes decisions often with a pool of decision sequence called experts but without knowledge of the future. After each step, one pays a cost based on the decision and observed rate. One reasonal goal would be to perform as well as the best expert in the pool. The modern and well-known way to attain this goal is the algorithm of exponential weighting. However, recently, another algorithm called follow the perturbed leader is developed and achieved about the same performance. In our work, we first show the properties shared in common by the two algorithms which explain the similarities on the performance. Next we will show that for a specific perturbation, the two algorithms are identical. Finally, we show with some examples that follow-the-leader style algorithms extend naturally to a large class of structured online problems for which the exponential algorithms are inefficient.
BibTeX
@misc{xiao2015move,
  author = {Chunyang Xiao},
  title = {{Move from Perturbed scheme to exponential weighting average}},
  year = {2015},
  eprint = {1512.07074},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1512.07074},
}
Figure