Asynchronous Successive Halving
Algorithms AIMech:AsynchronousSuccessiveHalving DRAFT
Aliases: ASHA, Asynchronous Successive Halving Algorithm
An asynchronous resource-allocation algorithm that promotes promising completed hyperparameter trials through increasing resource levels as workers become available and starts new trials when no eligible promotion is available, without waiting for an entire evaluation stage to finish.
Identity Notes & Concept Scope
ASHA is the asynchronous promotion procedure, not every early-stopping scheduler, the complete distributed training system, or a synonym for Hyperband or BOHB. A rung contains evaluations at one resource level; a bracket sets the starting resource and rung schedule. Multiple ASHA brackets can implement asynchronous Hyperband, while a single ASHA bracket does not include that wrapper. The source’s bounded promotion variant is the primary scope here. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 259 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in both worktree and main checkout, returning 26 lines in each checkout. These were prior candidate leads, source references and neighboring-method mentions, not existing records for these identities. Nine exact AIO CLASS nodes with synonyms and outgoing edges and six neighboring native mechanisms were inspected. Absence is bounded to this snapshot and semantic neighborhood.
Claims & Grounded Evidence
1 Claim
Mechanism
#method
Choose minimum and maximum resources r and R, a reduction factor eta, and starting-level offset s. Resource at rung k is r*eta^(s+k). Dispatch work to free workers and record completed rung losses. In the author dissertation’s Algorithm 3, scan promotable rungs from the highest eligible level downward, stopping below the maximum-resource rung. At each level, consider the currently best approximately 1/eta fraction of completed configurations and select an eligible one that has not already been promoted. If the entire scan yields none, sample a new configuration for the base rung. Thus the starting cohort can grow and promotions do not wait for every job at a rung. Promoted configurations may later fall outside the hindsight top fraction as additional results arrive. Checkpointing can reuse a trial’s previous training; it is distinct from copying weights between different configurations. The maximum resource limits promotion depth in this bounded version.
⚠️ Curated Limitations & Negative Results
- The MLSys PDF’s Algorithm 2 places the new-trial fallback inside its descending-rung loop. The author’s dissertation Algorithm 3 places it after that loop, consistent with the method prose. The record follows the latter and retains the discrepancy; it does not claim byte-equivalent pseudocode or an author-issued erratum.
- The top-fraction notation does not specify every discrete rounding, tie or failed-job policy. The literal schedule reaches r*eta^floor(log_eta(R/r)), which equals R only when the ratio aligns with a power of eta; implementations must define any terminal-budget adjustment.
- Early rankings and completion order can affect promotions. The paper’s discussion of vanishing mispromotions is not imported as an unconditional theorem for dependent upper-rung observations. No universal parallel speedup or finite-budget optimum is asserted.
- Only the declared methods and dissertation pages were inspected. System-specific scheduling, autoscaling, benchmark results and executable implementations are outside this record’s claims.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:TrainingStrategy
TrainingStrategy
|
related_match | The hyperparameter-optimization use of this procedure selects training settings or allocates resources to candidate models. This relates it to AIO’s training-strategy concept without making the algorithm a preprocessing subclass or equating broader best-candidate selection with a machine-learning task. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Liam Li, Kevin Jamieson, Afshin Rostamizadeh, Ekaterina Gonina, Jonathan Ben-Tzur, Moritz Hardt, Benjamin Recht, Ameet Talwalkar
|
primary paper
full_text
|
sha256:a4d8b9809fbb…
|
author-thesis
|
Liam Li
|
author technical report
full_text
|
sha256:26efc5ddc883…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T11:42:59Z
Updated: 2026-10-11T11:42:59Z
Source File:
data/curated/AsynchronousSuccessiveHalving.yaml