PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-stochastic Best Arm Identification and Hyperparameter Optimization

Kevin Jamieson, Ameet Talwalkar

arXiv:1502.07943v1cs.LGstat.ML

TL;DR

The paper addresses the lack of a best-arm identification framework for non-stochastic loss sequences, a setting motivated by hyperparameter optimization. It analyzes Successive Halving and applies the formulation to iterative machine-learning training, finding comparable test accuracies an order of magnitude faster than baselines. The approach remains agnostic to unknown convergence-rate functions, whose tight bounds can be difficult to construct.

  • Problem

    Best-arm identification had been studied in the stochastic but not the non-stochastic setting, despite hyperparameter optimization involving convergent, potentially irregular loss sequences.

  • Method

    The paper analyzes Successive Halving for non-stochastic best-arm identification and maps hyperparameter settings to arms whose intermediate training losses guide resource allocation.

  • Results

    Comparable test accuracies are typically achieved an order of magnitude faster than baseline methods by allocating more resources to promising hyperparameter settings.

  • Takeaways & Limitations

    The framework provides a general bandit-based approach for hyperparameter optimization that adapts to how quickly arms’ losses converge without changing the algorithm.

  • Takeaways & Limitations

    Tight bounds for the convergence functions γi are difficult to construct outside very simple problems and may contain unspecified constants.

Abstract

from arXiv · show

Motivated by the task of hyperparameter optimization, we introduce the non-stochastic best-arm identification problem. Within the multi-armed bandit literature, the cumulative regret objective enjoys algorithms and analyses for both the non-stochastic and stochastic settings while to the best of our knowledge, the best-arm identification framework has only been considered in the stochastic setting. We introduce the non-stochastic setting under this framework, identify a known algorithm that is well-suited for this setting, and analyze its behavior. Next, by leveraging the iterative nature of standard machine learning algorithms, we cast hyperparameter optimization as an instance of non-stochastic best-arm identification, and empirically evaluate our proposed algorithm on this task. Our empirical results show that, by allocating more resources to promising hyperparameter settings, we typically achieve comparable test accuracies an order of magnitude faster than baseline methods.

1. Introduction

The paper frames hyperparameter optimization as a non-stochastic best-arm identification problem, motivated by variable intermediate model quality and costly full training or evaluation. It proposes analyzing a bandit algorithm that can terminate poor settings early and reports order-of-magnitude speedups in empirical studies.

  • Motivation: Iterative training exposes intermediate losses, and hyperparameter settings can produce highly variable model quality before convergence.This motivates evaluating and terminating settings online rather than waiting for every model to train fully.
  • Related work: Most existing hyperparameter optimization methods treat training as a black box and evaluate models only after convergence.Some methods exploit intermediate results but require convergence-rate forms that are difficult to characterize broadly.
  • Problem: The paper identifies a gap in bandit research: best-arm identification had not adequately addressed the non-stochastic setting relevant to hyperparameter optimization.The setting includes loss sequences without known convergence rates and potentially nonmonotone, nonsmooth behavior.
  • Problem: Validation-loss computation can be drastically more expensive than a single training iteration, making the number of observed losses an important cost.This cost asymmetry is central to resource allocation for partially trained models.
  • Contributions: The paper studies a general non-stochastic bandit setting, analyzes a suitable algorithm, and empirically evaluates it for hyperparameter optimization.The reported experiments demonstrate order-of-magnitude speedups relative to standard baselines on real-world supervised-learning problems and datasets.
  • Scope: The setting extends beyond hyperparameter optimization to stochastic best-arm identification, max-bandits, feature-subset selection, and related optimization problems lacking i.i.d. assumptions.The paper organizes the setting, analysis, hyperparameter-optimization formulation, and experiments across subsequent sections.

2. Non-stochastic best arm identification

The paper defines non-stochastic best-arm identification for loss sequences generated independently of the algorithm, then explains why unknown convergence rates make identification difficult. It motivates Successive Halving and emphasizes loss-observation cost alongside total arm pulls.

  • Setting: Best-arm identification seeks the arm with the best average or limiting performance, unlike exploration-versus-exploitation, which optimizes cumulative payoff.The paper focuses on the non-stochastic best-arm objective, for which it reports no prior treatment in the literature.
  • Setting: The generalized formulation observes one arm’s loss while evaluating the algorithm on a separately chosen recommendation.This distinguishes identification from cumulative-regret settings, where the played arm is also the evaluated arm.
  • Assumptions: Loss sequences are generated by an oblivious adversary, so they are independent of the algorithm’s actions.The paper contrasts this assumption with an adaptive adversary that can change future losses based on prior plays.
  • Stochastic and non-stochastic settings: The stochastic formulation uses i.i.d. losses with constant means, whereas the non-stochastic formulation assumes convergent sequences with limiting values.Stochastic losses can be transformed into the non-stochastic framework through cumulative averages, and analogous constructions apply to statistics such as minima or maxima.
  • Challenges: Unknown convergence rates prevent reliable finite-time identification: an arm may never be safely rejected or verified as best or within ϵ of best.The convergence envelope γi(t) may decay arbitrarily slowly, so knowing that a limit exists is insufficient for a usable rate.
  • Algorithms and costs: Successive Halving is adopted because fixed-budget algorithms have attributes suited to the non-stochastic setting, while its analysis must be developed separately.The framework also tracks observed losses because evaluating an intermediate model can cost much more than pulling an arm.

