asha.hpp File Reference

ASHA (Asynchronous Successive Halving Algorithm; Li, Jamieson, Rostamizadeh, Gonina, Hardt, Recht, Talwalkar, "A System for Massively Parallel Hyperparameter Tuning," MLSys 2020): unlike synchronous Successive Halving/Hyperband (which process one full rung across every candidate before any candidate advances to the next), ASHA promotes a candidate to the next rung as soon as it qualifies (its metric is in the top 1/eta fraction of every candidate that has ever completed that rung so far), never waiting on the rest of the current rung's population. More...

#include <algorithm>
#include <functional>
#include <limits>
#include <memory>
#include <stdexcept>
#include <vector>
#include "pulsatrix/successive_halving.hpp"

Include dependency graph for asha.hpp:

Go to the source code of this file.

Classes
struct	pulsatrix::ASHAResult
	The best configuration/metric found, the total epoch budget spent, and how many distinct configurations were ever started (as opposed to promoted). More...
struct	pulsatrix::detail::ASHACandidate

Namespaces
namespace	pulsatrix
namespace	pulsatrix::detail

Functions
ASHAResult	pulsatrix::RunASHAOnConfigQueue (std::vector< Configuration > config_queue, const TrialFactory &make_trial, int initial_epoch_budget, double eta, int num_rungs)
	Runs ASHA, drawing new configurations from an explicit, ordered queue (rather than sampling indefinitely) – the pure, deterministic core; RunASHA (below) is the thin SearchSpace/RNG-sampling wrapper around it.
template<typename RNG >
ASHAResult	pulsatrix::RunASHA (const SearchSpace &space, const TrialFactory &make_trial, size_t max_configs_started, int initial_epoch_budget, double eta, int num_rungs, RNG &rng)
	RNG-driven wrapper: draws max_configs_started configurations from space via RandomSample to serve as the queue, then runs RunASHAOnConfigQueue.

Detailed Description

ASHA (Asynchronous Successive Halving Algorithm; Li, Jamieson, Rostamizadeh, Gonina, Hardt, Recht, Talwalkar, "A System for Massively Parallel Hyperparameter Tuning," MLSys 2020): unlike synchronous Successive Halving/Hyperband (which process one full rung across every candidate before any candidate advances to the next), ASHA promotes a candidate to the next rung as soon as it qualifies (its metric is in the top 1/eta fraction of every candidate that has ever completed that rung so far), never waiting on the rest of the current rung's population.

Note

This codebase's HPO loops are all single-threaded/sequential (no genuine parallel workers) – what "asynchronous" means concretely here is the algorithmic distinction from synchronous Successive Halving: promotion decisions are made opportunistically against the current state of every rung, one action (promote one candidate, or start one new one) per step, never gated on a full population finishing a rung together. This is the real mechanism ASHA is named for, independent of whether it runs across literal parallel workers or one sequential loop.