FIESTA: Fast IdEntification of State-of-The-Art models using adaptive bandit algorithms

Henry B. Moss, Andrew Moore, David S. Leslie, Paul Rayson

Abstract

We present FIESTA, a model selection approach that significantly reduces the computational resources required to reliably identify state-of-the-art performance from large collections of candidate models. Despite being known to produce unreliable comparisons, it is still common practice to compare model evaluations based on single choices of random seeds. We show that reliable model selection also requires evaluations based on multiple train-test splits (contrary to common practice in many shared tasks). Using bandit theory from the statistics literature, we are able to adaptively determine appropriate numbers of data splits and random seeds used to evaluate each model, focusing computational resources on the evaluation of promising models whilst avoiding wasting evaluations on models with lower performance. Furthermore, our user-friendly Python implementation produces confidence guarantees of correctly selecting the optimal model. We evaluate our algorithms by selecting between 8 target-dependent sentiment analysis methods using dramatically fewer model evaluations than current model selection approaches.

Introduction: The Reliability Crisis in Model Selection

In the race to claim "State-of-the-Art" (SOTA) status in Natural Language Processing (NLP), researchers face a reliability crisis. Model performance is inherently noisy due to two main factors: data stochasticity (performance varies by train-test split) and model stochasticity (sensitivity to random seeds for initialization and shuffling).

To be truly reliable, a researcher should evaluate a model over many different seeds and data splits. However, as models grow larger, running every candidate 10 or 20 times becomes computationally prohibitive. Most researchers settle for a "non-adaptive" approach: either running a single evaluation, which is unreliable, or running every model a fixed number of times, which is wasteful. As shown in Figure 1, relying on a single fixed split can lead to misleading conclusions, as the relative ranking of models can flip depending on the specific data partition used.

Figure 1: Performance variation across different seeds and data splits. The right panels show how rankings can shift between different fixed splits compared to the aggregate distribution on the left.

Methodology: Model Selection as a Multi-Armed Bandit Problem

FIESTA frames model selection as a Multi-Armed Bandit (MAB) problem—specifically "Best-Arm Identification." In this analogy, each model is an "arm" of a slot machine, and an evaluation (a train/test run) provides a noisy "reward." The goal is to find the arm with the highest mean reward as quickly as possible. The paper introduces three adaptive algorithms:

  • Sequential Halving (SH): Designed for a Fixed Budget scenario. It operates in rounds, evaluating all remaining models and discarding the bottom 50% in each round to focus resources on top contenders.
  • Top-Two Thompson Sampling (TTTS): Designed for a Fixed Confidence scenario. It maintains a mathematical "belief" about which model is best and chooses the next model to evaluate by comparing the current leader against a likely challenger.
  • Batch Thompson Sampling (BTS): An extension of TTTS that allows for parallel evaluations on modern GPU clusters.

Experimental Setup

The authors evaluated FIESTA on a Target-Dependent Sentiment Analysis (TDSA) task using the SemEval 2014 Task 4 Restaurant dataset. They compared 8 to 12 different model configurations, including architectures like ATAE, IAN, and TDLSTM, along with variants using different word embeddings and dropout settings to simulate a realistic, crowded leaderboard.

Key Results and Efficiency Gains

FIESTA demonstrates that to find a winner, you don't need to measure the losers precisely. By stopping evaluations of poor models early, FIESTA achieves significant efficiency gains:

  • Efficiency: In Fixed Confidence tests, the TTTS algorithm reached target confidence using roughly half the evaluations (130 vs 281) required by standard non-adaptive approaches.
  • Accuracy: For a fixed computational budget, Sequential Halving was significantly more likely to identify the true best model. As shown in Figure 2, at a budget of 204 evaluations, FIESTA picked the correct winner 99% of the time, compared to only 85% for the standard method.
Figure 2: Probability of selecting the optimal model under fixed budget constraints. Sequential Halving consistently outperforms non-adaptive baselines.

Discussion and Future Work

FIESTA provides a formal confidence level ($1-\delta$), giving researchers a statistical basis for SOTA claims. While the current implementation assumes Gaussian performance distributions, it proves highly effective in real-world engineering environments, even when running models in parallel batches. Future work may involve integrating FIESTA directly into hyperparameter optimization processes and developing versions robust to extreme evaluation outliers.

Summary updated

Abstract

We present FIESTA, a model selection approach that significantly reduces the computational resources required to reliably identify state-of-the-art performance from large collections of candidate models. Despite being known to produce unreliable comparisons, it is still common practice to compare model evaluations based on single choices of random seeds. We show that reliable model selection also requires evaluations based on multiple train-test splits (contrary to common practice in many shared tasks). Using bandit theory from the statistics literature, we are able to adaptively determine appropriate numbers of data splits and random seeds used to evaluate each model, focusing computational resources on the evaluation of promising models whilst avoiding wasting evaluations on models with lower performance. Furthermore, our user-friendly Python implementation produces confidence guarantees of correctly selecting the optimal model. We evaluate our algorithms by selecting between 8 target-dependent sentiment analysis methods using dramatically fewer model evaluations than current model selection approaches.
BibTeX
@inproceedings{moss2019fiesta,
  author = {Henry B. Moss and Andrew Moore and David S. Leslie and Paul Rayson},
  title = {{FIESTA: Fast IdEntification of State-of-The-Art models using adaptive bandit algorithms}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
  url = {https://openreview.net/forum?id=m9jPkO-Hu13},
}
Figure