No Regret Bound for Extreme Bandits

Robert Nishihara, David Lopez-Paz, Léon Bottou

Abstract

Algorithms for hyperparameter optimization abound, all of which work well under different and often unverifiable assumptions. Motivated by the general challenge of sequentially choosing which algorithm to use, we study the more specific task of choosing among distributions to use for random hyperparameter optimization. This work is naturally framed in the extreme bandit setting, which deals with sequentially choosing which distribution from a collection to sample in order to minimize (maximize) the single best cost (reward). Whereas the distributions in the standard bandit setting are primarily characterized by their means, a number of subtleties arise when we care about the minimal cost as opposed to the average cost. For example, there may not be a well-defined “best” distribution as there is in the standard bandit setting. The best distribution depends on the rewards that have been obtained and on the remaining time horizon. Whereas in the standard bandit setting, it is sensible to compare policies with an oracle which plays the single best arm, in the extreme bandit setting, there are multiple sensible oracle models. We define a sensible notion of “extreme regret” in the extreme bandit setting, which parallels the concept of regret in the standard bandit setting. We then prove that no policy can asymptotically achieve no extreme regret.

Introduction

In the landscape of machine learning, hyperparameter optimization (HPO) remains a critical yet challenging task. While various sophisticated algorithms exist, practitioners often rely on Random Search due to its simplicity and theoretical guarantees. However, a meta-problem arises: which search space (distribution) should one sample from? For instance, should a learning rate be sampled from a uniform or a log-uniform distribution?

This paper investigates this challenge through the lens of the Extreme Bandit setting. Unlike standard multi-armed bandits, where the goal is to maximize the cumulative or average reward, extreme bandits focus on the single best outcome (the "extreme" value) found across all trials. The authors present a surprising impossibility result: without strong assumptions about the underlying distributions, no strategy can guarantee "no regret" performance. In the worst case, any automated policy will be fundamentally slower than an ideal oracle.

The Extreme Bandit Framework

In a standard bandit problem, an agent pulls arms to maximize the expected mean. In HPO, however, we do not care about the average performance of our trials; we only care about the single trial that yielded the lowest validation error. This shift in objective changes the fundamental nature of the "best" arm.

In the extreme setting, the optimal distribution to sample from is not static. It depends heavily on the remaining time horizon and the best value observed so far. A distribution that frequently yields "good" results might be preferable for a short-term budget, while a distribution with a heavy tail—capable of producing rare, exceptional results—might be better if the budget allows for thousands of samples. This "moving target" makes the identification of a single best distribution impossible without knowing the total number of samples in advance.

Defining Extreme Regret

To quantify performance, the authors introduce the concept of Extreme Regret. In standard bandits, regret is typically the difference between the reward of the best arm and the reward of the chosen policy. In the extreme setting, the authors propose a temporal measure: the ratio of time horizons.

If an oracle requires $T$ samples to reach a specific error threshold $\alpha$, and a given policy requires $T'$ samples to reach that same threshold, the extreme regret is defined as the ratio $T'/T$. A "no extreme regret" policy would be one where this ratio approaches 1 as the time horizon $T$ goes to infinity.

The Impossibility Result

The core contribution of this work is Theorem 11, a mathematical proof that "no extreme regret" is unachievable in the extreme bandit setting.

Using a probabilistic construction, the authors demonstrate that for any sampling policy $\pi$, there exists a set of $K$ distributions such that the extreme regret is at least $K$. The proof involves:

  1. Defining a sequence of increasingly difficult target values ($\alpha_i$).
  2. Constructing "difficult" distributions where specific arms are only optimal within narrow, specific time windows.
  3. Showing that any policy can be "tricked" into wasting samples on sub-optimal arms, forcing the time-ratio regret to scale with the number of available distributions.

This implies that in the worst-case scenario, an automated strategy for selecting hyperparameter distributions will be at least $K$ times slower than an oracle that knows which distribution to prioritize for a given budget.

Key Insights

The Rule of 59

The paper highlights a frequentist baseline often overlooked in complex HPO discussions: the Rule of 59. This rule states that by taking 59 random samples from any distribution, there is a 95% chance of landing in the top 5% of all possible outcomes for that distribution. This distribution-agnostic guarantee serves as a benchmark that many sophisticated algorithms struggle to significantly outperform without additional structural knowledge.

Mixed Strategies

One of the more counter-intuitive findings is that a mixed strategy—sampling from multiple distributions simultaneously—can outperform any strategy that attempts to converge on a single "best" arm. Because the optimal arm changes based on the current best-found value and the remaining budget, maintaining a portfolio of distributions is often more robust than traditional "winner-take-all" bandit approaches.

Conclusion and Future Work

This research establishes a fundamental lower bound for hyperparameter optimization. It proves that the search space for HPO is too vast to master through pure exploration if the shapes of the distribution tails are unknown.

However, the authors note that this is a worst-case result. Real-world hyperparameter surfaces are rarely designed by an adversary to exploit these theoretical weaknesses; they often possess structural properties like smoothness or quasiconvexity. The path forward for the field lies in identifying and formalizing these realistic assumptions. By defining what a "typical" hyperparameter surface looks like, researchers may be able to develop algorithms that bypass this impossibility result and provably outperform simple random search.

Summary updated

Abstract

Algorithms for hyperparameter optimization abound, all of which work well under different and often unverifiable assumptions. Motivated by the general challenge of sequentially choosing which algorithm to use, we study the more specific task of choosing among distributions to use for random hyperparameter optimization. This work is naturally framed in the extreme bandit setting, which deals with sequentially choosing which distribution from a collection to sample in order to minimize (maximize) the single best cost (reward). Whereas the distributions in the standard bandit setting are primarily characterized by their means, a number of subtleties arise when we care about the minimal cost as opposed to the average cost. For example, there may not be a well-defined “best” distribution as there is in the standard bandit setting. The best distribution depends on the rewards that have been obtained and on the remaining time horizon. Whereas in the standard bandit setting, it is sensible to compare policies with an oracle which plays the single best arm, in the extreme bandit setting, there are multiple sensible oracle models. We define a sensible notion of “extreme regret” in the extreme bandit setting, which parallels the concept of regret in the standard bandit setting. We then prove that no policy can asymptotically achieve no extreme regret.
BibTeX
@inproceedings{nishihara2016no,
  author = {Robert Nishihara and David Lopez-Paz and Léon Bottou},
  title = {{No Regret Bound for Extreme Bandits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=zRPigG35GS},
}
Figure