3. Proposed algorithm and analysis

The paper analyzes Successive Halving for non-stochastic best-arm identification, using convergent but otherwise unknown loss sequences to characterize when it identifies the best arm. Its analysis compares resource allocation with uniform sampling and shows substantially better worst-case scaling in a representative setting.

  • Proposed algorithm: Successive Halving repeatedly allocates a fixed budget across surviving arms, evaluates them, removes the worst half, and continues until one arm remains.The algorithm was originally proposed for stochastic best-arm identification but is also applicable to the non-stochastic setting.
  • Analysis of Successive Halving: The analysis defines each arm’s limiting loss ν_i and non-increasing approximation envelope γ_i(t), then uses inverse envelopes to relate intermediate losses to final-arm ordering.If the envelopes are sufficiently small relative to the gap between final values, comparing intermediate values suffices to determine the ordering.
  • Analysis of Successive Halving: If the budget B exceeds the theorem’s threshold z, Successive Halving returns the best arm.The threshold sums the required sampling effort across competing arms and is suggested to be nearly minimax-tight up to logarithmic factors.
  • Examples and adaptivity: For feature selection, convergence bounds depending on subset condition numbers yield a sufficient budget for identifying the best arm, although tight γ_i bounds are difficult outside simple problems.Because the algorithm is agnostic to the γ_i functions, faster loss convergence leads to faster discovery without changing the algorithm.
  • Comparison to uniform allocation: The uniform strategy can fail under a budget condition that is necessary in the worst case, while Successive Halving’s sufficient effort behaves like (n −1) log_2(n) times an average inverse-envelope term.The corresponding uniform-strategy necessity scales with n times the maximum inverse-envelope term.
  • Comparison to uniform allocation: With ν_a = a/n and equal σ_a, Successive Halving needs essentially 4n log_2(n) resources versus n^2 for uniform allocation.The comparison exposes the worst-case gap between eliminating poor arms and allocating the same budget to every arm.
  • A pretty good arm: For an ϵ-good arm, unknown convergence envelopes prevent direct guarantees of ϵ-optimality, but Successive Halving has a fallback guarantee no worse than uniform allocation.In the feature-selection example, both methods achieve bν_i − ν_1 ≤ eO(n/B), while experiments observe order-of-magnitude speedups for Successive Halving.

4. Hyperparameter optimization for supervised learning

The paper formalizes supervised-learning hyperparameter optimization by treating hyperparameter settings as arms whose iterative validation losses can be evaluated over time. This transformation enables adaptive resource allocation across settings, while retaining the train–validate–test workflow and acknowledging technical assumptions about loss convergence.

  • Supervised learning uses hyperparameters to index models produced by a fixed algorithm A on training data.For each θ, the model is f_θ = A(TRAIN, θ).
  • The standard workflow partitions data into TRAIN, VAL, and TEST, trains one model per hyperparameter setting, selects the lowest validation-loss setting, and reports test loss.The selection criterion is empirical loss on VAL.
  • The paper seeks to exploit intermediate results because model selection over hyperparameters can be non-continuous and non-convex even when each fixed-setting model is efficiently computed iteratively.The approach is intended as a robust, principled alternative to methods that require explicit convergence-rate functions.
  • Because the learning algorithm is iterative, each hyperparameter setting produces intermediate models and a sequence of validation losses before convergence.The paper assumes that the limiting validation loss exists.
  • The resulting formulation samples candidate settings as arms and applies non-stochastic best-arm identification to allocate resources across them.Arms are generated uniformly within valid hyperparameter ranges, possibly on a log scale.
  • The approach fixes the candidate hyperparameter settings and adaptively allocates budget among them, complementing methods that adaptively choose settings.The paper identifies adaptive arm selection as future work rather than part of the presented formulation.

5. Experiment results

The experiments compare search algorithms for supervised-learning hyperparameter optimization under fixed iteration budgets. Successive Halving achieves a substantial wall-clock advantage on kernel SVM while matching low error.

  • Experimental setup: The study compares the proposed algorithm with uniform allocation and other search methods across supervised-learning hyperparameter optimization problems.Search algorithms divide a fixed total iteration budget among candidate arms; experiments use doubling budgets without warm starts.
  • Experimental setup: Experiments use training, validation, and test partitions, with all plots reporting loss on the test error.Datasets are split 90/10 into training-base and test data, then training-base is split 80/20 into training and validation data.
  • Ridge Regression: Ridge regression evaluates 10 randomly selected λ values from [10^-6, 100] on the Million Song Dataset year prediction task across 32 trials.The regularization hyperparameter is sampled uniformly on a log scale, and ridge regression is trained with stochastic gradient descent.
  • Kernel SVM: More than an order of magnitude faster, Successive Halving reaches the same low kernel-SVM error as uniform allocation and Successive Rejects in wall-clock time.Successive Halving and Successive Rejects perform comparably in iterations, so the reported separation is specifically in wall-clock time.
  • Matrix Completion: Matrix completion uses 64 arms formed from rank, regularization, and initialization hyperparameters, with 32 experimental trials.The Movielens 100k experiment samples d and σ linearly and λ logarithmically; each hyperparameter receives four samples.

6. Future directions

The authors identify richer convergence-aware analyses and switching costs as directions for extending the framework. These extensions would account for arm-specific rates and the cost of moving large intermediate models.

  • Future directions: Future analyses could use each arm’s specific convergence rate γi(t), analogous to modeling different variances in stochastic bandits.The current theoretical results are expressed using maxi γi(t), rather than arm-specific convergence rates.
  • Future directions: Pairwise switching costs could model the time required to move very large intermediate models in and out of memory between iterations.

A. Proof of Theorem 1

The proof establishes Theorem 1 by contradiction: assuming Successive Halving fails, it constructs nested subsets of possible loss sequences and shows the final subset is empty when B exceeds z.

  • Proof of Theorem 1: The proof fixes infinitely long loss sequences with limits νi and defines the set Ω of all possible sequences satisfying those limits.The envelopes γi(t) are thereby fixed for all time, and the given loss sequence is an element of Ω.
  • Proof of Theorem 1: Assuming Successive Halving fails to identify the best arm, the proof constructs an increasing sequence of subsets of Ω.The argument begins with the singleton containing the observed loss sequence and uses the algorithm’s surviving-arm sets.
  • Proof of Theorem 1: The proof bounds arm-survival conditions using the maximum envelope γ encoded in Ω and relaxes an equality condition to an inequality.The relevant summation depends on the limiting losses νi, and the analysis considers subsets containing the first |S′k| arms.
  • Proof of Theorem 1: The budget quantity Rk is lower-bounded through the surviving-set sizes, with an intentional near-factor-of-two underestimate simplifying the expression.The resulting equality is stated to hold when B > z.
  • Proof of Theorem 1: The proof’s final contradiction follows because B > z implies the terminal surviving-arm set contains only the best arm.A related bound is described as looser but more interpretable, with both inequalities achievable for particular νi settings.

B. Proof of Theorem 2

The proof of Theorem 2 analyzes the output of uniform allocation on arbitrary loss sequences and concludes that, when B > z, uniform allocation identifies the best arm.

  • Proof of Theorem 2: The proof defines bi([ℓ′i,t]) as the output of the uniform allocation strategy for input loss sequences.
  • Proof of Theorem 2: When B > z, the proof uses bi([ℓi,t]) = 1 to establish the stated best-arm identification result for uniform allocation.

C. Proof of Theorem 3

The proof constructs time-varying loss sequences using a monotonically decreasing function β(t) that converges to zero. Under this construction, all arms have the same gap quantity γ_i(t)=γ̄(t)=β(t).

  • The proof chooses an arbitrary monotonically decreasing function β(t) with limt→∞β(t)=0.
  • Losses are defined as ℓ1,t=ν1+β(t) for arm 1 and ℓi,t=νi−β(t) for every other arm.
  • The construction makes γ_i(t) and γ̄(t) equal to β(t) for all arms.

D. Proof of Theorem 4

The proof establishes a guarantee for the arm returned by the Successive Halving algorithm. It derives the result by examining arm eliminations and applying a trivial lower bound for R_k in the final step.

  • Theorem 4 guarantees a stated property for the arm returned by the Successive Halving algorithm in Figure 3.
  • The proof obtains the guarantee by inspecting how the algorithm eliminates arms.
  • The final proof step plugs in a trivial lower bound for R_k for every k.
Loading 1502.07943v1…